Re: [sqlite] Q about integer overflow in sqlite3MulInt64().

2016-09-20 Thread Richard Hipp 
On 9/20/16, Scott Hess  wrote:
> I also see that some systems
> include __builtin_mul_overflow() intrinsics, which can use the CPU's
> overflow flag, if available, which seems plausible.
>

I too have seen this, and look forward to the wide-spread availability
of these routines.  The functions are not available on my 4.8.4 GCC,
nor on MSVC 2012 (afaik).

Other intrinsic functions are used in SQLite.  For example:

 https://www.sqlite.org/src/artifact/3e2da61018?ln=1135-1157

Intrinsic functions can make a big difference in performance.
-- 
D. Richard Hipp
d...@sqlite.org
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Q about integer overflow in sqlite3MulInt64().

2016-09-20 Thread Scott Hess 
Yes - once the undefined behavior has happened, the compiler can
dispense with everything else, so if it can prove that your
after-the-fact checks can only happen in case of signed overflow, it
can simply omit them.  Great fun.

Dr Hipp landed https://www.sqlite.org/src/info/db3ebd7c52cfc5fc ,
which is basically what you suggested.  I also see that some systems
include __builtin_mul_overflow() intrinsics, which can use the CPU's
overflow flag, if available, which seems plausible.

-scott

On Tue, Sep 20, 2016 at 4:51 PM, Bernardo Sulzbach
 wrote:
> In time, ignore my previous reply to this thread as SQLite portability
> requirements make it invalid (at least I think they would). According to the
> C language standard, signed overflow is undefined behavior and, therefore,
> should not be relied upon.
>
> There is also a simpler way to check it using a division of the maximum
> possible value by the multiplier (which will never overflow).
>
>
> --
> Bernardo Sulzbach
> http://www.mafagafogigante.org/
> mafagafogiga...@mafagafogigante.org
> ___
> sqlite-users mailing list
> sqlite-users@mailinglists.sqlite.org
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Q about integer overflow in sqlite3MulInt64().

2016-09-20 Thread Bernardo Sulzbach 
In time, ignore my previous reply to this thread as SQLite portability 
requirements make it invalid (at least I think they would). According to 
the C language standard, signed overflow is undefined behavior and, 
therefore, should not be relied upon.


There is also a simpler way to check it using a division of the maximum 
possible value by the multiplier (which will never overflow).


--
Bernardo Sulzbach
http://www.mafagafogigante.org/
mafagafogiga...@mafagafogigante.org
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Q about integer overflow in sqlite3MulInt64().

2016-09-20 Thread Bernardo Sulzbach 

On 09/20/2016 04:51 PM, Scott Hess wrote:


No patch suggested, though I wouldn't be surprised if my brain makes a
suggestion after things simmer for an hour or so.  If either value
needs less than 31 bits, it can't happen, but there's not a simple bit
pattern to check, AFAICT.



Unless performance is of uttermost importance, just try and see if it 
fails or not.


prod = x * y;
if (y != 0) {
  if (prod / y != x) {
/* Overflow. */
  }
}

This also works for multiplications such as 1152921504606846976 * 3, 
which do not overflow, but have much bigger multiplicands.


--
Bernardo Sulzbach
http://www.mafagafogigante.org/
mafagafogiga...@mafagafogigante.org
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Q about integer overflow in sqlite3MulInt64().

2016-09-20 Thread Richard Hipp 
A new ticket has been created at

https://www.sqlite.org/src/info/1ec41379c9c1e400

On 9/20/16, Scott Hess  wrote:
> sqlite3MulInt64() in util.c appears to try to detect integer overflow
> by dividing the inputs by 2^32.  If both inputs are 0 when divided by
> 2^32, it does the 64-bit multiplication and moves on.
>
> In the case of something like |SELECT 3452005775*3452005775|, both
> inputs are greater than 2^31 but less than 2^32, but the result is
> greater than 2^63, so it ends up as a large negative number (ie,
> overflow, which is undefined for signed integers in C).  The smallest
> number this overflow happens to is sqrt(2^63)+1, which is 3037000500.
> Obviously there's a range of values where this can happen.
>
> No patch suggested, though I wouldn't be surprised if my brain makes a
> suggestion after things simmer for an hour or so.  If either value
> needs less than 31 bits, it can't happen, but there's not a simple bit
> pattern to check, AFAICT.
>
> -scott
> ___
> sqlite-users mailing list
> sqlite-users@mailinglists.sqlite.org
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>


-- 
D. Richard Hipp
d...@sqlite.org
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

[sqlite] Q about integer overflow in sqlite3MulInt64().

2016-09-20 Thread Scott Hess 
sqlite3MulInt64() in util.c appears to try to detect integer overflow
by dividing the inputs by 2^32.  If both inputs are 0 when divided by
2^32, it does the 64-bit multiplication and moves on.

In the case of something like |SELECT 3452005775*3452005775|, both
inputs are greater than 2^31 but less than 2^32, but the result is
greater than 2^63, so it ends up as a large negative number (ie,
overflow, which is undefined for signed integers in C).  The smallest
number this overflow happens to is sqrt(2^63)+1, which is 3037000500.
Obviously there's a range of values where this can happen.

No patch suggested, though I wouldn't be surprised if my brain makes a
suggestion after things simmer for an hour or so.  If either value
needs less than 31 bits, it can't happen, but there's not a simple bit
pattern to check, AFAICT.

-scott
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users