div_divide.c 文件参考

#include "../../include/lammp/impl/mparam.h"
#include "../../include/lammp/impl/tmp_alloc.h"
#include "../../include/lammp/lmmpn.h"

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

浏览源代码.

函数
mp_limb_t	lmmp_div_divide_ (mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, mp_limb_t inv21)
	分治除法运算
static mp_limb_t	lmmp_div_divide_n_ (mp_ptr dstq, mp_ptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t inv21, mp_ptr tp)

函数说明

lmmp_div_divide_()

mp_limb_t lmmp_div_divide_	(	mp_ptr	dstq,
		mp_ptr	numa,
		mp_size_t	na,
		mp_srcptr	numb,
		mp_size_t	nb,
		mp_limb_t	inv21
	)

分治除法运算

参数

dstq	输出商的缓冲区，长度至少为na-nb
numa	输入被除数（长度na），运算后存储余数（长度nb）
na	被除数的单精度数(limb)长度
numb	输入除数，长度为nb
nb	除数的单精度数(limb)长度
inv21	除数的2-1阶逆元（inv21([numb+nb-2,2])）

返回

商的最高位（qh）

警告

na>=2*nb, nb>=6, MSB(numb)=1, inv21=inv21([numb+nb-2,2]), sep(dstq,numa,numb)

注解

qh:[dstq,na-nb]=[numa,na] div [numb,nb], [numa,na-nb]=[numa,na] mod [numb,nb], return qh

在文件 div_divide.c 第 53 行定义.

                                                                                                                  {
    lmmp_param_assert(na >= 2 * nb);
    lmmp_param_assert(nb >= 6);
    lmmp_param_assert(numb[nb - 1] >= LIMB_B_2);
    mp_size_t nq = na - nb;
 
    dstq += nq;
    numa += nq;
 
    do {
        nq -= nb;
    } while (nq >= nb);
 
    dstq -= nq;
    numa -= nq;
 
    /* Perform the typically smaller block first. */
    mp_limb_t qh = lmmp_div_s_(dstq, numa, nb + nq, numb, nb);
 
    TEMP_DECL;
    mp_ptr tp = TALLOC_TYPE(nb, mp_limb_t);
    nq = na - nb - nq;
 
    do {
        dstq -= nb;
        numa -= nb;
        lmmp_div_divide_n_(dstq, numa, numb, nb, inv21, tp);
        nq -= nb;
    } while (nq > 0);
 
    TEMP_FREE;
    return qh;
}

引用了 LIMB_B_2, lmmp_div_divide_n_(), lmmp_div_s_(), lmmp_param_assert, TALLOC_TYPE, TEMP_DECL, TEMP_FREE , 以及 tp.

被这些函数引用 lmmp_div_(), lmmp_div_s_() , 以及 lmmp_inv_basecase_().

函数调用图:

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

lmmp_div_divide_n_()

static mp_limb_t lmmp_div_divide_n_ ( mp_ptr  dstq, mp_ptr  numa, mp_srcptr  numb, mp_size_t  n, mp_limb_t  inv21, mp_ptr  tp  )

static

在文件 div_divide.c 第 13 行定义.

                                                                                                                       {
    lmmp_param_assert(n >= 6);
    lmmp_param_assert(numb[n - 1] >= LIMB_B_2);
    mp_size_t lo = n >> 1, hi = n - lo;
    mp_limb_t cy, qh, ql;
 
    if (hi < DIV_DIVIDE_THRESHOLD) {
        qh = lmmp_div_basecase_(dstq + lo, numa + 2 * lo, 2 * hi, numb + lo, hi, inv21);
    } else {
        qh = lmmp_div_divide_n_(dstq + lo, numa + 2 * lo, numb + lo, hi, inv21, tp);
    }
    lmmp_mul_(tp, dstq + lo, hi, numb, lo);
 
    cy = lmmp_sub_n_(numa + lo, numa + lo, tp, n);
    if (qh)
        cy += lmmp_sub_n_(numa + n, numa + n, numb, lo);
 
    while (cy) {
        qh -= lmmp_sub_1_(dstq + lo, dstq + lo, hi, 1);
        cy -= lmmp_add_n_(numa + lo, numa + lo, numb, n);
    }
 
    if (lo < DIV_DIVIDE_THRESHOLD) {
        ql = lmmp_div_basecase_(dstq, numa + hi, 2 * lo, numb + hi, lo, inv21);
    } else {
        ql = lmmp_div_divide_n_(dstq, numa + hi, numb + hi, lo, inv21, tp);
    }
    lmmp_mul_(tp, numb, hi, dstq, lo);
 
    cy = lmmp_sub_n_(numa, numa, tp, n);
    if (ql)
        cy += lmmp_sub_n_(numa + lo, numa + lo, numb, hi);
 
    while (cy) {
        lmmp_sub_1_(dstq, dstq, lo, 1);
        cy -= lmmp_add_n_(numa, numa, numb, n);
    }
    return qh;
}

引用了 DIV_DIVIDE_THRESHOLD, LIMB_B_2, lmmp_add_n_(), lmmp_div_basecase_(), lmmp_div_divide_n_(), lmmp_mul_(), lmmp_param_assert, lmmp_sub_1_(), lmmp_sub_n_() , 以及 tp.

被这些函数引用 lmmp_div_divide_() , 以及 lmmp_div_divide_n_().

函数调用图:

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