/*=============================================================================
|
| NAME
|  
|      shiftRegister.cpp
|
| DESCRIPTION
|  
|     Binary linear feedback shift register class implementation.
|
| AUTHOR
|
|      Sean O'Connor
|    
| LEGAL
|
|     CRCDemo Version 2.1 - A Program for generating and checking CRC codes.
|     Copyright (C) 1999-2017 by Sean Erik O'Connor.  All Rights Reserved.
|
|     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/>.
|     
|     The author's address is artificer!AT!seanerikoconnor!DOT!freeservers!DOT!com
|     with !DOT! replaced by . and the !AT! replaced by @
|
+============================================================================*/

#include <string>
using namespace std ;

#include "dataTypes.h"
#include "shiftRegister.h"      //  class Shift_register()



/*=============================================================================
|
| NAME
|  
|     ShiftRegister
|
| DESCRIPTION
|  
|     Contructor for ShiftRegister class.  Initializes shift register contents
|     to zero, and sets up the given generator polynomial.
|
| PARAMETERS
|
|     generatorPoly   (Input)  Generator polynomial (yields shift register feedback
|                              connections).  Input in the form of a string. e.g.       
|                              ShiftRegister sr( "x ^ 16 + x ^ 15 + x ^ 2 + 1" ) ;
| RETURNS
|
| EXCEPTIONS
|
|    If there is an error, the degree of the generator polynomial
|    is zero.
|
| SIDE EFFECTS
|
| METHOD
|
|    Read the polynomial string backwards, from lowest to highest degree
|    coefficients.  Handle the constant term and x term as special cases.
|    Pack the coefficients into the generator polynomial in reverse bit order,
|    dropping the highest degree term.
|
|    For example, if g( x ) = x ^ 16  +  x ^ 15  +  x ^ 2  +  1
|    we represent g( x ) as A001 (hexadecimal).  This is the scheme:
|
|    Coefficients:           1 1000 0000 0000 0101
|    Reversed:               1010 0000 0000 0001 1
|    x ^ 16 term dropped:    1010 0000 0000 0001
|    Hexadecimal:              A    0    0    1
|    
|    Another example is CRC-32Q which has generator polynomial,
|    g( x ) = x^32+x^31+x^24+x^22+x^16+x^14+x^8+x^7+x^5+x^3+x+1
|   
|    Coefficients:           1 1000 0001 0100 0001 0100 0001 1010 1011
|    Reversed:               1101 0101 1000 0010 1000 0010 1000 0001 1
|    x ^ 16 term dropped:    1101 0101 1000 0010 1000 0010 1000 0001
|    Hexadecimal:              D    5    8    2    8    2    8    1
|
| BUGS
|
|    Assumes the polynomial has a constant term.
|    For 32 bit CRC, the leading bit in the generator
|    polynomial is trashed to zero.
|
| AUTHOR
|  
|     Sean E. O'Connor           2 February 2000
|
+============================================================================*/

ShiftRegister::ShiftRegister( const string & g )
              : contents_( 0 )            // Initial shift register contents is zero.
              , generatorPoly_( 0 )       // Polynomial is also initially zero.
              , degreeGeneratorPoly_( 0 ) // Zero degree, i.e. constant.  
{
    int i ;            //  Index of current character in polynomial string.
    int powerOfX = 0 ;
    int lastPowerOfX = 0 ;

    //  The polynomial string must have at least one character in it.
    if (g.empty())
        return ;

    // Point to the last character in the string.
    i = g.length() - 1 ;

    //  Skip trailing blanks at the end of the string.
    while (g[ i ] == ' ')
        --i ;

    //  Read the polynomial's constant term, if any,
    //  and add it as a 1 bit to the end of the buffer.
    if (g[ i ] == '1')
    {
        generatorPoly_ |= 1 ;
        --i ;
    }
    else              // No constant term --- error.
        return ;

    //  Parse the remaining x ^ n terms, assuming there is at 
    //  least one of them.

    while (i > 0)
    {
        while (g[ i ] == ' ')     // Skip any blanks.
            --i ;

        if (g[ i ] == '+')        // Eat the '+'.
            --i ;
        else                      // No plus means bad syntax.
            return ;

        while (g[ i ] == ' ')     // Skip any blanks.
            --i ;

        // Parse the "x" term, if any, shift left, and add a 
        // 1 bit to the end of the buffer.
        if (g[ i ] == 'X' || g[ i ] == 'x')
        {
            powerOfX = 1 ;
            --i ;
        }
        else  //  Parse the exponent "n" in the term "x ^ n".
        {
            int powerOf10 = 1 ;

            // Read digits from back to front.
            for (powerOfX = 0 ;
                 i > 0 && ('0' <= g[ i ] && g[ i ] <= '9') ;
                 --i, powerOf10 *= 10)
            {
                powerOfX += powerOf10 * (g[ i ] - (int)'0') ;
            }
        }

        while (g[ i ] == ' ')   // Skip blanks yet again.
            --i ;

        //  Parse the "x ^" part of the term "x ^ n".
        //  If we just parsed "x", we can skip this part.
        if (powerOfX > 1)
        {
             // Parse the exponentiation '^' symbol.
             if (g[ i ] == '^')
                --i ;
             else
                return ;

             while (g[ i ] == ' ')    // Skip blanks.
                 --i ;

             // Parse the "x" symbol.
            if (g[ i ] == 'X' || g[ i ] == 'x')
                --i ;
            else
                return ;

        } // end parse x ^ n.


        // Check that powers of x are increasing.
        if (powerOfX <= lastPowerOfX)
            return ;


        // Shift the coefficient "x ^ n" into place within 
        // the generator polynomial, in bit reversed order.
        // If we get the term x^N, where N = number of bits
        // in the generatorPoly buffer, which is the highest
        // possible term, shift by one less, since we'll
        // chop it off below anyway.
        int shiftLeftAmount = powerOfX - lastPowerOfX ;

        if (powerOfX == (8 * sizeof( generatorPoly_ )))
            --shiftLeftAmount ;

        for (int j = 0 ;  j < shiftLeftAmount ;  ++j )
           generatorPoly_ <<= 1 ;

        generatorPoly_ |= 1 ;

        lastPowerOfX = powerOfX ;

    } // end while i > 0

    //  Chop off the leading power of x, unless we've already
    //  handled the x^N case above.
    if (powerOfX != (8 * sizeof( generatorPoly_ )))
        generatorPoly_ >>= 1 ;

    //  Record the generator polynomial degree.
    degreeGeneratorPoly_ = lastPowerOfX ;

} // --------------------------< end ShiftRegister >----------------------------



/*=============================================================================
|
| NAME
|  
|     shiftInBit
|
| DESCRIPTION
|  
|     Shift one bit into the shift register.
|
| PARAMETERS
|
|    dataBit (Input)  Bit to shift into the shift register.  Must be 1 or 0 only.
|
| RETURNS
|
| EXCEPTIONS
|
| SIDE EFFECTS
|
| METHOD
|
| BUGS
|
| AUTHOR
|  
|     Sean E. O'Connor           2 February 2000
|
+============================================================================*/

void ShiftRegister::shiftInBit( int dataBit )
{
    syndrome_t feedback = 0 ;

    // To compute the feedback, add incoming data bit and leading bit of 
    // shift register modulo 2.  This is an XOR operation in computer talk.
    // Recall that we've reversed the order of the shift register circuit.
    if (dataBit ^ (contents_ & 1))
        feedback = generatorPoly_ ;
    else
        feedback = 0 ;

    // Shift.
    contents_ >>= 1 ;

    // Now were ready to add in the generator polynomial coefficients modulo 2
    // (or XOR if you prefer).
    contents_ ^= feedback ;

} // --------------------------< end shiftInBit >----------------------------



ShiftRegister::~ShiftRegister( void )
{

}


/*=============================================================================
|
| NAME
|  
|     shiftInByte
|
| DESCRIPTION
|  
|     Shift one byte into the shift register.
|
| PARAMETERS
|
|    dataByte (Input)  Byte to shift into the shift register.
|
| RETURNS
|
| EXCEPTIONS
|
| SIDE EFFECTS
|
| METHOD
|
| BUGS
|
| AUTHOR
|  
|     Sean E. O'Connor           2 February 2000
|
+============================================================================*/

void ShiftRegister::shiftInByte( unsigned char dataByte )
{
    int             i = 0 ;
    unsigned int mask = 0x80 ;

    // Shift in the 8 bits in the byte in left to right order.
    for (i = 0, mask = 0x80 ;  i < 8 ;  ++i, mask >>= 1)
        shiftInBit( ((mask & (unsigned int) dataByte) == 0 ? 0 : 1)  ) ;

} // --------------------------< end shiftInByte >----------------------------



/*=============================================================================
|
| NAME
|  
|     shiftRegContents
|
| DESCRIPTION
|  
|     Return the contents of the shift register.
|
| RETURNS
|
|     The GF( 2 ) coefficients of the polynomial, 
|                  n-k
|         i( x ) x     mod g( x )
|
|     packed into a syndrome_t integer.  The least significant
|     bit is the constant term of the polynomial.
|
| EXCEPTIONS
|
| SIDE EFFECTS
|
| METHOD
|
| BUGS
|
| AUTHOR
|  
|     Sean E. O'Connor           2 February 2000
|
+============================================================================*/

syndrome_t ShiftRegister::shiftRegContents( void )
{
    // in_mask points to the least significant bit in contents.
    // out_mask points to the most significant bit in the output.
    syndrome_t in_mask = 1 ;
    syndrome_t out_mask = (syndrome_t) 1 <<
                             (8 * sizeof( syndrome_t ) - 1) ;
    syndrome_t reversed = 0 ;

    // Reverse the bit order. 
    for (int i = 0 ;  i < 8 * sizeof( syndrome_t ) ;   ++i)
    {
        if (in_mask & contents_)
            reversed |= out_mask ;

        out_mask >>= 1 ;
        in_mask <<= 1 ;
    }

    return( reversed ) ;

} // --------------------------< end shiftInByte >----------------------------


void ShiftRegister::clear( syndrome_t presetValue )
{
    contents_ = presetValue ;
}

// Get the degree of the generator polynomial.
int ShiftRegister::getDegreeOfGeneratorPoly( void ) const
{
    return degreeGeneratorPoly_ ;
}