select_support_mcl.init_fast is broken

[jnalanko]

The init_fast function of select_support_mcl crashes with the following error:

Assertion failed: (idx < this->size()), function operator[]

My code is the following:

#include "sdsl/wavelet_trees.hpp"
#include "sdsl/construct.hpp"
#include <string>
#include <fstream>
#include <iostream>
#include <set>

using namespace std;
using namespace sdsl;

string read_raw_file(string filename){

    std::ifstream t(filename.c_str());
    std::string str;

    t.seekg(0, std::ios::end);   
    str.reserve(t.tellg());
    t.seekg(0, std::ios::beg);

    str.assign((std::istreambuf_iterator<char>(t)),
                std::istreambuf_iterator<char>());
    
    return str;
}

int main(){
    wt_huff<> wt;
    string s = read_raw_file("init_fast_killer.txt");
    construct_im(wt, s.c_str(), 1);
}

The file init_fast_killer.txt is attached (11MB).

The local variables at the moment of the crash are:

m_logn	uint32_t	25
m_logn2	uint32_t	625
m_logn4	uint32_t	390625
m_arg_cnt	sdsl::select_support::size_type	10665912
v	const bit_vector *	0x7fff5fbfd988	0x00007fff5fbfd988
  m_size	size_type	25587416
  m_data	uint64_t *	0x104000000	0x0000000104000000
  m_width	sdsl::int_vector<'\x01'>::int_width_type	'\x01'

SUPER_BLOCK_SIZE	sdsl::select_support::size_type	4096
sb	sdsl::select_support::size_type	2604
arg_position	size_type [4096]	
data	const uint64_t *	0x10430cdd8	0x000000010430cdd8
carry_new	uint64_t	0
last_k64	sdsl::select_support::size_type	4097
sb_cnt	sdsl::select_support::size_type	2603
i	sdsl::select_support::size_type	25587392
cnt_old	sdsl::select_support::size_type	10665912
cnt_new	sdsl::select_support::size_type	10665952
last_k64_sum	sdsl::select_support::size_type	10665985
pos_of_last_arg_in_the_block	sdsl::select_support::size_type	25587424
pos_diff	sdsl::select_support::size_type	770433
j	sdsl::select_support::size_type	25587416
k	sdsl::select_support::size_type	4024

The crash happens because the code tries to access index j = 25587416 in v, but the size of v is only 25587416, so we have an off by one error. I also see another problem: The value of last_k64 is 4097 but on line 289 of select_support_mcl.hpp we assign a value to arg_position[last_k64-1], which is one off the end of the array, since the size of the array is 4096.

init_fast_killer.txt

[jnalanko]

Is anybody able to reproduce the error?

[jnalanko]

Anyone?

[mpetri]

Can you try using the "new sdsl-lite" version which is developed at https://github.com/xxsds/sdsl-lite ?