Annotation of parser3/src/lib/md5/pa_xxhash.c, revision 1.1
1.1 ! moko 1: /** @file
! 2: Parser: XXH32 and XXH64, see pa_xxhash.h for the license.
! 3: */
! 4:
! 5: #include "pa_xxhash.h"
! 6:
! 7: volatile const char * IDENT_PA_XXHASH_C="$Id$" IDENT_PA_XXHASH_H;
! 8:
! 9: #define ROTL32(x, r) (((x) << (r)) | ((x) >> (32 - (r))))
! 10: #define ROTL64(x, r) (((x) << (r)) | ((x) >> (64 - (r))))
! 11:
! 12: // little endian read, not depending on the byte order and alignment
! 13: static uint32_t read32(const uint8_t* p) {
! 14: return (uint32_t)p[0] | ((uint32_t)p[1] << 8) | ((uint32_t)p[2] << 16) | ((uint32_t)p[3] << 24);
! 15: }
! 16:
! 17: static uint64_t read64(const uint8_t* p) {
! 18: return (uint64_t)read32(p) | ((uint64_t)read32(p + 4) << 32);
! 19: }
! 20:
! 21: #define PRIME32_1 0x9E3779B1U
! 22: #define PRIME32_2 0x85EBCA77U
! 23: #define PRIME32_3 0xC2B2AE3DU
! 24: #define PRIME32_4 0x27D4EB2FU
! 25: #define PRIME32_5 0x165667B1U
! 26:
! 27: static uint32_t round32(uint32_t acc, uint32_t input) {
! 28: acc += input * PRIME32_2;
! 29: acc = ROTL32(acc, 13);
! 30: return acc * PRIME32_1;
! 31: }
! 32:
! 33: uint32_t pa_xxh32(const void* input, size_t length, uint32_t seed) {
! 34: const uint8_t* p = (const uint8_t*)input;
! 35: const uint8_t* end = p + length;
! 36: uint32_t h;
! 37:
! 38: if (length >= 16) {
! 39: const uint8_t* limit = end - 16;
! 40: uint32_t v1 = seed + PRIME32_1 + PRIME32_2;
! 41: uint32_t v2 = seed + PRIME32_2;
! 42: uint32_t v3 = seed;
! 43: uint32_t v4 = seed - PRIME32_1;
! 44:
! 45: do {
! 46: v1 = round32(v1, read32(p)); p += 4;
! 47: v2 = round32(v2, read32(p)); p += 4;
! 48: v3 = round32(v3, read32(p)); p += 4;
! 49: v4 = round32(v4, read32(p)); p += 4;
! 50: } while (p <= limit);
! 51:
! 52: h = ROTL32(v1, 1) + ROTL32(v2, 7) + ROTL32(v3, 12) + ROTL32(v4, 18);
! 53: } else
! 54: h = seed + PRIME32_5;
! 55:
! 56: h += (uint32_t)length;
! 57:
! 58: while (p + 4 <= end) {
! 59: h += read32(p) * PRIME32_3;
! 60: h = ROTL32(h, 17) * PRIME32_4;
! 61: p += 4;
! 62: }
! 63: while (p < end) {
! 64: h += (*p++) * PRIME32_5;
! 65: h = ROTL32(h, 11) * PRIME32_1;
! 66: }
! 67:
! 68: h ^= h >> 15;
! 69: h *= PRIME32_2;
! 70: h ^= h >> 13;
! 71: h *= PRIME32_3;
! 72: h ^= h >> 16;
! 73: return h;
! 74: }
! 75:
! 76: #define PRIME64_1 ((uint64_t)0x9E3779B185EBCA87ULL)
! 77: #define PRIME64_2 ((uint64_t)0xC2B2AE3D27D4EB4FULL)
! 78: #define PRIME64_3 ((uint64_t)0x165667B19E3779F9ULL)
! 79: #define PRIME64_4 ((uint64_t)0x85EBCA77C2B2AE63ULL)
! 80: #define PRIME64_5 ((uint64_t)0x27D4EB2F165667C5ULL)
! 81:
! 82: static uint64_t round64(uint64_t acc, uint64_t input) {
! 83: acc += input * PRIME64_2;
! 84: acc = ROTL64(acc, 31);
! 85: return acc * PRIME64_1;
! 86: }
! 87:
! 88: static uint64_t merge_round64(uint64_t acc, uint64_t val) {
! 89: acc ^= round64(0, val);
! 90: return acc * PRIME64_1 + PRIME64_4;
! 91: }
! 92:
! 93: uint64_t pa_xxh64(const void* input, size_t length, uint64_t seed) {
! 94: const uint8_t* p = (const uint8_t*)input;
! 95: const uint8_t* end = p + length;
! 96: uint64_t h;
! 97:
! 98: if (length >= 32) {
! 99: const uint8_t* limit = end - 32;
! 100: uint64_t v1 = seed + PRIME64_1 + PRIME64_2;
! 101: uint64_t v2 = seed + PRIME64_2;
! 102: uint64_t v3 = seed;
! 103: uint64_t v4 = seed - PRIME64_1;
! 104:
! 105: do {
! 106: v1 = round64(v1, read64(p)); p += 8;
! 107: v2 = round64(v2, read64(p)); p += 8;
! 108: v3 = round64(v3, read64(p)); p += 8;
! 109: v4 = round64(v4, read64(p)); p += 8;
! 110: } while (p <= limit);
! 111:
! 112: h = ROTL64(v1, 1) + ROTL64(v2, 7) + ROTL64(v3, 12) + ROTL64(v4, 18);
! 113: h = merge_round64(h, v1);
! 114: h = merge_round64(h, v2);
! 115: h = merge_round64(h, v3);
! 116: h = merge_round64(h, v4);
! 117: } else
! 118: h = seed + PRIME64_5;
! 119:
! 120: h += (uint64_t)length;
! 121:
! 122: while (p + 8 <= end) {
! 123: h ^= round64(0, read64(p));
! 124: h = ROTL64(h, 27) * PRIME64_1 + PRIME64_4;
! 125: p += 8;
! 126: }
! 127: if (p + 4 <= end) {
! 128: h ^= (uint64_t)read32(p) * PRIME64_1;
! 129: h = ROTL64(h, 23) * PRIME64_2 + PRIME64_3;
! 130: p += 4;
! 131: }
! 132: while (p < end) {
! 133: h ^= (*p++) * PRIME64_5;
! 134: h = ROTL64(h, 11) * PRIME64_1;
! 135: }
! 136:
! 137: h ^= h >> 33;
! 138: h *= PRIME64_2;
! 139: h ^= h >> 29;
! 140: h *= PRIME64_3;
! 141: h ^= h >> 32;
! 142: return h;
! 143: }
E-mail: