Inconsistent behavior when doing bitwise arithmetic

[peter....@gmail.com]

Hi all,

I get a weird behavior when using bitwise-ior and bitwise-and with large numbers. Tested on 2 machines (racket 6.6, Ubuntu 16.04 and 14.04):

Here is the test example:

#lang racket
(define num #xffffffffffffffff) ;; remove one f, and the results are fine in both cases
(for ([i 5])
  (printf "~a~n" (bitwise-ior (bitwise-and num -2) 0)))


When run from DrRacket using ctr+r, it works properly:
18446744073709551614
18446744073709551614
18446744073709551614
18446744073709551614
18446744073709551614

When pasted into DrRacket's REPL (or run from command line via "racket random-bug.rkt"), the code does not only produce wrong result, but also seems to be counting something :)
70112357026588
70112357038692
70112357043588
70112357048576
70112357053344

Removing one "f" from the test number results in correct behavior in both cases.
Very large numbers are are reduced to the same range (around 54 bits).
Replacing the expression (bitwise-and num -2) by the corresponding number it computes results in correct behavior.

Cheers,
Peter

[John Boyle]

I can confirm weird behavior (and I get different weird results):

Welcome to Racket v6.5.
> (define num #xffffffffffffffff)

(for ([i 5])
  (printf "~a~n" (bitwise-ior (bitwise-and num -2) 0)))

2192618128
2192618180
2192618200
2192618668
2192618688

> (for ([i 5])
  (printf "~a~n" (bitwise-ior (bitwise-and num -2) 0)))

2192791964
2192792016
2192792036
2192792504
2192792524
> (bitwise-and num -2)
18446744073709551614
> (bitwise-and num -2)
18446744073709551614
> (bitwise-and num -2)
18446744073709551614
> (bitwise-and num -2)
18446744073709551614
> (define h (bitwise-and num -2))

> (for ([i 5])

  (printf "~a~n" (bitwise-ior h 0)))

18446744073709551614
18446744073709551614
18446744073709551614
18446744073709551614
18446744073709551614

> (for ([i 5])

  (printf "~a~n" (bitwise-ior h 0)))

18446744073709551614
18446744073709551614
18446744073709551614
18446744073709551614
18446744073709551614

--John Boyle

Science is what we understand well enough to explain to a computer. Art is everything else we do. --Knuth

--
You received this message because you are subscribed to the Google Groups "Racket Developers" group.
To unsubscribe from this group and stop receiving emails from it, send an email to racket-dev+unsubscribe@googlegroups.com.
To post to this group, send email to racke...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/racket-dev/d0310d90-0d88-4902-b430-0069b310d7a3%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Matthew Flatt]

Thanks for the report!

This is a bug in the optimizer's handling of `bitwise-and`, where I
made it assume a fixnum result if either argument is a fixnum. That's
obviously not correct if the fixnum is negative. I'll push a repair.

The difference you see when running in a module is because the
optimizer constant-folds the calculation, so there's no `bitwise-and`
call left to make incorrect assumptions about.

> --
> You received this message because you are subscribed to the Google Groups
> "Racket Developers" group.
> To unsubscribe from this group and stop receiving emails from it, send an

> email to racket-dev+...@googlegroups.com.

[peter....@gmail.com]

Do you have any guess why the resulting numbers vary so much?

[Vincent St-Amour]

Those numbers look like pointers interpreted as fixnums.

So my guess as to why they differ so much is that between each
operation, you call `printf`, which allocates enough to claim the
addresses between, e.g., 70112357026588 and 70112357038692. So that next
time around the loop, the result of the `bitwise-and` lives at
70112357038692.

Just a guess, though.

Vincent

> https://groups.google.com/d/msgid/racket-dev/c4b51560-736a-4a19-9b9f-0b28f4de66cb%40googlegroups.com.

[Gustavo Massaccesi]

> Those numbers look like pointers interpreted as fixnums

Yes.

The optimizer thought that the result of (bitwise-and num -2) was a
fixnum, so it changed
(bitwise-ior (bitwise-and num -2) 0)
to
(unsafe-fxior (bitwise-and num -2) 0)


All the pointers are even (actually a multiple of 4 in 32 bits and a
multiple of 8 in 64 bits). Fixnum are implemented as "pointers" to an
odd address, the fixnum n is encoded as 2*n+1.

I.E. If the "pointer" is even then it's a pointer to a real object. If
the "pointer" is odd then it's a fixnum.

In this case, the result of (bitwise-and num -2) was a pointer to a
bignum, but unsafe-fxior interpreted it as fixnum without checking the
parity, so what you see is the address of the bignum divided by 2.

Each iteration produces a new bignum, so you will usually get results
in an increasing order, as the allocator creates new objects.

Gustavo

> To view this discussion on the web visit https://groups.google.com/d/msgid/racket-dev/m2d1j3yuj4.wl-stamourv%40eecs.northwestern.edu.