package main

// QR Code encoder — implements ISO/IEC 18004 byte-mode encoding.
// Supports versions 1..40 and error correction levels L, M, Q, H.
//
// Pipeline:
//   data bytes → bit stream (mode + count + payload + terminator + padding)
//              → split into RS blocks → append EC codewords → interleave
//              → place function patterns in matrix
//              → place data codewords via snake walk
//              → apply best of 8 masks, rewrite format info
//              → emit SVG
//
// Matrix is two flat byte slices: `mod` holds module color (0 white, 1 black)
// and `fn` marks reserved positions (function patterns) so the snake walk and
// masking skip them.

// ============================================================================
// GF(256) Galois field — primitive polynomial 0x11d (x^8+x^4+x^3+x^2+1), α=2.
// ============================================================================

var (
	gfExp    [512]byte
	gfLog    [256]byte
	gfTables bool
)

// gfBuild fills the log/anti-log tables once. gfExp is doubled in length so
// gfMul never needs a modulo.
func gfBuild() {
	if gfTables {
		return
	}
	gfTables = true
	x := 1
	for i := 0; i < 255; i++ {
		gfExp[i] = byte(x)
		gfLog[x] = byte(i)
		x <<= 1
		if x&0x100 != 0 {
			x ^= 0x11d
		}
	}
	for i := 255; i < 512; i++ {
		gfExp[i] = gfExp[i-255]
	}
}

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

// rsGen returns the generator polynomial for nc EC codewords, as
//   g(x) = (x+α^0)(x+α^1)...(x+α^(nc-1))
// stored high-degree first: g[0] = x^nc coefficient (always 1),
// g[nc] = constant term.
func rsGen(nc int) []byte {
	gfBuild()
	g := []byte{:nc + 1}
	g[0] = 1
	length := 1
	for i := 0; i < nc; i++ {
		ai := gfExp[i]
		// Multiply g by (x + α^i). New degree is length.
		// new[j] = old[j] ^ α^i * old[j-1], with old[-1] = old[length] = 0.
		// Process right-to-left so we don't clobber old values.
		g[length] = gfMul(ai, g[length-1])
		for j := length - 1; j > 0; j-- {
			g[j] = g[j] ^ gfMul(ai, g[j-1])
		}
		length++
	}
	return g
}

// rsRemainder computes the RS remainder of `data` for a generator of degree
// nc, returning nc check bytes. This is classical polynomial long division.
func rsRemainder(data []byte, nc int) []byte {
	if nc == 0 {
		return []byte{:0}
	}
	g := rsGen(nc)
	// Augment data with nc zeros, divide by g, remainder sits in the tail.
	buf := []byte{:len(data) + nc}
	copy(buf, data)
	for i := 0; i < len(data); i++ {
		lead := buf[i]
		if lead == 0 {
			continue
		}
		// Subtract lead*g aligned at i. g[0]=1 so buf[i] zeroes.
		for j := 0; j <= nc; j++ {
			buf[i+j] ^= gfMul(lead, g[j])
		}
	}
	return buf[len(data):]
}

// ============================================================================
// QR standard tables (ISO/IEC 18004)
// ============================================================================

// Level indices. The on-wire format-info encoding uses a different permutation
// (L=01, M=00, Q=11, H=10); see formatBits.
const (
	qrLevelL = 0
	qrLevelM = 1
	qrLevelQ = 2
	qrLevelH = 3
)

// qrBlockInfo: one (version, level) RS block configuration.
// `nblock` is the total block count; `ecLen` the EC codewords per block.
// Per-block data lengths are derived: short blocks have
//   short = (totalCw - ecLen*nblock) / nblock
// data codewords, and the last `long = (totalCw - ecLen*nblock) % nblock`
// blocks have one extra data codeword each.
type qrBlockInfo struct {
	nblock int
	ecLen  int
}

type qrVersionInfo struct {
	totalCw int            // total codewords (data + EC)
	levels  [4]qrBlockInfo // indexed by qrLevel{L,M,Q,H}
}

// qrVersions[v] for v=1..40 holds the spec's Table 9 values.
// Index 0 is unused.
var qrVersions = [41]qrVersionInfo{
	{},
	{26, [4]qrBlockInfo{{1, 7}, {1, 10}, {1, 13}, {1, 17}}},     // 1
	{44, [4]qrBlockInfo{{1, 10}, {1, 16}, {1, 22}, {1, 28}}},    // 2
	{70, [4]qrBlockInfo{{1, 15}, {1, 26}, {2, 18}, {2, 22}}},    // 3
	{100, [4]qrBlockInfo{{1, 20}, {2, 18}, {2, 26}, {4, 16}}},   // 4
	{134, [4]qrBlockInfo{{1, 26}, {2, 24}, {4, 18}, {4, 22}}},   // 5
	{172, [4]qrBlockInfo{{2, 18}, {4, 16}, {4, 24}, {4, 28}}},   // 6
	{196, [4]qrBlockInfo{{2, 20}, {4, 18}, {6, 18}, {5, 26}}},   // 7
	{242, [4]qrBlockInfo{{2, 24}, {4, 22}, {6, 22}, {6, 26}}},   // 8
	{292, [4]qrBlockInfo{{2, 30}, {5, 22}, {8, 20}, {8, 24}}},   // 9
	{346, [4]qrBlockInfo{{4, 18}, {5, 26}, {8, 24}, {8, 28}}},   // 10
	{404, [4]qrBlockInfo{{4, 20}, {5, 30}, {8, 28}, {11, 24}}},  // 11
	{466, [4]qrBlockInfo{{4, 24}, {8, 22}, {10, 26}, {11, 28}}}, // 12
	{532, [4]qrBlockInfo{{4, 26}, {9, 22}, {12, 24}, {16, 22}}}, // 13
	{581, [4]qrBlockInfo{{4, 30}, {9, 24}, {16, 20}, {16, 24}}}, // 14
	{655, [4]qrBlockInfo{{6, 22}, {10, 24}, {12, 30}, {18, 24}}}, // 15
	{733, [4]qrBlockInfo{{6, 24}, {10, 28}, {17, 24}, {16, 30}}}, // 16
	{815, [4]qrBlockInfo{{6, 28}, {11, 28}, {16, 28}, {19, 28}}}, // 17
	{901, [4]qrBlockInfo{{6, 30}, {13, 26}, {18, 28}, {21, 28}}}, // 18
	{991, [4]qrBlockInfo{{7, 28}, {14, 26}, {21, 26}, {25, 26}}}, // 19
	{1085, [4]qrBlockInfo{{8, 28}, {16, 26}, {20, 30}, {25, 28}}}, // 20
	{1156, [4]qrBlockInfo{{8, 28}, {17, 26}, {23, 28}, {25, 30}}}, // 21
	{1258, [4]qrBlockInfo{{9, 28}, {17, 28}, {23, 30}, {34, 24}}}, // 22
	{1364, [4]qrBlockInfo{{9, 30}, {18, 28}, {25, 30}, {30, 30}}}, // 23
	{1474, [4]qrBlockInfo{{10, 30}, {20, 28}, {27, 30}, {32, 30}}}, // 24
	{1588, [4]qrBlockInfo{{12, 26}, {21, 28}, {29, 30}, {35, 30}}}, // 25
	{1706, [4]qrBlockInfo{{12, 28}, {23, 28}, {34, 28}, {37, 30}}}, // 26
	{1828, [4]qrBlockInfo{{12, 30}, {25, 28}, {34, 30}, {40, 30}}}, // 27
	{1921, [4]qrBlockInfo{{13, 30}, {26, 28}, {35, 30}, {42, 30}}}, // 28
	{2051, [4]qrBlockInfo{{14, 30}, {28, 28}, {38, 30}, {45, 30}}}, // 29
	{2185, [4]qrBlockInfo{{15, 30}, {29, 28}, {40, 30}, {48, 30}}}, // 30
	{2323, [4]qrBlockInfo{{16, 30}, {31, 28}, {43, 30}, {51, 30}}}, // 31
	{2465, [4]qrBlockInfo{{17, 30}, {33, 28}, {45, 30}, {54, 30}}}, // 32
	{2611, [4]qrBlockInfo{{18, 30}, {35, 28}, {48, 30}, {57, 30}}}, // 33
	{2761, [4]qrBlockInfo{{19, 30}, {37, 28}, {51, 30}, {60, 30}}}, // 34
	{2876, [4]qrBlockInfo{{19, 30}, {38, 28}, {53, 30}, {63, 30}}}, // 35
	{3034, [4]qrBlockInfo{{20, 30}, {40, 28}, {56, 30}, {66, 30}}}, // 36
	{3196, [4]qrBlockInfo{{21, 30}, {43, 28}, {59, 30}, {70, 30}}}, // 37
	{3362, [4]qrBlockInfo{{22, 30}, {45, 28}, {62, 30}, {74, 30}}}, // 38
	{3532, [4]qrBlockInfo{{24, 30}, {47, 28}, {65, 30}, {77, 30}}}, // 39
	{3706, [4]qrBlockInfo{{25, 30}, {49, 28}, {68, 30}, {81, 30}}}, // 40
}

// qrAlignPositions[v] is the list of alignment pattern center coordinates for
// version v. Both x and y use the same list (alignment grid is symmetric).
// Versions 1 has no alignment patterns.
var qrAlignPositions = [41][]int{
	{},                          // 0 unused
	{},                          // 1
	{6, 18},                     // 2
	{6, 22},                     // 3
	{6, 26},                     // 4
	{6, 30},                     // 5
	{6, 34},                     // 6
	{6, 22, 38},                 // 7
	{6, 24, 42},                 // 8
	{6, 26, 46},                 // 9
	{6, 28, 50},                 // 10
	{6, 30, 54},                 // 11
	{6, 32, 58},                 // 12
	{6, 34, 62},                 // 13
	{6, 26, 46, 66},             // 14
	{6, 26, 48, 70},             // 15
	{6, 26, 50, 74},             // 16
	{6, 30, 54, 78},             // 17
	{6, 30, 56, 82},             // 18
	{6, 30, 58, 86},             // 19
	{6, 34, 62, 90},             // 20
	{6, 28, 50, 72, 94},         // 21
	{6, 26, 50, 74, 98},         // 22
	{6, 30, 54, 78, 102},        // 23
	{6, 28, 54, 80, 106},        // 24
	{6, 32, 58, 84, 110},        // 25
	{6, 30, 58, 86, 114},        // 26
	{6, 34, 62, 90, 118},        // 27
	{6, 26, 50, 74, 98, 122},    // 28
	{6, 30, 54, 78, 102, 126},   // 29
	{6, 26, 52, 78, 104, 130},   // 30
	{6, 30, 56, 82, 108, 134},   // 31
	{6, 34, 60, 86, 112, 138},   // 32
	{6, 30, 58, 86, 114, 142},   // 33
	{6, 34, 62, 90, 118, 146},   // 34
	{6, 30, 54, 78, 102, 126, 150}, // 35
	{6, 24, 50, 76, 102, 128, 154}, // 36
	{6, 28, 54, 80, 106, 132, 158}, // 37
	{6, 32, 58, 84, 110, 136, 162}, // 38
	{6, 26, 54, 82, 110, 138, 166}, // 39
	{6, 30, 58, 86, 114, 142, 170}, // 40
}

// qrSize returns the module side length for a version.
func qrSize(v int) int { return 17 + 4*v }

// qrDataCodewords returns the number of data codewords (bytes) available at
// version v and level l, after subtracting the EC codewords.
func qrDataCodewords(v, l int) int {
	vi := qrVersions[v]
	lev := vi.levels[l]
	return vi.totalCw - lev.nblock*lev.ecLen
}

// ============================================================================
// Bit writer — appends bits MSB-first to a growing byte buffer.
// ============================================================================

type bitWriter struct {
	buf  []byte
	bits int // total bits written
}

// Write appends the low `n` bits of v to the buffer, MSB first (so that v's
// bit (n-1) becomes the next bit written).
func (w *bitWriter) Write(v uint32, n int) {
	for i := n - 1; i >= 0; i-- {
		if w.bits&7 == 0 {
			w.buf = append(w.buf, 0)
		}
		bit := byte((v >> uint(i)) & 1)
		w.buf[w.bits>>3] |= bit << uint(7-(w.bits&7))
		w.bits++
	}
}

// ============================================================================
// Byte-mode data stream: mode indicator + count + data + terminator + pad.
// ============================================================================

// qrEncodeByteStream emits a complete bit stream for byte-mode data at the
// given version and level. Returns a padded byte buffer of exactly the
// version's data-codeword length.
func qrEncodeByteStream(data []byte, v, l int) []byte {
	totalBytes := qrDataCodewords(v, l)
	totalBits := totalBytes * 8
	var w bitWriter

	// Mode indicator for 8-bit byte mode: 0100.
	w.Write(4, 4)

	// Character count indicator: 8 bits for v1..9, 16 bits for v10..40.
	countBits := 8
	if v >= 10 {
		countBits = 16
	}
	w.Write(uint32(len(data)), countBits)

	// Payload bytes.
	for i := 0; i < len(data); i++ {
		w.Write(uint32(data[i]), 8)
	}

	// Terminator: up to 4 zero bits, stop early if the buffer is full.
	term := totalBits - w.bits
	if term > 4 {
		term = 4
	}
	if term > 0 {
		w.Write(0, term)
	}

	// Pad to byte boundary with zeros.
	if w.bits&7 != 0 {
		w.Write(0, 8-(w.bits&7))
	}

	// Fill remaining bytes with the spec's alternating pad pattern.
	padA := byte(0xEC)
	padB := byte(0x11)
	for w.bits < totalBits {
		w.Write(uint32(padA), 8)
		padA, padB = padB, padA
	}

	// At this point w.buf is exactly totalBytes long.
	out := []byte{:totalBytes}
	copy(out, w.buf)
	return out
}

// ============================================================================
// RS-block split, EC, and interleave.
// ============================================================================

// qrBuildCodewords splits data into blocks per the (v, l) table, computes RS
// check codewords for each, and returns the interleaved codeword stream in
// the order required for placement.
func qrBuildCodewords(data []byte, v, l int) []byte {
	vi := qrVersions[v]
	lev := vi.levels[l]
	nblock := lev.nblock
	ne := lev.ecLen
	totalData := qrDataCodewords(v, l)

	// Short and long block sizes. Per spec, long blocks come *after* short
	// blocks in the source order, each with one additional data codeword.
	shortLen := totalData / nblock
	extra := totalData % nblock

	// Slice data into blocks, compute EC bytes for each.
	blockData := [][]byte{:nblock}
	blockEC := [][]byte{:nblock}
	off := 0
	for i := 0; i < nblock; i++ {
		dl := shortLen
		if i >= nblock-extra {
			dl++
		}
		blockData[i] = data[off : off+dl]
		blockEC[i] = rsRemainder(blockData[i], ne)
		off += dl
	}

	// Interleave data: take codeword 0 from every block, then codeword 1 from
	// every block, etc. Short blocks are skipped once exhausted.
	longLen := shortLen + 1
	out := []byte{:0:totalData + ne*nblock}
	for i := 0; i < longLen; i++ {
		for j := 0; j < nblock; j++ {
			if i < len(blockData[j]) {
				out = append(out, blockData[j][i])
			}
		}
	}
	// Interleave EC. All blocks have the same EC length, so no skipping.
	for i := 0; i < ne; i++ {
		for j := 0; j < nblock; j++ {
			out = append(out, blockEC[j][i])
		}
	}
	return out
}

// ============================================================================
// QR matrix — flat byte storage plus a "reserved" (function pattern) mask.
// ============================================================================

type qrMatrix struct {
	n   int
	mod []byte // size*size modules, 0=white, 1=black
	fn  []byte // size*size reserved flags, 1=function pattern
}

func newQRMatrix(n int) *qrMatrix {
	return &qrMatrix{n: n, mod: []byte{:n * n}, fn: []byte{:n * n}}
}

func (m *qrMatrix) get(x, y int) byte         { return m.mod[y*m.n+x] }
func (m *qrMatrix) set(x, y int, v byte)      { m.mod[y*m.n+x] = v }
func (m *qrMatrix) isFn(x, y int) bool        { return m.fn[y*m.n+x] != 0 }
func (m *qrMatrix) setFn(x, y int, v byte)    { m.mod[y*m.n+x] = v; m.fn[y*m.n+x] = 1 }
func (m *qrMatrix) reserve(x, y int)          { m.fn[y*m.n+x] = 1 }

// placeFinder draws a 7x7 finder pattern with top-left at (x0, y0). Also
// carves out the 1-module-wide white separator around the pattern (only the
// sides that are inside the matrix).
func (m *qrMatrix) placeFinder(x0, y0 int) {
	// The finder: outer 6x6 black border, 1-wide white inside, 3x3 black core.
	for dy := -1; dy <= 7; dy++ {
		for dx := -1; dx <= 7; dx++ {
			x := x0 + dx
			y := y0 + dy
			if x < 0 || x >= m.n || y < 0 || y >= m.n {
				continue
			}
			if dx == -1 || dx == 7 || dy == -1 || dy == 7 {
				// Separator: white + reserved.
				m.setFn(x, y, 0)
				continue
			}
			black := dx == 0 || dx == 6 || dy == 0 || dy == 6 ||
				(dx >= 2 && dx <= 4 && dy >= 2 && dy <= 4)
			v := byte(0)
			if black {
				v = 1
			}
			m.setFn(x, y, v)
		}
	}
}

// placeAlignment draws a 5x5 alignment pattern centered at (cx, cy).
func (m *qrMatrix) placeAlignment(cx, cy int) {
	for dy := -2; dy <= 2; dy++ {
		for dx := -2; dx <= 2; dx++ {
			x := cx + dx
			y := cy + dy
			black := dx == -2 || dx == 2 || dy == -2 || dy == 2 || (dx == 0 && dy == 0)
			v := byte(0)
			if black {
				v = 1
			}
			m.setFn(x, y, v)
		}
	}
}

// placeTiming draws the horizontal and vertical timing patterns on row 6 and
// column 6, skipping modules already reserved (finders and their separators).
func (m *qrMatrix) placeTiming() {
	for i := 0; i < m.n; i++ {
		v := byte(0)
		if i&1 == 0 {
			v = 1
		}
		if !m.isFn(i, 6) {
			m.setFn(i, 6, v)
		}
		if !m.isFn(6, i) {
			m.setFn(6, i, v)
		}
	}
}

// reserveFormatAreas marks the format-info positions as reserved (so the
// snake walk skips them). Actual values are written later in writeFormat.
// Also reserves the single "dark module".
func (m *qrMatrix) reserveFormatAreas() {
	// Around the top-left finder: column 8, rows 0..8 and row 8, cols 0..8.
	for i := 0; i < 9; i++ {
		m.reserve(8, i)
		m.reserve(i, 8)
	}
	// Along row 8 on the right side: cols n-8..n-1.
	for i := 0; i < 8; i++ {
		m.reserve(m.n-1-i, 8)
	}
	// Along column 8 at the bottom: rows n-7..n-1.
	for i := 0; i < 7; i++ {
		m.reserve(8, m.n-1-i)
	}
	// Dark module at (8, n-8).
	m.setFn(8, m.n-8, 1)
}

// reserveVersionAreas marks the version-info blocks (versions >= 7).
func (m *qrMatrix) reserveVersionAreas() {
	// Top-right block: rows 0..5, cols n-11..n-9.
	for y := 0; y < 6; y++ {
		for x := m.n - 11; x < m.n - 8; x++ {
			m.reserve(x, y)
		}
	}
	// Bottom-left block: cols 0..5, rows n-11..n-9.
	for y := m.n - 11; y < m.n - 8; y++ {
		for x := 0; x < 6; x++ {
			m.reserve(x, y)
		}
	}
}

// ============================================================================
// Format and version information (BCH-protected metadata).
// ============================================================================

// formatBits returns the 15-bit format info for level l and mask m, already
// BCH-encoded and XOR-masked per spec. Bit 0 is the LSB.
func formatBits(l, mask int) uint32 {
	// Spec level encoding: L=01, M=00, Q=11, H=10.
	levelCode := [4]uint32{1, 0, 3, 2}
	data := (levelCode[l] << 3) | uint32(mask)
	// BCH(15, 5) with generator 0x537 (x^10+x^8+x^5+x^4+x^2+x+1).
	rem := data << 10
	for i := 14; i >= 10; i-- {
		if rem&(1<<uint(i)) != 0 {
			rem ^= 0x537 << uint(i-10)
		}
	}
	bits := (data << 10) | rem
	return bits ^ 0x5412 // XOR mask forces non-zero output
}

// writeFormat places the 15 format-info bits in both of their locations.
func (m *qrMatrix) writeFormat(l, mask int) {
	bits := formatBits(l, mask)
	// Copy 1: around the top-left finder.
	// Bits 0..5 along column 8, rows 0..5.
	for i := 0; i < 6; i++ {
		m.setFn(8, i, byte((bits>>uint(i))&1))
	}
	// Bit 6 at (8, 7) — skipping row 6 (timing).
	m.setFn(8, 7, byte((bits>>6)&1))
	// Bit 7 at (8, 8), bit 8 at (7, 8).
	m.setFn(8, 8, byte((bits>>7)&1))
	m.setFn(7, 8, byte((bits>>8)&1))
	// Bits 9..14 along row 8, cols 5..0 — skipping col 6 (timing).
	for i := 9; i < 15; i++ {
		m.setFn(14-i, 8, byte((bits>>uint(i))&1))
	}
	// Copy 2: split between top-right and bottom-left finder sides.
	// Bits 0..7 along row 8, cols n-1..n-8.
	for i := 0; i < 8; i++ {
		m.setFn(m.n-1-i, 8, byte((bits>>uint(i))&1))
	}
	// Bits 8..14 along column 8, rows n-7..n-1.
	for i := 8; i < 15; i++ {
		m.setFn(8, m.n-15+i, byte((bits>>uint(i))&1))
	}
	// Dark module (always 1).
	m.setFn(8, m.n-8, 1)
}

// versionBits returns the 18-bit version info for v (>=7), BCH-encoded.
func versionBits(v int) uint32 {
	data := uint32(v)
	// BCH(18, 6) with generator 0x1F25 (x^12+x^11+x^10+x^9+x^8+x^5+x^2+1).
	rem := data << 12
	for i := 17; i >= 12; i-- {
		if rem&(1<<uint(i)) != 0 {
			rem ^= 0x1F25 << uint(i-12)
		}
	}
	return (data << 12) | rem
}

// writeVersion places version info (versions >=7 only) in both locations.
func (m *qrMatrix) writeVersion(v int) {
	if v < 7 {
		return
	}
	bits := versionBits(v)
	// Each block is 6 rows x 3 cols (or 3 rows x 6 cols). Bit 0 is the LSB.
	// Place bits[0..17] column by column.
	for i := 0; i < 18; i++ {
		bit := byte((bits >> uint(i)) & 1)
		a := i / 3
		b := i % 3
		// Top-right block: at (n-11+b, a).
		m.setFn(m.n-11+b, a, bit)
		// Bottom-left block: at (a, n-11+b).
		m.setFn(a, m.n-11+b, bit)
	}
}

// ============================================================================
// Snake walk for data placement.
// ============================================================================

// placeData writes interleaved codewords (MSB first within each byte) to the
// matrix, walking the standard snake pattern. Reserved positions are skipped.
// Any leftover modules at the end of the walk stay 0 ("remainder bits").
func (m *qrMatrix) placeData(codewords []byte) {
	n := m.n
	totalBits := len(codewords) * 8
	bitPos := 0
	upward := true

	// x = right column of the current 2-wide column pair, working right-to-left.
	x := n - 1
	for x > 0 {
		// The vertical timing column (col 6) is not a data column. When we
		// would land with col 6 as the right column of the pair, shift left
		// by one so the pair becomes (5, 4).
		if x == 6 {
			x = 5
		}
		for i := 0; i < n; i++ {
			y := n - 1 - i
			if !upward {
				y = i
			}
			// Right column of the pair, then left column.
			for dx := 0; dx < 2; dx++ {
				cx := x - dx
				if m.isFn(cx, y) {
					continue
				}
				if bitPos >= totalBits {
					continue
				}
				b := codewords[bitPos>>3]
				bit := (b >> uint(7-(bitPos&7))) & 1
				m.set(cx, y, bit)
				bitPos++
			}
		}
		upward = !upward
		x -= 2
	}
}

// ============================================================================
// Masking and penalty scoring.
// ============================================================================

// maskCond returns true for modules that should be flipped under the given
// mask pattern (x is column, y is row — spec uses (i=row, j=column)).
func maskCond(mask, x, y int) bool {
	switch mask {
	case 0:
		return (x+y)%2 == 0
	case 1:
		return y%2 == 0
	case 2:
		return x%3 == 0
	case 3:
		return (x+y)%3 == 0
	case 4:
		return (y/2+x/3)%2 == 0
	case 5:
		return (x*y)%2+(x*y)%3 == 0
	case 6:
		return ((x*y)%2+(x*y)%3)%2 == 0
	case 7:
		return ((x+y)%2+(x*y)%3)%2 == 0
	}
	return false
}

// applyMask XORs the mask pattern over every non-reserved module. Calling it
// again on the same matrix undoes the mask (XOR is self-inverse).
func (m *qrMatrix) applyMask(mask int) {
	for y := 0; y < m.n; y++ {
		for x := 0; x < m.n; x++ {
			if m.fn[y*m.n+x] != 0 {
				continue
			}
			if maskCond(mask, x, y) {
				m.mod[y*m.n+x] ^= 1
			}
		}
	}
}

// penalty computes the total mask penalty score per ISO/IEC 18004 section 8.3.
func (m *qrMatrix) penalty() int {
	n := m.n
	score := 0

	// Rule 1: runs of 5+ same-color modules in rows/columns.
	for y := 0; y < n; y++ {
		run := 1
		for x := 1; x < n; x++ {
			if m.get(x, y) == m.get(x-1, y) {
				run++
			} else {
				if run >= 5 {
					score += run - 2
				}
				run = 1
			}
		}
		if run >= 5 {
			score += run - 2
		}
	}
	for x := 0; x < n; x++ {
		run := 1
		for y := 1; y < n; y++ {
			if m.get(x, y) == m.get(x, y-1) {
				run++
			} else {
				if run >= 5 {
					score += run - 2
				}
				run = 1
			}
		}
		if run >= 5 {
			score += run - 2
		}
	}

	// Rule 2: 2x2 same-color blocks.
	for y := 0; y < n-1; y++ {
		for x := 0; x < n-1; x++ {
			v := m.get(x, y)
			if m.get(x+1, y) == v && m.get(x, y+1) == v && m.get(x+1, y+1) == v {
				score += 3
			}
		}
	}

	// Rule 3: 11-module finder-pattern lookalikes (1:1:3:1:1 plus 4 light).
	patA := [11]byte{1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0}
	patB := [11]byte{0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1}
	// Horizontal scan.
	for y := 0; y < n; y++ {
		for x := 0; x <= n-11; x++ {
			matchA := true
			matchB := true
			for i := 0; i < 11; i++ {
				v := m.get(x+i, y)
				if v != patA[i] {
					matchA = false
				}
				if v != patB[i] {
					matchB = false
				}
			}
			if matchA {
				score += 40
			}
			if matchB {
				score += 40
			}
		}
	}
	// Vertical scan.
	for x := 0; x < n; x++ {
		for y := 0; y <= n-11; y++ {
			matchA := true
			matchB := true
			for i := 0; i < 11; i++ {
				v := m.get(x, y+i)
				if v != patA[i] {
					matchA = false
				}
				if v != patB[i] {
					matchB = false
				}
			}
			if matchA {
				score += 40
			}
			if matchB {
				score += 40
			}
		}
	}

	// Rule 4: deviation of dark-module percentage from 50%.
	dark := 0
	total := n * n
	for i := 0; i < total; i++ {
		if m.mod[i] != 0 {
			dark++
		}
	}
	// |pct - 50| rounded down in units of 5, times 10.
	pct := dark * 100 / total
	dev := pct - 50
	if dev < 0 {
		dev = -dev
	}
	score += (dev / 5) * 10

	return score
}

// ============================================================================
// End-to-end encode — matrix build, mask selection.
// ============================================================================

// qrBuildMatrix creates a full QR matrix for (v, l) without yet applying a
// mask. Returns the matrix after function patterns and data have been placed.
func qrBuildMatrix(data []byte, v, l int) *qrMatrix {
	n := qrSize(v)
	m := newQRMatrix(n)

	// Function patterns first. Order matters: reserve format/version areas
	// before the snake walk so they're skipped.
	m.placeFinder(0, 0)
	m.placeFinder(n-7, 0)
	m.placeFinder(0, n-7)

	pos := qrAlignPositions[v]
	last := len(pos) - 1
	for i := 0; i <= last; i++ {
		for j := 0; j <= last; j++ {
			// Skip positions that would overlap a finder pattern.
			if (i == 0 && j == 0) ||
				(i == 0 && j == last) ||
				(i == last && j == 0) {
				continue
			}
			m.placeAlignment(pos[j], pos[i])
		}
	}
	m.placeTiming()
	m.reserveFormatAreas()
	if v >= 7 {
		m.reserveVersionAreas()
	}

	// Data stream + EC + interleave.
	stream := qrEncodeByteStream(data, v, l)
	codewords := qrBuildCodewords(stream, v, l)
	m.placeData(codewords)

	// Version info is fixed (no mask-dependent bits), write it now.
	m.writeVersion(v)
	return m
}

// qrEncode picks the best mask, writes format info, and returns the finished
// matrix. Tries all 8 masks and keeps the one with the lowest penalty score.
func qrEncode(data []byte, v, l int) *qrMatrix {
	var best *qrMatrix
	bestScore := -1
	for mask := 0; mask < 8; mask++ {
		m := qrBuildMatrix(data, v, l)
		m.applyMask(mask)
		m.writeFormat(l, mask)
		s := m.penalty()
		if bestScore < 0 || s < bestScore {
			bestScore = s
			best = m
		}
	}
	return best
}

// qrPickVersion finds the smallest version at level l that can hold data.
// Returns -1 if data is too long at this level even at version 40.
func qrPickVersion(dataLen, l int) int {
	for v := 1; v <= 40; v++ {
		countBits := 8
		if v >= 10 {
			countBits = 16
		}
		// Total bits required for mode+count+data (before terminator/padding).
		need := 4 + countBits + 8*dataLen
		cap := qrDataCodewords(v, l) * 8
		if need <= cap {
			return v
		}
	}
	return -1
}

// qrAuto picks the smallest version at the lowest EC level (L) that fits.
// Without a logo cutout there's no contiguous-loss risk to plan around, so
// 7% EC is plenty for on-screen display.
func qrAuto(data []byte) *qrMatrix {
	levels := [4]int{qrLevelL, qrLevelM, qrLevelQ, qrLevelH}
	for _, l := range levels {
		if v := qrPickVersion(len(data), l); v > 0 {
			return qrEncode(data, v, l)
		}
	}
	return nil
}

// ============================================================================
// SVG output.
// ============================================================================

// qrSVG renders `data` as an SVG string with each module rendered at modSize
// pixels per side. The output dimensions are exactly (n+8)*modSize square.
func qrSVG(data string, modSize int) string {
	m := qrAuto([]byte(data))
	if m == nil {
		return ""
	}
	n := m.n
	const quiet = 4 // spec-mandated quiet zone width (in modules)
	if modSize < 1 {
		modSize = 1
	}
	total := n + quiet*2
	svgSize := total * modSize

	svg := "<svg xmlns='http://www.w3.org/2000/svg' width='" | itoa(svgSize) |
		"' height='" | itoa(svgSize) | "' viewBox='0 0 " | itoa(svgSize) |
		" " | itoa(svgSize) | "' shape-rendering='crispEdges'>"
	svg = svg | "<rect width='100%' height='100%' fill='#ffffff'/>"

	for y := 0; y < n; y++ {
		for x := 0; x < n; x++ {
			if m.get(x, y) == 0 {
				continue
			}
			px := (x + quiet) * modSize
			py := (y + quiet) * modSize
			svg = svg | "<rect x='" | itoa(px) | "' y='" | itoa(py) |
				"' width='" | itoa(modSize) | "' height='" | itoa(modSize) |
				"' fill='#000000'/>"
		}
	}

	svg = svg | "</svg>"
	return svg
}