be/src/util/bit-packing-test.cc

// Licensed to the Apache Software Foundation (ASF) under one
// or more contributor license agreements.  See the NOTICE file
// distributed with this work for additional information
// regarding copyright ownership.  The ASF licenses this file
// to you under the Apache License, Version 2.0 (the
// "License"); you may not use this file except in compliance
// with the License.  You may obtain a copy of the License at
//
//   http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing,
// software distributed under the License is distributed on an
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, either express or implied.  See the License for the
// specific language governing permissions and limitations
// under the License.

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <random>
#include <unordered_map>

#include "testutil/gtest-util.h"
#include "testutil/rand-util.h"
#include "testutil/mem-util.h"
#include "util/bit-packing.h"
#include "util/bit-stream-utils.inline.h"

#include "common/names.h"

using std::uniform_int_distribution;
using std::mt19937;

namespace impala {

namespace {

constexpr int NUM_IN_VALUES = 64 * 1024;

template <typename UINT_T>
constexpr UINT_T ComputeMask(int bit_width) {
  return (bit_width < sizeof(UINT_T) * CHAR_BIT) ?
      ((1UL << bit_width) - 1) : static_cast<UINT_T>(~0UL);
}

}

/// Test unpacking a subarray of values to/from smaller buffers that are sized to exactly
/// fit the the input and output. 'in' is the original unpacked input, 'packed' is the
/// bit-packed data. The test copies 'num_in_values' packed values to a smaller temporary
/// buffer, then unpacks them to another temporary buffer. Both buffers are sized to the
/// minimum number of bytes required to fit the packed/unpacked data.
///
/// This is to test that we do not overrun either the input or output buffer for smaller
/// batch sizes.
template <typename UINT_T>
void UnpackSubset(const UINT_T* in, const uint8_t* packed, int num_in_values,
    int bit_width, bool aligned);

/// Test a packing/unpacking round-trip of the 'num_in_values' values in 'in',
/// packed with 'bit_width'. If 'aligned' is true, buffers for packed and unpacked data
/// are allocated at a 64-byte aligned address. Otherwise the buffers are misaligned
/// by 1 byte from a 64-byte aligned address.
template <typename UINT_T>
void PackUnpack(const UINT_T* in, int num_in_values, int bit_width, bool aligned) {
  LOG(INFO) << "num_in_values = " << num_in_values << " bit_width = " << bit_width
            << " aligned = " << aligned;

  // Mask out higher bits so that the values to pack are in range.
  const UINT_T mask = ComputeMask<UINT_T>(bit_width);
  const int misalignment = aligned ? 0 : 1;

  const int bytes_required = BitUtil::RoundUpNumBytes(bit_width * num_in_values);
  AlignedAllocation storage(bytes_required + misalignment);
  uint8_t* packed = storage.data() + misalignment;

  BitWriter writer(packed, bytes_required);
  if (bit_width > 0) {
    for (int i = 0; i < num_in_values; ++i) {
      ASSERT_TRUE(writer.PutValue(in[i] & mask, bit_width));
    }
  }
  writer.Flush();
  LOG(INFO) << "Wrote " << writer.bytes_written() << " bytes.";

  // Test unpacking all the values. Trying to unpack extra values should have the same
  // result because the input buffer size 'num_in_values' limits the number of values to
  // return.
  for (const int num_to_unpack : {num_in_values, num_in_values + 1, num_in_values + 77}) {
    LOG(INFO) << "Unpacking " << num_to_unpack;
    // Size buffer exactly so that ASAN can detect reads/writes that overrun the buffer.
    AlignedAllocation out_storage(num_to_unpack * sizeof(UINT_T) + misalignment);
    UINT_T* out = reinterpret_cast<UINT_T*>(out_storage.data() + misalignment);
    const auto result = BitPacking::UnpackValues<UINT_T>(
        bit_width, packed, writer.bytes_written(), num_to_unpack, out);
    ASSERT_EQ(packed + writer.bytes_written(), result.first)
        << "Unpacked different # of bytes from the # written";
    if (bit_width == 0) {
      // If no bits, we can get back as many as we ask for.
      ASSERT_EQ(num_to_unpack, result.second) << "Unpacked wrong # of values";
    } else if (bit_width < CHAR_BIT) {
      // We may get back some garbage values that we didn't actually pack if we
      // didn't use all of the trailing byte.
      const int max_packed_values = writer.bytes_written() * CHAR_BIT / bit_width;
      ASSERT_EQ(min(num_to_unpack, max_packed_values), result.second)
          << "Unpacked wrong # of values";
    } else {
      ASSERT_EQ(num_in_values, result.second) << "Unpacked wrong # of values";
    }

    for (int i = 0; i < num_in_values; ++i) {
      EXPECT_EQ(in[i] & mask, out[i]) << "Didn't get back input value " << i << "."
          << " Bit width: " << bit_width << ".";
    }
  }
  UnpackSubset<UINT_T>(in, packed, num_in_values, bit_width, aligned);
}

template <typename UINT_T>
void UnpackSubset(const UINT_T* in, const uint8_t* packed, int num_in_values,
    int bit_width, bool aligned) {
  const int misalignment = aligned ? 0 : 1;
  for (int num_to_unpack : {1, 10, 77, num_in_values - 7}) {
    if (num_to_unpack < 0 || num_to_unpack > num_in_values) continue;

    // Size buffers exactly so that ASAN can detect buffer overruns.
    const int64_t bytes_to_read = BitUtil::RoundUpNumBytes(num_to_unpack * bit_width);
    AlignedAllocation packed_copy_storage(bytes_to_read + misalignment);
    uint8_t* packed_copy = packed_copy_storage.data() + misalignment;
    memcpy(packed_copy, packed, bytes_to_read);
    AlignedAllocation out_storage(num_to_unpack * sizeof(UINT_T) + misalignment);
    UINT_T* out = reinterpret_cast<UINT_T*>(out_storage.data() + misalignment);
    const auto result = BitPacking::UnpackValues<UINT_T>(
        bit_width, packed_copy, bytes_to_read, num_to_unpack, out);
    ASSERT_EQ(packed_copy + bytes_to_read, result.first) << "Read wrong # of bytes";
    ASSERT_EQ(num_to_unpack, result.second) << "Unpacked wrong # of values";

    for (int i = 0; i < num_to_unpack; ++i) {
      ASSERT_EQ(in[i] & ComputeMask<UINT_T>(bit_width), out[i])
          << "Didn't get back input value " << i;
    }
  }
}

template <typename INT_T>
std::vector<INT_T> GenerateRandomInput(int length, INT_T lower, INT_T higher) {
  std::vector<INT_T> in(length);
  mt19937 rng;
  RandTestUtil::SeedRng("BIT_PACKING_TEST_RANDOM_SEED", &rng);
  uniform_int_distribution<INT_T> dist(lower, higher);
  std::generate(in.begin(), in.end(), [&rng, &dist] { return dist(rng); });

  return in;
}

// Test various odd input lengths to exercise boundary cases for full and partial
// batches of 32.
std::vector<int> GetLengths() {
  vector<int> lengths{NUM_IN_VALUES, NUM_IN_VALUES - 1, NUM_IN_VALUES - 16,
      NUM_IN_VALUES - 19, NUM_IN_VALUES - 31};
  for (int i = 0; i < 32; ++i) {
    lengths.push_back(i);
  }

  return lengths;
}

template <typename UINT_T>
void RandomUnpackTest() {
  const std::vector<UINT_T> in = GenerateRandomInput<UINT_T>(NUM_IN_VALUES,
      std::numeric_limits<UINT_T>::min(), std::numeric_limits<UINT_T>::max());

  const std::vector<int> lengths = GetLengths();

  constexpr int MAX_BITWIDTH = BitPacking::MAX_BITWIDTH;
  const int max_bit_width = std::min<int>(MAX_BITWIDTH, sizeof(UINT_T) * CHAR_BIT);
  for (int bit_width = 0; bit_width <= max_bit_width; ++bit_width) {
    for (const int length : lengths) {
      // Test that unpacking to/from aligned and unaligned memory works.
      for (const bool aligned : {true, false}) {
        PackUnpack<UINT_T>(in.data(), length, bit_width, aligned);
      }
    }
  }
}

TEST(BitPackingTest, RandomUnpack8) {
  RandomUnpackTest<uint8_t>();
}

TEST(BitPackingTest, RandomUnpack16) {
  RandomUnpackTest<uint16_t>();
}

TEST(BitPackingTest, RandomUnpack32) {
  RandomUnpackTest<uint32_t>();
}

TEST(BitPackingTest, RandomUnpack64) {
  RandomUnpackTest<uint64_t>();
}

// This is not the full dictionary encoding, only a big bit-packed literal run, no RLE is
// used.
template <typename T>
std::pair<std::vector<T>, std::vector<uint8_t>>
DictEncode(const std::vector<T>& input, int bit_width) {
  // Create dictionary and indices.
  std::unordered_map<T, std::size_t> index_map;

  std::vector<T> dict;
  std::vector<uint64_t> indices;

  for (const T value : input) {
    auto it = index_map.find(value);
    if (it != index_map.end()) {
      indices.push_back(it->second);
    } else {
      const std::size_t next_index = dict.size();
      index_map[value] = next_index;
      dict.push_back(value);
      indices.push_back(next_index);
    }
  }

  // Bit pack the indices.
  const int bytes_required = BitUtil::RoundUpNumBytes(bit_width * input.size());
  std::vector<uint8_t> out_data(bytes_required);

  // We do not write data if we do not have any. Doing it could also lead to undefined
  // behaviour as out_data.data() may be nullptr and BitWriter uses memcpy internally, and
  // passing a null pointer to memcpy is undefined behaviour.
  if (bytes_required > 0) {
    BitWriter writer(out_data.data(), bytes_required);
    if (bit_width > 0) {
      for (const uint64_t index : indices) {
        EXPECT_TRUE(writer.PutValue(index, bit_width));
      }
    }
    writer.Flush();
  }

  return std::make_pair(dict, out_data);
}

template <typename T>
void ExpectEqualsWithStride(const T* expected, int num_values,
    const uint8_t* actual, int actual_length, int stride) {
  for (std::size_t i = 0; i < num_values; i++) {
    const T expected_value = expected[i];

    DCHECK_LE(i * stride + sizeof(T), actual_length);
    const T actual_value = *reinterpret_cast<const T*>(&actual[i * stride]);

    EXPECT_EQ(expected_value, actual_value);
  }
}

// This does not test the full dictionary decoding, only the unpacking of a single
// bit-packed literal run (no RLE).
template <typename UINT_T>
void RandomUnpackAndDecodeTest() {
  constexpr int MAX_BITWIDTH = BitPacking::MAX_BITWIDTH;
  const int max_bit_width = std::min<int>({MAX_BITWIDTH, sizeof(UINT_T) * 8,
      sizeof(uint32_t) * 8 /* dictionary indices are 32 bit values */});

  const std::vector<int> lengths = GetLengths();

  for (int bit_width = 0; bit_width <= max_bit_width; ++bit_width) {
    const UINT_T max_dict_size = bit_width == sizeof(UINT_T) * 8
        ? std::numeric_limits<UINT_T>::max() : (1UL << bit_width);

    const std::vector<UINT_T> input = GenerateRandomInput<UINT_T>(NUM_IN_VALUES, 0,
        max_dict_size - 1 /* inclusive range */);

    for (int length : lengths) {
      const std::vector<UINT_T> in_data(input.begin(), input.begin() + length);

      std::pair<std::vector<UINT_T>, std::vector<uint8_t>> dict_and_data
          = DictEncode(in_data, bit_width);
      std::vector<UINT_T>& dict = dict_and_data.first;
      const std::vector<uint8_t>& data = dict_and_data.second;

      const std::vector<int> strides = {sizeof(UINT_T), sizeof(UINT_T) + 5,
        2 * sizeof(UINT_T) + 5};

      for (int stride : strides) {
        bool decode_error = false;
        std::vector<uint8_t> out(in_data.size() * stride);

        std::pair<const uint8_t*, int64_t> res
            = BitPacking::UnpackAndDecodeValues<UINT_T>(bit_width, data.data(),
                data.size(), dict.data(), dict.size(), in_data.size(),
            reinterpret_cast<UINT_T*>(out.data()), stride, &decode_error);

        EXPECT_FALSE(decode_error);
        EXPECT_EQ(in_data.size(), res.second);
        ExpectEqualsWithStride<UINT_T>(in_data.data(), in_data.size(), out.data(),
            out.size(), stride);
      }
    }
  }
}

TEST(BitPackingTest, RandomUnpackAndDecode8) {
  RandomUnpackAndDecodeTest<uint8_t>();
}

TEST(BitPackingTest, RandomUnpackAndDecode16) {
  RandomUnpackAndDecodeTest<uint16_t>();
}

TEST(BitPackingTest, RandomUnpackAndDecode32) {
  RandomUnpackAndDecodeTest<uint32_t>();
}

TEST(BitPackingTest, RandomUnpackAndDecode64) {
  RandomUnpackAndDecodeTest<uint64_t>();
}

}