Implementando hash CRC32 em TypeScript

CRC32 (Cyclic Redundancy Check 32-bit) é um algoritmo de soma de verificação usado para verificar a integridade dos dados.

É amplamente utilizado para verificar se os dados estão corrompidos durante comunicações ou transferências de arquivos.

Política de implementação

Para acelerar os cálculos do CRC32, usamos uma tabela de consulta de 256 entradas.

Depois que a tabela for gerada, os cálculos subsequentes poderão ser realizados rapidamente.

Gera tabela de pesquisa

Primeiro, crie uma função para gerar uma tabela para cálculo do CRC32.

let crc32Table: number[] | undefined;

function getTable(): number[] {
  if (crc32Table !== undefined && crc32Table.length > 0) return crc32Table;

  crc32Table = [];
  for (let i = 0; i < 256; ++i) {
    let r = i;
    for (let j = 0; j < 8; ++j) {
      r = (r & 1) === 1 ? 0xedb88320 ^ (r >>> 1) : r >>> 1;
    }
    crc32Table[i] = r >>> 0;
  }
  return crc32Table;
}

Crie uma nova tabela somente se nenhuma tabela tiver sido criada ainda.

Cada entrada representa o resultado da divisão polinomial em um valor de 8 bits.

Calculando o hash CRC32

Calcula um hash CRC32 dos dados de entrada usando uma tabela de consulta.

function crc32Hash(data: Uint8Array): number {
  const table = getTable();

  let crc = 0xffffffff;
  for (let o of data) {
    crc = (crc >>> 8) ^ table[(crc ^ o) & 0xff];
  }
  crc = crc ^ 0xffffffff;
  return crc >>> 0;
}

Ele recebe dados de entrada no formato Uint8Array e retorna um hash CRC32 como um número inteiro não assinado de 32 bits.

Código completo

A implementação completa combinando as duas funções acima é a seguinte.

let crc32Table: number[] | undefined;

function getTable(): number[] {
  if (crc32Table !== undefined && crc32Table.length > 0) return crc32Table;

  crc32Table = [];
  for (let i = 0; i < 256; ++i) {
    let r = i;
    for (let j = 0; j < 8; ++j) {
      r = (r & 1) === 1 ? 0xedb88320 ^ (r >>> 1) : r >>> 1;
    }
    crc32Table[i] = r >>> 0;
  }
  return crc32Table;
}

function crc32Hash(data: Uint8Array): number {
  const table = getTable();

  let crc = 0xffffffff;
  for (let o of data) {
    crc = (crc >>> 8) ^ table[(crc ^ o) & 0xff];
  }
  crc = crc ^ 0xffffffff;
  return crc >>> 0;
}

Exemplo de uso

Um exemplo de cálculo de um hash CRC32 de uma string.

console.log(crc32Hash(new TextEncoder().encode("hello")));

Converta-o para Uint8Array com TextEncoder e depois passe-o para a função crc32Hash.

resumo

CRC32 é um algoritmo de soma de verificação simples, mas prático.

Você pode usar tabelas de pesquisa para realizar cálculos rapidamente no TypeScript. Ele pode ser usado em diversas situações, como verificação de integridade de arquivos e geração de chaves de cache.