LMMP
4.3.0
Lamina High-Precision Arithmetic Library
Toggle main menu visibility
载入中...
搜索中...
未找到
fft_fuse.c
浏览该文件的文档.
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
/*
24
fft/ifft 蝶形数据面融合内核 lmmp_fft_bfy_fused_ / lmmp_ifft_bfy_fused_ 的 C 参考实现。
25
26
x64 汇编构建下符号由 arch/x64/fft_fuse.S 提供(本文件被构建系统排除);
27
GENERIC 与 arm64 汇编构建走此 C 实现(arm64 NEON 版待移植,由 CMake 补入)。
28
29
顺序流式访问(每 limb 恰好读写一次),不做 PART_SIZE 分块。
30
差链补码化同 add_n_sub_n_: d = a + ~t + k, k0 = 1 - b, 借位 = 1 - k。
31
*/
32
33
#include "
lmmpn/fft_ssa.h
"
34
35
mp_limb_t
lmmp_ifft_bfy_fused_
(
mp_ptr
numc,
mp_ptr
numa,
mp_ptr
numb
,
36
mp_size_t
l,
mp_size_t
w,
mp_size_t
shr) {
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
}
85
86
void
lmmp_fft_bfy_fused_
(
mp_ptr
numc,
mp_ptr
numa,
mp_ptr
numb
,
mp_size_t
l,
mp_size_t
w,
87
mp_size_t
shl,
mp_limb_t
* out) {
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
}
k
#define k
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 分解,单次调用完成)
定义
fft_fuse.c:86
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)
定义
fft_fuse.c:35
fft_ssa.h
mp_ptr
mp_limb_t * mp_ptr
定义
lmmp.h:96
mp_size_t
uint64_t mp_size_t
定义
lmmp.h:93
mp_limb_t
uint64_t mp_limb_t
定义
lmmp.h:92
LIMB_BITS
#define LIMB_BITS
定义
lmmp.h:102
t
#define t
numb
#define numb
s
#define s
src
lmmp
lmmpn
arch
generic
fft_fuse.c
生成于
, 为 LMMP使用
1.18.0