summaryrefslogtreecommitdiffstats
path: root/library/cpp/yt
diff options
context:
space:
mode:
Diffstat (limited to 'library/cpp/yt')
-rw-r--r--library/cpp/yt/coding/bit_io-inl.h69
-rw-r--r--library/cpp/yt/coding/bit_io.h63
-rw-r--r--library/cpp/yt/coding/interpolative-inl.h182
-rw-r--r--library/cpp/yt/coding/interpolative.h52
-rw-r--r--library/cpp/yt/coding/unittests/bit_io_ut.cpp69
-rw-r--r--library/cpp/yt/coding/unittests/interpolative_ut.cpp221
-rw-r--r--library/cpp/yt/coding/unittests/ya.make2
-rw-r--r--library/cpp/yt/coding/ya.make2
8 files changed, 660 insertions, 0 deletions
diff --git a/library/cpp/yt/coding/bit_io-inl.h b/library/cpp/yt/coding/bit_io-inl.h
new file mode 100644
index 00000000000..89d69be6251
--- /dev/null
+++ b/library/cpp/yt/coding/bit_io-inl.h
@@ -0,0 +1,69 @@
+#ifndef BIT_IO_INL_H_
+#error "Direct inclusion of this file is not allowed, include bit_io.h"
+// For the sake of sane code completion.
+#include "bit_io.h"
+#endif
+
+#include <util/system/compiler.h>
+#include <util/system/unaligned_mem.h>
+
+namespace NYT {
+
+////////////////////////////////////////////////////////////////////////////////
+
+inline TBitWriter::TBitWriter(char* ptr)
+ : Ptr_(ptr)
+{ }
+
+Y_FORCE_INLINE void TBitWriter::WriteBits(ui32 value, int width)
+{
+ // Flush a whole 32-bit word at once (a single unaligned store) instead of
+ // looping over individual bytes with a data-dependent trip count.
+ Accumulator_ = (Accumulator_ << width) | value;
+ BitCount_ += width;
+ if (BitCount_ >= 32) {
+ BitCount_ -= 32;
+ ui32 word = __builtin_bswap32(static_cast<ui32>(Accumulator_ >> BitCount_));
+ WriteUnaligned<ui32>(Ptr_, word);
+ Ptr_ += sizeof(word);
+ }
+}
+
+inline char* TBitWriter::Finish()
+{
+ while (BitCount_ >= 8) {
+ BitCount_ -= 8;
+ *Ptr_++ = static_cast<char>((Accumulator_ >> BitCount_) & 0xff);
+ }
+ if (BitCount_ > 0) {
+ *Ptr_++ = static_cast<char>((Accumulator_ << (8 - BitCount_)) & 0xff);
+ BitCount_ = 0;
+ }
+ Accumulator_ = 0;
+ return Ptr_;
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+inline TBitReader::TBitReader(const char* ptr)
+ : Ptr_(reinterpret_cast<const ui8*>(ptr))
+{ }
+
+Y_FORCE_INLINE ui32 TBitReader::ReadBits(int width)
+{
+ while (BitCount_ < width) {
+ Accumulator_ = (Accumulator_ << 8) | *Ptr_++;
+ BitCount_ += 8;
+ }
+ BitCount_ -= width;
+ return static_cast<ui32>((Accumulator_ >> BitCount_) & ((1ull << width) - 1));
+}
+
+inline const char* TBitReader::Finish()
+{
+ return reinterpret_cast<const char*>(Ptr_);
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+} // namespace NYT
diff --git a/library/cpp/yt/coding/bit_io.h b/library/cpp/yt/coding/bit_io.h
new file mode 100644
index 00000000000..18900d69f85
--- /dev/null
+++ b/library/cpp/yt/coding/bit_io.h
@@ -0,0 +1,63 @@
+#pragma once
+
+#include <util/system/types.h>
+
+namespace NYT {
+
+////////////////////////////////////////////////////////////////////////////////
+
+//! MSB-first bit writer over a caller-owned buffer.
+/*!
+ * Bits are flushed to the buffer in 4-byte chunks, so the buffer must have room
+ * for up to 3 bytes beyond the last logically-written byte before #Finish is
+ * called.
+ */
+class TBitWriter
+{
+public:
+ explicit TBitWriter(char* ptr);
+
+ //! Appends the #width low bits of #value. Requires 0 <= #width <= 32 and
+ //! #value < 2^#width (for #width == 32 any value is accepted).
+ void WriteBits(ui32 value, int width);
+
+ //! Pads the last partial byte with zero low bits and returns the
+ //! one-past-end pointer.
+ char* Finish();
+
+private:
+ char* Ptr_;
+ ui64 Accumulator_ = 0;
+ int BitCount_ = 0;
+};
+
+//! MSB-first bit reader.
+/*!
+ * Reads bits written by #TBitWriter. Assumes up to 8 bytes past the logical end
+ * of the stream are safe to read.
+ */
+class TBitReader
+{
+public:
+ explicit TBitReader(const char* ptr);
+
+ //! Reads and returns #width bits (0 <= #width <= 32).
+ ui32 ReadBits(int width);
+
+ //! Returns the one-past-end pointer; the (< 8) buffered sub-byte bits, which
+ //! are the writer's zero padding, are dropped.
+ const char* Finish();
+
+private:
+ const ui8* Ptr_;
+ ui64 Accumulator_ = 0;
+ int BitCount_ = 0;
+};
+
+////////////////////////////////////////////////////////////////////////////////
+
+} // namespace NYT
+
+#define BIT_IO_INL_H_
+#include "bit_io-inl.h"
+#undef BIT_IO_INL_H_
diff --git a/library/cpp/yt/coding/interpolative-inl.h b/library/cpp/yt/coding/interpolative-inl.h
new file mode 100644
index 00000000000..5eadfdd483e
--- /dev/null
+++ b/library/cpp/yt/coding/interpolative-inl.h
@@ -0,0 +1,182 @@
+#ifndef INTERPOLATIVE_INL_H_
+#error "Direct inclusion of this file is not allowed, include interpolative.h"
+// For the sake of sane code completion.
+#include "interpolative.h"
+#endif
+
+#include "bit_io.h"
+
+#include <library/cpp/yt/assert/assert.h>
+
+#include <library/cpp/yt/memory/range.h>
+
+#include <util/system/compiler.h>
+
+#include <array>
+#include <bit>
+#include <concepts>
+
+namespace NYT {
+
+////////////////////////////////////////////////////////////////////////////////
+
+namespace NInterpolativeCodingDetail {
+
+// Truncated-binary (minimal) code for a value in [0, rangeSize): the first
+// Cutoff values take LowWidth bits, the rest one more.
+struct TTruncatedBinaryParams
+{
+ int LowWidth; // floor(log2(rangeSize))
+ ui32 Cutoff; // 2^(LowWidth + 1) - rangeSize
+};
+
+Y_FORCE_INLINE TTruncatedBinaryParams GetTruncatedBinaryParams(ui32 rangeSize)
+{
+ int lowWidth = std::bit_width(rangeSize) - 1;
+ ui32 cutoff = (2u << lowWidth) - rangeSize;
+ return {lowWidth, cutoff};
+}
+
+// Writes #value in [0, #rangeSize) with the entropy-optimal integer code for a
+// uniform value. rangeSize == 1 yields lowWidth 0 / cutoff 1 and emits a
+// zero-width code (a no-op), so the singleton case needs no branch.
+Y_FORCE_INLINE void WriteTruncatedBinary(TBitWriter* writer, ui32 value, ui32 rangeSize)
+{
+ auto [lowWidth, cutoff] = GetTruncatedBinaryParams(rangeSize);
+ // Branchless: the (value >= cutoff) predicate would mispredict on nearly
+ // every element, so fold it into the emitted codeword and width instead.
+ ui32 isLong = value >= cutoff ? 1 : 0;
+ writer->WriteBits(value + (cutoff & (0u - isLong)), lowWidth + static_cast<int>(isLong));
+}
+
+Y_FORCE_INLINE ui32 ReadTruncatedBinary(TBitReader* reader, ui32 rangeSize)
+{
+ auto [lowWidth, cutoff] = GetTruncatedBinaryParams(rangeSize);
+ ui32 high = reader->ReadBits(lowWidth);
+ if (high < cutoff) {
+ return high;
+ }
+ ui32 low = reader->ReadBits(1);
+ return ((high << 1) | low) - cutoff;
+}
+
+// A subrange [BeginIndex, EndIndex) of the value array together with the
+// inclusive value bounds [Lo, Hi] that its elements must fall in. The median
+// values[m] is the only array element touched per node, which matters because
+// the traversal walks a large sequence in a cache-unfriendly tree order.
+struct TInterpolativeFrame
+{
+ int BeginIndex;
+ int EndIndex;
+ ui32 Lo;
+ ui32 Hi;
+};
+
+} // namespace NInterpolativeCodingDetail
+
+////////////////////////////////////////////////////////////////////////////////
+
+inline size_t GetInterpolativeMaxByteSize(int count, ui32 lo, ui32 hi)
+{
+ // Each element is coded in at most ceil(log2(hi - lo + 1)) bits; the trailing
+ // word covers the writer's 4-byte flush store.
+ int maxBitWidth = std::bit_width(hi - lo);
+ return (static_cast<size_t>(count) * maxBitWidth + 7) / 8 + sizeof(ui32);
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+// Both traversals descend the left child in place and stack only the (non-empty)
+// right child, so the stack sees ~count/2 pushes instead of ~count. Left-first
+// order matches between encoder and decoder.
+template <std::unsigned_integral T>
+void InterpolativeEncode(TBitWriter* writer, TRange<T> values, ui32 lo, ui32 hi)
+{
+ using namespace NInterpolativeCodingDetail;
+
+ int count = std::ssize(values);
+ if (count == 0) {
+ return;
+ }
+
+ // Right children stack up along the leftmost path => depth <= ceil(log2(count)).
+ std::array<TInterpolativeFrame, 48> stack;
+ int top = 0;
+ int beginIndex = 0;
+ int endIndex = count;
+ ui32 l = lo;
+ ui32 h = hi;
+ for (;;) {
+ // beginIndex is invariant while descending left; only endIndex/l/h change.
+ while (beginIndex < endIndex) {
+ int half = (endIndex - beginIndex) / 2;
+ int m = beginIndex + half;
+ // The next descent step reads values[beginIndex + half/2]; prefetch it
+ // to hide the cache-scattered tree walk on large sequences.
+ Y_PREFETCH_READ(values.data() + beginIndex + (half >> 1), 0);
+ ui32 value = static_cast<ui32>(values[m]);
+ // rangeSize = (upperBound - lowerBound + 1) simplifies to this;
+ // lowerBound = l + half.
+ ui32 rangeSize = (h - l) - static_cast<ui32>(endIndex - beginIndex) + 2;
+ WriteTruncatedBinary(writer, value - l - static_cast<ui32>(half), rangeSize);
+ if (m + 1 < endIndex) {
+ YT_ASSERT(top < std::ssize(stack));
+ stack[top++] = {m + 1, endIndex, value + 1, h};
+ }
+ endIndex = m;
+ h = value - 1;
+ }
+ if (top == 0) {
+ break;
+ }
+ auto f = stack[--top];
+ beginIndex = f.BeginIndex;
+ endIndex = f.EndIndex;
+ l = f.Lo;
+ h = f.Hi;
+ }
+}
+
+template <std::unsigned_integral T>
+void InterpolativeDecode(TBitReader* reader, TMutableRange<T> values, ui32 lo, ui32 hi)
+{
+ using namespace NInterpolativeCodingDetail;
+
+ int count = std::ssize(values);
+ if (count == 0) {
+ return;
+ }
+
+ std::array<TInterpolativeFrame, 48> stack;
+ int top = 0;
+ int beginIndex = 0;
+ int endIndex = count;
+ ui32 l = lo;
+ ui32 h = hi;
+ for (;;) {
+ while (beginIndex < endIndex) {
+ int half = (endIndex - beginIndex) / 2;
+ int m = beginIndex + half;
+ ui32 rangeSize = (h - l) - static_cast<ui32>(endIndex - beginIndex) + 2;
+ ui32 value = l + static_cast<ui32>(half) + ReadTruncatedBinary(reader, rangeSize);
+ values[m] = static_cast<T>(value);
+ if (m + 1 < endIndex) {
+ stack[top++] = {m + 1, endIndex, value + 1, h};
+ }
+ endIndex = m;
+ h = value - 1;
+ }
+ if (top == 0) {
+ break;
+ }
+ auto f = stack[--top];
+ beginIndex = f.BeginIndex;
+ endIndex = f.EndIndex;
+ l = f.Lo;
+ h = f.Hi;
+ }
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+} // namespace NYT
diff --git a/library/cpp/yt/coding/interpolative.h b/library/cpp/yt/coding/interpolative.h
new file mode 100644
index 00000000000..88e415e754c
--- /dev/null
+++ b/library/cpp/yt/coding/interpolative.h
@@ -0,0 +1,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_
diff --git a/library/cpp/yt/coding/unittests/bit_io_ut.cpp b/library/cpp/yt/coding/unittests/bit_io_ut.cpp
new file mode 100644
index 00000000000..5d61b166f0a
--- /dev/null
+++ b/library/cpp/yt/coding/unittests/bit_io_ut.cpp
@@ -0,0 +1,69 @@
+#include <library/cpp/testing/gtest/gtest.h>
+
+#include <library/cpp/yt/coding/bit_io.h>
+
+#include <utility>
+#include <vector>
+
+namespace NYT {
+namespace {
+
+////////////////////////////////////////////////////////////////////////////////
+
+TEST(TBitIOTest, RoundTrip)
+{
+ std::vector<std::pair<ui32, int>> items = {
+ {0, 0}, {1, 1}, {0, 1}, {5, 3}, {0, 8}, {255, 8}, {12345, 14},
+ {0, 32}, {0xffffffffu, 32}, {0x12345, 17}, {7, 3}, {1u << 30, 31},
+ };
+ std::vector<char> buffer(256, 0);
+
+ TBitWriter writer(buffer.data());
+ for (auto [value, width] : items) {
+ writer.WriteBits(value, width);
+ }
+ writer.Finish();
+
+ TBitReader reader(buffer.data());
+ for (auto [value, width] : items) {
+ EXPECT_EQ(reader.ReadBits(width), value) << "width=" << width;
+ }
+}
+
+TEST(TBitIOTest, ZeroWidthIsNoop)
+{
+ std::vector<char> buffer(16, 0);
+ TBitWriter writer(buffer.data());
+ writer.WriteBits(0, 0);
+ writer.WriteBits(1, 1);
+ writer.WriteBits(0, 0);
+ char* end = writer.Finish();
+ EXPECT_EQ(end - buffer.data(), 1); // a single bit occupies one byte
+
+ TBitReader reader(buffer.data());
+ EXPECT_EQ(reader.ReadBits(0), 0u);
+ EXPECT_EQ(reader.ReadBits(1), 1u);
+ EXPECT_EQ(reader.ReadBits(0), 0u);
+}
+
+TEST(TBitIOTest, FlushBoundary)
+{
+ // Many 17-bit writes repeatedly cross the internal 32-bit flush boundary.
+ constexpr int Count = 1000;
+ std::vector<char> buffer(Count * 3 + 16, 0);
+ TBitWriter writer(buffer.data());
+ for (int i = 0; i < Count; ++i) {
+ writer.WriteBits(static_cast<ui32>(i) & 0x1ffff, 17);
+ }
+ writer.Finish();
+
+ TBitReader reader(buffer.data());
+ for (int i = 0; i < Count; ++i) {
+ EXPECT_EQ(reader.ReadBits(17), static_cast<ui32>(i) & 0x1ffff) << "i=" << i;
+ }
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+} // namespace
+} // namespace NYT
diff --git a/library/cpp/yt/coding/unittests/interpolative_ut.cpp b/library/cpp/yt/coding/unittests/interpolative_ut.cpp
new file mode 100644
index 00000000000..a63b12f6eac
--- /dev/null
+++ b/library/cpp/yt/coding/unittests/interpolative_ut.cpp
@@ -0,0 +1,221 @@
+#include <library/cpp/testing/gtest/gtest.h>
+
+#include <library/cpp/yt/coding/interpolative.h>
+#include <library/cpp/yt/coding/varint.h>
+
+#include <algorithm>
+#include <bit>
+#include <numeric>
+#include <random>
+#include <set>
+#include <vector>
+
+namespace NYT {
+namespace {
+
+////////////////////////////////////////////////////////////////////////////////
+// Truncated binary
+
+TEST(TTruncatedBinaryTest, Exhaustive)
+{
+ for (ui32 rangeSize = 1; rangeSize <= 2050; ++rangeSize) {
+ for (ui32 value = 0; value < rangeSize; ++value) {
+ std::vector<char> buffer(16, 0);
+ TBitWriter writer(buffer.data());
+ NInterpolativeCodingDetail::WriteTruncatedBinary(&writer, value, rangeSize);
+ writer.Finish();
+
+ TBitReader reader(buffer.data());
+ EXPECT_EQ(NInterpolativeCodingDetail::ReadTruncatedBinary(&reader, rangeSize), value)
+ << "rangeSize=" << rangeSize << " value=" << value;
+ }
+ }
+}
+
+TEST(TTruncatedBinaryTest, MinimalLength)
+{
+ // Every codeword is floor(log2(rangeSize)) or ceil(log2(rangeSize)) bits.
+ for (ui32 rangeSize = 1; rangeSize <= 1000; ++rangeSize) {
+ int lowWidth = std::bit_width(rangeSize) - 1;
+ for (ui32 value = 0; value < rangeSize; ++value) {
+ std::vector<char> buffer(16, 0);
+ TBitWriter writer(buffer.data());
+ NInterpolativeCodingDetail::WriteTruncatedBinary(&writer, value, rangeSize);
+ char* end = writer.Finish();
+
+ TBitReader reader(buffer.data());
+ NInterpolativeCodingDetail::ReadTruncatedBinary(&reader, rangeSize);
+ const char* readEnd = reader.Finish();
+ i64 bytes = end - buffer.data();
+ // Read must consume no more bytes than were written.
+ EXPECT_LE(readEnd - buffer.data(), bytes);
+ EXPECT_LE(bytes, (lowWidth + 1 + 7) / 8 + 1);
+ }
+ }
+}
+
+////////////////////////////////////////////////////////////////////////////////
+// Interpolative coding
+
+template <class T>
+std::vector<char> Encode(const std::vector<T>& values, ui32 lo, ui32 hi)
+{
+ std::vector<char> buffer(values.size() * sizeof(ui32) + 16, 0);
+ TBitWriter writer(buffer.data());
+ InterpolativeEncode(&writer, TRange(values), lo, hi);
+ char* end = writer.Finish();
+ buffer.resize(end - buffer.data());
+ return buffer;
+}
+
+template <class T>
+std::vector<T> Decode(std::vector<char> buffer, int count, ui32 lo, ui32 hi)
+{
+ buffer.resize(buffer.size() + 8, 0); // reader may over-read up to 8 bytes
+ std::vector<T> values(count);
+ TBitReader reader(buffer.data());
+ InterpolativeDecode(&reader, TMutableRange(values), lo, hi);
+ return values;
+}
+
+template <class T>
+void ExpectRoundTrip(const std::vector<T>& values, ui32 lo, ui32 hi)
+{
+ auto decoded = Decode<T>(Encode(values, lo, hi), std::ssize(values), lo, hi);
+ EXPECT_EQ(decoded, values);
+}
+
+TEST(TInterpolativeCodingTest, Empty)
+{
+ ExpectRoundTrip<ui32>({}, 0, 100);
+}
+
+TEST(TInterpolativeCodingTest, Single)
+{
+ ExpectRoundTrip<ui32>({0}, 0, 0);
+ ExpectRoundTrip<ui32>({42}, 0, 100);
+ ExpectRoundTrip<ui32>({100}, 0, 100);
+}
+
+TEST(TInterpolativeCodingTest, SmallCases)
+{
+ ExpectRoundTrip<ui32>({3, 7}, 0, 10);
+ ExpectRoundTrip<ui32>({0, 1, 2}, 0, 2); // full, zero bits
+ ExpectRoundTrip<ui32>({0, 5, 10}, 0, 10); // boundaries present
+ ExpectRoundTrip<ui32>({1, 2, 3, 4, 5}, 0, 6);
+}
+
+TEST(TInterpolativeCodingTest, FullRange)
+{
+ // Every value present => every range collapses to a singleton (zero bits).
+ std::vector<ui32> values(500);
+ std::iota(values.begin(), values.end(), 7);
+ auto encoded = Encode(values, 7, 506);
+ EXPECT_TRUE(encoded.empty());
+ EXPECT_EQ(Decode<ui32>(encoded, 500, 7, 506), values);
+}
+
+TEST(TInterpolativeCodingTest, RandomRoundTrip)
+{
+ std::mt19937 rng(12345);
+ for (int iteration = 0; iteration < 500; ++iteration) {
+ ui32 universe = 1 + rng() % 200'000;
+ int count = std::min<ui32>(universe, 1 + rng() % 2000);
+ std::set<ui32> unique;
+ std::uniform_int_distribution<ui32> dist(0, universe - 1);
+ while (std::ssize(unique) < count) {
+ unique.insert(dist(rng));
+ }
+ std::vector<ui32> values(unique.begin(), unique.end());
+ ExpectRoundTrip<ui32>(values, 0, universe - 1);
+ }
+}
+
+TEST(TInterpolativeCodingTest, NonZeroLowerBound)
+{
+ std::mt19937 rng(999);
+ for (int iteration = 0; iteration < 200; ++iteration) {
+ ui32 lo = rng() % 100'000;
+ ui32 span = 1 + rng() % 100'000;
+ ui32 hi = lo + span;
+ int count = std::min<ui32>(span + 1, 1 + rng() % 500);
+ std::set<ui32> unique;
+ std::uniform_int_distribution<ui32> dist(lo, hi);
+ while (std::ssize(unique) < count) {
+ unique.insert(dist(rng));
+ }
+ std::vector<ui32> values(unique.begin(), unique.end());
+ ExpectRoundTrip<ui32>(values, lo, hi);
+ }
+}
+
+TEST(TInterpolativeCodingTest, Ui64Values)
+{
+ std::vector<ui64> values = {0, 1, 100, 1000, 50'000, 200'000};
+ ExpectRoundTrip<ui64>(values, 0, 200'000);
+}
+
+TEST(TInterpolativeCodingTest, MaxByteSize)
+{
+ std::mt19937 rng(555);
+ for (int iteration = 0; iteration < 300; ++iteration) {
+ ui32 universe = 1 + rng() % 200'000;
+ int count = std::min<ui32>(universe, 1 + rng() % 1000);
+ std::set<ui32> unique;
+ std::uniform_int_distribution<ui32> dist(0, universe - 1);
+ while (std::ssize(unique) < count) {
+ unique.insert(dist(rng));
+ }
+ std::vector<ui32> values(unique.begin(), unique.end());
+
+ size_t bound = GetInterpolativeMaxByteSize(count, 0, universe - 1);
+ std::vector<char> buffer(bound, 0);
+ TBitWriter writer(buffer.data());
+ InterpolativeEncode(&writer, TRange(values), 0, universe - 1);
+ EXPECT_LE(static_cast<size_t>(writer.Finish() - buffer.data()), bound);
+ }
+}
+
+TEST(TInterpolativeCodingTest, MultipleListsInOneBuffer)
+{
+ // Mirrors real usage: each list is prefixed with a varint length and is
+ // byte-aligned, so lists can be concatenated and read back in sequence.
+ std::mt19937 rng(7);
+ ui32 hi = 199999;
+ std::vector<std::vector<ui32>> lists;
+ for (int listIndex = 0; listIndex < 50; ++listIndex) {
+ int count = 1 + rng() % 300;
+ std::set<ui32> unique;
+ std::uniform_int_distribution<ui32> dist(0, hi);
+ while (std::ssize(unique) < count) {
+ unique.insert(dist(rng));
+ }
+ lists.emplace_back(unique.begin(), unique.end());
+ }
+
+ std::vector<char> buffer(200'000, 0);
+ char* ptr = buffer.data();
+ for (const auto& list : lists) {
+ ptr += WriteVarUint32(ptr, static_cast<ui32>(list.size()));
+ TBitWriter writer(ptr);
+ InterpolativeEncode(&writer, TRange(list), 0, hi);
+ ptr = writer.Finish();
+ }
+
+ const char* readPtr = buffer.data();
+ for (const auto& list : lists) {
+ ui32 count;
+ readPtr += ReadVarUint32(readPtr, &count);
+ ASSERT_EQ(count, list.size());
+ std::vector<ui32> decoded(count);
+ TBitReader reader(readPtr);
+ InterpolativeDecode(&reader, TMutableRange(decoded), 0, hi);
+ readPtr = reader.Finish();
+ EXPECT_EQ(decoded, list);
+ }
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+} // namespace
+} // namespace NYT
diff --git a/library/cpp/yt/coding/unittests/ya.make b/library/cpp/yt/coding/unittests/ya.make
index ab94ee8796a..945e63ab506 100644
--- a/library/cpp/yt/coding/unittests/ya.make
+++ b/library/cpp/yt/coding/unittests/ya.make
@@ -3,6 +3,8 @@ GTEST()
INCLUDE(${ARCADIA_ROOT}/library/cpp/yt/ya_cpp.make.inc)
SRCS(
+ bit_io_ut.cpp
+ interpolative_ut.cpp
zig_zag_ut.cpp
varint_ut.cpp
)
diff --git a/library/cpp/yt/coding/ya.make b/library/cpp/yt/coding/ya.make
index 639d94e755c..e5ea301cf90 100644
--- a/library/cpp/yt/coding/ya.make
+++ b/library/cpp/yt/coding/ya.make
@@ -6,7 +6,9 @@ SRCS(
)
PEERDIR(
+ library/cpp/yt/assert
library/cpp/yt/exception
+ library/cpp/yt/memory
)
END()
generated by cgit v1.3 (git 2.53.0) at 2026-07-16 22:08:11 +0000