{"thread":{"id":"46331","subject":"[PATCH] use DIV_ROUND_UP","startedAt":"2017-07-08T10:35:51Z","lastAt":"2017-07-11T07:42:01Z","messageCount":7,"participants":["René Scharfe","Martin Ågren","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"323989","messageId":"4d2c274a-f6cb-6ea5-304f-51a3152cc436@web.de","threadId":"46331","inReplyTo":null,"subject":"[PATCH] use DIV_ROUND_UP","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-07-08T10:35:35Z","receivedAt":"2017-07-08T10:35:51Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Convert code that divides and rounds up to use DIV_ROUND_UP to make the\nintent clearer and reduce the number of magic constants.\n\nSigned-off-by: Rene Scharfe <l.s.r@web.de>\n---\n builtin/gc.c           | 2 +-\n builtin/grep.c         | 2 +-\n builtin/log.c          | 2 +-\n builtin/receive-pack.c | 2 +-\n diff.c                 | 2 +-\n ewah/ewah_bitmap.c     | 4 ++--\n imap-send.c            | 2 +-\n sha1_name.c            | 2 +-\n shallow.c              | 8 ++++----\n 9 files changed, 13 insertions(+), 13 deletions(-)\n\ndiff --git a/builtin/gc.c b/builtin/gc.c\nindex bd91f136fe..2ba50a2873 100644\n--- a/builtin/gc.c\n+++ b/builtin/gc.c\n@@ -149,7 +149,7 @@ static int too_many_loose_objects(void)\n \tif (!dir)\n \t\treturn 0;\n \n-\tauto_threshold = (gc_auto_threshold + 255) / 256;\n+\tauto_threshold = DIV_ROUND_UP(gc_auto_threshold, 256);\n \twhile ((ent = readdir(dir)) != NULL) {\n \t\tif (strspn(ent->d_name, \"0123456789abcdef\") != 38 ||\n \t\t    ent->d_name[38] != '\\0')\ndiff --git a/builtin/grep.c b/builtin/grep.c\nindex fa351c49f4..0d6e669732 100644\n--- a/builtin/grep.c\n+++ b/builtin/grep.c\n@@ -543,7 +543,7 @@ static void compile_submodule_options(const struct grep_opt *opt,\n \t * submodule process has its own thread pool.\n \t */\n \targv_array_pushf(&submodule_options, \"--threads=%d\",\n-\t\t\t (num_threads + 1) / 2);\n+\t\t\t DIV_ROUND_UP(num_threads, 2));\n \n \t/* Add Pathspecs */\n \targv_array_push(&submodule_options, \"--\");\ndiff --git a/builtin/log.c b/builtin/log.c\nindex 8ca1de9894..c6362cf92e 100644\n--- a/builtin/log.c\n+++ b/builtin/log.c\n@@ -1308,7 +1308,7 @@ static struct commit *get_base_commit(const char *base_commit,\n \n \t\tif (rev_nr % 2)\n \t\t\trev[i] = rev[2 * i];\n-\t\trev_nr = (rev_nr + 1) / 2;\n+\t\trev_nr = DIV_ROUND_UP(rev_nr, 2);\n \t}\n \n \tif (!in_merge_bases(base, rev[0]))\ndiff --git a/builtin/receive-pack.c b/builtin/receive-pack.c\nindex 71c0c768db..cabdc55e09 100644\n--- a/builtin/receive-pack.c\n+++ b/builtin/receive-pack.c\n@@ -1806,7 +1806,7 @@ static const char *unpack_with_sideband(struct shallow_info *si)\n static void prepare_shallow_update(struct command *commands,\n \t\t\t\t   struct shallow_info *si)\n {\n-\tint i, j, k, bitmap_size = (si->ref->nr + 31) / 32;\n+\tint i, j, k, bitmap_size = DIV_ROUND_UP(si->ref->nr, 32);\n \n \tALLOC_ARRAY(si->used_shallow, si->shallow->nr);\n \tassign_shallow_commits_to_refs(si, si->used_shallow, NULL);\ndiff --git a/diff.c b/diff.c\nindex 00b4c86698..85e714f6c6 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -2095,7 +2095,7 @@ static void show_dirstat_by_line(struct diffstat_t *data, struct diff_options *o\n \t\t\t * bytes per \"line\".\n \t\t\t * This is stupid and ugly, but very cheap...\n \t\t\t */\n-\t\t\tdamage = (damage + 63) / 64;\n+\t\t\tdamage = DIV_ROUND_UP(damage, 64);\n \t\tALLOC_GROW(dir.files, dir.nr + 1, dir.alloc);\n \t\tdir.files[dir.nr].name = file->name;\n \t\tdir.files[dir.nr].changed = damage;\ndiff --git a/ewah/ewah_bitmap.c b/ewah/ewah_bitmap.c\nindex 2dc9c82ecf..06c479f70a 100644\n--- a/ewah/ewah_bitmap.c\n+++ b/ewah/ewah_bitmap.c\n@@ -210,8 +210,8 @@ size_t ewah_add(struct ewah_bitmap *self, eword_t word)\n void ewah_set(struct ewah_bitmap *self, size_t i)\n {\n \tconst size_t dist =\n-\t\t(i + BITS_IN_EWORD) / BITS_IN_EWORD -\n-\t\t(self->bit_size + BITS_IN_EWORD - 1) / BITS_IN_EWORD;\n+\t\tDIV_ROUND_UP(i + 1, BITS_IN_EWORD) -\n+\t\tDIV_ROUND_UP(self->bit_size, BITS_IN_EWORD);\n \n \tassert(i >= self->bit_size);\n \ndiff --git a/imap-send.c b/imap-send.c\nindex 351e84aea1..b2d0b849bb 100644\n--- a/imap-send.c\n+++ b/imap-send.c\n@@ -861,7 +861,7 @@ static char hexchar(unsigned int b)\n \treturn b < 10 ? '0' + b : 'a' + (b - 10);\n }\n \n-#define ENCODED_SIZE(n) (4*((n+2)/3))\n+#define ENCODED_SIZE(n) (4 * DIV_ROUND_UP((n), 3))\n static char *cram(const char *challenge_64, const char *user, const char *pass)\n {\n \tint i, resp_len, encoded_len, decoded_len;\ndiff --git a/sha1_name.c b/sha1_name.c\nindex e7f7b12ceb..8c513dbff6 100644\n--- a/sha1_name.c\n+++ b/sha1_name.c\n@@ -492,7 +492,7 @@ int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)\n \t\t * together we need to divide by 2; but we also want to round\n \t\t * odd numbers up, hence adding one before dividing.\n \t\t */\n-\t\tlen = (len + 1) / 2;\n+\t\tlen = DIV_ROUND_UP(len, 2);\n \t\t/*\n \t\t * For very small repos, we stick with our regular fallback.\n \t\t */\ndiff --git a/shallow.c b/shallow.c\nindex ef7ca78993..54359d5490 100644\n--- a/shallow.c\n+++ b/shallow.c\n@@ -443,7 +443,7 @@ struct paint_info {\n \n static uint32_t *paint_alloc(struct paint_info *info)\n {\n-\tunsigned nr = (info->nr_bits + 31) / 32;\n+\tunsigned nr = DIV_ROUND_UP(info->nr_bits, 32);\n \tunsigned size = nr * sizeof(uint32_t);\n \tvoid *p;\n \tif (!info->pool_count || size > info->end - info->free) {\n@@ -471,7 +471,7 @@ static void paint_down(struct paint_info *info, const struct object_id *oid,\n {\n \tunsigned int i, nr;\n \tstruct commit_list *head = NULL;\n-\tint bitmap_nr = (info->nr_bits + 31) / 32;\n+\tint bitmap_nr = DIV_ROUND_UP(info->nr_bits, 32);\n \tsize_t bitmap_size = st_mult(sizeof(uint32_t), bitmap_nr);\n \tstruct commit *c = lookup_commit_reference_gently(oid, 1);\n \tuint32_t *tmp; /* to be freed before return */\n@@ -611,7 +611,7 @@ void assign_shallow_commits_to_refs(struct shallow_info *info,\n \t\tpaint_down(&pi, ref->oid + i, i);\n \n \tif (used) {\n-\t\tint bitmap_size = ((pi.nr_bits + 31) / 32) * sizeof(uint32_t);\n+\t\tint bitmap_size = DIV_ROUND_UP(pi.nr_bits, 32) * sizeof(uint32_t);\n \t\tmemset(used, 0, sizeof(*used) * info->shallow->nr);\n \t\tfor (i = 0; i < nr_shallow; i++) {\n \t\t\tconst struct commit *c = lookup_commit(&oid[shallow[i]]);\n@@ -672,7 +672,7 @@ static void post_assign_shallow(struct shallow_info *info,\n \tstruct commit *c;\n \tuint32_t **bitmap;\n \tint dst, i, j;\n-\tint bitmap_nr = (info->ref->nr + 31) / 32;\n+\tint bitmap_nr = DIV_ROUND_UP(info->ref->nr, 32);\n \tstruct commit_array ca;\n \n \ttrace_printf_key(&trace_shallow, \"shallow: post_assign_shallow\\n\");\n-- \n2.13.2\n\n"},{"id":"324027","messageId":"CAN0heSr0qJv7VqaasLGNFbNDbqYOoqmi3FyLkb=co4E10Y9VOg@mail.gmail.com","threadId":"46331","inReplyTo":"4d2c274a-f6cb-6ea5-304f-51a3152cc436@web.de","subject":"Re: [PATCH] use DIV_ROUND_UP","fromName":"Martin Ågren","fromEmail":"martin.agren@gmail.com","sentAt":"2017-07-09T13:25:46Z","receivedAt":"2017-07-09T13:25:54Z","isPatch":true,"sender":{"key":"martin.agren@gmail.com","avatar":null},"body":"On 8 July 2017 at 12:35, René Scharfe <l.s.r@web.de> wrote:\n> Convert code that divides and rounds up to use DIV_ROUND_UP to make the\n> intent clearer and reduce the number of magic constants.\n...\n> diff --git a/sha1_name.c b/sha1_name.c\n> index e7f7b12ceb..8c513dbff6 100644\n> --- a/sha1_name.c\n> +++ b/sha1_name.c\n> @@ -492,7 +492,7 @@ int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)\n>                  * together we need to divide by 2; but we also want to round\n>                  * odd numbers up, hence adding one before dividing.\n>                  */\n> -               len = (len + 1) / 2;\n> +               len = DIV_ROUND_UP(len, 2);\n\nSince the addition is now an implementation detail of DIV_ROUND_UP,\nshould the comment be adjusted, maybe simply by removing \", hence\nadding one before dividing\"?\n\nOr perhaps even better, \"... divide by 2; but since len might be odd,\nwe need to make sure we round up as we divide\". My thinking being,\nwe're not actually rounding odd numbers up (presumably to even\nnumbers), but we're rounding the result of the division up (to the\nsmallest larger integer).\n"},{"id":"324029","messageId":"be5b6900-9e5e-0796-c16a-03c1b72cfa50@web.de","threadId":"46331","inReplyTo":"CAN0heSr0qJv7VqaasLGNFbNDbqYOoqmi3FyLkb=co4E10Y9VOg@mail.gmail.com","subject":"Re: [PATCH] use DIV_ROUND_UP","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-07-09T14:01:39Z","receivedAt":"2017-07-09T14:01:52Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 09.07.2017 um 15:25 schrieb Martin Ågren:\n> On 8 July 2017 at 12:35, René Scharfe <l.s.r@web.de> wrote:\n>> Convert code that divides and rounds up to use DIV_ROUND_UP to make the\n>> intent clearer and reduce the number of magic constants.\n> ...\n>> diff --git a/sha1_name.c b/sha1_name.c\n>> index e7f7b12ceb..8c513dbff6 100644\n>> --- a/sha1_name.c\n>> +++ b/sha1_name.c\n>> @@ -492,7 +492,7 @@ int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)\n>>                   * together we need to divide by 2; but we also want to round\n>>                   * odd numbers up, hence adding one before dividing.\n>>                   */\n>> -               len = (len + 1) / 2;\n>> +               len = DIV_ROUND_UP(len, 2);\n> \n> Since the addition is now an implementation detail of DIV_ROUND_UP,\n> should the comment be adjusted, maybe simply by removing \", hence\n> adding one before dividing\"?\n> \n> Or perhaps even better, \"... divide by 2; but since len might be odd,\n> we need to make sure we round up as we divide\". My thinking being,\n> we're not actually rounding odd numbers up (presumably to even\n> numbers), but we're rounding the result of the division up (to the\n> smallest larger integer).\n\nGood point; perhaps just squash this in?\n\n---\n sha1_name.c | 3 +--\n 1 file changed, 1 insertion(+), 2 deletions(-)\n\ndiff --git a/sha1_name.c b/sha1_name.c\nindex 8c513dbff6..74fcb6d788 100644\n--- a/sha1_name.c\n+++ b/sha1_name.c\n@@ -489,8 +489,7 @@ int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)\n \t\t * We now know we have on the order of 2^len objects, which\n \t\t * expects a collision at 2^(len/2). But we also care about hex\n \t\t * chars, not bits, and there are 4 bits per hex. So all\n-\t\t * together we need to divide by 2; but we also want to round\n-\t\t * odd numbers up, hence adding one before dividing.\n+\t\t * together we need to divide by 2 and round up.\n \t\t */\n \t\tlen = DIV_ROUND_UP(len, 2);\n \t\t/*\n-- \n2.13.2\n"},{"id":"324030","messageId":"CAN0heSpaLqfD_ZU=6K=bQs3E4iBj0BjQEVruivc7LXCWoXi2tg@mail.gmail.com","threadId":"46331","inReplyTo":"be5b6900-9e5e-0796-c16a-03c1b72cfa50@web.de","subject":"Re: [PATCH] use DIV_ROUND_UP","fromName":"Martin Ågren","fromEmail":"martin.agren@gmail.com","sentAt":"2017-07-09T15:14:52Z","receivedAt":"2017-07-09T15:14:58Z","isPatch":true,"sender":{"key":"martin.agren@gmail.com","avatar":null},"body":"On 9 July 2017 at 16:01, René Scharfe <l.s.r@web.de> wrote:\n> Am 09.07.2017 um 15:25 schrieb Martin Ågren:\n>> On 8 July 2017 at 12:35, René Scharfe <l.s.r@web.de> wrote:\n>>> Convert code that divides and rounds up to use DIV_ROUND_UP to make the\n>>> intent clearer and reduce the number of magic constants.\n>> ...\n>>> diff --git a/sha1_name.c b/sha1_name.c\n>>> index e7f7b12ceb..8c513dbff6 100644\n>>> --- a/sha1_name.c\n>>> +++ b/sha1_name.c\n>>> @@ -492,7 +492,7 @@ int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)\n>>>                   * together we need to divide by 2; but we also want to round\n>>>                   * odd numbers up, hence adding one before dividing.\n>>>                   */\n>>> -               len = (len + 1) / 2;\n>>> +               len = DIV_ROUND_UP(len, 2);\n>>\n>> Since the addition is now an implementation detail of DIV_ROUND_UP,\n>> should the comment be adjusted, maybe simply by removing \", hence\n>> adding one before dividing\"?\n>>\n>> Or perhaps even better, \"... divide by 2; but since len might be odd,\n>> we need to make sure we round up as we divide\". My thinking being,\n>> we're not actually rounding odd numbers up (presumably to even\n>> numbers), but we're rounding the result of the division up (to the\n>> smallest larger integer).\n>\n> Good point; perhaps just squash this in?\n>\n> ---\n>  sha1_name.c | 3 +--\n>  1 file changed, 1 insertion(+), 2 deletions(-)\n>\n> diff --git a/sha1_name.c b/sha1_name.c\n> index 8c513dbff6..74fcb6d788 100644\n> --- a/sha1_name.c\n> +++ b/sha1_name.c\n> @@ -489,8 +489,7 @@ int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)\n>                  * We now know we have on the order of 2^len objects, which\n>                  * expects a collision at 2^(len/2). But we also care about hex\n>                  * chars, not bits, and there are 4 bits per hex. So all\n> -                * together we need to divide by 2; but we also want to round\n> -                * odd numbers up, hence adding one before dividing.\n> +                * together we need to divide by 2 and round up.\n>                  */\n>                 len = DIV_ROUND_UP(len, 2);\n>                 /*\n\nMuch better than my suggestions.\n"},{"id":"324051","messageId":"20170710072701.cqzztww6mrqr7sli@sigill.intra.peff.net","threadId":"46331","inReplyTo":"4d2c274a-f6cb-6ea5-304f-51a3152cc436@web.de","subject":"Re: [PATCH] use DIV_ROUND_UP","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-07-10T07:27:01Z","receivedAt":"2017-07-10T07:27:22Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Jul 08, 2017 at 12:35:35PM +0200, René Scharfe wrote:\n\n> Convert code that divides and rounds up to use DIV_ROUND_UP to make the\n> intent clearer and reduce the number of magic constants.\n\nSounds like a good idea.\n\n> -\tauto_threshold = (gc_auto_threshold + 255) / 256;\n> +\tauto_threshold = DIV_ROUND_UP(gc_auto_threshold, 256);\n\nDIV_ROUND_UP(n,d) is defined as (n+d-1)/d. So this is clearly a\nmechanical conversion and thus correct. And most cases are like this,\nbut...\n\n> diff --git a/ewah/ewah_bitmap.c b/ewah/ewah_bitmap.c\n> index 2dc9c82ecf..06c479f70a 100644\n> --- a/ewah/ewah_bitmap.c\n> +++ b/ewah/ewah_bitmap.c\n> @@ -210,8 +210,8 @@ size_t ewah_add(struct ewah_bitmap *self, eword_t word)\n>  void ewah_set(struct ewah_bitmap *self, size_t i)\n>  {\n>  \tconst size_t dist =\n> -\t\t(i + BITS_IN_EWORD) / BITS_IN_EWORD -\n> -\t\t(self->bit_size + BITS_IN_EWORD - 1) / BITS_IN_EWORD;\n> +\t\tDIV_ROUND_UP(i + 1, BITS_IN_EWORD) -\n> +\t\tDIV_ROUND_UP(self->bit_size, BITS_IN_EWORD);\n\n...this first one is a bit trickier. Our \"n\" in the first one is now\n\"i+1\".  But that's because the original was implicitly canceling the\n\"-1\" and \"+1\" terms.\n\nSo I think it's a true mechanical conversion, but I have to admit the\noriginal is confusing. Without digging I suspect it's correct, though,\njust because a simple bug here would mean that our ewah bitmaps totally\ndon't work. So it's probably not worth spending time on.\n\n> [...]\n\nAnd all the others are straight-forward and obviously correct. So this\npatch looks good to me.\n\n-Peff\n"},{"id":"324086","messageId":"3f643932-0fe1-26b0-d2bf-a2124a74deca@web.de","threadId":"46331","inReplyTo":"20170710072701.cqzztww6mrqr7sli@sigill.intra.peff.net","subject":"Re: [PATCH] use DIV_ROUND_UP","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-07-10T17:08:38Z","receivedAt":"2017-07-10T17:09:08Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 10.07.2017 um 09:27 schrieb Jeff King:\n> On Sat, Jul 08, 2017 at 12:35:35PM +0200, René Scharfe wrote:\n>> diff --git a/ewah/ewah_bitmap.c b/ewah/ewah_bitmap.c\n>> index 2dc9c82ecf..06c479f70a 100644\n>> --- a/ewah/ewah_bitmap.c\n>> +++ b/ewah/ewah_bitmap.c\n>> @@ -210,8 +210,8 @@ size_t ewah_add(struct ewah_bitmap *self, eword_t word)\n>>   void ewah_set(struct ewah_bitmap *self, size_t i)\n>>   {\n>>   \tconst size_t dist =\n>> -\t\t(i + BITS_IN_EWORD) / BITS_IN_EWORD -\n>> -\t\t(self->bit_size + BITS_IN_EWORD - 1) / BITS_IN_EWORD;\n>> +\t\tDIV_ROUND_UP(i + 1, BITS_IN_EWORD) -\n>> +\t\tDIV_ROUND_UP(self->bit_size, BITS_IN_EWORD);\n> \n> ...this first one is a bit trickier. Our \"n\" in the first one is now\n> \"i+1\".  But that's because the original was implicitly canceling the\n> \"-1\" and \"+1\" terms.\n> \n> So I think it's a true mechanical conversion, but I have to admit the\n> original is confusing. Without digging I suspect it's correct, though,\n> just because a simple bug here would mean that our ewah bitmaps totally\n> don't work. So it's probably not worth spending time on.\n\nA few lines below there is \"self->bit_size = i + 1\", so the code\ncalculates how many words the old and the new value are apart (or by how\nmany words the bitmap needs to be extended), which becomes easier to see\nwith the patch.\n\nRené\n"},{"id":"324162","messageId":"20170711074143.fxedaod3bmsxck2o@sigill.intra.peff.net","threadId":"46331","inReplyTo":"3f643932-0fe1-26b0-d2bf-a2124a74deca@web.de","subject":"Re: [PATCH] use DIV_ROUND_UP","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-07-11T07:41:43Z","receivedAt":"2017-07-11T07:42:01Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jul 10, 2017 at 07:08:38PM +0200, René Scharfe wrote:\n\n> > So I think it's a true mechanical conversion, but I have to admit the\n> > original is confusing. Without digging I suspect it's correct, though,\n> > just because a simple bug here would mean that our ewah bitmaps totally\n> > don't work. So it's probably not worth spending time on.\n> \n> A few lines below there is \"self->bit_size = i + 1\", so the code\n> calculates how many words the old and the new value are apart (or by how\n> many words the bitmap needs to be extended), which becomes easier to see\n> with the patch.\n\nYeah, I'd agree the consistent use of \"i + 1\" makes the end result after\nyour patch easier to read.\n\n-Peff\n"}]}