Fork me on GitHub

大文件快速分析和查找

原创文章，未经允许，请勿转载

有时候有这种需求,需要从一个二进制大文件中查找是否有某种格式的文件，由于大文件是二进制，且非常大，几百M，一般的手工查找方式不太现实了。可以可以通过代码来遍历二进制，查找是否有该文件格式的关键字数据（一般文件头都会有标识，比如dds文件首三个字节是DDS，png、jpg、swf等文件都会有自己的标识头）。

关于搜索算法，我一开始想到的是字符串匹配算法，Google了一下，关于字符串匹配算法有很多种，其中称为Sunday的算法速度非常快，且非常容易理解。关于该算法的具体实现，可以查看本文末尾提供的参考资料，特别是那个PPT，看那个例子非常浅显明了。

字符串匹配算法只能从固定长度内存中匹配，几百M几G的文件不可能一次性全部读取到内存中，所以我使用了分块读取，而在读取下一块文件时，文件指针向后滑动一个窗口，重叠读取，避免这部分内容漏掉匹配。

    #include <stdio.h>
    #include <stdlib.h>

    #define TRUNK_SIZE 1024 * 100 //每次读取的块大小

    //创建预查表
    void preQsBc(unsigned char *pattern, int m, int qsBc[]) {
        int i;
        //qsBc[c]=min{i : 0  < i ≤ m and pattern[m-i]=c} if c occurs in pattern, m+1 otherwise 
        for (i = 0; i < 256; ++i)
            qsBc[i] = m + 1;//预先设置，假如i不在pattern串中，则表格值为m+1
        for (i = 0; i < m; ++i)//目的是设置表格值为i在pattern中，从右开始第一次出现的位置，
            qsBc[pattern[i]] = m - i;//这里循环是从左开始遍历，后边的值会覆盖前面设置的值，所以能达到目的
    }

    //pattern为要搜索的子串，m为pattern的长度
    void fQS(unsigned char *pattern, int m, FILE *fp) {
        if(m >= TRUNK_SIZE) {
            printf("not support:pattern length >= TRUNK_SIZE(%d)", TRUNK_SIZE);
            return;
        }

        //建立预查表
        int qsBc[256];
        preQsBc(pattern, m, qsBc);

        //取得文件尺寸
        int size;
        fseek(fp, 0, SEEK_END);
        size = ftell(fp);
        rewind(fp);

        printf("处理进度:00%%(00)");

        unsigned char *trunk = malloc(TRUNK_SIZE);//分配块内存
        int fpos = 0;//当前文件位置
        int count = 0;//匹配成功个数
        while(size - fpos >= m) {
            printf("\b\b\b\b\b\b\b%02d%%(%02d)",(unsigned)((fpos * 100.0f) / size),count);

            //读取一个块
            int n = (size - fpos) > TRUNK_SIZE ? TRUNK_SIZE : (size - fpos);
            fread(trunk, 1, n, fp);

            //从块中查找匹配
            int jpos = -1;
            int j = 0;
            while (j <= n - m) {
                if (memcmp(pattern, trunk + j, m) == 0) {
                    jpos = j;
                    ++count;
                    //printf("found in position:%d\n",fpos + j);
                    //匹配成功，文件位置为：fpos + j

                    //TODO:从文件中提取需要的内容

                }
                j += qsBc[trunk[j + m]];
            }

            if(size - fpos == m)break;//刚好到文件结尾，则立即结束查找

            if(jpos >= 0 && jpos == n - m) {//刚好尾部匹配成功，不需要滑动窗口
                fpos += n;
            }else {
                fpos += n - m;//向后滑动一个窗口,以防漏掉
            }
            //printf("fpos=%d\n",fpos);
            fseek(fp,fpos,SEEK_SET);
        }
        printf("\b\b\b\b\b\b\b%02d%%(%02d)",100,count);
        free(trunk);
        trunk = NULL;
    }

    int main(int argc,char **argv) {
        printf("---by yoyo(//yoyo.play175.com)----\n",);

        FILE *fp = fopen("E:\\yoyo\\mydocuments\\bigfile.bin","rb");
        if(fp == NULL) {
            perror("open file failed");
            goto exit;
        }

        fQS("DDS",3,fp);

        exit:
        if(fp != NULL) {
            fclose(fp);
            fp = NULL;
        }
        return 0;
    }

参考资料：

来源：悠游悠游，原文地址：https://yymmss.com/p/binary-file-dump.html