{"thread":{"id":"38503","subject":"[PATCH] decimal_width: avoid integer overflow","startedAt":"2015-02-05T08:14:19Z","lastAt":"2015-02-05T20:42:56Z","messageCount":2,"participants":["Jeff King","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"255619","messageId":"20150205081419.GA7666@peff.net","threadId":"38503","inReplyTo":null,"subject":"[PATCH] decimal_width: avoid integer overflow","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-02-05T08:14:19Z","receivedAt":"2015-02-05T08:14:19Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The decimal_width function originally appeared in blame.c as\n\"lineno_width\", and was designed for calculating the\nprint-width of small-ish integer values (line numbers in\ntext files). In ec7ff5b, it was made into a reusable\nfunction, and in dc801e7, we started using it to align\ndiffstats.\n\nBinary files in a diffstat show byte counts rather than line\nnumbers, meaning they can be quite large (e.g., consider\nadding or removing a 2GB file). decimal_width is not up to\nthe challenge for two reasons:\n\n  1. It takes the value as an \"int\", whereas large files may\n     easily surpass this. The value may be truncated, in\n     which case we will produce an incorrect value.\n\n  2. It counts \"up\" by repeatedly multiplying another\n     integer by 10 until it surpasses the value.  This can\n     cause an infinite loop when the value is close to the\n     largest representable integer.\n\n     For example, consider using a 32-bit signed integer,\n     and a value of 2,140,000,000 (just shy of 2^31-1).\n     We will count up and eventually see that 1,000,000,000\n     is smaller than our value. The next step would be to\n     multiply by 10 and see that 10,000,000,000 is too\n     large, ending the loop. But we can't represent that\n     value, and we have signed overflow.\n\n     This is technically undefined behavior, but a common\n     behavior is to lose the high bits, in which case our\n     iterator will certainly be less than the number. So\n     we'll keep multiplying, overflow again, and so on.\n\nThis patch changes the argument to a uintmax_t (the same\ntype we use to store the diffstat information for binary\nfilese), and counts \"down\" by repeatedly dividing our value\nby 10.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nNote that besides taking a larger type, we also switch to an unsigned\ntype. I don't think a signed value makes any sense here (do we include\nthe \"-\" or not?), and certainly would not have behaved correctly with\nthe old code. I did a quick look over all the callers, and they all look\nto be conceptually unsigned.\n\n cache.h | 2 +-\n pager.c | 8 ++++----\n 2 files changed, 5 insertions(+), 5 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex f704af5..04951dd 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -1498,7 +1498,7 @@ extern const char *pager_program;\n extern int pager_in_use(void);\n extern int pager_use_color;\n extern int term_columns(void);\n-extern int decimal_width(int);\n+extern int decimal_width(uintmax_t);\n extern int check_pager_config(const char *cmd);\n \n extern const char *editor_program;\ndiff --git a/pager.c b/pager.c\nindex f6e8c33..98b2682 100644\n--- a/pager.c\n+++ b/pager.c\n@@ -133,12 +133,12 @@ int term_columns(void)\n /*\n  * How many columns do we need to show this number in decimal?\n  */\n-int decimal_width(int number)\n+int decimal_width(uintmax_t number)\n {\n-\tint i, width;\n+\tint width;\n \n-\tfor (width = 1, i = 10; i <= number; width++)\n-\t\ti *= 10;\n+\tfor (width = 1; number >= 10; width++)\n+\t\tnumber /= 10;\n \treturn width;\n }\n \n-- \n2.3.0.rc1.287.g761fd19\n"},{"id":"255654","messageId":"xmqq1tm4ks33.fsf@gitster.dls.corp.google.com","threadId":"38503","inReplyTo":"20150205081419.GA7666@peff.net","subject":"Re: [PATCH] decimal_width: avoid integer overflow","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-02-05T20:42:56Z","receivedAt":"2015-02-05T20:42:56Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thanks (and thanks for ungetc one, too).\n"}]}