Skip to content

Instantly share code, notes, and snippets.

@Veedrac
Last active August 2, 2019 09:29
Show Gist options
  • Save Veedrac/069dd35f896de4df4e14b881a455ca47 to your computer and use it in GitHub Desktop.
Save Veedrac/069dd35f896de4df4e14b881a455ca47 to your computer and use it in GitHub Desktop.
Prints integers really fast. Pads output with null bytes to length-20 for speed reasons. The code is released under CC0. The length calculation (neg_log2 * 1233 >> 12) is from Bit Twiddling Hacks, and also public domain.
const char DIGIT_PAIRS[] =
"00" "01" "02" "03" "04" "05" "06" "07" "08" "09"
"10" "11" "12" "13" "14" "15" "16" "17" "18" "19"
"20" "21" "22" "23" "24" "25" "26" "27" "28" "29"
"30" "31" "32" "33" "34" "35" "36" "37" "38" "39"
"40" "41" "42" "43" "44" "45" "46" "47" "48" "49"
"50" "51" "52" "53" "54" "55" "56" "57" "58" "59"
"60" "61" "62" "63" "64" "65" "66" "67" "68" "69"
"70" "71" "72" "73" "74" "75" "76" "77" "78" "79"
"80" "81" "82" "83" "84" "85" "86" "87" "88" "89"
"90" "91" "92" "93" "94" "95" "96" "97" "98" "99";
size_t __attribute__ ((noinline)) print_buf64(char *buffer, uint64_t value) {
char digits[40];
memset(digits + 20, '\0', 20);
uint32_t top12 = value / UINT64_C(100000000);
uint32_t top4 = value / UINT64_C(10000000000000000);
uint32_t uvalue_0 = uint32_t(value) - top12 * 100000000;
uint32_t uvalue_1 = (uvalue_0 * UINT64_C(1374389535)) >> 37;
uint32_t uvalue_2 = (uvalue_0 * UINT64_C(3518437209)) >> 45;
uint32_t uvalue_3 = (uvalue_0 * UINT64_C(1125899907)) >> 50;
memcpy(digits + 18, &DIGIT_PAIRS[uvalue_0 * 2 - uvalue_1 * 200], 2);
memcpy(digits + 16, &DIGIT_PAIRS[uvalue_1 * 2 - uvalue_2 * 200], 2);
memcpy(digits + 14, &DIGIT_PAIRS[uvalue_2 * 2 - uvalue_3 * 200], 2);
memcpy(digits + 12, &DIGIT_PAIRS[uvalue_3 * 2], 2);
uint32_t uvalue_4 = top12 - top4 * 100000000;
uint32_t uvalue_5 = (uvalue_4 * UINT64_C(1374389535)) >> 37;
uint32_t uvalue_6 = (uvalue_4 * UINT64_C(3518437209)) >> 45;
uint32_t uvalue_7 = (uvalue_4 * UINT64_C(1125899907)) >> 50;
memcpy(digits + 10, &DIGIT_PAIRS[uvalue_4 * 2 - uvalue_5 * 200], 2);
memcpy(digits + 8, &DIGIT_PAIRS[uvalue_5 * 2 - uvalue_6 * 200], 2);
memcpy(digits + 6, &DIGIT_PAIRS[uvalue_6 * 2 - uvalue_7 * 200], 2);
memcpy(digits + 4, &DIGIT_PAIRS[uvalue_7 * 2], 2);
uint32_t uvalue_8 = top4;
uint32_t uvalue_9 = (uvalue_8 * UINT64_C(1374389535)) >> 37;
memcpy(digits + 2, &DIGIT_PAIRS[uvalue_8 * 2 - uvalue_9 * 200], 2);
memcpy(digits + 0, &DIGIT_PAIRS[uvalue_9 * 2], 2);
size_t neg_log2 = __builtin_clzll(value | 1);
size_t offset = neg_log2 * 1233 >> 12; // 1233 / 2**12 ≈ log10(2)
offset += digits[offset] == '0';
memcpy(buffer, digits + offset, 20);
return 20 - offset;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment