#navi_header|C言語系| お題：uuencode(1)の符号化・復号化の仕組みを追跡せよ。 #more|| * uuencodeの使い方とフォーマット uuencodeの使い方： uuencode [file] name fileが指定されない場合は標準入力から読み込まれる。nameは出力に含まれ、uudecodeが復元する時に必要となる。 適当なバイナリファイル"testbin"を用意し、uuencode結果を"testbin.u"に保存する。また、復元した時にファイル名が"alternate"となるようにする： $ cat testbin | uuencode alternate > testbin.u uudecodeで戻してみる。 $ uudecode testbin.u $ cmp alternate testbin $ echo $? 0 同一のファイルに復元された。 uuencodeコマンドの使い方は "man 1 uuencode", uuencodeの符号化の仕組みは "man 5 uuencode" に載っている。 http://www.jp.freebsd.org/cgi/mroff.cgi?subdir=man&lc=1&cmd=&man=uuencode&dir=jpman-5.4.0/man§=5 ざっと確認してみる。まず本来のバイト数は5738バイト、3で割ると2余る点に注意： $ wc -c testbin 5738 testbin (= 1912 * 3 + 2) headコマンドでヘッダ行を確認してみる。 $ head -n 2 testbin.u begin 644 alternate M?T5,1@$!`0````````````(``P`!````)(8$"#0```"P#````````#0`(``& "begin 644 alternate(LF)"がヘッダ行になる。 続いて本体データのエンコードされたデータ行が始まる。一行は改行を含み最大62文字。最初の１文字はその行の"エンコードする前の"バイト数 + 0x20(=空白)となっている。 上の例なら、先頭は"M": M = 0x4D = 10進77 (ASCIIコード) →バイト数は 0x20(=10進32) を引いた、45バイト。 uuencodeでは3バイト=24bitを単位として6bit x 4つに分割していくようになっている。 6bitということは10進で 0 - 63 となり、これに 0x20, 10進32, 空白文字のASCIIコードを足すことで、ASCIIコードの10進で32 - 95まで、すなわち数字・大文字アルファベット・あといくつかの記号文字に符号化できる。 45バイトと言うことは360bit, 6bitで分割すればちょうど60になる。すなわち、符号化された結果のASCIIコードの文字数は60文字になる： M(=45バイト→符号化すると60文字) + 符号化された60文字 + (改行) で、ちょうど一行62文字になっていることが確認出来た。 つづいてtailコマンドでトレーラ行近くを確認してみる。 $ tail -n 3 testbin.u 77W)E9VES=&5R7V9R86UE7VEN9F\`,0H` ` end 逆から見ていって、まず"end"がトレーラ行になる。その上の ` 一文字の行は、本体データの終わりを意味していて、本体データそれ自体には含まれない、只のマーカー(印)。値としては"`"、つまり復号化すれば0になる。 その上の行が、本体データの最後の行になる。 77W)E9VES=&5R7V9R86UE7VEN9F\`,0H` 符号化前のデータのバイト数を表す先頭1文字は "7", ASCIIコード10進で 55 , 空白文字の10進32を引けば 23 となる。 一方、符号化された文字数は32文字、つまり 32 x 6bit = 192bit = 24 x 8bit で、復号化すると24バイトになってしまう。 ここで元ファイルのサイズが、3で割ると2余る5738バイトだったことを思い出す。 uuencode(5)の仕様では、もし3で割ってあまりがでた場合はゴミデータをくっつけることで8bit x 3に揃えることが分かる。 よって最終行の意味するところは、 7(=23バイト) + 3で揃える為にゴミデータが追加され、24バイトとして符号化された32文字 + (改行) となり、仕様通りであることが確認出来た。 この辺りでソースコード探索に入る： $ locate uuencode ... /usr/src/usr.bin/uuencode/uuencode.c $ locate uudecode ... /usr/src/usr.bin/uudecode/uudecode.c * uuencode.cによる符号化処理 まずはuuencode.cを見てみる。シンプルな作りで、符号化の中心的な処理は次のコードが担当している。 #code|c|> /* ENC is the basic 1 character encoding function to make a char printing */ #define ENC(c) ((c) ? ((c) & 077) + ' ': '`') /* * copy from in to out, encoding as you go along. */ static void encode() { int ch, n; char *p; char buf[80]; while ((n = fread(buf, 1, 45, stdin)) > 0) { ch = ENC(n); if (putchar(ch) == EOF) break; for (p = buf; n > 0; n -= 3, p += 3) { ch = *p >> 2; ch = ENC(ch); if (putchar(ch) == EOF) break; ch = ((*p << 4) & 060) | ((p[1] >> 4) & 017); ch = ENC(ch); if (putchar(ch) == EOF) break; ch = ((p[1] << 2) & 074) | ((p[2] >> 6) & 03); ch = ENC(ch); if (putchar(ch) == EOF) break; ch = p[2] & 077; ch = ENC(ch); if (putchar(ch) == EOF) break; } if (putchar('\n') == EOF) break; } if (ferror(stdin)) err(1, "read error."); ch = ENC('\0'); (void)putchar(ch); (void)putchar('\n'); } ||< まずwhileから見てみる。 while ((n = fread(buf, 1, 45, stdin)) > 0) { 標準入力から、1バイト単位で45バイトを読み、"char buf[80]"に格納している。また"int n"には読み込まれたバイト数が格納される。なお入力ファイル名が指定された場合は、main()にて、freopen(3)を使って指定されたファイル名のファイルハンドルがstdinにセットされている。 続いてバイト数に対してENCマクロが適用される。 ch = ENC(n); この直後に"putchar(ch)"があることから、ここでENCマクロが返す値が、uuencodeで符号化された本体データ一行の、「バイト数を表す先頭一文字」であることが予想される。 ENCマクロの中身を見てみる。 #define ENC(c) ((c) ? ((c) & 077) + ' ': '`') 分解してみる。 if (c) { return ( (c) & 077 ) + ' '; } else { return '`'; } まずcが0の場合は、'`'が返される。なぜ'`'(ASCIIコード10進96)なのかはuudecodeの処理で明らかになる。 cが1以上の場合は、'077'がANDマスクされ、その結果に' '(SP, ASCIIコード10進32)を加算して返す。 '077'というのは、先頭に0が来ているので8進数(octal)である。ビットに戻せば、丁度 111 111 (binary) 7 7 (octal) となり、6bitのマスクになることが分かる。 つまりENCマクロが、6bit分を取り出した値に32を足すという符号化処理を担当していることが分かる。 if (putchar(ch) == EOF) break; この"putchar() -> EOFならbreak"という処理は以降のforループでも使われている。これは単純に、putchar()がEOFを返すという殆どあり得ない自体を想定した、万が一の予防線である。エラー処理を無視すれば、単純に"int ch" = ENCマクロの結果をputchar()して出力している、という意味になる。 これで、データ行の先頭１文字、その行に含まれている元データのバイト数を出力出来た。 以降forループで、元データを3バイト単位で処理していく。 for (p = buf; n > 0; n -= 3, p += 3) { pはfreadで格納されたbufの先頭に初期化される。nはfreadで読み込んだバイト数。つまりこのforループで、バッファを3バイトずつ処理していくことになる。なお、条件判断の "n > 0" と条件成立後に "n -= 3" していることから、もし読み込んだバイト数が3の倍数に満たない場合でも、余りの部分もこのループで処理されることが分かる。 ループの内部を見ていく。分かりやすいコードになっているので、コメントで解説を入れていく。 /* 2bit右シフトすることで、最初の1バイトの先頭6bitがchに代入される。 */ ch = *p >> 2; ch = ENC(ch); if (putchar(ch) == EOF) /* 24bit中6bit単位の1文字目を出力 */ break; /* (1) 最初の1バイトを4bit左シフト + 8進60でマスク * = 12345678 → 56780000 & 110 000 → 00780000：最初の1バイトの下位2bit * (2) 2バイト目を4bit右シフト + 8進17でマスク * = 12345678 → 00001234 & 001 111 → 00001234 : 2バイト目の上位4bit * (3) (1) OR (2) * = 00780000 OR 00001234 → 00781234 * 以上で、24bit中6bit単位の2文字目を取得 */ ch = ((*p << 4) & 060) | ((p[1] >> 4) & 017); ch = ENC(ch); if (putchar(ch) == EOF) /* 24bit中6bit単位の2文字目を出力 */ break; /* (1) 2バイト目を2bit左シフト + 8進74でマスク * = 12345678 → 34567800 & 111 100 → 00567800 : 2バイト目の下位4bit * (2) 3バイト目を6bit右シフト + 8進3でマスク * = 12345678 → 00000012 & 000 011 → 00000012 : 3バイト目の上位2bit * (3) (1) OR (2) * = 00567800 OR 00000012 → 00567812 * 以上で、24bit中6bit単位の3文字目を取得 */ ch = ((p[1] << 2) & 074) | ((p[2] >> 6) & 03); ch = ENC(ch); if (putchar(ch) == EOF) /* 24bit中6bit単位の3文字目を出力 */ break; /* 3バイト目を 8進77 でマスク * = 12345678 & 111 111 → 00345678 : 3バイト目の下位6bit * 以上で、24bit中6bit単位の4文字目を取得 */ ch = p[2] & 077; ch = ENC(ch); if (putchar(ch) == EOF) /* 24bit中6bit単位の4文字目を出力 */ break; 以上で24bit単位で処理していく符号化の実装を理解出来た。 なお、データが読み込まれるバッファ領域がwhileループでは一切クリアされず、次々にfreadされていく点に注意したい。 例えば最後のwhileループで20バイト読み込まれたとすると、 buf[0] - buf[19] までは読み込まれたデータで上書きされるが、 buf[20] - buf[44] の間は、直前のfread()で読み込まれたデータが残ってしまっている。 するとforループの最後のループ処理では、 buf[18], buf[19], buf[20] が処理され、buf[20]が3の倍数に合わせる為にくっつくゴミデータとなることが分かる。 uuencodeによる符号化処理は以上となる。続いてuudecodeのソースから、復号化処理の内部を見てみる。 * uudecode.cによる復号化処理 uudecodeはヘッダ行の検出や内容の妥当性チェックなどが入っている。本体データの復号化処理だけを抜き出してみる。 #code|c|> static int decode() { int n; char ch, *p; char buf[MAXPATHLEN]; /* ... */ /* for each input line */ for (;;) { if (!fgets(p = buf, sizeof(buf), stdin)) { warnx("%s: short file.", filename); return(1); } #define DEC(c) (((c) - ' ') & 077) /* single character decode */ /* * `n' is used to avoid writing out all the characters * at the end of the file. */ if ((n = DEC(*p)) <= 0) break; for (++p; n > 0; p += 4, n -= 3) if (n >= 3) { ch = DEC(p[0]) << 2 | DEC(p[1]) >> 4; putchar(ch); ch = DEC(p[1]) << 4 | DEC(p[2]) >> 2; putchar(ch); ch = DEC(p[2]) << 6 | DEC(p[3]); putchar(ch); } else { if (n >= 1) { ch = DEC(p[0]) << 2 | DEC(p[1]) >> 4; putchar(ch); } if (n >= 2) { ch = DEC(p[1]) << 4 | DEC(p[2]) >> 2; putchar(ch); } if (n >= 3) { ch = DEC(p[2]) << 6 | DEC(p[3]); putchar(ch); } } } } ||< forによる無限ループで、標準入力から1行ずつ読み取りbufに格納している。 for (;;) { if (!fgets(p = buf, sizeof(buf), stdin)) { 入力ファイル名が指定された場合は、main()にて、freopen(3)を使って指定されたファイル名のファイルハンドルがstdinにセットされているのはuuencodeの時と同様である。 続いてDECマクロが定義されている。 #define DEC(c) (((c) - ' ') & 077) /* single character decode */ これはuuencode.cのENCマクロの逆で、空白文字(ASCIIコード 10進32)を引いて、8進77 = 6bitのビットマスクを使い、6bit分を取り出している。 続く次のif文とbreakは、行の先頭文字をデコード = 元データのバイト数をnに格納し、もしそれが0(=本体データの終端)であればfor()ループを抜ける処理になっている。 if ((n = DEC(*p)) <= 0) break; その後、以下のforブロックで行の2文字目以降=符号化されたデータを4文字単位で処理していく。 for (++p; n > 0; p += 4, n -= 3) forブロックの中身については、uuencodeでのビット操作を逆転させていることが分かる。uuencodeでビットシフトやビットマスク処理を見ているので、uudecode側での細かい説明は省略する。 以上でuudecode側の復号化処理も見ることが出来た。 最後に、uuencode側のENCマクロで残っていた謎に決着をつける。 * 0が"`"にエンコードされる理由 ここで、uuencode側でのENCマクロをもう一度見直したい。 #define ENC(c) ((c) ? ((c) & 077) + ' ': '`') cが0の時、わざわざ'`'を返すようにしている。なぜ 0 + ' '(ASCIIコード 10進32)をそのまま返さないのか？が謎として残っていた。 これについては「デーモン君のソース探検」にて歴史と絡めて解説されている。 簡単にまとめると、SystemV初期のuuencodeは空白文字にエンコードしていた。しかし当時のネットワークの一部に、行末の空白文字を削ってしまうメールゲートウェイがあったため、それに対応する為仕様が変更された。 空白文字でも、削除されない為の空白以外の文字でも、デコードすると同じ値に戻るように・・・それで採用されたのが'`'文字になる。 もう一度DECマクロを見てみる。 #define DEC(c) (((c) - ' ') & 077) もしもcが空白文字の場合は、当然0になる。 cが'`'の場合： '`' = ASCIIコード 10進96 → '`' - ' '(ASCIIコード10進32) = 10進64 → 10進64を2進にすると、b1000000 → 8進77 (111 111) でANDして下位6bitを取り出すと、000 000 = 0 として、こちらも0になる。 このように、下位6bitを取り出してちょうど0になりかつ図形文字の範囲に収まっている'`'が、空白文字と互換を維持する為の代替として採用された。 今回のお題については、ここまで。 #navi_footer|C言語系|