space woes in assembly: 591 bytes into 512 bytes

[AndrewAPrice]

I was working on a bootsector for the 512 byte contest, and my idea is to make a demo with Pole-Position style graphics. First I wanted to make it a game, but after realizing how much space that would take I have lowered my expectations to showing a road with trees and fences zooming past (who places fences onto roads, I don't know).



Anyway, I had basic vector trees rendering (above) until I hit the dreaded 512 byte limit (it's times like these you think 1kb would give you the freedom you needed and how wonderful it would be if this were a 1kb demoscene competition instead!). I'm up to 591 bytes and my code basically contains the following:

• - Init logic
  - Draw terrain/map (the main loop)
  - Plot pixel
  - Draw line
  - Draw scaled vector image at coordinate
  - Generate random number
  - 2 vector images

So it's pretty much functionality complete (except the draw function doesn't have a delay in so it loops as fast as CPU'ingly possible).

I am asking if you can see what I could cut back on and which functions I can optimize (I'm relatively new to using assembly outside of short stubs of code, which you may tell from my coding style). I appreciate any help you can give me on this.

Here is a link to my FASM source: http://asm.pastebin.com/m5fd3525d

[Combuster]

you may want to try using a register-calling-convention instead of stack. It saves a lot of copies and memory references (saving you a byte for each stack reference that's optimized away)

[Owen]

A couple of little ones:

Code: Select all

        mov al, 0x13 ; 320 width, 200 height
        mov ah, 0x00

Surely that can't be shorter than a mov ax, 0x0013?

Also:

Code: Select all

        mov ah, 0 ; load a random seed from the time
        int 0x1a
        mov [seed], dx

Would rdtsc not be both smaller and more random?

[cxzuk]

Heya..

From what i can see, this test can be done by hand and removed from the code.

; the line is rendered from left to right, so test to make sure the
; starting coordinates are on the left, otherwise swap x1/y1 with x2/y2
mov ax, [p_x1] ; test if x1 <= x2
cmp ax, [p_x2]
jle .1
; else, x1 > x2, so swap x1,y1 with x2,y2
xchg ax, [p_x2]
mov [p_x1], ax

mov ax, [p_y1]
xchg ax, [p_y2]
mov [p_y1], ax
.1:

The only thing that calls "draw_line". And from what i can see the data it is given is pre-defined (the road drawing, and the image drawing). I had a look at the random number gen, and im guessing it only generates the x,y of the image?

MikeyB =]

[Gigasoft]

I don't know where you got the idea that cmp doesn't accept immediate values, which it does.

Generate_line seems buggy. It always writes the value -2745. I guess it's supposed to write the random value?

It could be rewritten like this:

lea di,[map+eax*2]
mov bx,23
imul ax,[seed],0x8405
mov word [seed],ax
mul bx
xchg dx,ax
stosw
ret

If you put a pusha and popa around the draw_line function, the code from draw to render_objects could be written as:
xor di,di
xor ax,ax
mov cx,32000
rep stosw
mov si,99
mov dx,199
mov bx,draw_line
push 159
push si
push byte 9
push dx
mov cl,8
call bx
push 160
push si
push 310
push dx
call bx
push 0
push si
push 319
push si
mov cl,2
call bx

The first generate_line loop seems buggy. It uses DX instead of CX for the line number. It could be written like this:
mov ax,99
.1:
pusha
call generate_line
popa
dec ax
jns .1

[AndrewAPrice]

Thank you, I've taken all of your replies into consideration and I've finally squashed it down into 512 bytes (my entry is posted here [1]).

@owen: I'm sticking with the BIOS's time, since rdtsc returns the number of clock ticks since the processor was turned on. As the boot sector loads immediately as I turn on the computer rdtsc was returning the exactly same value each time, so it wasn't very 'random'.
@Gigasoft: I'm not sure - I tried cmp with an constant value quickly yesterday and received an error yet today it works fine (I must have done something else alongside it). Also, I couldn't use rep stosw (though an interesting instruction!) since I'm now using the same loop to copy from the back to front buffer as I clear the back.

Anyway, thanks again!

[earlz]

line 33:

Code: Select all

       mov cx,100
        .1:
                dec cx
                pusha ; generate a random value for this line
                mov ax, dx
                call generate_line
                popa

                jcxz .2 ; loop if lines remain (jump if cx is 0)
                jmp .1
        .2:

Could you not condense that to use `loop` at the end? something like

Code: Select all

       mov cx,99 
        .1:
                pusha ; generate a random value for this line
                mov ax, dx
                call generate_line
                popa
                loop .1
        .2:

I think you would miss one iteration of the loop with that though... so idk..

[Owen]

@owen: I'm sticking with the BIOS's time, since rdtsc returns the number of clock ticks since the processor was turned on. As the boot sector loads immediately as I turn on the computer rdtsc was returning the exactly same value each time, so it wasn't very 'random'.

I'm surprised. A floppy/HD should be more random than that - or were you testing under an emulator?

[AndrewAPrice]

@owen: I'm sticking with the BIOS's time, since rdtsc returns the number of clock ticks since the processor was turned on. As the boot sector loads immediately as I turn on the computer rdtsc was returning the exactly same value each time, so it wasn't very 'random'.

I'm surprised. A floppy/HD should be more random than that - or were you testing under an emulator?

Yes.

@earlz: Already done, Gigasoft mentioned the same above.

Thanks everyone!

[pcmattman]

How are you rendering the trees? Are you drawing a bitmap or something, or actually drawing proper line segments?

[earlz]

How are you rendering the trees? Are you drawing a bitmap or something, or actually drawing proper line segments?

he said he was doing vector graphics..

[pcmattman]

He said "2 vector images", which could mean code to draw a bunch of hard-coded lines, or code to draw a bunch of lines from memory. Looking at the source (which I was trying to avoid doing by asking), I see the code draws from a location in memory.

Because the fence is made up of nothing more than a couple of rectangles (the tree is a little more complex), it may be easier to either:

• Store one rectangle and render it (n) times, increasing the y position each time to create the fence
• Don't store image data at all and write an algorithm to draw the shape

Until you remove or condense that image data somehow, you're wasting huge amounts of space.

Also, your tree_image has both the left and right side stored, you could get away with storing one half. Then you flip the co-ordinates to render the other side of the tree.

[AndrewAPrice]

Because the fence is made up of nothing more than a couple of rectangles (the tree is a little more complex), it may be easier to either:

• Store one rectangle and render it (n) times, increasing the y position each time to create the fence
• Don't store image data at all and write an algorithm to draw the shape

Also, your tree_image has both the left and right side stored, you could get away with storing one half. Then you flip the co-ordinates to render the other side of the tree.

All of those are good ideas. The first idea would work, but your second (doing it completely algorithmically) may not because the issue I see is the algorithm for rendering that may be larger than storing the image data. Both images are 29 bytes each (58 bytes in total), only enough room to fit approximately 8-12 instructions. But it could possibly be an advantage since I'll be able to get rid of draw_image.

Mirroring would work for both images and cut out just less than half of the image data. Pity I didn't think of that sooner!