C言語系/「デーモン君のソース探検」読書メモ/04, uuencode(1),uudecode(1)

• [ Prev ]
• [ Next ]
• [ C言語系 ]

お題：uuencode(1)の符号化・復号化の仕組みを追跡せよ。

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&sect=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を見てみる。シンプルな作りで、符号化の中心的な処理は次のコードが担当している。

/* 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はヘッダ行の検出や内容の妥当性チェックなどが入っている。本体データの復号化処理だけを抜き出してみる。

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になりかつ図形文字の範囲に収まっている'`'が、空白文字と互換を維持する為の代替として採用された。

今回のお題については、ここまで。

• [ Prev ]
• [ Next ]
• [ Up ]
• [ C言語系 ]