TweetFollow Us on Twitter

PROGRAMMER's CHALLENGE

Volume Number: 18 (2002)
Issue Number: 8
Column Tag: PROGRAMMER's CHALLENGE

PROGRAMMER's CHALLENGE

by Bob Boonstra

Endgame

The Chess players among you have another opportunity to excel this month. Back in 1995 (have I really been writing this column for that long?), we had a Challenge that required readers to identify all possible chess positions from a given board position. Gary Beith won that Challenge, and you might want to refer back to his solution when thinking about this month's problem, which invites you to solve the chess end game.

This month's problem is formulated as a C++ class. The prototype for the code you should write is:

typedef enum {
   kEmpty=0, kPawn, kKnight, kBishop, kRook, kQueen, kKing
} ChessPiece;
typedef enum {
   kNone=0,kWhite=1, kBlack
} Player;
typedef struct Square {
   ChessPiece piece;
   Player player;
} Square;
typedef struct PieceLocation {
   char row;
   char col;
} PieceLocation;
typedef Square Board[8][8];
   /* indexed as [row][col] */
   /* white start row is 0 */ 
   /* columns numbered left to right viewed from row 0 */
typedef struct Move {
   Board board;
      /* board before move is made */
   Player playerMoving;
      /* which player is making this move */
   PieceLocation pieceBeingMoved;
      /* which piece is being moved */
   PieceLocation destination;
      /* where is pieceBeingMoved being moved to */
   Move *alternativeMove;
      /* list pointer for alternative moves by playerMoving; 
         NULL if no more alternatives */
   Move *subsequentMove;
      /* subsequent move in this move tree, made by opponent to playerMoving,
         NULL if no subsequent move is possible */
   bool moveIsCapture;
      /* true if this move is a capture */
   bool moveIsCheck;
      /* true if this move places the opponent in check (but not mate) */
   bool moveIsMate;
      /* true if this move mates the opponent */
   bool moveIsPromotion;
      /* true if this move promotes a pawn at the 8th rank */
   ChessPiece pieceAfterPromotion;
      /* valid only if moveIsPromotion is true, set to value of new piece */
} Move;
class EndGame {
   Board board;
   Move *initialMove;
   /* add other private members as you see fit */
   ~EndGame(void) {
      /* your destructor code goes here */
   }
public:
   EndGame(Board initialBoard, Player playerToMove) {
      /* your constructor code goes here */
   }
   Move *Solve() {
      /* your code goes here */
      return moveTree;
   }
};

The constructor for your EndGame class is provided with the initial board configuration (board) and the identity of the player who moves first (playerToMove). When your Solve method is called, your job is to choose an initial move that leads to checkmate in the minimum number of moves possible. You also need to compute the possible opposing moves with which the other player might respond, and your response to each of those moves, and so on, until each branch of the tree results in checkmate.

Either your constructor or the Solve routine should allocate storage for your first move (moveTree). The Move structure contains the board configuration prior to making the move, the identity of the player making the move, the location and destination of the piece being moved, and some boolean values indicating the results of the move. It also contains a pointer to the next ply of the move tree (subsequentMove), and a pointer to alternative moves in the current ply (alternativeMove). The former contains moves made by the opposing player in response to this move, while the latter contains other moves that could be made by the current player instead of this move. Together, they allow you to describe the entire move tree.

Your destructor needs to free any memory allocated for the Move data structure.

In calculating moves, you can assume that any castling that might take place has already done so. You can also ignore the possibility of en passant pawn moves. You do need to consider the possibility of promoting a pawn by moving it to the 8th rank of the board. The Move data structure makes provision for specifying the type of the promoted piece.

The winner of this Challenge will be the entry that correctly solves all test cases in the least amount of execution time. Correctness means identifying all moves in the move tree, and guaranteeing checkmate in the minimum number of moves. Timing will include the constructor, a call to your solve routine, and a call to your destructor for a sequence of boards. I am eliminating the subjective evaluation factor for this Challenge because of questions about fairness, but both readers and I appreciate code that is clear and well commented.

This will be a native PowerPC Carbon C++ Challenge, using the Metrowerks CodeWarrior Pro 7.0 development environment. Please be certain that your code is carbonized, as I may evaluate this Challenge using Mac OS X.

Winner of the May, 2002 Challenge

The May Challenge asked users to assemble a Jigsaw puzzle. The puzzle was presented as a color bitmap, with each piece of the puzzle consisting of contiguous pixels of a unique color. The pieces were disassembled and rotated by some multiple of 90 degrees. All of them were "face up". The puzzle was guaranteed to be rectangular in shape, and the pieces were guaranteed to fit together in only one way. The top left corner of the puzzle was in the correct position, which removed any ambiguity about orientation. Congratulations to Tom Saxton for submitting the winning entry for this Challenge.

Generating test data for the Challenge is often, well, a challenge, and this was particularly the case this month. I needed to ensure that the puzzle pieces I generated fit together without ambiguity. And while I could have generated puzzle pieces using "cuts" based on straight line segments, I wanted pieces that resembled real jigsaw puzzles. After struggling with this for some time, I nearly despaired of this objective, but eventually I found something that seems quite pleasing.

The first step in puzzle generation was to divide the puzzle into a roughly rectangular grid. For this, I decided to superimpose several cosine waves with random amplitudes, wavelengths, and offsets. I settled on summing four cosine functions for each horizontal or vertical "cut" in the puzzle, with amplitudes between 5% and 10% of the average piece size and wavelengths between 33% and ~300% of the average piece size. I repeatedly divided the puzzle into different colors for each of these horizontal and vertical cuts. This created a rectangular grid of uniquely shaped pieces with pleasantly curved edges.

I could have stopped there, but I really wanted to have pieces that had the protuberances or "ears" commonly found in real jigsaw puzzles. Being uncertain about how to create these using mathematics, I thought about creating ears manually and "stamping" them onto each edge, modifying them slightly to make them unique. That idea lasted all of about fifteen minutes, as tedium drove this thought from my mind. Eventually, I decided to experiment with one of my favorite programs, Graphing Calculator. An early version of GC came bundled with MacOS for some time, but <plug> the commercial version http://www.pacifict.com offers significantly more functionality </plug>. Anyway, GC has helped me out in the past, so I started experimenting, and ran across this sample equation:



Looking at the part of this equation that is above the x axis with -1<x<0.5, it seemed pretty close to what I was looking for. And randomly varying the amplitude of the sin functions caused the ear to take different shapes. The coefficients in the sin functions needed to be constrained to between about 1.5 and 5.5 in order to prevent the ear from being pinched off and disconnected from the base. In my first few puzzles, a few of these disconnected pieces bypassed detection by me, but not by contestants, so I eventually settled on a more restricted range of parameters that generated slightly less interesting, but still acceptable, ear shapes. For each edge, I selected a location somewhere in the middle of the piece, randomized the direction of the ear (with a small probability of having no ear at all), superimposed the x axis above onto the curved line described above, and adjusted the piece boundary according to the portion of a shape like the one above located above the x-axis (or, for vertical lines, the portion right of the y-axis. This turned out to be less trivial than I had hoped, especially being careful to avoid creating those pesky disconnected pieces. Preventing one ear from intersecting with another ear and cutting a piece in two proved to be an additional complication, but the end result looked like this:


Tom locates the individual pieces of the puzzle in his _FFindPieces routine, and creates four bitmaps per piece, one for each possible rotation, in _FBuildPceBitmap. He detects edge pieces in the _GetEdgeInfo routine, marking them as such for future use. After placing the upper left piece in its guaranteed-correct position, the heavy lifting is done by the _FSolvePce routine, which solves the puzzle from top to bottom, left to right. Tom checks each possible rotation of each piece against the current piece location using two passes, the first trying to look at only pieces with the correct "innie/outie" (Tom's term) match, and the second to pick up pieces to weirdly shaped to be missed in the first pass. The logic for matching two pieces is rather intricate, and can be found in the _FTestPce routine.

Ernst solves the puzzles by first creating a vector array for each piece that described a clockwise path around the piece. He assembles the pieces by inserting them into a Shell data structure, first placing the edge pieces, and spiralling inward toward the center. While his solution is very fast, it became confused on the largest of my test cases, a problem that Ernst attributed to a lack of backtracking logic.

I evaluated the entries using 6 test cases that ranged in size from 24 pieces to 3750 pieces. Both Ernst and Tom were credited for including an optional feature to display the solved puzzle. Tom also displayed the puzzle in its disassembled state, and included options to display PICT and Jigsaw files, for which he earned a feature point reduction bonus. Ernst earned a larger point reduction for code clarity and commentary.

The table below lists, for each of the solutions submitted, the total execution time in seconds, the bonuses for clarity and for displaying the solved puzzle, and the total score. It also lists the programming language used for each entry. As usual, the number in parentheses after the entrant's name is the total number of Challenge points earned in all Challenges prior to this one.

   
                    Time     Cases     Clarity   Features   Score   Language
                    (secs)   Correct   Bonus     Bonus      
Tom Saxton (210)     597.1      6       0.10       0.25      388.1   C++
Ernst Munter (872)   89.9       5       0.25       0.20       49.5   C++

Top Contestants ...

Listed here are the Top Contestants for the Programmer's Challenge, including everyone who has accumulated 20 or more points during the past two years. The numbers below include points awarded over the 24 most recent contests, including points earned by this month's entrants.

   
Rank  Name              Points    Wins       Total
      (24 mo)           (24 mo)   Points   
 1.   Munter, Ernst       243       8         872   
 2.   Saxton, Tom          65       2         230   
 3.   Taylor, Jonathan     57       2          83   
 4.   Stenger, Allen       53       1         118   
 5.   Rieken, Willeke      42       2         134   
 6.   Wihlborg, Claes      40       2          49   
 8.   Gregg, Xan           20       1         140   
 9.   Mallett, Jeff        20       1         114   
10.   Cooper, Tony         20       1          20   
11.   Truskier, Peter      20       1          20   

Here is Tom's winning Jigsaw solution. The code had been abridged for publication because of page constraints; see http://www.mactech.com for the full version.

    Jigsaw.cp

    Copyright (c) 2002

    Tom Saxton

/*
*  Jigsaw
 *
 *  Created by Tom Saxton on Thu Apr 18 2002.
*/
#include <Carbon/Carbon.h>
#include "jigsaw.h"
// make sure we aren't using printf in the non-console builds
#ifndef UI_CONSOLE
#define printf error
#endif
typedef struct PT PT; // a point
struct PT
{
   int x, y;
};
#define zNil 0x7FFF
typedef struct EDGE EDGE; // info about an edge
struct EDGE
{
   char fEdge;
};
typedef enum
{
   btMask,
   btEdge
} BT;
typedef struct ROT ROT;
struct ROT // info for a rotation of a piece
{
   int mruReject;
   EDGE aedge[4];
   BitMap bitmapMask;
   BitMap bitmapEdge;
};
typedef struct PCE PCE;
struct PCE // a single piece, including its four rotations
{
   long cpixel;
   ushort clr;
   char cEdgeSide;
   char irotUsed;
   ROT arot[4];
};
typedef struct PUZ PUZ;
struct PUZ // the puzzle solving state
{
   // challenge state maintained by host
   CS *pcs;
   // the image data, (first the input file, then the output file after extracting the pieces)
   BITS bits;
   int fChangedSize;
   // bitmap mask for the puzzle as we decompose then solve it
   BitMap bitmapMask;
   
   // the array of pieces
   int cpce;
   PCE *papce;
   
   // memory block from which we allocate the bitmaps of the individual pieces
   char *pabBuffer;
   long cbBufferAlloc;
   long cbBufferUsed;
   
   // the current solution state
   int ipceNext;
   Rect rectPrev;
   int xRightEdge, yBottomEdge;
   int cpceRow;
   int yTopUnsolved;
   long cpixelImage;
   long cpixelPuzzle;
   long cpixelSolved;
   AbsoluteTime ticksTotal;
   AbsoluteTime tickStart;
};
// define adjacency
typedef struct DIR DIR;
struct DIR // a direction to move to an adjacent pixel
{
   int dx, dy;
};
// directions to look when checking the left edge of a piece
static const DIR s_adirLeft[] =
{
   {  0,  1 },
   { -1,  1 },
   { -1,  0 },
   { -1, -1 },
   {  0, -1 },
};
// directions to look when checking the top edge of a piece
static const DIR s_adirAbove[] = 
{
   {  1,  0 },
   {  1, -1 },
   {  0, -1 },
   { -1, -1 },
   { -1,  0 },
};
enum
{
   iedgeTop = 0,
   iedgeLeft,
   iedgeBottom,
   iedgeRight,
   cedge
};
// directions to look when finding the boundary of a piece
static const DIR s_adirEdge[cedge] = 
{
   {  1,  0 },
   {  0,  1 },
   { -1,  0 },
   {  0, -1 },
};
// function prototypes deleted for brevity
SolveJigsaw
// the public entry point to the puzzle solver
void SolveJigsaw(CS *pcs, const char pszFile[])
{
      
   long cbRead;
   OSStatus ec;
   int cSolved = 0;
   FN fnOut = fnNil;
   double musecTotal = 0.0;
   
   // init the puzzle structure
   PUZ puz;
   memset(&puz, 0, sizeof(PUZ));
   puz.pcs = pcs;
   
   // open and read the challenge file (omitted for brevity)
   // create and open the output file (omitted for brevity)
   
   // process the cases
   for (; iCase <= cCase; ++iCase)
   {
      // note the starting time
      puz.ticksTotal = s_tickZero;
      puz.tickStart = UpTime();
#ifdef UI_CONSOLE
      printf("process case %d of %d:\n", iCase, cCase);
#endif
       
      // load in the image
      if (!_FLoadData(&puz, iCase))
         break;
#ifdef UI_GUI
      // put the starting image into the output window
      puz.ticksTotal = AddAbsoluteToAbsolute(puz.ticksTotal, 
            SubAbsoluteFromAbsolute(UpTime(), puz.tickStart));
      DrawBits(puz.pcs, puz.bits, puz.xRightEdge, puz.yBottomEdge);
      puz.tickStart = UpTime();
#endif
            
      // let's find all of the pieces
      if (!_FFindPieces(&puz))
      {
         _FreePuz(&puz);
         continue;
      }
      
      // place the first piece into the output buffer
      _PlacePce(&puz, 0, 0, 0, 0);
#ifdef UI_GUI
      puz.ticksTotal = AddAbsoluteToAbsolute(puz.ticksTotal, 
               SubAbsoluteFromAbsolute(UpTime(), puz.tickStart));
      DrawBits(puz.pcs, puz.bits, puz.xRightEdge, puz.yBottomEdge);
      puz.tickStart = UpTime();
#endif
      while (puz.ipceNext < puz.cpce && _FSolvePce(&puz))
      {
#ifdef UI_GUI
         puz.ticksTotal = AddAbsoluteToAbsolute(puz.ticksTotal, 
               SubAbsoluteFromAbsolute(UpTime(), puz.tickStart));
         if (puz.fChangedSize)
         {
            DrawBits(puz.pcs, puz.bits, puz.xRightEdge, 
               puz.yBottomEdge);
            puz.fChangedSize = fFalse;
         }
         else
         {
            UpdateBits(puz.pcs, puz.bits, puz.rectPrev);
         }
         puz.tickStart = UpTime();
#endif
      }
      
      // if we completely solved the puzzle, write out the solution
      if (puz.ipceNext == puz.cpce)
      {
#ifdef UI_CONSOLE
         printf("\tpuzzle %d solved\n", iCase);
#endif
         // write out our solution
         if (!_FWriteResult(&puz, iCase))
            break;
         ++cSolved;
      }
      if (puz.ipceNext < puz.cpce)
      {
#ifdef UI_CONSOLE
         printf("ERROR: Solve failed after %d pieces\n", puz.ipceNext);
#endif
      }
      // free the memory used by this puzzle
      _FreePuz(&puz);
      
      // get the ending time and subtract the starting time to get elapsed time
      // write the time, in microseconds, to the file
      //      (omitted for brevity)
   }
#ifdef UI_CONSOLE
   printf("%d of %d puzzles solved, total time = %g\n", cSolved, cCase, musecTotal);
#endif
LRet:
   _FreePuz(&puz); // harmless if the puz was freed through normal process
   if (fnOut != 0)
      CloseFn(fnOut);
}
// load in the data for a puzzle (omitted for brevity)
static int _FLoadData(PUZ *ppuz, int iCase)
//    (omitted for brevity)
_FFindPieces
// locate the pieces in the input file, build bitmaps for them
static int _FFindPieces(PUZ *ppuz)
{
   int fSuccess = fFalse;
   ppuz->cpixelPuzzle = 0;
   ppuz->yTopUnsolved = 0;
   
   ushort *psw;
   {
      const ushort *pswLim = 
            &ppuz->bits.pasw[ppuz->bits.dx * ppuz->bits.dy];
      for (psw = ppuz->bits.pasw; psw < pswLim; ++psw)
         if (*psw > ppuz->cpce)
            ppuz->cpce = *psw;
   }
   // allocate and init the piece array
   ppuz->papce = new PCE[ppuz->cpce];
   if (ppuz->papce == NULL)
   {
#ifdef UI_CONSOLE
      printf("ERROR: oom allocating piece array with %d entries\n", 
               ppuz->cpce);
#endif
      goto LExit;
   }
   memset(ppuz->papce, 0, sizeof(PCE)*ppuz->cpce);
   psw = ppuz->bits.pasw;
   for (int y = 0; y < ppuz->bits.dy; ++y)
   {
      for (int x = 0; x < ppuz->bits.dx; )
      {
         int xStart = x++;
         ushort clr = *psw++;
         if (clr == 0)
            continue;
         while (x < ppuz->bits.dx && *psw == clr)
            ++x, ++psw;
         PCE *ppce = &ppuz->papce[clr-1];
         if (ppce->clr == 0)
         {
            ppce->clr = clr;
            _SetRect(&ppce->arot[0].bitmapMask.bounds, xStart, 
                  y, x, y+1);
         }
         else
         {
            _ExpandRect(&ppce->arot[0].bitmapMask.bounds, 
                  y, xStart, x);
         }
      }
   }
   // figure out an upper bound on how much bitmap data we'll need
   {
      int dzMost = 0;
      for (int ipce = 0; ipce < ppuz->cpce; ++ipce)
      {
         Rect *prect = &ppuz->papce[ipce].arot[0].bitmapMask.bounds;
         int dx = prect->right - prect->left;
         if (dx > dzMost)
            dzMost = dx;
         int dy = prect->bottom - prect->top;
         if (dy > dzMost)
            dzMost = dy;
      }
      long cbBitmapMost = dzMost * ((dzMost + 15) >> 4) << 1;
      ppuz->cbBufferAlloc = cbBitmapMost * ppuz->cpce * 8;
      ppuz->pabBuffer = new char[ppuz->cbBufferAlloc];
   }
   
   for (int ipce = 0; ipce < ppuz->cpce; ++ipce)
   {
      if (!_FBuildPceBitmaps(ppuz, ipce))
         goto LExit;
#ifdef UI_GUI
      ppuz->ticksTotal = AddAbsoluteToAbsolute(ppuz->ticksTotal, 
            SubAbsoluteFromAbsolute(UpTime(), ppuz->tickStart));
      UpdateBits(ppuz->pcs, ppuz->bits, ppuz->papce[ipce].arot[0].bitmapMask.bounds);
      ppuz->tickStart = UpTime();
#endif
   }
   
   fSuccess = fTrue;
#ifdef UI_CONSOLE
   printf("\tfound %d pieces comprising %ld pixels\n", ppuz->cpce, ppuz->cpixelPuzzle);
#endif
LExit:
   return fSuccess;
}
_FBuildPceBitmap
// build the required bitmaps for a puzzle piece in all four rotations
static int _FBuildPceBitmaps(PUZ *ppuz, int ipce)
{
   int fSuccess = fFalse;
   PCE *ppce = &ppuz->papce[ipce];
   
   Rect rectBounds = ppce->arot[0].bitmapMask.bounds;
   if (!_FCreateBitmap(ppuz, &ppce->arot[0].bitmapMask, 
               rectBounds.left, rectBounds.top, rectBounds.right, 
               rectBounds.bottom))
      goto LExit;
   if (!_FCreateBitmap(ppuz, &ppce->arot[0].bitmapEdge, 
               rectBounds.left, rectBounds.top, rectBounds.right, 
               rectBounds.bottom))
      goto LExit;
   ppuz->cpixelPuzzle += ppce->cpixel = _ColorFill(&ppuz->bits, 
               rectBounds, ppce->clr, &ppce->arot[0].bitmapMask);
   _BuildEdgeBitmap(ppce->arot[0].bitmapMask, 
               &ppce->arot[0].bitmapEdge);
   _GetEdgeInfo(ppuz, ppce);
   
   for (int irot = 1; irot < DIM(ppce->arot); ++irot)
      if (!_FRotateBitmap(ppuz, ppce->arot[0].bitmapEdge, irot, 
               &ppce->arot[irot].bitmapEdge))
         goto LExit;
      
   fSuccess = fTrue;
LExit:
   return fTrue;
}
_FSolvePce
// solve for one piece of the puzzle
static int _FSolvePce(PUZ *ppuz)
{
   // find the first unplaced pixel
   int xTarget, yTarget;
   // start x out just to the right of the most recent piece we placed,
   // unless that piece hit the right edge of the puzzle
   xTarget = ppuz->rectPrev.right;
   if (xTarget == ppuz->xRightEdge)
      xTarget = 0;
   else
      ++xTarget;
   // starting at the top of the unsolved area of the puzzle, march down
   // the chosen x column until we find an unset pixel
   for (yTarget = ppuz->yTopUnsolved; yTarget < ppuz->yBottomEdge; 
                  ++yTarget)
      if (!_FGetBit(ppuz->bitmapMask, xTarget, yTarget))
         break;
   // now, try to move as far up and to the left as possible since
   // we'd really like to have the upper left corner pixel of the next
   // piece as our target
   while (fTrue)
   {
      if (xTarget > 0 && !_FGetBit(ppuz->bitmapMask, xTarget-1, 
            yTarget))
         --xTarget;
      else if (yTarget > 0 && !_FGetBit(ppuz->bitmapMask, xTarget, 
            yTarget-1))
         --yTarget;
      else
         break;
   }
   
   // finally, make sure the target point in the leftmost unset pixel in yTarget's row
   // so that we only have to check the leftmost set pixel of each scan line in each
   // candidate piece
   for (int xT = xTarget - 1; xT >= ppuz->rectPrev.left; --xT)
   {
      if (!_FGetBit(ppuz->bitmapMask, xT, yTarget))
         xTarget = xT;
   }
   PT aptCheck[4];
   int cptCheck = 0;
   if (ppuz->rectPrev.right < ppuz->xRightEdge)
   {
      PCE *ppcePrev = &ppuz->papce[ppuz->ipceNext-1];
      ROT *prot = &ppcePrev->arot[ppcePrev->irotUsed];
      int cptIn = _CptGetEdgeShape(prot->bitmapMask, aptCheck);
      for (int ipt = 0; ipt < cptIn; ++ipt)
      {
         PT pt = aptCheck[ipt];
         _OffsetPt(&pt,
            ppuz->rectPrev.left - prot->bitmapEdge.bounds.left,
            ppuz->rectPrev.top  - prot->bitmapEdge.bounds.top
            );
         pt.x += 1;
         if (_FPtInRect(ppuz->bitmapMask.bounds, pt.x, pt.y) && 
                     !_FGetBit(ppuz->bitmapMask, pt.x, pt.y))
            aptCheck[cptCheck++] = pt;
      }
   }
   if (ppuz->yTopUnsolved > 0)
   {
      const PCE *ppceAbove = 
            &ppuz->papce[ppuz->ipceNext - ppuz->cpceRow];
      const ROT *protAbove = &ppceAbove->arot[ppceAbove->irotUsed];
      PT ptTop;
      ptTop.x = (protAbove->bitmapMask.bounds.left + 
            protAbove->bitmapMask.bounds.right)/2;
      for (ptTop.y = ppuz->yTopUnsolved; 
                  ptTop.y < ppuz->yBottomEdge; ++ptTop.y)
      {
         if (!_FGetBit(ppuz->bitmapMask, ptTop.x, ptTop.y))
         {
            aptCheck[cptCheck++] = ptTop;
            break;
         }
      }
   }
   for (int pass = 1; pass <= 2; ++pass)
   {
      for (int irot = 0; irot < DIM(ppuz->papce[0].arot); ++irot)
      {
         for (int ipce = ppuz->ipceNext; ipce < ppuz->cpce; ++ipce)
         {
            PCE *ppce = &ppuz->papce[ipce];
            ROT *prot = &ppce->arot[irot];
            
            // if we're looking for an edge piece, consider only edge pieces
            if (yTarget == 0 || xTarget == 0)
            {
               if (ppce->cEdgeSide == 0)
                  continue;
               if (yTarget == 0 && !prot->aedge[iedgeTop].fEdge)
                  continue;
               if (xTarget == 0 && !prot->aedge[iedgeLeft].fEdge)
                  continue;
            }
            
            if (pass == 2 && prot->mruReject != ppuz->ipceNext)
            {
               // some pieces are too wierd to work with the innie/outie testing (below),
               // let all the configurations that got rejected previously run through
               // this time, but don't test any piece twice!
               continue;
            }
            
            Rect bounds = prot->bitmapEdge.bounds;
            for (int y = WMin(bounds.bottom-1, 
               bounds.top + (yTarget - ppuz->yTopUnsolved)); 
               y >= bounds.top; --y)
            {
               for (int x = bounds.left; x < bounds.right; ++x)
               {
                  if (!_FGetBit(prot->bitmapEdge, x, y))
                     continue;
      
                  int dx = xTarget - x;
                  int dy = yTarget - y;
                  // make sure the proposed bounding box fits inside the puzzle
                  if (bounds.left + dx < 0 
                     || bounds.right + dx > ppuz->xRightEdge
                     || bounds.top + dy < 0 
                     || bounds.bottom + dy > ppuz->yBottomEdge)
                  {
                     continue;
                  }
                  if (pass == 1)
                  {
                     // make sure we have edge bits to join with check points on the 
                     // previous piece
                     int ipt;
                     for (ipt = 0; ipt < cptCheck; ++ipt)
                        if (!_FGetBitSafe(prot->bitmapEdge, 
                              aptCheck[ipt].x - dx, aptCheck[ipt].y - dy))
                           break;
                     if (ipt < cptCheck)
                     {
                        prot->mruReject = ppuz->ipceNext;
                        break;
                     }
                  }
                  if (_FTestPce(ppuz, ipce, irot, dx, dy))
                  {
                     _PlacePce(ppuz, ipce, irot, dx, dy);
                                       return fTrue;
                  }
                  break;
               }
            }
         }
      }
   }
   return fFalse;
}
_FTestPce
// test whether or not the indicated piece fits into the puzzle at
// the specified offset from it starting position.
static int _FTestPce(PUZ *ppuz, int ipce, int irot, 
                  int dx, int dy)
{
   int fPassed = fFalse;
   // check that no edge pixel invades the completed portion of the puzzle
   PCE *ppce = &ppuz->papce[ipce];
   ROT *prot = &ppce->arot[irot];
   BitMap *pbitmapEdge = &prot->bitmapEdge;
   Rect bounds = pbitmapEdge->bounds;
   for (int y = bounds.top; y < bounds.bottom; ++y)
   {
      uchar mask;
      int x = bounds.left;
      uchar *pb = _PbMaskForBitmapBit(pbitmapEdge, x, y, &mask);
      for ( ; x < bounds.right; )
      {
         char b = *pb++;
         if (b == 0)
         {
            x += 8;
            continue;
         }
         for ( ; mask != 0; ++x, mask >>= 1)
         {
            if (b & mask)
            {
               if (!_FPtInRect(ppuz->bitmapMask.bounds, x+dx, y+dy) || 
                        _FGetBit(ppuz->bitmapMask, x+dx, y+dy))
               {
                  goto LRet;
               }
            }
         }
         mask = 0x80;
      }
   }
   // make sure the mask bitmap has been built
   BitMap *pbitmapMask;
   pbitmapMask = &prot->bitmapMask;
   if (pbitmapMask->baseAddr == NULL)
   {
      if (!_FRotateBitmap(ppuz, ppce->arot[0].bitmapMask, irot, 
                  pbitmapMask))
      {
#ifdef UI_CONSOLE
         printf("ERROR: oom building rotated mask bitmap for piece %d\n", ppuz->ipceNext);
#endif
         goto LRet;
      }
   }
   // now scan left edge pixels looking for pixels that are interior to the proposed 
   // assembled pieces in order to pass, there have to be interior edge pixels from the 
   // top of the piece down "most"  the piece, with no gaps.
   {
      int xMid = (bounds.left + bounds.right)/2;
      int yInteriorLim = bounds.top;
      int yInteriorReqd = (bounds.top + bounds.bottom)/2;
      for (int y = bounds.top; y < bounds.bottom; ++y)
      {
         int x = bounds.left;
         uchar mask;
         uchar *pb = _PbMaskForBitmapBit(pbitmapEdge, bounds.left, 
                                       y, &mask);
         for ( ; x < xMid; )
         {
            char b = *pb++;
            if (b == 0x00)
            {
               x += 8;
               continue;
            }
            for ( ; mask != 0; ++x, mask >>= 1)
            {
               if (b & mask)
               {
                  if (x >= xMid)
                     break;
                  int idir;
                  for (idir = 0; idir < DIM(s_adirLeft); ++idir)
                  {
                     struct DIR dir = s_adirLeft[idir];
                     if (_FPtInRect(ppuz->bitmapMask.bounds, x+dx+dir.dx, 
                                 y+dy+dir.dy)
                        && !_FGetBit(ppuz->bitmapMask, x+dx+dir.dx, 
                                 y+dy+dir.dy)
                        && !_FGetBitSafe(*pbitmapMask, x+dir.dx, y+dir.dy)
                        )
                     {
                        break;
                     }
                  }
                  if (idir == DIM(s_adirLeft))
                  {
                     // this pixel is an interior pixel
                     if (yInteriorLim < y)
                     {
                        goto LRet; // we lose, there was a gap in the interior 
                                       //edge pixels
                     }
                     yInteriorLim = y+1;
                     x = bounds.right; // force the "x" loop to terminate
                     break;
                  }
                  else
                  {
                     // this pixel is not an interior pixel
                     if (y < yInteriorReqd)
                        goto LRet; // we didn't find enough contiguous interior 
                                       //edge pixels
                     
                     // we don't mind that this edge pixel isn't an interior pixel,
                     // and we can stop looking at this scan line
                     goto LPassedLeft;
                  }
               }
            }
            mask = 0x80;
         }
         
         Assert (x >= xMid);
         // any pixels on the left half of this scan line are interior pixels
         if (yInteriorLim < y)
            goto LRet; // we lose, there was a gap in the interior edge pixels
         yInteriorLim = y+1;
      }
   }
LPassedLeft:
   // now scan top edge pixels looking for pixels that are interior to the proposed 
   // assembled pieces in order to pass, there have to be interior edge pixels from the 
   // top of the piece down "most" of the piece, with no gaps.
   {
      int yMid = (bounds.top + bounds.bottom)/2;
      int xInteriorLim = bounds.left;
      int xInteriorReqd = (bounds.left + bounds.right)/2;
      for (int x = bounds.left; x < bounds.right; ++x)
      {
         int y = bounds.top;
         uchar mask;
         uchar *pb = _PbMaskForBitmapBit(pbitmapEdge, x, y, &mask);
         for ( ; y < yMid; ++y, pb += pbitmapEdge->rowBytes)
         {
            if (*pb & mask)
            {
               int idir;
               for (idir = 0; idir < DIM(s_adirAbove); ++idir)
               {
                  struct DIR dir = s_adirAbove[idir];
                  if (_FPtInRect(ppuz->bitmapMask.bounds, x+dx+dir.dx, 
                                    y+dy+dir.dy)
                     && !_FGetBit(ppuz->bitmapMask, x+dx+dir.dx, 
                                    y+dy+dir.dy)
                     && !_FGetBitSafe(*pbitmapMask, x+dir.dx, y+dir.dy)
                     )
                  {
                     break;
                  }
               }
               if (idir == DIM(s_adirAbove))
               {
                  // this pixel is an interior pixel
                  if (xInteriorLim < x)
                     goto LRet; // we lose, there was a gap in the interior edge 
                                    //pixels
                  xInteriorLim = x+1;
                  y = bounds.bottom; // force the "y" loop to terminate
                  break;
               }
               else
               {
                  // this pixel is not an interior pixel
                  if (x < xInteriorReqd)
                     goto LRet; // we didn't find enough contiguous interior 
                                    //edge pixels
                  
                  // we don't mind that this edge pixel isn't an interior pixel,
                  // and we can stop looking at this scan line
                  goto LPassedTop;
               }
            }
         }
         
         Assert (y >= yMid);
         // any pixels on the top half of this scan line are interior pixels
         if (xInteriorLim < x)
            goto LRet; // we lose, there was a gap in the interior edge pixels
         xInteriorLim = x+1;
      }
   }
LPassedTop:
   fPassed = fTrue;
LRet:
   return fPassed;
}
// write out the solved puzzle state
static int _FWriteResult(PUZ *ppuz, int iCase)
// omitted for brevity
_PlacePce
// place the indicated piece into the puzzle at the specified offset
// from its current position
static void _PlacePce(PUZ *ppuz, int ipce, int irot, int dxOffset, int dyOffset)
{
   PCE *ppce = &ppuz->papce[ipce];
   ROT *prot = &ppce->arot[irot];
   BitMap *pbitmapMask = &prot->bitmapMask;
   Rect boundsSrc = pbitmapMask->bounds;
   Rect boundsDst = boundsSrc;
   _OffsetRect(&boundsDst, dxOffset, dyOffset);
   // record the bounds of where we placed the most current piece
   ppuz->rectPrev = boundsDst;
   ppce->irotUsed = irot;
   
   // copy the piece to the output image
   _TransferBitmapToImage(ppuz, prot, btMask, ppce->clr, 
               dxOffset, dyOffset);
   // check to see if we've found the right edge yet
   if (ppuz->xRightEdge == ppuz->bits.dx && 
               prot->aedge[iedgeRight].fEdge)
   {
      // test to see if the piece we just put in is an edge piece,
      // we require a more strict "edge" test for this purpose
      int y;
      int x = boundsSrc.right - 1;
      for (y = boundsSrc.top; y < boundsSrc.bottom; ++y)
         if (!_FGetBit(*pbitmapMask, x, y))
            break;
      if (y > (boundsSrc.top + 2*boundsSrc.bottom)/3)
      {
         for ( ; y < boundsSrc.bottom; ++y)
            if (_FGetBit(*pbitmapMask, x, y))
               break;
         if (y == boundsSrc.bottom)
         {
            if ((ppuz->cpixelPuzzle % boundsDst.right) == 0
               && (ppuz->cpce % (ppuz->ipceNext+1)) == 0)
            {
               ppuz->xRightEdge = boundsDst.right;
               ppuz->yBottomEdge = ppuz->cpixelPuzzle/ppuz->xRightEdge;
               ppuz->cpceRow = ppuz->ipceNext+1;
               ppuz->fChangedSize = fTrue;
            }
         }
      }
   }
   // if we hit the right edge or hit a pixel in the first unsolved scan line, 
   // update ppuz->yTopUnsolved
   if (ppuz->rectPrev.right == ppuz->xRightEdge || 
               boundsSrc.top+dyOffset == ppuz->yTopUnsolved)
   {
      for ( ; ; ++ppuz->yTopUnsolved)
      {
         uchar mask;
         const uchar *pb = _PbMaskForBitmapBit(&ppuz->bitmapMask, 
               0, ppuz->yTopUnsolved, &mask);
         int x;
         for (x = 0; x < ppuz->xRightEdge; x += 8, ++pb)
         {
            if (*pb == 0xFF)
               continue;
            for ( ; mask != 0; mask >>= 1, ++x)
               if ((*pb & mask) == 0)
                  break;
            if (mask != 0)
               break;
         }
         if (x < ppuz->xRightEdge)
            break;
      }
   }
   
   // update stats
   ppuz->cpixelSolved += ppce->cpixel;
   
   // move the rotation we used to its correct location for use later
   _OffsetRect(&prot->bitmapMask.bounds, dxOffset, dyOffset);
   _OffsetRect(&prot->bitmapEdge.bounds, dxOffset, dyOffset);
   // update the piece array
   if (ipce != ppuz->ipceNext)
   {
      PCE pceT = ppuz->papce[ipce];
      ppuz->papce[ipce] = ppuz->papce[ppuz->ipceNext];
      ppuz->papce[ppuz->ipceNext] = pceT;
   }
   ++ppuz->ipceNext;
   
}
// set the mask bitmap and color in the solved puzzle with the new piece
static void _TransferBitmapToImage(PUZ *ppuz, const ROT *prot, 
      BT bt, ushort clr, int dxOffset, int dyOffset)
// omitted for brevity
_FreePuz
// free the puzzle state and everything it allocated
static void _FreePuz(PUZ *ppuz)
{
   _FreeBits(&ppuz->bits);
   _FreeBitmap(&ppuz->bitmapMask);
   if (ppuz->papce != NULL)
   {
      delete [] ppuz->pabBuffer;
      ppuz->pabBuffer = NULL;
      ppuz->cbBufferUsed = ppuz->cbBufferAlloc = 0;
      
      delete [] ppuz->papce;
      ppuz->papce = NULL;
      ppuz->cpce = ppuz->ipceNext = 0;
   }
   
}
_FreeBits
// free the buffer that holds the bitmap image data
static void _FreeBits(BITS *pbits)
{
   if (pbits->pasw != NULL)
   {
      delete [] pbits->pasw;
      pbits->pasw = NULL;
   }
}
_FCreateBitmap
// allocate a new bitmap with the specified bounding rect
// if ppuz != NULL, use the preallocted buffer, otherwise use new
static int _FCreateBitmap(PUZ *ppuz, BitMap *pbitmap, int xLeft, int yTop, int xRight, int yBottom)
{
   _SetRect(&pbitmap->bounds, xLeft, yTop, xRight, yBottom);
   pbitmap->rowBytes = (((xRight - xLeft) + 15) >> 4) << 1;
   long cbBitmap = _CbBitmap(*pbitmap);
   
   if (ppuz != NULL)
   {
      // grab the chunk we need
      pbitmap->baseAddr = &ppuz->pabBuffer[ppuz->cbBufferUsed];
      ppuz->cbBufferUsed += cbBitmap;
   }
   else
   {
      pbitmap->baseAddr = new char[cbBitmap];
   }
   memset(pbitmap->baseAddr, 0, cbBitmap);
   
   return pbitmap->baseAddr != NULL;
}
_FreeBitmap
// free a bitmap whose bits were individually allocated
// be careful: most bit maps get allocated from the preallocated buffer
static void _FreeBitmap(BitMap *pbitmap)
{
   if (pbitmap->baseAddr != NULL)
   {
      delete [] pbitmap->baseAddr;
      pbitmap->baseAddr = NULL;
   }
}
_FGetBit
// return the state of the specified bit
static int _FGetBit(const BitMap &bitmap, int x, int y)
{
   uchar mask;
   uchar *pb = _PbMaskForBitmapBit(&bitmap, x, y, &mask);
   int fSet = ((*pb) & mask) != 0;
   return fSet;
}
_FGetBitSafe
// return the value of the specified bit if it's withing the bitmap,
// otherwise return 0
static int _FGetBitSafe(const BitMap &bitmap, int x, int y)
{
   int fSet = _FPtInRect(bitmap.bounds, x, y) ? 
                           _FGetBit(bitmap, x, y) : 0;
   return fSet;
}
_SetBit
// makes sure the indicated bit is set, returns non-zero if the bit needed to be set
static void _SetBit(BitMap *pbitmap, int x, int y)
{
   uchar mask;
   uchar *pb = _PbMaskForBitmapBit(pbitmap, x, y, &mask);
   *pb |= mask;
}
// set a bit in the specified bitmap
static void _SetBit(BitMap *pbitmap, int x, int y, int fSet)
{
   uchar mask;
   uchar *pb = _PbMaskForBitmapBit(pbitmap, x, y, &mask);
   if (fSet)
      *pb |= mask;
   else
      *pb &= ~mask;
}
_CbBitmap
// return size needed for the specified bitmap's bitmap data
static long _CbBitmap(const BitMap &bitmap)
{
   return (bitmap.bounds.bottom - bitmap.bounds.top) * bitmap.rowBytes;
}
_PbMaskForBitmapBit
// for the specified pixel location within the bitmap, return the pointer
// to the correct byte in the bitmap data and the mask for the specified bit
// note - this is done incrementally in time critical routines
static uchar *_PbMaskForBitmapBit(const BitMap *pbitmap, int x, int y, uchar *pmask)
{
   y -= pbitmap->bounds.top;
   x -= pbitmap->bounds.left;
   *pmask = 0x80 >> (x & 0x7);
   return (uchar *)&pbitmap->baseAddr[y * pbitmap->rowBytes + 
                                                                  (x>>3)];
}
_OffsetPt
// offset the point by the specified amounts
static void _OffsetPt(PT *ppt, int dx, int dy)
{
   ppt->x += dx;
   ppt->y += dy;
}
_FPtInRect
// is the specified point in the specified rect?
static int _FPtInRect(const Rect &rect, int x, int y)
{
   return rect.left <= x && x < rect.right && 
                              rect.top <= y && y < rect.bottom;
}
_SetRect
// like QD routine, but thread safe
static void _SetRect(Rect *prect, short left, short top, short right, short bottom)
{
   prect->left = left;
   prect->top = top;
   prect->right = right;
   prect->bottom = bottom;
}
_OffsetRect
// like QD routine, but thread safe
static void _OffsetRect(Rect *prect, short dx, short dy)
{
   prect->left += dx;
   prect->right += dx;
   prect->top += dy;
   prect->bottom += dy;
}
_ExpandRect
// expand the specified rect to include the specified scan line
static void _ExpandRect(Rect *prect, int y, int xFirst, int xLim)
{
   prect->bottom = y + 1;
   if (prect->left > xFirst)
      prect->left = xFirst;
   if (prect->right < xLim)
      prect->right = xLim;
}
// find all of the pixels in the original puzzle image data which match the
// specified "color", constraining the search to the specified rectangle
static long _ColorFill(BITS *pbits, const Rect &rectBounds, ushort clrMatch, BitMap *pbitmapMask)
{
   ushort *psw = &pbits->pasw[rectBounds.top * pbits->dx + 
               rectBounds.left];
   int cswSkip = pbits->dx - (rectBounds.right - rectBounds.left);
   long cpixelMatch = 0;
   for (int y = rectBounds.top; y < rectBounds.bottom; ++y)
   {
      for (int x = rectBounds.left; x < rectBounds.right; 
                     ++x, ++psw)
      {
         if (*psw == clrMatch)
         {
            *psw = 0;
            _SetBit(pbitmapMask, x, y);
            ++cpixelMatch;
         }
      }
      psw += cswSkip;
   }
   
   return cpixelMatch;
}
_BuildEdgeBitmap
// find the boundary of a piece and construct a bitmap with those bits set
static void _BuildEdgeBitmap(const BitMap &bitmapMask, BitMap *pbitmapEdge)
{
   for (int y = bitmapMask.bounds.top; 
               y < bitmapMask.bounds.bottom; ++y)
   {
      for (int x = bitmapMask.bounds.left; 
               x < bitmapMask.bounds.right; ++x)
      {
         if (_FGetBit(bitmapMask, x, y))
         {
            for (int idir = 0; idir < DIM(s_adirEdge); ++idir)
            {
               const struct DIR *pdir = &s_adirEdge[idir];
               if (!_FGetBitSafe(bitmapMask, x+pdir->dx, y+pdir->dy))
               {
                  _SetBit(pbitmapEdge, x, y);
                  break;
               }
            }
         }
      }
   }
}
_FRotateBitmap
// rotate the given bitmap by the specified number of quarter turns and put
// the result in a newly allocated bitmap
static int _FRotateBitmap(PUZ *ppuz, const BitMap &bitmapSrc, 
            int irot, BitMap *pbitmapDst)
{
   Rect rectBounds = bitmapSrc.bounds;
   switch (irot)
   {
   case 1:
      if (!_FCreateBitmap(ppuz, pbitmapDst, rectBounds.top, 
                  rectBounds.left, rectBounds.bottom, rectBounds.right))
         return fFalse;
      _RotateBitmap90(bitmapSrc, pbitmapDst);
      break;
   case 2:
      if (!_FCreateBitmap(ppuz, pbitmapDst, rectBounds.left, 
                  rectBounds.top, rectBounds.right, rectBounds.bottom))
         return fFalse;
      _RotateBitmap180(bitmapSrc, pbitmapDst);
      break;
   case 3:
      if (!_FCreateBitmap(ppuz, pbitmapDst, rectBounds.top, 
                  rectBounds.left, rectBounds.bottom, rectBounds.right))
         return fFalse;
      _RotateBitmap270(bitmapSrc, pbitmapDst);
      break;
   }
   
   return fTrue;
}
_RotateBitmap180
// rotate the source bitmap by 180 degrees into the destination bitmap
static void _RotateBitmap180(const BitMap &bitmapSrc, 
               BitMap *pbitmapDst)
{
   for (int ySrc = bitmapSrc.bounds.top, 
                                       yDst = pbitmapDst->bounds.bottom-1; 
                                 ySrc < bitmapSrc.bounds.bottom; ++ySrc, --yDst)
      for (int xSrc = bitmapSrc.bounds.left, 
                              xDst = pbitmapDst->bounds.right-1; 
                           xSrc < bitmapSrc.bounds.right; ++xSrc, --xDst)
         _SetBit(pbitmapDst, xDst, yDst, _FGetBit(bitmapSrc, xSrc, ySrc));
}
// _RotateBitmap90 and _RotateBitmap270 omitted for brevity
_GetEdgeInfo
// get info about the edges of the specified piece
static void _GetEdgeInfo(PUZ *ppuz, PCE *ppce)
{
   ROT *prot = &ppce->arot[0];
   BitMap *pbitmap = &prot->bitmapEdge;
   Rect bounds = pbitmap->bounds;
   ppce->cEdgeSide = 0;
   for (int idir = 0; idir < DIM(s_adirEdge); ++idir)
   {
      const DIR dir = s_adirEdge[idir];
      
      int x, y;
      int zFirst, zLim, *pz;
      if (dir.dx != 0)
      {
         pz = &x;
         zFirst = bounds.left;
         zLim = bounds.right;
         y = dir.dx > 0 ? bounds.top : bounds.bottom - 1;
      }
      else
      {
         pz = &y;
         zFirst = bounds.top;
         zLim = bounds.bottom;
         x = dir.dy > 0 ? bounds.left : bounds.right - 1;
      }
      
      // scan to see if this side looks like an edge piece
      EDGE *pedge = &prot->aedge[idir];
      pedge->fEdge = fFalse;
      int dzEdge = zLim - zFirst;
      if (dzEdge < 0)
         dzEdge = -dzEdge;
      
      int cpixEdge = 0;
      for (*pz = zFirst ; *pz != zLim; *pz += 1)
      {
         if (!_FGetBit(*pbitmap, x, y))
         {
            cpixEdge = 0;
            continue;
         }
         if (cpixEdge++ > 0)
         {
            if (cpixEdge == dzEdge/2)
               prot->aedge[idir].fEdge = fTrue;
         }
         else if (prot->aedge[idir].fEdge)
         {
            prot->aedge[idir].fEdge = fFalse;
            break;
         }
      }
      if (prot->aedge[idir].fEdge)
         ++ppce->cEdgeSide;
   }
   // copy the edge information to the other rotations
   for (int irot = 1; irot < DIM(ppce->arot); ++irot)
      for (int iedge = 0; iedge < 4; ++iedge)
         ppce->arot[irot].aedge[iedge] = 
                        prot->aedge[(iedge + irot) % 4];
}
_FindCorners
// find a reasonable guess for the corners of the piece stored in the bitmap
static void _FindCorners(const BitMap &bitmap, 
                  PT *pptTop, PT *pptBottom)
{
   Rect rectBounds = bitmap.bounds;
   
   pptTop->x = -1;
   for (int d = 0; pptTop->x == -1; ++d)
   {
      PT pt;
      for (pt.x = rectBounds.right-1, pt.y = rectBounds.top+d;
         pt.y < rectBounds.bottom && pt.x >= rectBounds.left;
         --pt.x, ++pt.y)
      {
         if (_FGetBit(bitmap, pt.x, pt.y))
         {
            pptTop->x = _XFirstBit(bitmap, pptTop->y = ++pt.y);
            break;
         }
      }
   }
   
   pptBottom->x = -1;
   for (int d = 0; pptBottom->x == -1;++d)
   {
      PT pt;
      for (pt.x = rectBounds.right-1, pt.y = rectBounds.bottom-1-d;
         pt.y >= rectBounds.top && pt.x >= rectBounds.left;
         --pt.x, --pt.y)
      {
         if (_FGetBit(bitmap, pt.x, pt.y))
         {
            pptBottom->x = _XFirstBit(bitmap, pptBottom->y = --pt.y);
            break;
         }
      }
   }
}
_CptGetEdgeShape
// return up to three "interesting" points along the right edge of the piece
// stored in bitmap
static int _CptGetEdgeShape(const BitMap &bitmap, 
            PT paptCheck[3])
{
   // first, find the corners, more or less
   PT ptCornerTop, ptCornerBottom;
   _FindCorners(bitmap, &ptCornerTop, &ptCornerBottom);
   int dyQuarterEdge = (ptCornerBottom.y - ptCornerTop.y)/4;
   
   int cptCheck = 0;
   Rect rectBounds = bitmap.bounds;
   PT ptIn = {zNil, zNil}, ptOut = {zNil, zNil};
   int iptIn = -1, iptOut = -1;
   int xIn = rectBounds.right, xOut = rectBounds.left-1;
   int fOutPrev = fFalse, fInPrev = fFalse;
   int yMidMin = ptCornerTop.y+1;
   int yMidLim = ptCornerBottom.y;
   
   PT aptJump[255];
   int cptJump = 0;
   PT ptPrev;
   ptPrev.x = _XFirstBit(bitmap, ptPrev.y = yMidMin);
   aptJump[cptJump++] = ptPrev;
   for (PT ptCur = ptPrev; ++ptCur.y < yMidLim; )
   {
      ptCur.x = _XFirstBit(bitmap, ptCur.y);
      
      if (ptCur.x == ptPrev.x)
         continue;
      
      int dx = ptCur.x - ptPrev.x;
      int fIn = dx < 0;
      int fOut = !fIn;
      
      int yPeak;         
      if (fOut && fInPrev)
      {
         // we have local min!
         if (ptPrev.x < xIn
            && _FMiddleish(ptPrev.y, ptCur.y, yMidMin, yMidLim, &yPeak)
            )
         {
            ptIn.x = ptPrev.x;
            ptIn.y = yPeak;
            xIn = ptPrev.x;
            iptIn = cptJump-1;
         }
      }
      else if (fIn && fOutPrev)
      {
         // we have a local max!
         if (ptPrev.x > xOut
            && _FMiddleish(ptPrev.y, ptCur.y, yMidMin, yMidLim, &yPeak)
            )
         {
            ptOut.x = ptPrev.x;
            ptOut.y = yPeak;
            xOut = ptPrev.x;
            iptOut = cptJump-1;
         }
      }
      
      aptJump[cptJump++] = ptCur;
      ptPrev = ptCur;
      fInPrev = fIn;
      fOutPrev = fOut;
   }
   if (ptIn.x != zNil)
   {
      int iptPrev, iptNext, dx;
      
      for (iptPrev = iptIn; ; )
      {
         if (--iptPrev < 0)
            goto LCheckOut;
         dx = aptJump[iptPrev+1].x - aptJump[iptPrev].x;
         if (dx < -1)
            break;
         if (dx > 0)
            if (dx > 1 || aptJump[iptPrev+1].x > ptIn.x+1)
               goto LCheckOut;
      }
      for (iptNext = iptIn; ; )
      {
         if (++iptNext >= cptJump)
            goto LCheckOut;
         dx = aptJump[iptNext].x - aptJump[iptNext-1].x;
         if (dx > 1)
            break;
         if (dx < 0)
            if (dx < -1 || aptJump[iptNext].x < ptIn.x-1)
               goto LCheckOut;
      }
      
      // there has to be some bump to qualify as an innie
      if (aptJump[iptNext].y - (aptJump[iptPrev+1].y-1) > 
                              dyQuarterEdge*2)
         goto LSmooth;
      paptCheck[cptCheck].x = aptJump[iptPrev].x;
      paptCheck[cptCheck++].y = aptJump[iptPrev+1].y-1;
      paptCheck[cptCheck++] = ptIn;
      paptCheck[cptCheck++] = aptJump[iptNext];
      goto LRet;
   }
LCheckOut:
   if (ptOut.x != zNil && (ptIn.x == zNil || 
            ptOut.x == rectBounds.right-1))
   {
      int iptPrev, iptNext, dx;
      
      for (iptPrev = iptOut; ; )
      {
         if (--iptPrev < 0)
            goto LSmooth;
         dx = aptJump[iptPrev+1].x - aptJump[iptPrev].x;
         if (dx > 1)
            break;
         if (dx < 0)
            if (dx < -1 || aptJump[iptPrev+1].x < ptOut.x-1)
               goto LSmooth;
      }
      for (iptNext = iptOut; ; )
      {
         if (++iptNext >= cptJump)
            goto LSmooth;
         dx = aptJump[iptNext].x - aptJump[iptNext-1].x;
         if (dx < -1)
            break;
         if (dx > 0)
            if (dx > 1 || aptJump[iptNext].x > ptOut.x+1)
               goto LSmooth;
      }
      
      // there has to be some bump to qualify as an outie
      if (aptJump[iptNext].y - (aptJump[iptPrev+1].y-1) > 
                     dyQuarterEdge*2)
         goto LSmooth;
      paptCheck[cptCheck].x = aptJump[iptPrev].x;
      paptCheck[cptCheck++].y = aptJump[iptPrev+1].y-1;
      paptCheck[cptCheck++] = ptOut;
      paptCheck[cptCheck++] = aptJump[iptNext];
      goto LRet;
   }
LSmooth:   
   if (ptIn.x == zNil && ptOut.x == zNil)
   {
      int yWant = ptCornerTop.y + dyQuarterEdge;
      int ipt = 1;
      while (ipt < cptJump && aptJump[ipt].y <= yWant)
         ++ipt;
      paptCheck[cptCheck].y = yWant;
      paptCheck[cptCheck++].x = aptJump[ipt-1].x;
      yWant = ptCornerBottom.y - dyQuarterEdge;
      ipt = cptJump-1;
      while (aptJump[ipt].y > yWant)
         --ipt;
      paptCheck[cptCheck].y = yWant;
      paptCheck[cptCheck++].x = aptJump[ipt].x;
   }
   else
   {
      if (ptIn.x != zNil)
         paptCheck[cptCheck++] = ptIn;
      if (ptOut.x != zNil)
         paptCheck[cptCheck++] = ptOut;
   }
LRet:
   return cptCheck;
}
// determine if any element of the segment [x1, x2) is within the 
// the range [xFirst, xLim). If not, return fFalse. If so,
// set *pxMid to a pixel inside the both ranges, as near the midpoint of
// [xFirst, xLim) as possible
static int _FMiddleish(int x1, int x2, int xFirst, int xLim, int *pxMid)
{
   // calculate the midpoint and then the limits of the center segment
   int xMid = (xFirst + xLim)/2;
   if (x2 <= xFirst || xLim <= x1)
      return fFalse;
   if (x1 <= xMid && xMid < x2)
      *pxMid = xMid;
   else if (x1 > xMid)
      *pxMid = x1;
   else
      *pxMid = x2-1;
   return fTrue;
}
// find the rightmost set bit in the specified row of the bitmap
static int _XFirstBit(const BitMap &bitmap, int y)
{
   int x;
   for (x = bitmap.bounds.right-1; x >= bitmap.bounds.left; --x)
      if (_FGetBit(bitmap, x, y))
         break;
   return x;
}
// MusecFromTime omitted for brevity

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Freeway Pro 7.0.3 - Drag-and-drop Web de...
Freeway Pro lets you build websites with speed and precision... without writing a line of code! With its user-oriented drag-and-drop interface, Freeway Pro helps you piece together the website of... Read more
Cloud 3.3.0 - File sharing from your men...
Cloud is simple file sharing for the Mac. Drag a file from your Mac to the CloudApp icon in the menubar and we take care of the rest. A link to the file will automatically be copied to your clipboard... Read more
Cyberduck 4.6.5 - 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
Firefox 36.0 - Fast, safe Web browser. (...
Firefox for Mac offers a fast, safe Web browsing experience. Browse quickly, securely, and effortlessly. With its industry-leading features, Firefox is the choice of Web development professionals and... Read more
Thunderbird 31.5.0 - Email client from M...
As of July 2012, Thunderbird has transitioned to a new governance model, with new features being developed by the broader free software and open source community, and security fixes and improvements... Read more
VOX 2.4 - Music player that supports man...
VoxIt just sounds better! The beauty is in its simplicity, yet behind the minimal exterior lies a powerful music player with a ton of features & support for all audio formats you should ever need... Read more
A Better Finder Rename 9.46 - 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
WALTR 1.0.9 - Drag-and-drop any media fi...
WALTR is designed to make it easy to upload and convert any music or video file to an iPad or iPhone format for native playback. It supports a huge variety of media file types, including MP3, MP4,... Read more
Default Folder X 4.6.14 - Enhances Open...
Default Folder X attaches a toolbar to the right side of the Open and Save dialogs in any OS X-native application. The toolbar gives you fast access to various folders and commands. You just click on... Read more
Boom 2 1.1 - System-wide pro audio app f...
Boom 2 is a system-wide volume booster and equalizer app that is designed especially for OS X 10.10 Yosemite. It comes with a smart interface, self-calibrates itself according to your Mac, offers... Read more

Check Out the Trailer for the Upcoming F...
Check Out the Trailer for the Upcoming FINAL FANTASY: Record Keeper Posted by Jessica Fisher on February 26th, 2015 [ permalink ] DeNA and Square Enix have announced that | Read more »
Legacy Quest is an Upcoming Rouge-like T...
Legacy Quest is an Upcoming Rouge-like That’ll Kill the Whole Family Posted by Jessica Fisher on February 26th, 2015 [ permalink ] Nexon Co. | Read more »
Grudgeball: Enter the Chaosphere Review
Grudgeball: Enter the Chaosphere Review By Jordan Minor on February 26th, 2015 Our Rating: :: MUSCLE MENUniversal App - Designed for iPhone and iPad Regular Show gets an above average game.   | Read more »
Action RPG League of Angels – Fire Raide...
Gaia is being invaded by the Devil Prince and the demonic Devil Army at his disposal, and it’s up to you and your avatar to defeat him in League of Angels – Fire Raiders. Raise a mighty army from hundreds of recruitable angel heroes and take the... | Read more »
Burn Rubber on the Ice With a New Cars:...
Burn Rubber on the Ice With a New Cars: Fast as Lightning Update Posted by Jessica Fisher on February 26th, 2015 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
AdVenture Capitalist Review
AdVenture Capitalist Review By Jordan Minor on February 26th, 2015 Our Rating: :: DAS KAPITALUniversal App - Designed for iPhone and iPad An inadvertent Marxist manifesto.   | Read more »
Monster vs Sheep Review
Monster vs Sheep Review By Jennifer Allen on February 25th, 2015 Our Rating: :: SAMEY FUNUniversal App - Designed for iPhone and iPad What Monster vs Sheep lacks in variety it makes up for with stress relieving fun. At least, for a... | Read more »
Is Your Face Ready for the New Outwitter...
Is Your Face Ready for the New Outwitters 2.0 Trailer? Posted by Jessica Fisher on February 25th, 2015 [ permalink ] One Man Left Studios has announced that their turn-based strategy game, | Read more »
HowToFormat Review
HowToFormat Review By Jennifer Allen on February 25th, 2015 Our Rating: :: USEFUL TIPSiPhone App - Designed for the iPhone, compatible with the iPad Making a presentation and want to get it just right? HowToFormat teaches you how... | Read more »
Thermo Diem Review
Thermo Diem Review By Jennifer Allen on February 25th, 2015 Our Rating: :: GETS TO THE POINTUniversal App - Designed for iPhone and iPad Want to know whether it’s warmer or colder tomorrow? That’s precisely what Thermo Diem will... | Read more »

Price Scanner via MacPrices.net

New Travel Health App “My Travel Health” iOS...
Rochester, Minnesota based Travel Health and Wellness LLC has announced that its new iOS app help safeguard the user’s health when traveling abroad — “My Travel Health” is now available on the Apple... Read more
Sale! MacBook Airs for up to $115 off MSRP
B&H Photo has MacBook Airs on sale for up to $100 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 11″ 128GB MacBook Air: $799 100 off MSRP - 11″ 256GB MacBook Air: $999 $100... Read more
15-inch 2.0GHz Retina MacBook Pro (refurbishe...
The Apple Store has Apple Certified Refurbished previous-generation 15″ 2.0GHz Retina MacBook Pros available for $1489 including free shipping plus Apple’s standard one-year warranty. Their price is... Read more
Wither The iPad mini? End Of The Road Imminen...
AppleDailyReport’s Dennis Sellers predicts that the iPad mini is going to be left to wither on the vine, as it were, and then just allowed to fade away — a casualty of the IPhone 6 Plus and other... Read more
Android and iOS Duopoly Owns 96.3% of Smartph...
IDC reports that Android and iOS inched closer to total domination of the worldwide smartphone market in both the fourth quarter (4Q14) and the calendar year 2014 (CY14). According to data from the... Read more
13-inch 2.4GHz Retina MacBook Pro available f...
MacMall has the 2013 13″ 2.4GHz/128GB Retina MacBook Pro available for $999.99 for a limited time. Shipping is free. Their price is $300 off original MSRP, and it’s the only sub-$1000 new Retina... Read more
Save up to $300 on a new Mac, $30 on an iPad,...
Purchase a new Mac or iPad at The Apple Store for Education and take up to $300 off MSRP. All teachers, students, and staff of any educational institution qualify for the discount. Shipping is free,... Read more
Mac minis available for up to $75 off MSRP
MacMall has Mac minis on sale for up to $75 off MSRP including free shipping. Their prices are the lowest available for these models from any reseller: - 1.4GHz Mac mini: $459.99 $40 off - 2.6GHz Mac... Read more
WaterField Unveils Versatile Padded Gear Pouc...
San Francisco manufacturer WaterField Design’s new Padded Gear Pouch is a light and handy-sized, yet protective, organizer for every kind of take-along gear: technology, travel, toiletries,... Read more
College Student Deals: Additional $50 off Mac...
Take an additional $50 off all MacBooks and iMacs at Best Buy Online with their College Students Deals Savings, valid through April 11, 2015. Anyone with a valid .EDU email address can take advantage... Read more

Jobs Board

*Apple* Solutions Consultant - Retail Sales...
**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 - Retail Sales...
**Job Summary** As an Apple Solutions Consultant (ASC) you are the link between our customers and our products. Your role is to drive the Apple business in a retail Read more
*Apple* Solutions Consultant (ASC)- Retail S...
**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 - Retail Sales...
**Job Summary** As an Apple Solutions Consultant (ASC) you are the link between our customers and our products. Your role is to drive the Apple business in a retail Read more
Sr. Technical Services Consultant, *Apple*...
**Job Summary** Apple Professional Services (APS) has an opening for a senior technical position that contributes to Apple 's efforts for strategic and transactional Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.