ZXNet эхоконференция «code.zx»

Hello, All!

═══════════════════ cmp_str .t ══════════════════

(c) Иван Рощин, Москва

Fido : 2:5020/689.53
ZXNet : 500:95/462.53
E-mail: bestview@mtu-net.ru
WWW : http://www.ivr.da.ru

Процедура сравнения строк на ассемблере Z80
═══════════════════════════════════════════

("Радиомир. Ваш компьютер" 6/2003)

При написании программы BestView мне понадобилась процедура
сравнения двух строк со следующими входными и выходными
параметрами: в HL задаётся адрес первой строки, в DE - адрес
второй строки, в BC - длина строки (не равная 0); на выходе флаг
Z установлен, если строки совпали, и сброшен в противном случае.
Алгоритм сравнения строк очень простой: берём байт по
адресу, указанному в DE, сравниваем его с байтом по адресу,
указанному в HL, в случае неравенства - выходим из процедуры
(флаг Z при этом сброшен), в случае равенства - увеличиваем HL и
DE на 1 (таким образом, они будут теперь указывать на следующие
байты сравниваемых строк) и уменьшаем BC на 1 (т.е. уменьшаем
счётчик); если после уменьшения BC<>0, переходим к сравнению
следующих байтов, иначе (BC=0) строки совпали, тогда выходим из
процедуры (флаг Z при этом установлен).
Соответственно, я написал такую процедуру, которая
использовалась в BestView до версии 2.14 включительно:

COMP_ST LD A,(DE)
CP (HL)
RET NZ ;Hе совпали.

INC HL ;!
INC DE ;!
DEC BC ;!
LD A,B ;!
OR C ;!
JR NZ,COMP_ST

RET ;Совпали.

И вот недавно, просматривая её, я обратил внимание вот на
что: увеличение HL и DE на 1, уменьшение BC на 1, проверка BC на
равенство нулю - да ведь в системе команд процессора Z80 есть
команда, которая делает всё это!
Команда LDI копирует байт из (HL) в (DE), увеличивает HL и
DE на 1, уменьшает BC на 1, сбрасывает флаг P/V, если после
уменьшения BC=0, и устанавливает флаг P/V в противном случае.
То есть эта команда делает практически то же, что и помеченный
"!" фрагмент процедуры, только, во-первых, ещё копирует байт из
(HL) в (DE), и, во-вторых, помещает информацию о равенстве BC
нулю во флаг P/V, а не во флаг Z.
Копирование байта из (HL) в (DE) в рассматриваемой процедуре
совершенно ни к чему. Однако, приглядевшись внимательнее, можно
заметить, что после команды RET NZ байт по адресу, указанному в
HL, заведомо равен байту по адресу, указанному в DE
(действительно, если бы они не были равны, то после их сравнения
произошёл бы выход из процедуры).
А если байты равны, значит, копирование из (HL) в (DE) не
изменит (DE), то есть окажется безвредным побочным эффектом.
Тогда весь участок процедуры, помеченный "!", можно заменить
на одну команду LDI, одновременно заменив команду условного
перехода к началу цикла (JR NZ,COMP_ST) на команду
JP PE,COMP_ST - ведь теперь именно флаг P/V указывает на
выполнение или невыполнение условия BC=0.
Hо остаётся ещё одна проблема: при выходе из процедуры в
случае совпадения строк флаг Z должен быть установлен. И если
в первоначальном варианте процедуры он автоматически оказывался
установлен при проверке условия выхода из цикла (BC=0), то
теперь проверка этого условия вообще не связана с флагом Z.
Сначала я хотел добавить перед выходом из процедуры в случае
совпадения строк (т.е. перед последней командой RET) команду
XOR A, устанавливающую флаг Z. Hо, посмотрев в справочник, я
увидел, что команда LDI не меняет флаг Z, а посмотрев на
процедуру, увидел, что после сравнения очередных байтов строк
флаг Z заведомо будет установлен (ведь строки совпадают!). Таким
образом, ничего специально добавлять не потребовалось.
Итак, оптимизированный вариант процедуры:

COMP_ST LD A,(DE)
CP (HL)
RET NZ ;Hе совпали.

LDI ;Hа Z не влияет!
JP PE,COMP_ST

RET ;Совпали, Z=1!

Длина процедуры уменьшилась на 2 байта, а время выполнения
сократилось следующим образом: в случае, когда сравниваемые
строки не совпадают (причём их первые n байтов совпадают),
выигрыш составляет 12n тактов, а в случае, когда строки
совпадают (n - их длина), выигрыш составляет 12(n-1)+7 тактов.

════════════════════════════════════════════════

С уважением, Иван Рощин.

Hемедленно нажми на RESET, Ivan Roshin!

IR> ("Радиомир. Ваш компьютер" 6/2003)

IR> При написании программы BestView мне понадобилась процедура
IR> сравнения двух строк со следующими входными и выходными

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