Line data Source code
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/. */
4 :
5 : #include "CacheHashUtils.h"
6 :
7 : #include "mozilla/BasePrincipal.h"
8 : #include "plstr.h"
9 :
10 : namespace mozilla {
11 : namespace net {
12 :
13 : /**
14 : * CacheHash::Hash(const char * key, uint32_t initval)
15 : *
16 : * See http://burtleburtle.net/bob/hash/evahash.html for more information
17 : * about this hash function.
18 : *
19 : * This algorithm is used to check the data integrity.
20 : */
21 :
22 1303 : static inline void hashmix(uint32_t& a, uint32_t& b, uint32_t& c)
23 : {
24 1303 : a -= b; a -= c; a ^= (c>>13);
25 1303 : b -= c; b -= a; b ^= (a<<8);
26 1303 : c -= a; c -= b; c ^= (b>>13);
27 1303 : a -= b; a -= c; a ^= (c>>12);
28 1303 : b -= c; b -= a; b ^= (a<<16);
29 1303 : c -= a; c -= b; c ^= (b>>5);
30 1303 : a -= b; a -= c; a ^= (c>>3);
31 1303 : b -= c; b -= a; b ^= (a<<10);
32 1303 : c -= a; c -= b; c ^= (b>>15);
33 1303 : }
34 :
35 : CacheHash::Hash32_t
36 13 : CacheHash::Hash(const char *aData, uint32_t aSize, uint32_t aInitval)
37 : {
38 13 : const uint8_t *k = reinterpret_cast<const uint8_t*>(aData);
39 : uint32_t a, b, c, len;
40 :
41 : /* Set up the internal state */
42 13 : len = aSize;
43 13 : a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */
44 13 : c = aInitval; /* variable initialization of internal state */
45 :
46 : /*---------------------------------------- handle most of the key */
47 2593 : while (len >= 12)
48 : {
49 1290 : a += k[0] + (uint32_t(k[1])<<8) + (uint32_t(k[2])<<16) + (uint32_t(k[3])<<24);
50 1290 : b += k[4] + (uint32_t(k[5])<<8) + (uint32_t(k[6])<<16) + (uint32_t(k[7])<<24);
51 1290 : c += k[8] + (uint32_t(k[9])<<8) + (uint32_t(k[10])<<16) + (uint32_t(k[11])<<24);
52 1290 : hashmix(a, b, c);
53 1290 : k += 12; len -= 12;
54 : }
55 :
56 : /*------------------------------------- handle the last 11 bytes */
57 13 : c += aSize;
58 13 : switch(len) { /* all the case statements fall through */
59 1 : case 11: c += (uint32_t(k[10])<<24); MOZ_FALLTHROUGH;
60 1 : case 10: c += (uint32_t(k[9])<<16); MOZ_FALLTHROUGH;
61 1 : case 9 : c += (uint32_t(k[8])<<8); MOZ_FALLTHROUGH;
62 : /* the low-order byte of c is reserved for the length */
63 2 : case 8 : b += (uint32_t(k[7])<<24); MOZ_FALLTHROUGH;
64 4 : case 7 : b += (uint32_t(k[6])<<16); MOZ_FALLTHROUGH;
65 5 : case 6 : b += (uint32_t(k[5])<<8); MOZ_FALLTHROUGH;
66 6 : case 5 : b += k[4]; MOZ_FALLTHROUGH;
67 9 : case 4 : a += (uint32_t(k[3])<<24); MOZ_FALLTHROUGH;
68 10 : case 3 : a += (uint32_t(k[2])<<16); MOZ_FALLTHROUGH;
69 11 : case 2 : a += (uint32_t(k[1])<<8); MOZ_FALLTHROUGH;
70 11 : case 1 : a += k[0];
71 : /* case 0: nothing left to add */
72 : }
73 13 : hashmix(a, b, c);
74 :
75 13 : return c;
76 : }
77 :
78 : CacheHash::Hash16_t
79 6 : CacheHash::Hash16(const char *aData, uint32_t aSize, uint32_t aInitval)
80 : {
81 6 : Hash32_t hash = Hash(aData, aSize, aInitval);
82 6 : return (hash & 0xFFFF);
83 : }
84 :
85 0 : NS_IMPL_ISUPPORTS0(CacheHash)
86 :
87 0 : 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 0 : , mFinalized(false)
96 0 : {}
97 :
98 : void
99 0 : CacheHash::Feed(uint32_t aVal, uint8_t aLen)
100 : {
101 0 : switch (mPos) {
102 : case 0:
103 0 : mA += aVal;
104 0 : mPos ++;
105 0 : break;
106 :
107 : case 1:
108 0 : mB += aVal;
109 0 : mPos ++;
110 0 : break;
111 :
112 : case 2:
113 0 : mPos = 0;
114 0 : if (aLen == 4) {
115 0 : mC += aVal;
116 0 : hashmix(mA, mB, mC);
117 : }
118 : else {
119 0 : mC += aVal << 8;
120 : }
121 : }
122 :
123 0 : mLength += aLen;
124 0 : }
125 :
126 : void
127 0 : CacheHash::Update(const char *aData, uint32_t aLen)
128 : {
129 0 : const uint8_t *data = reinterpret_cast<const uint8_t*>(aData);
130 :
131 0 : MOZ_ASSERT(!mFinalized);
132 :
133 0 : if (mBufPos) {
134 0 : while (mBufPos != 4 && aLen) {
135 0 : mBuf += uint32_t(*data) << 8*mBufPos;
136 0 : data++;
137 0 : mBufPos++;
138 0 : aLen--;
139 : }
140 :
141 0 : if (mBufPos == 4) {
142 0 : mBufPos = 0;
143 0 : Feed(mBuf);
144 0 : mBuf = 0;
145 : }
146 : }
147 :
148 0 : if (!aLen)
149 0 : return;
150 :
151 0 : while (aLen >= 4) {
152 0 : Feed(data[0] + (uint32_t(data[1]) << 8) + (uint32_t(data[2]) << 16) +
153 0 : (uint32_t(data[3]) << 24));
154 0 : data += 4;
155 0 : aLen -= 4;
156 : }
157 :
158 0 : switch (aLen) {
159 0 : case 3: mBuf += data[2] << 16; MOZ_FALLTHROUGH;
160 0 : case 2: mBuf += data[1] << 8; MOZ_FALLTHROUGH;
161 0 : case 1: mBuf += data[0];
162 : }
163 :
164 0 : mBufPos = aLen;
165 : }
166 :
167 : CacheHash::Hash32_t
168 0 : CacheHash::GetHash()
169 : {
170 0 : if (!mFinalized)
171 : {
172 0 : if (mBufPos) {
173 0 : Feed(mBuf, mBufPos);
174 : }
175 0 : mC += mLength;
176 0 : hashmix(mA, mB, mC);
177 0 : mFinalized = true;
178 : }
179 :
180 0 : return mC;
181 : }
182 :
183 : CacheHash::Hash16_t
184 0 : CacheHash::GetHash16()
185 : {
186 0 : Hash32_t hash = GetHash();
187 0 : return (hash & 0xFFFF);
188 : }
189 :
190 : OriginAttrsHash
191 5 : GetOriginAttrsHash(const mozilla::OriginAttributes &aOA)
192 : {
193 10 : nsAutoCString suffix;
194 5 : aOA.CreateSuffix(suffix);
195 :
196 5 : SHA1Sum sum;
197 : SHA1Sum::Hash hash;
198 5 : sum.update(suffix.BeginReading(), suffix.Length());
199 5 : sum.finish(hash);
200 :
201 10 : return BigEndian::readUint64(&hash);
202 : }
203 :
204 : } // namespace net
205 : } // namespace mozilla
|
