Mar 94 Challenge
Volume Number: 10
Issue Number: 3
Column Tag: Programmers’ Challenge
Related Info: Color Quickdraw
Programmers’ Challenge 
By Mike Scanlin, MacTech Magazine Regular Contributing Author
Note: Source code files accompanying article are located on MacTech CD-ROM orsource code disks.
The rules
Here’s how it works: Each month there will be a different programming challenge
presented here. First, you must write some code that solves the challenge. Second, you
must optimize your code (a lot). Then, submit your solution to MacTech Magazine
(formerly MacTutor). A winner will be chosen based on code correctness, speed, size
and elegance (in that order of importance) as well as the postmark of the answer. In
the event of multiple equally desirable solutions, one winner will be chosen at random
(with honorable mention, but no prize, given to the runners up). The prize for the
best solution each month is $50 and a limited edition “The Winner! MacTech Magazine
Programming Challenge” T-shirt (not to be found in stores).
In order to make fair comparisons between solutions, all solutions must be in
ANSI compatible C (i.e., don’t use Think’s Object extensions). Only pure C code can be
used. Any entries with any assembly in them will be disqualified (except for those
challenges specifically stated to be in assembly). However, you may call any routine
in the Macintosh toolbox you want (i.e., it doesn’t matter if you use NewPtr instead of
malloc). All entries will be tested with the FPU and 68020 flags turned off in THINK C.
When timing routines, the latest version of THINK C will be used (with ANSI Settings
plus “Honor ‘register’ first” and “Use Global Optimizer” turned on) so beware if you
optimize for a different C compiler. All code should be limited to 60 characters wide.
This will aid us in dealing with e-mail gateways and page layout.
The solution and winners for this month’s Programmers’ Challenge will be
published in the issue two months later. All submissions must be received by the 10th
day of the month printed on the front of this issue.
All solutions should be marked “Attn: Programmers’ Challenge Solution” and
sent to Xplain Corporation (the publishers of MacTech Magazine) via “snail mail” or
preferably, e-mail - AppleLink: MT.PROGCHAL, Internet: progchallenge@xplain.com,
CompuServe: 71552,174 and America Online: MT PRGCHAL. If you send via snail
mail, please include a disk with the solution and all related files (including contact
information). See page 2 for information on “How to Contact Xplain Corporation.”
MacTech Magazine reserves the right to publish any solution entered in the
Programming Challenge of the Month and all entries are the property of MacTech
Magazine upon submission. The submission falls under all the same conventions of an
article submission.
BITMAP TO TEXT
Have you ever seen one of those text files where if you print it out, tack it on a
wall and step back it looks like a graphic? I’ve seen dragons, islands, Star Trek
images, etc. done this way. This month’s challenge is to write the routine that converts
a bitmap into a text equivalent.
The prototype of the function you write is:
/* 1 */
short BitMapToText(bitMapPtr, fontName,
fontSize, outputFile)
BitMap *bitMapPtr;
Str255 fontName;
unsigned short fontSize;
FILE *outputFile;
BitMapPtr points to the input bits. The max size is 1000 pixels square. fontname
is the name of the monospaced font to use (Monaco, Courier, for example) and fontSize
is the size of that font that should be used (6pt to 24pt). outputFile is a standard C
output stream that you should write your text output to, each line separated by a 0x0D
byte. The return value of the function is an error code: zero if nothing went wrong or
non-zero if an error occurred. Do not close outputFile when you are finished.
Your basic strategy will be to split the bitMap into character size pieces and then
find the best character match for each piece. You should only use the printable ASCII
characters (charCodes from 32 to 127, inclusive). The closeness-of-match algorithm
is not given. It’s up to you to pick something that works reasonably well and doesn’t
take 50 years to compute. This contest will be judged primarily on speed but routines
that produce unrecognizable output will be disqualified (no matter how fast they are).
Recognizability will be judged on the screen, at 72dpi.
Note that in order to have recognizable output the size of the smallest detail in the
input image needs to be roughly equal to or larger than a single character of the given
font and font size. This will be true for the test images I use (so don’t stress too much
over the problem of how to represent a very small image using only 24pt glyphs).
TWO MONTHS AGO WINNER
Of the eight entries I received for the Connect The Dots challenge, six worked
correctly. Bill Karsh (Chicago, IL) joins the ranks of Challenge superstars for coming
in first place for the second time. Bill previously won the Who Plays Who challenge
and is now tied in a 4-way tie for the most number of Challenge wins. Bill’s line
drawing routine is about 3x faster than Color QuickDraw for long lines and about 30x
faster for very short lines (for the special cases given in the challenge: no clipping,
pen size (1, 1), patCopy, no bitMaps). If you have intensive line-drawing routines in
your code you ought to consider casing out those cases that Bill’s code handles and using
it instead of many calls to Line or LineTo.
Here are the code sizes and average times (for medium to long line-length tests)
of each entry. Numbers in parens after a person’s name indicate how many times that
person has finished in the top 5 places of all previous Programmer Challenges, not
including this one:
Name Time Code
Bill Karsh (2) 1114 1314
Kevin Cutts (2) 1370 1802
Bob Boonstra (5) 1434 750
Allen Stenger (2) 1623 1664
John Heaney 1711 710
Stefan Pantke 2500 876
Color Quickdraw 3219 ?
There were three cases that had to be dealt with: 8-bit, 16-bit and 32-bit deep
pixMaps. Once the appropriate pixel value to stuff has been figured out, all three cases
are the same (as far as determining which pixels are part of the line). Bill solved this
redundant code problem by having the guts of each case #included in three different
places. This makes it easy to update the line generating code for all three cases at the
same time. And as did nearly everyone else, Bill handles the common cases of
horizontal and vertical lines separately (which is a big win for those cases).
For the 8-bit case he uses his own RGB2Index routine instead of the ROM’s
Color2Index, which would be fine if his routine worked all the time, but it doesn’t. It
only works if the RGB value you’re trying to convert is an exact match with one of the
index values. However, the main point of this challenge was about drawing lines fast,
not inverse color table lookups.
Kevin Cutts (Schaumburg, IL) and Bob Boonstra (Westford, MA) deserve a
mention here because in some of the very short line cases their code was faster than
Bill’s. But I think the average line drawn by QuickDraw is longer than a few pixels and
Bill’s code is faster for those cases so he wins.
I’d also like to apologize to Alan Hughes (Ames, IA) for the mixup last month that
caused his on-time and correct entry to the Present Packing Challenge to get to me
after I had sent in the column. His 94.2 average puts him in 3rd place and knocks Dave
Darrah out of the top 5.
As readers of this column know, I have been stressing 680x0 optimizations in
this column for over a year (and C code that generates better 680x0 code in Think C).
Now that the PowerPC is coming out I am faced with a choice: Which platform should I
run the challenge on, 680x0 or 601? Obviously, if there is a switch to 601 it would
not happen for at least a couple of months after they are made generally available. But
are readers interested in 601 tricks or should we stick to the installed base of 680x0s
for many more months? And if and when we switch to the 601, what PPC compiler
should I use to test challenge entries? Send me e-mail at the progchal addresses in the
front of the magazine and let me know what you think. Thanks.
Here’s Bill’s winning solution:
ConnectTheDots