mul_toom_interp7.c 文件参考

#include "../../include/lammp/impl/toom_interp.h"
#include "../../include/lammp/impl/divexact.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)
	Toom插值计算（7点插值）：用于Toom-44、Toom-53、Toom-62 乘法算法

宏定义说明

w0

#define w0   dst

w2

#define w2   (dst + 2 * n)

w6

#define w6   (dst + 6 * n)

函数说明

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_().

函数调用图:

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