LMMP
4.3.0
Lamina High-Precision Arithmetic Library
Toggle main menu visibility
载入中...
搜索中...
未找到
tiny.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/longlong.h
"
24
#include "
lmmp/lmmpn.h
"
25
#include "
lmmp/numth.h
"
26
27
28
int
lmmp_limb_bits_
(
mp_limb_t
x) {
29
int
k
= 0;
30
while
(x) {
31
x >>= 1;
32
k
++;
33
}
34
return
k
;
35
}
36
37
int
lmmp_limb_popcnt_
(
mp_limb_t
x) {
38
#if defined(__GNUC__) || defined(__clang__)
39
mp_limb_t
count;
40
#if defined(LMMP_ASM_X64)
41
__asm__
volatile
(
"popcnt %1, %0"
:
"=r"
(count) :
"r"
(x) :
"cc"
);
42
#else
43
count = __builtin_popcountll(x);
44
#endif
45
return
count;
46
#else
47
int
k
= 0;
48
while
(x) {
49
k
+= x & 1;
50
x >>= 1;
51
}
52
return
k
;
53
#endif
54
}
55
56
int
lmmp_leading_zeros_
(
mp_limb_t
x) {
57
if
(x == 0)
return
64;
58
#ifdef __GNUC__
59
return
__builtin_clzll(x);
60
#else
61
int
n
= 0;
62
if
(x <= 0x00000000FFFFFFFF) {
n
+= 32; x <<= 32; }
63
if
(x <= 0x0000FFFFFFFFFFFF) {
n
+= 16; x <<= 16; }
64
if
(x <= 0x00FFFFFFFFFFFFFF) {
n
+= 8; x <<= 8; }
65
if
(x <= 0x0FFFFFFFFFFFFFFF) {
n
+= 4; x <<= 4; }
66
if
(x <= 0x3FFFFFFFFFFFFFFF) {
n
+= 2; x <<= 2; }
67
if
(x <= 0x7FFFFFFFFFFFFFFF) {
n
+= 1; x <<= 1; }
68
return
n
;
69
#endif
70
}
71
72
int
lmmp_tailing_zeros_
(
mp_limb_t
x) {
73
if
(x == 0)
return
64;
74
#ifdef __GNUC__
75
return
__builtin_ctzll(x);
76
#else
77
int
n
= 0;
78
if
((x & 0x00000000FFFFFFFF) == 0) {
n
+= 32; x >>= 32; }
79
if
((x & 0x000000000000FFFF) == 0) {
n
+= 16; x >>= 16; }
80
if
((x & 0x00000000000000FF) == 0) {
n
+= 8; x >>= 8; }
81
if
((x & 0x000000000000000F) == 0) {
n
+= 4; x >>= 4; }
82
if
((x & 0x0000000000000003) == 0) {
n
+= 2; x >>= 2; }
83
if
((x & 0x0000000000000001) == 0) {
n
+= 1; x >>= 1; }
84
return
n
;
85
#endif
86
}
87
88
mp_limb_t
lmmp_mulh_
(
mp_limb_t
a,
mp_limb_t
b) {
89
#if (defined(__GNUC__) || defined(__clang__)) && defined(__SIZEOF_INT128__)
90
__uint128_t
t
= (__uint128_t)a * (__uint128_t)b;
91
return
(
mp_limb_t
)(
t
>> 64);
92
#else
93
uint64_t ah = a >> 32, bh = b >> 32;
94
a = (uint32_t)a, b = (uint32_t)b;
95
uint64_t
r0
= a * b,
r1
= a * bh,
r2
= ah * b,
r3
= ah * bh;
96
r3
+= (
r1
>> 32) + (
r2
>> 32);
97
r1
= (uint32_t)
r1
,
r2
= (uint32_t)
r2
;
98
r1
+=
r2
;
99
r1
+= (
r0
>> 32);
100
return
r3
+ (
r1
>> 32);
101
#endif
102
}
103
104
void
lmmp_mullh_
(
mp_limb_t
a,
mp_limb_t
b,
mp_ptr
restrict
dst) {
105
#if (defined(__GNUC__) || defined(__clang__)) && defined(__SIZEOF_INT128__)
106
__uint128_t
prod
= (__uint128_t)a * b;
107
dst[0] = (
mp_limb_t
)
prod
;
108
dst[1] = (
mp_limb_t
)(
prod
>> 64);
109
#else
110
uint64_t ah = a >> 32, bh = b >> 32;
111
a = (uint32_t)a, b = (uint32_t)b;
112
uint64_t
r0
= a * b,
r1
= a * bh,
r2
= ah * b,
r3
= ah * bh;
113
r3
+= (
r1
>> 32) + (
r2
>> 32);
114
r1
= (uint32_t)
r1
,
r2
= (uint32_t)
r2
;
115
r1
+=
r2
;
116
r1
+= (
r0
>> 32);
117
dst[1] =
r3
+ (
r1
>> 32);
118
dst[0] = (
r1
<< 32) | (uint32_t)
r0
;
119
#endif
120
}
121
122
ulong
lmmp_mulmod_ulong_
(
ulong
a,
ulong
b,
ulong
mod,
ulongp
restrict
q) {
123
int
shl =
lmmp_leading_zeros_
(mod);
124
mod <<= shl;
125
ulong
inv =
lmmp_inv_1_
(mod);
126
u128 ab = (u128)a * b;
127
ulong
r;
128
if
(shl > 0)
129
ab <<= shl;
130
_udiv_qrnnd_preinv
(*q, r, _u128high(ab), _u128low(ab), mod, inv);
131
return
r >> shl;
132
}
k
#define k
prod
#define prod
lmmp_limb_bits_
#define lmmp_limb_bits_
定义
inlines.h:164
lmmp_leading_zeros_
#define lmmp_leading_zeros_
定义
inlines.h:162
lmmp_mullh_
#define lmmp_mullh_
定义
inlines.h:166
lmmp_limb_popcnt_
#define lmmp_limb_popcnt_
定义
inlines.h:165
lmmp_tailing_zeros_
#define lmmp_tailing_zeros_
定义
inlines.h:163
lmmp_mulh_
#define lmmp_mulh_
定义
inlines.h:167
mp_ptr
mp_limb_t * mp_ptr
定义
lmmp.h:96
mp_limb_t
uint64_t mp_limb_t
定义
lmmp.h:92
lmmpn.h
lmmp_inv_1_
mp_limb_t lmmp_inv_1_(mp_limb_t x)
1阶逆元计算 (inv1)
定义
inv.c:124
longlong.h
_udiv_qrnnd_preinv
#define _udiv_qrnnd_preinv(q, r, nh, nl, d, di)
定义
longlong.h:596
r2
#define r2
r1
#define r1
r3
#define r3
r0
#define r0
t
#define t
n
#define n
numth.h
ulongp
uint64_t * ulongp
定义
numth.h:48
lmmp_mulmod_ulong_
ulong lmmp_mulmod_ulong_(ulong a, ulong b, ulong mod, ulongp q)
计算两个无符号整数的乘积,对mod取模,商放入 q 中
ulong
uint64_t ulong
定义
numth.h:39
restrict
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
test_powmod.c:35
src
lmmp
lmmpn
arch
generic
tiny.c
生成于
, 为 LMMP使用
1.18.0