mullo.c 文件参考

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

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

浏览源代码.

宏定义
#define	a0   (numa)
#define	a0   (numa)
#define	a1   (numa + m)
#define	a1   (numa + m)
#define	b0   (numb)
#define	b1   (numb + m)
#define	c0   (dst)
#define	c0   (dst)
#define	c1   (dst + m)
#define	c1   (dst + m)
#define	lo   (tp)
#define	lo1   (tp)
#define	lo2   (tp + t)
#define	MUL_TOOM66_THRESHOLD   MUL_FFT_THRESHOLD
#define	MUL_TOOM88_THRESHOLD   5621
#define	scratch   (tp + 2 * t)
#define	scratch   (tp + t)

函数
void	lmmp_mullo_ (mp_ptr restrict dst, mp_srcptr restrict numa, mp_srcptr restrict numb, mp_size_t n)
void	lmmp_mullo_dc_ (mp_ptr restrict dst, mp_srcptr restrict numa, mp_srcptr restrict numb, mp_ptr restrict tp, mp_size_t n)
void	lmmp_mullo_fft_ (mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n, mp_ptr scratch)
	Copyright (C) 2026 HJimmyK(Jericho Knox)
void	lmmp_sqrlo_dc_ (mp_ptr restrict dst, mp_srcptr restrict numa, mp_ptr restrict tp, mp_size_t n)

宏定义说明

a0 [1/2]

#define a0   (numa)

a0 [2/2]

#define a0   (numa)

a1 [1/2]

#define a1   (numa + m)

a1 [2/2]

#define a1   (numa + m)

b0

#define b0   (numb)

b1

#define b1   (numb + m)

c0 [1/2]

#define c0   (dst)

c0 [2/2]

#define c0   (dst)

c1 [1/2]

#define c1   (dst + m)

c1 [2/2]

#define c1   (dst + m)

lo

#define lo   (tp)

lo1

#define lo1   (tp)

lo2

#define lo2   (tp + t)

MUL_TOOM66_THRESHOLD

#define MUL_TOOM66_THRESHOLD   MUL_FFT_THRESHOLD

在文件 mullo.c 第 116 行定义.

MUL_TOOM88_THRESHOLD

#define MUL_TOOM88_THRESHOLD   5621

在文件 mullo.c 第 117 行定义.

scratch [1/2]

#define scratch   (tp + 2 * t)

scratch [2/2]

#define scratch   (tp + t)

函数说明

lmmp_mullo_()

void lmmp_mullo_	(	mp_ptr restrict	dst,
		mp_srcptr restrict	numa,
		mp_srcptr restrict	numb,
		mp_size_t	n
	)

在文件 mullo.c 第 219 行定义.

                                                                                                     {
    lmmp_param_assert(n > 0);
    if (n < MULLO_DC_THRESHOLD) {
        if (numa == numb) {
            TEMP_DECL;
            mp_ptr restrict tp = TALLOC_TYPE(2 * n, mp_limb_t);
            lmmp_sqrlo_dc_(dst, numa, tp, n);
            TEMP_FREE;
            return;
        }
        TEMP_DECL;
        mp_ptr restrict tp = TALLOC_TYPE(2 * n, mp_limb_t);
        lmmp_mullo_dc_(dst, numa, numb, tp, n);
        TEMP_FREE;
        return;
    } else {
        TEMP_DECL;
        mp_ptr restrict tp = TALLOC_TYPE(2 * n, mp_limb_t);
        lmmp_mullo_fft_(dst, numa, numb, n, tp);
        TEMP_FREE;
        return;
    }
}

引用了 lmmp_mullo_dc_(), lmmp_mullo_fft_(), lmmp_param_assert, lmmp_sqrlo_dc_(), MULLO_DC_THRESHOLD, n, numb, TALLOC_TYPE, TEMP_DECL, TEMP_FREE , 以及 tp.

函数调用图:

lmmp_mullo_dc_()

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

在文件 mullo.c 第 119 行定义.

  {
    if (n < MULLO_BASECASE_THRESHOLD) {
        lmmp_mul_1_(dst, numa, n, numb[0]);
        for (mp_size_t i = 1; i < n; ++i) {
            lmmp_mul_1_(tp, numa, n - i, numb[i]);
            lmmp_add_n_(dst + i, dst + i, tp, n - i);
        }
        return;
    } else {
        mp_size_t m, t;
        if (n < MUL_TOOM33_THRESHOLD) {
            m = 25 * n / 36;
        } else if (n < MUL_TOOM44_THRESHOLD) {
            m = 31 * n / 40;
        } else if (n < MUL_TOOM66_THRESHOLD) {
            m = 32 * n / 39;
        } else if (n < MUL_TOOM88_THRESHOLD) {
            m = 27 * n / 31;
        } else {
            m = 9 * n / 10;
        }
        t = n - m;
        lmmp_debug_assert(2 * n > 4 * t);
 
#define a0 (numa)             // [numa,     m]
#define a1 (numa + m)         // [numa+m,   t]
#define b0 (numb)             // [numb,     m]
#define b1 (numb + m)         // [numb+m,   t]
#define c0 (dst)              // [dst,      m]
#define c1 (dst + m)          // [dst+m,    t]
#define lo1 (tp)              // [tp,       t]
#define lo2 (tp + t)          // [tp+t,     t]
#define scratch (tp + 2 * t)  // [tp+2*t, 2*t]
        lmmp_mul_n_(tp, a0, b0, m);
        lmmp_copy(c0, tp, n);
        lmmp_mullo_dc_(lo1, a1, b0, scratch, t);
        lmmp_mullo_dc_(lo2, a0, b1, scratch, t);
        lmmp_add_n_(c1, c1, lo1, t);
        lmmp_add_n_(c1, c1, lo2, t);
        return;
    }
#undef a0
#undef a1
#undef b0
#undef b1
#undef c0
#undef c1
#undef lo1
#undef lo2
#undef scratch
}

引用了 a0, a1, b0, b1, c0, c1, lmmp_add_n_(), lmmp_copy, lmmp_debug_assert, lmmp_mul_1_(), lmmp_mul_n_, lmmp_mullo_dc_(), lo1, lo2, MUL_TOOM33_THRESHOLD, MUL_TOOM44_THRESHOLD, MUL_TOOM66_THRESHOLD, MUL_TOOM88_THRESHOLD, MULLO_BASECASE_THRESHOLD, n, numb, scratch, t , 以及 tp.

被这些函数引用 lmmp_mullo_(), lmmp_mullo_dc_() , 以及 lmmp_sqrlo_dc_().

函数调用图:

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

lmmp_mullo_fft_()

void lmmp_mullo_fft_	(	mp_ptr	dst,
		mp_srcptr	numa,
		mp_srcptr	numb,
		mp_size_t	n,
		mp_ptr	scratch
	)

Copyright (C) 2026 HJimmyK(Jericho Knox)

低位FFT乘法 [dst,n] = [numa,n] * [numb,n] mod B^n

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/.

在文件 mullo.c 第 22 行定义.

                                                                                              {
    lmmp_param_assert(n > 0);
    mp_size_t hn = lmmp_fft_next_size_((n + n + 1) >> 1);
    lmmp_assert(n + n > hn);
    mp_ptr tp = ALLOC_TYPE(hn + 1, mp_limb_t);
 
    mp_srcptr amodm = numa;
    mp_size_t nam = n;
    if (n > hn) {
        /*
          Z = B^hb - 1
          amodm = a mod Z
         */
        if (lmmp_add_(scratch, numa, hn, numa + hn, n - hn))
            lmmp_inc(scratch);
        amodm = scratch;
        nam = hn;
    }
    lmmp_mul_mersenne_(scratch, hn, amodm, nam, numb, n);
 
    mp_srcptr amodp = numa;
    mp_size_t nap = n;
    if (n > hn) {
        /*
          Z = B^hp - 1
          amodp = a mod Z
         */
        tp[hn] = 0;
        if (lmmp_sub_(tp, numa, hn, numa + hn, n - hn))
            lmmp_inc(tp);
        amodp = tp;
        nap = hn + 1;
    }
    lmmp_mul_fermat_(tp, hn, amodp, nap, numb, n);
 
    mp_limb_t cy = lmmp_shr1add_nc_(scratch, scratch, tp, hn, tp[hn]);
    cy <<= LIMB_BITS - 1;
    scratch[hn - 1] += cy;
    if (scratch[hn - 1] < cy)
        lmmp_inc(scratch);
 
    if (n == hn) {
        cy = tp[hn] + lmmp_sub_n_(scratch + hn, scratch, tp, hn);
        // cy==1 means [tp,hn+1]!=0, then [dst,hn]!=0
        // cy==2 is impossible since [tp,hn+1] is normalized.
        // so the following dec won't overflow.
        lmmp_dec_1(scratch, cy);
    } else {
        mp_size_t n2 = 2 * n;
        cy = lmmp_sub_n_(scratch + hn, scratch, tp, n2 - hn);
        cy = tp[hn] + lmmp_sub_nc_(tp + n2 - hn, scratch + n2 - hn, tp + n2 - hn, 2 * hn - n2, cy);
        cy = lmmp_sub_1_(scratch, scratch, n2, cy);
    }
    lmmp_free(tp);
    lmmp_copy(dst, scratch, n);
}

引用了 ALLOC_TYPE, LIMB_BITS, lmmp_add_(), lmmp_assert, lmmp_copy, lmmp_dec_1, lmmp_fft_next_size_(), lmmp_free(), lmmp_inc, lmmp_mul_fermat_(), lmmp_mul_mersenne_(), lmmp_param_assert, lmmp_shr1add_nc_(), lmmp_sub_(), lmmp_sub_1_(), lmmp_sub_n_(), lmmp_sub_nc_(), n, numb, scratch , 以及 tp.

被这些函数引用 lmmp_mullo_(), lmmp_mullo_n_(), lmmp_mullo_n_() , 以及 lmmp_sqrlo_n_().

函数调用图:

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

lmmp_sqrlo_dc_()

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

在文件 mullo.c 第 177 行定义.

                                                                                                   {
    if (n < MULLO_BASECASE_THRESHOLD) {
        lmmp_mul_1_(dst, numa, n, numa[0]);
        for (mp_size_t i = 1; i < n; ++i) {
            lmmp_mul_1_(tp, numa, n - i, numa[i]);
            lmmp_add_n_(dst + i, dst + i, tp, n - i);
        }
        return;
    } else {
        mp_size_t m, t;
        if (n < MUL_TOOM33_THRESHOLD) {
            m = 25 * n / 36;
        } else if (n < MUL_TOOM44_THRESHOLD) {
            m = 31 * n / 40;
        } else if (n < MUL_TOOM66_THRESHOLD) {
            m = 32 * n / 39;
        } else if (n < MUL_TOOM88_THRESHOLD) {
            m = 27 * n / 31;
        } else {
            m = 9 * n / 10;
        }
        t = n - m;
 
#define a0 (numa)
#define a1 (numa + m)
#define c0 (dst)
#define c1 (dst + m)
#define lo (tp)          // [tp, t]
#define scratch (tp + t) // [tp+t, 2*t]
        lmmp_sqr_(tp, a0, m);
        lmmp_copy(c0, tp, n);
        lmmp_mullo_dc_(lo, a0, a1, scratch, t);
        lmmp_addshl1_n_(c1, c1, lo, t);
    }
#undef a0
#undef a1
#undef c0
#undef c1
#undef lo
#undef scratch
}

引用了 a0, a1, c0, c1, lmmp_add_n_(), lmmp_addshl1_n_(), lmmp_copy, lmmp_mul_1_(), lmmp_mullo_dc_(), lmmp_sqr_, lo, MUL_TOOM33_THRESHOLD, MUL_TOOM44_THRESHOLD, MUL_TOOM66_THRESHOLD, MUL_TOOM88_THRESHOLD, MULLO_BASECASE_THRESHOLD, n, scratch, t , 以及 tp.

被这些函数引用 lmmp_mullo_().

函数调用图:

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