From e49317d415f5a44bad8377a208d61902d752303e Mon Sep 17 00:00:00 2001 From: George Spelvin Date: Thu, 4 Oct 2012 17:12:27 -0700 Subject: lib: vsprintf: optimize division by 10 for small integers Shrink the reciprocal approximations used in put_dec_full4() based on the comments in put_dec_full9(). Signed-off-by: George Spelvin Cc: Denys Vlasenko Cc: Michal Nazarewicz Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/vsprintf.c | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) (limited to 'lib/vsprintf.c') diff --git a/lib/vsprintf.c b/lib/vsprintf.c index 0e337541f00..67e74cbefa9 100644 --- a/lib/vsprintf.c +++ b/lib/vsprintf.c @@ -243,13 +243,14 @@ char *put_dec(char *buf, unsigned long long n) /* Second algorithm: valid only for 64-bit long longs */ +/* See comment in put_dec_full9 for choice of constants */ static noinline_for_stack char *put_dec_full4(char *buf, unsigned q) { unsigned r; - r = (q * 0xcccd) >> 19; + r = (q * 0xccd) >> 15; *buf++ = (q - 10 * r) + '0'; - q = (r * 0x199a) >> 16; + q = (r * 0xcd) >> 11; *buf++ = (r - 10 * q) + '0'; r = (q * 0xcd) >> 11; *buf++ = (q - 10 * r) + '0'; -- cgit v1.2.3-70-g09d2 From 2359172a75986359ce9cf041a9aca6a32cdf8779 Mon Sep 17 00:00:00 2001 From: George Spelvin Date: Thu, 4 Oct 2012 17:12:29 -0700 Subject: lib: vsprintf: optimize division by 10000 The same multiply-by-inverse technique can be used to convert division by 10000 to a 32x32->64-bit multiply. Signed-off-by: George Spelvin Cc: Denys Vlasenko Cc: Michal Nazarewicz Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/vsprintf.c | 60 ++++++++++++++++++++++++++++++++-------------------------- 1 file changed, 33 insertions(+), 27 deletions(-) (limited to 'lib/vsprintf.c') diff --git a/lib/vsprintf.c b/lib/vsprintf.c index 67e74cbefa9..8cb7635b2ce 100644 --- a/lib/vsprintf.c +++ b/lib/vsprintf.c @@ -245,17 +245,32 @@ char *put_dec(char *buf, unsigned long long n) /* See comment in put_dec_full9 for choice of constants */ static noinline_for_stack -char *put_dec_full4(char *buf, unsigned q) +void put_dec_full4(char *buf, unsigned q) { unsigned r; r = (q * 0xccd) >> 15; - *buf++ = (q - 10 * r) + '0'; + buf[0] = (q - 10 * r) + '0'; q = (r * 0xcd) >> 11; - *buf++ = (r - 10 * q) + '0'; + buf[1] = (r - 10 * q) + '0'; r = (q * 0xcd) >> 11; - *buf++ = (q - 10 * r) + '0'; - *buf++ = r + '0'; - return buf; + buf[2] = (q - 10 * r) + '0'; + buf[3] = r + '0'; +} + +/* + * Call put_dec_full4 on x % 10000, return x / 10000. + * The approximation x/10000 == (x * 0x346DC5D7) >> 43 + * holds for all x < 1,128,869,999. The largest value this + * helper will ever be asked to convert is 1,125,520,955. + * (d1 in the put_dec code, assuming n is all-ones). + */ +static +unsigned put_dec_helper4(char *buf, unsigned x) +{ + uint32_t q = (x * (uint64_t)0x346DC5D7) >> 43; + + put_dec_full4(buf, x - q * 10000); + return q; } /* Based on code by Douglas W. Jones found at @@ -277,28 +292,19 @@ char *put_dec(char *buf, unsigned long long n) d3 = (h >> 16); /* implicit "& 0xffff" */ q = 656 * d3 + 7296 * d2 + 5536 * d1 + ((uint32_t)n & 0xffff); + q = put_dec_helper4(buf, q); + + q += 7671 * d3 + 9496 * d2 + 6 * d1; + q = put_dec_helper4(buf+4, q); + + q += 4749 * d3 + 42 * d2; + q = put_dec_helper4(buf+8, q); - buf = put_dec_full4(buf, q % 10000); - q = q / 10000; - - d1 = q + 7671 * d3 + 9496 * d2 + 6 * d1; - buf = put_dec_full4(buf, d1 % 10000); - q = d1 / 10000; - - d2 = q + 4749 * d3 + 42 * d2; - buf = put_dec_full4(buf, d2 % 10000); - q = d2 / 10000; - - d3 = q + 281 * d3; - if (!d3) - goto done; - buf = put_dec_full4(buf, d3 % 10000); - q = d3 / 10000; - if (!q) - goto done; - buf = put_dec_full4(buf, q); - done: - while (buf[-1] == '0') + q += 281 * d3; + buf += 12; + if (q) + buf = put_dec_trunc8(buf, q); + else while (buf[-1] == '0') --buf; return buf; -- cgit v1.2.3-70-g09d2 From cb239d0a97d573150d6106a92c0641da0d03f6a1 Mon Sep 17 00:00:00 2001 From: George Spelvin Date: Thu, 4 Oct 2012 17:12:30 -0700 Subject: lib: vsprintf: optimize put_dec_trunc8() If you're going to have a conditional branch after each 32x32->64-bit multiply, might as well shrink the code and make it a loop. This also avoids using the long multiply for small integers. (This leaves the comments in a confusing state, but that's a separate patch to make review easier.) Signed-off-by: George Spelvin Cc: Denys Vlasenko Cc: Michal Nazarewicz Cc: Rabin Vincent Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/vsprintf.c | 22 ++++++---------------- 1 file changed, 6 insertions(+), 16 deletions(-) (limited to 'lib/vsprintf.c') diff --git a/lib/vsprintf.c b/lib/vsprintf.c index 8cb7635b2ce..c2236f14640 100644 --- a/lib/vsprintf.c +++ b/lib/vsprintf.c @@ -174,22 +174,12 @@ char *put_dec_trunc8(char *buf, unsigned r) unsigned q; /* Copy of previous function's body with added early returns */ - q = (r * (uint64_t)0x1999999a) >> 32; - *buf++ = (r - 10 * q) + '0'; /* 2 */ - if (q == 0) - return buf; - r = (q * (uint64_t)0x1999999a) >> 32; - *buf++ = (q - 10 * r) + '0'; /* 3 */ - if (r == 0) - return buf; - q = (r * (uint64_t)0x1999999a) >> 32; - *buf++ = (r - 10 * q) + '0'; /* 4 */ - if (q == 0) - return buf; - r = (q * (uint64_t)0x1999999a) >> 32; - *buf++ = (q - 10 * r) + '0'; /* 5 */ - if (r == 0) - return buf; + while (r >= 10000) { + q = r + '0'; + r = (r * (uint64_t)0x1999999a) >> 32; + *buf++ = q - 10*r; + } + q = (r * 0x199a) >> 16; *buf++ = (r - 10 * q) + '0'; /* 6 */ if (q == 0) -- cgit v1.2.3-70-g09d2 From f40005165f7f0bda6cc268bdbcaad98a8f26fb1a Mon Sep 17 00:00:00 2001 From: George Spelvin Date: Thu, 4 Oct 2012 17:12:32 -0700 Subject: lib: vsprintf: fix broken comments Numbering the 8 potential digits 2 though 9 never did make a lot of sense. Signed-off-by: George Spelvin Cc: Denys Vlasenko Cc: Michal Nazarewicz Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/vsprintf.c | 14 +++++++------- 1 file changed, 7 insertions(+), 7 deletions(-) (limited to 'lib/vsprintf.c') diff --git a/lib/vsprintf.c b/lib/vsprintf.c index c2236f14640..852f89f590a 100644 --- a/lib/vsprintf.c +++ b/lib/vsprintf.c @@ -180,19 +180,19 @@ char *put_dec_trunc8(char *buf, unsigned r) *buf++ = q - 10*r; } - q = (r * 0x199a) >> 16; - *buf++ = (r - 10 * q) + '0'; /* 6 */ + q = (r * 0x199a) >> 16; /* r <= 9999 */ + *buf++ = (r - 10 * q) + '0'; if (q == 0) return buf; - r = (q * 0xcd) >> 11; - *buf++ = (q - 10 * r) + '0'; /* 7 */ + r = (q * 0xcd) >> 11; /* q <= 999 */ + *buf++ = (q - 10 * r) + '0'; if (r == 0) return buf; - q = (r * 0xcd) >> 11; - *buf++ = (r - 10 * q) + '0'; /* 8 */ + q = (r * 0xcd) >> 11; /* r <= 99 */ + *buf++ = (r - 10 * q) + '0'; if (q == 0) return buf; - *buf++ = q + '0'; /* 9 */ + *buf++ = q + '0'; /* q <= 9 */ return buf; } -- cgit v1.2.3-70-g09d2 From 7c59154e7548429ff80384803577176466d2ab9a Mon Sep 17 00:00:00 2001 From: Andy Shevchenko Date: Thu, 4 Oct 2012 17:12:33 -0700 Subject: lib/vsprintf: update documentation to cover all of %p[Mm][FR] Acked-by: Andrei Emeltchenko Signed-off-by: Andy Shevchenko Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- Documentation/printk-formats.txt | 1 + lib/vsprintf.c | 5 ++++- 2 files changed, 5 insertions(+), 1 deletion(-) (limited to 'lib/vsprintf.c') diff --git a/Documentation/printk-formats.txt b/Documentation/printk-formats.txt index 7561d7ed8e1..8ffb274367c 100644 --- a/Documentation/printk-formats.txt +++ b/Documentation/printk-formats.txt @@ -69,6 +69,7 @@ MAC/FDDI addresses: %pMR 05:04:03:02:01:00 %pMF 00-01-02-03-04-05 %pm 000102030405 + %pmR 050403020100 For printing 6-byte MAC/FDDI addresses in hex notation. The 'M' and 'm' specifiers result in a printed address with ('M') or without ('m') byte diff --git a/lib/vsprintf.c b/lib/vsprintf.c index 852f89f590a..9287e254993 100644 --- a/lib/vsprintf.c +++ b/lib/vsprintf.c @@ -987,7 +987,7 @@ int kptr_restrict __read_mostly; * - 'm' For a 6-byte MAC address, it prints the hex address without colons * - 'MF' For a 6-byte MAC FDDI address, it prints the address * with a dash-separated hex notation - * - '[mM]R For a 6-byte MAC address, Reverse order (Bluetooth) + * - '[mM]R' For a 6-byte MAC address, Reverse order (Bluetooth) * - 'I' [46] for IPv4/IPv6 addresses printed in the usual way * IPv4 uses dot-separated decimal without leading 0's (1.2.3.4) * IPv6 uses colon separated network-order 16 bit hex with leading 0's @@ -1338,7 +1338,10 @@ qualifier: * %pR output the address range in a struct resource with decoded flags * %pr output the address range in a struct resource with raw flags * %pM output a 6-byte MAC address with colons + * %pMR output a 6-byte MAC address with colons in reversed order + * %pMF output a 6-byte MAC address with dashes * %pm output a 6-byte MAC address without colons + * %pmR output a 6-byte MAC address without colons in reversed order * %pI4 print an IPv4 address without leading zeros * %pi4 print an IPv4 address with leading zeros * %pI6 print an IPv6 address with colons -- cgit v1.2.3-70-g09d2 From da99075c1d368315e1508b6143226c0d27b621e0 Mon Sep 17 00:00:00 2001 From: Jan Beulich Date: Thu, 4 Oct 2012 17:13:24 -0700 Subject: lib/vsprintf.c: improve standard conformance of sscanf() Xen's pciback points out a couple of deficiencies with vsscanf()'s standard conformance: - Trailing character matching cannot be checked by the caller: With a format string of "(%x:%x.%x) %n" absence of the closing parenthesis cannot be checked, as input of "(00:00.0)" doesn't cause the %n to be evaluated (because of the code not skipping white space before the trailing %n). - The parameter corresponding to a trailing %n could get filled even if there was a matching error: With a format string of "(%x:%x.%x)%n", input of "(00:00.0]" would still fill the respective variable pointed to (and hence again make the mismatch non-detectable by the caller). This patch aims at fixing those, but leaves other non-conforming aspects of it untouched, among them these possibly relevant ones: - improper handling of the assignment suppression character '*' (blindly discarding all succeeding non-white space from the format and input strings), - not honoring conversion specifiers for %n, - not recognizing the C99 conversion specifier 't' (recognized by vsprintf()). Signed-off-by: Jan Beulich Cc: Konrad Rzeszutek Wilk Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/vsprintf.c | 33 ++++++++++++++------------------- 1 file changed, 14 insertions(+), 19 deletions(-) (limited to 'lib/vsprintf.c') diff --git a/lib/vsprintf.c b/lib/vsprintf.c index 9287e254993..39c99fea7c0 100644 --- a/lib/vsprintf.c +++ b/lib/vsprintf.c @@ -2017,7 +2017,7 @@ int vsscanf(const char *buf, const char *fmt, va_list args) s16 field_width; bool is_sign; - while (*fmt && *str) { + while (*fmt) { /* skip any white space in format */ /* white space in format matchs any amount of * white space, including none, in the input. @@ -2042,6 +2042,8 @@ int vsscanf(const char *buf, const char *fmt, va_list args) * advance both strings to next white space */ if (*fmt == '*') { + if (!*str) + break; while (!isspace(*fmt) && *fmt != '%' && *fmt) fmt++; while (!isspace(*str) && *str) @@ -2070,7 +2072,17 @@ int vsscanf(const char *buf, const char *fmt, va_list args) } } - if (!*fmt || !*str) + if (!*fmt) + break; + + if (*fmt == 'n') { + /* return number of characters read so far */ + *va_arg(args, int *) = str - buf; + ++fmt; + continue; + } + + if (!*str) break; base = 10; @@ -2103,13 +2115,6 @@ int vsscanf(const char *buf, const char *fmt, va_list args) num++; } continue; - case 'n': - /* return number of characters read so far */ - { - int *i = (int *)va_arg(args, int*); - *i = str - buf; - } - continue; case 'o': base = 8; break; @@ -2210,16 +2215,6 @@ int vsscanf(const char *buf, const char *fmt, va_list args) str = next; } - /* - * Now we've come all the way through so either the input string or the - * format ended. In the former case, there can be a %n at the current - * position in the format that needs to be filled. - */ - if (*fmt == '%' && *(fmt + 1) == 'n') { - int *p = (int *)va_arg(args, int *); - *p = str - buf; - } - return num; } EXPORT_SYMBOL(vsscanf); -- cgit v1.2.3-70-g09d2