VirtualBox

source: vbox/trunk/src/VBox/Runtime/common/checksum/alt-sha1.cpp@ 51879

Last change on this file since 51879 was 51879, checked in by vboxsync, 10 years ago

alt-sha1.cpp: Save an operation in both Ch() and Maj(). The Maj optimization is easier to figure out than the Ch() one.
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 13.7 KB
Line 
1/* $Id: alt-sha1.cpp 51879 2014-07-05 22:51:29Z vboxsync $ */
2/** @file
3 * IPRT - SHA-1 hash functions, Alternative Implementation.
4 */
5
6/*
7 * Copyright (C) 2009-2014 Oracle Corporation
8 *
9 * This file is part of VirtualBox Open Source Edition (OSE), as
10 * available from http://www.virtualbox.org. This file is free software;
11 * you can redistribute it and/or modify it under the terms of the GNU
12 * General Public License (GPL) as published by the Free Software
13 * Foundation, in version 2 as it comes in the "COPYING" file of the
14 * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
15 * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
16 *
17 * The contents of this file may alternatively be used under the terms
18 * of the Common Development and Distribution License Version 1.0
19 * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
20 * VirtualBox OSE distribution, in which case the provisions of the
21 * CDDL are applicable instead of those of the GPL.
22 *
23 * You may elect to license modified versions of this file under the
24 * terms and conditions of either the GPL or the CDDL or both.
25 */
26
27
28/*******************************************************************************
29* Defined Constants And Macros *
30*******************************************************************************/
31/** The SHA-1 block size (in bytes). */
32#define RTSHA1_BLOCK_SIZE 64U
33
34
35/*******************************************************************************
36* Header Files *
37*******************************************************************************/
38#include "internal/iprt.h"
39#include <iprt/types.h>
40#include <iprt/assert.h>
41#include <iprt/asm.h>
42#include <iprt/string.h>
43
44
45/** Our private context structure. */
46typedef struct RTSHA1ALTPRIVATECTX
47{
48 /** The W array.
49 * Buffering happens in the first 16 words, converted from big endian to host
50 * endian immediately before processing. The amount of buffered data is kept
51 * in the 6 least significant bits of cbMessage. */
52 uint32_t auW[80];
53 /** The message length (in bytes). */
54 uint64_t cbMessage;
55
56 /** The 5 hash values. */
57 uint32_t auH[5];
58} RTSHA1ALTPRIVATECTX;
59
60#define RT_SHA1_PRIVATE_ALT_CONTEXT
61#include <iprt/sha.h>
62
63
64AssertCompile(RT_SIZEOFMEMB(RTSHA1CONTEXT, abPadding) >= RT_SIZEOFMEMB(RTSHA1CONTEXT, AltPrivate));
65AssertCompileMemberSize(RTSHA1ALTPRIVATECTX, auH, RTSHA1_HASH_SIZE);
66
67
68
69
70RTDECL(void) RTSha1Init(PRTSHA1CONTEXT pCtx)
71{
72 pCtx->AltPrivate.cbMessage = 0;
73 pCtx->AltPrivate.auH[0] = UINT32_C(0x67452301);
74 pCtx->AltPrivate.auH[1] = UINT32_C(0xefcdab89);
75 pCtx->AltPrivate.auH[2] = UINT32_C(0x98badcfe);
76 pCtx->AltPrivate.auH[3] = UINT32_C(0x10325476);
77 pCtx->AltPrivate.auH[4] = UINT32_C(0xc3d2e1f0);
78}
79RT_EXPORT_SYMBOL(RTSha1Init);
80
81
82/**
83 * Initializes the auW array from the specfied input block.
84 *
85 * @param pCtx The SHA1 context.
86 * @param pbBlock The block. Must be 32-bit aligned.
87 */
88DECLINLINE(void) rtSha1BlockInit(PRTSHA1CONTEXT pCtx, uint8_t const *pbBlock)
89{
90 uint32_t const *pu32Block = (uint32_t const *)pbBlock;
91 Assert(!((uintptr_t)pu32Block & 3));
92
93 unsigned iWord;
94 for (iWord = 0; iWord < 16; iWord++)
95 pCtx->AltPrivate.auW[iWord] = RT_BE2H_U32(pu32Block[iWord]);
96
97 for (; iWord < RT_ELEMENTS(pCtx->AltPrivate.auW); iWord++)
98 {
99 uint32_t u32 = pCtx->AltPrivate.auW[iWord - 16];
100 u32 ^= pCtx->AltPrivate.auW[iWord - 14];
101 u32 ^= pCtx->AltPrivate.auW[iWord - 8];
102 u32 ^= pCtx->AltPrivate.auW[iWord - 3];
103 pCtx->AltPrivate.auW[iWord] = ASMRotateLeftU32(u32, 1);
104 }
105}
106
107
108/**
109 * Initializes the auW array from data buffered in the first part of the array.
110 *
111 * @param pCtx The SHA1 context.
112 */
113DECLINLINE(void) rtSha1BlockInitBuffered(PRTSHA1CONTEXT pCtx)
114{
115 unsigned iWord;
116 for (iWord = 0; iWord < 16; iWord++)
117 pCtx->AltPrivate.auW[iWord] = RT_BE2H_U32(pCtx->AltPrivate.auW[iWord]);
118
119 for (; iWord < RT_ELEMENTS(pCtx->AltPrivate.auW); iWord++)
120 {
121 uint32_t u32 = pCtx->AltPrivate.auW[iWord - 16];
122 u32 ^= pCtx->AltPrivate.auW[iWord - 14];
123 u32 ^= pCtx->AltPrivate.auW[iWord - 8];
124 u32 ^= pCtx->AltPrivate.auW[iWord - 3];
125 pCtx->AltPrivate.auW[iWord] = ASMRotateLeftU32(u32, 1);
126 }
127}
128
129
130/** Function 4.1, Ch(x,y,z). */
131DECL_FORCE_INLINE(uint32_t) rtSha1Ch(uint32_t uX, uint32_t uY, uint32_t uZ)
132{
133#if 1
134 /* Optimization that saves one operation and probably a temporary variable. */
135 uint32_t uResult = uY;
136 uResult ^= uZ;
137 uResult &= uX;
138 uResult ^= uZ;
139 return uResult;
140#else
141 /* The original. */
142 uint32_t uResult = uX & uY;
143 uResult ^= ~uX & uZ;
144 return uResult;
145#endif
146}
147
148
149/** Function 4.1, Parity(x,y,z). */
150DECL_FORCE_INLINE(uint32_t) rtSha1Parity(uint32_t uX, uint32_t uY, uint32_t uZ)
151{
152 uint32_t uResult = uX;
153 uResult ^= uY;
154 uResult ^= uZ;
155 return uResult;
156}
157
158
159/** Function 4.1, Maj(x,y,z). */
160DECL_FORCE_INLINE(uint32_t) rtSha1Maj(uint32_t uX, uint32_t uY, uint32_t uZ)
161{
162#if 1
163 /* Optimization that save one operation and probably a temporary variable. */
164 uint32_t uResult = uY;
165 uResult ^= uZ;
166 uResult &= uX;
167 uResult ^= uY & uZ;
168 return uResult;
169#else
170 /* The original. */
171 uint32_t uResult = (uX & uY);
172 uResult |= (uX & uZ);
173 uResult |= (uY & uZ);
174 return uResult;
175#endif
176}
177
178
179/**
180 * Process the current block.
181 *
182 * Requires one of the rtSha1BlockInit functions to be called first.
183 *
184 * @param pCtx The SHA1 context.
185 */
186static void rtSha1BlockProcess(PRTSHA1CONTEXT pCtx)
187{
188 uint32_t uA = pCtx->AltPrivate.auH[0];
189 uint32_t uB = pCtx->AltPrivate.auH[1];
190 uint32_t uC = pCtx->AltPrivate.auH[2];
191 uint32_t uD = pCtx->AltPrivate.auH[3];
192 uint32_t uE = pCtx->AltPrivate.auH[4];
193
194#if 1 /* Fully unrolled version. */
195 register uint32_t const *puW = &pCtx->AltPrivate.auW[0];
196# define SHA1_BODY(a_uW, a_uK, a_fnFt, a_uA, a_uB, a_uC, a_uD, a_uE) \
197 do { \
198 a_uE += a_uW; \
199 a_uE += (a_uK); \
200 a_uE += ASMRotateLeftU32(a_uA, 5); \
201 a_uE += a_fnFt(a_uB, a_uC, a_uD); \
202 a_uB = ASMRotateLeftU32(a_uB, 30); \
203 } while (0)
204# define FIVE_ITERATIONS(a_iStart, a_uK, a_fnFt) \
205 do { \
206 SHA1_BODY(/*puW[a_iStart + 0]*/ *puW++, a_uK, a_fnFt, uA, uB, uC, uD, uE); \
207 SHA1_BODY(/*puW[a_iStart + 1]*/ *puW++, a_uK, a_fnFt, uE, uA, uB, uC, uD); \
208 SHA1_BODY(/*puW[a_iStart + 2]*/ *puW++, a_uK, a_fnFt, uD, uE, uA, uB, uC); \
209 SHA1_BODY(/*puW[a_iStart + 3]*/ *puW++, a_uK, a_fnFt, uC, uD, uE, uA, uB); \
210 SHA1_BODY(/*puW[a_iStart + 4]*/ *puW++, a_uK, a_fnFt, uB, uC, uD, uE, uA); \
211 } while (0)
212# if 0 /* Variation that reduces the code size by a factor of 4 without much loss in preformance. */
213# define TWENTY_ITERATIONS(a_iFirst, a_uK, a_fnFt) \
214 do { unsigned i = 4; while (i-- > 0) FIVE_ITERATIONS(a_iFirst + (3 - i) * 5, a_uK, a_fnFt); } while (0)
215 /*for (unsigned i = a_iFirst; i < (a_iFirst + 20); i += 5) FIVE_ITERATIONS(i, a_uK, a_fnFt);*/
216# else
217# define TWENTY_ITERATIONS(a_iFirst, a_uK, a_fnFt) \
218 do { \
219 FIVE_ITERATIONS(a_iFirst + 0, a_uK, a_fnFt); \
220 FIVE_ITERATIONS(a_iFirst + 5, a_uK, a_fnFt); \
221 FIVE_ITERATIONS(a_iFirst + 10, a_uK, a_fnFt); \
222 FIVE_ITERATIONS(a_iFirst + 15, a_uK, a_fnFt); \
223 } while (0)
224# endif
225 TWENTY_ITERATIONS( 0, UINT32_C(0x5a827999), rtSha1Ch);
226 TWENTY_ITERATIONS(20, UINT32_C(0x6ed9eba1), rtSha1Parity);
227 TWENTY_ITERATIONS(40, UINT32_C(0x8f1bbcdc), rtSha1Maj);
228 TWENTY_ITERATIONS(60, UINT32_C(0xca62c1d6), rtSha1Parity);
229
230#elif 0 /* Version avoiding the constant selection. */
231 unsigned iWord = 0;
232# define TWENTY_ITERATIONS(a_iWordStop, a_uK, a_uExprBCD) \
233 for (; iWord < a_iWordStop; iWord++) \
234 { \
235 uint32_t uTemp = ASMRotateLeftU32(uA, 5); \
236 uTemp += (a_uExprBCD); \
237 uTemp += uE; \
238 uTemp += pCtx->AltPrivate.auW[iWord]; \
239 uTemp += (a_uK); \
240 \
241 uE = uD; \
242 uD = uC; \
243 uC = ASMRotateLeftU32(uB, 30); \
244 uB = uA; \
245 uA = uTemp; \
246 } do { } while (0)
247 TWENTY_ITERATIONS(20, UINT32_C(0x5a827999), rtSha1Ch(uB, uC, uD));
248 TWENTY_ITERATIONS(40, UINT32_C(0x6ed9eba1), rtSha1Parity(uB, uC, uD));
249 TWENTY_ITERATIONS(60, UINT32_C(0x8f1bbcdc), rtSha1Maj(uB, uC, uD));
250 TWENTY_ITERATIONS(80, UINT32_C(0xca62c1d6), rtSha1Parity(uB, uC, uD));
251
252#else /* Dead simple implementation. */
253 for (unsigned iWord = 0; iWord < RT_ELEMENTS(pCtx->AltPrivate.auW); iWord++)
254 {
255 uint32_t uTemp = ASMRotateLeftU32(uA, 5);
256 uTemp += uE;
257 uTemp += pCtx->AltPrivate.auW[iWord];
258 if (iWord <= 19)
259 {
260 uTemp += (uB & uC) | (~uB & uD);
261 uTemp += UINT32_C(0x5a827999);
262 }
263 else if (iWord <= 39)
264 {
265 uTemp += uB ^ uC ^ uD;
266 uTemp += UINT32_C(0x6ed9eba1);
267 }
268 else if (iWord <= 59)
269 {
270 uTemp += (uB & uC) | (uB & uD) | (uC & uD);
271 uTemp += UINT32_C(0x8f1bbcdc);
272 }
273 else
274 {
275 uTemp += uB ^ uC ^ uD;
276 uTemp += UINT32_C(0xca62c1d6);
277 }
278
279 uE = uD;
280 uD = uC;
281 uC = ASMRotateLeftU32(uB, 30);
282 uB = uA;
283 uA = uTemp;
284 }
285#endif
286
287 pCtx->AltPrivate.auH[0] += uA;
288 pCtx->AltPrivate.auH[1] += uB;
289 pCtx->AltPrivate.auH[2] += uC;
290 pCtx->AltPrivate.auH[3] += uD;
291 pCtx->AltPrivate.auH[4] += uE;
292}
293
294
295RTDECL(void) RTSha1Update(PRTSHA1CONTEXT pCtx, const void *pvBuf, size_t cbBuf)
296{
297 Assert(pCtx->AltPrivate.cbMessage < UINT64_MAX / 2);
298 uint8_t const *pbBuf = (uint8_t const *)pvBuf;
299
300 /*
301 * Deal with buffered bytes first.
302 */
303 size_t cbBuffered = (size_t)pCtx->AltPrivate.cbMessage & (RTSHA1_BLOCK_SIZE - 1U);
304 if (cbBuffered)
305 {
306 size_t cbMissing = RTSHA1_BLOCK_SIZE - cbBuffered;
307 if (cbBuf >= cbMissing)
308 {
309 memcpy((uint8_t *)&pCtx->AltPrivate.auW[0] + cbBuffered, pbBuf, cbMissing);
310 pCtx->AltPrivate.cbMessage += cbMissing;
311 pbBuf += cbMissing;
312 cbBuf -= cbMissing;
313
314 rtSha1BlockInitBuffered(pCtx);
315 rtSha1BlockProcess(pCtx);
316 }
317 else
318 {
319 memcpy((uint8_t *)&pCtx->AltPrivate.auW[0] + cbBuffered, pbBuf, cbBuf);
320 pCtx->AltPrivate.cbMessage += cbBuf;
321 return;
322 }
323 }
324
325 if (!((uintptr_t)pbBuf & 3))
326 {
327 /*
328 * Process full blocks directly from the input buffer.
329 */
330 while (cbBuf >= RTSHA1_BLOCK_SIZE)
331 {
332 rtSha1BlockInit(pCtx, pbBuf);
333 rtSha1BlockProcess(pCtx);
334
335 pCtx->AltPrivate.cbMessage += RTSHA1_BLOCK_SIZE;
336 pbBuf += RTSHA1_BLOCK_SIZE;
337 cbBuf -= RTSHA1_BLOCK_SIZE;
338 }
339 }
340 else
341 {
342 /*
343 * Unaligned input, so buffer it.
344 */
345 while (cbBuf >= RTSHA1_BLOCK_SIZE)
346 {
347 memcpy((uint8_t *)&pCtx->AltPrivate.auW[0], pbBuf, RTSHA1_BLOCK_SIZE);
348 rtSha1BlockInitBuffered(pCtx);
349 rtSha1BlockProcess(pCtx);
350
351 pCtx->AltPrivate.cbMessage += RTSHA1_BLOCK_SIZE;
352 pbBuf += RTSHA1_BLOCK_SIZE;
353 cbBuf -= RTSHA1_BLOCK_SIZE;
354 }
355 }
356
357 /*
358 * Stash any remaining bytes into the context buffer.
359 */
360 if (cbBuf > 0)
361 {
362 memcpy((uint8_t *)&pCtx->AltPrivate.auW[0], pbBuf, cbBuf);
363 pCtx->AltPrivate.cbMessage += cbBuf;
364 }
365}
366RT_EXPORT_SYMBOL(RTSha1Update);
367
368
369RTDECL(void) RTSha1Final(PRTSHA1CONTEXT pCtx, uint8_t pabDigest[RTSHA1_HASH_SIZE])
370{
371 Assert(pCtx->AltPrivate.cbMessage < UINT64_MAX / 2);
372
373 /*
374 * Complete the message by adding a single bit (0x80), padding till
375 * the next 448-bit boundrary, the add the message length.
376 */
377 uint64_t const cMessageBits = pCtx->AltPrivate.cbMessage * 8;
378
379 unsigned cbMissing = RTSHA1_BLOCK_SIZE - ((unsigned)pCtx->AltPrivate.cbMessage & (RTSHA1_BLOCK_SIZE - 1U));
380 static uint8_t const s_abSingleBitAndSomePadding[12] = { 0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };
381 if (cbMissing < 1U + 8U)
382 /* Less than 64+8 bits left in the current block, force a new block. */
383 RTSha1Update(pCtx, &s_abSingleBitAndSomePadding, sizeof(s_abSingleBitAndSomePadding));
384 else
385 RTSha1Update(pCtx, &s_abSingleBitAndSomePadding, 1);
386
387 unsigned cbBuffered = (unsigned)pCtx->AltPrivate.cbMessage & (RTSHA1_BLOCK_SIZE - 1U);
388 cbMissing = RTSHA1_BLOCK_SIZE - cbBuffered;
389 Assert(cbMissing >= 8);
390 memset((uint8_t *)&pCtx->AltPrivate.auW[0] + cbBuffered, 0, cbMissing - 8);
391
392 *(uint64_t *)&pCtx->AltPrivate.auW[14] = RT_H2BE_U64(cMessageBits);
393
394 /*
395 * Process the last buffered block constructed/completed above.
396 */
397 rtSha1BlockInitBuffered(pCtx);
398 rtSha1BlockProcess(pCtx);
399
400 /*
401 * Convert the byte order of the hash words and we're done.
402 */
403 pCtx->AltPrivate.auH[0] = RT_H2BE_U32(pCtx->AltPrivate.auH[0]);
404 pCtx->AltPrivate.auH[1] = RT_H2BE_U32(pCtx->AltPrivate.auH[1]);
405 pCtx->AltPrivate.auH[2] = RT_H2BE_U32(pCtx->AltPrivate.auH[2]);
406 pCtx->AltPrivate.auH[3] = RT_H2BE_U32(pCtx->AltPrivate.auH[3]);
407 pCtx->AltPrivate.auH[4] = RT_H2BE_U32(pCtx->AltPrivate.auH[4]);
408
409 memcpy(pabDigest, &pCtx->AltPrivate.auH[0], RTSHA1_HASH_SIZE);
410
411 RT_ZERO(pCtx->AltPrivate);
412 pCtx->AltPrivate.cbMessage = UINT64_MAX;
413}
414RT_EXPORT_SYMBOL(RTSha1Final);
415
416
417RTDECL(void) RTSha1(const void *pvBuf, size_t cbBuf, uint8_t pabDigest[RTSHA1_HASH_SIZE])
418{
419 RTSHA1CONTEXT Ctx;
420 RTSha1Init(&Ctx);
421 RTSha1Update(&Ctx, pvBuf, cbBuf);
422 RTSha1Final(&Ctx, pabDigest);
423}
424RT_EXPORT_SYMBOL(RTSha1);
425
426
Note: See TracBrowser for help on using the repository browser.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette