This library adds three features to Racket:
library support for bit strings, a generalization of byte vectors;
syntactic support for extracting integers, floats, sub-bit-strings and general values from bit strings; and
syntactic support for constructing bit strings from integers, floats, other bit strings and general values.
It is heavily inspired by Erlang’s binaries, bitstrings, and binary pattern-matching. The Erlang documentation provides a good introduction to these features:
The binary matching (bit-string-case) and formatting (bit-string) languages can also be extended with custom parsers and formatters, giving lightweight syntactic support for domain-specific binary encodings of values.
If you find that this library lacks some feature you need, or you have a suggestion for improving it, please don’t hesitate to get in touch with me!
Version 5.2 of this library supports short input signalling in custom extension parsers via an additional optional argument passed to their failure continuations.
Version 5.0 of this library repaired translation between little-endian integers and bit-strings of width not equal to a multiple of 8 bits. Previously, the high bits of such integers were placed in an incorrect position; see Binary representation of integers for details. This brings the behaviour of the library into line with Erlang. Since the change may affect existing programs, it warrants an incremented major version number.
Version 4.0 of this library changes the way custom parsers and formatters work, requiring them to be macros, where in previous releases they could have been implemented as functions. Version 4.0 of the library also supports the use of bit-string-case and bit-string in Typed Racket code.
Version 4.0 is also the final release made using the Planet package system. Current and future versions of this package will use the new Racket package system ("raco pkg") instead.
Version 3.2 of this library adds support for custom parsers and formatters.
Version 3.0 of this library uses instead of : to separate expressions from encoding specifications in the bit-string-case and bit-string macros. The reason for this is to avoid a collision with Typed Racket, which uses : for its own purposes.
A bit string is a sequence of bits, numbered ascending from zero. The first byte is bits 0 through 7 inclusive, where bit 0 is the most significant bit in the byte; the second byte is bits 8 through 15; and so on.
Concretely, a bit string is either
a byte vector, as returned by bytes and friends;
a bit-resolution slice of a byte vector, as returned by sub-bit-string; or
a splicing-together of two bit strings, as returned by bit-string-append.
The routines in this library are written, except where specified, to handle any of these three representations for bit strings.
All the functionality below can be accessed with a single require:
|(require bitsyntax)||package: bitsyntax|
(bit-string-case value-expr maybe-short-handler clause ...)
| #:on-short short-input-handler clause =
([segment-pattern ...] (when guard-expr) body-expr ...) |
([segment-pattern ...] body-expr ...) |
(else body-expr ...) segment-pattern = comparison-pattern | binding-pattern | discard-pattern comparison-pattern = (= expr custom-parser) | (= expr option ...) | (= expr) binding-pattern = (id custom-parser) | (id option ...) | (id) | id discard-pattern = ( custom-parser) | ( option ...) custom-parser = (expr expr ...) option = type-option | signedness-option | endianness-option | width-option type-option = integer | float | binary signedness-option = unsigned | signed endianness-option = little-endian | big-endian | native-endian width-option = bits n | bytes n | default
short-input-handler : (-> (-> any/c) any/c)
Each clause is then tried in turn. The first succeeding clause determines the result of the whole expression. A clause matches successfully if all its segment-patterns match some portion of the input, there is no unused input left over at the end, and the guard-expr (if there is one) evaluates to a true value. If a clause succeeds, then (begin body-expr ...) is evaluated, and its result becomes the result of the whole expression.
If a clause’s pattern attempts to read past the end of the given input, the input is considered to be short, and the short-input-handler is invoked, if one was supplied. If no short-input-handler was supplied, a short input just makes the clause fail, and matching continues with the next clause.
Each segment-pattern matches zero or more bits of the input bit string. The given type, signedness, endianness and width are used to extract a value from the bit string, at which point it is either compared to some other value using equal? (if a comparison-pattern was used in the segment-pattern), bound to a pattern variable (if a binding-pattern was used), or discarded (if a discard-pattern was used) before matching continues with the next segment-pattern.
The supported segment types are
integer – this is the default. A signed or unsigned, big- or little-endian integer of the given width in bits is read out of the bit string. Unless otherwise specified, integers default to big-endian, unsigned, and eight bits wide. Any width, not just multiples of eight, is supported. See Binary representation of integers for details.
float – A 32- or 64-bit float in either big- or little-endian byte order is read out of the bit string using floating-point-bytes->real. Unless otherwise specified, floats default to big-endian and 64 bits wide. Widths other than 32 or 64 bits are unsupported.
binary – A sub-bit-string is read out of the bit string. The bit string can be an arbitrary number of bits long, not just a multiple of eight. Unless otherwise specified, the entire rest of the input will be consumed and returned.
custom-parser – An arbitrary amount of the input is consumed, analysed, and transformed. The built-in parsing options can’t be specified in conjunction with a custom parser: instead, each custom parser accepts its own option arguments. See Custom parsers and custom formatters.
Each type (except for custom-parser) has a default signedness, endianness, and width in bits, as described above. These can all (again, except for custom-parsers, which manage such issues on their own) be overridden individually:
unsigned and signed specify that integers should be decoded in an unsigned or signed manner, respectively.
big-endian, little-endian and native-endian specify the endianness to use in decoding integers or floats. Specifying native-endian causes Racket to use whatever is the native endianness of the platform the program is currently running on (discovered using system-big-endian?).
default causes the decoder to use whatever the default width is for the type specified.
bytes n causes the decoder to try to consume n bytes of input for this segment-pattern.
bits n causes the decoder to try to consume n bits of input for this segment-pattern.
(bit-string-case some-input-value ([(= 0 bytes 2)] 'a) ([(f bits 10) ( bits 6)] (when (and (< f 123) (>= f 100))) 'between-100-and-123) ([(f bits 10) ( bits 6)] f) ([(f bits 10) ( bits 6) (rest binary)] (list f rest)))
This expression analyses some-input-value, which must be a (bit-string?). It may contain:
16 zero bits, in which case the result is 'a; or
a ten-bit big-endian unsigned integer followed by 6 bits which are ignored, where the integer is between 100 (inclusive) and 123 (exclusive), in which case the result is 'between-100-and-123; or
the same as the previous clause, but without the guard; if this succeeds, the result is the ten-bit integer itself; or
the same as the previous clause, but with an arbitrary number of bits following the six discarded bits. The result here is a list containing the ten-bit integer and the trailing bit string.
The following example parses a Pascal-style byte string (one length byte, followed by the right number of data bytes) and decodes it using a UTF-8 codec:
> (define (parse-pascal-string input-bit-string) (bit-string-case input-bit-string ([len (body binary bytes len)] (bytes->string/utf-8 (bit-string-pack body)))))
Notice how the len value, which came from the input bit string itself, is used to decide how much of the remaining input to consume.
Most of the time, bit-string-case is used with complete inputs. For example, a complete input might be the entirety of an Ethernet packet, a complete UDP datagram, or a precisely-measured HTTP POST request body. In these situations, no further input is expected to be available, and patterns in bit-string-case clauses that need to examine beyond the end of the currently-available input should simply fail. This is the default behaviour, when #:on-short is omitted from bit-string-case.
However, when working with inputs that are self-delimiting (such as JSON texts, XML documents, or S-expressions) and that are being read incrementally from input streams (i.e. ports, including in particular TCP connections), there may be an alternative, appropriate thing to do when a pattern needs to look past the end of the currently-available input. For example, it might be sensible to ask for more input.
A #:on-short handler function should take a single argument, a zero-argument function fail. The handler function may either return a value to be used as the result of the entire bit-string-case; perform some effect such as calling error; or invoke the passed-in fail function. The fail function should be called when the handler function has decided that the match should simply fail. Tail-calling fail from a handler function instructs bit-string-case to continue by moving on to the next clause in sequence.
For example, consider working with the Pascal-style string parser from above. Giving it a correctly-sized input works as expected:
> (parse-pascal-string #"\4ABCD")
Giving it an overlong input causes failure, as expected because of the rule that a clause only matches if its segment-patterns match all of the supplied input:
> (parse-pascal-string #"\4ABCDEFGH")
bit-string-case: No matching clauses for #"\4ABCDEFGH"
Similarly, giving it a short input causes failure, because by default
a short input is considered to be complete—
> (parse-pascal-string #"\4AB")
bit-string-case: No matching clauses for #"\4AB"
However, we may be in a situation where we are incrementally parsing strings from a slow TCP stream or similar. In this situation, we want to treat a short input as a signal that we need more input before we can decide how to continue:
> (define (parse-pascal-string/incremental input-bit-string) (bit-string-case input-bit-string #:on-short (lambda (fail) 'short) ([len (body binary bytes len)] (bytes->string/utf-8 (bit-string-pack body))))) > (parse-pascal-string/incremental #"\4ABCDEFGH")
bit-string-case: No matching clauses for #"\4ABCDEFGH"
> (parse-pascal-string/incremental #"\4ABCD")
> (parse-pascal-string/incremental #"\4AB")
Here, overlong and correctly-sized inputs are handled as before, but we use #:on-short to supply a handler function that returns 'short when more input is needed. The calling code might, for example, interpret 'short to mean that a further read from a TCP stream is needed to complete the input.
(bit-string spec ...)
spec = [segment-expr custom-formatter] | [segment-expr option ...] | segment-expr custom-formatter = (expr expr ...) option = type-option | endianness-option | width-option type-option = integer | float | binary endianness-option = little-endian | big-endian | native-endian width-option = bits n | bytes n | default
Each spec can specify an integer or floating-point number to encode, a bit string to copy into the output, or a custom formatting routine to apply to the given value. If a type is not specified, integer is assumed. If an endianness is (relevant but) not specified, big-endian is assumed. If a width is not given, integers are encoded as 8-bit quantities, floats are encoded as 64-bit quantities, and binary objects are copied into the output in their entirety. Custom formatters do not accept these options, since they manage the encoding of the value they are given themselves, and take whatever options they need by other means.
If a width is specified, integers will be truncated or sign-extended to fit, and binaries will be truncated. If a binary is shorter than a specified width, an error is signalled. Floating-point encoding can only be done using 32- or 64-bit widths, but integer encoding can be done using any bit width; see Binary representation of integers for details.
(define (string->pascal/utf-8 str) (let ((bs (string->bytes/utf-8 str))) (bit-string (bytes-length bs) [bs binary])))
This subroutine encodes its string argument using a UTF-8 codec, and then assembles it into a Pascal-style string with a prefix length byte. If the encoded string is longer than 255 bytes, note that the length byte will be truncated and so the encoding will be incorrect. A better encoder would ensure that bs was not longer than 255 bytes before encoding it as a Pascal string.
Note that if you wish to leave all the options at their defaults (that is, [... integer bits 8]), you can use the second form of spec given above.
Bits in a bit-string are always counted off from the MSB of a byte to the LSB rather than the other way around.
Endianness (when converting between bit-strings and integers) only affects which group of eight bits is dealt with first. In big-endian mode, bits are copied out in order from big end to little end, so an integer value with bits ABCDEFGHIJKL will lead to bits appearing in that order in the result. In little-endian mode, bits are copied out from MSB to LSB as usual, but the lowest eight bits of the integer are copied first, followed by the next byte’s worth, and so on, so ABCDEFGHIJKL will appear as EFGHIJKLABCD in the resulting bit-string.
For multiples of eight bits aligned to byte boundaries, the usual endianness conversions follow:
705 = 0000001011000001 ---> 1100000100000010 in little-endian
0 2 C 1 C 1 0 2
> (bytes->hex-string (bit-string->bytes (bit-string (705 big-endian bits 16))))
> (bytes->hex-string (bit-string->bytes (bit-string (705 little-endian bits 16))))
However, when other integer widths are used, little-endian conversion of values longer than eight bits can be surprising. For example, let’s first examine encoding the number 48 as a 6-bit integer followed by 705 as a 10-bit integer in big-endian:
48 = 110000xx
705 = 10110000 01xxxxxx
110000 10110000 01 = resulting bitstring
C 2 C 1
> (bytes->hex-string (bit-string->bytes (bit-string (48 big-endian bits 6) (705 big-endian bits 10))))
Encoding the same numbers with the same widths in little-endian, we see that the low byte of the 10-bit value is streamed immediately following the bits of the 6-bit value, followed by the remainder of the 10-bit value:
48 = xx110000 ---> 110000xx in little-endian
705 = xxxxxx10 11000001 ---> 11000001 10xxxxxx in little-endian
110000 11000001 10 = resulting bitstring
C 3 0 6
> (bytes->hex-string (bit-string->bytes (bit-string (48 little-endian bits 6) (705 little-endian bits 10))))
Finally, here is an example of a multiple of eight bits that is not aligned to a byte boundary. We will encode 47574 as a 16-bit quantity, padded with four zero bits on each side. First, in big-endian:
47574 = 10111001 11010110
0000 10111001 11010110 0000 = result
0 B 9 D 6 0
> (bytes->hex-string (bit-string->bytes (bit-string (0 big-endian bits 4) (47574 big-endian bits 16) (0 big-endian bits 4))))
And second, in little-endian:
47574 = 10111001 11010110 ---> 11010110 10111001 in little-endian
0000 11010110 10111001 0000 = result
0 D 6 B 9 0
> (bytes->hex-string (bit-string->bytes (bit-string (0 little-endian bits 4) (47574 little-endian bits 16) (0 little-endian bits 4))))
For simple uses of bit-string-case and bit-string, the built-in parsers and formatters will often be enough. Many binary data formats, however, make heavy use of domain-specific value encodings, and it quickly becomes either repetitive or awkward and error-prone to express these domain-specific formats. Custom parsers and custom formatters exist to allow you to extend both bit-string-case and bit-string to provide convenient shortcut syntax for domain-specific data formats.
For example, imagine a particular protocol makes heavy use of Pascal-style strings: sequences of UTF-8 encoded bytes prefixed by a single length byte, intrinsically limited to a maximum length of 255 bytes. Performing the necessary checks and transformations quickly gets repetitive, as you can see:
(bit-string-case packet ([(= PACKET-TYPE-ONE) username-length (raw-username binary bytes username-length) password-length (raw-password binary bytes password-length)] (let ((username (bytes->string/utf-8 raw-username)) (password (bytes->string/utf-8 raw-password))) ...)) ([(= PACKET-TYPE-TWO) (error-code big-endian integer bytes 2) error-text-length (raw-error-text binary bytes error-text-length)] (let ((error-text (bytes->string/utf-8 raw-error-text))) ...)) ...)
On the formatting side, things are just as bad:
(define (encode-packet-type-one username password) (let ((raw-username (string->bytes/utf-8 username)) (raw-password (string->bytes/utf-8 password))) (when (> (bytes-length raw-username) 255) (error 'encode-packet-type-one "Username too long")) (when (> (bytes-length raw-password) 255) (error 'encode-packet-type-one "Password too long")) (bit-string PACKET-TYPE-ONE (bytes-length raw-username) (raw-username binary) (bytes-length raw-password) (raw-password binary))))
By introducing a custom extension, comprising both a parser and formatter together, we can improve the situation enormously:
(define-syntax pascal-string/utf-8 (syntax-rules () [(_ #t input ks kf) ; The first argument to the custom parser/formatter ; will be a literal #t to signal it is being used ; as a parser. (bit-string-case input #:on-short (lambda (fail) (kf #t)) ; See "detailed anatomy" section below ([len (body binary bytes len) (rest binary)] (ks (bytes->string/utf-8 (bit-string->bytes body)) rest)) (else (kf)))] [(_ #f str) ; The first argument to the custom parser/formatter ; will be a literal #f to signal it is being used ; as a formatter. (let* ((bs (string->bytes/utf-8 str)) (len (bytes-length bs))) (when (> len 255) (error 'pascal-string/utf-8 "String of length ~v too long; max is 255 bytes" len)) (bit-string len (bs binary)))]))
(bit-string-case packet ([(= PACKET-TYPE-ONE) (username (pascal-string/utf-8)) (password (pascal-string/utf-8))] ...) ([(= PACKET-TYPE-TWO) (error-code big-endian integer bytes 2) (error-text (pascal-string/utf-8))] ...) ...)
Formatting is likewise much simplified:
(define (encode-packet-type-one username password) (bit-string PACKET-TYPE-ONE (username (pascal-string/utf-8)) (password (pascal-string/utf-8))))
Custom parser/formatters must be macros that accept one or more arguments. The first argument is a boolean flag, supplied as #t by bit-string-case or as #f by bit-string, indicating whether the custom extension is being used as a parser or a formatter, respectively. Following the flag,
parsers (#t) are given the remaining input to be parsed, a success continuation function ks and a failure continuation function kf, and
formatters (#f) are given the value to be formatted.
Subsequent arguments are supplied by the programmer at each use of the custom extension, and can be used to tweak the behaviour of the extension on a case-by-case basis.
For example, let’s suppose we didn’t want to restrict ourselves to the single length byte of Pascal-style strings, but wanted instead a more flexible way of indicating that a certain block of bytes should be interpreted and rendered as UTF-8 encoded text. We might define a custom parser/formatter like the following:
(define-syntax utf-8 (syntax-rules () ; Consume entirety of input, decode as UTF-8 [(_ #t input ks kf) (ks (bytes->string/utf-8 (bit-string->bytes input)) (bytes))] ; Consume a prefix of the input, decode as UTF-8 [(_ #t input ks kf length-in-bytes) (bit-string-case input #:on-short (lambda (fail) (kf #t)) ; Signal short input ([ (body binary bytes length-in-bytes) (rest binary)] (ks (bytes->string/utf-8 (bit-string->bytes body)) rest)) (else (kf)))] ; Encode the entire string without length prefix [(_ #f str) (string->bytes/utf-8 str)] ; Encode the entire string with a length prefix [(_ #f str (length-format-options ...)) (let* ((bs (string->bytes/utf-8 str)) (len (bytes-length bs))) (bit-string (len length-format-options ...) (bs binary)))]))
A more general utf-8 would be able to specify a length limit as well as a length format. Extending the example in this way is left as an exercise for the reader.
The utf-8 parser/formatter can then be used in any of four different ways:
In bit-string-case, as (var (utf-8)) – will take the remainder of the input and UTF-8 decode it to a string.
In bit-string-case, as (var (utf-8 123)) – will take the next 123 bytes of the input and UTF-8 decode it to a string. Note that the length, here 123, can come from some earlier field extracted from the input, leading to a form of dependent parsing.
In bit-string, as (val (utf-8)) – will encode and output the entirety of val as UTF-8.
In bit-string, as (val (utf-8 (option ...))) – will encode val as UTF-8, and will prepend the length of the encoded text in the output. The length will be formatted using the options, along the lines of ((bytes-length encoded-text) option ...), so the length can be encoded in any way at all. A recursive use of a custom formatter could even encode it in a variable-length fashion.
Giving arguments to custom parser/formatters opens the door to utilities such as variable-length integer codecs, generic zlib-based compressing codecs, generic encrypting codecs, generic transcoders and so on.
A custom extension should accept
the boolean flag indicating whether it is being used as a parser or a formatter,
additional arguments, depending on whether it is being used as a parser or a formatter, and
any other arguments supplied at the time of use.
The interface for calling the failure continuation is awkward: if backwards-compatibility had not been a concern, a separate "short input continuation" argument could have been supplied to custom extensions, rather than the current interface which overloads two uses onto the single failure continuation.
When called in "formatter" mode (with #f as its first argument), it should expect a piece of syntax denoting the value to be formatted as its second argument. The result of expansion should be an expression resulting in the encoded form of this value, as a bit-string.
The general form, then, of custom extensions, is:
(define-syntax my-custom-extension (syntax-rules () [(_ #t input success-k failure-k other-arg ...) (cond [(input-too-short-to-decide? input) (failure-k #t)] [(input-matched? input) (success-k (some-parse-result-from-analysis-of input) remainder-of-input)] [else (failure-k)])] [(_ #f value other-arg ...) (format-value-as-bit-string value)]))
(bit-string-split-at-or-false x offset) →
(or/c bit-string? #f) (or/c bit-string? #f) x : bit-string? offset : integer?
x : bit-string? low-bit : integer? high-bit : integer?
x : bit-string? big-endian? : boolean? signed? : boolean?
x : bit-string? big-endian? : boolean?
(bit-string->unsigned-integer x big-endian?) → exact-nonnegative-integer? x : bit-string? big-endian? : boolean?
The function bit-string->byte will raise an exception if given a bit string of any length other than exactly eight bits.
These procedures may be useful for debugging, but should not be relied upon otherwise.