binvert.c 文件参考

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

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

浏览源代码.

宏定义
#define	a_binvert   (tp)
#define	ahi   (numa + halfn)
#define	ahi   (numa + halfn)
#define	alo   (numa)
#define	alo   (numa)
#define	k   (tp)
#define	k   (tp)
#define	k   (tp + 1 * na)
#define	scratch   (tp + 3 * halfn)
#define	scratch   (tp + 3 * halfn)
#define	scratch   (tp + 2 * na)
#define	xhi   (dst + halfn)
#define	xhi   (dst + halfn)
#define	xlo   (dst)
#define	xlo   (dst)
#define	xlo_sqr   (tp + halfn)
#define	xlo_sqr   (tp + halfn)
#define	xlo_sqr_mul_ahi   (tp + 2 * halfn)
#define	xlo_sqr_mul_ahi   (tp + 2 * halfn)

函数
static void	binvert_mulhi_ (mp_ptr dst, mp_srcptr xp, mp_srcptr ap, mp_size_t n, mp_ptr tp)
	Copyright (C) 2026 HJimmyK(Jericho Knox)
void	lmmp_binvert_ (mp_ptr restrict dst, mp_srcptr restrict numa, mp_size_t na, mp_size_t n)
void	lmmp_binvert_n_dc_ (mp_ptr restrict dst, mp_srcptr restrict numa, mp_size_t n, mp_ptr restrict tp)
void	lmmp_binvert_unbalanced_ (mp_ptr restrict dst, mp_srcptr restrict numa, mp_size_t na, mp_size_t n, mp_ptr restrict tp)
static void	lmmp_mullo_n_ (mp_ptr restrict dst, mp_srcptr restrict numa, mp_srcptr restrict numb, mp_size_t n, mp_ptr restrict tp)
static void	lmmp_sqrlo_n_ (mp_ptr restrict dst, mp_srcptr restrict numa, mp_size_t n, mp_ptr restrict tp)

宏定义说明

a_binvert

#define a_binvert   (tp)

ahi [1/2]

#define ahi   (numa + halfn)

ahi [2/2]

#define ahi   (numa + halfn)

alo [1/2]

#define alo   (numa)

alo [2/2]

#define alo   (numa)

k [1/3]

#define k   (tp)

k [2/3]

#define k   (tp)

k [3/3]

#define k   (tp + 1 * na)

scratch [1/3]

#define scratch   (tp + 3 * halfn)

scratch [2/3]

#define scratch   (tp + 3 * halfn)

scratch [3/3]

#define scratch   (tp + 2 * na)

xhi [1/2]

#define xhi   (dst + halfn)

xhi [2/2]

#define xhi   (dst + halfn)

xlo [1/2]

#define xlo   (dst)

xlo [2/2]

#define xlo   (dst)

xlo_sqr [1/2]

#define xlo_sqr   (tp + halfn)

xlo_sqr [2/2]

#define xlo_sqr   (tp + halfn)

xlo_sqr_mul_ahi [1/2]

#define xlo_sqr_mul_ahi   (tp + 2 * halfn)

xlo_sqr_mul_ahi [2/2]

#define xlo_sqr_mul_ahi   (tp + 2 * halfn)

函数说明

binvert_mulhi_()

static void binvert_mulhi_ ( mp_ptr  dst, mp_srcptr  xp, mp_srcptr  ap, mp_size_t  n, mp_ptr  tp  )

inlinestatic

Copyright (C) 2026 HJimmyK(Jericho Knox)

This file is part of LAMMP.

LAMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License (LGPL) as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This program is distributed WITHOUT ANY WARRANTY.

See https://www.gnu.org/licenses/.

计算 [dst,n] = [xp,n]*[ap,n] div B^n

参数

dst	结果指针
tp	scratch space, need 2*n limbs

警告

[xp,n] * [ap,n] mod B^n == 1

在文件 binvert.c 第 28 行定义.

                                                                                                  {
    if (n < MULHI_MERSENNE_THRESHOLD) {
        lmmp_mul_n_(tp, xp, ap, n);
        lmmp_copy(dst, tp + n, n);
    } else {
        mp_size_t m = lmmp_fft_next_size_((n * 2 + 1) >> 1);
        lmmp_debug_assert(n * 2 > m && m >= n);
        lmmp_mul_mersenne_(tp, m, xp, n, ap, n);
        lmmp_dec(tp);
        mp_size_t fn = m - n;   // 从 tp+n 开始的长度
        mp_size_t sn = n - fn;  // 从 tp 开始的长度
        lmmp_copy(dst, tp + n, fn);
        lmmp_copy(dst + fn, tp, sn);
    }
}

引用了 lmmp_copy, lmmp_debug_assert, lmmp_dec, lmmp_fft_next_size_(), lmmp_mul_mersenne_(), lmmp_mul_n_, MULHI_MERSENNE_THRESHOLD, n , 以及 tp.

被这些函数引用 lmmp_binvert_n_dc_() , 以及 lmmp_binvert_unbalanced_().

函数调用图:

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

lmmp_binvert_()

void lmmp_binvert_	(	mp_ptr restrict	dst,
		mp_srcptr restrict	numa,
		mp_size_t	na,
		mp_size_t	n
	)

在文件 binvert.c 第 218 行定义.

                                                                                            {
    lmmp_param_assert(dst != NULL && numa != NULL);
    lmmp_param_assert(na > 0 && n > 0);
    lmmp_param_assert(numa[0] % 2 == 1);
    TEMP_DECL;
    if (n == na) {
        mp_ptr restrict tp = ALLOC_TYPE(5 * (n + 1) / 2, mp_limb_t);
        lmmp_binvert_n_dc_(dst, numa, na, tp);
    } else if (na == 1) {
        lmmp_binvert_unbalanced_1_(dst, numa[0], n);
    } else if (na == 2) {
        lmmp_binvert_unbalanced_2_(dst, numa, n);
    } else if (4 * n >= 5 * na) {
        // n/na >= 5/4 这是一个比较简单的调优结果
        mp_ptr restrict tp = ALLOC_TYPE((9 * n + 5) / 2, mp_limb_t);
        lmmp_binvert_unbalanced_(dst, numa, na, n, tp);
    } else {
        mp_ptr restrict ap = ALLOC_TYPE(n, mp_limb_t);
        mp_ptr restrict tp = ALLOC_TYPE((5 * n + 5) / 2, mp_limb_t);
        lmmp_copy(ap, numa, n);
        lmmp_zero(ap + na, n - na);
        lmmp_binvert_n_dc_(dst, ap, n, tp);
    }
    TEMP_FREE;
}

引用了 ALLOC_TYPE, lmmp_binvert_n_dc_(), lmmp_binvert_unbalanced_(), lmmp_binvert_unbalanced_1_(), lmmp_binvert_unbalanced_2_(), lmmp_copy, lmmp_param_assert, lmmp_zero, n, TEMP_DECL, TEMP_FREE , 以及 tp.

函数调用图:

lmmp_binvert_n_dc_()

void lmmp_binvert_n_dc_	(	mp_ptr restrict	dst,
		mp_srcptr restrict	numa,
		mp_size_t	n,
		mp_ptr restrict	tp
	)

在文件 binvert.c 第 106 行定义.

                                                                                                       {
    lmmp_param_assert(dst != NULL && tp != NULL);
    lmmp_param_assert(numa != NULL && n > 0);
    lmmp_param_assert(numa[0] % 2 == 1);
    if (n == 1) {
        dst[0] = lmmp_binvert_ulong_(numa[0]);
    } else if (n == 2) {
        lmmp_binvert_2_(dst, numa);
    } else if (n == 3) {
        lmmp_binvert_3_(dst, numa);
    } else if (n == 4) {
        lmmp_binvert_4_(dst, numa);
    } else if (n % 2 == 0) {
        mp_size_t halfn = n / 2;
 
#define k               (tp)              // [tp,          halfn]
#define alo             (numa)            // [numa,        halfn]
#define ahi             (numa + halfn)    // [numa+halfn,  halfn]
#define xlo             (dst)             // [dst,         halfn]
#define xhi             (dst + halfn)     // [dst+halfn,   halfn]
#define xlo_sqr         (tp + halfn)      // [tp+halfn,    halfn]
#define xlo_sqr_mul_ahi (tp + 2 * halfn)  // [tp+2*halfn,  halfn]
#define scratch         (tp + 3 * halfn)  // [tp+3*halfn,2*halfn]
//      ________________________________________________________________
// tp : |_________________________5*(n+1)/2____________________________|
//      |   k   | xlo_sqr | xlo_sqr_mul_ahi |   scratch   | remaining  |
//      |_halfn_|__halfn__|______halfn______|___2*halfn___|            |
 
        lmmp_binvert_n_dc_(xlo, alo, halfn, tp);
        binvert_mulhi_(k, xlo, alo, halfn, tp + halfn);
        lmmp_sqrlo_n_(xlo_sqr, xlo, halfn, scratch);
        lmmp_mullo_n_(xlo_sqr_mul_ahi, ahi, xlo_sqr, halfn, scratch);
        lmmp_mullo_n_(xhi, xlo, k, halfn, scratch);
        lmmp_add_n_(xhi, xhi, xlo_sqr_mul_ahi, halfn);
        lmmp_not_(xhi, xhi, halfn);
        lmmp_inc(xhi);
    } else {
        mp_size_t halfn = n / 2 + 1;
        mp_size_t ahin = n - halfn;
 
#define k               (tp)              // [tp,          halfn]
#define alo             (numa)            // [numa,        halfn]
#define ahi             (numa + halfn)    // [numa+halfn,   ahin]
#define xlo             (dst)             // [dst,         halfn]
#define xhi             (dst + halfn)     // [dst+halfn,    ahin]
#define xlo_sqr         (tp + halfn)      // [tp+halfn,     ahin]
#define xlo_sqr_mul_ahi (tp + 2 * halfn)  // [tp+2*halfn,   ahin]
#define scratch         (tp + 3 * halfn)  // [tp+3*halfn, 2*ahin]
//      ________________________________________________________________
// tp : |_________________________5*(n+1)/2____________________________|
//      |    k    | xlo_sqr | xlo_sqr_mul_ahi |   scratch  | remaining |
//      |__halfn__|__halfn__|______halfn______|___2*ahin___|           |
 
        lmmp_binvert_n_dc_(xlo, alo, halfn, tp);
        binvert_mulhi_(k, xlo, alo, halfn, tp + halfn);
        lmmp_sqrlo_n_(xlo_sqr, xlo, ahin, scratch);
        lmmp_mullo_n_(xlo_sqr_mul_ahi, ahi, xlo_sqr, ahin, scratch);
        lmmp_mullo_n_(xhi, xlo, k, ahin, scratch);
        lmmp_add_n_(xhi, xhi, xlo_sqr_mul_ahi, ahin);
        lmmp_not_(xhi, xhi, ahin);
        lmmp_inc(xhi);
    }
#undef k
#undef alo
#undef ahi
#undef xlo
#undef xhi
#undef xlo_sqr
#undef xlo_sqr_mul_ahi
#undef scratch
}

引用了 ahi, alo, binvert_mulhi_(), k, lmmp_add_n_(), lmmp_binvert_2_(), lmmp_binvert_3_(), lmmp_binvert_4_(), lmmp_binvert_n_dc_(), lmmp_binvert_ulong_(), lmmp_inc, lmmp_mullo_n_(), lmmp_not_(), lmmp_param_assert, lmmp_sqrlo_n_(), n, scratch, tp, xhi, xlo, xlo_sqr , 以及 xlo_sqr_mul_ahi.

被这些函数引用 lmmp_binvert_(), lmmp_binvert_n_dc_() , 以及 lmmp_binvert_unbalanced_().

函数调用图:

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

lmmp_binvert_unbalanced_()

void lmmp_binvert_unbalanced_	(	mp_ptr restrict	dst,
		mp_srcptr restrict	numa,
		mp_size_t	na,
		mp_size_t	n,
		mp_ptr restrict	tp
	)

在文件 binvert.c 第 178 行定义.

                                                                                                                           {
    lmmp_param_assert(dst != NULL && numa != NULL && tp != NULL);
    lmmp_param_assert(numa[0] % 2 == 1);
    lmmp_param_assert(n > na && na > 0);
 
#define a_binvert (tp)             // [tp,              na]
#define k         (tp + 1 * na)    // [tp+na,           na]
#define scratch   (tp + 2 * na)    // [tp+2*na, 5*(na+1)/2]
 
    lmmp_binvert_n_dc_(a_binvert, numa, na, scratch);
    lmmp_copy(dst, a_binvert, na);
    binvert_mulhi_(k, a_binvert, numa, na, scratch);
 
    // a_binvert 低位不可能为0，故加一不会进位
    lmmp_debug_assert(a_binvert[0] != 0);
    lmmp_not_(a_binvert, a_binvert, na);
    a_binvert[0] += 1;
 
    mp_size_t i = na;
    for (; i < n - na; i += na) {
        lmmp_mullo_n_(dst + i, a_binvert, k, na, scratch);
        /*
        FIXME: 这里的循环中，第二个乘数numa，始终保持不变
               在拥有可以惰性初始化的FFT算法的情况下，可以节省numa的正变换
               在循环的情况下，这将会有可观的性能提升
        */
        lmmp_mul_n_(scratch, dst + i, numa, na);
        // now [scratch,2*na] = a * p
        if (lmmp_add_n_(scratch, scratch, k, na)) {
            lmmp_inc(scratch + na);
        }
        lmmp_copy(k, scratch + na, na);
    }
 
    lmmp_mullo_n_(dst + i, a_binvert, k, n - i, scratch);
#undef a_binvert
#undef k
#undef scratch
}

引用了 a_binvert, binvert_mulhi_(), k, lmmp_add_n_(), lmmp_binvert_n_dc_(), lmmp_copy, lmmp_debug_assert, lmmp_inc, lmmp_mul_n_, lmmp_mullo_n_(), lmmp_not_(), lmmp_param_assert, n, scratch , 以及 tp.

被这些函数引用 lmmp_binvert_().

函数调用图:

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

lmmp_mullo_n_()

static void lmmp_mullo_n_ ( mp_ptr restrict  dst, mp_srcptr restrict  numa, mp_srcptr restrict  numb, mp_size_t  n, mp_ptr restrict  tp  )

inlinestatic

在文件 binvert.c 第 57 行定义.

  {
    if (n < MULLO_DC_THRESHOLD) {
        lmmp_mullo_dc_(dst, numa, numb, tp, n);
    } else {
        lmmp_mullo_fft_(dst, numa, numb, n, tp);
    }
}

引用了 lmmp_mullo_dc_(), lmmp_mullo_fft_(), MULLO_DC_THRESHOLD, n, numb , 以及 tp.

被这些函数引用 lmmp_binvert_n_dc_() , 以及 lmmp_binvert_unbalanced_().

函数调用图:

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

lmmp_sqrlo_n_()

static void lmmp_sqrlo_n_ ( mp_ptr restrict  dst, mp_srcptr restrict  numa, mp_size_t  n, mp_ptr restrict  tp  )

inlinestatic

在文件 binvert.c 第 44 行定义.

  {
    if (n < MULLO_DC_THRESHOLD) {
        lmmp_sqrlo_dc_(dst, numa, tp, n);
    } else {
        lmmp_mullo_fft_(dst, numa, numa, n, tp);
    }
}

引用了 lmmp_mullo_fft_(), lmmp_sqrlo_dc_(), MULLO_DC_THRESHOLD, n , 以及 tp.

被这些函数引用 lmmp_binvert_n_dc_().

函数调用图:

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