/*=============================================================================
|
| 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-2009 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.h>             // strlen()
#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( char * 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 == NULL || (i = strlen( g )) == 0)
        return ;

	// Point to the last character in the string.
    --i ; 

	//  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 )
{
    unsigned long int 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 an unsigned long 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
|
+============================================================================*/

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

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

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

    return( reversed ) ;

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


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

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