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

Apple macOS Sierra 10.12.3 - The latest...
With Apple macOS Sierra, Siri makes its debut on Mac, with new features designed just for the desktop. Your Mac works with iCloud and your Apple devices in smart new ways, and intelligent... Read more
Lyn 1.8.5 - Lightweight image browser an...
Lyn is a fast, lightweight image browser and viewer designed for photographers, graphic artists, and Web designers. Featuring an extremely versatile and aesthetically pleasing interface, it delivers... Read more
iClock Pro 3.4.7 - Customize your menuba...
iClock Pro is a menu bar replacement clock for Apple's default clock. iClock Pro is an update, total rewrite and improvement to the popular iClock. Have the day, date and time in different fonts and... Read more
Opera 42.0.2393.137 - High-performance W...
Opera is a fast and secure browser trusted by millions of users. With the intuitive interface, Speed Dial and visual bookmarks for organizing favorite sites, news feature with fresh, relevant content... Read more
Apple Security Update 2016-003 Supplemen...
Apple Security Update is recommended for all users and improves the security of OS X. For detailed information about the security content of this update, please visit: http://support.apple.com/kb/... Read more
Apple iOS 10.2.1 - The latest version of...
iOS 10 is the biggest release of iOS ever. A massive update to Messages brings the power of the App Store to your conversations and makes messaging more personal than ever. Find your route with... Read more
BetterTouchTool 1.992 - Customize Multi-...
BetterTouchTool adds many new, fully customizable gestures to the Magic Mouse, Multi-Touch MacBook trackpad, and Magic Trackpad. These gestures are customizable: Magic Mouse: Pinch in / out (zoom... Read more
Viber 6.5.5 - 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, so... Read more
Lyn 1.8.5 - Lightweight image browser an...
Lyn is a fast, lightweight image browser and viewer designed for photographers, graphic artists, and Web designers. Featuring an extremely versatile and aesthetically pleasing interface, it delivers... Read more
Apple iOS 10.2.1 - The latest version of...
iOS 10 is the biggest release of iOS ever. A massive update to Messages brings the power of the App Store to your conversations and makes messaging more personal than ever. Find your route with... Read more

Clash Royale gets some serious balance u...
| Read more »
Ironhide Game Studio prepares for a busy...
Kingdom Rush breathed fresh life into the tired tower defense genre way back in 2012. The game was a robust challenge that somehow managed to lift you up, rather than leaving you feeling crushed and hopeless. The rich array of unit types and... | Read more »
Collect pets and sling arrows in Arcane...
Mobile gaming is a crowded market, but regular updates are a good way to keep us attention-short players keen. The brand new content in Arcane Online is a prime example. Published by Japanese developer Gala, Arcane Online is a fantasy MMO that... | Read more »
Super Mario Run dashes onto Android in M...
Super Mario Run was one of the biggest mobile launches in 2016 before it was met with a lukewarm response by many. While the game itself plays a treat, it's pretty hard to swallow the steep price for the full game. With that said, Android users... | Read more »
WarFriends Beginner's Guide: How to...
Chillingo's new game, WarFriends, is finally available world wide, and so far it's a refreshing change from common mobile game trends. The game's a mix of tower defense, third person shooter, and collectible card game. There's a lot to unpack here... | Read more »
Super Gridland (Entertainment)
Super Gridland 1.0 Device: iOS Universal Category: Entertainment Price: $1.99, Version: 1.0 (iTunes) Description: Match. Build. Survive. "exquisitely tuned" - Rock Paper Shotgun No in-app purches, and no ads! | Read more »
Red's Kingdom (Games)
Red's Kingdom 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: Mad King Mac has kidnapped your father and stolen your golden nut! Solve puzzles and battle goons as you explore and battle your... | Read more »
Turbo League Guide: How to tame the cont...
| Read more »
Fire Emblem: Heroes coming to Google Pla...
Nintendo gave us our first look at Fire Emblem: Heroes, the upcoming mobile Fire Emblem game the company hinted at last year. Revealed at the Fire Emblem Direct event held today, the game will condense the series' tactical RPG combat into bite-... | Read more »
ReSlice (Music)
ReSlice 1.0 Device: iOS Universal Category: Music Price: $9.99, Version: 1.0 (iTunes) Description: Audio Slice Machine Slice your audio samples with ReSlice and create flexible musical atoms which can be triggered by MIDI notes or... | Read more »

Price Scanner via MacPrices.net

Deal alert! 13-inch 2.0GHz MacBook Pros for $...
B&H Photo has the new 2016 13″ 2.0GHz non-Touch Bar MacBook Pros in stock today and on sale for $225 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 13″ 2.0GHz MacBook Pro... Read more
Free LibreOffice Portable 5.2.4 Complete Offi...
PortableApps.com and The Document Foundation have announce the release of LibreOffice Portable 5.2.4. LibreOffice Portable is an Open Source full-featured office suite — including a word processor,... Read more
Apple Planning Three New Tablets For 2017 – D...
Digitimes’ Rebecca Kuo and Joseph Tsai say that unnamed insider sources report Apple having three new tablets in the pipeline for 2017 release: a 9.7-inch model with a friendly price range, a new mid... Read more
Roundup of 15-inch Touch Bar MacBook Pro sale...
B&H Photo has the new 2016 15″ Apple Touch Bar MacBook Pros in stock today and on sale for up to $150 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 15″ 2.7GHz Touch Bar... Read more
Apple refurbished iPad Pros available for up...
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
16GB iPad Air 2, Apple refurbished, available...
Apple has Certified Refurbished 16GB iPad Air 2s available for $319 including free shipping. A standard Apple one-year is included. Their price is $60 off original MSRP for this model. Read more
Apple iMacs on sale for up to $120 off MSRP
B&H Photo has 21″ and 27″ Apple iMacs on sale for up to $120 off MSRP, each including free shipping plus NY sales tax only: - 27″ 3.3GHz iMac 5K: $2199 $100 off MSRP - 27″ 3.2GHz/1TB Fusion iMac... Read more
Apple refurbished Apple TVs available for up...
Apple has Certified Refurbished 32GB and 64GB Apple TVs available for up to $30 off the cost of new models. Apple’s standard one-year warranty is included with each model, and shipping is free: -... Read more
Save up to $350 with Apple Certified Refurbis...
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
2015 12-inch Retina MacBooks, Apple refurbish...
Apple has Certified Refurbished 2015 12″ Retina MacBooks available for up to $410 off original MSRP. Apple will include a standard one-year warranty with each MacBook, and shipping is free. The... Read more

Jobs Board

*Apple* & PC Desktop Support Technician...
Apple & PC Desktop Support Technician job in Manhattan, NY Introduction: We have immediate job openings for several Desktop Support Technicians with one of our most Read more
*Apple* & PC Desktop Support Technician...
Apple & PC Desktop Support Technician job in Stamford, CT We have immediate job openings for several Desktop Support Technicians with one of our most well-known 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* Site Security Manager - Apple (Unite...
# Apple Site Security Manager Job Number: 54692472 Culver City, California, United States Posted: Jan. 19, 2017 Weekly Hours: 40.00 **Job Summary** The Apple Read more
*Apple* macOS Systems Integration Administra...
…most exceptional support available in the industry. SCI is seeking an Junior Apple macOS systems integration administrator that will be responsible for providing Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.