bitcoin-internals 0.7.0

// SPDX-License-Identifier: CC0-1.0

//! Unsigned 256-bit integer type.
//!
//! This type is an internal implementation detail used by crates in the rust-bitcoin ecosystem
//! (e.g. to implement the proof-of-work `Target` and `Work` types). It is not intended to be part
//! of the public API of any downstream crate.

use core::fmt::{self, Write as _};
use core::ops::{Add, Div, Mul, Not, Rem, Shl, Shr, Sub};

/// Big-endian 256 bit integer type.
// (high, low): u.0 contains the high bits, u.1 contains the low bits.
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
pub struct U256(u128, u128);

impl U256 {
    /// The maximum value of a `U256`.
    pub const MAX: Self =
        Self(0xffff_ffff_ffff_ffff_ffff_ffff_ffff_ffff, 0xffff_ffff_ffff_ffff_ffff_ffff_ffff_ffff);

    /// The value zero.
    pub const ZERO: Self = Self(0, 0);

    /// The value one.
    pub const ONE: Self = Self(0, 1);

    /// Constructs a new `U256` from its big-endian `high` and `low` 128-bit halves.
    #[must_use]
    pub const fn new(high: u128, low: u128) -> Self { Self(high, low) }

    /// Constructs a new `U256` from a big-endian array of `u8`s.
    pub fn from_be_bytes(a: [u8; 32]) -> Self {
        let (high, low) = split_in_half(a);
        let big = u128::from_be_bytes(high);
        let little = u128::from_be_bytes(low);
        Self(big, little)
    }

    /// Constructs a new `U256` from a little-endian array of `u8`s.
    pub fn from_le_bytes(a: [u8; 32]) -> Self {
        let (high, low) = split_in_half(a);
        let little = u128::from_le_bytes(high);
        let big = u128::from_le_bytes(low);
        Self(big, little)
    }

    /// Converts `U256` to a big-endian array of `u8`s.
    pub fn to_be_bytes(self) -> [u8; 32] {
        let mut out = [0; 32];
        out[..16].copy_from_slice(&self.0.to_be_bytes());
        out[16..].copy_from_slice(&self.1.to_be_bytes());
        out
    }

    /// Converts `U256` to a little-endian array of `u8`s.
    pub fn to_le_bytes(self) -> [u8; 32] {
        let mut out = [0; 32];
        out[..16].copy_from_slice(&self.1.to_le_bytes());
        out[16..].copy_from_slice(&self.0.to_le_bytes());
        out
    }

    /// Calculates 2^256 / (x + 1) where x is a 256 bit unsigned integer.
    ///
    /// ref: <https://github.com/bitcoin/bitcoin/blob/5fe753b56f450b054c42227c5df8346c72447490/src/chain.cpp#L133>
    ///
    /// 2**256 / (x + 1) == ~x / (x + 1) + 1
    ///
    /// (Equation shamelessly stolen from bitcoind)
    #[must_use]
    pub fn inverse(&self) -> Self {
        // We should never have a target/work of zero so this doesn't matter
        // that much but we define the inverse of 0 as max.
        if self.is_zero() {
            return Self::MAX;
        }
        // We define the inverse of 1 as max.
        if self.is_one() {
            return Self::MAX;
        }
        // We define the inverse of max as 1.
        if self.is_max() {
            return Self::ONE;
        }

        let ret = !*self / self.wrapping_inc();
        ret.wrapping_inc()
    }

    fn is_zero(&self) -> bool { self.0 == 0 && self.1 == 0 }

    fn is_one(&self) -> bool { self.0 == 0 && self.1 == 1 }

    /// Returns true if `self` is equal to [`U256::MAX`].
    pub fn is_max(&self) -> bool { self.0 == u128::MAX && self.1 == u128::MAX }

    /// Returns the low 32 bits.
    pub fn low_u32(&self) -> u32 { self.low_u128() as u32 }

    /// Returns the low 64 bits.
    pub fn low_u64(&self) -> u64 { self.low_u128() as u64 }

    /// Returns the low 128 bits.
    fn low_u128(&self) -> u128 { self.1 }

    /// Returns this `U256` as a `u128` saturating to `u128::MAX` if `self` is too big.
    // Mutagen gives false positive because >= and > both return u128::MAX
    pub fn saturating_to_u128(&self) -> u128 {
        if *self > Self::from(u128::MAX) {
            u128::MAX
        } else {
            self.low_u128()
        }
    }

    /// Returns the least number of bits needed to represent the number.
    pub fn bits(&self) -> u32 {
        if self.0 > 0 {
            256 - self.0.leading_zeros()
        } else {
            128 - self.1.leading_zeros()
        }
    }

    /// Wrapping multiplication by `u64`.
    ///
    /// # Returns
    ///
    /// The multiplication result along with a boolean indicating whether an arithmetic overflow
    /// occurred. If an overflow occurred then the wrapped value is returned.
    pub fn mul_u64(self, rhs: u64) -> (Self, bool) {
        let mut carry: u128 = 0;
        let mut split_le =
            [self.1 as u64, (self.1 >> 64) as u64, self.0 as u64, (self.0 >> 64) as u64];

        for word in &mut split_le {
            // This will not overflow, for proof see https://github.com/rust-bitcoin/rust-bitcoin/pull/1496#issuecomment-1365938572
            let n = carry + u128::from(rhs) * u128::from(*word);

            *word = n as u64; // Intentional truncation, save the low bits
            carry = n >> 64; // and carry the high bits.
        }

        let low = u128::from(split_le[0]) | (u128::from(split_le[1]) << 64);
        let high = u128::from(split_le[2]) | (u128::from(split_le[3]) << 64);
        (Self(high, low), carry != 0)
    }

    /// Calculates quotient and remainder.
    ///
    /// # Returns
    ///
    /// (quotient, remainder)
    ///
    /// # Panics
    ///
    /// If `rhs` is zero.
    #[allow(clippy::indexing_slicing)]
    fn div_rem(self, rhs: Self) -> (Self, Self) {
        let mut sub_copy = self;
        let mut shift_copy = rhs;
        let mut ret = [0u128; 2];

        let my_bits = self.bits();
        let your_bits = rhs.bits();

        // Check for division by 0
        assert!(your_bits != 0, "attempted to divide {} by zero", self);

        // Early return in case we are dividing by a larger number than us
        if my_bits < your_bits {
            return (Self::ZERO, sub_copy);
        }

        // Bitwise long division
        let mut shift = my_bits - your_bits;
        shift_copy = shift_copy << shift;
        loop {
            if sub_copy >= shift_copy {
                ret[1 - (shift / 128) as usize] |= 1 << (shift % 128);
                sub_copy = sub_copy.wrapping_sub(shift_copy);
            }
            shift_copy = shift_copy >> 1;
            if shift == 0 {
                break;
            }
            shift -= 1;
        }

        (Self(ret[0], ret[1]), sub_copy)
    }

    /// Calculates `self` + `rhs`
    ///
    /// Returns a tuple of the addition along with a boolean indicating whether an arithmetic
    /// overflow would occur. If an overflow would have occurred then the wrapped value is returned.
    #[must_use = "this returns the result of the operation, without modifying the original"]
    pub fn overflowing_add(self, rhs: Self) -> (Self, bool) {
        let mut ret = Self::ZERO;
        let mut ret_overflow = false;

        let (high, overflow) = self.0.overflowing_add(rhs.0);
        ret.0 = high;
        ret_overflow |= overflow;

        let (low, overflow) = self.1.overflowing_add(rhs.1);
        ret.1 = low;
        if overflow {
            let (high, overflow) = ret.0.overflowing_add(1);
            ret.0 = high;
            ret_overflow |= overflow;
        }

        (ret, ret_overflow)
    }

    /// Calculates `self` - `rhs`
    ///
    /// Returns a tuple of the subtraction along with a boolean indicating whether an arithmetic
    /// overflow would occur. If an overflow would have occurred then the wrapped value is returned.
    #[must_use = "this returns the result of the operation, without modifying the original"]
    pub fn overflowing_sub(self, rhs: Self) -> (Self, bool) {
        let ret = self.wrapping_add(!rhs).wrapping_add(Self::ONE);
        let overflow = rhs > self;
        (ret, overflow)
    }

    /// Calculates the multiplication of `self` and `rhs`.
    ///
    /// Returns a tuple of the multiplication along with a boolean
    /// indicating whether an arithmetic overflow would occur. If an
    /// overflow would have occurred then the wrapped value is returned.
    #[must_use = "this returns the result of the operation, without modifying the original"]
    pub fn overflowing_mul(self, rhs: Self) -> (Self, bool) {
        let mut ret = Self::ZERO;
        let mut ret_overflow = false;

        for i in 0..=3 {
            let to_mul = (rhs >> (64 * i)).low_u64();
            let (mul_res, overflow) = self.mul_u64(to_mul);
            ret_overflow |= overflow; // If multiplying lhs by the u64 overflowed, that's an overflow

            // Calculate the bits that will overflow during the shift below.
            let overflow_bits = if i > 0 { mul_res >> (256 - (64 * i)) } else { Self::ZERO };
            ret_overflow |= overflow_bits > Self::ZERO; // If there are bits that will be shifted out below, that's an overflow

            let (sum, overflow) = ret.overflowing_add(mul_res << (64 * i));
            ret = sum;
            ret_overflow |= overflow; // If adding the mul_u64 result overflowed, that's an overflow
        }

        (ret, ret_overflow)
    }

    /// Wrapping (modular) addition. Computes `self + rhs`, wrapping around at the boundary of the
    /// type.
    #[must_use = "this returns the result of the operation, without modifying the original"]
    pub fn wrapping_add(self, rhs: Self) -> Self {
        let (ret, _overflow) = self.overflowing_add(rhs);
        ret
    }

    /// Wrapping (modular) subtraction. Computes `self - rhs`, wrapping around at the boundary of
    /// the type.
    #[must_use = "this returns the result of the operation, without modifying the original"]
    pub fn wrapping_sub(self, rhs: Self) -> Self {
        let (ret, _overflow) = self.overflowing_sub(rhs);
        ret
    }

    /// Wrapping (modular) multiplication. Computes `self * rhs`, wrapping around at the boundary
    /// of the type.
    #[must_use = "this returns the result of the operation, without modifying the original"]
    pub fn wrapping_mul(self, rhs: Self) -> Self {
        let (ret, _overflow) = self.overflowing_mul(rhs);
        ret
    }

    /// Returns `self` incremented by 1 wrapping around at the boundary of the type.
    #[must_use = "this returns the result of the increment, without modifying the original"]
    pub fn wrapping_inc(&self) -> Self {
        let mut ret = Self::ZERO;

        ret.1 = self.1.wrapping_add(1);
        if ret.1 == 0 {
            ret.0 = self.0.wrapping_add(1);
        } else {
            ret.0 = self.0;
        }
        ret
    }

    /// Panic-free bitwise shift-left; yields `self << mask(rhs)`, where `mask` removes any
    /// high-order bits of `rhs` that would cause the shift to exceed the bitwidth of the type.
    ///
    /// Note that this is *not* the same as a rotate-left; the RHS of a wrapping shift-left is
    /// restricted to the range of the type, rather than the bits shifted out of the LHS being
    /// returned to the other end. We do not currently support `rotate_left`.
    #[must_use = "this returns the result of the operation, without modifying the original"]
    fn wrapping_shl(self, rhs: u32) -> Self {
        let shift = rhs & 0x0000_00ff;

        let mut ret = Self::ZERO;
        let word_shift = shift >= 128;
        let bit_shift = shift % 128;

        if word_shift {
            ret.0 = self.1 << bit_shift;
        } else {
            ret.0 = self.0 << bit_shift;
            if bit_shift > 0 {
                ret.0 += self.1.wrapping_shr(128 - bit_shift);
            }
            ret.1 = self.1 << bit_shift;
        }
        ret
    }

    /// Panic-free bitwise shift-right; yields `self >> mask(rhs)`, where `mask` removes any
    /// high-order bits of `rhs` that would cause the shift to exceed the bitwidth of the type.
    ///
    /// Note that this is *not* the same as a rotate-right; the RHS of a wrapping shift-right is
    /// restricted to the range of the type, rather than the bits shifted out of the LHS being
    /// returned to the other end. We do not currently support `rotate_right`.
    #[must_use = "this returns the result of the operation, without modifying the original"]
    fn wrapping_shr(self, rhs: u32) -> Self {
        let shift = rhs & 0x0000_00ff;

        let mut ret = Self::ZERO;
        let word_shift = shift >= 128;
        let bit_shift = shift % 128;

        if word_shift {
            ret.1 = self.0 >> bit_shift;
        } else {
            ret.0 = self.0 >> bit_shift;
            ret.1 = self.1 >> bit_shift;
            if bit_shift > 0 {
                ret.1 += self.0.wrapping_shl(128 - bit_shift);
            }
        }
        ret
    }

    /// Format `self` to `f` as a decimal when value is known to be non-zero.
    #[allow(clippy::indexing_slicing)]
    fn fmt_decimal(&self, f: &mut fmt::Formatter) -> fmt::Result {
        const DIGITS: usize = 78; // U256::MAX has 78 base 10 digits.
        const TEN: U256 = U256(0, 10);

        let mut buf = [0_u8; DIGITS];
        let mut i = DIGITS - 1; // We loop backwards.
        let mut cur = *self;

        loop {
            let digit = (cur % TEN).low_u128() as u8; // Cast after rem 10 is lossless.
            buf[i] = digit + b'0';
            cur = cur / TEN;
            if cur.is_zero() {
                break;
            }
            i -= 1;
        }
        let s = core::str::from_utf8(&buf[i..]).expect("digits 0-9 are valid UTF8");
        f.pad_integral(true, "", s)
    }

    /// Converts self to f64.
    #[inline]
    pub fn to_f64(self) -> f64 {
        // Reference: https://blog.m-ou.se/floats/
        // Step 1: Get leading zeroes
        let leading_zeroes = 256 - self.bits();
        // Step 2: Get msb to be farthest left bit
        let left_aligned = self.wrapping_shl(leading_zeroes);
        // Step 3: Shift msb to fit in lower 53 bits (128-53=75) to get the mantissa
        // * Shifting the border of the 2 u128s to line up with mantissa and dropped bits
        let middle_aligned = left_aligned >> 75;
        // * This is the 53 most significant bits as u128
        let mantissa = middle_aligned.0;
        // Step 4: Dropped bits (except for last 75 bits) are all in the second u128.
        // Bitwise OR the rest of the bits into it, preserving the highest bit,
        // so we take the lower 75 bits of middle_aligned.1 and mix it in. (See blog for explanation)
        let dropped_bits = middle_aligned.1 | (left_aligned.1 & 0x7FF_FFFF_FFFF_FFFF_FFFF);
        // Step 5: The msb of the dropped bits has been preserved, and all other bits
        // if any were set, would be set somewhere in the other 127 bits.
        // If msb of dropped bits is 0, it is mantissa + 0
        // If msb of dropped bits is 1, it is mantissa + 0 only if mantissa lowest bit is 0
        // and other bits of the dropped bits are all 0.
        // (This is why we only care if the other non-msb dropped bits are all 0 or not,
        // so we can just OR them to make sure any bits show up somewhere.)
        let mantissa =
            (mantissa + ((dropped_bits - ((dropped_bits >> 127) & !mantissa)) >> 127)) as u64;
        // Step 6: Calculate the exponent
        // If self is 0, exponent should be 0 (special meaning) and mantissa will end up 0 too
        // Otherwise, (255 - n) + 1022 so it simplifies to 1277 - n
        // 1023 and 1022 are the cutoffs for the exponent having the msb next to the decimal point
        let exponent = if self == Self::ZERO { 0 } else { 1277 - u64::from(leading_zeroes) };
        // Step 7: sign bit is always 0, exponent is shifted into place
        // Use addition instead of bitwise OR to saturate the exponent if mantissa overflows
        f64::from_bits((exponent << 52) + mantissa)
    }

    /// Parses exactly 64 ASCII hex characters (no `0x` prefix) into a `U256`.
    ///
    /// Returns `None` if `s` is not exactly 64 bytes long or contains a non-hex-digit character.
    /// Used by the `serde` human-readable `Deserialize` implementation below.
    #[cfg(feature = "serde")]
    fn from_exact_hex_bytes(s: &str) -> Option<Self> {
        if s.len() != 64 || !s.is_ascii() {
            return None;
        }
        let bytes = s.as_bytes();
        let mut out = [0_u8; 32];
        #[allow(clippy::indexing_slicing)]
        for i in 0..32 {
            let hi = (bytes[2 * i] as char).to_digit(16)?;
            let lo = (bytes[2 * i + 1] as char).to_digit(16)?;
            out[i] = ((hi << 4) | lo) as u8;
        }
        Some(Self::from_be_bytes(out))
    }
}

impl<T: Into<u128>> From<T> for U256 {
    fn from(x: T) -> Self { Self(0, x.into()) }
}

impl Add for U256 {
    type Output = Self;
    fn add(self, rhs: Self) -> Self {
        let (res, overflow) = self.overflowing_add(rhs);
        debug_assert!(!overflow, "addition of U256 values overflowed");
        res
    }
}

impl Sub for U256 {
    type Output = Self;
    fn sub(self, rhs: Self) -> Self {
        let (res, overflow) = self.overflowing_sub(rhs);
        debug_assert!(!overflow, "subtraction of U256 values overflowed");
        res
    }
}

impl Mul for U256 {
    type Output = Self;
    fn mul(self, rhs: Self) -> Self {
        let (res, overflow) = self.overflowing_mul(rhs);
        debug_assert!(!overflow, "multiplication of U256 values overflowed");
        res
    }
}

impl Div for U256 {
    type Output = Self;
    fn div(self, rhs: Self) -> Self { self.div_rem(rhs).0 }
}

impl Rem for U256 {
    type Output = Self;
    fn rem(self, rhs: Self) -> Self { self.div_rem(rhs).1 }
}

impl Not for U256 {
    type Output = Self;

    fn not(self) -> Self { Self(!self.0, !self.1) }
}

impl Shl<u32> for U256 {
    type Output = Self;
    fn shl(self, shift: u32) -> Self { self.wrapping_shl(shift) }
}

impl Shr<u32> for U256 {
    type Output = Self;
    fn shr(self, shift: u32) -> Self { self.wrapping_shr(shift) }
}

impl fmt::Display for U256 {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        if self.is_zero() {
            f.pad_integral(true, "", "0")
        } else {
            self.fmt_decimal(f)
        }
    }
}

impl fmt::Debug for U256 {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { write!(f, "{:#x}", self) }
}

impl fmt::Binary for U256 {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        if self.is_zero() {
            return f.pad_integral(true, "0b", "0");
        }

        let mut buf = [0u8; 256];
        let mut i = 256usize;
        let mut value = *self;

        #[allow(clippy::indexing_slicing)]
        while value > Self::ZERO {
            i -= 1;
            buf[i] = b'0' + (value.low_u64() & 1) as u8;
            value = value >> 1;
        }

        let ascii_slice = buf.get(i..).expect("i <= buf.len()");
        let s = core::str::from_utf8(ascii_slice).expect("binary digits are valid UTF8");
        f.pad_integral(true, "0b", s)
    }
}

impl fmt::Octal for U256 {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        if self.is_zero() {
            return f.pad_integral(true, "0o", "0");
        }

        let mut buf = [0u8; 86];
        let mut i = 86usize;
        let mut value = *self;

        #[allow(clippy::indexing_slicing)]
        while value > Self::ZERO {
            i -= 1;
            buf[i] = b'0' + (value.low_u64() & 7) as u8;
            value = value >> 3;
        }

        let ascii_slice = buf.get(i..).expect("i <= buf.len()");
        let s = core::str::from_utf8(ascii_slice).expect("octal digits are valid UTF8");
        f.pad_integral(true, "0o", s)
    }
}

// Hand-rolled hex formatting avoids dependency on an external hex crate.
macro_rules! impl_hex {
    ($hex:path, $lookup:expr) => {
        impl $hex for U256 {
            #[inline]
            fn fmt(&self, f: &mut fmt::Formatter) -> core::fmt::Result {
                if f.alternate() {
                    f.write_str("0x")?;
                }

                #[allow(clippy::indexing_slicing)]
                for byte in self.to_be_bytes() {
                    let upper_idx = ((byte & 0xf0) >> 4) as usize;
                    let lower_idx = (byte & 0xf) as usize;
                    f.write_char($lookup[upper_idx])?;
                    f.write_char($lookup[lower_idx])?;
                }
                Ok(())
            }
        }
    };
}
impl_hex!(
    fmt::LowerHex,
    ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f']
);
impl_hex!(
    fmt::UpperHex,
    ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F']
);

#[cfg(feature = "serde")]
impl crate::serde::Serialize for U256 {
    #[inline]
    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
    where
        S: crate::serde::Serializer,
    {
        struct DisplayHex(U256);

        impl fmt::Display for DisplayHex {
            #[inline]
            fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { write!(f, "{:x}", self.0) }
        }

        if serializer.is_human_readable() {
            serializer.collect_str(&DisplayHex(*self))
        } else {
            let bytes = self.to_be_bytes();
            serializer.serialize_bytes(&bytes)
        }
    }
}

#[cfg(feature = "serde")]
impl<'de> crate::serde::Deserialize<'de> for U256 {
    fn deserialize<D: crate::serde::Deserializer<'de>>(d: D) -> Result<Self, D::Error> {
        use crate::serde::de;

        if d.is_human_readable() {
            struct HexVisitor;

            impl de::Visitor<'_> for HexVisitor {
                type Value = U256;

                fn expecting(&self, f: &mut fmt::Formatter) -> fmt::Result {
                    f.write_str("a 32 byte ASCII hex string")
                }

                fn visit_str<E>(self, s: &str) -> Result<Self::Value, E>
                where
                    E: de::Error,
                {
                    if s.len() != 64 {
                        return Err(de::Error::invalid_length(s.len(), &self));
                    }

                    U256::from_exact_hex_bytes(s)
                        .ok_or_else(|| de::Error::invalid_value(de::Unexpected::Str(s), &self))
                }
            }
            d.deserialize_str(HexVisitor)
        } else {
            struct BytesVisitor;

            impl de::Visitor<'_> for BytesVisitor {
                type Value = U256;

                fn expecting(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
                    f.write_str("a sequence of bytes")
                }

                fn visit_bytes<E>(self, v: &[u8]) -> Result<Self::Value, E>
                where
                    E: de::Error,
                {
                    let b = v.try_into().map_err(|_| de::Error::invalid_length(v.len(), &self))?;
                    Ok(U256::from_be_bytes(b))
                }
            }

            d.deserialize_bytes(BytesVisitor)
        }
    }
}

/// Splits a 32 byte array into two 16 byte arrays.
fn split_in_half(a: [u8; 32]) -> ([u8; 16], [u8; 16]) {
    let mut high = [0_u8; 16];
    let mut low = [0_u8; 16];

    high.copy_from_slice(&a[..16]);
    low.copy_from_slice(&a[16..]);

    (high, low)
}

// 10^38 is the largest power of 10 that fits in a u128
const POW10_38: u128 = 10_u128.pow(38);
impl core::str::FromStr for U256 {
    type Err = ParseU256Error;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        let mut result = Self::ZERO;

        if s.is_empty() {
            return Err(ParseU256Error::Empty);
        }

        for chunk in s.as_bytes().rchunks(38).rev() {
            let chunk_str = core::str::from_utf8(chunk).map_err(ParseU256Error::InvalidEncoding)?;

            let val: u128 = chunk_str.parse().map_err(ParseU256Error::InvalidDigit)?;

            // Shift decimals and add chunk
            let (res, carry1) = result.overflowing_mul(POW10_38.into());
            let (res, carry2) = res.overflowing_add(val.into());

            if carry1 | carry2 {
                return Err(ParseU256Error::Overflow);
            }

            result = res;
        }

        Ok(result)
    }
}

/// Error returned when parsing a [`U256`] from a string.
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub enum ParseU256Error {
    /// Numeric value exceeded [`U256::MAX`].
    Overflow,
    /// Parsed string was empty.
    Empty,
    /// Failed parsing a target from an integer string.
    InvalidDigit(core::num::ParseIntError),
    /// Failed parsing due to non-ASCII encoding on the string.
    InvalidEncoding(core::str::Utf8Error),
}

impl From<core::convert::Infallible> for ParseU256Error {
    fn from(never: core::convert::Infallible) -> Self { match never {} }
}

impl fmt::Display for ParseU256Error {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match self {
            Self::Overflow => write!(f, "parsed value exceeded unsigned 256-bit range"),
            Self::Empty => write!(f, "parsed string is empty"),
            Self::InvalidEncoding(ref e) =>
                crate::write_err!(f, "parsed number contained non-ascii chars"; e),
            Self::InvalidDigit(ref e) =>
                crate::write_err!(f, "parsed number contained invalid digit"; e),
        }
    }
}

#[cfg(feature = "std")]
impl std::error::Error for ParseU256Error {
    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
        match self {
            Self::Overflow => None,
            Self::Empty => None,
            Self::InvalidEncoding(ref e) => Some(e),
            Self::InvalidDigit(ref e) => Some(e),
        }
    }
}

#[cfg(kani)]
mod verification {
    use super::U256;

    impl kani::Arbitrary for U256 {
        fn any() -> Self {
            let high: u128 = kani::any();
            let low: u128 = kani::any();
            Self::new(high, low)
        }
    }

    #[kani::unwind(5)] // mul_u64 loops over 4 64 bit ints so use one more than 4
    #[kani::proof]
    fn check_mul_u64() {
        let x: U256 = kani::any();
        let y: u64 = kani::any();

        let _ = x.mul_u64(y);
    }
}

#[cfg(test)]
mod tests {
    #[cfg(feature = "alloc")]
    use alloc::format;

    use super::*;

    /// Test-only helpers for [`U256`].
    impl U256 {
        fn bit_at(&self, index: usize) -> bool {
            assert!(index <= 255, "index out of bounds");

            let word = if index < 128 { self.1 } else { self.0 };
            (word & (1 << (index % 128))) != 0
        }

        fn from_array(a: [u64; 4]) -> Self {
            let mut ret = Self::ZERO;
            ret.0 = (u128::from(a[0]) << 64) ^ u128::from(a[1]);
            ret.1 = (u128::from(a[2]) << 64) ^ u128::from(a[3]);
            ret
        }
    }

    #[test]
    fn u256_num_bits() {
        assert_eq!(U256::from(255_u64).bits(), 8);
        assert_eq!(U256::from(256_u64).bits(), 9);
        assert_eq!(U256::from(300_u64).bits(), 9);
        assert_eq!(U256::from(60000_u64).bits(), 16);
        assert_eq!(U256::from(70000_u64).bits(), 17);

        let u = U256::from(u128::MAX) << 1;
        assert_eq!(u.bits(), 129);

        // Try to read the following lines out loud quickly
        let mut shl = U256::from(70000_u64);
        shl = shl << 100;
        assert_eq!(shl.bits(), 117);
        shl = shl << 100;
        assert_eq!(shl.bits(), 217);
        shl = shl << 100;
        assert_eq!(shl.bits(), 0);
    }

    #[test]
    fn u256_bit_at() {
        assert!(!U256::from(10_u64).bit_at(0));
        assert!(U256::from(10_u64).bit_at(1));
        assert!(!U256::from(10_u64).bit_at(2));
        assert!(U256::from(10_u64).bit_at(3));
        assert!(!U256::from(10_u64).bit_at(4));

        let u = U256::new(0xa000_0000_0000_0000_0000_0000_0000_0000, 0);
        assert!(u.bit_at(255));
        assert!(!u.bit_at(254));
        assert!(u.bit_at(253));
        assert!(!u.bit_at(252));
    }

    #[test]
    #[cfg(feature = "alloc")]
    #[cfg(feature = "serde")]
    fn u256_serde() {
        let check = |uint, hex| {
            let json = format!("\"{}\"", hex);
            assert_eq!(serde_json::to_string(&uint).unwrap(), json);
            assert_eq!(serde_json::from_str::<U256>(&json).unwrap(), uint);

            let bin_encoded = bincode::serialize(&uint).unwrap();
            let bin_decoded: U256 = bincode::deserialize(&bin_encoded).unwrap();
            assert_eq!(bin_decoded, uint);
        };

        check(U256::ZERO, "0000000000000000000000000000000000000000000000000000000000000000");
        check(
            U256::from(0xDEAD_BEEF_u32),
            "00000000000000000000000000000000000000000000000000000000deadbeef",
        );
        check(
            U256::from_array([0xdd44, 0xcc33, 0xbb22, 0xaa11]),
            "000000000000dd44000000000000cc33000000000000bb22000000000000aa11",
        );
        check(U256::MAX, "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff");
        check(
            U256::new(
                0xDEAD_BEEA_A69B_455C_D41B_B662_A69B_4550,
                0xA69B_455C_D41B_B662_A69B_4555_DEAD_BEEF,
            ),
            "deadbeeaa69b455cd41bb662a69b4550a69b455cd41bb662a69b4555deadbeef",
        );

        assert!(serde_json::from_str::<U256>(
            "\"fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffg\""
        )
        .is_err()); // invalid char
        assert!(serde_json::from_str::<U256>(
            "\"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff\""
        )
        .is_err()); // invalid length
        assert!(serde_json::from_str::<U256>(
            "\"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff\""
        )
        .is_err()); // invalid length
    }

    #[test]
    #[cfg(feature = "alloc")]
    fn u256_lower_hex() {
        assert_eq!(
            format!("{:x}", U256::from(0xDEAD_BEEF_u64)),
            "00000000000000000000000000000000000000000000000000000000deadbeef",
        );
        assert_eq!(
            format!("{:#x}", U256::from(0xDEAD_BEEF_u64)),
            "0x00000000000000000000000000000000000000000000000000000000deadbeef",
        );
        assert_eq!(
            format!("{:x}", U256::MAX),
            "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
        );
        assert_eq!(
            format!("{:#x}", U256::MAX),
            "0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
        );
    }

    #[test]
    #[cfg(feature = "alloc")]
    fn u256_upper_hex() {
        assert_eq!(
            format!("{:X}", U256::from(0xDEAD_BEEF_u64)),
            "00000000000000000000000000000000000000000000000000000000DEADBEEF",
        );
        assert_eq!(
            format!("{:#X}", U256::from(0xDEAD_BEEF_u64)),
            "0x00000000000000000000000000000000000000000000000000000000DEADBEEF",
        );
        assert_eq!(
            format!("{:X}", U256::MAX),
            "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
        );
        assert_eq!(
            format!("{:#X}", U256::MAX),
            "0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
        );
    }

    #[test]
    #[cfg(feature = "alloc")]
    fn u256_display() {
        assert_eq!(format!("{}", U256::from(100_u32)), "100",);
        assert_eq!(format!("{}", U256::ZERO), "0",);
        assert_eq!(format!("{}", U256::from(u64::MAX)), format!("{}", u64::MAX),);
        assert_eq!(
            format!("{}", U256::MAX),
            "115792089237316195423570985008687907853269984665640564039457584007913129639935",
        );
    }

    macro_rules! check_format {
        ($($test_name:ident, $val:literal, $format_string:literal, $expected:literal);* $(;)?) => {
            $(
                #[test]
                #[cfg(feature = "alloc")]
                fn $test_name() {
                    assert_eq!(format!($format_string, U256::from($val)), $expected);
                }
            )*
        }
    }
    check_format! {
        check_fmt_0, 0_u32, "{}", "0";
        check_fmt_1, 0_u32, "{:2}", " 0";
        check_fmt_2, 0_u32, "{:02}", "00";

        check_fmt_3, 1_u32, "{}", "1";
        check_fmt_4, 1_u32, "{:2}", " 1";
        check_fmt_5, 1_u32, "{:02}", "01";

        check_fmt_10, 10_u32, "{}", "10";
        check_fmt_11, 10_u32, "{:2}", "10";
        check_fmt_12, 10_u32, "{:02}", "10";
        check_fmt_13, 10_u32, "{:3}", " 10";
        check_fmt_14, 10_u32, "{:03}", "010";

        check_fmt_20, 1_u32, "{:<2}", "1 ";
        check_fmt_21, 1_u32, "{:<02}", "01";
        check_fmt_22, 1_u32, "{:>2}", " 1"; // This is default but check it anyways.
        check_fmt_23, 1_u32, "{:>02}", "01";
        check_fmt_24, 1_u32, "{:^3}", " 1 ";
        check_fmt_25, 1_u32, "{:^03}", "001";
        // Sanity check, for integral types precision is ignored.
        check_fmt_30, 0_u32, "{:.1}", "0";
        check_fmt_31, 0_u32, "{:4.1}", "   0";
        check_fmt_32, 0_u32, "{:04.1}", "0000";

        check_fmt_33, 0_u32, "{:b}", "0";
        check_fmt_34, 0_u32, "{:#b}", "0b0";
        check_fmt_35, 42_u32, "{:b}", "101010";
        check_fmt_36, 42_u32, "{:#b}", "0b101010";
        check_fmt_37, 42_u32, "{:8b}", "  101010";
        check_fmt_38, 42_u32, "{:08b}", "00101010";
        check_fmt_39, 42_u32, "{:<8b}", "101010  ";
        check_fmt_40, 42_u32, "{:>8b}", "  101010";
        check_fmt_41, 42_u32, "{:^8b}", " 101010 ";
        check_fmt_42, 42_u32, "{:#10b}", "  0b101010";
        check_fmt_43, 42_u32, "{:#010b}", "0b00101010";
        check_fmt_44, 42_u32, "{:.4b}", "101010";
        check_fmt_45, 42_u32, "{:10.4b}", "    101010";

        check_fmt_46, 0_u32, "{:o}", "0";
        check_fmt_47, 0_u32, "{:#o}", "0o0";
        check_fmt_48, 42_u32, "{:o}", "52";
        check_fmt_49, 42_u32, "{:#o}", "0o52";
        check_fmt_50, 42_u32, "{:4o}", "  52";
        check_fmt_51, 42_u32, "{:04o}", "0052";
        check_fmt_52, 42_u32, "{:<4o}", "52  ";
        check_fmt_53, 42_u32, "{:>4o}", "  52";
        check_fmt_54, 42_u32, "{:^4o}", " 52 ";
        check_fmt_55, 42_u32, "{:#6o}", "  0o52";
        check_fmt_56, 42_u32, "{:#06o}", "0o0052";
        check_fmt_57, 42_u32, "{:.4o}", "52";
        check_fmt_58, 42_u32, "{:6.4o}", "    52";
    }

    #[test]
    #[cfg(feature = "alloc")]
    fn u256_comp() {
        let small = U256::from_array([0, 0, 0, 10]);
        let big = U256::from_array([0, 0, 0x0209_E737_8231_E632, 0x8C8C_3EE7_0C64_4118]);
        let bigger = U256::from_array([0, 0, 0x0209_E737_8231_E632, 0x9C8C_3EE7_0C64_4118]);
        let biggest = U256::from_array([1, 0, 0x0209_E737_8231_E632, 0x5C8C_3EE7_0C64_4118]);

        assert!(small < big);
        assert!(big < bigger);
        assert!(bigger < biggest);
        assert!(bigger <= biggest);
        assert!(biggest <= biggest);
        assert!(bigger >= big);
        assert!(bigger >= small);
        assert!(small <= small);
    }

    const WANT: U256 =
        U256(0x1bad_cafe_dead_beef_deaf_babe_2bed_feed, 0xbaad_f00d_defa_ceda_11fe_d2ba_d1c0_ffe0);

    #[rustfmt::skip]
    const BE_BYTES: [u8; 32] = [
        0x1b, 0xad, 0xca, 0xfe, 0xde, 0xad, 0xbe, 0xef, 0xde, 0xaf, 0xba, 0xbe, 0x2b, 0xed, 0xfe, 0xed,
        0xba, 0xad, 0xf0, 0x0d, 0xde, 0xfa, 0xce, 0xda, 0x11, 0xfe, 0xd2, 0xba, 0xd1, 0xc0, 0xff, 0xe0,
    ];

    #[rustfmt::skip]
    const LE_BYTES: [u8; 32] = [
        0xe0, 0xff, 0xc0, 0xd1, 0xba, 0xd2, 0xfe, 0x11, 0xda, 0xce, 0xfa, 0xde, 0x0d, 0xf0, 0xad, 0xba,
        0xed, 0xfe, 0xed, 0x2b, 0xbe, 0xba, 0xaf, 0xde, 0xef, 0xbe, 0xad, 0xde, 0xfe, 0xca, 0xad, 0x1b,
    ];

    // Sanity check that we have the bytes in the correct big-endian order.
    #[test]
    fn sanity_be_bytes() {
        let mut out = [0_u8; 32];
        out[..16].copy_from_slice(&WANT.0.to_be_bytes());
        out[16..].copy_from_slice(&WANT.1.to_be_bytes());
        assert_eq!(out, BE_BYTES);
    }

    // Sanity check that we have the bytes in the correct little-endian order.
    #[test]
    fn sanity_le_bytes() {
        let mut out = [0_u8; 32];
        out[..16].copy_from_slice(&WANT.1.to_le_bytes());
        out[16..].copy_from_slice(&WANT.0.to_le_bytes());
        assert_eq!(out, LE_BYTES);
    }

    #[test]
    fn u256_to_be_bytes() {
        assert_eq!(WANT.to_be_bytes(), BE_BYTES);
    }

    #[test]
    fn u256_from_be_bytes() {
        assert_eq!(U256::from_be_bytes(BE_BYTES), WANT);
    }

    #[test]
    fn u256_to_le_bytes() {
        assert_eq!(WANT.to_le_bytes(), LE_BYTES);
    }

    #[test]
    fn u256_from_le_bytes() {
        assert_eq!(U256::from_le_bytes(LE_BYTES), WANT);
    }

    #[test]
    fn u256_from_u8() {
        let u = U256::from(0xbe_u8);
        assert_eq!(u, U256::new(0, 0xbe));
    }

    #[test]
    fn u256_from_u16() {
        let u = U256::from(0xbeef_u16);
        assert_eq!(u, U256::new(0, 0xbeef));
    }

    #[test]
    fn u256_from_u32() {
        let u = U256::from(0xdead_beef_u32);
        assert_eq!(u, U256::new(0, 0xdead_beef));
    }

    #[test]
    fn u256_from_u64() {
        let u = U256::from(0xdead_beef_cafe_babe_u64);
        assert_eq!(u, U256::new(0, 0xdead_beef_cafe_babe));
    }

    #[test]
    fn u256_from_u128() {
        let u = U256::from(0xdead_beef_cafe_babe_0123_4567_89ab_cdefu128);
        assert_eq!(u, U256::new(0, 0xdead_beef_cafe_babe_0123_4567_89ab_cdef));
    }

    macro_rules! test_from_unsigned_integer_type {
        ($($test_name:ident, $ty:ident);* $(;)?) => {
            $(
                #[test]
                fn $test_name() {
                    // Internal representation is big-endian.
                    let want = U256::new(0, 0xAB);

                    let x = 0xAB as $ty;
                    let got = U256::from(x);

                    assert_eq!(got, want);
                }
            )*
        }
    }
    test_from_unsigned_integer_type! {
        from_unsigned_integer_type_u8, u8;
        from_unsigned_integer_type_u16, u16;
        from_unsigned_integer_type_u32, u32;
        from_unsigned_integer_type_u64, u64;
        from_unsigned_integer_type_u128, u128;
    }

    #[test]
    fn u256_from_be_array_u64() {
        let array = [
            0x1bad_cafe_dead_beef,
            0xdeaf_babe_2bed_feed,
            0xbaad_f00d_defa_ceda,
            0x11fe_d2ba_d1c0_ffe0,
        ];

        let uint = U256::from_array(array);
        assert_eq!(uint, WANT);
    }

    #[test]
    fn u256_shift_left() {
        let u = U256::from(1_u32);
        assert_eq!(u << 0, u);
        assert_eq!(u << 1, U256::from(2_u64));
        assert_eq!(u << 63, U256::from(0x8000_0000_0000_0000_u64));
        assert_eq!(u << 64, U256::from_array([0, 0, 0x0000_0000_0000_0001, 0]));
        assert_eq!(u << 127, U256::new(0, 0x8000_0000_0000_0000_0000_0000_0000_0000));
        assert_eq!(u << 128, U256::new(1, 0));

        let x = U256::new(0, 0x8000_0000_0000_0000_0000_0000_0000_0000);
        assert_eq!(x << 1, U256::new(1, 0));
    }

    #[test]
    fn u256_shift_right() {
        let u = U256::new(1, 0);
        assert_eq!(u >> 0, u);
        assert_eq!(u >> 1, U256::new(0, 0x8000_0000_0000_0000_0000_0000_0000_0000));
        assert_eq!(u >> 127, U256::new(0, 2));
        assert_eq!(u >> 128, U256::new(0, 1));
    }

    #[test]
    fn u256_arithmetic() {
        let init = U256::from(0xDEAD_BEEF_DEAD_BEEF_u64);
        let copy = init;

        let add = init.wrapping_add(copy);
        assert_eq!(add, U256::from_array([0, 0, 1, 0xBD5B_7DDF_BD5B_7DDE]));
        // Bitshifts
        let shl = add << 88;
        assert_eq!(shl, U256::from_array([0, 0x01BD_5B7D, 0xDFBD_5B7D_DE00_0000, 0]));
        let shr = shl >> 40;
        assert_eq!(shr, U256::from_array([0, 0, 0x0001_BD5B_7DDF_BD5B, 0x7DDE_0000_0000_0000]));
        // Increment
        let mut incr = shr;
        incr = incr.wrapping_inc();
        assert_eq!(incr, U256::from_array([0, 0, 0x0001_BD5B_7DDF_BD5B, 0x7DDE_0000_0000_0001]));
        // Subtraction
        let sub = incr.wrapping_sub(init);
        assert_eq!(sub, U256::from_array([0, 0, 0x0001_BD5B_7DDF_BD5A, 0x9F30_4110_2152_4112]));
        // Multiplication
        let (mult, _) = sub.mul_u64(300);
        assert_eq!(mult, U256::from_array([0, 0, 0x0209_E737_8231_E632, 0x8C8C_3EE7_0C64_4118]));
        // Division
        assert_eq!(U256::from(105_u32) / U256::from(5_u32), U256::from(21_u32));
        let div = mult / U256::from(300_u32);
        assert_eq!(div, U256::from_array([0, 0, 0x0001_BD5B_7DDF_BD5A, 0x9F30_4110_2152_4112]));

        assert_eq!(U256::from(105_u32) % U256::from(5_u32), U256::ZERO);
        assert_eq!(U256::from(35_498_456_u32) % U256::from(3_435_u32), U256::from(1_166_u32));
        let rem_src = mult.wrapping_mul(U256::from(39842_u32)).wrapping_add(U256::from(9054_u32));
        assert_eq!(rem_src % U256::from(39_842_u32), U256::from(9_054_u32));
    }

    #[test]
    fn u256_bit_inversion() {
        let v = U256::new(1, 0);
        let want = U256::new(
            0xffff_ffff_ffff_ffff_ffff_ffff_ffff_fffe,
            0xffff_ffff_ffff_ffff_ffff_ffff_ffff_ffff,
        );
        assert_eq!(!v, want);

        let v = U256::new(0x0c0c_0c0c_0c0c_0c0c_0c0c_0c0c_0c0c_0c0c, 0xeeee_eeee_eeee_eeee);
        let want = U256::new(
            0xf3f3_f3f3_f3f3_f3f3_f3f3_f3f3_f3f3_f3f3,
            0xffff_ffff_ffff_ffff_1111_1111_1111_1111,
        );
        assert_eq!(!v, want);
    }

    #[test]
    fn u256_mul_u64_by_one() {
        let v = U256::from(0xDEAD_BEEF_DEAD_BEEF_u64);
        assert_eq!(v, v.mul_u64(1_u64).0);
    }

    #[test]
    fn u256_mul_u64_by_zero() {
        let v = U256::from(0xDEAD_BEEF_DEAD_BEEF_u64);
        assert_eq!(U256::ZERO, v.mul_u64(0_u64).0);
    }

    #[test]
    fn u256_mul_u64() {
        let u64_val = U256::from(0xDEAD_BEEF_DEAD_BEEF_u64);

        let u96_res = u64_val.mul_u64(0xFFFF_FFFF).0;
        let u128_res = u96_res.mul_u64(0xFFFF_FFFF).0;
        let u160_res = u128_res.mul_u64(0xFFFF_FFFF).0;
        let u192_res = u160_res.mul_u64(0xFFFF_FFFF).0;
        let u224_res = u192_res.mul_u64(0xFFFF_FFFF).0;
        let u256_res = u224_res.mul_u64(0xFFFF_FFFF).0;

        assert_eq!(u96_res, U256::from_array([0, 0, 0xDEAD_BEEE, 0xFFFF_FFFF_2152_4111]));
        assert_eq!(
            u128_res,
            U256::from_array([0, 0, 0xDEAD_BEEE_2152_4110, 0x2152_4111_DEAD_BEEF])
        );
        assert_eq!(
            u160_res,
            U256::from_array([0, 0xDEAD_BEED, 0x42A4_8222_0000_0001, 0xBD5B_7DDD_2152_4111])
        );
        assert_eq!(
            u192_res,
            U256::from_array([
                0,
                0xDEAD_BEEC_63F6_C334,
                0xBD5B_7DDF_BD5B_7DDB,
                0x63F6_C333_DEAD_BEEF
            ])
        );
        assert_eq!(
            u224_res,
            U256::from_array([
                0xDEAD_BEEB,
                0x8549_0448_5964_BAAA,
                0xFFFF_FFFB_A69B_4558,
                0x7AB6_FBBB_2152_4111
            ])
        );
        assert_eq!(
            u256_res,
            U256::new(
                0xDEAD_BEEA_A69B_455C_D41B_B662_A69B_4550,
                0xA69B_455C_D41B_B662_A69B_4555_DEAD_BEEF,
            )
        );
    }

    #[test]
    fn u256_addition() {
        let x = U256::from(u128::MAX);
        let (add, overflow) = x.overflowing_add(U256::ONE);
        assert!(!overflow);
        assert_eq!(add, U256::new(1, 0));

        let (add, _) = add.overflowing_add(U256::ONE);
        assert_eq!(add, U256::new(1, 1));
    }

    #[test]
    fn u256_subtraction() {
        let (sub, overflow) = U256::ONE.overflowing_sub(U256::ONE);
        assert!(!overflow);
        assert_eq!(sub, U256::ZERO);

        let x = U256::new(1, 0);
        let (sub, overflow) = x.overflowing_sub(U256::ONE);
        assert!(!overflow);
        assert_eq!(sub, U256::from(u128::MAX));
    }

    #[test]
    fn u256_multiplication() {
        let u64_val = U256::from(0xDEAD_BEEF_DEAD_BEEF_u64);

        let u128_res = u64_val.wrapping_mul(u64_val);

        assert_eq!(u128_res, U256::new(0, 0xC1B1_CD13_A4D1_3D46_048D_1354_216D_A321));

        let u256_res = u128_res.wrapping_mul(u128_res);

        assert_eq!(
            u256_res,
            U256::new(
                0x928D_92B4_D7F5_DF33_4AFC_FF6F_0375_C608,
                0xF5CF_7F36_18C2_C886_F4E1_66AA_D40D_0A41,
            )
        );
    }

    #[test]
    fn u256_multiplication_bits_in_each_word() {
        // Put a digit in the least significant bit of each 64 bit word.
        let u = (1_u128 << 64) | 1_u128;
        let x = U256::new(u, u);

        // Put a digit in the second least significant bit of each 64 bit word.
        let u = (2_u128 << 64) | 2_u128;
        let y = U256::new(u, u);

        let (got, overflow) = x.overflowing_mul(y);

        let want = U256::new(
            0x0000_0000_0000_0008_0000_0000_0000_0006,
            0x0000_0000_0000_0004_0000_0000_0000_0002,
        );
        assert!(overflow);
        assert_eq!(got, want);
    }

    #[test]
    fn u256_overflowing_mul() {
        let a = U256::new(u128::MAX, 0);
        let b = U256::new(1 << 65 | 1, 0);
        let (res, overflow) = a.overflowing_mul(b);
        assert_eq!(res, U256::ZERO);
        assert!(overflow);

        let a = U256::new(1 << 64, 0);
        let b = U256::new(1, 0);
        let (res, overflow) = a.overflowing_mul(b);
        assert_eq!(res, U256::ZERO);
        assert!(overflow);

        let a = U256::new(0, 1 << 63);
        let b = U256::new(1, 0);
        let (res, overflow) = a.overflowing_mul(b);
        assert_eq!(res, b << 63);
        assert!(!overflow);

        let (res, overflow) = U256::ONE.overflowing_mul(U256::ONE);
        assert_eq!(res, U256::ONE);
        assert!(!overflow);

        // Simple case near upper edge
        let a = U256::new(1 << 125, 0);
        let b = U256::new(0, 4);
        let (res, overflow) = a.overflowing_mul(b);
        assert_eq!(res, U256::new(1 << 127, 0));
        assert!(!overflow);

        // Check case where bits overflow during shift. Kills * -> + and - -> + mutants.
        let a = U256::ONE << 2;
        let b = U256::ONE << 254;
        let (res, overflow) = a.overflowing_mul(b);
        assert_eq!(res, U256::ZERO);
        assert!(overflow);

        // mul_u64 overflows twice but no other overflows. Kills |= -> ^= mutant.
        let a = U256::ONE << 255;
        let b = U256::new(1 << 1 | 1 << 65, 0);
        let (res, overflow) = a.overflowing_mul(b);
        assert_eq!(res, U256::ZERO);
        assert!(overflow);
    }

    #[test]
    fn u256_increment() {
        let mut val = U256::new(
            0xEFFF_FFFF_FFFF_FFFF_FFFF_FFFF_FFFF_FFFF,
            0xFFFF_FFFF_FFFF_FFFF_FFFF_FFFF_FFFF_FFFE,
        );
        val = val.wrapping_inc();
        assert_eq!(
            val,
            U256::new(
                0xEFFF_FFFF_FFFF_FFFF_FFFF_FFFF_FFFF_FFFF,
                0xFFFF_FFFF_FFFF_FFFF_FFFF_FFFF_FFFF_FFFF,
            )
        );
        val = val.wrapping_inc();
        assert_eq!(
            val,
            U256::new(
                0xF000_0000_0000_0000_0000_0000_0000_0000,
                0x0000_0000_0000_0000_0000_0000_0000_0000,
            )
        );

        assert_eq!(U256::MAX.wrapping_inc(), U256::ZERO);
    }

    #[test]
    fn u256_extreme_bitshift() {
        // Shifting a u64 by 64 bits gives an undefined value, so make sure that
        // we're doing the Right Thing here
        let init = U256::from(0xDEAD_BEEF_DEAD_BEEF_u64);

        assert_eq!(init << 64, U256::new(0, 0xDEAD_BEEF_DEAD_BEEF_0000_0000_0000_0000));
        let add = (init << 64).wrapping_add(init);
        assert_eq!(add, U256::new(0, 0xDEAD_BEEF_DEAD_BEEF_DEAD_BEEF_DEAD_BEEF));
        assert_eq!(add >> 0, U256::new(0, 0xDEAD_BEEF_DEAD_BEEF_DEAD_BEEF_DEAD_BEEF));
        assert_eq!(add << 0, U256::new(0, 0xDEAD_BEEF_DEAD_BEEF_DEAD_BEEF_DEAD_BEEF));
        assert_eq!(add >> 64, U256::new(0, 0x0000_0000_0000_0000_DEAD_BEEF_DEAD_BEEF));
        assert_eq!(
            add << 64,
            U256::new(0xDEAD_BEEF_DEAD_BEEF, 0xDEAD_BEEF_DEAD_BEEF_0000_0000_0000_0000)
        );
    }

    #[test]
    fn u256_is_max_correct_negative() {
        let tc = [U256::ZERO, U256::ONE, U256::from(u128::MAX)];
        for t in tc {
            assert!(!t.is_max());
        }
    }

    #[test]
    fn u256_is_max_correct_positive() {
        assert!(U256::MAX.is_max());

        let u = u128::MAX;
        assert!(((U256::from(u) << 128) + U256::from(u)).is_max());
    }

    #[test]
    fn u256_zero_min_max_inverse() {
        assert_eq!(U256::MAX.inverse(), U256::ONE);
        assert_eq!(U256::ONE.inverse(), U256::MAX);
        assert_eq!(U256::ZERO.inverse(), U256::MAX);
    }

    #[test]
    fn u256_wrapping_add_wraps_at_boundary() {
        assert_eq!(U256::MAX.wrapping_add(U256::ONE), U256::ZERO);
        assert_eq!(U256::MAX.wrapping_add(U256::from(2_u8)), U256::ONE);
    }

    #[test]
    fn u256_wrapping_sub_wraps_at_boundary() {
        assert_eq!(U256::ZERO.wrapping_sub(U256::ONE), U256::MAX);
        assert_eq!(U256::ONE.wrapping_sub(U256::from(2_u8)), U256::MAX);
    }

    #[test]
    fn mul_u64_overflows() {
        let (_, overflow) = U256::MAX.mul_u64(2);
        assert!(overflow, "max * 2 should overflow");
    }

    #[test]
    #[cfg(debug_assertions)]
    #[should_panic(expected = "overflowed")]
    fn u256_overflowing_addition_panics() { let _ = U256::MAX + U256::ONE; }

    #[test]
    #[cfg(debug_assertions)]
    #[should_panic(expected = "overflowed")]
    fn u256_overflowing_subtraction_panics() { let _ = U256::ZERO - U256::ONE; }

    #[test]
    #[cfg(debug_assertions)]
    #[should_panic(expected = "overflowed")]
    fn u256_multiplication_by_max_panics() { let _ = U256::MAX * U256::MAX; }

    #[test]
    fn u256_to_f64() {
        assert_eq!(U256::ZERO.to_f64(), 0.0_f64);
        assert_eq!(U256::ONE.to_f64(), 1.0_f64);
        assert_eq!(U256::MAX.to_f64(), 1.157_920_892_373_162e77_f64);
        assert_eq!((U256::MAX >> 1).to_f64(), 5.789_604_461_865_81e76_f64);
        assert_eq!((U256::MAX >> 128).to_f64(), 3.402_823_669_209_385e38_f64);
        assert_eq!((U256::MAX >> (256 - 54)).to_f64(), 1.801_439_850_948_198_4e16_f64);
        // 53 bits and below should not use exponents
        assert_eq!((U256::MAX >> (256 - 53)).to_f64(), 9_007_199_254_740_991.0_f64);
        assert_eq!((U256::MAX >> (256 - 32)).to_f64(), 4_294_967_295.0_f64);
        assert_eq!((U256::MAX >> (256 - 16)).to_f64(), 65535.0_f64);
        assert_eq!((U256::MAX >> (256 - 8)).to_f64(), 255.0_f64);
    }
}