from_str.c 文件参考

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

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

浏览源代码.

函数
mp_size_t	lmmp_from_str_ (mp_ptr dst, const mp_byte_t *src, mp_size_t len, int base)
	字符串转大数操作 [src,len,base] to [dst,return value,B]
static mp_size_t	lmmp_from_str_basecase_ (mp_ptr dst, const mp_byte_t *src, mp_size_t len, int base)
static mp_size_t	lmmp_from_str_divide_ (mp_ptr dst, const mp_byte_t *src, mp_size_t len, mp_basepow_t *pow, mp_ptr tp)
mp_size_t	lmmp_from_str_len_ (const mp_byte_t *src, mp_size_t len, int base)
	计算字符串转大数所需的 limb 缓冲区长度

函数说明

lmmp_from_str_()

mp_size_t lmmp_from_str_	(	mp_ptr	dst,
		const mp_byte_t *	src,
		mp_size_t	len,
		int	base
	)

字符串转大数操作 [src,len,base] to [dst,return value,B]

警告

len>=0, 2<=base<=256

参数

dst	大数结果输出指针
src	字符串源指针
len	字符串长度
base	字符串的进制基数

返回

转换后的大数 limb 长度

在文件 from_str.c 第 128 行定义.

                                                                                    {
    do {
        if (len == 0)
            return 0;
    } while (src[--len] == 0);
    ++len;
 
    mp_size_t limbs;
    if (LMMP_POW2_Q(base)) {
        mp_limb_t curlimb = 0;
        const mp_byte_t* srcend = src + len;
        int bitspd = lmmp_bases_table[base - 2].large_base;
        int bitpos = 0;
        limbs = 0;
 
        do {
            mp_limb_t curdigit = *src;
            curlimb |= curdigit << bitpos;
            bitpos += bitspd;
            if (bitpos >= LIMB_BITS) {
                dst[limbs] = curlimb;
                ++limbs;
                bitpos -= LIMB_BITS;
                curlimb = curdigit >> (bitspd - bitpos);
            }
        } while (++src != srcend);
        if (curlimb) {
            dst[limbs] = curlimb;
            ++limbs;
        }
    } else if (lmmp_from_str_len_(0, len, base) < FROM_STR_BASEPOW_THRESHOLD) {
        limbs = lmmp_from_str_basecase_(dst, src, len, base);
    } else {
        TEMP_DECL;
        mp_basepow_t powers[LIMB_BITS];
        mp_limb_t lbase = lmmp_bases_table[base - 2].large_base;
        mp_size_t digitspl = lmmp_bases_table[base - 2].digits_in_limb;
        mp_size_t bexp, lexp = (len - 1) / digitspl + 1;
        mp_size_t tzbit = lmmp_tailing_zeros_(lbase);
        // need 1 extra limb to store result
        mp_size_t alloc_size = lmmp_from_str_len_(0, len, base) + 1;
        mp_limb_t cy;
        mp_ptr tp;
 
        int cpow = lmmp_limb_bits_(lexp - 1);
 
        for (int i = cpow; i > 0; --i) {
            // we will calculate lbase^bexp
            bexp = ((lexp - 1) >> i) + 1;
            // we will calculate lbase^(bexp-1) first, and trim it s. t.
            // it contains at most 2 tailing 0 limb, then multiply it by lbase,
            // so we need npow limbs to store lbase^bexp
            mp_size_t npow = lmmp_from_str_len_(0, (bexp - 1) * digitspl + 1, base) + 1;
 
            if (tzbit) {
                mp_size_t tzlimb = tzbit * (bexp - 1) / LIMB_BITS;
                if (tzlimb >= 2)
                    npow -= tzlimb - 2;
            }
 
            // space needed for a trimmed npow-limb lbase^bexp
            alloc_size += npow;
        }
 
        tp = BALLOC_TYPE(alloc_size, mp_limb_t);
 
        for (int i = 0; i < 2; ++i) {
            tp[0] = lbase;
            powers[i].p = tp;
            powers[i].np = 1;
            tp += i + 1;
            powers[i].zeros = 0;
            powers[i].digits = digitspl * (i + 1);
            powers[i].base = base;
        }
 
        mp_ptr p = powers[1].p;
        mp_size_t zeros = 0, np = 1;
        for (int i = 2; i < cpow; ++i) {
            lmmp_sqr_(tp, p, np);
            np *= 2;
            np -= tp[np - 1] == 0;
            bexp = (lexp - 1) >> (cpow - i);
            if (bexp & 1) {
                cy = lmmp_mul_1_(tp, tp, np, lbase);
                tp[np] = cy;
                np += cy != 0;
            }
            zeros *= 2;
            while (tp[0] == 0) {
                // at most 2 tailing 0 limb here
                ++zeros;
                ++tp;
                --np;
            }
            p = tp;
            powers[i].p = p;
            powers[i].np = np;
            powers[i].zeros = zeros;
            powers[i].digits = digitspl * (bexp + 1);
            powers[i].base = base;
            tp += np + 1;
        }
 
        for (int i = 1; i < cpow; ++i) {
            p = powers[i].p;
            np = powers[i].np;
            cy = lmmp_mul_1_(p, p, np, lbase);
            p[np] = cy;
            np += cy != 0;
            if (p[0] == 0) {
                ++powers[i].zeros;
                ++p;
                --np;
            }
 
            powers[i].p = p;
            powers[i].np = np;
        }
 
        limbs = lmmp_from_str_divide_(tp, src, len, powers + cpow - 1, dst);
        lmmp_copy(dst, tp, limbs);
 
        TEMP_FREE;
    }
    return limbs;
}

引用了 BALLOC_TYPE, mp_basepow_t::base, mp_basepow_t::digits, mp_base_t::digits_in_limb, FROM_STR_BASEPOW_THRESHOLD, mp_base_t::large_base, LIMB_BITS, lmmp_bases_table, lmmp_copy, lmmp_from_str_basecase_(), lmmp_from_str_divide_(), lmmp_from_str_len_(), lmmp_limb_bits_(), lmmp_mul_1_(), LMMP_POW2_Q, lmmp_sqr_(), lmmp_tailing_zeros_(), mp_basepow_t::np, mp_basepow_t::p, TEMP_DECL, TEMP_FREE, tp , 以及 mp_basepow_t::zeros.

函数调用图:

lmmp_from_str_basecase_()

static mp_size_t lmmp_from_str_basecase_ ( mp_ptr  dst, const mp_byte_t *  src, mp_size_t  len, int  base  )

static

在文件 from_str.c 第 26 行定义.

                                                                                                    {
    lmmp_param_assert(src[len - 1] != 0);
    mp_size_t digitspl = lmmp_bases_table[base - 2].digits_in_limb;
    mp_limb_t lbase = lmmp_bases_table[base - 2].large_base;
    mp_size_t limbs = 0, i = len;
 
    while (i) {
        mp_limb_t curlimb;
        if (i >= digitspl) {
            curlimb = src[--i];
            for (mp_size_t j = 1; j < digitspl; ++j) {
                curlimb = curlimb * base + src[--i];
            }
        } else {
            curlimb = src[--i];
            lbase = base;
            while (i) {
                curlimb = curlimb * base + src[--i];
                lbase *= base;
            }
        }
 
        if (limbs == 0) {
            dst[0] = curlimb;
            limbs = 1;
        } else {
            mp_limb_t cy = lmmp_mul_1_(dst, dst, limbs, lbase);
            cy += lmmp_add_1_(dst, dst, limbs, curlimb);
            if (cy) {
                dst[limbs] = cy;
                ++limbs;
            }
        }
    }
 
    return limbs;
}

引用了 mp_base_t::digits_in_limb, mp_base_t::large_base, lmmp_add_1_(), lmmp_bases_table, lmmp_mul_1_() , 以及 lmmp_param_assert.

被这些函数引用 lmmp_from_str_() , 以及 lmmp_from_str_divide_().

函数调用图:

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

lmmp_from_str_divide_()

static mp_size_t lmmp_from_str_divide_ ( mp_ptr  dst, const mp_byte_t *  src, mp_size_t  len, mp_basepow_t *  pow, mp_ptr  tp  )

static

在文件 from_str.c 第 69 行定义.

  {
    lmmp_param_assert(src[len - 1] != 0);
    mp_size_t limbs;
 
    if (lmmp_from_str_len_(0, len, pow->base) < FROM_STR_DIVIDE_THRESHOLD) {
        limbs = lmmp_from_str_basecase_(dst, src, len, pow->base);
    } else {
        mp_size_t pdigits = pow->digits;
        if (len <= pdigits) {
            limbs = lmmp_from_str_divide_(dst, src, len, pow - 1, tp);
        } else {
            mp_ptr p = pow->p;
            mp_size_t np = pow->np;
            mp_size_t zeros = pow->zeros;
            mp_ptr lp = tp, hp = tp + np + zeros - 2;  // overwrite 2 limbs
            mp_size_t nl = 0, nh;
 
            mp_size_t llen = pdigits;
            while (llen && src[llen - 1] == 0) --llen;
            if (llen)
                nl = lmmp_from_str_divide_(lp, src, llen, pow - 1, dst);
 
            mp_limb_t save0 = hp[0], save1 = hp[1];  // save 2 limbs
            nh = lmmp_from_str_divide_(hp, src + pdigits, len - pdigits, pow - 1, dst);
            if (nh >= np)
                lmmp_mul_(dst + zeros, hp, nh, p, np);
            else
                lmmp_mul_(dst + zeros, p, np, hp, nh);
            // restore 2 limbs
            hp[0] = save0;
            hp[1] = save1;
 
            if (zeros < nl) {
                lmmp_copy(dst, lp, zeros);
                mp_limb_t cy = lmmp_add_n_(dst + zeros, dst + zeros, lp + zeros, nl - zeros);
                // h*p+l<=(B^nh-1)*p+(p-1)<B^nh*p, limited by nh+np limbs,
                // so inc won't overflow
                if (cy)
                    lmmp_inc(dst + nl);
            } else {
                lmmp_copy(dst, lp, nl);
                if (zeros > nl)
                    lmmp_zero(dst + nl, zeros - nl);
            }
 
            limbs = nh + np + zeros;
            limbs -= dst[limbs - 1] == 0;
        }
    }
 
    return limbs;
}

引用了 mp_basepow_t::base, mp_basepow_t::digits, FROM_STR_DIVIDE_THRESHOLD, lmmp_add_n_(), lmmp_copy, lmmp_from_str_basecase_(), lmmp_from_str_divide_(), lmmp_from_str_len_(), lmmp_inc, lmmp_mul_(), lmmp_param_assert, lmmp_zero, mp_basepow_t::np, mp_basepow_t::p, tp , 以及 mp_basepow_t::zeros.

被这些函数引用 lmmp_from_str_() , 以及 lmmp_from_str_divide_().

函数调用图:

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

lmmp_from_str_len_()

mp_size_t lmmp_from_str_len_	(	const mp_byte_t *	src,
		mp_size_t	len,
		int	base
	)

计算字符串转大数所需的 limb 缓冲区长度

参数

src	输入字符串指针
len	字符串长度
base	字符串的基数（2~256）

返回

存储该字符串数值所需的 limb 缓冲区长度

警告

len>=0, 2<=base<=256

注解

将会忽略前导零，

1. if (src!=NULL) 返回的长度可能会多分配一个 limb 空间
2. if (src==NULL) 返回len位base进制数的最大可能 limb 长度（最坏情况）

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

                                                                            {
    lmmp_param_assert(base >= 2 && base <= 256);
    if (src) {
        do {
            if (len == 0)
                return 1;
        } while (src[--len] == 0);
        ++len;
    }
    return lmmp_mulh_(len, lmmp_bases_table[base - 2].lg_base) + 1;
}

引用了 lmmp_bases_table, lmmp_mulh_() , 以及 lmmp_param_assert.

被这些函数引用 lmmp_from_str_(), lmmp_from_str_divide_() , 以及 lmmp_to_str_().

函数调用图:

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