Sans Pareil Technologies, Inc.

/*
 * Checksum.h
 *
 * Definition of the Checksum class.
 *
 * Copyright (c) 2007, Applied Informatics Software Engineering GmbH.
 * and Contributors.
 *
 * Permission is hereby granted, free of charge, to any person or organization
 * obtaining a copy of the software and accompanying documentation covered by
 * this license (the "Software") to use, reproduce, display, distribute,
 * execute, and transmit the Software, and to prepare derivative works of the
 * Software, and to permit third-parties to whom the Software is furnished to
 * do so, all subject to the following:
 *
 * The copyright notices in the Software and this entire statement, including
 * the above license grant, this restriction and the following disclaimer,
 * must be included in all copies of the Software, in whole or in part, and
 * all derivative works of the Software, unless such copies or derivative
 * works are solely in the form of machine-executable object code generated by
 * a source language processor.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
 * SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
 * FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 * DEALINGS IN THE SOFTWARE.
 */


#ifndef SPT_CHECKSUM
#define SPT_CHECKSUM

#if defined( ARDUINO )
#include "../StandardCplusplus/string"
#else
#include <string>
#endif

namespace spt
{
  /// @brief This class calculates CRC-32 or Adler-32 checksums for arbitrary data.
  ///
  /// A cyclic redundancy check (CRC) is a type of hash function, which is used to produce a
  /// small, fixed-size checksum of a larger block of data, such as a packet of network
  /// traffic or a computer file. CRC-32 is one of the most commonly used CRC algorithms.
  ///
  /// Adler-32 is a checksum algorithm which was invented by Mark Adler.
  /// It is almost as reliable as a 32-bit cyclic redundancy check for protecting against
  /// accidental modification of data, such as distortions occurring during a transmission,
  /// but is significantly faster to calculate in software.
  class Checksum
  {
  public:
    enum Type
    {
      TYPE_ADLER32 = 0,
      TYPE_CRC32
    };

    /// Creates the Checksum, using the given type initialised to 0.
    Checksum( Type t = TYPE_CRC32 );

    /// Destroys the Checksum.
    ~Checksum() {}

    /// Updates the checksum with the given data.
    void update( const char* data, uint16_t length );

    /// Updates the checksum with the given data.
    void update( const std::string& data )
    {
      update( data.c_str(), static_cast<uint32_t>( data.size() ) );
    }

    /// Updates the checksum with the given data.
    void update( char data ) { update( &data, 1 ); }

    /// Returns the calculated checksum.
    uint32_t checksum() const { return value; }

    /// Which type of checksum are we calulcating
    Type getType() const { return type; }

  private:
    Type type;
    uint32_t value;
  };

} // namespace spt


#endif // SPT_CHECKSUM

/*
 * Checksum.cpp
 *
 * Copyright (c) 2007, Applied Informatics Software Engineering GmbH.
 * and Contributors.
 *
 * Permission is hereby granted, free of charge, to any person or organization
 * obtaining a copy of the software and accompanying documentation covered by
 * this license (the "Software") to use, reproduce, display, distribute,
 * execute, and transmit the Software, and to prepare derivative works of the
 * Software, and to permit third-parties to whom the Software is furnished to
 * do so, all subject to the following:
 *
 * The copyright notices in the Software and this entire statement, including
 * the above license grant, this restriction and the following disclaimer,
 * must be included in all copies of the Software, in whole or in part, and
 * all derivative works of the Software, unless such copies or derivative
 * works are solely in the form of machine-executable object code generated by
 * a source language processor.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
 * SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
 * FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 * DEALINGS IN THE SOFTWARE.
 */


#include "Checksum.h"
#include "SPT.h"

namespace spt
{
  namespace checksum
  {
    const uint32_t Polynomial = 0xEDB88320;
    #define BASE 65521 /* largest prime smaller than 65536 */

    uint32_t adler32( const Byte *buf, uint16_t len, uint32_t previousAdler = 1 )
    {
      uint32_t s1 = previousAdler & 0xffff;
      uint32_t s2 = ( previousAdler >> 16 ) & 0xffff;

      for ( uint16_t n = 0; n < len; ++n )
      {
        s1 = ( s1 + buf[n] ) % BASE;
        s2 = ( s2 + s1 ) % BASE;
      }

      return ( s2 << 16 ) + s1;
    }

    /// compute CRC32
    uint32_t crc32( const Byte* data, uint16_t length, uint32_t previousCrc32 = 0 )
    {
      uint32_t crc = ~previousCrc32; // same as previousCrc32 ^ 0xFFFFFFFF
      uint8_t* current = (uint8_t*) data;

      while ( length-- )
      {
        crc ^= *current++;
        for ( uint8_t j = 0; j < 8; ++j )
        {
          uint8_t lowestBit = crc & 1;
          crc >>= 1;
          if ( lowestBit ) crc ^= Polynomial;
        }
      }

      return ~crc; // same as crc ^ 0xFFFFFFFF
    }

  } // namespace checksum
} // namespace spt


using spt::Byte;
using spt::Checksum;


Checksum::Checksum( Type t ) : type( t ), value( 0 )
{
  if ( t == TYPE_ADLER32 ) value = 1;
}


void Checksum::update(const char* data, uint16_t length )
{
  if ( type == TYPE_ADLER32 ) value = spt::checksum::adler32( reinterpret_cast<const Byte*>( data ), length, value );
  else value = spt::checksum::crc32( reinterpret_cast<const Byte*>( data ), length, value );
}

#if defined( ARDUINO )
#include "tut.hpp"
#include "SPT.h"
#include "Checksum.h"
#else
#include <tut/tut.hpp>
#include <Checksum.h>
#include <SPT.h>
#endif

using spt::Checksum;
using std::string;

namespace tut
{
  struct ChecksumTestData {};

  typedef test_group<ChecksumTestData> ChecksumTestGroup;
  typedef ChecksumTestGroup::object ChecksumTest;
  ChecksumTestGroup checksumTestGroup( "Checksum test suite" );


  template<>
  template<>
  void ChecksumTest::test<1>()
  {
    set_test_name( "abc" );

    string s( "abc" );
    Checksum cs;
    cs.update( s );
    ensure( "abc", cs.checksum() == 891568578 );
    spt::printFreeRam();
  }


  template<>
  template<>
  void ChecksumTest::test<2>()
  {
    set_test_name( "lower case" );

    string s( "abcdefghijklmnopqrstuvwxyz" );
    Checksum cs;
    cs.update( s );
    ensure( "lower case", cs.checksum() == 1277644989 );
    spt::printFreeRam();
  }


  template<>
  template<>
  void ChecksumTest::test<3>()
  {
    set_test_name( "upper case" );

    string s( "ABCDEFGHIJKLMNOPQRSTUVWXYZ" );
    Checksum cs;
    cs.update( s );
    ensure( "upper case", cs.checksum() == 2885122082 );
    spt::printFreeRam();
  }


  template<>
  template<>
  void ChecksumTest::test<4>()
  {
    set_test_name( "numbers and characters" );

    string s( "ABCDEFGHIJKL12345678901234567890123456789012345678901234567890123456789012345678901234567890MNOPQRSTUVWXYZ" );
    Checksum cs;
    cs.update( s );
    ensure( "numbers and characters", cs.checksum() == 1170154626 );
    spt::printFreeRam();
  }


  template<>
  template<>
  void ChecksumTest::test<5>()
  {
    set_test_name( "adler" );

    string s( "ABCDEFGHIJKL12345678901234567890123456789012345678901234567890123456789012345678901234567890MNOPQRSTUVWXYZ" );
    Checksum cs( Checksum::TYPE_ADLER32 );
    cs.update( s );
    ensure( "adler", cs.checksum() == 3934918728 );
    spt::printFreeRam();
  }


  template<>
  template<>
  void ChecksumTest::test<6>()
  {
    set_test_name( "crcUpdates" );

    Checksum cs;
    cs.update( 'a' );
    cs.update( 'b' );
    cs.update( 'c' );
    ensure( "crcUpdates", cs.checksum() == 0x352441C2 );
    spt::printFreeRam();
  }


  template<>
  template<>
  void ChecksumTest::test<7>()
  {
    set_test_name( "adlerUpdates" );

    Checksum cs( Checksum::TYPE_ADLER32 );
    cs.update( 'a' );
    cs.update( 'b' );
    cs.update( 'c' );
    ensure( "adlerUpdates", cs.checksum() == 0x024D0127 );
    spt::printFreeRam();
  }
}