[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [avr-chat] Storing table in flash
|
From: |
David Brown |
|
Subject: |
Re: [avr-chat] Storing table in flash |
|
Date: |
Sat, 12 Jan 2008 23:47:54 +0100 |
|
User-agent: |
Thunderbird 2.0.0.9 (Windows/20071031) |
Preston Wilson wrote:
"Kreyl" wrote:
I'm writing table-based crc16 calculation algoritm. So, I should
store this table somewhere.
Is that enough:
const uint16_t CRC16_8005_TABLE [256] = {
0x0000,0x8005,0x800f,0x000a,0x801b,0x001e,0x0014,0x8011,0x8033,0x0036,0x003c,
...
};
Or I need to use somewhat from <avr/pgmspace.h>? If so, how should I
do that?
Have you looked at avr-libc's crc16 routines? They are in util/crc16.h and
are written in inline assembly, but they include the equivalent C code above
the function definition.
This is the the code from the comments/documentation for crc16_update(),
which is the routine that I think is equivalent to the one your are
implementing (depends upon how the bits are shifted in [lsb vs msb first]
and the initial value [0x0000 vs 0xffff]):
uint16_t
crc16_update(uint16_t crc, uint8_t a)
{
int i;
crc ^= a;
for (i = 0; i < 8; ++i)
{
if (crc & 1)
crc = (crc >> 1) ^ 0xA001;
else
crc = (crc >> 1);
}
return crc;
}
And to answer your question, you can use the table as you have defined it if
you have enough memory to do that, but as the routine above shows, crc16
checksums can be done in a much more space efficient manner.
The table defined above is stored in RAM, not flash (although obviously
the initialisers are stored in flash), and thus takes up lots of
valuable ram space. The routines from avrlibc are much more space
efficient (no tables at all), but are much slower, since they handle a
single bit at a time. I've included routines below that use 256-entry
lookup tables in flash, and are therefore much faster than the avrlibc
version and don't have the ram requirements of the OP's. I've also
included a compromise solution - 16-entry tables, handling 4 bits at a
time. I haven't actually tried this version with avrgcc - I implemented
it in pure assembly many years ago, and it can be very small and tight
(using "swap" instructions). It may be an interesting test case for
benchmarking avrgcc.
If anyone wants to add these crc routines to avrlibc, modified to suit
the avrlibc coding style, then that's fine by me.
The 8-bit crc code used is the same polynomial as the Dallas one-wire
devices, though IIRC there are some differences in the algorithm
(different bit order, or starting value, or something). The 16-bit crc
polynomial is the common "CRC16", as used by the O/P.
mvh.,
David
/* crcTable[i] is used for byte-wise 8-bit crc routine */
static const uint8_t PROGMEM crcTable8[256] = {
0x00, 0x8D, 0x97, 0x1A, 0xA3, 0x2E, 0x34, 0xB9,
0xCB, 0x46, 0x5C, 0xD1, 0x68, 0xE5, 0xFF, 0x72,
0x1B, 0x96, 0x8C, 0x01, 0xB8, 0x35, 0x2F, 0xA2,
0xD0, 0x5D, 0x47, 0xCA, 0x73, 0xFE, 0xE4, 0x69,
0x36, 0xBB, 0xA1, 0x2C, 0x95, 0x18, 0x02, 0x8F,
0xFD, 0x70, 0x6A, 0xE7, 0x5E, 0xD3, 0xC9, 0x44,
0x2D, 0xA0, 0xBA, 0x37, 0x8E, 0x03, 0x19, 0x94,
0xE6, 0x6B, 0x71, 0xFC, 0x45, 0xC8, 0xD2, 0x5F,
0x6C, 0xE1, 0xFB, 0x76, 0xCF, 0x42, 0x58, 0xD5,
0xA7, 0x2A, 0x30, 0xBD, 0x04, 0x89, 0x93, 0x1E,
0x77, 0xFA, 0xE0, 0x6D, 0xD4, 0x59, 0x43, 0xCE,
0xBC, 0x31, 0x2B, 0xA6, 0x1F, 0x92, 0x88, 0x05,
0x5A, 0xD7, 0xCD, 0x40, 0xF9, 0x74, 0x6E, 0xE3,
0x91, 0x1C, 0x06, 0x8B, 0x32, 0xBF, 0xA5, 0x28,
0x41, 0xCC, 0xD6, 0x5B, 0xE2, 0x6F, 0x75, 0xF8,
0x8A, 0x07, 0x1D, 0x90, 0x29, 0xA4, 0xBE, 0x33,
0xD8, 0x55, 0x4F, 0xC2, 0x7B, 0xF6, 0xEC, 0x61,
0x13, 0x9E, 0x84, 0x09, 0xB0, 0x3D, 0x27, 0xAA,
0xC3, 0x4E, 0x54, 0xD9, 0x60, 0xED, 0xF7, 0x7A,
0x08, 0x85, 0x9F, 0x12, 0xAB, 0x26, 0x3C, 0xB1,
0xEE, 0x63, 0x79, 0xF4, 0x4D, 0xC0, 0xDA, 0x57,
0x25, 0xA8, 0xB2, 0x3F, 0x86, 0x0B, 0x11, 0x9C,
0xF5, 0x78, 0x62, 0xEF, 0x56, 0xDB, 0xC1, 0x4C,
0x3E, 0xB3, 0xA9, 0x24, 0x9D, 0x10, 0x0A, 0x87,
0xB4, 0x39, 0x23, 0xAE, 0x17, 0x9A, 0x80, 0x0D,
0x7F, 0xF2, 0xE8, 0x65, 0xDC, 0x51, 0x4B, 0xC6,
0xAF, 0x22, 0x38, 0xB5, 0x0C, 0x81, 0x9B, 0x16,
0x64, 0xE9, 0xF3, 0x7E, 0xC7, 0x4A, 0x50, 0xDD,
0x82, 0x0F, 0x15, 0x98, 0x21, 0xAC, 0xB6, 0x3B,
0x49, 0xC4, 0xDE, 0x53, 0xEA, 0x67, 0x7D, 0xF0,
0x99, 0x14, 0x0E, 0x83, 0x3A, 0xB7, 0xAD, 0x20,
0x52, 0xDF, 0xC5, 0x48, 0xF1, 0x7C, 0x66, 0xEB
};
/* crcTable[i] is used for byte-wise 8-bit crc routine */
static const uint16_t PROGMEM crcTable16[256] = {
0x0000, 0x8005, 0x800F, 0x000A, 0x801B, 0x001E, 0x0014, 0x8011,
0x8033, 0x0036, 0x003C, 0x8039, 0x0028, 0x802D, 0x8027, 0x0022,
0x8063, 0x0066, 0x006C, 0x8069, 0x0078, 0x807D, 0x8077, 0x0072,
0x0050, 0x8055, 0x805F, 0x005A, 0x804B, 0x004E, 0x0044, 0x8041,
0x80C3, 0x00C6, 0x00CC, 0x80C9, 0x00D8, 0x80DD, 0x80D7, 0x00D2,
0x00F0, 0x80F5, 0x80FF, 0x00FA, 0x80EB, 0x00EE, 0x00E4, 0x80E1,
0x00A0, 0x80A5, 0x80AF, 0x00AA, 0x80BB, 0x00BE, 0x00B4, 0x80B1,
0x8093, 0x0096, 0x009C, 0x8099, 0x0088, 0x808D, 0x8087, 0x0082,
0x8183, 0x0186, 0x018C, 0x8189, 0x0198, 0x819D, 0x8197, 0x0192,
0x01B0, 0x81B5, 0x81BF, 0x01BA, 0x81AB, 0x01AE, 0x01A4, 0x81A1,
0x01E0, 0x81E5, 0x81EF, 0x01EA, 0x81FB, 0x01FE, 0x01F4, 0x81F1,
0x81D3, 0x01D6, 0x01DC, 0x81D9, 0x01C8, 0x81CD, 0x81C7, 0x01C2,
0x0140, 0x8145, 0x814F, 0x014A, 0x815B, 0x015E, 0x0154, 0x8151,
0x8173, 0x0176, 0x017C, 0x8179, 0x0168, 0x816D, 0x8167, 0x0162,
0x8123, 0x0126, 0x012C, 0x8129, 0x0138, 0x813D, 0x8137, 0x0132,
0x0110, 0x8115, 0x811F, 0x011A, 0x810B, 0x010E, 0x0104, 0x8101,
0x8303, 0x0306, 0x030C, 0x8309, 0x0318, 0x831D, 0x8317, 0x0312,
0x0330, 0x8335, 0x833F, 0x033A, 0x832B, 0x032E, 0x0324, 0x8321,
0x0360, 0x8365, 0x836F, 0x036A, 0x837B, 0x037E, 0x0374, 0x8371,
0x8353, 0x0356, 0x035C, 0x8359, 0x0348, 0x834D, 0x8347, 0x0342,
0x03C0, 0x83C5, 0x83CF, 0x03CA, 0x83DB, 0x03DE, 0x03D4, 0x83D1,
0x83F3, 0x03F6, 0x03FC, 0x83F9, 0x03E8, 0x83ED, 0x83E7, 0x03E2,
0x83A3, 0x03A6, 0x03AC, 0x83A9, 0x03B8, 0x83BD, 0x83B7, 0x03B2,
0x0390, 0x8395, 0x839F, 0x039A, 0x838B, 0x038E, 0x0384, 0x8381,
0x0280, 0x8285, 0x828F, 0x028A, 0x829B, 0x029E, 0x0294, 0x8291,
0x82B3, 0x02B6, 0x02BC, 0x82B9, 0x02A8, 0x82AD, 0x82A7, 0x02A2,
0x82E3, 0x02E6, 0x02EC, 0x82E9, 0x02F8, 0x82FD, 0x82F7, 0x02F2,
0x02D0, 0x82D5, 0x82DF, 0x02DA, 0x82CB, 0x02CE, 0x02C4, 0x82C1,
0x8243, 0x0246, 0x024C, 0x8249, 0x0258, 0x825D, 0x8257, 0x0252,
0x0270, 0x8275, 0x827F, 0x027A, 0x826B, 0x026E, 0x0264, 0x8261,
0x0220, 0x8225, 0x822F, 0x022A, 0x823B, 0x023E, 0x0234, 0x8231,
0x8213, 0x0216, 0x021C, 0x8219, 0x0208, 0x820D, 0x8207, 0x0202
};
/* When you have a full table, an 8-bit CRC routine is pretty simple! */
uint8_t CrcByte8(uint8_t crc, uint8_t data) {
// Fold next byte into CRC
return pgm_read_byte(&crcTable8[crc ^ data]);
}
uint8_t CrcData8(uint8_t crc, const void* data, uint16_t size) {
// Fold bytes into CRC
const uint8_t* p = data;
while (size--) {
crc = pgm_read_byte(&crcTable8[crc ^ (*p++)]);
};
return crc;
}
uint16_t CrcByte16(uint16_t crc, uint8_t data) {
// Fold next byte into CRC
return (crc << 8) ^ pgm_read_word(&crcTable16[(crc >> 8) ^ data]);
}
uint16_t CrcData16(uint16_t crc, const void* data, uint16_t size) {
// Fold bytes into CRC
const uint8_t* p = data;
while (size--) {
crc = (crc << 8) ^ pgm_read_word(&crcTable16[(crc >> 8) ^
(*p++)]);
};
return crc;
}
// Implemented with nibbles
static const uint8_t PROGMEM crcTable8n[16] = {
0x00, 0x8D, 0x97, 0x1A, 0xA3, 0x2E, 0x34, 0xB9,
0xCB, 0x46, 0x5C, 0xD1, 0x68, 0xE5, 0xFF, 0x72
};
static const uint16_t PROGMEM crcTable16n[16] = {
0x0000, 0x8005, 0x800F, 0x000A, 0x801B, 0x001E, 0x0014, 0x8011,
0x8033, 0x0036, 0x003C, 0x8039, 0x0028, 0x802D, 0x8027, 0x0022
};
uint8_t CrcByte8n(uint8_t crc, uint8_t data) {
// Fold next byte into CRC
crc = (crc << 4) ^ (pgm_read_byte(&crcTable8n[(crc >> 4) ^
(data >> 4)]));
crc = (crc << 4) ^ (pgm_read_byte(&crcTable8n[(crc >> 4) ^
(data & 0x0f)]));
return crc;
}
uint8_t CrcData8n(uint8_t crc, const void* data, uint16_t size) {
// Fold bytes into CRC
const uint8_t* p = data;
while (size--) {
crc = (crc << 4) ^ (pgm_read_byte(&crcTable8n[(crc >>
4) ^ ((*p) >> 4)]));
crc = (crc << 4) ^ (pgm_read_byte(&crcTable8n[(crc >>
4) ^ ((*p) & 0x0f)]));
p++;
};
return crc;
}
uint16_t CrcByte16n(uint16_t crc, uint8_t data) {
// Fold next byte into CRC
crc = (crc << 4) ^ (pgm_read_word(&crcTable16n[(crc >> 12) ^
(data >> 4)]));
crc = (crc << 4) ^ (pgm_read_word(&crcTable16n[(crc >> 12) ^
(data & 0x0f)]));
return crc;
}
uint16_t CrcData16n(uint16_t crc, const void* data, uint16_t size) {
// Fold bytes into CRC
const uint8_t* p = data;
while (size--) {
crc = (crc << 4) ^ (pgm_read_word(&crcTable16n[(crc >>
12) ^ ((*p) >> 4)]));
crc = (crc << 4) ^ (pgm_read_word(&crcTable16n[(crc >>
12) ^ ((*p) & 0x0f)]));
p++;
};
return crc;
}