home *** CD-ROM | disk | FTP | other *** search
/ ftp.mactech.com 2010 / ftp.mactech.com.tar / ftp.mactech.com / challenge / 13.12 / Challenge.sit / Challenge / ImgDetector.c < prev    next >
Text File  |  1997-10-23  |  28KB  |  1,035 lines
  1. /**********************************************************/
  2. /*    ImgDetector.c
  3.  
  4. MacTech Challenge September 1997
  5. Image Locator
  6. by Ludovic Nicolle
  7. 621, chemin des tourterelles
  8. St-Nicolas, QC
  9. Canada,    G7A 3P3 
  10. tel: (418) 836-4610
  11. email: lnicolle@cmq.qc.ca
  12.  
  13. August 31th 1997.
  14. */
  15.  
  16. /*
  17. General issues:
  18. The code uses 3 functions, DetectLeft/Center/Right to find
  19. matches on each side and in the middle. The same three
  20. functions are used for the top/center/bottom on each colon.
  21.  
  22. Algorithmic considerations:
  23. the fundamental operation for each bit of the mask at any 
  24. particular location on the image is the following one and
  25. referred as the xor/and later in this discussion:
  26. mismatch = (pattern ^ background) & mask;
  27. if mismatch == 1, you got a bit mismatch.
  28.  
  29. Since it was assumed the code would more naturally be called
  30. with (noise < 0.5) than greater, it made sense to count the
  31. mismatches. The code actually substract any mismatch from
  32. the maximum allowed. (The variables names are maxBad for the 
  33. maximum and remBad for the remaining allowed bad bits at any
  34. time in the process.)
  35.  
  36. The first natural step of optimization was to treat the data
  37. in parallel, either 8, 16 or 32 bits at a time. I choosed to
  38. work on a 16 bits basis. After the entire operation of
  39. xor/and has been done on 16 bits, the number of 1's in the 
  40. 16 bits is loaded from a 64k static array (named gBitsOn)
  41. containing a 2^16 chars (this method proved to be 
  42. statistically much faster than anything else).
  43.  
  44. Since we needed to "move" the mask and pattern in parallel
  45. over the background, I choosed to move the background 
  46. instead so I had only one variable to shift each time.
  47.  
  48. In the DectectLeft/Right functions, the code reflects only
  49. those considerations, with a special treatment for the
  50. border when it is not flush.
  51.  
  52. The DetectCenter function uses a more sophisticated 
  53. algorithm derived form the simple one described above. While
  54. written in pure C portable code, is is really optimized for
  55. the register-rich PowerPC architecture. 
  56.  
  57. It uses 16 registers to treat 16 "remBad" in parallel. Each
  58. time a short is loaded for the pattern and for the mask, it
  59. is used to xor/and with 16 different positions of the 
  60. background. Reducing the number of loads from the memory 
  61. maximize the troughput of the function. An other register
  62. is used to globally monitor the status of the 16 remBads,
  63. using a simple bit array, and is called remFlag.
  64.  
  65. To achieve the best performance, all the 16 local remBads 
  66. had to be in registers. Intermediate versions having only
  67. 10 to 15 remBads in registers performed less than the
  68. all-in-regs one. To free as much registers as possible, the
  69. DetectCenter function was tweeked as much as possible:
  70. - since the pattern and mask had no padding rowBytes 
  71.     (rowBytes was still a multiple of 2 of course, but not 
  72.     necessarily of 4), the internal ptrs didn't needed
  73.     intermediate line ptrs (they are used on the Left/Right)
  74. - the line index of the mask/pattern is a float, using the
  75.     otherwise unused floating point unit of the processor,
  76. - many local variables were placed as dumb parameters of
  77.     the function (the ImageDetect calls use nil/0 as the 
  78.     6 first parameters) to fool the PowerPC Compiler which
  79.     follows the PowerPC binary architecture for allocating
  80.     parameters and local variables.
  81.  
  82. Many parameters were put as stack parameters in order to 
  83. free enough space for the remBad's and other inner loops 
  84. variables.
  85.  
  86. As a last note on this optimization issue, I want to say
  87. this version of the code uses an if (remBadxx) statement
  88. before each xor/and. On my PPC 601, this was less efficient
  89. than blind execution of the xor/and followed by the check to
  90. see if the remBad was now under 0. On the PPC 604, my tests
  91. showed that this version was faster, probably due to one or 
  92. both of the following factors:
  93. - branch prediction/excution is faster on the 604,
  94. - the 604/memory speed ratio being greater than with my 601, 
  95.     the load from the gBitsOn array incurs a greater time 
  96.     penalty than the time taken for branching.
  97.  
  98. */
  99.  
  100. /*
  101. InitTarget
  102. InitTarget jobs are:
  103. - to count the number of bits inside the pattern, 
  104. - to build an array containing the number of bits to remove 
  105.     when the mask is placed partially outside the 
  106.     backgroundImage, 
  107. - to find how many white rows and cols are on the 
  108.     left/right/top/bottom of the mask and squeeze the 
  109.     pattern and mask accordingly
  110. - to make local copies of the pattern and mask that have no
  111.     extra padding rowBytes,
  112. - to zero any mask bits on the right end of those rows if
  113.     they are not a multiple of 16.
  114.     
  115. ImageDetect determines the number of bad bits allowed with 
  116. the noise threshold then determines the number of rows must
  117. be tested on the top/bottom border. It also sets a few 
  118. globals about the locations.
  119.  
  120. It then repeatedly calls DetectLeft/Center/Right for the 
  121. top. It then calls the three functions once again for the
  122. middle (vertically speaking). Finally, they are called
  123. repeactedly again on the bottom.
  124. */
  125. typedef unsigned short    ushort;
  126. typedef unsigned long    ulong;
  127.  
  128. /*    the gBitsOn array is in the BitsOn.c file
  129.     which must be linked into the project.    */
  130. extern unsigned char    gBitsOn[256*256];
  131.  
  132. /*    Globals    */
  133. BitMap    gPattern;
  134. BitMap    gMask;
  135.  
  136. ushort    gmkWidth;
  137. ushort    gmkHeight;
  138. Point    gmkSkip;
  139.  
  140. Point    *gLocations;
  141. long    gLocationsCt;
  142. long    gMaxLocations;
  143.  
  144. ulong    gmkTotalBits;
  145. ulong    *gmkBitsCache;
  146.  
  147. void InitTarget(
  148.   BitMap pattern,  /* image to be detected */
  149.   BitMap mask      /* bits in image that we care about */
  150. );
  151.  
  152. long /* numFound */ ImageDetect(
  153.   BitMap backgroundImage,  /* find the target image in backgroundImage */
  154.   Point locations[],  /* return topLeft of matching locations here */
  155.   long maxLocations,  /* max number of locations to return */
  156.   float noise         /* allow this fraction of mismatched bits */
  157. );
  158.  
  159. void CleanUp(void);   /* deallocate any memory allocated by InitTarget */
  160.  
  161. void InitTarget(
  162. BitMap pattern,  /* image to be detected */
  163. BitMap mask      /* bits in image that we care about */
  164. )
  165. {
  166.     ulong    mkSize;
  167.     short    height, width;
  168.     short    minRowBytes;
  169.     short    lineIdx, colIdx;
  170.     short    mkTopSkip, mkBotSkip, mkRightSkip, mkLeftSkip;
  171.     Rect    srcRect, destRect;
  172.     ulong    *mkBitsCache;
  173.     ushort    *mkLinePtr, *mkCurPtr;
  174.     ulong    bitsCt;
  175.     Ptr        mkBaseAddr;
  176.     short    offSet;
  177.     
  178. /*    Calculating mask size    */
  179.     width = mask.bounds.right - mask.bounds.left;
  180.     height = mask.bounds.bottom - mask.bounds.top;
  181.  
  182. /*    Minimizing rowBytes and copying bitmaps    structures
  183.     and setting mask/pattern topleft to (0,0)        */
  184.     minRowBytes = 2 * ((width + 15) / 16);
  185.     mkSize = height * minRowBytes;
  186.     gMask.rowBytes = minRowBytes;
  187.     gMask.bounds.top = 0;
  188.     gMask.bounds.left = 0;
  189.     gMask.bounds.bottom = height;
  190.     gMask.bounds.right = width;
  191.  
  192.     gMask.baseAddr = NewPtr(mkSize);
  193.     if (width % 16)
  194.     {    /* Zeroing the last short of each row    */
  195.         offSet = minRowBytes - 2;
  196.         (Ptr)mkLinePtr = gMask.baseAddr + offSet;
  197.         for (lineIdx = 0; lineIdx < height; lineIdx++)
  198.         {
  199.             (*mkLinePtr) = 0;
  200.             (Ptr)mkLinePtr += minRowBytes;
  201.         }
  202.     }
  203.     CopyBits(&mask, &gMask, &mask.bounds, 
  204.                         &gMask.bounds, srcCopy, nil);
  205.     
  206. /*    filling lines cache, removing empty top lines and
  207.     counting empty top lines.
  208. */
  209.     (Ptr)mkBitsCache = NewPtr(sizeof(ulong) *
  210.                                         height * width);
  211.     gmkBitsCache = mkBitsCache;
  212.     (Ptr)mkLinePtr = gMask.baseAddr;
  213.     bitsCt = 0;
  214.     mkTopSkip = 0;
  215.     for (lineIdx = 0; lineIdx < height; lineIdx++)
  216.     {
  217.         if (mkBitsCache)
  218.             mkBitsCache[(lineIdx - mkTopSkip) * width] = 
  219.                                                     bitsCt;
  220.         mkCurPtr = mkLinePtr;
  221.         (Ptr)mkLinePtr += minRowBytes;
  222.         for (; mkCurPtr < mkLinePtr; mkCurPtr++)
  223.             bitsCt += gBitsOn[*mkCurPtr];
  224.         if (bitsCt == 0)
  225.             mkTopSkip++;
  226.     }
  227.     gmkTotalBits = bitsCt;
  228.     
  229. /*    counting empty bottom lines    */
  230.     mkBotSkip = 0;
  231.     lineIdx = height - mkTopSkip - 1;
  232.     for (lineIdx = height - mkTopSkip - 1; (lineIdx > 0) && 
  233.                 (mkBitsCache[lineIdx * width] == bitsCt);
  234.                                                 lineIdx--)
  235.             mkBotSkip++;
  236.     
  237.     height -= (mkTopSkip + mkBotSkip);
  238.     mkBaseAddr = gMask.baseAddr + mkTopSkip * minRowBytes;
  239.     
  240. /*    filling the bits cache*/
  241.     if (gmkBitsCache)
  242.     {
  243.         for (colIdx = 1; colIdx < width; colIdx++)
  244.         {
  245.             ushort    mkMask;
  246.             ulong    freeBitsCt;
  247.             short    colModulo;
  248.             
  249.             (Ptr)mkLinePtr = mkBaseAddr +
  250.                                 (height - 1) * minRowBytes;
  251.             mkLinePtr += (colIdx - 1) / 16 ;
  252.             colModulo = (colIdx - 1) % 16;
  253.             mkMask = 0xFFFF << (15 - colModulo);
  254.             freeBitsCt = 0;
  255.             for (lineIdx = height - 1; lineIdx >= 0; 
  256.                                                 lineIdx--)
  257.             {
  258.                 freeBitsCt += 
  259.                             gBitsOn[(*mkLinePtr) & mkMask];
  260.                 bitsCt = freeBitsCt +
  261.                             mkBitsCache[lineIdx * width + 
  262.                                     colIdx - 1 - colModulo];
  263.                 mkBitsCache[lineIdx * width + colIdx] = 
  264.                                                     bitsCt;
  265.                 (Ptr)mkLinePtr -= minRowBytes;
  266.             }
  267.         }
  268.     }
  269.  
  270. /*    calculating left and right empty cols    */
  271.     mkLeftSkip = 0;
  272.     for (colIdx = 1; 
  273.             (colIdx < width) && (mkBitsCache[colIdx] == 0);
  274.                                                 colIdx++)
  275.             mkLeftSkip++;
  276.     mkRightSkip = 0;
  277.     for (colIdx = width - 1; 
  278.             (colIdx > 0) && (mkBitsCache[colIdx] == bitsCt);
  279.                                                 colIdx--)
  280.             mkRightSkip++;
  281. /*    restructuring mkBitsCache according to the new width
  282.     if it's smaller.            */
  283.     if ((mkRightSkip + mkLeftSkip) > 0)
  284.     {
  285.         short    oldWidth = width;
  286.         
  287.         width -= (mkRightSkip + mkLeftSkip);
  288.         minRowBytes = 2 * ((width + 15) / 16);
  289.         
  290.         for (lineIdx = 0; lineIdx < height; lineIdx++)
  291.             for (colIdx = 0; colIdx < width; colIdx++)
  292.                 mkBitsCache[lineIdx * width + colIdx] = 
  293.                     mkBitsCache[lineIdx * oldWidth + 
  294.                                     colIdx + mkLeftSkip];
  295.     }
  296.     
  297. /*    initializing the pattern BitMap. the allocated space
  298.     will be used for mask or pattern data.
  299. */
  300.     gPattern.rowBytes = minRowBytes;
  301.     gPattern.bounds.top = 0;
  302.     gPattern.bounds.left = 0;
  303.     gPattern.bounds.bottom = height;
  304.     gPattern.bounds.right = width;
  305.     mkSize = minRowBytes * height;
  306.     gPattern.baseAddr = NewPtr(mkSize);
  307.     
  308.     if ((mkTopSkip > 0) || (mkLeftSkip > 0) || 
  309.         (minRowBytes < gMask.rowBytes))
  310.     {    /* I must recopy the mask bits    */        
  311.         srcRect.top = mkTopSkip;
  312.         srcRect.left = mkLeftSkip;
  313.         srcRect.bottom = mkTopSkip + height;
  314.         srcRect.right = mkLeftSkip + width;
  315.         destRect.top = 0;
  316.         destRect.left = 0;
  317.         destRect.bottom = height;
  318.         destRect.right = width;
  319.         
  320.         if (width % 16)
  321.         {    /* Zeroing the last short of each row    */            
  322.             offSet = minRowBytes - 2;
  323.             (Ptr)mkLinePtr = gPattern.baseAddr + offSet;
  324.             for (lineIdx = 0; lineIdx < height; lineIdx++)
  325.             {
  326.                 (*mkLinePtr) = 0;
  327.                 (Ptr)mkLinePtr += minRowBytes;
  328.             }
  329.         }
  330.         CopyBits(&gMask, &gPattern, &srcRect, &destRect,
  331.                                         srcCopy, nil);
  332. /*    switching bits data between gMask and gPattern    */
  333.         (Ptr)mkLinePtr = gMask.baseAddr;
  334.         gMask = gPattern;
  335.         gPattern.baseAddr = (Ptr)mkLinePtr;
  336.     }
  337.     
  338.     srcRect = pattern.bounds;
  339.     srcRect.top += mkTopSkip;
  340.     srcRect.bottom -= mkBotSkip;
  341.     srcRect.left += mkLeftSkip;
  342.     srcRect.right -= mkRightSkip;
  343.     CopyBits(&pattern, &gPattern, &srcRect, 
  344.                         &gPattern.bounds, srcCopy, nil);
  345.     
  346.     gmkWidth = width;
  347.     gmkHeight = height;
  348.     gmkSkip.v = mkTopSkip;
  349.     gmkSkip.h = mkLeftSkip;
  350. }
  351.  
  352.  
  353. void CleanUp(void)   /* deallocate any memory allocated by InitTarget */
  354. {
  355.     if (gPattern.baseAddr)
  356.         DisposePtr(gPattern.baseAddr);
  357.     if (gMask.baseAddr)
  358.         DisposePtr(gMask.baseAddr);
  359.     
  360.     if (gmkBitsCache)
  361.         DisposePtr((Ptr)gmkBitsCache);
  362. }
  363.  
  364. Boolean DetectLeft(
  365. BitMap*    picture, 
  366. long    maxBad,
  367. short    mkRowBytes,
  368. short    picRowBytes,
  369. short    picTop, 
  370. short    picTopLow,
  371. short    mkTop,
  372. short    mkBottom,
  373. short    mkWidth);
  374.  
  375. Boolean DetectCenter(
  376. ushort    *patCurPtr,
  377. ushort    *mkCurPtr,
  378. ushort    *picLinePtr,
  379. ushort    *picCurPtr,
  380. ulong    picLong,
  381. long    dumbReg,
  382. long    mkRowBytes,
  383. long    picRowBytes,
  384. long    mkTop,
  385. long    picTop,
  386. long    maxBad,
  387. long    picTopLow,
  388. long    picWidth,
  389. long    mkBottom,
  390. BitMap*    picture);
  391.  
  392. Boolean DetectRight(
  393. BitMap*    picture, 
  394. long    maxBad,
  395. short    mkRowBytes,
  396. short    picRowBytes,
  397. short    picTop, 
  398. short    picTopLow,
  399. short    mkTop,
  400. short    mkBottom,
  401. short    picWidth,
  402. short    mkWidth);
  403.  
  404.  
  405.  
  406. long /* numFound */ ImageDetect(
  407.   BitMap backgroundImage,  /* find the target image in backgroundImage */
  408.   Point locations[],  /* return topLeft of matching locations here */
  409.   long maxLocations,  /* max number of locations to return */
  410.   float noise         /* allow this fraction of mismatched bits */
  411. )
  412. {
  413.     ulong    maxBad;
  414.     short    picWidth, picHeight;
  415.     ulong    *mkBitsCache;
  416.     short    mkRowBytes;
  417.     short    picRowBytes;
  418.     short    mkLine, outTop, outBottom;
  419.     long    totalBits;
  420.     
  421.     gLocations = locations;
  422.     gLocationsCt = 0;
  423.     gMaxLocations = maxLocations;
  424.     
  425.     if (gmkBitsCache == nil)/*cannot work without cache */
  426.         return 0;            /*but this could be patched    */
  427.     if (noise < 0.0 || noise >= 1.0)
  428.         return 0;    /* not supposed to happen    */
  429.     if (gmkTotalBits == 0)
  430.         return 0;    /* there is no bits in the mask    */
  431.     maxBad = gmkTotalBits * noise;
  432.     
  433.     
  434.     picWidth = backgroundImage.bounds.right - 
  435.                     backgroundImage.bounds.left;
  436.     picHeight = backgroundImage.bounds.bottom - 
  437.                     backgroundImage.bounds.top;
  438.     
  439.     if ((picWidth < gmkWidth) ||
  440.         (picHeight < gmkHeight))
  441.         return 0;    /* not supposed to happen    */
  442.     
  443.     mkBitsCache = gmkBitsCache;
  444.     mkRowBytes = gMask.rowBytes;
  445.     picRowBytes = backgroundImage.rowBytes;
  446.     
  447. /* scan top    */
  448.     mkLine = 1;
  449.     while ((mkLine < gmkHeight) &&
  450.             (mkBitsCache[mkLine * gmkWidth] <= maxBad))
  451.         mkLine++;
  452.  
  453.     for (outTop = mkLine - 1; outTop >= 1; outTop--)
  454.     {
  455.         if (DetectLeft(&backgroundImage, maxBad, 
  456.             mkRowBytes, picRowBytes,
  457.             backgroundImage.bounds.top, 
  458.             backgroundImage.bounds.top + 1, 
  459.             outTop, gmkHeight, gmkWidth))
  460.             return gLocationsCt;
  461.         if (DetectCenter(nil, nil, nil, nil, 0, 0,
  462.             mkRowBytes, picRowBytes, outTop,
  463.             backgroundImage.bounds.top, 
  464.             maxBad - mkBitsCache[outTop * gmkWidth],
  465.             backgroundImage.bounds.top + 1, 
  466.             picWidth, gmkHeight, &backgroundImage))
  467.             return gLocationsCt;
  468.         if (DetectRight(&backgroundImage, maxBad,
  469.             mkRowBytes, picRowBytes,
  470.             backgroundImage.bounds.top, 
  471.             backgroundImage.bounds.top + 1, 
  472.             outTop, gmkHeight, picWidth, gmkWidth))
  473.             return gLocationsCt;
  474.     }
  475.  
  476. /*    scan middle    left    */
  477.     if (DetectLeft(&backgroundImage, maxBad, 
  478.             mkRowBytes, picRowBytes,
  479.             backgroundImage.bounds.top, 
  480.             backgroundImage.bounds.bottom - gmkHeight + 1,
  481.             0, gmkHeight, gmkWidth))
  482.         return gLocationsCt;
  483. /*    scan middle    center    */
  484.     if (DetectCenter(nil, nil, nil, nil, 0, 0,
  485.             mkRowBytes, picRowBytes, 0,
  486.             backgroundImage.bounds.top, maxBad, 
  487.             backgroundImage.bounds.bottom - gmkHeight + 1,
  488.             picWidth, gmkHeight, &backgroundImage))
  489.         return gLocationsCt;
  490. /*    scan middle    right    */
  491.     if (DetectRight(&backgroundImage, maxBad, 
  492.             mkRowBytes, picRowBytes,
  493.             backgroundImage.bounds.top, 
  494.             backgroundImage.bounds.bottom - gmkHeight + 1,
  495.             0, gmkHeight, picWidth, gmkWidth))
  496.         return gLocationsCt;
  497.  
  498. /*    scan bottom    */
  499.     totalBits = gmkTotalBits;
  500.     mkLine = 1;
  501.     while ((mkLine < gmkHeight) && ((gmkTotalBits - 
  502.             mkBitsCache[(gmkHeight - mkLine) * gmkWidth]) 
  503.                                     <= maxBad))
  504.         mkLine++;
  505.  
  506.     for (outBottom = 1; outBottom < mkLine; outBottom++)
  507.     {
  508.         if (DetectLeft(&backgroundImage, maxBad,
  509.             mkRowBytes, picRowBytes,
  510.             backgroundImage.bounds.bottom - gmkHeight + 
  511.                                                 outBottom, 
  512.             backgroundImage.bounds.bottom,
  513.             0, gmkHeight - outBottom, gmkWidth))
  514.             return gLocationsCt;
  515.         if (DetectCenter(nil, nil, nil, nil, 0, 0,
  516.             mkRowBytes, picRowBytes, 0,
  517.             backgroundImage.bounds.bottom - gmkHeight + 
  518.                                                 outBottom, 
  519.             maxBad - totalBits + 
  520.             mkBitsCache[(gmkHeight - outBottom) * gmkWidth],
  521.             backgroundImage.bounds.bottom, picWidth, 
  522.             gmkHeight - outBottom, &backgroundImage))
  523.             return gLocationsCt;
  524.         if (DetectRight(&backgroundImage, maxBad,
  525.             mkRowBytes, picRowBytes,
  526.             backgroundImage.bounds.bottom - gmkHeight + 
  527.                                                 outBottom, 
  528.             backgroundImage.bounds.bottom,
  529.             0, gmkHeight - outBottom, picWidth, gmkWidth))
  530.             return gLocationsCt;
  531.     }
  532.  
  533.     return gLocationsCt;
  534. }
  535.  
  536. Boolean DetectLeft(
  537. BitMap*    picture, 
  538. long    maxBad,
  539. short    mkRowBytes,
  540. short    picRowBytes,
  541. short    picTop, 
  542. short    picTopLow,
  543. short    mkTop,
  544. short    mkBottom,
  545. short    mkWidth)
  546. {
  547.     ushort    *picBasePtr, *picLinePtr, *picCurPtr;
  548.     ushort    *patBasePtr, *patLinePtr, *patCurPtr;
  549.     ushort    *mkBasePtr, *mkLinePtr, *mkCurPtr,
  550.             *mkEndOfLinePtr;
  551.     
  552.     short    mkLine;
  553.     ushort    outLeft;
  554.     ulong    picLong;
  555.     ushort    picShift;
  556.     long    remBad;
  557.     ushort    mkout16s;
  558.     
  559.     for (;picTop < picTopLow; picTop++)
  560.     {
  561.     outLeft = 1;
  562.     do
  563.     {    /*    calculating remBad    */
  564.         if ((mkTop)    ||             // we're out by the top
  565.             (mkBottom == gmkHeight))// we are fully in
  566.                                     // vertically
  567.             remBad = maxBad -
  568.                 gmkBitsCache[mkTop * mkWidth + outLeft];
  569.         else
  570.             remBad = maxBad - gmkTotalBits +
  571.                 gmkBitsCache[mkBottom * mkWidth + outLeft] -
  572.                                     gmkBitsCache[outLeft];
  573.                     
  574.         if (remBad < 0)
  575.             break;    // this causes the do{} to stop
  576.         
  577.         mkout16s = outLeft / 16;
  578.         (Ptr)mkBasePtr = gMask.baseAddr + 
  579.                             mkTop * mkRowBytes + mkout16s;
  580.         (Ptr)patBasePtr = gPattern.baseAddr + 
  581.                             mkTop * mkRowBytes + mkout16s;
  582.         (Ptr)picBasePtr = picture->baseAddr + 
  583.             (picTop - picture->bounds.top) * picRowBytes;
  584.  
  585.         picShift = outLeft & 0x0F;
  586.  
  587. /*    left border matching    */
  588.         if (picShift)
  589.         {
  590.             ushort    mkMask;
  591.             
  592.             mkMask = 0xFFFF >> picShift;
  593.             mkLinePtr = mkBasePtr++;
  594.             patLinePtr = patBasePtr++;
  595.             picLinePtr = picBasePtr++;
  596.             for (mkLine = mkTop; mkLine < mkBottom; 
  597.                                                 mkLine++)
  598.             {
  599.                 picLong = *picLinePtr;
  600.                 (Ptr)picLinePtr += picRowBytes;
  601.                 remBad -= gBitsOn[
  602.                 ((*patLinePtr) ^ (picLong >> picShift)) &
  603.                                 (*mkLinePtr) & mkMask];
  604.                 (Ptr)mkLinePtr += mkRowBytes;
  605.                 (Ptr)patLinePtr += mkRowBytes;
  606.             }
  607.         }
  608.         if (remBad < 0)
  609.             continue;
  610. /* regular pattern matching*/
  611.         mkLinePtr = mkBasePtr;
  612.         (Ptr)mkEndOfLinePtr = gMask.baseAddr + 
  613.                                 (mkTop + 1) * mkRowBytes;
  614.         patLinePtr = patBasePtr;
  615.         picLinePtr = picBasePtr;
  616.     /*for each line in the mask    */
  617.         for (mkLine = mkTop; mkLine < mkBottom; mkLine++)
  618.         {
  619.             mkCurPtr = mkLinePtr;
  620.             patCurPtr = patLinePtr;
  621.             picCurPtr = picLinePtr;
  622.             picLong = *picCurPtr++;
  623.             if (picShift)
  624.             {
  625.                 picLong <<= 16;
  626.                 picLong |= *picCurPtr++;
  627.             }
  628.     /* for each 16s of the mask inside the pict    */
  629.             for (; mkCurPtr < mkEndOfLinePtr; mkCurPtr++)
  630.             {
  631.                 remBad -= gBitsOn[((*patCurPtr++) ^
  632.                     (picLong >> picShift)) & (*mkCurPtr)];
  633.                 picLong <<= 16;
  634.                 picLong    |= *picCurPtr++;
  635.             }
  636.             if (remBad < 0)
  637.                 break;
  638.             (Ptr)mkLinePtr += mkRowBytes;
  639.             (Ptr)mkEndOfLinePtr += mkRowBytes;
  640.             (Ptr)patLinePtr += mkRowBytes;
  641.             (Ptr)picLinePtr += picRowBytes;
  642.         }
  643.         if (remBad >= 0)
  644.         {
  645.             if (gLocationsCt < gMaxLocations)
  646.             {
  647.                 gLocations[gLocationsCt].v = 
  648.                         picTop - mkTop - gmkSkip.v;
  649.                 gLocations[gLocationsCt++].h = 
  650.                         picture->bounds.left - outLeft
  651.                                     - gmkSkip.h;
  652.             } else
  653.                 return true;
  654.         }
  655.     } while (++outLeft < mkWidth);
  656.  
  657.     }
  658.     return false;
  659. }
  660.  
  661. #define AddCenterLocation(rem, shift);                \
  662.     if (rem >= 0)                                    \
  663.     {                                                \
  664.         if (gLocationsCt < gMaxLocations)            \
  665.         {                                            \
  666.             gLocations[gLocationsCt].v =             \
  667.                         picTop - mkTop - gmkSkip.v;    \
  668.             gLocations[gLocationsCt++].h =             \
  669.                 picture->bounds.left + shift +        \
  670.                 (picWidth - picRemain)                \
  671.                              - gmkSkip.h;            \
  672.         } else                                        \
  673.             return true;                            \
  674.     }
  675.  
  676. Boolean DetectCenter(
  677. ushort    *patCurPtr,
  678. ushort    *mkCurPtr,
  679. ushort    *picLinePtr,
  680. ushort    *picCurPtr,
  681. ulong    picLong,
  682. long    dumbReg,
  683. long    mkRowBytes,
  684. long    picRowBytes,
  685. long    mkTop,
  686. long    picTop,
  687. long    maxBad,
  688. long    picTopLow,
  689. long    picWidth,
  690. long    mkBottom,
  691. BitMap*    picture
  692. )
  693. {
  694.     short    picRemain;
  695.     float    mkLineStart;
  696.     float    mkLine;
  697.     
  698.     mkLineStart = mkBottom - mkTop - 0.5;
  699.     picWidth -= gmkWidth;
  700.     
  701.     for (; picTop < picTopLow; picTop++)
  702.     {
  703.     picRemain = picWidth;
  704.     do
  705.     {
  706.         register ushort    remFlag;
  707.         register long
  708.                 remBad00, remBad01, remBad02, remBad03,
  709.                 remBad04, remBad05, remBad06, remBad07,
  710.                 remBad08, remBad09, remBad10, remBad11,
  711.                 remBad12, remBad13, remBad14, remBad15;
  712.  
  713. /* initializing the remBads and remFlag    */
  714.         remFlag = 0xFFFF;
  715.         remBad00 = maxBad; remBad01 = remBad00;
  716.         remBad02 = remBad00; remBad03 = remBad01;
  717.         remBad04 = remBad00; remBad05 = remBad01;
  718.         remBad06 = remBad00; remBad07 = remBad01;
  719.         remBad08 = remBad00; remBad09 = remBad01;
  720.         remBad10 = remBad00; remBad11 = remBad01;
  721.         remBad12 = remBad00; remBad13 = remBad01;
  722.         remBad14 = remBad00; remBad15 = remBad01;
  723.         
  724.         switch (picRemain)
  725.         {
  726.             case 0:        remBad01 = -1;
  727.             case 1:        remBad02 = -1;
  728.             case 2:        remBad03 = -1;
  729.             case 3:        remBad04 = -1;
  730.             case 4:        remBad05 = -1;
  731.             case 5:        remBad06 = -1;
  732.             case 6:        remBad07 = -1;
  733.             case 7:        remBad08 = -1;
  734.             case 8:        remBad09 = -1;
  735.             case 9:        remBad10 = -1;
  736.             case 10:    remBad11 = -1;
  737.             case 11:    remBad12 = -1;
  738.             case 12:    remBad13 = -1;
  739.             case 13:    remBad14 = -1;
  740.             case 14:    remBad15 = -1;
  741.         }
  742.         (Ptr)mkCurPtr = 
  743.                     gMask.baseAddr + mkTop * mkRowBytes;
  744.         (Ptr)patCurPtr = 
  745.                     gPattern.baseAddr + mkTop * mkRowBytes;
  746. /* regular pattern matching*/
  747.         (Ptr)picLinePtr = picture->baseAddr +
  748.             (picTop - picture->bounds.top) * picRowBytes;
  749.         picLinePtr += (picWidth - picRemain) / 16;
  750.         
  751.     /*for each line in the mask    */
  752.         for (mkLine = mkLineStart; mkLine > 0.0; mkLine--)
  753.         {
  754.             picCurPtr = picLinePtr;
  755.             (Ptr)picLinePtr += mkRowBytes;
  756.             picLong = *picCurPtr++;
  757.     /* for each 16s of the mask    */
  758.             for (; picCurPtr <= picLinePtr; )
  759.             {
  760.                 ulong mkLo, patLo;
  761.                 
  762.                 picLong <<= 16;
  763.                 picLong    |= *picCurPtr++;
  764.  
  765.                 mkLo = (*mkCurPtr++);
  766.                 patLo = (*patCurPtr++);
  767.                 switch (picRemain)
  768.                 {
  769.                 default:
  770.                 case 15:
  771.                     if (remBad15 < 0)
  772.                         remFlag &= 0x7FFF;
  773.                     else remBad15 -= gBitsOn[(patLo ^
  774.                                 (picLong >> 1)) & mkLo];
  775.                 case 14:
  776.                     if (remBad14 < 0)
  777.                         remFlag &= 0xBFFF;
  778.                     else remBad14 -= gBitsOn[(patLo ^
  779.                                 (picLong >> 2)) & mkLo];
  780.                 case 13:
  781.                     if (remBad13 < 0)
  782.                         remFlag &= 0xDFFF;
  783.                     else remBad13 -= gBitsOn[(patLo ^
  784.                                 (picLong >> 3)) & mkLo];
  785.                 case 12:
  786.                     if (remBad12 < 0)
  787.                         remFlag &= 0xEFFF;
  788.                     else remBad12 -= gBitsOn[(patLo ^
  789.                                 (picLong >> 4)) & mkLo];
  790.                 case 11:
  791.                     if (remBad11 < 0)
  792.                         remFlag &= 0xF7FF;
  793.                     else remBad11 -= gBitsOn[(patLo ^
  794.                                 (picLong >> 5)) & mkLo];
  795.                 case 10:
  796.                     if (remBad10 < 0)
  797.                         remFlag &= 0xFBFF;
  798.                     else remBad10 -= gBitsOn[(patLo ^
  799.                                 (picLong >> 6)) & mkLo];
  800.                 case 9:
  801.                     if (remBad09 < 0)
  802.                         remFlag &= 0xFDFF;
  803.                     else remBad09 -= gBitsOn[(patLo ^
  804.                                 (picLong >> 7)) & mkLo];
  805.                 case 8:
  806.                     if (remBad08 < 0)
  807.                         remFlag &= 0xFEFF;
  808.                     else remBad08 -= gBitsOn[(patLo ^
  809.                                 (picLong >> 8)) & mkLo];
  810.                 case 7:
  811.                     if (remBad07 < 0)
  812.                         remFlag &= 0xFF7F;
  813.                     else remBad07 -= gBitsOn[(patLo ^
  814.                                 (picLong >> 9)) & mkLo];
  815.                 case 6:
  816.                     if (remBad06 < 0)
  817.                         remFlag &= 0xFFBF;
  818.                     else remBad06 -= gBitsOn[(patLo ^
  819.                                 (picLong >> 10)) & mkLo];
  820.                 case 5:
  821.                     if (remBad05 < 0)
  822.                         remFlag &= 0xFFDF;
  823.                     else remBad05 -= gBitsOn[(patLo ^
  824.                                 (picLong >> 11)) & mkLo];
  825.                 case 4:
  826.                     if (remBad04 < 0)
  827.                         remFlag &= 0xFFEF;
  828.                     else remBad04 -= gBitsOn[(patLo ^
  829.                                 (picLong >> 12)) & mkLo];
  830.                 case 3:
  831.                     if (remBad03 < 0)
  832.                         remFlag &= 0xFFF7;
  833.                     else remBad03 -= gBitsOn[(patLo ^
  834.                                 (picLong >> 13)) & mkLo];
  835.                 case 2:
  836.                     if (remBad02 < 0)
  837.                         remFlag &= 0xFFFB;
  838.                     else remBad02 -= gBitsOn[(patLo ^
  839.                                 (picLong >> 14)) & mkLo];
  840.                 case 1:
  841.                     if (remBad01 < 0)
  842.                         remFlag &= 0xFFFD;
  843.                     else remBad01 -= gBitsOn[(patLo ^
  844.                                 (picLong >> 15)) & mkLo];
  845.                 case 0:
  846.                     if (remBad00 < 0)
  847.                         remFlag &= 0xFFFE;
  848.                     else remBad00 -= gBitsOn[(patLo ^
  849.                                 (picLong >> 16)) & mkLo];
  850.                 }
  851.             }
  852.             (Ptr)picLinePtr -= mkRowBytes;
  853.             (Ptr)picLinePtr += picRowBytes;
  854.             
  855.             if (remFlag == 0)
  856.                 break;
  857.         }
  858.         if (remFlag)
  859.         {
  860.             AddCenterLocation(remBad00, 0);        
  861.             AddCenterLocation(remBad01, 1);        
  862.             AddCenterLocation(remBad02, 2);        
  863.             AddCenterLocation(remBad03, 3);        
  864.             AddCenterLocation(remBad04, 4);        
  865.             AddCenterLocation(remBad05, 5);        
  866.             AddCenterLocation(remBad06, 6);        
  867.             AddCenterLocation(remBad07, 7);        
  868.             AddCenterLocation(remBad08, 8);        
  869.             AddCenterLocation(remBad09, 9);        
  870.             AddCenterLocation(remBad10, 10);        
  871.             AddCenterLocation(remBad11, 11);        
  872.             AddCenterLocation(remBad12, 12);        
  873.             AddCenterLocation(remBad13, 13);        
  874.             AddCenterLocation(remBad14, 14);        
  875.             AddCenterLocation(remBad15, 15);        
  876.         }
  877.         picRemain -= 16;
  878.     } while (picRemain >= 0);
  879.     }
  880.     
  881.     return false;
  882. }
  883.  
  884. Boolean DetectRight(
  885. BitMap*    picture, 
  886. long    maxBad,
  887. short    mkRowBytes,
  888. short    picRowBytes,
  889. short    picTop,
  890. short    picTopLow,
  891. short    mkTop,
  892. short    mkBottom,
  893. short    picWidth,
  894. short    mkWidth)
  895. {
  896.     ushort    *picBasePtr, *picLinePtr, *picCurPtr;
  897.     ushort    *patBasePtr, *patLinePtr, *patCurPtr;
  898.     ushort    *mkBasePtr, *mkLinePtr, *mkCurPtr,
  899.             *mkEndOfLinePtr;
  900.     
  901.     short    mkLine;
  902.     ushort    outRight;
  903.     ulong    picLong;
  904.     ushort    picShift;
  905.     long    remBad;
  906.     ushort    mkout16s;
  907.     ushort    mktotal16s;
  908.     ushort    mkModulo;
  909.     ushort    picModulo;
  910.     ushort    flushModulo;
  911.     
  912.     mkModulo = mkWidth & 0x0F;
  913.     (Ptr)mkBasePtr = gMask.baseAddr + 
  914.                                         mkTop * mkRowBytes;
  915.     (Ptr)patBasePtr = gPattern.baseAddr + 
  916.                                         mkTop * mkRowBytes;
  917.     for (; picTop < picTopLow; picTop++)
  918.     {
  919.     outRight = 1;
  920.     do
  921.     {    /*    calculating remBad    */
  922.         if ((mkTop)    ||             // we're out by the top
  923.             (mkBottom == gmkHeight))// we are fully in
  924.                                     // vertically
  925.             remBad = maxBad - gmkTotalBits +
  926.                     gmkBitsCache[(mkTop + 1) * mkWidth - 
  927.                                             outRight] -
  928.                             gmkBitsCache[mkTop * mkWidth];
  929.         else
  930.             remBad = maxBad - gmkTotalBits +
  931.                     gmkBitsCache[mkWidth - outRight] +
  932.                     gmkBitsCache[mkBottom * mkWidth] -
  933.                     gmkBitsCache[(mkBottom + 1) * mkWidth - 
  934.                                                 outRight];
  935.         if (remBad < 0)
  936.             break;    // this causes the do{} to stop
  937.  
  938. /* setup    */
  939.         mktotal16s = (mkWidth + 15) / 16;
  940.         mkout16s = (outRight + 
  941.                     ((mkWidth - outRight - 1) & 0x0F)) / 16;
  942.         (Ptr)picBasePtr = picture->baseAddr +
  943.                     (picTop - picture->bounds.top) * 
  944.                                                 picRowBytes;
  945.         picModulo = picWidth & 0x0F;
  946.         flushModulo = (mkWidth - outRight) & 0x0F;
  947.         picShift = flushModulo - picModulo;
  948.             if (picShift < 0)
  949.                 picShift += 16;
  950. /*    right border matching    */
  951.         if (flushModulo > 0)
  952.         {
  953.             ulong    mkMask;
  954.             
  955.             mkLinePtr = mkBasePtr + mktotal16s - 
  956.                                             (mkout16s + 1);
  957.             patLinePtr = patBasePtr + mktotal16s - 
  958.                                             (mkout16s + 1);
  959.             picLinePtr = picBasePtr + (picWidth / 16 - 1);
  960.             mkMask = 0xFFFF << (16 - flushModulo);
  961.             for (mkLine = mkTop; 
  962.                             mkLine < mkBottom; mkLine++)
  963.             {
  964.                 picLong = *picLinePtr;
  965.                 picLong <<= 16;
  966.                 if (picModulo)
  967.                     picLong = *(picLinePtr + 1);
  968.                 picLong = picLong >> picShift;
  969.  
  970.                 remBad -= gBitsOn[((*patLinePtr) ^ picLong)
  971.                                  & (*mkLinePtr) & mkMask];
  972.                 
  973.                 (Ptr)mkLinePtr += mkRowBytes;
  974.                 (Ptr)patLinePtr += mkRowBytes;
  975.                 (Ptr)picLinePtr += picRowBytes;
  976.             }
  977.         }
  978.         if (remBad < 0)
  979.             continue;
  980. /*    Regular pattern matching    */
  981.  
  982.         mkLinePtr = mkBasePtr;
  983.         patLinePtr = patBasePtr;
  984.         picLinePtr = picBasePtr + (picWidth / 16) - 
  985.                                     (mktotal16s - mkout16s);
  986.         mkEndOfLinePtr = mkLinePtr + 
  987.                             mktotal16s - mkout16s;
  988.         if (flushModulo)
  989.             mkEndOfLinePtr--;
  990. /*    for each line in the mask    */
  991.         for (mkLine = mkTop; mkLine < mkBottom; mkLine++)
  992.         {
  993.             mkCurPtr = mkLinePtr;
  994.             patCurPtr = patLinePtr;
  995.             picCurPtr = picLinePtr;
  996.             picLong = *picCurPtr++;
  997.             if (picShift)
  998.             {
  999.                 picLong <<= 16;
  1000.                 picLong |= *picCurPtr++;
  1001.             }
  1002.     /* each short in the mask inside the pict    */
  1003.             for (; mkCurPtr < mkEndOfLinePtr; 
  1004.                                             mkCurPtr++)
  1005.             {
  1006.                 remBad -= gBitsOn[((*patCurPtr++) ^
  1007.                     (picLong >> picShift)) & (*mkCurPtr)];
  1008.                 picLong <<= 16;
  1009.                 picLong    |= *picCurPtr++;
  1010.             }
  1011.             if (remBad < 0)
  1012.                 break;
  1013.             (Ptr)mkLinePtr += mkRowBytes;
  1014.             (Ptr)mkEndOfLinePtr += mkRowBytes;
  1015.             (Ptr)patLinePtr += mkRowBytes;
  1016.             (Ptr)picLinePtr += picRowBytes;
  1017.         }
  1018.         if (remBad >= 0)
  1019.         {
  1020.             if (gLocationsCt < gMaxLocations)
  1021.             {
  1022.                 gLocations[gLocationsCt].v = 
  1023.                             picTop - mkTop - gmkSkip.v;
  1024.                 gLocations[gLocationsCt++].h = 
  1025.                     picture->bounds.right + outRight - 
  1026.                             mkWidth - gmkSkip.h;
  1027.             } else
  1028.                 return true;
  1029.         }
  1030.     } while (++outRight < mkWidth);
  1031.     
  1032.     }
  1033.     return false;
  1034. }
  1035.