Seven-Streams opened a new pull request, #815:
URL: https://github.com/apache/tvm-ffi/pull/815
[FEAT][RUST] Native BigInt arithmetic, ported from the C++ int_ops
Stacked on #804, which adds the `BigInt` value type with C++-backed
construction. Only the commits after that branch belong here.
## 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 that 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.
The memory model differs from C++ on purpose. C++ builds each result inside a
freshly allocated object and prunes its length afterwards, which in Rust
would
need a private allocator with a capacity prefix and its own deleter. Here
every
algorithm writes into `WordsBuf`, a 32-word stack buffer that spills to a
`Vec`, and finishes with `from_words`, which allocates the object at its
final
length through `ObjectArc::new_with_extra_items` as `Shape` and `String` do.
A result that fits `i64` never touches the heap, the crate's generic deleter
releases every object, and the loops themselves are unchanged.
Benchmarks against the C++ operators on the same machine (ns/op, lower is
better):
| operation | Rust | C++ |
| --- | ---: | ---: |
| add, 4 words + 1 | 23.5 | 15.3 |
| multiply, 4 x 4 words | 31.1 | 36.9 |
| divide, 4 words / 1 | 41.3 | 34.3 |
| divide, 4 words / 4 | 64.2 | 61.5 |
| shift left by 70 | 27.1 | 17.4 |
| heap construction | 15.5 | 13.0 |
| to decimal, 4 words | 192 | 628 |
Allocation now costs about the same on both sides; the remaining gap on add
and shift is loop code generation, which the C++ compiler turns into a
straight carry chain.
## Testing
- `cargo test -p tvm-ffi`: **286 passed**. `tests/test_big_int.rs` grows to
26
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.
- 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` and `clippy` clean on the new files. No C++ changes.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
