CODING - The Оптимизация - построение таблицы частоты повторения байтов.

<b>CODING</b> - The Оптимизация - построение таблицы частоты повторения байтов.

AY-Track:       L  I  G  H  T             
__________________________________________


(C)1999 DaniEl/PGC/BDA and MAX/Cyberax/BDA
__________________________________________


           The оптимизация #02


   Если вы уже закодили и  соптимизиривали
все что смогли, то сегодня я вам предлагаю
поломать голову.
   Задача: Построить таблицу частоты  пов-
торения байтов. На основе  массива  длиной
CODLEN. Первый  байт таблицы самый частый,
последний,  соответственно, самый  редкий,
если какие-то коды в  массиве  отсуствуют,
то частота  повторения данного байта равна
нулю.
   Ниже  приводится  листинг,  выполняющий
данную задачу. От вас требуется попытаться
соптимизировать данную  процедурку (сокра-
тить  объем  объектного  кода). Результаты
обязательно опубликуем в последующих номе-
рах Deja VU.
   Описывать алгоритм работы не  буду, по-
пытайтесь сами разобраться. Скажу  только,
что сначала создается таблица размером 512
байтов; первые два байта - количество  ко-
дов #00 в  массиве  длиной  CODLEN, вторые
два байта - количество кодов #01, и т. д.,
до #FF.


;(C) 19.02.1999 DaniEl/BDA
;Last optimization 22.02.1999


       ORG #8000


CODLEN EQU #4000; длина кодового блока
STRTAD EQU #C000; старт кодового блока

START  DI
       LD HL,D_BUFF
       PUSH HL
       LD DE,D_BUFF+1
       LD BC,#2FF
       SUB A
       LD (HL),A
       LDIR


       LD B,A
       POP IX; IX=D_BUFF
M1     PUSH BC
       LD DE,0
       LD BC,CODLEN
       LD HL,STRTAD
LOOP   CPIR
       JR NZ,JUMP
       INC DE
       JP PE,LOOP
JUMP   LD (IX+0),E
       LD (IX+1),D
       INC IX
       INC IX
       POP BC
       INC A
       DJNZ M1


       LD IY,KERNAL
       LD DE,CODLEN
L2     LD IX,D_BUFF
       LD BC,0
L1     LD L,(IX+0)
       LD H,(IX+1)
       OR A
       SBC HL,DE
       CALL Z,MAX
L3     INC IX
       INC IX
       INC C
       DJNZ L1


       DEC DE
       LD A,D
       OR E
       JR NZ,L2
       LD IY,23610
       EI
       RET


MAX    LD (IY+0),C
       INC IY
       RET


D_BUFF DEFS #200; Первые  2  байта - коли-
                ;чество  байтов #00, далее
                ;два байта - кол-во байтов
                ;#01 и т.д., до #FF.

KERNAL DEFS #100; Результат работы-таблич-
                ;ка   частоты   повторений
                ;байтов. Первый-самый час-
                ;тый, последний-самый ред-
                ;кий.

   Длина  процедуры  ровно 100 байтов. Не-
достаток - очень медленная работа,около 40
секунд на  один  банк  памяти (зависит  от
плотности данных).
   После написания этой процедуры, ее  ре-
шил  соптимизировать  MAX/Cyberax/BDA. Ре-
зультатом  его  работы  явилась  процедура
длиной 93 байта и  работающая  максимум  4
секунды на один банк.
   Недостатки - привязка к адресам, вырав-
ненным по границе 256 байтов (с начала па-
раграфа), кроме того, небольшое отклонение
от поставленной цели, а конкретно, резуль-
тирующая таблица содержит полный  диапазон
байтов от #00 до #FF,в то время как она не
должна содержать  байтов, отсутствующих  в
исследуемом массиве.
   Алгоритм   данной  процедуры  абсолютно
другой. Сначала создается таблица 512 бай-
тов (два параграфа),в первом параграфе на-
ходятся младшие байты, во втором- старшие.
Вместе, старший и  младший  байт, образуют
количество повторений в исследуемом масси-
ве в диапазоне от #00 до #FF. Далее проис-
ходит сортировка по следующему  принципу -
сравниваются два первых элемента в  табли-
це, если второй больше первого, то они ме-
няются местами, и далее сравниваются  эле-
менты второй и третий ..., и т.д. В  итоге
сортируются  обе  таблицы. (но  нам  нужна
только вторая - 256 байтов)
   Для  максимального  быстродействия  MAX
решил почти полностью  отказаться  от  ис-
пользования  индексных  регистров, а также
использовать в больших циклах  команды  JP
вместо JR.
   Вот листинг данной процедуры:

;(C) MAX/CYBERAX/BDA, 02.1999
;OPTIMIZATION

       ORG #7000


BUFF   EQU #80; СТАРШИЙ БАЙТ  АДРЕСА #8000
               ;ДЛЯ ТАБЛИЦЫ 512 БАЙТОВ.
TABLE  EQU BUFF+2; СТАРШ.БАЙТ АДРЕСА #8200
                 ;ДЛЯ ТАБЛИЦЫ 256 БАЙТОВ.

BLOCK  EQU #C000; СТАРТОВЫЙ АДРЕС БЛОКА.
CODLEN EQU #4000; ДЛИНА БЛОКА

MK_TAB  LD HL,BUFF*256
        LD DE,BUFF*256+1
        LD BC,#200
        LD (HL),L
        LDIR
MK_TB   LD (HL),L
        INC L
        JP NZ,MK_TB
        LD H,BUFF
        LD DE,BLOCK
        LD C,CODLEN/256;СТАРШИЙ БАЙТ ДЛИНЫ
                      ;B=0
TB_LP   LD A,(DE)
        LD L,A
        INC (HL)
        JP NZ,NO_HIGH
        INC H
        INC (HL)
        DEC H
NO_HIGH INC DE
        DJNZ TB_LP
        DEC C
        JP NZ,TB_LP


;Начало сортировки

SORT0   LD HL,BUFF*256
        LD HX,0
SORT1   LD E,(HL)
        INC H
        LD D,(HL)
        INC H
        LD A,(HL)
        INC L
        DEC H
        LD B,(HL)
        DEC H
        LD C,(HL)
        EX DE,HL
        AND A
        SBC HL,BC
        EX AF,AF'
        ADD HL,BC
        EX AF,AF'
        EX DE,HL
        JR NC,NO_SWAP
        LD (HL),E
        INC H
        LD (HL),D
        INC H
        LD E,(HL)
        LD (HL),A
        DEC L
        LD (HL),E
        DEC H
        LD (HL),B
        DEC H
        LD (HL),C
        INC L
        LD HX,#FF
NO_SWAP LD A,L
        INC A
        JP NZ,SORT1
        INC HX
        JP Z,SORT0
        RET


   Может  быть  вас  заинтересует  область
применения данных процедур? Отвечу, что их
можно  применить, например, при  написании
различных  упаковщиков. А  интересно - что
думает по этому поводу Дмитрий Пъянков  из
Горно-Алтайска?

      И пусть удача вас не покидает!