// -*- Pike -*-
// $Id$
// original author: Marc Dirix

#pike __REAL_VERSION__

//! CRC used in USB Token and Start-Of-Frame packets 

CrcAlgorithm CRC5_USB()
{
   return CrcAlgorithm( 5, ({ 5, 2, 0 }), 0x1F , 1, 0, 0x1F );
}

//! Used in ATM HEC and SMBus.

CrcAlgorithm CRC8_SMBUS()
{
   return CrcAlgorithm( 8, ({ 8, 2, 1, 0 }), 0 , 0, 0, 0 );
}

//! Used in Controller Area Network Frames
CrcAlgorithm CRC15()
{
   return CrcAlgorithm( 15, ({ 15, 14, 10, 8, 7, 4, 3, 0 }), 0 , 0, 0, 0 );
}

//! CRC16 IBM Standard
CrcAlgorithm CRC16()
{
   return CrcAlgorithm( 16, ({ 16, 15, 2, 0 }), 0 , 1, 0, 0 );
}

//! CRC16 xmodem or zmodem. Also used for PlugWise.
CrcAlgorithm CRC16X()
{
   return CrcAlgorithm( 16, 0x11021, 0, 0, 0 , 0);
}

//! Used in USB data packets
CrcAlgorithm CRC16_USB()
{
   return CrcAlgorithm( 16, ({ 16, 15, 2, 0 }), 0xFFFF , 1, 0, 0xFFFF );
}

//! CRC16 CCITT
//! @param seed
//! A integer starting value. If not set, seed=0xFFFF
CrcAlgorithm CRC_CCITT(int | void seed)
{
   int z = seed | 0xFFFF;
   return CrcAlgorithm( 16, ({ 16, 12, 5, 0 }), z , 0, 0, 0x0000 );
}

//! This is the algorithm used in X.25 and for the HDLC 2-byte FCS.
CrcAlgorithm CRC_HDLC()
{
   return CrcAlgorithm( 16, ({ 16, 12, 5, 0 }), 0xFFFF , 1, 0, 0xFFFF );
}

//! Used in RFC-2440 and MIL STD 188-184
CrcAlgorithm CRC24()
{
   return CrcAlgorithm( 24, ({ 24, 23, 18, 17, 14, 11, 10, 7, 6, 5, 4, 3, 1, 0}), 0xB704CE , 0, 0, 0 );
}

//! 32 Bit CRC algorithm.
CrcAlgorithm CRC32()
{
   return CrcAlgorithm( 32, ({ 32, 26, 23, 22, 16, 12, 11, 10, 8, 7, 5, 4, 2, 1, 0 }), 0xFFFFFFFF , 1, 0, 0xFFFFFFFF );
}

//! Used iSCSI (RFC-3385); usually credited to Guy Castagnoli
CrcAlgorithm CRC32C()
{
   return CrcAlgorithm( 16, ({ 32, 28, 27, 26, 25, 23, 22, 20, 19, 18, 14, 13, 11, 10, 9, 8, 6, 0 }), 0xFFFFFFFF , 1, 0, 0xFFFFFFFF );
}

//! ISO 3309
CrcAlgorithm CRC64()
{
   return CrcAlgorithm( 64, ({ 64, 4, 3, 1, 0 }), 0 , 1, 0, 0 );
}

//! A 256 bit CRC.
CrcAlgorithm CRC256()
{
   return CrcAlgorithm( 256, 
             0x82E2443E6320383A20B8A2A0A1EA91A3CCA99A30C5205038349C82AAA3A8FD2, 
            0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF,
            1, 0, 0 );
}

//! Inverts an integer.
//! @param value
//!    The integer to be inverted.
//! @param width
//!    The bit-length of the integer.
int reflect(int value, int width)
{
   int ret=0;
   for(int i=0; i<width; i++)
      ret+= (((value >> i) & 1) << (width -1 -i));
   return ret;
}

//! The main CRC class.
class CrcAlgorithm
{
   array polynomial=({});
   int seed=0;
   int width;
   int lsbFirst=0;
   int lsbFirstData=0;
   int xormask=0;
   
   //! Creates a CRC object.
   //! @param width
   //!    The length of the polynomial.
   //! @param polynomial
   //!    The polynomial, either an array or integer.
   //! @param seed
   //!    The starting value of the algoritm
   //! @param lsbFirst
   //!    Calculate the CRC from msb to lsb (zero) or lsb to msb (non zero).
   //! @param lsbFirstData
   //!    Calculate the data words from msb to lsb (zero) or lsb to msb (non zero).
   //!    If lsbFirstData is zero, lsbFirstData behaviour follows lsbFirst.
   //!  @param xormask
   //!     The output mask for the final computed CRC.
   void create(int width, int|array polynomial, int seed, int lsbFirst, int lsbFirstData,int xormask)
   {
      int polymask;
      this->width=width;
      this->seed=seed;     
      this->lsbFirst=lsbFirst;
      this->lsbFirstData=lsbFirstData;
      this->xormask=xormask;

      if (arrayp(polynomial))
         this->polynomial=polynomial;
      else 
      {
         polymask=polynomial;
         if(lsbFirst)
            polymask=reflect(polymask,width);
         this->polynomial = ({width});
         for( int i=(width-1); i>=0 ; --i)
         {
            if ( (polymask >> i) & 1)
            {
               this->polynomial +=({i}); 
            }
         }
      
      }
   }
   
   //! Calculate and returns CRC over a string.
   //! @param s
   //!    The string over which the CRC has to be calculated.
   int calcString( string s )
   {
         object a = CrcRegister( this );
      a->takeString(s);
      return a->getFinalValue();
   }
 
}

//! This Class holds the intermediate state of the CRC algorithm
class CrcRegister()
{
   CrcAlgorithm alg;
   int bitmask;
   int polymask;
   int lsbFirstData=0;
   int inBitMask;
   int outBitMask;
   int value;
   
   //! Create the object.
   //! @param alg
   //!    The CRC object.
   void create( CrcAlgorithm alg )
   {
      this->alg = alg;
      bitmask = (1 << alg->width) -1;
      int word = 0;
      foreach(alg->polynomial,int n)
         word |= 1 << n;
      polymask = word & bitmask;

      if(alg->lsbFirst)
      {
         polymask = reflect(polymask,alg->width);
         inBitMask = 1 << (alg->width -1 );
         outBitMask = 1;
      }
      else
      {
         this->inBitMask = 1;
         this->outBitMask = 1 << ( alg->width -1 );
      }
     
      this->lsbFirstData =  alg->lsbFirstData | alg->lsbFirst;
      this->value = alg->seed;   
   }
   
   //! Add's one bit to the CRC calculation.
   void takeBit( int bit )
   {
      int outBit;
      if ( bit > 1 || bit < 0 )
         werror( "Values other then 0 or 1 are not allowed for bits\n");
      outBit = ((this->value & this->outBitMask) !=0 );
      if ( alg->lsbFirst )
         value >>= 1;
      else
         value <<= 1;
      value &= bitmask;
      if ( outBit ^ bit )
         value ^= polymask; 
   }
  
   //! Add one word (int) to the CRC calculation.
   //! @param word
   //!    The added word (int)
   //! @param width
   //!    The bitlength of the word value. 
   //!    If none given a bitlength of 8 is assumed. 
   void takeWord( int word, int|void width )
   {
      int len = 8;
      if ( width > 0 )
         len = width;
      if ( this->lsbFirstData ) 
         for ( int i = 0; i < len; i++ )
            this->takeBit( (word >> i) & 1 );
      else
         for ( int i = (len-1) ; i >= 0 ; i-- )
            this->takeBit( (word >> i) & 1 );
         
   }
   
   //! Add a string to the CRC computation.
   //! @param s
   //!    The string to be added.
   void takeString( string s )
   {
     int len = String.width(s);
     foreach( s/"", string s)
         takeWord( s[0] , len);
   }
   
   //! Get the current intermediate state of the CRC algoritm.
   int getValue()
   {
      return value;
   }

   //! Returns the computed CRC value with xormask applied.
   int getFinalValue()
   {
      return value ^ alg->xormask;
   }
}