Program Listing for File varint.h

↰ Return to documentation for file (liberate/serialization/varint.h)

/*
 * This file is part of liberate.
 *
 * Author(s): Jens Finkhaeuser <jens@finkhaeuser.de>
 *
 * Copyright (c) 2020-2021 Jens Finkhaeuser.
 * Copyright (c) 2022 Interpeer gUG (haftungsbeschränkt)
 *
 * SPDX-License-Identifier: GPL-3.0-only
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
#ifndef LIBERATE_SERIALIZATION_VARINT_H
#define LIBERATE_SERIALIZATION_VARINT_H

#ifndef __cplusplus
#error You are trying to include a C++ only header file
#endif

#include <liberate.h>

#include <cstring>

#include <type_traits>

#include <limits>

#include <liberate/types/type_traits.h>
#include <liberate/types/varint.h>

namespace liberate::serialization {

namespace detail {

constexpr std::size_t ceil(double input)
{
  return (static_cast<double>(static_cast<std::size_t>(input)) == input)
    ? static_cast<std::size_t>(input)
    : static_cast<std::size_t>(input) + ((input > 0) ? 1 : 0);
}

} // namespace detail

constexpr std::size_t const VARINT_MAX_BUFSIZE = detail::ceil(
    double{sizeof(liberate::types::varint) * 8} / 7
);

inline std::size_t
sleb128_serialized_size(::liberate::types::varint const & value)
{
  using namespace liberate::types;
  using unsigned_base = std::make_unsigned<varint_base>::type;
  constexpr uint8_t mask{0x7f};
  constexpr uint8_t sign{0x40};
  constexpr varint_base sign_clamp = static_cast<varint_base>(~unsigned_base{0} << 57);

  bool negative = (value < 0);

  // We start with the least significant 7 bits, and consume buffer until it
  // runs out.
  size_t offset = 0;
  auto input = static_cast<varint_base>(value);

  do {
    uint8_t bits = static_cast<uint8_t>(input & mask);
    input >>= 7;
    if (negative) {
      input |= sign_clamp;
    }
    if ((input == 0 && (!(bits & sign)))
        || ((input == -1) && (bits & sign)))
    {
      break;
    }

    ++offset;
  } while (true);

  return offset + 1;
}


inline std::size_t
serialized_size(::liberate::types::varint const & value)
{
  return sleb128_serialized_size(value);
}


inline std::size_t
uleb128_serialized_size(::liberate::types::varint const & value)
{
  using namespace liberate::types;

  size_t offset = 0;
  auto input = static_cast<varint_base>(value);

  do {
    input >>= 7;
    ++offset;
  } while (input != 0);

  return offset;
}




template <
  typename outT,
  std::enable_if_t<liberate::types::is_8bit_type<outT>::value, int> = 0
>
std::size_t
sleb128_serialize_varint(outT * output, std::size_t output_length, ::liberate::types::varint const & value)
{
  if (!output || !output_length) {
    return 0;
  }

  using namespace liberate::types;
  using unsigned_base = std::make_unsigned<varint_base>::type;
  using unsigned_output = typename std::make_unsigned<outT>::type;
  constexpr unsigned_output more_bit{0x80};
  constexpr unsigned_output mask{0x7f};
  constexpr unsigned_output sign{0x40};
  constexpr varint_base sign_clamp = static_cast<varint_base>(~unsigned_base{0} << 57);

  bool negative = (value < 0);

  // We start with the least significant 7 bits, and consume buffer until it
  // runs out.
  size_t offset = 0;
  auto input = static_cast<varint_base>(value);

  do {
    if (offset >= output_length) {
      // Ran out of room
      return 0;
    }

    unsigned_output bits = static_cast<unsigned_output>(input & mask);
    input >>= 7;
    if (negative) {
      input |= sign_clamp;
    }
    if ((input == 0 && (!(bits & sign)))
        || ((input == -1) && (bits & sign)))
    {
      output[offset] = static_cast<outT>(bits);
      break;
    }

    output[offset] = static_cast<outT>(bits | more_bit);
    ++offset;
  } while (true);

  return offset + 1;
}


template <
  typename outT,
  std::enable_if_t<liberate::types::is_8bit_type<outT>::value, int> = 0
>
std::size_t
serialize_varint(outT * output, std::size_t output_length, ::liberate::types::varint const & value)
{
  return sleb128_serialize_varint(output, output_length, value);
}


template <
  typename outT,
  std::enable_if_t<liberate::types::is_8bit_type<outT>::value, int> = 0
>
std::size_t
uleb128_serialize_varint(outT * output, std::size_t output_length, ::liberate::types::varint const & value)
{
  if (!output || !output_length) {
    return 0;
  }

  using namespace liberate::types;
  using unsigned_output = typename std::make_unsigned<outT>::type;
  constexpr unsigned_output more_bit{0x80};
  constexpr unsigned_output mask{0x7f};

  size_t offset = 0;
  auto input = static_cast<varint_base>(value);

  do {
    if (offset >= output_length) {
      // Ran out of room
      return 0;
    }

    unsigned_output bits = static_cast<unsigned_output>(input & mask);
    input >>= 7;
    if (input != 0) {
      bits |= more_bit;
    }

    output[offset] = static_cast<outT>(bits);
    ++offset;
  } while (input != 0);

  return offset;
}



template <
  typename inT,
  std::enable_if_t<liberate::types::is_8bit_type<inT>::value, int> = 0
>
std::size_t
sleb128_deserialize_varint(::liberate::types::varint & value, inT const * input, std::size_t input_length)
{
  using varint_base = liberate::types::varint_base;

  if (!input || !input_length) {
    return 0;
  }

  using namespace liberate::types;
  using unsigned_base = std::make_unsigned<varint_base>::type;
  using unsigned_input = typename std::make_unsigned<inT>::type;
  constexpr unsigned_input more_bit{0x80};
  constexpr unsigned_input mask{0x7f};
  constexpr unsigned_input sign{0x40};

  varint_base val = 0;
  size_t shift = 0;
  size_t offset = 0;

  do {
    if (offset >= input_length) {
      // Ran out of data
      return 0;
    }

    unsigned_input tmp = static_cast<unsigned_input>(input[offset++]);
    val |= static_cast<varint_base>(tmp & mask) << shift;
    shift += 7;
    if (!(tmp & more_bit)) {
      if ((shift < 64) && (tmp & sign)) {
        val |= ~unsigned_base{0} << shift;
      }
      break;
    }
  } while (true);

  value = static_cast<liberate::types::varint>(val);
  return offset;
}


template <
  typename inT,
  std::enable_if_t<liberate::types::is_8bit_type<inT>::value, int> = 0
>
std::size_t
deserialize_varint(::liberate::types::varint & value, inT const * input, std::size_t input_length)
{
  return sleb128_deserialize_varint(value, input, input_length);
}


template <
  typename inT,
  std::enable_if_t<liberate::types::is_8bit_type<inT>::value, int> = 0
>
std::size_t
uleb128_deserialize_varint(::liberate::types::varint & value, inT const * input, std::size_t input_length)
{
  using varint_base = liberate::types::varint_base;

  if (!input || !input_length) {
    return 0;
  }

  using namespace liberate::types;
  using unsigned_base = std::make_unsigned<varint_base>::type;
  using unsigned_input = typename std::make_unsigned<inT>::type;
  constexpr unsigned_input more_bit{0x80};
  constexpr unsigned_input mask{0x7f};

  unsigned_base result = 0;
  size_t shift = 0;
  size_t offset = 0;

  while (true) {
    if (offset >= input_length) {
      return 0;
    }

    auto byte = input[offset];
    result |= static_cast<unsigned_base>(byte & mask) << shift;
    ++offset;

    if (!(byte & more_bit)) {
      break;
    }
    shift += 7;
  }

  value = static_cast<varint>(result);
  return offset;
}

} // namespace liberate::serialization

#endif // guard