-
Notifications
You must be signed in to change notification settings - Fork 14
/
bigint.go
169 lines (145 loc) · 3.62 KB
/
bigint.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
// Package bigint provides common functions for manipulating multi-precision integers.
package bigint
import (
"math/big"
"math/rand"
"strings"
)
// Zero returns 0.
func Zero() *big.Int {
return big.NewInt(0)
}
// One returns 1.
func One() *big.Int {
return big.NewInt(1)
}
// Hex constructs an integer from a hex string, returning the integer and a
// boolean indicating success. Underscore may be used as a separator.
func Hex(s string) (*big.Int, bool) {
return new(big.Int).SetString(stripliteral(s), 16)
}
// MustHex constructs an integer from a hex string. It panics on error.
func MustHex(s string) *big.Int {
x, ok := Hex(s)
if !ok {
panic("failed to parse hex integer")
}
return x
}
// Binary parses a binary string into an integer, returning the integer and a
// boolean indicating success. Underscore may be used as a separator.
func Binary(s string) (*big.Int, bool) {
return new(big.Int).SetString(stripliteral(s), 2)
}
// MustBinary constructs an integer from a binary string. It panics on error.
func MustBinary(s string) *big.Int {
x, ok := Binary(s)
if !ok {
panic("failed to parse binary integer")
}
return x
}
// stripliteral removes underscore spacers from a numeric literal.
func stripliteral(s string) string {
return strings.ReplaceAll(s, "_", "")
}
// Equal returns whether x equals y.
func Equal(x, y *big.Int) bool {
return x.Cmp(y) == 0
}
// EqualInt64 is a convenience for checking if x equals the int64 value y.
func EqualInt64(x *big.Int, y int64) bool {
return Equal(x, big.NewInt(y))
}
// IsZero returns true if x is zero.
func IsZero(x *big.Int) bool {
return x.Sign() == 0
}
// IsNonZero returns true if x is non-zero.
func IsNonZero(x *big.Int) bool {
return !IsZero(x)
}
// Clone returns a copy of x.
func Clone(x *big.Int) *big.Int {
return new(big.Int).Set(x)
}
// Pow2 returns 2ᵉ.
func Pow2(e uint) *big.Int {
return new(big.Int).Lsh(One(), e)
}
// IsPow2 returns whether x is a power of 2.
func IsPow2(x *big.Int) bool {
e := x.BitLen()
if e == 0 {
return false
}
return Equal(x, Pow2(uint(e-1)))
}
// Pow2UpTo returns all powers of two ⩽ x.
func Pow2UpTo(x *big.Int) []*big.Int {
p := One()
ps := []*big.Int{}
for p.Cmp(x) <= 0 {
ps = append(ps, Clone(p))
p.Lsh(p, 1)
}
return ps
}
// Mask returns the integer with 1s in positions [l,h).
func Mask(l, h uint) *big.Int {
mask := Pow2(h)
return mask.Sub(mask, Pow2(l))
}
// Ones returns 2ⁿ - 1, the integer with n 1s in the low bits.
func Ones(n uint) *big.Int {
return Mask(0, n)
}
// BitsSet returns the positions of set bits in x.
func BitsSet(x *big.Int) []int {
set := []int{}
for i := 0; i < x.BitLen(); i++ {
if x.Bit(i) == 1 {
set = append(set, i)
}
}
return set
}
// MinMax returns the minimum and maximum of x and y.
func MinMax(x, y *big.Int) (min, max *big.Int) {
if x.Cmp(y) < 0 {
return x, y
}
return y, x
}
// Extract bits [l,h) and shift them to the low bits.
func Extract(x *big.Int, l, h uint) *big.Int {
e := Mask(l, h)
e.And(e, x)
return e.Rsh(e, l)
}
// RandBits returns a random integer less than 2ⁿ.
func RandBits(r *rand.Rand, n uint) *big.Int {
max := Pow2(n)
return new(big.Int).Rand(r, max)
}
// Uint64s represents x in 64-bit limbs.
func Uint64s(x *big.Int) []uint64 {
z := Clone(x)
mask := Ones(64)
word := new(big.Int)
words := []uint64{}
for IsNonZero(z) {
word.And(z, mask)
words = append(words, word.Uint64())
z.Rsh(z, 64)
}
return words
}
// BytesLittleEndian returns the absolute value of x as a little-endian byte slice.
func BytesLittleEndian(x *big.Int) []byte {
b := x.Bytes()
for l, r := 0, len(b)-1; l < r; l, r = l+1, r-1 {
b[l], b[r] = b[r], b[l]
}
return b
}