bend-kit-bits Releases (2): 0.1.0.1 0xeffdf0a43b147136e34069ec484dac5e indexed https://jend.leeeet.dev/files.txt?path=bend-kit-bits@0.1.0.1 0.1.0.0 0xa5b0f53eaf9c9d7c9694e326ca453a91 unindexed https://jend.leeeet.dev/files.txt?path=bend-kit-bits@0.1.0.0 Definitions (55): Bits.mask (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=mask) def mask(+n: U32) -> U32: Bits.win.lsb.join (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=win.lsb.join) def win.lsb.join(+s: U32, +lo: U32, r: Array & U32) -> Array & U32: Bits.win.msb.join (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=win.msb.join) def win.msb.join(+s: U32, +lo: U32, r: Array & U32) -> Array & U32: Bits.win.lsb.at (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=win.lsb.at) def win.lsb.at(+p: U32, r: Array & U32) -> Array & U32: Bits.win.msb.at (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=win.msb.at) def win.msb.at(+p: U32, r: Array & U32) -> Array & U32: Bits.win (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=win) # The 32 stream bits from bit p, in stream order: first bit lowest LSB-first, highest MSB-first. # Bits past the buffer's last word wrap to its first, so callers mask what lies past the end. def win(msb: Bool, a: Array, +p: U32) -> Array & U32: Bits.field (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=field) # The first n (at most 32) bits of a window as a number, first stream bit most significant MSB-first. def field(+msb: Bool, +n: U32, +w: U32) -> U32: Bits.Reader (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=Reader) # A reader owns the buffer of len bytes; pos is the next bit. type Reader is Type: Reader{len: U32, buf: Array, pos: U32} Bits.Reader.new (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=Reader.new) def Reader.new(b: Bytes.Bytes) -> Reader: Bits.Reader.finish (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=Reader.finish) # The buffer back, and the bit position. def Reader.finish(r: Reader) -> Bytes.Bytes & U32: Bits.Reader.left (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=Reader.left) def Reader.left(r: Reader) -> Reader & U32: Bits.read.got (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=read.got) def read.got(+msb: Bool, +len: U32, +pos: U32, +n: U32, r: Array & U32) -> Reader & Maybe<&2, U32>: Bits.read.if (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=read.if) def read.if(ok: Bool, +msb: Bool, +len: U32, buf: Array, +pos: U32, +n: U32) -> Reader & Maybe<&2, U32>: Bits.read (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=read) def read(+msb: Bool, r: Reader, +n: U32) -> Reader & Maybe<&2, U32>: Bits.Reader.lsb (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=Reader.lsb) # The next n bits (0 to 32) as a number, and the reader past them. None, with the reader # unchanged, when n > 32 or fewer than n bits are left. def Reader.lsb(r: Reader, +n: U32) -> Reader & Maybe<&2, U32>: Bits.Reader.msb (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=Reader.msb) def Reader.msb(r: Reader, +n: U32) -> Reader & Maybe<&2, U32>: Bits.peek.got (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=peek.got) # Bits past the end read as 0: the low avail bits stay LSB-first, the high ones MSB-first. def peek.got(+msb: Bool, +len: U32, +pos: U32, +n: U32, +avail: U32, r: Array & U32) -> Reader & U32: Bits.peek (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=peek) def peek(+msb: Bool, r: Reader, +n0: U32) -> Reader & U32: Bits.Reader.peek.lsb (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=Reader.peek.lsb) # The next n bits (at most 32) without moving. Bits past the end read as 0. def Reader.peek.lsb(r: Reader, +n: U32) -> Reader & U32: Bits.Reader.peek.msb (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=Reader.peek.msb) def Reader.peek.msb(r: Reader, +n: U32) -> Reader & U32: Bits.Reader.skip (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=Reader.skip) # Moves n bits on. False, with the reader unchanged, when fewer than n are left. def Reader.skip(r: Reader, +n: U32) -> Reader & Bool: Bits.Reader.align (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=Reader.align) # Moves to the next byte boundary, as a DEFLATE stored block or a JPEG marker needs. def Reader.align(r: Reader) -> Reader: Bits.Writer (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=Writer) # A writer's buf has 2^dep words, all 0 past bit pos. type Writer is Type: Writer{buf: Array, dep: U32, pos: U32} Bits.Writer.new (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=Writer.new) def Writer.new() -> Writer: Bits.room (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=room) # A write adds at most 32 bits, so one doubling always makes room. def room(full: Bool, w: Writer) -> Writer: Bits.or.of (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=or.of) def or.of(+k: U32, +x: U32, r: Array & U32) -> Array: Bits.or.if (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=or.if) def or.if(some: Bool, a: Array, +k: U32, +x: U32) -> Array: Bits.parts (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=parts) # The parts of an n-bit v that land in word k and word k + 1, as stored words. def parts(msb: Bool, +s: U32, +n: U32, +v: U32) -> U32 & U32: Bits.write.put (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=write.put) def write.put(+k: U32, x: U32 & U32, a: Array) -> Array: Bits.write.at (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=write.at) def write.at(+msb: Bool, w: Writer, +n: U32, +v: U32) -> Writer: Bits.write (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=write) def write(+msb: Bool, w: Writer, +n0: U32, +v: U32) -> Writer: Bits.Writer.lsb (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=Writer.lsb) # Appends the low n bits of v (n is cut to 32). LSB-first sends v's lowest bit first; # MSB-first sends bit n - 1 first. def Writer.lsb(w: Writer, +n: U32, +v: U32) -> Writer: Bits.Writer.msb (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=Writer.msb) def Writer.msb(w: Writer, +n: U32, +v: U32) -> Writer: Bits.Writer.align (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=Writer.align) # Pads with 0 bits to the next byte boundary. def Writer.align(w: Writer) -> Writer: Bits.Writer.finish (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=Writer.finish) # The bytes written; 0 bits fill the last byte. def Writer.finish(w: Writer) -> Bytes.Bytes: Bits.Huff (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=Huff) # A canonical Huffman table: entry i of 2^max is (sym << 5) | len for the code that the # first max stream bits i start with, or 0 when no code does. msb is the stream's bit order. # ponytail: one level of 2^max entries; a two-level table if building it dominates short blocks. type Huff is Type: Huff{msb: Bool, max: U32, table: Array} Bits.Code (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=Code) # One symbol and the length of its code. type Code is Data: Code{sym: U32, len: U32} Bits.lens.max (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=lens.max) def lens.max(xs: List<&2, Code>, +m: U32) -> U32: Bits.count.of (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=count.of) def count.of(+len: U32, r: Array & U32) -> Array: Bits.count.if (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=count.if) def count.if(zero: Bool, c: Array, +len: U32) -> Array: Bits.count (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=count) def count(xs: List<&2, Code>, c: Array) -> Array: Bits.next.go (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=next.go) # RFC 1951 §3.2.2: next[l] = (next[l-1] + count[l-1]) << 1. r holds count[l-1]; left counts # the codes of length l - 1 still free, and a negative left means the lengths over-subscribe. def next.go(k: Nat, +l: U32, +code: U32, +left: U32, +ok: Bool, n: Array, r: Array & U32) -> Array & Bool: Bits.fill (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=fill) def fill(f: Nat, t: Array, +i: U32, +step: U32, +e: U32) -> Array: Bits.rev (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=rev) def rev(k: Nat, +v: U32, +acc: U32) -> U32: Bits.assign.put (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=assign.put) # MSB-first, a code fills a run of consecutive entries; LSB-first, its bits reversed fill every 2^len-th. def assign.put(+msb: Bool, +max: U32, +sym: U32, +len: U32, r: Array & U32, t: Array) -> Array & Array: Bits.assign.one (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=assign.one) def assign.one(zero: Bool, +msb: Bool, +max: U32, +sym: U32, +len: U32, st: Array & Array) -> Array & Array: Bits.assign (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=assign) def assign(xs: List<&2, Code>, +msb: Bool, +max: U32, st: Array & Array) -> Array: Bits.build.next (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=build.next) def build.next(+msb: Bool, +max: U32, xs: List<&2, Code>, r: Array & Bool) -> Maybe<&1, Huff>: Bits.build.short (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=build.short) def build.short(ok: Bool, +msb: Bool, +max: U32, +xs: List<&2, Code>) -> Maybe<&1, Huff>: Bits.Huff.from_codes (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=Huff.from_codes) # A table from codes. Codes go shortest first, ties in list order; length 0 means no code. # None when a length exceeds 16 or the lengths over-subscribe. An incomplete set is allowed, # and decode answers None for its unused codes. Symbols must be below 2^27. def Huff.from_codes(+msb: Bool, +xs: List<&2, Code>) -> Maybe<&1, Huff>: Bits.codes (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=codes) def codes(xs: List<&2, U32>, +i: U32) -> List<&2, Code>: Bits.Huff.from_lens (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=Huff.from_lens) # Symbol i has length lens[i], as DEFLATE sends them (RFC 1951 §3.2.2). def Huff.from_lens(+msb: Bool, +lens: List<&2, U32>) -> Maybe<&1, Huff>: Bits.decode.hit (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=decode.hit) # Bits past the end may be garbage in w: a code's entry repeats over every suffix, so only # its own len bits pick it, and len <= left keeps them inside the stream. def decode.hit(+msb: Bool, +max: U32, +len: U32, +pos: U32, +left: U32, buf: Array, r: Array & U32) -> Huff & Reader & Maybe<&2, U32>: Bits.decode.look (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=decode.look) def decode.look(+msb: Bool, +max: U32, +len: U32, +pos: U32, t: Array, r: Array & U32) -> Huff & Reader & Maybe<&2, U32>: Bits.Huff.decode (https://jend.leeeet.dev/definition.txt?path=bend-kit-bits@0.1.0.1/bits.bend&name=Huff.decode) # One symbol, and the reader past its code. None, with the reader unchanged, when the next # bits start no code or the input ends inside one. def Huff.decode(h: Huff, r: Reader) -> Huff & Reader & Maybe<&2, U32>: