Re: [sqlite] [BUG] Silent change in intergeral overflow handling in 3.7.6

[Jan Hudec]

Richard Hipp  writes:

> 
> On Wed, May 25, 2011 at 4:40 AM, Jan Hudec  wrote:
> 
> >  I need condition
> >
> >object_id = side_id & ~(1 << 63)
> >
> > but that's not valid syntax.
> >
> 
> Yeah it is.  Try, for example:
> 
> SELECT 1234 & ~(1<<63);
> SELECT (-1234) & ~(1<<63);

Wow, thanks. It's really strange that I didn't notice, because I
was looking for it when I wrote the code last year (using sqlite
3.6.20 back then and the operator is mentioned to exist since
long before version 3).

Best regards,
Jan
--
 Jan Hudec 

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

Re: [sqlite] [BUG] Silent change in intergeral overflow handling in 3.7.6

[Richard Hipp]

On Wed, May 25, 2011 at 4:40 AM, Jan Hudec  wrote:

>  I need condition
>
>object_id = side_id & ~(1 << 63)
>
> but that's not valid syntax.
>

Yeah it is.  Try, for example:

SELECT 1234 & ~(1<<63);
SELECT (-1234) & ~(1<<63);


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

Re: [sqlite] [BUG] Silent change in intergeral overflow handling in 3.7.6

[Doug Currie]

On May 26, 2011, at 2:54 AM, Jan Hudec wrote:
> Gotcha! No, it's not. -1-x is equivalent, but -x-1 is not:
> 
>sqlite> select -1-(1<<63), -(1<<63)-1;
>9223372036854775807|9.22337203685478e+18
> 
> Besides my point was not that it's not possible, but that it would
> be more readable with dedicated operator.

Yes.

The fact that a negative number (-1) minus a large positive number (1 << 63) 
results in a positive number does not seem to be in concert with the goal of 
handling arithmetic overflows sensibly. 

This is especially egregious in the second case where the result of negating a 
large positive number and subtracting one is positive AND REAL (double float). 

Ideally SQLite would guarantee one of (in my order of preference):

1) Integer operations that overflow 64 bits behave as wrapped twos complement, 
i.e., they return the low 64 bits of the infinite precision twos complement 
integer result

2) Integer operations that overflow 64 bits result in floating point values 
that approximate the result with the precision of IEEE double 

3) Integer operations that overflow have no guaranteed result

I think option 2 is what SQLite is supposed to do (per the release notes), but 
is failing in both cases of this example.

e

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

Re: [sqlite] [BUG] Silent change in intergeral overflow handling in 3.7.6

[Jan Hudec]

Igor Tandetnik  writes:

> Jan Hudec  wrote:
> > (it would be nicest if sqlite could get bitwise not one day).
> 
> -x-1  is equivalent, assuming two's complement representation.

Gotcha! No, it's not. -1-x is equivalent, but -x-1 is not:

sqlite> select -1-(1<<63), -(1<<63)-1;
9223372036854775807|9.22337203685478e+18

Besides my point was not that it's not possible, but that it would
be more readable with dedicated operator.

Regards,
Jan Hudec

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

Re: [sqlite] [BUG] Silent change in intergeral overflow handling in 3.7.6

[Jean-Christophe Deschamps]

Richard,

At 13:07 25/05/2011, you wrote:

>It turns out that the "expected" behavior does not happen in modern C
>compilers.  Overflow of signed integers is undefined behavior in C.  So if
>you have a signed integer overflow, it might wrap the result (the 
>"expected"
>result) or it might segfault, or it might reformat your hard drive 
>(probably
>not, but it could and still comply with the spec!)  Recent compilers will
>take advantage of this undefined behavior to take shortcuts with signed
>integer arithmetic, meaning that different things happen on different
>compilers and with different optimization settings.  On the other hand, we
>want SQLite to give the same answer regardless of how it is 
>compiled.  So as
>of version 3.7.6, SQLite is careful to avoid signed integer overflows.  We
>now require that SQLite work even if compiled using the -fwrapv option in
>GCC.

You're certainly right about your point and I'm not going to argue 
about the grounds of the C standard.

Nonetheless, the resulting behavior is surprising:

V:\Bin>sqlite3
SQLite version 3.7.6.3
Enter ".help" for instructions
Enter SQL statements terminated with a ";"
sqlite> .load unifuzz.dll
sqlite> CREATE TABLE if not exists "overflow" (
...>   "Test" INTEGER PRIMARY KEY AUTOINCREMENT,
...>   "Operation" CHAR,
...>   "IntValue" INTEGER,
...>   "Type" CHAR,
...>   "Hexa" CHAR);
sqlite>
sqlite> CREATE TRIGGER if not exists "trInsTest"
...> AFTER INSERT
...> ON "overflow"
...> BEGIN
...>  update overflow set type = typeof(intvalue), hexa = 
hexw(intvalue);
...> END;
sqlite> delete from overflow;
sqlite> insert into overflow (operation, intvalue) values ('initial 
value MAX_INT', 9223372036854775807);
sqlite> insert into overflow (operation, intvalue) values ('- MAX_INT', 
- (select intvalue from overflow where test = 1));
sqlite> insert into overflow (operation, intvalue) values ('MAX_INT + 
1', (select intvalue from overflow where test = 1) + 1);
sqlite> insert into overflow (operation, intvalue) values ('- MAX_INT - 
1', - (select intvalue from overflow where test = 1) - 1);
sqlite> select * from overflow;
1|initial value MAX_INT| 9223372036854775807|integer|7FFF
2|- MAX_INT|-9223372036854775807|integer|8001
3|MAX_INT + 1  |9.22337203685478e+18|real   |8000
4|- MAX_INT - 1|-9223372036854775808|integer|8000

The function hexw(x) is from the loaded extension and simply returns x 
as an hex string, as you can see.  It is just there to make the point 
clearer: test 3 and test 4 produce the same content but distinct values 
from distinct types.  That can make some applications choke.

I decided to avoid any early conversion possibly made by the statement 
parser and instead of typing literal values as 9223372036854775807 + 1, 
I retrieved the value as a subselect.

Since integer overflow is a concern and given that no standard way of 
dealing with it consistently is available over the millions of possible 
targets, wouldn't it be more consistent to have a build-time option 
ERR_ON_INT_OVERFLOW causing SQLite to return an error in case of 
integer overflow?


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

Re: [sqlite] [BUG] Silent change in intergeral overflow handling in 3.7.6

[Igor Tandetnik]

Jan Hudec  wrote:
> (it would be nicest if sqlite could get bitwise not one day).

-x-1  is equivalent, assuming two's complement representation.
-- 
Igor Tandetnik

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

Re: [sqlite] [BUG] Silent change in intergeral overflow handling in 3.7.6

[Jan Hudec]

Richard Hipp  writes:

> 
> On Wed, May 25, 2011 at 4:40 AM, Jan Hudec  wrote:
> 
> > Hello All,
> >
> > Semantics of operations on integers changed between 3.7.5 and 3.7.6. It
> > does
> > not seem to be mentioned in change log (http://www.sqlite.org/news.html),
> >
> 
> 4th bullet here:  http://www.sqlite.org/releaselog/3_7_6.html
> 
> > though it may affect existing applications:
> >
> >  * Up to 3.7.5, integer operations are always carried out in 64-bit
> > integers
> >   and overflow as expected for that type.
> >
> 
> It turns out that the "expected" behavior does not happen in modern C
> compilers.  Overflow of signed integers is undefined behavior in C.

Yes, I know. That's why I always use unsigned on the C side. However since
sqlite does not have unsigned numbers, it would be useful if it was defined
for what it does have.

> So if
> you have a signed integer overflow, it might wrap the result (the "expected"
> result) or it might segfault, or it might reformat your hard drive (probably
> not, but it could and still comply with the spec!)  Recent compilers will
> take advantage of this undefined behavior to take shortcuts with signed
> integer arithmetic, meaning that different things happen on different
> compilers and with different optimization settings.

Yes it will, if there are any.

> > Now when I need to join "sides" and "objects", I need condition
> >
> >object_id = side_id & ~(1 << 63)
> >
> > but that's not valid syntax. There are two alternatives:
> >
> >(1 << 63) - 1  or  -1 - (1 << 63)
> >
> 
> Surprisingly, the first does *not* work in C - at least not all the time.

Well, it will, for the simple reason that the result will be declared unsigned
and (besides not being overflow in that case) unsigned wrap around is defined.

> The answer is undefined.  It gives the "expected" answer often, especially
> when optimizations are disabled.  But if you crank up the optimization on a
> recent version of GCC or Clang, you'll likely get something different from
> what you expect, unfortunately.

In fact, there is no optimization it could do in this particular case.
Also it can't take any shortcuts in the SQLite evaluator code, because it
has to compile each operation separately, so it can't apply any
transformations, whether they assume overflow does not happen or not.

> > I used the first, because it is more readable to me (while the later is
> > exact
> > alternative to the bitwise not, it's not common knowledge, because other
> > languages do have bitwise not). But it stopped working in 3.7.6 (the later
> > still does, so I can convert it, but it's error-prone situation).

It seems there are not many people doing bit operations in sqlite, so I'll
just switch to the less obvious, but more correct variant.

(it would be nicest if sqlite could get bitwise not one day).

Regards,
Jan



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

Re: [sqlite] [BUG] Silent change in intergeral overflow handling in 3.7.6

[Richard Hipp]

On Wed, May 25, 2011 at 4:40 AM, Jan Hudec  wrote:

> Hello All,
>
> Semantics of operations on integers changed between 3.7.5 and 3.7.6. It
> does
> not seem to be mentioned in change log (http://www.sqlite.org/news.html),
>

4th bullet here:  http://www.sqlite.org/releaselog/3_7_6.html



> though it may affect existing applications:
>
>  * Up to 3.7.5, integer operations are always carried out in 64-bit
> integers
>   and overflow as expected for that type.
>

It turns out that the "expected" behavior does not happen in modern C
compilers.  Overflow of signed integers is undefined behavior in C.  So if
you have a signed integer overflow, it might wrap the result (the "expected"
result) or it might segfault, or it might reformat your hard drive (probably
not, but it could and still comply with the spec!)  Recent compilers will
take advantage of this undefined behavior to take shortcuts with signed
integer arithmetic, meaning that different things happen on different
compilers and with different optimization settings.  On the other hand, we
want SQLite to give the same answer regardless of how it is compiled.  So as
of version 3.7.6, SQLite is careful to avoid signed integer overflows.  We
now require that SQLite work even if compiled using the -fwrapv option in
GCC.

http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html
http://blog.regehr.org/archives/213



>  * From 3.7.6 on, integer operands of *some operations* (left shift being
>   notable exception) are converted to real if the operation would overflow.
>
> I don't think either behaviour is specified anywhere. However, the old
> behaviour was IMO consistent and was very useful for two cases:
>
>  * When working with unsigned numbers on the application side (arithmetic
>   operations except division (/) and right shift (>>) don't consider sign).
>  * To get some bit patterns when doing bitwise operations (since there are
>   & and |, but no negation and no hexadecimal literals).
>
> On the other hand the new behaviour will:
>
>  * Give MIN_INT64 for all operations that overflowed (the application
> expects
>   integer, so will probably read with sqlite3_column_int64 and conversion
> of
>   too large reals *is* specified to return MIN_INT64).
>  * Give inprecise result for cases where the overflows cancel out (e.g.
>   a + b - c where a + b overflows, but a + (b - c) does not.
>
> Would you be so kind and at least visibly document this change, consider
> which behaviour is actually prefered and document the behaviour. Thanks.
>
>
> As for my particular case, I have a database with table (let's call it
> "objects") with large integeral primary key and many other tables refering
> to
> it. And another table (let's call it "sides"), which needs *two* rows for
> each row in "objects". Since "integer primary key" is faster than "primary
> key (object_id, side)" and since the rows are mostly handled independenty
> (and have many other things refer to them), I construct a primary key with:
>
>object_id | (side << 63)
>
> Now when I need to join "sides" and "objects", I need condition
>
>object_id = side_id & ~(1 << 63)
>
> but that's not valid syntax. There are two alternatives:
>
>(1 << 63) - 1  or  -1 - (1 << 63)
>

Surprisingly, the first does *not* work in C - at least not all the time.
The answer is undefined.  It gives the "expected" answer often, especially
when optimizations are disabled.  But if you crank up the optimization on a
recent version of GCC or Clang, you'll likely get something different from
what you expect, unfortunately.


>
> I used the first, because it is more readable to me (while the later is
> exact
> alternative to the bitwise not, it's not common knowledge, because other
> languages do have bitwise not). But it stopped working in 3.7.6 (the later
> still does, so I can convert it, but it's error-prone situation).
>
> Regards,
> Jan
>
> --
>- Jan Hudec 
>
>
> ___
> sqlite-users mailing list
> sqlite-users@sqlite.org
> http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
>



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

Re: [sqlite] [BUG] Silent change in intergeral overflow handling in 3.7.6

[Jan Hudec]

Radovan Antloga  writes:

> http://www.sqlite.org/releaselog/3_7_6.html

Ok, I see it's mentioned there. Given that it changes semantics I would have
expected it to be mentioned more prominently though.

Now may I ask why it was done? Are there some known real world cases where it
is better (I have one real-world case where it's worse and generally think
that if application expects reals, it uses reals already anyway, so it does
not end up causing integer overflow).

> >   * Up to 3.7.5, integer operations are always carried out in 64-bit 
> > integers
> > and overflow as expected for that type.
> >   * From 3.7.6 on, integer operands of *some operations* (left shift being
> > notable exception) are converted to real if the operation would 
> > overflow.

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

Re: [sqlite] [BUG] Silent change in intergeral overflow handling in 3.7.6

[Jean-Denis Muys]

On 25 mai 2011, at 10:40, Jan Hudec wrote:
> Since "integer primary key" is faster than "primary
> key (object_id, side)" and since the rows are mostly handled independenty
> (and have many other things refer to them), I construct a primary key with:
> 
>object_id | (side << 63)
[...]
> Regards,
> Jan

Interesting. I too use an integer primary key as a bitfield. Specifically, I 
need to identify a data record in a three-dimensional space (a data cube), and 
my key is:

  (z << 16) + (y << 8) + x

This works for me because the three dimensions I use (x, y, z here) are 
positive integral values that can never exceed 255.

Clearly, I won't be affected by the overflow issue you discovered.

I hope there aren't other pitfalls when using a primary key as a bitfield.

JD

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

Re: [sqlite] [BUG] Silent change in intergeral overflow handling in 3.7.6

[Radovan Antloga]

See this:

http://www.sqlite.org/releaselog/3_7_6.html

Regards,
R.Antloga

S, Jan Hudec piše:
> Hello All,
>
> [Is this correct place to report a bug, or can I create it in Fossil
> somehow?]
>
> Semantics of operations on integers changed between 3.7.5 and 3.7.6. It does
> not seem to be mentioned in change log (http://www.sqlite.org/news.html),
> though it may affect existing applications:
>
>   * Up to 3.7.5, integer operations are always carried out in 64-bit integers
> and overflow as expected for that type.
>   * From 3.7.6 on, integer operands of *some operations* (left shift being
> notable exception) are converted to real if the operation would overflow.
>
> I don't think either behaviour is specified anywhere. However, the old
> behaviour was IMO consistent and was very useful for two cases:
>
>   * When working with unsigned numbers on the application side (arithmetic
> operations except division (/) and right shift (>>) don't consider sign).
>   * To get some bit patterns when doing bitwise operations (since there are
> &  and |, but no negation and no hexadecimal literals).
>
> On the other hand the new behaviour will:
>
>   * Give MIN_INT64 for all operations that overflowed (the application expects
> integer, so will probably read with sqlite3_column_int64 and conversion of
> too large reals *is* specified to return MIN_INT64).
>   * Give inprecise result for cases where the overflows cancel out (e.g.
> a + b - c where a + b overflows, but a + (b - c) does not.
>
> Would you be so kind and at least visibly document this change, consider
> which behaviour is actually prefered and document the behaviour. Thanks.
>
>
> As for my particular case, I have a database with table (let's call it
> "objects") with large integeral primary key and many other tables refering to
> it. And another table (let's call it "sides"), which needs *two* rows for
> each row in "objects". Since "integer primary key" is faster than "primary
> key (object_id, side)" and since the rows are mostly handled independenty
> (and have many other things refer to them), I construct a primary key with:
>
>  object_id | (side<<  63)
>
> Now when I need to join "sides" and "objects", I need condition
>
>  object_id = side_id&  ~(1<<  63)
>
> but that's not valid syntax. There are two alternatives:
>
>  (1<<  63) - 1  or  -1 - (1<<  63)
>
> I used the first, because it is more readable to me (while the later is exact
> alternative to the bitwise not, it's not common knowledge, because other
> languages do have bitwise not). But it stopped working in 3.7.6 (the later
> still does, so I can convert it, but it's error-prone situation).
>
> Regards,
> Jan
>
> --
>  - Jan Hudec
>
>
> ___
> sqlite-users mailing list
> sqlite-users@sqlite.org
> http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
>
>
>
>
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

[sqlite] [BUG] Silent change in intergeral overflow handling in 3.7.6

[Jan Hudec]

Hello All,

[Is this correct place to report a bug, or can I create it in Fossil
somehow?]

Semantics of operations on integers changed between 3.7.5 and 3.7.6. It does
not seem to be mentioned in change log (http://www.sqlite.org/news.html),
though it may affect existing applications:

 * Up to 3.7.5, integer operations are always carried out in 64-bit integers
   and overflow as expected for that type.
 * From 3.7.6 on, integer operands of *some operations* (left shift being
   notable exception) are converted to real if the operation would overflow.

I don't think either behaviour is specified anywhere. However, the old
behaviour was IMO consistent and was very useful for two cases:

 * When working with unsigned numbers on the application side (arithmetic
   operations except division (/) and right shift (>>) don't consider sign).
 * To get some bit patterns when doing bitwise operations (since there are
   & and |, but no negation and no hexadecimal literals).

On the other hand the new behaviour will:

 * Give MIN_INT64 for all operations that overflowed (the application expects
   integer, so will probably read with sqlite3_column_int64 and conversion of
   too large reals *is* specified to return MIN_INT64).
 * Give inprecise result for cases where the overflows cancel out (e.g.
   a + b - c where a + b overflows, but a + (b - c) does not.

Would you be so kind and at least visibly document this change, consider
which behaviour is actually prefered and document the behaviour. Thanks.


As for my particular case, I have a database with table (let's call it
"objects") with large integeral primary key and many other tables refering to
it. And another table (let's call it "sides"), which needs *two* rows for
each row in "objects". Since "integer primary key" is faster than "primary
key (object_id, side)" and since the rows are mostly handled independenty
(and have many other things refer to them), I construct a primary key with:

object_id | (side << 63)

Now when I need to join "sides" and "objects", I need condition

object_id = side_id & ~(1 << 63)

but that's not valid syntax. There are two alternatives:

(1 << 63) - 1  or  -1 - (1 << 63)

I used the first, because it is more readable to me (while the later is exact
alternative to the bitwise not, it's not common knowledge, because other
languages do have bitwise not). But it stopped working in 3.7.6 (the later
still does, so I can convert it, but it's error-prone situation).

Regards,
Jan

--
- Jan Hudec 


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