Opened 8 years ago

Closed 8 years ago

#17526 closed defect (fixed)

Bitset doctest failures on OS X

Reported by: jdemeyer Owned by:
Priority: blocker Milestone: sage-6.5
Component: misc Keywords:
Cc: jhpalmieri, SimonKing Merged in:
Authors: Jeroen Demeyer Reviewers: Simon King, John Palmieri
Report Upstream: N/A Work issues:
Branch: 0d1e149 (Commits, GitHub, GitLab) Commit: 0d1e1497735026f12f1cb06c5ef919f462d0bd23
Dependencies: Stopgaps:

Status badges

Description

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

Change History (9)

comment:1 Changed 8 years ago by jdemeyer

Authors: Jeroen Demeyer

comment:2 Changed 8 years ago by jdemeyer

Branch: u/jdemeyer/ticket/17526
Created: Dec 18, 2014, 8:25:25 PMDec 18, 2014, 8:25:25 PM
Modified: Dec 18, 2014, 8:55:15 PMDec 18, 2014, 8:55:15 PM

comment:3 Changed 8 years ago by jdemeyer

Commit: 0d1e1497735026f12f1cb06c5ef919f462d0bd23
Status: newneeds_review

New commits:

0d1e149Only add bits from extra limb if there is an extra limb

comment:4 Changed 8 years ago by jhpalmieri

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?

comment:5 Changed 8 years ago by SimonKing

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)

comment:6 Changed 8 years ago by jdemeyer

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.

comment:7 in reply to:  6 Changed 8 years ago by SimonKing

Reviewers: Simon King

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.

comment:8 Changed 8 years ago by jdemeyer

Reviewers: Simon KingSimon King, John Palmieri
Status: needs_reviewpositive_review

comment:9 Changed 8 years ago by vbraun

Branch: u/jdemeyer/ticket/175260d1e1497735026f12f1cb06c5ef919f462d0bd23
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.