Bumping manifests a=b2g-bump
[gecko.git] / netwerk / cache2 / CacheHashUtils.cpp
blob2171d27ae0dcdab2bdd02839df2227d80e2bd89a
1 /* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
5 #include "CacheHashUtils.h"
7 #include "plstr.h"
9 namespace mozilla {
10 namespace net {
12 /**
13 * CacheHash::Hash(const char * key, uint32_t initval)
15 * See http://burtleburtle.net/bob/hash/evahash.html for more information
16 * about this hash function.
18 * This algorithm is used to check the data integrity.
21 static inline void hashmix(uint32_t& a, uint32_t& b, uint32_t& c)
23 a -= b; a -= c; a ^= (c>>13);
24 b -= c; b -= a; b ^= (a<<8);
25 c -= a; c -= b; c ^= (b>>13);
26 a -= b; a -= c; a ^= (c>>12);
27 b -= c; b -= a; b ^= (a<<16);
28 c -= a; c -= b; c ^= (b>>5);
29 a -= b; a -= c; a ^= (c>>3);
30 b -= c; b -= a; b ^= (a<<10);
31 c -= a; c -= b; c ^= (b>>15);
34 CacheHash::Hash32_t
35 CacheHash::Hash(const char *aData, uint32_t aSize, uint32_t aInitval)
37 const uint8_t *k = reinterpret_cast<const uint8_t*>(aData);
38 uint32_t a, b, c, len;
40 // length = PL_strlen(key);
41 /* Set up the internal state */
42 len = aSize;
43 a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */
44 c = aInitval; /* variable initialization of internal state */
46 /*---------------------------------------- handle most of the key */
47 while (len >= 12)
49 a += k[0] + (uint32_t(k[1])<<8) + (uint32_t(k[2])<<16) + (uint32_t(k[3])<<24);
50 b += k[4] + (uint32_t(k[5])<<8) + (uint32_t(k[6])<<16) + (uint32_t(k[7])<<24);
51 c += k[8] + (uint32_t(k[9])<<8) + (uint32_t(k[10])<<16) + (uint32_t(k[11])<<24);
52 hashmix(a, b, c);
53 k += 12; len -= 12;
56 /*------------------------------------- handle the last 11 bytes */
57 c += aSize;
58 switch(len) { /* all the case statements fall through */
59 case 11: c += (uint32_t(k[10])<<24);
60 case 10: c += (uint32_t(k[9])<<16);
61 case 9 : c += (uint32_t(k[8])<<8);
62 /* the low-order byte of c is reserved for the length */
63 case 8 : b += (uint32_t(k[7])<<24);
64 case 7 : b += (uint32_t(k[6])<<16);
65 case 6 : b += (uint32_t(k[5])<<8);
66 case 5 : b += k[4];
67 case 4 : a += (uint32_t(k[3])<<24);
68 case 3 : a += (uint32_t(k[2])<<16);
69 case 2 : a += (uint32_t(k[1])<<8);
70 case 1 : a += k[0];
71 /* case 0: nothing left to add */
73 hashmix(a, b, c);
75 return c;
78 CacheHash::Hash16_t
79 CacheHash::Hash16(const char *aData, uint32_t aSize, uint32_t aInitval)
81 Hash32_t hash = Hash(aData, aSize, aInitval);
82 return (hash & 0xFFFF);
85 NS_IMPL_ISUPPORTS0(CacheHash)
87 CacheHash::CacheHash(uint32_t aInitval)
88 : mA(0x9e3779b9)
89 , mB(0x9e3779b9)
90 , mC(aInitval)
91 , mPos(0)
92 , mBuf(0)
93 , mBufPos(0)
94 , mLength(0)
95 , mFinalized(false)
98 void
99 CacheHash::Feed(uint32_t aVal, uint8_t aLen)
101 switch (mPos) {
102 case 0:
103 mA += aVal;
104 mPos ++;
105 break;
107 case 1:
108 mB += aVal;
109 mPos ++;
110 break;
112 case 2:
113 mPos = 0;
114 if (aLen == 4) {
115 mC += aVal;
116 hashmix(mA, mB, mC);
118 else {
119 mC += aVal << 8;
123 mLength += aLen;
126 void
127 CacheHash::Update(const char *aData, uint32_t aLen)
129 const uint8_t *data = reinterpret_cast<const uint8_t*>(aData);
131 MOZ_ASSERT(!mFinalized);
133 if (mBufPos) {
134 while (mBufPos != 4 && aLen) {
135 mBuf += uint32_t(*data) << 8*mBufPos;
136 data++;
137 mBufPos++;
138 aLen--;
141 if (mBufPos == 4) {
142 mBufPos = 0;
143 Feed(mBuf);
144 mBuf = 0;
148 if (!aLen)
149 return;
151 while (aLen >= 4) {
152 Feed(data[0] + (uint32_t(data[1]) << 8) + (uint32_t(data[2]) << 16) +
153 (uint32_t(data[3]) << 24));
154 data += 4;
155 aLen -= 4;
158 switch (aLen) {
159 case 3: mBuf += data[2] << 16;
160 case 2: mBuf += data[1] << 8;
161 case 1: mBuf += data[0];
164 mBufPos = aLen;
167 CacheHash::Hash32_t
168 CacheHash::GetHash()
170 if (!mFinalized)
172 if (mBufPos) {
173 Feed(mBuf, mBufPos);
175 mC += mLength;
176 hashmix(mA, mB, mC);
177 mFinalized = true;
180 return mC;
183 CacheHash::Hash16_t
184 CacheHash::GetHash16()
186 Hash32_t hash = GetHash();
187 return (hash & 0xFFFF);
190 } // net
191 } // mozilla