Jun 93 Challenge
 Volume Number: 9 Issue Number: 6 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 or source code disks.

## WHERE IN THE WORLD?

This month’s Challenge is a real world problem previously solved without reals by real MacTech reader Allen Stenger (Gardena, CA): You are given a large array of unique city names in alphabetical order ending with a sentinel of ‘ZZZ’ and a single city name to find in this array. You are to return the index of the desired city, or if it doesn’t match exactly, a list of the five closest matches. If there are more than five closest ones, return any five of them. The closeness-of-match algorithm, for purposes of this challenge, is “differing in the fewest positions from the desired name.” Take the longest of the two strings you’re comparing and each time a position doesn’t match (or is beyond the end of the shorter string) add 1 to your difference count; the smallest difference count is considered closest.

The input city list is an array of Str255s (pascal strings) in one big block where there will be, say, 200 to 1000 unique city names (in alphabetical order, all uppercase, with the ‘ZZZ’ sentinel as the last element). The city you are to find is the uppercase string pointed to by cityToFindNamePtr. The prototype of the function you write is:

```Boolean FindCity(cityNames,
cityToFindNamePtr, closestMatches)
Str255  cityNames[];
Str255  *cityToFindNamePtr;
unsigned short   closestMatches[];
```

If there is an exact match, return TRUE and set closestMatches[0] equal to the zero-based index of the match. If there is not an exact match, return FALSE and set closestMatches[0..4] to the five closest matches (in order of closeness, or, if they are equally close, in any order).

Allen says that this problem came up while working on the American Airlines reservation system, SABRE, a long time ago. He says that his tests then showed that city names were misspelled about 1/3rd of the time due to either poor spelling or typing by the reservation agents (no offense intended). You can use that information in your solution if you like; I will be simulating it with test data (exact matches will occur only 33% of the time I call your routine from my test bench).

## TWO MONTHS AGO WINNER

Congratulations to Steve Israelson (Vancouver, B.C.) for winning the “Rotated Bits” challenge. Right on his heels is Andy Scheck (location unknown) with an entry that was half as many bytes but which was just a little too slow in some cases to win. Jeff Mallett (Hickory, NC) deserves praise for his extremely small solution which was also near the top in terms of speed. Because it is so small, it is listed here as well, after Steve’s winning solution.

There were 16 entries to this challenge. Two of them were disqualified immediately because they were in assembly (nice try) and six others were disqualified for giving incorrect results (try testing with a 9x17 bitmap). Many people e-mailed me and asked if they could assume that rowBytes was divisible by four. The answer is: no. However, you could always case out on that case early on in your routine and then call one of two rotate functions based on if (rowBytes % 4 == 0) or not. Just so long as your solution has one entry point you can do whatever you like inside.

Here’s a summary of the eight entries that gave correct results. The bytes column is the code size, test 1 is the ticks to rotate 4000 small bitmaps (20x30 and smaller) and test 2 is the ticks to rotate 400 medium size bitmaps (300x400 pixels, approx). In all cases, the bitmaps were filled with the same random data before rotating:

Name bytes test 1 test 2

Steve Israelson 740 72 638

Andy Scheck 386 75 778

Jeff Mallett 194 91 936

Patrick Breen 668 125 902

Stepan Riha 656 122 1186

Dave Darrah 362 138 1453

Jan Bruyndonckx 490 205 1785

Dominic Mazzoni 244 630 6687

Steve’s winning solution is reasonably commented so I won’t go into detail here describing how it works. I will, however, offer some peephole optimizations to make it even better.

The first thing that the optimized eye notices about his code is that he multiplies, divides and mods by 8. It’s a dangerous assumption to make that the compiler will be smart and substitute shifts and ands where it can. I always prefer to make them explicit. Thus, I would change these lines:

``` srcRowX8 = srcRowBytes * 8;
srcData = const1 + srcX / 8;
if (remainder = (srcWidth % 8))
```

to these:

``` srcRowX8 = srcRowBytes << 3;
srcData = const1 + (srcX >> 3);
if (remainder = (srcWidth & (8 - 1)))
```

In addition to those, there is one point in his code where he multiplies by 7. He’d be better off by multiplying by 8 (using a shift) and then subtracting one. This:

``` src += srcOffset * 7;
is faster as:

src += srcOffset << 3;
src -= srcOffset;

```

After I made these changes and then ran test 2, the time went from 638 ticks to 542 ticks (it reduced the code size by 18 bytes, too).

Here’s Steve’s winning solution, followed by Jeff’s tiny solution:

```/*-------------------------------------------------
Steve Israelson
Motion Works Corp.
-------------------------------------------------*/
void RotateBitMapClockwise(BitMap *, BitMap *);
void rotateBlock(unsigned long *,unsigned char *,
long,unsigned char *,long);
void rotateLimitedBlock(unsigned long *,
unsigned char *, long,unsigned char *,long,
short);

/*-------------------------------------------------
Rotate the bitmap from src to dst by +90 degrees.  Make
a table for use in the rotate block routine.  Step through
the src in 8x8 blocks, starting from the bottom left.  Step
through dst in 8x8 blocks,  starting from the top left.
Handle the right edge of the bitmap specially to prevent bits
from being rotated into memory outside of the destination.

-------------------------------------------------*/
void RotateBitMapClockwise(BitMap *src, BitMap *dst)
{
unsigned long table[16] =
{0x00000000, 0x00000001, 0x00000100, 0x00000101,
0x00010000, 0x00010001, 0x00010100, 0x00010101,
0x01000000, 0x01000001, 0x01000100, 0x01000101,
0x01010000, 0x01010001, 0x01010100, 0x01010101};
/* x,y co-ord of source block */
register short  srcX, srcY;
/* row bytes, dereferenced for speed */
short  srcRowBytes, dstRowBytes;
/* src rowbytes * 8, for speed */
short  srcRowX8;
/* width and height of src */
short  srcWidth, srcHeight;
/* pointer to src and dst 8x8 blocks */
char   *srcData, *dstData;
/* pointer to bitmaps de-referenced for speed */
/* last few pixels to do specially */
short  remainder;
/* a constant, pre-calculated for speed */
char   *const1;

/* de-reference some constants */
srcRowBytes = src->rowBytes;
dstRowBytes = dst->rowBytes;

/* calculate some values */
srcWidth = src->bounds.right - src->bounds.left;
srcHeight = src->bounds.bottom - src->bounds.top;

srcRowX8 = srcRowBytes * 8;
const1 = srcAddr + (srcHeight - 8) * srcRowBytes;

/* loop through the source doing vertical
* slices starting at the left */
for (srcX = 0; srcX < srcWidth - 7; srcX += 8) {
/* bottom edge */
srcData = const1 + srcX / 8;
/* left edge */
dstData = dstAddr + srcX * dstRowBytes;
for (srcY = srcHeight - 1; srcY >= 0;
srcY -= 8 ) {
rotateBlock(table, (unsigned char *)srcData,
srcRowBytes, (unsigned char *)dstData,
dstRowBytes);
srcData -= srcRowX8; /* next vert block */
++dstData; /* next horiz block */
}
}

/* handle the last partial row by calling
* rotateLimitedBlock() */
if (remainder = (srcWidth % 8)) {
/* bottom edge */
srcData = const1 + srcX / 8;
/* left edge */
dstData = dstAddr + srcX * dstRowBytes;
for (srcY = srcHeight - 1; srcY >= 0;
srcY -= 8 ) {
rotateLimitedBlock(table,
(unsigned char *)srcData, srcRowBytes,
(unsigned char *)dstData, dstRowBytes,
remainder);
srcData -= srcRowX8;
++dstData;
}
}
}

/*-------------------------------------------------
Rotate an 8x8 block of pixels by treating the destination
block as 2 unsigned longs (64 bits!) and using a lookup
table to get a mask for the value of each row in the src
block.  The table essentially stretches out the source byte
to 8 times its size and then ORs it into the destination
64bits.  Since the bits are in the low bit of each byte,
the destination has to be shifted one position to the left
before each OR operation. The offset values are the
difference to rowBytes. If we had a 64bit data type, this
would be easier.
-------------------------------------------------*/
void rotateBlock(unsigned long *table,
unsigned char *src, long srcOffset,
unsigned char *dst, long dstOffset)
{
register unsigned long   resultLO, resultHi;
short  x;

resultLO = resultHi = 0;
src += srcOffset * 7;
/* compute the rotated result */
for (x = 0; x < 8; ++x) {
resultLO = resultLO << 1;
resultHi = resultHi << 1;
resultLO |= table[(*src) >> 4];
resultHi |= table[(*src) & 0x0F];
src -= srcOffset;
}

/* store the rotated result */
*dst = (resultLO & 0xFF000000) >> 24;
dst += dstOffset;
*dst = (resultLO & 0x00FF0000) >> 16;
dst += dstOffset;
*dst = (resultLO & 0x0000FF00) >> 8;
dst += dstOffset;
*dst = resultLO & 0x000000FF;
dst += dstOffset;
*dst = (resultHi & 0xFF000000) >> 24;
dst += dstOffset;
*dst = (resultHi & 0x00FF0000) >> 16;
dst += dstOffset;
*dst = (resultHi & 0x0000FF00) >> 8;
dst += dstOffset;
*dst = resultHi & 0x000000FF;
}

/*-------------------------------------------------
Same as other rotateBlock, except will do a
partial block. Useful to prevent the overwriting
of memory outside the bitmap!
-------------------------------------------------*/
void rotateLimitedBlock(unsigned long *table,
unsigned char *src, long srcOffset,
unsigned char *dst, long dstOffset, short lines)
{
register unsigned long   resultLO, resultHi;
short  x;

resultLO = resultHi = 0;
src += srcOffset * 7;
for (x = 0; x < 8; ++x) {
resultLO = resultLO << 1;
resultHi = resultHi << 1;
resultLO |= table[(*src) >> 4];
resultHi |= table[(*src) & 0x0F];
src -= srcOffset;
}
*dst = (resultLO & 0xFF000000) >> 24;
dst += dstOffset; if (lines == 1) return;
*dst = (resultLO & 0x00FF0000) >> 16;
dst += dstOffset; if (lines == 2) return;
*dst = (resultLO & 0x0000FF00) >> 8;
dst += dstOffset; if (lines == 3) return;
*dst = resultLO & 0x000000FF;
dst += dstOffset; if (lines == 4) return;
*dst = (resultHi & 0xFF000000) >> 24;
dst += dstOffset; if (lines == 5) return;
*dst = (resultHi & 0x00FF0000) >> 16;
dst += dstOffset; if (lines == 6) return;
*dst = (resultHi & 0x0000FF00) >> 8;
dst += dstOffset; if (lines == 7) return;
*dst = resultHi & 0x000000FF;
}

//*********************************************************
// RotateBitMapClockwise
// By Jeff Mallett
//
// Rotates the significant bits of the srcBitMapPtr 90°
// clockwise and stores the result in dstBitMapPtr.
//*********************************************************

#define kHighShortBit0x8000
#define kBitsPerShort16

// Creates a short from bits in different rows of
// the source bitmap.  Then copies this short into
// the destination bitmap.
#define COPY_TWO_BYTES(stopValue)  \
data = 0, bit = kHighShortBit;    \
do {   \
if (*srcPos & srcBit) data |= bit;\
srcPos += srcRowShorts;  \
} while ( (bit >>= 1) != stopValue ); \
*(dstPos++) = data

void RotateBitMapClockwise(BitMap *srcBitMapPtr,
BitMap *dstBitMapPtr)
{
register unsigned short data, *srcPos, bit;
register int j;
register unsigned short srcBit, *dstPos, stopBit;
register int i;
unsigned short *baseSrcPtr;
// shorts per row of source
const int srcRowShorts =
srcBitMapPtr->rowBytes >> 1;
const int numSrcRows =
srcBitMapPtr->bounds.bottom - srcBitMapPtr->bounds.top;

srcPos = baseSrcPtr =
srcBit = kHighShortBit;

for (i = srcBitMapPtr->bounds.right -
srcBitMapPtr->bounds.left; i; --i) {
// Copy one column of source to a row of destination
for (j = numSrcRows / kBitsPerShort; j; --j) {
COPY_TWO_BYTES(0);
}
if (j = numSrcRows % kBitsPerShort) {
stopBit = kHighShortBit >> j;
COPY_TWO_BYTES(stopBit); // Final 2 bytes
}
// Prepare to copy next column of source
if ( !(srcBit >>= 1) ) {
srcBit = kHighShortBit;
++baseSrcPtr;
}
srcPos = baseSrcPtr;
}
}
```

## 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. 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, and CompuServe: 71552,174. 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.

Community Search:
MacTech Search:

## Latest Forum Discussions

Fresh From the Land Down Under – The Tou...
After a two week hiatus, we are back with another episode of The TouchArcade Show. Eli is fresh off his trip to Australia, which according to him is very similar to America but more upside down. Also kangaroos all over. Other topics this week... | Read more »
TouchArcade Game of the Week: ‘Dungeon T...
I’m a little conflicted on this week’s pick. Pretty much everyone knows the legend of Dungeon Raid, the match-3 RPG hybrid that took the world by storm way back in 2011. Everyone at the time was obsessed with it, but for whatever reason the... | Read more »
Hello gentle readers, and welcome to the SwitchArcade Round-Up for July 19th, 2024. In today’s article, we finish up the week with the unusual appearance of a review. I’ve spent my time with Hot Lap Racing, and I’m ready to give my verdict. After... | Read more »
Draknek Interview: Alan Hazelden on Thin...
Ever since I played my first release from Draknek & Friends years ago, I knew I wanted to sit down with Alan Hazelden and chat about the team, puzzle games, and much more. | Read more »
The Latest ‘Marvel Snap’ OTA Update Buff...
I don’t know about all of you, my fellow Marvel Snap (Free) players, but these days when I see a balance update I find myself clenching my… teeth and bracing for the impact to my decks. They’ve been pretty spicy of late, after all. How will the... | Read more »
‘Honkai Star Rail’ Version 2.4 “Finest D...
HoYoverse just announced the Honkai Star Rail (Free) version 2.4 “Finest Duel Under the Pristine Blue" update alongside a surprising collaboration. Honkai Star Rail 2.4 follows the 2.3 “Farewell, Penacony" update. Read about that here. | Read more »
‘Vampire Survivors+’ on Apple Arcade Wil...
Earlier this month, Apple revealed that poncle’s excellent Vampire Survivors+ () would be heading to Apple Arcade as a new App Store Great. I reached out to poncle to check in on the DLC for Vampire Survivors+ because only the first two DLCs were... | Read more »
Homerun Clash 2: Legends Derby opens for...
Since launching in 2018, Homerun Clash has performed admirably for HAEGIN, racking up 12 million players all eager to prove they could be the next baseball champions. Well, the title will soon be up for grabs again, as Homerun Clash 2: Legends... | Read more »
‘Neverness to Everness’ Is a Free To Pla...
Perfect World Games and Hotta Studio (Tower of Fantasy) announced a new free to play open world RPG in the form of Neverness to Everness a few days ago (via Gematsu). Neverness to Everness has an urban setting, and the two reveal trailers for it... | Read more »
Meditative Puzzler ‘Ouros’ Coming to iOS...
Ouros is a mediative puzzle game from developer Michael Kamm that launched on PC just a couple of months back, and today it has been revealed that the title is now heading to iOS and Android devices next month. Which is good news I say because this... | Read more »

## Price Scanner via MacPrices.net

Amazon is still selling 16-inch MacBook Pros...
Prime Day in July is over, but Amazon is still selling 16-inch Apple MacBook Pros for \$500-\$600 off MSRP. Shipping is free. These are the lowest prices available this weekend for new 16″ Apple... Read more
Walmart continues to sell clearance 13-inch M...
Walmart continues to offer clearance, but new, Apple 13″ M1 MacBook Airs (8GB RAM, 256GB SSD) online for \$699, \$300 off original MSRP, in Space Gray, Silver, and Gold colors. These are new MacBooks... Read more
Apple is offering steep discounts, up to \$600...
Apple has standard-configuration 16″ M3 Max MacBook Pros available, Certified Refurbished, starting at \$2969 and ranging up to \$600 off MSRP. Each model features a new outer case, shipping is free,... Read more
Save up to \$480 with these 14-inch M3 Pro/M3...
Apple has 14″ M3 Pro and M3 Max MacBook Pros in stock today and available, Certified Refurbished, starting at \$1699 and ranging up to \$480 off MSRP. Each model features a new outer case, shipping is... Read more
Amazon has clearance 9th-generation WiFi iPad...
Amazon has Apple’s 9th generation 10.2″ WiFi iPads on sale for \$80-\$100 off MSRP, starting only \$249. Their prices are the lowest available for new iPads anywhere: – 10″ 64GB WiFi iPad (Space Gray or... Read more
Apple is offering a \$50 discount on 2nd-gener...
Apple has Certified Refurbished White and Midnight HomePods available for \$249, Certified Refurbished. That’s \$50 off MSRP and the lowest price currently available for a full-size Apple HomePod today... Read more
The latest MacBook Pro sale at Amazon: 16-inc...
Amazon is offering instant discounts on 16″ M3 Pro and 16″ M3 Max MacBook Pros ranging up to \$400 off MSRP as part of their early July 4th sale. Shipping is free. These are the lowest prices... Read more
14-inch M3 Pro MacBook Pros with 36GB of RAM...
B&H Photo has 14″ M3 Pro MacBook Pros with 36GB of RAM and 512GB or 1TB SSDs in stock today and on sale for \$200 off Apple’s MSRP, each including free 1-2 day shipping: – 14″ M3 Pro MacBook Pro (... Read more
14-inch M3 MacBook Pros with 16GB of RAM on s...
B&H Photo has 14″ M3 MacBook Pros with 16GB of RAM and 512GB or 1TB SSDs in stock today and on sale for \$150-\$200 off Apple’s MSRP, each including free 1-2 day shipping: – 14″ M3 MacBook Pro (... Read more
Amazon is offering \$170-\$200 discounts on new...
Amazon is offering a \$170-\$200 discount on every configuration and color of Apple’s M3-powered 15″ MacBook Airs. Prices start at \$1129 for models with 8GB of RAM and 256GB of storage: – 15″ M3... Read more

## Jobs Board

*Apple* Systems Engineer - Chenega Corporati...
…LLC,** a **Chenega Professional Services** ' company, is looking for a ** Apple Systems Engineer** to support the Information Technology Operations and Maintenance Read more
Solutions Engineer - *Apple* - SHI (United...
**Job Summary** An Apple Solution Engineer's primary role is tosupport SHI customers in their efforts to select, deploy, and manage Apple operating systems and Read more
*Apple* / Mac Administrator - JAMF Pro - Ame...
Amentum is seeking an ** Apple / Mac Administrator - JAMF Pro** to provide support with the Apple Ecosystem to include hardware and software to join our team and Read more
Operations Associate - *Apple* Blossom Mall...
Operations Associate - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Read more
Cashier - *Apple* Blossom Mall - JCPenney (...
Cashier - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Blossom Mall Read more