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