PackBits

PackBits is a fast, simple lossless compression scheme for run-length encoding of data.[1]

Apple introduced the PackBits format with the release of MacPaint on the Macintosh computer. This compression scheme can be used in TIFF files. TGA files also use this RLE compression scheme, but treats data stream as pixels instead of bytes. Packbit compression was also used in ILBM files.

A PackBits data stream consists of packets with a one-byte header followed by data. The header is a signed byte; the data can be signed, unsigned, or packed (such as MacPaint pixels).

In the following table, n is the value of the header byte as a signed integer.

Header byte Data following the header byte
0 to 127 (1 + n) literal bytes of data
−1 to −127 One byte of data, repeated (1 − n) times in the decompressed output
−128 No operation (skip and treat next byte as a header byte)

Note that interpreting 0 as positive or negative makes no difference in the output. Runs of two bytes adjacent to non-runs are typically written as literal data. There is no way based on the PackBits data to determine the end of the data stream; that is to say, one must already know the size of the compressed or uncompressed data before reading a PackBits data stream to know where it ends.

Apple Computer (see the external link) provides this short example of packed data: FE AA 02 80 00 2A FD AA 03 80 00 2A 22 F7 AA

The following code, written in Microsoft VBA, unpacks the data: 

Sub UnpackBitsDemo()
   Dim File As Variant
   Dim MyOutput As String
   Dim Count As Long
   Dim i As Long, j As Long
  
   File = "FE AA 02 80 00 2A FD AA 03 80 00 2A 22 F7 AA"
   File = Split(File, " ")
   
   For i = LBound(File) To UBound(File)
      Count = Application.WorksheetFunction.Hex2Dec(File(i))
      Select Case Count
      Case Is >= 128
         Count = 256 - Count 'Two's Complement
         For j = 0 To Count 'zero-based
            MyOutput = MyOutput & File(i + 1) & " "
         Next j
         i = i + 1 'Adjust the pointer
      Case Else
         For j = 0 To Count 'zero-based
            MyOutput = MyOutput & File(i + j + 1) & " "
         Next j
         i = i + j 'Adjust the pointer
      End Select
   Next i

   Debug.Print MyOutput
   'AA AA AA 80 00 2A AA AA AA AA 80 00 2A 22 AA AA AA AA AA AA AA AA AA AA
End Sub

The same implementation in JavaScript: 

/**
 * Helper functions to create readable input and output
 * 
 * Also, see this fiddle for interactive PackBits decoder:
 * https://jsfiddle.net/y13xkh65/3/
 */

function str2hex (str) {
    return str.split('').map(function (char) {
        var value = char.charCodeAt(0);

        return ((value < 16 ? '0' : '') + value.toString(16)).toUpperCase();
    }).join(' ');
}

function hex2str (hex) {
    return hex.split(' ').map(function (string) {
        return String.fromCharCode(parseInt(string, 16));
    }).join('');
}

/**
 * PackBits unpack function
 * 
 * @param {String} data
 * @return {String}
 */
function unpackBits (data) {
    var output = '',
    i = 0;

    while (i < data.length) {
        var hex = data.charCodeAt(i);

        if (hex == 128) {
            // Do nothing, nop
        }
        else if (hex > 128) {
            // This is a repeated byte
            hex = 256 - hex;

            for (var j = 0; j <= hex; ++j) {
                output += data.charAt(i + 1);
            }

            ++i;
        }
        else {
            // These are literal bytes
            for (var j = 0; j <= hex; ++j) {
                output += data.charAt(i + j + 1);
            }

            i += j;
        }

        ++i;
    }

    return output;
}

var original = 'FE AA 02 80 00 2A FD AA 03 80 00 2A 22 F7 AA',
    data = unpackBits(hex2str(original));

// Output is: AA AA AA 80 00 2A AA AA AA AA 80 00 2A 22 AA AA AA AA AA AA AA AA AA AA
console.log(str2hex(data));

References

  1. ^ Hernández León, Raudel; Pérez Suárez, Airel; Feregrino-Uribe, Claudia (2010). "A Compression Algorithm for Mining Frequent Itemsets" (PDF). New Trends in Electrical Engineering, Automatic Control, Computing and Communication Sciences. pp. 485–499. Archived from the original (PDF) on 2015-06-16.

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.