glusterfs

1
/*
2
  Copyright (c) 2008-2012 Red Hat, Inc. <http://www.redhat.com>
3
  This file is part of GlusterFS.
4

5
  This file is licensed to you under your choice of the GNU Lesser
6
  General Public License, version 3 or any later version (LGPLv3 or
7
  later), or the GNU General Public License, version 2 (GPLv2), in all
8
  cases as published by the Free Software Foundation.
9
*/
10

11
#include <stdint.h>
12
#include <stdlib.h>
13

14
#ifdef __FreeBSD__
15
#include <sys/endian.h>
16
#else
17
#include <endian.h>
18
#endif
19

20
#define get16bits(d) le16toh(*((const uint16_t *)(d)))
21

22
#define DM_DELTA 0x9E3779B9
23
#define DM_FULLROUNDS 10 /* 32 is overkill, 16 is strong crypto */
24
#define DM_PARTROUNDS 6  /* 6 gets complete mixing */
25

26
/*
27
  This is apparently the "fastest hash function for strings".
28
  Written by Paul Hsieh <http://www.azillionmonkeys.com/qed/hash.html>
29
*/
30

31
/* In any case make sure, you return 1 */
32

33
uint32_t
34
SuperFastHash(const char *data, int32_t len)
35
{
36
    uint32_t hash = len, tmp;
37
    int32_t rem;
38

39
    if (len <= 1 || data == NULL)
40
        return 1;
41

42
    rem = len & 3;
43
    len >>= 2;
44

45
    /* Main loop */
46
    for (; len > 0; len--) {
47
        hash += get16bits(data);
48
        tmp = (get16bits(data + 2) << 11) ^ hash;
49
        hash = (hash << 16) ^ tmp;
50
        data += 2 * sizeof(uint16_t);
51
        hash += hash >> 11;
52
    }
53

54
    /* Handle end cases */
55
    switch (rem) {
56
        case 3:
57
            hash += get16bits(data);
58
            hash ^= hash << 16;
59
            hash ^= data[sizeof(uint16_t)] << 18;
60
            hash += hash >> 11;
61
            break;
62
        case 2:
63
            hash += get16bits(data);
64
            hash ^= hash << 11;
65
            hash += hash >> 17;
66
            break;
67
        case 1:
68
            hash += *data;
69
            hash ^= hash << 10;
70
            hash += hash >> 1;
71
    }
72

73
    /* Force "avalanching" of final 127 bits */
74
    hash ^= hash << 3;
75
    hash += hash >> 5;
76
    hash ^= hash << 4;
77
    hash += hash >> 17;
78
    hash ^= hash << 25;
79
    hash += hash >> 6;
80

81
    return hash;
82
}
83

84
/* Davies-Meyer hashing function implementation
85
 */
86
static int
87
dm_round(int rounds, uint32_t *array, uint32_t *h0, uint32_t *h1)
88
{
89
    uint32_t sum = 0;
90
    int n = 0;
91
    uint32_t b0 = 0;
92
    uint32_t b1 = 0;
93

94
    b0 = *h0;
95
    b1 = *h1;
96

97
    n = rounds;
98

99
    do {
100
        sum += DM_DELTA;
101
        b0 += ((b1 << 4) + array[0]) ^ (b1 + sum) ^ ((b1 >> 5) + array[1]);
102
        b1 += ((b0 << 4) + array[2]) ^ (b0 + sum) ^ ((b0 >> 5) + array[3]);
103
    } while (--n);
104

105
    *h0 += b0;
106
    *h1 += b1;
107

108
    return 0;
109
}
110

111
uint32_t
112
__pad(int len)
113
{
114
    uint32_t pad = 0;
115

116
    pad = (uint32_t)len | ((uint32_t)len << 8);
117
    pad |= pad << 16;
118

119
    return pad;
120
}
121

122
uint32_t
123
gf_dm_hashfn(const char *msg, int len)
124
{
125
    uint32_t h0 = 0x9464a485;
126
    uint32_t h1 = 0x542e1a94;
127
    uint32_t array[4];
128
    uint32_t pad = 0;
129
    int i = 0;
130
    int j = 0;
131
    int full_quads = 0;
132
    int full_words = 0;
133
    int full_bytes = 0;
134
    uint32_t *intmsg = NULL;
135
    uint32_t word = 0;
136

137
    intmsg = (uint32_t *)msg;
138
    pad = __pad(len);
139

140
    full_bytes = len;
141
    full_words = len / 4;
142
    full_quads = len / 16;
143

144
    for (i = 0; i < full_quads; i++) {
145
        for (j = 0; j < 4; j++) {
146
            word = le32toh(*intmsg);
147
            array[j] = word;
148
            intmsg++;
149
            full_words--;
150
            full_bytes -= 4;
151
        }
152
        dm_round(DM_PARTROUNDS, &array[0], &h0, &h1);
153
    }
154

155
    for (j = 0; j < 4; j++) {
156
        if (full_words) {
157
            word = le32toh(*intmsg);
158
            array[j] = word;
159
            intmsg++;
160
            full_words--;
161
            full_bytes -= 4;
162
        } else {
163
            array[j] = pad;
164
            while (full_bytes) {
165
                array[j] <<= 8;
166
                array[j] |= msg[len - full_bytes];
167
                full_bytes--;
168
            }
169
        }
170
    }
171
    dm_round(DM_FULLROUNDS, &array[0], &h0, &h1);
172

173
    return h0 ^ h1;
174
}
175