| blob | 09500cddc009bb96e6b8373d583db69a2b69dc0d |
1 // SPDX-License-Identifier: MIT
3 //! This is a simple QR encoder for DRM panic.
4 //!
5 //! It is called from a panic handler, so it should't allocate memory and
6 //! does all the work on the stack or on the provided buffers. For
7 //! simplification, it only supports low error correction, and applies the
8 //! first mask (checkerboard). It will draw the smallest QRcode that can
9 //! contain the string passed as parameter. To get the most compact
10 //! QR code, the start of the URL is encoded as binary, and the
11 //! compressed kmsg is encoded as numeric.
12 //!
13 //! The binary data must be a valid URL parameter, so the easiest way is
14 //! to use base64 encoding. But this wastes 25% of data space, so the
15 //! whole stack trace won't fit in the QR code. So instead it encodes
16 //! every 13bits of input into 4 decimal digits, and then uses the
17 //! efficient numeric encoding, that encode 3 decimal digits into
18 //! 10bits. This makes 39bits of compressed data into 12 decimal digits,
19 //! into 40bits in the QR code, so wasting only 2.5%. And the numbers are
20 //! valid URL parameter, so the website can do the reverse, to get the
21 //! binary data.
22 //!
23 //! Inspired by these 3 projects, all under MIT license:
24 //!
25 //! * <https://github.com/kennytm/qrcode-rust>
26 //! * <https://github.com/erwanvivien/fast_qr>
27 //! * <https://github.com/bjguillot/qr>
29 use core::cmp;
30 use kernel::str::CStr;
32 #[derive(Debug, Clone, Copy, PartialEq, Eq, Ord, PartialOrd)]
33 struct Version(usize);
35 // Generator polynomials for ECC, only those that are needed for low quality.
36 const P7: [u8; 7] = [87, 229, 146, 149, 238, 102, 21];
37 const P10: [u8; 10] = [251, 67, 46, 61, 118, 70, 64, 94, 32, 45];
38 const P15: [u8; 15] = [
39 8, 183, 61, 91, 202, 37, 51, 58, 58, 237, 140, 124, 5, 99, 105,
40 ];
41 const P18: [u8; 18] = [
42 215, 234, 158, 94, 184, 97, 118, 170, 79, 187, 152, 148, 252, 179, 5, 98, 96, 153,
43 ];
44 const P20: [u8; 20] = [
45 17, 60, 79, 50, 61, 163, 26, 187, 202, 180, 221, 225, 83, 239, 156, 164, 212, 212, 188, 190,
46 ];
47 const P22: [u8; 22] = [
48 210, 171, 247, 242, 93, 230, 14, 109, 221, 53, 200, 74, 8, 172, 98, 80, 219, 134, 160, 105,
49 165, 231,
50 ];
51 const P24: [u8; 24] = [
52 229, 121, 135, 48, 211, 117, 251, 126, 159, 180, 169, 152, 192, 226, 228, 218, 111, 0, 117,
53 232, 87, 96, 227, 21,
54 ];
55 const P26: [u8; 26] = [
56 173, 125, 158, 2, 103, 182, 118, 17, 145, 201, 111, 28, 165, 53, 161, 21, 245, 142, 13, 102,
57 48, 227, 153, 145, 218, 70,
58 ];
59 const P28: [u8; 28] = [
60 168, 223, 200, 104, 224, 234, 108, 180, 110, 190, 195, 147, 205, 27, 232, 201, 21, 43, 245, 87,
61 42, 195, 212, 119, 242, 37, 9, 123,
62 ];
63 const P30: [u8; 30] = [
64 41, 173, 145, 152, 216, 31, 179, 182, 50, 48, 110, 86, 239, 96, 222, 125, 42, 173, 226, 193,
65 224, 130, 156, 37, 251, 216, 238, 40, 192, 180,
66 ];
68 /// QR Code parameters for Low quality ECC:
69 /// - Error Correction polynomial.
70 /// - Number of blocks in group 1.
71 /// - Number of blocks in group 2.
72 /// - Block size in group 1.
73 ///
74 /// (Block size in group 2 is one more than group 1).
75 struct VersionParameter(&'static [u8], u8, u8, u8);
76 const VPARAM: [VersionParameter; 40] = [
77 VersionParameter(&P7, 1, 0, 19), // V1
78 VersionParameter(&P10, 1, 0, 34), // V2
79 VersionParameter(&P15, 1, 0, 55), // V3
80 VersionParameter(&P20, 1, 0, 80), // V4
81 VersionParameter(&P26, 1, 0, 108), // V5
82 VersionParameter(&P18, 2, 0, 68), // V6
83 VersionParameter(&P20, 2, 0, 78), // V7
84 VersionParameter(&P24, 2, 0, 97), // V8
85 VersionParameter(&P30, 2, 0, 116), // V9
86 VersionParameter(&P18, 2, 2, 68), // V10
87 VersionParameter(&P20, 4, 0, 81), // V11
88 VersionParameter(&P24, 2, 2, 92), // V12
89 VersionParameter(&P26, 4, 0, 107), // V13
90 VersionParameter(&P30, 3, 1, 115), // V14
91 VersionParameter(&P22, 5, 1, 87), // V15
92 VersionParameter(&P24, 5, 1, 98), // V16
93 VersionParameter(&P28, 1, 5, 107), // V17
94 VersionParameter(&P30, 5, 1, 120), // V18
95 VersionParameter(&P28, 3, 4, 113), // V19
96 VersionParameter(&P28, 3, 5, 107), // V20
97 VersionParameter(&P28, 4, 4, 116), // V21
98 VersionParameter(&P28, 2, 7, 111), // V22
99 VersionParameter(&P30, 4, 5, 121), // V23
100 VersionParameter(&P30, 6, 4, 117), // V24
101 VersionParameter(&P26, 8, 4, 106), // V25
102 VersionParameter(&P28, 10, 2, 114), // V26
103 VersionParameter(&P30, 8, 4, 122), // V27
104 VersionParameter(&P30, 3, 10, 117), // V28
105 VersionParameter(&P30, 7, 7, 116), // V29
106 VersionParameter(&P30, 5, 10, 115), // V30
107 VersionParameter(&P30, 13, 3, 115), // V31
108 VersionParameter(&P30, 17, 0, 115), // V32
109 VersionParameter(&P30, 17, 1, 115), // V33
110 VersionParameter(&P30, 13, 6, 115), // V34
111 VersionParameter(&P30, 12, 7, 121), // V35
112 VersionParameter(&P30, 6, 14, 121), // V36
113 VersionParameter(&P30, 17, 4, 122), // V37
114 VersionParameter(&P30, 4, 18, 122), // V38
115 VersionParameter(&P30, 20, 4, 117), // V39
116 VersionParameter(&P30, 19, 6, 118), // V40
117 ];
119 const MAX_EC_SIZE: usize = 30;
120 const MAX_BLK_SIZE: usize = 123;
122 /// Position of the alignment pattern grid.
123 const ALIGNMENT_PATTERNS: [&[u8]; 40] = [
124 &[],
125 &[6, 18],
126 &[6, 22],
127 &[6, 26],
128 &[6, 30],
129 &[6, 34],
130 &[6, 22, 38],
131 &[6, 24, 42],
132 &[6, 26, 46],
133 &[6, 28, 50],
134 &[6, 30, 54],
135 &[6, 32, 58],
136 &[6, 34, 62],
137 &[6, 26, 46, 66],
138 &[6, 26, 48, 70],
139 &[6, 26, 50, 74],
140 &[6, 30, 54, 78],
141 &[6, 30, 56, 82],
142 &[6, 30, 58, 86],
143 &[6, 34, 62, 90],
144 &[6, 28, 50, 72, 94],
145 &[6, 26, 50, 74, 98],
146 &[6, 30, 54, 78, 102],
147 &[6, 28, 54, 80, 106],
148 &[6, 32, 58, 84, 110],
149 &[6, 30, 58, 86, 114],
150 &[6, 34, 62, 90, 118],
151 &[6, 26, 50, 74, 98, 122],
152 &[6, 30, 54, 78, 102, 126],
153 &[6, 26, 52, 78, 104, 130],
154 &[6, 30, 56, 82, 108, 134],
155 &[6, 34, 60, 86, 112, 138],
156 &[6, 30, 58, 86, 114, 142],
157 &[6, 34, 62, 90, 118, 146],
158 &[6, 30, 54, 78, 102, 126, 150],
159 &[6, 24, 50, 76, 102, 128, 154],
160 &[6, 28, 54, 80, 106, 132, 158],
161 &[6, 32, 58, 84, 110, 136, 162],
162 &[6, 26, 54, 82, 110, 138, 166],
163 &[6, 30, 58, 86, 114, 142, 170],
164 ];
166 /// Version information for format V7-V40.
167 const VERSION_INFORMATION: [u32; 34] = [
168 0b00_0111_1100_1001_0100,
169 0b00_1000_0101_1011_1100,
170 0b00_1001_1010_1001_1001,
171 0b00_1010_0100_1101_0011,
172 0b00_1011_1011_1111_0110,
173 0b00_1100_0111_0110_0010,
174 0b00_1101_1000_0100_0111,
175 0b00_1110_0110_0000_1101,
176 0b00_1111_1001_0010_1000,
177 0b01_0000_1011_0111_1000,
178 0b01_0001_0100_0101_1101,
179 0b01_0010_1010_0001_0111,
180 0b01_0011_0101_0011_0010,
181 0b01_0100_1001_1010_0110,
182 0b01_0101_0110_1000_0011,
183 0b01_0110_1000_1100_1001,
184 0b01_0111_0111_1110_1100,
185 0b01_1000_1110_1100_0100,
186 0b01_1001_0001_1110_0001,
187 0b01_1010_1111_1010_1011,
188 0b01_1011_0000_1000_1110,
189 0b01_1100_1100_0001_1010,
190 0b01_1101_0011_0011_1111,
191 0b01_1110_1101_0111_0101,
192 0b01_1111_0010_0101_0000,
193 0b10_0000_1001_1101_0101,
194 0b10_0001_0110_1111_0000,
195 0b10_0010_1000_1011_1010,
196 0b10_0011_0111_1001_1111,
197 0b10_0100_1011_0000_1011,
198 0b10_0101_0100_0010_1110,
199 0b10_0110_1010_0110_0100,
200 0b10_0111_0101_0100_0001,
201 0b10_1000_1100_0110_1001,
202 ];
204 /// Format info for low quality ECC.
205 const FORMAT_INFOS_QR_L: [u16; 8] = [
206 0x77c4, 0x72f3, 0x7daa, 0x789d, 0x662f, 0x6318, 0x6c41, 0x6976,
207 ];
209 impl Version {
210 /// Returns the smallest QR version than can hold these segments.
211 fn from_segments(segments: &[&Segment<'_>]) -> Option<Version> {
212 (1..=40)
213 .map(Version)
214 .find(|&v| v.max_data() * 8 >= segments.iter().map(|s| s.total_size_bits(v)).sum())
215 }
217 fn width(&self) -> u8 {
218 (self.0 as u8) * 4 + 17
219 }
221 fn max_data(&self) -> usize {
222 self.g1_blk_size() * self.g1_blocks() + (self.g1_blk_size() + 1) * self.g2_blocks()
223 }
225 fn ec_size(&self) -> usize {
226 VPARAM[self.0 - 1].0.len()
227 }
229 fn g1_blocks(&self) -> usize {
230 VPARAM[self.0 - 1].1 as usize
231 }
233 fn g2_blocks(&self) -> usize {
234 VPARAM[self.0 - 1].2 as usize
235 }
237 fn g1_blk_size(&self) -> usize {
238 VPARAM[self.0 - 1].3 as usize
239 }
241 fn alignment_pattern(&self) -> &'static [u8] {
242 ALIGNMENT_PATTERNS[self.0 - 1]
243 }
245 fn poly(&self) -> &'static [u8] {
246 VPARAM[self.0 - 1].0
247 }
249 fn version_info(&self) -> u32 {
250 if *self >= Version(7) {
251 VERSION_INFORMATION[self.0 - 7]
252 } else {
253 0
254 }
255 }
256 }
258 /// Exponential table for Galois Field GF(256).
259 const EXP_TABLE: [u8; 256] = [
260 1, 2, 4, 8, 16, 32, 64, 128, 29, 58, 116, 232, 205, 135, 19, 38, 76, 152, 45, 90, 180, 117,
261 234, 201, 143, 3, 6, 12, 24, 48, 96, 192, 157, 39, 78, 156, 37, 74, 148, 53, 106, 212, 181,
262 119, 238, 193, 159, 35, 70, 140, 5, 10, 20, 40, 80, 160, 93, 186, 105, 210, 185, 111, 222, 161,
263 95, 190, 97, 194, 153, 47, 94, 188, 101, 202, 137, 15, 30, 60, 120, 240, 253, 231, 211, 187,
264 107, 214, 177, 127, 254, 225, 223, 163, 91, 182, 113, 226, 217, 175, 67, 134, 17, 34, 68, 136,
265 13, 26, 52, 104, 208, 189, 103, 206, 129, 31, 62, 124, 248, 237, 199, 147, 59, 118, 236, 197,
266 151, 51, 102, 204, 133, 23, 46, 92, 184, 109, 218, 169, 79, 158, 33, 66, 132, 21, 42, 84, 168,
267 77, 154, 41, 82, 164, 85, 170, 73, 146, 57, 114, 228, 213, 183, 115, 230, 209, 191, 99, 198,
268 145, 63, 126, 252, 229, 215, 179, 123, 246, 241, 255, 227, 219, 171, 75, 150, 49, 98, 196, 149,
269 55, 110, 220, 165, 87, 174, 65, 130, 25, 50, 100, 200, 141, 7, 14, 28, 56, 112, 224, 221, 167,
270 83, 166, 81, 162, 89, 178, 121, 242, 249, 239, 195, 155, 43, 86, 172, 69, 138, 9, 18, 36, 72,
271 144, 61, 122, 244, 245, 247, 243, 251, 235, 203, 139, 11, 22, 44, 88, 176, 125, 250, 233, 207,
272 131, 27, 54, 108, 216, 173, 71, 142, 1,
273 ];
275 /// Reverse exponential table for Galois Field GF(256).
276 const LOG_TABLE: [u8; 256] = [
277 175, 0, 1, 25, 2, 50, 26, 198, 3, 223, 51, 238, 27, 104, 199, 75, 4, 100, 224, 14, 52, 141,
278 239, 129, 28, 193, 105, 248, 200, 8, 76, 113, 5, 138, 101, 47, 225, 36, 15, 33, 53, 147, 142,
279 218, 240, 18, 130, 69, 29, 181, 194, 125, 106, 39, 249, 185, 201, 154, 9, 120, 77, 228, 114,
280 166, 6, 191, 139, 98, 102, 221, 48, 253, 226, 152, 37, 179, 16, 145, 34, 136, 54, 208, 148,
281 206, 143, 150, 219, 189, 241, 210, 19, 92, 131, 56, 70, 64, 30, 66, 182, 163, 195, 72, 126,
282 110, 107, 58, 40, 84, 250, 133, 186, 61, 202, 94, 155, 159, 10, 21, 121, 43, 78, 212, 229, 172,
283 115, 243, 167, 87, 7, 112, 192, 247, 140, 128, 99, 13, 103, 74, 222, 237, 49, 197, 254, 24,
284 227, 165, 153, 119, 38, 184, 180, 124, 17, 68, 146, 217, 35, 32, 137, 46, 55, 63, 209, 91, 149,
285 188, 207, 205, 144, 135, 151, 178, 220, 252, 190, 97, 242, 86, 211, 171, 20, 42, 93, 158, 132,
286 60, 57, 83, 71, 109, 65, 162, 31, 45, 67, 216, 183, 123, 164, 118, 196, 23, 73, 236, 127, 12,
287 111, 246, 108, 161, 59, 82, 41, 157, 85, 170, 251, 96, 134, 177, 187, 204, 62, 90, 203, 89, 95,
288 176, 156, 169, 160, 81, 11, 245, 22, 235, 122, 117, 44, 215, 79, 174, 213, 233, 230, 231, 173,
289 232, 116, 214, 244, 234, 168, 80, 88, 175,
290 ];
292 // 4 bits segment header.
293 const MODE_STOP: u16 = 0;
294 const MODE_NUMERIC: u16 = 1;
295 const MODE_BINARY: u16 = 4;
296 /// Padding bytes.
297 const PADDING: [u8; 2] = [236, 17];
299 /// Get the next 13 bits of data, starting at specified offset (in bits).
300 fn get_next_13b(data: &[u8], offset: usize) -> Option<(u16, usize)> {
301 if offset < data.len() * 8 {
302 let size = cmp::min(13, data.len() * 8 - offset);
303 let byte_off = offset / 8;
304 let bit_off = offset % 8;
305 // `b` is 20 at max (`bit_off` <= 7 and `size` <= 13).
306 let b = (bit_off + size) as u16;
308 let first_byte = (data[byte_off] << bit_off >> bit_off) as u16;
310 let number = match b {
311 0..=8 => first_byte >> (8 - b),
312 9..=16 => (first_byte << (b - 8)) + (data[byte_off + 1] >> (16 - b)) as u16,
313 _ => {
314 (first_byte << (b - 8))
315 + ((data[byte_off + 1] as u16) << (b - 16))
316 + (data[byte_off + 2] >> (24 - b)) as u16
317 }
318 };
319 Some((number, size))
320 } else {
321 None
322 }
323 }
325 /// Number of bits to encode characters in numeric mode.
326 const NUM_CHARS_BITS: [usize; 4] = [0, 4, 7, 10];
327 const POW10: [u16; 4] = [1, 10, 100, 1000];
329 enum Segment<'a> {
330 Numeric(&'a [u8]),
331 Binary(&'a [u8]),
332 }
334 impl Segment<'_> {
335 fn get_header(&self) -> (u16, usize) {
336 match self {
337 Segment::Binary(_) => (MODE_BINARY, 4),
338 Segment::Numeric(_) => (MODE_NUMERIC, 4),
339 }
340 }
342 // Returns the size of the length field in bits, depending on QR Version.
343 fn length_bits_count(&self, version: Version) -> usize {
344 let Version(v) = version;
345 match self {
346 Segment::Binary(_) => match v {
347 1..=9 => 8,
348 _ => 16,
349 },
350 Segment::Numeric(_) => match v {
351 1..=9 => 10,
352 10..=26 => 12,
353 _ => 14,
354 },
355 }
356 }
358 // Number of characters in the segment.
359 fn character_count(&self) -> usize {
360 match self {
361 Segment::Binary(data) => data.len(),
362 Segment::Numeric(data) => {
363 let data_bits = data.len() * 8;
364 let last_chars = match data_bits % 13 {
365 1 => 1,
366 k => (k + 1) / 3,
367 };
368 // 4 decimal numbers per 13bits + remainder.
369 4 * (data_bits / 13) + last_chars
370 }
371 }
372 }
374 fn get_length_field(&self, version: Version) -> (u16, usize) {
375 (
376 self.character_count() as u16,
377 self.length_bits_count(version),
378 )
379 }
381 fn total_size_bits(&self, version: Version) -> usize {
382 let data_size = match self {
383 Segment::Binary(data) => data.len() * 8,
384 Segment::Numeric(_) => {
385 let digits = self.character_count();
386 10 * (digits / 3) + NUM_CHARS_BITS[digits % 3]
387 }
388 };
389 // header + length + data.
390 4 + self.length_bits_count(version) + data_size
391 }
393 fn iter(&self) -> SegmentIterator<'_> {
394 SegmentIterator {
395 segment: self,
396 offset: 0,
397 carry: 0,
398 carry_len: 0,
399 }
400 }
401 }
403 struct SegmentIterator<'a> {
404 segment: &'a Segment<'a>,
405 offset: usize,
406 carry: u16,
407 carry_len: usize,
408 }
410 impl Iterator for SegmentIterator<'_> {
411 type Item = (u16, usize);
413 fn next(&mut self) -> Option<Self::Item> {
414 match self.segment {
415 Segment::Binary(data) => {
416 if self.offset < data.len() {
417 let byte = data[self.offset] as u16;
418 self.offset += 1;
419 Some((byte, 8))
420 } else {
421 None
422 }
423 }
424 Segment::Numeric(data) => {
425 if self.carry_len == 3 {
426 let out = (self.carry, NUM_CHARS_BITS[self.carry_len]);
427 self.carry_len = 0;
428 self.carry = 0;
429 Some(out)
430 } else if let Some((bits, size)) = get_next_13b(data, self.offset) {
431 self.offset += size;
432 let new_chars = match size {
433 1 => 1,
434 k => (k + 1) / 3,
435 };
436 if self.carry_len + new_chars > 3 {
437 self.carry_len = new_chars + self.carry_len - 3;
438 let out = (
439 self.carry * POW10[new_chars - self.carry_len]
440 + bits / POW10[self.carry_len],
441 NUM_CHARS_BITS[3],
442 );
443 self.carry = bits % POW10[self.carry_len];
444 Some(out)
445 } else {
446 let out = (
447 self.carry * POW10[new_chars] + bits,
448 NUM_CHARS_BITS[self.carry_len + new_chars],
449 );
450 self.carry_len = 0;
451 Some(out)
452 }
453 } else if self.carry_len > 0 {
454 let out = (self.carry, NUM_CHARS_BITS[self.carry_len]);
455 self.carry_len = 0;
456 Some(out)
457 } else {
458 None
459 }
460 }
461 }
462 }
463 }
465 struct EncodedMsg<'a> {
466 data: &'a mut [u8],
467 ec_size: usize,
468 g1_blocks: usize,
469 g2_blocks: usize,
470 g1_blk_size: usize,
471 g2_blk_size: usize,
472 poly: &'static [u8],
473 version: Version,
474 }
476 /// Data to be put in the QR code, with correct segment encoding, padding, and
477 /// Error Code Correction.
478 impl EncodedMsg<'_> {
479 fn new<'a>(segments: &[&Segment<'_>], data: &'a mut [u8]) -> Option<EncodedMsg<'a>> {
480 let version = Version::from_segments(segments)?;
481 let ec_size = version.ec_size();
482 let g1_blocks = version.g1_blocks();
483 let g2_blocks = version.g2_blocks();
484 let g1_blk_size = version.g1_blk_size();
485 let g2_blk_size = g1_blk_size + 1;
486 let poly = version.poly();
488 // clear the output.
489 data.fill(0);
491 let mut em = EncodedMsg {
492 data,
493 ec_size,
494 g1_blocks,
495 g2_blocks,
496 g1_blk_size,
497 g2_blk_size,
498 poly,
499 version,
500 };
501 em.encode(segments);
502 Some(em)
503 }
505 /// Push bits of data at an offset (in bits).
506 fn push(&mut self, offset: &mut usize, bits: (u16, usize)) {
507 let (number, len_bits) = bits;
508 let byte_off = *offset / 8;
509 let bit_off = *offset % 8;
510 let b = bit_off + len_bits;
512 match (bit_off, b) {
513 (0, 0..=8) => {
514 self.data[byte_off] = (number << (8 - b)) as u8;
515 }
516 (0, _) => {
517 self.data[byte_off] = (number >> (b - 8)) as u8;
518 self.data[byte_off + 1] = (number << (16 - b)) as u8;
519 }
520 (_, 0..=8) => {
521 self.data[byte_off] |= (number << (8 - b)) as u8;
522 }
523 (_, 9..=16) => {
524 self.data[byte_off] |= (number >> (b - 8)) as u8;
525 self.data[byte_off + 1] = (number << (16 - b)) as u8;
526 }
527 _ => {
528 self.data[byte_off] |= (number >> (b - 8)) as u8;
529 self.data[byte_off + 1] = (number >> (b - 16)) as u8;
530 self.data[byte_off + 2] = (number << (24 - b)) as u8;
531 }
532 }
533 *offset += len_bits;
534 }
536 fn add_segments(&mut self, segments: &[&Segment<'_>]) {
537 let mut offset: usize = 0;
539 for s in segments.iter() {
540 self.push(&mut offset, s.get_header());
541 self.push(&mut offset, s.get_length_field(self.version));
542 for bits in s.iter() {
543 self.push(&mut offset, bits);
544 }
545 }
546 self.push(&mut offset, (MODE_STOP, 4));
548 let pad_offset = (offset + 7) / 8;
549 for i in pad_offset..self.version.max_data() {
550 self.data[i] = PADDING[(i & 1) ^ (pad_offset & 1)];
551 }
552 }
554 fn error_code_for_blocks(&mut self, offset: usize, size: usize, ec_offset: usize) {
555 let mut tmp: [u8; MAX_BLK_SIZE + MAX_EC_SIZE] = [0; MAX_BLK_SIZE + MAX_EC_SIZE];
557 tmp[0..size].copy_from_slice(&self.data[offset..offset + size]);
558 for i in 0..size {
559 let lead_coeff = tmp[i] as usize;
560 if lead_coeff == 0 {
561 continue;
562 }
563 let log_lead_coeff = usize::from(LOG_TABLE[lead_coeff]);
564 for (u, &v) in tmp[i + 1..].iter_mut().zip(self.poly.iter()) {
565 *u ^= EXP_TABLE[(usize::from(v) + log_lead_coeff) % 255];
566 }
567 }
568 self.data[ec_offset..ec_offset + self.ec_size]
569 .copy_from_slice(&tmp[size..size + self.ec_size]);
570 }
572 fn compute_error_code(&mut self) {
573 let mut offset = 0;
574 let mut ec_offset = self.g1_blocks * self.g1_blk_size + self.g2_blocks * self.g2_blk_size;
576 for _ in 0..self.g1_blocks {
577 self.error_code_for_blocks(offset, self.g1_blk_size, ec_offset);
578 offset += self.g1_blk_size;
579 ec_offset += self.ec_size;
580 }
581 for _ in 0..self.g2_blocks {
582 self.error_code_for_blocks(offset, self.g2_blk_size, ec_offset);
583 offset += self.g2_blk_size;
584 ec_offset += self.ec_size;
585 }
586 }
588 fn encode(&mut self, segments: &[&Segment<'_>]) {
589 self.add_segments(segments);
590 self.compute_error_code();
591 }
593 fn iter(&self) -> EncodedMsgIterator<'_> {
594 EncodedMsgIterator {
595 em: self,
596 offset: 0,
597 }
598 }
599 }
601 /// Iterator, to retrieve the data in the interleaved order needed by QR code.
602 struct EncodedMsgIterator<'a> {
603 em: &'a EncodedMsg<'a>,
604 offset: usize,
605 }
607 impl Iterator for EncodedMsgIterator<'_> {
608 type Item = u8;
610 // Send the bytes in interleaved mode, first byte of first block of group1,
611 // then first byte of second block of group1, ...
612 fn next(&mut self) -> Option<Self::Item> {
613 let em = self.em;
614 let blocks = em.g1_blocks + em.g2_blocks;
615 let g1_end = em.g1_blocks * em.g1_blk_size;
616 let g2_end = g1_end + em.g2_blocks * em.g2_blk_size;
617 let ec_end = g2_end + em.ec_size * blocks;
619 if self.offset >= ec_end {
620 return None;
621 }
623 let offset = if self.offset < em.g1_blk_size * blocks {
624 // group1 and group2 interleaved
625 let blk = self.offset % blocks;
626 let blk_off = self.offset / blocks;
627 if blk < em.g1_blocks {
628 blk * em.g1_blk_size + blk_off
629 } else {
630 g1_end + em.g2_blk_size * (blk - em.g1_blocks) + blk_off
631 }
632 } else if self.offset < g2_end {
633 // last byte of group2 blocks
634 let blk2 = self.offset - blocks * em.g1_blk_size;
635 em.g1_blk_size * em.g1_blocks + blk2 * em.g2_blk_size + em.g2_blk_size - 1
636 } else {
637 // EC blocks
638 let ec_offset = self.offset - g2_end;
639 let blk = ec_offset % blocks;
640 let blk_off = ec_offset / blocks;
642 g2_end + blk * em.ec_size + blk_off
643 };
644 self.offset += 1;
645 Some(em.data[offset])
646 }
647 }
649 /// A QR code image, encoded as a linear binary framebuffer.
650 /// 1 bit per module (pixel), each new line start at next byte boundary.
651 /// Max width is 177 for V40 QR code, so `u8` is enough for coordinate.
652 struct QrImage<'a> {
653 data: &'a mut [u8],
654 width: u8,
655 stride: u8,
656 version: Version,
657 }
659 impl QrImage<'_> {
660 fn new<'a, 'b>(em: &'b EncodedMsg<'b>, qrdata: &'a mut [u8]) -> QrImage<'a> {
661 let width = em.version.width();
662 let stride = (width + 7) / 8;
663 let data = qrdata;
665 let mut qr_image = QrImage {
666 data,
667 width,
668 stride,
669 version: em.version,
670 };
671 qr_image.draw_all(em.iter());
672 qr_image
673 }
675 fn clear(&mut self) {
676 self.data.fill(0);
677 }
679 // Set pixel to light color.
680 fn set(&mut self, x: u8, y: u8) {
681 let off = y as usize * self.stride as usize + x as usize / 8;
682 let mut v = self.data[off];
683 v |= 0x80 >> (x % 8);
684 self.data[off] = v;
685 }
687 // Invert a module color.
688 fn xor(&mut self, x: u8, y: u8) {
689 let off = y as usize * self.stride as usize + x as usize / 8;
690 self.data[off] ^= 0x80 >> (x % 8);
691 }
693 // Draw a light square at (x, y) top left corner.
694 fn draw_square(&mut self, x: u8, y: u8, size: u8) {
695 for k in 0..size {
696 self.set(x + k, y);
697 self.set(x, y + k + 1);
698 self.set(x + size, y + k);
699 self.set(x + k + 1, y + size);
700 }
701 }
703 // Finder pattern: 3 8x8 square at the corners.
704 fn draw_finders(&mut self) {
705 self.draw_square(1, 1, 4);
706 self.draw_square(self.width - 6, 1, 4);
707 self.draw_square(1, self.width - 6, 4);
708 for k in 0..8 {
709 self.set(k, 7);
710 self.set(self.width - k - 1, 7);
711 self.set(k, self.width - 8);
712 }
713 for k in 0..7 {
714 self.set(7, k);
715 self.set(self.width - 8, k);
716 self.set(7, self.width - 1 - k);
717 }
718 }
720 fn is_finder(&self, x: u8, y: u8) -> bool {
721 let end = self.width - 8;
722 #[expect(clippy::nonminimal_bool)]
723 {
724 (x < 8 && y < 8) || (x < 8 && y >= end) || (x >= end && y < 8)
725 }
726 }
728 // Alignment pattern: 5x5 squares in a grid.
729 fn draw_alignments(&mut self) {
730 let positions = self.version.alignment_pattern();
731 for &x in positions.iter() {
732 for &y in positions.iter() {
733 if !self.is_finder(x, y) {
734 self.draw_square(x - 1, y - 1, 2);
735 }
736 }
737 }
738 }
740 fn is_alignment(&self, x: u8, y: u8) -> bool {
741 let positions = self.version.alignment_pattern();
742 for &ax in positions.iter() {
743 for &ay in positions.iter() {
744 if self.is_finder(ax, ay) {
745 continue;
746 }
747 if x >= ax - 2 && x <= ax + 2 && y >= ay - 2 && y <= ay + 2 {
748 return true;
749 }
750 }
751 }
752 false
753 }
755 // Timing pattern: 2 dotted line between the finder patterns.
756 fn draw_timing_patterns(&mut self) {
757 let end = self.width - 8;
759 for x in (9..end).step_by(2) {
760 self.set(x, 6);
761 self.set(6, x);
762 }
763 }
765 fn is_timing(&self, x: u8, y: u8) -> bool {
766 x == 6 || y == 6
767 }
769 // Mask info: 15 bits around the finders, written twice for redundancy.
770 fn draw_maskinfo(&mut self) {
771 let info: u16 = FORMAT_INFOS_QR_L[0];
772 let mut skip = 0;
774 for k in 0..7 {
775 if k == 6 {
776 skip = 1;
777 }
778 if info & (1 << (14 - k)) == 0 {
779 self.set(k + skip, 8);
780 self.set(8, self.width - 1 - k);
781 }
782 }
783 skip = 0;
784 for k in 0..8 {
785 if k == 2 {
786 skip = 1;
787 }
788 if info & (1 << (7 - k)) == 0 {
789 self.set(8, 8 - skip - k);
790 self.set(self.width - 8 + k, 8);
791 }
792 }
793 }
795 fn is_maskinfo(&self, x: u8, y: u8) -> bool {
796 let end = self.width - 8;
797 // Count the dark module as mask info.
798 (x <= 8 && y == 8) || (y <= 8 && x == 8) || (x == 8 && y >= end) || (x >= end && y == 8)
799 }
801 // Version info: 18bits written twice, close to the finders.
802 fn draw_version_info(&mut self) {
803 let vinfo = self.version.version_info();
804 let pos = self.width - 11;
806 if vinfo != 0 {
807 for x in 0..3 {
808 for y in 0..6 {
809 if vinfo & (1 << (x + y * 3)) == 0 {
810 self.set(x + pos, y);
811 self.set(y, x + pos);
812 }
813 }
814 }
815 }
816 }
818 fn is_version_info(&self, x: u8, y: u8) -> bool {
819 let vinfo = self.version.version_info();
820 let pos = self.width - 11;
822 vinfo != 0 && ((x >= pos && x < pos + 3 && y < 6) || (y >= pos && y < pos + 3 && x < 6))
823 }
825 // Returns true if the module is reserved (Not usable for data and EC).
826 fn is_reserved(&self, x: u8, y: u8) -> bool {
827 self.is_alignment(x, y)
828 || self.is_finder(x, y)
829 || self.is_timing(x, y)
830 || self.is_maskinfo(x, y)
831 || self.is_version_info(x, y)
832 }
834 // Last module to draw, at bottom left corner.
835 fn is_last(&self, x: u8, y: u8) -> bool {
836 x == 0 && y == self.width - 1
837 }
839 // Move to the next module according to QR code order.
840 // From bottom right corner, to bottom left corner.
841 fn next(&self, x: u8, y: u8) -> (u8, u8) {
842 let x_adj = if x <= 6 { x + 1 } else { x };
843 let column_type = (self.width - x_adj) % 4;
845 match column_type {
846 2 if y > 0 => (x + 1, y - 1),
847 0 if y < self.width - 1 => (x + 1, y + 1),
848 0 | 2 if x == 7 => (x - 2, y),
849 _ => (x - 1, y),
850 }
851 }
853 // Find next module that can hold data.
854 fn next_available(&self, x: u8, y: u8) -> (u8, u8) {
855 let (mut x, mut y) = self.next(x, y);
856 while self.is_reserved(x, y) && !self.is_last(x, y) {
857 (x, y) = self.next(x, y);
858 }
859 (x, y)
860 }
862 fn draw_data(&mut self, data: impl Iterator<Item = u8>) {
863 let (mut x, mut y) = (self.width - 1, self.width - 1);
864 for byte in data {
865 for s in 0..8 {
866 if byte & (0x80 >> s) == 0 {
867 self.set(x, y);
868 }
869 (x, y) = self.next_available(x, y);
870 }
871 }
872 // Set the remaining modules (0, 3 or 7 depending on version).
873 // because 0 correspond to a light module.
874 while !self.is_last(x, y) {
875 if !self.is_reserved(x, y) {
876 self.set(x, y);
877 }
878 (x, y) = self.next(x, y);
879 }
880 }
882 // Apply checkerboard mask to all non-reserved modules.
883 fn apply_mask(&mut self) {
884 for x in 0..self.width {
885 for y in 0..self.width {
886 if (x ^ y) % 2 == 0 && !self.is_reserved(x, y) {
887 self.xor(x, y);
888 }
889 }
890 }
891 }
893 // Draw the QR code with the provided data iterator.
894 fn draw_all(&mut self, data: impl Iterator<Item = u8>) {
895 // First clear the table, as it may have already some data.
896 self.clear();
897 self.draw_finders();
898 self.draw_alignments();
899 self.draw_timing_patterns();
900 self.draw_version_info();
901 self.draw_data(data);
902 self.draw_maskinfo();
903 self.apply_mask();
904 }
905 }
907 /// C entry point for the rust QR Code generator.
908 ///
909 /// Write the QR code image in the data buffer, and return the QR code width,
910 /// or 0, if the data doesn't fit in a QR code.
911 ///
912 /// * `url`: The base URL of the QR code. It will be encoded as Binary segment.
913 /// * `data`: A pointer to the binary data, to be encoded. if URL is NULL, it
914 /// will be encoded as binary segment, otherwise it will be encoded
915 /// efficiently as a numeric segment, and appended to the URL.
916 /// * `data_len`: Length of the data, that needs to be encoded, must be less
917 /// than data_size.
918 /// * `data_size`: Size of data buffer, it should be at least 4071 bytes to hold
919 /// a V40 QR code. It will then be overwritten with the QR code image.
920 /// * `tmp`: A temporary buffer that the QR code encoder will use, to write the
921 /// segments and ECC.
922 /// * `tmp_size`: Size of the temporary buffer, it must be at least 3706 bytes
923 /// long for V40.
924 ///
925 /// # Safety
926 ///
927 /// * `url` must be null or point at a nul-terminated string.
928 /// * `data` must be valid for reading and writing for `data_size` bytes.
929 /// * `tmp` must be valid for reading and writing for `tmp_size` bytes.
930 ///
931 /// They must remain valid for the duration of the function call.
933 #[no_mangle]
934 pub unsafe extern "C" fn drm_panic_qr_generate(
935 url: *const i8,
936 data: *mut u8,
937 data_len: usize,
938 data_size: usize,
939 tmp: *mut u8,
940 tmp_size: usize,
941 ) -> u8 {
942 if data_size < 4071 || tmp_size < 3706 || data_len > data_size {
943 return 0;
944 }
945 // SAFETY: The caller ensures that `data` is a valid pointer for reading and
946 // writing `data_size` bytes.
947 let data_slice: &mut [u8] = unsafe { core::slice::from_raw_parts_mut(data, data_size) };
948 // SAFETY: The caller ensures that `tmp` is a valid pointer for reading and
949 // writing `tmp_size` bytes.
950 let tmp_slice: &mut [u8] = unsafe { core::slice::from_raw_parts_mut(tmp, tmp_size) };
951 if url.is_null() {
952 match EncodedMsg::new(&[&Segment::Binary(&data_slice[0..data_len])], tmp_slice) {
953 None => 0,
954 Some(em) => {
955 let qr_image = QrImage::new(&em, data_slice);
956 qr_image.width
957 }
958 }
959 } else {
960 // SAFETY: The caller ensures that `url` is a valid pointer to a
961 // nul-terminated string.
962 let url_cstr: &CStr = unsafe { CStr::from_char_ptr(url) };
963 let segments = &[
964 &Segment::Binary(url_cstr.as_bytes()),
965 &Segment::Numeric(&data_slice[0..data_len]),
966 ];
967 match EncodedMsg::new(segments, tmp_slice) {
968 None => 0,
969 Some(em) => {
970 let qr_image = QrImage::new(&em, data_slice);
971 qr_image.width
972 }
973 }
974 }
975 }
977 /// Returns the maximum data size that can fit in a QR code of this version.
978 /// * `version`: QR code version, between 1-40.
979 /// * `url_len`: Length of the URL.
980 ///
981 /// * If `url_len` > 0, remove the 2 segments header/length and also count the
982 /// conversion to numeric segments.
983 /// * If `url_len` = 0, only removes 3 bytes for 1 binary segment.
984 #[no_mangle]
985 pub extern "C" fn drm_panic_qr_max_data_size(version: u8, url_len: usize) -> usize {
986 #[expect(clippy::manual_range_contains)]
987 if version < 1 || version > 40 {
988 return 0;
989 }
990 let max_data = Version(version as usize).max_data();
992 if url_len > 0 {
993 // Binary segment (URL) 4 + 16 bits, numeric segment (kmsg) 4 + 12 bits => 5 bytes.
994 if url_len + 5 >= max_data {
995 0
996 } else {
997 let max = max_data - url_len - 5;
998 (max * 39) / 40
999 }
1000 } else {
1001 // Remove 3 bytes for the binary segment (header 4 bits, length 16 bits, stop 4bits).
1002 max_data - 3
1003 }
1004 }