Bits and Bit Fields

Bits and Bit Fields#

Some binary inputs use individual bits to specify contents. For instance, you might have a flag byte that holds multiple (bit) flags:

struct {
  unsigned int italic: 1;  // 1 bit
  unsigned int bold: 1;
  unsigned int underlined: 1;
  unsigned int strikethrough: 1;
  unsigned int brightness: 4;  // 4 bits
} format_flags;

How does one represent such bit fields in a Fandango spec?

Representing Bits#

In Fandango, bits can be represented in Fandango using the special values 0 (for a zero bit) and 1 (for a non-zero bit). Hence, you can define a <bit> value as

<bit> ::= 0 | 1

With this, the above format_flag byte would be specified as

<start>         ::= <format_flag>
<format_flag>   ::= <italic> <bold> <underlined> <strikethrough> <brightness>
<italic>        ::= <bit>
<bold>          ::= <bit>
<underlined>    ::= <bit>
<strikethrough> ::= <bit>
<brightness>    ::= <bit>{4}
<bit>           ::= 0 | 1

A <format_flag> symbol would thus always consist of these eight bits. We can use the special option --format=bits to view the output as a bit stream:

$ fandango fuzz --format=bits -f bits.fan -n 1 --start-symbol='<format_flag>'

01000010

Tip

The combination of --format=bits and --start-symbol is particularly useful to debug bit fields.

Internally, Fandango treats individual flags as integers, too. Hence, we can also apply constraints to the individual flags. For instance, we can profit from the fact that Python treats 0 as False and 1 as True:

$ fandango fuzz --format=bits -f bits.fan -n 10 -c '<italic> and <bold>'

00000100
00111110
10110011
01011111
00110011
01111010
00011101
10100000
10110101
10000010

Fandango strictly follows a “left-to-right” order - that is, the order in which bits and bytes are specified in the grammar, the most significant bit is stored first.

Hence, we can also easily set the value of the entire brightness field using a constraint:

$ fandango fuzz --format=bits -f bits.fan -n 1 -c '<brightness> == 0b1111'

00101111

Note

Fandango always strictly follows a “left-to-right” order - that is, the order in which bits and bytes are specified in the grammar.

Of course, we can also give the number in decimal format:

$ fandango fuzz --format=bits -f bits.fan -n 1 -c '<brightness> == 15'

01011111
10001111

01111111
00101111

10101111
01101111

11001111
00011111
00111111

10111111

Note how the last four bits (the <brightness> field) are always set to 1111 - the number 15.

Important

When implementing a format, be sure to follow its conventions regarding

  • bit ordering (most or least significant bit first)

  • byte ordering (most or least significant byte first)

Parsing Bits#

Fandango also supports parsing inputs with bits. This is what happens if we send a byte \xf0 (the upper four bits set) to the parser:

$ printf "\xf0" | fandango parse -f bits.fan -o - --format=bits

11110000

We see that the input was properly parsed and decomposed into individual bits.

This is the resulting parse tree:

_images/d15b9d042456f2c1ffb1a08ef78a708e7fbbddc3393cb2069e814383d488bb8d.png

The grammar format shows us that the values are properly assigned:

$ printf '\xf0' | fandango parse -f bits.fan -o - --format=grammar

<start> ::= <format_flag>
  <format_flag> ::= <italic> <bold> <underlined> <strikethrough> <brightness>  # 0b11110000
    <italic> ::= <bit>
      <bit> ::= None + bits: 1  # Position 0x0000 (0), bit 7
    <bold> ::= <bit>
      <bit> ::= None + bits: 1  # Position 0x0000 (0), bit 6
    <underlined> ::= <bit>
      <bit> ::= None + bits: 1  # Position 0x0000 (0), bit 5
    <strikethrough> ::= <bit>
      <bit> ::= None + bits: 1  # Position 0x0000 (0), bit 4
    <brightness> ::= <bit> <bit> <bit> <bit>  # 0b0000
      <bit> ::= None + bits: 0  # Position 0x0000 (0), bit 3
      <bit> ::= None + bits: 0  # Position 0x0000 (0), bit 2
      <bit> ::= None + bits: 0  # Position 0x0000 (0), bit 1
      <bit> ::= None + bits: 0  # Position 0x0000 (0), bit 0

Note

To parse bits properly, they must come in multiples of eight.

Bits and Padding#

When generating binary inputs, you may need to adhere to specific lengths. Such lengths are often enforced by padding – that is, adding bits until the required length is achieved. For instance, let us assume you have a field consisting of some bits. However, the overall length of the field must be a multiple of eight to have it byte-aligned. For such padding, define the field as

<field> ::= <bits> <padding>
<padding> ::= 0*

combined with a constraint

where len(<field>) % 8 == 0

Note that applied on derivation trees, len() always returns the number of child elements, not the string length; here, we use this to access the number of elements in <field>.

Contents