Alain BROBECKER Dracula / Positivity (STe) rte de Dardagny Baah / Arm's Tech (Archie) 01630 CHALLEX Baah (PC) FRANCE ----------------------------------------------------------------- 12 april 96 - GRAPHIC WAR - ============= (aka memory war ][) FOREWORD This text is aimed to assembly programmer, I doubt people programming in high level languages will appreciate it much. All algorithms, ideas and assembly code in here were made by me. (else I mention the author) If you use it in one of your programs, please send me a free copy of it and credit me. If you appreciated this text, I would be glad to know it. INTRODUCTION Again an article dedicated to the owners of low end computer, and which deals about reduction of program size on disk. Last time we saw how to create 'mathematical' tables, but what is the most expensive part of datas used in programs? Yup, graphixx. The common way to reduce their size is to use a packer, but as usual the best performances won' t be get by using a performant packer or what, but by combinating our grey cells and subtle formulaes. GETTING STARTED The first background we' ll create is not an idea of mine, but I found it in an issue of the excellent "Coder' s Revenge" magazine by the German crew Archiologics. (Though some issues were mostly in German, I recommend you get copies of them. Must mention I had troubles making it work on my 1Meg A3000,800Kb floppy too.) The trick is really simple, and efficient. The pixel at (x;y) quite simply gets the xANDy color, and with Archimede's standard palette you obtain a nice result, as can be seen in appendix A. Also note you can use the formula to perform a rotation/mapping without accessing memory, and you can also try xEORy as basic formula, or whatever combination such as (x+y)OR(x-y)... As usual, the program is very short (80 bytes) compared to the size the created 256*256 image would take on disk. The "packing" ratio is then 1:819, which proves to beat everyhing, even a fractal packer I think. (Since the philosophy of fractal packers is, as far as I know, to find a formula which constructs the image, and that is exactly what we do) By the way, when speaking about fractals, don' t you think the given image is quite similar to the Sierpinsky Gasket? Well, not very surprising since one way of obtaining this fractal involves eor operations from one line to one another. (Well, there is much to say about this, but it' s not our subject for now) AMIGA LIKE For some years now, amiga demomakers are putting "messy" 1 bitplane (ie 1 bit per pixel) image as a background, and I must admit that it looks quite nice. The way they are creating those backgrounds is very simple: they take a brush in deluxe paint, choose a color and make large random movements with the mouse, sometimes clearing, sometimes drawing. Don' t sound very hard to do huh? Well it isn' t, and we' ll prove it. The basic proggy which simulates an amiga graphist (hey, don' t take it too serious! ;) would look like the following... 10 : MODE 9:OFF 20 : COLOUR 0,0,4*17,0 : COLOUR 1,0,5*17,0 30 : FOR a%=1 TO 1<<13 40 : IF RND(2)=1 THEN GCOL(1) ELSE GCOL(0) 50 : CIRCLE FILL RND(1279),RND(1023),8 60 : NEXT a% So what are the problems when converting this to pure ASM. (Well, some basic+ASM programmers wouldn' t care, they would simply save it on disk, as they do for huge precalc tables! ;) The first one is to have a decent random generator. My generator is based upon no algorithm, I just tried operations combination till I got a decent one, which seemed to give equal probabilities for each number. As far as I know, the problem when creating a rnd number generator is in fact to have a "formula" which does not look like one. (Else, you may see patterns arising in your programs) My routine is quite small and fast (3 instructions, 5 cycles. If you have better, I would be glad to hear about it), and the really handy thing I learned out of my tries (and out of the vlc86c010 book, I must admit) is that shifts, rotations and carry mixed with classical operations gives good result for rnd generators. Once this problem has been set up, the other problems where quite easy to cope with. I only needed to draw (or clear) sprites. In order to simplify thing, I decided not to cope with maximum speed sprites and clipping (hey, I create a background only once in a demo, so my aim is not maximum speed, but minimum size!), making things much easier. So, the result is in appendix B, and provides a 440 bytes proggy which creates a 10240 bytes texture. For once I will let you calculate the "packing" ratio. (It become dull...) The main difference between a piccy generated by our proggy and a hand made background, is that sometimes a graphist try to have a logo or else drawn with the messy shit. We can do it too, but the equations will certainly be more complex. (And so will be the code. Don' t be afraid, complex code is the most interesting one) As an introduction to more sophisticated backgrounds, here is a proggy which draws a spiral. 10 : MODE 9:OFF:ORIGIN 640,512 20 : COLOUR 0,0,4*17,0 : COLOUR 1,0,5*17,0 30 : FOR r%=1 TO 1024 40 : x%=r%*COS(2*PI*r%/256) 50 : y%=r%*SIN(2*PI*r%/256) 60 : FOR a%=1 TO 4 70 : IF RND(2)=1 THEN GCOL(1) ELSE GCOL(0) 80 : CIRCLE FILL x%+RND(r%/3),y%+RND(r%/3),4+RND(r%/24) 90 : NEXT a% 100 : NEXT r% GREY EDIT LIKE After an excursion to alien worlds (amiga) we are back on the Archimedes world with a prestigious guest-star... (drum roll, applauses...) It is, it is... John KORTINK, the author of the GreyEdit program. If you can get a copy of it, don' t hesitate a second, it' s really worth its disk space. (Though I don' t use it much, I' m pleased to know it' s somewhere in my dusty disk box) Amongst other features, this proggy allows you to create a random pattern, and then apply "filters" on it, like smoothing, embossing and much more. After a few iterations of those operations, you will have (sometimes) a nice pattern appearing. A typical combinations which always give good results is creating the random texture, embossing it and then smoothing it. Now you' re normally familiar with random generation, so we have to fix the embossing and the smoothing. Embossing is easy to make, you only need to calculate the difference between two pixels, and this adds the relief. Of course, the difference will sometimes be negative or higher than the authorised maximum, then you set it to 0 or to the maximum value. If we don' t do this, there won' t be much changes between the initial texture and the embossed one, since they would both be random patterns only. Smoothing, though a bit harder, has quite a similar philosophy. The dest (x;y) pixel get the average of all the pixels surrounding source (x;y), with given coefficients. I choosed to take in account only the 8 pixels surrounding (x;y), and for the one who are used to mathematics, making the averaging is a stupid 3*3 matrix operation. As far as I know, the Gauss smooth means the coefs of matrix are given by a "Gaussian" equation, which varies exponentially with the distance. The coefficients I personnaly used have nothing to do with mathematics, they only give good results. One thing I wanted and which is not in GreyEdit is the "wrapping" of the created pattern. This kind of problem is easily set up by using x mod(N) instead of x, where N is the width of the texture. (Same for y) Another handy thing you shall know is that if you choose N a power of 2, the mod(N) operation is the same as ANDing the value with (N-1). The resulting program is again quite good in terms of size (392 bytes) and I very much like the resulting background. One problem is that the texture looks a bit tiny if looked at on a huge (640*512) screen. If you want to eliminate this problem, then you simply have to create a less random texture, add noise (=random perturbation) on it and go on as usual. I have not tested it right now, but I can' t imagine why it would not work. (Since I can' t have a 640*512 screen, I have no use of this) As an example, let' s say you create a 128*128 random pattern, then you double it, giving a 256*256 texture with square pixels. Then, add a small random perturbation to all pixels individually, and go on. (Emboss+Smooth) P.S: This has been used many times since, see damn!, IntroCR 1 & 2, NZCVdemo, Paranoid... - THE END - ;**************************************************************************** ;***** ***** ;***** APPENDIX A ***** ;***** ***** ;**************************************************************************** ; Not much to say, except that this small proggy certainly suits well for ; apprentice ASM coders. (Good lucks, guys. Getting started is the hardest) .make_background_1 mov r13,r14 ; Save return adress. swi 256+22 ; Switch to mode13. swi 256+13 swi OS_RemoveCursors ; Who needs them? adr r0,videoram_adress ; Use system routs to get videoram adress. mov r1,r0 swi OS_ReadVduVariables ldr r0,videoram_adress ; And put videoram adress in r0. mov r1,#255 ; r1=y counter. .y_loop mov r2,#255 ; r2=x counter. .x_loop and r3,r2,r1 ; Here' s the magical operation. strB r3,[r0],#1 ; Save xANDy in memory. subS r2,r2,#1 ; All 256 pixels drawn? bGE x_loop ; No, then loop. add r0,r0,#320-256 ; Next line. subS r1,r1,#1 ; All 256 lines drawn? bGE y_loop ; No, then loop. mov pc,r13 ; That' s all folks. .videoram_adress ; Here are the magical values used dcd 148,-1 ; by swi OS_ReadVduVariables. ;**************************************************************************** ;***** ***** ;***** APPENDIX B ***** ;***** ***** ;**************************************************************************** ; The really interesting thing is the random32 macro. Others things that ; should be noticed are that I create the 1 bpp background just after the ; proggy, (bss) and normally I should watch if I have enough Wimp_Slot. ; Another thing is that I know that the sprite is a 5*5 "circle", and so ; I was able to use tricks, so that it goes faster. I don' t perform ; clipping. Now go through the code if you want to know more. ; This macro takes two random numbers, and by using subtile (hum) operations ; it changes them in two new random numbers. macro random32 m0,m1 { add m0,m1,m0,ror #3 mov m0,m0,ror m1 eor m1,m0,m1,ror #7 } #set nb_sprites = 3<<12 ; Nb of sprites to put on screen. .make_background_2 mov r13,r14 ; Save return adress. swi 256+22 ; Switch to mode9. swi 256+9 swi OS_RemoveCursors ; Who needs them? adr r0,videoram_adress ; Use system routs to get videoram adress. mov r1,r0 swi OS_ReadVduVariables adr r0,colors ; Change colors using a swi. mov r1,#12 ; "Write" 12 bytes. (2 colors) swi OS_WriteN ; First we clear the place where we' ll put the background. adr r0,bss ; Create 1 bpp background here. mov r1,#512*(256+6)/8 ; Number of bytes to clear. mov r2,#0 ; Fill with zeroes. .clear_one str r2,[r0,r1] ; Clear one long. subS r1,r1,#4 ; All longs cleared? bGE clear_one ; Here really starts the creation of the background. mov r1,#nb_sprites ; Nb of sprites to 'draw'. adr r2,random_germs ; Load the random germs. ldmia r2!,{r2,r3} mov r4,#%01110 ; Mask for the sprites. mov r5,#%11111 .make_one_sprite mov r6,r2,lsr #32-8 ; r6=y=rnd(256). add r6,r0,r6,lsl #6 ; r6=tmp_buffer+y*512/64. mov r7,r3,lsr #32-4 ; r7=int(x/32)=rnd(16). add r6,r6,r7,lsl #2 ; r6 points on first longword. and r7,r2,#%11111 ; r7=x mod32=rnd(32). rsb r8,r7,#32 ; r8=32-(x mod32). mov r9,r5,lsl r7 ; Shift the two masks of sprite. mov r10,r5,lsr r8 mov r7,r4,lsl r7 mov r8,r4,lsr r8 tst r3,#%1 ; Clear or set the sprite? ; Here we draw all five lines of sprite. The drawing method depend upon CC, ; if set to NE, we 'orr' the shifted sprite and bground, else 'bic' them. ldmia r6,{r11,r12} : orrNE r11,r11,r7 : bicEQ r11,r11,r7 : orrNE r12,r12,r8 bicEQ r12,r12,r8 : stmia r6,{r11,r12} : add r6,r6,#64 ldmia r6,{r11,r12} : orrNE r11,r11,r9 : bicEQ r11,r11,r9 : orrNE r12,r12,r10 bicEQ r12,r12,r10 : stmia r6,{r11,r12} : add r6,r6,#64 ldmia r6,{r11,r12} : orrNE r11,r11,r9 : bicEQ r11,r11,r9 : orrNE r12,r12,r10 bicEQ r12,r12,r10 : stmia r6,{r11,r12} : add r6,r6,#64 ldmia r6,{r11,r12} : orrNE r11,r11,r9 : bicEQ r11,r11,r9 : orrNE r12,r12,r10 bicEQ r12,r12,r10 : stmia r6,{r11,r12} : add r6,r6,#64 ldmia r6,{r11,r12} : orrNE r11,r11,r7 : bicEQ r11,r11,r7 : orrNE r12,r12,r8 bicEQ r12,r12,r8 : stmia r6,{r11,r12} random32 r3,r2 ; Next random number. subS r1,r1,#1 ; One sprite drawn. bNE make_one_sprite ; Now draw a part of the 512*256, 1 bpp background to mode9 screen. add r0,r0,#3*4+3*64 ; Take middle of created bground. ldr r1,videoram_adress ; Adress of videoram. mov r2,#256 ; Nb of hlines to convert. .draw_one_hline mov r3,#10 ; Nb of 1 bpp longs to convert per hline. .draw_32_pixels mov r4,#4 ; 1 src long -> 4 dest longs. ldr r5,[r0],#4 ; Load source pixels, in 1 bpp. .draw_8_pixels movS r6,#0 ; r6 will contain the dest long. #set N=0 #rept 8 movS r5,r5,lsr #1 ; Put pixel in carry bit. addCS r6,r6,#1< mode13 color table. adr r1,bss ; Create texture here. ldr r2,videoram_adress ; Use videoram as temporary buffer. ; First, we fill first minibuffer with the random 'noise'. adr r3,random_germs ; Load germs for the random generator. ldmia r3,{r3-r4} mov r5,#N*N ; r5=nb of pixies to generate. mov r6,#&1f1f1f1f ; Mask for pixels' intensities. .random_fill and r7,r6,r3 ; Pixels' intensities between 0-31. str r7,[r1],#4 ; Save 4 pixels. random32 r3,r4 ; Next random number. subS r5,r5,#4 ; 4 pixels processed. bNE random_fill sub r1,r1,#N*N ; r1 back on its position. ; Then we add relief to the texture by taking the difference (delta) between ; the pixels up and down of the current position. mov r3,#0 ; r3=y counter<<(32-7). .emboss_one_line sub r4,r3,#1<<(32-M) ; r4=(y-1) mod N <<(32-M). (Wrapping) add r5,r3,#1<<(32-M) ; r5=(y+1) mod N <<(32-M). (Wrapping) add r4,r1,r4,lsr #(32-2*M) ; r4 points on src_line up. add r5,r1,r5,lsr #(32-2*M) ; r5 points on src_line down. mov r6,#N ; r6=nb of pixels per line. .emboss_one ldrB r8,[r4],#1 ; r8=pixie up. ldrB r7,[r5],#1 ; r7=pixie down. sub r7,r7,r8 ; r7=delta. addS r7,r7,#middle ; Add the middle constant. movMI r7,#0 ; Make sure intensity is between 0-31. cmp r7,#31 movGE r7,#31 strB r7,[r2],#1 ; Save it. subS r6,r6,#1 ; One pixel done bNE emboss_one addS r3,r3,#1<<(32-M) ; Line done. bNE emboss_one_line sub r2,r2,#N*N ; r2 back. ; We smooth the texture by applying the following 3*3 matrix on pixels... ; ( 1 2 1 ) ( pix0 pix1 pix2 ) ; 1/16 * ( 2 4 2 ) * ( pix3 pix4 pix5 ) = new pix. ; ( 1 2 1 ) ( pix6 pix7 pix8 ) ; At the same time we convert the intensities into pixels by using the ; given color table. mov r3,#0 ; r3=y counter. .smooth_line mov r4,#0 ; r4=x counter. sub r5,r3,#1<<(32-M) ; r5=(y-1) mod N <<(32-M). (Wrapping) add r7,r3,#1<<(32-M) ; r7=(y+1) mod N <<(32-M). (Wrapping) add r5,r2,r5,lsr #(32-2*M) ; r5 points on src_line up. add r6,r2,r3,lsr #(32-2*M) ; r6 points on src_line. add r7,r2,r7,lsr #(32-2*M) ; r7 points on src_line down. .smooth_one sub r8,r4,#1<<(32-M) ; r8=(x-1) mod N <<(32-M). (Wrapping) add r9,r4,#1<<(32-M) ; r9=(x+1) mod N <<(32-M). (Wrapping) ldrB r10,[r6,r4,lsr #(32-M)] ; Load all the pixels, and add them ldrB r14,[r5,r4,lsr #(32-M)] ; with the good coefficients in r10. add r10,r14,r10,lsl #1 ldrB r14,[r7,r4,lsr #(32-M)] add r10,r10,r14 ldrB r14,[r6,r8,lsr #(32-M)] add r10,r10,r14 ldrB r14,[r6,r9,lsr #(32-M)] add r10,r10,r14 ldrB r14,[r5,r8,lsr #(32-M)] add r10,r14,r10,lsl #1 ldrB r14,[r5,r9,lsr #(32-M)] add r10,r10,r14 ldrB r14,[r7,r8,lsr #(32-M)] add r10,r10,r14 ldrB r14,[r7,r9,lsr #(32-M)] add r10,r10,r14 mov r10,r10,lsr #5 ; r10=intensity. cmp r10,#11 ; No more than 12 colors. movGE r10,#11 ldrB r10,[r0,r10] ; Convert it with table lookup. strB r10,[r1],#1 ; And save new pixel value. addS r4,r4,#1<<(32-M) ; Next pixel. bNE smooth_one addS r3,r3,#1<<(32-M) ; Next line. bNE smooth_line ; Now we copy the created texture on screen. adr r0,bss ; Adress of created texture. ldr r1,videoram_adress ; r1=videoram adress. mov r2,#N ; r2=y counter. .y_loop mov r3,#N ; r3=x counter. .x_loop ldrB r4,[r0],#1 ; Load pixel. strB r4,[r1],#1 ; And copy it in videoram. subS r3,r3,#1 ; Whole hline drawn? bNE x_loop ; No, then loop. add r1,r1,#320-256 ; Next dest line. subS r2,r2,#1 ; All hlines drawn? bNE y_loop ; No, then loop. mov pc,r13 ; That' s all folks. .videoram_adress ; Here are the magical values used dcd 148,-1 ; by swi OS_ReadVduVariables. .color_table dcb &08,&09,&0a,&0b,&a4,&a5,&a6,&a7,&d8,&d9,&da,&db ; Blue. .random_germs ; The magical random numbers. dcd &eb1a2c37,&3fd2a145 .bss ; MUST BE AT THE VERY END.