// CRC examples -- Chapter 9

// Copyright 2024 Philip Koopman
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//    http://www.apache.org/licenses/LICENSE-2.0
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#include "chapter9_examples.h"
const uint32_t bitsPerByte = 8;

// Private declarations that are forward references in this file       
static uint16_t crcLookup16[65536];
static uint32_t crcLookupTableR[256];
static uint16_t crcLookupTableR32sub8[256];
static uint16_t crcLookupTableR64sub8[256];
static uint32_t crcLookupTableL[256];

static void crcLookupInitR16(uint16_t modulus);
static uint32_t crcLookupInitR(uint32_t modulus);
static uint32_t crcLookupInitR32sub8(uint32_t modulus);
static uint64_t crcLookupInitR64sub8(uint64_t modulus);
static uint32_t crcLookupInitL(uint32_t modulus, uint32_t bits);

// ---------------------- 
// Example from section 9.8.2 
// 16-bit CRC left shift with adjustment
//    Check value must be zero for initial computation
//    Returned value is zero for validation
// cw:      code word in 16-bit blocks
// cwSize:  number of 16-bit code word blocks to process
// initialSeed: sum initialization value
//                    -- this is a prefix to code word
// finalXOR: value XORed to final result
     
uint16_t CRC16_LeftA(uint16_t cw16[], uint32_t cwSize,
       uint32_t initialSeed, uint32_t finalXOR)
{
  const uint16_t modulus16L = 0x3D65; // Implicit topbit
  uint32_t bits = 16;             // 16-bit CRC
  uint32_t bottomBitMask = 1;     // Lowest bit position
  uint16_t remainder = initialSeed ; // shift register

 // Loop across seed value and then data word
 for(uint32_t block=0; block<cwSize; block++)     
 { 
  // Get the next block
  uint16_t nextBits = cw16[block]; 
  
  // Loop across bits in the block
  for(uint32_t bitPosn=0; bitPosn<bits; bitPosn++)     
  { 
   // Conditional XOR based on top bit of remainder
   const uint16_t topBit = 0x8000; // Topmost of 16 bits
  
   if( (remainder & topBit) == 0)
   { remainder <<= 1; 
   } else
   { remainder <<= 1;  
     remainder ^= modulus16L;  // Feedback activated
   }
   
   // XOR in the next data word bit from top of nextBits
   //  Result put into bottom bit of working remainder
   remainder ^= (nextBits >>(bits-1)) & bottomBitMask;
   nextBits <<= 1; // progress to next input bit
  } // End of loop across bits within block      
 }  // End of loop across blocks within code word

 // Check value adjustment is implicit in algorithm

 return(remainder^finalXOR);
}


// ----------------------
// Example from section 9.8.3 
// 16-bit CRC left shift with adjustment
//    Check value must be zero for initial computation
//    Returned value is zero for validation
// cw:      code word in 16-bit blocks
// cwSize:  number of 16-bit blocks to process
// initialSeed: sum initialization value 
// finalXOR: value XORed to final result

uint16_t CRC16_LeftB(uint16_t cw16[], uint32_t cwSize,
       uint32_t initialSeed, uint32_t finalXOR)
{
  const uint16_t modulus16L = 0x3D65;
  uint32_t bits = 16;     // 16-bit CRC
  uint16_t remainder = initialSeed; 
 
 // Loop across seed value and then data word
 for(uint32_t block=0; block < cwSize; block++)     
 { 
  // Loop across bits in the block
  for(uint32_t bitPosn=0; bitPosn < bits; bitPosn++)     
  { 
   // Conditional XOR based on top bit of remainder
   const uint16_t topBit = 0x8000; // Topmost bit
   if( (remainder & topBit) == 0)
   { remainder <<= 1; 
   } else
   { remainder <<= 1;  
     remainder ^= modulus16L;  // Feedback activated
   }
  } // End of loop across bits within block      

  // XOR all 16 bits of the next block at once
  remainder ^= cw16[block];

 }  // End of loop across blocks within code word
 
 // Check value adjustment is implicit in algorithm
 return(remainder^finalXOR);
}


// ----------------------
// Example from section 9.8.4 
// 16-bit CRC left shift with speed-up
//    Practical implementation with XORed initial seed
// cw:      code word in 16-bit blocks
// cwSize:  number of 16-bit blocks to process
// initialSeed: initial seed XORed with first block
// finalXOR: value XORed to final result

uint16_t CRC16_LeftC(uint16_t cw16[], uint32_t cwSize,
       uint32_t initialSeed, uint32_t finalXOR)
{
  const uint16_t modulus16L = 0x3D65;
  uint32_t bits = 16;     // 16-bit CRC
  uint16_t remainder = initialSeed; 
 
 // Loop across blocks in data word but not check value
 for(uint32_t block=0; block < (cwSize-1); block++)     
 { 
  // XOR all 16 bits of the next block at once
  remainder ^= cw16[block];
  
  // Loop across bits in the block
  for(uint32_t bitPosn=0; bitPosn<bits; bitPosn++)     
  { 
   // Conditional XOR based on top bit of remainder
   const uint16_t topBit = 0x8000; // Topmost bit
   if( (remainder & topBit) == 0)
   { remainder <<= 1; 
   } else
   { remainder <<= 1;  
     remainder ^= modulus16L;  // Feedback activated
   }
  } // End of loop across bits within block      
 }  // End of loop across blocks within code word

 // Optional check value adjustment
 remainder ^= cw16[cwSize-1];

 return(remainder^finalXOR);
}


// ----------------------
// Example from section 9.8.5 
// 16-bit CRC right shift with adjustment
// cw:      code word in 16-bit blocks
// cwSize:  number of 16-bit blocks to process
// initialSeed: initial seed XORed with first block
// finalXOR: value XORed to final result
// modulus16R: implicit +1 format

uint16_t CRC16_RightD(uint16_t cw16[], uint32_t cwSize,
       uint32_t initialSeed, uint32_t finalXOR)
{ 
  const uint16_t modulus16R = 0xA6BC;
  uint16_t remainder = initialSeed; 

 // Loop across blocks in data word but not check value
 for(uint32_t block=0; block < (cwSize-1); block++)     
 { 
  remainder ^= cw16[block];

  // Loop across bits in the block
  for(uint32_t bitPosn=0; bitPosn<16; bitPosn++)     
  { 
   // Conditional XOR based on bottom bit of remainder
   const uint16_t bottomBitMask = 1; // Bottom-most bit
   if( (remainder & bottomBitMask) == 0)
   { remainder >>= 1; 
   } else
   { remainder >>= 1;  
     remainder ^= modulus16R;  // Feedback activated
   }
  } // End of loop across bits within block      
 }  // End of loop across blocks within code word

 // Optional check value adjustment
 remainder ^= cw16[cwSize-1];
 
 return(remainder^finalXOR);
}


// ----------------------
// Example from section 9.8.6 
// 16-bit CRC right shift with 64K element lookup table
// cw:      code word in 16-bit blocks
// cwSize:  number of 16-bit blocks to process
// initialSeed: initial seed XORed with first block
// finalXOR: value XORed to final result
// modulus16R: implicit +1 format
  
uint16_t CRC16_RightE(uint16_t cw16[], uint32_t cwSize,
       uint32_t initialSeed, uint32_t finalXOR)
{ 
  const uint16_t modulus16R = 0xA6BC;
  crcLookupInitR16(modulus16R);  // Init lookup table
  
  uint16_t remainder = initialSeed; 
  
  // Loop across blocks in data word but not check value
  for(uint32_t block=0; block < (cwSize-1); block++)     
  { 
    // Get next block from data word
    uint16_t nextBits = cw16[block]; 
    remainder ^= nextBits;

    // Use lookup table to perform 16 shift-XOR cycles
    remainder = crcLookup16[remainder];
  }  // End of loop across blocks within code word

  // Optional check value adjustment
  remainder ^= cw16[cwSize-1];
  
  return(remainder^finalXOR);
}


// ----------------------
// Example from section 9.8.7
// Generic CRC right shift unadjusted
//    optimized byte-by-byte for 1 .. 32 bit CRCs
// dw:      byte-organized data word
// dwSize:  number of 8-bit blocks to process
// modulus: implicit +1 format
// initialSeed: sum initialization value
// finalXOR: value XORed to final result

uint32_t CRC_RGeneric(uint8_t dw[], uint32_t dwSize, 
                 uint32_t modulus, uint32_t initialSeed,
                 uint32_t finalXOR)
{
  uint32_t remainder = initialSeed; 

  // Loop across bytes in data word
  for(uint32_t block=0; block < dwSize; block++)     
  { 
    // Get next block from the data word
    remainder ^= (uint32_t)dw[block]; 
 
    // Loop across bits in the block
    for(uint32_t bitPosn=0; bitPosn<bitsPerByte; 
                                            bitPosn++)     
    { 
      // Conditional XOR based on bottom bit
      const uint32_t bottomBitMask = 1; // Bottom bit
      if( (remainder & bottomBitMask) == 0)
      { remainder >>= 1; 
      } else
      { remainder >>= 1;  
        remainder ^= modulus;  // Feedback activated
      }
    } // End of loop across bits within block      
 }  // End of loop across blocks within data word

 return(remainder^finalXOR);
}


// ----------------------
// Example from section 9.8.8
// Generic CRC right shift unadjusted
//   256 element lookup table for 1 .. 32 bit CRCs
// dw:      byte-organized data word
// dwSize:  number of 8-bit blocks to process
// initialSeed: initial seed XORed with first block
// finalXOR: value XORed to final result
// modulus: implicit +1 format

uint32_t CRC_RGenericT(uint8_t dw[], uint32_t dwSize, 
                uint32_t modulus, uint32_t initialSeed, 
                uint32_t finalXOR)
{
  crcLookupInitR(modulus); // Init lookup table
  uint32_t remainder = initialSeed; // shift register
 
  // Loop across bytes in data word
  for(uint32_t block=0; block< dwSize; block++)     
  { 
    // Get next block from the data word
    remainder ^= (uint32_t)dw[block]; 
    
    // Process an 8-bit shift-and-conditional-XOR 
    const uint32_t byteMask = 0xFF;
    uint32_t bottomByte = remainder & byteMask;

    remainder >>= bitsPerByte;
    remainder ^= crcLookupTableR[bottomByte];
  }  // End of loop across blocks within code word

  return(remainder^finalXOR);
}


// ----------------------
// Example from section 9.8.9
// Generic CRC left shift unadjusted
//    bit at a time -- for 8 .. 32 bit CRCs
// dw:      byte-organized data word
// dwSize:  number of 8-bit blocks to process
// modulus: explicit high bit format
// initialSeed: initial seed XORed with first block
// finalXOR: value XORed to final result
// bits:    number of bits (1..32)

uint32_t CRC_LGeneric(uint8_t dw[], uint32_t dwSize, 
               uint32_t modulus, uint32_t initialSeed, 
               uint32_t finalXOR, uint32_t bits)
{
 assert((bits >= 8) && (bits <= 32));
 uint32_t topRemainderMask = 1 << (bits-1); 

 uint32_t remainder = initialSeed; 

 // Loop across bytes in data word + check value
 for(uint32_t block=0; block < dwSize; block++)     
 { 
  // XOR next data word block into top active bits
  remainder ^= (dw[block] << (bits-8)); 
  
  // Loop across bits in the block
  for(uint32_t bitPosn=0; bitPosn<bitsPerByte;bitPosn++)     
  { 
   // Conditional XOR based on top bit of remainder
   if( (remainder & topRemainderMask) == 0)
   { remainder <<= 1; 
   } else
   { remainder <<= 1;  
     remainder ^= modulus;  // Feedback activated
   }
  } // End of loop across bits within block      
 }  // End of loop across blocks within code word
 
 return(remainder^finalXOR);
}


// ----------------------
// Example from section 9.8.10
// Generic CRC left shift using table lookup  
//    unadjusted -- for 8 .. 32 bit CRCs
// dw:      byte-organized data word
// dwSize:  number of 8-bit blocks to process
// modulus: explicit high bit format
// initialSeed: initial seed XORed with first block
// finalXOR: value XORed to final result
// bits:    number of bits (8..32)

uint32_t CRC_LGenericT(uint8_t dw[], uint32_t dwSize, 
               uint32_t modulus, uint32_t initialSeed, 
               uint32_t finalXOR, uint32_t bits)
{
 crcLookupInitL(modulus, bits); // Init lookup table
 uint32_t remainder = initialSeed;

 // Loop across bytes in data word + check value
 for(uint32_t block=0; block < dwSize; block++)     
 { 
  uint32_t lookupIndex = 
                      remainder >> (bits-bitsPerByte);
  lookupIndex ^= dw[block]; 
  
  remainder <<= bitsPerByte;
  
  const uint32_t byteMask = 0xFF;
  remainder ^= crcLookupTableL[lookupIndex & byteMask];
 }  // End of loop across blocks within code word

 // Mask out extraneous high bits
 remainder &= ((1<<bits) - 1);
 
 return(remainder^finalXOR);
}


// ----------------------
// Example from section 9.8.11
// Generic CRC right shift unadjusted 
//         32sub8 with high 8 bit polynomial
// dw:      byte-organized data word
// dwSize:  number of 8-bit blocks to process
// modulus: implicit +1 format
// initialSeed: initial seed XORed with first block
// finalXOR: value XORed to final result

uint32_t CRC_RGenericT32sub8(uint8_t dw[],
               uint32_t dwSize, uint32_t modulus, 
               uint32_t initialSeed, uint32_t finalXOR)
{
  // Sub8 polynomial only has bits 24..31 set
  assert((modulus & 0x00FFFFFF) == 0);  

  crcLookupInitR32sub8(modulus); // Init lookup table
  uint32_t remainder = initialSeed;
 
  // Loop across bytes in data word
  for(uint32_t block=0; block< dwSize; block++)     
  { 
    const uint32_t byteMask = 0xFF;
    
    // Get next block from the data word
    remainder ^= (uint32_t)dw[block]; 
    
    // Process an 8-bit shift-and-conditional-XOR 
    uint32_t bottomByte = remainder & byteMask;
    remainder >>= bitsPerByte;
    
    // lookup table only holds top 16 bits of value
    remainder^=((uint32_t)
             (crcLookupTableR32sub8[bottomByte]) <<16);
  }  // End of loop across blocks within code word

  return(remainder^finalXOR);
}


/////////////////////////////////////////////
// Bonus content -- 64 bit CRC examples

// ----------------------
// Bonus 64-bit right-shift CRC
// Generic CRC right shift unadjusted
// dw:      byte-organized data word
// dwSize:  number of 8-bit blocks to process
// modulus: implicit +1 format
// initialSeed: initial seed XORed with first block
// finalXOR: value XORed to final result

uint64_t CRC_RGeneric64(uint8_t dw[], uint32_t dwSize, 
                 uint64_t modulus, uint64_t initialSeed,
                 uint64_t finalXOR)
{
  uint64_t remainder = initialSeed; 

  // Loop across bytes in data word
  for(uint32_t block=0; block < dwSize; block++)     
  { 
    // Get next block from the data word
    remainder ^= (uint64_t)dw[block]; 
 
    // Loop across bits in the block
    for(uint32_t bitPosn=0; bitPosn<bitsPerByte; 
                                            bitPosn++)     
    { 
      // Conditional XOR based on bottom bit
      const uint64_t bottomBitMask = 1; // Bottom bit
      if( (remainder & bottomBitMask) == 0)
      { remainder >>= 1; 
      } else
      { remainder >>= 1;  
        remainder ^= modulus;  // Feedback activated
      }
    } // End of loop across bits within block      
 }  // End of loop across blocks within data word

 return(remainder^finalXOR);
}

// ----------------------
// Bonus -- 64-bit sub8 lookup table right shift
// Generic CRC right shift unadjusted -- 64sub8 with high 8 bit polynomial
// dw:      byte-organized data word
// dwSize:  number of 8-bit blocks to process
// modulus: implicit +1 format
// initialSeed: initial seed XORed with first block
// finalXOR: value XORed to final result

uint64_t CRC_RGenericT64sub8(uint8_t dw[],
               uint32_t dwSize, uint64_t modulus, 
               uint64_t initialSeed, uint64_t finalXOR)
{
  // Sub8 polynomial 56..63 bits
  assert((modulus & 0x00FFFFFFFFFFFFFFUL) == 0);  

  crcLookupInitR64sub8(modulus); 
  uint64_t remainder = initialSeed;
 
  // Loop across bytes in data word
  for(uint32_t block=0; block< dwSize; block++)     
  { 
    const uint32_t byteMask = 0xFF;
    
    // Get next block from the data word
    remainder ^= (uint64_t)dw[block]; 
    
    // Process an 8-bit shift-and-conditional-XOR 
    uint32_t bottomByte = remainder & byteMask;
    remainder >>= bitsPerByte;
    
    // Lookup table only holds top 16 bits of value
    remainder ^=((uint64_t)
             (crcLookupTableR64sub8[bottomByte])) <<48;
  }  // End of loop across blocks within code word

  return(remainder^finalXOR);
}


////////////////////////////////////////////////////////
////////////////////////////////////////////////////////
// Lookup table support

// Cycle RIGHT a remainder value right by N clocks
// remainder: starting remainder value
//   Only bottom k bits set for a k-bit check value
// modulus: in implicit +1 format
// iterations: 8 for a 256-element lookup table
//            16 for a 64K-element lookup table
// Could be uint32_t if only 32-bit and smaller polynomials in use
static uint64_t CycleR(uint64_t remainder,
               uint64_t modulus, uint32_t iterations)
{
  for( uint32_t cycles = 0; cycles<iterations; cycles++)
  {
    // Conditional XOR based on bottom bit of remainder
    const uint64_t bottomBitMask = 1UL; // Lowest bit position
    if( (remainder & bottomBitMask) == 0)
    { remainder >>= 1; 
    } else
    { remainder >>= 1;  
      remainder ^= modulus;  // feedback activated
    }
  }
  return(remainder);
}


// ----------------------
// 16-bit CRC brute force lookup table
// Included for illustration purposes -- 
//     in most cases you would not want to use this

// Remember most recent initialized polynomial here
static uint16_t crcLookup16PolyR = 0;

// Initializes table (if required) for a modulus with right-shift CRC
//    Immediate return with no delay if already initialized
//    Best practice is to call initialize at start of every CRC computation
// modulus: 16-bit polynomial in implicit +1 notation

void crcLookupInitR16(uint16_t modulus)
{ const uint32_t bits = 16;  // number of bits in CRC
  const uint32_t topBit16 = 1 << (bits-1);
  assert(modulus & topBit16);  // top bit for 16-bit modulus is set
  
  // for each possible 16-bit value  
  if (crcLookup16PolyR != modulus)
  {   
    const uint32_t all16BitValues = 1 << bits;
    for( uint32_t wordVal = 0; wordVal < all16BitValues; wordVal++)
    { crcLookup16[wordVal] = CycleR(wordVal, modulus, bits);
    }
  }
  // Remember table has been initialized for this modulus
  crcLookup16PolyR = modulus;
}


// ----------------------
// 32-bit right-shift lookup table can be used for 8 - 32 bit CRCs.
// Lookup table can be "const" and compiled into ROM if modulus is fixed.

// Remember most recent initialized polynomial
static uint32_t crcLookupPolyR = 0xEDB88320; // pre-initialized table

// --------------- code to initialize CRC right-shift lookup table
static uint32_t crcLookupTableR[256] = { 
// modulus=0xEDB88320 implicit +1
     0x00000000,  0x77073096,  0xEE0E612C,  0x990951BA, 
     0x076DC419,  0x706AF48F,  0xE963A535,  0x9E6495A3, 
     0x0EDB8832,  0x79DCB8A4,  0xE0D5E91E,  0x97D2D988, 
     0x09B64C2B,  0x7EB17CBD,  0xE7B82D07,  0x90BF1D91, 
     0x1DB71064,  0x6AB020F2,  0xF3B97148,  0x84BE41DE, 
     0x1ADAD47D,  0x6DDDE4EB,  0xF4D4B551,  0x83D385C7, 
     0x136C9856,  0x646BA8C0,  0xFD62F97A,  0x8A65C9EC, 
     0x14015C4F,  0x63066CD9,  0xFA0F3D63,  0x8D080DF5, 
     0x3B6E20C8,  0x4C69105E,  0xD56041E4,  0xA2677172, 
     0x3C03E4D1,  0x4B04D447,  0xD20D85FD,  0xA50AB56B, 
     0x35B5A8FA,  0x42B2986C,  0xDBBBC9D6,  0xACBCF940, 
     0x32D86CE3,  0x45DF5C75,  0xDCD60DCF,  0xABD13D59, 
     0x26D930AC,  0x51DE003A,  0xC8D75180,  0xBFD06116, 
     0x21B4F4B5,  0x56B3C423,  0xCFBA9599,  0xB8BDA50F, 
     0x2802B89E,  0x5F058808,  0xC60CD9B2,  0xB10BE924, 
     0x2F6F7C87,  0x58684C11,  0xC1611DAB,  0xB6662D3D, 
     0x76DC4190,  0x01DB7106,  0x98D220BC,  0xEFD5102A, 
     0x71B18589,  0x06B6B51F,  0x9FBFE4A5,  0xE8B8D433, 
     0x7807C9A2,  0x0F00F934,  0x9609A88E,  0xE10E9818, 
     0x7F6A0DBB,  0x086D3D2D,  0x91646C97,  0xE6635C01, 
     0x6B6B51F4,  0x1C6C6162,  0x856530D8,  0xF262004E, 
     0x6C0695ED,  0x1B01A57B,  0x8208F4C1,  0xF50FC457, 
     0x65B0D9C6,  0x12B7E950,  0x8BBEB8EA,  0xFCB9887C, 
     0x62DD1DDF,  0x15DA2D49,  0x8CD37CF3,  0xFBD44C65, 
     0x4DB26158,  0x3AB551CE,  0xA3BC0074,  0xD4BB30E2, 
     0x4ADFA541,  0x3DD895D7,  0xA4D1C46D,  0xD3D6F4FB, 
     0x4369E96A,  0x346ED9FC,  0xAD678846,  0xDA60B8D0, 
     0x44042D73,  0x33031DE5,  0xAA0A4C5F,  0xDD0D7CC9, 
     0x5005713C,  0x270241AA,  0xBE0B1010,  0xC90C2086, 
     0x5768B525,  0x206F85B3,  0xB966D409,  0xCE61E49F, 
     0x5EDEF90E,  0x29D9C998,  0xB0D09822,  0xC7D7A8B4, 
     0x59B33D17,  0x2EB40D81,  0xB7BD5C3B,  0xC0BA6CAD, 
     0xEDB88320,  0x9ABFB3B6,  0x03B6E20C,  0x74B1D29A, 
     0xEAD54739,  0x9DD277AF,  0x04DB2615,  0x73DC1683, 
     0xE3630B12,  0x94643B84,  0x0D6D6A3E,  0x7A6A5AA8, 
     0xE40ECF0B,  0x9309FF9D,  0x0A00AE27,  0x7D079EB1, 
     0xF00F9344,  0x8708A3D2,  0x1E01F268,  0x6906C2FE, 
     0xF762575D,  0x806567CB,  0x196C3671,  0x6E6B06E7, 
     0xFED41B76,  0x89D32BE0,  0x10DA7A5A,  0x67DD4ACC, 
     0xF9B9DF6F,  0x8EBEEFF9,  0x17B7BE43,  0x60B08ED5, 
     0xD6D6A3E8,  0xA1D1937E,  0x38D8C2C4,  0x4FDFF252, 
     0xD1BB67F1,  0xA6BC5767,  0x3FB506DD,  0x48B2364B, 
     0xD80D2BDA,  0xAF0A1B4C,  0x36034AF6,  0x41047A60, 
     0xDF60EFC3,  0xA867DF55,  0x316E8EEF,  0x4669BE79, 
     0xCB61B38C,  0xBC66831A,  0x256FD2A0,  0x5268E236, 
     0xCC0C7795,  0xBB0B4703,  0x220216B9,  0x5505262F, 
     0xC5BA3BBE,  0xB2BD0B28,  0x2BB45A92,  0x5CB36A04, 
     0xC2D7FFA7,  0xB5D0CF31,  0x2CD99E8B,  0x5BDEAE1D, 
     0x9B64C2B0,  0xEC63F226,  0x756AA39C,  0x026D930A, 
     0x9C0906A9,  0xEB0E363F,  0x72076785,  0x05005713, 
     0x95BF4A82,  0xE2B87A14,  0x7BB12BAE,  0x0CB61B38, 
     0x92D28E9B,  0xE5D5BE0D,  0x7CDCEFB7,  0x0BDBDF21, 
     0x86D3D2D4,  0xF1D4E242,  0x68DDB3F8,  0x1FDA836E, 
     0x81BE16CD,  0xF6B9265B,  0x6FB077E1,  0x18B74777, 
     0x88085AE6,  0xFF0F6A70,  0x66063BCA,  0x11010B5C, 
     0x8F659EFF,  0xF862AE69,  0x616BFFD3,  0x166CCF45, 
     0xA00AE278,  0xD70DD2EE,  0x4E048354,  0x3903B3C2, 
     0xA7672661,  0xD06016F7,  0x4969474D,  0x3E6E77DB, 
     0xAED16A4A,  0xD9D65ADC,  0x40DF0B66,  0x37D83BF0, 
     0xA9BCAE53,  0xDEBB9EC5,  0x47B2CF7F,  0x30B5FFE9, 
     0xBDBDF21C,  0xCABAC28A,  0x53B39330,  0x24B4A3A6, 
     0xBAD03605,  0xCDD70693,  0x54DE5729,  0x23D967BF, 
     0xB3667A2E,  0xC4614AB8,  0x5D681B02,  0x2A6F2B94, 
     0xB40BBE37,  0xC30C8EA1,  0x5A05DF1B,  0x2D02EF8D
    };


// Initialize right-shift table (if required) for a modulus
//    Immediate return with no delay if already initialized
//    Best practice is to call initialize at start of every CRC computation
//    Returns modulus
// modulus: polynomial in implicit +1 notation; 8-32 bits
static uint32_t crcLookupInitR(uint32_t modulus)
{ 
  uint32_t top25Bits = 0xFFFFFF80;
  assert((modulus & top25Bits) != 0); // at least an 8-bit CRC

  // only update table if the previous modulus is different
  if(crcLookupPolyR != modulus)
  { 
    // for each possible bottom 8 bit value  
    const uint32_t bitValues8 = 256;  // number of 8-bit values
    
    for( uint32_t byteVal = 0; byteVal < bitValues8; byteVal++)
    { crcLookupTableR[byteVal] = CycleR(byteVal, modulus, bitsPerByte);
    }
    crcLookupPolyR = modulus;
  }
  return(modulus);
}

// ----------------------
// 32-bit left-shift lookup table can be used for 8 - 32 bit CRCs.

// Remember the LEFT lookup table polynomial to avoid recomputation
static uint32_t crcLookupPolyL = 0; // 0 means uinitialized table

// Cycle LEFT a remainder value right by N clocks with a given polynomial
// remainder: starting remainder value
//         Should only have top 8 bits set for 256-element table
// modulus: full polynomial or implict top bit
// iterations: 8 for a 256-element lookup table
static uint32_t CycleL(uint32_t remainder, uint32_t modulus, 
                       uint32_t iterations, uint32_t bits)
{
  uint32_t topBitMask = 1 << (bits-1); // feedback bit
  
  for( uint32_t cycles = 0 ; cycles < iterations ; cycles++)
  {
    // Conditional XOR based on top bit of remainder
    if( (remainder & topBitMask) == 0)
    { remainder <<= 1; 
    } else
    { remainder ^= topBitMask;
      remainder <<= 1;  
      remainder ^= modulus;  // Feedback activated
    }
  }
  return(remainder);
}

// Initialize left-shift tables (if required) for a modulus
//    Immediate return with no delay if already initialized
//    Best practice is to call initialize at start of every CRC computation
//    Returns modulus
// modulus: full polynomial or implict top bit
static uint32_t crcLookupInitL(uint32_t modulus, uint32_t bits)
{ 
  assert(bits >= 8); // At least an 8 bit CRC
  
  // Only update table if the previous modulus is different
  if (crcLookupPolyL != modulus)
  { 
    // For each possible top 8 bit value  
    const uint32_t bitValues8 = 256; 
    
    for( uint32_t byteVal = 0; byteVal < bitValues8; byteVal++)
    { 
      uint32_t remainder = byteVal << (bits-8);
      crcLookupTableL[byteVal] = CycleL(remainder, modulus, bitsPerByte, bits);
    }
    crcLookupPolyL = modulus;
  }
  return(modulus);
}

// Print table for pasting into source code for compile-time initialization
//    Does the initialization as well automatically
//    Returns modulus
uint32_t crcLookupPrintR(uint32_t modulus)
{
  printf("// --------------- code to initialize CRC right shift lookup table\n");
  printf("static uint32_t crcLookupTableR[256] = { // modulus=0x%X implicit +1\n    ", modulus);
  
  crcLookupInitR(modulus);

  for( uint32_t byteVal = 0; byteVal < 256; byteVal++)
  { printf(" 0x%08X", crcLookupTableR[byteVal]); 
    if ((byteVal != 0xFF)) { printf(", "); }
    if ((byteVal & 0x3) == 3) { printf("\n    "); }
  }
  printf("};\n");
  printf("\nstatic uint32_t crcLookupPolyR = 0x%08X;\n", modulus);
  printf("// ---------------\n");
  return(modulus);
}


// ----------------------
// Special table for right shift sub8 lookups

// Remember most recent initialized polynomial
static uint32_t crcLookupPolyR32sub8 = 0; // sub8 polynomial

// Initialize right-shift table (if required) for a modulus
//    Immediate return with no delay if already initialized
//    Best practice is to call initialize at start of every CRC computation
//    Returns modulus
// modulus: polynomial in implicit +1 notation; 8-32 bits
static uint32_t crcLookupInitR32sub8(uint32_t modulus)
{ 
  uint32_t top8Bits = 0xFF000000;
  uint32_t bottom16Bits = 0x0000FFFF;
  uint32_t bottom24Bits = 0x00FFFFFF;
  assert((modulus & top8Bits) != 0); // sub8 CRC with some top 8 bits set
  assert((modulus & bottom24Bits) == 0); // sub8 CRC with no bottom 24 bits set

  // only update table if the previous modulus is different
  if(crcLookupPolyR32sub8 != modulus)
  { 
    // for each possible bottom 8 bit value  
    const uint32_t bitValues8 = 256;  // number of 8-bit values
    
    for( uint32_t byteVal = 0; byteVal < bitValues8; byteVal++)
    { 
      uint32_t fullTableValue = CycleR(byteVal, modulus, bitsPerByte);
      assert((fullTableValue & bottom16Bits) == 0);  // only top 16 bits set
      crcLookupTableR32sub8[byteVal] = fullTableValue >> 16;  // save top 16 bits
    }
    crcLookupPolyR32sub8 = modulus;
  }
  return(modulus);
}

// ----------------------
// Special table for right shift sub8 lookups

// Remember most recent initialized polynomial
static uint64_t crcLookupPolyR64sub8 = 0; // sub8 polynomial

static uint64_t crcLookupInitR64sub8(uint64_t modulus)
{ 
  uint64_t top8Bits     = 0xFF00000000000000UL;
  uint64_t bottom48Bits = 0x0000FFFFFFFFFFFFUL;
  uint64_t bottom56Bits = 0x00FFFFFFFFFFFFFFUL;
  assert((modulus & top8Bits) != 0); // sub8 CRC with some top 8 bits set
  assert((modulus & bottom56Bits) == 0); // sub8 CRC with no bottom bits set

  // only update table if the previous modulus is different
  if(crcLookupPolyR64sub8 != modulus)
  { 
    // for each possible bottom 8 bit value  
    const uint32_t bitValues8 = 256;  // number of 8-bit values
    
    for( uint32_t byteVal = 0; byteVal < bitValues8; byteVal++)
    { 
      uint64_t fullTableValue = CycleR(byteVal, modulus, bitsPerByte);
      assert((fullTableValue & bottom48Bits) == 0);  // only top 16 bits set
      crcLookupTableR64sub8[byteVal] = fullTableValue >> 48;  // save top 16 bits
    }
    crcLookupPolyR64sub8 = modulus;
  }
  return(modulus);
}