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;
}







  
 

Community Search:
MacTech Search:

Software Updates via MacUpdate

NeoFinder 7.4.1 - Catalog your external...
NeoFinder (formerly CDFinder) rapidly organizes your data, either on external or internal disks, or any other volumes. It catalogs and manages all your data, so you stay in control of your data... Read more
Tunnelblick 3.8.0 - GUI for OpenVPN.
Tunnelblick is a free, open source graphic user interface for OpenVPN on OS X. It provides easy control of OpenVPN client and/or server connections. It comes as a ready-to-use application with all... Read more
Tweetbot 3 for Twitter 3.3.1 - Popular T...
Tweetbot is a full-featured OS X Twitter client with a lot of personality. Whether it's the meticulously-crafted interface, sounds and animation, or features like multiple timelines and column views... Read more
Monosnap 3.5.9 - Versatile screenshot ut...
Monosnap lets you capture screenshots, share files, and record video and .gifs. Features Capture Capture full screen, just part of the screen, or a selected window Make your crop area pixel... Read more
Monosnap 3.5.9 - Versatile screenshot ut...
Monosnap lets you capture screenshots, share files, and record video and .gifs. Features Capture Capture full screen, just part of the screen, or a selected window Make your crop area pixel... Read more
Tweetbot 3 for Twitter 3.3.1 - Popular T...
Tweetbot is a full-featured OS X Twitter client with a lot of personality. Whether it's the meticulously-crafted interface, sounds and animation, or features like multiple timelines and column views... Read more
Tunnelblick 3.8.0 - GUI for OpenVPN.
Tunnelblick is a free, open source graphic user interface for OpenVPN on OS X. It provides easy control of OpenVPN client and/or server connections. It comes as a ready-to-use application with all... Read more
Bookends 13.2.5 - Reference management a...
Bookends is a full-featured bibliography/reference and information-management system for students and professionals. Bookends uses the cloud to sync reference libraries on all the Macs you use.... Read more
Quicken 2019 5.11.2 - Complete personal...
Quicken makes managing your money easier than ever. Whether paying bills, upgrading from Windows, enjoying more reliable downloads, or getting expert product help, Quicken's new and improved features... Read more
Bookends 13.2.5 - Reference management a...
Bookends is a full-featured bibliography/reference and information-management system for students and professionals. Bookends uses the cloud to sync reference libraries on all the Macs you use.... Read more

Latest Forum Discussions

See All

Void Tyrant guide - Tips and tricks for...
Void Tyrant continues to get a lot of play in these parts. Probably because the game is just so deep and varied. The next stop on our guide series for Void Tyrant is class-specific guides. First up is the Knight, as it’s the first class anyone has... | Read more »
Summon beasts and battle evil in epic re...
Imagine a tale of conlict between factions of good and evil, where rogueish heroes summon beasts to aid them in them in warfare and courageously battle dragons over fields of scorched earth and brimstone - that's exactly the essence of epic fantasy... | Read more »
Upcoming visual novel Arranged shines a...
If you’re in the market for a new type of visual novel designed to inform and make you think deeply about its subject matter, then Arranged by Kabuk Games could be exactly what you’re looking for. It’s a wholly unique take on marital traditions in... | Read more »
TEPPEN guide - The three best decks in T...
TEPPEN’s unique take on the collectible card game genre is exciting. It’s just over a week old, but that isn’t stopping lots of folks from speculating about the long-term viability of the game, as well as changes and additions that will happen over... | Read more »
Intergalactic puzzler Silly Memory serve...
Recently released matching puzzler Silly Memory is helping its fans with their intergalactic journeys this month with some very special offers on in-app purchases. In case you missed it, Silly Memory is the debut title of French based indie... | Read more »
TEPPEN guide - Tips and tricks for new p...
TEPPEN is a wild game that nobody asked for, but I’m sure glad it exists. Who would’ve thought that a CCG featuring Capcom characters could be so cool and weird? In case you’re not completely sure what TEPPEN is, make sure to check out our review... | Read more »
Dr. Mario World guide - Other games that...
We now live in a post-Dr. Mario World world, and I gotta say, things don’t feel too different. Nintendo continues to squirt out bad games on phones, causing all but the most stalwart fans of mobile games to question why they even bother... | Read more »
Strategy RPG Brown Dust introduces its b...
Epic turn-based RPG Brown Dust is set to turn 500 days old next week, and to celebrate, Neowiz has just unveiled its biggest and most exciting update yet, offering a host of new rewards, increased gacha rates, and a brand new feature that will... | Read more »
Dr. Mario World is yet another disappoin...
As soon as I booted up Dr. Mario World, I knew I wasn’t going to have fun with it. Nintendo’s record on phones thus far has been pretty spotty, with things trending downward as of late. [Read more] | Read more »
Retro Space Shooter P.3 is now available...
Shoot-em-ups tend to be a dime a dozen on the App Store, but every so often you come across one gem that aims to shake up the genre in a unique way. Developer Devjgame’s P.3 is the latest game seeking to do so this, working as a love letter to the... | Read more »

Price Scanner via MacPrices.net

Apple’s $1489 clearance price on refurbished...
Apple has Certified Refurbished 2018 13″ 2.3GHz 4-Core Touch Bar MacBook Pros available starting at $1489. Apple’s one-year warranty is included, shipping is free, and each MacBook has a new outer... Read more
New 2019 13″ 2.4GHz 4-Core MacBook Pros on sa...
Apple resellers B&H Photo and Amazon are offering the new 2019 13″ 2.4GHz 4-Core Touch Bar MacBook Pros for $150 off Apple’s MSRP. These are the same MacBook Pros sold by Apple in its retail and... Read more
B&H drops prices another $50 on clearance...
B&H Photo has dropped prices on clearance 2018 13″ MacBook Airs by a further $50 with models now available for $250 off Apple’s original MSRP. Overnight shipping, or expedited shipping, is free... Read more
Find the best sales & lowest prices on Ap...
Our Apple award-winning price trackers are the best place to look for the best sales and lowest prices on Apple gear. Scan our price trackers for the latest information on sales, bundles, and... Read more
Apple has clearance 2018 13″ MacBook Airs now...
Apple has Certified Refurbished 2018 13″ MacBook Airs available starting at only $849. Each MacBook features a new outer case, comes with a standard Apple one-year warranty, and is shipped free. The... Read more
Save $400 on the 8-Core iMac Pro today at Ama...
Amazon has the base 8-core iMac Pro on sale today for $4599 including free shipping. Their price is $400 off Apple’s MSRP, and it’s the currently lowest price available for an iMac Pro. For the... Read more
Flash sale! New 11″ 1TB WiFi iPad Pros for th...
Amazon has the 11″ 1TB WiFi iPad Pro on sale today for only $1199.99 including free shipping. Their price is $350 off Apple’s MSRP for this model, and it’s the lowest price ever for a 1TB 11″ iPad... Read more
Weekend Deal: 2018 13″ MacBook Airs starting...
B&H Photo has clearance 2018 13″ MacBook Airs available starting at only $999 with all models now available for $200 off Apple’s original MSRP. Overnight shipping, or expedited shipping, is free... Read more
Apple has clearance 10.5″ iPad Pros available...
Apple has Certified Refurbished 2017 10.5″ iPad Pros available starting at $469. An Apple one-year warranty is included with each iPad, outer shells are new, and shipping is free: – 64GB 10″ iPad Pro... Read more
Apple restocks refurbished iPad mini 4 models...
Apple has restocked Certified Refurbished 32GB iPad mini 4 WiFi models for $229 shipped. That’s $70 off original MSRP for the iPad mini 4. Space Gray, Silver, and Gold colors are available. Read more

Jobs Board

Best Buy *Apple* Computing Master - Best Bu...
**711495BR** **Job Title:** Best Buy Apple Computing Master **Job Category:** Store Associates **Location Number:** 000882-Waterfront-Store **Job Description:** The Read more
Best Buy *Apple* Computing Master - Best Bu...
**711597BR** **Job Title:** Best Buy Apple Computing Master **Job Category:** Sales **Location Number:** 000873-Colma CA-Store **Job Description:** **What does a Read more
Best Buy *Apple* Computing Master - Best Bu...
**711346BR** **Job Title:** Best Buy Apple Computing Master **Job Category:** Store Associates **Location Number:** 001095-Chesterfield-Store **Job Description:** Read more
Best Buy *Apple* Computing Master - Best Bu...
**704899BR** **Job Title:** Best Buy Apple Computing Master **Job Category:** Sales **Location Number:** 000135-Pleasant Hill-Store **Job Description:** **What does Read more
Best Buy *Apple* Computing Master - Best Bu...
**707083BR** **Job Title:** Best Buy Apple Computing Master **Job Category:** Sales **Location Number:** 000045-Rockford-Store **Job Description:** **What does a Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.