TweetFollow Us on Twitter

Sep 94 Challenge
Volume Number:10
Issue Number:9
Column Tag:Programmer’s Challenge

Programmer’s Challenge

By Mike Scanlin, Mountain View, CA

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 we present a different programming challenge here. First, you write some code that solves the challenge. Second, optimize your code (a lot). Then, submit your solution to MacTech Magazine (formerly MacTutor). We choose a winner 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 available 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). Use only pure C code. We will disqualify any entries with any assembly in them (except for those challenges specifically stated to be in assembly). You may call any routine in the Macintosh toolbox you want (e.g., it doesn’t matter if you use NewPtr instead of malloc). We test entries with the FPU and 68020 flags turned off in THINK C. We time routines with the latest version of THINK C (with “ANSI Settings”, “Honor ‘register’ first”, and “Use Global Optimizer” turned on), so beware if you optimize for a different C compiler. Limit your code to 60 characters wide. This helps us deal with e-mail gateways and simplifies page layout.

We publish the solution and winners for this month’s Programmers’ Challenge 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.

Mark solutions “Attn: Programmers’ Challenge Solution” and send them via e-mail - Internet progchallenge@xplain.com, AppleLink MT.PROGCHAL, CompuServe 71552,174 and America Online MT PRGCHAL. Include the solution, all related files, and your contact information. If you send via snail mail, please send a disk with those items on it; see “How to Contact Xplain Corporation” on page 2.

MacTech Magazine reserves the right to publish any solution entered in the Programming Challenge of the Month. Authors grant MacTech Magazine the non-exclusive right to publish entries without limitation upon submission of each entry. Authors retain copyrights for the code.

Erase Scribble

Challenge entrants liked the proposal for one function to set up their caches (which was not timed) and a second function to do the actual work (which was time critical). I can see why; it mirrors the way we implement things in the real world quite well. So, this month we have another challenge along these lines. The goal is to write the core code for an eraser tool. The tool erases line segments of a scribble drawn in the draw layer of a drawing program.

A Scribble is a variable length structure defined as:


/* 1 */
typedef struct Scribble {
 Point  startingPoint;
 Point  deltaPoints[];
}  Scribble,
  *ScribblePtr,
 **ScribbleHndl;

The startingPoint is where the scribble begins and each Point after that is a signed (dv,dh) offset from that point to the next point. At the very end of the deltaPoints array is a (0,0) entry. So if you had these bytes (0001 0004 0007 FFFF 0001 0001 0000 0000) then the scribble would consist of two line segments. One going from (x=4,y=1) to (3,8) and the other from (3,8) to (4,9).

The prototype of the two functions you write are:


/* 2 */
void *EraseScribbleInit(  theScribble, eraserSize);
ScribbleHndltheScribble;
unsigned short eraserSize;

Boolean PtInScribble(thePoint, theScribble, eraserSize,
 privateScribbleDataPtr);
Point   thePoint;
ScribbleHndltheScribble;
unsigned short eraserSize;

void      *privateScribbleDataPtr;

The routine EraseScribbleInit will be called once at the beginning of a given erase operation. It will NOT be timed (only the PtInScribble will count towards your time). It can create whatever lookup tables PtInScribble may need (up to 32K) and return a pointer to that private data. The return value from EraseScribbleInit will be passed to PtInScribble as the privateScribbleDataPtr parameter. You decide what it points to (if anything). And, yes, the same ScribbleHndl will be passed to the Init routine that is passed to the PtInScribble routine.

The scribbles that will be used will have between 2 and 500 Points (including the startingPoint). The eraserSize parameter is the size in pixels of the square eraser that the user is moving around. It will vary from 4 to 16 pixels and will be an even number. The function PtInScribble should return true if any part of the eraser is touching any of the vertices of the Scribble and false if not. Note that having the eraser intersect the middle of a line segment that is part of the Scribble does not count as a hit. This particular eraser only erases when it touches an endpoint of a segment. The (dv,dh) numbers will typically be small, probably 16 or less in absolute value with the average around 4 in absolute value (so that we have smooth Scribbles). The bounding box that contains each Scribble will be 1024 pixels square or smaller.

The goal is to make a PtInScribble routine fast enough so that the eraser the user is dragging around is not sluggish (imagine erasing a page containing 20 or 30 separate overlapping Scribbles). My test routine that calls your PtInScribble routine will take care of all the drawing and actual erasing; you just have to determine when the eraser touches a vertex of the Scribble or not.

Oh, yeah, one more thing: September is always Assembly Language Month here at the Programmer Challenge, and so, for this month only, you are allowed to use as much assembly language as you like in your solution. In fact, it is perfectly admissible to send in a C wrapper around a 100% assembly language solution. But you still have to write it in Think C using the prototypes above (use asm {} within the body of the function). In addition, you can write 68040 assembly if you want to (i.e. use instructions or addressing modes that may not exist on 68000, 020 and/or 030). Let ’em rip!

Two Months Ago Winner

Congratulations to Bob Noll (Arlington Heights, IL) for his excellent entry in the Color Space Conversion challenge. This is Bob’s first 1st place showing and it was during a month where there were several very high quality entries. Most of the 15 entries were no more than 50% slower than Bob’s winning entry.

Here are the times, code sizes and data sizes for each entry. The data size represents how many bytes the RGBtoYUVInit routine allocated when it was called (i.e. the size of the private lookup tables). 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 data

Bob Noll 135 1038 394272

Dan Waylonis 153 518 9232

Bob Boonstra (10) 165 1508 789520

Ernst Munter (1) 173 404 12336

Larry Landry (2) 174 1554 795728

Joe Francis 183 1154 9342

Ronald Nepsund (2) 190 744 7184

Clement Goebel (3) 195 1094 8208

Michael Panchenko (1) 198 278 9232

Allen Stenger (7) 227 1528 520240

John Schlack 236 916 9232

Ted DiSilvestre 283 674 9408

Daniel Farmer (1) 289 830 8208

Kevin Cutts (3) 563 698 31952

David Nebiker 4955 1178 27664

Bob decided to optimize his RGBtoYUVInit routine even though it would not count towards his overall time (bravo!). To get both speed and accuracy he uses a 96-bit fixed point number to create his lookup tables. He then implemented his own routines to perform math on this custom format. And he was able to integrate his rounding factor into his lookup tables to save himself that final step when calculating y, u and v.

I received quite a bit of mail regarding my statement “.5 rounding down to zero.” I did not disqualify anyone for misinterpreting this. What I meant was “.5 should round towards zero” meaning that -.5 to .5 inclusive should be rounded to zero. There are gains to be had when writing a JPEG compression engine if you can get as many zeros as possible up front, which is the reason for this non-standard (i.e. symmetrical about zero) way of rounding.

Here’s Bob’s winning solution:


/* 3 */
Written by Robert A. Noll, July, 1994.  Copyright © 1994 Robert A. Noll
RGBtoYUV.h 
RGBtoYUV.h - Header for RGBtoYUV routine.
#define NegToZero 1
typedef struct {
 unsigned long   sig;
 unsigned long*  rp;
 unsigned long*  gbp;
 unsigned char*  up;
 unsigned char*  vp;
 unsigned long   r[256];
 unsigned long   gb[65536];
 unsigned char   u[65536];
 unsigned char   v[65536];
 } PrivateBlock;

void *RGBtoYUVInit(void);

void RGBtoYUV(unsigned char *rPtr, // Red buffer
   unsigned char *gPtr,   // Green buffer
   unsigned char *bPtr,   // Blue buffer
   unsigned char *yPtr,   // Luminance buffer
     signed char *uPtr,   // U Chrominance buff
   signed char *vPtr,// V Chrominance buff
   unsigned long numPixels, // Number of Pixels
   void *privateDataPtr); // My private data

RGBtoYUV.c
RGBtoYUV.c - Convert RGB color to YUV color.

#include "RGBtoYUV.h"

RGBtoYUV

RGBtoYUV - Calculate the Y, U, and V values for set of R, G, and B values 
input.  This function relies completely on the data set up by RGBtoYUVInit 
and therefore checks the validity of the data sent.  It will return with 
no action if data is not valid.

void RGBtoYUV(unsigned char *rPtr, // Red buffer
   unsigned char *gPtr,   // Green buffer
   unsigned char *bPtr,   // Blue buffer
   unsigned char *yPtr,   // Luminance buffer
   signed char *uPtr,// U Chrominance buff
   signed char *vPtr,// V Chrominance buff
   unsigned long numPixels, // Number of Pixels
   void *privateDataPtr)  // My private data
 {
 PrivateBlock* pb = (PrivateBlock*)privateDataPtr;
 unsigned long *rp = pb->rp;
 unsigned long *gbp = pb->gbp;
 unsigned char *up = pb->up;
 unsigned char *vp = pb->vp;
 unsigned long tmp;
 union {
 unsigned short i;
 unsigned char c[2];
 } gb;
 
 if (pb->sig != 'RNCS') return;
 
 for (; numPixels>0; --numPixels,++rPtr,++gPtr,++bPtr,
 ++yPtr,++uPtr,++vPtr) {
 gb.c[0] = *gPtr;//Get index into gb and v tables 
 gb.c[1] = *bPtr;
 
 tmp = rp[*rPtr] + gbp[gb.i]; //  Calculate Y value from tables
 *yPtr = *((unsigned char*)&tmp);
 
 *vPtr = (*rPtr - vp[gb.i]) >> 1;  //  Calculate V value from table
 
 gb.c[0] = *rPtr;//Get index into u table
 gb.c[1] = *gPtr;
 
#if NegToZero
 //If for Negs .5 rounds up to 0 then if R == G and R|G > B we calc special.
 if (*rPtr==*gPtr && *gPtr>*bPtr)
 *uPtr = ((*bPtr - *gPtr) + 1) >> 1;
 else
#endif
 *uPtr = (*bPtr - up[gb.i]) >> 1;  // Calculate U value from table
 }
 }


RGBtoYUVInit.c
RGBtoYUVInit.c - Sets up the tables for use by RGBtoYUV.

#include "RGBtoYUV.h"

// A fixed point number type with 8 bits of intregral part and 88 bits 
of fractional part.
typedef struct {
 unsigned long val[3];
 } BigNum;
 
typedef struct {
 BigNum y[256];
 BigNum g[256];
 BigNum b[256];
 } TempBlock;

Multiply
Multiply - Takes a BigNum and multiplies it by a number in the range 
0 - 255.  
Result is put into 'ans'.

void Multiply(void* bits, unsigned char num, void* ans)
 {
 int x;
 unsigned short* bp = (unsigned short*)bits + 5;
 unsigned short* ap = (unsigned short*)ans + 5;
 unsigned long val = 0;
 
 for (x=6; x; --x,--bp,--ap) {
 val += (unsigned long)*bp * num;
 *ap = val;
 val >>= 16;
 }
 }

Add
Add - Adds two BigNums and returns the result in 'ans'

void Add(void* bits1, void* bits2, void* ans)
 {
 int x;
 unsigned short* bp1 = (unsigned short*)bits1 + 5;
 unsigned short* bp2 = (unsigned short*)bits2 + 5;
 unsigned short* ap = (unsigned short*)ans + 5;
 unsigned long val = 0;
 
 for (x=6; x; --x,--bp1,--bp2,--ap) {
 val += (unsigned long)*bp1 + *bp2;
 *ap = val;
 val >>= 16;
 }
 }
 
RGBtoYUVInit
RGBtoYUVInit - Sets up all the tables used by the RGBtoYUV function.
 
Since accuracy is a concern, I use my own number format and routines 
to calculate tables.  It turns out that FP routines are just as accurate 
but my stuff is 3x faster.

About calculations in general:

A table with all 16M values for each of Y, U, and V would be nice but, at 48MB, would be way over 1MB limit. With minor calcs in 'RGBtoYUV' I need two 64K entry tables for each of U and V. At full precision they would be 768K each. They get reduced greatly later. The Y table I break into two tables: one for the R calcs and one for the G and B combination. At full precision they would take 3K and 768K respectively. They get reduced later also. At this point we are a lot closer to the 1MB limit.

About Y calculations:

• 24 bits of fractional precision for the two tables was found to give proper results. This was found by checking the result of rounding the full precision result against the rounding of the sum of the two table entries for EVERY one of the 16M combinations. This allows us to represent our table entries in tables of 'unsigned long's. Table sizes are thus reduced to 1K and 256K.

• Rounding is handled by adding .7FFFFFFFFFFFFFFFFFFFFF to the 'gb' table values. This allows RGBtoYUV to just truncate its result.

• When R, G, and B are all equal then Y is the same number. With the tables that are built the checking for such a limited case (256 out of 16,777,216) just added space. (To calc 16M values takes a little over 2 minutes)

About U and V in general:

• Since B and R are multipied by .5 for these calcs we can except them as 7 bits of integral part and 1 bit of fraction.

• Since the B or R calculation will always result in some number X.0 or X.5. This enables us to do all rounding in the table values. Also we are able to store the table numbers in the same 7.1 bit format.

• If rounding is always down then RGBtoYUV can just truncate after the subtraction. If rounding is to be toward zero then special handling is needed.

About V calculations:

Because of the number of decimal places and the fact that the multipliers add up to .50000001 the G and B combination will never result in exactly X.0 or X.5. Thus for V we don't need to worry about whether -0.5 rounds up or down.

About U calculations:

• The R and G combination values will result in an X.0 or X.5 result when R == G

• If rounding is always down (.5 -> 0 and -.5 -> -1) then truncation after the calculation is all that is needed.

• If rounding is always towards zero (.5 -> 0 and -.5 -> 0) then RGBtoYUV will add .5 and then truncate when R and G are equal. All other cases will still be handled with just truncation.

 
/* 4 */
void *RGBtoYUVInit(void)
 {
 short r,g,b;
 BigNum mat[] = {
    { 0x004C8B43, 0x95810624, 0xDD2F1A9F },/*.29900000*/
    { 0x009645A1, 0xCAC08312, 0x6E978D4F },/*.58700000*/
    { 0x001D2F1A, 0x9FBE76C8, 0xB4395810 },/*.11400000*/
    { 0x002B3246, 0xA4293F94, 0x6A85AFD7 },/*.16873590*/
    { 0x0054CDB9, 0x5BD6C06B, 0x957A5028 },/*.33126410*/
    { 0x00800000, 0x00000000, 0x00000000 },/*.50000000*/
    { 0x00800000, 0x00000000, 0x00000000 },/*.50000000*/
    { 0x006B2F1C, 0x4D3DA074, 0x7F2DDD88 },/*.41868760*/
    { 0x0014D0E3, 0xDDB57D4F, 0xE1EA9636 },/*.08131241*/
    { 0x007FFFFF, 0xFFFFFFFF, 0xFFFFFFFF } /*.49999999*/
    };
 unsigned long *rp, *gbp;
 BigNum *gp, *bp, *yp, yt, ut, vt, xt;
 unsigned char *up, *vp;
 PrivateBlock *pb;
 TempBlock *tb;

 pb = (PrivateBlock*)NewPtr(sizeof(PrivateBlock));
 if (pb==0) {
 DebugStr("\pOut of Memory");
 return;
 }
 pb->rp = pb->r;
 pb->gbp = pb->gb;
 pb->up = pb->u;
 pb->vp = pb->v;
 
 tb = (TempBlock*)NewPtr(sizeof(TempBlock));
 if (tb==0) {
 DebugStr("\pOut of Memory");
 return;
 }
 
// r-values never = x.0 or x.5
 rp = pb->rp;
 for (r=0; r<256; ++r,++rp) {
 Multiply(&mat[0],r,&xt);
 *rp = *((unsigned long*)&xt);
 }
 
// This method same as 0-255, 0-255 method.
// My calc routines equal SANE routines and are 3 times faster.
// u-values are never == x.0 or x.5
// v-values are never == x.0 or x.5
  yp = tb->y;
  gp = tb->g;
  bp = tb->b;
 gbp = pb->gbp;
  up = pb->up;
  vp = pb->vp;
 for (b=0; b<256; ++b,++yp,++gp,++bp,++gbp,++up,++vp) {
 Multiply(&mat[2],b,yp);
 Add(yp,&mat[9],yp);
 *gbp = *((unsigned long*)yp);
 Multiply(&mat[4],b,gp);
 // Add(gp,&mat[9],gp);
 *up = *((unsigned short*)gp) >> 7;
 Multiply(&mat[8],b,bp);
 // Add(bp,&mat[9],bp);
 *vp = *((unsigned short*)bp) >> 7;
 }
 for (g=1; g<256; ++g) {
 Multiply(&mat[1],g,&yt);
 Add(&yt,&mat[9],&xt);
 *gbp = *((unsigned long*)&xt);
 ++gbp;
 Multiply(&mat[3],g,&ut);
 // Add(&ut,&mat[9],&xt);
 *up = *((unsigned short*)&ut) >> 7;
 ++up;
 Multiply(&mat[7],g,&vt);
 // Add(&vt,&mat[9],&xt);
 *vp = *((unsigned short*)&vt) >> 7;
 ++vp;
 yp = &tb->y[1];
 gp = &tb->g[1];
 bp = &tb->b[1];
 for (b=1; b<256;
 ++b,++gbp,++yp,++up,++gp,++vp,++bp) {
 Add(&yt,yp,&xt);
 *gbp = *((unsigned long*)&xt);
 if (g==b) {
 *up = b;
 *vp = b;
 }
 else {
 Add(&ut,gp,&xt);
 *up = *((unsigned short*)&xt) >> 7;
 Add(&vt,bp,&xt);
 *vp = *((unsigned short*)&xt) >> 7;
 }
 }
 }
 
 if (tb!=0)
 DisposPtr((Ptr)tb);

 pb->sig = 'RNCS';
 return pb;
 }







  
 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Latest Forum Discussions

See All

Can PokeMatch help you find love with Po...
The unofficial Pokemon GO companion app space has exploded almost as fast as the game itself over the last few weeks. Aspiring app developers, many of them working solo, have given us apps that locate Pokemon, keep track of the server status, and... | Read more »
How to get started with Prisma
If there's one thing people like to do more than taking pictures with their smartphones, it's tinkering with those photos in some way. Numerous apps have sprung up over the last several years that allow you to use filters and special effects to... | Read more »
6 Pokemon GO updates you can expect, acc...
Pokemon GO had a scheduled appearance at this year's San Diego Comic-Con for a while, but it was only relatively close to the show that it was upgraded to a spot in Hall H. That's the biggest venue at SDCC, one usually reserved for the largest... | Read more »
How to evolve Eevee in Pokemon GO
By now, almost everyone should be hip to how to evolve Pokemon in Pokemon GO (and if not, there's a guide for that). Just gather enough candy of the appropriate type, feed them all to the Pokemon, and evolution happens. It's a miracle that would... | Read more »
CSR Racing 2: Guide to all game modes
It might not seem like there are all that many ways to go fast in a straight line, but CSR Racing 2 begs to differ. [Read more] | Read more »
Bulb Boy (Games)
Bulb Boy 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: Multi-award winning 2D point & click horror adventure about a boy with a glowing head. | Read more »
5 top free emoji keyboard apps
If we're not at peak emoji yet as a society, it feels like we definitely should be. The emoji concept has gone far beyond what anyone in Japan could have envisioned when the people there unleashed it on an unsuspecting world, but the West has... | Read more »
How to unlock more characters in Disney...
One of the big charms of Disney Emoji Blitz is seeing a wide variety of beloved Disney and Pixar characters transformed into smiling emojis. Even someone like the sneaky Randall from Monsters Inc., who probably never cracked a smile on film, is... | Read more »
Cubway (Games)
Cubway 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: Cubway is a journey with an abstract story of lifecycle of rebirth, called Samsara. Guide the cube through the long way full of dangers... | Read more »
Colorcube (Games)
Colorcube 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: Turn pieces and blend colours in this minimal yet visually stunning puzzler.Over 200 handcrafted and challenging levels. Features... | Read more »

Price Scanner via MacPrices.net

External Keyboard Innovations For iPad Pro (1...
I’m an input device aficionado. With non-touchscreen computers, which includes all Macs, the keyboard and mouse or trackpad are the tactile points of interface between user and machine, and the... Read more
GSK Rheumatoid Arthritis Study Leverages iPho...
Global healthcare products company GlaxoSmithKline (GSK) says that since 2014 they have begun transforming the way they conduct research, by leveraging state-of-the-art digital technologies — a... Read more
Clearance 12-inch Retina MacBooks, Apple refu...
Apple has Certified Refurbished 2015 12″ Retina MacBooks available starting at $929. Apple will include a standard one-year warranty with each MacBook, and shipping is free. The following... Read more
13-inch Retina MacBook Pros on sale for up to...
B&H Photo has 13″ Retina MacBook Pros on sale for up to $150 off MSRP. Shipping is free, and B&H charges NY tax only: - 13″ 2.7GHz/128GB Retina MacBook Pro: $1199 $100 off MSRP - 13″ 2.7GHz/... Read more
13-inch 1.6GHz/128GB MacBook Air on sale for...
Amazon has the 13″ 1.6GHz/128GB MacBook Air on sale for $200 off MSRP for a limited time. Shipping is free: - 13″ 1.6GHz/128GB MacBook Air (sku MMGF2LL/A): $799.99 $200 off MSRP Their price is the... Read more
13-inch 1.6GHz/256GB MacBook Air on sale for...
Amazon has the 13″ 1.6GHz/256GB MacBook Air on sale for $200 off MSRP for a limited time. Shipping is free: - 13″ 1.6GHz/256GB MacBook Air (sku MMGG2LL/A): $999.99 $200 off MSRP Their price is the... Read more
Free iOS Business App notably* Helps Service...
PayStudio Inc. has introduced their new business app notably* 1.0, developed for iPhone and iPod touch. notably* was specifically developed to help service and trade professionals go digital and... Read more
27-inch iMacs on sale for $200 off MSRP
Amazon has 27″ iMacs on sale for $200 off MSRP including free shipping: - 27″ 3.3GHz iMac 5K: $2099 $200 off MSRP - 27″ 3.2GHz/1TB Fusion iMac 5K: $1799.99 $200 off MSRP - 27″ 3.2GHz/1TB HD iMac 5K... Read more
Mac Pros on sale for $200 off MSRP
B&H Photo has Mac Pros on sale for $200 off MSRP. Shipping is free, and B&H charges sales tax in NY only: - 3.7GHz 4-core Mac Pro: $2799, $200 off MSRP - 3.5GHz 6-core Mac Pro: $3799, $200... Read more
Save up to $600 with Apple refurbished Mac Pr...
Apple has Certified Refurbished Mac Pros available for up to $600 off the cost of new models. An Apple one-year warranty is included with each Mac Pro, and shipping is free. The following... Read more

Jobs Board

*Apple* Retail - Multiple Positions, Willow...
Job Description:SalesSpecialist - Retail Customer Service and SalesTransform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* Evangelist - JAMF Software (United S...
The Apple Evangelist is responsible for building and cultivating strategic relationships with Apple 's small and mid-market business development field teams. This Read more
*Apple* Solutions Consultant - APPLE (United...
Job Summary As an Apple Solutions Consultant, you'll be the link between our future customers and our products. You'll showcase your entrepreneurial spirit as you Read more
*Apple* Professional Learning Specialist - A...
Job Summary The Apple Professional Learning Specialist is a full-time position for one year with Apple in the Phoenix, AZ area. This position requires a high Read more
*Apple* Picker - Apple Hill Orchard (United...
Apple Hill Orchard, Co. Rte. 21,Whitehall, NY 9/7/16-10/228/16. Pick fresh market or processing apples Productivity of 60 boxes and 80 boxes processing fruit per Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.