mul_toom_interp6.c 文件参考

#include "../../include/lammp/impl/divexact.h"
#include "../../include/lammp/impl/toom_interp.h"

mul_toom_interp6.c 的引用(Include)关系图:

浏览源代码.

宏定义
#define	w0   (dst + 5 * n) /* w0n */
#define	w3   (dst + 2 * n) /* 2n+1 */
#define	w5   dst /* 2n */

函数
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 乘法算法

宏定义说明

w0

#define w0   (dst + 5 * n) /* w0n */

w3

#define w3   (dst + 2 * n) /* 2n+1 */

w5

#define w5   dst /* 2n */

函数说明

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

函数调用图:

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