This is an automated email from the ASF dual-hosted git repository.
tlopex pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/tvm-ffi.git
The following commit(s) were added to refs/heads/main by this push:
new a04b4120 [FEAT][RUST] Native BigInt arithmetic, ported from the C++
int_ops (#815)
a04b4120 is described below
commit a04b4120c449adef9008410f885a2a7c3804d167
Author: Linzhang Li <[email protected]>
AuthorDate: Sun Sep 27 23:17:56 2026 -0400
[FEAT][RUST] Native BigInt arithmetic, ported from the C++ int_ops (#815)
## Summary
`tvm_ffi::BigInt` gains arithmetic with unbounded signed integer
semantics,
implemented in Rust because the C ABI exposes no arithmetic entry points
and
the C++ operators are header-only.
- Operators `+ - * / % & | ^ << >>` for owned and borrowed operands with
`i64`
accepted on either side, compound assignment, unary `-` and `!`. `/` and
`%`
truncate toward zero; bitwise operations sign-extend infinitely. Like
the
primitive operators, `/`, `%`, `<<` and `>>` panic on a zero divisor or
a
negative count.
- Fallible forms for ffi callbacks, where a panic cannot unwind:
`try_div`,
`try_rem`, `div_rem`, `floor_div`, `floor_mod`, `try_shl`, `try_shr`. A
zero
divisor raises the new `ZERO_DIVISION_ERROR` kind, a negative shift
count
`ValueError`, and a shift whose result cannot be allocated
`OverflowError`.
- `FromStr` and `Display` in decimal, `to_f64` rounding to nearest with
ties to
even, and `is_zero`.
`big_int/int_ops.rs` mirrors C++ `details::int_ops` in `big_int.h` one
for
one, so the two can be reviewed side by side: sign-extended add,
subtract and
negate; multiply on `u128` with the signed correction; shifts; scalar
division
in radix 2^32 with the normalized 64-bit divisor path; Knuth's Algorithm
D for
multiword division; the floor variants; and the double conversion.
Results are built the way C++ builds them. Add, subtract, negate, the
bitwise
operations and the shifts compute each word once, so `BigInt::build`
writes
them straight into a fresh object and then prunes its logical size in
place,
like C++ `Normalize`. These objects come from `malloc` with a deleter
that
mirrors C++ `ArrayHandler::Deleter_`, because `free` needs no layout and
the
allocation may be longer than the final size. Multiplication and
division
accumulate into `WordsBuf`, a zeroed 32-word stack buffer that spills to
a
`Vec`, and finish with `from_words`, which allocates at the final length
through `ObjectArc::new_with_extra_items`. Every object keeps the C++
`BigIntObj` layout, so either runtime reads and releases the other's
values.
This also fixes the generic deleter behind
`ObjectArc::new_with_extra_items`.
When the last strong reference went while a weak reference remained, it
saved
the item count over the header's reference count, so the weak reference
saw a
live object, could lock it, and the memory was never freed. That
affected every
Rust-allocated `Shape`, `String`, `Bytes`, `Array` and `Tensor`, and
`BigInt`
once it allocates in Rust. The count now goes in the first word after
the
header.
Benchmarks against the C++ operators on the same machine (ns/op, lower
is
better; both Rust builds use 64-byte function alignment so that code
placement
does not move the numbers):
| operation | Rust | C++ |
| --- | ---: | ---: |
| add, 4 words + 1 | 15.8 | 15.0 |
| multiply, 4 x 4 words | 28.9 | 36.6 |
| divide, 4 words / 1 | 38.6 | 33.9 |
| divide, 4 words / 4 | 60.6 | 61.7 |
| shift left by 70 | 18.0 | 17.0 |
| heap construction | 13.2 | 12.4 |
| from double, 1e30 | 19.4 | 21.3 |
| to decimal, 4 words | 192 | 627 |
## Testing
- `cargo test -p tvm-ffi`: **292 passed**. `tests/test_big_int.rs` grows
to 27
tests, 13 of them for arithmetic: the cases ported from
`tests/cpp/test_big_int.cc` (promotion and demotion at the `i64`
boundary,
mixed `i64` operands, compound assignment); signed division in every
sign
quadrant with inline and multiword operands and every error path;
shift-count
overflow and negative counts; an independent fixture with decimal
expectations
computed in Python; decimal parsing; Algorithm D estimate clamping, one
and
two corrections, add-back and the maximal normalization shift; scalar
division boundaries including the two-correction path and `|INT64_MIN|`;
the
small-divisor remainder fast path against int32 boundary answers; a
1500-round random property test (ring identities, division identities
with
the truncating and flooring sign rules, shifts as multiplication and
floor
division, text and double round trips, cross-checked against `i128`
where it
applies); a Rust-allocated object held and released by a C++ container
and
compared and hashed by C++ against a runtime-built twin; and results
wider
than the stack buffer.
- Weak references: a new test in `tests/test_big_int.rs` holds a weak
reference the way C++ `WeakObjectPtr` does across the last strong
release of
a `from_words` object and of an operator result, and expects an expired
header and a freeing release; a new test in `tests/test_object.rs` does
the
same for a generic extra-items object and checks the layout it is freed
with.
Both fail before the deleter fix.
- An offline differential run against the C++ operators: 20,000 random
operand
pairs of 1 to 7 words (including 0, -1, `i64::MIN` and `i64::MAX` words)
through all 14 operations give 278,356 word-identical results, with the
same
inline or heap representation on both sides and the same error kinds.
C++
read every Rust-built heap result in place and released the last
reference
of 72,501 of them, with glibc heap checking on (`MALLOC_CHECK_=3`).
- Failing the result allocation of `BigInt::from(1).try_shl(64000)` with
an
`LD_PRELOAD` malloc shim returns `OverflowError` instead of aborting.
- An offline interop harness passes: Rust-built values through the C++
`+`, `*`, `/` and `<<`, agreement of C++ `operator<<` with Rust
`Display`,
`ZeroDivisionError` / `TypeError` / `ValueError` crossing from C++, C++
calling Rust callbacks with C++-built values, and reference counts back
to
one afterwards.
- `rustfmt` clean on the touched files and no new `clippy` findings. No
C++
changes.
---------
Signed-off-by: yuchuan <[email protected]>
---
rust/tvm-ffi/src/big_int.rs | 429 ------------------
rust/tvm-ffi/src/big_int/int_ops.rs | 741 +++++++++++++++++++++++++++++++
rust/tvm-ffi/src/big_int/mod.rs | 862 ++++++++++++++++++++++++++++++++++++
rust/tvm-ffi/src/error.rs | 1 +
rust/tvm-ffi/src/lib.rs | 2 +-
rust/tvm-ffi/src/object.rs | 42 +-
rust/tvm-ffi/tests/test_big_int.rs | 738 ++++++++++++++++++++++++++++--
rust/tvm-ffi/tests/test_object.rs | 116 +++++
8 files changed, 2440 insertions(+), 491 deletions(-)
diff --git a/rust/tvm-ffi/src/big_int.rs b/rust/tvm-ffi/src/big_int.rs
deleted file mode 100644
index fbcb750d..00000000
--- a/rust/tvm-ffi/src/big_int.rs
+++ /dev/null
@@ -1,429 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-use crate::derive::Object;
-use crate::error::{Error, OVERFLOW_ERROR, VALUE_ERROR};
-use crate::object::{unsafe_, Object, ObjectCoreWithExtraItems};
-use crate::type_traits::AnyCompatible;
-use std::cmp::Ordering;
-use std::fmt::{Debug, Display, Write as _};
-use std::hash::{Hash, Hasher};
-use tvm_ffi_sys::TVMFFITypeIndex as TypeIndex;
-use tvm_ffi_sys::{TVMFFIAny, TVMFFIAnyDataUnion, TVMFFIBigIntFromByteArray,
TVMFFIByteArray};
-
-/// ABI stable arbitrary-precision signed integer for ffi.
-///
-/// Mirrors C++ `tvm::ffi::BigInt`: a value that fits `i64` is stored inline as
-/// `kTVMFFIInt`, and any wider value owns a `kTVMFFIBigInt` object holding its
-/// minimal two's-complement `i64` words, least-significant word first. The
-/// runtime keeps that representation canonical, so equal values share one
-/// representation and word-wise comparison decides equality.
-///
-/// The Rust side transports values across the ABI and converts them to and
-/// from native integers; arithmetic stays with the C++ implementation.
-#[repr(C)]
-pub struct BigInt {
- data: TVMFFIAny,
-}
-
-// BigIntObj for heap-allocated integers: the word count, then the canonical
-// two's-complement words as trailing items. Mirrors C++ `details::BigIntObj`.
-// Instances are created by the runtime, which owns the normalization rules.
-#[repr(C)]
-#[derive(Object)]
-#[type_key = "ffi.BigInt"]
-#[type_index(TypeIndex::kTVMFFIBigInt)]
-#[type_final]
-pub(crate) struct BigIntObj {
- object: Object,
- size: usize,
-}
-
-unsafe impl ObjectCoreWithExtraItems for BigIntObj {
- type ExtraItem = i64;
- #[inline]
- /// Get the count of extra items (the logical word count)
- fn extra_items_count(this: &Self) -> usize {
- this.size
- }
-}
-
-impl BigInt {
- /// Create the integer zero.
- pub fn new() -> Self {
- Self::from_i64(0)
- }
-
- #[inline]
- fn from_i64(value: i64) -> Self {
- Self {
- data: TVMFFIAny {
- type_index: TypeIndex::kTVMFFIInt as i32,
- small_str_len: 0,
- data_union: TVMFFIAnyDataUnion { v_int64: value },
- },
- }
- }
-
- /// Create from two's-complement `i64` words, least-significant word first.
- ///
- /// Redundant sign-extension words are pruned and a value that fits `i64`
- /// is stored inline; an empty slice is zero.
- pub fn from_words(words: &[i64]) -> Self {
- let input = TVMFFIByteArray::new(words.as_ptr() as *const u8,
std::mem::size_of_val(words));
- let mut data = TVMFFIAny::new();
- unsafe {
- crate::check_safe_call!(TVMFFIBigIntFromByteArray(&input, &mut
data))
- .expect("TVMFFIBigIntFromByteArray failed");
- }
- Self { data }
- }
-
- /// Borrow the canonical two's-complement words, least-significant word
first.
- ///
- /// The slice is never empty and its last word carries the sign.
- pub fn words(&self) -> &[i64] {
- unsafe {
- if self.data.type_index == TypeIndex::kTVMFFIInt as i32 {
- std::slice::from_ref(&self.data.data_union.v_int64)
- } else {
- let obj: &BigIntObj = &*(self.data.data_union.v_obj as *const
BigIntObj);
- BigIntObj::extra_items(obj)
- }
- }
- }
-
- /// Whether the value is negative.
- pub fn is_negative(&self) -> bool {
- let words = self.words();
- words[words.len() - 1] < 0
- }
-
- /// Return the value when it fits `i64`.
- #[inline]
- pub fn to_i64(&self) -> Option<i64> {
- if self.data.type_index == TypeIndex::kTVMFFIInt as i32 {
- Some(unsafe { self.data.data_union.v_int64 })
- } else {
- None
- }
- }
-
- /// Return the value when it fits `u64`.
- pub fn to_u64(&self) -> Option<u64> {
- match *self.words() {
- [w0] => u64::try_from(w0).ok(),
- [w0, 0] => Some(w0 as u64),
- _ => None,
- }
- }
-
- /// Return the value when it fits `i128`.
- pub fn to_i128(&self) -> Option<i128> {
- match *self.words() {
- [w0] => Some(i128::from(w0)),
- [w0, w1] => Some((i128::from(w1) << 64) | i128::from(w0 as u64)),
- _ => None,
- }
- }
-
- /// Return the value when it fits `u128`.
- pub fn to_u128(&self) -> Option<u128> {
- let combine = |w0: i64, w1: i64| (u128::from(w1 as u64) << 64) |
u128::from(w0 as u64);
- match *self.words() {
- [w0] => u128::try_from(w0).ok(),
- [w0, w1] if w1 >= 0 => Some(combine(w0, w1)),
- [w0, w1, 0] => Some(combine(w0, w1)),
- _ => None,
- }
- }
-}
-
-impl Default for BigInt {
- #[inline]
- fn default() -> Self {
- Self::new()
- }
-}
-
-/// Macro to implement From for integer types that always fit i64
-macro_rules! impl_big_int_from_int {
- ($($int_type:ty),* $(,)?) => {
- $(
- impl From<$int_type> for BigInt {
- #[inline]
- fn from(value: $int_type) -> Self {
- Self::from_i64(value as i64)
- }
- }
- )*
- };
-}
-
-impl_big_int_from_int!(i8, i16, i32, i64, isize, u8, u16, u32);
-
-impl From<bool> for BigInt {
- #[inline]
- fn from(value: bool) -> Self {
- Self::from_i64(i64::from(value))
- }
-}
-
-impl From<u64> for BigInt {
- fn from(value: u64) -> Self {
- match i64::try_from(value) {
- Ok(value) => Self::from_i64(value),
- Err(_) => Self::from_words(&[value as i64, 0]),
- }
- }
-}
-
-impl From<usize> for BigInt {
- #[inline]
- fn from(value: usize) -> Self {
- Self::from(value as u64)
- }
-}
-
-impl From<i128> for BigInt {
- fn from(value: i128) -> Self {
- match i64::try_from(value) {
- Ok(value) => Self::from_i64(value),
- // The arithmetic shift keeps the sign in the high word.
- Err(_) => Self::from_words(&[value as i64, (value >> 64) as i64]),
- }
- }
-}
-
-impl From<u128> for BigInt {
- fn from(value: u128) -> Self {
- match i64::try_from(value) {
- Ok(value) => Self::from_i64(value),
- // The zero guard keeps the value positive; normalization prunes
it when redundant.
- Err(_) => Self::from_words(&[value as i64, (value >> 64) as i64,
0]),
- }
- }
-}
-
-/// Negate two's-complement words in place, modulo their fixed width.
-fn negate_in_place(words: &mut [i64]) {
- let mut carry = true;
- for word in words.iter_mut() {
- let (sum, overflow) = (!(*word as
u64)).overflowing_add(u64::from(carry));
- *word = sum as i64;
- carry = overflow;
- }
-}
-
-impl TryFrom<f64> for BigInt {
- type Error = Error;
-
- /// Convert a finite double by truncating toward zero.
- ///
- /// NaN raises `ValueError` and infinity raises `OverflowError`.
- fn try_from(value: f64) -> Result<Self, Error> {
- // The upper bound is exclusive: i64::MAX rounds up to 2^63 as a
double.
- const LOWER: f64 = i64::MIN as f64;
- if (LOWER..-LOWER).contains(&value) {
- return Ok(Self::from_i64(value as i64));
- }
- if value.is_nan() {
- return Err(Error::new(VALUE_ERROR, "Cannot convert NaN to BigInt",
""));
- }
- if value.is_infinite() {
- return Err(Error::new(
- OVERFLOW_ERROR,
- "Cannot convert infinity to BigInt",
- "",
- ));
- }
- // |value| >= 2^63 is an integer: place the 53-bit significand at its
binary exponent.
- let bits = value.to_bits();
- let exponent = (((bits >> 52) & 0x7ff) - 1075) as usize;
- let significand = (bits & ((1u64 << 52) - 1)) | (1u64 << 52);
- let whole = exponent / 64;
- let part = exponent % 64;
- // Low zero words, up to two significand words, and a zero sign guard.
- let mut words = vec![0i64; whole + 3];
- words[whole] = (significand << part) as i64;
- if part != 0 {
- words[whole + 1] = (significand >> (64 - part)) as i64;
- }
- if value < 0.0 {
- negate_in_place(&mut words);
- }
- Ok(Self::from_words(&words))
- }
-}
-
-impl Clone for BigInt {
- #[inline]
- fn clone(&self) -> Self {
- if self.data.type_index == TypeIndex::kTVMFFIBigInt as i32 {
- unsafe { unsafe_::inc_ref(self.data.data_union.v_obj) }
- }
- Self { data: self.data }
- }
-}
-
-impl Drop for BigInt {
- #[inline]
- fn drop(&mut self) {
- if self.data.type_index == TypeIndex::kTVMFFIBigInt as i32 {
- unsafe { unsafe_::dec_ref(self.data.data_union.v_obj) }
- }
- }
-}
-
-impl PartialEq for BigInt {
- /// Canonical words make equal values word-for-word identical.
- #[inline]
- fn eq(&self, other: &Self) -> bool {
- self.words() == other.words()
- }
-}
-
-impl Eq for BigInt {}
-
-impl PartialOrd for BigInt {
- #[inline]
- fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
- Some(self.cmp(other))
- }
-}
-
-impl Ord for BigInt {
- fn cmp(&self, other: &Self) -> Ordering {
- let (a, b) = (self.words(), other.words());
- let (negative_a, negative_b) = (a[a.len() - 1] < 0, b[b.len() - 1] <
0);
- if negative_a != negative_b {
- return if negative_a {
- Ordering::Less
- } else {
- Ordering::Greater
- };
- }
- // With equal signs, sign-extended words compare as unsigned from the
top.
- let extension = if negative_a { u64::MAX } else { 0 };
- let word = |words: &[i64], i: usize| words.get(i).map_or(extension,
|&w| w as u64);
- (0..a.len().max(b.len()))
- .rev()
- .map(|i| word(a, i).cmp(&word(b, i)))
- .find(|ordering| ordering.is_ne())
- .unwrap_or(Ordering::Equal)
- }
-}
-
-impl Hash for BigInt {
- #[inline]
- fn hash<H: Hasher>(&self, state: &mut H) {
- self.words().hash(state);
- }
-}
-
-impl Display for BigInt {
- fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
- if let Some(value) = self.to_i64() {
- return Display::fmt(&value, f);
- }
- let words = self.words();
- let negative = words[words.len() - 1] < 0;
- let mut magnitude = words.to_vec();
- if negative {
- negate_in_place(&mut magnitude);
- }
- // Peel base-10^19 chunks, least significant first, by long division.
- const CHUNK: u128 = 10_000_000_000_000_000_000;
- let mut chunks = Vec::new();
- while magnitude.last() == Some(&0) {
- magnitude.pop();
- }
- while !magnitude.is_empty() {
- let mut remainder = 0u128;
- for word in magnitude.iter_mut().rev() {
- let current = (remainder << 64) | u128::from(*word as u64);
- *word = (current / CHUNK) as i64;
- remainder = current % CHUNK;
- }
- chunks.push(remainder as u64);
- while magnitude.last() == Some(&0) {
- magnitude.pop();
- }
- }
- let mut digits = String::new();
- let mut chunks = chunks.iter().rev();
- // A heap value is never zero, so the leading chunk always exists.
- write!(digits, "{}", chunks.next().unwrap_or(&0))?;
- for chunk in chunks {
- write!(digits, "{chunk:019}")?;
- }
- f.pad_integral(!negative, "", &digits)
- }
-}
-
-impl Debug for BigInt {
- fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
- f.debug_struct("ffi.BigInt")
- .field("data", &format_args!("{self}"))
- .finish()
- }
-}
-
-//-----------------------------------------------------
-// AnyCompatible implementation for BigInt
-//-----------------------------------------------------
-unsafe impl AnyCompatible for BigInt {
- fn type_str() -> std::string::String {
- "BigInt".to_string()
- }
-
- unsafe fn copy_to_any_view(this: &Self, data: &mut TVMFFIAny) {
- *data = this.data;
- }
-
- unsafe fn move_to_any(src: Self, data: &mut TVMFFIAny) {
- *data = src.data;
- std::mem::forget(src);
- }
-
- unsafe fn check_any_strict(data: &TVMFFIAny) -> bool {
- data.type_index == TypeIndex::kTVMFFIInt as i32
- || data.type_index == TypeIndex::kTVMFFIBigInt as i32
- }
-
- unsafe fn copy_from_any_view_after_check(data: &TVMFFIAny) -> Self {
- if data.type_index == TypeIndex::kTVMFFIBigInt as i32 {
- unsafe { unsafe_::inc_ref(data.data_union.v_obj) }
- }
- Self { data: *data }
- }
-
- unsafe fn move_from_any_after_check(data: &mut TVMFFIAny) -> Self {
- Self { data: *data }
- }
-
- unsafe fn try_cast_from_any_view(data: &TVMFFIAny) -> Result<Self, ()> {
- if Self::check_any_strict(data) {
- Ok(Self::copy_from_any_view_after_check(data))
- } else if data.type_index == TypeIndex::kTVMFFIBool as i32 {
- Ok(Self::from_i64(data.data_union.v_int64))
- } else {
- Err(())
- }
- }
-}
diff --git a/rust/tvm-ffi/src/big_int/int_ops.rs
b/rust/tvm-ffi/src/big_int/int_ops.rs
new file mode 100644
index 00000000..fb6bff15
--- /dev/null
+++ b/rust/tvm-ffi/src/big_int/int_ops.rs
@@ -0,0 +1,741 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+//! Word-level integer algorithms behind the `BigInt` operators.
+//!
+//! Every fallback takes canonical two's-complement words, least-significant
+//! first, and returns a canonical `BigInt`. The functions mirror C++
+//! `details::int_ops` in `include/tvm/ffi/big_int.h` one for one; keep them in
+//! sync. Word arithmetic wraps modulo 2^64 on purpose, hence the explicit
+//! `wrapping_*`/`overflowing_*` forms. As in C++, a result whose words are
each
+//! computed once is written straight into a fresh object and pruned in place
+//! (`BigInt::build`); multiplication and division accumulate into a zeroed
+//! [`WordsBuf`] and finish with [`BigInt::from_words`].
+#![allow(clippy::needless_range_loop)]
+
+use super::BigInt;
+use crate::error::{Error, Result, OVERFLOW_ERROR, VALUE_ERROR,
ZERO_DIVISION_ERROR};
+use std::mem::MaybeUninit;
+
+const BASE: u64 = 1 << 32;
+
+/// Words kept on the stack before a result or scratch buffer spills to the
heap.
+const INLINE_WORDS: usize = 32;
+
+/// Result or scratch words, zeroed in place on first use: up to
`INLINE_WORDS` on
+/// the caller's stack, longer on the heap. Two phases avoid moving the array.
+struct WordsBuf {
+ inline: MaybeUninit<[i64; INLINE_WORDS]>,
+ heap: Vec<i64>,
+}
+
+impl WordsBuf {
+ #[inline(always)]
+ fn new() -> Self {
+ Self {
+ inline: MaybeUninit::uninit(),
+ heap: Vec::new(),
+ }
+ }
+
+ /// Zero `len` words in place and expose them; like `Vec`, exhaustion
aborts.
+ #[inline]
+ fn zeroed(&mut self, len: usize) -> &mut [i64] {
+ if len <= INLINE_WORDS {
+ return self.inline_zeroed(len);
+ }
+ self.heap.resize(len, 0);
+ &mut self.heap
+ }
+
+ #[inline]
+ fn inline_zeroed(&mut self, len: usize) -> &mut [i64] {
+ debug_assert!(len <= INLINE_WORDS);
+ let words = self.inline.as_mut_ptr().cast::<i64>();
+ // Only these `len` words are ever exposed, and they are initialized
here.
+ unsafe {
+ std::ptr::write_bytes(words, 0, len);
+ std::slice::from_raw_parts_mut(words, len)
+ }
+ }
+}
+
+pub(super) fn zero_division() -> Error {
+ Error::new(ZERO_DIVISION_ERROR, "Division by zero", "")
+}
+
+fn negative_shift() -> Error {
+ Error::new(VALUE_ERROR, "Negative BigInt shift count", "")
+}
+
+fn overflow(message: &str) -> Error {
+ Error::new(OVERFLOW_ERROR, message, "")
+}
+
+/// Whether a nonempty signed-word view represents a negative integer.
+#[inline]
+pub(super) fn is_negative(x: &[i64]) -> bool {
+ x[x.len() - 1] < 0
+}
+
+/// The word that sign-extends `x` beyond its length.
+#[inline]
+pub(super) fn extension(x: &[i64]) -> u64 {
+ if is_negative(x) {
+ u64::MAX
+ } else {
+ 0
+ }
+}
+
+/// Word `i` of `x`, sign-extended past its length.
+#[inline]
+pub(super) fn word_at(x: &[i64], i: usize, extension: u64) -> u64 {
+ x.get(i).map_or(extension, |&w| w as u64)
+}
+
+/// Length after pruning redundant sign words; zero words stay zero.
+pub(super) fn normalized_len(words: &[i64]) -> usize {
+ let mut size = words.len();
+ while size > 1 && words[size - 1] == (if words[size - 2] < 0 { -1 } else {
0 }) {
+ size -= 1;
+ }
+ size
+}
+
+// ---- Inline (i64) forms. `Ok(None)` means the result needs the multiword
fallback.
+
+/// Quotient of division rounded toward zero.
+#[inline]
+pub(super) fn trunc_div_i64(a: i64, b: i64) -> Result<Option<i64>> {
+ if b == 0 {
+ return Err(zero_division());
+ }
+ // i64::MIN / -1 is the only quotient that needs promotion.
+ Ok(a.checked_div(b))
+}
+
+/// Remainder of division rounded toward zero.
+#[inline]
+pub(super) fn trunc_mod_i64(a: i64, b: i64) -> Result<Option<i64>> {
+ if b == 0 {
+ return Err(zero_division());
+ }
+ // The remainder of i64::MIN / -1 is zero, which the wrapping form yields.
+ Ok(Some(a.wrapping_rem(b)))
+}
+
+/// Quotient of division rounded down.
+#[inline]
+pub(super) fn floor_div_i64(a: i64, b: i64) -> Result<Option<i64>> {
+ if b == 0 {
+ return Err(zero_division());
+ }
+ Ok(a.checked_div(b).map(|q| {
+ // A nonexact quotient of opposite signs rounds one lower.
+ if a.wrapping_rem(b) != 0 && ((a < 0) != (b < 0)) {
+ q - 1
+ } else {
+ q
+ }
+ }))
+}
+
+/// Remainder of division rounded down.
+#[inline]
+pub(super) fn floor_mod_i64(a: i64, b: i64) -> Result<Option<i64>> {
+ if b == 0 {
+ return Err(zero_division());
+ }
+ let r = a.wrapping_rem(b);
+ // Compensate for the quotient rounding down, preserving a = q*b + r.
+ Ok(Some(if r != 0 && ((a < 0) != (b < 0)) {
+ r + b
+ } else {
+ r
+ }))
+}
+
+/// Left shift, rejecting negative counts.
+#[inline]
+pub(super) fn shl_i64(a: i64, b: i64) -> Result<Option<i64>> {
+ if b < 0 {
+ return Err(negative_shift());
+ }
+ if b == 0 || a == 0 {
+ return Ok(Some(a));
+ }
+ // For positive a require a <= i64::MAX >> b; for negative a require a >=
-2^(63-b).
+ if b >= 64 || a > (i64::MAX >> b) || a < -(1i64 << (63 - b)) {
+ return Ok(None);
+ }
+ Ok(Some(a << b))
+}
+
+/// Right shift with arithmetic sign extension; this operation cannot overflow.
+#[inline]
+pub(super) fn shr_i64(a: i64, b: i64) -> Result<i64> {
+ if b < 0 {
+ return Err(negative_shift());
+ }
+ Ok(if b >= 64 {
+ if a < 0 {
+ -1
+ } else {
+ 0
+ }
+ } else {
+ a >> b
+ })
+}
+
+// ---- Multiword fallbacks.
+
+/// Add signed integers.
+pub(super) fn add(a: &[i64], b: &[i64]) -> BigInt {
+ // One sign-extension word retains the carry out until normalization.
+ let size = a.len().max(b.len()) + 1;
+ let (ext_a, ext_b) = (extension(a), extension(b));
+ let mut carry = 0u64;
+ BigInt::build(size, |i| {
+ let (sum, c1) = word_at(a, i, ext_a).overflowing_add(word_at(b, i,
ext_b));
+ let (result, c2) = sum.overflowing_add(carry);
+ carry = u64::from(c1 | c2);
+ result as i64
+ })
+}
+
+/// Subtract signed integers: a - b = a + !b + 1 after sign extension.
+pub(super) fn sub(a: &[i64], b: &[i64]) -> BigInt {
+ let size = a.len().max(b.len()) + 1;
+ let (ext_a, ext_b) = (extension(a), extension(b));
+ let mut carry = 1u64;
+ BigInt::build(size, |i| {
+ let (sum, c1) = word_at(a, i, ext_a).overflowing_add(!word_at(b, i,
ext_b));
+ let (result, c2) = sum.overflowing_add(carry);
+ carry = u64::from(c1 | c2);
+ result as i64
+ })
+}
+
+/// Negate a signed integer: -x = !x + 1, with room for negating a minimum
value.
+pub(super) fn negate(x: &[i64]) -> BigInt {
+ let size = x.len() + 1;
+ let ext = extension(x);
+ let mut carry = 1u64;
+ BigInt::build(size, |i| {
+ let word = !word_at(x, i, ext);
+ let (result, overflow) = word.overflowing_add(carry);
+ carry = u64::from(overflow);
+ result as i64
+ })
+}
+
+/// Negate two's-complement words in place, modulo their fixed width.
+pub(super) fn negate_in_place(words: &mut [i64]) {
+ let mut carry = true;
+ for word in words.iter_mut() {
+ let (sum, overflow) = (!(*word as
u64)).overflowing_add(u64::from(carry));
+ *word = sum as i64;
+ carry = overflow;
+ }
+}
+
+/// Multiply signed integers.
+pub(super) fn mul(a: &[i64], b: &[i64]) -> BigInt {
+ let (na, nb) = (a.len(), b.len());
+ let mut buf = WordsBuf::new();
+ let data = buf.zeroed(na + nb);
+ for i in 0..na {
+ let x = u128::from(a[i] as u64);
+ let mut carry = 0u128;
+ for j in 0..nb {
+ // x*y + word + carry < 2^128: each term is below its width's
maximum.
+ let product = x * u128::from(b[j] as u64) + u128::from(data[i + j]
as u64) + carry;
+ data[i + j] = product as u64 as i64;
+ carry = product >> 64;
+ }
+ data[i + nb] = carry as u64 as i64;
+ }
+ // With stored unsigned A/B and 0/1 negative indicators neg_a/neg_b,
+ // a = A - neg_a*2^(64*n), b = B - neg_b*2^(64*m). Thus ab is AB minus
+ // neg_a*B*2^(64*n) and neg_b*A*2^(64*m); the remaining
+ // neg_a*neg_b*2^(64*(n+m)) vanishes modulo the allocated n+m words.
+ let subtract_shifted = |data: &mut [i64], x: &[i64], shift: usize| {
+ let mut borrow = 0u64;
+ for i in 0..x.len() {
+ let word = x[i] as u64;
+ let (rhs, o1) = word.overflowing_add(borrow);
+ let (result, o2) = (data[shift + i] as u64).overflowing_sub(rhs);
+ data[shift + i] = result as i64;
+ borrow = u64::from(o1 | o2);
+ }
+ };
+ if is_negative(a) {
+ subtract_shifted(data, b, na);
+ }
+ if is_negative(b) {
+ subtract_shifted(data, a, nb);
+ }
+ BigInt::from_words(data)
+}
+
+/// Apply a sign-extended bitwise operation.
+fn bitwise(a: &[i64], b: &[i64], op: impl Fn(u64, u64) -> u64) -> BigInt {
+ let size = a.len().max(b.len());
+ let (ext_a, ext_b) = (extension(a), extension(b));
+ BigInt::build(size, |i| {
+ op(word_at(a, i, ext_a), word_at(b, i, ext_b)) as i64
+ })
+}
+
+pub(super) fn and(a: &[i64], b: &[i64]) -> BigInt {
+ bitwise(a, b, |x, y| x & y)
+}
+
+pub(super) fn or(a: &[i64], b: &[i64]) -> BigInt {
+ bitwise(a, b, |x, y| x | y)
+}
+
+pub(super) fn xor(a: &[i64], b: &[i64]) -> BigInt {
+ bitwise(a, b, |x, y| x ^ y)
+}
+
+/// Complement all sign-extended bits.
+pub(super) fn not(x: &[i64]) -> BigInt {
+ BigInt::build(x.len(), |i| !x[i])
+}
+
+/// Convert a nonnegative shift count; `None` when it does not fit `usize`.
+fn shift_count(count: &[i64]) -> Result<Option<usize>> {
+ if is_negative(count) {
+ return Err(negative_shift());
+ }
+ if count[1..].iter().any(|&w| w != 0) {
+ return Ok(None);
+ }
+ Ok(usize::try_from(count[0] as u64).ok())
+}
+
+/// Shift a signed integer left, growing as needed.
+///
+/// Inlined so callers unwrap the `Result` in registers: moving a `BigInt` out
of a
+/// returned `Result` reloads it in one 16-byte read that store forwarding
misses.
+#[inline]
+pub(super) fn shl(x: &[i64], count: &[i64]) -> Result<BigInt> {
+ let shift = shift_count(count)?;
+ if x.len() == 1 && x[0] == 0 {
+ return Ok(BigInt::from_i64(0));
+ }
+ let too_large = || overflow("BigInt shift count is too large");
+ let shift = shift.ok_or_else(too_large)?;
+ let whole = shift / 64;
+ let part = (shift % 64) as u32;
+ let size = x
+ .len()
+ .checked_add(whole)
+ .and_then(|size| size.checked_add(1))
+ .ok_or_else(too_large)?;
+ let ext = extension(x);
+ BigInt::try_build(size, |i| {
+ // The low `whole` words are zero.
+ if i < whole {
+ return 0;
+ }
+ let j = i - whole;
+ let mut word = word_at(x, j, ext) << part;
+ if part != 0 && j != 0 {
+ word |= (x[j - 1] as u64) >> (64 - part);
+ }
+ word as i64
+ })
+ .ok_or_else(|| overflow("BigInt allocation is too large"))
+}
+
+/// Shift a signed integer right with sign extension; huge counts give 0 or -1.
+pub(super) fn shr(x: &[i64], count: &[i64]) -> Result<BigInt> {
+ let shift = match shift_count(count)? {
+ Some(shift) if shift / 64 < x.len() => shift,
+ _ => return Ok(BigInt::from_i64(if is_negative(x) { -1 } else { 0 })),
+ };
+ let whole = shift / 64;
+ let size = x.len() - whole;
+ let part = (shift % 64) as u32;
+ let ext = extension(x);
+ let result = BigInt::build(size, |i| {
+ let mut word = (x[i + whole] as u64) >> part;
+ // The last partial word draws its high bits from the sign extension.
+ if part != 0 {
+ word |= word_at(x, i + whole + 1, ext) << (64 - part);
+ }
+ word as i64
+ });
+ Ok(result)
+}
+
+// Absolute-value access without copying operands: negation carries through the
+// low zero words, negates the first nonzero word, then complements higher
words.
+
+/// The first nonzero index, or `x.len()` for zero.
+fn first_nonzero(x: &[i64]) -> usize {
+ x.iter().position(|&w| w != 0).unwrap_or(x.len())
+}
+
+/// Raw word `i` of the absolute value of `x`; indices beyond the view read as
zero.
+#[inline]
+fn abs_word(x: &[i64], first_nonzero: usize, i: usize) -> i64 {
+ if i >= x.len() {
+ return 0;
+ }
+ let word = x[i];
+ if !is_negative(x) {
+ return word;
+ }
+ // Negation maps [0,0,w,v] to [0,0,-w,!v] as modulo-2^64 word patterns.
+ if i < first_nonzero {
+ 0
+ } else if i == first_nonzero {
+ word.wrapping_neg()
+ } else {
+ !word
+ }
+}
+
+/// Truncating quotient and remainder with an `i64` divisor.
+///
+/// The remainder is zero or has the dividend's sign.
+pub(super) fn div_rem_single(a: &[i64], b: i64) -> Result<(BigInt, BigInt)> {
+ if b == 0 {
+ return Err(zero_division());
+ }
+ let divisor = b.unsigned_abs();
+ let first_a = first_nonzero(a);
+ let nq = a.len() + 1;
+ let mut quotient = WordsBuf::new();
+ // The top word stays zero as the sign guard.
+ let q = quotient.zeroed(nq);
+ let mut remainder = 0u64;
+ let mut shift = 0u32;
+ let mut normalized = divisor;
+ if divisor > u64::from(u32::MAX) {
+ while normalized >> 63 == 0 {
+ normalized <<= 1;
+ shift += 1;
+ }
+ }
+ let divisor_high = normalized >> 32;
+ let divisor_low = normalized as u32 as u64;
+ for i in (0..a.len()).rev() {
+ let word = abs_word(a, first_a, i) as u64;
+ let quotient_word = if divisor <= u64::from(u32::MAX) {
+ // remainder < divisor < 2^32, so each brought-down half fits u64
+ // and yields a quotient half below 2^32 while restoring the bound.
+ let high = (remainder << 32) | (word >> 32);
+ let quotient_high = high / divisor;
+ remainder = high % divisor;
+ let low = (remainder << 32) | (word as u32 as u64);
+ let quotient_low = low / divisor;
+ remainder = low % divisor;
+ (quotient_high << 32) | quotient_low
+ } else {
+ // Normalize the carried 128-bit numerator without ever shifting
by 64.
+ let high = if shift != 0 {
+ (remainder << shift) | (word >> (64 - shift))
+ } else {
+ remainder
+ };
+ let low = word << shift;
+ // Requires upper < normalized; returns a radix-2^32 quotient digit
+ // and a remainder below normalized.
+ let digit = |upper: u64, next: u64| -> (u64, u64) {
+ let mut estimate = upper / divisor_high;
+ let mut residual = upper % divisor_high;
+ // The normalized high digit bounds overestimation by two.
Check
+ // the base before multiplying, and stop before a residual
shift
+ // can overflow.
+ while estimate >= BASE || estimate * divisor_low > (residual
<< 32) + next {
+ estimate -= 1;
+ residual += divisor_high;
+ if residual >= BASE {
+ break;
+ }
+ }
+ // Wrapped subtraction is exact: the true remainder is below
normalized.
+ let rest = (upper << 32)
+ .wrapping_add(next)
+ .wrapping_sub(estimate.wrapping_mul(normalized));
+ (estimate, rest)
+ };
+ let upper = digit(high, low >> 32);
+ let lower = digit(upper.1, low as u32 as u64);
+ remainder = lower.1 >> shift;
+ (upper.0 << 32) | lower.0
+ };
+ q[i] = quotient_word as i64;
+ }
+ if is_negative(a) != (b < 0) {
+ negate_in_place(&mut q[..nq]);
+ }
+ // remainder < |b| <= 2^63 makes the conversion and signed negation safe.
+ let mut signed_remainder = remainder as i64;
+ if is_negative(a) {
+ signed_remainder = -signed_remainder;
+ }
+ Ok((BigInt::from_words(q), BigInt::from_i64(signed_remainder)))
+}
+
+/// Truncating quotient and remainder in one division pass.
+///
+/// The remainder is zero or has the dividend's sign.
+pub(super) fn div_rem(a: &[i64], b: &[i64]) -> Result<(BigInt, BigInt)> {
+ if b.len() == 1 {
+ return div_rem_single(a, b[0]);
+ }
+ let first_a = first_nonzero(a);
+ let first_b = first_nonzero(b);
+ // Count magnitude digits, dropping the signed representation's high zero
guards.
+ let digit_count = |x: &[i64], first: usize| -> usize {
+ let mut words = x.len();
+ while words > 0 && abs_word(x, first, words - 1) == 0 {
+ words -= 1;
+ }
+ if words == 0 {
+ return 0;
+ }
+ let top = abs_word(x, first, words - 1) as u64;
+ 2 * words - usize::from(top >> 32 == 0)
+ };
+ let m = digit_count(a, first_a);
+ let n = digit_count(b, first_b);
+ if m < n {
+ return Ok((BigInt::from_i64(0), BigInt::from_words(a)));
+ }
+
+ // Algorithm D in radix 2^32 keeps products and estimates in u64. Digits
below
+ // are least-significant first; the scalar dispatch left at least two in b.
+ let top_word = abs_word(b, first_b, (n - 1) / 2) as u64;
+ let mut top_digit = (top_word >> (((n - 1) % 2) * 32)) as u32;
+ let mut shift = 0u32;
+ // Normalize both inputs until B[0] >= base/2, bounding the quotient
estimate error.
+ while top_digit < (1u32 << 31) {
+ top_digit <<= 1;
+ shift += 1;
+ }
+ let nq = (m - n) / 2 + 2;
+ let nr = n.div_ceil(2) + 1;
+ // The quotient words come first, then the Algorithm D scratch, in one
buffer.
+ let capacity = nq
+ .checked_add(m + 1)
+ .and_then(|words| words.checked_add(n))
+ .ok_or_else(|| overflow("BigInt division workspace is too large"))?;
+ let mut quotient = WordsBuf::new();
+ let mut remainder = WordsBuf::new();
+ let (q, scratch) = quotient.zeroed(capacity).split_at_mut(nq);
+ let (u, v) = scratch.split_at_mut(m + 1);
+ let r = remainder.zeroed(nr);
+ let normalize = |x: &[i64], first: usize, digits: usize, out: &mut [i64]|
-> u32 {
+ let mut carry = 0u64;
+ for i in 0..digits {
+ let word = abs_word(x, first, i / 2) as u64;
+ let part = (word >> ((i % 2) * 32)) as u32 as u64;
+ let value = (part << shift) | carry;
+ out[i] = (value as u32) as i64;
+ carry = value >> 32;
+ }
+ carry as u32
+ };
+ // The dividend also keeps its shifted high carry.
+ u[m] = i64::from(normalize(a, first_a, m, &mut u[..m]));
+ normalize(b, first_b, n, &mut v[..n]);
+
+ let mut quotient_word = 0u64;
+ for j in (0..=(m - n)).rev() {
+ // Step 1: estimate q = A[0]A[1] / B[0] with A[0] = u[j+n], B[0] =
v[n-1];
+ // A[0] <= B[0], and equality is clamped so q stays a radix digit.
+ let (mut estimate, mut residual) = if u[j + n] == v[n - 1] {
+ (BASE - 1, u[j + n - 1] as u64 + v[n - 1] as u64)
+ } else {
+ let numerator = ((u[j + n] as u64) << 32) | u[j + n - 1] as u64;
+ (numerator / v[n - 1] as u64, numerator % v[n - 1] as u64)
+ };
+ // Step 2: refine q with B[1] until q*B[1] <= r*base + A[2]; at most
two
+ // decrements, and r < base guards the shift.
+ while residual < BASE && estimate * v[n - 2] as u64 > (residual << 32)
+ u[j + n - 2] as u64
+ {
+ estimate -= 1;
+ residual += v[n - 1] as u64;
+ }
+ // Step 3: subtract q * B from the window; q is correct or one too
high.
+ let mut borrow = 0u64;
+ for i in 0..n {
+ // A radix-digit product plus the incoming borrow fits u64.
+ let product = estimate * v[i] as u64 + borrow;
+ let low = product as u32;
+ let old = u[j + i] as u32;
+ u[j + i] = i64::from(old.wrapping_sub(low));
+ borrow = (product >> 32) + u64::from(old < low);
+ }
+ let old = u[j + n] as u64;
+ // Only a borrow out of the full window means the result went negative.
+ let negative = old < borrow;
+ u[j + n] = i64::from(old.wrapping_sub(borrow) as u32);
+ if negative {
+ // Step 4: decrement q and add B back, restoring 0 <= R < divisor.
+ estimate -= 1;
+ let mut carry = 0u64;
+ for i in 0..n {
+ let sum = u[j + i] as u64 + v[i] as u64 + carry;
+ u[j + i] = i64::from(sum as u32);
+ carry = sum >> 32;
+ }
+ u[j + n] = i64::from((u[j + n] as u64 + carry) as u32);
+ }
+ // Pack descending quotient digits into complete words.
+ if j % 2 == 1 {
+ quotient_word = estimate << 32;
+ } else {
+ q[j / 2] = (quotient_word | estimate) as i64;
+ }
+ }
+ // Extract the remainder, undoing the normalization shift.
+ for i in 0..nr - 1 {
+ let digit = 2 * i;
+ let mut word = u[digit] as u64;
+ if digit + 1 < n {
+ word |= (u[digit + 1] as u64) << 32;
+ }
+ word >>= shift;
+ // Bring down bits from the next digit; shift zero never evaluates a
shift by 64.
+ if shift != 0 && digit + 2 < n {
+ word |= (u[digit + 2] as u64) << (64 - shift);
+ }
+ r[i] = word as i64;
+ }
+ // The quotient takes the operand-sign XOR, a nonzero remainder the
dividend's sign.
+ if is_negative(a) != is_negative(b) {
+ negate_in_place(q);
+ }
+ if is_negative(a) {
+ negate_in_place(r);
+ }
+ Ok((BigInt::from_words(q), BigInt::from_words(r)))
+}
+
+/// Quotient rounded toward zero.
+pub(super) fn trunc_div(a: &[i64], b: &[i64]) -> Result<BigInt> {
+ Ok(div_rem(a, b)?.0)
+}
+
+/// Remainder of truncating division: zero or with the dividend's sign.
+pub(super) fn trunc_mod(a: &[i64], b: &[i64]) -> Result<BigInt> {
+ if b.len() == 1 {
+ if b[0] == 0 {
+ return Err(zero_division());
+ }
+ let divisor = b[0].unsigned_abs();
+ if divisor <= u64::from(u32::MAX) {
+ // remainder < divisor < 2^32: each brought-down half fits u64 and
the
+ // result is inline, so no quotient or allocation is needed.
+ let first = first_nonzero(a);
+ let mut remainder = 0u64;
+ for i in (0..a.len()).rev() {
+ let word = abs_word(a, first, i) as u64;
+ remainder = ((remainder << 32) | (word >> 32)) % divisor;
+ remainder = ((remainder << 32) | (word as u32 as u64)) %
divisor;
+ }
+ let result = remainder as i64;
+ return Ok(BigInt::from_i64(if is_negative(a) {
+ -result
+ } else {
+ result
+ }));
+ }
+ }
+ Ok(div_rem(a, b)?.1)
+}
+
+/// Quotient rounded toward negative infinity.
+pub(super) fn floor_div(a: &[i64], b: &[i64]) -> Result<BigInt> {
+ let (quotient, remainder) = div_rem(a, b)?;
+ if !remainder.is_zero() && is_negative(a) != is_negative(b) {
+ // With a nonzero remainder, (q-1)*b + (r+b) preserves a while
rounding down.
+ return Ok(sub(quotient.words(), &[1]));
+ }
+ Ok(quotient)
+}
+
+/// Remainder of floor division: zero or with the divisor's sign.
+pub(super) fn floor_mod(a: &[i64], b: &[i64]) -> Result<BigInt> {
+ let remainder = trunc_mod(a, b)?;
+ if !remainder.is_zero() && is_negative(a) != is_negative(b) {
+ // The floor remainder is r+b, which |r| < |b| keeps inline for a
scalar divisor.
+ if let ([divisor], Some(r)) = (b, remainder.to_i64()) {
+ return Ok(BigInt::from_i64(r + divisor));
+ }
+ return Ok(add(remainder.words(), b));
+ }
+ Ok(remainder)
+}
+
+/// Convert to the nearest double, ties to even; `OverflowError` beyond the
finite range.
+pub(super) fn to_f64(x: &[i64]) -> Result<f64> {
+ let first = first_nonzero(x);
+ let mut size = x.len();
+ while size > 0 && abs_word(x, first, size - 1) == 0 {
+ size -= 1;
+ }
+ if size == 0 {
+ return Ok(0.0);
+ }
+ let does_not_fit = || overflow("BigInt does not fit finite double");
+ if size > 16 {
+ return Err(does_not_fit());
+ }
+ let high = abs_word(x, first, size - 1) as u64;
+ let bits = (size - 1) * 64 + (64 - high.leading_zeros() as usize);
+ let shift = bits.saturating_sub(53);
+ let bit = |i: usize| ((abs_word(x, first, i / 64) as u64) >> (i % 64)) & 1;
+ let mut significand = 0u64;
+ for i in (shift..bits).rev() {
+ significand = (significand << 1) | bit(i);
+ }
+ if shift > 0 {
+ let sticky = (0..shift - 1).any(|i| bit(i) != 0);
+ if bit(shift - 1) == 1 && (sticky || significand & 1 == 1) {
+ significand += 1;
+ }
+ }
+ if bits == 1024 && significand == 1 << 53 {
+ return Err(does_not_fit());
+ }
+ let result = significand as f64 * 2f64.powi(shift as i32);
+ Ok(if is_negative(x) { -result } else { result })
+}
+
+/// Multiply magnitude words by `factor` and add `addend`, growing as needed.
+pub(super) fn mul_add_small(magnitude: &mut Vec<u64>, factor: u64, addend:
u64) {
+ let mut carry = u128::from(addend);
+ for word in magnitude.iter_mut() {
+ let product = u128::from(*word) * u128::from(factor) + carry;
+ *word = product as u64;
+ carry = product >> 64;
+ }
+ if carry != 0 {
+ magnitude.push(carry as u64);
+ }
+}
diff --git a/rust/tvm-ffi/src/big_int/mod.rs b/rust/tvm-ffi/src/big_int/mod.rs
new file mode 100644
index 00000000..07857937
--- /dev/null
+++ b/rust/tvm-ffi/src/big_int/mod.rs
@@ -0,0 +1,862 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+//! Integers with inline `i64` storage and arbitrary-precision arithmetic.
+mod int_ops;
+
+use crate::derive::Object;
+use crate::error::{Error, Result, OVERFLOW_ERROR, VALUE_ERROR};
+use crate::object::{unsafe_, Object, ObjectArc, ObjectCoreWithExtraItems};
+use crate::type_traits::AnyCompatible;
+use std::alloc::Layout;
+use std::cmp::Ordering;
+use std::ffi::c_void;
+use std::fmt::{Debug, Display, Write as _};
+use std::hash::{Hash, Hasher};
+use std::ops::{
+ Add, AddAssign, BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor,
BitXorAssign, Div, DivAssign,
+ Mul, MulAssign, Neg, Not, Rem, RemAssign, Shl, ShlAssign, Shr, ShrAssign,
Sub, SubAssign,
+};
+use std::str::FromStr;
+use std::sync::atomic::AtomicU64;
+use
tvm_ffi_sys::TVMFFIObjectDeleterFlagBitMask::kTVMFFIObjectDeleterFlagBitMaskWeak;
+use tvm_ffi_sys::TVMFFITypeIndex as TypeIndex;
+use tvm_ffi_sys::{TVMFFIAny, TVMFFIAnyDataUnion, TVMFFIObject,
COMBINED_REF_COUNT_BOTH_ONE};
+
+/// ABI stable arbitrary-precision signed integer for ffi.
+///
+/// Mirrors C++ `tvm::ffi::BigInt`: a value that fits `i64` is stored inline as
+/// `kTVMFFIInt`, and any wider value owns a `kTVMFFIBigInt` object holding its
+/// minimal two's-complement `i64` words, least-significant word first. Every
+/// operation returns that canonical form, so word-wise comparison decides
equality.
+///
+/// Arithmetic is unbounded and signed. `/` and `%` truncate toward zero;
+/// [`floor_div`](Self::floor_div) and [`floor_mod`](Self::floor_mod) round
down.
+/// Bitwise operations sign-extend infinitely, and negative shift counts are
errors.
+/// Like the primitive operators, `/`, `%`, `<<` and `>>` panic on those
errors;
+/// the `try_*` methods return them instead, as ffi callbacks need since a
panic
+/// cannot unwind across them.
+#[repr(C)]
+pub struct BigInt {
+ data: TVMFFIAny,
+}
+
+// BigIntObj for heap-allocated integers: the word count, then the canonical
+// two's-complement words as trailing items. Mirrors C++ `details::BigIntObj`.
+#[repr(C)]
+#[derive(Object)]
+#[type_key = "ffi.BigInt"]
+#[type_index(TypeIndex::kTVMFFIBigInt)]
+#[type_final]
+struct BigIntObj {
+ object: Object,
+ size: usize,
+}
+
+unsafe impl ObjectCoreWithExtraItems for BigIntObj {
+ type ExtraItem = i64;
+ #[inline]
+ /// Get the count of extra items (the logical word count)
+ fn extra_items_count(this: &Self) -> usize {
+ this.size
+ }
+}
+
+// `BigInt::try_build` allocates from the C allocator like C++
+// `make_inplace_array_object`, so it can prune the logical size in place (C++
+// `ShrinkSize`): `free` needs no layout, unlike Rust's global allocator.
+extern "C" {
+ fn malloc(size: usize) -> *mut c_void;
+ fn free(ptr: *mut c_void);
+}
+
+/// Release an object from `BigInt::try_build` like C++
`ArrayHandler::Deleter_`;
+/// the words need no destructor.
+unsafe extern "C" fn delete_obj(ptr: *mut c_void, flags: i32) {
+ if flags & kTVMFFIObjectDeleterFlagBitMaskWeak as i32 != 0 {
+ free(ptr);
+ }
+}
+
+/// Layout of an object with `len` words; `None` beyond `isize::MAX` bytes.
+fn obj_layout(len: usize) -> Option<Layout> {
+ let words = Layout::array::<i64>(len).ok()?;
+ Some(Layout::new::<BigIntObj>().extend(words).ok()?.0)
+}
+
+impl BigInt {
+ /// Create the integer zero.
+ pub fn new() -> Self {
+ Self::from_i64(0)
+ }
+
+ #[inline]
+ fn from_i64(value: i64) -> Self {
+ Self {
+ data: TVMFFIAny {
+ type_index: TypeIndex::kTVMFFIInt as i32,
+ small_str_len: 0,
+ data_union: TVMFFIAnyDataUnion { v_int64: value },
+ },
+ }
+ }
+
+ /// Take ownership of a canonical multiword object without an extra
reference.
+ #[inline]
+ fn from_obj(obj: *mut BigIntObj) -> Self {
+ Self {
+ data: TVMFFIAny {
+ type_index: TypeIndex::kTVMFFIBigInt as i32,
+ small_str_len: 0,
+ data_union: TVMFFIAnyDataUnion {
+ v_obj: obj.cast::<TVMFFIObject>(),
+ },
+ },
+ }
+ }
+
+ /// Create from two's-complement `i64` words, least-significant word first.
+ ///
+ /// Redundant sign-extension words are pruned and a value that fits `i64`
+ /// is stored inline; an empty slice is zero.
+ #[inline]
+ pub fn from_words(words: &[i64]) -> Self {
+ let size = int_ops::normalized_len(words);
+ if size <= 1 {
+ return Self::from_i64(words.first().copied().unwrap_or(0));
+ }
+ // Allocated at its final length, so the crate's generic extra-items
deleter fits.
+ unsafe {
+ let mut obj = ObjectArc::new_with_extra_items(BigIntObj {
+ object: Object::new(),
+ size,
+ });
+ BigIntObj::extra_items_mut(&mut
obj).copy_from_slice(&words[..size]);
+ Self::from_obj(ObjectArc::into_raw(obj) as *mut BigIntObj)
+ }
+ }
+
+ /// Build from `len` words, word `i` being `word(i)` called in increasing
order,
+ /// written straight into a fresh object that is then pruned in place like
C++
+ /// `Normalize`; `None` when the object cannot be allocated.
+ #[inline]
+ fn try_build(len: usize, mut word: impl FnMut(usize) -> i64) ->
Option<Self> {
+ let layout = obj_layout(len)?;
+ unsafe {
+ let obj = malloc(layout.size()).cast::<BigIntObj>();
+ if obj.is_null() {
+ return None;
+ }
+ let data = obj.add(1).cast::<i64>();
+ for i in 0..len {
+ data.add(i).write(word(i));
+ }
+ let size =
int_ops::normalized_len(std::slice::from_raw_parts(data, len));
+ if size <= 1 {
+ let value = if size == 1 { *data } else { 0 };
+ free(obj.cast());
+ return Some(Self::from_i64(value));
+ }
+ obj.cast::<TVMFFIObject>().write(TVMFFIObject {
+ combined_ref_count:
AtomicU64::new(COMBINED_REF_COUNT_BOTH_ONE),
+ type_index: TypeIndex::kTVMFFIBigInt as i32,
+ __padding: 0,
+ deleter: Some(delete_obj),
+ });
+ std::ptr::addr_of_mut!((*obj).size).write(size);
+ Some(Self::from_obj(obj))
+ }
+ }
+
+ /// Like `try_build`, but like `Vec`, exhaustion aborts.
+ #[inline]
+ fn build(len: usize, word: impl FnMut(usize) -> i64) -> Self {
+ Self::try_build(len, word).unwrap_or_else(|| {
+
std::alloc::handle_alloc_error(obj_layout(len).unwrap_or(Layout::new::<BigIntObj>()))
+ })
+ }
+
+ /// Borrow the canonical two's-complement words, least-significant word
first.
+ ///
+ /// The slice is never empty and its last word carries the sign.
+ pub fn words(&self) -> &[i64] {
+ unsafe {
+ if self.data.type_index == TypeIndex::kTVMFFIInt as i32 {
+ std::slice::from_ref(&self.data.data_union.v_int64)
+ } else {
+ let obj: &BigIntObj = &*(self.data.data_union.v_obj as *const
BigIntObj);
+ BigIntObj::extra_items(obj)
+ }
+ }
+ }
+
+ /// Whether the value is negative.
+ pub fn is_negative(&self) -> bool {
+ int_ops::is_negative(self.words())
+ }
+
+ /// Whether the value is zero.
+ #[inline]
+ pub fn is_zero(&self) -> bool {
+ self.to_i64() == Some(0)
+ }
+
+ /// Return the value when it fits `i64`.
+ #[inline]
+ pub fn to_i64(&self) -> Option<i64> {
+ if self.data.type_index == TypeIndex::kTVMFFIInt as i32 {
+ Some(unsafe { self.data.data_union.v_int64 })
+ } else {
+ None
+ }
+ }
+
+ /// Return the value when it fits `u64`.
+ pub fn to_u64(&self) -> Option<u64> {
+ match *self.words() {
+ [w0] => u64::try_from(w0).ok(),
+ [w0, 0] => Some(w0 as u64),
+ _ => None,
+ }
+ }
+
+ /// Return the value when it fits `i128`.
+ pub fn to_i128(&self) -> Option<i128> {
+ match *self.words() {
+ [w0] => Some(i128::from(w0)),
+ [w0, w1] => Some((i128::from(w1) << 64) | i128::from(w0 as u64)),
+ _ => None,
+ }
+ }
+
+ /// Return the value when it fits `u128`.
+ pub fn to_u128(&self) -> Option<u128> {
+ let combine = |w0: i64, w1: i64| (u128::from(w1 as u64) << 64) |
u128::from(w0 as u64);
+ match *self.words() {
+ [w0] => u128::try_from(w0).ok(),
+ [w0, w1] if w1 >= 0 => Some(combine(w0, w1)),
+ [w0, w1, 0] => Some(combine(w0, w1)),
+ _ => None,
+ }
+ }
+
+ /// Convert to the nearest finite double, rounding ties to even.
+ ///
+ /// Raises `OverflowError` when the value rounds beyond the finite range.
+ pub fn to_f64(&self) -> Result<f64> {
+ match self.to_i64() {
+ Some(value) => Ok(value as f64),
+ None => int_ops::to_f64(self.words()),
+ }
+ }
+
+ /// Quotient rounded toward zero; raises `ZeroDivisionError`.
+ pub fn try_div(&self, rhs: &BigInt) -> Result<BigInt> {
+ div_impl(self, rhs)
+ }
+
+ /// Remainder of truncating division, zero or with the dividend's sign.
+ pub fn try_rem(&self, rhs: &BigInt) -> Result<BigInt> {
+ rem_impl(self, rhs)
+ }
+
+ /// Truncating quotient and remainder in one pass; raises
`ZeroDivisionError`.
+ pub fn div_rem(&self, rhs: &BigInt) -> Result<(BigInt, BigInt)> {
+ if let (Some(x), Some(y)) = (self.to_i64(), rhs.to_i64()) {
+ if let Some(q) = int_ops::trunc_div_i64(x, y)? {
+ return Ok((Self::from_i64(q),
Self::from_i64(x.wrapping_rem(y))));
+ }
+ }
+ int_ops::div_rem(self.words(), rhs.words())
+ }
+
+ /// Quotient rounded toward negative infinity; raises `ZeroDivisionError`.
+ pub fn floor_div(&self, rhs: &BigInt) -> Result<BigInt> {
+ floor_div_impl(self, rhs)
+ }
+
+ /// Remainder of floor division, zero or with the divisor's sign.
+ pub fn floor_mod(&self, rhs: &BigInt) -> Result<BigInt> {
+ floor_mod_impl(self, rhs)
+ }
+
+ /// Left shift; negative counts raise `ValueError`, excessive growth
`OverflowError`.
+ pub fn try_shl<C: Into<BigInt>>(&self, count: C) -> Result<BigInt> {
+ shl_impl(self, &count.into())
+ }
+
+ /// Sign-extending right shift; negative counts raise `ValueError`.
+ pub fn try_shr<C: Into<BigInt>>(&self, count: C) -> Result<BigInt> {
+ shr_impl(self, &count.into())
+ }
+}
+
+impl Default for BigInt {
+ #[inline]
+ fn default() -> Self {
+ Self::new()
+ }
+}
+
+/// Macro to implement From for integer types that always fit i64
+macro_rules! impl_big_int_from_int {
+ ($($int_type:ty),* $(,)?) => {
+ $(
+ impl From<$int_type> for BigInt {
+ #[inline]
+ fn from(value: $int_type) -> Self {
+ Self::from_i64(value as i64)
+ }
+ }
+ )*
+ };
+}
+
+impl_big_int_from_int!(i8, i16, i32, i64, isize, u8, u16, u32);
+
+impl From<bool> for BigInt {
+ #[inline]
+ fn from(value: bool) -> Self {
+ Self::from_i64(i64::from(value))
+ }
+}
+
+impl From<u64> for BigInt {
+ fn from(value: u64) -> Self {
+ match i64::try_from(value) {
+ Ok(value) => Self::from_i64(value),
+ Err(_) => Self::from_words(&[value as i64, 0]),
+ }
+ }
+}
+
+impl From<usize> for BigInt {
+ #[inline]
+ fn from(value: usize) -> Self {
+ Self::from(value as u64)
+ }
+}
+
+impl From<i128> for BigInt {
+ fn from(value: i128) -> Self {
+ match i64::try_from(value) {
+ Ok(value) => Self::from_i64(value),
+ // The arithmetic shift keeps the sign in the high word.
+ Err(_) => Self::from_words(&[value as i64, (value >> 64) as i64]),
+ }
+ }
+}
+
+impl From<u128> for BigInt {
+ fn from(value: u128) -> Self {
+ match i64::try_from(value) {
+ Ok(value) => Self::from_i64(value),
+ // The zero guard keeps the value positive; normalization prunes
it when redundant.
+ Err(_) => Self::from_words(&[value as i64, (value >> 64) as i64,
0]),
+ }
+ }
+}
+
+impl TryFrom<f64> for BigInt {
+ type Error = Error;
+
+ /// Convert a finite double by truncating toward zero.
+ ///
+ /// NaN raises `ValueError` and infinity raises `OverflowError`.
+ fn try_from(value: f64) -> Result<Self> {
+ // The upper bound is exclusive: i64::MAX rounds up to 2^63 as a
double.
+ const LOWER: f64 = i64::MIN as f64;
+ if (LOWER..-LOWER).contains(&value) {
+ return Ok(Self::from_i64(value as i64));
+ }
+ if value.is_nan() {
+ return Err(Error::new(VALUE_ERROR, "Cannot convert NaN to BigInt",
""));
+ }
+ if value.is_infinite() {
+ return Err(Error::new(
+ OVERFLOW_ERROR,
+ "Cannot convert infinity to BigInt",
+ "",
+ ));
+ }
+ // |value| >= 2^63 is an integer: shift the 53-bit significand to its
binary exponent.
+ let bits = value.to_bits();
+ let exponent = ((bits >> 52) & 0x7ff) as i64 - 1075;
+ let significand = ((bits & ((1u64 << 52) - 1)) | (1u64 << 52)) as i64;
+ let magnitude = Self::from_i64(significand) << exponent;
+ Ok(if value < 0.0 { -magnitude } else { magnitude })
+ }
+}
+
+impl FromStr for BigInt {
+ type Err = Error;
+
+ /// Parse an optionally signed decimal integer; anything else raises
`ValueError`.
+ fn from_str(text: &str) -> Result<Self> {
+ if let Ok(value) = text.parse::<i64>() {
+ return Ok(Self::from_i64(value));
+ }
+ let (negative, digits) = match text.as_bytes().first() {
+ Some(b'-') => (true, &text[1..]),
+ Some(b'+') => (false, &text[1..]),
+ _ => (false, text),
+ };
+ if digits.is_empty() || !digits.bytes().all(|byte|
byte.is_ascii_digit()) {
+ return Err(Error::new(
+ VALUE_ERROR,
+ "Invalid decimal string for BigInt",
+ "",
+ ));
+ }
+ // Accumulate 19-digit chunks: magnitude = magnitude * 10^len + chunk.
+ let mut magnitude = Vec::new();
+ for chunk in digits.as_bytes().chunks(19) {
+ let value = chunk
+ .iter()
+ .fold(0u64, |acc, &digit| acc * 10 + u64::from(digit - b'0'));
+ int_ops::mul_add_small(&mut magnitude, 10u64.pow(chunk.len() as
u32), value);
+ }
+ let mut words: Vec<i64> = magnitude.into_iter().map(|word| word as
i64).collect();
+ words.push(0);
+ if negative {
+ int_ops::negate_in_place(&mut words);
+ }
+ Ok(Self::from_words(&words))
+ }
+}
+
+impl Clone for BigInt {
+ #[inline]
+ fn clone(&self) -> Self {
+ if self.data.type_index == TypeIndex::kTVMFFIBigInt as i32 {
+ unsafe { unsafe_::inc_ref(self.data.data_union.v_obj) }
+ }
+ Self { data: self.data }
+ }
+}
+
+impl Drop for BigInt {
+ #[inline]
+ fn drop(&mut self) {
+ if self.data.type_index == TypeIndex::kTVMFFIBigInt as i32 {
+ unsafe { unsafe_::dec_ref(self.data.data_union.v_obj) }
+ }
+ }
+}
+
+impl PartialEq for BigInt {
+ /// Canonical words make equal values word-for-word identical.
+ #[inline]
+ fn eq(&self, other: &Self) -> bool {
+ self.words() == other.words()
+ }
+}
+
+impl Eq for BigInt {}
+
+impl PartialOrd for BigInt {
+ #[inline]
+ fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+ Some(self.cmp(other))
+ }
+}
+
+impl Ord for BigInt {
+ fn cmp(&self, other: &Self) -> Ordering {
+ let (a, b) = (self.words(), other.words());
+ let (negative_a, negative_b) = (int_ops::is_negative(a),
int_ops::is_negative(b));
+ if negative_a != negative_b {
+ return if negative_a {
+ Ordering::Less
+ } else {
+ Ordering::Greater
+ };
+ }
+ // With equal signs, sign-extended words compare as unsigned from the
top.
+ let extension = int_ops::extension(a);
+ (0..a.len().max(b.len()))
+ .rev()
+ .map(|i| int_ops::word_at(a, i,
extension).cmp(&int_ops::word_at(b, i, extension)))
+ .find(|ordering| ordering.is_ne())
+ .unwrap_or(Ordering::Equal)
+ }
+}
+
+impl Hash for BigInt {
+ #[inline]
+ fn hash<H: Hasher>(&self, state: &mut H) {
+ self.words().hash(state);
+ }
+}
+
+impl Display for BigInt {
+ fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+ if let Some(value) = self.to_i64() {
+ return Display::fmt(&value, f);
+ }
+ let words = self.words();
+ let negative = words[words.len() - 1] < 0;
+ let mut magnitude = words.to_vec();
+ if negative {
+ int_ops::negate_in_place(&mut magnitude);
+ }
+ // Peel base-10^19 chunks, least significant first, by long division.
+ const CHUNK: u128 = 10_000_000_000_000_000_000;
+ let mut chunks = Vec::new();
+ while let Some(top) = magnitude.iter().rposition(|&word| word != 0) {
+ magnitude.truncate(top + 1);
+ let mut remainder = 0u128;
+ for word in magnitude.iter_mut().rev() {
+ let current = (remainder << 64) | u128::from(*word as u64);
+ *word = (current / CHUNK) as i64;
+ remainder = current % CHUNK;
+ }
+ chunks.push(remainder as u64);
+ }
+ let mut digits = String::new();
+ let mut chunks = chunks.iter().rev();
+ // A heap value is never zero, so the leading chunk always exists.
+ write!(digits, "{}", chunks.next().unwrap_or(&0))?;
+ for chunk in chunks {
+ write!(digits, "{chunk:019}")?;
+ }
+ f.pad_integral(!negative, "", &digits)
+ }
+}
+
+impl Debug for BigInt {
+ fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+ f.debug_struct("ffi.BigInt")
+ .field("data", &format_args!("{self}"))
+ .finish()
+ }
+}
+
+// ---- Arithmetic: an inline fast path, then the word fallbacks.
+#[inline]
+fn add_impl(a: &BigInt, b: &BigInt) -> BigInt {
+ if let (Some(x), Some(y)) = (a.to_i64(), b.to_i64()) {
+ if let Some(result) = x.checked_add(y) {
+ return BigInt::from_i64(result);
+ }
+ }
+ int_ops::add(a.words(), b.words())
+}
+
+#[inline]
+fn sub_impl(a: &BigInt, b: &BigInt) -> BigInt {
+ if let (Some(x), Some(y)) = (a.to_i64(), b.to_i64()) {
+ if let Some(result) = x.checked_sub(y) {
+ return BigInt::from_i64(result);
+ }
+ }
+ int_ops::sub(a.words(), b.words())
+}
+
+#[inline]
+fn mul_impl(a: &BigInt, b: &BigInt) -> BigInt {
+ if let (Some(x), Some(y)) = (a.to_i64(), b.to_i64()) {
+ if let Some(result) = x.checked_mul(y) {
+ return BigInt::from_i64(result);
+ }
+ }
+ int_ops::mul(a.words(), b.words())
+}
+
+#[inline]
+fn div_impl(a: &BigInt, b: &BigInt) -> Result<BigInt> {
+ if let (Some(x), Some(y)) = (a.to_i64(), b.to_i64()) {
+ if let Some(result) = int_ops::trunc_div_i64(x, y)? {
+ return Ok(BigInt::from_i64(result));
+ }
+ }
+ int_ops::trunc_div(a.words(), b.words())
+}
+
+#[inline]
+fn rem_impl(a: &BigInt, b: &BigInt) -> Result<BigInt> {
+ if let (Some(x), Some(y)) = (a.to_i64(), b.to_i64()) {
+ if let Some(result) = int_ops::trunc_mod_i64(x, y)? {
+ return Ok(BigInt::from_i64(result));
+ }
+ }
+ int_ops::trunc_mod(a.words(), b.words())
+}
+
+#[inline]
+fn floor_div_impl(a: &BigInt, b: &BigInt) -> Result<BigInt> {
+ if let (Some(x), Some(y)) = (a.to_i64(), b.to_i64()) {
+ if let Some(result) = int_ops::floor_div_i64(x, y)? {
+ return Ok(BigInt::from_i64(result));
+ }
+ }
+ int_ops::floor_div(a.words(), b.words())
+}
+
+#[inline]
+fn floor_mod_impl(a: &BigInt, b: &BigInt) -> Result<BigInt> {
+ if let (Some(x), Some(y)) = (a.to_i64(), b.to_i64()) {
+ if let Some(result) = int_ops::floor_mod_i64(x, y)? {
+ return Ok(BigInt::from_i64(result));
+ }
+ }
+ int_ops::floor_mod(a.words(), b.words())
+}
+
+#[inline]
+fn shl_impl(a: &BigInt, b: &BigInt) -> Result<BigInt> {
+ if let (Some(x), Some(y)) = (a.to_i64(), b.to_i64()) {
+ if let Some(result) = int_ops::shl_i64(x, y)? {
+ return Ok(BigInt::from_i64(result));
+ }
+ }
+ int_ops::shl(a.words(), b.words())
+}
+
+#[inline]
+fn shr_impl(a: &BigInt, b: &BigInt) -> Result<BigInt> {
+ if let (Some(x), Some(y)) = (a.to_i64(), b.to_i64()) {
+ return Ok(BigInt::from_i64(int_ops::shr_i64(x, y)?));
+ }
+ int_ops::shr(a.words(), b.words())
+}
+
+#[inline]
+fn and_impl(a: &BigInt, b: &BigInt) -> BigInt {
+ if let (Some(x), Some(y)) = (a.to_i64(), b.to_i64()) {
+ return BigInt::from_i64(x & y);
+ }
+ int_ops::and(a.words(), b.words())
+}
+
+#[inline]
+fn or_impl(a: &BigInt, b: &BigInt) -> BigInt {
+ if let (Some(x), Some(y)) = (a.to_i64(), b.to_i64()) {
+ return BigInt::from_i64(x | y);
+ }
+ int_ops::or(a.words(), b.words())
+}
+
+#[inline]
+fn xor_impl(a: &BigInt, b: &BigInt) -> BigInt {
+ if let (Some(x), Some(y)) = (a.to_i64(), b.to_i64()) {
+ return BigInt::from_i64(x ^ y);
+ }
+ int_ops::xor(a.words(), b.words())
+}
+
+#[inline]
+fn neg_impl(a: &BigInt) -> BigInt {
+ if let Some(negated) = a.to_i64().and_then(i64::checked_neg) {
+ return BigInt::from_i64(negated);
+ }
+ int_ops::negate(a.words())
+}
+
+#[inline]
+fn not_impl(a: &BigInt) -> BigInt {
+ if let Some(x) = a.to_i64() {
+ return BigInt::from_i64(!x);
+ }
+ int_ops::not(a.words())
+}
+
+/// The operator form of a fallible operation panics like the primitive one
would.
+macro_rules! define_op_or_panic {
+ ($($name:ident => $imp:ident),* $(,)?) => {
+ $(
+ #[inline]
+ fn $name(a: &BigInt, b: &BigInt) -> BigInt {
+ $imp(a, b).unwrap_or_else(|error| panic!("{}",
error.message()))
+ }
+ )*
+ };
+}
+
+define_op_or_panic!(
+ div_or_panic => div_impl,
+ rem_or_panic => rem_impl,
+ shl_or_panic => shl_impl,
+ shr_or_panic => shr_impl,
+);
+
+/// Forward an operator to its implementation for owned and borrowed operands,
+/// with `i64` accepted on either side as C++ does.
+macro_rules! forward_binop {
+ ($Trait:ident::$method:ident, $Assign:ident::$assign:ident, $imp:ident) =>
{
+ impl $Trait<&BigInt> for &BigInt {
+ type Output = BigInt;
+ #[inline]
+ fn $method(self, rhs: &BigInt) -> BigInt {
+ $imp(self, rhs)
+ }
+ }
+ impl $Trait<BigInt> for &BigInt {
+ type Output = BigInt;
+ #[inline]
+ fn $method(self, rhs: BigInt) -> BigInt {
+ $imp(self, &rhs)
+ }
+ }
+ impl $Trait<&BigInt> for BigInt {
+ type Output = BigInt;
+ #[inline]
+ fn $method(self, rhs: &BigInt) -> BigInt {
+ $imp(&self, rhs)
+ }
+ }
+ impl $Trait<BigInt> for BigInt {
+ type Output = BigInt;
+ #[inline]
+ fn $method(self, rhs: BigInt) -> BigInt {
+ $imp(&self, &rhs)
+ }
+ }
+ impl $Trait<i64> for &BigInt {
+ type Output = BigInt;
+ #[inline]
+ fn $method(self, rhs: i64) -> BigInt {
+ $imp(self, &BigInt::from_i64(rhs))
+ }
+ }
+ impl $Trait<i64> for BigInt {
+ type Output = BigInt;
+ #[inline]
+ fn $method(self, rhs: i64) -> BigInt {
+ $imp(&self, &BigInt::from_i64(rhs))
+ }
+ }
+ impl $Trait<&BigInt> for i64 {
+ type Output = BigInt;
+ #[inline]
+ fn $method(self, rhs: &BigInt) -> BigInt {
+ $imp(&BigInt::from_i64(self), rhs)
+ }
+ }
+ impl $Trait<BigInt> for i64 {
+ type Output = BigInt;
+ #[inline]
+ fn $method(self, rhs: BigInt) -> BigInt {
+ $imp(&BigInt::from_i64(self), &rhs)
+ }
+ }
+ impl $Assign<&BigInt> for BigInt {
+ #[inline]
+ fn $assign(&mut self, rhs: &BigInt) {
+ *self = $imp(self, rhs);
+ }
+ }
+ impl $Assign<BigInt> for BigInt {
+ #[inline]
+ fn $assign(&mut self, rhs: BigInt) {
+ *self = $imp(self, &rhs);
+ }
+ }
+ impl $Assign<i64> for BigInt {
+ #[inline]
+ fn $assign(&mut self, rhs: i64) {
+ *self = $imp(self, &BigInt::from_i64(rhs));
+ }
+ }
+ };
+}
+
+forward_binop!(Add::add, AddAssign::add_assign, add_impl);
+forward_binop!(Sub::sub, SubAssign::sub_assign, sub_impl);
+forward_binop!(Mul::mul, MulAssign::mul_assign, mul_impl);
+forward_binop!(Div::div, DivAssign::div_assign, div_or_panic);
+forward_binop!(Rem::rem, RemAssign::rem_assign, rem_or_panic);
+forward_binop!(BitAnd::bitand, BitAndAssign::bitand_assign, and_impl);
+forward_binop!(BitOr::bitor, BitOrAssign::bitor_assign, or_impl);
+forward_binop!(BitXor::bitxor, BitXorAssign::bitxor_assign, xor_impl);
+forward_binop!(Shl::shl, ShlAssign::shl_assign, shl_or_panic);
+forward_binop!(Shr::shr, ShrAssign::shr_assign, shr_or_panic);
+
+impl Neg for &BigInt {
+ type Output = BigInt;
+ #[inline]
+ fn neg(self) -> BigInt {
+ neg_impl(self)
+ }
+}
+
+impl Neg for BigInt {
+ type Output = BigInt;
+ #[inline]
+ fn neg(self) -> BigInt {
+ neg_impl(&self)
+ }
+}
+
+impl Not for &BigInt {
+ type Output = BigInt;
+ #[inline]
+ fn not(self) -> BigInt {
+ not_impl(self)
+ }
+}
+
+impl Not for BigInt {
+ type Output = BigInt;
+ #[inline]
+ fn not(self) -> BigInt {
+ not_impl(&self)
+ }
+}
+
+// ---- AnyCompatible.
+unsafe impl AnyCompatible for BigInt {
+ fn type_str() -> std::string::String {
+ "BigInt".to_string()
+ }
+
+ unsafe fn copy_to_any_view(this: &Self, data: &mut TVMFFIAny) {
+ *data = this.data;
+ }
+
+ unsafe fn move_to_any(src: Self, data: &mut TVMFFIAny) {
+ *data = src.data;
+ std::mem::forget(src);
+ }
+
+ unsafe fn check_any_strict(data: &TVMFFIAny) -> bool {
+ data.type_index == TypeIndex::kTVMFFIInt as i32
+ || data.type_index == TypeIndex::kTVMFFIBigInt as i32
+ }
+
+ unsafe fn copy_from_any_view_after_check(data: &TVMFFIAny) -> Self {
+ if data.type_index == TypeIndex::kTVMFFIBigInt as i32 {
+ unsafe { unsafe_::inc_ref(data.data_union.v_obj) }
+ }
+ Self { data: *data }
+ }
+
+ unsafe fn move_from_any_after_check(data: &mut TVMFFIAny) -> Self {
+ Self { data: *data }
+ }
+
+ unsafe fn try_cast_from_any_view(data: &TVMFFIAny) ->
std::result::Result<Self, ()> {
+ if Self::check_any_strict(data) {
+ Ok(Self::copy_from_any_view_after_check(data))
+ } else if data.type_index == TypeIndex::kTVMFFIBool as i32 {
+ Ok(Self::from_i64(data.data_union.v_int64))
+ } else {
+ Err(())
+ }
+ }
+}
diff --git a/rust/tvm-ffi/src/error.rs b/rust/tvm-ffi/src/error.rs
index f540324a..2823ba71 100644
--- a/rust/tvm-ffi/src/error.rs
+++ b/rust/tvm-ffi/src/error.rs
@@ -49,6 +49,7 @@ pub const KEY_ERROR: ErrorKind = ErrorKind("KeyError");
pub const INDEX_ERROR: ErrorKind = ErrorKind("IndexError");
pub const INTERNAL_ERROR: ErrorKind = ErrorKind("InternalError");
pub const OVERFLOW_ERROR: ErrorKind = ErrorKind("OverflowError");
+pub const ZERO_DIVISION_ERROR: ErrorKind = ErrorKind("ZeroDivisionError");
/// error object
#[repr(C)]
diff --git a/rust/tvm-ffi/src/lib.rs b/rust/tvm-ffi/src/lib.rs
index f90c88b2..5d6425c0 100644
--- a/rust/tvm-ffi/src/lib.rs
+++ b/rust/tvm-ffi/src/lib.rs
@@ -48,7 +48,7 @@ pub use crate::dtype::DLDataTypeExt;
pub use crate::error::{Error, ErrorKind, Result};
pub use crate::error::{
ATTRIBUTE_ERROR, INDEX_ERROR, INTERNAL_ERROR, KEY_ERROR, OVERFLOW_ERROR,
RUNTIME_ERROR,
- TYPE_ERROR, VALUE_ERROR,
+ TYPE_ERROR, VALUE_ERROR, ZERO_DIVISION_ERROR,
};
pub use crate::extra::module::Module;
pub use crate::extra::structural_mutate::{
diff --git a/rust/tvm-ffi/src/object.rs b/rust/tvm-ffi/src/object.rs
index 8b19b5f0..f05d1a09 100644
--- a/rust/tvm-ffi/src/object.rs
+++ b/rust/tvm-ffi/src/object.rs
@@ -418,6 +418,14 @@ pub mod unsafe_ {
}
}
+ /// Layout of a `T` followed by `count` extra items, kept at least one
word past the
+ /// header: once a weak reference outlives the data, the deleter stores
`count` there.
+ pub(crate) fn extra_items_layout<T, U>(count: usize) -> std::alloc::Layout
{
+ let size = std::mem::size_of::<T>() + count * std::mem::size_of::<U>();
+ let min_size = std::mem::size_of::<TVMFFIObject>() +
std::mem::size_of::<u64>();
+ std::alloc::Layout::from_size_align(size.max(min_size),
std::mem::align_of::<T>()).unwrap()
+ }
+
pub(crate) unsafe extern "C" fn object_deleter_for_new_with_extra_items<T,
U>(
ptr: *mut c_void,
flags: i32,
@@ -428,27 +436,25 @@ pub mod unsafe_ {
if flags == kTVMFFIObjectDeleterFlagBitMaskBoth as i32 {
let extra_items_count = T::extra_items_count(&(*obj));
std::ptr::drop_in_place(obj);
- let layout = std::alloc::Layout::from_size_align(
- std::mem::size_of::<T>() + extra_items_count *
std::mem::size_of::<U>(),
- std::mem::align_of::<T>(),
- )
- .unwrap();
- std::alloc::dealloc(ptr as *mut u8, layout);
+ std::alloc::dealloc(
+ ptr as *mut u8,
+ extra_items_layout::<T, U>(extra_items_count),
+ );
} else {
- assert_eq!(std::mem::size_of::<T>() % std::mem::size_of::<u64>(),
0);
+ // Weak references keep using the header, so the weak phase finds
the item
+ // count in the first word after it.
+ let count_slot = (ptr as *mut
u8).add(std::mem::size_of::<TVMFFIObject>()) as *mut u64;
if flags & kTVMFFIObjectDeleterFlagBitMaskStrong as i32 != 0 {
let extra_items_count = T::extra_items_count(&(*obj));
std::ptr::drop_in_place(obj);
- std::ptr::write(obj as *mut u64, extra_items_count as u64);
+ std::ptr::write(count_slot, extra_items_count as u64);
}
if flags & kTVMFFIObjectDeleterFlagBitMaskWeak as i32 != 0 {
- let extra_items_count = std::ptr::read(obj as *mut u64) as
usize;
- let layout = std::alloc::Layout::from_size_align(
- std::mem::size_of::<T>() + extra_items_count *
std::mem::size_of::<U>(),
- std::mem::align_of::<T>(),
- )
- .unwrap();
- std::alloc::dealloc(ptr as *mut u8, layout);
+ let extra_items_count = std::ptr::read(count_slot) as usize;
+ std::alloc::dealloc(
+ ptr as *mut u8,
+ extra_items_layout::<T, U>(extra_items_count),
+ );
}
}
}
@@ -520,11 +526,7 @@ impl<T: ObjectCore> ObjectArc<T> {
assert_eq!(std::mem::align_of::<T>() % std::mem::align_of::<U>(),
0);
assert_eq!(std::mem::size_of::<T>() % std::mem::align_of::<U>(),
0);
let extra_items_count = T::extra_items_count(&data);
- let layout = std::alloc::Layout::from_size_align(
- std::mem::size_of::<T>() + extra_items_count *
std::mem::size_of::<U>(),
- std::mem::align_of::<T>(),
- )
- .unwrap();
+ let layout = unsafe_::extra_items_layout::<T,
U>(extra_items_count);
let raw_data_ptr = std::alloc::alloc(layout);
if raw_data_ptr.is_null() {
std::alloc::handle_alloc_error(layout);
diff --git a/rust/tvm-ffi/tests/test_big_int.rs
b/rust/tvm-ffi/tests/test_big_int.rs
index a64baf38..24765e04 100644
--- a/rust/tvm-ffi/tests/test_big_int.rs
+++ b/rust/tvm-ffi/tests/test_big_int.rs
@@ -60,6 +60,8 @@ fn test_big_int_inline_representation() {
assert_eq!(value.to_i64(), Some(0));
}
let inline = [
+ BigInt::from(false),
+ BigInt::from(true),
BigInt::from(-1i8),
BigInt::from(i16::MIN),
BigInt::from(u32::MAX),
@@ -70,6 +72,8 @@ fn test_big_int_inline_representation() {
BigInt::from(u128::from(u64::MAX >> 1)),
];
let expected = [
+ 0,
+ 1,
-1,
i64::from(i16::MIN),
i64::from(u32::MAX),
@@ -88,49 +92,11 @@ fn test_big_int_inline_representation() {
}
#[test]
-fn test_big_int_from_bool() {
- for (input, expected) in [(false, 0i64), (true, 1)] {
- let value = BigInt::from(input);
- assert_eq!(type_index_of(&value), TypeIndex::kTVMFFIInt as i32);
- assert_eq!(value.to_i64(), Some(expected));
- }
-}
-
-/// Rebuild a double from canonical words; exact when the magnitude has at
most 53 significant bits.
-fn words_as_f64(value: &BigInt) -> f64 {
- let negative = value.is_negative();
- let mut words: Vec<u64> = value
- .words()
- .iter()
- .map(|&w| if negative { !(w as u64) } else { w as u64 })
- .collect();
- if negative {
- for word in words.iter_mut() {
- let (sum, overflow) = word.overflowing_add(1);
- *word = sum;
- if !overflow {
- break;
- }
- }
- }
- let magnitude: f64 = words
- .iter()
- .enumerate()
- .filter(|(_, &word)| word != 0)
- .map(|(i, &word)| word as f64 * 2f64.powi(64 * i as i32))
- .sum();
- if negative {
- -magnitude
- } else {
- magnitude
- }
-}
-
-#[test]
-fn test_big_int_from_f64() {
+fn test_big_int_f64_conversions() {
let cases = [
(0.0, BigInt::from(0i64)),
(-0.0, BigInt::from(0i64)),
+ (f64::MIN_POSITIVE, BigInt::from(0i64)),
(1.9, BigInt::from(1i64)),
(-1.9, BigInt::from(-1i64)),
(-0.999, BigInt::from(0i64)),
@@ -163,7 +129,7 @@ fn test_big_int_from_f64() {
let value = BigInt::try_from(input).unwrap();
assert_eq!(type_index_of(&value), TypeIndex::kTVMFFIBigInt as i32);
assert_eq!(value.is_negative(), input < 0.0);
- assert_eq!(words_as_f64(&value), input, "{input}");
+ assert_eq!(value.to_f64().unwrap(), input, "{input}");
}
assert_eq!(
BigInt::try_from(3.0 * 2f64.powi(191)).unwrap().words(),
@@ -177,6 +143,23 @@ fn test_big_int_from_f64() {
assert_eq!(error.kind(), OVERFLOW_ERROR);
assert!(error.message().contains("infinity"));
}
+
+ // Nearest double with ties to even: 2^47 is half an ulp at 2^100.
+ let x = pow2(100);
+ assert_eq!(x.to_f64().unwrap(), 2f64.powi(100));
+ assert_eq!((&x + pow2(47)).to_f64().unwrap(), 2f64.powi(100));
+ let above = f64::from_bits(2f64.powi(100).to_bits() + 1);
+ assert_eq!((&x + pow2(47) + 1i64).to_f64().unwrap(), above);
+ assert_eq!(big(i64::MIN as i128).to_f64().unwrap(), i64::MIN as f64);
+ assert_eq!((-pow2(100) - 1i64).to_f64().unwrap(), -(2f64.powi(100)));
+ let largest = BigInt::try_from(f64::MAX).unwrap();
+ assert_eq!(largest.to_f64().unwrap(), f64::MAX);
+ assert_eq!((&largest + pow2(970) - 1i64).to_f64().unwrap(), f64::MAX);
+ for value in [&largest + pow2(970), pow2(1024), -pow2(1024), pow2(1100)] {
+ let error = value.to_f64().unwrap_err();
+ assert_eq!(error.kind(), OVERFLOW_ERROR);
+ assert!(error.message().contains("finite double"));
+ }
}
#[test]
@@ -556,3 +539,676 @@ fn test_big_int_structural_traversal() {
assert_eq!(leaf, wide());
assert_eq!(leaf.words().as_ptr(), wide_pointer);
}
+
+// ============================================================================
+// Arithmetic: ported from tests/cpp/test_big_int.cc.
+// ============================================================================
+
+fn big(value: i128) -> BigInt {
+ BigInt::from(value)
+}
+
+fn pow2(bits: i64) -> BigInt {
+ &big(1) << bits
+}
+
+fn assert_inline(value: &BigInt, expected: i64) {
+ assert_eq!(
+ type_index_of(value),
+ TypeIndex::kTVMFFIInt as i32,
+ "{value}"
+ );
+ assert_eq!(value.to_i64(), Some(expected));
+}
+
+#[test]
+fn test_big_int_promotion_demotion_and_mixed_operands() {
+ let high = &big(i64::MAX as i128) + 1i64;
+ assert_eq!(type_index_of(&high), TypeIndex::kTVMFFIBigInt as i32);
+ assert_eq!(high.to_string(), "9223372036854775808");
+ assert_inline(&(&high - 1i64), i64::MAX);
+ assert_inline(&-&high, i64::MIN);
+ assert_inline(&(&high + i64::MIN), 0);
+ assert_eq!(&big(i64::MIN as i128) - 1i64, -(&high + 1i64));
+ assert_eq!(-big(i64::MIN as i128), high);
+ assert_eq!(&big(i64::MIN as i128) / -1i64, high);
+ assert_inline(&(&big(i64::MIN as i128) % -1i64), 0);
+ assert_eq!(BigInt::from(u64::MAX).to_string(), "18446744073709551615");
+ assert_eq!(1i64 + BigInt::from(u64::MAX), pow2(64));
+ assert_eq!(
+ BigInt::from(u64::MAX) - big(1),
+ &BigInt::from(u64::MAX) - 1i64
+ );
+ for (a, b) in [(i64::MAX, 17i64), (-123, 17)] {
+ let (x, y) = (BigInt::from(a), BigInt::from(b));
+ assert_eq!(&x + &y, &x + b);
+ assert_eq!(&x + &y, a + &y);
+ assert_eq!(&x - &y, &x - b);
+ assert_eq!(&x - &y, a - &y);
+ assert_eq!(&x * &y, &x * b);
+ assert_eq!(&x * &y, a * &y);
+ assert_eq!((&x * &y) / &y, x);
+ assert_eq!(&x / &y, a / &y);
+ assert_eq!(&x / &y, &x / b);
+ assert_eq!(&x % &y, a % &y);
+ assert_eq!(&x % &y, &x % b);
+ assert_eq!(&x & &y, a & &y);
+ assert_eq!(&x | &y, &x | b);
+ assert_eq!(&x ^ &y, a ^ &y);
+ assert_eq!(std::cmp::min(&x, &y), &BigInt::from(a.min(b)));
+ assert_eq!(std::cmp::max(&x, &y), &BigInt::from(a.max(b)));
+ }
+ let heap = pow2(255);
+ assert_eq!(std::cmp::min(heap.clone(), -&heap), -&heap);
+ assert_eq!(std::cmp::max(-&heap, heap.clone()), heap);
+ let mut counter = big(i64::MAX as i128);
+ counter += 1i64;
+ assert_eq!(counter, high);
+ counter -= 1i64;
+ assert_inline(&counter, i64::MAX);
+ counter -= &big(1);
+ assert_inline(&counter, i64::MAX - 1);
+}
+
+#[test]
+fn test_big_int_signed_division() {
+ // (a, b, trunc q, trunc r, floor q, floor r)
+ for (a, b, q, r, floor_q, floor_r) in [
+ (7i64, 3i64, 2i64, 1i64, 2i64, 1i64),
+ (-7, 3, -2, -1, -3, 2),
+ (7, -3, -2, 1, -3, -2),
+ (-7, -3, 2, -1, 2, -1),
+ (-6, 3, -2, 0, -2, 0),
+ (0, 3, 0, 0, 0, 0),
+ ] {
+ let (x, y) = (BigInt::from(a), BigInt::from(b));
+ assert_inline(&(&x / &y), q);
+ assert_inline(&(&x % b), r);
+ assert_inline(&x.try_div(&y).unwrap(), q);
+ assert_inline(&x.try_rem(&y).unwrap(), r);
+ assert_inline(&x.floor_div(&y).unwrap(), floor_q);
+ assert_inline(&x.floor_mod(&y).unwrap(), floor_r);
+ let (dq, dr) = x.div_rem(&y).unwrap();
+ assert_inline(&dq, q);
+ assert_inline(&dr, r);
+ // Wide operands with the same values take the multiword paths.
+ let shift = 200i64;
+ let (wx, wy) = (&x << shift, &y << shift);
+ assert_inline(&(&wx / &wy), q);
+ assert_eq!(&wx % &wy, &BigInt::from(r) << shift);
+ assert_inline(&wx.floor_div(&wy).unwrap(), floor_q);
+ assert_eq!(wx.floor_mod(&wy).unwrap(), &BigInt::from(floor_r) <<
shift);
+ }
+ // An exact multiword quotient from a dividend with low zero words and a
minimum top word.
+ assert_eq!(
+ (&big(i64::MIN as i128) << 128i64)
+ .div_rem(&pow2(64))
+ .unwrap(),
+ (-pow2(127), big(0))
+ );
+ let wide = pow2(255) + 13i64;
+ for divisor in [big(0), pow2(0) - 1i64] {
+ for result in [
+ wide.try_div(&divisor),
+ wide.try_rem(&divisor),
+ wide.floor_div(&divisor),
+ wide.floor_mod(&divisor),
+ big(0).floor_mod(&divisor),
+ big(5).try_div(&divisor),
+ wide.div_rem(&divisor).map(|pair| pair.0),
+ ] {
+ let error = result.unwrap_err();
+ assert_eq!(error.kind(), ZERO_DIVISION_ERROR);
+ assert_eq!(error.message(), "Division by zero");
+ }
+ }
+}
+
+#[test]
+#[should_panic(expected = "Division by zero")]
+fn test_big_int_division_by_zero_panics() {
+ let _ = &pow2(100) / 0i64;
+}
+
+#[test]
+#[should_panic(expected = "Negative BigInt shift count")]
+fn test_big_int_negative_shift_panics() {
+ let _ = &big(1) << -1i64;
+}
+
+#[test]
+fn test_big_int_wide_arithmetic_and_bitwise() {
+ for shift in [0i64, 63, 64, 255, 256] {
+ let x = pow2(shift);
+ assert_eq!(&x >> shift, big(1));
+ assert_eq!(-&x >> shift, big(-1));
+ assert_inline(&(&x - &x), 0);
+ assert_inline(&((&x + 3i64) - &x), 3);
+ assert_eq!(&x & -1i64, x);
+ assert_eq!(-1i64 & &x, x);
+ assert_eq!(&x | -1i64, big(-1));
+ assert_eq!(!&x, -&x - 1i64);
+ assert_eq!((&x - 1i64) ^ &x, 2i64 * &x - 1i64);
+ assert_eq!((-&x - 1i64) >> shift, big(-2));
+ assert_eq!(&x << big(2), &x * 4i64);
+ assert_eq!(1i64 << BigInt::from(shift), x);
+ assert_eq!(x.try_shl(2).unwrap(), &x * 4i64);
+ assert_eq!(x.try_shr(shift).unwrap(), big(1));
+ }
+ let huge = pow2(255);
+ assert_inline(&(&huge >> &huge), 0);
+ assert_inline(&(-&huge >> &huge), -1);
+ assert_inline(&(&big(0) << &huge), 0);
+ let error = huge.try_shl(huge.clone()).unwrap_err();
+ assert_eq!(error.kind(), OVERFLOW_ERROR);
+ assert_eq!(error.message(), "BigInt shift count is too large");
+ // A count that fits `usize` but not memory is an error, not an abort.
+ for count in [1i64 << 61, i64::MAX] {
+ let error = big(1).try_shl(count).unwrap_err();
+ assert_eq!(error.kind(), OVERFLOW_ERROR);
+ assert_eq!(error.message(), "BigInt allocation is too large");
+ }
+ assert_inline(&huge.try_shr(huge.clone()).unwrap(), 0);
+ let error = huge.try_shl(-1).unwrap_err();
+ assert_eq!(error.kind(), VALUE_ERROR);
+ let error = big(0).try_shr(-1).unwrap_err();
+ assert_eq!(error.kind(), VALUE_ERROR);
+ assert_eq!(pow2(100).to_string(), "1267650600228229401496703205376");
+ // Mixed inline/heap bitwise operands and negative heap values.
+ let negative = -pow2(200) - 5i64;
+ assert_eq!(&negative & 0xffi64, big((-5i128) & 0xff));
+ assert_eq!(&negative | 0i64, negative);
+ assert_eq!(&negative ^ &negative, big(0));
+ assert_eq!(!&negative, pow2(200) + 4i64);
+}
+
+#[test]
+fn test_big_int_independent_wide_fixture() {
+ // Decimal expectations were computed with Python integers, independently
of these operators.
+ let a: BigInt =
+
"-57896044618658097711813390734279005840776448950576999782953508207182870753808"
+ .parse()
+ .unwrap();
+ let b: BigInt =
"1361129467683753853854892183719458155744".parse().unwrap();
+ assert_eq!(
+ (&a + &b).to_string(),
+
"-57896044618658097711813390734279005839415319482893245929098616023463412598064"
+ );
+ assert_eq!(
+ (&a * &b).to_string(),
+
"-78804012392788958424676746146478616550595249492184343272504214848687229926200124701108634385188332729146218745073152"
+ );
+ assert_eq!(
+ a.floor_div(&b).unwrap().to_string(),
+ "-42535295865117307932898767499013107221"
+ );
+ assert_eq!(
+ a.floor_mod(&b).unwrap().to_string(),
+ "340250229142126476510862697120718273616"
+ );
+ assert_eq!((&a & &b).to_string(), "72903423425023200");
+ assert_eq!(
+ (&a ^ &b).to_string(),
+
"-57896044618658097711813390734279005839415319482893245929098761830310262644464"
+ );
+ assert_eq!(
+ (&a >> 97i64).to_string(),
+ "-365375409332725729551097270762435786773001928705"
+ );
+}
+
+#[test]
+fn test_big_int_from_str() {
+ for value in [
+ big(0),
+ big(-1),
+ big(i64::MIN as i128),
+ big(i64::MAX as i128),
+ pow2(63),
+ -pow2(63) - 1i64,
+ pow2(255),
+ -pow2(255),
+ wide(),
+ -wide(),
+ BigInt::from(u128::MAX),
+ ] {
+ let text = value.to_string();
+ assert_eq!(text.parse::<BigInt>().unwrap(), value, "{text}");
+ if !value.is_negative() {
+ assert_eq!(format!("+{text}").parse::<BigInt>().unwrap(), value);
+ }
+ }
+ assert_inline(&"+0007".parse::<BigInt>().unwrap(), 7);
+ assert_inline(&"-0".parse::<BigInt>().unwrap(), 0);
+ assert_eq!(
+ "1267650600228229401496703205376".parse::<BigInt>().unwrap(),
+ pow2(100)
+ );
+ assert_eq!(
+ "000000000000000000001267650600228229401496703205376"
+ .parse::<BigInt>()
+ .unwrap(),
+ pow2(100)
+ );
+ for text in ["", "+", "-", "x", "12x", " 1", "1 ", "1.0", "--1", "0x10"] {
+ let error = text.parse::<BigInt>().unwrap_err();
+ assert_eq!(error.kind(), VALUE_ERROR, "{text:?}");
+ }
+}
+
+#[test]
+fn test_big_int_multiword_division_estimates() {
+ let base = pow2(32);
+ let divisor = pow2(63) + &base - 1i64;
+ let clamp_divisor = pow2(63) + 1i64;
+ let addback_divisor = pow2(95) + 1i64;
+ let shifted_divisor = pow2(64) + 1i64;
+ let wide_quotient = pow2(64) + 7i64;
+ let wide_remainder = pow2(63) + &base + 5i64;
+ // Clamp, one/two estimate corrections, addback, and maximal normalization
shift.
+ for (a, b, q, r) in [
+ (
+ &clamp_divisor * &base - 1i64,
+ clamp_divisor.clone(),
+ &base - 1i64,
+ pow2(63),
+ ),
+ (
+ &divisor * 2i64 - 1i64,
+ divisor.clone(),
+ big(1),
+ &divisor - 1i64,
+ ),
+ (
+ &divisor * (&base - 2i64) - 1i64,
+ divisor.clone(),
+ &base - 3i64,
+ &divisor - 1i64,
+ ),
+ (
+ &addback_divisor * (&base + 1i64) - 1i64,
+ addback_divisor.clone(),
+ base.clone(),
+ pow2(95),
+ ),
+ (
+ &shifted_divisor * &wide_quotient + &wide_remainder,
+ shifted_divisor.clone(),
+ wide_quotient.clone(),
+ wide_remainder.clone(),
+ ),
+ (&divisor - 1i64, divisor.clone(), big(0), &divisor - 1i64),
+ (divisor.clone(), divisor.clone(), big(1), big(0)),
+ ] {
+ assert_eq!(a.div_rem(&b).unwrap(), (q, r), "{a} / {b}");
+ }
+}
+
+#[test]
+fn test_big_int_scalar_div_rem_boundaries() {
+ let quotient = pow2(192) + 3i64;
+ let dividend = "ient * 3i64 + 2i64;
+ let maximum_remainder = "ient * pow2(63) + i64::MAX;
+ let half_max = i64::from(u32::MAX);
+ let half_boundary = (&BigInt::from(half_max) << 64i64) - 1i64;
+ let word_quotient = BigInt::from(u64::MAX);
+ let correction_divisor = 0x400000007fffffffi64;
+ // Zero, exact/nonexact, signed scalar remainder, and the full |INT64_MIN|
bound.
+ for (a, b, q, r) in [
+ (big(0), 3i64, big(0), 0i64),
+ (big(2), 3, big(0), 2),
+ (quotient.clone(), 1, quotient.clone(), 0),
+ (-"ient * 3i64, 3, -"ient, 0),
+ ("ient * 3i64, 3, quotient.clone(), 0),
+ (dividend.clone(), 3, quotient.clone(), 2),
+ (-÷nd, 3, -"ient, -2),
+ (maximum_remainder.clone(), i64::MIN, -"ient, i64::MAX),
+ (-&maximum_remainder, i64::MIN, quotient.clone(), -i64::MAX),
+ (big(i64::MIN as i128), -1, pow2(63), 0),
+ (
+ half_boundary.clone(),
+ half_max,
+ word_quotient.clone(),
+ half_max - 1,
+ ),
+ (
+ -&half_boundary,
+ -half_max,
+ word_quotient.clone(),
+ 1 - half_max,
+ ),
+ (
+ (&BigInt::from(half_max + 1) << 64i64) - 1i64,
+ half_max + 1,
+ word_quotient.clone(),
+ half_max,
+ ),
+ // One quotient correction, then two corrections with both overflow
guards.
+ (pow2(64), half_max + 2, BigInt::from(half_max), 1),
+ (
+ (&BigInt::from(correction_divisor) << 64i64) - 1i64,
+ correction_divisor,
+ word_quotient.clone(),
+ correction_divisor - 1,
+ ),
+ ] {
+ let (dq, dr) = a.div_rem(&BigInt::from(b)).unwrap();
+ assert_eq!(dq, q, "{a} / {b}");
+ assert_inline(&dr, r);
+ }
+}
+
+#[test]
+fn test_big_int_small_divisor_remainders() {
+ let value =
+ pow2(255) | (&BigInt::from(0x12345678i64) << 128i64) |
BigInt::from(0xfedcba9876543211u64);
+ // Independent signed int32 boundary answers, plus an exact
negative-divisor remainder.
+ for (a, b, trunc, floor) in [
+ (value.clone(), -2147483648i64, 1985229329i64, -162254319i64),
+ (-&value, 2147483647, -391319368, 1756164279),
+ (-&value, -2147483648, -1985229329, -1985229329),
+ (value.clone(), 2147483647, 391319368, 391319368),
+ (pow2(255), -2147483648, 0, 0),
+ ] {
+ assert_inline(&(&a % b), trunc);
+ assert_inline(&a.floor_mod(&BigInt::from(b)).unwrap(), floor);
+ }
+}
+
+/// Deterministic xorshift64 generator for the differential test.
+struct XorShift(u64);
+
+impl XorShift {
+ fn next(&mut self) -> u64 {
+ let mut x = self.0;
+ x ^= x << 13;
+ x ^= x >> 7;
+ x ^= x << 17;
+ self.0 = x;
+ x
+ }
+
+ /// One to six words mixing carry-sensitive patterns with random bits.
+ fn big_int(&mut self) -> BigInt {
+ let len = (self.next() % 6 + 1) as usize;
+ let words: Vec<i64> = (0..len)
+ .map(|_| match self.next() % 8 {
+ 0 => 0,
+ 1 => -1,
+ 2 => i64::MIN,
+ 3 => i64::MAX,
+ 4 => 1,
+ _ => self.next() as i64,
+ })
+ .collect();
+ BigInt::from_words(&words)
+ }
+}
+
+fn abs(value: &BigInt) -> BigInt {
+ if value.is_negative() {
+ -value
+ } else {
+ value.clone()
+ }
+}
+
+#[test]
+fn test_big_int_random_algebraic_properties() {
+ let pool = [
+ big(0),
+ big(1),
+ big(-1),
+ big(i64::MIN as i128),
+ big(i64::MAX as i128),
+ pow2(63),
+ -pow2(63),
+ pow2(64),
+ -pow2(64) - 1i64,
+ BigInt::from(u64::MAX),
+ pow2(128),
+ big(i128::MIN),
+ big(i128::MAX),
+ BigInt::from(u128::MAX),
+ wide(),
+ -wide(),
+ BigInt::from_words(&[0, 0, i64::MIN, 1]),
+ pow2(255) + 13i64,
+ ];
+ let mut rng = XorShift(0x9E37_79B9_7F4A_7C15);
+ let pick = |rng: &mut XorShift| {
+ if rng.next() % 4 == 0 {
+ pool[(rng.next() % pool.len() as u64) as usize].clone()
+ } else {
+ rng.big_int()
+ }
+ };
+ let largest_double = BigInt::try_from(f64::MAX).unwrap();
+ for _ in 0..1500 {
+ let a = pick(&mut rng);
+ let b = pick(&mut rng);
+ let context = format!("a = {a}, b = {b}");
+
+ // Ring identities; every result is checked for canonical form by `==`.
+ assert_eq!(&a + &b, &b + &a, "{context}");
+ assert_eq!((&a + &b) - &b, a, "{context}");
+ assert_eq!(&a - &b, &a + -&b, "{context}");
+ assert_eq!(&a * &b, &b * &a, "{context}");
+ assert_eq!(-(&a * &b), -&a * &b, "{context}");
+ assert_eq!(!&a, -&a - 1i64, "{context}");
+ assert_eq!(&a ^ &b, (&a | &b) - (&a & &b), "{context}");
+ assert_eq!((&a & &b) + (&a | &b), &a + &b, "{context}");
+ assert_eq!(a.cmp(&b), (&a - &b).cmp(&big(0)), "{context}");
+
+ // Native integers agree wherever they can represent the operands and
result.
+ if let (Some(x), Some(y)) = (a.to_i128(), b.to_i128()) {
+ for (expected, actual) in [
+ (x.checked_add(y), &a + &b),
+ (x.checked_sub(y), &a - &b),
+ (x.checked_mul(y), &a * &b),
+ (Some(x & y), &a & &b),
+ (Some(x | y), &a | &b),
+ (Some(x ^ y), &a ^ &b),
+ ] {
+ if let Some(expected) = expected {
+ assert_eq!(actual, BigInt::from(expected), "{context}");
+ }
+ }
+ if y != 0 && !(x == i128::MIN && y == -1) {
+ assert_eq!(a.try_div(&b).unwrap(), BigInt::from(x / y),
"{context}");
+ assert_eq!(a.try_rem(&b).unwrap(), BigInt::from(x % y),
"{context}");
+ assert_eq!(
+ a.floor_div(&b).unwrap(),
+ BigInt::from(x.div_euclid(y) - i128::from((y < 0) &
(x.rem_euclid(y) != 0))),
+ "{context}"
+ );
+ }
+ }
+
+ // Division identities: a = q*b + r with the truncating and flooring
sign rules.
+ if b.is_zero() {
+ for result in [
+ a.try_div(&b),
+ a.try_rem(&b),
+ a.floor_div(&b),
+ a.floor_mod(&b),
+ ] {
+ assert_eq!(result.unwrap_err().kind(), ZERO_DIVISION_ERROR);
+ }
+ } else {
+ let (q, r) = a.div_rem(&b).unwrap();
+ assert_eq!(q, a.try_div(&b).unwrap(), "{context}");
+ assert_eq!(r, a.try_rem(&b).unwrap(), "{context}");
+ assert_eq!(&q * &b + &r, a, "{context}");
+ assert!(abs(&r) < abs(&b), "{context}");
+ assert!(
+ r.is_zero() || r.is_negative() == a.is_negative(),
+ "{context}"
+ );
+ let (fq, fr) = (a.floor_div(&b).unwrap(),
a.floor_mod(&b).unwrap());
+ assert_eq!(&fq * &b + &fr, a, "{context}");
+ assert!(abs(&fr) < abs(&b), "{context}");
+ assert!(
+ fr.is_zero() || fr.is_negative() == b.is_negative(),
+ "{context}"
+ );
+ let rounds_down = !r.is_zero() && a.is_negative() !=
b.is_negative();
+ assert_eq!(
+ fq,
+ if rounds_down { &q - 1i64 } else { q.clone() },
+ "{context}"
+ );
+ assert_eq!((&a * &b).try_div(&b).unwrap(), a, "{context}");
+ assert!((&a * &b).try_rem(&b).unwrap().is_zero(), "{context}");
+ }
+
+ // Shifts are multiplication and floor division by powers of two.
+ let count = (rng.next() % 300) as i64;
+ let shifted = a.try_shl(count).unwrap();
+ assert_eq!(shifted, &a * pow2(count), "{context}, count = {count}");
+ assert_eq!(
+ shifted.try_shr(count).unwrap(),
+ a,
+ "{context}, count = {count}"
+ );
+ assert_eq!(
+ a.try_shr(count).unwrap(),
+ a.floor_div(&pow2(count)).unwrap(),
+ "{context}, count = {count}"
+ );
+ assert_eq!(a.try_shl(-1).unwrap_err().kind(), VALUE_ERROR);
+ assert_eq!(a.try_shr(-1).unwrap_err().kind(), VALUE_ERROR);
+
+ // Text round-trips exactly; the double is the nearest representable
value.
+ assert_eq!(a.to_string().parse::<BigInt>().unwrap(), a, "{context}");
+ match a.to_f64() {
+ Ok(value) => {
+ assert!(value.is_finite());
+ let nearest = BigInt::try_from(value).unwrap();
+ let difference = abs(&(&a - &nearest));
+ let exponent = ((value.abs().to_bits() >> 52) & 0x7ff) as i64
- 1075;
+ let ulp = if exponent > 0 { pow2(exponent) } else { big(1) };
+ assert!(
+ &difference * 2i64 <= ulp,
+ "{context}: {value} is not the nearest double"
+ );
+ if abs(&a) < pow2(53) {
+ assert_eq!(nearest, a, "{context}");
+ }
+ }
+ Err(error) => {
+ assert_eq!(error.kind(), OVERFLOW_ERROR);
+ assert!(abs(&a) > largest_double, "{context}");
+ }
+ }
+ }
+}
+
+#[test]
+fn test_big_int_native_objects_cross_runtime() {
+ let echo = echo();
+ // A Rust-allocated object: shared with a C++ container and released by
C++ last.
+ let product = &wide() * &wide();
+ // wide < 2^256, so the square needs 512 bits: eight words with no sign
guard.
+ assert_eq!(product.words().len(), 8);
+ assert_eq!(AnyView::from(&product).debug_strong_count(), Some(1));
+ let array = Array::<BigInt>::try_from(
+ Function::get_global("ffi.Array")
+ .unwrap()
+ .call_tuple((&product,))
+ .unwrap(),
+ )
+ .unwrap();
+ assert_eq!(AnyView::from(&product).debug_strong_count(), Some(2));
+ let echoed =
BigInt::try_from(echo.call_tuple((&product,)).unwrap()).unwrap();
+ assert_eq!(echoed.words().as_ptr(), product.words().as_ptr());
+ let pointer = product.words().as_ptr();
+ drop(product);
+ drop(echoed);
+ let held = array.get(0).unwrap();
+ assert_eq!(held.words().as_ptr(), pointer);
+ assert_eq!(AnyView::from(&held).debug_strong_count(), Some(2));
+ drop(array);
+ assert_eq!(AnyView::from(&held).debug_strong_count(), Some(1));
+
+ // The runtime allocates an equal twin from the Rust-built words.
+ let from_runtime = {
+ let words = held.words();
+ let input = tvm_ffi_sys::TVMFFIByteArray::new(
+ words.as_ptr() as *const u8,
+ std::mem::size_of_val(words),
+ );
+ let mut raw = tvm_ffi_sys::TVMFFIAny::new();
+ assert_eq!(
+ unsafe { tvm_ffi_sys::TVMFFIBigIntFromByteArray(&input, &mut raw)
},
+ 0
+ );
+ BigInt::try_from(unsafe { Any::from_raw_ffi_any(raw) }).unwrap()
+ };
+ assert_ne!(from_runtime.words().as_ptr(), held.words().as_ptr());
+ assert_eq!(from_runtime, held);
+ // C++ hashes and compares the Rust-built key against the runtime-built
probe.
+ let map: Map<BigInt, i64> = [(held.clone(), 1i64)].into_iter().collect();
+ assert_eq!(map.get(&from_runtime).unwrap(), Some(1));
+ // Rust arithmetic on the runtime-allocated operand; equal values demote
to inline zero.
+ assert_inline(&(&held - &from_runtime), 0);
+ assert_eq!(&held + &from_runtime, &held << 1i64);
+ drop(map);
+ assert_eq!(AnyView::from(&held).debug_strong_count(), Some(1));
+}
+
+/// Hold a weak reference as C++ `WeakObjectPtr` does (`Object::IncWeakRef`)
while the
+/// last strong reference to heap `value` goes, then release it
(`Object::DecWeakRef`).
+/// Returns the (strong, weak) counts the weak reference saw and whether it
freed.
+fn outlive_with_weak_ref(value: BigInt) -> (u64, u64, bool) {
+ use std::sync::atomic::{fence, Ordering};
+ use tvm_ffi_sys::COMBINED_REF_COUNT_WEAK_ONE as WEAK_ONE;
+ unsafe {
+ let raw = Any::into_raw_ffi_any(Any::from(value));
+ let header = raw.data_union.v_obj;
+ (*header)
+ .combined_ref_count
+ .fetch_add(WEAK_ONE, Ordering::Relaxed);
+ drop(Any::from_raw_ffi_any(raw));
+ let count = (*header).combined_ref_count.load(Ordering::Relaxed);
+ let last = (*header)
+ .combined_ref_count
+ .fetch_sub(WEAK_ONE, Ordering::Release)
+ == WEAK_ONE;
+ if last {
+ fence(Ordering::Acquire);
+ let weak =
+
tvm_ffi_sys::TVMFFIObjectDeleterFlagBitMask::kTVMFFIObjectDeleterFlagBitMaskWeak;
+ ((*header).deleter.unwrap())(header.cast(), weak as i32);
+ }
+ (count & 0xFFFF_FFFF, count >> 32, last)
+ }
+}
+
+#[test]
+fn test_big_int_objects_outlived_by_weak_ref() {
+ // Both allocation paths: `from_words` (crate allocator) and an operator
result.
+ for value in [BigInt::from(u64::MAX), &wide() + &wide()] {
+ assert!(value.to_i64().is_none());
+ assert_eq!(outlive_with_weak_ref(value), (0, 1, true));
+ }
+}
+
+#[test]
+fn test_big_int_wide_results_spill_to_heap_buffers() {
+ // Results and division scratch wider than the 32-word stack buffer take
the heap path.
+ let x = &pow2(3000) + 12345i64;
+ assert_eq!(x.words().len(), 47);
+ let square = &x * &x;
+ assert_eq!(square.words().len(), 94);
+ let (quotient, remainder) = square.div_rem(&x).unwrap();
+ assert_eq!(quotient, x);
+ assert_inline(&remainder, 0);
+ assert_eq!(&x % &pow2(3000), big(12345));
+ assert_eq!(&x + &x, &x << 1i64);
+ assert_inline(&(&(-&x) + &x), 0);
+ assert_eq!(&(&x << 100i64) >> 100i64, x);
+ assert_eq!(&x & &x, x);
+ assert_inline(&(&x ^ &x), 0);
+ assert_eq!(x.to_string().parse::<BigInt>().unwrap(), x);
+}
diff --git a/rust/tvm-ffi/tests/test_object.rs
b/rust/tvm-ffi/tests/test_object.rs
index ebab18e0..a5cb1a86 100644
--- a/rust/tvm-ffi/tests/test_object.rs
+++ b/rust/tvm-ffi/tests/test_object.rs
@@ -123,6 +123,122 @@ fn test_object_arc_with_extra_items() {
assert_eq!(delete_counter.load(Ordering::Relaxed), 1);
}
+// Records the size of this thread's latest deallocation, to check the layout
an
+// object is released with.
+struct RecordingAllocator;
+
+thread_local! {
+ static LAST_DEALLOC_SIZE: std::cell::Cell<usize> = const {
std::cell::Cell::new(0) };
+}
+
+unsafe impl std::alloc::GlobalAlloc for RecordingAllocator {
+ unsafe fn alloc(&self, layout: std::alloc::Layout) -> *mut u8 {
+ std::alloc::System.alloc(layout)
+ }
+
+ unsafe fn dealloc(&self, ptr: *mut u8, layout: std::alloc::Layout) {
+ let _ = LAST_DEALLOC_SIZE.try_with(|size| size.set(layout.size()));
+ std::alloc::System.dealloc(ptr, layout)
+ }
+}
+
+#[global_allocator]
+static ALLOCATOR: RecordingAllocator = RecordingAllocator;
+
+/// Drops `obj_arc` while a weak reference outlives it, held the way C++
`WeakObjectPtr`
+/// does (`Object::IncWeakRef`, then `Object::DecWeakRef`). `expired` runs
while only the
+/// weak reference is left. Returns the size the allocation is freed with.
+fn release_outlived_by_weak_ref<T: ObjectCore>(
+ mut obj_arc: ObjectArc<T>,
+ expired: impl FnOnce(),
+) -> usize {
+ use std::sync::atomic::fence;
+ use tvm_ffi_sys::COMBINED_REF_COUNT_WEAK_ONE as WEAK_ONE;
+ unsafe {
+ let header = ObjectArc::as_raw_mut(&mut obj_arc) as *mut TVMFFIObject;
+ (*header)
+ .combined_ref_count
+ .fetch_add(WEAK_ONE, Ordering::Relaxed);
+ drop(obj_arc);
+ // The data is dropped; the weak reference still sees an intact,
expired header.
+ assert_eq!(
+ (*header).combined_ref_count.load(Ordering::Relaxed),
+ WEAK_ONE
+ );
+ expired();
+ // The last weak reference frees the full allocation.
+ let old = (*header)
+ .combined_ref_count
+ .fetch_sub(WEAK_ONE, Ordering::Release);
+ assert_eq!(old, WEAK_ONE);
+ fence(Ordering::Acquire);
+ let weak =
tvm_ffi_sys::TVMFFIObjectDeleterFlagBitMask::kTVMFFIObjectDeleterFlagBitMaskWeak;
+ ((*header).deleter.unwrap())(header.cast(), weak as i32);
+ }
+ LAST_DEALLOC_SIZE.with(|size| size.get())
+}
+
+#[test]
+fn test_object_arc_with_extra_items_outlived_by_weak_ref() {
+ let delete_counter = Arc::new(AtomicU32::new(0));
+ let obj_arc = ObjectArc::new_with_extra_items(TestIntObj::new(13,
delete_counter.clone(), 10));
+ let freed = release_outlived_by_weak_ref(obj_arc, || {
+ assert_eq!(delete_counter.load(Ordering::Relaxed), 1);
+ });
+ assert_eq!(
+ freed,
+ std::mem::size_of::<TestIntObj>() + 10 * std::mem::size_of::<u64>()
+ );
+}
+
+// Only the header, with a fixed number of items after it.
+#[repr(C)]
+struct HeaderOnlyObj<const N: usize> {
+ object: Object,
+}
+
+unsafe impl<const N: usize> ObjectCore for HeaderOnlyObj<N> {
+ const TYPE_KEY: &'static str = Object::TYPE_KEY;
+ const TYPE_DEPTH: i32 = Object::TYPE_DEPTH;
+ #[inline]
+ fn type_index() -> i32 {
+ Object::type_index()
+ }
+ #[inline]
+ unsafe fn object_header_mut(this: &mut Self) -> &mut TVMFFIObject {
+ Object::object_header_mut(&mut this.object)
+ }
+}
+
+unsafe impl<const N: usize> ObjectCoreWithExtraItems for HeaderOnlyObj<N> {
+ type ExtraItem = u64;
+ #[inline]
+ fn extra_items_count(_: &Self) -> usize {
+ N
+ }
+}
+
+#[test]
+fn test_header_only_object_with_extra_items_outlived_by_weak_ref() {
+ // The item count is kept in the word after the header: the first item for
N = 2,
+ // padding the allocation reserves for N = 0.
+ let header_size = std::mem::size_of::<TVMFFIObject>();
+ let obj_arc = ObjectArc::new_with_extra_items(HeaderOnlyObj::<2> {
+ object: Object::new(),
+ });
+ assert_eq!(
+ release_outlived_by_weak_ref(obj_arc, || {}),
+ header_size + 16
+ );
+ let obj_arc = ObjectArc::new_with_extra_items(HeaderOnlyObj::<0> {
+ object: Object::new(),
+ });
+ assert_eq!(
+ release_outlived_by_weak_ref(obj_arc, || {}),
+ header_size + 8
+ );
+}
+
#[test]
fn test_object_arc_from_raw() {
unsafe {
