source: trunk/lib/hash_util.hpp @ 1889

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

Updated comments, debug statements.

File size: 3.4 KB
Line 
1#ifndef BYTE_UTIL_HPP
2#define BYTE_UTIL_HPP
3
4//#define NDEBUG /* Define to remove assertions and debug statements. */
5
6#include "bitblock.hpp"
7#include <cassert>
8#include <stdint.h>
9#include <iostream>
10using namespace std;
11
12/*  WARNING:
13
14    FW=1 indicates 'idx' and 'lgth' arguments are expressed in terms of bits.
15    FW=8 indicates 'idx' and 'lgth' arguments are expressed in terms of bytes.
16
17    slice<1> - performs a bit slice operation
18    slice<8> - performs a byte slice operation
19
20    hash<1> - returns a hash value based on bit indexed and bit length symbols
21    hash<8> - returns a hash value based on byte indexed and byte length symbols
22
23    Assumes 64 bits safety. That is, it is safe to dereference 64 bits beyond
24    the address of the indexed position (&buffer[0] + idx (bits|bytes)).
25*/
26
27template<uint32_t FW>
28IDISA_ALWAYS_INLINE uint64_t slice(const uint8_t * buffer, const uint32_t idx, const uint32_t bytes);
29
30/* WARNING: Length of Symbol Bits >= Length of Hash Bits.  */
31template<uint32_t FW>
32IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * b0, const uint8_t * b1, const uint32_t idx, const uint32_t lgth, const uint32_t hash_bits);
33
34template<>
35IDISA_ALWAYS_INLINE uint64_t slice<1>(const uint8_t * buffer, const uint32_t idx, const uint32_t lgth) {
36    assert(lgth > 0);
37    assert((idx+lgth)<((sizeof(uint64_t)*8)+1));
38
39    uint64_t shift = *((uint64_t *)(buffer + (idx/8))) >> (idx & 8-1);
40    uint64_t slice_mask = UINT64_MAX >> ((sizeof(uint64_t)*8 - lgth)); /* WARNING:      Bitwise full register shift is compiler depedendent.
41                                                                                        e.g. ~0 << 64 vs ~0 << n for n=64. */
42#ifndef NDEBUG
43    print_register<uint64_t>("shift", shift);
44    print_register<uint64_t>("slice mask", slice_mask);
45#endif
46    return shift & slice_mask;
47}
48
49template<>
50IDISA_ALWAYS_INLINE uint64_t slice<8>(const uint8_t * buffer, const uint32_t idx, const uint32_t lgth) {
51    assert(lgth > 0);
52    assert((idx+(lgth*8)) < ((sizeof(uint64_t)*8)+1));
53
54    uint64_t shift = *((uint64_t *)(buffer+idx));
55    uint64_t slice_mask = UINT64_MAX >> ((sizeof(uint64_t) - lgth)*8); /* WARNING:      Bitwise full register shift is compiler depedendent.
56                                                                                        e.g. ~0 << 64 vs ~0 << n for n=64. */
57#ifndef NDEBUG
58    print_register<uint64_t>("shift", shift);
59    print_register<uint64_t>("slice mask", slice_mask);
60#endif
61    return shift & slice_mask;
62}
63
64/* WARNING: Length of Symbol Bits >= Length of Hash Bits.  */
65template<uint32_t FW>
66IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * b0, const uint8_t * b1, const uint32_t idx, const uint32_t lgth, const uint32_t hash_bits) {
67
68    assert(lgth > 0);
69    assert((idx+(lgth*FW)) < ((sizeof(uint64_t)*8)+1));
70    assert((lgth*FW) >= hash_bits);
71
72    uint64_t x0 = slice<FW>(b0,idx,lgth);
73    uint64_t x1 = slice<FW>(b1,idx,lgth);
74    uint64_t mask = (1 << hash_bits) - 1;
75
76#ifndef NDEBUG
77    cout << "Index Lgth:  " << idx << endl;
78    cout << "Symbol Lgth: " << lgth << endl;
79    cout << "Hash Bits:   " << hash_bits << endl;
80    uint64_t masked_x0 = x0 & mask;
81    uint64_t shift_masked_x1 = (x1 >> ((lgth*FW) - hash_bits)) & mask;
82    print_register<uint64_t>("b0", *(uint64_t *)b0);
83    print_register<uint64_t>("b1", *(uint64_t *)b1);
84    print_register<uint64_t>("x0", x0);
85    print_register<uint64_t>("x1", x1);
86    print_register<uint64_t>("mask", mask);
87    print_register<uint64_t>("masked x0", masked_x0);
88    print_register<uint64_t>("shift masked x1", shift_masked_x1);
89#endif
90
91    return (x0 ^ (x1 >> ((lgth*FW) - hash_bits))) & mask;
92}
93
94
95#endif // BYTE_UTIL_HPP
96
Note: See TracBrowser for help on using the repository browser.