|
static inline size_t mi_ctz32(uint32_t x) { |
|
// de Bruijn multiplication, see <http://supertech.csail.mit.edu/papers/debruijn.pdf> |
|
static const unsigned char debruijn[32] = { |
|
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, |
|
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9 |
|
}; |
|
if (x==0) return 32; |
|
return debruijn[((x & -(int32_t)x) * 0x077CB531UL) >> 27]; |
|
} |
|
static inline size_t mi_clz32(uint32_t x) { |
|
// de Bruijn multiplication, see <http://supertech.csail.mit.edu/papers/debruijn.pdf> |
|
static const uint8_t debruijn[32] = { |
|
31, 22, 30, 21, 18, 10, 29, 2, 20, 17, 15, 13, 9, 6, 28, 1, |
|
23, 19, 11, 3, 16, 14, 7, 24, 12, 4, 8, 25, 5, 26, 27, 0 |
|
}; |
|
if (x==0) return 32; |
|
x |= x >> 1; |
|
x |= x >> 2; |
|
x |= x >> 4; |
|
x |= x >> 8; |
|
x |= x >> 16; |
|
return debruijn[(uint32_t)(x * 0x07C4ACDDUL) >> 27]; |
|
} |
|
|
Bug report
Bug description:
The integrated mimalloc has out-of-bounds bug in the generic implementation of ctz/clz:
cpython/Include/internal/mimalloc/mimalloc/internal.h
Lines 847 to 870 in 6a22963
On platforms with 64-bit
UL, the multiplication in index calculation can grow much larger than arraydebruijn[].It has been fixed in this upstream commit:
microsoft/mimalloc@ed31847
CPython versions tested on:
3.14, CPython main branch, 3.13, 3.15
Operating systems tested on:
Linux
Linked PRs