C ulong операция с массивом CRC32

Давайте проанализируем всю функцию. Функция объявлена ​​следующим образом:

void CRC32(const byte *buf, uint len, const byte init[4], byte crc[4]) 

const byte *buf - входной буфер, для которого вычисляется CRC

uint len - Длина вычисляемого CRC

const byte init[4] - вектор инициализации CRC

byte crc[4] - Вывод / результат вычисления CRC

Сначала мы видим, что crc инициализируется вектором инициализации в memcpy(crc, init, 4);. Затем у нас есть цикл, который повторяется len раз. В конце этого цикла указатель buf увеличивается на ++buf.

Теперь о той части, которую вы не понимаете.

Каждый байт buf подвергается операции XOR с crc[3], результат которой используется как смещение в crc32_table. Результирующее значение сохраняется в tmp, которое затем используется для шифрования четырех байтов crc. Ключевые факторы, лежащие в основе этой работы, включают crc32_table 256 записей и 256 возможных значений байта (что является результатом операции, которую вы пытаетесь понять). Таким образом, индекс смещения всегда действителен.

Остальные операции - это просто XOR, которые еще больше скремблируют crc.

ОБНОВЛЕНИЕ

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

Допустим, у нас есть следующий массив ulong crc32_table[256] в ячейке памяти 0x400000.

Тогда значение crc32_table равно 0x400000.

Кроме того, &crc32_table[0] также 0x400000 (это переводится в адрес первой записи в массиве crc32_table).

Однако &crc32_table[1] равно 0x400008 (если sizeof (ulong) в вашей системе составляет 8 байт)

Вот что интересно.

crc32_table + 1 также 0x400008 (то же, что и &crc32_table[1]).

Это известно как арифметика указателей, и это та же концепция, которая используется в предоставленном вами коде CRC. Этот код просто вычисляет смещение 0–255 в массиве размером 256, поэтому каждое возможное смещение является действительным и транслируется в соответствующий индекс массива.

Здесь,

const byte * tmp = (const byte *)(crc32_table + (crc[3] ^ *buf));

с buf, указывающим на следующий байт ввода, это исключает следующий байт ввода со старшим байтом текущего значения CRC и ищет его в таблице. Или, скорее, он ищет адрес этого элемента в таблице и преобразует его в const byte *, чтобы байты можно было прочитать позже. (crc32_table + (foo) совпадает с &crc32_table[foo].)

Тогда это:

crc[3] = crc[2] ^ tmp[3];
crc[2] = crc[1] ^ tmp[2];
crc[1] = crc[0] ^ tmp[1];
crc[0] = tmp[0];

сдвигает значение CRC на 8 бит (обратите внимание на индексы) и xors в значении, выбранном из таблицы. Здесь tmp - это указатель на байт (вероятно, unsigned char *), который затем указывает на первый байт одного из значений в таблице. При доступе через tmp[0] к tmp[3] затем читается этот байт и следующие байты значения по отдельности. Если ulong равно unsigned long, это как минимум 32 бита или четыре байта, поэтому доступ не переходит к следующему значению. Однако для того, чтобы это работало, необходимо знать, что порядок байтов правильный.

Я бы сделал это, используя uint32_ts вместо массивов символов, но что угодно. Что-то вроде этого, то есть, хотя я не тестировал, вероятно, это неправильно:

uint32_t tmp, crc = init;
while (len--) { 
    tmp = crc32_table(((crc >> 24) & 0xff) ^ *buf++);
    crc = (crc << 8) ^ tmp; 
}

Использование этой предварительно рассчитанной таблицы является оптимизацией для вычисления CRC. Если вы посмотрите на определения, вы обычно увидите их как схемы, в которых один бит смещается с одного конца регистра, используемый для возможного переворачивания некоторых битов в регистре, а входной бит смещается одновременно. время. Поиск в таблице обрабатывает только эти 8 бит за раз; значения в таблице - это чистые биты, перевернутые в регистре при сдвиге этих 8 битов.

Я отмечаю этот вопрос как ответ, так как здесь достаточно информации, чтобы решить мою проблему.