Inferno #10
30 апреля 2007

For Coderz - Код Грея и оптимизация программ.

     Код Грея и оптимизация программ

Lord Vader 

             I. Что это такое

   Код Грея  обычно применяется в тех слу─
чаях, когда измеряемый параметр изменяется
с шагом 1 последовательно во времени, нап─
ример, в механических валкодерах,некоторых
АЦП и т.д. Классический пример использова─
ния  кода Грея - сигналы с оптопар механи─
ческой мышки, имеющие вид

X:  _/~~~___/~~~_ 
Xq: ___/~~~___/~~~ 

и являющиеся 2-битным кодом Грея.

   Основное свойство кода Грея - при пере─
ходе  к соседнему состоянию в N-битной ве─
личине  в коде Грея меняется только 1 бит.
Например, для 4-битной величины последова─
тельность кодов Грея будет следующей:
 

  0000
  0001
  0011
  0010
  0110
  0111
  0101
  0100
  1100
  1101
  1111
  1110
  1010
  1011
  1001
 1000

   Отсюда видно правило формирования кодов
Грея: на  каждом  шаге надо поменять самый
младший бит,который не приведёт к повторе─
нию кода.

   Возможно  также и непосредственно пере─
водить  обычный  двоичный код в код Грея и
назад. Перевод из обычного кода в код Грея
(примеры  на  ассемблере Z80) для 8-битной
величины:

 Bin2Gray 
         ;IN:  A - in binary code
         ;OUT: A - in Gray code
         LD    C,A
         SRL   C
         XOR   C
        RET

   Перевод обратно:

 Gray2Bin 
         ;IN:  A - in Gray code
         ;OUT: A - in binary code
         LD    C,A
        XOR   A
 G2B_L 
         XOR   C
         SRL   C
         JR    NZ,G2B_L
        RET

   Более подробно о коде Грея можно прочи─
тать в [1] и [2].


         II. Примеры оптимизации

   Представьте себе, что требуется напеча─
тать  символ  8х8  в линейный буфер экрана
(где строчки идут друг за другом и для пе─
рехода на соседнюю надо прибавить к адресу
32 ). 
   Код получится такой:
 

        DUP   8
         LD    A,(DE)
         INC   E
         LD    (HL),A
         ADD   HL,BC ;BC=32
       EDUP

   Для прибавления 32 потребовалась аж це─
лая регистровая пара. Можно делать так:
 

         LD    A,L
         ADD   A,32
        LD    L,A

   Но  либо это совсем медленно, либо тре─
бует дополнительного регистра для хранения
числа 32.

   А  теперь попробуем перебирать адреса в
коде Грея:
 

         LD    A,(DE)
         INC   E ; SET 0,E
         LD    (HL),A
        SET   5,L    ; 000>001
 

         LD    A,(DE)
         SET   1,E
         LD    (HL),A
        SET   6,L    ; 001>011
 

         LD    A,(DE)
         DEC   E ; RES 0,E
         LD    (HL),A
        RES   5,L    ; 011>010
 

         LD    A,(DE)
         SET   2,E
         LD    (HL),A
        SET   7,L    ; 010>110
 

         LD    A,(DE)
         INC   E
         LD    (HL),A
        SET   5,L    ; 110>111
 

         LD    A,(DE)
         RES   1,E
         LD    (HL),A
        RES   6,L    ; 111>101
 

         LD    A,(DE)
         DEC   E
         LD    (HL),A
        RES   5,L    ; 101>100
 

         LD    A,(DE)
        LD    (HL),A ; 100

   Таким образом,мы как минимум избавились
от использования дополнительных регистров,
прибавив  почти такт к каждому копированию
(вместо INC E : ADD HL,BC - 2 SET/RES'а ).
Если же переставить байтики шрифта соотве─
тствующим  образом, то  можно везде писать
INC E - выигрыш очевиден. 

   Аналогичную  технику можно использовать
и в других случаях (каких - сам думайте:).
Для удобства написания можно ввести 2 мак─
роса (пример для арабского ассемблера  aka
Аль-асма ;). 
 

        MACRO GRAY
         
         INC   E
         SET   5,L
         
         SET   1,E
         SET   6,L
         
         DEC   E
         RES   5,L
         
         SET   2,E
         SET   7,L
         
         INC   E
         SET   5,L
         
         RES   1,E
         RES   6,L
         
         DEC   E
         RES   5,L
         
       ENDM

 

        MACRO DOIT
         LD    A,(DE)
         LD    (HL),A
       ENDM

 И далее:
        
        GRAY  DOIT

lvd^mHm  lvd@dgap.mipt.ru 

               Литература:

1. П. Хоровиц, У. Хилл. 
"Искусство схемотехники", гл.8. 
2. http://en.wikipedia.org/wiki/Gray_code 



Другие статьи номера:

Ликбез - Аккумуляторы. Практика использования.

Ликбез - Аккумуляторы. Результаты опытов с различными аккумуляторами.

Возможности Спектрума - Описание формата ani-файлов на ZX.

Inferno - Авторы журнала.

Возможности Спектрума - Способы воспроизведения многоканальной музыки на бипере.

Возможности Спектрума - О поддержке формата DVD на ZX.

Gameland - О конкурсе нелепых (или корявых) игр для ZX Spectrum - Crap Games Competition.

Графика - Как быстро рисовать цветные картинки.

Inferno - Вступление от редактора.

Inferno - Ошибки в предыдущих номерах.

For Coderz - Код Грея и оптимизация программ.

For Coderz - Построение графического пользовательского интерфейса.

Форматы - Подробно о декодере jpeg.

Железо - Описание микросхемы К561ПУ4.

Inferno - Письма в редакцию.

Форматы - Формат пакованного файла MegaLZ.

Scorpion ZS - Структура разметки винчестера на компьютере Scorpion.

ZX Клоны - Мультиплатформенность на ZX Spectrum. Компьютеры SAM Coupe и MSX.

Реклама - Реклама NedoPC.

Inferno - Об оболочке.

Активный отдых - Команда "Спектрум" на соревновании по ночному ориентированию Окинчица 2004.

Sofтинка - Сравнительная таблица результатов упаковки кодовых файлов различными упаковщиками.

Реклама - Реклама King of Evil.

Sofтинка - Программы для печати в приложении к журналу.

Sofтинка - Музыкальный редактор Pro Tracker v3.71. История изменений.

Реклама - Реклама от В. Богдановича.

Железо - О некоторых RND-генераторах.

Возможности Спектрума - Аппаратный скроллинг на ZX Spectrum.

Pentagon - Синхроселектор видеосигнала на Pentagon. Проблемы и схема.

DIY - Универсальный TAPE интерфейс. Схема загрузки и записи с ленты.

Звук - Особенности звукового устройства TurboSound FM.

DIY - Схема анализатора состояния TTL вывода.

Будущее Спектрума - Видеоконтроллеры V9990. Расширение графических возможностей ZX Spectrum.

Sofтинка - Обновления в просмотрщиках картинок: ANSI viewer, MCX viewer.

Интервью - Интервью с музыкантом X-Raizor из Omega Hackers Group.


Темы: Игры, Программное обеспечение, Пресса, Аппаратное обеспечение, Сеть, Демосцена, Люди, Программирование

Похожие статьи:
От редакции
Конструктор - вопросы рассширения ОЗУ до 512 кб.
7 Origins - Семерка лучших origin'ов-мудрых и не очень выражений.

В этот день...   18 июля