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

浏览该文件的源代码.

宏定义

#define BINVERT_255_   ((mp_limb_t)0xFEFEFEFEFEFEFEFF)
#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 + 11 * n)
#define r2   (dst + 7 * n)
#define r4   (dst + n3)

函数

void lmmp_toom_interp12_ (mp_ptr dst, mp_ptr r1, mp_ptr r3, mp_ptr r5, mp_size_t n, mp_size_t spt, int half, mp_ptr tp)
 Toom插值计算(12点插值):用于 Toom-6.5(toom6h/toom6 平方)乘法 评估点:inf(仅 half), ±4, ±2, ±1, ±1/2, ±1/4, 0

宏定义说明

◆ BINVERT_255_

#define BINVERT_255_   ((mp_limb_t)0xFEFEFEFEFEFEFEFF)

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

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

◆ BINVERT_2835_

#define BINVERT_2835_   ((mp_limb_t)0x938CC70553E3771B)

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

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

◆ BINVERT_42525_

#define BINVERT_42525_   ((mp_limb_t)0xE7B40D449F314C35)

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

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

◆ BINVERT_9_

#define BINVERT_9_   ((mp_limb_t)0x8E38E38E38E38E39)

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

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

◆ 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_interp12.c 第 27 行定义.

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

◆ r0

#define r0   (dst + 11 * n)

◆ r2

#define r2   (dst + 7 * n)

◆ r4

#define r4   (dst + n3)

函数说明

◆ lmmp_toom_interp12_()

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

Toom插值计算(12点插值):用于 Toom-6.5(toom6h/toom6 平方)乘法 评估点:inf(仅 half), ±4, ±2, ±1, ±1/2, ±1/4, 0

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

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

42 {
43 mp_limb_t cy, cy2;
44 mp_size_t n3, n3p1;
45 n3 = 3 * n;
46 n3p1 = n3 + 1;
47
49 lmmp_param_assert(spt > 0);
50 lmmp_param_assert(spt <= 2 * n);
51
52#define r4 (dst + n3) /* 3n+1 */
53#define r2 (dst + 7 * n) /* 3n+1 */
54#define r0 (dst + 11 * n) /* spt <= 2n */
55
56 /* 插值序列(值引用为混合后的和/差半边):
57 r? <- (r? - r0*x)/d 的消顶部项 + 交叉消元 + 精确除,最后重组 */
58
59 if (half != 0) {
60 cy = lmmp_sub_n_(r3, r3, r0, spt);
61 lmmp_dec_1(r3 + spt, cy);
62
63 cy = lmmp_submul_1_(r2, r0, spt, (mp_limb_t)1 << 10);
64 lmmp_dec_1(r2 + spt, cy);
65 DO_subrsh(r5, n3p1, r0, spt, 2);
66
67 cy = lmmp_submul_1_(r1, r0, spt, (mp_limb_t)1 << 20);
68 lmmp_dec_1(r1 + spt, cy);
69 DO_subrsh(r4, n3p1, r0, spt, 4);
70 }
71
72 r4[n3] -= lmmp_submul_1_(r4 + n, dst, 2 * n, (mp_limb_t)1 << 20);
73 DO_subrsh(r1 + n, 2 * n + 1, dst, 2 * n, 4);
74
75 lmmp_add_n_sub_n_(r1, r4, r4, r1, n3p1);
76
77 r5[n3] -= lmmp_submul_1_(r5 + n, dst, 2 * n, (mp_limb_t)1 << 10);
78 DO_subrsh(r2 + n, 2 * n + 1, dst, 2 * n, 2);
79
80 lmmp_add_n_sub_n_(r2, r5, r5, r2, n3p1);
81
82 r3[n3] -= lmmp_sub_n_(r3 + n, r3 + n, dst, 2 * n);
83
84 lmmp_submul_1_(r4, r5, n3p1, 257);
85 /* 随后除以 2835*4,操作数可能为负(补码) */
86 lmmp_divexact_odd_pi_(r4, r4, n3p1, 2835, BINVERT_2835_, 2);
87 if ((r4[n3] & (LIMB_MAX << (LIMB_BITS - 3))) != 0)
88 r4[n3] |= LIMB_MAX << (LIMB_BITS - 2);
89
90 lmmp_addmul_1_(r5, r4, n3p1, 60);
91 lmmp_divexact_odd_pi_(r5, r5, n3p1, 255, BINVERT_255_, 0);
92
93 cy = lmmp_submul_1_(r2, r3, n3p1, (mp_limb_t)1 << 5);
94 lmmp_debug_assert(cy == 0);
95
96 cy = lmmp_submul_1_(r1, r2, n3p1, 100);
97 lmmp_debug_assert(cy == 0);
98 cy = lmmp_submul_1_(r1, r3, n3p1, (mp_limb_t)1 << 9);
99 lmmp_debug_assert(cy == 0);
100 lmmp_divexact_odd_pi_(r1, r1, n3p1, 42525, BINVERT_42525_, 0);
101
102 cy = lmmp_submul_1_(r2, r1, n3p1, 225);
103 lmmp_debug_assert(cy == 0);
104 lmmp_divexact_odd_pi_(r2, r2, n3p1, 9, BINVERT_9_, 2);
105
106 cy = lmmp_sub_n_(r3, r3, r2, n3p1);
107 lmmp_debug_assert(cy == 0);
108
109 lmmp_shr1sub_n_(r4, r2, r4, n3p1);
110 r4[n3p1 - 1] &= LIMB_MAX >> 1;
111 cy = lmmp_sub_n_(r2, r2, r4, n3p1);
112 lmmp_debug_assert(cy == 0);
113
114 lmmp_shr1add_n_(r5, r5, r1, n3p1);
115 r5[n3p1 - 1] &= LIMB_MAX >> 1;
116
117 /* 最后两步插值(可并入重组) */
118 cy = lmmp_sub_n_(r3, r3, r1, n3p1);
119 lmmp_debug_assert(cy == 0);
120 cy = lmmp_sub_n_(r1, r1, r5, n3p1);
121 lmmp_debug_assert(cy == 0);
122
123 (void)tp; /* 现有原语集(submul/addmul/原生 add_n_sub_n)不消耗临时区 */
124
125 /***************************** 重组 *******************************/
126 /*
127 dst 操作前:
128 |M r0|L r0|___||H r2|M r2|L r2|___||H r4|M r4|L r4|____|H r8|L r8|dst
129 求和方案:
130 |__12|n_11|n_10|n__9|n__8|n__7|n__6|n__5|n__4|n__3|n__2|n___|n___|dst
131 |M r0|L r0|___||H r2|M r2|L r2|___||H r4|M r4|L r4|____|H_r8|L_r8|dst
132 ||H r1|M r1|L r1| ||H r3|M r3|L r3| ||H_r5|M_r5|L_r5|
133 */
134
135 cy = lmmp_add_n_(dst + n, dst + n, r5, n);
136 cy = lmmp_add_1_(dst + 2 * n, r5 + n, n, cy);
137 cy = r5[n3] + lmmp_add_nc_(dst + n3, dst + n3, r5 + 2 * n, n, cy);
138 lmmp_inc_1(dst + n3 + n, cy);
139
140 dst[2 * n3] += lmmp_add_n_(dst + 5 * n, dst + 5 * n, r3, n);
141 cy = lmmp_add_1_(dst + 2 * n3, r3 + n, n, dst[2 * n3]);
142 cy = r3[n3] + lmmp_add_nc_(dst + 7 * n, dst + 7 * n, r3 + 2 * n, n, cy);
143 lmmp_inc_1(dst + 8 * n, cy);
144
145 dst[10 * n] += lmmp_add_n_(dst + 9 * n, dst + 9 * n, r1, n);
146 if (half) {
147 cy = lmmp_add_1_(dst + 10 * n, r1 + n, n, dst[10 * n]);
148 if (spt > n) {
149 cy = r1[n3] + lmmp_add_nc_(dst + 11 * n, dst + 11 * n, r1 + 2 * n, n, cy);
150 lmmp_inc_1(dst + 4 * n3, cy);
151 } else {
152 cy2 = lmmp_add_nc_(dst + 11 * n, dst + 11 * n, r1 + 2 * n, spt, cy);
153 lmmp_debug_assert(cy2 == 0);
154 }
155 } else {
156 cy = lmmp_add_1_(dst + 10 * n, r1 + n, spt, dst[10 * n]);
157 lmmp_debug_assert(cy == 0);
158 }
159
160#undef r4
161#undef r2
162#undef r0
163}
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 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_

引用了 BINVERT_255_, 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_interp12_(), n, r0, r1, r2, r3, r4, r5 , 以及 tp.

被这些函数引用 lmmp_mul_toom6h_(), lmmp_sqr_toom6_() , 以及 lmmp_toom_interp12_().

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