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
$94.38
Apple Inc.
+0.44
MSFT
$44.73
Microsoft Corpora
-0.11
GOOG
$594.14
Google Inc.
+4.67

MacTech Search:
Community Search:

Software Updates via MacUpdate

Macs Fan Control 1.1.12 - Monitor and co...
Macs Fan Control allows you to monitor and control almost any aspect of your computer's fans, with support for controlling fan speed, temperature sensors pane, menu-bar icon, and autostart with... Read more
A Better Finder Rename 9.37 - File, phot...
A Better Finder Rename is the most complete renaming solution available on the market today. That's why, since 1996, tens of thousands of hobbyists, professionals and businesses depend on A Better... Read more
MacBook Air EFI Firmware Update 2.9 - Fo...
MacBook Air EFI Firmware Update is recommended for MacBook Air (Mid 2011) models. This update addresses an issue where systems may take longer to wake from sleep than expected and fixes a rare issue... Read more
FileZilla 3.9.0.1 - Fast and reliable FT...
FileZilla (ported from Windows) is a fast and reliable FTP client and server with lots of useful features and an intuitive interface.Version 3.9.0.1: MSW: Fix installation issue with locked DLLs... Read more
OS X Yosemite 10.10 DP4 - Developer Prev...
Note: This is a Developer Preview. You must be a registered Apple Mac Developer to download this update. OS X Yosemite is Apple's newest operating system for Mac. An elegant design that feels... Read more
FinderPop 2.5.6 - Classic Mac utility, n...
FinderPop is a Universal preference pane that extends OS X's contextual menus using a FinderPop Items folder much as the Apple Menu Items folder used to do for the Apple menu. It has other features... Read more
SpiderOak 5.1.7 - Secure cloud backup, s...
SpiderOak is a multi-platform secure online backup, storage, access, and sharing solution engineered for the consumer and small businesses. You must first sign up to use SpiderOak. Running natively... Read more
Espionage 3.6 - Simple, state of the art...
Espionage offers state-of-the-art encryption and plausible deniability for your confidential data. Sometimes, encrypting your data isn't enough to protect it. That's why Espionage 3 goes beyond data... Read more
calibre 1.45.0 - Complete e-library mana...
Calibre is a complete e-book library manager. Organize your collection, convert your books to multiple formats, and sync with all of your devices. Let Calibre be your multi-tasking digital... Read more
iFFmpeg 4.3.1 - Convert multimedia files...
iFFmpeg is a graphical front-end for FFmpeg, a command-line tool used to convert multimedia files between formats. The command line instructions can be very hard to master/understand, so iFFmpeg does... Read more

Latest Forum Discussions

See All

Celebrate Summer With a Cat in the Hat L...
Celebrate Summer With a Cat in the Hat Learning Library Sale Posted by Ellis Spice on July 22nd, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
MyTaskList Review
MyTaskList Review By Jennifer Allen on July 22nd, 2014 Our Rating: :: EFFECTIVE IF PLAINUniversal App - Designed for iPhone and iPad It’s not the most stylish of task management apps, but MyTaskList has all the features you could... | Read more »
FlyCraft Herbie: Crazy Machines Review
FlyCraft Herbie: Crazy Machines Review By Jennifer Allen on July 22nd, 2014 Our Rating: :: TRICKY FLYINGUniversal App - Designed for iPhone and iPad A tough game of careful thrusting and navigation, FlyCraft Herbie: Crazy Machines... | Read more »
MTN Review
MTN Review By Jessica Fisher on July 22nd, 2014 Our Rating: :: ADORABLE, SERENE, AND AMUSINGUniversal App - Designed for iPhone and iPad MTN is an adorable, talking pet mountain that is less game and more zen garden.   | Read more »
Fly High with Ninja UP! Now Available o...
Fly High with Ninja UP! Now Available on the App Store Posted by Jessica Fisher on July 22nd, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Bio Inc. Review
Bio Inc. Review By Nadia Oxford on July 22nd, 2014 Our Rating: :: SICKENING - IN A COMPELLING WAYUniversal App - Designed for iPhone and iPad Bio Inc is about orchestrating the medical destruction of a single person. If that doesn’... | Read more »
HELMUT Review
HELMUT Review By Andrew Fisher on July 21st, 2014 Our Rating: :: TRUNDLE SIMULATOR 2014Universal App - Designed for iPhone and iPad HELMUT is a fun, fleeting time-sink that offers a momentary distraction and nothing else.   | Read more »
Walkr Review
Walkr Review By Jennifer Allen on July 21st, 2014 Our Rating: :: ORIGINAL WALKINGiPhone App - Designed for the iPhone, compatible with the iPad Walking is a bit more exciting thanks to this planet building/discovering sim reliant... | Read more »
Zombie Commando Review
Zombie Commando Review By Jennifer Allen on July 21st, 2014 Our Rating: :: MINDLESS SLAUGHTERUniversal App - Designed for iPhone and iPad Briefly fun but ultimately forgettable, Zombie Commando will scratch an itch then be... | Read more »
Swords & Poker Adventures Review
Swords & Poker Adventures Review By Jennifer Allen on July 21st, 2014 Our Rating: :: SOULLESS POKER PLAYUniversal App - Designed for iPhone and iPad Swords & Poker Adventures is a mishmash of Poker and RPGing, but it lacks... | Read more »

Price Scanner via MacPrices.net

Apple restocks refurbished Mac minis for up t...
The Apple Store has restocked Apple Certified Refurbished Mac minis for up to $150 off the cost of new models. Apple’s one-year warranty is included with each mini, and shipping is free: - 2.5GHz Mac... Read more
Twelve South HiRise For MacBook – Height-Adju...
If you use your MacBook as a workhorse desktop substitute, as many of us do, a laptop stand combined with an external keyboard and pointing device are pretty much obligatory if you want to avoid... Read more
Why The Mac Was Not Included In The Apple/IBM...
TUAW’s Yoni Heisler cites Fredrick Paul of Network World whoi blogged last week that the Mac’s conspicuous absence from Apple and IBM’s landmark partnership agreement represents a huge squandered... Read more
Save $100 on 13-inch Retina MacBook Pros, plu...
Adorama has 13″ Retina MacBook Pros on sale for $100 off MSRP. Shipping is free, and Adorama charges sales tax in NY & NJ only: - 13″ 2.4GHz/128GB MacBook Pro with Retina Display: $1199 - 13″ 2.... Read more
Blurr it 2.3 for iOS – Quickly Blurs Selected...
Hyderabad, India based TouchLabs has announced a new update of Blurr it 2.3, their photography app for iOS users. Blurr it allows you to blur part of the image to hide potentially sensitive or... Read more
MacBook Airs on sale for $100 off MSRP, start...
Best Buy has the new 2014 MacBook Airs on sale for up to $100 off MSRP on their online store. Choose free home shipping or free local store pickup (if available). Prices valid for online orders only... Read more
Amazon Announces Kindle Unlimited: Unlimited...
Amazon.com has introduced Kindle Unlimited — a new subscription service which allows customers to freely read as much as they want from over 600,000 Kindle books, and listen as much as they want to... Read more
New Linksys Wireless Range Extenders Boost Wi...
Linksys has announced its new lineup of Linksys Wi-Fi Range Extenders. Consumers often experience a weak wireless signal in some parts of their house or apartment caused by blocking elements such as... Read more
MacBook Airs available starting at $719
The Apple Store has Apple Certified Refurbished 2013 & 2012 MacBook Airs in stock today starting at $719. An Apple one-year warranty is included with each MacBook, and shipping is free: 2013... Read more
Get the best deals on iPad minis with Apple r...
The Apple Store has Certified Refurbished 2nd generation iPad minis with Retina Displays available for up to $130 off the cost of new models, starting at $339. Apple’s one-year warranty is included... Read more

Jobs Board

*Apple* Computer Technician - Fairfield Coun...
Company DescriptionWe are an Apple Authorized Sales and Service Provider. We have been selling and servicing Apple computers in the Fairfield County area for over 20 Read more
*Apple* Computer Technician - Fairfield Coun...
Company DescriptionWe are an Apple Authorized Sales and Service Provider. We have been selling and servicing Apple computers in the Fairfield County area for over 20 Read more
Mac Expert - *Apple* Online Store Mexico -...
…MUST be fluent in English and Spanish to be considered for this position At Apple , we believe that hard work, a fun environment, creativity and innovation fuel the Read more
*Apple* Computer Technician - Fairfield Coun...
Company DescriptionWe are an Apple Authorized Sales and Service Provider. We have been selling and servicing Apple computers in the Fairfield County area for over 20 Read more
Mac Expert - *Apple* Online Store - Apple (...
**Job Summary** At Apple , we believe that hard work, a fun environment, creativity and innovation fuel the ultimate customer experience. We believe each customer Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.