volumen/internal/qrcode/galois.go

// Copyright (c) 2026 Petr Balvín <opensource@petrbalvin.org> (https://petrbalvin.org)
// SPDX-License-Identifier: PolyForm-Noncommercial-1.0.0

package qrcode

// Galois field arithmetic over GF(256) with the QR field polynomial
// 0x11D: log and antilog tables built once at init, and the
// Reed-Solomon remainder the annex specifies for error level M.
var (
	gfLog  [256]byte
	gfAnt  [256]byte
	rsPoly [][]byte // generator of degree i, index ecc length
)

func init() {
	x := 1
	for i := range 255 {
		gfAnt[i] = byte(x)
		gfLog[x] = byte(i)
		x <<= 1
		if x&0x100 != 0 {
			x ^= 0x11D
		}
	}
	// Degrees the supported versions need: level M ecc sizes run from
	// 10 to 30 codewords per block.
	rsPoly = make([][]byte, 31)
	rsPoly[0] = []byte{1}
	for d := 1; d < len(rsPoly); d++ {
		rsPoly[d] = polyMul(rsPoly[d-1], []byte{1, gfAnt[d-1]})
	}
}

func gfMul(a, b byte) byte {
	if a == 0 || b == 0 {
		return 0
	}
	return gfAnt[(int(gfLog[a])+int(gfLog[b]))%255]
}

func polyMul(a, b []byte) []byte {
	out := make([]byte, len(a)+len(b)-1)
	for i, av := range a {
		for j, bv := range b {
			out[i+j] ^= gfMul(av, bv)
		}
	}
	return out
}

// rsRemainder divides data by the generator of the given degree and
// returns the remainder, the error correction codewords.
func rsRemainder(data []byte, degree int) []byte {
	gen := rsPoly[degree]
	rem := make([]byte, degree)
	for _, b := range data {
		factor := b ^ rem[0]
		copy(rem, rem[1:])
		rem[degree-1] = 0
		if factor != 0 {
			for i, g := range gen[1:] {
				rem[i] ^= gfMul(g, factor)
			}
		}
	}
	return rem
}

// codewords packs the payload and returns the interleaved stream of
// data and error correction codewords the symbol carries.
func codewords(text []byte, version int) []byte {
	shapes, counts := blocks[version-1].shapes, blocks[version-1].counts
	dataCodewords := 0
	blockCount := 0
	for i, shape := range shapes {
		dataCodewords += shape.data * counts[i]
		blockCount += counts[i]
	}

	// The bit stream: mode, count, bytes, terminator, byte alignment
	// and the alternating pad bytes.
	var bit buf
	bit.push(4, 4) // byte mode
	if version >= 10 {
		bit.push(uint(len(text)), 16)
	} else {
		bit.push(uint(len(text)), 8)
	}
	for _, b := range text {
		bit.push(uint(b), 8)
	}
	bit.push(0, min(4, dataCodewords*8-bit.len()))
	bit.align()
	stream := bit.bytes()
	for len(stream) < dataCodewords {
		stream = append(stream, 0xEC, 0x11)
	}
	stream = stream[:dataCodewords]

	// Split into blocks, correct each, then interleave data and error
	// codewords the way the symbol reads them.
	type rsBlock struct {
		data []byte
		ecc  []byte
	}
	var list []rsBlock
	offset := 0
	for i, shape := range shapes {
		for c := 0; c < counts[i]; c++ {
			data := append([]byte(nil), stream[offset:offset+shape.data]...)
			offset += shape.data
			list = append(list, rsBlock{data: data, ecc: rsRemainder(data, shape.total-shape.data)})
		}
	}
	out := make([]byte, 0, dataCodewords+blockCount*(shapes[0].total-shapes[0].data))
	maxData := 0
	for _, shape := range shapes {
		maxData = max(maxData, shape.data)
	}
	for i := 0; i < maxData; i++ {
		for _, b := range list {
			if i < len(b.data) {
				out = append(out, b.data[i])
			}
		}
	}
	maxEcc := 0
	for _, b := range list {
		maxEcc = max(maxEcc, len(b.ecc))
	}
	for i := 0; i < maxEcc; i++ {
		for _, b := range list {
			if i < len(b.ecc) {
				out = append(out, b.ecc[i])
			}
		}
	}
	return out
}

// buf is the bit-level head of the codeword stream.
type buf struct {
	b     []byte
	nbits int
}

func (b *buf) push(v uint, n int) {
	for i := n - 1; i >= 0; i-- {
		if b.nbits%8 == 0 {
			b.b = append(b.b, 0)
		}
		if v&(1<<uint(i)) != 0 {
			b.b[len(b.b)-1] |= 1 << uint(7-b.nbits%8)
		}
		b.nbits++
	}
}

func (b *buf) len() int      { return b.nbits }
func (b *buf) align()        {} // push already writes byte-aligned bytes
func (b *buf) bytes() []byte { return b.b }