vintage_schematics/

ascii85.rs

//! Encoding and decoding of [ASCII85](https://en.wikipedia.org/wiki/Ascii85)-encoded data.
//!
//! # Examples
//!
//! ```rust
//! use vintage_schematics::ascii85::decode;
//!
//! let decoded = decode("87cURD_*#TDfTZ)+T").unwrap();
//! assert_eq!(decoded, b"Hello, world!");
//! ```

/// Error type returned by [`decode`].
#[derive(Debug, Copy, Clone, PartialEq, Eq)]
pub struct DecodeError {
	/// The position in the input where the error occurred.
	pub position: usize,

	/// The kind of error that occurred.
	pub kind: ErrorKind,
}

impl std::fmt::Display for DecodeError {
	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
		write!(f, "ascii85 decode error at position {}: {}", self.position, self.kind)
	}
}

impl std::error::Error for DecodeError {}

/// The kind of error that occurred during decoding ASCII85 input.
#[derive(Debug, Copy, Clone, PartialEq, Eq)]
pub enum ErrorKind {
	/// Invalid character.
	InvalidCharacter(char),

	/// Input data would overflow when decoded.
	Overflow { char: char, encoded_count: usize },

	/// 'y' at invalid position.
	BadYPosition,

	/// 'z' at invalid position.
	BadZPosition,
}

impl std::fmt::Display for ErrorKind {
	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
		match self {
			Self::InvalidCharacter(char) => write!(f, "invalid character: {char}"),
			Self::Overflow { char, encoded_count } => {
				write!(f, "malformed input: character '{char}' at chunk position {encoded_count} would overflow",)
			}
			Self::BadYPosition => write!(f, "encountered 'y' at invalid position"),
			Self::BadZPosition => write!(f, "encountered 'z' at invalid position"),
		}
	}
}

/// Array of powers of 85.
// when decoding ASCII85, wikipedia says that the fifth char shouldn't be multiplied by anything.
// however, in the hardcoded array, i'm instead multiplying by 85^0.
// this would mean that, if the fifth char is 'a', which has a value of (97-33=64), instead of adding `64*85^0`, we
// should just add `64` to the decoded value.
// HOWEVER, there are two cool and epic mathematical properties that help us out here:
// - CaEP 1: multiplying a number by 1 doesn't change it: https://en.wikipedia.org/wiki/Multiplicative_identity
// - CaEP 2: any number raised to the zeroth power is 1: https://en.wikipedia.org/wiki/Exponentiation#Zero_exponent
// this means that `64*85^0 = 64*1 = 64`.
// haters will say it's fake.
// i would direct the hater's attention to this exhaustive proof by LLVM: https://godbolt.org/z/9nM6Yze5s
// and also this: https://github.com/rust-lang/rust/blob/a33907a/library/core/src/num/uint_macros.rs#L3433-L3435
const POWS: [u32; 5] = [85u32.pow(4), 85u32.pow(3), 85u32.pow(2), 85u32.pow(1), 85u32.pow(0)];

/// Decodes an [ASCII85](https://en.wikipedia.org/wiki/Ascii85)-encoded string into a byte vector.
///
/// # Errors
///
/// Returns an error if the input data is not valid ASCII85.
/// See [`DecodeError`] for more information.
#[allow(clippy::missing_panics_doc)]
pub fn decode(input: &str) -> Result<Vec<u8>, DecodeError> {
	// janky ascii85 decoder

	// read these example tables upside-down for a clear description of the decoding behaviour:
	// https://en.wikipedia.org/wiki/Ascii85#Example_for_Ascii85

	// here's an example of how it works for the input on wikipedia:
	// - take the first five ASCII characters (`9jqo^`)
	// - subtract 33 from each character's ASCII value
	//   - INPUT:  |  9  |  j  |  q  |  o  |  ^  |
	//   - ASCII:  |  57 | 106 | 113 | 111 |  94 |
	//   - RESULT: |  24 |  73 |  80 |  78 |  61 |
	// - multiply every nth char by (85^(4-n)) and add them together
	//   - `POWS` contains precalculated powers of 85 in the correct order
	//   - 24*85^4 + 73*85^3 + 80*85^2 + 78*85^1 + 61*85^0
	//   - ≈1.25bn + ≈44.83m + 578,000 + 6630    + 61
	//   - =1,298,230,816
	// - encode as a big-endian 32-bit integer

	// you have now converted five ASCII characters into four bytes of data :) repeat until end of input

	let mut encoded_count = 0u32;
	let mut decoded_chunk = 0u32;

	// TODO: capacity calculation doesn't account for 'z's
	let mut decoded = Vec::with_capacity(((input.len() / 5) * 4) + 5);

	for (position, char) in input.chars().filter(|c| !c.is_ascii_whitespace()).enumerate() {
		let decode_err = |kind| DecodeError { position, kind };

		match char {
			// special cases: 'z' (four nulls) and 'y' (four spaces)
			'z' if encoded_count == 0 => decoded.extend_from_slice(&[0u8; 4]),
			'y' if encoded_count == 0 => decoded.extend_from_slice(&[b' '; 4]),
			'z' => {
				return Err(decode_err(ErrorKind::BadZPosition));
			}
			'y' => {
				return Err(decode_err(ErrorKind::BadYPosition));
			}

			// other chars
			_ => decode_character(char, &mut encoded_count, &mut decoded_chunk, &mut decoded).map_err(decode_err)?,
		}
	}

	// pad input with 'u's
	// but why?: https://en.wikipedia.org/wiki/Ascii85#Adobe_version
	let mut padding = 0;
	while encoded_count != 0 {
		decode_character('u', &mut encoded_count, &mut decoded_chunk, &mut decoded).map_err(|kind| DecodeError {
			position: input.len() + padding,
			kind,
		})?;
		padding += 1;
	}

	// remove trailing padding
	decoded.drain((decoded.len() - padding)..decoded.len());

	Ok(decoded)
}

fn decode_character(
	char: char,
	encoded_count: &mut u32,
	decoded_chunk: &mut u32,
	decoded: &mut Vec<u8>,
) -> Result<(), ErrorKind> {
	if !('!'..='u').contains(&char) {
		return Err(ErrorKind::InvalidCharacter(char));
	}
	let value = (char as u8) - 33;

	// each group of five characters encodes four bytes.
	// within each group of five, the nth character adds (85^(4-n)) to the decoded value
	let overflow_err = || ErrorKind::Overflow {
		char,
		encoded_count: *encoded_count as usize,
	};

	let value = u32::from(value).checked_mul(POWS[*encoded_count as usize]).ok_or_else(overflow_err)?;
	*decoded_chunk = decoded_chunk.checked_add(value).ok_or_else(overflow_err)?;

	*encoded_count += 1;
	if (*encoded_count) == 5 {
		// push bytes and reset state
		decoded.extend_from_slice(&decoded_chunk.to_be_bytes());
		*encoded_count = 0;
		*decoded_chunk = 0;
	}

	Ok(())
}

/// Encodes a set of bytes into an [ASCII85](https://en.wikipedia.org/wiki/Ascii85)-encoded string.
///
/// If `encode_y` is set, four consecutive spaces will be encoded as 'y' as in
/// [`btoa` version 4.2](https://en.wikipedia.org/wiki/Ascii85#btoa_version).
#[must_use]
#[allow(clippy::cast_possible_truncation, clippy::missing_panics_doc)]
pub fn encode(input: &[u8], encode_y: bool) -> String {
	let mut out = String::with_capacity((input.len() / 4) * 5);
	for chunk in input.chunks(4) {
		if chunk == [0u8; 4] {
			out.push('z');
			continue;
		} else if encode_y && chunk == [b' '; 4] {
			out.push('y');
			continue;
		}

		let (chunk, encoded_count) = if chunk.len() < 4 {
			let mut chunk = chunk.to_vec();
			let len = 4 - chunk.len();
			chunk.extend(std::iter::repeat_n(0u8, len));

			(u32::from_be_bytes(chunk.try_into().expect("chunk length should be 4")), 5 - len)
		} else {
			(u32::from_be_bytes(chunk.try_into().expect("chunk length should be 4")), 5)
		};

		// encode four bytes as five ASCII characters
		for pow in POWS.iter().take(encoded_count) {
			let encoded = ((((chunk / pow) % 85) + 33) as u8) as char;
			out.push(encoded);
		}
	}

	out
}