From 8aa6cee7eed01384771e05ecb425e4df9da4687b Mon Sep 17 00:00:00 2001 From: Mike Buland Date: Thu, 13 Jan 2011 23:30:44 +0000 Subject: Md5 works really, really well. It's fast, and sexy, and awesome. Thanks david. --- src/md5.cpp | 293 +++++++++++++++++++++++++++++++++--------------------- src/md5.h | 13 ++- src/unit/md5.unit | 82 +++++++++++++++ 3 files changed, 270 insertions(+), 118 deletions(-) create mode 100644 src/unit/md5.unit diff --git a/src/md5.cpp b/src/md5.cpp index 46ee769..a1345ce 100644 --- a/src/md5.cpp +++ b/src/md5.cpp @@ -11,9 +11,11 @@ #include "bu/md5.h" #include "bu/stream.h" - -// This performs a wrapping bitwise shift, kinda' fun! -#define bitRoll( val, amnt ) ((val<<(amnt)) | (val>>(32-(amnt)))) +#ifdef SYSTEM_BIG_ENDIAN +# define toLittleEndian( a, b ) _toLittleEndian( a, b ) +#else +# define toLittleEndian( a, b ) (void)0 +#endif Bu::Md5::Md5() { @@ -33,9 +35,8 @@ void Bu::Md5::reset() sum[2] = 0x98BADCFEU; sum[3] = 0x10325476U; - iBytes = 0; - memset( inbuf, 0, 4*16 ); - iFill = 0; + uBits[0] = 0; + uBits[1] = 0; } void Bu::Md5::setSalt( const Bu::FString & /*sSalt*/ ) @@ -45,137 +46,201 @@ void Bu::Md5::setSalt( const Bu::FString & /*sSalt*/ ) void Bu::Md5::addData( const void *sVData, int iSize ) { const char *sData = (const char *)sVData; + uint32_t t; + + t = uBits[0]; + if( (uBits[0] = t + ((uint32_t)iSize << 3)) < t ) + uBits[1]++; + uBits[1] += iSize >> 29; + + t = (t >> 3) & 0x3f; /* How many bytes we have buffered */ - int iInPos = 0; - for(;;) + /* Handle any leading odd-sized chunks */ + if( t ) { - for( ; iFill < 16*4 && iInPos < iSize; iFill++, iInPos++ ) - { - inbuf[iFill>>2] |= ((long)sData[iInPos]) << ((iFill*8)%32); + unsigned char *p = (unsigned char *) inbuf + t; + + t = 64 - t; + if( iSize < t ) { + memcpy( p, sData, iSize ); + return; } - if( iFill < 16*4 ) - break; - compBlock( inbuf, sum ); - memset( inbuf, 0, 4*16 ); - iFill = 0; + memcpy( p, sData, t ); + toLittleEndian( inbuf, 16 ); + compBlock( sum, (uint32_t *)inbuf ); + sData += t; + iSize -= t; } - iBytes += iSize; + + /* Process data in 64-byte chunks */ + while( iSize >= 64 ) + { + memcpy( inbuf, sData, 64 ); + toLittleEndian( inbuf, 16 ); + compBlock( sum, (uint32_t *)inbuf ); + sData += 64; + iSize -= 64; + } + + /* Handle any remaining bytes of data. */ + memcpy( inbuf, sData, iSize ); } Bu::FString Bu::Md5::getResult() { - long lsum[4]; + uint32_t lsum[4]; compCap( lsum ); return Bu::FString( (const char *)lsum, 4*4 ); } void Bu::Md5::writeResult( Bu::Stream &sOut ) { - long lsum[4]; + uint32_t lsum[4]; compCap( lsum ); sOut.write( lsum, 4*4 ); } -void Bu::Md5::compCap( long *sumout ) +void Bu::Md5::compCap( uint32_t *sumout ) { + uint8_t tmpbuf[64]; memcpy( sumout, sum, 4*4 ); - long lbuf[16]; - memcpy( lbuf, inbuf, 4*16 ); - - lbuf[iFill>>2] |= 0x80 << ((iFill*8)%32); - uint64_t iBits = iBytes*8; - if( iBytes > 0 && iFill>>2 >= 14 ) - { - compBlock( lbuf, sumout ); - memset( lbuf, 0, 4*16 ); - memcpy( lbuf+14, &iBits, 8 ); - compBlock( lbuf, sumout ); - } - else - { - memcpy( lbuf+14, &iBits, 8 ); - compBlock( lbuf, sumout ); + memcpy( tmpbuf, inbuf, 64 ); + + uint32_t count; + uint8_t *p; + + /* Compute number of bytes mod 64 */ + count = (uBits[0] >> 3) & 0x3F; + + /* Set the first char of padding to 0x80. This is safe since there is + always at least one byte free */ + p = tmpbuf + count; + *p++ = 0x80; + + /* Bytes of padding needed to make 64 bytes */ + count = 64 - 1 - count; + + /* Pad out to 56 mod 64 */ + if (count < 8) { + /* Two lots of padding: Pad the first block to 64 bytes */ + memset( p, 0, count ); + toLittleEndian( tmpbuf, 16 ); + compBlock( sumout, (uint32_t *)tmpbuf ); + + /* Now fill the next block with 56 bytes */ + memset( tmpbuf, 0, 56); + } else { + /* Pad block to 56 bytes */ + memset( p, 0, count - 8); } + toLittleEndian( tmpbuf, 14 ); + + /* Append length in bits and transform */ + ((uint32_t *) tmpbuf)[14] = uBits[0]; + ((uint32_t *) tmpbuf)[15] = uBits[1]; + + compBlock( sumout, (uint32_t *)tmpbuf ); + toLittleEndian((unsigned char *)sumout, 4); } -void Bu::Md5::compBlock( long *x, long *lsum ) +#define F1(x, y, z) (z ^ (x & (y ^ z))) +#define F2(x, y, z) F1(z, x, y) +#define F3(x, y, z) (x ^ y ^ z) +#define F4(x, y, z) (y ^ (x | ~z)) + +/* This is the central step in the MD5 algorithm. */ +#define MD5STEP(f, w, x, y, z, data, s) \ + ( w += f(x, y, z) + data, w = w<>(32-s), w += x ) + +void Bu::Md5::compBlock( uint32_t *lsum, uint32_t *x ) { - long a = lsum[0]; - long b = lsum[1]; - long c = lsum[2]; - long d = lsum[3]; - - a = md5_ff(a, b, c, d, x[ 0], 7 , -680876936); - d = md5_ff(d, a, b, c, x[ 1], 12, -389564586); - c = md5_ff(c, d, a, b, x[ 2], 17, 606105819); - b = md5_ff(b, c, d, a, x[ 3], 22, -1044525330); - a = md5_ff(a, b, c, d, x[ 4], 7 , -176418897); - d = md5_ff(d, a, b, c, x[ 5], 12, 1200080426); - c = md5_ff(c, d, a, b, x[ 6], 17, -1473231341); - b = md5_ff(b, c, d, a, x[ 7], 22, -45705983); - a = md5_ff(a, b, c, d, x[ 8], 7 , 1770035416); - d = md5_ff(d, a, b, c, x[ 9], 12, -1958414417); - c = md5_ff(c, d, a, b, x[10], 17, -42063); - b = md5_ff(b, c, d, a, x[11], 22, -1990404162); - a = md5_ff(a, b, c, d, x[12], 7 , 1804603682); - d = md5_ff(d, a, b, c, x[13], 12, -40341101); - c = md5_ff(c, d, a, b, x[14], 17, -1502002290); - b = md5_ff(b, c, d, a, x[15], 22, 1236535329); - - a = md5_gg(a, b, c, d, x[ 1], 5 , -165796510); - d = md5_gg(d, a, b, c, x[ 6], 9 , -1069501632); - c = md5_gg(c, d, a, b, x[11], 14, 643717713); - b = md5_gg(b, c, d, a, x[ 0], 20, -373897302); - a = md5_gg(a, b, c, d, x[ 5], 5 , -701558691); - d = md5_gg(d, a, b, c, x[10], 9 , 38016083); - c = md5_gg(c, d, a, b, x[15], 14, -660478335); - b = md5_gg(b, c, d, a, x[ 4], 20, -405537848); - a = md5_gg(a, b, c, d, x[ 9], 5 , 568446438); - d = md5_gg(d, a, b, c, x[14], 9 , -1019803690); - c = md5_gg(c, d, a, b, x[ 3], 14, -187363961); - b = md5_gg(b, c, d, a, x[ 8], 20, 1163531501); - a = md5_gg(a, b, c, d, x[13], 5 , -1444681467); - d = md5_gg(d, a, b, c, x[ 2], 9 , -51403784); - c = md5_gg(c, d, a, b, x[ 7], 14, 1735328473); - b = md5_gg(b, c, d, a, x[12], 20, -1926607734); - - a = md5_hh(a, b, c, d, x[ 5], 4 , -378558); - d = md5_hh(d, a, b, c, x[ 8], 11, -2022574463); - c = md5_hh(c, d, a, b, x[11], 16, 1839030562); - b = md5_hh(b, c, d, a, x[14], 23, -35309556); - a = md5_hh(a, b, c, d, x[ 1], 4 , -1530992060); - d = md5_hh(d, a, b, c, x[ 4], 11, 1272893353); - c = md5_hh(c, d, a, b, x[ 7], 16, -155497632); - b = md5_hh(b, c, d, a, x[10], 23, -1094730640); - a = md5_hh(a, b, c, d, x[13], 4 , 681279174); - d = md5_hh(d, a, b, c, x[ 0], 11, -358537222); - c = md5_hh(c, d, a, b, x[ 3], 16, -722521979); - b = md5_hh(b, c, d, a, x[ 6], 23, 76029189); - a = md5_hh(a, b, c, d, x[ 9], 4 , -640364487); - d = md5_hh(d, a, b, c, x[12], 11, -421815835); - c = md5_hh(c, d, a, b, x[15], 16, 530742520); - b = md5_hh(b, c, d, a, x[ 2], 23, -995338651); - - a = md5_ii(a, b, c, d, x[ 0], 6 , -198630844); - d = md5_ii(d, a, b, c, x[ 7], 10, 1126891415); - c = md5_ii(c, d, a, b, x[14], 15, -1416354905); - b = md5_ii(b, c, d, a, x[ 5], 21, -57434055); - a = md5_ii(a, b, c, d, x[12], 6 , 1700485571); - d = md5_ii(d, a, b, c, x[ 3], 10, -1894986606); - c = md5_ii(c, d, a, b, x[10], 15, -1051523); - b = md5_ii(b, c, d, a, x[ 1], 21, -2054922799); - a = md5_ii(a, b, c, d, x[ 8], 6 , 1873313359); - d = md5_ii(d, a, b, c, x[15], 10, -30611744); - c = md5_ii(c, d, a, b, x[ 6], 15, -1560198380); - b = md5_ii(b, c, d, a, x[13], 21, 1309151649); - a = md5_ii(a, b, c, d, x[ 4], 6 , -145523070); - d = md5_ii(d, a, b, c, x[11], 10, -1120210379); - c = md5_ii(c, d, a, b, x[ 2], 15, 718787259); - b = md5_ii(b, c, d, a, x[ 9], 21, -343485551); - - lsum[0] = a + lsum[0]; - lsum[1] = b + lsum[1]; - lsum[2] = c + lsum[2]; - lsum[3] = d + lsum[3]; + register uint32_t a, b, c, d; + a = lsum[0]; + b = lsum[1]; + c = lsum[2]; + d = lsum[3]; + + MD5STEP(F1, a, b, c, d, x[0] + 0xd76aa478, 7); + MD5STEP(F1, d, a, b, c, x[1] + 0xe8c7b756, 12); + MD5STEP(F1, c, d, a, b, x[2] + 0x242070db, 17); + MD5STEP(F1, b, c, d, a, x[3] + 0xc1bdceee, 22); + MD5STEP(F1, a, b, c, d, x[4] + 0xf57c0faf, 7); + MD5STEP(F1, d, a, b, c, x[5] + 0x4787c62a, 12); + MD5STEP(F1, c, d, a, b, x[6] + 0xa8304613, 17); + MD5STEP(F1, b, c, d, a, x[7] + 0xfd469501, 22); + MD5STEP(F1, a, b, c, d, x[8] + 0x698098d8, 7); + MD5STEP(F1, d, a, b, c, x[9] + 0x8b44f7af, 12); + MD5STEP(F1, c, d, a, b, x[10] + 0xffff5bb1, 17); + MD5STEP(F1, b, c, d, a, x[11] + 0x895cd7be, 22); + MD5STEP(F1, a, b, c, d, x[12] + 0x6b901122, 7); + MD5STEP(F1, d, a, b, c, x[13] + 0xfd987193, 12); + MD5STEP(F1, c, d, a, b, x[14] + 0xa679438e, 17); + MD5STEP(F1, b, c, d, a, x[15] + 0x49b40821, 22); + + MD5STEP(F2, a, b, c, d, x[1] + 0xf61e2562, 5); + MD5STEP(F2, d, a, b, c, x[6] + 0xc040b340, 9); + MD5STEP(F2, c, d, a, b, x[11] + 0x265e5a51, 14); + MD5STEP(F2, b, c, d, a, x[0] + 0xe9b6c7aa, 20); + MD5STEP(F2, a, b, c, d, x[5] + 0xd62f105d, 5); + MD5STEP(F2, d, a, b, c, x[10] + 0x02441453, 9); + MD5STEP(F2, c, d, a, b, x[15] + 0xd8a1e681, 14); + MD5STEP(F2, b, c, d, a, x[4] + 0xe7d3fbc8, 20); + MD5STEP(F2, a, b, c, d, x[9] + 0x21e1cde6, 5); + MD5STEP(F2, d, a, b, c, x[14] + 0xc33707d6, 9); + MD5STEP(F2, c, d, a, b, x[3] + 0xf4d50d87, 14); + MD5STEP(F2, b, c, d, a, x[8] + 0x455a14ed, 20); + MD5STEP(F2, a, b, c, d, x[13] + 0xa9e3e905, 5); + MD5STEP(F2, d, a, b, c, x[2] + 0xfcefa3f8, 9); + MD5STEP(F2, c, d, a, b, x[7] + 0x676f02d9, 14); + MD5STEP(F2, b, c, d, a, x[12] + 0x8d2a4c8a, 20); + + MD5STEP(F3, a, b, c, d, x[5] + 0xfffa3942, 4); + MD5STEP(F3, d, a, b, c, x[8] + 0x8771f681, 11); + MD5STEP(F3, c, d, a, b, x[11] + 0x6d9d6122, 16); + MD5STEP(F3, b, c, d, a, x[14] + 0xfde5380c, 23); + MD5STEP(F3, a, b, c, d, x[1] + 0xa4beea44, 4); + MD5STEP(F3, d, a, b, c, x[4] + 0x4bdecfa9, 11); + MD5STEP(F3, c, d, a, b, x[7] + 0xf6bb4b60, 16); + MD5STEP(F3, b, c, d, a, x[10] + 0xbebfbc70, 23); + MD5STEP(F3, a, b, c, d, x[13] + 0x289b7ec6, 4); + MD5STEP(F3, d, a, b, c, x[0] + 0xeaa127fa, 11); + MD5STEP(F3, c, d, a, b, x[3] + 0xd4ef3085, 16); + MD5STEP(F3, b, c, d, a, x[6] + 0x04881d05, 23); + MD5STEP(F3, a, b, c, d, x[9] + 0xd9d4d039, 4); + MD5STEP(F3, d, a, b, c, x[12] + 0xe6db99e5, 11); + MD5STEP(F3, c, d, a, b, x[15] + 0x1fa27cf8, 16); + MD5STEP(F3, b, c, d, a, x[2] + 0xc4ac5665, 23); + + MD5STEP(F4, a, b, c, d, x[0] + 0xf4292244, 6); + MD5STEP(F4, d, a, b, c, x[7] + 0x432aff97, 10); + MD5STEP(F4, c, d, a, b, x[14] + 0xab9423a7, 15); + MD5STEP(F4, b, c, d, a, x[5] + 0xfc93a039, 21); + MD5STEP(F4, a, b, c, d, x[12] + 0x655b59c3, 6); + MD5STEP(F4, d, a, b, c, x[3] + 0x8f0ccc92, 10); + MD5STEP(F4, c, d, a, b, x[10] + 0xffeff47d, 15); + MD5STEP(F4, b, c, d, a, x[1] + 0x85845dd1, 21); + MD5STEP(F4, a, b, c, d, x[8] + 0x6fa87e4f, 6); + MD5STEP(F4, d, a, b, c, x[15] + 0xfe2ce6e0, 10); + MD5STEP(F4, c, d, a, b, x[6] + 0xa3014314, 15); + MD5STEP(F4, b, c, d, a, x[13] + 0x4e0811a1, 21); + MD5STEP(F4, a, b, c, d, x[4] + 0xf7537e82, 6); + MD5STEP(F4, d, a, b, c, x[11] + 0xbd3af235, 10); + MD5STEP(F4, c, d, a, b, x[2] + 0x2ad7d2bb, 15); + MD5STEP(F4, b, c, d, a, x[9] + 0xeb86d391, 21); + + lsum[0] += a; + lsum[1] += b; + lsum[2] += c; + lsum[3] += d; } +void Bu::Md5::_toLittleEndian( uint8_t *buf, uint32_t count ) +{ + uint32_t t; + do { + t = (uint32_t) ((unsigned) buf[3] << 8 | buf[2]) << 16 | + ((unsigned) buf[1] << 8 | buf[0]); + *(uint32_t *) buf = t; + buf += 4; + } while( --count ); +} diff --git a/src/md5.h b/src/md5.h index 0be65fd..60992ac 100644 --- a/src/md5.h +++ b/src/md5.h @@ -14,6 +14,8 @@ namespace Bu { /** * Class for easily calculating MD5 sums of just about any data. + * This code is based on some public domain code written by Colin Plumb in + * 1993. *@author Mike Buland */ class Md5 : public Bu::CryptoHash @@ -36,13 +38,16 @@ namespace Bu /** * Compute one block of input data. */ - void compBlock( long *x, uint32_t *lsum ); + void compBlock( uint32_t *lsum, uint32_t *x ); void compCap( uint32_t *sumout ); + + void _addData( uint8_t *target, int &iCurFill, const void *sData, + int iSize ); + void _toLittleEndian( uint8_t *buf, uint32_t count ); - uint32_t inbuf[16]; - uint32_t iFill; + uint8_t inbuf[64]; uint32_t sum[4]; - uint64_t iBytes; + uint32_t uBits[2]; }; }; diff --git a/src/unit/md5.unit b/src/unit/md5.unit new file mode 100644 index 0000000..248aaaf --- /dev/null +++ b/src/unit/md5.unit @@ -0,0 +1,82 @@ +// vim: syntax=cpp +/* + * Copyright (C) 2007-2010 Xagasoft, All rights reserved. + * + * This file is part of the libbu++ library and is released under the + * terms of the license contained in the file LICENSE. + */ + +#include "bu/md5.h" + +#include + +suite Md5 +{ + test basics + { +#define tryStr( a, b ) \ + { Bu::Md5 m; m.addData(a); unitTest( m.getHexResult() == b ); } (void)0 + tryStr("", "d41d8cd98f00b204e9800998ecf8427e"); + tryStr("a", "0cc175b9c0f1b6a831c399e269772661"); + tryStr("abc", "900150983cd24fb0d6963f7d28e17f72"); + tryStr("message digest", "f96b697d7cb7938d525a2f31aaf161d0"); + tryStr("abcdefghijklmnopqrstuvwxyz", + "c3fcd3d76192e4007dfb496cca67e13b"); + tryStr("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789", + "d174ab98d277d9f5a5611c2c9f419d9f"); + tryStr("12345678901234567890123456789012345" + "678901234567890123456789012345678901234567890", + "57edf4a22be3c955ac49da2e2107b67a"); + } + + test twoChunks + { + Bu::Md5 m; + m.addData("12345678901234567890123456789012345"); + m.addData("678901234567890123456789012345678901234567890"); + unitTest( m.getHexResult() == "57edf4a22be3c955ac49da2e2107b67a" ); + } + + test biggerBlocks + { + const char *sums[33] = { + "75fcf199abe516903321095a588b938d", + "e26a863c96d6bdba6601175aedaae108", + "2b207fdcb222078d3ebfeb8d5e7c9315", + "b08683aaa465add72cc2b43ae42f4f70", + "638bb73963b2d925771c3579ccb5e879", + "c727bd4b48a88e3df5924a2604de0790", + "f33d21203c80490f7342e5853c5550eb", + "db449faca66a177aae59b1e36a19d053", + "c800d429afb5f5c820f75c2c94e2e2bb", + "43b79c70b9a6a11e823ffbfa0f45a4db", + "0177ffc483cf598ae3966b3a5ae00c8c", + "1a68fdf4b17a3820d48d101e9355a818" + }; + + char block[128]; + for( int i = 0; i < 128; i++ ) + block[i] = i*2; + + const char **curSum = sums; + for( int j = 1; j < 4096; j*=2 ) + { + /* + Bu::File fOut("temp", Bu::File::WriteNew ); + for( int b = 0; b < j; b++ ) + { + fOut.write( block, 128 ); + } + fOut.close(); + system("md5sum -b temp"); + */ + Bu::Md5 m; + for( int b = 0; b < j; b++ ) + { + m.addData( block, 128 ); + } + unitTest( m.getHexResult() == *curSum ); + curSum++; + } + } +} -- cgit v1.2.3