//  Boost CRC library crc.hpp header file  -----------------------------------//

//  Copyright 2001, 2004 Daryle Walker.  Use, modification, and distribution are

//  subject to the Boost Software License, Version 1.0.  (See accompanying file

//  LICENSE_1_0.txt or a copy at <http://www.boost.org/LICENSE_1_0.txt>.)

//  See <http://www.boost.org/libs/crc/> for the library's home page.

#ifndef BOOST_CRC_HPP

#define BOOST_CRC_HPP

#include <boost/config.hpp>   // for BOOST_STATIC_CONSTANT, etc.

#include <boost/integer.hpp>  // for boost::uint_t

#include <climits>  // for CHAR_BIT, etc.

#include <cstddef>  // for std::size_t

#include <boost/limits.hpp>  // for std::numeric_limits

// The type of CRC parameters that can go in a template should be related

// on the CRC's bit count.  This macro expresses that type in a compact

// form, but also allows an alternate type for compilers that don't support

// dependent types (in template value-parameters).

#if !(defined(BOOST_NO_DEPENDENT_TYPES_IN_TEMPLATE_VALUE_PARAMETERS) || (defined(BOOST_MSVC) && (BOOST_MSVC <= 1300)))

#define BOOST_CRC_PARM_TYPE  typename ::boost::uint_t<Bits>::fast

#else

#define BOOST_CRC_PARM_TYPE  unsigned long

#endif

// Some compilers [MS VC++ 6] cannot correctly set up several versions of a

// function template unless every template argument can be unambiguously

// deduced from the function arguments.  (The bug is hidden if only one version

// is needed.)  Since all of the CRC function templates have this problem, the

// workaround is to make up a dummy function argument that encodes the template

// arguments.  Calls to such template functions need all their template

// arguments explicitly specified.  At least one compiler that needs this

// workaround also needs the default value for the dummy argument to be

// specified in the definition.

#if defined(__GNUC__) || !defined(BOOST_NO_EXPLICIT_FUNCTION_TEMPLATE_ARGUMENTS)

#define BOOST_CRC_DUMMY_PARM_TYPE

#define BOOST_CRC_DUMMY_INIT

#define BOOST_ACRC_DUMMY_PARM_TYPE

#define BOOST_ACRC_DUMMY_INIT

#else

namespace boost { namespace detail {

    template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,

     BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,

     bool ReflectIn, bool ReflectRem >

    struct dummy_crc_argument  { };

} }

#define BOOST_CRC_DUMMY_PARM_TYPE   , detail::dummy_crc_argument<Bits, \

 TruncPoly, InitRem, FinalXor, ReflectIn, ReflectRem> *p_

#define BOOST_CRC_DUMMY_INIT        BOOST_CRC_DUMMY_PARM_TYPE = 0

#define BOOST_ACRC_DUMMY_PARM_TYPE  , detail::dummy_crc_argument<Bits, \

 TruncPoly, 0, 0, false, false> *p_

#define BOOST_ACRC_DUMMY_INIT       BOOST_ACRC_DUMMY_PARM_TYPE = 0

#endif

namespace boost

{

//  Forward declarations  ----------------------------------------------------//

template < std::size_t Bits >

    class crc_basic;

template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly = 0u,

           BOOST_CRC_PARM_TYPE InitRem = 0u,

           BOOST_CRC_PARM_TYPE FinalXor = 0u, bool ReflectIn = false,

           bool ReflectRem = false >

    class crc_optimal;

template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,

           BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,

           bool ReflectIn, bool ReflectRem >

    typename uint_t<Bits>::fast  crc( void const *buffer,

     std::size_t byte_count

     BOOST_CRC_DUMMY_PARM_TYPE );

template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly >

    typename uint_t<Bits>::fast  augmented_crc( void const *buffer,

     std::size_t byte_count, typename uint_t<Bits>::fast initial_remainder

     BOOST_ACRC_DUMMY_PARM_TYPE );

template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly >

    typename uint_t<Bits>::fast  augmented_crc( void const *buffer,

     std::size_t byte_count

     BOOST_ACRC_DUMMY_PARM_TYPE );

typedef crc_optimal<16, 0x8005, 0, 0, true, true>         crc_16_type;

typedef crc_optimal<16, 0x1021, 0xFFFF, 0, false, false>  crc_ccitt_type;

typedef crc_optimal<16, 0x8408, 0, 0, true, true>         crc_xmodem_type;

typedef crc_optimal<32, 0x04C11DB7, 0xFFFFFFFF, 0xFFFFFFFF, true, true>

  crc_32_type;

//  Forward declarations for implementation detail stuff  --------------------//

//  (Just for the stuff that will be needed for the next two sections)

namespace detail

{

    template < std::size_t Bits >

        struct mask_uint_t;

    template <  >

        struct mask_uint_t< std::numeric_limits<unsigned char>::digits >;

    #if USHRT_MAX > UCHAR_MAX

    template <  >

        struct mask_uint_t< std::numeric_limits<unsigned short>::digits >;

    #endif

    #if UINT_MAX > USHRT_MAX

    template <  >

        struct mask_uint_t< std::numeric_limits<unsigned int>::digits >;

    #endif

    #if ULONG_MAX > UINT_MAX

    template <  >

        struct mask_uint_t< std::numeric_limits<unsigned long>::digits >;

    #endif

    template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly, bool Reflect >

        struct crc_table_t;

    template < std::size_t Bits, bool DoReflect >

        class crc_helper;

    #ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION

    template < std::size_t Bits >

        class crc_helper< Bits, false >;

    #endif

}  // namespace detail

//  Simple cyclic redundancy code (CRC) class declaration  -------------------//

template < std::size_t Bits >

class crc_basic

{

    // Implementation type

    typedef detail::mask_uint_t<Bits>  masking_type;

public:

    // Type

    typedef typename masking_type::least  value_type;

    // Constant for the template parameter

    BOOST_STATIC_CONSTANT( std::size_t, bit_count = Bits );

    // Constructor

    explicit  crc_basic( value_type truncated_polynominal,

               value_type initial_remainder = 0, value_type final_xor_value = 0,

               bool reflect_input = false, bool reflect_remainder = false );

    // Internal Operations

    value_type  get_truncated_polynominal() const;

    value_type  get_initial_remainder() const;

    value_type  get_final_xor_value() const;

    bool        get_reflect_input() const;

    bool        get_reflect_remainder() const;

    value_type  get_interim_remainder() const;

    void        reset( value_type new_rem );

    void        reset();

    // External Operations

    void  process_bit( bool bit );

    void  process_bits( unsigned char bits, std::size_t bit_count );

    void  process_byte( unsigned char byte );

    void  process_block( void const *bytes_begin, void const *bytes_end );

    void  process_bytes( void const *buffer, std::size_t byte_count );

    value_type  checksum() const;

private:

    // Member data

    value_type  rem_;

    value_type  poly_, init_, final_;  // non-const to allow assignability

    bool        rft_in_, rft_out_;     // non-const to allow assignability

};  // boost::crc_basic

//  Optimized cyclic redundancy code (CRC) class declaration  ----------------//

template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,

           BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,

           bool ReflectIn, bool ReflectRem >

class crc_optimal

{

    // Implementation type

    typedef detail::mask_uint_t<Bits>  masking_type;

public:

    // Type

    typedef typename masking_type::fast  value_type;

    // Constants for the template parameters

    BOOST_STATIC_CONSTANT( std::size_t, bit_count = Bits );

    BOOST_STATIC_CONSTANT( value_type, truncated_polynominal = TruncPoly );

    BOOST_STATIC_CONSTANT( value_type, initial_remainder = InitRem );

    BOOST_STATIC_CONSTANT( value_type, final_xor_value = FinalXor );

    BOOST_STATIC_CONSTANT( bool, reflect_input = ReflectIn );

    BOOST_STATIC_CONSTANT( bool, reflect_remainder = ReflectRem );

    // Constructor

    explicit  crc_optimal( value_type init_rem = InitRem );

    // Internal Operations

    value_type  get_truncated_polynominal() const;

    value_type  get_initial_remainder() const;

    value_type  get_final_xor_value() const;

    bool        get_reflect_input() const;

    bool        get_reflect_remainder() const;

    value_type  get_interim_remainder() const;

    void        reset( value_type new_rem = InitRem );

    // External Operations

    void  process_byte( unsigned char byte );

    void  process_block( void const *bytes_begin, void const *bytes_end );

    void  process_bytes( void const *buffer, std::size_t byte_count );

    value_type  checksum() const;

    // Operators

    void        operator ()( unsigned char byte );

    value_type  operator ()() const;

private:

    // The implementation of output reflection depends on both reflect states.

    BOOST_STATIC_CONSTANT( bool, reflect_output = (ReflectRem != ReflectIn) );

    #ifndef __BORLANDC__

    #define BOOST_CRC_REF_OUT_VAL  reflect_output

    #else

    typedef crc_optimal  self_type;

    #define BOOST_CRC_REF_OUT_VAL  (self_type::reflect_output)

    #endif

    // More implementation types

    typedef detail::crc_table_t<Bits, TruncPoly, ReflectIn>  crc_table_type;

    typedef detail::crc_helper<Bits, ReflectIn>              helper_type;

    typedef detail::crc_helper<Bits, BOOST_CRC_REF_OUT_VAL>  reflect_out_type;

    #undef BOOST_CRC_REF_OUT_VAL

    // Member data

    value_type  rem_;

};  // boost::crc_optimal

//  Implementation detail stuff  ---------------------------------------------//

namespace detail

{

    // Forward declarations for more implementation details

    template < std::size_t Bits >

        struct high_uint_t;

    template < std::size_t Bits >

        struct reflector;

    // Traits class for mask; given the bit number

    // (1-based), get the mask for that bit by itself.

    template < std::size_t Bits >

    struct high_uint_t

        : boost::uint_t< Bits >

    {

        typedef boost::uint_t<Bits>        base_type;

        typedef typename base_type::least  least;

        typedef typename base_type::fast   fast;

#if defined(__EDG_VERSION__) && __EDG_VERSION__ <= 243

        static const least high_bit = 1ul << ( Bits - 1u );

        static const fast high_bit_fast = 1ul << ( Bits - 1u );

#else

        BOOST_STATIC_CONSTANT( least, high_bit = (least( 1u ) << ( Bits

         - 1u )) );

        BOOST_STATIC_CONSTANT( fast, high_bit_fast = (fast( 1u ) << ( Bits

         - 1u )) );

#endif

    };  // boost::detail::high_uint_t

    // Reflection routine class wrapper

    // (since MS VC++ 6 couldn't handle the unwrapped version)

    template < std::size_t Bits >

    struct reflector

    {

        typedef typename boost::uint_t<Bits>::fast  value_type;

        static  value_type  reflect( value_type x );

    };  // boost::detail::reflector

    // Function that reflects its argument

    template < std::size_t Bits >

    typename reflector<Bits>::value_type

    reflector<Bits>::reflect

    (

        typename reflector<Bits>::value_type  x

    )

    {

        value_type        reflection = 0;

        value_type const  one = 1;

        for ( std::size_t i = 0 ; i < Bits ; ++i, x >>= 1 )

        {

            if ( x & one )

            {

                reflection |= ( one << (Bits - 1u - i) );

            }

        }

        return reflection;

    }

    // Traits class for masks; given the bit number (1-based),

    // get the mask for that bit and its lower bits.

    template < std::size_t Bits >

    struct mask_uint_t

        : high_uint_t< Bits >

    {

        typedef high_uint_t<Bits>          base_type;

        typedef typename base_type::least  least;

        typedef typename base_type::fast   fast;

        #ifndef __BORLANDC__

        using base_type::high_bit;

        using base_type::high_bit_fast;

        #else

        BOOST_STATIC_CONSTANT( least, high_bit = base_type::high_bit );

        BOOST_STATIC_CONSTANT( fast, high_bit_fast = base_type::high_bit_fast );

        #endif

#if defined(__EDG_VERSION__) && __EDG_VERSION__ <= 243

        static const least sig_bits = (~( ~( 0ul ) << Bits )) ;

#else

        BOOST_STATIC_CONSTANT( least, sig_bits = (~( ~(least( 0u )) << Bits )) );

#endif

#if defined(__GNUC__) && __GNUC__ == 4 && __GNUC_MINOR__ == 0 && __GNUC_PATCHLEVEL__ == 2

        // Work around a weird bug that ICEs the compiler in build_c_cast

        BOOST_STATIC_CONSTANT( fast, sig_bits_fast = static_cast<fast>(sig_bits) );

#else

        BOOST_STATIC_CONSTANT( fast, sig_bits_fast = fast(sig_bits) );

#endif

    };  // boost::detail::mask_uint_t

    template <  >

    struct mask_uint_t< std::numeric_limits<unsigned char>::digits >

        : high_uint_t< std::numeric_limits<unsigned char>::digits >

    {

        typedef high_uint_t<std::numeric_limits<unsigned char>::digits>

          base_type;

        typedef base_type::least  least;

        typedef base_type::fast   fast;

        #ifndef __BORLANDC__

        using base_type::high_bit;

        using base_type::high_bit_fast;

        #else

        BOOST_STATIC_CONSTANT( least, high_bit = base_type::high_bit );

        BOOST_STATIC_CONSTANT( fast, high_bit_fast = base_type::high_bit_fast );

        #endif

        BOOST_STATIC_CONSTANT( least, sig_bits = (~( least(0u) )) );

        BOOST_STATIC_CONSTANT( fast, sig_bits_fast = fast(sig_bits) );

    };  // boost::detail::mask_uint_t

    #if USHRT_MAX > UCHAR_MAX

    template <  >

    struct mask_uint_t< std::numeric_limits<unsigned short>::digits >

        : high_uint_t< std::numeric_limits<unsigned short>::digits >

    {

        typedef high_uint_t<std::numeric_limits<unsigned short>::digits>

          base_type;

        typedef base_type::least  least;

        typedef base_type::fast   fast;

        #ifndef __BORLANDC__

        using base_type::high_bit;

        using base_type::high_bit_fast;

        #else

        BOOST_STATIC_CONSTANT( least, high_bit = base_type::high_bit );

        BOOST_STATIC_CONSTANT( fast, high_bit_fast = base_type::high_bit_fast );

        #endif

        BOOST_STATIC_CONSTANT( least, sig_bits = (~( least(0u) )) );

        BOOST_STATIC_CONSTANT( fast, sig_bits_fast = fast(sig_bits) );

    };  // boost::detail::mask_uint_t

    #endif

    #if UINT_MAX > USHRT_MAX

    template <  >

    struct mask_uint_t< std::numeric_limits<unsigned int>::digits >

        : high_uint_t< std::numeric_limits<unsigned int>::digits >

    {

        typedef high_uint_t<std::numeric_limits<unsigned int>::digits>

          base_type;

        typedef base_type::least  least;

        typedef base_type::fast   fast;

        #ifndef __BORLANDC__

        using base_type::high_bit;

        using base_type::high_bit_fast;

        #else

        BOOST_STATIC_CONSTANT( least, high_bit = base_type::high_bit );

        BOOST_STATIC_CONSTANT( fast, high_bit_fast = base_type::high_bit_fast );

        #endif

        BOOST_STATIC_CONSTANT( least, sig_bits = (~( least(0u) )) );

        BOOST_STATIC_CONSTANT( fast, sig_bits_fast = fast(sig_bits) );

    };  // boost::detail::mask_uint_t

    #endif

    #if ULONG_MAX > UINT_MAX

    template <  >

    struct mask_uint_t< std::numeric_limits<unsigned long>::digits >

        : high_uint_t< std::numeric_limits<unsigned long>::digits >

    {

        typedef high_uint_t<std::numeric_limits<unsigned long>::digits>

          base_type;

        typedef base_type::least  least;

        typedef base_type::fast   fast;

        #ifndef __BORLANDC__

        using base_type::high_bit;

        using base_type::high_bit_fast;

        #else

        BOOST_STATIC_CONSTANT( least, high_bit = base_type::high_bit );

        BOOST_STATIC_CONSTANT( fast, high_bit_fast = base_type::high_bit_fast );

        #endif

        BOOST_STATIC_CONSTANT( least, sig_bits = (~( least(0u) )) );

        BOOST_STATIC_CONSTANT( fast, sig_bits_fast = fast(sig_bits) );

    };  // boost::detail::mask_uint_t

    #endif

    // CRC table generator

    template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly, bool Reflect >

    struct crc_table_t

    {

        BOOST_STATIC_CONSTANT( std::size_t, byte_combos = (1ul << CHAR_BIT) );

        typedef mask_uint_t<Bits>            masking_type;

        typedef typename masking_type::fast  value_type;

#if defined(__BORLANDC__) && defined(_M_IX86) && (__BORLANDC__ == 0x560)

        // for some reason Borland's command line compiler (version 0x560)

        // chokes over this unless we do the calculation for it:

        typedef value_type                   table_type[ 0x100 ];

#else

        typedef value_type                   table_type[ byte_combos ];

#endif

        static  void  init_table();

        static  table_type  table_;

    };  // boost::detail::crc_table_t

    // CRC table generator static data member definition

    // (Some compilers [Borland C++] require the initializer to be present.)

    template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly, bool Reflect >

    typename crc_table_t<Bits, TruncPoly, Reflect>::table_type

    crc_table_t<Bits, TruncPoly, Reflect>::table_

     = { 0 };

    // Populate CRC lookup table

    template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly, bool Reflect >

    void

    crc_table_t<Bits, TruncPoly, Reflect>::init_table

    (

    )

    {

        // compute table only on the first run

        static  bool  did_init = false;

        if ( did_init )  return;

        // factor-out constants to avoid recalculation

        value_type const     fast_hi_bit = masking_type::high_bit_fast;

        unsigned char const  byte_hi_bit = 1u << (CHAR_BIT - 1u);

        // loop over every possible dividend value

        unsigned char  dividend = 0;

        do

        {

            value_type  remainder = 0;

            // go through all the dividend's bits

            for ( unsigned char mask = byte_hi_bit ; mask ; mask >>= 1 )

            {

                // check if divisor fits

                if ( dividend & mask )

                {

                    remainder ^= fast_hi_bit;

                }

                // do polynominal division

                if ( remainder & fast_hi_bit )

                {

                    remainder <<= 1;

                    remainder ^= TruncPoly;

                }

                else

                {

                    remainder <<= 1;

                }

            }

            table_[ crc_helper<CHAR_BIT, Reflect>::reflect(dividend) ]

             = crc_helper<Bits, Reflect>::reflect( remainder );

        }