LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
from_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
32mp_size_t lmmp_from_str_len_(const mp_byte_t* src, mp_size_t len, int base) {
33 lmmp_param_assert(base >= 2 && base <= 256);
34 if (src) {
35 do {
36 if (len == 0)
37 return 1;
38 } while (src[--len] == 0);
39 ++len;
40 }
41 return lmmp_mulh_(len, lmmp_bases_table[base - 2].lg_base) + 1;
42}
43
45 lmmp_param_assert(dst != NULL && src != NULL);
46 lmmp_param_assert(len > 0);
47 lmmp_param_assert(src[len - 1] != off);
48 mp_size_t digitspl = lmmp_bases_table[base - 2].digits_in_limb;
49 mp_limb_t lbase = lmmp_bases_table[base - 2].large_base;
50 mp_size_t limbs = 0, i = len;
51
52 while (i) {
53 mp_limb_t curlimb;
54 if (i >= digitspl) {
55 curlimb = src[--i] - off;
56 for (mp_size_t j = 1; j < digitspl; ++j) {
57 curlimb = curlimb * base + (src[--i] - off);
58 }
59 } else {
60 curlimb = src[--i] - off;
61 lbase = base;
62 while (i) {
63 curlimb = curlimb * base + (src[--i] - off);
64 lbase *= base;
65 }
66 }
67
68 if (limbs == 0) {
69 dst[0] = curlimb;
70 limbs = 1;
71 } else {
72 mp_limb_t cy = lmmp_mul_1_(dst, dst, limbs, lbase);
73 cy += lmmp_add_1_(dst, dst, limbs, curlimb);
74 if (cy) {
75 dst[limbs] = cy;
76 ++limbs;
77 }
78 }
79 }
80
81 return limbs;
82}
83
85 mp_ptr restrict dst,
86 const mp_byte_t* src,
87 mp_size_t len,
88 mp_basepow_t* pow,
90 mp_byte_t off
91) {
92 lmmp_param_assert(dst != NULL && src != NULL && tp != NULL);
93 lmmp_param_assert(len > 0);
94 lmmp_param_assert(src[len - 1] != off);
95 mp_size_t limbs;
96
98 limbs = lmmp_from_str_basecase_(dst, src, len, pow->base, off);
99 } else {
100 mp_size_t pdigits = pow->digits;
101 if (len <= pdigits) {
102 limbs = lmmp_from_str_divide_(dst, src, len, pow - 1, tp, off);
103 } else {
104 mp_ptr p = pow->p;
105 mp_size_t np = pow->np;
106 mp_size_t zeros = pow->zeros;
107 mp_ptr lp = tp, hp = tp + np + zeros - 2; // overwrite 2 limbs
108 mp_size_t nl = 0, nh;
109
110 mp_size_t llen = pdigits;
111 while (llen && src[llen - 1] == off) --llen;
112 if (llen)
113 nl = lmmp_from_str_divide_(lp, src, llen, pow - 1, dst, off);
114
115 mp_limb_t save0 = hp[0], save1 = hp[1]; // save 2 limbs
116 nh = lmmp_from_str_divide_(hp, src + pdigits, len - pdigits, pow - 1, dst, off);
117 if (nh >= np)
118 lmmp_mul_(dst + zeros, hp, nh, p, np);
119 else
120 lmmp_mul_(dst + zeros, p, np, hp, nh);
121 // restore 2 limbs
122 hp[0] = save0;
123 hp[1] = save1;
124
125 if (zeros < nl) {
126 lmmp_copy(dst, lp, zeros);
127 mp_limb_t cy = lmmp_add_n_(dst + zeros, dst + zeros, lp + zeros, nl - zeros);
128 // h*p+l<=(B^nh-1)*p+(p-1)<B^nh*p, limited by nh+np limbs,
129 // so inc won't overflow
130 if (cy)
131 lmmp_inc(dst + nl);
132 } else {
133 lmmp_copy(dst, lp, nl);
134 if (zeros > nl)
135 lmmp_zero(dst + nl, zeros - nl);
136 }
137
138 limbs = nh + np + zeros;
139 limbs -= dst[limbs - 1] == 0;
140 }
141 }
142
143 return limbs;
144}
145
146mp_size_t lmmp_from_str_(mp_ptr dst, const mp_byte_t* src, mp_size_t len, int base) {
147 lmmp_param_assert(base >= 2 && base <= 256);
148 lmmp_param_assert(dst != NULL && src != NULL);
149 do {
150 if (len == 0)
151 return 0;
152 } while (src[--len] == 0);
153 ++len;
154
155 mp_size_t limbs;
156 if (LMMP_POW2_Q(base)) {
157 mp_limb_t curlimb = 0;
158 const mp_byte_t* srcend = src + len;
159 int bitspd = lmmp_bases_table[base - 2].large_base;
160 int bitpos = 0;
161 limbs = 0;
162
163 do {
164 mp_limb_t curdigit = *src;
165 curlimb |= curdigit << bitpos;
166 bitpos += bitspd;
167 if (bitpos >= LIMB_BITS) {
168 dst[limbs] = curlimb;
169 ++limbs;
170 bitpos -= LIMB_BITS;
171 curlimb = curdigit >> (bitspd - bitpos);
172 }
173 } while (++src != srcend);
174 if (curlimb) {
175 dst[limbs] = curlimb;
176 ++limbs;
177 }
178 } else if (lmmp_from_str_len_(0, len, base) < FROM_STR_BASEPOW_THRESHOLD) {
179 limbs = lmmp_from_str_basecase_(dst, src, len, base, 0);
180 } else {
181 TEMP_DECL;
182 mp_basepow_t powers[LIMB_BITS];
183 mp_limb_t lbase = lmmp_bases_table[base - 2].large_base;
184 mp_size_t digitspl = lmmp_bases_table[base - 2].digits_in_limb;
185 mp_size_t bexp, lexp = (len - 1) / digitspl + 1;
186 mp_size_t tzbit = lmmp_tailing_zeros_(lbase);
187 // need 1 extra limb to store result
188 mp_size_t alloc_size = lmmp_from_str_len_(0, len, base) + 1;
189 mp_limb_t cy;
190 mp_ptr tp;
191
192 int cpow = lmmp_limb_bits_(lexp - 1);
193
194 for (int i = cpow; i > 0; --i) {
195 // we will calculate lbase^bexp
196 bexp = ((lexp - 1) >> i) + 1;
197 // we will calculate lbase^(bexp-1) first, and trim it s. t.
198 // it contains at most 2 tailing 0 limb, then multiply it by lbase,
199 // so we need npow limbs to store lbase^bexp
200 mp_size_t npow = lmmp_from_str_len_(0, (bexp - 1) * digitspl + 1, base) + 1;
201
202 if (tzbit) {
203 mp_size_t tzlimb = tzbit * (bexp - 1) / LIMB_BITS;
204 if (tzlimb >= 2)
205 npow -= tzlimb - 2;
206 }
207
208 // space needed for a trimmed npow-limb lbase^bexp
209 alloc_size += npow;
210 }
211
212 tp = BALLOC_TYPE(alloc_size, mp_limb_t);
213
214 for (int i = 0; i < 2; ++i) {
215 tp[0] = lbase;
216 powers[i].p = tp;
217 powers[i].np = 1;
218 tp += i + 1;
219 powers[i].zeros = 0;
220 powers[i].digits = digitspl * (i + 1);
221 powers[i].base = base;
222 }
223
224 mp_ptr p = powers[1].p;
225 mp_size_t zeros = 0, np = 1;
226 for (int i = 2; i < cpow; ++i) {
227 lmmp_sqr_(tp, p, np);
228 np *= 2;
229 np -= tp[np - 1] == 0;
230 bexp = (lexp - 1) >> (cpow - i);
231 if (bexp & 1) {
232 cy = lmmp_mul_1_(tp, tp, np, lbase);
233 tp[np] = cy;
234 np += cy != 0;
235 }
236 zeros *= 2;
237 while (tp[0] == 0) {
238 // at most 2 tailing 0 limb here
239 ++zeros;
240 ++tp;
241 --np;
242 }
243 p = tp;
244 powers[i].p = p;
245 powers[i].np = np;
246 powers[i].zeros = zeros;
247 powers[i].digits = digitspl * (bexp + 1);
248 powers[i].base = base;
249 tp += np + 1;
250 }
251
252 for (int i = 1; i < cpow; ++i) {
253 p = powers[i].p;
254 np = powers[i].np;
255 cy = lmmp_mul_1_(p, p, np, lbase);
256 p[np] = cy;
257 np += cy != 0;
258 if (p[0] == 0) {
259 ++powers[i].zeros;
260 ++p;
261 --np;
262 }
263
264 powers[i].p = p;
265 powers[i].np = np;
266 }
267
268 limbs = lmmp_from_str_divide_(tp, src, len, powers + cpow - 1, dst, 0);
269 lmmp_copy(dst, tp, limbs);
270
271 TEMP_FREE;
272 }
273 return limbs;
274}
#define lmmp_limb_bits_
#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_zero(dst, n)
定义 lmmp.h:476
#define LMMP_POW2_Q(n)
检查n是否为2的幂次方
定义 lmmp.h:467
uint64_t mp_size_t
定义 lmmp.h:93
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 FROM_STR_BASEPOW_THRESHOLD
#define FROM_STR_DIVIDE_THRESHOLD
static mp_limb_t lmmp_add_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
加单精度数静态内联函数 [dst,na]=[numa,na]+x
#define lmmp_inc(p)
加1宏(预期无进位)
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_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_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_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
无进位的n位加法 [dst,n] = [numa,n] + [numb,n]
定义 add_n.c:76
mp_size_t lmmp_from_str_len_(const mp_byte_t *src, mp_size_t len, int base)
计算字节数组转limb数组所需的 limb 缓冲区长度
#define tp
mp_size_t digits
mp_size_t lmmp_from_str_basecase_(mp_ptr dst, const mp_byte_t *src, mp_size_t len, int base, mp_byte_t off)
basecase 字节串转 limb 数组引擎
mp_size_t lmmp_from_str_divide_(mp_ptr dst, const mp_byte_t *src, mp_size_t len, mp_basepow_t *pow, mp_ptr tp, 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)