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