forked from pydio/cells
-
Notifications
You must be signed in to change notification settings - Fork 0
/
nat.go
113 lines (98 loc) · 2.77 KB
/
nat.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
/*
* Copyright (c) 2018. Abstrium SAS <team (at) pydio.com>
* This file is part of Pydio Cells.
*
* Pydio Cells is free software: you can redistribute it and/or modify
* it under the terms of the GNU Affero General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* Pydio Cells 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 Affero General Public License for more details.
*
* You should have received a copy of the GNU Affero General Public License
* along with Pydio Cells. If not, see <http://www.gnu.org/licenses/>.
*
* The latest code can be found at <https://pydio.com>.
*/
// This file implements unsigned multi-precision integers (natural
// numbers). They are the building blocks for the implementation
// of signed integers, rationals, and floating-point numbers.
package utils
import (
"math/big"
)
const (
// Compute the size _S of a Word in bytes.
_m = ^big.Word(0)
_logS = _m>>8&1 + _m>>16&1 + _m>>32&1
_S = 1<<_logS - 1
_W = _S << 3 // word size in bits
_B = 1 << _W // digit base
_M = _B - 1 // digit mask
_W2 = _W / 2 // half word size in bits
_B2 = 1 << _W2 // half digit base
_M2 = _B2 - 1 // half digit mask
)
// An unsigned integer x of the form
//
// x = x[n-1]*_B^(n-1) + x[n-2]*_B^(n-2) + ... + x[1]*_B + x[0]
//
// with 0 <= x[i] < _B and 0 <= i < n is stored in a slice of length n,
// with the digits x[i] as the slice elements.
//
// A number is normalized if the slice contains no leading 0 digits.
// During arithmetic operations, denormalized values may occur but are
// always normalized before returning the final result. The normalized
// representation of 0 is the empty or nil slice (length = 0).
//
type Nat []big.Word
var (
natOne = Nat{1}
natTwo = Nat{2}
natTen = Nat{10}
)
func (z Nat) clear() {
for i := range z {
z[i] = 0
}
}
func (z Nat) norm() Nat {
i := len(z)
for i > 0 && z[i-1] == 0 {
i--
}
return z[0:i]
}
func (z Nat) make(n int) Nat {
if n <= cap(z) {
return z[:n] // reuse z
}
// Choosing a good value for e has significant performance impact
// because it increases the chance that a value can be reused.
const e = 4 // extra capacity
return make(Nat, n, n+e)
}
// setBytes interprets buf as the bytes of a big-endian unsigned
// integer, sets z to that value, and returns z.
func (z Nat) setBytes(buf []byte) Nat {
z = z.make((len(buf) + _S - 1) / _S)
k := 0
s := uint(0)
var d big.Word
for i := len(buf); i > 0; i-- {
d |= big.Word(buf[i-1]) << s
if s += 8; s == _S*8 {
z[k] = d
k++
s = 0
d = 0
}
}
if k < len(z) {
z[k] = d
}
return z.norm()
}