Textnew2

С формальной стороны, команда CMPSx сравнивает элементы в памяти, длина которые задается последним символом мнемокода, а адреса текущим содержимым регистров ESI и EDI. Результат сравнения отражается флагами в регистре EFLAGS. После такого сравнения внутренние действия команды CMPSx изменяют значения регистров ESI и EDI так, чтобы они задавали следующие элементы для сравнения в том же направлении. Таким образом, при прямом направлении, заданном командой CLD, предшествующий команде сравнения (DF=0), значения этих регистров увеличиваются, а при обратном направлении (после команды STD) - уменьшаются. Величина такого изменения составляет один (для байтов, задаваемых символом B), два (для слов, задаваемых символом W) или четыре (для двойных слов, задаваемых символом D).

Собственно повторение обеспечивается командным байтом префикса повторения. Эта специфическая инструкция проверяет содержимое регистра ECX, и, если оно равно нулю, прекращает повторения команды сравнения, записанной непосредственно за этим префиксом. В результате начинает выполняться команда, следующая за командой строкового сравнения. При неравном нулю содержимое регистра ECX префикс повторения выполняет команду строкового сравнения. По результатам такого сравнения очередных элементов (в строковых данных) вырабатываются флаги для регистра EFLAGS. Если результат сравнения не согласуется с видом префикса повторения, то действия команды CMPSx прекращаются и далее выполняется команда, следующая за строковым сравнением. При текущем результате сравнения равно и префиксе REPE, а также при текущем результате сравнения не равно и префиксе REPNE значение регистра ECX уменьшается на единицу и команда строкового сравнения выполняется в очередной раз.

Следует обратить пристальное внимание начинающих на то, что команда CMPSx не является совершенно самостоятельной командой подобно обычным командам, отличным от строковых. Над какими операндами и в каком направлении выполняется обработка данных этой командой никак не видно из ее записи на ассемблере (и тем более из машинного кода). Эта команда подобно командам умножения и деления использует множество умолчаний, неявных для поверхностного читателя программы. Более того, эта команда является чем-то вроде "детали детского конструктора", из которого собирается функциональный участок программы. Чтобы строковая команда, причем не только сравнения, но, практически и любая другая строковая команда, выполнила свое назначение для программы, ее необходимо соединить со вспомогательными командами, которые подготовят ее выполнение, обеспечат повторение, а, может быть, и сформируеют окончательный результат ее работы.

В частности получения информации о тех символах строк данных, на которых обнаружено различие этих строк, требует дополнительных коррекций для значений в индексных регистрах, которые использовала команда CMPSx. Дело в том, что значения этих регистров, как бы "забегают вперед", на каждом шаге выполнения этой команды подготавливаясь к сравнению следующих элементов в сравниваемых строках. Поэтому после обнаружения не сравнения, необходимо эти значения как

111

бы "открутить обратно". С этой целью требуется выполнять команды DEC для регистров ESI и EDI при прямом направлении обработки и действиям с однобайтовыми элементами. (Для противоположного направления и том же размере элементов потребуются команды инкремента, а в общем случае команды сложения или вычитания размере элемента в байтах.)

Практическое применение команды строкового сравнения дано в подпрограмме strncmp, исходный текст которой на ассемблере приведен на рис. 6.2.1.

;procedure strncmp(target* edi, source* esi, maxlen ecx)

; result code = eax; position of different symbols into esi and edi strncmp:

push edi push esi push ecx cld

repe cmpsb dec esi dec edi

mov al,[esi] sub al, [edi] movsx eax,al pop ecx

pop esi pop edi ret

;end procedure strncmp

Рис. 6.2.1. Эффективная процедура strncmp сравнения строк

Процедура по своему назначению аналогична функции strncmp из стандартной библиотеки языка С и выдает в качестве результата в регистре EAX нулевое значении при равенстве сравниваемых строк и значение, равное разности отличающихся символов для неравных строк.

Эта процедура предполагает предварительное помещение адресов сравниваемых строк в регистры ESI и EDI, а числа сравниваемых байтов - в регистр ECX. Подготовительные действия в процедуре состоят всего лишь из установки прямого направления сравнения с помощью команды CLD. Основную работу данной процедуры выполняет ее третья команда, многократно повторяемая при выполнении с помощью префикса повторения REPE.

Для формирования значения результата, согласно описанному правилу, вначале регистры ESI и EDI устанавливаются на последние из сравниваемых элементов, а затем в регистре AL выполняется их вычитание. Для образования правильного значения во всем регистре EAX, старшие три байта этого регистра устанавливаются с

112

учетом знака в операнде исходного значения, с помощью специальной команды MOVSX. Эта команда имеет на ассемблере вид

MOVSX регистр_большего_размера, регистр_меньшего_размера

и применяется в данном случае для регистров EAX и AL.

На рис. 6.2.2 приведена аналогична по действиям процедура astrcnmp, не использующая строковых команд. Хотя последняя программа состоит из того же числа команд (равного 14), ее повторяемая часть состоит из шести команд, общим размером в десять байтов, что значительно замедляет обработку данных по сравнению с рассмотренным выше вариантом.

;procedure astrcnmp(target* edi, source* esi, maxlen ecx)

; result code = eax; position of different symbols into esi and edi astrncmp:

push edi push esi push ecx

met3: mov al, [esi] sub al, [edi] jne ex3

inc esi inc edi

loop met3, ecx ex3: movsx eax,al

pop ecx pop esi pop edi ret

;end procedure astrncmp

Рис. 6.2.2. Неэффективная процедура astrncmp сравнения строк

Кроме команды сравнения двух строк, имеется еще одна строковая команда сравнения, которая сравнивает значение в фиксированном регистре с последовательными элементами строкового массива. Такая команда имеет мнемокод SCASx, где метасимвол x имеет то же назначение, что и у рассмотренных выше команд (задает размер элементов данных, участвующих в сравнении). Команда SCASB первый из сравниваемых элементов берет из регистра AL, команда SCASW первый из сравниваемых элементов берет из регистра AX, а команда SCASD первый из сравниваемых элементов берет из регистра EAX. Второй из сравниваемых элементов берется из памяти, а именно из места, заданного адресом в регистре EDI.

Обычным для строковых команд образом, флажок DF задает здесь направление перебора элементов в памяти для сравнения, регистр EDI увеличивается (при DF=0) или уменьшается (при DF=1) в конце выполнения команды SCASx Каждое выпол-

113

нение этой команды устанавливает флаги сравнения в регистре EFLAGS, а для управлением повторением строковой команды используются обычно префиксы повторения REPE и REPNE. Причем оба этих префикса для данной команды имеют одинаковое по практической ценности применение. Префикс REPE позволяет искать в заданной строке первый символ, отличный от заданного, а префикс REPNE позволяет искать первый символ, совпадающий с заданным в регистре AL. (Или, соответственно, первый двухбайтовый или четырехбайтовый элемент.)

Как уже объяснялось выше, любая строковая команда, а, в частности, команда SCASx требует для содержательного использования вспомогательных команд. Для определения, какой же элемент строкового массива вызвал в действительности прекращения повторяющихся действий сравнения, оказывается необходимым провести соответствующую коррекцию содержимого регистра EDI. В частности при однобайтовых элементах и прямом направлении поиска, потребуется выполнить команду DEC EDI.

Применение строковой команды SCASB демонстрирует процедура strlen, исходный текст которой на ассемблере приведен на рис. 6.2.3. Эта процедуре по выполняемым действиям аналогична функции strlen из стандартной библиотеки языка Си и вычисляет длину текста, завершающегося нулевым байтом. Данная процедура требует перед своим вызовом занесения адреса строки в регистр ESI, а максимально возможного размера строки - в регистр ECX

;procedure strlen(source* esi, maxlen ecx): result = eax strlen:push ecx

push edi mov edi, esi cld

mov al,0 repne scasb

dec edi

sub edi, [esp] ; subtruct begin value of edi mov eax, edi

pop edi pop ecx ret

;end procedure strlen

Рис. 6.2.3. Эффективная процедура strlen вычисления длины строки

Повторяемые действия процедуры осуществляет единственная команда SCASB с префиксом повторения REPNE, для работы которой в регистр AL предварительно заносится значение 0 (значение, которое должно завершать текст строки). После нахождения нулевого байта в процедуре корректируется значение адреса в регистре EDI, так чтобы этот регистр задавал адрес только что просмотренного байта и из

114

него вычитается начальное значение регистра EDI, запомненное перед началом просмотра командой PUSH сохранения содержимого регистра в стеке. Одновременно демонстрируется доступ к запомненному ранее в стеке значению без использования команды POP. В данном месте используется тот факт, что в текущий момент на самом верху стека находится как раз значение запомненного ранее регистра EDI и доступ к нему задается через регистр указателя стека в виде [ESP].

Следует отметить, что такое использование призвано продемонстрировать саму возможность подобных действий с данными, но не рекомендуется, как нестандартный доступ к содержимому стеку (его можно рекомендовать только очень опытным и внимательным программистам). Более систематическим решением было бы, например, следующее

. . .
pop eax	; четыре команды вместо двух:
push eax	; sub edi, [esp]
sub eax, edi	; mov eax, edi
neg eax	;
. . .

где последовательно выполнение команд PUSH рег и POP рег оставляет на старом месте значение в стеке, но позволяет получить его и в регистре рег.

На рис. 6.2.4 приведена аналогична по действиям процедура astrlen, не использующая строковых команд. Хотя последняя программа состоит даже из меньшего числа команд (равного одиннадцати по сравнению с двенадцатью командами в программе рис. 6.2.3), ее повторяемая часть состоит из четырех команд, общим размером в восемь байтов, что значительно замедляет обработку данных по сравнению с рассмотренным выше вариантом.

;procedure astrlen(source* esi, maxlen ecx): result = eax

astrlen:	push esi
push ecx

met4: cmp byte [esi], 0 je ex4

inc esi

loop met4, ecx

ex4: sub esi, [esp] ; subtruct begin value of esi mov eax, esi

pop ecx pop esi ret

;end procedure strlen

Рис. 6.2.4. Неэффективная процедура astrlen вычисления длины строки

115

Наконец, на рис. 6.2.5 и 6.2.6 приведены процедуры получения из исходной строки текста новой строки, не содержащей пробелов в начале строки. Процедура getbegstr на рис. 6.2.5 используется строковую команду SCASB с префиксом повторения REPE для поиска первого не пробела, а процедура agetbegstr на рис. 6.2.6 не использует строковых команд.

;procedure getbegstr(target* esi, source* esi, maxlen ecx) getbegstr: push ecx

push edi cld

mov edi, esi

mov al,' ' ; сравнение с пробелом, который записывается между апострофами repe scasb

dec edi mov esi, edi pop edi pop ecx

ret

;end procedure getbegstr

Рис. 6.2.5. Эффективная процедура нахождения первого не пробела в строке

;procedure agetbegstr(target* esi, source* esi, maxlen ecx) agetbegstr: push ecx

bmet1: cmp byte [esi],' ' ; сравнение с пробелом, который записывается между апострофами

jne ex1 inc esi

loop bmet1,ecx ex1: pop ecx

ret

;end procedure agetbegstr

Рис. 6.2.6. Простая процедура нахождения первого не пробела в строке

Хотя вариант без строковых команд оказывается короче по числу команд и их суммарной длине (семь команд против одиннадцати со строкой командой), вариант, использующий строковое сравнение работает значительно быстрее.

На рис. 6.2.7. приведена основная часть программы, использующая рассмотренные выше процедуры работы со строками.

SEGMENT .text

_start:

116

;--- read(0, str1, 80) == <3>(ebx, ecx, edx) mov eax,3 ; N function=read

mov ebx,0 ; 0 handle=0 (stdin) mov ecx, str1 ; address of buf mov edx,80 ; number of byte int 80h

mov [actlen],eax

mov esi, eax

mov byte [str1+esi-1],0 ; last symbol of input - '\n' sub dword [actlen],1

mov esi, str1 mov ecx, [actlen] inc ecx

call getbegstr mov edi, txt1 call strncpy

;--- read(0, str2, 80) == <3>(ebx, ecx, edx) mov eax,3 ; N function=read

mov ebx,0 ; 0 handle=0 (stdin) mov ecx, str2 ; address of buf mov edx,80 ; number of byte int 80h

mov [actlen],eax mov esi, [actlen]

mov byte [str2+esi-1],0 ; last symbol of input - '\n' sub dword [actlen],1

mov esi, str2 mov ecx, [actlen] inc ecx

call getbegstr mov edi, txt2 call strncpy

mov esi, txt1 call strlen

mov [len1], eax

mov esi, txt2 call strlen

117

mov [len2], eax
cmp eax, [len1]
jge next
mov eax, [len1]
next: mov ecx, eax	; into ecx - Max(len1, len2)
mov esi, txt1
mov edi, txt2
call strncmp
cmp eax,0
jne wrne
mov ecx, mese

mov edx, lenmese

write: ;--- write(1, mese, lenmese) == <4>(ebx, ecx, edx)

	mov eax,4 ; N function=write
	mov ebx,1	; N handle=1 (stdout)
	int 80h
	mov eax, 1
	int 80h	; exit(0)
wrne: mov edx, lenmesne
	mov ecx, mesne
	mov al, [esi]
	mov [char1], al
	mov al, [edi]
	mov [char2], al
	jmp write
	SEGMENT .data
str1	times 81 db 0
str2	times 81 db 0
txt1	times 81 db 0
txt2	times 81 db 0
len1	dd 0
len2	dd 0
actlen	dd 0
mese	db 'Содержательная часть строк совпадает',13,10

lenmese equ $-mese

mesnedb 'Строки отличаются символами ' lenmesne equ $-mesne

char1 db 0,' г ' char2 db 0,13,10

Рис. 6.2.7. Подпрограмма использования строковых процедур.

118

Эта программа вводит с клавиатуры две текстовые строки, оканчивающиеся нажатием клавиши Enter, затем отбрасывает из дальнейшего рассмотрения начальные пробелы во введенных строках и сравнивает оставшиеся части текста. По результатам сравнения выдается сообщение, какими символами отличаются содержательные части этих строк или что содержимое этих частей совпадают.

В завершение следует все же сказать, что в современных аппаратных реализациях архитектуры Intel использование строковых команд действительно обеспечивает заметную эффективность только для достаточно больших строковых массивов. В частности при пересылке и сравнении очень больших блоков данных. Наличие же очень больших аппаратных кэшей в современных процессорах существенно сглаживает недостатки программных решений без строковых команд для относительно небольших строковых данных.

6.3. Лексический анализ на основе команды XLAT

Одной из классических операций анализа дискретных данных является определение класса, к которому относится данных элемент. В простейшей и наиболее значимой постановке, требуется определить подобную принадлежность для элемента, задаваемого однобайтовых кодом. Если подобных анализ входит как составная часть в более сложные задачи и повторяется очень часто, то наиболее эффективным решением с точки зрения быстродействия является использование табличных преобразований.

Табличное преобразование, по существу является явным хранением информации об отображении аргумента преобразования в его значение. С точки чистой математики это так называемый график отображения. К сожалению, подобный график удается полностью хранить в памяти только для отображений, аргумент которых принимает достаточно небольшое число значений. Читатель, видимо, знаком с этим практическим подходом по теории булевых функций, небольшое число наборов различных значений аргументов которых оказывается очень просто и удобно использовать.

Мы рассмотрим более частную ситуацию, когда и аргумент задается одним байтом (256-ю допустимыми значениями) и значение функции преобразования также имеет небольшое число значений, позволяющее кодировать их с помощью байтов.

Одной из таких задач является анализ текущего символа обработки на вопрос его принадлежности к классу латинских букв, классу русских букв, классу символов математических операций. (Заметим, что такая проблема характерна для лексического анализа исходного текста программ в процессе трансляции программ для получения из них исполняемых файлов или объектных кодов.)

В простейших, хотя и достаточно частых практических ситуациях, символы, принадлежащие к одному подобному классу, размещаются в соседних позициях в таблицах кодировки. В частности, принадлежность символа к строчным латинским буквам в кодировке ASCII может осуществить следующий фрагмент программы

119

. . . ; поместить символ в регистр AL cmp al, 'a'

jl nolat	; для произвольных таблиц кодировки надежней использовать JB nolat
cmp al, 'z'
jg nolat	; для произвольных таблиц кодировки надежней использовать JA nolat

; имеем латинскую строчную букву!

где метка nolat соответствует ситуации, когда анализируемый символ не принадлежит к строчным латинским буквам. Здесь использована замечательная особенность кодирования латинских букв в ASCII, заключающаяся в том, что они размещаются последовательно без каких-либо разрывов для других символов. Для кириллицы (русского алфавита) ситуация, как правило, менее удобная для программиста и ее символы могут размещаться несколькими разделенными интервалами. Поэтому может потребоваться не два, а значительно больше сравнений. В общем случае для анализа может потребоваться столько сравнений, сколько различных символов находится в рассматриваемом классе. Хотя путем перечисления вариантов достигается не только теоретическое, но и некоторое практическое решение, оно оказывается недостаточно эффективным, поскольку есть простой способ быстро решать эту проблему.

Теоретическая сторона решения заключается в использовании специальной заранее подготовленной таблицы. Элементами этой таблицы являются условные коды классов символов для данной задачи, причем в качестве k-го элемента этой таблицы должно хранится значение кода класса для k-го символа. Иначе говоря, в таблице на том месте, где размещается символ в его исходной системе кодирования, помещается код класса этого символа.

Для решения подобной задачи в состав архитектуры Intel включена специальная команда с мнемоникой XLAT. Она неявно использует два аргумента. Аргумент, который перед ее выполнением должен быть помещен в регистр EBX (регистр BX для 16-битного варианта), используется как адрес таблицы преобразования, занимающей 256 байтов. Другой аргумент, помещенный в регистр AL задает символ, анализируемый с помощью таблицы. Результат команда XLAT выдает в регистре AL.

Внутренние действия команды XLAT заключаются в выборе из таблицы, базовый адрес которой задается регистром EBX, единственного байта, находящегося в том однобайтовом элементе таблицы, порядковый номер которого равен числовому значению аргумента в регистре AL. Практически команда XLAT может быть промоделирована следующей последовательностью команд

push eax movzx eax, al

mov al, [ebx+eax] pop eax

Фактически же она выполняется гораздо проще, используя аппаратные средства и аналогична (несуществующей) команде MOV AL, [EBX+AL].

Есть один маленький нюанс, не обратив внимание на который, можно получить ошибку, трудно обнаруживаемую начинающим. Команда XLAT имеет такое имен-

120