mul_toom_eval.c 文件参考

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

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

浏览源代码.

宏定义
#define	DO_addlsh2(d, a, b, n, cy)

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

宏定义说明

DO_addlsh2

#define DO_addlsh2	(		d,
			a,
			b,
			n,
			cy
	)

值:

    do {                                 \
        (cy) <<= 2;                      \
        (cy) += lmmp_shl_(d, b, n, 2);   \
        (cy) += lmmp_add_n_(d, d, a, n); \
    } while (0)

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

       {                                 \
        (cy) <<= 2;                      \
        (cy) += lmmp_shl_(d, b, n, 2);   \
        (cy) += lmmp_add_n_(d, d, a, n); \
    } while (0)

函数说明

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

函数调用图:

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