search in byte array

[Frank]

Hello,
I have a byte array (byte[]) and want to search for 3 bytes next to each
other containing 0x10, 0x12 and 0x16. Is there some method for that?
Thanks
Frank

 

[Alberto Poblacion]

I have a byte array (byte[]) and want to search for 3 bytes next to each
other containing 0x10, 0x12 and 0x16. Is there some method for that?

No "easy" way. Since the array does not have any type of indexes, any
search method will ultimately loop through the contents of the array. So you
might as well write the search yourself:

byte[] ba = ...
for (int i=0; i<ba.Length-2; ba++)
{
if (ba==0x10 && ba[i+1]==0x12 && ba[i+2]==0x16)
{
//Found at position i.
}
}

 

[Frank]

Thanks Alberto,
but it's not the answer I was hoping for, of course I thought of this
solution.. I was looking for something like 'contains'.
Regards
Frank

I have a byte array (byte[]) and want to search for 3 bytes next to each
other containing 0x10, 0x12 and 0x16. Is there some method for that?

No "easy" way. Since the array does not have any type of indexes, any
search method will ultimately loop through the contents of the array. So
you might as well write the search yourself:

byte[] ba = ...
for (int i=0; i<ba.Length-2; ba++)
{
if (ba==0x10 && ba[i+1]==0x12 && ba[i+2]==0x16)
{
//Found at position i.
}
}

 

[=?ISO-8859-1?Q?G=F6ran_Andersson?=]

Thanks Alberto,
but it's not the answer I was hoping for, of course I thought of this
solution.. I was looking for something like 'contains'.
Regards
Frank

You can use the Array.IndexOf method to locate one value.

I have a byte array (byte[]) and want to search for 3 bytes next to each
other containing 0x10, 0x12 and 0x16. Is there some method for that?

No "easy" way. Since the array does not have any type of indexes, any
search method will ultimately loop through the contents of the array. So
you might as well write the search yourself:

byte[] ba = ...
for (int i=0; i<ba.Length-2; ba++)
{
if (ba==0x10 && ba[i+1]==0x12 && ba[i+2]==0x16)
{
//Found at position i.
}
}

 

[Alberto Poblacion]

it's not the answer I was hoping for, of course I thought of this
solution.. I was looking for something like 'contains'.

My point is that even if there were something like Contains, it would
not be more efficient than the search in a loop, since the internal
implementation of "contains" would have to perform precisely the same
operation.
"Contains" would make the source code clearer, but if making the code
clearer is what you want, you can always write your own "Contains" and add
it to the project, then call your own Contains.

The only thing that I can think that would (maybe) speed up the search is
to use unsafe code to treat groups of bytes as a single int, use "&" to
clear the remaining byte, and do the three-byte comparison in a single step.
I don't think that such an ugly solution is worth the minor improvement in
speed.

 

[Peter K]

You can use the Array.IndexOf method to locate one value.

Hi - this question peaked my interest, not that I can offer any help, but I
was wondering if something like the Boyer-Moore algorithm could be used?

 

[Guest]

The only other thing I can think of is to convert the byte array to a string
and then you can use the .IndexOf static method to find your "3 character"
substring.
Peter

 

[Frank]

yes I am using that. But conversion takes time (although in my app not that
important)
Frank

The only other thing I can think of is to convert the byte array to a
string
and then you can use the .IndexOf static method to find your "3 character"
substring.
Peter

--
Site: http://www.eggheadcafe.com
UnBlog: http://petesbloggerama.blogspot.com
Short urls & more: http://ittyurl.net

Hello,
I have a byte array (byte[]) and want to search for 3 bytes next to each
other containing 0x10, 0x12 and 0x16. Is there some method for that?
Thanks
Frank

 

[Peter Duniho]

Hi - this question peaked my interest, not that I can offer any help,
but I was wondering if something like the Boyer-Moore algorithm could
be used?

How many times do you (that is, the original poster) have to search the
array?

If just once, then nothing will be more efficient than just searching
through the string explicitly as suggested.

If more than once, yes...you may be able to take advantage of more
complicated algorithms (such as B-M). You have to trade off the cost of
preprocessing the array with the nominal cost of doing a search. In
general, I would expect more complicated algorithms to be worthwhile only
when you are doing repeated searches *and* the arrays being searched are
lengthy.

Pete

 

[Jon Skeet [C# MVP]]

Hi - this question peaked my interest, not that I can offer any help, but I
was wondering if something like the Boyer-Moore algorithm could be used?

Absolutely. I think Boyer-Moore tends to be used for text, but as far
as I'm aware it could search for any sequence within another sequence,
where appropriate equality comparisons are defined.

 

[Jon Skeet [C# MVP]]

My point is that even if there were something like Contains, it would
not be more efficient than the search in a loop, since the internal
implementation of "contains" would have to perform precisely the same
operation.

Not necessarily. It could, potentially, use something like the Boyer-
Moore algorithm. It would only be worth doing so in certain cases, but
that kind of thing would be possible. Of course, you could implement it
in your own code as well...

 

[Peter Duniho]

yes I am using that. But conversion takes time (although in my app not
that important)

You should not have to convert to String. The Array class itself has an
IndexOf() method.

 

[Jon Skeet [C# MVP]]

You should not have to convert to String. The Array class itself has an
IndexOf() method.

But that only looks for a single value. What's required here is to
search for a *sequence* of bytes, and there's nothing built-in which
does that simply (whereas string.IndexOf(string) searches for a
sequence of characters within a string).

There are other reasons not to use a string conversion though, such as
possible data loss/inaccuracy.

 

[Alberto Poblacion]

My point is that even if there were something like Contains, it would
not be more efficient than the search in a loop [...]

Not necessarily. It could, potentially, use something like the Boyer-
Moore algorithm.

Maybe for a generic comparison, but in this case where you are seeking a
specific sequence of three bytes, the proposed comparison:
if (ba==0x10 && ba[i+1]==0x12 && ba[i+2]==0x16)
is going to be extremely fast: a good compiler should be able to
optimize it into 9 machine code instructions on an i386 (load accumulator
from [register+n], compare accumulator with constant, jump if not zero to
next iteration. For most of the loops, only one of the three comparisons
would be executed and the other two skipped. Our worst case would require
O(n*3) comparisons, but the typical case would only require O(n). Even
though the Boyer-Moore algorithm under ideal conditions can reduce the
number of comparisons to O(n/m), which is O(n/3) in this particuar case,
there is no way that the implementation of the algorithm itself is going to
take less than the 6 machine instructions per loop that it could potentially
save.

 

[Peter Duniho]

But that only looks for a single value. What's required here is to
search for a *sequence* of bytes, and there's nothing built-in which
does that simply (whereas string.IndexOf(string) searches for a
sequence of characters within a string).

I agree that it's not as convenient as the String version of the method,
but using recursion one can easily and elegantly accomplish the same thing
using the Array version. I got the impression that ease of maintenance
was more important to the OP that performance, thus the recommendation.
Using IndexOf allows him to write the code in just a couple of lines,
rather than having to write out the nested loops that the explicit
algorithm would require.

There are other reasons not to use a string conversion though, such as
possible data loss/inaccuracy.

Agreed, and I should have mentioned that as well. I don't think it's
appropriate to try to shoe-horn a numerical array into something that is
(especially in .NET) fundamentally text-based. There's too many ways that
can go wrong; definitely the opposite of maintainable, IMHO.

Pete

 

[Jon Skeet [C# MVP]]

Not necessarily. It could, potentially, use something like the Boyer-
Moore algorithm.

Maybe for a generic comparison, but in this case where you are seeking a
specific sequence of three bytes, the proposed comparison:
if (ba==0x10 && ba[i+1]==0x12 && ba[i+2]==0x16)
is going to be extremely fast: a good compiler should be able to
optimize it into 9 machine code instructions on an i386 (load accumulator
from [register+n], compare accumulator with constant, jump if not zero to
next iteration. For most of the loops, only one of the three comparisons
would be executed and the other two skipped. Our worst case would require
O(n*3) comparisons, but the typical case would only require O(n). Even
though the Boyer-Moore algorithm under ideal conditions can reduce the
number of comparisons to O(n/m), which is O(n/3) in this particuar case,
there is no way that the implementation of the algorithm itself is going to
take less than the 6 machine instructions per loop that it could potentially
save.

I'm not sure - it depends on the cost of fetching data compared with
processing that data. I guess the cache is likely to deal with it to a
large extent. Certainly picking up a general case, analysing it and
coming up with the appropriate data would be costly, but in this
*specific* case we could probably write out the B-M algorithm
"longhand" fairly easily.

It would be interesting to benchmark, if I had the time.

 

[Jon Skeet [C# MVP]]

I agree that it's not as convenient as the String version of the method,
but using recursion one can easily and elegantly accomplish the same thing
using the Array version. I got the impression that ease of maintenance
was more important to the OP that performance, thus the recommendation.
Using IndexOf allows him to write the code in just a couple of lines,
rather than having to write out the nested loops that the explicit
algorithm would require.

There's no nested loop in the code posted by Alberto - it looks like a
pretty simple way of doing things to me.

I'm not sure I quite see how your IndexOf solution would be simpler,
but I could well be missing a trick. If you've got the time, could you
post some sample code?

Agreed, and I should have mentioned that as well. I don't think it's
appropriate to try to shoe-horn a numerical array into something that is
(especially in .NET) fundamentally text-based. There's too many ways that
can go wrong; definitely the opposite of maintainable, IMHO.

Yup

It might be interesting to write a generic "sequence within sequence"
finder some time. Wouldn't be too hard - with a signature of something
like:

int IndexOf<T> (IList<T> haystack, IList<T> needle)
where T : IEquatable<T>

which would cope with arrays automatically. Hmm. Maybe I should add it
to the wishlist for my MiscUtil library...

 

[Peter Duniho]

There's no nested loop in the code posted by Alberto - it looks like a
pretty simple way of doing things to me.

Well, Alberto's code assumes that you know ahead of time the three-byte
sequence you're looking for. For the specific example, it appears that's
fine, but since a general solution isn't hard to write I'd think it would
make more sense to do so. Then if the constants change or may be
determined dynamically at some point, the "hard" work is already done
(such as it is ).

I'm not sure I quite see how your IndexOf solution would be simpler,
but I could well be missing a trick. If you've got the time, could you
post some sample code?

No.

I thought about it some more and decided that a couple of nested loops
really isn't that bad, and that the recursion I was thinking of is
overkill for the specific situation. So I'll take back what I wrote about
a recursive solution taking advantage of the IndexOf() method. Sorry.

It might be interesting to write a generic "sequence within sequence"
finder some time. Wouldn't be too hard - with a signature of something
like:

int IndexOf<T> (IList<T> haystack, IList<T> needle)
where T : IEquatable<T>

which would cope with arrays automatically. Hmm. Maybe I should add it
to the wishlist for my MiscUtil library...

Sure. Though alternatively, the Array class already has generic "Find"
methods that take a predicate delegate as a parameter. It seems that a
future addition to the Array class in .NET itself should be this exact
functionality. To me, a String is really just a special-purpose array so
it seems natural to extend the existing Array class within .NET to support
the functionality String already has.

Pete

 

[Jon Skeet [C# MVP]]

Well, Alberto's code assumes that you know ahead of time the three-byte
sequence you're looking for. For the specific example, it appears that's
fine, but since a general solution isn't hard to write I'd think it would
make more sense to do so. Then if the constants change or may be
determined dynamically at some point, the "hard" work is already done
(such as it is ).

Right - sorry, I didn't realise you were talking about the more general
solution.

No.

I thought about it some more and decided that a couple of nested loops
really isn't that bad, and that the recursion I was thinking of is
overkill for the specific situation. So I'll take back what I wrote about
a recursive solution taking advantage of the IndexOf() method. Sorry.

No problem. Shame though - I'm always keen to learn a new trick

Sure. Though alternatively, the Array class already has generic "Find"
methods that take a predicate delegate as a parameter. It seems that a
future addition to the Array class in .NET itself should be this exact
functionality. To me, a String is really just a special-purpose array so
it seems natural to extend the existing Array class within .NET to support
the functionality String already has.

Mmm... Find certainly doesn't help at the moment, as the predicate will
only match the individual element.

I agree that it would be nice to get this in Array, although getting it
in *any* IList<T> would be even better, IMO.

 

[Peter Duniho]

No problem. Shame though - I'm always keen to learn a new trick

Well, I promise you when I actually do have a new trick, I'll post it.
For now, I just have to accept that I was off in the weeds for a moment.

Mmm... Find certainly doesn't help at the moment, as the predicate will
only match the individual element.

Right. My point was that the pattern of those methods within the class
could easily be extended so that they aren't limited to single elements.

I agree that it would be nice to get this in Array, although getting it
in *any* IList<T> would be even better, IMO.

Sure, whatever makes the most sense. I just happened to be looking at
Array at the time.

Pete