Re: [PATCH] cleanup: fix possible overflow errors in binary search

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



On Fri, Oct 06, 2017 at 09:52:31AM -0400, Derrick Stolee wrote:

> A common mistake when writing binary search is to allow possible
> integer overflow by using the simple average:
> 
> 	mid = (min + max) / 2;
> 
> Instead, use the overflow-safe version:
> 
> 	mid = min + (max - min) / 2;

Great, thank you for picking this up!

> The included changes were found using the following two greps:
> 
> 	grep "/ 2;" *.c
> 	grep "/ 2;" */*.c
> 	grep "/2;" */*.c

You can use[1]:

  git grep '/ 2;' '*.c'

to have Git expand the wildcard. That catches a few extra cases in
compat/regex/*.c.  Even though it's imported code, it might be
nice to cover those, too (since it's a possible bug, and also as a good
example).

[1] I'd actually write:

      git grep '/ *2;' '*.c'

    to do it all in one grep. :)

> ---
>  builtin/index-pack.c     | 4 ++--
>  builtin/pack-objects.c   | 2 +-
>  builtin/unpack-objects.c | 2 +-
>  cache-tree.c             | 2 +-
>  packfile.c               | 2 +-
>  sha1-lookup.c            | 2 +-
>  sha1_name.c              | 2 +-
>  string-list.c            | 2 +-
>  utf8.c                   | 2 +-
>  xdiff/xpatience.c        | 2 +-
>  10 files changed, 11 insertions(+), 11 deletions(-)

These all look good to me (really the only way the conversion could be
bad is if "min" was higher than "max", and each case is just inside a
loop condition which makes sure that is not the case).

-Peff



[Index of Archives]     [Linux Kernel Development]     [Gcc Help]     [IETF Annouce]     [DCCP]     [Netdev]     [Networking]     [Security]     [V4L]     [Bugtraq]     [Yosemite]     [MIPS Linux]     [ARM Linux]     [Linux Security]     [Linux RAID]     [Linux SCSI]     [Fedora Users]

  Powered by Linux