Branch data Line data Source code
1 : : // $Id: H3.h 3230 2006-06-08 02:19:25Z vern $
2 : :
3 : : // Copyright 2004, 2005
4 : : // The Regents of the University of California
5 : : // All Rights Reserved
6 : : //
7 : : // Permission to use, copy, modify and distribute any part of this
8 : : // h3.h file, without fee, and without a written agreement is hereby
9 : : // granted, provided that the above copyright notice, this paragraph
10 : : // and the following paragraphs appear in all copies.
11 : : //
12 : : // IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY
13 : : // PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
14 : : // DAMAGES, INCLUDING LOST PROFITS, ARISING OUT OF THE USE OF THIS
15 : : // SOFTWARE, EVEN IF THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF
16 : : // THE POSSIBILITY OF SUCH DAMAGE.
17 : : //
18 : : // THE SOFTWARE PROVIDED HEREIN IS ON AN "AS IS" BASIS, AND THE
19 : : // UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE MAINTENANCE,
20 : : // SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. THE UNIVERSITY
21 : : // OF CALIFORNIA MAKES NO REPRESENTATIONS AND EXTENDS NO WARRANTIES
22 : : // OF ANY KIND, EITHER IMPLIED OR EXPRESS, INCLUDING, BUT NOT LIMITED
23 : : // TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A
24 : : // PARTICULAR PURPOSE, OR THAT THE USE OF THE SOFTWARE WILL NOT INFRINGE
25 : : // ANY PATENT, TRADEMARK OR OTHER RIGHTS.
26 : : //
27 : : // The h3.h file is developed by the CoralReef development team at the
28 : : // University of California, San Diego under the Cooperative Association
29 : : // for Internet Data Analysis (CAIDA) Program. Support for this effort was
30 : : // provided by the CAIDA grant NCR-9711092, DARPA NGI Contract
31 : : // N66001-98-2-8922, DARPA NMS Grant N66001-01-1-8909, NSF Grant ANI-013710
32 : : // and by CAIDA members.
33 : : //
34 : : // Report bugs and suggestions to coral-bugs@caida.org.
35 : :
36 : : // H3 hash function family
37 : : // C++ template implementation by Ken Keys (kkeys@caida.org)
38 : : //
39 : : // Usage:
40 : : // #include <h3.h>
41 : : // const H3<T, N> h;
42 : : // T hashval = h(data, size [, offset]);
43 : : // (T) is the type to be returned by the hash function; must be an integral
44 : : // type, e.g. uint32_t.
45 : : // (N) is the size of the data in bytes (if data is a struct, beware of
46 : : // padding).
47 : : // The hash function hashes the (size) bytes of the data pointed to by (data),
48 : : // starting at (offset). Note: offset affects the hash value, so
49 : : // h(data, size, offset) is not the same as h(data+offset, size, 0).
50 : : // Typically (size) is N and (offset) is 0, but other values can be used to
51 : : // hash a substring of the data. Hashes of substrings can be bitwise-XOR'ed
52 : : // together to get the same result as hashing the full string.
53 : : // Any number of hash functions can be created by creating new instances of H3,
54 : : // with the same or different template parameters. The hash function is
55 : : // randomly generated using random(); you must call srandom() before the
56 : : // H3 constructor if you wish to seed it.
57 : :
58 : :
59 : : #ifndef H3_H
60 : : #define H3_H
61 : :
62 : : template<class T, int N> class H3 {
63 : : T byte_lookup[N][256];
64 : : public:
65 : : H3();
66 : : ~H3() { free(byte_lookup); }
67 : 217155 : T operator()(const void* data, size_t size, size_t offset = 0) const
68 : : {
69 : 217155 : const unsigned char *p = static_cast<const unsigned char*>(data);
70 : 217155 : T result = 0;
71 : :
72 : : // loop optmized with Duff's Device
73 : 217155 : register unsigned n = (size + 7) / 8;
74 [ + + + + + : 217155 : switch (size % 8) {
+ + + - ]
75 [ + + ]: 469403 : case 0: do { result ^= byte_lookup[offset++][*p++];
76 : 267556 : case 7: result ^= byte_lookup[offset++][*p++];
77 : 280643 : case 6: result ^= byte_lookup[offset++][*p++];
78 : 289717 : case 5: result ^= byte_lookup[offset++][*p++];
79 : 330685 : case 4: result ^= byte_lookup[offset++][*p++];
80 : 357617 : case 3: result ^= byte_lookup[offset++][*p++];
81 : 390969 : case 2: result ^= byte_lookup[offset++][*p++];
82 : 409172 : case 1: result ^= byte_lookup[offset++][*p++];
83 : : } while (--n > 0);
84 : : }
85 : :
86 : 217155 : return result;
87 : : }
88 : : };
89 : :
90 : : template<class T, int N>
91 : 3 : H3<T,N>::H3()
92 : : {
93 : : T bit_lookup[N * 8];
94 : :
95 [ + + ]: 771 : for (size_t bit = 0; bit < N * 8; bit++) {
96 : 768 : bit_lookup[bit] = 0;
97 [ + + ]: 2304 : for (size_t i = 0; i < sizeof(T)/2; i++) {
98 : : // assume random() returns at least 16 random bits
99 : 1536 : bit_lookup[bit] = (bit_lookup[bit] << 16) | (random() & 0xFFFF);
100 : : }
101 : : }
102 : :
103 [ + + ]: 99 : for (size_t byte = 0; byte < N; byte++) {
104 [ + + ]: 24672 : for (unsigned val = 0; val < 256; val++) {
105 : 24576 : byte_lookup[byte][val] = 0;
106 [ + + ]: 221184 : for (size_t bit = 0; bit < 8; bit++) {
107 : : // Does this mean byte_lookup[*][0] == 0? -RP
108 [ + + ]: 196608 : if (val & (1 << bit))
109 : 98307 : byte_lookup[byte][val] ^= bit_lookup[byte*8+bit];
110 : : }
111 : : }
112 : : }
113 : : }
114 : :
115 : : #endif //H3_H
|
