#include "bitmap_find.h"
#include "../base/UTHashTable_c.h"
#include <assert.h>
/* Node to be used in hash table. */
struct shiftNode {
UTHashNode_HEAD /* Make structure hashable */
MMRGBHex color; /* Key */
MMPoint offset; /* Value */
};
/* --- Hash table helper functions --- */
/* Adds hex-color/offset pair to jump table. */
static void addNodeToTable(UTHashTable *table, MMRGBHex color, MMPoint offset);
/* Returns node associated with color in jump table, or NULL if it
* doesn't exist. */
static struct shiftNode *nodeForColor(UTHashTable *table, MMRGBHex color);
/* Returns nonzero (true) if table has key, or zero (false) if not. */
#define tableHasKey(table, color) (nodeForColor(table, color) != NULL)
/* --- Boyer-Moore helper functions --- */
/* Calculates the first table for use in a Boyer-Moore search algorithm.
* Table is in the form [colors: shift_values], where colors are those in
* |needle|, and the shift values are each color's distance from the rightmost
* offset. All other colors are assumed to have a shift value equal to the
* length of needle.
*/
static void initBadShiftTable(UTHashTable *jumpTable, MMBitmapRef needle);
/* Frees memory occupied by calling initBadShiftTable().
* Currently this is just an alias for destroyHashTable(). */
#define destroyBadShiftTable(jumpTable) destroyHashTable(jumpTable)
/* Returns true if |needle| is found in |haystack| at |offset|. */
static int needleAtOffset(MMBitmapRef needle, MMBitmapRef haystack,
MMPoint offset, float tolerance);
/* --- --- */
/* An modification of the Boyer-Moore-Horspool Algorithm, only applied to
* bitmaps and colors instead of strings and characters.
*
* TODO: The Boyer-Moore algorithm (with the second jump table) would probably
* be more efficient, but this was simpler (for now).
*
* The jump table (|badShiftTable|) is passed as a parameter to avoid being
* recalculated each time. It should be a pointer to a UTHashTable init'd with
* initBadShiftTable().
*
* Returns 0 and sets |point| to the starting point of |needle| in |haystack|
* if |needle| was found in |haystack|, or returns -1 if not. */
static int findBitmapInRectAt(MMBitmapRef needle,
MMBitmapRef haystack,
MMPoint *point,
MMRect rect,
float tolerance,
MMPoint startPoint,
UTHashTable *badShiftTable)
{
const size_t scanHeight = rect.size.height - needle->height;
const size_t scanWidth = rect.size.width - needle->width;
MMPoint pointOffset = startPoint;
/* const MMPoint lastPoint = MMPointMake(needle->width - 1, needle->height - 1); */
/* Sanity check */
if (needle->height > haystack->height || needle->width > haystack->width ||
!MMBitmapRectInBounds(haystack, rect)) {
return -1;
}
assert(point != NULL);
assert(needle != NULL);
assert(needle->height > 0 && needle->width > 0);
assert(haystack != NULL);
assert(haystack->height > 0 && haystack->width > 0);
assert(badShiftTable != NULL);
/* Search |haystack|, while |needle| can still be within it. */
while (pointOffset.y <= scanHeight) {
/* struct shiftNode *node = NULL;
MMRGBHex lastColor; */
while (pointOffset.x <= scanWidth) {
/* Check offset in |haystack| for |needle|. */
if (needleAtOffset(needle, haystack, pointOffset, tolerance)) {
// ++pointOffset.x;
// ++pointOffset.y;
*point = pointOffset;
return 0;
}
/* Otherwise, calculate next x offset to check. */
/*
* Note that here we are getting the skip value based on the last
* color of |needle|, no matter where we didn't match. The
* alternative of pretending that the mismatched color was the previous
* color is slower in the normal case.
*/
/* lastColor = MMRGBHexAtPoint(haystack, pointOffset.x + lastPoint.x,
pointOffset.y + lastPoint.y); */
/* TODO: This fails on certain edge cases (issue#7). */
/* When a color is encountered that does not occur in |needle|, we can
* safely skip ahead for the whole length of |needle|.
* Otherwise, use the value stored in the jump table. */
/* node = nodeForColor(badShiftTable, lastColor);
pointOffset.x += (node == NULL) ? needle->width : (node->offset).x; */
/* For now, be naive. */
++pointOffset.x;
}
pointOffset.x = rect.origin.x;
/* lastColor = MMRGBHexAtPoint(haystack, pointOffset.x + lastPoint.x,
pointOffset.y + lastPoint.y);
node = nodeForColor(badShiftTable, lastColor);
pointOffset.y += node == NULL ? lastPoint.y : (node->offset).y; */
/* TODO: The above commented out code fails at certain edge cases, e.g.:
* Needle: [B, b
* b, b,
* B, b]
* Haystack: [w, w, w, w, w
* w, w, w, w, b
* w, w, w, b, b
* w, w, w, w, b]
* The previous algorithm noticed that the first 3 x 3 block had nothing
* in common with the image, and thus, after scanning the first row,
* skipped three blocks downward to scan the next (which didn't exist,
* so the loop ended). However, the needle was hidden IN-BETWEEN this
* jump -- skipping was appropriate for scanning the column but not
* the row.
*
* I need to figure out a more optimal solution; temporarily I am just
* scanning every single y coordinate, only skipping on x's. This
* always works, but is probably not optimal.
*/
++pointOffset.y;
}
return -1;
}
int findBitmapInRect(MMBitmapRef needle,
MMBitmapRef haystack,
MMPoint *point,
MMRect rect,
float tolerance)
{
UTHashTable badShiftTable;
int ret;
initBadShiftTable(&badShiftTable, needle);
ret = findBitmapInRectAt(needle, haystack, point, rect,
tolerance, MMPointZero, &badShiftTable);
destroyBadShiftTable(&badShiftTable);
return ret;
}
MMPointArrayRef findAllBitmapInRect(MMBitmapRef needle, MMBitmapRef haystack,
MMRect rect, float tolerance)
{
MMPointArrayRef pointArray = createMMPointArray(0);
MMPoint point = MMPointZero;
UTHashTable badShiftTable;
initBadShiftTable(&badShiftTable, needle);
while (findBitmapInRectAt(needle, haystack, &point, rect,
tolerance, point, &badShiftTable) == 0) {
const size_t scanWidth = (haystack->width - needle->width) + 1;
MMPointArrayAppendPoint(pointArray, point);
ITER_NEXT_POINT(point, scanWidth, 0);
}
destroyBadShiftTable(&badShiftTable);
return pointArray;
}
size_t countOfBitmapInRect(MMBitmapRef needle, MMBitmapRef haystack,
MMRect rect, float tolerance)
{
size_t count = 0;
MMPoint point = MMPointZero;
UTHashTable badShiftTable;
initBadShiftTable(&badShiftTable, needle);
while (findBitmapInRectAt(needle, haystack, &point, rect,
tolerance, point, &badShiftTable) == 0) {
const size_t scanWidth = (haystack->width - needle->width) + 1;
++count;
ITER_NEXT_POINT(point, scanWidth, 0);
}
destroyBadShiftTable(&badShiftTable);
return count;
}
/* --- Boyer-Moore helper functions --- */
static void initBadShiftTable(UTHashTable *jumpTable, MMBitmapRef needle)
{
const MMPoint lastPoint = MMPointMake(needle->width - 1, needle->height - 1);
const size_t maxColors = needle->width * needle->height;
MMPoint scan;
/* Allocate max size initially to avoid a million calls to malloc(). */
initHashTable(jumpTable, maxColors, sizeof(struct shiftNode));
/* Populate jumpTable with analysis of |needle|. */
for (scan.y = lastPoint.y; ; --scan.y) {
for (scan.x = lastPoint.x; ; --scan.x) {
MMRGBHex color = MMRGBHexAtPoint(needle, scan.x, scan.y);
if (!tableHasKey(jumpTable, color)) {
addNodeToTable(jumpTable, color,
MMPointMake(needle->width - scan.x,
needle->height - scan.y));
}
if (scan.x == 0) break; /* Avoid infinite loop from unsigned type. */
}
if (scan.y == 0) break;
}
}
static int needleAtOffset(MMBitmapRef needle, MMBitmapRef haystack,
MMPoint offset, float tolerance)
{
const MMPoint lastPoint = MMPointMake(needle->width - 1, needle->height - 1);
MMPoint scan;
/* Note that |needle| is searched backwards, in accordance with the
* Boyer-Moore search algorithm. */
for (scan.y = lastPoint.y; ; --scan.y) {
for (scan.x = lastPoint.x; ; --scan.x) {
MMRGBHex ncolor = MMRGBHexAtPoint(needle, scan.x, scan.y);
MMRGBHex hcolor = MMRGBHexAtPoint(haystack, offset.x + scan.x,
offset.y + scan.y);
if (!MMRGBHexSimilarToColor(ncolor, hcolor, tolerance)) return 0;
if (scan.x == 0) break; /* Avoid infinite loop from unsigned type. */
}
if (scan.y == 0) break;
}
return 1;
}
/* --- Hash table helper functions --- */
static void addNodeToTable(UTHashTable *table,
MMRGBHex hexColor,
MMPoint offset)
{
struct shiftNode *node = getNewNode(table);
node->color = hexColor;
node->offset = offset;
UTHASHTABLE_ADD_INT(table, color, node, struct shiftNode);
}
static struct shiftNode *nodeForColor(UTHashTable *table,
MMRGBHex color)
{
struct shiftNode *uttable = table->uttable;
struct shiftNode *node;
HASH_FIND_INT(uttable, &color, node);
return node;
}