storage/louds/simple_succinct_bit_vector_index.cc

// Copyright 2010-2018, Google Inc.
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following disclaimer
// in the documentation and/or other materials provided with the
// distribution.
//     * Neither the name of Google Inc. nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#include "storage/louds/simple_succinct_bit_vector_index.h"

#include <algorithm>
#include <iterator>
#include <vector>

#include "base/iterator_adapter.h"
#include "base/logging.h"
#include "base/port.h"

namespace mozc {
namespace storage {
namespace louds {
namespace {

// Simple adapter to convert from 1-bit index to 0-bit index.
class ZeroBitAdapter : public AdapterBase<int> {
 public:
  // Needs to be default constructive to create invalid iterator.
  ZeroBitAdapter() : index_(nullptr), chunk_size_(0) {}

  ZeroBitAdapter(const std::vector<int>* index, int chunk_size)
      : index_(index), chunk_size_(chunk_size) {}

  value_type operator()(const int *ptr) const {
    // The number of 0-bits
    //   = (total num bits) - (1-bits)
    //   = (chunk_size [bytes] * 8 [bits/byte] * (ptr's offset) - (1-bits)
    return chunk_size_ * 8 * (ptr - index_->data()) - *ptr;
  }

 private:
  const std::vector<int> *index_;
  int chunk_size_;
};

#ifdef __GNUC__
// TODO(hidehiko): Support XMM and 64-bits popcount for 64bits architectures.
inline int BitCount1(uint32 x) {
  return __builtin_popcount(x);
}
#else
int BitCount1(uint32 x) {
  x = ((x & 0xaaaaaaaa) >> 1) + (x & 0x55555555);
  x = ((x & 0xcccccccc) >> 2) + (x & 0x33333333);
  x = ((x >> 4) + x) & 0x0f0f0f0f;
  x = (x >> 8) + x;
  x = ((x >> 16) + x) & 0x3f;
  return x;
}
#endif

inline int BitCount0(uint32 x) {
  // Flip all bits, and count 1-bits.
  return BitCount1(~x);
}

inline bool IsPowerOfTwo(int value) {
  // value & -value is the well-known idiom to take the lowest 1-bit in
  // value, so value & ~(value & -value) clears the lowest 1-bit in value.
  // If the result is 0, value has only one 1-bit i.e. it is power of two.
  return value != 0 && (value & ~(value & -value)) == 0;
}

// Returns 1-bits in the data[0] ... data[length - 1].
int Count1Bits(const uint32 *data, int length) {
  int num_bits = 0;
  for (; length > 0; ++data, --length) {
    num_bits += BitCount1(*data);
  }
  return num_bits;
}

// Stores index (the camulative number of the 1-bits from begin of each chunk).
void InitIndex(
    const uint8 *data, int length, int chunk_size, std::vector<int> *index) {
  DCHECK_GE(chunk_size, 4);
  DCHECK(IsPowerOfTwo(chunk_size)) << chunk_size;
  DCHECK_EQ(length % 4, 0);

  index->clear();

  // Count the number of chunks with ceiling.
  const int chunk_length = (length + chunk_size - 1) / chunk_size;

  // Reserve the memory including a sentinel.
  index->reserve(chunk_length + 1);

  int num_bits = 0;
  for (int remaining_num_words = length / 4; remaining_num_words > 0;
       data += chunk_size, remaining_num_words -= chunk_size / 4) {
    index->push_back(num_bits);
    num_bits += Count1Bits(reinterpret_cast<const uint32 *>(data),
                           std::min(chunk_size / 4, remaining_num_words));
  }
  index->push_back(num_bits);

  CHECK_EQ(chunk_length + 1, index->size());
}

void InitLowerBound0Cache(const std::vector<int> &index, int chunk_size,
                          size_t increment, size_t size,
                          std::vector<const int *> *cache) {
  DCHECK_GT(increment, 0);
  cache->clear();
  cache->reserve(size + 2);
  cache->push_back(index.data());
  ZeroBitAdapter adapter(&index, chunk_size);
  for (size_t i = 1; i <= size; ++i) {
    const int target_index = increment * i;
    const int *ptr = std::lower_bound(
        MakeIteratorAdapter(index.data(), adapter),
        MakeIteratorAdapter(index.data() + index.size(), adapter),
        target_index).base();
    cache->push_back(ptr);
  }
  cache->push_back(index.data() + index.size());
}

void InitLowerBound1Cache(const std::vector<int> &index, int chunk_size,
                          size_t increment, size_t size,
                          std::vector<const int *> *cache) {
  DCHECK_GT(increment, 0);
  cache->clear();
  cache->reserve(size + 2);
  cache->push_back(index.data());
  for (size_t i = 1; i <= size; ++i) {
    const int target_index = increment * i;
    const int *ptr = std::lower_bound(index.data(), index.data() + index.size(),
                                      target_index);
    cache->push_back(ptr);
  }
  cache->push_back(index.data() + index.size());
}

}  // namespace

void SimpleSuccinctBitVectorIndex::Init(const uint8 *data, int length,
                                        size_t lb0_cache_size,
                                        size_t lb1_cache_size) {
  data_ = data;
  length_ = length;
  InitIndex(data, length, chunk_size_, &index_);

  // TODO(noriyukit): Currently, we simply use uniform increment width for lower
  // bound cache.  Nonuniform increment width may improve performance.
  lb0_cache_increment_ =
      lb0_cache_size == 0 ? GetNum0Bits() : GetNum0Bits() / lb0_cache_size;
  if (lb0_cache_increment_ == 0) {
    lb0_cache_increment_ = 1;
  }
  InitLowerBound0Cache(index_, chunk_size_, lb0_cache_increment_,
                       lb0_cache_size, &lb0_cache_);

  lb1_cache_increment_ =
      lb1_cache_size == 0 ? GetNum1Bits() : GetNum1Bits() / lb1_cache_size;
  if (lb1_cache_increment_ == 0) {
    lb1_cache_increment_ = 1;
  }
  InitLowerBound1Cache(index_, chunk_size_, lb1_cache_increment_,
                       lb1_cache_size, &lb1_cache_);
}

void SimpleSuccinctBitVectorIndex::Reset() {
  data_ = nullptr;
  length_ = 0;
  index_.clear();
  lb0_cache_increment_ = 1;
  lb0_cache_.clear();
  lb1_cache_increment_ = 1;
  lb1_cache_.clear();
}

int SimpleSuccinctBitVectorIndex::Rank1(int n) const {
  // Look up pre-computed 1-bits for the preceding chunks.
  const int num_chunks = n / (chunk_size_ * 8);
  int result = index_[n / (chunk_size_ * 8)];

  // Count 1-bits for remaining "words".
  result += Count1Bits(
      reinterpret_cast<const uint32 *>(data_ + num_chunks * chunk_size_),
      (n / 8 - num_chunks * chunk_size_) / 4);

  // Count 1-bits for remaining "bits".
  if (n % 32 > 0) {
    const int index = n / 32;
    const int shift = 32 - n % 32;
    result +=
        BitCount1(reinterpret_cast<const uint32 *>(data_)[index] << shift);
  }

  return result;
}

int SimpleSuccinctBitVectorIndex::Select0(int n) const {
  DCHECK_GT(n, 0);

  // Narrow down the range of |index_| on which lower bound is performed.
  int lb0_cache_index = n / lb0_cache_increment_;
  if (lb0_cache_index > lb0_cache_.size() - 2) {
    lb0_cache_index = lb0_cache_.size() - 2;
  }
  DCHECK_GE(lb0_cache_index, 0);

  // Binary search on chunks.
  ZeroBitAdapter adapter(&index_, chunk_size_);
  const int *chunk_ptr =
      std::lower_bound(
          MakeIteratorAdapter(lb0_cache_[lb0_cache_index], adapter),
          MakeIteratorAdapter(lb0_cache_[lb0_cache_index + 1], adapter), n)
          .base();
  const int chunk_index = (chunk_ptr - index_.data()) - 1;
  DCHECK_GE(chunk_index, 0);
  n -= chunk_size_ * 8 * chunk_index - index_[chunk_index];

  // Linear search on remaining "words"
  const uint32 *ptr =
      reinterpret_cast<const uint32 *>(data_) + chunk_index * chunk_size_ / 4;
  while (true) {
    const int bit_count = BitCount0(*ptr);
    if (bit_count >= n) {
      break;
    }
    n -= bit_count;
    ++ptr;
  }

  int index = (ptr - reinterpret_cast<const uint32 *>(data_)) * 32;
  for (uint32 word = ~(*ptr); n > 0; word >>= 1, ++index) {
    n -= (word & 1);
  }

  // Index points to the "next bit" of the target one.
  // Thus, subtract one to adjust.
  return index - 1;
}

int SimpleSuccinctBitVectorIndex::Select1(int n) const {
  DCHECK_GT(n, 0);

  // Narrow down the range of |index_| on which lower bound is performed.
  int lb1_cache_index = n / lb1_cache_increment_;
  if (lb1_cache_index > lb1_cache_.size() - 2) {
    lb1_cache_index = lb1_cache_.size() - 2;
  }
  DCHECK_GE(lb1_cache_index, 0);

  // Binary search on chunks.
  const int *chunk_ptr = std::lower_bound(lb1_cache_[lb1_cache_index],
                                          lb1_cache_[lb1_cache_index + 1], n);
  const int chunk_index = (chunk_ptr - index_.data()) - 1;
  DCHECK_GE(chunk_index, 0);
  n -= index_[chunk_index];

  // Linear search on remaining "words"
  const uint32 *ptr =
      reinterpret_cast<const uint32 *>(data_) + chunk_index * chunk_size_ / 4;
  while (true) {
    const int bit_count = BitCount1(*ptr);
    if (bit_count >= n) {
      break;
    }
    n -= bit_count;
    ++ptr;
  }

  int index = (ptr - reinterpret_cast<const uint32 *>(data_)) * 32;
  for (uint32 word = *ptr; n > 0; word >>= 1, ++index) {
    n -= (word & 1);
  }

  // Index points to the "next bit" of the target one.
  // Thus, subtract one to adjust.
  return index - 1;
}

}  // namespace louds
}  // namespace storage
}  // namespace mozc