ZX Review #7-8-9-10 08 ноября 1997

Ретро - 40 лучших процедур: Поиск подстроки.

      8.8. Поиск подстроки

  Длина: 168
  Количество переменных: 0
  Контрольная сумма: 19875
  Назначение: эта программа воз-
вращает позицию подстроки (B$) в
главной строке (A$) или 0 в слу-
чае ошибки.
  Вызов программы:
     LET P = USR адрес
  Контроль ошибок:  если  строка
не  существует, или  если  длина
подстроки равна  нулю, или  если
длина подстроки больше, чем дли-
на   главной  строки,  программа
возвращает значение 0. Если оши-
бки нет, но подстрока не найдена
в главной строке, программа так-
же дает 0.
  Комментарий: после  выхода  из
программы в машинных кодах пере-
менная P (может быть использова-
на любая другая переменная)  бу-
дет  хранить  искомое  значение.
Строки, к которым делается обра-
щение, не могут  быть  массивами
данных. Для изменения используе-
мых строк числа, отмеченные  "*"

должны быть изменены.  66* - это
подстрока, 65* - главная строка.
Для изменения эти числа  необхо-
димо заменить  кодами  требуемых
символов. Например, если вы  хо-
тите найти позицию  H$ в G$, то,
соответственно, надо будет ввес-
ти 71 (код G) и 72 (код H).

   ЛИСТИНГ МАШИННЫХ КОДОВ
МЕТКА  АССЕМБЛЕР      ЧИСЛА ДЛЯ ВВОДА147.

       SUB A         151
       LD B,A         71
       LD C,A         79
       LD D,A         87
       LD E,A         95
       LD HL,(23627)  42  75  92
NEXT_V LD A,(HL)     126
       CP 128        254 128
       JR Z,NOT_FD    40  95
       BIT 7,A       203 127
       JR NZ,FOR_NX   32  41
       CP 96         254  96
       JR NC,NUMBER   48  29
       CP 65         254  65*
       JR NZ,SUBSTR   32   2
       LD D,H         84
       LD E,L         93
SUBSTR CP 66         254  66*
       JR NZ,CHECK    32   2
       LD B,H         68
       LD C,L         77
CHECK  LD A,D        122
       OR E          179
       JR Z,STRING    40   4
       LD A,B        120
       OR C          177
       JR NZ,FOUND    32  38
STRING PUSH DE       213
       INC HL         35
       LD E,(HL)      94
       INC HL         35
       LD D,(HL)      86
ADD    ADD HL,DE      25
       POP DE        209
       JR INCRS       24   5
NUMBER INC HL         35
       INC HL         35
       INC HL         35
       INC HL         35
       INC HL         35
INCRS  INC HL         35
       JR NEXT_V      24 206
FOR_NX CP 224        254 224
       JR C,N_BIT     56   6
       PUSH DE       213
       LD DE,18       17  18   0
       JR ADD         24 234
N_BIT  BIT 5,A       203 111
       JR Z,STRING    40 225
NEXT_B INC HL         35
       BIT 7,(HL)    203 126
       JR Z,NEXT_B    40 251
       JR NUMBER      24 227
FOUND  EX DE,HL      235
       INC HL         35
       INC HL         35
       PUSH HL       229
       PUSH HL       229
       INC BC          3
       PUSH BC       197
       LD A,(BC)      10
       LD E,A         95
       INC BC          3
       LD A,(BC)      10
       LD D,A         87
       OR E          179
       JR Z,ZERO      40  11
       PUSH DE       213
       LD A,(HL)     126
       DEC HL         43
       LD L,(HL)     110
       LD H,A        103
       AND A         167
       SBC HL,DE     237  82
       JR NC,CONTIN   48   8
       POP BC        193
ZERO   POP BC        193
       POP BC        193
ERROR  POP BC        193
NOT_FD LD BC,0         1   0   0
       RET           201
CONTIN POP IX        221 225
       POP BC        193
       EX DE,HL      235
       POP HL        225
       INC BC          3
       INC BC          3
SAVE   INC HL         35
       PUSH HL       229
       PUSH BC       197
       PUSH IX       221 229
       PUSH DE       213
COMPAR LD A,(BC)      10
       CP (HL)       190
       JR Z,MATCH     40  12
       POP DE        209
       POP IX        221 225
       POP BC        193
       POP HL        225
       LD A,D        122
       OR E          179
       JR Z,ERROR     40 225
       DEC DE         27
       JR SAVE        24 234
MATCH  INC HL         35
       INC BC          3
       PUSH HL       229
       DEC IX        221  43
       PUSH IX       221 229
       POP HL        225
       LD A,H        124
       OR L          181
       POP HL        225
       JR NZ,COMPAR   32 227
       POP DE        209
       POP DE        209
       AND A         167
       SBC HL,DE     237  82
       POP DE        209
       POP DE        209
       POP DE        209
       AND A         167
       SBC HL,DE     237  82
       LD B,H         68
       LD C,L         77
       RET           201
2
  Как она работает:
  В аккумулятор, пару  регистров
BC и пару  регистров  DE  загру-
жается 0. Позднее в программе  в
BC будет установлен адрес  B$, а
в DE будет установлен адрес  A$.
В HL  загружается  адрес  начала
области программных переменных.
  В аккумулятор загружается байт
из  адреса, находящегося  в  HL.
Если аккумулятор  содержит  чис-
ло  128, программа  переходит  к
NOT_FD, т.к. достигнут конец об-
ласти  программных   переменных.
Если  бит  7  аккумулятора уста-
новлен в 1, делается  переход  к
FOR_NX, т.к. найденная  перемен-
ная - не строковая и  не  число,
имя которого состоит  только  из
одной литеры.  Если  аккумулятор
содержит число большее, чем  95,
делается переход к NUMBER.
  Для  достижения  этого   этапа
строка должна быть найдена. Если
в аккумуляторе содержится  число
65,  определяется  местонахожде-
ние строки A$, а  содержимое  HL
копируется в DE. Если  аккумуля-
тор содержит  число  66, опреде-
ляется строка B$, а HL копирует-
ся в BC. Если DE не равно 0 и BC
не равно 0, определяется  место-
нахождение обеих строк, и  прог-
рамма переходит к FOUND.
  Если программа достигает  про-
цедуры STRING, DE сохраняется  в
стека и загружается длиной  най-
денной строки. Это значение при-
бавляется к адресу старшего бай-
та указателей  строки  и  сохра-
няется в HL. DE восстанавливает-
ся из стека и делается переход к
INCRS.
  В процедуре NUMBER HL увеличи-
вается в 5 раз, указывая на пос-
ледний байт найденного числа. HL
затем увеличивается, указывая на
следующую переменную, и происхо-
дит переход к NEXT_V.
  В процедуре FOR_NX, если акку-
мулятор содержит  число  меньше,
чем  224,  делается  переход   к
N_BIT, т.к. встретившаяся  пере-
менная не  является  управляющей
переменной цикла FOR-NEXT.  Если
значение  аккумулятора   больше,
чем 223, то число 18 прибавляет-
ся к HL, указывая  на  последний
байт переменной  цикла, и  прог-
рамма возвращается к INCRS.
  Если программа достигает N_BIT
и бит 5 аккумулятора  установлен
в 0, делается переход к  STRING,
чтобы загрузить в HL адрес  сле-
дующей  переменной, т.к.  найден
массив.
  Если программа достигает NEXT_
B, найдено  число, имя  которого
больше одного символа по  длине.
Таким образом, HL  увеличивается
до тех пор, пока  не  укажет  на
последний символ имени  перемен-
ной, а затем  делается переход к
NUMBER.
  В процедуре FOUND в HL  загру-
жается адрес  строки  A$, и  это
значение  увеличивается  дважды,
чтобы  получить  адрес  старшего
байта указателей.  Это  значение
затем сохраняется в стеке  дваж-
ды.  BC  увеличивается, указывая
на младший байт указателей  под-
строки B$. Адрес в BC затем сох-
раняется в стеке.  В  DE  загру-
жается длина строки  B$  и  если
это значение  равно  0, делается
переход к ZERO. Затем  DE  поме-
щается в стек. В HL  загружается
длина строки A$ и если это  зна-
чение не меньше чем DE, програм-
ма переходит  к  CONTIN.  Указа-
тель  стека  затем  восстанавли-
вается, в  BC  загружается  0  и
программа возвращается в BASIC.
  В процедуре CONTIN в IX  уста-
навливается длина строки B$, а в
BC  помещается  адрес   младшего
байта указателей  для  подстроки
B$. В  DE  загружается  разность
длин строк A$ и B$, а в HL  заг-
ружается  адрес  старшего  байта
указателей для A$. BC затем уве-
личивается  дважды, чтобы  полу-
чить  адрес  первого  символа  в
подстроке B$. HL  увеличивается,
указывая  на  следующий   символ
строки A$. HL, BC, IX и  DE  за-
тем сохраняются на стеке. В  ак-
кумулятор  загружается  байт  по
адресу в BC и, если  это  значе-
ние равно значению байта по  ад-
ресу в  HL, делается  переход  к
MATCH.  DE, IX, BC  и  HL  затем
восстанавливаются из стека. Если
DE содержит 0, делается  переход
к ERROR, т.к. подстроки B$ нет в
строке A$. Счетчик DE уменьшает-
ся и  программа  возвращается  к
SAVE.
  Если программа достигает  про-
цедуры MATCH, HL и  BC  увеличи-
ваются,  указывая  на  следующий
символ A$ и  B$  соответственно.
HL затем  сохраняется  в  стеке.
IX, счетчик, уменьшается и  пос-
ле восстановления HL  из  стека,
если IX не содержит  0, програм-
ма возвращается к COMPAR.
  Для  достижения  этого   этапа
местонахождение подстроки  B$  в
строке A$ уже должно быть  опре-
делено. Длина подстроки B$ вычи-
тается  из  HL,  а  затем  адрес
страршего байта  указателей  для
строки A$ вычитается из HL.  Ре-
зультат - это позиция  подстроки
B$ в строке A$. Это значение ко-
пируется в пару регистров  BC  и
программа возвращается в BASIC.

           *   *   *

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

   Формат данных в Спектруме

  Данные в Спектруме хранятся  в
виде  переменных  и  массивов  в
специально выделенной для  этого
области памяти. Эта область  на-
чинается непосредственно за  об-
ластью,  в  которой  размещается
текст БЕЙСИК-программы.
  На начало области  программных
переменных  указывает   двухбай-
тная системная переменная  VARS.
Она расположена по адресу  23267
(5AE3H).
  Конец области программных  пе-
ременных задан специальным  мар-
кером - это байт, значение кото-
рого равно 80H (128).
  Спектрум  различает  несколько
разных типов переменных. Это:
  - обычная числовая переменная,
имя  которой  состоит  из  одной
буквы, например x;
  - числовая переменная, имя ко-
торой состоит из более, чем  од-
ной буквы, например, row;
  - числовой  массив,  например,
a(5) или b(3,3,40);
  - переменные, управляющие цик-
лами FOR...NEXT, например, 1;
  - строковые переменные, напри-
мер, a$;
  - строковые массивы, например,
b$(10,40).

      Числовая переменная
    с именем из одной буквы

  Занимает 6  байтов.  В  первом
байте хранится ее имя, в  после-
дующих пяти - ее значение в  ин-
тегральной  форме. Об интеграль-
ном представлении действительных
чисел  см.  "Программирование  в
машинных  кодах".  Первый   байт
имеет следующую раскладку:

   ┌──┬──┬──┬──┬──┬──┬──┬──┐
   │0 │1 │1 │б │у │к │в │а │
   └──┴──┴──┴──┴──┴──┴──┴──┘

  На то, что это  простая  пере-
менная, указывает  специфическое
расположение первых трех битов.

  Числовая переменная с именем
    более чем из одной буквы

  Ее первый байт  имеет  следую-
щий формат:

   ┌──┬──┬──┬──┬──┬──┬──┬──┐
   │1 │0 │1 │б │у │к │в │а │
   └──┴──┴──┴──┴──┴──┴──┴──┘

  Прочие байты имени (кроме пос-
леднего) имеют следующий формат:

   ┌──┬──┬──┬──┬──┬──┬──┬──┐
   │0 │б │у │к │в │а │. │. │
   └──┴──┴──┴──┴──┴──┴──┴──┘

  Последний байт имени:

   ┌──┬──┬──┬──┬──┬──┬──┬──┐
   │1 │б │у │к │в │а │. │. │
   └──┴──┴──┴──┴──┴──┴──┴──┘

  За именем следуют 5 байтов для
выражения самого числа в  интег-
ральной форме.

        Числовой массив

  Первый байт:

   ┌──┬──┬──┬──┬──┬──┬──┬──┐
   │1 │0 │0 │б │у │к │в │а │
   └──┴──┴──┴──┴──┴──┴──┴──┘

  Байты  2,  3  содержат  полную
длину всех элементов (по 5  бай-
тов на каждый  элемент  массива)
плюс по 2 байта на  каждую  раз-
мерность массива, плюс один байт
на указание  количества  размер-
ностей,  т.е.  здесь  содержится
указание на конец массива.
  Байт  4  содержит  размерность
массива.
  Байты 5, 6  содержат  количес-
тво элементов в  первом  измере-
нии.  Если  размерность  массива
более, чем 1, то:
  Байты 7, 8  содержат  количес-
тво элементов во втором  измере-
нии; и т.д. После этого идут са-
ми  элементы  массива:  по  пять
байтов на  каждый  элемент.  Для
многомерных  массивов    порядок
следования   данных   следующий:
b(1,1),b(1,2), b(1,3), b(2,1)...
b(3,3).

        Переменные цикла

  Первый байт:

   ┌──┬──┬──┬──┬──┬──┬──┬──┐
   │1 │1 │1 │б │у │к │в │а │
   └──┴──┴──┴──┴──┴──┴──┴──┘

  Далее:
  5 байтов - текущее значение;
  5 байтов - конечное значение;
  5 байтов - шаг;
  2 байта - номер строки возвра-
            та;
  1  байт - номер  оператора   в
строке, к  которому  выполняется
возврат.

     Символьная переменная

  Первый байт:

   ┌──┬──┬──┬──┬──┬──┬──┬──┐
   │0 │1 │0 │б │у │к │в │а │
   └──┴──┴──┴──┴──┴──┴──┴──┘

  Далее:
  2 байта - длина строки;
  x байтов - текст строки.

       Символьный массив

  Первый байт:

   ┌──┬──┬──┬──┬──┬──┬──┬──┐
   │1 │1 │0 │б │у │к │в │а │
   └──┴──┴──┴──┴──┴──┴──┴──┘

  Далее:
  2  байта - указание  на  конец
массива;
  1 байт - размерность;
  2 байта - длина в первом изме-
рении;
  ..............................
  2  байта - длина  в  последнем
измерении.
  Далее: по одному байту на каж-
дый элемент.