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