книги / Математическая логика и теория алгоритмов. Анализ алгоритмов
.pdfПродолжение табл. 3.5
Название |
Мнемокод |
КОП |
Байт |
Циклов |
Операция |
6.Переход,если |
JNZrel |
01.110.000 |
2 |
2 |
ЕслиА≠0, |
аккумуляторне |
|
xx.xxx.xxx |
|
|
то(РС)←(РС)+rel |
равеннулю |
|
|
|
|
иначе(РС)←(РС)+2 |
7.Переход,если |
JСrel |
01.000.000 |
2 |
2 |
ЕслиС=1, |
переносравен |
|
xx.xxx.xxx |
|
|
то(РС)←(РС)+rel |
единице |
|
|
|
|
иначе(РС)←(РС)+2 |
8.Переход,если |
JNСrel |
01.010.000 |
2 |
2 |
ЕслиС=0, |
переносравен |
|
xx.xxx.xxx |
|
|
то(РС)←(РС)+rel |
нулю |
|
|
|
|
иначе(РС)←(РС)+2 |
9.Переход,если |
JВbit,rel |
00.100.000 |
3 |
2 |
Если(b)=1, |
битравенединице |
|
xx.xxx.xxx |
|
|
то(РС)←(РС)+rel |
|
|
xx.xxx.xxx |
|
|
иначе(РС)←(РС)+3 |
10.Переход,если |
JNВbit,rel |
00.110.000 |
3 |
2 |
Если(b)=0, |
битравеннулю |
|
xx.xxx.xxx |
|
|
то(РС)←(РС)+rel |
|
|
xx.xxx.xxx |
|
|
иначе(РС)←(РС)+3 |
11.Переход,если |
JВСbit,rel |
00.010.000 |
3 |
2 |
Если(b)=1, |
битустановлен |
|
xx.xxx.xxx |
|
|
то(РС)←(РС)+rel |
споследующим |
|
xx.xxx.xxx |
|
|
и(b)←0иначе(РС) |
сбросомбита |
|
|
|
|
←(РС)+3 |
12.Декремент |
DJNZRn,rel |
11.011.rrr |
2 |
2 |
(РС)←(РС)+2, |
регистраипере- |
|
xx.xxx.xxx |
|
|
(Rn)←(Rn)–1, |
ход,еслиненоль |
|
|
|
|
если(Rn)≠0, |
|
|
|
|
|
то(РС)←(РС)+rel |
13.Декремент |
DJNZad,rel |
11.010.101 |
3 |
2 |
(РС)←(РС)+2, |
прямоадресуемо- |
|
xx.xxx.xxx |
|
|
(ad)←(ad)–1, |
гобайтаипере- |
|
xx.xxx.xxx |
|
|
если(ad)≠0, |
ход,еслиненоль |
|
|
|
|
то(РС)←(РС)+rel |
14. Сравнение |
СJNЕА, |
10.110.101 |
3 |
2 |
(РС)←(РС)+3, |
аккумулятора |
ad, rel |
xx.xxx.xxx |
|
|
если(А)≠(ad), |
с прямоадре- |
|
xx.xxx.xxx |
|
|
то(РС)←(РС)+rel |
суемым байтом |
|
|
|
|
если(А)<(ad), |
и переход, если |
|
|
|
|
то(С)←1, |
не равно |
|
|
|
|
иначе(С)←0 |
15.Сравнение |
СJNЕА,#d, |
10.110.100 |
3 |
2 |
(РС)←(РС)+3, |
аккумулятора |
rel |
xx.xxx.xxx |
|
|
если(А)≠#d,то(РС) |
сконстантой |
|
xx.xxx.xxx |
|
|
←(РС)+rel |
ипереход,если |
|
|
|
|
если(А)<#d, |
неравно |
|
|
|
|
то(С)←1, |
|
|
|
|
|
иначе(С)←0 |
61
Окончание табл. 3.5
Название |
Мнемокод |
КОП |
Байт |
Циклов |
Операция |
16. Абсолютный |
АCALLad11 |
а10а9.а810.0 |
2 |
2 |
(РС)←(РС)+2, |
вызовподпро- |
|
01 |
|
|
(SP)←(SP)+1 |
граммывпреде- |
|
а7а6.а5а4а3.а |
|
|
((SP))←(РС0–7) |
лахстраницы |
|
2а1а0 |
|
|
(SP)←(SP)+1 |
2Кбайта |
|
|
|
|
((SP))←(РС8–15) |
|
|
|
|
|
(РС0–10)←ad11 |
17.Возвратиз |
RET |
00.100.010 |
1 |
2 |
(РС8–15)←((SP)) |
подпрограммы |
|
|
|
|
(SP)←(SP)–1 |
|
|
|
|
|
(РС0–7)←((SP)) |
|
|
|
|
|
(SP)←(SP)–1 |
18.Возвратиз |
RETI |
00.110.010 |
1 |
2 |
(РС8–15)←((SP)) |
подпрограммы |
|
|
|
|
(SP)←(SP)–1 |
обработкипре- |
|
|
|
|
(РС0–7)←((SP)) |
рывания |
|
|
|
|
(SP)←(SP)–1 |
|
|
|
|
|
разрешениепрерыва- |
|
|
|
|
|
нияобслуживаемого |
|
|
|
|
|
уровня |
19.Холостая |
NOP |
00.000.000 |
1 |
1 |
(РС)←(РС)+1 |
команда |
|
|
|
|
|
Таким образом, используя подобные таблицы, можно подсчитать объём памяти, занимаемый программой на языке Ассемблер,числомашинныхциклов, необходимыхдляеёвыполнения.
Конечно, помимо команд в программе на языке Ассемблер имеются и другие выражения, например, метки, директивы, комментарии и пр., но на всех особенностях этого языка мы сейчас останавливаться не будем.
Остановимся только на записи чисел: 011101b, 1011100B – двоичные, бинарные числа (b или B); 735Q, 456o, 457О – восьмеричные числа (q, Q или о, О); 256 – десятичное число (система счисления не указывается – по умолчанию десятеричная); 0fah, 0CBH – шестнадцатеричные числа (h, H).
Число всегда начинается с цифры. Это необходимо для того, чтобы отличать шестнадцатеричное число от так называемого идентификатора: ADCH – идентификатор, 0ADCH – число.
62
Приведём простой пример «незавершающейся» программы для ввода информации с порта Р1 микроконтроллера 8051 и вывода ее на порты Р0, Р2, Р3 (рис. 3.2).
Рис.3.2.ПростейшаяпрограмманаязыкеASM51
Следует подчеркнуть, что шестнадцатеричные номера (адреса) портов такие: Р0 = 80Н, Р1 = 90Н, Р2 = 0А0Н, Р3 = 0В0Н. В конце программы пишем END, хотя он и недостижим (программа циклическая, работает непрерывно). Если бы мы вначале определили соответствие символических имен портов с их адресами, то можно было бы и писать в дальнейшем эти символические адреса, Ассемблер поймёт.
После написания программы ее необходимо откомпилировать, то есть получить объектный код. Это выполняется с помощью командного файла соответствующего компилятора 51.ВАТ. Запускаем компилятор (рис. 3.3).
Пишем название программы – у нас оно Prot1, нажимаем клавишу «Enter» (рис. 3.4).
После компиляции проверяем отсутствие ошибок в файле
Prot1.lst (рис. 3.5).
На рис. 3.5 первый столбец – адрес в байтах, второй столбец – шестнадцатеричный код. Ошибок нет! Как нет и кода для команды END. Умный АССЕМБЛЕР! Посмотрим сформированный (откомпилированный) шестнадцатеричный файл Prot1.hex (рис. 3.6).
63
Рис. 3.3. Запуск командного файла компилятора
Рис. 3.4. Компиляция программы
Рис. 3.5. Листинг программы при компиляции
Рис. 3.6. Откомпилированный файл
64
В файле Prot1.hex помимо кодов команд есть ещё и дополнительная информация, в частности, контрольная сумма. Вот этот файл Prot1.hex и загружают в микроконтроллер. Таким образом, получаем 20 байт, время выполнения четырех команд MOV 4 по одному машинному циклу, итого 4 цикла, время выполнения команды JMP – 2 цикла, итого 6 циклов.
При тактовой частоте 12 МГц один машинный цикл, состоящий из 12 периодов синхронизации, составляет:
12 1 |
1 10 6с 1 мкс. |
||
12 |
106 1 |
||
|
|||
|
c |
|
Следовательно, получаем время выполнения «одного прохода» 6 мкс. Микроконтроллер 8051 в системе схемотехнического моделирования Proteus 7.2 SP6 для этой задачи изображен на рис. 3.7.
Рис. 3.7. Микроконтроллер 8051
65
3.2.ПРИМЕР ПРОГРАММНОЙ РЕАЛИЗАЦИИ ВРЕМЕННОЙ ЗАДЕРЖКИ НА ЯЗЫКЕ ASM51
Точный анализ времени выполнения команд необходим для реализации временной задержки. Процедура реализуется методом реализации счётчика. В некоторый регистр загружается число, и оно циклически уменьшается на единицу (инкрементируется). При достижении нуля организуется выход из цикла. Задержка определяется величиной этого числа с учетом времени выполнения команд. Необходимо знать время выполнения команд в машинных циклах, и эта информация есть в таблице системы команд. Например, рассмотрим подпрограмму WAIT:
WAIT: MOV R6,#Х
W1: DJNZ R6,W1
RET
В регистр 6 загружается число Х, затем командой DJNZ R6,W1 организуется цикл – декремент с проверкой нулевого содержимого регистра.
Известно, что подпрограмма вызывается командой CALL, ее длительность – 2 машинных цикла, длительность команды MOV – 1 машинный цикл, длительность команды DJNZ – 2 машинных цикла, RET – 2 машинных цикла. С учетом того, что один машинный цикл выполняется 1 мкс, получаем: программа выполняется за (1+ 2 + 2Х + 2) мкс.
Для временной выдержки, например 125 мкс, необходимое число циклов вычисляется так:
Х = (125 – 5)/2 = 60.
Кстати, все эти вычисления можно поручить АССЕМБЛЕРУ! Онэтоможет,тоестьполучитьчислоХдлязаданнойзадержки.
В данном случае для реализации требуемой временной выдержки в регистр 6 загружается десятичное число 60. Задерж-
66
ка реализуется точно. Если число Х получается дробным, то для точной доводки можно применить холостые команды NOP.
Минимальная задержка, получаемая подпрограммой WAIT,
равна: 2 + 1 + 2 + 2 = 7 мкс, максимальная: 2 + 1 + 2·255 + 2 =
=515 мкс.
Аесли нужна большая задержка? Нужно организовать вложенные циклы. Например, так:
WAIT2: |
MOV R6,#255 |
W1: |
MOV R7,#0FFH |
W2: |
DJNZ R7,W2 |
|
DJNZ R6,W1 |
|
RET |
Для еще большей задержки можно организовать еще один цикл, в котором вызывается подпрограмма WAIT2.
Программа выдачи кода с задержкой – программа РRG6 выглядит следующим образом:
BEGIN: |
|
P1 EQU90H |
;определениепортаР1 |
P2 EQU0A0H |
;определениепортаР2 |
P0 EQU80H |
;определениепортаР0 |
P3 EQU0B0H |
;определениепортаР3 |
M1: MOVP2,P1 |
;вводс портаР1,выводнаР2 |
MOVR7,#30 |
;загрузкаконстанты30 вR7 |
M3: MOVR6,#255 |
;загрузкаконстанты255вR6 |
M4: MOVR5,#255 |
;загрузкаконстанты255вR5 |
M5: DJNZ R5,M5 |
;декрементR5ипереход,еслине0 |
DJNZ R6,M4 |
; декрементR6 ипереход |
DJNZ R7,M3 |
; декрементR7 ипереход |
JMPM1 |
; переходнаначало |
END |
|
67
3.3.ДИЗАССЕМБЛИРОВАНИЕ
Иногда, в том числе и у специалистов по безопасности информации, возникает необходимость в преобразовании машинного кода, объектного файла в текст программы на языке Ассемблер. Для этого используется так называемый Дизассе́мблер – специальный транслятор. Примером является Sourcer. Имеется также, например, так называемый PE Explorer (Portable Executable, формат исполняемых файлов), предназначенный для детального изучения содержимого PE-файлов [12]. PE Explorer часто рассматривают в качестве средства анализа вредоносного программного обеспечения или пораженных вирусами файлов, но ее возможности вовсе не ограничиваются распаковщиком и дизассемблером.
«Основная проблема дизассемблирования заключается вправильности интерпретации изучаемых данных. Отделить код от данных – задача невероятносложная,особеннокогдакодвключает
Рис. 3.8. Экранная форма PE Explorer
68
в себя специальные меры противодействия дизассемблированию»[12]. Поэтому полностью автоматическое дизассемблирование весьма и весьма проблематично, и оно, так же как и программирование вцелом, является не столько ремеслом, сколько искусством. Помимо этого не будем забывать и фундаментальные алгоритмические неразрешимости, связанные с созданием универсальных алгоритмов, в том числе для анализа других алгоритмов. В заключение приведёмэкраннуюформудизассемблераPEExplorer(рис.3.8).
3.4.ДЕКОМПИЛЯЦИЯ И ОБРАТНАЯ РАЗРАБОТКА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ
Декомпилятор – это программа, транслирующая исполняемый модуль (полученный на выходе компилятора) в эквивалентный исходный код на языке программирования высокого уровня.
Декомпиляция – процесс воссоздания исходного кода декомпилятором.
Обратная разработка (обратный инжиниринг, реверсинжиниринг; англ. reverse engineering) – исследование некоторого готового устройства или программы, а также документации на него с целью понять принцип его работы; например, чтобы обнаружить недокументированные возможности (в том числе программные закладки), сделать изменение или воспроизвести устройство, программу или иной объект с аналогичными функциями, но без прямого копирования.
Применяется обычно в том случае, если создатель оригинального объекта не предоставил информации о структуре и способе создания (производства) объекта. Правообладатели таких объектов могут заявить, что проведение обратной разработки или использование её результатов нарушает их исключительное право по закону об авторском праве и патентному законодательству.
Примеры декомпиляторов: FernFlower,.NET Reflector, dotPeek – для декомпиляции сборок.NET, ILSpy, Delphi Decompiler, JAD – JAva Decompiler.
69
3.5.ПРОГРАММНАЯ РЕАЛИЗАЦИЯ КОНЕЧНОГО АВТОМАТА
Рассмотрим метод программируемой логической матрицы
(PLA) [13].
Пусть нужно вычислить следующую систему переключательных (логических) функций:
z1 x2 x1 y1, z2 y1 y2x1.
Составимсписокконъюнкцийивозбуждаемыхимифункций:
1) x2 x1(z1), 2) y1(z1,z2), 3) y2x1(z2).
База полного входного слова – y2 y1 х2 x1, база полного выходного – слова z1 z2. Получим список (массив) констант.
Основная константа Х0i (i у нас от 1 до 3 – три конъюнкции) должна выделять существенные переменные, поэтому она содержит единицы в позициях существенных переменных i-й конъюнкции (позиции определяются базой полного входного слова).
Дополнительная константа ХДi соответствует значениям истинности переменных в данной конъюнкции, поэтому она содержит единицы в позициях не инверсированных переменных и нули в остальных позициях.
Для возбуждения выходных функций необходима третья маска – маска выходов Zi, которая содержит единицы в позициях логических функций, в которые входит соответствующая конъюнкция (позиции определяются базой полного выходного слова). С целью определения окончания массива констант после последней тройки масок следует нулевая константа (на месте первой – для несуществующей конъюнкции), являющаяся признаком окончания вычислений.
Итак,
70