Base85(85進数表記)に関する一考察

Base85 とは

Base64 等と同じ考え方で、印字可能な 85 文字を使用してバイナリデータ等を扱うためのエンコード方式。$2^{32} \lt {85}^5$ であることを利用して 4 バイトを 5 文字で表現する。

1 文字 = 1 バイトと仮定すると、Base64 はデータ量が 4 / 3 倍 (約33%増)になるのに対して Base85 は 5 / 4 倍 (25%増) なのでやや効率が良い。

Base85 に類する仕様はいくつかあるので、その簡単な紹介と、
各種プログラミング言語のソースコードにリテラル文字列として埋め込むときの問題点と
自分なりの解消法についてまとめてみる。

※実際には JavaScript 等だと文字列リテラルは実行時に UTF-8 → UTF-16 で一時的にデータ量が上記の 2 倍になってしまうのだけれど、とりあえずここではソースコードについてのみ考えている。

既存の Base85 類

Z85

文字集合

0123456789
abcdefghij
klmnopqrst
uvwxyzABCD
EFGHIJKLMN
OPQRSTUVWX
YZ.-:+=^!/
*?&<>()[]{
}@%$#

割と純粋な 85 進数。

バックスラッシュ, 引用符が省かれているので、(他と比べれば)ソースコードに埋め込みやすい。

Ascii85

文字集合

!"#$%&'()*
+,-./01234
56789:;<=>
?@ABCDEFGH
IJKLMNOPQR
STUVWXYZ[\
]^_`abcdef
ghijklmnop
qrstu

// 特殊文字
zy

85 文字に加えて 4byte の 0 block を表す z を加えた 86 文字を使うのが特徴。
バージョンによっては空白文字列の圧縮のために y (0x20202020) も用いられる。

デコードしやすいよう文字集合は、ascii コード上で連番になっている。

バイナリデータを文字列として転送するためのもので、
ソースコード埋め込み用途は考えられておらず、引用符などもそのまま含まれている。

z, y の存在があるため、並列化しにくい。

RFC1924: A Compact Representation of IPv6 Addresses

文字集合

0123456789
abcdefghij
klmnopqrst
uvwxyzABCD
EFGHIJKLMN
OPQRSTUVWX
YZ!#$%&()*
+-;<=>?@^_
`{|}~

IPv6 は 128 bit = 16 byte なので、20文字で表現しよう、というもの。
こちらは 4 byte 毎に 5 文字 に変換するのではなく 16 byte をまとめて 20 文字として扱っている。
128 bit 整数演算が要るので、これも埋め込み用途には向かない。

Z85 をソースコード埋め込みに使用したときの課題

Ascii85, RFC1924 は、それぞれソースコードへの埋め込み用途には問題があるので、使うとすれば Z85 である。

が、実際使ってみると Z85 もいくつか課題がある。

• エスケープが必要になるパターンが存在する
  • $, #, @ は各言語で、文字列リテラル中の変数や式の展開に使用されている。
  • */ が含まれている場合、(言語によっては)単純にコメントアウトできなくなる。
  • </script が含まれている場合、html 中の javascript 等で問題となる。
  • #, % は、dataURL (ascii エンコード)と組み合わせた場合に問題となる。
    • # は fragment identifier (いわゆるハッシュ) の区切り文字として扱われる。
    • % は エスケープ文字として扱われる。
    • dataURL の data 部は opaque (不透明) なので、reserved char (? 等) は使用できる。
• 元データが 4 の倍数 byte であることを前提としている
  • そうでないデータは 0 埋めをしたうえで、データ長を別に持つ必要がある。
• 各 4 byte ブロックに対して、ビッグエンディアンで読み取り、85進数上位桁から文字列化している。
  • デコードのコストがやや高い。
  • できればエンコードを高く、デコードを安くしたい。

俺々 Base85

上記課題を解消した Base85 を考えてみる。

文字集合

文字集合

!&()*+,-.0
123456789:
;<=>?ABCDE
FGHIJKLMNO
PQRSTUVWXY
Z[]^_abcde
fghijklmno
pqrstuvwxy
z{|}~

// 除外文字
\ %     エスケープに使用されるため
' " `   引用符として使用されるため
$ # @   変数・式の文字列展開として使用されるため
/       コメント・終了タグとして使用されるため

※ @ に関しては、問題になるのは Perl くらいなので、別な文字と置き換えても良いかもしれない。
※ 文字の順番は単に ascii コードの若い順。順序を入れ替えたほうが見栄えは良いかもしれない。

データ長に関して

元データサイズが N byte のとき、N を 4 で割ったあまりが

• 0 なら N / 4 * 5 の長さの文字列
• 1 なら floor(N/4) * 5 + 2 の長さの文字列
• 2 なら floor(N/4) * 5 + 3 の長さの文字列
• 3 なら floor(N/4) * 5 + 4 の長さの文字列

になるよう符号化し、パディングを行わない。

文字列長が M のとき、元データの長さ N は以下のように求められる。

• R = M % 5
• N = (M - R) / 5 * 4 + (R == 0 ? 0 : R - 1)

R = 1 時、不正な長さとなるが、その場合最後の 1 文字を捨てているのと同等である。

符号化方法

元データを リトルエンディアン で読み込んだうえで、85進数上位桁から文字列化する。
デコード処理が簡素化される。

サンプルコード

typescript

const C = "!&()*+,-.0123456789:;<=>?ABCDEFGHIJKLMNOPQRSTUVWXYZ[]^_abcdefghijklmnopqrstuvwxyz{|}~";
const M = C.split('')
    .reduce((o, c, i) => (o[c] = i, o), {} as Record<string, number>);

function encode(b: Uint8Array) {
  let n = b.length;
  let p = 0;
  let s = '';
  while (n) {
    let r = n < 4 ? n : 4;
    let d = 1;
    let h = 1;
    let v = 0;
    for (let i = 0; i < r; i++) {
      v = v + b[p++] * h;
      d *= 85;
      h *= 256;
    }
    for (let i = 0; i <= r; i++) {
      s += C[(v / d >>> 0) % 85];
      d = d / 85 | 0;
    }
    n -= r;
  }
  return s;
}

function decode(s: string) {
  let n = s.length;
  let r = n % 5;
  let b = new Uint8Array((n - r) / 5 * 4 + (r && r - 1));
  let p = 0, q = 0, v = 0;
  while (n) {
    let r = n < 5 ? n : 5;
    for (let i = 0; i < r; i++) v = v * 85 + M[s[p++]];
    for (let i = 1; i < r; i++) {
      b[q++] = v;
      v >>>= 8;
    }
    n -= r;
  }
  return b;
}

test

const bin = new TextEncoder().encode("Hello, World!");
console.log(bin);
// => [72, 101, 108, 108, 111, 44, 32, 87, 111, 114, 108, 100, 33]

const str = encode(bin);
console.log(str);
// => "Jr!cYD!6+:H>OA.!I"

const res = decode(str);
console.log(res);
// => [72, 101, 108, 108, 111, 44, 32, 87, 111, 114, 108, 100, 33]