niahash.c

#include <stdint.h>
#include <string.h>

#define HI(n) ((uint64_t)(n)>>32)
#define LO(n) ((uint64_t)(n)&0xffffffff)

#if 1
 /* IOS 1.15.0 */
 static uint64_t magic_table[16] = {
   0x2dd7caaefcf073eb, 0xa9209937349cfe9c,
   0xb84bfc934b0e60ef, 0xff709c157b26e477,
   0x3936fd8735455112, 0xca141bf22338d331,
   0xdd40e749cb64fd02, 0x5e268f564b0deb26,
   0x658239596bdea9ec, 0x31cedf33ac38c624,
   0x12f56816481b0cfd, 0x94e9de155f40f095,
   0x5089c907844c6325, 0xdf887e97d73c50e3,
   0xae8870787ce3c11d, 0xa6767d18c58d2117,
 };
#define ROUND_MAGIC_HI 0xe3f0d44988bcdfab
#define ROUND_MAGIC_LO 0x081570afdd535ec3
#define FINAL_MAGIC0 0xce7c4801d683e824
#define FINAL_MAGIC1 0x6823775b1daad522
#endif
#if 0
/* 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_high, uint64_t mul_low, 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_high, uint64_t mul_low, 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_low),        m1 = HI(mul_low);
	uint64_t m2 = LO(mul_high),  m3 = HI(mul_high);
	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);
}