1 /* ------------------------------------------------
2 Copyright 2014 AT&T Intellectual Property
3 Licensed under the Apache License, Version 2.0 (the "License");
4 you may not use this file except in compliance with the License.
5 You may obtain a copy of the License at
7 http://www.apache.org/licenses/LICENSE-2.0
9 Unless required by applicable law or agreed to in writing, software
10 distributed under the License is distributed on an "AS IS" BASIS,
11 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 See the License for the specific language governing permissions and
13 limitations under the License.
14 ------------------------------------------- */
24 //Provides 5-universal hash functions.
25 //Both a direct polynomial based one,
26 //and the much faster tabulation based one.
28 //It also provides 2-universal string hashing.
29 //For most applicatoins, introdcing a slight error,
30 //if you want almost 5-uninversal hashing for strings,
31 //you can do a 2-universal hashing into 32-bit integer
32 //getting very few collissoins, and then use the above
37 typedef gs_uint8_t INT8;
38 typedef gs_uint16_t INT16;
39 typedef gs_uint32_t INT32;
40 typedef gs_uint64_t INT64;
42 typedef INT64 * Hash61bit5univID;
43 typedef INT32** HashTab32bit5univID;
44 typedef INT32** HashTab32bitLPID;
45 typedef INT64** HashTab64bitLPID;
46 typedef INT64 * Hash32bit2univID;
47 typedef INT32 Hash32bitUnivID;
49 const INT32 MAX_INT32 = UINT_MAX;
52 INT64 str_compr_hid[16];
55 // INT64 last_compr_hid;
58 typedef VISHID * VarINT32StringHash32bit2univID;
63 INT64 str_compr_hid[16];
66 // INT64 last_compr_hid;
69 typedef VSHID * VarStringHash32bit2univID;
75 // different views of a 64-bit double word
82 const INT64 LowOnes = (((INT64)1)<<32)-1;
84 #define LOW(x) ((x)&LowOnes) // extract lower 32 bits from INT64
85 #define HIGH(x) ((x)>>32) // extract higher 32 bits from INT64
87 const INT64 Prime61 = (((INT64)1)<<61) - 1;
90 //Random numbers from random.org based on atmostpheric noise.
91 static INT64 Random64[200]= {0x285eb7722a62ce6eull,
92 0xa84c7463e2b7856bull,
93 0xb29100d6abcc8666ull,
94 0xf9bfca5b7461fb1full,
95 0x51c8dafc30c88dadull,
96 0x0687468c365ec51dull,
97 0x2bf2cd3ad64b6218ull,
98 0xc20565a4d1f00f9eull,
99 0x7d533575d313c658ull,
100 0xbf2fba6b00725b85ull,
101 0x4cfc2f6557e722beull,
102 0xedbce818556dfb2bull,
103 0xd9df508027db1bbeull,
104 0x21f2d922f712f48bull,
105 0xcd8b289d83a65804ull,
106 0x4a19cfb02445a6d2ull,
107 0xc95e56b1e19a4f94ull,
108 0xcfeeeaccaf477248ull,
109 0x4eec3378b73bb25cull,
110 0x18a3f38d1c48b2beull,
111 0x71b79ab5cb1e3730ull,
112 0x79cdb30e2f38309dull,
113 0xb41d4983bdbc8d6full,
114 0xba9f57c01b66b7e3ull,
115 0xe400503c95c16568ull,
116 0x5977bfd4630294f1ull,
117 0x57d4d7940099676full,
118 0xd945de9268f4b191ull,
119 0x4034711421eaf806ull,
120 0x6d8108a4a6d58c22ull,
121 0x5c421818ddbdd4eeull,
122 0xbd9b7e4071713c13ull,
123 0xa60d1d6e793e5eb2ull,
124 0x7443fb031b8ec6c7ull,
125 0xd8290c7120e05d4aull,
126 0x797fb1d9a6a8d27full,
127 0x543ec268ab1f2e45ull,
128 0xcaf2a6139701f320ull,
129 0x9519611d130bee47ull,
130 0x19bbc533f018be1aull,
131 0xdbfacdfeb573133dull,
132 0x3255dacc4c7bfe12ull,
133 0xbc6c9228e5518f6eull,
134 0xb5c1681037347178ull,
135 0xbaaa2cfef186bfadull,
136 0x1834b8ab0f9e876eull,
137 0x9d7b7f228433e0f7ull,
138 0xa99cc292d003dd09ull,
139 0xc0cb8037046b5295ull,
140 0xa6ffa3d4671aa3d2ull,
141 0xc27023fbee2862e6ull,
142 0x5a9877bcc4bd3172ull,
143 0xfcb0da3caf9fcfe0ull,
144 0xc35ef57e1866ceaeull,
145 0xd4f7c927d169a115ull,
146 0x699054518fc74756ull,
147 0xa75cbf617fc9db8dull,
148 0x7f3adf4369665a9cull,
149 0x6b98eeeb4c517f42ull,
150 0xa12e44f5de954f24ull,
151 0x5789ded4dced978eull,
152 0xe4dd20ed27cd3567ull,
153 0x9b4e90c365b8790bull,
154 0xd486ed6e099f499bull,
155 0x3f3d0ccfeaa0c0dcull,
156 0x548c746cdb192adaull,
157 0x8ce636d8469fe2dcull,
158 0xca59ec929549a6a1ull,
159 0x647b9878deaba1f0ull,
160 0xebbb4b2641c54d34ull,
161 0x7be6d2918b680abdull,
162 0x02ad265fb4733490ull,
163 0xfe1053044faf3486ull,
164 0x539ea358ff6b6df3ull,
165 0x025d73224a2b5826ull,
166 0x7daad302451f41b3ull,
167 0x6038455ddb535976ull,
168 0x8d6d00a9a728a067ull,
169 0xe9f03d61d4965d59ull,
170 0x38314b8102daff3bull,
171 0x56b335e7893a76f1ull,
172 0x1048ca2f415712abull,
173 0xa9bc989a891dc173ull,
174 0xb741df3ae02836c2ull,
175 0x7711e6c6f5830783ull,
176 0x8edbf2be9226e24bull,
177 0xe4a4b8ba310fc2e2ull,
178 0xbc7b67f4a02f23c8ull,
179 0x5669b1a9d6d8df17ull,
180 0xdd3ebf2e3c516e26ull,
181 0x77bdd6def5236c4full,
182 0x9aeb54bdffacd65eull,
183 0xab676483404a21b8ull,
184 0xf7270f77a9d1b3a3ull,
185 0x3794e1cdcc7de433ull,
186 0x8e2b74d3a06aa56aull,
187 0x572698d05b901d40ull,
188 0x7bd6c265c1dd5cdfull,
189 0xd2f68a53970db82eull,
190 0x0e1d5f5dd9bd23bdull,
191 0x48814c6813505051ull,
192 0x8f2d21a7d4e4a481ull,
193 0x144531c871920cf3ull,
194 0x45c6f81c7fbc3b2full,
195 0xc562f1fc7f07a944ull,
196 0xaabdf3d0aa9872e4ull,
197 0x8db1f9d827c8df98ull,
198 0xea787210e13c16c7ull,
199 0xd43f6f582629ff39ull,
200 0x6ec7599da4cb298dull,
201 0xfa99d7196097dd94ull,
202 0xbe3a8a172a62f40dull,
203 0x07477bc03d9d5471ull,
204 0x03777d1ee44c0fa6ull,
205 0x5c6df847b0ae6fd1ull,
206 0xc1fc3bc2352d8125ull,
207 0x6800e3321d35b697ull,
208 0x51cc735e1b0920a8ull,
209 0x93dc60a2430c11acull,
210 0x13b6bf8ffc4e9e30ull,
211 0xada08114e6a01701ull,
212 0x1459b7a4254da4cdull,
213 0xf7575cd7ededcdfdull,
214 0x1e43675ed5ed33eeull,
215 0x639f5ff579cc30d4ull,
216 0x8f4f75d7eea7e300ull,
217 0x518939accd43dadeull,
218 0x989a77577fac24e2ull,
219 0x86c5e3998c819d51ull,
220 0xb84770f9cc15d139ull,
221 0x11544010174c2c99ull,
222 0xfb238b962405a579ull,
223 0xca5bddde9b80cb7bull,
224 0xbbe71928190dfab4ull,
225 0x0ec620294742b8c8ull,
226 0x90bc7a703ed63900ull,
227 0x2c8a80e1e85f72bbull,
228 0xf19ab262ed2ad914ull,
229 0xa233e89fab33793cull,
230 0x75b6f59568a958f5ull,
231 0x31fb15af9a41aca2ull,
232 0xf89db05aa21b3d1cull,
233 0x0023d08c52147f63ull,
234 0x8e0e3c2aba81e8fdull,
235 0xdb2efd057c157e71ull,
236 0x1a1797a83e39dfe4ull,
237 0x3afc43e1979f507dull,
238 0x0e647a8d8abe0936ull,
239 0xc8e03f27082eb0daull,
240 0xc1b0c11db52da528ull,
241 0xadeb52a144f497ceull,
242 0x046fc2f53bd97c9bull,
243 0x2d587fdf5fae80d5ull,
244 0x14036c3fb77fd73eull,
245 0x883f768734d14676ull,
246 0x212df988a83caffeull,
247 0x36b41dac32387e17ull,
248 0x9dbee8d7cf804bccull,
249 0x34d9a58fb9a35794ull,
250 0xda82beba879e3576ull,
251 0x0366148280e5adf1ull,
252 0x634085dcdba7b174ull,
253 0x8451523252446534ull,
254 0xc74ce8b4d5175b9aull,
255 0x40afebd30a9a4837ull,
256 0x7232952ce84e90beull,
257 0x7443a6e37b87992dull,
258 0xace8a33649218d9aull,
259 0x9ad8af9614b75655ull,
260 0xd518d9a700179ac2ull,
261 0xc7f906d90fd36259ull,
262 0xe2c47ec3abd8a12dull,
263 0xca05e96fcbbb76c1ull,
264 0x7186661c9ddf4973ull,
265 0x0146f5f47d5f42c2ull,
266 0x74a7c485608ea178ull,
267 0x8cb5e3e5f84f3040ull,
268 0xb330869dc366037dull,
269 0x0dbc4d22f932bbd4ull,
270 0xa8460b43946a5ecbull,
271 0xcee72c72fe5ddea6ull,
272 0x9f953cc7859b2a4eull,
273 0x95ea396619e60182ull,
274 0xfe9890efa6aa8c3eull,
275 0x3c9a5691d1e25799ull,
276 0xa54eeb19aa718b62ull,
277 0x69907b2ec11d82b7ull,
278 0x408c5405984caa65ull,
279 0x6f11a21711640470ull,
280 0x20b9227a8f53f9aeull,
281 0x42df63b7ec442178ull,
282 0xbec247f79407d00aull,
283 0x2946c31558eab2bcull,
284 0x84d045ffa174048eull,
285 0x28bad532ba4a450cull,
286 0x93ccf0cbaa274d7aull,
287 0xff30008411d25158ull,
288 0x3845ce6dcc30080aull,
289 0xcf5925239b6f3dbaull,
290 0x1f148649ed53660dull};
297 static gs_int32_t nextrandom = 0;
298 static gs_int32_t endrandom = 100;
301 // The first "endrandom" numbers returned are truely random INT64.
302 // They are perfect for bases of new hash functions, and currently
303 // we have just enough such random numbers for tabulation based
304 // 5-universal hashing, or one of the other schemes provided.
305 // The remaining ones are based on the pseudo-random mrand48() which
306 // returns a signed 32-bit number. We do not use the unsigned lrand48()
307 // which only returns 31-bit.
308 inline static INT64 RandINT64() {
310 if (nextrandom<endrandom) r=Random64[nextrandom++];
312 // if (nextrandom==endrandom)
313 // fprintf(stderr,"Switching from random to pseudo-random in Rand64");
314 r =(INT64) mrand48();
315 r1 = (INT64) mrand48();
323 /* Computes ax+b mod Prime, possibly plus Prime,
324 exploiting the structure of Prime. */
325 inline static INT64 MultAddPrime(INT32 x, INT64 a, INT64 b) {
331 c = (c0&Prime61)+(c1>>29)+b;
335 /* CWtrick for 32-bit key x with prime 2^61-1 */
336 inline static INT64 Hash61bit5univ(INT32 x, Hash61bit5univID index) {
341 for (i=1;i<5;i++) h = MultAddPrime(x,h,index[i]);
342 h = (h&Prime61)+(h>>61);
343 if (h>=Prime61) h-=Prime61;
349 inline static INT64* InitHash61bit5univ() {
352 Hash61bit5univID hid = (INT64*) malloc(5*sizeof(INT64));
355 hid[i] = (hid[i]&Prime61)+(hid[i]>>61);
356 if (hid[i]>=Prime61) hid[i]-=Prime61;
361 inline static HashTab32bit5univID InitHashTab32bit5univ() {
363 HashTab32bit5univID htab;
364 Hash61bit5univID h61id;
367 htab = (HashTab32bit5univID) malloc(3*sizeof(INT32*));
369 htab[i] = (INT32*) malloc(65538*sizeof(INT32));
370 h61id = InitHash61bit5univ();
371 for (j=0;j<65538;j++) htab[i][j]=Hash61bit5univ(j,h61id);
376 /* tabulation based hashing for 32-bit key x using 16-bit characters.*/
377 inline INT64 HashTab32bit5univ(INT32 x, HashTab32bit5univID htab) {
382 x2 = 2 - (x2>>16) + (x2&65535); // optional compression
383 return htab[0][x0]^htab[1][x1]^htab[2][x2];
384 } // 8 + 4 = 12 instructions
387 /* Tabulation based hashing for 32-bit keys using 16-bit characters.*/
388 /* Uses 500KB tables and makes 2 lookups per hash. */
390 inline static HashTab32bitLPID InitHashShortTab32bitLP() {
392 HashTab32bitLPID htab;
393 Hash61bit5univID h61id;
396 htab = (HashTab32bitLPID) malloc(2*sizeof(INT32*));
398 htab[i] = (INT32*) malloc(65536*sizeof(INT32));
399 h61id = InitHash61bit5univ();
400 for (j=0;j<65536;j++) htab[i][j]=Hash61bit5univ(j,h61id);
405 /* tabulation based hashing for 32-bit key x using 16-bit characters.*/
406 inline INT64 HashShortTab32bitLP(INT32 x, HashTab32bitLPID htab) {
410 return htab[0][x0]^htab[1][x1];
414 /* Tabulation based hashing for 32-bit keys using 8-bit characters.*/
415 /* Uses 4KB tables and makes 4 lookups per hash. */
417 inline static HashTab32bitLPID InitHashCharTab32bitLP() {
419 HashTab32bitLPID htab;
420 Hash61bit5univID h61id;
423 htab = (HashTab32bitLPID) malloc(4*sizeof(INT32*));
425 htab[i] = (INT32*) malloc(256*sizeof(INT32));
426 h61id = InitHash61bit5univ();
427 for (j=0;j<256;j++) htab[i][j]=Hash61bit5univ(j,h61id);
432 inline INT32 HashCharTab32bitLP(INT32 x, HashTab32bitLPID htab) {
448 /* Tabulation based hashing for 64-bit keys using 16-bit characters.*/
449 /* Uses 2MB tables and makes 4 lookups per hash. */
452 inline static HashTab64bitLPID InitHashShortTab64bitLP() {
454 HashTab64bitLPID htab;
455 Hash61bit5univID h61id;
458 htab = (HashTab64bitLPID) malloc(4*sizeof(INT64*));
460 htab[i] = (INT64*) malloc(65536*sizeof(INT64));
461 h61id = InitHash61bit5univ();
462 for (j=0;j<65536;j++) htab[i][j]=Hash61bit5univ(j,h61id);
463 h61id = InitHash61bit5univ();
464 for (j=0;j<65536;j++) htab[i][j]+=Hash61bit5univ(j,h61id)<<32;
469 inline INT64 HashShortTab64bitLP(INT64 x, HashTab64bitLPID htab) {
484 /* Tabulation based hashing for 64-bit keys using 8-bit characters.*/
485 /* Uses 14KB tables and makes 8 lookups per hash. */
487 inline static HashTab64bitLPID InitHashCharTab64bitLP() {
489 HashTab64bitLPID htab;
490 Hash61bit5univID h61id;
493 htab = (HashTab64bitLPID) malloc(8*sizeof(INT64*));
495 htab[i] = (INT64*) malloc(256*sizeof(INT64));
496 h61id = InitHash61bit5univ();
497 for (j=0;j<256;j++) htab[i][j]=Hash61bit5univ(j,h61id);
498 h61id = InitHash61bit5univ();
499 for (j=0;j<256;j++) htab[i][j]+=Hash61bit5univ(j,h61id)<<32;
504 inline INT64 HashCharTab64bitLP(INT64 x, HashTab64bitLPID htab) {
520 /* Tabulation based hashing for 34-bit keys using 10-11-bit characters.*/
521 /* Uses 20KB tables and makes 3 lookups per hash. */
523 inline static HashTab32bitLPID InitHashMipTab32bitLP() {
525 HashTab32bitLPID htab;
526 Hash61bit5univID h61id;
529 htab = (HashTab32bitLPID) malloc(6*sizeof(INT32*));
531 htab[i] = (INT32*) malloc(0x800*sizeof(INT32));
532 h61id = InitHash61bit5univ();
533 for (j=0;j<0x800;j++) htab[i][j]=(INT32) Hash61bit5univ(j,h61id);
536 htab[i] = (INT32*) malloc(0x400*sizeof(INT32));
537 h61id = InitHash61bit5univ();
538 for (j=0;j<0x400;j++) htab[i][j]=(INT32) Hash61bit5univ(j,h61id);
543 inline INT32 HashMipTab32bitLP(INT32 x, HashTab32bitLPID htab) {
559 /* Tabulation based hashing for 64-bit keys using 10-11-bit characters.*/
560 /* Uses 80KB tables and makes 6 lookups per hash. */
562 inline static HashTab64bitLPID InitHashMipTab64bitLP() {
564 HashTab64bitLPID htab;
565 Hash61bit5univID h61id;
568 htab = (HashTab64bitLPID) malloc(6*sizeof(INT64*));
570 htab[i] = (INT64*) malloc(0x800*sizeof(INT64));
571 h61id = InitHash61bit5univ();
572 for (j=0;j<0x800;j++) htab[i][j]=Hash61bit5univ(j,h61id);
573 h61id = InitHash61bit5univ();
574 for (j=0;j<0x800;j++) htab[i][j]+=Hash61bit5univ(j,h61id)<<32;
577 htab[i] = (INT64*) malloc(0x400*sizeof(INT64));
578 h61id = InitHash61bit5univ();
579 for (j=0;j<0x400;j++) htab[i][j]=Hash61bit5univ(j,h61id);
580 h61id = InitHash61bit5univ();
581 for (j=0;j<0x400;j++) htab[i][j]+=Hash61bit5univ(j,h61id)<<32;
586 inline INT64 HashMipTab64bitLP(INT64 x, HashTab64bitLPID htab) {
607 inline static Hash32bit2univID InitHash32bit2univ() {
608 Hash32bit2univID hid = (INT64*) malloc(2*sizeof(INT64));
614 inline INT32 Hash32bit2univ(INT32 x, Hash32bit2univID hid) {
617 H = (x*hid[0])+hid[1];
623 // For the string hashing below is for string of 32bit integers, and
624 // the output is a 2-universal 32-bit number.
626 inline static Hash32bit2univID InitStringHash32bit2univ(gs_int32_t length) {
628 Hash32bit2univID hid = (INT64*) malloc((length+1)*sizeof(INT64));
629 for (i=0;i<=length;i++) hid[i]=RandINT64();
634 // ---------------------------------------------
635 // Mikkel's string hashing code, 250M hashes/sec
637 //assumes string length even
638 inline INT32 EvenStringHash32bit2univ(INT32 * x, gs_int32_t length,
639 Hash32bit2univID hid) {
646 for (i=0;i<length;i+=2) {
657 //assumes string length odd
658 inline INT32 OddStringHash32bit2univ(INT32 * x, gs_int32_t length,
659 Hash32bit2univID hid) {
666 for (i=1;i<length;i+=2) {
677 //Below we have the generic algorithm for fixed length string hashing
678 //For shorter strings of length < 6, it is worthwhile using
679 //specialized versions with fewer tests.
680 //All versions rely on the some initialization above.
681 inline INT32 StringHash32bit2univ(INT32 * x, gs_int32_t length, Hash32bit2univID hid) {
685 // for (i=0;i<length;i++) H = H^(x[i]*hid[i]);
689 if (length&1) return OddStringHash32bit2univ(x,length,hid);
690 else return EvenStringHash32bit2univ(x,length,hid);
693 // ---------------------------------------------
695 // ---------------------------------------------
696 // modification to Mikkel's string hashing code
697 // Return the full 64 bits ... low order bits are not random
698 // but we can squeeze a few more bits out.
700 //assumes string length even
701 inline INT64 EvenStringHash64bit(INT32 * x, gs_int32_t length,
702 Hash32bit2univID hid) {
708 for (i=0;i<length;i+=2) {
718 //assumes string length odd
719 inline INT64 OddStringHash64bit(INT32 * x, gs_int32_t length,
720 Hash32bit2univID hid) {
726 for (i=1;i<length;i+=2) {
736 //Below we have the generic algorithm for fixed length string hashing
737 //For shorter strings of length < 6, it is worthwhile using
738 //specialized versions with fewer tests.
739 //All versions rely on the some initialization above.
740 inline INT64 StringHash64bit(INT32 * x, gs_int32_t length, Hash32bit2univID hid) {
744 // for (i=0;i<length;i++) H = H^(x[i]*hid[i]);
748 if (length&1) return OddStringHash64bit(x,length,hid);
749 else return EvenStringHash64bit(x,length,hid);
752 // ---------------------------------------------
757 inline INT32 String2Hash32bit2univ(INT32 * x,Hash32bit2univID hid) {
771 inline INT32 String3Hash32bit2univ(INT32 * x,Hash32bit2univID hid) {
787 inline static VarINT32StringHash32bit2univID InitVarINT32StringHash32bitUniv() {
789 VarINT32StringHash32bit2univID hid;
791 hid = (VarINT32StringHash32bit2univID) malloc(sizeof(VISHID));
792 for (i=0;i<16;i++) hid->str_compr_hid[i]=RandINT64();
793 hid->string_hid = RandINT64() & Prime61;
794 // hid->last_compr_hid = RandINT64() | 0x1ull;
798 inline INT32 VarINT32StringHash32bitUniv(INT32 * x, gs_int32_t length, VarINT32StringHash32bit2univID hid) {
804 INT64 HxM00,HxM01,HxM10,HxM11,C0,C1,C2,CC;
806 if (length<16) return StringHash32bit2univ(x,length,hid->str_compr_hid);
815 C = x[i]*hid->str_compr_hid[j];
819 for (e=((int) (d>>1));e>0;e--) {
820 xh1=x[i]+hid->str_compr_hid[j+1];
821 xh2=x[i+1]+hid->str_compr_hid[j];
827 if (i==(INT32) length) {
830 H+=((INT64) length)*hid->length_factor;
837 //Multiply H*M mod Prime61, possibly plus Prime,
838 //exploiting the structure of Prime61.
839 //We assume H<2*Prime61 and M<=Prime61, e.g.,
841 HxM00 = LOW(H)*LOW(M);
842 HxM01 = LOW(H)*HIGH(M);
843 HxM10 = HIGH(H)*LOW(M);
844 HxM11 = HIGH(H)*HIGH(M); //has at most 60 bits
845 C0 = HxM00+(HxM01<<32)+(HxM10<<32);//overflow doesn't matter here.
846 C0 = C0&Prime61; //Has at most 61 bits.
847 C1 = (HxM00>>32)+HxM01+HxM10; //Overflow impossible each <=62 bits
848 C1 = C1>>29; //Has at most 33 bits.
849 C2 = HxM11<<3; //Has at most 123-64+3=62 bits.
850 CC = C0+C1+C2; //At most 63 bits.
851 H = (CC&Prime61)+(CC>>61); //<2*Prime
855 inline static VarStringHash32bit2univID InitVarStringHash32bitUniv() {
857 VarStringHash32bit2univID hid;
859 hid = (VarStringHash32bit2univID) malloc(sizeof(VSHID));
862 hid->str_compr_hid[i]=RandINT64();
864 hid->string_hid = RandINT64() & Prime61;
865 // hid->last_compr_hid = RandINT64() | 0x1ull;
869 inline INT32 VarStringHash32bitUniv(char * x, gs_int32_t length,
870 VarStringHash32bit2univID hid) {
872 INT32 h,i,l,d,str_ix;
875 INT64 HxM00,HxM01,HxM10,HxM11,C0,C1,C2,CC;
877 // Assumes hid->int_str[*]==0
880 memcpy(hid->int_str,x,length);
881 d=(length+3)>>2; //<16
882 h=StringHash32bit2univ(hid->int_str,d,hid->str_compr_hid);
883 for (i=0;i<d;i++) hid->int_str[i]=0;
892 memcpy(hid->int_str,x+str_ix,l);
897 C = hid->int_str[i]*hid->str_compr_hid[i];
901 xh1=hid->int_str[i]+hid->str_compr_hid[i+1];
902 xh2=hid->int_str[i+1]+hid->str_compr_hid[i];
907 for (i=0;i<d;i++) hid->int_str[i]=0;
908 if (str_ix==(INT32) length) {
911 H+=((INT64) length)*hid->length_factor;
918 //Multiply H*M mod Prime61, possibly plus Prime,
919 //exploiting the structure of Prime61.
920 //We assume H<2*Prime61 and M<=Prime61, e.g.,
922 HxM00 = LOW(H)*LOW(M);
923 HxM01 = LOW(H)*HIGH(M);
924 HxM10 = HIGH(H)*LOW(M);
925 HxM11 = HIGH(H)*HIGH(M); //has at most 60 bits
926 C0 = HxM00+(HxM01<<32)+(HxM10<<32);//overflow doesn't matter here.
927 C0 = C0&Prime61; //Has at most 61 bits.
928 C1 = (HxM00>>32)+HxM01+HxM10; //Overflow impossible each <=62 bits
929 C1 = C1>>29; //Has at most 33 bits.
930 C2 = HxM11<<3; //Has at most 123-64+3=62 bits.
931 CC = C0+C1+C2; //At most 63 bits.
932 H = (CC&Prime61)+(CC>>61); //<2*Prime