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.