source: trunk/lib/hash.hpp @ 1948

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

Updated hash functions.

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