LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
fft_fuse.c 文件参考
#include "lmmpn/fft_ssa.h"
fft_fuse.c 的引用(Include)关系图:

浏览该文件的源代码.

函数

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)

函数说明

◆ lmmp_fft_bfy_fused_()

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
警告
0<shl<64, 0<=w<=l, sep(numc,[numa|numb]), l>0, 各指针非空;实现见 lmmpn/arch/generic/fft_fuse.c(C)与 arch/{x64,arm64}/fft_fuse.S

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

87 {
88 const unsigned rshl = LIMB_BITS - shl;
89 mp_limb_t ca = 0, b = 0, prev = 0;
90
91 // 扫描1: numc[w+j] = (numa[j]-numb[j])<<shl 接链, numa[j] += numb[j]
92 for (mp_size_t j = 0; j < l - w; j++) {
93 mp_limb_t x = numa[j], y = numb[j];
94
95 mp_limb_t u = x - y;
96 mp_limb_t d = u - b;
97 b = (u > x) + (d > u);
98
99 __uint128_t s = (__uint128_t)x + y + ca;
100 numa[j] = (mp_limb_t)s;
101 ca = (mp_limb_t)(s >> 64);
102
103 numc[w + j] = (d << shl) | (prev >> rshl);
104 prev = d;
105 }
106
107 // 中点 ch 分解(acyo 链续, scyo/shl 链重置)
108 {
109 mp_limb_t shlcy = prev >> rshl;
110 mp_limb_t adj = b << shl;
111 out[0] = (shlcy >= adj) ? shlcy - adj : 0;
112 out[1] = (shlcy >= adj) ? 0 : adj - shlcy;
113 }
114 b = 0;
115 prev = 0;
116
117 // 扫描2: numc[j] = (numb[l-w+j]-numa[l-w+j])<<shl 接链, numa[l-w+j] += numb[l-w+j]
118 for (mp_size_t j = 0; j < w; j++) {
119 mp_limb_t x = numb[l - w + j], y = numa[l - w + j];
120
121 mp_limb_t u = x - y;
122 mp_limb_t d = u - b;
123 b = (u > x) + (d > u);
124
125 __uint128_t s = (__uint128_t)x + y + ca;
126 numa[l - w + j] = (mp_limb_t)s;
127 ca = (mp_limb_t)(s >> 64);
128
129 numc[j] = (d << shl) | (prev >> rshl);
130 prev = d;
131 }
132
133 out[2] = prev >> rshl;
134 out[3] = (ca << 1) | b;
135}
uint64_t mp_size_t
定义 lmmp.h:93
uint64_t mp_limb_t
定义 lmmp.h:92
#define LIMB_BITS
定义 lmmp.h:102
#define numb
#define s

引用了 LIMB_BITS, lmmp_fft_bfy_fused_(), numb , 以及 s.

被这些函数引用 lmmp_fft_bfy_() , 以及 lmmp_fft_bfy_fused_().

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

◆ lmmp_ifft_bfy_fused_()

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)

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

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比特级右移量
警告
0<shr<64, 0<=w<=l, sep(numc,[numa|numb]), l>0, 各指针非空;实现见 lmmpn/arch/generic/fft_fuse.c(C)与 arch/{x64,arm64}/fft_fuse.S
返回
打包进位 (acy_final << 1) | bcy_final(acy 为 numa 链,bcy 为 numc 链)

在文件 fft_fuse.c 第 35 行定义.

36 {
37 const unsigned rshr = LIMB_BITS - shr;
38 mp_limb_t acy = 0, bcy = 0; // acy=numa 链, bcy=numc 链(各段进出解包/重包)
39 mp_limb_t cur;
40
41 // 扫描1: numc[l-w+i] = numa[l-w+i] + t, numa[l-w+i] -= t(和→numc 即 bcy, 差→numa 即 acy)
42 cur = numb[0];
43 {
44 mp_limb_t ca = bcy, k = 1 - acy;
45 for (mp_size_t i = 0; i < w; i++) {
46 mp_limb_t nx = (i + 1 < w) ? numb[i + 1] : numb[w]; // 顶 limb 的 hi 来自 numb[w]
47 mp_limb_t t = (cur >> shr) | (nx << rshr);
48 cur = nx;
49 mp_limb_t a = numa[l - w + i];
50
51 __uint128_t s = (__uint128_t)a + t + ca;
52 __uint128_t d = (__uint128_t)a + ~t + k;
53 numc[l - w + i] = (mp_limb_t)s;
54 numa[l - w + i] = (mp_limb_t)d;
55 ca = (mp_limb_t)(s >> 64);
56 k = (mp_limb_t)(d >> 64);
57 }
58 bcy = ca;
59 acy = 1 - k;
60 }
61
62 // 扫描2: numc[i] = numa[i] - t', numa[i] += t'(和→numa 即 acy, 差→numc 即 bcy)
63 cur = numb[w];
64 {
65 mp_limb_t ca = acy, k = 1 - bcy;
66 for (mp_size_t i = 0; i < l - w; i++) {
67 mp_limb_t nx = (i + 1 < l - w) ? numb[w + i + 1] : numb[l]; // 顶 limb 的 hi 来自 numb[l]
68 mp_limb_t t = (cur >> shr) | (nx << rshr);
69 cur = nx;
70 mp_limb_t a = numa[i];
71
72 __uint128_t s = (__uint128_t)a + t + ca;
73 __uint128_t d = (__uint128_t)a + ~t + k;
74 numa[i] = (mp_limb_t)s;
75 numc[i] = (mp_limb_t)d;
76 ca = (mp_limb_t)(s >> 64);
77 k = (mp_limb_t)(d >> 64);
78 }
79 acy = ca;
80 bcy = 1 - k;
81 }
82
83 return (acy << 1) | bcy;
84}
#define k
#define t

引用了 k, LIMB_BITS, lmmp_ifft_bfy_fused_(), numb, s , 以及 t.

被这些函数引用 lmmp_ifft_bfy_() , 以及 lmmp_ifft_bfy_fused_().

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