Таблица переходов (computed goto)
Здравствуйте, друзья.
Задумался я тут об эффективном (по скорости) решении следующей задачи: выполнить переход на одну из нескольких веток программы в зависимости от значения параметра A.
Например, одно из возможных решений выглядит так:
Код:
LD HL,JUMP_TBL ;10
ADD A,A ;4
LD C,A ;4
LD B,0 ;7
ADD HL,BC ;11
LD A,(HL) ;7
INC HL ;6
LD H,(HL) ;7
LD L,A ;4
JP (HL) ;4
JUMP_TBL:
DW ROUTINE1
DW ROUTINE2
DW ROUTINE3
....
Данное решение канонично и универсально, но имеет 2 недостатка. 1) Скорость - 64 такта; 2) используется две регистровые пары.
Улучшенный вариант:
Код:
LD HL,JUMP_TBL ;10
ADD A,A ;4
ADD A,L ;4
LD L,A ;4
ADC A,H ;4
SUB L ;4
LD H,A ;4
LD A,(HL) ;7
INC HL ;6
LD H,(HL) ;7
LD L,A ;4
JP (HL) ;4
JUMP_TBL:
DW ROUTINE1
DW ROUTINE2
DW ROUTINE3
....
Здесь переход происходит за 62 такта и используется только одна регистровая пара.
Если гарантировать размещение таблицы без пересечения границы 256-байтных страниц, то можно еще сэкономить:
Код:
LD HL,JUMP_TBL ;10
ADD A,A ;4
ADD A,L ;4
LD L,A ;4
LD A,(HL) ;7
INC L ;4
LD H,(HL) ;7
LD L,A ;4
JP (HL) ;4
JUMP_TBL:
DW ROUTINE1
DW ROUTINE2
DW ROUTINE3
....
Исполняется за 48 тактов.
Если размещать таблицу в начале 256-байтной страницы - то:
Код:
LD H, HIGH(JUMP_TBL) ;7
ADD A,A ;4
LD L,A ;4
LD A,(HL) ;7
INC L ;4
LD H,(HL) ;7
LD L,A ;4
JP (HL) ;4
.ALIGN 256
JUMP_TBL:
DW ROUTINE1
DW ROUTINE2
DW ROUTINE3
....
Этот вариант исполняется за 41 такт.
Если все ветки, на которые производится переход, находятся в той же 256-байтной странице, что и таблица, то можно еще сэкономить:
Код:
LD H, HIGH(JUMP_TBL) ;7
LD L,A ;4
LD L,(HL) ;7
JP (HL) ;4
.ALIGN 256
JUMP_TBL:
DB LOW(ROUTINE1)
DB LOW(ROUTINE2)
DB LOW(ROUTINE3)
....
Данный вариант я уже не могу улучшить, он исполняется за 22 такта. По-прежнему остается проблема использования HL, в которой можно было бы передавать параметры, если бы эта пара не использовалась для перехода. Ну и серьёзные ограничения по размещению кода.
Без использования HL задачу можно решить, например, так:
Код:
ADD A,A ;4
LD (JT+1),A ;13
JT: JR JUMP_TBL ;12
JUMP_TBL:
JR ROUTINE1 ;12
JR ROUTINE2 ;12
JR ROUTINE3 ;12
....
Исполняется за 41 такт. Достоинства: не используется HL. Недостатки: нельзя размещать в ПЗУ; дистанция перехода ограничена.
При малом количестве веток можно еще рассмотреть такой вариант:
Код:
OR A ;4
JR Z,ROUTINE1 ;7/12
DEC A ;4
JR Z,ROUTINE2 ;7/12
DEC A ;4
JR Z,ROUTINE3 ;7/12
....
Тут полная свобода по размещению кода; исполняется за 16 тактов в лучшем случае, а в худшем - за (N-1)*11+16, где N - количество веток. Можно размещать в ПЗУ по произвольным адресам, но дистанция перехода ограничена.
Интересуют в первую очередь решения, где подпрограмм мало (4-8шт), и они короткие (ограниченность дистанции перехода не играет роли). Может быть, у кого-нибудь возникнут идеи получше?
