Function unpack_exact

cpp/src/arrow/util/bpacking_dispatch_internal.h:100–178

/// stop if it finds a byte aligned value start.
template <int kPackedBitWidth, bool kIsProlog, typename Uint>
ARROW_FORCE_INLINE int unpack_exact(const uint8_t* in, const uint8_t* in_end, Uint* out,
                                    int batch_size, int bit_offset) {
  static_assert(kPackedBitWidth > 0);

  // For the epilog we adapt the max spread since better alignment give shorter spreads
  ARROW_DCHECK(kIsProlog || bit_offset == 0);
  ARROW_DCHECK(bit_offset >= 0 && bit_offset < 8);
  constexpr int kMaxSpreadBytes = kIsProlog ? PackedMaxSpreadBytes(kPackedBitWidth)
                                            : PackedMaxSpreadBytes(kPackedBitWidth, 0);
  using buffer_uint = SpreadBufferUint<kMaxSpreadBytes>;
  constexpr int kBufferSize = sizeof(buffer_uint);
  // Due to misalignment, on large bit width, the spread can be larger than the maximum
  // size integer. For instance a 63 bit width misaligned packed integer can spread over 9
  // aligned bytes.
  constexpr bool kLarge = kBufferSize < kMaxSpreadBytes;
  constexpr buffer_uint kLowMask =
      bit_util::LeastSignificantBitMask<buffer_uint, true>(kPackedBitWidth);

  ARROW_DCHECK_GE(bit_offset, 0);
  ARROW_DCHECK_LE(bit_offset, 8);

  // Looping over values one by one
  const int start_bit_term = batch_size * kPackedBitWidth + bit_offset;
  int start_bit = bit_offset;
  while ((start_bit < start_bit_term) && (!kIsProlog || (start_bit % 8 != 0))) {
    const int start_byte = start_bit / 8;
    const int spread_bytes = ((start_bit + kPackedBitWidth - 1) / 8) - start_byte + 1;
    ARROW_DCHECK_LE(spread_bytes, kMaxSpreadBytes);
    ARROW_COMPILER_ASSUME(spread_bytes <= kMaxSpreadBytes);

    // Reading the bytes for the current value.
    buffer_uint buffer = 0;
    if (ARROW_PREDICT_TRUE(in + start_byte + kBufferSize < in_end)) {
      // Fast path we read the whole buffer. In all but few last reads (plural!) we will
      // always have enough bytes left in the buffer to avoid out-of-bounds reads. On top
      // of this, in Arrow, `unpack` is always called with `max_read_bytes` set, meaning
      // this will often be the *only* path taken.
      // We added this special case because `std::memcpy` without a compile time constant
      // was not inlined and optimized properly by the compiler, resulting to a function
      // call on each iteration.
      // This also handles the `kLarge` case detailed below.
      std::memcpy(&buffer, in + start_byte, kBufferSize);
    } else {
      // Slow path, we need to read exactly the correct number of bytes to avoid
      // out-of-bounds reads.
      if constexpr (kLarge) {
        // We read the max possible bytes in the first pass and handle the rest after.
        // Even though the worst spread does not happen on all iterations we can still
        // read all bytes because we will mask them.
        std::memcpy(&buffer, in + start_byte, std::min(kBufferSize, spread_bytes));
      } else {
        std::memcpy(&buffer, in + start_byte, spread_bytes);
      }
    }

    buffer = bit_util::FromLittleEndian(buffer);
    const int bit_offset = start_bit % 8;
    buffer >>= bit_offset;