Bitset doctest failures on OS X

[jdemeyer]

John Palmieri reports this in two OS X systems:

sage -t --warn-long 35.1 src/sage/data_structures/bitset.pyx
**********************************************************************
File "src/sage/data_structures/bitset.pyx", line 1998, in sage.data_structures.bitset.test_bitset
Failed example:
    test_bitset('00'*64, '01'*64, 127)
Expected:
    a 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    list a []
    a.size 128
    len(a) 0
    a.limbs ...
    b 01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101
    a.in(n)   False
    a.not_in(n)   True
    a.add(n)     00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
    a.discard(n)   00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a.set_to(n)  00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
    a.flip(n)    00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
    a.set_first_n(n)    11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110
    a.first_in_complement()    127
    a.isempty()  True
    a.eq(b)      False
    a.cmp(b)     -1
    a.lex_cmp(b) -1
    a.issubset(b) True
    a.issuperset(b) False
    a.copy()     00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    r.clear()     00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    complement a        11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
    a intersect b      00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a union b       01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101
    a minus b      00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a symmetric_difference b      01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101
    a.rshift(n)  00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a.lshift(n)  00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a.first()           -1
    a.next(n)           -1
    a.first_diff(b)     1
    a.next_diff(b, n)   127
    a.hamming_weight()  0
    a.map(m)  00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a == loads(dumps(a))  True
    rshifts add  True
    lshifts add  True
    intersection commutes True
    union commutes  True
    not not = id True
    flipped bit  127
    add bit      127
    discard bit    127
    lshift add unset ok True
    rshift set unset ok True
    reallocating a      00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    to size 127          0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    to size 254          00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    to original size    00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Got:
    a 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    list a []
    a.size 128
    len(a) 0
    a.limbs 2
    b 01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101
    a.in(n)   False
    a.not_in(n)   True
    a.add(n)     00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
    a.discard(n)   00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a.set_to(n)  00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
    a.flip(n)    00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
    a.set_first_n(n)    11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110
    a.first_in_complement()    127
    a.isempty()  True
    a.eq(b)      False
    a.cmp(b)     -1
    a.lex_cmp(b) -1
    a.issubset(b) True
    a.issuperset(b) False
    a.copy()     00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    r.clear()     00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    complement a        11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
    a intersect b      00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a union b       01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101
    a minus b      00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a symmetric_difference b      01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101
    a.rshift(n)  00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a.lshift(n)  00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a.first()           -1
    a.next(n)           -1
    a.first_diff(b)     1
    a.next_diff(b, n)   127
    a.hamming_weight()  0
    a.map(m)  00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    a == loads(dumps(a))  True
    rshifts add  False
    lshifts add  True
    intersection commutes True
    union commutes  True
    not not = id True
    flipped bit  127
    add bit      127
    discard bit    127
    lshift add unset ok True
    rshift set unset ok False
    reallocating a      00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    to size 127          0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    to size 254          00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    to original size    00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
**********************************************************************

I see a difference in rshift set unset ok False

CC: @jhpalmieri @simon-king-jena

Component: misc

Author: Jeroen Demeyer

Branch/Commit: 0d1e149

Reviewer: Simon King, John Palmieri

Issue created by migration from https://trac.sagemath.org/ticket/17526

[jdemeyer]

Author: Jeroen Demeyer

[jdemeyer]

Branch: u/jdemeyer/ticket/17526

[jdemeyer]

New commits:

0d1e149

Only add bits from extra limb if there is an extra limb

[jdemeyer]

Commit: 0d1e149

[jhpalmieri]

comment:4

There is also a difference in rshifts add False. Anyway, with this patch, the doctest passes on two different OS X machines (OS X 10.9 and 10.10). It would be good for someone who understands the bitset code to check this, though. Simon?

[simon-king-jena]

comment:5

Let me try to put some semantic on the existing code (i.e., without your patch).

We shift by n bits. The variable nlimbs denotes the number of limbs that are fully discarded by the shift.
Expl: If a limb comprises 32 bit and we shift by 37 bits, then nlimbs is 1.

The variable shifted_limbs denotes the number of limbs of a that carry data to-be-put into r (provided that r is large enough).
Expl: If a comprises 5 limbs in the example above, then we have shifted_limbs=4.

The variable nbits is the remainder of n by the limb size, hence, nbits=5 in our example.

If r is large enough to contain shifted_limbs limbs, then we can just shift (if nbits>0) resp. copy (if nbits==0). Otherwise, we can only shift r.limbs limbs.

If in our example r.limbs==3<shifted_limbs==4, then we would like to omit limb number 0 of a, and then take limbs 1, 2, 3 of a, shift it by 5 bits, and put the result into limbs 0,1 and 2 of r. In addition, we want that the first 5 bits of limb 4 of a shall appear as the 5 highest bits of limb number 2 of r.

However, if r.limbs>=4==shifted_limbs, then it is enough to shift limbs 1,2,3,4 of a, shift by 5 bits, and put the result into the limbs 0,1,2,3 of r. There are no additional 5 bits to be put somewhere. However, it is needed to clear the top bits of r: It could be that r does not use all bits of its limb number 3, and hence there might be some bits obtained from a that should be discarded.

Hence, I believe the following solution would be easier:

    if shifted_limbs <= r.limbs: # here I changed "<" to "<="
        if nbits:
            mpn_rshift(r.bits, a.bits + nlimbs, shifted_limbs, nbits)
        else:
            mpn_copyi(r.bits, a.bits + nlimbs, shifted_limbs)

        # Clear top limbs (note that r.limbs - shifted_limbs >= 1)
        mpn_zero(r.bits + (r.limbs - nlimbs), r.limbs - shifted_limbs)
    else:
        # Number of limbs to shift is r.limbs
        if nbits:
            mpn_rshift(r.bits, a.bits + nlimbs, r.limbs, nbits)
            # Add the additional bits from top limb of a
            r.bits[r.limbs-1] |= a.bits[r.limbs+nlimbs] << (GMP_LIMB_BITS - nbits)
        else:
            mpn_copyi(r.bits, a.bits + nlimbs, r.limbs)

        # Clear bits outside bitset in top limb
        bitset_fix(r)

[jdemeyer]

comment:6

You really need 3 cases, otherwise the comment note that r.limbs - shifted_limbs >= 1 becomes false. Moreover, the case shifted_limbs == r.limbs requires bitset_fix() in general.

[simon-king-jena]

comment:7

Replying to @jdemeyer:

You really need 3 cases, otherwise the comment note that r.limbs - shifted_limbs >= 1 becomes false.

... and ">=1" is needed, since mpn_zero can only zero a 'positive' number of limbs, right?

Moreover, the case shifted_limbs == r.limbs requires bitset_fix() in general.

Also correct.

OK, my questions are answered. I can not test if the branch fixes the problem on OSX. But the code looks good. If someone (John?) can confirm that it works on OSX, please feel free to switch to positive review.

[simon-king-jena]

Reviewer: Simon King

[jdemeyer]

Changed reviewer from Simon King to Simon King, John Palmieri

[vbraun]

Changed branch from u/jdemeyer/ticket/17526 to 0d1e149