From: Junio C Hamano <gitster@pobox.com>
Date: Sun, 7 Apr 2013 21:32:54 +0000 (-0700)
Subject: Merge branch 'jk/bisect-prn-unsigned'
X-Git-Tag: v1.8.3-rc0~95
X-Git-Url: https://git.lorimer.id.au/gitweb.git/diff_plain/252905dd4a237f884f4913a71b345d29abc899e3?ds=inline;hp=-c

Merge branch 'jk/bisect-prn-unsigned'

* jk/bisect-prn-unsigned:
bisect: avoid signed integer overflow
---

252905dd4a237f884f4913a71b345d29abc899e3
diff --combined bisect.c
index bd1b7b5dac,7f95273e69..374d9e24bd
--- a/bisect.c
+++ b/bisect.c
@@@ -525,9 -525,9 +525,9 @@@ struct commit_list *filter_skipped(stru
   * is increased by one between each call, but that should not matter
   * for this application.
   */
- static int get_prn(int count) {
+ static unsigned get_prn(unsigned count) {
  	count = count * 1103515245 + 12345;
- 	return ((unsigned)(count/65536) % PRN_MODULO);
+ 	return (count/65536) % PRN_MODULO;
  }
  
  /*
@@@ -956,41 -956,3 +956,41 @@@ int bisect_next_all(const char *prefix
  	return bisect_checkout(bisect_rev_hex, no_checkout);
  }
  
 +static inline int log2i(int n)
 +{
 +	int log2 = 0;
 +
 +	for (; n > 1; n >>= 1)
 +		log2++;
 +
 +	return log2;
 +}
 +
 +static inline int exp2i(int n)
 +{
 +	return 1 << n;
 +}
 +
 +/*
 + * Estimate the number of bisect steps left (after the current step)
 + *
 + * For any x between 0 included and 2^n excluded, the probability for
 + * n - 1 steps left looks like:
 + *
 + * P(2^n + x) == (2^n - x) / (2^n + x)
 + *
 + * and P(2^n + x) < 0.5 means 2^n < 3x
 + */
 +int estimate_bisect_steps(int all)
 +{
 +	int n, x, e;
 +
 +	if (all < 3)
 +		return 0;
 +
 +	n = log2i(all);
 +	e = exp2i(n);
 +	x = all - e;
 +
 +	return (e < 3 * x) ? n : n - 1;
 +}