Changeset 1877 for trunk/lib


Ignore:
Timestamp:
Jan 24, 2012, 8:32:13 PM (7 years ago)
Author:
ksherdy
Message:

Added slice and hash utility functions. This file is likely not the
final destination of the functions.

File:
1 copied

Legend:

Unmodified
Added
Removed
  • trunk/lib/hash_util.hpp

    r1871 r1877  
    22#define BYTE_UTIL_HPP
    33
     4//#define NDEBUG /* Define to remove assertions and debug statements. */
     5
    46#include "bitblock.hpp"
    57#include <cassert>
     8#include <stdint.h>
    69#include <iostream>
    710using namespace std;
    811
    9 /* WARNING - Buffer pointer cast to integer type. Pad bytes as necessary. */
     12/*  WARNING:
    1013
    11 template<class T, uint32_t SF>
    12 static IDISA_ALWAYS_INLINE T slice(const uint8_t * buffer, const uint32_t pos, const uint32_t lgth);
     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.
    1316
    14 template<class T, uint32_t SF>
    15 static IDISA_ALWAYS_INLINE T slice(const uint8_t * buffer, const uint32_t pos, const uint32_t lgth) {
     17    slice<1> - performs a bit slice operation
     18    slice<8> - performs a byte slice operation
    1619
    17     T shift = *((T *)(buffer+pos));
     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
    1822
    19     if(lgth != sizeof(T)) {
     23    Assumes 64 bits safety. That is, it is safe to dereference 64 bits beyion address
     24    the address of the indexed positio (&buffer[0] + idx (bits/bytes)).
     25*/
    2026
    21         const T ZERO  = 0;
    22         T mask = ~(~ZERO << (lgth * SF));
    23         return shift & mask;
     27template<uint32_t FW>
     28IDISA_ALWAYS_INLINE uint64_t slice(const uint8_t * buffer, const uint32_t idx, const uint32_t bytes);
    2429
    25     }
     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);
    2633
    27     return shift;
     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;
    2847}
     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 (bits or bytes): " << idx << endl;
     78    cout << "Symbol Lgth (bytes): " << 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
    2994
    3095#endif // BYTE_UTIL_HPP
Note: See TracChangeset for help on using the changeset viewer.