LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
to_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#include "impl/str_conv.h"
24#include "impl/inlines.h"
25#include "mparam.h"
26#include "impl/tmp_alloc.h"
27#include "lmmp/lmmpn.h"
28
30
31
33 lmmp_param_assert(base >= 2 && base <= 256);
34 int mslbits = 0;
35 if (numa) {
36 do {
37 if (na == 0)
38 return 1;
39 } while (numa[--na] == 0);
40 mslbits = lmmp_limb_bits_(numa[na]);
41 }
42 return lmmp_mulh_(na * LIMB_BITS + mslbits, lmmp_bases_table[base - 2].inv_lg_base) + 1;
43}
44
46 lmmp_param_assert(na > 0);
47 lmmp_param_assert(dst != NULL && numa != NULL);
48 lmmp_param_assert(numa[na - 1]!= 0);
49 int i;
50 int digitspl = lmmp_bases_table[base - 2].digits_in_limb;
51 mp_limb_t lbase = lmmp_bases_table[base - 2].large_base;
52 mp_size_t n = 0;
53 mp_limb_t frac;
55 lmmp_copy(tp + 1, numa, na);
56
57 do {
58 tp[0] = 0;
59 lmmp_div_1_(tp, tp, na + 1, lbase);
60 frac = tp[0] + 1;
61 na -= tp[na] == 0;
62 if (na == 0)
63 break;
64 i = digitspl;
65 do {
66 dst[--i] = (mp_byte_t)(lmmp_mulh_(frac, base) + off);
67 frac *= base;
68 } while (i);
69 dst += digitspl;
70 n += digitspl;
71 } while (1);
72
73 // 最高块需先以原始数字值判零剥前导零,再叠加 off
74 mp_limb_t msd;
75 i = digitspl;
76 while (i && (msd = lmmp_mulh_(frac, base)) == 0) {
77 --i;
78 frac *= base;
79 }
80 n += i;
81 while (i) {
82 dst[--i] = (mp_byte_t)(msd + off);
83 frac *= base;
84 msd = lmmp_mulh_(frac, base);
85 }
86 return n;
87}
88
90 mp_byte_t* dst,
91 mp_ptr restrict numa,
92 mp_size_t na,
93 mp_basepow_t* pow,
94 mp_ptr restrict tpq,
95 mp_byte_t off
96) {
97 lmmp_param_assert(na > 0);
98 lmmp_param_assert(dst != NULL && numa != NULL && tpq != NULL);
99 lmmp_param_assert(pow != NULL);
100 lmmp_param_assert(numa[na - 1] != 0);
101 mp_size_t digits;
102 if (na < TO_STR_DIVIDE_THRESHOLD) {
103 digits = lmmp_to_str_basecase_(dst, numa, na, pow->base, off);
104 } else {
105 mp_ptr p = pow->p, invp = pow->invp;
106 mp_size_t np = pow->np, ni = pow->ni;
107 mp_size_t zeros = pow->zeros;
108 mp_size_t pdigits = pow->digits;
109 int cnt = pow->norm_cnt;
110 int adjust = 0;
111
112 // may adjust na s.t. qh=0
113 if (na >= np + zeros) {
114 mp_limb_t ah = 0, al = numa[na - 1] << cnt;
115 if (cnt) {
116 ah = numa[na - 1] >> (LIMB_BITS - cnt);
117 if (na > zeros + 1)
118 al |= numa[na - 2] >> (LIMB_BITS - cnt);
119 }
120 adjust = (ah || al >= p[np - 1]);
121 }
122
123 // if numa<p
124 if (na + adjust <= np + zeros) {
125 // skip this power
126 digits = lmmp_to_str_divide_(dst, numa, na, pow - 1, tpq, off);
127 } else {
128 numa[na] = 0;
129 na += adjust;
130
131 numa += zeros;
132 na -= zeros;
133
134 mp_size_t nq = na - np, nr = np + zeros;
135 mp_ptr q = tpq, r = numa - zeros;
136
137 if (cnt)
138 lmmp_shl_(numa, numa, na, cnt);
139 if (invp)
140 lmmp_div_mulinv_(q, numa, na, p, np, invp, ni);
141 else
142 lmmp_div_s_(q, numa, na, p, np);
143 if (cnt)
144 lmmp_shr_(numa, numa, np, cnt);
145
146 mp_size_t digitsh = 0, digitsl = 0;
147
148 while (nq && q[nq - 1] == 0) --nq;
149 if (nq)
150 digitsh = lmmp_to_str_divide_(dst + pdigits, q, nq, pow - 1, tpq + nq + 1, off);
151
152 while (nr && r[nr - 1] == 0) --nr;
153 if (nr)
154 digitsl = lmmp_to_str_divide_(dst, r, nr, pow - 1, tpq, off);
155
156 if (digitsh) {
157 while (digitsl != pdigits) {
158 dst[digitsl] = off;
159 ++digitsl;
160 }
161 }
162
163 digits = digitsl + digitsh;
164 }
165 }
166 return digits;
167}
168
170 lmmp_param_assert(base >= 2 && base <= 256);
171 lmmp_param_assert(dst != NULL && numa != NULL);
172 do {
173 if (na == 0)
174 return 0;
175 } while (numa[--na] == 0);
176 ++na;
177
178 mp_size_t digits;
179 if (LMMP_POW2_Q(base)) {
180 mp_limb_t curlimb = numa[na - 1];
181 int cnt = lmmp_bases_table[base - 2].large_base;
182 int bitsh = lmmp_limb_bits_(curlimb);
183 int mask = (1 << cnt) - 1;
184 mp_size_t bits = bitsh + LIMB_BITS * (na - 1);
185 digits = (bits - 1) / cnt + 1;
186 dst += digits;
187 int bitpos = digits * cnt - LIMB_BITS * (na - 1);
188
189 do {
190 while ((bitpos -= cnt) >= 0) {
191 *--dst = curlimb >> bitpos & mask;
192 }
193 if (--na == 0)
194 break;
195 mp_limb_t prevlimb = curlimb << -bitpos;
196 curlimb = numa[na - 1];
197 bitpos += LIMB_BITS;
198 *--dst = (prevlimb | curlimb >> bitpos) & mask;
199 } while (1);
200 } else if (na < TO_STR_BASEPOW_THRESHOLD) {
201 digits = lmmp_to_str_basecase_(dst, numa, na, base, 0);
202 } else {
203 TEMP_DECL;
204 mp_basepow_t powers[LIMB_BITS];
205 mp_size_t exps[LIMB_BITS];
206 mp_limb_t lbase = lmmp_bases_table[base - 2].large_base;
207 mp_size_t digitspl = lmmp_bases_table[base - 2].digits_in_limb;
208 mp_size_t bexp = (lmmp_to_str_len_(numa, na, base) - 1) / digitspl + 1;
209 mp_size_t tzbit = lmmp_tailing_zeros_(lbase);
210 // numa 的拷贝空间,多一个 limb 预留规整化移位所需
211 mp_size_t alloc_size = na + 1;
212 mp_limb_t cy;
213 mp_ptr tp;
214
215 int cpow = 0;
216
217 do {
218 bexp = (bexp + 1) >> 1;
219 exps[cpow] = bexp;
220 ++cpow;
221
222 // we will calculate lbase^(bexp-1) first, and trim it s. t.
223 // it contains at most 2 tailing 0 limb, then multiply it by lbase,
224 // so we need npow limbs to store lbase^bexp
225 mp_size_t npow = lmmp_from_str_len_(0, (bexp - 1) * digitspl + 1, base) + 1;
226
227 // space needed for quotients in recursive calls,
228 // quotients are smaller than lbase^bexp
229 alloc_size += npow + 1;
230
231 if (tzbit) {
232 mp_size_t tzlimb = tzbit * (bexp - 1) / LIMB_BITS;
233 if (tzlimb >= 2)
234 npow -= tzlimb - 2;
235 }
236
237 // space needed for a trimmed npow-limb lbase^bexp and its inverse
238 alloc_size += npow * 2;
239 } while (bexp > 1);
240
241 tp = BALLOC_TYPE(alloc_size, mp_limb_t);
242
243 for (int i = 0; i < 2; ++i) {
244 tp[0] = lbase;
245 powers[i].p = tp;
246 powers[i].np = 1;
247 tp += i + 1;
248 powers[i].zeros = 0;
249 powers[i].digits = digitspl * (i + 1);
250 powers[i].base = base;
251 }
252
253 mp_ptr p = powers[1].p;
254 mp_size_t zeros = 0, np = 1;
255 bexp = 1;
256 for (int i = 2; i < cpow; ++i) {
257 lmmp_sqr_(tp, p, np);
258 bexp *= 2;
259 np *= 2;
260 np -= tp[np - 1] == 0;
261 if (bexp + 1 < exps[cpow - 1 - i]) {
262 cy = lmmp_mul_1_(tp, tp, np, lbase);
263 tp[np] = cy;
264 np += cy != 0;
265 ++bexp;
266 }
267 zeros *= 2;
268 while (tp[0] == 0) {
269 // at most 2 tailing 0 limb here
270 ++zeros;
271 ++tp;
272 --np;
273 }
274 p = tp;
275 powers[i].p = p;
276 powers[i].np = np;
277 powers[i].zeros = zeros;
278 powers[i].digits = digitspl * (bexp + 1);
279 powers[i].base = base;
280 tp += np + 1;
281 }
282
283 for (int i = 1; i < cpow; ++i) {
284 p = powers[i].p;
285 np = powers[i].np;
286 cy = lmmp_mul_1_(p, p, np, lbase);
287 p[np] = cy;
288 np += cy != 0;
289 if (p[0] == 0) {
290 ++powers[i].zeros;
291 ++p;
292 --np;
293 }
294
295 powers[i].p = p;
296 powers[i].np = np;
297
298 // Note: all powers except powers[0] are normalized
299 // ASSERT: powers[0] will be never used in lmmp_to_str_divide_
300 // i.e. TO_STR_DIVIDE_THRESHOLD >= 3
301 int cnt = lmmp_leading_zeros_(p[np - 1]);
302 if ((powers[i].norm_cnt = cnt))
303 lmmp_shl_(p, p, np, cnt);
304
305 if (np < DIV_MULINV_L_THRESHOLD) {
306 // use divs, no need to compute inv
307 powers[i].invp = 0;
308 powers[i].ni = 0;
309 } else {
310 // pre-compute inverse
311 mp_size_t ni = lmmp_div_inv_size_(np + powers[i].zeros, np);
312 lmmp_inv_prediv_(tp, p, np, ni);
313 powers[i].invp = tp;
314 powers[i].ni = ni;
315 tp += ni;
316 }
317 }
318
319 lmmp_copy(tp, numa, na);
320 digits = lmmp_to_str_divide_(dst, tp, na, powers + cpow - 1, tp + na + 1, 0);
321
322 TEMP_FREE;
323 }
324
325 return digits;
326}
#define lmmp_limb_bits_
#define lmmp_leading_zeros_
#define lmmp_sqr_
#define lmmp_tailing_zeros_
#define lmmp_mulh_
mp_limb_t * mp_ptr
定义 lmmp.h:96
uint8_t mp_byte_t
定义 lmmp.h:91
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
#define LMMP_POW2_Q(n)
检查n是否为2的幂次方
定义 lmmp.h:467
uint64_t mp_size_t
定义 lmmp.h:93
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
uint64_t mp_limb_t
定义 lmmp.h:92
#define LMMP_VECT_CONSERVATIVE
定义 lmmp.h:201
#define LIMB_BITS
定义 lmmp.h:102
#define lmmp_param_assert(x)
定义 lmmp.h:509
#define DIV_MULINV_L_THRESHOLD
#define TO_STR_DIVIDE_THRESHOLD
#define TO_STR_BASEPOW_THRESHOLD
mp_limb_t lmmp_div_s_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
除法运算
static mp_size_t lmmp_div_inv_size_(mp_size_t nq, mp_size_t nb)
计算预计算逆元的尺寸
mp_limb_t lmmp_div_1_(mp_ptr dstq, mp_srcptr numa, mp_size_t na, mp_limb_t x)
单精度数除法
定义 div.c:137
void lmmp_inv_prediv_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t ni)
除法前的逆元预计算,[dst,ni] = invappr( (ni+1 MSLs of numa) + 1 ) / B
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_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_str_len_(mp_srcptr numa, mp_size_t na, int base)
计算转换为字节数组,字节数组需要的缓冲区长度
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_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_div_mulinv_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, mp_srcptr invappr, mp_size_t ni)
乘法逆元除法
mp_size_t lmmp_from_str_len_(const mp_byte_t *src, mp_size_t len, int base)
计算字节数组转limb数组所需的 limb 缓冲区长度
#define tp
#define n
mp_size_t digits
mp_size_t lmmp_to_str_basecase_(mp_byte_t *dst, mp_srcptr numa, mp_size_t na, int base, mp_byte_t off)
basecase limb 数组转字节串引擎
mp_size_t lmmp_to_str_divide_(mp_byte_t *dst, mp_ptr numa, mp_size_t na, mp_basepow_t *pow, mp_ptr tpq, mp_byte_t off)
分治 limb 数组转字节串引擎
const mp_base_t lmmp_bases_table[255]
Copyright (C) 2026 HJimmyK (Jericho Knox)
mp_limb_t large_base
mp_size_t zeros
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define TEMP_FREE
#define BALLOC_TYPE(n, type)