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

浏览该文件的源代码.

宏定义

#define BINVERT_255_   ((mp_limb_t)0xFEFEFEFEFEFEFEFF)
#define BINVERT_255x182712915_   ((mp_limb_t)0x1B649A076FC4CB25)
#define BINVERT_255x188513325_   ((mp_limb_t)0x06DB993A6864275B)
#define BINVERT_2835_   ((mp_limb_t)0x938CC70553E3771B)
#define BINVERT_42525_   ((mp_limb_t)0xE7B40D449F314C35)
#define BINVERT_9_   ((mp_limb_t)0x8E38E38E38E38E39)
#define DO_subrsh(dst, nd, src, ns, s)
 Copyright (C) 2026 HJimmyK (Jericho Knox)
#define r0   (dst + 15 * n)
#define r2   (dst + 11 * n)
#define r4   (dst + 7 * n)
#define r6   (dst + n3)

函数

void lmmp_toom_interp16_ (mp_ptr dst, mp_ptr r1, mp_ptr r3, mp_ptr r5, mp_ptr r7, mp_size_t n, mp_size_t spt, int half, mp_ptr tp)
 Toom插值计算(16点插值):用于 Toom-8.5(toom8h/toom8 平方)乘法 评估点:inf(仅 half), ±8, ±4, ±2, ±1, ±1/2, ±1/4, ±1/8, 0

宏定义说明

◆ BINVERT_255_

#define BINVERT_255_   ((mp_limb_t)0xFEFEFEFEFEFEFEFF)

在文件 mul_toom_interp16.c 第 36 行定义.

◆ BINVERT_255x182712915_

#define BINVERT_255x182712915_   ((mp_limb_t)0x1B649A076FC4CB25)

在文件 mul_toom_interp16.c 第 39 行定义.

被这些函数引用 lmmp_toom_interp16_().

◆ BINVERT_255x188513325_

#define BINVERT_255x188513325_   ((mp_limb_t)0x06DB993A6864275B)

在文件 mul_toom_interp16.c 第 40 行定义.

被这些函数引用 lmmp_toom_interp16_().

◆ BINVERT_2835_

#define BINVERT_2835_   ((mp_limb_t)0x938CC70553E3771B)

在文件 mul_toom_interp16.c 第 37 行定义.

◆ BINVERT_42525_

#define BINVERT_42525_   ((mp_limb_t)0xE7B40D449F314C35)

在文件 mul_toom_interp16.c 第 38 行定义.

◆ BINVERT_9_

#define BINVERT_9_   ((mp_limb_t)0x8E38E38E38E38E39)

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

◆ DO_subrsh

#define DO_subrsh ( dst,
nd,
src,
ns,
s )
值:
do { \
mp_limb_t __cy; \
lmmp_dec_1((dst), (src)[0] >> (s)); \
__cy = lmmp_submul_1_((dst), (src) + 1, (ns) - 1, (mp_limb_t)1 << (LIMB_BITS - (s))); \
lmmp_dec_1((dst) + (ns) - 1, __cy); \
} while (0)
uint64_t mp_limb_t
定义 lmmp.h:92
#define LIMB_BITS
定义 lmmp.h:102
mp_limb_t lmmp_submul_1_(mp_ptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t b)
乘以单limb并累减操作 [numa,n] -= [numb,n] * b
#define s

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

在文件 mul_toom_interp16.c 第 27 行定义.

◆ r0

#define r0   (dst + 15 * n)

◆ r2

#define r2   (dst + 11 * n)

◆ r4

#define r4   (dst + 7 * n)

◆ r6

#define r6   (dst + n3)

函数说明

◆ lmmp_toom_interp16_()

void lmmp_toom_interp16_ ( mp_ptr dst,
mp_ptr r1,
mp_ptr r3,
mp_ptr r5,
mp_ptr r7,
mp_size_t n,
mp_size_t spt,
int half,
mp_ptr tp )

Toom插值计算(16点插值):用于 Toom-8.5(toom8h/toom8 平方)乘法 评估点:inf(仅 half), ±8, ±4, ±2, ±1, ±1/2, ±1/4, ±1/8, 0

参数
dst结果缓冲区(half ? 15n+spt : 14n+spt limbs) r8=f(0) 在 [dst,2n],r6 在 [dst+3n,3n+1],r4 在 [dst+7n,3n+1], r2 在 [dst+11n,3n+1],r0 在 [dst+15n,spt]
r1输入/临时:±8 点对混合后的奇系数(3n+1 limbs)
r3输入/临时:±2 点对(3n+1 limbs)
r5输入/临时:±1/4 点对(3n+1 limbs)
r7输入/临时:±1/8 点对(3n+1 limbs)
n每段标准 limb 长度
spt顶部系数 r0 的长度(0<spt<=2n)
half非零表示乘积多项式次数为奇(需要 inf 点,r0 有效)
tp临时缓存(3n+1 limbs)
注解
r1=f(±8), r2=f(±4), r3=f(±2), r4=f(±1), r5=f(±1/4), r6=f(±1/2), r7=f(±1/8);各 ± 点对须先经 lmmp_toom_couple_handling_ 混合; 负中间值以补码存放,输入被破坏
警告
n>0, 0<spt<=2n, sep(tp,[dst|r1|r3|r5|r7])

在文件 mul_toom_interp16.c 第 42 行定义.

44 {
45 mp_limb_t cy, cy2;
46 mp_size_t n3, n3p1;
47 n3 = 3 * n;
48 n3p1 = n3 + 1;
49
51 lmmp_param_assert(spt > 0);
52 lmmp_param_assert(spt <= 2 * n);
53
54#define r6 (dst + n3) /* 3n+1 */
55#define r4 (dst + 7 * n) /* 3n+1 */
56#define r2 (dst + 11 * n) /* 3n+1 */
57#define r0 (dst + 15 * n) /* spt <= 2n */
58
59 if (half != 0) {
60 cy = lmmp_sub_n_(r4, r4, r0, spt);
61 lmmp_dec_1(r4 + spt, cy);
62
63 cy = lmmp_submul_1_(r3, r0, spt, (mp_limb_t)1 << 14);
64 lmmp_dec_1(r3 + spt, cy);
65 DO_subrsh(r6, n3p1, r0, spt, 2);
66
67 cy = lmmp_submul_1_(r2, r0, spt, (mp_limb_t)1 << 28);
68 lmmp_dec_1(r2 + spt, cy);
69 DO_subrsh(r5, n3p1, r0, spt, 4);
70
71 cy = lmmp_submul_1_(r1, r0, spt, (mp_limb_t)1 << 42);
72 lmmp_dec_1(r1 + spt, cy);
73 DO_subrsh(r7, n3p1, r0, spt, 6);
74 }
75
76 r5[n3] -= lmmp_submul_1_(r5 + n, dst, 2 * n, (mp_limb_t)1 << 28);
77 DO_subrsh(r2 + n, 2 * n + 1, dst, 2 * n, 4);
78
79 lmmp_add_n_sub_n_(r2, r5, r5, r2, n3p1);
80
81 r6[n3] -= lmmp_submul_1_(r6 + n, dst, 2 * n, (mp_limb_t)1 << 14);
82 DO_subrsh(r3 + n, 2 * n + 1, dst, 2 * n, 2);
83
84 lmmp_add_n_sub_n_(r3, r6, r6, r3, n3p1);
85
86 r7[n3] -= lmmp_submul_1_(r7 + n, dst, 2 * n, (mp_limb_t)1 << 42);
87 DO_subrsh(r1 + n, 2 * n + 1, dst, 2 * n, 6);
88
89 lmmp_add_n_sub_n_(r1, r7, r7, r1, n3p1);
90
91 r4[n3] -= lmmp_sub_n_(r4 + n, r4 + n, dst, 2 * n);
92
93 lmmp_submul_1_(r5, r6, n3p1, 1028);
94 lmmp_submul_1_(r7, r5, n3p1, 1300);
95 lmmp_submul_1_(r7, r6, n3p1, 1052688);
96 lmmp_divexact_odd_pi_(r7, r7, n3p1, (mp_limb_t)255 * 188513325, BINVERT_255x188513325_, 0);
97
98 lmmp_submul_1_(r5, r7, n3p1, 12567555);
99 /* 随后除以 2835*64,操作数可能为负(补码) */
100 lmmp_divexact_odd_pi_(r5, r5, n3p1, 2835, BINVERT_2835_, 6);
101 if ((r5[n3] & (LIMB_MAX << (LIMB_BITS - 7))) != 0)
102 r5[n3] |= LIMB_MAX << (LIMB_BITS - 6);
103
104 lmmp_submul_1_(r6, r7, n3p1, 4095);
105 lmmp_addmul_1_(r6, r5, n3p1, 240);
106 /* 随后除以 255*4,操作数可能为负(补码) */
107 lmmp_divexact_odd_pi_(r6, r6, n3p1, 255, BINVERT_255_, 2);
108 if ((r6[n3] & (LIMB_MAX << (LIMB_BITS - 3))) != 0)
109 r6[n3] |= LIMB_MAX << (LIMB_BITS - 2);
110
111 cy = lmmp_submul_1_(r3, r4, n3p1, (mp_limb_t)1 << 7);
112 lmmp_debug_assert(cy == 0);
113
114 cy = lmmp_submul_1_(r2, r4, n3p1, (mp_limb_t)1 << 13);
115 lmmp_debug_assert(cy == 0);
116 cy = lmmp_submul_1_(r2, r3, n3p1, 400);
117 lmmp_debug_assert(cy == 0);
118
119 lmmp_submul_1_(r1, r4, n3p1, (mp_limb_t)1 << 19);
120 lmmp_submul_1_(r1, r2, n3p1, 1428);
121 lmmp_submul_1_(r1, r3, n3p1, 112896);
122 lmmp_divexact_odd_pi_(r1, r1, n3p1, (mp_limb_t)255 * 182712915, BINVERT_255x182712915_, 0);
123
124 cy = lmmp_submul_1_(r2, r1, n3p1, 15181425);
125 lmmp_debug_assert(cy == 0);
126 lmmp_divexact_odd_pi_(r2, r2, n3p1, 42525, BINVERT_42525_, 4);
127
128 cy = lmmp_submul_1_(r3, r1, n3p1, 3969);
129 lmmp_debug_assert(cy == 0);
130 cy = lmmp_submul_1_(r3, r2, n3p1, 900);
131 lmmp_debug_assert(cy == 0);
132 lmmp_divexact_odd_pi_(r3, r3, n3p1, 9, BINVERT_9_, 4);
133
134 cy = lmmp_sub_n_(r4, r4, r1, n3p1);
135 lmmp_debug_assert(cy == 0);
136 cy = lmmp_sub_n_(r4, r4, r3, n3p1);
137 lmmp_debug_assert(cy == 0);
138 cy = lmmp_sub_n_(r4, r4, r2, n3p1);
139 lmmp_debug_assert(cy == 0);
140
141 lmmp_shr1add_n_(r6, r2, r6, n3p1);
142 r6[n3p1 - 1] &= LIMB_MAX >> 1;
143 cy = lmmp_sub_n_(r2, r2, r6, n3p1);
144 lmmp_debug_assert(cy == 0);
145
146 lmmp_shr1sub_n_(r5, r3, r5, n3p1);
147 r5[n3p1 - 1] &= LIMB_MAX >> 1;
148 cy = lmmp_sub_n_(r3, r3, r5, n3p1);
149 lmmp_debug_assert(cy == 0);
150
151 lmmp_shr1add_n_(r7, r1, r7, n3p1);
152 r7[n3p1 - 1] &= LIMB_MAX >> 1;
153 cy = lmmp_sub_n_(r1, r1, r7, n3p1);
154 lmmp_debug_assert(cy == 0);
155
156 (void)tp; /* 现有原语集(submul/addmul/原生 add_n_sub_n)不消耗临时区 */
157
158 /***************************** 重组 *******************************/
159 /*
160 dst 操作前:
161 |M r0|L r0|___||H r2|M r2|L r2|___||H r4|M r4|L r4|___||H r6|M r6|L r6|____|H_r8|L_r8|dst
162 求和方案:
163 |__16|n_15|n_14|n_13|n_12|n_11|n_10|n__9|n__8|n__7|n__6|n__5|n__4|n__3|n__2|n___|n___|dst
164 |M r0|L r0|___||H r2|M r2|L r2|___||H r4|M r4|L r4|___||H r6|M r6|L r6|____|H_r8|L_r8|dst
165 ||H r1|M r1|L r1| ||H r3|M r3|L r3| ||H_r5|M_r5|L_r5| ||H_r7|M_r7|L_r7|
166 */
167
168 cy = lmmp_add_n_(dst + n, dst + n, r7, n);
169 cy = lmmp_add_1_(dst + 2 * n, r7 + n, n, cy);
170 cy = r7[n3] + lmmp_add_nc_(dst + n3, dst + n3, r7 + 2 * n, n, cy);
171 lmmp_inc_1(dst + 4 * n, cy);
172
173 dst[2 * n3] += lmmp_add_n_(dst + 5 * n, dst + 5 * n, r5, n);
174 cy = lmmp_add_1_(dst + 2 * n3, r5 + n, n, dst[2 * n3]);
175 cy = r5[n3] + lmmp_add_nc_(dst + 7 * n, dst + 7 * n, r5 + 2 * n, n, cy);
176 lmmp_inc_1(dst + 8 * n, cy);
177
178 dst[10 * n] += lmmp_add_n_(dst + 9 * n, dst + 9 * n, r3, n);
179 cy = lmmp_add_1_(dst + 10 * n, r3 + n, n, dst[10 * n]);
180 cy = r3[n3] + lmmp_add_nc_(dst + 11 * n, dst + 11 * n, r3 + 2 * n, n, cy);
181 lmmp_inc_1(dst + 12 * n, cy);
182
183 dst[14 * n] += lmmp_add_n_(dst + 13 * n, dst + 13 * n, r1, n);
184 if (half) {
185 cy = lmmp_add_1_(dst + 14 * n, r1 + n, n, dst[14 * n]);
186 if (spt > n) {
187 cy = r1[n3] + lmmp_add_nc_(dst + 15 * n, dst + 15 * n, r1 + 2 * n, n, cy);
188 lmmp_inc_1(dst + 16 * n, cy);
189 } else {
190 cy2 = lmmp_add_nc_(dst + 15 * n, dst + 15 * n, r1 + 2 * n, spt, cy);
191 lmmp_debug_assert(cy2 == 0);
192 }
193 } else {
194 cy = lmmp_add_1_(dst + 14 * n, r1 + n, spt, dst[14 * n]);
195 lmmp_debug_assert(cy == 0);
196 }
197
198#undef r6
199#undef r4
200#undef r2
201#undef r0
202}
mp_limb_t lmmp_divexact_odd_pi_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t d, mp_limb_t di, unsigned shr)
通用奇除数精确除,可带 2^shr 因子: [dst,na] = [numa,na] / (d*2^shr),其中 d 为奇数、di = d^(-1) mod B
uint64_t mp_size_t
定义 lmmp.h:93
#define lmmp_debug_assert(x)
定义 lmmp.h:498
#define LIMB_MAX
定义 lmmp.h:105
#define lmmp_param_assert(x)
定义 lmmp.h:509
mp_limb_t lmmp_shr1add_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
加法后右移1位 [dst,n] = ([numa,n] + [numb,n]) >> 1
定义 shr.c:65
static mp_limb_t lmmp_add_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
加单精度数静态内联函数 [dst,na]=[numa,na]+x
mp_limb_t lmmp_add_nc_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t c)
带进位的n位加法 [dst,n] = [numa,n] + [numb,n] + c
定义 add_n.c:58
mp_limb_t lmmp_addmul_1_(mp_ptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t b)
乘以单limb并累加操作 [numa,n] += [numb,n] * b
定义 mul_1.c:76
mp_limb_t lmmp_add_n_sub_n_(mp_ptr dsta, mp_ptr dstb, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
同时执行n位加法和减法 ([dsta,n],[dstb,n]) = ([numa,n]+[numb,n],[numa,n]-[numb,n])
#define lmmp_dec_1(p, dec)
减指定值宏(预期无借位)
mp_limb_t lmmp_sub_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
无借位的n位减法 [dst,n] = [numa,n] - [numb,n]
定义 sub_n.c:84
mp_limb_t lmmp_shr1sub_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
减法后右移1位 [dst,n] = ([numa,n] - [numb,n]) >> 1
定义 shr.c:87
#define lmmp_inc_1(p, inc)
加指定值宏(预期无进位)
mp_limb_t lmmp_add_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
无进位的n位加法 [dst,n] = [numa,n] + [numb,n]
定义 add_n.c:76
#define r2
#define r1
#define r3
#define r0
#define tp
#define n
#define r4
#define r5
#define r6
#define r7
#define BINVERT_42525_
#define DO_subrsh(dst, nd, src, ns, s)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define BINVERT_9_
#define BINVERT_255_
#define BINVERT_2835_
#define BINVERT_255x182712915_
#define BINVERT_255x188513325_

引用了 BINVERT_255_, BINVERT_255x182712915_, BINVERT_255x188513325_, BINVERT_2835_, BINVERT_42525_, BINVERT_9_, DO_subrsh, LIMB_BITS, LIMB_MAX, lmmp_add_1_(), lmmp_add_n_(), lmmp_add_n_sub_n_(), lmmp_add_nc_(), lmmp_addmul_1_(), lmmp_debug_assert, lmmp_dec_1, lmmp_divexact_odd_pi_(), lmmp_inc_1, lmmp_param_assert, lmmp_shr1add_n_(), lmmp_shr1sub_n_(), lmmp_sub_n_(), lmmp_submul_1_(), lmmp_toom_interp16_(), n, r0, r1, r2, r3, r4, r5, r6, r7 , 以及 tp.

被这些函数引用 lmmp_mul_toom8h_(), lmmp_sqr_toom8_() , 以及 lmmp_toom_interp16_().

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