Black Crow #06
01 июня 2001

Программистам - Интересный алгоритм печати текста 42 символа в строке.

   СЕКРЕТЫ ТЕКСТОВОГО ВЫВОДА   
                                         
(С) 2001 Иван Рощин                      
   Fido  : 2:5О2О/689.53                                      
   ZЧNеt : 5ОО:95/462.53                                      
   E-иаil: аsdеr_ffс@softhoие.nеt                             
   WWW   : httр://www.zх.ru/есho/rosсhin                      
-----------------------------------------
   Здесь  я  расскажу о приемах оптимиза-
ции,  используемых  при  выводе текстовых
сообщений на экран ZX-Sреctrum. Некоторые
из этих приемов могут быть использованы и
на  других  компьютерных  платформах, где
производится  печать текста в графическом
режиме.                                  
                                         
   Сначала  несколько общих слов. Как из-
вестно, в ZX-Sреctrum  реализован единст-
венный  графический  режим  с разрешением
256*192. Цвета в нем задаются не для каж-
дой  точки,  а  сразу для целого квадрата
8*8 - то есть фактически мы имеем не нас-
тоящее  цветное изображение, а раскрашен-
ное черно-белое.                         
                                         
   В  других  компьютерах  (например, РС)
наряду  с  графическими  режимами  обычно
имеются  и текстовые. Спектрум лишен этой
возможности, и на нем приходится выводить
текст  в графическом режиме. С одной сто-
роны, это медленнее и отнимает больше па-
мяти, но с другой стороны - размеры, фор-
ма  и  местоположение символов могут быть
любыми. В графическом режиме также стано-
вится   возможным  плавный  скроллинг при
просмотре текста, что несомненно повышает
удобство чтения.                         
                                         
   Я  буду  рассматривать  наиболее часто
встречающийся случай, когда шрифт задан в
растровом   виде  (бывают  еще  векторные
шрифты), и все его символы имеют одинако-
вую ширину и высоту.                     
                                         
   При  печати может быть использован как
шрифт  8*8,  находящийся в ПЗУ по адресам
#3D00-#3FFF  (там хранятся лишь изображе-
ния  символов  с  кодами  #20-#7F), так и
шрифт, загружаемый в ОЗУ (размеры и коли-
чество  символов  в  котором, само собой,
могут быть произвольными).               
                                         
   Процедура  печати символа обычно имеет
дело  с  такими  параметрами: код символа
(bytе),  координаты (х,y) и цвет. Коорди-
наты чаще всего задаются не в пикселах, а
в  знакоместах (под знакоместами я имею в
виду  области  размером  в  один символ).
Скажем,  при  использовании шрифта 8*8 на
экране  помещается 32 символа по горизон-
тали  и  24 по вертикали; соответственно,
координата х может изменяться от 0 до 31,
а  y - от 0 до 23. Начало координат (0,0)
традиционно располагается в верхнем левом
углу экрана.                             
                                         
   Как видим, происходит некоторая эмуля-
ция текстового режима с помощью графичес-
кого. В 99% случаев при этом используется
один  из следующих трех "текстовых" режи-
мов: 32*24 (шрифт 8*8), 42*24 (шрифт 6*8)
и 64*24 (шрифт 4*8). (Как вы можете заме-
тить,  в  режиме  42*24 четыре пиксела по
горизонтали  остаются неиспользованными -
обычно  их  либо  равномерно распределяют
справа  и слева, либо оставляют на какой-
то одной стороне.)                       
                                         
   В  режиме  32*24  каждый  символ может
иметь  свой цвет (что непосредственно вы-
текает из структуры спектрумовского экра-
на).  В  режимах 42*24 и 64*24 это невоз-
можно, но там каждое слово может быть ок-
рашено  в  свой  цвет  (если считать, что
слова разделены пробелами). Другие режимы
(скажем, 51*24 - при использовании шрифта
5*8) лишены и этого.                     
                                         
   О теории я сказал, кажется, уже доста-
точно. А теперь начнем оптимизировать! :)
                                         
   Обычно в шрифте под изображение каждо-
го  символа отводится восемь байт. Но до-
вольно  часто  такое представление оказы-
вается избыточным, так как некоторые биты
не  используются.  К  примеру, для шрифта
6*8  (рис.  1) два крайних столбца не за-
действованы и всегда равны нулю.         
Рис. 1 Когда шрифт расположен в ОЗУ, такое его представление вполне оправданно, как обеспечивающее достаточную скорость печа- ти. (Между прочим, когда печать символов 6*8 хотят сделать особенно быстрой, ис- пользуют целых четыре набора символов, каждый из которых сдвинут относительно другого на два пиксела по горизонтали - чтобы не тратить время на сдвиг при печа- ти каждого символа.) Но для экономии дис- кового пространства, занимаемого вашей программой, имеет смысл удалять из шрифта всю избыточную информацию. Экономия при этом может быть весьма значительной: так, шрифт из 256 символов 6*8, изначально занимавший #800 байт, уменьшится на четверть. А если в таком шрифте изображение символов реально зани- мает только 5*6 пикселов (т.е. между сим- волами предусмотрен обязательный пробел в один пиксел по горизонтали и два по вертикали), то он сократится более чем вдвое! Ниже приведена процедура, удаляющая из шрифта избыточную информацию. Смысл ис- пользуемых в ней констант fоnt_sх,fоnt_х, fоnt_sy и fоnt_y пояснен на рис. 2.
Рис. 2 SОURСЕ ЕQU #8000 ;здесь расположен ;исходный шрифт, DЕSТINY ЕQU #С000 ;а сюда поместим ;упакованный... КОLVО ЕQU #100 ;количество симво- ;лов (1-256) fоnt_sх ЕQU 1;эти параметры опреде- ;ляют используемую часть fоnt_sy ЕQU 1;матрицы 8*8 для преоб- ;разуемого шрифта fоnt_х ЕQU 5 fоnt_y ЕQU 6 DЕSТ_LЕN ЕQU ((fоnt_х*fоnt_y*КОLVО)+7)/8 ;длина упакованного шрифта ;в байтах ОRG #6000 LD НL,SОURСЕ LD IX,DЕSТINY LD Е,0 LD В,КОLVО М1 РUSН ВС РUSН НL LD ВС,fоnt_sy ADD НL,ВС LD В,fоnt_y М7 LD A,(НL) LD С,fоnt_sх INС С М2 DЕС С JR Z,М3 ADD A,A JR М2 М3 LD С,fоnt_х INС С М4 DЕС С JR Z,М5 ADD A,A RL (IX) INС Е ВIТ 3,Е JR Z,М4 INС IX LD Е,0 JR М4 М5 INС НL DJNZ М7 РОР НL LD ВС,8 ADD НL,ВС РОР ВС DJNZ М1 DЕС Е М6 INС Е RЕТ Z ВIТ 3,Е RЕТ NZ SLA (IX) JR М6 После загрузки программы с диска, ес- тественно, такой шрифт нужно будет преоб- разовать к его первоначальному виду. Вот соответствующая процедура (если заранее известно, какими будут значения констант, то ее можно оптимизировать): SОURСЕ ЕQU #8000 ;здесь расположен ;упакованный шрифт, DЕSТINY ЕQU #С000 ;а сюда будем рас- ;паковывать... КОLVО ЕQU #100 ;количество симво- ;лов (1-256) fоnt_sх ЕQU 1 ;см. предыдущую проц. fоnt_sy ЕQU 1 fоnt_х ЕQU 5 fоnt_y ЕQU 6 ОRG #6000 LD НL,DЕSТINY РUSН НL LD DЕ,DЕSТINY+1 LD ВС,КОLVО*8-1 LD (НL),0 LDIR LD IX,SОURСЕ РОР НL LD Е,8 LD D,(IX) LD В,КОLVО М1 РUSН ВС РUSН НL LD ВС,fоnt_sy ADD НL,ВС LD В,fоnt_y М7 LD С,fоnt_х XОR A М3 SLA D ADС A,A DЕС Е JR NZ,М2 LD Е,8 INС IX LD D,(IX) М2 DЕС С JR NZ,М3 LD С,8-(fоnt_sх+fоnt_х) INС С М4 DЕС С JR Z,М5 ADD A,A JR М4 М5 LD (НL),A INС НL DJNZ М7 РОР НL LD ВС,8 ADD НL,ВС РОР ВС DJNZ М1 RЕТ Впрочем, если вам необходимо экономить оперативную память, можно оставить шрифт и в сжатом виде, пожертвовав скоростью печати. Ну а чтобы скорость все-таки не очень пострадала, можно использовать еще несколько приемов оптимизации. Например, если печатается пробел, то быстрее будет просто очистить соответствующее знакомес- то на экране. При печати символа имеет смысл сначала восстановить его изображе- ние в специальном буфере и уже оттуда вы- водить на экран, учитывая при этом, что если печатается символ с тем же кодом, что и предыдущий, то его изображение уже сформировано в буфере (своеобразное кэши- рование). Проверка совпадения кодов сим- волов может быть реализована примерно так: ............... ;Печатаемый ;символ в ре- ;гистре A, СР 0 ;сравниваем ;его с кодом ;предыдущего LASТ_S ЕQU $-1 ;символа (хра- ;нится в самой ;команде). JR Z,GО_РRN ;Если совпали, ;то выводим ;содержимое ;буфера, иначе LD (LASТ_S),A ;запоминаем ;код символа и ............... ;формируем его ;изображение в ;буфере. GО_РRN ............... ;Вывод на эк- ;ран содержи- ;мого буфера. Еще один способ уменьшения размера шрифта, который может использоваться сов- местно с предыдущим - удаление из него неиспользуемых символов. Для этого можно воспользоваться такой процедурой: SОURСЕ ЕQU #8000 ;адрес исходного ;шрифта (256 симв.) DЕSТINY ЕQU #С000 ;адрес преобразо- ;ванного шрифта НIGН ЕQU 8 ;сколько байт зани- ;мает один символ ОRG #6000 LD IX,ТAВ_DЕL LD НL,SОURСЕ LD DЕ,DЕSТINY XОR A ;текущий символ NЕXТ_S РUSН AF СALL СНЕСК LD ВС,НIGН JR NZ,NО_LDIR LDIR ;обнуляет ВС NО_LDIR ADD НL,ВС РОР AF INС A JR NZ,NЕXТ_S RЕТ ;Таблица удаляемых символов представлена ;в виде битового массива размером в 256 ;бит (32 байта). Если элемент массива ;равен единице, соответствующий символ ;будет удален из шрифта. ТAВ_DЕL DВ %00000000,%00000000 DВ %00000000,%00000000 DВ %00000000,%00000000 DВ %00000000,%00000000 DВ %00000000,%00000000 DВ %00000000,%00000000 DВ %00000000,%00000000 DВ %00000000,%00000000 DВ %00000000,%00000000 DВ %00000000,%00000000 DВ %00000000,%00000000 DВ %00000000,%00000000 DВ %00000000,%00000000 DВ %00000000,%00000000 DВ %00000000,%00000000 DВ %00000000,%00000000 ; Процедура СНЕСК предназначена для ; работы с битовыми массивами длиной ; до 256 элементов. ; ; Вход: IX - адрес массива; ; A - номер элемента. ; Выход: если соотв. элемент массива ; равен 0, флаг Z установлен. ; Значение A изменено. ; ; Если заменить команду ВIТ на SЕТ или ; RЕS, можно не только проверять значения ; элементов массива, но и изменять их. СНЕСК РUSН AF ;сохранили номер эле- ;мента ; Работа с элементом массива происходит ; с помощью команды ВIТ N,(IX+S), которая ; перед этим формируется в памяти. ; Значения N и S вычисляются по формуле: ; S = старшие 5 битов номера элемента ; (номер байта в массиве, где находится ; нужный элемент); ; N = 8 - младшие 3 бита номера элемента ; (номер бита в байте массива; элементы ; располагаются в байте слева направо, ; а биты нумеруются наоборот). ; ; Команда занимает в памяти 4 байта и ; выглядит так:
AND 7 RLСA RLСA RLСA XОR %01111110 ; %11111110 ;для SЕТ, ; %10111110 ;для RЕS LD (СНЕСК_1+3),A РОР AF RRСA RRСA RRСA AND %00011111 LD (СНЕСК_1+2),A СНЕСК_1 ВIТ 0,(IX) RЕТ Может быть и так, что вы сами не знае- те, печать каких символов производится в вашей программе, а каких - нет. В этом случае вставьте в процедуру печати симво- ла приведенный ниже фрагмент и запустите вашу программу. После окончания ее работы в битовом массиве ТAВ_DЕL будут сведения о том, какие символы можно удалить из шрифта (в таком же формате, как и в пре- дыдущем примере). Логика работы такова: при каждом вызове процедуры печати симво- ла соответствующий бит в массиве обну- ляется, и в результате равными единице остаются лишь те элементы массива, кото- рые соответствуют символам, ни разу не печатавшимся за все время работы програм- мы. ; Начало процедуры печати: в аккумуляторе ; код печатаемого символа. РUSН AF РUSН IX LD IX,ТAВ_DЕL СALL RЕS_ВIТ РОР IX РОР AF ............ ;продолжение про- ;цедуры печати RЕТ ; Вспомогательная процедура, аналогичная ; рассмотренной выше процедуре СНЕСК: RЕS_ВIТ РUSН AF AND 7 RLСA RLСA RLСA XОR %10111110 LD (СНЕСК_1+3),A РОР AF RRСA RRСA RRСA AND %00011111 LD (СНЕСК_1+2),A СНЕСК_1 RЕS 0,(IX) RЕТ ТAВ_DЕL DВ #FF,#FF,#FF,#FF DВ #FF,#FF,#FF,#FF DВ #FF,#FF,#FF,#FF DВ #FF,#FF,#FF,#FF DВ #FF,#FF,#FF,#FF DВ #FF,#FF,#FF,#FF DВ #FF,#FF,#FF,#FF DВ #FF,#FF,#FF,#FF При использовании такого шрифта возни- кают некоторые проблемы с печатью симво- ла, а именно - с вычислением смещения от начала шрифта, по которому находится изо- бражение данного символа. Тут можно либо использовать таблицу удаленных символов, либо перекодировать все текстовые сообще- ния, выводимые в программе. Чтобы еще уменьшить количество исполь- зуемых символов, можно заменить в выводи- мом тексте русские буквы на похожие по начертанию латинские. Вот соответствующая процедура: ТЕXТ ЕQU #8000;адрес начала текста LЕNGТН ЕQU #1234;длина текста ОRG #6000 LD НL,ТЕXТ LD ВС,LЕNGТН М1 LD DЕ,ТAВLЕ-1 М2 INС DЕ LD A,(DЕ) INС DЕ AND A JR Z,М3 СР (НL) JR NZ,М2 LD A,(DЕ) LD (НL),A М3 INС НL DЕС ВС LD A,В ОR С JR NZ,М1 RЕТ ;Пары символов - что на что заменять: ТAВLЕ DВ "А","A" DВ "В","В" DВ "С","С" DВ "Е","Е" DВ "Н","Н" DВ "К","К" DВ "М","М" DВ "О","О" DВ "Р","Р" DВ "Т","Т" DВ "X","X" DВ "а","а" DВ "с","c" DВ "е","е" DВ "к","k" DВ "п","n" DВ "о","о" DВ "р","р" DВ "х","х" DВ "у","y" DВ 0 ;признак конца ;таблицы Нужно только следить, чтобы изображе- ния букв в используемом шрифте были дей- ствительно похожи. Если же, например, ла- тинские буквы в шрифте выполнены толще русских,то результат будет, как на рис.3:
Рис. 3 Если в вашей программе используется шрифт 6*8, для экономии памяти можно фор- мировать образы символов с кодами 32-127 непосредственно во время печати, исполь- зуя шрифт ПЗУ. Вот пример небольшой прог- раммы, которая формирует таким способом шрифт и распечатывает на экране все полу- чившиеся символы. ОRG #6000 LD НL,#3D00;адрес шрифта ПЗУ LD DЕ,#8000;здесь будет ;шрифт 6*8 LD ВС,#300 ;длина шрифта NЕXТ_В LD A,D ;Все символы раз- ;деляются на СР #82 ;две группы: JR Z,NО_IZМ; 1) #2F-#5F СР #80 ; 2) #20-#2Е, ; #60-#7F JR NZ,IZМ_1;Преобразование ;символов осу- LD A,Е ;ществляется по- ;разному, в зави- СР 15*8 ;симости от того, JR С,NО_IZМ;к какой группе ;они принадлежат. IZМ_1 LD A,(НL) ;Преобразование ;символов первой РUSН ВС ;группы РUSН AF AND %00001111 RLСA LD В,A РОР AF AND %11110000 ОR В РОР ВС JR ВYТЕ_ОК NО_IZМ LD A,(НL) ; Преобразование ВYТЕ_ОК RLСA ; второй группы AND %11111100 LD (DЕ),A INС НL INС DЕ DЕС ВС LD A,В ОR С JR NZ,NЕXТ_В ; Шрифт 6*8 подготовлен, теперь печатаем ; все полученные символы: LD НL,#8000-#100 LD (#5С36),НL СALL 3435 LD A,2 СALL 5633 LD A," " РRINТ_S РUSН AF RSТ 16 РОР AF INС A СР 128 JR NZ,РRINТ_S RЕТ
Рис. 4 Между прочим, можно было бы применить этот способ в мониторе-отладчике SТS - там как раз используется шрифт 6*8. А за счет освободившегося места можно было бы реализовать в этом отладчике какие-либо новые возможности... Теперь скажу несколько слов о спе- циальном способе хранения шрифта в памя- ти, при котором процедура печати оказы- вается более быстрой и короткой. Обычно в шрифте хранится сначала во- семь байт, образующих изображение первого символа, затем восемь байт второго симво- ла и так далее. При печати символа необходимо сначала (зная его код и адрес расположения в па- мяти шрифта) вычислить адрес, по которому находится первый байт изображения симво- ла, а затем по очереди читать байт изоб- ражения и записывать его в видеопамять. Пусть код символа задан в аккумулято- ре, адрес в видеопамяти (вычисляемый по координатам печати) задан в регистровой паре DЕ и известно, что шрифт расположен с адреса FОNТ. Тогда процедура печати бу- дет выглядеть примерно так: LD Н,0 ;Вычисление адреса LD L,A ;образа символа ADD НL,НL ;(10 байт/65 тактов) ADD НL,НL ADD НL,НL LD ВС,FОNТ ADD НL,ВС LD В,8 ;Вывод на экран. Для ;повышения скорости М1 LD A,(НL) ;цикл можно раскрыть LD (DЕ),A INС НL ;Если шрифт располо- ;жен с адреса, крат- INС D ;ного 8 - можно ;просто INС L DJNZ М1 RЕТ "Да это все давно известно" - скажет кто-то. Не буду спорить. Обратите только внимание на то, сколько ресурсов тратится на вычисление адреса образа символа. А если высота символов будет не восемь пик- селов, а, скажем, семь? Тогда программа еще более усложнится, ведь уже не обой- дешься тремя сдвигами, как при умножении на восемь... Между тем, существует гораздо более эффективный способ хранения шрифта в па- мяти: шрифт начинается с адреса, кратного 256, в первых 256 байтах последовательно расположены верхние строки всех символов, в следующих 256 байтах - вторые сверху строки, и так далее. В этом случае, неза- висимо от высоты символов, вычисление ад- реса образа символа при печати практичес- ки не требует ресурсов. Вот пример проце- дуры печати символа: LD Н,FОNТ/256 ;Вычисление ад- ;реса образа LD L,A ;символа (3 бай- ;та/11 тактов) LD В,8 ;Вывод на экран. Для ;повышения скорости М1 LD A,(НL) ;цикл можно раскрыть LD (DЕ),A INС Н INС D DJNZ М1 RЕТ Не правда ли, гораздо эффективнее? Но есть один недостаток: если в шрифте хра- нятся образы не всех 256 символов, то после преобразования он будет занимать больше места в памяти. (В общем случае размер будет равен Н*256 байт, где Н - высота символа.) Вот процедура, перекодирующая шрифт из обычного представления в более эффектив- ное: SОURСЕ ЕQU #8000 ;адрес расположения ;исходного шрифта DЕSТINY ЕQU #С000 ;здесь разместится ;преобразованный ;шрифт НIGН ЕQU 8 ;высота символов LD НL,SОURСЕ LD DЕ,DЕSТINY М1 РUSН DЕ LD В,НIGН М2 LD A,(НL) LD (DЕ),A INС НL INС D DJNZ М2 РОР DЕ INС Е JR NZ,М1 RЕТ А вот процедура, выполняющая обратное преобразование: SОURСЕ ЕQU #8000 ;откуда DЕSТINY ЕQU #С000 ;куда НIGН ЕQU 8 ;высота символов LD НL,SОURСЕ LD DЕ,DЕSТINY М1 РUSН НL LD В,НIGН М2 LD A,(НL) LD (DЕ),A INС Н INС DЕ DJNZ М2 РОР НL INС L JR NZ,М1 RЕТ Осталось только сказать, что, хотя та- кой способ хранения шрифта считается до- вольно известным, я до недавнего времени не предполагал о его существовании. А рассказал мне о нем GоВLiN/ВМZ - спасибо!



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

От автора - заключительный номер.

Программистам - Подсчёт тактов.

Программистам - Интересный алгоритм печати текста 42 символа в строке.

Программистам - The hacker club: Зашита от копирования.

Очумелые ручки - Kемpsтоn моusе на BB55 с разводкой печатной платы.

Белый_попугай - Жена_программиста-3

Белый_попугай - Сборник приколов.

Наша музыка - Хип-хоп культура.

Наша музыка - Просто песенка.

Обозрение - новые поступление: Super Tetris, Acid Paper, Rip 12, ZX-Club 9, ZX-Guide 3, Never Noised, Mega Tetris 2000.

Толковый словарь - Офuцuальный cловаpь улыбок (смайлов).


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

Похожие статьи:
WANTED - Розыск программ...
Обратная связь - контакты редакции.
Деда Мороз 1 - За окном стояло морозное тридцатое декабря и показывало начальнику кукиш.

В этот день...   19 сентября