May 94 Challenge
Volume Number: 10
Issue Number: 5
Column Tag: Programmers’ Challenge
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.
FLIP HORIZONTAL
This month’s challenge is to implement the Flip Horizontal menu item that you
find in most imaging applications. Your code will flip a given pixMap from right to left.
On exit from your routine the pixMap should be a horizontal mirror reflection of what
it was on input.
The prototype of the function you write is:
codeexamplestart
/* 1 */
void FlipPixMapHorz(thePixMapHndl)
PixMapHandle thePixMapHndl;
codeexampleend
You flip the pixMap pixels in place. That is, you overwrite the input pixels with
the output pixels as you go. Your routine needs to handle all of the possible pixMap
types, including a 1-bit deep bitMap and indexed types with less than 8 bits per index.
When timing solutions, equal weight will be given to each case: 1, 2, 4, 8, 16 and 32
bits per pixel.
TWO MONTHS AGO WINNER
I am happy to announce that we now have an undisputed Programmer Challenge
Champion! This month marks the 3rd time this person has come in 1st place (breaking
a 3-way tie). He has also finished in the top 5 places more often than any other
Challenge entrant (8 times, including this one). Congrats to Bob Boonstra (Westford,
MA) for his excellent solution to the Bitmap To Text challenge! His solution is about
2.6x faster than the only other entry this month, submitted by Challenge veteran Allen
Stenger (Gardena, CA).
Here are the code sizes and times for two different tests. 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 Code Time 1 Time 2
Bob Boonstra (7) 1264 4 13
Allen Stenger (4) 766 11 34
Both Bob and Allen chose to use similar algorithms. They split the bitmap into
character-sized cells and then tried to find a character from the given font that had a
similar density. As a measure of density they both counted the number of set bits in the
cell. Thus, the performance of the routine as a whole was largely dependent on how fast
their bitcount code was. Bob ended up using a faster bitcount, which looks something
like this:
/* 2 */
bitCount = 0;
if ((x = initVal) != 0) {
do {
bitCount++;
x = x & (x - 1);
} while (x != 0);
}
where initVal is the value that you’re trying to count the set bits for. This code
has the advantage that it does zero iterations of the loop if initVal is zero. Also, it only
makes one iteration through the loop for each set bit.
Allen used a 256 element lookup table where each entry in the table contained a
number from 0 to 8 representing the number of set bits of the index corresponding to
that entry. For instance, zero-based element number 7 contained the number 3
because there are 3 set bits when you write 7 as a base 2 number, 00000111. This
table lookup method is a good idea if you want to count bits in a long run of bytes but
for small bit fields that are not necessarily byte aligned there is too much masking and
other loop overhead.
Here’s Bob’s winning solution:
March 94 Challenge - BitMapToText
by Bob Boonstra
Strategy
The problem states that “the smallest detail in the input image [will] be roughly
equal to or larger than a single character of the given font and font size.” Therefore,
this solution attempts only to match the number of bits set in a given character size
piece of the image with the number of bits set in the character chosen to represent that
piece of the image.
The strategy is to:
(1) draw the characters from 32 to 127 in an offscreen bitmap.
(2) sort the characters in order of increasing number of bits set
(3) precalculate a mapping from pixel density to output characters
(4) loop thru the character size chunks of the image, count the number of bits
set, and output the corresponding character.
Assumptions
• Width of characters is assumed to be <=32 pixels (reasonable for (6-24 point
mono font)
• No assumption that actual height of font <= 24; ascent+descent+leading may
exceed point size
• Ref NIM: Text pg 4-11
bitMapPtr->rowBytes * (font height) assumed < 32K
/* 3 */
#include
#pragma options (honor_register, !assign_registers)
#define uchar unsigned char
#define ushort unsigned short
#define ulong unsigned long
#define EOL 0x0d
#define kErr 1
#define kFirstChar 32
#define kLastCharPlus1 128
#define kNumChars (kLastCharPlus1-kFirstChar)
#define kBytesPerBMChar sizeof(long)
#define kMaxCharWidth (8*kBytesPerBMChar)
#define kCharRowBytes 384
#define kBitsPerChunk 32
#define kMaxCharVals 512
#define DoSetMem(addr,sz,val)
{ register long *p = (long *)addr;
register short count = sz;
do *p++=val; while (--count);
}
/*
Macro BitCount(x,count) increments count for each bit in x set to 1.
WARNING: the expression (x=x--&x) in the BitCount macro is not
portable, because the order of evaluation is undefined, but it
generates correct fast code for (x=x&(x-1)) in THINK C. Non-portable
code is BAD FOR YOU, except where speed is very important, like in
this Challenge.
*/
#define BitCount(x,initVal,count)
if (x=initVal) do ++count; while (x = x--&x);
ushort lineHeight,charWid;
FontInfo fInfo;
short InitOffscreenBitMap(GrafPort *charPtr)
{
//
// Initialize font information
//
Point scalePt = {1,1};
ulong numBytes;
GetFontInfo(&fInfo);
lineHeight = fInfo.leading+fInfo.ascent+fInfo.descent;
charPtr->pnLoc.v = lineHeight -fInfo.descent;
//
// Initialize GrafPort and bitmap storage
//
numBytes = lineHeight*kCharRowBytes;
if (0 == (charPtr->portBits.baseAddr =
(QDPtr)NewPtr( numBytes )))
return kErr;
DoSetMem(charPtr->portBits.baseAddr,
numBytes/sizeof(long),0);
charPtr->portBits.rowBytes = kCharRowBytes;
charPtr->portBits.bounds.top = 0;
charPtr->portBits.bounds.left = 0;
charPtr->portBits.bounds.bottom = lineHeight;
charPtr->portBits.bounds.right = kCharRowBytes*8;
RectRgn(charPtr->visRgn,&charPtr->portBits.bounds);
charWid = StdTxMeas(1,"W",&scalePt,&scalePt,&fInfo);
/*if (charWid != fInfo.widMax) DebugStr("\p bad wid");*/
if (kBytesPerBMChar*8 < charWid) return kErr;