how to find offset of one binary file inside another?

Question

I have two binary files.
One of few hundreds kilos and other of few gigabytes.
I want to know whether the whole, smaller, file is contained within the larger one and if so then what is the offset from the start of the larger file.
I am interested only in exact matches i.e. whether the whole file is contained by the another.
Both files are binary.
Is there any existing tool/one-liner that does that ?

Answer 1

I could not come up with an existing tool.

grep -F --binary --byte-offset --only-matching seems to be close enough - but you can't escape newlines with -F. And cmp only allows to skip characters. diff also does not seem to be of much help.

But it is a few liner in a programming language with a decent library. For example as a C++ program using Boost:

#include <boost/algorithm/string/find.hpp>
#include <boost/iostreams/device/mapped_file.hpp>
#include <cassert>
#include <iostream>
using namespace boost;
using namespace boost::algorithm;
using namespace boost::iostreams;
using namespace std;

int main(int argc, char **argv)
{
  if (argc != 3) {
    cerr << "Call: " << argv[0] << " PATTERN_FILE SRC_FILE\n";
    return 3;
  }
  mapped_file_source pattern(argv[1]);
  mapped_file_source src(argv[2]);
  iterator_range<const char*> p_range(pattern.data(),
      pattern.data() + pattern.size());
  iterator_range<const char*> s_range(src.data(), src.data() + src.size());
  iterator_range<const char*> result = find_first(s_range, p_range);
  if (result) {
    size_t pos = result.begin()-s_range.begin();
    cout << pos << '\n';
    return 0;
  }
  return 1;
}

You can compile it like this (when the program source is saved as find.cc):

$ make CXXFLAGS="-Wall -g" LDLIBS="-lboost_iostreams" find

To test it:

$ dd if=WTF_-_EPISODE_277_RACHAEL_HARRIS.mp3 of=t skip=232323 bs=1 count=4K
$ ls -l t
-rw-r--r-- 1 juser users 4096 2012-05-31 15:24 t
$ ./find t WTF_-_EPISODE_277_RACHAEL_HARRIS.mp3
232323

The output is the matching position in the source file.

If the file is not contained the exit status is 1.

Answer 2

Here's a Python script that performs a substring search on an external file. The script was originally written by Kamran Khan and posted to his blog. I very slightly adapted it to take the search string from a file and search in standard input.

#!/usr/bin/env python
import locale
import os
import sys
import urllib2

def boyermoore_horspool(fd, needle):
    nlen = len(needle)
    nlast = nlen - 1

    skip = []
    for k in range(256):
        skip.append(nlen)
    for k in range(nlast):
        skip[ord(needle[k])] = nlast - k
    skip = tuple(skip)

    pos = 0
    consumed = 0
    haystack = bytes()
    while True:
        more = nlen - (consumed - pos)
        morebytes = fd.read(more)
        haystack = haystack[more:] + morebytes

        if len(morebytes) < more:
            return -1
        consumed = consumed + more

        i = nlast
        while i >= 0 and haystack[i] == needle[i]:
            i = i - 1
        if i == -1:
            return pos

        pos = pos + skip[ord(haystack[nlast])]

    return -1

if __name__ == "__main__":
    if len(sys.argv) < 2:
        sys.stderr.write("""Usage: horspool.py NEEDLE_FILE [URL]
Search for the contents of NEEDLE_FILE inside the content at URL.
If URL is omitted, search standard input.
If the content is found, print the offset of the first occurrence and return 0.
Otherwise, return 1.""")
        sys.exit(2)
    needle_file = open(sys.argv[1])
    needle = needle_file.read()
    needle_file.close
    fd = urllib2.urlopen(sys.argv[2]) if len(sys.argv) > 2 else sys.stdin
    offset = boyermoore_horspool(fd, needle)
    if offset >= 0: print offset
    else: sys.exit(1)
    fd.close()