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