source: trunk/lib/hash_util.hpp @ 1914

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

Added mask_hash function.

File size: 3.6 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/*  Hash Functions Templated on Field Width.
11
12    slice<1> - bit slice operation
13    FW=1 'pos' and 'lgth' args in terms of bits,
14    e.g. pos=1,lgth=7 => begin at bit index 1 and slice symbol of length 7 bits.
15
16    slice<8> - byte slice operation
17    FW=8 'pos' and 'lgth' args in terms of bytes, i.e. byte at index 1
18    e.g. pos=1,lgth=4 => begin at byte index position 1 and slice symbol of length 4 bytes.
19
20    shift_hash<1> - returns a hash value based on bit index and symbol length
21    shift_hash<8> - returns a hash value based on byte index and symbol length
22*/
23
24/* WARNING: Casts uint8_t * buffer at pos to uint64_t * and deferences. Segmentation faults w/o sufficient buffer padding.  */
25template<uint32_t FW>
26IDISA_ALWAYS_INLINE uint64_t mask_hash(const uint8_t * b0, const uint32_t hash_bits, const uint32_t lgth);
27
28template<uint32_t FW>
29IDISA_ALWAYS_INLINE uint64_t slice(const uint8_t * buffer, const uint32_t pos, const uint32_t lgth);
30
31template<uint32_t FW>
32IDISA_ALWAYS_INLINE uint64_t shift_hash(const uint8_t * b0, const uint8_t * b1, const uint32_t pos, const uint32_t hash_bits, const uint32_t lgth);
33
34template<>
35IDISA_ALWAYS_INLINE uint64_t slice<1>(const uint8_t * buffer, const uint32_t pos, const uint32_t lgth) {
36    assert(lgth > 0 && lgth <= 64);
37
38    uint64_t shift = *((uint64_t *)(buffer + (pos/8))) >> (pos & 8-1);
39    uint64_t slice_mask = UINT64_MAX >> ((sizeof(uint64_t)*8 - lgth));
40#ifndef NDEBUG
41    print_register<uint64_t>("shift", shift);
42    print_register<uint64_t>("slice mask", slice_mask);
43#endif
44    return shift & slice_mask;
45}
46
47template<>
48IDISA_ALWAYS_INLINE uint64_t slice<8>(const uint8_t * buffer, const uint32_t pos, const uint32_t lgth) {
49    assert(lgth > 0 && lgth <= 8);
50
51    uint64_t shift = *((uint64_t *)(buffer+pos));
52    uint64_t slice_mask = UINT64_MAX >> ((sizeof(uint64_t) - lgth)*8);
53#ifndef NDEBUG
54    print_register<uint64_t>("shift", shift);
55    print_register<uint64_t>("slice mask", slice_mask);
56#endif
57    return shift & slice_mask;
58}
59
60template<uint32_t FW>
61IDISA_ALWAYS_INLINE uint64_t mask_hash(const uint8_t * b0, const uint32_t hash_bits, const uint32_t lgth) {
62    assert(lgth > 0 && lgth*FW <= 64);
63    assert((lgth*FW) > hash_bits);
64
65    const uint64_t ONE = 1;
66    uint64_t mask = (ONE << hash_bits) - ONE;
67#ifndef NDEBUG
68    print_register<uint64_t>("mask", mask);
69#endif
70    return *((uint64_t *)b0) & mask;
71}
72
73template<uint32_t FW>
74IDISA_ALWAYS_INLINE uint64_t shift_hash(const uint8_t * b0, const uint8_t * b1, const uint32_t pos, const uint32_t hash_bits, const uint32_t lgth) {
75    assert(lgth > 0 && lgth*FW <= 64);
76    assert((lgth*FW) > hash_bits);
77
78    uint64_t x0 = slice<FW>(b0,pos,lgth);
79    uint64_t x1 = slice<FW>(b1,pos,lgth);
80    const uint64_t ONE = 1;
81    uint64_t mask = (ONE << hash_bits) - ONE;
82
83#ifndef NDEBUG
84    cout << "Position:  " << pos << endl;
85    cout << "Symbol Lgth: " << lgth << endl;
86    cout << "Hash Bits:   " << hash_bits << endl;
87
88    uint64_t masked_x0 = x0 & mask;
89    uint64_t shift_masked_x1 = (x1 >> ((lgth*FW) - hash_bits)) & mask;
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>("mask", mask);
95    print_register<uint64_t>("masked x0", masked_x0);
96    print_register<uint64_t>("shift masked x1", shift_masked_x1);
97#endif
98
99    return (x0 ^ (x1 >> ((lgth*FW) - hash_bits))) & mask;
100}
101
102
103
104
105#endif // BYTE_UTIL_HPP
106
Note: See TracBrowser for help on using the repository browser.