☰

如何查找一个二进制文件在另一个文件中的偏移量？

tag-icon • tag-icon linux files binary large-files
如何查找一个二进制文件在另一个文件中的偏移量？

我有两个二进制文件。
一个是几百公斤，另一个是几千兆字节。
我想知道整个较小的文件是否包含在较大的文件中，如果是，那么距较大文件开头的偏移量是多少。
我只对精确匹配感兴趣，即整个文件是否包含在另一个文件中。
这两个文件都是二进制的。
有没有现有的工具/单线可以做到这一点？

答案1

我想不出现有的工具。

grep -F --binary --byte-offset --only-matching似乎足够接近 - 但你无法使用 来逃避换行符-F。并且cmp只允许跳过字符。diff似乎也没有多大帮助。

但它是具有像样库的编程语言中的一些行。例如，作为使用 Boost 的 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 实现是最短的实现，并且不需要任何外部依赖项。

答案2

我们在生物信息学中一直这样做——除了我们也想要部分匹配，并且我们想知道它们匹配的程度。

BLAT 是我所知道的最快的解决方案：https://en.wikipedia.org/wiki/BLAT_（生物信息学）

它建立一个索引，建立索引后速度快得离谱。

答案3

下面是一个对外部文件执行子字符串搜索的 Python 脚本。该剧本最初由卡姆兰·汗和发布到他的博客。我对它进行了轻微的修改，以从文件中获取搜索字符串并在标准输入中进行搜索。

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

答案4

如果您有足够的内存，只需按小文件大小的块读取大文件即可。读取每个块后，将最后读取的两个块连接在一起，然后对结果进行字符串搜索。在 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 倍，具体取决于您的实现方式。好处是它非常快，因为它使用高度优化的简单字符串搜索。

相关内容