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

[Barmaley_m]

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

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