When talking about data encoding, programmers think of JSON or XML. These text encoding formats are designed to be easily parsed by computer programs and are also human-readable. But they are not compact. Some performance critical and resource sensitive applications will want to encode data in a format that is as compact as possible. For example, consider how color values are represented as binary data. A color will be a combination of red, green and blue channels, each taking a value between 0-255. That means, each channel can be represented by an unsigned byte and a color value will consume 3 bytes (24-bits) in total. This encoding is quite easy to implement in a language like C:

#include <stdio.h>

typedef unsigned char byte;

struct RGB {
  byte red;
  byte green;
  byte blue;
};

int main() {
  struct RGB rgb = {255, 100, 23};
  printf("%d, %d, %d\n", rgb.red, rgb.green, rgb.blue);
  //-> 255, 100, 23
  return 0;
}

Encoding colors as a struct of three bytes is less memory-hungry than using some textual format like:

{
  "red": 255,
  "green": 100,
  "blue": 23
}

But using three full bytes still may not be compact enough for some applications. For instance, a memory-constrained embedded device may not be able to dedicate 24-bits for each color value. It may want to represent colors as 16-bit (or even smaller) values. A common encoding for 16-bit color values dedicate 5-bits each for the red and blue channels and 6-bits for the green channel. As you figure out the bit-wizardry required to implement that encoding in C (or language X), let me show you how to do that in Erlang:

-module(color).
-export([encode/3, decode/1]).

encode(R, G, B) -> 
    <<R:5, G:6, B:5>>.

decode(<<R:5, G:6, B:5>>) ->
    [R, G, B].

This is how we use the color module to encode and decode 16-bit colors:

%% Usage:
> c(color).
{ok,color}
> RGB = color:encode(4, 50, 21).
> color:decode(RGB).
[4,50,21]

The color module makes use of the binary data structure of Erlang. Binaries are written and printed as sequences of integers or strings, enclosed in double less-than and greater-than brackets as shown below:

<<10, 100, 34>>
<<10, 100, 34>>

Each value in a binary is by default an unsigned byte in the range 0-255. When the total number of bits is not divisible by 8, the resulting data structure is called a bitstring. The following program creates a bitstring of length 9:

> M = <<3:5, 12:4>>.
> byte_size(M).
2
> bit_size(M).
9

Here we used the bit syntax notation for packing individual bits or sequences of bits in binary data. As we saw earlier, to pack 5 bits, 6 bits and 5 bits to a 16-bit memory area, we just do this:

> Color = <<4:5, 50:6, 21:5>>.

The packed values can be extracted using simple pattern matching:

> <<R:5, G:6, B:5>> = Color.
> [R, G, B].
[4, 50, 21]

No messy low-level operations involving bit shifting and masking! The bit-syntax makes it super easy to decode binary encoded data streams and files. Some examples of such data are network packets and media files (MPEG, AVI etc).

As an extended example of using binaries and bit syntax, we show a program for extracting meta information from image files. Support for JPEG and PNG formats are implemented in the code below.

-module(imgmeta).
-export([decode/1]).

decode(FileName) ->
    case file:open(FileName, [read, binary]) of
    {ok, F} -> Result = decode_file(F),
           file:close(F),
           Result;
    X -> X
    end.    

decode_file(F) ->
    case file:read(F, 1024) of
    {ok, Data} ->
        decode_header(Data);
    Err -> Err
    end.

%% JPEG.
%% Ref: http://www.file-recovery.com/jpg-signature-format.htm
%% The JPEG header starts with two 2-byte constants - 0xFFD8 and 0xFFE0.
%% This is followed by a 2-byte length field, which we ignore.
%% Then follows 5 bytes with the null-terminated string identifier - "JFIF".
%% At this point we recognize this as a JPEG file and pass the rest of the binary data
%% to the `decode_jpeg` function.
decode_header(<<16#FFD8:16, 16#FFE0:16, _:16, 74, 70, 73, 70, 0, Rest/binary>>) ->
    decode_jpeg(Rest);

%% PNG
%% Ref: http://www.libpng.org/pub/png/spec/1.2/PNG-Rationale.html
%% A PNG file starts with the constant 8 bytes - 137  80  78  71  13  10  26  10.
%% This is followed by a 4-bytes chunk length and a header chunk (identified by the string "IHDR".
decode_header(<<137, 80, 78, 71, 13, 10, 26, 10, 13:32, 73, 72, 68, 82, Rest/binary>>) ->
    decode_png(Rest);
decode_header(_) ->
    {error, unsupported_image_format}.

decode_jpeg(<<Version:16, Units, HorizRes:16, VertRes:16, HorizPixels, VertPixels, _/binary>>) ->
    {ok, jpeg, {version, Version, units, Units, 
        horizontal_resolution, HorizRes, vertical_resolution, VertRes,
        horizontal_pixel_count, HorizPixels, vertical_pixel_count, VertPixels}}.

decode_png(<<Height:32, Width:32, BitDepth, ColorType, CompressionMethod, InterlaceMethod, _/binary>>) ->
    {ok, png, {width, Width, height, Height, bit_depth, BitDepth, color_type, ColorType,
           compression, CompressionMethod, interlace, InterlaceMethod}}.

Usage:

> c(imgmeta).
{ok,imgmeta}
> imgmeta:decode("img.jpeg").
{ok,jpeg,
    {version,258,units,0,horizontal_resolution,100,
             vertical_resolution,100,horizontal_pixel_count,0,
             vertical_pixel_count,0}}
> imgmeta:decode("img.png").
{ok,png,
    {width,923,height,800,bit_depth,8,color_type,6,compression,
           0,interlace,0}}
> imgmeta:decode("img.gif").
{error,unsupported_image_format}

As an exercise, you may want to add support for GIF files. Find out the binary layout of a GIF header, translate that to bit syntax and have some fun playing with bits and bytes!


Note that name and e-mail are required for posting comments