alt-sha1.cpp revision 32551b58cc5cc616b772ab398081407bae75546e
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync/* $Id$ */
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync/** @file
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync * IPRT - SHA-1 hash functions, Alternative Implementation.
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync */
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync/*
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync * Copyright (C) 2009-2014 Oracle Corporation
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync *
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync * This file is part of VirtualBox Open Source Edition (OSE), as
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync * available from http://www.virtualbox.org. This file is free software;
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync * you can redistribute it and/or modify it under the terms of the GNU
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync * General Public License (GPL) as published by the Free Software
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync * Foundation, in version 2 as it comes in the "COPYING" file of the
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync *
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync * The contents of this file may alternatively be used under the terms
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync * of the Common Development and Distribution License Version 1.0
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync * VirtualBox OSE distribution, in which case the provisions of the
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync * CDDL are applicable instead of those of the GPL.
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync *
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync * You may elect to license modified versions of this file under the
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync * terms and conditions of either the GPL or the CDDL or both.
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync */
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync/*******************************************************************************
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync* Defined Constants And Macros *
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync*******************************************************************************/
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync/** The SHA-1 block size (in bytes). */
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync#define RTSHA1_BLOCK_SIZE 64U
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync/*******************************************************************************
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync* Header Files *
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync*******************************************************************************/
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync#include "internal/iprt.h"
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync#include <iprt/types.h>
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync#include <iprt/assert.h>
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync#include <iprt/asm.h>
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync#include <iprt/string.h>
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync/** Our private context structure. */
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsynctypedef struct RTSHA1ALTPRIVATECTX
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync{
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync /** The W array.
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync * Buffering happens in the first 16 words, converted from big endian to host
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync * endian immediately before processing. The amount of buffered data is kept
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync * in the 6 least significant bits of cbMessage. */
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync uint32_t auW[80];
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync /** The message length (in bytes). */
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync uint64_t cbMessage;
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync /** The 5 hash values. */
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync uint32_t auH[5];
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync} RTSHA1ALTPRIVATECTX;
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync#define RT_SHA1_PRIVATE_ALT_CONTEXT
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync#include <iprt/sha.h>
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsyncAssertCompile(RT_SIZEOFMEMB(RTSHA1CONTEXT, abPadding) >= RT_SIZEOFMEMB(RTSHA1CONTEXT, AltPrivate));
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsyncAssertCompileMemberSize(RTSHA1ALTPRIVATECTX, auH, RTSHA1_HASH_SIZE);
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsyncRTDECL(void) RTSha1Init(PRTSHA1CONTEXT pCtx)
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync{
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync pCtx->AltPrivate.cbMessage = 0;
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync pCtx->AltPrivate.auH[0] = UINT32_C(0x67452301);
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync pCtx->AltPrivate.auH[1] = UINT32_C(0xefcdab89);
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync pCtx->AltPrivate.auH[2] = UINT32_C(0x98badcfe);
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync pCtx->AltPrivate.auH[3] = UINT32_C(0x10325476);
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync pCtx->AltPrivate.auH[4] = UINT32_C(0xc3d2e1f0);
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync}
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsyncRT_EXPORT_SYMBOL(RTSha1Init);
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync/**
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync * Initializes the auW array from the specfied input block.
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync *
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync * @param pCtx The SHA1 context.
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync * @param pbBlock The block. Must be 32-bit aligned.
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync */
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsyncDECLINLINE(void) rtSha1BlockInit(PRTSHA1CONTEXT pCtx, uint8_t const *pbBlock)
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync{
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync uint32_t const *pu32Block = (uint32_t const *)pbBlock;
086f30e697aef37b4dbc818a42ecde0533bcc1d8vboxsync Assert(!((uintptr_t)pu32Block & 3));
unsigned iWord;
for (iWord = 0; iWord < 16; iWord++)
pCtx->AltPrivate.auW[iWord] = RT_BE2H_U32(pu32Block[iWord]);
for (; iWord < RT_ELEMENTS(pCtx->AltPrivate.auW); iWord++)
{
uint32_t u32 = pCtx->AltPrivate.auW[iWord - 16];
u32 ^= pCtx->AltPrivate.auW[iWord - 14];
u32 ^= pCtx->AltPrivate.auW[iWord - 8];
u32 ^= pCtx->AltPrivate.auW[iWord - 3];
pCtx->AltPrivate.auW[iWord] = ASMRotateLeftU32(u32, 1);
}
}
/**
* Initializes the auW array from data buffered in the first part of the array.
*
* @param pCtx The SHA1 context.
*/
DECLINLINE(void) rtSha1BlockInitBuffered(PRTSHA1CONTEXT pCtx)
{
unsigned iWord;
for (iWord = 0; iWord < 16; iWord++)
pCtx->AltPrivate.auW[iWord] = RT_BE2H_U32(pCtx->AltPrivate.auW[iWord]);
for (; iWord < RT_ELEMENTS(pCtx->AltPrivate.auW); iWord++)
{
uint32_t u32 = pCtx->AltPrivate.auW[iWord - 16];
u32 ^= pCtx->AltPrivate.auW[iWord - 14];
u32 ^= pCtx->AltPrivate.auW[iWord - 8];
u32 ^= pCtx->AltPrivate.auW[iWord - 3];
pCtx->AltPrivate.auW[iWord] = ASMRotateLeftU32(u32, 1);
}
}
/** Function 4.1, Ch(x,y,z). */
DECL_FORCE_INLINE(uint32_t) rtSha1Ch(uint32_t uX, uint32_t uY, uint32_t uZ)
{
uint32_t uResult = uX & uY;
uResult ^= ~uX & uZ;
return uResult;
}
/** Function 4.1, Parity(x,y,z). */
DECL_FORCE_INLINE(uint32_t) rtSha1Parity(uint32_t uX, uint32_t uY, uint32_t uZ)
{
uint32_t uResult = uX;
uResult ^= uY;
uResult ^= uZ;
return uResult;
}
/** Function 4.1, Maj(x,y,z). */
DECL_FORCE_INLINE(uint32_t) rtSha1Maj(uint32_t uX, uint32_t uY, uint32_t uZ)
{
uint32_t uResult = (uX & uY);
uResult |= (uX & uZ);
uResult |= (uY & uZ);
return uResult;
}
/**
* Process the current block.
*
* Requires one of the rtSha1BlockInit functions to be called first.
*
* @param pCtx The SHA1 context.
*/
static void rtSha1BlockProcess(PRTSHA1CONTEXT pCtx)
{
uint32_t uA = pCtx->AltPrivate.auH[0];
uint32_t uB = pCtx->AltPrivate.auH[1];
uint32_t uC = pCtx->AltPrivate.auH[2];
uint32_t uD = pCtx->AltPrivate.auH[3];
uint32_t uE = pCtx->AltPrivate.auH[4];
#if 1 /* Fully unrolled version. */
register uint32_t const *puW = &pCtx->AltPrivate.auW[0];
# define SHA1_BODY(a_uW, a_uK, a_fnFt, a_uA, a_uB, a_uC, a_uD, a_uE) \
do { \
a_uE += a_uW; \
a_uE += (a_uK); \
a_uE += ASMRotateLeftU32(a_uA, 5); \
a_uE += a_fnFt(a_uB, a_uC, a_uD); \
a_uB = ASMRotateLeftU32(a_uB, 30); \
} while (0)
# define FIVE_ITERATIONS(a_iStart, a_uK, a_fnFt) \
do { \
SHA1_BODY(/*puW[a_iStart + 0]*/ *puW++, a_uK, a_fnFt, uA, uB, uC, uD, uE); \
SHA1_BODY(/*puW[a_iStart + 1]*/ *puW++, a_uK, a_fnFt, uE, uA, uB, uC, uD); \
SHA1_BODY(/*puW[a_iStart + 2]*/ *puW++, a_uK, a_fnFt, uD, uE, uA, uB, uC); \
SHA1_BODY(/*puW[a_iStart + 3]*/ *puW++, a_uK, a_fnFt, uC, uD, uE, uA, uB); \
SHA1_BODY(/*puW[a_iStart + 4]*/ *puW++, a_uK, a_fnFt, uB, uC, uD, uE, uA); \
} while (0)
# if 0 /* Variation that reduces the code size by a factor of 4 without much loss in preformance. */
# define TWENTY_ITERATIONS(a_iFirst, a_uK, a_fnFt) \
do { unsigned i = 4; while (i-- > 0) FIVE_ITERATIONS(a_iFirst + (3 - i) * 5, a_uK, a_fnFt); } while (0)
/*for (unsigned i = a_iFirst; i < (a_iFirst + 20); i += 5) FIVE_ITERATIONS(i, a_uK, a_fnFt);*/
# else
# define TWENTY_ITERATIONS(a_iFirst, a_uK, a_fnFt) \
do { \
FIVE_ITERATIONS(a_iFirst + 0, a_uK, a_fnFt); \
FIVE_ITERATIONS(a_iFirst + 5, a_uK, a_fnFt); \
FIVE_ITERATIONS(a_iFirst + 10, a_uK, a_fnFt); \
FIVE_ITERATIONS(a_iFirst + 15, a_uK, a_fnFt); \
} while (0)
# endif
TWENTY_ITERATIONS( 0, UINT32_C(0x5a827999), rtSha1Ch);
TWENTY_ITERATIONS(20, UINT32_C(0x6ed9eba1), rtSha1Parity);
TWENTY_ITERATIONS(40, UINT32_C(0x8f1bbcdc), rtSha1Maj);
TWENTY_ITERATIONS(60, UINT32_C(0xca62c1d6), rtSha1Parity);
#elif 0 /* Version avoiding the constant selection. */
unsigned iWord = 0;
# define TWENTY_ITERATIONS(a_iWordStop, a_uK, a_uExprBCD) \
for (; iWord < a_iWordStop; iWord++) \
{ \
uint32_t uTemp = ASMRotateLeftU32(uA, 5); \
uTemp += (a_uExprBCD); \
uTemp += uE; \
uTemp += pCtx->AltPrivate.auW[iWord]; \
uTemp += (a_uK); \
\
uE = uD; \
uD = uC; \
uC = ASMRotateLeftU32(uB, 30); \
uB = uA; \
uA = uTemp; \
} do { } while (0)
TWENTY_ITERATIONS(20, UINT32_C(0x5a827999), rtSha1Ch(uB, uC, uD));
TWENTY_ITERATIONS(40, UINT32_C(0x6ed9eba1), rtSha1Parity(uB, uC, uD));
TWENTY_ITERATIONS(60, UINT32_C(0x8f1bbcdc), rtSha1Maj(uB, uC, uD));
TWENTY_ITERATIONS(80, UINT32_C(0xca62c1d6), rtSha1Parity(uB, uC, uD));
#else /* Dead simple implementation. */
for (unsigned iWord = 0; iWord < RT_ELEMENTS(pCtx->AltPrivate.auW); iWord++)
{
uint32_t uTemp = ASMRotateLeftU32(uA, 5);
uTemp += uE;
uTemp += pCtx->AltPrivate.auW[iWord];
if (iWord <= 19)
{
uTemp += (uB & uC) | (~uB & uD);
uTemp += UINT32_C(0x5a827999);
}
else if (iWord <= 39)
{
uTemp += uB ^ uC ^ uD;
uTemp += UINT32_C(0x6ed9eba1);
}
else if (iWord <= 59)
{
uTemp += (uB & uC) | (uB & uD) | (uC & uD);
uTemp += UINT32_C(0x8f1bbcdc);
}
else
{
uTemp += uB ^ uC ^ uD;
uTemp += UINT32_C(0xca62c1d6);
}
uE = uD;
uD = uC;
uC = ASMRotateLeftU32(uB, 30);
uB = uA;
uA = uTemp;
}
#endif
pCtx->AltPrivate.auH[0] += uA;
pCtx->AltPrivate.auH[1] += uB;
pCtx->AltPrivate.auH[2] += uC;
pCtx->AltPrivate.auH[3] += uD;
pCtx->AltPrivate.auH[4] += uE;
}
RTDECL(void) RTSha1Update(PRTSHA1CONTEXT pCtx, const void *pvBuf, size_t cbBuf)
{
Assert(pCtx->AltPrivate.cbMessage < UINT64_MAX / 2);
uint8_t const *pbBuf = (uint8_t const *)pvBuf;
/*
* Deal with buffered bytes first.
*/
size_t cbBuffered = (size_t)pCtx->AltPrivate.cbMessage & (RTSHA1_BLOCK_SIZE - 1U);
if (cbBuffered)
{
size_t cbMissing = RTSHA1_BLOCK_SIZE - cbBuffered;
if (cbBuf >= cbMissing)
{
memcpy((uint8_t *)&pCtx->AltPrivate.auW[0] + cbBuffered, pbBuf, cbMissing);
pCtx->AltPrivate.cbMessage += cbMissing;
pbBuf += cbMissing;
cbBuf -= cbMissing;
rtSha1BlockInitBuffered(pCtx);
rtSha1BlockProcess(pCtx);
}
else
{
memcpy((uint8_t *)&pCtx->AltPrivate.auW[0] + cbBuffered, pbBuf, cbBuf);
pCtx->AltPrivate.cbMessage += cbBuf;
return;
}
}
if (!((uintptr_t)pbBuf & 3))
{
/*
* Process full blocks directly from the input buffer.
*/
while (cbBuf >= RTSHA1_BLOCK_SIZE)
{
rtSha1BlockInit(pCtx, pbBuf);
rtSha1BlockProcess(pCtx);
pCtx->AltPrivate.cbMessage += RTSHA1_BLOCK_SIZE;
pbBuf += RTSHA1_BLOCK_SIZE;
cbBuf -= RTSHA1_BLOCK_SIZE;
}
}
else
{
/*
* Unaligned input, so buffer it.
*/
while (cbBuf >= RTSHA1_BLOCK_SIZE)
{
memcpy((uint8_t *)&pCtx->AltPrivate.auW[0], pbBuf, RTSHA1_BLOCK_SIZE);
rtSha1BlockInitBuffered(pCtx);
rtSha1BlockProcess(pCtx);
pCtx->AltPrivate.cbMessage += RTSHA1_BLOCK_SIZE;
pbBuf += RTSHA1_BLOCK_SIZE;
cbBuf -= RTSHA1_BLOCK_SIZE;
}
}
/*
* Stash any remaining bytes into the context buffer.
*/
if (cbBuf > 0)
{
memcpy((uint8_t *)&pCtx->AltPrivate.auW[0], pbBuf, cbBuf);
pCtx->AltPrivate.cbMessage += cbBuf;
}
}
RT_EXPORT_SYMBOL(RTSha1Update);
RTDECL(void) RTSha1Final(PRTSHA1CONTEXT pCtx, uint8_t pabDigest[RTSHA1_HASH_SIZE])
{
Assert(pCtx->AltPrivate.cbMessage < UINT64_MAX / 2);
/*
* Complete the message by adding a single bit (0x80), padding till
* the next 448-bit boundrary, the add the message length.
*/
uint64_t const cMessageBits = pCtx->AltPrivate.cbMessage * 8;
unsigned cbMissing = RTSHA1_BLOCK_SIZE - ((unsigned)pCtx->AltPrivate.cbMessage & (RTSHA1_BLOCK_SIZE - 1U));
static uint8_t const s_abSingleBitAndSomePadding[12] = { 0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };
if (cbMissing < 1U + 8U)
/* Less than 64+8 bits left in the current block, force a new block. */
RTSha1Update(pCtx, &s_abSingleBitAndSomePadding, sizeof(s_abSingleBitAndSomePadding));
else
RTSha1Update(pCtx, &s_abSingleBitAndSomePadding, 1);
unsigned cbBuffered = (unsigned)pCtx->AltPrivate.cbMessage & (RTSHA1_BLOCK_SIZE - 1U);
cbMissing = RTSHA1_BLOCK_SIZE - cbBuffered;
Assert(cbMissing >= 8);
memset((uint8_t *)&pCtx->AltPrivate.auW[0] + cbBuffered, 0, cbMissing - 8);
*(uint64_t *)&pCtx->AltPrivate.auW[14] = RT_H2BE_U64(cMessageBits);
/*
* Process the last buffered block constructed/completed above.
*/
rtSha1BlockInitBuffered(pCtx);
rtSha1BlockProcess(pCtx);
/*
* Convert the byte order of the hash words and we're done.
*/
pCtx->AltPrivate.auH[0] = RT_H2BE_U32(pCtx->AltPrivate.auH[0]);
pCtx->AltPrivate.auH[1] = RT_H2BE_U32(pCtx->AltPrivate.auH[1]);
pCtx->AltPrivate.auH[2] = RT_H2BE_U32(pCtx->AltPrivate.auH[2]);
pCtx->AltPrivate.auH[3] = RT_H2BE_U32(pCtx->AltPrivate.auH[3]);
pCtx->AltPrivate.auH[4] = RT_H2BE_U32(pCtx->AltPrivate.auH[4]);
memcpy(pabDigest, &pCtx->AltPrivate.auH[0], RTSHA1_HASH_SIZE);
RT_ZERO(pCtx->AltPrivate);
pCtx->AltPrivate.cbMessage = UINT64_MAX;
}
RT_EXPORT_SYMBOL(RTSha1Final);
RTDECL(void) RTSha1(const void *pvBuf, size_t cbBuf, uint8_t pabDigest[RTSHA1_HASH_SIZE])
{
RTSHA1CONTEXT Ctx;
RTSha1Init(&Ctx);
RTSha1Update(&Ctx, pvBuf, cbBuf);
RTSha1Final(&Ctx, pabDigest);
}
RT_EXPORT_SYMBOL(RTSha1);