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
|
#pragma once
#include "bit_io.h"
#include <library/cpp/yt/memory/range.h>
#include <util/system/types.h>
#include <concepts>
namespace NYT {
////////////////////////////////////////////////////////////////////////////////
//
// Binary interpolative coding for a sorted, strictly increasing sequence of
// integers drawn from a known range [lo, hi]. The value domain is 32-bit: lo, hi
// and hence every value fit in ui32, independent of the element type T (which is
// merely the container's width).
//
// It recursively encodes the median element within the range implied by its
// position and its already-coded neighbors, so clustered sequences compress far
// below a flat log2 per element and no per-element headers are needed. Each
// element is stored with a truncated-binary (minimal) code, which spends the
// fractional part of log2(range) instead of rounding every element up to a whole
// bit.
//
// The bit stream is MSB-first (see bit_io.h).
//
////////////////////////////////////////////////////////////////////////////////
//! Encodes #values, which must be strictly increasing and all within [#lo, #hi],
//! with binary interpolative coding. An empty range emits nothing; the length is
//! not stored and must be conveyed out of band (e.g. as a varint prefix).
template <std::unsigned_integral T>
void InterpolativeEncode(TBitWriter* writer, TRange<T> values, ui32 lo, ui32 hi);
//! Decodes a sequence written by #InterpolativeEncode into #values, whose size
//! must equal the encoded element count. #lo and #hi must match the encoder.
template <std::unsigned_integral T>
void InterpolativeDecode(TBitReader* reader, TMutableRange<T> values, ui32 lo, ui32 hi);
//! An upper bound on the buffer size #InterpolativeEncode needs to encode #count
//! values over [#lo, #hi], including the slack the writer requires.
size_t GetInterpolativeMaxByteSize(int count, ui32 lo, ui32 hi);
////////////////////////////////////////////////////////////////////////////////
} // namespace NYT
#define INTERPOLATIVE_INL_H_
#include "interpolative-inl.h"
#undef INTERPOLATIVE_INL_H_
|
