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

https://rfc.zeromq.org/spec/32/

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

割と純粋な 85 進数。

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

### Ascii85

https://ja.wikipedia.org/wiki/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

https://tools.ietf.org/html/rfc1924

~~~:文字集合
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進数**上位桁**から文字列化する。
デコード処理が簡素化される。

### サンプルコード

~~~ts: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;
}
~~~

~~~ts: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]
~~~