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

浏览该文件的源代码.

宏定义

#define getbit(p, bi)
 Copyright (C) 2026 HJimmyK (Jericho Knox)

函数

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)
void lmmp_powmod_2_ (mp_ptr restrict dst, mp_srcptr restrict bp, mp_srcptr restrict ep, mp_size_t en, mp_srcptr restrict mod)
static u128 mont2_mul_2 (u128 a, u128 b, u128 n, u128 ninv)
static u128 mont2_redc (u128 thi, u128 tlo, u128 n, u128 ninv)
static u128 mont2_sqr (u128 a, u128 n, u128 ninv)
static void mul_128 (u128 a, u128 b, u128 *hi, u128 *lo)
static void sqr_128 (u128 a, u128 *hi, u128 *lo)

宏定义说明

◆ getbit

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

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

在文件 powmod_2.c 第 29 行定义.

函数说明

◆ count_bits()

mp_bitcnt_t count_bits ( mp_srcptr p,
mp_size_t n )
inlinestatic

在文件 powmod_2.c 第 50 行定义.

50 {
51 return (n - 1) * LIMB_BITS + lmmp_limb_bits_(p[n - 1]);
52}
#define lmmp_limb_bits_
#define n

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

函数调用图:

◆ getbits()

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

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

31 {
32 mp_bitcnt_t nbits_in_r;
33 mp_limb_t r;
34 mp_size_t i;
35
36 if (bi <= nbits) {
37 return p[0] & (((mp_limb_t)1 << bi) - 1);
38 } else {
39 bi -= nbits; /* bit index of low bit to extract */
40 i = bi / LIMB_BITS; /* word index of low bit to extract */
41 bi %= LIMB_BITS; /* bit index in low word */
42 r = p[i] >> bi; /* extract (low) bits */
43 nbits_in_r = LIMB_BITS - bi; /* number of bits now in r */
44 if (nbits_in_r < nbits) /* did we get enough bits? */
45 r += p[i + 1] << nbits_in_r; /* prepend bits from higher word */
46 return r & (((mp_limb_t)1 << nbits) - 1);
47 }
48}
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.

函数调用图:

◆ lmmp_powmod_2_()

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

在文件 powmod_2.c 第 159 行定义.

165 {
166 lmmp_param_assert(dst != NULL && bp != NULL && ep != NULL && mod != NULL);
167 lmmp_param_assert(en > 0 && ep[en - 1] > 0);
168 lmmp_param_assert(mod[0] % 2 == 1);
169 lmmp_param_assert(mod[1] != 0);
170
171 u128 n = _u128load(mod);
172 if (_u128load(bp) == 0) {
173 lmmp_zero(dst, 2);
174 return;
175 }
176 mp_bitcnt_t ebi = count_bits(ep, en);
177 /* 指数为 1:契约 [bp,2] < [mod,2],直接拷贝即已取模 */
178 if (ebi == 1) {
179 lmmp_copy(dst, bp, 2);
180 return;
181 }
182
183 unsigned windowsize = lmmp_powmod_win_size_(ebi);
184 lmmp_debug_assert(windowsize < ebi);
185 /* ninv = -m^(-1) mod B^2:u128 回绕取负 */
186 mp_limb_t inv[2];
187 lmmp_binvert_2_(inv, mod);
188 u128 ninv = 0 - _u128load(inv);
189
190 /* 进蒙域:x_m = b*B^2 mod m,一次 4/2 除法(低位补两个零 limb 实现 <<B^2) */
191 u128 u;
192 {
193 mp_limb_t num[4] = {0, 0, bp[0], bp[1]};
194 mp_limb_t r[2];
195 lmmp_div_(NULL, r, num, 4, mod, 2);
196 u = _u128load(r);
197 }
198
199 mp_bitcnt_t cnt;
200 unsigned this_windowsize;
201 mp_limb_t expbits;
202 TEMP_DECL;
203 u128* restrict pp = TALLOC_TYPE((mp_size_t)1 << (windowsize - 1), u128);
204
205 pp[0] = u;
206 if (windowsize > 1) {
207 u128 b2 = mont2_sqr(u, n, ninv);
208 for (mp_size_t i = 1; i < ((mp_size_t)1 << (windowsize - 1)); i++)
209 pp[i] = mont2_mul_2(pp[i - 1], b2, n, ninv);
210
211 expbits = getbits(ep, ebi, windowsize);
212 ebi -= windowsize;
213
214 ctz_shr_u64(expbits, expbits, cnt);
215 ebi += cnt;
216
217 u = pp[expbits >> 1];
218 } else {
219 --ebi;
220 }
221
222 while (ebi != 0) {
223 while (getbit(ep, ebi) == 0) {
224 u = mont2_sqr(u, n, ninv);
225 if (--ebi == 0)
226 goto done;
227 }
228
229 /* The next bit of the exponent is 1. Now extract the largest block of
230 bits <= windowsize, and such that the least significant bit is 1. */
231
232 expbits = getbits(ep, ebi, windowsize);
233 this_windowsize = LMMP_MIN(windowsize, ebi);
234
235 ctz_shr_u64(expbits, expbits, cnt);
236 this_windowsize -= cnt;
237 ebi -= this_windowsize;
238
239 while (this_windowsize > 1) {
240 u = mont2_sqr(u, n, ninv);
241 u = mont2_sqr(u, n, ninv);
242 this_windowsize -= 2;
243 }
244
245 if (this_windowsize != 0)
246 u = mont2_sqr(u, n, ninv);
247 u = mont2_mul_2(u, pp[expbits >> 1], n, ninv);
248 }
249
250done:
251 /* 出蒙域:REDC(u * 1) = u*B^(-2) mod m */
252 _u128store(dst, mont2_redc(0, u, n, ninv));
253 TEMP_FREE;
254}
static u128 mont2_mul_2(u128 a, u128 b, u128 n, u128 ninv)
static u128 mont2_redc(u128 thi, u128 tlo, u128 n, u128 ninv)
static u128 mont2_sqr(u128 a, u128 n, u128 ninv)
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
#define lmmp_zero(dst, n)
定义 lmmp.h:476
#define lmmp_debug_assert(x)
定义 lmmp.h:498
#define LMMP_MIN(l, o)
返回两个数中的较小值
定义 lmmp.h:450
#define lmmp_param_assert(x)
定义 lmmp.h:509
void lmmp_div_(mp_ptr dstq, mp_ptr dstr, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
除法和取模操作
定义 div.c:85
#define ctz_shr_u64(r, x, cnt)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define b2
void lmmp_binvert_2_(mp_ptr dst, mp_srcptr numa)
计算 [numa,2] 在 B^2 下的逆元
#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
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define TEMP_FREE
#define TALLOC_TYPE(n, type)

引用了 b2, count_bits(), ctz_shr_u64, getbit, getbits(), lmmp_binvert_2_(), lmmp_copy, lmmp_debug_assert, lmmp_div_(), LMMP_MIN, lmmp_param_assert, lmmp_powmod_2_(), lmmp_zero, mont2_mul_2(), mont2_redc(), mont2_sqr(), n, restrict, TALLOC_TYPE, TEMP_DECL , 以及 TEMP_FREE.

函数调用图:

◆ mont2_mul_2()

u128 mont2_mul_2 ( u128 a,
u128 b,
u128 n,
u128 ninv )
inlinestatic

在文件 powmod_2.c 第 153 行定义.

153 {
154 u128 h, l;
155 mul_128(a, b, &h, &l);
156 return mont2_redc(h, l, n, ninv);
157}
static void mul_128(u128 a, u128 b, u128 *hi, u128 *lo)

引用了 mont2_mul_2(), mont2_redc(), mul_128() , 以及 n.

函数调用图:

◆ mont2_redc()

u128 mont2_redc ( u128 thi,
u128 tlo,
u128 n,
u128 ninv )
inlinestatic

在文件 powmod_2.c 第 102 行定义.

102 {
103#if defined(LMMP_ASM_ARM64)
104 u128 q = tlo * ninv;
105 u128 qh, ql;
106 mul_128(q, n, &qh, &ql);
107 ulong t0 = _u128low(tlo), t1 = _u128high(tlo);
108 ulong p0 = _u128low(ql), p1 = _u128high(ql);
109 ulong k0 = (t0 + p0) < t0; /* lo 低 limb 进位(lo 值本身无消费者) */
110 ulong l1 = t1 + p1;
111 ulong k1 = l1 < t1;
112 l1 += k0;
113 k1 |= l1 < k0;
114 ulong h0 = _u128low(thi) + _u128low(qh);
115 ulong j0 = h0 < _u128low(qh);
116 h0 += k1;
117 j0 |= h0 < k1;
118 ulong h1 = _u128high(thi) + _u128high(qh);
119 ulong j1 = h1 < _u128high(qh);
120 h1 += j0;
121 j1 |= h1 < j0;
122 ulong n0 = _u128low(n), n1 = _u128high(n);
123 if (j1 || (h1 > n1) || (h1 == n1 && h0 >= n0)) {
124 ulong bw = h0 < n0; /* 借位跨 limb 传播 */
125 h0 -= n0;
126 h1 -= n1 + bw; /* j1 分支下回绕即真值 */
127 }
128 return ((u128)h1 << 64) | h0;
129#else
130 u128 q = tlo * ninv;
131 u128 qh, ql, lo, hi, c, c1, c2;
132 mul_128(q, n, &qh, &ql);
133 lo = tlo + ql;
134 c = lo < tlo;
135 hi = thi + qh;
136 c1 = hi < thi;
137 hi += c;
138 c2 = c && hi == 0;
139 if (c1 | c2)
140 hi -= n;
141 else if (hi >= n)
142 hi -= n;
143 return hi;
144#endif
145}
#define lo
#define c1
uint64_t ulong
定义 numth.h:39

引用了 c1, lo, mont2_redc(), mul_128() , 以及 n.

函数调用图:

◆ mont2_sqr()

u128 mont2_sqr ( u128 a,
u128 n,
u128 ninv )
inlinestatic

在文件 powmod_2.c 第 147 行定义.

147 {
148 u128 h, l;
149 sqr_128(a, &h, &l);
150 return mont2_redc(h, l, n, ninv);
151}
static void sqr_128(u128 a, u128 *hi, u128 *lo)

引用了 mont2_redc(), mont2_sqr(), n , 以及 sqr_128().

函数调用图:

◆ mul_128()

void mul_128 ( u128 a,
u128 b,
u128 * hi,
u128 * lo )
inlinestatic

在文件 powmod_2.c 第 56 行定义.

56 {
57#if defined(__clang__) && !defined(LMMP_ASM_ARM64)
58 ulong a0 = _u128low(a), a1 = _u128high(a);
59 ulong b0 = _u128low(b), b1 = _u128high(b);
60 u128 p00 = (u128)a0 * b0;
61 u128 p01 = (u128)a0 * b1;
62 u128 p10 = (u128)a1 * b0;
63 u128 p11 = (u128)a1 * b1;
64 u128 mid = p01 + p10;
65 u128 cm = mid < p01; /* 129 位交叉和进位,属 hi 的第 64 位 */
66 u128 l = (mid << 64) + p00;
67 u128 cl = l < p00; /* 进位属 hi 的第 0 位 */
68 *lo = l;
69 *hi = p11 + (mid >> 64) + cl + (cm << 64);
70#else
71 ulong u[4];
72 _umul128to256_(_u128high(a), _u128low(a), _u128high(b), _u128low(b), u);
73 *lo = ((u128)u[1] << 64) | u[0];
74 *hi = ((u128)u[3] << 64) | u[2];
75#endif
76}
static void _umul128to256_(uint64_t a_high, uint64_t a_low, uint64_t b_high, uint64_t b_low, uint64_t rr[4])
#define b0
#define b1
#define a0
#define a1

引用了 _umul128to256_(), a0, a1, b0, b1, lo , 以及 mul_128().

函数调用图:

◆ sqr_128()

void sqr_128 ( u128 a,
u128 * hi,
u128 * lo )
inlinestatic

在文件 powmod_2.c 第 79 行定义.

79 {
80#if defined(__clang__) && !defined(LMMP_ASM_ARM64)
81 ulong a0 = _u128low(a), a1 = _u128high(a);
82 u128 p0 = (u128)a0 * a0;
83 u128 m = (u128)a0 * a1; /* 交叉积,加倍后 129 位 */
84 u128 p1 = (u128)a1 * a1;
85 u128 ml = m << 1;
86 u128 mh = m >> 127; /* 加倍进位(0/1),属 hi 的第 64 位 */
87 u128 l = (ml << 64) + p0;
88 u128 cl = l < p0;
89 *lo = l;
90 *hi = p1 + (ml >> 64) + cl + (mh << 64);
91#else
92 ulong u[4];
93 _usqr128to256_(_u128high(a), _u128low(a), u);
94 *lo = ((u128)u[1] << 64) | u[0];
95 *hi = ((u128)u[3] << 64) | u[2];
96#endif
97}
static void _usqr128to256_(uint64_t a_high, uint64_t a_low, uint64_t rr[4])

引用了 _usqr128to256_(), a0, a1, lo , 以及 sqr_128().

函数调用图: