Month: February 2013

Bit packing and unpacking is a handy way of consolidating multiple data values into a single variable, thus compressing the amount of data being stored or transmitted. The number of values that can be stored depends upon the width of the data to be stored as well as the type of the value that it is packed into. A simple byte can store up to 8 bits of data. Larger types such as ints can store up to 16, 32 or 64 bits. This is an especially efficient technique for storing several small-width values, often smaller than the smallest width supported by a platform (such as byte or boolean flags) into a single large value such as a 32-bit integer.

Bit flags are commonly used for implementing low-level features, such as storing file access-permissions or packing values into a single value before transmitting across a bus. However, they can be applied with equal ease to higher level tasks such as storing user preferences or choosing which widgets to display from an enumerated list. We will see here how to use bit flags to store font formatting preferences, and apply them later to a label.

Bitwise Operators

There are a couple of operators we need to understand before we can move on to the implementation. Bitwise operators, by definition, work on individual bits inside a value. Since they are implemented directly by the processor itself, they are much faster than arithmetic operators such as division and multiplication. We will use bitwise AND (&), bitwise OR (|) and left shifts (<<) in this exercise.

A bitwise AND operation takes the binary representations of two values and performs a logical AND operation on each bit. The result is 1 in every position where both the bits are 1, and 0 if either or both bits are 0.

    001010
AND 011011
    ------
    001010

Bitwise OR on the other hand, compares two bits in corresponding positions, and sets the result to 1 if either of them is 1, or to 0 if both of them are 0.

    001010
OR  011011
    ------
    011011

Bitwise left shift operator moves individual bits within a single value by the number of places specified in the second operand. The value is padded with 0s on the right, and the left-most bits are dropped off.

    001010 << 1 = 010100

Implementation

We set up a simple Windows Forms project and draw three checkboxes and one label on the form. The aim is to have the checkboxes control three font properties of the label – weight, style and underlining. All checkboxes are given appropriate labels and configured to execute the _changeFormatting method of the form every time the CheckStateChanged event is fired. The code for this method is shown below.

private void ChangeFormatting(object sender, EventArgs e)
{
    byte flags = 0;

    flags = (byte)(
        Convert.ToByte(this.chkUnderline.Checked) << 2 |
        Convert.ToByte(this.chkItalic.Checked) << 1 |
        Convert.ToByte(this.chkBold.Checked)
        );

    Font f = new Font(this.label1.Font.FontFamily, this.label1.Font.Size, (FontStyle)(
        (flags & (byte)FontStyle.Underline) |
        (flags & (byte)FontStyle.Italic) |
        (flags & (byte)FontStyle.Bold)
        ));

    this.label1.Font = f;
}

Packing

In the first statement, the flags variable is populated with the values of each checkbox. We want to store the three flags in the last three bits of a single byte.

In order to do so, we take the value of each boolean (either true or false), convert it into a byte, then shift it by an appropriate number of positions. The value of the underline flag is to be stored in the 2nd bit (starting from 0). So we left-shift its value by 2. Similarly, the italic flag is stored in the 1st position, so its boolean value is shifted by 1. The value of the bold flag does not need to be shifted at all.

    00000001 << 2 = 00000100 // Underline
    00000001 << 1 = 00000010 // Italic
    00000001                 // Bold (no shifting required)

A consolidated value can be generated by ORing the three values together.

    00000100
 OR 00000010
 OR 00000001
    --------
    00000111 // Decimal value 7

    00000000
 OR 00000010
 OR 00000001
    --------
    00000011 // Decimal value 3

    00000100
 OR 00000000
 OR 00000001
    --------
    00000101 // Decimal value 5

The decimal value can then be stored in a database or other persistent storage system as an integer or byte. This is better than having to store three boolean fields. This information can transmitted across systems too as a packed unit, to be unpacked later only when the preferences have to be applied to a display element.

In our example, we are unpacking and applying the values immediately for brevity. But a more practical situation would probably involve serializing the value somewhere, then deserializing and applying the font properties later at another location.

Unpacking

In order to apply the font styles on a display element, the individual values of each style parameter must be extracted from the packed value and then applied. The .NET framework defines enumerations for each of these style parameters in the System.Drawing.FontStyle enum. The values for each style parameter are listed below.

You will notice that each enumeration is double the value of its predecessor, hence moving the digit 1 by one position leftwards with every increase. This is a key feature of bit flags. Each element differs from the others only in the position of the 1 bit. Thus, the value of a given flag can be extracted from the packed value by ANDing the packed value with the value of the enumeration.

     00000111 // Packed value decimal 7
AND  00000100 // Underline enum decimal 4
     --------
     00000100 // Result - show underlines

This operations shows that the value of the underline flag is true. If the packed value was the decimal 3 instead of 7, then the operation would play out as shown below, resulting in the value 0 for the underline flag.

     00000011 // Packed value
AND  00000100 // Underline enum
     --------
     00000010 // Result - hide underlines

All that is needed then is to convert the result byte into a boolean and apply it wherever required. In our example above, the constructor of the Font class requires the values packed together any way as a FontStyle enum. To do this, each bit is ANDed with its corresponding enum, then all of them are combined together again using an OR operation. The resultant byte is cast into a FontStyle before being passed to the constructor.