29#define _FFT_TABLE_ENTRY(n) {((mp_size_t)3 << (2 * (n) - 5)) + 1, (n)}
30#define _FFT_TABLE_ENTRY4(n) \
31 _FFT_TABLE_ENTRY(n), _FFT_TABLE_ENTRY((n) + 1), _FFT_TABLE_ENTRY((n) + 2), _FFT_TABLE_ENTRY((n) + 3)
34#define FFT_TABLE_MAX_ROWS 68
99 n = (((
n - 1) >>
k) + 1) <<
k;
106#if LMMP_DEBUG_MEMORY_CHECK == 1
114#if LMMP_DEBUG_MEMORY_CHECK == 1
134 lmmp_shr_(dst, numa + offset, lena, shr);
174 cc =
lmmp_shl_(dst + w, src, l - w, shl);
193 dst[l] = dst[0] < cc;
233 scyo =
lmmp_sub_nc_(numc + off - (l - w),
numb + off, numa + off, cursize, scyo);
239 scyo = -scyo +
numb[l] - numa[l];
240 acyo += numa[l] +
numb[l];
262 numc[l] = numc[0] < chp;
288 bcyo =
lmmp_add_nc_(numc + off, numa + off,
numb + off - (l - w), cursize, bcyo);
289 acyo =
lmmp_sub_nc_(numa + off, numa + off,
numb + off - (l - w), cursize, acyo);
298 acyo +=
numb[l] >> shr;
299 bcyo = -bcyo - (
numb[l] >> shr);
301 acyo -= numa[l - w - 1] < shrcyo;
302 numa[l - w - 1] -= shrcyo;
303 numc[l - w - 1] += shrcyo;
304 bcyo += numc[l - w - 1] < shrcyo;
354 for (
mp_size_t i = 0; i < Kq; i += dis) {
413 for (
mp_size_t i = 0; i < Kq; i += dis) {
471 if (nums[nlen - 1]) {
475 if (nums[nlen - 1] == 0 && nums[nlen - 2] >> (
LIMB_BITS - 1)) {
488 borrow = -nums[nlen - 1];
502 }
else if (roffset + nlen <= rn) {
503 lmmp_add_(dst + roffset, nums, nlen, dst + roffset, rhead - roffset);
504 rhead = roffset + nlen;
506 maxc +=
lmmp_add_(dst + roffset, nums, rn - roffset, dst + roffset, rhead - roffset);
507 maxc -=
lmmp_sub_(dst, dst, rn, nums + rn - roffset, nlen + roffset - rn);
void lmmp_fft_bfy_fused_(mp_ptr numc, mp_ptr numa, mp_ptr numb, mp_size_t l, mp_size_t w, mp_size_t shl, mp_limb_t *out)
fft 蝶形数据面融合内核(两段扫描 + 中点 ch 分解,单次调用完成)
mp_limb_t lmmp_ifft_bfy_fused_(mp_ptr numc, mp_ptr numa, mp_ptr numb, mp_size_t l, mp_size_t w, mp_size_t shr)
Copyright (C) 2026 HJimmyK (Jericho Knox)
mp_size_t lmmp_fft_best_k_(mp_size_t n)
查找对于 m>=n 的模 B^m+1 FFT运算的最优k值
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的循环特性)
#define _FFT_TABLE_ENTRY4(n)
void lmmp_fft_shl_coef_(fft_memstack *ms, mp_ptr *coef, mp_size_t shl)
对模 2^n+1 的系数执行左移操作
static void lmmp_ifft_b1_(fft_memstack *ms, mp_ptr *coef, mp_size_t dis, mp_size_t k, mp_size_t w, mp_size_t w0)
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]
static void lmmp_ifft_4_(fft_memstack *ms, mp_ptr *coef, mp_size_t k, mp_size_t w)
static const mp_size_t lmmp_fft_table_[][2]
void lmmp_fft_(fft_memstack *ms, mp_ptr *coef, mp_size_t k, mp_size_t w)
void lmmp_fft_bfy_(fft_memstack *ms, mp_ptr *coef, mp_size_t wing, mp_size_t w)
FFT蝶形运算(Butterfly Operation) (a,b) = (a + b, (a-b) << w ) mod 2^n+1 a=[coef[0],ms->lenw+1],...
static void lmmp_fft_b1_(fft_memstack *ms, mp_ptr *coef, mp_size_t dis, mp_size_t k, mp_size_t w, mp_size_t w0)
static void lmmp_fft_4_(fft_memstack *ms, mp_ptr *coef, mp_size_t k, mp_size_t w)
void lmmp_ifft_bfy_(fft_memstack *ms, mp_ptr *coef, mp_size_t wing, mp_size_t w)
FFT蝶形运算(Butterfly Operation) (a,b) = (a+(b>>w), a-(b>>w)) mod 2^n+1 a=[coef[0],ms->lenw+1],...
#define FFT_MEMSTACK_DEPTH
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define lmmp_copy(dst, src, n)
#define lmmp_zero(dst, n)
#define lmmp_debug_assert(x)
void * lmmp_alloc(size_t size)
内存分配函数(调用lmmp_heap_alloc_fn)
const mp_limb_t * mp_srcptr
void lmmp_abort(lmmp_error_t type, const char *msg, const char *func, int line)
LMMP 全局退出函数,内部错误或断言失败时调用,若设置了全局退出函数,则会调用该函数,否则会调用默认的退出函数。
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
@ LMMP_ERROR_OUT_OF_BOUNDS
#define LMMP_MIN(l, o)
返回两个数中的较小值
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
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]
#define lmmp_dec(p)
减1宏(预期无借位)
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
#define lmmp_inc(p)
加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_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_size_t lmmp_fft_next_size_(mp_size_t n)
计算满足 >=n 的最小费马/梅森乘法可行尺寸
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
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]
#define lmmp_dec_1(p, dec)
减指定值宏(预期无借位)
void lmmp_not_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
按位取反操作 [dst,na] = ~[numa,na] (对每个limb执行按位非操作)
#define lmmp_inc_1(p, inc)
加指定值宏(预期无进位)
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