Implementation of the PackBits algorithm

Question

I want to implement the PackBits algorithm.

The background is that I am writing some code for an ONVIF camera. I want to compress a pattern/string of 1's and 0's with PackBits, and I also want to decode an existing packed string.

JavaScript has my preference, but C, PHP or similar will do too.

I have been looking for some examples, but couldn't find any.

How can I implement the PackBits algorithm?

Answer 1

You can use the following pack/unpack functions. I added a demo with the example data on Wikipedia:

const pack = s =>
    s.match(/(.)\1{1,127}|(?:(.)(?!\2)){1,128}/gs).map(s =>
        s[0] === s[1] ? String.fromCharCode(257-s.length) + s[0]
                      : String.fromCharCode(s.length-1) + s
    ).join("");

function unpack(s) {
    let res = "";
    let i = 0;
    while (i < s.length) {
        let hdr = s.charCodeAt(i++);
        res += hdr > 128 ? s[i++].repeat(257 - hdr)
             : hdr < 128 ? s.slice(i, i += hdr+1)
             : "";
    }
    return res;
}

const toHex = s => Array.from(s, c => c.charCodeAt().toString(16).padStart(2, "0")).join(" ");

// Demo
let s = "\xAA\xAA\xAA\x80\x00\x2A\xAA\xAA\xAA\xAA\x80\x00\x2A\x22\xAA\xAA\xAA\xAA\xAA\xAA\xAA\xAA\xAA\xAA";
console.log(toHex(s));

let packed = pack(s);
console.log(toHex(packed));

let unpacked = unpack(packed);
console.log(toHex(unpacked));

console.log(s === unpacked ? "OK" : "Mismatch!");

Note that the code on Wikipedia does not deal with the header value (128) according to the specification. A header value of 128, which as a signed byte is -128, should be skipped -- it has no payload.

As you mentioned base64 encoding in comments: JavaScript has atob and btoa functions for that purpose.

Without s flag, with a base64 encoded example

If you don't have support for the s flag for regexes, then in the regex replace each . with [^].

In this version I use that regular expression, and include an example that uses a base64 encoded string (the one you mention in comments):

const pack = s =>
    s.match(/([^])\1{1,127}|(?:([^])(?!\2)){1,128}/g).map(s =>
        s[0] === s[1] ? String.fromCharCode(257-s.length) + s[0]
                      : String.fromCharCode(s.length-1) + s
    ).join("");

function unpack(s) {
    let res = "";
    let i = 0;
    while (i < s.length) {
        let hdr = s.charCodeAt(i++);
        res += hdr > 128 ? s[i++].repeat(257 - hdr)
             : hdr < 128 ? s.slice(i, i += hdr+1)
             : "";
    }
    return res;
}

const toHex = s => Array.from(s, c => c.charCodeAt().toString(16).padStart(2, "0")).join(" ");

// Demo
let base64encoded = "0P8A8A==";
console.log("packed, base64 encoded input: ", base64encoded);

let s = atob(base64encoded);
console.log("base64 decoded: ", toHex(s));

let unpacked = unpack(s);
console.log("unpacked: ", toHex(unpacked));