source: trunk/lib/hash.hpp @ 3341

Last change on this file since 3341 was 2719, checked in by cameron, 7 years ago

Some copyright and description fixes

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