LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
test_str.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/*
24 字符串转换验证(无 BigInt oracle)。库约定:每字节一个 digit 值
25 (0..base-1),低位在前(little-endian digit order),零值串长 0。
26
27 1. round-trip:to_str → from_str 值复原(多进制 × 多尺寸)
28 2. div_1 重算数字:被除数逐位 div_1 取余重建 digit 串,与 to_str
29 输出精确一致(div_1 由 div 套件独立保证)
30 3. Horner 重建:digit 串经 mul_1+加法逐位求值,与 from_str 输出
31 精确一致
32 4. 写死值锚点(0/1/10/255 等)
33 5. 特化接口:hex(snprintf 按 limb 重建参考串)/ decimal(与
34 to_str+dec_to_chars / from_str 交叉),幂表生命周期(deinit/init)
35*/
36
37#include "lmmp/lmmpn.h"
38#include "cases.h"
40
41#include <ctype.h>
42#include <stdio.h>
43#include <string.h>
44
45// 参考 digit 串:div_1 逐位取余(低位在前;独立于 to_str_ 的幂表路径)
46static mp_size_t ref_digits(mp_byte_t *out, mp_srcptr x, mp_size_t n, int base) {
47 mp_size_t len = 0;
48 mp_ptr work = alloc_limbs(n + 1), q = alloc_limbs(n + 1);
49 lmmp_zero(work, n + 1);
50 memcpy(work, x, (size_t)n * 8);
51 mp_size_t wn = norm_len(work, n + 1);
52 while (wn > 0) {
53 mp_limb_t r = lmmp_div_1_(q, work, wn, base);
54 out[len++] = (mp_byte_t)r;
55 memcpy(work, q, (size_t)wn * 8);
56 while (wn > 0 && work[wn - 1] == 0) --wn;
57 }
58 lmmp_free(work);
59 lmmp_free(q);
60 return len;
61}
62
63// 参考 limb 值:Horner val = val*base + d(高位 digit 先;缓冲须已分配
64// 且本函数全程保持零化)
65static mp_size_t ref_value(mp_ptr val, mp_size_t cap, const mp_byte_t* d, mp_size_t len, int base) {
66 lmmp_zero(val, cap);
67 for (mp_size_t i = len; i-- > 0;) {
68 lmmp_mul_1_(val, val, cap, base); // 高位零垫,cap 内无溢出
69 add_small_inplace(val, cap, d[i]);
70 }
71 return norm_len(val, cap);
72}
73
74// 顶部 limb 的有效位数
75static int limb_bits_of(u64 x) {
76 int k = 0;
77 while (x) {
78 x >>= 1;
79 ++k;
80 }
81 return k;
82}
83
84// 参考十六进制串:每 limb "%016llx" 自高向低拼接后整体反转,前 digits
85// 个字符即低位在前的约定串(纯 limb 运算,无大整数)
86static mp_size_t ref_hex_string(char *out, mp_srcptr x, mp_size_t n, bool upper) {
87 for (mp_size_t i = 0; i < n; ++i) {
88 char buf[17];
89 snprintf(buf, sizeof(buf), "%016llx", (unsigned long long)x[i]);
90 for (size_t j = 0; j < 16; ++j) {
91 char c = buf[15 - j];
92 out[16 * i + j] = upper ? (char)toupper((unsigned char)c) : c;
93 }
94 }
95 mp_size_t nlen = norm_len(x, n);
96 mp_size_t bits = nlen ? 64 * (nlen - 1) + limb_bits_of(x[nlen - 1]) : 0;
97 return (bits + 3) / 4;
98}
99
101 char *reference = lmmp_alloc(16 * n + 1);
102 mp_size_t digits = ref_hex_string(reference, x, n, false);
103
104 TEST_CHECK_EQ(lmmp_to_hex_len_(x, n), digits);
105 TEST_CHECK_EQ(lmmp_to_hex_len_(NULL, n), (mp_size_t)(n * 16));
106
107 for (int upper = 0; upper <= 1; ++upper) {
108 char* got = (char*)lmmp_alloc((size_t)digits + 8);
109 mp_size_t gotn = lmmp_to_hex_(got, x, n, (bool)upper);
110 TEST_CHECK_EQ(gotn, digits);
111 ref_hex_string(reference, x, n, (bool)upper);
112 TEST_CHECK_MSG(memcmp(got, reference, digits) == 0, "to_hex vs reference");
113 if (norm_len(x, n) > 0) TEST_CHECK_MSG(got[digits - 1] != '0', "to_hex no leading zero");
114
115 // from_hex:大小写混合 + 末尾补 '0'(值前导零)
116 TEST_CHECK_EQ(lmmp_from_hex_len_(got, gotn), norm_len(x, n));
117
118 char *padded = lmmp_alloc(gotn + 5);
119 for (mp_size_t i = 0; i < gotn; ++i)
120 padded[i] =
121 (i & 1) ? (char)toupper((unsigned char)got[(size_t)i]) : got[(size_t)i];
122
123 memset(padded + gotn, '0', 5);
124 mp_size_t need = lmmp_from_hex_len_(padded, gotn + 5);
125 mp_ptr back = alloc_limbs((size_t)need + 2);
126 mp_size_t backn = lmmp_from_hex_(back, padded, gotn + 5);
127 TEST_CHECK_MSG(mpn_eq(back, backn, x, n), "hex roundtrip");
128 lmmp_free(back);
129 lmmp_free(got);
130 lmmp_free(padded);
131 }
132 lmmp_free(reference);
133}
134
136 // 参考:to_str_(base 10) 数字节 + lmmp_dec_to_chars_(同为低位在前)
137 mp_size_t reflen = lmmp_to_str_len_(x, n, 10);
138 mp_byte_t* digits = (mp_byte_t*)lmmp_alloc((size_t)reflen + 8);
139 mp_size_t refn = lmmp_to_str_(digits, x, n, 10);
140 lmmp_dec_to_chars_(digits, refn);
141
143 TEST_CHECK_MSG(dlen >= refn, "to_decimal_len upper bound");
144 char* got = (char*)lmmp_alloc((size_t)dlen + 8);
145 mp_size_t gotn = lmmp_to_decimal_(got, x, n);
146 TEST_CHECK_EQ(gotn, refn);
147 if (gotn == refn)
148 TEST_CHECK_MSG(memcmp(got, digits, (size_t)refn) == 0, "to_decimal vs to_str+chars");
149
150 // 独立数字位检查(大尺寸):div_1 逐位参考不走 to_decimal 的幂表
151 // 路径;got 与 rd 同为低位在前
152 if (n >= 100) {
153 mp_byte_t *rd = lmmp_alloc(64 * n);
154 mp_size_t ref_digits_len = ref_digits(rd, x, n, 10);
155 TEST_CHECK_EQ(ref_digits_len, gotn);
156 for (mp_size_t i = 0; i < gotn && i < ref_digits_len; ++i)
157 if (rd[(size_t)i] != (mp_byte_t)(got[i] - '0')) {
158 TEST_CHECK_MSG(false, "to_decimal digit vs div_1 reference");
159 break;
160 }
161 lmmp_free(rd);
162 }
163
164 // from:对照 from_str_(数字节)
165 mp_byte_t *digit_vals = digits;
166 for (mp_size_t i = 0; i < refn; ++i) digit_vals[(size_t)i] = (mp_byte_t)(digits[i] - '0');
167 mp_size_t wlen = lmmp_from_str_len_(digit_vals, refn, 10);
168 mp_ptr want = alloc_limbs((size_t)wlen + 2);
169 mp_size_t wantn = lmmp_from_str_(want, digit_vals, refn, 10);
170
171 char *padded = lmmp_alloc(gotn + 3);
172 memcpy(padded, got, gotn);
173 memset(padded + gotn, '0', 3);
174 mp_size_t dneed = lmmp_from_decimal_len_(padded, gotn + 3);
175 TEST_CHECK_MSG(dneed >= wantn, "from_decimal_len upper bound");
176 mp_ptr back = alloc_limbs((size_t)dneed + 2);
177 mp_size_t backn = lmmp_from_decimal_(back, padded, gotn + 3);
178 TEST_CHECK_EQ(backn, wantn);
179 if (backn == wantn)
180 TEST_CHECK_MSG(memcmp(back, want, (size_t)wantn * 8) == 0, "from_decimal vs from_str");
181 TEST_CHECK_MSG(mpn_eq(back, backn, x, n), "decimal roundtrip");
182
183 lmmp_free(back);
184 lmmp_free(want);
185 lmmp_free(padded);
186 lmmp_free(got);
187 lmmp_free(digits);
188}
189
190TEST_CASE("str/roundtrip", to_str_from_str_roundtrip) {
191 u64 seed = 0xe3459cd6b789abeful;
192 int bases[] = {2, 8, 10, 16, 36, 62, 100, 256};
193 for (size_t base_index = 0; base_index < ARRAY_SIZE(bases); ++base_index) {
194 int base = bases[base_index];
195 const mp_size_t n_values[] = {1, 2, 5, 10, 20, 40};
196 for (size_t n_index = 0; n_index < ARRAY_SIZE(n_values); ++n_index) {
197 mp_size_t n = n_values[n_index];
198 for (int iter = 0; iter < 3; ++iter) {
199 mp_ptr x = alloc_limbs(n);
200 random_limbs(x, n, &seed);
201
202 mp_size_t str_len = lmmp_to_str_len_(x, n, base);
203 mp_byte_t* str = (mp_byte_t*)lmmp_alloc((size_t)str_len + 8);
204 mp_size_t actual = lmmp_to_str_(str, x, n, base);
205 TEST_CHECK_MSG(actual <= str_len, "to_str actual <= len");
206
207 mp_size_t need = lmmp_from_str_len_(str, actual, base);
208 mp_ptr back = alloc_limbs((size_t)need + 2);
209 mp_size_t back_n = lmmp_from_str_(back, str, actual, base);
210 TEST_CHECK_MSG(mpn_eq(back, back_n, x, n), "string roundtrip equality");
211
212 // div_1 重算数字:digit 串精确一致
213 mp_byte_t *rd = lmmp_alloc(64 * n);
214 mp_size_t ref_digits_len = ref_digits(rd, x, n, base);
215 bool dok = ref_digits_len == actual &&
216 memcmp(rd, str, (size_t)actual) == 0;
217 TEST_CHECK_MSG(dok, "to_str digits == div_1 recomputation");
218 lmmp_free(rd);
219
220 // Horner 重建:from_str 值精确一致
221 mp_ptr hv = alloc_limbs((size_t)need + 2);
222 mp_size_t hn = ref_value(hv, need + 2, str, actual, base);
223 TEST_CHECK_MSG(mpn_eq(hv, hn, x, n), "from_str value == Horner rebuild");
224
225 lmmp_free(hv);
226 lmmp_free(back);
227 lmmp_free(str);
228 lmmp_free(x);
229 }
230 }
231 // 零值 round-trip(零值串长 0,from_str 空串回零)
232 mp_ptr z = alloc_limbs(2);
233 lmmp_zero(z, 2);
234 {
235 mp_byte_t zbuf[4];
236 mp_size_t zn = lmmp_to_str_(zbuf, z, 2, base);
237 TEST_CHECK_EQ(zn, (mp_size_t)0);
238 mp_ptr back = alloc_limbs(2);
239 mp_size_t bn = lmmp_from_str_(back, zbuf, zn, base);
240 TEST_CHECK_MSG(bn == 0 || (bn == 1 && back[0] == 0), "zero roundtrip");
241 lmmp_free(back);
242 }
243 lmmp_free(z);
244 }
245}
246
247static void check_value(mp_srcptr x, mp_size_t n, const mp_byte_t *expect,
248 mp_size_t expected_len, int base) {
249 mp_size_t want = lmmp_to_str_len_(x, n, base);
250 mp_byte_t *str = lmmp_alloc(want + 8);
251 mp_size_t actual = lmmp_to_str_(str, x, n, base);
252 TEST_CHECK_EQ(actual, expected_len);
253 if (actual == expected_len)
254 TEST_CHECK_MSG(memcmp(str, expect, actual) == 0, "known digit string match");
255 lmmp_free(str);
256}
257
258TEST_CASE("str/known", known_values) {
259 const mp_limb_t v0[] = {0}, v1[] = {1}, v10[] = {10}, v255[] = {255};
260 const mp_byte_t empty[] = {0};
261 check_value(v0, 1, empty, 0, 10);
262 check_value(v1, 1, (const mp_byte_t[]){1}, 1, 10);
263 check_value(v10, 1, (const mp_byte_t[]){0, 1}, 2, 10);
264 check_value(v255, 1, (const mp_byte_t[]){5, 5, 2}, 3, 10);
265 check_value(v255, 1, (const mp_byte_t[]){1, 1, 1, 1, 1, 1, 1, 1}, 8, 2);
266 check_value(v255, 1, (const mp_byte_t[]){15, 15}, 2, 16);
267
268 const mp_limb_t vB[] = {0, 1};
269 const mp_byte_t wantB[65] = {[64] = 1};
270 check_value(vB, 2, wantB, ARRAY_SIZE(wantB), 2);
271
272 const mp_limb_t vF[] = {LIMB_MAX};
273 mp_byte_t wantF[16];
274 memset(wantF, 15, sizeof(wantF));
275 check_value(vF, 1, wantF, ARRAY_SIZE(wantF), 16);
276}
277
278TEST_CASE("str/hex_spec", hex_specialized) {
279 u64 seed = 0xfeedfacecafebeeful;
280 const mp_size_t n_values[] = {1, 2, 3, 5, 17, 64, 100, 333};
281 for (size_t n_index = 0; n_index < ARRAY_SIZE(n_values); ++n_index) {
282 mp_size_t n = n_values[n_index];
283 mp_ptr x = alloc_limbs(n);
284 random_limbs(x, n, &seed);
285 check_hex_one(x, n);
286 lmmp_free(x);
287 }
288 // 顶部 limb 特殊值(nibble 边界)
289 const u64 top_values[] = {1ull, 0xfull, 0x10ull, 0xffull};
290 for (size_t top_index = 0; top_index < ARRAY_SIZE(top_values); ++top_index) {
291 u64 top = top_values[top_index];
292 mp_ptr x = alloc_limbs(9);
293 random_limbs(x, 9, &seed);
294 x[8] = top;
295 check_hex_one(x, 9);
296 lmmp_free(x);
297 }
298 // 零值与空串
299 mp_limb_t zero[1] = {0};
301 char buf[8];
302 TEST_CHECK_EQ(lmmp_to_hex_(buf, zero, 1, false), (mp_size_t)0);
304 mp_ptr dst = alloc_limbs(4);
305 TEST_CHECK_EQ(lmmp_from_hex_(dst, "0000", 4), (mp_size_t)0);
306 TEST_CHECK_EQ(lmmp_from_hex_(dst, "", 0), (mp_size_t)0);
307 TEST_CHECK_EQ(lmmp_from_hex_(dst, "f", 1), (mp_size_t)1);
308 TEST_CHECK_EQ(dst[0], (mp_limb_t)15);
309 TEST_CHECK_EQ(lmmp_from_hex_(dst, "F", 1), (mp_size_t)1);
310 TEST_CHECK_EQ(dst[0], (mp_limb_t)15);
311 TEST_CHECK_EQ(lmmp_from_hex_(dst, "71", 2), (mp_size_t)1);
312 TEST_CHECK_EQ(dst[0], (mp_limb_t)0x17); // 低位在前:'7' 在前 = 0x7+0x10
313 lmmp_free(dst);
314}
315
316TEST_CASE("str/decimal_spec", decimal_specialized) {
317 u64 seed = 0xd1ce0dd1ce0dd1ceull;
318 // 覆盖 basecase/分治阈值附近与幂表逐层增长
319 const mp_size_t n_values[] = {1, 2, 3, 29, 30, 31, 44, 45, 60, 100, 137, 200, 300};
320 for (size_t n_index = 0; n_index < ARRAY_SIZE(n_values); ++n_index) {
321 mp_size_t n = n_values[n_index];
322 mp_ptr x = alloc_limbs(n);
323 random_limbs(x, n, &seed);
325 lmmp_free(x);
326 }
327 // 幂表收缩复用:小规模再次转换
328 for (int rep = 0; rep < 3; ++rep) {
329 mp_ptr x = alloc_limbs(33);
330 random_limbs(x, 33, &seed);
331 check_decimal_one(x, 33);
332 lmmp_free(x);
333 }
334 // 顶部 limb 特殊值
335 const u64 top_values[] = {1ull, 0x10ull, 0xffull};
336 for (size_t top_index = 0; top_index < ARRAY_SIZE(top_values); ++top_index) {
337 u64 top = top_values[top_index];
338 mp_ptr x = alloc_limbs(41);
339 random_limbs(x, 41, &seed);
340 x[40] = top;
341 check_decimal_one(x, 41);
342 lmmp_free(x);
343 }
344 // 零值与写死小值
345 mp_limb_t zero[1] = {0};
346 TEST_CHECK_MSG(lmmp_to_decimal_len_(zero, 1) >= 1, "zero to_decimal_len");
347 char buf[8];
348 TEST_CHECK_EQ(lmmp_to_decimal_(buf, zero, 1), (mp_size_t)0);
350 mp_ptr dst = alloc_limbs(4);
351 TEST_CHECK_EQ(lmmp_from_decimal_(dst, "000000", 6), (mp_size_t)0);
354 TEST_CHECK_EQ(dst[0], (mp_limb_t)7);
355 TEST_CHECK_EQ(lmmp_from_decimal_(dst, "96", 2), (mp_size_t)1); // 低位在前: 96 -> 6*10+9=69
356 TEST_CHECK_EQ(dst[0], (mp_limb_t)69);
357 lmmp_free(dst);
358}
359
360TEST_CASE("str/decimal_powcache", decimal_pow_cache_lifecycle) {
361 u64 seed = 0x5eed5eed5eed5eedull;
362 mp_ptr big1 = alloc_limbs(300), big2 = alloc_limbs(150), small = alloc_limbs(35);
363 random_limbs(big1, 300, &seed);
364 random_limbs(big2, 150, &seed);
365 random_limbs(small, 35, &seed);
366
367 check_decimal_one(big1, 300); // 增长
368 check_decimal_one(small, 35); // 复用
369 check_decimal_one(big2, 150); // 复用
370
371 // deinit 释放幂表后重新初始化,验证惰性重建
374 check_decimal_one(big2, 150);
375 check_decimal_one(small, 35);
376 lmmp_free(big1);
377 lmmp_free(big2);
378 lmmp_free(small);
379}
380
381void test_str(void) {
382 TEST_RUN("str/roundtrip", to_str_from_str_roundtrip);
383 TEST_RUN("str/known", known_values);
384 TEST_RUN("str/hex_spec", hex_specialized);
385 TEST_RUN("str/decimal_spec", decimal_specialized);
386 TEST_RUN("str/decimal_powcache", decimal_pow_cache_lifecycle);
387}
#define k
#define bn
mp_limb_t * mp_ptr
定义 lmmp.h:96
uint8_t mp_byte_t
定义 lmmp.h:91
#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)
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
#define LIMB_MAX
定义 lmmp.h:105
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
void lmmp_global_init(void)
全局初始化函数(线程局部的)
uint64_t mp_limb_t
定义 lmmp.h:92
void lmmp_global_deinit(void)
全局释放函数(线程局部的)
mp_limb_t u64
Copyright (C) 2026 HJimmyK (Jericho Knox)
void test_str(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_size_t lmmp_to_hex_len_(mp_srcptr numa, mp_size_t na)
计算转换为十六进制字符串需要的缓冲区长度
mp_size_t lmmp_from_hex_len_(const char *src, mp_size_t len)
计算十六进制字符串转limb数组所需的 limb 缓冲区长度
mp_size_t lmmp_to_decimal_(char *dst, mp_srcptr numa, mp_size_t na)
limb数组转十进制字符串 [numa,na,B] to [dst,return value,10]
mp_size_t lmmp_from_decimal_(mp_ptr dst, const char *src, mp_size_t len)
十进制字符串转limb数组 [src,len,10] to [dst,return value,B]
mp_size_t lmmp_to_str_(mp_byte_t *dst, mp_srcptr numa, mp_size_t na, int base)
limb数组转字节数组操作 [numa,na,B] to [dst,return value,base]
mp_size_t lmmp_to_hex_(char *dst, mp_srcptr numa, mp_size_t na, bool upper)
limb数组转十六进制字符串 [numa,na,B] to [dst,return value,16]
void lmmp_dec_to_chars_(mp_byte_t *dst, mp_size_t n)
十进制数字字节原地转字符 [dst,n]: [0,9] -> ['0','9']
mp_size_t lmmp_from_str_(mp_ptr dst, const mp_byte_t *src, mp_size_t len, int base)
字节数组转limb数组操作 [src,len,base] to [dst,return value,B]
mp_size_t lmmp_to_str_len_(mp_srcptr numa, mp_size_t na, int base)
计算转换为字节数组,字节数组需要的缓冲区长度
mp_size_t lmmp_to_decimal_len_(mp_srcptr numa, mp_size_t na)
计算转换为十进制字符串需要的缓冲区长度
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_size_t lmmp_from_decimal_len_(const char *src, mp_size_t len)
计算十进制字符串转limb数组所需的 limb 缓冲区长度
mp_size_t lmmp_from_hex_(mp_ptr dst, const char *src, mp_size_t len)
十六进制字符串转limb数组 [src,len,16] to [dst,return value,B]
mp_size_t lmmp_from_str_len_(const mp_byte_t *src, mp_size_t len, int base)
计算字节数组转limb数组所需的 limb 缓冲区长度
#define v0
#define v1
#define n
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 perf.h:40
#define TEST_CHECK_MSG(cond, msg)
定义 test.h:38
#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
static int limb_bits_of(u64 x)
static mp_size_t ref_hex_string(char *out, mp_srcptr x, mp_size_t n, bool upper)
static mp_size_t ref_digits(mp_byte_t *out, mp_srcptr x, mp_size_t n, int base)
Copyright (C) 2026 HJimmyK (Jericho Knox)
static void check_hex_one(mp_srcptr x, mp_size_t n)
static mp_size_t ref_value(mp_ptr val, mp_size_t cap, const mp_byte_t *d, mp_size_t len, int base)
static void check_value(mp_srcptr x, mp_size_t n, const mp_byte_t *expect, mp_size_t expected_len, int base)
static void check_decimal_one(mp_srcptr x, mp_size_t n)