include/swift/Basic/Varint.h

//===--- Varint.h - Variable length integer encoding ------------*- C++ -*-===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
///
/// \file Varint.h
/// Defines transformations of integral types to/from variable length
///        7-bit encoding.
//===----------------------------------------------------------------------===//

#include <numeric>
#include <type_traits>

#include "llvm/ADT/SmallVector.h"

#ifndef SWIFT_BASIC_VARINT_H
#define SWIFT_BASIC_VARINT_H

namespace swift {
namespace Varint {

/// Encode an unsigned integral type to a variable length 7-bit-encoded sequence
/// of bytes.
template <typename T>
llvm::SmallVector<uint8_t, 10> encode(
  typename std::enable_if<
    std::is_integral<T>::value && std::is_unsigned<T>::value, T
  >::type i
) {
  llvm::SmallVector<uint8_t, 10> bytes;
  do {
    uint8_t b = i & 0x7F;
    i >>= 7;
    if (i)
      b |= 0x80;
    bytes.push_back(b);
  } while (i);
  return bytes;
}

/// Encode a signed integral type to a variable length 7-bit-encoded sequence of
/// bytes.
///
/// This transforms the signed value into an unsigned value and delegates
/// to the unsigned version of `encode`.
template <typename T>
llvm::SmallVector<uint8_t, 10> encode(
  typename std::enable_if<
    std::is_integral<T>::value && std::is_signed<T>::value, T
  >::type i
) {
  // Zig-zag encode the signed integer into the unsigned integer type.
  // Negative numbers are encoded as unsigned odd numbers in the
  // unsigned type, positive numbers are even. This prioritizes the
  // smaller numbers around zero, while making it compatible with
  // 7-bit encoding:
  // -3 -> 5
  // -2 -> 3
  // -1 -> 1
  //  0 -> 0
  //  1 -> 2
  //  2 -> 4
  //  3 -> 6
  typename std::make_unsigned<T>::type z = i < 0 ? ~(i << 1) : (i << 1);
  return encode<decltype(z)>(z);
}

/// Decode a variable length 7-bit encoded sequence of bytes to an unsigned
/// integer type.
template <typename T>
typename std::enable_if<
  std::is_integral<T>::value && std::is_unsigned<T>::value, T
>::type
decode(const uint8_t *bytes) {
  size_t i = 0;
  size_t shift = 0;
  T decoded = 0;
  do {
    decoded |= T(bytes[i] & 0x7F) << shift;
    shift += 7;
  } while (bytes[i++] & 0x80);
  return decoded;
}

/// Decode a variable length 7-bit-encoded sequence of bytes to a signed integer
/// type.
///
/// This delegates to the unsigned version of `decode` and transforms the
/// value back into its signed version.
template <typename T>
typename std::enable_if<
  std::is_integral<T>::value && std::is_signed<T>::value, T
>::type
decode(const uint8_t *bytes) {
  auto decoded = decode<typename std::make_unsigned<T>::type>(bytes);
  // Zig-zag decode back into the signed integer type.
  return decoded & 1 ? ~(decoded >> 1) : (decoded >> 1);
}

} // end namespace Varint
} // end namespace swift

#endif // SWIFT_BASIC_VARINT_H