;******************************************************;
;* PLASMA.ASM -- Simple plasma display, with rotating *;
;* palette. Requires VGA, 386. *;
;******************************************************;
;
; Submitter: Paul Hsieh
; Size: 390 bytes (total of 169 bytes savings from original)
; Date: Mon, Feb 17.
;
;------------------------------------------------------------------------------
;
; Techniques used in size optimizing from the original source as given in
; the PT&T 2.0 contest.
;
; (1) There were numerous gimme's such as: only using a byte where the
; original was using a word, or word instead of dword; removing unnecessary
; stack frames; skipping the "wait for vertical blank end" before the "wait
; for vertical blank start"; removing redundant "test" operations when an
; arithmetic operation had occurred just before it; optimizing stack and
; register references.
;
; (2) The next thing I did was try to rearrange the small routines (SetPal,
; SetPixel, GetPixel, Rand and rand192) in terms of content and register API.
; It was fairly straight forward removing the stack frames and minimizing all
; but the SetPal routine. (At this point the SetPixel function looked more
; like the mirror image of the current GetPixel function.) The SetPal
; routine needed special attention, since it was artificially tied down to
; the data structure "Palette[bx]". By changing the palette initialization
; function and inlining the SetPal function into the inner loop, I was able
; to drop the redundant copy for the second half of the Palette table. I
; also changed the "Palette" offset declaration to a constant so that it
; could simultaneously initialize bl for whatever extraneous purpose. Only in
; the final phase of optimization did I see a way to take advantage of it!
;
; (3) With all the simple optimization tasks out of the way, I set about
; trying to understand how the algorithm works. After a while I realized
; that the algorithm was essentially a recursive stochastic mountain fractal
; that is color mapped rather than height mapped. By understanding this at a
; high level I was able to picture the whole algorithm in my head and it
; became instantly clear what the next big redundancy in the algorithm was:
; The plotting routines had 3 complicated termination conditions which were
; glutting up the code. I more fully characterized the essential "singular"
; recursive subdivision configuration as being a rectangle of height 1 and
; the termination condition being a rectangle of width 1 or 0. All under the
; proviso that no pixel is ever drawn twice, and "Adjust" calls are always
; made before "Plasma" recurse calls. Rather than pulling the logic of the
; duplicated pixels into the subdivision algorithm, I put it into the SetPixel
; routine itself, where I took advantage of GetPixel's address offset
; calculation as a side effect. The recursive structure changed somewhat, and
; I had to play with the stack to accomodate it. Although I only got modest
; gains from it (since it was really just a trade in complexity) it was by far
; the most complicated of all the changes. I actually implemented some
; debugging code to trace through so that I had everything clear in my mind.
;
; (4) After all these rearrangements other redundancies were uncovered that
; were hidden to me before. Many more references to the stack were actually
; redundant since nearly all the values were already in registers. Two more
; "gimmes" using the fact that all Y values are < 256 and thus the high byte
; is set to zero. At this point there were only two xor reg,reg commands.
; I found a way to change "Rand" yet again to more closely match the contexts
; of the callers, and save the xor edx,edx in the process. I took a second
; look at the stack frames and realized that I could get rid of all of them
; easily. After careful consideration, I've decided that without compromise,
; the add constant in the random number generator can be 1.
;
; (5) After a nights sleep and dreaming about 16 bit optimizations (a very
; twisted state to be in!) I found 4 more gimmes. (1) Set palette buffer
; address so that as a side effect after the last InitPal, bx=A000. (2) Use
; dl instead of al in SetPixel. (3) Remove ds override on self modifying
; code (boy was *that* ever stupid ...) (4) Set EBX to 95, via xor ebx,ebx
; then setting bl.
;
; (6) Re-implemented all recursive calls, as a massive return chain setup.
; That is, the parameters for all the calls are worked out in advance, so they
; along with the start addresses of the next call (in lieu of the actual return
; addresses) are stored on the stack in the correct call order. Doing this
; allows me to take advantage of call address redundancy, by sticking the call
; addresses in a register (bp) and just pushing them onto the stack. Code was
; then rearranged so that many jmps became unneccessary (they just fell
; through.) At this point, the code becomes extremely unmaintainable, as the
; recursive call structure is now completely hidden.
;
; (7) I implemented the call chain idea in the two other places where is
; seemed to work out. Put color accumulator into the GetPixel call itself.
; A few more gimme's (folding the init of ebx and pushing of zeros together.)
; At this point, finding new optimization areas is getting painful. Optimize
; the clamping to take sign of dx into account from previous sar, and unsigned
; byte comparison to check against 192 (251, is maximal possible value.)
;
; (8) Use only 16 bit bx as divisor (range is small enough) without
; compromising randomness, use CX = 0 side effect for zero rather than
; clearing ebx. Reduce pushad/popad to pusha/popa. Swap roles of si and bx
; so that I can use lea si,[bx+di] command!! Hey! In most cases cwd is the
; same as xor dx,dx!! Did a recheck on the (dx+ax*2)>>1 and realized it
; simplifies to (dx>>1)+ax since there can never be a bottom bit carry.
;
; (9) Fixed problem with esp. Win 3.0 does not clear the upper half of esp
; on DOS box initialization, which must do wonders for stability. Anyhow, I
; went back to using bp, and lost two bytes.
;
; (10) I went over the code again, but in its current state it has so far
; resisted further ideas from me. In this vein I hand it over to others
; (though lets see how I do in the competition first.) In the event that I
; win (and my approach is worthwhile analyzing further), I would like to
; offer the following suggestions for further optimizations that I suspect
; may lead to something, but I myself could not work out how:
;
; - The random number generator is horrendously bloated, given its use of 32
; bit registers. Using a simple LFSR may be potential alternative, but its
; not clear that it will both be "random" and shorter than the current
; implementation. Either way, something should be done about it; there's a
; 9 byte instruction in there! (T. Remmel disallowed use of the FPU other-
; wise I would have tried to maintain "RandNum" in the FPU stack.)
;
; - The initial palette table clear feels very redundant considering that the
; InitPal call also walks over the same structure. There ought to be a way
; reinvest less then 9 bytes into clearing that table somehow.
;
; - The self modification for the initial palette set up was an after thought
; (once I learned that not setting the palette on start up constituted lack
; of duplication.) So there might be room for rearchitecting in there
; somewhere to save some of the 6 bytes used in the self modification write
; instruction itself.
;
; - There may be a way to further reduce the partial stack frame used in
; "Adjust". BP is a completely free register, and Adjust does not use any
; more stack, except for the call to "Rand" and tail usage via SetPixel.
; Perhaps retargetting the stack via bp for the pusha/popa's then ripping
; the parameters off the stack with pop's can somehow be made to work.
;
;------------------------------------------------------------------------------
;
; I've had way too much fun with this code. I especially enjoyed it because
; it was not so terribly off from the very beginning as to be too much work
; from the very get go. It really exercised my abstract thinking and there
; were a lot of things that I could do to squeeze bytes here and there.
;
;------------------------------------------------------------------------------
.Model Tiny
.386
.Code
Org 100h
Prog Proc
mov ax,13h ;Set video mode 13h
int 10h
mov bx,9d00h
mov cx,576
mov di,bx ;Zero the palette
xor ax,ax
rep stosw
call InitPal ;First half of palette
mov bx,9d00h+0240h
call InitPal ;Second half of palette
call RotateStart
mov byte ptr [MungePoint],0b4h ; Re-patch opcode.
push 40h ;ES = 40h
pop es
mov eax,es:[6Ch] ;Seed RNG with current time.
mov RandNum,eax
mov bp,offset rand192
mov es,bx ;Side effect, BX = 0A000h, ES points to VGA
mov bx,319 ;Small redundancy savings.
push word ptr 199 ;Draw plasma
push bx
push cx ;Side effect CX = 0.
push cx
push offset Reconnect
push cx
push bp
push 63999
push bp
push 63680
push bp
push bx
rand192:
mov si,95 ;Get random number 1-191
call Rand
add ax,si
pop bx
mov es:[bx],al
ret
Reconnect:
call Plasma
RotateStart:
mov si,9d00h
Rotate: mov dx,03DAh ;Status port
VRTloop2: in al,dx ;Wait for next vertical blank interval
test al,8
jz VRTloop2
mov dl,0C8h ;Index port
mov al,1 ;Set register 1
out dx,al
inc dx ;Data port
mov cx,0240h
rep outsb
add si,3-576 ;Advance palette
cmp si,9d00h+0240h ;Check for wrap
je RotateStart ;Loop back...
MungePoint:
ret
db 01h ; Self-modded to "mov ah,1".
int 16h ; Check for keypress. (Dont wait.)
jz Rotate
Done: mov ax,3 ;Set text mode
int 10h
ret ;Return (exit)
Prog EndP
;**************************** InitPal -- Setup rainbow palette values.
InitPal Proc
mov ah,3fh
PalLoop: mov [bx],ah ;Set palette values
mov [bx+2],al
mov word ptr [bx+193],ax
mov word ptr [bx+384],ax
add bx,3 ;Advance pointers
add ax,0ff01h ;Loop back
jns PalLoop
ret
InitPal Endp
P_Done: push bp
ret ;Return, pop args
;**************************** Plasma -- Recursive plasma procedure
Plasma Proc
pop bp ; Save return address
pop si ; Pull values off stack.
pop ax
pop cx
pop dx
mov bx,si ;x = (x1 + x2) / 2
add bx,cx
sar bx,1
mov di,ax ;y = (y1 + y2) / 2
add di,dx
sar di,1
cmp bx,si ; Implies that |x2-x1|<=1
je P_Done ; Actual recursive termination condition.
push dx
push bx
push di
push si
push bp ;Actual return address.
mov bp,offset Plasma
push dx ;Plasma x, y, x2, y2
push cx
push di
push bx
push bp ;Ret-chain back to plasma.
push dx ;Adjust bottom side
push bx
push dx
push cx
push dx
push si
push bp ;Ret-chain back to plasma.
mov bp,offset Adjust
push ax ;Adjust top side
push bx
push ax
push cx
push ax
push si
push bp
cmp di,ax ; Implies that |y2-y1|<=1
je Adjust
push bp
mov bp,sp
mov word ptr [bp+8*2],offset P_Center
pop bp
push di ;Adjust right side
push cx
push dx
push cx
push ax
push cx
push bp
push di ;Adjust left side
push si
push dx
push si
push ax
push si
push bp
Plasma EndP
;**************************** Adjust -- Random adjust pixel midpoint
Adjust Proc
mov bp,sp
pusha ;Save all registers
cwd ;Sends DX->0 since 0<=ax<200
mov bx,[bp+2]
mov di,[bp+4]
call GetPixel
lea cx,[bx+di]
mov bx,[bp+6]
mov di,[bp+8]
call GetPixel
lea si,[bx+di]
sub si,cx ;SI = |x2 - x1| + |y2 - y1|
call Rand
sar dx,1 ;We know this is equivalent because a carry
add dx,ax ;can never happen on the last bit.
jg $+4
mov dl,1
cmp dl,192
jbe $+4
mov dl,192
mov bx,[bp+10] ;Get values
mov di,[bp+12]
call SetPixel
A_Done: popa ;Restore registers
ret 12 ;Return, pop args
Adjust EndP
;**************************** Additional Plasma fragments
P_Center:
mov bp,offset Plasma
push di ;Plasma x, y1, x2, y
push cx
push ax
push bx
push bp ;Ret-chain back to plasma.
push di ;Plasma x1, y1, x, y
push bx
push ax
push si
push bp ;Ret-chain back to plasma.
push bp
mov bp,offset GetPixel
push bx
push di
mov bx,si
mov di,ax
push di
push dx
cwd ;Same as xor dx,dx since 0<=ax<200
call bp
pop di
call bp
mov bx,cx
call bp
pop di
call bp
pop di
pop bx
shr dx,2 ;DX = average of corners
;**************************** SetPixel -- Write a pixel
SetPixel Proc
call GetPixel
test al,al ; Is pixel already plotted?
jnz SP_Skip ; If so just punt. (DX destroyed.)
mov es:[si+bx],dl ; SI and DL, side effects from GetPixel
SP_Skip: ret
SetPixel EndP
;**************************** GetPixel -- Read a pixel
GetPixel Proc
imul word ptr si,di,0140H
mov al,es:[si+bx]
add dx,ax
ret
GetPixel EndP
;**************************** Rand -- Random number generator
; Random number between in the range {-si, ..., 0, ..., si}.
Rand Proc
pusha ;Save registers
inc si ;SI = maximum
imul dword ptr eax,RandNum,19660Dh
inc ax ;EAX = RandNum * 19660Dh + 1h
mov RandNum,eax ;Save random number
mov ax,word ptr RandNum[2] ;Get top half. (retain randomness)
cwd ;DX:AX = number
idiv si ;Divide by max (note: si can never be 0)
mov bp,sp
mov [bp+0eh],dx ;Change pushed AX
popa ;Restore registers
ret ;Return
Rand EndP
;**************************** DATA section
RandNum dd ?
End Prog
