## 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 cyclesxor a            ; good, 1 byte / 4 cycles`

8088 Code
`mov ax,0         ; bad, 3 bytes / 4 cyclesxor 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 cyclesld c,32ld bc,10*256+32  ; good, 3 bytes / 11 cycles`

8088 Code
`mov ch,10        ; bad, 4 bytes / 8 cyclesmov cl,32mov cx,10*256+32 ; good, 3 bytes / 4 cycles`

Never compare to zero:

Z80 Code
`cp 0             ; bad, 2 bytes / 7 cyclesor a             ; good, 1 byte / 4 cycles`

8088 Code
`cmp ax,0         ; bad, 3 bytes / 4 cyclestest 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:
cmp word[xa],n1+i1+10
jc gogo
mov word[xa],n1

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

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

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

; *** mark primes in table

gogo:
mov ax,word[xa]
xchg dx,ax
mov si,prime
ptab:
lodsw
cmp dx,ax
jc fini
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
call x3
pop ax
push ax
sub ax,bx
call x3
pop ax

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

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

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

x6:
xabs:
neg ax
js xabs
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:
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.