diff options
Diffstat (limited to 'drivers/gpu/drm/drm_panic_qr.rs')
| -rw-r--r-- | drivers/gpu/drm/drm_panic_qr.rs | 201 |
1 files changed, 97 insertions, 104 deletions
diff --git a/drivers/gpu/drm/drm_panic_qr.rs b/drivers/gpu/drm/drm_panic_qr.rs index bcf248f69252..dd55b1cb764d 100644 --- a/drivers/gpu/drm/drm_panic_qr.rs +++ b/drivers/gpu/drm/drm_panic_qr.rs @@ -5,7 +5,7 @@ //! It is called from a panic handler, so it should't allocate memory and //! does all the work on the stack or on the provided buffers. For //! simplification, it only supports low error correction, and applies the -//! first mask (checkerboard). It will draw the smallest QRcode that can +//! first mask (checkerboard). It will draw the smallest QR code that can //! contain the string passed as parameter. To get the most compact //! QR code, the start of the URL is encoded as binary, and the //! compressed kmsg is encoded as numeric. @@ -13,12 +13,13 @@ //! The binary data must be a valid URL parameter, so the easiest way is //! to use base64 encoding. But this wastes 25% of data space, so the //! whole stack trace won't fit in the QR code. So instead it encodes -//! every 13bits of input into 4 decimal digits, and then uses the +//! every 7 bytes of input into 17 decimal digits, and then uses the //! efficient numeric encoding, that encode 3 decimal digits into -//! 10bits. This makes 39bits of compressed data into 12 decimal digits, -//! into 40bits in the QR code, so wasting only 2.5%. And the numbers are +//! 10bits. This makes 168bits of compressed data into 51 decimal digits, +//! into 170bits in the QR code, so wasting only 1.17%. And the numbers are //! valid URL parameter, so the website can do the reverse, to get the -//! binary data. +//! binary data. This is the same algorithm used by Fido v2.2 QR-initiated +//! authentication specification. //! //! Inspired by these 3 projects, all under MIT license: //! @@ -26,8 +27,7 @@ //! * <https://github.com/erwanvivien/fast_qr> //! * <https://github.com/bjguillot/qr> -use core::cmp; -use kernel::str::CStr; +use kernel::{prelude::*, str::CStr}; #[derive(Debug, Clone, Copy, PartialEq, Eq, Ord, PartialOrd)] struct Version(usize); @@ -296,35 +296,11 @@ const MODE_BINARY: u16 = 4; /// Padding bytes. const PADDING: [u8; 2] = [236, 17]; -/// Get the next 13 bits of data, starting at specified offset (in bits). -fn get_next_13b(data: &[u8], offset: usize) -> Option<(u16, usize)> { - if offset < data.len() * 8 { - let size = cmp::min(13, data.len() * 8 - offset); - let byte_off = offset / 8; - let bit_off = offset % 8; - // `b` is 20 at max (`bit_off` <= 7 and `size` <= 13). - let b = (bit_off + size) as u16; - - let first_byte = (data[byte_off] << bit_off >> bit_off) as u16; - - let number = match b { - 0..=8 => first_byte >> (8 - b), - 9..=16 => (first_byte << (b - 8)) + (data[byte_off + 1] >> (16 - b)) as u16, - _ => { - (first_byte << (b - 8)) - + ((data[byte_off + 1] as u16) << (b - 16)) - + (data[byte_off + 2] >> (24 - b)) as u16 - } - }; - Some((number, size)) - } else { - None - } -} - /// Number of bits to encode characters in numeric mode. const NUM_CHARS_BITS: [usize; 4] = [0, 4, 7, 10]; -const POW10: [u16; 4] = [1, 10, 100, 1000]; +/// Number of decimal digits required to encode n bytes of binary data. +/// eg: you need 15 decimal digits to fit 6 bytes of binary data. +const BYTES_TO_DIGITS: [usize; 8] = [0, 3, 5, 8, 10, 13, 15, 17]; enum Segment<'a> { Numeric(&'a [u8]), @@ -339,7 +315,7 @@ impl Segment<'_> { } } - // Returns the size of the length field in bits, depending on QR Version. + /// Returns the size of the length field in bits, depending on QR Version. fn length_bits_count(&self, version: Version) -> usize { let Version(v) = version; match self { @@ -355,18 +331,14 @@ impl Segment<'_> { } } - // Number of characters in the segment. + /// Number of characters in the segment. fn character_count(&self) -> usize { match self { Segment::Binary(data) => data.len(), Segment::Numeric(data) => { - let data_bits = data.len() * 8; - let last_chars = match data_bits % 13 { - 1 => 1, - k => (k + 1) / 3, - }; - // 4 decimal numbers per 13bits + remainder. - 4 * (data_bits / 13) + last_chars + let last_chars = BYTES_TO_DIGITS[data.len() % 7]; + // 17 decimal numbers per 7bytes + remainder. + 17 * (data.len() / 7) + last_chars } } } @@ -394,8 +366,48 @@ impl Segment<'_> { SegmentIterator { segment: self, offset: 0, - carry: 0, - carry_len: 0, + decfifo: Default::default(), + } + } +} + +/// Max fifo size is 17 (max push) + 2 (max remaining) +const MAX_FIFO_SIZE: usize = 19; + +/// A simple Decimal digit FIFO +#[derive(Default)] +struct DecFifo { + decimals: [u8; MAX_FIFO_SIZE], + len: usize, +} + +impl DecFifo { + fn push(&mut self, data: u64, len: usize) { + let mut chunk = data; + for i in (0..self.len).rev() { + self.decimals[i + len] = self.decimals[i]; + } + for i in 0..len { + self.decimals[i] = (chunk % 10) as u8; + chunk /= 10; + } + self.len += len; + } + + /// Pop 3 decimal digits from the FIFO + fn pop3(&mut self) -> Option<(u16, usize)> { + if self.len == 0 { + None + } else { + let poplen = 3.min(self.len); + self.len -= poplen; + let mut out = 0; + let mut exp = 1; + for i in 0..poplen { + out += self.decimals[self.len + i] as u16 * exp; + exp *= 10; + } + Some((out, NUM_CHARS_BITS[poplen])) } } } @@ -403,8 +415,7 @@ impl Segment<'_> { struct SegmentIterator<'a> { segment: &'a Segment<'a>, offset: usize, - carry: u16, - carry_len: usize, + decfifo: DecFifo, } impl Iterator for SegmentIterator<'_> { @@ -422,41 +433,17 @@ impl Iterator for SegmentIterator<'_> { } } Segment::Numeric(data) => { - if self.carry_len == 3 { - let out = (self.carry, NUM_CHARS_BITS[self.carry_len]); - self.carry_len = 0; - self.carry = 0; - Some(out) - } else if let Some((bits, size)) = get_next_13b(data, self.offset) { - self.offset += size; - let new_chars = match size { - 1 => 1, - k => (k + 1) / 3, - }; - if self.carry_len + new_chars > 3 { - self.carry_len = new_chars + self.carry_len - 3; - let out = ( - self.carry * POW10[new_chars - self.carry_len] - + bits / POW10[self.carry_len], - NUM_CHARS_BITS[3], - ); - self.carry = bits % POW10[self.carry_len]; - Some(out) - } else { - let out = ( - self.carry * POW10[new_chars] + bits, - NUM_CHARS_BITS[self.carry_len + new_chars], - ); - self.carry_len = 0; - Some(out) - } - } else if self.carry_len > 0 { - let out = (self.carry, NUM_CHARS_BITS[self.carry_len]); - self.carry_len = 0; - Some(out) - } else { - None + if self.decfifo.len < 3 && self.offset < data.len() { + // If there are less than 3 decimal digits in the fifo, + // take the next 7 bytes of input, and push them to the fifo. + let mut buf = [0u8; 8]; + let len = 7.min(data.len() - self.offset); + buf[..len].copy_from_slice(&data[self.offset..self.offset + len]); + let chunk = u64::from_le_bytes(buf); + self.decfifo.push(chunk, BYTES_TO_DIGITS[len]); + self.offset += len; } + self.decfifo.pop3() } } } @@ -545,7 +532,7 @@ impl EncodedMsg<'_> { } self.push(&mut offset, (MODE_STOP, 4)); - let pad_offset = (offset + 7) / 8; + let pad_offset = offset.div_ceil(8); for i in pad_offset..self.version.max_data() { self.data[i] = PADDING[(i & 1) ^ (pad_offset & 1)]; } @@ -607,8 +594,8 @@ struct EncodedMsgIterator<'a> { impl Iterator for EncodedMsgIterator<'_> { type Item = u8; - // Send the bytes in interleaved mode, first byte of first block of group1, - // then first byte of second block of group1, ... + /// Send the bytes in interleaved mode, first byte of first block of group1, + /// then first byte of second block of group1, ... fn next(&mut self) -> Option<Self::Item> { let em = self.em; let blocks = em.g1_blocks + em.g2_blocks; @@ -659,7 +646,7 @@ struct QrImage<'a> { impl QrImage<'_> { fn new<'a, 'b>(em: &'b EncodedMsg<'b>, qrdata: &'a mut [u8]) -> QrImage<'a> { let width = em.version.width(); - let stride = (width + 7) / 8; + let stride = width.div_ceil(8); let data = qrdata; let mut qr_image = QrImage { @@ -676,7 +663,7 @@ impl QrImage<'_> { self.data.fill(0); } - // Set pixel to light color. + /// Set pixel to light color. fn set(&mut self, x: u8, y: u8) { let off = y as usize * self.stride as usize + x as usize / 8; let mut v = self.data[off]; @@ -684,13 +671,13 @@ impl QrImage<'_> { self.data[off] = v; } - // Invert a module color. + /// Invert a module color. fn xor(&mut self, x: u8, y: u8) { let off = y as usize * self.stride as usize + x as usize / 8; self.data[off] ^= 0x80 >> (x % 8); } - // Draw a light square at (x, y) top left corner. + /// Draw a light square at (x, y) top left corner. fn draw_square(&mut self, x: u8, y: u8, size: u8) { for k in 0..size { self.set(x + k, y); @@ -822,7 +809,7 @@ impl QrImage<'_> { vinfo != 0 && ((x >= pos && x < pos + 3 && y < 6) || (y >= pos && y < pos + 3 && x < 6)) } - // Returns true if the module is reserved (Not usable for data and EC). + /// Returns true if the module is reserved (Not usable for data and EC). fn is_reserved(&self, x: u8, y: u8) -> bool { self.is_alignment(x, y) || self.is_finder(x, y) @@ -831,13 +818,14 @@ impl QrImage<'_> { || self.is_version_info(x, y) } - // Last module to draw, at bottom left corner. + /// Last module to draw, at bottom left corner. fn is_last(&self, x: u8, y: u8) -> bool { x == 0 && y == self.width - 1 } - // Move to the next module according to QR code order. - // From bottom right corner, to bottom left corner. + /// Move to the next module according to QR code order. + /// + /// From bottom right corner, to bottom left corner. fn next(&self, x: u8, y: u8) -> (u8, u8) { let x_adj = if x <= 6 { x + 1 } else { x }; let column_type = (self.width - x_adj) % 4; @@ -850,7 +838,7 @@ impl QrImage<'_> { } } - // Find next module that can hold data. + /// Find next module that can hold data. fn next_available(&self, x: u8, y: u8) -> (u8, u8) { let (mut x, mut y) = self.next(x, y); while self.is_reserved(x, y) && !self.is_last(x, y) { @@ -879,7 +867,7 @@ impl QrImage<'_> { } } - // Apply checkerboard mask to all non-reserved modules. + /// Apply checkerboard mask to all non-reserved modules. fn apply_mask(&mut self) { for x in 0..self.width { for y in 0..self.width { @@ -890,7 +878,7 @@ impl QrImage<'_> { } } - // Draw the QR code with the provided data iterator. + /// Draw the QR code with the provided data iterator. fn draw_all(&mut self, data: impl Iterator<Item = u8>) { // First clear the table, as it may have already some data. self.clear(); @@ -911,16 +899,16 @@ impl QrImage<'_> { /// /// * `url`: The base URL of the QR code. It will be encoded as Binary segment. /// * `data`: A pointer to the binary data, to be encoded. if URL is NULL, it -/// will be encoded as binary segment, otherwise it will be encoded -/// efficiently as a numeric segment, and appended to the URL. +/// will be encoded as binary segment, otherwise it will be encoded +/// efficiently as a numeric segment, and appended to the URL. /// * `data_len`: Length of the data, that needs to be encoded, must be less -/// than data_size. +/// than `data_size`. /// * `data_size`: Size of data buffer, it should be at least 4071 bytes to hold -/// a V40 QR code. It will then be overwritten with the QR code image. +/// a V40 QR code. It will then be overwritten with the QR code image. /// * `tmp`: A temporary buffer that the QR code encoder will use, to write the -/// segments and ECC. +/// segments and ECC. /// * `tmp_size`: Size of the temporary buffer, it must be at least 3706 bytes -/// long for V40. +/// long for V40. /// /// # Safety /// @@ -929,7 +917,7 @@ impl QrImage<'_> { /// * `tmp` must be valid for reading and writing for `tmp_size` bytes. /// /// They must remain valid for the duration of the function call. -#[no_mangle] +#[export] pub unsafe extern "C" fn drm_panic_qr_generate( url: *const kernel::ffi::c_char, data: *mut u8, @@ -980,8 +968,13 @@ pub unsafe extern "C" fn drm_panic_qr_generate( /// * If `url_len` > 0, remove the 2 segments header/length and also count the /// conversion to numeric segments. /// * If `url_len` = 0, only removes 3 bytes for 1 binary segment. -#[no_mangle] -pub extern "C" fn drm_panic_qr_max_data_size(version: u8, url_len: usize) -> usize { +/// +/// # Safety +/// +/// Always safe to call. +// Required to be unsafe due to the `#[export]` annotation. +#[export] +pub unsafe extern "C" fn drm_panic_qr_max_data_size(version: u8, url_len: usize) -> usize { #[expect(clippy::manual_range_contains)] if version < 1 || version > 40 { return 0; |