Expand description
This module provides the low-level operations for working with arbitrary precision numbers.
Overview
This module forms the core of the library. As such, the functions are required to be highly
performant, even small inefficiencies can cause a large impact given how frequently some of
these functions are called. addmul
for example is one of the most frequently called functions
in the library, so an efficiencies there will be multiplied out to almost the entire library.
There are no real restrictions on the functions that can implemented in here. Exposed functions should be generally useful to high-level code, but otherwise any operation that can be more efficiently implemented here and then exposed by a higher-level API is a candidate.
The functions in this module assume that all inputs are valid, though some checking is performed in debug builds.
Limbs
A Limb
is a single “digit” in an arbitrary-precision integer. To explain, consider the
standard base we work in, base-10. Base-10 uses represents numbers as a sequence of the digits
0-9. The number 251 is 2 x 10^2 + 5 x 10^1 + 1 x 10^0. Similarly base-16 (hexadecimal) uses
sixteen digits and a base of 16 to represent numbers.
A Limb
is one word, with N bits (32 on a 32-bit platform, 64 on a 64-bit platform), so it can
represent 2^N unique values. It can therefore form the basis of a base-2^N number system. The
word “Limb” is used by GMP to distinguish it from a regular numerical digit, and there is no
obvious reason to use different terminology.
Limb
itself implements a number of useful methods. The basic mathematical operators are
implemented to provide wrapping behaviour by default. The most basic operations are also
implemented on Limb
, notably multiplication with a two-word output and division of a two-word
numerator by a one-word denominator. The implementations of these operations are done with
inline assembly on x86 platforms with a Rust implementation as fallback.
Integer representation
Integers are passed around as pointers to a series of Limb
s. The limbs are stored
least-significant first. If required, a size parameter is also provided, but otherwise is
omitted when it can be inferred from other sources of information. This is the case with the
output pointers used to store the result, they are assumed to have enough memory store the
result as the maximum output size is bounded by the size of the inputs.
The integers are not required to be “normalized” in most cases. That is, they may have zero-value limbs in the highest positions. Functions should aim to avoid requiring normalized integers but otherwise explicitly document said requirement.
Memory allocation
No function will allocate memory for a return value. However, it is sometimes required to allocate “scratch space” for storing intermediate values. This scratch space is always temporary and freed before the function returns. Functions that need to make heavy use of scratch space while also being recursive, are split so that scratch space can be re-used.
Argument Conventions
There are no hard-and-fast rules for the argument conventions in this module. There are however some general conventions:
- Output/Result pointer goes first (if applicable).
- Pointer and matching size are kept close together in the argument list.
- Sizes come after the matching pointers. For example,
add_n
takes two pointers and a length, the length applies to both pointers and so comes after both of them.
Modules
Functions
Adds the n
least signficant limbs of xp
and yp
, storing the result in {wp, n}.
If there was a carry, it is returned.
Multiplies the n
least-signficiant digits of xp
by vl
and adds them to the n
least-significant digits of wp
. Returns the highest limb of the result.
Performs a bitwise “and” (&
) of the n least signficant limbs of xp
and yp
, storing the
result in wp
Performs a bitwise and of the n least signficant limbs of xp
and yp
, with the limbs of yp
being first inverted. The result is stored in wp
.
Compares the n
least-significant limbs of xp
and yp
, returning whether
{xp, n} is less than, equal to or greater than {yp, n}
Called when a divide by zero occurs.
Divides {np, ns} by {dp, ds}. If ns <= ds, the quotient is stored in {qp, 1}, otherwise the quotient is stored to {qp, (ns - ds) + 1}. The remainder is always stored to {rp, ds}.
Multiplies the n
least-significant limbs of xp
by vl
storing the n
least-significant
limbs of the product in {wp, n}
.
Performs a bitwise “nand” of the n least signficant limbs of xp
and yp
, storing the
result in wp
Performs a bitwise “nor” of the n least signficant limbs of xp
and yp
, storing the
result in wp
Returns the size of the integer pointed to by p
such that the most
significant limb is non-zero.
Performs a bitwise inversion (“not”) of the n least signficant limbs of xp
, storing the
result in wp
Performs a bitwise “or” (|
) of the n least signficant limbs of xp
and yp
, storing the
result in wp
Performs a bitwise “or” of the n least signficant limbs of xp
and yp
, with the limbs of yp
being first inverted. The result is stored in wp
.
Scans for the first 0 bit starting from the least-significant bit the the most, returning the bit index.
Scans for the first 1 bit starting from the least-significant bit the the most, returning the bit index.
Performs a bit-shift of the limbs in {xp, xs}, left by cnt
bits storing the result in {rp,
rs}. The top-most shifted bits are returned.
Performs a bit-shift of the limbs in {xp, xs}, right by cnt
bits storing the result in {rp,
rs}. The bottom-most shifted bits are returned.
Squares the number in {xp, xs}
storing the result in {wp, xs*2}
.
This is slightly more efficient than regular multiplication with both
inputs the same.
Subtracts the n
least signficant limbs of yp
from xp
, storing the result in {wp, n}.
If there was a borrow from a higher-limb (i.e., the result would be negative), it is returned.
Multiplies the n
least-signficiant digits of xp
by vl
and subtracts them from the n
least-significant digits of wp
. Returns the highest limb of the result, adjust for borrow.
Computes the two’s complement of the xs
least significant words
of xp
. The result is stored the result in wp
, and a carry is
returned, if there is one.
Performs a bitwise “xor” (^
) of the n least signficant limbs of xp
and yp
, storing the
result in wp