use std::fmt;
use zeroize::Zeroizing;
const ALPHABET: &[u8; 32] = b"0123456789ABCDEFGHJKMNPQRSTVWXYZ";
pub const ROW_DATA: usize = 28;
pub const ROW_PARITY: usize = 4;
pub const ROW_LEN: usize = ROW_DATA + ROW_PARITY;
const MAX_ERASURES: usize = 2;
const POLY: u8 = 0b10_0101;
const fn gf_mul(a: u8, b: u8) -> u8 {
let mut a = a & 31;
let mut b = b & 31;
let mut product = 0u8;
while b != 0 {
if b & 1 == 1 {
product ^= a;
}
b >>= 1;
a <<= 1;
if a & 0b10_0000 != 0 {
a ^= POLY;
}
}
product & 31
}
#[allow(clippy::indexing_slicing)] const INVERSES: [u8; 32] = {
let mut table = [0u8; 32];
let mut a = 1u8;
while a < 32 {
let mut x = 1u8;
while x < 32 {
if gf_mul(a, x) == 1 {
table[a as usize] = x;
}
x += 1;
}
a += 1;
}
table
};
fn gf_inv(a: u8) -> u8 {
INVERSES.get(usize::from(a & 31)).copied().unwrap_or(0)
}
fn interpolate(points: &[(u8, u8)], x: u8) -> u8 {
let mut result = 0u8;
for (i, &(xi, yi)) in points.iter().enumerate() {
let mut basis = 1u8;
for (j, &(xj, _)) in points.iter().enumerate() {
if i != j {
basis = gf_mul(basis, gf_mul(x ^ xj, gf_inv(xi ^ xj)));
}
}
result ^= gf_mul(yi, basis);
}
result
}
fn point(position: usize) -> u8 {
u8::try_from(position & 31).unwrap_or(0)
}
fn parity(data: &[u8]) -> [u8; ROW_PARITY] {
let points: Vec<(u8, u8)> = data
.iter()
.enumerate()
.map(|(i, &d)| (point(i), d))
.collect();
let mut out = [0u8; ROW_PARITY];
for (k, slot) in out.iter_mut().enumerate() {
*slot = interpolate(&points, point(ROW_DATA.saturating_add(k)));
}
out
}
fn to_symbols(bytes: &[u8]) -> Vec<u8> {
let mut out = Vec::with_capacity(bytes.len().saturating_mul(8).div_ceil(5));
let mut acc: u32 = 0;
let mut bits: u32 = 0;
for &b in bytes {
acc = (acc << 8) | u32::from(b);
bits = bits.saturating_add(8);
while bits >= 5 {
bits = bits.saturating_sub(5);
out.push(u8::try_from((acc >> bits) & 31).unwrap_or(0));
}
}
if bits > 0 {
out.push(u8::try_from((acc << (5u32.saturating_sub(bits))) & 31).unwrap_or(0));
}
out
}
fn from_symbols(symbols: &[u8]) -> Option<Vec<u8>> {
let mut out = Vec::with_capacity(symbols.len().saturating_mul(5) / 8);
let mut acc: u32 = 0;
let mut bits: u32 = 0;
for &s in symbols {
acc = (acc << 5) | u32::from(s & 31);
bits = bits.saturating_add(5);
while bits >= 8 {
bits = bits.saturating_sub(8);
out.push(u8::try_from((acc >> bits) & 0xff).unwrap_or(0));
}
}
if bits >= 5 || (acc << (8u32.saturating_sub(bits))) & 0xff != 0 {
return None;
}
Some(out)
}
pub fn encode(bytes: &[u8]) -> String {
let symbols = Zeroizing::new(to_symbols(bytes));
let mut out = String::with_capacity(symbols.len().saturating_add(ROW_LEN).saturating_mul(2));
for data in symbols.chunks(ROW_DATA) {
for &s in data {
out.push(letter(s));
}
for p in parity(data) {
out.push(letter(p));
}
}
out
}
fn letter(symbol: u8) -> char {
ALPHABET
.get(usize::from(symbol & 31))
.map_or('0', |&b| char::from(b))
}
enum Read {
Separator,
Erasure,
Value(u8),
Unknown,
}
fn read(c: char) -> Read {
let c = c.to_ascii_uppercase();
match c {
' ' | '-' | '|' | '\t' | '\n' | '\r' | '.' => Read::Separator,
'?' | 'U' => Read::Erasure,
'O' => Read::Value(0),
'I' | 'L' => Read::Value(1),
_ => ALPHABET
.iter()
.position(|&x| char::from(x) == c)
.and_then(|p| u8::try_from(p).ok())
.map_or(Read::Unknown, Read::Value),
}
}
pub fn decode(text: &str) -> Result<Decoded, RowError> {
let mut symbols: Vec<Option<u8>> = Vec::with_capacity(text.len());
for (position, c) in text.chars().enumerate() {
match read(c) {
Read::Separator => {}
Read::Erasure => symbols.push(None),
Read::Value(v) => symbols.push(Some(v)),
Read::Unknown => return Err(RowError::Character { position }),
}
}
if symbols.is_empty() {
return Err(RowError::Empty);
}
let tail = symbols.len() % ROW_LEN;
if tail != 0 && tail <= ROW_PARITY {
return Err(RowError::Shape {
characters: symbols.len(),
});
}
let mut data = Zeroizing::new(Vec::with_capacity(symbols.len()));
let mut repaired = Vec::new();
for (index, row) in symbols.chunks(ROW_LEN).enumerate() {
let row_number = index.saturating_add(1);
let (fixed, repair) = repair_row(row).ok_or(RowError::Row {
row: row_number,
unreadable: row.iter().filter(|s| s.is_none()).count(),
})?;
if let Some(repair) = repair {
repaired.push(Repair {
row: row_number,
kind: repair,
});
}
data.extend_from_slice(
fixed
.get(..row.len().saturating_sub(ROW_PARITY))
.unwrap_or(&[]),
);
}
let bytes = from_symbols(&data).ok_or(RowError::Padding)?;
Ok(Decoded {
bytes: Zeroizing::new(bytes),
repaired,
})
}
pub fn read_row(text: &str, row: usize) -> Result<RowRead, RowError> {
let mut symbols: Vec<Option<u8>> = Vec::with_capacity(ROW_LEN);
for (position, c) in text.chars().enumerate() {
match read(c) {
Read::Separator => {}
Read::Erasure => symbols.push(None),
Read::Value(v) => symbols.push(Some(v)),
Read::Unknown => return Err(RowError::Character { position }),
}
}
if symbols.is_empty() {
return Err(RowError::Empty);
}
if symbols.len() <= ROW_PARITY || symbols.len() > ROW_LEN {
return Err(RowError::Shape {
characters: symbols.len(),
});
}
let (fixed, repair) = repair_row(&symbols).ok_or(RowError::Row {
row,
unreadable: symbols.iter().filter(|s| s.is_none()).count(),
})?;
Ok(RowRead {
text: Zeroizing::new(fixed.iter().map(|&s| letter(s)).collect()),
repair: repair.map(|kind| Repair { row, kind }),
})
}
#[derive(Debug)]
pub struct RowRead {
pub text: Zeroizing<String>,
pub repair: Option<Repair>,
}
fn repair_row(row: &[Option<u8>]) -> Option<(Vec<u8>, Option<RepairKind>)> {
let erased: Vec<usize> = row
.iter()
.enumerate()
.filter_map(|(i, s)| s.is_none().then_some(i))
.collect();
if erased.len() > MAX_ERASURES {
return None;
}
let data_len = row.len().saturating_sub(ROW_PARITY);
let filled = fill(row, &erased, data_len)?;
if checks(&filled, data_len) {
let repair = (!erased.is_empty()).then_some(RepairKind::Unreadable {
count: erased.len(),
});
return Some((filled, repair));
}
if !erased.is_empty() {
return None;
}
let mut found: Option<(usize, Vec<u8>)> = None;
for position in 0..row.len() {
let candidate = fill(row, &[position], data_len)?;
if checks(&candidate, data_len) && candidate.get(position) != row.get(position)?.as_ref() {
if found.is_some() {
return None;
}
found = Some((position, candidate));
}
}
let (position, fixed) = found?;
Some((fixed, Some(RepairKind::Wrong { position })))
}
fn fill(row: &[Option<u8>], holes: &[usize], data_len: usize) -> Option<Vec<u8>> {
let known: Vec<(u8, u8)> = row
.iter()
.enumerate()
.filter(|(i, s)| s.is_some() && !holes.contains(i))
.filter_map(|(i, s)| s.map(|v| (row_point(i, row.len()), v)))
.take(data_len)
.collect();
if known.len() < data_len {
return None;
}
let mut out = Vec::with_capacity(row.len());
for (i, s) in row.iter().enumerate() {
match s {
Some(v) if !holes.contains(&i) => out.push(*v),
_ => out.push(interpolate(&known, row_point(i, row.len()))),
}
}
Some(out)
}
fn row_point(i: usize, len: usize) -> u8 {
let data_len = len.saturating_sub(ROW_PARITY);
if i < data_len {
point(i)
} else {
point(ROW_DATA.saturating_add(i.saturating_sub(data_len)))
}
}
fn checks(row: &[u8], data_len: usize) -> bool {
let (data, given) = row.split_at(data_len.min(row.len()));
parity(data) == given
}
#[derive(Debug)]
pub struct Decoded {
pub bytes: Zeroizing<Vec<u8>>,
pub repaired: Vec<Repair>,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Repair {
pub row: usize,
pub kind: RepairKind,
}
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub enum RepairKind {
Wrong {
position: usize,
},
Unreadable {
count: usize,
},
}
impl fmt::Display for Repair {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self.kind {
RepairKind::Wrong { position } => write!(
f,
"row {}: character {} was wrong and has been corrected; check it against the sheet",
self.row,
position.saturating_add(1)
),
RepairKind::Unreadable { count } => write!(
f,
"row {}: {count} unreadable character{} recovered",
self.row,
if count == 1 { "" } else { "s" }
),
}
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub enum RowError {
Empty,
Character {
position: usize,
},
Shape {
characters: usize,
},
Row {
row: usize,
unreadable: usize,
},
Padding,
}
impl fmt::Display for RowError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::Empty => write!(f, "nothing to read"),
Self::Character { position } => write!(
f,
"character {} is not a digit or a letter; write ? for one that cannot be read",
position.saturating_add(1)
),
Self::Shape { characters } => write!(
f,
"{characters} characters do not make rows of 32; a last row has at least 5"
),
Self::Row { row, unreadable } => match unreadable {
0 => write!(
f,
"row {row} does not check and has more than one wrong character; read it \
again from the sheet"
),
1 | 2 => write!(
f,
"row {row} has {unreadable} unreadable and still does not check, so another \
character is wrong; a row recovers two unreadable or one wrong, not both; \
read it again from the sheet"
),
_ => write!(
f,
"row {row} has {unreadable} unreadable characters and recovers at most two; \
read it again from the sheet"
),
},
Self::Padding => write!(f, "the characters do not end on a whole byte"),
}
}
}
impl std::error::Error for RowError {}
#[cfg(test)]
#[allow(clippy::indexing_slicing, clippy::arithmetic_side_effects)]
mod tests {
use super::*;
#[test]
fn the_field_has_inverses_and_the_polynomial_is_primitive() {
for a in 1..32u8 {
assert_eq!(gf_mul(a, gf_inv(a)), 1, "{a}");
}
let mut seen = std::collections::BTreeSet::new();
let mut x = 1u8;
for _ in 0..31 {
seen.insert(x);
x = gf_mul(x, 2);
}
assert_eq!(seen.len(), 31);
assert_eq!(x, 1);
}
#[test]
fn a_row_is_its_data_and_four_parity_characters() {
let text = encode(&[0u8; 35]);
assert_eq!(text.len(), 64);
assert_eq!(&text[..28], "0".repeat(28));
assert_eq!(&text[28..32], "0000");
let text = encode(&[0xFF; 35]);
assert_eq!(text.len(), 64);
assert!(text.chars().all(|c| ALPHABET.contains(&(c as u8))));
}
#[test]
fn bytes_round_trip_at_every_length() {
for len in 0..=100usize {
let bytes: Vec<u8> = (0..len)
.map(|i| u8::try_from(i.wrapping_mul(53).wrapping_add(7) & 0xff).unwrap())
.collect();
let text = encode(&bytes);
let rows = len.saturating_mul(8).div_ceil(5).div_ceil(ROW_DATA);
assert_eq!(
text.len(),
len.saturating_mul(8).div_ceil(5) + rows * ROW_PARITY,
"{len}"
);
if len == 0 {
assert_eq!(decode(&text).unwrap_err(), RowError::Empty);
continue;
}
let decoded = decode(&text).unwrap_or_else(|e| panic!("{len}: {e}"));
assert_eq!(*decoded.bytes, bytes, "{len}");
assert!(decoded.repaired.is_empty());
}
}
#[test]
fn case_confusions_and_separators_are_read_through() {
let bytes = b"a value to write";
let text = encode(bytes);
let grouped: String = text
.to_ascii_lowercase()
.as_bytes()
.chunks(4)
.map(|g| std::str::from_utf8(g).unwrap())
.collect::<Vec<_>>()
.join(" ");
assert_eq!(*decode(&grouped).unwrap().bytes, bytes);
let confused = text.replace('0', "O").replace('1', "l");
assert_eq!(*decode(&confused).unwrap().bytes, bytes);
let mut chars: Vec<char> = text.chars().collect();
chars[0] = 'u';
let with_u: String = chars.iter().collect();
let decoded = decode(&with_u).unwrap();
assert_eq!(*decoded.bytes, bytes);
assert_eq!(
decoded.repaired,
vec![Repair {
row: 1,
kind: RepairKind::Unreadable { count: 1 }
}]
);
chars[0] = '#';
let outside: String = chars.iter().collect();
assert_eq!(
decode(&outside).unwrap_err(),
RowError::Character { position: 0 }
);
}
#[test]
fn one_wrong_character_anywhere_in_a_row_is_corrected_and_named() {
let bytes = [0x5A; 35];
let text = encode(&bytes);
let chars: Vec<char> = text.chars().collect();
for position in 0..chars.len() {
let mut wrong = chars.clone();
wrong[position] = if wrong[position] == 'Q' { 'R' } else { 'Q' };
let wrong: String = wrong.into_iter().collect();
let decoded = decode(&wrong).unwrap_or_else(|e| panic!("position {position}: {e}"));
assert_eq!(*decoded.bytes, bytes, "position {position}");
assert_eq!(
decoded.repaired,
[Repair {
row: position / ROW_LEN + 1,
kind: RepairKind::Wrong {
position: position % ROW_LEN
}
}],
"position {position}"
);
}
}
#[test]
fn two_unreadable_characters_in_a_row_are_recovered() {
let bytes = b"thirty-two bytes of some secret!";
let text = encode(bytes);
let mut chars: Vec<char> = text.chars().collect();
chars[3] = '?';
chars[30] = '?';
chars[40] = '?';
let smudged: String = chars.iter().collect();
let decoded = decode(&smudged).unwrap();
assert_eq!(*decoded.bytes, bytes);
assert_eq!(decoded.repaired.len(), 2);
assert_eq!(
decoded.repaired[0].to_string(),
"row 1: 2 unreadable characters recovered"
);
assert_eq!(
decoded.repaired[1],
Repair {
row: 2,
kind: RepairKind::Unreadable { count: 1 }
}
);
}
#[test]
fn a_row_beyond_repair_is_refused_by_name() {
let text = encode(&[0x33; 35]);
let mut chars: Vec<char> = text.chars().collect();
chars[35] = if chars[35] == 'A' { 'B' } else { 'A' };
chars[50] = if chars[50] == 'A' { 'B' } else { 'A' };
let wrong: String = chars.iter().collect();
assert_eq!(
decode(&wrong).unwrap_err(),
RowError::Row {
row: 2,
unreadable: 0
}
);
let mut chars: Vec<char> = text.chars().collect();
chars[0] = '?';
chars[1] = '?';
chars[2] = '?';
let smudged: String = chars.iter().collect();
assert_eq!(
decode(&smudged).unwrap_err(),
RowError::Row {
row: 1,
unreadable: 3
}
);
let mut chars: Vec<char> = text.chars().collect();
chars[5] = '?';
chars[9] = if chars[9] == 'A' { 'B' } else { 'A' };
let mixed: String = chars.iter().collect();
let err = decode(&mixed).unwrap_err();
assert_eq!(
err,
RowError::Row {
row: 1,
unreadable: 1
}
);
assert!(err.to_string().contains("not both"));
}
#[test]
fn a_shape_that_is_not_rows_is_refused() {
assert_eq!(
decode("ABCD").unwrap_err(),
RowError::Shape { characters: 4 }
);
assert_eq!(
decode(&"A".repeat(34)).unwrap_err(),
RowError::Shape { characters: 34 }
);
assert_eq!(decode(" - ").unwrap_err(), RowError::Empty);
}
}