Code Monkey home page Code Monkey logo

smhasher's Introduction

SMhasher

Linux Build status Windows Build status FreeBSD Build status

Hash function MiB/sec cycl./hash cycl./map size Quality problems
donothing32 11149460.06 4.00 - 13 bad seed 0, test NOP
donothing64 11787676.42 4.00 - 13 bad seed 0, test NOP
donothing128 11745060.76 4.06 - 13 bad seed 0, test NOP
NOP_OAAT_read64 11372846.37 14.00 - 47 test NOP
BadHash 769.94 73.97 - 47 bad seed 0, test FAIL
sumhash 10699.57 29.53 - 363 bad seed 0, test FAIL
sumhash32 42877.79 23.12 - 863 UB, test FAIL
multiply_shift 8026.77 26.05 226.80 (8) 345 bad seeds & 0xfffffff0, fails most tests
pair_multiply_shift 3716.95 40.22 186.34 (3) 609 fails most tests
--------------------------
crc32 383.12 134.21 257.50 (11) 422 insecure, 8590x collisions, distrib, PerlinNoise
md5_32 350.53 644.31 894.12 (10) 4419
md5_64 351.01 656.67 897.43 (12) 4419
md5-128 350.89 681.88 894.03 (13) 4419
sha1_32 353.03 1385.80 1759.94 (5) 5126 Sanity, Cyclic low32, 36.6% distrib
sha1_64 353.03 1385.80 1759.94 (5) 5126 Sanity, Cyclic low32, 36.6% distrib
sha1-160 364.95 1470.55 1794.16 (13) 5126 Comb/Cyclic low32
sha2-224 147.13 1354.81 1589.92 (12) Comb low32
sha2-224_64 147.60 1360.10 1620.93 (13) Cyclic low32
sha2-256 147.80 1374.90 1606.06 (16)
sha2-256_64 148.01 1376.34 1624.71 (16)
sha1ni 1601.21 174.16 397.28 (6) 989 insecure,sanity, Permutation, Zeroes, machine-specific
sha1ni_32 1576.17 174.04 405.56 (6) 989 machine-specific
sha2ni-256 1527.38 184.35 404.40 (4) 4241 insecure,sanity, Permutation, Zeroes, machine-specific
sha2ni-256_64 1501.85 186.20 407.96 (5) 4241 Zeroes, machine-specific
blake3_c 1288.84 357.69 582.89 (6) no 32bit portability
rmd128 290.90 710.49 965.55 (6)
rmd160 202.16 1045.79 1287.74 (16) Cyclic hi32
rmd256 364.81 584.86 835.02 (11)
edonr224 864.69 303.42 526.94 (6)
edonr256 847.85 305.79 510.01 (4)
blake2s-128 295.30 698.09 1059.24 (51)
blake2s-160 215.01 1026.74 1239.54 (11)
blake2s-224 207.06 1063.86 1236.50 (20)
blake2s-256 215.28 1014.88 1230.38 (28)
blake2s-256_64 211.52 1044.22 1228.43 (8)
blake2b-160 356.08 1236.84 1458.15 (12)
blake2b-224 356.59 1228.50 1425.87 (16)
blake2b-256 355.97 1232.22 1443.31 (19)
blake2b-256_64 356.97 1222.76 1435.03 (9)
asconhashv12 144.98 885.02 1324.23 (38) 4341
asconhashv12_64 159.68 386.90 480.86 (4) 6490
sha3-256 100.58 3877.18 4159.79 (37) PerlinNoise
sha3-256_64 100.57 3909.00 4174.63 (16) PerlinNoise
hasshe2 2773.89 64.35 282.30 (3) 445 Permutation,TwoBytes,Zeroes,Seed
poly_1_mersenne 1369.21 61.59 248.86 (4) 479 fails most tests
poly_2_mersenne 1364.03 70.30 261.00 (6) 479
poly_3_mersenne 1342.82 80.22 268.79 (2) 479
poly_4_mersenne 1343.19 89.13 277.52 (3) 479
tabulation32 5781.16 40.00 241.79 (10) 848 collisions
tabulation 7875.01 39.95 249.49 (3) 554
crc32_hw 6244.38 41.23 226.80 (2) 653 insecure, 100% bias, collisions, distrib, BIC, machine-specific (SSE4.2/NEON)
crc32_hw1 7569.29 49.07 233.75 (3) 671 insecure, 100% bias, collisions, distrib, BIC, machine-specific (x86 SSE4.2)
crc64_hw 6143.62 40.48 223.13 (2) 652 insecure, 100% bias, collisions, distrib, BIC, machine-specific (SSE4.2/NEON)
crc32_pclmul - - - insecure, 100% bias, collisions, distrib, BIC, machine-specific (x86 SSE4.2+PCLMUL)
o1hash 11629440.57 18.15 199.35 (2) 101 insecure, no seed, zeros, fails all tests
fibonacci 16878.32 22.94 803.18 (15) 1692 UB, zeros, fails all tests
FNV1a 760.52 73.83 254.29 (5) 204 bad seed, zeros, fails all tests
FNV1A_Totenschiff 6274.78 26.23 251.13 (2) 270 UB, zeros, fails all tests
FNV1A_Pippip_Yurii 6172.14 27.55 244.80 (2) 147 UB, sanity, fails all tests
FNV1a_YT 13486.49 30.50 237.43 (4) 321 bad seed, UB, fails all tests
FNV2 6171.60 32.20 208.59 (4) 278 fails all tests
FNV64 774.37 72.43 201.15 (2) 79 fails all tests
FNV128 390.14 136.42 289.00 (3) 171 fails all tests
k-hash32 2230.42 53.05 264.64 (3) 808 insecure, zeros, UB, bad seeds, fails all tests
k-hash64 2451.88 48.66 249.44 (2) 609 insecure, zeros, UB, bad seeds, fails all tests
fletcher2 15552.61 20.61 335.31 (3) 248 bad seed 0, UB, fails all tests
fletcher4 15556.93 20.60 358.60 (3) 371 bad seed 0, UB, fails all tests
bernstein 1045.97 58.31 225.78 (3) 41 bad seed 0, fails all tests
sdbm 784.83 68.57 222.68 (5) 41 bad seed 0, fails all tests
x17 748.75 74.13 236.00 (10) 79 99.98% bias, fails all tests
libiberty 628.66 84.95 225.07 (4) 37 insecure, 100% bias, fails all tests, bad seed
gcc 611.69 86.47 231.51 (5) 39 insecure, 100% bias, fails all tests, bad seed
JenkinsOOAT 627.64 107.04 252.79 (3) 153 bad seed 0, 53.5% bias, fails all tests
JenkinsOOAT_perl 608.10 94.17 254.09 (4) 65 bad seed 0, 1.5-11.5% bias, 7.2x collisions, BIC, LongNeighbors
MicroOAAT 701.35 76.68 251.01 (3) 68 100% bias, distrib, BIC
pearsonhash64 434.17 124.14 230.79 (4) Avalanche, Seed, SSSE3 only. broken MSVC
pearsonhash128 434.23 121.34 221.03 (7) Avalanche, Seed, SSSE3 only. broken MSVC
pearsonhash256 444.08 119.11 229.75 (4) Avalanche, Seed, SSSE3 only. broken MSVC
VHASH_32 13053.40 65.84 289.86 (3) 1231 sanity, Seed, MomentChi2
VHASH_64 13465.50 63.88 286.38 (5) 1231 sanity, Seed, Sparse
farsh32 27038.23 66.88 278.89 (5) 944 insecure: AppendedZeroes, collisions+bias, MomentChi2, LongNeighbors
farsh64 13829.32 112.46 332.59 (3) 944 insecure: AppendedZeroes, collisions+bias, MomentChi2, LongNeighbors
farsh128 6878.88 233.35 384.85 (3) 944 insecure: AppendedZeroes, collisions+bias, permut,combin,2bytes,zeroes,PerlinNoise
farsh256 3467.37 440.40 593.57 (5) 944 insecure: AppendedZeroes, collisions+bias, permut,combin,2bytes,zeroes,PerlinNoise
jodyhash32 1794.34 41.12 235.12 (4) 102 bias, collisions, distr, BIC LongNeighbors
jodyhash64 4813.10 40.72 239.22 (6) 118 bias, collisions, distr, BIC, LongNeighbors
lookup3 2475.35 39.65 240.10 (3) 341 UB, 28% bias, collisions, 30% distr, BIC
superfast 2058.22 49.56 254.12 (3) 210 UB, bad seed 0, 91% bias, 5273.01x collisions, 37% distr, BIC
MurmurOAAT 506.66 103.33 236.89 (3) 47 bad seed 0, collisions, 99.998% distr., BIC, LongNeighbors
Crap8 3041.14 37.25 247.87 (4) 342 UB, 2.42% bias, collisions, 2% distrib
Murmur1 2027.85 48.51 253.34 (3) 358 UB, 1 bad seed, 511x collisions, Diff, BIC
Murmur2 3089.18 41.22 238.42 (4) 358 UB, 1 bad seed, 1.7% bias, 81x coll, 1.7% distrib, BIC
Murmur2A 3087.98 45.90 238.54 (4) 407 UB, 1 bad seed, 12.7% bias, LongNeighbors
Murmur2B 5919.38 38.18 215.96 (3) 433 UB, 1.8% bias, collisions, 3.4% distrib, BIC
Murmur2C 3810.98 49.09 218.51 (3) 444 UB, 2^32 bad seeds, 91% bias, collisions, distr, BIC, LongNeighbors
Murmur3A 2982.67 49.08 245.78 (4) 351 UB, 1 bad seed, Moment Chi2 69
PMurHash32 3005.85 48.88 242.38 (3) 1862 1 bad seed, Moment Chi2 69
Murmur3C 4833.18 56.87 250.47 (6) 859 UB, LongNeighbors, Text, DiffDist
mirhash32low 6145.39 36.95 235.09 (4) 1112 UB, 4 bad seeds, Cyclic, LongNeighbors, machine-specific (32/64 differs)
PMPML_32 6639.68 45.33 257.45 (3) 1084 Avalanche >512, unseeded: Seed, BIC, MomentChi2, PerlinNoise
PMPML_64 9833.77 50.00 251.64 (6) 1305 unseeded: Seed, MomentChi2, BIC
xxHash32 5865.17 49.20 242.74 (3) 738 LongNeighbors, collisions with 4bit diff, MomentChi2 220
metrohash64 14741.56 39.44 215.76 (2) 624 UB, LongNeighbors, BIC
metrohash64_1 14298.77 40.31 223.25 (4) 624 UB, LongNeighbors, BIC, MomentChi2
metrohash64crc_1 6929.69 44.65 223.68 (3) 632 UB, Cyclic 8/8 byte, DiffDist, BIC, MomentChi2, machine-specific (SSE4.2/NEON)
metrohash64crc_2 8150.65 43.72 219.45 (5) 632 UB, Cyclic 8/8 byte, DiffDist, BIC, machine-specific (SSE4.2/NEON)
cmetrohash64_1o 14921.73 38.95 213.25 (2) 3506 UB, LongNeighbors, BIC, MomentChi2
cmetrohash64_1 14151.73 40.90 211.89 (2) 652 UB, LongNeighbors, BIC, MomentChi2
City64noSeed 14209.19 31.80 225.90 (5) 1038 Avalanche, Sparse, TwoBytes, MomentChi2, Seed
City64 13887.84 46.32 239.77 (3) 1120 Sparse, TwoBytes
t1ha1_64le 13442.64 31.41 219.58 (3) 517 Avalanche
t1ha1_64be 11586.02 32.74 232.55 (3) 555 Avalanche
t1ha0_32le 7401.21 48.27 238.99 (3) 509 Sparse, LongNeighbors
t1ha0_32be 6217.37 50.66 244.51 (3) 533 Sparse, LongNeighbors
t1ha2_stream 14011.63 80.72 275.17 (3) 1665 Sparse, Permutation, LongNeighbors
t1ha2_stream128 13136.06 97.80 306.11 (7) 1665 Sparse, Permutation, LongNeighbors
aesnihash 5579.32 56.83 258.71 (5) 1209 fails many tests, machine-specific (x64 AES-NI)
falkhash 50631.69 123.02 322.14 (7) 264 Sparse, LongNeighbors, machine-specific (x64 AES-NI)
MeowHash 29969.40 64.96 274.29 (4) 1764 Sparse, invertible, machine-specific (x64 AES-NI)
MeowHash64low 29485.59 65.98 278.05 (3) 1764 Sparse, invertible, machine-specific (x64 AES-NI)
MeowHash32low 26944.58 65.95 292.79 (9) 1764 Sparse, invertible, machine-specific (x64 AES-NI)
--------------------------------------
tifuhash_64 35.60 1679.52 1212.75 (15) 276 Cyclic low32
floppsyhash 35.72 1868.92 1411.07 (7) 623
beamsplitter 789.22 682.45 1150.33 (26) 4203 UB
discohash1 4131.12 199.00 398.35 (5) 1294
discohash1-128 4072.95 234.17 438.43 (5) 1294
discohash2 3986.52 207.52 421.99 (2) 1294
discohash2-128 4094.73 236.61 433.35 (4) 1294
discoNONG 3698.45 399.67 597.78 (9) bad seeds
chaskey 1143.05 113.70 294.43 (4) 1609 PerlinNoise
SipHash 943.53 147.15 338.74 (4) 1071
HalfSipHash 1141.57 79.65 263.96 (3) 700 zeroes
GoodOAAT 743.81 85.62 231.22 (3) 237
pearsonbhash64 1794.83 97.80 268.90 (8) 683
pearsonbhash128 1691.62 104.57 272.38 (4) 1134
pearsonbhash256 1442.59 126.04 309.34 (4) 844
prvhash64_64m 3077.18 47.31 241.92 (3) 349
prvhash64_64 3015.08 48.03 240.64 (3) 384
prvhash64_128 3353.81 67.64 266.32 (2) 718
prvhash64s_64 6591.34 273.50 464.65 (3) 2640
prvhash64s_128 6581.40 333.83 528.07 (5) 2799
SipHash13 1812.75 106.56 310.76 (5) 778 0.9% bias
TSip 4233.17 53.31 249.19 (3) 519 !msvc
seahash 8261.80 58.94 256.08 (4) 871 PerlinNoise, !msvc
seahash32low 8266.17 58.90 290.21 (16) 871 PerlinNoise 32, !msvc
clhash 18703.04 70.19 282.12 (6) 1809 PerlinNoise, machine-specific (x64 SSE4.2)
HighwayHash64 6242.58 99.55 248.41 (3) 2546
Murmur3F 7623.44 52.69 221.87 (3) 699 UB
MUM 9563.99 34.99 228.55 (5) 1912 UB, too many bad seeds, machine-specific (32/64 differs)
MUMlow 9261.89 36.17 247.66 (4) 1912 UB, 5 bad seeds
xmsx32 2039.10 46.39 249.30 (7) 192 2 bad seeds
mirhash 6139.07 37.02 209.47 (3) 1112 UB, 2^36 bad seeds, LongNeighbors, machine-specific (32/64 differs)
mirhashstrict 3549.01 49.99 224.91 (2) 1112
mirhashstrict32low 3441.35 50.60 247.19 (3) 1112 1 bad seed, MomentChi2 9
fasthash32 6128.28 40.30 241.64 (4) 566 UB
fasthash64 5818.92 38.70 220.74 (2) 509 UB
aesni 31232.34 29.21 230.14 (4) 519 machine-specific (x64 AES-NI)
aesni-low 31221.14 29.64 226.18 (3) 519 machine-specific (x64 AES-NI)
mx3 9034.90 48.71 227.89 (2) 734 UB
pengyhash 13428.80 74.24 275.42 (5) 421
City32 5551.28 54.40 261.64 (2) 1319
City64low 13904.10 46.24 260.08 (3) 1120
City128 14031.96 89.09 290.05 (10) 1841
CityCrc128 7916.44 55.50 240.79 (2) 295
FarmHash32 21755.58 47.54 258.35 (3) 11489 machine-specific (x64 SSE4/AVX)
FarmHash64 12845.53 47.11 251.58 (3) 3758
FarmHash128 13913.65 70.25 263.06 (3) 163
farmhash32_c 21601.86 47.38 273.00 (3) 762 machine-specific (x64 SSE4/AVX)
farmhash64_c 12834.10 47.23 246.20 (2) 3688
farmhash128_c 13753.24 68.96 263.76 (3) 1890
metrohash64_2 14316.37 40.23 218.28 (3) 627 UB, LongNeighbors
cmetrohash64_2 14294.26 40.76 221.40 (4) 655 LongNeighbors
metrohash128 15634.66 73.28 261.23 (4) 773 UB, LongNeighbors
metrohash128_1 15806.97 72.30 260.90 (4) 773 UB, LongNeighbors
metrohash128_2 15822.60 72.30 255.34 (3) 773 UB, LongNeighbors
metrohash128crc_1 8009.23 78.72 281.55 (13) 723 UB, machine-specific (SSE4.2/NEON)
metrohash128crc_2 7878.22 79.90 275.22 (4) 723 UB, machine-specific (SSE4.2/NEON)
xxHash64 12108.87 49.78 228.83 (2) 1999
Spooky32 13108.95 56.27 255.36 (3) 2221 UB
Spooky64 13529.36 58.76 236.31 (3) 2221 UB
Spooky128 11781.35 58.91 242.91 (3) 2221 UB
SpookyV2_32 13529.16 55.55 248.37 (4) 2069
SpookyV2_64 12678.82 56.71 243.21 (4) 2069
SpookyV2_128 13512.82 58.33 244.56 (5) 2069
ahash64 9862.62 27.32 181.68 (1) 412 rust
xxh3 21033.55 29.48 226.77 (4) 744 DiffDist bit 7 w. 36 bits, BIC
xxh3low 17093.19 30.57 242.07 (7) 756
xxh128 18802.16 32.37 234.30 (4) 1012
xxh128low 18833.05 32.30 234.68 (3) 1012
t1ha2_atonce 13854.44 37.92 233.54 (2) 541 Zeroes low3
t1ha2_atonce128 14148.42 55.70 253.74 (6) 613 LongNeighbors
t1ha0_aes_noavx 27231.59 37.70 236.10 (3) 925 LongNeighbors, machine-specific (x86 AES-NI)
t1ha0_aes_avx1 22714.85 48.12 226.52 (16) 843 LongNeighbors, machine-specific (x64 AVX.txt)
t1ha0_aes_avx2 56919.46 36.70 233.14 (2) 792 LongNeighbors, machine-specific (x64 AVX2)
wyhash32 2532.89 48.40 484.57 (1) 426 4 bad and broken seeds, 32-bit
wyhash32low 22393.77 29.04 243.40 (3) 474 5 bad seeds
wyhash 22540.23 28.87 236.16 (8) 474
umash32 21427.57 42.12 255.55 (5) 1530
umash32_hi 21483.12 42.65 251.09 (4) 1530
umash64 21690.08 41.67 238.01 (4) 1530
umash128 13211.88 43.37 237.40 (3) 1530
halftime_hash64 4735.63 99.90 315.34 (3) 2911
halftime_hash128 17534.53 97.97 311.10 (4) 2462
halftime_hash256 18003.39 99.46 315.09 (3) 2622
halftime_hash512 10890.15 118.05 333.45 (3) 3550
nmhash32 12969.62 55.88 265.69 (4) 2445
nmhash32x 12775.08 42.66 246.05 (3) 1494
k-hashv32 9181.87 52.76 245.14 (3) 1280
k-hashv64 7850.92 46.94 193.94 (1) 1279
komihash 12242.78 33.02 236.07 (2) 1323
polymur 9676.33 42.70 246.53 (3) 1128

The sortable table variants:

Summary

I added some SSE assisted hashes and fast intel/arm CRC32-C, AES and SHA HW variants. See also the old https://github.com/aappleby/smhasher/wiki, the improved, but unmaintained fork https://github.com/demerphq/smhasher, and the new improved version SMHasher3 https://gitlab.com/fwojcik/smhasher3.

So the fastest hash functions on x86_64 without quality problems are:

  • xxh3low
  • wyhash
  • umash (even universal!)
  • ahash64
  • t1ha2_atonce
  • komihash
  • FarmHash (not portable, too machine specific: 64 vs 32bit, old gcc, ...)
  • halftime_hash128
  • Spooky32
  • pengyhash
  • nmhash32
  • mx3
  • MUM/mir (different results on 32/64-bit archs, lots of bad seeds to filter out)
  • fasthash32

Hash functions for symbol tables or hash tables typically use 32 bit hashes, for databases, file systems and file checksums typically 64 or 128bit, for crypto now starting with 256 bit.

Typical median key size in perl5 is 20, the most common 4. Similar for all other dynamic languages. See github.com/rurban/perl-hash-stats

When used in a hash table the instruction cache will usually beat the CPU and throughput measured here. In my tests the smallest FNV1A beats the fastest crc32_hw1 with Perl 5 hash tables. Even if those worse hash functions will lead to more collisions, the overall speed advantage and inline-ability beats the slightly worse quality. See e.g. A Seven-Dimensional Analysis of Hashing Methods and its Implications on Query Processing for a concise overview of the best hash table strategies, confirming that the simplest Mult hashing (bernstein, FNV*, x17, sdbm) always beat "better" hash functions (Tabulation, Murmur, Farm, ...) when used in a hash table.

The fast hash functions tested here are recommendable as fast for file digests and maybe bigger databases, but not for 32bit hash tables. The "Quality problems" lead to less uniform distribution, i.e. more collisions and worse performance, but are rarely related to real security attacks, just the 2nd sanity AppendZeroes test against \0 invariance is security relevant.

Columns

MiB/sec: The average of the Bulk key speed test for alignments 0-7 with 262144-byte keys. The higher the better.

cycl./hash: The average of the Small key speed test for 1-31 byte keys. The smaller the better.

cycl./map: The result of the Hashmap test for /usr/dict/words with fast C++ hashmap get queries, with the standard deviation in brackets. This tests the inlinability of the hash function in practise (see size). The smaller the better.

size: The object size in byte on AMD64. This affects the inlinability in e.g. hash tables. The smaller the better.

Quality problems: See the failures in the linked doc. The less the better.

Other

SECURITY

The hash table attacks described in SipHash against City, Murmur or Perl JenkinsOAAT or at Hash Function Lounge are not included here. We list some known attacks at GH #186.

Such an attack avoidance cannot be the problem of the hash function, but only the hash table collision resolution scheme. You can attack every single hash function, even the best and most secure if you detect the seed, e.g. from language (mis-)features, side-channel attacks, collision timings and independly the sort-order, so you need to protect your collision handling scheme from the worst-case O(n), i.e. separate chaining with linked lists. Linked lists chaining allows high load factors, but is very cache-unfriendly. The only recommendable linked list scheme is inlining the key or hash into the array. Nowadays everybody uses fast open addressing, even if the load factor needs to be ~50%, unless you use Cuckoo Hashing.

I.e. the usage of SipHash for their hash table in Python 3.4, ruby, rust, systemd, OpenDNS, Haskell and OpenBSD is pure security theatre. SipHash is not secure enough for security purposes and not fast enough for general usage. Brute-force generation of ~32k collisions need 2-4m for all these hashes. siphash being the slowest needs max 4m, other typically max 2m30s, with <10s for practical 16k collision attacks with all hash functions. Using Murmur is usually slower than a simple Mult, even in the worst case. Provable secure is only uniform hashing, i.e. 2-5 independent Mult or Tabulation, or using a guaranteed logarithmic collision scheme (a tree) or a linear collision scheme, such as swisstable/folly-F14, Robin Hood or Cuckoo hashing with collision counting.

One more note regarding security: Nowadays even SHA1 can be solved in a solver, like Z3 (or faster ones) for practical hash table collision attacks (i.e. 14-20 bits). All hash functions with less than 160 bits tested here cannot be considered "secure" at all.

The '\0' vulnerability attack with binary keys is tested in the 2nd Sanity Zero test.

CRYPTO

Our crypto hashes are hardened with an added size_t seed, mixed into the initial state, and the versions which require zero-padding are hardened by adding the len also, to prevent from collisions with AppendedZeroes for the padding. The libtomcrypt implementations already provide for that, but others might not. Without, such crypto hash functions are unsuitable for normal tasks, as it's trivial to create collisions by padding or bad seeds.

The official NIST hash function testsuite does not do such extensive statistical tests, to search for weak ranges in the bits. Also crypto does not change the initial state, which we do here for our random 32bit seed. Crypto mostly cares about unreversable key -> hash functions without changing the initial fixed state and timings/sidechannel attacks.

The NIST "Cryptographic Algorithm Validation Program" (CAVP) involves the testing of the implementations of FIPS-approved and NIST-recommended cryptographic algorithms. During the NIST SHA-3 competition, the testing methodology was borrowed from the "CAVP", as the KATs and MCTs of the SHA-3 Competition Test Suite were based on the CAVP tests for SHA-2. In addition to this, the “Extremely Long Message Test,” not present in the CAVP for SHA-2, required the submitters to generate the hash value corresponding to a message with a length of 1 GiB. “NIST - Cryptographic Algorithm Validation Program (CAVP),” June 2017. Available: http://csrc.nist.gov/groups/STM/cavp (No testing source code provided, just high-level descriptions)

Two other independent third party testsuites found an extensive number of bugs and weaknesses in the SHA3 candidates. "Finding Bugs in Cryptographic Hash Function Implementations", Nicky Mouha, Mohammad S Raunak, D. Richard Kuhn, and Raghu Kacker, 2017. https://eprint.iacr.org/2017/891.pdf

Maybe independent researchers should come together to do a better public SHA-4 round, based on better and more testing methods, open source code for the tests, and using standard industry practices, such as valgrind, address-sanitizer and ubsan to detect obvious bugs.

PROBLEMS

  • Bad Seeds

    Hash functions are typically initialized with a random seed. But some seed values may lead to bad hash functions, regardless of the key. In the regular case with random seeds the probablity of such bad seeds is very low, like 2^32 or 2^64. A practical application needs to know if bad seeds exist and choose another one. See e.g. mirhash_seed_init() and mirhash_bad_seeds() in Hashes.h. Note that a bad seed is not really a problem when you skip this seed during initialization. It can still be a GOOD or recommended hash function. But a bad seed of 0 leading to collisions is considered a bug, a bad hash function.

    We test for internal secrets, if they will be multiplied with 0. This is also called "blinding multiplication". main.cpp lists some secrets for each hash function we test against. The function <hash>_bad_seeds() lists the confirmed bad seeds.

    Special care needs to be taken for crc, most FNV1 variants, fletcher, Jenkins. And with GOOD hashes most MUM variants, like mirhash, MUM, wyhash.

    Independently from this, when the attacker knows the seed it will lead to DDOS attacks. Even with crypto hashes in power2 hashtables.

Typical undefined behaviour (UB) problems:

  • Misaligned

    Many word-wise hashes (in opposite to safe byte-wise processing) don't check the input buffer for proper word alignment, which will fail with ubsan or Sparc. word being int32_t or int64_t or even more. On some old RISC hardware this will be a BUS error, you can even let Intel HW generate such a bus error by setting some CPU flag. But generally using misaligned accesses is fine.

    These are: mx3, Spooky, mirhash (but not strict), MUM, fasthash, Murmur3*, Murmur2*, metrohash* (all but cmetro*), Crap8, beamsplitter, lookup3, fletcher4, fletcher2, all sanmayce FNV1a_ variants (FNV1a_YT, FNV1A_Pippip_Yurii, FNV1A_Totenschiff, ...), fibonacci.

    The usual mitigation is to check the buffer alignment either in the caller, provide a pre-processing loop for the misaligned prefix, or copy the whole buffer into a fresh aligned area. Put that extra code inside #ifdef HAVE_ALIGNED_ACCESS_REQUIRED.

  • oob - Out of bounds

    Some hash function assume a padded input buffer which can be accessed past its length up to the word size. This allows for faster loop processing, as no 2nd loop or switch table for the rest is needed, but it requires a cooperative calling enviroment and is as such considered cheating.

  • Signed integer overflow

    A simple type error, this hash needs to use unsigned integer types internally, to avoid undefined and inconsistent behaviour. i.e. SuperFastHash: signed integer overflow: -2147483641 + -113 cannot be represented in type 'int'

  • shift exponent overflow

    With: FNV1A_Pippip_Yurii, FNV1A_Totenschiff, pair_multiply_shift, sumhash32 shift exponent 64 is too large for 64-bit type 'long unsigned int'

smhasher's People

Contributors

atdt avatar avaneev avatar cjacek avatar cyan4973 avatar data-man avatar dlebed avatar dunpyl avatar erthink avatar funny-falcon avatar fwojcik avatar jbapple avatar jbruchon avatar jherico avatar logan007 avatar mqudsi avatar o0101 avatar odidev avatar paulie-g avatar peterrk avatar pkhuong avatar rurban avatar schiller-manuel avatar shaan1337 avatar tansy avatar thomasahle avatar tkaitchuck avatar uxcn avatar valera-rozuvan avatar vegorov1 avatar wangyi-fudan avatar

Stargazers

avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar

Watchers

avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar

Forkers

koolhazz ikruglov uname nventdata aburan28 mohae blep overstart uxcn chunhui-shi vegorov1 containerz zzl0 erthink funny-falcon chunhualiu divfor mzsk michaeljclark mcaceresb skyformat99 ralic jessebo own2pwn gpakosz igxactly-forks scottbtang dbremner troosh zhouyonglong cjacek dunpyl bobhansen databmk jeisc oparvu dev-alex-alex2006hw google6 yougzh martinus hello-anmol cih-y2k cybernetics cyan4973 vdt ib23 monomagentaeggroll 4144 switch33 ourobouros zhangdinet zkh2018 blacknovatech paulie-g brucewanght backwardn dingdang2012 denise-amiga kutayzorlu data-man sonntex vakninyogev dosycorps hashtang sanarora hinh1108 jinfeihan57 espadrine marcelomata clayne hansonzhao007 cxz tevador jackwasey yehia2amer freewheelerz hixio-mh thomasahle aureooms-contrib jakobtejs pkhuong ivan-v-kush gopherj jbapple jart mohneeshjha odidev ohsdba sighingnow zenoproject logan007 atdt shaan1337 riazantsev jtholmi jbro885 kevin-14 maorv fxamacker michaelbelousov

smhasher's Issues

null test 

bool NullTest ( struct HashInfo *info ){
  pfHash hash = info->hash;
  unsigned long long h0,	h1;	
  hash(NULL,	0,	0,	&h0);	
  hash(NULL,	0,	1,	&h1);
  printf("nullkey_seed0\t%llu\nnullkey_seed1\t%llu\n%s\n",	h0,	h1,	
           h0==h1?"FAIL":(h0==0||h1==1?"Imperfect":"PASS"));
  return	h0!=h1;
}

clhash FAIL

fasthash64 Imperfect

City64 Imperfect

MUM Imperfect

xxh3 Imperfect

t1ha2_atonce Imperfect

I break t1ha using practrand

Hi, I used Lemire's https://github.com/lemire/testingRNG to break t1ha.
The trick is to transform a hash function to a PRNG, and test it using mature PRNG tests, such as testU01 and practrand.
I edited testxorshift128plus.c with the following code :
//#include "xorshift128plus.h"
#include "t1ha.c"
uint64_t seed, zero=0;
void xorshift128plus_seed(uint64_t s){ seed=s; }
uint64_t xorshift128plus(void){ seed++; return t1ha(&zero, 8, seed); }

in this way, t1ha is forced to act as a PRNG using his weak seed. And practrand crushed the original t1ha and t1ha1_le. However, t1ha2_atonce seems to survive.
This trick may be incorporated to SMHasher to crush more hash function.

Add more realistic Text HashTable tests

Find the distribution of the most common chars in programming language names (ean...)
Test against randomly generated names from those with typical short lengths (see rurban/perl-hash-stats).

And test a more common hash table speed scenario (I-Cache),
to verify why FNV1A and Spooky32 are so much better there than the others.

CPU feature detection

Could I suggest parsing gcc -march=native -dM -E - <<< '' rather than /proc/cpuinfo? It'll be implicitly filtered to whatever the current compiler can handle; which helps for old compilers, but also captures features that appear in the future with less rework to the parser.

This makes it easier to work with cross compilers because the command will return a tangible error, and then it can fail over to $CC $CFLAGS -dM -E - <<< '' and those variables can be set as needed to choose the required hardware features.

I think this might also be a better way to handle ABIs like x32 (and others), which have a 32-bit pointer but native 64-bit arithmetic.

Better Hashmap tests

Originally I also checked various other much faster linear probing hashmaps, such as e.g. from rigtorp or the two swisstable variants (Google and Facebook), but I settled with the slow standard (seperate chaining) for fair comparison purposes.
Maybe add other ones, and document them.

@dumblob Speaking about currently worldwide available hashmaps, definitely skim the comparison from Martin Ankerl https://martin.ankerl.com/2019/04/01/hashmap-benchmarks-05-conclusion/ to notice one very important thing. Namely that some hashmaps are almost not at all sensitive to collisions and throughput and latency (Throughput versus latency) of the hash function, but other hashmaps rely completely on the quality and throughput and/or latency of the hash function.
To be fair in showing real use case scenarios, we would actually need to test one representative from the sensitive corner and one from the insensitive corner.

@rurban True. There should be a fast, sensitive linear probing also, besides the usual insensitive std chaining. About a robin_hood I'm not sure. It's much more stable than linear probing, and from outside just a fast chaining variant.
we need to add the stddev to the mean cycles. I'll also add the initial insert/delete timings, but without trials and outlier removal.
For poor hash functions add better security measures, like collision counting or tree-conversion.
None of the usual hashmaps are secure, so maybe add fixed versions and test the overhead.

The goal should be to choose a good hash function, small (inlinable!) and not too many collisions, based on the timings, for slow <unordered_map> and fast hash tables. With string keys, not numbers.

Parts taken from the discussions at #80 and #61

Differential test results in out of memory

I made some tests with smhasher and modyfied sumhash32 with this:

void
sumhash32(const void *key, int len, uint32_t seed, void *out)
{
	uint32_t	  h = seed,tmp;
	const uint32_t *data = (const uint32_t *)key;
#define ROT32(X,N) ((X<<N) | (X>>(32-N)))
#define mix(h,x) h += x;h *= x;h ^= ROT32(h,7);

	for (int i = 0; i < len / 4; i++) {
		mix(h,data[i]);
	}
	uint32_t mod = len % 4;
	len -= mod;
	uint32_t a = 0;
	for(int i = 0;i < mod;i++){
		a <<= 8;
		a |= ((unsigned char *)key)[len+i];
	}
	mix(h,a);
  	*(uint32_t *) out = h;
}

and during difftest it results in out of memory

wyhash

Dear Author:
I developed a new hash function that passed all your tests. It is the fastest one for short keys, faster than t1ha. Since I am new to github, just let you known it from this way. It is located at https://github.com/wangyi-fudan/wyhash

Running extended tests

I've been using this great fork of SMHasher to validate a new hash algorithm,
and in the process, I found it useful to push the tests to higher limits.

The reason is, most tests are designed around "small" input length, in order to scout a tractable search space. Unfortunately, many modern hash algorithms feature different code paths depending on the input size. As a consequence, path for large input length is not stressed enough, which makes it possible to "pass" the tests, while they were effectively skipped.

Another factor is that computing capacity has increased a lot since SMHasher initial release, and it's now less problematic to run and analyse many more results per test.

I've implemented these changes in a fork at Cyan4973/SMHasher. I was wondering if you would be interested in such changes, and if yes, if you have some PR-related requirements, for example around patch size.

CPU tests: Crash with SIGILL

Hi, smasher crashes on my system with this:

Program received signal SIGILL, Illegal instruction.
0x00005555555b2d0a in _mm_aesenc_si128 (__Y=..., __X=...) at /usr/lib/gcc/x86_64-linux-gnu/6/include/wmmintrin.h:63

Could this be a problem with CPU feature detection?

I'm running Debian 9.5, my Processor is a i5 760.
Flags from my /proc/cpuinfo:
flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc aperfmperf pni dtes64 monitor ds_cpl vmx smx est tm2 ssse3 cx16 xtpr pdcm sse4_1 sse4_2 popcnt lahf_lm ssbd ibrs ibpb stibp kaiser tpr_shadow vnmi flexpriority ept vpid dtherm ida flush_l1d

wyhash bug fixed

Dear rurban:
Tommy Ettinger fixed a bug in wyhash which cause avalanche failure in 136 bit. wyhash have been updated. (I updated too quickly, sorry to trouble you frequently :-)

generate better docs: md and graphs

Generate more informative docs.
markdown with graphs should be good enough.
Also generate more docs comparing the top 5 in each category.

see e.g. demerphq/smhasher

Moment test breaks several hashes including xxh3 

void MomentTest ( pfHash hash){
	printf("Running MomentTest...\n");
	unsigned	k=0,	s=0;
	unsigned long long l,	h,	x;
	long double sa=0,	saa=0,	sb=0,	sbb=0,	n=0xffffffffull;
	hash(&k,4,s,&l);	for(unsigned	i=1;	i>0;	i++){	hash(&i,4,s,&h);	x=__builtin_popcountll(l^h);	x=x*x*x*x*x;	sa+=x;	saa+=x*x;	l=h;	}
	hash(&k,4,s,&l);	for(unsigned	i=1;	i>0;	i++){	hash(&k,4,i,&h);	x=__builtin_popcountll(l^h);	x=x*x*x*x*x;	sb+=x;	sbb+=x*x;	l=h;	}
	sa/=n;	saa=(saa/n-sa*sa)/n;	sb/=n;	sbb=(sbb/n-sb*sb)/n;	double	chi2=(sa-sb)*(sa-sb)/(saa+sbb);
	printf("KeySeedMomentChi2:\t%g\t%s\n",	chi2,	chi2>3.84145882069413?"FAIL!!!!":"PASS");
}

64bit hash chisq:
t1ha2_atonce 0.0170684 PASS
wyhash 0.0347747 PASS
xxHash64 0.145062 PASS
MUM 0.589962 PASS
farmhash64_c 1.05341 PASS
SipHash 2.38213 PASS
(c)metrohash64_2 3.43323 PASS
Spooky64 14.5622 FAIL
(c)metrohash64_1 674.801 FAIL
fasthash64 15556.8 FAIL
xxh3 117826 FAIL

32bit hash chisq:
GoodOAAT 0.00156549 PASS
MUMlow: 0.0022278 PASS
City32 0.0325398 PASS
wyhash32low 0.0465943 PASS
fasthash32 1.7319 PASS
City64low 4.3816 FAIL
Spooky32 34.9565 FAIL
xxHash32 344.586 FAIL
Murmur3A 97936.1 FAIL

wyhash have been updated accord to this new finding :-)

wyhash update

Dear rurban:
wyhash have been updated significantly with the "threat" of XXH3. The cycles per hash have been reduced by 1.5 on average. The long key speed is much higher. Also portability has been improve due to aligned read. cheers!

Add some more hash funcs

https://code.google.com/p/crcutil/ has some efficient (in fact the currently most efficient) funcs. multiword_128_64_gcc_amd64_sse2

http://www.strchr.com/hash_functions lists some FNV1 based improvements and more, with a good quality check from the dragon book.
https://github.com/gpnuma/fsbench-density.git could be imported as submodule.
esp. Jesteress, Meiyan, YoshimitsuTRIAD, Tesla, ...
and they (fsbench) have also all the new secure hashes.

CityHash32 (without seed, but can be added. I wrote one)

fletcher2,4 from ZFS

I wrote also the metrohash64crc_1,2 variants, but with too many collisions in one test so far.

sse4.2 run-time probing can be added into main, to see if the target can run the version which was configured.

Check for arithmetic collisions

I have recently discovered some hash functions perform poorly on arithmetic operations on hashes,

For example on the FNV1a family, if I hash 32-bit integers, then if a+b=c+d, then f(a)+f(b)=f(c)+f(d). I think testing some basic arithmetic properties of hashes might be interesting. I'm not sure the best way of going about adding new tests, is there a guide (and are you interested in new types of tests?)

FNV1A_Yorikke - The branchless superfast lookuper for SMALL KEYS

Hi Reini,
please consider taking a look at my latest-n-fastest etude - 'Yorikke':

The source code along with the superheavy (1 trillion unique keys) benchmark is freely downloadable at:
www.sanmayce.com/Fastest_Hash/Knight-Tour_FNV1A_Yorikke_vs_CRC32_TRISMUS.zip

The quick overview:

// "There it now stands for ever. Black on white.
// I can't get away from it. Ahoy, Yorikke, ahoy, hoy, ho!
// Go to hell now if you wish. What do I care? It's all the same now to me.
// I am part of you now. Where you go I go, where you leave I leave, when you go to the devil I go. Married.
// Vanished from the living. Damned and doomed. Of me there is not left a breath in all the vast world.
// Ahoy, Yorikke! Ahoy, hoy, ho!
// I am not buried in the sea,
// The death ship is now part of me
// So far from sunny New Orleans
// So far from lovely Louisiana."
// /An excerpt from 'THE DEATH SHIP - THE STORY OF AN AMERICAN SAILOR' by B.TRAVEN/
// 
// "Walking home to our good old Yorikke, I could not help thinking of this beautiful ship, with a crew on board that had faces as if they were seeing ghosts by day and by night.
// Compared to that gilded Empress, the Yorikke was an honorable old lady with lavender sachets in her drawers.
// Yorikke did not pretend to anything she was not. She lived up to her looks. Honest to her lowest ribs and to the leaks in her bilge.
// Now, what is this? I find myself falling in love with that old jane.
// All right, I cannot pass by you, Yorikke; I have to tell you I love you. Honest, baby, I love you.
// I have six black finger-nails, and four black and green-blue nails on my toes, which you, honey, gave me when necking you.
// Grate-bars have crushed some of my toes. And each finger-nail has its own painful story to tell.
// My chest, my back, my arms, my legs are covered with scars of burns and scorchings.
// Each scar, when it was being created, caused me pains which I shall surely never forget.
// But every outcry of pain was a love-cry for you, honey.
// You are no hypocrite. Your heart does not bleed tears when you do not feel heart-aches deeply and truly.
// You do not dance on the water if you do not feel like being jolly and kicking chasers in the pants.
// Your heart never lies. It is fine and clean like polished gold. Never mind the rags, honey dear.
// When you laugh, your whole soul and all your body is laughing.
// And when you weep, sweety, then you weep so that even the reefs you pass feel like weeping with you.
// I never want to leave you again, honey. I mean it. Not for all the rich and elegant buckets in the world.
// I love you, my gypsy of the sea!"
// /An excerpt from 'THE DEATH SHIP - THE STORY OF AN AMERICAN SAILOR' by B.TRAVEN/
//
#define _rotl_KAZE(x, n) (((x) << (n)) | ((x) >> (32-(n))))
#define _PADr_KAZE(x, n) ( ((x) << (n))>>(n) )
#define ROLInBits 27 // 5 in r.1; Caramba: it should be ROR by 5 not ROL, from the very beginning the idea was to mix two bytes by shifting/masking the first 5 'noisy' bits (ASCII 0-31 symbols).
uint32_t FNV1A_Hash_Yorikke_v2(const char *str, uint32_t wrdlen)
{
    const uint32_t PRIME = 591798841;
    uint32_t hash32 = 2166136261;
    uint64_t PADDEDby8;
    const char *p = str;
	//uint64_t dbg=0x4241414141414143; // LSB first: CAAAAAAB
	//int i;
	//wrdlen=2;
	//PADDEDby8 = ( (*(uint64_t *)(&dbg+0)) << ((8-wrdlen&7)<<3) ) >> ((8-wrdlen&7)<<3);
	//PADDEDby8 = _PADr_KAZE(*(uint64_t *)(&dbg+0), (8-wrdlen&7)<<3);
	//printf("\n");
	//for (i=0; i<8; i++) {
	//printf("%c",*((char *)&PADDEDby8+i)); //CA
	//}
	//printf("\n");
	//exit(0);

    for(; wrdlen >= 2*sizeof(uint32_t); wrdlen -= 2*sizeof(uint32_t), p += 2*sizeof(uint32_t)) {
        hash32 = ( _rotl_KAZE(hash32,ROLInBits) ^ (*(uint32_t *)(p+0)) ) * PRIME;        
        hash32 = ( _rotl_KAZE(hash32,ROLInBits) ^ (*(uint32_t *)(p+4)) ) * PRIME;        
    }

// Alternatively, the remaining 7[-] bytes could be padded and processed as 2x4... with _PADr_KAZE(x, (8-wrdlen&7)<<3)

	//if (wrdlen) {
		PADDEDby8 = _PADr_KAZE(*(uint64_t *)(p+0), (8-wrdlen&7)<<3);
	        hash32 = ( _rotl_KAZE(hash32,ROLInBits) ^ *(uint32_t *)((char *)&PADDEDby8+0) ) * PRIME;        
	        hash32 = ( _rotl_KAZE(hash32,ROLInBits) ^ *(uint32_t *)((char *)&PADDEDby8+4) ) * PRIME;        
	//}

//    // Cases: 0,1,2,3,4,5,6,7
//    if (wrdlen & sizeof(uint32_t)) {
//		hash32 = (hash32 ^ *(uint16_t*)(p+0)) * PRIME;
//		hash32B = (hash32B ^ *(uint16_t*)(p+2)) * PRIME;
//		p += 2*sizeof(uint16_t);
//    }
//    if (wrdlen & sizeof(uint16_t)) {
//        hash32 = (hash32 ^ *(uint16_t*)p) * PRIME;
//        p += sizeof(uint16_t);
//    }
//    if (wrdlen & 1) 
//        hash32 = (hash32 ^ *p) * PRIME;

    return hash32 ^ (hash32 >> 16);
}

// https://www.strchr.com/hash_functions#comment_776
// The very instrumental and informative page of Peter Kankowski, first column is time (smaller-better), last one is collisions (smaller-better):
/*
dic_common_words.txt 
500 lines read
1024 elements in the table (10 bits)
           Jesteress:         55 [  110]
              Meiyan:         56 [  102]
             Yorikke:         54 [   98] ! Best Speed, Best Dispersion ! on Core 2, 32bit executable
              FNV-1a:         69 [  124]
              Larson:         68 [   99]
              CRC-32:         65 [  101]
             Murmur2:         71 [  103]
             Murmur3:         68 [  101]
           XXHfast32:         80 [  110]
         XXHstrong32:         80 [  109]
dic_fr.txt 
13408 lines read
32768 elements in the table (15 bits)
           Jesteress:       1757 [ 2427]
              Meiyan:       1775 [ 2377]
             Yorikke:       1672 [ 2413] ! Best Speed, - ! on Core 2, 32bit executable
              FNV-1a:       2097 [ 2446]
              Larson:       2033 [ 2447]
              CRC-32:       2140 [ 2400]
             Murmur2:       2266 [ 2399]
             Murmur3:       2116 [ 2376]
           XXHfast32:       2428 [ 2494]
         XXHstrong32:       2431 [ 2496]
dic_ip.txt 
3925 lines read
8192 elements in the table (13 bits)
           Jesteress:        436 [  819]
              Meiyan:        451 [  807]
             Yorikke:        486 [  789] ! - , Best Dispersion ! on Core 2, 32bit executable
              FNV-1a:        614 [  796]
              Larson:        587 [  789]
              CRC-32:        589 [  802]
             Murmur2:        566 [  825]
             Murmur3:        549 [  818]
           XXHfast32:        704 [  829]
         XXHstrong32:        704 [  829]
dic_numbers.txt 
500 lines read
1024 elements in the table (10 bits)
           Jesteress:         40 [  300]
              Meiyan:         32 [  125]
             Yorikke:         37 [   82] ! - , - ! on Core 2, 32bit executable
              FNV-1a:         35 [  108]
              Larson:         26 [   16]
              CRC-32:         34 [   64]
             Murmur2:         45 [  104]
             Murmur3:         42 [  104]
           XXHfast32:         53 [  102]
         XXHstrong32:         53 [  102]
dic_postfix.txt 
500 lines read
1024 elements in the table (10 bits)
           Jesteress:         70 [  106]
              Meiyan:         74 [  112]
             Yorikke:         76 [   99] ! - , - ! on Core 2, 32bit executable
              FNV-1a:        159 [  105]
              Larson:        160 [  105]
              CRC-32:        129 [   94]
             Murmur2:         99 [  111]
             Murmur3:         98 [  105]
           XXHfast32:         76 [  106]
         XXHstrong32:         82 [  112]
dic_prefix.txt 
500 lines read
1024 elements in the table (10 bits)
           Jesteress:         73 [  102]
              Meiyan:         77 [  106]
             Yorikke:         79 [   94] ! - , Best Dispersion ! on Core 2, 32bit executable
              FNV-1a:        165 [   94]
              Larson:        161 [   99]
              CRC-32:        135 [  107]
             Murmur2:        103 [  106]
             Murmur3:        101 [  103]
           XXHfast32:         77 [  103]
         XXHstrong32:         82 [  102]
dic_Shakespeare.txt 
3228 lines read
8192 elements in the table (13 bits)
           Jesteress:        357 [  585]
              Meiyan:        366 [  588]
             Yorikke:        349 [  536] ! Best Speed, - ! on Core 2, 32bit executable
              FNV-1a:        419 [  555]
              Larson:        404 [  583]
              CRC-32:        433 [  563]
             Murmur2:        471 [  566]
             Murmur3:        443 [  555]
           XXHfast32:        493 [  491]
         XXHstrong32:        493 [  491]
dic_variables.txt 
1842 lines read
4096 elements in the table (12 bits)
           Jesteress:        249 [  366]
              Meiyan:        256 [  350]
             Yorikke:        240 [  351] ! Best Speed, - ! on Core 2, 32bit executable
              FNV-1a:        318 [  374]
              Larson:        313 [  366]
              CRC-32:        309 [  338]
             Murmur2:        318 [  383]
             Murmur3:        299 [  334]
           XXHfast32:        336 [  347]
         XXHstrong32:        339 [  355]
*/

/*
E:\_TEXTUAL_MADNESS_bare-minimum_2019-Sep-28\Nakamichi_2019-Sep-28\hash_updated>Knight-Tour_FNV1A_Yorikke2_vs_CRC32_TRISMUS.exe a8 4000000000
Knight-Tour_FNV1A_Yorikke2_vs_CRC32_TRISMUS, subrevision Efix, written by Kaze (based on Kurt White's code), downloadable at www.sanmayce.com/Fastest_Hash
Purpose: to compare FNV1A_Yorikke2 and CRC32 by giving the highest number of collisions i.e. the deepest nest/layer, the-lesser-the-better.
Note: In this subrevision a KT is transformed to lowercase at each position ONCE, KT is transformed to lowercase and then to uppercase at each position ONCE,
      and these two 2x64 sequences reversed, i.e. all the 4x64 combinations.
      Thus excluding the original KT we can hash 1+ trillion 1Kb UNIQUE chunks by having only 4 billion KTs.
Example: D:\>Knight-Tour_FNV1A_Yorikke2_vs_CRC32_TRISMUS a8 4000000000
Polynomial used:
CRC32: 0x8F6E37A0
KEYS to be hashed = 4,000,000,000x4x64
HashSizeInBits = 27
ReportAtEvery = 134,217,727
Allocating HASH memory 512MB ... OK
Allocating HASH memory 512MB ... OK
The first KT:
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
gives following 4x64 UNIQUE derivatives:
a8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8c7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7e8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8g7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7h5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5g3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3h1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1f2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2h3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3g1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1e2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2c1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1a2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2b4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4a6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6b8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8d7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7f8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8h7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7g5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5f7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7h8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8g6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6h4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4g2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2e1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1c2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2a1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1b3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3a5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5b7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7d8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8c6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6a7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7c8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8e7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7g8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8h6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6g4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4h2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2f1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1d2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2b1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1a3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3b5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5d6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6f5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5d4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4f3E5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3e5C4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5c4B2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4b2D3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2d3F4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3f4E6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4e6C5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6c5A4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5a4B6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4b6D5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6d5F6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5f6E4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6e4C3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4c3D1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3d1E3
A8C7E8G7H5G3H1F2H3G1E2C1A2B4A6B8D7F8H7G5F7H8G6H4G2E1C2A1B3A5B7D8C6A7C8E7G8H6G4H2F1D2B1A3B5D6F5D4F3E5C4B2D3F4E6C5A4B6D5F6E4C3D1e3
e3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3d1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1c3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3e4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4f6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6d5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5b6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6a4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4c5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5e6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6f4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4d3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3b2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2c4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4e5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5f3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3d4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4f5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5d6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6b5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5a3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3b1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1d2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2f1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1h2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2g4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4h6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6g8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8e7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7c8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8a7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7c6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6d8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8b7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7a5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5b3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3a1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1c2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2e1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1g2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2h4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4g6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6h8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8f7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7g5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5h7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7f8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8d7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7b8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8a6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6b4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4a2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2c1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1e2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2g1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1h3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3f2H1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2h1G3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1g3H5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3h5G7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5g7E8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7e8C7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8c7A8
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7a8
A8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8C7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7E8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8G7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7H5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5G3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3H1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1F2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2H3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3G1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1E2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2C1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1A2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2B4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4A6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6B8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8D7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7F8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8H7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7G5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5F7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7H8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8G6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6H4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4G2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2E1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1C2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2A1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1B3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3A5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5B7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7D8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8C6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6A7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7C8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8E7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7G8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8H6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6G4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4H2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2F1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1D2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2B1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1A3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3B5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5D6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6F5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5D4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4F3e5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3E5c4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5C4b2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4B2d3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2D3f4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3F4e6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4E6c5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6C5a4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5A4b6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4B6d5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6D5f6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5F6e4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6E4c3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4C3d1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3D1e3
a8c7e8g7h5g3h1f2h3g1e2c1a2b4a6b8d7f8h7g5f7h8g6h4g2e1c2a1b3a5b7d8c6a7c8e7g8h6g4h2f1d2b1a3b5d6f5d4f3e5c4b2d3f4e6c5a4b6d5f6e4c3d1E3
E3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3D1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1C3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3E4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4F6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6D5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5B6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6A4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4C5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5E6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6F4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4D3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3B2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2C4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4E5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5F3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3D4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4F5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5D6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6B5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5A3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3B1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1D2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2F1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1H2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2G4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4H6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6G8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8E7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7C8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8A7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7C6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6D8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8B7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7A5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5B3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3A1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1C2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2E1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1G2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2H4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4G6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6H8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8F7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7G5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5H7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7F8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8D7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7B8a6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8A6b4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6B4a2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4A2c1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2C1e2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1E2g1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2G1h3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1H3f2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3F2h1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2H1g3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1G3h5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3H5g7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5G7e8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7E8c7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8C7a8
e3d1c3e4f6d5b6a4c5e6f4d3b2c4e5f3d4f5d6b5a3b1d2f1h2g4h6g8e7c8a7c6d8b7a5b3a1c2e1g2h4g6h8f7g5h7f8d7b8a6b4a2c1e2g1h3f2h1g3h5g7e8c7A8
FNV1A_Yorikke_v2       : KT_DumpCounter = 0,000,134,217,729; 000,000,002 x MAXcollisionsAtSomeSlots = 000,011; HASHfreeSLOTS = 0,049,574,606
CRC32 0x8F6E37A0, iSCSI: KT_DumpCounter = 0,000,134,217,729; 000,000,004 x MAXcollisionsAtSomeSlots = 000,011; HASHfreeSLOTS = 0,049,561,215
FNV1A_Yorikke_v2       : KT_DumpCounter = 0,000,268,435,457; 000,000,004 x MAXcollisionsAtSomeSlots = 000,014; HASHfreeSLOTS = 0,018,312,537
CRC32 0x8F6E37A0, iSCSI: KT_DumpCounter = 0,000,268,435,457; 000,000,004 x MAXcollisionsAtSomeSlots = 000,014; HASHfreeSLOTS = 0,018,307,048
FNV1A_Yorikke_v2       : KT_DumpCounter = 0,000,402,653,185; 000,000,022 x MAXcollisionsAtSomeSlots = 000,016; HASHfreeSLOTS = 0,006,764,093
CRC32 0x8F6E37A0, iSCSI: KT_DumpCounter = 0,000,402,653,185; 000,000,008 x MAXcollisionsAtSomeSlots = 000,017; HASHfreeSLOTS = 0,006,762,415
FNV1A_Yorikke_v2       : KT_DumpCounter = 0,000,536,870,913; 000,000,001 x MAXcollisionsAtSomeSlots = 000,022; HASHfreeSLOTS = 0,002,498,600
CRC32 0x8F6E37A0, iSCSI: KT_DumpCounter = 0,000,536,870,913; 000,000,002 x MAXcollisionsAtSomeSlots = 000,020; HASHfreeSLOTS = 0,002,496,170
FNV1A_Yorikke_v2       : KT_DumpCounter = 0,000,671,088,641; 000,000,002 x MAXcollisionsAtSomeSlots = 000,024; HASHfreeSLOTS = 0,000,921,568
CRC32 0x8F6E37A0, iSCSI: KT_DumpCounter = 0,000,671,088,641; 000,000,002 x MAXcollisionsAtSomeSlots = 000,023; HASHfreeSLOTS = 0,000,922,884
FNV1A_Yorikke_v2       : KT_DumpCounter = 0,000,805,306,369; 000,000,001 x MAXcollisionsAtSomeSlots = 000,027; HASHfreeSLOTS = 0,000,339,948
CRC32 0x8F6E37A0, iSCSI: KT_DumpCounter = 0,000,805,306,369; 000,000,002 x MAXcollisionsAtSomeSlots = 000,026; HASHfreeSLOTS = 0,000,339,990
FNV1A_Yorikke_v2       : KT_DumpCounter = 0,000,939,524,097; 000,000,001 x MAXcollisionsAtSomeSlots = 000,029; HASHfreeSLOTS = 0,000,125,193
CRC32 0x8F6E37A0, iSCSI: KT_DumpCounter = 0,000,939,524,097; 000,000,002 x MAXcollisionsAtSomeSlots = 000,028; HASHfreeSLOTS = 0,000,126,260
FNV1A_Yorikke_v2       : KT_DumpCounter = 0,001,073,741,825; 000,000,001 x MAXcollisionsAtSomeSlots = 000,030; HASHfreeSLOTS = 0,000,046,341
CRC32 0x8F6E37A0, iSCSI: KT_DumpCounter = 0,001,073,741,825; 000,000,002 x MAXcollisionsAtSomeSlots = 000,030; HASHfreeSLOTS = 0,000,046,780
FNV1A_Yorikke_v2       : KT_DumpCounter = 0,001,207,959,553; 000,000,002 x MAXcollisionsAtSomeSlots = 000,031; HASHfreeSLOTS = 0,000,017,252
CRC32 0x8F6E37A0, iSCSI: KT_DumpCounter = 0,001,207,959,553; 000,000,002 x MAXcollisionsAtSomeSlots = 000,030; HASHfreeSLOTS = 0,000,017,200
FNV1A_Yorikke_v2       : KT_DumpCounter = 0,001,342,177,281; 000,000,001 x MAXcollisionsAtSomeSlots = 000,033; HASHfreeSLOTS = 0,000,006,272
CRC32 0x8F6E37A0, iSCSI: KT_DumpCounter = 0,001,342,177,281; 000,000,002 x MAXcollisionsAtSomeSlots = 000,033; HASHfreeSLOTS = 0,000,006,284
FNV1A_Yorikke_v2       : KT_DumpCounter = 0,001,476,395,009; 000,000,002 x MAXcollisionsAtSomeSlots = 000,034; HASHfreeSLOTS = 0,000,002,304
CRC32 0x8F6E37A0, iSCSI: KT_DumpCounter = 0,001,476,395,009; 000,000,002 x MAXcollisionsAtSomeSlots = 000,034; HASHfreeSLOTS = 0,000,002,338
FNV1A_Yorikke_v2       : KT_DumpCounter = 0,001,610,612,737; 000,000,002 x MAXcollisionsAtSomeSlots = 000,036; HASHfreeSLOTS = 0,000,000,876
CRC32 0x8F6E37A0, iSCSI: KT_DumpCounter = 0,001,610,612,737; 000,000,006 x MAXcollisionsAtSomeSlots = 000,035; HASHfreeSLOTS = 0,000,000,834
FNV1A_Yorikke_v2       : KT_DumpCounter = 0,001,744,830,465; 000,000,005 x MAXcollisionsAtSomeSlots = 000,037; HASHfreeSLOTS = 0,000,000,292
CRC32 0x8F6E37A0, iSCSI: KT_DumpCounter = 0,001,744,830,465; 000,000,002 x MAXcollisionsAtSomeSlots = 000,038; HASHfreeSLOTS = 0,000,000,304
FNV1A_Yorikke_v2       : KT_DumpCounter = 0,001,879,048,193; 000,000,001 x MAXcollisionsAtSomeSlots = 000,040; HASHfreeSLOTS = 0,000,000,108
CRC32 0x8F6E37A0, iSCSI: KT_DumpCounter = 0,001,879,048,193; 000,000,004 x MAXcollisionsAtSomeSlots = 000,040; HASHfreeSLOTS = 0,000,000,124
FNV1A_Yorikke_v2       : KT_DumpCounter = 0,002,013,265,921; 000,000,003 x MAXcollisionsAtSomeSlots = 000,041; HASHfreeSLOTS = 0,000,000,041
CRC32 0x8F6E37A0, iSCSI: KT_DumpCounter = 0,002,013,265,921; 000,000,006 x MAXcollisionsAtSomeSlots = 000,041; HASHfreeSLOTS = 0,000,000,046
FNV1A_Yorikke_v2       : KT_DumpCounter = 0,002,147,483,649; 000,000,004 x MAXcollisionsAtSomeSlots = 000,042; HASHfreeSLOTS = 0,000,000,016
CRC32 0x8F6E37A0, iSCSI: KT_DumpCounter = 0,002,147,483,649; 000,000,004 x MAXcollisionsAtSomeSlots = 000,043; HASHfreeSLOTS = 0,000,000,008
FNV1A_Yorikke_v2       : KT_DumpCounter = 0,002,281,701,377; 000,000,002 x MAXcollisionsAtSomeSlots = 000,046; HASHfreeSLOTS = 0,000,000,007
CRC32 0x8F6E37A0, iSCSI: KT_DumpCounter = 0,002,281,701,377; 000,000,002 x MAXcollisionsAtSomeSlots = 000,045; HASHfreeSLOTS = 0,000,000,002
FNV1A_Yorikke_v2       : KT_DumpCounter = 0,002,415,919,105; 000,000,001 x MAXcollisionsAtSomeSlots = 000,049; HASHfreeSLOTS = 0,000,000,001
CRC32 0x8F6E37A0, iSCSI: KT_DumpCounter = 0,002,415,919,105; 000,000,002 x MAXcollisionsAtSomeSlots = 000,047; HASHfreeSLOTS = 0,000,000,000
FNV1A_Yorikke_v2       : KT_DumpCounter = 0,002,550,136,833; 000,000,001 x MAXcollisionsAtSomeSlots = 000,052; HASHfreeSLOTS = 0,000,000,000
CRC32 0x8F6E37A0, iSCSI: KT_DumpCounter = 0,002,550,136,833; 000,000,002 x MAXcollisionsAtSomeSlots = 000,048; HASHfreeSLOTS = 0,000,000,000
FNV1A_Yorikke_v2       : KT_DumpCounter = 0,002,684,354,561; 000,000,001 x MAXcollisionsAtSomeSlots = 000,052; HASHfreeSLOTS = 0,000,000,000
CRC32 0x8F6E37A0, iSCSI: KT_DumpCounter = 0,002,684,354,561; 000,000,002 x MAXcollisionsAtSomeSlots = 000,050; HASHfreeSLOTS = 0,000,000,000
FNV1A_Yorikke_v2       : KT_DumpCounter = 0,002,818,572,289; 000,000,001 x MAXcollisionsAtSomeSlots = 000,052; HASHfreeSLOTS = 0,000,000,000
CRC32 0x8F6E37A0, iSCSI: KT_DumpCounter = 0,002,818,572,289; 000,000,002 x MAXcollisionsAtSomeSlots = 000,052; HASHfreeSLOTS = 0,000,000,000
FNV1A_Yorikke_v2       : KT_DumpCounter = 0,002,952,790,017; 000,000,003 x MAXcollisionsAtSomeSlots = 000,053; HASHfreeSLOTS = 0,000,000,000
CRC32 0x8F6E37A0, iSCSI: KT_DumpCounter = 0,002,952,790,017; 000,000,002 x MAXcollisionsAtSomeSlots = 000,054; HASHfreeSLOTS = 0,000,000,000
...

E:\_TEXTUAL_MADNESS_bare-minimum_2019-Sep-28\Nakamichi_2019-Sep-28\hash_updated>
*/

wyhash V3

Dear Rurban:

wyhash has been updated to V3 https://github.com/wangyi-fudan/wyhash

I summarized the progress:

V1: your version. fast small key hash, security holes.

V1=>V2 security enhancement at the cost of a litte bulk speed loss. At least we can say that wyhash has paid attention to security.

V2=>V3 2X bulk hash speed improvement with the same security level with V2:

The speed benchmark is as follow (on a new very fast Xeon Gold CPU):

key size wyhash XXH_SCALAR XXH_SSE2 XXH3_AVX2 t1ha2_atonce
bulk:bytes/cycle 9.888 3.173 9.931 15.500 7.872
small:cycles/hash 13.070 18.293 18.304 18.242 25.830

Hope you like it.
Yours,
Yi

simplify the hash API, call the hash function naturally

Call the hash function naturally
e.g. 32bit: uint32_t hash(const char* key, int len, uint32_t seed);
or 64bit: uint64_t hash(const char* key, int len, uint64_t seed);

Add pfhash templates for 32bit, 64bit (skip 128bit? not really needed).
Add \_test functions only for those with a different signature: e.g. seed as first PMurHash32(MH_UINT32 seed, const void *key, int len);

So one doesn't have to provide unnatural API's just to get an smhasher advantage.

Maybe provide hash classes for all functions, seperated into bitsize, seedsize, with optional init (clhash), and converter (seed first, ...)

Are you actively accepting patches?

First off, thank you for updating smhasher from the Google code variant. I've been using smhasher to compare/contrast hashes, and I came across some modifications that lead to more consistent behavior (no more fractional cycles/hash, unless hashes are weird like that, and/or CPU scaling is in effect). I have also been adding more output column data for the small key speed tests.

Really, I just wanted to know if you were interested in PRs to provide more output information (possibly with a command line option), more consistent timings, fixes for compilation on some Ubuntu Linux variants. Speaking of which, some of my changes may take some testing on your end of things, and hopefully I can get it working with your existing test suite.

Have a great rest of your weekend.

Add security tests

There's still the myth of secure hash table functions around, esp. from the SipHash folks, as you can see at google/highwayhash#28
So add tests to prove them otherwise.

  • brute-force collisions of the bit range 0-32, and present the timings and number of collisions.
  • use a solver for 10bits, and present the timings to find the collisions.

Allow all keys of char 0-255, i.e. including null and control chars. hash functions take binary input, even if some applications reject those keys.
It is also a good metric for the hash function algorithmic complexity.

Absolute results are wrong

Looking at timing again, it's all off. E.g. FNV-1a has one IMUL (3 cycles latency) and one XOR (1 cycle latency) applied serially on each byte. It just can't be faster than 4 cycles per byte. Time stamp counter in newer processors is time-based, it increments on constant rate that doesn't change when CPU boosts its frequency, it doesn't depend on CPU state. So RDTSC doesn't measure real cycles passed anymore, and benchmark can report speed in cycles faster than it really executes. On my desktop 3.5GHz Haswell CPU (3.8GHz with TurboBoost), reported speed is 1-3.5/3.8=8% faster than real speed. On laptops it's apparently far more different.

"MiB/sec @ 3 ghz" is entirely wrong too. It's just the result of multiplication (bytes/cycle) * 3*10^9 / 1024^2, but bytes/cycle is wrong.

So while relative benchmark results are sensible and useful, absolute results are incorrect.

cross page boundary (Hash_Pippip)

Your algorithm (Hash_Pippip), can cross a MMU page boundary and can produce general protection fault.

As option I propose this (a bit modified FNV1a):

uint32_t fnv_1a(const char* key, size_t len)
{
    uint32_t hash32 = 2166136261;
    const uint32_t PRIME = 1607;

    for (size_t cnt = len / sizeof(uint32_t); cnt--; key += sizeof(uint32_t))
        hash32 = (hash32 ^ (*(uint32_t*)key)) * PRIME;

    if (len & sizeof(uint16_t)) {
        hash32 = (hash32 ^ (*(uint16_t*)key)) * PRIME;
        key += sizeof(uint16_t);
    }
    if (len & 1)
        hash32 = (hash32 ^ (*key)) * PRIME;

    return hash32 ^ (hash32 >> 16);
}

Make not found

When running testall.sh I get;

./testall.sh
make: *** No targets specified and no makefile found. Stop.
./testall.sh: 1: ./testall.sh: ./SMHasher: not found

What's the make process?

compilation metrohash64crc failder under MSVC9

i use https://github.com/flier/pyfasthash
in my python code
it's use your great smhasher repository as git submodule
when i try compile this extension under MCVC9

i have following errors

src\smhasher\metrohash64crc.cpp(52) : error C3861: '_mm_crc32_u64': identifier not found
src\smhasher\metrohash64crc.cpp(53) : error C3861: '_mm_crc32_u64': identifier not found
src\smhasher\metrohash64crc.cpp(54) : error C3861: '_mm_crc32_u64': identifier not found
src\smhasher\metrohash64crc.cpp(55) : error C3861: '_mm_crc32_u64': identifier not found
src\smhasher\metrohash64crc.cpp(84) : error C3861: '_mm_crc32_u64': identifier not found
src\smhasher\metrohash64crc.cpp(90) : error C3861: '_mm_crc32_u64': identifier not found
src\smhasher\metrohash64crc.cpp(96) : error C3861: '_mm_crc32_u64': identifier not found
src\smhasher\metrohash64crc.cpp(130) : error C3861: '_mm_crc32_u64': identifier not found
src\smhasher\metrohash64crc.cpp(131) : error C3861: '_mm_crc32_u64': identifier not found
src\smhasher\metrohash64crc.cpp(132) : error C3861: '_mm_crc32_u64': identifier not found
src\smhasher\metrohash64crc.cpp(133) : error C3861: '_mm_crc32_u64': identifier not found
src\smhasher\metrohash64crc.cpp(162) : error C3861: '_mm_crc32_u64': identifier not found
src\smhasher\metrohash64crc.cpp(168) : error C3861: '_mm_crc32_u64': identifier not found
src\smhasher\metrohash64crc.cpp(174) : error C3861: '_mm_crc32_u64': identifier not found
error: Setup script exited with error: command 'C:\\Users\\nulluser\\AppData\\Local\\Programs\\Common\\Microsoft\\Visual C++ for Python\\9.0\\VC\\Bin\\cl.exe' failed with exit status 2

i don't know C++ ;) sorry
could you help me resolve this compilation issue?

Typos in README summary table?

It seems typos were introduced to the README summary table in commit 00a4e5a.

I could be reading it wrong, but the "Quality problems" column in lines 49 through 69 appears to be shifted one row up for a few hashes: i.e. the problems noted correspond to the hash one row down. In commit 00a4e5a, a hash was added but the quality problems column does not appear to have been copied correctly.

The hashes affected are:

  • City32 vs City64: The former has no issues in the log but is noted to have 2 minor collisions, whereas the latter has no problems noted but has 2 collisions in its log (here).
  • Spooky128 vs xxHash32: The former has no issues in the log but is noted to have collisions with 4-bit differentials (here), whereas the latter has no problems noted but has a collision with 4-bit differentials (here).
  • metrohash128_2 vs metrohash64crc_1 and metrohash64crc_2: The first has no collisions in its log but is noted to have cyclic collisions with 8 byte (which is not even checked in the log, see here), whereas the second metrohash64 is noted to have no problems but also has cyclic collisions with 8 byte here.

Issues adding hash, linker errors

Hi,
I've been trying for quite a while now to get our blake2s hash added however I've been running into issues when trying to compile. I'm not sure if these issues I'm having are staring me right in the face but unfortunately I can't figure it out. Essentially, I added 3 header files and a C file. I assumed all I needed to do was add the blake2s.c into the cmakelists.txt add_library() function but that doesn't seem to help. Can anyone give me a hand here? I'd really appreciate it.

Let me go through what all I've added to make sure you have all the info you may need to help.
I have:
blake2.h
blake2-impl.h
blake2s.h
blake2s.c

I have included blake2s.c in the add_library() function in CMakeLists.txt

# CMakeLists.txt
add_library(
    SMHasherSupport
    # ......others
    blake2s.c
)

I have included blake2s.h in Hashes.h as well as given the following method definition:

// Hashes.h
#include "blake2s.h"
// ....other includes

void blake2s (const void *key, int len, uint32_t seed, void *out);
// ...….other has functions follow

In Hashes.cpp I have implemented the method.

// Hashes.cpp
void
blake2s(const void *key, int len, uint32_t seed, void *out)
{
    my_blake2s((char *)key, len, seed, (char *)out;
}

Lastly, in main.cpp I have put blake2s into g_hashes[]

// main.cpp
HashInfo g_hashes[] =
{
    { blake2s, 32, 0x0, "blake2s", "blake2s 32-bit cryptographic hash function"},
    // DoNothingHash and so on goes here

Note: I'm still having trouble understanding what values are coming through key, len, seed, and out but I'm assuming your definition of "key" is the string that you are trying to hash, len is the length of that string, seed is a random number to give an extra level of protection on the hash? Similar to a salt? And out is the final hash string? It seems everyone has a different term for things when it comes to hashing as the blake2s that my work is using says the key is the salt.
Anyways......this is what I got so far and everytime I try to compile, I receive this in terminal:

...
...
[98%] Building CXX object CMakeFiles/SMHasher.dir/main.cpp.o
[100%] Linking CXX executable SMHasher
./usr/bint/ld: libSMHasherSupport.a(Hashes.cpp.o): in function `blake2s(void const*, int, unsigned int, void*)':
Hashes.cpp:(.text+0x1): undefined reference to `my_blake2s(void const*, int, unsigned int, void*)'
collect2: error: ld returned 1 exit status
make[2]: *** [CMakeFiles/SMHasher.dir/build.make:85: SMHasher] Error 1
make[1]: *** [CMakeFiles/Makefile2:110: CMakeFiles/SMHasher.dir/all] Error 2
make: *** [Makefile:84: all] Error 2

So it seems everything goes fine until it's time to read from one my of files that aren't in the original repo (the my_blake2s file being in blake2s.c). I have added much smaller hash functions (like Djb2) directly to Hashes.cpp and after building first time I'm used to getting a verification hex code to slot in however I have not been able to get all of blake2s directly into Hashes.cpp without the multiple files (I'm an intern so don't have too much experience working with larger projects until recently - 4months ago).

Thanks!
Matt

Building on CMake 3.5.1 fails due to policy CMP0066

As mentioned in the title, the build fails with CMake 3.5.1 due to the CMP0066 policy (CMakeLists.txt:17), which was introduced in CMake 3.7. I assume that this will also cause the build to fail on any 3.x < 3.7 version since that the only check you are doing is IF (CMAKE_MAJOR_VERSION GREATER 2). You should check for major version >= 3 and minor version >= 7 before setting the policy. The same goes for the policy CMP0065 (introduced in version 3.4) and policy CMP00056 (introduced in version 3.2).

Here is the output from CMake 3.5.1 I get on my computer:

marco:~/prog/github/smhasher$ mkdir build && cd build
marco:~/prog/github/smhasher/build$ cmake ..
-- The C compiler identification is GNU 5.4.0
-- The CXX compiler identification is GNU 5.4.0
-- Check for working C compiler: /usr/bin/cc
-- Check for working C compiler: /usr/bin/cc -- works
-- Detecting C compiler ABI info
-- Detecting C compiler ABI info - done
-- Detecting C compile features
-- Detecting C compile features - done
-- Check for working CXX compiler: /usr/bin/c++
-- Check for working CXX compiler: /usr/bin/c++ -- works
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Detecting CXX compile features
-- Detecting CXX compile features - done
CMake Error at CMakeLists.txt:17 (cmake_policy):
  Policy "CMP0066" is not known to this version of CMake.


-- Check if the system is big endian
-- Searching 16 bit integer
-- Looking for sys/types.h
-- Looking for sys/types.h - found
-- Looking for stdint.h
-- Looking for stdint.h - found
-- Looking for stddef.h
-- Looking for stddef.h - found
-- Check size of unsigned short
-- Check size of unsigned short - done
-- Using unsigned short
-- Check if the system is big endian - little endian
-- Configuring incomplete, errors occurred!
See also "/home/marco/prog/github/smhasher/build/CMakeFiles/CMakeOutput.log".
See also "/home/marco/prog/github/smhasher/build/CMakeFiles/CMakeError.log".

strange or incorrect results in REAME.md

Seems here a set of mistakes:

  1. md5 and sha1 looks miserably
    md5_32a == 8589.93x collisions, distrib
    sha1_32a == collisions, 36.6% distrib
    Sure this could be truth, but a sign error in the code and/or in the test.

  2. falkhash result too much differs from local testing.
    Scores 39817.46, but my actual local test (i7-6700K) shows only 8909.54 MiB/Sec.
    For reference, t1ha_aes (properly optimized) shows 34867.98.

  3. results of functions that uses SSE4.2 CRC32C also notable differs from my local testing.
    CityCrc128: 21009.15 vs local 14807.96.
    t1ha_crc: 16757.73 vs local 19237.25.
    metrohash128crc_1: 27790.85 vs local 21289.30.

About the security claims in README

I'm not convinced that the claims about resistance to "hash flooding" algorithmic complexity DDoS attacks in the SECURITY chapter of README.md are correct. I'll address some of the claims.

Such an attack avoidance cannot not be the problem of the hash function, but the hash table collision resolution scheme.

The hash table collision resolution scheme does affect the performance but does not address the O(n) issues with hash collisions. A good resolution scheme can only help when (hash % tablesize) is equal between two hashes, but the hashes are not equal.

If two keys in the hash table give bit-to-bit identical hashes, the hash table implementation has to use strcmp() or similar to compare the entire key byte-by-byte. This will result in O(n^2) work with regards to the size of the input keys. This is bad when hashing HTTP request headers or other untrusted data.

This issue is made worse in the very simple hash functions because it's trivial to create hash collisions by appending a few bytes to the end of a key and strcmp() can't early exit before scanning the whole input.

You can attack every single hash function, even the best and most secure if you detect the seed

Indeed, the motivation for SipHash is to make recovering the key from timing information (or other side channels) difficult. It's the only hash function that I could find with any credible, peer-reviewed cryptanalysis on key recover.

Too bad that SipHash is pretty slow (2000 MB/s on my Skylake, the SSE2, SSSE3 and AVX2 implementations were slower) due to poor instruction level parallelism caused by explicit dependencies between instructions (in particular when implemented with SIMD). There are hash functions in smhasher that perform 5x to 15x faster than that.

If anyone is aware of any better performing hash functions that have been designed and analyzed with key recovery difficulty in mind, please do share.

Please discuss.

Add hmakholm/smhasher LongNeighborTest

Good test esp. for long blocks (Spooky), and the separate byte-wise processing of unaligned rest parts.
https://github.com/hmakholm/smhasher/blob/master/src/LongNeighborTest.md

This test uses a meet-in-the-middle approach to look for hash collisions between messages with low Hamming distances.

Developing the test was prompted by the discovery that SpookyHash V2 has lots of 3-bit collisions due to insufficient diffusion between the processing of the last full input block and the partial block at the end of the input. The goal of the test is to discover similar trouble in other hashes.

Because Spooky has an unusually large block size of 96 bytes (=768 bits), and it uses a completely different algorithm for messages shorter than 2 blocks, this problem only shows up for messages of length 281 to 287 bytes, and then again from 377 to 383 bytes, etc. Notably, messages of any "nice" length are not affected, which means that we need to test for all possible message lenghts.

Just need permission from Semmle Ltd

Massive difference in reported performance

I have a fork from some time in late 2015, which I used to add a c implementation of metrohash and a version with some optimizations for shorter keys. I kept the fork after the pull request was accepted upstream, here.

I've now tried the latest master and, besides what i reported in #45 , I am seeing massive differences in reported performance. For cmetrohash64_1, I am seeing:

--- my old fork (old build) ---
[[[ Speed Tests ]]]

Bulk speed test - 262144-byte keys
Alignment  7 -  4.087 bytes/cycle - 11694.32 MiB/sec @ 3 ghz
Alignment  6 -  4.087 bytes/cycle - 11694.35 MiB/sec @ 3 ghz
Alignment  5 -  4.088 bytes/cycle - 11694.78 MiB/sec @ 3 ghz
Alignment  4 -  4.087 bytes/cycle - 11691.98 MiB/sec @ 3 ghz
Alignment  3 -  4.087 bytes/cycle - 11692.93 MiB/sec @ 3 ghz
Alignment  2 -  4.088 bytes/cycle - 11695.01 MiB/sec @ 3 ghz
Alignment  1 -  4.087 bytes/cycle - 11693.52 MiB/sec @ 3 ghz
Alignment  0 -  4.214 bytes/cycle - 12057.15 MiB/sec @ 3 ghz
Average      -  4.103 bytes/cycle - 11739.26 MiB/sec @ 3 ghz

Small key speed test -    1-byte keys -    25.03 cycles/hash
Small key speed test -    2-byte keys -    22.72 cycles/hash
Small key speed test -    3-byte keys -    24.72 cycles/hash
Small key speed test -    4-byte keys -    23.93 cycles/hash
Small key speed test -    5-byte keys -    24.81 cycles/hash
Small key speed test -    6-byte keys -    31.58 cycles/hash
Small key speed test -    7-byte keys -    33.89 cycles/hash
Small key speed test -    8-byte keys -    24.33 cycles/hash
Small key speed test -    9-byte keys -    24.08 cycles/hash
Small key speed test -   10-byte keys -    24.59 cycles/hash
Small key speed test -   11-byte keys -    26.19 cycles/hash
Small key speed test -   12-byte keys -    24.89 cycles/hash
Small key speed test -   13-byte keys -    25.67 cycles/hash
Small key speed test -   14-byte keys -    32.87 cycles/hash
Small key speed test -   15-byte keys -    32.59 cycles/hash
Small key speed test -   16-byte keys -    25.20 cycles/hash
Small key speed test -   17-byte keys -    35.00 cycles/hash
Small key speed test -   18-byte keys -    33.86 cycles/hash
Small key speed test -   19-byte keys -    36.35 cycles/hash
Small key speed test -   20-byte keys -    33.22 cycles/hash
Small key speed test -   21-byte keys -    35.64 cycles/hash
Small key speed test -   22-byte keys -    34.87 cycles/hash
Small key speed test -   23-byte keys -    37.67 cycles/hash
Small key speed test -   24-byte keys -    28.85 cycles/hash
Small key speed test -   25-byte keys -    36.54 cycles/hash
Small key speed test -   26-byte keys -    35.79 cycles/hash
Small key speed test -   27-byte keys -    37.79 cycles/hash
Small key speed test -   28-byte keys -    36.27 cycles/hash
Small key speed test -   29-byte keys -    36.64 cycles/hash
Small key speed test -   30-byte keys -    36.64 cycles/hash
Small key speed test -   31-byte keys -    36.45 cycles/hash
Average                                    29.959 cycles/hash
---

--- my old fork (new build) ---
[[[ Speed Tests ]]]

Bulk speed test - 262144-byte keys
Alignment  7 -  4.282 bytes/cycle - 12252.21 MiB/sec @ 3 ghz
Alignment  6 -  4.282 bytes/cycle - 12250.16 MiB/sec @ 3 ghz
Alignment  5 -  4.282 bytes/cycle - 12251.42 MiB/sec @ 3 ghz
Alignment  4 -  4.282 bytes/cycle - 12251.76 MiB/sec @ 3 ghz
Alignment  3 -  4.282 bytes/cycle - 12251.84 MiB/sec @ 3 ghz
Alignment  2 -  4.283 bytes/cycle - 12253.69 MiB/sec @ 3 ghz
Alignment  1 -  4.283 bytes/cycle - 12253.13 MiB/sec @ 3 ghz
Alignment  0 -  4.477 bytes/cycle - 12808.42 MiB/sec @ 3 ghz
Average      -  4.307 bytes/cycle - 12321.58 MiB/sec @ 3 ghz

Small key speed test -    1-byte keys -    28.09 cycles/hash
Small key speed test -    2-byte keys -    28.04 cycles/hash
Small key speed test -    3-byte keys -    23.64 cycles/hash
Small key speed test -    4-byte keys -    22.84 cycles/hash
Small key speed test -    5-byte keys -    23.91 cycles/hash
Small key speed test -    6-byte keys -    25.69 cycles/hash
Small key speed test -    7-byte keys -    43.28 cycles/hash
Small key speed test -    8-byte keys -    27.13 cycles/hash
Small key speed test -    9-byte keys -    23.84 cycles/hash
Small key speed test -   10-byte keys -    23.90 cycles/hash
Small key speed test -   11-byte keys -    23.87 cycles/hash
Small key speed test -   12-byte keys -    23.09 cycles/hash
Small key speed test -   13-byte keys -    25.49 cycles/hash
Small key speed test -   14-byte keys -    26.53 cycles/hash
Small key speed test -   15-byte keys -    27.38 cycles/hash
Small key speed test -   16-byte keys -    26.85 cycles/hash
Small key speed test -   17-byte keys -    28.03 cycles/hash
Small key speed test -   18-byte keys -    28.09 cycles/hash
Small key speed test -   19-byte keys -    28.64 cycles/hash
Small key speed test -   20-byte keys -    28.61 cycles/hash
Small key speed test -   21-byte keys -    28.78 cycles/hash
Small key speed test -   22-byte keys -    29.31 cycles/hash
Small key speed test -   23-byte keys -    29.46 cycles/hash
Small key speed test -   24-byte keys -    26.75 cycles/hash
Small key speed test -   25-byte keys -    29.50 cycles/hash
Small key speed test -   26-byte keys -    30.41 cycles/hash
Small key speed test -   27-byte keys -    31.03 cycles/hash
Small key speed test -   28-byte keys -    30.18 cycles/hash
Small key speed test -   29-byte keys -    31.50 cycles/hash
Small key speed test -   30-byte keys -    32.22 cycles/hash
Small key speed test -   31-byte keys -    40.30 cycles/hash
Average                                    27.386 cycles/hash
---

--- master ---
[[[ Speed Tests ]]]

Bulk speed test - 262144-byte keys
Alignment  7 -  4.284 bytes/cycle - 12255.87 MiB/sec @ 3 ghz
Alignment  6 -  4.283 bytes/cycle - 12253.74 MiB/sec @ 3 ghz
Alignment  5 -  4.283 bytes/cycle - 12254.33 MiB/sec @ 3 ghz
Alignment  4 -  4.284 bytes/cycle - 12256.09 MiB/sec @ 3 ghz
Alignment  3 -  4.283 bytes/cycle - 12254.51 MiB/sec @ 3 ghz
Alignment  2 -  4.284 bytes/cycle - 12255.59 MiB/sec @ 3 ghz
Alignment  1 -  4.283 bytes/cycle - 12254.99 MiB/sec @ 3 ghz
Alignment  0 -  4.500 bytes/cycle - 12875.79 MiB/sec @ 3 ghz
Average      -  4.311 bytes/cycle - 12332.61 MiB/sec @ 3 ghz

Small key speed test -    1-byte keys -    25.00 cycles/hash
Small key speed test -    2-byte keys -    25.00 cycles/hash
Small key speed test -    3-byte keys -    31.00 cycles/hash
Small key speed test -    4-byte keys -    25.00 cycles/hash
Small key speed test -    5-byte keys -    30.00 cycles/hash
Small key speed test -    6-byte keys -    30.00 cycles/hash
Small key speed test -    7-byte keys -    36.00 cycles/hash
Small key speed test -    8-byte keys -    35.00 cycles/hash
Small key speed test -    9-byte keys -    40.00 cycles/hash
Small key speed test -   10-byte keys -    40.00 cycles/hash
Small key speed test -   11-byte keys -    46.00 cycles/hash
Small key speed test -   12-byte keys -    40.00 cycles/hash
Small key speed test -   13-byte keys -    45.88 cycles/hash
Small key speed test -   14-byte keys -    46.00 cycles/hash
Small key speed test -   15-byte keys -    52.00 cycles/hash
Small key speed test -   16-byte keys -    39.00 cycles/hash
Small key speed test -   17-byte keys -    45.00 cycles/hash
Small key speed test -   18-byte keys -    45.00 cycles/hash
Small key speed test -   19-byte keys -    50.46 cycles/hash
Small key speed test -   20-byte keys -    45.00 cycles/hash
Small key speed test -   21-byte keys -    50.00 cycles/hash
Small key speed test -   22-byte keys -    50.99 cycles/hash
Small key speed test -   23-byte keys -    56.00 cycles/hash
Small key speed test -   24-byte keys -    45.00 cycles/hash
Small key speed test -   25-byte keys -    50.00 cycles/hash
Small key speed test -   26-byte keys -    50.82 cycles/hash
Small key speed test -   27-byte keys -    56.00 cycles/hash
Small key speed test -   28-byte keys -    51.00 cycles/hash
Small key speed test -   29-byte keys -    56.00 cycles/hash
Small key speed test -   30-byte keys -    57.00 cycles/hash
Small key speed test -   31-byte keys -    62.00 cycles/hash
Average                                    43.747 cycles/
---

I started going through the 100 or so commits before now and then to try to figure out where this comes from, but finally decided it was quicker to ask ;)

As you can see, increase in throughput is the same for my old snapshot and current master if built with my current gcc 8.1.1. At least that's where it looks to be coming from. The difference in cycles/hash must be a result of something introduced since then. Has the way you count cycles fundamentally changed?

Commit broke cmetrohash64_1o

Commit fe3f367 which claims to fix "MSVC2015 x64 build" completely replaced all of my code in opt_cmetrohash64_1.c, breaking it in the process (you can't run smhasher on it in master). If it didn't build on MSVC, which is possible, the entire hash should've been ifdef'ed out for MSVC builds. To be honest, I don't understand what happened there.

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.