Binary Data

Isn't It All 'Binary'?

• All data is stored as 1's and 0's
• But those 1's and 0's may represent:
  • Characters that can be displayed as text
  • Something else
• That “something else” is (misleadingly) called binary data
  • Usually means “anything you can't manipulate it with a standard text editor”
• Why use it?
  • Size
    • "10239472" is 8 bytes long
    • The 32-bit integer it represents is 4 bytes
    • "False" is 5 bytes, 0 is one bit (40:1)
  • Speed
    • Takes dozens of operations to add the integer represented by "34" to the one represented by "57"
  • Hardware interfaces
    • Somewhere, something has to convert the electrical signal from the gas chromatograph to a readable number
  • Lack of anything better
    • It's possible to represent images as text (ASCII art, PostScript)
    • But sound? Or movies?
• A lot of scientific data is stored in binary formats
  • Important to know how to work with it
  • But please, don't write code to do this unless you absolutely have to
    • Good libraries exist for working with every image, sound, and video format out there
• Comment on this slide

How Numbers Are Stored

• Positive numbers stored in base-2 format
  • 1001₂ is (1×2³)+(0×2²)+(0×2¹)+(1×2⁰) = 9
• Could use sign-and-value for negative numbers
  • 0011₂ would be 3₁₀, 1011₂ would be -3₁₀
  • But then there'd be two representations of zero (0000 and 1000)
• More efficient to use two's complement
  • “Roll over” when going below zero, like a car's odometer
  • 1111₂ is -1₁₀, 1110₂ is -2₁₀, etc.
  • 1000₂ is the most negative 4-bit integer, 0111₂ the most positive
  • Asymmetric: there is one more negative number than positive
    • Since there has to be room for 0 in the middle
• Comment on this slide

Bitwise Operators

• Like most languages, Python has four operators that work on bits

  • Name	Symbol	Purpose	Example
    And	&	1 if both bits are 1, 0 otherwise	0110 & 1010 = 0010
    Or	|	1 if either bit is 1	0110 & 1010 = 1110
    Xor	^	1 if the bits are different, 0 if they're the same	0110 & 1010 = 1100
    Not	~	Flip each bit	~0110 = 1001

    Table 20.1: Bitwise Operators in Python

  • Note: the name “xor” is short for “exclusive or”, i.e., either/or
• Common to store several independent yes-or-no flags as a set of bits
  • Example: need to record whether a sample contains any mercury, phosphorus, or chlorine
  • Use bit 1 for mercury, bit 2 for phosphorus, bit 3 for chlorine

  • Figure 20.1: Using Bits to Record Sets of Flags

  • Define constants to test for particular elements

  • #            hex     binary
    MERCURY    = 0x01  # 0001
    PHOSPHORUS = 0x02  # 0010
    CHLORINE   = 0x04  # 0100
    
    # Sample contains mercury and chlorine
    sample = MERCURY | CHLORINE
    print 'sample: %04x' % sample
    
    # Check for various elements
    for (flag, name) in [[MERCURY, "mercury"],
                         [PHOSPHORUS, "phosphorus"],
                         [CHLORINE, "chlorine"]]:
        if sample & flag:
            print 'sample contains', name
        else:
            print 'sample does not contain', name
    

    sample: 0005
    sample contains mercury
    sample does not contain phosphorus
    sample contains chlorine
    

• Can use and, or, and not to set specific bits to 1 or 0
  • To set the i^th of x to 1:
    • Create a value mask in which bit i is 1 and all others are 0
    • Use x = x | mask
  • To set the i^th of x to 0:
    • Create a value mask in which bit i is 1 and all others are 0
    • Negate it using ~, so that the i^th bit is 0, and all the others are 1
    • Use x = x & mask
• Comment on this slide

Shifting

• Shifting an integer's bits left N places written as x << N
  • Each leftward shift corresponds to multiplying by 2
  • Just as shifting a decimal number left corresponds to multiplying by 10
  • Example: 6<<2 is 0110₂<<2, or 1100₂, which is 12
• Shifting a number right corresponds to division by 2 (throwing away the remainder)
  • 7₁₀>>1 is 0111₂>>1, or 0011₂, which is 3₁₀
• Shifting is not more efficient than multiplication and division on modern computers
• What happens if the top bit changes value as a result of a shift?
  • 6₁₀<<1 = 0110₂<<1 = 1100₂
  • On a 4-bit machine, this is -4₁₀, not 12₁₀
  • Some machines preserve the sign bit when shifting down
    • So 1100₂>>1 = 1110₂, instead of 0110₂
    • Depends on the hardware being used
    • Java provides a separate operator for this
• Comment on this slide

Floating Point

• Floating point numbers are more complicated
  • A 32-bit float has:
    • One bit for the sign
    • 23 bits for the mantissa (or value)
    • 8 bits for the exponent

    • Figure 20.2: Floating Point Representation

• This means that you can only represent a fixed set of values
  • If the actual value isn't in that set, you must settle for the closest available approximation
• Consequence #1: values are unevenly spaced
  • Imagine we only had 6 bits for each floating-point number (1 sign, 3 mantissa, 2 exponent)
  • Means less absolute precision for numbers with larger magnitudes

  • Figure 20.3: Uneven Spacing of Floating-Point Numbers

• Consequence #2: roundoff errors
  • Our system can represent 6, and it can represent ¼, but not 5¾
  • So 6 - 0.25 is 6, not 5.75
    • And if 6 - 0.25 - 0.25 - 0.25 - 0.25 is evaluated left to right, the answer is still 6
  • This is not random
    • Happens exactly the same way every time
  • But it is very hard to reason about
    • Which is why people get Ph.D.'s in numerical analysis
• Comment on this slide

Binary I/O

• Read and write binary data using standard file methods
  • f.read(N) reads (up to) next N bytes
    • Result is returned as a string, but there's no guarantee its contents are readable
    • If the file is empty, returns None
  • f.write(str) writes the bytes in the string str
• Caution: must open files in binary mode on Windows
  • input = open(filename, 'rb') (and similarly for output)
  • Otherwise, the low-level routines Python relies on convert Windows line endings "\r\n" to Unix-style "\n"…
  • …which is an unkind thing to do to an image
  • Example: open a file using "r", then in "rb"
    • Identical on Unix, but different on Windows

    • import sys
      print sys.platform
      for mode in ('r', 'rb'):
        f = open('open_binary.py', mode)
        s = f.read(40)
        f.close()
        print repr(s)
      

      linux2
      'import sys\nprint sys.platform\nfor mode i'
      'import sys\nprint sys.platform\nfor mode i'
      

• Comment on this slide

Packing and Unpacking

• In C and Fortran, an integer is a raw 32-bit value
  • fwrite(&array, sizeof(int), 3, file) will write 3 4-byte integers from address array to file
• Python, Java, and other languages usually don't use raw values
  • There's no guarantee that things like lists are stored contiguously in memory…
  • …so programs need to pack data into contiguous bytes for writing…
  • …and unpack those bytes to recreate the structures when reading
• Packing looks a lot like formatting a string
  • A format specifies the data types being packed (including sizes, where appropriate)
  • This format exactly determines how much memory is required by the packed representation
  • The result of packing is a chunk of bytes
    • Stored as a string in Python
    • But as mentioned above, it's not a string of characters

  • Figure 20.4: Packing Data

• Unpacking reverses this process
  • Read bytes from a “string” according to a format
  • Use the data in these bytes to create Python data structures
  • Return the result as a tuple of values

  • Figure 20.5: Unpacking Data

• Comment on this slide

The struct Module

• Use Python's struct module to pack and unpack
  • pack(fmt, v1, v2, …) packs the values v1, v2, etc. according to fmt, returning a string
  • unpack(fmt, str) unpacks the values in str according to fmt, returning a tuple
  • calcsize(fmt) calculates how large (in bytes) the data produced using fmt will be
    • Packing and unpacking are always fixed-size operations
• Format specifiers

  • Format	Meaning
    "c"	Single character (i.e., string of length 1)
    "B"	Unsigned 8-bit integer
    "h"	Short (16-bit) integer
    "i"	32-bit integer
    "f"	32-bit float
    "d"	Double-precision (64-bit) float
    "2"	String of fixed size (see below)

    Table 20.2: Format Specifiers in Python

  • Any format can be preceded by a count
    • E.g., "4i" is four integers
  • Must always specify the size of strings
    • E.g., "4s" for a 4-character string
    • Otherwise, how would unpack know how much data to use?
  • How much data is packed is specified by the format
    • Can pack the lowest 8 or 16 bits of an integer using "B" or "h" instead of the full 32
• Example: pack two integers, using only 16 bits for each

  • import struct
    
    fmt = 'hh' # two 16-bit integers
    
    x = 31
    y = 65
    
    binary = struct.pack(fmt, x, y)
    print 'binary representation:', repr(binary)
    
    normal = struct.unpack(fmt, binary)
    print 'back to normal:', normal
    

    binary representation: '\x1f\x00A\x00'
    back to normal: (31, 65)
    

  • Uh, what's '\x1f\x00A\x00'?
  • If Python finds a character in a string that doesn't have a printable representation, it prints a 2-digit hexadecimal (base-16) escape sequence
    • Uses the letters A-F (or a-f) to represent the digits from 10 to 15
  • So this string represents the four bytes ['\x1f', '\x00', 'A', '\x00']
    • 1f₁₆ is (1×16 + 15), or 31
    • ASCII code for the letter "A" is 65₁₀
• Note that the least significant byte of the integer comes first
  • This is called little-endian, and is used by all Intel processors
  • Other chips put the most significant byte first (big-endian)
  • If you move data from one architecture to another, it's your responsibility to flip the bytes…
  • …because the machine doesn't know what the bytes mean

  • import struct
    
    packed = struct.pack('4c', 'a', 'b', 'c', 'd')
    print 'packed string:', repr(packed)
    
    left16, right16 = struct.unpack('hh', packed)
    print 'as two 16-bit integers:', left16, right16
    
    all32 = struct.unpack('i', packed)
    print 'as a single 32-bit integer', all32[0]
    
    float32 = struct.unpack('f', packed)
    print 'as a 32-bit float', float32[0]
    

    packed string: 'abcd'
    as two 16-bit integers: 25185 25699
    as a single 32-bit integer 1684234849
    as a 32-bit float 1.67779994081e+22
    

• Can be very hard to track down errors in packing and unpacking
  • Unpacking the wrong type, or too many/too few values, produces garbage
• Comment on this slide

Packing Variable-Length Data

• How to store a variable-length vector of integers?
  • Store the number of elements in a fixed-size header
  • Then store that many integers one by one

  • Figure 20.6: Packing a Variable-Length Vector

• Packing is easy:

  • def packVec(vec):
        buf = struct.pack('i', len(vec))
        for v in vec:
            buf += struct.pack('i', v)
        return buf
    

• Unpacking is a little harder
  • Use calcsize('i') instead of hard-coding the number 4
    • 64-bit machines are on their way…
  • Each pass through the unpacking loop, have to step up to the right location in the packed string

  • def unpackVec(buf):
    
        # Get the count of the number of elements in the vector.
        intSize = struct.calcsize('i')
        count = struct.unpack('i', buf[0:intSize])[0]
    
        # Get 'count' values, one by one.
        pos = intSize
        result = []
        for i in range(count):
            v = struct.unpack('i', buf[pos:pos+intSize])
            result.append(v[0])
            pos += intSize
    
        return result
    

• And then we test:

  • if __name__ == '__main__':
    
        tests = [
            [],
            [1],
            [1, 2],
            [-3, 456, 7890]
        ]
    
        for t in tests:
            s = packVec(t)
            v = unpackVec(s)
            assert v == t
    

• Problem: what if you want to pack strings, but don't know their length in advance?
• Solution: create the format string on the fly, and save the string's length as well as its characters

  • import struct
    
    def packStrings(strings):
        result = ''
        for s in strings:
            length = len(s)
            format = 'i%ds' % length
            result += struct.pack(format, length, s)
        return result
    
    def unpackStrings(buf):
        intSize = struct.calcsize('i')
        pos = 0
        result = []
        while pos < len(buf):
            length = struct.unpack('i', buf[pos:pos+intSize])[0]
            pos += intSize
            format = '%ds' % length
            s = struct.unpack(format, buf[pos:pos+length])[0]
            pos += length
            result.append(s)
        return result
    
    if __name__ == '__main__':
        tests = ['', 'a', 'bcd']
        for i in range(len(tests)):
            t = tests[0:i+1]
            buffer = packStrings(t)
            result = unpackStrings(buffer)
            assert result == t
    

• Comment on this slide

Metadata

• Literally, “data about data”
  • I.e., data that describes other data, such as the date it was collected, or its format
• When creating binary files, put a header at the start of the file that describes the format of the data the file contains
  • Advantages:
    • One parser handles all data files
    • Can't lose the format: programs come and go, but data is forever
  • Disadvantages:
    • Slower (generality always is)
    • Reader is more complicated than a single special-purpose reader would be…
    • …but simpler than the sum of all the special-purpose readers you'd have to write…
    • …and you only have to debug it once
• Files have a three-part structure:
  • Integer (fixed size) recording the length of the metadata
  • Metadata (N bytes) describing the format of the records in the file
  • The records themselves

  • Figure 20.7: Structure of a Binary File With Metadata

• Step 1: store a list of identically-structured records to a file

  • def store(outstream, format, data):
        '''Store records in a file.  Each record is either a list or a
        tuple; all records must have exactly the same format.'''
    
        # Length of metadata.
        s = struct.pack("i", len(format))
        outstream.write(s)
    
        # Metadata.
        outstream.write(format)
    
        # Records.
        for d in data:
            d = [format] + list(d)          # Build pack's argument list
            s = struct.pack(*d)             # Apply pack to those arguments
            outstream.write(s)
    

  • Notice how struct.pack is called
    • It takes each value to be packed as a separate argument, rather than taking a list of values
    • First argument has to be the format
    • So create a list with the format, and the values to be packed, and apply struct.pack to it
    • Common pattern when using variable number of arguments
• Step 2: unpack the bytes created by store
  • Read the size of the metadata, then the metadata, then the data

  • def retrieve(instream):
    
        '''Retrieve records from a file whose format is:
           'i'      : length of metadata
           metadata : record format descriptor
           records  : actual data'''
    
        # Length of metadata.
        numBytes = struct.calcsize("i")
        s = instream.read(numBytes)
        formatLen = struct.unpack("i", s)[0]
    
        # Metadata.
        format = instream.read(formatLen)
        recordLen = struct.calcsize(format)
    
        # Records.
        data = []
        s = instream.read(recordLen)
        while s:
            assert len(s) == recordLen
            d = list(struct.unpack(format, s))
            data.append(d)
            s = instream.read(recordLen)
    
        # Done
        return data
    

  • Notice the assert in the reading loop
    • Defensive programming
• Step 3: test that it works
  • Just as important as steps 1 and 2

  • if __name__ == '__main__':
    
        from cStringIO import StringIO
    
        tests = [
            ['i',   [[1]]],
            ['i',   [[1], [2]]],
            ['3s',  [['xyz']]],
            ['3s',  [['abc'], ['def']]],
            ['f3s', [[1.0, 'pqr']]],
            ['f3s', [[2.0, 'stu'], [3.0, 'vwx']]]
        ]
    
        for (format, data) in tests:
            outstream = StringIO()
            store(outstream, format, data)
            instream = StringIO(outstream.getvalue())
            dup = retrieve(instream)
            assert data == dup
    

• Comment on this slide