diff options
Diffstat (limited to 'tvix/store/src/nixbase32.rs')
| -rw-r--r-- | tvix/store/src/nixbase32.rs | 165 |
1 files changed, 108 insertions, 57 deletions
diff --git a/tvix/store/src/nixbase32.rs b/tvix/store/src/nixbase32.rs index 913e60714b..39aa4f1d54 100644 --- a/tvix/store/src/nixbase32.rs +++ b/tvix/store/src/nixbase32.rs @@ -4,113 +4,164 @@ //! encoding to "nix base32" doesn't use any padding, and reads in characters //! in reverse order. //! -//! This is also the main reason why `data_encoding::Encoding` can't be used -//! directly, but this module aims to provide a similar interface (with some -//! methods omitted). -use data_encoding::{DecodeError, Encoding, Specification}; -use lazy_static::lazy_static; - -/// Nixbase32Encoding wraps a data_encoding::Encoding internally. -/// We can't use it directly, as nix also reads in characters in reverse order. -pub struct Nixbase32Encoding { - encoding: Encoding, -} +//! This is also the main reason why we can't use `data_encoding::Encoding` - +//! it gets things wrong if there normally would be a need for padding. + +use std::fmt::Write; + +use thiserror::Error; -lazy_static! { - /// Returns a Nixbase32Encoding providing some functions seen on a data_encoding::Encoding. - pub static ref NIXBASE32: Nixbase32Encoding = nixbase32_encoding(); +const ALPHABET: &'static [u8; 32] = b"0123456789abcdfghijklmnpqrsvwxyz"; + +/// Errors that can occur while decoding nixbase32-encoded data. +#[derive(Debug, Eq, PartialEq, Error)] +pub enum Nixbase32DecodeError { + #[error("character {0:x} not in alphabet")] + CharacterNotInAlphabet(u8), + #[error("nonzero carry")] + NonzeroCarry(), } -/// Populates the Nixbase32Encoding struct with a data_encoding::Encoding, -/// using the nixbase32 alphabet and config. -fn nixbase32_encoding() -> Nixbase32Encoding { - let mut spec = Specification::new(); - spec.symbols.push_str("0123456789abcdfghijklmnpqrsvwxyz"); +/// Returns encoded input +pub fn encode(input: &[u8]) -> String { + let output_len = encode_len(input.len()); + let mut output = String::with_capacity(output_len); + + if output_len > 0 { + for n in (0..=output_len - 1).rev() { + let b = n * 5; // bit offset within the entire input + let i = b / 8; // input byte index + let j = b % 8; // bit offset within that input byte - Nixbase32Encoding { - encoding: spec.encoding().unwrap(), + let mut c = input[i] >> j; + if i + 1 < input.len() { + // we want to right shift, and discard shifted out bits (unchecked) + // To do this without panicing, we need to do the shifting in u16 + // and convert back to u8 afterwards. + c |= ((input[i + 1] as u16) << 8 - j as u16) as u8 + } + + output + .write_char(ALPHABET[(c & 0x1f) as usize] as char) + .unwrap(); + } } + + output } -impl Nixbase32Encoding { - /// Returns encoded input - pub fn encode(&self, input: &[u8]) -> String { - // Reverse the input, reading in the bytes in reverse order. - let reversed: Vec<u8> = input.iter().cloned().rev().collect(); - self.encoding.encode(&reversed) - } +/// This maps a nixbase32-encoded character to its binary representation, which +/// is also the index of the character in the alphabet. +fn decode_char(encoded_char: &u8) -> Option<u8> { + Some(match encoded_char { + b'0'..=b'9' => encoded_char - b'0', + b'a'..=b'd' => encoded_char - b'a' + 10_u8, + b'f'..=b'n' => encoded_char - b'f' + 14_u8, + b'p'..=b's' => encoded_char - b'p' + 23_u8, + b'v'..=b'z' => encoded_char - b'v' + 27_u8, + _ => return None, + }) +} - /// Returns decoded input - /// Check [data_encoding::Encoding::encode] for the error cases. - pub fn decode(&self, input: &[u8]) -> Result<Vec<u8>, DecodeError> { - // Decode first, then reverse the bytes of the output. - let mut output = self.encoding.decode(input)?; - output.reverse(); - Ok(output) - } +/// Returns decoded input +pub fn decode(input: &[u8]) -> Result<Vec<u8>, Nixbase32DecodeError> { + let output_len = decode_len(input.len()); + let mut output: Vec<u8> = vec![0x00; output_len]; + + // loop over all characters in reverse, and keep the iteration count in n. + for (n, c) in input.iter().rev().enumerate() { + match decode_char(c) { + None => return Err(Nixbase32DecodeError::CharacterNotInAlphabet(*c)), + Some(c_decoded) => { + let b = n * 5; + let i = b / 8; + let j = b % 8; - /// Returns the decoded length of an input of length len. - /// Check [data_encoding::Encoding::decode_len] for the error cases. - pub fn decode_len(&self, len: usize) -> Result<usize, DecodeError> { - self.encoding.decode_len(len) + let val = (c_decoded as u16).rotate_left(j as u32); + output[i] |= (val & 0x00ff) as u8; + let carry = ((val & 0xff00) >> 8) as u8; + + // if we're at the end of dst… + if i == output_len - 1 { + // but have a nonzero carry, the encoding is invalid. + if carry != 0 { + return Err(Nixbase32DecodeError::NonzeroCarry()); + } + } else { + output[i + 1] |= carry; + } + } + } } - /// Returns the encoded length of an input of length len - pub fn encode_len(&self, len: usize) -> usize { - self.encoding.encode_len(len) + Ok(output) +} + +/// Returns the decoded length of an input of length len. +pub fn decode_len(len: usize) -> usize { + return (len * 5) / 8; +} + +/// Returns the encoded length of an input of length len +pub fn encode_len(len: usize) -> usize { + if len == 0 { + return 0; } + return (len * 8 - 1) / 5 + 1; } #[cfg(test)] mod tests { - use crate::nixbase32::NIXBASE32; use test_case::test_case; #[test_case("", vec![] ; "empty bytes")] - // FUTUREWORK: b/235 - // this seems to encode to 3w? - // #[test_case("0z", vec![0x1f]; "one byte")] + #[test_case("0z", vec![0x1f]; "one byte")] #[test_case("00bgd045z0d4icpbc2yyz4gx48ak44la", vec![ 0x8a, 0x12, 0x32, 0x15, 0x22, 0xfd, 0x91, 0xef, 0xbd, 0x60, 0xeb, 0xb2, 0x48, 0x1a, 0xf8, 0x85, 0x80, 0xf6, 0x16, 0x00]; "store path")] + #[test_case("0c5b8vw40dy178xlpddw65q9gf1h2186jcc3p4swinwggbllv8mk", vec![ + 0xb3, 0xa2, 0x4d, 0xe9, 0x7a, 0x8f, 0xdb, 0xc8, 0x35, 0xb9, 0x83, 0x31, 0x69, 0x50, 0x10, 0x30, + 0xb8, 0x97, 0x70, 0x31, 0xbc, 0xb5, 0x4b, 0x3b, 0x3a, 0xc1, 0x37, 0x40, 0xf8, 0x46, 0xab, 0x30, + ]; "sha256")] fn encode(enc: &str, dec: Vec<u8>) { - assert_eq!(enc, NIXBASE32.encode(&dec)); + assert_eq!(enc, super::encode(&dec)); } #[test_case("", Some(vec![]) ; "empty bytes")] - // FUTUREWORK: b/235 - // this seems to require spec.check_trailing_bits and still fails? - // #[test_case("0z", Some(vec![0x1f]); "one byte")] + #[test_case("0z", Some(vec![0x1f]); "one byte")] #[test_case("00bgd045z0d4icpbc2yyz4gx48ak44la", Some(vec![ 0x8a, 0x12, 0x32, 0x15, 0x22, 0xfd, 0x91, 0xef, 0xbd, 0x60, 0xeb, 0xb2, 0x48, 0x1a, 0xf8, 0x85, 0x80, 0xf6, 0x16, 0x00]); "store path")] + #[test_case("0c5b8vw40dy178xlpddw65q9gf1h2186jcc3p4swinwggbllv8mk", Some(vec![ + 0xb3, 0xa2, 0x4d, 0xe9, 0x7a, 0x8f, 0xdb, 0xc8, 0x35, 0xb9, 0x83, 0x31, 0x69, 0x50, 0x10, 0x30, + 0xb8, 0x97, 0x70, 0x31, 0xbc, 0xb5, 0x4b, 0x3b, 0x3a, 0xc1, 0x37, 0x40, 0xf8, 0x46, 0xab, 0x30, + ]); "sha256")] // this is invalid encoding, because it encodes 10 1-bytes, so the carry // would be 2 1-bytes #[test_case("zz", None; "invalid encoding-1")] // this is an even more specific example - it'd decode as 00000000 11 - // FUTUREWORK: b/235 - // #[test_case("c0", None; "invalid encoding-2")] + #[test_case("c0", None; "invalid encoding-2")] fn decode(enc: &str, dec: Option<Vec<u8>>) { match dec { Some(dec) => { // The decode needs to match what's passed in dec - assert_eq!(dec, NIXBASE32.decode(enc.as_bytes()).unwrap()); + assert_eq!(dec, super::decode(enc.as_bytes()).unwrap()); } None => { // the decode needs to be an error - assert_eq!(true, NIXBASE32.decode(enc.as_bytes()).is_err()); + assert_eq!(true, super::decode(enc.as_bytes()).is_err()); } } } #[test] fn encode_len() { - assert_eq!(NIXBASE32.encode_len(20), 32) + assert_eq!(super::encode_len(20), 32) } #[test] fn decode_len() { - assert_eq!(NIXBASE32.decode_len(32).unwrap(), 20) + assert_eq!(super::decode_len(32), 20) } } |