Created
November 6, 2016 23:59
-
-
Save popcornmix/f94e6ab0566a60b7fd1e8acccc0647f8 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdint.h> | |
#include <string.h> | |
#define HI(n) ((uint64_t)(n)>>32) | |
#define LO(n) ((uint64_t)(n)&0xffffffff) | |
#if 1 | |
/* IOS 1.13.3 */ | |
static uint64_t magic_table[16] = { | |
0x95C05F4D1512959E, 0xE4F3C46EEF0DCF07, | |
0x6238DC228F980AD2, 0x53F3E3BC49607092, | |
0x4E7BE7069078D625, 0x1016D709D1AD25FC, | |
0x044E89B8AC76E045, 0xE0B684DDA364BFA1, | |
0x90C533B835E89E5F, 0x3DAF462A74FA874F, | |
0xFEA54965DD3EF5A0, 0x287A5D7CCB31B970, | |
0xAE681046800752F8, 0x121C2D6EAF66EC6E, | |
0xEE8F8CA7E090FB20, 0xCE1AE25F48FE0A52, | |
}; | |
#define ROUND_MAGIC_HI 0x78F32468CD48D6DE | |
#define ROUND_MAGIC_LO 0x14C983660183C0AE | |
#define FINAL_MAGIC0 0xBDB31B10864F3F87 | |
#define FINAL_MAGIC1 0x5B7E9E828A9B8ABD | |
#endif | |
#if 0 | |
/* Android 0.43.4 */ | |
static uint64_t magic_table[16] = { | |
0x48CD0D725609F95F, 0x25D4A39B5ACB4330, | |
0x1C0C27978A3649A3, 0x5C7068B9C51C5E4B, | |
0x69A054CBE1369106, 0x4C318ED6A12B9645, | |
0xC751EECD2715C836, 0xAAEDCC7A92014B7A, | |
0xE91DB51D36F47460, 0x78EA4A974D9157B8, | |
0xE4E65C1A929E8AB1, 0x6BC61BB9C5988769, | |
0x78C7794B899D8819, 0xB338727B9C7600F7, | |
0x26BA60FCB9EDC151, 0xE7D74B3CD6293E6B, | |
}; | |
#define ROUND_MAGIC_HI 0x1A32C90D816A2F1F | |
#define ROUND_MAGIC_LO 0x76327D13FD037D57 | |
#define FINAL_MAGIC0 0x106245053E723AD8 | |
#define FINAL_MAGIC1 0x1CDA65FFA125C8F6 | |
#endif | |
#if 0 | |
/* Android 0.41.4 */ | |
static uint64_t magic_table[16] = { | |
0x475BD60F17CE7238, 0xC11B0E0066794E31, | |
0x75F5BD04F566D70C, 0x09F4F46E7CEC785C, | |
0x6A52B40820F5EBFF, 0x27F300DB7195A066, | |
0xBDFDE4DAC75939BF, 0xF7F239CFD77A36AB, | |
0x7013DEFA151CD579, 0x8864183CFD4C24F9, | |
0x21C426C79EA1445A, 0xB188FEAE415747BA, | |
0x127421C8D0BD9352, 0x8C7E6FC0526AD558, | |
0x7E33F449C404A71A, 0xE955B7D15DE757DC, | |
}; | |
#define ROUND_MAGIC_HI 0x232B242A99C10878 | |
#define ROUND_MAGIC_LO 0x667EFDF872801CD8 | |
#define FINAL_MAGIC0 0xF6AC14F2D12AB0C1 | |
#define FINAL_MAGIC1 0x101FF0340EC93F87 | |
#endif | |
void mul128(uint64_t *hi, uint64_t *lo, uint64_t a, uint64_t b) | |
{ | |
uint64_t a_lo = (uint64_t)(uint32_t)a; | |
uint64_t a_hi = a >> 32; | |
uint64_t b_lo = (uint64_t)(uint32_t)b; | |
uint64_t b_hi = b >> 32; | |
uint64_t p0 = a_lo * b_lo; | |
uint64_t p1 = a_lo * b_hi; | |
uint64_t p2 = a_hi * b_lo; | |
uint64_t p3 = a_hi * b_hi; | |
uint32_t cy = (uint32_t)(((p0 >> 32) + (uint32_t)p1 + (uint32_t)p2) >> 32); | |
*lo = p0 + (p1 << 32) + (p2 << 32); | |
*hi = p3 + (p1 >> 32) + (p2 >> 32) + cy; | |
} | |
void add128(uint64_t *hash_high, uint64_t *hash_low, uint64_t add_high, uint64_t add_low) | |
{ | |
*hash_high += add_high; | |
*hash_low += add_low; | |
// check for overflow of low 64 bits, add carry to high | |
if (*hash_low < add_low) | |
(*hash_high)++; | |
} | |
uint64_t compute_hash(const uint8_t *in, uint32_t len); | |
void hash_muladd(uint64_t *hash_high, uint64_t *hash_low, uint64_t mul_hi, uint64_t mul_lo, uint64_t add_high, uint64_t add_low); | |
void hash_chunk(uint64_t *hash_high, uint64_t *hash_low, const uint8_t *chunk, int64_t size); | |
static uint64_t read_int64(const uint8_t *p); | |
uint64_t read_int64(const uint8_t *p) | |
{ | |
// endian-safe read 64-bit integer | |
uint64_t n = 0; | |
for (int i = 7; i >= 0; i--) { | |
n = (n << 8) | p[i]; | |
} | |
return n; | |
} | |
uint64_t compute_hash(const uint8_t *in, uint32_t len) | |
{ | |
uint32_t num_chunks = len / 128; | |
// copy tail, pad with zeroes | |
uint8_t tail[128] = {0}; | |
int tail_size = len % 128; | |
memcpy(tail, in + len - tail_size, tail_size); | |
uint64_t hash_high, hash_low; | |
if (num_chunks) { | |
// Hash the first 128 bytes | |
hash_chunk(&hash_high, &hash_low, in, 128); | |
} else { | |
// Hash the tail | |
hash_chunk(&hash_high, &hash_low, tail, tail_size); | |
} | |
add128(&hash_high, &hash_low, ROUND_MAGIC_HI, ROUND_MAGIC_LO); | |
if (num_chunks) { | |
while (--num_chunks) { | |
in += 128; | |
uint64_t chunk_high, chunk_low; | |
hash_chunk(&chunk_high, &chunk_low, in, 128); | |
hash_muladd(&hash_high, &hash_low, ROUND_MAGIC_HI, ROUND_MAGIC_LO, chunk_high, chunk_low); | |
} | |
if (tail_size) { | |
uint64_t chunk_high, chunk_low; | |
hash_chunk(&chunk_high, &chunk_low, tail, tail_size); | |
hash_muladd(&hash_high, &hash_low, ROUND_MAGIC_HI, ROUND_MAGIC_LO, chunk_high, chunk_low); | |
} | |
} | |
// Finalize the hash | |
add128(&hash_high, &hash_low, tail_size * 8, 0); | |
if (hash_high > 0x7fffffffffffffff || (hash_high == 0x7fffffffffffffff && hash_low >= 0xffffffffffffffff)) { | |
add128(&hash_high, &hash_low, 0, 1); | |
} | |
hash_high &= ~(1ULL<<63); | |
uint64_t X = hash_high + HI(hash_low); | |
X = HI(X + HI(X) + 1) + hash_high; | |
uint64_t Y = (X << 32) + hash_low; | |
uint64_t A = X + FINAL_MAGIC0; | |
if (A < X) { | |
A += 0x101; | |
} | |
uint64_t B = Y + FINAL_MAGIC1; | |
if (B < Y) { | |
B += 0x101; | |
} | |
uint64_t H_high, H_low; | |
mul128(&H_high, &H_low, A, B); | |
uint64_t temp_high, temp_low; | |
mul128(&temp_high, &temp_low, 0x101, H_high); | |
add128(&temp_high, &temp_low, 0, H_low); | |
H_high = temp_high; | |
H_low = temp_low; | |
mul128(&temp_high, &temp_low, 0x101, H_high); | |
add128(&temp_high, &temp_low, 0, H_low); | |
H_high = temp_high; | |
H_low = temp_low; | |
if (H_high) { | |
add128(&H_high, &H_low, 0, 0x101); | |
} | |
if (H_low > 0xFFFFFFFFFFFFFEFE) { | |
add128(&H_high, &H_low, 0, 0x101); | |
} | |
return H_low; | |
} | |
void hash_chunk(uint64_t *hash_high, uint64_t *hash_low, const uint8_t *chunk, int64_t size) | |
{ | |
*hash_high = 0; | |
*hash_low = 0; | |
for (int i = 0; i < 8; i++) { | |
int offset = i * 16; | |
if (offset >= size) { | |
break; | |
} | |
uint64_t a = read_int64(chunk + offset); | |
uint64_t b = read_int64(chunk + offset + 8); | |
uint64_t add_high, add_low; | |
mul128(&add_high, &add_low, a + magic_table[i * 2], b + magic_table[i * 2 + 1]); | |
add128(hash_high, hash_low, add_high, add_low); | |
} | |
*hash_high &= ~(3ULL<<62); | |
} | |
void hash_muladd(uint64_t *hash_high, uint64_t *hash_low, uint64_t mul_hi, uint64_t mul_lo, uint64_t add_high, uint64_t add_low) | |
{ | |
uint64_t a0 = LO(add_low), a1 = HI(add_low), a23 = add_high; | |
uint64_t m0 = LO(mul_lo), m1 = HI(mul_lo); | |
uint64_t m2 = LO(mul_hi), m3 = HI(mul_hi); | |
uint64_t h0 = LO(*hash_low), h1 = HI(*hash_low); | |
uint64_t h2 = LO(*hash_high), h3 = HI(*hash_high); | |
/* Column sums, before carry */ | |
uint64_t c0 = (h0 * m0); | |
uint64_t c1 = (h0 * m1) + (h1 * m0); | |
uint64_t c2 = (h0 * m2) + (h1 * m1) + (h2 * m0); | |
uint64_t c3 = (h0 * m3) + (h1 * m2) + (h2 * m1) + (h3 * m0); | |
uint64_t c4 = (h1 * m3) + (h2 * m2) + (h3 * m1); | |
uint64_t c5 = (h2 * m3) + (h3 * m2); | |
uint64_t c6 = (h3 * m3); | |
/* Combine, add, and carry (bugs included) */ | |
uint64_t r2 = c2 + (c6 << 1) + a23; | |
uint64_t r3 = c3 + HI(r2); | |
uint64_t r0 = c0 + (c4 << 1) + a0 + (r3 >> 31); | |
uint64_t r1 = c1 + (c5 << 1) + a1 + HI(r0); | |
/* Return */ | |
*hash_high = ((r3 << 33 >> 1) | LO(r2)) + HI(r1); | |
*hash_low = (r1 << 32) | LO(r0); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment