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 remainder4// of dividing it by a fixed polynomial. The bit-reflected, table-driven form5// implemented here is the one everything actually uses — zip, gzip, PNG, and6// 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, so15// anyone can craft a different message with the same checksum. Never use it to16// authenticate anything.17//18// A live demo of this package is at19// [r/moul/x/daily/crc32demo](/r/moul/x/daily/crc32demo/v0).20package crc322122import "strings"2324// Common reversed polynomials.25const (26 IEEE = 0xEDB8832027 Castagnoli = 0x82F63B7828 Koopman = 0xEB31D82E29)3031// Table is a precomputed byte-wise lookup table for one polynomial.32type Table [256]uint323334// MakeTable builds the lookup table for a reversed polynomial. Building it once35// and reusing it is the whole point of the table-driven form: it trades 1 KiB36// for eight bit-shifts per byte.37func MakeTable(poly uint32) *Table {38 var t Table39 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) ^ poly44 } else {45 crc >>= 146 }47 }48 t[i] = crc49 }50 return &t51}5253var ieeeTable = MakeTable(IEEE)5455// Update adds the bytes of s to a running checksum.56//57// Takes and returns the RAW register, not the final value: the caller-visible58// checksum is the register XOR 0xFFFFFFFF, so chaining Update calls on final59// 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 crc65}6667// Finalize turns a running register into the checksum.68func Finalize(crc uint32) uint32 { return crc ^ 0xFFFFFFFF }6970// 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}7475// Checksum returns the IEEE CRC-32 of s — the one zip, gzip and PNG use.76func Checksum(s string) uint32 { return ChecksumWith(s, ieeeTable) }7778// Hex renders a checksum as eight lowercase hex digits, zero-padded, which is79// how CRCs are conventionally shown.80func Hex(crc uint32) string {81 const digits = "0123456789abcdef"82 var b [8]byte83 for i := 7; i >= 0; i-- {84 b[i] = digits[crc&0xF]85 crc >>= 486 }87 return string(b[:])88}8990// ChecksumHex is Checksum rendered with Hex.91func ChecksumHex(s string) string { return Hex(Checksum(s)) }9293// Verify reports whether s has the expected checksum.94func Verify(s string, expected uint32) bool { return Checksum(s) == expected }9596// 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 out103}104Signatures reconstructed verbatim from vm/qfuncs — interface params keep their inline definitions.