src/common/header_enc_dec.cc

// Copyright 2019 Google LLC
//
// Licensed 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
//
//     https://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.
// -----------------------------------------------------------------------------
//
// Bitstream/chunk header reader and writer.
// It is based on https://en.wikipedia.org/wiki/LEB128#Unsigned_LEB128
// with the removed pessimization described at
// https://en.wikipedia.org/wiki/Variable-length_quantity#Removing_redundancy
//
// Author: Skal (pascal.massimino@gmail.com)

#include "src/common/header_enc_dec.h"

#include <cassert>
#include <cstdint>

#include "src/common/constants.h"
#include "src/utils/ans.h"
#include "src/utils/data_source.h"
#include "src/utils/utils.h"
#include "src/wp2/base.h"

namespace WP2 {

//------------------------------------------------------------------------------

static_assert(GetMaxVarIntLength(0, kMaxVarInt) == kMaxVarIntLength, "Error");

WP2Status TryReadVarInt(DataSource* const data_source, uint32_t min_value,
                        uint32_t max_value, uint32_t* const value) {
  assert(min_value <= max_value);
  *value = 0;
  uint32_t num_bytes = 0;
  uint32_t max_remaining_value = max_value - min_value;
  assert(max_remaining_value <= kMaxVarInt);
  bool read_next_byte = (max_remaining_value > 0);
  while (read_next_byte) {
    const uint32_t i = num_bytes++;         // Current byte index.
    assert(num_bytes <= kMaxVarIntLength);  // Otherwise 'max_value>kMaxVarInt'.
    const uint8_t* bytes;
    WP2_CHECK_OK(data_source->TryGetNext(num_bytes, &bytes),
                 WP2_STATUS_NOT_ENOUGH_DATA);

    // One bit is reserved to know if the next byte should be read, unless the
    // remaining value fits in this byte.
    read_next_byte = (max_remaining_value > 0xFF && (bytes[i] & 0x80));
    // If 'read_next_byte', at least 1 remains, meaning storing 0 is pointless,
    // so add 1 to the next byte. The following is equivalent to keeping 7 bits
    // of this byte and adding 1 to the next byte.
    *value += (uint32_t)bytes[i] << (7 * i);
    max_remaining_value >>= 7;
    if (read_next_byte) --max_remaining_value;
  }
  *value += min_value;
  WP2_CHECK_OK(*value <= max_value, WP2_STATUS_BITSTREAM_ERROR);
  data_source->MarkNumBytesAsRead(num_bytes);
  return WP2_STATUS_OK;
}

uint32_t WriteVarInt(uint32_t value, uint32_t min_value, uint32_t max_value,
                     uint8_t dst[]) {
  assert(min_value <= value && value <= max_value);
  value -= min_value;      // Get rid of 'min_value'.
  max_value -= min_value;  // Consider 'value' in [0:max_value].
  assert(max_value <= kMaxVarInt);

  uint32_t num_used_bytes = 0;
  if (max_value == 0) return num_used_bytes;
  while (value > 0x7F && max_value > 0xFF) {
    dst[num_used_bytes++] = (value & 0x7F) | 0x80;
    value >>= 7;
    --value;  // 'value' is known to be > 0, so avoid literally encoding a 0.
    max_value >>= 7;
    --max_value;
  }
  dst[num_used_bytes++] = value;
  return num_used_bytes;
}

//------------------------------------------------------------------------------

uint32_t BitUnpacker::ReadBits(uint32_t num_bits, WP2_OPT_LABEL) {
  const uint32_t value = ReadBitsInternal(num_bits);
  WP2Trace("%s: value=%u num_bits=%d", debug_prefix_, label, value, num_bits);
  return value;
}

int32_t BitUnpacker::ReadSBits(uint32_t num_bits, WP2_OPT_LABEL) {
  const int32_t value =
      (int32_t)ReadBitsInternal(num_bits) - (1 << (num_bits - 1));
  WP2Trace("%s: value=%d num_bits=%d (signed)", debug_prefix_, label, value,
           num_bits);
  return value;
}

uint32_t BitUnpacker::ReadVarUInt(uint32_t min_value, uint32_t max_value,
                                  WP2_OPT_LABEL) {
  assert(min_value <= max_value);
  if (status_ != WP2_STATUS_OK) return 0;
  if (min_value == max_value) {
    WP2Trace("%s: value=%u in [%u:%u]", debug_prefix_, label, min_value,
             min_value, max_value);
    return 0;
  }
  assert(bit_pos_ == 8);  // Not-aligned variable-length ints are not supported.
  uint32_t value;
  status_ = TryReadVarInt(data_source_, min_value, max_value, &value);
  WP2Trace("%s: value=%u in [%u:%u]", debug_prefix_, label, value, min_value,
           max_value);
  // No need to update 'byte_' or 'bit_pos_' because whole bytes were read.
  return (status_ == WP2_STATUS_OK) ? value : 0;
}

Rectangle BitUnpacker::ReadRect(uint32_t canvas_width, uint32_t canvas_height,
                                WP2_OPT_LABEL) {
  assert(canvas_width > 0 && canvas_height > 0);
  // Read reversed width and height first, as these tend to be near 'canvas_*'.
  Rectangle rect;
  rect.width = canvas_width - ReadVarUInt(0, canvas_width - 1, label);
  rect.height = canvas_height - ReadVarUInt(0, canvas_height - 1, label);
  rect.x = ReadVarUInt(0, canvas_width - rect.width, label);
  rect.y = ReadVarUInt(0, canvas_height - rect.height, label);
  return rect;
}

bool BitUnpacker::Pad() {
  const uint32_t bits_to_pad = bit_pos_ & 7;
  if (bits_to_pad == 0) return true;
  return (ReadBits(8 - bits_to_pad, "padding") == 0);
}

bool BitUnpacker::Prefetch(uint32_t num_bits) {
  if (status_ != WP2_STATUS_OK) return false;
  const uint8_t* unused;
  return data_source_->TryGetNext(GetMinNumBytes(num_bits),
                                  /*data_pointer=*/&unused);
}

uint32_t BitUnpacker::GetMinNumBytes(uint32_t num_bits) const {
  assert(bit_pos_ > 0 && bit_pos_ <= 8);
  // (8 - bit_pos_) is the number of not-yet-used bits in 'byte_'.
  // Number of new bytes to read in order to have at least 'num_bits':
  //   num_bytes_to_read = ceil((num_bits - (8 - bit_pos_)) / 8)
  return (bit_pos_ + num_bits - 1) >> 3;
}

uint32_t BitUnpacker::ReadBitsInternal(uint32_t num_bits) {
  assert(num_bits <= 24);
  if (status_ != WP2_STATUS_OK || num_bits == 0) return 0;

  const uint32_t num_bytes_to_read = GetMinNumBytes(num_bits);
  const uint8_t* bytes;
  if (!data_source_->TryReadNext(num_bytes_to_read, &bytes)) {
    status_ = WP2_STATUS_NOT_ENOUGH_DATA;
    return 0;
  }

  // Concatenate all bytes containing at least some of the 'num_bits'.
  uint32_t value = byte_ >> bit_pos_;  // Retrieve unused bits, if any.
  uint32_t shift = 8 - bit_pos_;  // Next bits are inserted as most significant.
  for (uint32_t i = 0; i < num_bytes_to_read; ++i, shift += 8) {
    value |= (uint32_t)bytes[i] << shift;
    byte_ = bytes[i];  // Remember last read byte.
  }
  value &= ((1u << num_bits) - 1u);      // Remove the unrelated bits.
  bit_pos_ = (bit_pos_ + num_bits) & 7;  // Remember the used bits of 'byte_'.
  if (bit_pos_ == 0) bit_pos_ = 8;  // If so, set the whole 'byte_' as used.
  return value;
}

//------------------------------------------------------------------------------

void BitPacker::PutBits(uint32_t value, uint32_t num_bits, WP2_OPT_LABEL) {
  WP2Trace("%s: value=%u num_bits=%u", debug_prefix_, label, value, num_bits);
  PutBitsInternal(value, num_bits);
}

void BitPacker::PutSBits(int32_t value, uint32_t num_bits, WP2_OPT_LABEL) {
  const int32_t max_abs_value = (1 << (num_bits - 1));
  assert(value >= -max_abs_value && value < max_abs_value);
  WP2Trace("%s: value=%d num_bits=%u (signed)", debug_prefix_, label, value,
           num_bits);
  PutBitsInternal((uint32_t)(value + max_abs_value), num_bits);
}

void BitPacker::PutVarUInt(uint32_t value, uint32_t min_value,
                           uint32_t max_value, WP2_OPT_LABEL) {
  assert(min_value <= value && value <= max_value);
  // Make sure any 'value' would fit in 'buf_'.
  if (((max_pos_ - bit_pos_ + 7) >> 3) <
      GetMaxVarIntLength(min_value, max_value)) {
    error_ = true;
  } else {
    assert((bit_pos_ & 7) == 0);
    WP2Trace("%s: value=%u in [%u:%u]", debug_prefix_, label, value, min_value,
             max_value);
    const uint32_t num_written_bytes =
        WriteVarInt(value, min_value, max_value, buf_ + (bit_pos_ >> 3));
    bit_pos_ += num_written_bytes << 3;
  }
}

void BitPacker::PutRect(const Rectangle& rect, uint32_t canvas_width,
                        uint32_t canvas_height, WP2_OPT_LABEL) {
  assert(rect.width > 0 && rect.height > 0);
  assert(rect.x + rect.width <= canvas_width);
  assert(rect.y + rect.height <= canvas_height);
  // Put reversed width and height first, as these tend to be near 'canvas_*'.
  PutVarUInt(canvas_width - rect.width, 0, canvas_width - 1, label);
  PutVarUInt(canvas_height - rect.height, 0, canvas_height - 1, label);
  PutVarUInt(rect.x, 0, canvas_width - rect.width, label);
  PutVarUInt(rect.y, 0, canvas_height - rect.height, label);
}

void BitPacker::Pad() {
  const uint32_t bits_to_pad = bit_pos_ & 7;
  if (bits_to_pad == 0) return;
  PutBits(/*value=*/0, 8 - bits_to_pad, "padding");
}

void BitPacker::PutBitsInternal(uint32_t value, uint32_t num_bits) {
  assert(num_bits <= 24);
  assert(value < (1u << num_bits));

  const uint32_t shift = bit_pos_ & 7;
  uint32_t pos = bit_pos_ >> 3;
  bit_pos_ += num_bits;
  if (bit_pos_ > max_pos_) {  // Make sure 'value' fits in 'buf_'.
    error_ = true;
    return;
  }
  value <<= shift;
  for (uint32_t n = 0; n < num_bits + shift; n += 8) {
    buf_[pos++] |= value & 0xff;
    value >>= 8;
  }
}

//------------------------------------------------------------------------------

}  // namespace WP2