Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > C/C++: Общие вопросы > Вычисление контрольной суммы


Автор: AntonN 8.8.2006, 16:52
Всем Привет!

У меня проблема с вычислением CRC16. Есть небольшое объяснение и примеры, но как они получились не понимаю....

CRC is calculated over data bytes of the message (start and end of message characters are excluded). CRC is initialised to 0000. Two examples of messages with checksum:

CRC-16:
1A 32 12 34 56 0D 38 43
1A 33 12 34 56 0D 39 BF

1 и 6 байты не считаются... т.е. из 32 12 34 56 сумма получается 38 43

Есть еще программа на ассемблере которая вычисляет эту сумму, но, к сожалению, его я не знаю... 

Here is our crc-program (Motorola 6809 assembly language)

***********************************************
CRC_O EQU * program updates crc-sum
* CRC_D (2 bytes) with character in A-reg.
CRC_G EQU $A001
***********************************************

DSCT
CRC_D RMB 2 crc-sum
PSCT 
PSHS D,X
* char to stack
PSHS A
* crc to D
LDD CRC_D
LDX #8
REPEAT
LSRA msb of crc
EORB S char
BITB #1
IF <EQ> THEN.S
* b0s same before shift
EORB S restore of B
RORB
ELSE.S
* b0s not same before shift
EORB S restore of B
RORB
EORA #CRC_G!>8
EORB #CRC_G!.$FF
ENDI
LSR S char
LEAX -1,X
UNTIL <EQ>
* char has been processed
STD CRC_D
LEAS 1,S
PULS D,X,PC
* 8*35+44(+JSR) us 324(+JSR) us

Помогите, плиз, ОООЧЕНЬ надо...

Заранее благодарен,
Антон

Автор: _hunter 8.8.2006, 17:02
дык помогти с чем?
и при чем тут C/C++

Автор: MAKCim 8.8.2006, 17:07
Цитата

дык помогти с чем?
и при чем тут C/C++ 

судя по всему с asm-а на С/С++ перевести

Автор: _hunter 8.8.2006, 17:21
дык это даже не асм...

Автор: dumb 8.8.2006, 17:24
это асм, только мотороловский.. ;)

AntonN, четвертую тему в "А здесь смотрели?"(внизу) посмотри.

Автор: Mayk 8.8.2006, 17:24
Цитата(_hunter @  8.8.2006,  21:21 Найти цитируемый пост)
дык это даже не асм...

Цитата(AntonN @  8.8.2006,  20:52 Найти цитируемый пост)
(Motorola 6809 assembly language)

забавный синтаксис.

Добавлено @ 17:25 
не успел! /me опередили.

Автор: Fin 8.8.2006, 17:27
На одном из сайтов (Помоему Алголист), я видел такой алгоритм подсчета CRC32
Код

DWORD  CountCRC(char *Buf, int Len)

{
DWORD  crc=0;

static const DWORD table [] = {

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

}; 



    int nIndex; 

    for (int i=0;i<Len;i++) 

    { 



        nIndex = (crc >> 24) & 0xFF;  

        crc = ((crc << 8) | Buf[i]) ^ table[nIndex]; 

      } 

return crc;
}


Добавлено @ 17:30 
ОПс не заметил, что парню нужно CRC16.

Добавлено @ 17:41 
Вот ссылочка http://algolist.manual.ru/compress/index.php. Внизу страници есть ссылочка на книгу в формате PDF "Элементарное руководство по CRC-алгоритмам обнаружения ошибок" Весит 165 килобайт.

Автор: AntonN 9.8.2006, 14:11
Цитата

Вот ссылочка http://algolist.manual.ru/compress/index.php. Внизу страници есть ссылочка на книгу в формате PDF "Элементарное руководство по CRC-алгоритмам обнаружения ошибок" Весит 165 килобайт.

Спасибо... Книгу читал, но итоговая сумма получается неверной... В файле показан мой процесс вычисления... Может, в чем-то не прав? ИМХО у них алгоритм какой-то другой... Для этого ассемблеровский код и выложил....

Заранее благодарен,
Антон

Автор: AntonN 10.8.2006, 14:05
Неужели никто не сможет мне помочь???
 smile 
В zip-у вирусов нет, не бойтесь.... Хотел выложить .doc-овский файл, но вылезла ошибка о том, что данный тип файла не может быть прикреплен.... 

Заранее благодарен,
Антон

Автор: _hunter 10.8.2006, 14:27
помочь с чем? -- в сети порядочно алгоритмов CRC16. реализуй два и сравни с твоим -- будет понятно кто не прав.
+ попробуй проинвертировать сумму...

Автор: dumb 10.8.2006, 16:14
Код

static const unsigned short crc16tab[] = /* CRC lookup table */
{
    0x0000, 0xC0C1, 0xC181, 0x0140, 0xC301, 0x03C0, 0x0280, 0xC241,
    0xC601, 0x06C0, 0x0780, 0xC741, 0x0500, 0xC5C1, 0xC481, 0x0440,
    0xCC01, 0x0CC0, 0x0D80, 0xCD41, 0x0F00, 0xCFC1, 0xCE81, 0x0E40,
    0x0A00, 0xCAC1, 0xCB81, 0x0B40, 0xC901, 0x09C0, 0x0880, 0xC841,
    0xD801, 0x18C0, 0x1980, 0xD941, 0x1B00, 0xDBC1, 0xDA81, 0x1A40,
    0x1E00, 0xDEC1, 0xDF81, 0x1F40, 0xDD01, 0x1DC0, 0x1C80, 0xDC41,
    0x1400, 0xD4C1, 0xD581, 0x1540, 0xD701, 0x17C0, 0x1680, 0xD641,
    0xD201, 0x12C0, 0x1380, 0xD341, 0x1100, 0xD1C1, 0xD081, 0x1040,
    0xF001, 0x30C0, 0x3180, 0xF141, 0x3300, 0xF3C1, 0xF281, 0x3240,
    0x3600, 0xF6C1, 0xF781, 0x3740, 0xF501, 0x35C0, 0x3480, 0xF441,
    0x3C00, 0xFCC1, 0xFD81, 0x3D40, 0xFF01, 0x3FC0, 0x3E80, 0xFE41,
    0xFA01, 0x3AC0, 0x3B80, 0xFB41, 0x3900, 0xF9C1, 0xF881, 0x3840,
    0x2800, 0xE8C1, 0xE981, 0x2940, 0xEB01, 0x2BC0, 0x2A80, 0xEA41,
    0xEE01, 0x2EC0, 0x2F80, 0xEF41, 0x2D00, 0xEDC1, 0xEC81, 0x2C40,
    0xE401, 0x24C0, 0x2580, 0xE541, 0x2700, 0xE7C1, 0xE681, 0x2640,
    0x2200, 0xE2C1, 0xE381, 0x2340, 0xE101, 0x21C0, 0x2080, 0xE041,
    0xA001, 0x60C0, 0x6180, 0xA141, 0x6300, 0xA3C1, 0xA281, 0x6240,
    0x6600, 0xA6C1, 0xA781, 0x6740, 0xA501, 0x65C0, 0x6480, 0xA441,
    0x6C00, 0xACC1, 0xAD81, 0x6D40, 0xAF01, 0x6FC0, 0x6E80, 0xAE41,
    0xAA01, 0x6AC0, 0x6B80, 0xAB41, 0x6900, 0xA9C1, 0xA881, 0x6840,
    0x7800, 0xB8C1, 0xB981, 0x7940, 0xBB01, 0x7BC0, 0x7A80, 0xBA41,
    0xBE01, 0x7EC0, 0x7F80, 0xBF41, 0x7D00, 0xBDC1, 0xBC81, 0x7C40,
    0xB401, 0x74C0, 0x7580, 0xB541, 0x7700, 0xB7C1, 0xB681, 0x7640,
    0x7200, 0xB2C1, 0xB381, 0x7340, 0xB101, 0x71C0, 0x7080, 0xB041,
    0x5000, 0x90C1, 0x9181, 0x5140, 0x9301, 0x53C0, 0x5280, 0x9241,
    0x9601, 0x56C0, 0x5780, 0x9741, 0x5500, 0x95C1, 0x9481, 0x5440,
    0x9C01, 0x5CC0, 0x5D80, 0x9D41, 0x5F00, 0x9FC1, 0x9E81, 0x5E40,
    0x5A00, 0x9AC1, 0x9B81, 0x5B40, 0x9901, 0x59C0, 0x5880, 0x9841,
    0x8801, 0x48C0, 0x4980, 0x8941, 0x4B00, 0x8BC1, 0x8A81, 0x4A40,
    0x4E00, 0x8EC1, 0x8F81, 0x4F40, 0x8D01, 0x4DC0, 0x4C80, 0x8C41,
    0x4400, 0x84C1, 0x8581, 0x4540, 0x8701, 0x47C0, 0x4680, 0x8641,
    0x8201, 0x42C0, 0x4380, 0x8341, 0x4100, 0x81C1, 0x8081, 0x4040
};

void crc16_init(unsigned short *uCrc16)
{
    *uCrc16 = 0xFFFF; // - так обычно инициализируется seed crc16
}

void crc16_update(unsigned short *uCrc16, unsigned char *pBuffer, unsigned long uBufSize)
{
    unsigned long i = 0;

    for(i = 0; i < uBufSize; i++)
        *uCrc16 = (*uCrc16 >> 8) ^ crc16tab[(*uCrc16 ^ *pBuffer++) & 0xFF];
}

void crc16_final(unsigned short *uCrc16)
{
    *uCrc16 = ~(*uCrc16); // так обычно завершается подсчет для блока данных
}

в общем, пару упрощений они сделали.
использовать примерно так:
Код

char * buf = "\x32\x12\x34\x56";
unsigned short crc = 0; // "CRC is initialised to 0000."
crc16_update(&crc, buf, sizeof(buf));
printf( "crc16 = %X", crc );

Автор: AntonN 11.8.2006, 13:22
Цитата

Код

static const unsigned short crc16tab[] = /* CRC lookup table */
{
    0x0000, 0xC0C1, 0xC181, 0x0140, 0xC301, 0x03C0, 0x0280, 0xC241,
    0xC601, 0x06C0, 0x0780, 0xC741, 0x0500, 0xC5C1, 0xC481, 0x0440,
    0xCC01, 0x0CC0, 0x0D80, 0xCD41, 0x0F00, 0xCFC1, 0xCE81, 0x0E40,
    0x0A00, 0xCAC1, 0xCB81, 0x0B40, 0xC901, 0x09C0, 0x0880, 0xC841,
    0xD801, 0x18C0, 0x1980, 0xD941, 0x1B00, 0xDBC1, 0xDA81, 0x1A40,
    0x1E00, 0xDEC1, 0xDF81, 0x1F40, 0xDD01, 0x1DC0, 0x1C80, 0xDC41,
    0x1400, 0xD4C1, 0xD581, 0x1540, 0xD701, 0x17C0, 0x1680, 0xD641,
    0xD201, 0x12C0, 0x1380, 0xD341, 0x1100, 0xD1C1, 0xD081, 0x1040,
    0xF001, 0x30C0, 0x3180, 0xF141, 0x3300, 0xF3C1, 0xF281, 0x3240,
    0x3600, 0xF6C1, 0xF781, 0x3740, 0xF501, 0x35C0, 0x3480, 0xF441,
    0x3C00, 0xFCC1, 0xFD81, 0x3D40, 0xFF01, 0x3FC0, 0x3E80, 0xFE41,
    0xFA01, 0x3AC0, 0x3B80, 0xFB41, 0x3900, 0xF9C1, 0xF881, 0x3840,
    0x2800, 0xE8C1, 0xE981, 0x2940, 0xEB01, 0x2BC0, 0x2A80, 0xEA41,
    0xEE01, 0x2EC0, 0x2F80, 0xEF41, 0x2D00, 0xEDC1, 0xEC81, 0x2C40,
    0xE401, 0x24C0, 0x2580, 0xE541, 0x2700, 0xE7C1, 0xE681, 0x2640,
    0x2200, 0xE2C1, 0xE381, 0x2340, 0xE101, 0x21C0, 0x2080, 0xE041,
    0xA001, 0x60C0, 0x6180, 0xA141, 0x6300, 0xA3C1, 0xA281, 0x6240,
    0x6600, 0xA6C1, 0xA781, 0x6740, 0xA501, 0x65C0, 0x6480, 0xA441,
    0x6C00, 0xACC1, 0xAD81, 0x6D40, 0xAF01, 0x6FC0, 0x6E80, 0xAE41,
    0xAA01, 0x6AC0, 0x6B80, 0xAB41, 0x6900, 0xA9C1, 0xA881, 0x6840,
    0x7800, 0xB8C1, 0xB981, 0x7940, 0xBB01, 0x7BC0, 0x7A80, 0xBA41,
    0xBE01, 0x7EC0, 0x7F80, 0xBF41, 0x7D00, 0xBDC1, 0xBC81, 0x7C40,
    0xB401, 0x74C0, 0x7580, 0xB541, 0x7700, 0xB7C1, 0xB681, 0x7640,
    0x7200, 0xB2C1, 0xB381, 0x7340, 0xB101, 0x71C0, 0x7080, 0xB041,
    0x5000, 0x90C1, 0x9181, 0x5140, 0x9301, 0x53C0, 0x5280, 0x9241,
    0x9601, 0x56C0, 0x5780, 0x9741, 0x5500, 0x95C1, 0x9481, 0x5440,
    0x9C01, 0x5CC0, 0x5D80, 0x9D41, 0x5F00, 0x9FC1, 0x9E81, 0x5E40,
    0x5A00, 0x9AC1, 0x9B81, 0x5B40, 0x9901, 0x59C0, 0x5880, 0x9841,
    0x8801, 0x48C0, 0x4980, 0x8941, 0x4B00, 0x8BC1, 0x8A81, 0x4A40,
    0x4E00, 0x8EC1, 0x8F81, 0x4F40, 0x8D01, 0x4DC0, 0x4C80, 0x8C41,
    0x4400, 0x84C1, 0x8581, 0x4540, 0x8701, 0x47C0, 0x4680, 0x8641,
    0x8201, 0x42C0, 0x4380, 0x8341, 0x4100, 0x81C1, 0x8081, 0x4040
};

void crc16_init(unsigned short *uCrc16)
{
    *uCrc16 = 0xFFFF; // - так обычно инициализируется seed crc16
}

void crc16_update(unsigned short *uCrc16, unsigned char *pBuffer, unsigned long uBufSize)
{
    unsigned long i = 0;

    for(i = 0; i < uBufSize; i++)
        *uCrc16 = (*uCrc16 >> 8) ^ crc16tab[(*uCrc16 ^ *pBuffer++) & 0xFF];
}

void crc16_final(unsigned short *uCrc16)
{
    *uCrc16 = ~(*uCrc16); // так обычно завершается подсчет для блока данных
}

в общем, пару упрощений они сделали.
использовать примерно так:
Код

char * buf = "\x32\x12\x34\x56";
unsigned short crc = 0; // "CRC is initialised to 0000."
crc16_update(&crc, buf, sizeof(buf));
printf( "crc16 = %X", crc );



Dumb, спасибо большое!  smile 

Все работает.... Осталось только разобраться как....  smile 

Антон

Автор: jonie 11.8.2006, 22:35
не в тему (но всеже о том) генерировал когда-то давно, когда надо было для CRC32 таблицу сам (уж больно ломает меня писать этот массивчик ручками, да и зачем...)
это для CRC32 (asm)
Код

;;;;;;;;;;;;;;;;;
;;Init CRC32 table
;;in push offset table
;;   call InitCRCTable
;;out:???
;; mailmodule myst have :
;; magic_table    DWORD 256 dup (?)
;; as example)...
;;;;;;;;;;;;;;;;;;

magic_poly        equ 0EDB88320h


InitCRCTable PROC
    push EBP
    mov  EBP,ESP

    push ECX
    push EBX
    mov  EBX,[EBP+8]                  ;offset table
    mov  CL,00                        ;TOTAL Iteration
@_InitCRCTable1_@:
    xor  EAX,EAX
    mov  al,cl
;{======================}
    mov  CH,1
  @_InitCRCTable2_@:
    TEST EAX,01
    JZ   @_InitCRCTable3_@
    SHR  EAX,1
    XOR  EAX,magic_poly
    jmp  short @_InitCRCTable4_@
  @_InitCRCTable3_@:
    SHR  EAX,1
  @_InitCRCTable4_@:
    inc  CH
    cmp  CH,09
    jnz  @_InitCRCTable2_@
;{======================}
    mov  [EBX],EAX
    ADD  EBX,4
    inc  CL
    jnz  @_InitCRCTable1_@
    pop  EBX
    pop  ECX
    pop  EBP
    ret  4
InitCRCTable ENDP

не оптимизированно  толком (ибо не тут и надо скорость выжимать ессно).... но вроде работало
кстати аналогично можно и для CRC16 сделать... принцип любой цикличной суммы одинаков.. хоть crc128 берите....
а код... писалось давно и неправда)

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)