Add bit I/O and binary interpolative coding to library/cpp/yt/coding

### `bit_io.h`
MSB-first bit-stream writer/reader (`TBitWriter` / `TBitReader`) over a caller-owned buffer. The writer flushes whole 32-bit words via the unaligned-store API; the reader assumes a few bytes of over-read slack.

### `interpolative.h`
- **Truncated-binary (minimal) code** — the entropy-optimal integer code for a uniform value in `[0, rangeSize)`.
- **Binary interpolative coding** — `InterpolativeEncode` / `InterpolativeDecode` for sorted, strictly increasing integer sequences over a known range `[lo, hi]`. It recursively codes the median of each subrange, compressing clustered sequences well below a flat `log2` per element with no per-element headers. Length is conveyed out of band (e.g. via the existing `varint`).
commit_hash:8baf84444b8cf8e8a6e32776b4ff48582187ac2b

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()