LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
test_memory_layout.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
29/*
30 内存布局(原地/错位重叠)专项:算术正确性由 low/asm 系列覆盖,
31 这里以「分离缓冲的同函数调用」为期望,验证重叠布局不破坏结果、
32 不越界写。
33*/
34
35TEST_CASE("memory/addsub", add_n_sub_n_inplace_pair) {
36 const mp_size_t n = 5;
37 const u64 av[5] = {UINT64_MAX - 2, 1, 0, UINT64_MAX, 7};
38 const u64 bv[5] = {3, UINT64_MAX, UINT64_MAX - 1, 0, 1};
39
40 /* 输出缓冲多配 1 limb 置哨兵:越界写可见 */
41 mp_ptr a = alloc_limbs(n + 1), b = alloc_limbs(n + 1), sa = alloc_limbs(n), sb = alloc_limbs(n),
42 ref_sum = alloc_limbs(n), ref_diff = alloc_limbs(n);
43 const mp_limb_t sent = UINT64_C(0x5a5af00dcafebeef);
44 a[n] = sent; b[n] = sent;
45 for (mp_size_t i = 0; i < n; ++i) {
46 a[i] = av[i]; b[i] = bv[i]; sa[i] = av[i]; sb[i] = bv[i];
47 }
48 u64 carry = lmmp_add_n_(ref_sum, sa, sb, n);
49 u64 borrow = lmmp_sub_n_(ref_diff, sa, sb, n);
50
51 /* dsta == numa 且 dstb == numb,同时原地写回两个输入。 */
52 const mp_limb_t cb = lmmp_add_n_sub_n_(a, b, a, b, n);
53 TEST_CHECK_EQ(cb, (carry ? 2u : 0u) | (borrow ? 1u : 0u));
54 TEST_CHECK_EQ(memcmp(a, ref_sum, n * 8), 0);
55 TEST_CHECK_EQ(memcmp(b, ref_diff, n * 8), 0);
56 TEST_CHECK_EQ(a[n], sent);
57 TEST_CHECK_EQ(b[n], sent);
58
59 /* 交换两个输出位置:dsta == numb、dstb == numa。 */
60 for (mp_size_t i = 0; i < n; ++i) { a[i] = av[i]; b[i] = bv[i]; }
61 const mp_limb_t cb2 = lmmp_add_n_sub_n_(b, a, a, b, n);
62 TEST_CHECK_EQ(cb2, cb);
63 TEST_CHECK_EQ(memcmp(b, ref_sum, n * 8), 0);
64 TEST_CHECK_EQ(memcmp(a, ref_diff, n * 8), 0);
65 TEST_CHECK_EQ(a[n], sent);
66 TEST_CHECK_EQ(b[n], sent);
67
68 lmmp_free(a); lmmp_free(b); lmmp_free(sa); lmmp_free(sb);
69 lmmp_free(ref_sum); lmmp_free(ref_diff);
70}
71
72TEST_CASE("memory/addsub", addshl1_subshl1_inplace) {
73 const mp_size_t n = 4;
74 const u64 av[4] = {1, 0, UINT64_MAX - 1, 5};
75 const u64 bv[4] = {UINT64_MAX, 1, 0, 0};
76
77 /* 输出缓冲多配 1 limb 置哨兵:越界写可见 */
78 mp_ptr a = alloc_limbs(n + 1), b = alloc_limbs(n + 1), sa = alloc_limbs(n), sb = alloc_limbs(n),
79 ref = alloc_limbs(n + 1);
80 const mp_limb_t sent = UINT64_C(0x5a5af00dcafebeef);
81 a[n] = sent; b[n] = sent;
82 for (mp_size_t i = 0; i < n; ++i) {
83 a[i] = av[i]; b[i] = bv[i]; sa[i] = av[i]; sb[i] = bv[i];
84 }
85
86 /* dst == numa(原地)。 */
87 u64 cy_ref = lmmp_addshl1_n_(ref, sa, sb, n);
88 const mp_limb_t cy = lmmp_addshl1_n_(a, a, b, n);
89 TEST_CHECK_EQ(cy, cy_ref);
90 TEST_CHECK_EQ(memcmp(a, ref, n * 8), 0);
91 TEST_CHECK_EQ(a[n], sent);
92
93 /* subshl1:a = [0,0,0,2] >= b<<1,dst == numb。 */
94 const u64 bigv[4] = {0, 0, 0, 2};
95 for (mp_size_t i = 0; i < n; ++i) { a[i] = bigv[i]; sa[i] = bigv[i]; sb[i] = bv[i]; }
96 u64 bw_ref = lmmp_subshl1_n_(ref, sa, sb, n);
97 const mp_limb_t bw = lmmp_subshl1_n_(b, a, b, n);
98 TEST_CHECK_EQ(bw, bw_ref);
99 TEST_CHECK_EQ(memcmp(b, ref, n * 8), 0);
100 TEST_CHECK_EQ(a[n], sent);
101 TEST_CHECK_EQ(b[n], sent);
102
103 lmmp_free(a); lmmp_free(b); lmmp_free(sa); lmmp_free(sb); lmmp_free(ref);
104}
105
106TEST_CASE("memory/shift", shr1add_shr1sub_inplace) {
107 const mp_size_t n = 6;
108 const u64 av[6] = {0, UINT64_MAX, 1, UINT64_MAX - 1, 0, 3};
109 const u64 bv[6] = {1, 1, UINT64_MAX, 0, UINT64_MAX, 0};
110
111 mp_ptr a = alloc_limbs(n), b = alloc_limbs(n), sa = alloc_limbs(n), sb = alloc_limbs(n),
112 ref = alloc_limbs(n);
113 for (mp_size_t i = 0; i < n; ++i) {
114 a[i] = av[i]; b[i] = bv[i]; sa[i] = av[i]; sb[i] = bv[i];
115 }
116
117 /* dst == numa。 */
118 u64 l_ref = lmmp_shr1add_n_(ref, sa, sb, n);
119 const mp_limb_t lsb = lmmp_shr1add_n_(a, a, b, n);
120 TEST_CHECK_EQ(lsb, l_ref);
121 TEST_CHECK_EQ(memcmp(a, ref, n * 8), 0);
122
123 /* dst == numb。 */
124 for (mp_size_t i = 0; i < n; ++i) { a[i] = av[i]; b[i] = bv[i]; }
125 l_ref = lmmp_shr1add_n_(ref, sa, sb, n);
126 const mp_limb_t lsb3 = lmmp_shr1add_n_(b, a, b, n);
127 TEST_CHECK_EQ(lsb3, l_ref);
128 TEST_CHECK_EQ(memcmp(b, ref, n * 8), 0);
129
130 /* shr1sub:a >= b 时 dst 原地覆盖 a 或 b(先恢复 a/b——上一段
131 dst==numb 的 shr1add 已改写 b)。 */
132 for (mp_size_t i = 0; i < n; ++i) { a[i] = av[i]; b[i] = bv[i]; }
133 if (mpn_cmp(sa, n, sb, n) >= 0) {
134 l_ref = lmmp_shr1sub_n_(ref, sa, sb, n);
135 const mp_limb_t lsb_s = lmmp_shr1sub_n_(a, a, b, n);
136 TEST_CHECK_EQ(lsb_s, l_ref);
137 TEST_CHECK_EQ(memcmp(a, ref, n * 8), 0);
138
139 for (mp_size_t i = 0; i < n; ++i) { a[i] = av[i]; b[i] = bv[i]; }
140 const mp_limb_t lsb_s2 = lmmp_shr1sub_n_(b, a, b, n);
141 TEST_CHECK_EQ(lsb_s2, l_ref);
142 TEST_CHECK_EQ(memcmp(b, ref, n * 8), 0);
143 }
144
145 lmmp_free(a); lmmp_free(b); lmmp_free(sa); lmmp_free(sb); lmmp_free(ref);
146}
147
148TEST_CASE("memory/mul1", mul_1_shifted_overlap) {
149 const mp_size_t n = 5;
150 const u64 av[5] = {0, 1, UINT64_MAX, 0x8000000000000001ull, 0};
151 const u64 x = UINT64_C(0x9e3779b97f4a7c15);
152
153 mp_ptr a = alloc_limbs(n), buf = alloc_limbs(n + 2), ref = alloc_limbs(n + 1);
154 for (mp_size_t i = 0; i < n; ++i) a[i] = av[i];
155
156 /* dst == numa;期望取分离调用。 */
157 memcpy(buf, a, n * sizeof(mp_limb_t));
158 u64 c_ref = lmmp_mul_1_(ref, a, n, x);
159 const mp_limb_t c0 = lmmp_mul_1_(buf, buf, n, x);
160 TEST_CHECK_EQ(c0, c_ref);
161 TEST_CHECK_EQ(memcmp(buf, ref, n * 8), 0);
162
163 /* 极端 n==1:写死常数 (2^64-1)^2 = 2^128 - 2^65 + 1。 */
164 buf[0] = UINT64_MAX;
165 buf[1] = 0;
166 buf[2] = 0;
167 const mp_limb_t c2 = lmmp_mul_1_(buf + 1, buf, 1, UINT64_MAX);
168 TEST_CHECK_EQ(buf[1], 1u); /* 低 limb */
169 TEST_CHECK_EQ(c2, UINT64_MAX - 1); /* 高 limb */
170 TEST_CHECK_EQ(buf[2], 0u);
171
172 lmmp_free(a);
173 lmmp_free(buf);
174 lmmp_free(ref);
175}
176
177TEST_CASE("memory/div1", div_1_shifted_overlap) {
178 const mp_size_t n = 5;
179 const u64 av[5] = {0, 0, UINT64_MAX, 1, 0x7fffffffffffffffull};
180 const u64 x = UINT64_C(0x100000001b3);
181
182 mp_ptr a = alloc_limbs(n), buf = alloc_limbs(n + 1), refq = alloc_limbs(n + 1),
183 t = alloc_limbs(n + 1);
184 for (mp_size_t i = 0; i < n; ++i) a[i] = av[i];
185
186 /* 分离参考(另加重建恒等式 q*x + r == a)。 */
187 u64 r_ref = lmmp_div_1_(refq, a, n, x);
188 u64 hi = lmmp_mul_1_(t, refq, n, x);
189 t[n] = hi;
190 add_small_inplace(t, n + 1, r_ref);
191 TEST_CHECK(mpn_eq(t, n + 1, a, n));
192
193 /* dstq == numa。 */
194 memcpy(buf + 1, a, n * sizeof(mp_limb_t));
195 const mp_limb_t r0 = lmmp_div_1_(buf + 1, buf + 1, n, x);
196 TEST_CHECK_EQ(r0, r_ref);
197 TEST_CHECK_EQ(memcmp(buf + 1, refq, n * 8), 0);
198
199 /* dstq == numa - 1,即库允许的左移一格重叠布局。 */
200 memcpy(buf + 1, a, n * sizeof(mp_limb_t));
201 const mp_limb_t r1 = lmmp_div_1_(buf, buf + 1, n, x);
202 TEST_CHECK_EQ(r1, r_ref);
203 TEST_CHECK_EQ(memcmp(buf, refq, n * 8), 0);
204
205 lmmp_free(a);
206 lmmp_free(buf);
207 lmmp_free(refq);
208 lmmp_free(t);
209}
210
211TEST_CASE("memory/muladd", addmul_submul_equal_sources) {
212 const mp_size_t n = 4;
213 const u64 av[4] = {UINT64_MAX - 1, 0, 1, 7};
214 const u64 x = 3;
215
216 mp_ptr a = alloc_limbs(n), backup = alloc_limbs(n), t = alloc_limbs(n + 1);
217 for (mp_size_t i = 0; i < n; ++i) a[i] = av[i];
218
219 /* addmul_1 允许 numa == numb:期望 = a + a*x(mul_1 + add_n 组合)。
220 sum 低 n limbs 在 t,sum 第 n limb = hi + add_n 进位。 */
221 memcpy(backup, a, n * sizeof(mp_limb_t));
222 u64 hi = lmmp_mul_1_(t, backup, n, x);
223 u64 c = lmmp_add_n_(t, backup, t, n);
224 u64 sum_top = hi + c; // addmul 进位输出
225 const mp_limb_t c_add = lmmp_addmul_1_(a, a, n, x);
226 TEST_CHECK_EQ(memcmp(a, t, n * 8), 0);
227 TEST_CHECK_EQ(c_add, sum_top);
228
229 /* submul_1 允许 numa == numb:x==1 时结果为零且无借位。 */
230 memcpy(a, backup, n * sizeof(mp_limb_t));
231 const mp_limb_t c_sub_zero = lmmp_submul_1_(a, a, n, 1);
232 TEST_CHECK_EQ(c_sub_zero, 0u);
233 for (mp_size_t i = 0; i < n; ++i) TEST_CHECK_EQ(a[i], 0u);
234
235 /* x==2:a - 2a 低 n limbs 全零、借位 = 顶 limb+1 语义(组合路径复核)。 */
236 memcpy(a, backup, n * sizeof(mp_limb_t));
237 mp_ptr b2 = alloc_limbs(n);
238 u64 c1 = lmmp_add_n_(b2, backup, backup, n); // 2a
239 u64 w = lmmp_sub_n_(t, backup, b2, n); // a - 2a
240 const mp_limb_t c_sub = lmmp_submul_1_(a, a, n, 2);
241 TEST_CHECK_EQ(memcmp(a, t, n * 8), 0);
242 TEST_CHECK_EQ(c_sub, w + c1);
243
244 lmmp_free(a);
245 lmmp_free(backup);
246 lmmp_free(t);
247 lmmp_free(b2);
248}
249
251 TEST_RUN("memory/addsub", add_n_sub_n_inplace_pair);
252 TEST_RUN("memory/addsub", addshl1_subshl1_inplace);
253 TEST_RUN("memory/shift", shr1add_shr1sub_inplace);
254 TEST_RUN("memory/mul1", mul_1_shifted_overlap);
255 TEST_RUN("memory/div1", div_1_shifted_overlap);
256 TEST_RUN("memory/muladd", addmul_submul_equal_sources);
257}
mp_limb_t * mp_ptr
定义 lmmp.h:96
uint64_t mp_size_t
定义 lmmp.h:93
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_memory_layout(void)
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_shr1add_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
加法后右移1位 [dst,n] = ([numa,n] + [numb,n]) >> 1
定义 shr.c:65
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_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_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])
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_shr1sub_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
减法后右移1位 [dst,n] = ([numa,n] - [numb,n]) >> 1
定义 shr.c:87
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 r1
#define r0
#define b2
#define t
#define n
#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