|
LMMP 4.3.0
Lamina High-Precision Arithmetic Library
|
宏定义 | |
| #define | _FFT_TABLE_ENTRY(n) |
| Copyright (C) 2026 HJimmyK (Jericho Knox) | |
| #define | _FFT_TABLE_ENTRY4(n) |
| #define | FFT_TABLE_MAX_ROWS 68 |
函数 | |
| void | lmmp_fft_ (fft_memstack *ms, mp_ptr *coef, mp_size_t k, mp_size_t w) |
| static void | lmmp_fft_4_ (fft_memstack *ms, mp_ptr *coef, mp_size_t k, mp_size_t w) |
| static void | lmmp_fft_b1_ (fft_memstack *ms, mp_ptr *coef, mp_size_t dis, mp_size_t k, mp_size_t w, mp_size_t w0) |
| 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_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内存栈的分配/释放接口 | |
| mp_size_t | lmmp_fft_next_size_ (mp_size_t n) |
| 计算满足 >=n 的最小费马/梅森乘法可行尺寸 | |
| 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) |
| static void | lmmp_ifft_4_ (fft_memstack *ms, mp_ptr *coef, mp_size_t k, mp_size_t w) |
| static void | lmmp_ifft_b1_ (fft_memstack *ms, mp_ptr *coef, mp_size_t dis, mp_size_t k, mp_size_t w, mp_size_t w0) |
| 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 | |
| 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 乘法的结果合并 | |
变量 | |
| static const mp_size_t | lmmp_fft_table_ [][2] |
| #define _FFT_TABLE_ENTRY | ( | n | ) |
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
| #define _FFT_TABLE_ENTRY4 | ( | n | ) |
| 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_().
|
static |
引用了 k, lmmp_fft_4_() , 以及 lmmp_fft_bfy_().
被这些函数引用 lmmp_fft_() , 以及 lmmp_fft_4_().
|
static |
引用了 k, lmmp_fft_b1_(), lmmp_fft_bfy_() , 以及 w0.
被这些函数引用 lmmp_fft_() , 以及 lmmp_fft_b1_().
查找对于 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_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_().
计算满足 >=n 的最小费马/梅森乘法可行尺寸
| n | 输入的目标尺寸 |
引用了 k, lmmp_debug_assert, lmmp_fft_best_k_(), lmmp_fft_next_size_(), LOG2_LIMB_BITS , 以及 n.
被这些函数引用 bench_mul_mersenne_fft(), lmmp_binvert_unbalance_(), lmmp_div_mulinv_(), lmmp_divexact_mu_run_(), lmmp_fft_next_size_(), lmmp_hgcd_apply_mod_(), lmmp_mersenne_next_size_(), lmmp_mont_init_(), lmmp_mont_need_(), lmmp_mul_fft_(), lmmp_mul_fft_unbalance_(), lmmp_mul_mersenne_(), lmmp_mul_toom62_unbalance_(), lmmp_mullo_fft_(), lmmp_mullo_fft_cache_init_(), lmmp_sqr_fft_(), lmmp_sqr_mersenne_() , 以及 TEST_CASE().
| 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_().
|
static |
引用了 k, lmmp_ifft_4_() , 以及 lmmp_ifft_bfy_().
被这些函数引用 lmmp_ifft_() , 以及 lmmp_ifft_4_().
|
static |
引用了 k, lmmp_ifft_b1_(), lmmp_ifft_bfy_() , 以及 w0.
被这些函数引用 lmmp_ifft_() , 以及 lmmp_ifft_b1_().
| 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_().
| 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_().
|
static |
被这些函数引用 lmmp_fft_best_k_().