summaryrefslogtreecommitdiff
path: root/src/common/hash.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/common/hash.cpp')
-rw-r--r--src/common/hash.cpp524
1 files changed, 0 insertions, 524 deletions
diff --git a/src/common/hash.cpp b/src/common/hash.cpp
deleted file mode 100644
index e2364d700..000000000
--- a/src/common/hash.cpp
+++ /dev/null
@@ -1,524 +0,0 @@
1// Copyright 2013 Dolphin Emulator Project / 2014 Citra Emulator Project
2// Licensed under GPLv2 or any later version
3// Refer to the license.txt file included.
4
5#include <algorithm>
6
7#include "common/common_funcs.h" // For rotl
8#include "common/hash.h"
9#include "common/platform.h"
10
11#if _M_SSE >= 0x402
12#include "common/cpu_detect.h"
13#include <nmmintrin.h>
14#endif
15
16static u64 (*ptrHashFunction)(const u8 *src, int len, u32 samples) = &GetMurmurHash3;
17
18// uint32_t
19// WARNING - may read one more byte!
20// Implementation from Wikipedia.
21u32 HashFletcher(const u8* data_u8, size_t length)
22{
23 const u16* data = (const u16*)data_u8; /* Pointer to the data to be summed */
24 size_t len = (length + 1) / 2; /* Length in 16-bit words */
25 u32 sum1 = 0xffff, sum2 = 0xffff;
26
27 while (len)
28 {
29 size_t tlen = len > 360 ? 360 : len;
30 len -= tlen;
31
32 do {
33 sum1 += *data++;
34 sum2 += sum1;
35 }
36 while (--tlen);
37
38 sum1 = (sum1 & 0xffff) + (sum1 >> 16);
39 sum2 = (sum2 & 0xffff) + (sum2 >> 16);
40 }
41
42 // Second reduction step to reduce sums to 16 bits
43 sum1 = (sum1 & 0xffff) + (sum1 >> 16);
44 sum2 = (sum2 & 0xffff) + (sum2 >> 16);
45 return(sum2 << 16 | sum1);
46}
47
48
49// Implementation from Wikipedia
50// Slightly slower than Fletcher above, but slightly more reliable.
51#define MOD_ADLER 65521
52// data: Pointer to the data to be summed; len is in bytes
53u32 HashAdler32(const u8* data, size_t len)
54{
55 u32 a = 1, b = 0;
56
57 while (len)
58 {
59 size_t tlen = len > 5550 ? 5550 : len;
60 len -= tlen;
61
62 do
63 {
64 a += *data++;
65 b += a;
66 }
67 while (--tlen);
68
69 a = (a & 0xffff) + (a >> 16) * (65536 - MOD_ADLER);
70 b = (b & 0xffff) + (b >> 16) * (65536 - MOD_ADLER);
71 }
72
73 // It can be shown that a <= 0x1013a here, so a single subtract will do.
74 if (a >= MOD_ADLER)
75 {
76 a -= MOD_ADLER;
77 }
78
79 // It can be shown that b can reach 0xfff87 here.
80 b = (b & 0xffff) + (b >> 16) * (65536 - MOD_ADLER);
81
82 if (b >= MOD_ADLER)
83 {
84 b -= MOD_ADLER;
85 }
86
87 return((b << 16) | a);
88}
89
90// Stupid hash - but can't go back now :)
91// Don't use for new things. At least it's reasonably fast.
92u32 HashEctor(const u8* ptr, int length)
93{
94 u32 crc = 0;
95
96 for (int i = 0; i < length; i++)
97 {
98 crc ^= ptr[i];
99 crc = (crc << 3) | (crc >> 29);
100 }
101
102 return(crc);
103}
104
105
106#if EMU_ARCH_BITS == 64
107
108//-----------------------------------------------------------------------------
109// Block read - if your platform needs to do endian-swapping or can only
110// handle aligned reads, do the conversion here
111
112inline u64 getblock(const u64 * p, int i)
113{
114 return p[i];
115}
116
117//----------
118// Block mix - combine the key bits with the hash bits and scramble everything
119
120inline void bmix64(u64 & h1, u64 & h2, u64 & k1, u64 & k2, u64 & c1, u64 & c2)
121{
122 k1 *= c1;
123 k1 = _rotl64(k1,23);
124 k1 *= c2;
125 h1 ^= k1;
126 h1 += h2;
127
128 h2 = _rotl64(h2,41);
129
130 k2 *= c2;
131 k2 = _rotl64(k2,23);
132 k2 *= c1;
133 h2 ^= k2;
134 h2 += h1;
135
136 h1 = h1*3+0x52dce729;
137 h2 = h2*3+0x38495ab5;
138
139 c1 = c1*5+0x7b7d159c;
140 c2 = c2*5+0x6bce6396;
141}
142
143//----------
144// Finalization mix - avalanches all bits to within 0.05% bias
145
146inline u64 fmix64(u64 k)
147{
148 k ^= k >> 33;
149 k *= 0xff51afd7ed558ccd;
150 k ^= k >> 33;
151 k *= 0xc4ceb9fe1a85ec53;
152 k ^= k >> 33;
153
154 return k;
155}
156
157u64 GetMurmurHash3(const u8 *src, int len, u32 samples)
158{
159 const u8 * data = (const u8*)src;
160 const int nblocks = len / 16;
161 u32 Step = (len / 8);
162 if(samples == 0) samples = std::max(Step, 1u);
163 Step = Step / samples;
164 if(Step < 1) Step = 1;
165
166 u64 h1 = 0x9368e53c2f6af274;
167 u64 h2 = 0x586dcd208f7cd3fd;
168
169 u64 c1 = 0x87c37b91114253d5;
170 u64 c2 = 0x4cf5ad432745937f;
171
172
173 //----------
174 // body
175
176 const u64 * blocks = (const u64 *)(data);
177
178 for(int i = 0; i < nblocks; i+=Step)
179 {
180 u64 k1 = getblock(blocks,i*2+0);
181 u64 k2 = getblock(blocks,i*2+1);
182
183 bmix64(h1,h2,k1,k2,c1,c2);
184 }
185
186 //----------
187 // tail
188
189 const u8 * tail = (const u8*)(data + nblocks*16);
190
191 u64 k1 = 0;
192 u64 k2 = 0;
193
194 switch(len & 15)
195 {
196 case 15: k2 ^= u64(tail[14]) << 48;
197 case 14: k2 ^= u64(tail[13]) << 40;
198 case 13: k2 ^= u64(tail[12]) << 32;
199 case 12: k2 ^= u64(tail[11]) << 24;
200 case 11: k2 ^= u64(tail[10]) << 16;
201 case 10: k2 ^= u64(tail[ 9]) << 8;
202 case 9: k2 ^= u64(tail[ 8]) << 0;
203
204 case 8: k1 ^= u64(tail[ 7]) << 56;
205 case 7: k1 ^= u64(tail[ 6]) << 48;
206 case 6: k1 ^= u64(tail[ 5]) << 40;
207 case 5: k1 ^= u64(tail[ 4]) << 32;
208 case 4: k1 ^= u64(tail[ 3]) << 24;
209 case 3: k1 ^= u64(tail[ 2]) << 16;
210 case 2: k1 ^= u64(tail[ 1]) << 8;
211 case 1: k1 ^= u64(tail[ 0]) << 0;
212 bmix64(h1,h2,k1,k2,c1,c2);
213 };
214
215 //----------
216 // finalization
217
218 h2 ^= len;
219
220 h1 += h2;
221 h2 += h1;
222
223 h1 = fmix64(h1);
224 h2 = fmix64(h2);
225
226 h1 += h2;
227
228 return h1;
229}
230
231
232// CRC32 hash using the SSE4.2 instruction
233u64 GetCRC32(const u8 *src, int len, u32 samples)
234{
235#if _M_SSE >= 0x402
236 u64 h = len;
237 u32 Step = (len / 8);
238 const u64 *data = (const u64 *)src;
239 const u64 *end = data + Step;
240 if(samples == 0) samples = std::max(Step, 1u);
241 Step = Step / samples;
242 if(Step < 1) Step = 1;
243 while(data < end)
244 {
245 h = _mm_crc32_u64(h, data[0]);
246 data += Step;
247 }
248
249 const u8 *data2 = (const u8*)end;
250 return _mm_crc32_u64(h, u64(data2[0]));
251#else
252 return 0;
253#endif
254}
255
256
257/*
258 * NOTE: This hash function is used for custom texture loading/dumping, so
259 * it should not be changed, which would require all custom textures to be
260 * recalculated for their new hash values. If the hashing function is
261 * changed, make sure this one is still used when the legacy parameter is
262 * true.
263 */
264u64 GetHashHiresTexture(const u8 *src, int len, u32 samples)
265{
266 const u64 m = 0xc6a4a7935bd1e995;
267 u64 h = len * m;
268 const int r = 47;
269 u32 Step = (len / 8);
270 const u64 *data = (const u64 *)src;
271 const u64 *end = data + Step;
272 if(samples == 0) samples = std::max(Step, 1u);
273 Step = Step / samples;
274 if(Step < 1) Step = 1;
275 while(data < end)
276 {
277 u64 k = data[0];
278 data+=Step;
279 k *= m;
280 k ^= k >> r;
281 k *= m;
282 h ^= k;
283 h *= m;
284 }
285
286 const u8 * data2 = (const u8*)end;
287
288 switch(len & 7)
289 {
290 case 7: h ^= u64(data2[6]) << 48;
291 case 6: h ^= u64(data2[5]) << 40;
292 case 5: h ^= u64(data2[4]) << 32;
293 case 4: h ^= u64(data2[3]) << 24;
294 case 3: h ^= u64(data2[2]) << 16;
295 case 2: h ^= u64(data2[1]) << 8;
296 case 1: h ^= u64(data2[0]);
297 h *= m;
298 };
299
300 h ^= h >> r;
301 h *= m;
302 h ^= h >> r;
303
304 return h;
305}
306#else
307// CRC32 hash using the SSE4.2 instruction
308u64 GetCRC32(const u8 *src, int len, u32 samples)
309{
310#if _M_SSE >= 0x402
311 u32 h = len;
312 u32 Step = (len/4);
313 const u32 *data = (const u32 *)src;
314 const u32 *end = data + Step;
315 if(samples == 0) samples = std::max(Step, 1u);
316 Step = Step / samples;
317 if(Step < 1) Step = 1;
318 while(data < end)
319 {
320 h = _mm_crc32_u32(h, data[0]);
321 data += Step;
322 }
323
324 const u8 *data2 = (const u8*)end;
325 return (u64)_mm_crc32_u32(h, u32(data2[0]));
326#else
327 return 0;
328#endif
329}
330
331//-----------------------------------------------------------------------------
332// Block read - if your platform needs to do endian-swapping or can only
333// handle aligned reads, do the conversion here
334
335inline u32 getblock(const u32 * p, int i)
336{
337 return p[i];
338}
339
340//----------
341// Finalization mix - force all bits of a hash block to avalanche
342
343// avalanches all bits to within 0.25% bias
344
345inline u32 fmix32(u32 h)
346{
347 h ^= h >> 16;
348 h *= 0x85ebca6b;
349 h ^= h >> 13;
350 h *= 0xc2b2ae35;
351 h ^= h >> 16;
352
353 return h;
354}
355
356inline void bmix32(u32 & h1, u32 & h2, u32 & k1, u32 & k2, u32 & c1, u32 & c2)
357{
358 k1 *= c1;
359 k1 = _rotl(k1,11);
360 k1 *= c2;
361 h1 ^= k1;
362 h1 += h2;
363
364 h2 = _rotl(h2,17);
365
366 k2 *= c2;
367 k2 = _rotl(k2,11);
368 k2 *= c1;
369 h2 ^= k2;
370 h2 += h1;
371
372 h1 = h1*3+0x52dce729;
373 h2 = h2*3+0x38495ab5;
374
375 c1 = c1*5+0x7b7d159c;
376 c2 = c2*5+0x6bce6396;
377}
378
379//----------
380
381u64 GetMurmurHash3(const u8* src, int len, u32 samples)
382{
383 const u8 * data = (const u8*)src;
384 u32 out[2];
385 const int nblocks = len / 8;
386 u32 Step = (len / 4);
387 if(samples == 0) samples = std::max(Step, 1u);
388 Step = Step / samples;
389 if(Step < 1) Step = 1;
390
391 u32 h1 = 0x8de1c3ac;
392 u32 h2 = 0xbab98226;
393
394 u32 c1 = 0x95543787;
395 u32 c2 = 0x2ad7eb25;
396
397 //----------
398 // body
399
400 const u32 * blocks = (const u32 *)(data + nblocks*8);
401
402 for(int i = -nblocks; i < 0; i+=Step)
403 {
404 u32 k1 = getblock(blocks,i*2+0);
405 u32 k2 = getblock(blocks,i*2+1);
406
407 bmix32(h1,h2,k1,k2,c1,c2);
408 }
409
410 //----------
411 // tail
412
413 const u8 * tail = (const u8*)(data + nblocks*8);
414
415 u32 k1 = 0;
416 u32 k2 = 0;
417
418 switch(len & 7)
419 {
420 case 7: k2 ^= tail[6] << 16;
421 case 6: k2 ^= tail[5] << 8;
422 case 5: k2 ^= tail[4] << 0;
423 case 4: k1 ^= tail[3] << 24;
424 case 3: k1 ^= tail[2] << 16;
425 case 2: k1 ^= tail[1] << 8;
426 case 1: k1 ^= tail[0] << 0;
427 bmix32(h1,h2,k1,k2,c1,c2);
428 };
429
430 //----------
431 // finalization
432
433 h2 ^= len;
434
435 h1 += h2;
436 h2 += h1;
437
438 h1 = fmix32(h1);
439 h2 = fmix32(h2);
440
441 h1 += h2;
442 h2 += h1;
443
444 out[0] = h1;
445 out[1] = h2;
446
447 return *((u64 *)&out);
448}
449
450/*
451 * FIXME: The old 32-bit version of this hash made different hashes than the
452 * 64-bit version. Until someone can make a new version of the 32-bit one that
453 * makes identical hashes, this is just a c/p of the 64-bit one.
454 */
455u64 GetHashHiresTexture(const u8 *src, int len, u32 samples)
456{
457 const u64 m = 0xc6a4a7935bd1e995ULL;
458 u64 h = len * m;
459 const int r = 47;
460 u32 Step = (len / 8);
461 const u64 *data = (const u64 *)src;
462 const u64 *end = data + Step;
463 if(samples == 0) samples = std::max(Step, 1u);
464 Step = Step / samples;
465 if(Step < 1) Step = 1;
466 while(data < end)
467 {
468 u64 k = data[0];
469 data+=Step;
470 k *= m;
471 k ^= k >> r;
472 k *= m;
473 h ^= k;
474 h *= m;
475 }
476
477 const u8 * data2 = (const u8*)end;
478
479 switch(len & 7)
480 {
481 case 7: h ^= u64(data2[6]) << 48;
482 case 6: h ^= u64(data2[5]) << 40;
483 case 5: h ^= u64(data2[4]) << 32;
484 case 4: h ^= u64(data2[3]) << 24;
485 case 3: h ^= u64(data2[2]) << 16;
486 case 2: h ^= u64(data2[1]) << 8;
487 case 1: h ^= u64(data2[0]);
488 h *= m;
489 };
490
491 h ^= h >> r;
492 h *= m;
493 h ^= h >> r;
494
495 return h;
496}
497#endif
498
499u64 GetHash64(const u8 *src, int len, u32 samples)
500{
501 return ptrHashFunction(src, len, samples);
502}
503
504// sets the hash function used for the texture cache
505void SetHash64Function(bool useHiresTextures)
506{
507 if (useHiresTextures)
508 {
509 ptrHashFunction = &GetHashHiresTexture;
510 }
511#if _M_SSE >= 0x402
512 else if (cpu_info.bSSE4_2 && !useHiresTextures) // sse crc32 version
513 {
514 ptrHashFunction = &GetCRC32;
515 }
516#endif
517 else
518 {
519 ptrHashFunction = &GetMurmurHash3;
520 }
521}
522
523
524
HIC SVNT DRACONES