//! Unique symbol made from human readable tags.

// This module implements https://en.wikipedia.org/wiki/Arithmetic_coding for the
// purpose of packing a string into a u64 to use as an ID. If you want to use
// arithmetic coding consider the https://docs.rs/arcode/latest/arcode/ crate.
// This algorithm is able to compress about 10-12 characters into a u64.

use range::*;

/// Unique symbol, given a unique tag.
///
/// ```
/// use uniserde::symbol::Symbol;
///
/// const PROPERTY: Symbol = Symbol::new("Property");
/// # let _ = PROPERTY;
/// ```
///
/// This type can be used to create "extendable enums" where
/// each variant is given by a different Symbol.
///
/// Internally each [`Symbol`] is just a [`u64`]. As such, a [`Symbol`] is very cheap
/// to copy and compare.
#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
#[repr(transparent)]
pub struct Symbol(u64);

impl Symbol {
    /// Panicking version of [`Self::try_new()`].
    ///
    /// This is more useful in const contexts as you don't have to handle the possible
    /// error manually.
    ///
    /// # Panics
    /// This function will panic when [`Self::try_new()`] would return an error.
    ///
    /// ```compile_fail
    /// use uniserde::symbol::Symbol;
    ///
    /// // The tag is to long so new will panic.
    /// const MY_SYMBOL: Symbol = Symbol::new("some really long tag");
    /// # let _ = MY_SYMBOL;
    /// ```
    #[track_caller]
    pub const fn new(tag: &str) -> Self {
        match Self::try_new(tag) {
            Ok(s) => s,
            Err(EncodeError::TooComplex { .. }) => {
                panic!("Tag is too complex to encode. Try making it shorter.")
            }
            Err(EncodeError::UnknownChar(_)) => {
                panic!(
                    "Unknown character, supported characters \
                    are: a-z, A-Z, 0-9, _, -, and space."
                );
            }
        }
    }

    /// Create a new symbol from a string tag.
    ///
    /// `tag` can be a string with the characters `a-z`, `A-Z`, `0-9`, `_`,
    /// `-`, and ` ` (space). The tag can range from 0 to about 10 characters
    /// in length. There is not fixed limit on the length. If the tag
    /// is too complex to store in the symbol then a
    /// [`EncodeError::TooComplex`] error is returned. If this happens try using
    /// a shorter tag and/or remove capitals and numbers.
    pub const fn try_new(tag: &str) -> Result<Self, EncodeError<'_>> {
        match encode(tag) {
            Ok(tag) => Ok(Self(tag)),
            Err(err) => Err(err),
        }
    }

    /// Convert the symbol to it's integer representation.
    ///
    /// This is provided to allow using a [`Symbol`] as a const generic.
    ///
    /// ```
    /// use uniserde::symbol::Symbol;
    ///
    /// struct MyType<const N: u64>;
    ///
    /// type OtherType = MyType<{ Symbol::new("OtherType").to_int() }>;
    /// # let _: OtherType;
    /// ```
    pub const fn to_int(self) -> u64 {
        self.0
    }

    /// Create a symbol from a integer.
    ///
    /// This is to be used in combination with [`Self::to_int()`] to rebuild
    /// the [`Symbol`].
    ///
    /// This function cannot fail. However, if a integer not made by
    /// [`Self::to_int()`] is provided then the Symbol will likely display
    /// as a random string when calling [`Display::fmt()`][core::fmt::Display::fmt]
    /// or [`Debug::fmt()`][core::fmt::Debug::fmt].
    pub const fn from_int(value: u64) -> Self {
        Self(value)
    }

    /// Const form of [`PartialEq::eq()`].
    ///
    /// Checking for equality via [`Self::to_int()`] is also possible.
    pub const fn eq(self, other: Self) -> bool {
        self.0 == other.0
    }
}

impl core::fmt::Debug for Symbol {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        f.debug_tuple("Symbol").field(&DisplayFmt(self.0)).finish()
    }
}

/// Helper for printing the symbol in the Debug impl.
struct DisplayFmt(u64);

impl core::fmt::Debug for DisplayFmt {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        decode(self.0, f)
    }
}

impl core::fmt::Display for Symbol {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        decode(self.0, f)
    }
}

/// Error while encoding a tag for a [`Symbol`].
#[derive(Debug)]
pub enum EncodeError<'a> {
    /// The tag is too complex to fit in a [`u64`].
    ///
    /// If this happens, then reduce the string to around what `encoded` has.
    TooComplex {
        /// The amount of the input string that was encoded properly.
        encoded: &'a str,
    },

    /// An unknown character was found in the tag.
    ///
    /// Supported characters: `a-z`, `A-Z`, `0-9`, `_`, `-`, and ` ` (space).
    UnknownChar(char),
}

impl<'a> EncodeError<'a> {
    /// Create a TooComplex error in a const ocntext.
    const fn too_complex(input: &'a str, length: usize) -> Self {
        // If the length is past the end then we just return all of the string.
        if length >= input.len() {
            return Self::TooComplex { encoded: input };
        }

        // Slice the string manually.
        let buffer = input.as_bytes();
        let (slice, _) = buffer.split_at(length);
        let s = match core::str::from_utf8(slice) {
            Ok(s) => s,

            // This shouldn't happen because if we would split an unicode char we
            // would have has a unknown char instead.
            Err(_) => panic!("Not valid UTF8"),
        };

        Self::TooComplex { encoded: s }
    }
}

impl<'a> core::fmt::Display for EncodeError<'a> {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        match self {
            EncodeError::TooComplex { encoded } => write!(
                f,
                "Tag is to complex to encode. \
                Encoded this portion of the tag: \
                `{encoded}`. Try making the tag shorter."
            ),
            EncodeError::UnknownChar(char) => write!(
                f,
                "Unknown character `{char}`, \
                supported characters are: a-z, A-Z, 0-9, _, -, and space."
            ),
        }
    }
}

#[cfg(feature = "std")]
impl<'a> std::error::Error for EncodeError<'a> {}

// Decode an arithmetic coded int into a string.
fn decode(input: u64, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
    // The interval and a range in that interval.
    let (interval, mut range) = Interval::new();

    // The precision needs to match what was used for the encoding (in the interval).
    let mut precision = 31;

    // The input buffer being read from.
    let mut input_buffer = 0;

    // Offset into the input.
    let mut offset = 0;

    // Read a bit to fill the precision.
    for _ in 0..precision {
        input_buffer = (input_buffer << 1)
            | match bit(&mut precision, &mut offset, input) {
                Some(x) => x,
                None => {
                    // If an error happens then we print this and return.
                    // As decoding is only used for displaying the symbol.
                    write!(f, "<EOF>")?;
                    return Ok(());
                }
            };
    }

    // Loop until we run out of input or hit a \0.
    let mut len = 0;
    loop {
        // The symbol that covers the input.
        let symbol: usize;

        // The range of the symbol.
        let mut low_high: Range;

        // Lower and upper bound of binary search.
        let mut sym_idx_low_high = (0, ALPHABET.len());

        // Binary search for the symbol that covers the input.
        loop {
            // Guess half of the range.
            let sym_idx_mid = (sym_idx_low_high.0 + sym_idx_low_high.1) / 2;

            // Find the range the symbol covers.
            low_high = calculate_range(range, sym_idx_mid, len);

            if low_high.low <= input_buffer && input_buffer < low_high.high {
                // The range coverse the input so its the correct symbol.
                symbol = sym_idx_mid;
                break;
            } else if input_buffer >= low_high.high {
                // The symbol covers a region that is to low.
                // We move the search to above the symbol.
                sym_idx_low_high.0 = sym_idx_mid + 1;
            } else {
                // The symbol covers a region that is to high.
                // We move the search to below the symbol.
                sym_idx_low_high.1 = sym_idx_mid - 1;
            }
        }

        // When we see a null byte we know the string is done.
        if symbol == ALPHABET.len() {
            break;
        }

        // Update the range to be what we found for the symbol.
        range = low_high;

        // Keep scaling the range up.
        while interval.in_bottom_half(range) || interval.in_upper_half(range) {
            if interval.in_bottom_half(range) {
                // The range is in the bottom half of the interval.
                range = interval.scale_bottom_half(range);

                // Move the input to follow the scaling of the range.
                // The lowest bit is given a new bit from the input.
                input_buffer = (2 * input_buffer)
                    | match bit(&mut precision, &mut offset, input) {
                        Some(x) => x,
                        None => {
                            // If an error happens then we print this and return.
                            // As decoding is only used for displaying the symbol.
                            write!(f, "<EOF>")?;
                            return Ok(());
                        }
                    };
            } else if interval.in_upper_half(range) {
                // The range in the top half of the interval.
                range = interval.scale_upper_half(range);

                // Move the input to follow the scaling of the range.
                // The lowest bit is given a new bit from the input.
                input_buffer = (2 * (input_buffer - interval.half()))
                    | match bit(&mut precision, &mut offset, input) {
                        Some(x) => x,
                        None => {
                            // If an error happens then we print this and return.
                            // As decoding is only used for displaying the symbol.
                            write!(f, "<EOF>")?;
                            return Ok(());
                        }
                    };
            }
        }

        // Keep scaling the range when it contains the half point of the interval.
        while interval.in_middle_half(range) {
            // The range is in the middle of the interval (contains the center).
            // Scale it up by a factor of 2.
            range = interval.scale_middle_half(range);

            // Scale the input to follow the range.
            // The lowest bit is given a new bit from the input.
            input_buffer = (2 * (input_buffer - interval.quarter()))
                | match bit(&mut precision, &mut offset, input) {
                    Some(x) => x,
                    None => {
                        // If an error happens then we print this and return.
                        // As decoding is only used for displaying the symbol.
                        write!(f, "<EOF>")?;
                        return Ok(());
                    }
                };
        }

        // At this point we know the symbol and are ready to find the next one
        // after making sure the range is large enough for the precision.

        // Write out the symbol we found.
        core::fmt::Display::fmt(&(ALPHABET[symbol].0 as char), f)?;

        len += 1;
    }

    Ok(())
}

// Read a bit from the input int.
fn bit(precision: &mut u64, offset: &mut u64, input: u64) -> Option<u64> {
    // We only have 64 bits of input possible from a u64.
    if *offset < 64 {
        // Read the bit.
        let bit = (input & (1u64 << *offset)) != 0;

        // Move the cursor forward to read the next bit next time.
        *offset += 1;

        Some(bit as _)
    } else {
        // If there is no more precision then we have no more input.
        if *precision == 0 {
            return None;
        }

        // Lower the precision and give back a 0 bit as we have no more real
        // information.
        *precision -= 1;
        Some(0)
    }
}

// Arithmetic code a string into a int.
//
// This is a type of compression.
const fn encode(input: &str) -> Result<u64, EncodeError<'_>> {
    // Interval and current range in that interval.
    let (interval, mut range) = Interval::new();

    // Output buffer.
    let mut output = 0;

    // Offset into the output buffer to write to.
    let mut offset = 0;

    // Index into the input string.
    let mut index = 0;

    // Bits pending to write.
    let mut pending_bit_count = 0;

    // For each char in the string and the terminator.
    while index < input.len() + 1 {
        // Get the char.
        let symbol = if index == input.len() {
            // Terminate with the null byte so we can recover the length in the
            // decode.
            b'\0'
        } else {
            input.as_bytes()[index]
        };

        // Find the symbol in the alphabet.
        let Some(symbol_index) = find_symbol(symbol) else {
            return Err(EncodeError::UnknownChar(symbol as char));
        };

        // Update the range to be for the symbol.
        range = calculate_range(range, symbol_index, index);

        // While the range is in the bottom or top half we can emit a bit
        // and scale the range back to not loose precision.
        while interval.in_bottom_half(range) || interval.in_upper_half(range) {
            if interval.in_bottom_half(range) {
                // Rescale range to the full interval.
                range = interval.scale_bottom_half(range);

                // Emit a 0 as the range was in the lower half of the interval.
                (output, offset, pending_bit_count) =
                    match emit(output, offset, pending_bit_count, false) {
                        Some(x) => x,
                        None => return Err(EncodeError::too_complex(input, index)),
                    };
            } else if interval.in_upper_half(range) {
                // Rescale range to the full interval.
                range = interval.scale_upper_half(range);

                // Emit a 1 as the range was in the lower half of the interval.
                (output, offset, pending_bit_count) =
                    match emit(output, offset, pending_bit_count, true) {
                        Some(x) => x,
                        None => return Err(EncodeError::too_complex(input, index)),
                    };
            }
        }

        // If the range is in the middle then the above couldn't scale it up.
        // So we do it here from the middle.
        // Because we don't know which side it will eventually be we add pending bits.
        while interval.in_middle_half(range) {
            // Rescale range to the full interval.
            range = interval.scale_middle_half(range);

            pending_bit_count += 1;
        }

        // Move to the next char.
        index += 1;
    }

    pending_bit_count += 1;

    if interval.in_bottom_quarter(range) {
        (output, _, _) = match emit(output, offset, pending_bit_count, false) {
            Some(x) => x,
            None => return Err(EncodeError::too_complex(input, index)),
        };
    } else {
        (output, _, _) = match emit(output, offset, pending_bit_count, true) {
            Some(x) => x,
            None => return Err(EncodeError::too_complex(input, index)),
        };
    }

    Ok(output)
}

// Emit a bit into the output int.
const fn emit(
    mut output: u64,
    mut offset: u64,
    mut pending_bit_count: usize,
    bit: bool,
) -> Option<(u64, u64, usize)> {
    // We can't emit a bit if we ran out of room.
    if offset + pending_bit_count as u64 >= 64 {
        return None;
    }

    // Emit the bit.
    output |= (bit as u64) << offset;
    offset += 1;

    // For each middle half scale emit the inverse bit.
    while pending_bit_count > 0 {
        // Emit a inverted bit for each pending bit.
        output |= (!bit as u64) << offset;
        offset += 1;
        pending_bit_count -= 1;
    }

    // Return updated output state.
    Some((output, offset, pending_bit_count))
}

// Calculate the range a symbol covers.
//
// The input `range` is the current range the symbol's range will be scaled to be
// inside of.
const fn calculate_range(range: Range, symbol_index: usize, len: usize) -> Range {
    // The symbol's range needs to be scaled down by the current width.
    let new_width = range.high - range.low;

    // Get the probability range of the symbol, this is from 0 to 65536.
    let Range { low, high } = probability(symbol_index, len);

    // Scale the probability range to be within the given range.
    Range {
        low: range.low + new_width * low / 65536,
        high: range.low + new_width * high / 65536,
    }
}

// Get the probability range for a symbol.
//
// Probabilities are p/65536.
const fn probability(symbol_index: usize, len: usize) -> Range {
    if symbol_index == ALPHABET.len() {
        // If this is the \0 symbol then we use whatever is left.

        // Lookup the probability of the last symbol for this len.
        let (_, table) = ALPHABET[ALPHABET.len() - 1];
        let t = table[len].0;
        let f = table[len].1;

        // Use the remaining range.
        Range {
            low: t + f,
            high: 65536,
        }
    } else {
        // Lookup the symbol.
        let (_, table) = ALPHABET[symbol_index];

        // Lookup the probability for this length.
        let t = table[len].0;
        let f = table[len].1;

        Range {
            low: t,
            high: t + f,
        }
    }
}

// Find the index of a symbol.
const fn find_symbol(symbol: u8) -> Option<usize> {
    if symbol == b'\0' {
        // We use this special value as \0 isn't in the table.
        return Some(ALPHABET.len());
    }

    // Look through the table.
    let mut i = 0;
    while i < ALPHABET.len() {
        if ALPHABET[i].0 == symbol {
            return Some(i);
        }
        i += 1;
    }
    None
}

mod range {
    // A range in an interval.
    #[derive(Debug, Copy, Clone)]
    pub struct Range {
        pub low: u64,
        pub high: u64,
    }

    // An interval given by a precision.
    //
    // The range of the arithmetic coding "bounces" around this interval.
    #[derive(Debug, Copy, Clone)]
    pub struct Interval {
        one_quarter: u64,
        half: u64,
        three_quarter: u64,
    }

    impl Interval {
        pub const fn new() -> (Self, Range) {
            // A precision of 31 bits is hardcoded to not overflow the u64 multiplication
            // and because the alphabet uses a 2^16 divisor.
            let precision = 31;

            let high: u64 = 1 << precision;
            (
                Self {
                    one_quarter: high / 4,
                    half: high / 2,
                    three_quarter: (high / 4) * 3,
                },
                Range { low: 0, high },
            )
        }

        /// Check if the range is entirely in the bottom half of the interval.
        pub const fn in_bottom_half(&self, range: Range) -> bool {
            range.high < self.half
        }

        /// Check if the range is entirely in the upper half of the interval.
        pub const fn in_upper_half(&self, range: Range) -> bool {
            range.low > self.half
        }

        /// Check if the range is entirely in the middle half of the interval.
        pub const fn in_middle_half(&self, range: Range) -> bool {
            range.low > self.one_quarter && range.high < self.three_quarter
        }

        pub const fn in_bottom_quarter(&self, range: Range) -> bool {
            range.low <= self.one_quarter
        }

        /// Take a range in the upper half of the interval and scale it
        /// to the whole interval.
        pub const fn scale_upper_half(&self, mut range: Range) -> Range {
            range.low = (range.low - self.half) << 1;
            range.high = (range.high - self.half) << 1;
            range
        }

        /// Take a range in the middle of the interval and scale it
        /// to the whole interval.
        pub const fn scale_middle_half(&self, mut range: Range) -> Range {
            range.low = (range.low - self.one_quarter) << 1;
            range.high = (range.high - self.one_quarter) << 1;
            range
        }

        /// Take a range in the bottom half of the interval and scale it
        /// to the whole interval.
        pub const fn scale_bottom_half(&self, mut range: Range) -> Range {
            range.low <<= 1;
            range.high <<= 1;
            range
        }

        /// Get the half way point.
        pub const fn half(&self) -> u64 {
            self.half
        }

        /// Get the quarter point.
        pub const fn quarter(&self) -> u64 {
            self.one_quarter
        }
    }
}

#[cfg(test)]
mod test {
    use super::*;
    use proptest::proptest;
    use std::collections::HashMap;

    proptest! {
        #[allow(unreachable_code)]
        #[test]
        #[cfg_attr(miri, ignore)]
        fn encode_decode(str in "(?:[a-z]|[A-Z]|[0-9]|[ _-]){0,18}") {
            // Generate a symbol from the string.
            let s = match Symbol::try_new(&str) {
                Ok(s) => s,
                Err(EncodeError::TooComplex { .. }) => {
                    // All too complex should be over 4 chars.
                    assert!(str.len() > 3);
                    return Ok(());
                }
                Err(err) => panic!("{:?}", err),
            };

            // Format symbol as string to decode it.
            let x = format!("{}", s);

            // The symbol as a string should match the original string.
            assert_eq!(x, str);
        }
    }

    #[test]
    #[should_panic(expected = "Tag is too complex to encode. Try making it shorter.")]
    fn too_complex_panic() {
        Symbol::new("0123456789");
    }

    #[test]
    #[should_panic(
        expected = "Unknown character, supported characters are: a-z, A-Z, 0-9, _, -, and space."
    )]
    fn unknown_char_panic() {
        Symbol::new("Hello, world");
    }

    #[test]
    fn in_match() {
        // This module is to give a path in the match instead of just a
        // possible binding.
        mod s {
            use super::*;

            pub const A: Symbol = Symbol::new("A");
            pub const B: Symbol = Symbol::new("B");
            pub const C: Symbol = Symbol::new("C");
        }

        match Symbol::new("B") {
            s::A => panic!(),
            s::B => {}
            s::C => panic!(),
            _ => unreachable!(),
        }
    }

    #[test]
    fn in_generic() {
        struct X<const N: u64>;

        // A symbol can become a int to use in a const generic.
        type Z = X<{ Symbol::new("Hello world").to_int() }>;
        let _: Z;
    }

    #[test]
    fn examples() {
        // Some fixed examples.

        const _: Symbol = Symbol::new("eeeeeeeeeeeeeeee");
        const _: Symbol = Symbol::new("XXX");
        const _: Symbol = Symbol::new("Hello world");
        const _: Symbol = Symbol::new("hello world_");
        const _: Symbol = Symbol::new("____________");
        const _: Symbol = Symbol::new("          ");
        const _: Symbol = Symbol::new("--------");
        const _: Symbol = Symbol::new("_-_-_-_-_");
        const _: Symbol = Symbol::new("123456");
        const _: Symbol = Symbol::new("1111111");
        const _: Symbol = Symbol::new("99999");
        const _: Symbol = Symbol::new("0000");
        const _: Symbol = Symbol::new("Example  ");
        const _: Symbol = Symbol::new("ABCDEF");
        const _: Symbol = Symbol::new("");

        const _: Symbol = Symbol::new("Protocol");
        const _: Symbol = Symbol::new("Attribute");
        const _: Symbol = Symbol::new("TypeName");
        const _: Symbol = Symbol::new("Name");
        const _: Symbol = Symbol::new("Field");
        const _: Symbol = Symbol::new("Variant");
        const _: Symbol = Symbol::new("Struct");
        const _: Symbol = Symbol::new("Module");
        const _: Symbol = Symbol::new("Enum");
        const _: Symbol = Symbol::new("Union");
        const _: Symbol = Symbol::new("Sequence");
        const _: Symbol = Symbol::new("Walker");
        const _: Symbol = Symbol::new("Builder");
        const _: Symbol = Symbol::new("Map");
        const _: Symbol = Symbol::new("Variable");

        const _: Symbol = Symbol::new("alksjdoiwsd");
        const _: Symbol = Symbol::new("2309ja");
        const _: Symbol = Symbol::new("SAF012");
    }

    #[test]
    fn alphabet() {
        // This test is special. It generates the model table from a set
        // of basic probability lists. If the table in the code is wrong
        // compared to the one generated then this test will print out
        // the correct table to be copy pasted into the code.

        let lower = HashMap::<char, f64>::from([
            ('e', 12.02),
            ('t', 9.10),
            ('a', 8.12),
            ('o', 7.68),
            ('i', 7.31),
            ('n', 6.95),
            ('s', 6.28),
            ('r', 6.02),
            ('h', 5.92),
            ('d', 4.32),
            ('l', 3.98),
            ('u', 2.88),
            ('c', 2.71),
            ('m', 2.71),
            ('f', 2.30),
            ('y', 2.11),
            ('w', 2.09),
            ('g', 2.03),
            ('p', 1.82),
            ('b', 1.49),
            ('v', 1.11),
            ('k', 0.69),
            ('x', 0.17),
            ('q', 0.11),
            ('j', 0.10),
            ('z', 0.07),
        ]);
        assert_eq!(lower.len(), 26);
        assert!((lower.iter().map(|(_, x)| x).sum::<f64>() - 100.0).abs() < 0.1);

        let upper = HashMap::<char, f64>::from([
            ('A', 5.64),
            ('B', 6.25),
            ('C', 9.44),
            ('D', 5.39),
            ('E', 3.42),
            ('F', 4.26),
            ('G', 3.58),
            ('H', 4.10),
            ('I', 3.22),
            ('J', 0.95),
            ('K', 1.32),
            ('L', 3.71),
            ('M', 5.71),
            ('N', 2.29),
            ('O', 2.70),
            ('P', 8.13),
            ('Q', 0.53),
            ('R', 4.49),
            ('S', 11.65),
            ('T', 5.52),
            ('U', 2.54),
            ('V', 1.58),
            ('W', 2.82),
            ('X', 0.09),
            ('Y', 0.38),
            ('Z', 0.27),
        ]);
        assert_eq!(upper.len(), 26);
        assert!((upper.iter().map(|(_, x)| x).sum::<f64>() - 100.0).abs() < 0.1);

        let digit = HashMap::<char, f64>::from([
            ('1', 30.1),
            ('2', 17.6),
            ('3', 12.5),
            ('4', 9.7),
            ('5', 7.9),
            ('6', 6.7),
            ('7', 5.8),
            ('8', 5.1),
            ('9', 3.6),
            ('0', 1.0),
        ]);
        assert_eq!(digit.len(), 10);
        assert!((digit.iter().map(|(_, x)| x).sum::<f64>() - 100.0).abs() < 0.1);

        let extra = HashMap::<char, f64>::from([(' ', 30.0), ('_', 60.0), ('-', 10.0)]);
        assert_eq!(extra.len(), 3);
        assert!((extra.iter().map(|(_, x)| x).sum::<f64>() - 100.0).abs() < 0.1);

        let all: HashMap<char, f64> = lower
            .iter()
            .map(|(c, f)| (*c, (f / 100.0) * 0.90))
            .chain(upper.iter().map(|(c, f)| (*c, (f / 100.0) * 0.025)))
            .chain(digit.iter().map(|(c, f)| (*c, (f / 100.0) * 0.0141)))
            .chain(extra.iter().map(|(c, f)| (*c, (f / 100.0) * 0.06)))
            // .chain([('\0', (0.07003f64 * 65536.0).round() as u64)])
            .collect();
        let mut all: Vec<_> = all.into_iter().collect();
        all.sort_by(|(a, _), (b, _)| a.cmp(b));
        assert_eq!(all.len(), 26 + 26 + 10 + 3);
        let diff = all.iter().map(|(_, x)| x).sum::<f64>() - 1.0;
        assert!(diff.abs() < 0.0001, "{}", diff);

        // This is how likely the end of the string is given the length.
        let scales: [f64; 18] = [
            0.0001, 0.001, 0.01, 0.023, 0.048, 0.074, 0.103, 0.135, 0.169, 0.207, 0.250, 0.298,
            0.353, 0.419, 0.500, 0.603, 0.750, 0.95,
        ];
        let mut totals = [0u64; 18];
        let with_len: Vec<(u8, [(u64, u64); 18])> = all
            .into_iter()
            .map(|(c, f)| {
                let mut lens = [(0, 0); 18];
                for j in 0..16 {
                    lens[j].0 = totals[j];
                    let f = ((f * (1.0 - scales[j])) * 65536.0).round() as u64;
                    lens[j].1 = f;
                    totals[j] += f;
                }
                (c as _, lens)
            })
            .collect();
        assert_eq!(with_len.len(), 26 + 26 + 10 + 3);

        // If the table in the code is wrong then print the right one and panic.
        if ALPHABET != with_len {
            eprintln!("const ALPHABET: &[(u8, [(u64, u64); 18])] = &[");
            for (c, table) in &with_len {
                use std::fmt::Write;
                let mut table_s = String::new();
                for (t, f) in table {
                    write!(table_s, "({},{}),", t, f).unwrap();
                }

                eprintln!("    (b{:?}, [{}]),", *c as char, table_s);
            }
            eprintln!("];");
            panic!("alphabet is wrong")
        }
    }
}

// This is the model used in the arithmetic coding.
#[rustfmt::skip]
const ALPHABET: &[(u8, [(u64, u64); 18])] = &[
    (b' ', [(0,1180),(0,1178),(0,1168),(0,1153),(0,1123),(0,1092),(0,1058),(0,1020),(0,980),(0,935),(0,885),(0,828),(0,763),(0,685),(0,590),(0,468),(0,0),(0,0),]),
    (b'-', [(1180,393),(1178,393),(1168,389),(1153,384),(1123,374),(1092,364),(1058,353),(1020,340),(980,327),(935,312),(885,295),(828,276),(763,254),(685,228),(590,197),(468,156),(0,0),(0,0),]),
    (b'0', [(1573,9),(1571,9),(1557,9),(1537,9),(1497,9),(1456,9),(1411,8),(1360,8),(1307,8),(1247,7),(1180,7),(1104,6),(1017,6),(913,5),(787,5),(624,4),(0,0),(0,0),]),
    (b'1', [(1582,278),(1580,278),(1566,275),(1546,272),(1506,265),(1465,258),(1419,249),(1368,241),(1315,231),(1254,221),(1187,209),(1110,195),(1023,180),(918,162),(792,139),(628,110),(0,0),(0,0),]),
    (b'2', [(1860,163),(1858,162),(1841,161),(1818,159),(1771,155),(1723,151),(1668,146),(1609,141),(1546,135),(1475,129),(1396,122),(1305,114),(1203,105),(1080,94),(931,81),(738,65),(0,0),(0,0),]),
    (b'3', [(2023,115),(2020,115),(2002,114),(1977,113),(1926,110),(1874,107),(1814,104),(1750,100),(1681,96),(1604,92),(1518,87),(1419,81),(1308,75),(1174,67),(1012,58),(803,46),(0,0),(0,0),]),
    (b'4', [(2138,90),(2135,90),(2116,89),(2090,88),(2036,85),(1981,83),(1918,80),(1850,78),(1777,74),(1696,71),(1605,67),(1500,63),(1383,58),(1241,52),(1070,45),(849,36),(0,0),(0,0),]),
    (b'5', [(2228,73),(2225,73),(2205,72),(2178,71),(2121,69),(2064,68),(1998,65),(1928,63),(1851,61),(1767,58),(1672,55),(1563,51),(1441,47),(1293,42),(1115,37),(885,29),(0,0),(0,0),]),
    (b'6', [(2301,62),(2298,62),(2277,61),(2249,60),(2190,59),(2132,57),(2063,56),(1991,54),(1912,51),(1825,49),(1727,46),(1614,43),(1488,40),(1335,36),(1152,31),(914,25),(0,0),(0,0),]),
    (b'7', [(2363,54),(2360,54),(2338,53),(2309,52),(2249,51),(2189,50),(2119,48),(2045,46),(1963,45),(1874,43),(1773,40),(1657,38),(1528,35),(1371,31),(1183,27),(939,21),(0,0),(0,0),]),
    (b'8', [(2417,47),(2414,47),(2391,47),(2361,46),(2300,45),(2239,44),(2167,42),(2091,41),(2008,39),(1917,37),(1813,35),(1695,33),(1563,30),(1402,27),(1210,24),(960,19),(0,0),(0,0),]),
    (b'9', [(2464,33),(2461,33),(2438,33),(2407,33),(2345,32),(2283,31),(2209,30),(2132,29),(2047,28),(1954,26),(1848,25),(1728,23),(1593,22),(1429,19),(1234,17),(979,13),(0,0),(0,0),]),
    (b'A', [(2497,92),(2494,92),(2471,91),(2440,90),(2377,88),(2314,86),(2239,83),(2161,80),(2075,77),(1980,73),(1873,69),(1751,65),(1615,60),(1448,54),(1251,46),(992,37),(0,0),(0,0),]),
    (b'B', [(2589,102),(2586,102),(2562,101),(2530,100),(2465,97),(2400,95),(2322,92),(2241,89),(2152,85),(2053,81),(1942,77),(1816,72),(1675,66),(1502,59),(1297,51),(1029,41),(0,0),(0,0),]),
    (b'C', [(2691,155),(2688,155),(2663,153),(2630,151),(2562,147),(2495,143),(2414,139),(2330,134),(2237,129),(2134,123),(2019,116),(1888,109),(1741,100),(1561,90),(1348,77),(1070,61),(0,0),(0,0),]),
    (b'D', [(2846,88),(2843,88),(2816,87),(2781,86),(2709,84),(2638,82),(2553,79),(2464,76),(2366,73),(2257,70),(2135,66),(1997,62),(1841,57),(1651,51),(1425,44),(1131,35),(0,0),(0,0),]),
    (b'E', [(2934,56),(2931,56),(2903,55),(2867,55),(2793,53),(2720,52),(2632,50),(2540,48),(2439,47),(2327,44),(2201,42),(2059,39),(1898,36),(1702,33),(1469,28),(1166,22),(0,0),(0,0),]),
    (b'F', [(2990,70),(2987,70),(2958,69),(2922,68),(2846,66),(2772,65),(2682,63),(2588,60),(2486,58),(2371,55),(2243,52),(2098,49),(1934,45),(1735,41),(1497,35),(1188,28),(0,0),(0,0),]),
    (b'G', [(3060,59),(3057,59),(3027,58),(2990,57),(2912,56),(2837,54),(2745,53),(2648,51),(2544,49),(2426,47),(2295,44),(2147,41),(1979,38),(1776,34),(1532,29),(1216,23),(0,0),(0,0),]),
    (b'H', [(3119,67),(3116,67),(3085,67),(3047,66),(2968,64),(2891,62),(2798,60),(2699,58),(2593,56),(2473,53),(2339,50),(2188,47),(2017,43),(1810,39),(1561,34),(1239,27),(0,0),(0,0),]),
    (b'I', [(3186,53),(3183,53),(3152,52),(3113,52),(3032,50),(2953,49),(2858,47),(2757,46),(2649,44),(2526,42),(2389,40),(2235,37),(2060,34),(1849,31),(1595,26),(1266,21),(0,0),(0,0),]),
    (b'J', [(3239,16),(3236,16),(3204,15),(3165,15),(3082,15),(3002,14),(2905,14),(2803,13),(2693,13),(2568,12),(2429,12),(2272,11),(2094,10),(1880,9),(1621,8),(1287,6),(0,0),(0,0),]),
    (b'K', [(3255,22),(3252,22),(3219,21),(3180,21),(3097,21),(3016,20),(2919,19),(2816,19),(2706,18),(2580,17),(2441,16),(2283,15),(2104,14),(1889,13),(1629,11),(1293,9),(0,0),(0,0),]),
    (b'L', [(3277,61),(3274,61),(3240,60),(3201,59),(3118,58),(3036,56),(2938,55),(2835,53),(2724,51),(2597,48),(2457,46),(2298,43),(2118,39),(1902,35),(1640,30),(1302,24),(0,0),(0,0),]),
    (b'M', [(3338,94),(3335,93),(3300,93),(3260,91),(3176,89),(3092,87),(2993,84),(2888,81),(2775,78),(2645,74),(2503,70),(2341,66),(2157,61),(1937,54),(1670,47),(1326,37),(0,0),(0,0),]),
    (b'N', [(3432,38),(3428,37),(3393,37),(3351,37),(3265,36),(3179,35),(3077,34),(2969,32),(2853,31),(2719,30),(2573,28),(2407,26),(2218,24),(1991,22),(1717,19),(1363,15),(0,0),(0,0),]),
    (b'O', [(3470,44),(3465,44),(3430,44),(3388,43),(3301,42),(3214,41),(3111,40),(3001,38),(2884,37),(2749,35),(2601,33),(2433,31),(2242,29),(2013,26),(1736,22),(1378,18),(0,0),(0,0),]),
    (b'P', [(3514,133),(3509,133),(3474,132),(3431,130),(3343,127),(3255,123),(3151,119),(3039,115),(2921,111),(2784,106),(2634,100),(2464,94),(2271,86),(2039,77),(1758,67),(1396,53),(0,0),(0,0),]),
    (b'Q', [(3647,9),(3642,9),(3606,9),(3561,8),(3470,8),(3378,8),(3270,8),(3154,8),(3032,7),(2890,7),(2734,7),(2558,6),(2357,6),(2116,5),(1825,4),(1449,3),(0,0),(0,0),]),
    (b'R', [(3656,74),(3651,73),(3615,73),(3569,72),(3478,70),(3386,68),(3278,66),(3162,64),(3039,61),(2897,58),(2741,55),(2564,52),(2363,48),(2121,43),(1829,37),(1452,29),(0,0),(0,0),]),
    (b'S', [(3730,191),(3724,191),(3688,189),(3641,186),(3548,182),(3454,177),(3344,171),(3226,165),(3100,159),(2955,151),(2796,143),(2616,134),(2411,123),(2164,111),(1866,95),(1481,76),(0,0),(0,0),]),
    (b'T', [(3921,90),(3915,90),(3877,90),(3827,88),(3730,86),(3631,84),(3515,81),(3391,78),(3259,75),(3106,72),(2939,68),(2750,63),(2534,59),(2275,53),(1961,45),(1557,36),(0,0),(0,0),]),
    (b'U', [(4011,42),(4005,42),(3967,41),(3915,41),(3816,40),(3715,39),(3596,37),(3469,36),(3334,35),(3178,33),(3007,31),(2813,29),(2593,27),(2328,24),(2006,21),(1593,17),(0,0),(0,0),]),
    (b'V', [(4053,26),(4047,26),(4008,26),(3956,25),(3856,25),(3754,24),(3633,23),(3505,22),(3369,22),(3211,21),(3038,19),(2842,18),(2620,17),(2352,15),(2027,13),(1610,10),(0,0),(0,0),]),
    (b'W', [(4079,46),(4073,46),(4034,46),(3981,45),(3881,44),(3778,43),(3656,41),(3527,40),(3391,38),(3232,37),(3057,35),(2860,32),(2637,30),(2367,27),(2040,23),(1620,18),(0,0),(0,0),]),
    (b'X', [(4125,1),(4119,1),(4080,1),(4026,1),(3925,1),(3821,1),(3697,1),(3567,1),(3429,1),(3269,1),(3092,1),(2892,1),(2667,1),(2394,1),(2063,1),(1638,1),(0,0),(0,0),]),
    (b'Y', [(4126,6),(4120,6),(4081,6),(4027,6),(3926,6),(3822,6),(3698,6),(3568,5),(3430,5),(3270,5),(3093,5),(2893,4),(2668,4),(2395,4),(2064,3),(1639,2),(0,0),(0,0),]),
    (b'Z', [(4132,4),(4126,4),(4087,4),(4033,4),(3932,4),(3828,4),(3704,4),(3573,4),(3435,4),(3275,4),(3098,3),(2897,3),(2672,3),(2399,3),(2067,2),(1641,2),(0,0),(0,0),]),
    (b'_', [(4136,2359),(4130,2357),(4091,2336),(4037,2305),(3936,2246),(3832,2185),(3708,2116),(3577,2041),(3439,1961),(3279,1871),(3101,1769),(2900,1656),(2675,1526),(2402,1371),(2069,1180),(1643,937),(0,0),(0,0),]),
    (b'a', [(6495,4789),(6487,4785),(6427,4741),(6342,4679),(6182,4559),(6017,4435),(5824,4296),(5618,4143),(5400,3980),(5150,3798),(4870,3592),(4556,3362),(4201,3099),(3773,2783),(3249,2395),(2580,1901),(0,0),(0,0),]),
    (b'b', [(11284,879),(11272,878),(11168,870),(11021,859),(10741,837),(10452,814),(10120,788),(9761,760),(9380,730),(8948,697),(8462,659),(7918,617),(7300,569),(6556,511),(5644,439),(4481,349),(0,0),(0,0),]),
    (b'c', [(12163,1598),(12150,1597),(12038,1582),(11880,1562),(11578,1522),(11266,1480),(10908,1434),(10521,1383),(10110,1328),(9645,1268),(9121,1199),(8535,1122),(7869,1034),(7067,929),(6083,799),(4830,635),(0,0),(0,0),]),
    (b'd', [(13761,2548),(13747,2545),(13620,2523),(13442,2489),(13100,2426),(12746,2359),(12342,2286),(11904,2204),(11438,2117),(10913,2021),(10320,1911),(9657,1789),(8903,1649),(7996,1480),(6882,1274),(5465,1012),(0,0),(0,0),]),
    (b'e', [(16309,7089),(16292,7083),(16143,7019),(15931,6927),(15526,6749),(15105,6565),(14628,6359),(14108,6133),(13555,5892),(12934,5622),(12231,5317),(11446,4977),(10552,4587),(9476,4119),(8156,3545),(6477,2815),(0,0),(0,0),]),
    (b'f', [(23398,1356),(23375,1355),(23162,1343),(22858,1325),(22275,1291),(21670,1256),(20987,1217),(20241,1173),(19447,1127),(18556,1076),(17548,1017),(16423,952),(15139,878),(13595,788),(11701,678),(9292,539),(0,0),(0,0),]),
    (b'g', [(24754,1197),(24730,1196),(24505,1185),(24183,1170),(23566,1140),(22926,1109),(22204,1074),(21414,1036),(20574,995),(19632,949),(18565,898),(17375,841),(16017,775),(14383,696),(12379,599),(9831,475),(0,0),(0,0),]),
    (b'h', [(25951,3491),(25926,3488),(25690,3457),(25353,3411),(24706,3324),(24035,3233),(23278,3132),(22450,3020),(21569,2902),(20581,2769),(19463,2619),(18216,2451),(16792,2259),(15079,2029),(12978,1746),(10306,1386),(0,0),(0,0),]),
    (b'i', [(29442,4311),(29414,4307),(29147,4268),(28764,4212),(28030,4105),(27268,3993),(26410,3868),(25470,3730),(24471,3583),(23350,3419),(22082,3234),(20667,3027),(19051,2790),(17108,2505),(14724,2156),(11692,1712),(0,0),(0,0),]),
    (b'j', [(33753,59),(33721,59),(33415,58),(32976,58),(32135,56),(31261,55),(30278,53),(29200,51),(28054,49),(26769,47),(25316,44),(23694,41),(21841,38),(19613,34),(16880,29),(13404,23),(0,0),(0,0),]),
    (b'k', [(33812,407),(33780,407),(33473,403),(33034,398),(32191,387),(31316,377),(30331,365),(29251,352),(28103,338),(26816,323),(25360,305),(23735,286),(21879,263),(19647,236),(16909,203),(13427,162),(0,0),(0,0),]),
    (b'l', [(34219,2347),(34187,2345),(33876,2324),(33432,2294),(32578,2235),(31693,2174),(30696,2106),(29603,2031),(28441,1951),(27139,1862),(25665,1761),(24021,1648),(22142,1519),(19883,1364),(17112,1174),(13589,932),(0,0),(0,0),]),
    (b'm', [(36566,1598),(36532,1597),(36200,1582),(35726,1562),(34813,1522),(33867,1480),(32802,1434),(31634,1383),(30392,1328),(29001,1268),(27426,1199),(25669,1122),(23661,1034),(21247,929),(18286,799),(14521,635),(0,0),(0,0),]),
    (b'n', [(38164,4099),(38129,4095),(37782,4058),(37288,4005),(36335,3903),(35347,3796),(34236,3677),(33017,3546),(31720,3406),(30269,3251),(28625,3074),(26791,2878),(24695,2652),(22176,2382),(19085,2050),(15156,1627),(0,0),(0,0),]),
    (b'o', [(42263,4529),(42224,4525),(41840,4485),(41293,4426),(40238,4312),(39143,4195),(37913,4063),(36563,3918),(35126,3764),(33520,3592),(31699,3397),(29669,3180),(27347,2931),(24558,2632),(21135,2265),(16783,1798),(0,0),(0,0),]),
    (b'p', [(46792,1073),(46749,1072),(46325,1063),(45719,1049),(44550,1022),(43338,994),(41976,963),(40481,929),(38890,892),(37112,851),(35096,805),(32849,754),(30278,695),(27190,624),(23400,537),(18581,426),(0,0),(0,0),]),
    (b'q', [(47865,65),(47821,65),(47388,64),(46768,63),(45572,62),(44332,60),(42939,58),(41410,56),(39782,54),(37963,51),(35901,49),(33603,46),(30973,42),(27814,38),(23937,32),(19007,26),(0,0),(0,0),]),
    (b'r', [(47930,3550),(47886,3547),(47452,3515),(46831,3469),(45634,3380),(44392,3288),(42997,3185),(41466,3071),(39836,2951),(38014,2816),(35950,2663),(33649,2493),(31015,2297),(27852,2063),(23969,1775),(19033,1410),(0,0),(0,0),]),
    (b's', [(51480,3704),(51433,3700),(50967,3667),(50300,3619),(49014,3526),(47680,3430),(46182,3323),(44537,3204),(42787,3078),(40830,2937),(38613,2778),(36142,2600),(33312,2397),(29915,2152),(25744,1852),(20443,1471),(0,0),(0,0),]),
    (b't', [(55184,5367),(55133,5362),(54634,5314),(53919,5244),(52540,5110),(51110,4970),(49505,4815),(47741,4643),(45865,4460),(43767,4256),(41391,4026),(38742,3768),(35709,3473),(32067,3118),(27596,2684),(21914,2131),(0,0),(0,0),]),
    (b'u', [(60551,1699),(60495,1697),(59948,1682),(59163,1660),(57650,1617),(56080,1573),(54320,1524),(52384,1469),(50325,1412),(48023,1347),(45417,1274),(42510,1192),(39182,1099),(35185,987),(30280,849),(24045,674),(0,0),(0,0),]),
    (b'v', [(62250,655),(62192,654),(61630,648),(60823,640),(59267,623),(57653,606),(55844,587),(53853,566),(51737,544),(49370,519),(46691,491),(43702,460),(40281,424),(36172,380),(31129,327),(24719,260),(0,0),(0,0),]),
    (b'w', [(62905,1233),(62846,1231),(62278,1220),(61463,1204),(59890,1174),(58259,1142),(56431,1106),(54419,1066),(52281,1024),(49889,978),(47182,925),(44162,865),(40705,798),(36552,716),(31456,616),(24979,489),(0,0),(0,0),]),
    (b'x', [(64138,100),(64077,100),(63498,99),(62667,98),(61064,95),(59401,93),(57537,90),(55485,87),(53305,83),(50867,80),(48107,75),(45027,70),(41503,65),(37268,58),(32072,50),(25468,40),(0,0),(0,0),]),
    (b'y', [(64238,1244),(64177,1243),(63597,1232),(62765,1216),(61159,1185),(59494,1152),(57627,1116),(55572,1077),(53388,1034),(50947,987),(48182,933),(45097,874),(41568,805),(37326,723),(32122,622),(25508,494),(0,0),(0,0),]),
    (b'z', [(65482,41),(65420,41),(64829,41),(63981,40),(62344,39),(60646,38),(58743,37),(56649,36),(54422,34),(51934,33),(49115,31),(45971,29),(42373,27),(38049,24),(32744,21),(26002,16),(0,0),(0,0),]),
];