md5.cpp

Go to the documentation of this file.

//
// Copyright (C) 2001-2013 Graeme Walker <graeme_walker@users.sourceforge.net>
// 
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
// 
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
// 
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.
// ===
//
// md5.cpp
//
// An implementation of the RFC-1321 message digest algorithm.
//
// This code was developed from main body of RFC 1321 without reference to the
// RSA reference implementation in the appendix.
//
// A minor portability advantage over the RSA implementation is that there is no 
// need to define a datatype that is exactly 32 bits: the requirement is that 
// 'big_t' is at least 32 bits, but it can be more.
// 
// Stylistic advantages are that it is written in C++ with an enclosing namespace,
// it does not use preprocessor macros, and there is an element of layering with 
// digest_stream built on top of the low-level digest class.

#include "md5.h"

md5::digest::digest()
{
        init() ;
}

md5::digest::digest( state_type d_in ) :
        a(d_in.a) ,
        b(d_in.b) ,
        c(d_in.c) ,
        d(d_in.d)
{
}

md5::digest::state_type md5::digest::state() const
{
        big_t mask = 0 ;
        small_t thirty_two = 32U ;
        small_t sizeof_thirty_two_bits = 4U ; // 4x8=32
        if( sizeof(mask) > sizeof_thirty_two_bits ) 
        {
                mask = ~0U ;
                mask <<= thirty_two ; // ignore warnings here
        }
        state_type result = { a & ~mask , b & ~mask , c & ~mask , d & ~mask } ;
        return result ;
}

md5::digest::digest( const md5::string_type & s )
{
        init() ;
        small_t n = block::blocks( s.length() ) ;
        for( small_t i = 0U ; i < n ; ++i )
        {
                block blk( s , i , block::end(s.length()) ) ;
                add( blk ) ;
        }
}

void md5::digest::add( const block & m )
{
        digest old( *this ) ;
        round1( m ) ;
        round2( m ) ;
        round3( m ) ;
        round4( m ) ;
        add( old ) ;
}

void md5::digest::init()
{
        a = 0x67452301UL ;
        b = 0xefcdab89UL ;
        c = 0x98badcfeUL ;
        d = 0x10325476UL ;
}

void md5::digest::add( const digest & other )
{
        a += other.a ;
        b += other.b ;
        c += other.c ;
        d += other.d ;
}

void md5::digest::round1( const block & m )
{
        digest & r = *this ;
        r(m,F,ABCD, 0, 7, 1); r(m,F,DABC, 1,12, 2); r(m,F,CDAB, 2,17, 3); r(m,F,BCDA, 3,22, 4);
        r(m,F,ABCD, 4, 7, 5); r(m,F,DABC, 5,12, 6); r(m,F,CDAB, 6,17, 7); r(m,F,BCDA, 7,22, 8);
        r(m,F,ABCD, 8, 7, 9); r(m,F,DABC, 9,12,10); r(m,F,CDAB,10,17,11); r(m,F,BCDA,11,22,12);
        r(m,F,ABCD,12, 7,13); r(m,F,DABC,13,12,14); r(m,F,CDAB,14,17,15); r(m,F,BCDA,15,22,16);
}

void md5::digest::round2( const block & m )
{
        digest & r = *this ;
        r(m,G,ABCD, 1, 5,17); r(m,G,DABC, 6, 9,18); r(m,G,CDAB,11,14,19); r(m,G,BCDA, 0,20,20);
        r(m,G,ABCD, 5, 5,21); r(m,G,DABC,10, 9,22); r(m,G,CDAB,15,14,23); r(m,G,BCDA, 4,20,24);
        r(m,G,ABCD, 9, 5,25); r(m,G,DABC,14, 9,26); r(m,G,CDAB, 3,14,27); r(m,G,BCDA, 8,20,28);
        r(m,G,ABCD,13, 5,29); r(m,G,DABC, 2, 9,30); r(m,G,CDAB, 7,14,31); r(m,G,BCDA,12,20,32);
}

void md5::digest::round3( const block & m )
{
        digest & r = *this ;
        r(m,H,ABCD, 5, 4,33); r(m,H,DABC, 8,11,34); r(m,H,CDAB,11,16,35); r(m,H,BCDA,14,23,36);
        r(m,H,ABCD, 1, 4,37); r(m,H,DABC, 4,11,38); r(m,H,CDAB, 7,16,39); r(m,H,BCDA,10,23,40);
        r(m,H,ABCD,13, 4,41); r(m,H,DABC, 0,11,42); r(m,H,CDAB, 3,16,43); r(m,H,BCDA, 6,23,44);
        r(m,H,ABCD, 9, 4,45); r(m,H,DABC,12,11,46); r(m,H,CDAB,15,16,47); r(m,H,BCDA, 2,23,48);
}

void md5::digest::round4( const block & m )
{
        digest & r = *this ;
        r(m,I,ABCD, 0, 6,49); r(m,I,DABC, 7,10,50); r(m,I,CDAB,14,15,51); r(m,I,BCDA, 5,21,52);
        r(m,I,ABCD,12, 6,53); r(m,I,DABC, 3,10,54); r(m,I,CDAB,10,15,55); r(m,I,BCDA, 1,21,56);
        r(m,I,ABCD, 8, 6,57); r(m,I,DABC,15,10,58); r(m,I,CDAB, 6,15,59); r(m,I,BCDA,13,21,60);
        r(m,I,ABCD, 4, 6,61); r(m,I,DABC,11,10,62); r(m,I,CDAB, 2,15,63); r(m,I,BCDA, 9,21,64);
}

void md5::digest::operator()( const block & m , aux_fn_t aux , Permutation p , small_t k , small_t s , small_t i )
{
        if( p == ABCD ) a = op( m , aux , a , b , c , d , k , s , i ) ;
        if( p == DABC ) d = op( m , aux , d , a , b , c , k , s , i ) ;
        if( p == CDAB ) c = op( m , aux , c , d , a , b , k , s , i ) ;
        if( p == BCDA ) b = op( m , aux , b , c , d , a , k , s , i ) ;
}

md5::big_t md5::digest::op( const block & m , aux_fn_t aux , big_t a , big_t b , big_t c , big_t d , 
        small_t k , small_t s , small_t i )
{
        return b + rot32( s , ( a + (*aux)( b , c , d ) + m.X(k) + T(i) ) ) ;
}

md5::big_t md5::digest::rot32( small_t places , big_t n )
{
        // circular rotate of 32 LSBs, with corruption of higher bits
        big_t overflow_mask = ( 1UL << places ) - 1UL ; // in case big_t is more than 32 bits
        big_t overflow = ( n >> ( 32U - places ) ) ;
        return ( n << places ) | ( overflow & overflow_mask ) ;
}

md5::big_t md5::digest::F( big_t x , big_t y , big_t z )
{
        return ( x & y ) | ( ~x & z ) ;
}

md5::big_t md5::digest::G( big_t x , big_t y , big_t z )
{
        return ( x & z ) | ( y & ~z ) ;
}

md5::big_t md5::digest::H( big_t x , big_t y , big_t z )
{
        return x ^ y ^ z ;
}

md5::big_t md5::digest::I( big_t x , big_t y , big_t z )
{
        return y ^ ( x | ~z ) ;
}

md5::big_t md5::digest::T( small_t i )
{
        // T = static_cast<big_t>( 4294967296.0 * std::fabs(std::sin(static_cast<double>(i))) ) for 1 <= i <= 64
        //
        static big_t t_map[] = 
        {
                0xd76aa478UL ,
                0xe8c7b756UL ,
                0x242070dbUL ,
                0xc1bdceeeUL ,
                0xf57c0fafUL ,
                0x4787c62aUL ,
                0xa8304613UL ,
                0xfd469501UL ,
                0x698098d8UL ,
                0x8b44f7afUL ,
                0xffff5bb1UL ,
                0x895cd7beUL ,
                0x6b901122UL ,
                0xfd987193UL ,
                0xa679438eUL ,
                0x49b40821UL ,
                0xf61e2562UL ,
                0xc040b340UL ,
                0x265e5a51UL ,
                0xe9b6c7aaUL ,
                0xd62f105dUL ,
                0x02441453UL ,
                0xd8a1e681UL ,
                0xe7d3fbc8UL ,
                0x21e1cde6UL ,
                0xc33707d6UL ,
                0xf4d50d87UL ,
                0x455a14edUL ,
                0xa9e3e905UL ,
                0xfcefa3f8UL ,
                0x676f02d9UL ,
                0x8d2a4c8aUL ,
                0xfffa3942UL ,
                0x8771f681UL ,
                0x6d9d6122UL ,
                0xfde5380cUL ,
                0xa4beea44UL ,
                0x4bdecfa9UL ,
                0xf6bb4b60UL ,
                0xbebfbc70UL ,
                0x289b7ec6UL ,
                0xeaa127faUL ,
                0xd4ef3085UL ,
                0x04881d05UL ,
                0xd9d4d039UL ,
                0xe6db99e5UL ,
                0x1fa27cf8UL ,
                0xc4ac5665UL ,
                0xf4292244UL ,
                0x432aff97UL ,
                0xab9423a7UL ,
                0xfc93a039UL ,
                0x655b59c3UL ,
                0x8f0ccc92UL ,
                0xffeff47dUL ,
                0x85845dd1UL ,
                0x6fa87e4fUL ,
                0xfe2ce6e0UL ,
                0xa3014314UL ,
                0x4e0811a1UL ,
                0xf7537e82UL ,
                0xbd3af235UL ,
                0x2ad7d2bbUL ,
                0xeb86d391UL } ;
        return t_map[i-1UL] ;
}

// ===

md5::string_type md5::format::raw( const digest::state_type & d )
{
        string_type result ;
        result.reserve( 16U ) ;
        result.append( raw(d.a) ) ;
        result.append( raw(d.b) ) ;
        result.append( raw(d.c) ) ;
        result.append( raw(d.d) ) ;
        return result ;
}

md5::string_type md5::format::raw( big_t n )
{
        string_type result ;
        result.reserve( 4U ) ;
        result.append( 1U , static_cast<char>(n&0xffUL) ) ; n >>= 8U ;
        result.append( 1U , static_cast<char>(n&0xffUL) ) ; n >>= 8U ;
        result.append( 1U , static_cast<char>(n&0xffUL) ) ; n >>= 8U ;
        result.append( 1U , static_cast<char>(n&0xffUL) ) ;
        return result ;
}

md5::string_type md5::format::rfc( const digest & d )
{
        return rfc( d.state() ) ;
}

md5::string_type md5::format::rfc( const digest::state_type & d )
{
        string_type result ;
        result.reserve( 32U ) ;
        result.append( str(d.a) ) ;
        result.append( str(d.b) ) ;
        result.append( str(d.c) ) ;
        result.append( str(d.d) ) ;
        return result ;
}

md5::string_type md5::format::str( big_t n )
{
        string_type result ;
        result.reserve( 8U ) ;
        result.append( str2(n&0xffUL) ) ; n >>= 8U ;
        result.append( str2(n&0xffUL) ) ; n >>= 8U ;
        result.append( str2(n&0xffUL) ) ; n >>= 8U ;
        result.append( str2(n&0xffUL) ) ;
        return result ;
}

md5::string_type md5::format::str2( small_t n )
{
        return str1((n>>4U)&0xfU) + str1(n&0xfU) ;
}

md5::string_type md5::format::str1( small_t n )
{
        n = n <= 15U ? n : 0U ;
        const char * map = "0123456789abcdef" ;
        return string_type( 1U , map[n] ) ;
}

// ===

md5::block::block( const md5::string_type & s , small_t block , big_t end_value ) :
        m_s(s) ,
        m_block(block) ,
        m_end_value(end_value)
{
}

md5::big_t md5::block::end( small_t length )
{
        big_t result = length ;
        result *= 8UL ;
        return result ;
}

md5::small_t md5::block::rounded( small_t raw_byte_count )
{
        small_t n = raw_byte_count + 64U ;
        return n - ( ( raw_byte_count + 8U ) % 64U ) ;
}

md5::small_t md5::block::blocks( small_t raw_byte_count )
{
        small_t byte_count = rounded(raw_byte_count) + 8U ;
        return byte_count / 64UL ;
}

md5::big_t md5::block::X( small_t dword_index ) const
{
        small_t byte_index = ( m_block * 64U ) + ( dword_index * 4U ) ;
        big_t result = x( byte_index + 3U ) ;
        result <<= 8U ; result += x( byte_index + 2U ) ;
        result <<= 8U ; result += x( byte_index + 1U ) ;
        result <<= 8U ; result += x( byte_index + 0U ) ;
        return result ;
}

md5::small_t md5::block::x( small_t i ) const
{
        small_t length = m_s.length() ;
        if( i < length )
        {
                return static_cast<unsigned char>(m_s[i]) ;
        }
        else if( i < rounded(length) )
        {
                return i == length ? 128U : 0U ;
        }
        else
        {
                small_t byte_shift = i - rounded(length) ;
                if( byte_shift >= sizeof(big_t) ) 
                {
                        return 0U ;
                }
                else
                {
                        small_t bit_shift = byte_shift * 8U ;

                        big_t end_value = m_end_value >> bit_shift ;
                        return static_cast<small_t>( end_value & 0xffUL ) ;
                }
        }
}

// ===

md5::digest_stream::digest_stream() :
        m_length(0U)
{
}

md5::digest_stream::digest_stream( digest::state_type dd , small_t length ) :
        m_digest(dd) ,
        m_length(length)
{
}

void md5::digest_stream::add( const md5::string_type & s )
{
        m_buffer.append( s ) ;
        m_length += s.length() ;

        while( m_buffer.length() >= 64U )
        {
                block m( m_buffer , 0U , 0UL ) ;
                m_digest.add( m ) ;
                m_buffer.erase( 0U , 64U ) ;
        }
}

void md5::digest_stream::close()
{
        block b( m_buffer , 0U , block::end(m_length) ) ;
        m_digest.add( b ) ;
        m_buffer.erase() ;
}

md5::digest_stream::state_type md5::digest_stream::state() const
{
        state_type result ;
        result.d = m_digest.state() ;
        result.n = m_length ;
        result.s = m_buffer ;
        return result ;
}

md5::small_t md5::digest_stream::size() const
{
        return m_length ;
}