folly/folly/Varint.h

/*
 * Copyright (c) Meta Platforms, Inc. and affiliates.
 *
 * 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
 *
 *     http://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.
 */

#pragma once

#include <type_traits>

#include <folly/Conv.h>
#include <folly/Expected.h>
#include <folly/Likely.h>
#include <folly/Portability.h>
#include <folly/Range.h>

namespace folly {

/**
 * Variable-length integer encoding, using a little-endian, base-128
 * representation.
 *
 * The MSb is set on all bytes except the last.
 *
 * Details:
 * https://developers.google.com/protocol-buffers/docs/encoding#varints
 *
 * If you want to encode multiple values, GroupVarint (in GroupVarint.h)
 * is faster and likely smaller.
 */

/**
 * Maximum length (in bytes) of the varint encoding of a 32-bit value.
 */
constexpr size_t kMaxVarintLength32 = …;

/**
 * Maximum length (in bytes) of the varint encoding of a 64-bit value.
 */
constexpr size_t kMaxVarintLength64 = …;

/**
 * Encode a value in the given buffer, returning the number of bytes used
 * for encoding.
 * buf must have enough space to represent the value (at least
 * kMaxVarintLength64 bytes to encode arbitrary 64-bit values)
 */
size_t encodeVarint(uint64_t val, uint8_t* buf);

/**
 * Determine the number of bytes needed to represent "val".
 * 32-bit values need at most 5 bytes.
 * 64-bit values need at most 10 bytes.
 */
int encodeVarintSize(uint64_t val);

/**
 * Decode a value from a given buffer, advances data past the returned value.
 * Throws on error.
 */
template <class T>
uint64_t decodeVarint(Range<T*>& data);

enum class DecodeVarintError { … };

/**
 * A variant of decodeVarint() that does not throw on error. Useful in contexts
 * where only part of a serialized varint may be attempted to be decoded, e.g.,
 * when a serialized varint arrives on the boundary of a network packet.
 */
template <class T>
Expected<uint64_t, DecodeVarintError> tryDecodeVarint(Range<T*>& data);

/**
 * ZigZag encoding that maps signed integers with a small absolute value
 * to unsigned integers with a small (positive) values. Without this,
 * encoding negative values using Varint would use up 9 or 10 bytes.
 *
 * if x >= 0, encodeZigZag(x) == 2*x
 * if x <  0, encodeZigZag(x) == -2*x - 1
 */

inline uint64_t encodeZigZag(int64_t val) { … }

inline int64_t decodeZigZag(uint64_t val) { … }

// Implementation below

inline size_t encodeVarint(uint64_t val, uint8_t* buf) { … }

inline int encodeVarintSize(uint64_t val) { … }

template <class T>
inline uint64_t decodeVarint(Range<T*>& data) { … }

template <class T>
inline Expected<uint64_t, DecodeVarintError> tryDecodeVarint(Range<T*>& data) { … }

} // namespace folly