6.2. Применение строковых команд сравнения

Кроме эффективной реализации пересылки массивов, идея строковых команд использована для более эффективной реализации сравнения строк. Заметим, что в упомянутой выше архитектуре IBM360 имелась команда

CLC операнд1(сколько), операнд2

которая была предназначена для сравнения произвольных последовательностей байтов (длиной не более 255).

В архитектуре Intel для аналогичных целей содержится строковая команда с обобщенной мнемоникой CMPSx, где последний метасимвол x должен быть представлен одной из букв B, W или D, согласно типу размера элементов строкового массива (соответствуя обозначениям BYTE, WORD и DWORD). Данная команда также предназначена лишь для центральной части фрагмента программного кода, который в совокупности реализует сравнение строковых массивов. Подготовительными командами в этом фрагменте должны задаваться необходимые значения для регистров ESI, EDI и ECX. Регистр ESI перед первым выполнением строковой команды сравнения CMPSx должен содержать адрес первого элемента операнда операнд1, а регистр EDI - первого из сравниваемых элементов операнда операнд1. При этом, аналогично строковым командам пересылки, должен быть соответствующим образом установлен флаг направления DF в регистре флагов. Если требуется сравнение последовательности элементов от младших адресов к старшим, на этот флаг устанавливается командой CLD, а для противоположного направления сравнения - командой STD. Следует обратить внимание, что при сравнении от старших адресов к младшим начальные значения регистров ESI и EDI должны указывать на последний элемент в областях данных, которые обозначены в наших рассуждениях как операнд1 и операнд2.

Для сравнения последовательности элементов строк команда CMPSx должна использоваться с префиксом повторения. (Без префикса повторения эта команда выполнится всего лишь с одним элементом из заданных строк, хотя содержимое регистров ESI и EDI при этом изменится, чтобы показывать на следующий элемент каждой из строк.) Префикс повторения для команд сравнения может задаваться в одном из двух вариантов, которые обозначаются на ассемблере мнемокодами REPE и REPNE. Префикс REPE используется, если сравнение следующих очередных элементов строк следует производить только после обнаружения равенства элементов в текущем шаге сравнения. Префикс REPNE предназначен для повторения действий команды строкового сравнения при обнаружении несравнения элементов на текущем шаге.

Таким образом, если строки сравниваются на предмет нахождения первого различного в них элемента, то необходимо применить префикс REPE непосредственно перед командой CMPSx. Если же строки сравниваются на предмет нахождения первого совпадающего по значению элемента, то следует использовать префикс REPNE. Следует заметить, что синонимами префиксов REPE и REPNE служат, соответственно, префиксы REPZ и REPNZ.

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

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

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

В частности, получение информации о тех символах строк данных, на которых обнаружено различие этих строк, требует дополнительных коррекций для значений в индексных регистрах, которые использовала команда CMPSx. Дело в том, что значения этих регистров, как бы «забегают вперед», на каждом шаге выполнения этой команды подготавливаясь к сравнению следующих элементов в сравниваемых строках. Поэтому после обнаружения несравнения, необходимо эти значения как бы «открутить обратно». С этой целью требуется выполнять команды 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 старшие три байта этого регистра устанавливаются с учетом знака в операнде исходного значения, с помощью специальной команды MOVSX. Эта команда имеет на ассемблере вид

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

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

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

Обычным для строковых команд образом флажок DF задает здесь направление перебора элементов в памяти для сравнения, регистр EDI увеличивается (при DF=0) или уменьшается (при DF=1) в конце выполнения команды SCASx. Каждое выполнение этой команды устанавливает флаги сравнения в регистре EFLAGS, а для управления повторением строковой команды используются обычно префиксы повторения REPE и REPNE. Причем оба этих префикса для данной команды имеют одинаковое по практической ценности применение. Префикс REPE позволяет искать в заданной строке первый символ, отличный от заданного, а префикс REPNE позволяет искать первый символ, совпадающий с заданным в регистре AL. (Или, соответственно, первый двухбайтовый или четырехбайтовый элемент.)

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

Применение строковой команды SCASB демонстрирует процедура strlen, исходный текст которой на ассемблере приведен в листинге 6.2.2. Эта процедуре по выполняемым действиям аналогична функции 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.2. Эффективная процедура strlen вычисления длины строки

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

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

. . .

pop eax ; четыре команды вместо двух:

push eax ; sub edi, [esp]

sub eax, edi ; mov eax, edi

neg eax ;

. . .

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

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

;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.3. Неэффективная процедура astrlen вычисления длины строки

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

getbegstr: push ecx ;procedure getbegstr(target* esi, source* esi, maxlen 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.4. Эффективная процедура нахождения первого непробела в строке

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

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

jne ex1

inc esi

loop bmet1,ecx

ex1: pop ecx

ret

;end procedure agetbegstr

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

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

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