drivers/gpu/drm/drm_panic_qr.rs

   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
  29 use core::cmp;
  30 use kernel::str::CStr;
  31
  32 #[derive(Debug, Clone, Copy, PartialEq, Eq, Ord, PartialOrd)]
  33 struct Version(usize);
  34
  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 ];
  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).
  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 ];
 118
 119 const MAX_EC_SIZE: usize = 30;
 120 const MAX_BLK_SIZE: usize = 123;
 121
 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 ];
 165
 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 ];
 203
 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 ];
 208
 209 impl Version {
 210     /// Returns the smallest QR version than can hold these segments.
 211     fn from_segments(segments: &[&Segment<'_>]) -> Option<Version> {
 212         for v in (1..=40).map(|k| Version(k)) {
 213             if v.max_data() * 8 >= segments.iter().map(|s| s.total_size_bits(v)).sum() {
 214                 return Some(v);
 215             }
 216         }
 217         None
 218     }
 219
 220     fn width(&self) -> u8 {
 221         (self.0 as u8) * 4 + 17
 222     }
 223
 224     fn max_data(&self) -> usize {
 225         self.g1_blk_size() * self.g1_blocks() + (self.g1_blk_size() + 1) * self.g2_blocks()
 226     }
 227
 228     fn ec_size(&self) -> usize {
 229         VPARAM[self.0 - 1].0.len()
 230     }
 231
 232     fn g1_blocks(&self) -> usize {
 233         VPARAM[self.0 - 1].1 as usize
 234     }
 235
 236     fn g2_blocks(&self) -> usize {
 237         VPARAM[self.0 - 1].2 as usize
 238     }
 239
 240     fn g1_blk_size(&self) -> usize {
 241         VPARAM[self.0 - 1].3 as usize
 242     }
 243
 244     fn alignment_pattern(&self) -> &'static [u8] {
 245         &ALIGNMENT_PATTERNS[self.0 - 1]
 246     }
 247
 248     fn poly(&self) -> &'static [u8] {
 249         VPARAM[self.0 - 1].0
 250     }
 251
 252     fn version_info(&self) -> u32 {
 253         if *self >= Version(7) {
 254             VERSION_INFORMATION[self.0 - 7]
 255         } else {
 256             0
 257         }
 258     }
 259 }
 260
 261 /// Exponential table for Galois Field GF(256).
 262 const EXP_TABLE: [u8; 256] = [
 263     1, 2, 4, 8, 16, 32, 64, 128, 29, 58, 116, 232, 205, 135, 19, 38, 76, 152, 45, 90, 180, 117,
 264     234, 201, 143, 3, 6, 12, 24, 48, 96, 192, 157, 39, 78, 156, 37, 74, 148, 53, 106, 212, 181,
 265     119, 238, 193, 159, 35, 70, 140, 5, 10, 20, 40, 80, 160, 93, 186, 105, 210, 185, 111, 222, 161,
 266     95, 190, 97, 194, 153, 47, 94, 188, 101, 202, 137, 15, 30, 60, 120, 240, 253, 231, 211, 187,
 267     107, 214, 177, 127, 254, 225, 223, 163, 91, 182, 113, 226, 217, 175, 67, 134, 17, 34, 68, 136,
 268     13, 26, 52, 104, 208, 189, 103, 206, 129, 31, 62, 124, 248, 237, 199, 147, 59, 118, 236, 197,
 269     151, 51, 102, 204, 133, 23, 46, 92, 184, 109, 218, 169, 79, 158, 33, 66, 132, 21, 42, 84, 168,
 270     77, 154, 41, 82, 164, 85, 170, 73, 146, 57, 114, 228, 213, 183, 115, 230, 209, 191, 99, 198,
 271     145, 63, 126, 252, 229, 215, 179, 123, 246, 241, 255, 227, 219, 171, 75, 150, 49, 98, 196, 149,
 272     55, 110, 220, 165, 87, 174, 65, 130, 25, 50, 100, 200, 141, 7, 14, 28, 56, 112, 224, 221, 167,
 273     83, 166, 81, 162, 89, 178, 121, 242, 249, 239, 195, 155, 43, 86, 172, 69, 138, 9, 18, 36, 72,
 274     144, 61, 122, 244, 245, 247, 243, 251, 235, 203, 139, 11, 22, 44, 88, 176, 125, 250, 233, 207,
 275     131, 27, 54, 108, 216, 173, 71, 142, 1,
 276 ];
 277
 278 /// Reverse exponential table for Galois Field GF(256).
 279 const LOG_TABLE: [u8; 256] = [
 280     175, 0, 1, 25, 2, 50, 26, 198, 3, 223, 51, 238, 27, 104, 199, 75, 4, 100, 224, 14, 52, 141,
 281     239, 129, 28, 193, 105, 248, 200, 8, 76, 113, 5, 138, 101, 47, 225, 36, 15, 33, 53, 147, 142,
 282     218, 240, 18, 130, 69, 29, 181, 194, 125, 106, 39, 249, 185, 201, 154, 9, 120, 77, 228, 114,
 283     166, 6, 191, 139, 98, 102, 221, 48, 253, 226, 152, 37, 179, 16, 145, 34, 136, 54, 208, 148,
 284     206, 143, 150, 219, 189, 241, 210, 19, 92, 131, 56, 70, 64, 30, 66, 182, 163, 195, 72, 126,
 285     110, 107, 58, 40, 84, 250, 133, 186, 61, 202, 94, 155, 159, 10, 21, 121, 43, 78, 212, 229, 172,
 286     115, 243, 167, 87, 7, 112, 192, 247, 140, 128, 99, 13, 103, 74, 222, 237, 49, 197, 254, 24,
 287     227, 165, 153, 119, 38, 184, 180, 124, 17, 68, 146, 217, 35, 32, 137, 46, 55, 63, 209, 91, 149,
 288     188, 207, 205, 144, 135, 151, 178, 220, 252, 190, 97, 242, 86, 211, 171, 20, 42, 93, 158, 132,
 289     60, 57, 83, 71, 109, 65, 162, 31, 45, 67, 216, 183, 123, 164, 118, 196, 23, 73, 236, 127, 12,
 290     111, 246, 108, 161, 59, 82, 41, 157, 85, 170, 251, 96, 134, 177, 187, 204, 62, 90, 203, 89, 95,
 291     176, 156, 169, 160, 81, 11, 245, 22, 235, 122, 117, 44, 215, 79, 174, 213, 233, 230, 231, 173,
 292     232, 116, 214, 244, 234, 168, 80, 88, 175,
 293 ];
 294
 295 // 4 bits segment header.
 296 const MODE_STOP: u16 = 0;
 297 const MODE_NUMERIC: u16 = 1;
 298 const MODE_BINARY: u16 = 4;
 299 /// Padding bytes.
 300 const PADDING: [u8; 2] = [236, 17];
 301
 302 /// Get the next 13 bits of data, starting at specified offset (in bits).
 303 fn get_next_13b(data: &[u8], offset: usize) -> Option<(u16, usize)> {
 304     if offset < data.len() * 8 {
 305         let size = cmp::min(13, data.len() * 8 - offset);
 306         let byte_off = offset / 8;
 307         let bit_off = offset % 8;
 308         // `b` is 20 at max (`bit_off` <= 7 and `size` <= 13).
 309         let b = (bit_off + size) as u16;
 310
 311         let first_byte = (data[byte_off] << bit_off >> bit_off) as u16;
 312
 313         let number = match b {
 314             0..=8 => first_byte >> (8 - b),
 315             9..=16 => (first_byte << (b - 8)) + (data[byte_off + 1] >> (16 - b)) as u16,
 316             _ => {
 317                 (first_byte << (b - 8))
 318                     + ((data[byte_off + 1] as u16) << (b - 16))
 319                     + (data[byte_off + 2] >> (24 - b)) as u16
 320             }
 321         };
 322         Some((number, size))
 323     } else {
 324         None
 325     }
 326 }
 327
 328 /// Number of bits to encode characters in numeric mode.
 329 const NUM_CHARS_BITS: [usize; 4] = [0, 4, 7, 10];
 330 const POW10: [u16; 4] = [1, 10, 100, 1000];
 331
 332 enum Segment<'a> {
 333     Numeric(&'a [u8]),
 334     Binary(&'a [u8]),
 335 }
 336
 337 impl Segment<'_> {
 338     fn get_header(&self) -> (u16, usize) {
 339         match self {
 340             Segment::Binary(_) => (MODE_BINARY, 4),
 341             Segment::Numeric(_) => (MODE_NUMERIC, 4),
 342         }
 343     }
 344
 345     // Returns the size of the length field in bits, depending on QR Version.
 346     fn length_bits_count(&self, version: Version) -> usize {
 347         let Version(v) = version;
 348         match self {
 349             Segment::Binary(_) => match v {
 350                 1..=9 => 8,
 351                 _ => 16,
 352             },
 353             Segment::Numeric(_) => match v {
 354                 1..=9 => 10,
 355                 10..=26 => 12,
 356                 _ => 14,
 357             },
 358         }
 359     }
 360
 361     // Number of characters in the segment.
 362     fn character_count(&self) -> usize {
 363         match self {
 364             Segment::Binary(data) => data.len(),
 365             Segment::Numeric(data) => {
 366                 let data_bits = data.len() * 8;
 367                 let last_chars = match data_bits % 13 {
 368                     1 => 1,
 369                     k => (k + 1) / 3,
 370                 };
 371                 // 4 decimal numbers per 13bits + remainder.
 372                 4 * (data_bits / 13) + last_chars
 373             }
 374         }
 375     }
 376
 377     fn get_length_field(&self, version: Version) -> (u16, usize) {
 378         (
 379             self.character_count() as u16,
 380             self.length_bits_count(version),
 381         )
 382     }
 383
 384     fn total_size_bits(&self, version: Version) -> usize {
 385         let data_size = match self {
 386             Segment::Binary(data) => data.len() * 8,
 387             Segment::Numeric(_) => {
 388                 let digits = self.character_count();
 389                 10 * (digits / 3) + NUM_CHARS_BITS[digits % 3]
 390             }
 391         };
 392         // header + length + data.
 393         4 + self.length_bits_count(version) + data_size
 394     }
 395
 396     fn iter(&self) -> SegmentIterator<'_> {
 397         SegmentIterator {
 398             segment: self,
 399             offset: 0,
 400             carry: 0,
 401             carry_len: 0,
 402         }
 403     }
 404 }
 405
 406 struct SegmentIterator<'a> {
 407     segment: &'a Segment<'a>,
 408     offset: usize,
 409     carry: u16,
 410     carry_len: usize,
 411 }
 412
 413 impl Iterator for SegmentIterator<'_> {
 414     type Item = (u16, usize);
 415
 416     fn next(&mut self) -> Option<Self::Item> {
 417         match self.segment {
 418             Segment::Binary(data) => {
 419                 if self.offset < data.len() {
 420                     let byte = data[self.offset] as u16;
 421                     self.offset += 1;
 422                     Some((byte, 8))
 423                 } else {
 424                     None
 425                 }
 426             }
 427             Segment::Numeric(data) => {
 428                 if self.carry_len == 3 {
 429                     let out = (self.carry, NUM_CHARS_BITS[self.carry_len]);
 430                     self.carry_len = 0;
 431                     self.carry = 0;
 432                     Some(out)
 433                 } else if let Some((bits, size)) = get_next_13b(data, self.offset) {
 434                     self.offset += size;
 435                     let new_chars = match size {
 436                         1 => 1,
 437                         k => (k + 1) / 3,
 438                     };
 439                     if self.carry_len + new_chars > 3 {
 440                         self.carry_len = new_chars + self.carry_len - 3;
 441                         let out = (
 442                             self.carry * POW10[new_chars - self.carry_len]
 443                                 + bits / POW10[self.carry_len],
 444                             NUM_CHARS_BITS[3],
 445                         );
 446                         self.carry = bits % POW10[self.carry_len];
 447                         Some(out)
 448                     } else {
 449                         let out = (
 450                             self.carry * POW10[new_chars] + bits,
 451                             NUM_CHARS_BITS[self.carry_len + new_chars],
 452                         );
 453                         self.carry_len = 0;
 454                         Some(out)
 455                     }
 456                 } else if self.carry_len > 0 {
 457                     let out = (self.carry, NUM_CHARS_BITS[self.carry_len]);
 458                     self.carry_len = 0;
 459                     Some(out)
 460                 } else {
 461                     None
 462                 }
 463             }
 464         }
 465     }
 466 }
 467
 468 struct EncodedMsg<'a> {
 469     data: &'a mut [u8],
 470     ec_size: usize,
 471     g1_blocks: usize,
 472     g2_blocks: usize,
 473     g1_blk_size: usize,
 474     g2_blk_size: usize,
 475     poly: &'static [u8],
 476     version: Version,
 477 }
 478
 479 /// Data to be put in the QR code, with correct segment encoding, padding, and
 480 /// Error Code Correction.
 481 impl EncodedMsg<'_> {
 482     fn new<'a, 'b>(segments: &[&Segment<'b>], data: &'a mut [u8]) -> Option<EncodedMsg<'a>> {
 483         let version = Version::from_segments(segments)?;
 484         let ec_size = version.ec_size();
 485         let g1_blocks = version.g1_blocks();
 486         let g2_blocks = version.g2_blocks();
 487         let g1_blk_size = version.g1_blk_size();
 488         let g2_blk_size = g1_blk_size + 1;
 489         let poly = version.poly();
 490
 491         // clear the output.
 492         data.fill(0);
 493
 494         let mut em = EncodedMsg {
 495             data: data,
 496             ec_size,
 497             g1_blocks,
 498             g2_blocks,
 499             g1_blk_size,
 500             g2_blk_size,
 501             poly,
 502             version,
 503         };
 504         em.encode(segments);
 505         Some(em)
 506     }
 507
 508     /// Push bits of data at an offset (in bits).
 509     fn push(&mut self, offset: &mut usize, bits: (u16, usize)) {
 510         let (number, len_bits) = bits;
 511         let byte_off = *offset / 8;
 512         let bit_off = *offset % 8;
 513         let b = bit_off + len_bits;
 514
 515         match (bit_off, b) {
 516             (0, 0..=8) => {
 517                 self.data[byte_off] = (number << (8 - b)) as u8;
 518             }
 519             (0, _) => {
 520                 self.data[byte_off] = (number >> (b - 8)) as u8;
 521                 self.data[byte_off + 1] = (number << (16 - b)) as u8;
 522             }
 523             (_, 0..=8) => {
 524                 self.data[byte_off] |= (number << (8 - b)) as u8;
 525             }
 526             (_, 9..=16) => {
 527                 self.data[byte_off] |= (number >> (b - 8)) as u8;
 528                 self.data[byte_off + 1] = (number << (16 - b)) as u8;
 529             }
 530             _ => {
 531                 self.data[byte_off] |= (number >> (b - 8)) as u8;
 532                 self.data[byte_off + 1] = (number >> (b - 16)) as u8;
 533                 self.data[byte_off + 2] = (number << (24 - b)) as u8;
 534             }
 535         }
 536         *offset += len_bits;
 537     }
 538
 539     fn add_segments(&mut self, segments: &[&Segment<'_>]) {
 540         let mut offset: usize = 0;
 541
 542         for s in segments.iter() {
 543             self.push(&mut offset, s.get_header());
 544             self.push(&mut offset, s.get_length_field(self.version));
 545             for bits in s.iter() {
 546                 self.push(&mut offset, bits);
 547             }
 548         }
 549         self.push(&mut offset, (MODE_STOP, 4));
 550
 551         let pad_offset = (offset + 7) / 8;
 552         for i in pad_offset..self.version.max_data() {
 553             self.data[i] = PADDING[(i & 1) ^ (pad_offset & 1)];
 554         }
 555     }
 556
 557     fn error_code_for_blocks(&mut self, offset: usize, size: usize, ec_offset: usize) {
 558         let mut tmp: [u8; MAX_BLK_SIZE + MAX_EC_SIZE] = [0; MAX_BLK_SIZE + MAX_EC_SIZE];
 559
 560         tmp[0..size].copy_from_slice(&self.data[offset..offset + size]);
 561         for i in 0..size {
 562             let lead_coeff = tmp[i] as usize;
 563             if lead_coeff == 0 {
 564                 continue;
 565             }
 566             let log_lead_coeff = usize::from(LOG_TABLE[lead_coeff]);
 567             for (u, &v) in tmp[i + 1..].iter_mut().zip(self.poly.iter()) {
 568                 *u ^= EXP_TABLE[(usize::from(v) + log_lead_coeff) % 255];
 569             }
 570         }
 571         self.data[ec_offset..ec_offset + self.ec_size]
 572             .copy_from_slice(&tmp[size..size + self.ec_size]);
 573     }
 574
 575     fn compute_error_code(&mut self) {
 576         let mut offset = 0;
 577         let mut ec_offset = self.g1_blocks * self.g1_blk_size + self.g2_blocks * self.g2_blk_size;
 578
 579         for _ in 0..self.g1_blocks {
 580             self.error_code_for_blocks(offset, self.g1_blk_size, ec_offset);
 581             offset += self.g1_blk_size;
 582             ec_offset += self.ec_size;
 583         }
 584         for _ in 0..self.g2_blocks {
 585             self.error_code_for_blocks(offset, self.g2_blk_size, ec_offset);
 586             offset += self.g2_blk_size;
 587             ec_offset += self.ec_size;
 588         }
 589     }
 590
 591     fn encode(&mut self, segments: &[&Segment<'_>]) {
 592         self.add_segments(segments);
 593         self.compute_error_code();
 594     }
 595
 596     fn iter(&self) -> EncodedMsgIterator<'_> {
 597         EncodedMsgIterator {
 598             em: self,
 599             offset: 0,
 600         }
 601     }
 602 }
 603
 604 /// Iterator, to retrieve the data in the interleaved order needed by QR code.
 605 struct EncodedMsgIterator<'a> {
 606     em: &'a EncodedMsg<'a>,
 607     offset: usize,
 608 }
 609
 610 impl Iterator for EncodedMsgIterator<'_> {
 611     type Item = u8;
 612
 613     // Send the bytes in interleaved mode, first byte of first block of group1,
 614     // then first byte of second block of group1, ...
 615     fn next(&mut self) -> Option<Self::Item> {
 616         let em = self.em;
 617         let blocks = em.g1_blocks + em.g2_blocks;
 618         let g1_end = em.g1_blocks * em.g1_blk_size;
 619         let g2_end = g1_end + em.g2_blocks * em.g2_blk_size;
 620         let ec_end = g2_end + em.ec_size * blocks;
 621
 622         if self.offset >= ec_end {
 623             return None;
 624         }
 625
 626         let offset = if self.offset < em.g1_blk_size * blocks {
 627             // group1 and group2 interleaved
 628             let blk = self.offset % blocks;
 629             let blk_off = self.offset / blocks;
 630             if blk < em.g1_blocks {
 631                 blk * em.g1_blk_size + blk_off
 632             } else {
 633                 g1_end + em.g2_blk_size * (blk - em.g1_blocks) + blk_off
 634             }
 635         } else if self.offset < g2_end {
 636             // last byte of group2 blocks
 637             let blk2 = self.offset - blocks * em.g1_blk_size;
 638             em.g1_blk_size * em.g1_blocks + blk2 * em.g2_blk_size + em.g2_blk_size - 1
 639         } else {
 640             // EC blocks
 641             let ec_offset = self.offset - g2_end;
 642             let blk = ec_offset % blocks;
 643             let blk_off = ec_offset / blocks;
 644
 645             g2_end + blk * em.ec_size + blk_off
 646         };
 647         self.offset += 1;
 648         Some(em.data[offset])
 649     }
 650 }
 651
 652 /// A QR code image, encoded as a linear binary framebuffer.
 653 /// 1 bit per module (pixel), each new line start at next byte boundary.
 654 /// Max width is 177 for V40 QR code, so `u8` is enough for coordinate.
 655 struct QrImage<'a> {
 656     data: &'a mut [u8],
 657     width: u8,
 658     stride: u8,
 659     version: Version,
 660 }
 661
 662 impl QrImage<'_> {
 663     fn new<'a, 'b>(em: &'b EncodedMsg<'b>, qrdata: &'a mut [u8]) -> QrImage<'a> {
 664         let width = em.version.width();
 665         let stride = (width + 7) / 8;
 666         let data = qrdata;
 667
 668         let mut qr_image = QrImage {
 669             data,
 670             width,
 671             stride,
 672             version: em.version,
 673         };
 674         qr_image.draw_all(em.iter());
 675         qr_image
 676     }
 677
 678     fn clear(&mut self) {
 679         self.data.fill(0);
 680     }
 681
 682     // Set pixel to light color.
 683     fn set(&mut self, x: u8, y: u8) {
 684         let off = y as usize * self.stride as usize + x as usize / 8;
 685         let mut v = self.data[off];
 686         v |= 0x80 >> (x % 8);
 687         self.data[off] = v;
 688     }
 689
 690     // Invert a module color.
 691     fn xor(&mut self, x: u8, y: u8) {
 692         let off = y as usize * self.stride as usize + x as usize / 8;
 693         self.data[off] ^= 0x80 >> (x % 8);
 694     }
 695
 696     // Draw a light square at (x, y) top left corner.
 697     fn draw_square(&mut self, x: u8, y: u8, size: u8) {
 698         for k in 0..size {
 699             self.set(x + k, y);
 700             self.set(x, y + k + 1);
 701             self.set(x + size, y + k);
 702             self.set(x + k + 1, y + size);
 703         }
 704     }
 705
 706     // Finder pattern: 3 8x8 square at the corners.
 707     fn draw_finders(&mut self) {
 708         self.draw_square(1, 1, 4);
 709         self.draw_square(self.width - 6, 1, 4);
 710         self.draw_square(1, self.width - 6, 4);
 711         for k in 0..8 {
 712             self.set(k, 7);
 713             self.set(self.width - k - 1, 7);
 714             self.set(k, self.width - 8);
 715         }
 716         for k in 0..7 {
 717             self.set(7, k);
 718             self.set(self.width - 8, k);
 719             self.set(7, self.width - 1 - k);
 720         }
 721     }
 722
 723     fn is_finder(&self, x: u8, y: u8) -> bool {
 724         let end = self.width - 8;
 725         (x < 8 && y < 8) || (x < 8 && y >= end) || (x >= end && y < 8)
 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
 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 }
 976
 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     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 }