|
LMMP 4.3.0
Lamina High-Precision Arithmetic Library
|
#include "lmmp/lmmpn.h"结构体 | |
| struct | fft_memstack |
宏定义 | |
| #define | FFT_MEMSTACK_DEPTH 16 |
| Copyright (C) 2026 HJimmyK (Jericho Knox) | |
函数 | |
| void | lmmp_fft_ (fft_memstack *ms, mp_ptr *coef, mp_size_t k, mp_size_t w) |
| 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_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 分解,单次调用完成) | |
| 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内存栈的分配/释放接口 | |
| 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) |
| 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 | |
| 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) |
| ifft 蝶形数据面融合内核(两段扫描 + 连续进位链,单次调用完成) | |
| 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 乘法的结果合并 | |
| struct fft_memstack |
| 成员变量 | ||
|---|---|---|
| mp_size_t | lenw | |
| mp_ssize_t | maxdepth | |
| void * | mem[16] | |
| mp_size_t | memsize[16] | |
| mp_ptr | temp_coef | |
| mp_ssize_t | tempdepth | |
| #define FFT_MEMSTACK_DEPTH 16 |
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
被这些函数引用 lmmp_fft_memstack_().
| void lmmp_fft_ | ( | 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_().
查找对于 m>=n 的模 B^m+1 FFT运算的最优k值
| n | - 输入的机器字长度 |
引用了 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_().
| 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) |
| wing | b的索引 |
| w | 左移的比特数(0<=w<n) |
引用了 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_().
| 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 分解,单次调用完成)
扫描1(j∈[0,l-w)):D = numa[j] - numb[j] (-scyo 链,起点0) numc[w+j] = (D << shl) 接 shl 移位链(起点0) numa[j] = numa[j] + numb[j] (+acyo 链,起点0) 中点:ch = shlcy1 - (scyo1 << shl) 分解为 chp/chn(scyo1/shlcy1 为扫描1终值) 扫描2(j∈[0,w)):D2 = numb[l-w+j] - numa[l-w+j] (-scyo 链重置0) numc[j] = (D2 << shl) 接 shl 链(重置0) numa[l-w+j] += numb[l-w+j] (+acyo 链续)
| numc | 蝶形输出系数指针(temp_coef) |
| numa | 系数 a 指针(原地加) |
| numb | 系数 b 指针(只读) |
| l | 系数长度(ms->lenw) |
| w | 机器字级移位量(0<=w<=l) |
| shl | 比特级左移量 |
| out | 输出数组(至少 4 个 limb):out[0]=chp, out[1]=chn, out[2]=shlcy2(扫描2 shl 链移出位),out[3]=(acy_final<<1)|scyo_final |
在文件 fft_fuse.c 第 86 行定义.
引用了 LIMB_BITS, lmmp_fft_bfy_fused_(), numb , 以及 s.
被这些函数引用 lmmp_fft_bfy_() , 以及 lmmp_fft_bfy_fused_().
| 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 | 输出系数的机器字长度 |
引用了 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_().
| void * lmmp_fft_memstack_ | ( | fft_memstack * | ms, |
| mp_size_t | size ) |
FFT内存栈的分配/释放接口
| ms | 内存栈结构体栈帧 |
| size | 分配大小(字节),size=0表示释放当前层内存 |
引用了 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_().
| 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) |
引用了 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_().
| 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_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_().
| void lmmp_ifft_ | ( | 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_().
| 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) |
| wing | b的索引 |
| w | 左移的比特数(0<=w<n) |
引用了 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_().
| 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 ) |
ifft 蝶形数据面融合内核(两段扫描 + 连续进位链,单次调用完成)
Copyright (C) 2026 HJimmyK (Jericho Knox)
以 t_i = [numb]>>shr 的逐 limb 流水线(numb 全程只读,不回写移位结果): 扫描1(i∈[0,w)):numc[l-w+i] = numa[l-w+i] + t_i (+bcy 链) numa[l-w+i] -= t_i (+acy 链) 扫描2(i∈[0,l-w)):numc[i] = numa[i] - t'_i (+bcy 链续) numa[i] += t'_i (+acy 链续),t'_i 从 numb[w] 起算 两段扫描的顶 limb 分别从 numb[w]、numb[l] 取高 shr 位(内核自行加载)
| numc | 蝶形输出系数指针(temp_coef) |
| numa | 系数 a 指针(原地加减) |
| numb | 系数 b 指针(只读,须有 l+1 个 limb 可读) |
| l | 系数长度(ms->lenw) |
| w | 机器字级移位量(0<=w<=l) |
| shr | 比特级右移量 |
ifft 蝶形数据面融合内核(两段扫描 + 连续进位链,单次调用完成)
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_fuse.c 第 35 行定义.
引用了 k, LIMB_BITS, lmmp_ifft_bfy_fused_(), numb, s , 以及 t.
被这些函数引用 lmmp_ifft_bfy_() , 以及 lmmp_ifft_bfy_fused_().
| 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 | 输出结果数组 |
| pfca | FFT系数数组指针数组 |
| K | FFT块数(2^k) |
| k | FFT层数 |
| n | 系数总比特数 |
| M | 每个块的比特数 |
| rn | 结果长度(机器字) |
引用了 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_().