pprintint.h (19309B)
1 /* 2 * The MIT License (MIT) 3 * 4 * Copyright (c) 2016 Mikkel F. Jørgensen, dvide.com 5 * 6 * Permission is hereby granted, free of charge, to any person obtaining a copy 7 * of this software and associated documentation files (the "Software"), to deal 8 * in the Software without restriction, including without limitation the rights 9 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 10 * copies of the Software, and to permit persons to whom the Software is 11 * furnished to do so, subject to the following conditions: 12 * 13 * The above copyright notice and this permission notice shall be included in all 14 * copies or substantial portions of the Software. 15 * 16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 21 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 22 * SOFTWARE. 23 * 24 * 25 * Fast printing of (u)int8/16/32/64_t, (u)int, (u)long. 26 * 27 * Functions take for the 28 * 29 * int print_<type>(type value, char *buf); 30 * 31 * and returns number of characters printed, excluding trailing '\0' 32 * which is also printed. Prints at most 21 characters including zero- 33 * termination. 34 * 35 * The function `print_bool` is a bit different - it simply prints "true\0" for 36 * non-zero integers, and "false\0" otherwise. 37 * 38 * The general algorithm is in-place formatting using binary search log10 39 * followed by duff device loop unrolling div / 100 stages. 40 * 41 * The simpler post copy algorithm also provided for fmt_(u)int uses a 42 * temp buffer and loops over div/100 and post copy to target buffer. 43 * 44 * 45 * Benchmarks on core-i7, 2.2GHz, 64-bit clang/OS-X -O2: 46 * 47 * print_int64: avg 15ns for values between INT64_MIN + (10^7/2 .. 10^7/2) 48 * print_int64: avg 11ns for values between 10^9 + (0..10,000,000). 49 * print_int32: avg 7ns for values cast from INT64_MIN + (10^7/2 .. 10^7/2) 50 * print_int32: avg 7ns for values between 10^9 + (0..10,000,000). 51 * print_int64: avg 13ns for values between 10^16 + (0..10,000,000). 52 * print_int64: avg 5ns for values between 0 and 10,000,000. 53 * print_int32: avg 5ns for values between 0 and 10,000,000. 54 * print_int16: avg 10ns for values cast from 0 and 10,000,000. 55 * print_int8: avg 4ns for values cast from 0 and 10,000,000. 56 * 57 * Post copy algorithm: 58 * print_int: avg 12ns for values between INT64_MIN + (10^7/2 .. 10^7/2) 59 * print_int: avg 14ns for values between 10^9 + (0..10,000,000). 60 * print_long: avg 29ns for values between INT64_MIN + (10^7/2 .. 10^7/2) 61 * 62 * The post copy algorithm is nearly half as fast as the in-place 63 * algorithm, but can also be faster occasionally - possibly because the 64 * optimizer being able to skip the copy step. 65 */ 66 67 #ifndef PPRINTINT_H 68 #define PPRINTINT_H 69 70 #ifdef __cplusplus 71 extern "C" { 72 #endif 73 74 #ifndef UINT8_MAX 75 #include <stdint.h> 76 #endif 77 78 #include "pattributes.h" /* fallthrough */ 79 80 #define PDIAGNOSTIC_IGNORE_UNUSED_FUNCTION 81 #include "pdiagnostic_push.h" 82 83 static int print_bool(int n, char *p); 84 85 static int print_uint8(uint8_t n, char *p); 86 static int print_uint16(uint16_t n, char *p); 87 static int print_uint32(uint32_t n, char *p); 88 static int print_uint64(uint64_t n, char *p); 89 static int print_int8(int8_t n, char *p); 90 static int print_int16(int16_t n, char *p); 91 static int print_int32(int32_t n, char *p); 92 static int print_int64(int64_t n, char *p); 93 94 /* 95 * Uses slightly slower, but more compact alogrithm 96 * that is not hardcoded to implementation size. 97 * Other types may be defined using macros below. 98 */ 99 static int print_ulong(unsigned long n, char *p); 100 static int print_uint(unsigned int n, char *p); 101 static int print_int(int n, char *p); 102 static int print_long(long n, char *p); 103 104 105 #if defined(__i386__) || defined(__x86_64__) || defined(_M_IX86) || defined(_M_X64) 106 #define __print_unaligned_copy_16(p, q) (*(uint16_t*)(p) = *(uint16_t*)(q)) 107 #else 108 #define __print_unaligned_copy_16(p, q) \ 109 ((((uint8_t*)(p))[0] = ((uint8_t*)(q))[0]), \ 110 (((uint8_t*)(p))[1] = ((uint8_t*)(q))[1])) 111 #endif 112 113 static const char __print_digit_pairs[] = 114 "0001020304050607080910111213141516171819" 115 "2021222324252627282930313233343536373839" 116 "4041424344454647484950515253545556575859" 117 "6061626364656667686970717273747576777879" 118 "8081828384858687888990919293949596979899"; 119 120 #define __print_stage() \ 121 p -= 2; \ 122 dp = __print_digit_pairs + (n % 100) * 2; \ 123 n /= 100; \ 124 __print_unaligned_copy_16(p, dp); 125 126 #define __print_long_stage() \ 127 __print_stage() \ 128 __print_stage() 129 130 #define __print_short_stage() \ 131 *--p = (n % 10) + '0'; \ 132 n /= 10; 133 134 static int print_bool(int n, char *buf) 135 { 136 if (n) { 137 memcpy(buf, "true\0", 5); 138 return 4; 139 } else { 140 memcpy(buf, "false\0", 6); 141 return 5; 142 } 143 } 144 145 static int print_uint8(uint8_t n, char *p) 146 { 147 const char *dp; 148 149 if (n >= 100) { 150 p += 3; 151 *p = '\0'; 152 __print_stage(); 153 p[-1] = (char)n + '0'; 154 return 3; 155 } 156 if (n >= 10) { 157 p += 2; 158 *p = '\0'; 159 __print_stage(); 160 return 2; 161 } 162 p[1] = '\0'; 163 p[0] = (char)n + '0'; 164 return 1; 165 } 166 167 static int print_uint16(uint16_t n, char *p) 168 { 169 int k = 0; 170 const char *dp; 171 172 if (n >= 1000) { 173 if(n >= 10000) { 174 k = 5; 175 } else { 176 k = 4; 177 } 178 } else { 179 if(n >= 100) { 180 k = 3; 181 } else if(n >= 10) { 182 k = 2; 183 } else { 184 k = 1; 185 } 186 } 187 p += k; 188 *p = '\0'; 189 if (k & 1) { 190 switch (k) { 191 case 5: 192 __print_stage(); 193 pattribute(fallthrough); 194 case 3: 195 __print_stage(); 196 pattribute(fallthrough); 197 case 1: 198 p[-1] = (char)n + '0'; 199 } 200 } else { 201 switch (k) { 202 case 4: 203 __print_stage(); 204 pattribute(fallthrough); 205 case 2: 206 __print_stage(); 207 } 208 } 209 return k; 210 } 211 212 static int print_uint32(uint32_t n, char *p) 213 { 214 int k = 0; 215 const char *dp; 216 217 if(n >= 10000UL) { 218 if(n >= 10000000UL) { 219 if(n >= 1000000000UL) { 220 k = 10; 221 } else if(n >= 100000000UL) { 222 k = 9; 223 } else { 224 k = 8; 225 } 226 } else { 227 if(n >= 1000000UL) { 228 k = 7; 229 } else if(n >= 100000UL) { 230 k = 6; 231 } else { 232 k = 5; 233 } 234 } 235 } else { 236 if(n >= 100UL) { 237 if(n >= 1000UL) { 238 k = 4; 239 } else { 240 k = 3; 241 } 242 } else { 243 if(n >= 10UL) { 244 k = 2; 245 } else { 246 k = 1UL; 247 } 248 } 249 } 250 p += k; 251 *p = '\0'; 252 if (k & 1) { 253 switch (k) { 254 case 9: 255 __print_stage(); 256 pattribute(fallthrough); 257 case 7: 258 __print_stage(); 259 pattribute(fallthrough); 260 case 5: 261 __print_stage(); 262 pattribute(fallthrough); 263 case 3: 264 __print_stage(); 265 pattribute(fallthrough); 266 case 1: 267 p[-1] = (char)n + '0'; 268 } 269 } else { 270 switch (k) { 271 case 10: 272 __print_stage(); 273 pattribute(fallthrough); 274 case 8: 275 __print_stage(); 276 pattribute(fallthrough); 277 case 6: 278 __print_stage(); 279 pattribute(fallthrough); 280 case 4: 281 __print_stage(); 282 pattribute(fallthrough); 283 case 2: 284 __print_stage(); 285 } 286 } 287 return k; 288 } 289 290 static int print_uint64(uint64_t n, char *p) 291 { 292 int k = 0; 293 const char *dp; 294 const uint64_t x = 1000000000ULL; 295 296 if (n < x) { 297 return print_uint32((uint32_t)n, p); 298 } 299 if(n >= 10000ULL * x) { 300 if(n >= 10000000ULL * x) { 301 if(n >= 1000000000ULL * x) { 302 if (n >= 10000000000ULL * x) { 303 k = 11 + 9; 304 } else { 305 k = 10 + 9; 306 } 307 } else if(n >= 100000000ULL * x) { 308 k = 9 + 9; 309 } else { 310 k = 8 + 9; 311 } 312 } else { 313 if(n >= 1000000ULL * x) { 314 k = 7 + 9; 315 } else if(n >= 100000ULL * x) { 316 k = 6 + 9; 317 } else { 318 k = 5 + 9; 319 } 320 } 321 } else { 322 if(n >= 100ULL * x) { 323 if(n >= 1000ULL * x) { 324 k = 4 + 9; 325 } else { 326 k = 3 + 9; 327 } 328 } else { 329 if(n >= 10ULL * x) { 330 k = 2 + 9; 331 } else { 332 k = 1 + 9; 333 } 334 } 335 } 336 p += k; 337 *p = '\0'; 338 if (k & 1) { 339 switch (k) { 340 case 19: 341 __print_stage(); 342 pattribute(fallthrough); 343 case 17: 344 __print_stage(); 345 pattribute(fallthrough); 346 case 15: 347 __print_stage(); 348 pattribute(fallthrough); 349 case 13: 350 __print_stage(); 351 pattribute(fallthrough); 352 case 11: 353 __print_stage() 354 __print_short_stage(); 355 } 356 } else { 357 switch (k) { 358 case 20: 359 __print_stage(); 360 pattribute(fallthrough); 361 case 18: 362 __print_stage(); 363 pattribute(fallthrough); 364 case 16: 365 __print_stage(); 366 pattribute(fallthrough); 367 case 14: 368 __print_stage(); 369 pattribute(fallthrough); 370 case 12: 371 __print_stage(); 372 pattribute(fallthrough); 373 case 10: 374 __print_stage(); 375 } 376 } 377 __print_long_stage() 378 __print_long_stage() 379 return k; 380 } 381 382 static int print_int8(int8_t n, char *p) 383 { 384 int sign; 385 386 if ((sign = n < 0)) { 387 *p++ = '-'; 388 n = -n; 389 } 390 return print_uint8((uint8_t)n, p) + sign; 391 } 392 393 static int print_int16(int16_t n, char *p) 394 { 395 int sign; 396 397 if ((sign = n < 0)) { 398 *p++ = '-'; 399 n = -n; 400 } 401 return print_uint16((uint16_t)n, p) + sign; 402 } 403 404 static int print_int32(int32_t n, char *p) 405 { 406 int sign; 407 408 if ((sign = n < 0)) { 409 *p++ = '-'; 410 n = -n; 411 } 412 return print_uint32((uint32_t)n, p) + sign; 413 } 414 415 static int print_int64(int64_t n, char *p) 416 { 417 int sign; 418 419 if ((sign = n < 0)) { 420 *p++ = '-'; 421 n = -n; 422 } 423 return print_uint64((uint64_t)n, p) + sign; 424 } 425 426 #define __define_print_int_simple(NAME, UNAME, T, UT) \ 427 static int UNAME(UT n, char *buf) \ 428 { \ 429 char tmp[20]; \ 430 char* p = tmp + 20; \ 431 char* q = p; \ 432 unsigned int k, m; \ 433 \ 434 while (n >= 100) { \ 435 p -= 2; \ 436 m = (unsigned int)(n % 100) * 2; \ 437 n /= 100; \ 438 __print_unaligned_copy_16(p, __print_digit_pairs + m); \ 439 } \ 440 p -= 2; \ 441 m = (unsigned int)n * 2; \ 442 __print_unaligned_copy_16(p, __print_digit_pairs + m); \ 443 if (n < 10) { \ 444 ++p; \ 445 } \ 446 k = (unsigned int)(q - p); \ 447 while (p != q) { \ 448 *buf++ = *p++; \ 449 } \ 450 *buf = '\0'; \ 451 return (int)k; \ 452 } \ 453 \ 454 static int NAME(T n, char *buf) \ 455 { \ 456 int sign = n < 0; \ 457 \ 458 if (sign) { \ 459 *buf++ = '-'; \ 460 n = -n; \ 461 } \ 462 return UNAME((UT)n, buf) + sign; \ 463 } 464 465 __define_print_int_simple(print_int, print_uint, int, unsigned int) 466 __define_print_int_simple(print_long, print_ulong, long, unsigned long) 467 468 #ifdef PPRINTINT_BENCH 469 int main() { 470 int64_t count = 10000000; /* 10^7 */ 471 #if 0 472 int64_t base = 0; 473 int64_t base = 10000000000000000; /* 10^16 */ 474 int64_t base = 1000000000; /* 10^9 */ 475 #endif 476 int64_t base = INT64_MIN - count/2; 477 char buf[100]; 478 int i, k = 0, n = 0; 479 for (i = 0; i < count; i++) { 480 k = print_int64(i + base, buf); 481 n += buf[0] + buf[k - 1]; 482 } 483 return n; 484 } 485 /* Call with time on executable, multiply time in seconds by 100 to get time unit in ns/number. */ 486 #endif /* PPRINTINT_BENCH */ 487 488 #ifdef PPRINTINT_TEST 489 490 #include <stdio.h> 491 #include <string.h> 492 493 int main() 494 { 495 char buf[21]; 496 int failed = 0; 497 int k; 498 499 k = print_uint64(UINT64_MAX, buf); 500 if (strlen(buf) != k) printf("length error\n"); 501 if (strcmp("18446744073709551615", buf)) { 502 printf("UINT64_MAX didn't print correctly, got:\n'%s'\n", buf); 503 ++failed; 504 } 505 k = print_int64(INT64_MAX, buf); 506 if (strlen(buf) != k) printf("length error\n"); 507 if (strcmp("9223372036854775807", buf)) { 508 printf("INT64_MAX didn't print correctly, got:\n'%s'\n", buf); 509 ++failed; 510 } 511 k = print_int64(INT64_MIN, buf); 512 if (strlen(buf) != k) printf("length error\n"); 513 if (strcmp("-9223372036854775808", buf)) { 514 printf("INT64_MIN didn't print correctly, got:\n'%s'\n", buf); 515 ++failed; 516 } 517 k = print_uint32(UINT32_MAX, buf); 518 if (strlen(buf) != k) printf("length error\n"); 519 if (strcmp("4294967295", buf)) { 520 printf("UINT32_MAX didn't print correctly, got:\n'%s'\n", buf); 521 ++failed; 522 } 523 k = print_int32(INT32_MAX, buf); 524 if (strlen(buf) != k) printf("length error\n"); 525 if (strcmp("2147483647", buf)) { 526 printf("INT32_MAX didn't print correctly, got:\n'%s'\n", buf); 527 ++failed; 528 } 529 k = print_int32(INT32_MIN, buf); 530 if (strlen(buf) != k) printf("length error\n"); 531 if (strcmp("-2147483648", buf)) { 532 printf("INT32_MIN didn't print correctly, got:\n'%s'\n", buf); 533 ++failed; 534 } 535 k = print_uint16(UINT16_MAX, buf); 536 if (strlen(buf) != k) printf("length error\n"); 537 if (strcmp("65535", buf)) { 538 printf("UINT16_MAX didn't print correctly, got:\n'%s'\n", buf); 539 ++failed; 540 } 541 k = print_int16(INT16_MAX, buf); 542 if (strlen(buf) != k) printf("length error\n"); 543 if (strcmp("32767", buf)) { 544 printf("INT16_MAX didn't print correctly, got:\n'%s'\n", buf); 545 ++failed; 546 } 547 k = print_int16(INT16_MIN, buf); 548 if (strlen(buf) != k) printf("length error\n"); 549 if (strcmp("-32768", buf)) { 550 printf("INT16_MIN didn't print correctly, got:\n'%s'\n", buf); 551 ++failed; 552 } 553 k = print_uint8(UINT8_MAX, buf); 554 if (strlen(buf) != k) printf("length error\n"); 555 if (strcmp("255", buf)) { 556 printf("INT8_MAX didn't print correctly, got:\n'%s'\n", buf); 557 ++failed; 558 } 559 k = print_int8(INT8_MAX, buf); 560 if (strlen(buf) != k) printf("length error\n"); 561 if (strcmp("127", buf)) { 562 printf("INT8_MAX didn't print correctly, got:\n'%s'\n", buf); 563 ++failed; 564 } 565 k = print_int8(INT8_MIN, buf); 566 if (strlen(buf) != k) printf("length error\n"); 567 if (strcmp("-128", buf)) { 568 printf("INT8_MIN didn't print correctly, got:\n'%s'\n", buf); 569 ++failed; 570 } 571 k = print_int(INT32_MAX, buf); 572 if (strlen(buf) != k) printf("length error\n"); 573 if (strcmp("2147483647", buf)) { 574 printf("INT32_MAX didn't print correctly with k = print_int, got:\n'%s'\n", buf); 575 ++failed; 576 } 577 k = print_int(INT32_MIN, buf); 578 if (strlen(buf) != k) printf("length error\n"); 579 if (strcmp("-2147483648", buf)) { 580 printf("INT32_MIN didn't print correctly k = print_int, got:\n'%s'\n", buf); 581 ++failed; 582 } 583 k = print_long(INT32_MAX, buf); 584 if (strlen(buf) != k) printf("length error\n"); 585 if (strcmp("2147483647", buf)) { 586 printf("INT32_MAX didn't print correctly with fmt_long, got:\n'%s'\n", buf); 587 ++failed; 588 } 589 k = print_long(INT32_MIN, buf); 590 if (strlen(buf) != k) printf("length error\n"); 591 if (strcmp("-2147483648", buf)) { 592 printf("INT32_MIN didn't print correctly fmt_long, got:\n'%s'\n", buf); 593 ++failed; 594 } 595 k = print_bool(1, buf); 596 if (strlen(buf) != k) printf("length error\n"); 597 if (strcmp("true", buf) { 598 printf("1 didn't print 'true' as expected, got:\n'%s'\n", buf); 599 ++failed; 600 } 601 k = print_bool(-1, buf); 602 if (strlen(buf) != k) printf("length error\n"); 603 if (strcmp("true", buf) { 604 printf("-1 didn't print 'true' as expected, got:\n'%s'\n", buf); 605 ++failed; 606 } 607 k = print_bool(, buf); 608 if (strlen(buf) != k) printf("length error\n"); 609 if (strcmp("false", buf) { 610 printf("0 didn't print 'false' as expected, got:\n'%s'\n", buf); 611 ++failed; 612 } 613 if (failed) { 614 printf("FAILED\n"); 615 return -1; 616 } 617 printf("SUCCESS\n"); 618 return 0; 619 } 620 #endif /* PPRINTINT_TEST */ 621 622 #include "pdiagnostic_pop.h" 623 624 #ifdef __cplusplus 625 } 626 #endif 627 628 #endif /* PPRINTINT_H */