LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
fft_ssa.c 文件参考
#include "lmmpn/fft_ssa.h"
#include "mparam.h"
fft_ssa.c 的引用(Include)关系图:

浏览该文件的源代码.

宏定义

#define _FFT_TABLE_ENTRY(n)
 Copyright (C) 2026 HJimmyK (Jericho Knox)
#define _FFT_TABLE_ENTRY4(n)
#define FFT_TABLE_MAX_ROWS   68

函数

void lmmp_fft_ (fft_memstack *ms, mp_ptr *coef, mp_size_t k, mp_size_t w)
static void lmmp_fft_4_ (fft_memstack *ms, mp_ptr *coef, mp_size_t k, mp_size_t w)
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)
mp_size_t lmmp_fft_best_k_ (mp_size_t n)
 查找对于 m>=n 的模 B^m+1 FFT运算的最优k值
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], b=[coef[wing],ms->lenw+1], n=ms->lenw * LIMB_BITS
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_memstack_ (fft_memstack *ms, mp_size_t size)
 FFT内存栈的分配/释放接口
mp_size_t lmmp_fft_next_size_ (mp_size_t n)
 计算满足 >=n 的最小费马/梅森乘法可行尺寸
void lmmp_fft_shl_coef_ (fft_memstack *ms, mp_ptr *coef, mp_size_t shl)
 对模 2^n+1 的系数执行左移操作
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的循环特性)
void lmmp_ifft_ (fft_memstack *ms, mp_ptr *coef, mp_size_t k, mp_size_t w)
static void lmmp_ifft_4_ (fft_memstack *ms, mp_ptr *coef, mp_size_t k, mp_size_t w)
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_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], b=[coef[wing],ms->lenw+1], n=ms->lenw * LIMB_BITS
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 乘法的结果合并

变量

static const mp_size_t lmmp_fft_table_ [][2]

宏定义说明

◆ _FFT_TABLE_ENTRY

#define _FFT_TABLE_ENTRY ( n)
值:
{((mp_size_t)3 << (2 * (n) - 5)) + 1, (n)}
uint64_t mp_size_t
定义 lmmp.h:93
#define n

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

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

◆ _FFT_TABLE_ENTRY4

#define _FFT_TABLE_ENTRY4 ( n)
值:
#define _FFT_TABLE_ENTRY(n)
Copyright (C) 2026 HJimmyK (Jericho Knox)

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

◆ FFT_TABLE_MAX_ROWS

#define FFT_TABLE_MAX_ROWS   68

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

函数说明

◆ lmmp_fft_()

void lmmp_fft_ ( fft_memstack * ms,
mp_ptr * coef,
mp_size_t k,
mp_size_t w )

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

390 {
391 mp_size_t k1 = k >> 1;
392 k -= k1;
393 mp_size_t Kp = ((mp_size_t)1) << k;
394 mp_size_t Kq = ((mp_size_t)1) << k1;
395
396 for (mp_size_t i = 0; i < Kp; ++i) lmmp_fft_b1_(ms, coef + i, Kp, k1, w, i * w);
397
398 for (mp_size_t i = 0; i < Kq; ++i) lmmp_fft_4_(ms, coef + Kp * i, k, w * Kq);
399}
#define k
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)

引用了 k, lmmp_fft_(), lmmp_fft_4_() , 以及 lmmp_fft_b1_().

被这些函数引用 lmmp_fft_(), lmmp_mul_fermat_(), lmmp_mul_fermat_cache_(), lmmp_mul_fermat_cache_init_(), lmmp_mul_fermat_recurse_(), lmmp_mul_mersenne_cache_(), lmmp_mul_mersenne_cache_init_(), lmmp_mul_mersenne_fft_(), lmmp_sqr_fermat_(), lmmp_sqr_fermat_recurse_() , 以及 lmmp_sqr_mersenne_fft_().

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

◆ lmmp_fft_4_()

void lmmp_fft_4_ ( fft_memstack * ms,
mp_ptr * coef,
mp_size_t k,
mp_size_t w )
static

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

369 {
370 if (k == 1)
371 lmmp_fft_bfy_(ms, coef, 1, 0);
372 else {
373 k -= 2;
374 mp_size_t Kq = ((mp_size_t)1) << k;
375 for (mp_size_t i = 0; i < Kq; ++i) {
376 lmmp_fft_bfy_(ms, coef + i, Kq * 2, i * w);
377 lmmp_fft_bfy_(ms, coef + i + Kq, Kq * 2, (i + Kq) * w);
378 lmmp_fft_bfy_(ms, coef + i, Kq, 2 * i * w);
379 lmmp_fft_bfy_(ms, coef + i + 2 * Kq, Kq, 2 * i * w);
380 }
381 if (k > 0) {
382 lmmp_fft_4_(ms, coef, k, w * 4);
383 lmmp_fft_4_(ms, coef + Kq, k, w * 4);
384 lmmp_fft_4_(ms, coef + 2 * Kq, k, w * 4);
385 lmmp_fft_4_(ms, coef + 3 * Kq, k, w * 4);
386 }
387 }
388}
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],...

引用了 k, lmmp_fft_4_() , 以及 lmmp_fft_bfy_().

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

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

◆ lmmp_fft_b1_()

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

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

348 {
349 if (k == 1)
350 lmmp_fft_bfy_(ms, coef, dis, w0);
351 else {
352 k -= 2;
353 mp_size_t Kq = dis << k;
354 for (mp_size_t i = 0; i < Kq; i += dis) {
355 lmmp_fft_bfy_(ms, coef + i, 2 * Kq, i * w + w0);
356 lmmp_fft_bfy_(ms, coef + i + Kq, 2 * Kq, (i + Kq) * w + w0);
357 lmmp_fft_bfy_(ms, coef + i, Kq, 2 * (i * w + w0));
358 lmmp_fft_bfy_(ms, coef + i + Kq * 2, Kq, 2 * (i * w + w0));
359 }
360 if (k > 0) {
361 lmmp_fft_b1_(ms, coef, dis, k, 4 * w, 4 * w0);
362 lmmp_fft_b1_(ms, coef + Kq, dis, k, 4 * w, 4 * w0);
363 lmmp_fft_b1_(ms, coef + Kq * 2, dis, k, 4 * w, 4 * w0);
364 lmmp_fft_b1_(ms, coef + Kq * 3, dis, k, 4 * w, 4 * w0);
365 }
366 }
367}
#define w0

引用了 k, lmmp_fft_b1_(), lmmp_fft_bfy_() , 以及 w0.

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

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

◆ lmmp_fft_best_k_()

mp_size_t lmmp_fft_best_k_ ( mp_size_t n)

查找对于 m>=n 的模 B^m+1 FFT运算的最优k值

参数
n- 输入的机器字长度
返回
最优的k值

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

89 {
90 mp_size_t k = 0;
91 while (n >= lmmp_fft_table_[k + 1][0]) ++k;
92 return lmmp_fft_table_[k][1];
93}
static const mp_size_t lmmp_fft_table_[][2]

引用了 k, lmmp_fft_best_k_(), lmmp_fft_table_ , 以及 n.

被这些函数引用 lmmp_fft_best_k_(), lmmp_fft_next_size_(), lmmp_mul_fermat_(), lmmp_mul_fermat_cache_init_(), lmmp_mul_fermat_recurse_(), lmmp_mul_mersenne_cache_init_(), lmmp_mul_mersenne_fft_(), lmmp_sqr_fermat_(), lmmp_sqr_fermat_recurse_(), lmmp_sqr_mersenne_fft_() , 以及 mrs_fermat_usable_().

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

◆ lmmp_fft_bfy_()

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], b=[coef[wing],ms->lenw+1], n=ms->lenw * LIMB_BITS

参数
ms内存栈结构体指针
coef系数数组指针数组(coef[0]=a, coef[wing]=b)
wingb的索引
w左移的比特数(0<=w<n)
警告
n = ms->lenw * LIMB_BITS a,b 均已伪归一化(mod 2^n+1) ms->temp_coef 有至少 lenw + 1 个字长

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

205 {
206 mp_ptr numa = coef[0]; // 系数a
207 mp_ptr numb = coef[wing]; // 系数b
208 mp_ptr numc = ms->temp_coef; // 临时数组(存储a-b<<w)
209 mp_size_t shl = w & (LIMB_BITS - 1); // 比特级左移量
210 w /= LIMB_BITS; // 机器字级左移量
211 mp_size_t l = ms->lenw; // 系数长度(机器字)
212
213 mp_slimb_t acyo = 0, scyo = 0;
214 mp_limb_t shlcyo = 0, chp = 0, chn = 0;
215 mp_limb_t out[4]; // fft 融合内核出参 {chp, chn, shlcy2, (acyo<<1)|scyo}
216 if (shl) {
217 lmmp_fft_bfy_fused_(numc, numa, numb, l, w, shl, out);
218 chp = out[0];
219 chn = out[1];
220 shlcyo = out[2];
221 acyo = (mp_slimb_t)(out[3] >> 1);
222 scyo = (mp_slimb_t)(out[3] & 1);
223 } else {
224 for (mp_size_t off = 0; off < l - w; off += PART_SIZE) {
225 mp_size_t cursize = LMMP_MIN(l - w - off, PART_SIZE);
226 scyo = lmmp_sub_nc_(numc + w + off, numa + off, numb + off, cursize, scyo);
227 acyo = lmmp_add_nc_(numa + off, numa + off, numb + off, cursize, acyo);
228 }
229 chn = (mp_limb_t)scyo; // shl=0: ch = 0 - scyo
230 scyo = 0;
231 for (mp_size_t off = l - w; off < l; off += PART_SIZE) {
232 mp_size_t cursize = LMMP_MIN(l - off, PART_SIZE);
233 scyo = lmmp_sub_nc_(numc + off - (l - w), numb + off, numa + off, cursize, scyo);
234 acyo = lmmp_add_nc_(numa + off, numa + off, numb + off, cursize, acyo);
235 }
236 }
237
238 numc[w] += shlcyo; // 左移进位加到numc[w]
239 scyo = -scyo + numb[l] - numa[l]; // 调整借位(包含最高位)
240 acyo += numa[l] + numb[l]; // 调整进位(包含最高位)
241
242 numa[l] = numa[0] < (mp_limb_t)(acyo);
243 lmmp_dec_1(numa, acyo - numa[l]);
244
245 numc[l] = 1;
246 ++chn;
247 if (scyo > 0)
248 lmmp_inc_1(numc + w, (mp_limb_t)scyo << shl);
249 else if (scyo < 0) {
250 if (scyo == -2 && shl == LIMB_BITS - 1)
251 lmmp_dec(numc + w + 1);
252 else
253 lmmp_dec_1(numc + w, (mp_limb_t)(-scyo) << shl);
254 }
255 chp += numc[l];
256
257 if (chn >= chp) {
258 numc[l] = 0;
259 lmmp_inc_1(numc, chn - chp);
260 } else {
261 chp -= chn;
262 numc[l] = numc[0] < chp;
263 lmmp_dec_1(numc, chp - numc[l]);
264 }
265
266 coef[wing] = numc;
267 ms->temp_coef = numb;
268}
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_size_t lenw
mp_limb_t * mp_ptr
定义 lmmp.h:96
int64_t mp_slimb_t
定义 lmmp.h:94
uint64_t mp_limb_t
定义 lmmp.h:92
#define LMMP_MIN(l, o)
返回两个数中的较小值
定义 lmmp.h:450
#define LIMB_BITS
定义 lmmp.h:102
#define PART_SIZE
#define lmmp_dec(p)
减1宏(预期无借位)
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
定义 add_n.c:58
#define lmmp_dec_1(p, dec)
减指定值宏(预期无借位)
#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
定义 sub_n.c:67
#define numb

引用了 fft_memstack::lenw, LIMB_BITS, lmmp_add_nc_(), lmmp_dec, lmmp_dec_1, lmmp_fft_bfy_(), lmmp_fft_bfy_fused_(), lmmp_inc_1, LMMP_MIN, lmmp_sub_nc_(), numb, PART_SIZE , 以及 fft_memstack::temp_coef.

被这些函数引用 lmmp_fft_4_(), lmmp_fft_b1_() , 以及 lmmp_fft_bfy_().

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

◆ lmmp_fft_extract_coef_()

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]

参数
dst输出系数数组(长度lenw+1)
numa输入大数指针
bitoffset起始比特偏移量(>=0)
bits提取的比特数(0 < bits <= LIMB_BITS*lenw)
lenw输出系数的机器字长度
警告
bitoffset>=0, 0<bits<=LIMB_BITS*lenw, sep(dst,numa)

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

129 {
130 mp_size_t shr = bitoffset & (LIMB_BITS - 1), offset = bitoffset / LIMB_BITS;
131
132 mp_size_t lena = (bitoffset + bits - 1) / LIMB_BITS - offset + 1, endp = (bits - 1) / LIMB_BITS;
133
134 lmmp_shr_(dst, numa + offset, lena, shr); // shr=0 时函数内即整段拷贝
135
136 dst[endp] &= LIMB_MAX >> (-bits & (LIMB_BITS - 1));
137
138 lmmp_zero(dst + endp + 1, lenw - endp);
139}
#define lmmp_zero(dst, n)
定义 lmmp.h:476
#define LIMB_MAX
定义 lmmp.h:105
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

引用了 LIMB_BITS, LIMB_MAX, lmmp_fft_extract_coef_(), lmmp_shr_() , 以及 lmmp_zero.

被这些函数引用 lmmp_fft_extract_coef_(), lmmp_mul_fermat_(), lmmp_mul_fermat_cache_(), lmmp_mul_fermat_cache_init_(), lmmp_mul_fermat_recurse_(), lmmp_mul_mersenne_cache_(), lmmp_mul_mersenne_cache_init_(), lmmp_mul_mersenne_fft_(), lmmp_sqr_fermat_(), lmmp_sqr_fermat_recurse_() , 以及 lmmp_sqr_mersenne_fft_().

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

◆ lmmp_fft_memstack_()

void * lmmp_fft_memstack_ ( fft_memstack * ms,
mp_size_t size )

FFT内存栈的分配/释放接口

参数
ms内存栈结构体栈帧
size分配大小(字节),size=0表示释放当前层内存
返回
分配成功:返回mp_ptr*;释放:返回0

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

103 {
104 if (size) {
105 if (++ms->tempdepth > ms->maxdepth) {
106#if LMMP_DEBUG_MEMORY_CHECK == 1
107 if (ms->maxdepth + 1 >= FFT_MEMSTACK_DEPTH) {
108 lmmp_abort(LMMP_ERROR_OUT_OF_BOUNDS, "fft memstack depth overflow", __func__, __LINE__);
109 }
110#endif
111 ms->mem[++ms->maxdepth] = lmmp_alloc(size);
112 ms->memsize[ms->maxdepth] = size;
113 }
114#if LMMP_DEBUG_MEMORY_CHECK == 1
115 if (ms->memsize[ms->tempdepth] != size) {
116 lmmp_abort(LMMP_ERROR_OUT_OF_BOUNDS, "fft memstack size mismatch at same depth", __func__, __LINE__);
117 }
118#endif
119 return ms->mem[ms->tempdepth];
120 } else {
121 if (--ms->tempdepth < 0) {
122 for (mp_size_t i = 0; i <= (mp_size_t)(ms->maxdepth); ++i) lmmp_free(ms->mem[i]);
123 ms->maxdepth = -1;
124 }
125 return 0;
126 }
127}
#define FFT_MEMSTACK_DEPTH
Copyright (C) 2026 HJimmyK (Jericho Knox)
mp_ssize_t maxdepth
mp_size_t memsize[16]
void * mem[16]
mp_ssize_t tempdepth
void * lmmp_alloc(size_t size)
内存分配函数(调用lmmp_heap_alloc_fn)
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
定义 lmmp.h:287

引用了 FFT_MEMSTACK_DEPTH, lmmp_abort(), lmmp_alloc(), LMMP_ERROR_OUT_OF_BOUNDS, lmmp_fft_memstack_(), lmmp_free(), fft_memstack::maxdepth, fft_memstack::mem, fft_memstack::memsize , 以及 fft_memstack::tempdepth.

被这些函数引用 lmmp_fft_gr_cache_free_(), lmmp_fft_memstack_(), lmmp_mul_fermat_(), lmmp_mul_fermat_cache_(), lmmp_mul_fermat_cache_init_(), lmmp_mul_fermat_recurse_(), lmmp_mul_mersenne_cache_(), lmmp_mul_mersenne_cache_init_(), lmmp_mul_mersenne_fft_(), lmmp_sqr_fermat_(), lmmp_sqr_fermat_recurse_() , 以及 lmmp_sqr_mersenne_fft_().

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

◆ 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_fft_shl_coef_()

void lmmp_fft_shl_coef_ ( fft_memstack * ms,
mp_ptr * coef,
mp_size_t shl )

对模 2^n+1 的系数执行左移操作

参数
ms内存栈结构体指针
coef输入输出系数数组指针(指针的指针,用于交换内存)
shl左移的比特数(0<shl<2*n)
警告
n = ms->lenw * LIMB_BITS *coef 已伪归一化(mod 2^n+1) ms->temp_coef 至少有 lenw+1 个机器字

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

141 {
142 mp_size_t l = ms->lenw; // 系数的机器字长度
143 mp_size_t w = shl / LIMB_BITS; // 左移的机器字数量
144 shl &= LIMB_BITS - 1; // 剩余的比特偏移(0~LIMB_BITS-1)
145 mp_ptr src = *coef; // 源系数数组
146 mp_ptr dst = ms->temp_coef; // 目标临时数组
147 mp_limb_t cc, rd; // 进位变量(cc=carry, rd=read)
148
149 if (w >= l) {
150 w -= l;
151 if (shl) {
152 lmmp_shl_(dst, src + l - w, w + 1, shl);
153 rd = dst[w];
154 cc = lmmp_shlnot_(dst + w, src, l - w, shl);
155 } else {
156 if (w)
157 lmmp_copy(dst, src + l - w, w);
158 rd = src[l];
159 lmmp_not_(dst + w, src, l - w);
160 cc = 0;
161 }
162 dst[l] = 0;
163 ++cc;
164 lmmp_inc_1(dst, cc);
165
166 if (++rd == 0)
167 lmmp_inc(dst + w + 1);
168 else
169 lmmp_inc_1(dst + w, rd);
170 } else {
171 if (shl) {
172 lmmp_shlnot_(dst, src + l - w, w + 1, shl);
173 rd = ~dst[w];
174 cc = lmmp_shl_(dst + w, src, l - w, shl);
175 } else {
176 if (w)
177 lmmp_not_(dst, src + l - w, w);
178 rd = src[l];
179
180 lmmp_copy(dst + w, src, l - w);
181 cc = 0;
182 }
183 dst[l] = 2;
184 lmmp_inc_1(dst, 3);
185 lmmp_dec_1(dst, cc);
186
187 if (++rd == 0)
188 lmmp_dec(dst + w + 1);
189 else
190 lmmp_dec_1(dst + w, rd);
191
192 cc = dst[l];
193 dst[l] = dst[0] < cc;
194 lmmp_dec_1(dst, cc - dst[l]);
195 }
196
197 ms->temp_coef = src;
198 *coef = dst;
199}
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
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
#define lmmp_inc(p)
加1宏(预期无进位)
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
void lmmp_not_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
按位取反操作 [dst,na] = ~[numa,na] (对每个limb执行按位非操作)
定义 not.c:26

引用了 fft_memstack::lenw, LIMB_BITS, lmmp_copy, lmmp_dec, lmmp_dec_1, lmmp_fft_shl_coef_(), lmmp_inc, lmmp_inc_1, lmmp_not_(), lmmp_shl_(), lmmp_shlnot_() , 以及 fft_memstack::temp_coef.

被这些函数引用 lmmp_fft_shl_coef_(), lmmp_fft_shr_coef_(), lmmp_mul_fermat_(), lmmp_mul_fermat_cache_(), lmmp_mul_fermat_cache_init_(), lmmp_mul_fermat_recurse_(), lmmp_sqr_fermat_() , 以及 lmmp_sqr_fermat_recurse_().

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

◆ lmmp_fft_shr_coef_()

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的循环特性)

参数
ms内存栈结构体指针
coef输入输出系数数组指针
shr右移的比特数(0 < shr < 2*n)

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

201 {
202 lmmp_fft_shl_coef_(ms, coef, 2 * ms->lenw * LIMB_BITS - shr);
203}
void lmmp_fft_shl_coef_(fft_memstack *ms, mp_ptr *coef, mp_size_t shl)
对模 2^n+1 的系数执行左移操作

引用了 fft_memstack::lenw, LIMB_BITS, lmmp_fft_shl_coef_() , 以及 lmmp_fft_shr_coef_().

被这些函数引用 lmmp_fft_shr_coef_(), lmmp_mul_fermat_recombine_(), lmmp_mul_mersenne_cache_(), lmmp_mul_mersenne_cache_init_(), lmmp_mul_mersenne_fft_() , 以及 lmmp_sqr_mersenne_fft_().

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

◆ lmmp_ifft_()

void lmmp_ifft_ ( fft_memstack * ms,
mp_ptr * coef,
mp_size_t k,
mp_size_t w )

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

443 {
444 mp_size_t k1 = k >> 1;
445 k -= k1;
446 mp_size_t Kp = ((mp_size_t)1) << k;
447 mp_size_t Kq = ((mp_size_t)1) << k1;
448
449 for (mp_size_t i = 0; i < Kq; ++i) lmmp_ifft_4_(ms, coef + Kp * i, k, w * Kq);
450
451 for (mp_size_t i = 0; i < Kp; ++i) lmmp_ifft_b1_(ms, coef + i, Kp, k1, w, i * w);
452}
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)
static void lmmp_ifft_4_(fft_memstack *ms, mp_ptr *coef, mp_size_t k, mp_size_t w)

引用了 k, lmmp_ifft_(), lmmp_ifft_4_() , 以及 lmmp_ifft_b1_().

被这些函数引用 lmmp_ifft_(), lmmp_mul_fermat_(), lmmp_mul_fermat_cache_(), lmmp_mul_fermat_cache_init_(), lmmp_mul_fermat_recurse_(), lmmp_mul_mersenne_cache_(), lmmp_mul_mersenne_cache_init_(), lmmp_mul_mersenne_fft_(), lmmp_sqr_fermat_(), lmmp_sqr_fermat_recurse_() , 以及 lmmp_sqr_mersenne_fft_().

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

◆ lmmp_ifft_4_()

void lmmp_ifft_4_ ( fft_memstack * ms,
mp_ptr * coef,
mp_size_t k,
mp_size_t w )
static

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

422 {
423 if (k == 1)
424 lmmp_ifft_bfy_(ms, coef, 1, 0);
425 else {
426 k -= 2;
427 mp_size_t Kq = ((mp_size_t)1) << k;
428 if (k > 0) {
429 lmmp_ifft_4_(ms, coef, k, w * 4);
430 lmmp_ifft_4_(ms, coef + Kq, k, w * 4);
431 lmmp_ifft_4_(ms, coef + 2 * Kq, k, w * 4);
432 lmmp_ifft_4_(ms, coef + 3 * Kq, k, w * 4);
433 }
434 for (mp_size_t i = 0; i < Kq; ++i) {
435 lmmp_ifft_bfy_(ms, coef + i, Kq, 2 * i * w);
436 lmmp_ifft_bfy_(ms, coef + i + 2 * Kq, Kq, 2 * i * w);
437 lmmp_ifft_bfy_(ms, coef + i, Kq * 2, i * w);
438 lmmp_ifft_bfy_(ms, coef + i + Kq, Kq * 2, (i + Kq) * w);
439 }
440 }
441}
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],...

引用了 k, lmmp_ifft_4_() , 以及 lmmp_ifft_bfy_().

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

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

◆ lmmp_ifft_b1_()

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 )
static

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

401 {
402 if (k == 1)
403 lmmp_ifft_bfy_(ms, coef, dis, w0);
404 else {
405 k -= 2;
406 mp_size_t Kq = dis << k;
407 if (k > 0) {
408 lmmp_ifft_b1_(ms, coef, dis, k, 4 * w, 4 * w0);
409 lmmp_ifft_b1_(ms, coef + Kq, dis, k, 4 * w, 4 * w0);
410 lmmp_ifft_b1_(ms, coef + Kq * 2, dis, k, 4 * w, 4 * w0);
411 lmmp_ifft_b1_(ms, coef + Kq * 3, dis, k, 4 * w, 4 * w0);
412 }
413 for (mp_size_t i = 0; i < Kq; i += dis) {
414 lmmp_ifft_bfy_(ms, coef + i, Kq, 2 * (i * w + w0));
415 lmmp_ifft_bfy_(ms, coef + i + Kq * 2, Kq, 2 * (i * w + w0));
416 lmmp_ifft_bfy_(ms, coef + i, 2 * Kq, i * w + w0);
417 lmmp_ifft_bfy_(ms, coef + i + Kq, 2 * Kq, (i + Kq) * w + w0);
418 }
419 }
420}

引用了 k, lmmp_ifft_b1_(), lmmp_ifft_bfy_() , 以及 w0.

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

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

◆ lmmp_ifft_bfy_()

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], b=[coef[wing],ms->lenw+1], n=ms->lenw * LIMB_BITS

参数
ms内存栈结构体指针
coef系数数组指针数组(coef[0]=a, coef[wing]=b)
wingb的索引
w左移的比特数(0<=w<n)
警告
n = ms->lenw * LIMB_BITS a,b 均已伪归一化(mod 2^n+1) ms->temp_coef 有至少 lenw + 1 个字长

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

270 {
271 mp_ptr numa = coef[0];
272 mp_ptr numb = coef[wing];
273 mp_ptr numc = ms->temp_coef;
274 mp_size_t shr = w & (LIMB_BITS - 1);
275 w /= LIMB_BITS;
276 mp_size_t l = ms->lenw;
277
278 mp_slimb_t bcyo = 0, acyo = 0, ah;
279 mp_limb_t shrcyo = shr ? numb[0] << (LIMB_BITS - shr) : 0;
280 mp_limb_t kc; // ifft 融合内核的打包进位 (acyo<<1)|bcyo
281 if (shr) {
282 kc = lmmp_ifft_bfy_fused_(numc, numa, numb, l, w, shr);
283 acyo = (mp_slimb_t)(kc >> 1);
284 bcyo = (mp_slimb_t)(kc & 1);
285 } else {
286 for (mp_size_t off = l - w; off < l; off += PART_SIZE) {
287 mp_size_t cursize = LMMP_MIN(l - off, PART_SIZE);
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);
290 }
291 for (mp_size_t off = 0; off < l - w; off += PART_SIZE) {
292 mp_size_t cursize = LMMP_MIN(l - w - off, PART_SIZE);
293 bcyo = lmmp_sub_nc_(numc + off, numa + off, numb + w + off, cursize, bcyo);
294 acyo = lmmp_add_nc_(numa + off, numa + off, numb + w + off, cursize, acyo);
295 }
296 }
297
298 acyo += numb[l] >> shr;
299 bcyo = -bcyo - (numb[l] >> shr);
300
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;
305
306 ah = numa[l];
307
308 numa[l] += 1;
309 if (w == 0)
310 numa[l] += acyo;
311 else {
312 if (acyo < 0)
313 lmmp_dec(numa + l - w);
314 else
315 lmmp_inc_1(numa + l - w, acyo);
316 }
317 acyo = numa[l] - 1;
318 if (acyo < 0) {
319 numa[l] = 0;
320 lmmp_inc(numa);
321 } else {
322 numa[l] = numa[0] < (mp_limb_t)acyo;
323 lmmp_dec_1(numa, acyo - numa[l]);
324 }
325
326 numc[l] = ah + 2;
327 if (w == 0)
328 numc[l] += bcyo;
329 else {
330 if (bcyo > 0)
331 lmmp_inc(numc + l - w);
332 else
333 lmmp_dec_1(numc + l - w, -bcyo);
334 }
335 bcyo = numc[l] - 2;
336 if (bcyo <= 0) {
337 numc[l] = 0;
338 lmmp_inc_1(numc, -bcyo);
339 } else {
340 numc[l] = numc[0] < (mp_limb_t)bcyo;
341 lmmp_dec_1(numc, bcyo - numc[l]);
342 }
343
344 coef[wing] = numc;
345 ms->temp_coef = numb;
346}
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)

引用了 fft_memstack::lenw, LIMB_BITS, lmmp_add_nc_(), lmmp_dec, lmmp_dec_1, lmmp_ifft_bfy_(), lmmp_ifft_bfy_fused_(), lmmp_inc, lmmp_inc_1, LMMP_MIN, lmmp_sub_nc_(), numb, PART_SIZE , 以及 fft_memstack::temp_coef.

被这些函数引用 lmmp_ifft_4_(), lmmp_ifft_b1_() , 以及 lmmp_ifft_bfy_().

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

◆ lmmp_mul_fermat_recombine_()

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 乘法的结果合并

参数
ms内存栈结构体指针
dst输出结果数组
pfcaFFT系数数组指针数组
KFFT块数(2^k)
kFFT层数
n系数总比特数
M每个块的比特数
rn结果长度(机器字)

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

463 {
464 mp_size_t rhead = 0, nlen = ms->lenw + 1;
465 mp_slimb_t borrow = 0, maxc = 0;
466
467 for (mp_size_t i = 0; i < K; ++i) {
468 lmmp_fft_shr_coef_(ms, pfca + i, (i * n >> k) + k);
469 mp_ptr nums = pfca[i];
470
471 if (nums[nlen - 1]) {
472 lmmp_dec(nums);
473 --nums[nlen - 1];
474 }
475 if (nums[nlen - 1] == 0 && nums[nlen - 2] >> (LIMB_BITS - 1)) {
476 lmmp_dec(nums);
477 --nums[nlen - 1];
478 }
479
480 if (borrow) {
481 mp_size_t brshift = borrow - 1 + n - M;
482 mp_size_t bshl = brshift & (LIMB_BITS - 1);
483 brshift /= LIMB_BITS;
484 --nums[nlen - 1];
485 lmmp_dec_1(nums + brshift, (mp_limb_t)1 << bshl);
486 ++nums[nlen - 1];
487 }
488 borrow = -nums[nlen - 1];
489 nums[nlen - 1] = 0;
490
491 mp_size_t roffset = i * M;
492 mp_size_t shl = roffset & (LIMB_BITS - 1);
493 roffset /= LIMB_BITS;
494
495 if (shl)
496 lmmp_shl_(nums, nums, nlen, shl);
497
498 if (i == 0) {
499 // 重组先写入 [dst,rn],最高 limb 在处理进位时写入。
500 rhead = LMMP_MIN(nlen, rn);
501 lmmp_copy(dst, nums, rhead);
502 } else if (roffset + nlen <= rn) {
503 lmmp_add_(dst + roffset, nums, nlen, dst + roffset, rhead - roffset);
504 rhead = roffset + nlen;
505 } else {
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);
508 rhead = rn;
509 }
510 }
511
512 if (borrow) {
513 mp_size_t cyshift = borrow - 1 + n - M;
514 mp_size_t cshl = cyshift & (LIMB_BITS - 1);
515 cyshift /= LIMB_BITS;
516 maxc += lmmp_add_1_(dst + cyshift, dst + cyshift, rn - cyshift, (mp_limb_t)1 << cshl);
517 }
518
519 if (maxc > 0) {
520 dst[rn] = dst[0] < (mp_limb_t)maxc;
521 lmmp_dec_1(dst, maxc - dst[rn]);
522 } else {
523 dst[rn] = 0;
524 lmmp_inc_1(dst, -maxc);
525 }
526}
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]
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
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]

引用了 k, fft_memstack::lenw, LIMB_BITS, lmmp_add_(), lmmp_add_1_(), lmmp_copy, lmmp_dec, lmmp_dec_1, lmmp_fft_shr_coef_(), lmmp_inc_1, LMMP_MIN, lmmp_mul_fermat_recombine_(), lmmp_shl_(), lmmp_sub_() , 以及 n.

被这些函数引用 lmmp_mul_fermat_(), lmmp_mul_fermat_cache_(), lmmp_mul_fermat_cache_init_(), lmmp_mul_fermat_recombine_(), lmmp_mul_fermat_recurse_(), lmmp_sqr_fermat_() , 以及 lmmp_sqr_fermat_recurse_().

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

变量说明

◆ lmmp_fft_table_

const mp_size_t lmmp_fft_table_[][2]
static

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

被这些函数引用 lmmp_fft_best_k_().