☰

別のファイル内でバイナリファイルのオフセットを見つけるには？

tag-icon • tag-icon linux files binary large-files
別のファイル内でバイナリファイルのオフセットを見つけるには？

2つのバイナリファイルがあります。
1つは数百キログラム、もう1つは数ギガバイトです。
小さなファイル全体が大きなファイルに含まれているかどうかを知りたいです。では、大きなファイルの先頭でオフセットはいくらですか？
私は正確な一致に興味があります。つまり、ファイル全体が別のファイルに含まれているかどうかです。
どちらのファイルもバイナリです。
これを行うための既存のツール/シングルライナーはありますか？

答え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

私たちは生物情報学で常にこれを行います。ただ、部分一致も欲しいし、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

メモリが十分な場合は、大きなファイルを小さなファイルサイズのチャンクに分割して読みます。各チャンクを読み込んだ後、最後に読み取った2つのチャンクを連結し、結果を文字列として検索します。 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倍です。利点は、高度に最適化された単純な文字列検索を使用するため、非常に高速です。

関連情報