CompressSearch algorithm

Question

I Rewrote all code, aimed at a variable reduction, and reduced complexity. removed all extraneous code unnecessary to the operation, reduced indexing surfaces, tests all work consistently. Added midpoint matching to search, combined Reader and Searching into a class.

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Drawing.Imaging;

namespace ActiveScreenMatch
{
    public unsafe class ThisScreenSearch
    {
        internal Bitmap BitmapToMap { get; }

        internal BitmapData BitmapToMapData { get; }

        private BiDirectionalReader DesktopReader { get; }

        /// <summary>
        /// Class reads bitmap and stores combined index of top,bot to midpoint and cache the resulting binary lines as Memory<bool>
        /// </summary>
        internal class BiDirectionalReader
        {
            internal int SetWidth { get; }
            internal int SetHeight { get; }
            private byte* Bits { get; }
            private int Stride { get; }
            internal List<(int TopIndex, int BottomIndex)> BiDirectionalIndex { get; }
            internal SortedList<int, Memory<bool>> CachedItems { get; }

            public BiDirectionalReader(byte* mapPointer, int mapWidth, int mapHeight, int mapStride)
            {
                Bits = mapPointer;
                SetWidth = mapWidth;
                SetHeight = mapHeight;
                Stride = mapStride;
                CachedItems = new SortedList<int, Memory<bool>>(SetHeight);
                BiDirectionalIndex = new List<(int, int)>();
                List<byte> Masks = new List<byte>();
                // PreProcess mask for line
                for (int x = 0; x < SetWidth - 1; x++)
                {
                    Masks.Add((byte)(0x80 >> (x & 0x7)));
                }

                // iterate forward and back over bitmap to create index and parse bytes to bools
                int top = -1, bot = SetHeight;
                while (++top <= (SetHeight - 1) / 2 && --bot >= (SetHeight - 1) / 2)
                {
                    // declare array to hold results
                    var topLine = new bool[SetWidth];
                    var botLine = new bool[SetWidth];
                    // iterate over the width of the bitmap on both lines
                    for (int x = 0; x < SetWidth - 1; x++)
                    {
                        var mask = Masks[x];
                        byte tret = *(Bits + (top * Stride) + (x >> 3));
                        byte bret = *(Bits + (bot * Stride) + (x >> 3));
                        tret &= mask;
                        bret &= mask;
                        topLine[x] = tret > 0;
                        botLine[x] = bret > 0;
                    }
                    // store index
                    BiDirectionalIndex.Add((top, bot));
                    // store lines parse in cache
                    CachedItems.Add(top, new Memory<bool>(topLine));
                    CachedItems.Add(bot, new Memory<bool>(botLine));
                }
            }
        }

        public Point CompressSearch(Bitmap target)
        {
            // parse the target bitmap using out reader
            var TargetData = target.LockBits(new Rectangle(0, 0, target.Width, target.Height), ImageLockMode.ReadOnly, PixelFormat.Format1bppIndexed);
            var TScan0 = TargetData.Scan0;
            var TargetReader = new BiDirectionalReader((byte*)TScan0, TargetData.Width, TargetData.Height, TargetData.Stride);
            // clean up.
            target.UnlockBits(TargetData);

            int FoundTop = -1;
            int FoundBottom = -1;

            // Parse the Index to check if top and bottom line contain set bits
            // probably not the most optimal solution, but it doesn't use linq
            foreach ((int TopIndex, int BottomIndex) in TargetReader.BiDirectionalIndex)
            {
                (Memory<bool> TopLine, Memory<bool> BottomLine) = (TargetReader.CachedItems[TopIndex], TargetReader.CachedItems[BottomIndex]);
                if (FoundTop == -1 && TopLine.Span.IndexOf(true) > -1)
                {
                    FoundTop = TopIndex;
                }
                if (FoundBottom == -1 && BottomLine.Span.IndexOf(true) > -1)
                {
                    FoundBottom = BottomIndex;
                }
                if (FoundTop > -1 && FoundBottom > -1)
                {
                    break;
                }
            }
            // if top and bottom are not -1 start searching.
            if (FoundTop > -1 && FoundBottom > -1)
            {
                // get target lines by the index found above
                var TargetTop = TargetReader.CachedItems[FoundTop];
                var TargetBottom = TargetReader.CachedItems[FoundBottom];
                // calculate the offset between top and bottom
                var Offset = FoundBottom - FoundTop;
                // if offset > 1 locate use the offset /2 as midpoint else return default line(all false)
                Memory<bool> TargetMid = Offset > 1 ? TargetReader.CachedItems[FoundTop + (Offset / 2)] : new Memory<bool>(new bool[TargetReader.SetWidth]);
                // Iterate over the provided index for the searched bitmap
                foreach ((int Top, int Bot) in DesktopReader.BiDirectionalIndex)
                {
                    // check index
                    // if index > - 1 slice to point and check for match on mid and bottom
                    var Index = DesktopReader.CachedItems[Top].Span.IndexOf(TargetBottom.Span);
                    if (Index > -1
                        && DesktopReader.CachedItems[Top - (Offset / 2)].Span.Slice(Index).IndexOf(TargetMid.Span) == 0
                        && DesktopReader.CachedItems[Top - Offset].Span.Slice(Index).IndexOf(TargetTop.Span) == 0)
                    {
                        return new Point(Index + (TargetReader.SetWidth / 2), Top - (TargetReader.SetHeight / 2));
                    }
                    Index = DesktopReader.CachedItems[Bot].Span.IndexOf(TargetTop.Span);
                    if (Index > -1
                        && DesktopReader.CachedItems[Bot + (Offset / 2)].Span.Slice(Index).IndexOf(TargetMid.Span) == 0
                        && DesktopReader.CachedItems[Bot + Offset].Span.Slice(Index).IndexOf(TargetBottom.Span) == 0)
                    {
                        return new Point(Index + (TargetReader.SetWidth / 2), Bot + (TargetReader.SetHeight / 2));
                    }
                }
            }
            return default;
        }

        public ThisScreenSearch(Bitmap desktop)
        {
            BitmapToMap = desktop ?? throw new ArgumentNullException(nameof(desktop));
            BitmapToMapData = desktop.LockBits(new Rectangle(0, 0, desktop.Width, desktop.Height), ImageLockMode.ReadOnly, PixelFormat.Format1bppIndexed);
            var DScan0 = BitmapToMapData.Scan0;
            DesktopReader = new BiDirectionalReader((byte*)DScan0, BitmapToMapData.Width, BitmapToMapData.Height, BitmapToMapData.Stride);
            BitmapToMap.UnlockBits(BitmapToMapData);
        }
    }
}

How it can be used.

        var p = new ThisScreenSearch(NativeMethods.PrintWindow())
            .CompressSearch(NativeMethods.GetBlackWhiteAt(new Point(1815,1044), new Size(16,16)));

It probably won't handle odd-sized bitmaps. But I am happy with the success so far.

Thank you for reading this and bearing with me as I sorted it out.

Answer 1

In the BiDirectionalReader constructor, the while loop condition can be shortened to while (++top <= --bot) (or replaced with a for loop). If the bitmap height is odd, the middle row will have duplicate entries in CachedItems.

It is unclear to me why you're excluding the last column when constructing the BiDirectionalIndex and CachedItems data.

The three duplicated statements in the inner for loop can be reduced to one line each:

topLine[x] = (Bits[top * Stride + (x >> 3)] & mask) != 0;
botLine[x] = (Bits[bot * Stride + (x >> 3)] & mask) != 0;

The declaration (Memory<bool> TopLine, Memory<bool> BottomLine) in CompressSearch would be more readable if written as two separate declarations, which also allows easy use of var:

var TopLine = TargetReader.CachedItems[TopIndex];
var BottomLine = TargetReader.CachedItems[BottomIndex];

The if (FoundTop > -1 && FoundBottom > -1) check could be split up and moved into the two earlier ifs. This would allow for only checking one value (since you just assigned one value, you only need to check the other), and would then only do this check when it needs to be done, rather than every loop iteration.

There is a bit of inconsistency in the naming style, as sometimes your identifiers start with a capital letter, other times lowercase. I had initially though this was a distinction between member variables and parameters or local variables, but I see this is not the case.

Answer 2

I am not familiar with C#.

Here are some of my observations:

1. ++top <= (SetHeight - 1) / 2 && --bot >= (SetHeight - 1) / 2 is hard to read for two reasons:

   1. There are inline pre-/post-increments (++top and --bot)
      • Short circuiting may make the behaviour not obvious for beginners
   2. There are two conditions (++top <= (SetHeight - 1) / 2 and --bot >= (SetHeight - 1) / 2)
      • what it is checking is not obvious
      • I would replace it with:

++top
isBottomHalf = (top <= (SetHeight - 1) / 2)

if (isBottomHalf) {
    --bot
    isTopHalf = (bot >= (SetHeight - 1) / 2)
    if (isTopHalf) {
        // your code here
    }
}

2. I found it odd that some variables start with capitals (Bits, SetWidth, ...) and some with lowercase (topLine, botLine, ...)

3. The naming is inconsistent: topLine/botLine and tret/bret (the latter should be topRet/botRet)

Answer 3

This is the nth version, it is broken down into smaller functions, but uses more CPU to operate. I took the above advice to reduce comparisons and also attacked the Collections namespace and And Tuples.

I also changed it from eagerly parsing the entire bitmap search area upfront to only parsing 4 lines at a time.

In an attempt to make it more readable, I broke down operations that could take 1 line into multiline statements.

Small improvements over last version.updates: Fourth Cache Line(QuadCache) Coding conventions followed, removed stackalloc and resulting copy from the stack, added summaries and comments.

using System;
using System.Drawing;
using System.Drawing.Imaging;
using NoAlloq;

namespace SlidingBitmap
{
    /// <summary>
    /// Ref struct reads bitmap and stores boolean caches of input to search for, and iterates over the internal bitmap passed in constructor
    /// Expanding Span with some NoAllog's Linq functionality for Span
    /// </summary>

    public ref struct SlidingBitmapCache
    {
        /// <summary>
        /// QuadCache holds Spans to 4 blocks of memory
        /// </summary>
        private ref struct QuadCache
        {
            public Span<bool> CacheFirst;
            public Span<bool> CacheSecond;
            public Span<bool> CacheThird;
            public Span<bool> CacheFourth;

            public QuadCache(Span<bool> cacheFirst, Span<bool> cacheSecond, Span<bool> cacheThird, Span<bool> cacheFourth)
            {
                CacheFirst = cacheFirst;
                CacheSecond = cacheSecond;
                CacheThird = cacheThird;
                CacheFourth = cacheFourth;
            }
        }

        // Desktop QuadCache
        private QuadCache DesktopCache;

        // Target QuadCache
        private QuadCache TargetCache;

        // Storage for localizing the Bitmaps width passed in Constructor to SlidingBitmapCache
        private readonly int DesktopWidth;
        // Indexes for Desktop and Target bitmaps
        private Span<int> DesktopIndexes;
        private Span<int> TargetIndexes;

        // Storage for holding the Locked Bitmap Data for unlocking 
        // I can't unlock bits unless I cache input from the constructor, 
        // caching leads to parsing entire bitmap upfront, not the path I want to take.
        private BitmapData DesktopData { get; }

        /// <summary>
        /// SlidingBitmapCache 
        /// Initializes all the necessary variables Start the operation 
        /// </summary>
        /// <param name="desktop"></param>
        public SlidingBitmapCache(Bitmap desktop)
        {
            DesktopData = desktop.LockBits(new Rectangle(0, 0, desktop.Width, desktop.Height), ImageLockMode.ReadOnly, PixelFormat.Format1bppIndexed);

            DesktopWidth = desktop.Width;

            DesktopIndexes = new int[4] { 0,  1, desktop.Height - 2, desktop.Height - 1 };

            TargetIndexes = new int[4] { 0, 0, 0, 0 };

            DesktopCache = new QuadCache(new Span<bool>(new bool[DesktopWidth]),
                                         new Span<bool>(new bool[DesktopWidth]),
                                         new Span<bool>(new bool[DesktopWidth]),
                                         new Span<bool>(new bool[DesktopWidth]));

            TargetCache = new QuadCache(Span<bool>.Empty,
                                        Span<bool>.Empty,
                                        Span<bool>.Empty,
                                        Span<bool>.Empty);

            CacheLinesAt(DesktopData, DesktopIndexes, DesktopCache);
        }

        /// <summary>
        /// CacheLinesAt 
        /// copies lines referenced by indexes in data to cache
        /// </summary>
        /// <param name="data"></param>
        /// <param name="indexes"></param>
        /// <param name="cache"></param>
        private void CacheLinesAt(BitmapData data, Span<int> indexes, QuadCache cache)
        {
            var dataStride = data.Stride;
            // iterate over the width of the bitmap on all lines
            for (int x = 0; x <= data.Width - 1; x++)
            {
                unsafe
                {
                    byte* ptr = (byte*)data.Scan0;
                    byte* calcPtr = ptr + (indexes[0] * dataStride) + (x >> 3);
                    byte firstRet = *calcPtr;
                    calcPtr = ptr + ((indexes[1]) * dataStride) + (x >> 3);
                    byte secondRet = *calcPtr;
                    calcPtr = ptr + (indexes[2] * dataStride) + (x >> 3);
                    byte thirdRet = *calcPtr;
                    calcPtr = ptr + (indexes[3] * dataStride) + (x >> 3);
                    byte fourthRet = *calcPtr;
                    byte Mask = (byte)(0x80 >> (x & 0x7));
                    firstRet &= Mask;
                    secondRet &= Mask;
                    thirdRet &= Mask;
                    fourthRet &= Mask;
                    cache.CacheFirst[x] = firstRet > 0;
                    cache.CacheSecond[x] = secondRet > 0;
                    cache.CacheThird[x] = thirdRet > 0;
                    cache.CacheFourth[x] = fourthRet > 0;
                }
            }
        }

        /// <summary>
        /// GetLineAt is used for inline repositioning of a Single Cache line.
        /// Works the same as above.
        /// </summary>
        /// <param name="data"></param>
        /// <param name="index"></param>
        /// <param name="cache"></param>
        private void GetLineAt(BitmapData data, int index, Span<bool> cache)
        {
            unsafe
            {
                void* ptr = (byte*)data.Scan0;
                // iterate over the width of the bitmap on both lines
                for (int x = 0; x <= data.Width - 1; x++)
                {
                    byte ret = *((byte*)ptr + (index * data.Stride) + (x >> 3));
                    ret &= (byte)(0x80 >> (x & 0x7));
                    cache[x] = ret > 0;
                }
            }
        }

        /// <summary>
        /// GetGoodCacheLinesAt is designed for pulling cache lines with bits set for top and bottom Cache Lines
        /// as well as setting 2nd and 3rd lines.
        /// </summary>
        /// <param name="target"></param>
        /// <returns name ="Span<int>"></returns>
        private Span<int> GetGoodCacheLines(Bitmap target)
        {
            int targetWidth = target.Width;
            int targetHeight = target.Height - 1;
            TargetIndexes = new int[] { 0, 1, targetHeight -2, targetHeight -1 };
            TargetCache = new QuadCache(new Span<bool>(new bool[targetWidth]),
                                        new Span<bool>(new bool[targetWidth]),
                                        new Span<bool>(new bool[targetWidth]),
                                        new Span<bool>(new bool[targetWidth]));

            Span<int> result = new int[] { -1, -1, -1, -1 };

            BitmapData Data = target.LockBits(new Rectangle(0, 0, targetWidth, targetHeight), ImageLockMode.ReadOnly, PixelFormat.Format1bppIndexed);

            while (TargetIndexes[1] <= (target.Height - 1) / 2)
            {
                CacheLinesAt(Data, TargetIndexes, TargetCache);

                if (result[0] == -1 && TargetCache.CacheFirst.AnyTrue())
                {
                    result[0] = TargetIndexes[0];
                }

                if (result[3] == -1 && TargetCache.CacheFourth.AnyTrue())
                {
                    result[3] = TargetIndexes[3];
                }

                if( result[0] > -1 && result[3] > -1)
                {
                    target.UnlockBits(Data);
                    result[1] = TargetIndexes[1];
                    result[2] = TargetIndexes[2];
                    return result;
                }

                ++TargetIndexes[0];
                ++TargetIndexes[1];
                --TargetIndexes[2];
                --TargetIndexes[3];
            }
            target.UnlockBits(Data);
            return result;
        }
        // TODO:
        /// <summary>
        /// Check 4  Cached lines of target against that of search area
        /// offsets desktop caches to find matches restoring changes
        /// I want to avoid allocations and copying here as much as feasible
        /// </summary>
        /// <param name="offsets"></param>
        private Point CheckCaches(Span<int> offsets)
        {
            int firstIndex = DesktopCache.CacheFirst.IndexOf(TargetCache.CacheFourth);
            if (firstIndex > -1)
            {

            }
            int secondIndex = DesktopCache.CacheSecond.IndexOf(TargetCache.CacheFourth);
            if (secondIndex > -1)
            {

            }
            int thirdIndex = DesktopCache.CacheThird.IndexOf(TargetCache.CacheFirst);
            if (thirdIndex > -1)
            {

            }
            int fourthIndex = DesktopCache.CacheFourth.IndexOf(TargetCache.CacheFirst);
            if (fourthIndex > -1)
            {

            }
            return default;
        }

        /// <summary>
        /// The public API for 
        /// this takes target bitmap and iterates of iternal search area
        /// checking the cache at each iteration
        /// </summary>
        /// <param name="target"></param>
        /// <returns>Point</returns>
        public Point LineCachingSearch(Bitmap target)
        {
            Span<int> indexes = GetGoodCacheLines(target);
            while (DesktopIndexes[1] <= (DesktopData.Height - 2) / 2)
            {
                if (CheckCaches(indexes) == default)
                {
                    ++DesktopIndexes[0];
                    ++DesktopIndexes[1];
                    --DesktopIndexes[2];
                    --DesktopIndexes[3];
                    CacheLinesAt(DesktopData, DesktopIndexes, DesktopCache);
                }
            }
            return default;
        }
    }
}

Not complete, just POC, Search algorithm with NoAlloq LINQ on Span forthcoming.