Difference between revisions of "MELT.COM"

From SizeCoding
Jump to: navigation, search
m (Or you could rethink it completely)
 
(10 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 +
[[Category:Case Study]]
 
MELT.COM was written by an unknown author in the 1980s.  Originally 49 bytes in size, it performs the following cute effect:
 
MELT.COM was written by an unknown author in the 1980s.  Originally 49 bytes in size, it performs the following cute effect:
  
Line 12: Line 13:
  
 
doScreen:                               
 
doScreen:                               
                 mov    cx, 2000        ; Going to loop over all 2000 characters
+
                 mov    cx, 2000        ; Going to loop over all (80*25=)2000 characters
                                        ; (80 * 25 = 2000)
+
                 xor    bx, bx          ; bx = 0.  Also our "num of altered chars" counter
                 xor    bx, bx          ; bx = 0
 
                                        ; bx is also our "num of altered chars" counter
 
 
                 mov    di, bx          ; es:di now points at the screen (b800:0000)
 
                 mov    di, bx          ; es:di now points at the screen (b800:0000)
  
Line 27: Line 26:
 
                 inc    bx              ; increase "number of processed chars" counter
 
                 inc    bx              ; increase "number of processed chars" counter
 
                 jmp    short nextChar  ; Keep processing characters
 
                 jmp    short nextChar  ; Keep processing characters
; ---------------------------------------------------------------------------
 
  
 
upToSpace:                               
 
upToSpace:                               
Line 49: Line 47:
 
* Replace DOS exit sequence with RET, since this is a .COM file
 
* Replace DOS exit sequence with RET, since this is a .COM file
 
* The "CMP bx,0" can be replaced with a shorter test like "OR bx,bx"
 
* The "CMP bx,0" can be replaced with a shorter test like "OR bx,bx"
* There is inefficient loading and saving of screen characters with manually advancing DI twice -- 80x86 has 1-byte string instructions to do that, so we'll use LODSW and STOSW.  This will load the character attribute byte redundantly, but we don't care about speed, we care about size.
+
* There is inefficient loading and saving of screen characters with manually advancing DI twice -- 80x86 has 1-byte string instructions to do that, so we'll use LODSW and STOSW.  This will load the character attribute byte redundantly, but we don't care about speed, we care about size.  Because we only use LODS once, we can shave a byte by getting rid of MOV DS,AX (3 bytes) and using ES: LODS (2 bytes) in the inner loop.
  
This shaves 11 bytes down to 38 total.  At this point we can make some drastic changes that will shave bytes, but also make the program not behave ''exactly'' as it did before.  I chose to do the following:
+
This shaves 12 bytes down to 37 total.  At this point we can make some drastic changes that will shave bytes, but also make the program not behave ''exactly'' as it did before.  I chose to do the following:
  
 
* 2000 is 7D0 in hex.  Change MOV CX,2000 (decimal) to MOV CH,08 (hex) to shave a byte.  This could result in CX being anywhere in the range 0800 to 08FF but the difference is minimal at execution time.  It's also larger than the original area, but that is fine since there is there is extra screen RAM after the visible portion of the screen.
 
* 2000 is 7D0 in hex.  Change MOV CX,2000 (decimal) to MOV CH,08 (hex) to shave a byte.  This could result in CX being anywhere in the range 0800 to 08FF but the difference is minimal at execution time.  It's also larger than the original area, but that is fine since there is there is extra screen RAM after the visible portion of the screen.
 
* The code contains a check for characters below #32 (space) and moves them upward.  Most characters onscreen are going to be above #32, so this isn't really necessary and I removed the check.  Even if it were necessary, removing the check will just rotate them downward until they wrap around to 255, then go downward again until hitting #32 and stopping.
 
* The code contains a check for characters below #32 (space) and moves them upward.  Most characters onscreen are going to be above #32, so this isn't really necessary and I removed the check.  Even if it were necessary, removing the check will just rotate them downward until they wrap around to 255, then go downward again until hitting #32 and stopping.
  
This gets the code down to 30 bytes:
+
This gets the code down to 29 bytes:
  
 
<syntaxhighlight lang=nasm>
 
<syntaxhighlight lang=nasm>
Line 62: Line 60:
  
 
                 mov    ah, 0B8h
 
                 mov    ah, 0B8h
                 mov    es, ax          ; es now points to screen segment
+
                 mov    es, ax          ; es so we can use es: LODS and STOS to the same place
                mov    ds, ax          ; ds = es so we can LODS and STOS to the same place
 
  
 
doScreen:
 
doScreen:
Line 72: Line 69:
  
 
alterChars:
 
alterChars:
                 lodsw                   ; Retreive onscreen character
+
                 es: lodsw               ; Retreive onscreen character
 
                 cmp    al, 32          ; comp to a space character (#32)
 
                 cmp    al, 32          ; comp to a space character (#32)
 
                 jz      short nextChar  ; If already a space, do nothing
 
                 jz      short nextChar  ; If already a space, do nothing
Line 87: Line 84:
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Optimizing this further is left as an exercise to the reader.  It may be possible to shrink it further using instructions for the 80186 and later processors, but it runs way too quickly on those systems, so if doing so you may want to insert a HLT to pace the animation at 18.2 Hz.  It may also be possible to shrink it by taking advantage of the fact that ASCII character #0 is a null and shows nothing onscreen (just like the #32 space character), so instead of decrementing down to #32, you could decrement down to #0 in a more optimized form (like using the zero flag).
+
Optimizing the above is left as an exercise to the reader.  It may be possible to shrink it further using instructions for the 80186 and later processors, but it runs way too quickly on those systems, so if doing so you may want to insert a HLT to pace the animation at 18.2 Hz.  It may also be possible to shrink it by taking advantage of the fact that ASCII character #0 is a null and shows nothing onscreen (just like the #32 space character), so instead of decrementing down to #32, you could decrement down to #0 in a more optimized form (like using the zero flag).
  
 +
== Or you could rethink it completely ==
  
 +
If you're willing to deviate from the original target environment (namely, that it was designed for a 4.77 MHz 8088), you can eliminate range checking for all sorts of optimizations. 
 
Instead of using two pointers/segments, it's possible to use only one, and directly operate on the chars on screen. Combined with optimized segment assignment and exclusion of the "processed chars"-count (fixed amount of iterations, set to the maximum possible 65536 * 255) this results in a 17 byte variation :
 
Instead of using two pointers/segments, it's possible to use only one, and directly operate on the chars on screen. Combined with optimized segment assignment and exclusion of the "processed chars"-count (fixed amount of iterations, set to the maximum possible 65536 * 255) this results in a 17 byte variation :
  
Line 97: Line 96:
 
doChar:
 
doChar:
 
scasw ; used to advance DI by 2, and as DS high byte (0AFh)
 
scasw ; used to advance DI by 2, and as DS high byte (0AFh)
cmp byte [di],32 ; is the current char on screen a "space"?
+
cmp byte [di],32     ; is the current char on screen a "space"?
 
jz short skip ; yes, don't decrement
 
jz short skip ; yes, don't decrement
 
dec byte [di] ; nope, decrement
 
dec byte [di] ; nope, decrement
Line 106: Line 105:
 
ret ; quit
 
ret ; quit
 
</syntaxhighlight>
 
</syntaxhighlight>
 +
 +
The above performs the same function as the previous optimization, but runs much more slowly as it traverses more RAM areas than necessary.
  
 
There might be a way of altering the <code>NOP</code> to something useful.
 
There might be a way of altering the <code>NOP</code> to something useful.
 +
 +
Returning to the non-printing null char, we can shave one more byte, to produce this 16 bytes version:
 +
 +
<syntaxhighlight lang=nasm>
 +
lds bx,[si] ; load DS from our code "scasw" + "nop" = 0AF90h
 +
nop ; for alignment, maybe optimization potential here ;)
 +
doChar:
 +
scasw ; used to advance DI by 2, and as DS high byte (0AFh)
 +
cmp byte [di],al     ; is the current char on screen a "null"?
 +
jz short skip ; yes, don't decrement
 +
dec byte [di] ; nope, decrement
 +
skip:
 +
dec dx ; first loop, besides the first time
 +
jnz doChar ; it's 65536 iterations
 +
loop doChar ; second loop, 255 times
 +
ret ; quit
 +
</syntaxhighlight>
 +
 +
The above performs a similar function as the previous optimization, but runs even more slowly as it requires regular characters to be decremented further than before.
 +
 +
Note the <CODE>CMP/JZ/DEC</CODE> sequence.  If we can control the carry flag as a result of the comparison, then we can perform a conditional decrement without the branch, via an <CODE>ADC</CODE>.
 +
 +
Of course, if the AL register is zero, then there can never be a carry as a result of the comparison, but if we increase AL to 1, then every value other than zero will clear the carry.
 +
 +
To increase the AX register would normally cost us one byte, but we happen to have one to spare in the <CODE>LDS</CODE> alignment.
 +
 +
That allows us to shave one more byte, to produce this 15 bytes version:
 +
 +
<syntaxhighlight lang=nasm>
 +
lds bx,[si] ; load DS from our code "scasw" + "inc" = 0AF40h
 +
inc ax ; set AL to 1, also for alignment
 +
doChar:
 +
scasw ; used to advance DI by 2, and as DS high byte (0AFh)
 +
cmp byte [di],al     ; is the current char on screen a "null"?
 +
adc byte [di],0ffh  ; if not, then decrement
 +
dec dx ; first loop, besides the first time
 +
jnz doChar ; it's 65536 iterations
 +
loop doChar ; second loop, 255 times
 +
ret ; quit
 +
</syntaxhighlight>

Latest revision as of 02:24, 15 August 2016

MELT.COM was written by an unknown author in the 1980s. Originally 49 bytes in size, it performs the following cute effect:

(The video is simulated and shows how MELT performs on the old hardware it was written for.) This effect is achieved by increasing or decreasing each onscreen character's value until it reaches #32, the space character. The original source is lost to history, but here's a quick commented disassembly:

                org 100h

                mov     ax, 0B800h
                mov     es, ax          ; es now points to screen segment

doScreen:                               
                mov     cx, 2000        ; Going to loop over all (80*25=)2000 characters
                xor     bx, bx          ; bx = 0.  Also our "num of altered chars" counter
                mov     di, bx          ; es:di now points at the screen (b800:0000)

alterChars:                             
                mov     ah, es:[di]     ; Retreive onscreen character
                cmp     ah, 32          ; comp to a space character (#32)
                jz      short nextChar  ; If already a space, do nothing
                jl      short upToSpace ; If lower than a space, increase upward
                dec     ah              ; If higher than a space, decrease downward
                mov     es:[di], ah     ; Store altered character back to screen
                inc     bx              ; increase "number of processed chars" counter
                jmp     short nextChar  ; Keep processing characters

upToSpace:                              
                inc     ah              ; Increase character upwards towards a space
                mov     es:[di], ah     ; Store altered character back to screen
                inc     bx              ; increase "number of processed chars" counter

nextChar:                               
                inc     di
                inc     di              ; es:di now points to next character
                loop    alterChars      ; Continue processing characters
                cmp     bx, 0           ; Were any characters processed?
                jnz     short doScreen  ; If so (bx != 0), keep processing
                mov     ah, 4Ch         ; Otherwise, get ready to terminate
                int     21h             ; DOS - 2+ - QUIT WITH EXIT CODE (EXIT)

There are some very quick wins right off the bat:

  • AX is already 0, so set AX=B800 by setting AH=B8
  • Replace DOS exit sequence with RET, since this is a .COM file
  • The "CMP bx,0" can be replaced with a shorter test like "OR bx,bx"
  • There is inefficient loading and saving of screen characters with manually advancing DI twice -- 80x86 has 1-byte string instructions to do that, so we'll use LODSW and STOSW. This will load the character attribute byte redundantly, but we don't care about speed, we care about size. Because we only use LODS once, we can shave a byte by getting rid of MOV DS,AX (3 bytes) and using ES: LODS (2 bytes) in the inner loop.

This shaves 12 bytes down to 37 total. At this point we can make some drastic changes that will shave bytes, but also make the program not behave exactly as it did before. I chose to do the following:

  • 2000 is 7D0 in hex. Change MOV CX,2000 (decimal) to MOV CH,08 (hex) to shave a byte. This could result in CX being anywhere in the range 0800 to 08FF but the difference is minimal at execution time. It's also larger than the original area, but that is fine since there is there is extra screen RAM after the visible portion of the screen.
  • The code contains a check for characters below #32 (space) and moves them upward. Most characters onscreen are going to be above #32, so this isn't really necessary and I removed the check. Even if it were necessary, removing the check will just rotate them downward until they wrap around to 255, then go downward again until hitting #32 and stopping.

This gets the code down to 29 bytes:

                org 100h

                mov     ah, 0B8h
                mov     es, ax          ; es so we can use es: LODS and STOS to the same place

doScreen:
                mov     ch, 08          ; (80 * 25 = 2000/07d0h)
                xor     bx, bx          ; bx is also our "num of altered chars" counter
                mov     di, bx          ; es:di now points at the screen (b800:0000)
                mov     si, di          ; ds:si = es:di, needed for lods/stos

alterChars:
                es: lodsw               ; Retreive onscreen character
                cmp     al, 32          ; comp to a space character (#32)
                jz      short nextChar  ; If already a space, do nothing
                dec     al              ; If higher than a space, decrease downward
                inc     bx              ; increase "number of processed chars" counter

nextChar:
                stosw
                loop    alterChars      ; Continue processing characters
                or      bx,bx           ; Were any characters processed?
                jnz     short doScreen  ; If so (bx != 0), keep processing
                ret                     ; exit

Optimizing the above is left as an exercise to the reader. It may be possible to shrink it further using instructions for the 80186 and later processors, but it runs way too quickly on those systems, so if doing so you may want to insert a HLT to pace the animation at 18.2 Hz. It may also be possible to shrink it by taking advantage of the fact that ASCII character #0 is a null and shows nothing onscreen (just like the #32 space character), so instead of decrementing down to #32, you could decrement down to #0 in a more optimized form (like using the zero flag).

Or you could rethink it completely

If you're willing to deviate from the original target environment (namely, that it was designed for a 4.77 MHz 8088), you can eliminate range checking for all sorts of optimizations. Instead of using two pointers/segments, it's possible to use only one, and directly operate on the chars on screen. Combined with optimized segment assignment and exclusion of the "processed chars"-count (fixed amount of iterations, set to the maximum possible 65536 * 255) this results in a 17 byte variation :

			lds		bx,[si]			; load DS from our code "scasw" + "nop" = 0AF90h
			nop						; for alignment, maybe optimization potential here ;)
doChar:
			scasw					; used to advance DI by 2, and as DS high byte (0AFh)
			cmp 	byte [di],32	    ; is the current char on screen a "space"?
			jz		short skip 		; yes, don't decrement
			dec 	byte [di]		; nope, decrement
skip:
			dec 	dx				; first loop, besides the first time 
			jnz 	doChar			; it's 65536 iterations
			loop 	doChar			; second loop, 255 times
			ret						; quit

The above performs the same function as the previous optimization, but runs much more slowly as it traverses more RAM areas than necessary.

There might be a way of altering the NOP to something useful.

Returning to the non-printing null char, we can shave one more byte, to produce this 16 bytes version:

			lds		bx,[si]			; load DS from our code "scasw" + "nop" = 0AF90h
			nop						; for alignment, maybe optimization potential here ;)
doChar:
			scasw					; used to advance DI by 2, and as DS high byte (0AFh)
			cmp 	byte [di],al	    ; is the current char on screen a "null"?
			jz		short skip 		; yes, don't decrement
			dec 	byte [di]		; nope, decrement
skip:
			dec 	dx				; first loop, besides the first time 
			jnz 	doChar			; it's 65536 iterations
			loop 	doChar			; second loop, 255 times
			ret						; quit

The above performs a similar function as the previous optimization, but runs even more slowly as it requires regular characters to be decremented further than before.

Note the CMP/JZ/DEC sequence. If we can control the carry flag as a result of the comparison, then we can perform a conditional decrement without the branch, via an ADC.

Of course, if the AL register is zero, then there can never be a carry as a result of the comparison, but if we increase AL to 1, then every value other than zero will clear the carry.

To increase the AX register would normally cost us one byte, but we happen to have one to spare in the LDS alignment.

That allows us to shave one more byte, to produce this 15 bytes version:

			lds		bx,[si]			; load DS from our code "scasw" + "inc" = 0AF40h
			inc		ax				; set AL to 1, also for alignment
doChar:
			scasw					; used to advance DI by 2, and as DS high byte (0AFh)
			cmp 	byte [di],al	    ; is the current char on screen a "null"?
			adc 	byte [di],0ffh  ; if not, then decrement
			dec 	dx				; first loop, besides the first time 
			jnz 	doChar			; it's 65536 iterations
			loop 	doChar			; second loop, 255 times
			ret						; quit