BitVisorのprintf実装の解説です。core/printf.cおよびprocess/lib/lib_printf.cの話なんですが、中身はほとんど同じなのでcore/printf.cにします。
はじめに
/*
* Copyright (c) 2007, 2008 University of Tsukuba
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* 1. Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright notice,
* this list of conditions and the following disclaimer in the documentation
* and/or other materials provided with the distribution.
* 3. Neither the name of the University of Tsukuba nor the names of its
* contributors may be used to endorse or promote products derived from
* this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*/
仕様?
コメントで仕様のようなものが入っています。浮動小数点等はありませんが、だいたいはPOSIXのprintfと同じようなものですね、たぶん。
/* printf 20071010
%[flags][width][.[precision]][length modifier]<conversion>
flags:
# alternate form
0 zero padded
- left adjusted
' ' a blank before a positive number
+ a sign before a number
width, precision:
decimal number only.
length modifier:
h short
hh char
l long
ll long long
j intmax_t
z size_t
t ptrdiff_t
conversion:
d, i integer as decimal
o unsigned integer as octal number
u unsigned integer as decimal number
X unsigned integer as capital hexadecimal number
x unsigned integer as hexadecimal number
c int as character
s char* as string
p void* as hexadecimal number
% %
*/
入り口
printf, vprintf, snprintf, vsnprintfはすべて、do_printf関数に集約される仕掛けになっています。例としてprintfとvprintfのところを見てみます。
int
printf (const char *format, ...)
{
va_list ap;
int r;
va_start (ap, format);
r = vprintf (format, ap);
va_end (ap);
return r;
}
int
vprintf (const char *format, va_list ap)
{
int r;
spinlock_lock (&printf_lock);
r = do_printf (format, ap, do_putchar, NULL);
spinlock_unlock (&printf_lock);
return r;
}
printfはvprintfを呼んでいるだけなので何でもないです。vprintfはロックを取ってdo_printfを呼んでいます。do_putcharというのが出力関数で、NULLはそれに渡すデータのポインターです。vsnprintfでは書き込み先バッファーの情報を持つ構造体のポインターを渡しています。
static int
do_printf (const char *format, va_list ap, int (*func)(int c, void *data),
void *data)
こんな感じの関数で、引数については特に難しいところはなさそうです。
vprintfのロックは何かというと、複数のプロセッサーから同時に呼び出した時に出力が混ざらないようにするためのロックになります。お気づきの方もいると思いますが、printfの%sに変なポインターを渡してクラッシュしてしまった場合、panic処理中のprintfでデッドロック・ハングアップしてしまうことでしょう。
do_printf
do_printfの中身はformatを解釈し、%を見つけて処理をしていきます。
while ((c = *format++) != '\0') {
Cでよくあるループですね。
if (c == '%') {
%を見つけたら何かしていきます。長いので先にelseを見ておきましょう。
} else {
PUTCHAR (c);
}
PUTCHARマクロに渡します。マクロの中身は:
#define PUTCHAR(c) do { if (func (c, data) < 0) goto error; n++; } while (0)
関数ポインターfuncに渡して失敗したらgoto error、成功時はnをインクリメントするだけです。
じゃあ%の時の処理はというと...
f = parse_format (&format, &width, &precision);
これがformatの解釈を行い、fとwidthとprecisionを返すという関数です。これは引数の取り出しは行いません。
fというのは様々な変換内容を表すものです。
if (f & LENGTH_INTMAX)
f |= LENGTH_LONGLONG;
else if (f & LENGTH_SIZE)
f |= LENGTH_LONG;
else if (f & LENGTH_PTRDIFF)
f |= LENGTH_LONG;
こんな感じでintmax_t型はlong long扱い、size_t型はlong扱い、ptrdiff_t型はlong扱いにします。
if (f == END_STRING) {
break;
formatが変なところで途絶えていた場合の中断処理です。
} else if (f & CONVERSION_NONE) {
PUTCHAR ('%');
%%指定はCONVERSION_NONEになります。
} else if (f & CONVERSION_INT) {
long long intval;
unsigned long long uintval;
if (f & LENGTH_CHAR)
intval = (long long)va_arg (ap, int);
else if (f & LENGTH_SHORT)
intval = (long long)va_arg (ap, int);
else if (f & LENGTH_LONGLONG)
intval = va_arg (ap, long long);
else if (f & LENGTH_LONG)
intval = (long long)va_arg (ap, long);
else
intval = (long long)va_arg (ap, int);
if (intval < 0) {
uintval = (unsigned long long)-intval;
f |= FLAG_MINUS;
} else {
uintval = (unsigned long long)intval;
f |= FLAG_PLUS;
}
n += do_conversion_int (uintval, f, width,
precision, func, data);
continue;
CONVERSION_INTは%dの処理ですね。実は%cもこれになっています。型に合わせてva_argで引数を取り出し、負の数であれば符号を反転し、do_conversion_int関数に渡すことで、文字列に変換されます。%cの場合はCONVERSION_CHARACTERというのがセットされているので、それで単に1バイトに変換されます。continueがあるのは謎です。不要ですね。
CONVERSION_UINTも符号の扱いがないだけでほとんど同じようなものですので省略します。%uや%xなどの処理になります。
} else if (f & CONVERSION_VOIDP) {
void *voidpval;
unsigned long long uintval;
voidpval = va_arg (ap, void *);
uintval = (unsigned long long)
(unsigned long)voidpval;
n += do_conversion_int (uintval, f, width,
precision, func, data);
これは%pに対する処理です。void *型として取り出した後unsigned long型にキャストし、それを%#xと同等の扱いで出力します。
} else if (f & CONVERSION_CHARP) {
char *charpval;
charpval = va_arg (ap, char *);
if (charpval == NULL)
charpval = "(null)";
n += do_conversion_string (charpval, f, width,
precision, func,
data);
これは%sの処理です。NULLポインターだけは特別に処理されます。do_conversion_stringが幅などを合わせて出力します。
} else {
n += do_conversion_string ("FORMAT ERROR",
CONVERSION_CHARP,
0, 0, func, data);
全部ダメな時はこんなエラーが出力されます。
parse_format
これがformatの%の後ろの解釈なのですが、そんなに凝ったことはしていません。
*width = 0;
*precision = 0;
while ((c = *(*format)++) != '\0') {
switch (c) {
case '#':
r |= FLAG_ALTERNATE_FORM;
break;
case '0':
r |= FLAG_ZERO_PADDED;
break;
case '-':
r |= FLAG_LEFT_ADJUSTED;
break;
case ' ':
r |= FLAG_POSITIVE_BLANK;
break;
case '+':
r |= FLAG_POSITIVE_SIGN;
break;
default:
goto parse_width;
}
}
return END_STRING;
こんな感じで最初のflagsを解釈します。
while ((c = *(*format)++) != '\0') {
parse_width:
if (c >= '0' && c <= '9') {
r |= HAS_WIDTH;
*width *= 10;
*width += (c - '0');
} else {
goto parse_precision;
}
}
return END_STRING;
次にwidthの解釈をします。
parse_precision:
if (c != '.')
goto parse_length_modifier;
r |= HAS_PRECISION;
while ((c = *(*format)++) != '\0') {
if (c >= '0' && c <= '9') {
*precision *= 10;
*precision += (c - '0');
} else {
goto parse_length_modifier;
}
}
return END_STRING;
次にprecisionを解釈します。
while ((c = *(*format)++) != '\0') {
parse_length_modifier:
switch (c) {
case 'h':
if (r & LENGTH_SHORT)
r |= LENGTH_CHAR;
else
r |= LENGTH_SHORT;
break;
case 'l':
if (r & LENGTH_LONG)
r |= LENGTH_LONGLONG;
else
r |= LENGTH_LONG;
break;
case 'j':
r |= LENGTH_INTMAX;
break;
case 'z':
r |= LENGTH_SIZE;
break;
case 't':
r |= LENGTH_PTRDIFF;
break;
default:
goto parse_conversion;
}
}
return END_STRING;
そしてlength modifierの解釈です。hhやllは、単純にふたつのビットを重ねて立てる仕掛けです。do_printfの中で参照する時に順番を間違えなければ良いわけです。
parse_conversion:
switch (c) {
case 'd':
case 'i':
r |= CONVERSION_INT | CONVERSION_DECIMAL;
break;
case 'o':
r |= CONVERSION_UINT | CONVERSION_OCTAL;
break;
case 'u':
r |= CONVERSION_UINT | CONVERSION_DECIMAL;
break;
case 'X':
r |= CONVERSION_CAPITAL;
/* Fall through */
case 'x':
r |= CONVERSION_UINT | CONVERSION_HEXADECIMAL;
break;
case 'c':
r |= CONVERSION_INT | CONVERSION_CHARACTER;
break;
case 's':
r |= CONVERSION_CHARP;
break;
case 'p':
r |= CONVERSION_VOIDP | CONVERSION_HEXADECIMAL |
FLAG_ALTERNATE_FORM;
break;
case '%':
r |= CONVERSION_NONE;
break;
}
return r;
最後にconversionの解釈です。このように、型と10進数・16進数などのビットをORしていきます。
do_conversion_string
文字列の幅を整えて出す処理です。
static int
do_conversion_string (const char *str, int f, int width, int precision,
int (*func)(int c, void *data), void *data)
{
int len;
int n = 0;
int leftsp = 0, rightsp = 0;
len = 0;
while (!((f & HAS_PRECISION) && len >= precision) &&
str[len] != '\0')
len++;
if ((f & HAS_WIDTH) && width > len) {
if (f & FLAG_LEFT_ADJUSTED)
rightsp = width - len;
else
leftsp = width - len;
}
while (leftsp--)
PUTCHAR (' ');
while (len--)
PUTCHAR (*str++);
while (rightsp--)
PUTCHAR (' ');
error:
return n;
}
printfのformat指定って案外高機能ですよね。このように長さを調べて、文字列の左右に加えるスペースの数を計算して1バイトずつ出力していきます。
do_conversion_int
整数の変換処理です。
static int
do_conversion_int (unsigned long long val, int f, int width, int precision,
int (*func)(int c, void *data), void *data)
{
int len = 0;
int n = 0;
int leftsp = 0, leftlen = 0, leftzero = 0, rightsp = 0;
char buf[32], *leftbuf = "", *bufp;
if (f & CONVERSION_CHARACTER) {
PUTCHAR ((int)val);
return n;
}
まず真っ先に%cの処理です。%cの時は単に1バイト出して終わりにしています。お気づきの方がいらっしゃると思いますが、widthの解釈をしていませんね。バグですかね。
if ((f & HAS_PRECISION) && precision == 0 && val == 0)
return 0;
precisionがあって0で値も0の時は何も出力しないみたいです。これもwidthの解釈を忘れているような気がします。バグっぽいですね。
if (f & CONVERSION_DECIMAL)
len = valconv (val, buf, sub10, "0123456789");
else if (f & CONVERSION_OCTAL)
len = valconv (val, buf, sub8, "01234567");
else if ((f & CONVERSION_HEXADECIMAL) && (f & CONVERSION_CAPITAL))
len = valconv (val, buf, sub16, "0123456789ABCDEF");
else if (f & CONVERSION_HEXADECIMAL)
len = valconv (val, buf, sub16, "0123456789abcdef");
これが数値の文字列への変換処理を呼び出している部分です。なんと10進数も8進数も16進数もすべてvalconvという関数で行います。詳細は後で。
if ((f & HAS_PRECISION) && precision > len)
leftzero = precision - len;
precisionの処理です。頭に0を出す数を決めます。
if (!(f & CONVERSION_DECIMAL) &&
(f & FLAG_ALTERNATE_FORM) && val != 0) {
if ((f & CONVERSION_OCTAL) && leftzero == 0) {
leftbuf = "0";
leftlen = 1;
} else if (f & CONVERSION_HEXADECIMAL) {
if (f & CONVERSION_CAPITAL)
leftbuf = "0X";
else
leftbuf = "0x";
leftlen = 2;
}
}
#というformat指定がある時は、8進数なら頭に0、16進数なら頭に0Xまたは0xをつける仕掛けがあります。その処理です。
if (f & CONVERSION_DECIMAL) {
if (f & FLAG_PLUS) {
if (f & FLAG_POSITIVE_SIGN) {
leftbuf = "+";
leftlen = 1;
} else if (f & FLAG_POSITIVE_BLANK) {
leftbuf = " ";
leftlen = 1;
}
} else if (f & FLAG_MINUS) {
leftbuf = "-";
leftlen = 1;
}
}
10進数に限り、符号の処理が必要になります。符号なしの場合はFLAG_PLUSもFLAG_MINUSもありません。符号付きの場合、0以上がFLAG_PLUS, 0未満がFLAG_MINUSになります。
if ((f & HAS_WIDTH) && width > leftlen + leftzero + len) {
if (f & FLAG_LEFT_ADJUSTED)
rightsp = width - (leftlen + leftzero + len);
else
leftsp = width - (leftlen + leftzero + len);
}
幅が合うようにスペースの数を計算していきます。
if ((f & FLAG_ZERO_PADDED) && !(f & HAS_PRECISION)) {
leftzero += leftsp;
leftsp = 0;
}
ゼロの数の調整です。
bufp = buf;
while (leftsp--)
PUTCHAR (' ');
while (leftlen--)
PUTCHAR (*leftbuf++);
while (leftzero--)
PUTCHAR ('0');
while (len--)
PUTCHAR (*bufp++);
while (rightsp--)
PUTCHAR (' ');
error:
return n;
}
bufは配列で、変換された文字列が入っています。それと符号や空白などを含めて出力します。
valconv
数値を文字列に変換する処理です。
static int
valconv (unsigned long long val, char *buf, unsigned long long *sub, char *str)
{
int n = 0;
int digit;
if (val == 0) {
*buf++ = '0';
return 1;
}
while (val < *sub)
sub++;
while (*sub) {
digit = 0;
while (val >= *sub) {
digit++;
val -= *sub;
}
*buf++ = str[digit];
n++;
sub++;
}
return n;
}
短いですね! subという引数に以下のような配列のポインターをもらっています。
static unsigned long long sub16[] = {
0x1000000000000000ULL,
0x100000000000000ULL,
0x10000000000000ULL,
0x1000000000000ULL,
0x100000000000ULL,
0x10000000000ULL,
0x1000000000ULL,
0x100000000ULL,
0x10000000ULL,
0x1000000ULL,
0x100000ULL,
0x10000ULL,
0x1000ULL,
0x100ULL,
0x10ULL,
0x1ULL,
0x0ULL,
};
先頭が一番大きな桁の"1"を表しています。大きさを比較しながら減算していき、1桁ずつ文字に変換していきます。当然、16進数の"F"に到達するには16回もの比較と15回もの減算を行うことになり、あまり効率が良いものではありません。
通常こういう時には、割った余りを使うのではないかと思いますが、なんでこんなことをしているのかというと、割り算には制約があるからです。
div %esi
i386のこのような整数の割り算命令は、%edxと%eaxで表される64ビットの値を、%esiの32ビットで割り、商を%eaxに、余りを%edxにそれぞれ32ビットで入れてくれる命令です。しかし、10というような小さな数で割る場合、商が32ビットに収まりきらないケースがよくあります。その場合、この命令は例外を生成してしまい、動きません。対策としては、core/arith.sのmpudiv_128_32関数がやっているように、割り算命令を複数回用い、筆算で1桁ずつ割り算していく時と同じように、32ビットずつ割り算をしていく必要があります。
この制約のため、Cで単純に64ビット同士の割り算を書くと、32ビットコンパイル時には別の関数の呼び出しに変換されてしまいます。BitVisorにはその関数の実装がありませんので、コンパイルに失敗します。対策としてはmpudiv_128_32関数を自分で呼び出す方法もありますが、数が小さいのでわざわざそうするのももったいないなということで、引き算で書いてあるというわけです。
余談
実は、MS-DOSを使っていた頃に、アセンブリ言語でディスクの空き容量や全体容量を表示するプログラムを書いて、割り算命令で例外を食らったことがあります。16ビットなので制約が厳しかったわけです。容量の表示といっても、フロッピーディスクのせいぜい2MBもないくらいの容量であれば、例えばまず10000で割ってから、その商と余りをそれぞれ10で割っていくというやり方で回避できたのですが、それをハードドライブに持ち込んだらクラッシュしてしまいました。当時、割り算命令を複数回使えば多倍長整数の割り算ができるということに全く気づかず、引き算でやる方法も思いつかず、お手上げだったわけですが、今思えば、引き算を繰り返す手法なら、小学生でも思い付いても良かったのではないかなと思います。しかも、当時のi8088では、割り算命令は強烈に遅かったので、10回くらいなら引き算の繰り返しのほうが圧倒的に速かったはずです。