Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_graphics/src/qr.rs

27.3 KiB, 78 runs

created by r1870400018:14232, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! A QR Code encoder: text or bytes in, a grid of dark and light modules out.
2//!
3//! This is a from-scratch, zero-dependency port of the algorithm published by Project Nayuki
4//! (MIT licence), whose structure this follows closely because the QR Code standard is a frozen
5//! ISO/IEC 18004 specification and correctness is the whole point. The encoder owns every step:
6//! byte-mode segment packing, Reed-Solomon error correction over GF(256), version selection,
7//! function-pattern layout, the eight data masks, and the penalty-driven choice between them.
8//!
9//! Only the module matrix is produced. Turning that grid into pixels, an SVG, or a printed square
10//! is a rendering concern that belongs to the caller, so no image output lives here.
11//!
12//! # What is encoded
13//!
14//! Byte mode (arbitrary octets, which for text means its UTF-8 bytes) is the only segment mode
15//! implemented, because the reason this exists is to carry short URLs for device pairing, and a
16//! URL is bytes. Numeric and alphanumeric modes, which pack decimal digits or a restricted
17//! 45-character set more tightly, are deliberately omitted; a caller who needs the extra density
18//! for a purely numeric payload is the signal to add them.
19//!
20//! # Example
21//!
22//! ```
23//! use oxedyne_fe2o3_graphics::qr::{encode, QrEcc};
24//!
25//! if let Ok(qr) = encode("https://example.org", QrEcc::Medium) {
26//! assert!(qr.get(0, 0)); // The finder pattern's outer ring is dark at the corner.
27//! assert!(qr.size() >= 21); // Version 1 is 21 by 21, and larger versions only grow.
28//! }
29//! ```
30//!
31//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
32//! Anthropic Claude
33
34use oxedyne_fe2o3_core::prelude::*;
35
36/// The four error-correction levels, from the least redundancy to the most.
37///
38/// A higher level survives more damage to the printed symbol but leaves fewer bits for the
39/// payload at a given version, so the encoder may have to step up to a larger version to fit the
40/// same data.
41#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
42pub enum QrEcc {
43 Low, // tolerates about 7% of the codewords corrupted
44 Medium, // about 15%
45 Quartile, // about 25%
46 High, // about 30%
47}
48
49impl QrEcc {
50
51 /// The index of this level in the standard's per-version parameter tables, where Low is 0 and
52 /// High is 3.
53 fn ordinal(self) -> usize {
54 match self {
55 Self::Low => 0,
56 Self::Medium => 1,
57 Self::Quartile => 2,
58 Self::High => 3,
59 }
60 }
61
62 /// The two-bit value that names this level inside the format-information field. Note that this
63 /// is not the same order as [`QrEcc::ordinal`]: the standard assigns Medium the value 0.
64 fn format_bits(self) -> u32 {
65 match self {
66 Self::Low => 1,
67 Self::Medium => 0,
68 Self::Quartile => 3,
69 Self::High => 2,
70 }
71 }
72}
73
74pub const MIN_VERSION: u8 = 1; // a 21 by 21 grid
75pub const MAX_VERSION: u8 = 40; // a 177 by 177 grid
76
77// The mask-penalty weights, one per rule.
78const PENALTY_N1: i32 = 3; // a run of five or more same-coloured modules in a line
79const PENALTY_N2: i32 = 3; // a two-by-two block of one colour
80const PENALTY_N3: i32 = 40; // a finder-like 1:1:3:1:1 pattern in a line
81const PENALTY_N4: i32 = 10; // each 5% the dark-module proportion strays from one half
82
83// Number of error-correction codewords in each block, indexed by [ecc ordinal][version], with
84// version 0 unused and set to an illegal value so a stray index is caught rather than silently
85// wrong.
86static ECC_CODEWORDS_PER_BLOCK: [[i8; 41]; 4] = [
87 // 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
88 [-1, 7, 10, 15, 20, 26, 18, 20, 24, 30, 18, 20, 24, 26, 30, 22, 24, 28, 30, 28, 28, 28, 28, 30, 30, 26, 28, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30], // Low
89 [-1, 10, 16, 26, 18, 24, 16, 18, 22, 22, 26, 30, 22, 22, 24, 24, 28, 28, 26, 26, 26, 26, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28], // Medium
90 [-1, 13, 22, 18, 26, 18, 24, 18, 22, 20, 24, 28, 26, 24, 20, 30, 24, 28, 28, 26, 30, 28, 30, 30, 30, 30, 28, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30], // Quartile
91 [-1, 17, 28, 22, 16, 22, 28, 26, 26, 24, 28, 24, 28, 22, 24, 24, 30, 28, 28, 26, 28, 30, 24, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30], // High
92];
93
94// Number of error-correction blocks, indexed by [ecc ordinal][version], with version 0 unused.
95static NUM_ERROR_CORRECTION_BLOCKS: [[i8; 41]; 4] = [
96 // 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
97 [-1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 4, 4, 4, 4, 4, 6, 6, 6, 6, 7, 8, 8, 9, 9, 10, 12, 12, 12, 13, 14, 15, 16, 17, 18, 19, 19, 20, 21, 22, 24, 25], // Low
98 [-1, 1, 1, 1, 2, 2, 4, 4, 4, 5, 5, 5, 8, 9, 9, 10, 10, 11, 13, 14, 16, 17, 17, 18, 20, 21, 23, 25, 26, 28, 29, 31, 33, 35, 37, 38, 40, 43, 45, 47, 49], // Medium
99 [-1, 1, 1, 2, 2, 4, 4, 6, 6, 8, 8, 8, 10, 12, 16, 12, 17, 16, 18, 21, 20, 23, 23, 25, 27, 29, 34, 34, 35, 38, 40, 43, 45, 48, 51, 53, 56, 59, 62, 65, 68], // Quartile
100 [-1, 1, 1, 2, 4, 4, 4, 5, 6, 8, 8, 11, 11, 16, 16, 18, 16, 19, 21, 25, 25, 25, 34, 30, 32, 35, 37, 40, 42, 45, 48, 51, 54, 57, 60, 63, 66, 70, 74, 77, 81], // High
101];
102
103/// A finished QR Code as a square grid of modules.
104///
105/// The grid alone is deliberately all this exposes: it is what a renderer needs, and everything
106/// used to build it (function-pattern bookkeeping, the codeword stream) is discarded once the
107/// modules are fixed.
108#[derive(Clone, Debug, PartialEq, Eq)]
109pub struct QrMatrix {
110 size: usize, // side length in modules, always odd, 21 to 177
111 mods: Vec<bool>, // row-major, size * size of them, true meaning dark
112 ver: u8, // 1 to 40
113 ecc: QrEcc, // the level actually used, which may exceed the one requested
114}
115
116impl QrMatrix {
117
118 /// The side length in modules.
119 pub fn size(&self) -> usize {
120 self.size
121 }
122
123 /// The version number, 1 to 40, where the side length is `version * 4 + 17`.
124 pub fn version(&self) -> u8 {
125 self.ver
126 }
127
128 /// May be higher than the level asked for, when the chosen version had spare capacity.
129 pub fn ecc(&self) -> QrEcc {
130 self.ecc
131 }
132
133 /// Is the module at column `x`, row `y` dark? Coordinates outside the grid are light,
134 /// matching the quiet zone a decoder assumes surrounds the symbol.
135 pub fn get(&self, x: usize, y: usize) -> bool {
136 if x >= self.size || y >= self.size {
137 return false;
138 }
139 self.mods[y * self.size + x]
140 }
141}
142
143/// Encodes text as a QR Code in byte mode, choosing the smallest version that fits at the given
144/// error-correction level and the mask with the lowest penalty.
145///
146/// The text is taken as its UTF-8 bytes. The error-correction level is a floor, not an exact
147/// setting: when the chosen version leaves room, the level is raised for free, so the returned
148/// [`QrMatrix::ecc`] may exceed `ecc`.
149pub fn encode(text: &str, ecc: QrEcc) -> Outcome<QrMatrix> {
150 encode_bytes(text.as_bytes(), ecc)
151}
152
153/// Encodes arbitrary bytes as a QR Code in byte mode. See [`encode`] for the version and mask
154/// selection, which is identical; this is the entry point when the payload is not text.
155pub fn encode_bytes(data: &[u8], ecc: QrEcc) -> Outcome<QrMatrix> {
156 encode_bytes_advanced(data, ecc, MIN_VERSION, MAX_VERSION, None, true)
157}
158
159/// Encodes bytes with full control over the version range, the mask, and error-correction
160/// boosting, for callers that need a specific symbol rather than the smallest convenient one.
161///
162/// * `minver` and `maxver` bound the version search, each in 1 to 40 with `minver <= maxver`.
163/// * `mask` forces one of the eight masks (0 to 7) when `Some`, or asks for automatic selection
164/// when `None`.
165/// * `boost` raises the error-correction level to fill spare capacity when true.
166pub fn encode_bytes_advanced(
167 data: &[u8],
168 ecc: QrEcc,
169 minver: u8,
170 maxver: u8,
171 mask: Option<u8>,
172 boost: bool,
173)
174 -> Outcome<QrMatrix>
175{
176 if minver < MIN_VERSION || maxver > MAX_VERSION || minver > maxver {
177 return Err(err!(
178 "The version range {} to {} lies outside 1 to 40, or is inverted.", minver, maxver;
179 Invalid, Input, Range));
180 }
181 if let Some(m) = mask {
182 if m > 7 {
183 return Err(err!(
184 "The mask {} is not one of the eight masks 0 to 7.", m;
185 Invalid, Input, Range));
186 }
187 }
188
189 // The bits a byte-mode segment occupies at a version depend only on the character-count field
190 // width, which itself depends on the version band, so widen the version until the data fits.
191 let mut ver = minver;
192 let used = loop {
193 let cap = res!(num_data_codewords(ver, ecc)) * 8; // Bits available.
194 let need = segment_bits(data.len(), ver); // Bits the segment needs.
195 if let Some(n) = need {
196 if n <= cap {
197 break n;
198 }
199 }
200 if ver >= maxver {
201 return Err(err!(
202 "{} bytes do not fit a QR Code of version {} at the requested error-correction \
203 level.", data.len(), maxver;
204 Input, Excessive, Size));
205 }
206 ver += 1;
207 };
208
209 // With the version fixed, spend any slack on stronger error correction, since a symbol that
210 // can fit more redundancy for free may as well.
211 let mut ecc = ecc;
212 if boost {
213 for cand in [QrEcc::Medium, QrEcc::Quartile, QrEcc::High] {
214 if used <= res!(num_data_codewords(ver, cand)) * 8 {
215 ecc = cand;
216 }
217 }
218 }
219
220 // Build the bit stream: the byte-mode indicator, the character count, then the data bytes.
221 let mut bits: Vec<bool> = Vec::new();
222 append_bits(&mut bits, 0x4, 4); // Byte-mode indicator.
223 append_bits(&mut bits, data.len() as u32, char_count_bits(ver));
224 for &b in data {
225 append_bits(&mut bits, u32::from(b), 8);
226 }
227
228 // Pad: a terminator of up to four zero bits, zeros to the next byte boundary, then the two
229 // alternating pad bytes until the data capacity is full.
230 let cap = res!(num_data_codewords(ver, ecc)) * 8;
231 let term = std::cmp::min(4, cap - bits.len());
232 append_bits(&mut bits, 0, term as u8);
233 let pad_to_byte = bits.len().wrapping_neg() & 7;
234 append_bits(&mut bits, 0, pad_to_byte as u8);
235 let mut pads = [0xEC_u32, 0x11].into_iter().cycle();
236 while bits.len() < cap {
237 if let Some(p) = pads.next() {
238 append_bits(&mut bits, p, 8);
239 }
240 }
241
242 // Pack the bits into codeword bytes, most-significant bit first.
243 let mut codewords = vec![0u8; bits.len() / 8];
244 for (i, bit) in bits.iter().enumerate() {
245 if *bit {
246 codewords[i >> 3] |= 1 << (7 - (i & 7));
247 }
248 }
249
250 build(ver, ecc, &codewords, mask)
251}
252
253/// Appends the low `len` bits of `val`, most-significant first.
254fn append_bits(bits: &mut Vec<bool>, val: u32, len: u8) {
255 let n = len as i32;
256 for i in (0 .. n).rev() {
257 bits.push((val >> i) & 1 != 0);
258 }
259}
260
261fn get_bit(x: u32, i: i32) -> bool {
262 (x >> i) & 1 != 0
263}
264
265/// The width of the byte-mode character-count field at a version: eight bits for versions 1 to 9,
266/// sixteen bits thereafter.
267fn char_count_bits(ver: u8) -> u8 {
268 if ver <= 9 { 8 } else { 16 }
269}
270
271/// The total bits a single byte-mode segment of `len` bytes occupies at a version, or `None` when
272/// the length overflows the character-count field.
273fn segment_bits(len: usize, ver: u8) -> Option<usize> {
274 let ccbits = char_count_bits(ver);
275 if len >= (1usize << ccbits) {
276 return None; // The length does not fit the field.
277 }
278 Some(4 + usize::from(ccbits) + len * 8)
279}
280
281/// The version is assumed valid, so the illegal padding entries are never reached.
282fn table_get(table: &[[i8; 41]; 4], ver: u8, ecc: QrEcc) -> usize {
283 let v = table[ecc.ordinal()][ver as usize];
284 if v < 0 { 0 } else { v as usize }
285}
286
287/// The number of bits a version can hold before error correction and function patterns are
288/// removed, that is, the count of data and error-correction modules together.
289fn num_raw_data_modules(ver: u8) -> usize {
290 let v = ver as usize;
291 let mut n = (16 * v + 128) * v + 64;
292 if v >= 2 {
293 let numalign = v / 7 + 2;
294 n -= (25 * numalign - 10) * numalign - 55;
295 if v >= 7 {
296 n -= 36; // Two version-information blocks of eighteen bits.
297 }
298 }
299 n
300}
301
302/// The number of eight-bit data codewords a version holds at an error-correction level, once the
303/// error-correction codewords are set aside.
304fn num_data_codewords(ver: u8, ecc: QrEcc) -> Outcome<usize> {
305 if !(MIN_VERSION ..= MAX_VERSION).contains(&ver) {
306 return Err(err!("Version {} lies outside 1 to 40.", ver; Invalid, Input, Range));
307 }
308 let raw = num_raw_data_modules(ver) / 8;
309 let ecc_words = table_get(&ECC_CODEWORDS_PER_BLOCK, ver, ecc)
310 * table_get(&NUM_ERROR_CORRECTION_BLOCKS, ver, ecc);
311 Ok(raw - ecc_words)
312}
313
314// -------------------------------------------------------------------------------------------------
315// Reed-Solomon error correction over GF(256) with the QR reducing polynomial x^8 + x^4 + x^3 +
316// x^2 + 1 (0x11D).
317// -------------------------------------------------------------------------------------------------
318
319/// Multiplies two field elements of GF(256) by Russian-peasant multiplication, reducing modulo
320/// the QR field's primitive polynomial.
321fn gf_mul(x: u8, y: u8) -> u8 {
322 let mut z: u8 = 0;
323 for i in (0 .. 8).rev() {
324 // Double, reducing when the high bit falls off, then add x when this bit of y is set.
325 z = (z << 1) ^ (((z >> 7) & 1) * 0x1D);
326 z ^= ((y >> i) & 1) * x;
327 }
328 z
329}
330
331/// Computes the divisor polynomial for `degree` error-correction codewords: the product of the
332/// monomials (x - r^i) for i in 0 to degree-1, with the leading coefficient of 1 dropped and the
333/// remaining coefficients stored from the second-highest degree down to the constant term.
334fn rs_divisor(degree: usize) -> Vec<u8> {
335 let mut result = vec![0u8; degree];
336 if degree == 0 {
337 return result;
338 }
339 result[degree - 1] = 1; // Start with the monomial x^0.
340 let mut root: u8 = 1;
341 for _ in 0 .. degree {
342 // Multiply the current product by (x - r^i).
343 for j in 0 .. result.len() {
344 result[j] = gf_mul(result[j], root);
345 if j + 1 < result.len() {
346 result[j] ^= result[j + 1];
347 }
348 }
349 root = gf_mul(root, 0x02);
350 }
351 result
352}
353
354/// Divides the data polynomial by the divisor and returns the remainder, which is the block's
355/// error-correction codewords.
356fn rs_remainder(data: &[u8], divisor: &[u8]) -> Vec<u8> {
357 let mut result = vec![0u8; divisor.len()];
358 for &b in data {
359 let factor = b ^ result.remove(0);
360 result.push(0);
361 for (x, &y) in result.iter_mut().zip(divisor.iter()) {
362 *x ^= gf_mul(y, factor);
363 }
364 }
365 result
366}
367
368// -------------------------------------------------------------------------------------------------
369// Grid construction.
370// -------------------------------------------------------------------------------------------------
371
372/// The working grid during construction: the modules plus a parallel record of which cells are
373/// function patterns and so must not carry data or be masked.
374struct Grid {
375 size: i32, // side length in modules
376 mods: Vec<bool>, // row-major, true meaning dark
377 func: Vec<bool>, // function module? same order as mods
378}
379
380impl Grid {
381
382 /// Creates an all-light grid with no function modules yet.
383 fn new(size: i32) -> Self {
384 let n = (size * size) as usize;
385 Self {
386 size,
387 mods: vec![false; n],
388 func: vec![false; n],
389 }
390 }
391
392 /// Reads a module, treating anything outside the grid as light.
393 fn get(&self, x: i32, y: i32) -> bool {
394 if x < 0 || y < 0 || x >= self.size || y >= self.size {
395 return false;
396 }
397 self.mods[(y * self.size + x) as usize]
398 }
399
400 /// Sets a module and records whether it is a function pattern. Coordinates outside the grid
401 /// are ignored, which lets a pattern near an edge be drawn with a single unconditional loop.
402 fn set(&mut self, x: i32, y: i32, dark: bool, is_func: bool) {
403 if x < 0 || y < 0 || x >= self.size || y >= self.size {
404 return;
405 }
406 let i = (y * self.size + x) as usize;
407 self.mods[i] = dark;
408 self.func[i] = is_func;
409 }
410
411 /// Is this cell a function module? Anything outside the grid counts as one.
412 fn is_func(&self, x: i32, y: i32) -> bool {
413 if x < 0 || y < 0 || x >= self.size || y >= self.size {
414 return true;
415 }
416 self.func[(y * self.size + x) as usize]
417 }
418}
419
420/// Assembles the whole symbol: draws the function patterns, interleaves the data with its error
421/// correction, lays the codewords into the data region, then applies and records the mask.
422fn build(ver: u8, ecc: QrEcc, codewords: &[u8], mask: Option<u8>)
423 -> Outcome<QrMatrix>
424{
425 let size = (ver as i32) * 4 + 17;
426 let mut g = Grid::new(size);
427
428 draw_function_patterns(&mut g, ver, ecc);
429 let all = res!(add_ecc_and_interleave(ver, ecc, codewords));
430 draw_codewords(&mut g, &all);
431
432 // Choose a mask: the requested one, or the lowest-penalty one found by trying all eight.
433 let chosen = match mask {
434 Some(m) => m,
435 None => {
436 let mut best = 0u8;
437 let mut best_pen = i32::MAX;
438 for m in 0 .. 8u8 {
439 apply_mask(&mut g, m);
440 draw_format_bits(&mut g, ecc, m);
441 let pen = penalty_score(&g);
442 if pen < best_pen {
443 best_pen = pen;
444 best = m;
445 }
446 apply_mask(&mut g, m); // The mask is its own inverse, so this undoes it.
447 }
448 best
449 },
450 };
451 apply_mask(&mut g, chosen);
452 draw_format_bits(&mut g, ecc, chosen);
453
454 Ok(QrMatrix {
455 size: size as usize,
456 mods: g.mods,
457 ver,
458 ecc,
459 })
460}
461
462/// Draws the timing lines, the three finder patterns and their separators, the alignment
463/// patterns, the dark module, and placeholder format and version information.
464fn draw_function_patterns(g: &mut Grid, ver: u8, ecc: QrEcc) {
465 let size = g.size;
466
467 // Timing patterns: alternating modules along row six and column six.
468 for i in 0 .. size {
469 g.set(6, i, i % 2 == 0, true);
470 g.set(i, 6, i % 2 == 0, true);
471 }
472
473 // The three finder patterns, at every corner but the bottom right, with their separators.
474 draw_finder(g, 3, 3);
475 draw_finder(g, size - 4, 3);
476 draw_finder(g, 3, size - 4);
477
478 // Alignment patterns at the grid of standard positions, skipping the three finder corners.
479 let pos = alignment_positions(ver);
480 let n = pos.len();
481 for i in 0 .. n {
482 for j in 0 .. n {
483 let corner = (i == 0 && j == 0)
484 || (i == 0 && j == n - 1)
485 || (i == n - 1 && j == 0);
486 if !corner {
487 draw_alignment(g, pos[i], pos[j]);
488 }
489 }
490 }
491
492 // Format and version information: a placeholder now, drawn for real once the mask is known.
493 draw_format_bits(g, ecc, 0);
494 draw_version(g, ver);
495}
496
497/// Draws a seven-by-seven finder pattern centred at the given coordinates, together with the
498/// one-module light separator that rings it.
499fn draw_finder(g: &mut Grid, cx: i32, cy: i32) {
500 for dy in -4i32 ..= 4 {
501 for dx in -4i32 ..= 4 {
502 let dist = std::cmp::max(dx.abs(), dy.abs()); // Chebyshev distance.
503 g.set(cx + dx, cy + dy, dist != 2 && dist != 4, true);
504 }
505 }
506}
507
508/// Draws a five-by-five alignment pattern centred at the given coordinates.
509fn draw_alignment(g: &mut Grid, cx: i32, cy: i32) {
510 for dy in -2i32 ..= 2 {
511 for dx in -2i32 ..= 2 {
512 g.set(cx + dx, cy + dy, std::cmp::max(dx.abs(), dy.abs()) != 1, true);
513 }
514 }
515}
516
517/// The centre coordinates of the alignment patterns for a version. Version 1 has none; from
518/// version 2 the coordinates form an evenly spaced grid whose spacing the standard fixes.
519fn alignment_positions(ver: u8) -> Vec<i32> {
520 if ver == 1 {
521 return Vec::new();
522 }
523 let v = ver as i32;
524 let num = v / 7 + 2; // The number of coordinates along one side.
525 let step = if ver == 32 {
526 26
527 } else {
528 (v * 4 + num * 2 + 1) / (num * 2 - 2) * 2
529 };
530 let size = v * 4 + 17;
531 let mut result: Vec<i32> = (0 .. num - 1).map(|i| size - 7 - i * step).collect();
532 result.push(6);
533 result.reverse();
534 result
535}
536
537/// Draws the fifteen-bit format information, a BCH-protected code naming the error-correction
538/// level and the mask, in its two copies around the finder patterns.
539fn draw_format_bits(g: &mut Grid, ecc: QrEcc, mask: u8) {
540 let data = (ecc.format_bits() << 3) | u32::from(mask);
541 let mut rem = data;
542 for _ in 0 .. 10 {
543 rem = (rem << 1) ^ (((rem >> 9) & 1) * 0x537);
544 }
545 let bits = ((data << 10) | rem) ^ 0x5412; // The standard's mask against an all-zero code.
546
547 // First copy, split around the top-left finder.
548 for i in 0 .. 6 {
549 g.set(8, i, get_bit(bits, i), true);
550 }
551 g.set(8, 7, get_bit(bits, 6), true);
552 g.set(8, 8, get_bit(bits, 7), true);
553 g.set(7, 8, get_bit(bits, 8), true);
554 for i in 9 .. 15 {
555 g.set(14 - i, 8, get_bit(bits, i), true);
556 }
557
558 // Second copy, along the edges beside the other two finders.
559 let size = g.size;
560 for i in 0 .. 8 {
561 g.set(size - 1 - i, 8, get_bit(bits, i), true);
562 }
563 for i in 8 .. 15 {
564 g.set(8, size - 15 + i, get_bit(bits, i), true);
565 }
566 g.set(8, size - 8, true, true); // The dark module, always set.
567}
568
569/// Draws the eighteen-bit version information, present only from version 7, in its two copies near
570/// the bottom-left and top-right finders.
571fn draw_version(g: &mut Grid, ver: u8) {
572 if ver < 7 {
573 return;
574 }
575 let data = u32::from(ver);
576 let mut rem = data;
577 for _ in 0 .. 12 {
578 rem = (rem << 1) ^ (((rem >> 11) & 1) * 0x1F25);
579 }
580 let bits = (data << 12) | rem;
581
582 let size = g.size;
583 for i in 0 .. 18 {
584 let bit = get_bit(bits, i);
585 let a = size - 11 + i % 3;
586 let b = i / 3;
587 g.set(a, b, bit, true);
588 g.set(b, a, bit, true);
589 }
590}
591
592/// Splits the data codewords into blocks, appends each block's Reed-Solomon error correction, then
593/// interleaves the blocks into the single codeword sequence the standard lays into the grid.
594fn add_ecc_and_interleave(ver: u8, ecc: QrEcc, data: &[u8])
595 -> Outcome<Vec<u8>>
596{
597 let expect = res!(num_data_codewords(ver, ecc));
598 if data.len() != expect {
599 return Err(err!(
600 "The data has {} codewords but version {} needs {}.", data.len(), ver, expect;
601 Bug, Mismatch, Size));
602 }
603
604 let numblocks = table_get(&NUM_ERROR_CORRECTION_BLOCKS, ver, ecc);
605 let blockecc = table_get(&ECC_CODEWORDS_PER_BLOCK, ver, ecc);
606 let rawcw = num_raw_data_modules(ver) / 8;
607 let numshort = numblocks - rawcw % numblocks; // Blocks one codeword shorter than the rest.
608 let shortlen = rawcw / numblocks; // Total codewords in a short block.
609
610 let divisor = rs_divisor(blockecc);
611 let mut blocks: Vec<Vec<u8>> = Vec::with_capacity(numblocks);
612 let mut k = 0usize; // Read cursor into the data.
613 for i in 0 .. numblocks {
614 let datlen = shortlen - blockecc + if i < numshort { 0 } else { 1 };
615 let mut blk = data[k .. k + datlen].to_vec();
616 k += datlen;
617 let ecc_bytes = rs_remainder(&blk, &divisor);
618 if i < numshort {
619 blk.push(0); // Pad short blocks so every block interleaves at the same width.
620 }
621 blk.extend_from_slice(&ecc_bytes);
622 blocks.push(blk);
623 }
624
625 // Interleave: take the ith codeword of every block in turn, skipping the padding cell that
626 // short blocks carry in the data region.
627 let mut result: Vec<u8> = Vec::with_capacity(rawcw);
628 let width = shortlen + 1; // The length of the longest block.
629 for i in 0 .. width {
630 for (j, blk) in blocks.iter().enumerate() {
631 if i != shortlen - blockecc || j >= numshort {
632 result.push(blk[i]);
633 }
634 }
635 }
636 Ok(result)
637}
638
639/// Lays the interleaved codeword bytes into the data region in the standard's zigzag order: up and
640/// down pairs of columns, right to left, skipping the vertical timing column and every function
641/// module.
642fn draw_codewords(g: &mut Grid, data: &[u8]) {
643 let size = g.size;
644 let mut i = 0usize; // Bit index into the data.
645 let mut right = size - 1; // The right column of the current pair.
646 while right >= 1 {
647 if right == 6 {
648 right = 5; // Skip the vertical timing column.
649 }
650 for v in 0 .. size {
651 for j in 0 .. 2 {
652 let x = right - j;
653 let upward = ((right + 1) & 2) == 0;
654 let y = if upward { size - 1 - v } else { v };
655 if !g.is_func(x, y) && i < data.len() * 8 {
656 let dark = get_bit(u32::from(data[i >> 3]), 7 - (i & 7) as i32);
657 g.set(x, y, dark, false);
658 i += 1;
659 }
660 }
661 }
662 right -= 2;
663 }
664}
665
666/// Applies one of the eight data masks in place, flipping data modules where the mask condition
667/// holds and leaving function modules untouched. Applying the same mask twice restores the grid.
668fn apply_mask(g: &mut Grid, mask: u8) {
669 let size = g.size;
670 for y in 0 .. size {
671 for x in 0 .. size {
672 if g.is_func(x, y) {
673 continue;
674 }
675 let (xl, yl) = (x as i64, y as i64);
676 let invert = match mask {
677 0 => (xl + yl) % 2 == 0,
678 1 => yl % 2 == 0,
679 2 => xl % 3 == 0,
680 3 => (xl + yl) % 3 == 0,
681 4 => (xl / 3 + yl / 2) % 2 == 0,
682 5 => xl * yl % 2 + xl * yl % 3 == 0,
683 6 => (xl * yl % 2 + xl * yl % 3) % 2 == 0,
684 _ => ((xl + yl) % 2 + xl * yl % 3) % 2 == 0,
685 };
686 if invert {
687 let idx = (y * size + x) as usize;
688 g.mods[idx] = !g.mods[idx];
689 }
690 }
691 }
692}
693
694/// The total penalty score of a grid, the sum of the standard's four rules. A lower score is a
695/// more robust symbol, which is how the best mask is chosen.
696fn penalty_score(g: &Grid) -> i32 {
697 let size = g.size;
698 let mut result: i32 = 0;
699
700 // Rule one and rule three, scanning each row then each column: runs of five or more same
701 // modules, and finder-like patterns.
702 for y in 0 .. size {
703 let mut colour = false;
704 let mut run = 0i32;
705 let mut hist = FinderRun::new(size);
706 for x in 0 .. size {
707 if g.get(x, y) == colour {
708 run += 1;
709 if run == 5 {
710 result += PENALTY_N1;
711 } else if run > 5 {
712 result += 1;
713 }
714 } else {
715 hist.add(run);
716 if !colour {
717 result += hist.count() * PENALTY_N3;
718 }
719 colour = g.get(x, y);
720 run = 1;
721 }
722 }
723 result += hist.terminate(colour, run) * PENALTY_N3;
724 }
725 for x in 0 .. size {
726 let mut colour = false;
727 let mut run = 0i32;
728 let mut hist = FinderRun::new(size);
729 for y in 0 .. size {
730 if g.get(x, y) == colour {
731 run += 1;
732 if run == 5 {
733 result += PENALTY_N1;
734 } else if run > 5 {
735 result += 1;
736 }
737 } else {
738 hist.add(run);
739 if !colour {
740 result += hist.count() * PENALTY_N3;
741 }
742 colour = g.get(x, y);
743 run = 1;
744 }
745 }
746 result += hist.terminate(colour, run) * PENALTY_N3;
747 }
748
749 // Rule two: every two-by-two block of one colour.
750 for y in 0 .. size - 1 {
751 for x in 0 .. size - 1 {
752 let c = g.get(x, y);
753 if c == g.get(x + 1, y) && c == g.get(x, y + 1) && c == g.get(x + 1, y + 1) {
754 result += PENALTY_N2;
755 }
756 }
757 }
758
759 // Rule four: how far the proportion of dark modules strays from one half, in 5% steps.
760 let dark: i32 = g.mods.iter().filter(|&&m| m).count() as i32;
761 let total = size * size;
762 let k = ((dark * 20 - total * 10).abs() + total - 1) / total - 1;
763 result += k * PENALTY_N4;
764
765 result
766}
767
768/// A sliding record of the last seven run lengths along a line, used to detect the finder-like
769/// 1:1:3:1:1 pattern that rule three penalises.
770struct FinderRun {
771 size: i32, // grid side length, added as the light border around the symbol
772 hist: [i32; 7], // the seven most recent run lengths, most recent first
773}
774
775impl FinderRun {
776
777 fn new(size: i32) -> Self {
778 Self { size, hist: [0i32; 7] }
779 }
780
781 /// Pushes a run length onto the history, dropping the oldest, and folds in the light border
782 /// at the very start of a line.
783 fn add(&mut self, run: i32) {
784 let mut run = run;
785 if self.hist[0] == 0 {
786 run += self.size; // The quiet zone before the first run.
787 }
788 for i in (1 .. self.hist.len()).rev() {
789 self.hist[i] = self.hist[i - 1];
790 }
791 self.hist[0] = run;
792 }
793
794 /// Counts the finder-like patterns ending at the current position, either zero, one, or two.
795 /// Only meaningful immediately after a light run has been added.
796 fn count(&self) -> i32 {
797 let h = &self.hist;
798 let n = h[1];
799 let core = n > 0 && h[2] == n && h[3] == n * 3 && h[4] == n && h[5] == n;
800 i32::from(core && h[0] >= n * 4 && h[6] >= n)
801 + i32::from(core && h[6] >= n * 4 && h[0] >= n)
802 }
803
804 /// Terminates the line, folding in the final run and the trailing light border, and returns
805 /// the finder-like patterns that close it out.
806 fn terminate(mut self, colour: bool, run: i32) -> i32 {
807 let mut run = run;
808 if colour {
809 self.add(run); // Close a dark run first.
810 run = 0;
811 }
812 run += self.size; // The quiet zone after the last run.
813 self.add(run);
814 self.count()
815 }
816}
817
818#[cfg(test)]
819mod tests;