strstrの字体？

Question

私は、さまざまな文字列を散りばめたバイナリデータのファイルを持っています。私はCコードを記述して、ファイル内にユーザが指定した文字列が最初に出現するのを見つけようとしています。 （私はこれはbashので行うことができます知っているが、私は他の理由のためのCコードが必要）コードを、そのままでは、次のとおりです。

#include <stdio.h> 
#include <string.h> 

#define CHUNK_SIZE 512 

int main(int argc, char **argv) { 
    char *fname = argv[1]; 
    char *tag = argv[2]; 
    FILE *infile; 
    char *chunk; 
    char *taglcn = NULL; 
    long lcn_in_file = 0; 
    int back_step; 
    fpos_t pos; 

    // allocate chunk 
    chunk = (char*)malloc((CHUNK_SIZE + 1) * sizeof(char)); 

    // find back_step 
    back_step = strlen(tag) - 1; 

    // open file 
    infile = fopen(fname, "r"); 

    // loop 
    while (taglcn == NULL) { 
     // read chunk 
     memset(chunk, 0, (CHUNK_SIZE + 1) * sizeof(char)); 
     fread(chunk, sizeof(char), CHUNK_SIZE, infile); 
     printf("Read %c\n", chunk[0]); 
     // look for tag 
     taglcn = strstr(chunk, tag); 
     if (taglcn != NULL) { 
      // if you find tag, add to location the offset in bytes from beginning of chunk 
      lcn_in_file += (long)(taglcn - chunk); 
      printf("HEY I FOUND IT!\n"); 
     } else { 
      // if you don't find tag, add chunk size minus back_step to location and ... 
      lcn_in_file += ((CHUNK_SIZE - back_step) * sizeof(char)); 
      // back file pointer up by back_step for next read 
      fseek(infile, -back_step, SEEK_CUR); 
      fgetpos(infile, &pos); 
      printf("%ld\n", pos); 
      printf("%s\n\n\n", chunk); 
     } 
    } 
    printf("%ld\n", lcn_in_file); 

    fclose(infile); 
    free(chunk); 
} 

あなたが迷っている場合は、back_stepが低いの世話をするために入れています問題の文字列がchunk境界で分割されることがあります。

私が調べようとしているファイルは、約1Gbのサイズです。問題は何らかの理由で最初の9000バイト以内の文字列を見つけることができますが、それを超えるとstrstrは何らかの文字列を検出しないことになります。つまり、ファイルに9000バイトを超える文字列が見つかると、strstrはそれを検出しません。コードはファイル全体を読み込み、検索文字列を決して見つけません。

CHUNK_SIZEを128から50000に変更しようとしましたが、結果に変更はありません。私はまたback_stepを変えてみました。私はstrstrが文字列を見つけられなかったときにchunk文字を印刷する診断コードを入れてしまっていて、確かにその文字列は正しいと思われる場所です。 posの診断出力は常に正しいです。

どこに間違っているのか教えていただけますか？ strstrは間違ったツールですか？

Answer 1

strstrがコードで失敗する最も一般的な理由は、ファイルにnullバイトが存在することです。さらに、ファイルオフセットを意味のあるものにするために、ファイルをバイナリモードで開く必要があります。

ブロック内の一連のバイトをスキャンするには、memmem()関数を使用します。それはあなたのシステム上で利用できない場合は、ここでは簡単な実装です：

#include <string.h> 

void *memmem(const void *haystack, size_t n1, const void *needle, size_t n2) { 
    const unsigned char *p1 = haystack; 
    const unsigned char *p2 = needle; 

    if (n2 == 0) 
     return (void*)p1; 
    if (n2 > n1) 
     return NULL; 

    const unsigned char *p3 = p1 + n1 - n2 + 1; 
    for (const unsigned char *p = p1; (p = memchr(p, *p2, p3 - p)) != NULL; p++) { 
     if (!memcmp(p, p2, n2)) 
      return (void*)p; 
    } 
    return NULL; 
} 

あなたは、このようにプログラムを修正します：これは、ファイルがCHUNK_SIZEバイトのチャンクで読み取られること

#include <errno.h> 
#include <stdio.h> 
#include <string.h> 

void *memmem(const void *haystack, size_t n1, const void *needle, size_t n2); 

#define CHUNK_SIZE 65536 

int main(int argc, char **argv) { 

    if (argc < 3) { 
     fprintf(sderr, "missing parameters\n"); 
     exit(1); 
    } 

    // open file 
    char *fname = argv[1]; 
    FILE *infile = fopen(fname, "rb"); 
    if (infile == NULL) { 
     fprintf(sderr, "cannot open file %s: %s\n", fname, strerror(errno)); 
     exit(1); 
    } 

    char *tag = argv[2]; 
    size_t tag_len = strlen(tag); 
    size_t overlap_len = 0; 
    long long pos = 0; 

    char *chunk = malloc(CHUNK_SIZE + tag_len - 1); 
    if (chunk == NULL) { 
     fprintf(sderr, "cannot allocate memory\n"); 
     exit(1); 
    } 

    // loop 
    for (;;) { 
     // read chunk 
     size_t chunk_len = overlap_len + fread(chunk + overlap_len, 1, 
               CHUNK_SIZE, infile); 
     if (chunk_len < tag_len) { 
      // end of file or very short file 
      break; 
     } 
     // look for tag 
     char *tag_location = memmem(chunk, chunk_len, tag, tag_len); 
     if (tag_location != NULL) { 
      // if you find tag, add to location the offset in bytes from beginning of chunk 
      printf("string found at %lld\n", pos + (tag_location - chunk)); 
      break; 
     } else { 
      // if you don't find tag, add chunk size minus back_step to location and ... 
      overlap_len = tag_len - 1; 
      memmove(chunk, chunk + chunk_len - overlap_len, overlap_len); 
      pos += chunk_len - overlap_len; 
     } 
    } 

    fclose(infile); 
    free(chunk); 
    return 0; 
} 

は注意CHUNK_SIZEがファイルシステムブロックサイズの倍数の場合は最適です。

Answer 2

バイナリデータファイルには、文字列の終わりとして動作する '\ 0'バイトが含まれます。その中にあるものが多いほど、より短い範囲のstrstrが検索されます。ノートstrstrは、一度0バイトに達するとその作業が完了したとみなします。

あなたはすなわち、限り、あなたはチャンク内まだあるようチャンクにNULLバイトの後に再起動

while (strlen (chunk) < CHUNKSIZE) 
    chunk += strlen (chunk) + 1; 

のような間隔でメモリをスキャンすることができます。

Answer 3

ファイルがバイナリであると言うので、strstr()は、ファイルの最初のヌルバイトでスキャンを停止します。

バイナリデータでパターンを検索する場合は、memmem()関数が使用可能な場合は適切です。これはLinuxやその他のプラットフォーム（BSD、macOSなど）で利用できますが、標準CやPOSIXの一部として定義されていません。 とほぼ同じ関係にあり、memcpy()は、strcpy()となります。

---

コードがfread()によって読み取られたバイト数を検出し、唯一その上で検索する必要があることに注意してください。

char *tag = …;  // Identify the data to be searched for 
size_t taglen = …; // Identify the data's length (maybe strlen(tag)) 
int  nbytes; 
while ((nbytes = fread(chunk, 1, (CHUNK_SIZE + 1), infile)) > 0) 
{ 
    … 
    tagcln = memmem(chunk, nbytes, tag, taglen); 
    if (tagcln != 0) 
     …found it… 
    … 
} 

なぜ+1がチャンクサイズになっているのかはっきりしません。 fread()関数は、データの末尾などにnullバイトを追加しません。私はその面を変更せずに残しましたが、おそらく自分のコードでは使用しませんでした。

2つのチャンク間の境界にまたがるタグを識別することができます。

Answer 4

実際には単純なコードでは、mmap()とmemcmp()を使用できます。

エラーチェックと適切なヘッダファイルは、読者の練習として残している（少なくとも1つのバグがある - 読者が検索するために別の行使）：

int main(int argc, char **argv) 
{ 
    // put usable names on command-line args 
    char *fname = argv[ 1 ]; 
    char *tag = argv[ 2 ]; 

    // mmap the entire file 
    int fd = open(fname, O_RDONLY); 
    struct stat sb; 
    fstat(fd, &sb); 
    char *contents = mmap(NULL, sb.st_size, PROT_READ, MAP_PRIVATE, fd, 0); 
    close(fd); 

    size_t tag_len = strlen(tag); 

    size_t bytes_to_check = 1UL + sb.st_size - tag_len; 

    for (size_t ii = 0; ii < bytes_to_check; ii++) 
    { 
     if (!memcmp(contents + ii, tag, tag_len)) 
     { 
      // match found 
      // (probably want to check if contents[ ii + tag_len ] 
      // is a `\0' char to get actual string matches) 
     } 
    } 

    munmap(contents, sb.st_len); 

    return(0); 
} 

おそらくどこにも近くではありません最も速い方法です（一般的に、mmap()は、パフォーマンスの勝者の近くにはありません。特に、ファイルを最初から最後までストリーミングする場合）。簡略です。

（読み取っている間にファイルサイズが変更されても問題があることに注意してください）ファイルが大きくなると追加のデータは表示されません。