Re: [sqlite] Q about integer overflow in sqlite3MulInt64().
On 9/20/16, Scott Hesswrote: > 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().
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 Sulzbachwrote: > 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().
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().
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().
A new ticket has been created at https://www.sqlite.org/src/info/1ec41379c9c1e400 On 9/20/16, Scott Hesswrote: > 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().
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