Секреты оптимизации. Часть 1

Реализация Case of на асме для AVR-ов и PIC-ов

Часть 1. Реализация оператора "case of" на ассемблере

Часть 2. Как инвертировать порядок бит в байте (алгоритмы и примеры на ассемблере)

В этой статье, на примере двух контроллеров, показано как на ассемблере можно различными способами организовать аналог оператора языков высокого уровня case of. Кроме того, вы увидите преимущества архитектуры контроллеров AVR с их расширенным набором команд и доступом к счётчику команд (что также открывает интересные дополнительные возможности).

Итак, представьте, что у нас есть некоторая переменная и, в зависимости от её значения, нам нужно выполнить тот или иной набор действий. Ну, например, прислали вы контроллеру команду по com-порту и, в зависимости от того какая это команда, нужно сделать те или иные действия. В языках высокого уровня такие вещи проще всего реализуются с помощью оператора case of, примерно вот так (запись в зависимости от языка может быть различной, но смысл такой):

  A: integer        ; есть у нас некая переменная A
   ...              ; где-то здесь мы получили в A какое-то число
  case A of         ; выбираем какой оператор выполнять, в зависимости от A
  { 1: оператор 1   ; если A=1 - выполняем этот оператор
    2: оператор 2   ; если A=2 - выполняем этот оператор
    3: оператор 3   ; если A=3 - выполняем этот оператор
       ...
    else оператор E ; выполняется в случае ошибки (если ничего не выбрали)
  }

Теперь давайте подумаем, как реализовать то же самое на асме? Итак, пусть мы имеем некое число в регистре T0 и K вариантов дальнейших действий, в зависимости от этого числа. Если это число равно Ch1, то выполняется оператор 1, если Ch2 - оператор 2, ... если Chk - оператор k.

Очевидно, что самый простой путь - сравнить значение переменной T0 со всеми возможными вариантами значения Ch и в случае совпадения выполнить соответствующее действие.

Для PIC-контроллеров такой метод будет выглядеть вот так:

 movf  T0,0     ; копируем значение из регистра T0 в регистр w
 xorlw Ch1      ; сравниваем w с константой Ch1 (содержимое w изменится)
                ;(если равны - установится флаг Z)
 btfsc STATUS,Z ; проверяем флаг Z, если он
   goto Op1     ; не установлен - пропускаем эту команду
 movf  T0,0
 xorlw Ch2
 btfsc STATUS,Z
   goto Op2
 ...
 movf  T0,0
 xorlw Chk
 btfsc STATUS,Z
   goto Opk
 goto OpE       ; переход к обработчику ошибки
Op1: ...        ; код "оператора" 1
     ...
     goto Next
Op2: ...        ; код "оператора" 2
     ...
     goto Next
 ...
 ...
OpK: ...        ; код "оператора" k
     ...
     goto Next
OpE: ...        ; код обработчика ошибки
 ...
Next:
 ...            ; продолжение программы

То есть, - копируем в регистр, который не жалко испортить, сравниваем, проверяем результат сравнения и переходим или не переходим (в этом случае вместо перехода выполняется nop) по нужному адресу. Итого, по 4 команды для каждого варианта.

Для контроллеров AVR аналогичный метод выглядел бы вот так:

 cpi  T0,Ch1 ; сравниваем T0 с константой Ch1
             ; (при этом содержимое T0 не изменится)
 breq Op1    ; если равны - переходим к выполнению оператора 1
 cpi  T0,Ch2
 breq Op2
 ...
 cpi  T0,Chk
 breq Opk
 rjmp OpE    ; переход к обработчику ошибки
Op1: ...     ; код "оператора" 1
     ...
     rjmp Next
Op2: ...     ; код "оператора" 2
     ...
     rjmp Next
 ...
 ...
OpK: ...     ; код "оператора" k
     ...
     rjmp Next
OpE: ...     ; код обработчика ошибки
 ...
Next:
 ...         ; продолжение программы

Как видите, код для AVR получается в два раза короче. Во-первых, потому что сравнение не портит содержимое регистра (значит нам не нужно резервное копирование T0 в дополнительный регистр) и, во-вторых, потому что в AVR проверку результата сравнения и переход можно выполнить одной командой.

Далее, если числа Ch1, Ch2, ... Chk расположены по порядку друг за другом ( скажем 1,2,3,4,5 или 7,8,9,10), то оба кода можно упростить.

Код для контроллеров PIC в этом случае будет вот таким:

 movlw Ch1      ; загружаем в w значение Ch1
 subwf T0,1     ; вычисляем T0-Ch1
                ; т.е. если ,например, у нас был ряд 3, 4, 5, 6
                ; и T0 было равно 5, то теперь будет ряд 0,1,2,3
                ; и T0 будет равно 2
 btfsc Status,C ; если значение в T0 было меньше Ch1,
                ; то после вычитания установится флаг C
 goto OpE
 btfsc Status,Z ; если T0 было равно Ch1, то установится флаг Z
  goto Op1
 decfsz T0,1    ; вычитаем 1, если результат 0 - пропускаем следующую команду
   goto Not_op2
Op2: ...
     ...
     goto Next
Not_op2:
 decfsz T0,1
   goto Not_op3
Op3: ...
     ...
     goto Next
Not_op3:
 ...
 ...
 decfsz T0,1
   goto OpE
OpK: ...
     ...
     goto Next
OpE:
 ...
     goto Next
Op1: ...
     ...
Next:
 ...           ; продолжение программы

Ага, код для пика почти сравнялся по длине с кодом для AVR. Теперь мы для каждого сравнения и перехода тратим две команды. Однако, как вы увидите в дальнейшем, в некоторых случаях можно написать код ещё короче. Кроме того, в приведённых алгоритмах переход к выполнению различных "операторов" занимает различное количество времени, поскольку проверки выполняются последовательно и прежде чем мы дойдём до проверки равенства T0 и Chk - мы должны проверить ещё k-1 условий. Этот факт, делает невозможным использование подобных алгоритмов в различном "секретном" оборудовании (типа шифровальных железок или кодовых замков), поскольку различие во времени перехода на разные участки кода - это потенциальная уязвимость.

И что же делать? А вот теперь давайте поговорим о том, как разработчики AVR подарили нам доступ к счётчику команд и что это нам даёт.

Итак, в контроллерах AVR мы имеем доступ к стеку (команды push, pop), т.е. мы можем сохранить число из регистра в стек и можем загрузить число из стека в регистр. Ну и что? А то, что при вызове подпрограммы контроллер сохраняет в стеке адрес следующей инструкции, а при выполнении команды ret он этот адрес из стека загружает. А раз мы можем править стек, - значит мы можем править и счётчик команд по своему усмотрению.

Пока непонятно как нам это поможет, да? Тогда смотрим на приведённый ниже код:

 cpi T0,Ch1       ; сравниваем T0 и Ch1
 brlo OpE         ; если T0 < Ch1 - переход к обработчику ошибки
 cpi T0,(Chk+1)   ; сравниваем T0 и Chk+1
 brsh OpE         ; если T0 > или = Chk+1 - переход к обработчику ошибки
 subi T0,Ch1      ; вычисляем T0-Ch1
                  ; т.е. если ,например, у нас был ряд 3, 4, 5, 6
                  ; и T0 было равно 5, то теперь будет ряд 0,1,2,3
                  ; и T0 будет равно 2 
 rcall Start_Case ; сохраняем в стек адрес команды, следующей за rcall
                  ; и переходим на метку Start_Case (т.е. фактически - к
Start_Case:       ; следующей команде, сохранив её адрес в стеке)
 pop ZH           ; извлекаем из стека 16-ти битный указатель
 pop ZL           ; на команду pop ZH в регистр Z
 adiw ZL,7        ; вычисляем начальный адрес блока переходов
                  ; (добавляем 7, поскольку у нас полученный через стек
                  ; адрес команды pop ZH сдвинут от начала блока
                  ; переходов на 7 команд
 add ZL,T0        ; добавляем T0 (вычисляем адрес команды
                  ; перехода на нужный "оператор")
 brcc NotC        ; если флаг переноса не установился -
 inc ZH           ; пропускаем эту команду
NotC:
 ijmp             ; и переходим по вычисленному адресу в блок переходов
                  ; здесь можно было сохранить в стек ZL и ZH
                  ; а потом выполнить команду ret, но
                  ; ijmp - короче и быстрее
 rjmp Op1     ; начало блока переходов
 rjmp Op2
  ...
 rjmp Opk     ; конец блока переходов
Op1:  ...
      ...
 rjmp Next
Op2:  ...
      ...
 rjmp Next
  ...
  ...
OpE:  ...
      ...
Next:
  ...          ; продолжение программы

Теперь выбор нужного "оператора" занимает одинаковое время для всех вариантов и, плюс к этому, для добавления N новых вариантов нужно добавить всего N команд. То есть без учёта 13-ти дополнительных команд, требуемых на подготовку такого трюка, нам требуется всего одна команда на каждый вариант.

Если у нас меньше 13 различных вариантов, то никаких преимуществ в длине и времени выполнения последний код не даёт, но если вариантов больше, то последний код будет короче и быстрее, чем первый.

Часть 1. Реализация оператора "case of" на ассемблере

Часть 2. Как инвертировать порядок бит в байте (алгоритмы и примеры на ассемблере)

radiohlam.ruтеорияконтроллеры и программирование

Понравилась статья? Поделись с друзьями!

Обсудить эту статью на форуме

 
Rambler's Top100 © 2009 - Материалы сайта охраняются законом об авторском праве