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

FotoMagico 5.6.12 - Powerful slideshow c...
FotoMagico lets you create professional slideshows from your photos and music with just a few, simple mouse clicks. It sports a very clean and intuitive yet powerful user interface. High image... Read more
OmniGraffle Pro 7.12.1 - Create diagrams...
OmniGraffle Pro helps you draw beautiful diagrams, family trees, flow charts, org charts, layouts, and (mathematically speaking) any other directed or non-directed graphs. We've had people use... Read more
beaTunes 5.2.1 - Organize your music col...
beaTunes is a full-featured music player and organizational tool for music collections. How well organized is your music library? Are your artists always spelled the same way? Any R.E.M. vs REM?... Read more
HandBrake 1.3.0 - Versatile video encode...
HandBrake is a tool for converting video from nearly any format to a selection of modern, widely supported codecs. Features Supported Sources VIDEO_TS folder, DVD image or real DVD (unencrypted... Read more
Macs Fan Control 1.5.1.6 - Monitor and c...
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
TunnelBear 3.9.3 - Subscription-based pr...
TunnelBear is a subscription-based virtual private network (VPN) service and companion app, enabling you to browse the internet privately and securely. Features Browse privately - Secure your data... Read more
calibre 4.3.0 - Complete e-book library...
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 librarian... Read more
Lyn 1.13 - Lightweight image browser and...
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
Visual Studio Code 1.40.0 - Cross-platfo...
Visual Studio Code provides developers with a new choice of developer tool that combines the simplicity and streamlined experience of a code editor with the best of what developers need for their... Read more
OmniGraffle 7.12.1 - Create diagrams, fl...
OmniGraffle helps you draw beautiful diagrams, family trees, flow charts, org charts, layouts, and (mathematically speaking) any other directed or non-directed graphs. We've had people use Graffle to... Read more

Latest Forum Discussions

See All

The House of Da Vinci 2 gets a new gamep...
The House of Da Vinci launched all the way back in 2017. Now, developer Blue Brain Games is gearing up to deliver a second dose of The Room-inspired puzzling. Some fresh details have now emerged, alongside the game's first official trailer. [Read... | Read more »
Shoot 'em up action awaits in Battl...
BattleBrew Productions has just introduced another entry into its award winning, barrelpunk inspired, BattleSky Brigade series. Whilst its previous title BattleSky Brigade TapTap provided fans with idle town building gameplay, this time the... | Read more »
Arcade classic R-Type Dimensions EX blas...
If you're a long time fan of shmups and have been looking for something to play lately, Tozai Games may have just released an ideal game for you on iOS. R-Type Dimensions EX brings the first R-Type and its sequel to iOS devices. [Read more] | Read more »
Intense VR first-person shooter Colonicl...
Our latest VR obsession is Colonicle, an intense VR FPS, recently released on Oculus and Google Play, courtesy of From Fake Eyes and Goboogie Games. It's a pulse-pounding multiplayer shooter which should appeal to genre fanatics and newcomers alike... | Read more »
PUBG Mobile's incoming update bring...
PUGB Mobile's newest Royale Pass season they're calling Fury of the Wasteland arrives tomorrow and with it comes a fair chunk of new content to the game. We'll be seeing a new map, weapon and even a companion system. [Read more] | Read more »
PSA: Download Bastion for free, but wait...
There hasn’t been much news from Supergiant Games on mobile lately regarding new games, but there’s something going on with their first game. Bastion released on the App Store in 2012, and back then it was published by Warner Bros. This Warner... | Read more »
Apple Arcade: Ranked - 51+ [Updated 11.5...
This is Part 2 of our Apple Arcade Ranking list. To see part 1, go here. 51. Patterned [Read more] | Read more »
NABOKI is a blissful puzzler from acclai...
Acclaimed developer Rainbow Train's latest game, NABOKI, is set to launch for iOS, Android, and Steam on November 13th. It's a blissful puzzler all about taking levels apart in interesting, inventive ways. [Read more] | Read more »
A Case of Distrust is a narrative-driven...
A Case of Distrust a narrative-focused mystery game that's set in the roaring 20s. In it, you play as a detective with one of the most private eye sounding names ever – Phyllis Cadence Malone. You'll follow her journey in San Francisco as she... | Read more »
Brown Dust’s October update offers playe...
October is turning out to be a productive month for the Neowiz team, and a fantastic month to be a Brown Dust player. First, there was a crossover event with the popular manga That Time I Got Reincarnated as a Slime. Then, there was the addition of... | Read more »

Price Scanner via MacPrices.net

Score a 37% discount on Apple Smart Keyboards...
Amazon has Apple Smart Keyboards for current-generation 10″ iPad Airs and previous-generation 10″ iPad Pros on sale today for $99.99 shipped. That’s a 37% discount over Apple’s regular MSRP of $159... Read more
Apple has refurbished 2019 13″ 1.4GHz MacBook...
Apple has a full line of Certified Refurbished 2019 13″ 1.4GHz 4-Core Touch Bar MacBook Pros available starting at $1099 and up to $230 off MSRP. Apple’s one-year warranty is included, shipping is... Read more
2019 13″ 1.4GHz 4-Core MacBook Pros on sale f...
Amazon has new 2019 13″ 1.4GHz 4-Core Touch Bar MacBook Pros on sale for $150-$200 off Apple’s MSRP. These are the same MacBook Pros sold by Apple in its retail and online stores: – 2019 13″ 1.4GHz/... Read more
11″ 64GB Gray WiFi iPad Pro on sale for $674,...
Amazon has the 11″ 64GB Gray WiFi iPad Pro on sale today for $674 shipped. Their price is $125 off MSRP for this iPad, and it’s the lowest price available for the 64GB model from any Apple reseller. Read more
2019 15″ MacBook Pros available for up to $42...
Apple has a full line of 2019 15″ 6-Core and 8-Core Touch Bar MacBook Pros, Certified Refurbished, available for up to $420 off the cost of new models. Each model features a new outer case, shipping... Read more
2019 15″ MacBook Pros on sale this week for $...
Apple resellers B&H Photo and Amazon are offering the new 2019 15″ MacBook Pros for up to $300 off Apple’s MSRP including free shipping. These are the same MacBook Pros sold by Apple in its... Read more
Sunday Sale: AirPods with Wireless Charging C...
B&H Photo has Apple AirPods with Wireless Charging Case on sale for $159.99 through 11:59pm ET on November 11th. Their price is $40 off Apple’s MSRP, and it’s the lowest price available for these... Read more
Details of Sams Club November 9th one day App...
Through midnight Saturday night (November 9th), Sams Club online has several Apple products on sale as part of their One Day sales event. Choose free shipping or free local store pickup (if available... Read more
Sprint is offering the 64GB Apple iPhone 11 f...
Sprint has the new 64GB iPhone 11 available for $15 per month for new lines. That’s about 50% off their standard monthly lease of $29.17. Over is valid until November 24, 2019. The fine print: “Lease... Read more
New Sprint November iPhone deal: Lease one iP...
Switch to Sprint and purchase an Apple iPhone 11, 11 Pro, or 11 Pro Max, and get a second 64GB iPhone 11 for free. Requires 2 new lines or 1 upgrade-eligible line and 1 new line. Offer is valid from... Read more

Jobs Board

*Apple* Mobility Pro - Best Buy (United Stat...
**746087BR** **Job Title:** Apple Mobility Pro **Job Category:** Store Associates **Store NUmber or Department:** 000319-Harlem & Irving-Store **Job Description:** Read more
Best Buy *Apple* Computing Master - Best Bu...
**743392BR** **Job Title:** Best Buy Apple Computing Master **Job Category:** Store Associates **Store NUmber or Department:** 001171-Southglenn-Store **Job Read more
Best Buy *Apple* Computing Master - Best Bu...
**746015BR** **Job Title:** Best Buy Apple Computing Master **Job Category:** Sales **Store NUmber or Department:** 000372-Federal Way-Store **Job Description:** Read more
*Apple* Mobility Pro - Best Buy (United Stat...
**744658BR** **Job Title:** Apple Mobility Pro **Job Category:** Store Associates **Store NUmber or Department:** 000586-South Hills-Store **Job Description:** At Read more
Best Buy *Apple* Computing Master - Best Bu...
**741552BR** **Job Title:** Best Buy Apple Computing Master **Job Category:** Sales **Store NUmber or Department:** 000277-Metcalf-Store **Job Description:** **What Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.