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
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
|
defpackage bigint2 :
import core
import verse
;============ Big Int Library =============
; d contains the Array<Int>, stored so the least significant word is at
; index 0.
;------------ Helper Functions ------------
public defn pow (x:Int,y:Int) -> Int :
var x* = 1
var y* = y
while y* != 0 :
x* = times(x*,x)
y* = minus(y*,1)
x*
public defn pow (x:Long,y:Long) -> Long :
var x* = to-long(1)
var y* = y
while y* != to-long(0) :
x* = times(x*,x)
y* = minus(y*,to-long(1))
x*
public defn to-int (x:Long) -> Int :
if x > to-long(2147483647) or x < to-long(-2147483648) : error("Long too big to convert to Int")
else : to-int(to-string(x))
public defn req-num-bits (i: Int) -> Int :
val i* =
if i < 0 : ((-1 * i) - 1)
else : i
ceil-log2(i* + 1) + 1
val word-size = 32
val all-digits = "0123456789abcdef"
defn as-digit (c: Char) -> Int :
index-of(all-digits, c) as Int
defn num-words (b:BigInt) : length(d(b))
defn shamt (c:Char) :
if c == 'b': 1
else if c == 'h': 4
else: error("Unsupported BigInt base.")
defn req-words (num-bits:Int) : (num-bits + word-size - 1) / word-size
defn to-hex (b:BigInt) -> String :
defn as-hex (i: Int) -> String : substring(all-digits,i,i + 1)
var li = List<String>()
val tib = num-bits(b) % 4
for i in 0 to num-bits(b) by 4 do :
val word-index = i / 32
val bit-index = i % 32
var mask = 15
val digit =
if (i + tib) == num-bits(b) :
(d(b)[word-index] >> bit-index) & (pow(2,tib) - 1)
else :
(d(b)[word-index] >> bit-index) & 15
li = List(as-hex(digit),li)
var saw-not-zero? = false
val li* = Vector<String>()
for i in 0 to length(li) do :
val x = li[i]
if saw-not-zero? == false and x == "0" and i < length(li) - 1 : false
else :
saw-not-zero? = true
add(li*,x)
string-join([ '\"' 'h' string-join(li*) '\"'])
defn to-bin (b:BigInt) -> String :
string-join $ generate<Char> :
defn* loop (pos:Int) :
if (pos >= 0) :
yield(if (d(b)[pos / 32] >> (pos % 32))&1 == 1: '1' else: '0')
loop(pos - 1)
loop(num-bits(b) - 1)
defn check-index (index:Int) -> False :
if index < 0 : error("Bit index cannot be negative")
false
defn check-bit (bit:Int) -> False :
if bit != 0 and bit != 1 : error("Cannot set a bit other than 0 or 1")
;------------ Library ----------------
public defstruct BigInt <: Gettable & Settable :
d : Array<Int>
num-bits : Int
with :
constructor => #BigInt
public defn BigInt (d:Array<Int>, num-bits:Int) :
check-index(num-bits)
if num-bits > length(d) * word-size :
error("Number of bits greater than size of BigInt")
val msw-index = req-words(num-bits) - 1
val msb-index = num-bits % word-size
;Zero out all bits above num-bits
if msb-index != 0 :
d[msw-index] = d[msw-index] & (2 ^ msb-index - 1)
for x in (msw-index + 1) to length(d) do :
d[msw-index] = 0
#BigInt(d,num-bits)
public defmethod get (b:BigInt, index:Int) -> Int :
check-index(index)
if index >= num-bits(b) : error("Bit index is too high")
val word-index = index / 32
val bit-index = index % 32
(d(b)[word-index] >> bit-index) & 1
defmethod set (b:BigInt, index:Int, bit:Int) -> False :
check-index(index)
check-bit(bit)
val word-index = index / 32
val bit-index = index % 32
d(b)[word-index] = ((bit & 1) << bit-index) | d(b)[word-index]
public defmethod to-string (b:BigInt) : to-hex(b)
;string-join([to-hex(b) "'" num-bits(b)])
public defmethod print (o:OutputStream, b:BigInt) :
print(o, to-string(b))
public defn req-num-bits (b:BigInt) -> Int :
var msb = 0
var seen? = false
for i in 0 to num-bits(b) do :
val index = num-bits(b) - 1 - i
if b[index] != 0 and seen? == false :
msb = index
seen? = true
msb + 1
public defn BigIntZero (num-bits:Int) -> BigInt :
val num-words = (num-bits + word-size - 1) / word-size
val d = Array<Int>(num-words)
for i in 0 to length(d) do :
d[i] = 0
BigInt(d,num-bits)
public defn BigIntLit (data:Int) -> BigInt :
BigIntLit(data,req-num-bits(data))
public defn BigIntLit (data:Int, num-bits:Int) -> BigInt :
val b = BigIntZero(num-bits)
d(b)[0] = data
b
public defn BigIntLit (data:String) -> BigInt :
val num-bits = (length(data) - 1) * shamt(data[0])
BigIntLit(data,num-bits)
public defn BigIntLit (data:String, num-bits:Int) -> BigInt :
val lit = BigIntZero(num-bits)
val digits = substring(data, 1)
;; println-all(["BASE " base " SHAMT " shamt " DIGITS " digits])
for i in 0 to num-words(lit) do :
d(lit)[i] = 0
for i in 0 to length(digits) do :
val off = (length(digits) - 1 - i) * shamt(data[0])
val wi = off / word-size
val bi = off % word-size
d(lit)[wi] = d(lit)[wi] | (as-digit(digits[i]) << bi)
;; println-all(["OFF " off " wi " wi " bi " bi " lit[wi] " lit[wi] " => " lit])
;; println-all(["RES = " lit])
lit
;------------------- Library API -----------------
;High is NOT inclusive
public defn bits (b:BigInt, high:Int, low:Int) -> BigInt :
check-index(high)
check-index(low)
if high <= low : error("High bit is less than or equal to low bit")
val b* = BigIntZero(high - low)
for i in 0 to num-bits(b*) do :
b*[i] = b[i + low]
b*
public defn bit (b:BigInt, index:Int) -> BigInt :
check-index(index)
val b* = BigIntZero(1)
b*[0] = b[index]
b*
public defn rsh (b:BigInt, amount:Int) -> BigInt :
check-index(amount)
bits(b,num-bits(b), amount)
|
