Search sequence byte location in binary file

userAxEl1 0
Viewed 67

I want to write a plugin like search function in binary Viewer, searching specific sequence in an binary file by text, hex or bit. https://www.proxoft.com/BinaryViewer.aspx

std::vector<int> search_bit(std::string& file_path, std::string& bit)
std::vector<int> search_hex(std::string& file_path, std::string& hex)
std::vector<int> search_text(std::string& file_path, std::string& text)

For example, I open a 6 bytes binary file "path" : 30 30 31 31 30 31(hex view)
search_bit(path, "001100000001"), 
search_hex(path, "3031"), search_text(path, "01") all return {1, 4}. 
Because "30 31" starts at 1 and 4 byte in this file. (hex"30" stands for ASCII 0, "31" stands for 1)

Is there any reference that could help? sorry this looks like asking for code, I know litte about memory mapping technique. [1]: https://i.stack.imgur.com/9YmKc.png

binaryfiles qt c++
1 Answers

For all three problems you could use https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm it is relatively simple (https://www.geeksforgeeks.org/kmp-algorithm-for-pattern-searching/) and will yield relatively fast execution times.

In context of "subbyte" comparisons:

For searching a bit pattern you could use std::vector (space efficent), or std::bitset<[...]> (algorithm used would be the same just the "character" would be 1 bit), but be aware that you can only load one byte at a time from a file.

For searching a hex pattern you could use custom bitfield struct (https://en.cppreference.com/w/cpp/language/bit_field):

struct hex_pair
{
    uint8_t h0 : 4; // only use 4 bits
    uint8_t h1 : 4; // only use 4 bits
}; // this will be space efficent and fast in term of loading (this struct is trivial)

// loading
file_size = [...]
hex_pair* data_store = [...];
ifile.read(reinterpret_cast<char*>(data_store), file_size);

If you want to complicate the problem a bit you could use https://en.cppreference.com/w/cpp/iterator/istream_iterator to load the data from file (this will optimize memory usage a bit) + some window buffer for KMP algorithm to have enough data to work on.

MichalK0
Related