md5.cpp

Go to the documentation of this file.

//
// Copyright (C) 2017 Graeme Walker
// 
// 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 ;
}

/// \file md5.cpp