2013-12-09

Base64 decoder - Bash Advent Calendar - Day 9

むか~し、このネタをどこかに書いた気がするので、既に見たことがあったらゴメンナサイ。何度も書くけどネタがないんです。ネタください。

Base64の仕様

RFC3548読んでください。以上。だって、ここ読むような人は大体知ってるか、知らなくてもこの後読めば分かるでしょ。

では何なので、エンコーダーの場合

  1. 3 octet (24 bit, ASCII char 3 文字分) を 6bit のかたまり x 4 に展開
  2. 各 6 bit を以下の文字に変換
    • 0 〜 25: "A" 〜 "Z"
    • 26 〜 51: "a" 〜 "z"
    • 52 〜 61: "0" 〜 "9"
    • 62: "+", 63: "/" 
    • 処理の最後、入力が 1 octet もしくは 2octet しかない場合には "=" で padding
という感じで変換します。これでも意味不明なら、Wikipedia でもなんでも、適当に検索して自分で調べてね。

Bashの64進数

前回、基数が37以上の場合を説明しませんでしたが、下記64進数のマッピングから類推してください。で、64進数のマッピングは

  • 0 〜 9: "0" 〜 "9"
  • 10 〜 35: "a" 〜 "z"
  • 36 〜 61: "A" 〜 "Z"
  • 62: "@", 63: "_" 
となっております。そんなわけで、上のマッピングのの違いを吸収してあげるだけで、Base64デコーダーが算術式評価で簡単に作れる、はず。paddingとか面倒だけど。

検証用入力値

"Bash" AND "base64" で検索すると出てくる数々の、「コマンドライン上でBase64」を処理する方法。全然、Bash スクリプトじゃないじゃないか。そこですぐスクリプトが検索結果に出てきたらネタにならないんですけどね。

とにかく、検索したところ base64 コマンドを使えと。まんまですね。というわけで
$ echo "Hello World!!" | base64
SGVsbG8gV29ybGQhIQo=
全然関係ないですけど、おせっかいにもヒストリー展開が有効になってると !! がヒストリー展開されていやーんなことになるかもしれませんが、ここは適宜自分の好きな文字に置き換えるなり、ヒストリー展開を未来永劫禁止したり、好きなようにしてください。

スクリプト

とりあえずネタなので、不正な入力のハンドリングはなしということで。誰も実際にこんなん使わないでしょ。

四文字受け取って三オクテット返す関数

これがメインですが
four_char_to_three_octet() {
    local input="$1"
    local bash_64=$(LC_ALL=C tr "A-Za-z0-9+/=" "0-9a-zA-Z@_0" <<< "${input}")
    local -i base_64_num="64#${bash_64}"
    printf '\\x%02x\\x%02x\\x%02x\n' \
      $(( (base_64_num & 0xff0000) >> 16)) \
      $(( (base_64_num & 0x00ff00) >>  8)) \
      $(( base_64_num & 0x0000ff ))
}
tr を Bash ビルトインだけで書くこともできるのですが、全然関係ないところでスクリプトの量が10倍ぐらいになるので今日のところは tr で勘弁してください。tr の同等の処理じゃなく、単純に仕様に従って数値に変換してもいいんですが、そうすると「Bashの64進数表記」というネタの根本がどっかにいってしまうし、面白くもなんともありません。

色々実装の仕方はあると思うのですが、とりあえずここでは padding は無視して "=" も 0 に変換してます。それと printf の出力に余計な \ がついてるのは後で出てきます。とりあえず、実行結果は
$ four_char_to_three_octet "SGVs"
\x48\x65\x6c
となりますが、これは "Hello world!!" の最初の3文字 Hel に一致するはず
$ echo -n Hel | od -An -t x1
 48 65 6c

1行分の文字列を4文字ずつに区切る

仕様上、パディングを含めれば必ず1行は4の倍数文字なので
split_line() {
  local line="$1"
  local result=()
  local -i i
  for ((i = 0; i < ${#line}; i += 4)); do
    result+=(${line:i:4})
  done
  echo "${result[@]}"
}
と何も考えずに4文字ずつ区切るだけ。
$ split_line "SGVsbG8gV29ybGQhIQo="
SGVs bG8g V29y bGQh IQo=

パディング処理

詳細は自分で計算するなり、仕様をチェックしてくれればいいのですが、パディングはなし、1文字、2文字の3通りで、パディングの文字数分のオクテットだけ出力を削ればOKです。four_char_to_three_octet は1オクテットにつき \xXX で4文字出力するので、パディングの長さ×4文字削除しています。
strip_padded_part() {
  local src="$1"    # XXXX, XXX= or XX==
  local output="$2" # \xXX\xXX\xXX
  local src_except_padding="${src%%=*}"
  local -i padding_length="4 - ${#src_except_padding}"
  echo "${output:0:12-(padding_length * 4)}"
}
12は "\xXX\xXX\xXX" の文字数です。なんかもっとスマートな方法がある気がする、というか3オクテットを一つの文字列で返したのが敗因ですね。思いつきでこの記事を書きながらスクリプトを書いてるのでこんなハメに。最初にスクリプトを全部書き終えてから記事にすればよかった。

閑話休題、これで
$ four_char_to_three_octet "IQo="
\x21\x0a\x00
$ strip_padded_part "IQo=" '\x21\x0a\x00'
\x21\x0a
ちゃんと不要な \x00 が削除されてるのが分かります。

バイナリ出力

あとは今までのをまとめて、バイナリ出力するだけです。
base64_decode() {
  local line
  local four_char
  local three_octet
  while read line; do
    for four_char in $(split_line "${line}"); do
      three_octet=$(four_char_to_three_octet "${four_char}")
      if [[ "${four_char}" == *= ]]; then
        three_octet=$(strip_padded_part "${four_char}" "${three_octet}")
      fi
      printf "${three_octet}"
    done
  done
}
printf に引数一つだけというのは、Cならかなりダメコードのサインなのですが、printf "\xXX" (または "\0XXX")、もしくは echo -e だけがバイナリーを出力する手段 (printf "%c" は違うのが残念)なので、このようになっております。今回は printf の直後に - が来ないのが分かってますが、そうじゃない場合に気持ち悪いので echo -n -e "..." よりは printf -- "..." の方が好みです。って、"--" をここでは指定してないので一緒ですけどね。

とにかく
$ base64_decode <<< "SGVsbG8gV29ybGQhIQo="
Hello World!!
$
と、まさしくデコードできました。めでたしめでたし。ちなみに途中経過で \0x0a が出てくる通り、エンコードされた文字列に改行文字が入ってるので、出力にも改行が入ってますが、末尾に改行なんてないバイナリーデータでも正しく処理できるはずです。

今日の結論。スクリプトを書き終わって、ちゃんと恥ずかしくないようなものになってから記事を書きましょう。


コメントを投稿

XKB で遊んでみよう (2)

xkb_keymap xkb_keymap エントリーは、xkb で使われる設定一式です。中身は xkb_keycodes xkb_types xkb_compat xkb_symbols の各エントリーからなります。おまけとして xkb_geometry ...