LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
powlo.c 文件参考
#include "impl/tmp_alloc.h"
#include "impl/longlong.h"
#include "impl/inlines.h"
#include "mparam.h"
#include "lmmp/lmmpn.h"
#include "lmmp/numth.h"
powlo.c 的引用(Include)关系图:

浏览该文件的源代码.

宏定义

#define getbit(p, bi)

函数

static mp_bitcnt_t count_bits (mp_srcptr p, mp_size_t n)
static mp_limb_t getbits (const mp_limb_t *p, mp_bitcnt_t bi, mp_bitcnt_t nbits)
static void lmmp_mullo_n_ (mp_ptr restrict dst, mp_srcptr restrict numa, mp_srcptr restrict numb, mp_size_t n, mp_ptr restrict tp)
void lmmp_powlo_ (mp_ptr restrict dst, mp_srcptr restrict bp, mp_size_t n, mp_srcptr restrict ep, mp_size_t en)
void lmmp_powlo_1_ (mp_ptr restrict dst, mp_srcptr restrict bp, mp_srcptr restrict ep, mp_size_t en)
void lmmp_powlo_2_ (mp_ptr restrict dst, mp_srcptr restrict bp, mp_srcptr restrict ep, mp_size_t en)
static void lmmp_sqrlo_n_ (mp_ptr restrict dst, mp_srcptr restrict numa, mp_size_t n, mp_ptr restrict tp)
 Copyright (C) 2026 HJimmyK (Jericho Knox)
static mp_size_t win_size (mp_size_t eb)

宏定义说明

◆ getbit

#define getbit ( p,
bi )
值:
((p[(bi - 1) / LIMB_BITS] >> (bi - 1) % LIMB_BITS) & 1)
#define LIMB_BITS
定义 lmmp.h:102

在文件 powlo.c 第 65 行定义.

被这些函数引用 lmmp_powlo_(), lmmp_powlo_1_(), lmmp_powlo_2_(), lmmp_powmod_1_(), lmmp_powmod_2_() , 以及 lmmp_powmod_odd_mont_().

函数说明

◆ count_bits()

mp_bitcnt_t count_bits ( mp_srcptr p,
mp_size_t n )
inlinestatic

在文件 powlo.c 第 86 行定义.

86 {
87 return (n - 1) * LIMB_BITS + lmmp_limb_bits_(p[n - 1]);
88}
#define lmmp_limb_bits_
#define n

引用了 count_bits(), LIMB_BITS, lmmp_limb_bits_ , 以及 n.

被这些函数引用 count_bits(), count_bits(), count_bits(), count_bits(), lmmp_powlo_(), lmmp_powlo_1_(), lmmp_powlo_2_(), lmmp_powmod_1_(), lmmp_powmod_2_(), lmmp_powmod_odd_() , 以及 lmmp_powmod_odd_mont_().

函数调用图:
这是这个函数的调用关系图:

◆ getbits()

mp_limb_t getbits ( const mp_limb_t * p,
mp_bitcnt_t bi,
mp_bitcnt_t nbits )
inlinestatic

在文件 powlo.c 第 67 行定义.

67 {
68 mp_bitcnt_t nbits_in_r;
69 mp_limb_t r;
70 mp_size_t i;
71
72 if (bi <= nbits) {
73 return p[0] & (((mp_limb_t)1 << bi) - 1);
74 } else {
75 bi -= nbits; /* bit index of low bit to extract */
76 i = bi / LIMB_BITS; /* word index of low bit to extract */
77 bi %= LIMB_BITS; /* bit index in low word */
78 r = p[i] >> bi; /* extract (low) bits */
79 nbits_in_r = LIMB_BITS - bi; /* number of bits now in r */
80 if (nbits_in_r < nbits) /* did we get enough bits? */
81 r += p[i + 1] << nbits_in_r; /* prepend bits from higher word */
82 return r & (((mp_limb_t)1 << nbits) - 1);
83 }
84}
size_t mp_bitcnt_t
定义 lmmp.h:98
uint64_t mp_size_t
定义 lmmp.h:93
uint64_t mp_limb_t
定义 lmmp.h:92

引用了 getbits() , 以及 LIMB_BITS.

被这些函数引用 getbits(), getbits(), getbits(), getbits(), lmmp_powlo_(), lmmp_powlo_1_(), lmmp_powlo_2_(), lmmp_powmod_1_(), lmmp_powmod_2_() , 以及 lmmp_powmod_odd_mont_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_mullo_n_()

void lmmp_mullo_n_ ( mp_ptr restrict dst,
mp_srcptr restrict numa,
mp_srcptr restrict numb,
mp_size_t n,
mp_ptr restrict tp )
inlinestatic

在文件 powlo.c 第 44 行定义.

50 {
51 if (n < MULLO_DC_THRESHOLD) {
52 lmmp_mullo_dc_(dst, numa, numb, tp, n);
53 } else {
54 lmmp_mullo_fft_(dst, numa, numb, n, tp);
55 }
56}
#define MULLO_DC_THRESHOLD
void lmmp_mullo_dc_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_ptr tp, mp_size_t n)
低位乘法 [dst,n] = [numa,n] * [numb,n] mod B^n
void lmmp_mullo_fft_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n, mp_ptr scratch)
低位FFT乘法 [dst,n] = [numa,n] * [numb,n] mod B^n
定义 mullo.c:68
#define numb
#define tp

引用了 lmmp_mullo_dc_(), lmmp_mullo_fft_(), lmmp_mullo_n_(), MULLO_DC_THRESHOLD, n, numb, restrict , 以及 tp.

函数调用图:

◆ lmmp_powlo_()

void lmmp_powlo_ ( mp_ptr restrict dst,
mp_srcptr restrict bp,
mp_size_t n,
mp_srcptr restrict ep,
mp_size_t en )

在文件 powlo.c 第 90 行定义.

90 {
91 lmmp_param_assert(ep[en - 1] > 0);
92 lmmp_param_assert(n > 0 && en > 0);
93 lmmp_param_assert(dst != NULL && bp != NULL && ep != NULL);
94 if (n == 1) {
95 lmmp_powlo_1_(dst, bp, ep, en);
96 return;
97 }
98 if (n == 2) {
99 lmmp_powlo_2_(dst, bp, ep, en);
100 return;
101 }
102 mp_bitcnt_t cnt, ebi;
103 unsigned windowsize, this_windowsize;
104 mp_limb_t expbits;
105 mp_limb_t* pp;
106 long i;
107 int flipflop;
108 TEMP_DECL;
110 mp_ptr restrict scratch = tp + 3 * n;
111
112 ebi = count_bits(ep, en);
113
114 /* 指数为 1:[bp,n] mod B^n 即截断本身,免去建表与梯子 */
115 if (ebi == 1) {
116 lmmp_copy(dst, bp, n);
117 TEMP_FREE;
118 return;
119 }
120
121 windowsize = win_size(ebi);
122 if (windowsize > 1) {
123 mp_limb_t *this_pp, *last_pp;
124 lmmp_debug_assert(windowsize < ebi);
125
126 pp = TALLOC_TYPE((n << (windowsize - 1)), mp_limb_t);
127
128 this_pp = pp;
129
130 lmmp_copy(this_pp, bp, n);
131
132 /* Store b^2 in tp. */
133 lmmp_sqrlo_n_(tp, bp, n, scratch);
134
135 /* Precompute odd powers of b and put them in the temporary area at pp. */
136 i = (1 << (windowsize - 1)) - 1;
137 do {
138 last_pp = this_pp;
139 this_pp += n;
140 lmmp_mullo_n_(this_pp, last_pp, tp, n, scratch);
141 } while (--i != 0);
142
143 expbits = getbits(ep, ebi, windowsize);
144 ebi -= windowsize;
145
146 ctz_shr_u64(expbits, expbits, cnt);
147 ebi += cnt;
148
149 lmmp_copy(dst, pp + n * (expbits >> 1), n);
150 } else {
151 pp = tp + n;
152 lmmp_copy(pp, bp, n);
153 lmmp_copy(dst, bp, n);
154 --ebi;
155 }
156
157 flipflop = 0;
158
159 do {
160 while (getbit(ep, ebi) == 0) {
161 lmmp_sqrlo_n_(tp, dst, n, scratch);
162 LMMP_SWAP(dst, tp, mp_ptr);
163 flipflop = !flipflop;
164 if (--ebi == 0)
165 goto done;
166 }
167
168 /* The next bit of the exponent is 1. Now extract the largest block of
169 bits <= windowsize, and such that the least significant bit is 1. */
170
171 expbits = getbits(ep, ebi, windowsize);
172 this_windowsize = LMMP_MIN(windowsize, ebi);
173
174 ctz_shr_u64(expbits, expbits, cnt);
175 this_windowsize -= cnt;
176 ebi -= this_windowsize;
177
178 while (this_windowsize > 1) {
179 lmmp_sqrlo_n_(tp, dst, n, scratch);
180 lmmp_sqrlo_n_(dst, tp, n, scratch);
181 this_windowsize -= 2;
182 }
183
184 if (this_windowsize != 0)
185 lmmp_sqrlo_n_(tp, dst, n, scratch);
186 else {
187 LMMP_SWAP(dst, tp, mp_ptr);
188 flipflop = !flipflop;
189 }
190 lmmp_mullo_n_(dst, tp, pp + n * (expbits >> 1), n, scratch);
191 } while (ebi != 0);
192
193done:
194 if (flipflop)
195 lmmp_copy(tp, dst, n);
196 TEMP_FREE;
197}
static void lmmp_mullo_n_(mp_ptr restrict dst, mp_srcptr restrict numa, mp_srcptr restrict numb, mp_size_t n, mp_ptr restrict tp)
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define LMMP_SWAP(x, y, type)
交换两个变量的值
定义 lmmp.h:458
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
#define lmmp_debug_assert(x)
定义 lmmp.h:498
#define LMMP_MIN(l, o)
返回两个数中的较小值
定义 lmmp.h:450
#define lmmp_param_assert(x)
定义 lmmp.h:509
#define ctz_shr_u64(r, x, cnt)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define scratch
void lmmp_powlo_2_(mp_ptr dst, mp_srcptr bp, mp_srcptr ep, mp_size_t en)
计算 [bp,2]^[ep,en] mod B^2,并将结果写入 [dst,2](lmmp_powlo_ 的 2 limb 特化)
void lmmp_powlo_1_(mp_ptr dst, mp_srcptr bp, mp_srcptr ep, mp_size_t en)
计算 [bp,1]^[ep,en] mod B,并将结果写入 [dst,1](lmmp_powlo_ 的 1 limb 特化)
static mp_size_t win_size(mp_size_t eb)
定义 powlo.c:58
#define getbit(p, bi)
定义 powlo.c:65
static mp_bitcnt_t count_bits(mp_srcptr p, mp_size_t n)
定义 powlo.c:86
static mp_limb_t getbits(const mp_limb_t *p, mp_bitcnt_t bi, mp_bitcnt_t nbits)
定义 powlo.c:67
static void lmmp_sqrlo_n_(mp_ptr restrict dst, mp_srcptr restrict numa, mp_size_t n, mp_ptr restrict tp)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 powlo.c:31
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define TEMP_FREE
#define TALLOC_TYPE(n, type)

引用了 count_bits(), ctz_shr_u64, getbit, getbits(), lmmp_copy, lmmp_debug_assert, LMMP_MIN, lmmp_mullo_n_(), lmmp_param_assert, lmmp_powlo_(), lmmp_powlo_1_(), lmmp_powlo_2_(), lmmp_sqrlo_n_(), LMMP_SWAP, n, restrict, scratch, TALLOC_TYPE, TEMP_DECL, TEMP_FREE, tp , 以及 win_size().

函数调用图:

◆ lmmp_powlo_1_()

void lmmp_powlo_1_ ( mp_ptr restrict dst,
mp_srcptr restrict bp,
mp_srcptr restrict ep,
mp_size_t en )

在文件 powlo.c 第 208 行定义.

208 {
209 lmmp_param_assert(dst != NULL && bp != NULL && ep != NULL);
210 lmmp_param_assert(en > 0 && ep[en - 1] > 0);
211 mp_limb_t u = bp[0];
212 mp_bitcnt_t ebi = count_bits(ep, en);
213
214 /* 指数为 1:b mod B 即 [bp,1] 本身 */
215 if (ebi == 1) {
216 dst[0] = u;
217 return;
218 }
219
220 unsigned windowsize = win_size(ebi);
221 lmmp_debug_assert(windowsize < ebi);
222 mp_bitcnt_t cnt;
223 unsigned this_windowsize;
224 mp_limb_t expbits;
225 TEMP_DECL;
226 mp_ptr restrict pp = TALLOC_TYPE((mp_size_t)1 << (windowsize - 1), mp_limb_t);
227
228 pp[0] = u;
229 if (windowsize > 1) {
230 mp_limb_t b2 = u * u; /* b^2 mod B:u64 回绕乘 */
231 for (mp_size_t i = 1; i < ((mp_size_t)1 << (windowsize - 1)); i++)
232 pp[i] = pp[i - 1] * b2;
233
234 expbits = getbits(ep, ebi, windowsize);
235 ebi -= windowsize;
236
237 ctz_shr_u64(expbits, expbits, cnt);
238 ebi += cnt;
239
240 u = pp[expbits >> 1];
241 } else {
242 --ebi;
243 }
244
245 while (ebi != 0) {
246 while (getbit(ep, ebi) == 0) {
247 u *= u;
248 if (--ebi == 0)
249 goto done;
250 }
251
252 /* The next bit of the exponent is 1. Now extract the largest block of
253 bits <= windowsize, and such that the least significant bit is 1. */
254
255 expbits = getbits(ep, ebi, windowsize);
256 this_windowsize = LMMP_MIN(windowsize, ebi);
257
258 ctz_shr_u64(expbits, expbits, cnt);
259 this_windowsize -= cnt;
260 ebi -= this_windowsize;
261
262 while (this_windowsize > 1) {
263 u *= u;
264 u *= u;
265 this_windowsize -= 2;
266 }
267
268 if (this_windowsize != 0)
269 u *= u;
270 u *= pp[expbits >> 1];
271 }
272
273done:
274 dst[0] = u;
275 TEMP_FREE;
276}
#define b2

引用了 b2, count_bits(), ctz_shr_u64, getbit, getbits(), lmmp_debug_assert, LMMP_MIN, lmmp_param_assert, lmmp_powlo_1_(), restrict, TALLOC_TYPE, TEMP_DECL, TEMP_FREE , 以及 win_size().

函数调用图:

◆ lmmp_powlo_2_()

void lmmp_powlo_2_ ( mp_ptr restrict dst,
mp_srcptr restrict bp,
mp_srcptr restrict ep,
mp_size_t en )

在文件 powlo.c 第 278 行定义.

278 {
279 lmmp_param_assert(dst != NULL && bp != NULL && ep != NULL);
280 lmmp_param_assert(en > 0 && ep[en - 1] > 0);
281 u128 u = _u128load(bp);
282 mp_bitcnt_t ebi = count_bits(ep, en);
283
284 /* 指数为 1:b mod B^2 即 [bp,2] 本身 */
285 if (ebi == 1) {
286 _u128store(dst, u);
287 return;
288 }
289
290 unsigned windowsize = win_size(ebi);
291 lmmp_debug_assert(windowsize < ebi);
292 mp_bitcnt_t cnt;
293 unsigned this_windowsize;
294 mp_limb_t expbits;
295 TEMP_DECL;
296 u128* restrict pp = TALLOC_TYPE((mp_size_t)1 << (windowsize - 1), u128);
297
298 pp[0] = u;
299 if (windowsize > 1) {
300 u128 b2 = _umul128to128_(_u128high(u), _u128low(u), _u128high(u), _u128low(u)); /* b^2 mod B^2 */
301 for (mp_size_t i = 1; i < ((mp_size_t)1 << (windowsize - 1)); i++)
302 pp[i] = _umul128to128_(_u128high(pp[i - 1]), _u128low(pp[i - 1]), _u128high(b2), _u128low(b2));
303
304 expbits = getbits(ep, ebi, windowsize);
305 ebi -= windowsize;
306
307 ctz_shr_u64(expbits, expbits, cnt);
308 ebi += cnt;
309
310 u = pp[expbits >> 1];
311 } else {
312 --ebi;
313 }
314
315 while (ebi != 0) {
316 while (getbit(ep, ebi) == 0) {
317 u = _umul128to128_(_u128high(u), _u128low(u), _u128high(u), _u128low(u));
318 if (--ebi == 0)
319 goto done;
320 }
321
322 /* The next bit of the exponent is 1. Now extract the largest block of
323 bits <= windowsize, and such that the least significant bit is 1. */
324
325 expbits = getbits(ep, ebi, windowsize);
326 this_windowsize = LMMP_MIN(windowsize, ebi);
327
328 ctz_shr_u64(expbits, expbits, cnt);
329 this_windowsize -= cnt;
330 ebi -= this_windowsize;
331
332 while (this_windowsize > 1) {
333 u = _umul128to128_(_u128high(u), _u128low(u), _u128high(u), _u128low(u));
334 u = _umul128to128_(_u128high(u), _u128low(u), _u128high(u), _u128low(u));
335 this_windowsize -= 2;
336 }
337
338 if (this_windowsize != 0)
339 u = _umul128to128_(_u128high(u), _u128low(u), _u128high(u), _u128low(u));
340 u = _umul128to128_(_u128high(u), _u128low(u), _u128high(pp[expbits >> 1]), _u128low(pp[expbits >> 1]));
341 }
342
343done:
344 _u128store(dst, u);
345 TEMP_FREE;
346}
static __uint128_t _umul128to128_(uint64_t a_high, uint64_t a_low, uint64_t b_high, uint64_t b_low)

引用了 _umul128to128_(), b2, count_bits(), ctz_shr_u64, getbit, getbits(), lmmp_debug_assert, LMMP_MIN, lmmp_param_assert, lmmp_powlo_2_(), restrict, TALLOC_TYPE, TEMP_DECL, TEMP_FREE , 以及 win_size().

函数调用图:

◆ lmmp_sqrlo_n_()

void lmmp_sqrlo_n_ ( mp_ptr restrict dst,
mp_srcptr restrict numa,
mp_size_t n,
mp_ptr restrict tp )
inlinestatic

Copyright (C) 2026 HJimmyK (Jericho Knox)

This file is part of LMMP.

LMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.

SPDX-License-Identifier: LGPL-3.0-or-later

在文件 powlo.c 第 31 行定义.

36 {
37 if (n < MULLO_DC_THRESHOLD) {
38 lmmp_sqrlo_dc_(dst, numa, tp, n);
39 } else {
40 lmmp_mullo_fft_(dst, numa, numa, n, tp);
41 }
42}
void lmmp_sqrlo_dc_(mp_ptr dst, mp_srcptr numa, mp_ptr tp, mp_size_t n)
低位平方 [dst,n] = [numa,n]^2 mod B^n

引用了 lmmp_mullo_fft_(), lmmp_sqrlo_dc_(), lmmp_sqrlo_n_(), MULLO_DC_THRESHOLD, n, restrict , 以及 tp.

被这些函数引用 lmmp_powlo_() , 以及 lmmp_sqrlo_n_().

函数调用图:
这是这个函数的调用关系图:

◆ win_size()

mp_size_t win_size ( mp_size_t eb)
inlinestatic

在文件 powlo.c 第 58 行定义.

58 {
60 static mp_bitcnt_t x[] = {7, 25, 81, 241, 673, 1793, 4609, 11521, 28161, ~(mp_bitcnt_t)0};
61 for (k = 0; eb > x[k++];);
62 return k;
63}
#define k

引用了 k , 以及 win_size().

被这些函数引用 lmmp_powlo_(), lmmp_powlo_1_(), lmmp_powlo_2_() , 以及 win_size().

函数调用图:
这是这个函数的调用关系图: