Binary pattern matching in Elixir with PNG parsing example
Dealing with binary data has always been a pickle in OOP language. Pattern matching is very fundamental to Elixir making the functions much more descriptive. I was very pleased to see that the pattern matching was not just limited to tuple, list etc. but extended to binary data as well. This makes it very easy to write or parse binary protocol in Elixir. In this post we'll take a look at how to do binary pattern matching and then write a simple parser for PNG binary format.
Binary pattern matching:
Creating binaries:
Let's start from the basics. In Elixir we can represent a binary number by <<A>> where A is some number in range of 0 - 255, if the number exceeds that range then it gets wrapped around so 256 will become 0. If you want to define multiple binary number lets say a 2 byte number then you separate it with , so <<1, 2>> creates a 2 byte number and in binary it will be 00000001 00000010 which translates to 258.
As you might have thought that if you want to write a value greater that 255 how would you do it. By default each number is a byte long but you can change a size when defining a binary. The <<1,2>> can be defined as << 258 :: size(16) >>, you can see both are same by << 1, 2 >> == << 258 :: size(16) >>.
The size is in bits so you can define any arbitrary number of bits and it will construct a binary number for you according to that. So << 1 :: size(3) >> translate to 001. Usually protocols that are not byte order are hard to deal with but this makes it very easy to deal with any arbitrary size of binary protocol.
If you try this in IEx, you might see that some numbers are printed as string, that is because in Elixir strings are just binaries, so where it sees that a binary can be represented as a string, it does that otherwise it falls back to printing the binary number under <<>>
Pattern match:
Pattern matching is similar to how you define the binary.
<<a, b>> = <<1,2>> will result in assigning 1 to a and 2 to b. Just like in defining binary you can specify size, you can do the same thing when pattern matching. <<a :: size(16)>> = <<1,2>> here a is 2 bytes long and its value becomes 258. If you leave out the size then it will consider it to be 1 byte long.
What if you just want to parse the first few bits/bytes and then store the rest (which is of arbitrary byte length) in another variable.
Lets say we have a binary protocol where header is the first byte and data is rest of the binary, we can extract that information as follows
iex(1)> << header :: size(8), data :: binary >> = <<1,2,3,4,5>>
<<1, 2, 3, 4, 5>>
iex(2)> header
1
iex(3)> data
<<2, 3, 4, 5>>
iex(4)> << header :: size(8), data :: binary >> = <<5,6>>
<<5, 6>>
iex(5)> header
5
iex(6)> data
<<6>>
As you can see that specifying binary at the end tell Elixir that whatever is remaining assign it to data but this only works if the remaining data is multiple of 8 bits. If you have the data which can be arbitrary bit length then you can add bitstring instead, so the pattern now looks like << header :: size(8), data :: bitstring >>.
Matching on arbitrary length can only be done at end of the pattern and not anywhere else, so something like << header :: binary, data :: size(8) will not work.
Another way of defining binary size (byte length) is << header :: binary - size(1), data :: binary>>. Here binary - size(1) means that its 1 byte length i.e. 8 bits.
If you have a static byte/bit in the binary format then you can also match it as follows
iex(7)> <<"MY_FORMAT", header :: size(8), data :: binary>> = <<"MY_FORMAT", 5,6>>
<<77, 89, 95, 70, 79, 82, 77, 65, 84, 5, 6>>
iex(8)> header
5
iex(9)> data
<<6>>
iex(10)> <<"MY_FORMAT", header :: size(8), data :: binary>> = <<"MY_FORMAT", 5,6,7,8>>
<<77, 89, 95, 70, 79, 82, 77, 65, 84, 5, 6, 7, 8>>
iex(11)> header
5
iex(12)> data
<<6, 7, 8>>
Parsing PNG binary format:
Let's first take a quick look at what the PNG binary format looks like.
# The first 33 bytes containing the information about PNG. Numbers in brackets are number of bits for that data
+------------------+
|0x89504E470D0A1A0A| <- Static binary in start of PNG file
+------------------+----+------------------+
| Length (32) |IHDR| Width (32) |
+------------------+----+-------+----------+--+
| Height (32) |Bit depth(8)|Color Type(8)|
+---------------------+---------+------+-------------------+
|Compression method(8)|Filter method(8)|Interlace method(8)|
+---------------+------------------------------------------+
| CRC (32) |
+---------------+
# PNG is composed of multiple chunks after the first part and each chunk has the same format
+--------------+----------------+-------------------+
| Length (32) | Chunk type (32)| Data (Length size)|
+--------------+----------------+-------------------+
| CRC (32) |
+--------------+
The above gives a description of what the PNG binary format looks like. It contains the first part, which is in start of all the PNG files, containing information about the image, followed by multiple chunks, each chunk follow the same pattern. This is how PNG is formed.
We are going to extract the information from an image file and put into a struct in Elixir. Lets see how we will pattern match the first part
<<0x89, 0x50, 0x4E, 0x47, 0x0D, 0x0A, 0x1A, 0x0A,
length :: size(32),
"IHDR",
width :: size(32),
height :: size(32),
bit_depth,
color_type,
compression_method,
filter_method,
interlace_method,
crc :: size(32),
chunks :: binary >>
We are just describing what the format looks like and Elixir takes care of everything. You can see that the chunks at the end will have rest of the data which we will pattern match on chunks format. The chunks is binary and not bitstring because PNG conforms to byte length and not some arbitrary bit length.
Let's see how to pattern match the chunk format
<<length :: size(32),
chunk_type :: size(32),
chunk_data :: binary - size(length),
crc :: size(32),
chunks :: binary>>
Here the most interesting thing is that we matched length in pattern and used it in the pattern as well. In Elixir pattern matching you can use the assigned variable in the pattern following it, thats why we are able to extract the chunk_data based on the length.
The final code looks like
defmodule Expng do
defstruct [:width, :height, :bit_depth, :color_type, :compression, :filter, :interlace, :chunks]
def png_parse(<<
0x89, 0x50, 0x4E, 0x47, 0x0D, 0x0A, 0x1A, 0x0A,
_length :: size(32),
"IHDR",
width :: size(32),
height :: size(32),
bit_depth,
color_type,
compression_method,
filter_method,
interlace_method,
_crc :: size(32),
chunks :: binary>>) do
png = %Expng{
width: width,
height: height,
bit_depth: bit_depth,
color_type: color_type,
compression: compression_method,
filter: filter_method,
interlace: interlace_method,
chunks: []}
png_parse_chunks(chunks, png)
end
defp png_parse_chunks(<<
length :: size(32),
chunk_type :: size(32),
chunk_data :: binary - size(length),
crc :: size(32),
chunks :: binary>>, png) do
chunk = %{length: length, chunk_type: chunk_type, data: chunk_data, crc: crc}
png = %{png | chunks: [chunk | png.chunks]}
png_parse_chunks(chunks, png)
end
defp png_parse_chunks(<<>>, png) do
%{png | chunks: Enum.reverse(png.chunks)}
end
end
Just use IEx to run File.read!("/path/to/png/file.png") |> Expng.png_parse and it should spit out the information it extracted from the PNG.
Now you don't need to fear binary format anymore, just go ahead and crack open those binary information using pattern matching awesomeness.
Japanese translation of this post - Thanks to @mathshun