/*=============================================================================
|
| NAME
|
|      shiftRegister.h
|
| DESCRIPTION
|
|     Class definition for a binary linear feedback shift register.
|
| AUTHOR
|
|      Sean O'Connor
|    
| LEGAL
|
|     CRCDemo Version 2.1 - A Program for generating and checking CRC codes.
|     Copyright (C) 1999-2008 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;  version 2
|     of the License.
|     
|     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, write to the Free Software
|     Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
|     
|     The author's address is artifex@seanerikoconnor.freeservers.com
|
+============================================================================*/

#ifndef __SHIFT_REGISTER_H__
#define __SHIFT_REGISTER_H__


/*=============================================================================
|
| NAME
|  
|     ShiftRegister
|
| DESCRIPTION
|  
|     Simulation of a binary linear feedback shift register, used to 
|     generate or check a CRC code.
|
| NOTES|
|                                     n-k
|     This circuit computes [ i( x ) x    ] mod g( x ) where
|
|                   n-k            n-k-1
|         g( x ) = x     + g      x      + ... + g x  +  g
|                           n-k-1                 1       0
|
|                       k-1
|         i( x ) = a   x     + ... + a x  +  a
|                   k-1               1       0
|
|     Polynomial coefficients are in the field GF( 2 ), i.e. 
|     modulo 2 arithmetic.
|
|       +---------------------+-----------------------+--------------+
|       |                     |                       |              |
|       |                     v                       |              v
|       |                 +-------+                +-----+        +-----+
|       |                 | g     |                | g   |        | g   |
|     +---+               |  n-k-1|                |  1  |        |  0  |
|     | -1|               +-------+                +-----+        +-----+
|     +---+                   |                       |              |
|       ^        +--------+   |             +-----+   |  +------+    |
|       |        |  (k)   |   v             |  (k)|   v  |  (k) |    |
|       +<-------| a      |<--+--- ... -----| a   |<--+--| a    |<---+
|       |        |  n-k-1 |                 |  1  |      |  0   |
|       |        +--------+                 +-----+      +------+
|       |
|    { a   ... a  }
|       k-1     0
|
|                                            (0)
|     Shift register contents is initially  a        = ... = a = 0
|                                            n-k-1            0
|            
|     The bits a  are shifted in at the left.
|               i
|
|     After k shifts the shift register contents is
|
|                  n-k
|         i( x ) x     mod g( x ) = 
|
|              (k)   n-k-1          (k)        (k)
|             a     x      + ... + a    x  +  a
|              n-k-1                1          0
|
|     The shift register contents is encoded in reverse order from 
|     the above diagram:  The least significant bit in the contents
|     is the coefficient
|
|        (k)                    (k)
|      a      and the msb is  a     
|        n-k-1                  0
|
|     Advantages:
|         (1) We are independent of the computer hardware's word size.
|         (2) It is easier to compute feedback, which we can do by
|             accessing the least significant bit, also in a machine
|             independent way.
|
|     Disadvantages:
|         We must reverse the bits when we print out the result.
|
|     We store the coefficients of g( x ) in a packed binary format. 
|     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
|     x ^ 16 term dropped:    1000 0000 0000 0101
|     Reversed:               1010 0000 0000 0001
|     Hexadecimal:              A    0    0    1
|
|  Example
|
|                             16    15    2             16
|         CRC-16 is g( x ) = x  +  x  +  x  +  1,  n = 2  - 1, n - k = 16.
|
|                       8
|         Let i( x ) = x  +  x.   Coefficients of i are 
|         0001 0000 0010 [binary] = 0102 [hex] = ^A ^B [ascii]
|
|                        n-k
|         Then [ i( x ) x   ] mod g( x ) = 
|
|          24     17      16    15    2        10    9     3     2
|         x    + x   mod x  +  x  +  x + 1  = x  +  x  +  x  +  x
|
|         Coefficients are 0000 0110 0000 1100 [binary] = 060C [hex].
|
| References:
|
|     "Generating CRCs with software", Robert Grappel, EDN Magazine,
|      October 31, 1984, pg. 205.
|
|      Fairchild Advanced Schottky TTL Databook,
|      54/74F401 CRC Generator/Checker.
| BUGS
|
+============================================================================*/

class ShiftRegister
{
    public:
		// Initialize shift register with a given polynomial g( x ).
        ShiftRegister( char * g ) ;  

		// Destructor.
       ~ShiftRegister( void ) ;
	   
	    // Shift one bit into the shift register.
        void shiftInBit( int dataBit ) ;

		// Shift one 8-bit byte into the shift register
        void shiftInByte( unsigned char dataByte ) ;

		// Return the contents of the shift register 
		// (coefficients of the polynomial in binary format).
        unsigned long shiftRegContents( void ) ;

		// Clear the shift register.
		void clear( unsigned long presetValue = 0L ) ;

		// Get the degree of the generator polynomial.
		int getDegreeOfGeneratorPoly( void ) const ;

    private:
		// Shift register contents, packed binary coefficients of
		// the polynomial
        unsigned long int
            contents_ ;

		// Generator polynomial in bit-packed format
		// and its degree.
		int degreeGeneratorPoly_ ;

        unsigned long int
            generatorPoly_ ;

		// Disallow default copy constructor.
		ShiftRegister( const ShiftRegister & shiftRegister ) ;

		// Disallow default assignment operator.
		ShiftRegister & operator=( const ShiftRegister & shiftRegister ) ;
} ;

#endif //__SHIFT_REGISTER_H__