Module ramp::ll [−][src]
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
base |
Base conversion utilities |
limb | |
limb_ptr | |
pow |
Functions
add⚠ | |
add_1⚠ | |
add_n⚠ |
Adds the |
addmul_1⚠ |
Multiplies the |
and_n⚠ |
Performs a bitwise "and" ( |
and_not_n⚠ |
Performs a bitwise and of the n least signficant limbs of |
cmp⚠ |
Compares the |
copy_decr⚠ |
Copies the |
copy_incr⚠ |
Copies the |
copy_rest⚠ |
Copies the |
decr⚠ | |
divide_by_zero |
Called when a divide by zero occurs. |
divrem⚠ |
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}. |
divrem_1⚠ |
Divides the |
divrem_2⚠ | |
gcd⚠ | |
incr⚠ | |
is_zero⚠ |
Checks that all |
mul⚠ |
Multiplies |
mul_1⚠ |
Multiplies the |
nand_n⚠ |
Performs a bitwise "nand" of the n least signficant limbs of |
nor_n⚠ |
Performs a bitwise "nor" of the n least signficant limbs of |
normalize⚠ |
Returns the size of the integer pointed to by |
not⚠ |
Performs a bitwise inversion ("not") of the n least signficant limbs of |
or_n⚠ |
Performs a bitwise "or" ( |
or_not_n⚠ |
Performs a bitwise "or" of the n least signficant limbs of |
overlap⚠ | |
same_or_decr⚠ | |
same_or_incr⚠ | |
same_or_separate⚠ | |
scan_0⚠ |
Scans for the first 0 bit starting from the least-significant bit the the most, returning the bit index. |
scan_1⚠ |
Scans for the first 1 bit starting from the least-significant bit the the most, returning the bit index. |
shl⚠ |
Performs a bit-shift of the limbs in {xp, xs}, left by |
shr⚠ |
Performs a bit-shift of the limbs in {xp, xs}, right by |
sqr⚠ |
Squares the number in |
sub⚠ | |
sub_1⚠ | |
sub_n⚠ |
Subtracts the |
submul_1⚠ |
Multiplies the |
twos_complement⚠ |
Computes the two's complement of the |
xor_n⚠ |
Performs a bitwise "xor" ( |
zero⚠ |