1 package main
2
3 // QR Code encoder — implements ISO/IEC 18004 byte-mode encoding.
4 // Supports versions 1..40 and error correction levels L, M, Q, H.
5 //
6 // Pipeline:
7 // data bytes → bit stream (mode + count + payload + terminator + padding)
8 // → split into RS blocks → append EC codewords → interleave
9 // → place function patterns in matrix
10 // → place data codewords via snake walk
11 // → apply best of 8 masks, rewrite format info
12 // → emit SVG
13 //
14 // Matrix is two flat byte slices: `mod` holds module color (0 white, 1 black)
15 // and `fn` marks reserved positions (function patterns) so the snake walk and
16 // masking skip them.
17
18 // ============================================================================
19 // GF(256) Galois field — primitive polynomial 0x11d (x^8+x^4+x^3+x^2+1), α=2.
20 // ============================================================================
21
22 var (
23 gfExp [512]byte
24 gfLog [256]byte
25 gfTables bool
26 )
27
28 // gfBuild fills the log/anti-log tables once. gfExp is doubled in length so
29 // gfMul never needs a modulo.
30 func gfBuild() {
31 if gfTables {
32 return
33 }
34 gfTables = true
35 x := 1
36 for i := 0; i < 255; i++ {
37 gfExp[i] = byte(x)
38 gfLog[x] = byte(i)
39 x <<= 1
40 if x&0x100 != 0 {
41 x ^= 0x11d
42 }
43 }
44 for i := 255; i < 512; i++ {
45 gfExp[i] = gfExp[i-255]
46 }
47 }
48
49 func gfMul(a, b byte) byte {
50 if a == 0 || b == 0 {
51 return 0
52 }
53 return gfExp[int(gfLog[a])+int(gfLog[b])]
54 }
55
56 // rsGen returns the generator polynomial for nc EC codewords, as
57 // g(x) = (x+α^0)(x+α^1)...(x+α^(nc-1))
58 // stored high-degree first: g[0] = x^nc coefficient (always 1),
59 // g[nc] = constant term.
60 func rsGen(nc int) []byte {
61 gfBuild()
62 g := []byte{:nc + 1}
63 g[0] = 1
64 length := 1
65 for i := 0; i < nc; i++ {
66 ai := gfExp[i]
67 // Multiply g by (x + α^i). New degree is length.
68 // new[j] = old[j] ^ α^i * old[j-1], with old[-1] = old[length] = 0.
69 // Process right-to-left so we don't clobber old values.
70 g[length] = gfMul(ai, g[length-1])
71 for j := length - 1; j > 0; j-- {
72 g[j] = g[j] ^ gfMul(ai, g[j-1])
73 }
74 length++
75 }
76 return g
77 }
78
79 // rsRemainder computes the RS remainder of `data` for a generator of degree
80 // nc, returning nc check bytes. This is classical polynomial long division.
81 func rsRemainder(data []byte, nc int) []byte {
82 if nc == 0 {
83 return []byte{:0}
84 }
85 g := rsGen(nc)
86 // Augment data with nc zeros, divide by g, remainder sits in the tail.
87 buf := []byte{:len(data) + nc}
88 copy(buf, data)
89 for i := 0; i < len(data); i++ {
90 lead := buf[i]
91 if lead == 0 {
92 continue
93 }
94 // Subtract lead*g aligned at i. g[0]=1 so buf[i] zeroes.
95 for j := 0; j <= nc; j++ {
96 buf[i+j] ^= gfMul(lead, g[j])
97 }
98 }
99 return buf[len(data):]
100 }
101
102 // ============================================================================
103 // QR standard tables (ISO/IEC 18004)
104 // ============================================================================
105
106 // Level indices. The on-wire format-info encoding uses a different permutation
107 // (L=01, M=00, Q=11, H=10); see formatBits.
108 const (
109 qrLevelL = 0
110 qrLevelM = 1
111 qrLevelQ = 2
112 qrLevelH = 3
113 )
114
115 // qrBlockInfo: one (version, level) RS block configuration.
116 // `nblock` is the total block count; `ecLen` the EC codewords per block.
117 // Per-block data lengths are derived: short blocks have
118 // short = (totalCw - ecLen*nblock) / nblock
119 // data codewords, and the last `long = (totalCw - ecLen*nblock) % nblock`
120 // blocks have one extra data codeword each.
121 type qrBlockInfo struct {
122 nblock int
123 ecLen int
124 }
125
126 type qrVersionInfo struct {
127 totalCw int // total codewords (data + EC)
128 levels [4]qrBlockInfo // indexed by qrLevel{L,M,Q,H}
129 }
130
131 // qrVersions[v] for v=1..40 holds the spec's Table 9 values.
132 // Index 0 is unused.
133 var qrVersions = [41]qrVersionInfo{
134 {},
135 {26, [4]qrBlockInfo{{1, 7}, {1, 10}, {1, 13}, {1, 17}}}, // 1
136 {44, [4]qrBlockInfo{{1, 10}, {1, 16}, {1, 22}, {1, 28}}}, // 2
137 {70, [4]qrBlockInfo{{1, 15}, {1, 26}, {2, 18}, {2, 22}}}, // 3
138 {100, [4]qrBlockInfo{{1, 20}, {2, 18}, {2, 26}, {4, 16}}}, // 4
139 {134, [4]qrBlockInfo{{1, 26}, {2, 24}, {4, 18}, {4, 22}}}, // 5
140 {172, [4]qrBlockInfo{{2, 18}, {4, 16}, {4, 24}, {4, 28}}}, // 6
141 {196, [4]qrBlockInfo{{2, 20}, {4, 18}, {6, 18}, {5, 26}}}, // 7
142 {242, [4]qrBlockInfo{{2, 24}, {4, 22}, {6, 22}, {6, 26}}}, // 8
143 {292, [4]qrBlockInfo{{2, 30}, {5, 22}, {8, 20}, {8, 24}}}, // 9
144 {346, [4]qrBlockInfo{{4, 18}, {5, 26}, {8, 24}, {8, 28}}}, // 10
145 {404, [4]qrBlockInfo{{4, 20}, {5, 30}, {8, 28}, {11, 24}}}, // 11
146 {466, [4]qrBlockInfo{{4, 24}, {8, 22}, {10, 26}, {11, 28}}}, // 12
147 {532, [4]qrBlockInfo{{4, 26}, {9, 22}, {12, 24}, {16, 22}}}, // 13
148 {581, [4]qrBlockInfo{{4, 30}, {9, 24}, {16, 20}, {16, 24}}}, // 14
149 {655, [4]qrBlockInfo{{6, 22}, {10, 24}, {12, 30}, {18, 24}}}, // 15
150 {733, [4]qrBlockInfo{{6, 24}, {10, 28}, {17, 24}, {16, 30}}}, // 16
151 {815, [4]qrBlockInfo{{6, 28}, {11, 28}, {16, 28}, {19, 28}}}, // 17
152 {901, [4]qrBlockInfo{{6, 30}, {13, 26}, {18, 28}, {21, 28}}}, // 18
153 {991, [4]qrBlockInfo{{7, 28}, {14, 26}, {21, 26}, {25, 26}}}, // 19
154 {1085, [4]qrBlockInfo{{8, 28}, {16, 26}, {20, 30}, {25, 28}}}, // 20
155 {1156, [4]qrBlockInfo{{8, 28}, {17, 26}, {23, 28}, {25, 30}}}, // 21
156 {1258, [4]qrBlockInfo{{9, 28}, {17, 28}, {23, 30}, {34, 24}}}, // 22
157 {1364, [4]qrBlockInfo{{9, 30}, {18, 28}, {25, 30}, {30, 30}}}, // 23
158 {1474, [4]qrBlockInfo{{10, 30}, {20, 28}, {27, 30}, {32, 30}}}, // 24
159 {1588, [4]qrBlockInfo{{12, 26}, {21, 28}, {29, 30}, {35, 30}}}, // 25
160 {1706, [4]qrBlockInfo{{12, 28}, {23, 28}, {34, 28}, {37, 30}}}, // 26
161 {1828, [4]qrBlockInfo{{12, 30}, {25, 28}, {34, 30}, {40, 30}}}, // 27
162 {1921, [4]qrBlockInfo{{13, 30}, {26, 28}, {35, 30}, {42, 30}}}, // 28
163 {2051, [4]qrBlockInfo{{14, 30}, {28, 28}, {38, 30}, {45, 30}}}, // 29
164 {2185, [4]qrBlockInfo{{15, 30}, {29, 28}, {40, 30}, {48, 30}}}, // 30
165 {2323, [4]qrBlockInfo{{16, 30}, {31, 28}, {43, 30}, {51, 30}}}, // 31
166 {2465, [4]qrBlockInfo{{17, 30}, {33, 28}, {45, 30}, {54, 30}}}, // 32
167 {2611, [4]qrBlockInfo{{18, 30}, {35, 28}, {48, 30}, {57, 30}}}, // 33
168 {2761, [4]qrBlockInfo{{19, 30}, {37, 28}, {51, 30}, {60, 30}}}, // 34
169 {2876, [4]qrBlockInfo{{19, 30}, {38, 28}, {53, 30}, {63, 30}}}, // 35
170 {3034, [4]qrBlockInfo{{20, 30}, {40, 28}, {56, 30}, {66, 30}}}, // 36
171 {3196, [4]qrBlockInfo{{21, 30}, {43, 28}, {59, 30}, {70, 30}}}, // 37
172 {3362, [4]qrBlockInfo{{22, 30}, {45, 28}, {62, 30}, {74, 30}}}, // 38
173 {3532, [4]qrBlockInfo{{24, 30}, {47, 28}, {65, 30}, {77, 30}}}, // 39
174 {3706, [4]qrBlockInfo{{25, 30}, {49, 28}, {68, 30}, {81, 30}}}, // 40
175 }
176
177 // qrAlignPositions[v] is the list of alignment pattern center coordinates for
178 // version v. Both x and y use the same list (alignment grid is symmetric).
179 // Versions 1 has no alignment patterns.
180 var qrAlignPositions = [41][]int{
181 {}, // 0 unused
182 {}, // 1
183 {6, 18}, // 2
184 {6, 22}, // 3
185 {6, 26}, // 4
186 {6, 30}, // 5
187 {6, 34}, // 6
188 {6, 22, 38}, // 7
189 {6, 24, 42}, // 8
190 {6, 26, 46}, // 9
191 {6, 28, 50}, // 10
192 {6, 30, 54}, // 11
193 {6, 32, 58}, // 12
194 {6, 34, 62}, // 13
195 {6, 26, 46, 66}, // 14
196 {6, 26, 48, 70}, // 15
197 {6, 26, 50, 74}, // 16
198 {6, 30, 54, 78}, // 17
199 {6, 30, 56, 82}, // 18
200 {6, 30, 58, 86}, // 19
201 {6, 34, 62, 90}, // 20
202 {6, 28, 50, 72, 94}, // 21
203 {6, 26, 50, 74, 98}, // 22
204 {6, 30, 54, 78, 102}, // 23
205 {6, 28, 54, 80, 106}, // 24
206 {6, 32, 58, 84, 110}, // 25
207 {6, 30, 58, 86, 114}, // 26
208 {6, 34, 62, 90, 118}, // 27
209 {6, 26, 50, 74, 98, 122}, // 28
210 {6, 30, 54, 78, 102, 126}, // 29
211 {6, 26, 52, 78, 104, 130}, // 30
212 {6, 30, 56, 82, 108, 134}, // 31
213 {6, 34, 60, 86, 112, 138}, // 32
214 {6, 30, 58, 86, 114, 142}, // 33
215 {6, 34, 62, 90, 118, 146}, // 34
216 {6, 30, 54, 78, 102, 126, 150}, // 35
217 {6, 24, 50, 76, 102, 128, 154}, // 36
218 {6, 28, 54, 80, 106, 132, 158}, // 37
219 {6, 32, 58, 84, 110, 136, 162}, // 38
220 {6, 26, 54, 82, 110, 138, 166}, // 39
221 {6, 30, 58, 86, 114, 142, 170}, // 40
222 }
223
224 // qrSize returns the module side length for a version.
225 func qrSize(v int) int { return 17 + 4*v }
226
227 // qrDataCodewords returns the number of data codewords (bytes) available at
228 // version v and level l, after subtracting the EC codewords.
229 func qrDataCodewords(v, l int) int {
230 vi := qrVersions[v]
231 lev := vi.levels[l]
232 return vi.totalCw - lev.nblock*lev.ecLen
233 }
234
235 // ============================================================================
236 // Bit writer — appends bits MSB-first to a growing byte buffer.
237 // ============================================================================
238
239 type bitWriter struct {
240 buf []byte
241 bits int // total bits written
242 }
243
244 // Write appends the low `n` bits of v to the buffer, MSB first (so that v's
245 // bit (n-1) becomes the next bit written).
246 func (w *bitWriter) Write(v uint32, n int) {
247 for i := n - 1; i >= 0; i-- {
248 if w.bits&7 == 0 {
249 w.buf = append(w.buf, 0)
250 }
251 bit := byte((v >> uint(i)) & 1)
252 w.buf[w.bits>>3] |= bit << uint(7-(w.bits&7))
253 w.bits++
254 }
255 }
256
257 // ============================================================================
258 // Byte-mode data stream: mode indicator + count + data + terminator + pad.
259 // ============================================================================
260
261 // qrEncodeByteStream emits a complete bit stream for byte-mode data at the
262 // given version and level. Returns a padded byte buffer of exactly the
263 // version's data-codeword length.
264 func qrEncodeByteStream(data []byte, v, l int) []byte {
265 totalBytes := qrDataCodewords(v, l)
266 totalBits := totalBytes * 8
267 var w bitWriter
268
269 // Mode indicator for 8-bit byte mode: 0100.
270 w.Write(4, 4)
271
272 // Character count indicator: 8 bits for v1..9, 16 bits for v10..40.
273 countBits := 8
274 if v >= 10 {
275 countBits = 16
276 }
277 w.Write(uint32(len(data)), countBits)
278
279 // Payload bytes.
280 for i := 0; i < len(data); i++ {
281 w.Write(uint32(data[i]), 8)
282 }
283
284 // Terminator: up to 4 zero bits, stop early if the buffer is full.
285 term := totalBits - w.bits
286 if term > 4 {
287 term = 4
288 }
289 if term > 0 {
290 w.Write(0, term)
291 }
292
293 // Pad to byte boundary with zeros.
294 if w.bits&7 != 0 {
295 w.Write(0, 8-(w.bits&7))
296 }
297
298 // Fill remaining bytes with the spec's alternating pad pattern.
299 padA := byte(0xEC)
300 padB := byte(0x11)
301 for w.bits < totalBits {
302 w.Write(uint32(padA), 8)
303 padA, padB = padB, padA
304 }
305
306 // At this point w.buf is exactly totalBytes long.
307 out := []byte{:totalBytes}
308 copy(out, w.buf)
309 return out
310 }
311
312 // ============================================================================
313 // RS-block split, EC, and interleave.
314 // ============================================================================
315
316 // qrBuildCodewords splits data into blocks per the (v, l) table, computes RS
317 // check codewords for each, and returns the interleaved codeword stream in
318 // the order required for placement.
319 func qrBuildCodewords(data []byte, v, l int) []byte {
320 vi := qrVersions[v]
321 lev := vi.levels[l]
322 nblock := lev.nblock
323 ne := lev.ecLen
324 totalData := qrDataCodewords(v, l)
325
326 // Short and long block sizes. Per spec, long blocks come *after* short
327 // blocks in the source order, each with one additional data codeword.
328 shortLen := totalData / nblock
329 extra := totalData % nblock
330
331 // Slice data into blocks, compute EC bytes for each.
332 blockData := [][]byte{:nblock}
333 blockEC := [][]byte{:nblock}
334 off := 0
335 for i := 0; i < nblock; i++ {
336 dl := shortLen
337 if i >= nblock-extra {
338 dl++
339 }
340 blockData[i] = data[off : off+dl]
341 blockEC[i] = rsRemainder(blockData[i], ne)
342 off += dl
343 }
344
345 // Interleave data: take codeword 0 from every block, then codeword 1 from
346 // every block, etc. Short blocks are skipped once exhausted.
347 longLen := shortLen + 1
348 out := []byte{:0:totalData + ne*nblock}
349 for i := 0; i < longLen; i++ {
350 for j := 0; j < nblock; j++ {
351 if i < len(blockData[j]) {
352 out = append(out, blockData[j][i])
353 }
354 }
355 }
356 // Interleave EC. All blocks have the same EC length, so no skipping.
357 for i := 0; i < ne; i++ {
358 for j := 0; j < nblock; j++ {
359 out = append(out, blockEC[j][i])
360 }
361 }
362 return out
363 }
364
365 // ============================================================================
366 // QR matrix — flat byte storage plus a "reserved" (function pattern) mask.
367 // ============================================================================
368
369 type qrMatrix struct {
370 n int
371 mod []byte // size*size modules, 0=white, 1=black
372 fn []byte // size*size reserved flags, 1=function pattern
373 }
374
375 func newQRMatrix(n int) *qrMatrix {
376 return &qrMatrix{n: n, mod: []byte{:n * n}, fn: []byte{:n * n}}
377 }
378
379 func (m *qrMatrix) get(x, y int) byte { return m.mod[y*m.n+x] }
380 func (m *qrMatrix) set(x, y int, v byte) { m.mod[y*m.n+x] = v }
381 func (m *qrMatrix) isFn(x, y int) bool { return m.fn[y*m.n+x] != 0 }
382 func (m *qrMatrix) setFn(x, y int, v byte) { m.mod[y*m.n+x] = v; m.fn[y*m.n+x] = 1 }
383 func (m *qrMatrix) reserve(x, y int) { m.fn[y*m.n+x] = 1 }
384
385 // placeFinder draws a 7x7 finder pattern with top-left at (x0, y0). Also
386 // carves out the 1-module-wide white separator around the pattern (only the
387 // sides that are inside the matrix).
388 func (m *qrMatrix) placeFinder(x0, y0 int) {
389 // The finder: outer 6x6 black border, 1-wide white inside, 3x3 black core.
390 for dy := -1; dy <= 7; dy++ {
391 for dx := -1; dx <= 7; dx++ {
392 x := x0 + dx
393 y := y0 + dy
394 if x < 0 || x >= m.n || y < 0 || y >= m.n {
395 continue
396 }
397 if dx == -1 || dx == 7 || dy == -1 || dy == 7 {
398 // Separator: white + reserved.
399 m.setFn(x, y, 0)
400 continue
401 }
402 black := dx == 0 || dx == 6 || dy == 0 || dy == 6 ||
403 (dx >= 2 && dx <= 4 && dy >= 2 && dy <= 4)
404 v := byte(0)
405 if black {
406 v = 1
407 }
408 m.setFn(x, y, v)
409 }
410 }
411 }
412
413 // placeAlignment draws a 5x5 alignment pattern centered at (cx, cy).
414 func (m *qrMatrix) placeAlignment(cx, cy int) {
415 for dy := -2; dy <= 2; dy++ {
416 for dx := -2; dx <= 2; dx++ {
417 x := cx + dx
418 y := cy + dy
419 black := dx == -2 || dx == 2 || dy == -2 || dy == 2 || (dx == 0 && dy == 0)
420 v := byte(0)
421 if black {
422 v = 1
423 }
424 m.setFn(x, y, v)
425 }
426 }
427 }
428
429 // placeTiming draws the horizontal and vertical timing patterns on row 6 and
430 // column 6, skipping modules already reserved (finders and their separators).
431 func (m *qrMatrix) placeTiming() {
432 for i := 0; i < m.n; i++ {
433 v := byte(0)
434 if i&1 == 0 {
435 v = 1
436 }
437 if !m.isFn(i, 6) {
438 m.setFn(i, 6, v)
439 }
440 if !m.isFn(6, i) {
441 m.setFn(6, i, v)
442 }
443 }
444 }
445
446 // reserveFormatAreas marks the format-info positions as reserved (so the
447 // snake walk skips them). Actual values are written later in writeFormat.
448 // Also reserves the single "dark module".
449 func (m *qrMatrix) reserveFormatAreas() {
450 // Around the top-left finder: column 8, rows 0..8 and row 8, cols 0..8.
451 for i := 0; i < 9; i++ {
452 m.reserve(8, i)
453 m.reserve(i, 8)
454 }
455 // Along row 8 on the right side: cols n-8..n-1.
456 for i := 0; i < 8; i++ {
457 m.reserve(m.n-1-i, 8)
458 }
459 // Along column 8 at the bottom: rows n-7..n-1.
460 for i := 0; i < 7; i++ {
461 m.reserve(8, m.n-1-i)
462 }
463 // Dark module at (8, n-8).
464 m.setFn(8, m.n-8, 1)
465 }
466
467 // reserveVersionAreas marks the version-info blocks (versions >= 7).
468 func (m *qrMatrix) reserveVersionAreas() {
469 // Top-right block: rows 0..5, cols n-11..n-9.
470 for y := 0; y < 6; y++ {
471 for x := m.n - 11; x < m.n - 8; x++ {
472 m.reserve(x, y)
473 }
474 }
475 // Bottom-left block: cols 0..5, rows n-11..n-9.
476 for y := m.n - 11; y < m.n - 8; y++ {
477 for x := 0; x < 6; x++ {
478 m.reserve(x, y)
479 }
480 }
481 }
482
483 // ============================================================================
484 // Format and version information (BCH-protected metadata).
485 // ============================================================================
486
487 // formatBits returns the 15-bit format info for level l and mask m, already
488 // BCH-encoded and XOR-masked per spec. Bit 0 is the LSB.
489 func formatBits(l, mask int) uint32 {
490 // Spec level encoding: L=01, M=00, Q=11, H=10.
491 levelCode := [4]uint32{1, 0, 3, 2}
492 data := (levelCode[l] << 3) | uint32(mask)
493 // BCH(15, 5) with generator 0x537 (x^10+x^8+x^5+x^4+x^2+x+1).
494 rem := data << 10
495 for i := 14; i >= 10; i-- {
496 if rem&(1<<uint(i)) != 0 {
497 rem ^= 0x537 << uint(i-10)
498 }
499 }
500 bits := (data << 10) | rem
501 return bits ^ 0x5412 // XOR mask forces non-zero output
502 }
503
504 // writeFormat places the 15 format-info bits in both of their locations.
505 func (m *qrMatrix) writeFormat(l, mask int) {
506 bits := formatBits(l, mask)
507 // Copy 1: around the top-left finder.
508 // Bits 0..5 along column 8, rows 0..5.
509 for i := 0; i < 6; i++ {
510 m.setFn(8, i, byte((bits>>uint(i))&1))
511 }
512 // Bit 6 at (8, 7) — skipping row 6 (timing).
513 m.setFn(8, 7, byte((bits>>6)&1))
514 // Bit 7 at (8, 8), bit 8 at (7, 8).
515 m.setFn(8, 8, byte((bits>>7)&1))
516 m.setFn(7, 8, byte((bits>>8)&1))
517 // Bits 9..14 along row 8, cols 5..0 — skipping col 6 (timing).
518 for i := 9; i < 15; i++ {
519 m.setFn(14-i, 8, byte((bits>>uint(i))&1))
520 }
521 // Copy 2: split between top-right and bottom-left finder sides.
522 // Bits 0..7 along row 8, cols n-1..n-8.
523 for i := 0; i < 8; i++ {
524 m.setFn(m.n-1-i, 8, byte((bits>>uint(i))&1))
525 }
526 // Bits 8..14 along column 8, rows n-7..n-1.
527 for i := 8; i < 15; i++ {
528 m.setFn(8, m.n-15+i, byte((bits>>uint(i))&1))
529 }
530 // Dark module (always 1).
531 m.setFn(8, m.n-8, 1)
532 }
533
534 // versionBits returns the 18-bit version info for v (>=7), BCH-encoded.
535 func versionBits(v int) uint32 {
536 data := uint32(v)
537 // BCH(18, 6) with generator 0x1F25 (x^12+x^11+x^10+x^9+x^8+x^5+x^2+1).
538 rem := data << 12
539 for i := 17; i >= 12; i-- {
540 if rem&(1<<uint(i)) != 0 {
541 rem ^= 0x1F25 << uint(i-12)
542 }
543 }
544 return (data << 12) | rem
545 }
546
547 // writeVersion places version info (versions >=7 only) in both locations.
548 func (m *qrMatrix) writeVersion(v int) {
549 if v < 7 {
550 return
551 }
552 bits := versionBits(v)
553 // Each block is 6 rows x 3 cols (or 3 rows x 6 cols). Bit 0 is the LSB.
554 // Place bits[0..17] column by column.
555 for i := 0; i < 18; i++ {
556 bit := byte((bits >> uint(i)) & 1)
557 a := i / 3
558 b := i % 3
559 // Top-right block: at (n-11+b, a).
560 m.setFn(m.n-11+b, a, bit)
561 // Bottom-left block: at (a, n-11+b).
562 m.setFn(a, m.n-11+b, bit)
563 }
564 }
565
566 // ============================================================================
567 // Snake walk for data placement.
568 // ============================================================================
569
570 // placeData writes interleaved codewords (MSB first within each byte) to the
571 // matrix, walking the standard snake pattern. Reserved positions are skipped.
572 // Any leftover modules at the end of the walk stay 0 ("remainder bits").
573 func (m *qrMatrix) placeData(codewords []byte) {
574 n := m.n
575 totalBits := len(codewords) * 8
576 bitPos := 0
577 upward := true
578
579 // x = right column of the current 2-wide column pair, working right-to-left.
580 x := n - 1
581 for x > 0 {
582 // The vertical timing column (col 6) is not a data column. When we
583 // would land with col 6 as the right column of the pair, shift left
584 // by one so the pair becomes (5, 4).
585 if x == 6 {
586 x = 5
587 }
588 for i := 0; i < n; i++ {
589 y := n - 1 - i
590 if !upward {
591 y = i
592 }
593 // Right column of the pair, then left column.
594 for dx := 0; dx < 2; dx++ {
595 cx := x - dx
596 if m.isFn(cx, y) {
597 continue
598 }
599 if bitPos >= totalBits {
600 continue
601 }
602 b := codewords[bitPos>>3]
603 bit := (b >> uint(7-(bitPos&7))) & 1
604 m.set(cx, y, bit)
605 bitPos++
606 }
607 }
608 upward = !upward
609 x -= 2
610 }
611 }
612
613 // ============================================================================
614 // Masking and penalty scoring.
615 // ============================================================================
616
617 // maskCond returns true for modules that should be flipped under the given
618 // mask pattern (x is column, y is row — spec uses (i=row, j=column)).
619 func maskCond(mask, x, y int) bool {
620 switch mask {
621 case 0:
622 return (x+y)%2 == 0
623 case 1:
624 return y%2 == 0
625 case 2:
626 return x%3 == 0
627 case 3:
628 return (x+y)%3 == 0
629 case 4:
630 return (y/2+x/3)%2 == 0
631 case 5:
632 return (x*y)%2+(x*y)%3 == 0
633 case 6:
634 return ((x*y)%2+(x*y)%3)%2 == 0
635 case 7:
636 return ((x+y)%2+(x*y)%3)%2 == 0
637 }
638 return false
639 }
640
641 // applyMask XORs the mask pattern over every non-reserved module. Calling it
642 // again on the same matrix undoes the mask (XOR is self-inverse).
643 func (m *qrMatrix) applyMask(mask int) {
644 for y := 0; y < m.n; y++ {
645 for x := 0; x < m.n; x++ {
646 if m.fn[y*m.n+x] != 0 {
647 continue
648 }
649 if maskCond(mask, x, y) {
650 m.mod[y*m.n+x] ^= 1
651 }
652 }
653 }
654 }
655
656 // penalty computes the total mask penalty score per ISO/IEC 18004 section 8.3.
657 func (m *qrMatrix) penalty() int {
658 n := m.n
659 score := 0
660
661 // Rule 1: runs of 5+ same-color modules in rows/columns.
662 for y := 0; y < n; y++ {
663 run := 1
664 for x := 1; x < n; x++ {
665 if m.get(x, y) == m.get(x-1, y) {
666 run++
667 } else {
668 if run >= 5 {
669 score += run - 2
670 }
671 run = 1
672 }
673 }
674 if run >= 5 {
675 score += run - 2
676 }
677 }
678 for x := 0; x < n; x++ {
679 run := 1
680 for y := 1; y < n; y++ {
681 if m.get(x, y) == m.get(x, y-1) {
682 run++
683 } else {
684 if run >= 5 {
685 score += run - 2
686 }
687 run = 1
688 }
689 }
690 if run >= 5 {
691 score += run - 2
692 }
693 }
694
695 // Rule 2: 2x2 same-color blocks.
696 for y := 0; y < n-1; y++ {
697 for x := 0; x < n-1; x++ {
698 v := m.get(x, y)
699 if m.get(x+1, y) == v && m.get(x, y+1) == v && m.get(x+1, y+1) == v {
700 score += 3
701 }
702 }
703 }
704
705 // Rule 3: 11-module finder-pattern lookalikes (1:1:3:1:1 plus 4 light).
706 patA := [11]byte{1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0}
707 patB := [11]byte{0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1}
708 // Horizontal scan.
709 for y := 0; y < n; y++ {
710 for x := 0; x <= n-11; x++ {
711 matchA := true
712 matchB := true
713 for i := 0; i < 11; i++ {
714 v := m.get(x+i, y)
715 if v != patA[i] {
716 matchA = false
717 }
718 if v != patB[i] {
719 matchB = false
720 }
721 }
722 if matchA {
723 score += 40
724 }
725 if matchB {
726 score += 40
727 }
728 }
729 }
730 // Vertical scan.
731 for x := 0; x < n; x++ {
732 for y := 0; y <= n-11; y++ {
733 matchA := true
734 matchB := true
735 for i := 0; i < 11; i++ {
736 v := m.get(x, y+i)
737 if v != patA[i] {
738 matchA = false
739 }
740 if v != patB[i] {
741 matchB = false
742 }
743 }
744 if matchA {
745 score += 40
746 }
747 if matchB {
748 score += 40
749 }
750 }
751 }
752
753 // Rule 4: deviation of dark-module percentage from 50%.
754 dark := 0
755 total := n * n
756 for i := 0; i < total; i++ {
757 if m.mod[i] != 0 {
758 dark++
759 }
760 }
761 // |pct - 50| rounded down in units of 5, times 10.
762 pct := dark * 100 / total
763 dev := pct - 50
764 if dev < 0 {
765 dev = -dev
766 }
767 score += (dev / 5) * 10
768
769 return score
770 }
771
772 // ============================================================================
773 // End-to-end encode — matrix build, mask selection.
774 // ============================================================================
775
776 // qrBuildMatrix creates a full QR matrix for (v, l) without yet applying a
777 // mask. Returns the matrix after function patterns and data have been placed.
778 func qrBuildMatrix(data []byte, v, l int) *qrMatrix {
779 n := qrSize(v)
780 m := newQRMatrix(n)
781
782 // Function patterns first. Order matters: reserve format/version areas
783 // before the snake walk so they're skipped.
784 m.placeFinder(0, 0)
785 m.placeFinder(n-7, 0)
786 m.placeFinder(0, n-7)
787
788 pos := qrAlignPositions[v]
789 last := len(pos) - 1
790 for i := 0; i <= last; i++ {
791 for j := 0; j <= last; j++ {
792 // Skip positions that would overlap a finder pattern.
793 if (i == 0 && j == 0) ||
794 (i == 0 && j == last) ||
795 (i == last && j == 0) {
796 continue
797 }
798 m.placeAlignment(pos[j], pos[i])
799 }
800 }
801 m.placeTiming()
802 m.reserveFormatAreas()
803 if v >= 7 {
804 m.reserveVersionAreas()
805 }
806
807 // Data stream + EC + interleave.
808 stream := qrEncodeByteStream(data, v, l)
809 codewords := qrBuildCodewords(stream, v, l)
810 m.placeData(codewords)
811
812 // Version info is fixed (no mask-dependent bits), write it now.
813 m.writeVersion(v)
814 return m
815 }
816
817 // qrEncode picks the best mask, writes format info, and returns the finished
818 // matrix. Tries all 8 masks and keeps the one with the lowest penalty score.
819 func qrEncode(data []byte, v, l int) *qrMatrix {
820 var best *qrMatrix
821 bestScore := -1
822 for mask := 0; mask < 8; mask++ {
823 m := qrBuildMatrix(data, v, l)
824 m.applyMask(mask)
825 m.writeFormat(l, mask)
826 s := m.penalty()
827 if bestScore < 0 || s < bestScore {
828 bestScore = s
829 best = m
830 }
831 }
832 return best
833 }
834
835 // qrPickVersion finds the smallest version at level l that can hold data.
836 // Returns -1 if data is too long at this level even at version 40.
837 func qrPickVersion(dataLen, l int) int {
838 for v := 1; v <= 40; v++ {
839 countBits := 8
840 if v >= 10 {
841 countBits = 16
842 }
843 // Total bits required for mode+count+data (before terminator/padding).
844 need := 4 + countBits + 8*dataLen
845 cap := qrDataCodewords(v, l) * 8
846 if need <= cap {
847 return v
848 }
849 }
850 return -1
851 }
852
853 // qrAuto picks the smallest version at the lowest EC level (L) that fits.
854 // Without a logo cutout there's no contiguous-loss risk to plan around, so
855 // 7% EC is plenty for on-screen display.
856 func qrAuto(data []byte) *qrMatrix {
857 levels := [4]int{qrLevelL, qrLevelM, qrLevelQ, qrLevelH}
858 for _, l := range levels {
859 if v := qrPickVersion(len(data), l); v > 0 {
860 return qrEncode(data, v, l)
861 }
862 }
863 return nil
864 }
865
866 // ============================================================================
867 // SVG output.
868 // ============================================================================
869
870 // qrSVG renders `data` as an SVG string with each module rendered at modSize
871 // pixels per side. The output dimensions are exactly (n+8)*modSize square.
872 func qrSVG(data string, modSize int) string {
873 m := qrAuto([]byte(data))
874 if m == nil {
875 return ""
876 }
877 n := m.n
878 const quiet = 4 // spec-mandated quiet zone width (in modules)
879 if modSize < 1 {
880 modSize = 1
881 }
882 total := n + quiet*2
883 svgSize := total * modSize
884
885 svg := "<svg xmlns='http://www.w3.org/2000/svg' width='" | itoa(svgSize) |
886 "' height='" | itoa(svgSize) | "' viewBox='0 0 " | itoa(svgSize) |
887 " " | itoa(svgSize) | "' shape-rendering='crispEdges'>"
888 svg = svg | "<rect width='100%' height='100%' fill='#ffffff'/>"
889
890 for y := 0; y < n; y++ {
891 for x := 0; x < n; x++ {
892 if m.get(x, y) == 0 {
893 continue
894 }
895 px := (x + quiet) * modSize
896 py := (y + quiet) * modSize
897 svg = svg | "<rect x='" | itoa(px) | "' y='" | itoa(py) |
898 "' width='" | itoa(modSize) | "' height='" | itoa(modSize) |
899 "' fill='#000000'/>"
900 }
901 }
902
903 svg = svg | "</svg>"
904 return svg
905 }
906