Email: Password: Remember Me | Create Account (Free)

Back to Subject List

Old thread has been locked -- no new posts accepted in this thread
Michael Karas
08/04/07 08:14
Read: 6757 times
Beaverton Or

#142761 - Runtime Computed Table??
Responding to: John Myers's previous message
In the common scheme of today's microcontrollers with the program code contained in on-board FLASH and data stored into on-board RAM I would suggest that a run time computed CRC table is a bad trade off on the use of RAM versus FLASH. I would really recommend that you use a pre-computed table and directly embed it into your code space so that the you do not "waste" RAM which is the more scarce resource on almost all MCUs.

If you are interested I have used a scheme that uses a table lookup scheme for CRC computation that uses a very small look up table of some 32-bytes by doing table look-up on data nibbles (4-bits at a time) instead of using a byte at a time scheme. The performance gain over bit serial methods is still substantial and with the speed of many modern MCSs the method is very usable in cases where a huge table is not attractive. The typical CRC table for byte-at-a-time schemes eats up 512 bytes.

Here is C code for the nibble CRC algorithm:
// CRC table for implementing CRC16 with 0x1021 polynomial

__flash const unsigned int crc_table[16] =
     0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50A5, 0x60C6, 0x70E7, 
     0x8108, 0x9129, 0xA14A, 0xB16B, 0xC18C, 0xD1AD, 0xE1CE, 0xF1EF, 

// routine to calculate the CRC of a current value with a 
// new byte value. The new CRC result is returned.

unsigned int calc_crc(unsigned int crc, unsigned char data)
    crc = crc_table[((crc >> 12) ^ (data >> 4)) & 0x0F] ^ (crc << 4);
    crc = crc_table[((crc >> 12) ^ (data & 0x0F)) & 0x0F] ^ (crc << 4);

Michael Karas

List of 23 messages in thread
How to create a crc table?      John Myers      08/04/07 01:33      
   simple      Jan Waclawek      08/04/07 07:10      
      RE: simple      John Myers      08/04/07 14:34      
         I said it\'s simple      Jan Waclawek      08/04/07 16:33      
            Thank you      John Myers      08/04/07 17:27      
            Protocols      Andy Neil      08/06/07 06:48      
               examples      Jan Waclawek      08/06/07 07:05      
   Runtime Computed Table??      Michael Karas      08/04/07 08:14      
      RE: Runtime...?      John Myers      08/04/07 15:02      
      table is not necessary      Jan Waclawek      08/04/07 16:41      
         Benchmark      John Myers      08/04/07 17:16      
            I did benchmarks as such on AVR      Michael Karas      08/04/07 18:38      
               Similar findings      Russell Bull      08/04/07 20:05      
                  no beavers that I've tended to!!      Michael Karas      08/04/07 21:50      
               not bitwise....      Jan Waclawek      08/05/07 01:45      
            Better is a strong word      Neil Kurzman      08/05/07 20:19      
               Also comment about SMBus PEC Code...      Michael Karas      08/05/07 20:30      
   The Table      Neil Kurzman      08/06/07 10:19      
   The Nibble Table for Poly 107      Neil Kurzman      08/06/07 10:20      
   The formula      Neil Kurzman      08/06/07 10:22      
   Have you seen this?      Richard Erlacher      08/06/07 17:42      
      Now I have      Neil Kurzman      08/06/07 20:26      
      Yes, that is a Key Document!      Andy Neil      08/07/07 01:45      

Back to Subject List