pub fn ones(n: u16) -> u128 {
    0_u128.wrapping_sub(1) >> (128 - n)
}

pub fn parse_int(s: &str) -> Result<u128, core::num::ParseIntError> {
    let mut chars = s.chars();

    if chars.next() == Some('0') {
        if chars.next() == Some('x') {
            let res = chars.collect::<String>();
            return u128::from_str_radix(&res, 16);
        } else if chars.next().is_some() {
            panic!("other bases not supported");
        }
    }

    let signed: i128 = s.parse()?;

    Ok(signed as _)
}

pub fn reverse(mut x: u128, n: u16) -> u128 {
    match n {
        1 => x & 1,
        2 => ((x >> 1) & 1) + ((x << 1) & 2),
        3..=4 => {
            x = ((x >> 2) & 3) + ((x << 2) & 0xc);
            x = ((x >> 1) & 5) + ((x << 1) & 0xa);
            x >> (4 - n)
        }
        5..=8 => {
            x = ((x >> 4) & 0x0f) + ((x << 4) & 0xf0);
            x = ((x >> 2) & 0x33) + ((x << 2) & 0xcc);
            x = ((x >> 1) & 0x55) + ((x << 1) & 0xaa);
            x >> (8 - n)
        }
        9..=16 => {
            x = ((x >> 8) & 0x00ff) + ((x << 8) & 0xff00);
            x = ((x >> 4) & 0x0f0f) + ((x << 4) & 0xf0f0);
            x = ((x >> 2) & 0x3333) + ((x << 2) & 0xcccc);
            x = ((x >> 1) & 0x5555) + ((x << 1) & 0xaaaa);
            x >> (16 - n)
        }
        17..=32 => {
            x = ((x >> 16) & 0x0000ffff) + ((x << 16) & 0xffff0000);
            x = ((x >> 8) & 0x00ff00ff) + ((x << 8) & 0xff00ff00);
            x = ((x >> 4) & 0x0f0f0f0f) + ((x << 4) & 0xf0f0f0f0);
            x = ((x >> 2) & 0x33333333) + ((x << 2) & 0xcccccccc);
            x = ((x >> 1) & 0x55555555) + ((x << 1) & 0xaaaaaaaa);
            x >> (32 - n)
        }
        33..=64 => {
            x = ((x >> 32) & 0x00000000ffffffff) + ((x << 32) & 0xffffffff00000000);
            x = ((x >> 16) & 0x0000ffff0000ffff) + ((x << 16) & 0xffff0000ffff0000);
            x = ((x >> 8) & 0x00ff00ff00ff00ff) + ((x << 8) & 0xff00ff00ff00ff00);
            x = ((x >> 4) & 0x0f0f0f0f0f0f0f0f) + ((x << 4) & 0xf0f0f0f0f0f0f0f0);
            x = ((x >> 2) & 0x3333333333333333) + ((x << 2) & 0xcccccccccccccccc);
            x = ((x >> 1) & 0x5555555555555555) + ((x << 1) & 0xaaaaaaaaaaaaaaaa);
            x >> (64 - n)
        }
        65..=128 => {
            let hi = reverse(x, 64) << (n - 64);
            let lo = reverse(x >> 64, n - 64);
            lo | hi
        }
        _ => panic!("Bitwidth must be less than 128!"),
    }
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn reverse_one_bit() {
        assert_eq!(0, reverse(0, 1));
        assert_eq!(1, reverse(1, 1));
    }

    #[test]
    fn reverse_two_bits() {
        assert_eq!(0b00, reverse(0b00, 2));
        assert_eq!(0b10, reverse(0b01, 2));
        assert_eq!(0b01, reverse(0b10, 2));
        assert_eq!(0b11, reverse(0b11, 2));
    }

    #[test]
    fn reverse_three_bits() {
        assert_eq!(0b000, reverse(0b000, 3));
        assert_eq!(0b100, reverse(0b001, 3));
        assert_eq!(0b010, reverse(0b010, 3));
        assert_eq!(0b110, reverse(0b011, 3));
        assert_eq!(0b001, reverse(0b100, 3));
        assert_eq!(0b101, reverse(0b101, 3));
        assert_eq!(0b011, reverse(0b110, 3));
        assert_eq!(0b111, reverse(0b111, 3));
    }

    #[test]
    fn reverse_four_bits() {
        assert_eq!(0b0000, reverse(0b0000, 4));
        assert_eq!(0b1000, reverse(0b0001, 4));
        assert_eq!(0b0100, reverse(0b0010, 4));
        assert_eq!(0b1100, reverse(0b0011, 4));
        assert_eq!(0b0010, reverse(0b0100, 4));
        assert_eq!(0b1010, reverse(0b0101, 4));
        assert_eq!(0b0110, reverse(0b0110, 4));
        assert_eq!(0b1110, reverse(0b0111, 4));
        assert_eq!(0b0001, reverse(0b1000, 4));
        assert_eq!(0b1001, reverse(0b1001, 4));
        assert_eq!(0b0101, reverse(0b1010, 4));
        assert_eq!(0b1101, reverse(0b1011, 4));
        assert_eq!(0b0011, reverse(0b1100, 4));
        assert_eq!(0b1011, reverse(0b1101, 4));
        assert_eq!(0b0111, reverse(0b1110, 4));
        assert_eq!(0b1111, reverse(0b1111, 4));
    }

    #[test]
    fn reverse_five_bits() {
        assert_eq!(0b10101, reverse(0b10101, 5));
        assert_eq!(0b10100, reverse(0b00101, 5));
        assert_eq!(0b00101, reverse(0b10100, 5));
        assert_eq!(0b10001, reverse(0b10001, 5));
        assert_eq!(0b11101, reverse(0b10111, 5));
        assert_eq!(0b10111, reverse(0b11101, 5));
    }

    #[test]
    fn reverse_six_bits() {
        assert_eq!(0b010101, reverse(0b101010, 6));
        assert_eq!(0b010100, reverse(0b001010, 6));
        assert_eq!(0b000101, reverse(0b101000, 6));
        assert_eq!(0b100010, reverse(0b010001, 6));
        assert_eq!(0b111010, reverse(0b010111, 6));
        assert_eq!(0b101110, reverse(0b011101, 6));
    }

    #[test]
    fn reverse_seven_bits() {
        assert_eq!(0b0010101, reverse(0b1010100, 7));
        assert_eq!(0b0010100, reverse(0b0010100, 7));
        assert_eq!(0b1000101, reverse(0b1010001, 7));
        assert_eq!(0b1100010, reverse(0b0100011, 7));
        assert_eq!(0b1110100, reverse(0b0010111, 7));
        assert_eq!(0b1011100, reverse(0b0011101, 7));
    }

    #[test]
    fn reverse_eight_bits() {
        assert_eq!(0b00010101, reverse(0b10101000, 8));
        assert_eq!(0b10010100, reverse(0b00101001, 8));
        assert_eq!(0b01000101, reverse(0b10100010, 8));
        assert_eq!(0b11100010, reverse(0b01000111, 8));
        assert_eq!(0b01110100, reverse(0b00101110, 8));
        assert_eq!(0b11011100, reverse(0b00111011, 8));
    }

    #[test]
    fn reverse_nine_bits() {
        assert_eq!(0b000101011, reverse(0b110101000, 9));
        assert_eq!(0b100101001, reverse(0b100101001, 9));
        assert_eq!(0b010001011, reverse(0b110100010, 9));
        assert_eq!(0b111000101, reverse(0b101000111, 9));
        assert_eq!(0b011101001, reverse(0b100101110, 9));
        assert_eq!(0b110111001, reverse(0b100111011, 9));
    }

    #[test]
    fn reverse_sixteen_bits() {
        assert_eq!(0b1000010101110101, reverse(0b1010111010100001, 16));
        assert_eq!(0b1010010100110101, reverse(0b1010110010100101, 16));
        assert_eq!(0b1001000101110101, reverse(0b1010111010001001, 16));
        assert_eq!(0b1011100010110101, reverse(0b1010110100011101, 16));
        assert_eq!(0b1001110100110101, reverse(0b1010110010111001, 16));
        assert_eq!(0b1011011100110101, reverse(0b1010110011101101, 16));
    }

    #[test]
    fn reverse_seventeen_bits() {
        assert_eq!(0b10100010101110101, reverse(0b10101110101000101, 17));
        assert_eq!(0b10010010100110101, reverse(0b10101100101001001, 17));
        assert_eq!(0b10101000101110101, reverse(0b10101110100010101, 17));
        assert_eq!(0b10011100010110101, reverse(0b10101101000111001, 17));
        assert_eq!(0b10101110100110101, reverse(0b10101100101110101, 17));
        assert_eq!(0b10011011100110101, reverse(0b10101100111011001, 17));
    }

    #[test]
    fn reverse_thirty_two_bits() {
        assert_eq!(
            0b01000101011101011000010101110101,
            reverse(0b10101110101000011010111010100010, 32)
        );
        assert_eq!(
            0b10100101001101011010010100110101,
            reverse(0b10101100101001011010110010100101, 32)
        );
        assert_eq!(
            0b01010001011101011001000101110101,
            reverse(0b10101110100010011010111010001010, 32)
        );
        assert_eq!(
            0b10111000101101011011100010110101,
            reverse(0b10101101000111011010110100011101, 32)
        );
        assert_eq!(
            0b01011101001101011001110100110101,
            reverse(0b10101100101110011010110010111010, 32)
        );
        assert_eq!(
            0b10110111001101011011011100110101,
            reverse(0b10101100111011011010110011101101, 32)
        );
    }

    #[test]
    fn reverse_thirty_three_bits() {
        assert_eq!(
            0b101000101011101011000010101110101,
            reverse(0b101011101010000110101110101000101, 33)
        );
        assert_eq!(
            0b010100101001101011010010100110101,
            reverse(0b101011001010010110101100101001010, 33)
        );
        assert_eq!(
            0b101010001011101011001000101110101,
            reverse(0b101011101000100110101110100010101, 33)
        );
        assert_eq!(
            0b010111000101101011011100010110101,
            reverse(0b101011010001110110101101000111010, 33)
        );
        assert_eq!(
            0b101011101001101011001110100110101,
            reverse(0b101011001011100110101100101110101, 33)
        );
        assert_eq!(
            0b010110111001101011011011100110101,
            reverse(0b101011001110110110101100111011010, 33)
        );
    }

    #[test]
    fn reverse_sixty_four_bits() {
        assert_eq!(0xf0f0f0f0f0f0f0f0, reverse(0x0f0f0f0f0f0f0f0f, 64));
        assert_eq!(0x3535353535353535, reverse(0xacacacacacacacac, 64));
    }

    #[test]
    fn reverse_sixty_five_bits() {
        assert_eq!(0x10000000000000000, reverse(1, 65));
        assert_eq!(0x1f0f0f0f0f0f0f0f0, reverse(0x01e1e1e1e1e1e1e1f, 65));
    }

    #[test]
    fn reverse_one_hundred_twenty_eight_bits() {
        assert_eq!(0x80000000000000000000000000000000, reverse(1, 128));
        assert_eq!(
            0xf0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0,
            reverse(0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f, 128)
        );
        assert_eq!(
            0x35353535353535353535353535353535,
            reverse(0xacacacacacacacacacacacacacacacac, 128)
        );
    }

    #[test]
    fn parse_int_dec() {
        assert_eq!(Ok(42), parse_int("42"));
    }

    #[test]
    fn parse_int_hex() {
        assert_eq!(Ok(42), parse_int("0x2a"));
    }
}