Added support for ZRLE encoding

Fixed eslint warnings

Improved memory usage of zrle decoding.  Added unit tests for zrle decoding.

Added support for ZRLE encoding

Fixed eslint warnings

Reverted allowIncomplete changes to Inflator

Fixed failing tests for zrle decoder.

3 files changed, 312 insertions, 0 deletions

diff --git a/core/decoders/zrle.js b/core/decoders/zrle.js
new file mode 100644
index 0000000..97fbd58
--- /dev/null
+++ b/core/decoders/zrle.js
@@ -0,0 +1,185 @@
+/*
+ * noVNC: HTML5 VNC client
+ * Copyright (C) 2021 The noVNC Authors
+ * Licensed under MPL 2.0 (see LICENSE.txt)
+ *
+ * See README.md for usage and integration instructions.
+ *
+ */
+
+import Inflate from "../inflator.js";
+
+const ZRLE_TILE_WIDTH = 64;
+const ZRLE_TILE_HEIGHT = 64;
+
+export default class ZRLEDecoder {
+    constructor() {
+        this._length = 0;
+        this._inflator = new Inflate();
+
+        this._pixelBuffer = new Uint8Array(ZRLE_TILE_WIDTH * ZRLE_TILE_HEIGHT * 4);
+        this._tileBuffer = new Uint8Array(ZRLE_TILE_WIDTH * ZRLE_TILE_HEIGHT * 4);
+    }
+
+    decodeRect(x, y, width, height, sock, display, depth) {
+        if (this._length === 0) {
+            if (sock.rQwait("ZLib data length", 4)) {
+                return false;
+            }
+            this._length = sock.rQshift32();
+        }
+        if (sock.rQwait("Zlib data", this._length)) {
+            return false;
+        }
+
+        const data = sock.rQshiftBytes(this._length);
+
+        this._inflator.setInput(data);
+
+        for (let ty = y; ty < y + height; ty += ZRLE_TILE_HEIGHT) {
+            let th = Math.min(ZRLE_TILE_HEIGHT, y + height - ty);
+
+            for (let tx = x; tx < x + width; tx += ZRLE_TILE_WIDTH) {
+                let tw = Math.min(ZRLE_TILE_WIDTH, x + width - tx);
+
+                const tileSize = tw * th;
+                const subencoding = this._inflator.inflate(1)[0];
+                if (subencoding === 0) {
+                    // raw data
+                    const data = this._readPixels(tileSize);
+                    display.blitImage(tx, ty, tw, th, data, 0, false);
+                } else if (subencoding === 1) {
+                    // solid
+                    const background = this._readPixels(1);
+                    display.fillRect(tx, ty, tw, th, [background[0], background[1], background[2]]);
+                } else if (subencoding >= 2 && subencoding <= 16) {
+                    const data = this._decodePaletteTile(subencoding, tileSize, tw, th);
+                    display.blitImage(tx, ty, tw, th, data, 0, false);
+                } else if (subencoding === 128) {
+                    const data = this._decodeRLETile(tileSize);
+                    display.blitImage(tx, ty, tw, th, data, 0, false);
+                } else if (subencoding >= 130 && subencoding <= 255) {
+                    const data = this._decodeRLEPaletteTile(subencoding - 128, tileSize);
+                    display.blitImage(tx, ty, tw, th, data, 0, false);
+                } else {
+                    throw new Error('Unknown subencoding: ' + subencoding);
+                }
+            }
+        }
+        this._length = 0;
+        return true;
+    }
+
+    _getBitsPerPixelInPalette(paletteSize) {
+        if (paletteSize <= 2) {
+            return 1;
+        } else if (paletteSize <= 4) {
+            return 2;
+        } else if (paletteSize <= 16) {
+            return 4;
+        }
+    }
+
+    _readPixels(pixels) {
+        let data = this._pixelBuffer;
+        const buffer = this._inflator.inflate(3*pixels);
+        for (let i = 0, j = 0; i < pixels*4; i += 4, j += 3) {
+            data[i]     = buffer[j];
+            data[i + 1] = buffer[j + 1];
+            data[i + 2] = buffer[j + 2];
+            data[i + 3] = 255;  // Add the Alpha
+        }
+        return data;
+    }
+
+    _decodePaletteTile(paletteSize, tileSize, tilew, tileh) {
+        const data = this._tileBuffer;
+        const palette = this._readPixels(paletteSize);
+        const bitsPerPixel = this._getBitsPerPixelInPalette(paletteSize);
+        const mask = (1 << bitsPerPixel) - 1;
+
+        let offset = 0;
+        let encoded = this._inflator.inflate(1)[0];
+
+        for (let y=0; y<tileh; y++) {
+            let shift = 8-bitsPerPixel;
+            for (let x=0; x<tilew; x++) {
+                if (shift<0) {
+                    shift=8-bitsPerPixel;
+                    encoded = this._inflator.inflate(1)[0];
+                }
+                let indexInPalette = (encoded>>shift) & mask;
+
+                data[offset] = palette[indexInPalette * 4];
+                data[offset + 1] = palette[indexInPalette * 4 + 1];
+                data[offset + 2] = palette[indexInPalette * 4 + 2];
+                data[offset + 3] = palette[indexInPalette * 4 + 3];
+                offset += 4;
+                shift-=bitsPerPixel;
+            }
+            if (shift<8-bitsPerPixel && y<tileh-1) {
+                encoded =  this._inflator.inflate(1)[0];
+            }
+        }
+        return data;
+    }
+
+    _decodeRLETile(tileSize) {
+        const data = this._tileBuffer;
+        let i = 0;
+        while (i < tileSize) {
+            const pixel = this._readPixels(1);
+            const length = this._readRLELength();
+            for (let j = 0; j < length; j++) {
+                data[i * 4] = pixel[0];
+                data[i * 4 + 1] = pixel[1];
+                data[i * 4 + 2] = pixel[2];
+                data[i * 4 + 3] = pixel[3];
+                i++;
+            }
+        }
+        return data;
+    }
+
+    _decodeRLEPaletteTile(paletteSize, tileSize) {
+        const data = this._tileBuffer;
+
+        // palette
+        const palette = this._readPixels(paletteSize);
+
+        let offset = 0;
+        while (offset < tileSize) {
+            let indexInPalette = this._inflator.inflate(1)[0];
+            let length = 1;
+            if (indexInPalette >= 128) {
+                indexInPalette -= 128;
+                length = this._readRLELength();
+            }
+            if (indexInPalette > paletteSize) {
+                throw new Error('Too big index in palette: ' + indexInPalette + ', palette size: ' + paletteSize);
+            }
+            if (offset + length > tileSize) {
+                throw new Error('Too big rle length in palette mode: ' + length + ', allowed length is: ' + (tileSize - offset));
+            }
+
+            for (let j = 0; j < length; j++) {
+                data[offset * 4] = palette[indexInPalette * 4];
+                data[offset * 4 + 1] = palette[indexInPalette * 4 + 1];
+                data[offset * 4 + 2] = palette[indexInPalette * 4 + 2];
+                data[offset * 4 + 3] = palette[indexInPalette * 4 + 3];
+                offset++;
+            }
+        }
+        return data;
+    }
+
+    _readRLELength() {
+        let length = 0;
+        let current = 0;
+        do {
+            current = this._inflator.inflate(1)[0];
+            length += current;
+        } while (current === 255);
+        return length + 1;
+    }
+}
diff --git a/core/rfb.js b/core/rfb.js
index ea3bf58..0be2fa6 100644
--- a/core/rfb.js
+++ b/core/rfb.js
@@ -32,6 +32,7 @@ import RREDecoder from "./decoders/rre.js";
 import HextileDecoder from "./decoders/hextile.js";
 import TightDecoder from "./decoders/tight.js";
 import TightPNGDecoder from "./decoders/tightpng.js";
+import ZRLEDecoder from "./decoders/zrle.js";
 
 // How many seconds to wait for a disconnect to finish
 const DISCONNECT_TIMEOUT = 3;
@@ -218,6 +219,7 @@ export default class RFB extends EventTargetMixin {
         this._decoders[encodings.encodingHextile] = new HextileDecoder();
         this._decoders[encodings.encodingTight] = new TightDecoder();
         this._decoders[encodings.encodingTightPNG] = new TightPNGDecoder();
+        this._decoders[encodings.encodingZRLE] = new ZRLEDecoder();
 
         // NB: nothing that needs explicit teardown should be done
         // before this point, since this can throw an exception
@@ -1772,6 +1774,7 @@ export default class RFB extends EventTargetMixin {
         if (this._fbDepth == 24) {
             encs.push(encodings.encodingTight);
             encs.push(encodings.encodingTightPNG);
+            encs.push(encodings.encodingZRLE);
             encs.push(encodings.encodingHextile);
             encs.push(encodings.encodingRRE);
         }
diff --git a/tests/test.zrle.js b/tests/test.zrle.js
new file mode 100644
index 0000000..e09d208
--- /dev/null
+++ b/tests/test.zrle.js
@@ -0,0 +1,124 @@
+const expect = chai.expect;
+
+import Websock from '../core/websock.js';
+import Display from '../core/display.js';
+
+import ZRLEDecoder from '../core/decoders/zrle.js';
+
+import FakeWebSocket from './fake.websocket.js';
+
+function testDecodeRect(decoder, x, y, width, height, data, display, depth) {
+    let sock;
+
+    sock = new Websock;
+    sock.open("ws://example.com");
+
+    sock.on('message', () => {
+        decoder.decodeRect(x, y, width, height, sock, display, depth);
+    });
+
+    // Empty messages are filtered at multiple layers, so we need to
+    // do a direct call
+    if (data.length === 0) {
+        decoder.decodeRect(x, y, width, height, sock, display, depth);
+    } else {
+        sock._websocket._receiveData(new Uint8Array(data));
+    }
+
+    display.flip();
+}
+
+describe('ZRLE Decoder', function () {
+    let decoder;
+    let display;
+
+    before(FakeWebSocket.replace);
+    after(FakeWebSocket.restore);
+
+    beforeEach(function () {
+        decoder = new ZRLEDecoder();
+        display = new Display(document.createElement('canvas'));
+        display.resize(4, 4);
+    });
+
+    it('should handle the Raw subencoding', function () {
+        testDecodeRect(decoder, 0, 0, 4, 4,
+                       [0x00, 0x00, 0x00, 0x0e, 0x78, 0x5e, 0x62, 0x60, 0x60, 0xf8, 0x4f, 0x12, 0x02, 0x00, 0x00, 0x00, 0xff, 0xff],
+                       display, 24);
+
+        let targetData = new Uint8Array([
+            0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff,
+            0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff,
+            0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff,
+            0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff
+        ]);
+
+        expect(display).to.have.displayed(targetData);
+    });
+
+    it('should handle the Solid subencoding', function () {
+        testDecodeRect(decoder, 0, 0, 4, 4,
+                       [0x00, 0x00, 0x00, 0x0c, 0x78, 0x5e, 0x62, 0x64, 0x60, 0xf8, 0x0f, 0x00, 0x00, 0x00, 0xff, 0xff],
+                       display, 24);
+
+        let targetData = new Uint8Array([
+            0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff,
+            0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff,
+            0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff,
+            0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff
+        ]);
+
+        expect(display).to.have.displayed(targetData);
+    });
+
+
+    it('should handle the Palette Tile subencoding', function () {
+        testDecodeRect(decoder, 0, 0, 4, 4,
+                       [0x00, 0x00, 0x00, 0x12,  0x78, 0x5E, 0x62, 0x62, 0x60, 248, 0xff, 0x9F, 0x01, 0x08, 0x3E, 0x7C, 0x00, 0x00, 0x00, 0x00, 0xff, 0xff],
+                       display, 24);
+
+        let targetData = new Uint8Array([
+            0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff,
+            0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff,
+            0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff,
+            0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff
+        ]);
+
+        expect(display).to.have.displayed(targetData);
+    });
+
+    it('should handle the RLE Tile subencoding', function () {
+        testDecodeRect(decoder, 0, 0, 4, 4,
+                       [0x00, 0x00, 0x00, 0x0d, 0x78, 0x5e, 0x6a, 0x60, 0x60, 0xf8, 0x2f, 0x00, 0x00, 0x00, 0x00, 0xff, 0xff],
+                       display, 24);
+
+        let targetData = new Uint8Array([
+            0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff,
+            0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff,
+            0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff,
+            0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff
+        ]);
+
+        expect(display).to.have.displayed(targetData);
+    });
+
+    it('should handle the RLE Palette Tile subencoding', function () {
+        testDecodeRect(decoder, 0, 0, 4, 4,
+                       [0x00, 0x00, 0x00, 0x11, 0x78, 0x5e, 0x6a, 0x62, 0x60, 0xf8, 0xff, 0x9f, 0x81, 0xa1, 0x81, 0x1f, 0x00, 0x00, 0x00, 0xff, 0xff],
+                       display, 24);
+
+        let targetData = new Uint8Array([
+            0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff,
+            0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff,
+            0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff,
+            0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff
+        ]);
+
+        expect(display).to.have.displayed(targetData);
+    });
+
+    it('should fail on an invalid subencoding', function () {
+        let data = [0x00, 0x00, 0x00, 0x0c, 0x78, 0x5e, 0x6a, 0x64, 0x60, 0xf8, 0x0f, 0x00, 0x00, 0x00, 0xff, 0xff];
+        expect(() => testDecodeRect(decoder, 0, 0, 4, 4, data, display, 24)).to.throw();
+    });
+});