Разница местоположения контрольной суммы и CR C. ПОЧЕМУ? - PullRequest
Новая
       116

Разница местоположения контрольной суммы и CR C. ПОЧЕМУ?

0 голосов
/ 02 апреля 2020

У меня есть вопрос при изучении CR C и контрольной суммы.

CR C находится в хвосте, но контрольная сумма находится в заголовке. Я думал из-за усложнения CR C и контрольной суммы. CR C более сложный, поэтому он находит заголовок, но контрольная сумма менее сложна, поэтому он находит хвост. Это правильно?

Почему это так?

1 Ответ

0 голосов
/ 02 апреля 2020

В случае переданных или полученных данных аппаратные реализации обычно генерируют CR C или контрольную сумму во время передачи данных, а затем передают CR C или контрольную сумму (так что CR C или контрольная сумма будет в конце данных). Это избавляет от необходимости буферизовать больше, чем требуется для хранения CR C или контрольной суммы и единицы передачи (такой как байт).

Для сообщения в памяти, CR C четность байты или контрольные суммы могут быть расположены в любом месте сообщения. Для контрольной суммы это прямо, но для CR C CR C должен генерироваться нормально, затем циклически возвращаться и сохраняться в том месте, где он будет находиться в сообщении. Цикл в обратном направлении можно оптимизировать, как показано во второй части моего ответа.

Контрольные суммы могут быть где угодно в сообщении, поскольку вычисление легко.

В шестнадцатеричном формате Intel используется / был довольно распространенным форматом для хранения двоичных данных в текстовом файле и имел контрольную сумму после конца данных в каждой строке текстового файла:

https://en.wikipedia.org/wiki/Intel_HEX#Record_structure

Заголовок IPv4 помещает контрольную сумму в message_word [5]:

https://en.wikipedia.org/wiki/IPv4_header_checksum#Calculating_the_IPv4_header_checksum

Возможно иметь чеки CR C где угодно в сообщение. Байты четности обнуляются, вычисляется нормальный CR C, затем CR C "циклически повторяется" до места, где он будет сохранен. Вместо реверсирования CR C можно использовать умножение без переноса: 

parity = (crc · (pow(2,-1-reverse_distance)%poly))%poly

-1 представляет период c циклического периода для CR C. Для CRC32 период равен 2 ^ 32-1 = 0xffffffff

Пример кода для 32-байтового сообщения с 14 байтами данных, 4 байтами четности, 14 байтами данных. После сохранения байтов четности в сообщении обычный расчет CR C для сообщения будет равен нулю. 

#include <stdio.h>

typedef unsigned char       uint8_t;
typedef unsigned int       uint32_t;

static uint32_t crctbl[256];

void GenTbl(void)                       /* generate crc table */
{
uint32_t crc;
uint32_t c;
uint32_t i;
    for(c = 0; c < 0x100; c++){
        crc = c<<24;
        for(i = 0; i < 8; i++)
            crc = (crc<<1)^((0-(crc>>31))&0x04c11db7);
        crctbl[c] = crc;
    }
}

uint32_t GenCrc(uint8_t * bfr, size_t size) /* generate crc */
{
uint32_t crc = 0u;
    while(size--)
        crc = (crc<<8)^crctbl[(crc>>24)^*bfr++];
    return(crc);
}

/* carryless multiply modulo crc */
uint32_t MpyModCrc(uint32_t a, uint32_t b) /* (a*b)%crc */
{
uint32_t pd = 0;
uint32_t i;
    for(i = 0; i < 32; i++){
        pd = (pd<<1)^((0-(pd>>31))&0x04c11db7u);
        pd ^= (0-(b>>31))&a;
        b <<= 1;
    }
    return pd;
}

/* exponentiate by repeated squaring modulo crc */
uint32_t PowModCrc(uint32_t p)          /* pow(2,p)%crc */
{
uint32_t prd = 0x1u;                    /* current product */
uint32_t sqr = 0x2u;                    /* current square */
    while(p){
        if(p&1)
            prd = MpyModCrc(prd, sqr);
        sqr = MpyModCrc(sqr, sqr);
        p >>= 1;
    }
    return prd;
}

/*  message 14 data, 4 parities, 14 data */
/*  parities = crc cycled backwards 18 bytes */

int main()
{
uint32_t pmr;
uint32_t crc;
uint32_t par;
uint8_t msg[32] = {0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,
                   0x09,0x0a,0x0b,0x0c,0x0d,0x0e,0x00,0x00,
                   0x00,0x00,0x13,0x14,0x15,0x16,0x17,0x18,
                   0x19,0x1a,0x1b,0x1c,0x1d,0x1e,0x1f,0x20};

    GenTbl();                           /* generate crc table */
    pmr = PowModCrc(-1-(18*8));         /* pmr = pow(2,-1-18*8)%crc */
    crc = GenCrc(msg, 32);              /* generate crc */
    par = MpyModCrc(crc, pmr);          /* par = (crc*pmr)%crc */
    msg[14] = (uint8_t)(par>>24);       /* store parities in msg */
    msg[15] = (uint8_t)(par>>16);
    msg[16] = (uint8_t)(par>> 8);
    msg[17] = (uint8_t)(par>> 0);
    crc = GenCrc(msg, 32);              /* crc == 0 */
    printf("%08x\n", crc);

    return 0;
}
...