Function ParseLeadingLEB128

cpp/src/arrow/util/bit_util.h:312–365

/// \see MaxLEB128ByteLenFor
template <typename Int>
constexpr int32_t ParseLeadingLEB128(const uint8_t* data, int32_t max_data_size,
                                     Int* out) {
  constexpr auto kMaxBytes = kMaxLEB128ByteLenFor<Int>;
  static_assert(kMaxBytes >= 1);
  constexpr uint8_t kLow7Mask = 0x7F;
  constexpr uint8_t kContinuationBit = 0x80;
  constexpr int32_t kSignBitCount = std::is_signed_v<Int> ? 1 : 0;
  // Number of bits allowed for encoding data on the last byte to avoid overflow
  constexpr uint8_t kHighBitCount = (8 * sizeof(Int) - kSignBitCount) % 7;
  // kHighBitCount least significant `0` bits and the rest with `1`
  constexpr uint8_t kHighForbiddenMask = ~((1 << kHighBitCount) - 1);

  // Iteratively building the value
  std::make_unsigned_t<Int> value = 0;

  // Read as many bytes as we could be for the given output.
  for (int32_t i = 0; i < kMaxBytes - 1; i++) {
    // We have not finished reading a valid LEB128, yet we run out of data
    if (ARROW_PREDICT_FALSE(i >= max_data_size)) {
      return 0;
    }

    // Read the byte and set its 7 LSB to in the final value
    const uint8_t byte = data[i];
    value |= static_cast<Int>(byte & kLow7Mask) << (7 * i);

    // Check for lack of continuation flag in MSB
    if ((byte & kContinuationBit) == 0) {
      *out = value;
      return i + 1;
    }
  }

  // Process the last index avoiding overflowing
  constexpr int32_t last = kMaxBytes - 1;

  // We have not finished reading a valid LEB128, yet we run out of data
  if (ARROW_PREDICT_FALSE(last >= max_data_size)) {
    return 0;
  }

  const uint8_t byte = data[last];

  // Need to check if there are bits that would overflow the output.
  // Also checks that there is no continuation.
  if (ARROW_PREDICT_FALSE((byte & kHighForbiddenMask) != 0)) {
    return 0;
  }

  // No longer need to mask since we ensured
  value |= static_cast<Int>(byte) << (7 * last);
  *out = value;
  return last + 1;
}
}  // namespace bit_util
}  // namespace arrow