tab-hash 0.3.0

Simple and twisted tabulation hashing for 32-bit and 64-bit unsigned integers.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

/* This is the implementation presented by Mikkel Thorup in https://arxiv.org/abs/1505.01523
 * It is used as reference implementation for tests.
 */
#include <stdint.h> //defines uintX_t as unsigned X-bit integer.
typedef unsigned __int128 uint128_t;

uint32_t SimpleTab32(uint32_t x, uint32_t H[4][256]) {
  uint32_t i;
  uint32_t h = 0;
  uint8_t c;
  for (i=0; i<4; i++) {
    c = x;
    h ^= H[i][c];
    x = x >> 8;
  }
  return h;
}


uint32_t TwistedTab32(uint32_t x, uint64_t H[4][256]) {
  uint32_t i;
  uint64_t h = 0;
  uint8_t c;
  for (i=0; i<3; i++) {
    c = x;
    h ^= H[i][c];
    x = x >> 8;
  }
  c = x^h;
  // extra xor compared with simple
  h ^= H[i][c];
  h >>= 32;
  // extra shift compared with simple
  return ((uint32_t) h);
}





// 64-bit version
uint64_t SimpleTab64(uint64_t x, uint64_t H[8][256]) {
  uint64_t i;
  uint64_t h = 0;
  uint8_t c;
  for (i=0; i<8; i++) {
    c = x;
    h ^= H[i][c];
    x = x >> 8;
  }
  return h;
}

/* 64-bit version */
uint64_t TwistedTab64(uint64_t x, uint128_t H[8][256]) {
  uint64_t i;
  uint128_t h = 0;
  uint8_t c;
  for (i=0; i<7; i++) {
    c = x;
    h ^= H[i][c];
    x = x >> 8;
  }
  c = x^h;
  // extra xor compared with simple
  h ^= H[i][c];
  h >>= 64;
  // extra shift compared with simple
  return ((uint64_t) h);
}