binaryio: Functions for Reading and Writing Binary Data
On this page:
prefixcode-encode
prefixcode-encode!
prefixcode-build-decode-tree
prefixcode-decode
prefixcode-decode!
prefixcode-decode-list
prefixcode-decode1
8.18
top up

9Prefix Codes: Encoding and DecodingπŸ”— i

(require binaryio/prefixcode ) package: binaryio-lib

Added in version 1.2 of package binaryio-lib.

This module provides encoding and decoding support using prefix codes (aka prefix-free codes), including Huffman codes. See binaryio/huffman for support for computing such codes.

procedure

( prefixcode-encode encode-table
input
[ msf?
#:padpad-sbv])
→
bytes? exact-nonnegative-integer?
encode-table :
(or/c (hash/c any/c sbv? )
(listof (cons/c any/c sbv? ))
(vectorof sbv? ))
input:sequence?
msf?:boolean? =#t
pad-sbv:sbv? =empty-sbv
Encodes the values of input using encode-table, which represents the prefix code as a mapping of values to short bitvectors. The input can be any sequence, including strings, byte strings, lists, and so on. The result is a byte string containing the encoded bits, along with the number of bits in the encoding. See output-bitport-get-output for the format of the encoded byte string and the interpretation of the pad-sbv argument.

The encode-table must be one of the following:
Each code in the table must be unique, and the set of codes must form a valid prefix code. Otherwise, the results of encoding and decoding are unpredictable.

If msf? is #t (the default), then bits within each byte are added in most significant first order. If msf? is #f, then bits within each byte are added in least significant first order.

Examples:
> (require binaryio/examples/hpack)
> (define-values (encenc-bits)
(prefixcode-encode hpack-encode-table#"hello world!"#:padhpack-end-code))
> (values encenc-bits)

#"234円264円Pu<36円312円$376円?"

74

procedure

( prefixcode-encode! bp
encode-table
input
[ #:padpad-sbv]) → void?
bp:output-bitport?
encode-table :
(or/c (hash/c any/c sbv? )
(listof (cons/c any/c sbv? ))
(vectorof sbv? ))
input:sequence?
pad-sbv:sbv? =empty-sbv
Like prefixcode-encode , but writes the encoded bits to bp.

procedure

( prefixcode-build-decode-tree encode-table)→any/c

encode-table :
(or/c (hash/c any/c sbv? )
(listof (cons/c any/c sbv? ))
(vectorof sbv? ))
Converts encode-table (see prefixcode-encode ) into a data structure suitable for decoding the same prefix code.

The representation is not specified, but if all values in the table are readable (or quotable), then the representation of the decoder tree is readable (or quotable).

Example:
> (define hpack-decode-tree(prefixcode-build-decode-tree hpack-encode-table))

procedure

( prefixcode-decode decode-tree
bs
[ start-bit-index
end-bit-index
msf?
#:endend-code
#:handle-errorhandle-error]) → bytes?
decode-tree:any/c
bs:bytes?
start-bit-index:exact-nonnegative-integer? =0
end-bit-index : exact-nonnegative-integer?
= (* 8(bytes-length bs))
msf?:boolean? =#t
end-code:(or/c sbv? #f)=#f
handle-error :
(-> (or/c 'bad'incomplete)
exact-nonnegative-integer?
exact-nonnegative-integer?
sbv?
any )
= (lambda (modestartendcode)(error ....))
Decodes bs (from start-bit-index, inclusive, to end-bit-index, exclusive) using the prefix code represented by decode-tree, which must have been produced by prefixcode-build-decode-tree .

Each value represented by decode-tree must be a byte, character, byte string, or character string. Each decoded value is accumulated into a byte string, which is the result of successful decoding.

If the decoder encounters a sequence of bits that is not a valid code prefix, it calls

(handle-error'badbad-start-indexbad-end-indexbad-code)

to handle the error. If the decoder reaches end-bit-index without completing the current code, and if end-code is #f, then it handles the error by calling

(handle-error'incompleteincomplete-start-indexend-bit-indexincomplete-code)

But if end-code is a bitvector, then no error is signaled if the bits between the end of the last complete code and end-bit-index are a prefix of end-code.

Note that if handle-error returns normally, its result is discarded, so it is recommended that handle-error escape (for example, by raising an exception).

Examples:
> (prefixcode-decode hpack-decode-treeenc0enc-bits)

#"hello world!"

> (prefixcode-decode hpack-decode-treeenc#:endhpack-end-code)

#"hello world!"

> (prefixcode-decode hpack-decode-treeenc#:handle-errorlist )

#"hello world!"

procedure

( prefixcode-decode! output
decode-tree
bs
[ start-bit-index
end-bit-index
msf?
#:endend-code
#:handle-errorhandle-error])
→(or/c void? any )
output:(or/c output-port? (-> any/c void? ))
decode-tree:any/c
bs:bytes?
start-bit-index:exact-nonnegative-integer? =0
end-bit-index : exact-nonnegative-integer?
= (* 8(bytes-length bs))
msf?:boolean? =#t
end-code:(or/c sbv? #f)=#f
handle-error :
(-> (or/c 'bad'incomplete)
exact-nonnegative-integer?
exact-nonnegative-integer?
sbv?
any )
= (lambda (modestartendcode)(error ....))
Like prefixcode-decode , but each decoded value is sent to output, and the result of a successful decoding is (void ).

If output is an output port, then a decoded value must be a byte, character, byte string, or character string, and the value is emitted by writing it to the port. If output is a procedure, then any value is allowed, and the value is emitted by calling output on it.

If decoding completes successfully, the result is (void ); otherwise, it is the result of the call to handle-error.

Examples:
> (call-with-output-bytes
(lambda (out)
(prefixcode-decode! outhpack-decode-treeenc0enc-bits)))

#"hello world!"

> (call-with-output-bytes
(lambda (out)
(prefixcode-decode! outhpack-decode-treeenc0#:endhpack-end-code)))

#"hello world!"

> (prefixcode-decode! void hpack-decode-treeenc#:handle-errorlist )

'(incomplete 74 80 4128774)

procedure

( prefixcode-decode-list decode-tree
bs
[ start-bit-index
end-bit-index
msf?
#:endend-code
#:handle-errorhandle-error]) → list?
decode-tree:any/c
bs:bytes?
start-bit-index:exact-nonnegative-integer? =0
end-bit-index : exact-nonnegative-integer?
= (* 8(bytes-length bs))
msf?:boolean? =#t
end-code:(or/c sbv? #f)=#f
handle-error :
(-> (or/c 'bad'incomplete)
exact-nonnegative-integer?
exact-nonnegative-integer?
sbv?
any )
= (lambda (modestartendcode)(error ....))
Like prefixcode-decode , but decodes the input to a list. This allows values other than bytes, characters, and character strings to be conveniently decoded.

Note that if handle-error returns normally, its result is discarded, so it is recommended that handle-error escape (for example, by raising an exception).

procedure

( prefixcode-decode1 decode-tree
bs
[ start-bit-index
end-bit-index
msf?
#:endend-code])
→
(or/c 'ok'bad'end'incomplete)
exact-nonnegative-integer?
any/c
decode-tree:any/c
bs:bytes?
start-bit-index:exact-nonnegative-integer? =0
end-bit-index : exact-nonnegative-integer?
= (* 8(bytes-length bs))
msf?:boolean? =#t
end-code:(or/c sbv? #f)=#f
Like prefixcode-decode , but decodes a single value from the input. The result is one of the following:

  • (values 'oknext-bit-indexvalue) — The bits from start-bit-index (inclusive) to next-bit-index (exclusive) represent the code for value.

  • (values 'badnext-bit-indexbad-code) — The bits from start-bit-index to next-bit-index do not represent a valid code or its prefix. The bad-code result contains those bits as a bitvector.

  • (values 'incompletenext-bit-indexincomplete-code) — The bits from start-bit-index to next-bit-index represent an incomplete code, but it is not a prefix of end-code. The incomplete-code result contains those bits as a bitvector.

  • (values 'endnext-bit-indexfinal-code) — The bits from start-bit-index to next-bit-index represent a prefix of end-code — possibly all of end-code, possibly empty (if start-bit-index equals end-bit-index). The final-code result contains those bits as a bitvector.

Examples:
> (prefixcode-decode1 hpack-decode-treeenc0)

'ok

6

104

> (prefixcode-decode1 hpack-decode-treeenc6)

'ok

11

101

> (bytes 104101)

#"he"

top up

AltStyle γ«γ‚ˆγ£γ¦ε€‰ζ›γ•γ‚ŒγŸγƒšγƒΌγ‚Έ (->γ‚ͺγƒͺγ‚ΈγƒŠγƒ«) /