Executable Compressors

An exe packer is a utility to reduce the size of executable files. It compresses a program and creates a new program with the compressed data and code to extract and run the original. Commonly used compression techniques include variants of Run Length Encoding and members of the LZ family of algorithms.

It's debatable whether there's still any real benefit to compressing exe files. Originally the reduced storage space would have been an advantage as would the slightly reduced disk (or even tape) load time. Nowadays the potential benefits are lower network bandwidth and smaller downloads.

Exe compressors present some interesting challenges for a programmer. The effectiveness of the compression has to be balanced against the size of the decompressor. The compression algorithm has to be chosen carefully for speedy decompression. If the program has a relocation table, what's the best way to optimise it? How can the additional memory requirements be minimised?

It shouldn't come as any surprise that hundreds of programmers have risen to the challenge and written an exe packer. A quick search of the net turns up at least 80 for DOS / Windows and several for other environments.

In 8086 assembly, a Run Length decoder for a DOS .COM file can be written in under 40 bytes and decoders for the simplest LZ77 derivatives in under 50 bytes. Here's an example RLE decoder:

; 8086 .COM RLE decoder

move:   ; copy unpacker and compressed
; code elsewhere in memory

mov si, unpack
mov di, freemem
mov cx, codeend-unpack
push di
rep movsb

; setup RLE paremeters

mov si, freemem+code-unpack
mov di, program
mov bx, num_of_tokens

; transfer control to unpack

ret

; unpack compressed program

unpack: push di
rle:    lodsb
cmp al, token
jne single
lodsw
mov cl,ah
db 0F3h ; rep
single: stosb
dec bx
jne rle

; transfer control to program

ret

code:   ; .....

codeend:

If you have any thoughts on the advantages / disadvantages of exe packers or any implementation ideas I'd love to hear them. Also does anyone know anything about the history of exe packers? The earliest I've found is from November 1987.

Implement MIN in Forth without Conditional Code

While lurking in the #forth channel on irc.freenode.net I was pointed to an interesting problem from the Gforth tutorial. The problem is to implement MIN in Forth without any conditionally executed code.

DO, LOOP, BEGIN, UNTIL, REPEAT, WHILE, IF, ELSE and THEN are all forbidden.  MIN removes the top two values from the data stack then puts the lower of the two back on.

Can you implement MIN under these conditions? If so I challenge you implement it in as few Forth words as possible! Let me know if your implementation is under 10 words :-)

BF Joust King of the Hill

BF Joust is a capture the flag programming game based on the esoteric Brainf*** programming language. Recently ais523 revised the language and enviroment, setting up a king of the hill tournament.

The game is played between two programs on a tape with a length randomly chosen between 10 and 30 cells. The cells initially contain 0 with the exception of the cells at either end which contain the flag 128.

Each program views the tape with their own flag on the left and the opponent's flag on the right. The object of the game is to find and set the opponents flag to 0 and keep it 0 for two consecutive cycles. If a program's pointer points to a location off the tape, it loses.

Here's a quick summary of the instruction set:

Op	Description
<	move the pointer to the left
>	move the pointer to the right
+	add 1 to the value stored at pointer
-	subtract 1 from the value stored at pointer
[	jump past the matching ] if the cell at pointer is 0
]	jump to instruction after matching [ unless cell at pointer is 0
.	no operation, do nothing

The interpreter also understands certain macros. Instructions inside parentheses are repeated a number of times. For example (>-)*4 expands to >->->->-.

For full details see the rules on the BF Joust Wiki page and check the current hill standings. To submit a program to the BF Joust hill, join the channel #esoteric on irc.freenode.net and send a message to egobot:

/msg egobot !bfjoust program_name program_code

It isn't possible to remove a program, but it can be replaced by submitting another with the same name.

Finally, I'll leave you with the code for shortsword the current king of the hill with 100% wins ;-)

(>++>--)*2(>)*6([-[+]]>)*20

The standings:

ID Score Pts Program
18 90.00  18 shortsword.bfjoust
19 71.12  12 stranger.bfjoust
16 69.75  11 scythe_impomatic.bfjoust
 1 59.38   9 ais523_attack5.bfjoust
 6 42.50   4 ais523_defend5.bfjoust
 2 41.50   6 ais523_attackslow.bfjoust
 7 38.00   2 asie1.bfjoust
 0 37.00   0 ais523_attack2.bfjoust
12 32.38  -1 fool1.bfjoust
 9 28.00   0 attack1.bfjoust
 4 18.25  -4 ais523_defend0_1.bfjoust
 3 16.25  -5 ais523_defend0.bfjoust
11 11.88  -9 ehirdomatic.bfjoust
10 10.50  -7 defend1.bfjoust
 5 10.50  -5 ais523_defend1.bfjoust
17  5.62  -4 shield.bfjoust
15  5.62  -9 programname.bfjoust
14  2.62 -10 nop.bfjoust
 8  2.62  -8 asie2.bfjoust
20  0.00   0 stuff.bfjoust
13  0.00   0 iwin.bfjoust

Let me know if you have any success with BF Joust.

CoreLife: Programming in 2 Dimensions!

For a while I've been promising to take a closer look at Dennis Luehring's list of programming games to select a few for further investigation. The list contains over 1500 links in 200 categories!

The first I've chosen is CoreLife, a 2D variant of Corewar by Brent Adams. CoreLife is one of the earliest 2D programming languages, predating Befunge by a few months.

Battles take place on a 100 × 100 memory grid. The outcome of a battle isn't uniquely determined by the initial conditions as there's a random element to the game.

Unfortunately, there's very little information about CoreLife strategies. There are 13 published battle programs. Most of these launch imps or bomb the grid with protected locations. Battle programs are often surrounded by a membrane or shield of protected locations. Despite this CoreLife has the potential to support more complex programs, for example replicators.

I've set myself the challenge of writing a replicator. First I'll attempt to write something linear and if that's successful, a square replicator! Has anyone experimented with CoreLife and if so, did you create a successful program or discover anything interesting?

For more information about programming games, take a look at Steven Robbins' list of programming games or Dennis Luehring's list of programming games.

The Recursive Universe by William Poundstone

In The Recursive Universe, William Poundstone uses Conway's Life as a vehicle to explore complexity theory and modern physics. Poundstone demonstrates how simple rules can produce complex results when applied recursively and suspects our own universe was created in a similar manner.

Conway's Game of Life was devised by John Conway in 1970. The Game of Life is played on a grid of square cells, each of which can be in one of two states, dead or alive. Three simple rules are applied repeatedly, first to the initial pattern, then to each new pattern in turn:

• a live cell with less than 2 neighbours dies
• a live cell with more than 3 neighbours dies
• a dead cell with 3 neighbours becomes a live cell

Each cell has eight neighbours, 2 horizontally, 2 vertically and 4 diagonally. Conway's Game of Life is also know as 23/3 Life. This indicate a live cell survives if it has 2 or 3 neighbours and a dead cell becomes live if it has 3 neighbours.

The Recursive Universe briefly explores some variations of Life, for example 34/34 Life. I'm currently experimenting with some other variations and will let you know the results shortly.

A Quick Look at a Programmer's Bookshelf

One of the best ways to get to know someone is to look at their bookshelf. -- Kathy Sierra

Here's a quick look at the programming section of the bookshelf next to my desk. It reflects my current interests pretty well:

• algorithms, Knuth and Introduction to Algorithms
• compilers, including the red and green dragon books
• operating system development
• artificial life
• assembly language, books on 68000, 8086 and 6809
• computer history, Hackers and Fire in the Valley
• web development

What's on your bookshelf?

Playing with the Arduino Microcontroller Board

Here are a couple of pictures of my latest toy, the Arduino Duemilanove microcontroller. It's equipped with 16K flash memory, 1K SRAM and 0.5K EEPROM and is currently sitting on my desk, flashing out "hello world" in Morse Code. The processor is an Atmel ATMega168 running at 16MHz.

Now I just need to learn the assembly language so I can implement something useful :-)