DTACK Revisited

Once upon a time, before 747s were invented and the world's population headed north of five billion, people got along with just one name. After all, everybody was born, lived, and died without ever leaving their village. Everybody knew Tom, Dick, and Harry.

Then Europeans got an itch for tourism. With the English leading the way, everybody got to choose a second name whether they wanted one or not. They were given the choice of colors or occupations: Blue, Cooper, Fletcher. MacLaren means "son of Laren." Place names became a favorite, especially as the practice migrated to the continent.

My name means "Mt. Harden" in German. It's spelled the same way as Charles Lindbergh (you may have heard of Charlie and his solo Atlantic flight). But the guardians at the gates of Ellis Island during the big European wave of immigration translated foreign names into English freely; "bergh" also is "berg." "Burg" or "burgh" is German for castle or fort. The Pennsylvania cities of Harrisburg and Pittsburgh grew up around forts.

I've long been resigned to having my name routinely misspelled. When I first wrote this column (Dr. Dobb's Sourcebook, March/April 1995), it was misspelled in the table of contents and on my first check.

In the editing of Michael Abrash's book ZEN of Graphics Programming, this was raised to an art form. My name first appears on page 1 of chapter 17, where it's misspelled twice, differently. On the first page of chapter 18, my name is again spelled two ways, once correctly. But the book publisher qualified for international competition by misspelling my name twice, differently, in the same caption: Table 18.1 "Hardenburg Circles versus Optimized Hardenburgh Circles." Sigh.

My name isn't the only thing the book publisher had problems with; in the index under "Circles" we find "Hardenburgh's circle algorighm" (sic).

By now you may be wondering what a hardware guy's name (or variations thereupon) is doing in a book that has "Programming" in the title. Well, check my bio on the bottom of this page. I once developed a full-blown 68000-based, incrementally compiled Basic for the Atari ST, a project that required several years and some help from others. The language, called "DBASIC," worked fine but only sold 72 copies (unknown to me at the time, Atari was shipping all its STs to Germany where a third-party BASIC by GFA did emerge).

Now you know why I call myself a hardware person. I've actually made some money from time to time on hardware.

DBASIC needed a command to draw a circle. When I checked out published algorithms, the only ones I could find used either a multiply or, in one case, a divide (!) inside the main loop. So I devised my own algorithm. After calculating a couple of squared terms, the main loop just used integer adds and subtracts. After DBASIC had already flopped, I devised a similar algorithm for ellipses. All these were in 68000 assembly for the ST.

This brings us to 1989, when both Michael Abrash and I were writing for the late bimonthly Programmer's Journal. When I learned that Michael lived only a few miles from me, I arranged a meeting. I presented my algorithms and suggested that we collaborate on an article. You see, I didn't (then) know how to program using x86 assembly or VGA cards and those subjects were Michael's specialty.

Michael agreed the algorithms should be published but envisioned several articles, a lot more work than I had planned. We agreed that Michael should write the articles alone, mentioning me as the source of the algorithms. Chapters 17o 19 of ZEN originally appeared as articles in the first three 1990 issues of PJ.

I'm resurrecting this old story for two reasons, both of which are related to Michael's column in the previous issue (Dr. Dobb's Sourcebook, January/February 1996) of this magazine. Reason one is that in his last three paragraphs Michael describes how sharing benefits the larger community. Hey, I believe in that stuff too. Reason two is that the folk at id Software, Michael's employer, may not be using the optimum method of developing software.

Having turned over my circle-drawing algorithm, which was the fastest I had ever seen, I soon got a call from Michael. "Hal, you don't need to square those terms. Your 'finite difference' algorithm works just fine using the unsquared values if you make this one small change...." Michael was right, and his simplification enabled the use of 16-bit, rather than 32-bit integers. (See ZEN, page 1 of chapter 19.)

As Michael has pointed out, it's just about impossible for any one person to devise an algorithm that somebody else can't improve. I already knew that. In fact, I had deliberately depended on that in optimizing the inner kernel of the commercially failed language DBASIC.

A language that's slow performing a fundamental integer operation such as C%=A%+B% is destined to be slow, period. I wanted DBASIC to be a fast, incrementally compiled language. Back in 1985, I posted the code then used to execute C%=A%+B% in DBASIC on the company bulletin board, along with the number of 68000 clocks needed.

By the next day another programmer, James Shaker, had replaced the code sequence with a modified form that ran in fewer clocks. I looked at the change, decided it could be improved, and posted a third version that same day. Within a week, the code had been sped up by a factor of 5 (!) and we had arrived at the final form of the innermost kernel of DBASIC. Nobody had ever put his name on any of those sheets of paper.

According to Michael's column, id Software had a performance problem in an innermost kernel of their new game, Quake. Hidden surface removal was proving too slow when there were lots of surfaces. id's honcho, John Carmack, solved the problem by parking his 1200-HP Ferrari and pulling an all-weekender. This is great if you have a John Carmack around and he doesn't mind losing sleep.

But for the ordinary mortals who constitute most programming teams, a good way to solve really tough, important problems is to use egoless programming. Post the problem and its current implementation and performance on the bulletin board. Don't sign the posting. Unless the other team members are being micromanaged, this is an irresistible challenge.

Egoless programming isn't an available option for persons who believe they're much more competent and innovative than their associates. If that belief is correct, great! But for the rest of us...

(This is not intended to knock John Carmack, who seems to be a pretty good programmer and who, as the boss, generously allowed Michael to share some of the innermost details of Quake with us.)

Try this technique at work. Without revealing any proprietary details, please let me and/or Dr. Dobb's know how it worked.

Sharing software is obviously beneficial to the larger community. How about sharing hardware information? Well, I did some of that way back in '81 and '83.

In 1979, when Motorola's 68000 microprocessor was approaching completion, there was a fierce fight within Big M. The chip makers in Austin wanted to sell the 68K to all comers. But Big M's computer and semiconductor division headquarters were located in Phoenix, where there also was a computer systems group. The systems group wanted to limit the 68K's use to high-end minicomputers. The chip boys had to make their case in memos via snail mail, while the systems folk lobbied over three-martini lunches. Guess who won?

So it became Big M's official but unannounced policy to keep the 68000 out of the personal computer marketplace. This was accomplished in two ways: Application engineers were forbidden to provide any assistance whatsoever to personal computer types. And the Ap Notes for the 68K exclusively described incredibly complex systems.

My small company bought the first two 68000s to be sold across Hamilton Electro Sales' counter, in November 1980. For six months I tried to get information about how to use the 68K in a simple, PC-related application. I didn't understand why the application engineers literally would not talk to me.

Then I got mad. I carefully read the data sheet, and discovered that if pin 10, DTACK, was grounded, then the 68000 became a nice tame device that could be designed into extremely simple systems just like the 6502 that I'd been working with up to then. Since nobody else in the PC world seemed to have access to that info, I started the newsletter DTACK Grounded in July 1981. The first issue explained exactly how to design the 68000 into a simple system. I was sharing my information.

By November, I had registered the fictitious name DTACK Grounded and was selling 68000-based attached processors for the Pet and Apple II. The Apple II version became a profitable product, and I wound up publishing 45 mostly monthly issues--1000 pages--of the newsletter.

When I began the DTACK effort in 1981, the 68000 was by far the fastest available microprocessor. Intel's Pentium runs integer stuff over 200 times faster now than the 68K did then. FP performance? Don't ask...

It was obvious from the first that while the 68000 was a really fast integer processor, it needed an FP math accelerator like the Intel 8087. Big M had in fact announced that it would ship such a part for the 68K in 1982, but it was vaporware until mid-1985.

Meanwhile, National Semiconductor developed a line of 68K-like processors, the 32000 series. NS used separate teams to develop the integer CPU and the FPU chips. The CPUs remained heavily bug-ridden for a long time. But when the 16032 FPU appeared in mid-1983, it worked.

Having learned from my original 68K experience, I carefully studied the 16032 data sheet and decided the FPU would (unlike Intel's 8087) easily interface with the 68K. So my little company built up a test jig using 3M's neat prototyping kit and guess what--it worked. But, unlike what the 16032 data sheet said, the FPU had to be run using a synchronous clock.

I published all this information in newsletter #24 (October 24, 1983), including a photograph of the prototype board. I contacted Stan Baker about this, and Stan's popular hardware column in Electronic Engineering Times reported that the 68K and the National Semi FP chip were compatible and a lot faster than Intel's x86 + 8087 combo. My next newsletter carried a photo and complete schematic of our second, simplified prototype. Soon we were selling production boards, one of which accepted up to three 16032s.

I thought Big M would be happy; FP support for the 68K now was readily available. Wrong. Big M folk were furious with me; they wanted everybody to wait for their 68881 to arrive. I thought National Semi would be happy because here was another market for its FP chip. Wrong. National Semi's minions were peeved because they didn't want its FPU used to support 68K-based systems. Intel was understandably unhappy. For a while there I screened my mail for letter bombs.

(National Semi told everybody that I didn't know what I was talking about; the 16032 was too an asynchronous part. Five months later, the data sheet was quietly changed to require synchronous operation. Tsk.)

In my column in the September/October Dr. Dobb's Sourcebook, I shared more hardware info: why CPU clock pushing was a really good idea, especially for Intel's Pentium/75. I suspected the column would not be joyously embraced by Intel.

On December 12, 1995, an article appeared in my local newspaper's (the San Jose Mercury News) "Business" section about Intel modifying its Pentium design. It seems that after Intel decides a CPU's designated clock, it can be programmed internally to limit its speed. Some partial quotes:

..."overspeed protection" prevents criminals and others from winding up a 75 MHz Pentium, for example.

Some unsavory folks knew it was hard to physically tell the faster chips from the slower ones.

The "overclocked" chip would initially test OK. But it probably would burn out and stop working in a short time. [This assertion is "factually challenged" -- HWH]

...the [clock-pushing] practice has been around for years and was cause for concern among law enforcement officials.

Hmm. I wonder just how that circuitry works. The easiest method would limit the phase-lock loop clock multiple. But the P75, P90, and P100s all use a 1.5x multiple, which still would allow P75s to be pushed to 100 MHz. And I wonder when Intel's gonna start shipping them new chips that foil us criminals? The P75s currently on the market assuredly do not have that circuitry activated, if it's present at all.

My Dr. Dobb's editor helpfully pointed out that I could use the jail pay phone to verbally deliver my next Sourcebook column (not to mention that he would spring for a collect call). Yet another reason why sharing hardware info with the larger community sometimes ain't such a good idea.

The Push     Tries  Success  Ratio

P75 -> P90     31     31     100%

P75 -> P100    21     18      86%

P75 -> P120     9      7      78%

P75 -> P133     3      1      33%

P133 -> P180    4      3      75%