Search a string buffer with nulls (chr(0))

[!NoItAll]

I need to search a buffer for a string of characters.
The buffer is essentially a binary file (it's an image) and contains lots of chr(0) characters.
The string I need to locate also contains chr(0) characters. In fact it is the following string:
chr(100) & chr(0) & chr(0) & chr(163)

This is a marker in the image file for items I need to process.
So I though I would do the following:

Dim sFileBuffer as String  = system.io.file.readalltext("myimagefile")
Dim sLookFor as String = chr(100) & chr(0) & chr(0) & chr(163)
 
Dim iLocation as Integer = sFileBuffer.IndexOf(sLookFor)
 

The problem is that, although the characters in sLookFor definitely exist inside of sFileBuffer - IndexOf will always return -1 (not found).

I tried the following:

Dim Marker() as Byte = {100, 0, 0 , 163}
Dim sLookFor as String = System.Text.Encoding.UTF8.GetString(Marker)
Dim sFileBuffer as String  = system.io.file.readalltext("myimagefile",  Encoding.UTF8)
 
Dim iLocation as Integer = sFileBuffer.IndexOf(sLookFor)
 

But this appears to only find occurrences of Chr(100) & Chr(0) - not the full 4 character sequence I desire. It appears to see the second Chr(0) as a termination of the search string.

I think the sticking point here is the null. Yes - I can string.replace(chr(0), Chr(255)) in both the sLookFor and the sFileBuffer and adjust my search accordingly - but that seems like a mess to me.

Is there not a way to search a buffer of binary data? I've tried working with byte arrays - but there appears to be no way to easily search for a sequence of byte values - just individual elements in the array.

VB6 did this perfectly just using strings.

[tlhintoq]

I can't speak to VB6 doing this, but a string by definition is unicode terminated with a chr(0)
http://msdn.microsoft.com/en-us/libr...em.string.aspx
http://msdn.microsoft.com/en-us/libr...67(VS.85).aspx

So you have two issues:
1) your single bytes are being turned into two-byte unicode characters when the string is made, so your string no longer properly represents your bytes.
2) The first char(0) is the termination of the string

[!NoItAll]

Ok - I will now answer my own question - and maybe someone will say - No - not that way dummy!
It appears that the way VB.NET stores strings is very different from the way VB6 did (DUH!). So reading a file into a string variable using file.readalltext like this:

Dim MyFileData as String = System.IO.File.FeadAllText("mybinaryfile.bin")

encodes the data accurately, but differently than assigning characters to a string like:

Dim MySearchString as String = Chr(100) & Chr(0) & Chr(0) & Chr(163)

So you really will never find it using:

Dim iLocation as Integer = MyFileData.IndexOf(MySearchString)

This is because the data in MyFileData and MySearchString is not encoded the same way into their respective string variables.

Instead what you must do is make sure that both strings are encoded into the string variable identically. Do it this way:

Dim MySearchString as String = (Chr(100) & Chr(0) & Chr(0) & Chr(163)).Normalize
Dim MyFileData as String = System.IO.File.ReadAllText("mybinaryfile.bin", Encoding.Default).Normalize
 
Dim iLocation as Integer = MyFileData.IndexOf(MySearchString)
 
 

This will return what you are looking for: binary data in the string variable. Both strings have been normalized to the same Unicode encoding scheme. There are options for the String.Normalize method - but you really don't care what they are as long as BOTH strings are encoded identically.

The Normalize method does the trick without mucking up your code.

[!NoItAll]

@tlhintoq
Funny - I saw your response after I posted my solution. QA TLHO'
We are clearly on the same page - however it does appear that VB.NET strings can contain chr(0) characters and still be used (including those annoying little nulls) provided you are aware of how it is encoded. I'm not entirely sure exactly what VB.NET does with the ReadAllText method because I have to explicitly call ReadAllText("mybinaryfile.bin", Encoding.Default). Apparently Encoding.Default is not the default encoding used by ReadAllText, because if I fail to use the Encoding.Default parameter my comparisons will fail - even though I String.Normalize the result.
In the end I think there are a lot of variables at play here and I've likely just come up with a relatively superficial solution. My goal was to keep the code simple and clean - avoiding making string copies all over the place.
I think, if I had a longer string to search for I would have to pay closer attention to how the String.Normalize method worked on it - I'm outa my league here though.

Des

[tlhintoq]

I personally think the real answer is to lot look for strings, don't convert to strings, don't muddle the data.

Why don't you want to just search the byte[] for the pattern you are looking for?

[!NoItAll]

I would love to - but I have not found any way to search for a sequence of bytes in a byte array. All of the built-in .net functionality for searching in arrays is about finding single elements, not a sequence of elements.
Perhaps I've just not looked hard enough..

[tlhintoq]

All of the built-in .net functionality

built-in

Who said "built-in"? Make your own.

Loop through the target array looking for the first byte
Upon finding it, you loop through the rest of your comparrison array checking if each item matches. If you get through the entire comparator then you have a match.

Its just a loop with one nested loop inside.

[!NoItAll]

I think it's a little more complicated then that - however I take your point and wrote the following comparison...
Now I did not spend a lot of time optimizing the code - and someone who knows better can probably reduce this a lot - however I need to keep two counters, one for loop for the main text and another for the text I'm looking for. All of this inside a Do Loop to iterate through the main text.
Frankly, this works much faster then I thought it would.
The stopwatch, however shows that the first time through the FindStrInArray it takes about 7 or 8 times longer than the simple string.indexof function.
However - the second time through it is about 3 times FASTER then the string.indexof function.

Now I know the exercise was about searching BINARY data and my example uses just text - however I have done all of the same things you must do for it to work with binary data - that is to explicity set the encoding on both the data I am searching and the data I am searching for. Of course you don't need to do this with the byte array.

If anyone wants to run this just create a form with a single button and paste this into your form code. Don't get fancy and rename the form or button...
You will need the declaration.txt file that is attached. It's read from the D: drive on my machine - you can put it anywhere you like.

Public Class Form1
 
    Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
 
        Dim sDecl As String = System.IO.File.ReadAllText("d:\decli\Declaration.txt", System.Text.Encoding.Default).Normalize
        Dim byteDecl() As Byte = System.IO.File.ReadAllBytes("d:\decli\Declaration.txt")
        Dim sFindMe As String = ("abolishing the free System of English Laws").Normalize
        Dim byteFindMe() As Byte = System.Text.ASCIIEncoding.ASCII.GetBytes("abolishing the free System of English Laws")
        Dim iLocation As Integer = 0
        Dim StopWatch As New System.Diagnostics.Stopwatch
        'Which is faster?
        'this
 
        StopWatch.Start()
        iLocation = sDecl.IndexOf(sFindMe)
        StopWatch.Stop()
 
        MsgBox(iLocation.ToString & Environment.NewLine & StopWatch.Elapsed.ToString)
 
        StopWatch.Reset()
 
        'reset ilocation
        StopWatch.Start()
        iLocation = FindStrInArray(byteDecl, byteFindMe)
        StopWatch.Stop()
 
        MsgBox(iLocation.ToString & Environment.NewLine & StopWatch.Elapsed.ToString)
 
        StopWatch.Reset()
        'or this
 
    End Sub
    Friend Function FindStrInArray(ByVal LookIn() As Byte, ByVal Find() As Byte) As Integer
 
        Dim J As Integer = 1
        Dim I As Integer = 0
        Dim iLocation As Integer = 0
 
        Do While J < Find.Length
            'find the first char
            iLocation = Array.IndexOf(LookIn, Find(0), iLocation)
            'if the first char was found then look for the rest
            If iLocation > -1 Then
                iLocation += 1
                For I = iLocation To (iLocation + (Find.Length - 2))
                    If LookIn(I) <> Find(J) Then
                        J = 1    'return J to 0 since we have to start all over with the next occurance of the first char
                        Continue Do
                    End If
                    J += 1
                Next
                Return (iLocation - 1)
            Else
                'it was not found anywhere
                Exit Do
            End If
        Loop
 
        Return -1
 
    End Function
End Class
 

This was a fun exercise - but unless the loop-search function can be improved to work considerably faster than the string.indexof function then I'm not thinking its worth it. The loop is faster only when you call it multiple times to do the same thing - whereas the simpler approach is faster for each original call. And last, but certainly not least, the simpler call is just that, less code, cleaner and much easier to maintain - provided you understand the use and that each string must be explicitly encoded identically when you intend to do searches of binary data.

[tlhintoq]

The stopwatch, however shows that the first time through the FindStrInArray it takes about 7 or 8 times longer than the simple string.indexof function.
However - the second time through it is about 3 times FASTER then the string.indexof function.

Take a good read through the MSDN of the Stopwatch class. The first use of a stopwatch (or the first use after it has not been used in a while) is not reliable.

One has to use the stopwatch, throw out those results. Then use it for real. Honest.

[tlhintoq]

Its just a loop with one nested loop inside.

I think it's a little more complicated then that

Here is a C# version of what I was suggesting. One loop inside another

// Returns the value of the NEXT byte after the match
// Or -1 if no match
        public int ReturnLocationAfterFound(byte[] SearchBytes, byte[] Targetbytes)
        {
            for (int a = 0; a < Targetbytes.Length; a++)
            {
                // Search the length of the target array
                if (Targetbytes[a] == SearchBytes[0])
                {
                    // We found a match to the first byte of our comparitor
                    // Do all the rest match?
                    for (int b = 0; b < SearchBytes.Length; b++)
                    {
                        bool WeHaveAWinner = false;
                        if (Targetbytes[a + b] == SearchBytes[b])
                        {
                            WeHaveAWinner = true;// Keeps setting to true as long as they match
                        }
                        else
                        {
                            WeHaveAWinner = false;
                            break;// break out of the 'b' loop since it doesn't match
                        }
                        if (WeHaveAWinner) return a + b;// this is the location right after our match
                    }
                }
            }
            // If we got this far there was no match
            return -1;
        }
 

• The outter loop (the 'a' loop) is going through your big array one position at a time.
• If a match is found to the first byte of your search pattern then it will fall into the inner loop (the 'b' loop)
• From there it will check every byte of the search pattern in sequence to the next position of the big array.
• If at any point they fail to match we break out of the inner loop, putting us back into the outter loop, moving on to the next byte of the big array.
• If we get all the way through the inner loop, then we have a complete match and we return the next position after the matching section, since that is where you said you wanted to start processing.

[!NoItAll]

Oh my - so we could ask the question:
"When is a stopwatch not a stopwatch?"
Answer: "When Microsoft builds it." cue laughter and applause...
Not being a C# person I can still appreciate the superior elegance of your approach. It does, however, look as though it will return a+b as soon as it just finds a match to the first char in TargetBytes.
Would you not need Continue For (or the C# equivalent) after WeHaveAWinner = True? Also - just return a once b = (searchbytes.length-1). I don't see a need for the booleans.

in VB it would look like this:

Public Function ReturnLocationAfterFound(ByVal SearchBytes As Byte(), ByVal Targetbytes As Byte()) As Integer
        For a As Integer = 0 To (Targetbytes.Length - 1)
            ' Search the length of the target array
            If Targetbytes(a) = SearchBytes(0) Then
                ' We found a match to the first byte of our comparitor
                ' Do all the rest match?
                For b As Integer = 0 To (SearchBytes.Length - 1)
                    Dim WeHaveAWinner As Boolean = False
                    If Targetbytes(a + b) = SearchBytes(b) Then
                        If b = (SearchBytes.Length - 1) Then
                            Return a
                        End If
                        Continue For
                    Else
                        ' break out of the 'b' loop since it doesn't match
                        Exit For
                    End If
                Next
            End If
        Next
        ' If we got this far there was no match
        Return (-1)
    End Function
 

When I run the unreliable stopwatch this routine in VB now takes less time than my less elegant solution - so this looks really good.
I think I will keep this arrow in my quiver!

Des

[tlhintoq]

It does, however, look as though it will return a+b as soon as it just finds a match to the first char in TargetBytes.

Yep. That return should have been moved down to lines so it was outside the 'b' loop. Correction below

// Returns the value of the NEXT byte after the match
// Or -1 if no match
        public int ReturnLocationAfterFound(byte[] SearchBytes, byte[] Targetbytes)
        {
            for (int a = 0; a < Targetbytes.Length; a++)
            {
                // Search the length of the target array
                if (Targetbytes[a] == SearchBytes[0])
                {
                    // We found a match to the first byte of our comparitor
                    // Do all the rest match?
                    for (int b = 0; b < SearchBytes.Length; b++)
                    {
                        bool WeHaveAWinner = false;
                        if (Targetbytes[a + b] == SearchBytes[b])
                        {
                            WeHaveAWinner = true;// Keeps setting to true as long as they match
                        }
                        else
                        {
                            WeHaveAWinner = false;
                            break;// break out of the 'b' loop since it doesn't match
                        }
                    }
                       // Yep, this should have been outside of the 'for' loop construct
                        if (WeHaveAWinner) return a + b;// this is the location right after our match
                }
            }
            // If we got this far there was no match
            return -1;
        }

Would you not need Continue For (or the C# equivalent)

Nope. Everything within the curly braces is the 'for' loop. No need to specify a 'continue'. As a matter of fact your placement of the DIM Bool and Continue seem odd to me, but I'm not a VB guy. to me it looks as if the bool will get reintialized to false every loop through b, plus the continue is in the middle of the If...Then... Else... Doesn't that mean the "continue for' get's run before the 'else' clause of the 'if', and therefore the loop starts all over without ever executing the 'else' condition. Basically making the else clause unreachable?

<more studying of your VB translation>

Ok, I think I get what you've done. Ok, yeah...The way you've done it the bool is not used. Just a little difference in programming style but they both get the job done. We both have 3 'if' conditions, I just prefer to not have two inside the inner loop, because they both get evaluated on every pass through the loop. I don't think the difference in processing time of one or two 'if' checks is ever going to make a detectable difference. You'd have to be searching for a signature of a 1000 bytes, and doing it 1000 times to see much of a reduction in performance.

By returning 'a' you are returning the start position of the matching set of bytes.
By returning 'a + b' you are return the start position of the bytes *after* the matching set of bytes. I guess it just depends on what you are looking for.

I thought the goal was to process everything *after* the 'signature' you were looking for, so that's why I went with returning a+b.

Not being a C# person I can still appreciate the superior elegance of your approach.

I appreciate the kind words, but I think your take on the approach is every bit as good and clean. Keep up the good work.