可変長バイトコード

可変長バイトコードとは

ここで言う可変長バイトコードは int（4バイト）を long（8バイト）整数を 4、8 バイトといった 固定長サイズで表現するのではなく、その値により 1～ 5 / 10 バイトで表現するものである。 数値自体は７ビットで表し、先頭の１ビットは後ろにバイトが続くか、それともこれで終わりかを 表すフラグビットとして使う。非常に小さい数値は 1 バイトで表現できるが、 正味32ビット必要な数値では 5 バイト、正味64ビット必要な数値では 10 バイト必要となるため、 固定整数の int や long よりもより多くのメモリを必要とする。 小さな数値が多い時には、int や long よりも少ないメモリで表現できる。 このため、OpenStreetMap の圧縮データ形式である *.pbf形式[1] や *.o5m 形式[2]などで使われている。 例えば、３バイトで表される数値は以下の通りである。符号ありの 0 は二通りある。

    1xxxxxxx 1xxxxxxx 0xxxxxxx 符号なし 3x7 = 21ビット. 0 ～ 221
    1xxxxxx0 1xxxxxxx 0xxxxxxx 符号あり正 20ビット. 0 ～ 220
    1xxxxxx1 1xxxxxxx 0xxxxxxx 符号あり負 20ビット. 0 ～ －220 

符号化プログラム

ByteBufferを使ってもよいが、byte配列の方がオーバヘッドは少ないであろう。

    static int ConvertULong(long v, byte[] buf, int ix) {
        byte frac = (byte)(v & 0x7f);
        while (frac != v) {
            buf[ix++] = (byte)(frac | 0x80);
            v >>= 7;
            frac = (byte)(v & 0x7f);
        }
        buf[ix++] = frac;
        return ix;
    }

    static int ConvertSLong(long v, byte[] buf, int ix) {
        long u = v<0 ? ((-v)<<1) - 1 : v<<1;
        return ConvertULong(u, buf, ix);
    }

復号化プログラム

C++ や C# などでは、参照型の int が使えるが、Java にはない。 メソッドで簡単に値(long 型)とインデックス(int 型)の二つを戻す方法がないため、 ByteBuffer を使う。

    static long ParseULong(ByteBuffer buffer) {
        long value = 0;
        long b = 0x80;
        for (int i = 0; (b & 0x80) != 0; i += 7) {
            b = buffer.get();
            long part = (b & 0x7F) << i;
            value |= part;
        }
        return value;
    }

    static long ParseSLong(ByteBuffer buffer) {
        long value = ParseULong(buffer);
        if ((value & 1) != 0) { // negative
            return -(value >> 1) - 1;
        } else {                // positive
            return (value >> 1);
        }
    }

参考記事