FSoE: Как устроены таблицы CRC?

Протокол FSoE (Functional Safety over EtherCAT) использует 16-битный CRC для защиты своих защитных сообщений. Реализации обычно опираются на две предвычисленные таблицы поиска по 256 элементов, традиционно называемые CRC16_TABLE и CRC16_TABLE2. В этом посте подробно объясняется, как именно эти таблицы выводятся из полинома CRC — никаких введённых вручную «магических» констант, только полином и алгоритм.

Полином

CRC для FSoE построен на 17-битном полиноме

$$ P(x) = x^{16} + x^{13} + x^{12} + x^{11} + x^{8} + x^{7} + x^{5} + x^{4} + x^{2} + x + 1 $$

который, упакованный как шестнадцатеричное значение с неявным членом $x^{16}$, равен 0x139B7. 16-битное представление, используемое внутри сдвигового регистра (полином без члена $x^{16}$), равно 0x39B7.

CRC обрабатывается в направлении MSB-first (так называемое «нормальное», или неотражённое, направление): каждый бит сообщения берётся со старшего конца рабочего регистра, а полином XOR-ится всякий раз, когда бит, выдвигаемый из вершины, равен 1.

Что такое элемент таблицы поиска CRC

Побайтовая таблица поиска CRC позволяет обрабатывать целый байт (8 бит) одним обращением к таблице вместо восьми отдельных битовых сдвигов. Для CRC в направлении MSB-first шириной $W = 16$ элемент для значения байта $i$ — это остаток от деления полинома

$$ \text{table}[i] = \left( i \cdot x^{W + 8k} \right) \bmod P(x) $$

где $k$ задаёт позицию байта внутри многобайтовой группы, для которой предназначена таблица:

Множитель $x^{W} = x^{16}$ учитывает 16-битную ширину регистра CRC (остаток имеет ширину 16 бит).
Множитель $x^{8k}$ учитывает, что байт смещён на $k$ байтовых позиций вправо (в сторону младших разрядов) внутри группы, поэтому требуется дополнительно сократить $8k$ битовых позиций.

Вычислительно это реализуется загрузкой $i$ в старший байт 16-битного регистра ($\text{crc} = i \ll 8$) и последующим выполнением $8 + 8k$ левых сдвигов, причём при каждом сдвиге полином XOR-ится в регистр, если установлен бит 15 (бит, который вот-вот покинет вершину):

$$ \text{crc} \gets \begin{cases} (\text{crc} \ll 1) \oplus \texttt{0x39B7} & \text{if } \text{crc} \mathbin{\&} \texttt{0x8000} \\ \text{crc} \ll 1 & \text{otherwise} \end{cases} $$

Это в точности деление «уголком» $i \cdot x^{8+8k}$ на $P(x)$ с сохранением только 16-битного остатка.

Две таблицы FSoE

Реализация FSoE использует две таблицы, соответствующие двум разным значениям $k$:

`CRC16_TABLE` — обычная побайтовая таблица ($k = 0$)

$$ \text{CRC16\_TABLE}[i] = \left( i \cdot x^{16} \right) \bmod P(x) $$

Вычисляется 8 левыми сдвигами значения $i \ll 8$. Это стандартная таблица поиска, используемая для обновления CRC по одному байту за раз:

$$ \text{crc} \gets (\text{crc} \ll 8) \oplus \text{CRC16\_TABLE}[\text{byte}] $$

`CRC16_TABLE2` — таблица для slice-by-4 ($k = 3$)

$$ \text{CRC16\_TABLE2}[i] = \left( i \cdot x^{40} \right) \bmod P(x) $$

Вычисляется 32 левыми сдвигами значения $i \ll 8$ (поскольку $8 + 8 \cdot 3 = 32$). Это таблица slice-by-4 для младшего байта 4-байтовой группы. Эквивалентно, это результат четырёхкратного применения обычного поиска по CRC16_TABLE, начиная с байта $i$, — то есть обработки байта $i$ с последующими тремя нулевыми байтами:

$$ \text{CRC16\_TABLE2}[i] = \underbrace{\text{process}(\ldots\text{process}(\text{process}(i \ll 8) \ll 8) \ll 8)}_{4 \text{ lookups}} $$

На шаге обновления slice-by-4, обрабатывающем сразу четыре байта, CRC обновляется так:

$$ \text{crc} \gets \text{CRC16\_TABLE2}[\text{crc}_{\text{lo}} \oplus b_0] \oplus \text{CRC16\_TABLE}[\text{crc}_{\text{hi}} \oplus b_1] \oplus \ldots $$

где $b_0$ — младший входной байт (тот, которому требуется наибольшее дополнительное сокращение, поэтому $k=3$).

Программа-генератор

Следующая программа на C генерирует обе таблицы из полинома 0x39B7 и выводит их в виде исходного кода на C. Ядром является единственная функция table_entry(i, shifts), выполняющая описанное выше полиномиальное деление «уголком» в направлении MSB-first. CRC16_TABLE строится с shifts = 8 ($k=0$), а CRC16_TABLE2 — с shifts = 32 ($k=3$).

GenTables.c

/*
 * GenTables.c
 * ============
 *
 * Программа-генератор таблиц поиска CRC-16 для FSoE
 * (Functional Safety over EtherCAT).
 *
 * После компиляции и запуска эта программа выводит исходный код на C для
 * второго файла (Tables.c), содержащего две 16-битные таблицы поиска по
 * 256 элементов. Таблицы выводятся исключительно из полинома CRC; в
 * сгенерированном выводе нет никаких введённых вручную констант.
 *
 *
 * CRC
 * --------
 *
 * CRC для FSoE — это 16-битный CRC, использующий 17-битный полином
 *
 *     P(x) = x^16 + x^13 + x^12 + x^11 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1
 *
 * который в упакованной шестнадцатеричной форме (без неявного члена x^16)
 * равен
 *
 *     0x39B7   (16 бит)
 *
 * или, с учётом члена x^16,
 *
 *     0x139B7  (17 бит).
 *
 * CRC обрабатывается в направлении MSB-first (иногда называемом «нормальным»
 * или «неотражённым»): каждый бит сообщения берётся со старшего конца
 * рабочего регистра, а полином XOR-ится, когда выдвигаемый бит равен 1.
 *
 *
 * Как строятся таблицы
 * ---------------------------
 *
 * Таблица поиска CRC позволяет обрабатывать целый байт (8 бит) одним
 * обращением к таблице вместо 8 отдельных битовых сдвигов. Для CRC в
 * направлении MSB-first элемент для значения байта `i` — это остаток от
 * деления полинома
 *
 *     table[i] = ( i * x^(16 + 8*k) ) mod P(x)
 *
 * где `k` задаёт позицию байта внутри многобайтовой группы, для которой
 * предназначена таблица. Множитель x^16 учитывает 16-битную ширину регистра
 * CRC (остаток имеет ширину 16 бит), а множитель x^(8*k) учитывает, что
 * байт смещён на `k` байтовых позиций вправо (в сторону младших разрядов)
 * внутри группы, поэтому требуется дополнительно сократить `8*k` битовых
 * позиций.
 *
 * Вычислительно это реализуется загрузкой `i` в старший байт 16-битного
 * регистра (crc = i << 8) и последующим выполнением `8 + 8*k` левых
 * сдвигов, причём при каждом сдвиге полином XOR-ится в регистр, если бит,
 * который вот-вот покинет вершину (бит 15), установлен:
 *
 *     for (n = 0; n < 8 + 8*k; n++)
 *         crc = (crc & 0x8000) ? ((crc << 1) ^ POLY) : (crc << 1);
 *
 * Здесь строятся две таблицы:
 *
 *   CRC16_TABLE   (k = 0):  table[i] = (i * x^16) mod P    --  8 сдвигов
 *       Это обычная побайтовая таблица поиска. Используется для обновления
 *       CRC по одному байту за раз:
 *           crc = (crc << 8) ^ CRC16_TABLE[byte];
 *
 *   CRC16_TABLE2  (k = 3):  table[i] = (i * x^40) mod P    -- 32 сдвига
 *       Это таблица slice-by-4 для младшего байта 4-байтовой группы.
 *       Эквивалентно, это результат четырёхкратного применения обычного
 *       поиска по таблице, начиная с байта `i` (т.е. обработки байта `i` с
 *       последующими тремя нулевыми байтами). Используется на шаге
 *       обновления slice-by-4, обрабатывающем сразу четыре байта:
 *           crc ^= (input32 & 0xFF);                       // внести
 *           crc  = CRC16_TABLE2[crc & 0xFF]                // младший байт
 *                ^ CRC16_TABLE [(input32 >> 8)  & 0xFF]    // ...затем
 *                ^ <slice k=1 table>[(input32 >> 16) & 0xFF]   // оставшиеся
 *                ^ <slice k=2 table>[(input32 >> 24) & 0xFF]   // байты.
 *       (Для реализации FSoE требуются только CRC16_TABLE и CRC16_TABLE2;
 *       таблицы срезов k=1 и k=2 здесь не генерируются.)
 *
 * Сборка и запуск:
 *     cc -std=c99 -O2 -o GenTables GenTables.c
 *     ./GenTables > Tables.c
 */

#include <stdint.h>
#include <stdio.h>

/* Младшие 16 бит полинома 0x139B7 (член x^16 неявный). */
#define POLY 0x39B7U

/*
 * Вычисление одного элемента таблицы CRC-16 в направлении MSB-first.
 *
 *   i      : значение байта (0..255), используемое как индекс таблицы.
 *   shifts : количество левых сдвигов = 8 + 8*k, где k — позиция байта
 *            внутри 4-байтового среза (k=0 -> 8 сдвигов, k=3 ->
 *            32 сдвига).
 *
 * Байт помещается в старший октет 16-битного регистра и сдвигается влево
 * `shifts` раз. Всякий раз, когда перед сдвигом установлен старший бит
 * (бит 15), после сдвига полином XOR-ится в регистр — это в точности
 * деление «уголком» (i * x^(8+shifts)) на P(x) с сохранением только
 * 16-битного остатка.
 */
static uint16_t table_entry(uint8_t i, int shifts)
{
    uint16_t crc = (uint16_t)i << 8;
    int n;
    for (n = 0; n < shifts; ++n) {
        if (crc & 0x8000U)
            crc = (uint16_t)((crc << 1) ^ POLY);
        else
            crc = (uint16_t)(crc << 1);
    }
    return crc;
}

/*
 * Заполнение 256-элементной таблицы путём независимого вычисления каждого
 * элемента. `shifts` выбирает, какая таблица среза строится (8 для k=0,
 * 32 для k=3).
 */
static void build_table(uint16_t table[256], int shifts)
{
    int i;
    for (i = 0; i < 256; ++i)
        table[i] = table_entry((uint8_t)i, shifts);
}

/* Вывод 256-элементной таблицы uint16_t как исходника на C, по 8 значений в строке. */
static void print_table(const char *name, const uint16_t table[256])
{
    int i;
    printf("const uint16_t %s[256] = {\n", name);
    for (i = 0; i < 256; i += 8) {
        printf("    0x%04X, 0x%04X, 0x%04X, 0x%04X, "
               "0x%04X, 0x%04X, 0x%04X, 0x%04X,\n",
               table[i],   table[i+1], table[i+2], table[i+3],
               table[i+4], table[i+5], table[i+6], table[i+7]);
    }
    printf("};\n");
}

int main(void)
{
    uint16_t table1[256]; /* k = 0: (i * x^16) mod P */
    uint16_t table2[256]; /* k = 3: (i * x^40) mod P */

    build_table(table1, 8);   /* обычная побайтовая таблица        */
    build_table(table2, 32);  /* slice-by-4, младший байт          */

    /*
     * Вывод второго файла исходного кода (Tables.c). Заголовочный комментарий,
     * записанный здесь, точно документирует, что представляют собой таблицы
     * и как они связаны с полиномом, чтобы файл Tables.c был самодостаточным.
     */
    printf("/*\n");
    printf(" * Tables.c  (auto-generated by GenTables.c -- do not edit)\n");
    printf(" * =======================================================\n");
    printf(" *\n");
    printf(" * Две 16-битные таблицы поиска CRC по 256 элементов для\n");
    printf(" * CRC-16 FSoE (Functional Safety over EtherCAT).\n");
    printf(" *\n");
    printf(" * Полином\n");
    printf(" * -----------\n");
    printf(" *   P(x) = x^16 + x^13 + x^12 + x^11 + x^8 + x^7 + x^5\n");
    printf(" *          + x^4 + x^2 + x + 1\n");
    printf(" *   упакованный (без члена x^16): 0x39B7\n");
    printf(" *   упакованный (с членом x^16):  0x139B7\n");
    printf(" *\n");
    printf(" * Направление: MSB-first (\"нормальное\", неотражённое).\n");
    printf(" *\n");
    printf(" * Построение таблиц\n");
    printf(" * ------------------\n");
    printf(" * Каждый элемент — это остаток от деления полинома:\n");
    printf(" *\n");
    printf(" *   table[i] = ( i * x^(16 + 8*k) ) mod P(x)\n");
    printf(" *\n");
    printf(" * вычисляемый загрузкой i в старший байт 16-битного\n");
    printf(" * регистра (crc = i << 8) и выполнением 8 + 8*k левых\n");
    printf(" * сдвигов, с XOR-ом полинома всякий раз, когда перед сдвигом\n");
    printf(" * установлен бит 15:\n");
    printf(" *\n");
    printf(" *   for (n = 0; n < 8 + 8*k; n++)\n");
    printf(" *       crc = (crc & 0x8000) ? ((crc << 1) ^ 0x39B7)\n");
    printf(" *                             :  (crc << 1);\n");
    printf(" *\n");
    printf(" * Таблицы в этом файле\n");
    printf(" * -------------------\n");
    printf(" * CRC16_TABLE   (k = 0,  8 сдвигов):\n");
    printf(" *   table[i] = (i * x^16) mod P.\n");
    printf(" *   Обычная побайтовая таблица поиска. Используется для\n");
    printf(" *   обновления CRC по одному байту за раз:\n");
    printf(" *       crc = (crc << 8) ^ CRC16_TABLE[byte];\n");
    printf(" *\n");
    printf(" * CRC16_TABLE2  (k = 3, 32 сдвига):\n");
    printf(" *   table[i] = (i * x^40) mod P.\n");
    printf(" *   Таблица slice-by-4 для младшего байта 4-байтовой\n");
    printf(" *   группы; эквивалентно — результат четырёхкратного\n");
    printf(" *   применения обычного поиска по таблице, начиная с байта i\n");
    printf(" *   (байт i с последующими тремя нулевыми байтами).\n");
    printf(" */\n");
    printf("\n");
    printf("#include <stdint.h>\n");
    printf("\n");

    print_table("CRC16_TABLE",  table1);
    printf("\n");
    print_table("CRC16_TABLE2", table2);

    return 0;
}

/*
 * GenTables.c
 * ============
 *
 * Программа-генератор таблиц поиска CRC-16 для FSoE
 * (Functional Safety over EtherCAT).
 *
 * После компиляции и запуска эта программа выводит исходный код на C для
 * второго файла (Tables.c), содержащего две 16-битные таблицы поиска по
 * 256 элементов. Таблицы выводятся исключительно из полинома CRC; в
 * сгенерированном выводе нет никаких введённых вручную констант.
 *
 *
 * CRC
 * --------
 *
 * CRC для FSoE — это 16-битный CRC, использующий 17-битный полином
 *
 *     P(x) = x^16 + x^13 + x^12 + x^11 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1
 *
 * который в упакованной шестнадцатеричной форме (без неявного члена x^16)
 * равен
 *
 *     0x39B7   (16 бит)
 *
 * или, с учётом члена x^16,
 *
 *     0x139B7  (17 бит).
 *
 * CRC обрабатывается в направлении MSB-first (иногда называемом «нормальным»
 * или «неотражённым»): каждый бит сообщения берётся со старшего конца
 * рабочего регистра, а полином XOR-ится, когда выдвигаемый бит равен 1.
 *
 *
 * Как строятся таблицы
 * ---------------------------
 *
 * Таблица поиска CRC позволяет обрабатывать целый байт (8 бит) одним
 * обращением к таблице вместо 8 отдельных битовых сдвигов. Для CRC в
 * направлении MSB-first элемент для значения байта `i` — это остаток от
 * деления полинома
 *
 *     table[i] = ( i * x^(16 + 8*k) ) mod P(x)
 *
 * где `k` задаёт позицию байта внутри многобайтовой группы, для которой
 * предназначена таблица. Множитель x^16 учитывает 16-битную ширину регистра
 * CRC (остаток имеет ширину 16 бит), а множитель x^(8*k) учитывает, что
 * байт смещён на `k` байтовых позиций вправо (в сторону младших разрядов)
 * внутри группы, поэтому требуется дополнительно сократить `8*k` битовых
 * позиций.
 *
 * Вычислительно это реализуется загрузкой `i` в старший байт 16-битного
 * регистра (crc = i << 8) и последующим выполнением `8 + 8*k` левых
 * сдвигов, причём при каждом сдвиге полином XOR-ится в регистр, если бит,
 * который вот-вот покинет вершину (бит 15), установлен:
 *
 *     for (n = 0; n < 8 + 8*k; n++)
 *         crc = (crc & 0x8000) ? ((crc << 1) ^ POLY) : (crc << 1);
 *
 * Здесь строятся две таблицы:
 *
 *   CRC16_TABLE   (k = 0):  table[i] = (i * x^16) mod P    --  8 сдвигов
 *       Это обычная побайтовая таблица поиска. Используется для обновления
 *       CRC по одному байту за раз:
 *           crc = (crc << 8) ^ CRC16_TABLE[byte];
 *
 *   CRC16_TABLE2  (k = 3):  table[i] = (i * x^40) mod P    -- 32 сдвига
 *       Это таблица slice-by-4 для младшего байта 4-байтовой группы.
 *       Эквивалентно, это результат четырёхкратного применения обычного
 *       поиска по таблице, начиная с байта `i` (т.е. обработки байта `i` с
 *       последующими тремя нулевыми байтами). Используется на шаге
 *       обновления slice-by-4, обрабатывающем сразу четыре байта:
 *           crc ^= (input32 & 0xFF);                       // внести
 *           crc  = CRC16_TABLE2[crc & 0xFF]                // младший байт
 *                ^ CRC16_TABLE [(input32 >> 8)  & 0xFF]    // ...затем
 *                ^ <slice k=1 table>[(input32 >> 16) & 0xFF]   // оставшиеся
 *                ^ <slice k=2 table>[(input32 >> 24) & 0xFF]   // байты.
 *       (Для реализации FSoE требуются только CRC16_TABLE и CRC16_TABLE2;
 *       таблицы срезов k=1 и k=2 здесь не генерируются.)
 *
 * Сборка и запуск:
 *     cc -std=c99 -O2 -o GenTables GenTables.c
 *     ./GenTables > Tables.c
 */

#include <stdint.h>
#include <stdio.h>

/* Младшие 16 бит полинома 0x139B7 (член x^16 неявный). */
#define POLY 0x39B7U

/*
 * Вычисление одного элемента таблицы CRC-16 в направлении MSB-first.
 *
 *   i      : значение байта (0..255), используемое как индекс таблицы.
 *   shifts : количество левых сдвигов = 8 + 8*k, где k — позиция байта
 *            внутри 4-байтового среза (k=0 -> 8 сдвигов, k=3 ->
 *            32 сдвига).
 *
 * Байт помещается в старший октет 16-битного регистра и сдвигается влево
 * `shifts` раз. Всякий раз, когда перед сдвигом установлен старший бит
 * (бит 15), после сдвига полином XOR-ится в регистр — это в точности
 * деление «уголком» (i * x^(8+shifts)) на P(x) с сохранением только
 * 16-битного остатка.
 */
static uint16_t table_entry(uint8_t i, int shifts)
{
    uint16_t crc = (uint16_t)i << 8;
    int n;
    for (n = 0; n < shifts; ++n) {
        if (crc & 0x8000U)
            crc = (uint16_t)((crc << 1) ^ POLY);
        else
            crc = (uint16_t)(crc << 1);
    }
    return crc;
}

/*
 * Заполнение 256-элементной таблицы путём независимого вычисления каждого
 * элемента. `shifts` выбирает, какая таблица среза строится (8 для k=0,
 * 32 для k=3).
 */
static void build_table(uint16_t table[256], int shifts)
{
    int i;
    for (i = 0; i < 256; ++i)
        table[i] = table_entry((uint8_t)i, shifts);
}

/* Вывод 256-элементной таблицы uint16_t как исходника на C, по 8 значений в строке. */
static void print_table(const char *name, const uint16_t table[256])
{
    int i;
    printf("const uint16_t %s[256] = {\n", name);
    for (i = 0; i < 256; i += 8) {
        printf("    0x%04X, 0x%04X, 0x%04X, 0x%04X, "
               "0x%04X, 0x%04X, 0x%04X, 0x%04X,\n",
               table[i],   table[i+1], table[i+2], table[i+3],
               table[i+4], table[i+5], table[i+6], table[i+7]);
    }
    printf("};\n");
}

int main(void)
{
    uint16_t table1[256]; /* k = 0: (i * x^16) mod P */
    uint16_t table2[256]; /* k = 3: (i * x^40) mod P */

    build_table(table1, 8);   /* обычная побайтовая таблица        */
    build_table(table2, 32);  /* slice-by-4, младший байт          */

    /*
     * Вывод второго файла исходного кода (Tables.c). Заголовочный комментарий,
     * записанный здесь, точно документирует, что представляют собой таблицы
     * и как они связаны с полиномом, чтобы файл Tables.c был самодостаточным.
     */
    printf("/*\n");
    printf(" * Tables.c  (auto-generated by GenTables.c -- do not edit)\n");
    printf(" * =======================================================\n");
    printf(" *\n");
    printf(" * Две 16-битные таблицы поиска CRC по 256 элементов для\n");
    printf(" * CRC-16 FSoE (Functional Safety over EtherCAT).\n");
    printf(" *\n");
    printf(" * Полином\n");
    printf(" * -----------\n");
    printf(" *   P(x) = x^16 + x^13 + x^12 + x^11 + x^8 + x^7 + x^5\n");
    printf(" *          + x^4 + x^2 + x + 1\n");
    printf(" *   упакованный (без члена x^16): 0x39B7\n");
    printf(" *   упакованный (с членом x^16):  0x139B7\n");
    printf(" *\n");
    printf(" * Направление: MSB-first (\"нормальное\", неотражённое).\n");
    printf(" *\n");
    printf(" * Построение таблиц\n");
    printf(" * ------------------\n");
    printf(" * Каждый элемент — это остаток от деления полинома:\n");
    printf(" *\n");
    printf(" *   table[i] = ( i * x^(16 + 8*k) ) mod P(x)\n");
    printf(" *\n");
    printf(" * вычисляемый загрузкой i в старший байт 16-битного\n");
    printf(" * регистра (crc = i << 8) и выполнением 8 + 8*k левых\n");
    printf(" * сдвигов, с XOR-ом полинома всякий раз, когда перед сдвигом\n");
    printf(" * установлен бит 15:\n");
    printf(" *\n");
    printf(" *   for (n = 0; n < 8 + 8*k; n++)\n");
    printf(" *       crc = (crc & 0x8000) ? ((crc << 1) ^ 0x39B7)\n");
    printf(" *                             :  (crc << 1);\n");
    printf(" *\n");
    printf(" * Таблицы в этом файле\n");
    printf(" * -------------------\n");
    printf(" * CRC16_TABLE   (k = 0,  8 сдвигов):\n");
    printf(" *   table[i] = (i * x^16) mod P.\n");
    printf(" *   Обычная побайтовая таблица поиска. Используется для\n");
    printf(" *   обновления CRC по одному байту за раз:\n");
    printf(" *       crc = (crc << 8) ^ CRC16_TABLE[byte];\n");
    printf(" *\n");
    printf(" * CRC16_TABLE2  (k = 3, 32 сдвига):\n");
    printf(" *   table[i] = (i * x^40) mod P.\n");
    printf(" *   Таблица slice-by-4 для младшего байта 4-байтовой\n");
    printf(" *   группы; эквивалентно — результат четырёхкратного\n");
    printf(" *   применения обычного поиска по таблице, начиная с байта i\n");
    printf(" *   (байт i с последующими тремя нулевыми байтами).\n");
    printf(" */\n");
    printf("\n");
    printf("#include <stdint.h>\n");
    printf("\n");

    print_table("CRC16_TABLE",  table1);
    printf("\n");
    print_table("CRC16_TABLE2", table2);

    return 0;
}

Соберите и запустите:

Build commands

cc -std=c99 -O2 -o GenTables GenTables.c
./GenTables > Tables.c

cc -std=c99 -O2 -o GenTables GenTables.c
./GenTables > Tables.c

Сгенерированные таблицы

Вывод генератора — следующий самодостаточный файл исходного кода на C. Обе таблицы точно совпадают с эталонными таблицами FSoE — каждый из 256 элементов в каждой таблице.

Tables.c

/*
 * Tables.c  (auto-generated by GenTables.c -- do not edit)
 * =======================================================
 *
 * Две 16-битные таблицы поиска CRC по 256 элементов для
 * CRC-16 FSoE (Functional Safety over EtherCAT).
 *
 * Полином
 * -----------
 *   P(x) = x^16 + x^13 + x^12 + x^11 + x^8 + x^7 + x^5
 *          + x^4 + x^2 + x + 1
 *   упакованный (без члена x^16): 0x39B7
 *   упакованный (с членом x^16):  0x139B7
 *
 * Направление: MSB-first ("нормальное", неотражённое).
 *
 * Построение таблиц
 * ------------------
 * Каждый элемент — это остаток от деления полинома:
 *
 *   table[i] = ( i * x^(16 + 8*k) ) mod P(x)
 *
 * вычисляемый загрузкой i в старший байт 16-битного
 * регистра (crc = i << 8) и выполнением 8 + 8*k левых
 * сдвигов, с XOR-ом полинома всякий раз, когда перед сдвигом
 * установлен бит 15:
 *
 *   for (n = 0; n < 8 + 8*k; n++)
 *       crc = (crc & 0x8000) ? ((crc << 1) ^ 0x39B7)
 *                             :  (crc << 1);
 *
 * Таблицы в этом файле
 * -------------------
 * CRC16_TABLE   (k = 0,  8 сдвигов):
 *   table[i] = (i * x^16) mod P.
 *   Обычная побайтовая таблица поиска. Используется для
 *   обновления CRC по одному байту за раз:
 *       crc = (crc << 8) ^ CRC16_TABLE[byte];
 *
 * CRC16_TABLE2  (k = 3, 32 сдвига):
 *   table[i] = (i * x^40) mod P.
 *   Таблица slice-by-4 для младшего байта 4-байтовой
 *   группы; эквивалентно — результат четырёхкратного
 *   применения обычного поиска по таблице, начиная с байта i
 *   (байт i с последующими тремя нулевыми байтами).
 */

#include <stdint.h>

const uint16_t CRC16_TABLE[256] = {
    0x0000, 0x39B7, 0x736E, 0x4AD9, 0xE6DC, 0xDF6B, 0x95B2, 0xAC05,
    0xF40F, 0xCDB8, 0x8761, 0xBED6, 0x12D3, 0x2B64, 0x61BD, 0x580A,
    0xD1A9, 0xE81E, 0xA2C7, 0x9B70, 0x3775, 0x0EC2, 0x441B, 0x7DAC,
    0x25A6, 0x1C11, 0x56C8, 0x6F7F, 0xC37A, 0xFACD, 0xB014, 0x89A3,
    0x9AE5, 0xA352, 0xE98B, 0xD03C, 0x7C39, 0x458E, 0x0F57, 0x36E0,
    0x6EEA, 0x575D, 0x1D84, 0x2433, 0x8836, 0xB181, 0xFB58, 0xC2EF,
    0x4B4C, 0x72FB, 0x3822, 0x0195, 0xAD90, 0x9427, 0xDEFE, 0xE749,
    0xBF43, 0x86F4, 0xCC2D, 0xF59A, 0x599F, 0x6028, 0x2AF1, 0x1346,
    0x0C7D, 0x35CA, 0x7F13, 0x46A4, 0xEAA1, 0xD316, 0x99CF, 0xA078,
    0xF872, 0xC1C5, 0x8B1C, 0xB2AB, 0x1EAE, 0x2719, 0x6DC0, 0x5477,
    0xDDD4, 0xE463, 0xAEBA, 0x970D, 0x3B08, 0x02BF, 0x4866, 0x71D1,
    0x29DB, 0x106C, 0x5AB5, 0x6302, 0xCF07, 0xF6B0, 0xBC69, 0x85DE,
    0x9698, 0xAF2F, 0xE5F6, 0xDC41, 0x7044, 0x49F3, 0x032A, 0x3A9D,
    0x6297, 0x5B20, 0x11F9, 0x284E, 0x844B, 0xBDFC, 0xF725, 0xCE92,
    0x4731, 0x7E86, 0x345F, 0x0DE8, 0xA1ED, 0x985A, 0xD283, 0xEB34,
    0xB33E, 0x8A89, 0xC050, 0xF9E7, 0x55E2, 0x6C55, 0x268C, 0x1F3B,
    0x18FA, 0x214D, 0x6B94, 0x5223, 0xFE26, 0xC791, 0x8D48, 0xB4FF,
    0xECF5, 0xD542, 0x9F9B, 0xA62C, 0x0A29, 0x339E, 0x7947, 0x40F0,
    0xC953, 0xF0E4, 0xBA3D, 0x838A, 0x2F8F, 0x1638, 0x5CE1, 0x6556,
    0x3D5C, 0x04EB, 0x4E32, 0x7785, 0xDB80, 0xE237, 0xA8EE, 0x9159,
    0x821F, 0xBBA8, 0xF171, 0xC8C6, 0x64C3, 0x5D74, 0x17AD, 0x2E1A,
    0x7610, 0x4FA7, 0x057E, 0x3CC9, 0x90CC, 0xA97B, 0xE3A2, 0xDA15,
    0x53B6, 0x6A01, 0x20D8, 0x196F, 0xB56A, 0x8CDD, 0xC604, 0xFFB3,
    0xA7B9, 0x9E0E, 0xD4D7, 0xED60, 0x4165, 0x78D2, 0x320B, 0x0BBC,
    0x1487, 0x2D30, 0x67E9, 0x5E5E, 0xF25B, 0xCBEC, 0x8135, 0xB882,
    0xE088, 0xD93F, 0x93E6, 0xAA51, 0x0654, 0x3FE3, 0x753A, 0x4C8D,
    0xC52E, 0xFC99, 0xB640, 0x8FF7, 0x23F2, 0x1A45, 0x509C, 0x692B,
    0x3121, 0x0896, 0x424F, 0x7BF8, 0xD7FD, 0xEE4A, 0xA493, 0x9D24,
    0x8E62, 0xB7D5, 0xFD0C, 0xC4BB, 0x68BE, 0x5109, 0x1BD0, 0x2267,
    0x7A6D, 0x43DA, 0x0903, 0x30B4, 0x9CB1, 0xA506, 0xEFDF, 0xD668,
    0x5FCB, 0x667C, 0x2CA5, 0x1512, 0xB917, 0x80A0, 0xCA79, 0xF3CE,
    0xABC4, 0x9273, 0xD8AA, 0xE11D, 0x4D18, 0x74AF, 0x3E76, 0x07C1,
};

const uint16_t CRC16_TABLE2[256] = {
    0x0000, 0x7648, 0xEC90, 0x9AD8, 0xE097, 0x96DF, 0x0C07, 0x7A4F,
    0xF899, 0x8ED1, 0x1409, 0x6241, 0x180E, 0x6E46, 0xF49E, 0x82D6,
    0xC885, 0xBECD, 0x2415, 0x525D, 0x2812, 0x5E5A, 0xC482, 0xB2CA,
    0x301C, 0x4654, 0xDC8C, 0xAAC4, 0xD08B, 0xA6C3, 0x3C1B, 0x4A53,
    0xA8BD, 0xDEF5, 0x442D, 0x3265, 0x482A, 0x3E62, 0xA4BA, 0xD2F2,
    0x5024, 0x266C, 0xBCB4, 0xCAFC, 0xB0B3, 0xC6FB, 0x5C23, 0x2A6B,
    0x6038, 0x1670, 0x8CA8, 0xFAE0, 0x80AF, 0xF6E7, 0x6C3F, 0x1A77,
    0x98A1, 0xEEE9, 0x7431, 0x0279, 0x7836, 0x0E7E, 0x94A6, 0xE2EE,
    0x68CD, 0x1E85, 0x845D, 0xF215, 0x885A, 0xFE12, 0x64CA, 0x1282,
    0x9054, 0xE61C, 0x7CC4, 0x0A8C, 0x70C3, 0x068B, 0x9C53, 0xEA1B,
    0xA048, 0xD600, 0x4CD8, 0x3A90, 0x40DF, 0x3697, 0xAC4F, 0xDA07,
    0x58D1, 0x2E99, 0xB441, 0xC209, 0xB846, 0xCE0E, 0x54D6, 0x229E,
    0xC070, 0xB638, 0x2CE0, 0x5AA8, 0x20E7, 0x56AF, 0xCC77, 0xBA3F,
    0x38E9, 0x4EA1, 0xD479, 0xA231, 0xD87E, 0xAE36, 0x34EE, 0x42A6,
    0x08F5, 0x7EBD, 0xE465, 0x922D, 0xE862, 0x9E2A, 0x04F2, 0x72BA,
    0xF06C, 0x8624, 0x1CFC, 0x6AB4, 0x10FB, 0x66B3, 0xFC6B, 0x8A23,
    0xD19A, 0xA7D2, 0x3D0A, 0x4B42, 0x310D, 0x4745, 0xDD9D, 0xABD5,
    0x2903, 0x5F4B, 0xC593, 0xB3DB, 0xC994, 0xBFDC, 0x2504, 0x534C,
    0x191F, 0x6F57, 0xF58F, 0x83C7, 0xF988, 0x8FC0, 0x1518, 0x6350,
    0xE186, 0x97CE, 0x0D16, 0x7B5E, 0x0111, 0x7759, 0xED81, 0x9BC9,
    0x7927, 0x0F6F, 0x95B7, 0xE3FF, 0x99B0, 0xEFF8, 0x7520, 0x0368,
    0x81BE, 0xF7F6, 0x6D2E, 0x1B66, 0x6129, 0x1761, 0x8DB9, 0xFBF1,
    0xB1A2, 0xC7EA, 0x5D32, 0x2B7A, 0x5135, 0x277D, 0xBDA5, 0xCBED,
    0x493B, 0x3F73, 0xA5AB, 0xD3E3, 0xA9AC, 0xDFE4, 0x453C, 0x3374,
    0xB957, 0xCF1F, 0x55C7, 0x238F, 0x59C0, 0x2F88, 0xB550, 0xC318,
    0x41CE, 0x3786, 0xAD5E, 0xDB16, 0xA159, 0xD711, 0x4DC9, 0x3B81,
    0x71D2, 0x079A, 0x9D42, 0xEB0A, 0x9145, 0xE70D, 0x7DD5, 0x0B9D,
    0x894B, 0xFF03, 0x65DB, 0x1393, 0x69DC, 0x1F94, 0x854C, 0xF304,
    0x11EA, 0x67A2, 0xFD7A, 0x8B32, 0xF17D, 0x8735, 0x1DED, 0x6BA5,
    0xE973, 0x9F3B, 0x05E3, 0x73AB, 0x09E4, 0x7FAC, 0xE574, 0x933C,
    0xD96F, 0xAF27, 0x35FF, 0x43B7, 0x39F8, 0x4FB0, 0xD568, 0xA320,
    0x21F6, 0x57BE, 0xCD66, 0xBB2E, 0xC161, 0xB729, 0x2DF1, 0x5BB9,
};

/*
 * Tables.c  (auto-generated by GenTables.c -- do not edit)
 * =======================================================
 *
 * Две 16-битные таблицы поиска CRC по 256 элементов для
 * CRC-16 FSoE (Functional Safety over EtherCAT).
 *
 * Полином
 * -----------
 *   P(x) = x^16 + x^13 + x^12 + x^11 + x^8 + x^7 + x^5
 *          + x^4 + x^2 + x + 1
 *   упакованный (без члена x^16): 0x39B7
 *   упакованный (с членом x^16):  0x139B7
 *
 * Направление: MSB-first ("нормальное", неотражённое).
 *
 * Построение таблиц
 * ------------------
 * Каждый элемент — это остаток от деления полинома:
 *
 *   table[i] = ( i * x^(16 + 8*k) ) mod P(x)
 *
 * вычисляемый загрузкой i в старший байт 16-битного
 * регистра (crc = i << 8) и выполнением 8 + 8*k левых
 * сдвигов, с XOR-ом полинома всякий раз, когда перед сдвигом
 * установлен бит 15:
 *
 *   for (n = 0; n < 8 + 8*k; n++)
 *       crc = (crc & 0x8000) ? ((crc << 1) ^ 0x39B7)
 *                             :  (crc << 1);
 *
 * Таблицы в этом файле
 * -------------------
 * CRC16_TABLE   (k = 0,  8 сдвигов):
 *   table[i] = (i * x^16) mod P.
 *   Обычная побайтовая таблица поиска. Используется для
 *   обновления CRC по одному байту за раз:
 *       crc = (crc << 8) ^ CRC16_TABLE[byte];
 *
 * CRC16_TABLE2  (k = 3, 32 сдвига):
 *   table[i] = (i * x^40) mod P.
 *   Таблица slice-by-4 для младшего байта 4-байтовой
 *   группы; эквивалентно — результат четырёхкратного
 *   применения обычного поиска по таблице, начиная с байта i
 *   (байт i с последующими тремя нулевыми байтами).
 */

#include <stdint.h>

const uint16_t CRC16_TABLE[256] = {
    0x0000, 0x39B7, 0x736E, 0x4AD9, 0xE6DC, 0xDF6B, 0x95B2, 0xAC05,
    0xF40F, 0xCDB8, 0x8761, 0xBED6, 0x12D3, 0x2B64, 0x61BD, 0x580A,
    0xD1A9, 0xE81E, 0xA2C7, 0x9B70, 0x3775, 0x0EC2, 0x441B, 0x7DAC,
    0x25A6, 0x1C11, 0x56C8, 0x6F7F, 0xC37A, 0xFACD, 0xB014, 0x89A3,
    0x9AE5, 0xA352, 0xE98B, 0xD03C, 0x7C39, 0x458E, 0x0F57, 0x36E0,
    0x6EEA, 0x575D, 0x1D84, 0x2433, 0x8836, 0xB181, 0xFB58, 0xC2EF,
    0x4B4C, 0x72FB, 0x3822, 0x0195, 0xAD90, 0x9427, 0xDEFE, 0xE749,
    0xBF43, 0x86F4, 0xCC2D, 0xF59A, 0x599F, 0x6028, 0x2AF1, 0x1346,
    0x0C7D, 0x35CA, 0x7F13, 0x46A4, 0xEAA1, 0xD316, 0x99CF, 0xA078,
    0xF872, 0xC1C5, 0x8B1C, 0xB2AB, 0x1EAE, 0x2719, 0x6DC0, 0x5477,
    0xDDD4, 0xE463, 0xAEBA, 0x970D, 0x3B08, 0x02BF, 0x4866, 0x71D1,
    0x29DB, 0x106C, 0x5AB5, 0x6302, 0xCF07, 0xF6B0, 0xBC69, 0x85DE,
    0x9698, 0xAF2F, 0xE5F6, 0xDC41, 0x7044, 0x49F3, 0x032A, 0x3A9D,
    0x6297, 0x5B20, 0x11F9, 0x284E, 0x844B, 0xBDFC, 0xF725, 0xCE92,
    0x4731, 0x7E86, 0x345F, 0x0DE8, 0xA1ED, 0x985A, 0xD283, 0xEB34,
    0xB33E, 0x8A89, 0xC050, 0xF9E7, 0x55E2, 0x6C55, 0x268C, 0x1F3B,
    0x18FA, 0x214D, 0x6B94, 0x5223, 0xFE26, 0xC791, 0x8D48, 0xB4FF,
    0xECF5, 0xD542, 0x9F9B, 0xA62C, 0x0A29, 0x339E, 0x7947, 0x40F0,
    0xC953, 0xF0E4, 0xBA3D, 0x838A, 0x2F8F, 0x1638, 0x5CE1, 0x6556,
    0x3D5C, 0x04EB, 0x4E32, 0x7785, 0xDB80, 0xE237, 0xA8EE, 0x9159,
    0x821F, 0xBBA8, 0xF171, 0xC8C6, 0x64C3, 0x5D74, 0x17AD, 0x2E1A,
    0x7610, 0x4FA7, 0x057E, 0x3CC9, 0x90CC, 0xA97B, 0xE3A2, 0xDA15,
    0x53B6, 0x6A01, 0x20D8, 0x196F, 0xB56A, 0x8CDD, 0xC604, 0xFFB3,
    0xA7B9, 0x9E0E, 0xD4D7, 0xED60, 0x4165, 0x78D2, 0x320B, 0x0BBC,
    0x1487, 0x2D30, 0x67E9, 0x5E5E, 0xF25B, 0xCBEC, 0x8135, 0xB882,
    0xE088, 0xD93F, 0x93E6, 0xAA51, 0x0654, 0x3FE3, 0x753A, 0x4C8D,
    0xC52E, 0xFC99, 0xB640, 0x8FF7, 0x23F2, 0x1A45, 0x509C, 0x692B,
    0x3121, 0x0896, 0x424F, 0x7BF8, 0xD7FD, 0xEE4A, 0xA493, 0x9D24,
    0x8E62, 0xB7D5, 0xFD0C, 0xC4BB, 0x68BE, 0x5109, 0x1BD0, 0x2267,
    0x7A6D, 0x43DA, 0x0903, 0x30B4, 0x9CB1, 0xA506, 0xEFDF, 0xD668,
    0x5FCB, 0x667C, 0x2CA5, 0x1512, 0xB917, 0x80A0, 0xCA79, 0xF3CE,
    0xABC4, 0x9273, 0xD8AA, 0xE11D, 0x4D18, 0x74AF, 0x3E76, 0x07C1,
};

const uint16_t CRC16_TABLE2[256] = {
    0x0000, 0x7648, 0xEC90, 0x9AD8, 0xE097, 0x96DF, 0x0C07, 0x7A4F,
    0xF899, 0x8ED1, 0x1409, 0x6241, 0x180E, 0x6E46, 0xF49E, 0x82D6,
    0xC885, 0xBECD, 0x2415, 0x525D, 0x2812, 0x5E5A, 0xC482, 0xB2CA,
    0x301C, 0x4654, 0xDC8C, 0xAAC4, 0xD08B, 0xA6C3, 0x3C1B, 0x4A53,
    0xA8BD, 0xDEF5, 0x442D, 0x3265, 0x482A, 0x3E62, 0xA4BA, 0xD2F2,
    0x5024, 0x266C, 0xBCB4, 0xCAFC, 0xB0B3, 0xC6FB, 0x5C23, 0x2A6B,
    0x6038, 0x1670, 0x8CA8, 0xFAE0, 0x80AF, 0xF6E7, 0x6C3F, 0x1A77,
    0x98A1, 0xEEE9, 0x7431, 0x0279, 0x7836, 0x0E7E, 0x94A6, 0xE2EE,
    0x68CD, 0x1E85, 0x845D, 0xF215, 0x885A, 0xFE12, 0x64CA, 0x1282,
    0x9054, 0xE61C, 0x7CC4, 0x0A8C, 0x70C3, 0x068B, 0x9C53, 0xEA1B,
    0xA048, 0xD600, 0x4CD8, 0x3A90, 0x40DF, 0x3697, 0xAC4F, 0xDA07,
    0x58D1, 0x2E99, 0xB441, 0xC209, 0xB846, 0xCE0E, 0x54D6, 0x229E,
    0xC070, 0xB638, 0x2CE0, 0x5AA8, 0x20E7, 0x56AF, 0xCC77, 0xBA3F,
    0x38E9, 0x4EA1, 0xD479, 0xA231, 0xD87E, 0xAE36, 0x34EE, 0x42A6,
    0x08F5, 0x7EBD, 0xE465, 0x922D, 0xE862, 0x9E2A, 0x04F2, 0x72BA,
    0xF06C, 0x8624, 0x1CFC, 0x6AB4, 0x10FB, 0x66B3, 0xFC6B, 0x8A23,
    0xD19A, 0xA7D2, 0x3D0A, 0x4B42, 0x310D, 0x4745, 0xDD9D, 0xABD5,
    0x2903, 0x5F4B, 0xC593, 0xB3DB, 0xC994, 0xBFDC, 0x2504, 0x534C,
    0x191F, 0x6F57, 0xF58F, 0x83C7, 0xF988, 0x8FC0, 0x1518, 0x6350,
    0xE186, 0x97CE, 0x0D16, 0x7B5E, 0x0111, 0x7759, 0xED81, 0x9BC9,
    0x7927, 0x0F6F, 0x95B7, 0xE3FF, 0x99B0, 0xEFF8, 0x7520, 0x0368,
    0x81BE, 0xF7F6, 0x6D2E, 0x1B66, 0x6129, 0x1761, 0x8DB9, 0xFBF1,
    0xB1A2, 0xC7EA, 0x5D32, 0x2B7A, 0x5135, 0x277D, 0xBDA5, 0xCBED,
    0x493B, 0x3F73, 0xA5AB, 0xD3E3, 0xA9AC, 0xDFE4, 0x453C, 0x3374,
    0xB957, 0xCF1F, 0x55C7, 0x238F, 0x59C0, 0x2F88, 0xB550, 0xC318,
    0x41CE, 0x3786, 0xAD5E, 0xDB16, 0xA159, 0xD711, 0x4DC9, 0x3B81,
    0x71D2, 0x079A, 0x9D42, 0xEB0A, 0x9145, 0xE70D, 0x7DD5, 0x0B9D,
    0x894B, 0xFF03, 0x65DB, 0x1393, 0x69DC, 0x1F94, 0x854C, 0xF304,
    0x11EA, 0x67A2, 0xFD7A, 0x8B32, 0xF17D, 0x8735, 0x1DED, 0x6BA5,
    0xE973, 0x9F3B, 0x05E3, 0x73AB, 0x09E4, 0x7FAC, 0xE574, 0x933C,
    0xD96F, 0xAF27, 0x35FF, 0x43B7, 0x39F8, 0x4FB0, 0xD568, 0xA320,
    0x21F6, 0x57BE, 0xCD66, 0xBB2E, 0xC161, 0xB729, 0x2DF1, 0x5BB9,
};

Итоги

Обе таблицы CRC для FSoE — это таблицы поиска CRC-16 в направлении MSB-first для полинома $P(x) = $ 0x139B7. Они различаются только позицией байта $k$ внутри 4-байтового среза:

Таблица	$k$	Формула	Сдвиги	Назначение
`CRC16_TABLE`	0	$(i \cdot x^{16}) \bmod P$	8	Обычное побайтовое обновление CRC
`CRC16_TABLE2`	3	$(i \cdot x^{40}) \bmod P$	32	Slice-by-4, младший байт

Программа-генератор (GenTables.c) строит обе таблицы исключительно из полинома с помощью единственной функции table_entry(i, shifts) и выводит второй файл исходного кода (Tables.c), содержащий таблицы с самодокументируемым заголовочным комментарием.

Связанные статьи

Обзор и основы

Что на самом деле означает аббревиатура FSoE? — что означает аббревиатура FSoE
FSoE: структура кадра на примерах — общая структура Safety PDU
FSoE: таблица команд safety PDU — полный список команд FSoE

CRC

FSoE CRC: какой полином используется? — 17-битный полином CRC FSoE
FSoE: Как работает наследование CRC? — как цепочка CRC связывает последовательные PDU

Коды ошибок и формат данных

FSoE: список всех кодов ошибок связи — все коды ошибок связи FSoE
FSoE: данные передаются в little-endian или big-endian? — порядок байтов в многобайтовых полях