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

浏览该文件的源代码.

宏定义

#define w0   (dst + 5 * n)
#define w3   (dst + 2 * n)
#define w5   dst

函数

void lmmp_toom_interp6_ (mp_ptr dst, mp_size_t n, enum toom6_flags flags, mp_ptr w4, mp_ptr w2, mp_ptr w1, mp_size_t w0n)
 Copyright (C) 2026 HJimmyK (Jericho Knox)

宏定义说明

◆ w0

#define w0   (dst + 5 * n)

◆ w3

#define w3   (dst + 2 * n)

被这些函数引用 lmmp_toom_interp6_() , 以及 lmmp_toom_interp7_().

◆ w5

#define w5   dst

被这些函数引用 lmmp_toom_interp6_() , 以及 lmmp_toom_interp7_().

函数说明

◆ lmmp_toom_interp6_()

void lmmp_toom_interp6_ ( mp_ptr dst,
mp_size_t n,
enum toom6_flags flags,
mp_ptr w4,
mp_ptr w2,
mp_ptr w1,
mp_size_t w0n )

Copyright (C) 2026 HJimmyK (Jericho Knox)

Toom插值计算(6点插值):用于Toom-43和Toom-52 乘法算法

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)

参数
dst最终乘积结果缓冲区(5n + w0n limbs) w5 储存在[dst,2n], w3 储存在[dst+2n,2n+1], w0 储存在[dst+5n,w0n].
nToom-6 拆分后每段标准 limb 长度
flags插值符号标志位
w4输入/临时:点值 W4 缓冲区(2n+1 limbs)
w2输入/临时:点值 W2 缓冲区(2n+1 limbs)
w1输入/临时:点值 W1 缓冲区(2n+1 limbs)
w0n输入:最低位段 W0 的实际 limb 长度(0 < w0n <= 2n)
注解
w5=f(0), w4=f(-1), w3=f(1), w2=f(-2), w1=f(2), w0=f(inf)
警告
n>0, 0<w0n<=2n, dst!=NULL, w4!=NULL, w2!=NULL, w1!=NULL

在文件 mul_toom_interp6.c 第 56 行定义.

64 {
65
67 lmmp_param_assert(2 * n >= w0n && w0n > 0);
68 mp_limb_t cy;
69 /* cy6 can be stored in w1[2*n], cy4 in w4[0], embankment in w2[0] */
70 mp_limb_t cy4, cy6, embankment;
71
72#define w5 dst /* 2n */
73#define w3 (dst + 2 * n) /* 2n+1 */
74#define w0 (dst + 5 * n) /* w0n */
75
76 /* W2 =(W1 - W2)>>2 */
77 if (flags & toom6_vm2_neg)
78 lmmp_add_n_(w2, w1, w2, 2 * n + 1);
79 else
80 lmmp_sub_n_(w2, w1, w2, 2 * n + 1);
81 lmmp_shr_(w2, w2, 2 * n + 1, 2);
82
83 /* W1 =(W1 - W5)>>1 */
84 w1[2 * n] -= lmmp_sub_n_(w1, w1, w5, 2 * n);
85 lmmp_shr_(w1, w1, 2 * n + 1, 1);
86
87 /* W1 =(W1 - W2)>>1 */
88 lmmp_shr1sub_n_(w1, w1, w2, 2 * n + 1);
89
90 /* W4 =(W3 - W4)>>1 */
91 if (flags & toom6_vm1_neg) {
92 lmmp_shr1add_n_(w4, w3, w4, 2 * n + 1);
93 } else {
94 lmmp_shr1sub_n_(w4, w3, w4, 2 * n + 1);
95 }
96
97 /* W2 =(W2 - W4)/3 */
98 lmmp_sub_n_(w2, w2, w4, 2 * n + 1);
99 lmmp_divexact_by3_(w2, w2, 2 * n + 1);
100
101 /* W3 = W3 - W4 - W5 */
102 lmmp_sub_n_(w3, w3, w4, 2 * n + 1);
103 w3[2 * n] -= lmmp_sub_n_(w3, w3, w5, 2 * n);
104
105 /* W1 =(W1 - W3)/3 */
106 lmmp_sub_n_(w1, w1, w3, 2 * n + 1);
107 lmmp_divexact_by3_(w1, w1, 2 * n + 1);
108
109 cy = lmmp_add_n_(dst + n, dst + n, w4, 2 * n + 1);
110 lmmp_inc_1(dst + 3 * n + 1, cy);
111
112 /* W2 -= W0<<2 */
113 /* {W4,2*n+1} is now free and can be overwritten. */
114 cy = lmmp_shl_(w4, w0, w0n, 2);
115 cy += lmmp_sub_n_(w2, w2, w4, w0n);
116
117 lmmp_dec_1(w2 + w0n, cy);
118
119 /* W4L = W4L - W2L */
120 cy = lmmp_sub_n_(dst + n, dst + n, w2, n);
121 lmmp_dec_1(w3, cy);
122
123 /* W3H = W3H + W2L */
124 cy4 = w3[2 * n] + lmmp_add_n_(dst + 3 * n, dst + 3 * n, w2, n);
125 /* W1L + W2H */
126 cy = w2[2 * n] + lmmp_add_n_(dst + 4 * n, w1, w2 + n, n);
127 lmmp_inc_1(w1 + n, cy);
128
129 /* W0 = W0 + W1H */
130 if (w0n > n)
131 cy6 = w1[2 * n] + lmmp_add_n_(w0, w0, w1 + n, n);
132 else
133 cy6 = lmmp_add_n_(w0, w0, w1 + n, w0n);
134
135 cy = lmmp_sub_n_(dst + 2 * n, dst + 2 * n, dst + 4 * n, n + w0n);
136
137 /* embankment is a "dirty trick" to avoid carry/borrow propagation
138 beyond allocated memory */
139 embankment = w0[w0n - 1] - 1;
140 w0[w0n - 1] = 1;
141 if (w0n > n) {
142 if (cy4 > cy6)
143 lmmp_inc_1(dst + 4 * n, cy4 - cy6);
144 else
145 lmmp_dec_1(dst + 4 * n, cy6 - cy4);
146 lmmp_dec_1(dst + 3 * n + w0n, cy);
147 lmmp_inc_1(w0 + n, cy6);
148 } else {
149 lmmp_inc_1(dst + 4 * n, cy4);
150 lmmp_dec_1(dst + 3 * n + w0n, cy + cy6);
151 }
152 w0[w0n - 1] += embankment;
153
154#undef w5
155#undef w3
156#undef w0
157}
void lmmp_divexact_by3_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
Copyright (C) 2026 HJimmyK (Jericho Knox)
uint64_t mp_limb_t
定义 lmmp.h:92
#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
mp_limb_t lmmp_shr_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shr)
右移操作 [dst,na] = [numa,na]>>shr,dst的高shr位填充0
定义 shr.c:26
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
#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 n
#define w3
#define w0
#define w5
#define w2
@ toom6_vm2_neg
@ toom6_vm1_neg

引用了 lmmp_add_n_(), lmmp_dec_1, lmmp_divexact_by3_(), lmmp_inc_1, lmmp_param_assert, lmmp_shl_(), lmmp_shr1add_n_(), lmmp_shr1sub_n_(), lmmp_shr_(), lmmp_sub_n_(), lmmp_toom_interp6_(), n, toom6_vm1_neg, toom6_vm2_neg, w0, w2, w3 , 以及 w5.

被这些函数引用 lmmp_mul_toom43_(), lmmp_mul_toom52_() , 以及 lmmp_toom_interp6_().

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