1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
|
#pragma once
#include "routing/routing_exceptions.hpp"
#include "coding/bit_streams.hpp"
#include "coding/elias_coder.hpp"
#include "base/assert.hpp"
#include "base/bits.hpp"
#include "base/checked_cast.hpp"
#include "base/macros.hpp"
#include <limits>
#include <type_traits>
namespace routing
{
template <typename T, typename Source>
T ReadDelta(BitReader<Source> & reader)
{
static_assert(std::is_unsigned<T>::value, "T should be an unsigned type");
uint64_t const decoded = coding::DeltaCoder::Decode(reader);
if (decoded > std::numeric_limits<T>::max())
{
MYTHROW(CorruptedDataException,
("Decoded value", decoded, "out of limit", std::numeric_limits<T>::max()));
}
return static_cast<T>(decoded);
}
template <typename T, typename Sink>
void WriteDelta(BitWriter<Sink> & writer, T value)
{
static_assert(std::is_unsigned<T>::value, "T should be an unsigned type");
ASSERT_GREATER(value, 0, ());
bool const success = coding::DeltaCoder::Encode(writer, static_cast<uint64_t>(value));
ASSERT(success, ());
UNUSED_VALUE(success);
}
template <typename T, typename Source>
T ReadGamma(BitReader<Source> & reader)
{
static_assert(std::is_unsigned<T>::value, "T should be an unsigned type");
uint64_t const decoded = coding::GammaCoder::Decode(reader);
if (decoded > std::numeric_limits<T>::max())
{
MYTHROW(CorruptedDataException,
("Decoded value", decoded, "out of limit", std::numeric_limits<T>::max()));
}
return static_cast<T>(decoded);
}
template <typename T, typename Sink>
void WriteGamma(BitWriter<Sink> & writer, T value)
{
static_assert(std::is_unsigned<T>::value, "T should be an unsigned type");
ASSERT_GREATER(value, 0, ());
bool const success = coding::GammaCoder::Encode(writer, static_cast<uint64_t>(value));
ASSERT(success, ());
UNUSED_VALUE(success);
}
// C++ standart says:
// if the value can't be represented in the destination unsigned type,
// the result is implementation-defined.
//
// ModularCast makes unambiguous conversion from unsigned value to signed.
// The resulting value is the least signed integer congruent to the source integer
// (modulo 2^n where n is the number of bits used to represent the unsigned type)
template <typename Unsigned, typename Signed = typename std::make_signed<Unsigned>::type>
Signed ModularCast(Unsigned value)
{
static_assert(std::is_unsigned<Unsigned>::value, "T should be an unsigned type");
if (value <= static_cast<Unsigned>(std::numeric_limits<Signed>::max()))
return static_cast<Signed>(value);
auto constexpr minSignedT = std::numeric_limits<Signed>::min();
return static_cast<Signed>(value - static_cast<Unsigned>(minSignedT)) + minSignedT;
}
// Encodes current as delta compared with prev.
template <typename T, typename UnsignedT = typename std::make_unsigned<T>::type>
UnsignedT EncodeZigZagDelta(T prev, T current)
{
static_assert(std::is_integral<T>::value, "T should be an integral type");
using SignedT = typename std::make_signed<T>::type;
auto const unsignedPrev = static_cast<UnsignedT>(prev);
auto const unsignedCurrent = static_cast<UnsignedT>(current);
auto originalDelta = ModularCast(static_cast<UnsignedT>(unsignedCurrent - unsignedPrev));
static_assert(std::is_same<decltype(originalDelta), SignedT>::value,
"It's expected that ModuleCast returns SignedT");
auto encodedDelta = bits::ZigZagEncode(originalDelta);
static_assert(std::is_same<decltype(encodedDelta), UnsignedT>::value,
"It's expected that bits::ZigZagEncode returns UnsignedT");
return encodedDelta;
}
// Reverse function for EncodeZigZagDelta.
template <typename T, typename UnsignedT = typename std::make_unsigned<T>::type>
T DecodeZigZagDelta(T prev, UnsignedT delta)
{
static_assert(std::is_integral<T>::value, "T should be an integral type");
using SignedT = typename std::make_signed<T>::type;
auto decoded = bits::ZigZagDecode(delta);
static_assert(std::is_same<decltype(decoded), SignedT>::value,
"It's expected that bits::ZigZagDecode returns SignedT");
return prev + static_cast<T>(decoded);
}
} // namespace routing
|
