Implémentation du hachage CRC32 dans TypeScript

CRC32 (Cyclic Redundancy Check 32-bit) est un algorithme de somme de contrôle utilisé pour vérifier l’intégrité des données.

Il est largement utilisé pour vérifier si les données sont corrompues lors des communications ou des transferts de fichiers.

Politique de mise en œuvre

Pour accélérer les calculs CRC32, nous utilisons une table de recherche à 256 entrées.

Une fois le tableau généré, les calculs ultérieurs peuvent être effectués rapidement.

Générer une table de recherche

Tout d’abord, créez une fonction pour générer un tableau pour le calcul 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;
}

Créez une nouvelle table uniquement si aucune table n’a encore été créée.

Chaque entrée représente le résultat d’une division polynomiale sur une valeur de 8 bits.

Calcul du hachage CRC32

Calcule un hachage CRC32 des données d’entrée à l’aide d’une table de recherche.

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;
}

Il prend les données d’entrée au format Uint8Array et renvoie un hachage CRC32 sous la forme d’un entier non signé de 32 bits.

Code complet

L’implémentation complète combinant les deux fonctions ci-dessus est la suivante.

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;
}

Exemple d’utilisation

Un exemple de calcul d’un hachage CRC32 d’une chaîne.

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

Convertissez-le en Uint8Array avec TextEncoder, puis transmettez-le à la fonction crc32Hash.

résumé

CRC32 est un algorithme de somme de contrôle simple mais pratique.

Vous pouvez utiliser des tables de recherche pour effectuer des calculs rapidement dans TypeScript. Il peut être utilisé dans diverses situations, telles que la vérification de l’intégrité des fichiers et la génération de clés de cache.