TweetFollow Us on Twitter

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 or source 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

Response to Jan 94 MacTech Programmer's Challenge.

Object: Go around QD to draw color lines as fast as possible.

Specs:

• nDots >= 2,

• handle only cases {(pixelSize,cmpSize,cmpCount) = (8,8,1), (16,5,3), (32,8,3)},

• arbitrary alpha-bits,

• don't bother clipping,

• penSize = 1,1,

• patCopy mode.

Notes on method: Specify segment by two endpoints {(x,y)=(a,b),(A,B)}. Form of line is {(x,y): (y-b)/(x-a) = m}, where slope m = (B-b)/(A-a). Then, y = m*(x-a)+b.

Two successive values of y are: y2 = m*(x2-a)+b; y1 = m*(x1-a)+b, and the diff is, y2-y1 = m, since x2-x1 will always = 1 (pixel).

Therefore, as we move from x to x, we add or sub m to the previous value of y.

Speed: The cases that arise for combinations of {dy,dx} fall generally into 8 octants that cover the plane. Diagonally opposite octants are treated together, so there are 4 main cases to worry about. We first weed out 3 special cases: exactly horizontal, vertical, and diagonal segs. These are the simplest, most common, and fastest.

In a given octant, one of |dx|, |dy| is strictly larger than the other. Our loop over pixels will always be over the larger magnitude for higher resolution drawing. The slope is formed then by smallNum/largeNum which must have quotient == 0, and remainder == smallNum. Adding the slope is a matter of accumulating remainders. If this sum exceeds largeNum, we move to next pixel.


/* 2 */
#pragma options( honor_register, !assign_registers )
#pragma options( !check_ptrs )

#include"ConnectTheDots.h"

#define HiFiveMask 0xF800
#define Abs( a ) (a > 0 ? a : -a)

/* RGB2Index
 *
 * Expects rgb color is an exact member of table, to avoid time spent 
close
 * matching. Index is just position in table.
 */
static Byte RGB2Index( ColorSpec *cSpec, RGBColor *rgb )
{
 register ColorSpec*cs = cSpec;
 register short  entries = ((short*)cs)[-1]+1;
 register short  red = rgb->red,
 green = rgb->green,
 blue = rgb->blue;
 do {
 if( red   == cs->rgb.red  &&
 blue  == cs->rgb.blue &&
 green == cs->rgb.green )
 return cs-cSpec;
 ++cs;
 } while( --entries );
}
/* Lines8
 *
 * Depth == 8 case.
 *
 * To maximize register usage, chose to put rowBytes in address reg. 
 
 * Also, some vars like v_Cnt are dual purpose.
 */
static void Lines8(
 PixMapPtrpm,
 Point  dot[],
 unsigned short  nDots,
 register Byte   pixel )
{
 register Ptr  at;
 #include "ConnectTheDots.com"
}

/* Lines16
 */
static void Lines16(
 PixMapPtrpm,
 Point  dot[],
 unsigned short  nDots,
 register short  pixel )
{
 register short  *at;
 #include "ConnectTheDots.com"
}

/* Lines32
 *
 * align ensures 4-byte stack alignment for better speed.
 */
static void Lines32(
 PixMapPtrpm,
 Point  dot[],
 unsigned short  nDots,
 short  align,
 register long   pixel )
{
 register long   *at;
 #include "ConnectTheDots.com"
}

/* ConnectTheDots */
void ConnectTheDots(
 unsigned short  nDots,
 Point  dot[],
 PixMapHandle    pmH,
 RGBColor color )
{
 register PixMapPtrpm = *pmH;
 register unsigned short  pix16;
 register Ptr    p32;
 long   pix32;
 
 if( pm->pixelSize == 8 ) {
 
 Lines8( pm, dot, nDots,
 RGB2Index(&(**pm->pmTable).ctTable, &color) );
 }
 if( pm->pixelSize == 16 ) {

 pix16  = (color.red   & HiFiveMask) >> 1;
 pix16 |= (color.green & HiFiveMask) >> 6;
 pix16 |= (color.blue  & HiFiveMask) >> 11;
 
 Lines16( pm, dot, nDots, pix16 );
 }
 if( pm->pixelSize == 32 ) {
 
 p32 = ((Byte*)&pix32) + 1;
 *p32++ = *(Byte*)&color.red;
 *p32++ = *(Byte*)&color.green;
 *p32++ = *(Byte*)&color.blue;
 
 Lines32( pm, dot, nDots, 0, pix32 );
 }
}

This is the part of the line drawing algorithm common to all three depths, and it’s in its own separate file called ConnectTheDots.com. This is an unusual, but very useful way to use #include directive. Treat this file like a .h file, though it contains code instead of interface info. That means, like a .h file, you do not directly compile or link this file. If using Think C, don't put it in your project. It automatically becomes part of the .c file at compile time.

/* 3 */
/* ConnectTheDots.com
*/

// start
 register Ptr    rowBytes;
 register short  *pnt;
 register short  dh, dv, h_Sum, v_Cnt;
 Ptr    savedRowBytes;
 short  *savedPnt;
 short  pad;
 
 --nDots;
 
 pnt = (short*)dot;
 savedRowBytes = (Ptr)(pm->rowBytes & 0x7fff);

 do {

 // find this seg's dimensions {dv,dh} and endpoints in bounds coordinate
 // system.  ends are (v,h) and (v+dv,h+dh).
 // point to pixels, and restore rowBytes, which are altered in loop.

 dv       = *pnt++;
 dh       = *pnt++;
 v_Cnt    = *pnt;
 h_Sum    = pnt[1];
 dv      -= v_Cnt;
 dh      -= h_Sum;
 v_Cnt   -= pm->bounds.top;
 h_Sum   -= pm->bounds.left;
 at       = pm->baseAddr;
 rowBytes = savedRowBytes;
 
 if( !dh ) {
 // do vertical line
 if( dv < 0 ) {
 v_Cnt += dv;
 dv = -dv;
 }

 at = (Ptr)at + (long)v_Cnt*(short)rowBytes;
 at += h_Sum;
 
 v_Cnt = dv + 1;
 
doVert:
 do {
 *at = pixel;
 at = (Ptr)at + (long)rowBytes;
 } while( --v_Cnt );
 }
 else if( !dv ) {
 
 // do horizontal line
 
 if( dh < 0 ) {
 h_Sum += dh;
 dh = -dh;
 }
 
 at = (Ptr)at + (long)v_Cnt*(short)rowBytes;
 at += h_Sum;
 
 ++dh;
 
 do {
 *at++ = pixel;
 } while( --dh );
 }
 else if( Abs( dv ) >= Abs( dh ) ) {
 
 // more vertical or diagonal
 
 if( dv < 0 ) {
 v_Cnt += dv;
 h_Sum += dh;
 dv = -dv;
 dh = -dh;
 }
 
 at = (Ptr)at + (long)v_Cnt*(short)rowBytes;
 at += h_Sum;
 
 v_Cnt = dv + 1;
 
 if( dh == dv ) {
 rowBytes += sizeof(pixel);
 goto doVert;
 }
 else if( -dh == dv ) {
 rowBytes -= sizeof(pixel);
 goto doVert;
 }
 else {

 h_Sum = 0;
 
 savedPnt = pnt;
 pnt = (short*)sizeof(pixel);
 
 if( dh < 0 ) {
 dh = -dh;
 pnt = (short*)-sizeof(pixel);
 }

 do {
 *at = pixel;
 at = (Ptr)at + (long)rowBytes;
 
 h_Sum += dh;
 
 if( h_Sum >= dv ) {
 h_Sum -= dv;
 at = (Ptr)at + (long)pnt;
 }
 } while( --v_Cnt );
 
 pnt = savedPnt;
 }
 }
 else {
 
 // more horizontal
 
 if( dh < 0 ) {
 v_Cnt += dv;
 h_Sum += dh;
 dv = -dv;
 dh = -dh;
 }
 
 at = (Ptr)at + (long)v_Cnt*(short)rowBytes;
 at += h_Sum;
 
 v_Cnt = dh + 1;
 h_Sum = 0;

 if( dv < 0 ) {
 dv = -dv;
 rowBytes = (Ptr)(-(short)rowBytes);
 }
 
 do {
 *at++ = pixel;
 
 h_Sum += dv;
 
 if( h_Sum >= dh ) {
 h_Sum -= dh;
 at = (Ptr)at + (long)rowBytes;
 }
 } while( --v_Cnt );
 }
 } while( --nDots );
 
// end







  
 

Community Search:
MacTech Search:

Software Updates via MacUpdate

WhiteCap 6.7 - Visual plug-in for iTunes...
WhiteCap is a sleek and sophisticated music visualizer and screensaver that features futuristic, wireframe mesh visuals with dynamic backgrounds and colors. WhiteCap contains thousands of visual... Read more
Dropbox 24.4.16 - Cloud backup and synch...
Dropbox is an application that creates a special Finder folder that automatically syncs online and between your computers. It allows you to both backup files and keep them up-to-date between systems... Read more
Amazon Chime 4.2.5645 - Amazon-based com...
Amazon Chime is a communications service that transforms online meetings with a secure, easy-to-use application that you can trust. Amazon Chime works seamlessly across your devices so that you can... Read more
Notion 0.1.8 - A unified workspace for m...
Notion is the unified workspace for modern teams. Features: Integration with Slack Documents Wikis Tasks Note: This application contains in-app and/or external module purchases. Version 0.1.8:... Read more
Google Chrome 58.0.3029.81 - Modern and...
Google Chrome is a Web browser by Google, created to be a modern platform for Web pages and applications. It utilizes very fast loading of Web pages and has a V8 engine, which is a custom built... Read more
Notion 0.1.8 - A unified workspace for m...
Notion is the unified workspace for modern teams. Features: Integration with Slack Documents Wikis Tasks Note: This application contains in-app and/or external module purchases. Version 0.1.8:... Read more
WhiteCap 6.7 - Visual plug-in for iTunes...
WhiteCap is a sleek and sophisticated music visualizer and screensaver that features futuristic, wireframe mesh visuals with dynamic backgrounds and colors. WhiteCap contains thousands of visual... Read more
Dropbox 24.4.16 - Cloud backup and synch...
Dropbox is an application that creates a special Finder folder that automatically syncs online and between your computers. It allows you to both backup files and keep them up-to-date between systems... Read more
Google Chrome 58.0.3029.81 - Modern and...
Google Chrome is a Web browser by Google, created to be a modern platform for Web pages and applications. It utilizes very fast loading of Web pages and has a V8 engine, which is a custom built... Read more
Amazon Chime 4.2.5645 - Amazon-based com...
Amazon Chime is a communications service that transforms online meetings with a secure, easy-to-use application that you can trust. Amazon Chime works seamlessly across your devices so that you can... Read more

Latest Forum Discussions

See All

ChordFlow (Music)
ChordFlow 1.0.0 Device: iOS Universal Category: Music Price: $6.99, Version: 1.0.0 (iTunes) Description: ChordFlow is a chord sequencer with a unique 4-track polyphonic arpeggiator, extensive chord library, MIDI out and Ableton Link... | Read more »
The Walking Dead: A New Frontier is out...
The newest season of Telltale Games'The Walking Dead is well underway. After the release of the third episode, "Above the Law" about a month ago, episode four, "Thicker Than Water" is hot and ready for more zombies and gut-wrenching emotional... | Read more »
Best games we played this week
Another week, another new wave of mobile games do dive into. We've dug through the list of apps that came out this week to tell you which apps are worth your sweet time. And while there weren't too many games this week, there were some big ones.... | Read more »
Vignettes (Games)
Vignettes 1.0.1 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0.1 (iTunes) Description: Vignettes is a casual but unique exploration game without text or characters, where objects shapeshift as you spin them around... | Read more »
Get Me Outta Here is an 80s retro shoote...
Are you ready to fight some aliens? Because Crescent Moon Games has released the retro shooter Get Me Outta Here on iOS devices today. [Read more] | Read more »
Get a bunch of Apple productivity apps f...
If you're an Apple Mac owner, you're probably aware of the host of Apple productivity apps the company includes in all new Mac purchases. Apps like iMovie, Keynote, and of course, GarageBand. While you used to be able to also buy these apps... | Read more »
Terra Mystica (Games)
Terra Mystica 1.03 Device: iOS Universal Category: Games Price: $9.99, Version: 1.03 (iTunes) Description: Short Summary:≈≈≈≈≈≈≈≈≈≈≈≈≈ | Read more »
Ms. Spell (Games)
Ms. Spell 1.0 Device: iOS Universal Category: Games Price: $.99, Version: 1.0 (iTunes) Description: Cast spells and battle monsters in this turn based game, that has you delving into ever the changing Dreadwood to retrieve the lost... | Read more »
Invert - A Minimal Puzzle Game (Games)
Invert - A Minimal Puzzle Game 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: Invert is a minimalist puzzle game for fans of brain teasers, logic puzzles, and Rubik's Cube fiddlers. | Read more »
Evergrow: Paper Forest (Games)
Evergrow: Paper Forest 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: Solve puzzles in the handcrafted forests of Evergrow through the eyes of an imaginative child and his parents. Discover... | Read more »

Price Scanner via MacPrices.net

Apple now offering Certified Refurbished 13-i...
Apple is now offering Certified Refurbished 2016 13″ Touch Bar MacBook Pros for $270-$300 off original MSRP. An Apple one-year warranty is included with each model, and shipping is free: - 13″ 2.9GHz... Read more
MyGiHealth Digestive Symptom Tracker Version...
My Total Health, Inc. has announced the release of MyGiHealth 2.1, an important update to their digestive symptom tracker developed exclusively for iPhone, iPad and iPod touch devices. MyGiHealth is... Read more
Galaxy S8 Materials Costs Highest by Far Comp...
The new Samsung Galaxy S8 equipped with 64 gigabytes (GB) of NAND flash memory carries a bill of materials (BOM) cost that comes out to US$301.60, much higher than for previous versions of the... Read more
iCarMode 4.0 Car Dashboard App For iOS Integr...
Indie developer Diego Resnik has announced the release of iCarMode 4.0, an update to his productivity app developed for iOS devices. iCarMode has positioned itself as a true car dashboard app,... Read more
How to save $150+ on Apple’s 13-inch 2.0GHz n...
Apple Authorized Reseller B&H Photo has non-Touch Bar 13″ 2.0GHz MacBook Pros on sale for $150 off MSRP for a limited time. Shipping is free, and B&H charges NY sales tax only: - 13″ 2.0GHz... Read more
15-inch 2.2GHz Retina MacBook Pro, Apple refu...
Apple has Certified Refurbished 2015 15″ 2.2GHz Retina MacBook Pros available for $1699. That’s $300 off MSRP, and it’s the lowest price available for a 15″ MacBook Pro. An Apple one-year warranty is... Read more
Apple Certified Refurbished iMacs available f...
Apple has Certified Refurbished 2015 21″ & 27″ iMacs available for up to $350 off MSRP. Apple’s one-year warranty is standard, and shipping is free. The following models are available: - 21″ 3.... Read more
Save up to $160 with Apple refurbished 9-inch...
Apple has Certified Refurbished 9″ and 12″ Apple iPad Pros available for up to $160 off the cost of new iPads. An Apple one-year warranty is included with each model, and shipping is free: - 32GB 9″... Read more
27-inch Apple iMacs on sale for $200 off MSRP
Amazon has 27″ iMacs on sale for $200-$201 off MSRP, each including free shipping: - 27″ 3.3GHz iMac 5K: $2099.99 $200 off MSRP - 27″ 3.2GHz/1TB Fusion iMac 5K: $1798 $201 off MSRP - 27″ 3.2GHz/1TB... Read more
13-inch 2.7GHz Retina MacBook Pro on sale for...
B&H Photo has the 2015 13″ 2.7GHz/128GB Retina Apple MacBook Pro on sale for $130 off MSRP. Shipping is free, and B&H charges NY tax only: - 13″ 2.7GHz/128GB Retina MacBook Pro (MF839LL/A): $... Read more

Jobs Board

*Apple* Mobile Master - Best Buy (United Sta...
What does a Best Buy Apple Mobile Master do? At Best Buy, our mission is to leverage the unique talents and passions of our employees to inspire, delight, and enrich Read more
*Apple* Retail - Multiple Positions - Apple,...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* Mac Computer Technician - GeekHampto...
…complex computer issues over the phone and in person? GeekHampton, Long Island's Apple Premium Service Provider, is looking for you! Come work with our crew Read more
*Apple* Mobile Master - Best Buy (United Sta...
**489879BR** **Job Title:** Apple Mobile Master **Location Number:** 000402-Utica-Store **Job Description:** **What does a Best Buy Apple Mobile Master do?** At Read more
Best Buy *Apple* Computing Master - Best Bu...
**500058BR** **Job Title:** Best Buy Apple Computing Master **Location Number:** 001092-Columbia Heights-Store **Job Description:** **What does a Best Buy Apple Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.