tek​/rjc :: OSASK計画

tek圧縮でよく使われるrjcについて ^[1]

• (by K^[2], 2008.12.09)

(0) ^[3]

• まずは祝tek普及～！・・・NWSOSの開発が再開されてしかもtek圧縮を採用する予定らしいことをIRCで教えてもらいました。とてもうれしいです。OSASK発祥の圧縮文化は少しずつですが着実に認められて浸透しているようです。---この件修正。詳細はこめんと欄参照。
  
  
  
  
• （2008.12.09時点での）tek圧縮普及リスト：
  • 旧OSASK、OSASK-HBのOSやアプリおよびデータファイル （tek1/tek2/tek5）
  • Susieプラグイン（tek1/tek2/tek5）
  • sarアーカイブ（tek1/tek2/tek5）
  • 「はりぼてOS」およびその発展型OS（tek1/tek2/tek5）
  • MonaOSでのtek5圧縮のアプリ
  • おれんじぺこでのtek1圧縮のアプリ、おれんじぺこでの（正確にはCOM64-GREでの）tek1/tek2/tek5展開APIの採用
  • 次期NWSOSでのOS本体のtek5圧縮（予定）
    
    
    
    
• これでOSASKがもしOSとしての競争に敗北し絶滅してしまったとしても、圧縮文化の発祥としてそしてtekの発祥としてOSASK計画は歴史に名を残すことができるかもしれないわけです（上記のどれかが生き残っていてくれさえすれば）。まあOSとしても敗北しないほうがもちろんいいですし、僕は敗北するとはまだ思っていませんが。

(1) ^[4]

• さてそのtek圧縮ですが、実はOSASK以外のOSではtek圧縮だけを普通に使っているだけです。データファイルは確かにこれで問題ないんです。しかし新旧のOSASKアプリでは当然のようにrjcというフィルタも併用していて、これが圧縮率を高めるのに大いに寄与しています。これじゃあOSASKアプリとサイズ比較するときにOSASKばかりが有利になってしまってずるいと思います。
• またrjcに相当するフィルタは、LZMA(7z)やUPXでも当然のように利用されていて、rjcを使わないtek5とこれらを比較すると場合によっては圧縮率で逆転します。それじゃあtek5の実力が誤解されかねません。それは僕としては不本意です。もちろんrjcはtek5以外のtek圧縮とも併用できますし、相性もいいです。
• rjcを使わずにtek5した場合と、rjcしてからtek5した場合のサイズの差は、たいてい1割前後です。この差はかなり大きいです。tek5の改良だけで（たいした速度低下もなく）1割も圧縮率を改善するというのはほぼ不可能といっていいレベルだと思います。
• rjcは極めて処理時間が短く、コードもとても小さい簡単なフィルタです。rjc単体で見るとrjcによってサイズが増えたり減ったりすることはありません。大きさはそのままで圧縮が効きやすい状態にしているだけです。・・・処理内容を簡単に説明するとIA-32の分岐処理のコードは相対ジャンプ命令（near-callも該当）が中心で、同じオフセットへのジャンプであってもそれぞれ違う機械語になっています。つまり同じ場所へのジャンプ命令であるにもかかわらず、それは何度出てきても初出の命令列になり、スライド辞書圧縮がほとんど効きません。こういうコードはIA-32の一般的なプログラムでは頻出するので、これをrjcエンコードフィルタによってスライド辞書法が適用しやすい形式に変換してから圧縮してやろうというわけです。また展開時には通常のtek展開の後にrjcのデコードフィルタをかけることで、展開処理を完了します。

(2) ^[5]

• rjcは以下のような簡単な関数で、エンコード・デコードできます。この関数が返す値は、rjcが変換した箇所の個数です。以下はabcdw006で採用されているrjcです。

int rjc(int size, UCHAR *p0, int mode)
/* mode:    0:decode, 1:encode */
{
    UCHAR *p = p0, *p1 = p0 + size, *pp = p0 - 4;
    int ofs0 = 0, ofs = 0, ofs1 = size;
    int i, j, k, m = 0;
    while (p < p1) {
        if (0xe8 <= *p && *p <= 0xe9 && &p[4] < p1) {  /* e8 (call32), e9 (jmp32) */
    r32:
            p++;
            if (p - pp < 4)
                continue;
            i = p[0] | p[1] << 8 | p[2] << 16 | p[3] << 24;
            k = i;
            j = (p - p0) + ofs + 4; /* 相対アドレス基点 */
            pp = p;
            if (i == 0 || i == 0x80808080)
                i ^= 0x80808080;
            if (mode) { /* encode */
                if (ofs0 - j <= i && i < ofs1 - j)
                    i += j;
                else if (ofs1 - j <= i && i < ofs1)
                    i -= ofs1 - ofs0;
            } else { /* decode */
                if (ofs0 <= i && i < ofs1)
                    i -= j;
                else if (ofs0 - j <= i && i < ofs0)
                    i += ofs1 - ofs0;
            }
            if (i == 0 || i == 0x80808080)
                i ^= 0x80808080;
            if (i != k) {
                p[0] =  i        & 0xff;
                p[1] = (i >>  8) & 0xff;
                p[2] = (i >> 16) & 0xff;
                p[3] = (i >> 24) & 0xff;
                p += 4;
                m++;
            }
            continue;
        }
        p++;
        if (p[-1] == 0x0f && &p[4] < p1 && (p[0] & 0xf0) == 0x80) /* 0f 8x (jcc32) */
            goto r32;
    }
    return m;
}

• このフィルタを実行ファイル全体にかけても十分に効果は出ますが、コードセクションがファイル内のどこなのか分かっているのなら、コードセクションにのみrjcしたほうが、rjc時間が短くなりますし（といっても些細な差ですが）、圧縮率も若干改善します（微々たる差でしかないことも多いですが）。

(3) ^[6]

• 参考までに、NWSOS0034-IMG内のNWSA.EXEとNWSC.EXEについてrjcの効果を挙げておきます（2ちゃんねるで話題になっていたので）。僕にはコードセクションの位置は分からないので、とりあえずrjcはファイル全体にかけています。

  	圧縮なし	tek5だけ	最高パラメタtek5だけ	rjc+tek5	rjc+最高パラメタtek5
  NWSA.EXE	121,040	50,041	49,414	46,678	46,107
  NWSC.EXE	152,512	71,174	70,230	63,204	62,291

こめんと欄 ^[7]

• 補足：(0)でNWSOSのtek圧縮の採用を歓迎したが、GUIGUI01​/memo12^[8]の問題によりこれを撤回し、むしろ遺憾であるとする。 -- K^[2] 2008-12-13 (土) 18:59:40