avoid possible overflow?

avoid possible overflow?

[Carles Pina i Estany]

[-- Attachment #1: Type: text/plain, Size: 640 bytes --]


Hello,

The common pattern when doing a search by bisection is something like:
+      current = min + (max - min) / 2;

Instead of the first natural idea:
-      current = (max + min) / 2;

To avoid overflows.

In gettext/gettext.c it's used in the "incorrect" way. It's not a big
problem since would happen only with .mo files with lot of strings, like
number that int represents in that architecture divided by 2 (aprox
aprox.).

See the attached file for a patch if we want to patch.

Else I would at least add a comment that we simplified because we
consider that will not happen.

Thanks,

-- 
Carles Pina i Estany
	http://pinux.info

[-- Attachment #2: gettext_overflow.patch --]
[-- Type: text/x-diff, Size: 786 bytes --]

=== modified file 'ChangeLog'
--- ChangeLog	2010-02-13 15:48:22 +0000
+++ ChangeLog	2010-02-14 00:02:48 +0000
@@ -1,3 +1,8 @@
+2010-02-13  Carles Pina i Estany  <carles@pina.cat>
+
+	* gettext/gettext.c (grub_gettext_translate): Avoids possible
+	overflow.
+
 2010-02-13  Vladimir Serbinenko  <phcoder@gmail.com>
 
 	Merge grub_ieee1275_map_physical into grub_map and rename to

=== modified file 'gettext/gettext.c'
--- gettext/gettext.c	2010-01-20 08:12:47 +0000
+++ gettext/gettext.c	2010-02-13 23:56:58 +0000
@@ -192,7 +192,7 @@ grub_gettext_translate (const char *orig
 	  grub_free (current_string);
 	  found = 1;
 	}
-      current = (max + min) / 2;
+      current = min + (max - min) / 2;
     }
 
   ret = found ? grub_gettext_gettranslation_from_position (current) : orig;

Re: avoid possible overflow?

[Vladimir 'φ-coder/phcoder' Serbinenko]

[-- Attachment #1: Type: text/plain, Size: 1386 bytes --]

Carles Pina i Estany wrote:
> Hello,
>
> The common pattern when doing a search by bisection is something like:
> +      current = min + (max - min) / 2;
>
> Instead of the first natural idea:
> -      current = (max + min) / 2;
>
> To avoid overflows.
>
> In gettext/gettext.c it's used in the "incorrect" way. It's not a big
> problem since would happen only with .mo files with lot of strings, like
> number that int represents in that architecture divided by 2 (aprox
> aprox.).
>
> See the attached file for a patch if we want to patch.
>   
You forgot to make the same change before the loop. But actually it
doesn't matter because overflow in this statement:
  internal_position = offsettranslation + position * 8;
is reached well before the overflow in bisecting. Anyway this
mattersonly for >4GiB files and unless we put videos in .po I don't see
how this limit would be reached. So I prefer readability and would
reject this patch.
> Else I would at least add a comment that we simplified because we
> consider that will not happen.
>
> Thanks,
>
>   
> ------------------------------------------------------------------------
>
> _______________________________________________
> Grub-devel mailing list
> Grub-devel@gnu.org
> http://lists.gnu.org/mailman/listinfo/grub-devel


-- 
Regards
Vladimir 'φ-coder/phcoder' Serbinenko



[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 293 bytes --]

Re: avoid possible overflow?

[richardvoigt]

2010/2/16 Vladimir 'φ-coder/phcoder' Serbinenko <phcoder@gmail.com>:
> Carles Pina i Estany wrote:
>> Hello,
>>
>> The common pattern when doing a search by bisection is something like:
>> +      current = min + (max - min) / 2;
>>
>> Instead of the first natural idea:
>> -      current = (max + min) / 2;
>>
>> To avoid overflows.
>>
>> In gettext/gettext.c it's used in the "incorrect" way. It's not a big
>> problem since would happen only with .mo files with lot of strings, like
>> number that int represents in that architecture divided by 2 (aprox
>> aprox.).
>>
>> See the attached file for a patch if we want to patch.
>>
> You forgot to make the same change before the loop. But actually it
> doesn't matter because overflow in this statement:
>  internal_position = offsettranslation + position * 8;
> is reached well before the overflow in bisecting. Anyway this
> mattersonly for >4GiB files and unless we put videos in .po I don't see
> how this limit would be reached. So I prefer readability and would
> reject this patch.

There's a very readable way to express the "better" code that's immune
to the overflow:

int const range = max - min; /* or unsigned int, if min and max are
declared that way */
current = min + range / 2;


>> Else I would at least add a comment that we simplified because we
>> consider that will not happen.
>>
>> Thanks,
>>
>>
>> ------------------------------------------------------------------------
>>
>> _______________________________________________
>> Grub-devel mailing list
>> Grub-devel@gnu.org
>> http://lists.gnu.org/mailman/listinfo/grub-devel
>
>
> --
> Regards
> Vladimir 'φ-coder/phcoder' Serbinenko
>
>
>
> _______________________________________________
> Grub-devel mailing list
> Grub-devel@gnu.org
> http://lists.gnu.org/mailman/listinfo/grub-devel
>
>