TypeScriptでCRC32ハッシュを実装する

CRC32 (Cyclic Redundancy Check 32-bit) は、データの整合性チェックに使われるチェックサムアルゴリズムだ。

通信やファイル転送で、データが破損していないかを確認するために広く使われている。

実装方針

CRC32の計算を高速化するため、256エントリのルックアップテーブルを使う。

一度テーブルを生成すれば、以降の計算は高速に行える。

ルックアップテーブルの生成

まず、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;
}

テーブルが未生成の場合のみ新しいテーブルを作成する。

各エントリは、8ビットの値に対する多項式除算の結果を表す。

CRC32ハッシュの計算

ルックアップテーブルを使って、入力データのCRC32ハッシュを計算する。

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

Uint8Array形式の入力データを受け取り、32ビットの符号なし整数としてCRC32ハッシュを返す。

完全なコード

上記の2つの関数を組み合わせた完全な実装は以下の通り。

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

使用例

文字列のCRC32ハッシュを計算する例。

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

TextEncoderでUint8Arrayに変換してから、crc32Hash関数に渡す。

まとめ

CRC32はシンプルだが実用的なチェックサムアルゴリズムだ。

ルックアップテーブルを使えば、TypeScriptでも高速に計算できる。ファイルの整合性チェックやキャッシュキーの生成など、さまざまな場面で活用できる。