source: trunk/lib/hash.hpp @ 2196

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

Added alignment assertion.

File size: 5.5 KB
Line 
1#ifndef HASH_HPP
2#define HASH_HPP
3
4/*=============================================================================
5  allocator.hpp - Hash Utilities.
6  Created on: 18-December-2011
7  Author: Ken Herdy
8=============================================================================*/
9
10// #define HASH_HPP_DEBUG
11
12//#define NDEBUG // if NDEBUG then disable assertions
13
14#include "../lib/bitblock.hpp"
15#include <cassert>
16#include <stdint.h>
17#include <iostream>
18using namespace std;
19
20///////////////////////////////////////////////////////////////////////////////
21//
22// WARNING: Pad or Perish
23//
24// 'bit_slice' and 'byte_slice' slice forward via a static cast to the
25// uint64_t type at the position of the base address + bit_idx
26// and require up to sizeof(uint64_t) bytes of additional padding.
27//
28///////////////////////////////////////////////////////////////////////////////
29
30static int32_t bytes2bits(int32_t bytes) { return bytes * 8; }
31static int32_t bits2bytes(int32_t bits) /*{ return (bits + 8) / (8); } */ { return ((bits & (8-1) != 0) ? (bits + 8) / (8) : (bits/8)); }
32static IDISA_ALWAYS_INLINE uint64_t gen_mask(const uint32_t mask_bits);
33
34//static IDISA_ALWAYS_INLINE uint64_t byte_slice(const uint8_t * base, const int32_t byte_idx, const uint32_t slice_bytes);
35//static IDISA_ALWAYS_INLINE uint64_t byte_compress_hash(const uint8_t * h0, const uint8_t * h1, const int32_t byte_idx, const uint32_t slice_bytes, const uint32_t hash_bytes);
36
37static IDISA_ALWAYS_INLINE uint64_t bit_slice(const uint8_t * base, const int32_t bit_idx, const uint32_t slice_bits);
38static IDISA_ALWAYS_INLINE uint64_t bit_compress_hash(const uint8_t * h0, const uint8_t * h1, const int32_t bit_idx, const uint32_t slice_bits, const uint32_t hash_bits);
39
40///////////////////////////////////////////////////////////////////////////////
41
42static IDISA_ALWAYS_INLINE uint64_t gen_mask(const uint32_t mask_bits) {
43    assert(mask_bits >= 0);
44
45    const uint64_t ONE = 1;
46    uint64_t mask = (ONE << mask_bits) - ONE;
47#ifdef HASH_HPP_DEBUG
48    print_register<uint64_t>("mask", mask);
49#endif
50    return mask;
51}
52
53//static IDISA_ALWAYS_INLINE uint64_t byte_slice(const uint8_t * base, const int32_t byte_idx, const uint32_t slice_bytes) {
54//    assert(slice_bytes >= 0 && slice_bytes <= sizeof(uint64_t));
55//    assert(byte_idx >= 0);
56
57//    uint64_t shift = *((uint64_t *)(base + byte_idx));
58//    uint64_t mask = gen_mask(bytes2bits(slice_bytes));
59//    uint64_t r = shift & mask;
60
61//#ifdef HASH_HPP_DEBUG
62//    print_register<BitBlock>("base", *(BitBlock *)base);
63//    cout << "byte index:" << byte_idx << endl;
64//    print_register<BitBlock>("shift", *(BitBlock *)&shift);
65//    print_register<uint64_t>("mask", mask);
66//    print_register<uint64_t>("r", r);
67//#endif
68
69//    return r;
70//}
71
72static IDISA_ALWAYS_INLINE uint64_t bit_slice(const uint8_t * base, const int32_t bit_idx, const uint32_t slice_bits) {
73    assert(slice_bits >= 0 && slice_bits <= bytes2bits(sizeof(uint64_t)));
74    assert(bit_idx >= 0);
75
76    uint64_t shift = *((uint64_t *)(base + (bit_idx/8))) >> (bit_idx & (8-1));
77    uint64_t mask = gen_mask(slice_bits);
78    uint64_t r = shift & mask;
79
80#ifdef HASH_HPP_DEBUG
81    print_register<uint64_t>("base", *(uint64_t *)base);
82    cout << "           bit index = " << bit_idx << endl;
83    print_register<uint64_t>("shift", *(uint64_t *)&shift);
84    print_register<uint64_t>("mask", mask);
85    print_register<uint64_t>("r", r);
86#endif
87
88    return r;
89}
90
91static IDISA_ALWAYS_INLINE uint64_t bit_compress_hash(const uint8_t * h0, const uint8_t * h1, const int32_t bit_idx, const uint32_t slice_bits, const uint32_t hash_bits) {
92
93    assert(hash_bits > 0 && hash_bits <= 64);
94    assert(slice_bits >= hash_bits);
95
96    uint64_t x0 = bit_slice(h0,bit_idx,hash_bits);
97    uint64_t x1 = bit_slice(h1,bit_idx+slice_bits-hash_bits,hash_bits);
98
99    //assert(x0 != x1);
100    uint64_t mask = gen_mask(slice_bits);
101    uint64_t r = x0 ^ x1;
102
103#ifdef HASH_HPP_DEBUG
104    print_register<uint64_t>("h0", *(uint64_t *)(h0));
105    print_register<uint64_t>("h1", *(uint64_t *)(h1));
106    print_register<uint64_t>("x0", x0);
107    print_register<uint64_t>("x1", x1);
108    print_register<uint64_t>("r", r);
109#endif
110
111    return r  & mask;
112}
113
114#endif // HASH_HPP
115
116/*
117static IDISA_ALWAYS_INLINE uint64_t bit_expand_hash(const uint8_t * base, const uint8_t * base1, const int32_t offset, const uint32_t slice_size, const uint32_t hash_size);
118static IDISA_ALWAYS_INLINE uint64_t bit_expand_hash(const uint8_t * base, const uint8_t * base1, const int32_t offset, const uint32_t slice_size, const uint32_t hash_size) {
119    assert(slice_size > 0 && slice_size <= 64);
120    //assert(slice_size <= hash_size);
121
122    uint64_t x0 = bit_slice(base,offset,slice_size);
123    uint64_t x1 = bit_slice(base1,offset,slice_size);
124    uint64_t mask = gen_mask(hash_size);
125
126    assert(x0 != x1);
127
128    uint64_t t = x0 ^ x1;
129    uint64_t r = t;
130    int32_t shift = slice_size;
131
132    print_register<uint64_t>("t", t);
133    print_register<uint64_t>("r", r);
134
135    while(shift > 0) {
136
137#ifndef NDEBUG
138    cout << "Stream offset (bit):  " << offset << endl;
139    cout << "Symbol lgth (bits): " << slice_size << endl;
140    cout << "Hash size (bits):   " << hash_size << endl;
141    cout << "Shift (bits): " << shift << endl;
142
143    print_register<uint64_t>("base", *(uint64_t *)base);
144    print_register<uint64_t>("base1", *(uint64_t *)base1);
145    print_register<uint64_t>("x0", x0);
146    print_register<uint64_t>("x1", x1);
147    print_register<uint64_t>("r", r);
148#endif
149        r = r | (r << (uint32_t)shift);
150        shift -= slice_size;
151        print_register<uint64_t>("r", r);
152    }
153
154    return r & mask;
155}
156*/
Note: See TracBrowser for help on using the repository browser.