Comment On OMGWTF Finalist #01: The Buggy 4-Function Calculator

This is the first article in a twelve-part series that discusses the twelve finalists and their calculator submissions for the OMGWTF Programming Contest. The entries are being presented in the order submitted, and the winner will be announced on June 18, 2007.

As Jake, Intern Boyd, and I sat around the conference table and scrolled through codefile after codefile, solution after solution, Entry #1000043 – Stephen Oberholtzer’s “Buggy 4-Function Calculator” – sucked us in. It didn’t feel like we were looking at a purposely contrived contest entry, it felt like a real, live, rotting codebase. The kind of codebase that plagues so many organizations: fragile, old, bug-ridden, and passed through the hands of several developers.

Although a handful of submissions came with a fun, fictional story (and don’t worry – I will be talking about these later and making them all available on the contest site soon), the Buggy 4-Function Calculator felt the most authentic. So far as we can tell from the code, this particular calculator started its life around 1995 because Window’s Calculator was “not an acceptable implementation.” Skeptical of floating point operations on the then-new Pentium processors, the original developer created his own 256-byte fixed point structures in order to perform mathematical operations.

The code is riddled with some familiar functions and a rather interesting approach to mathematics (if we can even call it that). But before delving into those details, I’d like to introduce you to this monstrosity’s creator.

Stephen Oberholtzer hails from King of Prussia, Pennsylvania (United States). He got his start in programming by making that little “turtle” draw pictures on the screen using LOGO and moved on to BASIC and Pascal programming shortly thereafter.

These days, Stephen writes primarily C code in his role as an Embedded Software Engineer at a small cashless payment company called Freedompay and has worked there for six and a half years. He develops for tiny devices called “Nodes” that have a whopping 512K of memory, a 2x20 display, and a RISC processor that can’t divide. Really: their compiler treats “%” and “/” as syntactical sugar that gets replaced with a call to a library function which, in turn, uses a series of bitshifts and subtractions to perform division.

This lack of division was one of Stephen’s inspirations for creating his entry. Doom (the original version for DOS) and its use of 32-bit fixed-point values also helped out. But the main concept – a decrepit application written by several incompetent developers over several years – could have only come from once place: the experience of having seen it and worked with it before. And I’m sure we’ve all been there before.

A lot of the code and problems in Buggy 4-Function Calculator resulted from the “core” solution: a Not-Invented-Here approach to floating-point math. To get around the uncertainly of where exactly the decimal point is, this following 256-bit structure is used:

typedef unsigned long long u64;
...
typedef struct {
	u64 a;
	u64 b;
	u64 c;
	u64 d;
} value_t;

One half is for numbers before the decimal point, the other is for after. As you might imagine, this makes doing simple mathematical operations quite challenging. That fact, along with a handful of incompetent coders over the years, and you've got a painful application to work with. The code is certainly worth reading through in its entirety (download link at the end), but I’ll show a few functions

static long long MakeNegative(long long x)
{
	/* find out how long to make it */
	/* BUG #42: add 2, not 1, to make room for the NUL terminator 
	 * Fixed 2001-03-24
	 */
	int len = 2 + ceil(log(x)/log(10));
	char *p = malloc(len);
	sprintf(p, "%+lld", x);
	p[0] ^= 0x06;
	return atoq(p);
}

Interestingly enough, on 2001-03-25, the day after MakeNegative was fixed, all calls to it were replaced as code from ConvertForMath (responsible for converting floats to value_t) shows:

	if (s) {
		/* Bug #9612: Customer 153 reported memory leak using MakeNegative method
		 * Fixed 2001-03-25
		 */
		int carry = 1;
		int i;
		u64 *j;
		for (i=4, j=&out->d; i>0; i--, j--) {
			// *j = MakeNegative(*j);
			*j = ~*j;
			if (carry) (*j)++;
			carry = (*j)==0;
		}
	}

Long time readers who recognized MakeNegative as a (several-time) real-world WTF, may also appreciate the implementation of IsNegative:

static int IsNegative(float arg)
{
	char*p = (char*) malloc(20);
	sprintf(p, "%f", arg);
	return p[0]=='-';
}

The pièce de résistance, however, is the DoDivision function. It was not only also inspired by a WTF posted here, but also includes commented-out code (with a TODO to uncomment it before submitting) that would otherwise cause the calculator to fail the “divide by zero” test case. Fortunately, the configuration instructions told us to uncomment this before running…

float DoDiv(float _dividend, float _divisor, int *isErr)
{
	// TODO: Uncomment this before releasing to production/submitting to contest
/*	if (_divisor == 0) {
		*isErr = 1;
		return 0;
	}
*/
	*isErr = 0;

	int negop1 = 0, negop2 = 0;
	if (IsNegative(_dividend)) {
		negop1 = 1;
		_dividend = -_dividend;
	}
	if (IsNegative(_divisor)) {
		negop2 = 1;
		_divisor = -_divisor;
	}

	value_t dividend, divisor;
	value_t quot;
	float retsign = (negop1 ^ negop2) ? -1 : 1;
	float accumfloat = 0;
	int shiftiness = 0;

	memset(&quot, 0, sizeof quot);
	ConvertForMath(_dividend, &dividend, isErr);
	if (*isErr) return 0;
	ConvertForMath(_divisor, &divisor, isErr);
	if (*isErr) return 0;

	int shiftdir = Compare(&divisor, &dividend);
	/* if they are equal the answer must be 1 or -1 */
	if (shiftdir == 0) return retsign;
	/* Prime loop */
	if (shiftdir < 0) {
		value_t divisortmp;

		memcpy(&divisortmp, &divisor, sizeof divisor);
		/* Divisor is less than dividend: shift divisor left until 
		 * dividend is less than divisor, then use the last position we had before then */
		while( Compare(&divisortmp, &dividend) <= 0) {
			shiftiness++;
			memcpy(&divisor, &divisortmp, sizeof divisor);
			ShiftLeft(&divisortmp, 1);
		}
		shiftiness--;
	} else {
		/* Divisor is greater than dividend; shift divisor right until
		 * divisor is less than or equal to dividend 
		 * we will fix this at the start of the upcoming while() loop
		 */
	}

	/* repeat until dividend is zero */
	while (Compare(&dividend, &Zero) > 0) {
		int i, carry;
		u64 *j, *k;

		/* shift divisor over until it's less than the dividend */
		while (Compare(&divisor, &dividend) > 0) {
			ShiftRight(&divisor, 1);
			if (--shiftiness < EXPONENT_D)
				/* the only place in C/C++ where a 'goto' is required:
				 * Breaking out of an outer while()
				 */
				goto escape;
		}

		ChangeBit(&quot, shiftiness, 1);
		for (i=4, carry=1, j=&dividend.d, k=&divisor.d; i>0; i--, j--, k--) {
			u64 ktmp = ~*k;
			u64 tmp = *j + ktmp + carry;
			carry = ((*j^ktmp)&HIGH_BIT) ? ((*j|ktmp)^tmp)>>63 : *j>>63;
			*j = tmp;
		}

	}
escape:
	return retsign * ConvertResult(&quot);
}

I’ll leave you with Stephen’s answer to a question I asked all finalists: would you replace calc.exe on Windows with your calculator?

Maybe, if I was about to give the computer to someone I knew (a) would need to use Calc, and (b) I really, really, really disliked.

Download Entry #100043, Buggy 4-Function Calculator (ZIP File)