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

浏览该文件的源代码.

结构体

struct  toom62_cache_t

宏定义

#define a0   numa
#define a0   numa
#define a0   numa
#define a1   (numa + n)
#define a1   (numa + n)
#define a1   (numa + n)
#define a2   (numa + 2 * n)
#define a2   (numa + 2 * n)
#define a2   (numa + 2 * n)
#define a3   (numa + 3 * n)
#define a3   (numa + 3 * n)
#define a3   (numa + 3 * n)
#define a4   (numa + 4 * n)
#define a4   (numa + 4 * n)
#define a4   (numa + 4 * n)
#define a5   (numa + 5 * n)
#define a5   (numa + 5 * n)
#define a5   (numa + 5 * n)
#define b0   numb
#define b0   numb
#define b0   numb
#define b1   (numb + n)
#define b1   (numb + n)
#define b1   (numb + n)
#define bs1   (cache->bs1)
#define bs1   (cache->bs1)
#define bs2   (cache->bs2)
#define bs2   (cache->bs2)
#define bsh   (cache->bsh)
#define bsh   (cache->bsh)
#define bsm1   (cache->bsm1)
#define bsm1   (cache->bsm1)
#define bsm2   (cache->bsm2)
#define bsm2   (cache->bsm2)
#define lmmp_mul_n_(dst, numa, numb, n)
 Copyright (C) 2026 HJimmyK (Jericho Knox)
#define n   (cache->n)
#define n   (cache->n)
#define numb   (cache->numb)
#define numb   (cache->numb)
#define s   (cache->s)
#define s   (cache->s)
#define scratch   (cache->scratch)
#define scratch   (cache->scratch)
#define scratch_out   (scratch + 8 * n + 4)
#define scratch_out   (scratch + 8 * n + 4)
#define scratch_out   (scratch + 8 * n + 4)
#define t   (cache->t)
#define t   (cache->t)
#define tmp   (cache->tmp)
#define tmp   (cache->tmp)
#define v0   dst
#define v0   dst
#define v0   dst
#define v1   (dst + 2 * n)
#define v1   (dst + 2 * n)
#define v1   (dst + 2 * n)
#define v2   scratch
#define v2   scratch
#define v2   scratch
#define vh   (scratch + 4 * n + 2)
#define vh   (scratch + 4 * n + 2)
#define vh   (scratch + 4 * n + 2)
#define vinf   (dst + 6 * n)
#define vinf   (dst + 6 * n)
#define vinf   (dst + 6 * n)
#define vm1   (scratch + 6 * n + 3)
#define vm1   (scratch + 6 * n + 3)
#define vm1   (scratch + 6 * n + 3)
#define vm2   (scratch + 2 * n + 1)
#define vm2   (scratch + 2 * n + 1)
#define vm2   (scratch + 2 * n + 1)

函数

void lmmp_mul_toom62_ (mp_ptr restrict dst, mp_srcptr restrict numa, mp_size_t na, mp_srcptr restrict numb, mp_size_t nb)
static void lmmp_mul_toom62_cache_ (mp_ptr restrict dst, mp_srcptr restrict numa, const toom62_cache_t *cache, enum toom7_flags bflags)
static enum toom7_flags lmmp_mul_toom62_cache_init_ (mp_ptr restrict dst, mp_srcptr restrict numa, toom62_cache_t *cache)
void lmmp_mul_toom62_unbalance_ (mp_ptr restrict dst, mp_srcptr restrict numa, mp_size_t na, mp_srcptr restrict numb, mp_size_t nb)

结构体说明

◆ toom62_cache_t

struct toom62_cache_t

在文件 mul_toom62.c 第 239 行定义.

toom62_cache_t 的协作图:
成员变量
mp_ptr restrict bs1
mp_ptr restrict bs2
mp_ptr restrict bsh
mp_ptr restrict bsm1
mp_ptr restrict bsm2
mp_size_t n
mp_srcptr restrict numb
mp_size_t s
mp_ptr restrict scratch
mp_size_t t
mp_ptr restrict tmp

宏定义说明

◆ a0 [1/3]

#define a0   numa

◆ a0 [2/3]

#define a0   numa

◆ a0 [3/3]

#define a0   numa

◆ a1 [1/3]

#define a1   (numa + n)

◆ a1 [2/3]

#define a1   (numa + n)

◆ a1 [3/3]

#define a1   (numa + n)

◆ a2 [1/3]

#define a2   (numa + 2 * n)

◆ a2 [2/3]

#define a2   (numa + 2 * n)

◆ a2 [3/3]

#define a2   (numa + 2 * n)

◆ a3 [1/3]

#define a3   (numa + 3 * n)

◆ a3 [2/3]

#define a3   (numa + 3 * n)

◆ a3 [3/3]

#define a3   (numa + 3 * n)

◆ a4 [1/3]

#define a4   (numa + 4 * n)

◆ a4 [2/3]

#define a4   (numa + 4 * n)

◆ a4 [3/3]

#define a4   (numa + 4 * n)

◆ a5 [1/3]

#define a5   (numa + 5 * n)

◆ a5 [2/3]

#define a5   (numa + 5 * n)

◆ a5 [3/3]

#define a5   (numa + 5 * n)

◆ b0 [1/3]

#define b0   numb

◆ b0 [2/3]

#define b0   numb

◆ b0 [3/3]

#define b0   numb

◆ b1 [1/3]

#define b1   (numb + n)

◆ b1 [2/3]

#define b1   (numb + n)

◆ b1 [3/3]

#define b1   (numb + n)

◆ bs1 [1/2]

#define bs1   (cache->bs1)

◆ bs1 [2/2]

#define bs1   (cache->bs1)

◆ bs2 [1/2]

#define bs2   (cache->bs2)

◆ bs2 [2/2]

#define bs2   (cache->bs2)

◆ bsh [1/2]

#define bsh   (cache->bsh)

◆ bsh [2/2]

#define bsh   (cache->bsh)

◆ bsm1 [1/2]

#define bsm1   (cache->bsm1)

◆ bsm1 [2/2]

#define bsm1   (cache->bsm1)

◆ bsm2 [1/2]

#define bsm2   (cache->bsm2)

◆ bsm2 [2/2]

#define bsm2   (cache->bsm2)

◆ lmmp_mul_n_

#define lmmp_mul_n_ ( dst,
numa,
numb,
n )
值:
lmmp_mul_hard_n_((dst), (numa), (numb), (n)); \
else if ((n) < MUL_TOOM33_THRESHOLD) \
lmmp_mul_toom22_((dst), (numa), (n), (numb), (n)); \
else if ((n) < MUL_TOOM44_THRESHOLD) \
lmmp_mul_toom33_((dst), (numa), (n), (numb), (n)); \
else \
lmmp_mul_toom44_((dst), (numa), (n), (numb), (n))
#define MUL_TOOM22_THRESHOLD
#define MUL_TOOM33_THRESHOLD
#define MUL_TOOM44_THRESHOLD
#define numb
#define 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

在文件 mul_toom62.c 第 30 行定义.

◆ n [1/2]

#define n   (cache->n)

◆ n [2/2]

#define n   (cache->n)

◆ numb [1/2]

#define numb   (cache->numb)

◆ numb [2/2]

#define numb   (cache->numb)

◆ s [1/2]

#define s   (cache->s)

◆ s [2/2]

#define s   (cache->s)

◆ scratch [1/2]

#define scratch   (cache->scratch)

◆ scratch [2/2]

◆ scratch_out [1/3]

#define scratch_out   (scratch + 8 * n + 4)

◆ scratch_out [2/3]

#define scratch_out   (scratch + 8 * n + 4)

◆ scratch_out [3/3]

#define scratch_out   (scratch + 8 * n + 4)

◆ t [1/2]

#define t   (cache->t)

◆ t [2/2]

#define t   (cache->t)

◆ tmp [1/2]

#define tmp   (cache->tmp)

◆ tmp [2/2]

◆ v0 [1/3]

#define v0   dst

◆ v0 [2/3]

#define v0   dst

◆ v0 [3/3]

#define v0   dst

◆ v1 [1/3]

#define v1   (dst + 2 * n)

◆ v1 [2/3]

#define v1   (dst + 2 * n)

◆ v1 [3/3]

#define v1   (dst + 2 * n)

◆ v2 [1/3]

#define v2   scratch

◆ v2 [2/3]

#define v2   scratch

◆ v2 [3/3]

#define v2   scratch

◆ vh [1/3]

#define vh   (scratch + 4 * n + 2)

◆ vh [2/3]

#define vh   (scratch + 4 * n + 2)

◆ vh [3/3]

#define vh   (scratch + 4 * n + 2)

◆ vinf [1/3]

#define vinf   (dst + 6 * n)

◆ vinf [2/3]

#define vinf   (dst + 6 * n)

◆ vinf [3/3]

#define vinf   (dst + 6 * n)

◆ vm1 [1/3]

#define vm1   (scratch + 6 * n + 3)

◆ vm1 [2/3]

#define vm1   (scratch + 6 * n + 3)

◆ vm1 [3/3]

#define vm1   (scratch + 6 * n + 3)

◆ vm2 [1/3]

#define vm2   (scratch + 2 * n + 1)

◆ vm2 [2/3]

#define vm2   (scratch + 2 * n + 1)

◆ vm2 [3/3]

#define vm2   (scratch + 2 * n + 1)

函数说明

◆ lmmp_mul_toom62_()

void lmmp_mul_toom62_ ( mp_ptr restrict dst,
mp_srcptr restrict numa,
mp_size_t na,
mp_srcptr restrict numb,
mp_size_t nb )

在文件 mul_toom62.c 第 58 行定义.

58 {
59 lmmp_param_assert(6 * nb > na);
60 lmmp_param_assert(2 * na > 5 * nb);
61
62 mp_size_t n, s, t;
63 mp_limb_t cy;
64 mp_ptr as1, asm1, as2, asm2, ash;
66 mp_ptr gp;
67 enum toom7_flags aflags, bflags;
69
70#define a0 numa
71#define a1 (numa + n)
72#define a2 (numa + 2 * n)
73#define a3 (numa + 3 * n)
74#define a4 (numa + 4 * n)
75#define a5 (numa + 5 * n)
76#define b0 numb
77#define b1 (numb + n)
78
79 n = 1 + (na >= 3 * nb ? (na - 1) / (mp_size_t)6 : (nb - 1) >> 1);
80 lmmp_param_assert(na > 5 * n && nb > n);
81 s = na - 5 * n;
82 t = nb - n;
83
84 lmmp_param_assert(0 < s && s <= n);
85 lmmp_param_assert(0 < t && t <= n);
86
88
90 as1 = tmp;
91 asm1 = as1 + n + 1;
92 as2 = asm1 + n + 1;
93 asm2 = as2 + n + 1;
94 ash = asm2 + n + 1;
95 bs1 = ash + n + 1;
96 bsm1 = bs1 + n + 1;
97 bs2 = bsm1 + n;
98 bsm2 = bs2 + n + 1;
99 bsh = bsm2 + n + 1;
100
101 gp = dst;
102
103 /* Compute as1 and asm1. */
104 aflags = (enum toom7_flags)(toom7_w3_neg & lmmp_toom_eval_pm1_(as1, asm1, 5, numa, n, s, gp));
105
106 /* Compute as2 and asm2. */
107 aflags = (enum toom7_flags)(aflags | (toom7_w1_neg & lmmp_toom_eval_pm2_(as2, asm2, 5, numa, n, s, gp)));
108
109 /* Compute ash = 32 a0 + 16 a1 + 8 a2 + 4 a3 + 2 a4 + a5
110 = 2*(2*(2*(2*(2*a0 + a1) + a2) + a3) + a4) + a5 */
111
112 cy = lmmp_addshl1_n_(ash, a1, a0, n);
113 cy = 2 * cy + lmmp_addshl1_n_(ash, a2, ash, n);
114 cy = 2 * cy + lmmp_addshl1_n_(ash, a3, ash, n);
115 cy = 2 * cy + lmmp_addshl1_n_(ash, a4, ash, n);
116 if (s < n) {
117 mp_limb_t cy2;
118 cy2 = lmmp_addshl1_n_(ash, a5, ash, s);
119 ash[n] = 2 * cy + lmmp_shl_(ash + s, ash + s, n - s, 1);
120 lmmp_inc_1(ash + s, cy2);
121 } else
122 ash[n] = 2 * cy + lmmp_addshl1_n_(ash, a5, ash, n);
123
124 /* Compute bs1 and bsm1. */
125 if (t == n) {
126 if (lmmp_cmp_(b0, b1, n) < 0) {
127 cy = lmmp_add_n_sub_n_(bs1, bsm1, b1, b0, n);
128 bflags = toom7_w3_neg;
129 } else {
130 cy = lmmp_add_n_sub_n_(bs1, bsm1, b0, b1, n);
131 bflags = (enum toom7_flags)0;
132 }
133 bs1[n] = cy >> 1;
134 } else {
135 bs1[n] = lmmp_add_(bs1, b0, n, b1, t);
136 if (lmmp_zero_q_(b0 + t, n - t) && lmmp_cmp_(b0, b1, t) < 0) {
137 lmmp_sub_n_(bsm1, b1, b0, t);
138 lmmp_zero(bsm1 + t, n - t);
139 bflags = toom7_w3_neg;
140 } else {
141 lmmp_sub_(bsm1, b0, n, b1, t);
142 bflags = (enum toom7_flags)0;
143 }
144 }
145
146 /* Compute bs2 and bsm2. Recycling bs1 and bsm1; bs2=bs1+b1, bsm2 =
147 bsm1 - b1 */
148 lmmp_add_(bs2, bs1, n + 1, b1, t);
149 if (bflags & toom7_w3_neg) {
150 bsm2[n] = lmmp_add_(bsm2, bsm1, n, b1, t);
151 bflags = (enum toom7_flags)(bflags | toom7_w1_neg);
152 } else {
153 if (t < n) {
154 if (lmmp_zero_q_(bsm1 + t, n - t) && lmmp_cmp_(bsm1, b1, t) < 0) {
156 lmmp_zero(bsm2 + t, n + 1 - t);
157 bflags = (enum toom7_flags)(bflags | toom7_w1_neg);
158 } else {
159 lmmp_sub_(bsm2, bsm1, n, b1, t);
160 bsm2[n] = 0;
161 }
162 } else {
163 if (lmmp_cmp_(bsm1, b1, n) < 0) {
165 bflags = (enum toom7_flags)(bflags | toom7_w1_neg);
166 } else {
168 }
169 bsm2[n] = 0;
170 }
171 }
172
173 /* Compute bsh, recycling bs1. bsh=bs1+b0; */
174 bsh[n] = bs1[n] + lmmp_add_n_(bsh, bs1, b0, n);
175
176 lmmp_debug_assert(as1[n] <= 5);
177 lmmp_debug_assert(bs1[n] <= 1);
178 lmmp_debug_assert(asm1[n] <= 2);
179 lmmp_debug_assert(as2[n] <= 62);
180 lmmp_debug_assert(bs2[n] <= 2);
181 lmmp_debug_assert(asm2[n] <= 41);
182 lmmp_debug_assert(bsm2[n] <= 1);
183 lmmp_debug_assert(ash[n] <= 62);
184 lmmp_debug_assert(bsh[n] <= 2);
185
186#define v0 dst /* 2n */
187#define v1 (dst + 2 * n) /* 2n+1 */
188#define vinf (dst + 6 * n) /* s+t */
189#define v2 scratch /* 2n+1 */
190#define vm2 (scratch + 2 * n + 1) /* 2n+1 */
191#define vh (scratch + 4 * n + 2) /* 2n+1 */
192#define vm1 (scratch + 6 * n + 3) /* 2n+1 */
193#define scratch_out (scratch + 8 * n + 4) /* 2n+1 */
194 /* Total scratch need: 10*n+5 */
195
196 /* Must be in allocation order, as they overwrite one limb beyond
197 * 2n+1. */
198 lmmp_mul_n_(v2, as2, bs2, n + 1); /* v2, 2n+1 limbs */
199 lmmp_mul_n_(vm2, asm2, bsm2, n + 1); /* vm2, 2n+1 limbs */
200 lmmp_mul_n_(vh, ash, bsh, n + 1); /* vh, 2n+1 limbs */
201
202 /* vm1, 2n+1 limbs */
204 cy = 0;
205 if (asm1[n] == 1) {
206 cy = lmmp_add_n_(vm1 + n, vm1 + n, bsm1, n);
207 } else if (asm1[n] == 2) {
208 cy = lmmp_addshl1_n_(vm1 + n, vm1 + n, bsm1, n);
209 }
210 vm1[2 * n] = cy;
211
212 /* v1, 2n+1 limbs */
213 lmmp_mul_n_(v1, as1, bs1, n);
214 if (as1[n] == 1) {
215 cy = bs1[n] + lmmp_add_n_(v1 + n, v1 + n, bs1, n);
216 } else if (as1[n] == 2) {
217 cy = 2 * bs1[n] + lmmp_addshl1_n_(v1 + n, v1 + n, bs1, n);
218 } else if (as1[n] != 0) {
219 cy = as1[n] * bs1[n] + lmmp_addmul_1_(v1 + n, bs1, n, as1[n]);
220 } else
221 cy = 0;
222 if (bs1[n] != 0)
223 cy += lmmp_add_n_(v1 + n, v1 + n, as1, n);
224 v1[2 * n] = cy;
225
226 lmmp_mul_n_(v0, a0, b0, n); /* v0, 2n limbs */
227
228 /* vinf, s+t limbs */
229 if (s > t)
230 lmmp_mul_(vinf, a5, s, b1, t);
231 else
232 lmmp_mul_(vinf, b1, t, a5, s);
233
234 lmmp_toom_interp7_(dst, n, (enum toom7_flags)(aflags ^ bflags), vm2, vm1, v2, vh, s + t, scratch_out);
235
237}
#define lmmp_mul_n_
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_zero(dst, n)
定义 lmmp.h:476
uint64_t mp_size_t
定义 lmmp.h:93
#define lmmp_debug_assert(x)
定义 lmmp.h:498
uint64_t mp_limb_t
定义 lmmp.h:92
#define lmmp_param_assert(x)
定义 lmmp.h:509
static mp_limb_t lmmp_add_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
加法静态内联函数 [dst,na]=[numa,na]+[numb,nb]
void lmmp_mul_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
不等长乘法操作 [dst,na+nb] = [numa,na] * [numb,nb]
mp_limb_t lmmp_addshl1_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
加法结合左移1位操作 [dst,n] = [numa,n] + ([numb,n] << 1)
定义 shl.c:53
int lmmp_cmp_(mp_srcptr numa, mp_srcptr numb, mp_size_t n)
比较函数
定义 cmp.c:26
int lmmp_zero_q_(mp_srcptr p, mp_size_t n)
判零函数
定义 cmp.c:55
mp_limb_t lmmp_shl_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shl)
左移操作 [dst,na] = [numa,na]<<shl,dst的低shl位填充0
定义 shl.c:26
static mp_limb_t lmmp_sub_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
减法静态内联函数 [dst,na]=[numa,na]-[numb,nb]
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])
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
#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 b0
#define b1
#define a0
#define a1
#define v0
#define bsm1
#define asm1
#define vinf
#define vm1
#define a2
#define v1
#define v2
#define t
#define a3
#define s
#define bs1
#define bs2
#define as2
#define asm2
#define bsm2
#define as1
#define vm2
#define vh
#define a4
#define scratch_out
#define a5
#define scratch
#define tmp
#define bsh
int lmmp_toom_eval_pm2_(mp_ptr xp2, mp_ptr xm2, unsigned k, mp_srcptr xp, mp_size_t n, mp_size_t hn, mp_ptr tp)
通用高阶 Toom 求值:k次多项式在 x = +2 和 x = -2 处求值
int lmmp_toom_eval_pm1_(mp_ptr xp1, mp_ptr xm1, unsigned k, mp_srcptr xp, mp_size_t n, mp_size_t hn, mp_ptr tp)
通用高阶 Toom 求值:k次多项式在 x = +1 和 x = -1 处求值
void lmmp_toom_interp7_(mp_ptr dst, mp_size_t n, enum toom7_flags flags, mp_ptr w1, mp_ptr w3, mp_ptr w4, mp_ptr w5, mp_size_t w6n, mp_ptr tp)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define SALLOC_TYPE(n, type)
#define TEMP_S_DECL
#define TEMP_S_FREE
toom7_flags
@ toom7_w1_neg
@ toom7_w3_neg

引用了 a0, a1, a2, a3, a4, a5, as1, as2, asm1, asm2, b0, b1, bs1, bs2, bsh, bsm1, bsm2, lmmp_add_(), lmmp_add_n_(), lmmp_add_n_sub_n_(), lmmp_addmul_1_(), lmmp_addshl1_n_(), lmmp_cmp_(), lmmp_debug_assert, lmmp_inc_1, lmmp_mul_(), lmmp_mul_n_, lmmp_mul_toom62_(), lmmp_param_assert, lmmp_shl_(), lmmp_sub_(), lmmp_sub_n_(), lmmp_toom_eval_pm1_(), lmmp_toom_eval_pm2_(), lmmp_toom_interp7_(), lmmp_zero, lmmp_zero_q_(), n, numb, restrict, s, SALLOC_TYPE, scratch, scratch_out, t, TEMP_S_DECL, TEMP_S_FREE, tmp, toom7_w1_neg, toom7_w3_neg, v0, v1, v2, vh, vinf, vm1 , 以及 vm2.

函数调用图:

◆ lmmp_mul_toom62_cache_()

void lmmp_mul_toom62_cache_ ( mp_ptr restrict dst,
mp_srcptr restrict numa,
const toom62_cache_t * cache,
enum toom7_flags bflags )
static

在文件 mul_toom62.c 第 438 行定义.

443 {
444#define numb (cache->numb)
445#define n (cache->n)
446#define s (cache->s)
447#define t (cache->t)
448#define scratch (cache->scratch)
449#define tmp (cache->tmp)
450#define bs1 (cache->bs1)
451#define bsm1 (cache->bsm1)
452#define bs2 (cache->bs2)
453#define bsm2 (cache->bsm2)
454#define bsh (cache->bsh)
455
456 mp_limb_t cy;
457 mp_ptr as1, asm1, as2, asm2, ash;
458 enum toom7_flags aflags;
459
460#define a0 numa
461#define a1 (numa + n)
462#define a2 (numa + 2 * n)
463#define a3 (numa + 3 * n)
464#define a4 (numa + 4 * n)
465#define a5 (numa + 5 * n)
466#define b0 numb
467#define b1 (numb + n)
468
469 as1 = tmp;
470 asm1 = as1 + n + 1;
471 as2 = asm1 + n + 1;
472 asm2 = as2 + n + 1;
473 ash = asm2 + n + 1;
474
475
476 /* Compute as1 and asm1. */
477 aflags = (enum toom7_flags)(toom7_w3_neg & lmmp_toom_eval_pm1_(as1, asm1, 5, numa, n, s, dst));
478
479 /* Compute as2 and asm2. */
480 aflags = (enum toom7_flags)(aflags | (toom7_w1_neg & lmmp_toom_eval_pm2_(as2, asm2, 5, numa, n, s, dst)));
481
482 /* Compute ash = 32 a0 + 16 a1 + 8 a2 + 4 a3 + 2 a4 + a5
483 = 2*(2*(2*(2*(2*a0 + a1) + a2) + a3) + a4) + a5 */
484
485 cy = lmmp_addshl1_n_(ash, a1, a0, n);
486 cy = 2 * cy + lmmp_addshl1_n_(ash, a2, ash, n);
487 cy = 2 * cy + lmmp_addshl1_n_(ash, a3, ash, n);
488 cy = 2 * cy + lmmp_addshl1_n_(ash, a4, ash, n);
489 if (s < n) {
490 mp_limb_t cy2;
491 cy2 = lmmp_addshl1_n_(ash, a5, ash, s);
492 ash[n] = 2 * cy + lmmp_shl_(ash + s, ash + s, n - s, 1);
493 lmmp_inc_1(ash + s, cy2);
494 } else
495 ash[n] = 2 * cy + lmmp_addshl1_n_(ash, a5, ash, n);
496
497 lmmp_debug_assert(as1[n] <= 5);
498 lmmp_debug_assert(asm1[n] <= 2);
499 lmmp_debug_assert(as2[n] <= 62);
500 lmmp_debug_assert(asm2[n] <= 41);
501 lmmp_debug_assert(ash[n] <= 62);
502
503#define v0 dst /* 2n */
504#define v1 (dst + 2 * n) /* 2n+1 */
505#define vinf (dst + 6 * n) /* s+t */
506#define v2 scratch /* 2n+1 */
507#define vm2 (scratch + 2 * n + 1) /* 2n+1 */
508#define vh (scratch + 4 * n + 2) /* 2n+1 */
509#define vm1 (scratch + 6 * n + 3) /* 2n+1 */
510#define scratch_out (scratch + 8 * n + 4) /* 2n+1 */
511 /* Total scratch need: 10*n+5 */
512
513 /* Must be in allocation order, as they overwrite one limb beyond
514 * 2n+1. */
515 lmmp_mul_n_(v2, as2, bs2, n + 1); /* v2, 2n+1 limbs */
516 lmmp_mul_n_(vm2, asm2, bsm2, n + 1); /* vm2, 2n+1 limbs */
517 lmmp_mul_n_(vh, ash, bsh, n + 1); /* vh, 2n+1 limbs */
518
519 /* vm1, 2n+1 limbs */
521 cy = 0;
522 if (asm1[n] == 1) {
523 cy = lmmp_add_n_(vm1 + n, vm1 + n, bsm1, n);
524 } else if (asm1[n] == 2) {
525 cy = lmmp_addshl1_n_(vm1 + n, vm1 + n, bsm1, n);
526 }
527 vm1[2 * n] = cy;
528
529 /* v1, 2n+1 limbs */
530 lmmp_mul_n_(v1, as1, bs1, n);
531 if (as1[n] == 1) {
532 cy = bs1[n] + lmmp_add_n_(v1 + n, v1 + n, bs1, n);
533 } else if (as1[n] == 2) {
534 cy = 2 * bs1[n] + lmmp_addshl1_n_(v1 + n, v1 + n, bs1, n);
535 } else if (as1[n] != 0) {
536 cy = as1[n] * bs1[n] + lmmp_addmul_1_(v1 + n, bs1, n, as1[n]);
537 } else
538 cy = 0;
539 if (bs1[n] != 0)
540 cy += lmmp_add_n_(v1 + n, v1 + n, as1, n);
541 v1[2 * n] = cy;
542
543 lmmp_mul_n_(v0, a0, b0, n); /* v0, 2n limbs */
544
545 /* vinf, s+t limbs */
546 if (s > t)
547 lmmp_mul_(vinf, a5, s, b1, t);
548 else
549 lmmp_mul_(vinf, b1, t, a5, s);
550
551 lmmp_toom_interp7_(dst, n, (enum toom7_flags)(aflags ^ bflags), vm2, vm1, v2, vh, s + t, scratch_out);
552
553#undef numb
554#undef n
555#undef s
556#undef t
557#undef scratch
558#undef tmp
559#undef bs1
560#undef bsm1
561#undef bs2
562#undef bsm2
563#undef bsh
564}

引用了 a0, a1, a2, a3, a4, a5, as1, as2, asm1, asm2, b0, b1, bs1, bs2, bsh, bsm1, bsm2, lmmp_add_n_(), lmmp_addmul_1_(), lmmp_addshl1_n_(), lmmp_debug_assert, lmmp_inc_1, lmmp_mul_(), lmmp_mul_n_, lmmp_mul_toom62_cache_(), lmmp_shl_(), lmmp_toom_eval_pm1_(), lmmp_toom_eval_pm2_(), lmmp_toom_interp7_(), n, restrict, s, scratch_out, t, tmp, toom7_w1_neg, toom7_w3_neg, v0, v1, v2, vh, vinf, vm1 , 以及 vm2.

被这些函数引用 lmmp_mul_toom62_cache_() , 以及 lmmp_mul_toom62_unbalance_().

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

◆ lmmp_mul_toom62_cache_init_()

enum toom7_flags lmmp_mul_toom62_cache_init_ ( mp_ptr restrict dst,
mp_srcptr restrict numa,
toom62_cache_t * cache )
static

在文件 mul_toom62.c 第 253 行定义.

257 {
258#define numb (cache->numb)
259#define n (cache->n)
260#define s (cache->s)
261#define t (cache->t)
262#define scratch (cache->scratch)
263#define tmp (cache->tmp)
264#define bs1 (cache->bs1)
265#define bsm1 (cache->bsm1)
266#define bs2 (cache->bs2)
267#define bsm2 (cache->bsm2)
268#define bsh (cache->bsh)
269
270 mp_limb_t cy;
271 mp_ptr restrict as1, asm1, as2, asm2, ash;
272 enum toom7_flags aflags, bflags;
273
274#define a0 numa
275#define a1 (numa + n)
276#define a2 (numa + 2 * n)
277#define a3 (numa + 3 * n)
278#define a4 (numa + 4 * n)
279#define a5 (numa + 5 * n)
280#define b0 numb
281#define b1 (numb + n)
282
283
284 as1 = tmp;
285 asm1 = as1 + n + 1;
286 as2 = asm1 + n + 1;
287 asm2 = as2 + n + 1;
288 ash = asm2 + n + 1;
289
290
291 /* Compute as1 and asm1. */
292 aflags = (enum toom7_flags)(toom7_w3_neg & lmmp_toom_eval_pm1_(as1, asm1, 5, numa, n, s, dst));
293
294 /* Compute as2 and asm2. */
295 aflags = (enum toom7_flags)(aflags | (toom7_w1_neg & lmmp_toom_eval_pm2_(as2, asm2, 5, numa, n, s, dst)));
296
297 /* Compute ash = 32 a0 + 16 a1 + 8 a2 + 4 a3 + 2 a4 + a5
298 = 2*(2*(2*(2*(2*a0 + a1) + a2) + a3) + a4) + a5 */
299
300 cy = lmmp_addshl1_n_(ash, a1, a0, n);
301 cy = 2 * cy + lmmp_addshl1_n_(ash, a2, ash, n);
302 cy = 2 * cy + lmmp_addshl1_n_(ash, a3, ash, n);
303 cy = 2 * cy + lmmp_addshl1_n_(ash, a4, ash, n);
304 if (s < n) {
305 mp_limb_t cy2;
306 cy2 = lmmp_addshl1_n_(ash, a5, ash, s);
307 ash[n] = 2 * cy + lmmp_shl_(ash + s, ash + s, n - s, 1);
308 lmmp_inc_1(ash + s, cy2);
309 } else
310 ash[n] = 2 * cy + lmmp_addshl1_n_(ash, a5, ash, n);
311
312 /* Compute bs1 and bsm1. */
313 if (t == n) {
314 if (lmmp_cmp_(b0, b1, n) < 0) {
315 cy = lmmp_add_n_sub_n_(bs1, bsm1, b1, b0, n);
316 bflags = toom7_w3_neg;
317 } else {
318 cy = lmmp_add_n_sub_n_(bs1, bsm1, b0, b1, n);
319 bflags = (enum toom7_flags)0;
320 }
321 bs1[n] = cy >> 1;
322 } else {
323 bs1[n] = lmmp_add_(bs1, b0, n, b1, t);
324 if (lmmp_zero_q_(b0 + t, n - t) && lmmp_cmp_(b0, b1, t) < 0) {
325 lmmp_sub_n_(bsm1, b1, b0, t);
326 lmmp_zero(bsm1 + t, n - t);
327 bflags = toom7_w3_neg;
328 } else {
329 lmmp_sub_(bsm1, b0, n, b1, t);
330 bflags = (enum toom7_flags)0;
331 }
332 }
333
334 /* Compute bs2 and bsm2. Recycling bs1 and bsm1; bs2=bs1+b1, bsm2 =
335 bsm1 - b1 */
336 lmmp_add_(bs2, bs1, n + 1, b1, t);
337 if (bflags & toom7_w3_neg) {
338 bsm2[n] = lmmp_add_(bsm2, bsm1, n, b1, t);
339 bflags = (enum toom7_flags)(bflags | toom7_w1_neg);
340 } else {
341 if (t < n) {
342 if (lmmp_zero_q_(bsm1 + t, n - t) && lmmp_cmp_(bsm1, b1, t) < 0) {
344 lmmp_zero(bsm2 + t, n + 1 - t);
345 bflags = (enum toom7_flags)(bflags | toom7_w1_neg);
346 } else {
347 lmmp_sub_(bsm2, bsm1, n, b1, t);
348 bsm2[n] = 0;
349 }
350 } else {
351 if (lmmp_cmp_(bsm1, b1, n) < 0) {
353 bflags = (enum toom7_flags)(bflags | toom7_w1_neg);
354 } else {
356 }
357 bsm2[n] = 0;
358 }
359 }
360
361 /* Compute bsh, recycling bs1. bsh=bs1+b0; */
362 bsh[n] = bs1[n] + lmmp_add_n_(bsh, bs1, b0, n);
363
364 lmmp_debug_assert(as1[n] <= 5);
365 lmmp_debug_assert(bs1[n] <= 1);
366 lmmp_debug_assert(asm1[n] <= 2);
367 lmmp_debug_assert(as2[n] <= 62);
368 lmmp_debug_assert(bs2[n] <= 2);
369 lmmp_debug_assert(asm2[n] <= 41);
370 lmmp_debug_assert(bsm2[n] <= 1);
371 lmmp_debug_assert(ash[n] <= 62);
372 lmmp_debug_assert(bsh[n] <= 2);
373
374#define v0 dst /* 2n */
375#define v1 (dst + 2 * n) /* 2n+1 */
376#define vinf (dst + 6 * n) /* s+t */
377#define v2 scratch /* 2n+1 */
378#define vm2 (scratch + 2 * n + 1) /* 2n+1 */
379#define vh (scratch + 4 * n + 2) /* 2n+1 */
380#define vm1 (scratch + 6 * n + 3) /* 2n+1 */
381#define scratch_out (scratch + 8 * n + 4) /* 2n+1 */
382 /* Total scratch need: 10*n+5 */
383
384 /* Must be in allocation order, as they overwrite one limb beyond
385 * 2n+1. */
386 lmmp_mul_n_(v2, as2, bs2, n + 1); /* v2, 2n+1 limbs */
387 lmmp_mul_n_(vm2, asm2, bsm2, n + 1); /* vm2, 2n+1 limbs */
388 lmmp_mul_n_(vh, ash, bsh, n + 1); /* vh, 2n+1 limbs */
389
390 /* vm1, 2n+1 limbs */
392 cy = 0;
393 if (asm1[n] == 1) {
394 cy = lmmp_add_n_(vm1 + n, vm1 + n, bsm1, n);
395 } else if (asm1[n] == 2) {
396 cy = lmmp_addshl1_n_(vm1 + n, vm1 + n, bsm1, n);
397 }
398 vm1[2 * n] = cy;
399
400 /* v1, 2n+1 limbs */
401 lmmp_mul_n_(v1, as1, bs1, n);
402 if (as1[n] == 1) {
403 cy = bs1[n] + lmmp_add_n_(v1 + n, v1 + n, bs1, n);
404 } else if (as1[n] == 2) {
405 cy = 2 * bs1[n] + lmmp_addshl1_n_(v1 + n, v1 + n, bs1, n);
406 } else if (as1[n] != 0) {
407 cy = as1[n] * bs1[n] + lmmp_addmul_1_(v1 + n, bs1, n, as1[n]);
408 } else
409 cy = 0;
410 if (bs1[n] != 0)
411 cy += lmmp_add_n_(v1 + n, v1 + n, as1, n);
412 v1[2 * n] = cy;
413
414 lmmp_mul_n_(v0, a0, b0, n); /* v0, 2n limbs */
415
416 /* vinf, s+t limbs */
417 if (s > t)
418 lmmp_mul_(vinf, a5, s, b1, t);
419 else
420 lmmp_mul_(vinf, b1, t, a5, s);
421
422 lmmp_toom_interp7_(dst, n, (enum toom7_flags)(aflags ^ bflags), vm2, vm1, v2, vh, s + t, scratch_out);
423
424 return bflags;
425#undef numb
426#undef n
427#undef s
428#undef t
429#undef scratch
430#undef tmp
431#undef bs1
432#undef bsm1
433#undef bs2
434#undef bsm2
435#undef bsh
436}

引用了 a0, a1, a2, a3, a4, a5, as1, as2, asm1, asm2, b0, b1, bs1, bs2, bsh, bsm1, bsm2, lmmp_add_(), lmmp_add_n_(), lmmp_add_n_sub_n_(), lmmp_addmul_1_(), lmmp_addshl1_n_(), lmmp_cmp_(), lmmp_debug_assert, lmmp_inc_1, lmmp_mul_(), lmmp_mul_n_, lmmp_mul_toom62_cache_init_(), lmmp_shl_(), lmmp_sub_(), lmmp_sub_n_(), lmmp_toom_eval_pm1_(), lmmp_toom_eval_pm2_(), lmmp_toom_interp7_(), lmmp_zero, lmmp_zero_q_(), n, restrict, s, scratch_out, t, tmp, toom7_w1_neg, toom7_w3_neg, v0, v1, v2, vh, vinf, vm1 , 以及 vm2.

被这些函数引用 lmmp_mul_toom62_cache_init_() , 以及 lmmp_mul_toom62_unbalance_().

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

◆ lmmp_mul_toom62_unbalance_()

void lmmp_mul_toom62_unbalance_ ( mp_ptr restrict dst,
mp_srcptr restrict numa,
mp_size_t na,
mp_srcptr restrict numb,
mp_size_t nb )

在文件 mul_toom62.c 第 566 行定义.

572 {
573 lmmp_param_assert(na >= 5 * nb);
574 TEMP_DECL;
576
577 toom62_cache_t cache;
578 cache.numb = numb;
579 cache.n = 1 + (3 * nb - 1) / (mp_size_t)6;
580 cache.s = 3 * nb - 5 * cache.n;
581 cache.t = nb - cache.n;
582 cache.scratch = BALLOC_TYPE(20 * cache.n + 20, mp_limb_t);
583 cache.tmp = cache.scratch + 10 * cache.n + 10;
584 cache.bs1 = cache.tmp + 5 * cache.n + 5;
585 cache.bsm1 = cache.bs1 + cache.n + 1;
586 cache.bs2 = cache.bsm1 + cache.n;
587 cache.bsm2 = cache.bs2 + cache.n + 1;
588 cache.bsh = cache.bsm2 + cache.n + 1;
589
590 enum toom7_flags bflags = lmmp_mul_toom62_cache_init_(dst, numa, &cache);
591 dst += 3 * nb;
592 numa += 3 * nb;
593 na -= 3 * nb;
594 lmmp_copy(ws, dst, nb);
595 while (na >= 5 * nb) {
596 lmmp_mul_toom62_cache_(dst, numa, &cache, bflags);
597 if (lmmp_add_n_(dst, dst, ws, nb))
598 lmmp_inc(dst + nb);
599 dst += 3 * nb;
600 numa += 3 * nb;
601 na -= 3 * nb;
602 lmmp_copy(ws, dst, nb);
603 }
604 // 0 <= na < 2 nb
605 if (na >= nb)
606 lmmp_mul_(dst, numa, na, numb, nb);
607 else
608 lmmp_mul_(dst, numb, nb, numa, na);
609 if (lmmp_add_n_(dst, dst, ws, nb))
610 lmmp_inc(dst + nb);
611 TEMP_FREE;
612}
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
#define lmmp_inc(p)
加1宏(预期无进位)
mp_srcptr restrict numb
mp_ptr restrict bsm1
static void lmmp_mul_toom62_cache_(mp_ptr restrict dst, mp_srcptr restrict numa, const toom62_cache_t *cache, enum toom7_flags bflags)
mp_ptr restrict bsm2
mp_ptr restrict scratch
mp_ptr restrict tmp
mp_ptr restrict bsh
mp_ptr restrict bs1
mp_ptr restrict bs2
static enum toom7_flags lmmp_mul_toom62_cache_init_(mp_ptr restrict dst, mp_srcptr restrict numa, toom62_cache_t *cache)
#define TEMP_DECL
#define TEMP_FREE
#define BALLOC_TYPE(n, type)

引用了 BALLOC_TYPE, toom62_cache_t::bs1, toom62_cache_t::bs2, toom62_cache_t::bsh, toom62_cache_t::bsm1, toom62_cache_t::bsm2, lmmp_add_n_(), lmmp_copy, lmmp_inc, lmmp_mul_(), lmmp_mul_toom62_cache_(), lmmp_mul_toom62_cache_init_(), lmmp_mul_toom62_unbalance_(), lmmp_param_assert, toom62_cache_t::n, numb, toom62_cache_t::numb, restrict, toom62_cache_t::s, SALLOC_TYPE, toom62_cache_t::scratch, toom62_cache_t::t, TEMP_DECL, TEMP_FREE , 以及 toom62_cache_t::tmp.

函数调用图: