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: