ydb/library/cpp/yt/coding/unittests/interpolative_ut.cpp, branch main Mirror of YDB github repos https://code.mastervirt.ru/ydb/atom?h=main 2026-07-12T15:29:27Z Add bit I/O and binary interpolative coding to library/cpp/yt/coding 2026-07-12T15:29:27Z babenko babenko@yandex-team.com 2026-07-12T15:08:01Z urn:sha1:bedbabe6038ff3387ea48584da3e274e837551ff ### `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