1 /*=============================================================================
  2 |
  3 | NAME
  4 |  
  5 |      shiftRegister.cpp
  6 |
  7 | DESCRIPTION
  8 |  
  9 |     Binary linear feedback shift register class implementation.
 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 #include <string>
 39 using namespace std ;
 40 
 41 #include "dataTypes.h"
 42 #include "shiftRegister.h"      //  class Shift_register()
 43 
 44 
 45 
 46 /*=============================================================================
 47 |
 48 | NAME
 49 |  
 50 |     ShiftRegister
 51 |
 52 | DESCRIPTION
 53 |  
 54 |     Contructor for ShiftRegister class.  Initializes shift register contents
 55 |     to zero, and sets up the given generator polynomial.
 56 |
 57 | PARAMETERS
 58 |
 59 |     generatorPoly   (Input)  Generator polynomial (yields shift register feedback
 60 |                              connections).  Input in the form of a string. e.g.       
 61 |                              ShiftRegister sr( "x ^ 16 + x ^ 15 + x ^ 2 + 1" ) ;
 62 | RETURNS
 63 |
 64 | EXCEPTIONS
 65 |
 66 |    If there is an error, the degree of the generator polynomial
 67 |    is zero.
 68 |
 69 | SIDE EFFECTS
 70 |
 71 | METHOD
 72 |
 73 |    Read the polynomial string backwards, from lowest to highest degree
 74 |    coefficients.  Handle the constant term and x term as special cases.
 75 |    Pack the coefficients into the generator polynomial in reverse bit order,
 76 |    dropping the highest degree term.
 77 |
 78 |    For example, if g( x ) = x ^ 16  +  x ^ 15  +  x ^ 2  +  1
 79 |    we represent g( x ) as A001 (hexadecimal).  This is the scheme:
 80 |
 81 |    Coefficients:           1 1000 0000 0000 0101
 82 |    Reversed:               1010 0000 0000 0001 1
 83 |    x ^ 16 term dropped:    1010 0000 0000 0001
 84 |    Hexadecimal:              A    0    0    1
 85 |    
 86 |    Another example is CRC-32Q which has generator polynomial,
 87 |    g( x ) = x^32+x^31+x^24+x^22+x^16+x^14+x^8+x^7+x^5+x^3+x+1
 88 |   
 89 |    Coefficients:           1 1000 0001 0100 0001 0100 0001 1010 1011
 90 |    Reversed:               1101 0101 1000 0010 1000 0010 1000 0001 1
 91 |    x ^ 16 term dropped:    1101 0101 1000 0010 1000 0010 1000 0001
 92 |    Hexadecimal:              D    5    8    2    8    2    8    1
 93 |
 94 | BUGS
 95 |
 96 |    Assumes the polynomial has a constant term.
 97 |    For 32 bit CRC, the leading bit in the generator
 98 |    polynomial is trashed to zero.
 99 |
100 | AUTHOR
101 |  
102 |     Sean E. O'Connor           2 February 2000
103 |
104 +============================================================================*/
105 
106 ShiftRegister::ShiftRegister( const string & g )
107               : contents_( 0 )            // Initial shift register contents is zero.
108               , generatorPoly_( 0 )       // Polynomial is also initially zero.
109               , degreeGeneratorPoly_( 0 ) // Zero degree, i.e. constant.  
110 {
111     int i ;            //  Index of current character in polynomial string.
112     int powerOfX = 0 ;
113     int lastPowerOfX = 0 ;
114 
115     //  The polynomial string must have at least one character in it.
116     if (g.empty())
117         return ;
118 
119     // Point to the last character in the string.
120     i = g.length() - 1 ;
121 
122     //  Skip trailing blanks at the end of the string.
123     while (g[ i ] == ' ')
124         --i ;
125 
126     //  Read the polynomial's constant term, if any,
127     //  and add it as a 1 bit to the end of the buffer.
128     if (g[ i ] == '1')
129     {
130         generatorPoly_ |= 1 ;
131         --i ;
132     }
133     else              // No constant term --- error.
134         return ;
135 
136     //  Parse the remaining x ^ n terms, assuming there is at 
137     //  least one of them.
138 
139     while (i > 0)
140     {
141         while (g[ i ] == ' ')     // Skip any blanks.
142             --i ;
143 
144         if (g[ i ] == '+')        // Eat the '+'.
145             --i ;
146         else                      // No plus means bad syntax.
147             return ;
148 
149         while (g[ i ] == ' ')     // Skip any blanks.
150             --i ;
151 
152         // Parse the "x" term, if any, shift left, and add a 
153         // 1 bit to the end of the buffer.
154         if (g[ i ] == 'X' || g[ i ] == 'x')
155         {
156             powerOfX = 1 ;
157             --i ;
158         }
159         else  //  Parse the exponent "n" in the term "x ^ n".
160         {
161             int powerOf10 = 1 ;
162 
163             // Read digits from back to front.
164             for (powerOfX = 0 ;
165                  i > 0 && ('0' <= g[ i ] && g[ i ] <= '9') ;
166                  --i, powerOf10 *= 10)
167             {
168                 powerOfX += powerOf10 * (g[ i ] - (int)'0') ;
169             }
170         }
171 
172         while (g[ i ] == ' ')   // Skip blanks yet again.
173             --i ;
174 
175         //  Parse the "x ^" part of the term "x ^ n".
176         //  If we just parsed "x", we can skip this part.
177         if (powerOfX > 1)
178         {
179              // Parse the exponentiation '^' symbol.
180              if (g[ i ] == '^')
181                 --i ;
182              else
183                 return ;
184 
185              while (g[ i ] == ' ')    // Skip blanks.
186                  --i ;
187 
188              // Parse the "x" symbol.
189             if (g[ i ] == 'X' || g[ i ] == 'x')
190                 --i ;
191             else
192                 return ;
193 
194         } // end parse x ^ n.
195 
196 
197         // Check that powers of x are increasing.
198         if (powerOfX <= lastPowerOfX)
199             return ;
200 
201 
202         // Shift the coefficient "x ^ n" into place within 
203         // the generator polynomial, in bit reversed order.
204         // If we get the term x^N, where N = number of bits
205         // in the generatorPoly buffer, which is the highest
206         // possible term, shift by one less, since we'll
207         // chop it off below anyway.
208         int shiftLeftAmount = powerOfX - lastPowerOfX ;
209 
210         if (powerOfX == (8 * sizeof( generatorPoly_ )))
211             --shiftLeftAmount ;
212 
213         for (int j = 0 ;  j < shiftLeftAmount ;  ++j )
214            generatorPoly_ <<= 1 ;
215 
216         generatorPoly_ |= 1 ;
217 
218         lastPowerOfX = powerOfX ;
219 
220     } // end while i > 0
221 
222     //  Chop off the leading power of x, unless we've already
223     //  handled the x^N case above.
224     if (powerOfX != (8 * sizeof( generatorPoly_ )))
225         generatorPoly_ >>= 1 ;
226 
227     //  Record the generator polynomial degree.
228     degreeGeneratorPoly_ = lastPowerOfX ;
229 
230 } // --------------------------< end ShiftRegister >----------------------------
231 
232 
233 
234 /*=============================================================================
235 |
236 | NAME
237 |  
238 |     shiftInBit
239 |
240 | DESCRIPTION
241 |  
242 |     Shift one bit into the shift register.
243 |
244 | PARAMETERS
245 |
246 |    dataBit (Input)  Bit to shift into the shift register.  Must be 1 or 0 only.
247 |
248 | RETURNS
249 |
250 | EXCEPTIONS
251 |
252 | SIDE EFFECTS
253 |
254 | METHOD
255 |
256 | BUGS
257 |
258 | AUTHOR
259 |  
260 |     Sean E. O'Connor           2 February 2000
261 |
262 +============================================================================*/
263 
264 void ShiftRegister::shiftInBit( int dataBit )
265 {
266     syndrome_t feedback = 0 ;
267 
268     // To compute the feedback, add incoming data bit and leading bit of 
269     // shift register modulo 2.  This is an XOR operation in computer talk.
270     // Recall that we've reversed the order of the shift register circuit.
271     if (dataBit ^ (contents_ & 1))
272         feedback = generatorPoly_ ;
273     else
274         feedback = 0 ;
275 
276     // Shift.
277     contents_ >>= 1 ;
278 
279     // Now were ready to add in the generator polynomial coefficients modulo 2
280     // (or XOR if you prefer).
281     contents_ ^= feedback ;
282 
283 } // --------------------------< end shiftInBit >----------------------------
284 
285 
286 
287 ShiftRegister::~ShiftRegister( void )
288 {
289 
290 }
291 
292 
293 /*=============================================================================
294 |
295 | NAME
296 |  
297 |     shiftInByte
298 |
299 | DESCRIPTION
300 |  
301 |     Shift one byte into the shift register.
302 |
303 | PARAMETERS
304 |
305 |    dataByte (Input)  Byte to shift into the shift register.
306 |
307 | RETURNS
308 |
309 | EXCEPTIONS
310 |
311 | SIDE EFFECTS
312 |
313 | METHOD
314 |
315 | BUGS
316 |
317 | AUTHOR
318 |  
319 |     Sean E. O'Connor           2 February 2000
320 |
321 +============================================================================*/
322 
323 void ShiftRegister::shiftInByte( unsigned char dataByte )
324 {
325     int             i = 0 ;
326     unsigned int mask = 0x80 ;
327 
328     // Shift in the 8 bits in the byte in left to right order.
329     for (i = 0, mask = 0x80 ;  i < 8 ;  ++i, mask >>= 1)
330         shiftInBit( ((mask & (unsigned int) dataByte) == 0 ? 0 : 1)  ) ;
331 
332 } // --------------------------< end shiftInByte >----------------------------
333 
334 
335 
336 /*=============================================================================
337 |
338 | NAME
339 |  
340 |     shiftRegContents
341 |
342 | DESCRIPTION
343 |  
344 |     Return the contents of the shift register.
345 |
346 | RETURNS
347 |
348 |     The GF( 2 ) coefficients of the polynomial, 
349 |                  n-k
350 |         i( x ) x     mod g( x )
351 |
352 |     packed into a syndrome_t integer.  The least significant
353 |     bit is the constant term of the polynomial.
354 |
355 | EXCEPTIONS
356 |
357 | SIDE EFFECTS
358 |
359 | METHOD
360 |
361 | BUGS
362 |
363 | AUTHOR
364 |  
365 |     Sean E. O'Connor           2 February 2000
366 |
367 +============================================================================*/
368 
369 syndrome_t ShiftRegister::shiftRegContents( void )
370 {
371     // in_mask points to the least significant bit in contents.
372     // out_mask points to the most significant bit in the output.
373     syndrome_t in_mask = 1 ;
374     syndrome_t out_mask = (syndrome_t) 1 <<
375                              (8 * sizeof( syndrome_t ) - 1) ;
376     syndrome_t reversed = 0 ;
377 
378     // Reverse the bit order. 
379     for (int i = 0 ;  i < 8 * sizeof( syndrome_t ) ;   ++i)
380     {
381         if (in_mask & contents_)
382             reversed |= out_mask ;
383 
384         out_mask >>= 1 ;
385         in_mask <<= 1 ;
386     }
387 
388     return( reversed ) ;
389 
390 } // --------------------------< end shiftInByte >----------------------------
391 
392 
393 void ShiftRegister::clear( syndrome_t presetValue )
394 {
395     contents_ = presetValue ;
396 }
397 
398 // Get the degree of the generator polynomial.
399 int ShiftRegister::getDegreeOfGeneratorPoly( void ) const
400 {
401     return degreeGeneratorPoly_ ;
402 }