atmos/os_lib/js/

bigint.rs

//! 任意精度整数 BigInt の実装。
//!
//! ECMAScript の BigInt セマンティクスに沿った符号付き多倍長整数。
//! 内部表現は「符号 + ベース 2^32 のリム列（リトルエンディアン: limbs[0] が最下位）」。
//! ゼロは `negative=false` かつ `limbs` 空（正規形）で表す。
//! no_std 環境のため alloc のみ使用し、除算は素朴な long division を用いる。

use alloc::string::String;
use alloc::vec::Vec;
use core::cmp::Ordering;

/// ベース 2^32 のリムで表す符号付き任意精度整数。
#[derive(Clone, PartialEq, Eq)]
pub struct BigInt {
    /// true なら負。ゼロのときは必ず false（正規形）。
    negative: bool,
    /// 絶対値のリム列（リトルエンディアン）。末尾の 0 は持たない（正規形）。
    limbs: Vec<u32>,
}

impl BigInt {
    /// 値 0。
    pub fn zero() -> Self {
        BigInt {
            negative: false,
            limbs: Vec::new(),
        }
    }

    /// ゼロかどうか。
    pub fn is_zero(&self) -> bool {
        self.limbs.is_empty()
    }

    /// 末尾の 0 リムを除去し、ゼロなら符号を正に揃える（正規形化）。
    fn normalize(mut self) -> Self {
        while let Some(&last) = self.limbs.last() {
            if last == 0 {
                self.limbs.pop();
            } else {
                break;
            }
        }
        if self.limbs.is_empty() {
            self.negative = false;
        }
        self
    }

    /// i64 から生成。
    pub fn from_i64(mut v: i64) -> Self {
        if v == 0 {
            return BigInt::zero();
        }
        let negative = v < 0;
        // i64::MIN の絶対値はオーバーフローするため u64 で扱う。
        let mut mag = if negative {
            (v as i128).unsigned_abs()
        } else {
            v as u128
        };
        let _ = &mut v;
        let mut limbs = Vec::new();
        while mag > 0 {
            limbs.push((mag & 0xFFFF_FFFF) as u32);
            mag >>= 32;
        }
        BigInt { negative, limbs }.normalize()
    }

    /// u64 から生成（常に非負）。`DataView.prototype.getBigUint64` 用。
    pub fn from_u64(v: u64) -> Self {
        if v == 0 {
            return BigInt::zero();
        }
        let mut mag = v;
        let mut limbs = Vec::new();
        while mag > 0 {
            limbs.push((mag & 0xFFFF_FFFF) as u32);
            mag >>= 32;
        }
        BigInt { negative: false, limbs }.normalize()
    }

    /// f64 から生成（整数値のみ受理。小数・非有限は None）。
    pub fn from_f64(v: f64) -> Option<Self> {
        if !v.is_finite() {
            return None;
        }
        if libm::trunc(v) != v {
            return None;
        }
        if v == 0.0 {
            return Some(BigInt::zero());
        }
        let negative = v < 0.0;
        let mut mag = libm::fabs(v);
        // 2^32 進で下位から取り出す。f64 は 2^53 まで整数を正確に表現できるが、
        // それを超える大きさも近似的に分解する（仕様の厳密さより実用性を優先）。
        let mut limbs = Vec::new();
        let base = 4294967296.0_f64; // 2^32
        while mag >= 1.0 {
            let rem = mag - libm::floor(mag / base) * base;
            limbs.push(rem as u32);
            mag = libm::floor(mag / base);
        }
        Some(BigInt { negative, limbs }.normalize())
    }

    /// 十進文字列をパース（先頭に符号可、`_` 区切り許容）。失敗で None。
    pub fn parse_decimal(s: &str) -> Option<Self> {
        let t = s.trim();
        if t.is_empty() {
            return Some(BigInt::zero());
        }
        let (negative, digits) = match t.strip_prefix('-') {
            Some(rest) => (true, rest),
            None => (false, t.strip_prefix('+').unwrap_or(t)),
        };
        if digits.is_empty() {
            return None;
        }
        let mut acc = BigInt::zero();
        let ten = BigInt::from_i64(10);
        for ch in digits.chars() {
            if ch == '_' {
                continue;
            }
            let d = ch.to_digit(10)?;
            acc = acc.mul(&ten).add(&BigInt::from_i64(d as i64));
        }
        acc.negative = negative;
        Some(acc.normalize())
    }

    /// 文字列をパース（0x/0o/0b 接頭辞対応、それ以外は十進）。
    pub fn parse_str(s: &str) -> Option<Self> {
        let t = s.trim();
        let (neg, body) = match t.strip_prefix('-') {
            Some(r) => (true, r),
            None => (false, t.strip_prefix('+').unwrap_or(t)),
        };
        let parsed = if let Some(h) = body.strip_prefix("0x").or_else(|| body.strip_prefix("0X")) {
            Self::parse_radix(h, 16)
        } else if let Some(o) = body.strip_prefix("0o").or_else(|| body.strip_prefix("0O")) {
            Self::parse_radix(o, 8)
        } else if let Some(b) = body.strip_prefix("0b").or_else(|| body.strip_prefix("0B")) {
            Self::parse_radix(b, 2)
        } else {
            Self::parse_decimal(body)
        };
        parsed.map(|mut v| {
            if neg {
                v.negative = !v.negative;
            }
            v.normalize()
        })
    }

    /// 指定基数（2〜16）の桁列をパース。
    fn parse_radix(digits: &str, radix: u32) -> Option<Self> {
        if digits.is_empty() {
            return None;
        }
        let mut acc = BigInt::zero();
        let base = BigInt::from_i64(radix as i64);
        for ch in digits.chars() {
            if ch == '_' {
                continue;
            }
            let d = ch.to_digit(radix)?;
            acc = acc.mul(&base).add(&BigInt::from_i64(d as i64));
        }
        Some(acc)
    }

    /// 絶対値の大小比較。
    fn cmp_magnitude(&self, other: &Self) -> Ordering {
        if self.limbs.len() != other.limbs.len() {
            return self.limbs.len().cmp(&other.limbs.len());
        }
        // 上位リムから比較。
        for i in (0..self.limbs.len()).rev() {
            if self.limbs[i] != other.limbs[i] {
                return self.limbs[i].cmp(&other.limbs[i]);
            }
        }
        Ordering::Equal
    }

    /// 符号込みの全順序比較。
    #[allow(clippy::should_implement_trait)]
    pub fn cmp(&self, other: &Self) -> Ordering {
        match (self.negative, other.negative) {
            (false, true) => Ordering::Greater,
            (true, false) => Ordering::Less,
            (false, false) => self.cmp_magnitude(other),
            (true, true) => other.cmp_magnitude(self),
        }
    }

    /// 絶対値の加算（符号は無視）。
    fn add_magnitude(a: &[u32], b: &[u32]) -> Vec<u32> {
        let mut out = Vec::with_capacity(a.len().max(b.len()) + 1);
        let mut carry: u64 = 0;
        let n = a.len().max(b.len());
        for i in 0..n {
            let av = *a.get(i).unwrap_or(&0) as u64;
            let bv = *b.get(i).unwrap_or(&0) as u64;
            let sum = av + bv + carry;
            out.push((sum & 0xFFFF_FFFF) as u32);
            carry = sum >> 32;
        }
        if carry > 0 {
            out.push(carry as u32);
        }
        out
    }

    /// 絶対値の減算 a - b（a >= b を前提）。
    fn sub_magnitude(a: &[u32], b: &[u32]) -> Vec<u32> {
        let mut out = Vec::with_capacity(a.len());
        let mut borrow: i64 = 0;
        for i in 0..a.len() {
            let av = a[i] as i64;
            let bv = *b.get(i).unwrap_or(&0) as i64;
            let mut diff = av - bv - borrow;
            if diff < 0 {
                diff += 1 << 32;
                borrow = 1;
            } else {
                borrow = 0;
            }
            out.push((diff & 0xFFFF_FFFF) as u32);
        }
        out
    }

    /// 加算。
    pub fn add(&self, other: &Self) -> Self {
        if self.negative == other.negative {
            // 同符号: 絶対値を足して符号は据え置き。
            BigInt {
                negative: self.negative,
                limbs: Self::add_magnitude(&self.limbs, &other.limbs),
            }
            .normalize()
        } else {
            // 異符号: 絶対値の大きい方から小さい方を引く。
            match self.cmp_magnitude(other) {
                Ordering::Equal => BigInt::zero(),
                Ordering::Greater => BigInt {
                    negative: self.negative,
                    limbs: Self::sub_magnitude(&self.limbs, &other.limbs),
                }
                .normalize(),
                Ordering::Less => BigInt {
                    negative: other.negative,
                    limbs: Self::sub_magnitude(&other.limbs, &self.limbs),
                }
                .normalize(),
            }
        }
    }

    /// 減算。
    pub fn sub(&self, other: &Self) -> Self {
        // a - b = a + (-b)
        let neg_other = BigInt {
            negative: !other.negative,
            limbs: other.limbs.clone(),
        }
        .normalize();
        self.add(&neg_other)
    }

    /// 符号反転。
    pub fn neg(&self) -> Self {
        if self.is_zero() {
            return BigInt::zero();
        }
        BigInt {
            negative: !self.negative,
            limbs: self.limbs.clone(),
        }
    }

    /// 絶対値。
    pub fn abs(&self) -> Self {
        BigInt {
            negative: false,
            limbs: self.limbs.clone(),
        }
    }

    /// 乗算（素朴な O(n*m) 筆算）。
    pub fn mul(&self, other: &Self) -> Self {
        if self.is_zero() || other.is_zero() {
            return BigInt::zero();
        }
        let mut out = alloc::vec![0u32; self.limbs.len() + other.limbs.len()];
        for (i, &a) in self.limbs.iter().enumerate() {
            let mut carry: u64 = 0;
            for (j, &b) in other.limbs.iter().enumerate() {
                let idx = i + j;
                let cur = out[idx] as u64 + (a as u64) * (b as u64) + carry;
                out[idx] = (cur & 0xFFFF_FFFF) as u32;
                carry = cur >> 32;
            }
            // 端のキャリーを伝播。
            let mut k = i + other.limbs.len();
            while carry > 0 {
                let cur = out[k] as u64 + carry;
                out[k] = (cur & 0xFFFF_FFFF) as u32;
                carry = cur >> 32;
                k += 1;
            }
        }
        BigInt {
            negative: self.negative != other.negative,
            limbs: out,
        }
        .normalize()
    }

    /// 絶対値どうしの除算 → (商, 剰余) を絶対値で返す。
    /// 素朴なビット単位の long division（速度より明快さを優先）。
    fn divmod_magnitude(a: &[u32], b: &[u32]) -> (Vec<u32>, Vec<u32>) {
        // b == 0 は呼び出し側で弾く前提。
        let dividend = BigInt {
            negative: false,
            limbs: a.to_vec(),
        }
        .normalize();
        let divisor = BigInt {
            negative: false,
            limbs: b.to_vec(),
        }
        .normalize();
        if dividend.cmp_magnitude(&divisor) == Ordering::Less {
            return (Vec::new(), dividend.limbs);
        }
        // ビット長を求める。
        let total_bits = dividend.limbs.len() * 32;
        let mut quotient = BigInt::zero();
        let mut remainder = BigInt::zero();
        let one = BigInt::from_i64(1);
        for i in (0..total_bits).rev() {
            // remainder <<= 1
            remainder = remainder.shl_bits(1);
            // remainder |= bit i of dividend
            let limb = i / 32;
            let bit = i % 32;
            if (dividend.limbs[limb] >> bit) & 1 == 1 {
                remainder = remainder.add(&one);
            }
            if remainder.cmp_magnitude(&divisor) != Ordering::Less {
                remainder = BigInt {
                    negative: false,
                    limbs: Self::sub_magnitude(&remainder.limbs, &divisor.limbs),
                }
                .normalize();
                quotient = quotient.set_bit(i);
            }
        }
        (quotient.normalize().limbs, remainder.normalize().limbs)
    }

    /// 絶対値を左へ bit ビットシフト（内部用、符号は維持）。
    fn shl_bits(&self, bits: usize) -> Self {
        if self.is_zero() || bits == 0 {
            return self.clone();
        }
        let limb_shift = bits / 32;
        let bit_shift = bits % 32;
        let mut out = alloc::vec![0u32; self.limbs.len() + limb_shift + 1];
        for (i, &v) in self.limbs.iter().enumerate() {
            let val = (v as u64) << bit_shift;
            out[i + limb_shift] |= (val & 0xFFFF_FFFF) as u32;
            out[i + limb_shift + 1] |= (val >> 32) as u32;
        }
        BigInt {
            negative: self.negative,
            limbs: out,
        }
        .normalize()
    }

    /// 絶対値を右へ bit ビットシフト（内部用、符号は維持。算術的切り捨て）。
    fn shr_bits(&self, bits: usize) -> Self {
        if self.is_zero() || bits == 0 {
            return self.clone();
        }
        let limb_shift = bits / 32;
        let bit_shift = bits % 32;
        if limb_shift >= self.limbs.len() {
            return BigInt::zero();
        }
        let mut out = alloc::vec![0u32; self.limbs.len() - limb_shift];
        for i in 0..out.len() {
            let lo = self.limbs[i + limb_shift] >> bit_shift;
            let hi = if bit_shift > 0 && i + limb_shift + 1 < self.limbs.len() {
                self.limbs[i + limb_shift + 1] << (32 - bit_shift)
            } else {
                0
            };
            out[i] = lo | hi;
        }
        BigInt {
            negative: self.negative,
            limbs: out,
        }
        .normalize()
    }

    /// ビット i を 1 にした新しい値を返す（絶対値操作・内部用）。
    fn set_bit(&self, i: usize) -> Self {
        let limb = i / 32;
        let bit = i % 32;
        let mut limbs = self.limbs.clone();
        if limb >= limbs.len() {
            limbs.resize(limb + 1, 0);
        }
        limbs[limb] |= 1 << bit;
        BigInt {
            negative: self.negative,
            limbs,
        }
    }

    /// 除算（商）。ゼロ除算は None。商は 0 方向への切り捨て（truncation）。
    pub fn div(&self, other: &Self) -> Option<Self> {
        if other.is_zero() {
            return None;
        }
        let (q, _) = Self::divmod_magnitude(&self.limbs, &other.limbs);
        Some(
            BigInt {
                negative: self.negative != other.negative,
                limbs: q,
            }
            .normalize(),
        )
    }

    /// 剰余。ゼロ除算は None。符号は被除数に従う（ECMAScript 準拠）。
    pub fn rem(&self, other: &Self) -> Option<Self> {
        if other.is_zero() {
            return None;
        }
        let (_, r) = Self::divmod_magnitude(&self.limbs, &other.limbs);
        Some(
            BigInt {
                negative: self.negative,
                limbs: r,
            }
            .normalize(),
        )
    }

    /// 累乗（指数は非負 BigInt のみ。負指数は None）。二乗法で計算。
    pub fn pow(&self, exp: &Self) -> Option<Self> {
        if exp.negative {
            return None;
        }
        if exp.is_zero() {
            return Some(BigInt::from_i64(1));
        }
        let mut result = BigInt::from_i64(1);
        let mut base = self.clone();
        let mut e = exp.clone();
        let two = BigInt::from_i64(2);
        while !e.is_zero() {
            // e が奇数なら result *= base
            let (_, r) = Self::divmod_magnitude(&e.limbs, &two.limbs);
            let odd = !r.is_empty();
            if odd {
                result = result.mul(&base);
            }
            base = base.mul(&base);
            e = e.shr_bits(1).abs();
        }
        Some(result)
    }

    /// 十進文字列化。
    pub fn to_decimal_string(&self) -> String {
        if self.is_zero() {
            return String::from("0");
        }
        // 絶対値を 10^9 チャンクで割り続けて下位から桁を得る。
        let mut digits_rev: Vec<u32> = Vec::new();
        let chunk = BigInt::from_i64(1_000_000_000);
        let mut cur = self.abs();
        while !cur.is_zero() {
            let (q, r) = Self::divmod_magnitude(&cur.limbs, &chunk.limbs);
            let rem_val = limbs_to_u64(&r) as u32;
            digits_rev.push(rem_val);
            cur = BigInt {
                negative: false,
                limbs: q,
            }
            .normalize();
        }
        let mut s = String::new();
        if self.negative {
            s.push('-');
        }
        // 最上位チャンクは前ゼロなし、それ以降は 9 桁ゼロ詰め。
        for (i, chunk_val) in digits_rev.iter().rev().enumerate() {
            if i == 0 {
                s.push_str(&alloc::format!("{}", chunk_val));
            } else {
                s.push_str(&alloc::format!("{:09}", chunk_val));
            }
        }
        s
    }

    /// 近似的に f64 へ変換（Number(bigint) 用。大きすぎる値は Infinity に近づく）。
    pub fn to_f64(&self) -> f64 {
        let mut result = 0.0_f64;
        let base = 4294967296.0_f64; // 2^32
        for &limb in self.limbs.iter().rev() {
            result = result * base + (limb as f64);
        }
        if self.negative {
            -result
        } else {
            result
        }
    }

    /// 1 かどうか（絶対値が 1 で正）。
    pub fn is_one(&self) -> bool {
        !self.negative && self.limbs.len() == 1 && self.limbs[0] == 1
    }

    /// このビット長（絶対値を表すのに必要な最小ビット数）。ゼロは 0。
    fn bit_length(&self) -> usize {
        match self.limbs.last() {
            None => 0,
            Some(&top) => (self.limbs.len() - 1) * 32 + (32 - top.leading_zeros() as usize),
        }
    }

    /// 指定リム数の「2 の補数表現」をリトルエンディアンの u32 列で返す。
    /// 負数は ~|x| + 1 を width リム幅で計算する。正数はゼロ拡張。
    fn to_twos_complement(&self, width: usize) -> Vec<u32> {
        let mut out = alloc::vec![0u32; width];
        for (i, slot) in out.iter_mut().enumerate() {
            *slot = *self.limbs.get(i).unwrap_or(&0);
        }
        if self.negative {
            // ビット反転して +1。
            for slot in out.iter_mut() {
                *slot = !*slot;
            }
            let mut carry = 1u64;
            for slot in out.iter_mut() {
                let v = *slot as u64 + carry;
                *slot = (v & 0xFFFF_FFFF) as u32;
                carry = v >> 32;
                if carry == 0 {
                    break;
                }
            }
        }
        out
    }

    /// width リム幅の 2 の補数表現（リトルエンディアン）から BigInt を復元する。
    /// 最上位ビットが 1 なら負数とみなす。
    fn from_twos_complement(mut limbs: Vec<u32>) -> Self {
        let negative = limbs
            .last()
            .map(|&top| (top >> 31) & 1 == 1)
            .unwrap_or(false);
        if negative {
            // 2 の補数を反転して大きさを得る: |x| = ~bits + 1。
            for slot in limbs.iter_mut() {
                *slot = !*slot;
            }
            let mut carry = 1u64;
            for slot in limbs.iter_mut() {
                let v = *slot as u64 + carry;
                *slot = (v & 0xFFFF_FFFF) as u32;
                carry = v >> 32;
                if carry == 0 {
                    break;
                }
            }
        }
        BigInt { negative, limbs }.normalize()
    }

    /// 2 つの値のビット演算に必要なリム幅（両者の絶対値ビット長 + 符号ビット余裕）。
    fn bitop_width(&self, other: &Self) -> usize {
        let bits = self.bit_length().max(other.bit_length());
        // 符号ビットのために 1 ビット余分に確保し、リム単位へ切り上げる。
        (bits / 32) + 2
    }

    /// ビット AND（2 の補数の無限長セマンティクス）。
    pub fn bitand(&self, other: &Self) -> Self {
        let w = self.bitop_width(other);
        let a = self.to_twos_complement(w);
        let b = other.to_twos_complement(w);
        let out: Vec<u32> = a.iter().zip(b.iter()).map(|(x, y)| x & y).collect();
        Self::from_twos_complement(out)
    }

    /// ビット OR。
    pub fn bitor(&self, other: &Self) -> Self {
        let w = self.bitop_width(other);
        let a = self.to_twos_complement(w);
        let b = other.to_twos_complement(w);
        let out: Vec<u32> = a.iter().zip(b.iter()).map(|(x, y)| x | y).collect();
        Self::from_twos_complement(out)
    }

    /// ビット XOR。
    pub fn bitxor(&self, other: &Self) -> Self {
        let w = self.bitop_width(other);
        let a = self.to_twos_complement(w);
        let b = other.to_twos_complement(w);
        let out: Vec<u32> = a.iter().zip(b.iter()).map(|(x, y)| x ^ y).collect();
        Self::from_twos_complement(out)
    }

    /// ビット NOT（~x = -(x+1)、2 の補数の恒等式）。
    pub fn bitnot(&self) -> Self {
        // ~x = -x - 1
        self.neg().sub(&BigInt::from_i64(1))
    }

    /// 左シフト（count は非負 i64。符号は保存、絶対値を count ビット左へ）。
    pub fn shl(&self, count: i64) -> Self {
        if count < 0 {
            return self.shr(-count);
        }
        let shifted = self.shl_bits(count as usize);
        BigInt {
            negative: self.negative,
            limbs: shifted.limbs,
        }
        .normalize()
    }

    /// 右シフト（算術シフト = 床方向。負数では -infinity 方向へ丸める ECMAScript 準拠）。
    pub fn shr(&self, count: i64) -> Self {
        if count < 0 {
            return self.shl(-count);
        }
        let n = count as usize;
        if !self.negative {
            // 正数は単純な論理右シフト。
            let shifted = self.shr_bits(n);
            return BigInt {
                negative: false,
                limbs: shifted.limbs,
            }
            .normalize();
        }
        // 負数の算術右シフトは床関数: floor(x / 2^n)。
        // |x| を n ビット右シフトし、切り捨てた下位ビットが非ゼロなら -1 する。
        let full_limbs = n / 32;
        let rem_bits = n % 32;
        let mut truncated_bits = false;
        for &l in self.limbs.iter().take(full_limbs) {
            if l != 0 {
                truncated_bits = true;
                break;
            }
        }
        if !truncated_bits && rem_bits > 0 {
            if let Some(&l) = self.limbs.get(full_limbs) {
                let mask = (1u32 << rem_bits) - 1;
                if (l & mask) != 0 {
                    truncated_bits = true;
                }
            }
        }
        let mag = self.shr_bits(n);
        let mut result = BigInt {
            negative: true,
            limbs: mag.limbs,
        }
        .normalize();
        if truncated_bits {
            // 床方向へさらに 1 引く（負方向に大きくする）。
            result = result.sub(&BigInt::from_i64(1));
        }
        result
    }

    /// BigInt.asUintN(bits, x): 下位 bits ビットを符号なし整数として解釈。
    pub fn as_uint_n(&self, bits: u64) -> Self {
        if bits == 0 {
            return BigInt::zero();
        }
        let full_limbs = (bits / 32) as usize;
        let rem_bits = (bits % 32) as usize;
        let width = full_limbs + if rem_bits > 0 { 1 } else { 0 } + 1;
        let tc = self.to_twos_complement(width);
        let out_limbs_count = full_limbs + if rem_bits > 0 { 1 } else { 0 };
        let mut out = alloc::vec![0u32; out_limbs_count];
        for i in 0..full_limbs {
            if i < tc.len() {
                out[i] = tc[i];
            }
        }
        if rem_bits > 0 && full_limbs < tc.len() {
            let mask = (1u32 << rem_bits) - 1;
            out[full_limbs] = tc[full_limbs] & mask;
        }
        // 符号なしなので最上位に符号ビットが立たないよう、そのまま大きさとして扱う。
        BigInt {
            negative: false,
            limbs: out,
        }
        .normalize()
    }

    /// BigInt.asIntN(bits, x): 下位 bits ビットを符号付き 2 の補数として解釈。
    pub fn as_int_n(&self, bits: u64) -> Self {
        if bits == 0 {
            return BigInt::zero();
        }
        let unsigned = self.as_uint_n(bits);
        // 最上位ビット（bits-1）が立っていれば 2^bits を引いて負数化。
        let top = (bits - 1) as usize;
        let limb = top / 32;
        let bit = top % 32;
        let is_neg = limb < unsigned.limbs.len() && (unsigned.limbs[limb] >> bit) & 1 == 1;
        if is_neg {
            // result = unsigned - 2^bits
            let two_pow = BigInt::from_i64(1).shl(bits as i64);
            unsigned.sub(&two_pow)
        } else {
            unsigned
        }
    }

    /// 下位64ビットを2の補数のビットパターンとして u64 へ切り詰める。
    /// `DataView.prototype.setBigInt64/setBigUint64` がバイト列へ書き戻す際に使う。
    pub fn to_u64_truncated(&self) -> u64 {
        let unsigned = self.as_uint_n(64);
        let low = *unsigned.limbs.first().unwrap_or(&0) as u64;
        let high = *unsigned.limbs.get(1).unwrap_or(&0) as u64;
        low | (high << 32)
    }
}

/// リム列（最大 2 リム想定）を u64 に詰める補助。
fn limbs_to_u64(limbs: &[u32]) -> u64 {
    let mut v = 0u64;
    for (i, &l) in limbs.iter().enumerate().take(2) {
        v |= (l as u64) << (32 * i);
    }
    v
}

/// BigInt 自己テスト。(pass, total) を返す。
/// 算術・比較・ビット演算・シフト・asIntN/asUintN・パース・文字列化を検証する。
pub fn selftest() -> (usize, usize) {
    let mut pass = 0usize;
    let mut total = 0usize;

    // 文字列等価で検証する小ヘルパ。
    fn check_str(pass: &mut usize, total: &mut usize, got: &str, want: &str) {
        *total += 1;
        if got == want {
            *pass += 1;
        }
    }
    // 真偽値検証ヘルパ。
    fn check_bool(pass: &mut usize, total: &mut usize, cond: bool) {
        *total += 1;
        if cond {
            *pass += 1;
        }
    }
    // Option<String> 検証ヘルパ（unwrap を使わずに失敗を None として扱う）。
    // パース失敗や div/pow の None はそのまま不一致（テスト失敗）になる。
    fn check_opt(pass: &mut usize, total: &mut usize, got: Option<String>, want: &str) {
        *total += 1;
        if got.as_deref() == Some(want) {
            *pass += 1;
        }
    }

    let bi = BigInt::from_i64;
    let p = &mut pass;
    let t = &mut total;

    // --- パース & 文字列化 ---
    check_opt(
        p,
        t,
        BigInt::parse_str("0").map(|b| b.to_decimal_string()),
        "0",
    );
    check_opt(
        p,
        t,
        BigInt::parse_str("12345678901234567890").map(|b| b.to_decimal_string()),
        "12345678901234567890",
    );
    check_opt(
        p,
        t,
        BigInt::parse_str("-98765432109876543210").map(|b| b.to_decimal_string()),
        "-98765432109876543210",
    );
    check_opt(
        p,
        t,
        BigInt::parse_str("0xff").map(|b| b.to_decimal_string()),
        "255",
    );
    check_opt(
        p,
        t,
        BigInt::parse_str("0b1010").map(|b| b.to_decimal_string()),
        "10",
    );
    check_opt(
        p,
        t,
        BigInt::parse_str("0o17").map(|b| b.to_decimal_string()),
        "15",
    );
    check_opt(
        p,
        t,
        BigInt::parse_str("1_000_000").map(|b| b.to_decimal_string()),
        "1000000",
    );

    // --- 加減算（桁上がり・桁借り・符号交差）---
    check_str(p, t, &bi(2).add(&bi(3)).to_decimal_string(), "5");
    check_opt(
        p,
        t,
        BigInt::parse_str("4294967295").map(|b| b.add(&bi(1)).to_decimal_string()),
        "4294967296",
    );
    check_str(p, t, &bi(5).sub(&bi(8)).to_decimal_string(), "-3");
    check_str(p, t, &bi(-5).add(&bi(5)).to_decimal_string(), "0");
    check_opt(
        p,
        t,
        BigInt::parse_str("18446744073709551616").map(|b| b.sub(&bi(1)).to_decimal_string()),
        "18446744073709551615",
    );

    // --- 乗算 ---
    check_str(
        p,
        t,
        &bi(123456789).mul(&bi(987654321)).to_decimal_string(),
        "121932631112635269",
    );
    check_str(p, t, &bi(-7).mul(&bi(6)).to_decimal_string(), "-42");
    check_opt(
        p,
        t,
        BigInt::parse_str("99999999999999999999").and_then(|a| {
            BigInt::parse_str("99999999999999999999").map(|b| a.mul(&b).to_decimal_string())
        }),
        "9999999999999999999800000000000000000001",
    );

    // --- 除算・剰余（符号は被除数に従う）---
    check_opt(
        p,
        t,
        bi(100).div(&bi(7)).map(|b| b.to_decimal_string()),
        "14",
    );
    check_opt(
        p,
        t,
        bi(100).rem(&bi(7)).map(|b| b.to_decimal_string()),
        "2",
    );
    check_opt(
        p,
        t,
        bi(-100).div(&bi(7)).map(|b| b.to_decimal_string()),
        "-14",
    );
    check_opt(
        p,
        t,
        bi(-100).rem(&bi(7)).map(|b| b.to_decimal_string()),
        "-2",
    );
    check_bool(p, t, bi(1).div(&bi(0)).is_none());

    // --- 累乗 ---
    check_opt(
        p,
        t,
        bi(2).pow(&bi(64)).map(|b| b.to_decimal_string()),
        "18446744073709551616",
    );
    check_opt(p, t, bi(3).pow(&bi(0)).map(|b| b.to_decimal_string()), "1");
    check_opt(
        p,
        t,
        bi(-2).pow(&bi(3)).map(|b| b.to_decimal_string()),
        "-8",
    );

    // --- 比較 ---
    check_bool(p, t, bi(5).cmp(&bi(7)) == Ordering::Less);
    check_bool(p, t, bi(-3).cmp(&bi(-9)) == Ordering::Greater);
    check_bool(p, t, bi(42).cmp(&bi(42)) == Ordering::Equal);

    // --- ビット演算（正数）---
    check_str(
        p,
        t,
        &bi(0b1100).bitand(&bi(0b1010)).to_decimal_string(),
        "8",
    ); // 0b1000
    check_str(
        p,
        t,
        &bi(0b1100).bitor(&bi(0b1010)).to_decimal_string(),
        "14",
    ); // 0b1110
    check_str(
        p,
        t,
        &bi(0b1100).bitxor(&bi(0b1010)).to_decimal_string(),
        "6",
    ); // 0b0110

    // --- ビット演算（負数: 2 の補数の無限長セマンティクス）---
    check_str(p, t, &bi(5).bitnot().to_decimal_string(), "-6"); // ~5n == -6n
    check_str(p, t, &bi(-1).bitnot().to_decimal_string(), "0"); // ~(-1n) == 0n
    check_str(p, t, &bi(-1).bitand(&bi(5)).to_decimal_string(), "5"); // -1n & 5n == 5n
    check_str(p, t, &bi(-1).bitor(&bi(5)).to_decimal_string(), "-1"); // -1n | 5n == -1n
    check_str(p, t, &bi(-2).bitand(&bi(3)).to_decimal_string(), "2"); // -2n & 3n == 2n
    check_str(p, t, &bi(-1).bitxor(&bi(-1)).to_decimal_string(), "0"); // -1n ^ -1n == 0n

    // --- シフト ---
    check_str(
        p,
        t,
        &bi(1).shl(64).to_decimal_string(),
        "18446744073709551616",
    );
    check_str(p, t, &bi(255).shr(4).to_decimal_string(), "15");
    // 負数の算術右シフト（床方向）: -8 >> 1 == -4, -7 >> 1 == -4
    check_str(p, t, &bi(-8).shr(1).to_decimal_string(), "-4");
    check_str(p, t, &bi(-7).shr(1).to_decimal_string(), "-4");
    check_str(p, t, &bi(-1).shr(5).to_decimal_string(), "-1");
    check_str(
        p,
        t,
        &bi(12345).shl(40).shr(40).to_decimal_string(),
        "12345",
    );

    // --- asUintN / asIntN ---
    check_str(p, t, &bi(256).as_uint_n(8).to_decimal_string(), "0");
    check_str(p, t, &bi(257).as_uint_n(8).to_decimal_string(), "1");
    check_str(p, t, &bi(-1).as_uint_n(8).to_decimal_string(), "255");
    check_str(p, t, &bi(255).as_int_n(8).to_decimal_string(), "-1");
    check_str(p, t, &bi(128).as_int_n(8).to_decimal_string(), "-128");
    check_str(p, t, &bi(127).as_int_n(8).to_decimal_string(), "127");
    check_str(p, t, &bi(0x8000).as_int_n(16).to_decimal_string(), "-32768");

    // --- f64 変換 ---
    check_bool(p, t, bi(9007199254740992).to_f64() == 9007199254740992.0);
    check_bool(
        p,
        t,
        BigInt::from_f64(42.0).map(|b| b.to_decimal_string()) == Some(String::from("42")),
    );
    check_bool(p, t, BigInt::from_f64(1.5).is_none());

    (pass, total)
}