[PATCH] use DIV_ROUND_UP

[PATCH] use DIV_ROUND_UP

[René Scharfe]

Convert code that divides and rounds up to use DIV_ROUND_UP to make the
intent clearer and reduce the number of magic constants.

Signed-off-by: Rene Scharfe <l.s.r@web.de>
---
 builtin/gc.c           | 2 +-
 builtin/grep.c         | 2 +-
 builtin/log.c          | 2 +-
 builtin/receive-pack.c | 2 +-
 diff.c                 | 2 +-
 ewah/ewah_bitmap.c     | 4 ++--
 imap-send.c            | 2 +-
 sha1_name.c            | 2 +-
 shallow.c              | 8 ++++----
 9 files changed, 13 insertions(+), 13 deletions(-)

diff --git a/builtin/gc.c b/builtin/gc.c
index bd91f136fe..2ba50a2873 100644
--- a/builtin/gc.c
+++ b/builtin/gc.c
@@ -149,7 +149,7 @@ static int too_many_loose_objects(void)
 	if (!dir)
 		return 0;
 
-	auto_threshold = (gc_auto_threshold + 255) / 256;
+	auto_threshold = DIV_ROUND_UP(gc_auto_threshold, 256);
 	while ((ent = readdir(dir)) != NULL) {
 		if (strspn(ent->d_name, "0123456789abcdef") != 38 ||
 		    ent->d_name[38] != '\0')
diff --git a/builtin/grep.c b/builtin/grep.c
index fa351c49f4..0d6e669732 100644
--- a/builtin/grep.c
+++ b/builtin/grep.c
@@ -543,7 +543,7 @@ static void compile_submodule_options(const struct grep_opt *opt,
 	 * submodule process has its own thread pool.
 	 */
 	argv_array_pushf(&submodule_options, "--threads=%d",
-			 (num_threads + 1) / 2);
+			 DIV_ROUND_UP(num_threads, 2));
 
 	/* Add Pathspecs */
 	argv_array_push(&submodule_options, "--");
diff --git a/builtin/log.c b/builtin/log.c
index 8ca1de9894..c6362cf92e 100644
--- a/builtin/log.c
+++ b/builtin/log.c
@@ -1308,7 +1308,7 @@ static struct commit *get_base_commit(const char *base_commit,
 
 		if (rev_nr % 2)
 			rev[i] = rev[2 * i];
-		rev_nr = (rev_nr + 1) / 2;
+		rev_nr = DIV_ROUND_UP(rev_nr, 2);
 	}
 
 	if (!in_merge_bases(base, rev[0]))
diff --git a/builtin/receive-pack.c b/builtin/receive-pack.c
index 71c0c768db..cabdc55e09 100644
--- a/builtin/receive-pack.c
+++ b/builtin/receive-pack.c
@@ -1806,7 +1806,7 @@ static const char *unpack_with_sideband(struct shallow_info *si)
 static void prepare_shallow_update(struct command *commands,
 				   struct shallow_info *si)
 {
-	int i, j, k, bitmap_size = (si->ref->nr + 31) / 32;
+	int i, j, k, bitmap_size = DIV_ROUND_UP(si->ref->nr, 32);
 
 	ALLOC_ARRAY(si->used_shallow, si->shallow->nr);
 	assign_shallow_commits_to_refs(si, si->used_shallow, NULL);
diff --git a/diff.c b/diff.c
index 00b4c86698..85e714f6c6 100644
--- a/diff.c
+++ b/diff.c
@@ -2095,7 +2095,7 @@ static void show_dirstat_by_line(struct diffstat_t *data, struct diff_options *o
 			 * bytes per "line".
 			 * This is stupid and ugly, but very cheap...
 			 */
-			damage = (damage + 63) / 64;
+			damage = DIV_ROUND_UP(damage, 64);
 		ALLOC_GROW(dir.files, dir.nr + 1, dir.alloc);
 		dir.files[dir.nr].name = file->name;
 		dir.files[dir.nr].changed = damage;
diff --git a/ewah/ewah_bitmap.c b/ewah/ewah_bitmap.c
index 2dc9c82ecf..06c479f70a 100644
--- a/ewah/ewah_bitmap.c
+++ b/ewah/ewah_bitmap.c
@@ -210,8 +210,8 @@ size_t ewah_add(struct ewah_bitmap *self, eword_t word)
 void ewah_set(struct ewah_bitmap *self, size_t i)
 {
 	const size_t dist =
-		(i + BITS_IN_EWORD) / BITS_IN_EWORD -
-		(self->bit_size + BITS_IN_EWORD - 1) / BITS_IN_EWORD;
+		DIV_ROUND_UP(i + 1, BITS_IN_EWORD) -
+		DIV_ROUND_UP(self->bit_size, BITS_IN_EWORD);
 
 	assert(i >= self->bit_size);
 
diff --git a/imap-send.c b/imap-send.c
index 351e84aea1..b2d0b849bb 100644
--- a/imap-send.c
+++ b/imap-send.c
@@ -861,7 +861,7 @@ static char hexchar(unsigned int b)
 	return b < 10 ? '0' + b : 'a' + (b - 10);
 }
 
-#define ENCODED_SIZE(n) (4*((n+2)/3))
+#define ENCODED_SIZE(n) (4 * DIV_ROUND_UP((n), 3))
 static char *cram(const char *challenge_64, const char *user, const char *pass)
 {
 	int i, resp_len, encoded_len, decoded_len;
diff --git a/sha1_name.c b/sha1_name.c
index e7f7b12ceb..8c513dbff6 100644
--- a/sha1_name.c
+++ b/sha1_name.c
@@ -492,7 +492,7 @@ int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)
 		 * together we need to divide by 2; but we also want to round
 		 * odd numbers up, hence adding one before dividing.
 		 */
-		len = (len + 1) / 2;
+		len = DIV_ROUND_UP(len, 2);
 		/*
 		 * For very small repos, we stick with our regular fallback.
 		 */
diff --git a/shallow.c b/shallow.c
index ef7ca78993..54359d5490 100644
--- a/shallow.c
+++ b/shallow.c
@@ -443,7 +443,7 @@ struct paint_info {
 
 static uint32_t *paint_alloc(struct paint_info *info)
 {
-	unsigned nr = (info->nr_bits + 31) / 32;
+	unsigned nr = DIV_ROUND_UP(info->nr_bits, 32);
 	unsigned size = nr * sizeof(uint32_t);
 	void *p;
 	if (!info->pool_count || size > info->end - info->free) {
@@ -471,7 +471,7 @@ static void paint_down(struct paint_info *info, const struct object_id *oid,
 {
 	unsigned int i, nr;
 	struct commit_list *head = NULL;
-	int bitmap_nr = (info->nr_bits + 31) / 32;
+	int bitmap_nr = DIV_ROUND_UP(info->nr_bits, 32);
 	size_t bitmap_size = st_mult(sizeof(uint32_t), bitmap_nr);
 	struct commit *c = lookup_commit_reference_gently(oid, 1);
 	uint32_t *tmp; /* to be freed before return */
@@ -611,7 +611,7 @@ void assign_shallow_commits_to_refs(struct shallow_info *info,
 		paint_down(&pi, ref->oid + i, i);
 
 	if (used) {
-		int bitmap_size = ((pi.nr_bits + 31) / 32) * sizeof(uint32_t);
+		int bitmap_size = DIV_ROUND_UP(pi.nr_bits, 32) * sizeof(uint32_t);
 		memset(used, 0, sizeof(*used) * info->shallow->nr);
 		for (i = 0; i < nr_shallow; i++) {
 			const struct commit *c = lookup_commit(&oid[shallow[i]]);
@@ -672,7 +672,7 @@ static void post_assign_shallow(struct shallow_info *info,
 	struct commit *c;
 	uint32_t **bitmap;
 	int dst, i, j;
-	int bitmap_nr = (info->ref->nr + 31) / 32;
+	int bitmap_nr = DIV_ROUND_UP(info->ref->nr, 32);
 	struct commit_array ca;
 
 	trace_printf_key(&trace_shallow, "shallow: post_assign_shallow\n");
-- 
2.13.2

Re: [PATCH] use DIV_ROUND_UP

[Martin Ågren]

On 8 July 2017 at 12:35, René Scharfe <l.s.r@web.de> wrote:
> Convert code that divides and rounds up to use DIV_ROUND_UP to make the
> intent clearer and reduce the number of magic constants.
...
> diff --git a/sha1_name.c b/sha1_name.c
> index e7f7b12ceb..8c513dbff6 100644
> --- a/sha1_name.c
> +++ b/sha1_name.c
> @@ -492,7 +492,7 @@ int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)
>                  * together we need to divide by 2; but we also want to round
>                  * odd numbers up, hence adding one before dividing.
>                  */
> -               len = (len + 1) / 2;
> +               len = DIV_ROUND_UP(len, 2);

Since the addition is now an implementation detail of DIV_ROUND_UP,
should the comment be adjusted, maybe simply by removing ", hence
adding one before dividing"?

Or perhaps even better, "... divide by 2; but since len might be odd,
we need to make sure we round up as we divide". My thinking being,
we're not actually rounding odd numbers up (presumably to even
numbers), but we're rounding the result of the division up (to the
smallest larger integer).

Re: [PATCH] use DIV_ROUND_UP

[René Scharfe]

Am 09.07.2017 um 15:25 schrieb Martin Ågren:
> On 8 July 2017 at 12:35, René Scharfe <l.s.r@web.de> wrote:
>> Convert code that divides and rounds up to use DIV_ROUND_UP to make the
>> intent clearer and reduce the number of magic constants.
> ...
>> diff --git a/sha1_name.c b/sha1_name.c
>> index e7f7b12ceb..8c513dbff6 100644
>> --- a/sha1_name.c
>> +++ b/sha1_name.c
>> @@ -492,7 +492,7 @@ int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)
>>                   * together we need to divide by 2; but we also want to round
>>                   * odd numbers up, hence adding one before dividing.
>>                   */
>> -               len = (len + 1) / 2;
>> +               len = DIV_ROUND_UP(len, 2);
> 
> Since the addition is now an implementation detail of DIV_ROUND_UP,
> should the comment be adjusted, maybe simply by removing ", hence
> adding one before dividing"?
> 
> Or perhaps even better, "... divide by 2; but since len might be odd,
> we need to make sure we round up as we divide". My thinking being,
> we're not actually rounding odd numbers up (presumably to even
> numbers), but we're rounding the result of the division up (to the
> smallest larger integer).

Good point; perhaps just squash this in?

---
 sha1_name.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

diff --git a/sha1_name.c b/sha1_name.c
index 8c513dbff6..74fcb6d788 100644
--- a/sha1_name.c
+++ b/sha1_name.c
@@ -489,8 +489,7 @@ int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)
 		 * We now know we have on the order of 2^len objects, which
 		 * expects a collision at 2^(len/2). But we also care about hex
 		 * chars, not bits, and there are 4 bits per hex. So all
-		 * together we need to divide by 2; but we also want to round
-		 * odd numbers up, hence adding one before dividing.
+		 * together we need to divide by 2 and round up.
 		 */
 		len = DIV_ROUND_UP(len, 2);
 		/*
-- 
2.13.2

Re: [PATCH] use DIV_ROUND_UP

[Martin Ågren]

On 9 July 2017 at 16:01, René Scharfe <l.s.r@web.de> wrote:
> Am 09.07.2017 um 15:25 schrieb Martin Ågren:
>> On 8 July 2017 at 12:35, René Scharfe <l.s.r@web.de> wrote:
>>> Convert code that divides and rounds up to use DIV_ROUND_UP to make the
>>> intent clearer and reduce the number of magic constants.
>> ...
>>> diff --git a/sha1_name.c b/sha1_name.c
>>> index e7f7b12ceb..8c513dbff6 100644
>>> --- a/sha1_name.c
>>> +++ b/sha1_name.c
>>> @@ -492,7 +492,7 @@ int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)
>>>                   * together we need to divide by 2; but we also want to round
>>>                   * odd numbers up, hence adding one before dividing.
>>>                   */
>>> -               len = (len + 1) / 2;
>>> +               len = DIV_ROUND_UP(len, 2);
>>
>> Since the addition is now an implementation detail of DIV_ROUND_UP,
>> should the comment be adjusted, maybe simply by removing ", hence
>> adding one before dividing"?
>>
>> Or perhaps even better, "... divide by 2; but since len might be odd,
>> we need to make sure we round up as we divide". My thinking being,
>> we're not actually rounding odd numbers up (presumably to even
>> numbers), but we're rounding the result of the division up (to the
>> smallest larger integer).
>
> Good point; perhaps just squash this in?
>
> ---
>  sha1_name.c | 3 +--
>  1 file changed, 1 insertion(+), 2 deletions(-)
>
> diff --git a/sha1_name.c b/sha1_name.c
> index 8c513dbff6..74fcb6d788 100644
> --- a/sha1_name.c
> +++ b/sha1_name.c
> @@ -489,8 +489,7 @@ int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)
>                  * We now know we have on the order of 2^len objects, which
>                  * expects a collision at 2^(len/2). But we also care about hex
>                  * chars, not bits, and there are 4 bits per hex. So all
> -                * together we need to divide by 2; but we also want to round
> -                * odd numbers up, hence adding one before dividing.
> +                * together we need to divide by 2 and round up.
>                  */
>                 len = DIV_ROUND_UP(len, 2);
>                 /*

Much better than my suggestions.

Re: [PATCH] use DIV_ROUND_UP

[Jeff King]

On Sat, Jul 08, 2017 at 12:35:35PM +0200, René Scharfe wrote:

> Convert code that divides and rounds up to use DIV_ROUND_UP to make the
> intent clearer and reduce the number of magic constants.

Sounds like a good idea.

> -	auto_threshold = (gc_auto_threshold + 255) / 256;
> +	auto_threshold = DIV_ROUND_UP(gc_auto_threshold, 256);

DIV_ROUND_UP(n,d) is defined as (n+d-1)/d. So this is clearly a
mechanical conversion and thus correct. And most cases are like this,
but...

> diff --git a/ewah/ewah_bitmap.c b/ewah/ewah_bitmap.c
> index 2dc9c82ecf..06c479f70a 100644
> --- a/ewah/ewah_bitmap.c
> +++ b/ewah/ewah_bitmap.c
> @@ -210,8 +210,8 @@ size_t ewah_add(struct ewah_bitmap *self, eword_t word)
>  void ewah_set(struct ewah_bitmap *self, size_t i)
>  {
>  	const size_t dist =
> -		(i + BITS_IN_EWORD) / BITS_IN_EWORD -
> -		(self->bit_size + BITS_IN_EWORD - 1) / BITS_IN_EWORD;
> +		DIV_ROUND_UP(i + 1, BITS_IN_EWORD) -
> +		DIV_ROUND_UP(self->bit_size, BITS_IN_EWORD);

...this first one is a bit trickier. Our "n" in the first one is now
"i+1".  But that's because the original was implicitly canceling the
"-1" and "+1" terms.

So I think it's a true mechanical conversion, but I have to admit the
original is confusing. Without digging I suspect it's correct, though,
just because a simple bug here would mean that our ewah bitmaps totally
don't work. So it's probably not worth spending time on.

> [...]

And all the others are straight-forward and obviously correct. So this
patch looks good to me.

-Peff

Re: [PATCH] use DIV_ROUND_UP

[René Scharfe]

Am 10.07.2017 um 09:27 schrieb Jeff King:
> On Sat, Jul 08, 2017 at 12:35:35PM +0200, René Scharfe wrote:
>> diff --git a/ewah/ewah_bitmap.c b/ewah/ewah_bitmap.c
>> index 2dc9c82ecf..06c479f70a 100644
>> --- a/ewah/ewah_bitmap.c
>> +++ b/ewah/ewah_bitmap.c
>> @@ -210,8 +210,8 @@ size_t ewah_add(struct ewah_bitmap *self, eword_t word)
>>   void ewah_set(struct ewah_bitmap *self, size_t i)
>>   {
>>   	const size_t dist =
>> -		(i + BITS_IN_EWORD) / BITS_IN_EWORD -
>> -		(self->bit_size + BITS_IN_EWORD - 1) / BITS_IN_EWORD;
>> +		DIV_ROUND_UP(i + 1, BITS_IN_EWORD) -
>> +		DIV_ROUND_UP(self->bit_size, BITS_IN_EWORD);
> 
> ...this first one is a bit trickier. Our "n" in the first one is now
> "i+1".  But that's because the original was implicitly canceling the
> "-1" and "+1" terms.
> 
> So I think it's a true mechanical conversion, but I have to admit the
> original is confusing. Without digging I suspect it's correct, though,
> just because a simple bug here would mean that our ewah bitmaps totally
> don't work. So it's probably not worth spending time on.

A few lines below there is "self->bit_size = i + 1", so the code
calculates how many words the old and the new value are apart (or by how
many words the bitmap needs to be extended), which becomes easier to see
with the patch.

René

Re: [PATCH] use DIV_ROUND_UP

[Jeff King]

On Mon, Jul 10, 2017 at 07:08:38PM +0200, René Scharfe wrote:

> > So I think it's a true mechanical conversion, but I have to admit the
> > original is confusing. Without digging I suspect it's correct, though,
> > just because a simple bug here would mean that our ewah bitmaps totally
> > don't work. So it's probably not worth spending time on.
> 
> A few lines below there is "self->bit_size = i + 1", so the code
> calculates how many words the old and the new value are apart (or by how
> many words the bitmap needs to be extended), which becomes easier to see
> with the patch.

Yeah, I'd agree the consistent use of "i + 1" makes the end result after
your patch easier to read.

-Peff