PackBits算法的实现

Question

我想实现 PackBits 算法。

背景是我正在为 ONVIF 相机编写一些代码。我想用 PackBits 压缩 1 和 0 的 pattern/string，我还想解码现有的打包字符串。

JavaScript 是我的偏好，但 C、PHP 或类似的也可以。

我一直在寻找一些示例，但找不到。

如何实现 PackBits 算法？

Answer 1

PackBits 算法的维基百科页面有一个 JS 实现示例和其他链接。它有以下评论，其中还包括一个 JSFiddle：

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

一个 PackBits 数据流由带有 one-byte header 后跟数据的数据包组成。 header 是一个带符号的字节；数据可以是有符号的、无符号的或打包的（例如 MacPaint 像素）。

在下面的table中，n是header字节的值作为有符号整数。

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)

这是一个相当简单的游程编码算法。

有关 Typescript 中的实现，请参阅：https://github.com/fiahfy/packbits。

https://en.wikipedia.org/wiki/PackBits

Answer 2

您可以使用以下 pack/unpack 功能。我在 Wikipedia:

上添加了一个带有示例数据的演示

const pack = s =>
    s.match(/(.){1,127}|(?:(.)(?!)){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!");

请注意，根据规范，维基百科上的代码并未处理 header 值 (128)。 header 值为 128，作为带符号的字节是 -128，应该被跳过——它没有有效载荷。

正如您在评论中提到的 base64 编码：JavaScript 具有用于该目的的 atob and btoa 函数。

没有`s`标志，有一个base64编码的例子

如果您不支持正则表达式的 s 标志，则在正则表达式中将每个 . 替换为 [^]。

在此版本中，我使用该正则表达式，并包含一个使用 base64 编码字符串的示例（您在评论中提到的那个）：

const pack = s =>
    s.match(/([^]){1,127}|(?:([^])(?!)){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));

PackBits算法的实现

Implementation of the PackBits algorithm

javascript

algorithm

run-length-encoding

没有`s`标志，有一个base64编码的例子

PackBits算法的实现

Implementation of the PackBits algorithm

javascript

algorithm

run-length-encoding

没有s标志，有一个base64编码的例子

没有`s`标志，有一个base64编码的例子