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
|
defpackage bigint2 :
import core
import verse
import firrtl/ir-utils
;============ Big Int Library =============
; d contains the Array<Int>, stored so the least significant word is at
; index 0.
;------------ Helper Functions ------------
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 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>()
for i in 0 to num-bits(b) by 4 do :
val word-index = i / 32
val bit-index = i % 32
val digit = (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)
public defmethod print (o:OutputStream, b:BigInt) :
print(o, to-string(b))
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 base = data[0]
val shamt = if base == 'b': 1 else if base == 'h': 4 else: 2
val digits = substring(data, 1)
val num-bits = length(digits) * shamt
BigIntLit(digits,shamt,num-bits)
public defn BigIntLit (digits:String, shamt:Int, num-bits:Int) -> BigInt :
val lit = BigIntZero(num-bits)
;; 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
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)
|
