toom_interp.h 文件参考

#include "tmp_alloc.h"
#include "../lmmpn.h"

toom_interp.h 的引用(Include)关系图:

此图展示该文件直接或间接的被哪些文件引用了:

浏览源代码.

枚举
enum	toom6_flags { toom6_all_pos = 0 , toom6_vm1_neg = 1 , toom6_vm2_neg = 2 }
enum	toom7_flags { toom7_w1_neg = 1 , toom7_w3_neg = 2 }

函数
int	lmmp_toom_eval_dgr3_pm1_ (mp_ptr xp1, mp_ptr xm1, mp_srcptr xp, mp_size_t n, mp_size_t x3n, mp_ptr tp)
	Toom-3 专用：3次多项式在 x = +1 和 x = -1 处求值 计算 P(+1) 和 P(-1)，其中 P(x) 是一个3次多项式（4段系数）。
int	lmmp_toom_eval_dgr3_pm2_ (mp_ptr xp2, mp_ptr xm2, mp_srcptr xp, mp_size_t n, mp_size_t x3n, mp_ptr tp)
	Toom-3 专用：3次多项式在 x = +2 和 x = -2 处求值 计算 P(+2) 和 P(-2)，其中 P(x) 是一个3次多项式（4段系数）。
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 处求值
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 处求值
void	lmmp_toom_interp5_ (mp_ptr dst, mp_ptr v2, mp_ptr vm1, mp_size_t n, mp_size_t spt, int vm1_neg, mp_limb_t vinf0)
	Toom插值计算（5点插值），用于Toom-33和Toom-42乘法算法
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)
	Toom插值计算（6点插值）：用于Toom-43和Toom-52 乘法算法
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)
	Toom插值计算（7点插值）：用于Toom-44、Toom-53、Toom-62 乘法算法

枚举类型说明

toom6_flags

enum toom6_flags

枚举值
toom6_all_pos
toom6_vm1_neg
toom6_vm2_neg

在文件 toom_interp.h 第 25 行定义.

{ toom6_all_pos = 0, toom6_vm1_neg = 1, toom6_vm2_neg = 2 };

toom7_flags

enum toom7_flags

枚举值
toom7_w1_neg
toom7_w3_neg

在文件 toom_interp.h 第 27 行定义.

{ toom7_w1_neg = 1, toom7_w3_neg = 2 };

函数说明

lmmp_toom_eval_dgr3_pm1_()

int lmmp_toom_eval_dgr3_pm1_	(	mp_ptr	xp1,
		mp_ptr	xm1,
		mp_srcptr	xp,
		mp_size_t	n,
		mp_size_t	x3n,
		mp_ptr	tp
	)

Toom-3 专用：3次多项式在 x = +1 和 x = -1 处求值 计算 P(+1) 和 P(-1)，其中 P(x) 是一个3次多项式（4段系数）。

参数

xp1	输出：P(+1) 的结果（n+1 个 limbs 空间）
xm1	输出：P(-1) 的结果（n+1 个 limbs 空间）
xp	输入：多项式系数数组（共4段，每段 n limbs）
n	输入：每段完整系数的 limb 长度
x3n	输入：最后一段系数的实际长度（通常等于 n）
tp	临时缓存空间（至少 n+1 limbs）

警告

0<x3n<=n

返回

符号位：0=正，~0=负（对应 P(-1)）

在文件 mul_toom_eval.c 第 9 行定义.

                                                                                                          {
    int neg;
    lmmp_param_assert(x3n > 0);
    lmmp_param_assert(x3n <= n);
 
    xp1[n] = lmmp_add_n_(xp1, xp, xp + 2 * n, n);
    tp[n] = lmmp_add_(tp, xp + n, n, xp + 3 * n, x3n);
 
    neg = (lmmp_cmp_(xp1, tp, n + 1) < 0) ? ~0 : 0;
    if (neg)
        lmmp_add_n_sub_n_(xp1, xm1, tp, xp1, n + 1);
    else
        lmmp_add_n_sub_n_(xp1, xm1, xp1, tp, n + 1);
 
    lmmp_debug_assert(xp1[n] <= 3);
    lmmp_debug_assert(xm1[n] <= 1);
 
    return neg;
}

引用了 lmmp_add_(), lmmp_add_n_(), lmmp_add_n_sub_n_(), lmmp_cmp_(), lmmp_debug_assert, lmmp_param_assert , 以及 tp.

被这些函数引用 lmmp_mul_toom43_(), lmmp_mul_toom44_() , 以及 lmmp_sqr_toom4_().

函数调用图:

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

lmmp_toom_eval_dgr3_pm2_()

int lmmp_toom_eval_dgr3_pm2_	(	mp_ptr	xp2,
		mp_ptr	xm2,
		mp_srcptr	xp,
		mp_size_t	n,
		mp_size_t	x3n,
		mp_ptr	tp
	)

Toom-3 专用：3次多项式在 x = +2 和 x = -2 处求值 计算 P(+2) 和 P(-2)，其中 P(x) 是一个3次多项式（4段系数）。

参数

xp2	输出：P(+2) 的结果（n+1 个 limbs 空间）
xm2	输出：P(-2) 的结果（n+1 个 limbs 空间）
xp	输入：多项式系数数组（共4段，每段 n limbs）
n	输入：每段完整系数的 limb 长度
x3n	输入：最后一段系数的实际长度
tp	临时缓存空间（至少 n+1 limbs）

警告

0<x3n<=n

返回

符号位：0=正，~0=负（对应 P(-2)）

在文件 mul_toom_eval.c 第 29 行定义.

                                                                                                          {
    mp_limb_t cy;
    int neg;
    lmmp_param_assert(x3n > 0);
    lmmp_param_assert(x3n <= n);
    /* (x0 + 4 * x2) +/- (2 x1 + 8 x_3) */
 
    cy = lmmp_shl_(tp, xp + 2 * n, n, 2);
    xp2[n] = cy + lmmp_add_n_(xp2, tp, xp, n);
 
    tp[x3n] = lmmp_shl_(tp, xp + 3 * n, x3n, 2);
    if (x3n < n)
        tp[n] = lmmp_add_(tp, xp + n, n, tp, x3n + 1);
    else
        tp[n] += lmmp_add_n_(tp, xp + n, tp, n);
 
    lmmp_shl_(tp, tp, n + 1, 1);
 
    neg = (lmmp_cmp_(xp2, tp, n + 1) < 0) ? ~0 : 0;
 
    if (neg)
        lmmp_add_n_sub_n_(xp2, xm2, tp, xp2, n + 1);
    else
        lmmp_add_n_sub_n_(xp2, xm2, xp2, tp, n + 1);
 
    lmmp_debug_assert(xp2[n] < 15);
    lmmp_debug_assert(xm2[n] < 10);
 
    return neg;
}

引用了 lmmp_add_(), lmmp_add_n_(), lmmp_add_n_sub_n_(), lmmp_cmp_(), lmmp_debug_assert, lmmp_param_assert, lmmp_shl_() , 以及 tp.

被这些函数引用 lmmp_mul_toom43_(), lmmp_mul_toom44_() , 以及 lmmp_sqr_toom4_().

函数调用图:

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

lmmp_toom_eval_pm1_()

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 处求值

参数

xp1	输出：P(+1) 的结果（n+1 limbs）
xm1	输出：P(-1) 的结果（n+1 limbs）
k	输入：多项式次数（也是完整段的数量）
xp	输入：多项式系数数组
n	输入：每段完整系数的 limb 长度
hn	输入：最后一段系数的实际长度
tp	临时缓存空间（n+1 limbs）

警告

0<hn<=n, 3 < k

返回

符号位：0=正，~0=负

在文件 mul_toom_eval.c 第 60 行定义.

                                                                                                                {
    unsigned i;
    int neg;
    lmmp_param_assert(k >= 4);
 
    lmmp_param_assert(hn > 0);
    lmmp_param_assert(hn <= n);
 
    /* The degree k is also the number of full-size coefficients, so
     * that last coefficient, of size hn, starts at xp + k*n. */
 
    xp1[n] = lmmp_add_n_(xp1, xp, xp + 2 * n, n);
    for (i = 4; i < k; i += 2) lmmp_add_(xp1, xp1, n + 1, xp + i * n, n);
 
    tp[n] = lmmp_add_n_(tp, xp + n, xp + 3 * n, n);
    for (i = 5; i < k; i += 2) lmmp_add_(tp, tp, n + 1, xp + i * n, n);
 
    if (k & 1)
        lmmp_add_(tp, tp, n + 1, xp + k * n, hn);
    else
        lmmp_add_(xp1, xp1, n + 1, xp + k * n, hn);
 
    neg = (lmmp_cmp_(xp1, tp, n + 1) < 0) ? ~0 : 0;
 
    if (neg)
        lmmp_add_n_sub_n_(xp1, xm1, tp, xp1, n + 1);
    else
        lmmp_add_n_sub_n_(xp1, xm1, xp1, tp, n + 1);
 
    lmmp_debug_assert(xp1[n] <= k);
    lmmp_debug_assert(xm1[n] <= k / 2 + 1);
 
    return neg;
}

引用了 k, lmmp_add_(), lmmp_add_n_(), lmmp_add_n_sub_n_(), lmmp_cmp_(), lmmp_debug_assert, lmmp_param_assert , 以及 tp.

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

函数调用图:

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

lmmp_toom_eval_pm2_()

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 处求值

参数

xp2	输出：P(+2) 的结果（n+1 limbs）
xm2	输出：P(-2) 的结果（n+1 limbs）
k	输入：多项式次数
xp	输入：多项式系数数组
n	输入：每段完整系数的 limb 长度
hn	输入：最后一段系数的实际长度
tp	临时缓存空间（n+1 limbs）

警告

0<hn<=n, 3 < k < LIMB_BITS

返回

符号位：0=正，~0=负

在文件 mul_toom_eval.c 第 107 行定义.

                                                                                                                {
    int i;
    int neg;
    mp_limb_t cy;
    lmmp_param_assert(k >= 3);
    lmmp_param_assert(k < LIMB_BITS);
 
    lmmp_param_assert(hn > 0);
    lmmp_param_assert(hn <= n);
 
    /* The degree k is also the number of full-size coefficients, so
     * that last coefficient, of size hn, starts at xp + k*n. */
 
    cy = 0;
    DO_addlsh2(xp2, xp + (k - 2) * n, xp + k * n, hn, cy);
    if (hn != n)
        cy = lmmp_add_1_(xp2 + hn, xp + (k - 2) * n + hn, n - hn, cy);
    for (i = k - 4; i >= 0; i -= 2) DO_addlsh2(xp2, xp + i * n, xp2, n, cy);
    xp2[n] = cy;
 
    k--;
 
    cy = 0;
    DO_addlsh2(tp, xp + (k - 2) * n, xp + k * n, n, cy);
    for (i = k - 4; i >= 0; i -= 2) DO_addlsh2(tp, xp + i * n, tp, n, cy);
    tp[n] = cy;
 
    if (k & 1)
        lmmp_shl_(tp, tp, n + 1, 1);
    else
        lmmp_shl_(xp2, xp2, n + 1, 1);
 
    neg = (lmmp_cmp_(xp2, tp, n + 1) < 0) ? ~0 : 0;
 
    if (neg)
        lmmp_add_n_sub_n_(xp2, xm2, tp, xp2, n + 1);
    else
        lmmp_add_n_sub_n_(xp2, xm2, xp2, tp, n + 1);
 
    lmmp_debug_assert(xp2[n] < (1ull << (k + 2)) - 1);
    lmmp_debug_assert(xm2[n] < ((1 << (k + 3)) - 1 - (1 ^ (k & 1))) / 3);
 
    neg ^= ((k & 1) - 1);
 
    return neg;
}

引用了 DO_addlsh2, k, LIMB_BITS, lmmp_add_1_(), lmmp_add_n_sub_n_(), lmmp_cmp_(), lmmp_debug_assert, lmmp_param_assert, lmmp_shl_() , 以及 tp.

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

函数调用图:

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

lmmp_toom_interp5_()

void lmmp_toom_interp5_	(	mp_ptr	dst,
		mp_ptr	v2,
		mp_ptr	vm1,
		mp_size_t	n,
		mp_size_t	spt,
		int	vm1_neg,
		mp_limb_t	vinf0
	)

Toom插值计算（5点插值），用于Toom-33和Toom-42乘法算法

参数

dst	输出结果缓冲区，存储插值计算结果 v(0)储存在[dst,2n]，v(1)储存在[dst+2n,2n]
v2	v(2)插值点值，长度为 2n+1
vm1	v(-1)插值点值，长度为 2n+1
n	操作数的 limb 长度
spt	系数r4的长度
vm1_neg	符号标记：v(-1)是否为负数（1表示负，0表示正）
vinf0	无穷远点插值的低64位值

在文件 mul_toom_interp5.c 第 10 行定义.

                                                                                                                     {
    mp_limb_t cy, saved;
    mp_size_t dnp = 2 * n + 1;
 
#define r0 (dst)
#define r1 (dst + n)
#define r2 (dst + 2 * n)
#define r3 (dst + 3 * n)
#define r4 (dst + 4 * n)
#define v0 r0
#define v1 r2
#define vinf r4
 
    // v2=(v2-vm1)/3
    if (vm1_neg)
        lmmp_add_n_(v2, v2, vm1, dnp);
    else
        lmmp_sub_n_(v2, v2, vm1, dnp);
    lmmp_divexact_by3_(v2, v2, dnp);
 
    // vm1=(v1-vm1)/2
    if (vm1_neg)
        lmmp_shr1add_n_(vm1, v1, vm1, dnp);
    else
        lmmp_shr1sub_n_(vm1, v1, vm1, dnp);
 
    // v1=v1-v0
    v1[2 * n] -= lmmp_sub_n_(v1, v1, v0, 2 * n);
 
    // v2=(v2-v1)/2
    lmmp_shr1sub_n_(v2, v2, v1, dnp);
 
    // v1=v1-vm1
    lmmp_sub_n_(v1, v1, vm1, dnp);
 
    // add vm1 at correct place.
    cy = lmmp_add_n_(r1, r1, vm1, dnp);
    lmmp_inc_1(r3 + 1, cy);  // at most propagate to v1[2*n]
 
    saved = v1[2 * n];  // it is vinf[0]
    vinf[0] = vinf0;    // correct value of vinf
 
    // v2=v2-vinf*2
    cy = lmmp_shl_(vm1, vinf, spt, 1);
    cy += lmmp_sub_n_(v2, v2, vm1, spt);
    lmmp_dec_1(v2 + spt, cy);
 
    // vinf+=v2h, no overflow
    cy = lmmp_add_n_(vinf, vinf, v2 + n, n + 1);
    lmmp_inc_1(r3 + dnp, cy);
 
    // v1-=vinf, (same time vmh-=v2h)
    cy = lmmp_sub_n_(v1, v1, vinf, spt);
    vinf0 = vinf[0];
    v1[2 * n] = saved;  // correct value of v1
    lmmp_dec_1(v1 + spt, cy);
 
    // vml-=v2l
    cy = lmmp_sub_n_(r1, r1, v2, n);
    lmmp_dec_1(v1, cy);
 
    // last v2l
    cy = lmmp_add_n_(r3, r3, v2, n);
    v1[2 * n] += cy;  // no carry
    lmmp_inc_1(vinf, vinf0);
}

引用了 lmmp_add_n_(), lmmp_dec_1, lmmp_divexact_by3_(), lmmp_inc_1, lmmp_shl_(), lmmp_shr1add_n_(), lmmp_shr1sub_n_(), lmmp_sub_n_(), r1, r3, v0, v1, v2, vinf , 以及 vm1.

被这些函数引用 lmmp_mul_toom33_(), lmmp_mul_toom42_(), lmmp_mul_toom42_cache_(), lmmp_mul_toom42_cache_init_() , 以及 lmmp_sqr_toom3_().

函数调用图:

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

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
	)

Toom插值计算（6点插值）：用于Toom-43和Toom-52 乘法算法

参数

dst	输出：最终乘积结果缓冲区（5n + w0n limbs） w5 储存在[dst,2n], w3 储存在[dst+2n,2n+1], w0 储存在[dst+5n,w0n].
n	输入：Toom-6 拆分后每段标准 limb 长度
flags	输入：Toom-6 插值符号标志位（控制正负号运算） toom6_vm2_neg: 对应 x=-2 点值符号 toom6_vm1_neg: 对应 x=-1 点值符号
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

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

  {
 
    lmmp_param_assert(n > 0);
    lmmp_param_assert(2 * n >= w0n && w0n > 0);
    mp_limb_t cy;
    /* cy6 can be stored in w1[2*n], cy4 in w4[0], embankment in w2[0] */
    mp_limb_t cy4, cy6, embankment;
 
#define w5 dst           /* 2n   */
#define w3 (dst + 2 * n) /* 2n+1 */
#define w0 (dst + 5 * n) /* w0n  */
 
    /* W2 =(W1 - W2)>>2 */
    if (flags & toom6_vm2_neg)
        lmmp_add_n_(w2, w1, w2, 2 * n + 1);
    else
        lmmp_sub_n_(w2, w1, w2, 2 * n + 1);
    lmmp_shr_(w2, w2, 2 * n + 1, 2);
 
    /* W1 =(W1 - W5)>>1 */
    w1[2 * n] -= lmmp_sub_n_(w1, w1, w5, 2 * n);
    lmmp_shr_(w1, w1, 2 * n + 1, 1);
 
    /* W1 =(W1 - W2)>>1 */
    lmmp_shr1sub_n_(w1, w1, w2, 2 * n + 1);
 
    /* W4 =(W3 - W4)>>1 */
    if (flags & toom6_vm1_neg) {
        lmmp_shr1add_n_(w4, w3, w4, 2 * n + 1);
    } else {
        lmmp_shr1sub_n_(w4, w3, w4, 2 * n + 1);
    }
 
    /* W2 =(W2 - W4)/3 */
    lmmp_sub_n_(w2, w2, w4, 2 * n + 1);
    lmmp_divexact_by3_(w2, w2, 2 * n + 1);
 
    /* W3 = W3 - W4 - W5 */
    lmmp_sub_n_(w3, w3, w4, 2 * n + 1);
    w3[2 * n] -= lmmp_sub_n_(w3, w3, w5, 2 * n);
 
    /* W1 =(W1 - W3)/3 */
    lmmp_sub_n_(w1, w1, w3, 2 * n + 1);
    lmmp_divexact_by3_(w1, w1, 2 * n + 1);
 
    cy = lmmp_add_n_(dst + n, dst + n, w4, 2 * n + 1);
    lmmp_inc_1(dst + 3 * n + 1, cy);
 
    /* W2 -= W0<<2 */
    /* {W4,2*n+1} is now free and can be overwritten. */
    cy = lmmp_shl_(w4, w0, w0n, 2);
    cy += lmmp_sub_n_(w2, w2, w4, w0n);
 
    lmmp_dec_1(w2 + w0n, cy);
 
    /* W4L = W4L - W2L */
    cy = lmmp_sub_n_(dst + n, dst + n, w2, n);
    lmmp_dec_1(w3, cy);
 
    /* W3H = W3H + W2L */
    cy4 = w3[2 * n] + lmmp_add_n_(dst + 3 * n, dst + 3 * n, w2, n);
    /* W1L + W2H */
    cy = w2[2 * n] + lmmp_add_n_(dst + 4 * n, w1, w2 + n, n);
    lmmp_inc_1(w1 + n, cy);
 
    /* W0 = W0 + W1H */
    if (w0n > n)
        cy6 = w1[2 * n] + lmmp_add_n_(w0, w0, w1 + n, n);
    else
        cy6 = lmmp_add_n_(w0, w0, w1 + n, w0n);
 
    cy = lmmp_sub_n_(dst + 2 * n, dst + 2 * n, dst + 4 * n, n + w0n);
 
    /* embankment is a "dirty trick" to avoid carry/borrow propagation
       beyond allocated memory */
    embankment = w0[w0n - 1] - 1;
    w0[w0n - 1] = 1;
    if (w0n > n) {
        if (cy4 > cy6)
            lmmp_inc_1(dst + 4 * n, cy4 - cy6);
        else
            lmmp_dec_1(dst + 4 * n, cy6 - cy4);
        lmmp_dec_1(dst + 3 * n + w0n, cy);
        lmmp_inc_1(w0 + n, cy6);
    } else {
        lmmp_inc_1(dst + 4 * n, cy4);
        lmmp_dec_1(dst + 3 * n + w0n, cy + cy6);
    }
    w0[w0n - 1] += embankment;
 
#undef w5
#undef w3
#undef w0
}

引用了 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_(), toom6_vm1_neg, toom6_vm2_neg, w0, w2, w3 , 以及 w5.

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

函数调用图:

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

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
	)

Toom插值计算（7点插值）：用于Toom-44、Toom-53、Toom-62 乘法算法

参数

dst	输出结果缓冲区，存储插值计算结果（6*n + w6n limbs） w0 储存在[dst,2n], w2 储存在[dst+2n,2n+1], w6 储存在[dst+6n,w6n].
n	输入：Toom-7 拆分后每段标准 limb 长度
flags	输入：Toom-7 符号标志位，控制插值中的正负号运算 toom7_w1_neg: 点值 W1 符号位 toom7_w3_neg: 点值 W3 符号位
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

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

  {
    lmmp_param_assert(w6n > 0);
    lmmp_param_assert(w6n <= 2 * n);
    mp_size_t m;
    mp_limb_t cy;
 
    m = 2 * n + 1;
#define w0 dst
#define w2 (dst + 2 * n)
#define w6 (dst + 6 * n)
 
    lmmp_add_n_(w5, w5, w4, m);
    if (flags & toom7_w1_neg) {
        lmmp_shr1add_n_(w1, w1, w4, m);
    } else {
        lmmp_shr1sub_n_(w1, w4, w1, m);
    }
    lmmp_sub_(w4, w4, m, w0, 2 * n);
    lmmp_sub_n_(w4, w4, w1, m);
 
    lmmp_debug_assert(!(w4[0] & 3));
 
    lmmp_shr_(w4, w4, m, 2); /* w4>=0 */
 
    tp[w6n] = lmmp_shl_(tp, w6, w6n, 4);
    lmmp_sub_(w4, w4, m, tp, w6n + 1);
 
    if (flags & toom7_w3_neg) {
        lmmp_shr1add_n_(w3, w3, w2, m);
    } else {
        lmmp_shr1sub_n_(w3, w2, w3, m);
    }
 
    lmmp_sub_n_(w2, w2, w3, m);
 
    lmmp_submul_1_(w5, w2, m, 65);
    lmmp_sub_(w2, w2, m, w6, w6n);
    lmmp_sub_(w2, w2, m, w0, 2 * n);
 
    lmmp_addmul_1_(w5, w2, m, 45);
    lmmp_debug_assert(!(w5[0] & 1));
    lmmp_shr_(w5, w5, m, 1);
    lmmp_sub_n_(w4, w4, w2, m);
 
    lmmp_divexact_by3_(w4, w4, m);
    lmmp_sub_n_(w2, w2, w4, m);
 
    lmmp_sub_n_(w1, w5, w1, m);
    lmmp_shl_(tp, w3, m, 3);
    lmmp_sub_n_(w5, w5, tp, m);
    lmmp_divexact_by9_(w5, w5, m);
    lmmp_sub_n_(w3, w3, w5, m);
 
    lmmp_divexact_by15_(w1, w1, m);
    lmmp_shr1add_n_(w1, w1, w5, m);
    w1[m - 1] &= LIMB_MAX >> 1;
 
    lmmp_sub_n_(w5, w5, w1, m);
 
    /* These bounds are valid for the 4x4 polynomial product of toom44,
     * and they are conservative for toom53 and toom62. */
    lmmp_debug_assert(w1[2 * n] < 2);
    lmmp_debug_assert(w2[2 * n] < 3);
    lmmp_debug_assert(w3[2 * n] < 4);
    lmmp_debug_assert(w4[2 * n] < 3);
    lmmp_debug_assert(w5[2 * n] < 2);
 
    cy = lmmp_add_n_(dst + n, dst + n, w1, m);
    lmmp_inc_1(w2 + n + 1, cy);
    cy = lmmp_add_n_(dst + 3 * n, dst + 3 * n, w3, n);
    lmmp_inc_1(w3 + n, w2[2 * n] + cy);
    cy = lmmp_add_n_(dst + 4 * n, w3 + n, w4, n);
    lmmp_inc_1(w4 + n, w3[2 * n] + cy);
    cy = lmmp_add_n_(dst + 5 * n, w4 + n, w5, n);
    lmmp_inc_1(w5 + n, w4[2 * n] + cy);
    if (w6n > n + 1) {
        cy = lmmp_add_n_(dst + 6 * n, dst + 6 * n, w5 + n, n + 1);
        lmmp_inc_1(dst + 7 * n + 1, cy);
    } else {
        lmmp_assert(lmmp_add_n_(dst + 6 * n, dst + 6 * n, w5 + n, w6n));
    }
}

引用了 LIMB_MAX, lmmp_add_n_(), lmmp_addmul_1_(), lmmp_assert, 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_(), 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_().

函数调用图:

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