#include "../../../include/lammp/lmmpn.h"
#include "../../../include/lammp/numth.h"
#include "../../../include/lammp/impl/longlong.h"

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

函数
int	lmmp_leading_zeros_ (mp_limb_t x)
	计算一个单精度数(limb)中前导零的个数

int	lmmp_limb_bits_ (mp_limb_t x)
	计算满足 2^k > x 的最小自然数k

int	lmmp_limb_popcnt_ (mp_limb_t x)
	计算一个64位无符号整数中1的个数

mp_limb_t	lmmp_mulh_ (mp_limb_t a, mp_limb_t b)
	计算两个64位无符号整数相乘的高位结果 (a*b)/2^64

void	lmmp_mullh_ (mp_limb_t a, mp_limb_t b, mp_ptr restrict dst)

ulong	lmmp_mulmod_ulong_ (ulong a, ulong b, ulong mod, ulongp restrict q)

int	lmmp_tailing_zeros_ (mp_limb_t x)
	计算一个单精度数(limb)中末尾零的个数

函数说明

◆ lmmp_leading_zeros_()

int lmmp_leading_zeros_ ( mp_limb_t x )

计算一个单精度数(limb)中前导零的个数

参数

x	输入的64位无符号整数

返回: 前导零的位数（范围：0~64）

在文件 tiny.c 第 35 行定义.

                                     {
    if (x == 0) return 64;
#ifdef __GNUC__
    return __builtin_clzll(x);
#elif _MSC_VER
    unsigned long index;
    _BitScanReverse64(&index, x);  
    return 63 - (int)index;
#else
    int n = 0;
    if (x <= 0x00000000FFFFFFFF) { n += 32; x <<= 32; }
    if (x <= 0x0000FFFFFFFFFFFF) { n += 16; x <<= 16; }
    if (x <= 0x00FFFFFFFFFFFFFF) { n += 8;  x <<= 8; }
    if (x <= 0x0FFFFFFFFFFFFFFF) { n += 4;  x <<= 4; }
    if (x <= 0x3FFFFFFFFFFFFFFF) { n += 2;  x <<= 2; }
    if (x <= 0x7FFFFFFFFFFFFFFF) { n += 1;  x <<= 1; }
#endif
}

被这些函数引用 lmmp_bninv_(), lmmp_div_(), lmmp_div_1_(), lmmp_div_2_(), lmmp_inv_(), lmmp_mod_1_(), lmmp_mod_2_(), lmmp_mulmod_ulong_(), lmmp_pow_basecase_(), lmmp_sqrt_(), lmmp_sqrt_newton_(), lmmp_to_str_() , 以及 mont63_R2().

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

◆ lmmp_limb_bits_()

int lmmp_limb_bits_ ( mp_limb_t x )

计算满足 2^k > x 的最小自然数k

参数

x	输入的64位无符号整数

返回: 满足条件的最小自然数k

在文件 tiny.c 第 11 行定义.

                                 {
    int k = 0;
    while (x) {
        x >>= 1;
        k++;
    }
    return k;
}

引用了 k.

被这些函数引用 lmmp_extract_bits_(), lmmp_from_str_(), lmmp_lehmer_extract_(), lmmp_pow_(), lmmp_to_str_() , 以及 lmmp_to_str_len_().

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

◆ lmmp_limb_popcnt_()

int lmmp_limb_popcnt_ ( mp_limb_t x )

计算一个64位无符号整数中1的个数

参数

x	输入的64位无符号整数

返回: 1的个数

在文件 tiny.c 第 20 行定义.

                                   {
#ifdef __GNUC__
  return __builtin_popcountll(x);
#elif _MSC_VER
  return (int)__popcnt64(x);
#else
    int k = 0;
    while (x) {
        k += x & 1;
        x >>= 1;
    }
    return k;
#endif
}

引用了 k.

被这些函数引用 lmmp_factorial_size_(), lmmp_multinomial_(), lmmp_nCr_size_(), lmmp_nPr_size_() , 以及 lmmp_pow_().

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

◆ lmmp_mulh_()

mp_limb_t lmmp_mulh_	(	mp_limb_t	a,
		mp_limb_t	b
	)

计算两个64位无符号整数相乘的高位结果 (a*b)/2^64

参数

a	第一个64位无符号整数
b	第二个64位无符号整数

返回: 乘积的高64位结果

在文件 tiny.c 第 73 行定义.

                                               {
#if (defined(__GNUC__) || defined(__clang__)) && defined(__SIZEOF_INT128__)
    __uint128_t t = (__uint128_t)a * (__uint128_t)b;
    return (mp_limb_t)(t >> 64);
#elif defined(_MSC_VER) && (defined(_M_X64) || defined(_M_ARM64))
    return __umulh(a, b);
#else
    uint64_t ah = a >> 32, bh = b >> 32;
    a = (uint32_t)a, b = (uint32_t)b;
    uint64_t r0 = a * b, r1 = a * bh, r2 = ah * b, r3 = ah * bh;
    r3 += (r1 >> 32) + (r2 >> 32);
    r1 = (uint32_t)r1, r2 = (uint32_t)r2;
    r1 += r2;
    r1 += (r0 >> 32);
    return r3 + (r1 >> 32);
#endif
}

引用了 r0, r1, r2 , 以及 r3.

被这些函数引用 lmmp_from_str_len_(), lmmp_to_str_basecase_() , 以及 lmmp_to_str_len_().

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

◆ lmmp_mullh_()

void lmmp_mullh_	(	mp_limb_t	a,
		mp_limb_t	b,
		mp_ptr restrict	dst
	)

在文件 tiny.c 第 91 行定义.

                                                                {
#if (defined(__GNUC__) || defined(__clang__)) && defined(__SIZEOF_INT128__)
    __uint128_t prod = (__uint128_t)a * b;
    dst[0] = (mp_limb_t)prod;        
    dst[1] = (mp_limb_t)(prod >> 64);
#elif defined(_MSC_VER) && (defined(_M_X64) || defined(_M_ARM64))
    dst[0] = _umul128(a, b, dst + 1);
#else
    uint64_t ah = a >> 32, bh = b >> 32;
    a = (uint32_t)a, b = (uint32_t)b;
    uint64_t r0 = a * b, r1 = a * bh, r2 = ah * b, r3 = ah * bh;
    r3 += (r1 >> 32) + (r2 >> 32);
    r1 = (uint32_t)r1, r2 = (uint32_t)r2;
    r1 += r2;
    r1 += (r0 >> 32);
    dst[1] = r3 + (r1 >> 32);
    dst[0] = (r1 << 32) | (uint32_t)r0;
#endif
}

引用了 r0, r1, r2 , 以及 r3.

◆ lmmp_mulmod_ulong_()

ulong lmmp_mulmod_ulong_	(	ulong	a,
		ulong	b,
		ulong	mod,
		ulongp restrict	q
	)

在文件 tiny.c 第 111 行定义.

                                                                         {
    int shl = lmmp_leading_zeros_(mod);
    mod <<= shl;
    ulong inv = lmmp_inv_1_(mod);
    ulong ab[2];
    ulong r;
    _umul64to128_(a, b, ab, ab + 1);
    if (shl > 0)
        _u128lshl(ab, ab, shl);
    _udiv_qrnnd_preinv(*q, r, ab[1], ab[0], mod, inv);
    return r >> shl;
}

引用了 _u128lshl, _udiv_qrnnd_preinv, _umul64to128_(), lmmp_inv_1_() , 以及 lmmp_leading_zeros_().

函数调用图:

◆ lmmp_tailing_zeros_()

int lmmp_tailing_zeros_ ( mp_limb_t x )

计算一个单精度数(limb)中末尾零的个数

参数

x	输入的64位无符号整数

返回: 末尾零的位数（范围：0~64）

在文件 tiny.c 第 54 行定义.

                                     {
    if (x == 0) return 64;
#ifdef __GNUC__
    return __builtin_ctzll(x);
#elif _MSC_VER
    unsigned long index;
    _BitScanForward64(&index, x);
    return (int)index;
#else
    int n = 0;
    if ((x & 0x00000000FFFFFFFF) == 0) { n += 32; x >>= 32; }
    if ((x & 0x000000000000FFFF) == 0) { n += 16; x >>= 16; }
    if ((x & 0x00000000000000FF) == 0) { n += 8;  x >>= 8; }
    if ((x & 0x000000000000000F) == 0) { n += 4;  x >>= 4; }
    if ((x & 0x0000000000000003) == 0) { n += 2;  x >>= 2; }
    if ((x & 0x0000000000000001) == 0) { n += 1;  x >>= 1; }
#endif
}

被这些函数引用 lmmp_from_str_(), lmmp_gcd_11_(), lmmp_gcd_22_(), lmmp_pow_(), lmmp_pow_1_(), lmmp_to_str_() , 以及 pow_nPr_().

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