Loading...
Note: File does not exist in v3.1.
1// SPDX-License-Identifier: MIT
2
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>
28
29use core::cmp;
30use kernel::str::CStr;
31
32#[derive(Debug, Clone, Copy, PartialEq, Eq, Ord, PartialOrd)]
33struct Version(usize);
34
35// Generator polynomials for ECC, only those that are needed for low quality.
36const P7: [u8; 7] = [87, 229, 146, 149, 238, 102, 21];
37const P10: [u8; 10] = [251, 67, 46, 61, 118, 70, 64, 94, 32, 45];
38const P15: [u8; 15] = [
39 8, 183, 61, 91, 202, 37, 51, 58, 58, 237, 140, 124, 5, 99, 105,
40];
41const P18: [u8; 18] = [
42 215, 234, 158, 94, 184, 97, 118, 170, 79, 187, 152, 148, 252, 179, 5, 98, 96, 153,
43];
44const 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];
47const 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];
51const 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];
55const 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];
59const 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];
63const 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];
67
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).
75struct VersionParameter(&'static [u8], u8, u8, u8);
76const 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];
118
119const MAX_EC_SIZE: usize = 30;
120const MAX_BLK_SIZE: usize = 123;
121
122/// Position of the alignment pattern grid.
123const 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];
165
166/// Version information for format V7-V40.
167const 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];
203
204/// Format info for low quality ECC.
205const FORMAT_INFOS_QR_L: [u16; 8] = [
206 0x77c4, 0x72f3, 0x7daa, 0x789d, 0x662f, 0x6318, 0x6c41, 0x6976,
207];
208
209impl 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 }
216
217 fn width(&self) -> u8 {
218 (self.0 as u8) * 4 + 17
219 }
220
221 fn max_data(&self) -> usize {
222 self.g1_blk_size() * self.g1_blocks() + (self.g1_blk_size() + 1) * self.g2_blocks()
223 }
224
225 fn ec_size(&self) -> usize {
226 VPARAM[self.0 - 1].0.len()
227 }
228
229 fn g1_blocks(&self) -> usize {
230 VPARAM[self.0 - 1].1 as usize
231 }
232
233 fn g2_blocks(&self) -> usize {
234 VPARAM[self.0 - 1].2 as usize
235 }
236
237 fn g1_blk_size(&self) -> usize {
238 VPARAM[self.0 - 1].3 as usize
239 }
240
241 fn alignment_pattern(&self) -> &'static [u8] {
242 ALIGNMENT_PATTERNS[self.0 - 1]
243 }
244
245 fn poly(&self) -> &'static [u8] {
246 VPARAM[self.0 - 1].0
247 }
248
249 fn version_info(&self) -> u32 {
250 if *self >= Version(7) {
251 VERSION_INFORMATION[self.0 - 7]
252 } else {
253 0
254 }
255 }
256}
257
258/// Exponential table for Galois Field GF(256).
259const 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];
274
275/// Reverse exponential table for Galois Field GF(256).
276const 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];
291
292// 4 bits segment header.
293const MODE_STOP: u16 = 0;
294const MODE_NUMERIC: u16 = 1;
295const MODE_BINARY: u16 = 4;
296/// Padding bytes.
297const PADDING: [u8; 2] = [236, 17];
298
299/// Get the next 13 bits of data, starting at specified offset (in bits).
300fn 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;
307
308 let first_byte = (data[byte_off] << bit_off >> bit_off) as u16;
309
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}
324
325/// Number of bits to encode characters in numeric mode.
326const NUM_CHARS_BITS: [usize; 4] = [0, 4, 7, 10];
327const POW10: [u16; 4] = [1, 10, 100, 1000];
328
329enum Segment<'a> {
330 Numeric(&'a [u8]),
331 Binary(&'a [u8]),
332}
333
334impl 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 }
341
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 }
357
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 }
373
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 }
380
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 }
392
393 fn iter(&self) -> SegmentIterator<'_> {
394 SegmentIterator {
395 segment: self,
396 offset: 0,
397 carry: 0,
398 carry_len: 0,
399 }
400 }
401}
402
403struct SegmentIterator<'a> {
404 segment: &'a Segment<'a>,
405 offset: usize,
406 carry: u16,
407 carry_len: usize,
408}
409
410impl Iterator for SegmentIterator<'_> {
411 type Item = (u16, usize);
412
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}
464
465struct 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}
475
476/// Data to be put in the QR code, with correct segment encoding, padding, and
477/// Error Code Correction.
478impl 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();
487
488 // clear the output.
489 data.fill(0);
490
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 }
504
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;
511
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 }
535
536 fn add_segments(&mut self, segments: &[&Segment<'_>]) {
537 let mut offset: usize = 0;
538
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));
547
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 }
553
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];
556
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 }
571
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;
575
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 }
587
588 fn encode(&mut self, segments: &[&Segment<'_>]) {
589 self.add_segments(segments);
590 self.compute_error_code();
591 }
592
593 fn iter(&self) -> EncodedMsgIterator<'_> {
594 EncodedMsgIterator {
595 em: self,
596 offset: 0,
597 }
598 }
599}
600
601/// Iterator, to retrieve the data in the interleaved order needed by QR code.
602struct EncodedMsgIterator<'a> {
603 em: &'a EncodedMsg<'a>,
604 offset: usize,
605}
606
607impl Iterator for EncodedMsgIterator<'_> {
608 type Item = u8;
609
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;
618
619 if self.offset >= ec_end {
620 return None;
621 }
622
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;
641
642 g2_end + blk * em.ec_size + blk_off
643 };
644 self.offset += 1;
645 Some(em.data[offset])
646 }
647}
648
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.
652struct QrImage<'a> {
653 data: &'a mut [u8],
654 width: u8,
655 stride: u8,
656 version: Version,
657}
658
659impl 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;
664
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 }
674
675 fn clear(&mut self) {
676 self.data.fill(0);
677 }
678
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 }
686
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 }
692
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 }
702
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 }
719
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 }
727
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 }
739
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 }
754
755 // Timing pattern: 2 dotted line between the finder patterns.
756 fn draw_timing_patterns(&mut self) {
757 let end = self.width - 8;
758
759 for x in (9..end).step_by(2) {
760 self.set(x, 6);
761 self.set(6, x);
762 }
763 }
764
765 fn is_timing(&self, x: u8, y: u8) -> bool {
766 x == 6 || y == 6
767 }
768
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;
773
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 }
794
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 }
800
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;
805
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 }
817
818 fn is_version_info(&self, x: u8, y: u8) -> bool {
819 let vinfo = self.version.version_info();
820 let pos = self.width - 11;
821
822 vinfo != 0 && ((x >= pos && x < pos + 3 && y < 6) || (y >= pos && y < pos + 3 && x < 6))
823 }
824
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 }
833
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 }
838
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;
844
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 }
852
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 }
861
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 }
881
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 }
892
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}
906
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.
932#[no_mangle]
933pub unsafe extern "C" fn drm_panic_qr_generate(
934 url: *const kernel::ffi::c_char,
935 data: *mut u8,
936 data_len: usize,
937 data_size: usize,
938 tmp: *mut u8,
939 tmp_size: usize,
940) -> u8 {
941 if data_size < 4071 || tmp_size < 3706 || data_len > data_size {
942 return 0;
943 }
944 // SAFETY: The caller ensures that `data` is a valid pointer for reading and
945 // writing `data_size` bytes.
946 let data_slice: &mut [u8] = unsafe { core::slice::from_raw_parts_mut(data, data_size) };
947 // SAFETY: The caller ensures that `tmp` is a valid pointer for reading and
948 // writing `tmp_size` bytes.
949 let tmp_slice: &mut [u8] = unsafe { core::slice::from_raw_parts_mut(tmp, tmp_size) };
950 if url.is_null() {
951 match EncodedMsg::new(&[&Segment::Binary(&data_slice[0..data_len])], tmp_slice) {
952 None => 0,
953 Some(em) => {
954 let qr_image = QrImage::new(&em, data_slice);
955 qr_image.width
956 }
957 }
958 } else {
959 // SAFETY: The caller ensures that `url` is a valid pointer to a
960 // nul-terminated string.
961 let url_cstr: &CStr = unsafe { CStr::from_char_ptr(url) };
962 let segments = &[
963 &Segment::Binary(url_cstr.as_bytes()),
964 &Segment::Numeric(&data_slice[0..data_len]),
965 ];
966 match EncodedMsg::new(segments, tmp_slice) {
967 None => 0,
968 Some(em) => {
969 let qr_image = QrImage::new(&em, data_slice);
970 qr_image.width
971 }
972 }
973 }
974}
975
976/// Returns the maximum data size that can fit in a QR code of this version.
977/// * `version`: QR code version, between 1-40.
978/// * `url_len`: Length of the URL.
979///
980/// * If `url_len` > 0, remove the 2 segments header/length and also count the
981/// conversion to numeric segments.
982/// * If `url_len` = 0, only removes 3 bytes for 1 binary segment.
983#[no_mangle]
984pub extern "C" fn drm_panic_qr_max_data_size(version: u8, url_len: usize) -> usize {
985 #[expect(clippy::manual_range_contains)]
986 if version < 1 || version > 40 {
987 return 0;
988 }
989 let max_data = Version(version as usize).max_data();
990
991 if url_len > 0 {
992 // Binary segment (URL) 4 + 16 bits, numeric segment (kmsg) 4 + 12 bits => 5 bytes.
993 if url_len + 5 >= max_data {
994 0
995 } else {
996 let max = max_data - url_len - 5;
997 (max * 39) / 40
998 }
999 } else {
1000 // Remove 3 bytes for the binary segment (header 4 bits, length 16 bits, stop 4bits).
1001 max_data - 3
1002 }
1003}