В прошлой теме были рассмотрены общие моменты работы со стеком. Теперь посмотрим, как мы можем добавить работу со стеком в наш симулятор ассемблера, созданный в прошлых темах.
Прежде всего нам надо добавить две дополнительные инструкции - для добавления в стек и для извлечения из стека. В 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 Переполнение стека