serious bug in (cython) bitsets, Cython hackers please have a look

[Dima Pasechnik]

bitset_in(s,m) returns wrong answers for sets of size
m=320+k*128, k>=0. Linux-only, works on macOS
Found while working on https://github.com/sagemath/sage/issues/41472
(fixing this bitsets issue will fix the latter)

# save as t.pyx and run
# sage: %runfile t.pyx
# sage: t(320), and more generally t(320+k*128) for k>=1
# false on macOS, true on Linux, oops
from sage.data_structures.bitset_base cimport *
def t(n):
cdef bitset_t s
cdef int i
cdef int max
max = n
bitset_init(s, max)
for i in range(max):
bitset_set(s, i)
return bitset_in(s, max)

[Vincent Delecroix]

This is not an allowed instruction. You are accessing index n but only
the indices 0 to n-1 (included) are in the bitset. There is no bounds
check in bitset_in (which would be too onerous). The behavior is
unspecified as you are accessing unknown memory space.

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To view this discussion visit https://groups.google.com/d/msgid/sage-devel/CAAWYfq05RjwzE%2B8-x5zhnH_U1WUSgtL6R57N9cu7DTZQrKN-mA%40mail.gmail.com.