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

浏览该文件的源代码.

函数

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_fermat_cache_ (mp_ptr dst, mp_srcptr numa, fft_gr_cache *ctx)
 费马数模乘法(缓存版) [dst,rn+1]=[numa,na]*[numb,nb] mod B^rn+1
void lmmp_mul_fermat_cache_init_ (mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, fft_gr_cache *ctx)
 费马数模乘法(缓存版) [dst,rn+1]=[numa,na]*[numb,nb] mod B^rn+1 第二个操作数将被缓存
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)
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_cache_ (mp_ptr dst, mp_srcptr numa, fft_cache *ctx)
 FFT乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_mul_fft_cache_init_ (mp_ptr dst, mp_size_t hn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, fft_cache *ctx)
 FFT乘法运算 [dst,na+nb] = [numa,na] * [numb,nb] 第二个操作数将被缓存
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_ 的后半):两域残差 → 精确积
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_ 的前半)
void lmmp_mul_fft_unbalance_ (mp_ptr restrict dst, mp_srcptr restrict numa, mp_size_t na, mp_srcptr restrict numb, mp_size_t nb)
void lmmp_mul_mersenne_cache_ (mp_ptr dst, mp_srcptr numa, fft_gr_cache *ctx)
 梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1
void lmmp_mul_mersenne_cache_init_ (mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, fft_gr_cache *ctx)
 梅森数模乘法 [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_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}
#define k
mp_size_t lmmp_fft_best_k_(mp_size_t n)
查找对于 m>=n 的模 B^m+1 FFT运算的最优k值
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
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_zero(dst, n)
定义 lmmp.h:476
uint64_t mp_size_t
定义 lmmp.h:93
#define lmmp_debug_assert(x)
定义 lmmp.h:498
#define LIMB_BYTES
定义 lmmp.h:103
#define LMMP_MIN(l, o)
返回两个数中的较小值
定义 lmmp.h:450
#define LIMB_BITS
定义 lmmp.h:102
#define lmmp_dec(p)
减1宏(预期无借位)
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)
#define numb
#define n

引用了 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_fermat_cache_()

void lmmp_mul_fermat_cache_ ( mp_ptr dst,
mp_srcptr numa,
fft_gr_cache * ctx )

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

参数
dst输出结果缓冲区,长度为 lmmp_mul_fermat_cache_init_()函数中输入参数的 rn+1
numa第一个输入操作数,长度为 lmmp_mul_fermat_cache_init_()函数中输入参数的 na
ctx费马数模乘法缓存上下文
警告
eqsep(dst,numa), 0<=[numa,na]<2*B^rn
注解
使用被缓存的[numb,nb]作为第二个乘数,numb可以在lmmp_mul_fermat_cache_()函数前被释放,不会影响后续计算
返回
无返回值,结果存储在dst中

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

367 {
368 lmmp_param_assert(dst != NULL && numa != NULL);
369 lmmp_param_assert(ctx != NULL);
370 fft_memstack* bmsr = &ctx->bmsr;
371 fft_memstack* amsr = &ctx->amsr;
372
373 amsr->maxdepth = -1;
374 amsr->tempdepth = -1;
375 amsr->temp_coef = (mp_ptr)lmmp_fft_memstack_(amsr, ctx->a_size);
376
377 bmsr->temp_coef = ctx->temp_coefb;
378 mp_ptr* pfca = (mp_ptr*)(amsr->temp_coef + ctx->nlen);
379 mp_ptr* pfcb = (mp_ptr*)(bmsr->temp_coef + ctx->nlen);
380
381 mp_size_t narest = ctx->na * LIMB_BITS;
382
383 for (mp_size_t i = 0; i < ctx->K; ++i) {
384 mp_size_t coeflen;
385 pfca[i] = (mp_ptr)(pfca + ctx->K) + i * ctx->nlen;
386 if (narest > 0) {
387 coeflen = ctx->M + (i == ctx->K - 1);
388 coeflen = LMMP_MIN(narest, coeflen);
389 narest -= coeflen;
390 lmmp_fft_extract_coef_(pfca[i], numa, ctx->M * i, coeflen, amsr->lenw);
391 if (i > 0)
392 lmmp_fft_shl_coef_(amsr, pfca + i, i * ctx->n >> ctx->k);
393 } else {
394 lmmp_zero(pfca[i], ctx->nlen);
395 }
396 }
397 lmmp_fft_(amsr, pfca, ctx->k, ctx->n >> (ctx->k - 1));
398
399 lmmp_mul_fermat_recurse_(amsr, pfca, pfcb, ctx->K);
400
401 lmmp_ifft_(amsr, pfca, ctx->k, ctx->n >> (ctx->k - 1));
402
403 lmmp_mul_fermat_recombine_(amsr, dst, pfca, ctx->K, ctx->k, ctx->n, ctx->M, ctx->rn);
404
405 if (dst[ctx->rn] && !lmmp_zero_q_(dst, ctx->rn)) {
406 dst[ctx->rn] = 0;
407 lmmp_dec(dst);
408 }
409 lmmp_fft_memstack_(amsr, 0);
410}
#define lmmp_param_assert(x)
定义 lmmp.h:509
fft_memstack bmsr
mp_size_t a_size
fft_memstack amsr

引用了 fft_gr_cache::a_size, fft_gr_cache::amsr, fft_gr_cache::bmsr, fft_gr_cache::K, fft_gr_cache::k, fft_memstack::lenw, LIMB_BITS, lmmp_dec, lmmp_fft_(), lmmp_fft_extract_coef_(), lmmp_fft_memstack_(), lmmp_fft_shl_coef_(), lmmp_ifft_(), LMMP_MIN, lmmp_mul_fermat_cache_(), lmmp_mul_fermat_recombine_(), lmmp_mul_fermat_recurse_(), lmmp_param_assert, lmmp_zero, lmmp_zero_q_(), fft_gr_cache::M, fft_memstack::maxdepth, fft_gr_cache::n, fft_gr_cache::na, fft_gr_cache::nlen, fft_gr_cache::rn, fft_memstack::temp_coef, fft_gr_cache::temp_coefb , 以及 fft_memstack::tempdepth.

被这些函数引用 lmmp_mul_fermat_cache_(), lmmp_mul_fft_cache_(), lmmp_mullo_fft_cache_() , 以及 TEST_CASE().

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

◆ lmmp_mul_fermat_cache_init_()

void lmmp_mul_fermat_cache_init_ ( mp_ptr dst,
mp_size_t rn,
mp_srcptr numa,
mp_size_t na,
mp_srcptr numb,
mp_size_t nb,
fft_gr_cache * ctx )

费马数模乘法(缓存版) [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 长度
ctx费马数模乘法缓存上下文
警告
eqsep(dst,[numa|numb]), 0<=[numa,na]<2*B^rn, 0<=[numb,nb]<2*B^rn, lmmp_fft_next_size_(rn)==rn
注解
[numb,nb]将会被缓存,第二个乘数始终保持不变时,在后续计算中可以调用lmmp_mul_fermat_cache_()函数节省40的计算时间 numb可以在lmmp_mul_fermat_cache_()函数前被释放,不会影响后续计算
返回
无返回值,结果存储在dst中

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

287 {
288 lmmp_param_assert(na > 0 && nb > 0);
289 lmmp_param_assert(dst != NULL && numa != NULL && numb != NULL);
290 lmmp_param_assert(ctx != NULL);
291 ctx->na = na;
292 ctx->rn = rn;
293 ctx->N = rn * LIMB_BITS;
294 ctx->k = lmmp_fft_best_k_(rn);
295 ctx->K = ((mp_size_t)1) << ctx->k;
296 lmmp_debug_assert(!(ctx->N & (ctx->K - 1)));
297 ctx->M = ctx->N >> ctx->k;
298 ctx->n = 2 * ctx->M + ctx->k + 2;
299 ctx->n = (ctx->n + LIMB_BITS - 1) & (-LIMB_BITS);
300 ctx->n = (((ctx->n - 1) >> ctx->k) + 1) << ctx->k;
301
302 fft_memstack* bmsr = &ctx->bmsr;
303 fft_memstack* amsr = &ctx->amsr;
304 amsr->maxdepth = -1;
305 amsr->tempdepth = -1;
306 amsr->lenw = ctx->n / LIMB_BITS;
307 ctx->nlen = amsr->lenw + 1;
308 ctx->a_size = (((ctx->nlen + 1) << (ctx->k)) + ctx->nlen) * LIMB_BYTES;
309 amsr->temp_coef = (mp_ptr)lmmp_fft_memstack_(amsr, ctx->a_size);
310
311 mp_ptr* pfca = (mp_ptr*)(amsr->temp_coef + ctx->nlen);
312 mp_ptr* pfcb = NULL;
313
314 bmsr->maxdepth = -1;
315 bmsr->tempdepth = -1;
316 bmsr->lenw = ctx->n / LIMB_BITS;
317 bmsr->temp_coef = (mp_ptr)lmmp_fft_memstack_(bmsr, ctx->a_size);
318 ctx->temp_coefb = bmsr->temp_coef;
319 pfcb = (mp_ptr*)(bmsr->temp_coef + ctx->nlen);
320
321 mp_size_t narest = na * LIMB_BITS, nbrest = nb * LIMB_BITS;
322 for (mp_size_t i = 0; i < ctx->K; ++i) {
323 mp_size_t coeflen;
324 pfca[i] = (mp_ptr)(pfca + ctx->K) + i * ctx->nlen;
325 if (narest > 0) {
326 coeflen = ctx->M + (i == ctx->K - 1);
327 coeflen = LMMP_MIN(narest, coeflen);
328 narest -= coeflen;
329 lmmp_fft_extract_coef_(pfca[i], numa, ctx->M * i, coeflen, amsr->lenw);
330 if (i > 0)
331 lmmp_fft_shl_coef_(amsr, pfca + i, i * ctx->n >> ctx->k);
332 } else {
333 lmmp_zero(pfca[i], ctx->nlen);
334 }
335 }
336 lmmp_fft_(amsr, pfca, ctx->k, ctx->n >> (ctx->k - 1));
337
338 for (mp_size_t i = 0; i < ctx->K; ++i) {
339 mp_size_t coeflen;
340 pfcb[i] = (mp_ptr)(pfcb + ctx->K) + i * ctx->nlen;
341 if (nbrest > 0) {
342 coeflen = ctx->M + (i == ctx->K - 1);
343 coeflen = LMMP_MIN(nbrest, coeflen);
344 nbrest -= coeflen;
345 lmmp_fft_extract_coef_(pfcb[i], numb, ctx->M * i, coeflen, bmsr->lenw);
346 if (i > 0)
347 lmmp_fft_shl_coef_(bmsr, pfcb + i, i * ctx->n >> ctx->k);
348 } else {
349 lmmp_zero(pfcb[i], ctx->nlen);
350 }
351 }
352 lmmp_fft_(bmsr, pfcb, ctx->k, ctx->n >> (ctx->k - 1));
353
354 lmmp_mul_fermat_recurse_(amsr, pfca, pfcb, ctx->K);
355
356 lmmp_ifft_(amsr, pfca, ctx->k, ctx->n >> (ctx->k - 1));
357
358 lmmp_mul_fermat_recombine_(amsr, dst, pfca, ctx->K, ctx->k, ctx->n, ctx->M, ctx->rn);
359
360 if (dst[rn] && !lmmp_zero_q_(dst, rn)) {
361 dst[rn] = 0;
362 lmmp_dec(dst);
363 }
364 lmmp_fft_memstack_(amsr, 0);
365}

引用了 fft_gr_cache::a_size, fft_gr_cache::amsr, fft_gr_cache::bmsr, fft_gr_cache::K, fft_gr_cache::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_cache_init_(), lmmp_mul_fermat_recombine_(), lmmp_mul_fermat_recurse_(), lmmp_param_assert, lmmp_zero, lmmp_zero_q_(), fft_gr_cache::M, fft_memstack::maxdepth, fft_gr_cache::N, fft_gr_cache::n, fft_gr_cache::na, fft_gr_cache::nlen, numb, fft_gr_cache::rn, fft_memstack::temp_coef, fft_gr_cache::temp_coefb , 以及 fft_memstack::tempdepth.

被这些函数引用 lmmp_mul_fermat_cache_init_(), lmmp_mul_fft_cache_init_(), lmmp_mullo_fft_cache_init_() , 以及 TEST_CASE().

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

◆ lmmp_mul_fermat_recurse_()

void lmmp_mul_fermat_recurse_ ( fft_memstack * ms,
mp_ptr * pc1,
mp_ptr * pc2,
mp_size_t K0 )
static

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

费马变换乘法递归函数(核心乘法逻辑)

参数
ms- 内存栈结构体指针
pc1- 第一个数的FFT系数数组指针数组
pc2- 第二个数的FFT系数数组指针数组
K0- FFT块数
警告
K0>0 所有系数均已伪归一化(mod B^lenw+1) nsqr=1表示乘法,nsqr=0表示平方

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

43 {
44 const int nsqr = 1;
45 mp_ptr push_temp_coef = ms->temp_coef;
46 mp_size_t rn = ms->lenw;
47
48 if (rn < MUL_FFT_MODF_THRESHOLD) {
49 mp_ptr temp_mul = (mp_ptr)lmmp_fft_memstack_(ms, (rn + 1) * 2 * LIMB_BYTES);
50 for (mp_size_t i = 0; i < K0; ++i) {
51 lmmp_mul_n_(temp_mul, pc1[i], pc2[i], rn + 1);
52
53 // 模 B^rn+1 归一化:temp_mul - temp_mul[rn ...]
54 mp_limb_t maxc = lmmp_sub_n_(pc1[i], temp_mul, temp_mul + rn, rn) + temp_mul[rn * 2];
55 pc1[i][rn] = 0;
56 lmmp_inc_1(pc1[i], maxc);
57 }
58 lmmp_fft_memstack_(ms, 0);
59 } else {
60 mp_size_t N = rn * LIMB_BITS; // 总比特数
62 mp_size_t K = ((mp_size_t)1) << k; // FFT块数(2^k)
63 lmmp_debug_assert(!(N & (K - 1)));
64 mp_size_t M = N >> k; // 每个块的比特数(N/K)
65 mp_size_t n = 2 * M + k + 2; // 扩展系数长度(保证归一化)
66
67 // 规整n:必须是LIMB_BITS和K的整数倍
68 n = (n + LIMB_BITS - 1) & (-LIMB_BITS);
69 n = (((n - 1) >> k) + 1) << k;
70
71 ms->lenw = n / LIMB_BITS;
72 mp_size_t nlen = ms->lenw + 1;
73
74 ms->temp_coef = (mp_ptr)lmmp_fft_memstack_(ms, (((nlen + 1) << (k + nsqr)) + nlen) * LIMB_BYTES);
75 mp_ptr *pfca = (mp_ptr*)(ms->temp_coef + nlen), *pfcb = pfca;
76 for (mp_size_t i = 0; i < K; ++i) pfca[i] = (mp_ptr)(pfca + K) + i * nlen;
77 pfcb += (nlen + 1) << k;
78 for (mp_size_t i = 0; i < K; ++i) pfcb[i] = (mp_ptr)(pfcb + K) + i * nlen;
79
80 for (mp_size_t j = 0; j < K0; ++j) {
81 mp_ptr numa = pc1[j];
82 mp_ptr numb = pc2[j];
83
84 for (mp_size_t i = 0; i < K; ++i) {
85 lmmp_fft_extract_coef_(pfca[i], numa, M * i, M + (i == K - 1), ms->lenw);
86 if (i > 0)
87 lmmp_fft_shl_coef_(ms, pfca + i, i * n >> k);
88 }
89 lmmp_fft_(ms, pfca, k, n >> (k - 1));
90
91 for (mp_size_t i = 0; i < K; ++i) {
92 lmmp_fft_extract_coef_(pfcb[i], numb, M * i, M + (i == K - 1), ms->lenw);
93 if (i > 0)
94 lmmp_fft_shl_coef_(ms, pfcb + i, i * n >> k);
95 }
96 lmmp_fft_(ms, pfcb, k, n >> (k - 1));
97
98 // dot product
99 lmmp_mul_fermat_recurse_(ms, pfca, pfcb, K);
100
101 lmmp_ifft_(ms, pfca, k, n >> (k - 1));
102
103 lmmp_mul_fermat_recombine_(ms, numa, pfca, K, k, n, M, rn);
104 }
105 lmmp_fft_memstack_(ms, 0);
106 }
107
108 ms->temp_coef = push_temp_coef;
109 ms->lenw = rn;
110}
#define lmmp_mul_n_
uint64_t mp_limb_t
定义 lmmp.h:92
#define MUL_FFT_MODF_THRESHOLD
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
#define lmmp_inc_1(p, inc)
加指定值宏(预期无进位)

引用了 k, fft_memstack::lenw, LIMB_BITS, LIMB_BYTES, lmmp_debug_assert, lmmp_fft_(), lmmp_fft_best_k_(), lmmp_fft_extract_coef_(), lmmp_fft_memstack_(), lmmp_fft_shl_coef_(), lmmp_ifft_(), lmmp_inc_1, lmmp_mul_fermat_recombine_(), lmmp_mul_fermat_recurse_(), lmmp_mul_n_, lmmp_sub_n_(), MUL_FFT_MODF_THRESHOLD, n, numb , 以及 fft_memstack::temp_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_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
mp_size_t lmmp_fft_next_size_(mp_size_t n)
计算满足 >=n 的最小费马/梅森乘法可行尺寸
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 tp
#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_cache_()

void lmmp_mul_fft_cache_ ( mp_ptr dst,
mp_srcptr numa,
fft_cache * ctx )

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

参数
dst输出结果缓冲区,长度至少为 na+nb
numa第一个输入操作数,长度为 na
ctxFFT乘法缓存上下文
警告
???<=na, sep(dst,numa), dst!=NULL, numa!=NULL, numb!=NULL, ctx!=NULL
注解
[numb,nb]将会被缓存,第二个乘数始终保持不变时,在后续计算中可以调用lmmp_mul_fft_cache_()函数节省40的计算时间 numb可以在lmmp_mul_fft_cache_()函数前被释放,不会影响后续计算
返回
无返回值,结果存储在dst中

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

736 {
737 lmmp_param_assert(dst != NULL && numa != NULL);
738 lmmp_param_assert(ctx != NULL);
739 mp_srcptr amodm = numa;
740 if (ctx->na > ctx->hn) {
741 if (lmmp_add_(dst, numa, ctx->hn, numa + ctx->hn, ctx->na - ctx->hn))
742 lmmp_inc(dst);
743 amodm = dst;
744 }
745 lmmp_mul_mersenne_cache_(dst, amodm, &ctx->mersenne);
746
747 mp_srcptr amodp = numa;
748 if (ctx->na > ctx->hn) {
749 ctx->tp[ctx->hn] = 0;
750 if (lmmp_sub_(ctx->tp, numa, ctx->hn, numa + ctx->hn, ctx->na - ctx->hn))
751 lmmp_inc(ctx->tp);
752 amodp = ctx->tp;
753 }
754 lmmp_mul_fermat_cache_(ctx->tp, amodp, &ctx->fermat);
755
756 lmmp_mul_fft_crt_(dst, ctx->tp, ctx->hn, ctx->na + ctx->nb);
757}
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
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_inc(p)
加1宏(预期无进位)
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]
mp_size_t na
void lmmp_mul_mersenne_cache_(mp_ptr dst, mp_srcptr numa, fft_gr_cache *ctx)
梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1
fft_gr_cache mersenne
mp_size_t nb
mp_size_t hn
fft_gr_cache fermat
void lmmp_mul_fermat_cache_(mp_ptr dst, mp_srcptr numa, fft_gr_cache *ctx)
费马数模乘法(缓存版) [dst,rn+1]=[numa,na]*[numb,nb] mod B^rn+1

引用了 fft_cache::fermat, fft_cache::hn, lmmp_add_(), lmmp_inc, lmmp_mul_fermat_cache_(), lmmp_mul_fft_cache_(), lmmp_mul_fft_crt_(), lmmp_mul_mersenne_cache_(), lmmp_param_assert, lmmp_sub_(), fft_cache::mersenne, fft_cache::na, fft_cache::nb , 以及 fft_cache::tp.

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

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

◆ lmmp_mul_fft_cache_init_()

void lmmp_mul_fft_cache_init_ ( mp_ptr dst,
mp_size_t hn,
mp_srcptr numa,
mp_size_t na,
mp_srcptr numb,
mp_size_t nb,
fft_cache * ctx )

FFT乘法运算 [dst,na+nb] = [numa,na] * [numb,nb] 第二个操作数将被缓存

参数
dst输出结果缓冲区,长度至少为 na+nb
hn双域模运算的阶数。须满足 hn<na+nb<=2*hn,使 CRT 重组能容纳完整乘积。
numa第一个输入操作数,长度为 na
na第一个操作数的 limb 长度
numb第二个输入操作数,长度为 nb
nb第二个操作数的 limb 长度
ctxFFT乘法缓存上下文
警告
0<nb<=na, hn<na+nb<=2*hn, lmmp_fft_next_size_(hn)==hn, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL, ctx!=NULL
注解
[numb,nb]将会被缓存,第二个乘数始终保持不变时,在后续计算中可以调用lmmp_mul_fft_cache_()函数节省40的计算时间 numb可以在lmmp_mul_fft_cache_()函数前被释放,不会影响后续计算
返回
无返回值,结果存储在dst中

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

700 {
701 lmmp_param_assert(na > 0 && nb > 0);
702 lmmp_param_assert(na >= nb);
703 lmmp_param_assert(na + nb > hn);
704 lmmp_param_assert(na + nb <= 2 * hn);
705 lmmp_param_assert(dst != NULL && numa != NULL && numb != NULL);
706 lmmp_param_assert(ctx != NULL);
707 ctx->hn = hn;
708 ctx->na = na;
709 ctx->nb = nb;
710 ctx->tp = ALLOC_TYPE(hn + 1, mp_limb_t);
711
712 mp_srcptr amodm = numa;
713 mp_size_t nam = na;
714 if (na > hn) {
715 if (lmmp_add_(dst, numa, hn, numa + hn, na - hn))
716 lmmp_inc(dst);
717 amodm = dst;
718 nam = hn;
719 }
720 lmmp_mul_mersenne_cache_init_(dst, hn, amodm, nam, numb, nb, &ctx->mersenne);
721
722 mp_srcptr amodp = numa;
723 mp_size_t nap = na;
724 if (na > hn) {
725 ctx->tp[hn] = 0;
726 if (lmmp_sub_(ctx->tp, numa, hn, numa + hn, na - hn))
727 lmmp_inc(ctx->tp);
728 amodp = ctx->tp;
729 nap = hn + 1;
730 }
731 lmmp_mul_fermat_cache_init_(ctx->tp, hn, amodp, nap, numb, nb, &ctx->fermat);
732
733 lmmp_mul_fft_crt_(dst, ctx->tp, hn, na + nb);
734}
void lmmp_mul_fermat_cache_init_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, fft_gr_cache *ctx)
费马数模乘法(缓存版) [dst,rn+1]=[numa,na]*[numb,nb] mod B^rn+1 第二个操作数将被缓存
void lmmp_mul_mersenne_cache_init_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, fft_gr_cache *ctx)
梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1 第二个操作数将被缓存

引用了 ALLOC_TYPE, fft_cache::fermat, fft_cache::hn, lmmp_add_(), lmmp_inc, lmmp_mul_fermat_cache_init_(), lmmp_mul_fft_cache_init_(), lmmp_mul_fft_crt_(), lmmp_mul_mersenne_cache_init_(), lmmp_param_assert, lmmp_sub_(), fft_cache::mersenne, fft_cache::na, fft_cache::nb, numb , 以及 fft_cache::tp.

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

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

◆ lmmp_mul_fft_crt_()

void lmmp_mul_fft_crt_ ( mp_ptr dst,
mp_ptr tp,
mp_size_t hn,
mp_size_t nab )
static

FFT 双域 CRT 重构尾部(lmmp_mul_fft_mods_ 的后半):两域残差 → 精确积

参数
dst输入输出:入口为梅森域残差 [dst,hn](P mod B^hn-1,规范形 [0,B^hn-1)),出口为精确积 [dst,nab]
tp输入输出:入口为费马域残差 [tp,hn+1](P mod B^hn+1,库规范形 [0,B^hn]),出口内容破坏
hn变换阶数(与 mods_ 一致)
nab积长度界(P < B^nab),hn < nab <= 2*hn
警告
sep(dst,tp), nab>hn, nab<=2*hn

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

659 {
660 mp_limb_t cy = lmmp_shr1add_nc_(dst, dst, tp, hn, tp[hn]);
661 cy <<= LIMB_BITS - 1;
662 dst[hn - 1] += cy;
663 if (dst[hn - 1] < cy)
664 lmmp_inc(dst);
665
666 if (nab == 2 * hn) {
667 cy = tp[hn] + lmmp_sub_n_(dst + hn, dst, tp, hn);
668 // cy==1 means [tp,hn+1]!=0, then [dst,hn]!=0
669 // cy==2 is impossible since [tp,hn+1] is normalized.
670 // so the following dec won't overflow.
671 lmmp_dec_1(dst, cy);
672 } else {
673 cy = lmmp_sub_n_(dst + hn, dst, tp, nab - hn);
674 cy = tp[hn] + lmmp_sub_nc_(tp + nab - hn, dst + nab - hn, tp + nab - hn, 2 * hn - nab, cy);
675 cy = lmmp_sub_1_(dst, dst, nab, cy);
676 }
677}
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
#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
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

引用了 LIMB_BITS, lmmp_dec_1, lmmp_inc, lmmp_mul_fft_crt_(), lmmp_shr1add_nc_(), lmmp_sub_1_(), lmmp_sub_n_(), lmmp_sub_nc_() , 以及 tp.

被这些函数引用 lmmp_mul_fft_(), lmmp_mul_fft_cache_(), lmmp_mul_fft_cache_init_() , 以及 lmmp_mul_fft_crt_().

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

◆ lmmp_mul_fft_mods_()

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

FFT 双域模乘计算:分别求梅森域与费马域残差(lmmp_mul_fft_crt_ 的前半)

参数
dst输出:梅森域结果 [dst,hn] = P mod (B^hn-1),P = [numa,na]*[numb,nb]
tp输出:费马域结果 [tp,hn+1] = P mod (B^hn+1)(库规范形 [0,B^hn]), na > hn 时兼作 numa 的费马折叠工作区(需 hn+1 limb)
hn变换阶数(两域共用)
numa第一操作数(超长时按域折叠:amodm = a mod (B^hn-1) 原位写入 dst, amodp = a mod (B^hn+1) 原位写入 tp,折叠取 [低hn)±[高位))
nanuma 长度(任意 > 0;> hn 时触发折叠)
numb第二操作数(不折叠,要求 nb <= hn)
nbnumb 长度
警告
nb<=na, nb<=hn, sep(dst,[numa|numb]), sep(tp,[numa|numb]), dst 与 tp 分离
注解
na > hn 时 dst 先接收梅森折叠值(nam 截为 hn),随后被梅森域积覆写; tp 同理(nap 截为 hn+1)

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

618 {
619 mp_srcptr amodm = numa;
620 mp_size_t nam = na;
621 if (na > hn) {
622 /*
623 Z = B^hb - 1
624 amodm = a mod Z
625 */
626 if (lmmp_add_(dst, numa, hn, numa + hn, na - hn))
627 lmmp_inc(dst);
628 amodm = dst;
629 nam = hn;
630 }
631 lmmp_mul_mersenne_fft_(dst, hn, amodm, nam, numb, nb);
632
633 mp_srcptr amodp = numa;
634 mp_size_t nap = na;
635 if (na > hn) {
636 /*
637 Z = B^hp + 1
638 amodp = a mod Z
639 */
640 tp[hn] = 0;
641 if (lmmp_sub_(tp, numa, hn, numa + hn, na - hn))
642 lmmp_inc(tp);
643 amodp = tp;
644 nap = hn + 1;
645 }
646 lmmp_mul_fermat_(tp, hn, amodp, nap, numb, nb);
647}
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_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

引用了 lmmp_add_(), lmmp_inc, lmmp_mul_fermat_(), lmmp_mul_fft_mods_(), lmmp_mul_mersenne_fft_(), lmmp_sub_(), numb , 以及 tp.

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

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

◆ lmmp_mul_fft_unbalance_()

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

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

765 {
766 lmmp_param_assert(na >= 3 * nb);
768 mp_size_t sna = 3 * nb;
769 mp_size_t hn = lmmp_fft_next_size_((sna + nb + 1) >> 1);
770 sna = (hn << 1) - 1 - nb;
771 fft_cache ctx;
772 lmmp_mul_fft_cache_init_(dst, hn, numa, sna, numb, nb, &ctx);
773 dst += sna;
774 numa += sna;
775 na -= sna;
776 lmmp_copy(ws, dst, nb);
777 while (na >= sna) {
778 lmmp_mul_fft_cache_(dst, numa, &ctx);
779 if (lmmp_add_n_(dst, dst, ws, nb))
780 lmmp_inc(dst + nb);
781 dst += sna;
782 numa += sna;
783 na -= sna;
784 lmmp_copy(ws, dst, nb);
785 }
787 // remaining na < sna
788 if (na >= nb)
789 lmmp_mul_(dst, numa, na, numb, nb);
790 else if (na > 0)
791 lmmp_mul_(dst, numb, nb, numa, na);
792 else // na == 0
793 lmmp_zero(dst, nb);
794 if (lmmp_add_n_(dst, dst, ws, nb))
795 lmmp_inc(dst + nb);
796 lmmp_free(ws);
797}
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
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_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
static void lmmp_fft_cache_free_(fft_cache *ctx)
释放FFT模乘法缓存上下文
void lmmp_mul_fft_cache_init_(mp_ptr dst, mp_size_t hn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, fft_cache *ctx)
FFT乘法运算 [dst,na+nb] = [numa,na] * [numb,nb] 第二个操作数将被缓存
void lmmp_mul_fft_cache_(mp_ptr dst, mp_srcptr numa, fft_cache *ctx)
FFT乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)

引用了 ALLOC_TYPE, lmmp_add_n_(), lmmp_copy, lmmp_fft_cache_free_(), lmmp_fft_next_size_(), lmmp_free(), lmmp_inc, lmmp_mul_(), lmmp_mul_fft_cache_(), lmmp_mul_fft_cache_init_(), lmmp_mul_fft_unbalance_(), lmmp_param_assert, lmmp_zero, numb , 以及 restrict.

函数调用图:

◆ lmmp_mul_mersenne_cache_()

void lmmp_mul_mersenne_cache_ ( mp_ptr dst,
mp_srcptr numa,
fft_gr_cache * ctx )

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

参数
dst输出结果缓冲区,长度为 lmmp_mul_mersenne_cache_init_()函数中输入参数的 rn
numa第一个输入操作数,长度为 lmmp_mul_mersenne_cache_init_()函数中输入参数的 na
ctx梅森数模乘法缓存上下文
警告
eqsep(dst,numa), 0<=[numa,na]<B^rn
注解
使用被缓存的[numb,nb]作为第二个乘数,numb可以在lmmp_mul_mersenne_cache_()函数前被释放,不会影响后续计算
返回
无返回值,结果存储在dst中

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

523 {
524 lmmp_param_assert(dst != NULL && numa != NULL);
525 lmmp_param_assert(ctx != NULL);
526 fft_memstack* bmsr = &ctx->bmsr;
527 fft_memstack* amsr = &ctx->amsr;
528
529 amsr->maxdepth = -1;
530 amsr->tempdepth = -1;
531 amsr->lenw = ctx->n / LIMB_BITS;
532 amsr->temp_coef = (mp_ptr)lmmp_fft_memstack_(amsr, ctx->a_size);
533
534 bmsr->temp_coef = ctx->temp_coefb;
535 mp_ptr* pfca = (mp_ptr*)(amsr->temp_coef + ctx->nlen);
536 mp_ptr* pfcb = (mp_ptr*)(bmsr->temp_coef + ctx->nlen);
537
538 mp_size_t narest = ctx->na * LIMB_BITS;
539
540 for (mp_size_t i = 0; i < ctx->K; ++i) {
541 mp_size_t coeflen;
542 pfca[i] = (mp_ptr)(pfca + ctx->K) + i * ctx->nlen;
543 if (narest > 0) {
544 coeflen = ctx->M + (i == ctx->K - 1);
545 coeflen = LMMP_MIN(narest, ctx->M);
546 narest -= coeflen;
547 lmmp_fft_extract_coef_(pfca[i], numa, ctx->M * i, coeflen, amsr->lenw);
548 } else {
549 lmmp_zero(pfca[i], ctx->nlen);
550 }
551 }
552 lmmp_fft_(amsr, pfca, ctx->k, ctx->n >> (ctx->k - 1));
553
554 lmmp_mul_fermat_recurse_(amsr, pfca, pfcb, ctx->K);
555
556 lmmp_ifft_(amsr, pfca, ctx->k, ctx->n >> (ctx->k - 1));
557
558 mp_size_t rhead = 0, maxc = 0;
559 for (mp_size_t i = 0; i < ctx->K; ++i) {
560 lmmp_fft_shr_coef_(amsr, pfca + i, ctx->k);
561 mp_ptr nums = pfca[i];
562
563 if (nums[ctx->nlen - 1]) {
564 lmmp_dec(nums);
565 lmmp_debug_assert(nums[ctx->nlen - 1] == 1);
566 nums[ctx->nlen - 1] = 0;
567 }
568
569 mp_size_t roffset = i * ctx->M;
570 mp_size_t shl = roffset & (LIMB_BITS - 1);
571 roffset /= LIMB_BITS;
572
573 if (shl)
574 lmmp_shl_(nums, nums, ctx->nlen, shl);
575
576 if (i == 0) {
577 rhead = LMMP_MIN(ctx->nlen, ctx->rn);
578 lmmp_copy(dst, nums, rhead);
579 } else if (roffset + ctx->nlen <= ctx->rn) {
580 lmmp_add_(dst + roffset, nums, ctx->nlen, dst + roffset, rhead - roffset);
581 rhead = roffset + ctx->nlen;
582 } else {
583 maxc += lmmp_add_(dst + roffset, nums, ctx->rn - roffset, dst + roffset, rhead - roffset);
584 maxc += lmmp_add_(dst, dst, ctx->rn, nums + ctx->rn - roffset, ctx->nlen + roffset - ctx->rn);
585 rhead = ctx->rn;
586 }
587 }
588
589 if (!lmmp_add_1_(dst, dst, ctx->rn, 1 + maxc))
590 lmmp_dec(dst);
591
592 lmmp_fft_memstack_(amsr, 0);
593}
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_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
加单精度数静态内联函数 [dst,na]=[numa,na]+x
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

引用了 fft_gr_cache::a_size, fft_gr_cache::amsr, fft_gr_cache::bmsr, fft_gr_cache::K, fft_gr_cache::k, fft_memstack::lenw, LIMB_BITS, lmmp_add_(), lmmp_add_1_(), lmmp_copy, lmmp_debug_assert, lmmp_dec, lmmp_fft_(), lmmp_fft_extract_coef_(), lmmp_fft_memstack_(), lmmp_fft_shr_coef_(), lmmp_ifft_(), LMMP_MIN, lmmp_mul_fermat_recurse_(), lmmp_mul_mersenne_cache_(), lmmp_param_assert, lmmp_shl_(), lmmp_zero, fft_gr_cache::M, fft_memstack::maxdepth, fft_gr_cache::n, fft_gr_cache::na, fft_gr_cache::nlen, fft_gr_cache::rn, fft_memstack::temp_coef, fft_gr_cache::temp_coefb , 以及 fft_memstack::tempdepth.

被这些函数引用 lmmp_binvert_unbalance_(), lmmp_div_mulinv_(), lmmp_divexact_mu_run_(), lmmp_hgcd_apply_mod_(), lmmp_mont_redc_(), lmmp_mul_fft_cache_(), lmmp_mul_mersenne_cache_(), lmmp_mullo_fft_cache_() , 以及 TEST_CASE().

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

◆ lmmp_mul_mersenne_cache_init_()

void lmmp_mul_mersenne_cache_init_ ( mp_ptr dst,
mp_size_t rn,
mp_srcptr numa,
mp_size_t na,
mp_srcptr numb,
mp_size_t nb,
fft_gr_cache * ctx )

梅森数模乘法 [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 长度
ctx梅森数模乘法缓存上下文
警告
eqsep(dst,[numa|numb]), 0<=[numa,na]<B^rn, 0<=[numb,nb]<B^rn, lmmp_fft_next_size_(rn)==rn
注解
[numb,nb]将会被缓存,第二个乘数始终保持不变时,在后续计算中可以调用lmmp_mul_mersenne_cache_()函数节省40的计算时间 numb可以在lmmp_mul_mersenne_cache_()函数前被释放,不会影响后续计算
返回
无返回值,结果存储在dst中

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

420 {
421 lmmp_param_assert(na > 0 && nb > 0);
422 lmmp_param_assert(dst != NULL && numa != NULL && numb != NULL);
423 lmmp_param_assert(ctx != NULL);
424 ctx->na = na;
425 ctx->rn = rn;
426 ctx->N = rn * LIMB_BITS;
427 ctx->k = lmmp_fft_best_k_(rn);
428 ctx->K = ((mp_size_t)1) << ctx->k;
429 lmmp_debug_assert(!(ctx->N & (ctx->K - 1)));
430 ctx->M = ctx->N >> ctx->k;
431 ctx->n = 2 * ctx->M + ctx->k;
432 ctx->n = (ctx->n + LIMB_BITS - 1) & (-LIMB_BITS);
433 ctx->n = (((ctx->n - 1) >> (ctx->k - 1)) + 1) << (ctx->k - 1);
434
435 fft_memstack* bmsr = &ctx->bmsr;
436 fft_memstack* amsr = &ctx->amsr;
437 amsr->maxdepth = -1;
438 amsr->tempdepth = -1;
439 amsr->lenw = ctx->n / LIMB_BITS;
440 ctx->nlen = amsr->lenw + 1;
441 ctx->a_size = (((ctx->nlen + 1) << (ctx->k)) + ctx->nlen) * LIMB_BYTES;
442 amsr->temp_coef = (mp_ptr)lmmp_fft_memstack_(amsr, ctx->a_size);
443 mp_ptr* pfca = (mp_ptr*)(amsr->temp_coef + ctx->nlen);
444 mp_ptr* pfcb = NULL;
445
446 bmsr->maxdepth = -1;
447 bmsr->tempdepth = -1;
448 bmsr->lenw = ctx->n / LIMB_BITS;
449 bmsr->temp_coef = (mp_ptr)lmmp_fft_memstack_(bmsr, ctx->a_size);
450 ctx->temp_coefb = bmsr->temp_coef;
451 pfcb = (mp_ptr*)(bmsr->temp_coef + ctx->nlen);
452
453 mp_size_t narest = na * LIMB_BITS, nbrest = nb * LIMB_BITS;
454
455 for (mp_size_t i = 0; i < ctx->K; ++i) {
456 mp_size_t coeflen;
457 pfca[i] = (mp_ptr)(pfca + ctx->K) + i * ctx->nlen;
458 if (narest > 0) {
459 coeflen = ctx->M + (i == ctx->K - 1);
460 coeflen = LMMP_MIN(narest, ctx->M);
461 narest -= coeflen;
462 lmmp_fft_extract_coef_(pfca[i], numa, ctx->M * i, coeflen, amsr->lenw);
463 } else {
464 lmmp_zero(pfca[i], ctx->nlen);
465 }
466 }
467 lmmp_fft_(amsr, pfca, ctx->k, ctx->n >> (ctx->k - 1));
468
469 for (mp_size_t i = 0; i < ctx->K; ++i) {
470 mp_size_t coeflen;
471 pfcb[i] = (mp_ptr)(pfcb + ctx->K) + i * ctx->nlen;
472 if (nbrest > 0) {
473 coeflen = LMMP_MIN(nbrest, ctx->M);
474 nbrest -= coeflen;
475 lmmp_fft_extract_coef_(pfcb[i], numb, ctx->M * i, coeflen, bmsr->lenw);
476 } else {
477 lmmp_zero(pfcb[i], ctx->nlen);
478 }
479 }
480 lmmp_fft_(bmsr, pfcb, ctx->k, ctx->n >> (ctx->k - 1));
481
482 lmmp_mul_fermat_recurse_(amsr, pfca, pfcb, ctx->K);
483
484 lmmp_ifft_(amsr, pfca, ctx->k, ctx->n >> (ctx->k - 1));
485
486 mp_size_t rhead = 0, maxc = 0;
487 for (mp_size_t i = 0; i < ctx->K; ++i) {
488 lmmp_fft_shr_coef_(amsr, pfca + i, ctx->k);
489 mp_ptr nums = pfca[i];
490
491 if (nums[ctx->nlen - 1]) {
492 lmmp_dec(nums);
493 lmmp_debug_assert(nums[ctx->nlen - 1] == 1);
494 nums[ctx->nlen - 1] = 0;
495 }
496
497 mp_size_t roffset = i * ctx->M;
498 mp_size_t shl = roffset & (LIMB_BITS - 1);
499 roffset /= LIMB_BITS;
500
501 if (shl)
502 lmmp_shl_(nums, nums, ctx->nlen, shl);
503
504 if (i == 0) {
505 rhead = LMMP_MIN(ctx->nlen, rn);
506 lmmp_copy(dst, nums, rhead);
507 } else if (roffset + ctx->nlen <= rn) {
508 lmmp_add_(dst + roffset, nums, ctx->nlen, dst + roffset, rhead - roffset);
509 rhead = roffset + ctx->nlen;
510 } else {
511 maxc += lmmp_add_(dst + roffset, nums, rn - roffset, dst + roffset, rhead - roffset);
512 maxc += lmmp_add_(dst, dst, rn, nums + rn - roffset, ctx->nlen + roffset - rn);
513 rhead = rn;
514 }
515 }
516
517 if (!lmmp_add_1_(dst, dst, rn, 1 + maxc))
518 lmmp_dec(dst);
519
520 lmmp_fft_memstack_(amsr, 0);
521}

引用了 fft_gr_cache::a_size, fft_gr_cache::amsr, fft_gr_cache::bmsr, fft_gr_cache::K, fft_gr_cache::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_cache_init_(), lmmp_param_assert, lmmp_shl_(), lmmp_zero, fft_gr_cache::M, fft_memstack::maxdepth, fft_gr_cache::N, fft_gr_cache::n, fft_gr_cache::na, fft_gr_cache::nlen, numb, fft_gr_cache::rn, fft_memstack::temp_coef, fft_gr_cache::temp_coefb , 以及 fft_memstack::tempdepth.

被这些函数引用 lmmp_binvert_unbalance_(), lmmp_div_mulinv_(), lmmp_divexact_mu_run_(), lmmp_hgcd_apply_mod_(), lmmp_mont_redc_(), lmmp_mul_fft_cache_init_(), lmmp_mul_mersenne_cache_init_(), lmmp_mullo_fft_cache_init_() , 以及 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}

引用了 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().

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