bitsyntax
1 Introduction
2 Changes
3 What is a bit string?
4 API
4.1 Types
Bit  String
4.2 Pattern-matching bit strings
bit-string-case
4.3 Assembling bit strings from pieces
bit-string
4.4 Binary representation of integers
4.5 Custom parsers and custom formatters
4.5.1 Supplying arguments to custom parsers and formatters
4.5.2 The detailed anatomy of a custom extension
4.6 Bit string utilities
bit-string?
bit-string-length
bit-string-empty?
bit-string-equal?
bit-string-append
bit-string-split-at
bit-string-split-at-or-false
bit-string-take
bit-string-drop
sub-bit-string
bit-string-ref
bit-string->bytes
bit-string->bytes/  align
bit-string-byte-count
bit-string-pack!
bit-string-pack
copy-bits!
bit-string->integer
bit-string->byte
bit-string->signed-integer
bit-string->unsigned-integer
integer->bit-string
4.7 Debugging utilities
bit-slice?
bit-slice-binary
bit-slice-low-bit
bit-slice-high-bit
splice?
splice-left
splice-right
5.0

bitsyntax

Tony Garnock-Jones <[email protected]>

1 Introduction

This library adds three features to Racket:

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!

2 Changes

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.1 of this library adds bit-string-take and bit-string-drop, and causes the empty bit-string to be treated as an identity in bit-string-append.

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.

3 What is a bit string?

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

The routines in this library are written, except where specified, to handle any of these three representations for bit strings.

If you need to flatten a bit string into a contiguous sequence of whole bytes, use bit-string->bytes or bit-string->bytes/align.

4 API

All the functionality below can be accessed with a single require:

 (require bitsyntax) package: bitsyntax

4.1 Types

syntax

BitString

The Typed Racket type of bit strings. A value has type BitString if and only if it also results in #t when given to bit-string?.

4.2 Pattern-matching bit strings

syntax

(bit-string-case value-expr clause ...)

 
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
The value-expr is evaluated first. It must evaluate to a bit string—any object for which bit-string? would return #t.

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 none of the clauses succeed, and there is an else clause, its body-exprs are evaluated and returned. If there’s no else clause and none of the others succeed, an error is signalled.

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

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:

For example:

(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:

The following code block 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:

(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.

4.3 Assembling bit strings from pieces

syntax

(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
This form assembles and encodes a collection of values into a single bit string. Each of the zero or more specs supplies zero or more bits of the resulting bit string. The core language supports encoding of integers, floating-point numbers, and bit-strings, and custom formatters (see Custom parsers and custom formatters) can be used to give a convenient syntax for encoding other kinds of value.

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.

For example:

(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.

4.4 Binary representation of integers

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))))

"02c1"

> (bytes->hex-string (bit-string->bytes (bit-string (705 :: little-endian bits 16))))

"c102"

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))))

"c2c1"

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))))

"c306"

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))))

"0b9d60"

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))))

"0d6b90"

4.5 Custom parsers and custom formatters

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
       ([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)))]))

This single definition can now be used in any bit-string-case or bit-string expression where it is in scope. Here’s the earlier example, rewritten to use pascal-string/utf-8:

(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))))
4.5.1 Supplying arguments to custom parsers and formatters

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,

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
       ([ (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:

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.

Applications of a custom extension macro are rewritten by bit-string-case from (extension arg ...) to (extension #t input ks kf arg ...), and by bit-string to (extension #f value arg ...).

4.5.2 The detailed anatomy of a custom extension

A custom extension should accept

When used in "parser" mode (with #t as its first argument), expects a piece of syntax denoting an input bit-string, a "success continuation" and a "failure continuation" as its second through fourth arguments. The result of expansion should analyse the input bit-string as it sees fit. If it decides it has successfully matched a prefix of the input, it should call the success continuation with two arguments: the value extracted from the input prefix, and the remaining unconsumed input (as a bit-string). If, on the other hand, it decides it cannot match a prefix of the input, it should call the failure continuation with no arguments.

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 ...)
     (if (analyze input)
         (success-k result-of-analysis remainder-of-input)
         (failure-k))]
    [(_ #f value other-arg ...)
     (format-value-as-bit-string value)]))

4.6 Bit string utilities

procedure

(bit-string? x)  boolean?

  x : any?
Returns #t if its argument is either a bytes?, a bit-slice? or a splice?. Returns #f otherwise.

procedure

(bit-string-length x)  integer?

  x : bit-string?
Returns the length of its argument, in bits.

procedure

(bit-string-empty? x)  boolean?

  x : bit-string?
Returns #t iff its argument’s bit-string-length is zero.

procedure

(bit-string-equal? x y)  boolean?

  x : bit-string?
  y : bit-string?
Returns #t iff the bit sequences described by x and y are identical.

procedure

(bit-string-append a ...)  bit-string?

  a : bit-string?
Appends its arguments in order, producing a new bit string. Uses splice internally when it can’t arrange to return a bit string previously constructed. (The practical upshot of this is that you might need to use bit-string->bytes to "flatten" appended bit-strings from time to time.)

procedure

(bit-string-split-at x offset)  
bit-string? bit-string?
  x : bit-string?
  offset : integer?
Produces two values: the bit-string containing bits [0..offset) of x, and the bit-string containing bits [offset..(bit-string-length x)) of x. If offset is negative or greater-or-equal-to the number of bits in x, an error is signalled.

procedure

(bit-string-split-at-or-false x offset)  
(or/c bit-string? #f)
(or/c bit-string? #f)
  x : bit-string?
  offset : integer?
Like (bit-string-split-at x offset), but if offset is out of range returns (values #f #f) instead of signalling an error. This procedure is used in the implementation of bit-string-case.

procedure

(bit-string-take x offset)  bit-string?

  x : bit-string?
  offset : integer?
Retrieves the first offset bits of x. Raises an exception if offset is out-of-bounds.

procedure

(bit-string-drop x offset)  bit-string?

  x : bit-string?
  offset : integer?
Discards the first offset bits of x. Raises an exception if offset is out-of-bounds.

procedure

(sub-bit-string x low-bit high-bit)  bit-string?

  x : bit-string?
  low-bit : integer?
  high-bit : integer?
If (<= 0 low-bit high-bit (sub1 (bit-string-length x))), returns the bit-string containing bits [low-bit..high-bit) of x. Otherwise, signals an error.

procedure

(bit-string-ref x offset)  (or/c 0 1)

  x : bit-string?
  offset : integer?
Extracts bit number offset from x. Signals an error if offset is negative or greater-than-or-equal-to the length of x.

procedure

(bit-string->bytes x)  bytes?

  x : bit-string?
Flattens any splices or bit-slices in x, producing a single contiguous byte vector with x’s contents. If (positive? (remainder (bit-string-length x) 8)), pads out the remaining bits with zeros on the right.

procedure

(bit-string->bytes/align x align-right?)  bytes?

  x : bit-string?
  align-right? : boolean?
As bit-string->bytes, but offers the choice of padding on the right (if align-right? is #f) or on the left (if align-right? is #t) when padding is required. (Note that to align the bits in x on the right is to pad with zeros on the left, and vice versa.)

procedure

(bit-string-byte-count x)  integer?

  x : bit-string?
Returns the smallest number of whole bytes that could contain all the bits in x.

procedure

(bit-string-pack! x buf offset)  void?

  x : bit-string?
  buf : bytes?
  offset : integer?
Copies the entirety of x into buf, overwriting bits starting with the offsetth. It is an error for buf not to have enough room or for offset to be out-of-bounds.

procedure

(bit-string-pack x)  bit-string?

  x : bit-string?
Returns a bit string equivalent to x (i.e. with exactly the same bits in the same order) but with any intermediate splices or bit-slices flattened away. The result will either be a bytes? of the correct length, or a bit-slice referring to a section of a byte vector of length (bit-string-byte-count x).

procedure

(copy-bits! target    
  target-offset    
  source    
  source-offset    
  count)  void?
  target : bytes?
  target-offset : integer?
  source : bytes?
  source-offset : integer?
  count : integer?
Overwrites bits [target-offset..(+ target-offset count)) of target with bits [source-offset..(+ source-offset count)) of source. Undefined behaviour results when (eq? target source).

procedure

(bit-string->integer x big-endian? signed?)  exact-integer?

  x : bit-string?
  big-endian? : boolean?
  signed? : boolean?
Interprets the bits in x as an integer, using either a big- or little-endian byte-ordering convention (per big-endian?), and either unsigned or two’s-complement signed arithmetic (per signed?) to produce the result.

procedure

(bit-string->byte x)  byte?

  x : bit-string?

procedure

(bit-string->signed-integer x big-endian?)  exact-integer?

  x : bit-string?
  big-endian? : boolean?

procedure

(bit-string->unsigned-integer x 
  big-endian?) 
  exact-nonnegative-integer?
  x : bit-string?
  big-endian? : boolean?
Specialized versions of bit-string->integer, giving better type information for use with Typed Racket.

The function bit-string->byte will raise an exception if given a bit string of any length other than exactly eight bits.

procedure

(integer->bit-string n width big-endian?)  bit-string?

  n : integer?
  width : integer?
  big-endian? : boolean?
Encodes n as a bit string of length width bits, truncating or sign-extending as required, and using a big- or little-endian byte-ordering convention as per big-endian?.

4.7 Debugging utilities

These procedures may be useful for debugging, but should not be relied upon otherwise.

procedure

(bit-slice? x)  boolean?

  x : any?
Returns #t if and only if x is a bit-slice.

procedure

(bit-slice-binary x)  bytes?

  x : bit-slice?
Extracts the underlying byte vector from a bit-slice.

procedure

(bit-slice-low-bit x)  integer?

  x : bit-slice?

procedure

(bit-slice-high-bit x)  integer?

  x : bit-slice?
Extract the low (inclusive) and high (exclusive) bit indexes, respectively, from a bit-slice. The bit-slice itself represents bits [low..high) of the underlying byte vector.

procedure

(splice? x)  boolean?

  x : any?
Returns #t if and only if x is a splice of two bit-strings.

procedure

(splice-left x)  bit-string?

  x : splice?

procedure

(splice-right x)  bit-string?

  x : splice?
Extract the left and right bit-strings, respectively, that are spliced together by the given splice x.