path: root/tvix/nix-compat/src/nixbase32.rs

//! Implements the slightly odd "base32" encoding that's used in Nix.
//!
//! Nix uses a custom alphabet. Contrary to other implementations (RFC4648),
//! encoding to "nix base32" doesn't use any padding, and reads in characters
//! in reverse order.
//!
//! 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 data_encoding::{DecodeError, DecodeKind};

const ALPHABET: &[u8; 32] = b"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);

    for n in (0..output_len).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

        // 5-bit words aren't aligned to bytes
        // we can only read byte-aligned units
        // read 16 bits then shift and mask to 5
        let c = {
            let mut word = input[i] as u16;
            if let Some(&msb) = input.get(i + 1) {
                word |= (msb as u16) << 8;
            }
            (word >> j) & 0x1f
        };

        output.write_char(ALPHABET[c as usize] as char).unwrap();
    }

    output
}

/// This maps a nixbase32-encoded character to its binary representation, which
/// is also the index of the character in the alphabet. Invalid characters are
/// mapped to 0xFF, which is itself an invalid value.
const BASE32_ORD: [u8; 256] = {
    let mut ord = [0xFF; 256];
    let mut alphabet = ALPHABET.as_slice();
    let mut i = 0;

    while let &[c, ref tail @ ..] = alphabet {
        ord[c as usize] = i;
        alphabet = tail;
        i += 1;
    }

    ord
};

/// Returns decoded input
pub fn decode(input: impl AsRef<[u8]>) -> Result<Vec<u8>, DecodeError> {
    let input = input.as_ref();

    let output_len = decode_len(input.len());
    if input.len() != encode_len(output_len) {
        return Err(DecodeError {
            position: input.len().min(encode_len(output_len)),
            kind: DecodeKind::Length,
        });
    }
    let mut output: Vec<u8> = vec![0x00; output_len];

    decode_inner(input, &mut output)?;
    Ok(output)
}

pub fn decode_fixed<const K: usize>(input: impl AsRef<[u8]>) -> Result<[u8; K], DecodeError> {
    let input = input.as_ref();

    if input.len() != encode_len(K) {
        return Err(DecodeError {
            position: input.len().min(encode_len(K)),
            kind: DecodeKind::Length,
        });
    }

    let mut output = [0; K];
    decode_inner(input, &mut output)?;
    Ok(output)
}

fn decode_inner(input: &[u8], output: &mut [u8]) -> Result<(), DecodeError> {
    // loop over all characters in reverse, and keep the iteration count in n.
    let mut carry = 0;
    let mut mask = 0;
    for (n, &c) in input.iter().rev().enumerate() {
        let b = n * 5;
        let i = b / 8;
        let j = b % 8;

        let digit = BASE32_ORD[c as usize];
        let value = (digit as u16) << j;
        output[i] |= value as u8 | carry;
        carry = (value >> 8) as u8;

        mask |= digit;
    }

    if mask == 0xFF {
        return Err(DecodeError {
            position: find_invalid(input),
            kind: DecodeKind::Symbol,
        });
    }

    // if we're at the end, but have a nonzero carry, the encoding is invalid.
    if carry != 0 {
        return Err(DecodeError {
            position: 0,
            kind: DecodeKind::Trailing,
        });
    }

    Ok(())
}

fn find_invalid(input: &[u8]) -> usize {
    for (i, &c) in input.iter().enumerate() {
        if !ALPHABET.contains(&c) {
            return i;
        }
    }

    unreachable!()
}

/// Returns the decoded length of an input of length len.
pub const fn decode_len(len: usize) -> usize {
    (len * 5) / 8
}

/// Returns the encoded length of an input of length len
pub const fn encode_len(len: usize) -> usize {
    (len * 8 + 4) / 5
}

#[cfg(test)]
mod tests {
    use hex_literal::hex;
    use rstest::rstest;

    #[rstest]
    #[case::empty_bytes("", &[])]
    #[case::one_byte("0z", &hex!("1f"))]
    #[case::store_path("00bgd045z0d4icpbc2yyz4gx48ak44la", &hex!("8a12321522fd91efbd60ebb2481af88580f61600"))]
    #[case::sha256("0c5b8vw40dy178xlpddw65q9gf1h2186jcc3p4swinwggbllv8mk", &hex!("b3a24de97a8fdbc835b9833169501030b8977031bcb54b3b3ac13740f846ab30"))]
    #[test]
    fn encode(#[case] enc: &str, #[case] dec: &[u8]) {
        assert_eq!(enc, super::encode(dec));
    }

    #[rstest]
    #[case::empty_bytes("", Some(&[][..]) )]
    #[case::one_byte("0z", Some(&hex!("1f")[..]))]
    #[case::store_path("00bgd045z0d4icpbc2yyz4gx48ak44la", Some(&hex!("8a12321522fd91efbd60ebb2481af88580f61600")[..]))]
    #[case::sha256("0c5b8vw40dy178xlpddw65q9gf1h2186jcc3p4swinwggbllv8mk", Some(&hex!("b3a24de97a8fdbc835b9833169501030b8977031bcb54b3b3ac13740f846ab30")[..]))]
    // this is invalid encoding, because it encodes 10 1-bits, so the carry
    // would be 2 1-bits
    #[case::invalid_encoding_1("zz", None)]
    // this is an even more specific example - it'd decode as 00000000 11
    #[case::invalid_encoding_2("c0", None)]
    // This has an invalid length
    #[case::invalid_encoding_3("0", None)]
    // This has an invalid length
    #[case::invalid_encoding_4("0zz", None)]
    #[test]
    fn decode(#[case] enc: &str, #[case] dec: Option<&[u8]>) {
        match dec {
            Some(dec) => {
                // The decode needs to match what's passed in dec
                assert_eq!(dec, super::decode(enc).unwrap());
            }
            None => {
                // the decode needs to be an error
                assert!(super::decode(enc).is_err());
            }
        }
    }

    #[test]
    fn decode_fixed() {
        assert_eq!(
            super::decode_fixed("00bgd045z0d4icpbc2yyz4gx48ak44la").unwrap(),
            hex!("8a12321522fd91efbd60ebb2481af88580f61600")
        );
        assert_eq!(
            super::decode_fixed::<32>("00").unwrap_err(),
            super::DecodeError {
                position: 2,
                kind: super::DecodeKind::Length
            }
        );
    }

    #[test]
    fn encode_len() {
        assert_eq!(super::encode_len(0), 0);
        assert_eq!(super::encode_len(20), 32);
    }

    #[test]
    fn decode_len() {
        assert_eq!(super::decode_len(0), 0);
        assert_eq!(super::decode_len(1), 0);
        assert_eq!(super::decode_len(2), 1);
        assert_eq!(super::decode_len(3), 1);
        assert_eq!(super::decode_len(4), 2);
        assert_eq!(super::decode_len(5), 3);
        assert_eq!(super::decode_len(32), 20);
    }
}