#gaato/deflate

moon add gaato/deflate

///|
test "compress and decompress a whole stream of each format" {
  let text = b"hello, hello, hello"
  assert_eq(@deflate.decompress(@deflate.compress(text)), text)
  assert_eq(@zlib.decompress(@zlib.compress(text, level=9)), text)
  assert_eq(@gzip.decompress(@gzip.compress(text, level=1)), text)
}

///|
test "decompress a whole stream of each format" {
  let raw = b"\xcb\x48\xcd\xc9\xc9\x07\x00"
  assert_eq(@deflate.decompress(raw), b"hello")
  let zlib = b"\x78\x9c\xcb\x48\xcd\xc9\xc9\x07\x00\x06\x2c\x02\x15"
  assert_eq(@zlib.decompress(zlib, max_output=16 * 1024 * 1024), b"hello")
  let gzip = b"\x1f\x8b\x08\x00\x00\x00\x00\x00\x02\x03\xcb\x48\xcd\xc9\xc9\x07\x00\x86\xa6\x10\x36\x05\x00\x00\x00"
  assert_eq(@gzip.decompress(gzip), b"hello")
}

///|
fn gunzip(chunks : Array[Bytes], sink : (BytesView) -> Unit) -> Unit raise {
  let decoder = @gzip.Decoder()
  let out = FixedArray::make(64 * 1024, b'\x00')
  for i, chunk in chunks {
    let mut input = chunk[:]
    for ;; {
      let status = decoder.step_into(input, out, end=i == chunks.length() - 1)
      input = input[decoder.last_consumed():]
      sink(Bytes::from_array(out[:decoder.last_produced()]))
      match status {
        Done => return
        NeedMoreInput => break
        NeedMoreOutput => ()
      }
    }
  }
}

///|
test "decode a gzip stream chunk by chunk" {
  let decoded = Buffer()
  gunzip(
    [
      b"\x1f\x8b\x08\x00\x00\x00\x00\x00", b"\x02\x03\xcb\x48\xcd\xc9\xc9\x07", b"\x00\x86\xa6\x10\x36\x05\x00\x00\x00",
    ],
    bytes => decoded.write_bytes(bytes.to_owned()),
  )
  assert_eq(decoded.to_bytes(), b"hello")
}

///|
/// Compresses each message of a connection into one zlib stream, as
/// Discord's `zlib-stream` does: every message ends in a sync flush. Returns
/// the bytes to send for each message.
fn compress_messages(messages : Array[Bytes]) -> Array[Bytes] {
  let encoder = @zlib.Encoder()
  let out = FixedArray::make(64 * 1024, b'\x00')
  messages.map(message => {
    let part = Buffer()
    let mut input = message[:]
    for ;; {
      let status = encoder.step_into(input, out, action=Flush)
      input = input[encoder.last_consumed():]
      part.write_bytes(Bytes::from_array(out[:encoder.last_produced()]))
      if status is NeedMoreInput {
        break
      }
    }
    part.to_bytes()
  })
}

///|
test "each message decodes on its own, without the end of the stream" {
  let messages = [b"{\"op\":10}", b"{\"op\":11}"]
  let decoder = @zlib.Decoder()
  let out = FixedArray::make(64 * 1024, b'\x00')
  for i, part in compress_messages(messages) {
    assert_true(part[part.length() - 4:] is [0x00, 0x00, 0xff, 0xff])
    assert_true(decoder.step_into(part, out, end=false) is NeedMoreInput)
    assert_eq(Bytes::from_array(out[:decoder.last_produced()]), messages[i])
  }
}

#gzip

///|
test "one member, then what follows it" {
  let gz = b"\x1f\x8b\x08\x00\x00\x00\x00\x00\x02\x03\xcb\x48\xcd\xc9\xc9\x07\x00\x86\xa6\x10\x36\x05\x00\x00\x00"
  let input = Bytes::from_array([..gz, 0, 0, 0, 0])
  let decoder = @gzip.Decoder(until=EndOfMember)
  let out = FixedArray::make(64, b'\x00')
  assert_true(decoder.step_into(input, out, end=true) is Done)
  assert_eq(Bytes::from_array(out[:decoder.last_produced()]), b"hello")
  assert_eq(input[decoder.last_consumed():], b"\x00\x00\x00\x00")
  let header = decoder.header().unwrap()
  assert_eq(header.os, b'\x03')
  assert_true(header.name is None)
}

///|
test "skip the header's fields" {
  // A member named "a.txt" (FNAME).
  let gz = b"\x1f\x8b\x08\x08\x00\x00\x00\x00\x00\x03a.txt\x00\xcb\x48\xcd\xc9\xc9\x07\x00\x86\xa6\x10\x36\x05\x00\x00\x00"
  let decoder = @gzip.Decoder(keep_header=false)
  let out = FixedArray::make(64, b'\x00')
  assert_true(decoder.step_into(gz, out, end=true) is Done)
  assert_eq(Bytes::from_array(out[:decoder.last_produced()]), b"hello")
  assert_true(decoder.header() is Some({ name: None, os: b'\x03', .. }))
  assert_eq(@gzip.decompress(gz), b"hello")
}

///|
test "a member with a name" {
  let header : @gzip.Header = {
    text: true,
    mtime: 1700000000,
    xfl: b'\x00',
    os: b'\x03',
    extra: None,
    name: Some(b"notes.txt"),
    comment: None,
  }
  assert_true(header.is_writable())
  let gz = @gzip.compress(b"hello", header~)
  let decoder = @gzip.Decoder()
  let out = FixedArray::make(64, b'\x00')
  assert_true(decoder.step_into(gz, out, end=true) is Done)
  assert_eq(decoder.header(), Some(header))
  // The default header: MTIME 0, XFL 0 at level 6, OS 255.
  assert_eq(
    @gzip.compress(b"hello")[:10],
    b"\x1f\x8b\x08\x00\x00\x00\x00\x00\x00\xff",
  )
}

#zlib

///|
test "a stream that needs a dictionary" {
  let dictionary = b"hello, dictionary"
  // zlib.deflateSync("hello", { dictionary }) in Node.
  let stream = b"\x78\xbb\x39\x4e\x06\x97\xcb\x00\x09\x00\x00\x06\x2c\x02\x15"
  let needed = try @zlib.decompress(stream) catch {
    CodecError(DictionaryRequired(id), _) => id
    _ => None
  } noraise {
    _ => None
  }
  assert_eq(needed, Some(@zlib.dictionary_id(dictionary)))
  assert_eq(@zlib.decompress(stream, dictionary~), b"hello")
}

///|
test "compress with a dictionary" {
  let dictionary = b"{\"op\":0,\"t\":\"MESSAGE_CREATE\",\"d\":{\"content\":\""
  let message = b"{\"op\":0,\"t\":\"MESSAGE_CREATE\",\"d\":{\"content\":\"hi\"}}"
  let stream = @zlib.compress(message, dictionary~)
  assert_eq(@zlib.decompress(stream, dictionary~), message)
  assert_true(stream.length() < @zlib.compress(message).length())
}

#A stream that does not end

• NeedMoreInput, with the frame consumed, is the answer to every frame. Everything the frame determines has been written, so after a frame that ends in 00 00 ff ff the whole message is out. The decoder does not know where messages end; the suffix does.
• NeedMoreOutput: the slice is full. Call again with the rest of the frame, frame[last_consumed():].
• Done: the stream ended, which a gateway stream never does. until=EndOfMember makes the decoder report this at once; under the default, it would wait for what follows and raise TrailingData on the next frame.

///|
/// Inflates the frames of one connection, and returns its messages.
fn inflate_messages(frames : Array[Bytes]) -> Array[Bytes] raise {
  let decoder = @zlib.Decoder(until=EndOfMember)
  let out = FixedArray::make(64 * 1024, b'\x00')
  let message = Buffer()
  let messages = []
  for frame in frames {
    let mut input = frame[:]
    for ;; {
      let status = decoder.step_into(input, out, end=false)
      input = input[decoder.last_consumed():]
      message.write_bytes(Bytes::from_array(out[:decoder.last_produced()]))
      match status {
        NeedMoreInput => break
        NeedMoreOutput => ()
        Done => fail("the stream ended")
      }
    }
    if frame is [.., 0x00, 0x00, 0xff, 0xff] {
      messages.push(message.to_bytes())
      message.reset()
    }
  }
  messages
}

///|
test "a message split across frames comes out once its flush arrives" {
  let messages = [b"{\"op\":10}", b"{\"op\":0,\"t\":\"READY\"}"]
  let parts = compress_messages(messages)
  // The second message in two frames.
  let second = parts[1]
  let frames = [parts[0], second[:3].to_owned(), second[3:].to_owned()]
  assert_eq(inflate_messages(frames), messages)
}

#What it does

• Decodes every DEFLATE block (stored, fixed and dynamic Huffman codes) with a 32 KiB window, and preset dictionaries for raw DEFLATE and zlib. It refuses what zlib refuses, with zlib's kind of error: reserved block types and codes, over-subscribed and incomplete codes, distances before the start of the output, and the reserved header fields and values of zlib and gzip. Crafted streams and thousands of corrupted ones are checked against zlib's answers.
• Checks every checksum: zlib's Adler-32, gzip's CRC-32 and length, and the header CRC when a gzip header has one. Output comes out as soon as it is decoded, before the checksum that covers it, so ChecksumMismatch can follow output you already have; decompress returns only checked output.
• Never reads past the end of a stream: after Done under until=EndOfMember, what follows is input[last_consumed():], whatever the input splits. Raw DEFLATE and zlib streams cannot be concatenated, so under the default until=EndOfInput anything after one raises TrailingData.
• Takes input in chunks of any size, down to one byte, and writes output into buffers of any size, under the rules of gaato/codec_bytes. Memory is the window and the decoding tables, 46,592 bytes with a dictionary or without (a dictionary is your bytes, held by reference), plus a gzip header's fields; memory_usage() reports it.
• A step that raises first writes the output that comes before the error, and last_consumed() and last_produced() say what it took and wrote, so a stream with bytes after it gives all its output, then TrailingData, with last_consumed() at its end: whether it came in one step or many. A malformed stream gives the same output before the same kind of error however its input and output are split.
• Every malformed stream raises gaato/codec's CodecError(kind, message), with the kind Truncated, Corrupt, ChecksumMismatch, TrailingData, DictionaryRequired, DictionaryMismatch or LimitExceeded (a gzip header over max_header_bytes, with resource: Memory; more than max_output from decompress, with resource: Output). An error inside the DEFLATE data of a zlib or gzip stream keeps its kind. It does not abort. In a catch on these functions, CodecError(kind, _) and the kinds match unqualified, with no import; to name the types elsewhere, import gaato/codec_bytes, which re-exports them.
• Encodes with libdeflate's levels: 0 stores the input; 1 finds matches in a hash table; 2 to 4 take the longest match at each position, and 5 to 9 look one or two positions ahead for a better one, over hash chains. Each block takes the fixed Huffman code, a dynamic one or no code (stored), whichever is smallest, and ends where the data changes (libdeflate's block splitting) or after 64 KiB. Inputs of a few dozen bytes or less are stored, as libdeflate stores them. With the same input, no dictionary and no flush, the streams are the bytes that libdeflate 1.24 writes when its blocks are limited to 64 KiB. They decode with zlib and the gzip command, whole and cut after every flush (scripts/crosscheck.mbtx, run in CI), and the same input gives the same bytes on every target, however it is split. An encoder never raises.
• An encoder's memory is fixed by its level: 542,516 bytes at the default level (the 32 KiB window, a 64 KiB block and what the parser looks ahead, the block's output, the match tables and the block's sequences), 361,948 at level 1 and 131,077 at level 0, with a dictionary or without, and for gzip its header's bytes; memory_usage() reports it.
• The zlib and gzip header checks, Adler-32's sums (which never overflow), the decoder's verdict on a code's lengths, and the canonical codes the encoder writes are proved against RFC 1950, RFC 1951 and RFC 1952 with moon prove; PROOFS.md lists what is proved and what is trusted.

#Compression ratio

#Known limits

• Levels stop at 9: libdeflate's levels 10 to 12, whose near-optimal parsing comes out about 3 % smaller than level 9 at several times the time, are not here, and higher levels are clamped to 9.
• A flush is a sync flush: zlib's full flush, which also forgets the window, is not offered.

#License

#gaato/deflate

moon add gaato/deflate

///|
test "compress and decompress a whole stream of each format" {
  let text = b"hello, hello, hello"
  assert_eq(@deflate.decompress(@deflate.compress(text)), text)
  assert_eq(@zlib.decompress(@zlib.compress(text, level=9)), text)
  assert_eq(@gzip.decompress(@gzip.compress(text, level=1)), text)
}

///|
test "decompress a whole stream of each format" {
  let raw = b"\xcb\x48\xcd\xc9\xc9\x07\x00"
  assert_eq(@deflate.decompress(raw), b"hello")
  let zlib = b"\x78\x9c\xcb\x48\xcd\xc9\xc9\x07\x00\x06\x2c\x02\x15"
  assert_eq(@zlib.decompress(zlib, max_output=16 * 1024 * 1024), b"hello")
  let gzip = b"\x1f\x8b\x08\x00\x00\x00\x00\x00\x02\x03\xcb\x48\xcd\xc9\xc9\x07\x00\x86\xa6\x10\x36\x05\x00\x00\x00"
  assert_eq(@gzip.decompress(gzip), b"hello")
}

///|
fn gunzip(chunks : Array[Bytes], sink : (BytesView) -> Unit) -> Unit raise {
  let decoder = @gzip.Decoder()
  let out = FixedArray::make(64 * 1024, b'\x00')
  for i, chunk in chunks {
    let mut input = chunk[:]
    for ;; {
      let status = decoder.step_into(input, out, end=i == chunks.length() - 1)
      input = input[decoder.last_consumed():]
      sink(Bytes::from_array(out[:decoder.last_produced()]))
      match status {
        Done => return
        NeedMoreInput => break
        NeedMoreOutput => ()
      }
    }
  }
}

///|
test "decode a gzip stream chunk by chunk" {
  let decoded = Buffer()
  gunzip(
    [
      b"\x1f\x8b\x08\x00\x00\x00\x00\x00", b"\x02\x03\xcb\x48\xcd\xc9\xc9\x07", b"\x00\x86\xa6\x10\x36\x05\x00\x00\x00",
    ],
    bytes => decoded.write_bytes(bytes.to_owned()),
  )
  assert_eq(decoded.to_bytes(), b"hello")
}

///|
/// Compresses each message of a connection into one zlib stream, as
/// Discord's `zlib-stream` does: every message ends in a sync flush. Returns
/// the bytes to send for each message.
fn compress_messages(messages : Array[Bytes]) -> Array[Bytes] {
  let encoder = @zlib.Encoder()
  let out = FixedArray::make(64 * 1024, b'\x00')
  messages.map(message => {
    let part = Buffer()
    let mut input = message[:]
    for ;; {
      let status = encoder.step_into(input, out, action=Flush)
      input = input[encoder.last_consumed():]
      part.write_bytes(Bytes::from_array(out[:encoder.last_produced()]))
      if status is NeedMoreInput {
        break
      }
    }
    part.to_bytes()
  })
}

///|
test "each message decodes on its own, without the end of the stream" {
  let messages = [b"{\"op\":10}", b"{\"op\":11}"]
  let decoder = @zlib.Decoder()
  let out = FixedArray::make(64 * 1024, b'\x00')
  for i, part in compress_messages(messages) {
    assert_true(part[part.length() - 4:] is [0x00, 0x00, 0xff, 0xff])
    assert_true(decoder.step_into(part, out, end=false) is NeedMoreInput)
    assert_eq(Bytes::from_array(out[:decoder.last_produced()]), messages[i])
  }
}

#gzip

///|
test "one member, then what follows it" {
  let gz = b"\x1f\x8b\x08\x00\x00\x00\x00\x00\x02\x03\xcb\x48\xcd\xc9\xc9\x07\x00\x86\xa6\x10\x36\x05\x00\x00\x00"
  let input = Bytes::from_array([..gz, 0, 0, 0, 0])
  let decoder = @gzip.Decoder(until=EndOfMember)
  let out = FixedArray::make(64, b'\x00')
  assert_true(decoder.step_into(input, out, end=true) is Done)
  assert_eq(Bytes::from_array(out[:decoder.last_produced()]), b"hello")
  assert_eq(input[decoder.last_consumed():], b"\x00\x00\x00\x00")
  let header = decoder.header().unwrap()
  assert_eq(header.os, b'\x03')
  assert_true(header.name is None)
}

///|
test "skip the header's fields" {
  // A member named "a.txt" (FNAME).
  let gz = b"\x1f\x8b\x08\x08\x00\x00\x00\x00\x00\x03a.txt\x00\xcb\x48\xcd\xc9\xc9\x07\x00\x86\xa6\x10\x36\x05\x00\x00\x00"
  let decoder = @gzip.Decoder(keep_header=false)
  let out = FixedArray::make(64, b'\x00')
  assert_true(decoder.step_into(gz, out, end=true) is Done)
  assert_eq(Bytes::from_array(out[:decoder.last_produced()]), b"hello")
  assert_true(decoder.header() is Some({ name: None, os: b'\x03', .. }))
  assert_eq(@gzip.decompress(gz), b"hello")
}

///|
test "a member with a name" {
  let header : @gzip.Header = {
    text: true,
    mtime: 1700000000,
    xfl: b'\x00',
    os: b'\x03',
    extra: None,
    name: Some(b"notes.txt"),
    comment: None,
  }
  assert_true(header.is_writable())
  let gz = @gzip.compress(b"hello", header~)
  let decoder = @gzip.Decoder()
  let out = FixedArray::make(64, b'\x00')
  assert_true(decoder.step_into(gz, out, end=true) is Done)
  assert_eq(decoder.header(), Some(header))
  // The default header: MTIME 0, XFL 0 at level 6, OS 255.
  assert_eq(
    @gzip.compress(b"hello")[:10],
    b"\x1f\x8b\x08\x00\x00\x00\x00\x00\x00\xff",
  )
}

#zlib

///|
test "a stream that needs a dictionary" {
  let dictionary = b"hello, dictionary"
  // zlib.deflateSync("hello", { dictionary }) in Node.
  let stream = b"\x78\xbb\x39\x4e\x06\x97\xcb\x00\x09\x00\x00\x06\x2c\x02\x15"
  let needed = try @zlib.decompress(stream) catch {
    CodecError(DictionaryRequired(id), _) => id
    _ => None
  } noraise {
    _ => None
  }
  assert_eq(needed, Some(@zlib.dictionary_id(dictionary)))
  assert_eq(@zlib.decompress(stream, dictionary~), b"hello")
}

///|
test "compress with a dictionary" {
  let dictionary = b"{\"op\":0,\"t\":\"MESSAGE_CREATE\",\"d\":{\"content\":\""
  let message = b"{\"op\":0,\"t\":\"MESSAGE_CREATE\",\"d\":{\"content\":\"hi\"}}"
  let stream = @zlib.compress(message, dictionary~)
  assert_eq(@zlib.decompress(stream, dictionary~), message)
  assert_true(stream.length() < @zlib.compress(message).length())
}

#A stream that does not end

• NeedMoreInput, with the frame consumed, is the answer to every frame. Everything the frame determines has been written, so after a frame that ends in 00 00 ff ff the whole message is out. The decoder does not know where messages end; the suffix does.
• NeedMoreOutput: the slice is full. Call again with the rest of the frame, frame[last_consumed():].
• Done: the stream ended, which a gateway stream never does. until=EndOfMember makes the decoder report this at once; under the default, it would wait for what follows and raise TrailingData on the next frame.

///|
/// Inflates the frames of one connection, and returns its messages.
fn inflate_messages(frames : Array[Bytes]) -> Array[Bytes] raise {
  let decoder = @zlib.Decoder(until=EndOfMember)
  let out = FixedArray::make(64 * 1024, b'\x00')
  let message = Buffer()
  let messages = []
  for frame in frames {
    let mut input = frame[:]
    for ;; {
      let status = decoder.step_into(input, out, end=false)
      input = input[decoder.last_consumed():]
      message.write_bytes(Bytes::from_array(out[:decoder.last_produced()]))
      match status {
        NeedMoreInput => break
        NeedMoreOutput => ()
        Done => fail("the stream ended")
      }
    }
    if frame is [.., 0x00, 0x00, 0xff, 0xff] {
      messages.push(message.to_bytes())
      message.reset()
    }
  }
  messages
}

///|
test "a message split across frames comes out once its flush arrives" {
  let messages = [b"{\"op\":10}", b"{\"op\":0,\"t\":\"READY\"}"]
  let parts = compress_messages(messages)
  // The second message in two frames.
  let second = parts[1]
  let frames = [parts[0], second[:3].to_owned(), second[3:].to_owned()]
  assert_eq(inflate_messages(frames), messages)
}

#What it does

• Decodes every DEFLATE block (stored, fixed and dynamic Huffman codes) with a 32 KiB window, and preset dictionaries for raw DEFLATE and zlib. It refuses what zlib refuses, with zlib's kind of error: reserved block types and codes, over-subscribed and incomplete codes, distances before the start of the output, and the reserved header fields and values of zlib and gzip. Crafted streams and thousands of corrupted ones are checked against zlib's answers.
• Checks every checksum: zlib's Adler-32, gzip's CRC-32 and length, and the header CRC when a gzip header has one. Output comes out as soon as it is decoded, before the checksum that covers it, so ChecksumMismatch can follow output you already have; decompress returns only checked output.
• Never reads past the end of a stream: after Done under until=EndOfMember, what follows is input[last_consumed():], whatever the input splits. Raw DEFLATE and zlib streams cannot be concatenated, so under the default until=EndOfInput anything after one raises TrailingData.
• Takes input in chunks of any size, down to one byte, and writes output into buffers of any size, under the rules of gaato/codec_bytes. Memory is the window and the decoding tables, 46,592 bytes with a dictionary or without (a dictionary is your bytes, held by reference), plus a gzip header's fields; memory_usage() reports it.
• A step that raises first writes the output that comes before the error, and last_consumed() and last_produced() say what it took and wrote, so a stream with bytes after it gives all its output, then TrailingData, with last_consumed() at its end: whether it came in one step or many. A malformed stream gives the same output before the same kind of error however its input and output are split.
• Every malformed stream raises gaato/codec's CodecError(kind, message), with the kind Truncated, Corrupt, ChecksumMismatch, TrailingData, DictionaryRequired, DictionaryMismatch or LimitExceeded (a gzip header over max_header_bytes, with resource: Memory; more than max_output from decompress, with resource: Output). An error inside the DEFLATE data of a zlib or gzip stream keeps its kind. It does not abort. In a catch on these functions, CodecError(kind, _) and the kinds match unqualified, with no import; to name the types elsewhere, import gaato/codec_bytes, which re-exports them.
• Encodes with libdeflate's levels: 0 stores the input; 1 finds matches in a hash table; 2 to 4 take the longest match at each position, and 5 to 9 look one or two positions ahead for a better one, over hash chains. Each block takes the fixed Huffman code, a dynamic one or no code (stored), whichever is smallest, and ends where the data changes (libdeflate's block splitting) or after 64 KiB. Inputs of a few dozen bytes or less are stored, as libdeflate stores them. With the same input, no dictionary and no flush, the streams are the bytes that libdeflate 1.24 writes when its blocks are limited to 64 KiB. They decode with zlib and the gzip command, whole and cut after every flush (scripts/crosscheck.mbtx, run in CI), and the same input gives the same bytes on every target, however it is split. An encoder never raises.
• An encoder's memory is fixed by its level: 542,516 bytes at the default level (the 32 KiB window, a 64 KiB block and what the parser looks ahead, the block's output, the match tables and the block's sequences), 361,948 at level 1 and 131,077 at level 0, with a dictionary or without, and for gzip its header's bytes; memory_usage() reports it.
• The zlib and gzip header checks, Adler-32's sums (which never overflow), the decoder's verdict on a code's lengths, and the canonical codes the encoder writes are proved against RFC 1950, RFC 1951 and RFC 1952 with moon prove; PROOFS.md lists what is proved and what is trusted.

#Compression ratio

#Known limits

• Levels stop at 9: libdeflate's levels 10 to 12, whose near-optimal parsing comes out about 3 % smaller than level 9 at several times the time, are not here, and higher levels are clamped to 9.
• A flush is a sync flush: zlib's full flush, which also forgets the window, is not offered.

#License