BSDiffバイナリ差分アルゴリズムの解説

// oldposやnewpos、ctrl[n]など、ほとんどの変数はoff_t型(64-bit符号付き整数)
// ssize_t newsize = 新ファイルのサイズ
// u_char *new = 新ファイルの書き込み先バッファ先頭
// ssize_t oldsize = 旧ファイルのサイズ
// u_char *old = 旧ファイル全体のバイト列
oldpos=0;newpos=0;
while(newpos<newsize) {
    /* Read control data */
    for(i=0;i<=2;i++) {
        lenread = io->read(cstream, buf, 8);
        if (lenread < 8)
            errx(1, "Corrupt patch\n");
        ctrl[i]=offtin(buf); // offtinはchar[8]からoff_tへ変換する関数
    };

    /* Sanity-check */
    if(newpos+ctrl[0]>newsize) //ctrl[0]が負の時に漏れてしまうのでは？
        errx(1,"Corrupt patch\n");

    /* Read diff string */
    lenread = io->read(dstream, new + newpos, ctrl[0]);
    if (lenread < ctrl[0])
        errx(1, "Corrupt patch\n");

    /* Add old data to diff string */
    for(i=0;i<ctrl[0];i++)
        if((oldpos+i>=0) && (oldpos+i<oldsize))
            new[newpos+i]+=old[oldpos+i];

    /* Adjust pointers */
    newpos+=ctrl[0];
    oldpos+=ctrl[0];

    /* Sanity-check */
    if(newpos+ctrl[1]>newsize) //ctrl[1]が負の時に漏れてしまうのでは？
        errx(1,"Corrupt patch\n");

    /* Read extra string */
    lenread = io->read(estream, new + newpos, ctrl[1]);
    if (lenread < ctrl[1])
        errx(1, "Corrupt patch\n");

    /* Adjust pointers */
    newpos+=ctrl[1];
    oldpos+=ctrl[2];
};

static void bsdiff(
    u_char * const olddata, const off_t oldsize,
    u_char * const newdata, const off_t newsize,
    std::function<void(off_t, off_t, off_t)> writeCtrl,
    std::vector<u_char> &db,
    std::vector<u_char> &eb)
{
    // 検索に必要な索引を作る
    std::unique_ptr<off_t[]> I(new off_t[oldsize+1]);
    {
        std::unique_ptr<off_t[]> V(new off_t[oldsize+1]);
        qsufsort(I.get(),V.get(),olddata,oldsize);
    }

    // 出力バッファを準備
    db.clear(); db.reserve(newsize+1);
    eb.clear(); eb.reserve(newsize+1);

    // 新ファイルを先頭から末尾へスキャンしていきながら、新ファイルの領域が旧ファイルのどの領域と対応づけられるか決めていく。
    // 領域の対応関係が確定したら、その領域のパッチをwriteCtrl,db,ebへ出力。
    off_t scan=0; //調べているnew上の位置
    off_t lastscan=0; //前回一致のnew上の先頭。出力し終わったnew上の末端
    off_t lastpos=0; //前回一致のold上の先頭
    off_t lastoffset=0; //new上の位置からold上の位置を求めるための差(lastpos-lastscan)
    while(lastscan < newsize){
        // 切れ目を見つける。
        off_t len=0;
        off_t pos;
        for(off_t scsc=scan, oldscore=0; scan<newsize;) {
            // old 内から new[scan...newsize) との最長一致を探す。
            // posはその位置、lenはその長さ。
            // old[pos...pos+len) == new[scan...scan+len) となる。
            len=search(I.get(),olddata,oldsize,newdata+scan,newsize-scan,
                    0,oldsize,&pos);

            // oldscoreを差分的に更新する。
            // oldscoreは今回一致範囲[scan...scan+len)と前回一致の続きとの一致バイト数。
            // scscをscan+lenまで進めることによる増加分を数える。
            for(;scsc<scan+len;scsc++)
                if((scsc+lastoffset<oldsize) &&
                   (olddata[scsc+lastoffset] == newdata[scsc]))
                    oldscore++;

            // 前回一致の前方延長が新旧完全に一致しているので、その前方延長を継続。
            if(len == oldscore && len != 0){
                scan += len;
                scsc = scan;
                oldscore = 0;
                continue;
            }

            // 前回一致の前方延長に9バイト以上の不一致があり(len-oldscore > 8)、
            // 他の場所に9バイト以上の完全一致が見つかった(len > 8)
            // ので、参照する旧領域を切り替える。
            if(len>oldscore+8) break;

            // oldscoreを差分的に更新する。
            // scanを1進めることによる減少分。
            if((scan+lastoffset<oldsize) &&
                (olddata[scan+lastoffset] == newdata[scan]))
                oldscore--;
            ++scan;
        }

        // 近似的な一致・不一致の境界線を定める。

        // 前回一致の先頭(lastpos)から前方へ、あまり変化していない長さを求める。
        // 一致を50%以上含んでいて、一致がある程度多くなっていればどんどん延ばす。
        off_t lenf=0;
        for(off_t i=0,s=0,Sf=0;(lastscan+i<scan)&&(lastpos+i<oldsize);) {
            if(olddata[lastpos+i]==newdata[lastscan+i]) s++;
            i++;
            if(s*2-i>Sf*2-lenf) { Sf=s; lenf=i; };
        };

        // 今回一致の先頭(pos)から後方へ、あまり変化していない長さを求める。
        // 一致を50%以上含んでいて、一致がある程度多くなっていればどんどん延ばす。
        off_t lenb=0;
        if(scan<newsize) {
            for(off_t i=1,s=0,Sb=0;(scan>=lastscan+i)&&(pos>=i);i++) {
                if(olddata[pos-i]==newdata[scan-i]) s++;
                if(s*2-i>Sb*2-lenb) { Sb=s; lenb=i; };
            };
        };

        // 前回一致の前方延長と今回一致の後方延長が重なっているなら、
        // 前回一致の前方延長を優先しつつ、境目を確定させる。
        if(lastscan+lenf>scan-lenb) {
            off_t overlap=(lastscan+lenf)-(scan-lenb);
            off_t Ss=0,lens=0;
            for(off_t i=0,s=0;i<overlap;i++) {
                if(newdata[lastscan+lenf-overlap+i]==
                   olddata[lastpos+lenf-overlap+i]) s++;
                if(newdata[scan-lenb+i]==
                   olddata[pos-lenb+i]) s--;
                if(s>Ss) { Ss=s; lens=i+1; };
            };

            lenf+=lens-overlap;
            lenb-=lens;
        };

        // 差分を出力する。(deltaブロック、extraブロック、ctrlブロックへ)

        // ADD操作: new[lastscan...lastscan+lenf) - old[lastpos...lastpos+lenf) をdiffブロックへ出力
        for(off_t i=0;i<lenf;i++)
            db.push_back(newdata[lastscan+i]-olddata[lastpos+i]);
        // INSERT操作: new[lastscan+lenf...scan-lenb) をextraブロックへ出力
        for(off_t i=0;i<(scan-lenb)-(lastscan+lenf);i++)
            eb.push_back(newdata[lastscan+lenf+i]);
        writeCtrl(
            lenf, //ADD長
            (scan-lenb)-(lastscan+lenf), //INSERT長
            (pos-lenb)-(lastpos+lenf)); //旧ファイルの現在位置を pos-lenb へ移動

        lastscan=scan-lenb; //ここまで新ファイルを出力
        lastpos=pos-lenb; //lastscanに対応するold上の位置
        lastoffset=pos-scan; //新ファイル上の位置から旧ファイル上のマッチする位置へ変換するための差(scan+i + lastoffset は pos+iに対応する)

        scan += len;
    }
}

    /* Sanity-check */
    if(newpos+ctrl[0]>newsize)
        errx(1,"Corrupt patch\n");