/*============================================================================= | | 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-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 | +============================================================================*/ #include // 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_ ; }