OpenImageIO
 All Classes Files Friends Macros Pages
hash.h
Go to the documentation of this file.
1 /*
2  Copyright 2008 Larry Gritz and the other authors and contributors.
3  All Rights Reserved.
4 
5  Redistribution and use in source and binary forms, with or without
6  modification, are permitted provided that the following conditions are
7  met:
8  * Redistributions of source code must retain the above copyright
9  notice, this list of conditions and the following disclaimer.
10  * Redistributions in binary form must reproduce the above copyright
11  notice, this list of conditions and the following disclaimer in the
12  documentation and/or other materials provided with the distribution.
13  * Neither the name of the software's owners nor the names of its
14  contributors may be used to endorse or promote products derived from
15  this software without specific prior written permission.
16  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19  A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20  OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22  LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 
28  (This is the Modified BSD License)
29 */
30 
31 
37 
38 #ifndef OPENIMAGEIO_HASH_H
39 #define OPENIMAGEIO_HASH_H
40 
41 #include <vector>
42 
43 #include <boost/version.hpp>
44 
45 #define OIIO_HAVE_BOOST_UNORDERED_MAP
46 #include <boost/unordered_map.hpp>
47 #include <boost/unordered_set.hpp>
48 
49 #include "export.h"
50 #include "version.h"
51 #include "fmath.h" /* for endian */
52 
53 
54 OIIO_NAMESPACE_ENTER {
55 
56 namespace xxhash {
57 
58 // xxhash: http://code.google.com/p/xxhash/
59 // It's BSD licensed.
60 
61 // Calculate the 32-bits hash of "input", of length "len"
62 // "seed" can be used to alter the result
63 unsigned int OIIO_API XXH_fast32 (const void* input, int len,
64  unsigned int seed=1771);
65 
66 // Same as XXH_fast(), but the resulting hash has stronger properties
67 unsigned int OIIO_API XXH_strong32 (const void* input, int len,
68  unsigned int seed=1771);
69 } // end namespace xxhash
70 
71 
72 
73 
74 namespace bjhash {
75 
76 // Bob Jenkins "lookup3" hashes: http://burtleburtle.net/bob/c/lookup3.c
77 // It's in the public domain.
78 
79 inline uint32_t rotl32 (uint32_t x, int k) { return (x<<k) | (x>>(32-k)); }
80 inline uint64_t rotl64 (uint64_t x, int k) { return (x<<k) | (x>>(64-k)); }
81 
82 // Mix up the bits of a, b, and c (changing their values in place).
83 inline void bjmix (uint32_t &a, uint32_t &b, uint32_t &c)
84 {
85  a -= c; a ^= rotl32(c, 4); c += b;
86  b -= a; b ^= rotl32(a, 6); a += c;
87  c -= b; c ^= rotl32(b, 8); b += a;
88  a -= c; a ^= rotl32(c,16); c += b;
89  b -= a; b ^= rotl32(a,19); a += c;
90  c -= b; c ^= rotl32(b, 4); b += a;
91 }
92 
93 // Mix up and combine the bits of a, b, and c (doesn't change them, but
94 // returns a hash of those three original values). 21 ops
95 inline uint32_t bjfinal (uint32_t a, uint32_t b, uint32_t c=0xdeadbeef)
96 {
97  c ^= b; c -= rotl32(b,14);
98  a ^= c; a -= rotl32(c,11);
99  b ^= a; b -= rotl32(a,25);
100  c ^= b; c -= rotl32(b,16);
101  a ^= c; a -= rotl32(c,4);
102  b ^= a; b -= rotl32(a,14);
103  c ^= b; c -= rotl32(b,24);
104  return c;
105 }
106 
107 // Mix up 4 64-bit inputs (non-destructively), and return a 64 bit hash.
108 // Adapted from http://burtleburtle.net/bob/c/SpookyV2.h 33 ops
109 inline uint64_t bjfinal64 (uint64_t h0, uint64_t h1, uint64_t h2, uint64_t h3)
110 {
111  h3 ^= h2; h2 = rotl64(h2,15); h3 += h2;
112  h0 ^= h3; h3 = rotl64(h3,52); h0 += h3;
113  h1 ^= h0; h0 = rotl64(h0,26); h1 += h0;
114  h2 ^= h1; h1 = rotl64(h1,51); h2 += h1;
115  h3 ^= h2; h2 = rotl64(h2,28); h3 += h2;
116  h0 ^= h3; h3 = rotl64(h3,9); h0 += h3;
117  h1 ^= h0; h0 = rotl64(h0,47); h1 += h0;
118  h2 ^= h1; h1 = rotl64(h1,54); h2 += h1;
119  h3 ^= h2; h2 = rotl64(h2,32); h3 += h2;
120  h0 ^= h3; h3 = rotl64(h3,25); h0 += h3;
121  h1 ^= h0; h0 = rotl64(h0,63); h1 += h0;
122  return h1;
123 }
124 
125 // Standard "lookup3" hash, arbitrary length in bytes.
126 uint32_t OIIO_API hashlittle (const void *key, size_t length,
127  uint32_t seed=1771);
128 
129 // Hash an array of 32 bit words -- faster than hashlittle if you know
130 // it's a whole number of 4-byte words.
131 uint32_t OIIO_API hashword (const uint32_t *key, size_t nwords,
132  uint32_t seed=1771);
133 
134 } // end namespace bjhash
135 
136 
137 namespace murmur {
138 
139 // These functions were lifted from the public domain Murmurhash3. We
140 // don't bother using Murmurhash -- in my tests, it was slower than
141 // xxhash in all cases, and comparable to bjhash. But these two fmix
142 // functions are useful for scrambling the bits of a single 32 or 64 bit
143 // value.
144 
145 inline uint32_t fmix (uint32_t h)
146 {
147  h ^= h >> 16;
148  h *= 0x85ebca6b;
149  h ^= h >> 13;
150  h *= 0xc2b2ae35;
151  h ^= h >> 16;
152  return h;
153 }
154 
155 inline uint64_t fmix (uint64_t k)
156 {
157  k ^= k >> 33;
158  k *= 0xff51afd7ed558ccdULL;
159  k ^= k >> 33;
160  k *= 0xc4ceb9fe1a85ec53ULL;
161  k ^= k >> 33;
162  return k;
163 }
164 
165 } // end namespace murmur
166 
167 
168 class CSHA1; // opaque forward declaration
169 
170 
174 class OIIO_API SHA1 {
175 public:
177  SHA1 (const void *data=NULL, size_t size=0);
178  ~SHA1 ();
179 
181  void append (const void *data, size_t size);
183  template<class T> void appendvec (const std::vector<T> &v) {
184  append (&v[0], v.size()*sizeof(T));
185  }
186 
188  struct Hash {
189  unsigned char hash[20];
190  };
191 
193  void gethash (Hash &h);
194 
197  void gethash (void *h) { gethash (*(Hash *)h); }
198 
200  std::string digest ();
201 
203  static std::string digest (const void *data, size_t size) {
204  SHA1 s (data, size); return s.digest();
205  }
206 
207 private:
208  CSHA1 *m_csha1;
209  bool m_final;
210 };
211 
212 
213 } OIIO_NAMESPACE_EXIT
214 
215 #endif // OPENIMAGEIO_HASH_H