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에서도 고속으로 계산할 수 있다. 파일의 무결성 체크나 캐시 키의 생성 등, 다양한 장면에서 활용할 수 있다.