3
\$\begingroup\$

I have searched for method to find and replace strings sequence in binary files without any luck. The main requirement was that method should not load all file in memory but rather use chunks. I am new in c# and code may look not "polished" but it works fine. Maybe someone will have ideas how this code could be improved or does it have any flaws? p.s. Thanks goes to Jon Skeet for idea.

public static void ReplaceTextInFile(string inFile, string find, string replace)
{

    if (find.Length!=replace.Length) throw new ArgumentException("The lenght of find and replace strings must match!");

    const int chunkPrefix = 1024*10;
    var findBytes = GetBytes(find);
    var replaceBytes = GetBytes(replace);
    long chunkSize = findBytes.Length * chunkPrefix;
    var f = new FileInfo(inFile);
    if (f.Length < chunkSize)
        chunkSize = f.Length;

    var readBuffer = new byte[chunkSize];

    using (Stream stream = File.Open(inFile, FileMode.Open))
    {
        int bytesRead;
        while ((bytesRead=stream.Read(readBuffer, 0, readBuffer.Length)) != 0)
        {
            var replacePositions = new List<int>();
            var matches = SearchBytePattern(findBytes, readBuffer, ref replacePositions);
            if (matches != 0)
                foreach (var replacePosition in replacePositions)
                {
                    var originalPosition = stream.Position;
                    stream.Position = originalPosition - bytesRead + replacePosition;
                    stream.Write(replaceBytes, 0, replaceBytes.Length);                            
                    stream.Position = originalPosition;
                }


            if (stream.Length == stream.Position) break;
            var moveBackByHalf = stream.Position - (bytesRead / 2);
            stream.Position = moveBackByHalf;
        }

    }

}


static public int SearchBytePattern(byte[] pattern, byte[] bytes, ref List<int> position)
{
    int matches = 0;
    for (int i = 0; i < bytes.Length; i++)
    {
        if (pattern[0] == bytes[i] && bytes.Length - i >= pattern.Length)
        {
            bool ismatch = true;
            for (int j = 1; j < pattern.Length && ismatch == true; j++)
            {
                if (bytes[i + j] != pattern[j])
                    ismatch = false;
            }
            if (ismatch)
            {
                position.Add(i);
                matches++;
                i += pattern.Length - 1;
            }
        }
    }
    return matches;
}

public static byte[] GetBytes(string text)
{
    return Encoding.UTF8.GetBytes(text);
}

usage

 ReplaceTextInFile(@"MyFile.bin", "Text to replace", "New Text! Test!");
\$\endgroup\$
4
\$\begingroup\$

A few issues with the code:

  • You're comparing the string length for both, but then replacing the bytes. In UTF-8 encoding, as you're using, it's possible that the two will be different: if find = "aeiou" and replace = "áéíóú" you'll have findBytes.Length == 5, and replaceBytes.Length == 10
  • You don't need to pass the position parameter by reference to SearchBytePattern, since you're not changing the reference, only calling methods on it.
  • On SearchBytePattern, you don't need the outermost loop to go all the way to bytes.Length, it only needs to go to bytes.Length - pattern.Length + 1 (and that would simplify the inner "if"
  • stream.Read doesn't necessarily return the count of bytes you asked for - it can return less than that. Your code should be ready to handle that situation.
\$\endgroup\$
  • \$\begingroup\$ +1 This will only work for plain ASCII strings (but since there is a requirement that find/replace length are equal, I believe this is a pretty specific application which could be limited to ASCII). Also, as you said, the last block will create problems if the previous one had a match near the end because OP doesn't check the actual bytes read. \$\endgroup\$ – Groo Jul 3 '11 at 17:57
3
\$\begingroup\$

Performance wise, you might want to check Boyer-Moore's algorithm (Googling found this article on CodeProject, and this article somewhere else). The algorithm is very efficient because it preprocesses your input string to know where to jump when there is a mismatch.

For example, if you are looking for the string "Text to replace" (15 chars), you should first check the 15-th character in your input stream. If it is a 'z', then obviously you can immediately jump 15 characters ahead, because there is no such character in your search string. On the other hand, if it's an 'r', then it might be the starting letter of the word replace, and the algorithm will jump 6 characters to try to align the matching string with the input stream. This is far more efficient than moving the pointer by only a single position in each iteration.

Next, your buffer size of 10*1024*find.Length doesn't make sense. What is the purpose of this multiplication compared to a fixed buffer size (larger than find, of course)? And, more importantly, why do you keep going back by half this length every time, when you have already checked this data and should only backup for find.Length-1 (in case the match is at the very end of your buffer)? What you are doing right now would only make sense if your buffer is exactly twice the length of find (which is what Jon probably meant in his answer).

Apart from that, carlosfigueiras answer covers the errors in your code (SearchBytePattern should have a parameter indicating the number of bytes actually read from the stream), and the problems dealing with Unicode (if you haven't read it already, check Jon Skeet's OMG Ponies, the part about Unicode).

\$\endgroup\$
  • \$\begingroup\$ I use "going back by half" method to not miss Search String. As you already correctly pointed Search String can be separated by chunks. \$\endgroup\$ – Tomas Jul 4 '11 at 8:21
2
\$\begingroup\$

You could remove the first if statement in SearchBytePattern by changing the condition in the outer for loop and the start of the inner for loop like so:

for (int i = 0; i < bytes.Length - pattern.Length; i++)
{
    bool ismatch = true;
    for (int j = 0; j < pattern.Length && ismatch == true; j++)

further, you can break the inner loop, when a difference is found:

if (bytes[i + j] != pattern[j])
{
    ismatch = false;
    break;
}
\$\endgroup\$
2
\$\begingroup\$

So a few immediate things I see are, the hardcoded encoding, if you aren't going to identify the encoding of the file to search automatically, then make it a parameter the user specifies. You really can't do this accurately without certainty of the correct encoding to use. For more information on this and why check out: http://www.joelonsoftware.com/articles/Unicode.html

Also, the chunk prefix is better off either handed in by the user, or being based off a: memory constraints you are aware of for the activity of this process, or b: the size of the file, as the chunk size will cause wildly different read-through performance based on the size of the file, i.e.

2gb file at 20mb a chunk will be processed much quicker than at 256b a chunk. A 400k file would be completely acceptable at 256b a chunk.

Know the memory limitations, concurrency expectations (so you aren't creating too many IO waits), and time expectations of the user to decide the chunk size, otherwise leave it up to users as a parameter.

Next, the name SearchBytePattern gives absolutely no illustration to the user what it's going to do, (I'm still not sure what it does having read it..) maybe it is returning the position of the beginning index of the BytePattern? Maybe it's returning by parameter the actual string in it's location? Give it a very clear unambiguous name (even if it's long), same goes for the parameters, a "position" is an integer, a list of int's might be positions? Or something else, and it's uncelar what they're positions for..

Disambiguate your parameters and method names.

Next, get rid of SearchBytePattern altogether anyway, instead of downconverting your searchpattern to bytes, use the correct encoding with a StreamReader and a StreamWriter which sends to a seperate file. then you just need to (forgive minor mistakes, winging it..):

char[] charsReadFromFile = new char[chunkSize];

do
{
    int numberOfCharsReadFromFile = streamReaderOnGivenFile.Read(charsReadFromFile, 0, chunkSize);
    string stringReadFromFile = new String(charsReadFromFile).Trim(charsReadFromFile.Skip(numberOfCharsReadFromFile).ToArray());
    streamWriterOnNewFile.Write(stringReadFromFile.Replace(searchPattern, stringToReplacePatternWith));
} while(numberOfCharsReadFromFile > 0)
\$\endgroup\$
0
\$\begingroup\$

One thing I noted is that your SearchBytePattern function returns an int that is always equal to the number of elements in the position list. You can either make the return void, or make the function return a new list, since the two are superfluous.

Also, comments help.

\$\endgroup\$

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.