LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
mul_cache.h
浏览该文件的文档.
1/**
2 * Copyright (C) 2026 HJimmyK (Jericho Knox)
3 *
4 * This file is part of LMMP.
5 *
6 * LMMP is free software: you can redistribute it and/or modify it
7 * under the terms of the GNU Lesser General Public License as
8 * published by the Free Software Foundation; either version 3 of
9 * the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library. If not, see
18 * <https://www.gnu.org/licenses/>.
19 *
20 * SPDX-License-Identifier: LGPL-3.0-or-later
21 */
22
23#ifndef __LMMP_MUL_CACHE_H__
24#define __LMMP_MUL_CACHE_H__
25
26#include "lmmpn/fft_ssa.h"
27
28
43
52
53typedef struct {
54 fft_cache mul; /* 双域乘法缓存(numb 侧被缓存) */
55 mp_size_t n; /* mullo 截断长度 */
56 mp_size_t hn; /* = lmmp_fft_next_size_(n) */
58
59/**
60 * @brief 释放费马或梅森数模乘法缓存上下文
61 * @param ctx 费马或梅森数模乘法缓存上下文
62 */
63static inline void lmmp_fft_gr_cache_free_(fft_gr_cache* ctx) {
64 lmmp_fft_memstack_(&ctx->bmsr, 0);
65}
66
67/**
68 * @brief 释放FFT模乘法缓存上下文
69 * @param ctx FFT模乘法缓存上下文
70 */
71static inline void lmmp_fft_cache_free_(fft_cache* ctx) {
74 lmmp_free(ctx->tp);
75}
76
77/**
78 * @brief 释放 mullo 缓存上下文
79 * @param ctx mullo 缓存上下文
80 */
81static inline void lmmp_mullo_cache_free_(fft_mullo_cache* ctx) {
83}
84
85/**
86 * @brief 费马数模乘法(缓存版) [dst,rn+1]=[numa,na]*[numb,nb] mod B^rn+1
87 * 第二个操作数将被缓存
88 * @param dst 输出结果缓冲区,长度至少为 rn+1
89 * @param rn 模运算的阶数参数,须为 FFT 可行尺寸(lmmp_fft_next_size_(rn)==rn);
90 * rn = lmmp_fft_next_size_((na + nb + 1) >> 1) 为可容纳乘积的推荐最小值
91 * @param numa 第一个输入操作数,长度为 na
92 * @param na 第一个操作数的 limb 长度
93 * @param numb 第二个输入操作数,长度为 nb
94 * @param nb 第二个操作数的 limb 长度
95 * @param ctx 费马数模乘法缓存上下文
96 * @warning eqsep(dst,[numa|numb]), 0<=[numa,na]<2*B^rn, 0<=[numb,nb]<2*B^rn, lmmp_fft_next_size_(rn)==rn
97 * @note [numb,nb]将会被缓存,第二个乘数始终保持不变时,在后续计算中可以调用lmmp_mul_fermat_cache_()函数节省40%的计算时间
98 * numb可以在lmmp_mul_fermat_cache_()函数前被释放,不会影响后续计算
99 * @return 无返回值,结果存储在dst中
100 */
102 fft_gr_cache* ctx);
103
104/**
105 * @brief 费马数模乘法(缓存版) [dst,rn+1]=[numa,na]*[numb,nb] mod B^rn+1
106 * @param dst 输出结果缓冲区,长度为 lmmp_mul_fermat_cache_init_()函数中输入参数的 rn+1
107 * @param numa 第一个输入操作数,长度为 lmmp_mul_fermat_cache_init_()函数中输入参数的 na
108 * @param ctx 费马数模乘法缓存上下文
109 * @warning eqsep(dst,numa), 0<=[numa,na]<2*B^rn
110 * @note 使用被缓存的[numb,nb]作为第二个乘数,numb可以在lmmp_mul_fermat_cache_()函数前被释放,不会影响后续计算
111 * @return 无返回值,结果存储在dst中
112 */
114
115/**
116 * @brief 梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1
117 * 第二个操作数将被缓存
118 * @param dst 输出结果缓冲区,长度至少为 rn
119 * @param rn 模运算的阶数参数,须为 FFT 可行尺寸(lmmp_fft_next_size_(rn)==rn);
120 * rn = lmmp_fft_next_size_((na + nb + 1) >> 1) 为可容纳乘积的推荐最小值
121 * @param numa 第一个输入操作数,长度为 na
122 * @param na 第一个操作数的 limb 长度
123 * @param numb 第二个输入操作数,长度为 nb
124 * @param nb 第二个操作数的 limb 长度
125 * @param ctx 梅森数模乘法缓存上下文
126 * @warning eqsep(dst,[numa|numb]), 0<=[numa,na]<B^rn, 0<=[numb,nb]<B^rn, lmmp_fft_next_size_(rn)==rn
127 * @note [numb,nb]将会被缓存,第二个乘数始终保持不变时,在后续计算中可以调用lmmp_mul_mersenne_cache_()函数节省40%的计算时间
128 * numb可以在lmmp_mul_mersenne_cache_()函数前被释放,不会影响后续计算
129 * @return 无返回值,结果存储在dst中
130 */
132 fft_gr_cache* ctx);
133
134/**
135 * @brief 梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1
136 * @param dst 输出结果缓冲区,长度为 lmmp_mul_mersenne_cache_init_()函数中输入参数的 rn
137 * @param numa 第一个输入操作数,长度为 lmmp_mul_mersenne_cache_init_()函数中输入参数的 na
138 * @param ctx 梅森数模乘法缓存上下文
139 * @warning eqsep(dst,numa), 0<=[numa,na]<B^rn
140 * @note 使用被缓存的[numb,nb]作为第二个乘数,numb可以在lmmp_mul_mersenne_cache_()函数前被释放,不会影响后续计算
141 * @return 无返回值,结果存储在dst中
142 */
144
145/**
146 * @brief FFT乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
147 * 第二个操作数将被缓存
148 * @param dst 输出结果缓冲区,长度至少为 na+nb
149 * @param hn 双域模运算的阶数。须满足 hn<na+nb<=2*hn,使 CRT 重组能容纳完整乘积。
150 * @param numa 第一个输入操作数,长度为 na
151 * @param na 第一个操作数的 limb 长度
152 * @param numb 第二个输入操作数,长度为 nb
153 * @param nb 第二个操作数的 limb 长度
154 * @param ctx FFT乘法缓存上下文
155 * @warning 0<nb<=na, hn<na+nb<=2*hn, lmmp_fft_next_size_(hn)==hn, sep(dst,[numa|numb]),
156 * dst!=NULL, numa!=NULL, numb!=NULL, ctx!=NULL
157 * @note [numb,nb]将会被缓存,第二个乘数始终保持不变时,在后续计算中可以调用lmmp_mul_fft_cache_()函数节省40%的计算时间
158 * numb可以在lmmp_mul_fft_cache_()函数前被释放,不会影响后续计算
159 * @return 无返回值,结果存储在dst中
160 */
162 fft_cache* ctx);
163
164/**
165 * @brief FFT乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
166 * @param dst 输出结果缓冲区,长度至少为 na+nb
167 * @param numa 第一个输入操作数,长度为 na
168 * @param ctx FFT乘法缓存上下文
169 * @warning ???<=na, sep(dst,numa), dst!=NULL, numa!=NULL, numb!=NULL, ctx!=NULL
170 * @note [numb,nb]将会被缓存,第二个乘数始终保持不变时,在后续计算中可以调用lmmp_mul_fft_cache_()函数节省40%的计算时间
171 * numb可以在lmmp_mul_fft_cache_()函数前被释放,不会影响后续计算
172 * @return 无返回值,结果存储在dst中
173 */
174void lmmp_mul_fft_cache_(mp_ptr dst, mp_srcptr numa, fft_cache* ctx);
175
176/**
177 * @brief 低位乘法(缓存版) [dst,n] = [numa,n] * [numb,n] mod B^n
178 * 第二个操作数将被缓存
179 * @param dst 输出结果缓冲区,长度至少为 n
180 * @param numa 第一个输入操作数,长度为 n
181 * @param numb 第二个输入操作数,长度为 n
182 * @param n 操作数的 limb 长度
183 * @param scratch 临时空间(2*n 个 limb,两操作数分离)
184 * @param ctx mullo 缓存上下文
185 * @warning n>???, sep(scratch,[numa|numb]), sep(dst,[numa|numb|scratch]), dst!=NULL, numa!=NULL, numb!=NULL
186 * @note [numb,nb]将会被缓存,第二个乘数始终保持不变时,在后续计算中可以调用lmmp_mullo_fft_cache_()函数节省40%的计算时间
187 * numb可以在lmmp_mullo_fft_cache_()函数前被释放,不会影响后续计算
188 * @return 无返回值,结果存储在dst中
189 */
191 fft_mullo_cache* ctx);
192
193/**
194 * @brief 低位乘法(缓存版) [dst,n] = [numa,n] * 缓存numb mod B^n
195 * @param dst 输出结果缓冲区,长度至少为 n
196 * @param numa 第一个输入操作数,长度为 lmmp_mullo_fft_cache_init_() 中输入参数的 n
197 * @param scratch 临时空间(2*n 个 limb)
198 * @param ctx mullo 缓存上下文
199 * @warning sep(scratch,numa), sep(dst,[numa|scratch]), dst!=NULL, numa!=NULL, scratch!=NULL, ctx!=NULL
200 * @return 无返回值,结果存储在dst中
201 */
203
204#endif // __LMMP_MUL_CACHE_H__
void * lmmp_fft_memstack_(fft_memstack *ms, mp_size_t size)
FFT内存栈的分配/释放接口
mp_limb_t * mp_ptr
定义 lmmp.h:96
uint64_t mp_size_t
定义 lmmp.h:93
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
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
static void lmmp_fft_cache_free_(fft_cache *ctx)
释放FFT模乘法缓存上下文
mp_size_t nb
fft_memstack bmsr
mp_size_t hn
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
static void lmmp_fft_gr_cache_free_(fft_gr_cache *ctx)
释放费马或梅森数模乘法缓存上下文
fft_gr_cache fermat
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]
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_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 第二个操作数将被缓存
定义 mullo.c:86
mp_size_t a_size
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 第二个操作数将被缓存
fft_memstack amsr
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define numb
#define n
#define scratch