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/. */
6 #include "mozilla/SHA1.h"
7 #include "mozilla/Assertions.h"
9 // FIXME: We should probably create a more complete mfbt/Endian.h. This assumes
10 // that any compiler that doesn't define these macros is little endian.
11 #if defined(__BYTE_ORDER__) && defined(__ORDER_LITTLE_ENDIAN__)
12 #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
13 #define MOZ_IS_LITTLE_ENDIAN
16 #define MOZ_IS_LITTLE_ENDIAN
19 using namespace mozilla
;
21 static inline uint32_t SHA_ROTL(uint32_t t
, uint32_t n
)
23 return ((t
<< n
) | (t
>> (32 - n
)));
26 #ifdef MOZ_IS_LITTLE_ENDIAN
27 static inline unsigned SHA_HTONL(unsigned x
) {
28 const unsigned int mask
= 0x00FF00FF;
29 x
= (x
<< 16) | (x
>> 16);
30 return ((x
& mask
) << 8) | ((x
>> 8) & mask
);
33 static inline unsigned SHA_HTONL(unsigned x
) {
38 static void shaCompress(volatile unsigned *X
, const uint32_t * datain
);
40 #define SHA_F1(X,Y,Z) ((((Y)^(Z))&(X))^(Z))
41 #define SHA_F2(X,Y,Z) ((X)^(Y)^(Z))
42 #define SHA_F3(X,Y,Z) (((X)&(Y))|((Z)&((X)|(Y))))
43 #define SHA_F4(X,Y,Z) ((X)^(Y)^(Z))
45 #define SHA_MIX(n,a,b,c) XW(n) = SHA_ROTL(XW(a)^XW(b)^XW(c)^XW(n), 1)
47 SHA1Sum::SHA1Sum() : size(0), mDone(false)
49 // Initialize H with constants from FIPS180-1.
57 /* Explanation of H array and index values:
58 * The context's H array is actually the concatenation of two arrays
59 * defined by SHA1, the H array of state variables (5 elements),
60 * and the W array of intermediate values, of which there are 16 elements.
61 * The W array starts at H[5], that is W[0] is H[5].
62 * Although these values are defined as 32-bit values, we use 64-bit
63 * variables to hold them because the AMD64 stores 64 bit values in
64 * memory MUCH faster than it stores any smaller values.
66 * Rather than passing the context structure to shaCompress, we pass
67 * this combined array of H and W values. We do not pass the address
68 * of the first element of this array, but rather pass the address of an
69 * element in the middle of the array, element X. Presently X[0] is H[11].
70 * So we pass the address of H[11] as the address of array X to shaCompress.
71 * Then shaCompress accesses the members of the array using positive AND
74 * Pictorially: (each element is 8 bytes)
75 * H | H0 H1 H2 H3 H4 W0 W1 W2 W3 W4 W5 W6 W7 W8 W9 Wa Wb Wc Wd We Wf |
76 * X |-11-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 X0 X1 X2 X3 X4 X5 X6 X7 X8 X9 |
78 * The byte offset from X[0] to any member of H and W is always
79 * representable in a signed 8-bit value, which will be encoded
80 * as a single byte offset in the X86-64 instruction set.
81 * If we didn't pass the address of H[11], and instead passed the
82 * address of H[0], the offsets to elements H[16] and above would be
83 * greater than 127, not representable in a signed 8-bit value, and the
84 * x86-64 instruction set would encode every such offset as a 32-bit
85 * signed number in each instruction that accessed element H[16] or
86 * higher. This results in much bigger and slower code.
88 #define H2X 11 /* X[0] is H[11], and H[0] is X[-11] */
89 #define W2X 6 /* X[0] is W[6], and W[0] is X[-6] */
92 * SHA: Add data to context.
94 void SHA1Sum::update(const uint8_t *dataIn
, uint32_t len
)
97 register unsigned int lenB
;
98 register unsigned int togo
;
103 /* accumulate the byte count. */
104 lenB
= (unsigned int)(size
) & 63U;
109 * Read the data into W and process blocks as they get full
115 memcpy(u
.b
+ lenB
, dataIn
, togo
);
118 lenB
= (lenB
+ togo
) & 63U;
120 shaCompress(&H
[H2X
], u
.w
);
125 shaCompress(&H
[H2X
], (uint32_t *)dataIn
);
129 memcpy(u
.b
, dataIn
, len
);
135 * SHA: Generate hash value
137 void SHA1Sum::finish(uint8_t hashout
[20])
140 register uint64_t size2
= size
;
141 register uint32_t lenB
= (uint32_t)size2
& 63;
143 static const uint8_t bulk_pad
[64] = { 0x80,0,0,0,0,0,0,0,0,0,
144 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
145 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 };
148 * Pad with a binary 1 (e.g. 0x80), then zeroes, then length in bits
151 update(bulk_pad
, (((55+64) - lenB
) & 63) + 1);
152 MOZ_ASSERT(((uint32_t)size
& 63) == 56);
153 /* Convert size from bytes to bits. */
155 u
.w
[14] = SHA_HTONL((uint32_t)(size2
>> 32));
156 u
.w
[15] = SHA_HTONL((uint32_t)size2
);
157 shaCompress(&H
[H2X
], u
.w
);
162 u
.w
[0] = SHA_HTONL(H
[0]);
163 u
.w
[1] = SHA_HTONL(H
[1]);
164 u
.w
[2] = SHA_HTONL(H
[2]);
165 u
.w
[3] = SHA_HTONL(H
[3]);
166 u
.w
[4] = SHA_HTONL(H
[4]);
167 memcpy(hashout
, u
.w
, 20);
172 * SHA: Compression function, unrolled.
174 * Some operations in shaCompress are done as 5 groups of 16 operations.
175 * Others are done as 4 groups of 20 operations.
176 * The code below shows that structure.
178 * The functions that compute the new values of the 5 state variables
179 * A-E are done in 4 groups of 20 operations (or you may also think
180 * of them as being done in 16 groups of 5 operations). They are
181 * done by the SHA_RNDx macros below, in the right column.
183 * The functions that set the 16 values of the W array are done in
184 * 5 groups of 16 operations. The first group is done by the
185 * LOAD macros below, the latter 4 groups are done by SHA_MIX below,
186 * in the left column.
188 * gcc's optimizer observes that each member of the W array is assigned
189 * a value 5 times in this code. It reduces the number of store
190 * operations done to the W array in the context (that is, in the X array)
191 * by creating a W array on the stack, and storing the W values there for
192 * the first 4 groups of operations on W, and storing the values in the
193 * context's W array only in the fifth group. This is undesirable.
194 * It is MUCH bigger code than simply using the context's W array, because
195 * all the offsets to the W array in the stack are 32-bit signed offsets,
196 * and it is no faster than storing the values in the context's W array.
198 * The original code for sha_fast.c prevented this creation of a separate
199 * W array in the stack by creating a W array of 80 members, each of
200 * whose elements is assigned only once. It also separated the computations
201 * of the W array values and the computations of the values for the 5
202 * state variables into two separate passes, W's, then A-E's so that the
203 * second pass could be done all in registers (except for accessing the W
204 * array) on machines with fewer registers. The method is suboptimal
205 * for machines with enough registers to do it all in one pass, and it
206 * necessitates using many instructions with 32-bit offsets.
208 * This code eliminates the separate W array on the stack by a completely
209 * different means: by declaring the X array volatile. This prevents
210 * the optimizer from trying to reduce the use of the X array by the
211 * creation of a MORE expensive W array on the stack. The result is
212 * that all instructions use signed 8-bit offsets and not 32-bit offsets.
214 * The combination of this code and the -O3 optimizer flag on GCC 3.4.3
215 * results in code that is 3 times faster than the previous NSS sha_fast
219 shaCompress(volatile unsigned *X
, const uint32_t *inbuf
)
221 register unsigned A
, B
, C
, D
, E
;
224 #define XH(n) X[n-H2X]
225 #define XW(n) X[n-W2X]
227 #define K0 0x5a827999L
228 #define K1 0x6ed9eba1L
229 #define K2 0x8f1bbcdcL
230 #define K3 0xca62c1d6L
232 #define SHA_RND1(a,b,c,d,e,n) \
233 a = SHA_ROTL(b,5)+SHA_F1(c,d,e)+a+XW(n)+K0; c=SHA_ROTL(c,30)
234 #define SHA_RND2(a,b,c,d,e,n) \
235 a = SHA_ROTL(b,5)+SHA_F2(c,d,e)+a+XW(n)+K1; c=SHA_ROTL(c,30)
236 #define SHA_RND3(a,b,c,d,e,n) \
237 a = SHA_ROTL(b,5)+SHA_F3(c,d,e)+a+XW(n)+K2; c=SHA_ROTL(c,30)
238 #define SHA_RND4(a,b,c,d,e,n) \
239 a = SHA_ROTL(b,5)+SHA_F4(c,d,e)+a+XW(n)+K3; c=SHA_ROTL(c,30)
241 #define LOAD(n) XW(n) = SHA_HTONL(inbuf[n])
249 LOAD(0); SHA_RND1(E
,A
,B
,C
,D
, 0);
250 LOAD(1); SHA_RND1(D
,E
,A
,B
,C
, 1);
251 LOAD(2); SHA_RND1(C
,D
,E
,A
,B
, 2);
252 LOAD(3); SHA_RND1(B
,C
,D
,E
,A
, 3);
253 LOAD(4); SHA_RND1(A
,B
,C
,D
,E
, 4);
254 LOAD(5); SHA_RND1(E
,A
,B
,C
,D
, 5);
255 LOAD(6); SHA_RND1(D
,E
,A
,B
,C
, 6);
256 LOAD(7); SHA_RND1(C
,D
,E
,A
,B
, 7);
257 LOAD(8); SHA_RND1(B
,C
,D
,E
,A
, 8);
258 LOAD(9); SHA_RND1(A
,B
,C
,D
,E
, 9);
259 LOAD(10); SHA_RND1(E
,A
,B
,C
,D
,10);
260 LOAD(11); SHA_RND1(D
,E
,A
,B
,C
,11);
261 LOAD(12); SHA_RND1(C
,D
,E
,A
,B
,12);
262 LOAD(13); SHA_RND1(B
,C
,D
,E
,A
,13);
263 LOAD(14); SHA_RND1(A
,B
,C
,D
,E
,14);
264 LOAD(15); SHA_RND1(E
,A
,B
,C
,D
,15);
266 SHA_MIX( 0, 13, 8, 2); SHA_RND1(D
,E
,A
,B
,C
, 0);
267 SHA_MIX( 1, 14, 9, 3); SHA_RND1(C
,D
,E
,A
,B
, 1);
268 SHA_MIX( 2, 15, 10, 4); SHA_RND1(B
,C
,D
,E
,A
, 2);
269 SHA_MIX( 3, 0, 11, 5); SHA_RND1(A
,B
,C
,D
,E
, 3);
271 SHA_MIX( 4, 1, 12, 6); SHA_RND2(E
,A
,B
,C
,D
, 4);
272 SHA_MIX( 5, 2, 13, 7); SHA_RND2(D
,E
,A
,B
,C
, 5);
273 SHA_MIX( 6, 3, 14, 8); SHA_RND2(C
,D
,E
,A
,B
, 6);
274 SHA_MIX( 7, 4, 15, 9); SHA_RND2(B
,C
,D
,E
,A
, 7);
275 SHA_MIX( 8, 5, 0, 10); SHA_RND2(A
,B
,C
,D
,E
, 8);
276 SHA_MIX( 9, 6, 1, 11); SHA_RND2(E
,A
,B
,C
,D
, 9);
277 SHA_MIX(10, 7, 2, 12); SHA_RND2(D
,E
,A
,B
,C
,10);
278 SHA_MIX(11, 8, 3, 13); SHA_RND2(C
,D
,E
,A
,B
,11);
279 SHA_MIX(12, 9, 4, 14); SHA_RND2(B
,C
,D
,E
,A
,12);
280 SHA_MIX(13, 10, 5, 15); SHA_RND2(A
,B
,C
,D
,E
,13);
281 SHA_MIX(14, 11, 6, 0); SHA_RND2(E
,A
,B
,C
,D
,14);
282 SHA_MIX(15, 12, 7, 1); SHA_RND2(D
,E
,A
,B
,C
,15);
284 SHA_MIX( 0, 13, 8, 2); SHA_RND2(C
,D
,E
,A
,B
, 0);
285 SHA_MIX( 1, 14, 9, 3); SHA_RND2(B
,C
,D
,E
,A
, 1);
286 SHA_MIX( 2, 15, 10, 4); SHA_RND2(A
,B
,C
,D
,E
, 2);
287 SHA_MIX( 3, 0, 11, 5); SHA_RND2(E
,A
,B
,C
,D
, 3);
288 SHA_MIX( 4, 1, 12, 6); SHA_RND2(D
,E
,A
,B
,C
, 4);
289 SHA_MIX( 5, 2, 13, 7); SHA_RND2(C
,D
,E
,A
,B
, 5);
290 SHA_MIX( 6, 3, 14, 8); SHA_RND2(B
,C
,D
,E
,A
, 6);
291 SHA_MIX( 7, 4, 15, 9); SHA_RND2(A
,B
,C
,D
,E
, 7);
293 SHA_MIX( 8, 5, 0, 10); SHA_RND3(E
,A
,B
,C
,D
, 8);
294 SHA_MIX( 9, 6, 1, 11); SHA_RND3(D
,E
,A
,B
,C
, 9);
295 SHA_MIX(10, 7, 2, 12); SHA_RND3(C
,D
,E
,A
,B
,10);
296 SHA_MIX(11, 8, 3, 13); SHA_RND3(B
,C
,D
,E
,A
,11);
297 SHA_MIX(12, 9, 4, 14); SHA_RND3(A
,B
,C
,D
,E
,12);
298 SHA_MIX(13, 10, 5, 15); SHA_RND3(E
,A
,B
,C
,D
,13);
299 SHA_MIX(14, 11, 6, 0); SHA_RND3(D
,E
,A
,B
,C
,14);
300 SHA_MIX(15, 12, 7, 1); SHA_RND3(C
,D
,E
,A
,B
,15);
302 SHA_MIX( 0, 13, 8, 2); SHA_RND3(B
,C
,D
,E
,A
, 0);
303 SHA_MIX( 1, 14, 9, 3); SHA_RND3(A
,B
,C
,D
,E
, 1);
304 SHA_MIX( 2, 15, 10, 4); SHA_RND3(E
,A
,B
,C
,D
, 2);
305 SHA_MIX( 3, 0, 11, 5); SHA_RND3(D
,E
,A
,B
,C
, 3);
306 SHA_MIX( 4, 1, 12, 6); SHA_RND3(C
,D
,E
,A
,B
, 4);
307 SHA_MIX( 5, 2, 13, 7); SHA_RND3(B
,C
,D
,E
,A
, 5);
308 SHA_MIX( 6, 3, 14, 8); SHA_RND3(A
,B
,C
,D
,E
, 6);
309 SHA_MIX( 7, 4, 15, 9); SHA_RND3(E
,A
,B
,C
,D
, 7);
310 SHA_MIX( 8, 5, 0, 10); SHA_RND3(D
,E
,A
,B
,C
, 8);
311 SHA_MIX( 9, 6, 1, 11); SHA_RND3(C
,D
,E
,A
,B
, 9);
312 SHA_MIX(10, 7, 2, 12); SHA_RND3(B
,C
,D
,E
,A
,10);
313 SHA_MIX(11, 8, 3, 13); SHA_RND3(A
,B
,C
,D
,E
,11);
315 SHA_MIX(12, 9, 4, 14); SHA_RND4(E
,A
,B
,C
,D
,12);
316 SHA_MIX(13, 10, 5, 15); SHA_RND4(D
,E
,A
,B
,C
,13);
317 SHA_MIX(14, 11, 6, 0); SHA_RND4(C
,D
,E
,A
,B
,14);
318 SHA_MIX(15, 12, 7, 1); SHA_RND4(B
,C
,D
,E
,A
,15);
320 SHA_MIX( 0, 13, 8, 2); SHA_RND4(A
,B
,C
,D
,E
, 0);
321 SHA_MIX( 1, 14, 9, 3); SHA_RND4(E
,A
,B
,C
,D
, 1);
322 SHA_MIX( 2, 15, 10, 4); SHA_RND4(D
,E
,A
,B
,C
, 2);
323 SHA_MIX( 3, 0, 11, 5); SHA_RND4(C
,D
,E
,A
,B
, 3);
324 SHA_MIX( 4, 1, 12, 6); SHA_RND4(B
,C
,D
,E
,A
, 4);
325 SHA_MIX( 5, 2, 13, 7); SHA_RND4(A
,B
,C
,D
,E
, 5);
326 SHA_MIX( 6, 3, 14, 8); SHA_RND4(E
,A
,B
,C
,D
, 6);
327 SHA_MIX( 7, 4, 15, 9); SHA_RND4(D
,E
,A
,B
,C
, 7);
328 SHA_MIX( 8, 5, 0, 10); SHA_RND4(C
,D
,E
,A
,B
, 8);
329 SHA_MIX( 9, 6, 1, 11); SHA_RND4(B
,C
,D
,E
,A
, 9);
330 SHA_MIX(10, 7, 2, 12); SHA_RND4(A
,B
,C
,D
,E
,10);
331 SHA_MIX(11, 8, 3, 13); SHA_RND4(E
,A
,B
,C
,D
,11);
332 SHA_MIX(12, 9, 4, 14); SHA_RND4(D
,E
,A
,B
,C
,12);
333 SHA_MIX(13, 10, 5, 15); SHA_RND4(C
,D
,E
,A
,B
,13);
334 SHA_MIX(14, 11, 6, 0); SHA_RND4(B
,C
,D
,E
,A
,14);
335 SHA_MIX(15, 12, 7, 1); SHA_RND4(A
,B
,C
,D
,E
,15);