source: trunk/lib/hash.hpp @ 1918

Last change on this file since 1918 was 1918, checked in by ksherdy, 7 years ago

Update hash functions.

File size: 5.7 KB
Line 
1#ifndef BYTE_UTIL_HPP
2#define BYTE_UTIL_HPP
3
4#include "bitblock.hpp"
5#include <cassert>
6#include <stdint.h>
7#include <iostream>
8using namespace std;
9
10/* WARNING:     Pad 8 bytes.
11                Internal static casts of uint8_t * b0 to uint64_t * and deference. */
12
13
14static IDISA_ALWAYS_INLINE uint64_t gen_mask(const uint32_t hash_size);
15static IDISA_ALWAYS_INLINE uint64_t byte_mask_hash(const uint8_t *b0, const uint32_t pos, const uint32_t hash_size);
16
17/* pos (bits) */
18static IDISA_ALWAYS_INLINE uint64_t bit_offset_slice(const uint8_t * buffer, const uint32_t pos, const uint32_t slice_size);
19static IDISA_ALWAYS_INLINE uint64_t bit_compress_hash(const uint8_t * b0, const uint8_t * b1, const uint32_t pos, const uint32_t slice_size, const uint32_t hash_size);
20
21/* pos (bytes) */
22static IDISA_ALWAYS_INLINE uint64_t byte_offset_slice(const uint8_t * buffer, const uint32_t pos, const uint32_t slice_size);
23static IDISA_ALWAYS_INLINE uint64_t byte_compress_hash(const uint8_t * b0, const uint32_t pos, const uint32_t slice_size, const uint32_t hash_size);
24
25static IDISA_ALWAYS_INLINE uint64_t gen_mask(const uint32_t hash_size) {
26    assert(hash_size > 0);
27
28    const uint64_t ONE = 1;
29    uint64_t mask = (ONE << hash_size) - ONE;
30#ifndef NDEBUG
31    print_register<uint64_t>("mask", mask);
32#endif
33    return mask;
34}
35
36static IDISA_ALWAYS_INLINE uint64_t byte_mask_hash(const uint8_t *b0, const uint32_t pos, const uint32_t hash_size) {
37    uint64_t mask = gen_mask(hash_size);
38    return *((uint64_t *)(b0 + pos)) & mask;
39}
40
41/* pos (bits) */
42static IDISA_ALWAYS_INLINE uint64_t bit_offset_slice(const uint8_t * buffer, const uint32_t pos, const uint32_t slice_size) {
43    assert(slice_size > 0 && slice_size <= 64);
44
45    uint64_t shift = *((uint64_t *)(buffer + (pos/8))) >> (pos & 8-1);
46    uint64_t mask = gen_mask(slice_size);
47    uint64_t r = shift & mask;
48
49#ifndef NDEBUG
50    print_register<uint64_t>("shift", shift);
51    print_register<uint64_t>("mask", mask);
52#endif
53
54    return r;
55}
56
57/* pos (bytes) */
58static IDISA_ALWAYS_INLINE uint64_t byte_offset_slice(const uint8_t * buffer, const uint32_t pos, const uint32_t slice_size) {
59    assert(slice_size > 0 && slice_size <= 64);
60
61    uint64_t shift = *((uint64_t *)(buffer+pos));
62    uint64_t mask = gen_mask(slice_size);
63    uint64_t r = shift & mask;
64
65#ifndef NDEBUG
66    print_register<uint64_t>("shift", shift);
67    print_register<uint64_t>("mask", mask);
68#endif
69    return r;
70}
71
72static IDISA_ALWAYS_INLINE uint64_t bit_compress_hash(const uint8_t * b0, const uint8_t * b1, const uint32_t pos, const uint32_t slice_size, const uint32_t hash_size) {
73    assert(slice_size > 0 && slice_size <= 64);
74    assert(slice_size >= hash_size); /* negative shifts undefined in C standard, (x1 >> shift) */
75
76#ifndef NDEBUG
77    cout << endl;
78    cout << "Stream pos (bit):  " << pos << endl;
79    cout << "Slice size (bits): "  << slice_size << endl;
80    cout << "Hash size (bits):   " << hash_size << endl;
81#endif
82
83    uint64_t x0 = bit_offset_slice(b0,pos,slice_size);
84    uint64_t x1 = bit_offset_slice(b1,pos,slice_size);
85    uint64_t shift = (slice_size - hash_size);
86    uint64_t mask = gen_mask(hash_size);
87    uint64_t r = (x0 ^ (x1 >> shift)) & mask;
88
89#ifndef NDEBUG
90    print_register<uint64_t>("b0", *(uint64_t *)b0);
91    print_register<uint64_t>("b1", *(uint64_t *)b1);
92    print_register<uint64_t>("x0", x0);
93    print_register<uint64_t>("x1", x1);
94    print_register<uint64_t>("shift x1", (x1 >> shift));
95    print_register<uint64_t>("r", r);
96#endif
97
98    return r;
99}
100
101static IDISA_ALWAYS_INLINE uint64_t byte_compress_hash(const uint8_t * b0, const uint32_t pos, const uint32_t slice_size, const uint32_t hash_size) {
102    assert(slice_size > 0 && slice_size <= 64);
103    assert(slice_size >= hash_size); // negative shifts undefined in C standard
104
105#ifndef NDEBUG
106    cout << endl;
107    cout << "Stream pos (byte):  " << pos << endl;
108    cout << "Slice size (bits): "  << slice_size << endl;
109    cout << "Hash size (bits):   " << hash_size << endl;
110#endif
111
112    uint64_t x0 = *((uint64_t *)(b0+pos));
113    uint64_t shift = (slice_size - hash_size);  // negative shifts undefined in C standard
114    uint64_t mask = gen_mask(hash_size);
115    uint64_t r = (x0 ^ (x0 >> shift)) & mask;
116
117#ifndef NDEBUG
118    print_register<uint64_t>("b0", *(uint64_t *)(b0));
119    print_register<uint64_t>("x0", x0);
120    print_register<uint64_t>("x0 >> shift", x0>>shift);
121    print_register<uint64_t>("r", r);
122#endif
123
124    return r;
125}
126
127#endif // BYTE_UTIL_HPP
128
129/*
130static IDISA_ALWAYS_INLINE uint64_t bit_expand_hash(const uint8_t * b0, const uint8_t * b1, const uint32_t pos, const uint32_t slice_size, const uint32_t hash_size);
131static IDISA_ALWAYS_INLINE uint64_t bit_expand_hash(const uint8_t * b0, const uint8_t * b1, const uint32_t pos, const uint32_t slice_size, const uint32_t hash_size) {
132    assert(slice_size > 0 && slice_size <= 64);
133    //assert(slice_size <= hash_size);
134
135    uint64_t x0 = bit_offset_slice(b0,pos,slice_size);
136    uint64_t x1 = bit_offset_slice(b1,pos,slice_size);
137    uint64_t mask = gen_mask(hash_size);
138
139    assert(x0 != x1);
140
141    uint64_t t = x0 ^ x1;
142    uint64_t r = t;
143    int32_t shift = slice_size;
144
145    print_register<uint64_t>("t", t);
146    print_register<uint64_t>("r", r);
147
148    while(shift > 0) {
149
150#ifndef NDEBUG
151    cout << "Stream pos (bit):  " << pos << endl;
152    cout << "Symbol lgth (bits): " << slice_size << endl;
153    cout << "Hash size (bits):   " << hash_size << endl;
154    cout << "Shift (bits): " << shift << endl;
155
156    print_register<uint64_t>("b0", *(uint64_t *)b0);
157    print_register<uint64_t>("b1", *(uint64_t *)b1);
158    print_register<uint64_t>("x0", x0);
159    print_register<uint64_t>("x1", x1);
160    print_register<uint64_t>("r", r);
161#endif
162        r = r | (r << (uint32_t)shift);
163        shift -= slice_size;
164        print_register<uint64_t>("r", r);
165    }
166
167    return r & mask;
168}
169*/
Note: See TracBrowser for help on using the repository browser.