printf加强版
本文前置内容:printf 底层剖析及可变参数探究
本文参考文章:x86环境下将64位整数转换为字符串 - 仲夏夜的乙醇 ,使用位运算代替取模
本节对应分支:printk-enhanced
上节说到 Linux 0.11 的 printk 不支持输出 short (不是不支持,而是表现得和 int 相同)和 long long,本节修改代码来支持 %hd
和 %lld
。
本以为很简单,只需像之前那样对 short 或 long long 数值不断除以基数并取模,依次得到数字字符,然后组成字符串即可。没想到的是,Bochs 的 32 位 x86 环境不支持 64 位除法和取模运算 ,也就是说无法支持以下操作:
long long a = 10;
long long b = 2;
long long c = a / b;
long long d = a % c;
否则会报错,如下:
undefined reference to `__divdi3'
undefined reference to `__moddi3'
__divdi3
和 __moddi3
是 gcc 为我们准备的 64 位除法和取模函数,当发生以上情况时,就用这两个函数来模拟除法和取模 。但由于咋们是自己实现操作系统,所以不能引入外部库函数(就算能,俺也不愿意,俺可不想让复杂的库函数来破坏我们操作系统的简洁性,而且链接了一个库,往往会连着其他许多库)。所以,我们要自己实现 64 位除法和取模函数。
坏消息是,笔者找了一天的相关资料,发现要么实现过于复杂,要么函数有 bug 。绞尽脑汁时,突然在知乎大佬的一篇文章中看见了这样一个等式:
x=2^{32}×H+L
其中 H 为 64 位整型 x 的高 32 位,L 为低 32 位。笔者狂喜,接着在草稿纸上写下了如下等式:
x/y=(2^{32}×H+L)/y=2^{32}×H/y+L/y
其中 y 为 32 位整型,因为 y 就是基数 base,范围在 2~32 之间。
这样一来,不就将 64 位除法转换为了 32 位除法吗?哇哈哈哈哈,原来不过如此嘛!等着,别急,突然觉得哪有问题…计算机的除法是向下取整的,这也能使用分配律吗?当然不行,反例如下:
61/8=(29+32)/8=29/8+32/8=3+4=7 //该等式成立,但换个方式拆分就不行了:
61/8=(31+31)/8=31/8+31/8=3+3=6 //哦豁
所以此方法无效喽,那怎么办?别急,考虑到我们的除法有一定特殊性,除数只为 8、10、16(printf只支持这三种格式打印),这个特性也许能用上。先想想,为什么取整除法不能像上面那样分配?因为拆分方式会影响两方的精度丢失情况,随着双方的精度丢失情况变化,就会影响最终结果。那么,使另一方被整除,从而将精度丢失只划给一方,这样不就能保证结果不受拆分方式而改变了吗?具体做法如下:
对于八进制:x/8=(2^{32}×H+L)/2^{3}=2^{32-3}×H+L/8=2^{29}×H+L/8
对于十六进制:x/16=(2^{32}×H+L)/2^4=2^{32-4}×H+L/16=2^{28}×H+L/16
可以发现,精度丢失只发生在 L/base 上,所以结果一定正确。
上面解决了 64 位除法的问题,那取模怎么解决呢?使用位运算的一个特性就可以完美解决这个问题:
取模运算 (a%b) 在当 b 为 2^n 时可简化为 a & (b - 1)
简单证明:当 b 为 2^n 时,a/b的意义就是 a 右移 n 位,而右移的 n 位的值,就是 a%b 的值。
以上除法和取模的方法只能用于 2 的幂,而 10 不是 2 的幂,所以只有另找办法了。所幸,那位知乎大佬的代码恰好能解决这个问题,详细参见x86环境下将64位整数转换为字符串 - 仲夏夜的乙醇。最终代码如下:
#define is_digit(c) ((c) >= '0' && (c) <= '9')
static int skip_atoi(const char **fmtp)
{
int i=0;
while (is_digit(**fmtp))
i = i*10 + *((*fmtp)++) - '0';
return i;
}
#define ZEROPAD 1 /* pad with zero */
#define SIGN 2 /* unsigned/signed long */
#define PLUS 4 /* show plus */
#define SPACE 8 /* space if plus */
#define LEFT 16 /* left justified */
#define SPECIAL 32 /* 0x */
#define SMALL 64 /* use 'abcdef' instead of 'ABCDEF' */
#define LONG 128 //if long long
unsigned int do_div_10(unsigned int* n)
{
unsigned int t = *n % 10;
*n = *n / 10;
return t;
}
unsigned int do_div_16_8(unsigned long long *n, int base)
{
unsigned int t = base==16?28:29;
unsigned int low = *n;
unsigned int hign= (*n)>>32;
unsigned int mod = ((*n)&(base==16?15:7)); //a & (base - 1)
unsigned long long tmp = (unsigned long long)(1<<t) * hign + low / base;
*n = tmp;
return mod;
}
static char * number(char * str, long long num, int base, int size, int precision,int type)
{
char c,sign,tmp[36];
const char *digits="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int i;
if (type&SMALL) digits="0123456789abcdefghijklmnopqrstuvwxyz";
if (type&LEFT) type &= ~ZEROPAD;
if (base<2 || base>36)
return 0;
c = (type & ZEROPAD) ? '0' : ' ' ;
if (type&SIGN && num<0)
{
sign='-';
num = -num;
}
else
sign=(type&PLUS) ? '+' : ((type&SPACE) ? ' ' : 0);
if (sign) size--;
if (type&SPECIAL)
{
if (base==16) size -= 2;
else if (base==8)
size--;
}
i=0;
if (num==0)
tmp[i++]='0';
if(base==16 || base==8)
{
if(!(type&LONG))
{
int *p = #
*(++p) = 0;
}
while (num!=0)
tmp[i++]=digits[do_div_16_8(&num,base)];
}
if(base==10)
{
if(!(type&LONG))
{
while (num != 0)
tmp[i++] = digits[do_div_10(&num)];
}
else
{
unsigned int low = num;
unsigned int hign= num>>32;
while(low>0)
{
tmp[i++] = ((hign % 10) * 6 + low % 10) % 10 + '0';
low = 429496729 * (hign % 10) + low / 10 + ((hign % 10) * 6 + low % 10) / 10;
hign = hign / 10;
}
}
}
if (i>precision)
precision=i;
size -= precision;
if (!(type&(ZEROPAD+LEFT)))
while(size-->0)
*str++ = ' ';
if (sign)
*str++ = sign;
if (type&SPECIAL)
{
if (base==8)
*str++ = '0';
else if (base==16)
{
*str++ = '0';
*str++ = digits[33];
}
}
if (!(type&LEFT))
while(size-->0)
*str++ = c;
while(i<precision--)
*str++ = '0';
while(i-->0)
*str++ = tmp[i];
while(size-->0)
*str++ = ' ';
return str;
}
int vsprintf(char *buf, const char *fmt, va_list args)
{
int len;
char * str;
char *s;
int *ip;
int flags; /* flags to number() */
int field_width; /* width of output field */
int precision; /* min. # of digits for integers; max number of chars for from string */
int qualifier; /* 'h', 'l', or 'L' for integer fields */
for (str=buf ; *fmt ; ++fmt)
{
if (*fmt != '%')
{
*str++ = *fmt;
continue;
}
/* process flags */
flags = 0;
repeat:
++fmt; /* this also skips first '%' */
switch (*fmt)
{
case '-': flags |= LEFT; goto repeat;
case '+': flags |= PLUS; goto repeat;
case ' ': flags |= SPACE; goto repeat;
case '#': flags |= SPECIAL; goto repeat;
case '0': flags |= ZEROPAD; goto repeat;
}
/* get field width */
field_width = -1;
if (is_digit(*fmt))
field_width = skip_atoi(&fmt);
else if (*fmt == '*')
{
++fmt;
/* it's the next argument */
field_width = va_arg(args, int);
if (field_width < 0)
{
field_width = -field_width;
flags |= LEFT;
}
}
/* get the precision */
precision = -1;
if (*fmt == '.')
{
++fmt;
if (is_digit(*fmt))
precision = skip_atoi(&fmt);
else if (*fmt == '*')
{
++fmt;
/* it's the next argument */
precision = va_arg(args, int);
}
if (precision < 0)
precision = 0;
}
/* get the conversion qualifier */
qualifier = -1;
if (*fmt == 'h')
{
qualifier = *fmt;
++fmt;
}
else if(*fmt == 'l')
{
qualifier = *fmt;
fmt++;
if(*fmt == 'l')
{
qualifier = 'm';
flags |= LONG;
fmt++;
}
}
switch (*fmt)
{
case 'c':
if (!(flags & LEFT))
while (--field_width > 0)
*str++ = ' ';
*str++ = (unsigned char) va_arg(args, int);
while (--field_width > 0)
*str++ = ' ';
break;
case 's':
s = va_arg(args, char *);
len = strlen(s);
if (precision < 0)
precision = len;
else if (len > precision)
len = precision;
if (!(flags & LEFT))
while (len < field_width--)
*str++ = ' ';
for (int i = 0; i < len; ++i)
*str++ = *s++;
while (len < field_width--)
*str++ = ' ';
break;
case 'o':
if(qualifier=='h')
str = number(str, va_arg(args, unsigned short), 8, field_width, precision, flags);
else if(qualifier=='l')
str = number(str, va_arg(args, unsigned long), 8, field_width, precision, flags);
else if(qualifier=='m')
str = number(str, va_arg(args, unsigned long long), 8, field_width, precision, flags);
else
str = number(str, va_arg(args, unsigned int), 8, field_width, precision, flags);
break;
case 'p':
if (field_width == -1)
{
field_width = 8;
flags |= ZEROPAD;
}
str = number(str,(unsigned long) va_arg(args, void *), 16,field_width, precision, flags);
break;
case 'x':
flags |= SMALL;
case 'X':
if(qualifier=='h')
str = number(str, va_arg(args, unsigned short), 16, field_width, precision, flags);
else if(qualifier=='l')
str = number(str, va_arg(args, unsigned long), 16, field_width, precision, flags);
else if(qualifier=='m')// %llx
str = number(str, va_arg(args, unsigned long long), 16, field_width, precision, flags);
else
str = number(str, va_arg(args, unsigned int), 16, field_width, precision, flags);
break;
case 'd':
case 'i':
flags |= SIGN;
if(qualifier=='h')
str = number(str, va_arg(args, short), 10, field_width, precision, flags);
else if(qualifier=='l')
str = number(str, va_arg(args, long), 10, field_width, precision, flags);
else if(qualifier=='m')
str = number(str, va_arg(args, long long), 10, field_width, precision, flags);
else
str = number(str, va_arg(args, int), 10, field_width, precision, flags);
break;
case 'u':
if(qualifier=='h')
str = number(str, va_arg(args, unsigned short), 10, field_width, precision, flags);
else if(qualifier=='l')
str = number(str, va_arg(args, unsigned long), 10, field_width, precision, flags);
else if(qualifier=='m')
str = number(str, va_arg(args, unsigned long long), 10, field_width, precision, flags);
else
str = number(str, va_arg(args, unsigned int), 10, field_width, precision, flags);
break;
case 'n':
ip = va_arg(args, int *);
*ip = (str - buf);
break;
default:
if (*fmt != '%')
*str++ = '%';
if (*fmt)
*str++ = *fmt;
else
--fmt;
break;
}
}
*str = '\0';
return str-buf;
}
-
do_div_16_8 函数就是处理 16 进制和 8 进制的例程,逻辑和前文所述相同,不再赘述。
-
此版本用 do_div_10 来代替了之前版本的 do_div 函数,没什么原因,只是不喜欢内联。do_div_10 只用来处理 32 位除法。
-
86~88 行用来处理 64 位 10 进制除法。
-
第 198 行,当类型为 long long 时,将 qualifier 赋值为 ‘m’,以便在 switch 中识别并处理
-
第 199 行,当类型为 long long 时,将 LONG 标记加入 flag 。打印 8 进制和 16 进制时,如果不为 long long,第 67~68 行则将 num 的高 4 位置零,只计算低 4 位。为什么要这样做呢?因为打印负的 16 进制和 8 进制的 32 位整型时,由于负数(补码)的首位为 1,传入 number 函数时,该数会发生符号扩展(因为 number 的参数 num 是 long long,而实参是 32 位),比如 32 整型数 -1 的二进制是
0XFFFFFFFF
,符号扩展后就成为0xFFFFFFFFFFFFFFFF
,因此造成的结果就是:printf("%x",-1)
也会打印0xFFFFFFFFFFFFFFFF
,而正确的结果应该是 8 个 F 。所以要对于 32 位负整型,需要将高 32 位清零。注意!打印八进制和十六进制的负数时,是直接打印其补码!
最终效果如下:
本文结束。