Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Errors in iter1() #6

Closed
pmarks opened this issue Jun 25, 2024 · 1 comment
Closed

Errors in iter1() #6

pmarks opened this issue Jun 25, 2024 · 1 comment
Labels
bug Something isn't working

Comments

@pmarks
Copy link

pmarks commented Jun 25, 2024

Very cool crate! I ran into some cases where iter1() returns incorrect results - it appears to skip blocks of ~8 ONE bits. I augmented test_random_data_rank() with some tests of iter0/1 and ran into a crash. The test below will fail with thread 'bit_vec::fast_rs_vec::tests::test_random_data_rank' panicked at src/bit_vec/fast_rs_vec/iter.rs:327:19: attempt to shift left with overflow on x86_64. I get the same failure with and without target-cpu=native

Test:

#[test]
fn test_random_data_rank() {
    let mut bv = BitVec::with_capacity(LENGTH);
    let mut rng = StdRng::from_seed([
        0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5,
        6, 7,
    ]);
    let sample = Uniform::new(0, 2);
    static LENGTH: usize = 4 * SUPER_BLOCK_SIZE;

    for _ in 0..LENGTH {
        bv.append_bit(sample.sample(&mut rng));
    }

    let bv = RsVec::from_bit_vec(bv);

    assert_eq!(bv.len(), LENGTH);

    // new iter0/1 tests
    for bit1 in bv.iter1() {
        assert_eq!(bv.get(bit1), Some(1));
    }

    for bit0 in bv.iter0() {
        assert_eq!(bv.get(bit0), Some(0));
    }

    let mut all_bits: Vec<_> = bv.iter0().chain(bv.iter1()).collect();
    all_bits.sort();
    all_bits.dedup();
    assert_eq!(all_bits.len(), LENGTH);
}

Relevant stack:

                               at /mnt/home/pat/code/vers/src/bit_vec/fast_rs_vec/iter.rs:327:19
  21:     0x559235af78b8 - <vers_vecs::bit_vec::fast_rs_vec::iter::SelectIter<_> as core::iter::traits::iterator::Iterator>::next::h917ec949850a2aeb
                               at /mnt/home/pat/code/vers/src/bit_vec/fast_rs_vec/iter.rs:358:13
  22:     0x559235adffcf - vers_vecs::bit_vec::fast_rs_vec::tests::test_random_data_rank::hbe5742e7b9163e43
                               at /mnt/home/pat/code/vers/src/bit_vec/fast_rs_vec/tests.rs:36:17
  23:     0x559235ac5077 - vers_vecs::bit_vec::fast_rs_vec::tests::test_random_data_rank::{{closure}}::h661c2093803983ac
                               at /mnt/home/pat/code/vers/src/bit_vec/fast_rs_vec/tests.rs:19:27
  24:     0x559235b27da6 - core::ops::function::FnOnce::call_once::h22b1d390239012f7```
@Cydhra Cydhra added the bug Something isn't working label Jun 25, 2024
Cydhra added a commit that referenced this issue Jun 25, 2024
Cydhra added a commit that referenced this issue Jun 25, 2024
…s the last block of a super block, because it accessed metadata of the next super block

fix: Issue #6, which happened because the number of ones in a block was incorrectly calculated (I forgot to subtract zeros of other super blocks)
@Cydhra
Copy link
Owner

Cydhra commented Jun 25, 2024

Fixed in 685b673. Released as 1.3.2 on crates.io.
Will be merged into master before next minor release.

@Cydhra Cydhra closed this as completed Jun 25, 2024
Cydhra added a commit that referenced this issue Jun 28, 2024
* added test case testing the correct construction of the block structure, and one that tests issue #6

* fix: last_block check in select iterators failed if the last_block was the last block of a super block, because it accessed metadata of the next super block
fix: Issue #6, which happened because the number of ones in a block was incorrectly calculated (I forgot to subtract zeros of other super blocks)

* code style

* #8: storing the last word in the select-iterator makes no sense, because we cannot safely compare the rank within a block to the ranks within the word, since we do not have access to the popcounts of previous words. We could keep track of them, but there are 8 words in a block, it's not worth it.

* Added a fuzzing test for iter0 and iter1

* bumped patch version to 1.3.3
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working
Projects
None yet
Development

No branches or pull requests

2 participants