как найти смещение одного двоичного файла в другом?

Я не мог придумать существующий инструмент.

grep -F --binary --byte-offset --only-matching кажется, достаточно близок - но Вы не можете выйти из новых строк с -F. И cmp только позволяет пропускать символы. diff также, кажется, не помогает.

Но это - некоторые лайнер на языке программирования с достойной библиотекой. Например, как программа C++ с помощью Повышения:

#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;
}

Можно скомпилировать его как это (когда источник программы сохраняется как find.cc):

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

Протестировать его:

$ 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
$ ./searchb t WTF_-_EPISODE_277_RACHAEL_HARRIS.mp3
232323

Вывод является положением соответствия в исходном файле.

Если файл не содержится, статус выхода 1.

Обновление: Тем временем я реализовал этот простой инструмент на нескольких языках (C/C ++/Python/Rust/Go) и включал те реализации в мой служебный репозиторий. Искать searchb*. Реализация Python является самой короткой и не требует никаких внешних зависимостей.

Вот сценарий Python, который выполняет поиск подстроки на внешнем файле. Сценарий был первоначально записан Kamran Khan и размещен в его блоге. Я очень немного адаптировал его для взятия строки поиска из файла и поиска в стандартном входе.

#!/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()

Если у вас есть память, просто прочитайте большой файл кусками размером с меньший. После того, как каждый фрагмент прочитан, объедините последние два фрагмента, прочитанные вместе, а затем выполните строковый поиск результата. В Python 3.8+ код выглядит так:

def find_at_offset(large_fp, small_fp):
    small = small_fp.read()
    blocks = [b"", b""]
    base = 0
    while blk := large_fp.read(len(small)):
        base += len(blocks[0])
        del blocks[0]
        blocks.append(blk)
        offset = b"".join(blocks).find(small)
        if offset != -1:
            return base + offset
    return -1

Концепция очень проста, хорошо переводится на старый добрый C и не требует каких-либо специальных функций, таких как отображение памяти. Предостережение заключается в том, что для этого требуется минимальный доступный объем памяти, равный 3 -5-кратному размеру небольшого файла, в зависимости от того, как вы его реализуете. Преимущество в том, что это очень быстро, потому что он использует простой строковый поиск, который очень оптимизирован.

Мы постоянно делаем это в биоинформатике -, за исключением того, что нам также нужны частичные совпадения, и мы хотим знать, насколько хорошо они совпадают.

BLAT — самое быстрое решение, которое я знаю:https://en.wikipedia.org/wiki/BLAT_(биоинформатика)

Он строит индекс и после построения индекса работает невероятно быстро.