bris4_subarray.cpp

#include <sdsl/bit_vectors.hpp>
#include <sdsl/int_vector.hpp>
#include <string>
#include <vector>
#include <ctime>
#include <chrono>
#include <iterator>
#include <iostream>
#include "vbyte_helpers.hpp"
#include <valgrind/callgrind.h>

using namespace std;
using namespace sdsl;

uint32_t bit_length = 4;
unsigned int random_accesses = 1000000;
uint32_t cap = 1<<bit_length;
int main(int argc, char *argv[]) {
  if(argc<=1) {
    cerr << "Give uint64_t file as parameter" << endl;
    return 1;
  }

  vector<uint64_t> original = read_data_from_file(argv[1]);

  std::array<std::vector<uint32_t>, 16> data;
  for(int i = 0; i < 16; i++) {
    vector<uint32_t> vec;
    data[i] = vec;
  }

  for(vector<uint64_t>::const_iterator i = original.begin(); i != original.end(); i++) {
    vector<uint32_t> v = vb_encode_number(*i, cap);
    v.front() += cap;
    int level = 0;
    for(auto j = v.rbegin(); j != v.rend(); j++) {
      data[level].push_back(*j);
      level++;
    }
  }
  bit_vector b[16];

  std::array<std::vector<uint8_t>, 16> iv;
  size_t index = 0;
  for(int i = 0; i < 16; i++) {
    vector<uint8_t> vec(data[i].size()/2 +1,0);
    bit_vector bv(data[i].size(), 0);
    index = 0;
    for (vector<uint32_t>::const_iterator j = data[i].begin(); j != data[i].end(); j++, index++) {
      uint8_t value = *j;
      if(index%2 == 0) {
        vec[index/2] = (value%cap)<<4;
      }
      else {
        vec[index/2] += value%cap;

      }
      bv[index] = (*j>>bit_length) & 1;
    }

    iv[i] = vec;
    b[i] = bv;
  }

  rank_support_v<0> rb[16];
  for(int i =0; i < 16; i++) {
    rank_support_v<0> r(&b[i]);
    rb[i] = r;
  }

  srand((unsigned) time(0));

  vector<unsigned int> indices(random_accesses, 0);
  for(vector<uint64_t>::size_type i = 0; i < indices.size(); i++) {
    indices[i] = rand()%(original.size()-50);
  }

  chrono::steady_clock::time_point time_begin = chrono::steady_clock::now();
  uint64_t z = 0;
  uint64_t val = 0;
  uint8_t subarray_len = 50;
  uint32_t level_indices[16];
  int max_level=-1;
  for (vector<unsigned int>::const_iterator i = indices.begin(); i != indices.end(); i++) {
    index = *i;
    max_level = -1;
    int current_level = 0;
    for(int counter=0;counter<subarray_len;counter++) {
      index = *i + counter;
      current_level = 0;
      val = 0;
      while(b[current_level][index] == 0) {
        uint8_t d = iv[current_level][index/2];
        if(index%2==1) {
          d=d&15;
        }
        else {
          d=d>>4;
        }
        val = (val<<bit_length) + d;
        if(max_level < current_level) {
          level_indices[current_level] = rb[current_level](index);
          max_level = current_level;
        }
        index = level_indices[current_level];
        level_indices[current_level]++;
        current_level++;
      }
      uint8_t e = iv[current_level][index/2];
      if(index%2==1) {
        e=e&15;
      }
      else {
        e=e>>4;
      }

      val = (val<<bit_length) + e;

      // the following is for accessing the value so it's not optimized out
      z = z^val;
      // sanity check for debugging the values
      if(0 && val != original[*i+counter]) {
        cout << "Did not match: " << val << " vs " << original[*i+counter] << endl;
      }
    }
  }

  chrono::steady_clock::time_point time_end = chrono::steady_clock::now();
  cout << "checksum: " << z << endl;
  cout << "Time taken: " << chrono::duration_cast<chrono::milliseconds> (time_end - time_begin).count() << "[ms]" << endl;
  return 0;
}