Rank returns wrong results

[rob-p]

Hi,

I've been looking at some different rank and select implementations, and during testing I've noticed that the current implementation here returns incorrect results for the rank operation (compared to Vinga's rank9b --- which I verified to be correct). Is this a known issue? I haven't dug into the code to determine exactly why the bug is happening, but it seems to happen in both large and small-scale bit vectors, so it might even be related to the popcountLinear implementation.

[dave-andersen]

Hi, Rob - we don't have any known issues. Could you help provide a test case we can use to reproduce this? Thanks!

[rob-p]

Hi Dave,

Thanks for the reply! I've been looking into this, and the issue seems to derive from how the underlying bit-array is stored. Specifically, the assumed order of the bytes within each word. I'm using this bit array library, and the native storage is directly compatible with Vinga's implementation. However, to get efficient/rankselect to return the correct results, I have to reverse the bytes of each word (e.g. via repeated calls to the bit_array_reverse_region() function on word-sized chunks of the bit array). Thus, I'm thinking that this is not a bug in rankselect, but rather a difference in the assumed endian-ness of the underlying word-packed representation of the bitvector. I think I was just taken by surprise that passing exactly the same memory to the Vinga rank9b implementation and rankselect resulted in completely different behavior. In case you're interested, the code I was testing with is here --- though, the tests should now work with the re-arrangement of the bit array for rankselect.

Please let me know if I'm mistaken about my interpretation here. Otherwise, please feel free to close this issue! Of course, I think a brief mention about the assumed memory layout of the bitvector somewhere in the readme might help future users of rankselect avoid the confusions I had ;).

Best,
Rob