CRC32ハッシュを生成

CRC32

Cyclic Redundancy Check 32-bit

データの整合性チェックなどに使用されるチェックサムアルゴリズム

TypeScriptによるCRC32の実装

テーブルの生成

CRC32の計算を高速化するために、まず256エントリのルックアップテーブルを生成。

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ハッシュを計算。

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ハッシュを返す。

コード全体

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

使用例

文字列 ‘hello’ のCRC32ハッシュを計算し、結果をコンソールに出力

console.log(crc32Hash(new TextEncoder().encode('hello')))