Implementierung von CRC32-Hashing in TypeScript

CRC32 (Cyclic Redundancy Check 32-bit) ist ein Prüfsummenalgorithmus zur Überprüfung der Datenintegrität.

Es wird häufig verwendet, um zu überprüfen, ob Daten während der Kommunikation oder Dateiübertragung beschädigt sind.

Implementierungsrichtlinie

Um CRC32-Berechnungen zu beschleunigen, verwenden wir eine Nachschlagetabelle mit 256 Einträgen.

Sobald die Tabelle erstellt ist, können nachfolgende Berechnungen schnell durchgeführt werden.

Nachschlagetabelle generieren

Erstellen Sie zunächst eine Funktion zum Generieren einer Tabelle für die CRC32-Berechnung.

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

Erstellen Sie nur dann eine neue Tabelle, wenn noch keine Tabelle erstellt wurde.

Jeder Eintrag stellt das Ergebnis einer Polynomdivision durch einen 8-Bit-Wert dar.

Berechnung des CRC32-Hash

Berechnet mithilfe einer Nachschlagetabelle einen CRC32-Hash der Eingabedaten.

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

Es nimmt Eingabedaten im Uint8Array-Format entgegen und gibt einen CRC32-Hash als 32-Bit-Ganzzahl ohne Vorzeichen zurück.

Vollständiger Code

Die vollständige Implementierung, die die beiden oben genannten Funktionen kombiniert, ist wie folgt.

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

Anwendungsbeispiel

Ein Beispiel für die Berechnung eines CRC32-Hashs einer Zeichenfolge.

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

Konvertieren Sie es mit TextEncoder in Uint8Array und übergeben Sie es dann an die crc32Hash-Funktion.

Zusammenfassung

CRC32 ist ein einfacher, aber praktischer Prüfsummenalgorithmus.

Sie können Nachschlagetabellen verwenden, um Berechnungen schnell in TypeScript durchzuführen. Es kann in einer Vielzahl von Situationen verwendet werden, beispielsweise zur Überprüfung der Dateiintegrität und zur Generierung von Cache-Schlüsseln.