intn.c

Include dependency graph for intn.c:

Defines

USE_64BIT_MUL

UINT16_IN_A_DIGIT (sizeof(intn_digit_t) / sizeof(uint16_t))

INTN_DIVMNU_MAX_IN_LEN (INTN_MAX_IN_LEN + 1)

MIN(a, b) (((a) < (b)) ? (a) : (b))

MAX(a, b) (((a) > (b)) ? (a) : (b))

HAS_BUILTIN(x) 0

Typedefs

typedef intn_digit_t (*bit_op_t)(intn_digit_t a, intn_digit_t b)

Functions

static size_t neg_and_count_in_place(intn_digit_t out[], size_t len)

static inline size_t pad_uint16_to_digits(uint16_t n16[], size_t n16_len)

static void mulmnu32(const uint32_t u[], size_t m, const uint32_t v[], size_t n, uint32_t w[])

void intn_mulu(const uint32_t m[], size_t m_len, const uint32_t n[], size_t n_len, uint32_t out[])

Multiply two unsigned multi-precision integers.

Performs multiplication of magnitudes only, without considering signs.

Note

Accepts both normalized and non-normalized inputs

Note

Based on algorithms from Hacker’s Delight

Parameters:

m – First multiplicand
m_len – Length of first multiplicand in digits
n – Second multiplicand
n_len – Length of second multiplicand in digits
out – [out] Result buffer (must have at least INTN_MUL_OUT_LEN(m_len, n_len) digits)

Pre:

out buffer must be at least INTN_MUL_OUT_LEN(m_len, n_len) digits

Post:

Exactly m_len + n_len digits are written (some may be zero)

Post:

Result may have leading zeros (not normalized)

void intn_mul_int64(int64_t num1, int64_t num2, intn_digit_t *out, intn_integer_sign_t *out_sign)

Multiply two 64-bit signed integers (int64_t) producing multi-precision result.

Specialized multiplication for int64_t values that may overflow.

Parameters:

num1 – First multiplicand
num2 – Second multiplicand
out – [out] Result buffer (must have at least INTN_MUL_OUT_LEN(INTN_INT64_LEN,INTN_INT64_LEN) digits)
out_sign – [out] Sign of result

Pre:

out buffer must be at least INTN_MUL_OUT_LEN(INTN_INT64_LEN, INTN_INT64_LEN) digits

Post:

Exactly INTN_INT64_LEN + INTN_INT64_LEN digits are written

static size_t count16(const uint16_t *num, size_t num_len)

static inline uint32_t uint32_nlz(uint32_t x)

static int divmnu16(uint16_t q[], uint16_t r[], const uint16_t u[], const uint16_t v[], int m, int n)

static void big_endian_digits_to_uint16(const intn_digit_t num[], size_t len, uint16_t dest_buf[])

static void big_endian_uint16_to_digit_in_place(uint16_t num16[], size_t len16)

size_t intn_divu(const intn_digit_t m[], size_t m_len, const intn_digit_t n[], size_t n_len, intn_digit_t q_out[], intn_digit_t r_out[], size_t *r_out_len)

Divide two unsigned multi-precision integers with optional remainder.

Performs division of magnitudes m / n, computing quotient and optionally remainder.

Note

Accepts both normalized and non-normalized inputs

Note

Based on algorithms from Hacker’s Delight

Parameters:

m – Dividend
m_len – Length of dividend in digits
n – Divisor (must not be zero)
n_len – Length of divisor in digits
q_out – [out] Quotient buffer (must have at least INTN_DIV_OUT_LEN(m_len, n_len) digits)
r_out – [out] Remainder buffer (may be NULL, else must have at least INTN_REM_OUT_LEN(m_len, n_len) digits)
r_out_len – [out] Length of remainder (may be NULL if r_out is NULL)

Returns:

Length of quotient in digits

Pre:

n must not be zero

Pre:

q_out buffer must be at least INTN_DIV_OUT_LEN(m_len, n_len) digits

Pre:

r_out buffer (if not NULL) must be at least INTN_REM_OUT_LEN(m_len, n_len) digits

Post:

Quotient and remainder may have leading zeros (not normalized)

int intn_cmp(const intn_digit_t a[], size_t a_len, const intn_digit_t b[], size_t b_len)

Compare two unsigned multi-precision integers.

Compares the magnitude of two multi-precision integers, ignoring sign. Accepts both normalized and non-normalized inputs.

Note

Leading zeros are ignored in comparison

Note

Accepts both normalized and non-normalized inputs

Parameters:

a – First integer array
a_len – Length of first integer in digits
b – Second integer array
b_len – Length of second integer in digits

Returns:

-1 if a < b, 0 if a == b, 1 if a > b

size_t intn_addu(const intn_digit_t a[], size_t a_len, const intn_digit_t b[], size_t b_len, intn_digit_t out[])

Add two unsigned multi-precision integers.

Performs addition of magnitudes only, without considering signs (similar to unsigned addition).

Note

Accepts both normalized and non-normalized inputs

Parameters:

a – First addend
a_len – Length of first addend in digits
b – Second addend
b_len – Length of second addend in digits
out – [out] Result buffer (must have at least INTN_ADD_OUT_LEN(a_len, b_len) digits)

Returns:

Actual length of result in digits (may be less than buffer size)

Pre:

out buffer must be at least INTN_ADD_OUT_LEN(a_len, b_len) digits

Post:

Result may have leading zeros (not normalized)

size_t intn_add(const intn_digit_t m[], size_t m_len, intn_integer_sign_t m_sign, const intn_digit_t n[], size_t n_len, intn_integer_sign_t n_sign, intn_digit_t out[], intn_integer_sign_t *out_sign)

Add two signed multi-precision integers.

Performs signed addition of two multi-precision integers with separate signs.

Note

Accepts both normalized and non-normalized inputs

Parameters:

m – First addend magnitude
m_len – Length of first addend in digits
m_sign – Sign of first addend
n – Second addend magnitude
n_len – Length of second addend in digits
n_sign – Sign of second addend
out – [out] Result buffer (must have at least INTN_ADD_OUT_LEN(m_len, n_len) digits)
out_sign – [out] Sign of result

Returns:

Actual length of result in digits (may be less than buffer size)

Pre:

out buffer must be at least INTN_ADD_OUT_LEN(m_len, n_len) digits

Post:

Result may have leading zeros (not normalized)

size_t intn_add_int64(int64_t num1, int64_t num2, intn_digit_t *out, intn_integer_sign_t *out_sign)

Add two 64-bit signed integers (int64_t) producing multi-precision result.

Specialized addition for int64_t values that may overflow.

Parameters:

num1 – First 64-bit addend
num2 – Second 64-bit addend
out – [out] Result buffer (must have at least INTN_ADD_OUT_LEN(INTN_INT64_LEN,INTN_INT64_LEN) digits)
out_sign – [out] Sign of result

Returns:

Actual length of result in digits

Pre:

out buffer must be at least INTN_ADD_OUT_LEN(INTN_INT64_LEN, INTN_INT64_LEN) digits

size_t intn_subu(const intn_digit_t a[], size_t a_len, const intn_digit_t b[], size_t b_len, intn_digit_t out[])

Subtract two unsigned multi-precision integers.

Performs subtraction of magnitudes only (a - b) where a must be >= b.

Note

Accepts both normalized and non-normalized inputs

Parameters:

a – Minuend (must be >= b)
a_len – Length of minuend in digits
b – Subtrahend
b_len – Length of subtrahend in digits
out – [out] Result buffer (must have at least INTN_SUB_OUT_LEN(a_len, b_len) digits)

Returns:

Actual length of result in digits (may be less than buffer size)

Pre:

a >= b (use intn_cmp to verify if needed)

Pre:

out buffer must be at least INTN_SUB_OUT_LEN(a_len, b_len) digits

Post:

Result may have leading zeros (not normalized)

size_t intn_sub(const intn_digit_t m[], size_t m_len, intn_integer_sign_t m_sign, const intn_digit_t n[], size_t n_len, intn_integer_sign_t n_sign, intn_digit_t out[], intn_integer_sign_t *out_sign)

Subtract two signed multi-precision integers.

Performs signed subtraction (m - n) with separate signs.

Note

Accepts both normalized and non-normalized inputs

Parameters:

m – Minuend magnitude
m_len – Length of minuend in digits
m_sign – Sign of minuend
n – Subtrahend magnitude
n_len – Length of subtrahend in digits
n_sign – Sign of subtrahend
out – [out] Result buffer (must have at least INTN_SUB_OUT_LEN(m_len, n_len) digits)
out_sign – [out] Sign of result

Returns:

Actual length of result in digits (may be less than buffer size)

Pre:

out buffer must be at least INTN_SUB_OUT_LEN(m_len, n_len) digits

Post:

Result may have leading zeros (not normalized)

size_t intn_sub_int64(int64_t num1, int64_t num2, intn_digit_t *out, intn_integer_sign_t *out_sign)

Subtract two 64-bit signed integers (int64_t) producing multi-precision result.

Specialized subtraction for int64_t values that may overflow.

Parameters:

num1 – Minuend
num2 – Subtrahend
out – [out] Result buffer (must have at least INTN_SUB_OUT_LEN(INTN_INT64_LEN,INTN_INT64_LEN) digits)
out_sign – [out] Sign of result

Returns:

Actual length of result in digits

Pre:

out buffer must be at least INTN_SUB_OUT_LEN(INTN_INT64_LEN, INTN_INT64_LEN) digits

static void neg(const intn_digit_t in[], size_t in_len, intn_digit_t out[])

static void cond_neg(intn_integer_sign_t sign, const intn_digit_t in[], size_t in_len, intn_digit_t out[])

static size_t prepare_working_buf(const intn_digit_t m[], size_t m_len, intn_integer_sign_t m_sign, const intn_digit_t n[], size_t n_len, intn_integer_sign_t n_sign, const intn_digit_t *b[], size_t *b_len, intn_integer_sign_t *b_sign, intn_digit_t out[])

static inline void signed_bitwise(const intn_digit_t b[], size_t b_len, intn_integer_sign_t b_sign, intn_digit_t out[], size_t out_len, bit_op_t bit_op)

static inline intn_integer_sign_t sign_bitwise(intn_integer_sign_t m_sign, intn_integer_sign_t n_sign, bit_op_t bit_op)

static inline size_t count_and_normalize_sign(const intn_digit_t num[], size_t len, intn_integer_sign_t sign, intn_integer_sign_t *out_sign)

static inline intn_digit_t digit_bor(intn_digit_t a, intn_digit_t b)

size_t intn_bor(const intn_digit_t m[], size_t m_len, intn_integer_sign_t m_sign, const intn_digit_t n[], size_t n_len, intn_integer_sign_t n_sign, intn_digit_t out[], intn_integer_sign_t *out_sign)

Bitwise OR of two signed multi-precision integers.

Performs bitwise OR by internally converting to two’s complement, applying the operation, then converting back to sign-magnitude form.

// Example: 0xFFFFFFFF00000000000012345678 | -1
// Input: {0x12345678, 0x0, 0xFFFF0000, 0xFFFF} | {0x1} with negative sign
// Internal two's complement: {0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}
// Result: {0x1, 0x0, 0x0, 0x0} with negative sign (equals -1)

Note

Input and output are in sign-magnitude form, not two’s complement

Note

Accepts both normalized and non-normalized inputs

Parameters:

m – First operand magnitude
m_len – Length of first operand in digits
m_sign – Sign of first operand
n – Second operand magnitude
n_len – Length of second operand in digits
n_sign – Sign of second operand
out – [out] Result buffer (must have at least MAX_LEN(m_len, n_len) + 1 digits)
out_sign – [out] Sign of result

Returns:

Length of result in digits

Pre:

out buffer must be at least MAX_LEN(m_len, n_len) + 1 digits

Post:

Result may have leading zeros (not normalized)

static inline intn_digit_t digit_band(intn_digit_t a, intn_digit_t b)

size_t intn_band(const intn_digit_t m[], size_t m_len, intn_integer_sign_t m_sign, const intn_digit_t n[], size_t n_len, intn_integer_sign_t n_sign, intn_digit_t out[], intn_integer_sign_t *out_sign)

Bitwise AND of two signed multi-precision integers.

Performs bitwise AND by internally converting to two’s complement, applying the operation, then converting back to sign-magnitude form.

// Example: 0xFFFFFFFFF123456789ABFFFFFFFF & -0xFFFFFFFF000000000000FFFFFFFF
// Input: {0xFFFFFFFF, 0x456789AB, 0xFFFFF123, 0xFFFF} &
//        {0xFFFFFFFF, 0x0, 0xFFFF0000, 0xFFFF} with negative sign
// Result: {0x1, 0x456789AB, 0xF123} (equals 0xF123456789AB00000001)

Note

Input and output are in sign-magnitude form, not two’s complement

Note

Accepts both normalized and non-normalized inputs

Parameters:

m – First operand magnitude
m_len – Length of first operand in digits
m_sign – Sign of first operand
n – Second operand magnitude
n_len – Length of second operand in digits
n_sign – Sign of second operand
out – [out] Result buffer (must have at least MAX_LEN(m_len, n_len) + 1 digits)
out_sign – [out] Sign of result

Returns:

Length of result in digits

Pre:

out buffer must be at least MAX_LEN(m_len, n_len) + 1 digits

Post:

Result may have leading zeros (not normalized)

static inline intn_digit_t digit_bxor(intn_digit_t a, intn_digit_t b)

size_t intn_bxor(const intn_digit_t m[], size_t m_len, intn_integer_sign_t m_sign, const intn_digit_t n[], size_t n_len, intn_integer_sign_t n_sign, intn_digit_t out[], intn_integer_sign_t *out_sign)

Bitwise XOR of two signed multi-precision integers.

Performs bitwise XOR by internally converting to two’s complement, applying the operation, then converting back to sign-magnitude form.

// Example: 0xFFFFFFFF00000000000012345678 ^ -1
// Input: {0x12345678, 0x0, 0xFFFF0000, 0xFFFF} ^ {0x1} with negative sign
// Result: {0x12345679, 0x0, 0xFFFF0000, 0xFFFF} with negative sign

Note

Input and output are in sign-magnitude form, not two’s complement

Note

Accepts both normalized and non-normalized inputs

Parameters:

m – First operand magnitude
m_len – Length of first operand in digits
m_sign – Sign of first operand
n – Second operand magnitude
n_len – Length of second operand in digits
n_sign – Sign of second operand
out – [out] Result buffer (must have at least MAX_LEN(m_len, n_len) + 1 digits)
out_sign – [out] Sign of result

Returns:

Length of result in digits

Pre:

out buffer must be at least MAX_LEN(m_len, n_len) + 1 digits

Post:

Result may have leading zeros (not normalized)

size_t intn_bnot(const intn_digit_t m[], size_t m_len, intn_integer_sign_t m_sign, intn_digit_t out[], intn_integer_sign_t *out_sign)

Bitwise NOT of a signed multi-precision integer.

Performs bitwise NOT operation (one’s complement).

Note

Accepts both normalized and non-normalized inputs

Parameters:

m – Operand magnitude
m_len – Length of operand in digits
m_sign – Sign of operand
out – [out] Result buffer (must have at least m_len + 1 digits)
out_sign – [out] Sign of result

Returns:

Length of result in digits

Pre:

out buffer must be at least m_len + 1 digits

Post:

Result may have leading zeros (not normalized)

size_t intn_bsl(const intn_digit_t num[], size_t len, size_t n, intn_digit_t *out)

Bit shift left of multi-precision integer.

Shifts integer left by n bit positions.

Note

Accepts both normalized and non-normalized inputs

Warning

If return value > INTN_BSL_MAX_RES_LEN, result overflowed and out buffer was not written. Caller must check return value before using result.

Parameters:

num – Integer to shift
len – Length of integer in digits
n – Number of bit positions to shift
out – [out] Result buffer (must have sufficient space, see warning)

Returns:

Length of result in digits

Pre:

out buffer must be at least INTN_BSL_MAX_RES_LEN digits when shift is reasonable

Post:

Result may have leading zeros (not normalized)

void bsru(const uint32_t num[], size_t effective_bits_len, size_t n, uint32_t last_digit, uint32_t *out)

size_t intn_bsr(const intn_digit_t num[], size_t len, intn_integer_sign_t num_sign, size_t n, intn_digit_t *out)

Bit shift right of signed multi-precision integer.

Performs arithmetic right shift (sign-extending) by n bit positions.

Note

Follows Erlang semantics: large shifts converge to -1 (negative) or 0 (non-negative)

Note

Accepts both normalized and non-normalized inputs

Parameters:

num – Integer magnitude to shift
len – Length of integer in digits
num_sign – Sign of integer
n – Number of bit positions to shift
out – [out] Result buffer (must have at least len digits)

Returns:

Length of result in digits

Pre:

out buffer must be at least len digits

Post:

Result may have leading zeros (not normalized)

size_t intn_count_digits(const intn_digit_t *num, size_t num_len)

Count non-zero digits in multi-precision integer.

Returns the number of significant (non-zero) digits, effectively normalizing the length. This is used to determine the actual size of a result after an operation that may produce leading zeros.

Note

Essential for normalization after operations

// Examples:
intn_count_digits({0x0, 0x0, 0x0, 0x80000000}, 4) -> 4 (no leading zeros)
intn_count_digits({0x0, 0x0, 0x0, 0x80000000, 0x0}, 5) -> 4 (one leading zero)

Parameters:

num – Integer array to count
num_len – Length of array in digits

Returns:

Number of non-zero digits (0 if integer is zero)

double intn_to_double(const intn_digit_t *num, size_t num_len, intn_integer_sign_t sign)

Convert multi-precision integer to double.

Converts integer to floating-point representation. May lose precision for large integers.

Note

Precision loss expected for integers > 53 bits

Note

With current 256-bit limit, result always fits in double range

Note

Accepts both normalized and non-normalized inputs

Parameters:

num – Integer magnitude (must be normalized)
len – Length of integer in digits
sign – Sign of integer

Returns:

Double representation

int intn_from_double(double dnum, intn_digit_t *out, intn_integer_sign_t *out_sign)

Convert double to multi-precision integer.

Converts floating-point value to integer, truncating fractional part.

Parameters:

dnum – Double value to convert
out – [out] Result buffer (must have sufficient space)
out_sign – [out] Sign of result

Returns:

Number of digits in result, or negative on error

Pre:

dnum must be finite (not NaN or infinity)

Post:

Result may have leading zeros (not normalized)

char *intn_to_string(const intn_digit_t *num, size_t len, intn_integer_sign_t num_sign, int base, size_t *string_len)

Convert multi-precision integer to string.

Converts integer to ASCII string representation in specified base. Output uses uppercase letters for digits > 9, with no base prefix (e.g., no “0x”).

Note

Output format: uppercase letters, no base prefix

Note

Accepts both normalized and non-normalized inputs

Parameters:

num – Integer magnitude (must be normalized)
len – Length of integer in digits
num_sign – Sign of integer
base – Number base for conversion (2-36)
string_len – [out] Length of resulting string (not including null terminator)

Returns:

Newly allocated null-terminated string (caller must free)

Pre:

base >= 2 && base <= 36

Post:

Returned string must be freed by caller

static void ipow(int base, int exp, intn_digit_t *out)

int intn_parse(const char buf[], size_t buf_len, int base, intn_digit_t *out, intn_integer_sign_t *out_sign)

Parse ASCII string to multi-precision integer.

Parses integer from ASCII representation in specified base. Supports chunk parsing for arbitrarily large integers.

Note

No base prefixes (like “0x”) are supported

Note

Leading zeros in input are skipped automatically

Note

Signs (+/-) accepted unless rejected by caller options

Note

Case-insensitive for letter digits (a-z, A-Z)

Parameters:

buf – Buffer containing ASCII digits
buf_len – Length of buffer in bytes
base – Number base for parsing (2-36)
out – [out] Result buffer (must have at least INTN_MAX_RES_LEN digits)
out_sign – [out] Sign of parsed integer

Returns:

Number of digits in result, or negative on parse error

Pre:

base >= 2 && base <= 36

Pre:

buf != NULL when buf_len > 0 (NULL allowed only for zero-length buffer)

Pre:

out buffer must be at least INTN_MAX_RES_LEN digits

Post:

Result may have leading zeros (not normalized)

int intn_from_integer_bytes(const uint8_t in[], size_t in_size, intn_from_integer_options_t opts, intn_digit_t out[], intn_integer_sign_t *out_sign)

Convert byte array to multi-precision integer.

Converts integer from byte representation with specified endianness and signedness.

Parameters:

in – Input byte array
in_size – Size of input in bytes
opts – Conversion options (endianness, signedness)
out – [out] Result buffer (must have at least intn_required_digits_for_unsigned_integer(in_size) digits)
out_sign – [out] Sign of result

Returns:

Number of digits in result, or negative on error

Pre:

out buffer must have sufficient space based on in_size

Post:

Result may have leading zeros (not normalized)

int intn_to_integer_bytes(const intn_digit_t in[], size_t in_len, intn_integer_sign_t in_sign, intn_from_integer_options_t opts, uint8_t out[], size_t out_len)

Convert multi-precision integer to byte array.

Converts integer to byte representation with specified endianness and signedness.

Parameters:

in – Integer magnitude (must be normalized)
in_len – Length of integer in digits
in_sign – Sign of integer
opts – Conversion options (endianness, signedness)
out – [out] Output byte buffer
out_len – Size of output buffer in bytes

Returns:

Number of bytes written, or negative on error (buffer too small)

Pre:

Input must be normalized for correct size calculation

size_t intn_required_unsigned_integer_bytes(const intn_digit_t in[], size_t in_len)

Calculate bytes needed for unsigned integer representation.

Returns minimum number of bytes needed to represent the integer as an unsigned value.

Parameters:

in – Integer magnitude (must be normalized)
in_len – Length of integer in digits

Returns:

Number of bytes required

Pre:

Input must be normalized for accurate result