# parquet.bitio > A module of parquet's API. Bit-level readers: little-endian bit packing and the RLE/bit-packed hybrid. Parquet packs small integers two ways, and both are here: * **bit packing** — values of a fixed bit width laid down least-significant bit first, running across byte boundaries. This is the packing used inside a hybrid run and inside a `DELTA_BINARY_PACKED` miniblock. (It is *not* the `BIT_PACKED` legacy level encoding, which packs most-significant bit first; that one has its own reader below.) * **the RLE/bit-packed hybrid** — a sequence of runs, each either a repeated value or a block of bit-packed values, introduced by a ULEB128 header. Definition levels, repetition levels, dictionary indices and `RLE`-encoded booleans are all this. Everything is bounds checked: a truncated buffer, a run that claims more values than remain, or a bit width above 64 raises rather than reading past the end of the span. ## Structs ### `BitReader` ```mojo struct BitReader[origin: ImmOrigin] ``` Reads little-endian bit-packed values out of a borrowed span. Implements: `Copyable`, `Movable` Fields: - `data: Span[UInt8, origin]` - `bit_pos: Int` #### `__init__` ```mojo def __init__(out self, data: Span[UInt8, origin]) ``` #### `byte_pos` ```mojo def byte_pos(self) -> Int ``` #### `align` ```mojo def align(mut self) ``` #### `get` ```mojo def get(mut self, width: Int) -> UInt64 ``` Read one value of `width` bits, least-significant bit first. ### `HybridRuns` ```mojo struct HybridRuns[origin: ImmOrigin] ``` An RLE/bit-packed hybrid stream, read a block at a time. `decode_hybrid_into` materialises the whole stream. A consumer that reads each value once and then throws it away — the dictionary gather — pays for that array twice, once written and once read straight back, and pays for the allocation under it. This hands the same values out in blocks of `HYBRID_BLOCK` into a scratch buffer the caller reuses. Every run header, bit width and length is validated exactly as `decode_hybrid_into` validates it, with the same errors. Implements: `Copyable`, `Movable` Fields: - `data: Span[UInt8, origin]` - `width: Int` - `pos: Int` - `left: Int`: Values still owed to the caller. - `run_left: Int`: Values still to come out of the run in progress. - `run_value: UInt64` - `run_packed: Bool` #### `__init__` ```mojo def __init__(out self, data: Span[UInt8, origin], width: Int, count: Int) ``` #### `next_block` ```mojo def next_block(mut self, mut scratch: List[UInt32]) -> Tuple[Int, Bool] ``` Decode the next values into `scratch[0 : n]`; return `(n, uniform)`. `n` is zero once every value asked for has been handed out. `uniform` says the whole block came out of one repeated run, so a consumer that has to validate the values can do it with one comparison instead of a scan. `scratch` must hold at least `HYBRID_BLOCK` values, and a block is that many — a multiple of eight, which is what lets a bit-packed run be taken a block at a time. Eight values of `width` bits are exactly `width` bytes, so a block boundary inside a run is still a byte boundary; only the very last block of the stream may be shorter, and nothing is read after it. ### `HybridDecoder` ```mojo struct HybridDecoder[origin: ImmOrigin] ``` The RLE / bit-packed hybrid used for levels, dictionary indices and `RLE` booleans. ```text run := bit-packed-run | rle-run bit-packed := rle-run := ``` Implements: `Copyable`, `Movable` Fields: - `data: Span[UInt8, origin]` - `pos: Int` - `width: Int` - `buffer: List[UInt64]` - `buf_pos: Int` - `value: UInt64` - `remaining: Int` - `is_packed: Bool` #### `__init__` ```mojo def __init__(out self, data: Span[UInt8, origin], width: Int) ``` #### `next` ```mojo def next(mut self) -> UInt64 ``` #### `take` ```mojo def take(mut self, count: Int, mut out: List[UInt64]) ``` Append the next `count` values. ## Functions ### `bit_width` ```mojo def bit_width(max_value: Int) -> Int ``` The number of bits needed to hold `max_value` (0 for 0). ### `unpack_lsb` ```mojo def unpack_lsb(data: Span[UInt8], start_byte: Int, width: Int, count: Int, mut out: List[UInt64]) -> Int ``` Append `count` little-endian bit-packed values; return the end byte. ### `unpack_lsb_into` ```mojo def unpack_lsb_into[dt: DType](data: Span[UInt8], start_byte: Int, width: Int, count: Int, mut out: List[Scalar[dt]], at: Int) -> Int ``` Unpack `count` little-endian bit-packed values of `width` bits into `out[at : at + count]`, which the caller has already sized. Returns the byte just past the run. The body of the run is read one *unaligned 64-bit window* per value — a load, a shift and a mask — which is what makes bit-packed levels and dictionary indices cheap. Only the last few values, whose window would reach past the end of the buffer, take the byte-at-a-time path. ### `levels_all_equal` ```mojo def levels_all_equal(data: Span[UInt8], width: Int, count: Int, value: Int) -> Bool ``` Is every one of the next `count` hybrid-encoded levels equal to `value`? Only run *headers* are read, so this is O(runs), not O(values). A bit-packed run answers `False` without being unpacked: a page whose levels are all the maximum is written as RLE runs by every writer in the wild, and that is the case worth the fast path. ### `decode_hybrid_into` ```mojo def decode_hybrid_into[dt: DType](data: Span[UInt8], width: Int, count: Int, mut out: List[Scalar[dt]], at: Int) ``` Decode `count` RLE/bit-packed hybrid values into `out[at : at + count]`, which the caller has already sized. Runs are handled whole — a repeated run is a fill, a bit-packed run is one `unpack_lsb_into` — so nothing goes through a per-value decoder. This is the hot path for dictionary indices. ### `decode_levels_into` ```mojo def decode_levels_into(data: Span[UInt8], width: Int, count: Int, max_level: Int, mut out: List[UInt16]) -> Int ``` Append `count` hybrid-encoded levels to `out`; return how many of them equal `max_level`. Runs are handled whole: a repeated run is a fill, a bit-packed run is one `unpack_lsb_into` call. Nothing goes through a per-value decoder. ### `unpack_msb` ```mojo def unpack_msb(data: Span[UInt8], start_byte: Int, width: Int, count: Int, mut out: List[UInt64]) -> Int ``` The legacy `BIT_PACKED` level encoding — most-significant bit first. ### `read_uleb128` ```mojo def read_uleb128(data: Span[UInt8], pos: Int) -> Tuple[UInt64, Int] ``` Decode a ULEB128 at `pos`; return the value and the byte after it. ### `zigzag_decode` ```mojo def zigzag_decode(u: UInt64) -> Int64 ``` Undo zigzag: 0,1,2,3,4 -> 0,-1,1,-2,2. ### `read_zigzag` ```mojo def read_zigzag(data: Span[UInt8], pos: Int) -> Tuple[Int64, Int] ``` Decode a zigzag ULEB128 at `pos`; return the value and the next byte. ## Aliases ### `HYBRID_BLOCK` ```mojo comptime HYBRID_BLOCK = 1024 ``` How many values `HybridRuns.next_block` hands out at a time. Four kilobytes of `UInt32` scratch, which stays in L1 between the decode and whatever consumes it. parquet-cpp's `ProcessValues` and arrow-rs's `RleDecoder::get_batch_with_dict` both use exactly 1024. It has to be a multiple of eight, for the reason `next_block` gives.