1

I'm playing around with FNV-1a hashing. I have a very simple implementation, which seems to work very well for 32 bit hashes and 64 bit hashes:

const ulong FNV_PRIME = 0x00000100000001B3;
const ulong FNV_OFFSETBASIS = 0xCBF29CE484222325;
ulong hash = FNV_OFFSETBASIS;

var fileContents = File.ReadAllBytes(@"D:\Some.iso");

foreach(var b in fileContents){
    hash ^= b;
    hash *= FNV_PRIME;
}

Console.WriteLine(hash);
Console.WriteLine(BitConverter.GetBytes(hash));

For the 32-bit hash, I used uint (32 bit integer). For the 64 bit hash, I'm using ulong (64 bit integer).

Now, I'd like to try the 128-bit variant. C# however, does not have a 128-bit integer type. Or does it? The .NET documentation for System.Guid clearly states (under "Remarks"):

A GUID is a 128-bit integer (16 bytes) that can be used across all computers and networks

So, why are they stating that it is a 128-bit integer? Can I do arithmetics on the type? I've tried, but I cannot seem to assign a number (such as the initial offset) to a type of System.Guid. I can't say that I'm that surprised, but I'm wondering why it is so clearly stated this is a "128-bit integer".

(One of the possible solutions for the original problem is obviously to use the System.Numerics.BigInteger library. I just came across this during my search and was wondering about the statement on MSDN).

Rainmaker
  • 173
  • 3
  • 13
  • 4
    For descriptive convenience, a value may be described as "an n-bit integer", but that does not imply that there is a specific type for that integer. I don't believe C# has a 128-bit integer type except, or course, as a BigInteger. – President James K. Polk Jun 12 '20 at 21:09
  • Your question is not very explicit,isn't converting it to [BigInteger](https://learn.microsoft.com/en-us/dotnet/api/system.numerics.biginteger?view=netcore-3.1) enough for you? – Gabriel Alexandre Jun 12 '20 at 21:19
  • As long as you have not completed your 6 year college math degree, base class [is here](https://learn.microsoft.com/en-us/dotnet/api/system.security.cryptography.hashalgorithm?view=netcore-3.1). Pick the derived one you like. – Hans Passant Jun 12 '20 at 22:31
  • @Polk: Thanks for the quick responses. I wasn't familiar with the term "n-bit integer" being a common term. "Size of object", "memory allocated" etc would be more descriptive in my opinion. @Gabriel; well, that works, obviously. But, I want this to be fast and scale up to billions. So I'm looking at whether I can do it more efficiently compared to an immutable type. I.e. Karatsuba algorithm or something. I know this is probably unnecessary micro-optimizing – Rainmaker Jun 13 '20 at 00:51

0 Answers0