perfsqr.c 文件参考

#include "../../../include/lammp/numth.h"

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

浏览源代码.

宏定义
#define	ADD(c, a, val)
#define	B1   (LIMB_BITS / 4)
#define	B2   (B1 * 2)
#define	B3   (B1 * 3)
#define	HIGH0(n)   ((n) >> B3)
#define	HIGH1(n)   ((n) >> B2)
#define	HIGH2(n)   ((n) >> B1)
#define	LOW0(n)   ((n) & M3)
#define	LOW1(n)   (((n) & M2) << B1)
#define	LOW2(n)   (((n) & M1) << B2)
#define	M1   ((1ULL << B1) - 1)
#define	M2   ((1ULL << B2) - 1)
#define	M3   ((1ULL << B3) - 1)
#define	MASK48   (0xFFFFFFFFFFFF)
	Copyright (C) 2026 HJimmyK(Jericho Knox)
#define	PARTS0(n)   (LOW0(n) + HIGH0(n))
#define	PARTS1(n)   (LOW1(n) + HIGH1(n))
#define	PARTS2(n)   (LOW2(n) + HIGH2(n))

函数
static bool	is_perfsqr_p13 (uchar r)
static bool	is_perfsqr_p17 (uchar r)
static bool	is_perfsqr_p241 (ushort r)
static bool	is_perfsqr_p256 (uchar r)
static bool	is_perfsqr_p257 (ushort r)
static bool	is_perfsqr_p5 (uchar r)
static bool	is_perfsqr_p673 (ushort r)
static bool	is_perfsqr_p7 (uchar r)
static bool	is_perfsqr_p9 (uchar r)
static bool	is_perfsqr_p97 (uchar r)
mp_limb_t	lmmp_mod_2p48sub1_ (mp_srcptr p, mp_size_t n)
	计算 [p,n] % 2^48-1
bool	lmmp_perfsqr_filter_ (mp_srcptr p, mp_size_t n)
	非完全平方数过滤器
bool	lmmp_perfsqr_filter_1_ (mp_limb_t p)
	非完全平方数过滤器

宏定义说明

ADD

#define ADD	(		c,
			a,
			val
	)

值:

    do {                               \
        mp_limb_t new_a = (a) + (val); \
        (c) += new_a < (a);            \
        (a) = new_a;                   \
    } while (0)

在文件 perfsqr.c 第 43 行定义.

       {                               \
        mp_limb_t new_a = (a) + (val); \
        (c) += new_a < (a);            \
        (a) = new_a;                   \
    } while (0)

B1

#define B1   (LIMB_BITS / 4)

在文件 perfsqr.c 第 21 行定义.

B2

#define B2   (B1 * 2)

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

B3

#define B3   (B1 * 3)

在文件 perfsqr.c 第 23 行定义.

HIGH0

#define HIGH0

(

n

)

((n) >> B3)

在文件 perfsqr.c 第 30 行定义.

HIGH1

#define HIGH1

(

n

)

((n) >> B2)

在文件 perfsqr.c 第 33 行定义.

HIGH2

#define HIGH2

(

n

)

((n) >> B1)

在文件 perfsqr.c 第 36 行定义.

LOW0

#define LOW0

(

n

)

((n) & M3)

在文件 perfsqr.c 第 29 行定义.

LOW1

#define LOW1

(

n

)

(((n) & M2) << B1)

在文件 perfsqr.c 第 32 行定义.

LOW2

#define LOW2

(

n

)

(((n) & M1) << B2)

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

M1

#define M1   ((1ULL << B1) - 1)

在文件 perfsqr.c 第 25 行定义.

M2

#define M2   ((1ULL << B2) - 1)

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

M3

#define M3   ((1ULL << B3) - 1)

在文件 perfsqr.c 第 27 行定义.

MASK48

#define MASK48   (0xFFFFFFFFFFFF)

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

在文件 perfsqr.c 第 19 行定义.

PARTS0

#define PARTS0

(

n

)

(LOW0(n) + HIGH0(n))

在文件 perfsqr.c 第 38 行定义.

PARTS1

#define PARTS1

(

n

)

(LOW1(n) + HIGH1(n))

在文件 perfsqr.c 第 39 行定义.

PARTS2

#define PARTS2

(

n

)

(LOW2(n) + HIGH2(n))

在文件 perfsqr.c 第 40 行定义.

函数说明

is_perfsqr_p13()

static bool is_perfsqr_p13 ( uchar  r )

inlinestatic

在文件 perfsqr.c 第 121 行定义.

                                           {
    return r == 0 || r == 1 || r == 3 || r == 4 || r == 9 || r == 10 || r == 12;
}

被这些函数引用 lmmp_perfsqr_filter_() , 以及 lmmp_perfsqr_filter_1_().

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

is_perfsqr_p17()

static bool is_perfsqr_p17 ( uchar  r )

inlinestatic

在文件 perfsqr.c 第 125 行定义.

                                           {
    return r == 0 || r == 1 || r == 2 || r == 4 || r == 8 || r == 9 || r == 13 || r == 15 || r == 16;
}

被这些函数引用 lmmp_perfsqr_filter_() , 以及 lmmp_perfsqr_filter_1_().

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

is_perfsqr_p241()

static bool is_perfsqr_p241 ( ushort  r )

inlinestatic

在文件 perfsqr.c 第 137 行定义.

                                             {
    static const uint64_t p241[] = {0x3C67A3116B15977F, 0x2FD21C174C8FA909, 0x98F24257C4CBA0E1, 0x0001FBA6A35A2317};
    ushort elem = r / 64;
    lmmp_param_assert(elem < 4);
    ushort bit = r % 64;
    return (p241[elem] >> bit) & 1ULL;
}

引用了 lmmp_param_assert , 以及 n.

被这些函数引用 lmmp_perfsqr_filter_() , 以及 lmmp_perfsqr_filter_1_().

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

is_perfsqr_p256()

static bool is_perfsqr_p256 ( uchar  r )

inlinestatic

在文件 perfsqr.c 第 164 行定义.

                                            {
    static const uint64_t p256[] = {0x0202021202030213, 0x0202021202020213, 0x0202021202030212, 0x0202021202020212};
    ushort elem = r / 64;
    lmmp_param_assert(elem < 4);
    ushort bit = r % 64;
    return (p256[elem] >> bit) & 1ULL;
}

引用了 lmmp_param_assert , 以及 n.

被这些函数引用 lmmp_perfsqr_filter_() , 以及 lmmp_perfsqr_filter_1_().

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

is_perfsqr_p257()

static bool is_perfsqr_p257 ( ushort  r )

inlinestatic

在文件 perfsqr.c 第 145 行定义.

                                             {
    static const uint64_t p257[] = {0x7E16541DE6E7AB17, 0x1F76811C93128359, 0x6B052324E205BBE3, 0xA3579D9EE0A9A1FA,
                                     0x0000000000000001};
    ushort elem = r / 64;
    lmmp_param_assert(elem < 5);
    ushort bit = r % 64;
    return (p257[elem] >> bit) & 1ULL;
}

引用了 lmmp_param_assert , 以及 n.

被这些函数引用 lmmp_perfsqr_filter_() , 以及 lmmp_perfsqr_filter_1_().

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

is_perfsqr_p5()

static bool is_perfsqr_p5 ( uchar  r )

inlinestatic

在文件 perfsqr.c 第 113 行定义.

                                          {
    return r == 0 || r == 1 || r == 4;
}

被这些函数引用 lmmp_perfsqr_filter_() , 以及 lmmp_perfsqr_filter_1_().

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

is_perfsqr_p673()

static bool is_perfsqr_p673 ( ushort  r )

inlinestatic

在文件 perfsqr.c 第 154 行定义.

                                             {
    static const uint64_t p673[] = {0x85F744B13FA573DF, 0xC231D5979ABA4F21, 0xE944C76E98DD0C01, 0xD20E0F2BD993E915,
                                     0x616259FB225208AB, 0x7E691A18F8B7B47C, 0x53C1C12F54412913, 0xDB8C8A5EA25F266F,
                                     0xA6AE310E00C2EC65, 0x348BBE8613C97567, 0x00000001EF3A97F2};
    ushort elem = r / 64;
    lmmp_param_assert(elem < 11);
    ushort bit = r % 64;
    return (p673[elem] >> bit) & 1ULL;
}

引用了 lmmp_param_assert , 以及 n.

被这些函数引用 lmmp_perfsqr_filter_() , 以及 lmmp_perfsqr_filter_1_().

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

is_perfsqr_p7()

static bool is_perfsqr_p7 ( uchar  r )

inlinestatic

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

                                          {
    return r == 0 || r == 1 || r == 2 || r == 4;
}

被这些函数引用 lmmp_perfsqr_filter_() , 以及 lmmp_perfsqr_filter_1_().

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

is_perfsqr_p9()

static bool is_perfsqr_p9 ( uchar  r )

inlinestatic

在文件 perfsqr.c 第 109 行定义.

                                          {
    return r == 0 || r == 1 || r == 4 || r == 7;
}

被这些函数引用 lmmp_perfsqr_filter_() , 以及 lmmp_perfsqr_filter_1_().

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

is_perfsqr_p97()

static bool is_perfsqr_p97 ( uchar  r )

inlinestatic

在文件 perfsqr.c 第 129 行定义.

                                           {
    return r ==  0 || r ==  1 || r ==  2 || r ==  3 || r ==  4 || r ==  6 || r ==  8 || r ==  9 || r == 11 || r == 12 ||
           r == 16 || r == 18 || r == 22 || r == 24 || r == 25 || r == 27 || r == 31 || r == 32 || r == 33 || r == 35 ||
           r == 36 || r == 43 || r == 44 || r == 47 || r == 48 || r == 49 || r == 50 || r == 53 || r == 54 || r == 61 ||
           r == 62 || r == 64 || r == 65 || r == 66 || r == 70 || r == 72 || r == 73 || r == 75 || r == 79 || r == 81 ||
           r == 85 || r == 86 || r == 88 || r == 89 || r == 91 || r == 93 || r == 94 || r == 95 || r == 96;
}

被这些函数引用 lmmp_perfsqr_filter_() , 以及 lmmp_perfsqr_filter_1_().

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

lmmp_mod_2p48sub1_()

mp_limb_t lmmp_mod_2p48sub1_	(	mp_srcptr	p,
		mp_size_t	n
	)

计算 [p,n] % 2^48-1

参数

p	被除数指针
n	被除数的 limb 长度

警告

p!=NULL, n>0

返回

[numa,na] % 2^48-1

在文件 perfsqr.c 第 50 行定义.

                                                       {
    lmmp_param_assert(n > 0 && p != NULL);
 
    mp_limb_t c0 = 0, c1 = 0, c2 = 0;
    mp_limb_t a0 = 0, a1 = 0, a2 = 0;
 
    while (n >= 3) {
        ADD(c0, a0, p[0]);
        ADD(c1, a1, p[1]);
        ADD(c2, a2, p[2]);
        p += 3;
        n -= 3;
    }
    if (n == 2) {
        ADD(c0, a0, p[0]);
        ADD(c1, a1, p[1]);
    } else if (n == 1) {
        ADD(c0, a0, p[0]);
    }
 
    mp_limb_t res = PARTS0(a0) + PARTS1(a1) + PARTS2(a2) 
                  + PARTS1(c0) + PARTS2(c1) + PARTS0(c2);
 
    res = (res & MASK48) + (res >> B3);
    if (res >= MASK48)
        res -= MASK48;
    return res;
}

引用了 a0, a1, a2, ADD, B3, c0, c1, lmmp_param_assert, MASK48, n, PARTS0, PARTS1 , 以及 PARTS2.

被这些函数引用 lmmp_perfsqr_filter_().

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

lmmp_perfsqr_filter_()

bool lmmp_perfsqr_filter_	(	mp_srcptr	p,
		mp_size_t	n
	)

非完全平方数过滤器

参数

p	输入指针
n	输入的 limb 长度

警告

p!=NULL, n>0

返回

false 意味着必定为非完全平方数，所有完全平方数和部分非完全平方数会返回 true

注解

此过滤器主要针对随机输入情况，对于大概率是完全平方数的输入，可以无需此函数。

在文件 perfsqr.c 第 181 行定义.

                                                    {
    lmmp_param_assert(n > 0 && p != NULL);
    mp_limb_t a = p[0] % 256;
    if (!is_perfsqr_p256(a))
        return false;
    mp_limb_t r = lmmp_mod_2p48sub1_(p, n);
    return is_perfsqr_p9(r % 9) && is_perfsqr_p5(r % 5) && is_perfsqr_p7(r % 7) && is_perfsqr_p13(r % 13) &&
           is_perfsqr_p17(r % 17) && is_perfsqr_p97(r % 97) && is_perfsqr_p241(r % 241) &&
           is_perfsqr_p257(r % 257) && is_perfsqr_p673(r % 673);
}

引用了 is_perfsqr_p13(), is_perfsqr_p17(), is_perfsqr_p241(), is_perfsqr_p256(), is_perfsqr_p257(), is_perfsqr_p5(), is_perfsqr_p673(), is_perfsqr_p7(), is_perfsqr_p9(), is_perfsqr_p97(), lmmp_mod_2p48sub1_(), lmmp_param_assert , 以及 n.

函数调用图:

lmmp_perfsqr_filter_1_()

bool lmmp_perfsqr_filter_1_

(

mp_limb_t

p

)

非完全平方数过滤器

参数

p

输入数

返回

false 意味着必定为非完全平方数，所有完全平方数和部分非完全平方数会返回 true

注解

此过滤器主要针对随机输入情况，对于大概率是完全平方数的输入，可以无需此函数。

在文件 perfsqr.c 第 172 行定义.

                                         {
    mp_limb_t a = p % 256;
    if (!is_perfsqr_p256(a)) return false;
    p = p % MASK48;
    return is_perfsqr_p9(p % 9) && is_perfsqr_p5(p % 5) && is_perfsqr_p7(p % 7) && is_perfsqr_p13(p % 13) &&
           is_perfsqr_p17(p % 17) && is_perfsqr_p97(p % 97) && is_perfsqr_p241(p % 241) &&
           is_perfsqr_p257(p % 257) && is_perfsqr_p673(p % 673);
}

引用了 is_perfsqr_p13(), is_perfsqr_p17(), is_perfsqr_p241(), is_perfsqr_p256(), is_perfsqr_p257(), is_perfsqr_p5(), is_perfsqr_p673(), is_perfsqr_p7(), is_perfsqr_p9(), is_perfsqr_p97(), MASK48 , 以及 n.

函数调用图: