LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
test_threshold_boundaries.c 文件参考
#include "mparam.h"
#include "lmmp/lmmpn.h"
#include "lmmp/numth.h"
#include "cases.h"
#include "support/lmmp_test_utils.h"
#include <string.h>
test_threshold_boundaries.c 的引用(Include)关系图:

浏览该文件的源代码.

函数

static void check_mul_n (mp_size_t n, u64 seed)
static void fill_deterministic (mp_ptr p, mp_size_t n, u64 seed)
static u64 modpow32 (u64 base, u64 exp, u32 p)
 Copyright (C) 2026 HJimmyK (Jericho Knox)
 TEST_CASE ("threshold/div", divide_threshold_boundary)
 TEST_CASE ("threshold/divexact", divexact_two_threshold_boundaries)
 TEST_CASE ("threshold/mul", mul_n_toom_boundaries)
 TEST_CASE ("threshold/mullo", mullo_dc_boundary)
 TEST_CASE ("threshold/pow", pow_1_exp_boundary)
void test_threshold_boundaries (void)

函数说明

◆ check_mul_n()

void check_mul_n ( mp_size_t n,
u64 seed )
static

在文件 test_threshold_boundaries.c 第 62 行定义.

62 {
63 mp_ptr a = alloc_limbs(n), b = alloc_limbs(n), d = alloc_limbs(2 * n + 2),
64 ref = alloc_limbs(2 * n + 2);
65 fill_deterministic(a, n, seed);
66 fill_deterministic(b, n, seed ^ 0x9e3779b97f4a7c15ull);
67
68 lmmp_mul_n_(d, a, b, n);
69 lmmp_mul_basecase_(ref, a, n, b, n);
70 bool ok = memcmp(d, ref, (size_t)(2 * n) * 8) == 0;
71 ok = ok && mod_is_product(d, 2 * n, a, n, b, n);
72 TEST_CHECK_MSG(ok, "mul_n at threshold boundary");
73 lmmp_free(a);
74 lmmp_free(b);
75 lmmp_free(d);
76 lmmp_free(ref);
77}
#define lmmp_mul_n_
mp_limb_t * mp_ptr
定义 lmmp.h:96
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
void lmmp_mul_basecase_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
基础乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
#define n
#define TEST_CHECK_MSG(cond, msg)
定义 test.h:38
static void fill_deterministic(mp_ptr p, mp_size_t n, u64 seed)

引用了 check_mul_n(), fill_deterministic(), lmmp_free(), lmmp_mul_basecase_(), lmmp_mul_n_, n , 以及 TEST_CHECK_MSG.

被这些函数引用 check_mul_n() , 以及 TEST_CASE().

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

◆ fill_deterministic()

void fill_deterministic ( mp_ptr p,
mp_size_t n,
u64 seed )
static

在文件 test_threshold_boundaries.c 第 56 行定义.

56 {
57 for (mp_size_t i = 0; i < n; ++i) p[i] = xorshift64(&seed);
58 if (n > 0) p[n - 1] |= (u64)1 << 63;
59}
uint64_t mp_size_t
定义 lmmp.h:93
mp_limb_t u64
Copyright (C) 2026 HJimmyK (Jericho Knox)

引用了 fill_deterministic() , 以及 n.

被这些函数引用 check_mul_n(), fill_deterministic(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().

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

◆ modpow32()

u64 modpow32 ( u64 base,
u64 exp,
u32 p )
static

Copyright (C) 2026 HJimmyK (Jericho Knox)

This file is part of LMMP.

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

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.

SPDX-License-Identifier: LGPL-3.0-or-later

在文件 test_threshold_boundaries.c 第 46 行定义.

46 {
47 u64 r = 1 % p, a = base % p;
48 while (exp) {
49 if (exp & 1) r = r * a % p;
50 a = a * a % p;
51 exp >>= 1;
52 }
53 return r;
54}

引用了 modpow32().

被这些函数引用 check_pow1_agree(), modpow32(), modpow32(), TEST_CASE() , 以及 TEST_CASE().

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

◆ TEST_CASE() [1/5]

TEST_CASE ( "threshold/div" ,
divide_threshold_boundary  )

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

116 {
119 u64 seed = 0x0123456789abcdefull;
120 for (size_t n_index = 0; n_index < ARRAY_SIZE(ns); ++n_index) {
121 mp_size_t n = ns[n_index];
122 const mp_size_t na = 2 * n;
123 mp_ptr num = alloc_limbs(na), den = alloc_limbs(n), q = alloc_limbs(n + 2),
124 r = alloc_limbs(n + 2), t = alloc_limbs(2 * n + 4), qd = alloc_limbs(na + 2),
125 sum = alloc_limbs(2 * n + 4);
126 fill_deterministic(num, na, seed);
127 fill_deterministic(den, n, seed ^ 0xfedcba9876543210ull);
128 num[na - 1] &= ~((u64)1 << 63); /* 保证 q 不超过 n+1 limbs */
129
130 lmmp_div_(q, r, num, na, den, n);
131 // q*d + r == num(库乘重建 + 零垫对齐加)
132 lmmp_mul_(qd, q, n + 1, den, n);
133 lmmp_zero(sum, 2 * n + 4);
134 memcpy(sum, qd, (size_t)(2 * n + 1) * 8);
135 lmmp_zero(t, 2 * n + 4);
136 memcpy(t, r, (size_t)n * 8);
137 lmmp_add_n_(sum, sum, t, 2 * n + 4);
138 TEST_CHECK_MSG(mpn_eq(sum, 2 * n + 4, num, na), "div q*d+r rebuild at boundary");
139 // 余数界:r < den
140 TEST_CHECK_MSG(mpn_cmp(r, n, den, n) < 0, "div rem < den at boundary");
141
142 lmmp_free(num);
143 lmmp_free(den);
144 lmmp_free(q);
145 lmmp_free(r);
146 lmmp_free(t);
147 lmmp_free(qd);
148 lmmp_free(sum);
149 }
150}
#define lmmp_zero(dst, n)
定义 lmmp.h:476
#define DIV_DIVIDE_THRESHOLD
Copyright (C) 2026 HJimmyK (Jericho Knox)
void lmmp_mul_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
不等长乘法操作 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_div_(mp_ptr dstq, mp_ptr dstr, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
除法和取模操作
定义 div.c:85
mp_limb_t lmmp_add_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
无进位的n位加法 [dst,n] = [numa,n] + [numb,n]
定义 add_n.c:76
#define t
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 perf.h:40

引用了 ARRAY_SIZE, DIV_DIVIDE_THRESHOLD, fill_deterministic(), lmmp_add_n_(), lmmp_div_(), lmmp_free(), lmmp_mul_(), lmmp_zero, n, t, TEST_CASE , 以及 TEST_CHECK_MSG.

函数调用图:

◆ TEST_CASE() [2/5]

TEST_CASE ( "threshold/divexact" ,
divexact_two_threshold_boundaries  )

在文件 test_threshold_boundaries.c 第 152 行定义.

152 {
153 u64 seed = 0x0fedcba987654321ull;
154 typedef struct {
155 mp_size_t nn, dn;
156 } Case;
157 const Case cases[] = {
164 };
165 for (size_t c_index = 0; c_index < ARRAY_SIZE(cases); ++c_index) {
166 const Case c = cases[c_index];
167 const mp_size_t qn = c.nn - c.dn;
168 mp_ptr q0 = alloc_limbs(qn), dp = alloc_limbs(c.dn), np = alloc_limbs(c.nn + 2),
169 dst = alloc_limbs(c.nn + 2);
170 fill_deterministic(q0, qn, seed);
171 fill_deterministic(dp, c.dn, seed ^ 0xa5a5a5a55a5a5a5aull);
172 dp[0] |= 1u;
173 dp[c.dn - 1] |= (u64)1 << 63;
174
175 if (qn >= c.dn)
176 lmmp_mul_(np, q0, qn, dp, c.dn);
177 else
178 lmmp_mul_(np, dp, c.dn, q0, qn);
179 np[c.nn] = 0;
180
181 lmmp_divexact_(dst, np, c.nn, dp, c.dn);
182 TEST_CHECK_MSG(mpn_eq(dst, qn, q0, qn),
183 "divexact boundary recovers original quotient");
184
185 lmmp_free(q0);
186 lmmp_free(dp);
187 lmmp_free(np);
188 lmmp_free(dst);
189 }
190}
#define DIVEXACT_NN_THRESHOLD
#define DIVEXACT_BASECASE_THRESHOLD
void lmmp_divexact_(mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn)
精确除法([dst,nn]=[np,nn]/[dp,dn],且余数必须为0)

引用了 ARRAY_SIZE, DIVEXACT_BASECASE_THRESHOLD, DIVEXACT_NN_THRESHOLD, fill_deterministic(), lmmp_divexact_(), lmmp_free(), lmmp_mul_(), TEST_CASE , 以及 TEST_CHECK_MSG.

函数调用图:

◆ TEST_CASE() [3/5]

TEST_CASE ( "threshold/mul" ,
mul_n_toom_boundaries  )

在文件 test_threshold_boundaries.c 第 79 行定义.

79 {
80 check_mul_n(MUL_TOOM22_THRESHOLD > 1 ? MUL_TOOM22_THRESHOLD - 1 : 1, 0x1111222233334444ull);
81 check_mul_n(MUL_TOOM22_THRESHOLD, 0x2222333344445555ull);
82 check_mul_n(MUL_TOOM22_THRESHOLD + 1, 0x3333444455556666ull);
83
84 check_mul_n(MUL_TOOM33_THRESHOLD > 1 ? MUL_TOOM33_THRESHOLD - 1 : 1, 0x4444555566667777ull);
85 check_mul_n(MUL_TOOM33_THRESHOLD, 0x5555666677778888ull);
86 check_mul_n(MUL_TOOM33_THRESHOLD + 1, 0x6666777788889999ull);
87
88 check_mul_n(MUL_TOOM44_THRESHOLD > 1 ? MUL_TOOM44_THRESHOLD - 1 : 1, 0x777788889999aaabull);
89 check_mul_n(MUL_TOOM44_THRESHOLD, 0x88889999aaaabbbbull);
90 check_mul_n(MUL_TOOM44_THRESHOLD + 1, 0x9999aaaabbbbccccull);
91}
#define MUL_TOOM22_THRESHOLD
#define MUL_TOOM33_THRESHOLD
#define MUL_TOOM44_THRESHOLD
static void check_mul_n(mp_size_t n, u64 seed)

引用了 check_mul_n(), MUL_TOOM22_THRESHOLD, MUL_TOOM33_THRESHOLD, MUL_TOOM44_THRESHOLD , 以及 TEST_CASE.

函数调用图:

◆ TEST_CASE() [4/5]

TEST_CASE ( "threshold/mullo" ,
mullo_dc_boundary  )

在文件 test_threshold_boundaries.c 第 93 行定义.

93 {
96 u64 seed = 0xabcddcba12344321ull;
97 for (size_t n_index = 0; n_index < ARRAY_SIZE(sizes); ++n_index) {
98 mp_size_t n = sizes[n_index];
99 mp_ptr a = alloc_limbs(n), b = alloc_limbs(n), lo = alloc_limbs(n),
100 full = alloc_limbs(2 * n + 2);
101 fill_deterministic(a, n, seed);
102 fill_deterministic(b, n, seed ^ 0x13579bdf2468ace0ull);
103
104 lmmp_mul_(full, a, n, b, n);
105 lmmp_mullo_(lo, a, b, n);
106 TEST_CHECK_MSG(memcmp(lo, full, (size_t)n * sizeof(mp_limb_t)) == 0,
107 "mullo low limbs match full product at threshold");
108
109 lmmp_free(a);
110 lmmp_free(b);
111 lmmp_free(lo);
112 lmmp_free(full);
113 }
114}
uint64_t mp_limb_t
定义 lmmp.h:92
#define MULLO_DC_THRESHOLD
void lmmp_mullo_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
低位乘法 [dst,n] = [numa,n] * [numb,n] mod B^n
#define lo

引用了 ARRAY_SIZE, fill_deterministic(), lmmp_free(), lmmp_mul_(), lmmp_mullo_(), lo, MULLO_DC_THRESHOLD, n, TEST_CASE , 以及 TEST_CHECK_MSG.

函数调用图:

◆ TEST_CASE() [5/5]

TEST_CASE ( "threshold/pow" ,
pow_1_exp_boundary  )

在文件 test_threshold_boundaries.c 第 192 行定义.

192 {
193 const mp_limb_t base = 3;
194 mp_ptr b = alloc_limbs(1);
195 b[0] = base;
196 const ulong exps[] = {POW_1_EXP_THRESHOLD > 1 ? (ulong)POW_1_EXP_THRESHOLD - 1 : 1,
198 (ulong)POW_1_EXP_THRESHOLD + 1, 1ul};
199 for (size_t e_index = 0; e_index < ARRAY_SIZE(exps); ++e_index) {
200 ulong e = exps[e_index];
201 const mp_size_t rn = lmmp_pow_size_(b, 1, e);
202 mp_ptr dst = alloc_limbs(rn + 2), dst1 = alloc_limbs(rn + 2);
203 // 多 limb 入口(单 limb 底)与 pow_1_ 精确一致
204 const mp_size_t got = lmmp_pow_(dst, rn, b, 1, e);
205 const mp_size_t got1 = lmmp_pow_1_(dst1, rn, base, e);
206 TEST_CHECK_MSG(got == got1 && memcmp(dst, dst1, (size_t)got * 8) == 0,
207 "pow_ vs pow_1_ at exp boundary");
208 // 模幂参考(32 位素数)
209 bool ok = true;
210 for (int i = 0; i < MOD_P_CNT && ok; ++i)
211 ok = mod32(dst, got, MOD_P[i]) == modpow32(base, e, MOD_P[i]);
212 TEST_CHECK_MSG(ok, "pow boundary modpow check");
213 lmmp_free(dst);
214 lmmp_free(dst1);
215 }
216 lmmp_free(b);
217}
#define POW_1_EXP_THRESHOLD
mp_size_t lmmp_pow_1_(mp_ptr dst, mp_size_t rn, mp_limb_t base, ulong exp)
计算幂次方 [dst,rn] = [base,1] ^ exp
mp_size_t lmmp_pow_(mp_ptr dst, mp_size_t rn, mp_srcptr base, mp_size_t n, ulong exp)
计算大整数幂 [dst,rn] = [base,n] ^ exp
uint64_t ulong
定义 numth.h:39
mp_size_t lmmp_pow_size_(mp_srcptr base, mp_size_t n, ulong exp)
计算幂次方需要的limb缓冲区长度 [base,n] ^ exp
定义 pow.c:103
static u64 modpow32(u64 base, u64 exp, u32 p)
Copyright (C) 2026 HJimmyK (Jericho Knox)

引用了 ARRAY_SIZE, lmmp_free(), lmmp_pow_(), lmmp_pow_1_(), lmmp_pow_size_(), modpow32(), POW_1_EXP_THRESHOLD, TEST_CASE , 以及 TEST_CHECK_MSG.

函数调用图:

◆ test_threshold_boundaries()

void test_threshold_boundaries ( void )

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

219 {
220 TEST_RUN("threshold/mul", mul_n_toom_boundaries);
221 TEST_RUN("threshold/mullo", mullo_dc_boundary);
222 TEST_RUN("threshold/div", divide_threshold_boundary);
223 TEST_RUN("threshold/divexact", divexact_two_threshold_boundaries);
224 TEST_RUN("threshold/pow", pow_1_exp_boundary);
225}
#define TEST_RUN(category, name)
定义 test.h:36

引用了 TEST_RUN , 以及 test_threshold_boundaries().

被这些函数引用 main() , 以及 test_threshold_boundaries().

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