1 //! QR decode, taken from https://raw.githubusercontent.com/WanzenBug/rqrr/505c281db1fe4c7d30e3be595ec5a48b2cedebde/src/decode.rs
2
3 use std::io::Write;
4 use std::mem;
5
6 use g2p::{g2p, GaloisField};
7
8 use crate::decode::version_db::{RSParameters, VERSION_DATA_BASE};
9 use crate::decode::{BitGrid, DeQRError, DeQRResult};
10
11 g2p!(GF16, 4, modulus: 0b1_0011);
12 g2p!(GF256, 8, modulus: 0b1_0001_1101);
13
14 const MAX_PAYLOAD_SIZE: usize = 8896;
15
16 /// Version of a QR Code which determines its size
17 #[derive(Debug, Clone, Copy, Eq, PartialEq)]
18 pub struct Version(pub usize);
19
20 impl Version {
21 /// Given the grid size, determine the likely grid size
from_size(b: usize) -> DeQRResult<Self>22 pub fn from_size(b: usize) -> DeQRResult<Self> {
23 let computed_version = b.saturating_sub(17) / 4;
24
25 if computed_version > 0 && computed_version <= 40 {
26 Ok(Version(computed_version))
27 } else {
28 Err(DeQRError::InvalidVersion)
29 }
30 }
31
32 /// Return the size of a grid of the given version
to_size(&self) -> usize33 pub fn to_size(&self) -> usize {
34 self.0 as usize * 4 + 17
35 }
36 }
37
38 /// MetaData for a QR grid
39 ///
40 /// Stores information about the size/version of given grid. Also contains information about the
41 /// error correction level and bit mask used.
42 #[derive(Debug, Clone, Copy, Eq, PartialEq)]
43 pub struct MetaData {
44 /// The version/size of the grid
45 pub version: Version,
46 /// the error correction leven, between 0 and 3
47 pub ecc_level: u16,
48 /// The mask that was used, value between 0 and 7
49 pub mask: u16,
50 }
51
52 #[derive(Clone)]
53 pub struct RawData {
54 data: [u8; MAX_PAYLOAD_SIZE],
55 len: usize,
56 }
57
58 impl RawData {
new() -> Self59 pub fn new() -> Self {
60 RawData {
61 data: [0; MAX_PAYLOAD_SIZE],
62 len: 0,
63 }
64 }
65
push(&mut self, bit: bool)66 pub fn push(&mut self, bit: bool) {
67 assert!((self.len >> 8) < MAX_PAYLOAD_SIZE);
68 let bitpos = (self.len & 7) as u8;
69 let bytepos = self.len >> 3;
70
71 if bit {
72 self.data[bytepos] |= 0x80_u8 >> bitpos;
73 }
74 self.len += 1;
75 }
76 }
77
78 #[derive(Clone)]
79 pub struct CorrectedDataStream {
80 data: [u8; MAX_PAYLOAD_SIZE],
81 ptr: usize,
82 bit_len: usize,
83 }
84
85 impl CorrectedDataStream {
bits_remaining(&self) -> usize86 pub fn bits_remaining(&self) -> usize {
87 assert!(self.bit_len >= self.ptr);
88 self.bit_len - self.ptr
89 }
90
take_bits(&mut self, nbits: usize) -> usize91 pub fn take_bits(&mut self, nbits: usize) -> usize {
92 let mut ret = 0;
93 let max_len = ::std::cmp::min(self.bits_remaining(), nbits);
94 assert!(max_len <= mem::size_of::<usize>() * 8);
95 for _ in 0..max_len {
96 let b = self.data[self.ptr >> 3];
97 let bitpos = self.ptr & 7;
98 ret <<= 1;
99 if 0 != (b << bitpos) & 0x80 {
100 ret |= 1
101 }
102 self.ptr += 1;
103 }
104 ret
105 }
106 }
107
108 /* ***********************************************************************
109 * Decoder algorithm
110 */
111 #[derive(Copy, Clone)]
112 pub struct DataStream {
113 pub raw: [u8; MAX_PAYLOAD_SIZE],
114 pub data_bits: usize,
115 pub ptr: usize,
116 pub data: [u8; MAX_PAYLOAD_SIZE],
117 }
118
119 /// Given a grid try to decode and write it to the output writer
120 ///
121 /// This tries to read the bit patterns from a [Grid](trait.Grid.html), correct errors
122 /// and/or missing bits and write the result to the output. If successful also returns
123 /// [MetaData](struct.MetaData.html) of the read grid.
decode<W>(code: &dyn BitGrid, writer: W) -> DeQRResult<MetaData> where W: Write,124 pub fn decode<W>(code: &dyn BitGrid, writer: W) -> DeQRResult<MetaData>
125 where
126 W: Write,
127 {
128 let meta = read_format(code)?;
129 let raw = read_data(code, &meta);
130 let stream = codestream_ecc(&meta, raw)?;
131 decode_payload(&meta, stream, writer)?;
132
133 Ok(meta)
134 }
135
decode_payload<W>( meta: &MetaData, mut ds: CorrectedDataStream, mut writer: W, ) -> DeQRResult<()> where W: Write,136 pub(crate) fn decode_payload<W>(
137 meta: &MetaData,
138 mut ds: CorrectedDataStream,
139 mut writer: W,
140 ) -> DeQRResult<()>
141 where
142 W: Write,
143 {
144 while ds.bits_remaining() >= 4 {
145 let ty = ds.take_bits(4);
146 match ty {
147 0 => break,
148 1 => decode_numeric(meta, &mut ds, &mut writer),
149 2 => decode_alpha(meta, &mut ds, &mut writer),
150 3 => decode_structured(meta, &mut ds, &mut writer),
151 4 => decode_byte(meta, &mut ds, &mut writer),
152 8 => decode_kanji(meta, &mut ds, &mut writer),
153 7 => decode_eci(meta, &mut ds, &mut writer),
154 _ => Err(DeQRError::UnknownDataType)?,
155 }?;
156 }
157 Ok(())
158 }
159
decode_eci<W>(_meta: &MetaData, ds: &mut CorrectedDataStream, mut _writer: W) -> DeQRResult<()> where W: Write,160 fn decode_eci<W>(_meta: &MetaData, ds: &mut CorrectedDataStream, mut _writer: W) -> DeQRResult<()>
161 where
162 W: Write,
163 {
164 if ds.bits_remaining() < 8 {
165 Err(DeQRError::DataUnderflow)?
166 }
167
168 let mut _eci = ds.take_bits(8) as u32;
169 if _eci & 0xc0 == 0x80 {
170 if ds.bits_remaining() < 8 {
171 Err(DeQRError::DataUnderflow)?
172 }
173 _eci = (_eci << 8) | (ds.take_bits(8) as u32)
174 } else if _eci & 0xe0 == 0xc0 {
175 if ds.bits_remaining() < 16 {
176 Err(DeQRError::DataUnderflow)?
177 }
178
179 _eci = (_eci << 16) | (ds.take_bits(16) as u32)
180 }
181 Ok(())
182 }
183
decode_kanji<W>(meta: &MetaData, ds: &mut CorrectedDataStream, mut writer: W) -> DeQRResult<()> where W: Write,184 fn decode_kanji<W>(meta: &MetaData, ds: &mut CorrectedDataStream, mut writer: W) -> DeQRResult<()>
185 where
186 W: Write,
187 {
188 let nbits = match meta.version {
189 Version(0..=9) => 8,
190 Version(10..=26) => 10,
191 _ => 12,
192 };
193
194 let count = ds.take_bits(nbits);
195 if ds.bits_remaining() < count * 13 {
196 Err(DeQRError::DataUnderflow)?
197 }
198
199 for _ in 0..count {
200 let d = ds.take_bits(13);
201 let ms_b = d / 0xc0;
202 let ls_b = d % 0xc0;
203 let intermediate = ms_b << 8 | ls_b;
204 let sjw = if intermediate + 0x8140 <= 0x9ffc {
205 /* bytes are in the range 0x8140 to 0x9FFC */
206 (intermediate + 0x8140) as u16
207 } else {
208 (intermediate + 0xc140) as u16
209 };
210 writer
211 .write_all(&[(sjw >> 8) as u8, (sjw & 0xff) as u8])
212 .map_err(|_| DeQRError::IoError)?;
213 }
214 Ok(())
215 }
216
decode_structured<W>(meta: &MetaData, ds: &mut CorrectedDataStream, writer: W) -> DeQRResult<()> where W: Write,217 fn decode_structured<W>(meta: &MetaData, ds: &mut CorrectedDataStream, writer: W) -> DeQRResult<()>
218 where
219 W: Write,
220 {
221 let _current = ds.take_bits(4);
222 let _total = ds.take_bits(4);
223 let _parity = ds.take_bits(8);
224 let _mode_bits = ds.take_bits(4);
225 //println!("decode_structured {}/{} parity:{} mode_bits:{}", current, total, parity,mode_bits);
226 decode_byte(meta, ds, writer)?;
227 Ok(())
228 }
229
decode_byte<W>(meta: &MetaData, ds: &mut CorrectedDataStream, mut writer: W) -> DeQRResult<()> where W: Write,230 fn decode_byte<W>(meta: &MetaData, ds: &mut CorrectedDataStream, mut writer: W) -> DeQRResult<()>
231 where
232 W: Write,
233 {
234 let nbits = match meta.version {
235 Version(0..=9) => 8,
236 _ => 16,
237 };
238
239 let count = ds.take_bits(nbits);
240 //println!("decode_byte version:{:?} count:{} bits_remaining:{}", meta.version, count, ds.bits_remaining());
241 if ds.bits_remaining() < count * 8 {
242 return Err(DeQRError::DataUnderflow)?;
243 }
244
245 for _ in 0..count {
246 let buf = &[ds.take_bits(8) as u8];
247 writer.write_all(buf).map_err(|_| DeQRError::IoError)?;
248 }
249 Ok(())
250 }
251
decode_alpha<W>(meta: &MetaData, ds: &mut CorrectedDataStream, mut writer: W) -> DeQRResult<()> where W: Write,252 fn decode_alpha<W>(meta: &MetaData, ds: &mut CorrectedDataStream, mut writer: W) -> DeQRResult<()>
253 where
254 W: Write,
255 {
256 let nbits = match meta.version {
257 Version(0..=9) => 9,
258 Version(10..=26) => 11,
259 _ => 13,
260 };
261 let mut count = ds.take_bits(nbits);
262 let mut buf = [0; 2];
263
264 while count >= 2 {
265 alpha_tuple(&mut buf, ds, 11, 2)?;
266 writer.write_all(&buf[..]).map_err(|_| DeQRError::IoError)?;
267 count -= 2;
268 }
269
270 if count == 1 {
271 alpha_tuple(&mut buf, ds, 6, 1)?;
272 writer
273 .write_all(&buf[..1])
274 .map_err(|_| DeQRError::IoError)?;
275 }
276
277 Ok(())
278 }
279
alpha_tuple( buf: &mut [u8; 2], ds: &mut CorrectedDataStream, nbits: usize, digits: usize, ) -> DeQRResult<()>280 fn alpha_tuple(
281 buf: &mut [u8; 2],
282 ds: &mut CorrectedDataStream,
283 nbits: usize,
284 digits: usize,
285 ) -> DeQRResult<()> {
286 if ds.bits_remaining() < nbits {
287 Err(DeQRError::DataUnderflow)
288 } else {
289 let mut tuple = ds.take_bits(nbits);
290 for i in (0..digits).rev() {
291 const ALPHA_MAP: &[u8; 46] = b"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ $%*+-./:\x00";
292 buf[i] = ALPHA_MAP[tuple % 45];
293 tuple /= 45;
294 }
295 Ok(())
296 }
297 }
298
decode_numeric<W>(meta: &MetaData, ds: &mut CorrectedDataStream, mut writer: W) -> DeQRResult<()> where W: Write,299 fn decode_numeric<W>(meta: &MetaData, ds: &mut CorrectedDataStream, mut writer: W) -> DeQRResult<()>
300 where
301 W: Write,
302 {
303 let nbits = match meta.version {
304 Version(0..=9) => 10,
305 Version(10..=26) => 12,
306 _ => 14,
307 };
308
309 let mut count = ds.take_bits(nbits);
310 let mut buf = [0; 3];
311 while count >= 3 {
312 numeric_tuple(&mut buf, ds, 10, 3)?;
313 writer.write_all(&buf[..]).map_err(|_| DeQRError::IoError)?;
314 count -= 3;
315 }
316
317 if count == 2 {
318 numeric_tuple(&mut buf, ds, 7, 2)?;
319 writer
320 .write_all(&buf[..2])
321 .map_err(|_| DeQRError::IoError)?;
322 count -= 2;
323 }
324 if count == 1 {
325 numeric_tuple(&mut buf, ds, 4, 1)?;
326 writer
327 .write_all(&buf[..1])
328 .map_err(|_| DeQRError::IoError)?;
329 }
330
331 Ok(())
332 }
333
numeric_tuple( buf: &mut [u8; 3], ds: &mut CorrectedDataStream, nbits: usize, digits: usize, ) -> DeQRResult<()>334 fn numeric_tuple(
335 buf: &mut [u8; 3],
336 ds: &mut CorrectedDataStream,
337 nbits: usize,
338 digits: usize,
339 ) -> DeQRResult<()> {
340 if ds.bits_remaining() < nbits {
341 Err(DeQRError::DataUnderflow)
342 } else {
343 let mut tuple = ds.take_bits(nbits);
344 for i in (0..digits).rev() {
345 buf[i] = (tuple % 10) as u8 + b'0';
346 tuple /= 10;
347 }
348 Ok(())
349 }
350 }
351
codestream_ecc(meta: &MetaData, ds: RawData) -> DeQRResult<CorrectedDataStream>352 pub(crate) fn codestream_ecc(meta: &MetaData, ds: RawData) -> DeQRResult<CorrectedDataStream> {
353 let mut out = CorrectedDataStream {
354 data: [0; MAX_PAYLOAD_SIZE],
355 ptr: 0,
356 bit_len: 0,
357 };
358
359 let ver = &VERSION_DATA_BASE[meta.version.0 as usize];
360 let sb_ecc = &ver.ecc[meta.ecc_level as usize];
361 let lb_ecc = RSParameters {
362 bs: sb_ecc.bs + 1,
363 dw: sb_ecc.dw + 1,
364 ns: sb_ecc.ns,
365 };
366
367 let lb_count = (ver.data_bytes - sb_ecc.bs * sb_ecc.ns) / (sb_ecc.bs + 1);
368 let bc = lb_count + sb_ecc.ns;
369 let ecc_offset = sb_ecc.dw * bc + lb_count;
370
371 let mut dst_offset = 0;
372 for i in 0..bc {
373 let ecc = if i < sb_ecc.ns { sb_ecc } else { &lb_ecc };
374 let dst = &mut out.data[dst_offset..(dst_offset + ecc.bs)];
375 let num_ec = ecc.bs - ecc.dw;
376 for j in 0..ecc.dw {
377 dst[j] = ds.data[j * bc + i];
378 }
379 for j in 0..num_ec {
380 dst[ecc.dw + j] = ds.data[ecc_offset + j * bc + i];
381 }
382 correct_block(dst, ecc)?;
383
384 dst_offset += ecc.dw;
385 }
386
387 out.bit_len = dst_offset * 8;
388 Ok(out)
389 }
390
correct_block(block: &mut [u8], ecc: &RSParameters) -> DeQRResult<()>391 fn correct_block(block: &mut [u8], ecc: &RSParameters) -> DeQRResult<()> {
392 assert!(ecc.bs > ecc.dw);
393
394 let npar = ecc.bs - ecc.dw;
395 let mut sigma_deriv = [GF256::ZERO; 64];
396
397 // Calculate syndromes. If all 0 there is nothing to do.
398 let s = match block_syndromes(&block[..ecc.bs], npar) {
399 Ok(_) => return Ok(()),
400 Err(s) => s,
401 };
402
403 let sigma = berlekamp_massey(&s, npar);
404 /* Compute derivative of sigma */
405 for i in (1..64).step_by(2) {
406 sigma_deriv[i - 1] = sigma[i];
407 }
408
409 /* Compute error evaluator polynomial */
410 let omega = eloc_poly(&s, &sigma, npar - 1);
411
412 /* Find error locations and magnitudes */
413 for i in 0..ecc.bs {
414 let xinv = GF256::GENERATOR.pow(255 - i);
415 if poly_eval(&sigma, xinv) == GF256::ZERO {
416 let sd_x = poly_eval(&sigma_deriv, xinv);
417 let omega_x = poly_eval(&omega, xinv);
418 let error = omega_x / sd_x;
419 block[ecc.bs - i - 1] = (GF256(block[ecc.bs - i - 1]) + error).0;
420 }
421 }
422
423 match block_syndromes(&block[..ecc.bs], npar) {
424 Ok(_) => Ok(()),
425 Err(_) => Err(DeQRError::DataEcc),
426 }
427 }
428 /* ***********************************************************************
429 * Code stream error correction
430 *
431 * Generator polynomial for GF(2^8) is x^8 + x^4 + x^3 + x^2 + 1
432 */
block_syndromes(block: &[u8], npar: usize) -> Result<[GF256; 64], [GF256; 64]>433 fn block_syndromes(block: &[u8], npar: usize) -> Result<[GF256; 64], [GF256; 64]> {
434 let mut nonzero: bool = false;
435 let mut s = [GF256::ZERO; 64];
436
437 for i in 0..npar {
438 for j in 0..block.len() {
439 let c = GF256(block[block.len() - 1 - j]);
440 s[i] += c * GF256::GENERATOR.pow(i * j);
441 }
442 if s[i] != GF256::ZERO {
443 nonzero = true;
444 }
445 }
446 if nonzero {
447 Err(s)
448 } else {
449 Ok(s)
450 }
451 }
452
poly_eval<G>(s: &[G; 64], x: G) -> G where G: GaloisField,453 fn poly_eval<G>(s: &[G; 64], x: G) -> G
454 where
455 G: GaloisField,
456 {
457 let mut sum = G::ZERO;
458 let mut x_pow = G::ONE;
459
460 for i in 0..64 {
461 sum += s[i] * x_pow;
462 x_pow *= x;
463 }
464 sum
465 }
466
eloc_poly(s: &[GF256; 64], sigma: &[GF256; 64], npar: usize) -> [GF256; 64]467 fn eloc_poly(s: &[GF256; 64], sigma: &[GF256; 64], npar: usize) -> [GF256; 64] {
468 let mut omega = [GF256::ZERO; 64];
469 for i in 0..npar {
470 let a = sigma[i];
471 for j in 0..(npar - i) {
472 let b = s[j + 1];
473 omega[i + j] += a * b;
474 }
475 }
476 omega
477 }
478 /* ***********************************************************************
479 * Berlekamp-Massey algorithm for finding error locator polynomials.
480 */
berlekamp_massey<G>(s: &[G; 64], n: usize) -> [G; 64] where G: GaloisField,481 fn berlekamp_massey<G>(s: &[G; 64], n: usize) -> [G; 64]
482 where
483 G: GaloisField,
484 {
485 let mut ts: [G; 64] = [G::ZERO; 64];
486 let mut cs: [G; 64] = [G::ZERO; 64];
487 let mut bs: [G; 64] = [G::ZERO; 64];
488 let mut l: usize = 0;
489 let mut m: usize = 1;
490 let mut b = G::ONE;
491 bs[0] = G::ONE;
492 cs[0] = G::ONE;
493
494 for n in 0..n {
495 let mut d = s[n];
496
497 // Calculate in GF(p):
498 // d = s[n] + \Sum_{i=1}^{l} c[i] * s[n - i]
499 for i in 1..=l {
500 d += cs[i] * s[n - i];
501 }
502 // Pre-calculate d * b^-1 in GF(p)
503 let mult = d / b;
504
505 if d == G::ZERO {
506 m += 1
507 } else if l * 2 <= n {
508 ts.copy_from_slice(&cs);
509 poly_add(&mut cs, &bs, mult, m);
510 bs.copy_from_slice(&ts);
511 l = n + 1 - l;
512 b = d;
513 m = 1
514 } else {
515 poly_add(&mut cs, &bs, mult, m);
516 m += 1
517 }
518 }
519 cs
520 }
521 /* ***********************************************************************
522 * Polynomial operations
523 */
poly_add<G>(dst: &mut [G; 64], src: &[G; 64], c: G, shift: usize) -> () where G: GaloisField,524 fn poly_add<G>(dst: &mut [G; 64], src: &[G; 64], c: G, shift: usize) -> ()
525 where
526 G: GaloisField,
527 {
528 if c == G::ZERO {
529 return;
530 }
531
532 for i in 0..64 {
533 let p = i + shift;
534 if p >= 64 {
535 break;
536 }
537 let v = src[i];
538 dst[p] += v * c;
539 }
540 }
541
read_data(code: &dyn BitGrid, meta: &MetaData) -> RawData542 pub(crate) fn read_data(code: &dyn BitGrid, meta: &MetaData) -> RawData {
543 let mut ds = RawData::new();
544
545 let mut y = code.size() - 1;
546 let mut x = code.size() - 1;
547 let mut neg_dir = true;
548
549 while x > 0 {
550 if x == 6 {
551 x -= 1;
552 }
553 if !reserved_cell(meta.version, y, x) {
554 ds.push(read_bit(code, meta, y, x));
555 }
556 if !reserved_cell(meta.version, y, x - 1) {
557 ds.push(read_bit(code, meta, y, x - 1));
558 }
559
560 let (new_y, new_neg_dir) = match (y, neg_dir) {
561 (0, true) => {
562 x = x.saturating_sub(2);
563 (0, false)
564 }
565 (y, false) if y == code.size() - 1 => {
566 x = x.saturating_sub(2);
567 (code.size() - 1, true)
568 }
569 (y, true) => (y - 1, true),
570 (y, false) => (y + 1, false),
571 };
572
573 y = new_y;
574 neg_dir = new_neg_dir;
575 }
576
577 ds
578 }
579
read_bit(code: &dyn BitGrid, meta: &MetaData, y: usize, x: usize) -> bool580 fn read_bit(code: &dyn BitGrid, meta: &MetaData, y: usize, x: usize) -> bool {
581 let mut v = code.bit(y, x) as u8;
582 if mask_bit(meta.mask, y, x) {
583 v ^= 1
584 }
585 v != 0
586 }
587
mask_bit(mask: u16, y: usize, x: usize) -> bool588 fn mask_bit(mask: u16, y: usize, x: usize) -> bool {
589 match mask {
590 0 => 0 == (y + x) % 2,
591 1 => 0 == y % 2,
592 2 => 0 == x % 3,
593 3 => 0 == (y + x) % 3,
594 4 => 0 == ((y / 2) + (x / 3)) % 2,
595 5 => 0 == ((y * x) % 2 + (y * x) % 3),
596 6 => 0 == ((y * x) % 2 + (y * x) % 3) % 2,
597 7 => 0 == ((y * x) % 3 + (y + x) % 2) % 2,
598 _ => panic!("Unknown mask value"),
599 }
600 }
601
reserved_cell(version: Version, i: usize, j: usize) -> bool602 fn reserved_cell(version: Version, i: usize, j: usize) -> bool {
603 let ver = &VERSION_DATA_BASE[version.0];
604 let size = version.0 * 4 + 17;
605
606 /* Finder + format: top left */
607 if i < 9 && j < 9 {
608 return true;
609 }
610
611 /* Finder + format: bottom left */
612 if i + 8 >= size && j < 9 {
613 return true;
614 }
615
616 /* Finder + format: top right */
617 if i < 9 && j + 8 >= size {
618 return true;
619 }
620
621 /* Exclude timing patterns */
622 if i == 6 || j == 6 {
623 return true;
624 }
625
626 /* Exclude version info, if it exists. Version info sits adjacent to
627 * the top-right and bottom-left finders in three rows, bounded by
628 * the timing pattern.
629 */
630 if version.0 >= 7 {
631 if i < 6 && j + 11 >= size {
632 return true;
633 } else if i + 11 >= size && j < 6 {
634 return true;
635 }
636 }
637
638 /* Exclude alignment patterns */
639 let mut ai = None;
640 let mut aj = None;
641
642 fn abs_diff(x: usize, y: usize) -> usize {
643 if x < y {
644 y - x
645 } else {
646 x - y
647 }
648 }
649
650 let mut len = 0;
651 for (a, &pattern) in ver.apat.iter().take_while(|&&x| x != 0).enumerate() {
652 len = a;
653 if abs_diff(pattern, i) < 3 {
654 ai = Some(a)
655 }
656 if abs_diff(pattern, j) < 3 {
657 aj = Some(a)
658 }
659 }
660
661 match (ai, aj) {
662 (Some(x), Some(y)) if x == len && y == len => true,
663 (Some(x), Some(_)) if 0 < x && x < len => true,
664 (Some(_), Some(x)) if 0 < x && x < len => true,
665 _ => false,
666 }
667 }
668
correct_format(mut word: u16) -> DeQRResult<u16>669 fn correct_format(mut word: u16) -> DeQRResult<u16> {
670 /* Evaluate U (received codeword) at each of alpha_1 .. alpha_6
671 * to get S_1 .. S_6 (but we index them from 0).
672 */
673 if let Err(mut s) = format_syndromes(word) {
674 let sigma = berlekamp_massey(&mut s, 6);
675
676 /* Now, find the roots of the polynomial */
677 for i in 0..15 {
678 if poly_eval(&sigma, GF16::GENERATOR.pow(15 - i)) == GF16::ZERO {
679 word ^= 1 << i;
680 }
681 }
682
683 // Double CHECK syndromes
684 format_syndromes(word).map_err(|_| DeQRError::FormatEcc)?;
685 }
686 Ok(word)
687 }
688
read_format(code: &dyn BitGrid) -> DeQRResult<MetaData>689 pub(crate) fn read_format(code: &dyn BitGrid) -> DeQRResult<MetaData> {
690 let mut format = 0;
691
692 // Try first location
693 const XS: [usize; 15] = [8, 8, 8, 8, 8, 8, 8, 8, 7, 5, 4, 3, 2, 1, 0];
694 const YS: [usize; 15] = [0, 1, 2, 3, 4, 5, 7, 8, 8, 8, 8, 8, 8, 8, 8];
695 for i in (0..15).rev() {
696 format = (format << 1) | code.bit(YS[i], XS[i]) as u16;
697 }
698 format ^= 0x5412;
699
700 // Check format, try other location if needed
701 let verified_format = correct_format(format).or_else(|_| {
702 let mut format = 0;
703 for i in 0..7 {
704 format = (format << 1) | code.bit(code.size() - 1 - i, 8) as u16;
705 }
706 for i in 0..8 {
707 format = (format << 1) | code.bit(8, code.size() - 8 + i) as u16;
708 }
709 format ^= 0x5412;
710 correct_format(format)
711 })?;
712
713 let fdata = verified_format >> 10;
714 let ecc_level = fdata >> 3;
715 let mask = fdata & 7;
716 let version = Version::from_size(code.size())?;
717
718 Ok(MetaData {
719 version,
720 ecc_level,
721 mask,
722 })
723 }
724 /* ***********************************************************************
725 * Format value error correction
726 *
727 * Generator polynomial for GF(2^4) is x^4 + x + 1
728 */
format_syndromes(u: u16) -> Result<[GF16; 64], [GF16; 64]>729 fn format_syndromes(u: u16) -> Result<[GF16; 64], [GF16; 64]> {
730 let mut result = [GF16(0); 64];
731 let mut nonzero = false;
732
733 for i in 0..6 {
734 for j in 0..15 {
735 if u & (1 << j) != 0 {
736 result[i] += GF16::GENERATOR.pow((i + 1) * j);
737 }
738 }
739 if result[i].0 != 0 {
740 nonzero = true;
741 }
742 }
743
744 if nonzero {
745 Err(result)
746 } else {
747 Ok(result)
748 }
749 }
750
751 #[cfg(test)]
752 mod tests {
753 use super::*;
754
755 #[test]
test_mask_0()756 fn test_mask_0() {
757 let test = [
758 [1, 0, 1, 0, 1, 0, 1],
759 [0, 1, 0, 1, 0, 1, 0],
760 [1, 0, 1, 0, 1, 0, 1],
761 [0, 1, 0, 1, 0, 1, 0],
762 [1, 0, 1, 0, 1, 0, 1],
763 [0, 1, 0, 1, 0, 1, 0],
764 [1, 0, 1, 0, 1, 0, 1],
765 ];
766
767 for x in 0..7 {
768 for y in 0..7 {
769 assert_eq!(test[y][x] != 0, mask_bit(0, y, x));
770 }
771 }
772 }
773
774 #[test]
test_mask_1()775 fn test_mask_1() {
776 let test = [
777 [1, 1, 1, 1, 1, 1, 1],
778 [0, 0, 0, 0, 0, 0, 0],
779 [1, 1, 1, 1, 1, 1, 1],
780 [0, 0, 0, 0, 0, 0, 0],
781 [1, 1, 1, 1, 1, 1, 1],
782 [0, 0, 0, 0, 0, 0, 0],
783 [1, 1, 1, 1, 1, 1, 1],
784 ];
785
786 for x in 0..7 {
787 for y in 0..7 {
788 assert_eq!(test[y][x] != 0, mask_bit(1, y, x));
789 }
790 }
791 }
792
793 #[test]
test_mask_2()794 fn test_mask_2() {
795 let test = [
796 [1, 0, 0, 1, 0, 0, 1],
797 [1, 0, 0, 1, 0, 0, 1],
798 [1, 0, 0, 1, 0, 0, 1],
799 [1, 0, 0, 1, 0, 0, 1],
800 [1, 0, 0, 1, 0, 0, 1],
801 [1, 0, 0, 1, 0, 0, 1],
802 [1, 0, 0, 1, 0, 0, 1],
803 ];
804
805 for x in 0..7 {
806 for y in 0..7 {
807 assert_eq!(test[y][x] != 0, mask_bit(2, y, x));
808 }
809 }
810 }
811
812 #[test]
test_mask_3()813 fn test_mask_3() {
814 let test = [
815 [1, 0, 0, 1, 0, 0, 1],
816 [0, 0, 1, 0, 0, 1, 0],
817 [0, 1, 0, 0, 1, 0, 0],
818 [1, 0, 0, 1, 0, 0, 1],
819 [0, 0, 1, 0, 0, 1, 0],
820 [0, 1, 0, 0, 1, 0, 0],
821 [1, 0, 0, 1, 0, 0, 1],
822 ];
823
824 for x in 0..7 {
825 for y in 0..7 {
826 assert_eq!(test[y][x] != 0, mask_bit(3, y, x));
827 }
828 }
829 }
830
831 #[test]
test_mask_4()832 fn test_mask_4() {
833 let test = [
834 [1, 1, 1, 0, 0, 0, 1],
835 [1, 1, 1, 0, 0, 0, 1],
836 [0, 0, 0, 1, 1, 1, 0],
837 [0, 0, 0, 1, 1, 1, 0],
838 [1, 1, 1, 0, 0, 0, 1],
839 [1, 1, 1, 0, 0, 0, 1],
840 [0, 0, 0, 1, 1, 1, 0],
841 ];
842
843 for x in 0..7 {
844 for y in 0..7 {
845 assert_eq!(test[y][x] != 0, mask_bit(4, y, x));
846 }
847 }
848 }
849
850 #[test]
test_mask_5()851 fn test_mask_5() {
852 let test = [
853 [1, 1, 1, 1, 1, 1, 1],
854 [1, 0, 0, 0, 0, 0, 1],
855 [1, 0, 0, 1, 0, 0, 1],
856 [1, 0, 1, 0, 1, 0, 1],
857 [1, 0, 0, 1, 0, 0, 1],
858 [1, 0, 0, 0, 0, 0, 1],
859 [1, 1, 1, 1, 1, 1, 1],
860 ];
861
862 for x in 0..7 {
863 for y in 0..7 {
864 assert_eq!(test[y][x] != 0, mask_bit(5, y, x));
865 }
866 }
867 }
868
869 #[test]
test_mask_6()870 fn test_mask_6() {
871 let test = [
872 [1, 1, 1, 1, 1, 1, 1],
873 [1, 1, 1, 0, 0, 0, 1],
874 [1, 1, 0, 1, 1, 0, 1],
875 [1, 0, 1, 0, 1, 0, 1],
876 [1, 0, 1, 1, 0, 1, 1],
877 [1, 0, 0, 0, 1, 1, 1],
878 [1, 1, 1, 1, 1, 1, 1],
879 ];
880
881 for x in 0..7 {
882 for y in 0..7 {
883 assert_eq!(test[y][x] != 0, mask_bit(6, y, x));
884 }
885 }
886 }
887
888 #[test]
test_mask_7()889 fn test_mask_7() {
890 let test = [
891 [1, 0, 1, 0, 1, 0, 1],
892 [0, 0, 0, 1, 1, 1, 0],
893 [1, 0, 0, 0, 1, 1, 1],
894 [0, 1, 0, 1, 0, 1, 0],
895 [1, 1, 1, 0, 0, 0, 1],
896 [0, 1, 1, 1, 0, 0, 0],
897 [1, 0, 1, 0, 1, 0, 1],
898 ];
899
900 for x in 0..7 {
901 for y in 0..7 {
902 assert_eq!(test[y][x] != 0, mask_bit(7, y, x));
903 }
904 }
905 }
906 }
907