Menu
▾
▴
[Csp-commits] svn:csp r1543 - in trunk/CSP/SimData: . Include/SimData Source
|
From: <sv...@ww...> - 2005-05-14 19:55:01
|
Author: mkrose Date: 2005-05-14 12:54:53 -0700 (Sat, 14 May 2005) New Revision: 1543 Modified: trunk/CSP/SimData/CHANGES.current trunk/CSP/SimData/Include/SimData/HashUtility.h trunk/CSP/SimData/Source/HashUtility.cpp Log: Add helper functions for producing 32-bit hashes for integer and string types. These all use the original newhash function to do the work. Add functions for combining 32-bit hashes to produce ordered and un- ordered fingerprints. Browse at: https://www.zerobar.net/viewcvs/viewcvs.cgi?view=rev&rev=1543 Modified: trunk/CSP/SimData/CHANGES.current =================================================================== --- trunk/CSP/SimData/CHANGES.current 2005-05-04 12:07:26 UTC (rev 1542) +++ trunk/CSP/SimData/CHANGES.current 2005-05-14 19:54:53 UTC (rev 1543) @@ -1,6 +1,12 @@ Version 0.4.0 (in progress) =========================== +2005-05-14: onsight + * Add helper functions for producing 32-bit hashes for integer and string + types. These all use the original newhash function to do the work. + Add functions for combining 32-bit hashes to produce ordered and un- + ordered fingerprints. + 2005-04-02: onsight * Add a few convenience methods to LLA. Modified: trunk/CSP/SimData/Include/SimData/HashUtility.h =================================================================== --- trunk/CSP/SimData/Include/SimData/HashUtility.h 2005-05-04 12:07:26 UTC (rev 1542) +++ trunk/CSP/SimData/Include/SimData/HashUtility.h 2005-05-14 19:54:53 UTC (rev 1543) @@ -1,5 +1,5 @@ /* SimData: Data Infrastructure for Simulations - * Copyright (C) 2002 Mark Rose <tm...@st...> + * Copyright (C) 2002, 2005 Mark Rose <tm...@st...> * * This file is part of SimData. * @@ -56,7 +56,14 @@ extern SIMDATA_EXPORT uint32 newhash4_cstring(std::string const &); extern SIMDATA_EXPORT HashT newhasht_cstring(std::string const &); +/** SimData standard 32-bit hash functions. + */ +extern SIMDATA_EXPORT uint32 hash_uint32(uint32); +extern SIMDATA_EXPORT uint32 hash_uint32(uint64); +extern SIMDATA_EXPORT uint32 hash_uint32(std::string const &); +extern SIMDATA_EXPORT uint32 hash_uint32(const char *buffer, const int len); + /** A 64-bit hash value. */ struct SIMDATA_EXPORT HashT { @@ -305,6 +312,19 @@ extern std::ostream & operator<<(std::ostream &o, const hasht &x); +// Combine 32 bit hashes to produce a fingerprint that depends on the +// order of the values. +inline uint32 make_ordered_fingerprint(uint32 x, uint32 y) { + return (x << 11) ^ (x >> 21) ^ y; +} + + +// Combine 32 bit hashes to produce a fingerprint that is independent +// of the order of the values. +inline uint32 make_unordered_fingerprint(uint32 x, uint32 y) { + return x + y; +} + //@} Modified: trunk/CSP/SimData/Source/HashUtility.cpp =================================================================== --- trunk/CSP/SimData/Source/HashUtility.cpp 2005-05-04 12:07:26 UTC (rev 1542) +++ trunk/CSP/SimData/Source/HashUtility.cpp 2005-05-14 19:54:53 UTC (rev 1543) @@ -1,7 +1,7 @@ -/* SimDataCSP: Data Infrastructure for Simulations - * Copyright (C) 2002 Mark Rose <tm...@st...> +/* SimData: Data Infrastructure for Simulations + * Copyright (C) 2002, 2005 Mark Rose <tm...@st...> * - * This file is part of SimDataCSP. + * This file is part of SimData. * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License @@ -24,16 +24,16 @@ * Hash functions utilities * * The hash functions coded here are from "Hash Functions for Hash - * Table Lookup" by Robert J. Jenokins Jr., and are Public Domain. + * Table Lookup" by Robert J. Jenkins Jr., and are Public Domain. * See <http://burtleburtle.net/bob/hash/evahash.html> */ + #include <sstream> #include <iomanip> #include <SimData/HashUtility.h> - NAMESPACE_SIMDATA HASH<const char*> hashstring::h; @@ -41,15 +41,15 @@ // The mixing step #define mix(a,b,c) \ { \ - a=a-b; a=a-c; a=a^(c>>13); \ - b=b-c; b=b-a; b=b^(a<<8); \ - c=c-a; c=c-b; c=c^(b>>13); \ - a=a-b; a=a-c; a=a^(c>>12); \ - b=b-c; b=b-a; b=b^(a<<16); \ - c=c-a; c=c-b; c=c^(b>>5); \ - a=a-b; a=a-c; a=a^(c>>3); \ - b=b-c; b=b-a; b=b^(a<<10); \ - c=c-a; c=c-b; c=c^(b>>15); \ + a=a-b; a=a-c; a=a^(c>>13); \ + b=b-c; b=b-a; b=b^(a<<8); \ + c=c-a; c=c-b; c=c^(b>>13); \ + a=a-b; a=a-c; a=a^(c>>12); \ + b=b-c; b=b-a; b=b^(a<<16); \ + c=c-a; c=c-b; c=c^(b>>5); \ + a=a-b; a=a-c; a=a^(c>>3); \ + b=b-c; b=b-a; b=b^(a<<10); \ + c=c-a; c=c-b; c=c^(b>>15); \ } /** A character string to 32-bit hash function. @@ -60,47 +60,46 @@ * @param length the length of the string in bytes. * @param initval the previous hash, or an arbitrary value */ -uint32 newhash(register uint8 const *k, uint32 length, uint32 initval) +inline uint32 newhash(register uint8 const *k, uint32 length, uint32 initval) { - register uint32 a,b,c; // the internal state - uint32 len; // how many key bytes still need mixing + register uint32 a,b,c; // the internal state + uint32 len; // how many key bytes still need mixing - // Set up the internal state - len = length; - a = b = 0x9e3779b9; // the golden ratio; an arbitrary value - c = initval; // variable initialization of internal state + // Set up the internal state + len = length; + a = b = 0x9e3779b9; // the golden ratio; an arbitrary value + c = initval; // variable initialization of internal state - // handle most of the key + // handle most of the key - while (len >= 12) - { - a=a+(k[0]+((uint32)k[1]<<8)+((uint32)k[2]<<16) +((uint32)k[3]<<24)); - b=b+(k[4]+((uint32)k[5]<<8)+((uint32)k[6]<<16) +((uint32)k[7]<<24)); - c=c+(k[8]+((uint32)k[9]<<8)+((uint32)k[10]<<16)+((uint32)k[11]<<24)); - mix(a,b,c); - k = k+12; len = len-12; - } + while (len >= 12) { + a=a+(k[0]+((uint32)k[1]<<8)+((uint32)k[2]<<16) +((uint32)k[3]<<24)); + b=b+(k[4]+((uint32)k[5]<<8)+((uint32)k[6]<<16) +((uint32)k[7]<<24)); + c=c+(k[8]+((uint32)k[9]<<8)+((uint32)k[10]<<16)+((uint32)k[11]<<24)); + mix(a,b,c); + k = k+12; len = len-12; + } - // handle the last 11 bytes - c = c+length; - switch(len) { // all the case statements fall through - case 11: c=c+((uint32)k[10]<<24); - case 10: c=c+((uint32)k[9]<<16); - case 9 : c=c+((uint32)k[8]<<8); - // the first byte of c is reserved for the length - case 8 : b=b+((uint32)k[7]<<24); - case 7 : b=b+((uint32)k[6]<<16); - case 6 : b=b+((uint32)k[5]<<8); - case 5 : b=b+k[4]; - case 4 : a=a+((uint32)k[3]<<24); - case 3 : a=a+((uint32)k[2]<<16); - case 2 : a=a+((uint32)k[1]<<8); - case 1 : a=a+k[0]; - // case 0: nothing left to add - } - mix(a,b,c); - // report the result - return c; + // handle the last 11 bytes + c = c+length; + switch(len) { // all the case statements fall through + case 11: c=c+((uint32)k[10]<<24); + case 10: c=c+((uint32)k[9]<<16); + case 9 : c=c+((uint32)k[8]<<8); + // the first byte of c is reserved for the length + case 8 : b=b+((uint32)k[7]<<24); + case 7 : b=b+((uint32)k[6]<<16); + case 6 : b=b+((uint32)k[5]<<8); + case 5 : b=b+k[4]; + case 4 : a=a+((uint32)k[3]<<24); + case 3 : a=a+((uint32)k[2]<<16); + case 2 : a=a+((uint32)k[1]<<8); + case 1 : a=a+k[0]; + // case 0: nothing left to add + } + mix(a,b,c); + // report the result + return c; } @@ -114,11 +113,30 @@ */ HashT newhasht_cstring(std::string const &str) { uint32 h0, h1; - h0 = newhash((uint8 const*)str.c_str(), str.size(), 0); - h1 = newhash((uint8 const*)str.c_str(), str.size(), 1); + h0 = newhash(reinterpret_cast<uint8 const*>(str.c_str()), str.size(), 0); + h1 = newhash(reinterpret_cast<uint8 const*>(str.c_str()), str.size(), 1); return HashT(h1, h0); } +// 32-bit hash helpers + +uint32 hash_uint32(uint32 x) { + return newhash(reinterpret_cast<uint8 const*>(&x), 4, 0); +} + +uint32 hash_uint32(uint64 x) { + return newhash(reinterpret_cast<uint8 const*>(&x), 8, 0); +} + +uint32 hash_uint32(std::string const &x) { + return newhash(reinterpret_cast<uint8 const*>(x.c_str()), x.size(), 0); +} + +uint32 hash_uint32(const char *buffer, const int len) { + return newhash(reinterpret_cast<uint8 const*>(buffer), len, 0); +} + + std::string HashT::str() const { std::stringstream repr; repr << *this; |
