1
\$\begingroup\$

I'm trying to quickly and efficiently find every recurring position of small byte arrays (4 bytes) in large binary files (several GBs). My current method is as follows:

Stream stream = File.OpenRead(filepath);

List<long> searchResults = new List<long>(); //The results as offsets within the file
int searchPosition = 0; //Track of how much of the array has been matched
int[] searchPattern = { 0x00, 0x01, 0x02, 0x03 }; // The array to search

while(true) //Loop until we reach the end of the file
{
    var latestbyte = stream.ReadByte();
    if(latestbyte == -1) break; //We have reached the end of the file

    if(latestbyte == searchPattern[searchPosition]
    {
        searchPosition++;
        if(searchPosition == searchPattern.Length)
        {
            searchResults.Add(stream.Position);
        }
    }
    else
    {
        searchPosition = 0;
    }
}

It's slow, and seems quite inefficient (3-4 seconds for a small 174MB file, 35 seconds for a 3GB one).

How can I improve the performance?

I looked into Boyer-Moore, but is it really worth it, considering the pattern i'm looking for is only 4 bytes?

\$\endgroup\$
  • 1
    \$\begingroup\$ Ok, now that this is fixed, let me ask you two questions: 1. Can there be same bytes (or sub-sequences) in the search pattern? Because you could skip start of the sequence being inside (not finding the occurence). 2. Title states arrays, plural, does that mean "any of given patterns" or you mean "you can give it any but single pattern"? In any case, I would use some buffer, read it in chunks and to solve possible problem - revert to position after we started matching the pattern if it was not full match. \$\endgroup\$ – firda Aug 22 '18 at 16:36
  • \$\begingroup\$ Yes, string searching algorithms will be worth it if your file is large. You should check other algorithms as some might be more efficient considering your small pattern. \$\endgroup\$ – IEatBagels Aug 22 '18 at 16:57
  • \$\begingroup\$ You would get better performance by reading large chunks at once. You should also compare the byte at the current position with the 4th byte of your pattern. Not equal ? Skip 4 bytes and repeat. Equal ? Compare the previous 3 bytes. \$\endgroup\$ – Sylvain Rodrigue Aug 22 '18 at 16:59
1
\$\begingroup\$

This is not a full review, but longer description of an idea. Let me use Henrik's answer as a start and improve it by taking advantage of the length of the pattern - 4 bytes. We can merge it to single uint variable and match it as a whole. The basis of the loop would look like this:

uint pattern = 0x00010203; // Big Endian
uint view = 0; // bytes shifted into this for easy compare
//...
for (int i = 0; i < readCount; i++) // see Henrik's answer
{
    view = (view << 8) | buffer[i]; // shift-in next byte
    if(view == pattern && filePosition >= 3) // make sure we already got at least 4 bytes
        searchResults.Add(filePosition - 3);

This also avoids problems with patterns containing same bytes and can easily be upgraded to match multiple patterns (one of) at once.

P.S.: A cast to uint could be needed in some places, compiler would tell.

\$\endgroup\$
  • \$\begingroup\$ I see what you mean, but isn't it limited to patterns with length == sizeof(uint)? \$\endgroup\$ – Henrik Hansen Aug 23 '18 at 8:08
  • 1
    \$\begingroup\$ Yes it is and that is exactly what OP asked for, twice, read first line and last line of the description. \$\endgroup\$ – firda Aug 23 '18 at 8:33
1
\$\begingroup\$

You should be aware, that if you have a search pattern like:

byte[] pattern = { 0x00, 0x01, 0x02, 0x03 };

and a file sequence as

..., 0x00, 0x00, 0x01, 0x02, 0x03,...

Then it won't be found, because the first 0x00 will increment searchPosition to 1, so the second 0x00 will test false in if(latestbyte == searchPattern[searchPosition].

The solution is to reset the searchPosition whenever the latestbyte equals searchPattern[0]:

while(true) //Loop until we reach the end of the file
{
    var latestbyte = stream.ReadByte();
    if(latestbyte == -1) break; //We have reached the end of the file

    if (latestbyte == searchPattern[0])
      searchPosition = 0;

    if(latestbyte == searchPattern[searchPosition]
    {
        searchPosition++;
        if(searchPosition == searchPattern.Length)
        {
            searchResults.Add(stream.Position);
            searchPosition = 0;
        }
    }
}

OBS: This is only working for search patterns with bytes, that are all different (see Firdas comment).


The position of the found pattern, you add to the result is actually the position of the last byte in the pattern. Maybe the start position is more interesting:

searchResults.Add(stream.Position - searchPattern.Length);


As Sylvain suggests you can improve performance a bit by reading larger chunks of bytes and evaluate them in turn successively:

List<long> GetPatternPositions(string path, byte[] pattern)
{
  using (FileStream stream = new FileStream(path, FileMode.Open))
  {
    List<long> searchResults = new List<long>(); //The results as offsets within the file
    int patternPosition = 0; //Track of how much of the array has been matched
    long filePosition = 0;
    long bufferSize = Math.Min(stream.Length, 100_000);

    byte[] buffer = new byte[bufferSize];
    int readCount = 0;

    while ((readCount = stream.Read(buffer, 0, buffer.Length)) > 0)
    {
      for (int i = 0; i < readCount; i++)
      {
        byte currentByte = buffer[i];

        if (currentByte == pattern[0])
          patternPosition = 0;

        if (currentByte == pattern[patternPosition])
        {
          patternPosition++;
          if (patternPosition == pattern.Length)
          {
            searchResults.Add(filePosition + 1 - pattern.Length);
            patternPosition = 0;
          }
        }
        filePosition++;
      }
    }

    return searchResults;
  }
}

The improvement is not that impressive, but maybe you can experiment with the bufferSize to optimize it?

\$\endgroup\$
  • \$\begingroup\$ Your solution would probably still have problems with patterns like 0x00, 0x01, 0x00, 0x01 (never matching it, because you will keep restarting on each 0x00). That gives me an idea: why not taking advantage of the length of the pattern? We know it is 4B, so, we could use uint and shift the bytes in, comparing the uint as a whole, avoiding theese problems alltogether, while also allowing scaling-up to multi-pattern search. \$\endgroup\$ – firda Aug 23 '18 at 6:17
  • \$\begingroup\$ @firda: You are certainly right about the pattern match, I'll think of an update. Feel free to expand you idea in an answer :-) \$\endgroup\$ – Henrik Hansen Aug 23 '18 at 6:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.