552 lines
18 KiB
Python
552 lines
18 KiB
Python
from collections import deque
|
|
|
|
from typing_extensions import Self
|
|
from lib.prettytable import PrettyTable
|
|
|
|
|
|
class BasicRegister:
|
|
"""
|
|
The BasicRegister represents a hardware register capable of manipulating multiple bits at a time.
|
|
|
|
:param deque[bool] memory: The bits stored inside the register.
|
|
"""
|
|
|
|
def __init__(self, memory: deque[bool]):
|
|
self.memory: deque[bool] = memory
|
|
|
|
def __repr__(self) -> str:
|
|
return "".join([str(int(value)) for value in self.memory])
|
|
|
|
def __str__(self) -> str:
|
|
return "".join([str(int(value)) for value in self.memory])
|
|
|
|
def __len__(self) -> int:
|
|
return len(self.memory)
|
|
|
|
def adjusted_by_size(self, resulting_size: int) -> Self:
|
|
"""
|
|
Adjusts a register to a given size.
|
|
|
|
:param int resulting_size: The size of the resulting register.
|
|
|
|
:return: A register of a specified size.
|
|
:rtype: BasicRegister
|
|
"""
|
|
current_memory_size: int = len(self.memory)
|
|
return BasicRegister(
|
|
deque([False] * max(resulting_size - current_memory_size, 0) + list(self.memory)[-resulting_size:])
|
|
)
|
|
|
|
def negate(self):
|
|
"""
|
|
Performs logical negation on the register.
|
|
"""
|
|
self.memory = deque([not value for value in self.memory])
|
|
|
|
def left_shift(self, shift_in_value: bool = False, bits_shifted: int = 1) -> deque[bool]:
|
|
"""
|
|
Shifts the register to the left by a specified number of steps.
|
|
|
|
:param bool shift_in_value: The value that shifts inside the freed space.
|
|
:param int bits_shifted: The number of bits by which the register is shifted.
|
|
|
|
:return: The bits shifted outside the register.
|
|
:rtype: deque[bool]
|
|
"""
|
|
self.memory.extend([shift_in_value] * bits_shifted)
|
|
shifted_bits: deque[bool] = deque([self.memory.popleft() for _i in range(bits_shifted)])
|
|
return shifted_bits
|
|
|
|
def right_shift(self, shift_in_value: bool = False, bits_shifted: int = 1) -> deque[bool]:
|
|
"""
|
|
Shifts the register to the right by a specified number of steps
|
|
|
|
:param bool shift_in_value: The value that shifts inside the freed space.
|
|
:param int bits_shifted: The number of bits by which the register is shifted.
|
|
|
|
:return: The bits shifted outside the register.
|
|
:rtype: deque[bool]
|
|
"""
|
|
self.memory.extendleft([shift_in_value] * bits_shifted)
|
|
shifted_bits: deque[bool] = deque([self.memory.pop() for _i in range(bits_shifted)])
|
|
return shifted_bits
|
|
|
|
|
|
class Counter(BasicRegister):
|
|
"""
|
|
The Counter represents a hardware register specifically designed for countdowns.
|
|
|
|
:param int value: Initial numeric value this Counter holds.
|
|
"""
|
|
|
|
def __init__(self, value: int):
|
|
# memory: deque[bool] = deque([i == "1" for i in bin(value)[2:]])
|
|
super().__init__(deque([i == "1" for i in bin(value)[2:]]))
|
|
# self.memory: deque[bool] = deque([i == "1" for i in bin(value)[2:]])
|
|
|
|
def __repr__(self) -> str:
|
|
return "".join([str(int(value)) for value in self.memory])
|
|
|
|
def __str__(self) -> str:
|
|
return "".join([str(int(value)) for value in self.memory])
|
|
|
|
def __len__(self) -> int:
|
|
return len(self.memory)
|
|
|
|
def decrement(self):
|
|
self.memory = binary_subtraction(self, BasicRegister(deque([False] * (len(self.memory) - 1) + [True]))).memory
|
|
|
|
def non_zero(self) -> bool:
|
|
return any(self.memory)
|
|
|
|
|
|
def negated(memory: deque[bool]) -> deque[bool]:
|
|
"""
|
|
Returns negated memory chunk.
|
|
|
|
:param deque[bool] memory: Memory chunk to be negated.
|
|
|
|
:return: Negated memory chunk.
|
|
:rtype: deque[bool]
|
|
"""
|
|
return deque([not value for value in memory])
|
|
|
|
|
|
def get_memory(variable_name: str) -> deque[bool]:
|
|
"""
|
|
Reads user input to be used as a memory array.
|
|
|
|
:param str variable_name: The name to be displayed in the input line.
|
|
|
|
:return: A list of boolean values read from user.
|
|
:rtype: list[bool]
|
|
"""
|
|
while True:
|
|
input_chars: list[str] = list(input(f"Enter {variable_name}: "))
|
|
|
|
if all(character in ["0", "1"] for character in input_chars):
|
|
return deque([True if character == "1" else False for character in input_chars])
|
|
else:
|
|
print(f"[ERROR] The {variable_name} may contain only 1-s and 0-s!")
|
|
|
|
|
|
def binary_sum_with_carry(first_term: BasicRegister, second_term: BasicRegister) -> tuple[BasicRegister, int]:
|
|
"""
|
|
Sums two registers' values and keeps the carry-out.
|
|
|
|
:param BasicRegister first_term: First register.
|
|
:param BasicRegister second_term: Second register.
|
|
|
|
:return: Register containing the sum and the carry-out bit.
|
|
:rtype: tuple[BasicRegister, int]
|
|
"""
|
|
result_term = BasicRegister(deque([False] * len(first_term)))
|
|
|
|
carry = False
|
|
for i in range(len(first_term) - 1, -1, -1):
|
|
current_bit_sum = first_term.memory[i] + second_term.memory[i] + carry
|
|
carry = bool(current_bit_sum & 2)
|
|
result_term.memory[i] = bool(current_bit_sum & 1)
|
|
|
|
return result_term, carry
|
|
|
|
|
|
def binary_sum(first_term: BasicRegister, second_term: BasicRegister) -> BasicRegister:
|
|
"""
|
|
Sums two terms containing binary numbers.
|
|
|
|
:param BasicRegister first_term: First register to add.
|
|
:param BasicRegister second_term: Second register to add.
|
|
|
|
:return: Register containing the sum.
|
|
:rtype: BasicRegister
|
|
"""
|
|
return binary_sum_with_carry(first_term, second_term)[0]
|
|
|
|
|
|
def binary_subtraction(minuend: BasicRegister, subtrahend: BasicRegister) -> BasicRegister:
|
|
"""
|
|
Subtracts the second term from the first in binary using ones' complement.
|
|
|
|
:param BasicRegister minuend: Register to subtract from.
|
|
:param BasicRegister subtrahend: Register to subtract by.
|
|
|
|
:return: Register containing the difference.
|
|
:rtype: BasicRegister
|
|
"""
|
|
subtrahend = BasicRegister(subtrahend.memory)
|
|
subtrahend.negate()
|
|
|
|
difference: BasicRegister
|
|
final_carry: bool
|
|
difference, final_carry = binary_sum_with_carry(minuend, subtrahend)
|
|
|
|
if final_carry:
|
|
return binary_sum(difference, BasicRegister(deque([False] * (len(difference) - 1) + [True])))
|
|
else:
|
|
difference.negate()
|
|
return difference
|
|
|
|
|
|
def binary_subtraction_second_complement(minuend: BasicRegister, subtrahend: BasicRegister) \
|
|
-> tuple[BasicRegister, bool]:
|
|
"""
|
|
Subtracts the second term from the first in binary using seconds' complement.
|
|
|
|
:param BasicRegister minuend: Register to subtract from.
|
|
:param BasicRegister subtrahend: Register to subtract by.
|
|
|
|
:return: Register containing the difference.
|
|
:rtype: BasicRegister
|
|
"""
|
|
subtrahend = BasicRegister(subtrahend.memory)
|
|
subtrahend.negate()
|
|
|
|
subtrahend = binary_sum(*align_registers(subtrahend, BasicRegister([True])))
|
|
|
|
difference: BasicRegister
|
|
final_carry: bool
|
|
difference, final_carry = binary_sum_with_carry(minuend, subtrahend)
|
|
|
|
return difference, final_carry
|
|
|
|
|
|
def align_registers(*registers: BasicRegister) -> tuple[BasicRegister, ...]:
|
|
"""
|
|
Aligns registers by the length of the bigger one.
|
|
|
|
:param BasicRegister registers: Registers to align.
|
|
|
|
:return: Aligned registers.
|
|
:rtype: tuple[BasicRegister, ...]
|
|
"""
|
|
required_size: int = max(map(len, registers))
|
|
return tuple(reg.adjusted_by_size(required_size) for reg in registers)
|
|
|
|
|
|
def format_device_state_table(table) -> str:
|
|
pt = PrettyTable()
|
|
pt.field_names = table[0]
|
|
|
|
for block in table[1:]:
|
|
for line in block[:-1]:
|
|
pt.add_row(line)
|
|
pt.add_row(block[-1], divider=True)
|
|
|
|
return pt.get_string()
|
|
|
|
|
|
def binary_multiplication_method_1(first_term: BasicRegister, second_term: BasicRegister) \
|
|
-> tuple[BasicRegister, list[list[str]]]:
|
|
"""
|
|
Multiplies two terms containing binary numbers using first method.
|
|
|
|
:param BasicRegister first_term: First register to multiply.
|
|
:param BasicRegister second_term: Second register to multiply.
|
|
|
|
:return: Register containing the product.
|
|
:rtype: BasicRegister
|
|
"""
|
|
first_term, second_term = align_registers(first_term, second_term)
|
|
n: int = len(first_term)
|
|
|
|
rg1 = BasicRegister(deque([False] * n))
|
|
rg2 = BasicRegister(first_term.memory)
|
|
rg3 = BasicRegister(second_term.memory)
|
|
ct = Counter(n)
|
|
|
|
data_table = [["iter", "RG1", "RG2", "RG3", "CT", "MicroOperations"]]
|
|
|
|
i = 0
|
|
data_table.append([])
|
|
data_table[-1].append(list(map(str, [i, rg1, rg2, rg3, ct, "-"])))
|
|
|
|
while ct.non_zero():
|
|
i += 1
|
|
data_table.append([])
|
|
|
|
if rg2.memory[n-1]:
|
|
rg1 = binary_sum(rg1, rg3)
|
|
data_table[-1].append(list(map(str, [i, rg1, rg2, rg3, ct, "RG1 := RG1 + RG3"])))
|
|
|
|
rg2.right_shift(rg1.memory[n-1])
|
|
rg1.right_shift()
|
|
ct.decrement()
|
|
|
|
data_table[-1].append(list(map(str, [i, rg1, rg2, rg3, ct, "RG2 := RG1[1].r(RG2)\nRG1 := 0.r(RG1)\nCT := CT - 1"])))
|
|
|
|
return BasicRegister(rg1.memory + rg2.memory), data_table
|
|
|
|
|
|
def binary_multiplication_method_2(first_term: BasicRegister, second_term: BasicRegister) \
|
|
-> tuple[BasicRegister, list[list[str]]]:
|
|
"""
|
|
Multiplies two terms containing binary numbers using second method.
|
|
|
|
:param BasicRegister first_term: First register to multiply.
|
|
:param BasicRegister second_term: Second register to multiply.
|
|
|
|
:return: Register containing the product.
|
|
:rtype: BasicRegister
|
|
"""
|
|
first_term, second_term = align_registers(first_term, second_term)
|
|
n: int = len(first_term)
|
|
|
|
rg1 = BasicRegister(deque([False] * (2*n)))
|
|
rg2 = BasicRegister(first_term.memory)
|
|
rg3 = BasicRegister(deque([False] * n + list(second_term.memory)))
|
|
|
|
i = 0
|
|
data_table = [["iter", "RG1", "RG2", "RG3", "MicroOperations"], []]
|
|
|
|
data_table[-1].append(list(map(str, [i, rg1, rg2, rg3, "-"])))
|
|
|
|
while any(rg2.memory):
|
|
i += 1
|
|
data_table.append([])
|
|
|
|
if rg2.memory[n-1]:
|
|
rg1 = binary_sum(rg1, rg3)
|
|
data_table[-1].append(list(map(str, [i, rg1, rg2, rg3, "RG1 := RG1 + RG3"])))
|
|
|
|
rg2.right_shift()
|
|
rg3.left_shift()
|
|
|
|
data_table[-1].append(list(map(str, [i, rg1, rg2, rg3, "RG2 := 0.r(RG2)\nRG3 := l(RG3).0"])))
|
|
|
|
return rg1, data_table
|
|
|
|
|
|
def binary_multiplication_method_3(first_term: BasicRegister, second_term: BasicRegister) \
|
|
-> tuple[BasicRegister, list[list[str]]]:
|
|
"""
|
|
Multiplies two terms containing binary numbers using third method.
|
|
|
|
:param BasicRegister first_term: First register to multiply.
|
|
:param BasicRegister second_term: Second register to multiply.
|
|
|
|
:return: Register containing the product.
|
|
:rtype: BasicRegister
|
|
"""
|
|
first_term, second_term = align_registers(first_term, second_term)
|
|
n: int = len(first_term)
|
|
|
|
data_table = [["iter", "RG2", "RG1", "RG3", "CT", "MicroOperations"]]
|
|
|
|
rg1 = BasicRegister(deque([False] * n))
|
|
rg2 = BasicRegister(first_term.memory + deque([False]))
|
|
rg3 = BasicRegister(deque([False] * (n+1)) + second_term.memory)
|
|
ct = Counter(n)
|
|
|
|
i = 0
|
|
data_table.append([])
|
|
data_table[-1].append(list(map(str, [i, rg2, rg1, rg3, ct, "-"])))
|
|
|
|
while ct.non_zero():
|
|
i += 1
|
|
data_table.append([])
|
|
|
|
if rg2.memory[0]:
|
|
result: list[bool] = list(binary_sum(BasicRegister(rg2.memory + rg1.memory), rg3).memory)
|
|
rg2 = BasicRegister(deque(result[:n+1]))
|
|
rg1 = BasicRegister(deque(result[n+1:]))
|
|
data_table[-1].append(list(map(str, [i, rg2, rg1, rg3, ct, "RG2.RG1 := RG2.RG1 + RG3"])))
|
|
|
|
rg2.left_shift(rg1.memory[0])
|
|
rg1.left_shift()
|
|
ct.decrement()
|
|
|
|
data_table[-1].append(list(map(str, [i, rg2, rg1, rg3, ct, "RG2.RG1 := l(RG2.RG1).0\nCT := CT - 1"])))
|
|
|
|
return BasicRegister(deque(list(rg2.memory + rg1.memory)[:-1])), data_table
|
|
|
|
|
|
def binary_multiplication_method_4(first_term: BasicRegister, second_term: BasicRegister) \
|
|
-> tuple[BasicRegister, list[list[str]]]:
|
|
"""
|
|
Multiplies two terms containing binary numbers using fourth method.
|
|
|
|
:param BasicRegister first_term: First register to multiply.
|
|
:param BasicRegister second_term: Second register to multiply.
|
|
|
|
:return: Register containing the product.
|
|
:rtype: BasicRegister
|
|
"""
|
|
first_term, second_term = align_registers(first_term, second_term)
|
|
n: int = len(first_term)
|
|
|
|
rg1 = BasicRegister(deque([False] * (2*n+1)))
|
|
rg2 = BasicRegister(first_term.memory)
|
|
rg3 = BasicRegister(deque([False]) + second_term.memory + deque([False] * n))
|
|
|
|
data_table = [["iter", "RG1", "RG2", "RG3", "MicroOperations"]]
|
|
|
|
i = 0
|
|
data_table.append([])
|
|
data_table[-1].append(list(map(str, [i, rg1, rg2, rg3, "-"])))
|
|
|
|
while any(rg2.memory):
|
|
i += 1
|
|
data_table.append([])
|
|
|
|
if rg2.memory[0]:
|
|
rg1 = binary_sum(rg1, rg3)
|
|
data_table[-1].append(list(map(str, [i, rg1, rg2, rg3, "RG1 := RG1 + RG3"])))
|
|
|
|
rg2.left_shift()
|
|
rg3.right_shift()
|
|
|
|
data_table[-1].append(list(map(str, [i, rg1, rg2, rg3, "RG2 := l(RG2).0\nRG3 := 0.r(RG3)"])))
|
|
|
|
return BasicRegister(deque(list(rg1.memory)[:-1])), data_table
|
|
|
|
def binary_division_method_1(first_term: BasicRegister, second_term: BasicRegister) \
|
|
-> tuple[BasicRegister, list[list[str]]]:
|
|
"""
|
|
Divides first term by the second term containing binary numbers using first method.
|
|
|
|
:param: BasicRegister first_term: Register being divided.
|
|
:param: BasicRegister second_term: Register being divided by.
|
|
|
|
:return: Register containing the division result.
|
|
:rtype: BasicRegister
|
|
"""
|
|
|
|
first_term, second_term = align_registers(first_term, second_term)
|
|
n: int = len(first_term)
|
|
|
|
rg1 = BasicRegister(deque([False, False]) + second_term.memory)
|
|
rg2 = BasicRegister(deque([False, False]) + first_term.memory)
|
|
rg3 = BasicRegister(deque([True] * (n+1)))
|
|
|
|
data_table = [["iter", "RG3", "RG2", "RG1", "MicroOperations"]]
|
|
i = 0
|
|
|
|
data_table.append([])
|
|
data_table[-1].append(list(map(str, [i, rg3, rg2, rg1, "-"])))
|
|
|
|
while rg3.memory[0]:
|
|
i += 1
|
|
data_table.append([])
|
|
|
|
if rg2.memory[0]:
|
|
rg2 = binary_sum(rg2, rg1)
|
|
data_table[-1].append(list(map(str, [i, rg3, rg2, rg1, "RG2 := RG2 + RG1"])))
|
|
else:
|
|
rg2, _ = binary_subtraction_second_complement(rg2, rg1)
|
|
data_table[-1].append(list(map(str, [i, rg3, rg2, rg1, "RG2 := RG2 - RG1"])))
|
|
|
|
rg3.left_shift(not rg2.memory[0])
|
|
rg2.left_shift()
|
|
data_table[-1].append(list(map(str, [i, rg3, rg2, rg1, f"RG3 := l(RG3).!RG2[{n+2}]\nRG2 := l(RG2).0"])))
|
|
|
|
return BasicRegister(deque(list(rg3.memory)[1:])), data_table
|
|
|
|
def binary_division_method_2(first_term: BasicRegister, second_term: BasicRegister) \
|
|
-> tuple[BasicRegister, list[list[str]]]:
|
|
"""
|
|
Divides first term by the second term containing binary numbers using second method.
|
|
|
|
:param: BasicRegister first_term: Register being divided.
|
|
:param: BasicRegister second_term: Register being divided by.
|
|
|
|
:return: Register containing the division result.
|
|
:rtype: BasicRegister
|
|
"""
|
|
|
|
first_term, second_term = align_registers(first_term, second_term)
|
|
n: int = len(first_term)
|
|
|
|
rg1 = BasicRegister(deque([False]) + second_term.memory + deque([False]*n))
|
|
rg2 = BasicRegister(deque([False]) + first_term.memory + deque([False]*n))
|
|
rg3 = BasicRegister(deque([True] * (n+1)))
|
|
|
|
data_table = [["iter", "RG3", "RG2", "RG1", "MicroOperations"]]
|
|
i = 0
|
|
carry = False
|
|
|
|
data_table.append([])
|
|
data_table[-1].append(list(map(str, [i, rg3, rg2, rg1, "-"])))
|
|
|
|
while rg3.memory[0]:
|
|
i += 1
|
|
data_table.append([])
|
|
|
|
if rg2.memory[0]:
|
|
rg2, carry = binary_sum_with_carry(rg2, rg1)
|
|
data_table[-1].append(list(map(str, [i, rg3, rg2, rg1, "RG2 := RG2 + RG1"])))
|
|
else:
|
|
rg2, carry = binary_subtraction_second_complement(rg2, rg1)
|
|
data_table[-1].append(list(map(str, [i, rg3, rg2, rg1, "RG2 := RG2 - RG1"])))
|
|
|
|
rg3.left_shift(carry)
|
|
rg1.right_shift()
|
|
data_table[-1].append(list(map(str, [i, rg3, rg2, rg1, f"RG3 := l(RG3).SM[p]\nRG1 := 0.r(RG1)"])))
|
|
|
|
return BasicRegister(deque(list(rg3.memory)[1:])), data_table
|
|
|
|
def binary_square_root(first_term: BasicRegister) \
|
|
-> tuple[BasicRegister, list[list[str]]]:
|
|
"""
|
|
Extracts the square root of first term.
|
|
|
|
:param: BasicRegister first_term: Register for square root extraction.
|
|
|
|
:return: Register containing the division result and the state table of a virtual
|
|
device that extracted the square root of the given term.
|
|
:rtype: tuple[BasicRegister, list[list[str]]]
|
|
"""
|
|
|
|
n: int = len(first_term)
|
|
i = 0
|
|
|
|
rga = BasicRegister(deque([False]*n))
|
|
rgb = BasicRegister(deque([False]*(n+2)))
|
|
rgc = BasicRegister(first_term.memory)
|
|
ct = Counter(n)
|
|
|
|
data_table = [["iter", "RGA", "RGB", "RGC", "CT", "MicroOperations"]]
|
|
|
|
data_table.append([])
|
|
data_table[-1].append(list(map(str, [i, rga, rgb, rgc, ct, "-"])))
|
|
|
|
# two initial shifts
|
|
rgb.left_shift(rgc.memory[0])
|
|
rgc.left_shift()
|
|
data_table[-1].append(list(map(str, [i, rga, rgb, rgc, ct, "RGB := l(RGB).RGC[0]\nRGC := l(RGC).0"])))
|
|
|
|
rgb.left_shift(rgc.memory[0])
|
|
rgc.left_shift()
|
|
data_table[-1].append(list(map(str, [i, rga, rgb, rgc, ct, "RGB := l(RGB).RGC[0]\nRGC := l(RGC).0"])))
|
|
|
|
# initial inverted addition
|
|
rgb = binary_sum(rgb, BasicRegister(negated(rga.memory) + deque([True, True])))
|
|
data_table[-1].append(list(map(str, [i, rga, rgb, rgc, ct, "RGB := RGB + !(RGA).11"])))
|
|
|
|
while ct.non_zero():
|
|
data_table.append([])
|
|
i += 1
|
|
|
|
rga.left_shift(not rgb.memory[0])
|
|
rgb.left_shift(rgc.memory[0])
|
|
rgc.left_shift()
|
|
|
|
data_table[-1].append(list(map(str, [i, rga, rgb, rgc, ct, "RGA := l(RGA).!(RGB[0])\nRGB := l(RGB).RGC[0]\nRGC := l(RGC).0"])))
|
|
|
|
rgb.left_shift(rgc.memory[0])
|
|
rgc.left_shift()
|
|
|
|
data_table[-1].append(list(map(str, [i, rga, rgb, rgc, ct, "RGB := l(RGB).RGC[0]\nRGC := l(RGC).0"])))
|
|
|
|
if rgb.memory[0]:
|
|
rgb = binary_sum(rgb, BasicRegister(rga.memory + deque([True, True])))
|
|
data_table[-1].append(list(map(str, [i, rga, rgb, rgc, ct, "RGB := RGB + RGA.11"])))
|
|
else:
|
|
rgb = binary_sum(rgb, BasicRegister(negated(rga.memory) + deque([True, True])))
|
|
data_table[-1].append(list(map(str, [i, rga, rgb, rgc, ct, "RGB := RGB + !(RGA).11"])))
|
|
|
|
ct.decrement()
|
|
data_table[-1].append(list(map(str, [i, rga, rgb, rgc, ct, "CT := CT - 1"])))
|
|
|
|
return rga, data_table
|