Таблица переходов (computed goto)

**Barmaley_m** · 10.01.2019, 03:08

Здравствуйте, друзья.

Задумался я тут об эффективном (по скорости) решении следующей задачи: выполнить переход на одну из нескольких веток программы в зависимости от значения параметра 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шт), и они короткие (ограниченность дистанции перехода не играет роли). Может быть, у кого-нибудь возникнут идеи получше?

**Advertiser** · 10.01.2019, 03:08

**shurik-ua** · 10.01.2019, 04:09

если количество переходов не больше 255/3
таблица должна быть выровнена на 256 байт

Код:

  ld h, high table
  ld l,a
  rl a
  add a,l
  ld l, a
  jp (hl)
table:
  jmp subr1
  jmp subr2
  ...

такты не считал - но вроде тоже можно юзать

- - - Добавлено - - -

Сообщение от Barmaley_m

Без использования 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. Недостатки: нельзя размещать в ПЗУ; дистанция перехода ограничена.

ну или так - если оптимизация по скорости и памятью можно жертвовать:

Код:

  add a,a
  add a,a
  ld (jt+1),a
jt:
  jr jump_tbl
jump_tbl:
  jmp subr1
  nop
  jmp subr2
  nop
  ...

jmp кстати выполняется за 10 тактов а не за 12 как jr

**Barmaley_m** · 10.01.2019, 20:49

Сообщение от shurik-ua

таблица должна быть выровнена на 256 байт

Спасибо, хорошие варианты. В первом из них ошибка - исправляю и считаю такты по твоим вариантам ниже:

Код:

  ld h, high table ;7
  ld l,a ;4
  add a,a ;4
  add a,l ;4
  ld l, a ;4
  jp (hl) ;4
table:
  jmp subr1 ;10
  jmp subr2
  ...

Тут получается переход через 37 тактов; дистанция перехода не ограничена. По достоинствам/недостаткам сравнимо с моим вариантом, который 41 такт, но быстрее. Спасибо.

Сообщение от shurik-ua

ну или так - если оптимизация по скорости и памятью можно жертвовать

Когда требуется размещать таблицу с выравниванием на 256 байт - то экономия памяти в 1 байт на подпрограмму - мелочь. Как же я сам не догадался, что можно команды jp размещать через nop! Это ведь существенно ускоряет вычисление адреса для jp (hl).

Код:

  add a,a ;4
  add a,a ;4
  ld (jt+1),a ;13
jt:
  jr jump_tbl ;12
jump_tbl:
  jp subr1 ;10
  nop
  jp subr2
  nop
  ...

Тоже хорошая идея. Исполняется за 43 такта - сравнимо с моим вариантом ld (jt+1),a и jr/jr, который исполняется за 41 такт. Но в твоём варианте зато нет ограничения на дистанцию перехода.

Сообщение от shurik-ua

jmp кстати выполняется за 10 тактов а не за 12 как jr

Это да, но для jp надо затратить лишние 4 такта на дополнительную команду add a,a. Так что суммарно получается проигрыш в 2 такта. Но годится, если нужно снять ограничения на дистанцию перехода.

**goodboy** · 10.01.2019, 22:14

в AYплейерах часто используется таблица с однобайтным смещением.
a=x
...
ld hl,table
ld c,a
ld b,0
add hl,bc
ld c,(hl)
add hl,bc
jp (hl)

**Barmaley_m** · 11.01.2019, 00:07

Сообщение от goodboy

в AYплейерах часто используется таблица с однобайтным смещением.

Спасибо. Тоже имеет право на существование. По скорости - 54 такта. Достоинства: нет требований на выравнивание. Недостаток: использует 2 регистровые пары.

**shurik-ua** · 13.01.2019, 18:28

вот ещё вариант - если переходов не больше 128:

Код:

  add a,a                4
  ld (m0+1),a          13
m0:
  ld hl,(jmp_table)    16
  jmp (hl)                4
align 256
jmp_table:
  dw subr1
  dw subr2
  ...

37 тактов

**Shiny** · 14.01.2019, 11:59

эх, теоретики(: в демо используется переход по сформированной таблице, на которую указывает стек
ret - вот все такты

Если извращаться до конца, то можно разместить в таблице 256б мл. байт адрес перехода и далее ст. байт адреса перехода

Код:

;A=num
 ld h, jumpt/256
 ld l,a
 ld a,(hl)
 inc h
 ld h,(hl)
 ld l,a
 jp (hl)

**JV-Soft** · 14.01.2019, 15:50

Очень полезная тема , давайте еще извращений , мне в VGM плеере за 69 тактов надо выбрать команду ,сделать переход на ее обработчик, выбрать данные, вывести их на ямаху )

**Shiny** · 14.01.2019, 16:41

Сообщение от JV-Soft

Очень полезная тема , давайте еще извращений , мне в VGM плеере за 69 тактов надо выбрать команду ,сделать переход на ее обработчик, выбрать данные, вывести их на ямаху )

мсье знает толк в извращениях (:

**shurik-ua** · 14.01.2019, 20:24

Сообщение от Shiny

Если извращаться до конца, то можно разместить в таблице 256б мл. байт адрес перехода и далее ст. байт адреса перехода

тоже думал об этом - только непонятно как эти таблицы будут генерироваться во время ассемблирования.

ZXPRESS •	ZXART •
ZXTUNES •	ZX Spectrum Old Demos •
Virtual TR-DOS •	World of Spectrum •

User Tag List

Тема: Таблица переходов (computed goto)

Опции темы

Отображение

Таблица переходов (computed goto)

Информация о теме

Пользователи, просматривающие эту тему

Похожие темы

частотная таблица

Программы переходов экрана

Настроечная таблица

Кворум + 5V + TV = Шахматная Таблица

Имитация GOTO из машкода

Ваши права