В прошлой теме были рассмотрены общие моменты работы со стеком. Теперь посмотрим, как мы можем добавить работу со стеком в наш симулятор ассемблера, созданный в прошлых темах.
Прежде всего нам надо добавить две дополнительные инструкции - для добавления в стек и для извлечения из стека. В Intel х86-64 это обычно инструкции PUSH и POP для добавления в стек и получения из стека соответственно.
push operand ; добавляем в стек значение из operand pop operand ; получаем из стека значение в operand
В ARM64 применяются инструкции STR(сохранение в стек) и LDR (получение из стека) с чуть более сложным синтаксисом:
STR Xn, [SP, #-N]! // Xn копируются в память по адресу SP – N, N - смещение относительно верхушки стека LDR Xn, [SP], #N // помещает данные из стека по адресу из регистра SP в регистр Xn
Стоит отметить, что в ARM64 число N должно быть кратно 16 байтам, то есть при каждом добавлении в стек мы можем занять в нем не меньше 16 байт. В Intel можно добавить в стек значения в 2 или 8 байт. У нас ограничение на размер не будет, так как все значения у нас по умолчанию размером 32 бита (4 байта).
В качестве названий инструкций возьмем мнемоники PUSH и POP как более распространенные и определим следующую программу:
instructions = [] # список инструкций
r = [0]*4 # значения 4 регистров
# карта сопоставления регистров и их индексов в списке r
regs32 = {"r0":0, "r1":1, "r2":2, "r3":3}
pc = 0 # указатель на следующую инструкцию
# флаги
c = 0 # флаг переноса
n = 0 # флаг знака
z = 0 # флан нуля
addr = 0 # адрес инструкции
sym_tab = {} # таблица символов
sp = 8 # указатель стека
stack = [0]*sp # условный стек
# поддерживаемые инструкции и их типы
# 1 - инструкции с 1 операндом - меткой
# 2 - инструкции с 2 операндами, где первый операнд - регистр, а второй - регистр или литерал
# 3 - инструкции с 3 операндами, где первый и второй операнды - регистр, а третий - регистр или литерал
# 4 - инструкции с 1 операндом, где операнд может быть регистром или литералом
# 5 - инструкции с 1 операндом, где операнд может быть регистром
mnemonics = {"b": (1,1), "beq":(1,1), "bne":(1,1), "mov":(2,2), "cmp":(2,2), "add": (3,3),
"sub":(3, 3), "and": (3,3), "orr": (3,3), "push": (4,1), "pop":(5,1)}
# считываем файл hello.s в список инструкций
with open("hello.s", "r", encoding="utf8") as source:
lines = source.readlines()
# обрабатываем строки из файла
for i in range(0,len(lines)):
lines[i] = lines[i].split("//")[0] \
.replace(",", " ") \
.strip().rstrip("\n") \
.lower()
while " " in lines[i]: # заменяем несколько пробелов одним
lines[i] = lines[i].replace(" ", " ")
if(lines[i]) == "": continue # если получилась пустая строка, переходим к следующей строке
tokens = lines[i].split(" ") # разбиваем инструкцию на токены
# если токен заканчивается на двоеточие, то это метка
if(tokens[0][-1]==":"):
label = tokens[0][:-1]
if(label in sym_tab):
print("Метка", label, "уже существует")
break
sym_tab[label] = addr # добавляем метку в таблицу символов
if(len(tokens)==1): continue # если инструкция на следующей строке, переходим к ней
else: tokens = tokens[1:] # получаем токены инструкции
instructions.append(tokens) # добавляем инструкцию в список instructions
addr = addr + 1 # увеличиваем указатель инструкций
# функций вывода состояния программы на консоль
def print_state(instruction):
print(f"pc:{pc}", end=" ") # выводим значение PC
print(f"{instruction:<15}", end=" ") # выводим текущую инструкцию
for reg in regs32: # выводим регистры
rInd = regs32[reg]
print(f"{reg}:0x{r[rInd]:04x}", end=" ")
print("\n" + " "*23 + f"c: {c} n: {n} z: {z}") # выводим флаги
print(" "*23 + "stack:", stack, "\tsp: ", sp) # выводим стек и sp
# получаем адрес, на который указывает метка
def get_label_addr(token):
if (token in sym_tab): return sym_tab[token]
print("Не найдена метка", token)
return None
# получаем индекс регистра
def get_register_index(token, show_error):
if (token in regs32): return regs32[token]
if show_error: print("Некорректный регистр", token)
return None
# получаем значение регистра
def get_register(token, show_error):
rInd = get_register_index(token, show_error)
if (rInd != None): return r[rInd]
return None
# получаем литерал
def get_literal(token):
try:
result = 0
if (token[0:2]=="0x"): result = int(token[2:],16) # если 16-ричное число
elif (token[0:2]=="0b"): result = int(token[2:],2) # если двоичное число
else: result= int(token)
return result & 0xffffffff # нормализуем литерал до 32 разрядов
except ValueError:
print("Некорректный токен", token)
return None
# получаем операнд, который может быть регистром или литералом
def get_register_or_literal(token):
reg = get_register(token, False)
if (reg != None): return reg
return get_literal(token)
# получаем тип инструкции
def get_opType(tokens):
if tokens[0] not in mnemonics: # проверяем корректность инструкции
print("Некорректная инструкция ", tokens[0])
return None
# получаем количество операндов для данной инструкции и ее тип
type, count = mnemonics[tokens[0]]
if count!= len(tokens[1:]): # проверяем количество операндов
print("Некорректное количество операндов для инструкции: ", tokens[0])
return None
return type
# цикл обработки инструкций
while True:
if pc >= len(instructions): break # если инструкции закончились, то выход из цикла
tokens = instructions[pc] # получаем текущую инструкцию для выполнения
pc = pc + 1 # увеличиваем указатель инструкций
opType = get_opType(tokens) # получаем количество операндов
if(opType == None): break
# получаем операнды
op1, op2, op3 = 0, 0, 0
# если 1-й операнд - метка
if(opType==1): op1 = get_label_addr(tokens[1])
# если 1-й операнд - регистр
if(opType in [2, 3, 5]): op1=get_register_index(tokens[1], True)
# если 1-й операнд - регистр или литерал (push)
if(opType==4): op1 = get_register_or_literal(tokens[1])
# если 2-й операнд - регистр или литерал
if(opType==2): op2 = get_register_or_literal(tokens[2])
# если 2-й операнд - регистр
# а 3-й операнд - регистр или литерал
if(opType==3):
op2 = get_register(tokens[2], True)
op3 = get_register_or_literal(tokens[3])
# если какой-то параметр не установлен, завершаем цикл
if(None in [op1, op2, op3]): break
result = 0
match tokens[0]:
case "mov":
result = op2
case "and":
result = op2 & op3
case "orr":
result = op2 | op3
case "add":
result = op2 + op3
# если сумма больше 32 разрядов, устанавливаем флаг переноса
if(result > 0xffffffff): c = 1
else: c=0
case "sub":
result = op2 - op3
if(op2 < op3): c = 1 # если идет заимствование, устанавливаем флаг переноса
else: c=0
case "cmp":
result = r[op1] - op2
if(r[op1] < op2): c = 1 # если идет заимствование, устанавливаем флаг переноса
else: c=0
case "b": # если безусловный переход
pc = op1 # адрес следующей инструкции берем из 1-го операнда
case "beq": # условный переход
if z==1: pc = op1 # если операнды равны
case "bne": # условный переход
if z==0: pc = op1 # если операнды НЕ равны
case "push": # добавляем в стек
if sp==0:
print("Переполнение стека")
break
sp = sp - 1 # уменьшаем указатель стека. стек указывает на следующее свободное место
stack[sp] = op1 # помещаем в стек данные
case "pop": # получаем из стека
if(sp >= len(stack)):
print("Нельзя получить данные из пустого стека") # если стек пуст
break
result = stack[sp] # получаем данные
sp = sp + 1 # увеличиваем адрес в стеке
result = result & 0xffffffff # нормализация значения до 32 разрядов
# установка флагов знака (n) и нуля (z)
if(tokens[0] not in ["mov", "b", "beq", "bne", "pop", "push"]):
# получаем флаг знака
n = (result >> 31)
# получаем флаг нуля
z = 1 if result == 0 else 0
# установка целевого регистра
if(tokens[0] not in ["cmp", "b", "beq", "bne", "push"]):
r[op1] = result
print_state(" ".join(tokens)) # логгируем состояние программы на консоль
Разберем измененные моменты. Прежде всего добавляем переменные для стека и указателя стека:
sp = 8 # указатель стека stack = [0]*sp # условный стек
В словаре мнемоник инструкций добавляем новые инструкции:
mnemonics = {"b": (1,1), "beq":(1,1), "bne":(1,1), "mov":(2,2), "cmp":(2,2), "add": (3,3),
"sub":(3, 3), "and": (3,3), "orr": (3,3), "push": (4,1), "pop":(5,1)}
Теперь каждой инструкции сопоставлен кортеж. Первый элемент кортежа - тип инструкции, а второй элемент - количество операндов инструкции. Тип инструкции позволяет определить, как получать операнды для этой инструкции. В данном случае мы будем использовать следующие типы:
1 - инструкции с 1 операндом - меткой
2 - инструкции с 2 операндами, где первый операнд - регистр, а второй - регистр или литерал
3 - инструкции с 3 операндами, где первый и второй операнды - регистр, а третий - регистр или литерал
4 - инструкции с 1 операндом, где операнд может быть регистром или литералом
5 - инструкции с 1 операндом, где операнд может быть регистром
Например, инструкция "push" имеет тип 4, то есть она принимает 1 операнд, который может быть или регистром, или литералом и который представляет добавляемое в стек значение. А инструкция "pop" имеет тип 5 и также принимает 1 операнд, но он может быть только регистром, в который помещается извлеченное из стека значение.
В функции get_opType проверяем количество операндов инструкции и возвращаем ее тип:
def get_opType(tokens):
...............................
# получаем количество операндов для данной инструкции и ее тип
type, count = mnemonics[tokens[0]]
if count!= len(tokens[1:]): # проверяем количество операндов
print("Некорректное количество операндов для инструкции: ", tokens[0])
return None
return type
Получив тип инструкции, получаем операнды в соответствии с этим типов. Например, инструкция добавления в стек - push имеет тип 4, где единственный операнд может быть регистром или литералом. Поэтому для его получения применяем функцию get_register_or_literal:
# если 1-й операнд - регистр или литерал (push) if(type==4): op1 = get_register_or_literal(tokens[1])
Если инструкция - "push", то добавляем в стек и инкрементируем адрес в sp:
case "push": # добавляем в стек
if sp==0:
print("Переполнение стека")
break
sp = sp - 1 # уменьшаем указатель стека. стек указывает на следующее свободное место
stack[sp] = op1 # помещаем в стек данные
Если инструкция - "pop", то получаем из стека в переменную result и уменьшаем адрес в sp:
case "pop": # получаем из стека
if(sp >= len(stack)):
print("Нельзя получить данные из пустого стека") # если стек пуст
break
result = stack[sp] # получаем данные
sp = sp + 1 # увеличиваем адрес в стеке
В функции print_state дополнительно выводим состояние стека и регистра sp.
Определим в файле "hello.s" следующий код на ассемблере:
mov r1, 4 // r1 = 4 push r1 // помещаем в стек число из r1 push 5 // помещаем в стек число 5 pop r0 // извлекаем из стека значение в r0 pop r3 // извлекаем из стека значение в r3
Запустим наш симулятор ассемблера:
pc:1 mov r1 4 r0:0x0000 r1:0x0004 r2:0x0000 r3:0x0000
c: 0 n: 0 z: 0
stack: [0, 0, 0, 0, 0, 0, 0, 0] sp: 8
pc:2 push r1 r0:0x0000 r1:0x0004 r2:0x0000 r3:0x0000
c: 0 n: 0 z: 0
stack: [0, 0, 0, 0, 0, 0, 0, 4] sp: 7
pc:3 push 5 r0:0x0000 r1:0x0004 r2:0x0000 r3:0x0000
c: 0 n: 0 z: 0
stack: [0, 0, 0, 0, 0, 0, 5, 4] sp: 6
pc:4 pop r0 r0:0x0005 r1:0x0004 r2:0x0000 r3:0x0000
c: 0 n: 0 z: 0
stack: [0, 0, 0, 0, 0, 0, 5, 4] sp: 7
pc:5 pop r3 r0:0x0005 r1:0x0004 r2:0x0000 r3:0x0004
c: 0 n: 0 z: 0
stack: [0, 0, 0, 0, 0, 0, 5, 4] sp: 8
И мы видим, как значение регистра r1 и число 5 помещаеются в стек и затем извлекаются в регистры r0 и r3. И также можем увидеть, как изменяется указатель sp.
Если мы попытаемся добавить в стек больше элементов, чем он может вместить, то мы получим ошибку переполнения стека. Например, пусть у нас есть следующая программа на ассемблере:
mov r1, 4 push 1 push 2 push 3 push 4 push 5 push 6 push 7 push 8 push 9
В этом случае мы получим следующий результат:
pc:1 mov r1 4 r0:0x0000 r1:0x0004 r2:0x0000 r3:0x0000
c: 0 n: 0 z: 0
stack: [0, 0, 0, 0, 0, 0, 0, 0] sp: 8
pc:2 push 1 r0:0x0000 r1:0x0004 r2:0x0000 r3:0x0000
c: 0 n: 0 z: 0
stack: [0, 0, 0, 0, 0, 0, 0, 1] sp: 7
pc:3 push 2 r0:0x0000 r1:0x0004 r2:0x0000 r3:0x0000
c: 0 n: 0 z: 0
stack: [0, 0, 0, 0, 0, 0, 2, 1] sp: 6
pc:4 push 3 r0:0x0000 r1:0x0004 r2:0x0000 r3:0x0000
c: 0 n: 0 z: 0
stack: [0, 0, 0, 0, 0, 3, 2, 1] sp: 5
pc:5 push 4 r0:0x0000 r1:0x0004 r2:0x0000 r3:0x0000
c: 0 n: 0 z: 0
stack: [0, 0, 0, 0, 4, 3, 2, 1] sp: 4
pc:6 push 5 r0:0x0000 r1:0x0004 r2:0x0000 r3:0x0000
c: 0 n: 0 z: 0
stack: [0, 0, 0, 5, 4, 3, 2, 1] sp: 3
pc:7 push 6 r0:0x0000 r1:0x0004 r2:0x0000 r3:0x0000
c: 0 n: 0 z: 0
stack: [0, 0, 6, 5, 4, 3, 2, 1] sp: 2
pc:8 push 7 r0:0x0000 r1:0x0004 r2:0x0000 r3:0x0000
c: 0 n: 0 z: 0
stack: [0, 7, 6, 5, 4, 3, 2, 1] sp: 1
pc:9 push 8 r0:0x0000 r1:0x0004 r2:0x0000 r3:0x0000
c: 0 n: 0 z: 0
stack: [8, 7, 6, 5, 4, 3, 2, 1] sp: 0
Переполнение стека