Sunday 21 September 2008

Optimising Assembly Like an 80's Hacker

Forget about fancy algorithms and data structures. If you want respect as an 80's hacker, follow these simple tips.

Never get caught setting a register to zero without using xor:

Z80 Code
ld a,0           ; bad, 2 bytes / 7 cycles

xor a ; good, 1 byte / 4 cycles

8088 Code
mov ax,0         ; bad, 3 bytes / 4 cycles

xor ax,ax ; good, 2 bytes / 3 cycles

Never set two 8 bit register independently. Code readability is not required:

Z80 Code
ld b,10          ; bad, 4 bytes / 14 cycles
ld c,32

ld bc,10*256+32 ; good, 3 bytes / 11 cycles

8088 Code
mov ch,10        ; bad, 4 bytes / 8 cycles
mov cl,32

mov cx,10*256+32 ; good, 3 bytes / 4 cycles

Never compare to zero:

Z80 Code
cp 0             ; bad, 2 bytes / 7 cycles

or a ; good, 1 byte / 4 cycles

8088 Code
cmp ax,0         ; bad, 3 bytes / 4 cycles

test ax,ax ; good, 2 bytes / 3 cycles

Remember, you don't need to worry about code alignment, order of instructions or processor penalties. Follow these simple tips and your super-optimised bubble sort will demand the utmost respect!

Friday 12 September 2008

Al Zimmermann's Programming Contests

Normally I don't participate in programming challenges, but something about the latest of Al Zimmermann's Programming Contests caught my attention.

The idea is to submit sets of numbers so their combination by addition and subtraction generates the most distinct primes.  There are 12 problems, for sets of 3 to 14 numbers.

A pen and paper should be sufficient to find the optimal solution for 3 numbers.  Don't be fooled however, the solutions for 4+ require a program to search through the possibilities.

4 yields easily to a computer search with at least three optimal solutions waiting to be discovered.  Despite writing a program which tests 280,000 potential solutions per second, I haven't found the top solution for 5.

Currently I'm restricting the search space to one odd number, one multiple of 6 and the remaining numbers all multiples of 30.  Maybe this is too restrictive?

Here's the program I'm using.  Any suggestions how I can improve the speed?
n1 equ 1
n2 equ 6
n3 equ 30
n4 equ 90
n5 equ 270

i1 equ 600
i2 equ 600

vprime equ 7000

numb equ 5

; *** generate list of primes

mov si,prime+4
mov bx,5
nextpr:
mov di,prime+2
try:
mov ax,bx
xor dx,dx
div word[di]
or dx,dx
jz notpr
scasw
ja try
mov word[si],bx
cmpsw
notpr:
inc bx
inc bx
cmp si,prime+vprime
jne nextpr

; *** fill prime table with zero

xchg ax,bx
mov di,tabl
xchg ax,cx
xor ax,ax
rep stosb

; *** update values to test

testnew:
add word[xa],2
cmp word[xa],n1+i1+10
jc gogo
mov word[xa],n1

add word[xb],6
cmp word[xb],n2+i2+10
jc gogo
mov word[xb],n2

add word[xc],30
mov ax,word[xc]
cmp ax,word[xd]
jc gogo
mov word[xc],n3

add word[xd],30
mov ax,word[xd]
cmp ax,word[xe]
jc gogo
mov word[xd],n4

add word[xe],30

; *** mark primes in table

gogo:
mov ax,word[xa]
add ax,word[xe]
add ax,word[xd]
add ax,word[xc]
add ax,word[xb]
xchg dx,ax
mov si,prime
ptab:
lodsw
cmp dx,ax
jc fini
add ax,tabl
xchg bx,ax
mov byte[bx],1
cmp si,prime+vprime
jne ptab
fini:

; *** test

xor bp,bp
mov ax,word[xa]
mov bx,word[xe]
mov cx,word[xd]
mov dx,word[xc]
mov di,word[xb]

call x2

; *** if there's a new top score...

xchg ax,bp
cmp ax,word[xhigh]
jl next

; *** ... display the winning numbers

mov word[xhigh],ax
call printdec

mov dl,' '
call printchar
mov dl,'-'
call printchar

mov cx,numb
lea si,word[xa]
disp:
mov dl,' '
call printchar
lodsw
call printdec
loop disp

mov dl,0D
call printchar
mov dl,0A
call printchar

; *** and repeat

next:
mov ah,1
int 016h
jz redo
int 020h
redo:
jmp testnew


x2:
push ax
add ax,bx
call x3
pop ax
push ax
sub ax,bx
call x3
pop ax

x3:
push ax
add ax,cx
call x4
pop ax
push ax
sub ax,cx
call x4
pop ax

x4:
push ax
add ax,dx
call x5
pop ax
push ax
sub ax,dx
call x5
pop ax

x5:
push ax
add ax,di
call x6
pop ax
push ax
sub ax,di
call x6
pop ax

x6:
xabs:
neg ax
js xabs
add ax,tabl
xchg ax,si
cmp byte[si],0
je notprx
inc bp
mov byte[si],0
notprx:
xchg ax,si
ret

; *** print number in ax

printdec:
push ax
push cx
push dx
mov cx,10
xor dx,dx
div cx
test ax,ax
je pdbye
call printdec
pdbye:
add dl,'0'
call printchar
pop dx
pop cx
pop ax
ret

printchar:
mov ah,2
int 021
ret

xhigh:dw 0

xa:dw n1-2
xb:dw n2
xc:dw n3
xd:dw n4
xe:dw n5

prime:
dw 2
dw 3

tabl equ prime+vprime+10

Tuesday 2 September 2008

Five Programming Books I Couldn't Survive Without

There's roughly 400 programming books on my bookshelf.  If I had to reduce it to just five, here are the books I just couldn't live without.
  1. Introduction to Algorithms - Cormen, Leiserson, Rivest & Stein.  This programming book provides in depth yet accessible coverage of many algorithms.  If I want to get the job done as quickly and painfree as possible, I reach for Introduction to Algorithms before Knuth's The Art of Computer Programming every time.
  2. Compilers: Principles, Techniques and Tools - Aho, Sethi & Ullman.  "The Dragon Book" provides an excellent introduction to compiling before getting stuck into the inner workings of analysis, translation, code generation and optimisation.
  3. The New Turing Omnibus - Dewdney.  Sitting atop the fun programming books category, Dewdney's book offers 66 articles covering a variety of computer science topics and recreational computing problems.
  4. Fundamentals of Operating Systems - Lister.  The way the structure of this book mirrors the structure of an operating system makes it an easier point of reference than books such as Krakowiak's Principles of Operating Systems.
  5. Advanced Spectrum FORTH - Thomasson.  Depite being written for a sadly obsolete platform, Advanced Spectrum FORTH remains one of the best FORTH programming books.  The source code for the dictionary provides a valuable resource.
Disagree?  Think I've missed out a classic programming book?  Drop me a comment below.