Нужно переделать алгоритм вычисления CRC32 табличным способом

@XRS · Регистрация: 15.08.2016

Студворк — интернет-сервис помощи студентам

Привет всем.

Предисловие. Есть промышленное изделие, в котором надо программно считать CRC32 для блоков данных. Алгоритм определен заказчиком и его никак нельзя менять! Т.к. CRC32 потом сверяется внешней программой на компе и записью в документах.

Есть такая проблема. Алгоритм вычисления этой CRC32 реализован сдвигами побитно для каждого нового байта в блоке, т.е. самый медленный из возможных. Блоки бывают большой длины и вычисление занимает приличное время. Все бы хорошо, но алгоритм не совсем стандартный (как я понял). Вопрос в следующем: может ли кто то помочь переделать исходник чтобы реализовать его табличным методом? Т.е. сгенерировать таблицу из 256 (для байтовых входных данных) или 16 (для 4-х битных входных данных) 32-х битных элементов и процедуру для вычисления CRC32 с этой таблицей. Если это вообще возможно. Но пока мне не удалось. На выходе не получается нужная CRC.

"Не совсем стандартный метод CRC32" - это означает, что он старый и вычисление идет по несколько иной схеме, чем современные реализации (к которым мы привыкли). Функция совсем простая (реально 6 строк на "Си"), а как переделать на работу с таблицей и как получить саму таблицу? Все файлы и исходник на "Си" (консольное приложение) приложены в архиве, там и текст описания метода. Можно собрать под DOS или Win32 любым компилятором. Я компилировал с помощью Borland C++ 5.5.1 for Win32.

Строка "123456789" должна давать в итоге CRC = 0xCCBD34E2.

Вложение содержит все подробности и исходник (RAR архив).

Заранее буду благодарен.

@L0M · 06.12.2019, 16:09

XRS, без гарантий, поэтому проверяйте:

C++

#include <windows.h>
#include <stdio.h>
#include <io.h>
#include <fcntl.h>
#include <sys\stat.h>
 
// -------------------------------------------
 
#define  CRC32_INIT_VALUE  0x00000000UL  // начальное значение CRC
#define  CRC32_POLYNOMIAL  0x04C11DB7UL  // полином
 
const DWORD Crc32Table[256] = {
    0x00000000, 0x04C11DB7, 0x09823B6E, 0x0D4326D9,
    0x130476DC, 0x17C56B6B, 0x1A864DB2, 0x1E475005,
    0x2608EDB8, 0x22C9F00F, 0x2F8AD6D6, 0x2B4BCB61,
    0x350C9B64, 0x31CD86D3, 0x3C8EA00A, 0x384FBDBD,
    0x4C11DB70, 0x48D0C6C7, 0x4593E01E, 0x4152FDA9,
    0x5F15ADAC, 0x5BD4B01B, 0x569796C2, 0x52568B75,
    0x6A1936C8, 0x6ED82B7F, 0x639B0DA6, 0x675A1011,
    0x791D4014, 0x7DDC5DA3, 0x709F7B7A, 0x745E66CD,
    0x9823B6E0, 0x9CE2AB57, 0x91A18D8E, 0x95609039,
    0x8B27C03C, 0x8FE6DD8B, 0x82A5FB52, 0x8664E6E5,
    0xBE2B5B58, 0xBAEA46EF, 0xB7A96036, 0xB3687D81,
    0xAD2F2D84, 0xA9EE3033, 0xA4AD16EA, 0xA06C0B5D,
    0xD4326D90, 0xD0F37027, 0xDDB056FE, 0xD9714B49,
    0xC7361B4C, 0xC3F706FB, 0xCEB42022, 0xCA753D95,
    0xF23A8028, 0xF6FB9D9F, 0xFBB8BB46, 0xFF79A6F1,
    0xE13EF6F4, 0xE5FFEB43, 0xE8BCCD9A, 0xEC7DD02D,
    0x34867077, 0x30476DC0, 0x3D044B19, 0x39C556AE,
    0x278206AB, 0x23431B1C, 0x2E003DC5, 0x2AC12072,
    0x128E9DCF, 0x164F8078, 0x1B0CA6A1, 0x1FCDBB16,
    0x018AEB13, 0x054BF6A4, 0x0808D07D, 0x0CC9CDCA,
    0x7897AB07, 0x7C56B6B0, 0x71159069, 0x75D48DDE,
    0x6B93DDDB, 0x6F52C06C, 0x6211E6B5, 0x66D0FB02,
    0x5E9F46BF, 0x5A5E5B08, 0x571D7DD1, 0x53DC6066,
    0x4D9B3063, 0x495A2DD4, 0x44190B0D, 0x40D816BA,
    0xACA5C697, 0xA864DB20, 0xA527FDF9, 0xA1E6E04E,
    0xBFA1B04B, 0xBB60ADFC, 0xB6238B25, 0xB2E29692,
    0x8AAD2B2F, 0x8E6C3698, 0x832F1041, 0x87EE0DF6,
    0x99A95DF3, 0x9D684044, 0x902B669D, 0x94EA7B2A,
    0xE0B41DE7, 0xE4750050, 0xE9362689, 0xEDF73B3E,
    0xF3B06B3B, 0xF771768C, 0xFA325055, 0xFEF34DE2,
    0xC6BCF05F, 0xC27DEDE8, 0xCF3ECB31, 0xCBFFD686,
    0xD5B88683, 0xD1799B34, 0xDC3ABDED, 0xD8FBA05A,
    0x690CE0EE, 0x6DCDFD59, 0x608EDB80, 0x644FC637,
    0x7A089632, 0x7EC98B85, 0x738AAD5C, 0x774BB0EB,
    0x4F040D56, 0x4BC510E1, 0x46863638, 0x42472B8F,
    0x5C007B8A, 0x58C1663D, 0x558240E4, 0x51435D53,
    0x251D3B9E, 0x21DC2629, 0x2C9F00F0, 0x285E1D47,
    0x36194D42, 0x32D850F5, 0x3F9B762C, 0x3B5A6B9B,
    0x0315D626, 0x07D4CB91, 0x0A97ED48, 0x0E56F0FF,
    0x1011A0FA, 0x14D0BD4D, 0x19939B94, 0x1D528623,
    0xF12F560E, 0xF5EE4BB9, 0xF8AD6D60, 0xFC6C70D7,
    0xE22B20D2, 0xE6EA3D65, 0xEBA91BBC, 0xEF68060B,
    0xD727BBB6, 0xD3E6A601, 0xDEA580D8, 0xDA649D6F,
    0xC423CD6A, 0xC0E2D0DD, 0xCDA1F604, 0xC960EBB3,
    0xBD3E8D7E, 0xB9FF90C9, 0xB4BCB610, 0xB07DABA7,
    0xAE3AFBA2, 0xAAFBE615, 0xA7B8C0CC, 0xA379DD7B,
    0x9B3660C6, 0x9FF77D71, 0x92B45BA8, 0x9675461F,
    0x8832161A, 0x8CF30BAD, 0x81B02D74, 0x857130C3,
    0x5D8A9099, 0x594B8D2E, 0x5408ABF7, 0x50C9B640,
    0x4E8EE645, 0x4A4FFBF2, 0x470CDD2B, 0x43CDC09C,
    0x7B827D21, 0x7F436096, 0x7200464F, 0x76C15BF8,
    0x68860BFD, 0x6C47164A, 0x61043093, 0x65C52D24,
    0x119B4BE9, 0x155A565E, 0x18197087, 0x1CD86D30,
    0x029F3D35, 0x065E2082, 0x0B1D065B, 0x0FDC1BEC,
    0x3793A651, 0x3352BBE6, 0x3E119D3F, 0x3AD08088,
    0x2497D08D, 0x2056CD3A, 0x2D15EBE3, 0x29D4F654,
    0xC5A92679, 0xC1683BCE, 0xCC2B1D17, 0xC8EA00A0,
    0xD6AD50A5, 0xD26C4D12, 0xDF2F6BCB, 0xDBEE767C,
    0xE3A1CBC1, 0xE760D676, 0xEA23F0AF, 0xEEE2ED18,
    0xF0A5BD1D, 0xF464A0AA, 0xF9278673, 0xFDE69BC4,
    0x89B8FD09, 0x8D79E0BE, 0x803AC667, 0x84FBDBD0,
    0x9ABC8BD5, 0x9E7D9662, 0x933EB0BB, 0x97FFAD0C,
    0xAFB010B1, 0xAB710D06, 0xA6322BDF, 0xA2F33668,
    0xBCB4666D, 0xB8757BDA, 0xB5365D03, 0xB1F740B4
};
 
 
// тип: объединение: как двойное слово и как 4 байта
typedef union _DWORD_DATA
{
    DWORD  d;
    BYTE   b[4];
} DWORD_DATA, * PDWORD_DATA;
 
void CRC32Init(PDWORD_DATA pCRC);
void CRC32Update(PDWORD_DATA pCRC, BYTE b);
void CRC32UpdateBlock(PDWORD_DATA pCRC, CONST BYTE* pBuffer, DWORD BlockSize);
void CRC32Done(PDWORD_DATA pCRC);
 
#define  RESULT_OK     0
#define  RESULT_ERROR  1
 
#define  LF  "\n"
 
#define  BUFFER_SIZE  1024  // размер буфера в байтах
 
// -------------------------------------------
 
LPSTR       pInFileName;
int         hFile;
DWORD       FileSize;
DWORD       FileOst;  // длина остатка
DWORD_DATA  uCRC;  // CRC
DWORD       CurDataSize;  // размер текущего блока
BYTE        Buffer[BUFFER_SIZE];
 
// -------------------------------------------
 
 
// Генерация таблицы.
void genTable() {
    // CRC_Polynom - значение полинома CRC
    // CRCTable[0x100] - таблица
    for (int x = 0; x < 0x100; x++) {
        DWORD _crc = x << 24;
        for (int y = 0; y < 8; y++) {
            _crc = (_crc & (1 << 31)) ? ((_crc << 1) ^ CRC32_POLYNOMIAL) : (_crc << 1);
        }
        printf("0x%08lX, ", _crc);
        if ((x + 1) % 4 == 0)
            puts("");
    }
}
 
 
int main(int argc, char* argv[])
{
    //genTable();
    //return 0;
 
    //if (argc != 2)
    //{
    //  printf("CRC32 Calc" LF "Usage: crc32.exe <file>" LF);
    //  return RESULT_ERROR;
    //}
 
    //// копировать указатель на имя файла
    //pInFileName = argv[1];
 
    pInFileName = "TEST.BIN";
 
    // открыть файл на чтение в двоичном режиме
    hFile = _open(pInFileName,
        O_RDONLY | O_BINARY,  // параметр access
        S_IREAD);             // параметр mode
    if (hFile == -1)
    {
        printf("crc32: File %s open error" LF, pInFileName);
        return RESULT_ERROR;
    }
 
    // получить длину открытого файла
    FileSize = (DWORD)_filelength(hFile);
    if (FileSize == (DWORD)-1L)
    {
        printf("crc32: filelength error in %s" LF, pInFileName);
        _close(hFile);
        return RESULT_ERROR;
    }
 
    CRC32Init(&uCRC);  // инициализировать начальное значение CRC
 
    // цикл - подсчет CRC
    FileOst = FileSize;  // осталось обработать байт
    while (TRUE)
    {
        // вычислить размер текущего блока (но не более BUFFER_SIZE байт)
        CurDataSize = (FileOst < BUFFER_SIZE) ?
            FileOst : BUFFER_SIZE;
 
        if (!CurDataSize)
            break;  // больше нет данных для обработки - найден конец файла
 
        _read(hFile, Buffer, CurDataSize);  // читать файл в буфер Buffer
 
        CRC32UpdateBlock(&uCRC, Buffer, CurDataSize);  // вычислить CRC для блока данных
 
        FileOst -= CurDataSize;  // учесть обработанный кусок данных
    }
 
    CRC32Done(&uCRC);  // финализировать конечное значение CRC
 
    // вывод результата
    printf("File: \"%s\"   CRC: %02X %02X %02X %02X" LF,
        pInFileName,
        uCRC.b[3], uCRC.b[2], uCRC.b[1], uCRC.b[0]);
 
    _close(hFile);
    return RESULT_OK;
}
 
// -------------------------------------------
 
// инициализировать начальное значение CRC до подсчета
// вход:  pCRC - указатель на CRC
// выход: нет
 
void CRC32Init(PDWORD_DATA pCRC)
{
    pCRC->d = CRC32_INIT_VALUE;
}
 
// -------------------------------------------
 
// ВОТ ЭТУ ФУНКЦИЮ И ХОЧЕТСЯ ПЕРЕДЕЛАТЬ НА ТАБЛИЧНЫЙ СПОСОБ
 
// вычислить CRC для очередного байта
// вход:  b - байт
//        pCRC - указатель на CRC
// выход: обновленное значение CRC
 
void CRC32Update(PDWORD_DATA pCRC, BYTE b)
{
    pCRC->d = ((pCRC->d << 8) | b) ^ Crc32Table[(pCRC->d >> 24) & 0xFF];
 
#if 0
    BYTE  FlagHiBitCRC;
    BYTE  i;
 
    // цикл по числу бит в байте
    for (i = 0; i < 8; i++)
    {
        FlagHiBitCRC = pCRC->b[3] & 0x80;  // запомнить старший бит CRC[3]: TRUE - бит=1, FALSE - бит=0
 
        pCRC->d <<= 1;  // рабочий регистр сдвинуть влево / в CRC[0] младший бит стал =0
 
        // суть действия: перенести старший бит b в младший бит CRC[0] (неважно: он =0 или =1)
        if (b & 0x80)  // если старший бит b =1
            pCRC->b[0] |= 0x01;  // перенести его в младший бит CRC[0]
 
        if (FlagHiBitCRC)  // флаг старшего бита =1
            pCRC->d ^= CRC32_POLYNOMIAL;  // XOR
 
        b <<= 1;
    }
#endif
 
    // печать для проверки CRC после каждого байта
    //printf("%02X %02X %02X %02X" LF,
    //  pCRC->b[3], pCRC->b[2], pCRC->b[1], pCRC->b[0]);
}
 
// -------------------------------------------
 
// вычислить CRC для блока данных
// вход:  pBuffer - указатель на блок данных
//        BlockSize - длина блока в байтах
//        pCRC - указатель на CRC
// выход: обновленное значение CRC
 
void CRC32UpdateBlock(PDWORD_DATA pCRC, CONST BYTE* pBuffer, DWORD BlockSize)
{
    while (BlockSize)
    {
        CRC32Update(pCRC, *pBuffer);
        pBuffer++;
        BlockSize--;
    }
}
 
// -------------------------------------------
 
// финализировать конечное значение CRC после подсчета
// вход:  pCRC - указатель на CRC
// выход: нет
 
void CRC32Done(PDWORD_DATA pCRC)
{
 
}
 
// -------------------------------------------

Я там внёс кое-какие правки, не относящиеся к сути вопроса:
- по поводу POSIX-функций. А то компилятор ругался.
- и обошёл ввод имени файла из командной строки для удобства отладки.

В коде остался кое-какой мусор - тоже можно убрать. Пока оставил, если править придётся.

@XRS · 07.12.2019, 11:35 **[ТС]**

L0M
Спасибо за ответ! Сейчас компьютер разобран, сложно посмотреть. Проанализирую и отвечу. Спасибо вам!

@XRS · 10.12.2019, 10:43 **[ТС]**

L0M
Хочу вам выразить огромную благодарность за помощь! Ваше решение оказалось верным. Я проделал эксперимент - с помощью любимого FAR-а собрал имена к ~27000 файлов на ~32 Гб (через временную панель), создал 2 .bat файла (старая и новая версии), запустил, сравнил результаты. Результат сравнения – совпадает полностью (за исключением файлов более 4 Гб, т.к. функция filelength не дает длину для таких файлов и ее надо заменить на GetFileInformationByHandle). Программа ускорилась в 4 раза.

Я никогда не занимался алгоритмами CRC, и насколько понял, генерация таблицы зависит только от полинома (она полностью идентична тому, что в исходнике от WMAX). Поэтому у меня такие вопросы:

Как вы пришли к этой формуле:

C++

1	crc = ((crc << 8) \| b) ^ Crc32Table[(crc >> 24) & 0xFF];

в сравнении алгоритм WMAX:

C++

1	crc = (crc << 8) ^ Crc32Table[((crc >> 24) ^ b) & 0xFF];

Может быть у вас есть какая тот толковая литература с примерами? Или ссылки. У меня есть этот W. Wesley Peterson в переводе, но там нет логических схем и много математики. Другие статьи разбирают одно и то же, и авторы не сильно вникают в суть.

@L0M · 10.12.2019, 17:46

XRS, рад, что у вас всё заработало нормально. Я тоже никогда не занимался алгоритмами CRC, и решение было получено скорее методами реверс-инжиниринга, чем математическим анализом алгоритмов. Ну и почитал, конечно.

К такой формуле пришёл исходя из того, что, скорее всего, алгоритм в вашей программе очень старый и надо искать что-то достаточно простое из начала разработки алгоритмов CRC. Почитал Википедию, посмотрел и поэкспериментировал с реализациями из Викиучебника, почитал статью Ross N. Williams Элементарное руководство по CRC-алгоритмам обнаружения ошибок (сильно помогла, рекомендую). Ну и потом паззл сложился.

Кстати, у меня не только эта формула изменена, но и сгенерирована новая таблица. Одно без другого работать не будет.

@XRS · 12.12.2019, 11:17 **[ТС]**

L0M
Викиучебник я смотрел. Смутило то, что в этом алгоритме схема иная. Но оказалось, что таблица приведенная вами идентична тем, которые для этого полинома в современных алгоритмах. Я проверил. Кстати за "Ross N. Williams" спасибо, пригодится.

Продолжая тему. В конечном итоге я хотел сделать вот что: для обычного CRC32 (ZIP,RAR) у меня есть реализация, в которой таблица состоит из 16 элементов DWORD, а входной байт разбивается на 2 ниббла и сдвиги там по 4 разряда. Этот метод медленнее, чем тот, где таблица из 256 элементов, но экономит память (таблица всего 16*4 = 64 байта).

Потратил полдня и нашел решение (очевидно как и вы - методом реверсного анализа). Сначала воспользовался алгоритмом, который сдвигает побитно. Посмотрел какое значение должно получаться после 4, 8, 12, 16, 20 сдвигов, записал. Потом стал смотреть (исходя из вашей формулы) что (какой элемент из 256-элементной таблицы) должно браться, чтобы на определенный входной ниббл (а их 16 вариантов) получить нужное значение. Потом осмыслил то, какие значение должны быть в этой маленькой таблице и в конце концов все заработало!

Так что привожу этот пример, может быть кому то пригодится:

C

// это таблица - это первые 16 элементов из 256-элементной таблицы (подряд)
const DWORD Crc32Table16[16] = {
   0x00000000, 0x04C11DB7, 0x09823B6E, 0x0D4326D9,
   0x130476DC, 0x17C56B6B, 0x1A864DB2, 0x1E475005,
   0x2608EDB8, 0x22C9F00F, 0x2F8AD6D6, 0x2B4BCB61,
   0x350C9B64, 0x31CD86D3, 0x3C8EA00A, 0x384FBDBD
};
 
// ------------------------------------------------------
 
#define  LF  "\n"
 
// генерация таблицы из 16 элементов (вывод на stdout)
// Crc32Table16[16] - таблица
 
void CRC32_GenTable16 (void)
{
WORD   i,k;
BYTE   bit;
DWORD  crc;
 
   printf ("const DWORD Crc32Table16[16] = {" LF);
   k = 0;
   for (i=0; i<256; i++)
   {
      if ((i < 16) && (i % 4 == 0))
         printf ("  ");  // отступ
      crc = (i << 24);
      for (bit=0; bit<8; bit++)
      {
         if (crc & 0x80000000UL)  crc = (crc << 1) ^ CRC32_POLYNOMIAL;
         else                     crc = (crc << 1);
      }
      // после цикла по bit записывать(выводить) в таблицу
      if (i < 16)
      {
         //Crc32Table16[k] = crc;  k++;
         if (i != 15)  printf (" 0x%08lX,", crc);
         else          printf (" 0x%08lX",  crc);
         if ((i + 1) % 4 == 0)
            printf (LF);  // перевод строки
      }
   }
   printf ("};" LF);
}
 
// ------------------------------------------------------
 
// вычислить CRC для байта данных (фрагмент, без оптимизаций)
DWORD  crc;
BYTE  Index;
 
      // b - входной байт
      // если таблица из 16 элементов
      // первым обработать старший ниббл 'b' (т.к. сдвиги влево)
      Index = (BYTE)(crc >> 28);
      crc = Crc32Table16[Index]  ^  ((crc << 4) | (b >> 4));
      // обработать младший ниббл
      Index = (BYTE)(crc >> 28);
      crc = Crc32Table16[Index]  ^  ((crc << 4) | (b & 0xF));

@L0M · 12.12.2019, 22:23

XRS, вполне достойно. Единственно, вы отрезали определение символа CRC32_POLYNOMIAL. Хотя, конечно из таблицы понятно какой был использован полином.

@XRS · 13.12.2019, 09:27 **[ТС]**

Сообщение от L0M

вы отрезали определение символа CRC32_POLYNOMIAL

Но оно есть в вашем ответе выше

C++

1	#define CRC32_POLYNOMIAL 0x04C11DB7UL

а т.к. вся эта тема про один и тот же алгоритм, значит, и полином тот же.

@XRS 219 / 16 / 0 Регистрация: 15.08.2016 Сообщений: 39
	07.12.2019, 11:35 [ТС]	3
	L0M Спасибо за ответ! Сейчас компьютер разобран, сложно посмотреть. Проанализирую и отвечу. Спасибо вам! 0

@L0M Мозгоправ 1742 / 1036 / 468 Регистрация: 01.10.2018 Сообщений: 2,138 Записей в блоге: 2
	10.12.2019, 17:46	5
	XRS, рад, что у вас всё заработало нормально. Я тоже никогда не занимался алгоритмами CRC, и решение было получено скорее методами реверс-инжиниринга, чем математическим анализом алгоритмов. Ну и почитал, конечно. К такой формуле пришёл исходя из того, что, скорее всего, алгоритм в вашей программе очень старый и надо искать что-то достаточно простое из начала разработки алгоритмов CRC. Почитал Википедию, посмотрел и поэкспериментировал с реализациями из Викиучебника, почитал статью Ross N. Williams Элементарное руководство по CRC-алгоритмам обнаружения ошибок (сильно помогла, рекомендую). Ну и потом паззл сложился. Кстати, у меня не только эта формула изменена, но и сгенерирована новая таблица. Одно без другого работать не будет. 0

@L0M Мозгоправ 1742 / 1036 / 468 Регистрация: 01.10.2018 Сообщений: 2,138 Записей в блоге: 2
	12.12.2019, 22:23	7
	XRS, вполне достойно. Единственно, вы отрезали определение символа CRC32_POLYNOMIAL. Хотя, конечно из таблицы понятно какой был использован полином. 0

	13.12.2019, 09:27

Опции темы

Нужно переделать алгоритм вычисления CRC32 табличным способом

Решение