In August 2001 I came up with a crazy idea: I went on the
comp.os.os2.programmer.misc
newsgroup and announced an "OS/2 Miniaturization Contest", that is a
contest
for OS/2 programmers with the goal of creating the smallest possible
program
fulfilling a set of conditions. The important conditions were:
Before I announced the contest I already had some ideas about how to create very small executables. But even I was surprised by the winning programs. The winners of the three categories were:
The most amazing is of course the Custom category winner. Especially if you realize that the size of the LX header is 196 bytes and the OS/2 loader will refuse to even try loading anything smaller than 196 bytes. This header-sized executable however prints a 17-byte message and returns to the system without crashing. I will not discuss this category in detail and instead refer readers to Martin Lafaix's dissection of his winning program (aptly named Fandango on Core).
Now that I'm done with the contest background, on to some juicy code. The code that I will present here is my own but it includes many ideas from the winners. I built all the code using Watcom 11.0c tools but it should be possible to adapt them for use with other assemblers/compilers, perhaps excluding the most advanced C code. I will explain all the compiler and linker switches that are not immediately obvious.
I assume that the reader has working knowledge of assembly, C, the
x86
architecture and OS/2 executable format and execution environment. This
is decidedly not beginner stuff although beginners might learn a trick
or two, if they won't be too overwhelmed. If they are, well, come back
in a year or two. I was once a beginner too.
Okay, so how do you print a message on the console using the OS/2 API? The first immediately obvious choice is DosWrite. But DosWrite has some serious drawbacks. It requires four parameters (ie. four DWORDs on stack) and it lives in DOSCALLS.DLL (the OS/2 kernel really) which has rather long name that will have to be embedded in the executable.
So let's look around some more. There happens to be another rarely used OS/2 API which we can use. It is DosPutMessage. It only has three parameters and even better, is located in MSG.DLL (short module name).
The entire source of a program (called asm1.asm) using DosPutMessage looks like this:
.386p
EXTRN DosPutMessage:BYTE
_DATA SEGMENT BYTE PUBLIC
USE32
'STACK'
_msg:
DB "I'm really small!",0aH
_DATA ENDS
_TEXT SEGMENT BYTE PUBLIC
USE32
'CODE'
ASSUME CS:_TEXT, DS:_TEXT, SS:_TEXT
startup:
push offset flat:_msg
push 12H
push 1
call near ptr
flat:DosPutMessage
add esp,0CH
ret
_TEXT ENDS
END startup
As you can see, this program is very short and doesn't use any tricks. The only "trick" is that it doesn't use DosExit and just RETs instead. That will in effect execute DosExit with default parameters. After assembling with WASM and linking with WLINK you'll end up with a 545 byte program. The exact commands I used were
wasm asm1.asm
wlink file asm1 lib os2386 option st=32k
The only perhaps not entirely obvious switch is op st=32k which sets the stack to 32 kilobytes. Without this, the program would only have 18 bytes of stack (the message it should print) and would crash right when starting up.
While 545 bytes is not that bad in the age of bloatware, it's easy to improve the size a lot using LxLite:
lxlite /T /ZS:512 asm1.exe
The tricky part here is stripping the MS-DOS stub program (the /T and /ZS options) which is 128 bytes large and significantly contributes to program's size. OS/2 is quite capable of running programs without the stub. MS-DOS won't be able to run them of course but that was not a requirement of the contest. LxLite does some further optimizations too and the result is a 325 byte program. This is much better than 545 but still nowhere near the winners. The masters apparently have some aces up their sleeves. So let's take a look at them.
To achieve minimum sizes, it is necessary to attack on several fronts. The obvious one is to reduce program code. The non-obvious one is to reduce the LX structure overhead.
So let's start with something entirely different. There is one more way to reduce program size. While I believe there is no better way to print a message using the base OS/2 API, Warp 4 (the baseline for the contest) does provide one little known way which is even more suitable. Warp 4 comes with a C runtime DLL which is somewhat altered version of VisualAge C++ version 3 C runtime DLL. There are actually several versions of the DLL - LIBCS.DLL (single-threaded), LIBCM.DLL (multi-threaded) and LIBCN.DLL (subsystem). These provide vprintf() and puts() which both only require a single argument. I chose puts() because it allows for further optimization in leaving out the newline from the message (puts() prints newline automatically). However the ordinal of vprintf() requires one less byte of storage in the import table of the resulting executable so the end result is the same. Anyway here's asm2.asm:
.386p
EXTRN puts:BYTE
_DATA SEGMENT BYTE PUBLIC
USE32
'STACK'
_msg:
DB "I'm really small!"
_DATA ENDS
_TEXT SEGMENT BYTE PUBLIC
USE32
'CODE'
ASSUME CS:_TEXT, DS:_TEXT, SS:_TEXT
startup:
mov eax,offset flat:_msg
jmp near puts
_TEXT ENDS
END startup
Note that puts() (and vprintf() too) require a NULL terminated string, unlike DosPutMessage. But because we know (don't we?) that the data segment is guaranteed to be initialized with zeros, we can leave that out. Another important thing to remember is that puts() uses the _Optlink calling convention with parameters passed via registers and not stack.
This program uses one other interesting optimization. Instead of calling puts(), it jumps to it. When puts() returns, it will return directly to the caller of our program which saves us a RET instruction. Even better, the fixup for puts() is initialized with zeros in the executable image which allows the linker and/or LxLite to save further 4 bytes. The executable is now 318 bytes big. Enjoy the beauty of a program that is two instructions long and actually does something, without even crashing. Now the ride starts getting real interesting.
To get to the winning range, we need to get rid of some 45 bytes of excessive fat. This might seem impossible because the program already is quite small. So let's get nasty and do things little kids aren't allowed to. It's really simple but very non-obvious, as asm3.asm shows:
.386p
EXTRN puts:BYTE
_TEXT SEGMENT BYTE PUBLIC
USE32
'STACK'
ASSUME CS:_TEXT, DS:_TEXT, SS:_TEXT
_msg:
DB "I'm really small!",0
startup:
mov eax,offset flat:_msg
jmp near puts
_TEXT ENDS
END startup
Yes, this program has only one segment! This segment doesn't have the executable flag but it runs just fine and that's important... what's more important, it's only 283 bytes. We're in the winning range! So where do we save more bytes? There are two ways. One of them is extremely simple: rename the executable! The module name is stored within the executable and to save precious bytes, you can use an empty name (.exe). Another way to save space is the first instruction of the program. The MOV takes five bytes in the executable whereas the JMP only takes one byte (because the zeros of the address fixup are left out).
We happen to know what the MOV instruction will put into EAX. It will be 10000H (64K) because that's the linear address where the executable will always be loaded. Knut St. Osmundsen came up with the most elegant method of loading 10000H into EAX in 3 bytes of code. This is the final version of the program source (asm4.asm):
.386p
EXTRN puts:BYTE
_TEXT SEGMENT BYTE PUBLIC
USE32
'STACK'
ASSUME CS:_TEXT, DS:_TEXT, SS:_TEXT
_msg:
DB "I'm really small!",0
startup:
dec ax
inc eax
jmp near puts
_TEXT ENDS
END startup
Here are the commands I used to build the executable:
wasm asm4.asm
wlink f asm4 n .exe imp puts LIBCS.362 op st=32k
ren .exe asm4.exe
lxlite /T /ZS:512 asm4.exe
For those unfamiliar with WLINK directives, the imp puts LIBCS.362 directive tells the linker that symbol puts is imported from library LIBCS as ordinal 362. We could have used LIBCM just as well but the mini-program is single threaded so LIBCS works just fine. As for the ordinal, it is easy to find it with EXEHDR. It would have been possible to use an import library but using the import directive doesn't require one to actually have the import library. This way even the few poor souls who still don't have the Warp 4 Toolkit can build the program.
The trick is the n .exe directive (Name). That tells WLINK to use an empty module name. The final size is now 274 bytes, and this is as far as the Watcom tools will go (at least I think so). Knut's winning program is one byte smaller but that's due to difference between executables produced with WLINK and ILINK, there is no way to control it. And hey, 274 bytes isn't bad either.
It is interesting to note that the entire program source code is
very
small and even the commands used to build it aren't very complex. But
this
is deceptive because the program implicitly relies on a number of
features
of the x86 architecture as well as the OS/2 32-bit execution
environment.
void puts(char *s);
#pragma data_seg("MYDATA", "STACK")
#pragma code_seg("MYDATA", "STACK")
char msg[] = "I'm really small!";
void _System startup(void) {
puts(msg);
}
This is built with the following commands:
wcc386 -s -g=DGROUP mini.c
wlink sys os2v2 name .exe f mini imp puts_ LIBCM.362 op
start=startup,st=32k,nod
ren .exe minic.exe
lxLite.exe /T /ZS:512 minic.exe
The resulting executable, minic.exe, is only 276 bytes in size! How is that possible? Closer inspection reveals that the only difference between the C and assembly versions is the program code. The C program uses code equivalent to this:
mov eax,offset
flat:_msg
jmp near puts
Yes, the compiler is pretty damn clever and optimized the code as much as it could. Because the compiler has no idea where the code will finally end up, it cannot replace the offset to the message with a constant. Apart from this, the C version uses all the tricks explained in the assembly section.
The tricky part here is convincing the compiler and linker to build this program. To achieve that, two rarely used pragmas are needed. The #pragma data_seg and code_seg are fairly standard (in that most compilers support some equivalent functionality) and determine the segment where the data and generated code will be placed. In this case the code and data segments are the same of course. Why do they have class STACK? That's because WLINK requires a segment with that class to be present when linking the final executable.
Now for the compiler switches. The -s (turn off stack checking) is pretty obvious. Having stack checking on would increase code size and what's much worse, it would require the C runtime to be present. That's out of the question. The -g switch controls the group where the code segment will be placed. This has to be DGROUP, otherwise the linker couldn't merge the data and code segments. Fortunately Watcom tools are pretty flexible here.
The linker switches are similar to the ones used for the assembly program, although two new ones were added. The NOD option is a shorthand for NODefaultlibs and turns off default library searches (there are special records in the object files generated by the compiler). Much the same effect could be achieved using the -zl compiler switch.
But the key to success is the start option. In the assembly code we used the END directive to designate the program's entry point. There is no equivalent in C, although IBM C supports #pragma entry. Watcom C has no such pragma but allows us to specify the program entry point via the start=symbol option of WLINK.
The final version of the C code looks perhaps more complex than the
assembly version but still not too complex. Rest assured that it is the
result of many hours of intense fight with the compiler, trying to find
the right mix of ingredients that would force the compiler and linker
to
do something it rather wouldn't do. Strangely enough, the result of the
battle
isn't even very big.