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

浏览该文件的源代码.

宏定义

#define w0   dst
#define w2   (dst + 2 * n)
#define w6   (dst + 6 * n)

函数

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)

宏定义说明

◆ w0

#define w0   dst

◆ w2

◆ w6

#define w6   (dst + 6 * n)

被这些函数引用 lmmp_toom_interp7_().

函数说明

◆ lmmp_toom_interp7_()

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)

Toom插值计算(7点插值):用于Toom-44、Toom-53、Toom-62 乘法算法

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输出结果缓冲区,存储插值计算结果(6*n + w6n limbs) w0 储存在[dst,2n], w2 储存在[dst+2n,2n+1], w6 储存在[dst+6n,w6n].
nToom-7 拆分后每段标准 limb 长度
flagsToom-7 符号标志位,控制插值中的正负号运算
w1输入/临时:点值 W1 缓冲区(2n+1 limbs)
w3输入/临时:点值 W3 缓冲区(2n+1 limbs)
w4输入/临时:点值 W4 缓冲区(2n+1 limbs)
w5输入/临时:点值 W5 缓冲区(2n+1 limbs)
w6n输入:最低位段 W6 的实际 limb 长度 (0 < w6n <= 2n)
tp临时缓存空间(2*n+1 limbs)
注解
w0=f(0), w1=f(-2), w2=f(1), w3=f(-1), w4=f(2), w5=64*f(1/2), w6=f(inf),
警告
n>0, 0<w6n<=2n, dst!=NULL, w1!=NULL, w3!=NULL, w4!=NULL, w5!=NULL, tp!=NULL

在文件 mul_toom_interp7.c 第 62 行定义.

72 {
73 lmmp_param_assert(w6n > 0);
74 lmmp_param_assert(w6n <= 2 * n);
75 mp_size_t m;
76 mp_limb_t cy;
77
78 m = 2 * n + 1;
79#define w0 dst
80#define w2 (dst + 2 * n)
81#define w6 (dst + 6 * n)
82
83 lmmp_add_n_(w5, w5, w4, m);
84 if (flags & toom7_w1_neg) {
85 lmmp_shr1add_n_(w1, w1, w4, m);
86 } else {
87 lmmp_shr1sub_n_(w1, w4, w1, m);
88 }
89 lmmp_sub_(w4, w4, m, w0, 2 * n);
90 lmmp_sub_n_(w4, w4, w1, m);
91
92 lmmp_debug_assert(!(w4[0] & 3));
93
94 lmmp_shr_(w4, w4, m, 2); /* w4>=0 */
95
96 tp[w6n] = lmmp_shl_(tp, w6, w6n, 4);
97 lmmp_sub_(w4, w4, m, tp, w6n + 1);
98
99 if (flags & toom7_w3_neg) {
100 lmmp_shr1add_n_(w3, w3, w2, m);
101 } else {
102 lmmp_shr1sub_n_(w3, w2, w3, m);
103 }
104
105 lmmp_sub_n_(w2, w2, w3, m);
106
107 lmmp_submul_1_(w5, w2, m, 65);
108 lmmp_sub_(w2, w2, m, w6, w6n);
109 lmmp_sub_(w2, w2, m, w0, 2 * n);
110
111 lmmp_addmul_1_(w5, w2, m, 45);
112 lmmp_debug_assert(!(w5[0] & 1));
113 lmmp_shr_(w5, w5, m, 1);
114 lmmp_sub_n_(w4, w4, w2, m);
115
116 lmmp_divexact_by3_(w4, w4, m);
117 lmmp_sub_n_(w2, w2, w4, m);
118
119 lmmp_sub_n_(w1, w5, w1, m);
120 lmmp_shl_(tp, w3, m, 3);
121 lmmp_sub_n_(w5, w5, tp, m);
123 lmmp_sub_n_(w3, w3, w5, m);
124
125 lmmp_divexact_by15_(w1, w1, m);
126 lmmp_shr1add_n_(w1, w1, w5, m);
127 w1[m - 1] &= LIMB_MAX >> 1;
128
129 lmmp_sub_n_(w5, w5, w1, m);
130
131 /* These bounds are valid for the 4x4 polynomial product of toom44,
132 * and they are conservative for toom53 and toom62. */
133 lmmp_debug_assert(w1[2 * n] < 2);
134 lmmp_debug_assert(w2[2 * n] < 3);
135 lmmp_debug_assert(w3[2 * n] < 4);
136 lmmp_debug_assert(w4[2 * n] < 3);
137 lmmp_debug_assert(w5[2 * n] < 2);
138
139 cy = lmmp_add_n_(dst + n, dst + n, w1, m);
140 lmmp_inc_1(w2 + n + 1, cy);
141 cy = lmmp_add_n_(dst + 3 * n, dst + 3 * n, w3, n);
142 lmmp_inc_1(w3 + n, w2[2 * n] + cy);
143 cy = lmmp_add_n_(dst + 4 * n, w3 + n, w4, n);
144 lmmp_inc_1(w4 + n, w3[2 * n] + cy);
145 cy = lmmp_add_n_(dst + 5 * n, w4 + n, w5, n);
146 lmmp_inc_1(w5 + n, w4[2 * n] + cy);
147 if (w6n > n + 1) {
148 cy = lmmp_add_n_(dst + 6 * n, dst + 6 * n, w5 + n, n + 1);
149 lmmp_inc_1(dst + 7 * n + 1, cy);
150 } else {
151 cy = lmmp_add_n_(dst + 6 * n, dst + 6 * n, w5 + n, w6n);
152 lmmp_debug_assert(cy == 0);
153 }
154}
void lmmp_divexact_by9_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
精确除以9([dst,na] = [numa,na] / 9)
void lmmp_divexact_by3_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
Copyright (C) 2026 HJimmyK (Jericho Knox)
void lmmp_divexact_by15_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
精确除以15([dst,na] = [numa,na] / 15)
uint64_t mp_size_t
定义 lmmp.h:93
#define lmmp_debug_assert(x)
定义 lmmp.h:498
#define LIMB_MAX
定义 lmmp.h:105
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
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_submul_1_(mp_ptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t b)
乘以单limb并累减操作 [numa,n] -= [numb,n] * b
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 tp
#define n
#define w3
#define w0
#define w5
#define w2
#define w6
@ toom7_w1_neg
@ toom7_w3_neg

引用了 LIMB_MAX, lmmp_add_n_(), lmmp_addmul_1_(), lmmp_debug_assert, lmmp_divexact_by15_(), lmmp_divexact_by3_(), lmmp_divexact_by9_(), lmmp_inc_1, lmmp_param_assert, lmmp_shl_(), lmmp_shr1add_n_(), lmmp_shr1sub_n_(), lmmp_shr_(), lmmp_sub_(), lmmp_sub_n_(), lmmp_submul_1_(), lmmp_toom_interp7_(), n, toom7_w1_neg, toom7_w3_neg, tp, w0, w2, w3, w5 , 以及 w6.

被这些函数引用 lmmp_mul_toom44_(), lmmp_mul_toom53_(), lmmp_mul_toom62_(), lmmp_mul_toom62_cache_(), lmmp_mul_toom62_cache_init_(), lmmp_sqr_toom4_() , 以及 lmmp_toom_interp7_().

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