written by Walter Bright
November 28, 2009
Back in the bad old DOS days, to have a large, capable application meant writing it in assembler because:
- hand written assembler was often more than twice as fast as C
- with very tight memory, the smaller the app the more room there was for data
- compilers in the early days were rather poor
Early successful apps like Lotus 1-2-3 (and of course, DOS itself) were written in assembler.
But, as things got better (especially with the arrival of protected mode) the advantages of assembler started getting outweighed by its disadvantages, i.e. the high cost of developing in it. One was faced with a choice — rewrite the app from scratch, or translate it from assembler to C. Translating had the huge advantage of one didn’t lose all the about how things need to work that gets embedded in the code.
I had the job at the time of converting a huge (and very successful) electronic schematic editor, DASH, from assembler into C. In C it could then be recompiled for 32 bits, and even ported to other platforms like the Sun workstations. The conversion took months, but was a big success.
Today, I am faced with the linker, Optlink. It was originally written in 16 bit assembler, and was also very successful. It survived the transition to 32 bits by being recoded, line by line, by its original author Steve Russell. The linker ran like lightning, and still does. No other linker remotely comes close. Every line of it is heavily optimized, and even scheduled. It’s a marvel of assembler coding skill. But it being in assembler means its stuck in the past: inflexible, unfixable, unportable. The time has come to do something about it.
It’s sort of like keeping a P-51 fighter in flying condition these days — the engineers who designed it are all gone, the manufacturer no longer makes any parts for it, the drawings are gone, and the people who built them are gone. Pretty much, you’re all on your own, figuring things out, machining any parts needed, etc. Of course, it’s all worth it because a flying P-51 is a pretty sweet machine!
I figure the best thing to do is to translate it to C, as linkers have an awful lot of in them about how things work in the real world rather than how they are documented. I estimated that relearning that lore would take a huge amount of time, and would take an unacceptable toll on the users while they struggled with outlying problems. (Although few will be called upon to convert assembler to C, converting from one language to another often comes up and many of the issues are the same.)
Why use C instead of the D programming language? Certainly, D is usable for such low level coding and, when programming at this level, there isn’t a practical difference between the two. The problem is that the system to build Optlink uses some old tools that only work with an old version of the object file format. The D compiler uses newer obj format features, the C compiler still uses the old ones. It was just easier to use the C compiler rather than modify the D one. Once the source is all in C, it will be trivial to shift it over to D and the modern tools.
After a few false starts, I remembered the lessons from converting DASH, which are:
- Convert a small slice at a time, then build and test. If it broke, you can substitute back in the old asm code, and then figure out where you went wrong as the problem area is small.
- Don’t try and redesign or fix anything during this process. It’s terribly hard sometimes to resist this urge, but it always ends up badly if you succumb. It becomes a hunk o’ junk that doesn’t work and you’ve no idea why.
- Doing it a bit at a time means you always have a working version of the app. This is fairly motivating, rather than having a long desert of nothing working and no idea if you’ve committed some obscure and fundamental error.
- While not fixing the design in the process, it is very helpful to add in comments as you figure things out, for the next guy who has to translate it from C onwards!
- Optlink did not link with any other library, not even the C standard library. So by using C, it had to be C that used nothing from the library, not even the startup code. This meant I had no printf, which turned out to be so unbearable I grabbed the printf source from the C library and hacked it up to work in Optlink (Optlink didn’t have FILE or stdout).
- The C compiler prepends _ to global identifers, so they wouldn’t match with Optlink ones. The easiest solution was to hack the C compiler to stop doing that.
- Optlink used specially named sections. Fortunately, the C compiler had a switch to name the code sections to match.
- Function calling sequence. Optlink uses about every function calling sequence imaginable, from registers to stack to even the flags register. Converting any function to C first required figuring out what its (usually undocumented) calling convention was, and what registers it used/destroyed, and recoding it to use the C convention.
- It was usually easiest to use local variable names with the same name as the register they replace. So the conversion has a lot of locals with names like EAX, ESI, etc. This makes it easy to compare the two sets of sources. Once the C version is verified, more useful names can be used.
- Gotos. Of course, assembler has no structured statements. Functions are a rat’s nest of goto’s. The easy way is just leave the goto’s intact in the C source. After it all works, then see about replacing them with structured control flow.
- Accurately typing variables. In particular, C will helpfully multiply the offset to a pointer by the size of the type pointed to. In asm, this is done manually. So one has to figure out the type pointed to, divide the offset by that value, and put that in the C source. This is very easy to get wrong, so I like to verify by compiling then disassembling and comparing the instructions. That’s easier than debugging random crashes.
- Macros and conditional assembly. It’s been a looong time since I’ve used MASM, and how that all works has gone out of my head. It’s easier to cut through the chaff and just disassemble the output of the assembler to see what the real instructions are. This also helps to verify that you’ve got the offsets of struct members the same as in the assembler.
- Optlink has no unit tests. Writing them would require understanding what the various functions do, and I won’t know precisely what they are supposed to do until most of the program is converted.
Once it is all in C, then the old build system can be scrapped, the special compiler switches and hacks removed, it can be hooked up to the C standard library, and then built as a real C app.
Then, it can be easily converted to a D app and the possibilities are unlimited.
Most people would consider this an exercise in self-flagellation, but I enjoy doing it.
I don’t know yet how this is all going to work out, as I am only part way through the process. It’ll take a long time. But I’m looking forward to freeing Optlink from its heritage so it will be useful for another 10 years.
Early results, though, are the C source code is about 30% smaller than the corresponding ASM code, and the C object code is about 30% larger than the ASM object code. That’s in line with historical experience I’ve had working with C and assembler.
The difference in object code size is primarily due to the assembler having done register assignments that cross over multiple function calls. There’s just a lot less pushing and popping of parameters. There are also a lot of functions with multiple entry points. I don’t know of any current compiler that is able to enregister across a flow graph of function calls, or is able to tail merge multiple functions.
Although I have not run any speed tests, I expect the performance of the non-I/O bound code to be about 30% slower. Since a linker tends to be I/O bound, the actual performance loss probably will be about 10%, which I can live with.
Thanks to David Held and Bartosz Milewski for reviewing this.