Важная информация

User Tag List

Страница 1 из 2 12 ПоследняяПоследняя
Показано с 1 по 10 из 18

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

  1. #1
    Master
    Регистрация
    08.05.2007
    Адрес
    Dnepropetrovsk
    Сообщений
    961
    Спасибо Благодарностей отдано 
    0
    Спасибо Благодарностей получено 
    0
    Поблагодарили
    0 сообщений
    Mentioned
    3 Post(s)
    Tagged
    0 Thread(s)

    Question Таблица переходов (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шт), и они короткие (ограниченность дистанции перехода не играет роли). Может быть, у кого-нибудь возникнут идеи получше?
    Последний раз редактировалось Barmaley_m; 10.01.2019 в 03:16.

  2. #1
    С любовью к вам, Yandex.Direct
    Размещение рекламы на форуме способствует его дальнейшему развитию

  3. #2
    Master
    Регистрация
    24.05.2005
    Адрес
    г. Запорожье, Украина
    Сообщений
    881
    Спасибо Благодарностей отдано 
    56
    Спасибо Благодарностей получено 
    47
    Поблагодарили
    26 сообщений
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    если количество переходов не больше 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
    Последний раз редактировалось shurik-ua; 10.01.2019 в 04:12.

  4. #3
    Master
    Регистрация
    08.05.2007
    Адрес
    Dnepropetrovsk
    Сообщений
    961
    Спасибо Благодарностей отдано 
    0
    Спасибо Благодарностей получено 
    0
    Поблагодарили
    0 сообщений
    Mentioned
    3 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от 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 такта. Но годится, если нужно снять ограничения на дистанцию перехода.

  5. #4
    Guru Аватар для goodboy
    Регистрация
    27.02.2005
    Адрес
    москва
    Сообщений
    11,136
    Записей в дневнике
    1
    Спасибо Благодарностей отдано 
    9
    Спасибо Благодарностей получено 
    109
    Поблагодарили
    64 сообщений
    Mentioned
    4 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

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

  6. #5
    Master
    Регистрация
    08.05.2007
    Адрес
    Dnepropetrovsk
    Сообщений
    961
    Спасибо Благодарностей отдано 
    0
    Спасибо Благодарностей получено 
    0
    Поблагодарили
    0 сообщений
    Mentioned
    3 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

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

  7. #6
    Master
    Регистрация
    24.05.2005
    Адрес
    г. Запорожье, Украина
    Сообщений
    881
    Спасибо Благодарностей отдано 
    56
    Спасибо Благодарностей получено 
    47
    Поблагодарили
    26 сообщений
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    вот ещё вариант - если переходов не больше 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 тактов

  8. #7
    Guru Аватар для Shiny
    Регистрация
    19.01.2017
    Адрес
    г. Арзамас
    Сообщений
    2,119
    Записей в дневнике
    36
    Спасибо Благодарностей отдано 
    0
    Спасибо Благодарностей получено 
    12
    Поблагодарили
    5 сообщений
    Mentioned
    2 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

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

    Если извращаться до конца, то можно разместить в таблице 256б мл. байт адрес перехода и далее ст. байт адреса перехода
    Код:
    ;A=num
     ld h, jumpt/256
     ld l,a
     ld a,(hl)
     inc h
     ld h,(hl)
     ld l,a
     jp (hl)

  9. #8
    Guru Аватар для JV-Soft
    Регистрация
    14.05.2015
    Адрес
    г. Харьков, Украина
    Сообщений
    2,491
    Спасибо Благодарностей отдано 
    31
    Спасибо Благодарностей получено 
    60
    Поблагодарили
    18 сообщений
    Mentioned
    2 Post(s)
    Tagged
    1 Thread(s)

    По умолчанию

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

    Арфы нет ,возьмите бубен
    Безумие это повторение одного и того же в ожидании другого результата.


    Сайт http://p-45.zzz.com.ua
    Amiga A500
    Восстановлен(2018) дополнен и в строю - Pentagon (1991) 1024k (256kb ROM 4 конфигурации ПЗУ)/turbo 7 мгц/кеш 32кб/covox/ TS /AY mouse/fdd 3.5" /Nemo-Ide/10gb HDD (DNA-OS)
    Восстановлен(2015) и в строю - Харьков 128
    Восстановлен(2016) ZX-Дигитайзер

    Ждут паяльника - пентагон 48 , pentagon 128.
    [свернуть]

  10. #9
    Guru Аватар для Shiny
    Регистрация
    19.01.2017
    Адрес
    г. Арзамас
    Сообщений
    2,119
    Записей в дневнике
    36
    Спасибо Благодарностей отдано 
    0
    Спасибо Благодарностей получено 
    12
    Поблагодарили
    5 сообщений
    Mentioned
    2 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

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

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

  11. #10
    Master
    Регистрация
    24.05.2005
    Адрес
    г. Запорожье, Украина
    Сообщений
    881
    Спасибо Благодарностей отдано 
    56
    Спасибо Благодарностей получено 
    47
    Поблагодарили
    26 сообщений
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от Shiny Посмотреть сообщение
    Если извращаться до конца, то можно разместить в таблице 256б мл. байт адрес перехода и далее ст. байт адреса перехода
    тоже думал об этом - только непонятно как эти таблицы будут генерироваться во время ассемблирования.

Страница 1 из 2 12 ПоследняяПоследняя

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

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

Эту тему просматривают: 1 (пользователей: 0 , гостей: 1)

Похожие темы

  1. частотная таблица
    от goodboy в разделе Музыка
    Ответов: 36
    Последнее: 26.07.2017, 13:41
  2. Программы переходов экрана
    от AAA в разделе Софт
    Ответов: 2
    Последнее: 19.03.2013, 18:02
  3. Настроечная таблица
    от Addison в разделе Софт
    Ответов: 11
    Последнее: 19.07.2009, 20:15
  4. Кворум + 5V + TV = Шахматная Таблица
    от JeRrS в разделе Кворум
    Ответов: 1
    Последнее: 07.10.2006, 14:19
  5. Имитация GOTO из машкода
    от Jukov в разделе Программирование
    Ответов: 7
    Последнее: 01.10.2006, 15:12

Ваши права

  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения
  •