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