nxt.digestx.fnv source code

1 /** FNV(Fowler-Noll-Vo) hash implementation.
2  *
3  * This module conforms to the APIs defined in std.digest.
4  */
5 module nxt.digestx.fnv;
6 
7 public import std.digest;
8 
9 /**
10  * Template API FNV-1(a) hash implementation.
11  */
12 struct FNV(ulong bitLength, bool fnv1a = false)
13 {
14     static if (bitLength == 32)
15     {
16         alias Element = uint;
17     }
18     else static if (bitLength == 64)
19     {
20         alias Element = ulong;
21     }
22     else
23     {
24         static assert(0, "Unsupported hash length " ~ bitLength.stringof);
25     }
26 
27     pragma(inline, true):
28 
29     /// Initializes the digest calculation.
30     void start() @safe pure nothrow @nogc
31     {
32         _hash = fnvOffsetBasis;
33     }
34 
35     /// Feeds the digest with data.
36     void put(scope const(ubyte)[] data...) pure nothrow @nogc
37     {
38         foreach (immutable ubyte e; data)
39         {
40             static if (fnv1a)
41             {
42                 _hash ^= e;
43                 _hash *= fnvPrime;
44             }
45             else
46             {
47                 _hash *= fnvPrime;
48                 _hash ^= e;
49             }
50         }
51     }
52 
53     /// Feeds the digest with `data` being a static array.
54     void putStaticArray(size_t n)(scope auto ref const(ubyte)[n] data)
55         pure nothrow @nogc
56     {
57         static foreach (i; 0 .. n) // unroll
58         {
59             static if (fnv1a)
60             {
61                 _hash ^= data[i];
62                 _hash *= fnvPrime;
63             }
64             else
65             {
66                 _hash *= fnvPrime;
67                 _hash ^= data[i];
68             }
69         }
70     }
71 
72     /// Returns the finished FNV digest. This also calls start to reset the internal state.
73     ubyte[bitLength / 8] finish() @trusted pure nothrow @nogc
74     {
75         import std.bitmanip : nativeToBigEndian;
76         _result = _hash;
77         start();
78         return nativeToBigEndian(_result);
79     }
80 
81     Element get() const
82     {
83         return _result;
84     }
85 
86 private:
87 
88     // FNV-1 hash parameters
89     static if (bitLength == 32)
90     {
91         enum Element fnvPrime = 0x1000193U;
92         enum Element fnvOffsetBasis = 0x811C9DC5U;
93     }
94     else static if (bitLength == 64)
95     {
96         enum Element fnvPrime = 0x100000001B3UL;
97         enum Element fnvOffsetBasis = 0xCBF29CE484222325UL;
98     }
99     else
100     {
101         static assert(0, "Unsupported hash length " ~ bitLength.stringof);
102     }
103 
104     Element _hash;
105     Element _result;
106 }
107 
108 alias FNV32 = FNV!32; /// 32bit FNV-1, hash size is ubyte[4]
109 alias FNV64 = FNV!64; /// 64bit FNV-1, hash size is ubyte[8]
110 alias FNV32A = FNV!(32, true); /// 32bit FNV-1a, hash size is ubyte[4]
111 alias FNV64A = FNV!(64, true); /// 64bit FNV-1a, hash size is ubyte[8]
112 
113 ///
114 unittest
115 {
116     import std.conv : hexString;
117     // alias FNV32Digest = WrapperDigest!FNV32; /// OOP API for 32bit FNV-1
118     // alias FNV64Digest = WrapperDigest!FNV64; /// OOP API for 64bit FNV-1
119     alias FNV32ADigest = WrapperDigest!FNV32A; /// OOP API for 32bit FNV-1a
120     // alias FNV64ADigest = WrapperDigest!FNV64A; /// OOP API for 64bit FNV-1a
121 
122     const immutable(char)[5] hello = "hello";
123 
124     FNV64 fnv64;
125     fnv64.start();
126     fnv64.put(cast(ubyte[])hello[]);
127     assert(toHexString(fnv64.finish()) == "7B495389BDBDD4C7");
128 
129     fnv64.putStaticArray(cast(ubyte[5])hello);
130     assert(toHexString(fnv64.finish()) == "7B495389BDBDD4C7");
131 
132     // Template API
133     assert(digest!FNV32("abc") == hexString!"439C2F4B");
134     assert(digest!FNV64("abc") == hexString!"D8DCCA186BAFADCB");
135     assert(digest!FNV32A("abc") == hexString!"1A47E90B");
136     assert(digest!FNV64A("abc") == hexString!"E71FA2190541574B");
137 
138     // OOP API
139     Digest fnv = new FNV32ADigest;
140     ubyte[] d = fnv.digest("1234");
141     assert(d == hexString!"FDC422FD");
142 }
143 
144 /// Convenience aliases for std.digest.digest using the FNV implementation.
145 auto fnv32Of(T...)(in T data)
146 {
147     return digest!(FNV32, T)(data);
148 }
149 /// ditto
150 auto fnv64Of(T...)(in T data)
151 {
152     return digest!(FNV64, T)(data);
153 }
154 /// ditto
155 auto fnv32aOf(T...)(in T data)
156 {
157     return digest!(FNV32A, T)(data);
158 }
159 /// ditto
160 auto fnv64aOf(T...)(in T data)
161 {
162     return digest!(FNV64A, T)(data);
163 }
164 
165 ///
166 @safe pure nothrow @nogc unittest
167 {
168     import std.conv : hexString;
169     assert(fnv32Of("") == hexString!"811C9DC5");
170     assert(fnv64Of("") == hexString!"CBF29CE484222325");
171     assert(fnv32aOf("") == hexString!"811C9DC5");
172     assert(fnv64aOf("") == hexString!"CBF29CE484222325");
173 }