LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
lmmp_test_utils.h
浏览该文件的文档.
1/**
2 * Copyright (C) 2026 HJimmyK (Jericho Knox)
3 *
4 * This file is part of LMMP.
5 *
6 * LMMP is free software: you can redistribute it and/or modify it
7 * under the terms of the GNU Lesser General Public License as
8 * published by the Free Software Foundation; either version 3 of
9 * the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library. If not, see
18 * <https://www.gnu.org/licenses/>.
19 *
20 * SPDX-License-Identifier: LGPL-3.0-or-later
21 */
22
23#ifndef LMMP_TEST_UTILS_H
24#define LMMP_TEST_UTILS_H
25
26#include <stdbool.h>
27#include <string.h>
28
29#include "lmmp/lmmp.h"
30#include "lmmp/lmmpn.h"
31#include "lmmp/numth.h"
32
33typedef mp_limb_t u64;
34typedef uint u32;
35
36// 简单确定性 xorshift64 随机源,避免测试输入与库 RNG 互相影响。
37static inline u64 xorshift64(u64 *s) {
38 *s ^= *s << 13;
39 *s ^= *s >> 7;
40 *s ^= *s << 17;
41 return *s;
42}
43
44static inline mp_ptr alloc_limbs(size_t n) { return (mp_ptr)lmmp_alloc(n * sizeof(mp_limb_t)); }
45
46// [p,n] = 随机 limbs;top_nonzero 时顶 limb 置最高位(归一化)
47static inline void random_limbs_with_top(mp_ptr p, size_t n, u64 *seed, bool top_nonzero) {
48 for (size_t i = 0; i < n; ++i) p[i] = xorshift64(seed);
49 if (n > 0 && top_nonzero) p[n - 1] |= (u64)1 << 63;
50}
51
52static inline void random_limbs(mp_ptr p, size_t n, u64 *seed) {
53 random_limbs_with_top(p, n, seed, true);
54}
55
56// 有效长度:去除前导零后的数值长度(n==0 或全零返回 0)
57static inline mp_size_t norm_len(const mp_limb_t* p, mp_size_t n) {
58 while (n > 0 && p[n - 1] == 0) --n;
59 return n;
60}
61
62// 手工把小值 v 加到 [p,n] 上(v 任意 u64),返回溢出进位
63static inline u64 add_small_inplace(mp_ptr p, size_t n, u64 v) {
64 size_t i = 0;
65 u64 old = p[0];
66 p[0] += v;
67 u64 carry = (p[0] < old) ? 1 : 0;
68 while (carry && ++i < n) {
69 old = p[i];
70 ++p[i];
71 carry = (p[i] < old) ? 1 : 0;
72 }
73 return (carry && i == n) ? 1 : 0;
74}
75
76// 手工把小值 v 从 [p,n] 减去,返回借位
77static inline u64 sub_small_inplace(mp_ptr p, size_t n, u64 v) {
78 size_t i = 0;
79 u64 old = p[0];
80 p[0] -= v;
81 u64 borrow = (p[0] > old) ? 1 : 0;
82 while (borrow && ++i < n) {
83 old = p[i];
84 --p[i];
85 borrow = (p[i] > old) ? 1 : 0;
86 }
87 return (borrow && i == n) ? 1 : 0;
88}
89
90// [p,n] 右移 1 位,顶位补 top_bit;返回原最低位
91static inline u64 shr1_inplace(mp_ptr p, size_t n, u64 top_bit) {
92 u64 low = p[0] & 1;
93 for (size_t i = 0; i + 1 < n; ++i) p[i] = (p[i] >> 1) | (p[i + 1] << 63);
94 if (n > 0) p[n - 1] = (p[n - 1] >> 1) | (top_bit << 63);
95 return low;
96}
97
98// 数值比较(忽略前导零):a<b 返回 -1,相等 0,a>b 返回 1
99static inline int mpn_cmp(const mp_limb_t* a, mp_size_t an, const mp_limb_t* b, mp_size_t bn) {
100 an = norm_len(a, an);
101 bn = norm_len(b, bn);
102 if (an != bn) return an < bn ? -1 : 1;
103 for (mp_size_t i = an; i-- > 0;)
104 if (a[i] != b[i]) return a[i] < b[i] ? -1 : 1;
105 return 0;
106}
107
108static inline bool mpn_eq(const mp_limb_t* a, mp_size_t an, const mp_limb_t* b, mp_size_t bn) {
109 return mpn_cmp(a, an, b, bn) == 0;
110}
111
112/*
113 模检查:验证 limb 数组在 32 位素数下的模值。素数均 < 2^32,故两个
114 模值的乘积 < 2^64,无需 128 位中间量。被测的大数结果与由输入模值
115 直接计算出的期望模值一致,可捕捉绝大多数字节/进位类错误。
116*/
117static const u32 MOD_P[] = {4294967291u, 4294967279u, 4294967231u, 2147483647u, 1000000007u};
118static const int MOD_P_CNT = (int)(sizeof(MOD_P) / sizeof(MOD_P[0]));
119
120// [p,n] mod m(m 须为奇素数以外亦可用,仅要求 m != 0);库 mod_1 路径
121static inline u64 mod32(const mp_limb_t* p, mp_size_t n, u32 m) { return lmmp_mod_1_(p, n, m); }
122
123static inline u64 mulmod32(u64 a, u64 b, u64 m) { return (a * b) % m; } // a,b < m < 2^32
124static inline u64 addmod32(u64 a, u64 b, u64 m) { return (a + b) % m; } // a,b < m,和 < 2^33
125static inline u64 submod32(u64 a, u64 b, u64 m) { return (a + m - b) % m; }
126
127// 模值相等:[a,an] 与 [b,bn] 在全部内置素数下同余
128static inline bool mod_eq(const mp_limb_t* a, mp_size_t an, const mp_limb_t* b, mp_size_t bn) {
129 an = norm_len(a, an);
130 bn = norm_len(b, bn);
131 for (int i = 0; i < MOD_P_CNT; ++i) {
132 u32 p = MOD_P[i];
133 if (mod32(a, an, p) != mod32(b, bn, p)) return false;
134 }
135 return true;
136}
137
138// 模乘检查:[r,rn] ≡ [a,an]*[b,bn] (mod p) 对全部内置素数成立
139static inline bool mod_is_product(const mp_limb_t* r, mp_size_t rn, const mp_limb_t* a, mp_size_t an,
140 const mp_limb_t* b, mp_size_t bn) {
141 an = norm_len(a, an);
142 bn = norm_len(b, bn);
143 rn = norm_len(r, rn);
144 for (int i = 0; i < MOD_P_CNT; ++i) {
145 u32 p = MOD_P[i];
146 u64 want = mulmod32(mod32(a, an, p), mod32(b, bn, p), p);
147 if (mod32(r, rn, p) != want) return false;
148 }
149 return true;
150}
151
152// 模和检查:[r,rn] ≡ [a,an]+[b,bn] (mod p)
153static inline bool mod_is_sum(const mp_limb_t* r, mp_size_t rn, const mp_limb_t* a, mp_size_t an,
154 const mp_limb_t* b, mp_size_t bn) {
155 an = norm_len(a, an);
156 bn = norm_len(b, bn);
157 rn = norm_len(r, rn);
158 for (int i = 0; i < MOD_P_CNT; ++i) {
159 u32 p = MOD_P[i];
160 u64 want = addmod32(mod32(a, an, p), mod32(b, bn, p), p);
161 if (mod32(r, rn, p) != want) return false;
162 }
163 return true;
164}
165
166// 模差检查:[r,rn] ≡ [a,an]-[b,bn] (mod p)(模意义下无符号差)
167static inline bool mod_is_diff(const mp_limb_t* r, mp_size_t rn, const mp_limb_t* a, mp_size_t an,
168 const mp_limb_t* b, mp_size_t bn) {
169 an = norm_len(a, an);
170 bn = norm_len(b, bn);
171 rn = norm_len(r, rn);
172 for (int i = 0; i < MOD_P_CNT; ++i) {
173 u32 p = MOD_P[i];
174 u64 want = submod32(mod32(a, an, p), mod32(b, bn, p), p);
175 if (mod32(r, rn, p) != want) return false;
176 }
177 return true;
178}
179
180// 整除性判据:[p,pn] mod [d,dn] == 0(恒等式必要条件,库 div_ 求余)
181static inline bool divides_all(const mp_limb_t* d, mp_size_t dn, const mp_limb_t* p, mp_size_t pn) {
182 if (dn == 0) return false;
183 mp_ptr r = (mp_ptr)lmmp_alloc((size_t)dn * sizeof(mp_limb_t));
184 lmmp_div_(NULL, r, p, pn, d, dn);
185 bool ok = norm_len(r, dn) == 0;
186 lmmp_free(r);
187 return ok;
188}
189
190// 零垫对齐加法:sum = a + b(长度取 mx;库 add_n_)
191static inline void pad_add(const mp_limb_t* a, mp_size_t la, const mp_limb_t* b, mp_size_t lb, mp_size_t mx,
192 mp_ptr sum) {
193 lmmp_zero(sum, mx);
194 memcpy(sum, a, (size_t)la * 8);
195 mp_ptr pad = alloc_limbs(mx);
196 lmmp_zero(pad, mx);
197 memcpy(pad, b, (size_t)lb * 8);
198 lmmp_add_n_(sum, sum, pad, mx);
199 lmmp_free(pad);
200}
201
202// mul_ 契约 na>=nb:按长度排序后调用
203static inline void mul_sorted(mp_ptr dst, const mp_limb_t* a, mp_size_t la, const mp_limb_t* b,
204 mp_size_t lb) {
205 if (la >= lb) lmmp_mul_(dst, a, la, b, lb);
206 else lmmp_mul_(dst, b, lb, a, la);
207}
208
209// [e,en] 乘小常数 v 的链参考(库 mul_1_ 原地),返回新长度;越界返回 -1
210static inline mp_size_t chain_mul_small(mp_ptr e, mp_size_t en, u64 v, size_t cap) {
211 u64 hi = lmmp_mul_1_(e, e, en, v);
212 if (hi) {
213 if ((size_t)en + 1 >= cap) return -1;
214 e[en] = hi;
215 return en + 1;
216 }
217 return en;
218}
219
220// 64 位内素数试除参考(标量简单参考允许域)
221static inline bool is_prime_small(u32 n) {
222 if (n < 2) return false;
223 for (u32 d = 2; (u64)d * d <= n; ++d)
224 if (n % d == 0) return false;
225 return true;
226}
227
228// 相邻斐波那契对 (F(k), F(k+1)),F(k+1) 实际长度 >= want_n;返回 F(k+1)
229// 实际长度(fibonacci2_ 返回值)。缓冲上方零垫:F(k) 长度可为返回值或其减一。
230static inline mp_size_t fib_pair(mp_ptr x, mp_ptr y, mp_size_t buf, mp_size_t want_n) {
231 ulong k = 3;
232 for (;; ++k) {
233 mp_size_t need = lmmp_fibonacci_size_(k + 1);
234 // size_ 比实际长度多 2-4 limb:need 超 buf+4 后实际长度也不可能 <= buf
235 if (need > buf + 4) return 0;
236 if (need <= buf) {
237 lmmp_zero(x, buf);
238 lmmp_zero(y, buf);
239 mp_size_t ly = lmmp_fibonacci2_(y, x, need, k); // x=F(k), y=F(k+1)
240 if (ly >= want_n) return ly;
241 }
242 }
243}
244
245#endif // LMMP_TEST_UTILS_H
#define k
#define an
#define bn
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_zero(dst, n)
定义 lmmp.h:476
uint64_t mp_size_t
定义 lmmp.h:93
void * lmmp_alloc(size_t size)
内存分配函数(调用lmmp_heap_alloc_fn)
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
uint64_t mp_limb_t
定义 lmmp.h:92
static bool mpn_eq(const mp_limb_t *a, mp_size_t an, const mp_limb_t *b, mp_size_t bn)
static u64 shr1_inplace(mp_ptr p, size_t n, u64 top_bit)
static bool mod_is_product(const mp_limb_t *r, mp_size_t rn, const mp_limb_t *a, mp_size_t an, const mp_limb_t *b, mp_size_t bn)
static void random_limbs_with_top(mp_ptr p, size_t n, u64 *seed, bool top_nonzero)
static const int MOD_P_CNT
static bool mod_is_sum(const mp_limb_t *r, mp_size_t rn, const mp_limb_t *a, mp_size_t an, const mp_limb_t *b, mp_size_t bn)
static u64 sub_small_inplace(mp_ptr p, size_t n, u64 v)
static u64 mulmod32(u64 a, u64 b, u64 m)
static mp_ptr alloc_limbs(size_t n)
static u64 xorshift64(u64 *s)
static const u32 MOD_P[]
static void mul_sorted(mp_ptr dst, const mp_limb_t *a, mp_size_t la, const mp_limb_t *b, mp_size_t lb)
static bool is_prime_small(u32 n)
static bool mod_eq(const mp_limb_t *a, mp_size_t an, const mp_limb_t *b, mp_size_t bn)
static u64 mod32(const mp_limb_t *p, mp_size_t n, u32 m)
static int mpn_cmp(const mp_limb_t *a, mp_size_t an, const mp_limb_t *b, mp_size_t bn)
static bool mod_is_diff(const mp_limb_t *r, mp_size_t rn, const mp_limb_t *a, mp_size_t an, const mp_limb_t *b, mp_size_t bn)
static void random_limbs(mp_ptr p, size_t n, u64 *seed)
static mp_size_t fib_pair(mp_ptr x, mp_ptr y, mp_size_t buf, mp_size_t want_n)
static void pad_add(const mp_limb_t *a, mp_size_t la, const mp_limb_t *b, mp_size_t lb, mp_size_t mx, mp_ptr sum)
static mp_size_t norm_len(const mp_limb_t *p, mp_size_t n)
static bool divides_all(const mp_limb_t *d, mp_size_t dn, const mp_limb_t *p, mp_size_t pn)
static u64 addmod32(u64 a, u64 b, u64 m)
static u64 add_small_inplace(mp_ptr p, size_t n, u64 v)
mp_limb_t u64
Copyright (C) 2026 HJimmyK (Jericho Knox)
static u64 submod32(u64 a, u64 b, u64 m)
static mp_size_t chain_mul_small(mp_ptr e, mp_size_t en, u64 v, size_t cap)
mp_limb_t lmmp_mod_1_(mp_srcptr numa, mp_size_t na, mp_limb_t x)
单精度数取余
定义 div.c:38
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]
mp_limb_t lmmp_mul_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
乘以单limb操作 [dst,na] = [numa,na] * x
定义 mul_1.c:27
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 s
#define n
mp_size_t lmmp_fibonacci2_(mp_ptr dst, mp_ptr dst2, mp_size_t rn, ulong n)
计算 Fibonacci 数对:[dst,rn] = F[n],[dst2,rn] = F[n-1]
uint32_t uint
定义 numth.h:38
uint64_t ulong
定义 numth.h:39
mp_size_t lmmp_fibonacci_size_(ulong n)
计算 Fibonacci 数 F[n](及 F[n-1])所需的 limb 缓冲区长度