LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
fft_ssa.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_FFT_SSA_H__
24#define __LMMP_FFT_SSA_H__
25
26#include "lmmp/lmmpn.h"
27
28#define FFT_MEMSTACK_DEPTH 16
29
30
31typedef struct {
32 mp_ptr temp_coef; // 用于数据交换的临时系数数组
33 mp_size_t lenw; // 系数的机器字(limb)长度
34 mp_ssize_t maxdepth; // 内存栈的最大深度(已分配的层数)
35 mp_ssize_t tempdepth; // 内存栈的当前深度(正在使用的层数)
36 void* mem[FFT_MEMSTACK_DEPTH]; // 存储内存块的指针
37 mp_size_t memsize[FFT_MEMSTACK_DEPTH]; // 存储每层内存块的大小(以字节为单位)
39
40/**
41 * @brief 查找对于 m>=n 的模 B^m+1 FFT运算的最优k值
42 * @param n - 输入的机器字长度
43 * @return 最优的k值
44 */
46
47/**
48 * @brief FFT内存栈的分配/释放接口
49 * @param ms 内存栈结构体栈帧
50 * @param size 分配大小(字节),size=0表示释放当前层内存
51 * @return 分配成功:返回mp_ptr*;释放:返回0
52 */
54
55/**
56 * @brief [dst,lenw+1] = [(bit*)numa+bitoffset, bits]
57 * @param dst 输出系数数组(长度lenw+1)
58 * @param numa 输入大数指针
59 * @param bitoffset 起始比特偏移量(>=0)
60 * @param bits 提取的比特数(0 < bits <= LIMB_BITS*lenw)
61 * @param lenw 输出系数的机器字长度
62 * @warning bitoffset>=0, 0<bits<=LIMB_BITS*lenw, sep(dst,numa)
63 */
64void lmmp_fft_extract_coef_(mp_ptr dst, mp_srcptr numa, mp_size_t bitoffset, mp_size_t bits, mp_size_t lenw);
65
66/**
67 * @brief 对模 2^n+1 的系数执行左移操作
68 * @param ms 内存栈结构体指针
69 * @param coef 输入输出系数数组指针(指针的指针,用于交换内存)
70 * @param shl 左移的比特数(0<shl<2*n)
71 * @warning n = ms->lenw * LIMB_BITS
72 * *coef 已伪归一化(mod 2^n+1)
73 * ms->temp_coef 至少有 lenw+1 个机器字
74 */
76
77/**
78 * @brief 对模 2^n+1 的系数执行右移操作
79 * 右移shr位 = 左移(2n - shr)位(mod 2^n+1的循环特性)
80 * @param ms 内存栈结构体指针
81 * @param coef 输入输出系数数组指针
82 * @param shr 右移的比特数(0 < shr < 2*n)
83 */
85
86/**
87 * @brief FFT蝶形运算(Butterfly Operation)
88 * (a,b) = (a + b, (a-b) << w ) mod 2^n+1
89 * a=[coef[0],ms->lenw+1], b=[coef[wing],ms->lenw+1], n=ms->lenw * LIMB_BITS
90 * @param ms 内存栈结构体指针
91 * @param coef 系数数组指针数组(coef[0]=a, coef[wing]=b)
92 * @param wing b的索引
93 * @param w 左移的比特数(0<=w<n)
94 * @warning n = ms->lenw * LIMB_BITS
95 * a,b 均已伪归一化(mod 2^n+1)
96 * ms->temp_coef 有至少 lenw + 1 个字长
97 */
98void lmmp_fft_bfy_(fft_memstack* ms, mp_ptr* coef, mp_size_t wing, mp_size_t w);
99
100/**
101 * @brief FFT蝶形运算(Butterfly Operation)
102 * (a,b) = (a+(b>>w), a-(b>>w)) mod 2^n+1
103 * a=[coef[0],ms->lenw+1], b=[coef[wing],ms->lenw+1], n=ms->lenw * LIMB_BITS
104 * @param ms 内存栈结构体指针
105 * @param coef 系数数组指针数组(coef[0]=a, coef[wing]=b)
106 * @param wing b的索引
107 * @param w 左移的比特数(0<=w<n)
108 * @warning n = ms->lenw * LIMB_BITS
109 * a,b 均已伪归一化(mod 2^n+1)
110 * ms->temp_coef 有至少 lenw + 1 个字长
111 */
112void lmmp_ifft_bfy_(fft_memstack* ms, mp_ptr* coef, mp_size_t wing, mp_size_t w);
113
114/**
115 * @brief ifft 蝶形数据面融合内核(两段扫描 + 连续进位链,单次调用完成)
116 *
117 * 以 t_i = [numb]>>shr 的逐 limb 流水线(numb 全程只读,不回写移位结果):
118 * 扫描1(i∈[0,w)):numc[l-w+i] = numa[l-w+i] + t_i (+bcy 链)
119 * numa[l-w+i] -= t_i (+acy 链)
120 * 扫描2(i∈[0,l-w)):numc[i] = numa[i] - t'_i (+bcy 链续)
121 * numa[i] += t'_i (+acy 链续),t'_i 从 numb[w] 起算
122 * 两段扫描的顶 limb 分别从 numb[w]、numb[l] 取高 shr 位(内核自行加载)
123 * @param numc 蝶形输出系数指针(temp_coef)
124 * @param numa 系数 a 指针(原地加减)
125 * @param numb 系数 b 指针(只读,须有 l+1 个 limb 可读)
126 * @param l 系数长度(ms->lenw)
127 * @param w 机器字级移位量(0<=w<=l)
128 * @param shr 比特级右移量
129 * @warning 0<shr<64, 0<=w<=l, sep(numc,[numa|numb]), l>0,
130 * 各指针非空;实现见 lmmpn/arch/generic/fft_fuse.c(C)与 arch/{x64,arm64}/fft_fuse.S
131 * @return 打包进位 (acy_final << 1) | bcy_final(acy 为 numa 链,bcy 为 numc 链)
132 */
134 mp_size_t l, mp_size_t w, mp_size_t shr);
135
136/**
137 * @brief fft 蝶形数据面融合内核(两段扫描 + 中点 ch 分解,单次调用完成)
138 *
139 * 扫描1(j∈[0,l-w)):D = numa[j] - numb[j] (-scyo 链,起点0)
140 * numc[w+j] = (D << shl) 接 shl 移位链(起点0)
141 * numa[j] = numa[j] + numb[j] (+acyo 链,起点0)
142 * 中点:ch = shlcy1 - (scyo1 << shl) 分解为 chp/chn(scyo1/shlcy1 为扫描1终值)
143 * 扫描2(j∈[0,w)):D2 = numb[l-w+j] - numa[l-w+j] (-scyo 链重置0)
144 * numc[j] = (D2 << shl) 接 shl 链(重置0)
145 * numa[l-w+j] += numb[l-w+j] (+acyo 链续)
146 * @param numc 蝶形输出系数指针(temp_coef)
147 * @param numa 系数 a 指针(原地加)
148 * @param numb 系数 b 指针(只读)
149 * @param l 系数长度(ms->lenw)
150 * @param w 机器字级移位量(0<=w<=l)
151 * @param shl 比特级左移量
152 * @param out 输出数组(至少 4 个 limb):out[0]=chp, out[1]=chn,
153 * out[2]=shlcy2(扫描2 shl 链移出位),out[3]=(acy_final<<1)|scyo_final
154 * @warning 0<shl<64, 0<=w<=l, sep(numc,[numa|numb]), l>0,
155 * 各指针非空;实现见 lmmpn/arch/generic/fft_fuse.c(C)与 arch/{x64,arm64}/fft_fuse.S
156 */
158 mp_size_t shl, mp_limb_t* out);
159
160void lmmp_fft_(fft_memstack* ms, mp_ptr* coef, mp_size_t k, mp_size_t w);
161
163
164/**
165 * @brief 费马变换 模 B^n+1 乘法的结果合并
166 * @param ms 内存栈结构体指针
167 * @param dst 输出结果数组
168 * @param pfca FFT系数数组指针数组
169 * @param K FFT块数(2^k)
170 * @param k FFT层数
171 * @param n 系数总比特数
172 * @param M 每个块的比特数
173 * @param rn 结果长度(机器字)
174 */
176 mp_size_t M, mp_size_t rn);
177
178#endif // __LMMP_FFT_SSA_H__
#define k
void lmmp_fft_bfy_fused_(mp_ptr numc, mp_ptr numa, mp_ptr numb, mp_size_t l, mp_size_t w, mp_size_t shl, mp_limb_t *out)
fft 蝶形数据面融合内核(两段扫描 + 中点 ch 分解,单次调用完成)
mp_limb_t lmmp_ifft_bfy_fused_(mp_ptr numc, mp_ptr numa, mp_ptr numb, mp_size_t l, mp_size_t w, mp_size_t shr)
Copyright (C) 2026 HJimmyK (Jericho Knox)
mp_size_t lmmp_fft_best_k_(mp_size_t n)
查找对于 m>=n 的模 B^m+1 FFT运算的最优k值
void lmmp_fft_shr_coef_(fft_memstack *ms, mp_ptr *coef, mp_size_t shr)
对模 2^n+1 的系数执行右移操作 右移shr位 = 左移(2n - shr)位(mod 2^n+1的循环特性)
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)
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],...
void lmmp_ifft_bfy_(fft_memstack *ms, mp_ptr *coef, mp_size_t wing, mp_size_t w)
FFT蝶形运算(Butterfly Operation) (a,b) = (a+(b>>w), a-(b>>w)) mod 2^n+1 a=[coef[0],ms->lenw+1],...
#define FFT_MEMSTACK_DEPTH
Copyright (C) 2026 HJimmyK (Jericho Knox)
mp_ssize_t maxdepth
mp_size_t memsize[16]
void * mem[16]
mp_ssize_t tempdepth
mp_size_t lenw
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
int64_t mp_ssize_t
定义 lmmp.h:95
uint64_t mp_limb_t
定义 lmmp.h:92
#define numb
#define n