From bedbabe6038ff3387ea48584da3e274e837551ff Mon Sep 17 00:00:00 2001
From: babenko <babenko@yandex-team.com>
Date: Sun, 12 Jul 2026 18:08:01 +0300
Subject: Add bit I/O and binary interpolative coding to library/cpp/yt/coding
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

### `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
---
 library/cpp/yt/coding/interpolative.h | 52 +++++++++++++++++++++++++++++++++++
 1 file changed, 52 insertions(+)
 create mode 100644 library/cpp/yt/coding/interpolative.h

(limited to 'library/cpp/yt/coding/interpolative.h')

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_
-- 
cgit v1.3