-/* ------------------------------------------------
-Copyright 2014 AT&T Intellectual Property
- Licensed under the Apache License, Version 2.0 (the "License");
- you may not use this file except in compliance with the License.
- You may obtain a copy of the License at
-
- http://www.apache.org/licenses/LICENSE-2.0
-
- Unless required by applicable law or agreed to in writing, software
- distributed under the License is distributed on an "AS IS" BASIS,
- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- See the License for the specific language governing permissions and
- limitations under the License.
- ------------------------------------------- */
-
-#ifndef _STRINGHASH_H
-#define _STRINGHASH_H
-#include <stdlib.h>
-#include <stdio.h>
-#include <limits.h>
-#include <stdint.h>
-#include <string.h>
-
-//Provides 5-universal hash functions.
-//Both a direct polynomial based one,
-//and the much faster tabulation based one.
-//
-//It also provides 2-universal string hashing.
-//For most applicatoins, introdcing a slight error,
-//if you want almost 5-uninversal hashing for strings,
-//you can do a 2-universal hashing into 32-bit integer
-//getting very few collissoins, and then use the above
-//5-universal one.
-
-
-
-typedef gs_uint8_t INT8;
-typedef gs_uint16_t INT16;
-typedef gs_uint32_t INT32;
-typedef gs_uint64_t INT64;
-
-typedef INT64 * Hash61bit5univID;
-typedef INT32** HashTab32bit5univID;
-typedef INT32** HashTab32bitLPID;
-typedef INT64** HashTab64bitLPID;
-typedef INT64 * Hash32bit2univID;
-typedef INT32 Hash32bitUnivID;
-
-const INT32 MAX_INT32 = UINT_MAX;
-
-typedef struct {
- INT64 str_compr_hid[16];
- INT64 string_hid;
- INT64 length_factor;
- // INT64 last_compr_hid;
-} VISHID;
-
-typedef VISHID * VarINT32StringHash32bit2univID;
-
-
-typedef struct {
- INT32 int_str[16];
- INT64 str_compr_hid[16];
- INT64 string_hid;
- INT64 length_factor;
- // INT64 last_compr_hid;
-} VSHID;
-
-typedef VSHID * VarStringHash32bit2univID;
-
-
-
-
-
-// different views of a 64-bit double word
-typedef union {
- INT64 as_int64;
- INT32 as_int32s[2];
- INT16 as_int16s[4];
-} int64views;
-
-const INT64 LowOnes = (((INT64)1)<<32)-1;
-
-#define LOW(x) ((x)&LowOnes) // extract lower 32 bits from INT64
-#define HIGH(x) ((x)>>32) // extract higher 32 bits from INT64
-
-const INT64 Prime61 = (((INT64)1)<<61) - 1;
-
-
-//Random numbers from random.org based on atmostpheric noise.
-INT64 Random64[200]= {0x285eb7722a62ce6eull,
- 0xa84c7463e2b7856bull,
- 0xb29100d6abcc8666ull,
- 0xf9bfca5b7461fb1full,
- 0x51c8dafc30c88dadull,
- 0x0687468c365ec51dull,
- 0x2bf2cd3ad64b6218ull,
- 0xc20565a4d1f00f9eull,
- 0x7d533575d313c658ull,
- 0xbf2fba6b00725b85ull,
- 0x4cfc2f6557e722beull,
- 0xedbce818556dfb2bull,
- 0xd9df508027db1bbeull,
- 0x21f2d922f712f48bull,
- 0xcd8b289d83a65804ull,
- 0x4a19cfb02445a6d2ull,
- 0xc95e56b1e19a4f94ull,
- 0xcfeeeaccaf477248ull,
- 0x4eec3378b73bb25cull,
- 0x18a3f38d1c48b2beull,
- 0x71b79ab5cb1e3730ull,
- 0x79cdb30e2f38309dull,
- 0xb41d4983bdbc8d6full,
- 0xba9f57c01b66b7e3ull,
- 0xe400503c95c16568ull,
- 0x5977bfd4630294f1ull,
- 0x57d4d7940099676full,
- 0xd945de9268f4b191ull,
- 0x4034711421eaf806ull,
- 0x6d8108a4a6d58c22ull,
- 0x5c421818ddbdd4eeull,
- 0xbd9b7e4071713c13ull,
- 0xa60d1d6e793e5eb2ull,
- 0x7443fb031b8ec6c7ull,
- 0xd8290c7120e05d4aull,
- 0x797fb1d9a6a8d27full,
- 0x543ec268ab1f2e45ull,
- 0xcaf2a6139701f320ull,
- 0x9519611d130bee47ull,
- 0x19bbc533f018be1aull,
- 0xdbfacdfeb573133dull,
- 0x3255dacc4c7bfe12ull,
- 0xbc6c9228e5518f6eull,
- 0xb5c1681037347178ull,
- 0xbaaa2cfef186bfadull,
- 0x1834b8ab0f9e876eull,
- 0x9d7b7f228433e0f7ull,
- 0xa99cc292d003dd09ull,
- 0xc0cb8037046b5295ull,
- 0xa6ffa3d4671aa3d2ull,
- 0xc27023fbee2862e6ull,
- 0x5a9877bcc4bd3172ull,
- 0xfcb0da3caf9fcfe0ull,
- 0xc35ef57e1866ceaeull,
- 0xd4f7c927d169a115ull,
- 0x699054518fc74756ull,
- 0xa75cbf617fc9db8dull,
- 0x7f3adf4369665a9cull,
- 0x6b98eeeb4c517f42ull,
- 0xa12e44f5de954f24ull,
- 0x5789ded4dced978eull,
- 0xe4dd20ed27cd3567ull,
- 0x9b4e90c365b8790bull,
- 0xd486ed6e099f499bull,
- 0x3f3d0ccfeaa0c0dcull,
- 0x548c746cdb192adaull,
- 0x8ce636d8469fe2dcull,
- 0xca59ec929549a6a1ull,
- 0x647b9878deaba1f0ull,
- 0xebbb4b2641c54d34ull,
- 0x7be6d2918b680abdull,
- 0x02ad265fb4733490ull,
- 0xfe1053044faf3486ull,
- 0x539ea358ff6b6df3ull,
- 0x025d73224a2b5826ull,
- 0x7daad302451f41b3ull,
- 0x6038455ddb535976ull,
- 0x8d6d00a9a728a067ull,
- 0xe9f03d61d4965d59ull,
- 0x38314b8102daff3bull,
- 0x56b335e7893a76f1ull,
- 0x1048ca2f415712abull,
- 0xa9bc989a891dc173ull,
- 0xb741df3ae02836c2ull,
- 0x7711e6c6f5830783ull,
- 0x8edbf2be9226e24bull,
- 0xe4a4b8ba310fc2e2ull,
- 0xbc7b67f4a02f23c8ull,
- 0x5669b1a9d6d8df17ull,
- 0xdd3ebf2e3c516e26ull,
- 0x77bdd6def5236c4full,
- 0x9aeb54bdffacd65eull,
- 0xab676483404a21b8ull,
- 0xf7270f77a9d1b3a3ull,
- 0x3794e1cdcc7de433ull,
- 0x8e2b74d3a06aa56aull,
- 0x572698d05b901d40ull,
- 0x7bd6c265c1dd5cdfull,
- 0xd2f68a53970db82eull,
- 0x0e1d5f5dd9bd23bdull,
- 0x48814c6813505051ull,
- 0x8f2d21a7d4e4a481ull,
- 0x144531c871920cf3ull,
- 0x45c6f81c7fbc3b2full,
- 0xc562f1fc7f07a944ull,
- 0xaabdf3d0aa9872e4ull,
- 0x8db1f9d827c8df98ull,
- 0xea787210e13c16c7ull,
- 0xd43f6f582629ff39ull,
- 0x6ec7599da4cb298dull,
- 0xfa99d7196097dd94ull,
- 0xbe3a8a172a62f40dull,
- 0x07477bc03d9d5471ull,
- 0x03777d1ee44c0fa6ull,
- 0x5c6df847b0ae6fd1ull,
- 0xc1fc3bc2352d8125ull,
- 0x6800e3321d35b697ull,
- 0x51cc735e1b0920a8ull,
- 0x93dc60a2430c11acull,
- 0x13b6bf8ffc4e9e30ull,
- 0xada08114e6a01701ull,
- 0x1459b7a4254da4cdull,
- 0xf7575cd7ededcdfdull,
- 0x1e43675ed5ed33eeull,
- 0x639f5ff579cc30d4ull,
- 0x8f4f75d7eea7e300ull,
- 0x518939accd43dadeull,
- 0x989a77577fac24e2ull,
- 0x86c5e3998c819d51ull,
- 0xb84770f9cc15d139ull,
- 0x11544010174c2c99ull,
- 0xfb238b962405a579ull,
- 0xca5bddde9b80cb7bull,
- 0xbbe71928190dfab4ull,
- 0x0ec620294742b8c8ull,
- 0x90bc7a703ed63900ull,
- 0x2c8a80e1e85f72bbull,
- 0xf19ab262ed2ad914ull,
- 0xa233e89fab33793cull,
- 0x75b6f59568a958f5ull,
- 0x31fb15af9a41aca2ull,
- 0xf89db05aa21b3d1cull,
- 0x0023d08c52147f63ull,
- 0x8e0e3c2aba81e8fdull,
- 0xdb2efd057c157e71ull,
- 0x1a1797a83e39dfe4ull,
- 0x3afc43e1979f507dull,
- 0x0e647a8d8abe0936ull,
- 0xc8e03f27082eb0daull,
- 0xc1b0c11db52da528ull,
- 0xadeb52a144f497ceull,
- 0x046fc2f53bd97c9bull,
- 0x2d587fdf5fae80d5ull,
- 0x14036c3fb77fd73eull,
- 0x883f768734d14676ull,
- 0x212df988a83caffeull,
- 0x36b41dac32387e17ull,
- 0x9dbee8d7cf804bccull,
- 0x34d9a58fb9a35794ull,
- 0xda82beba879e3576ull,
- 0x0366148280e5adf1ull,
- 0x634085dcdba7b174ull,
- 0x8451523252446534ull,
- 0xc74ce8b4d5175b9aull,
- 0x40afebd30a9a4837ull,
- 0x7232952ce84e90beull,
- 0x7443a6e37b87992dull,
- 0xace8a33649218d9aull,
- 0x9ad8af9614b75655ull,
- 0xd518d9a700179ac2ull,
- 0xc7f906d90fd36259ull,
- 0xe2c47ec3abd8a12dull,
- 0xca05e96fcbbb76c1ull,
- 0x7186661c9ddf4973ull,
- 0x0146f5f47d5f42c2ull,
- 0x74a7c485608ea178ull,
- 0x8cb5e3e5f84f3040ull,
- 0xb330869dc366037dull,
- 0x0dbc4d22f932bbd4ull,
- 0xa8460b43946a5ecbull,
- 0xcee72c72fe5ddea6ull,
- 0x9f953cc7859b2a4eull,
- 0x95ea396619e60182ull,
- 0xfe9890efa6aa8c3eull,
- 0x3c9a5691d1e25799ull,
- 0xa54eeb19aa718b62ull,
- 0x69907b2ec11d82b7ull,
- 0x408c5405984caa65ull,
- 0x6f11a21711640470ull,
- 0x20b9227a8f53f9aeull,
- 0x42df63b7ec442178ull,
- 0xbec247f79407d00aull,
- 0x2946c31558eab2bcull,
- 0x84d045ffa174048eull,
- 0x28bad532ba4a450cull,
- 0x93ccf0cbaa274d7aull,
- 0xff30008411d25158ull,
- 0x3845ce6dcc30080aull,
- 0xcf5925239b6f3dbaull,
- 0x1f148649ed53660dull};
-
-
-
-
-
-
-gs_int32_t nextrandom = 0;
-gs_int32_t endrandom = 100;
-
-
-// The first "endrandom" numbers returned are truely random INT64.
-// They are perfect for bases of new hash functions, and currently
-// we have just enough such random numbers for tabulation based
-// 5-universal hashing, or one of the other schemes provided.
-// The remaining ones are based on the pseudo-random mrand48() which
-// returns a signed 32-bit number. We do not use the unsigned lrand48()
-// which only returns 31-bit.
-inline static INT64 RandINT64() {
- INT64 r,r1;
- if (nextrandom<endrandom) r=Random64[nextrandom++];
- else {
- if (nextrandom==endrandom)
- fprintf(stderr,"Switching from random to pseudo-random in Rand64");
- r =(INT64) mrand48();
- r1 = (INT64) mrand48();
- r=r<<32;
- r=r^r1;
- }
- return r;
-}
-
-
-/* Computes ax+b mod Prime, possibly plus Prime,
- exploiting the structure of Prime. */
-inline static INT64 MultAddPrime(INT32 x, INT64 a, INT64 b) {
- INT64 a0,a1,c0,c1,c;
- a0 = LOW(a)*x;
- a1 = HIGH(a)*x;
- c0 = a0+(a1<<32);
- c1 = (a0>>32)+a1;
- c = (c0&Prime61)+(c1>>29)+b;
- return c;
-} // 12 instructions
-
-/* CWtrick for 32-bit key x with prime 2^61-1 */
-inline static INT64 Hash61bit5univ(INT32 x, Hash61bit5univID index) {
- INT64 h;
- gs_int32_t i;
-
- h = index[0];
- for (i=1;i<5;i++) h = MultAddPrime(x,h,index[i]);
- h = (h&Prime61)+(h>>61);
- if (h>=Prime61) h-=Prime61;
- return h;
-}
-
-
-
-inline static INT64* InitHash61bit5univ() {
- gs_int32_t i;
-
- Hash61bit5univID hid = (INT64*) malloc(5*sizeof(INT64));
- for (i=0;i<5;i++) {
- hid[i]=RandINT64();
- hid[i] = (hid[i]&Prime61)+(hid[i]>>61);
- if (hid[i]>=Prime61) hid[i]-=Prime61;
- }
- return hid;
-}
-
-inline static HashTab32bit5univID InitHashTab32bit5univ() {
- gs_uint32_t i,j;
- HashTab32bit5univID htab;
- Hash61bit5univID h61id;
-
-
- htab = (HashTab32bit5univID) malloc(3*sizeof(INT32*));
- for (i=0;i<3;i++) {
- htab[i] = (INT32*) malloc(65538*sizeof(INT32));
- h61id = InitHash61bit5univ();
- for (j=0;j<65538;j++) htab[i][j]=Hash61bit5univ(j,h61id);
- }
- return htab;
-}
-
-/* tabulation based hashing for 32-bit key x using 16-bit characters.*/
-inline INT64 HashTab32bit5univ(INT32 x, HashTab32bit5univID htab) {
- INT32 x0, x1, x2;
- x0 = x&65535;
- x1 = x>>16;
- x2 = x0 + x1;
- x2 = 2 - (x2>>16) + (x2&65535); // optional compression
- return htab[0][x0]^htab[1][x1]^htab[2][x2];
-} // 8 + 4 = 12 instructions
-
-
-/* Tabulation based hashing for 32-bit keys using 16-bit characters.*/
-/* Uses 500KB tables and makes 2 lookups per hash. */
-
-inline static HashTab32bitLPID InitHashShortTab32bitLP() {
- gs_uint32_t i,j;
- HashTab32bitLPID htab;
- Hash61bit5univID h61id;
-
-
- htab = (HashTab32bitLPID) malloc(2*sizeof(INT32*));
- for (i=0;i<2;i++) {
- htab[i] = (INT32*) malloc(65536*sizeof(INT32));
- h61id = InitHash61bit5univ();
- for (j=0;j<65536;j++) htab[i][j]=Hash61bit5univ(j,h61id);
- }
- return htab;
-}
-
-/* tabulation based hashing for 32-bit key x using 16-bit characters.*/
-inline INT64 HashShortTab32bitLP(INT32 x, HashTab32bitLPID htab) {
- INT32 x0, x1;
- x0 = x&65535;
- x1 = x>>16;
- return htab[0][x0]^htab[1][x1];
-}
-
-
-/* Tabulation based hashing for 32-bit keys using 8-bit characters.*/
-/* Uses 4KB tables and makes 4 lookups per hash. */
-
-inline static HashTab32bitLPID InitHashCharTab32bitLP() {
- gs_uint32_t i,j;
- HashTab32bitLPID htab;
- Hash61bit5univID h61id;
-
-
- htab = (HashTab32bitLPID) malloc(4*sizeof(INT32*));
- for (i=0;i<4;i++) {
- htab[i] = (INT32*) malloc(256*sizeof(INT32));
- h61id = InitHash61bit5univ();
- for (j=0;j<256;j++) htab[i][j]=Hash61bit5univ(j,h61id);
- }
- return htab;
-}
-
-inline INT32 HashCharTab32bitLP(INT32 x, HashTab32bitLPID htab) {
- INT8 c;
- INT32 h;
- gs_int32_t i;
-
- c=x;
- h=htab[0][c];
- for (i=1;i<4;i++) {
- x>>=8;
- c=x;
- h=h^htab[i][c];
- }
- return h;
-}
-
-
-/* Tabulation based hashing for 64-bit keys using 16-bit characters.*/
-/* Uses 2MB tables and makes 4 lookups per hash. */
-
-
-inline static HashTab64bitLPID InitHashShortTab64bitLP() {
- gs_int32_t i,j;
- HashTab64bitLPID htab;
- Hash61bit5univID h61id;
-
-
- htab = (HashTab64bitLPID) malloc(4*sizeof(INT64*));
- for (i=0;i<4;i++) {
- htab[i] = (INT64*) malloc(65536*sizeof(INT64));
- h61id = InitHash61bit5univ();
- for (j=0;j<65536;j++) htab[i][j]=Hash61bit5univ(j,h61id);
- h61id = InitHash61bit5univ();
- for (j=0;j<65536;j++) htab[i][j]+=Hash61bit5univ(j,h61id)<<32;
- }
- return htab;
-}
-
-inline INT64 HashShortTab64bitLP(INT64 x, HashTab64bitLPID htab) {
- INT16 c;
- INT64 h;
- gs_int32_t i;
-
- c=x;
- h=htab[0][c];
- for (i=1;i<4;i++) {
- x>>=16;
- c=x;
- h=h^htab[i][c];
- }
- return h;
-}
-
-/* Tabulation based hashing for 64-bit keys using 8-bit characters.*/
-/* Uses 14KB tables and makes 8 lookups per hash. */
-
-inline static HashTab64bitLPID InitHashCharTab64bitLP() {
- gs_int32_t i,j;
- HashTab64bitLPID htab;
- Hash61bit5univID h61id;
-
-
- htab = (HashTab64bitLPID) malloc(8*sizeof(INT64*));
- for (i=0;i<8;i++) {
- htab[i] = (INT64*) malloc(256*sizeof(INT64));
- h61id = InitHash61bit5univ();
- for (j=0;j<256;j++) htab[i][j]=Hash61bit5univ(j,h61id);
- h61id = InitHash61bit5univ();
- for (j=0;j<256;j++) htab[i][j]+=Hash61bit5univ(j,h61id)<<32;
- }
- return htab;
-}
-
-inline INT64 HashCharTab64bitLP(INT64 x, HashTab64bitLPID htab) {
- INT8 c;
- INT64 h;
- gs_int32_t i;
-
- c=x;
- h=htab[0][c];
- for (i=1;i<8;i++) {
- x>>=8;
- c=x;
- h=h^htab[i][c];
- }
- return h;
-}
-
-
-/* Tabulation based hashing for 34-bit keys using 10-11-bit characters.*/
-/* Uses 20KB tables and makes 3 lookups per hash. */
-
-inline static HashTab32bitLPID InitHashMipTab32bitLP() {
- gs_int32_t i,j;
- HashTab32bitLPID htab;
- Hash61bit5univID h61id;
-
-
- htab = (HashTab32bitLPID) malloc(6*sizeof(INT32*));
- for (i=0;i<2;i++) {
- htab[i] = (INT32*) malloc(0x800*sizeof(INT32));
- h61id = InitHash61bit5univ();
- for (j=0;j<0x800;j++) htab[i][j]=(INT32) Hash61bit5univ(j,h61id);
- }
- for (i=2;i<3;i++) {
- htab[i] = (INT32*) malloc(0x400*sizeof(INT32));
- h61id = InitHash61bit5univ();
- for (j=0;j<0x400;j++) htab[i][j]=(INT32) Hash61bit5univ(j,h61id);
- }
- return htab;
-}
-
-inline INT32 HashMipTab32bitLP(INT32 x, HashTab32bitLPID htab) {
- INT32 c;
- INT32 h;
- gs_int32_t i;
-
- h=0;
- for (i=0;i<2;i++) {
- c= x & 0x7FFull;
- h=h^htab[i][c];
- x>>=11;
- }
- c= x & 0x3FFull;
- h=h^htab[2][c];
- return h;
-}
-
-/* Tabulation based hashing for 64-bit keys using 10-11-bit characters.*/
-/* Uses 80KB tables and makes 6 lookups per hash. */
-
-inline static HashTab64bitLPID InitHashMipTab64bitLP() {
- gs_int32_t i,j;
- HashTab64bitLPID htab;
- Hash61bit5univID h61id;
-
-
- htab = (HashTab64bitLPID) malloc(6*sizeof(INT64*));
- for (i=0;i<4;i++) {
- htab[i] = (INT64*) malloc(0x800*sizeof(INT64));
- h61id = InitHash61bit5univ();
- for (j=0;j<0x800;j++) htab[i][j]=Hash61bit5univ(j,h61id);
- h61id = InitHash61bit5univ();
- for (j=0;j<0x800;j++) htab[i][j]+=Hash61bit5univ(j,h61id)<<32;
- }
- for (i=4;i<6;i++) {
- htab[i] = (INT64*) malloc(0x400*sizeof(INT64));
- h61id = InitHash61bit5univ();
- for (j=0;j<0x400;j++) htab[i][j]=Hash61bit5univ(j,h61id);
- h61id = InitHash61bit5univ();
- for (j=0;j<0x400;j++) htab[i][j]+=Hash61bit5univ(j,h61id)<<32;
- }
- return htab;
-}
-
-inline INT64 HashMipTab64bitLP(INT64 x, HashTab64bitLPID htab) {
- INT64 c;
- INT64 h;
- gs_int32_t i;
-
- h=0;
- for (i=0;i<4;i++) {
- c= x & 0x7FFull;
- h=h^htab[i][c];
- x>>=11;
- }
- for (i=4;i<6;i++) {
- c= x & 0x3FFull;
- h=h^htab[i][c];
- x>>=10;
- }
- return h;
-}
-
-
-
-inline static Hash32bit2univID InitHash32bit2univ() {
- Hash32bit2univID hid = (INT64*) malloc(2*sizeof(INT64));
- hid[0]=RandINT64();
- hid[1]=RandINT64();
- return hid;
-}
-
-inline INT32 Hash32bit2univ(INT32 x, Hash32bit2univID hid) {
- INT64 H;
- INT32 h;
- H = (x*hid[0])+hid[1];
- h = H >> 32;
- return h;
-}
-
-
-// For the string hashing below is for string of 32bit integers, and
-// the output is a 2-universal 32-bit number.
-
-inline static Hash32bit2univID InitStringHash32bit2univ(gs_int32_t length) {
- gs_int32_t i;
- Hash32bit2univID hid = (INT64*) malloc((length+1)*sizeof(INT64));
- for (i=0;i<=length;i++) hid[i]=RandINT64();
- return hid;
-}
-
-
-
-//assumes string length even
-inline INT32 EvenStringHash32bit2univ(INT32 * x, gs_int32_t length,
- Hash32bit2univID hid) {
- gs_int32_t i;
- INT64 H;
- INT32 h;
- INT64 xh1,xh2,y;
-
- H=0;
- for (i=0;i<length;i+=2) {
- xh1=x[i]+hid[i+1];
- xh2=x[i+1]+hid[i];
- y=xh1*xh2;
- H = H^y;
- }
- H=H^hid[length];
- h = H >> 32;
- return h;
-}
-
-//assumes string length odd
-inline INT32 OddStringHash32bit2univ(INT32 * x, gs_int32_t length,
- Hash32bit2univID hid) {
- gs_int32_t i;
- INT64 H;
- INT32 h;
- INT64 xh1,xh2,y;
-
- H = x[0]*hid[0];
- for (i=1;i<length;i+=2) {
- xh1=x[i]+hid[i+1];
- xh2=x[i+1]+hid[i];
- y=xh1*xh2;
- H = H^y;
- }
- H=H^hid[length];
- h = H >> 32;
- return h;
-}
-
-//Below we have the generic algorithm for fixed length string hashing
-//For shorter strings of length < 6, it is worthwhile using
-//specialized versions with fewer tests.
-//All versions rely on the some initialization above.
-inline INT32 StringHash32bit2univ(INT32 * x, gs_int32_t length, Hash32bit2univID hid) {
-// gs_int32_t i;
-// INT64 H=0;
-// INT32 h;
-// for (i=0;i<length;i++) H = H^(x[i]*hid[i]);
-// H=H^hid[length];
-// h = H >> 32;
-// return h;
- if (length&1) return OddStringHash32bit2univ(x,length,hid);
- else return EvenStringHash32bit2univ(x,length,hid);
-}
-
-
-//string of length 2
-inline INT32 String2Hash32bit2univ(INT32 * x,Hash32bit2univID hid) {
- INT64 H;
- INT32 h;
- INT64 xh1,xh2;
-
- xh1=x[0]+hid[1];
- xh2=x[1]+hid[0];
- H=xh1*xh2;
- H=H^hid[2];
- h = H >> 32;
- return h;
-}
-
-//string of length 3
-inline INT32 String3Hash32bit2univ(INT32 * x,Hash32bit2univID hid) {
- INT64 H;
- INT32 h;
- INT64 xh1,xh2,y;
-
- H = x[0]*hid[0];
- xh1=x[1]+hid[2];
- xh2=x[2]+hid[1];
- y=xh1*xh2;
- H = H^y;
- H=H^hid[3];
- h = H >> 32;
- return h;
-}
-
-
-inline static VarINT32StringHash32bit2univID InitVarINT32StringHash32bitUniv() {
- gs_int32_t i;
- VarINT32StringHash32bit2univID hid;
-
- hid = (VarINT32StringHash32bit2univID) malloc(sizeof(VISHID));
- for (i=0;i<16;i++) hid->str_compr_hid[i]=RandINT64();
- hid->string_hid = RandINT64() & Prime61;
- // hid->last_compr_hid = RandINT64() | 0x1ull;
- return hid;
- }
-
-inline INT32 VarINT32StringHash32bitUniv(INT32 * x, gs_int32_t length, VarINT32StringHash32bit2univID hid) {
-
- INT32 h,i,j,d;
- gs_int32_t e;
- INT64 C,H,M;
- INT64 xh1,xh2,y;
- INT64 HxM00,HxM01,HxM10,HxM11,C0,C1,C2,CC;
-
- if (length<16) return StringHash32bit2univ(x,length,hid->str_compr_hid);
- H=0;
- i=0;
- for (;;) {
- d=length-i;
- C = 0;
- j=0;
- if (d>16) d=16;
- else if (d&1) {
- C = x[i]*hid->str_compr_hid[j];
- i++;
- j++;
- }
- for (e=((int) (d>>1));e>0;e--) {
- xh1=x[i]+hid->str_compr_hid[j+1];
- xh2=x[i+1]+hid->str_compr_hid[j];
- y=xh1*xh2;
- C = C^y;
- i+=2;
- j+=2;
- }
- if (i==(INT32) length) {
- H<<=4;
- H+=C;
- H+=((INT64) length)*hid->length_factor;
- h=(H>>32);
- return h;
- }
- C>>=4;
- H+=C;
- M=hid->string_hid;
- //Multiply H*M mod Prime61, possibly plus Prime,
- //exploiting the structure of Prime61.
- //We assume H<2*Prime61 and M<=Prime61, e.g.,
- //H*M <2^123.
- HxM00 = LOW(H)*LOW(M);
- HxM01 = LOW(H)*HIGH(M);
- HxM10 = HIGH(H)*LOW(M);
- HxM11 = HIGH(H)*HIGH(M); //has at most 60 bits
- C0 = HxM00+(HxM01<<32)+(HxM10<<32);//overflow doesn't matter here.
- C0 = C0&Prime61; //Has at most 61 bits.
- C1 = (HxM00>>32)+HxM01+HxM10; //Overflow impossible each <=62 bits
- C1 = C1>>29; //Has at most 33 bits.
- C2 = HxM11<<3; //Has at most 123-64+3=62 bits.
- CC = C0+C1+C2; //At most 63 bits.
- H = (CC&Prime61)+(CC>>61); //<2*Prime
- }
-}
-
-inline static VarStringHash32bit2univID InitVarStringHash32bitUniv() {
- gs_int32_t i;
- VarStringHash32bit2univID hid;
-
- hid = (VarStringHash32bit2univID) malloc(sizeof(VSHID));
- for (i=0;i<16;i++) {
- hid->int_str[i]=0;
- hid->str_compr_hid[i]=RandINT64();
- }
- hid->string_hid = RandINT64() & Prime61;
- // hid->last_compr_hid = RandINT64() | 0x1ull;
- return hid;
- }
-
-inline INT32 VarStringHash32bitUniv(char * x, gs_int32_t length,
- VarStringHash32bit2univID hid) {
-
- INT32 h,i,l,d,str_ix;
- INT64 C,H,M;
- INT64 xh1,xh2,y;
- INT64 HxM00,HxM01,HxM10,HxM11,C0,C1,C2,CC;
-
- // Assumes hid->int_str[*]==0
-
- if (length<=60) {
- memcpy(hid->int_str,x,length);
- d=(length+3)>>2; //<16
- h=StringHash32bit2univ(hid->int_str,d,hid->str_compr_hid);
- for (i=0;i<d;i++) hid->int_str[i]=0;
- return h;
- }
- H=0;
- str_ix=0;
- for (;;) {
- C = 0;
- l=length-str_ix;
- if (l>64) l=64;
- memcpy(hid->int_str,x+str_ix,l);
- str_ix+=l;
- d=(l+3)>>2;
- i=0;
- if (d&1) {
- C = hid->int_str[i]*hid->str_compr_hid[i];
- i++;
- }
- while (i<d) {
- xh1=hid->int_str[i]+hid->str_compr_hid[i+1];
- xh2=hid->int_str[i+1]+hid->str_compr_hid[i];
- y=xh1*xh2;
- C = C^y;
- i+=2;
- }
- for (i=0;i<d;i++) hid->int_str[i]=0;
- if (str_ix==(INT32) length) {
- H<<=4;
- H+=C;
- H+=((INT64) length)*hid->length_factor;
- h=(H>>32);
- return h;
- }
- C>>=4;
- H+=C;
- M=hid->string_hid;
- //Multiply H*M mod Prime61, possibly plus Prime,
- //exploiting the structure of Prime61.
- //We assume H<2*Prime61 and M<=Prime61, e.g.,
- //H*M <2^123.
- HxM00 = LOW(H)*LOW(M);
- HxM01 = LOW(H)*HIGH(M);
- HxM10 = HIGH(H)*LOW(M);
- HxM11 = HIGH(H)*HIGH(M); //has at most 60 bits
- C0 = HxM00+(HxM01<<32)+(HxM10<<32);//overflow doesn't matter here.
- C0 = C0&Prime61; //Has at most 61 bits.
- C1 = (HxM00>>32)+HxM01+HxM10; //Overflow impossible each <=62 bits
- C1 = C1>>29; //Has at most 33 bits.
- C2 = HxM11<<3; //Has at most 123-64+3=62 bits.
- CC = C0+C1+C2; //At most 63 bits.
- H = (CC&Prime61)+(CC>>61); //<2*Prime
- }
-}
-
-
-#endif
-
+/* ------------------------------------------------\r
+Copyright 2014 AT&T Intellectual Property\r
+ Licensed under the Apache License, Version 2.0 (the "License");\r
+ you may not use this file except in compliance with the License.\r
+ You may obtain a copy of the License at\r
+\r
+ http://www.apache.org/licenses/LICENSE-2.0\r
+\r
+ Unless required by applicable law or agreed to in writing, software\r
+ distributed under the License is distributed on an "AS IS" BASIS,\r
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
+ See the License for the specific language governing permissions and\r
+ limitations under the License.\r
+ ------------------------------------------- */\r
+\r
+#ifndef _STRINGHASH_H\r
+#define _STRINGHASH_H\r
+#include <stdlib.h>\r
+#include <stdio.h>\r
+#include <limits.h>\r
+#include <stdint.h>\r
+#include <string.h>\r
+\r
+//Provides 5-universal hash functions.\r
+//Both a direct polynomial based one,\r
+//and the much faster tabulation based one.\r
+//\r
+//It also provides 2-universal string hashing.\r
+//For most applicatoins, introdcing a slight error,\r
+//if you want almost 5-uninversal hashing for strings,\r
+//you can do a 2-universal hashing into 32-bit integer\r
+//getting very few collissoins, and then use the above\r
+//5-universal one.\r
+\r
+\r
+\r
+typedef gs_uint8_t INT8;\r
+typedef gs_uint16_t INT16;\r
+typedef gs_uint32_t INT32;\r
+typedef gs_uint64_t INT64;\r
+\r
+typedef INT64 * Hash61bit5univID;\r
+typedef INT32** HashTab32bit5univID;\r
+typedef INT32** HashTab32bitLPID;\r
+typedef INT64** HashTab64bitLPID;\r
+typedef INT64 * Hash32bit2univID;\r
+typedef INT32 Hash32bitUnivID;\r
+\r
+const INT32 MAX_INT32 = UINT_MAX;\r
+\r
+typedef struct {\r
+ INT64 str_compr_hid[16];\r
+ INT64 string_hid;\r
+ INT64 length_factor;\r
+ // INT64 last_compr_hid;\r
+} VISHID;\r
+\r
+typedef VISHID * VarINT32StringHash32bit2univID;\r
+\r
+\r
+typedef struct {\r
+ INT32 int_str[16];\r
+ INT64 str_compr_hid[16];\r
+ INT64 string_hid;\r
+ INT64 length_factor;\r
+ // INT64 last_compr_hid;\r
+} VSHID;\r
+\r
+typedef VSHID * VarStringHash32bit2univID;\r
+\r
+\r
+\r
+\r
+\r
+// different views of a 64-bit double word\r
+typedef union {\r
+ INT64 as_int64;\r
+ INT32 as_int32s[2];\r
+ INT16 as_int16s[4];\r
+} int64views;\r
+\r
+const INT64 LowOnes = (((INT64)1)<<32)-1;\r
+\r
+#define LOW(x) ((x)&LowOnes) // extract lower 32 bits from INT64\r
+#define HIGH(x) ((x)>>32) // extract higher 32 bits from INT64\r
+\r
+const INT64 Prime61 = (((INT64)1)<<61) - 1;\r
+\r
+\r
+//Random numbers from random.org based on atmostpheric noise.\r
+INT64 Random64[200]= {0x285eb7722a62ce6eull,\r
+ 0xa84c7463e2b7856bull,\r
+ 0xb29100d6abcc8666ull,\r
+ 0xf9bfca5b7461fb1full,\r
+ 0x51c8dafc30c88dadull,\r
+ 0x0687468c365ec51dull,\r
+ 0x2bf2cd3ad64b6218ull,\r
+ 0xc20565a4d1f00f9eull,\r
+ 0x7d533575d313c658ull,\r
+ 0xbf2fba6b00725b85ull,\r
+ 0x4cfc2f6557e722beull,\r
+ 0xedbce818556dfb2bull,\r
+ 0xd9df508027db1bbeull,\r
+ 0x21f2d922f712f48bull,\r
+ 0xcd8b289d83a65804ull,\r
+ 0x4a19cfb02445a6d2ull,\r
+ 0xc95e56b1e19a4f94ull,\r
+ 0xcfeeeaccaf477248ull,\r
+ 0x4eec3378b73bb25cull,\r
+ 0x18a3f38d1c48b2beull,\r
+ 0x71b79ab5cb1e3730ull,\r
+ 0x79cdb30e2f38309dull,\r
+ 0xb41d4983bdbc8d6full,\r
+ 0xba9f57c01b66b7e3ull,\r
+ 0xe400503c95c16568ull,\r
+ 0x5977bfd4630294f1ull,\r
+ 0x57d4d7940099676full,\r
+ 0xd945de9268f4b191ull,\r
+ 0x4034711421eaf806ull,\r
+ 0x6d8108a4a6d58c22ull,\r
+ 0x5c421818ddbdd4eeull,\r
+ 0xbd9b7e4071713c13ull,\r
+ 0xa60d1d6e793e5eb2ull,\r
+ 0x7443fb031b8ec6c7ull,\r
+ 0xd8290c7120e05d4aull,\r
+ 0x797fb1d9a6a8d27full,\r
+ 0x543ec268ab1f2e45ull,\r
+ 0xcaf2a6139701f320ull,\r
+ 0x9519611d130bee47ull,\r
+ 0x19bbc533f018be1aull,\r
+ 0xdbfacdfeb573133dull,\r
+ 0x3255dacc4c7bfe12ull,\r
+ 0xbc6c9228e5518f6eull,\r
+ 0xb5c1681037347178ull,\r
+ 0xbaaa2cfef186bfadull,\r
+ 0x1834b8ab0f9e876eull,\r
+ 0x9d7b7f228433e0f7ull,\r
+ 0xa99cc292d003dd09ull,\r
+ 0xc0cb8037046b5295ull,\r
+ 0xa6ffa3d4671aa3d2ull,\r
+ 0xc27023fbee2862e6ull,\r
+ 0x5a9877bcc4bd3172ull,\r
+ 0xfcb0da3caf9fcfe0ull,\r
+ 0xc35ef57e1866ceaeull,\r
+ 0xd4f7c927d169a115ull,\r
+ 0x699054518fc74756ull,\r
+ 0xa75cbf617fc9db8dull,\r
+ 0x7f3adf4369665a9cull,\r
+ 0x6b98eeeb4c517f42ull,\r
+ 0xa12e44f5de954f24ull,\r
+ 0x5789ded4dced978eull,\r
+ 0xe4dd20ed27cd3567ull,\r
+ 0x9b4e90c365b8790bull,\r
+ 0xd486ed6e099f499bull,\r
+ 0x3f3d0ccfeaa0c0dcull,\r
+ 0x548c746cdb192adaull,\r
+ 0x8ce636d8469fe2dcull,\r
+ 0xca59ec929549a6a1ull,\r
+ 0x647b9878deaba1f0ull,\r
+ 0xebbb4b2641c54d34ull,\r
+ 0x7be6d2918b680abdull,\r
+ 0x02ad265fb4733490ull,\r
+ 0xfe1053044faf3486ull,\r
+ 0x539ea358ff6b6df3ull,\r
+ 0x025d73224a2b5826ull,\r
+ 0x7daad302451f41b3ull,\r
+ 0x6038455ddb535976ull,\r
+ 0x8d6d00a9a728a067ull,\r
+ 0xe9f03d61d4965d59ull,\r
+ 0x38314b8102daff3bull,\r
+ 0x56b335e7893a76f1ull,\r
+ 0x1048ca2f415712abull,\r
+ 0xa9bc989a891dc173ull,\r
+ 0xb741df3ae02836c2ull,\r
+ 0x7711e6c6f5830783ull,\r
+ 0x8edbf2be9226e24bull,\r
+ 0xe4a4b8ba310fc2e2ull,\r
+ 0xbc7b67f4a02f23c8ull,\r
+ 0x5669b1a9d6d8df17ull,\r
+ 0xdd3ebf2e3c516e26ull,\r
+ 0x77bdd6def5236c4full,\r
+ 0x9aeb54bdffacd65eull,\r
+ 0xab676483404a21b8ull,\r
+ 0xf7270f77a9d1b3a3ull,\r
+ 0x3794e1cdcc7de433ull,\r
+ 0x8e2b74d3a06aa56aull,\r
+ 0x572698d05b901d40ull,\r
+ 0x7bd6c265c1dd5cdfull,\r
+ 0xd2f68a53970db82eull,\r
+ 0x0e1d5f5dd9bd23bdull,\r
+ 0x48814c6813505051ull,\r
+ 0x8f2d21a7d4e4a481ull,\r
+ 0x144531c871920cf3ull,\r
+ 0x45c6f81c7fbc3b2full,\r
+ 0xc562f1fc7f07a944ull,\r
+ 0xaabdf3d0aa9872e4ull,\r
+ 0x8db1f9d827c8df98ull,\r
+ 0xea787210e13c16c7ull,\r
+ 0xd43f6f582629ff39ull,\r
+ 0x6ec7599da4cb298dull,\r
+ 0xfa99d7196097dd94ull,\r
+ 0xbe3a8a172a62f40dull,\r
+ 0x07477bc03d9d5471ull,\r
+ 0x03777d1ee44c0fa6ull,\r
+ 0x5c6df847b0ae6fd1ull,\r
+ 0xc1fc3bc2352d8125ull,\r
+ 0x6800e3321d35b697ull,\r
+ 0x51cc735e1b0920a8ull,\r
+ 0x93dc60a2430c11acull,\r
+ 0x13b6bf8ffc4e9e30ull,\r
+ 0xada08114e6a01701ull,\r
+ 0x1459b7a4254da4cdull,\r
+ 0xf7575cd7ededcdfdull,\r
+ 0x1e43675ed5ed33eeull,\r
+ 0x639f5ff579cc30d4ull,\r
+ 0x8f4f75d7eea7e300ull,\r
+ 0x518939accd43dadeull,\r
+ 0x989a77577fac24e2ull,\r
+ 0x86c5e3998c819d51ull,\r
+ 0xb84770f9cc15d139ull,\r
+ 0x11544010174c2c99ull,\r
+ 0xfb238b962405a579ull,\r
+ 0xca5bddde9b80cb7bull,\r
+ 0xbbe71928190dfab4ull,\r
+ 0x0ec620294742b8c8ull,\r
+ 0x90bc7a703ed63900ull,\r
+ 0x2c8a80e1e85f72bbull,\r
+ 0xf19ab262ed2ad914ull,\r
+ 0xa233e89fab33793cull,\r
+ 0x75b6f59568a958f5ull,\r
+ 0x31fb15af9a41aca2ull,\r
+ 0xf89db05aa21b3d1cull,\r
+ 0x0023d08c52147f63ull,\r
+ 0x8e0e3c2aba81e8fdull,\r
+ 0xdb2efd057c157e71ull,\r
+ 0x1a1797a83e39dfe4ull,\r
+ 0x3afc43e1979f507dull,\r
+ 0x0e647a8d8abe0936ull,\r
+ 0xc8e03f27082eb0daull,\r
+ 0xc1b0c11db52da528ull,\r
+ 0xadeb52a144f497ceull,\r
+ 0x046fc2f53bd97c9bull,\r
+ 0x2d587fdf5fae80d5ull,\r
+ 0x14036c3fb77fd73eull,\r
+ 0x883f768734d14676ull,\r
+ 0x212df988a83caffeull,\r
+ 0x36b41dac32387e17ull,\r
+ 0x9dbee8d7cf804bccull,\r
+ 0x34d9a58fb9a35794ull,\r
+ 0xda82beba879e3576ull,\r
+ 0x0366148280e5adf1ull,\r
+ 0x634085dcdba7b174ull,\r
+ 0x8451523252446534ull,\r
+ 0xc74ce8b4d5175b9aull,\r
+ 0x40afebd30a9a4837ull,\r
+ 0x7232952ce84e90beull,\r
+ 0x7443a6e37b87992dull,\r
+ 0xace8a33649218d9aull,\r
+ 0x9ad8af9614b75655ull,\r
+ 0xd518d9a700179ac2ull,\r
+ 0xc7f906d90fd36259ull,\r
+ 0xe2c47ec3abd8a12dull,\r
+ 0xca05e96fcbbb76c1ull,\r
+ 0x7186661c9ddf4973ull,\r
+ 0x0146f5f47d5f42c2ull,\r
+ 0x74a7c485608ea178ull,\r
+ 0x8cb5e3e5f84f3040ull,\r
+ 0xb330869dc366037dull,\r
+ 0x0dbc4d22f932bbd4ull,\r
+ 0xa8460b43946a5ecbull,\r
+ 0xcee72c72fe5ddea6ull,\r
+ 0x9f953cc7859b2a4eull,\r
+ 0x95ea396619e60182ull,\r
+ 0xfe9890efa6aa8c3eull,\r
+ 0x3c9a5691d1e25799ull,\r
+ 0xa54eeb19aa718b62ull,\r
+ 0x69907b2ec11d82b7ull,\r
+ 0x408c5405984caa65ull,\r
+ 0x6f11a21711640470ull,\r
+ 0x20b9227a8f53f9aeull,\r
+ 0x42df63b7ec442178ull,\r
+ 0xbec247f79407d00aull,\r
+ 0x2946c31558eab2bcull,\r
+ 0x84d045ffa174048eull,\r
+ 0x28bad532ba4a450cull,\r
+ 0x93ccf0cbaa274d7aull,\r
+ 0xff30008411d25158ull,\r
+ 0x3845ce6dcc30080aull,\r
+ 0xcf5925239b6f3dbaull,\r
+ 0x1f148649ed53660dull};\r
+\r
+\r
+\r
+\r
+\r
+\r
+gs_int32_t nextrandom = 0;\r
+gs_int32_t endrandom = 100;\r
+\r
+\r
+// The first "endrandom" numbers returned are truely random INT64.\r
+// They are perfect for bases of new hash functions, and currently\r
+// we have just enough such random numbers for tabulation based\r
+// 5-universal hashing, or one of the other schemes provided.\r
+// The remaining ones are based on the pseudo-random mrand48() which\r
+// returns a signed 32-bit number. We do not use the unsigned lrand48()\r
+// which only returns 31-bit.\r
+inline static INT64 RandINT64() {\r
+ INT64 r,r1;\r
+ if (nextrandom<endrandom) r=Random64[nextrandom++];\r
+ else {\r
+ if (nextrandom==endrandom)\r
+ fprintf(stderr,"Switching from random to pseudo-random in Rand64");\r
+ r =(INT64) mrand48();\r
+ r1 = (INT64) mrand48();\r
+ r=r<<32;\r
+ r=r^r1;\r
+ }\r
+ return r;\r
+}\r
+\r
+\r
+/* Computes ax+b mod Prime, possibly plus Prime,\r
+ exploiting the structure of Prime. */\r
+inline static INT64 MultAddPrime(INT32 x, INT64 a, INT64 b) {\r
+ INT64 a0,a1,c0,c1,c;\r
+ a0 = LOW(a)*x;\r
+ a1 = HIGH(a)*x;\r
+ c0 = a0+(a1<<32);\r
+ c1 = (a0>>32)+a1;\r
+ c = (c0&Prime61)+(c1>>29)+b;\r
+ return c;\r
+} // 12 instructions\r
+\r
+/* CWtrick for 32-bit key x with prime 2^61-1 */\r
+inline static INT64 Hash61bit5univ(INT32 x, Hash61bit5univID index) {\r
+ INT64 h;\r
+ gs_int32_t i;\r
+\r
+ h = index[0];\r
+ for (i=1;i<5;i++) h = MultAddPrime(x,h,index[i]);\r
+ h = (h&Prime61)+(h>>61);\r
+ if (h>=Prime61) h-=Prime61;\r
+ return h;\r
+}\r
+\r
+\r
+\r
+inline static INT64* InitHash61bit5univ() {\r
+ gs_int32_t i;\r
+\r
+ Hash61bit5univID hid = (INT64*) malloc(5*sizeof(INT64));\r
+ for (i=0;i<5;i++) {\r
+ hid[i]=RandINT64();\r
+ hid[i] = (hid[i]&Prime61)+(hid[i]>>61);\r
+ if (hid[i]>=Prime61) hid[i]-=Prime61;\r
+ }\r
+ return hid;\r
+}\r
+\r
+inline static HashTab32bit5univID InitHashTab32bit5univ() {\r
+ gs_uint32_t i,j;\r
+ HashTab32bit5univID htab;\r
+ Hash61bit5univID h61id;\r
+\r
+\r
+ htab = (HashTab32bit5univID) malloc(3*sizeof(INT32*));\r
+ for (i=0;i<3;i++) {\r
+ htab[i] = (INT32*) malloc(65538*sizeof(INT32));\r
+ h61id = InitHash61bit5univ();\r
+ for (j=0;j<65538;j++) htab[i][j]=Hash61bit5univ(j,h61id);\r
+ }\r
+ return htab;\r
+}\r
+\r
+/* tabulation based hashing for 32-bit key x using 16-bit characters.*/\r
+inline INT64 HashTab32bit5univ(INT32 x, HashTab32bit5univID htab) {\r
+ INT32 x0, x1, x2;\r
+ x0 = x&65535;\r
+ x1 = x>>16;\r
+ x2 = x0 + x1;\r
+ x2 = 2 - (x2>>16) + (x2&65535); // optional compression\r
+ return htab[0][x0]^htab[1][x1]^htab[2][x2];\r
+} // 8 + 4 = 12 instructions\r
+\r
+\r
+/* Tabulation based hashing for 32-bit keys using 16-bit characters.*/\r
+/* Uses 500KB tables and makes 2 lookups per hash. */\r
+\r
+inline static HashTab32bitLPID InitHashShortTab32bitLP() {\r
+ gs_uint32_t i,j;\r
+ HashTab32bitLPID htab;\r
+ Hash61bit5univID h61id;\r
+\r
+\r
+ htab = (HashTab32bitLPID) malloc(2*sizeof(INT32*));\r
+ for (i=0;i<2;i++) {\r
+ htab[i] = (INT32*) malloc(65536*sizeof(INT32));\r
+ h61id = InitHash61bit5univ();\r
+ for (j=0;j<65536;j++) htab[i][j]=Hash61bit5univ(j,h61id);\r
+ }\r
+ return htab;\r
+}\r
+\r
+/* tabulation based hashing for 32-bit key x using 16-bit characters.*/\r
+inline INT64 HashShortTab32bitLP(INT32 x, HashTab32bitLPID htab) {\r
+ INT32 x0, x1;\r
+ x0 = x&65535;\r
+ x1 = x>>16;\r
+ return htab[0][x0]^htab[1][x1];\r
+}\r
+\r
+\r
+/* Tabulation based hashing for 32-bit keys using 8-bit characters.*/\r
+/* Uses 4KB tables and makes 4 lookups per hash. */\r
+\r
+inline static HashTab32bitLPID InitHashCharTab32bitLP() {\r
+ gs_uint32_t i,j;\r
+ HashTab32bitLPID htab;\r
+ Hash61bit5univID h61id;\r
+\r
+\r
+ htab = (HashTab32bitLPID) malloc(4*sizeof(INT32*));\r
+ for (i=0;i<4;i++) {\r
+ htab[i] = (INT32*) malloc(256*sizeof(INT32));\r
+ h61id = InitHash61bit5univ();\r
+ for (j=0;j<256;j++) htab[i][j]=Hash61bit5univ(j,h61id);\r
+ }\r
+ return htab;\r
+}\r
+\r
+inline INT32 HashCharTab32bitLP(INT32 x, HashTab32bitLPID htab) {\r
+ INT8 c;\r
+ INT32 h;\r
+ gs_int32_t i;\r
+\r
+ c=x;\r
+ h=htab[0][c];\r
+ for (i=1;i<4;i++) {\r
+ x>>=8;\r
+ c=x;\r
+ h=h^htab[i][c];\r
+ }\r
+ return h;\r
+}\r
+\r
+\r
+/* Tabulation based hashing for 64-bit keys using 16-bit characters.*/\r
+/* Uses 2MB tables and makes 4 lookups per hash. */\r
+\r
+\r
+inline static HashTab64bitLPID InitHashShortTab64bitLP() {\r
+ gs_int32_t i,j;\r
+ HashTab64bitLPID htab;\r
+ Hash61bit5univID h61id;\r
+\r
+\r
+ htab = (HashTab64bitLPID) malloc(4*sizeof(INT64*));\r
+ for (i=0;i<4;i++) {\r
+ htab[i] = (INT64*) malloc(65536*sizeof(INT64));\r
+ h61id = InitHash61bit5univ();\r
+ for (j=0;j<65536;j++) htab[i][j]=Hash61bit5univ(j,h61id);\r
+ h61id = InitHash61bit5univ();\r
+ for (j=0;j<65536;j++) htab[i][j]+=Hash61bit5univ(j,h61id)<<32;\r
+ }\r
+ return htab;\r
+}\r
+\r
+inline INT64 HashShortTab64bitLP(INT64 x, HashTab64bitLPID htab) {\r
+ INT16 c;\r
+ INT64 h;\r
+ gs_int32_t i;\r
+\r
+ c=x;\r
+ h=htab[0][c];\r
+ for (i=1;i<4;i++) {\r
+ x>>=16;\r
+ c=x;\r
+ h=h^htab[i][c];\r
+ }\r
+ return h;\r
+}\r
+\r
+/* Tabulation based hashing for 64-bit keys using 8-bit characters.*/\r
+/* Uses 14KB tables and makes 8 lookups per hash. */\r
+\r
+inline static HashTab64bitLPID InitHashCharTab64bitLP() {\r
+ gs_int32_t i,j;\r
+ HashTab64bitLPID htab;\r
+ Hash61bit5univID h61id;\r
+\r
+\r
+ htab = (HashTab64bitLPID) malloc(8*sizeof(INT64*));\r
+ for (i=0;i<8;i++) {\r
+ htab[i] = (INT64*) malloc(256*sizeof(INT64));\r
+ h61id = InitHash61bit5univ();\r
+ for (j=0;j<256;j++) htab[i][j]=Hash61bit5univ(j,h61id);\r
+ h61id = InitHash61bit5univ();\r
+ for (j=0;j<256;j++) htab[i][j]+=Hash61bit5univ(j,h61id)<<32;\r
+ }\r
+ return htab;\r
+}\r
+\r
+inline INT64 HashCharTab64bitLP(INT64 x, HashTab64bitLPID htab) {\r
+ INT8 c;\r
+ INT64 h;\r
+ gs_int32_t i;\r
+\r
+ c=x;\r
+ h=htab[0][c];\r
+ for (i=1;i<8;i++) {\r
+ x>>=8;\r
+ c=x;\r
+ h=h^htab[i][c];\r
+ }\r
+ return h;\r
+}\r
+\r
+\r
+/* Tabulation based hashing for 34-bit keys using 10-11-bit characters.*/\r
+/* Uses 20KB tables and makes 3 lookups per hash. */\r
+\r
+inline static HashTab32bitLPID InitHashMipTab32bitLP() {\r
+ gs_int32_t i,j;\r
+ HashTab32bitLPID htab;\r
+ Hash61bit5univID h61id;\r
+\r
+\r
+ htab = (HashTab32bitLPID) malloc(6*sizeof(INT32*));\r
+ for (i=0;i<2;i++) {\r
+ htab[i] = (INT32*) malloc(0x800*sizeof(INT32));\r
+ h61id = InitHash61bit5univ();\r
+ for (j=0;j<0x800;j++) htab[i][j]=(INT32) Hash61bit5univ(j,h61id);\r
+ }\r
+ for (i=2;i<3;i++) {\r
+ htab[i] = (INT32*) malloc(0x400*sizeof(INT32));\r
+ h61id = InitHash61bit5univ();\r
+ for (j=0;j<0x400;j++) htab[i][j]=(INT32) Hash61bit5univ(j,h61id);\r
+ }\r
+ return htab;\r
+}\r
+\r
+inline INT32 HashMipTab32bitLP(INT32 x, HashTab32bitLPID htab) {\r
+ INT32 c;\r
+ INT32 h;\r
+ gs_int32_t i;\r
+\r
+ h=0;\r
+ for (i=0;i<2;i++) {\r
+ c= x & 0x7FFull;\r
+ h=h^htab[i][c];\r
+ x>>=11;\r
+ }\r
+ c= x & 0x3FFull;\r
+ h=h^htab[2][c];\r
+ return h;\r
+}\r
+\r
+/* Tabulation based hashing for 64-bit keys using 10-11-bit characters.*/\r
+/* Uses 80KB tables and makes 6 lookups per hash. */\r
+\r
+inline static HashTab64bitLPID InitHashMipTab64bitLP() {\r
+ gs_int32_t i,j;\r
+ HashTab64bitLPID htab;\r
+ Hash61bit5univID h61id;\r
+\r
+\r
+ htab = (HashTab64bitLPID) malloc(6*sizeof(INT64*));\r
+ for (i=0;i<4;i++) {\r
+ htab[i] = (INT64*) malloc(0x800*sizeof(INT64));\r
+ h61id = InitHash61bit5univ();\r
+ for (j=0;j<0x800;j++) htab[i][j]=Hash61bit5univ(j,h61id);\r
+ h61id = InitHash61bit5univ();\r
+ for (j=0;j<0x800;j++) htab[i][j]+=Hash61bit5univ(j,h61id)<<32;\r
+ }\r
+ for (i=4;i<6;i++) {\r
+ htab[i] = (INT64*) malloc(0x400*sizeof(INT64));\r
+ h61id = InitHash61bit5univ();\r
+ for (j=0;j<0x400;j++) htab[i][j]=Hash61bit5univ(j,h61id);\r
+ h61id = InitHash61bit5univ();\r
+ for (j=0;j<0x400;j++) htab[i][j]+=Hash61bit5univ(j,h61id)<<32;\r
+ }\r
+ return htab;\r
+}\r
+\r
+inline INT64 HashMipTab64bitLP(INT64 x, HashTab64bitLPID htab) {\r
+ INT64 c;\r
+ INT64 h;\r
+ gs_int32_t i;\r
+\r
+ h=0;\r
+ for (i=0;i<4;i++) {\r
+ c= x & 0x7FFull;\r
+ h=h^htab[i][c];\r
+ x>>=11;\r
+ }\r
+ for (i=4;i<6;i++) {\r
+ c= x & 0x3FFull;\r
+ h=h^htab[i][c];\r
+ x>>=10;\r
+ }\r
+ return h;\r
+}\r
+\r
+\r
+\r
+inline static Hash32bit2univID InitHash32bit2univ() {\r
+ Hash32bit2univID hid = (INT64*) malloc(2*sizeof(INT64));\r
+ hid[0]=RandINT64();\r
+ hid[1]=RandINT64();\r
+ return hid;\r
+}\r
+\r
+inline INT32 Hash32bit2univ(INT32 x, Hash32bit2univID hid) {\r
+ INT64 H;\r
+ INT32 h;\r
+ H = (x*hid[0])+hid[1];\r
+ h = H >> 32;\r
+ return h;\r
+}\r
+\r
+\r
+// For the string hashing below is for string of 32bit integers, and\r
+// the output is a 2-universal 32-bit number.\r
+\r
+inline static Hash32bit2univID InitStringHash32bit2univ(gs_int32_t length) {\r
+ gs_int32_t i;\r
+ Hash32bit2univID hid = (INT64*) malloc((length+1)*sizeof(INT64));\r
+ for (i=0;i<=length;i++) hid[i]=RandINT64();\r
+ return hid;\r
+}\r
+\r
+\r
+\r
+//assumes string length even\r
+inline INT32 EvenStringHash32bit2univ(INT32 * x, gs_int32_t length,\r
+ Hash32bit2univID hid) {\r
+ gs_int32_t i;\r
+ INT64 H;\r
+ INT32 h;\r
+ INT64 xh1,xh2,y;\r
+\r
+ H=0;\r
+ for (i=0;i<length;i+=2) {\r
+ xh1=x[i]+hid[i+1];\r
+ xh2=x[i+1]+hid[i];\r
+ y=xh1*xh2;\r
+ H = H^y;\r
+ }\r
+ H=H^hid[length];\r
+ h = H >> 32;\r
+ return h;\r
+}\r
+\r
+//assumes string length odd\r
+inline INT32 OddStringHash32bit2univ(INT32 * x, gs_int32_t length,\r
+ Hash32bit2univID hid) {\r
+ gs_int32_t i;\r
+ INT64 H;\r
+ INT32 h;\r
+ INT64 xh1,xh2,y;\r
+\r
+ H = x[0]*hid[0];\r
+ for (i=1;i<length;i+=2) {\r
+ xh1=x[i]+hid[i+1];\r
+ xh2=x[i+1]+hid[i];\r
+ y=xh1*xh2;\r
+ H = H^y;\r
+ }\r
+ H=H^hid[length];\r
+ h = H >> 32;\r
+ return h;\r
+}\r
+\r
+//Below we have the generic algorithm for fixed length string hashing\r
+//For shorter strings of length < 6, it is worthwhile using\r
+//specialized versions with fewer tests.\r
+//All versions rely on the some initialization above.\r
+inline INT32 StringHash32bit2univ(INT32 * x, gs_int32_t length, Hash32bit2univID hid) {\r
+// gs_int32_t i;\r
+// INT64 H=0;\r
+// INT32 h;\r
+// for (i=0;i<length;i++) H = H^(x[i]*hid[i]);\r
+// H=H^hid[length];\r
+// h = H >> 32;\r
+// return h;\r
+ if (length&1) return OddStringHash32bit2univ(x,length,hid);\r
+ else return EvenStringHash32bit2univ(x,length,hid);\r
+}\r
+\r
+\r
+//string of length 2\r
+inline INT32 String2Hash32bit2univ(INT32 * x,Hash32bit2univID hid) {\r
+ INT64 H;\r
+ INT32 h;\r
+ INT64 xh1,xh2;\r
+\r
+ xh1=x[0]+hid[1];\r
+ xh2=x[1]+hid[0];\r
+ H=xh1*xh2;\r
+ H=H^hid[2];\r
+ h = H >> 32;\r
+ return h;\r
+}\r
+\r
+//string of length 3\r
+inline INT32 String3Hash32bit2univ(INT32 * x,Hash32bit2univID hid) {\r
+ INT64 H;\r
+ INT32 h;\r
+ INT64 xh1,xh2,y;\r
+\r
+ H = x[0]*hid[0];\r
+ xh1=x[1]+hid[2];\r
+ xh2=x[2]+hid[1];\r
+ y=xh1*xh2;\r
+ H = H^y;\r
+ H=H^hid[3];\r
+ h = H >> 32;\r
+ return h;\r
+}\r
+\r
+\r
+inline static VarINT32StringHash32bit2univID InitVarINT32StringHash32bitUniv() {\r
+ gs_int32_t i;\r
+ VarINT32StringHash32bit2univID hid;\r
+\r
+ hid = (VarINT32StringHash32bit2univID) malloc(sizeof(VISHID));\r
+ for (i=0;i<16;i++) hid->str_compr_hid[i]=RandINT64();\r
+ hid->string_hid = RandINT64() & Prime61;\r
+ // hid->last_compr_hid = RandINT64() | 0x1ull;\r
+ return hid;\r
+ }\r
+\r
+inline INT32 VarINT32StringHash32bitUniv(INT32 * x, gs_int32_t length, VarINT32StringHash32bit2univID hid) {\r
+\r
+ INT32 h,i,j,d;\r
+ gs_int32_t e;\r
+ INT64 C,H,M;\r
+ INT64 xh1,xh2,y;\r
+ INT64 HxM00,HxM01,HxM10,HxM11,C0,C1,C2,CC;\r
+\r
+ if (length<16) return StringHash32bit2univ(x,length,hid->str_compr_hid);\r
+ H=0;\r
+ i=0;\r
+ for (;;) {\r
+ d=length-i;\r
+ C = 0;\r
+ j=0;\r
+ if (d>16) d=16;\r
+ else if (d&1) {\r
+ C = x[i]*hid->str_compr_hid[j];\r
+ i++;\r
+ j++;\r
+ }\r
+ for (e=((int) (d>>1));e>0;e--) {\r
+ xh1=x[i]+hid->str_compr_hid[j+1];\r
+ xh2=x[i+1]+hid->str_compr_hid[j];\r
+ y=xh1*xh2;\r
+ C = C^y;\r
+ i+=2;\r
+ j+=2;\r
+ }\r
+ if (i==(INT32) length) {\r
+ H<<=4;\r
+ H+=C;\r
+ H+=((INT64) length)*hid->length_factor;\r
+ h=(H>>32);\r
+ return h;\r
+ }\r
+ C>>=4;\r
+ H+=C;\r
+ M=hid->string_hid;\r
+ //Multiply H*M mod Prime61, possibly plus Prime,\r
+ //exploiting the structure of Prime61.\r
+ //We assume H<2*Prime61 and M<=Prime61, e.g.,\r
+ //H*M <2^123.\r
+ HxM00 = LOW(H)*LOW(M);\r
+ HxM01 = LOW(H)*HIGH(M);\r
+ HxM10 = HIGH(H)*LOW(M);\r
+ HxM11 = HIGH(H)*HIGH(M); //has at most 60 bits\r
+ C0 = HxM00+(HxM01<<32)+(HxM10<<32);//overflow doesn't matter here.\r
+ C0 = C0&Prime61; //Has at most 61 bits.\r
+ C1 = (HxM00>>32)+HxM01+HxM10; //Overflow impossible each <=62 bits\r
+ C1 = C1>>29; //Has at most 33 bits.\r
+ C2 = HxM11<<3; //Has at most 123-64+3=62 bits.\r
+ CC = C0+C1+C2; //At most 63 bits.\r
+ H = (CC&Prime61)+(CC>>61); //<2*Prime\r
+ }\r
+}\r
+\r
+inline static VarStringHash32bit2univID InitVarStringHash32bitUniv() {\r
+ gs_int32_t i;\r
+ VarStringHash32bit2univID hid;\r
+\r
+ hid = (VarStringHash32bit2univID) malloc(sizeof(VSHID));\r
+ for (i=0;i<16;i++) {\r
+ hid->int_str[i]=0;\r
+ hid->str_compr_hid[i]=RandINT64();\r
+ }\r
+ hid->string_hid = RandINT64() & Prime61;\r
+ // hid->last_compr_hid = RandINT64() | 0x1ull;\r
+ return hid;\r
+ }\r
+\r
+inline INT32 VarStringHash32bitUniv(char * x, gs_int32_t length,\r
+ VarStringHash32bit2univID hid) {\r
+\r
+ INT32 h,i,l,d,str_ix;\r
+ INT64 C,H,M;\r
+ INT64 xh1,xh2,y;\r
+ INT64 HxM00,HxM01,HxM10,HxM11,C0,C1,C2,CC;\r
+\r
+ // Assumes hid->int_str[*]==0\r
+\r
+ if (length<=60) {\r
+ memcpy(hid->int_str,x,length);\r
+ d=(length+3)>>2; //<16\r
+ h=StringHash32bit2univ(hid->int_str,d,hid->str_compr_hid);\r
+ for (i=0;i<d;i++) hid->int_str[i]=0;\r
+ return h;\r
+ }\r
+ H=0;\r
+ str_ix=0;\r
+ for (;;) {\r
+ C = 0;\r
+ l=length-str_ix;\r
+ if (l>64) l=64;\r
+ memcpy(hid->int_str,x+str_ix,l);\r
+ str_ix+=l;\r
+ d=(l+3)>>2;\r
+ i=0;\r
+ if (d&1) {\r
+ C = hid->int_str[i]*hid->str_compr_hid[i];\r
+ i++;\r
+ }\r
+ while (i<d) {\r
+ xh1=hid->int_str[i]+hid->str_compr_hid[i+1];\r
+ xh2=hid->int_str[i+1]+hid->str_compr_hid[i];\r
+ y=xh1*xh2;\r
+ C = C^y;\r
+ i+=2;\r
+ }\r
+ for (i=0;i<d;i++) hid->int_str[i]=0;\r
+ if (str_ix==(INT32) length) {\r
+ H<<=4;\r
+ H+=C;\r
+ H+=((INT64) length)*hid->length_factor;\r
+ h=(H>>32);\r
+ return h;\r
+ }\r
+ C>>=4;\r
+ H+=C;\r
+ M=hid->string_hid;\r
+ //Multiply H*M mod Prime61, possibly plus Prime,\r
+ //exploiting the structure of Prime61.\r
+ //We assume H<2*Prime61 and M<=Prime61, e.g.,\r
+ //H*M <2^123.\r
+ HxM00 = LOW(H)*LOW(M);\r
+ HxM01 = LOW(H)*HIGH(M);\r
+ HxM10 = HIGH(H)*LOW(M);\r
+ HxM11 = HIGH(H)*HIGH(M); //has at most 60 bits\r
+ C0 = HxM00+(HxM01<<32)+(HxM10<<32);//overflow doesn't matter here.\r
+ C0 = C0&Prime61; //Has at most 61 bits.\r
+ C1 = (HxM00>>32)+HxM01+HxM10; //Overflow impossible each <=62 bits\r
+ C1 = C1>>29; //Has at most 33 bits.\r
+ C2 = HxM11<<3; //Has at most 123-64+3=62 bits.\r
+ CC = C0+C1+C2; //At most 63 bits.\r
+ H = (CC&Prime61)+(CC>>61); //<2*Prime\r
+ }\r
+}\r
+\r
+\r
+#endif\r
+\r
Code Review / com / gs-lite.git / blobdiff