LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
test_low_limb.c
浏览该文件的文档.
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#include "lmmp/lmmpn.h"
24#include "cases.h"
26
27#include <string.h>
28
29const size_t MAX_N = 128;
30
31TEST_CASE("low/limb", endianness) {
32#if defined(__BYTE_ORDER__) && defined(__ORDER_LITTLE_ENDIAN__)
33 bool little = (__BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__);
34#else
35 bool little = true; // 项目硬性要求 64 位平台,当前测试平台均为小端。
36#endif
37 TEST_CHECK_EQ(lmmp_endian(), little);
38}
39
40TEST_CASE("low/limb", limb_bits) {
46 TEST_CHECK_EQ(lmmp_limb_bits_(UINT64_MAX), 64);
47 u64 seed = 0x12345678abcdef;
48 for (int i = 0; i < 200; ++i) {
49 u64 x = xorshift64(&seed);
50 int expect = 0;
51 u64 t = x;
52 while (t) { ++expect; t >>= 1; }
54 }
55}
56
57TEST_CASE("low/limb", popcnt_clz_ctz) {
58 u64 seed = 0x9e3779b97f4a7c15ull;
59 for (int i = 0; i < 300; ++i) {
60 u64 x = xorshift64(&seed);
61 int pc = 0;
62 u64 t = x;
63 while (t) { pc += (int)(t & 1); t >>= 1; }
65
66 int lz = 0;
67 for (int b = 63; b >= 0; --b) {
68 if ((x >> b) & 1) break;
69 ++lz;
70 }
71 if (x == 0) lz = 64;
73
74 int tz = 0;
75 t = x;
76 if (t == 0) tz = 64;
77 else while ((t & 1) == 0) { ++tz; t >>= 1; }
79 }
83}
84
85/*
86 mulh/mullh 无 u128 参考,改用三层验证:
87 1) 写死常数:(2^64-1)^2 = 0xFFFFFFFFFFFFFFFE_0000000000000001 等代数已知值
88 2) 结构恒等式:(2^64-1)*x = x*2^64 - x,故 hi=x-1、lo=-x(x>0);
89 2^63*x = x<<63,故 hi=x>>1、lo=x<<63;x*0=0;x*1=x
90 3) 库内交叉:mullh 的积 hi:lo 用 div_2 除回乘数,须整除且商还原
91*/
92TEST_CASE("low/limb", mulh_mullh) {
93 // 写死常数锚点
94 mp_limb_t dst[2];
95 lmmp_mullh_(0xFFFFFFFFFFFFFFFFull, 0xFFFFFFFFFFFFFFFFull, dst);
96 TEST_CHECK_EQ(dst[0], 0x0000000000000001ull);
97 TEST_CHECK_EQ(dst[1], 0xFFFFFFFFFFFFFFFEull);
98 lmmp_mullh_(0xFFFFFFFFFFFFFFFFull, 2, dst);
99 TEST_CHECK_EQ(dst[0], 0xFFFFFFFFFFFFFFFEull);
100 TEST_CHECK_EQ(dst[1], 1ull);
101 TEST_CHECK_EQ(lmmp_mulh_(0, 0x9e3779b97f4a7c15ull), 0ull);
102 TEST_CHECK_EQ(lmmp_mulh_(1, 0x9e3779b97f4a7c15ull), 0ull);
103
104 u64 seed = 0xdeadbeefcafebabeull;
105 for (int i = 0; i < 300; ++i) {
106 u64 a = xorshift64(&seed);
107 u64 b = xorshift64(&seed);
108
109 // 结构恒等式:(2^64-1)*x
110 lmmp_mullh_(0xFFFFFFFFFFFFFFFFull, b, dst);
111 TEST_CHECK_EQ(dst[0], (u64)(0 - b));
112 TEST_CHECK_EQ(dst[1], b - 1);
113 // 2^63*x
114 lmmp_mullh_(0x8000000000000000ull, b, dst);
115 TEST_CHECK_EQ(dst[0], b << 63);
116 TEST_CHECK_EQ(dst[1], b >> 1);
117 // x*1 与 x*0
118 lmmp_mullh_(a, 1, dst);
119 TEST_CHECK_EQ(dst[0], a);
120 TEST_CHECK_EQ(dst[1], 0ull);
121 lmmp_mullh_(a, 0, dst);
122 TEST_CHECK_EQ(dst[0], 0ull);
123 TEST_CHECK_EQ(dst[1], 0ull);
124
125 // 交叉:hi:lo / b == a 且整除(b==0 跳过;单 limb 除数走 div_1)
126 lmmp_mullh_(a, b, dst);
127 if (b != 0) {
128 TEST_CHECK_EQ(lmmp_mulh_(a, b), dst[1]);
129 mp_limb_t q[2], dv[2];
130 dv[0] = dst[0];
131 dv[1] = dst[1];
132 mp_limb_t rem = lmmp_div_1_(q, dv, 2, b);
133 TEST_CHECK_EQ(q[0], a);
134 TEST_CHECK_EQ(q[1], 0ull);
135 TEST_CHECK_EQ(rem, 0ull);
136 }
137 }
138}
139
140/*
141 add/sub 系列用互逆恒等式:dst = a+b-c*B^n ⟹ dst - b == a(借位==c),
142 dst + b ≡ a(进位==c 的补),以及 add_nc(+1) == add_n 后加 1。
143*/
144TEST_CASE("low/addsub", add_sub_n) {
145 u64 seed = 0x1111111122222222ull;
146 for (size_t n = 1; n <= MAX_N; ++n) {
147 for (int iter = 0; iter < 20; ++iter) {
148 mp_ptr a = alloc_limbs(n), b = alloc_limbs(n), dst = alloc_limbs(n), r = alloc_limbs(n),
149 d2 = alloc_limbs(n);
150 random_limbs(a, n, &seed);
151 random_limbs(b, n, &seed);
152
153 u64 carry = lmmp_add_n_(dst, a, b, n);
154 // 互逆:dst - b == a,借位 == 进位
155 u64 borrow = lmmp_sub_n_(r, dst, b, n);
156 TEST_CHECK_EQ(borrow, carry);
157 TEST_CHECK(mpn_eq(r, n, a, n));
158 // 交换律:b + a 同结果同进位
159 lmmp_add_n_(r, b, a, n);
160 TEST_CHECK_EQ(memcmp(r, dst, n * 8), 0);
161
162 // add_nc(+1) == add_n 结果再 +1(手工 limb 进位传播)
163 u64 c0 = lmmp_add_nc_(d2, a, b, n, 0);
164 TEST_CHECK_EQ(c0, carry);
165 TEST_CHECK_EQ(memcmp(d2, dst, n * 8), 0);
166 u64 c1 = lmmp_add_nc_(d2, a, b, n, 1);
167 memcpy(r, dst, n * 8);
168 int i = 0;
169 while (i < (int)n && ++r[i] == 0) ++i; // r = dst + 1
170 TEST_CHECK_EQ(memcmp(d2, r, n * 8), 0);
171 TEST_CHECK_EQ(c1, (i == (int)n) ? carry + 1 : carry);
172
173 // sub_nc(0) 与 sub_n 一致;sub_nc(1) == sub_n 结果再 -1
174 u64 b0 = lmmp_sub_nc_(d2, a, b, n, 0);
175 u64 bn_ = lmmp_sub_n_(r, a, b, n);
176 TEST_CHECK_EQ(b0, bn_);
177 TEST_CHECK_EQ(memcmp(d2, r, n * 8), 0);
178 u64 b1 = lmmp_sub_nc_(d2, a, b, n, 1);
179 lmmp_sub_n_(r, a, b, n); // r 复用为 sub_n 结果
180 i = 0;
181 while (i < (int)n && r[i]-- == 0) ++i; // r = sub_n 结果 - 1
182 TEST_CHECK_EQ(memcmp(d2, r, n * 8), 0);
183 TEST_CHECK_EQ(b1, (i == (int)n) ? bn_ + 1 : bn_);
184
185 lmmp_free(a); lmmp_free(b); lmmp_free(dst); lmmp_free(r); lmmp_free(d2);
186 }
187 }
188}
189
190/*
191 add_n_sub_n:da = a+b(进位 c),db = a-b(借位 s)。
192 验证 da - b == a(借位 c)与 db + b == a(进位 s)—— 两个互逆关系
193 覆盖双输出的正确性;返回值编码 (c<<1)|s。
194*/
195TEST_CASE("low/addsub", add_n_sub_n) {
196 u64 seed = 0x3333333344444444ull;
197 for (size_t n = 1; n <= MAX_N; ++n) {
198 for (int iter = 0; iter < 20; ++iter) {
199 mp_ptr a = alloc_limbs(n), b = alloc_limbs(n), da = alloc_limbs(n), db = alloc_limbs(n),
200 r = alloc_limbs(n);
201 random_limbs(a, n, &seed);
202 random_limbs(b, n, &seed);
203
204 mp_limb_t cb = lmmp_add_n_sub_n_(da, db, a, b, n);
205
206 u64 carry = lmmp_add_n_(r, a, b, n);
207 TEST_CHECK_EQ(memcmp(da, r, n * 8), 0);
208 u64 borrow = lmmp_sub_n_(r, a, b, n);
209 TEST_CHECK_EQ(memcmp(db, r, n * 8), 0);
210 TEST_CHECK_EQ(cb, (carry ? 2u : 0u) | (borrow ? 1u : 0u));
211
212 // 互逆关系
213 u64 w = lmmp_sub_n_(r, da, b, n);
214 TEST_CHECK_EQ(w, carry);
215 TEST_CHECK(mpn_eq(r, n, a, n));
216 u64 c2 = lmmp_add_n_(r, db, b, n);
217 TEST_CHECK_EQ(c2, borrow);
218 TEST_CHECK(mpn_eq(r, n, a, n));
219
220 lmmp_free(a); lmmp_free(b); lmmp_free(da); lmmp_free(db); lmmp_free(r);
221 }
222 }
223}
224
225/*
226 shl/shr 互逆:V = (a << s) 的 n+1 limb 表示 = [dst(n limbs) | ret]。
227 对 V 做 shr(2, s) 必须还原 a 且返回 0;反向 (a>>s)<<s 补零低位与
228 移出位重组还原 a 的低 s 位。
229*/
230TEST_CASE("low/shift", shl_shr) {
231 u64 seed = 0x5555555566666666ull;
232 for (size_t n = 1; n <= MAX_N; n += 3) {
233 for (int iter = 0; iter < 5; ++iter) {
234 mp_ptr a = alloc_limbs(n), dst = alloc_limbs(n), dst2 = alloc_limbs(n + 1),
235 vbuf = alloc_limbs(n + 1);
236 random_limbs(a, n, &seed);
237
238 for (size_t s = 0; s < 64; ++s) {
239 mp_limb_t ret = lmmp_shl_(dst, a, n, s);
240 // V = dst ++ [ret](ret 是移出高 s 位,s>0 时 < 2^s)
241 memcpy(vbuf, dst, n * 8);
242 vbuf[n] = ret;
243 if (s == 0) {
244 TEST_CHECK_EQ(ret, 0ull);
245 } else {
246 TEST_CHECK(ret < ((u64)1 << s) || ret == 0);
247 TEST_CHECK(ret == (a[n - 1] >> (64 - s))); // 移出位 = a 顶 s 位
248 }
249 mp_limb_t r2 = lmmp_shr_(dst2, vbuf, n + 1, s);
250 TEST_CHECK_EQ(r2, 0ull);
251 TEST_CHECK_EQ(memcmp(dst2, a, n * 8), 0); // (a<<s)>>s == a
252
253 // 反向:shr 后 shl 还原低 s 位
254 mp_limb_t r3 = lmmp_shr_(dst, a, n, s);
255 if (s == 0) {
256 TEST_CHECK_EQ(r3, 0ull);
257 TEST_CHECK_EQ(memcmp(dst, a, n * 8), 0);
258 } else {
259 // 返回值为移出的低 s 位置于最高 s 位
260 u64 expect_ret = (a[0] & (((u64)1 << s) - 1)) << (64 - s);
261 TEST_CHECK_EQ(r3, expect_ret);
262 // (a>>s)<<s == a 且低 s 位清零
263 mp_limb_t r4 = lmmp_shl_(dst2, dst, n, s);
264 TEST_CHECK_EQ(r4, 0ull);
265 u64 lowmask = ((u64)1 << s) - 1;
266 TEST_CHECK_EQ(dst2[0] & lowmask, 0ull);
267 u64 alow = a[0] & lowmask;
268 TEST_CHECK_EQ(dst2[0] | alow, a[0]);
269 TEST_CHECK_EQ(memcmp(dst2 + 1, a + 1, (n - 1) * 8), 0);
270 }
271 }
272
273 lmmp_free(a); lmmp_free(dst); lmmp_free(dst2); lmmp_free(vbuf);
274 }
275 }
276}
277
278/*
279 mul_1/addmul_1/submul_1 与除法互逆重建:
280 mul_1: P = a*x(n+1 limbs: dst ++ [carry]),div_1(P, x) 整除且商 == a
281 addmul_1: 等价于 mul_1 后 add_n 累加(两条路径比对)
282 submul_1: 等价于 sub_n 减去 mul_1 积(借位复合 w1 + hi)
283*/
284TEST_CASE("low/mul1", mul_1_addmul_submul) {
285 u64 seed = 0x7777777788888888ull;
286 for (size_t n = 1; n <= MAX_N; ++n) {
287 for (int iter = 0; iter < 20; ++iter) {
288 mp_ptr a = alloc_limbs(n), dst = alloc_limbs(n + 1), q = alloc_limbs(n + 1),
289 acc = alloc_limbs(n + 1), acc2 = alloc_limbs(n + 1), t = alloc_limbs(n + 2);
290 random_limbs(a, n, &seed);
291 u64 x = xorshift64(&seed) | 1;
292
293 u64 carry = lmmp_mul_1_(dst, a, n, x);
294 dst[n] = carry;
295 {
296 u64 rem = lmmp_div_1_(q, dst, n + 1, x);
297 TEST_CHECK_EQ(rem, 0ull);
298 TEST_CHECK(mpn_eq(q, n + 1, a, n)); // 商恰为 a(顶 limb 0)
299 }
300 // x=1 / x=B-1 锚点
301 lmmp_mul_1_(dst, a, n, 1);
302 TEST_CHECK_EQ(memcmp(dst, a, n * 8), 0);
303 lmmp_mul_1_(dst, a, n, 0);
304 for (size_t i = 0; i < n; ++i) TEST_CHECK_EQ(dst[i], 0ull);
305
306 // addmul_1 交叉路径
307 random_limbs(acc, n, &seed);
308 memcpy(acc2, acc, n * 8);
309 acc2[n] = 0;
310 u64 mcy = lmmp_mul_1_(dst, a, n, x);
311 u64 c1 = lmmp_add_n_(t, acc, dst, n) + mcy; // 进位=加进位+乘进位
312 u64 c2 = lmmp_addmul_1_(acc2, a, n, x);
313 TEST_CHECK_EQ(memcmp(acc2, t, n * 8), 0);
314 TEST_CHECK_EQ(c2, c1);
315
316 // submul_1 交叉路径:borrow = w_sub + hi(a*x)
317 memcpy(acc2, acc, n * 8);
318 acc2[n] = 0;
319 u64 w = lmmp_sub_n_(t, acc, dst, n);
320 u64 c3 = lmmp_submul_1_(acc2, a, n, x);
321 TEST_CHECK_EQ(memcmp(acc2, t, n * 8), 0);
322 TEST_CHECK_EQ(c3, w + carry);
323
324 lmmp_free(a); lmmp_free(dst); lmmp_free(q); lmmp_free(acc); lmmp_free(acc2);
325 lmmp_free(t);
326 }
327 }
328}
329
330/*
331 not/shlnot/addshl1_n/subshl1_n 恒等式:
332 not: 逐 limb 取反(a + not(a) == 全 F)
333 shlnot: == not(shl(a, s)) 的低 n limbs
334 addshl1_n: a + 2b == add_n(a, add_n(b,b)),进位复合 c1+c2
335 subshl1_n: a - 2b == sub_n(a, 2b),借位复合 w1+c1
336*/
337TEST_CASE("low/misc", shlnot_not_addshl1_subshl1) {
338 u64 seed = 0x99999999aaaaaaaaull;
339 for (size_t n = 1; n <= MAX_N; ++n) {
340 for (int iter = 0; iter < 20; ++iter) {
341 mp_ptr a = alloc_limbs(n), b = alloc_limbs(n), dst = alloc_limbs(n + 1),
342 t = alloc_limbs(n + 1), b2 = alloc_limbs(n + 1);
343 random_limbs(a, n, &seed);
344 random_limbs(b, n, &seed);
345
346 lmmp_not_(dst, a, n);
347 for (size_t i = 0; i < n; ++i) TEST_CHECK_EQ(dst[i], ~a[i]);
348 // a + not(a) == 全 F(逐 limb 和为 B-1,无进位传出)
349 u64 c = lmmp_add_n_(t, a, dst, n);
350 TEST_CHECK_EQ(c, 0ull);
351 for (size_t i = 0; i < n; ++i) TEST_CHECK_EQ(t[i], ~(u64)0);
352
353 for (size_t s = 0; s < 64; ++s) {
354 mp_limb_t r1 = lmmp_shl_(t, a, n, s);
355 mp_limb_t r2 = lmmp_shlnot_(dst, a, n, s);
356 lmmp_not_(b2, t, n); // b2 复用:not(shl body)
357 TEST_CHECK_EQ(memcmp(dst, b2, n * 8), 0);
358 TEST_CHECK_EQ(r2, r1); // shlnot 移出位与 shl 一致
359 }
360
361 // addshl1_n == a + 2b 复合路径
362 u64 c1 = lmmp_add_n_(b2, b, b, n); // 2b 低 n limbs,进位 c1
363 u64 c2 = lmmp_add_n_(t, a, b2, n); // a + 2b 低 n limbs,进位 c2
364 u64 cy = lmmp_addshl1_n_(dst, a, b, n);
365 TEST_CHECK_EQ(memcmp(dst, t, n * 8), 0);
366 TEST_CHECK_EQ(cy, c1 + c2);
367
368 // subshl1_n == a - 2b 复合路径
369 u64 w1 = lmmp_sub_n_(t, a, b2, n); // a - 2b 低 n limbs,借位 w1
370 u64 bo = lmmp_subshl1_n_(dst, a, b, n);
371 TEST_CHECK_EQ(memcmp(dst, t, n * 8), 0);
372 TEST_CHECK_EQ(bo, w1 + c1);
373
375 }
376 }
377}
378
379void test_low_limb(void) {
380 TEST_RUN("low/limb", endianness);
381 TEST_RUN("low/limb", limb_bits);
382 TEST_RUN("low/limb", popcnt_clz_ctz);
383 TEST_RUN("low/limb", mulh_mullh);
384 TEST_RUN("low/addsub", add_sub_n);
385 TEST_RUN("low/addsub", add_n_sub_n);
386 TEST_RUN("low/shift", shl_shr);
387 TEST_RUN("low/mul1", mul_1_addmul_submul);
388 TEST_RUN("low/misc", shlnot_not_addshl1_subshl1);
389}
#define lmmp_limb_bits_
#define lmmp_leading_zeros_
#define lmmp_mullh_
#define lmmp_limb_popcnt_
#define lmmp_tailing_zeros_
#define lmmp_mulh_
mp_limb_t * mp_ptr
定义 lmmp.h:96
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
uint64_t mp_limb_t
定义 lmmp.h:92
mp_limb_t u64
Copyright (C) 2026 HJimmyK (Jericho Knox)
void test_low_limb(void)
mp_limb_t lmmp_shlnot_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shl)
左移后按位取反操作 [dst,na] = ~([numa,na] << shl),dst的低shl位填充1
mp_limb_t lmmp_div_1_(mp_ptr dstq, mp_srcptr numa, mp_size_t na, mp_limb_t x)
单精度数除法
定义 div.c:137
mp_limb_t lmmp_subshl1_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
减法结合左移1位操作 [dst,n] = [numa,n] - ([numb,n] << 1)
定义 shl.c:80
mp_limb_t lmmp_shr_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shr)
右移操作 [dst,na] = [numa,na]>>shr,dst的高shr位填充0
定义 shr.c:26
mp_limb_t lmmp_addshl1_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
加法结合左移1位操作 [dst,n] = [numa,n] + ([numb,n] << 1)
定义 shl.c:53
mp_limb_t lmmp_add_nc_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t c)
带进位的n位加法 [dst,n] = [numa,n] + [numb,n] + c
定义 add_n.c:58
mp_limb_t lmmp_shl_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shl)
左移操作 [dst,na] = [numa,na]<<shl,dst的低shl位填充0
定义 shl.c:26
mp_limb_t lmmp_addmul_1_(mp_ptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t b)
乘以单limb并累加操作 [numa,n] += [numb,n] * b
定义 mul_1.c:76
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
mp_limb_t lmmp_add_n_sub_n_(mp_ptr dsta, mp_ptr dstb, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
同时执行n位加法和减法 ([dsta,n],[dstb,n]) = ([numa,n]+[numb,n],[numa,n]-[numb,n])
static bool lmmp_endian(void)
运行时判断端序
定义 lmmpn.h:40
void lmmp_not_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
按位取反操作 [dst,na] = ~[numa,na] (对每个limb执行按位非操作)
定义 not.c:26
mp_limb_t lmmp_submul_1_(mp_ptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t b)
乘以单limb并累减操作 [numa,n] -= [numb,n] * b
mp_limb_t lmmp_sub_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
无借位的n位减法 [dst,n] = [numa,n] - [numb,n]
定义 sub_n.c:84
mp_limb_t lmmp_sub_nc_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t c)
带借位的n位减法 [dst,n] = [numa,n] - [numb,n] - c
定义 sub_n.c:67
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 b0
#define b1
#define r2
#define r1
#define r3
#define b2
#define t
#define s
#define n
#define r4
#define c1
#define c0
#define TEST_CHECK(cond)
定义 test.h:37
#define TEST_CASE(category, name)
定义 test.h:35
#define TEST_CHECK_EQ(a, b)
定义 test.h:39
#define TEST_RUN(category, name)
定义 test.h:36
const size_t MAX_N
Copyright (C) 2026 HJimmyK (Jericho Knox)