5
\$\begingroup\$

A little over a year ago, I asked this question. Since then, I've implemented the larger bit variations and am looking for any and all feedback - performance is obviously key when talking about FNV-1a, but having maintainable code and being correct and decently unit-testable are also paramount.

GitHub

Base class Fnv1aBigBase (some method header documentation omitted for brevity):

public abstract class Fnv1aBigBase : HashAlgorithm
{
    /// <summary>
    /// The "wrap-around" modulo value for keeping multiplication within the number of bits.
    /// </summary>
    private readonly BigInteger modValue;

    /// <summary>
    /// The prime.
    /// </summary>
    private readonly BigInteger fnvPrime;

    /// <summary>
    /// The non-zero offset basis.
    /// </summary>
    private readonly BigInteger fnvOffsetBasis;

    /// <summary>
    /// The computed hash value.
    /// </summary>
    private BigInteger hash;

    protected Fnv1aBigBase(BigInteger modValue, BigInteger fnvPrime, BigInteger fnvOffsetBasis)
    {
        this.modValue = modValue;
        this.fnvPrime = fnvPrime;
        this.fnvOffsetBasis = fnvOffsetBasis;
        this.Initialize();
    }

    public override sealed void Initialize()
    {
        this.hash = this.fnvOffsetBasis;
    }

    protected override void HashCore(byte[] array, int ibStart, int cbSize)
    {
        for (var i = ibStart; i < cbSize; i++)
        {
            unchecked
            {
                this.hash ^= array[i];
                this.hash = (this.hash * this.fnvPrime) % this.modValue;
            }
        }
    }

    protected override byte[] HashFinal()
    {
        return this.hash.ToByteArray();
    }
}

Fnv1a128:

public sealed class Fnv1a128 : Fnv1aBigBase
{
    public Fnv1a128() : base(
            BigInteger.Parse("100000000000000000000000000000000", NumberStyles.AllowHexSpecifier),
            BigInteger.Parse("0000000001000000000000000000013B", NumberStyles.AllowHexSpecifier),
            BigInteger.Parse("6C62272E07BB014262B821756295C58D", NumberStyles.AllowHexSpecifier))
    {
    }
}

Fnv1a256:

public sealed class Fnv1a256 : Fnv1aBigBase
{
    public Fnv1a256() : base(
            BigInteger.Parse("1000000000000000000000000000000000000000000000000000000000000000", NumberStyles.AllowHexSpecifier),
            BigInteger.Parse("0000000000000000000001000000000000000000000000000000000000000163", NumberStyles.AllowHexSpecifier),
            BigInteger.Parse("0DD268DBCAAC550362D98C384C4E576CCC8B1536847B6BBB31023B4C8CAEE0535", NumberStyles.AllowHexSpecifier))
    {
    }
}

Fnv1a512:

public sealed class Fnv1a512 : Fnv1aBigBase
{
    public Fnv1a512() : base(
            BigInteger.Parse("10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", NumberStyles.AllowHexSpecifier),
            BigInteger.Parse("00000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000157", NumberStyles.AllowHexSpecifier),
            BigInteger.Parse("0B86DB0B1171F4416DCA1E50F309990ACAC87D059C90000000000000000000D21E948F68A34C192F62EA79BC942DBE7CE182036415F56E34BAC982AAC4AFE9FD9", NumberStyles.AllowHexSpecifier))
    {
    }
}

Fnv1a1024:

public sealed class Fnv1a1024 : Fnv1aBigBase
{
    public Fnv1a1024() : base(
            BigInteger.Parse("1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", NumberStyles.AllowHexSpecifier),
            BigInteger.Parse("000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000018D", NumberStyles.AllowHexSpecifier),
            BigInteger.Parse("0000000000000000005F7A76758ECC4D32E56D5A591028B74B29FC4223FDADA16C3BF34EDA3674DA9A21D9000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000004C6D7EB6E73802734510A555F256CC005AE556BDE8CC9C6A93B21AFF4B16C71EE90B3", NumberStyles.AllowHexSpecifier))
    {
    }
}
\$\endgroup\$
  • \$\begingroup\$ No sure answer, but it would probably result in better performance if you wrote a custom unchecked variant of BigInteger for each size, since you know the modValue, rather than relying on the default implementation that can grow to any size. \$\endgroup\$ – Snowbody Mar 27 '15 at 19:28
  • \$\begingroup\$ I have been surprised before to find that unchecked blocks can be slower than regular blocks. Try special casing the HashCore invocations where ibStart is 0 and cbSize is the length of the array -- a for loop from 0 to < array.length will optimize out the array checks. You may find it is faster. FNV1a is not considered a super-great algorithm, by the way. \$\endgroup\$ – Frank Hileman Mar 27 '15 at 21:50
  • \$\begingroup\$ Why the crypto tag? Fnv1a isn't a cryptographic hash. \$\endgroup\$ – CodesInChaos Apr 13 '15 at 12:55
  • \$\begingroup\$ Noted and corrected. \$\endgroup\$ – Jesse C. Slicer Apr 13 '15 at 13:35
2
\$\begingroup\$

Things I like:

  • Your abstract base class. It's a very wise design choice.
  • You protected its constructor properly so that it's clear only child classes can call on the base class.
  • Clear, simple, easy to read code.
  • You sealed all of the concrete implementations.

Things I don't like:

  • The XML doc comments on private fields. Leave the comments themselves, but the ///<SUMMARY> tags are just clutter.
  • In the loop, ibStart and cbSize could use more verbose names. Maybe it'd be clear to me if I had more domain knowledge, but I don't.

This is very clean, very nice code. Unless you've profiled the code and identified a slowdown somewhere, you're done here. Move along.

\$\endgroup\$
  • 1
    \$\begingroup\$ Thank you for the commentary. Just FYI ibStart and cbSize are named as such because that's their names in the base method HashCore in the .NET CLR. The XML doc I omitted on that method reads thus: "The offset into the byte array from which to begin using data." and "The number of bytes in the byte array to use as data.". \$\endgroup\$ – Jesse C. Slicer Mar 29 '15 at 16:34
  • 1
    \$\begingroup\$ I had a feeling that I was missing some domain knowledge that would make them crystal clear. Thanks for filling in the blank. \$\endgroup\$ – RubberDuck Mar 29 '15 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.