Как построить таблицу CRC32 для Ogg? - PullRequest
Новая
       55

Как построить таблицу CRC32 для Ogg?

0 голосов
/ 23 ноября 2018

С этот ответ Я адаптировал приведенный ниже код: 

function _makeCRCTable() {
    const CRCTable = new Uint32Array(256);
    for (let i = 256; i--;) {
        let char = i;
        for (let j = 8; j--;) {
            char = char & 1 ? 3988292384 ^ char >>> 1 : char >>> 1;
        }
        CRCTable[i] = char;
    }
    return CRCTable;
}

Этот код генерирует таблицу как здесь , но для Ogg мне нужна другая таблица - как здесь .

Из Документация Ogg :

32-битное значение CRC (прямой алгоритм, начальное значение и конечное значение XOR = 0, полином генератора= 0x04c11db7) 

parseInt('04c11db7', 16)

return 79764919 - я пробовал этот полином, но полученная таблица неверна.

Я новичок в поле CRC, как я обнаружил Есть несколько вариантов алгоритма CRC32 .

1 Ответ

0 голосов
/ 23 ноября 2018

Я не уверен в приоритетности javascript, но xor должен произойти после сдвига: 

char = char & 1 ? 3988292384 ^ (char >>> 1) : char >>> 1;

Однако первая отображаемая таблица выглядит правильно, так как table [128] = table [0x80]= 3988292384 = 0xEDB88320, то есть бит 0x104c11db7, затем смещенный вправо на один бит.

Вторая ваша таблица предназначена для CRC со смещением влево, где таблица [1] = x04c11db7.В этом случае внутренний цикл будет содержать что-то вроде этого: 

let char = i << 24;
for (let j = 8; j--;) {
    char = char & 0x80000000 ? 0x04c11db7 ^ char << 1 : char << 1;
}

Пример кода C для сравнения генерирует crc для шаблонов {0x01}, {0x01,0x00}, {0x01,0x00,0x00}, {0x01,0x00,0x00,0x00}. 

#include <stdio.h>

typedef unsigned char uint8_t;
typedef unsigned int  uint32_t;

uint32_t crctbl[256];

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

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

int main(int argc, char** argv)
{
    uint32_t crc;
    uint8_t bfr[4] = {0x01,0x00,0x00,0x00};
    gentbl();
    crc = crc32(bfr, 1);        /* 0x04c11db7 */
    printf("%08x\n", crc);
    crc = crc32(bfr, 2);        /* 0xd219c1dc */
    printf("%08x\n", crc);
    crc = crc32(bfr, 3);        /* 0x01d8ac87 */
    printf("%08x\n", crc);
    crc = crc32(bfr, 4);        /* 0xdc6d9ab7 */
    printf("%08x\n", crc);
    return(0);
}

Для JS: 

function _makeCRC32Table() {
    const polynomial = 79764919;
    const mask = 2147483648;
    const CRCTable = new Uint32Array(256);
    for (let i = 256; i--;) {
        let char = i << 24;
        for (let j = 8; j--;) {
            char = char & mask ? polynomial ^ char << 1 : char << 1;
        }
        CRCTable[i] = char;
    }
    return CRCTable;
}

Как использовать эту таблицу: 

[1, 0].reduce((crc, byte) => crc << 8 >>> 0 ^ CRCTable[crc >>> 24 ^ byte], 0) >>> 0

Здесьмы добавили >>> 0, который принимает модуль числа - потому что в JS нет unsigned int - JavaScript не имеет целых чисел.Он имеет только числа с плавающей запятой двойной точности .

Обратите внимание, что для Ogg вы должны установить сгенерированный CRC в обратном порядке.

...