strstr 的微妙之处?
Subtlety in strstr?
我有一个二进制数据文件,其中散布着各种字符串。我正在尝试编写 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
是不是用错了工具?
二进制数据文件将包含“\0”字节作为字符串结尾。里面的东西越多,strstr
搜索的区域就会越短。注意 strstr
一旦遇到 0 字节就会认为它的工作已经完成。
您可以像
这样按时间间隔扫描内存
while (strlen (chunk) < CHUNKSIZE)
chunk += strlen (chunk) + 1;
即只要您仍在块中,就在块中的空字节后重新启动。
既然你说你的文件是二进制文件,strstr()
将在文件中的第一个空字节处停止扫描。
如果您希望在二进制数据中寻找模式,那么 memmem()
function is appropriate, if it is available. It is available on Linux and some other platforms (BSD, macOS, …) but it is not defined as part of standard C or POSIX. It bears roughly the same relation to strstr()
that memcpy()
bears to 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()
函数不会在数据末尾添加空字节或类似内容。我保留了这方面不变,但可能不会在我自己的代码中使用它。
您最好注意识别跨越两个块之间边界的标签。
代码中 strstr
失败的最可能原因是文件中存在空字节。此外,您应该以二进制模式打开文件以使文件偏移量有意义。
要扫描块中的字节序列,请使用 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;
}
您可以这样修改您的程序:
#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
字节的块读取,如果 CHUNK_SIZE
是文件系统块大小的倍数,这是最佳的。
对于一些非常简单的代码,您可以使用mmap()
and memcmp()
。
错误检查和正确的头文件留作 reader 的练习(至少有一个错误 - reader 找到的另一个练习):
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 `[=10=]' char to get actual string matches)
}
}
munmap( contents, sb.st_len );
return( 0 );
}
这可能不会接近最快的方式(一般来说,mmap()
不会接近性能赢家,特别是在这种简单地从头到尾流式传输文件的用例中结束),但它简单。
(请注意,如果文件大小在读取过程中发生变化,mmap()
也会出现问题。如果文件变大,您将看不到额外的数据。如果文件变短,您将看到SIGBUS
当您尝试读取已删除的数据时。)
我有一个二进制数据文件,其中散布着各种字符串。我正在尝试编写 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
是不是用错了工具?
二进制数据文件将包含“\0”字节作为字符串结尾。里面的东西越多,strstr
搜索的区域就会越短。注意 strstr
一旦遇到 0 字节就会认为它的工作已经完成。
您可以像
这样按时间间隔扫描内存while (strlen (chunk) < CHUNKSIZE)
chunk += strlen (chunk) + 1;
即只要您仍在块中,就在块中的空字节后重新启动。
既然你说你的文件是二进制文件,strstr()
将在文件中的第一个空字节处停止扫描。
如果您希望在二进制数据中寻找模式,那么 memmem()
function is appropriate, if it is available. It is available on Linux and some other platforms (BSD, macOS, …) but it is not defined as part of standard C or POSIX. It bears roughly the same relation to strstr()
that memcpy()
bears to 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()
函数不会在数据末尾添加空字节或类似内容。我保留了这方面不变,但可能不会在我自己的代码中使用它。
您最好注意识别跨越两个块之间边界的标签。
代码中 strstr
失败的最可能原因是文件中存在空字节。此外,您应该以二进制模式打开文件以使文件偏移量有意义。
要扫描块中的字节序列,请使用 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;
}
您可以这样修改您的程序:
#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
字节的块读取,如果 CHUNK_SIZE
是文件系统块大小的倍数,这是最佳的。
对于一些非常简单的代码,您可以使用mmap()
and memcmp()
。
错误检查和正确的头文件留作 reader 的练习(至少有一个错误 - reader 找到的另一个练习):
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 `[=10=]' char to get actual string matches)
}
}
munmap( contents, sb.st_len );
return( 0 );
}
这可能不会接近最快的方式(一般来说,mmap()
不会接近性能赢家,特别是在这种简单地从头到尾流式传输文件的用例中结束),但它简单。
(请注意,如果文件大小在读取过程中发生变化,mmap()
也会出现问题。如果文件变大,您将看不到额外的数据。如果文件变短,您将看到SIGBUS
当您尝试读取已删除的数据时。)