crc32.gno

  1// Package crc32 implements the CRC-32 checksum as a pure, reusable package.
  2//
  3// CRC-32 treats a message as one enormous binary number and takes the remainder
  4// of dividing it by a fixed polynomial. The bit-reflected, table-driven form
  5// implemented here is the one everything actually uses — zip, gzip, PNG, and
  6// Ethernet all speak IEEE.
  7//
  8// Three polynomials are provided:
  9//
 10//   - IEEE       (0xEDB88320) — zip/gzip/PNG. The default.
 11//   - Castagnoli (0x82F63B78) — iSCSI/btrfs; better error detection.
 12//   - Koopman    (0xEB31D82E)
 13//
 14// A CRC is an ACCIDENT detector, not a security primitive: it is linear, so
 15// anyone can craft a different message with the same checksum. Never use it to
 16// authenticate anything.
 17//
 18// A live demo of this package is at
 19// [r/moul/x/daily/crc32demo](/r/moul/x/daily/crc32demo/v0).
 20package crc32
 21
 22import "strings"
 23
 24// Common reversed polynomials.
 25const (
 26	IEEE       = 0xEDB88320
 27	Castagnoli = 0x82F63B78
 28	Koopman    = 0xEB31D82E
 29)
 30
 31// Table is a precomputed byte-wise lookup table for one polynomial.
 32type Table [256]uint32
 33
 34// MakeTable builds the lookup table for a reversed polynomial. Building it once
 35// and reusing it is the whole point of the table-driven form: it trades 1 KiB
 36// for eight bit-shifts per byte.
 37func MakeTable(poly uint32) *Table {
 38	var t Table
 39	for i := 0; i < 256; i++ {
 40		crc := uint32(i)
 41		for j := 0; j < 8; j++ {
 42			if crc&1 != 0 {
 43				crc = (crc >> 1) ^ poly
 44			} else {
 45				crc >>= 1
 46			}
 47		}
 48		t[i] = crc
 49	}
 50	return &t
 51}
 52
 53var ieeeTable = MakeTable(IEEE)
 54
 55// Update adds the bytes of s to a running checksum.
 56//
 57// Takes and returns the RAW register, not the final value: the caller-visible
 58// checksum is the register XOR 0xFFFFFFFF, so chaining Update calls on final
 59// values would be wrong. Start from 0 and finish with Finalize.
 60func Update(crc uint32, t *Table, s string) uint32 {
 61	for i := 0; i < len(s); i++ {
 62		crc = t[byte(crc)^s[i]] ^ (crc >> 8)
 63	}
 64	return crc
 65}
 66
 67// Finalize turns a running register into the checksum.
 68func Finalize(crc uint32) uint32 { return crc ^ 0xFFFFFFFF }
 69
 70// ChecksumWith returns the CRC-32 of s under the given table.
 71func ChecksumWith(s string, t *Table) uint32 {
 72	return Finalize(Update(0xFFFFFFFF, t, s))
 73}
 74
 75// Checksum returns the IEEE CRC-32 of s — the one zip, gzip and PNG use.
 76func Checksum(s string) uint32 { return ChecksumWith(s, ieeeTable) }
 77
 78// Hex renders a checksum as eight lowercase hex digits, zero-padded, which is
 79// how CRCs are conventionally shown.
 80func Hex(crc uint32) string {
 81	const digits = "0123456789abcdef"
 82	var b [8]byte
 83	for i := 7; i >= 0; i-- {
 84		b[i] = digits[crc&0xF]
 85		crc >>= 4
 86	}
 87	return string(b[:])
 88}
 89
 90// ChecksumHex is Checksum rendered with Hex.
 91func ChecksumHex(s string) string { return Hex(Checksum(s)) }
 92
 93// Verify reports whether s has the expected checksum.
 94func Verify(s string, expected uint32) bool { return Checksum(s) == expected }
 95
 96// Split returns the checksum of each line of s, in order.
 97func Split(s string) []string {
 98	out := []string{}
 99	for _, line := range strings.Split(s, "\n") {
100		out = append(out, ChecksumHex(line))
101	}
102	return out
103}