1 /*=============================================================================
  2 |
  3 | NAME
  4 |
  5 |      shiftRegister.h
  6 |
  7 | DESCRIPTION
  8 |
  9 |     Class definition for a binary linear feedback shift register.
 10 |
 11 | AUTHOR
 12 |
 13 |      Sean O'Connor
 14 |    
 15 | LEGAL
 16 |
 17 |     CRCDemo Version 2.1 - A Program for generating and checking CRC codes.
 18 |     Copyright (C) 1999-2019 by Sean Erik O'Connor.  All Rights Reserved.
 19 |
 20 |     This program is free software: you can redistribute it and/or modify
 21 |     it under the terms of the GNU General Public License as published by
 22 |     the Free Software Foundation, either version 3 of the License, or
 23 |     (at your option) any later version.
 24 |
 25 |     This program is distributed in the hope that it will be useful,
 26 |     but WITHOUT ANY WARRANTY; without even the implied warranty of
 27 |     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 28 |     GNU General Public License for more details.
 29 |
 30 |     You should have received a copy of the GNU General Public License
 31 |     along with this program.  If not, see <http://www.gnu.org/licenses/>.
 32 |     
 33 |     The author's address is artificer!AT!seanerikoconnor!DOT!freeservers!DOT!com
 34 |     with !DOT! replaced by . and the !AT! replaced by @
 35 |
 36 +============================================================================*/
 37 
 38 #ifndef __SHIFT_REGISTER_H__
 39 #define __SHIFT_REGISTER_H__
 40 
 41 #include "dataTypes.h"
 42 
 43 #include <string>
 44 using namespace std ;
 45 
 46 
 47 /*=============================================================================
 48 |
 49 | NAME
 50 |  
 51 |     ShiftRegister
 52 |
 53 | DESCRIPTION
 54 |  
 55 |     Simulation of a binary linear feedback shift register, used to 
 56 |     generate or check a CRC code.
 57 |
 58 | NOTES|
 59 |                                     n-k
 60 |     This circuit computes [ i( x ) x    ] mod g( x ) where
 61 |
 62 |                   n-k            n-k-1
 63 |         g( x ) = x     + g      x      + ... + g x  +  g
 64 |                           n-k-1                 1       0
 65 |
 66 |                       k-1
 67 |         i( x ) = a   x     + ... + a x  +  a
 68 |                   k-1               1       0
 69 |
 70 |     Polynomial coefficients are in the field GF( 2 ), i.e. 
 71 |     modulo 2 arithmetic.
 72 |
 73 |       +---------------------+-----------------------+--------------+
 74 |       |                     |                       |              |
 75 |       |                     v                       |              v
 76 |       |                 +-------+                +-----+        +-----+
 77 |       |                 | g     |                | g   |        | g   |
 78 |     +---+               |  n-k-1|                |  1  |        |  0  |
 79 |     | -1|               +-------+                +-----+        +-----+
 80 |     +---+                   |                       |              |
 81 |       ^        +--------+   |             +-----+   |  +------+    |
 82 |       |        |  (k)   |   v             |  (k)|   v  |  (k) |    |
 83 |       +<-------| a      |<--+--- ... -----| a   |<--+--| a    |<---+
 84 |       |        |  n-k-1 |                 |  1  |      |  0   |
 85 |       |        +--------+                 +-----+      +------+
 86 |       |
 87 |    { a   ... a  }
 88 |       k-1     0
 89 |
 90 |                                            (0)
 91 |     Shift register contents is initially  a        = ... = a = 0
 92 |                                            n-k-1            0
 93 |            
 94 |     The bits a  are shifted in at the left.
 95 |               i
 96 |
 97 |     After k shifts the shift register contents is
 98 |
 99 |                  n-k
100 |         i( x ) x     mod g( x ) = 
101 |
102 |              (k)   n-k-1          (k)        (k)
103 |             a     x      + ... + a    x  +  a
104 |              n-k-1                1          0
105 |
106 |     The shift register contents is encoded in reverse order from 
107 |     the above diagram:  The least significant bit in the contents
108 |     is the coefficient
109 |
110 |        (k)                    (k)
111 |      a      and the msb is  a     
112 |        n-k-1                  0
113 |
114 |     Advantages:
115 |         (1) We are independent of the computer hardware's word size.
116 |         (2) It is easier to compute feedback, which we can do by
117 |             accessing the least significant bit, also in a machine
118 |             independent way.
119 |
120 |     Disadvantages:
121 |         We must reverse the bits when we print out the result.
122 |
123 |     We store the coefficients of g( x ) in a packed binary format. 
124 |     For example, if g( x ) = x ^ 16  +  x ^ 15  +  x ^ 2  +  1
125 |     we represent g( x ) as A001 (hexadecimal).  This is the scheme:
126 |
127 |     Coefficients:           1 1000 0000 0000 0101
128 |     x ^ 16 term dropped:    1000 0000 0000 0101
129 |     Reversed:               1010 0000 0000 0001
130 |     Hexadecimal:              A    0    0    1
131 |
132 |  Example
133 |
134 |                             16    15    2             16
135 |         CRC-16 is g( x ) = x  +  x  +  x  +  1,  n = 2  - 1, n - k = 16.
136 |
137 |                       8
138 |         Let i( x ) = x  +  x.   Coefficients of i are 
139 |         0001 0000 0010 [binary] = 0102 [hex] = ^A ^B [ascii]
140 |
141 |                        n-k
142 |         Then [ i( x ) x   ] mod g( x ) = 
143 |
144 |          24     17      16    15    2        10    9     3     2
145 |         x    + x   mod x  +  x  +  x + 1  = x  +  x  +  x  +  x
146 |
147 |         Coefficients are 0000 0110 0000 1100 [binary] = 060C [hex].
148 |
149 | References:
150 |
151 |     "Generating CRCs with software", Robert Grappel, EDN Magazine,
152 |      October 31, 1984, pg. 205.
153 |
154 |      Fairchild Advanced Schottky TTL Databook,
155 |      54/74F401 CRC Generator/Checker.
156 | BUGS
157 |
158 +============================================================================*/
159 
160 class ShiftRegister
161 {
162     public:
163         // Initialize shift register with a given polynomial g( x ).
164         ShiftRegister( const string & g ) ;
165 
166         // Destructor.
167        ~ShiftRegister( void ) ;
168 
169         // Shift one bit into the shift register.
170         void shiftInBit( int dataBit ) ;
171 
172         // Shift one 8-bit byte into the shift register
173         void shiftInByte( unsigned char dataByte ) ;
174 
175         // Return the contents of the shift register 
176         // (coefficients of the polynomial in binary format).
177         syndrome_t shiftRegContents( void ) ;
178 
179         // Clear the shift register.
180         void clear( syndrome_t presetValue = 0L ) ;
181 
182         // Get the degree of the generator polynomial.
183         int getDegreeOfGeneratorPoly( void ) const ;
184 
185     private:
186         // Shift register contents, packed binary coefficients of
187         // the polynomial
188         syndrome_t
189             contents_ ;
190 
191         // Generator polynomial in bit-packed format
192         // and its degree.
193         int degreeGeneratorPoly_ ;
194 
195         syndrome_t
196             generatorPoly_ ;
197 
198         // Disallow default copy constructor.
199         ShiftRegister( const ShiftRegister & shiftRegister ) ;
200 
201         // Disallow default assignment operator.
202         ShiftRegister & operator=( const ShiftRegister & shiftRegister ) ;
203 } ;
204 
205 #endif //__SHIFT_REGISTER_H__