Changeset 1948 for trunk


Ignore:
Timestamp:
Feb 29, 2012, 9:47:31 PM (7 years ago)
Author:
ksherdy
Message:

Updated hash functions.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/lib/hash.hpp

    r1940 r1948  
    1 #ifndef BYTE_UTIL_HPP
    2 #define BYTE_UTIL_HPP
     1#ifndef HASH_HPP
     2#define HASH_HPP
    33
    4 #include "bitblock.hpp"
     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"
    513#include <cassert>
    614#include <stdint.h>
     
    816using namespace std;
    917
    10 /* WARNING:     Pad 8 bytes.
    11                 Internal static casts of uint8_t * base to uint64_t * and deference. */
     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///////////////////////////////////////////////////////////////////////////////
    1224
    13 static int32_t bytes2bits(int32_t bits) { return bits * 8; }
     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));
    1427
    15 static IDISA_ALWAYS_INLINE uint64_t gen_mask(const uint32_t hash_size);
     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);
    1631
    17 /* offset (bits) */
    18 static IDISA_ALWAYS_INLINE uint64_t bit_offset_slice(const uint8_t * base, const int32_t offset, const uint32_t slice_size);
     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);
    1933
    20 /* offset (bytes) */
    21 //static IDISA_ALWAYS_INLINE uint64_t byte_offset_slice(const uint8_t * base, const int32_t offset, const uint32_t slice_size);
     34///////////////////////////////////////////////////////////////////////////////
    2235
    23 /* offset (bits) */
    24 static IDISA_ALWAYS_INLINE uint64_t compress_hash(const uint8_t * base, const int32_t offset, const uint32_t slice_size, const uint32_t hash_size);
    25 
    26 static IDISA_ALWAYS_INLINE uint64_t gen_mask(const uint32_t hash_size) {
    27     assert(hash_size > 0);
     36static IDISA_ALWAYS_INLINE uint64_t gen_mask(const uint32_t mask_bits) {
     37    assert(mask_bits >= 0);
    2838
    2939    const uint64_t ONE = 1;
    30     uint64_t mask = (ONE << hash_size) - ONE;
    31 #ifndef NDEBUG
     40    uint64_t mask = (ONE << mask_bits) - ONE;
     41#ifdef HASH_HPP_DEBUG
    3242    print_register<uint64_t>("mask", mask);
    3343#endif
     
    3545}
    3646
    37 /* offset (bits) */
    38 static IDISA_ALWAYS_INLINE uint64_t bit_offset_slice(const uint8_t * base, const int32_t offset, const uint32_t slice_size) {
    39     assert(slice_size > 0 && slice_size <= 64);
    40     assert((offset & (8-1)) >= 0); // negative shifts undefined in C standard
     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);
    4150
    42     uint64_t shift = *((uint64_t *)(base + (offset/8))) >> (offset & (8-1));
    43     uint64_t mask = gen_mask(slice_size);
     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);
    4472    uint64_t r = shift & mask;
    4573
    46 #ifndef NDEBUG
    47     print_register<uint64_t>("shift", shift);
     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);
    4878    print_register<uint64_t>("mask", mask);
     79    print_register<uint64_t>("r", r);
    4980#endif
    5081
     
    5283}
    5384
    54 static IDISA_ALWAYS_INLINE uint64_t compress_hash(const uint8_t * base, const int32_t offset, const uint32_t slice_size, const uint32_t hash_size) {
    55     //assert(slice_size > 0 && slice_size <= 64);
    56     //assert(slice_size >= hash_size); // negative shifts undefined in C standard
     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) {
    5786
    5887    assert(hash_size > 0 && hash_size <= 64);
    5988    assert(slice_size >= hash_size);
    6089
    61 #ifndef NDEBUG
    62     cout << endl;
    63     cout << "Stream offset (byte):  " << offset << endl;
    64     cout << "Slice size (bits): "  << slice_size << endl;
    65     cout << "Hash size (bits):   " << hash_size << endl;
    66 #endif
     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);
    6792
    68     uint64_t x0 = bit_offset_slice(base,offset,hash_size);
    69     uint64_t x1 = bit_offset_slice(base,offset+slice_size-hash_size,hash_size);
     93    assert(x0 != x1);
     94    uint64_t r = x0 ^ x1;
    7095
    71     //uint64_t x0 = //*((uint64_t *)(base+offset));
    72     //uint64_t shift = (slice_size - hash_size);  // negative shifts undefined in C standard
    73     uint64_t mask = gen_mask(hash_size);
    74     uint64_t r = (x0 ^ x1) & mask;
    75 
    76 #ifndef NDEBUG
    77     print_register<uint64_t>("base", *(uint64_t *)(base));
     96#ifdef HASH_HPP_DEBUG
     97    print_register<uint64_t>("h0", *(uint64_t *)(h0));
     98    print_register<uint64_t>("h1", *(uint64_t *)(h1));
    7899    print_register<uint64_t>("x0", x0);
    79     //print_register<uint64_t>("x0 >> shift", x0>>shift);
    80100    print_register<uint64_t>("x1", x1);
    81101    print_register<uint64_t>("r", r);
     
    85105}
    86106
    87 #endif // BYTE_UTIL_HPP
    88 
    89 /* offset (bytes) */
    90 /*
    91 static IDISA_ALWAYS_INLINE uint64_t byte_offset_slice(const uint8_t * base, const int32_t offset, const uint32_t slice_size) {
    92     assert(slice_size > 0 && slice_size <= 64);
    93 
    94     uint64_t shift = *((uint64_t *)(base+offset));
    95     uint64_t mask = gen_mask(slice_size);
    96     uint64_t r = shift & mask;
    97 
    98 #ifndef NDEBUG
    99     print_register<uint64_t>("shift", shift);
    100     print_register<uint64_t>("mask", mask);
    101 #endif
    102     return r;
    103 }
    104 */
     107#endif // HASH_HPP
    105108
    106109/*
     
    110113    //assert(slice_size <= hash_size);
    111114
    112     uint64_t x0 = bit_offset_slice(base,offset,slice_size);
    113     uint64_t x1 = bit_offset_slice(base1,offset,slice_size);
     115    uint64_t x0 = bit_slice(base,offset,slice_size);
     116    uint64_t x1 = bit_slice(base1,offset,slice_size);
    114117    uint64_t mask = gen_mask(hash_size);
    115118
Note: See TracChangeset for help on using the changeset viewer.