LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
lmmpn.h 文件参考
#include <stdbool.h>
#include "lmmp.h"
lmmpn.h 的引用(Include)关系图:
此图展示该文件被哪些文件直接或间接地引用了:

浏览该文件的源代码.

宏定义

#define LMMP_ADDCB_(r, x, y)
#define LMMP_AORS_(FUNCTION, TEST)
#define LMMP_AORS_1_(OP, CB)
#define lmmp_dec(p)
 减1宏(预期无借位)
#define lmmp_dec_1(p, dec)
 减指定值宏(预期无借位)
#define lmmp_inc(p)
 加1宏(预期无进位)
#define lmmp_inc_1(p, inc)
 加指定值宏(预期无进位)
#define LMMP_INLINE   static inline
 Copyright (C) 2026 HJimmyK (Jericho Knox)
#define LMMP_NOVECTOR
#define LMMP_SUBCB_(r, x, y)

函数

static mp_limb_t lmmp_add_ (mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
 加法静态内联函数 [dst,na]=[numa,na]+[numb,nb]
static mp_limb_t lmmp_add_1_ (mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
 加单精度数静态内联函数 [dst,na]=[numa,na]+x
mp_limb_t lmmp_add_n_ (mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
 无进位的n位加法 [dst,n] = [numa,n] + [numb,n]
mp_limb_t lmmp_add_n_sub_n_ (mp_ptr dsta, mp_ptr dstb, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
 同时执行n位加法和减法 ([dsta,n],[dstb,n]) = ([numa,n]+[numb,n],[numa,n]-[numb,n])
mp_limb_t lmmp_add_nc_ (mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t c)
 带进位的n位加法 [dst,n] = [numa,n] + [numb,n] + c
mp_limb_t lmmp_addmul_1_ (mp_ptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t b)
 乘以单limb并累加操作 [numa,n] += [numb,n] * b
mp_limb_t lmmp_addmul_2_ (mp_ptr numa, mp_srcptr numb, mp_size_t n, mp_srcptr bp)
 乘以双limb并累加 [numa,n] += [numb,n] * [bp,2]
mp_limb_t lmmp_addshl1_n_ (mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
 加法结合左移1位操作 [dst,n] = [numa,n] + ([numb,n] << 1)
void lmmp_b36_to_chars_ (mp_byte_t *dst, mp_size_t n, bool upper)
 36进制数字字节原地转字符 [dst,n]: [0,35] -> ['0'-'9','a'-'z']或['0'-'9','A'-'Z']
void lmmp_bninv_ (mp_ptr dstq, mp_srcptr numa, mp_size_t na, mp_size_t ni)
 近似逆元计算 [dstq,na+ni+2] = B^(2*(na+ni)) / ([numa,na] * B^ni) + [0|-ept]
int lmmp_cmp_ (mp_srcptr numa, mp_srcptr numb, mp_size_t n)
 比较函数
void lmmp_dec_to_chars_ (mp_byte_t *dst, mp_size_t n)
 十进制数字字节原地转字符 [dst,n]: [0,9] -> ['0','9']
void lmmp_div_ (mp_ptr dstq, mp_ptr dstr, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
 除法和取模操作
mp_limb_t lmmp_div_1_ (mp_ptr dstq, mp_srcptr numa, mp_size_t na, mp_limb_t x)
 单精度数除法
mp_limb_t lmmp_div_1_s_ (mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_limb_t x)
 单精度数除法(除数为1个limb)
void lmmp_div_2_ (mp_ptr dstq, mp_srcptr numa, mp_size_t na, mp_ptr numb)
 双精度数除法 (除数为2个limb)
mp_limb_t lmmp_div_2_s_ (mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb)
 双精度数除法(除数为2个limb)
mp_limb_t lmmp_div_3_2_ (mp_ptr numa, mp_srcptr numb, mp_limb_t inv21)
 3/2位除法运算 [numa,2]=[numa,3] mod [numb,2]
mp_limb_t lmmp_div_basecase_ (mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, mp_limb_t inv21)
 基础除法运算
mp_limb_t lmmp_div_divide_ (mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, mp_limb_t inv21)
 分治除法运算
static mp_size_t lmmp_div_inv_size_ (mp_size_t nq, mp_size_t nb)
 计算预计算逆元的尺寸
mp_limb_t lmmp_div_mulinv_ (mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, mp_srcptr invappr, mp_size_t ni)
 乘法逆元除法
mp_limb_t lmmp_div_s_ (mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
 除法运算
static bool lmmp_endian (void)
 运行时判断端序
mp_bitcnt_t lmmp_extract_bits_ (mp_srcptr num, mp_size_t n, mp_limb_t *ext, int bits)
 提取高位指定位数,并返回低位bits位数
mp_size_t lmmp_fft_next_size_ (mp_size_t n)
 计算满足 >=n 的最小费马/梅森乘法可行尺寸
mp_size_t lmmp_from_decimal_ (mp_ptr dst, const char *src, mp_size_t len)
 十进制字符串转limb数组 [src,len,10] to [dst,return value,B]
mp_size_t lmmp_from_decimal_len_ (const char *src, mp_size_t len)
 计算十进制字符串转limb数组所需的 limb 缓冲区长度
mp_size_t lmmp_from_hex_ (mp_ptr dst, const char *src, mp_size_t len)
 十六进制字符串转limb数组 [src,len,16] to [dst,return value,B]
mp_size_t lmmp_from_hex_len_ (const char *src, mp_size_t len)
 计算十六进制字符串转limb数组所需的 limb 缓冲区长度
mp_size_t lmmp_from_str_ (mp_ptr dst, const mp_byte_t *src, mp_size_t len, int base)
 字节数组转limb数组操作 [src,len,base] to [dst,return value,B]
mp_size_t lmmp_from_str_len_ (const mp_byte_t *src, mp_size_t len, int base)
 计算字节数组转limb数组所需的 limb 缓冲区长度
void lmmp_inv_ (mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t nf)
 求逆操作 [dst,na+nf+1] = (B^(2*(na+nf)) - 1) / ([numa,na]*B^nf) + [0|-1]
mp_limb_t lmmp_inv_1_ (mp_limb_t x)
 1阶逆元计算 (inv1)
mp_limb_t lmmp_inv_2_1_ (mp_limb_t xh, mp_limb_t xl)
 2-1阶逆元计算 (inv21)
void lmmp_inv_basecase_ (mp_ptr dst, mp_srcptr numa, mp_size_t na)
 近似逆元计算
void lmmp_inv_prediv_ (mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t ni)
 除法前的逆元预计算,[dst,ni] = invappr( (ni+1 MSLs of numa) + 1 ) / B
void lmmp_invappr_ (mp_ptr dst, mp_srcptr numa, mp_size_t na)
 近似逆元计算 (invappr)
void lmmp_invappr_newton_ (mp_ptr dst, mp_srcptr numa, mp_size_t na)
 近似逆元计算(牛顿迭代法)
int lmmp_leading_zeros_ (mp_limb_t x)
 计算一个单精度数(limb)中前导零的个数
int lmmp_limb_bits_ (mp_limb_t x)
 计算满足 2^k > x 的最小自然数k
int lmmp_limb_popcnt_ (mp_limb_t x)
 计算一个64位无符号整数中1的个数
mp_size_t lmmp_mersenne_next_size_ (mp_size_t n)
 计算满足 >=n 的最小分治梅森乘法可行尺寸
mp_limb_t lmmp_mod_1_ (mp_srcptr numa, mp_size_t na, mp_limb_t x)
 单精度数取余
void lmmp_mod_2_ (mp_srcptr numa, mp_size_t na, mp_ptr numb)
 双精度数取余 (除数为2个limb)
mp_limb_t lmmp_mod_preinv_1_ (mp_srcptr numa, mp_size_t na, mp_limb_t x, mp_limb_t inv, mp_limb_t k)
 单精度数取余(预备逆元版) [numa,na] mod x,同 lmmp_mod_1_
void lmmp_mul_ (mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
 不等长乘法操作 [dst,na+nb] = [numa,na] * [numb,nb]
mp_limb_t lmmp_mul_1_ (mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
 乘以单limb操作 [dst,na] = [numa,na] * x
void lmmp_mul_basecase_ (mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
 基础乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_mul_fermat_ (mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
 费马数模乘法 [dst,rn+1]=[numa,na]*[numb,nb] mod B^rn+1
void lmmp_mul_fft_ (mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
 FFT乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_mul_fft_unbalance_ (mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
 FFT不平衡乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_mul_mersenne_ (mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
 梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1
void lmmp_mul_mersenne_dc_ (mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
 分治梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1
void lmmp_mul_mersenne_fft_ (mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
 FFT 梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1
void lmmp_mul_n_ (mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
 等长乘法操作 [dst,2*n] = [numa,n] * [numb,n]
void lmmp_mul_toom22_ (mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
 Toom-22乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_mul_toom32_ (mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
 Toom-32乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_mul_toom33_ (mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
 Toom-33乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_mul_toom42_ (mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
 Toom-42乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_mul_toom42_unbalance_ (mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
 Toom-42不平衡乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_mul_toom43_ (mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
 Toom-43乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_mul_toom44_ (mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
 Toom-44乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_mul_toom52_ (mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
 Toom-52乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_mul_toom53_ (mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
 Toom-53乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_mul_toom62_ (mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
 Toom-62乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_mul_toom62_unbalance_ (mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
 Toom-62不平衡乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_mul_toom6h_ (mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
 Toom-6.5乘法运算 [dst,na+nb] = [numa,na] * [numb,nb] (非对称切分+条件inf点,原生支持不平衡;评估点 inf,±4,±2,±1,±1/2,±1/4,0)
void lmmp_mul_toom8h_ (mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
 Toom-8.5乘法运算 [dst,na+nb] = [numa,na] * [numb,nb] (非对称切分+条件inf点,原生支持不平衡;评估点 inf,±8,±4,±2,±1,±1/2,±1/4,±1/8,0)
mp_limb_t lmmp_mulh_ (mp_limb_t a, mp_limb_t b)
 计算两个64位无符号整数相乘的高位结果 (a*b)/B
void lmmp_mullh_ (mp_limb_t a, mp_limb_t b, mp_ptr dst)
 计算两个64位无符号整数相乘的128位结果 (a*b)
void lmmp_mullo_ (mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
 低位乘法 [dst,n] = [numa,n] * [numb,n] mod B^n
void lmmp_mullo_basecase_ (mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
 基础低位乘法 [dst,n] = [numa,n] * [numb,n] mod B^n
void lmmp_mullo_dc_ (mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_ptr tp, mp_size_t n)
 低位乘法 [dst,n] = [numa,n] * [numb,n] mod B^n
void lmmp_mullo_fft_ (mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n, mp_ptr scratch)
 低位FFT乘法 [dst,n] = [numa,n] * [numb,n] mod B^n
void lmmp_not_ (mp_ptr dst, mp_srcptr numa, mp_size_t na)
 按位取反操作 [dst,na] = ~[numa,na] (对每个limb执行按位非操作)
mp_limb_t lmmp_shl_ (mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shl)
 左移操作 [dst,na] = [numa,na]<<shl,dst的低shl位填充0
mp_limb_t lmmp_shl_c_ (mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shl, mp_limb_t c)
 带进位的左移操作 [dst,na] = [numa,na]<<shl,dst的低shl位填充c的低shl位
mp_limb_t lmmp_shlnot_ (mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shl)
 左移后按位取反操作 [dst,na] = ~([numa,na] << shl),dst的低shl位填充1
mp_limb_t lmmp_shr1add_n_ (mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
 加法后右移1位 [dst,n] = ([numa,n] + [numb,n]) >> 1
mp_limb_t lmmp_shr1add_nc_ (mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t c)
 带进位加法后右移1位 [dst,n] = ([numa,n] + [numb,n] + c) >> 1
mp_limb_t lmmp_shr1sub_n_ (mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
 减法后右移1位 [dst,n] = ([numa,n] - [numb,n]) >> 1
mp_limb_t lmmp_shr1sub_nc_ (mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t c)
 带借位减法后右移1位 [dst,n] = ([numa,n] - [numb,n] - c) >> 1
mp_limb_t lmmp_shr_ (mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shr)
 右移操作 [dst,na] = [numa,na]>>shr,dst的高shr位填充0
mp_limb_t lmmp_shr_c_ (mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shr, mp_limb_t c)
 带进位的右移操作 [dst,na] = [numa,na]>>shr,dst的高shr位填充c的高shr位
void lmmp_sqr_ (mp_ptr dst, mp_srcptr numa, mp_size_t na)
 平方操作 [dst,2*na] = [numa,na]^2
void lmmp_sqr_basecase_ (mp_ptr dst, mp_srcptr numa, mp_size_t na)
 基础平方运算 [dst,2*na] = [numa,na]^2
void lmmp_sqr_fermat_ (mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na)
 SSA FFT 版费马数模平方 [dst,rn+1]=[numa,na]^2 mod B^rn+1
void lmmp_sqr_fft_ (mp_ptr dst, mp_srcptr numa, mp_size_t na)
 FFT平方运算 [dst,2*na] = [numa,na]^2
void lmmp_sqr_mersenne_ (mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na)
 梅森数模平方 [dst,rn] = [numa,na]^2 mod B^rn-1
void lmmp_sqr_mersenne_dc_ (mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na)
 分治梅森数模平方 [dst,rn] = [numa,na]^2 mod B^rn-1
void lmmp_sqr_mersenne_fft_ (mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na)
 FFT 梅森数模平方 [dst,rn] = [numa,na]^2 mod B^rn-1
void lmmp_sqr_toom2_ (mp_ptr dst, mp_srcptr numa, mp_size_t na)
 Toom-2平方运算 [dst,2*na] = [numa,na]^2
void lmmp_sqr_toom3_ (mp_ptr dst, mp_srcptr numa, mp_size_t na)
 Toom-3平方运算 [dst,2*na] = [numa,na]^2
void lmmp_sqr_toom4_ (mp_ptr dst, mp_srcptr numa, mp_size_t an)
 Toom-4平方运算 [dst,2*na] = [numa,na]^2
void lmmp_sqr_toom6_ (mp_ptr dst, mp_srcptr numa, mp_size_t na)
 Toom-6平方运算 [dst,2*na] = [numa,na]^2 (评估点 ±4,±2,±1,±1/2,±1/4,0,无inf点)
void lmmp_sqr_toom8_ (mp_ptr dst, mp_srcptr numa, mp_size_t na)
 Toom-8平方运算 [dst,2*na] = [numa,na]^2 (评估点 ±8,±4,±2,±1,±1/2,±1/4,±1/8,0,无inf点)
void lmmp_sqrlo_basecase_ (mp_ptr dst, mp_srcptr numa, mp_size_t n)
 基础低位平方 [dst,n] = [numa,n]^2 mod B^n
void lmmp_sqrlo_dc_ (mp_ptr dst, mp_srcptr numa, mp_ptr tp, mp_size_t n)
 低位平方 [dst,n] = [numa,n]^2 mod B^n
static mp_limb_t lmmp_sub_ (mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
 减法静态内联函数 [dst,na]=[numa,na]-[numb,nb]
static mp_limb_t lmmp_sub_1_ (mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
 减单精度数静态内联函数 [dst,na]=[numa,na]-x
mp_limb_t lmmp_sub_n_ (mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
 无借位的n位减法 [dst,n] = [numa,n] - [numb,n]
mp_limb_t lmmp_sub_nc_ (mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t c)
 带借位的n位减法 [dst,n] = [numa,n] - [numb,n] - c
mp_limb_t lmmp_submul_1_ (mp_ptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t b)
 乘以单limb并累减操作 [numa,n] -= [numb,n] * b
mp_limb_t lmmp_subshl1_n_ (mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
 减法结合左移1位操作 [dst,n] = [numa,n] - ([numb,n] << 1)
int lmmp_tailing_zeros_ (mp_limb_t x)
 计算一个单精度数(limb)中末尾零的个数
mp_size_t lmmp_to_decimal_ (char *dst, mp_srcptr numa, mp_size_t na)
 limb数组转十进制字符串 [numa,na,B] to [dst,return value,10]
mp_size_t lmmp_to_decimal_len_ (mp_srcptr numa, mp_size_t na)
 计算转换为十进制字符串需要的缓冲区长度
mp_size_t lmmp_to_hex_ (char *dst, mp_srcptr numa, mp_size_t na, bool upper)
 limb数组转十六进制字符串 [numa,na,B] to [dst,return value,16]
mp_size_t lmmp_to_hex_len_ (mp_srcptr numa, mp_size_t na)
 计算转换为十六进制字符串需要的缓冲区长度
mp_size_t lmmp_to_str_ (mp_byte_t *dst, mp_srcptr numa, mp_size_t na, int base)
 limb数组转字节数组操作 [numa,na,B] to [dst,return value,base]
mp_size_t lmmp_to_str_len_ (mp_srcptr numa, mp_size_t na, int base)
 计算转换为字节数组,字节数组需要的缓冲区长度
int lmmp_zero_q_ (mp_srcptr p, mp_size_t n)
 判零函数

宏定义说明

◆ LMMP_ADDCB_

#define LMMP_ADDCB_ ( r,
x,
y )
值:
((r) < (y))

在文件 lmmpn.h 第 1246 行定义.

被这些函数引用 lmmp_add_1_().

◆ LMMP_AORS_

#define LMMP_AORS_ ( FUNCTION,
TEST )
值:
mp_limb_t _x_; \
if (FUNCTION(dst, numa, numb, nb)) { \
LMMP_NOVECTOR \
do { \
if (nb >= na) \
return 1; \
_x_ = numa[nb]; \
} while (TEST); \
} \
if (dst != numa && na != nb) \
lmmp_copy(dst + nb, numa + nb, na - nb); \
return 0
uint64_t mp_limb_t
定义 lmmp.h:92
#define numb

在文件 lmmpn.h 第 1182 行定义.

被这些函数引用 lmmp_add_() , 以及 lmmp_sub_().

◆ LMMP_AORS_1_

#define LMMP_AORS_1_ ( OP,
CB )
值:
mp_size_t _i_ = 1; \
mp_limb_t _x_ = numa[0], _r_ = _x_ OP x; \
dst[0] = _r_; \
if (CB(_r_, _x_, x)) { \
do { \
if (_i_ >= na) \
return 1; \
_x_ = numa[_i_]; \
_r_ = _x_ OP 1; \
dst[_i_] = _r_; \
++_i_; \
} while (CB(_r_, _x_, 1)); \
} \
if (numa != dst && na != _i_) \
lmmp_copy(dst + _i_, numa + _i_, na - _i_); \
return 0
uint64_t mp_size_t
定义 lmmp.h:93

在文件 lmmpn.h 第 1227 行定义.

被这些函数引用 lmmp_add_1_() , 以及 lmmp_sub_1_().

◆ lmmp_dec

◆ lmmp_dec_1

#define lmmp_dec_1 ( p,
dec )
值:
do { \
mp_ptr _p_ = (p); \
mp_limb_t _dec_ = (dec), _x_; \
_x_ = *_p_; \
*_p_ = _x_ - _dec_; \
if (_x_ < _dec_) \
while ((*(++_p_))-- == 0); \
} while (0)

减指定值宏(预期无借位)

参数
p指针
dec要减的单精度数值
注解
先减最低位,若产生借位则逐位减1,直到无借位(预期无溢出)

在文件 lmmpn.h 第 1145 行定义.

被这些函数引用 lmmp_fft_bfy_(), lmmp_fft_shl_coef_(), lmmp_ifft_bfy_(), lmmp_invappr_newton_(), lmmp_invcbrt_newton_(), lmmp_invsqrt_newton_(), lmmp_mul_fermat_recombine_(), lmmp_mul_fft_crt_(), lmmp_mullo_crt_(), lmmp_sqr_fft_(), lmmp_toom_interp12_(), lmmp_toom_interp16_(), lmmp_toom_interp5_(), lmmp_toom_interp6_(), mrs_mul_core_() , 以及 mrs_sqr_core_().

◆ lmmp_inc

◆ lmmp_inc_1

#define lmmp_inc_1 ( p,
inc )
值:
do { \
mp_ptr _p_ = (p); \
mp_limb_t _inc_ = (inc), _x_; \
_x_ = *_p_ + _inc_; \
*_p_ = _x_; \
if (_x_ < _inc_) \
while (++(*(++_p_)) == 0); \
} while (0)

加指定值宏(预期无进位)

参数
p指针
inc要加的单精度数值
注解
先加最低位,若产生进位则逐位加1,直到无进位(预期无溢出)

在文件 lmmpn.h 第 1118 行定义.

被这些函数引用 lmmp_cbrt_6_fast_(), lmmp_cbrt_divide_(), lmmp_fft_bfy_(), lmmp_fft_shl_coef_(), lmmp_ifft_bfy_(), lmmp_invcbrt_newton_(), lmmp_invsqrt_newton_(), lmmp_mul_fermat_recombine_(), lmmp_mul_fermat_recurse_(), lmmp_mul_toom22_(), lmmp_mul_toom32_(), lmmp_mul_toom44_(), lmmp_mul_toom53_(), lmmp_mul_toom62_(), lmmp_mul_toom62_cache_(), lmmp_mul_toom62_cache_init_(), lmmp_sqr_fermat_recurse_(), lmmp_sqr_toom2_(), lmmp_sqr_toom4_(), lmmp_toom_eval_pm2exp_(), lmmp_toom_interp12_(), lmmp_toom_interp16_(), lmmp_toom_interp5_(), lmmp_toom_interp6_(), lmmp_toom_interp7_(), mersenne_oracle(), mrs_mul_bnp1_(), mrs_mul_core_(), mrs_sqr_bnp1_() , 以及 mrs_sqr_core_().

◆ LMMP_INLINE

#define LMMP_INLINE   static inline

Copyright (C) 2026 HJimmyK (Jericho Knox)

This file is part of LMMP.

LMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.

SPDX-License-Identifier: LGPL-3.0-or-later

在文件 lmmpn.h 第 30 行定义.

被这些函数引用 lmmp_add_(), lmmp_add_1_(), lmmp_div_inv_size_(), lmmp_endian(), lmmp_pcg64_128_random(), lmmp_pcg64_128_srandom(), lmmp_seed_generator(), lmmp_sub_(), lmmp_sub_1_(), lmmp_xoshiro256pp_random(), lmmp_xoshiro256pp_srandom(), mix64(), pcg64_128_action(), pcg64_le_action(), pcg64_le_seq_init(), pcg64_le_seq_next() , 以及 rotl().

◆ LMMP_NOVECTOR

#define LMMP_NOVECTOR

在文件 lmmpn.h 第 1179 行定义.

◆ LMMP_SUBCB_

#define LMMP_SUBCB_ ( r,
x,
y )
值:
((x) < (y))

在文件 lmmpn.h 第 1248 行定义.

被这些函数引用 lmmp_sub_1_().

函数说明

◆ lmmp_add_()

mp_limb_t lmmp_add_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na,
mp_srcptr numb,
mp_size_t nb )
inlinestatic

加法静态内联函数 [dst,na]=[numa,na]+[numb,nb]

参数
dst输出结果缓冲区,存储numa + numb
numa第一个加数,长度为na
na第一个加数的 limb 长度
numb第二个加数,长度为nb
nb第二个加数的 limb 长度
返回
进位标志(1表示有进位,0表示无进位)
警告
0<nb<=na, eqsep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL

在文件 lmmpn.h 第 1206 行定义.

1206 {
1207 LMMP_AORS_(lmmp_add_n_, ((dst[nb++] = _x_ + 1) == 0));
1208}
#define LMMP_AORS_(FUNCTION, TEST)
mp_limb_t lmmp_add_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
无进位的n位加法 [dst,n] = [numa,n] + [numb,n]
定义 add_n.c:76

引用了 lmmp_add_(), lmmp_add_n_(), LMMP_AORS_, LMMP_INLINE , 以及 numb.

被这些函数引用 gcdext_row_mul_(), lmmp_add_(), lmmp_binvert_unbalance_(), lmmp_cbrt_(), lmmp_gcdext_1_(), lmmp_gcdext_2_(), lmmp_gcdext_derive_(), lmmp_gcdext_hgcd_(), lmmp_gcdext_smag_(), lmmp_hgcd_adjust_(), lmmp_hgcd_fold_mod_(), lmmp_hgcd_matrix_update_q_(), lmmp_invcbrt_newton_(), lmmp_invsqrt_newton_(), lmmp_mul_fermat_recombine_(), lmmp_mul_fft_cache_(), lmmp_mul_fft_cache_init_(), lmmp_mul_fft_mods_(), lmmp_mul_mersenne_cache_(), lmmp_mul_mersenne_cache_init_(), lmmp_mul_mersenne_fft_(), lmmp_mul_toom22_(), lmmp_mul_toom32_(), lmmp_mul_toom33_(), lmmp_mul_toom42_(), lmmp_mul_toom42_cache_(), lmmp_mul_toom42_cache_init_(), lmmp_mul_toom43_(), lmmp_mul_toom52_(), lmmp_mul_toom53_(), lmmp_mul_toom62_(), lmmp_mul_toom62_cache_init_(), lmmp_nthroot_(), lmmp_sqr_mersenne_fft_(), lmmp_sqr_toom2_(), lmmp_sqr_toom3_(), lmmp_toom_eval_dgr3_pm1_(), lmmp_toom_eval_dgr3_pm2_(), lmmp_toom_eval_pm1_(), lmmp_toom_eval_pm2rexp_(), mat22_add_(), mat22_addsg_(), mersenne_oracle(), mrs_mul_core_(), mrs_sqr_core_(), TEST_CASE() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_add_1_()

mp_limb_t lmmp_add_1_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na,
mp_limb_t x )
inlinestatic

加单精度数静态内联函数 [dst,na]=[numa,na]+x

参数
dst输出结果缓冲区,存储numa + x
numa被加数,长度为na
na被加数的 limb 长度
x加数(单个 limb )
返回
进位标志(1表示有进位,0表示无进位)
警告
na>0, eqsep(dst,numa), dst!=NULL, numa!=NULL

在文件 lmmpn.h 第 1259 行定义.

1259 {
1261}
#define LMMP_AORS_1_(OP, CB)
#define LMMP_ADDCB_(r, x, y)

引用了 lmmp_add_1_(), LMMP_ADDCB_, LMMP_AORS_1_ , 以及 LMMP_INLINE.

被这些函数引用 gcdext_row_qscalar_(), lc1_(), lmmp_add_1_(), lmmp_cbrt_(), lmmp_cbrt_divide_(), lmmp_fibonacci_(), lmmp_from_str_basecase_(), lmmp_hgcd_matrix_mul_u_(), lmmp_inv_prediv_(), lmmp_mont_sp_redc_(), lmmp_mul_fermat_recombine_(), lmmp_mul_mersenne_cache_(), lmmp_mul_mersenne_cache_init_(), lmmp_mul_mersenne_fft_(), lmmp_mul_toom32_(), lmmp_mul_toom33_(), lmmp_mul_toom42_(), lmmp_mul_toom42_cache_(), lmmp_mul_toom42_cache_init_(), lmmp_mul_toom43_(), lmmp_nthroot_(), lmmp_sqr_mersenne_fft_(), lmmp_sqr_toom3_(), lmmp_sqrt_divide_(), lmmp_toom_couple_handling_(), lmmp_toom_eval_pm2_(), lmmp_toom_interp12_(), lmmp_toom_interp16_() , 以及 nthroot_add_small_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_add_n_()

mp_limb_t lmmp_add_n_ ( mp_ptr dst,
mp_srcptr numa,
mp_srcptr numb,
mp_size_t n )

无进位的n位加法 [dst,n] = [numa,n] + [numb,n]

参数
dst结果输出指针
numa第一个加数指针
numb第二个加数指针
nlimb长度
警告
n>0, eqsep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
返回
运算后的最终进位值 [0|1]

在文件 add_n.c 第 76 行定义.

76 {
77 mp_size_t i = 0;
78 mp_limb_t cy = 0;
79
80 for (; i < n; i++) {
81 mp_limb_t a, b, r;
82 a = numa[i];
83 b = numb[i];
84 r = a + cy;
85 cy = (r < cy);
86 r += b;
87 cy += (r < b);
88 dst[i] = r;
89 }
90
91 return cy;
92}
#define n

引用了 lmmp_add_n_(), n , 以及 numb.

被这些函数引用 bench_add_n(), cbrt_floor_ok(), check_addmul_2(), coeff_bound_l(), fib2_core_(), ipn_mont_add_(), ipn_mont_dbl_(), ipn_mont_half_(), ipn_mont_sub_(), ipn_sdiv_mul1_(), lmmp_add_(), lmmp_add_n_(), lmmp_binvert_unbalance_(), lmmp_cbrt_6_fast_(), lmmp_div_(), lmmp_div_basecase_(), lmmp_div_divide_n_(), lmmp_div_mulinv_(), lmmp_div_s_(), lmmp_fibonacci_(), lmmp_from_str_divide_(), lmmp_invappr_newton_(), lmmp_mont_redc_bc_(), lmmp_mul_fft_unbalance_(), lmmp_mul_toom22_(), lmmp_mul_toom32_(), lmmp_mul_toom33_(), lmmp_mul_toom42_(), lmmp_mul_toom42_cache_(), lmmp_mul_toom42_cache_init_(), lmmp_mul_toom42_unbalance_(), lmmp_mul_toom43_(), lmmp_mul_toom62_(), lmmp_mul_toom62_cache_(), lmmp_mul_toom62_cache_init_(), lmmp_mul_toom62_unbalance_(), lmmp_mullh_(), lmmp_mullo_dc_(), lmmp_powmod_(), lmmp_sqr_toom2_(), lmmp_toom_couple_handling_(), lmmp_toom_eval_dgr3_pm1_(), lmmp_toom_eval_dgr3_pm2_(), lmmp_toom_eval_pm1_(), lmmp_toom_interp12_(), lmmp_toom_interp16_(), lmmp_toom_interp5_(), lmmp_toom_interp6_(), lmmp_toom_interp7_(), mrs_mul_core_(), mrs_sqr_core_(), pad_add(), pad_add_value(), run_gcdext_pair(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE() , 以及 verify_div_relation().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_add_n_sub_n_()

mp_limb_t lmmp_add_n_sub_n_ ( mp_ptr dsta,
mp_ptr dstb,
mp_srcptr numa,
mp_srcptr numb,
mp_size_t n )

同时执行n位加法和减法 ([dsta,n],[dstb,n]) = ([numa,n]+[numb,n],[numa,n]-[numb,n])

Copyright (C) 2026 HJimmyK (Jericho Knox)

参数
dsta加法结果输出指针
dstb减法结果输出指针
numa第一个操作数指针(被加数/被减数)
numb第二个操作数指针(加数/减数)
nlimb长度
警告
n>0, eqsep(dsta,[numa|numb]), eqsep(dstb,[numa|numb]), dsta!=NULL, dstb!=NULL, numa!=NULL, numb!=NULL
返回
组合返回值 cb = 2*c + b (c为加法进位, b为减法借位) 返回值范围: 0(无进位无借位),1(无进位有借位),2(有进位无借位),3(有进位有借位)

同时执行n位加法和减法 ([dsta,n],[dstb,n]) = ([numa,n]+[numb,n],[numa,n]-[numb,n])

This file is part of LMMP.

LMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.

SPDX-License-Identifier: LGPL-3.0-or-later

在文件 add_n_sub_n.c 第 33 行定义.

33 {
34 mp_size_t i = 0;
35 mp_limb_t cy = 0;
36 mp_limb_t k = 1;
37
38 for (; i + 4 <= n; i += 4) {
39 mp_limb_t a0 = numa[i + 0], a1 = numa[i + 1], a2 = numa[i + 2], a3 = numa[i + 3];
40 mp_limb_t b0 = numb[i + 0], b1 = numb[i + 1], b2 = numb[i + 2], b3 = numb[i + 3];
41 mp_limb_t nb0 = ~b0, nb1 = ~b1, nb2 = ~b2, nb3 = ~b3;
42
43 __uint128_t s0 = (__uint128_t)a0 + b0 + cy;
44 __uint128_t s1 = (__uint128_t)a1 + b1 + (mp_limb_t)(s0 >> 64);
45 __uint128_t s2 = (__uint128_t)a2 + b2 + (mp_limb_t)(s1 >> 64);
46 __uint128_t s3 = (__uint128_t)a3 + b3 + (mp_limb_t)(s2 >> 64);
47 cy = (mp_limb_t)(s3 >> 64);
48
49 __uint128_t t0 = (__uint128_t)a0 + nb0 + k;
50 __uint128_t t1 = (__uint128_t)a1 + nb1 + (mp_limb_t)(t0 >> 64);
51 __uint128_t t2 = (__uint128_t)a2 + nb2 + (mp_limb_t)(t1 >> 64);
52 __uint128_t t3 = (__uint128_t)a3 + nb3 + (mp_limb_t)(t2 >> 64);
53 k = (mp_limb_t)(t3 >> 64);
54
55 dsta[i + 0] = (mp_limb_t)s0;
56 dsta[i + 1] = (mp_limb_t)s1;
57 dsta[i + 2] = (mp_limb_t)s2;
58 dsta[i + 3] = (mp_limb_t)s3;
59 dstb[i + 0] = (mp_limb_t)t0;
60 dstb[i + 1] = (mp_limb_t)t1;
61 dstb[i + 2] = (mp_limb_t)t2;
62 dstb[i + 3] = (mp_limb_t)t3;
63 }
64 for (; i < n; i++) {
65 mp_limb_t a = numa[i], b = numb[i], nb = ~b;
66 __uint128_t s = (__uint128_t)a + b + cy;
67 __uint128_t t = (__uint128_t)a + nb + k;
68 dsta[i] = (mp_limb_t)s;
69 cy = (mp_limb_t)(s >> 64);
70 dstb[i] = (mp_limb_t)t;
71 k = (mp_limb_t)(t >> 64);
72 }
73
74 return 2 * cy + (1 - k);
75}
#define k
#define b0
#define b1
#define a0
#define a1
#define a2
#define b2
#define t
#define a3
#define s
#define b3

引用了 a0, a1, a2, a3, b0, b1, b2, b3, k, lmmp_add_n_sub_n_(), n, numb, s , 以及 t.

被这些函数引用 lmmp_add_n_sub_n_(), lmmp_mul_toom32_(), lmmp_mul_toom33_(), lmmp_mul_toom42_(), lmmp_mul_toom42_cache_(), lmmp_mul_toom42_cache_init_(), lmmp_mul_toom43_(), lmmp_mul_toom52_(), lmmp_mul_toom53_(), lmmp_mul_toom62_(), lmmp_mul_toom62_cache_init_(), lmmp_mullh_(), lmmp_sqr_toom3_(), lmmp_toom_eval_dgr3_pm1_(), lmmp_toom_eval_dgr3_pm2_(), lmmp_toom_eval_pm1_(), lmmp_toom_eval_pm2_(), lmmp_toom_eval_pm2exp_(), lmmp_toom_eval_pm2rexp_(), lmmp_toom_interp12_(), lmmp_toom_interp16_(), TEST_CASE() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_add_nc_()

mp_limb_t lmmp_add_nc_ ( mp_ptr dst,
mp_srcptr numa,
mp_srcptr numb,
mp_size_t n,
mp_limb_t c )

带进位的n位加法 [dst,n] = [numa,n] + [numb,n] + c

Copyright (C) 2026 HJimmyK (Jericho Knox)

参数
dst结果输出指针
numa第一个加数指针
numb第二个加数指针
nlimb长度
c初始进位值 [0|1]
警告
c=[0|1], n>0, eqsep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
返回
运算后的最终进位值 [0|1]

带进位的n位加法 [dst,n] = [numa,n] + [numb,n] + c

This file is part of LMMP.

LMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.

SPDX-License-Identifier: LGPL-3.0-or-later

在文件 add_n.c 第 58 行定义.

58 {
59 mp_size_t i = 0;
60 mp_limb_t cy = c;
61
62 for (; i < n; i++) {
63 mp_limb_t a, b, r;
64 a = numa[i];
65 b = numb[i];
66 r = a + cy;
67 cy = (r < cy);
68 r += b;
69 cy += (r < b);
70 dst[i] = r;
71 }
72
73 return cy;
74}

引用了 lmmp_add_nc_(), n , 以及 numb.

被这些函数引用 bench_add_nc(), lmmp_add_nc_(), lmmp_fft_bfy_(), lmmp_ifft_bfy_(), lmmp_invappr_newton_(), lmmp_mont_redc_(), lmmp_mullh_(), lmmp_redc_(), lmmp_toom_interp12_(), lmmp_toom_interp16_(), TEST_CASE(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_addmul_1_()

mp_limb_t lmmp_addmul_1_ ( mp_ptr numa,
mp_srcptr numb,
mp_size_t n,
mp_limb_t b )

乘以单limb并累加操作 [numa,n] += [numb,n] * b

参数
numa被加数指针(结果也存储在此)
numb乘数指针
nlimb长度
b乘数
警告
n>0, eqsep(numa,numb)), numa!=NULL, numb!=NULL
返回
运算后的进位limb值

在文件 mul_1.c 第 76 行定义.

76 {
77 mp_limb_t cl = 0;
78 mp_size_t i = 0;
79
80 for (; i + 4 <= n; i += 4) {
81 __uint128_t a0 = (__uint128_t)numb[i + 0] * b + numa[i + 0] + cl;
82 __uint128_t a1 = (__uint128_t)numb[i + 1] * b + numa[i + 1] + (mp_limb_t)(a0 >> 64);
83 __uint128_t a2 = (__uint128_t)numb[i + 2] * b + numa[i + 2] + (mp_limb_t)(a1 >> 64);
84 __uint128_t a3 = (__uint128_t)numb[i + 3] * b + numa[i + 3] + (mp_limb_t)(a2 >> 64);
85 numa[i + 0] = (mp_limb_t)a0;
86 numa[i + 1] = (mp_limb_t)a1;
87 numa[i + 2] = (mp_limb_t)a2;
88 numa[i + 3] = (mp_limb_t)a3;
89 cl = (mp_limb_t)(a3 >> 64);
90 }
91 for (; i < n; i++) {
92 __uint128_t a = (__uint128_t)numb[i] * b + numa[i] + cl;
93 numa[i] = (mp_limb_t)a;
94 cl = (mp_limb_t)(a >> 64);
95 }
96 return cl;
97}

引用了 a0, a1, a2, a3, lmmp_addmul_1_(), n , 以及 numb.

被这些函数引用 bench_addmul_1(), check_addmul_2(), gcdext_row_qscalar_(), lc1_(), lmmp_addmul_1_(), lmmp_cbrt_(), lmmp_cbrt_divide_(), lmmp_divexact_basecase_(), lmmp_hgcd_matrix_mul_u_(), lmmp_mont_redc_bc_(), lmmp_mul_toom62_(), lmmp_mul_toom62_cache_(), lmmp_mul_toom62_cache_init_(), lmmp_mullo_basecase_(), lmmp_shlnot_(), lmmp_sqrlo_basecase_(), lmmp_sqrt_(), lmmp_sqrt_divide_(), lmmp_toom_eval_pm2exp_(), lmmp_toom_eval_pm2rexp_(), lmmp_toom_interp12_(), lmmp_toom_interp16_(), lmmp_toom_interp7_(), TEST_CASE(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_addmul_2_()

mp_limb_t lmmp_addmul_2_ ( mp_ptr numa,
mp_srcptr numb,
mp_size_t n,
mp_srcptr bp )

乘以双limb并累加 [numa,n] += [numb,n] * [bp,2]

参数
numa被加数指针(前 n limb 就地累加结果,第 n+1 limb 直接覆写)
numb乘数数组指针
nlimb长度
bp双limb乘数(2 个limb)
警告
n>0, eqsep(numa,numb), sep(numa,bp), numb!=NULL, bp!=NULL
返回
第 n+1 limb(最高溢出 limb)
注解
第 n limb 写入 numa[n](覆写而非累加该处旧值)

在文件 mul_1.c 第 99 行定义.

99 {
100 mp_limb_t b0 = bp[0], b1 = bp[1];
101 mp_limb_t alo = 0, ahi = 0;
102 mp_size_t i = 0;
103
104 /* 双 limb 滚动累加器 alo*B^i + ahi*B^(i+1):t 收纳本位(含 numa[i] 与 b0 行),
105 u 收纳上位(b1 行 + t 进位),两项各 < B^2 无 u128 回绕 */
106 for (; i < n; i++) {
107 __uint128_t t = (__uint128_t)numb[i] * b0 + numa[i] + alo;
108 __uint128_t u = (__uint128_t)numb[i] * b1 + ahi + (mp_limb_t)(t >> 64);
109 numa[i] = (mp_limb_t)t;
110 alo = (mp_limb_t)u;
111 ahi = (mp_limb_t)(u >> 64);
112 }
113 numa[n] = alo;
114 return ahi;
115}

引用了 b0, b1, lmmp_addmul_2_(), n, numb , 以及 t.

被这些函数引用 check_addmul_2(), lmmp_addmul_2_(), lmmp_divexact_basecase_(), lmmp_mont_redc_bc_() , 以及 lmmp_shlnot_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_addshl1_n_()

mp_limb_t lmmp_addshl1_n_ ( mp_ptr dst,
mp_srcptr numa,
mp_srcptr numb,
mp_size_t n )

加法结合左移1位操作 [dst,n] = [numa,n] + ([numb,n] << 1)

参数
dst结果输出指针
numa被加数指针
numb加数指针(先左移1位)
nlimb长度
警告
n>0, eqsep(dst,[numa|numb]), dst!=NULL, numa!=NULL
返回
运算后的进位值 [0|1|2]

在文件 shl.c 第 53 行定义.

53 {
54 mp_limb_t c = 0, mb = 0;
55 mp_size_t i = 0;
56
57#define LMMP_ADDSHL1_STEP(k) \
58 { \
59 mp_limb_t v = numb[i + (k)]; \
60 mp_limb_t lo = (v << 1) | mb; \
61 mb = v >> (LIMB_BITS - 1); \
62 __uint128_t s = (__uint128_t)lo + numa[i + (k)] + c; \
63 dst[i + (k)] = (mp_limb_t)s; \
64 c = (mp_limb_t)(s >> 64); \
65 }
66
67 for (; i + 4 <= n; i += 4) {
72 }
73 for (; i < n; i++) {
75 }
76#undef LMMP_ADDSHL1_STEP
77 return c + mb;
78}
#define LMMP_ADDSHL1_STEP(k)

引用了 lmmp_addshl1_n_(), LMMP_ADDSHL1_STEP, n , 以及 numb.

被这些函数引用 bench_addshl1_n(), lmmp_addshl1_n_(), lmmp_fibonacci_(), lmmp_mul_toom33_(), lmmp_mul_toom42_(), lmmp_mul_toom42_cache_(), lmmp_mul_toom42_cache_init_(), lmmp_mul_toom44_(), lmmp_mul_toom53_(), lmmp_mul_toom62_(), lmmp_mul_toom62_cache_(), lmmp_mul_toom62_cache_init_(), lmmp_shlnot_(), lmmp_sqr_toom3_(), lmmp_sqr_toom4_(), lmmp_sqrlo_dc_(), lmmp_sqrt_divide_(), TEST_CASE(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_b36_to_chars_()

void lmmp_b36_to_chars_ ( mp_byte_t * dst,
mp_size_t n,
bool upper )

36进制数字字节原地转字符 [dst,n]: [0,35] -> ['0'-'9','a'-'z']或['0'-'9','A'-'Z']

参数
dst输入数字字节数组,同时也是字符输出数组
n字节数组长度
upper大小写选择:true输出大写字母,false输出小写字母
警告
n>=0, dst!=NULL, 0<=dst[i]<=35
注解
原地操作,数值数组转化成字符串

在文件 to_chars.c 第 31 行定义.

31 {
32 // x>=10 时 c = x + '0' + adj, adj = 'a'-'0'-10 = 39 (小写) / 'A'-'0'-10 = 7 (大写)
33 // -(x>9) 生成全0/全1掩码,与 adj 按位与实现无分支选择
34 const int adj = upper ? 7 : 39;
35 for (mp_size_t i = 0; i < n; i++) {
36 int x = dst[i];
37 dst[i] = (mp_byte_t)(x + '0' + (-(x > 9) & adj));
38 }
39}
uint8_t mp_byte_t
定义 lmmp.h:91

引用了 lmmp_b36_to_chars_() , 以及 n.

被这些函数引用 lmmp_b36_to_chars_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_bninv_()

void lmmp_bninv_ ( mp_ptr dstq,
mp_srcptr numa,
mp_size_t na,
mp_size_t ni )

近似逆元计算 [dstq,na+ni+2] = B^(2*(na+ni)) / ([numa,na] * B^ni) + [0|-ept]

参数
dstq输出逆元的缓冲区,长度至少为na+ni+2
numa输入指针(长度na)
na输入指针的 limb 长度
ni精度因子
警告
na>0, sep(dstq,numa), dstq!=NULL, numa[na-1]!=0, dstq!=NULL, numa!=NULL
注解
也就是计算 B^(2*na+ni) div [numa,na] + [0|-ept],存在接近2^-64的绝对误差

引用了 LMMP_API , 以及 lmmp_bninv_().

被这些函数引用 lmmp_bninv_(), lmmp_bninv_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_cmp_()

int lmmp_cmp_ ( mp_srcptr numa,
mp_srcptr numb,
mp_size_t n )

比较函数

Copyright (C) 2026 HJimmyK (Jericho Knox)

参数
numa第一个指针,长度为n
numb第二个指针,长度为n
n比较两数的 limb 长度
返回
1(numa>numb) / 0(numa==numb) / -1(numa<numb)
警告
n>0, numa!=NULL, numb!=NULL
注解
从最高位开始逐位比较,直到找到不同位。

比较函数

This file is part of LMMP.

LMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.

SPDX-License-Identifier: LGPL-3.0-or-later

在文件 cmp.c 第 26 行定义.

26 {
28 lmmp_param_assert(numa != NULL);
29 lmmp_param_assert(numb != NULL);
30 /* 顶部剥皮 r = 4,1,2,3 个 limb(依 n mod 4,0 取 4):短行程早退窗口,
31 余段长度恰为 4 的倍数,下方 4-limb 步进无需标量尾与运行时版本化 */
32 mp_size_t r = n & 3;
33 if (r == 0) r = 4;
34 for (mp_size_t k = 0; k < r; k++) {
35 mp_limb_t x = numa[n - 1 - k];
36 mp_limb_t y = numb[n - 1 - k];
37 if (x != y)
38 return (x > y ? 1 : -1);
39 }
40 /* 余段自顶向下按 4 limb 一组:异或折叠判差,有差组内自顶定位 */
41 for (mp_size_t i = n - r; i != 0;) {
42 i -= 4;
43 mp_limb_t d = (numa[i + 0] ^ numb[i + 0]) | (numa[i + 1] ^ numb[i + 1]) |
44 (numa[i + 2] ^ numb[i + 2]) | (numa[i + 3] ^ numb[i + 3]);
45 if (d) {
46 for (mp_size_t j = i + 3; j >= i; j--) {
47 if (numa[j] != numb[j])
48 return (numa[j] > numb[j] ? 1 : -1);
49 }
50 }
51 }
52 return 0;
53}
#define lmmp_param_assert(x)
定义 lmmp.h:509

引用了 k, lmmp_cmp_(), lmmp_param_assert, n , 以及 numb.

被这些函数引用 gcdext_pick_s_(), ipn_lucas_i_(), ipn_mont_add_(), ipn_mont_dbl_(), ipn_notrial_i_(), ipn_proth_i_(), ipn_sprp_1_(), ipn_sprp_base2_(), lmmp_cbrt_3_(), lmmp_cbrt_6_fix_(), lmmp_cmp_(), lmmp_div_(), lmmp_div_basecase_(), lmmp_div_mulinv_(), lmmp_div_s_(), lmmp_gcd_hgcd_(), lmmp_gcd_lehmer_(), lmmp_gcdext_hgcd_(), lmmp_gcdext_lehmer_(), lmmp_gcdext_smag_(), lmmp_hgcd_(), lmmp_hgcd_core_(), lmmp_hgcd_step_(), lmmp_invappr_newton_(), lmmp_lehmer_sub_mag_(), lmmp_modinv_(), lmmp_mont_redc_(), lmmp_mont_sp_redc_(), lmmp_mul_toom22_(), lmmp_mul_toom32_(), lmmp_mul_toom33_(), lmmp_mul_toom42_(), lmmp_mul_toom42_cache_(), lmmp_mul_toom42_cache_init_(), lmmp_mul_toom43_(), lmmp_mul_toom52_(), lmmp_mul_toom53_(), lmmp_mul_toom62_(), lmmp_mul_toom62_cache_init_(), lmmp_sqr_toom2_(), lmmp_sqr_toom3_(), lmmp_toom_eval_dgr3_pm1_(), lmmp_toom_eval_dgr3_pm2_(), lmmp_toom_eval_pm1_(), lmmp_toom_eval_pm2_(), lmmp_toom_eval_pm2exp_(), lmmp_toom_eval_pm2rexp_(), mag_cmp_(), mat22_addsg_(), matrix_equal(), proth_cert_g(), proth_certified(), TEST_CASE(), TEST_CASE() , 以及 try_div_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_dec_to_chars_()

void lmmp_dec_to_chars_ ( mp_byte_t * dst,
mp_size_t n )

十进制数字字节原地转字符 [dst,n]: [0,9] -> ['0','9']

Copyright (C) 2026 HJimmyK (Jericho Knox)

参数
dst输入数字字节数组,同时也是字符输出数组
n字节数组长度
警告
n>=0, dst!=NULL, 0<=dst[i]<=9
注解
原地操作,数值数组转化成字符串

十进制数字字节原地转字符 [dst,n]: [0,9] -> ['0','9']

This file is part of LMMP.

LMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.

SPDX-License-Identifier: LGPL-3.0-or-later

在文件 to_chars.c 第 26 行定义.

26 {
27 for (mp_size_t i = 0; i < n; i++)
28 dst[i] = (mp_byte_t)(dst[i] + (mp_byte_t)'0');
29}

引用了 lmmp_dec_to_chars_() , 以及 n.

被这些函数引用 check_decimal_one() , 以及 lmmp_dec_to_chars_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_div_()

void lmmp_div_ ( mp_ptr dstq,
mp_ptr dstr,
mp_srcptr numa,
mp_size_t na,
mp_srcptr numb,
mp_size_t nb )

除法和取模操作

参数
dstq商结果输出指针(NULL表示不计算商)
dstr余数结果输出指针(NULL表示不计算余数)
numa被除数指针
na被除数的 limb 长度
numb除数指针
nb除数的 limb 长度
警告
0<nb<=na, numb[nb-1]!=0, sep(dstq,[numa|numb]), eqsep(dstr,[numa|numb])) numa!=NULL, numb!=NULL 特殊情况: nb==1时, dstq>=numa-1 是允许的 nb==2时, dstq>=numa 是允许的
注解
如果dstq不为NULL: [dstq,na-nb+1] = [numa,na] / [numb,nb] (商) 如果dstr不为NULL: [dstr,nb] = [numa,na] mod [numb,nb] (余数)

在文件 div.c 第 85 行定义.

85 {
86 lmmp_param_assert(na >= nb);
87 lmmp_param_assert(numa != NULL && numb != NULL && nb > 0);
88 lmmp_param_assert(numb[nb - 1] > 0);
89 if (nb == 1) {
90 mp_limb_t rem = lmmp_div_1_(dstq, numa, na, *numb);
91 if (dstr)
92 *dstr = rem;
93 } else if (nb == 2) {
94 mp_limb_t brem[2];
95 brem[0] = numb[0];
96 brem[1] = numb[1];
97 lmmp_div_2_(dstq, numa, na, brem);
98 if (dstr) {
99 dstr[0] = brem[0];
100 dstr[1] = brem[1];
101 }
102 } else {
103 int adjust = numa[na - 1] >= numb[nb - 1];
104 int cnt = lmmp_leading_zeros_(numb[nb - 1]);
105 mp_size_t nq = na + adjust - nb;
106 if (nq == 0) {
107 if (dstr && dstr != numa)
108 lmmp_copy(dstr, numa, nb);
109 if (dstq)
110 dstq[0] = 0;
111 return;
112 }
113 TEMP_DECL;
114
115 if (!dstq)
116 dstq = TALLOC_TYPE(na - nb + 1, mp_limb_t);
117 dstq[na - nb] = 0;
118
119 if (nq >= nb) {
120 mp_ptr restrict numa2 = TALLOC_TYPE(na + 1, mp_limb_t);
121 mp_ptr numb2;
122 if (cnt) {
123 numa2[na] = lmmp_shl_(numa2, numa, na, cnt);
124 numb2 = TALLOC_TYPE(nb, mp_limb_t);
125 lmmp_shl_(numb2, numb, nb, cnt);
126 } else {
127 numa2[na] = 0;
128 lmmp_copy(numa2, numa, na);
129 numb2 = (mp_ptr)numb;
130 }
131
132 mp_limb_t inv21 = lmmp_inv_2_1_(numb2[nb - 1], numb2[nb - 2]);
133 na += adjust;
134
135 if (nb < DIV_DIVIDE_THRESHOLD)
136 lmmp_div_basecase_(dstq, numa2, na, numb2, nb, inv21);
137 else if (nb < DIV_MULINV_L_THRESHOLD || na < 2 * DIV_MULINV_N_THRESHOLD)
138 lmmp_div_divide_(dstq, numa2, na, numb2, nb, inv21);
139 else {
140 mp_limb_t ni = lmmp_div_inv_size_(nq, nb);
141 mp_ptr invappr = TALLOC_TYPE(ni, mp_limb_t);
142 lmmp_inv_prediv_(invappr, numb2, nb, ni);
143 lmmp_div_mulinv_(dstq, numa2, na, numb2, nb, invappr, ni);
144 }
145
146 if (dstr) {
147 lmmp_shr_(dstr, numa2, nb, cnt); // cnt=0 时函数内即整段拷贝
148 }
149 } else {
150 // nq=na-nb+adj<nb
151 //-> na+adj>=2nq+1
152 mp_size_t ni = nb - nq;
153 mp_ptr numa2, numb2;
155 mp_limb_t cy;
156
157 numa2 = TALLOC_TYPE(nq * 2 + 1, mp_limb_t);
158 if (cnt) {
159 numb2 = TALLOC_TYPE(nq, mp_limb_t);
160 lmmp_shl_(numb2, numb + ni, nq, cnt);
161 numb2[0] |= numb[ni - 1] >> (LIMB_BITS - cnt);
162 cy = lmmp_shl_(numa2, numa + na - 2 * nq, 2 * nq, cnt);
163 if (adjust) {
164 numa2[2 * nq] = cy;
165 ++numa2; // numa2[0] is as significant as numa[ni=na-2nq+adjust]
166 } else
167 numa2[0] |= numa[na - 2 * nq - 1] >> (LIMB_BITS - cnt);
168 } else {
169 numb2 = (mp_ptr)numb + ni;
170 lmmp_copy(numa2, numa + na - 2 * nq, 2 * nq);
171 if (adjust) {
172 numa2[2 * nq] = 0;
173 ++numa2;
174 }
175 }
176
177 // now: 0<=numa2<B^2nq, B^nq/2<=numb2<B^nq, and 0<=numa2/numb2<B^nq
178 // ignored bits could be seen as fraction part of numa and numb
179 // we can prove: Q<=Qh<=Q+2
180 // where Q=floor(numa/numb) is the real quotient
181 // Qh=floor(floor(numa)/floor(numb)) as below
182
183 if (nq == 1) {
184 lmmp_div_1_s_(dstq, numa2, 2, *numb2);
185 } else if (nq == 2) {
186 lmmp_div_2_s_(dstq, numa2, 4, numb2);
187 } else {
188 mp_limb_t inv21 = lmmp_inv_2_1_(numb2[nq - 1], numb2[nq - 2]);
189
190 if (nq < DIV_DIVIDE_THRESHOLD)
191 lmmp_div_basecase_(dstq, numa2, 2 * nq, numb2, nq, inv21);
192 else if (nq < DIV_MULINV_N_THRESHOLD)
193 lmmp_div_divide_(dstq, numa2, 2 * nq, numb2, nq, inv21);
194 else {
195 mp_size_t inv_ni = lmmp_div_inv_size_(nq, nq);
196 mp_ptr invappr = tp;
197 lmmp_inv_prediv_(invappr, numb2, nq, inv_ni);
198 lmmp_div_mulinv_(dstq, numa2, 2 * nq, numb2, nq, invappr, inv_ni);
199 }
200 }
201 /*
202 true remainder = partial remainder - quotient * ignored divisor limbs
203
204 Multiply the first ignored divisor limb by the most significant
205 quotient limb. If that product is > the partial remainder's
206 most significant limb, we know the quotient is too large. This
207 test quickly catches most cases where the quotient is too large;
208 it catches all cases where the quotient is 2 too large.*/
209
210 mp_limb_t x;
211 if (cnt) {
212 mp_limb_t dl;
213 if (ni < 2)
214 dl = 0;
215 else
216 dl = numb[ni - 2];
217 x = (numb[ni - 1] << cnt) | (dl >> (LIMB_BITS - cnt));
218 } else
219 x = numb[ni - 1];
220 mp_limb_t h = (x >> LIMB_BITS / 2) * (dstq[nq - 1] >> LIMB_BITS / 2);
221 mp_limb_t rnb = 0; // remainder[nb]
222 mp_size_t nr = nq; // remainder=rnb:[numa2,nr]:[...,ni]
223
224 if (h > numa2[nq - 1]) {
225 lmmp_dec(dstq);
226 rnb = lmmp_add_n_(numa2, numa2, numb2, nq);
227 }
228
229 // if cnt, recover the shift of partial remainder
230 // and remove the effect of the partial-ignored numa[ni-1] and numb[ni-1]
231 if (cnt) {
232 numa2[nq] = rnb;
233 ++nr;
234 --ni;
235 lmmp_shl_(numa2, numa2, nr, LIMB_BITS - cnt);
236 numa2[0] |= numa[ni] & (LIMB_MAX >> cnt);
237 cy = lmmp_submul_1_(numa2, dstq, nq, numb[ni] & (LIMB_MAX >> cnt));
238 rnb = -(numa2[nq] < cy);
239 numa2[nq] -= cy;
240 }
241
242 if (ni == 0) {
243 if (dstr) {
244 if (rnb)
245 lmmp_add_n_(dstr, numa2, numb, nr);
246 else
247 lmmp_copy(dstr, numa2, nr);
248 }
249 } else {
250 tp[nb - 1] = 0;
251 if (ni < nq)
252 lmmp_mul_(tp, dstq, nq, numb, ni);
253 else
254 lmmp_mul_(tp, numb, ni, dstq, nq);
255
256 if (dstr) {
257 mp_ptr remptr = dstr == numb ? tp : dstr;
258 cy = lmmp_sub_n_(remptr, numa, tp, ni);
259 rnb -= lmmp_sub_nc_(remptr + ni, numa2, tp + ni, nr, cy);
260 if (rnb)
261 lmmp_add_n_(dstr, remptr, numb, nb);
262 else if (dstr != remptr)
263 lmmp_copy(dstr, remptr, nb);
264 } else {
265 int hcmp = lmmp_cmp_(numa2, tp + ni, nr);
266 if (hcmp < 0)
267 --rnb;
268 else if (hcmp == 0)
269 rnb -= (lmmp_cmp_(numa, tp, ni) < 0);
270 }
271 }
272
273 if (rnb)
274 lmmp_dec(dstq);
275 }
276
277 TEMP_FREE;
278 }
279}
#define lmmp_leading_zeros_
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
#define LIMB_MAX
定义 lmmp.h:105
#define LIMB_BITS
定义 lmmp.h:102
#define DIV_DIVIDE_THRESHOLD
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define DIV_MULINV_N_THRESHOLD
#define DIV_MULINV_L_THRESHOLD
static mp_size_t lmmp_div_inv_size_(mp_size_t nq, mp_size_t nb)
计算预计算逆元的尺寸
mp_limb_t lmmp_div_1_s_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_limb_t x)
单精度数除法(除数为1个limb)
mp_limb_t lmmp_div_1_(mp_ptr dstq, mp_srcptr numa, mp_size_t na, mp_limb_t x)
单精度数除法
定义 div.c:137
#define lmmp_dec(p)
减1宏(预期无借位)
void lmmp_inv_prediv_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t ni)
除法前的逆元预计算,[dst,ni] = invappr( (ni+1 MSLs of numa) + 1 ) / B
void lmmp_div_2_(mp_ptr dstq, mp_srcptr numa, mp_size_t na, mp_ptr numb)
双精度数除法 (除数为2个limb)
定义 div.c:294
mp_limb_t lmmp_shr_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shr)
右移操作 [dst,na] = [numa,na]>>shr,dst的高shr位填充0
定义 shr.c:26
void lmmp_mul_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
不等长乘法操作 [dst,na+nb] = [numa,na] * [numb,nb]
int lmmp_cmp_(mp_srcptr numa, mp_srcptr numb, mp_size_t n)
比较函数
定义 cmp.c:26
mp_limb_t lmmp_shl_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shl)
左移操作 [dst,na] = [numa,na]<<shl,dst的低shl位填充0
定义 shl.c:26
mp_limb_t lmmp_div_mulinv_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, mp_srcptr invappr, mp_size_t ni)
乘法逆元除法
mp_limb_t lmmp_div_2_s_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb)
双精度数除法(除数为2个limb)
mp_limb_t lmmp_submul_1_(mp_ptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t b)
乘以单limb并累减操作 [numa,n] -= [numb,n] * b
mp_limb_t lmmp_sub_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
无借位的n位减法 [dst,n] = [numa,n] - [numb,n]
定义 sub_n.c:84
mp_limb_t lmmp_inv_2_1_(mp_limb_t xh, mp_limb_t xl)
2-1阶逆元计算 (inv21)
定义 inv.c:27
mp_limb_t lmmp_div_basecase_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, mp_limb_t inv21)
基础除法运算
mp_limb_t lmmp_sub_nc_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t c)
带借位的n位减法 [dst,n] = [numa,n] - [numb,n] - c
定义 sub_n.c:67
mp_limb_t lmmp_div_divide_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, mp_limb_t inv21)
分治除法运算
#define tp
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define TEMP_FREE
#define TALLOC_TYPE(n, type)

引用了 DIV_DIVIDE_THRESHOLD, DIV_MULINV_L_THRESHOLD, DIV_MULINV_N_THRESHOLD, LIMB_BITS, LIMB_MAX, lmmp_add_n_(), lmmp_cmp_(), lmmp_copy, lmmp_dec, lmmp_div_(), lmmp_div_1_(), lmmp_div_1_s_(), lmmp_div_2_(), lmmp_div_2_s_(), lmmp_div_basecase_(), lmmp_div_divide_(), lmmp_div_inv_size_(), lmmp_div_mulinv_(), lmmp_inv_2_1_(), lmmp_inv_prediv_(), lmmp_leading_zeros_, lmmp_mul_(), lmmp_param_assert, lmmp_shl_(), lmmp_shr_(), lmmp_sub_n_(), lmmp_sub_nc_(), lmmp_submul_1_(), numb, restrict, TALLOC_TYPE, TEMP_DECL, TEMP_FREE , 以及 tp.

被这些函数引用 bench_div(), bench_powmod_even(), divides_all(), fill_odd_mod(), lmmp_bninv_(), lmmp_div_(), lmmp_div_s_(), lmmp_gcd_hgcd_(), lmmp_gcd_lehmer_(), lmmp_gcdext_1_(), lmmp_gcdext_2_(), lmmp_gcdext_hgcd_(), lmmp_gcdext_lehmer_(), lmmp_hgcd_step_(), lmmp_modinv_(), lmmp_mont_redcify_(), lmmp_nthroot_(), lmmp_powmod_(), lmmp_powmod_2_(), make_odd_mod(), mulmod_limbs(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE() , 以及 try_div_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_div_1_()

mp_limb_t lmmp_div_1_ ( mp_ptr dstq,
mp_srcptr numa,
mp_size_t na,
mp_limb_t x )

单精度数除法

参数
dstq输出商的缓冲区(可为NULL,此时仅计算余数)
numa输入被除数,长度为na
na被除数的 limb 长度
x除数(单个 limb )
返回
除法余数(单个 limb )
警告
na>0, x!=0, eqsep(dstq,numa),
eqsep(numa,dstq), numa!=NULL, na>0, x>0, dstq>=numa-1 是可以接受的
注解
if (dstq!=NULL) [dstq,na] = [numa,na] div x

在文件 div.c 第 137 行定义.

137 {
138 mp_limb_t ah, al;
139 if (na == 1) {
140 ah = numa[0];
141 if (dstq)
142 dstq[0] = ah / x;
143 return ah % x;
144 }
145 if (dstq) {
146 mp_limb_t t = numa[na - 2], q = 0, r = 0;
147 const int shift = lmmp_leading_zeros_(x);
148 if (shift > 0) {
149 /*
150 ah al
151 X|XXXtttX|XXXmmmX|XXXnnnX|XXX----|
152 |000XXXX|tttXXXX|mmmXXXX|nnnXXXX|
153 t numa[na]
154
155 ah al
156 X|XXXtttX|XXXmmmX|XXXnnnX|XXX----|
157 |000XXXX|tttXXXX|mmmXXXX|nnnXXXX|
158 t
159 numa[na]
160 */
161 const int rshift = LIMB_BITS - shift;
162 ah = numa[na - 1] >> rshift;
163 t = numa[na - 2];
164 al = (numa[na - 1] << shift) | (t >> rshift);
165 x <<= shift;
166 const mp_limb_t inv = lmmp_inv_1_(x);
167 _udiv_qrnnd_preinv(q, r, ah, al, x, inv);
168 dstq[na - 1] = q;
169 na -= 2;
170 while (na-- > 0) {
171 ah = r;
172 al = t << shift;
173 t = numa[na];
174 al |= t >> rshift;
175 _udiv_qrnnd_preinv(q, r, ah, al, x, inv);
176 dstq[na + 1] = q;
177 }
178 ah = r;
179 al = t << shift;
180 _udiv_qrnnd_preinv(q, r, ah, al, x, inv);
181 dstq[0] = q;
182 return r >> shift;
183 } else {
184 /*
185 ah al
186 |000XXXX|tttXXXX|mmmXXXX|nnnXXXX|
187 t numa[na]
188 */
189 ah = 0;
190 t = numa[na - 2];
191 al = numa[na - 1];
192 const mp_limb_t inv = lmmp_inv_1_(x);
193 q = al / x;
194 r = al % x;
195 dstq[na - 1] = q;
196 na -= 2;
197 while (na-- > 0) {
198 ah = r;
199 al = t;
200 t = numa[na];
201 _udiv_qrnnd_preinv(q, r, ah, al, x, inv);
202 dstq[na + 1] = q;
203 }
204 ah = r;
205 al = t;
206 _udiv_qrnnd_preinv(q, r, ah, al, x, inv);
207 dstq[0] = q;
208 return r;
209 }
210 } else {
211 return lmmp_mod_1_(numa, na, x);
212 }
213}
mp_limb_t lmmp_mod_1_(mp_srcptr numa, mp_size_t na, mp_limb_t x)
单精度数取余
定义 div.c:38
mp_limb_t lmmp_inv_1_(mp_limb_t x)
1阶逆元计算 (inv1)
定义 inv.c:124
#define _udiv_qrnnd_preinv(q, r, nh, nl, d, di)

引用了 _udiv_qrnnd_preinv, LIMB_BITS, lmmp_div_1_(), lmmp_inv_1_(), lmmp_leading_zeros_, lmmp_mod_1_() , 以及 t.

被这些函数引用 bench_div_1(), lmmp_bninv_(), lmmp_cbrt_(), lmmp_cbrt_divide_(), lmmp_div_(), lmmp_div_1_(), lmmp_div_3_2_(), lmmp_invcbrt_newton_(), lmmp_nthroot_(), lmmp_to_str_basecase_(), ref_digits(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_div_1_s_()

mp_limb_t lmmp_div_1_s_ ( mp_ptr dstq,
mp_ptr numa,
mp_size_t na,
mp_limb_t x )

单精度数除法(除数为1个limb)

参数
dstq输出商的缓冲区,长度至少为na-1
numa输入被除数(长度na),运算后存储余数(长度1)
na被除数的 limb 长度
x除数(单个 limb )
返回
商的最高位(qh)
警告
na>1, MSB(x)=1, sep(dstq,numa), dstq!=NULL, numa!=NULL
注解
qh:[dstq,na-1]=[numa,na] div x, [numa,1]=[numa,na] mod x, return qh

引用了 LMMP_API , 以及 lmmp_div_1_s_().

被这些函数引用 bench_div_1_s(), lmmp_div_(), lmmp_div_1_s_(), lmmp_div_1_s_(), lmmp_div_s_(), TEST_CASE() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_div_2_()

void lmmp_div_2_ ( mp_ptr dstq,
mp_srcptr numa,
mp_size_t na,
mp_ptr numb )

双精度数除法 (除数为2个limb)

参数
dstq输出商的缓冲区,长度至少为na-1(可为NULL,此时仅计算余数)
numa输入被除数(长度na)
na被除数的 limb 长度
numb输入除数(长度2)[numb,2]=[numa,na] mod [numb,2]
警告
na>=2, numb[1]!=0, eqsep(dstq,numa), numa!=NULL, numb!=NULL, dstq>=numa 是可以接受的
注解
if (dstq!=NULL) [dstq,na-1]=[numa,na] div [numb,2]

在文件 div.c 第 294 行定义.

294 {
295 mp_limb_t q, r1, r0, a2, a1, a0, b1, b0;
296 b1 = numb[1];
297 b0 = numb[0];
298 if (na == 2) {
299 int shift = lmmp_leading_zeros_(b1);
300 if (shift > 0) {
301 const int rshift = LIMB_BITS - shift;
302 b1 = (b1 << shift) | (b0 >> rshift);
303 b0 <<= shift;
304 a2 = numa[1] >> rshift;
305 a1 = (numa[1] << shift) | (numa[0] >> rshift);
306 a0 = (numa[0] << shift);
308 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
309 if (dstq)
310 dstq[0] = q;
311 numb[0] = (r0 >> shift) | (r1 << rshift);
312 numb[1] = r1 >> shift;
313 return;
314 } else {
315 u128 a = _u128load(numa), b = _u128load(numb);
316 if (a < b) {
317 _u128store(numb, a);
318 if (dstq)
319 dstq[0] = 0;
320 return;
321 } else {
322 _u128store(numb, a - b);
323 if (dstq)
324 dstq[0] = 1;
325 return;
326 }
327 }
328 }
329 if (dstq) {
330 int shift = lmmp_leading_zeros_(b1);
331 if (shift > 0) {
332 /*
333 a2 a1 a0
334 X|XXXtttX|XXXmmmX|XXXnnnX|XXX----|
335 |000XXXX|tttXXXX|mmmXXXX|nnnXXXX|
336 numa[na]
337 */
338 const int rshift = LIMB_BITS - shift;
339 b1 = (b1 << shift) | (b0 >> rshift);
340 b0 <<= shift;
341 const mp_limb_t inv = lmmp_inv_2_1_(b1, b0);
342 a2 = numa[na - 1] >> rshift;
343 a1 = (numa[na - 1] << shift) | (numa[na - 2] >> rshift);
344 a0 = (numa[na - 2] << shift) | (numa[na - 3] >> rshift);
345 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
346 dstq[na - 2] = q;
347 na -= 2;
348 while (na-- > 1) {
349 a2 = r1;
350 a1 = r0;
351 a0 = (numa[na] << shift) | (numa[na - 1] >> rshift);
352 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
353 dstq[na] = q;
354 }
355
356 a2 = r1;
357 a1 = r0;
358 a0 = (numa[na] << shift);
359 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
360 dstq[0] = q;
361 numb[0] = (r0 >> shift) | (r1 << rshift);
362 numb[1] = r1 >> shift;
363 return;
364 } else {
365 /*
366 a2 a1 a0
367 |000XXXX|tttXXXX|mmmXXXX|nnnXXXX|
368 numa[na]
369 */
370 const mp_limb_t inv = lmmp_inv_2_1_(b1, b0);
371 a2 = 0;
372 a1 = numa[na - 1];
373 a0 = numa[na - 2];
374 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
375 dstq[na - 2] = q;
376 na -= 2;
377 while (na-- > 1) {
378 a2 = r1;
379 a1 = r0;
380 a0 = numa[na];
381 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
382 dstq[na] = q;
383 }
384 a2 = r1;
385 a1 = r0;
386 a0 = numa[na];
387 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
388 dstq[0] = q;
389 numb[0] = r0;
390 numb[1] = r1;
391 return;
392 }
393 } else {
394 int shift = lmmp_leading_zeros_(b1);
395 if (shift > 0) {
396 const int rshift = LIMB_BITS - shift;
397 b1 = (b1 << shift) | (b0 >> rshift);
398 b0 <<= shift;
399 const mp_limb_t inv = lmmp_inv_2_1_(b1, b0);
400 a2 = numa[na - 1] >> rshift;
401 a1 = (numa[na - 1] << shift) | (numa[na - 2] >> rshift);
402 a0 = (numa[na - 2] << shift) | (numa[na - 3] >> rshift);
403 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
404 na -= 2;
405 while (na-- > 1) {
406 a2 = r1;
407 a1 = r0;
408 a0 = (numa[na] << shift) | (numa[na - 1] >> rshift);
409 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
410 }
411
412 a2 = r1;
413 a1 = r0;
414 a0 = (numa[na] << shift);
415 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
416 numb[0] = (r0 >> shift) | (r1 << rshift);
417 numb[1] = r1 >> shift;
418 return;
419 } else {
420 const mp_limb_t inv = lmmp_inv_2_1_(b1, b0);
421 a2 = 0;
422 a1 = numa[na - 1];
423 a0 = numa[na - 2];
424 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
425 na -= 2;
426 while (na-- > 1) {
427 a2 = r1;
428 a1 = r0;
429 a0 = numa[na];
430 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
431 }
432 a2 = r1;
433 a1 = r0;
434 a0 = numa[na];
435 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
436 numb[0] = r0;
437 numb[1] = r1;
438 return;
439 }
440 }
441}
#define _udiv_qr_3by2(q, r1, r0, n2, n1, n0, d1, d0, dinv)
#define r1
#define r0

引用了 _udiv_qr_3by2, a0, a1, a2, b0, b1, LIMB_BITS, lmmp_div_2_(), lmmp_inv_2_1_(), lmmp_leading_zeros_, numb, r0 , 以及 r1.

被这些函数引用 bench_div_2(), ll_small_preinv(), lmmp_bninv_(), lmmp_div_(), lmmp_div_2_(), lmmp_div_3_2_(), mont2_preinv() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_div_2_s_()

mp_limb_t lmmp_div_2_s_ ( mp_ptr dstq,
mp_ptr numa,
mp_size_t na,
mp_srcptr numb )

双精度数除法(除数为2个limb)

参数
dstq输出商的缓冲区,长度至少为na-2
numa输入被除数(长度na),运算后存储余数(长度2)
na被除数的 limb 长度
numb输入除数,长度为2
返回
商的最高位(qh)
警告
na>2, MSB(numb)=1, sep(dstq,numa,numb), dstq!=NULL, numa!=NULL, numb!=NULL
注解
qh:[dstq,na-2]=[numa,na] div [numb,2], [numa,2]=[numa,na] mod [numb,2], return qh

引用了 LMMP_API, lmmp_div_2_s_() , 以及 numb.

被这些函数引用 bench_div_2_s(), lmmp_div_(), lmmp_div_2_s_(), lmmp_div_2_s_(), lmmp_div_s_(), lmmp_inv_basecase_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_div_3_2_()

mp_limb_t lmmp_div_3_2_ ( mp_ptr numa,
mp_srcptr numb,
mp_limb_t inv21 )

3/2位除法运算 [numa,2]=[numa,3] mod [numb,2]

参数
numa输入被除数(长度3),运算后存储余数(长度2)
numb输入除数(长度2)
inv21除数的2-1阶逆元(提前计算好的inv21([numb,2]))
警告
[numa,3]<[numb,2]*B, MSB(numb)=1, inv21=inv21([numb,2]), eqsep(numa,numb), numb!=NULL, numa!=NULL
返回
商值(单精度数)

引用了 k, LMMP_API, lmmp_div_1_(), lmmp_div_2_(), lmmp_div_3_2_(), lmmp_mod_1_(), lmmp_mod_2_(), lmmp_mod_preinv_1_() , 以及 numb.

被这些函数引用 bench_div_3_2(), lmmp_div_3_2_(), lmmp_div_3_2_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_div_basecase_()

mp_limb_t lmmp_div_basecase_ ( mp_ptr dstq,
mp_ptr numa,
mp_size_t na,
mp_srcptr numb,
mp_size_t nb,
mp_limb_t inv21 )

基础除法运算

参数
dstq输出商的缓冲区,长度至少为na-nb
numa输入被除数(长度na),运算后存储余数(长度nb)
na被除数的 limb 长度
numb输入除数,长度为nb
nb除数的 limb 长度
inv21除数的2-1阶逆元(inv21([numb+nb-2,2]))
返回
商的最高位(qh)
警告
na>=nb>=3, MSB(numb)=1, inv21=inv21([numb+nb-2,2]), sep(dstq,numa,numb), dstq!=NULL, numa!=NULL, numb!=NULL
注解
qh:[dstq,na-nb]=[numa,na] div [numb,nb], [numa,na-nb]=[numa,na] mod [numb,nb], return qh

引用了 LMMP_API, lmmp_div_basecase_() , 以及 numb.

被这些函数引用 lmmp_bninv_appr_newton_(), lmmp_div_(), lmmp_div_basecase_(), lmmp_div_basecase_(), lmmp_div_divide_n_(), lmmp_div_s_(), lmmp_inv_basecase_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_div_divide_()

mp_limb_t lmmp_div_divide_ ( mp_ptr dstq,
mp_ptr numa,
mp_size_t na,
mp_srcptr numb,
mp_size_t nb,
mp_limb_t inv21 )

分治除法运算

参数
dstq输出商的缓冲区,长度至少为na-nb
numa输入被除数(长度na),运算后存储余数(长度nb)
na被除数的 limb 长度
numb输入除数,长度为nb
nb除数的 limb 长度
inv21除数的2-1阶逆元(inv21([numb+nb-2,2]))
返回
商的最高位(qh)
警告
na>=2*nb, nb>=6, MSB(numb)=1, inv21=inv21([numb+nb-2,2]), sep(dstq,numa,numb), dstq!=NULL, numa!=NULL, numb!=NULL
注解
qh:[dstq,na-nb]=[numa,na] div [numb,nb], [numa,na-nb]=[numa,na] mod [numb,nb], return qh

引用了 lmmp_div_divide_() , 以及 numb.

被这些函数引用 lmmp_div_(), lmmp_div_divide_(), lmmp_div_divide_(), lmmp_div_s_(), lmmp_inv_basecase_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_div_inv_size_()

mp_size_t lmmp_div_inv_size_ ( mp_size_t nq,
mp_size_t nb )
inlinestatic

计算预计算逆元的尺寸

参数
nq商的 limb 长度
nb除数的 limb 长度
返回
计算需要预计算逆元尺寸ni(ni<=nb)
注解
用于已归一化除法([nq+nb]/[nb]=[nq])的逆元 ni 尺寸

在文件 lmmpn.h 第 985 行定义.

985 {
986 mp_size_t ni, b;
987 if (nq > nb) {
988 b = (nq - 1) / nb + 1; // ceil(nq/nb), number of blocks
989 ni = (nq - 1) / b + 1; // ceil(nq/b)
990 } else if (3 * nq > nb) {
991 ni = (nq - 1) / 2 + 1; // b=2
992 } else {
993 ni = (nq - 1) / 1 + 1; // b=1
994 }
995 return ni;
996}

引用了 lmmp_div_inv_size_() , 以及 LMMP_INLINE.

被这些函数引用 dec_pow_extend_(), lmmp_div_(), lmmp_div_inv_size_(), lmmp_div_s_() , 以及 lmmp_to_str_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_div_mulinv_()

mp_limb_t lmmp_div_mulinv_ ( mp_ptr dstq,
mp_ptr numa,
mp_size_t na,
mp_srcptr numb,
mp_size_t nb,
mp_srcptr invappr,
mp_size_t ni )

乘法逆元除法

参数
dstq输出商的缓冲区,长度至少为na-nb
numa输入被除数(长度na),运算后存储余数(长度nb)
na被除数的 limb 长度
numb输入除数,长度为nb
nb除数的 limb 长度
invappr预计算的近似逆元,长度为ni
ni预计算逆元的 limb 长度
返回
商的最高位(qh)
警告
na>=nb>=ni>0, MSB(numb)=1, [invappr,ni]=inv_prediv([numb,nb]), sep(dstq,numa,numb,invappr)) dstq!=NULL, numa!=NULL, numb!=NULL, invappr!=NULL
注解
qh:[dstq,na-1]=[numa,na] div x, [numa,1]=[numa,na] mod x, return qh

引用了 lmmp_div_mulinv_() , 以及 numb.

被这些函数引用 lmmp_div_(), lmmp_div_mulinv_(), lmmp_div_mulinv_(), lmmp_div_s_() , 以及 lmmp_to_str_divide_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_div_s_()

mp_limb_t lmmp_div_s_ ( mp_ptr dstq,
mp_ptr numa,
mp_size_t na,
mp_srcptr numb,
mp_size_t nb )

除法运算

参数
dstq输出商的缓冲区,长度至少为na-nb
numa输入被除数(长度na),运算后存储余数(长度nb)
na被除数的 limb 长度
numb输入除数,长度为nb
nb除数的 limb 长度
返回
商的最高位(qh)
警告
na>=nb>0, MSB(numb)=1, sep(dstq,numa,numb), dstq!=NULL, numa!=NULL, numb!=NULL
注解
qh:[dstq,na-nb]=[numa,na] div [numb,nb], [numa,nb]=[numa,na] mod [numb,nb], return qh

引用了 LMMP_API, lmmp_div_(), lmmp_div_s_() , 以及 numb.

被这些函数引用 lmmp_cbrt_6_fast_(), lmmp_cbrt_divide_(), lmmp_div_divide_(), lmmp_div_s_(), lmmp_div_s_(), lmmp_invcbrt_newton_(), lmmp_invsqrt_newton_(), lmmp_sqrt_divide_(), lmmp_to_str_divide_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_endian()

bool lmmp_endian ( void )
inlinestatic

运行时判断端序

返回
true 表示小端序,false 表示大端序

在文件 lmmpn.h 第 40 行定义.

40 {
41 int num = 1;
42 return (*(char*)&num) != 0;
43}

引用了 lmmp_endian() , 以及 LMMP_INLINE.

被这些函数引用 lmmp_endian() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_extract_bits_()

mp_bitcnt_t lmmp_extract_bits_ ( mp_srcptr num,
mp_size_t n,
mp_limb_t * ext,
int bits )

提取高位指定位数,并返回低位bits位数

参数
num待提取的指针
nnum的 limb 长度
bits待提取的位数(1-64)
ext提取结果输出指针
警告
n>0, 1<=bits<=64, ext!=NULL, num!=NULL
注解
如果bits大于num的实际位数,则不会保证ext有效位数为bits位; 如果bits小于等于num的实际位数,则ext将会有bits位有效位数。
返回
剩余的低位bits数量

引用了 LMMP_API, lmmp_extract_bits_() , 以及 n.

被这些函数引用 lmmp_extract_bits_() , 以及 lmmp_extract_bits_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_fft_next_size_()

mp_size_t lmmp_fft_next_size_ ( mp_size_t n)

计算满足 >=n 的最小费马/梅森乘法可行尺寸

参数
n输入的目标尺寸
返回
满足条件的SSA乘法最小尺寸

在文件 fft_ssa.c 第 95 行定义.

95 {
99 n = (((n - 1) >> k) + 1) << k;
100 return n;
101}
mp_size_t lmmp_fft_best_k_(mp_size_t n)
查找对于 m>=n 的模 B^m+1 FFT运算的最优k值
#define lmmp_debug_assert(x)
定义 lmmp.h:498
#define LOG2_LIMB_BITS
定义 lmmp.h:104

引用了 k, lmmp_debug_assert, lmmp_fft_best_k_(), lmmp_fft_next_size_(), LOG2_LIMB_BITS , 以及 n.

被这些函数引用 bench_mul_mersenne_fft(), lmmp_binvert_unbalance_(), lmmp_div_mulinv_(), lmmp_divexact_mu_run_(), lmmp_fft_next_size_(), lmmp_hgcd_apply_mod_(), lmmp_mersenne_next_size_(), lmmp_mont_init_(), lmmp_mont_need_(), lmmp_mul_fft_(), lmmp_mul_fft_unbalance_(), lmmp_mul_mersenne_(), lmmp_mul_toom62_unbalance_(), lmmp_mullo_fft_(), lmmp_mullo_fft_cache_init_(), lmmp_sqr_fft_(), lmmp_sqr_mersenne_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_from_decimal_()

mp_size_t lmmp_from_decimal_ ( mp_ptr dst,
const char * src,
mp_size_t len )

十进制字符串转limb数组 [src,len,10] to [dst,return value,B]

参数
dst结果输出指针
src字符串源指针
len字符串长度
警告
len>=0, dst!=NULL, src!=NULL, src[i] in {'0'-'9'}
注解
低位digit在数组前端;将忽略末尾的'0'; dst 需要 lmmp_from_decimal_len_(src,len) 的长度(转换过程中作为临时空间使用)
返回
转换后的结果的 limb 长度(零值返回0)

在文件 from_decimal.c 第 43 行定义.

43 {
44 lmmp_param_assert(dst != NULL && src != NULL);
45 do {
46 if (len == 0)
47 return 0;
48 } while (src[--len] == '0');
49 ++len;
50
52 return lmmp_from_str_basecase_(dst, (const mp_byte_t*)src, len, DEC_BASE, '0');
53
54 // 惰性获取全局幂表(置于 TEMP_B_DECL 之前,幂表持久堆分配与临时分配互不干扰)
55 mp_size_t grps = (len - 1) / lmmp_bases_table[DEC_BASE - 2].digits_in_limb + 1;
56 int ctop;
57 mp_basepow_t* pows = lmmp_dec_pow_table_(grps, &ctop);
58
59 mp_size_t limbs = lmmp_from_str_len_(0, len, DEC_BASE);
61 // 结果缓冲(多 1 limb)+ 各层非归一化幂值副本
62 //(引擎乘法需要真值,而幂表存的是归一化值)
63 mp_size_t alloc = limbs + 1;
64 for (int i = 0; i <= ctop; ++i)
65 alloc += pows[i].np + 1;
67
69 mp_ptr cp = tp + limbs + 1;
70 for (int i = 0; i <= ctop; ++i) {
71 upows[i] = pows[i];
72 lmmp_copy(cp, pows[i].p, pows[i].np);
73 if (pows[i].norm_cnt)
74 lmmp_shr_(cp, cp, pows[i].np, pows[i].norm_cnt);
75 upows[i].p = cp;
76 cp += pows[i].np + 1;
77 }
78
79 limbs = lmmp_from_str_divide_(tp, (const mp_byte_t*)src, len, upows + ctop, dst, '0');
80 lmmp_copy(dst, tp, limbs);
81
83 return limbs;
84}
#define FROM_STR_BASEPOW_THRESHOLD
mp_size_t lmmp_from_str_len_(const mp_byte_t *src, mp_size_t len, int base)
计算字节数组转limb数组所需的 limb 缓冲区长度
mp_basepow_t * lmmp_dec_pow_table_(mp_size_t grps, int *ctop)
获取(惰性构建/扩展)全局十进制幂表
mp_size_t lmmp_from_str_basecase_(mp_ptr dst, const mp_byte_t *src, mp_size_t len, int base, mp_byte_t off)
basecase 字节串转 limb 数组引擎
mp_size_t lmmp_from_str_divide_(mp_ptr dst, const mp_byte_t *src, mp_size_t len, mp_basepow_t *pow, mp_ptr tp, mp_byte_t off)
分治字节串转 limb 数组引擎
const mp_base_t lmmp_bases_table[255]
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define DEC_BASE
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_B_DECL
#define BALLOC_TYPE(n, type)
#define TEMP_B_FREE

引用了 BALLOC_TYPE, DEC_BASE, FROM_STR_BASEPOW_THRESHOLD, LIMB_BITS, lmmp_bases_table, lmmp_copy, lmmp_dec_pow_table_(), lmmp_from_decimal_(), lmmp_from_str_basecase_(), lmmp_from_str_divide_(), lmmp_from_str_len_(), lmmp_param_assert, lmmp_shr_(), mp_basepow_t::np, mp_basepow_t::p, TEMP_B_DECL, TEMP_B_FREE , 以及 tp.

被这些函数引用 check_decimal_one(), lmmp_from_decimal_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_from_decimal_len_()

mp_size_t lmmp_from_decimal_len_ ( const char * src,
mp_size_t len )

计算十进制字符串转limb数组所需的 limb 缓冲区长度

Copyright (C) 2026 HJimmyK (Jericho Knox)

参数
src输入字符串指针
len字符串长度
警告
len>=0
注解
将会忽略字符串末尾的'0'(值前导零),
  1. if (src!=NULL) 零值返回0,其余情况返回的长度可能会多分配一个 limb 空间
  2. if (src==NULL) 返回len个字符的最大可能 limb 长度(最坏情况)
返回
所需的 limb 缓冲区长度上界

计算十进制字符串转limb数组所需的 limb 缓冲区长度

This file is part of LMMP.

LMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.

SPDX-License-Identifier: LGPL-3.0-or-later

在文件 from_decimal.c 第 31 行定义.

31 {
32 if (src) {
33 // 忽略末尾的 '0'(值前导零,字符串低位在前)
34 do {
35 if (len == 0)
36 return 0;
37 } while (src[--len] == '0');
38 ++len;
39 }
40 return lmmp_mulh_(len, lmmp_bases_table[DEC_BASE - 2].lg_base) + 1;
41}
#define lmmp_mulh_

引用了 DEC_BASE, lmmp_bases_table, lmmp_from_decimal_len_() , 以及 lmmp_mulh_.

被这些函数引用 check_decimal_one(), lmmp_from_decimal_len_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_from_hex_()

mp_size_t lmmp_from_hex_ ( mp_ptr dst,
const char * src,
mp_size_t len )

十六进制字符串转limb数组 [src,len,16] to [dst,return value,B]

参数
dst结果输出指针
src字符串源指针
len字符串长度
警告
len>=0, dst!=NULL, src!=NULL, src[i] in {'0'-'9','a'-'f','A'-'F'}
注解
低位digit(nibble)在数组前端;将忽略末尾的'0';将会忽略大小写,'a'等同于'A'
返回
转换后的结果的 limb 长度(零值返回0)

在文件 from_hex.c 第 35 行定义.

35 {
36 lmmp_param_assert(dst != NULL && src != NULL);
37 do {
38 if (len == 0)
39 return 0;
40 } while (src[--len] == '0');
41 ++len;
42
43 mp_size_t nfull = len >> 4;
44 const char* sp = src;
45 for (mp_size_t i = 0; i < nfull; ++i, sp += 16) {
46 mp_limb_t l = 0;
47 // 组内自高向低读,使得 sp[j] 落在第 j 个 nibble
48 for (int j = 15; j >= 0; --j)
49 l = (l << 4) | lmmp_hex_val_tab[(mp_byte_t)sp[j]];
50 dst[i] = l;
51 }
52
53 int r = (int)(len & 15);
54 if (r) {
55 mp_limb_t l = 0;
56 for (int j = r - 1; j >= 0; --j)
57 l = (l << 4) | lmmp_hex_val_tab[(mp_byte_t)sp[j]];
58 dst[nfull] = l;
59 }
60
61 return nfull + (r != 0);
62}
static const mp_byte_t lmmp_hex_val_tab[256]
Copyright (C) 2026 HJimmyK (Jericho Knox)

引用了 lmmp_from_hex_(), lmmp_hex_val_tab , 以及 lmmp_param_assert.

被这些函数引用 check_hex_one(), lmmp_from_hex_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_from_hex_len_()

mp_size_t lmmp_from_hex_len_ ( const char * src,
mp_size_t len )

计算十六进制字符串转limb数组所需的 limb 缓冲区长度

Copyright (C) 2026 HJimmyK (Jericho Knox)

参数
src输入字符串指针
len字符串长度
警告
len>=0
注解
将会忽略字符串末尾的'0'(值前导零),
  1. if (src!=NULL) 返回精确的 limb 长度(零值返回0)
  2. if (src==NULL) 返回len个字符的最大可能 limb 长度(最坏情况)
返回
所需的 limb 缓冲区长度

计算十六进制字符串转limb数组所需的 limb 缓冲区长度

This file is part of LMMP.

LMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.

SPDX-License-Identifier: LGPL-3.0-or-later

在文件 from_hex.c 第 28 行定义.

28 {
29 if (src) {
30 // 忽略末尾的 '0'(值前导零,字符串低位在前)
31 do {
32 if (len == 0)
33 return 0;
34 } while (src[--len] == '0');
35 ++len;
36 }
37 return (len + 15) >> 4;
38}

引用了 lmmp_from_hex_len_().

被这些函数引用 check_hex_one(), lmmp_from_hex_len_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_from_str_()

mp_size_t lmmp_from_str_ ( mp_ptr dst,
const mp_byte_t * src,
mp_size_t len,
int base )

字节数组转limb数组操作 [src,len,base] to [dst,return value,B]

参数
dst结果输出指针
src字节数组源指针
len字节数组长度
base字节数组的进制基数
警告
len>=0, 2<=base<=256, dst!=NULL, src!=NULL
返回
转换后的结果的 limb 长度

在文件 from_str.c 第 146 行定义.

146 {
147 lmmp_param_assert(base >= 2 && base <= 256);
148 lmmp_param_assert(dst != NULL && src != NULL);
149 do {
150 if (len == 0)
151 return 0;
152 } while (src[--len] == 0);
153 ++len;
154
155 mp_size_t limbs;
156 if (LMMP_POW2_Q(base)) {
157 mp_limb_t curlimb = 0;
158 const mp_byte_t* srcend = src + len;
159 int bitspd = lmmp_bases_table[base - 2].large_base;
160 int bitpos = 0;
161 limbs = 0;
162
163 do {
164 mp_limb_t curdigit = *src;
165 curlimb |= curdigit << bitpos;
166 bitpos += bitspd;
167 if (bitpos >= LIMB_BITS) {
168 dst[limbs] = curlimb;
169 ++limbs;
170 bitpos -= LIMB_BITS;
171 curlimb = curdigit >> (bitspd - bitpos);
172 }
173 } while (++src != srcend);
174 if (curlimb) {
175 dst[limbs] = curlimb;
176 ++limbs;
177 }
178 } else if (lmmp_from_str_len_(0, len, base) < FROM_STR_BASEPOW_THRESHOLD) {
179 limbs = lmmp_from_str_basecase_(dst, src, len, base, 0);
180 } else {
181 TEMP_DECL;
182 mp_basepow_t powers[LIMB_BITS];
183 mp_limb_t lbase = lmmp_bases_table[base - 2].large_base;
184 mp_size_t digitspl = lmmp_bases_table[base - 2].digits_in_limb;
185 mp_size_t bexp, lexp = (len - 1) / digitspl + 1;
186 mp_size_t tzbit = lmmp_tailing_zeros_(lbase);
187 // need 1 extra limb to store result
188 mp_size_t alloc_size = lmmp_from_str_len_(0, len, base) + 1;
189 mp_limb_t cy;
190 mp_ptr tp;
191
192 int cpow = lmmp_limb_bits_(lexp - 1);
193
194 for (int i = cpow; i > 0; --i) {
195 // we will calculate lbase^bexp
196 bexp = ((lexp - 1) >> i) + 1;
197 // we will calculate lbase^(bexp-1) first, and trim it s. t.
198 // it contains at most 2 tailing 0 limb, then multiply it by lbase,
199 // so we need npow limbs to store lbase^bexp
200 mp_size_t npow = lmmp_from_str_len_(0, (bexp - 1) * digitspl + 1, base) + 1;
201
202 if (tzbit) {
203 mp_size_t tzlimb = tzbit * (bexp - 1) / LIMB_BITS;
204 if (tzlimb >= 2)
205 npow -= tzlimb - 2;
206 }
207
208 // space needed for a trimmed npow-limb lbase^bexp
209 alloc_size += npow;
210 }
211
212 tp = BALLOC_TYPE(alloc_size, mp_limb_t);
213
214 for (int i = 0; i < 2; ++i) {
215 tp[0] = lbase;
216 powers[i].p = tp;
217 powers[i].np = 1;
218 tp += i + 1;
219 powers[i].zeros = 0;
220 powers[i].digits = digitspl * (i + 1);
221 powers[i].base = base;
222 }
223
224 mp_ptr p = powers[1].p;
225 mp_size_t zeros = 0, np = 1;
226 for (int i = 2; i < cpow; ++i) {
227 lmmp_sqr_(tp, p, np);
228 np *= 2;
229 np -= tp[np - 1] == 0;
230 bexp = (lexp - 1) >> (cpow - i);
231 if (bexp & 1) {
232 cy = lmmp_mul_1_(tp, tp, np, lbase);
233 tp[np] = cy;
234 np += cy != 0;
235 }
236 zeros *= 2;
237 while (tp[0] == 0) {
238 // at most 2 tailing 0 limb here
239 ++zeros;
240 ++tp;
241 --np;
242 }
243 p = tp;
244 powers[i].p = p;
245 powers[i].np = np;
246 powers[i].zeros = zeros;
247 powers[i].digits = digitspl * (bexp + 1);
248 powers[i].base = base;
249 tp += np + 1;
250 }
251
252 for (int i = 1; i < cpow; ++i) {
253 p = powers[i].p;
254 np = powers[i].np;
255 cy = lmmp_mul_1_(p, p, np, lbase);
256 p[np] = cy;
257 np += cy != 0;
258 if (p[0] == 0) {
259 ++powers[i].zeros;
260 ++p;
261 --np;
262 }
263
264 powers[i].p = p;
265 powers[i].np = np;
266 }
267
268 limbs = lmmp_from_str_divide_(tp, src, len, powers + cpow - 1, dst, 0);
269 lmmp_copy(dst, tp, limbs);
270
271 TEMP_FREE;
272 }
273 return limbs;
274}
#define lmmp_limb_bits_
#define lmmp_sqr_
#define lmmp_tailing_zeros_
#define LMMP_POW2_Q(n)
检查n是否为2的幂次方
定义 lmmp.h:467
mp_limb_t lmmp_mul_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
乘以单limb操作 [dst,na] = [numa,na] * x
定义 mul_1.c:27
mp_size_t digits
mp_limb_t large_base
mp_size_t zeros

引用了 BALLOC_TYPE, mp_basepow_t::base, mp_basepow_t::digits, mp_base_t::digits_in_limb, FROM_STR_BASEPOW_THRESHOLD, mp_base_t::large_base, LIMB_BITS, lmmp_bases_table, lmmp_copy, lmmp_from_str_(), lmmp_from_str_basecase_(), lmmp_from_str_divide_(), lmmp_from_str_len_(), lmmp_limb_bits_, lmmp_mul_1_(), lmmp_param_assert, LMMP_POW2_Q, lmmp_sqr_, lmmp_tailing_zeros_, mp_basepow_t::np, mp_basepow_t::p, TEMP_DECL, TEMP_FREE, tp , 以及 mp_basepow_t::zeros.

被这些函数引用 check_decimal_one(), lmmp_from_str_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_from_str_len_()

mp_size_t lmmp_from_str_len_ ( const mp_byte_t * src,
mp_size_t len,
int base )

计算字节数组转limb数组所需的 limb 缓冲区长度

Copyright (C) 2026 HJimmyK (Jericho Knox)

参数
src输入字节数组指针
len字节数组长度
base字节数组的基数(2~256)
返回
存储该字节数组数值所需的 limb 缓冲区长度
警告
len>=0, 2<=base<=256
注解
将会忽略前导零,
  1. if (src!=NULL) 返回的长度可能会多分配一个 limb 空间
  2. if (src==NULL) 返回len位base进制数的最大可能 limb 长度(最坏情况)

计算字节数组转limb数组所需的 limb 缓冲区长度

This file is part of LMMP.

LMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.

SPDX-License-Identifier: LGPL-3.0-or-later

在文件 from_str.c 第 32 行定义.

32 {
33 lmmp_param_assert(base >= 2 && base <= 256);
34 if (src) {
35 do {
36 if (len == 0)
37 return 1;
38 } while (src[--len] == 0);
39 ++len;
40 }
41 return lmmp_mulh_(len, lmmp_bases_table[base - 2].lg_base) + 1;
42}

引用了 lmmp_bases_table, lmmp_from_str_len_(), lmmp_mulh_ , 以及 lmmp_param_assert.

被这些函数引用 check_decimal_one(), lmmp_from_decimal_(), lmmp_from_str_(), lmmp_from_str_divide_(), lmmp_from_str_len_(), lmmp_to_str_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_inv_()

void lmmp_inv_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na,
mp_size_t nf )

求逆操作 [dst,na+nf+1] = (B^(2*(na+nf)) - 1) / ([numa,na]*B^nf) + [0|-1]

参数
dst逆元结果输出指针
numa源操作数指针
na操作数的 limb 长度
nf精度因子
警告
na>0, numa[na-1]!=0, eqsep(dst,numa), dst!=NULL, numa!=NULL

在文件 inv.c 第 173 行定义.

173 {
174 lmmp_param_assert(na > 0);
175 lmmp_param_assert(dst != NULL && numa != NULL);
176 lmmp_param_assert(numa[na - 1] != 0);
177 mp_limb_t high = numa[na - 1];
178 int nsh = lmmp_leading_zeros_(high);
179 TEMP_DECL;
180 if (dst == numa || nsh || nf) {
181 nf += nsh != 0;
182 mp_ptr restrict numa2 = TALLOC_TYPE(na + nf, mp_limb_t);
183 lmmp_zero(numa2, nf);
184 lmmp_shl_(numa2 + nf, numa, na, nsh); // nsh=0 时函数内即整段拷贝
185 numa = numa2;
186 }
187 lmmp_invappr_(dst, numa, na + nf);
188 if (nsh)
189 lmmp_shr_c_(dst, dst, na + nf, LIMB_BITS - nsh, (mp_limb_t)1 << nsh);
190 else
191 dst[na + nf] = 1;
192 TEMP_FREE;
193}
#define lmmp_zero(dst, n)
定义 lmmp.h:476
void lmmp_invappr_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
近似逆元计算 (invappr)
mp_limb_t lmmp_shr_c_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shr, mp_limb_t c)
带进位的右移操作 [dst,na] = [numa,na]>>shr,dst的高shr位填充c的高shr位
定义 shr.c:39

引用了 LIMB_BITS, lmmp_inv_(), lmmp_invappr_(), lmmp_leading_zeros_, lmmp_param_assert, lmmp_shl_(), lmmp_shr_c_(), lmmp_zero, restrict, TALLOC_TYPE, TEMP_DECL , 以及 TEMP_FREE.

被这些函数引用 lmmp_inv_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_inv_1_()

mp_limb_t lmmp_inv_1_ ( mp_limb_t x)

1阶逆元计算 (inv1)

参数
x输入的64位无符号整数,最高位为1(MSB(x)=1)
返回
计算结果:(B^2-1)/x - B
警告
MSB(x)=1, 即x>=2^63

在文件 inv.c 第 124 行定义.

124 {
125 mp_limb_t r, m;
126 {
127 mp_limb_t p, ql;
128 unsigned ul, uh, qh;
129
130 ul = x & LLIMB_MASK;
131 uh = x >> (LIMB_BITS / 2);
132 qh = (x ^ LIMB_MAX) / uh;
133
134 r = ((~x - (mp_limb_t)qh * uh) << (LIMB_BITS / 2)) | LLIMB_MASK;
135 p = (mp_limb_t)qh * ul;
136 if (r < p) {
137 qh--;
138 r += x;
139 if (r >= x)
140 if (r < p) {
141 qh--;
142 r += x;
143 }
144 }
145 r -= p;
146 p = (r >> (LIMB_BITS / 2)) * qh + r;
147 ql = (p >> (LIMB_BITS / 2)) + 1;
148 r = (r << (LIMB_BITS / 2)) + LLIMB_MASK - ql * x;
149 if (r >= (LIMB_MAX & (p << (LIMB_BITS / 2)))) {
150 ql--;
151 r += x;
152 }
153 m = ((mp_limb_t)qh << (LIMB_BITS / 2)) + ql;
154 if (r >= x) {
155 m++;
156 r -= x;
157 }
158 }
159 return m;
160}
#define LLIMB_MASK
定义 lmmp.h:108

引用了 LIMB_BITS, LIMB_MAX, LLIMB_MASK , 以及 lmmp_inv_1_().

被这些函数引用 bench_inv_1(), lmmp_div_1_(), lmmp_div_1_s_(), lmmp_inv_1_(), lmmp_inv_basecase_(), lmmp_mod_1_(), lmmp_mulmod_ulong_(), lmmp_sqrlo_dc_(), mont_R2(), mont_R2(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), trialdiv_init_chunk_() , 以及 trialdiv_init_inv_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_inv_2_1_()

mp_limb_t lmmp_inv_2_1_ ( mp_limb_t xh,
mp_limb_t xl )

2-1阶逆元计算 (inv21)

Copyright (C) 2026 HJimmyK (Jericho Knox)

参数
xh输入数的高64位部分
xl输入数的低64位部分
返回
计算结果:(B^3-1)/(xh*B+xl) - B
警告
MSB(xh)=1, 即xh>=2^63

2-1阶逆元计算 (inv21)

This file is part of LMMP.

LMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.

SPDX-License-Identifier: LGPL-3.0-or-later

在文件 inv.c 第 27 行定义.

27 {
28 mp_limb_t r, m;
29 {
30 mp_limb_t p, ql;
31 unsigned ul, uh, qh;
32
33 /* For notation, let b denote the half-limb base, so that B = b^2.
34 Split u1 = b uh + ul. */
35 ul = xh & LLIMB_MASK;
36 uh = xh >> (LIMB_BITS / 2);
37
38 /* Approximation of the high half of quotient. Differs from the 2/1
39 inverse of the half limb uh, since we have already subtracted
40 u0. */
41 qh = (xh ^ LIMB_MAX) / uh;
42
43 /* Adjust to get a half-limb 3/2 inverse, i.e., we want
44
45 qh' = floor( (b^3 - 1) / u) - b = floor ((b^3 - b u - 1) / u
46 = floor( (b (~u) + b-1) / u),
47
48 and the remainder
49
50 r = b (~u) + b-1 - qh (b uh + ul)
51 = b (~u - qh uh) + b-1 - qh ul
52
53 Subtraction of qh ul may underflow, which implies adjustments.
54 But by normalization, 2 u >= B > qh ul, so we need to adjust by
55 at most 2.
56 */
57
58 r = ((~xh - (mp_limb_t)qh * uh) << (LIMB_BITS / 2)) | LLIMB_MASK;
59
60 p = (mp_limb_t)qh * ul;
61 /* Adjustment steps taken from udiv_qrnnd_c */
62 if (r < p) {
63 qh--;
64 r += xh;
65 if (r >= xh) /* i.e. we didn't get carry when adding to r */
66 if (r < p) {
67 qh--;
68 r += xh;
69 }
70 }
71 r -= p;
72
73 /* Low half of the quotient is
74
75 ql = floor ( (b r + b-1) / u1).
76
77 This is a 3/2 division (on half-limbs), for which qh is a
78 suitable inverse. */
79
80 p = (r >> (LIMB_BITS / 2)) * qh + r;
81 /* Unlike full-limb 3/2, we can add 1 without overflow. For this to
82 work, it is essential that ql is a full mp_limb_t. */
83 ql = (p >> (LIMB_BITS / 2)) + 1;
84
85 /* By the 3/2 trick, we don't need the high half limb. */
86 r = (r << (LIMB_BITS / 2)) + LLIMB_MASK - ql * xh;
87
88 if (r >= (LIMB_MAX & (p << (LIMB_BITS / 2)))) {
89 ql--;
90 r += xh;
91 }
92 m = ((mp_limb_t)qh << (LIMB_BITS / 2)) + ql;
93 if (r >= xh) {
94 m++;
95 r -= xh;
96 }
97 }
98
99 /* Now m is the 2/1 inverse of u1. If u0 > 0, adjust it to become a
100 3/2 inverse. */
101 if (xl > 0) {
102 mp_limb_t th, tl;
103 r = ~r;
104 r += xl;
105 if (r < xl) {
106 m--;
107 if (r >= xh) {
108 m--;
109 r -= xh;
110 }
111 r -= xh;
112 }
113 _umul64to128_(xl, m, &tl, &th);
114 r += th;
115 if (r < th) {
116 m--;
117 m -= ((r > xh) | ((r == xh) & (tl > xl)));
118 }
119 }
120
121 return m;
122}
static void _umul64to128_(uint64_t a, uint64_t b, uint64_t *low, uint64_t *high)

引用了 _umul64to128_(), LIMB_BITS, LIMB_MAX, LLIMB_MASK , 以及 lmmp_inv_2_1_().

被这些函数引用 bench_div_3_2(), bench_inv_2_1(), ipn_sdiv_init_(), lmmp_bninv_appr_newton_(), lmmp_div_(), lmmp_div_2_(), lmmp_div_2_s_(), lmmp_div_s_(), lmmp_inv_2_1_(), lmmp_inv_basecase_(), lmmp_mod_2_(), lmmp_sqrlo_dc_(), TEST_CASE(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_inv_basecase_()

void lmmp_inv_basecase_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na )

近似逆元计算

参数
dst输出结果缓冲区,长度为na
numa输入操作数,长度为na
na输入操作数的 limb 长度
警告
na>0, MSB(numa)=1, sep(dst,numa), dst!=NULL, numa!=NULL
返回
无返回值,结果存储在dst中,[dst,na]=(B^(2*na)-1)/[numa,na] - B^na

引用了 LMMP_API , 以及 lmmp_inv_basecase_().

被这些函数引用 lmmp_inv_basecase_(), lmmp_inv_basecase_(), lmmp_invappr_() , 以及 lmmp_invappr_newton_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_inv_prediv_()

void lmmp_inv_prediv_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na,
mp_size_t ni )

除法前的逆元预计算,[dst,ni] = invappr( (ni+1 MSLs of numa) + 1 ) / B

Copyright (C) 2026 HJimmyK (Jericho Knox)

参数
dst输出预计算逆元的缓冲区,长度为ni
numa输入操作数,长度为na
na输入操作数的 limb 长度
ni预计算逆元的目标尺寸
警告
na>=ni>0, MSB(numa)=1, eqsep(dst,numa), dst!=NULL, numa!=NULL
注解
if (ni=na) [dst,na] = (B^(2*na)-1) / [numa,na] - B^na

除法前的逆元预计算,[dst,ni] = invappr( (ni+1 MSLs of numa) + 1 ) / B

This file is part of LMMP.

LMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.

SPDX-License-Identifier: LGPL-3.0-or-later

在文件 div_mulinv.c 第 30 行定义.

30 {
31 lmmp_param_assert(na >= ni);
32 lmmp_param_assert(ni > 0);
33 lmmp_param_assert(dst != NULL && numa != NULL);
34 lmmp_param_assert(numa[na - 1] >= LIMB_B_2);
36 mp_limb_t cy;
38
39 if (na == ni) {
40 lmmp_copy(tp + 1, numa, ni);
41 tp[0] = 1;
42 cy = 0;
43 } else {
44 cy = lmmp_add_1_(tp, numa + na - (ni + 1), ni + 1, 1);
45 }
46 if (cy)
47 lmmp_zero(dst, ni);
48 else {
49 mp_ptr restrict invappr = TALLOC_TYPE(ni + 1, mp_limb_t);
50 lmmp_invappr_(invappr, tp, ni + 1);
51 lmmp_copy(dst, invappr + 1, ni);
52 }
54}
#define LIMB_B_2
static mp_limb_t lmmp_add_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
加单精度数静态内联函数 [dst,na]=[numa,na]+x

引用了 LIMB_B_2, lmmp_add_1_(), lmmp_copy, lmmp_inv_prediv_(), lmmp_invappr_(), lmmp_param_assert, lmmp_zero, restrict, TALLOC_TYPE, TEMP_DECL, TEMP_FREE , 以及 tp.

被这些函数引用 dec_pow_extend_(), lmmp_div_(), lmmp_div_s_(), lmmp_inv_prediv_() , 以及 lmmp_to_str_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_invappr_()

void lmmp_invappr_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na )

近似逆元计算 (invappr)

参数
dst输出结果缓冲区,长度为na
numa输入操作数,长度为na
na输入操作数的 limb 长度
警告
na>0, MSB(numa)=1, sep(dst,numa), dst!=NULL, numa!=NULL
返回
无返回值,结果存储在dst中,[dst,na] = (B^(2*na)-1)/[numa,na] - B^na + [0|-1]

引用了 LMMP_API , 以及 lmmp_invappr_().

被这些函数引用 lmmp_inv_(), lmmp_inv_prediv_(), lmmp_invappr_() , 以及 lmmp_invappr_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_invappr_newton_()

void lmmp_invappr_newton_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na )

近似逆元计算(牛顿迭代法)

参数
dst输出结果缓冲区,长度为na
numa输入操作数,长度为na
na输入操作数的 limb 长度
警告
na>4, MSB(numa)=1, sep(dst,numa), dst!=NULL, numa!=NULL
返回
无返回值,结果存储在dst中,[dst,na]=(B^(2*na)-1)/[numa,na]-B^na+[0|-1]

引用了 LMMP_API , 以及 lmmp_invappr_newton_().

被这些函数引用 lmmp_invappr_(), lmmp_invappr_newton_() , 以及 lmmp_invappr_newton_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_leading_zeros_()

int lmmp_leading_zeros_ ( mp_limb_t x)

计算一个单精度数(limb)中前导零的个数

参数
x输入的64位无符号整数
返回
前导零的位数(范围:0~64)

在文件 tiny.c 第 56 行定义.

56 {
57 if (x == 0) return 64;
58#ifdef __GNUC__
59 return __builtin_clzll(x);
60#else
61 int n = 0;
62 if (x <= 0x00000000FFFFFFFF) { n += 32; x <<= 32; }
63 if (x <= 0x0000FFFFFFFFFFFF) { n += 16; x <<= 16; }
64 if (x <= 0x00FFFFFFFFFFFFFF) { n += 8; x <<= 8; }
65 if (x <= 0x0FFFFFFFFFFFFFFF) { n += 4; x <<= 4; }
66 if (x <= 0x3FFFFFFFFFFFFFFF) { n += 2; x <<= 2; }
67 if (x <= 0x7FFFFFFFFFFFFFFF) { n += 1; x <<= 1; }
68 return n;
69#endif
70}

引用了 lmmp_leading_zeros_ , 以及 n.

◆ lmmp_limb_bits_()

int lmmp_limb_bits_ ( mp_limb_t x)

计算满足 2^k > x 的最小自然数k

Copyright (C) 2026 HJimmyK (Jericho Knox)

参数
x输入的64位无符号整数
返回
满足条件的最小自然数k

计算满足 2^k > x 的最小自然数k

This file is part of LMMP.

LMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.

SPDX-License-Identifier: LGPL-3.0-or-later

在文件 tiny.c 第 28 行定义.

28 {
29 int k = 0;
30 while (x) {
31 x >>= 1;
32 k++;
33 }
34 return k;
35}

引用了 k , 以及 lmmp_limb_bits_.

◆ lmmp_limb_popcnt_()

int lmmp_limb_popcnt_ ( mp_limb_t x)

计算一个64位无符号整数中1的个数

参数
x输入的64位无符号整数
返回
1的个数

在文件 tiny.c 第 37 行定义.

37 {
38#if defined(__GNUC__) || defined(__clang__)
39 mp_limb_t count;
40#if defined(LMMP_ASM_X64)
41 __asm__ volatile("popcnt %1, %0" : "=r"(count) : "r"(x) : "cc");
42#else
43 count = __builtin_popcountll(x);
44#endif
45 return count;
46#else
47 int k = 0;
48 while (x) {
49 k += x & 1;
50 x >>= 1;
51 }
52 return k;
53#endif
54}

引用了 k , 以及 lmmp_limb_popcnt_.

◆ lmmp_mersenne_next_size_()

mp_size_t lmmp_mersenne_next_size_ ( mp_size_t n)

计算满足 >=n 的最小分治梅森乘法可行尺寸

参数
n输入的目标尺寸
返回
满足条件的分治梅森乘法最小尺寸
注解
梅森缓存和fft算法应该改用 lmmp_fft_next_size_

在文件 mul_mersenne.c 第 408 行定义.

408 {
409 if (n < MUL_MERSENNE_DC_THRESHOLD) return n;
410 if (n < 4 * (MUL_MERSENNE_DC_THRESHOLD - 1) + 1) return (n + 1) & ~(mp_size_t)1;
411 if (n < 8 * (MUL_MERSENNE_DC_THRESHOLD - 1) + 1) return (n + 3) & ~(mp_size_t)3;
412 mp_size_t nh = (n + 1) >> 1;
413 if (nh < MUL_FFT_MODF_THRESHOLD) return (n + 7) & ~(mp_size_t)7;
414 return 2 * lmmp_fft_next_size_(nh);
415}
#define MUL_MERSENNE_DC_THRESHOLD
#define MUL_FFT_MODF_THRESHOLD
mp_size_t lmmp_fft_next_size_(mp_size_t n)
计算满足 >=n 的最小费马/梅森乘法可行尺寸

引用了 lmmp_fft_next_size_(), lmmp_mersenne_next_size_(), MUL_FFT_MODF_THRESHOLD, MUL_MERSENNE_DC_THRESHOLD , 以及 n.

被这些函数引用 bench_mul_mersenne_dc(), binvert_mulhi_(), lmmp_binvert_unbalance_(), lmmp_div_mulinv_(), lmmp_divexact_mu_run_(), lmmp_hgcd_apply_mod_(), lmmp_invappr_newton_(), lmmp_invcbrt_newton_(), lmmp_invsqrt_newton_(), lmmp_mersenne_next_size_(), lmmp_mont_init_(), lmmp_mont_need_(), lmmp_mul_toom62_unbalance_(), lmmp_redc_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_mod_1_()

mp_limb_t lmmp_mod_1_ ( mp_srcptr numa,
mp_size_t na,
mp_limb_t x )

单精度数取余

参数
numa输入被除数,长度为na
na被除数的 limb 长度
x除数(单个 limb )
返回
除法余数(单个 limb )
警告
na>0, x!=0, numa!=NULL

在文件 div.c 第 38 行定义.

38 {
39 mp_limb_t ah, al;
40 if (na == 1) {
41 ah = numa[0];
42 return ah % x;
43 }
44 mp_limb_t t = numa[na - 2], q, r;
45 const int shift = lmmp_leading_zeros_(x);
46 if (shift > 0) {
47 const int rshift = LIMB_BITS - shift;
48 ah = numa[na - 1] >> rshift;
49 t = numa[na - 2];
50 al = (numa[na - 1] << shift) | (t >> rshift);
51 x <<= shift;
52 const mp_limb_t inv = lmmp_inv_1_(x);
53 _udiv_qrnnd_preinv(q, r, ah, al, x, inv);
54 na -= 2;
55 while (na-- > 0) {
56 ah = r;
57 al = t << shift;
58 t = numa[na];
59 al |= t >> rshift;
60 _udiv_qrnnd_preinv(q, r, ah, al, x, inv);
61 }
62 ah = r;
63 al = t << shift;
64 _udiv_qrnnd_preinv(q, r, ah, al, x, inv);
65 (void)q;
66 return r >> shift;
67 } else {
68 ah = 0;
69 t = numa[na - 2];
70 al = numa[na - 1];
71 const mp_limb_t inv = lmmp_inv_1_(x);
72 q = al / x;
73 r = al % x;
74 na -= 2;
75 while (na-- > 0) {
76 ah = r;
77 al = t;
78 t = numa[na];
79 _udiv_qrnnd_preinv(q, r, ah, al, x, inv);
80 }
81 ah = r;
82 al = t;
83 _udiv_qrnnd_preinv(q, r, ah, al, x, inv);
84 (void)q;
85 return r;
86 }
87}

引用了 _udiv_qrnnd_preinv, LIMB_BITS, lmmp_inv_1_(), lmmp_leading_zeros_, lmmp_mod_1_() , 以及 t.

被这些函数引用 bench_mod_1(), ipn_jacobi_D_(), lmmp_div_1_(), lmmp_div_3_2_(), lmmp_gcd_1_(), lmmp_gcdext_1_(), lmmp_mod_1_(), lmmp_modinv_(), mod32(), mulmod64(), powmod_ref_u64(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_mod_2_()

void lmmp_mod_2_ ( mp_srcptr numa,
mp_size_t na,
mp_ptr numb )

双精度数取余 (除数为2个limb)

参数
numa输入被除数(长度na)
na被除数的 limb 长度
numb输入除数(长度2)[numb,2]=[numa,na] mod [numb,2]
警告
na>=2, numb[1]!=0, numb!=NULL, numa!=NULL

在文件 div.c 第 215 行定义.

215 {
216 mp_limb_t q, r1, r0, a2, a1, a0, b1, b0;
217 b1 = numb[1];
218 b0 = numb[0];
219 if (na == 2) {
220 int shift = lmmp_leading_zeros_(b1);
221 if (shift > 0) {
222 const int rshift = LIMB_BITS - shift;
223 b1 = (b1 << shift) | (b0 >> rshift);
224 b0 <<= shift;
225 a2 = numa[1] >> rshift;
226 a1 = (numa[1] << shift) | (numa[0] >> rshift);
227 a0 = (numa[0] << shift);
229 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
230 numb[0] = (r0 >> shift) | (r1 << rshift);
231 numb[1] = r1 >> shift;
232 return;
233 } else {
234 u128 a = _u128load(numa), b = _u128load(numb);
235 if (a < b) {
236 _u128store(numb, a);
237 return;
238 } else {
239 _u128store(numb, a - b);
240 return;
241 }
242 }
243 } else {
244 int shift = lmmp_leading_zeros_(b1);
245 if (shift > 0) {
246 const int rshift = LIMB_BITS - shift;
247 b1 = (b1 << shift) | (b0 >> rshift);
248 b0 <<= shift;
249 const mp_limb_t inv = lmmp_inv_2_1_(b1, b0);
250 a2 = numa[na - 1] >> rshift;
251 a1 = (numa[na - 1] << shift) | (numa[na - 2] >> rshift);
252 a0 = (numa[na - 2] << shift) | (numa[na - 3] >> rshift);
253 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
254 na -= 2;
255 while (na-- > 1) {
256 a2 = r1;
257 a1 = r0;
258 a0 = (numa[na] << shift) | (numa[na - 1] >> rshift);
259 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
260 }
261
262 a2 = r1;
263 a1 = r0;
264 a0 = (numa[na] << shift);
265 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
266 numb[0] = (r0 >> shift) | (r1 << rshift);
267 numb[1] = r1 >> shift;
268 return;
269 } else {
270 const mp_limb_t inv = lmmp_inv_2_1_(b1, b0);
271 a2 = 0;
272 a1 = numa[na - 1];
273 a0 = numa[na - 2];
274 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
275 na -= 2;
276 while (na-- > 1) {
277 a2 = r1;
278 a1 = r0;
279 a0 = numa[na];
280 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
281 }
282 a2 = r1;
283 a1 = r0;
284 a0 = numa[na];
285 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
286 numb[0] = r0;
287 numb[1] = r1;
288 return;
289 }
290 }
291}

引用了 _udiv_qr_3by2, a0, a1, a2, b0, b1, LIMB_BITS, lmmp_inv_2_1_(), lmmp_leading_zeros_, lmmp_mod_2_(), numb, r0 , 以及 r1.

被这些函数引用 bench_mod_2(), lmmp_div_3_2_(), lmmp_gcd_2_(), lmmp_gcdext_2_(), lmmp_mod_2_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_mod_preinv_1_()

mp_limb_t lmmp_mod_preinv_1_ ( mp_srcptr numa,
mp_size_t na,
mp_limb_t x,
mp_limb_t inv,
mp_limb_t k )

单精度数取余(预备逆元版) [numa,na] mod x,同 lmmp_mod_1_

参数
numa输入被除数,长度为na
na被除数的 limb 长度
x除数(单个 limb )
inv预计算逆元 lmmp_inv_1_(x<<k)
k预计算移位量 lmmp_leading_zeros_(x)
返回
除法余数(单个 limb )
警告
na>0, x!=0, numa!=NULL, k=lmmp_leading_zeros_(x), inv=lmmp_inv_1_(x<<k)
注解
同一 x 反复取模时(如固定素数逐候选判整除),预处理一次、多次调用本函数, 省去每次调用的 clz/归一化/lmmp_inv_1_ 开销

在文件 div.c 第 89 行定义.

89 {
90 mp_limb_t ah, al;
91 if (na == 1) {
92 ah = numa[0];
93 return ah % x;
94 }
95 mp_limb_t t = numa[na - 2], q, r;
96 if (k > 0) {
97 const mp_limb_t rshift = LIMB_BITS - k;
98 ah = numa[na - 1] >> rshift;
99 t = numa[na - 2];
100 al = (numa[na - 1] << k) | (t >> rshift);
101 x <<= k;
102 _udiv_qrnnd_preinv(q, r, ah, al, x, inv);
103 na -= 2;
104 while (na-- > 0) {
105 ah = r;
106 al = t << k;
107 t = numa[na];
108 al |= t >> rshift;
109 _udiv_qrnnd_preinv(q, r, ah, al, x, inv);
110 }
111 ah = r;
112 al = t << k;
113 _udiv_qrnnd_preinv(q, r, ah, al, x, inv);
114 (void)q;
115 return r >> k;
116 } else {
117 ah = 0;
118 t = numa[na - 2];
119 al = numa[na - 1];
120 q = al / x;
121 r = al % x;
122 na -= 2;
123 while (na-- > 0) {
124 ah = r;
125 al = t;
126 t = numa[na];
127 _udiv_qrnnd_preinv(q, r, ah, al, x, inv);
128 }
129 ah = r;
130 al = t;
131 _udiv_qrnnd_preinv(q, r, ah, al, x, inv);
132 (void)q;
133 return r;
134 }
135}

引用了 _udiv_qrnnd_preinv, k, LIMB_BITS, lmmp_mod_preinv_1_() , 以及 t.

被这些函数引用 lmmp_div_3_2_(), lmmp_mod_preinv_1_(), TEST_CASE(), TEST_CASE() , 以及 trialdiv_leg_preinv_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_mul_()

void lmmp_mul_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na,
mp_srcptr numb,
mp_size_t nb )

不等长乘法操作 [dst,na+nb] = [numa,na] * [numb,nb]

参数
dst乘积结果输出指针(需要 na+nb 的 limb 长度)
numa第一个乘数指针(较长的操作数)
na第一个操作数的 limb 长度
numb第二个乘数指针(较短的操作数)
nb第二个操作数的 limb 长度
警告
0<nb<=na, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
返回
无返回值,结果存储在dst中

引用了 LMMP_API, lmmp_mul_() , 以及 numb.

被这些函数引用 bench_mul(), cbrt_floor_ok(), check_addmul_2(), check_vs_dispatch(), coeff_bound_l(), lmmp_binvert_n_dc_(), lmmp_bninv_appr_newton_(), lmmp_cbrt_(), lmmp_cbrt_divide_(), lmmp_cbrt_newton_(), lmmp_div_(), lmmp_div_divide_n_(), lmmp_div_mulinv_(), lmmp_div_s_(), lmmp_divexact_divide_(), lmmp_divexact_mu_run_(), lmmp_elem_mul_ulong_(), lmmp_fibonacci_(), lmmp_from_str_divide_(), lmmp_gcd_mul_(), lmmp_gcdext_2_(), lmmp_gcdext_derive_(), lmmp_gcdext_lehmer_(), lmmp_huff_tree_mul_(), lmmp_invappr_newton_(), lmmp_invcbrt_newton_(), lmmp_invsqrt_newton_(), lmmp_mul_(), lmmp_mul_(), lmmp_mul_fft_unbalance_(), lmmp_mul_toom22_(), lmmp_mul_toom32_(), lmmp_mul_toom33_(), lmmp_mul_toom42_(), lmmp_mul_toom42_cache_(), lmmp_mul_toom42_cache_init_(), lmmp_mul_toom42_unbalance_(), lmmp_mul_toom43_(), lmmp_mul_toom44_(), lmmp_mul_toom52_(), lmmp_mul_toom53_(), lmmp_mul_toom62_(), lmmp_mul_toom62_cache_(), lmmp_mul_toom62_cache_init_(), lmmp_mul_toom62_unbalance_(), lmmp_mul_toom6h_(), lmmp_mul_toom8h_(), lmmp_nthroot_(), lmmp_pow_win2_(), lmmp_powmod_(), lmmp_powmod_odd_mont_(), lmmp_sqrt_newton_(), make_divexact_ctx(), mat22_mul_(), mat22_mulsg_(), mersenne_oracle(), mrs_mul_core_(), mul_sorted(), mulmod_limbs(), nthroot_pow_trunc_(), pow_nPr_(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), test_fn_heap_balance_full_cycle(), test_fn_lifecycle_idempotent(), verify_div_relation() , 以及 verify_inverse().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_mul_1_()

mp_limb_t lmmp_mul_1_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na,
mp_limb_t x )

乘以单limb操作 [dst,na] = [numa,na] * x

Copyright (C) 2026 HJimmyK (Jericho Knox)

参数
dst结果输出指针
numa被乘数指针
na操作数的 limb 长度
x单个limb乘数
警告
na>0, eqsep(dst,numa), dst!=NULL, numa!=NULL
返回
运算后的进位limb值

乘以单limb操作 [dst,na] = [numa,na] * x

This file is part of LMMP.

LMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.

SPDX-License-Identifier: LGPL-3.0-or-later

在文件 mul_1.c 第 27 行定义.

27 {
28 /*
29 链式 (a_{k-1} >> 64) 进位提取使 GCC/Clang 均生成 add/adc 融合序列,
30 单 limb 链长约 2c,展开宽度 W 可将链摊薄为 (W+1)/W c:
31 - clang 会把 4 路链式源码回卷成 2 路(实测慢约 7~12%),6 路是其
32 能保持的最小宽度;
33 - gcc 恰好相反,4 路最优、6 路慢约 4%。
34 故按编译器选择展开宽度。
35 */
36 mp_limb_t cl = 0;
37 mp_size_t i = 0;
38
39#if defined(__clang__)
40 for (; i + 6 <= na; i += 6) {
41 __uint128_t a0 = (__uint128_t)numa[i + 0] * x + cl;
42 __uint128_t a1 = (__uint128_t)numa[i + 1] * x + (mp_limb_t)(a0 >> 64);
43 __uint128_t a2 = (__uint128_t)numa[i + 2] * x + (mp_limb_t)(a1 >> 64);
44 __uint128_t a3 = (__uint128_t)numa[i + 3] * x + (mp_limb_t)(a2 >> 64);
45 __uint128_t a4 = (__uint128_t)numa[i + 4] * x + (mp_limb_t)(a3 >> 64);
46 __uint128_t a5 = (__uint128_t)numa[i + 5] * x + (mp_limb_t)(a4 >> 64);
47 dst[i + 0] = (mp_limb_t)a0;
48 dst[i + 1] = (mp_limb_t)a1;
49 dst[i + 2] = (mp_limb_t)a2;
50 dst[i + 3] = (mp_limb_t)a3;
51 dst[i + 4] = (mp_limb_t)a4;
52 dst[i + 5] = (mp_limb_t)a5;
53 cl = (mp_limb_t)(a5 >> 64);
54 }
55#else
56 for (; i + 4 <= na; i += 4) {
57 __uint128_t a0 = (__uint128_t)numa[i + 0] * x + cl;
58 __uint128_t a1 = (__uint128_t)numa[i + 1] * x + (mp_limb_t)(a0 >> 64);
59 __uint128_t a2 = (__uint128_t)numa[i + 2] * x + (mp_limb_t)(a1 >> 64);
60 __uint128_t a3 = (__uint128_t)numa[i + 3] * x + (mp_limb_t)(a2 >> 64);
61 dst[i + 0] = (mp_limb_t)a0;
62 dst[i + 1] = (mp_limb_t)a1;
63 dst[i + 2] = (mp_limb_t)a2;
64 dst[i + 3] = (mp_limb_t)a3;
65 cl = (mp_limb_t)(a3 >> 64);
66 }
67#endif
68 for (; i < na; i++) {
69 __uint128_t a = (__uint128_t)numa[i] * x + cl;
70 dst[i] = (mp_limb_t)a;
71 cl = (mp_limb_t)(a >> 64);
72 }
73 return cl;
74}
#define a4
#define a5

引用了 a0, a1, a2, a3, a4, a5 , 以及 lmmp_mul_1_().

被这些函数引用 bench_mul_1(), cbrt_floor_ok(), chain_mul_small(), check_pow1_laws(), gcdext_pick_s_(), ipn_sdiv_mul1_(), lc1_(), lmmp_3pow_1_(), lmmp_cbrt_(), lmmp_cbrt_6_fast_(), lmmp_cbrt_divide_(), lmmp_cbrt_knorm_(), lmmp_elem_mul_ulong_(), lmmp_from_str_(), lmmp_from_str_basecase_(), lmmp_gcdext_1_(), lmmp_gcdext_hgcd_(), lmmp_gcdext_lehmer_(), lmmp_hgcd_matrix_mul_u_(), lmmp_hgcd_step_(), lmmp_lehmer_mul_(), lmmp_mul_1_(), lmmp_mullo_basecase_(), lmmp_nthroot_(), lmmp_pow_(), lmmp_shlnot_(), lmmp_sqrlo_basecase_(), lmmp_to_str_(), lmmp_u32_pow_1_(), lmmp_u64_pow_1_(), lmmp_u8_pow_1_(), ref_value(), run_gcdext_pair(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE() , 以及 verify_inverse().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_mul_basecase_()

void lmmp_mul_basecase_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na,
mp_srcptr numb,
mp_size_t nb )

基础乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]

参数
dst输出结果缓冲区,长度至少为 na+nb
numa第一个输入操作数,长度为 na
na第一个操作数的 limb 长度
numb第二个输入操作数,长度为 nb
nb第二个操作数的 limb 长度
警告
0<nb<=na, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
返回
无返回值,结果存储在dst中

引用了 LMMP_API, lmmp_mul_basecase_() , 以及 numb.

被这些函数引用 __lmmp_mul_hard_n_(), bench_mul_basecase(), check_mul_n(), check_vs_oracle(), lmmp_cbrt_(), lmmp_cbrt_6_fast_(), lmmp_cbrt_divide_(), lmmp_cube_6_(), lmmp_cube_6_(), lmmp_mul_(), lmmp_mul_basecase_(), lmmp_mul_basecase_(), lmmp_u16_pow_1_(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_mul_fermat_()

void lmmp_mul_fermat_ ( mp_ptr dst,
mp_size_t rn,
mp_srcptr numa,
mp_size_t na,
mp_srcptr numb,
mp_size_t nb )

费马数模乘法 [dst,rn+1]=[numa,na]*[numb,nb] mod B^rn+1

参数
dst输出结果缓冲区,长度至少为 rn+1
rn模运算的阶数参数,须为 FFT 可行尺寸(lmmp_fft_next_size_(rn)==rn); rn = lmmp_fft_next_size_((na + nb + 1) >> 1) 为可容纳乘积的推荐最小值
numa第一个输入操作数,长度为 na
na第一个操作数的 limb 长度
numb第二个输入操作数,长度为 nb
nb第二个操作数的 limb 长度
警告
eqsep(dst,[numa|numb]), 0<=[numa,na]<2*B^rn, 0<=[numb,nb]<2*B^rn, lmmp_fft_next_size_(rn)==rn, dst!=NULL, numa!=NULL, numb!=NULL
注解
如果[numa,na]==[numb,nb],请使用lmmp_sqr_fermat_函数,此函数不会检查操作数是否一致并跳转到lmmp_sqr_fermat_函数
返回
无返回值,结果存储在dst中

在文件 mul_fft.c 第 112 行定义.

112 {
113 const int nsqr = 1;
114 mp_size_t N = rn * LIMB_BITS; // 结果总比特数
116 mp_size_t K = ((mp_size_t)1) << k; // FFT块数(2^k)
117 lmmp_debug_assert(!(N & (K - 1)));
118 mp_size_t M = N >> k; // 每个块的比特数
119 mp_size_t n = 2 * M + k + 2; // 扩展系数长度
120
121 n = (n + LIMB_BITS - 1) & (-LIMB_BITS);
122 n = (((n - 1) >> k) + 1) << k;
123
124 // 初始化内存栈
125 fft_memstack msr;
126 msr.maxdepth = -1;
127 msr.tempdepth = -1;
128 msr.lenw = n / LIMB_BITS;
129 mp_size_t nlen = msr.lenw + 1;
130
131 msr.temp_coef = (mp_ptr)lmmp_fft_memstack_(&msr, (((nlen + 1) << (k + nsqr)) + nlen) * LIMB_BYTES);
132
133 mp_ptr *pfca = (mp_ptr*)(msr.temp_coef + nlen), *pfcb = pfca;
134 mp_size_t narest = na * LIMB_BITS, nbrest = nb * LIMB_BITS;
135
136 for (mp_size_t i = 0; i < K; ++i) {
137 mp_size_t coeflen;
138 pfca[i] = (mp_ptr)(pfca + K) + i * nlen;
139 if (narest > 0) {
140 coeflen = M + (i == K - 1);
141 coeflen = LMMP_MIN(narest, coeflen);
142 narest -= coeflen;
143 lmmp_fft_extract_coef_(pfca[i], numa, M * i, coeflen, msr.lenw);
144 if (i > 0)
145 lmmp_fft_shl_coef_(&msr, pfca + i, i * n >> k);
146 } else {
147 lmmp_zero(pfca[i], nlen);
148 }
149 }
150 lmmp_fft_(&msr, pfca, k, n >> (k - 1));
151
152 pfcb += (nlen + 1) << k;
153 for (mp_size_t i = 0; i < K; ++i) {
154 mp_size_t coeflen;
155 pfcb[i] = (mp_ptr)(pfcb + K) + i * nlen;
156 if (nbrest > 0) {
157 coeflen = M + (i == K - 1);
158 coeflen = LMMP_MIN(nbrest, coeflen);
159 nbrest -= coeflen;
160 lmmp_fft_extract_coef_(pfcb[i], numb, M * i, coeflen, msr.lenw);
161 if (i > 0)
162 lmmp_fft_shl_coef_(&msr, pfcb + i, i * n >> k);
163 } else {
164 lmmp_zero(pfcb[i], nlen);
165 }
166 }
167 lmmp_fft_(&msr, pfcb, k, n >> (k - 1));
168
169 lmmp_mul_fermat_recurse_(&msr, pfca, pfcb, K);
170
171 lmmp_ifft_(&msr, pfca, k, n >> (k - 1));
172
173 lmmp_mul_fermat_recombine_(&msr, dst, pfca, K, k, n, M, rn);
174
175 // 处理模 B^rn+1 的溢出
176 if (dst[rn] && !lmmp_zero_q_(dst, rn)) {
177 dst[rn] = 0;
178 lmmp_dec(dst);
179 }
180
181 lmmp_fft_memstack_(&msr, 0);
182}
void lmmp_fft_shl_coef_(fft_memstack *ms, mp_ptr *coef, mp_size_t shl)
对模 2^n+1 的系数执行左移操作
void lmmp_mul_fermat_recombine_(fft_memstack *ms, mp_ptr dst, mp_ptr *pfca, mp_size_t K, mp_size_t k, mp_size_t n, mp_size_t M, mp_size_t rn)
费马变换 模 B^n+1 乘法的结果合并
void * lmmp_fft_memstack_(fft_memstack *ms, mp_size_t size)
FFT内存栈的分配/释放接口
void lmmp_ifft_(fft_memstack *ms, mp_ptr *coef, mp_size_t k, mp_size_t w)
void lmmp_fft_extract_coef_(mp_ptr dst, mp_srcptr numa, mp_size_t bitoffset, mp_size_t bits, mp_size_t lenw)
[dst,lenw+1] = [(bit*)numa+bitoffset, bits]
void lmmp_fft_(fft_memstack *ms, mp_ptr *coef, mp_size_t k, mp_size_t w)
mp_ssize_t maxdepth
mp_ssize_t tempdepth
mp_size_t lenw
#define LIMB_BYTES
定义 lmmp.h:103
#define LMMP_MIN(l, o)
返回两个数中的较小值
定义 lmmp.h:450
int lmmp_zero_q_(mp_srcptr p, mp_size_t n)
判零函数
定义 cmp.c:55
static void lmmp_mul_fermat_recurse_(fft_memstack *ms, mp_ptr *pc1, mp_ptr *pc2, mp_size_t K0)
Copyright (C) 2026 HJimmyK (Jericho Knox)

引用了 k, fft_memstack::lenw, LIMB_BITS, LIMB_BYTES, lmmp_debug_assert, lmmp_dec, lmmp_fft_(), lmmp_fft_best_k_(), lmmp_fft_extract_coef_(), lmmp_fft_memstack_(), lmmp_fft_shl_coef_(), lmmp_ifft_(), LMMP_MIN, lmmp_mul_fermat_(), lmmp_mul_fermat_recombine_(), lmmp_mul_fermat_recurse_(), lmmp_zero, lmmp_zero_q_(), fft_memstack::maxdepth, n, numb, fft_memstack::temp_coef , 以及 fft_memstack::tempdepth.

被这些函数引用 lmmp_mul_fermat_(), lmmp_mul_fft_mods_(), lmmp_mul_toom62_unbalance_(), lmmp_mullo_fft_() , 以及 mrs_mul_core_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_mul_fft_()

void lmmp_mul_fft_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na,
mp_srcptr numb,
mp_size_t nb )

FFT乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]

参数
dst输出结果缓冲区,长度至少为 na+nb
numa第一个输入操作数,长度为 na
na第一个操作数的 limb 长度
numb第二个输入操作数,长度为 nb
nb第二个操作数的 limb 长度
警告
???<=nb<=na, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
返回
无返回值,结果存储在dst中

在文件 mul_fft.c 第 679 行定义.

679 {
680 lmmp_param_assert(na > 0 && nb > 0);
681 lmmp_param_assert(na >= nb);
682 lmmp_param_assert(dst != NULL && numa != NULL && numb != NULL);
683 mp_size_t hn = lmmp_fft_next_size_((na + nb + 1) >> 1);
684 lmmp_assert(na + nb > hn);
685 mp_ptr tp = ALLOC_TYPE(hn + 1, mp_limb_t);
686
687 lmmp_mul_fft_mods_(dst, tp, hn, numa, na, numb, nb);
688 lmmp_mul_fft_crt_(dst, tp, hn, na + nb);
689 lmmp_free(tp);
690}
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
#define lmmp_assert(x)
定义 lmmp.h:481
static void lmmp_mul_fft_mods_(mp_ptr dst, mp_ptr tp, mp_size_t hn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
FFT 双域模乘计算:分别求梅森域与费马域残差(lmmp_mul_fft_crt_ 的前半)
static void lmmp_mul_fft_crt_(mp_ptr dst, mp_ptr tp, mp_size_t hn, mp_size_t nab)
FFT 双域 CRT 重构尾部(lmmp_mul_fft_mods_ 的后半):两域残差 → 精确积
#define ALLOC_TYPE(n, type)

引用了 ALLOC_TYPE, lmmp_assert, lmmp_fft_next_size_(), lmmp_free(), lmmp_mul_fft_(), lmmp_mul_fft_crt_(), lmmp_mul_fft_mods_(), lmmp_param_assert, numb , 以及 tp.

被这些函数引用 __lmmp_mul_n_(), bench_mul_fft(), lmmp_mul_(), lmmp_mul_fft_(), lmmp_mul_n_() , 以及 lmmp_mul_toom62_unbalance_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_mul_fft_unbalance_()

void lmmp_mul_fft_unbalance_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na,
mp_srcptr numb,
mp_size_t nb )

FFT不平衡乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]

参数
dst输出结果缓冲区,长度至少为 na+nb
hnFFT模域参数
numa第一个输入操作数,长度为 na
na第一个操作数的 limb 长度
numb第二个输入操作数,长度为 nb
nb第二个操作数的 limb 长度
警告
???<=nb<=na, na>=3*nb, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
返回
无返回值,结果存储在dst中

引用了 LMMP_API, lmmp_mul_fft_unbalance_() , 以及 numb.

被这些函数引用 lmmp_mul_(), lmmp_mul_fft_unbalance_() , 以及 lmmp_mul_fft_unbalance_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_mul_mersenne_()

void lmmp_mul_mersenne_ ( mp_ptr dst,
mp_size_t rn,
mp_srcptr numa,
mp_size_t na,
mp_srcptr numb,
mp_size_t nb )

梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1

参数
dst输出结果缓冲区,长度至少为 rn
rn模运算的阶数参数,任意正尺寸均可(未对齐 fft 可行尺寸时回落 dc); rn = lmmp_fft_next_size_((na + nb + 1) >> 1) 为进入 fft 档的推荐最小值
numa第一个输入操作数,长度为 na
na第一个操作数的 limb 长度
numb第二个输入操作数,长度为 nb
nb第二个操作数的 limb 长度
警告
sep(dst,[numa|numb]), 0<=[numa,na]<B^rn, 0<=[numb,nb]<B^rn, dst!=NULL, numa!=NULL, numb!=NULL
注解
na/nb 大小序不限(内部按交换律规范化为 nb<=na);rn 对齐粒度不限 (未达 fft 可行尺寸时即使超过阈值也回落 dc); 如果[numa,na]==[numb,nb],请使用lmmp_sqr_mersenne_函数,此函数不会检查操作数是否一致并跳转到lmmp_sqr_mersenne_函数;
返回
无返回值,结果存储在dst中

在文件 mul_mersenne.c 第 417 行定义.

417 {
418 if (na < nb) {
419 mp_srcptr tp = numa;
420 mp_size_t tn = na;
421 numa = numb;
422 na = nb;
423 numb = tp;
424 nb = tn;
425 }
426 /* fft 分支要求 rn 为 fft 可行尺寸(缓存结构与 mersenne_next_size 的粗粒度
427 输出均不保证),未对齐时回落 dc(任意 rn 合法) */
428 if (rn >= MUL_MERSENNE_FFT_THRESHOLD && lmmp_fft_next_size_(rn) == rn)
429 lmmp_mul_mersenne_fft_(dst, rn, numa, na, numb, nb);
430 else
431 lmmp_mul_mersenne_dc_(dst, rn, numa, na, numb, nb);
432}
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
#define MUL_MERSENNE_FFT_THRESHOLD
void lmmp_mul_mersenne_dc_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
分治梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1
void lmmp_mul_mersenne_fft_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
FFT 梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1

引用了 lmmp_fft_next_size_(), lmmp_mul_mersenne_(), lmmp_mul_mersenne_dc_(), lmmp_mul_mersenne_fft_(), MUL_MERSENNE_FFT_THRESHOLD, numb , 以及 tp.

被这些函数引用 binvert_mulhi_(), lmmp_binvert_unbalance_(), lmmp_div_mulinv_(), lmmp_divexact_mu_run_(), lmmp_hgcd_apply_mod_(), lmmp_invappr_newton_(), lmmp_invcbrt_newton_(), lmmp_invsqrt_newton_(), lmmp_mont_redc_(), lmmp_mul_mersenne_(), lmmp_mul_toom62_unbalance_(), lmmp_redc_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_mul_mersenne_dc_()

void lmmp_mul_mersenne_dc_ ( mp_ptr dst,
mp_size_t rn,
mp_srcptr numa,
mp_size_t na,
mp_srcptr numb,
mp_size_t nb )

分治梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1

参数
dst输出结果缓冲区,长度至少为 rn
rn模运算的阶数参数
numa第一个输入操作数,长度为 na
na第一个操作数的 limb 长度
numb第二个输入操作数,长度为 nb
nb第二个操作数的 limb 长度
警告
sep(dst,[numa|numb]), 0<=[numa,na]<B^rn, 0<=[numb,nb]<B^rn, na+nb>rn/2, dst!=NULL, numa!=NULL, numb!=NULL
注解
如果[numa,na]==[numb,nb],请使用lmmp_sqr_mersenne_dc_函数,此函数不会检查操作数是否一致并跳转到lmmp_sqr_mersenne_dc_函数
返回
无返回值,结果存储在dst中

在文件 mul_mersenne.c 第 385 行定义.

385 {
386 lmmp_param_assert(na > 0 && nb > 0);
387 lmmp_param_assert(nb <= na && na <= rn);
388 lmmp_param_assert(dst != NULL && numa != NULL && numb != NULL);
389 lmmp_debug_assert(na + nb > rn / 2);
390
391 mp_ptr tp = ALLOC_TYPE(2 * rn + 4, mp_limb_t);
392 mrs_mul_core_(dst, rn, numa, na, numb, nb, tp);
393 mrs_norm_zero_(dst, rn);
394 lmmp_free(tp);
395}
static void mrs_norm_zero_(mp_ptr p, mp_size_t n)
零类归一化:[p,n] == B^n-1 时清零(内部半归一化 → 库规范 0 表示)
static void mrs_mul_core_(mp_ptr rp, mp_size_t rn, mp_srcptr ap, mp_size_t an, mp_srcptr bp, mp_size_t bn, mp_ptr tp)
分治梅森乘法核心(半归一化内部约定:零类 = B^n-1)

引用了 ALLOC_TYPE, lmmp_debug_assert, lmmp_free(), lmmp_mul_mersenne_dc_(), lmmp_param_assert, mrs_mul_core_(), mrs_norm_zero_(), numb , 以及 tp.

被这些函数引用 bench_mul_mersenne_dc(), lmmp_mul_mersenne_(), lmmp_mul_mersenne_dc_(), lmmp_mul_toom62_unbalance_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_mul_mersenne_fft_()

void lmmp_mul_mersenne_fft_ ( mp_ptr dst,
mp_size_t rn,
mp_srcptr numa,
mp_size_t na,
mp_srcptr numb,
mp_size_t nb )

FFT 梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1

参数
dst输出结果缓冲区,长度至少为 rn
rn模运算的阶数参数,须为 FFT 可行尺寸(lmmp_fft_next_size_(rn)==rn); rn = lmmp_fft_next_size_((na + nb + 1) >> 1) 为可容纳乘积的推荐最小值
numa第一个输入操作数,长度为 na
na第一个操作数的 limb 长度
numb第二个输入操作数,长度为 nb
nb第二个操作数的 limb 长度
警告
eqsep(dst,[numa|numb]), 0<=[numa,na]<B^rn, 0<=[numb,nb]<B^rn, lmmp_fft_next_size_(rn)==rn, dst!=NULL, numa!=NULL, numb!=NULL
注解
如果[numa,na]==[numb,nb],请使用lmmp_sqr_mersenne_fft_函数,此函数不会检查操作数是否一致并跳转到lmmp_sqr_mersenne_fft_函数
返回
无返回值,结果存储在dst中

在文件 mul_fft.c 第 184 行定义.

184 {
185 const int nsqr = 1;
186 mp_size_t N = rn * LIMB_BITS; // 结果总比特数
187 mp_size_t k = lmmp_fft_best_k_(rn); // 最优FFT层数
188 mp_size_t K = ((mp_size_t)1) << k; // FFT块数(2^k)
189 // 断言:N必须是K的整数倍
190 lmmp_debug_assert(!(N & (K - 1)));
191 mp_size_t M = N >> k; // 每个块的比特数
192 mp_size_t n = 2 * M + k; // 扩展系数长度(梅森数比费马数少2)
193
194 // 规整n:必须是LIMB_BITS和K/2的整数倍
195 n = (n + LIMB_BITS - 1) & (-LIMB_BITS);
196 n = (((n - 1) >> (k - 1)) + 1) << (k - 1);
197
198 // 初始化内存栈
199 fft_memstack msr;
200 msr.maxdepth = -1;
201 msr.tempdepth = -1;
202 msr.lenw = n / LIMB_BITS;
203 mp_size_t nlen = msr.lenw + 1;
204
205 msr.temp_coef = (mp_ptr)lmmp_fft_memstack_(&msr, (((nlen + 1) << (k + nsqr)) + nlen) * LIMB_BYTES);
206
207 mp_ptr *pfca = (mp_ptr*)(msr.temp_coef + nlen), *pfcb = pfca;
208 mp_size_t narest = na * LIMB_BITS, nbrest = nb * LIMB_BITS;
209
210 for (mp_size_t i = 0; i < K; ++i) {
211 mp_size_t coeflen;
212 pfca[i] = (mp_ptr)(pfca + K) + i * nlen;
213 if (narest > 0) {
214 coeflen = LMMP_MIN(narest, M);
215 narest -= coeflen;
216 lmmp_fft_extract_coef_(pfca[i], numa, M * i, coeflen, msr.lenw);
217 } else {
218 lmmp_zero(pfca[i], nlen);
219 }
220 }
221 lmmp_fft_(&msr, pfca, k, n >> (k - 1));
222
223 pfcb += (nlen + 1) << k;
224 for (mp_size_t i = 0; i < K; ++i) {
225 mp_size_t coeflen;
226 pfcb[i] = (mp_ptr)(pfcb + K) + i * nlen;
227 if (nbrest > 0) {
228 coeflen = LMMP_MIN(nbrest, M);
229 nbrest -= coeflen;
230 lmmp_fft_extract_coef_(pfcb[i], numb, M * i, coeflen, msr.lenw);
231 } else {
232 lmmp_zero(pfcb[i], nlen);
233 }
234 }
235 lmmp_fft_(&msr, pfcb, k, n >> (k - 1));
236
237 lmmp_mul_fermat_recurse_(&msr, pfca, pfcb, K);
238
239 lmmp_ifft_(&msr, pfca, k, n >> (k - 1));
240
241 mp_size_t rhead = 0, maxc = 0;
242 for (mp_size_t i = 0; i < K; ++i) {
243 lmmp_fft_shr_coef_(&msr, pfca + i, k);
244 mp_ptr nums = pfca[i];
245
246 if (nums[nlen - 1]) {
247 lmmp_dec(nums);
248 lmmp_debug_assert(nums[nlen - 1] == 1);
249 nums[nlen - 1] = 0;
250 }
251
252 mp_size_t roffset = i * M;
253 mp_size_t shl = roffset & (LIMB_BITS - 1);
254 roffset /= LIMB_BITS;
255
256 if (shl)
257 lmmp_shl_(nums, nums, nlen, shl);
258
259 if (i == 0) {
260 // 首个系数未移位,超出 [dst,rn] 的扩展 limb 已清零。
261 rhead = LMMP_MIN(nlen, rn);
262 lmmp_copy(dst, nums, rhead);
263 } else if (roffset + nlen <= rn) {
264 lmmp_add_(dst + roffset, nums, nlen, dst + roffset, rhead - roffset);
265 rhead = roffset + nlen;
266 } else {
267 maxc += lmmp_add_(dst + roffset, nums, rn - roffset, dst + roffset, rhead - roffset);
268 maxc += lmmp_add_(dst, dst, rn, nums + rn - roffset, nlen + roffset - rn);
269 rhead = rn;
270 }
271 }
272
273 if (!lmmp_add_1_(dst, dst, rn, 1 + maxc))
274 lmmp_dec(dst);
275
276 lmmp_fft_memstack_(&msr, 0);
277}
void lmmp_fft_shr_coef_(fft_memstack *ms, mp_ptr *coef, mp_size_t shr)
对模 2^n+1 的系数执行右移操作 右移shr位 = 左移(2n - shr)位(mod 2^n+1的循环特性)
static mp_limb_t lmmp_add_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
加法静态内联函数 [dst,na]=[numa,na]+[numb,nb]

引用了 k, fft_memstack::lenw, LIMB_BITS, LIMB_BYTES, lmmp_add_(), lmmp_add_1_(), lmmp_copy, lmmp_debug_assert, lmmp_dec, lmmp_fft_(), lmmp_fft_best_k_(), lmmp_fft_extract_coef_(), lmmp_fft_memstack_(), lmmp_fft_shr_coef_(), lmmp_ifft_(), LMMP_MIN, lmmp_mul_fermat_recurse_(), lmmp_mul_mersenne_fft_(), lmmp_shl_(), lmmp_zero, fft_memstack::maxdepth, n, numb, fft_memstack::temp_coef , 以及 fft_memstack::tempdepth.

被这些函数引用 bench_mul_mersenne_fft(), lmmp_mul_fft_mods_(), lmmp_mul_mersenne_(), lmmp_mul_mersenne_fft_(), lmmp_mul_toom62_unbalance_(), lmmp_mullo_fft_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_mul_n_()

void lmmp_mul_n_ ( mp_ptr dst,
mp_srcptr numa,
mp_srcptr numb,
mp_size_t n )

等长乘法操作 [dst,2*n] = [numa,n] * [numb,n]

参数
dst乘积结果输出指针(需要 2*n 的 limb 长度)
numa第一个乘数指针
numb第二个乘数指针
nlimb长度
警告
n>0, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
返回
无返回值,结果存储在dst中

引用了 LMMP_API, lmmp_mul_n_, n , 以及 numb.

◆ lmmp_mul_toom22_()

void lmmp_mul_toom22_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na,
mp_srcptr numb,
mp_size_t nb )

Toom-22乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]

参数
dst输出结果缓冲区,长度至少为 na+nb
numa第一个输入操作数,长度为 na
na第一个操作数的 limb 长度
numb第二个输入操作数,长度为 nb
nb第二个操作数的 limb 长度
警告
1/2<nb/na<=1, nb>=5, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
返回
无返回值,结果存储在dst中

引用了 LMMP_API, lmmp_mul_toom22_() , 以及 numb.

被这些函数引用 __lmmp_mul_n_(), bench_mul_toom22(), lmmp_mul_(), lmmp_mul_n_(), lmmp_mul_toom22_() , 以及 lmmp_mul_toom22_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_mul_toom32_()

void lmmp_mul_toom32_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na,
mp_srcptr numb,
mp_size_t nb )

Toom-32乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]

参数
dst输出结果缓冲区,长度至少为 na+nb
numa第一个输入操作数,长度为 na
na第一个操作数的 limb 长度
numb第二个输入操作数,长度为 nb
nb第二个操作数的 limb 长度
警告
1/3<nb/na<1, nb>=12, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
返回
无返回值,结果存储在dst中

引用了 LMMP_API, lmmp_mul_toom32_() , 以及 numb.

被这些函数引用 lmmp_mul_(), lmmp_mul_toom32_() , 以及 lmmp_mul_toom32_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_mul_toom33_()

void lmmp_mul_toom33_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na,
mp_srcptr numb,
mp_size_t nb )

Toom-33乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]

参数
dst输出结果缓冲区,长度至少为 na+nb
numa第一个输入操作数,长度为 na
na第一个操作数的 limb 长度
numb第二个输入操作数,长度为 nb
nb第二个操作数的 limb 长度
警告
2/3<nb/na<=1, nb>=26, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
返回
无返回值,结果存储在dst中

引用了 LMMP_API, lmmp_mul_toom33_() , 以及 numb.

被这些函数引用 __lmmp_mul_n_(), bench_mul_toom33(), lmmp_mul_(), lmmp_mul_n_(), lmmp_mul_toom33_() , 以及 lmmp_mul_toom33_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_mul_toom42_()

void lmmp_mul_toom42_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na,
mp_srcptr numb,
mp_size_t nb )

Toom-42乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]

参数
dst输出结果缓冲区,长度至少为 na+nb
numa第一个输入操作数,长度为 na
na第一个操作数的 limb 长度
numb第二个输入操作数,长度为 nb
nb第二个操作数的 limb 长度
警告
1/4<nb/na<2/3, nb>=20, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
返回
无返回值,结果存储在dst中

引用了 LMMP_API, lmmp_mul_toom42_() , 以及 numb.

被这些函数引用 lmmp_mul_(), lmmp_mul_toom42_() , 以及 lmmp_mul_toom42_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_mul_toom42_unbalance_()

void lmmp_mul_toom42_unbalance_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na,
mp_srcptr numb,
mp_size_t nb )

Toom-42不平衡乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]

参数
dst输出结果缓冲区,长度至少为 na+nb
numa第一个输入操作数,长度为 na
na第一个操作数的 limb 长度
numb第二个输入操作数,长度为 nb
nb第二个操作数的 limb 长度
警告
na>=3*nb, nb>=20, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
返回
无返回值,结果存储在dst中

引用了 LMMP_API, lmmp_mul_toom42_unbalance_() , 以及 numb.

被这些函数引用 lmmp_mul_(), lmmp_mul_toom42_unbalance_() , 以及 lmmp_mul_toom42_unbalance_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_mul_toom43_()

void lmmp_mul_toom43_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na,
mp_srcptr numb,
mp_size_t nb )

Toom-43乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]

参数
dst输出结果缓冲区,长度至少为 na+nb
numa第一个输入操作数,长度为 na
na第一个操作数的 limb 长度
numb第二个输入操作数,长度为 nb
nb第二个操作数的 limb 长度
警告
1/2<nb/na<1, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
返回
无返回值,结果存储在dst中

引用了 LMMP_API, lmmp_mul_toom43_() , 以及 numb.

被这些函数引用 lmmp_mul_(), lmmp_mul_toom43_() , 以及 lmmp_mul_toom43_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_mul_toom44_()

void lmmp_mul_toom44_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na,
mp_srcptr numb,
mp_size_t nb )

Toom-44乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]

参数
dst输出结果缓冲区,长度至少为 na+nb
numa第一个输入操作数,长度为 na
na第一个操作数的 limb 长度
numb第二个输入操作数,长度为 nb
nb第二个操作数的 limb 长度
警告
3/4<nb/na<=1, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
返回
无返回值,结果存储在dst中

引用了 LMMP_API, lmmp_mul_toom44_() , 以及 numb.

被这些函数引用 __lmmp_mul_n_(), bench_mul_toom44(), lmmp_mul_(), lmmp_mul_n_(), lmmp_mul_toom44_() , 以及 lmmp_mul_toom44_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_mul_toom52_()

void lmmp_mul_toom52_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na,
mp_srcptr numb,
mp_size_t nb )

Toom-52乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]

参数
dst输出结果缓冲区,长度至少为 na+nb
numa第一个输入操作数,长度为 na
na第一个操作数的 limb 长度
numb第二个输入操作数,长度为 nb
nb第二个操作数的 limb 长度
警告
1/5<nb/na<1/2, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
返回
无返回值,结果存储在dst中

引用了 LMMP_API, lmmp_mul_toom52_() , 以及 numb.

被这些函数引用 lmmp_mul_(), lmmp_mul_toom52_() , 以及 lmmp_mul_toom52_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_mul_toom53_()

void lmmp_mul_toom53_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na,
mp_srcptr numb,
mp_size_t nb )

Toom-53乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]

参数
dst输出结果缓冲区,长度至少为 na+nb
numa第一个输入操作数,长度为 na
na第一个操作数的 limb 长度
numb第二个输入操作数,长度为 nb
nb第二个操作数的 limb 长度
警告
2/5<nb/na<3/4, na>4*n, nb>2*n while n=max(ceil(na/5),ceil(nb/3)) sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
返回
无返回值,结果存储在dst中

引用了 LMMP_API, lmmp_mul_toom53_() , 以及 numb.

被这些函数引用 lmmp_mul_(), lmmp_mul_toom53_(), lmmp_mul_toom53_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_mul_toom62_()

void lmmp_mul_toom62_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na,
mp_srcptr numb,
mp_size_t nb )

Toom-62乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]

参数
dst输出结果缓冲区,长度至少为 na+nb
numa第一个输入操作数,长度为 na
na第一个操作数的 limb 长度
numb第二个输入操作数,长度为 nb
nb第二个操作数的 limb 长度
警告
1/6<nb/na<2/5, na>5*n, nb>n while n=max(ceil(na/6),ceil(nb/2)) sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
返回
无返回值,结果存储在dst中

引用了 LMMP_API, lmmp_mul_toom62_() , 以及 numb.

被这些函数引用 lmmp_mul_(), lmmp_mul_toom62_(), lmmp_mul_toom62_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_mul_toom62_unbalance_()

void lmmp_mul_toom62_unbalance_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na,
mp_srcptr numb,
mp_size_t nb )

Toom-62不平衡乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]

参数
dst输出结果缓冲区,长度至少为 na+nb
numa第一个输入操作数,长度为 na
na第一个操作数的 limb 长度
numb第二个输入操作数,长度为 nb
nb第二个操作数的 limb 长度
警告
na>=5*nb, nb>=??, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
返回
无返回值,结果存储在dst中

引用了 LMMP_API, lmmp_fft_next_size_(), lmmp_mersenne_next_size_(), lmmp_mul_fermat_(), lmmp_mul_fft_(), lmmp_mul_mersenne_(), lmmp_mul_mersenne_dc_(), lmmp_mul_mersenne_fft_(), lmmp_mul_toom62_unbalance_(), lmmp_sqr_fermat_(), lmmp_sqr_fft_(), lmmp_sqr_mersenne_(), lmmp_sqr_mersenne_dc_(), lmmp_sqr_mersenne_fft_(), n , 以及 numb.

被这些函数引用 lmmp_mul_(), lmmp_mul_toom62_unbalance_() , 以及 lmmp_mul_toom62_unbalance_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_mul_toom6h_()

void lmmp_mul_toom6h_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na,
mp_srcptr numb,
mp_size_t nb )

Toom-6.5乘法运算 [dst,na+nb] = [numa,na] * [numb,nb] (非对称切分+条件inf点,原生支持不平衡;评估点 inf,±4,±2,±1,±1/2,±1/4,0)

参数
dst输出结果缓冲区,长度至少为 na+nb
numa第一个输入操作数,长度为 na
na第一个操作数的 limb 长度
numb第二个输入操作数,长度为 nb
nb第二个操作数的 limb 长度
警告
46<=nb<=na, na*6<nb*17, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
返回
无返回值,结果存储在dst中

引用了 LMMP_API, lmmp_mul_toom6h_() , 以及 numb.

被这些函数引用 __lmmp_mul_n_(), lmmp_mul_(), lmmp_mul_n_(), lmmp_mul_toom6h_(), lmmp_mul_toom6h_(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_mul_toom8h_()

void lmmp_mul_toom8h_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na,
mp_srcptr numb,
mp_size_t nb )

Toom-8.5乘法运算 [dst,na+nb] = [numa,na] * [numb,nb] (非对称切分+条件inf点,原生支持不平衡;评估点 inf,±8,±4,±2,±1,±1/2,±1/4,±1/8,0)

参数
dst输出结果缓冲区,长度至少为 na+nb
numa第一个输入操作数,长度为 na
na第一个操作数的 limb 长度
numb第二个输入操作数,长度为 nb
nb第二个操作数的 limb 长度
警告
86<=nb<=na, na<=4*nb, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
返回
无返回值,结果存储在dst中

引用了 LMMP_API, lmmp_mul_toom8h_() , 以及 numb.

被这些函数引用 __lmmp_mul_n_(), lmmp_mul_(), lmmp_mul_n_(), lmmp_mul_toom8h_(), lmmp_mul_toom8h_(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_mulh_()

mp_limb_t lmmp_mulh_ ( mp_limb_t a,
mp_limb_t b )

计算两个64位无符号整数相乘的高位结果 (a*b)/B

参数
a第一个64位无符号整数
b第二个64位无符号整数
返回
乘积的高64位结果

在文件 tiny.c 第 88 行定义.

88 {
89#if (defined(__GNUC__) || defined(__clang__)) && defined(__SIZEOF_INT128__)
90 __uint128_t t = (__uint128_t)a * (__uint128_t)b;
91 return (mp_limb_t)(t >> 64);
92#else
93 uint64_t ah = a >> 32, bh = b >> 32;
94 a = (uint32_t)a, b = (uint32_t)b;
95 uint64_t r0 = a * b, r1 = a * bh, r2 = ah * b, r3 = ah * bh;
96 r3 += (r1 >> 32) + (r2 >> 32);
97 r1 = (uint32_t)r1, r2 = (uint32_t)r2;
98 r1 += r2;
99 r1 += (r0 >> 32);
100 return r3 + (r1 >> 32);
101#endif
102}
#define r2
#define r3

引用了 lmmp_mulh_, r0, r1, r2, r3 , 以及 t.

◆ lmmp_mullh_()

void lmmp_mullh_ ( mp_limb_t a,
mp_limb_t b,
mp_ptr dst )

计算两个64位无符号整数相乘的128位结果 (a*b)

参数
dst输出结果缓冲区,存储乘积结果,长度为 2
a第一个64位无符号整数
b第二个64位无符号整数
警告
dst!=NULL
返回
无返回值

引用了 lmmp_add_n_(), lmmp_add_n_sub_n_(), lmmp_add_nc_(), LMMP_API, lmmp_mullh_, lmmp_not_(), lmmp_shl_(), lmmp_shl_c_(), lmmp_shr1add_n_(), lmmp_shr1add_nc_(), lmmp_shr1sub_n_(), lmmp_shr1sub_nc_(), lmmp_shr_(), lmmp_shr_c_(), lmmp_sub_n_(), lmmp_sub_nc_(), n , 以及 numb.

函数调用图:

◆ lmmp_mullo_()

void lmmp_mullo_ ( mp_ptr dst,
mp_srcptr numa,
mp_srcptr numb,
mp_size_t n )

低位乘法 [dst,n] = [numa,n] * [numb,n] mod B^n

参数
dst输出结果缓冲区,长度至少为 n
numa第一个输入操作数,长度为 n
numb第二个输入操作数,长度为 n
nlimb长度
警告
n>0, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
返回
无返回值,结果存储在dst中,[dst,n]=[numa,n] * [numb,n] mod B^n

引用了 LMMP_API, lmmp_mullo_(), n , 以及 numb.

被这些函数引用 bench_mullo(), lmmp_mullo_(), lmmp_mullo_(), lmmp_powmod_(), TEST_CASE() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_mullo_basecase_()

void lmmp_mullo_basecase_ ( mp_ptr dst,
mp_srcptr numa,
mp_srcptr numb,
mp_size_t n )

基础低位乘法 [dst,n] = [numa,n] * [numb,n] mod B^n

参数
dst输出结果缓冲区,长度至少为 n
numa第一个输入操作数,长度为 n
numb第二个输入操作数,长度为 n
nlimb长度
警告
n>0, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
返回
无返回值,结果存储在dst中,[dst,n]=[numa,n] * [numb,n] mod B^n

引用了 LMMP_API, lmmp_mullo_basecase_(), n , 以及 numb.

被这些函数引用 bench_mullo_basecase(), lmmp_mullo_basecase_(), lmmp_mullo_basecase_() , 以及 lmmp_mullo_dc_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_mullo_dc_()

void lmmp_mullo_dc_ ( mp_ptr dst,
mp_srcptr numa,
mp_srcptr numb,
mp_ptr tp,
mp_size_t n )

低位乘法 [dst,n] = [numa,n] * [numb,n] mod B^n

参数
dst输出结果缓冲区,长度至少为 n
numa第一个输入操作数,长度为 n
numb第二个输入操作数,长度为 n
tp临时缓冲区,长度至少为 2*n
nlimb长度
警告
n>0, sep(dst,[numa|numb],tp), dst!=NULL, numa!=NULL, numb!=NULL
返回
无返回值,结果存储在dst中,[dst,n]=[numa,n] * [numb,n] mod B^n

引用了 LMMP_API, lmmp_mullo_dc_(), n, numb , 以及 tp.

被这些函数引用 bench_mullo_dc(), lmmp_binvert_unbalance_(), lmmp_mont_redc_(), lmmp_mullo_(), lmmp_mullo_dc_(), lmmp_mullo_dc_(), lmmp_mullo_n_(), lmmp_mullo_n_(), lmmp_mullo_n_(), lmmp_redc_() , 以及 lmmp_sqrlo_dc_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_mullo_fft_()

void lmmp_mullo_fft_ ( mp_ptr dst,
mp_srcptr numa,
mp_srcptr numb,
mp_size_t n,
mp_ptr scratch )

低位FFT乘法 [dst,n] = [numa,n] * [numb,n] mod B^n

参数
dst输出结果缓冲区,长度至少为 n
numa第一个输入操作数,长度为 n
numb第二个输入操作数,长度为 n
scratch临时缓冲区,长度至少为 2*n
n缓冲区 limb 长度
警告
???<n, sep(scratch,[numa|numb]), eqsep(dst,scratch)
返回
无返回值,结果存储在dst中,[dst,n]=[numa,n] * [numb,n] mod B^n

在文件 mullo.c 第 68 行定义.

68 {
71 lmmp_debug_assert(n <= hn);
72 mp_ptr tp = ALLOC_TYPE(hn + 1, mp_limb_t);
73
74 if (numa == numb) {
76 lmmp_sqr_fermat_(tp, hn, numa, n);
77 } else {
79 lmmp_mul_fermat_(tp, hn, numa, n, numb, n);
80 }
81
82 lmmp_mullo_crt_(dst, scratch, tp, n, hn);
84}
void lmmp_sqr_mersenne_fft_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na)
FFT 梅森数模平方 [dst,rn] = [numa,na]^2 mod B^rn-1
void lmmp_mul_fermat_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
费马数模乘法 [dst,rn+1]=[numa,na]*[numb,nb] mod B^rn+1
void lmmp_sqr_fermat_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na)
SSA FFT 版费马数模平方 [dst,rn+1]=[numa,na]^2 mod B^rn+1
#define scratch
static void lmmp_mullo_crt_(mp_ptr dst, mp_ptr lp, mp_ptr hp, mp_size_t n, mp_size_t hn)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 mullo.c:46

引用了 ALLOC_TYPE, lmmp_debug_assert, lmmp_fft_next_size_(), lmmp_free(), lmmp_mul_fermat_(), lmmp_mul_mersenne_fft_(), lmmp_mullo_crt_(), lmmp_mullo_fft_(), lmmp_param_assert, lmmp_sqr_fermat_(), lmmp_sqr_mersenne_fft_(), n, numb, scratch , 以及 tp.

被这些函数引用 bench_mullo_fft(), lmmp_mullo_(), lmmp_mullo_fft_(), lmmp_mullo_n_(), lmmp_mullo_n_(), lmmp_mullo_n_(), lmmp_redc_(), lmmp_sqrlo_dc_() , 以及 lmmp_sqrlo_n_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_not_()

void lmmp_not_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na )

按位取反操作 [dst,na] = ~[numa,na] (对每个limb执行按位非操作)

Copyright (C) 2026 HJimmyK (Jericho Knox)

参数
dst结果输出指针
numa源操作数指针
nalimb长度
警告
na>0, eqsep(dst,numa), dst!=NULL, numa!=NULL

按位取反操作 [dst,na] = ~[numa,na] (对每个limb执行按位非操作)

This file is part of LMMP.

LMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.

SPDX-License-Identifier: LGPL-3.0-or-later

在文件 not.c 第 26 行定义.

26 {
27 for (mp_size_t i = 0; i < na; i++) {
28 dst[i] = ~numa[i];
29 }
30}

引用了 lmmp_not_().

被这些函数引用 bench_not(), lmmp_binvert_n_dc_(), lmmp_binvert_unbalance_(), lmmp_fft_shl_coef_(), lmmp_inv_basecase_(), lmmp_invappr_newton_(), lmmp_invcbrt_newton_(), lmmp_invsqrt_newton_(), lmmp_mont_init_(), lmmp_mont_redc_(), lmmp_mullh_(), lmmp_not_(), lmmp_redc_(), lmmp_shlnot_(), mrs_neg_(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_shl_()

mp_limb_t lmmp_shl_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na,
mp_size_t shl )

左移操作 [dst,na] = [numa,na]<<shl,dst的低shl位填充0

Copyright (C) 2026 HJimmyK (Jericho Knox)

参数
dst结果输出指针
numa源操作数指针
nalimb长度
shl左移的位数 (0~63)
警告
na>0, 0<=shl<64, eqsep(dst,numa), dst!=NULL, numa!=NULL
返回
其最低shl个比特位填充[numa,na]被移出的shl个最高位,其余比特位为0

左移操作 [dst,na] = [numa,na]<<shl,dst的低shl位填充0

This file is part of LMMP.

LMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.

SPDX-License-Identifier: LGPL-3.0-or-later

在文件 shl.c 第 26 行定义.

26 {
27 if (shl == 0) {
28 lmmp_copy(dst, numa, na);
29 return 0;
30 }
31 const mp_size_t rshr = LIMB_BITS - shl;
32 mp_limb_t retval = numa[na - 1] >> rshr;
33 // 降序:dst==numa 原地时每个 numa[i-1] 在被覆盖前读取
34 for (mp_size_t i = na - 1; i > 0; i--) dst[i] = (numa[i] << shl) | (numa[i - 1] >> rshr);
35 dst[0] = numa[0] << shl;
36 return retval;
37}

引用了 LIMB_BITS, lmmp_copy , 以及 lmmp_shl_().

被这些函数引用 bench_shl(), dec_pow_extend_(), dec_pow_init_(), fib2_core_(), is_square_2(), lmmp_10pow_1_(), lmmp_12pow_1_(), lmmp_14pow_1_(), lmmp_2factorial_(), lmmp_6pow_1_(), lmmp_arith_seqprod_(), lmmp_bninv_(), lmmp_bninv_appr_newton_(), lmmp_cbrt_shapply_(), lmmp_div_(), lmmp_factorial_(), lmmp_fft_shl_coef_(), lmmp_fibonacci_(), lmmp_hyperfac_(), lmmp_inv_(), lmmp_mul_fermat_recombine_(), lmmp_mul_mersenne_cache_(), lmmp_mul_mersenne_cache_init_(), lmmp_mul_mersenne_fft_(), lmmp_mul_toom43_(), lmmp_mul_toom44_(), lmmp_mul_toom53_(), lmmp_mul_toom62_(), lmmp_mul_toom62_cache_(), lmmp_mul_toom62_cache_init_(), lmmp_mullh_(), lmmp_multinomial_(), lmmp_nCr_(), lmmp_nPr_(), lmmp_nthroot_(), lmmp_pow_1_(), lmmp_shl_(), lmmp_sqr_mersenne_fft_(), lmmp_sqr_toom4_(), lmmp_sqrt_(), lmmp_sqrt_newton_(), lmmp_superfac_(), lmmp_to_str_(), lmmp_to_str_divide_(), lmmp_toom_eval_dgr3_pm2_(), lmmp_toom_eval_pm2_(), lmmp_toom_eval_pm2exp_(), lmmp_toom_eval_pm2rexp_(), lmmp_toom_interp5_(), lmmp_toom_interp6_(), lmmp_toom_interp7_(), nthroot_chop_(), nthroot_top_limbs_(), pow_nPr_(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_shl_c_()

mp_limb_t lmmp_shl_c_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na,
mp_size_t shl,
mp_limb_t c )

带进位的左移操作 [dst,na] = [numa,na]<<shl,dst的低shl位填充c的低shl位

参数
dst结果输出指针
numa源操作数指针
nalimb长度
shl左移的位数 (0~63)
c进位值(其高(64-shl)位必须为0)
警告
na>0, 0<=shl<64, eqsep(dst,numa), dst!=NULL, numa!=NULL c的高(64-shl)位必须为0
返回
其最低shl个比特位填充[numa,na]被移出的shl个最高位,其余比特位为0

在文件 shl.c 第 39 行定义.

39 {
40 if (shl == 0) {
41 lmmp_copy(dst, numa, na);
42 return 0;
43 }
44 const mp_size_t rshr = LIMB_BITS - shl;
45 mp_limb_t retval = numa[na - 1] >> rshr;
46 c &= ((mp_limb_t)1 << shl) - 1;
47 // 同 lmmp_shl_:降序写入保证原地正确
48 for (mp_size_t i = na - 1; i > 0; i--) dst[i] = (numa[i] << shl) | (numa[i - 1] >> rshr);
49 dst[0] = (numa[0] << shl) | c;
50 return retval;
51}

引用了 LIMB_BITS, lmmp_copy , 以及 lmmp_shl_c_().

被这些函数引用 lmmp_mullh_(), lmmp_shl_c_(), lmmp_sqrt_divide_(), TEST_CASE() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_shlnot_()

mp_limb_t lmmp_shlnot_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na,
mp_size_t shl )

左移后按位取反操作 [dst,na] = ~([numa,na] << shl),dst的低shl位填充1

参数
dst结果输出指针
numa源操作数指针
nalimb长度
shl左移的位数 (0~63)
警告
na>0, 0<=shl<64, eqsep(dst,numa), dst!=NULL, numa!=NULL
返回
其最低shl个比特位填充[numa,na]被移出的shl个最高位,其余比特位为0

引用了 lmmp_addmul_1_(), lmmp_addmul_2_(), lmmp_addshl1_n_(), LMMP_API, lmmp_mul_1_(), lmmp_shlnot_(), lmmp_submul_1_(), lmmp_subshl1_n_(), n , 以及 numb.

被这些函数引用 bench_shlnot(), lmmp_fft_shl_coef_(), lmmp_invsqrt_newton_(), lmmp_shlnot_(), lmmp_shlnot_(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_shr1add_n_()

mp_limb_t lmmp_shr1add_n_ ( mp_ptr dst,
mp_srcptr numa,
mp_srcptr numb,
mp_size_t n )

加法后右移1位 [dst,n] = ([numa,n] + [numb,n]) >> 1

参数
dst结果输出指针
numa第一个加数指针
numb第二个加数指针
nlimb长度
警告
n>0, eqsep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
返回
右移操作产生的进位值 [0|1]

在文件 shr.c 第 65 行定义.

65 {
66 return lmmp_shr1add_nc_(dst, numa, numb, n, 0);
67}
mp_limb_t lmmp_shr1add_nc_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t c)
带进位加法后右移1位 [dst,n] = ([numa,n] + [numb,n] + c) >> 1
定义 shr.c:53

引用了 lmmp_shr1add_n_(), lmmp_shr1add_nc_(), n , 以及 numb.

被这些函数引用 bench_shr1add_n(), lmmp_mul_toom32_(), lmmp_mullh_(), lmmp_shr1add_n_(), lmmp_toom_couple_handling_(), lmmp_toom_interp12_(), lmmp_toom_interp16_(), lmmp_toom_interp5_(), lmmp_toom_interp6_(), lmmp_toom_interp7_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_shr1add_nc_()

mp_limb_t lmmp_shr1add_nc_ ( mp_ptr dst,
mp_srcptr numa,
mp_srcptr numb,
mp_size_t n,
mp_limb_t c )

带进位加法后右移1位 [dst,n] = ([numa,n] + [numb,n] + c) >> 1

参数
dst结果输出指针
numa第一个加数指针
numb第二个加数指针
nlimb长度
c初始进位值 [0|1]
警告
n>0, c=[0|1], eqsep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
返回
右移操作产生的进位值 [0|1]

在文件 shr.c 第 53 行定义.

53 {
54 __uint128_t pr = (__uint128_t)numa[0] + numb[0] + c;
55 mp_limb_t l = (mp_limb_t)pr & 1;
56 for (mp_size_t i = 1; i < n; i++) {
57 __uint128_t cr = (__uint128_t)numa[i] + numb[i] + (mp_limb_t)(pr >> 64);
58 dst[i - 1] = ((mp_limb_t)pr >> 1) | ((mp_limb_t)cr << 63);
59 pr = cr;
60 }
61 dst[n - 1] = ((mp_limb_t)pr >> 1) | ((mp_limb_t)(pr >> 64) << 63);
62 return l;
63}

引用了 lmmp_shr1add_nc_(), n , 以及 numb.

被这些函数引用 lmmp_mul_fft_crt_(), lmmp_mullh_(), lmmp_mullo_crt_(), lmmp_shr1add_n_(), lmmp_shr1add_nc_(), lmmp_sqr_fft_(), mrs_mul_core_(), mrs_sqr_core_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_shr1sub_n_()

mp_limb_t lmmp_shr1sub_n_ ( mp_ptr dst,
mp_srcptr numa,
mp_srcptr numb,
mp_size_t n )

减法后右移1位 [dst,n] = ([numa,n] - [numb,n]) >> 1

参数
dst结果输出指针
numa被减数指针
numb减数指针
n操作数的位数(limb数量)
警告
n>0, eqsep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
返回
右移操作产生的进位值 (0或1)

在文件 shr.c 第 87 行定义.

87 {
88 return lmmp_shr1sub_nc_(dst, numa, numb, n, 0);
89}
mp_limb_t lmmp_shr1sub_nc_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t c)
带借位减法后右移1位 [dst,n] = ([numa,n] - [numb,n] - c) >> 1
定义 shr.c:69

引用了 lmmp_shr1sub_n_(), lmmp_shr1sub_nc_(), n , 以及 numb.

被这些函数引用 bench_shr1sub_n(), lmmp_mul_toom32_(), lmmp_mullh_(), lmmp_shr1sub_n_(), lmmp_toom_couple_handling_(), lmmp_toom_interp12_(), lmmp_toom_interp16_(), lmmp_toom_interp5_(), lmmp_toom_interp6_(), lmmp_toom_interp7_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_shr1sub_nc_()

mp_limb_t lmmp_shr1sub_nc_ ( mp_ptr dst,
mp_srcptr numa,
mp_srcptr numb,
mp_size_t n,
mp_limb_t c )

带借位减法后右移1位 [dst,n] = ([numa,n] - [numb,n] - c) >> 1

参数
dst结果输出指针
numa被减数指针
numb减数指针
nlimb长度
c初始借位值 [0|1]
警告
n>0, c=[0|1], eqsep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
返回
右移操作产生的进位值 [0|1]

在文件 shr.c 第 69 行定义.

69 {
70 mp_limb_t o = numa[0];
71 mp_limb_t u = o - numb[0];
72 mp_limb_t pr = u - c;
73 mp_limb_t d = (u > o) + (pr > u);
74 mp_limb_t l = pr & 1;
75 for (mp_size_t i = 1; i < n; i++) {
76 o = numa[i];
77 u = o - numb[i];
78 mp_limb_t r = u - d;
79 d = (u > o) + (r > u);
80 dst[i - 1] = (pr >> 1) | (r << 63);
81 pr = r;
82 }
83 dst[n - 1] = (pr >> 1) | (d << 63);
84 return l;
85}

引用了 lmmp_shr1sub_nc_(), n , 以及 numb.

被这些函数引用 lmmp_mullh_(), lmmp_shr1sub_n_(), lmmp_shr1sub_nc_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_shr_()

mp_limb_t lmmp_shr_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na,
mp_size_t shr )

右移操作 [dst,na] = [numa,na]>>shr,dst的高shr位填充0

Copyright (C) 2026 HJimmyK (Jericho Knox)

参数
dst结果输出指针
numa源操作数指针
nalimb长度
shr右移的位数 (0~63)
警告
na>0, 0<=shr<64, eqsep(dst,numa), dst!=NULL, numa!=NULL 允许dst指针地址小于numa(即支持原地长移位操作)
返回
其最高shr个比特位填充[numa,na]被移出的shr个最低位,其余比特位为0

右移操作 [dst,na] = [numa,na]>>shr,dst的高shr位填充0

This file is part of LMMP.

LMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.

SPDX-License-Identifier: LGPL-3.0-or-later

在文件 shr.c 第 26 行定义.

26 {
27 if (shr == 0) {
28 lmmp_copy(dst, numa, na);
29 return 0;
30 }
31 const mp_size_t rshr = LIMB_BITS - shr;
32 mp_limb_t retval = numa[0] << rshr;
33 mp_size_t i = 0;
34 for (; i + 1 < na; i++) dst[i] = (numa[i] >> shr) | (numa[i + 1] << rshr);
35 dst[i] = numa[i] >> shr;
36 return retval;
37}

引用了 LIMB_BITS, lmmp_copy , 以及 lmmp_shr_().

被这些函数引用 bench_shr(), dec_pow_extend_(), ipn_lucas_i_(), ipn_mont_half_(), ipn_notrial_i_(), lmmp_bninv_(), lmmp_cbrt_(), lmmp_div_(), lmmp_fft_extract_coef_(), lmmp_from_decimal_(), lmmp_gcdext_derive_(), lmmp_invsqrt_newton_(), lmmp_mullh_(), lmmp_nthroot_(), lmmp_powmod_(), lmmp_shr_(), lmmp_sqrt_(), lmmp_sqrt_divide_(), lmmp_sqrt_newton_(), lmmp_to_str_divide_(), lmmp_toom_couple_handling_(), lmmp_toom_interp6_(), lmmp_toom_interp7_(), nthroot_top_limbs_(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_shr_c_()

mp_limb_t lmmp_shr_c_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na,
mp_size_t shr,
mp_limb_t c )

带进位的右移操作 [dst,na] = [numa,na]>>shr,dst的高shr位填充c的高shr位

参数
dst结果输出指针
numa源操作数指针
nalimb长度
shr右移的位数 (0~63)
c进位值(其低(64-shr)位必须为0)
警告
na>0, 0<=shr<64, eqsep(dst,numa), dst!=NULL, numa!=NULL c的低(64-shr)位必须为0 允许dst指针地址小于numa(即支持原地长移位操作)
返回
其最高shr个比特位填充[numa,na]被移出的shr个最低位,其余比特位为0

在文件 shr.c 第 39 行定义.

39 {
40 if (shr == 0) {
41 lmmp_copy(dst, numa, na);
42 return 0;
43 }
44 const mp_size_t rshr = LIMB_BITS - shr;
45 mp_limb_t retval = numa[0] << rshr;
46 mp_size_t i = 0;
47 for (; i + 1 < na; i++) dst[i] = (numa[i] >> shr) | (numa[i + 1] << rshr);
48 c &= ~(((mp_limb_t)1 << rshr) - 1);
49 dst[i] = (numa[i] >> shr) | c;
50 return retval;
51}

引用了 LIMB_BITS, lmmp_copy , 以及 lmmp_shr_c_().

被这些函数引用 lmmp_inv_(), lmmp_mullh_(), lmmp_shr_c_(), TEST_CASE() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_sqr_()

void lmmp_sqr_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na )

平方操作 [dst,2*na] = [numa,na]^2

参数
dst平方结果输出指针(需要2*na的limb长度)
numa输入操作数指针
na输入的 limb 长度
警告
na>0, sep(dst,numa), dst!=NULL, numa!=NULL
返回
无返回值,结果存储在dst中

引用了 LMMP_API , 以及 lmmp_sqr_.

◆ lmmp_sqr_basecase_()

void lmmp_sqr_basecase_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na )

基础平方运算 [dst,2*na] = [numa,na]^2

参数
dst输出结果缓冲区,长度至少为 2*na
numa输入操作数,长度为 na
na输入操作数的 limb 长度
警告
0<na, sep(dst,numa), dst!=NULL, numa!=NULL
返回
无返回值,结果存储在dst中

引用了 LMMP_API , 以及 lmmp_sqr_basecase_().

被这些函数引用 __lmmp_sqr_hard_n_(), bench_sqr_basecase(), lmmp_sqr_basecase_(), lmmp_sqr_basecase_(), TEST_CASE() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_sqr_fermat_()

void lmmp_sqr_fermat_ ( mp_ptr dst,
mp_size_t rn,
mp_srcptr numa,
mp_size_t na )

SSA FFT 版费马数模平方 [dst,rn+1]=[numa,na]^2 mod B^rn+1

参数
dst输出结果缓冲区,长度至少为 rn+1
rn模运算的阶数参数,须为 FFT 可行尺寸(lmmp_fft_next_size_(rn)==rn); rn = lmmp_fft_next_size_((2*na + 1) >> 1) 为可容纳乘积的推荐最小值
numa操作数,长度为 na
na操作数的 limb 长度
警告
eqsep(dst,numa), 0<=[numa,na]<2*B^rn, lmmp_fft_next_size_(rn)==rn, dst!=NULL, numa!=NULL
返回
无返回值,结果存储在dst中

在文件 sqr_fft.c 第 87 行定义.

87 {
88 mp_size_t N = rn * LIMB_BITS;
90 mp_size_t K = ((mp_size_t)1) << k;
91 lmmp_debug_assert(!(N & (K - 1)));
92 mp_size_t M = N >> k;
93 mp_size_t n = 2 * M + k + 2;
94
95 n = (n + LIMB_BITS - 1) & (-LIMB_BITS);
96 n = (((n - 1) >> k) + 1) << k;
97
98 fft_memstack msr;
99 msr.maxdepth = -1;
100 msr.tempdepth = -1;
101 msr.lenw = n / LIMB_BITS;
102 mp_size_t nlen = msr.lenw + 1;
103
104 msr.temp_coef = (mp_ptr)lmmp_fft_memstack_(&msr, (((nlen + 1) << k) + nlen) * LIMB_BYTES);
105
106 mp_ptr *pfca = (mp_ptr*)(msr.temp_coef + nlen);
107 mp_size_t narest = na * LIMB_BITS;
108
109 for (mp_size_t i = 0; i < K; ++i) {
110 mp_size_t coeflen;
111 pfca[i] = (mp_ptr)(pfca + K) + i * nlen;
112 if (narest > 0) {
113 coeflen = M + (i == K - 1);
114 coeflen = LMMP_MIN(narest, coeflen);
115 narest -= coeflen;
116 lmmp_fft_extract_coef_(pfca[i], numa, M * i, coeflen, msr.lenw);
117 if (i > 0)
118 lmmp_fft_shl_coef_(&msr, pfca + i, i * n >> k);
119 } else {
120 lmmp_zero(pfca[i], nlen);
121 }
122 }
123 lmmp_fft_(&msr, pfca, k, n >> (k - 1));
124
125 lmmp_sqr_fermat_recurse_(&msr, pfca, K);
126
127 lmmp_ifft_(&msr, pfca, k, n >> (k - 1));
128
129 lmmp_mul_fermat_recombine_(&msr, dst, pfca, K, k, n, M, rn);
130
131 if (dst[rn] && !lmmp_zero_q_(dst, rn)) {
132 dst[rn] = 0;
133 lmmp_dec(dst);
134 }
135
136 lmmp_fft_memstack_(&msr, 0);
137}
static void lmmp_sqr_fermat_recurse_(fft_memstack *ms, mp_ptr *pc1, mp_size_t K0)
Copyright (C) 2026 HJimmyK (Jericho Knox)

引用了 k, fft_memstack::lenw, LIMB_BITS, LIMB_BYTES, lmmp_debug_assert, lmmp_dec, lmmp_fft_(), lmmp_fft_best_k_(), lmmp_fft_extract_coef_(), lmmp_fft_memstack_(), lmmp_fft_shl_coef_(), lmmp_ifft_(), LMMP_MIN, lmmp_mul_fermat_recombine_(), lmmp_sqr_fermat_(), lmmp_sqr_fermat_recurse_(), lmmp_zero, lmmp_zero_q_(), fft_memstack::maxdepth, n, fft_memstack::temp_coef , 以及 fft_memstack::tempdepth.

被这些函数引用 lmmp_mul_toom62_unbalance_(), lmmp_mullo_fft_(), lmmp_sqr_fermat_(), lmmp_sqr_fft_() , 以及 mrs_sqr_core_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_sqr_fft_()

void lmmp_sqr_fft_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na )

FFT平方运算 [dst,2*na] = [numa,na]^2

参数
dst输出结果缓冲区,长度至少为 2*na
numa输入操作数指针,长度为 na
na输入操作数的 limb 长度
警告
???<=na, sep(dst,numa), dst!=NULL, numa!=NULL
返回
无返回值,结果存储在dst中

在文件 sqr_fft.c 第 216 行定义.

216 {
217 lmmp_param_assert(na > 0);
218 lmmp_param_assert(dst != NULL && numa != NULL);
220 lmmp_debug_assert(na <= hn);
221 mp_ptr tp = ALLOC_TYPE(hn + 1, mp_limb_t);
222
223 lmmp_sqr_mersenne_fft_(dst, hn, numa, na);
224 lmmp_sqr_fermat_(tp, hn, numa, na);
225
226 mp_limb_t cy = lmmp_shr1add_nc_(dst, dst, tp, hn, tp[hn]);
227 cy <<= LIMB_BITS - 1;
228 dst[hn - 1] += cy;
229 if (dst[hn - 1] < cy)
230 lmmp_inc(dst);
231
232 if (na == hn) {
233 cy = tp[hn] + lmmp_sub_n_(dst + hn, dst, tp, hn);
234 // cy==1 means [tp,hn+1]!=0, then [dst,hn]!=0
235 // cy==2 is impossible since [tp,hn+1] is normalized.
236 // so the following dec won't overflow.
237 lmmp_dec_1(dst, cy);
238 } else {
239 cy = lmmp_sub_n_(dst + hn, dst, tp, 2 * na - hn);
240 cy = tp[hn] + lmmp_sub_nc_(tp + 2 * na - hn, dst + 2 * na - hn, tp + 2 * na - hn, 2 * hn - (2 * na), cy);
241 cy = lmmp_sub_1_(dst, dst, 2 * na, cy);
242 }
243 lmmp_free(tp);
244}
#define lmmp_inc(p)
加1宏(预期无进位)
#define lmmp_dec_1(p, dec)
减指定值宏(预期无借位)
static mp_limb_t lmmp_sub_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
减单精度数静态内联函数 [dst,na]=[numa,na]-x

引用了 ALLOC_TYPE, LIMB_BITS, lmmp_debug_assert, lmmp_dec_1, lmmp_fft_next_size_(), lmmp_free(), lmmp_inc, lmmp_param_assert, lmmp_shr1add_nc_(), lmmp_sqr_fermat_(), lmmp_sqr_fft_(), lmmp_sqr_mersenne_fft_(), lmmp_sub_1_(), lmmp_sub_n_(), lmmp_sub_nc_() , 以及 tp.

被这些函数引用 __lmmp_sqr_(), lmmp_mul_toom62_unbalance_(), lmmp_sqr_() , 以及 lmmp_sqr_fft_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_sqr_mersenne_()

void lmmp_sqr_mersenne_ ( mp_ptr dst,
mp_size_t rn,
mp_srcptr numa,
mp_size_t na )

梅森数模平方 [dst,rn] = [numa,na]^2 mod B^rn-1

参数
dst输出结果缓冲区,长度至少为 rn
rn模运算的阶数参数,任意正尺寸均可(未对齐 fft 可行尺寸时回落 dc); rn = lmmp_fft_next_size_((2*na + 1) >> 1) 为进入 fft 档的推荐最小值
numa输入操作数,长度为 na
na输入操作数的 limb 长度
警告
sep(dst,numa), 0<=[numa,na]<B^rn, dst!=NULL, numa!=NULL
返回
无返回值,结果存储在dst中

在文件 mul_mersenne.c 第 434 行定义.

434 {
435 if (rn >= SQR_MERSENNE_FFT_THRESHOLD && lmmp_fft_next_size_(rn) == rn)
436 lmmp_sqr_mersenne_fft_(dst, rn, numa, na);
437 else
438 lmmp_sqr_mersenne_dc_(dst, rn, numa, na);
439}
#define SQR_MERSENNE_FFT_THRESHOLD
void lmmp_sqr_mersenne_dc_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na)
分治梅森数模平方 [dst,rn] = [numa,na]^2 mod B^rn-1

引用了 lmmp_fft_next_size_(), lmmp_sqr_mersenne_(), lmmp_sqr_mersenne_dc_(), lmmp_sqr_mersenne_fft_() , 以及 SQR_MERSENNE_FFT_THRESHOLD.

被这些函数引用 lmmp_invcbrt_newton_(), lmmp_invsqrt_newton_(), lmmp_mul_toom62_unbalance_(), lmmp_sqr_mersenne_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_sqr_mersenne_dc_()

void lmmp_sqr_mersenne_dc_ ( mp_ptr dst,
mp_size_t rn,
mp_srcptr numa,
mp_size_t na )

分治梅森数模平方 [dst,rn] = [numa,na]^2 mod B^rn-1

参数
dst输出结果缓冲区,长度至少为 rn
rn模运算的阶数参数
numa输入操作数,长度为 na
na输入操作数的 limb 长度
警告
sep(dst,numa), 0<=[numa,na]<B^rn, 4*na>rn, dst!=NULL, numa!=NULL
返回
无返回值,结果存储在dst中

在文件 mul_mersenne.c 第 397 行定义.

397 {
398 lmmp_param_assert(na > 0 && na <= rn);
399 lmmp_param_assert(dst != NULL && numa != NULL);
400 lmmp_debug_assert(4 * na > rn);
401
402 mp_ptr tp = ALLOC_TYPE(2 * rn + 4, mp_limb_t);
403 mrs_sqr_core_(dst, rn, numa, na, tp);
404 mrs_norm_zero_(dst, rn);
405 lmmp_free(tp);
406}
static void mrs_sqr_core_(mp_ptr rp, mp_size_t rn, mp_srcptr ap, mp_size_t an, mp_ptr tp)
分治梅森平方核心(半归一化内部约定:零类 = B^n-1)

引用了 ALLOC_TYPE, lmmp_debug_assert, lmmp_free(), lmmp_param_assert, lmmp_sqr_mersenne_dc_(), mrs_norm_zero_(), mrs_sqr_core_() , 以及 tp.

被这些函数引用 lmmp_mul_toom62_unbalance_(), lmmp_sqr_mersenne_(), lmmp_sqr_mersenne_dc_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_sqr_mersenne_fft_()

void lmmp_sqr_mersenne_fft_ ( mp_ptr dst,
mp_size_t rn,
mp_srcptr numa,
mp_size_t na )

FFT 梅森数模平方 [dst,rn] = [numa,na]^2 mod B^rn-1

参数
dst输出结果缓冲区,长度至少为 rn
rn模运算的阶数参数,须为 FFT 可行尺寸(lmmp_fft_next_size_(rn)==rn); rn = lmmp_fft_next_size_((2*na + 1) >> 1) 为可容纳乘积的推荐最小值
numa输入操作数,长度为 na
na输入操作数的 limb 长度
警告
eqsep(dst,numa), 0<=[numa,na]<B^rn, lmmp_fft_next_size_(rn)==rn, dst!=NULL, numa!=NULL
返回
无返回值,结果存储在dst中

在文件 sqr_fft.c 第 139 行定义.

139 {
140 mp_size_t N = rn * LIMB_BITS;
142 mp_size_t K = ((mp_size_t)1) << k;
143
144 lmmp_debug_assert(!(N & (K - 1)));
145 mp_size_t M = N >> k;
146 mp_size_t n = 2 * M + k;
147
148 n = (n + LIMB_BITS - 1) & (-LIMB_BITS);
149 n = (((n - 1) >> (k - 1)) + 1) << (k - 1);
150
151 fft_memstack msr;
152 msr.maxdepth = -1;
153 msr.tempdepth = -1;
154 msr.lenw = n / LIMB_BITS;
155 mp_size_t nlen = msr.lenw + 1;
156
157 msr.temp_coef = (mp_ptr)lmmp_fft_memstack_(&msr, (((nlen + 1) << k) + nlen) * LIMB_BYTES);
158
159 mp_ptr *pfca = (mp_ptr*)(msr.temp_coef + nlen);
160 mp_size_t narest = na * LIMB_BITS;
161
162 for (mp_size_t i = 0; i < K; ++i) {
163 mp_size_t coeflen;
164 pfca[i] = (mp_ptr)(pfca + K) + i * nlen;
165 if (narest > 0) {
166 coeflen = LMMP_MIN(narest, M);
167 narest -= coeflen;
168 lmmp_fft_extract_coef_(pfca[i], numa, M * i, coeflen, msr.lenw);
169 } else {
170 lmmp_zero(pfca[i], nlen);
171 }
172 }
173 lmmp_fft_(&msr, pfca, k, n >> (k - 1));
174
175 lmmp_sqr_fermat_recurse_(&msr, pfca, K);
176
177 lmmp_ifft_(&msr, pfca, k, n >> (k - 1));
178
179 mp_size_t rhead = 0, maxc = 0;
180 for (mp_size_t i = 0; i < K; ++i) {
181 lmmp_fft_shr_coef_(&msr, pfca + i, k);
182 mp_ptr nums = pfca[i];
183
184 if (nums[nlen - 1]) {
185 lmmp_dec(nums);
186 lmmp_debug_assert(nums[nlen - 1] == 1);
187 nums[nlen - 1] = 0;
188 }
189
190 mp_size_t roffset = i * M;
191 mp_size_t shl = roffset & (LIMB_BITS - 1);
192 roffset /= LIMB_BITS;
193
194 if (shl)
195 lmmp_shl_(nums, nums, nlen, shl);
196
197 if (i == 0) {
198 rhead = LMMP_MIN(nlen, rn);
199 lmmp_copy(dst, nums, rhead);
200 } else if (roffset + nlen <= rn) {
201 lmmp_add_(dst + roffset, nums, nlen, dst + roffset, rhead - roffset);
202 rhead = roffset + nlen;
203 } else {
204 maxc += lmmp_add_(dst + roffset, nums, rn - roffset, dst + roffset, rhead - roffset);
205 maxc += lmmp_add_(dst, dst, rn, nums + rn - roffset, nlen + roffset - rn);
206 rhead = rn;
207 }
208 }
209
210 if (!lmmp_add_1_(dst, dst, rn, 1 + maxc))
211 lmmp_dec(dst);
212
213 lmmp_fft_memstack_(&msr, 0);
214}

引用了 k, fft_memstack::lenw, LIMB_BITS, LIMB_BYTES, lmmp_add_(), lmmp_add_1_(), lmmp_copy, lmmp_debug_assert, lmmp_dec, lmmp_fft_(), lmmp_fft_best_k_(), lmmp_fft_extract_coef_(), lmmp_fft_memstack_(), lmmp_fft_shr_coef_(), lmmp_ifft_(), LMMP_MIN, lmmp_shl_(), lmmp_sqr_fermat_recurse_(), lmmp_sqr_mersenne_fft_(), lmmp_zero, fft_memstack::maxdepth, n, fft_memstack::temp_coef , 以及 fft_memstack::tempdepth.

被这些函数引用 lmmp_mul_toom62_unbalance_(), lmmp_mullo_fft_(), lmmp_sqr_fft_(), lmmp_sqr_mersenne_(), lmmp_sqr_mersenne_fft_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_sqr_toom2_()

void lmmp_sqr_toom2_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na )

Toom-2平方运算 [dst,2*na] = [numa,na]^2

参数
dst输出结果缓冲区,长度至少为 2*na
numa输入操作数,长度为 na
na输入操作数的 limb 长度
警告
4<=na, sep(dst,numa), dst!=NULL, numa!=NULL
返回
无返回值,结果存储在dst中

引用了 LMMP_API , 以及 lmmp_sqr_toom2_().

被这些函数引用 __lmmp_sqr_(), lmmp_sqr_(), lmmp_sqr_toom2_(), lmmp_sqr_toom2_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_sqr_toom3_()

void lmmp_sqr_toom3_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na )

Toom-3平方运算 [dst,2*na] = [numa,na]^2

参数
dst输出结果缓冲区,长度至少为 2*na
numa输入操作数,长度为 na
na输入操作数的 limb 长度
警告
5<=na, sep(dst,numa), dst!=NULL, numa!=NULL
返回
无返回值,结果存储在dst中

引用了 LMMP_API , 以及 lmmp_sqr_toom3_().

被这些函数引用 __lmmp_sqr_(), lmmp_sqr_(), lmmp_sqr_toom3_(), lmmp_sqr_toom3_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_sqr_toom4_()

void lmmp_sqr_toom4_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t an )

Toom-4平方运算 [dst,2*na] = [numa,na]^2

参数
dst输出结果缓冲区,长度至少为 2*na
numa输入操作数,长度为 na
na输入操作数的 limb 长度
警告
10<=na, sep(dst,numa), dst!=NULL, numa!=NULL
返回
无返回值,结果存储在dst中

引用了 an, LMMP_API , 以及 lmmp_sqr_toom4_().

被这些函数引用 __lmmp_sqr_(), lmmp_sqr_(), lmmp_sqr_toom4_(), lmmp_sqr_toom4_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_sqr_toom6_()

void lmmp_sqr_toom6_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na )

Toom-6平方运算 [dst,2*na] = [numa,na]^2 (评估点 ±4,±2,±1,±1/2,±1/4,0,无inf点)

参数
dst输出结果缓冲区,长度至少为 2*na
numa输入操作数,长度为 na
na输入操作数的 limb 长度
警告
26<=na, sep(dst,numa), dst!=NULL, numa!=NULL
返回
无返回值,结果存储在dst中

引用了 LMMP_API , 以及 lmmp_sqr_toom6_().

被这些函数引用 __lmmp_sqr_(), lmmp_sqr_(), lmmp_sqr_toom6_(), lmmp_sqr_toom6_(), TEST_CASE() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_sqr_toom8_()

void lmmp_sqr_toom8_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na )

Toom-8平方运算 [dst,2*na] = [numa,na]^2 (评估点 ±8,±4,±2,±1,±1/2,±1/4,±1/8,0,无inf点)

参数
dst输出结果缓冲区,长度至少为 2*na
numa输入操作数,长度为 na
na输入操作数的 limb 长度
警告
51<=na, na!=57, sep(dst,numa), dst!=NULL, numa!=NULL
返回
无返回值,结果存储在dst中

引用了 LMMP_API , 以及 lmmp_sqr_toom8_().

被这些函数引用 __lmmp_sqr_(), lmmp_sqr_(), lmmp_sqr_toom8_(), lmmp_sqr_toom8_(), TEST_CASE() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_sqrlo_basecase_()

void lmmp_sqrlo_basecase_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t n )

基础低位平方 [dst,n] = [numa,n]^2 mod B^n

参数
dst输出结果缓冲区,长度至少为 n
numa输入操作数,长度为 n
nlimb长度
警告
n>0, sep(dst,numa), dst!=NULL, numa!=NULL
返回
无返回值,结果存储在dst中,[dst,n]=[numa,n]^2 mod B^n
注解
三角分解:上三角交叉积每对只乘一次(约 n^2/4 次 limb 乘法, 为 mullo(a,a) 的一半),末尾一趟融合的倍增+对角平方收尾

引用了 LMMP_API, lmmp_sqrlo_basecase_() , 以及 n.

被这些函数引用 lmmp_sqrlo_basecase_(), lmmp_sqrlo_basecase_() , 以及 lmmp_sqrlo_dc_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_sqrlo_dc_()

void lmmp_sqrlo_dc_ ( mp_ptr dst,
mp_srcptr numa,
mp_ptr tp,
mp_size_t n )

低位平方 [dst,n] = [numa,n]^2 mod B^n

参数
dst输出结果缓冲区,长度至少为 n
numa第一个输入操作数,长度为 n
tp临时缓冲区,长度至少为 2*n
nlimb长度
警告
n>0, sep(dst,numa,tp), dst!=NULL, numa!=NULL, tp!=NULL
返回
无返回值,结果存储在dst中,[dst,n]=[numa,n]^2 mod B^n

引用了 LMMP_API, lmmp_inv_1_(), lmmp_inv_2_1_(), lmmp_mullo_fft_(), lmmp_sqrlo_dc_(), n, numb, scratch , 以及 tp.

被这些函数引用 lmmp_mullo_(), lmmp_sqrlo_dc_(), lmmp_sqrlo_dc_() , 以及 lmmp_sqrlo_n_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_sub_()

mp_limb_t lmmp_sub_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na,
mp_srcptr numb,
mp_size_t nb )
inlinestatic

减法静态内联函数 [dst,na]=[numa,na]-[numb,nb]

参数
dst输出结果缓冲区,存储numa - numb
numa被减数,长度为na
na被减数的 limb 长度
numb减数,长度为nb
nb减数的 limb 长度
返回
借位标志(1表示有借位,0表示无借位)
警告
0<nb<=na, eqsep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL

在文件 lmmpn.h 第 1220 行定义.

1220 {
1221 LMMP_AORS_(lmmp_sub_n_, ((dst[nb++] = _x_ - 1), _x_ == 0));
1222}

引用了 LMMP_AORS_, LMMP_INLINE, lmmp_sub_(), lmmp_sub_n_() , 以及 numb.

被这些函数引用 gcdext_pick_s_(), lmmp_cbrt_6_fast_(), lmmp_cbrt_divide_(), lmmp_gcdext_1_(), lmmp_gcdext_2_(), lmmp_gcdext_derive_(), lmmp_gcdext_hgcd_(), lmmp_gcdext_lehmer_(), lmmp_gcdext_smag_(), lmmp_hgcd_adjust_(), lmmp_lehmer_sub_mag_(), lmmp_modinv_(), lmmp_mul_fermat_recombine_(), lmmp_mul_fft_cache_(), lmmp_mul_fft_cache_init_(), lmmp_mul_fft_mods_(), lmmp_mul_toom22_(), lmmp_mul_toom32_(), lmmp_mul_toom52_(), lmmp_mul_toom62_(), lmmp_mul_toom62_cache_init_(), lmmp_nthroot_(), lmmp_sqrt_divide_(), lmmp_sub_(), lmmp_toom_interp7_(), mat22_addsg_(), mrs_mul_core_(), mrs_sqr_core_(), TEST_CASE(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_sub_1_()

mp_limb_t lmmp_sub_1_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na,
mp_limb_t x )
inlinestatic

减单精度数静态内联函数 [dst,na]=[numa,na]-x

参数
dst输出结果缓冲区,存储numa - x
numa被减数,长度为na
na被减数的 limb 长度
x减数(单个 limb )
返回
借位标志(1表示有借位,0表示无借位)
警告
na>0, eqsep(dst,numa), dst!=NULL, numa!=NULL

在文件 lmmpn.h 第 1272 行定义.

1272 {
1274}
#define LMMP_SUBCB_(r, x, y)

引用了 LMMP_AORS_1_, LMMP_INLINE, lmmp_sub_1_() , 以及 LMMP_SUBCB_.

被这些函数引用 lc1_(), lmmp_cbrt_(), lmmp_cbrt_divide_(), lmmp_div_divide_n_(), lmmp_div_mulinv_(), lmmp_div_s_(), lmmp_fibonacci_(), lmmp_mont_fold_hi_(), lmmp_mul_fft_crt_(), lmmp_mul_toom32_(), lmmp_mul_toom42_(), lmmp_mul_toom42_cache_init_(), lmmp_mullo_crt_(), lmmp_powmod_(), lmmp_sqr_fft_(), lmmp_sqrt_(), lmmp_sqrt_divide_(), lmmp_sub_1_(), mrs_mul_core_(), mrs_sqr_core_() , 以及 nthroot_sub_small_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_sub_n_()

mp_limb_t lmmp_sub_n_ ( mp_ptr dst,
mp_srcptr numa,
mp_srcptr numb,
mp_size_t n )

无借位的n位减法 [dst,n] = [numa,n] - [numb,n]

参数
dst结果输出指针
numa被减数指针
numb减数指针
nlimb长度
警告
n>0, eqsep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
返回
运算后的最终借位值 [0|1]

在文件 sub_n.c 第 84 行定义.

84 {
85 mp_size_t i = 0;
86 mp_limb_t cy = 0;
87
88 for (; i < n; i++) {
89 mp_limb_t a, b;
90 a = numa[i];
91 b = numb[i];
92 b += cy;
93 cy = (b < cy);
94 cy += (a < b);
95 dst[i] = a - b;
96 }
97
98 return cy;
99}

引用了 lmmp_sub_n_(), n , 以及 numb.

被这些函数引用 bench_sub_n(), fib2_core_(), ipn_mont_add_(), ipn_mont_dbl_(), ipn_mont_neg_(), ipn_mont_sub_(), ipn_proth_i_(), lmmp_bninv_appr_newton_(), lmmp_cbrt_(), lmmp_cbrt_6_fast_(), lmmp_cbrt_divide_(), lmmp_div_(), lmmp_div_basecase_(), lmmp_div_divide_n_(), lmmp_div_mulinv_(), lmmp_div_s_(), lmmp_divexact_divide_(), lmmp_divexact_mu_run_(), lmmp_fibonacci_(), lmmp_hgcd_apply_mod_(), lmmp_invappr_newton_(), lmmp_mont_fold_hi_(), lmmp_mont_init_(), lmmp_mont_redc_(), lmmp_mont_sp_redc_(), lmmp_mul_fermat_recurse_(), lmmp_mul_fft_crt_(), lmmp_mul_toom22_(), lmmp_mul_toom32_(), lmmp_mul_toom52_(), lmmp_mul_toom62_(), lmmp_mul_toom62_cache_init_(), lmmp_mullh_(), lmmp_mullo_crt_(), lmmp_powmod_(), lmmp_sqr_fermat_recurse_(), lmmp_sqr_fft_(), lmmp_sqr_toom2_(), lmmp_sub_(), lmmp_sub_n_(), lmmp_toom_couple_handling_(), lmmp_toom_interp12_(), lmmp_toom_interp16_(), lmmp_toom_interp5_(), lmmp_toom_interp6_(), lmmp_toom_interp7_(), mrs_mul_bnp1_(), mrs_mul_core_(), mrs_sqr_bnp1_(), mrs_sqr_core_(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_sub_nc_()

mp_limb_t lmmp_sub_nc_ ( mp_ptr dst,
mp_srcptr numa,
mp_srcptr numb,
mp_size_t n,
mp_limb_t c )

带借位的n位减法 [dst,n] = [numa,n] - [numb,n] - c

Copyright (C) 2026 HJimmyK (Jericho Knox)

参数
dst结果输出指针
numa被减数指针
numb减数指针
nlimb长度
c初始借位值 [0|1]
警告
c=[0|1], n>0, eqsep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
返回
运算后的最终借位值 [0|1]

带借位的n位减法 [dst,n] = [numa,n] - [numb,n] - c

This file is part of LMMP.

LMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.

SPDX-License-Identifier: LGPL-3.0-or-later

在文件 sub_n.c 第 67 行定义.

67 {
68 mp_size_t i = 0;
69 mp_limb_t cy = c;
70
71 for (; i < n; i++) {
72 mp_limb_t a, b;
73 a = numa[i];
74 b = numb[i];
75 b += cy;
76 cy = (b < cy);
77 cy += (a < b);
78 dst[i] = a - b;
79 }
80
81 return cy;
82}

引用了 lmmp_sub_nc_(), n , 以及 numb.

被这些函数引用 bench_sub_nc(), lmmp_div_(), lmmp_div_mulinv_(), lmmp_divexact_mu_run_(), lmmp_fft_bfy_(), lmmp_ifft_bfy_(), lmmp_invappr_newton_(), lmmp_mul_fft_crt_(), lmmp_mullh_(), lmmp_mullo_crt_(), lmmp_sqr_fft_(), lmmp_sub_nc_(), mrs_mul_core_(), mrs_sqr_core_(), TEST_CASE(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_submul_1_()

mp_limb_t lmmp_submul_1_ ( mp_ptr numa,
mp_srcptr numb,
mp_size_t n,
mp_limb_t b )

乘以单limb并累减操作 [numa,n] -= [numb,n] * b

参数
numa被减数指针(结果也存储在此)
numb乘数指针
nlimb长度
b乘数
警告
n>0, eqsep(numa,numb)), numa!=NULL, numb!=NULL
返回
运算后的借位limb值

在文件 mul_1.c 第 131 行定义.

131 {
132 mp_limb_t d = 0;
133 mp_size_t i = 0;
134
135#define LMMP_SUBMUL_1_STEP(k) \
136 { \
137 __uint128_t P = (__uint128_t)numb[i + (k)] * b; \
138 mp_limb_t o = numa[i + (k)]; \
139 mp_limb_t u = o - (mp_limb_t)P; \
140 mp_limb_t r = u - d; \
141 d = (mp_limb_t)(P >> 64) + (u > o) + (r > u); \
142 numa[i + (k)] = r; \
143 }
144
145 for (; i + 8 <= n; i += 8) {
154 }
155 for (; i < n; i++) {
157 }
158#undef LMMP_SUBMUL_1_STEP
159 return d;
160}
#define LMMP_SUBMUL_1_STEP(k)

引用了 lmmp_submul_1_(), LMMP_SUBMUL_1_STEP, n , 以及 numb.

被这些函数引用 bench_submul_1(), ipn_sdiv_mul1_(), lc1_(), lmmp_cbrt_(), lmmp_cbrt_divide_(), lmmp_div_(), lmmp_div_basecase_(), lmmp_hgcd_step_(), lmmp_shlnot_(), lmmp_sqrt_(), lmmp_submul_1_(), lmmp_toom_interp12_(), lmmp_toom_interp16_(), lmmp_toom_interp7_(), TEST_CASE(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_subshl1_n_()

mp_limb_t lmmp_subshl1_n_ ( mp_ptr dst,
mp_srcptr numa,
mp_srcptr numb,
mp_size_t n )

减法结合左移1位操作 [dst,n] = [numa,n] - ([numb,n] << 1)

参数
dst结果输出指针
numa被减数指针
numb减数指针(先左移1位)
nlimb长度
警告
n>0, eqsep(dst,[numa|numb]), dst!=NULL, numa!=NULL
返回
运算后的借位值 [0|1|2]

在文件 shl.c 第 80 行定义.

80 {
81 mp_limb_t d = 0, mb = 0;
82 mp_size_t i = 0;
83
84#define LMMP_SUBSHL1_STEP(k) \
85 { \
86 mp_limb_t v = numb[i + (k)]; \
87 mp_limb_t lo = (v << 1) | mb; \
88 mb = v >> (LIMB_BITS - 1); \
89 mp_limb_t o = numa[i + (k)]; \
90 mp_limb_t u = o - lo; \
91 mp_limb_t r = u - d; \
92 d = (u > o) + (r > u); \
93 dst[i + (k)] = r; \
94 }
95
96 for (; i + 4 <= n; i += 4) {
101 }
102 for (; i < n; i++) {
104 }
105#undef LMMP_SUBSHL1_STEP
106 return d + mb;
107}
#define LMMP_SUBSHL1_STEP(k)

引用了 lmmp_subshl1_n_(), LMMP_SUBSHL1_STEP, n , 以及 numb.

被这些函数引用 bench_subshl1_n(), lmmp_shlnot_(), lmmp_subshl1_n_(), TEST_CASE(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_tailing_zeros_()

int lmmp_tailing_zeros_ ( mp_limb_t x)

计算一个单精度数(limb)中末尾零的个数

参数
x输入的64位无符号整数
返回
末尾零的位数(范围:0~64)

在文件 tiny.c 第 72 行定义.

72 {
73 if (x == 0) return 64;
74#ifdef __GNUC__
75 return __builtin_ctzll(x);
76#else
77 int n = 0;
78 if ((x & 0x00000000FFFFFFFF) == 0) { n += 32; x >>= 32; }
79 if ((x & 0x000000000000FFFF) == 0) { n += 16; x >>= 16; }
80 if ((x & 0x00000000000000FF) == 0) { n += 8; x >>= 8; }
81 if ((x & 0x000000000000000F) == 0) { n += 4; x >>= 4; }
82 if ((x & 0x0000000000000003) == 0) { n += 2; x >>= 2; }
83 if ((x & 0x0000000000000001) == 0) { n += 1; x >>= 1; }
84 return n;
85#endif
86}

引用了 lmmp_tailing_zeros_ , 以及 n.

◆ lmmp_to_decimal_()

mp_size_t lmmp_to_decimal_ ( char * dst,
mp_srcptr numa,
mp_size_t na )

limb数组转十进制字符串 [numa,na,B] to [dst,return value,10]

参数
dst字符串输出指针
numa输入指针
na输入的 limb 长度
警告
na>=0, dst!=NULL, numa!=NULL
注解
低位digit在数组前端,数值与字符转换一次遍历完成
返回
转换后的字符串长度(零值返回0)

在文件 to_decimal.c 第 147 行定义.

147 {
148 lmmp_param_assert(dst != NULL && numa != NULL);
149 do {
150 if (na == 0)
151 return 0;
152 } while (numa[--na] == 0);
153 ++na;
154
156 return lmmp_to_str_basecase_((mp_byte_t*)dst, numa, na, DEC_BASE, '0');
157
158 // 惰性获取全局幂表
159 mp_size_t digits = lmmp_to_str_len_(numa, na, DEC_BASE);
160 mp_size_t grps = (digits - 1) / lmmp_bases_table[DEC_BASE - 2].digits_in_limb + 1;
161 int ctop;
162 mp_basepow_t* pows = lmmp_dec_pow_table_(grps, &ctop);
163
165 // numa 拷贝空间(多 1 limb 预留规整移位)+ 各层商空间
166 mp_size_t alloc = na + 1;
167 for (int i = 1; i <= ctop; ++i)
168 alloc += pows[i].np + pows[i].zeros + 1;
169 mp_ptr tp = BALLOC_TYPE(alloc, mp_limb_t);
170
171 lmmp_copy(tp, numa, na);
172 digits = lmmp_to_str_divide_((mp_byte_t*)dst, tp, na, pows + ctop, tp + na + 1, '0');
173
175 return digits;
176}
#define TO_STR_BASEPOW_THRESHOLD
mp_size_t lmmp_to_str_len_(mp_srcptr numa, mp_size_t na, int base)
计算转换为字节数组,字节数组需要的缓冲区长度
mp_size_t lmmp_to_str_basecase_(mp_byte_t *dst, mp_srcptr numa, mp_size_t na, int base, mp_byte_t off)
basecase limb 数组转字节串引擎
mp_size_t lmmp_to_str_divide_(mp_byte_t *dst, mp_ptr numa, mp_size_t na, mp_basepow_t *pow, mp_ptr tpq, mp_byte_t off)
分治 limb 数组转字节串引擎

引用了 BALLOC_TYPE, DEC_BASE, lmmp_bases_table, lmmp_copy, lmmp_dec_pow_table_(), lmmp_param_assert, lmmp_to_decimal_(), lmmp_to_str_basecase_(), lmmp_to_str_divide_(), lmmp_to_str_len_(), TEMP_B_DECL, TEMP_B_FREE, TO_STR_BASEPOW_THRESHOLD , 以及 tp.

被这些函数引用 check_decimal_one(), lmmp_to_decimal_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_to_decimal_len_()

mp_size_t lmmp_to_decimal_len_ ( mp_srcptr numa,
mp_size_t na )

计算转换为十进制字符串需要的缓冲区长度

Copyright (C) 2026 HJimmyK (Jericho Knox)

参数
numa输入指针,长度为na
na输入的 limb 长度
警告
na>=0
注解
将会忽略numa的前导零limb,
  1. if (numa!=NULL) 返回的长度可能会多分配一个字节
  2. if (numa==NULL) 返回na个limb长度的数的最大可能字符长度(最坏情况)
返回
十进制字符数的上界

计算转换为十进制字符串需要的缓冲区长度

This file is part of LMMP.

LMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.

SPDX-License-Identifier: LGPL-3.0-or-later

在文件 to_decimal.c 第 32 行定义.

32 {
33 int mslbits = 0;
34 if (numa) {
35 do {
36 if (na == 0)
37 return 1;
38 } while (numa[--na] == 0);
39 mslbits = lmmp_limb_bits_(numa[na]);
40 }
41 return lmmp_mulh_(na * LIMB_BITS + mslbits, lmmp_bases_table[DEC_BASE - 2].inv_lg_base) + 1;
42}

引用了 DEC_BASE, LIMB_BITS, lmmp_bases_table, lmmp_limb_bits_, lmmp_mulh_ , 以及 lmmp_to_decimal_len_().

被这些函数引用 check_decimal_one(), lmmp_to_decimal_len_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_to_hex_()

mp_size_t lmmp_to_hex_ ( char * dst,
mp_srcptr numa,
mp_size_t na,
bool upper )

limb数组转十六进制字符串 [numa,na,B] to [dst,return value,16]

参数
dst字符串输出指针
numa输入指针
na输入的 limb 长度
upper大小写选择:true输出大写字母,false输出小写字母
警告
na>=0, dst!=NULL, numa!=NULL
注解
低位digit(nibble)在数组前端;小端序平台下与字节串布局一致, 输出长度恰好为 lmmp_to_hex_len_(numa,na)
返回
转换后的字符串长度(零值返回0)

在文件 to_hex.c 第 86 行定义.

86 {
87 lmmp_param_assert(dst != NULL && numa != NULL);
88 do {
89 if (na == 0)
90 return 0;
91 } while (numa[--na] == 0);
92 ++na;
93
94 const uint16_t* ptab = upper ? lmmp_hex_pair_upper : lmmp_hex_pair_lower;
95 mp_limb_t top = numa[na - 1];
96 int bits = lmmp_limb_bits_(top);
97 mp_size_t digits = (mp_size_t)((LIMB_BITS * (na - 1) + bits + 3) >> 2);
98
99 char* wp = dst;
100 for (mp_size_t i = 0; i < na - 1; ++i) {
101 mp_limb_t l = numa[i];
102 for (int j = 0; j < 8; ++j) {
103 uint16_t p = ptab[l & 0xff];
104 wp[0] = (char)p; // 低 nibble 字符在前
105 wp[1] = (char)(p >> 8); // 高 nibble 字符
106 wp += 2;
107 l >>= 8;
108 }
109 }
110 while (top >> 4) { // 剩余至少 2 个 nibble
111 uint16_t p = ptab[top & 0xff];
112 wp[0] = (char)p;
113 wp[1] = (char)(p >> 8);
114 wp += 2;
115 top >>= 8;
116 }
117 if (top)
118 *wp++ = (char)ptab[top];
119
120 return digits;
121}
static const uint16_t lmmp_hex_pair_upper[256]
static const uint16_t lmmp_hex_pair_lower[256]
Copyright (C) 2026 HJimmyK (Jericho Knox)

引用了 LIMB_BITS, lmmp_hex_pair_lower, lmmp_hex_pair_upper, lmmp_limb_bits_, lmmp_param_assert , 以及 lmmp_to_hex_().

被这些函数引用 check_hex_one(), lmmp_to_hex_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_to_hex_len_()

mp_size_t lmmp_to_hex_len_ ( mp_srcptr numa,
mp_size_t na )

计算转换为十六进制字符串需要的缓冲区长度

Copyright (C) 2026 HJimmyK (Jericho Knox)

参数
numa输入指针,长度为na
na输入的 limb 长度
警告
na>=0
注解
将会忽略numa的前导零limb,
  1. if (numa!=NULL) 返回精确的十六进制字符长度(零值返回0)
  2. if (numa==NULL) 返回na个limb长度的数的最大可能字符长度(最坏情况)
返回
十六进制字符数

计算转换为十六进制字符串需要的缓冲区长度

This file is part of LMMP.

LMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.

SPDX-License-Identifier: LGPL-3.0-or-later

在文件 to_hex.c 第 28 行定义.

28 {
29 if (numa) {
30 do {
31 if (na == 0)
32 return 0;
33 } while (numa[--na] == 0);
34 // na 现为最高非零 limb 下标
35 return (LIMB_BITS * na + lmmp_limb_bits_(numa[na]) + 3) >> 2;
36 }
37 return na << 4;
38}

引用了 LIMB_BITS, lmmp_limb_bits_ , 以及 lmmp_to_hex_len_().

被这些函数引用 check_hex_one(), lmmp_to_hex_len_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_to_str_()

mp_size_t lmmp_to_str_ ( mp_byte_t * dst,
mp_srcptr numa,
mp_size_t na,
int base )

limb数组转字节数组操作 [numa,na,B] to [dst,return value,base]

参数
dst字节数组结果输出指针
numa输入指针
na输入的 limb 长度
base目标字节数组的进制基数
警告
na>=0, 2<=base<=256, dst!=NULL, numa!=NULL
返回
转换后的字节数组长度

在文件 to_str.c 第 169 行定义.

169 {
170 lmmp_param_assert(base >= 2 && base <= 256);
171 lmmp_param_assert(dst != NULL && numa != NULL);
172 do {
173 if (na == 0)
174 return 0;
175 } while (numa[--na] == 0);
176 ++na;
177
178 mp_size_t digits;
179 if (LMMP_POW2_Q(base)) {
180 mp_limb_t curlimb = numa[na - 1];
181 int cnt = lmmp_bases_table[base - 2].large_base;
182 int bitsh = lmmp_limb_bits_(curlimb);
183 int mask = (1 << cnt) - 1;
184 mp_size_t bits = bitsh + LIMB_BITS * (na - 1);
185 digits = (bits - 1) / cnt + 1;
186 dst += digits;
187 int bitpos = digits * cnt - LIMB_BITS * (na - 1);
188
189 do {
190 while ((bitpos -= cnt) >= 0) {
191 *--dst = curlimb >> bitpos & mask;
192 }
193 if (--na == 0)
194 break;
195 mp_limb_t prevlimb = curlimb << -bitpos;
196 curlimb = numa[na - 1];
197 bitpos += LIMB_BITS;
198 *--dst = (prevlimb | curlimb >> bitpos) & mask;
199 } while (1);
200 } else if (na < TO_STR_BASEPOW_THRESHOLD) {
201 digits = lmmp_to_str_basecase_(dst, numa, na, base, 0);
202 } else {
203 TEMP_DECL;
204 mp_basepow_t powers[LIMB_BITS];
205 mp_size_t exps[LIMB_BITS];
206 mp_limb_t lbase = lmmp_bases_table[base - 2].large_base;
207 mp_size_t digitspl = lmmp_bases_table[base - 2].digits_in_limb;
208 mp_size_t bexp = (lmmp_to_str_len_(numa, na, base) - 1) / digitspl + 1;
209 mp_size_t tzbit = lmmp_tailing_zeros_(lbase);
210 // numa 的拷贝空间,多一个 limb 预留规整化移位所需
211 mp_size_t alloc_size = na + 1;
212 mp_limb_t cy;
213 mp_ptr tp;
214
215 int cpow = 0;
216
217 do {
218 bexp = (bexp + 1) >> 1;
219 exps[cpow] = bexp;
220 ++cpow;
221
222 // we will calculate lbase^(bexp-1) first, and trim it s. t.
223 // it contains at most 2 tailing 0 limb, then multiply it by lbase,
224 // so we need npow limbs to store lbase^bexp
225 mp_size_t npow = lmmp_from_str_len_(0, (bexp - 1) * digitspl + 1, base) + 1;
226
227 // space needed for quotients in recursive calls,
228 // quotients are smaller than lbase^bexp
229 alloc_size += npow + 1;
230
231 if (tzbit) {
232 mp_size_t tzlimb = tzbit * (bexp - 1) / LIMB_BITS;
233 if (tzlimb >= 2)
234 npow -= tzlimb - 2;
235 }
236
237 // space needed for a trimmed npow-limb lbase^bexp and its inverse
238 alloc_size += npow * 2;
239 } while (bexp > 1);
240
241 tp = BALLOC_TYPE(alloc_size, mp_limb_t);
242
243 for (int i = 0; i < 2; ++i) {
244 tp[0] = lbase;
245 powers[i].p = tp;
246 powers[i].np = 1;
247 tp += i + 1;
248 powers[i].zeros = 0;
249 powers[i].digits = digitspl * (i + 1);
250 powers[i].base = base;
251 }
252
253 mp_ptr p = powers[1].p;
254 mp_size_t zeros = 0, np = 1;
255 bexp = 1;
256 for (int i = 2; i < cpow; ++i) {
257 lmmp_sqr_(tp, p, np);
258 bexp *= 2;
259 np *= 2;
260 np -= tp[np - 1] == 0;
261 if (bexp + 1 < exps[cpow - 1 - i]) {
262 cy = lmmp_mul_1_(tp, tp, np, lbase);
263 tp[np] = cy;
264 np += cy != 0;
265 ++bexp;
266 }
267 zeros *= 2;
268 while (tp[0] == 0) {
269 // at most 2 tailing 0 limb here
270 ++zeros;
271 ++tp;
272 --np;
273 }
274 p = tp;
275 powers[i].p = p;
276 powers[i].np = np;
277 powers[i].zeros = zeros;
278 powers[i].digits = digitspl * (bexp + 1);
279 powers[i].base = base;
280 tp += np + 1;
281 }
282
283 for (int i = 1; i < cpow; ++i) {
284 p = powers[i].p;
285 np = powers[i].np;
286 cy = lmmp_mul_1_(p, p, np, lbase);
287 p[np] = cy;
288 np += cy != 0;
289 if (p[0] == 0) {
290 ++powers[i].zeros;
291 ++p;
292 --np;
293 }
294
295 powers[i].p = p;
296 powers[i].np = np;
297
298 // Note: all powers except powers[0] are normalized
299 // ASSERT: powers[0] will be never used in lmmp_to_str_divide_
300 // i.e. TO_STR_DIVIDE_THRESHOLD >= 3
301 int cnt = lmmp_leading_zeros_(p[np - 1]);
302 if ((powers[i].norm_cnt = cnt))
303 lmmp_shl_(p, p, np, cnt);
304
305 if (np < DIV_MULINV_L_THRESHOLD) {
306 // use divs, no need to compute inv
307 powers[i].invp = 0;
308 powers[i].ni = 0;
309 } else {
310 // pre-compute inverse
311 mp_size_t ni = lmmp_div_inv_size_(np + powers[i].zeros, np);
312 lmmp_inv_prediv_(tp, p, np, ni);
313 powers[i].invp = tp;
314 powers[i].ni = ni;
315 tp += ni;
316 }
317 }
318
319 lmmp_copy(tp, numa, na);
320 digits = lmmp_to_str_divide_(dst, tp, na, powers + cpow - 1, tp + na + 1, 0);
321
322 TEMP_FREE;
323 }
324
325 return digits;
326}

引用了 BALLOC_TYPE, mp_basepow_t::base, mp_basepow_t::digits, mp_base_t::digits_in_limb, DIV_MULINV_L_THRESHOLD, mp_basepow_t::invp, mp_base_t::large_base, LIMB_BITS, lmmp_bases_table, lmmp_copy, lmmp_div_inv_size_(), lmmp_from_str_len_(), lmmp_inv_prediv_(), lmmp_leading_zeros_, lmmp_limb_bits_, lmmp_mul_1_(), lmmp_param_assert, LMMP_POW2_Q, lmmp_shl_(), lmmp_sqr_, lmmp_tailing_zeros_, lmmp_to_str_(), lmmp_to_str_basecase_(), lmmp_to_str_divide_(), lmmp_to_str_len_(), mp_basepow_t::ni, mp_basepow_t::np, mp_basepow_t::p, TEMP_DECL, TEMP_FREE, TO_STR_BASEPOW_THRESHOLD, tp , 以及 mp_basepow_t::zeros.

被这些函数引用 big_to_decimal(), check_decimal_one(), check_value(), lmmp_to_str_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_to_str_len_()

mp_size_t lmmp_to_str_len_ ( mp_srcptr numa,
mp_size_t na,
int base )

计算转换为字节数组,字节数组需要的缓冲区长度

Copyright (C) 2026 HJimmyK (Jericho Knox)

参数
numa输入指针,长度为na
na输入的 limb 长度
base目标基数(2~256)
警告
na>=0, 2<=base<=256
注解
将会忽略numa的前导零,
  1. if (numa!=NULL) 返回的长度可能会多分配一个字节
  2. if (numa==NULL) 返回na个limb长度的数的最大可能字节长度(最坏情况)
返回
在指定基数下的位数

计算转换为字节数组,字节数组需要的缓冲区长度

This file is part of LMMP.

LMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.

SPDX-License-Identifier: LGPL-3.0-or-later

在文件 to_str.c 第 32 行定义.

32 {
33 lmmp_param_assert(base >= 2 && base <= 256);
34 int mslbits = 0;
35 if (numa) {
36 do {
37 if (na == 0)
38 return 1;
39 } while (numa[--na] == 0);
40 mslbits = lmmp_limb_bits_(numa[na]);
41 }
42 return lmmp_mulh_(na * LIMB_BITS + mslbits, lmmp_bases_table[base - 2].inv_lg_base) + 1;
43}

引用了 LIMB_BITS, lmmp_bases_table, lmmp_limb_bits_, lmmp_mulh_, lmmp_param_assert , 以及 lmmp_to_str_len_().

被这些函数引用 check_decimal_one(), check_value(), lmmp_to_decimal_(), lmmp_to_str_(), lmmp_to_str_len_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_zero_q_()

int lmmp_zero_q_ ( mp_srcptr p,
mp_size_t n )

判零函数

参数
p指针
n数的 limb 长度
返回
1(全零) / 0(非零)
警告
n>0, p!=NULL
注解
从最高位开始检查,只要有非零位则返回0。

在文件 cmp.c 第 55 行定义.

55 {
57 lmmp_param_assert(p != NULL);
58 /* 同 lmmp_cmp_ 的剥皮结构 */
59 mp_size_t r = n & 3;
60 if (r == 0) r = 4;
61 for (mp_size_t k = 0; k < r; k++) {
62 if (p[n - 1 - k] != 0)
63 return 0;
64 }
65 /* 余段按 4 limb 一组,或折叠非零检测 */
66 for (mp_size_t i = n - r; i != 0;) {
67 i -= 4;
68 if ((p[i] | p[i + 1] | p[i + 2] | p[i + 3]) != 0)
69 return 0;
70 }
71 return 1;
72}

引用了 k, lmmp_param_assert, lmmp_zero_q_() , 以及 n.

被这些函数引用 ipn_lucas_i_(), ipn_mont_mul_small_(), ipn_notrial_i_(), lmmp_gcd_hgcd_(), lmmp_hgcd_core_(), lmmp_invcbrt_newton_(), lmmp_invsqrt_newton_(), lmmp_mont_redc_(), lmmp_mul_fermat_(), lmmp_mul_fermat_cache_(), lmmp_mul_fermat_cache_init_(), lmmp_mul_toom22_(), lmmp_mul_toom32_(), lmmp_mul_toom42_(), lmmp_mul_toom42_cache_init_(), lmmp_mul_toom52_(), lmmp_mul_toom62_(), lmmp_mul_toom62_cache_init_(), lmmp_perfsqr_(), lmmp_powmod_(), lmmp_powmod_odd_(), lmmp_redc_(), lmmp_sqr_fermat_(), lmmp_zero_q_(), mrs_neg_() , 以及 try_div_().

函数调用图:
这是这个函数的调用关系图: