Skip to content

Instantly share code, notes, and snippets.

@flaviut

flaviut/SMHasher Output

Last active August 29, 2015 14:01
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save flaviut/71b771138800dedf7066 to your computer and use it in GitHub Desktop.
Save flaviut/71b771138800dedf7066 to your computer and use it in GitHub Desktop.
Download ZIP
Running the CrapWow hash through SMHasher
Raw
patch.diff
Index: Hashes.cpp
===================================================================
--- Hashes.cpp (revision 152)
+++ Hashes.cpp (working copy)
@@ -153,3 +153,24 @@
{
*(uint32_t*)out = Crap8((const uint8_t*)key,len,seed);
}
+
+uint32_t CrapWow( const uint8_t *key, uint32_t len, uint32_t seed ) {
+ #define cwfold( a, b, lo, hi ) { p = (uint32_t)(a) * (uint64_t)(b); lo ^= (uint32_t)p; hi ^= (uint32_t)(p >> 32); }
+ #define cwmixa( in ) { cwfold( in, m, k, h ); }
+ #define cwmixb( in ) { cwfold( in, n, h, k ); }
+
+ const uint32_t m = 0x57559429, n = 0x5052acdb, *key4 = (const uint32_t *)key;
+ uint32_t h = len, k = len + seed + n;
+ uint64_t p;
+
+ while ( len >= 8 ) { cwmixb(key4[0]) cwmixa(key4[1]) key4 += 2; len -= 8; }
+ if ( len >= 4 ) { cwmixb(key4[0]) key4 += 1; len -= 4; }
+ if ( len ) { cwmixa( key4[0] & ( ( 1 << ( len * 8 ) ) - 1 ) ) }
+ cwmixb( h ^ (k + n) )
+ return k ^ h;
+}
+
+void CrapWow_test ( const void * key, int len, uint32_t seed, void * out)
+{
+ *(uint32_t*)out = CrapWow((const uint8_t*) key, len, seed);
+}
Index: Hashes.h
===================================================================
--- Hashes.h (revision 152)
+++ Hashes.h (working copy)
@@ -34,6 +34,7 @@
void lookup3_test ( const void * key, int len, uint32_t seed, void * out );
void MurmurOAAT_test ( const void * key, int len, uint32_t seed, void * out );
void Crap8_test ( const void * key, int len, uint32_t seed, void * out );
+void CrapWow_test ( const void * key, int len, uint32_t seed, void * out);
void CityHash128_test ( const void * key, int len, uint32_t seed, void * out );
void CityHash64_test ( const void * key, int len, uint32_t seed, void * out );
Index: main.cpp
===================================================================
--- main.cpp (revision 152)
+++ main.cpp (working copy)
@@ -58,6 +58,7 @@
{ SuperFastHash, 32, 0x980ACD1D, "superfast", "Paul Hsieh's SuperFastHash" },
{ MurmurOAAT_test, 32, 0x5363BD98, "MurmurOAAT", "Murmur one-at-a-time" },
{ Crap8_test, 32, 0x743E97A1, "Crap8", "Crap8" },
+ { CrapWow_test, 32, 0x49ECB015, "CrapWow", "CrapWow" },
{ CityHash64_test, 64, 0x25A20825, "City64", "Google CityHash64WithSeed" },
{ CityHash128_test, 128, 0x6531F54E, "City128", "Google CityHash128WithSeed" },
Raw
SMHasher Output
-------------------------------------------------------------------------------
--- Testing CrapWow (CrapWow)
[[[ Sanity Tests ]]]
Verification value 0x49ECB015 : Passed!
Running sanity check 1..........PASS
Running sanity check 2..........PASS
[[[ Speed Tests ]]]
Bulk speed test - 262144-byte keys
Alignment 0 - 2.148 bytes/cycle - 6145.41 MiB/sec @ 3 ghz
Alignment 1 - 2.094 bytes/cycle - 5991.13 MiB/sec @ 3 ghz
Alignment 2 - 2.094 bytes/cycle - 5990.76 MiB/sec @ 3 ghz
Alignment 3 - 2.094 bytes/cycle - 5990.27 MiB/sec @ 3 ghz
Alignment 4 - 2.094 bytes/cycle - 5990.87 MiB/sec @ 3 ghz
Alignment 5 - 2.094 bytes/cycle - 5991.73 MiB/sec @ 3 ghz
Alignment 6 - 2.094 bytes/cycle - 5991.53 MiB/sec @ 3 ghz
Alignment 7 - 2.093 bytes/cycle - 5988.82 MiB/sec @ 3 ghz
Small key speed test - 1-byte keys - 92.00 cycles/hash
Small key speed test - 2-byte keys - 93.37 cycles/hash
Small key speed test - 3-byte keys - 93.45 cycles/hash
Small key speed test - 4-byte keys - 91.79 cycles/hash
Small key speed test - 5-byte keys - 95.03 cycles/hash
Small key speed test - 6-byte keys - 95.19 cycles/hash
Small key speed test - 7-byte keys - 95.64 cycles/hash
Small key speed test - 8-byte keys - 102.58 cycles/hash
Small key speed test - 9-byte keys - 106.26 cycles/hash
Small key speed test - 10-byte keys - 106.00 cycles/hash
Small key speed test - 11-byte keys - 106.00 cycles/hash
Small key speed test - 12-byte keys - 104.31 cycles/hash
Small key speed test - 13-byte keys - 108.00 cycles/hash
Small key speed test - 14-byte keys - 108.00 cycles/hash
Small key speed test - 15-byte keys - 108.00 cycles/hash
Small key speed test - 16-byte keys - 106.79 cycles/hash
Small key speed test - 17-byte keys - 109.97 cycles/hash
Small key speed test - 18-byte keys - 119.59 cycles/hash
Small key speed test - 19-byte keys - 122.63 cycles/hash
Small key speed test - 20-byte keys - 108.80 cycles/hash
Small key speed test - 21-byte keys - 123.57 cycles/hash
Small key speed test - 22-byte keys - 124.83 cycles/hash
Small key speed test - 23-byte keys - 111.68 cycles/hash
Small key speed test - 24-byte keys - 111.65 cycles/hash
Small key speed test - 25-byte keys - 113.36 cycles/hash
Small key speed test - 26-byte keys - 113.00 cycles/hash
Small key speed test - 27-byte keys - 113.38 cycles/hash
Small key speed test - 28-byte keys - 113.30 cycles/hash
Small key speed test - 29-byte keys - 116.35 cycles/hash
Small key speed test - 30-byte keys - 115.00 cycles/hash
Small key speed test - 31-byte keys - 115.00 cycles/hash
[[[ Differential Tests ]]]
Testing 8303632 up-to-5-bit differentials in 64-bit keys -> 32 bit hashes.
1000 reps, 8303632000 total tests, expecting 1.93 random collisions..........
1 total collisions, of which 1 single collisions were ignored
Testing 11017632 up-to-4-bit differentials in 128-bit keys -> 32 bit hashes.
1000 reps, 11017632000 total tests, expecting 2.57 random collisions..........
25 total collisions, of which 25 single collisions were ignored
Testing 2796416 up-to-3-bit differentials in 256-bit keys -> 32 bit hashes.
1000 reps, 2796416000 total tests, expecting 0.65 random collisions..........
4 total collisions, of which 4 single collisions were ignored
[[[ Avalanche Tests ]]]
Testing 32-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is 0.652667%
Testing 40-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is 0.607333%
Testing 48-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is 0.726000%
Testing 56-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is 0.668667%
Testing 64-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is 0.688000%
Testing 72-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is 0.660667%
Testing 80-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is 0.644667%
Testing 88-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is 0.612000%
Testing 96-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is 0.603333%
Testing 104-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is 0.660667%
Testing 112-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is 0.698667%
Testing 120-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is 0.655333%
Testing 128-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is 0.705333%
Testing 136-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is 0.686000%
Testing 144-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is 0.692000%
Testing 152-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is 0.668667%
[[[ Keyset 'Cyclic' Tests ]]]
Keyset 'Cyclic' - 8 cycles of 4 bytes - 10000000 keys
Testing collisions - Expected 11641.53, actual 9999999.00 (858.99x) !!!!!
Testing distribution - Worst bias is the 20-bit window at bit 0 - 100.000% !!!!!
Keyset 'Cyclic' - 8 cycles of 5 bytes - 10000000 keys
Testing collisions - Expected 11641.53, actual 11670.00 ( 1.00x)
Testing distribution - Worst bias is the 20-bit window at bit 14 - 0.030%
Keyset 'Cyclic' - 8 cycles of 6 bytes - 10000000 keys
Testing collisions - Expected 11641.53, actual 9999999.00 (858.99x) !!!!!
Testing distribution - Worst bias is the 20-bit window at bit 0 - 100.000% !!!!!
Keyset 'Cyclic' - 8 cycles of 7 bytes - 10000000 keys
Testing collisions - Expected 11641.53, actual 11572.00 ( 0.99x)
Testing distribution - Worst bias is the 19-bit window at bit 19 - 0.031%
Keyset 'Cyclic' - 8 cycles of 8 bytes - 10000000 keys
Testing collisions - Expected 11641.53, actual 9999999.00 (858.99x) !!!!!
Testing distribution - Worst bias is the 20-bit window at bit 0 - 100.000% !!!!!
*********FAIL*********
[[[ Keyset 'TwoBytes' Tests ]]]
Keyset 'TwoBytes' - up-to-4-byte keys, 652545 total keys
Testing collisions - Expected 49.57, actual 44.00 ( 0.89x)
Testing distribution - Worst bias is the 16-bit window at bit 12 - 1.092% !!!!!
Keyset 'TwoBytes' - up-to-8-byte keys, 5471025 total keys
Testing collisions - Expected 3484.56, actual 328785.00 (94.35x) !!!!!
Testing distribution - Worst bias is the 20-bit window at bit 12 - 10.697% !!!!!
Keyset 'TwoBytes' - up-to-12-byte keys, 18616785 total keys
Testing collisions - Expected 40347.77, actual 5909127.00 (146.45x) !!!!!
Testing distribution - Worst bias is the 20-bit window at bit 10 - 12.568% !!!!!
Keyset 'TwoBytes' - up-to-16-byte keys, 44251425 total keys
Testing collisions - Expected 227963.15, actual 22709235.00 (99.62x) !!!!!
Testing distribution - Worst bias is the 20-bit window at bit 10 - 11.781% !!!!!
Keyset 'TwoBytes' - up-to-20-byte keys, 86536545 total keys
Testing collisions - Expected 871784.70, actual 55394512.00 (63.54x) !!!!!
Testing distribution - Worst bias is the 20-bit window at bit 6 - 10.918% !!!!!
*********FAIL*********
[[[ Keyset 'Sparse' Tests ]]]
Keyset 'Sparse' - 32-bit keys with up to 6 bits set - 1149017 keys
Testing collisions - Expected 153.70, actual 162.00 ( 1.05x)
Testing distribution - Worst bias is the 17-bit window at bit 3 - 0.086%
Keyset 'Sparse' - 40-bit keys with up to 6 bits set - 4598479 keys
Testing collisions - Expected 2461.72, actual 2457.00 ( 1.00x)
Testing distribution - Worst bias is the 19-bit window at bit 13 - 0.046%
Keyset 'Sparse' - 48-bit keys with up to 5 bits set - 1925357 keys
Testing collisions - Expected 431.55, actual 465.00 ( 1.08x)
Testing distribution - Worst bias is the 18-bit window at bit 5 - 0.052%
Keyset 'Sparse' - 56-bit keys with up to 5 bits set - 4216423 keys
Testing collisions - Expected 2069.66, actual 2109.00 ( 1.02x)
Testing distribution - Worst bias is the 19-bit window at bit 26 - 0.047%
Keyset 'Sparse' - 64-bit keys with up to 5 bits set - 8303633 keys
Testing collisions - Expected 8026.87, actual 8102.00 ( 1.01x)
Testing distribution - Worst bias is the 20-bit window at bit 29 - 0.045%
Keyset 'Sparse' - 96-bit keys with up to 4 bits set - 3469497 keys
Testing collisions - Expected 1401.34, actual 1727661.00 (1232.86x) !!!!!
Testing distribution - Worst bias is the 19-bit window at bit 22 - 15.815% !!!!!
Keyset 'Sparse' - 256-bit keys with up to 3 bits set - 2796417 keys
Testing collisions - Expected 910.36, actual 2678870.00 (2942.64x) !!!!!
Testing distribution - Worst bias is the 19-bit window at bit 19 - 92.133% !!!!!
Keyset 'Sparse' - 2048-bit keys with up to 2 bits set - 2098177 keys
Testing collisions - Expected 512.50, actual 2095109.00 (4088.01x) !!!!!
Testing distribution - Worst bias is the 18-bit window at bit 19 - 99.455% !!!!!
*********FAIL*********
[[[ Keyset 'Combination Lowbits' Tests ]]]
Keyset 'Combination' - up to 8 blocks from a set of 8 - 19173960 keys
Testing collisions - Expected 42799.01, actual 19152183.00 (447.49x) !!!!!
Testing distribution - Worst bias is the 20-bit window at bit 8 - 99.473% !!!!!
*********FAIL*********
[[[ Keyset 'Combination Highbits' Tests ]]]
Keyset 'Combination' - up to 8 blocks from a set of 8 - 19173960 keys
Testing collisions - Expected 42799.01, actual 19152192.00 (447.49x) !!!!!
Testing distribution - Worst bias is the 20-bit window at bit 6 - 99.476% !!!!!
*********FAIL*********
[[[ Keyset 'Combination 0x8000000' Tests ]]]
Keyset 'Combination' - up to 20 blocks from a set of 2 - 2097150 keys
Testing collisions - Expected 512.00, actual 2097084.00 (4095.88x) !!!!!
Testing distribution - Worst bias is the 18-bit window at bit 9 - 99.996% !!!!!
*********FAIL*********
[[[ Keyset 'Combination 0x0000001' Tests ]]]
Keyset 'Combination' - up to 20 blocks from a set of 2 - 2097150 keys
Testing collisions - Expected 512.00, actual 2097084.00 (4095.88x) !!!!!
Testing distribution - Worst bias is the 18-bit window at bit 9 - 99.995% !!!!!
*********FAIL*********
[[[ Keyset 'Combination Hi-Lo' Tests ]]]
Keyset 'Combination' - up to 6 blocks from a set of 15 - 12204240 keys
Testing collisions - Expected 17339.30, actual 11923580.00 (687.66x) !!!!!
Testing distribution - Worst bias is the 20-bit window at bit 5 - 93.406% !!!!!
*********FAIL*********
[[[ Keyset 'Window' Tests ]]]
Keyset 'Windowed' - 64-bit key, 20-bit window - 64 tests, 1048576 keys per test
Window at 0 - Testing collisions - Expected 128.00, actual 128.00 ( 1.00x)
Window at 1 - Testing collisions - Expected 128.00, actual 128.00 ( 1.00x)
Window at 2 - Testing collisions - Expected 128.00, actual 145.00 ( 1.13x)
Window at 3 - Testing collisions - Expected 128.00, actual 131.00 ( 1.02x)
Window at 4 - Testing collisions - Expected 128.00, actual 111.00 ( 0.87x)
Window at 5 - Testing collisions - Expected 128.00, actual 123.00 ( 0.96x)
Window at 6 - Testing collisions - Expected 128.00, actual 105.00 ( 0.82x)
Window at 7 - Testing collisions - Expected 128.00, actual 102.00 ( 0.80x)
Window at 8 - Testing collisions - Expected 128.00, actual 124.00 ( 0.97x)
Window at 9 - Testing collisions - Expected 128.00, actual 104.00 ( 0.81x)
Window at 10 - Testing collisions - Expected 128.00, actual 120.00 ( 0.94x)
Window at 11 - Testing collisions - Expected 128.00, actual 146.00 ( 1.14x)
Window at 12 - Testing collisions - Expected 128.00, actual 147.00 ( 1.15x)
Window at 13 - Testing collisions - Expected 128.00, actual 118.00 ( 0.92x)
Window at 14 - Testing collisions - Expected 128.00, actual 120.00 ( 0.94x)
Window at 15 - Testing collisions - Expected 128.00, actual 110.00 ( 0.86x)
Window at 16 - Testing collisions - Expected 128.00, actual 103.00 ( 0.80x)
Window at 17 - Testing collisions - Expected 128.00, actual 130.00 ( 1.02x)
Window at 18 - Testing collisions - Expected 128.00, actual 117.00 ( 0.91x)
Window at 19 - Testing collisions - Expected 128.00, actual 120.00 ( 0.94x)
Window at 20 - Testing collisions - Expected 128.00, actual 120.00 ( 0.94x)
Window at 21 - Testing collisions - Expected 128.00, actual 110.00 ( 0.86x)
Window at 22 - Testing collisions - Expected 128.00, actual 102.00 ( 0.80x)
Window at 23 - Testing collisions - Expected 128.00, actual 110.00 ( 0.86x)
Window at 24 - Testing collisions - Expected 128.00, actual 133.00 ( 1.04x)
Window at 25 - Testing collisions - Expected 128.00, actual 127.00 ( 0.99x)
Window at 26 - Testing collisions - Expected 128.00, actual 128.00 ( 1.00x)
Window at 27 - Testing collisions - Expected 128.00, actual 122.00 ( 0.95x)
Window at 28 - Testing collisions - Expected 128.00, actual 125.00 ( 0.98x)
Window at 29 - Testing collisions - Expected 128.00, actual 111.00 ( 0.87x)
Window at 30 - Testing collisions - Expected 128.00, actual 107.00 ( 0.84x)
Window at 31 - Testing collisions - Expected 128.00, actual 118.00 ( 0.92x)
Window at 32 - Testing collisions - Expected 128.00, actual 133.00 ( 1.04x)
Window at 33 - Testing collisions - Expected 128.00, actual 136.00 ( 1.06x)
Window at 34 - Testing collisions - Expected 128.00, actual 123.00 ( 0.96x)
Window at 35 - Testing collisions - Expected 128.00, actual 141.00 ( 1.10x)
Window at 36 - Testing collisions - Expected 128.00, actual 113.00 ( 0.88x)
Window at 37 - Testing collisions - Expected 128.00, actual 136.00 ( 1.06x)
Window at 38 - Testing collisions - Expected 128.00, actual 141.00 ( 1.10x)
Window at 39 - Testing collisions - Expected 128.00, actual 132.00 ( 1.03x)
Window at 40 - Testing collisions - Expected 128.00, actual 129.00 ( 1.01x)
Window at 41 - Testing collisions - Expected 128.00, actual 133.00 ( 1.04x)
Window at 42 - Testing collisions - Expected 128.00, actual 146.00 ( 1.14x)
Window at 43 - Testing collisions - Expected 128.00, actual 114.00 ( 0.89x)
Window at 44 - Testing collisions - Expected 128.00, actual 114.00 ( 0.89x)
Window at 45 - Testing collisions - Expected 128.00, actual 116.00 ( 0.91x)
Window at 46 - Testing collisions - Expected 128.00, actual 118.00 ( 0.92x)
Window at 47 - Testing collisions - Expected 128.00, actual 132.00 ( 1.03x)
Window at 48 - Testing collisions - Expected 128.00, actual 144.00 ( 1.13x)
Window at 49 - Testing collisions - Expected 128.00, actual 137.00 ( 1.07x)
Window at 50 - Testing collisions - Expected 128.00, actual 163.00 ( 1.27x)
Window at 51 - Testing collisions - Expected 128.00, actual 131.00 ( 1.02x)
Window at 52 - Testing collisions - Expected 128.00, actual 123.00 ( 0.96x)
Window at 53 - Testing collisions - Expected 128.00, actual 144.00 ( 1.13x)
Window at 54 - Testing collisions - Expected 128.00, actual 119.00 ( 0.93x)
Window at 55 - Testing collisions - Expected 128.00, actual 113.00 ( 0.88x)
Window at 56 - Testing collisions - Expected 128.00, actual 130.00 ( 1.02x)
Window at 57 - Testing collisions - Expected 128.00, actual 114.00 ( 0.89x)
Window at 58 - Testing collisions - Expected 128.00, actual 117.00 ( 0.91x)
Window at 59 - Testing collisions - Expected 128.00, actual 143.00 ( 1.12x)
Window at 60 - Testing collisions - Expected 128.00, actual 124.00 ( 0.97x)
Window at 61 - Testing collisions - Expected 128.00, actual 126.00 ( 0.98x)
Window at 62 - Testing collisions - Expected 128.00, actual 127.00 ( 0.99x)
Window at 63 - Testing collisions - Expected 128.00, actual 127.00 ( 0.99x)
Window at 64 - Testing collisions - Expected 128.00, actual 128.00 ( 1.00x)
[[[ Keyset 'Text' Tests ]]]
Keyset 'Text' - keys of form "Foo[XXXX]Bar" - 14776336 keys
Testing collisions - Expected 25418.13, actual 25373.00 ( 1.00x)
Testing distribution - Worst bias is the 20-bit window at bit 26 - 0.018%
Keyset 'Text' - keys of form "FooBar[XXXX]" - 14776336 keys
Testing collisions - Expected 25418.13, actual 25249.00 ( 0.99x)
Testing distribution - Worst bias is the 20-bit window at bit 31 - 0.023%
Keyset 'Text' - keys of form "[XXXX]FooBar" - 14776336 keys
Testing collisions - Expected 25418.13, actual 25407.00 ( 1.00x)
Testing distribution - Worst bias is the 20-bit window at bit 31 - 0.015%
[[[ Keyset 'Zeroes' Tests ]]]
Keyset 'Zeroes' - 65536 keys
Testing collisions - Expected 0.50, actual 31328.00 (62656.96x) !!!!!
Testing distribution - Worst bias is the 13-bit window at bit 20 - 94.384% !!!!!
*********FAIL*********
[[[ Keyset 'Seed' Tests ]]]
Keyset 'Seed' - 1000000 keys
Testing collisions - Expected 116.42, actual 69.00 ( 0.59x)
Testing distribution - Worst bias is the 17-bit window at bit 22 - 8.965% !!!!!
Input vcode 0xa9089da9, Output vcode 0xf5542a54, Result vcode 0x00000001
Verification value is 0x00000001 - Testing took 1845.087393 seconds
-------------------------------------------------------------------------------
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment