TweetFollow Us on Twitter

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 or source 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)
PixMapHandlethePixMapHndl;

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 <stdio.h>

#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;
    return 0;
  }

//
// Draw the characters of the given font into an offscreen
// bitmap.
//
void  DrawTheChars(GrafPtr charPort)
{ 
  register Point scalePt = {1,1};
  register short hPos = kMaxCharWidth-charWid;
  register short count;
  uchar chVal = kFirstChar;
  count = kNumChars; do {
    charPort->pnLoc.h = hPos;
    StdText(1,&chVal,scalePt,scalePt);
    hPos += kMaxCharWidth;
    ++chVal;
  } while (--count);
}

//
// Calculate the number of bits set in each character, for subsequent 
use in comparing
//  to a section of the bitmap.
//
void InitBitsSetArray(register char *p,register ushort *c)
{
  register short count;
  p += (ushort)fInfo.leading*kCharRowBytes;
  count = kNumChars; do {
    register ushort bitcount=0;
    register uchar *q = (uchar *)p;
    register short vCount;
    vCount = lineHeight-fInfo.leading; do {
      register ulong row;       
      BitCount(row,*(ulong *)q,bitcount);
      q += kCharRowBytes;
    } while (--vCount);
//  Following line fudges the density value for characters to account 
for the fact 
//  that the most dense character is significantly less dense than a 
dark section of a
//  bitmap.
    bitcount += bitcount>>1;
    *c++ = bitcount;
    p += kBytesPerBMChar;
  } while (--count);
}

//
// Sort the characters in order of increasing number of bits set (density).
//
void SortBitsSetArray(register ushort *v, 
                      register ushort *c)
{
  register ushort *x;
  register ushort count,val,xVal,newVal;
// Initialize sort order
  count = kNumChars; val = 0; x=c; do {
    *x++ = val;  ++val;
  } while (--count);
// Bidirectional exchange sort is good enough for this small array
  count = kNumChars-1;
  x = c;
  val = *(v+*c);
  do {
    ushort *saveC;
    ushort saveCount;
    xVal = *(c+1);
    newVal = *(v+xVal);
    if (val > /**x*/ newVal) {
//    Swap pointers
      *(c+1) = *c;   *c = xVal;
      if (count < kNumChars-1) {
        saveC=c+1;  saveCount=count;  val = *(v+*c); 
        do {
          xVal = *(c-1);  x = v+xVal;  newVal = *x;
          if (val >= newVal) break;
          *(c-1) = *c;  *c = xVal;   --c;
        } while (++count < kNumChars-1);
        count = saveCount;  c=saveC;  val = *(v+*c);
      } else {
        val = *(v+*c++);
      }
    } else {
      val = newVal;  ++c;
    }
  } while (--count);
}

//
// Initialize a mapping from number of bits set in a character-sized 
section of the
// bitmap to the character used to represent that section.
//
void InitCharPointerArray(register ushort *v, 
     register ushort *c, register ushort *p)
{
  register short count1,count2,count3;
  register short currentVal;
  count2 = kNumChars;
  count1 = -1;
  do {
    currentVal = *(v+*c);
    if (currentVal>count1) {
      count3 = (ushort)(currentVal-count1)/2;
      if (count3) do {
        *p++=*(p-1);
        if (++count1 >= kMaxCharVals) return;
      } while (--count3);
      do {
        *p++=' '+*c;
        if (++count1 >= kMaxCharVals) return;
      } while (currentVal>count1);
    }
    ++c;
  } while (--count2);
  do {
    *p++=*(p-1);
  } while (++count1<kMaxCharVals);
}

short BitMapToText(bitMapPtr,fontName,fontSize,outputFile)
BitMap *bitMapPtr;
Str255 fontName;
unsigned short fontSize;
FILE *outputFile;
{
GrafPort charPort;
GrafPtr savePort;

//
// bitsSet[x] is the number of bits set to 1 in the  representation of 
character ' '+x
// sortedCharP[y]+' ' is the y-th character in order of  increasing number 
of bits set
//
ushort bitsSet[kNumChars],sortedCharP[kNumChars];
//
// charVals[c] is the character to be output for a character size piece 
of the bitmap 
// with c bits set
//
ushort charVals[1+kMaxCharVals];

register ulong *q,*rowP;
register short count,numBitsSet;
register ulong mask;

register uchar *p;
ulong origMask;
ushort lineBytes;
short rCnt,rowBytes,hPix,fontNum,theErr;

  GetFNum(fontName,&fontNum);
  if (0 == fontNum) return (kErr);
  if (!RealFont(fontNum,fontSize)) return (kErr);
  GetPort(&savePort);
  OpenPort(&charPort);
  TextFont(fontNum);
  TextSize(fontSize);
  if (theErr = InitOffscreenBitMap(&charPort))
    return theErr;
//
// Draw characters in bitmap.  Draws them one at a time so we can align 
the characters
// within long words. 
//
  DrawTheChars(&charPort);
  SetPort(savePort);
//  
// Init charVal array of characters to output.
//
  InitBitsSetArray(charPort.portBits.baseAddr,bitsSet);
  SortBitsSetArray(bitsSet,sortedCharP);
  InitCharPointerArray(bitsSet,sortedCharP,charVals);
//
//  Process bitMap.
//
  p = (uchar *)bitMapPtr->baseAddr;
  rowBytes = bitMapPtr->rowBytes;
  lineBytes = rowBytes*lineHeight;
  rCnt = bitMapPtr->bounds.bottom - bitMapPtr->bounds.top;
  hPix = bitMapPtr->bounds.right - bitMapPtr->bounds.left;
//
// Set a mask of charWid characters using a sign-extended shift.
//
  origMask = mask = (ulong)
           ((signed long)0x80000000>>(charWid-1));
//
//  Loop on rows of characters.
//
  do {
    short numBits,bitsThisChunk,bitsToGo,hCnt;
    rowP = (ulong *)p;
    bitsThisChunk = kBitsPerChunk;
    hCnt = hPix;
    numBits = bitsToGo = charWid;
//
//  Loop on chars within current row.
//
    do {
//
//    Count bits set in current char.
//
      numBitsSet=0;
//
//    Loop on pixels in this chunk.
//
      do {
        q = rowP;
        count = lineHeight;
//
//      Count number of bits set in this chunk.
//
        do {
          register ulong ch;
          BitCount(ch,*q & mask,numBitsSet);
          q = (ulong *)((uchar *)q + rowBytes);
        } while (--count);
//
//  Continue processing current char if there are bitsToGo.
//
        if (0 == (bitsThisChunk -= numBits)) {
//        Check for end of row.
          if (hCnt < (bitsThisChunk=kBitsPerChunk))
            bitsThisChunk = hCnt;
          ++rowP;
          if (bitsToGo-=numBits) {
            if (bitsToGo > hCnt) bitsToGo = hCnt;
            mask = origMask << (charWid - bitsToGo);
            numBits = bitsToGo;
          } else {
            mask = origMask;
            break;
          }
        } else if (numBits != charWid) {
          mask = (origMask >> bitsToGo);
          break;
        } else {
          mask >>= numBits;
          break;
        }
      } while (true);  /* break if (0 == bitsToGo) */
      numBits = bitsToGo = charWid;
      if (numBits>bitsThisChunk) numBits= bitsThisChunk;
//
//  Select output character;
//
      if (numBitsSet<kMaxCharVals)
        count = *(charVals+numBitsSet);
      else count = *(charVals+kMaxCharVals);
      putc(count,outputFile);
    } while (0 < (hCnt-=charWid));
    p += lineBytes;
    putc(EOL,outputFile);
    if (0 > rCnt) break;
    if (0 > (rCnt-=lineHeight)) lineHeight += rCnt;
    mask =  origMask;
  } while (true);
  return 0;
}







  
 
AAPL
$567.77
Apple Inc.
+43.02
MSFT
$39.86
Microsoft Corpora
+0.17
GOOG
$525.16
Google Inc.
-1.78

MacTech Search:
Community Search:

Software Updates via MacUpdate

Ember 1.5.1 - Versatile digital scrapboo...
Ember (formerly LittleSnapper) is your digital scrapbook of things that inspire you: websites, photos, apps or other things. Just drag in images that you want to keep, organize them into relevant... Read more
Cyberduck 4.4.4 - FTP and SFTP browser....
Cyberduck is a robust FTP/FTP-TLS/SFTP browser for the Mac whose lack of visual clutter and cleverly intuitive features make it easy to use. Support for external editors and system technologies such... Read more
TechTool Pro 7.0.3 - Hard drive and syst...
TechTool Pro is now 7, and this is the most advanced version of the acclaimed Macintosh troubleshooting utility created in its 20-year history. Micromat has redeveloped TechTool Pro 7 to be fully 64... Read more
OnyX 2.8.5 - Maintenance and optimizatio...
OnyX is a multifunctional utility for OS X. It allows you to verify the startup disk and the structure of its System files, to run miscellaneous tasks of system maintenance, to configure the hidden... Read more
MacFamilyTree 7.1.6 - Create and explore...
MacFamilyTree gives genealogy a facelift: it's modern, interactive, incredibly fast, and easy to use. We're convinced that generations of chroniclers would have loved to trade in their genealogy... Read more
EtreCheck 1.9.9 - For troubleshooting yo...
EtreCheck is a simple little app to display the important details of your system configuration and allow you to copy that information to the Clipboard. It is meant to be used with Apple Support... Read more
TeamViewer 9.0.28116 - Establish remote...
TeamViewer gives you remote control of any computer or Mac over the Internet within seconds, or can be used for online meetings. Find out why more than 200 million users trust TeamViewer! Free for... Read more
DiskAid 6.6.3 - Use your iOS device as a...
DiskAid is the ultimate transfer tool for accessing the iPod, iPhone or iPad directly from the desktop. Access data such as: music, video, photos, contacts, notes, call history, text messages (SMS),... Read more
Viber 4.1.0 - Send messages and make cal...
Viber lets you send free messages and make free calls to other Viber users, on any device and network, in any country! Viber syncs your contacts, messages and call history with your mobile device,... Read more
Apple iOS 7.1.1 - The latest version of...
The latest version of iOS can be downloaded through iTunes. Apple iOS 7 brings an all-new design and all-new features. Simplicity Simplicity is often equated with minimalism. Yet true simplicity is... Read more

Latest Forum Discussions

See All

Pen & Ink Review
Pen & Ink Review By Jennifer Allen on April 24th, 2014 Our Rating: :: CONVENIENT ARTISTRYiPad Only App - Designed for the iPad Pen & Ink is an ideal way to sketch down some visual ideas or simply spark your imagination.   | Read more »
Sonic & All-Stars Racing Transformed...
Sonic & All-Stars Racing Transformed Now Free, to Add New Iconic Characters and Elements Posted by Tre Lawrence on April 24th, 2014 [ | Read more »
Soccer Rally 2 Review
Soccer Rally 2 Review By Carter Dotson on April 24th, 2014 Our Rating: :: GOALKEEPINGUniversal App - Designed for iPhone and iPad Soccer Rally 2 is the most serious vehicular soccer game ever created.   | Read more »
Galaxy Conquerors Review
Galaxy Conquerors Review By Jennifer Allen on April 24th, 2014 Our Rating: :: RETRO SHOOTINGUniversal App - Designed for iPhone and iPad Old school shooting is fun but inaccurate in Galaxy Conquerors.   | Read more »
Yomi Review
Yomi Review By Rob Thomas on April 24th, 2014 Our Rating: :: C-C-C-COMBO BREAKERiPad Only App - Designed for the iPad Round One – Fight! No quarters required for this iOS adaptation of a tabletop adaptation of the arcade fighting... | Read more »
Injustice: Gods Among Us Updated with Ne...
Injustice: Gods Among Us Updated with New Characters, Leaderboards, Gear, and Online Multiplayer Posted by Rob Rich on April 24th, 2014 [ | Read more »
Spin It Review
Spin It Review By Jordan Minor on April 24th, 2014 Our Rating: :: SPIN ME RIGHT ROUNDUniversal App - Designed for iPhone and iPad Spin It has a fine puzzle game model, but its execution lacks energy.   | Read more »
Productivity App NoteSuite is Having its...
Productivity App NoteSuite is Having its Biggest Sale Ever, Just for One Week Posted by Rob Rich on April 24th, 2014 [ permalink ] | Read more »
Wayward Souls Review
Wayward Souls Review By Carter Dotson on April 24th, 2014 Our Rating: :: CARRY ON, WAYWARD SONUniversal App - Designed for iPhone and iPad Wayward Souls is a roguelike-inspired action-RPG that sets a high bar for other games to... | Read more »
The Sandbox Gets Update, Receives New Ca...
The Sandbox Gets Update, Receives New Campaign and New Elements Posted by Tre Lawrence on April 24th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »

Price Scanner via MacPrices.net

Strong iPhone Sales Drive Apple Record March...
Apple on Wednesday announced financial results for its fiscal 2014 second quarter ended March 29, 2014. The Company posted quarterly revenue of $45.6 billion and quarterly net profit of $10.2 billion... Read more
Award-Winning NoteSuite Productivity App is $...
Minneapolis based Theory.io has announced an 80-Percent Markdown NoteSuite for iPad. NoteSuite helps users stay organized by capturing their notes, to-dos and documents in one organized place.... Read more
16GB 1st generation iPad mini available for $...
Radio Shack has a select number of refurbished 1st generation 16GB WiFi iPad minis available for $199.99 on their online store. Choose free shipping or free ship-to-store. We expect these to sell out... Read more
13-inch 2.5GHz MacBook Pro on sale for $100 o...
B&H Photo has the 13″ 2.5GHz MacBook Pro on sale for $1099 including free shipping plus NY sales tax only. Their price is $100 off MSRP. Read more
iPad Sales “Lull” A Reality Correction Of Unm...
I have lots of time for Jean-Louis Gassée, the former Apple Computer executive (1981 to 1990) who succeeded Steve Jobs as head of Macintosh development when the latter was dismissed in 1985. Mr.... Read more
Apple Makes OS X Betas Available To All – Wit...
Apple’s OS X Beta Seed Program, which lets you install the latest pre-release builds, try it out, and submit your feedback, is now open to anyone who wants to sign on rather than to developers and... Read more
Apple Releases iOS 7.1.1 Update
The latest iOS 7.1.1 update contains improvements, bug fixes and security updates, including: • Further improvements to Touch ID fingerprint recognition • Fixes a bug that could impact keyboard... Read more
Logitech Announces Thinner, Lighter, More Fle...
Logitech has announced an update to its Ultrathin for iPad Air, iPad mini and iPad mini with Retina display, improving the flexibility and design of its award-winning predecessor with an even thinner... Read more
Logitech Introduces Hinge, Big Bang and Turna...
Logitech has announced expansion of its tablet product line with three new cases – the Logitech Hinge, the Logitech Big Bang and the Logitech Turnaround – each for the iPad Air, iPad mini and iPad... Read more
WaterField’s Rough Rider Leather Messenger Ba...
WaterField Designs have announced the new 15-inch size of their popular Rough Rider leather messenger bag, a vintage-looking bag that combines Old West charm and ruggedness with distinctly modern... Read more

Jobs Board

*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
Position Opening at *Apple* - Apple (United...
…customers purchase our products, you're the one who helps them get more out of their new Apple technology. Your day in the Apple Store is filled with a range of Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
*Apple* Inc. Research Data Specialist - Appl...
…of Worldwide Market Research & Intelligence. The team is responsible for conducting Apple branded consumer market research. It is also responsible for analyzing data Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.