-
Notifications
You must be signed in to change notification settings - Fork 0
/
arithmetic.py
185 lines (138 loc) · 4.72 KB
/
arithmetic.py
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
from gates import NOT, NOT16, AND16, OR16WAY, XOR, AND, MUX16
from typing import Tuple
from utils import is_n_bit_vector
ZERO16 = (False,) * 16
def HALFADDER(x: bool, y: bool) -> tuple[bool, bool]:
"""Adds up 2 bits."""
# pre-conditions
assert isinstance(x, bool)
assert isinstance(y, bool)
# body
s = XOR(x, y)
carry = AND(x, y)
out = s, carry
# post-conditions
assert is_n_bit_vector(out, n=2)
return out
def FULLADDER(x: bool, y: bool, carry: bool) -> tuple[bool, bool]:
"""Adds up 3 bits."""
# pre-conditions
assert isinstance(x, bool)
assert isinstance(y, bool)
assert isinstance(carry, bool)
# body
fst_sum, fst_carry = HALFADDER(x, y)
snd_sum, snd_carry = HALFADDER(fst_sum, carry)
new_sum = snd_sum
new_carry = fst_carry or snd_carry
out = new_sum, new_carry
# post-conditions
assert is_n_bit_vector(out, n=2), "Output must be 2-tuple of `bool`s"
return out
def ADD16(xs: tuple[bool, ...], ys: tuple[bool, ...]) -> tuple[bool, ...]:
"""Adds up two 16-bit two's complement numbers. Overflow is ignored."""
# pre-conditions
assert is_n_bit_vector(xs, n=16), "`x` must be a 16-tuple of `bool`s"
assert is_n_bit_vector(ys, n=16), "`y` must be a 16-tuple of `bool`s"
# body
out, carry = [False] * 16, False
for i, (x, y) in enumerate(zip(xs[::-1], ys[::-1])):
out[i], carry = FULLADDER(x, y, carry)
out = tuple(out[::-1]) # type: ignore
# post-conditions
assert is_n_bit_vector(out, n=16), "`out` must be a 16-tuple of `bool`s"
return out # type: ignore
def INC16(xs: tuple[bool, ...]) -> tuple[bool, ...]:
"""Adds 1 to input. Overflow is ignored."""
# pre-conditions
assert is_n_bit_vector(xs, n=16), "`xs` must be a 16-tuple of `bool`s"
# body
one = (False,) * 15 + (True,)
out = ADD16(xs, one)
# post-conditions
assert is_n_bit_vector(out, n=16), "`out` must be a 16-tuple of `bool`s"
return out
def NEG16(xs: tuple[bool, ...]) -> tuple[bool, ...]:
"""Negates input."""
# pre-conditions
assert is_n_bit_vector(xs, n=16), "`xs` must be a 16-tuple of `bool`s"
# body
out = INC16(NOT16(xs))
# post-conditions
assert is_n_bit_vector(out, n=16), "`out` must be a 16-tuple of `bool`s"
return out
def _PRESET16(xs: tuple[bool, ...], zx: bool, nx: bool) -> tuple[bool, ...]:
"""Prepares input for ALU. Zeroes out input if `zx` is `True` then negates input if `nx` is `True`."""
# pre-conditions
assert is_n_bit_vector(xs, n=16), "`xs` must be a 16-tuple of `bool`s"
assert isinstance(zx, bool), "`zx` must be a `bool`"
assert isinstance(nx, bool), "`nx` must be a `bool`"
# body
zeroed = MUX16(
xs,
ZERO16,
zx,
)
out = MUX16(
zeroed,
NOT16(zeroed),
nx,
)
# post-conditions
assert is_n_bit_vector(out, n=16), "`out` must be a 16-tuple of `bool`s"
return out
def ALU(
xs: tuple[bool, ...],
ys: tuple[bool, ...],
zx: bool,
nx: bool,
zy: bool,
ny: bool,
f: bool,
no: bool,
) -> tuple[tuple[bool, ...], bool, bool]:
"""
Performs arithmetic and logic operations on two 16-bit two's complement numbers. Overflow is ignored.
Args:
xs: 16-bit two's complement number
ys: 16-bit two's complement number
zx: if True, `xs` is set to 0
nx: if True, `xs` is negated
zy: if True, `ys` is set to 0
ny: if True, `ys` is negated
f: if True, `xs` and `ys` are added, otherwise they're anded
no: if True, the output is negated
Returns:
out: 16-bit two's complement number
zr: if True, `out` is 0
ng: if True, `out` is negative
"""
# pre-conditions
assert is_n_bit_vector(xs, n=16), "`xs` must be a 16-tuple of `bool`s"
assert is_n_bit_vector(ys, n=16), "`ys` must be a 16-tuple of `bool`s"
assert isinstance(zx, bool), "`zx` must be a `bool`"
assert isinstance(nx, bool), "`nx` must be a `bool`"
assert isinstance(zy, bool), "`zy` must be a `bool`"
assert isinstance(ny, bool), "`ny` must be a `bool`"
assert isinstance(f, bool), "`f` must be a `bool`"
assert isinstance(no, bool), "`no` must be a `bool`"
# body
tx = _PRESET16(xs, zx, nx)
ty = _PRESET16(ys, zy, ny)
out = MUX16(
AND16(tx, ty),
ADD16(tx, ty),
f,
)
tout = MUX16(
out,
NOT16(out),
no,
)
zr = NOT(OR16WAY(tout))
ng = tout[0]
# post-conditions
assert is_n_bit_vector(out, n=16), "`out` must be a 16-tuple of `bool`s"
assert isinstance(zr, bool), "`zr` must be a `bool`"
assert isinstance(ng, bool), "`ng` must be a `bool`"
return tout, zr, ng