← Back to branch summary

~ps10gel/ubuntu/xenial/trafficserver/6.2.0

« back to all changes in this revision

Viewing changes to lib/ts/MMH.cc

  • Committer: Bazaar Package Importer
  • Author(s): Arno Toell
  • Date: 2011-01-13 11:49:18 UTC
  • Revision ID: james.westby@ubuntu.com-20110113114918-vu422h8dknrgkj15
Tags: upstream-2.1.5-unstable
Import upstream version 2.1.5-unstable

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/ts/MMH.cc
 
1
/** @file
 
2
 
 
3
  A brief file description
 
4
 
 
5
  @section license License
 
6
 
 
7
  Licensed to the Apache Software Foundation (ASF) under one
 
8
  or more contributor license agreements.  See the NOTICE file
 
9
  distributed with this work for additional information
 
10
  regarding copyright ownership.  The ASF licenses this file
 
11
  to you under the Apache License, Version 2.0 (the
 
12
  "License"); you may not use this file except in compliance
 
13
  with the License.  You may obtain a copy of the License at
 
14
 
 
15
      http://www.apache.org/licenses/LICENSE-2.0
 
16
 
 
17
  Unless required by applicable law or agreed to in writing, software
 
18
  distributed under the License is distributed on an "AS IS" BASIS,
 
19
  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 
20
  See the License for the specific language governing permissions and
 
21
  limitations under the License.
 
22
 */
 
23
 
 
24
#include <stdlib.h>
 
25
#include <string.h>
 
26
#include "ink_assert.h"
 
27
#include "ink_platform.h"
 
28
#include "MMH.h"
 
29
 
 
30
#ifndef USE_MD5_FOR_MMH
 
31
 
 
32
#define MMH_X_SIZE      512
 
33
 
 
34
/* BUG: INKqa11504: need it be to 64 bits...otherwise it overflows */
 
35
static uint64_t MMH_x[MMH_X_SIZE + 8] = {
 
36
  0x3ee18b32, 0x746d0d6b, 0x591be6a3, 0x760bd17f,
 
37
  0x363c765d, 0x4bf3d5c5, 0x10f0510a, 0x39a84605,
 
38
  0x2282b48f, 0x6903652e, 0x1b491170, 0x1ab8407a,
 
39
  0x776b8aa8, 0x5b126ffe, 0x5095db1a, 0x565fe90c,
 
40
  0x3ae1f068, 0x73fdf0cb, 0x72f39a81, 0x6a40a4a3,
 
41
  0x4ef557fe, 0x360c1a2c, 0x4579b0ea, 0x61dfd174,
 
42
  0x269b242f, 0x752d6298, 0x15f10fa3, 0x618b7ab3,
 
43
  0x6699171f, 0x488f2c6c, 0x790f8cdb, 0x5ed15565,
 
44
  0x04eba3c0, 0x5009ac0b, 0x3a5d6c1f, 0x1a4f7853,
 
45
  0x1affabd4, 0x74aace1f, 0x2310b46d, 0x466b611a,
 
46
  0x18c5d4a0, 0x7eb9fffe, 0x76098df6, 0x4172f860,
 
47
  0x689e3c2f, 0x722cdc29, 0x64548175, 0x28f46721,
 
48
  0x58fdf93f, 0x12c2dcee, 0x58cb1327, 0x02d4af27,
 
49
  0x4d1c6fcd, 0x72fe572d, 0x7038d366, 0x0bfa1898,
 
50
  0x788d2438, 0x1f131f37, 0x25729ee6, 0x635ea6a9,
 
51
  0x3b0b5714, 0x6ac759d2, 0x5faf688a, 0x0c2fe571,
 
52
  0x7487538e, 0x65491b59, 0x60cd86e4, 0x5d6482d8,
 
53
  0x4a59fa77, 0x78439700, 0x56a51f48, 0x360544ae,
 
54
  0x6c01b3ef, 0x2228c036, 0x15b7e88b, 0x326e0dd8,
 
55
  0x509491af, 0x72d06023, 0x26181f5d, 0x7924c4a4,
 
56
  0x70c60bf2, 0x7b5bc151, 0x28e42640, 0x48af0c3e,
 
57
  0x009b6301, 0x06dd3366, 0x2ad1eb24, 0x102ce33c,
 
58
  0x1e504f5a, 0x5ab4c90f, 0x669ccca1, 0x118d5954,
 
59
  0x1a1e4a7c, 0x1807d1f9, 0x525a58d0, 0x2f13ae2d,
 
60
  0x17335a52, 0x714eb2f9, 0x1865dfc7, 0x61b64b52,
 
61
  0x0dc9e939, 0x4fccde4c, 0x6d5873af, 0x47c62b43,
 
62
  0x0fa1d4b0, 0x2f00cdf8, 0x68029083, 0x52645fa6,
 
63
  0x4bb37c9b, 0x53d60251, 0x48364566, 0x35b4889b,
 
64
  0x46783d34, 0x30c12697, 0x210459a1, 0x36962f2d,
 
65
  0x36305d8f, 0x170e9dbd, 0x687c8739, 0x261c14e4,
 
66
  0x3cc51cc7, 0x02add945, 0x01a88529, 0x6617aa77,
 
67
  0x6be627ca, 0x14c7fc46, 0x46fb3b41, 0x1bffff9e,
 
68
  0x1e6c61be, 0x10966c8f, 0x3f69199b, 0x1b5e9e06,
 
69
  0x4880890f, 0x055613e6, 0x6c742db5, 0x7be1e15e,
 
70
  0x2522e317, 0x41fe3369, 0x2b462f30, 0x605b7e8e,
 
71
  0x1c19b868, 0x3fadcb16, 0x781c5e24, 0x1c6b0c08,
 
72
  0x499f0bb9, 0x04b0b766, 0x7d6cad1e, 0x097f7d36,
 
73
  0x2e02956a, 0x03adc713, 0x4ce950b7, 0x6e57a313,
 
74
  0x557badb5, 0x73212afb, 0x3f7f6ed2, 0x0558e3d6,
 
75
  0x28376f73, 0x54dac21d, 0x6c3f4771, 0x67147bc8,
 
76
  0x5ae9fd88, 0x51ede3c0, 0x1067d134, 0x5246b937,
 
77
  0x056e74ed, 0x5d7869b2, 0x62356370, 0x76a0c583,
 
78
  0x3defb558, 0x5200dcae, 0x1432a7e8, 0x3ae4ad55,
 
79
  0x0c4cca8a, 0x0607c4d7, 0x1944ae2b, 0x726479f0,
 
80
  0x558e6035, 0x5ae64061, 0x4e1e9a8a, 0x0cf04d9f,
 
81
  0x46ef4a87, 0x0554224f, 0x70d70ab3, 0x03cc954e,
 
82
  0x39d0cd57, 0x1b11fb56, 0x62a0e9ee, 0x55888135,
 
83
  0x3e93ebeb, 0x29578ee1, 0x0bcb0ef4, 0x529e16af,
 
84
  0x165bab64, 0x39ed562e, 0x52c59d67, 0x48c84d29,
 
85
  0x0fd0d1c7, 0x795fd395, 0x79a1c4f3, 0x5010c835,
 
86
  0x4fbe4ba8, 0x49a597e9, 0x29f017ff, 0x59dde0be,
 
87
  0x2c660275, 0x15fcfbf7, 0x1eab540f, 0x38e2cf56,
 
88
  0x74608d5c, 0x7cd4b02c, 0x52a115b9, 0x2bdee9ac,
 
89
  0x5456c6da, 0x63626453, 0x15279241, 0x19b60519,
 
90
  0x508af0e1, 0x2e3ce97b, 0x568710d4, 0x6abb3059,
 
91
  0x7897b1a5, 0x17034ff6, 0x2aef7d5e, 0x5a281657,
 
92
  0x0fa5d304, 0x76f0a37e, 0x31be0f08, 0x46ce7c20,
 
93
  0x563e4e90, 0x31540773, 0x1cdc9c51, 0x10366bfa,
 
94
  0x1b6cd03a, 0x615f1540, 0x18c3d6c8, 0x3cb2bf8e,
 
95
  0x29bf799c, 0x40b87edb, 0x42c34863, 0x1e9edb40,
 
96
  0x64734fe2, 0x3ddf176a, 0x1c458c7f, 0x06138c9f,
 
97
  0x5e695e56, 0x02c98403, 0x0474de75, 0x660e1df8,
 
98
  0x6df73788, 0x3770f68c, 0x758bb7d5, 0x0763d105,
 
99
  0x16e61f16, 0x153974c1, 0x29ded842, 0x1a0d12c3,
 
100
  0x599ec61d, 0x05904d54, 0x79e9b0ea, 0x4976da61,
 
101
  0x5834243c, 0x67c17d2f, 0x65fbcda0, 0x17bdc554,
 
102
  0x465e9741, 0x7a0ee6d5, 0x3b357597, 0x0d1da287,
 
103
  0x01211373, 0x04a05de6, 0x5deb5dbd, 0x6d993eb0,
 
104
  0x2064ce7c, 0x3011a8c1, 0x36ece6b1, 0x4a0963be,
 
105
  0x0cf46ef0, 0x0d53ba44, 0x63260063, 0x187f1d6e,
 
106
  0x7e866a7e, 0x4b6885af, 0x254d6d47, 0x715474fd,
 
107
  0x6896dcb2, 0x7554eea6, 0x2161bf36, 0x5387f5f8,
 
108
  0x5c4bc064, 0x059a7755, 0x7d4307e1, 0x17326e2f,
 
109
  0x5e2315c1, 0x14c26eae, 0x1e5cd6f2, 0x352b7ac8,
 
110
  0x66591ef3, 0x381e80cd, 0x19b3bfc1, 0x3668946f,
 
111
  0x4b6d7d70, 0x20feab7d, 0x1b6340af, 0x356b6cab,
 
112
  0x299099dc, 0x295ab8d4, 0x184c8623, 0x134f8e4c,
 
113
  0x7caf609c, 0x716d81f9, 0x2e04231f, 0x1dd45301,
 
114
  0x43e9fcf9, 0x1c225c06, 0x0994797e, 0x5b3f6006,
 
115
  0x1d22dcec, 0x32993108, 0x3f0c2bcc, 0x4d44fbfa,
 
116
  0x389de78c, 0x7f8be723, 0x5dab92c1, 0x7866afce,
 
117
  0x3bfc7011, 0x4a27d7d3, 0x0c79d05c, 0x268dc4da,
 
118
  0x3fe10f84, 0x1f18394d, 0x20b9ba99, 0x312e520a,
 
119
  0x64cf2f05, 0x322a7c04, 0x4cc077ce, 0x7218aa35,
 
120
  0x550cacb8, 0x5943be47, 0x15b346a8, 0x0d6a1d8e,
 
121
  0x3f08a54d, 0x7a6e9807, 0x274f8bbc, 0x6feb2033,
 
122
  0x64b10c2b, 0x2cbaa0b7, 0x0db7decc, 0x22b807e3,
 
123
  0x10d15c39, 0x6a9b314c, 0x5ff27199, 0x5072b2cd,
 
124
  0x4eaf4b49, 0x5a890464, 0x7df0ca60, 0x548e8983,
 
125
  0x5e3f0a21, 0x70027683, 0x503e6bf2, 0x47ad6e0d,
 
126
  0x77173b26, 0x6dc04878, 0x4d73a573, 0x439b4a1a,
 
127
  0x2e6569a7, 0x1630e5de, 0x1be363af, 0x6f5f0e52,
 
128
  0x5b266bc3, 0x2f2a51be, 0x204e7e14, 0x1b3314c6,
 
129
  0x4472b8f9, 0x4162fb52, 0x72549950, 0x3223f889,
 
130
  0x0e655f4a, 0x65c3dce4, 0x04825988, 0x22b41458,
 
131
  0x53a4e10d, 0x3e2a66d5, 0x29de3e31, 0x0252fa74,
 
132
  0x267fe54f, 0x42d6d8ba, 0x5951218f, 0x73db5791,
 
133
  0x618444e4, 0x79abcaa1, 0x0ddcf5c8, 0x2cbed2e6,
 
134
  0x73159e0e, 0x7aadc871, 0x10e3f9a4, 0x762e9d65,
 
135
  0x2a7138c9, 0x59fe016f, 0x5b6c3ee4, 0x28888205,
 
136
  0x695fa5b1, 0x50f92ddd, 0x07eefc3b, 0x42bb693a,
 
137
  0x71312191, 0x3653ecbd, 0x1d80c4ed, 0x5a536187,
 
138
  0x6a286789, 0x4a1ffbb3, 0x1e976003, 0x5a8c5f29,
 
139
  0x2ac83bdb, 0x5ab9cb08, 0x63039928, 0x5a4c04f4,
 
140
  0x7b329952, 0x40d40fcb, 0x01810524, 0x2555e83c,
 
141
  0x748d0b4f, 0x534f1612, 0x272353f2, 0x6992e1ea,
 
142
  0x33cc5e71, 0x5163b55e, 0x29886a7f, 0x7cfb1eae,
 
143
  0x330271e0, 0x6f05e91c, 0x35b01e02, 0x64bbc053,
 
144
  0x76eb9337, 0x62612f48, 0x044e0af2, 0x1dac022e,
 
145
  0x1ca56f0c, 0x0210ef2c, 0x5af7a1a9, 0x2632f2b0,
 
146
  0x23d0401c, 0x0c594a46, 0x77582293, 0x297df41b,
 
147
  0x4c7b8718, 0x6c48d948, 0x4835e412, 0x74795651,
 
148
  0x28ca3506, 0x4071f739, 0x032fdbf2, 0x097f7bc8,
 
149
  0x44ced256, 0x47f25cb9, 0x43500684, 0x45481b9a,
 
150
  0x5a5ecc82, 0x4fe9ed61, 0x337ee559, 0x556852b9,
 
151
  0x0b24b460, 0x696db949, 0x7a2def9d, 0x4fcd5640,
 
152
  0x1babd707, 0x5c9254a3, 0x44d26e0d, 0x0e26b8e4,
 
153
  0x3b1c3b5c, 0x0078c784, 0x27a7dc96, 0x1d525589,
 
154
  0x4384ae38, 0x447b77c3, 0x78488b8c, 0x5eab10f1,
 
155
  0x16812737, 0x37cc8efa, 0x219cda83, 0x00bcc48f,
 
156
  0x3c667020, 0x492d7eaa, 0x710d06ce, 0x4172c47a,
 
157
  0x358098ec, 0x1fff647b, 0x65672792, 0x1a7b927d,
 
158
  0x24006275, 0x04e630a0, 0x2f2a9185, 0x5873704b,
 
159
  0x0a8c69bc, 0x06b49059, 0x49837c48, 0x4f90a2d0,
 
160
  0x29ad7dd7, 0x3674be92, 0x46d5635f, 0x782758a2,
 
161
  0x721a2a75, 0x13427ca9, 0x20e03cc9, 0x5f884596,
 
162
  0x19dc210f, 0x066c954d, 0x52f43f40, 0x5d9c256f,
 
163
  0x7f0acaae, 0x1e186b81, 0x55e9920f, 0x0e4f77b2,
 
164
  0x6700ec53, 0x268837c0, 0x554ce08b, 0x4284e695,
 
165
  0x2127e806, 0x384cb53b, 0x51076b2f, 0x23f9eb15
 
166
};
 
167
 
 
168
// We don't need this generator in release.
 
169
#ifdef TEST
 
170
// generator for above
 
171
static void
 
172
ink_init_MMH()
 
173
{
 
174
  srand48(13);                  // must remain the same!
 
175
  for (int i = 0; i < MMH_X_SIZE; i++)
 
176
    MMH_x[i] = lrand48();
 
177
}
 
178
#endif /* TEST */
 
179
 
 
180
 
 
181
#ifndef __GNUC__
 
182
// these are short < 16 bytes, help by permitting inlining
 
183
static inline void
 
184
_memcpy(void *dest, const void *src, int nbytes)
 
185
{
 
186
  for (int i = 0; i < nbytes; i++)
 
187
    ((char *) dest)[i] = ((char *) src)[i];
 
188
}
 
189
 
 
190
#define memcpy _memcpy
 
191
#endif
 
192
 
 
193
int
 
194
ink_code_incr_MMH_init(MMH_CTX * ctx)
 
195
{
 
196
  ctx->buffer_size = 0;
 
197
  ctx->blocks = 0;
 
198
  ctx->state[0] = ((uint64_t) MMH_x[MMH_X_SIZE + 0] << 32) + MMH_x[MMH_X_SIZE + 1];
 
199
  ctx->state[1] = ((uint64_t) MMH_x[MMH_X_SIZE + 2] << 32) + MMH_x[MMH_X_SIZE + 3];
 
200
  ctx->state[2] = ((uint64_t) MMH_x[MMH_X_SIZE + 4] << 32) + MMH_x[MMH_X_SIZE + 5];
 
201
  ctx->state[3] = ((uint64_t) MMH_x[MMH_X_SIZE + 6] << 32) + MMH_x[MMH_X_SIZE + 7];
 
202
  return 0;
 
203
}
 
204
 
 
205
int
 
206
ink_code_MMH(unsigned char *input, int len, unsigned char *sixteen_byte_hash)
 
207
{
 
208
  MMH_CTX ctx;
 
209
  ink_code_incr_MMH_init(&ctx);
 
210
  ink_code_incr_MMH_update(&ctx, (const char *) input, len);
 
211
  ink_code_incr_MMH_final((char *) sixteen_byte_hash, &ctx);
 
212
  return 0;
 
213
}
 
214
 
 
215
static inline void
 
216
MMH_update(MMH_CTX * ctx, unsigned char *ab)
 
217
{
 
218
  uint32_t *b = (uint32_t *) ab;
 
219
  ctx->state[0] += b[0] * MMH_x[(ctx->blocks + 0) % MMH_X_SIZE];
 
220
  ctx->state[1] += b[1] * MMH_x[(ctx->blocks + 1) % MMH_X_SIZE];
 
221
  ctx->state[2] += b[2] * MMH_x[(ctx->blocks + 2) % MMH_X_SIZE];
 
222
  ctx->state[3] += b[3] * MMH_x[(ctx->blocks + 3) % MMH_X_SIZE];
 
223
  ctx->blocks += 4;
 
224
}
 
225
 
 
226
static inline void
 
227
MMH_updateb1(MMH_CTX * ctx, unsigned char *ab)
 
228
{
 
229
  uint32_t *b = (uint32_t *) (ab - 1);
 
230
  uint32_t b0 = b[0], b1 = b[1], b2 = b[2], b3 = b[3], b4 = b[4];
 
231
  b0 = (b0 << 8) + (b1 >> 24);
 
232
  b1 = (b1 << 8) + (b2 >> 24);
 
233
  b2 = (b2 << 8) + (b3 >> 24);
 
234
  b3 = (b3 << 8) + (b4 >> 24);
 
235
  ctx->state[0] += b0 * MMH_x[(ctx->blocks + 0) % MMH_X_SIZE];
 
236
  ctx->state[1] += b1 * MMH_x[(ctx->blocks + 1) % MMH_X_SIZE];
 
237
  ctx->state[2] += b2 * MMH_x[(ctx->blocks + 2) % MMH_X_SIZE];
 
238
  ctx->state[3] += b3 * MMH_x[(ctx->blocks + 3) % MMH_X_SIZE];
 
239
  ctx->blocks += 4;
 
240
}
 
241
 
 
242
static inline void
 
243
MMH_updateb2(MMH_CTX * ctx, unsigned char *ab)
 
244
{
 
245
  uint32_t *b = (uint32_t *) (ab - 2);
 
246
  uint32_t b0 = b[0], b1 = b[1], b2 = b[2], b3 = b[3], b4 = b[4];
 
247
  b0 = (b0 << 16) + (b1 >> 16);
 
248
  b1 = (b1 << 16) + (b2 >> 16);
 
249
  b2 = (b2 << 16) + (b3 >> 16);
 
250
  b3 = (b3 << 16) + (b4 >> 16);
 
251
  ctx->state[0] += b0 * MMH_x[(ctx->blocks + 0) % MMH_X_SIZE];
 
252
  ctx->state[1] += b1 * MMH_x[(ctx->blocks + 1) % MMH_X_SIZE];
 
253
  ctx->state[2] += b2 * MMH_x[(ctx->blocks + 2) % MMH_X_SIZE];
 
254
  ctx->state[3] += b3 * MMH_x[(ctx->blocks + 3) % MMH_X_SIZE];
 
255
  ctx->blocks += 4;
 
256
}
 
257
 
 
258
static inline void
 
259
MMH_updateb3(MMH_CTX * ctx, unsigned char *ab)
 
260
{
 
261
  uint32_t *b = (uint32_t *) (ab - 3);
 
262
  uint32_t b0 = b[0], b1 = b[1], b2 = b[2], b3 = b[3], b4 = b[4];
 
263
  b0 = (b0 << 24) + (b1 >> 8);
 
264
  b1 = (b1 << 24) + (b2 >> 8);
 
265
  b2 = (b2 << 24) + (b3 >> 8);
 
266
  b3 = (b3 << 24) + (b4 >> 8);
 
267
  ctx->state[0] += b0 * MMH_x[(ctx->blocks + 0) % MMH_X_SIZE];
 
268
  ctx->state[1] += b1 * MMH_x[(ctx->blocks + 1) % MMH_X_SIZE];
 
269
  ctx->state[2] += b2 * MMH_x[(ctx->blocks + 2) % MMH_X_SIZE];
 
270
  ctx->state[3] += b3 * MMH_x[(ctx->blocks + 3) % MMH_X_SIZE];
 
271
  ctx->blocks += 4;
 
272
}
 
273
 
 
274
static inline void
 
275
MMH_updatel1(MMH_CTX * ctx, unsigned char *ab)
 
276
{
 
277
  uint32_t *b = (uint32_t *) (ab - 1);
 
278
  uint32_t b0 = b[0], b1 = b[1], b2 = b[2], b3 = b[3], b4 = b[4];
 
279
  b0 = (b0 >> 8) + (b1 << 24);
 
280
  b1 = (b1 >> 8) + (b2 << 24);
 
281
  b2 = (b2 >> 8) + (b3 << 24);
 
282
  b3 = (b3 >> 8) + (b4 << 24);
 
283
  ctx->state[0] += b0 * MMH_x[(ctx->blocks + 0) % MMH_X_SIZE];
 
284
  ctx->state[1] += b1 * MMH_x[(ctx->blocks + 1) % MMH_X_SIZE];
 
285
  ctx->state[2] += b2 * MMH_x[(ctx->blocks + 2) % MMH_X_SIZE];
 
286
  ctx->state[3] += b3 * MMH_x[(ctx->blocks + 3) % MMH_X_SIZE];
 
287
  ctx->blocks += 4;
 
288
}
 
289
 
 
290
static inline void
 
291
MMH_updatel2(MMH_CTX * ctx, unsigned char *ab)
 
292
{
 
293
  uint32_t *b = (uint32_t *) (ab - 2);
 
294
  uint32_t b0 = b[0], b1 = b[1], b2 = b[2], b3 = b[3], b4 = b[4];
 
295
  b0 = (b0 >> 16) + (b1 << 16);
 
296
  b1 = (b1 >> 16) + (b2 << 16);
 
297
  b2 = (b2 >> 16) + (b3 << 16);
 
298
  b3 = (b3 >> 16) + (b4 << 16);
 
299
  ctx->state[0] += b0 * MMH_x[(ctx->blocks + 0) % MMH_X_SIZE];
 
300
  ctx->state[1] += b1 * MMH_x[(ctx->blocks + 1) % MMH_X_SIZE];
 
301
  ctx->state[2] += b2 * MMH_x[(ctx->blocks + 2) % MMH_X_SIZE];
 
302
  ctx->state[3] += b3 * MMH_x[(ctx->blocks + 3) % MMH_X_SIZE];
 
303
  ctx->blocks += 4;
 
304
}
 
305
 
 
306
static inline void
 
307
MMH_updatel3(MMH_CTX * ctx, unsigned char *ab)
 
308
{
 
309
  uint32_t *b = (uint32_t *) (ab - 3);
 
310
  uint32_t b0 = b[0], b1 = b[1], b2 = b[2], b3 = b[3], b4 = b[4];
 
311
  b0 = (b0 >> 24) + (b1 << 8);
 
312
  b1 = (b1 >> 24) + (b2 << 8);
 
313
  b2 = (b2 >> 24) + (b3 << 8);
 
314
  b3 = (b3 >> 24) + (b4 << 8);
 
315
  ctx->state[0] += b0 * MMH_x[(ctx->blocks + 0) % MMH_X_SIZE];
 
316
  ctx->state[1] += b1 * MMH_x[(ctx->blocks + 1) % MMH_X_SIZE];
 
317
  ctx->state[2] += b2 * MMH_x[(ctx->blocks + 2) % MMH_X_SIZE];
 
318
  ctx->state[3] += b3 * MMH_x[(ctx->blocks + 3) % MMH_X_SIZE];
 
319
  ctx->blocks += 4;
 
320
}
 
321
 
 
322
int
 
323
ink_code_incr_MMH_update(MMH_CTX * ctx, const char *ainput, int input_length)
 
324
{
 
325
  unsigned char *in = (unsigned char *) ainput;
 
326
  unsigned char *end = in + input_length;
 
327
  if (ctx->buffer_size) {
 
328
    int l = 16 - ctx->buffer_size;
 
329
    if (input_length >= l) {
 
330
      memcpy(ctx->buffer + ctx->buffer_size, in, l);
 
331
      ctx->buffer_size = 0;
 
332
      in += l;
 
333
      if (ctx->buffer_size & 0x0f)
 
334
        return 0;
 
335
      MMH_update(ctx, ctx->buffer);
 
336
    } else
 
337
      goto Lstore;
 
338
  }
 
339
  {
 
340
    // check alignment
 
341
    int alignment = (int)((intptr_t) in & 0x3);
 
342
    if (alignment) {
 
343
#if defined(_BIG_ENDIAN)
 
344
#define big_endian 1
 
345
#elif defined(_LITTLE_ENDIAN)
 
346
#define big_endian 0
 
347
#else
 
348
      unsigned int endian = 1;
 
349
      int big_endian = !*(char *) &endian;
 
350
#endif
 
351
      if (big_endian) {
 
352
        if (alignment == 1) {
 
353
          while (in + 16 <= end) {
 
354
            MMH_updateb1(ctx, in);
 
355
            in += 16;
 
356
          }
 
357
        } else if (alignment == 2) {
 
358
          while (in + 16 <= end) {
 
359
            MMH_updateb2(ctx, in);
 
360
            in += 16;
 
361
          }
 
362
        } else if (alignment == 3)
 
363
          while (in + 16 <= end) {
 
364
            MMH_updateb3(ctx, in);
 
365
            in += 16;
 
366
          }
 
367
      } else {
 
368
        if (alignment == 1) {
 
369
          while (in + 16 <= end) {
 
370
            MMH_updatel1(ctx, in);
 
371
            in += 16;
 
372
          }
 
373
        } else if (alignment == 2) {
 
374
          while (in + 16 <= end) {
 
375
            MMH_updatel2(ctx, in);
 
376
            in += 16;
 
377
          }
 
378
        } else if (alignment == 3)
 
379
          while (in + 16 <= end) {
 
380
            MMH_updatel3(ctx, in);
 
381
            in += 16;
 
382
          }
 
383
      }
 
384
    } else {
 
385
      while (in + 16 <= end) {
 
386
        MMH_update(ctx, in);
 
387
        in += 16;
 
388
      }
 
389
    }
 
390
  }
 
391
Lstore:
 
392
  if (end - in) {
 
393
    int oldbs = ctx->buffer_size;
 
394
    ctx->buffer_size += (int) (end - in);
 
395
#ifndef TEST
 
396
    ink_assert(ctx->buffer_size < 16);
 
397
#endif
 
398
    memcpy(ctx->buffer + oldbs, in, (int) (end - in));
 
399
  }
 
400
  return 0;
 
401
}
 
402
 
 
403
#if defined(__GNUC__)
 
404
#define _memset memset
 
405
#else
 
406
// NOT general purpose
 
407
inline void
 
408
_memset(unsigned char *b, int c, int len)
 
409
{
 
410
  (void) c;
 
411
  int o = len & 0x3, i;
 
412
  for (i = 0; i < o; i++)
 
413
    b[i] = 0;
 
414
  for (i = 0; i < (len - o) / 4; i++)
 
415
    ((uint32_t *) (b + o))[i] = 0;
 
416
}
 
417
#endif
 
418
 
 
419
 
 
420
int
 
421
ink_code_incr_MMH_final(char *presult, MMH_CTX * ctx)
 
422
{
 
423
  unsigned int len = ctx->blocks * 4 + ctx->buffer_size;
 
424
  // pad out to 16 bytes
 
425
  if (ctx->buffer_size) {
 
426
    _memset(ctx->buffer + ctx->buffer_size, 0, 16 - ctx->buffer_size);
 
427
    ctx->buffer_size = 0;
 
428
    MMH_update(ctx, ctx->buffer);
 
429
  }
 
430
  // append length (before padding)
 
431
  unsigned int *pbuffer = (unsigned int *) ctx->buffer;
 
432
  pbuffer[1] = pbuffer[2] = pbuffer[3] = pbuffer[0] = len;
 
433
  MMH_update(ctx, ctx->buffer);
 
434
  // final phase
 
435
  uint32_t *b = (uint32_t *) presult;
 
436
  uint64_t d = (((uint64_t) 1) << 32) + 15;
 
437
  uint32_t b0 = uint32_t(ctx->state[0] % d);
 
438
  uint32_t b1 = uint32_t(ctx->state[1] % d);
 
439
  uint32_t b2 = uint32_t(ctx->state[2] % d);
 
440
  uint32_t b3 = uint32_t(ctx->state[3] % d);
 
441
  // scramble the bits, losslessly (reversibly)
 
442
  b[0] = b0;
 
443
  b[1] = b1 ^ (b0 >> 24) ^ (b0 << 8);
 
444
  b[2] = b2 ^ (b1 >> 16) ^ (b1 << 16)
 
445
    ^ (b0 >> 24) ^ (b0 << 8);
 
446
  b[3] = b3 ^ (b1 >> 8) ^ (b1 << 24)
 
447
    ^ (b2 >> 16) ^ (b2 << 16)
 
448
    ^ (b0 >> 24) ^ (b0 << 8);
 
449
 
 
450
  b0 = b[0];
 
451
  b1 = b[1];
 
452
  b2 = b[2];
 
453
  b3 = b[3];
 
454
 
 
455
  b[2] = b2 ^ (b3 >> 24) ^ (b3 << 8);
 
456
  b[1] = b1 ^ (b2 >> 16) ^ (b2 << 16)
 
457
    ^ (b3 >> 24) ^ (b3 << 8);
 
458
  b[0] = b0 ^ (b3 >> 8) ^ (b3 << 24)
 
459
    ^ (b2 >> 16) ^ (b2 << 16)
 
460
    ^ (b1 >> 24) ^ (b1 << 8);
 
461
  return 0;
 
462
}
 
463
 
 
464
#ifdef TEST
 
465
 
 
466
#define TEST_COLLISIONS 10000000
 
467
 
 
468
static int
 
469
xxcompar(uint32_t ** x, uint32_t ** y)
 
470
{
 
471
  for (int i = 0; i < 4; i++) {
 
472
    if (x[i] > y[i])
 
473
      return 1;
 
474
    if (x[i] < y[i])
 
475
      return -1;
 
476
  }
 
477
  return 0;
 
478
}
 
479
 
 
480
typedef uint32_t i4_t[4];
 
481
i4_t *xxh;
 
482
double *xf;
 
483
 
 
484
main()
 
485
{
 
486
  union
 
487
  {
 
488
    unsigned char hash[16];
 
489
    uint32_t h[4];
 
490
  } h;
 
491
 
 
492
  xxh = (i4_t *) malloc(4 * sizeof(uint32_t) * TEST_COLLISIONS);
 
493
  xf = (double *) malloc(sizeof(double) * TEST_COLLISIONS);
 
494
 
 
495
  printf("test collisions\n");
 
496
  char *sc1 = "http://npdev:19080/1.6664000000/4000";
 
497
  char *sc2 = "http://npdev:19080/1.8666000000/4000";
 
498
  char *sc3 = "http://:@npdev/1.6664000000/4000;?";
 
499
  char *sc4 = "http://:@npdev/1.8666000000/4000;?";
 
500
  ink_code_MMH((unsigned char *) sc1, strlen(sc1), h.hash);
 
501
  printf("%X %X %X %X\n", h.h[0], h.h[1], h.h[2], h.h[3]);
 
502
  ink_code_MMH((unsigned char *) sc2, strlen(sc2), h.hash);
 
503
  printf("%X %X %X %X\n", h.h[0], h.h[1], h.h[2], h.h[3]);
 
504
  ink_code_MMH((unsigned char *) sc3, strlen(sc3), h.hash);
 
505
  printf("%X %X %X %X\n", h.h[0], h.h[1], h.h[2], h.h[3]);
 
506
  ink_code_MMH((unsigned char *) sc4, strlen(sc4), h.hash);
 
507
  printf("%X %X %X %X\n", h.h[0], h.h[1], h.h[2], h.h[3]);
 
508
 
 
509
  srand48(time(NULL));
 
510
  for (int xx = 0; xx < TEST_COLLISIONS; xx++) {
 
511
    char xs[256];
 
512
    xf[xx] = drand48();
 
513
    sprintf(xs, "http://@npdev/%16.14f/4000;?", xf[xx]);
 
514
    ink_code_MMH((unsigned char *) xs, strlen(xs), (unsigned char *) &xxh[xx]);
 
515
  }
 
516
  qsort(xxh, TEST_COLLISIONS, 16, xxcompar);
 
517
  for (int xy = 0; xy < TEST_COLLISIONS - 1; xy++) {
 
518
    if (xxh[xy][0] == xxh[xy + 1][0] &&
 
519
        xxh[xy][1] == xxh[xy + 1][1] && xxh[xy][2] == xxh[xy + 1][2] && xxh[xy][3] == xxh[xy + 1][3])
 
520
      printf("********** collision %d\n", xy);
 
521
  }
 
522
 
 
523
  unsigned char *s = (unsigned char *) MMH_x;
 
524
  int l = sizeof(MMH_x);
 
525
  unsigned char *s1 = (unsigned char *) malloc(l + 3);
 
526
  s1 += 1;
 
527
  memcpy(s1, s, l);
 
528
  unsigned char *s2 = (unsigned char *) malloc(l + 3);
 
529
  s2 += 2;
 
530
  memcpy(s2, s, l);
 
531
  unsigned char *s3 = (unsigned char *) malloc(l + 3);
 
532
  s3 += 3;
 
533
  memcpy(s3, s, l);
 
534
 
 
535
  printf("test alignment\n");
 
536
  ink_code_MMH(s, l, h.hash);
 
537
  printf("%X %X %X %X\n", h.h[0], h.h[1], h.h[2], h.h[3]);
 
538
  ink_code_MMH(s1, l, h.hash);
 
539
  printf("%X %X %X %X\n", h.h[0], h.h[1], h.h[2], h.h[3]);
 
540
  ink_code_MMH(s2, l, h.hash);
 
541
  printf("%X %X %X %X\n", h.h[0], h.h[1], h.h[2], h.h[3]);
 
542
  ink_code_MMH(s3, l, h.hash);
 
543
  printf("%X %X %X %X\n", h.h[0], h.h[1], h.h[2], h.h[3]);
 
544
 
 
545
  int i = 0;
 
546
  MMH_CTX c;
 
547
  unsigned char *t = s;
 
548
  printf("test chunking\n");
 
549
  ink_code_incr_MMH_init(&c);
 
550
  for (i = 0; i < 24; i++) {
 
551
    ink_code_incr_MMH_update(&c, (char *) t, i);
 
552
    t += i;
 
553
  }
 
554
  ink_code_incr_MMH_final((char *) h.hash, &c);
 
555
  printf("%X %X %X %X\n", h.h[0], h.h[1], h.h[2], h.h[3]);
 
556
  int q = t - s;
 
557
  ink_code_MMH(s, q, h.hash);
 
558
  printf("%X %X %X %X\n", h.h[0], h.h[1], h.h[2], h.h[3]);
 
559
 
 
560
  FILE *fp = fopen("/kernel/genunix", "r");
 
561
  char x[4096];
 
562
  int hist[256];
 
563
  memset(hist, 0, sizeof(hist));
 
564
  size_t xx;
 
565
  while (((xx = fread(x, 1, 128, fp)) == 128)) {
 
566
    ink_code_MMH((unsigned char *) x, 128, h.hash);
 
567
    hist[h.h[0] & 255]++;
 
568
  }
 
569
  for (int z = 0; z < 256; z++) {
 
570
    printf("%6d ", hist[z]);
 
571
    if (!(z % 7))
 
572
      printf("\n");
 
573
  }
 
574
}
 
575
#endif
 
576
 
 
577
#endif