Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members

HashKey Class Reference

#include <Hash.h>

List of all members.

Public Member Functions

 HashKey (bro_int_t i)
 HashKey (bro_uint_t u)
 HashKey (const uint32 u[], int n)
 HashKey (double d)
 HashKey (const void *p)
 HashKey (const char *s)
 HashKey (const BroString *s)
 ~HashKey ()
 HashKey (int copy_key, void *key, int size)
 HashKey (const void *key, int size, hash_t hash)
 HashKey (const void *bytes, int size)
 HashKey (const void *key, int size, hash_t hash, bool dont_copy)
void * TakeKey ()
const void * Key () const
int Size () const
hash_t Hash () const
unsigned int MemoryAllocation () const

Static Public Member Functions

hash_t HashBytes (const void *bytes, int size)

Protected Member Functions

void * CopyKey (const void *key, int size) const

Protected Attributes

union {
   bro_int_t   i
   double   d
   const void *   p
} key_u
void * key
int is_our_dynamic
int size
int hash

Constructor & Destructor Documentation

HashKey::HashKey (  bro_int_t  i  ) 
 

Definition at line 89 of file Hash.cc.

References bro_int_t, hash, HashBytes(), is_our_dynamic, key, key_u, and size. 

00090         {
00091         key_u.i = i;
00092         key = (void*) &key_u;
00093         size = sizeof(i);
00094         hash = HashBytes(key, size);
00095         is_our_dynamic = 0;
00096         }

HashKey::HashKey (  bro_uint_t  u  ) 
 

Definition at line 98 of file Hash.cc.

References bro_int_t, bro_uint_t, hash, HashBytes(), is_our_dynamic, key, key_u, and size. 

00099         {
00100         key_u.i = bro_int_t(u);
00101         key = (void*) &key_u;
00102         size = sizeof(u);
00103         hash = HashBytes(key, size);
00104         is_our_dynamic = 0;
00105         }

HashKey::HashKey (  const uint32  u[],
int  n
) 
 

Definition at line 120 of file Hash.cc.

References hash, HashBytes(), is_our_dynamic, key, size, and uint32. 

00121         {
00122         size = n * sizeof(u[0]);
00123         key = (void*) u;
00124         hash = HashBytes(key, size);
00125         is_our_dynamic = 0;
00126         }

HashKey::HashKey (  double  d  ) 
 

Definition at line 128 of file Hash.cc.

References hash, HashBytes(), i, is_our_dynamic, key, key_u, and size. 

00129         {
00130         union {
00131                 double d;
00132                 int i[2];
00133         } u;
00134 
00135         key_u.d = u.d = d;
00136         key = (void*) &key_u;
00137         size = sizeof(d);
00138         hash = HashBytes(key, size);
00139         is_our_dynamic = 0;
00140         }

HashKey::HashKey (  const void *  p  ) 
 

Definition at line 142 of file Hash.cc.

References hash, HashBytes(), is_our_dynamic, key, key_u, p, and size. 

00143         {
00144         key_u.p = p;
00145         key = (void*) &key_u;
00146         size = sizeof(p);
00147         hash = HashBytes(key, size);
00148         is_our_dynamic = 0;
00149         }

HashKey::HashKey (  const char *  s  ) 
 

Definition at line 151 of file Hash.cc.

References hash, HashBytes(), is_our_dynamic, key, and size. 

00152         {
00153         size = strlen(s);       // note - skip final \0
00154         key = (void*) s;
00155         hash = HashBytes(key, size);
00156         is_our_dynamic = 0;
00157         }

HashKey::HashKey (  const BroString *  s  ) 
 

Definition at line 159 of file Hash.cc.

References BroString::Bytes(), hash, HashBytes(), is_our_dynamic, key, BroString::Len(), and size. 

00160         {
00161         size = s->Len();
00162         key = (void*) s->Bytes();
00163         hash = HashBytes(key, size);
00164         is_our_dynamic = 0;
00165         }

HashKey::~HashKey (   )  [inline]
 

Definition at line 50 of file Hash.h.

References is_our_dynamic, and key. 

00051                 {
00052                 if ( is_our_dynamic )
00053                         delete [] (char *) key;
00054                 }

HashKey::HashKey (  int  copy_key,
void *  key,
int  size
) 
 

Definition at line 167 of file Hash.cc.

References hash, HashBytes(), is_our_dynamic, key, and size. 

00168         {
00169         size = arg_size;
00170         is_our_dynamic = 1;
00171 
00172         if ( copy_key )
00173                 {
00174                 key = (void*) new char[size];
00175                 memcpy(key, arg_key, size);
00176                 }
00177         else
00178                 key = arg_key;
00179 
00180         hash = HashBytes(key, size);
00181         }

HashKey::HashKey (  const void *  key,
int  size,
hash_t  hash
) 
 

Definition at line 183 of file Hash.cc.

References CopyKey(), hash, hash_t, is_our_dynamic, key, and size. 

00184         {
00185         size = arg_size;
00186         hash = arg_hash;
00187         key = CopyKey(arg_key, size);
00188         is_our_dynamic = 1;
00189         }

HashKey::HashKey (  const void *  bytes,
int  size
) 
 

Definition at line 200 of file Hash.cc.

References CopyKey(), hash, HashBytes(), is_our_dynamic, key, and size. 

00201         {
00202         size = arg_size;
00203         key = CopyKey(bytes, size);
00204         hash = HashBytes(key, size);
00205         is_our_dynamic = 1;
00206         }

HashKey::HashKey (  const void *  key,
int  size,
hash_t  hash,
bool  dont_copy
) 
 

Definition at line 191 of file Hash.cc.

References hash, hash_t, is_our_dynamic, key, and size. 

00193         {
00194         size = arg_size;
00195         hash = arg_hash;
00196         key = const_cast<void*>(arg_key);
00197         is_our_dynamic = 0;
00198         }

Member Function Documentation

void * HashKey::CopyKey (  const void *  key,
int  size
)  const [protected]
 

Definition at line 219 of file Hash.cc.

Referenced by HashKey(), and TakeKey(). 

00220         {
00221         void* k_copy = (void*) new char[s];
00222         memcpy(k_copy, k, s);
00223         return k_copy;
00224         }

hash_t HashKey::Hash (   )  const [inline]
 

Definition at line 86 of file Hash.h.

References hash, and hash_t.

Referenced by Dictionary::Insert(), Dictionary::Lookup(), ConnCompressor::PktHdrToPendingConn(), PersistenceSerializer::Register(), and Dictionary::Remove(). 

00086 { return hash; }

hash_t HashKey::HashBytes (  const void *  bytes,
int  size
)  [static]
 

Definition at line 226 of file Hash.cc.

References TwoWise::Hash(), hash_cnt_all, hash_cnt_uhash, hash_t, hmac_md5(), i, size, uhash_key, UHASH_KEY_SIZE, uint16, uint32, uint64, uint8, and y.

Referenced by SSL_Interpreter::analyzeCertificate(), and HashKey(). 

00227         {
00228 #ifdef USE_OLD_BRO_HASH
00229         // ### Shall we remove this?
00230         const unsigned char* cp = (const unsigned char*) bytes;
00231         hash_t h = 0;
00232 
00233         for ( int i = 0; i < size; ++i )
00234                 // Overflow is okay here.
00235                 h = (h >> 31) + (h << 1) + cp[i];
00236 
00237         return h;
00238 #endif /* USE_OLD_BRO_HASH */
00239 
00240         ++hash_cnt_all;
00241 
00242 #ifdef USE_H3
00243         if ( size == 0 ) // H3 doesn't check if size is zero
00244                 return 0;
00245 
00246         if ( size <= UHASH_KEY_SIZE )
00247                 {
00248                 ++hash_cnt_uhash;
00249                 return (*h3)(bytes, size);
00250                 }
00251 #endif /* USE_H3 */
00252 
00253 #ifdef USE_DIETZFELBINGER
00254         if ( size <= UHASH_KEY_SIZE )
00255                 {
00256                 ++hash_cnt_uhash;
00257                 return two_wise->Hash(size, bytes);
00258                 }
00259 #endif /* USE_DIETZFELBINGER */
00260 
00261 #ifdef USE_UMAC_NH
00262         // Use the NH hash function proposed in UMAC.
00263         // (See http://www.cs.ucdavis.edu/~rogaway/umac/)
00264         //
00265         // Essentially, it is computed as:
00266         // H = (x_0 +_16 k_0) * (x_1 +_16 k_1) +
00267         //      (x_2 +_16 k_2) * (x_3 +_16 k_3) + ...
00268         // where {k_i} are keys for universal hashing,
00269         // {x_i} are data words, and +_16 means plus mod 2^16.
00270         //
00271         // This is faster than UHASH because no modulo operation
00272         // is needed.
00273 
00274         typedef uint16 uhash_word_t;
00275         typedef uint32 uhash_dword_t;
00276 
00277         if ( (unsigned int) size <= UHASH_KEY_SIZE - sizeof(uhash_word_t) )
00278                 {
00279                 ++hash_cnt_uhash;
00280 
00281                 const uhash_word_t* uhash = (const uhash_word_t *) uhash_key;
00282                 const uint8* data = (const uint8 *) bytes;
00283                 uhash_dword_t sum = 0;
00284 
00285                 int i, j, k;
00286                 uhash_word_t x, y;
00287                 k = 0;
00288 
00289                 for ( i = 0; i + sizeof(uhash_word_t) < size; )
00290                         {
00291                         x = 0;
00292 
00293                         for ( j = 0; j < sizeof(uhash_word_t) && i + j < size; ++j )
00294                                 x = (x << 8) | data[i+j];
00295 
00296                         i += j;
00297                         x += uhash[k++];
00298                         y = 0;
00299 
00300                         for ( j = 0; j < sizeof(uhash_word_t) && i + j < size; ++j )
00301                                 y = (y << 8) | data[i+j];
00302 
00303                         i += j;
00304                         y += uhash[k++];
00305 
00306                         sum += ((uhash_dword_t) x) * ((uhash_dword_t) y);
00307                         }
00308 
00309                 x = 0;
00310                 for ( j = 0; j < sizeof(uhash_word_t) && i + j < size; ++j )
00311                         x = (x << 8) | data[i+j];
00312                 x += uhash[k++];
00313 
00314                 y = size + uhash[k++];
00315                 sum += ((uhash_dword_t) x) * ((uhash_dword_t) y);
00316 
00317                 return hash_t(sum);
00318                 }
00319 #endif /* USE_UMAC_NH */
00320 
00321 #ifdef USE_UHASH
00322         // Universal hashing by division (ax mod p).
00323         typedef uint32 uhash_word_t;
00324 
00325         // We do this typedef here rather than in util.h because
00326         // "long long" is not in fact ANSI C++ (though it *is* ANSI C),
00327         // so if it turns out to be problematic we can turn it off
00328         // by not using UHASH.
00329         typedef unsigned long long uint64;
00330 
00331         typedef uint64 uhash_dword_t;
00332 
00333         if ( (unsigned int) size <= UHASH_KEY_SIZE - sizeof(uhash_word_t) )
00334                 {
00335                 ++hash_cnt_uhash;
00336 
00337                 const uhash_word_t* uhash = (const uhash_word_t *) uhash_key;
00338                 static const uhash_dword_t uhash_prime = (uint64) 1 << 32 + 15;
00339 
00340                 uhash_dword_t sum =
00341                         (uhash_dword_t) (size + 1) *
00342                         ((uhash_dword_t) uhash[0] + 1);
00343 
00344                 int i, j, k;
00345                 const uint8* data = (const uint8*) bytes;
00346                 for ( i = 0, k = 1; i < size; i += sizeof(uhash_word_t), ++k )
00347                         {
00348                         uhash_dword_t x = 0;
00349                         for ( j = 0; unsigned(j) < sizeof(uhash_word_t) && i + j < size; ++j )
00350                                 x = (x << 8) | (uhash_dword_t) data[i+j];
00351 
00352                         sum += ((x + 1) * ((uhash_dword_t) uhash[k] + 1)) %
00353                                 uhash_prime;
00354                         }
00355 
00356                 return hash_t((sum % uhash_prime) & 0xffffffff);
00357                 }
00358 
00359 #endif /* USE_UHASH */
00360 
00361         // Fall back to HMAC/MD5 for longer data (which is usually rare).
00362         hash_t digest[16];
00363         hmac_md5(size, (unsigned char*) bytes, (unsigned char*) digest);
00364         return digest[0];
00365         }

const void* HashKey::Key (   )  const [inline]
 

Definition at line 84 of file Hash.h.

References key.

Referenced by Dictionary::Lookup(), ConnCompressor::PktHdrToPendingConn(), CompositeHash::RecoverVals(), PersistenceSerializer::Register(), and Dictionary::Remove(). 

00084 { return key; }

unsigned int HashKey::MemoryAllocation (   )  const [inline]
 

Definition at line 88 of file Hash.h.

References pad_size(), padded_sizeof, and size.

Referenced by Connection::MemoryAllocation(). 

00088 { return padded_sizeof(*this) + pad_size(size); }

int HashKey::Size (   )  const [inline]
 

Definition at line 85 of file Hash.h.

References size.

Referenced by Dictionary::Insert(), Dictionary::Lookup(), ConnCompressor::PktHdrToPendingConn(), CompositeHash::RecoverOneVal(), CompositeHash::RecoverVals(), PersistenceSerializer::Register(), and Dictionary::Remove(). 

00085 { return size; }

void * HashKey::TakeKey (   ) 
 

Definition at line 208 of file Hash.cc.

References CopyKey(), is_our_dynamic, key, and size.

Referenced by Dictionary::Insert(). 

00209         {
00210         if ( is_our_dynamic )
00211                 {
00212                 is_our_dynamic = 0;
00213                 return key;
00214                 }
00215         else
00216                 return CopyKey(key, size);
00217         }

Member Data Documentation

double HashKey::d [protected]
 

Definition at line 99 of file Hash.h.

int HashKey::hash [protected]
 

Definition at line 105 of file Hash.h.

Referenced by Hash(), and HashKey().

bro_int_t HashKey::i [protected]
 

Definition at line 95 of file Hash.h.

Referenced by HashBytes(), and HashKey().

int HashKey::is_our_dynamic [protected]
 

Definition at line 104 of file Hash.h.

Referenced by HashKey(), TakeKey(), and ~HashKey().

void* HashKey::key [protected]
 

Definition at line 103 of file Hash.h.

Referenced by HashKey(), Key(), TakeKey(), and ~HashKey().

union { ... } HashKey::key_u [protected]
 

Referenced by HashKey().

const void* HashKey::p [protected]
 

Definition at line 100 of file Hash.h.

int HashKey::size [protected]
 

Definition at line 105 of file Hash.h.

Referenced by HashKey(), MemoryAllocation(), Size(), and TakeKey().

The documentation for this class was generated from the following files:
Generated on Wed Sep 14 03:09:48 2005 for bro_docs by doxygen 1.3.5