c# - How Can I Fix My Method To Scan large array of bytes for smaller arrays

Question

i want to create a method to scan arrays of bytes for a specific array i have already done this, but there is something else i want, i want to extend it so that it can scan arrays with some indexes being unknowns by replacing them with 256(0xff) e.g if i have an array like this [1,2,3,4,5,6,7,8,9,20,30,50] normally, i can search for [5,6,7] and it would index [4] because that is where 5 begins i want to be able to search for something like [5,256,7] which means if i dont know the actual value of 256, i would still get a correct answer

my solution is grab a chunk of 256/512 bytes,use a for loop to read a chunk of x bytes(in this case, 3 bytes), and replace 256 with the corresponding value of the corresponding index in the bytes being read

here is the code i have tried, but it isnt working properly

p.s, this method is meant to scan really big arrays that is why there are some large values

public long arraySearch(byte[] scanFor, long startIndex, long endIndex)
{
    if (scanFor.Length == 0 || startIndex == 0 || endIndex == 0 || endIndex 
<= startIndex - scanFor.Length) return 0;

    long tempStart = startAddress;
    long foundIndex = 0;
    long tmpAd = 0;

    long maxChunk = endIndex - startIndex;
    float parts = maxChunk / 256;

    int x = 0;
    byte[] tmp = new byte[scanFor.Length];
    byte[] buf = new byte[256];

    for (x = 0; x < parts; x++) 
    {
//the 'byte[] ReadArray(int64 index,int length)' method returns a byte array 
(byte[]) at the given index of the specified size
        buf = ReadArray(tempStart, 256);

        for (int i = 0; i < 256; i++)
        {

            if (buf[i] == scanFor[0])
            {
                tmp = ReadArray(tempStart + i, scanFor.Length);
                    for (int iii = 0; iii < scanFor.Length; iii++)
                    {
                        if (scanFor[iii] == 0xff) scanFor[iii] = tmp[iii];
                    }

                tmpAd = tempStart + i;
//the 'ByteArrayCompare' method compares all elements of an array and 
returns true if all are equal
                if (ByteArrayCompare(tmp, scanFor))
                {
                    foundIndex = tmpAd;
                    break;
                }
            }
        }
        tempStart += 256;
    }
    return foundIndex;
}

Answer 1

I find your code very confusing, so I can't tell you what's wrong with it, but I can try to explain a working solution, inspired by your attempt, for you.

First of all I created a few helper stuff, to simulate your environment - tell me if I understood something wrong (The parts are just there to simplify things for me):

private static readonly byte [] FirstPart = Enumerable.Repeat (1, 250).Select (i => (byte) i).ToArray ();
private static readonly byte [] SecondPart = Enumerable.Range (1, 250).Select (i => (byte) i).ToArray ();
private static readonly byte [] ThirdPart = Enumerable.Range (0, 250).Select (i => (byte) i).ToArray ();
private static readonly byte [] FourthPart = Enumerable.Repeat (1, 500).Select (i => (byte) i).ToArray ();

private static readonly byte [] WholeArray =
    new [] {FirstPart, SecondPart, ThirdPart, FourthPart}.SelectMany (bytes => bytes).ToArray ();

private static byte [] ReadArray (long index, int length) =>
    WholeArray.Where ((b, i) => i >= index && i < index + length).ToArray ();

Then this is the implementation of ArraySearch I came up with - I explained it in the comments, if something is unclear, feel free to ask:

public static long ArraySearch (byte [] scanFor, long startIndex, long endIndex)
{
    if (startIndex < 0 ||
        endIndex < startIndex ||
        scanFor.Length > endIndex - startIndex) //Check wether the parameters are valid
        return -1;

    if (scanFor.Length == 0) //If the scanFor is empty, we must return 0 directly, 
        //as an IndexOutOfRange exception would be caused otherwise
        return 0;

    var partsCount = (endIndex - startIndex) / 256; //The number of parts to scan

    long tempFoundIndex = -1; //The found index, that is later going to be returned

    for (var i = 0; i < partsCount; i++) //We iterate through the parts 
        //to find an item in those parts which matches the first item of the array we're searching for
    {
        var start = i * 256 + startIndex; //This is the startIndex of the current part
        if (start > endIndex) //If the start index is already bigger than the endIndex, we can directly break, 
            //because we won't find the array in the specified range anymore 
            break;
        var part = ReadArray (start, 256); //This is the part we're currently scanning

        for (var j = 0; j < part.Length && start + j <= endIndex; j++) //Now we're iterating this part
            //to find the item which matches the first item of the array we're searching for
            if (scanFor [0] == 0xFF || part [j] == scanFor [0]) //If we found such an item, 
                //we want to check all following items, wether they match the to search array as well
            {
                var arrayCheckFailed = false; //This indicates wether it already failed, 
                //so that it doesn't continue to search
                var tempScanForIndex = 0; //This is the index of the item from ScanFor we're currently checking
                tempFoundIndex = start + j; //This is the starting index we found 
                //and we later want to return, if all items match
                for (var i2 = i; i2 < partsCount && !arrayCheckFailed; i2++) 
                    //So we're once again iterating through the parts (beginning from the current part)
                    //to check the items from the parts
                {
                    var start2 = i2 * 256 + startIndex; //This is once again the startIndex of the current part
                    if (start2 > endIndex) //see above
                        break;
                    var part2 = ReadArray (start2, 256);//TODO RENAME
                    for (var j2 = i2 == i ? j : 0; j2 < part2.Length && start2 + j2 <= endIndex; j2++)
                        if (scanFor [tempScanForIndex] == 0xFF || part2 [j2] == scanFor [tempScanForIndex])
                        {
                            tempScanForIndex++; //If the current item matched, we want to check the next item
                            if (scanFor.Length <= tempScanForIndex) //And if we checked enough items, 
                                //we know that the array matches, so we can return the found index
                                return tempFoundIndex;
                        }
                        else
                        {
                            arrayCheckFailed = true; 
                                //If it didn't match we continue to search for a first item which matches
                            tempFoundIndex = -1; 
                            break;
                        }
                }
            }
    }
    return tempFoundIndex;
}

---

I tested this with this method:

private static void Main ()
{
    Console.Write (ArraySearch (ThirdPart.Select ((b, i) => i == 0 ? (byte) 0xFF : b).ToArray (), 0, 1100));
    Console.ReadLine ();
}

The output was 249, which seemd correct to me.

I couldn't test it in your environment, so please inform me, if something isn't working as it should.