Реализация CRC32 в TypeScript

Обеспечение проверки целостности данных с помощью алгоритма CRC32

Целостность данных имеет решающее значение в различных приложениях, включая передачу файлов, сетевые протоколы и системы хранения. Чтобы гарантировать, что данные остаются неповрежденными во время передачи или хранения, обычно используются алгоритмы контрольной суммы, такие как CRC32 (32-битная проверка циклическим избыточным кодом). В этой статье мы рассмотрим реализацию CRC32 в TypeScript/JavaScript, популярном языке веб-разработки.

В отличие от других языков программирования, таких как Java, PHP или Python, JavaScript не имеет встроенной поддержки CRC32. Однако в этой статье мы реализуем CRC32, совместимый с упомянутыми языками (аналогично тому, что используется в zip-архивах).

Понимание CRC

CRC32 генерирует 32-битное значение контрольной суммы. Это значение можно использовать для обнаружения ошибок при передаче или хранении. Поэтому одним из основных требований (среди прочих, таких как простота и скорость) к CRC является возможность обнаружения ошибок. Это означает, что вероятность столкновений должна быть низкой.

CRC основан на процессе деления. Деление выполняется с помощью операции двоичного исключающего ИЛИ (XOR). После обработки всех битов сообщения последний остаток, полученный от деления, представляет собой контрольную сумму.

При вычислении CRC может использоваться побитовый сдвиг влево ‹‹ и побитовый сдвиг вправо ››. Мы реализуем версию без знака со сдвигом вправо (без знака CRC32), которая иногда упоминается как «обратная».

CRC 3-битный псевдоалгоритм контрольной суммы

Чтобы лучше понять, как это работает, давайте начнем с реализации простого 3-битного псевдоалгоритма CRC, который будет генерировать 3-битную контрольную сумму.

const divisor = 0b111;
let crc = 0b000;

for (const byte of bytes) {
  let reminder = byte;
  for (let i = 0; i < 8; i++) {
    if (reminder & 1) {
      reminder = (reminder >>> 1) ^ divisor;
    } else {
      reminder = reminder >>> 1;
    }
  }

  // final division
  crc = crc ^ reminder;
}

Мы должны заметить, что:

Ввод обрабатывается как последовательность битов, сгруппированных в байты.
Есть начальное состояние, установленное на 0b000.
3-битное напоминание вычисляется для каждого бита в байте на основе значения младшего значащего бита (LSB). Если бит не установлен, деление не производится.
Существует 3-битный делитель, который используется в операции XOR для вычисления напоминания.
3-битная контрольная сумма вычисляется для каждого входящего байта с использованием операции XOR с 3-битным напоминанием.
Длина бита делителя влияет на длину бита CRC. Например, уменьшение делителя до 0b11 (2 бита) увеличит количество коллизий и значительно снизит эффективность алгоритма (см. Выход 2).

Давайте проверим результаты:

console.log('1234567890', crc3('1234567890'));
console.log('123456789', crc3('123456789'));
console.log('12345678', crc3('12345678'));
console.log('hello', crc3('hello'));
console.log('hello crc3', crc3('hello crc3'));
console.log('some other text', crc3('some other text'));

Выход 1:

{ '1234567890': '1' }
{ '123456789': '2' }
{ '12345678': '7' }
{ hello: '4' }
{ 'hello crc3': '3' }
{ 'some other text': '4' }
{ 'empty string': '0' }

Здесь мы видим, что полученная контрольная сумма находится в десятичном диапазоне от 0 до 7, что отражает 3-битное значение. Поскольку возможных контрольных сумм всего 8, мы видим, что вероятность коллизий высока. Например, расчетное значение для «привет» и «другой текст» одинаково.

Важно использовать делитель той же длины битов, что и максимально возможная длина битов контрольной суммы (в данном примере это 3 бита). Посмотрите, как использование делителя менее 3 бит, например 2 бита, повлияет на результирующий код.

Выход 2. Использование делителя 0b11 приводит к большему количеству коллизий.

{ '1234567890': '2' }
{ '123456789': '0' }
{ '12345678': '2' }
{ hello: '0' }
{ 'hello crc3': '1' }
{ 'some other text': '2' }
{ 'empty string': '0' }

CRC32

Одно из основных отличий между псевдо-CRC3, который мы имеем в примере выше, и реальным CRC32, заключается в использовании многочлена в качестве делителя. Алгоритм CRC32 использует предопределенный полином, который можно записать в виде двоичного числа определенной длины.

Вот список примитивных неприводимых полиномов для порождения элементов бинарного поля расширения GF(2m) из базового конечного поля. Список содержит многочлены от 32 [Ref. 1].

x^32 + x^22 + x^2 + x^1 + 1
x^32 + x^22 + x^21 + x^20 + x^18 + x^17 + x^15 + x^13 + x^12 + x^10 + x^8 + x^6 + x^4 + x^1 + 1
x^32 + x^23 + x^17 + x^16 + x^14 + x^10 + x^8 + x^7 + x^6 + x^5 + x^3 + 1
x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x^1 + 1
x^32 + x^27 + x^26 + x^25 + x^24 + x^23 + x^22 + x^17 + x^13 + x^11 + x^10+x^9+x^8+x^7+x^2+x^1 + 1
x^32 + x^28 + x^19 + x^18 + x^16 + x^14 + x^11 + x^10 + x^9 + x^6 + x^5 + x^1 + 1

Самый популярный полином — 0x04C11DB7, а его обратная версия (взятая в обратном порядке) — 0xEDB88320 [Ref. 2].

x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x^1 + 1
which is 00000100110000010001110110110111 or 0x04C11DB7
reversing the bits we will have 11101101101110001000001100100000 or 0xEDB88320

Мы будем использовать 0xEDB88320 в нашей реализации CRC32.

Реализация Unsigned CRC32 в TypeScript

Вот грязная версия рабочего CRC32 в TS.

const toUnsignedInt32 = (n: number): number => {
  if (n >= 0) {
    return n;
  }
  return 0xFFFFFFFF - (n * -1) + 1;
}
export const crc32UnsignedFull = (input: string): number => {
  const encoder = new TextEncoder();
  const bytes = encoder.encode(input);
  const divisor = 0xEDB88320;
  let crc = 0xFFFFFFFF;
  for (const byte of bytes) {
    crc = (crc ^ byte);
    for (let i = 0; i < 8; i++) {
      if (crc & 1) {
        crc = (crc >>> 1) ^ divisor;
      } else {
        crc = crc >>> 1;
      }
    }
  }
  return toUnsignedInt32(crc ^ 0xFFFFFFFF);
};

Выход 3. Подсчитаем контрольную сумму для «hello crc32».

console.log(crc32UnsignedFull('hello crc32')); // 2560021400

Он «грязный», потому что не оптимизирован. Но расчеты правильные. Здесь мы должны заметить:

Начальное состояние установлено на 0xFFFFFFFF.
Перед возвратом применяется результирующая операция XOR контрольной суммы с 0xFFFFFFFF.
Результат преобразуется в беззнаковое целое.

Оптимизация

В цикле for мы вычисляем результат для каждого байта. Каждый входящий байт может иметь 256 состояний, поэтому мы можем построить таблицу поиска с 256 предварительно вычисленными результатами.

const buildCRC32LookupTable = (polynomial: number): number[] => {
  const table: number[] = [];
  for (let n = 0; n < 256; n++) {
    let reminder = n;
    for (let i = 0; i < 8; i++) {
      if (reminder & 1) {
        reminder = (reminder >>> 1) ^ polynomial;
      } else {
        reminder = reminder >>> 1;
      }
    }
    table.push(toUnsignedInt32(reminder));
  }
  return table;
}

Выход 4. Таблица поиска

console.log(JSON.stringify(buildCRC32LookupTable(0xEDB88320)));
// [0, 1996959894, 3993919788, 2567524794, 124634137, 1886057615, 3915621685, 2657392035, 249268274, 2044508324, 3772115230, 2547177864, 162941995, 2125561021, 3887607047, 2428444049, 498536548, 1789927666, 4089016648, 2227061214, 450548861, 1843258603, 4107580753, 2211677639, 325883990, 1684777152, 4251122042, 2321926636, 335633487, 1661365465, 4195302755, 2366115317, 997073096, 1281953886, 3579855332, 2724688242, 1006888145, 1258607687, 3524101629, 2768942443, 901097722, 1119000684, 3686517206, 2898065728, 853044451, 1172266101, 3705015759, 2882616665, 651767980, 1373503546, 3369554304, 3218104598, 565507253, 1454621731, 3485111705, 3099436303, 671266974, 1594198024, 3322730930, 2970347812, 795835527, 1483230225, 3244367275, 3060149565, 1994146192, 31158534, 2563907772, 4023717930, 1907459465, 112637215, 2680153253, 3904427059, 2013776290, 251722036, 2517215374, 3775830040, 2137656763, 141376813, 2439277719, 3865271297, 1802195444, 476864866, 2238001368, 4066508878, 1812370925, 453092731, 2181625025, 4111451223, 1706088902, 314042704, 2344532202, 4240017532, 1658658271, 366619977, 2362670323, 4224994405, 1303535960, 984961486, 2747007092, 3569037538, 1256170817, 1037604311, 2765210733, 3554079995, 1131014506, 879679996, 2909243462, 3663771856, 1141124467, 855842277, 2852801631, 3708648649, 1342533948, 654459306, 3188396048, 3373015174, 1466479909, 544179635, 3110523913, 3462522015, 1591671054, 702138776, 2966460450, 3352799412, 1504918807, 783551873, 3082640443, 3233442989, 3988292384, 2596254646, 62317068, 1957810842, 3939845945, 2647816111, 81470997, 1943803523, 3814918930, 2489596804, 225274430, 2053790376, 3826175755, 2466906013, 167816743, 2097651377, 4027552580, 2265490386, 503444072, 1762050814, 4150417245, 2154129355, 426522225, 1852507879, 4275313526, 2312317920, 282753626, 1742555852, 4189708143, 2394877945, 397917763, 1622183637, 3604390888, 2714866558, 953729732, 1340076626, 3518719985, 2797360999, 1068828381, 1219638859, 3624741850, 2936675148, 906185462, 1090812512, 3747672003, 2825379669, 829329135, 1181335161, 3412177804, 3160834842, 628085408, 1382605366, 3423369109, 3138078467, 570562233, 1426400815, 3317316542, 2998733608, 733239954, 1555261956, 3268935591, 3050360625, 752459403, 1541320221, 2607071920, 3965973030, 1969922972, 40735498, 2617837225, 3943577151, 1913087877, 83908371, 2512341634, 3803740692, 2075208622, 213261112, 2463272603, 3855990285, 2094854071, 198958881, 2262029012, 4057260610, 1759359992, 534414190, 2176718541, 4139329115, 1873836001, 414664567, 2282248934, 4279200368, 1711684554, 285281116, 2405801727, 4167216745, 1634467795, 376229701, 2685067896, 3608007406, 1308918612, 956543938, 2808555105, 3495958263, 1231636301, 1047427035, 2932959818, 3654703836, 1088359270, 936918000, 2847714899, 3736837829, 1202900863, 817233897, 3183342108, 3401237130, 1404277552, 615818150, 3134207493, 3453421203, 1423857449, 601450431, 3009837614, 3294710456, 1567103746, 711928724, 3020668471, 3272380065, 1510334235, 755167117]

Окончательный вариант

Ниже представлена окончательная версия Unsigned CRC32, реализованная на TypeScript. В отличие от других популярных реализаций JS/TS, эта версия использует TextEncoder вместо Buffer и поддерживается во всех современных браузерах без дополнительных зависимостей полифилла.

/**
 * Calculate CRC32 unsigned for 0x04C11DB7 polynomial.
 * Browser and NodeJS compatible version.
 */
export class CRC32 {
  /**
   * Lookup table calculated for 0xEDB88320 divisor
   */
  protected lookupTable = [0, 1996959894, 3993919788, 2567524794, 124634137, 1886057615, 3915621685, 2657392035, 249268274, 2044508324, 3772115230, 2547177864, 162941995, 2125561021, 3887607047, 2428444049, 498536548, 1789927666, 4089016648, 2227061214, 450548861, 1843258603, 4107580753, 2211677639, 325883990, 1684777152, 4251122042, 2321926636, 335633487, 1661365465, 4195302755, 2366115317, 997073096, 1281953886, 3579855332, 2724688242, 1006888145, 1258607687, 3524101629, 2768942443, 901097722, 1119000684, 3686517206, 2898065728, 853044451, 1172266101, 3705015759, 2882616665, 651767980, 1373503546, 3369554304, 3218104598, 565507253, 1454621731, 3485111705, 3099436303, 671266974, 1594198024, 3322730930, 2970347812, 795835527, 1483230225, 3244367275, 3060149565, 1994146192, 31158534, 2563907772, 4023717930, 1907459465, 112637215, 2680153253, 3904427059, 2013776290, 251722036, 2517215374, 3775830040, 2137656763, 141376813, 2439277719, 3865271297, 1802195444, 476864866, 2238001368, 4066508878, 1812370925, 453092731, 2181625025, 4111451223, 1706088902, 314042704, 2344532202, 4240017532, 1658658271, 366619977, 2362670323, 4224994405, 1303535960, 984961486, 2747007092, 3569037538, 1256170817, 1037604311, 2765210733, 3554079995, 1131014506, 879679996, 2909243462, 3663771856, 1141124467, 855842277, 2852801631, 3708648649, 1342533948, 654459306, 3188396048, 3373015174, 1466479909, 544179635, 3110523913, 3462522015, 1591671054, 702138776, 2966460450, 3352799412, 1504918807, 783551873, 3082640443, 3233442989, 3988292384, 2596254646, 62317068, 1957810842, 3939845945, 2647816111, 81470997, 1943803523, 3814918930, 2489596804, 225274430, 2053790376, 3826175755, 2466906013, 167816743, 2097651377, 4027552580, 2265490386, 503444072, 1762050814, 4150417245, 2154129355, 426522225, 1852507879, 4275313526, 2312317920, 282753626, 1742555852, 4189708143, 2394877945, 397917763, 1622183637, 3604390888, 2714866558, 953729732, 1340076626, 3518719985, 2797360999, 1068828381, 1219638859, 3624741850, 2936675148, 906185462, 1090812512, 3747672003, 2825379669, 829329135, 1181335161, 3412177804, 3160834842, 628085408, 1382605366, 3423369109, 3138078467, 570562233, 1426400815, 3317316542, 2998733608, 733239954, 1555261956, 3268935591, 3050360625, 752459403, 1541320221, 2607071920, 3965973030, 1969922972, 40735498, 2617837225, 3943577151, 1913087877, 83908371, 2512341634, 3803740692, 2075208622, 213261112, 2463272603, 3855990285, 2094854071, 198958881, 2262029012, 4057260610, 1759359992, 534414190, 2176718541, 4139329115, 1873836001, 414664567, 2282248934, 4279200368, 1711684554, 285281116, 2405801727, 4167216745, 1634467795, 376229701, 2685067896, 3608007406, 1308918612, 956543938, 2808555105, 3495958263, 1231636301, 1047427035, 2932959818, 3654703836, 1088359270, 936918000, 2847714899, 3736837829, 1202900863, 817233897, 3183342108, 3401237130, 1404277552, 615818150, 3134207493, 3453421203, 1423857449, 601450431, 3009837614, 3294710456, 1567103746, 711928724, 3020668471, 3272380065, 1510334235, 755167117];

  public calculate(input: string): number {
    const bytes = this.strToBytes(input);
    let crc = 0xFFFFFFFF;
    for (const byte of bytes) {
      const tableIndex = (crc ^ byte) & 0xFF;
      const tableVal = this.lookupTable?.[tableIndex];
      if (tableVal === undefined) throw new Error('tableIndex out of range 0-255');
      crc = (crc >>> 8) ^ tableVal;
    }

    return this.toUint32(crc ^ 0xFFFFFFFF);
  }

  protected strToBytes(input: string): Uint8Array {
    const encoder = new TextEncoder();
    return encoder.encode(input);
  }

  protected toUint32(num: number): number {
    if (num >= 0) {
      return num;
    }
    const a = new Uint32Array(1);
    a[0] = num;
    return a[0];
  }
}

Выход 5.

const crc = new CRC32();
console.log(crc.calculate('hello crc32')); // 2560021400 (0x9896d398)

Вопросы

Полиномиальное представление битов имеет 33 бита, как мы получаем число 0x4c11db7?

Отвечать. Поскольку в многочлене c*x³² + c*x²⁶ + c*x²³ + c*x²² + c*x¹⁶ + c*x¹² + c*x¹¹ + c*x¹⁰ + c*x⁸ + c*x⁷ + c*x⁵ + c*x⁴ + c*x² + c*x¹ + 1 опускаем коэффициенты, равные 0, и оставляем только c = 1, полное представление 100000100110000010001110110110111 (33 бита). Но CRC32 вычисляет 32-битное целое число, а 33-битное просто не подходит. Поэтому нам нужно отбросить лишние биты MSB. См. код ниже.

const a = new Int32Array(1);
a[0] = 0b100000100110000010001110110110111; // put 33 bits into 32 bit registry
a[0].toString(16); // 4c11db7
a[0].toString(2); // 100110000010001110110110111 - leading 1 dropped, other leading 0 not printed

2. Почему нам нужно использовать обратный многочлен? Или как делитель 0xEDB88320 был получен из 0x04C11DB7?

Отвечать. Мы меняем местами биты 0x04C11DB7.

'00000100110000010001110110110111'.split('').reverse().join(''); // 11101101101110001000001100100000
(0b11101101101110001000001100100000).toString(16); // edb88320

Также 0xEDB88320 использует 32 бита по сравнению с 27 битами 0x04C11DB7, что важно для обратного алгоритма CRC (помните результаты после использования 2-битного делителя 0b11 в CRC3 «Выход 2» выше).

(0x04C11DB7).toString(2).length; // 27
(0xEDB88320).toString(2).length; // 32

Увеличение числа битов (степени полинома) усложняет вычисления, а результирующая контрольная сумма более уникальна (улучшает обнаружение ошибок).

3. Есть ли разница в получении последовательности байтов из TextEncoder вместо charCodeAt?

Отвечать. Да. Они могут давать разные результаты для многобайтовых символов. charCodeAt() фокусируется на кодовых точках Unicode, а TextEncoder возвращает массив байтов на основе кодировки. [См. пример в ссылке. 4]

Совместимость

Давайте проверим, будет ли контрольная сумма, рассчитанная на нескольких других языках программирования для той же входной строки, соответствовать результатам, полученным в выходных данных 5.

Джава

import java.util.zip.CRC32;
import java.util.zip.Checksum;

public class CRC32Test {
  public static void main(String[] args) {
    String input = "hello crc32";
    byte[] bytes = input.getBytes();
    Checksum checksum = new CRC32(); // java.util.zip.CRC32
    checksum.update(bytes, 0, bytes.length);
    System.out.println(checksum.getValue());
  }
}

Результат 2560021400 (0x9896d398).

Питон

import binascii
binascii.crc32(b'hello crc32')

Результат 2560021400 (0x9896d398).

import zlib
zlib.crc32(b'hello crc32')

Тот же результат: 2560021400 (0x9896d398).

PHP

php -r 'echo crc32("hello crc32"), "\n";'

Выводит 2560021400 (0x9896d398).

Заключение

Реализация алгоритма CRC32 в TypeScript предоставляет мощный инструмент для проверки целостности данных. Понимая основы и выполняя расчет CRC32, разработчики могут обеспечить надежность и целостность данных в различных приложениях.

Реализация CRC32 в TypeScript

Обеспечение проверки целостности данных с помощью алгоритма CRC32

Понимание CRC

CRC 3-битный псевдоалгоритм контрольной суммы

CRC32

Реализация Unsigned CRC32 в TypeScript

Оптимизация

Окончательный вариант

Вопросы

Совместимость

Джава

Питон

PHP

Заключение

Рекомендации

смотрите также:

Новые материалы

Как проанализировать работу вашего классификатора?

Работа с цепями Маркова, часть 4 (Машинное обучение)

Crazy Laravel Livewire упростил мне создание электронной коммерции (панель администратора и API) [Часть 3]

Использование машинного обучения и Python для классификации 1000 сезонов новичков MLB Hitter

Учебные заметки: создание моего первого пакета Node.js

Забудьте о Matplotlib: улучшите визуализацию данных с помощью умопомрачительных функций Seaborn!

ИИ в аэрокосмической отрасли

Метки