Programmers - An interesting algorithm for printing text with 42 characters per line.

Black Crow #06
 SECRETS OF TEXT OUTPUT   
                                         
(C) 2001 Ivan Roshchin                      
   Fido  : 2:5О2О/689.53                                      
  ZЧNet : SOO:95/462.53                                      
   E-uail: asder_ffc@softhoue.pet                             
   WWW  : http://www.zx.ru/echo/roschin                      
-------------------------------------------------------
 Here I will talk about optimization techniques
tions used in text output
messages on the screen ZX-Spectrum. Some
of these techniques can be used and
on other computer platforms where
text is printed in graphic
mode.                                  
                                         
   First, a few general words. How from-
It is known that the ZX-Spectrum implements a single
veingraphics mode with resolution
256*192. The colors in it are not specified for each
dots, but immediately for the whole square
8*8 - that is, in fact, we do not have us -
is a color image, and the colorized
new black and white.                         
                                         
   On other computers (for example, PC)
along with graphics modes usually
There are also text ones. Spectrum is deprived of this
possibilities, and it is necessary to deduce on it
text in graphic mode. With one hundred
rons, it's slower and takes up more par-
crumpled, but on the other hand - sizes, shapes
ma and location of characters can be
any. In graphic mode, it also becomes
Smooth scrolling is possible when
viewing the text, which undoubtedly increases
ease of reading.                         
                                         
   I will consider most often
a common case when the font is specified in
raster form (there are also vector
fonts), and all its characters have the same
different width and height.                     
                                         
 When printing, it can be used as
8*8 font located in ROM at addresses
#3D00-#ЗFFF (only images are stored there
symbols with codes #20-#7F), and
font loaded into RAM (sizes and quantities)
quality of symbols in which, of course,
there may bearbitrary).               
                                         
   The procedure for printing a character usually has
dealing with the following parameters: character code
(byte), coordinates (x,y) and color. Coordi-
Nats are most often specified not in pixels, but
in familiar places (by familiar places I mean in
area of one character in size).
Let's say, when using an 8*8 font on
screen fits 32 characters horizontally
waist and 24 vertically; accordingly,
the x coordinate can vary from 0 to 31,
and y is from 0 to 23. Origin (0,0)
traditionally located in the upper left
corner of the screen.                             
                                         
 As we can see, some emulation occurs
text mode using graphical
whom. In 99% of cases this is used
one of the following three "text" modes -
mov: 32*24 (font 8*8), 42*24 (font 6*8)
and 64*24 (font 4*8). (How can you replace
tit, in 42*24 mode four pixels
horizontal lines remain unused -
usually they are either evenly distributed
right and left, or left on some
then one side.)                       
                                         
   In 32*24 mode, each character can
have your own color (which directly you-
flows from the structure of the Spectrum screen-
on).  In 42*24 and 64*24 modes this is impossible.
possible, but every word can be thereok-
painted in your own color (assuming that
words are separated by spaces). Other modes
(let's say 51*24 - when using a font
5*8) are deprived of this too.                     
                                         
 I’ve already said enough about theory, it seems
exactly. Now let's start optimizing! :)
                                         
   Usually in a font for each image
Eight bytes are allocated for the first character. But before-
Quite often such a presentation turns out to be
appears redundant, since some bits
are not used.  For example, for the font
6*8 (Fig. 1) the two outer columns are not
valid and always equal to zero.         
Fig. 1 Whenthe font is located in RAM, such his idea is quite justified, as providing sufficient printing speed tee. (By the way, when printing characters They want to make 6*8 especially fast, using use as many as four character sets, each of which is shifted relative to another by two pixels horizontally - so as not to waste time on shift when printing ty of each character.) But to save dis- of the space occupied by your program, it makes sense to remove from the font all redundant information. The savings can be quite significant: so, a font of 256 characters 6*8, originally occupying #800 bytes, will decrease by a quarter. And if in this font, the image of the characters is really under- only 5*6 pixels (i.e. between sim- oxen provides a mandatory gap in one pixel horizontally and two horizontally verticals), then it will be reduced by more than double! Below is the procedure to remove from font redundant information. The meaning of the constants used in it are font_sx, font_x, font_sy and font_y are explained in Fig. 2.
Рис. 2 SOURCE EQU #8000 ;здесь расположен ;исходный шрифт, DESTINY EQU #С000 ;а сюда поместим;packed... KOLVO EQU #100 ;number of symbols ;fishing (1-256) font_sx EQU 1;these parameters define ;remove the part being used font_sy EQU 1; matrices 8*8 for conversion ;definable font font_х EQU 5 font_y EQU 6 DEST_LEN EQU ((font_х*font_y*KOLVO)+7)/8 ;packed font length ;in bytes ORG #6000 LD HL,SOURCE LD IX,DESTINY LD E,0 LD В,KOLVO M1 PUSH Sun PUSH HL LD VS,font_sy ADD HL,VS LD B,font_y M7 LD A,(HL) LD С,font_sx INC C M2 DEC C JR Z,M3 ADD A,A JR M2 M3 LD С,font_х INC CM4 DEC C JR Z,M5 ADD A,A RL (IX) INC E BIT 3,E JR Z,M4 INC IX LD E,0 JR M4 M5 INC HL DJNZ M7 POP HL LD Sun,8 ADD HL,VS ROR Sun DJNZ M1 DEC E M6 INC E RET Z BIT 3,E RET NZ SLA (IX) JR M6 After loading the program from disk, Naturally, such a font will need to be transformed revert to its original form. Here the appropriate procedure (if in advance it is known what the values of the constants will be, then it can be optimized): SOURCEEQU #8000 ;located here ;packed font, DESTINY EQU #С000;and here we will dis- ;pack... KOLVO EQU #100 ;number of symbols ;fishing (1-256) font_sx EQU 1 ;see previous percentage font_sy EQU 1 font_х EQU 5 font_y EQU 6 ORG #6000 LD HL,DESTINY PUSH HL LD DE,DESTINY+1 LD BC,KOLVO*8-1 LD(HL),0 LDIR LD IX,SOURCE POP HL LD E,8 LD D,(IX) LD В,KOLVO M1 PUSH Sun PUSH HL LD VS,font_sy ADD HL,VS LD B,font_y M7 LD С,font_х XOR A M3 SLA D ADC A,A DECE JR NZ,M2 LD E,8 INC IX LD D,(IX) M2 DEC C JR NZ,M3 LD С,8-(font_sx+font_х) INC C M4 DEC C JR Z,M5 ADD A,A JR M4 M5 LD (HL),A INC HL DJNZ M7 POP HL LD Sun,8 ADD HL,VS ROR Sun DJNZ M1 RET However, if you need to save RAM, you can leave the font and in compressed form, sacrificing speed print. Well, so that the speed still doesn’t very damaged, can still be used several optimization techniques. For example, if a space is printed, it will be faster just clear the corresponding familiarity then on the screen. When printing a character it has it makes sense to first restore his imagein a special buffer and from there extract display on the screen, taking into account that if a character with the same code is printed, same as the previous one, its image is already formed in a buffer (a kind of cache- roving). Checking whether the symbol codes match oxen can be sold approximately like this: ............... ;Printable ;symbol in re- ;Gister A, SR 0 ; compare ;it with code ;previous LAST_S EQU $-1 ;character (stored ; appears in the ;team). JR Z,GO_PRN ;If they match, ;then we output ;contents ;buffer, otherwise LD (LAST_S),A ;remember ;character code and ............... ;form it ;image in ;buffer. GO_PRN ............... ;Output to ;ran contain- ;my buffer. Another way to reduce size font that canbe used jointly local with the previous one - removal from it unused characters. To do this you can use this procedure: SOURCE EQU #8000 ;source address ;font (256 characters) DESTINY EQU #С000 ;converter address ;bath font HIGH EQU 8 ;how many bytes are under- ;draws one character ORG #6000 LD IX,TAB_DEL LD HL,SOURCE LD DE,DESTINY XOR A ;current character NEXT_S PUSH AF CALL SNESK LD Sun,HIGH JR NZ,NO_LDIR LDIR ;zeroes the aircraft NO_LDIR ADD HL,SUN POP AF INC A JR NZ,NEXT_S RET ;The table of characters to be deleted is presented ;as a bit array of size 256 ;bit (32 bytes). If an array element ;equal to one, corresponding symbol ;will be removed from the font.TAB_DEL DB %00000000,%00000000 DB %00000000,%00000000 DB %00000000,%00000000 DB %00000000,%00000000 DB %00000000,%00000000 DB %00000000,%00000000 DB %00000000,%00000000 DB %00000000,%00000000 DB %00000000,%00000000 DB %00000000,%00000000 DB %00000000,%00000000 DB %00000000,%00000000 DB %00000000,%00000000 DB %00000000,%00000000 DB %00000000,%00000000 DB %00000000,%00000000 ; The SNESK procedure is intended for ; working with bit arrays of length ; up to 256 elements. ; ; Input: IX - array address; ; A - element number. ; Output: if acc. array element ; is 0, the Z flag is set. ; The value of A has been changed. ; ; If you replace the BIT command with SET or ; RES, you can not only check values ; elements of the array, but also change them. SNESK PUSH AF ;saved the element number;menta ; Working with an array element occurs ; using the BIT N,(IX+S) command, which ; before this is formed in memory. ; The values of N and S are calculated using the formula: ; S = high 5 bits of element number ; (byte number in the array where it is located ; desired element); ; N = 8 - low 3 bits of element number ; (bit number in the array byte; elements ; are located in a byte from left to right, ; and the bits are numbered backwards). ; ; The command takes up 4 bytes in memory and ; looks like this:
AND 7 RLCA RLCA RLCA XOR %01111110 ;%11111110 ;for SET, ; %10111110 ;for RES LD (SNESK_1+3),A POP AF RRCA RRCA RRCA AND %00011111 LD (SNESK_1+2),A SNESK_1 BIT 0,(IX) RET It may be that you yourself don’t know... those whose characters are printed in your program and which ones not. In this case, insert symbols into the printing procedure la the below snippet and run your program. After finishing her work the TAB_DEL bit array will contain information about which characters can be removed from font (in the same format as in the previous previous example). The logic of the work is as follows: every time you call the print procedure, symbols reset the corresponding bit in the array to zero lies, and as a result equal to one Only those elements of the array remain that some correspond to the symbols, never printed throughout the entire period of operation of the program we. ; Starting the printing procedure: in battery ; codeprintable character. PUSH AF PUSH IX LD IX,TAB_DEL CALL RES_BIT POP IX POP AF ............ ;continued ;printing procedures RET ; Auxiliary procedure similar ; the SNESK procedure discussed above: RES_BIT PUSH AF AND 7 RLCA RLCA RLCA XOR %10111110 LD (SNESK_1+3),A POP AF RRCA RRCA RRCA AND %00011111 LD (SNESK_1+2),A SNESK_1 RES 0,(IX) RET TAB_DEL DB #FF,#FF,#FF,#FFDB #FF,#FF,#FF,#FF DB #FF,#FF,#FF,#FF DB #FF,#FF,#FF,#FF DB #FF,#FF,#FF,#FF DB #FF,#FF,#FF,#FF DB #FF,#FF,#FF,#FF DB #FF,#FF,#FF,#FF When using such a font, there are problems there are some problems with the printing of symbols la, namely, with the calculation of the offset from the beginning of the font on which the image is located expression of this symbol. Here you can either use the table of deleted symbols, or recode all text messages tions output in the program. To further reduce the amount of use the characters you create can be replaced in the output In my text, Russian letters are similar in Latin style. Here is the relevant one procedure: TEXT EQU #8000; text start address LENGTH EQU #1234;text length ORG #6000 LD HL,TECHT LD SUN,LENGTH M1 LD DE,TABLE-1 M2 INC DE LD A,(DE) INC DEAND A JR Z,M3 SR (HL) JR NZ,M2 LD A,(DE) LD(HL),A M3 INC HL DEC BC LD A,B OR C JR NZ,M1 RET ;Pairs of characters - what to replace with what: TABLE DB "A","A" DB "B","B" DB "C","C" DB "E","E" DB "N","N" DB "K","K" DB "M","M" DB "O","O" DB "P","P" DB "T","T" DB "X","X" DB "a","a" DB "c","c" DB "e","e" DB "k","k" DB "n","n" DB "o","o"DB "r","r" DB "x","x" DB "y","y" DB 0 ;terminator ;tables You just need to make sure that the image the letters in the font used were effective really similar. If, for example, la- Teen letters in the font are made thicker Russians, then the result will be as in Fig. 3:
Fig. 3 If your program uses font 6*8, to save memory you can format create symbol images with codes 32-127 directly during printing, use I'm reading the ROM font. Here is an example of a small program: frames that forms in this way font and prints all semi- read symbols. ORG #6000LD HL,#3D00;ROM font address LD DE,#8000;will be here ;font 6*8 LD BC,#300 ;font length NEXT_B LD A,D ;All characters are different ;divided into CP #82 ;two groups: JR Z,NO_IZM; 1) #2F-#5F CP #80 ; 2) #20-#2E, ; #60-#7F JR NZ,IZM_1;Conversion ;characters osu- LD A,E ;sold by ;different, depending CP 15*8; depending on JR С,NO_IZM;to which group ;they belong. IZM_1 LD A,(HL) ;Conversion ;characters of the first PUSH sun ;groups PUSH AF AND %00001111 RLCA LD B,A POP AF AND %11110000 OR B ROR Sun JR BYTE_OK NO_IZM LD A,(HL) ; Conversion BYTE_OKRLCA ; second group AND %11111100 LD(DE),A INC HL INC DE DEC Sun LD A,B OR C JR NZ,NEXT_В ; The 6*8 font is ready, now we print ; all received characters: LD HL,#8000-#100 LD (#5С36),HL CALL 3435 LD A,2 CALL 5633 LD A," " PRINT_S PUSH AF RST 16 POP AF INC A SR 128 JR NZ,PRINT_S RET
Fig. 4 By the way, one could use this method in the STS debugger monitor - The font used there is 6*8. And for account of the free space could be implement in this debugger any new opportunities... Now I’ll say a few words about the special cial method of storing a font in memory ty, in which the printing procedure renders appears faster and shorter. Usually the font stores first the seven bytes forming the image of the first character, then eight bytes of the second character la and so on. When printingcharacter is necessary first (knowing its code and location address in pa- crumple the font) calculate the address at which the first byte of the symbol image is located la, and then read the image byte in turn image and record it into video memory. Let the symbol code be specified in the accumulative re, address in video memory (calculated by print coordinates) is specified in the register pair DE and it is known that the font is located from the FONT address. Then the printing procedure will be will look something like this: LD Н,0 ;Address calculation LD L,A ;character image ADD HL,HL ;(10 bytes/65 clock cycles) ADD HL,HL ADD HL,HL LD BC,FONT ADD HL,VS LD V,8 ;Output on screen. For ;increase speed M1 LD A,(HL); the cycle can be opened LD(DE),A INC HL ;If the font is located ;wives from the address, briefly- INC D; many 8 - possible ;just INC L DJNZ M1 RET "Yes, that's allhas long been known" - he will say someone. I won't argue. Pay only attention to how many resources are spent to calculate the address of the symbol image. A if the height of the characters is not eight pixels - villages, but, say, seven? Then the program will become even more complicated, because there will no longer be you do it with three shifts, as in multiplication for eight... Meanwhile, there is much more efficient way to store font in pa- mint: the font starts with an address that is a multiple of 256, in the first 256 bytes sequentially the top lines of all characters are located, in the next 256 bytes - second from top lines, and so on. In this case, depending on the height of the characters, the calculation of ad- Res of the character image when printing is practically ki does not require resources. Here is an example of the process character printing fools: LD Н,FONT/256 ;Calculation of ad- ;resa image LD L,A ;characters (3 bytes) ;ta/11 bars) LD V,8 ;Output on screen. For ;increase speed M1 LD A,(HL); the cycle can be opened LD(DE),A INC N INC D DJNZ M1RET Isn't it much more effective? But there is one drawback: if the font contains Not all 256 symbols appear, then after conversion it will occupy more memory space. (In general the size will be equal to H*256 bytes, where H is character height.) Here is a procedure to recode a font from conventional representation into a more efficient new: SOURCE EQU #8000 ;location address ;original font DESTINY EQU #С000 ; will be located here ;converted ;font HIGH EQU 8 ;character height LD HL,SOURCE LD DE,DESTINY M1 PUSH DE LD B,HIGH M2 LD A,(HL) LD(DE),A INC HL INC D DJNZ M2 POP DE INC EJR NZ,M1 RET Here's a procedure that does the opposite: conversion: SOURCE EQU #8000 ;from DESTINY EQU #С000 ;where HIGH EQU 8 ;character height LD HL,SOURCE LD DE,DESTINY M1 PUSH HL LD B,HIGH M2 LD A,(HL) LD(DE),A INC N INC DE DJNZ M2 POP HL INC L JR NZ,M1 RET All that remains is to say that, although Which method of storing a font is considered acceptable? freely known, until recently I didn't imagine its existence. A told me about it GoBLiN/BMZ - thank you!

Share your thoughts about the article