// BMMatch.h
#ifndef __BMMATCH_H__010417_2236_70554750__INCLUDED__
#define __BMMATCH_H__010417_2236_70554750__INCLUDED__

#include <stdio.h>
#include <limits.h>

// 検索文字列は２５５文字まで
const int BMM_PAT_MAX  = 255;
// 再検索
const int BMM_NEXT     = -1;
// 見つかりませんでした
const int BMM_NOTFOUND = -1;

// 表を再利用できるように、保存できるようにします
// skip がＢＭ法用の表で、
// pat が前に検索した文字列で、
// nFound が前に検索した箇所で、
// nPatLen が pat の長さです
struct SBMMatch
{
    int  skip[UCHAR_MAX + 1];
    char pat[BMM_PAT_MAX + 1];
    int  nFound;
    int  nPatLen;
};

// ファイル内をＢＭ法で検索します
// ファイルはバイナリモードで開かれている必要があります
// nFirst は検索を始める場所で、
// pat は検索文字列で、bm は上の構造体です
// pat に NULL を指定すると、bm.pat を検索文字列として使います
// さらに nFound に BMM_NEXT を指定すると、bm.nFound + 1 から始めます
// 初めて検索する際に、構造体の初期化は必要ありませんが、
// 初期化していない構造体を使って再検索を行ったときの動作は
// 全く保証されないものとします
// 見つかった場合は true を、見つからなかった場合は false を返します
// 位置は bm.nFound に入ります
bool BMMatch(FILE* file, SBMMatch& bm,
             int nFirst = BMM_NEXT, const char* pat = NULL);

#endif // #ifndef __BMMATCH_H__010417_2236_70554750__INCLUDED__

// BMMatch.cpp
#include <stdio.h>
#include <string.h>
#include "BMMatch.h"

#define numof(array)  (sizeof (array) / sizeof *(array))

static void BMMakeSkipTable(SBMMatch& bm);

bool BMMatch(FILE* file, SBMMatch& bm,
             int nFirst, const char* pat)
{
    if(pat == NULL)
    {
        if(bm.nPatLen == 0)
            return false;
        if(nFirst == BMM_NEXT)
            nFirst = bm.nFound + 1;
    }
    else
    {
        // 最低限の初期化
        bm.pat[0]  = 0;
        bm.nFound  = BMM_NOTFOUND;
        bm.nPatLen = 0;

        // それ以外の初期化
        int nPatLen = strlen(pat);
        if(nPatLen <= 0 || BMM_PAT_MAX < nPatLen)
            return false;
        bm.nPatLen = nPatLen;
        strcpy(bm.pat, pat);
        BMMakeSkipTable(bm);
    }

    // バッファサイズ
    const int BMM_BUFSIZE = (BMM_PAT_MAX + 1) * 4;
    // ダブルバッファ
    char      dblbuf[2][BMM_BUFSIZE];
    // どちらのバッファを使っているか
    int       fBuf        = 0;
    // バッファへのポインタ
    char*     src         = dblbuf[0];
    // 読み出しサイズ
    int       nRead;
    // 読み戻しでバッファが変わったかどうか
    bool      bSwitched   = false;
    // 最初以外で読み出した回数
    int       nCount      = 0;

    int       nPatLen     = bm.nPatLen - 1;
    char      letLast     = bm.pat[nPatLen];
    char      letSkip;
    int       i           = nPatLen;

    // ファイルの nFirst バイト目に移動します
    fseek(file, nFirst, SEEK_SET);

    nRead = fread(src, 1, BMM_BUFSIZE, file);

    while(bSwitched || i < nRead)
    {
        letSkip = src[i];

        if(letSkip == letLast)
        {
            int j = nPatLen;
            int k = i;

            do
            {
                // 見つかりました
                if(j == 0)
                {
                    bm.nFound = nFirst + nCount * BMM_BUFSIZE + k;
                    return true;
                }

                j--; k--;
                // k が負になったらバッファを交換
                if(k < 0)
                {
                    src = dblbuf[fBuf ^= 1];
                    bSwitched = true;
                    k += BMM_BUFSIZE;
                    nCount--;
                }
            }
            while(src[k] == bm.pat[j]);
        }

        // バッファが交換されているときは、元に戻す
        if(bSwitched)
        {
            src       = dblbuf[fBuf ^= 1];
            bSwitched = false;
            nCount++;
        }
        i += bm.skip[(unsigned char)letSkip];

        // バッファを超えた時は、次のバッファに読み出す
        if(i >= BMM_BUFSIZE)
        {
            if(nRead != BMM_BUFSIZE)
                break;

            src   = dblbuf[fBuf ^= 1];
            i    -= BMM_BUFSIZE;
            nCount++;
            nRead = fread(src, 1, BMM_BUFSIZE, file);
        }
    }
    bm.nFound = BMM_NOTFOUND;
    return false;
}

static void BMMakeSkipTable(SBMMatch& bm)
{
    int i;

    for(i = 0; i < numof(bm.skip); i++)
        bm.skip[i] = bm.nPatLen;
    for(i = 0; bm.pat[i + 1] != 0; i++)
        bm.skip[bm.pat[i]] = bm.nPatLen - 1 - i;
}

// DblBuf1.cpp
#include <iostream.h>
#include <stdio.h>
#include <string.h>
#include "BMMatch.h"

static FILE* OpenFile();
static bool Match(FILE* file, SBMMatch& bm);

int main()
{
    FILE*    file = NULL;

    file = OpenFile();
    if(file == NULL)
        goto ON_ERROR;

    SBMMatch bm;
    while(Match(file, bm));

ON_ERROR:
    if(file != NULL)
        fclose(file);
    return 0;
}

static FILE* OpenFile()
{
    char szPath[512];

    cout << "検索したいファイルのパスを入力してください。" << endl
         << "> " << flush;
    cin >> szPath;

    // $ で終了します
    if(strcmp(szPath, "$") == 0)
        return NULL;

    return fopen(szPath, "rb");
}

static bool Match(FILE* file, SBMMatch& bm)
{
    char     pat[1024];
    bool     bRet;

    cout << "検索したい文字列を入力してください。" << endl
         << "> " << flush;
    cin >> pat;

    // $ で終了します
    if(strcmp(pat, "$") == 0)
        return false;
    // / で次を検索します
    else if(strcmp(pat, "/") == 0)
        bRet = BMMatch(file, bm);
    // 普通に検索します
    else
        bRet = BMMatch(file, bm, 0, pat);

    if(bRet)
        cout << bm.nFound << " バイト目に見つかりました！" << endl;
    else
        cout << "見つかりませんでした..." << endl;
    return true;
}