00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031 #include <shogun/lib/common.h>
00032 #include <shogun/lib/Hash.h>
00033 #include <ctype.h>
00034
00035 using namespace shogun;
00036
00037 uint32_t CHash::crc32(uint8_t *data, int32_t len)
00038 {
00039 uint32_t result;
00040 int32_t i,j;
00041 uint8_t octet;
00042
00043 result = 0-1;
00044 for (i=0; i<len; i++)
00045 {
00046 octet = *(data++);
00047 for (j=0; j<8; j++)
00048 {
00049 if ((octet >> 7) ^ (result >> 31))
00050 {
00051 result = (result << 1) ^ 0x04c11db7;
00052 }
00053 else
00054 {
00055 result = (result << 1);
00056 }
00057 octet <<= 1;
00058 }
00059 }
00060
00061 return ~result;
00062 }
00063
00064 void CHash::MD5(unsigned char *x, unsigned l, unsigned char *buf)
00065 {
00066 struct MD5Context ctx;
00067
00068 MD5Init(&ctx);
00069 MD5Update(&ctx, x, l);
00070 MD5Final(buf, &ctx);
00071 }
00072
00073 #ifndef HIGHFIRST
00074 #define byteReverse(buf, len)
00075 #else
00076 void byteReverse(unsigned char *buf, unsigned uint32_t longs);
00077
00078 #ifndef ASM_MD5
00079
00080
00081
00082 void byteReverse(unsigned char *buf, unsigned uint32_t longs)
00083 {
00084 uint32_t t;
00085 do {
00086 t = (uint32_t) ((unsigned) buf[3] << 8 | buf[2]) << 16 |
00087 ((unsigned) buf[1] << 8 | buf[0]);
00088 *(uint32_t *) buf = t;
00089 buf += 4;
00090 } while (--longs);
00091 }
00092 #endif
00093 #endif
00094
00095 void CHash::MD5Init(struct MD5Context *ctx)
00096 {
00097 ctx->buf[0] = 0x67452301;
00098 ctx->buf[1] = 0xefcdab89;
00099 ctx->buf[2] = 0x98badcfe;
00100 ctx->buf[3] = 0x10325476;
00101
00102 ctx->bits[0] = 0;
00103 ctx->bits[1] = 0;
00104 }
00105
00106 void CHash::MD5Update(struct MD5Context *ctx, unsigned char const *buf,
00107 unsigned len)
00108 {
00109 uint32_t t;
00110
00111
00112
00113 t = ctx->bits[0];
00114 if ((ctx->bits[0] = t + ((uint32_t) len << 3)) < t)
00115 ctx->bits[1]++;
00116 ctx->bits[1] += len >> 29;
00117
00118 t = (t >> 3) & 0x3f;
00119
00120
00121
00122 if (t) {
00123 unsigned char *p = (unsigned char *) ctx->in + t;
00124
00125 t = 64 - t;
00126 if (len < t) {
00127 memcpy(p, buf, len);
00128 return;
00129 }
00130 memcpy(p, buf, t);
00131 byteReverse(ctx->in, 16);
00132 MD5Transform(ctx->buf, (uint32_t *) ctx->in);
00133 buf += t;
00134 len -= t;
00135 }
00136
00137
00138 while (len >= 64) {
00139 memcpy(ctx->in, buf, 64);
00140 byteReverse(ctx->in, 16);
00141 MD5Transform(ctx->buf, (uint32_t *) ctx->in);
00142 buf += 64;
00143 len -= 64;
00144 }
00145
00146
00147
00148 memcpy(ctx->in, buf, len);
00149 }
00150
00151 void CHash::MD5Final(unsigned char digest[16], struct MD5Context *ctx)
00152 {
00153 unsigned count;
00154 unsigned char *p;
00155
00156
00157 count = (ctx->bits[0] >> 3) & 0x3F;
00158
00159
00160
00161 p = ctx->in + count;
00162 *p++ = 0x80;
00163
00164
00165 count = 64 - 1 - count;
00166
00167
00168 if (count < 8) {
00169
00170 memset(p, 0, count);
00171 byteReverse(ctx->in, 16);
00172 MD5Transform(ctx->buf, (uint32_t *) ctx->in);
00173
00174
00175 memset(ctx->in, 0, 56);
00176 } else {
00177
00178 memset(p, 0, count - 8);
00179 }
00180 byteReverse(ctx->in, 14);
00181
00182
00183 ctx->uin[14] = ctx->bits[0];
00184 ctx->uin[15] = ctx->bits[1];
00185
00186 MD5Transform(ctx->buf, (uint32_t *) ctx->in);
00187 byteReverse((unsigned char *) ctx->buf, 4);
00188 memcpy(digest, ctx->buf, 16);
00189 memset(ctx, 0, sizeof(*ctx));
00190 }
00191
00192 #ifndef ASM_MD5
00193
00194
00195
00196
00197 #define F1(x, y, z) (z ^ (x & (y ^ z)))
00198 #define F2(x, y, z) F1(z, x, y)
00199 #define F3(x, y, z) (x ^ y ^ z)
00200 #define F4(x, y, z) (y ^ (x | ~z))
00201
00202
00203 #ifdef __PUREC__
00204 #define MD5STEP(f, w, x, y, z, data, s) \
00205 ( w += f + data, w = w<<s | w>>(32-s), w += x )
00206 #else
00207 #define MD5STEP(f, w, x, y, z, data, s) \
00208 ( w += f(x, y, z) + data, w = w<<s | w>>(32-s), w += x )
00209 #endif
00210
00211 void CHash::MD5Transform(uint32_t buf[4], uint32_t const in[16])
00212 {
00213 register uint32_t a, b, c, d;
00214
00215 a = buf[0];
00216 b = buf[1];
00217 c = buf[2];
00218 d = buf[3];
00219
00220 #ifdef __PUREC__
00221 MD5STEP(F1(b, c, d), a, b, c, d, in[0] + 0xd76aa478L, 7);
00222 MD5STEP(F1(a, b, c), d, a, b, c, in[1] + 0xe8c7b756L, 12);
00223 MD5STEP(F1(d, a, b), c, d, a, b, in[2] + 0x242070dbL, 17);
00224 MD5STEP(F1(c, d, a), b, c, d, a, in[3] + 0xc1bdceeeL, 22);
00225 MD5STEP(F1(b, c, d), a, b, c, d, in[4] + 0xf57c0fafL, 7);
00226 MD5STEP(F1(a, b, c), d, a, b, c, in[5] + 0x4787c62aL, 12);
00227 MD5STEP(F1(d, a, b), c, d, a, b, in[6] + 0xa8304613L, 17);
00228 MD5STEP(F1(c, d, a), b, c, d, a, in[7] + 0xfd469501L, 22);
00229 MD5STEP(F1(b, c, d), a, b, c, d, in[8] + 0x698098d8L, 7);
00230 MD5STEP(F1(a, b, c), d, a, b, c, in[9] + 0x8b44f7afL, 12);
00231 MD5STEP(F1(d, a, b), c, d, a, b, in[10] + 0xffff5bb1L, 17);
00232 MD5STEP(F1(c, d, a), b, c, d, a, in[11] + 0x895cd7beL, 22);
00233 MD5STEP(F1(b, c, d), a, b, c, d, in[12] + 0x6b901122L, 7);
00234 MD5STEP(F1(a, b, c), d, a, b, c, in[13] + 0xfd987193L, 12);
00235 MD5STEP(F1(d, a, b), c, d, a, b, in[14] + 0xa679438eL, 17);
00236 MD5STEP(F1(c, d, a), b, c, d, a, in[15] + 0x49b40821L, 22);
00237
00238 MD5STEP(F2(b, c, d), a, b, c, d, in[1] + 0xf61e2562L, 5);
00239 MD5STEP(F2(a, b, c), d, a, b, c, in[6] + 0xc040b340L, 9);
00240 MD5STEP(F2(d, a, b), c, d, a, b, in[11] + 0x265e5a51L, 14);
00241 MD5STEP(F2(c, d, a), b, c, d, a, in[0] + 0xe9b6c7aaL, 20);
00242 MD5STEP(F2(b, c, d), a, b, c, d, in[5] + 0xd62f105dL, 5);
00243 MD5STEP(F2(a, b, c), d, a, b, c, in[10] + 0x02441453L, 9);
00244 MD5STEP(F2(d, a, b), c, d, a, b, in[15] + 0xd8a1e681L, 14);
00245 MD5STEP(F2(c, d, a), b, c, d, a, in[4] + 0xe7d3fbc8L, 20);
00246 MD5STEP(F2(b, c, d), a, b, c, d, in[9] + 0x21e1cde6L, 5);
00247 MD5STEP(F2(a, b, c), d, a, b, c, in[14] + 0xc33707d6L, 9);
00248 MD5STEP(F2(d, a, b), c, d, a, b, in[3] + 0xf4d50d87L, 14);
00249 MD5STEP(F2(c, d, a), b, c, d, a, in[8] + 0x455a14edL, 20);
00250 MD5STEP(F2(b, c, d), a, b, c, d, in[13] + 0xa9e3e905L, 5);
00251 MD5STEP(F2(a, b, c), d, a, b, c, in[2] + 0xfcefa3f8L, 9);
00252 MD5STEP(F2(d, a, b), c, d, a, b, in[7] + 0x676f02d9L, 14);
00253 MD5STEP(F2(c, d, a), b, c, d, a, in[12] + 0x8d2a4c8aL, 20);
00254
00255 MD5STEP(F3(b, c, d), a, b, c, d, in[5] + 0xfffa3942L, 4);
00256 MD5STEP(F3(a, b, c), d, a, b, c, in[8] + 0x8771f681L, 11);
00257 MD5STEP(F3(d, a, b), c, d, a, b, in[11] + 0x6d9d6122L, 16);
00258 MD5STEP(F3(c, d, a), b, c, d, a, in[14] + 0xfde5380cL, 23);
00259 MD5STEP(F3(b, c, d), a, b, c, d, in[1] + 0xa4beea44L, 4);
00260 MD5STEP(F3(a, b, c), d, a, b, c, in[4] + 0x4bdecfa9L, 11);
00261 MD5STEP(F3(d, a, b), c, d, a, b, in[7] + 0xf6bb4b60L, 16);
00262 MD5STEP(F3(c, d, a), b, c, d, a, in[10] + 0xbebfbc70L, 23);
00263 MD5STEP(F3(b, c, d), a, b, c, d, in[13] + 0x289b7ec6L, 4);
00264 MD5STEP(F3(a, b, c), d, a, b, c, in[0] + 0xeaa127faL, 11);
00265 MD5STEP(F3(d, a, b), c, d, a, b, in[3] + 0xd4ef3085L, 16);
00266 MD5STEP(F3(c, d, a), b, c, d, a, in[6] + 0x04881d05L, 23);
00267 MD5STEP(F3(b, c, d), a, b, c, d, in[9] + 0xd9d4d039L, 4);
00268 MD5STEP(F3(a, b, c), d, a, b, c, in[12] + 0xe6db99e5L, 11);
00269 MD5STEP(F3(d, a, b), c, d, a, b, in[15] + 0x1fa27cf8L, 16);
00270 MD5STEP(F3(c, d, a), b, c, d, a, in[2] + 0xc4ac5665L, 23);
00271
00272 MD5STEP(F4(b, c, d), a, b, c, d, in[0] + 0xf4292244L, 6);
00273 MD5STEP(F4(a, b, c), d, a, b, c, in[7] + 0x432aff97L, 10);
00274 MD5STEP(F4(d, a, b), c, d, a, b, in[14] + 0xab9423a7L, 15);
00275 MD5STEP(F4(c, d, a), b, c, d, a, in[5] + 0xfc93a039L, 21);
00276 MD5STEP(F4(b, c, d), a, b, c, d, in[12] + 0x655b59c3L, 6);
00277 MD5STEP(F4(a, b, c), d, a, b, c, in[3] + 0x8f0ccc92L, 10);
00278 MD5STEP(F4(d, a, b), c, d, a, b, in[10] + 0xffeff47dL, 15);
00279 MD5STEP(F4(c, d, a), b, c, d, a, in[1] + 0x85845dd1L, 21);
00280 MD5STEP(F4(b, c, d), a, b, c, d, in[8] + 0x6fa87e4fL, 6);
00281 MD5STEP(F4(a, b, c), d, a, b, c, in[15] + 0xfe2ce6e0L, 10);
00282 MD5STEP(F4(d, a, b), c, d, a, b, in[6] + 0xa3014314L, 15);
00283 MD5STEP(F4(c, d, a), b, c, d, a, in[13] + 0x4e0811a1L, 21);
00284 MD5STEP(F4(b, c, d), a, b, c, d, in[4] + 0xf7537e82L, 6);
00285 MD5STEP(F4(a, b, c), d, a, b, c, in[11] + 0xbd3af235L, 10);
00286 MD5STEP(F4(d, a, b), c, d, a, b, in[2] + 0x2ad7d2bbL, 15);
00287 MD5STEP(F4(c, d, a), b, c, d, a, in[9] + 0xeb86d391L, 21);
00288 #else
00289 MD5STEP(F1, a, b, c, d, in[0] + 0xd76aa478, 7);
00290 MD5STEP(F1, d, a, b, c, in[1] + 0xe8c7b756, 12);
00291 MD5STEP(F1, c, d, a, b, in[2] + 0x242070db, 17);
00292 MD5STEP(F1, b, c, d, a, in[3] + 0xc1bdceee, 22);
00293 MD5STEP(F1, a, b, c, d, in[4] + 0xf57c0faf, 7);
00294 MD5STEP(F1, d, a, b, c, in[5] + 0x4787c62a, 12);
00295 MD5STEP(F1, c, d, a, b, in[6] + 0xa8304613, 17);
00296 MD5STEP(F1, b, c, d, a, in[7] + 0xfd469501, 22);
00297 MD5STEP(F1, a, b, c, d, in[8] + 0x698098d8, 7);
00298 MD5STEP(F1, d, a, b, c, in[9] + 0x8b44f7af, 12);
00299 MD5STEP(F1, c, d, a, b, in[10] + 0xffff5bb1, 17);
00300 MD5STEP(F1, b, c, d, a, in[11] + 0x895cd7be, 22);
00301 MD5STEP(F1, a, b, c, d, in[12] + 0x6b901122, 7);
00302 MD5STEP(F1, d, a, b, c, in[13] + 0xfd987193, 12);
00303 MD5STEP(F1, c, d, a, b, in[14] + 0xa679438e, 17);
00304 MD5STEP(F1, b, c, d, a, in[15] + 0x49b40821, 22);
00305
00306 MD5STEP(F2, a, b, c, d, in[1] + 0xf61e2562, 5);
00307 MD5STEP(F2, d, a, b, c, in[6] + 0xc040b340, 9);
00308 MD5STEP(F2, c, d, a, b, in[11] + 0x265e5a51, 14);
00309 MD5STEP(F2, b, c, d, a, in[0] + 0xe9b6c7aa, 20);
00310 MD5STEP(F2, a, b, c, d, in[5] + 0xd62f105d, 5);
00311 MD5STEP(F2, d, a, b, c, in[10] + 0x02441453, 9);
00312 MD5STEP(F2, c, d, a, b, in[15] + 0xd8a1e681, 14);
00313 MD5STEP(F2, b, c, d, a, in[4] + 0xe7d3fbc8, 20);
00314 MD5STEP(F2, a, b, c, d, in[9] + 0x21e1cde6, 5);
00315 MD5STEP(F2, d, a, b, c, in[14] + 0xc33707d6, 9);
00316 MD5STEP(F2, c, d, a, b, in[3] + 0xf4d50d87, 14);
00317 MD5STEP(F2, b, c, d, a, in[8] + 0x455a14ed, 20);
00318 MD5STEP(F2, a, b, c, d, in[13] + 0xa9e3e905, 5);
00319 MD5STEP(F2, d, a, b, c, in[2] + 0xfcefa3f8, 9);
00320 MD5STEP(F2, c, d, a, b, in[7] + 0x676f02d9, 14);
00321 MD5STEP(F2, b, c, d, a, in[12] + 0x8d2a4c8a, 20);
00322
00323 MD5STEP(F3, a, b, c, d, in[5] + 0xfffa3942, 4);
00324 MD5STEP(F3, d, a, b, c, in[8] + 0x8771f681, 11);
00325 MD5STEP(F3, c, d, a, b, in[11] + 0x6d9d6122, 16);
00326 MD5STEP(F3, b, c, d, a, in[14] + 0xfde5380c, 23);
00327 MD5STEP(F3, a, b, c, d, in[1] + 0xa4beea44, 4);
00328 MD5STEP(F3, d, a, b, c, in[4] + 0x4bdecfa9, 11);
00329 MD5STEP(F3, c, d, a, b, in[7] + 0xf6bb4b60, 16);
00330 MD5STEP(F3, b, c, d, a, in[10] + 0xbebfbc70, 23);
00331 MD5STEP(F3, a, b, c, d, in[13] + 0x289b7ec6, 4);
00332 MD5STEP(F3, d, a, b, c, in[0] + 0xeaa127fa, 11);
00333 MD5STEP(F3, c, d, a, b, in[3] + 0xd4ef3085, 16);
00334 MD5STEP(F3, b, c, d, a, in[6] + 0x04881d05, 23);
00335 MD5STEP(F3, a, b, c, d, in[9] + 0xd9d4d039, 4);
00336 MD5STEP(F3, d, a, b, c, in[12] + 0xe6db99e5, 11);
00337 MD5STEP(F3, c, d, a, b, in[15] + 0x1fa27cf8, 16);
00338 MD5STEP(F3, b, c, d, a, in[2] + 0xc4ac5665, 23);
00339
00340 MD5STEP(F4, a, b, c, d, in[0] + 0xf4292244, 6);
00341 MD5STEP(F4, d, a, b, c, in[7] + 0x432aff97, 10);
00342 MD5STEP(F4, c, d, a, b, in[14] + 0xab9423a7, 15);
00343 MD5STEP(F4, b, c, d, a, in[5] + 0xfc93a039, 21);
00344 MD5STEP(F4, a, b, c, d, in[12] + 0x655b59c3, 6);
00345 MD5STEP(F4, d, a, b, c, in[3] + 0x8f0ccc92, 10);
00346 MD5STEP(F4, c, d, a, b, in[10] + 0xffeff47d, 15);
00347 MD5STEP(F4, b, c, d, a, in[1] + 0x85845dd1, 21);
00348 MD5STEP(F4, a, b, c, d, in[8] + 0x6fa87e4f, 6);
00349 MD5STEP(F4, d, a, b, c, in[15] + 0xfe2ce6e0, 10);
00350 MD5STEP(F4, c, d, a, b, in[6] + 0xa3014314, 15);
00351 MD5STEP(F4, b, c, d, a, in[13] + 0x4e0811a1, 21);
00352 MD5STEP(F4, a, b, c, d, in[4] + 0xf7537e82, 6);
00353 MD5STEP(F4, d, a, b, c, in[11] + 0xbd3af235, 10);
00354 MD5STEP(F4, c, d, a, b, in[2] + 0x2ad7d2bb, 15);
00355 MD5STEP(F4, b, c, d, a, in[9] + 0xeb86d391, 21);
00356 #endif
00357
00358 buf[0] += a;
00359 buf[1] += b;
00360 buf[2] += c;
00361 buf[3] += d;
00362 }
00363 #endif
00364
00365 uint32_t CHash::MurmurHash3(uint8_t* data, int32_t len, uint32_t seed)
00366 {
00367 return PMurHash32(seed, data, len);
00368 }
00369
00370 void CHash::IncrementalMurmurHash3(uint32_t *ph1, uint32_t *pcarry, uint8_t* data, int32_t len)
00371 {
00372 PMurHash32_Process(ph1, pcarry, data, len);
00373 }
00374
00375 uint32_t CHash::FinalizeIncrementalMurmurHash3(uint32_t h, uint32_t carry, uint32_t total_length)
00376 {
00377 return PMurHash32_Result(h, carry, total_length);
00378 }
00379
00380 uint32_t CHash::MurmurHashString(substring s, uint32_t h)
00381 {
00382 uint32_t ret = 0;
00383
00384
00385 for(; *(s.start) <= 0x20 && s.start < s.end; s.start++);
00386
00387
00388 for(; *(s.end-1) <= 0x20 && s.end > s.start; s.end--);
00389
00390 char *p = s.start;
00391 while (p != s.end)
00392 if (isdigit(*p))
00393 ret = 10*ret + *(p++) - '0';
00394 else
00395 return MurmurHash3((uint8_t *)s.start, s.end - s.start, h);
00396
00397 return ret + h;
00398 }