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

浏览该文件的源代码.

结构体

struct  fft_cache
struct  fft_gr_cache
 Copyright (C) 2026 HJimmyK (Jericho Knox) 更多...
struct  fft_mullo_cache

函数

static void lmmp_fft_cache_free_ (fft_cache *ctx)
 释放FFT模乘法缓存上下文
static void lmmp_fft_gr_cache_free_ (fft_gr_cache *ctx)
 释放费马或梅森数模乘法缓存上下文
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 第二个操作数将被缓存
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] 第二个操作数将被缓存
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 第二个操作数将被缓存
static void lmmp_mullo_cache_free_ (fft_mullo_cache *ctx)
 释放 mullo 缓存上下文
void lmmp_mullo_fft_cache_ (mp_ptr dst, mp_srcptr numa, mp_ptr scratch, fft_mullo_cache *ctx)
 低位乘法(缓存版) [dst,n] = [numa,n] * 缓存numb mod B^n
void lmmp_mullo_fft_cache_init_ (mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n, mp_ptr scratch, fft_mullo_cache *ctx)
 低位乘法(缓存版) [dst,n] = [numa,n] * [numb,n] mod B^n 第二个操作数将被缓存

结构体说明

◆ fft_cache

struct fft_cache

在文件 mul_cache.h 第 44 行定义.

fft_cache 的协作图:
成员变量
fft_gr_cache fermat
mp_size_t hn
fft_gr_cache mersenne
mp_size_t na
mp_size_t nb
mp_ptr tp

◆ fft_gr_cache

struct fft_gr_cache

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

在文件 mul_cache.h 第 29 行定义.

fft_gr_cache 的协作图:
成员变量
mp_size_t a_size
fft_memstack amsr
fft_memstack bmsr
mp_size_t K
mp_size_t k
mp_size_t M
mp_size_t N
mp_size_t n
mp_size_t na
mp_size_t nlen
mp_size_t rn
mp_ptr temp_coefb

◆ fft_mullo_cache

struct fft_mullo_cache

在文件 mul_cache.h 第 53 行定义.

fft_mullo_cache 的协作图:
成员变量
mp_size_t hn
fft_cache mul
mp_size_t n

函数说明

◆ lmmp_fft_cache_free_()

void lmmp_fft_cache_free_ ( fft_cache * ctx)
inlinestatic

释放FFT模乘法缓存上下文

参数
ctxFFT模乘法缓存上下文

在文件 mul_cache.h 第 71 行定义.

71 {
74 lmmp_free(ctx->tp);
75}
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
fft_gr_cache mersenne
static void lmmp_fft_gr_cache_free_(fft_gr_cache *ctx)
释放费马或梅森数模乘法缓存上下文
fft_gr_cache fermat

引用了 fft_cache::fermat, lmmp_fft_cache_free_(), lmmp_fft_gr_cache_free_(), lmmp_free(), fft_cache::mersenne , 以及 fft_cache::tp.

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

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

◆ lmmp_fft_gr_cache_free_()

void lmmp_fft_gr_cache_free_ ( fft_gr_cache * ctx)
inlinestatic

释放费马或梅森数模乘法缓存上下文

参数
ctx费马或梅森数模乘法缓存上下文

在文件 mul_cache.h 第 63 行定义.

63 {
64 lmmp_fft_memstack_(&ctx->bmsr, 0);
65}
void * lmmp_fft_memstack_(fft_memstack *ms, mp_size_t size)
FFT内存栈的分配/释放接口
fft_memstack bmsr

引用了 fft_gr_cache::bmsr, lmmp_fft_gr_cache_free_() , 以及 lmmp_fft_memstack_().

被这些函数引用 lmmp_binvert_unbalance_(), lmmp_div_mulinv_(), lmmp_divexact_mu_run_(), lmmp_fft_cache_free_(), lmmp_fft_gr_cache_free_(), lmmp_hgcd_apply_mod_(), lmmp_mont_free_(), TEST_CASE() , 以及 TEST_CASE().

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

◆ 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}
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_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_MIN(l, o)
返回两个数中的较小值
定义 lmmp.h:450
#define LIMB_BITS
定义 lmmp.h:102
#define lmmp_param_assert(x)
定义 lmmp.h:509
#define lmmp_dec(p)
减1宏(预期无借位)
int lmmp_zero_q_(mp_srcptr p, mp_size_t n)
判零函数
定义 cmp.c:55
mp_size_t a_size
fft_memstack amsr
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)

引用了 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}
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 LIMB_BYTES
定义 lmmp.h:103
#define numb

引用了 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_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
mp_size_t nb
mp_size_t hn
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
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_ 的后半):两域残差 → 精确积

引用了 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}
uint64_t mp_limb_t
定义 lmmp.h:92
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 第二个操作数将被缓存
#define ALLOC_TYPE(n, type)

引用了 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_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的循环特性)
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
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_mullo_cache_free_()

void lmmp_mullo_cache_free_ ( fft_mullo_cache * ctx)
inlinestatic

释放 mullo 缓存上下文

参数
ctxmullo 缓存上下文

在文件 mul_cache.h 第 81 行定义.

81 {
83}
static void lmmp_fft_cache_free_(fft_cache *ctx)
释放FFT模乘法缓存上下文

引用了 lmmp_fft_cache_free_(), lmmp_mullo_cache_free_() , 以及 fft_mullo_cache::mul.

被这些函数引用 lmmp_binvert_unbalance_(), lmmp_divexact_mu_run_(), lmmp_mont_free_() , 以及 lmmp_mullo_cache_free_().

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

◆ lmmp_mullo_fft_cache_()

void lmmp_mullo_fft_cache_ ( mp_ptr dst,
mp_srcptr numa,
mp_ptr scratch,
fft_mullo_cache * ctx )

低位乘法(缓存版) [dst,n] = [numa,n] * 缓存numb mod B^n

参数
dst输出结果缓冲区,长度至少为 n
numa第一个输入操作数,长度为 lmmp_mullo_fft_cache_init_() 中输入参数的 n
scratch临时空间(2*n 个 limb)
ctxmullo 缓存上下文
警告
sep(scratch,numa), sep(dst,[numa|scratch]), dst!=NULL, numa!=NULL, scratch!=NULL, ctx!=NULL
返回
无返回值,结果存储在dst中

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

105 {
106 lmmp_param_assert(dst != NULL && numa != NULL);
107 lmmp_param_assert(scratch != NULL && ctx != NULL);
109 lmmp_mul_fermat_cache_(ctx->mul.tp, numa, &ctx->mul.fermat);
110 lmmp_mullo_crt_(dst, scratch, ctx->mul.tp, ctx->n, ctx->hn);
111}
#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

引用了 fft_cache::fermat, fft_mullo_cache::hn, lmmp_mul_fermat_cache_(), lmmp_mul_mersenne_cache_(), lmmp_mullo_crt_(), lmmp_mullo_fft_cache_(), lmmp_param_assert, fft_cache::mersenne, fft_mullo_cache::mul, fft_mullo_cache::n, scratch , 以及 fft_cache::tp.

被这些函数引用 lmmp_binvert_unbalance_(), lmmp_divexact_mu_run_(), lmmp_mont_redc_() , 以及 lmmp_mullo_fft_cache_().

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

◆ lmmp_mullo_fft_cache_init_()

void lmmp_mullo_fft_cache_init_ ( mp_ptr dst,
mp_srcptr numa,
mp_srcptr numb,
mp_size_t n,
mp_ptr scratch,
fft_mullo_cache * ctx )

低位乘法(缓存版) [dst,n] = [numa,n] * [numb,n] mod B^n 第二个操作数将被缓存

参数
dst输出结果缓冲区,长度至少为 n
numa第一个输入操作数,长度为 n
numb第二个输入操作数,长度为 n
n操作数的 limb 长度
scratch临时空间(2*n 个 limb,两操作数分离)
ctxmullo 缓存上下文
警告
n>???, sep(scratch,[numa|numb]), sep(dst,[numa|numb|scratch]), dst!=NULL, numa!=NULL, numb!=NULL
注解
[numb,nb]将会被缓存,第二个乘数始终保持不变时,在后续计算中可以调用lmmp_mullo_fft_cache_()函数节省40的计算时间 numb可以在lmmp_mullo_fft_cache_()函数前被释放,不会影响后续计算
返回
无返回值,结果存储在dst中

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

87 {
89 lmmp_param_assert(dst != NULL && numa != NULL && numb != NULL);
90 lmmp_param_assert(scratch != NULL && ctx != NULL);
92 lmmp_debug_assert(n <= hn);
93 ctx->n = n;
94 ctx->hn = hn;
95 ctx->mul.hn = hn;
96 ctx->mul.na = n;
97 ctx->mul.nb = n;
98 ctx->mul.tp = ALLOC_TYPE(hn + 1, mp_limb_t);
99
101 lmmp_mul_fermat_cache_init_(ctx->mul.tp, hn, numa, n, numb, n, &ctx->mul.fermat);
102 lmmp_mullo_crt_(dst, scratch, ctx->mul.tp, n, hn);
103}
mp_size_t lmmp_fft_next_size_(mp_size_t n)
计算满足 >=n 的最小费马/梅森乘法可行尺寸
#define n

引用了 ALLOC_TYPE, fft_cache::fermat, fft_cache::hn, fft_mullo_cache::hn, lmmp_debug_assert, lmmp_fft_next_size_(), lmmp_mul_fermat_cache_init_(), lmmp_mul_mersenne_cache_init_(), lmmp_mullo_crt_(), lmmp_mullo_fft_cache_init_(), lmmp_param_assert, fft_cache::mersenne, fft_mullo_cache::mul, fft_mullo_cache::n, n, fft_cache::na, fft_cache::nb, numb, scratch , 以及 fft_cache::tp.

被这些函数引用 lmmp_binvert_unbalance_(), lmmp_divexact_mu_run_(), lmmp_mont_redc_() , 以及 lmmp_mullo_fft_cache_init_().

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