From 65ad3224e920deecb91a3c28e15341c8584a372c Mon Sep 17 00:00:00 2001 From: Pierre Ossman Date: Fri, 7 Mar 2014 13:48:29 +0100 Subject: [PATCH] Consolidate the different palette handler implementations --- common/rfb/CMakeLists.txt | 1 - common/rfb/Palette.h | 190 ++++++++++++++++++++++++++++ common/rfb/TightEncoder.h | 31 +---- common/rfb/TightPalette.cxx | 110 ----------------- common/rfb/TightPalette.h | 127 ------------------- common/rfb/hextileEncodeBetter.h | 16 +-- common/rfb/tightEncode.h | 204 ++++++++----------------------- common/rfb/zrleEncode.h | 86 +++---------- 8 files changed, 272 insertions(+), 493 deletions(-) create mode 100644 common/rfb/Palette.h delete mode 100644 common/rfb/TightPalette.cxx delete mode 100644 common/rfb/TightPalette.h diff --git a/common/rfb/CMakeLists.txt b/common/rfb/CMakeLists.txt index 590aea77..48590f36 100644 --- a/common/rfb/CMakeLists.txt +++ b/common/rfb/CMakeLists.txt @@ -53,7 +53,6 @@ set(RFB_SOURCES Timer.cxx TightDecoder.cxx TightEncoder.cxx - TightPalette.cxx TransImageGetter.cxx UpdateTracker.cxx VNCSConnectionST.cxx diff --git a/common/rfb/Palette.h b/common/rfb/Palette.h new file mode 100644 index 00000000..a9003354 --- /dev/null +++ b/common/rfb/Palette.h @@ -0,0 +1,190 @@ +/* Copyright (C) 2000-2005 Constantin Kaplinsky. All Rights Reserved. + * Copyright (C) 2011 D. R. Commander. All Rights Reserved. + * Copyright 2014 Pierre Ossman for Cendio AB + * + * This is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This software is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this software; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, + * USA. + */ +#ifndef __RFB_PALETTE_H__ +#define __RFB_PALETTE_H__ + +#include +#include + +#include + +namespace rfb { + class Palette { + public: + Palette() { clear(); } + ~Palette() {} + + int size() const { return numColours; } + + void clear() { numColours = 0; memset(hash, 0, sizeof(hash)); } + + inline bool insert(rdr::U32 colour, int numPixels); + inline unsigned char lookup(rdr::U32 colour) const; + inline rdr::U32 getColour(unsigned char index) const; + inline int getCount(unsigned char index) const; + + protected: + inline unsigned char genHash(rdr::U32 colour) const; + + protected: + int numColours; + + struct PaletteListNode { + PaletteListNode *next; + unsigned char idx; + rdr::U32 colour; + }; + + struct PaletteEntry { + PaletteListNode *listNode; + int numPixels; + }; + + // This is the raw list of colours, allocated from 0 and up + PaletteListNode list[256]; + // Hash table for quick lookup into the list above + PaletteListNode *hash[256]; + // Occurances of each colour, where the 0:th entry is the most common. + // Indices also refer to this array. + PaletteEntry entry[256]; + }; +} + +inline bool rfb::Palette::insert(rdr::U32 colour, int numPixels) +{ + PaletteListNode* pnode; + PaletteListNode* prev_pnode; + unsigned char hash_key, idx; + + hash_key = genHash(colour); + + pnode = hash[hash_key]; + prev_pnode = NULL; + + // Do we already have an entry for this colour? + while (pnode != NULL) { + if (pnode->colour == colour) { + // Yup + + idx = pnode->idx; + numPixels = entry[idx].numPixels + numPixels; + + // The extra pixels might mean we have to adjust the sort list + while (idx > 0) { + if (entry[idx-1].numPixels >= numPixels) + break; + entry[idx] = entry[idx-1]; + entry[idx].listNode->idx = idx; + idx--; + } + + if (idx != pnode->idx) { + entry[idx].listNode = pnode; + pnode->idx = idx; + } + + entry[idx].numPixels = numPixels; + + return true; + } + + prev_pnode = pnode; + pnode = pnode->next; + } + + // Check if palette is full. + if (numColours == 256) + return false; + + // Create a new colour entry + pnode = &list[numColours]; + pnode->next = NULL; + pnode->idx = 0; + pnode->colour = colour; + + // Add it to the hash table + if (prev_pnode != NULL) + prev_pnode->next = pnode; + else + hash[hash_key] = pnode; + + // Move palette entries with lesser pixel counts. + idx = numColours; + while (idx > 0) { + if (entry[idx-1].numPixels >= numPixels) + break; + entry[idx] = entry[idx-1]; + entry[idx].listNode->idx = idx; + idx--; + } + + // And add it into the freed slot. + pnode->idx = idx; + entry[idx].listNode = pnode; + entry[idx].numPixels = numPixels; + + numColours++; + + return true; +} + +inline unsigned char rfb::Palette::lookup(rdr::U32 colour) const +{ + unsigned char hash_key; + PaletteListNode* pnode; + + hash_key = genHash(colour); + pnode = hash[hash_key]; + + while (pnode != NULL) { + if (pnode->colour == colour) + return pnode->idx; + pnode = pnode->next; + } + + // We are being fed a bad colour + assert(false); + + return 0; +} + +inline rdr::U32 rfb::Palette::getColour(unsigned char index) const +{ + return entry[index].listNode->colour; +} + +inline int rfb::Palette::getCount(unsigned char index) const +{ + return entry[index].numPixels; +} + +inline unsigned char rfb::Palette::genHash(rdr::U32 colour) const +{ + unsigned char hash_key; + + // djb2 hash function + hash_key = 5; // 5381 & 0xff + for (int i = 0; i < 32; i += 8) + hash_key = ((hash_key << 5) + hash_key) ^ (colour >> i); + + return hash_key; +} + +#endif diff --git a/common/rfb/TightEncoder.h b/common/rfb/TightEncoder.h index e2fa96e8..a876b6f6 100644 --- a/common/rfb/TightEncoder.h +++ b/common/rfb/TightEncoder.h @@ -23,6 +23,7 @@ #include #include #include +#include // FIXME: Check if specifying extern "C" is really necessary. #include @@ -44,28 +45,6 @@ namespace rfb { int jpegSubsampling; }; - // - // C-style structures to store palette entries and compression paramentes. - // Such code probably should be converted into C++ classes. - // - - struct TIGHT_COLOR_LIST { - TIGHT_COLOR_LIST *next; - int idx; - rdr::U32 rgb; - }; - - struct TIGHT_PALETTE_ENTRY { - TIGHT_COLOR_LIST *listNode; - int numPixels; - }; - - struct TIGHT_PALETTE { - TIGHT_PALETTE_ENTRY entry[256]; - TIGHT_COLOR_LIST *hash[256]; - TIGHT_COLOR_LIST list[256]; - }; - // // Compression level stuff. The following array contains various // encoder parameters for each of 10 compression levels (0..9). @@ -99,9 +78,6 @@ namespace rfb { rdr::ZlibOutStream *zos, int zlibLevel, rdr::OutStream *os); - int paletteInsert(rdr::U32 rgb, int numPixels, int bpp); - void paletteReset(void); - void fastFillPalette8(const rdr::U8 *data, int stride, const Rect &r); void fastFillPalette16(const rdr::U16 *data, int stride, const Rect &r); void fastFillPalette32(const rdr::U32 *data, int stride, const Rect &r); @@ -149,9 +125,8 @@ namespace rfb { PixelFormat serverpf, clientpf; bool pack24; - int palMaxColors, palNumColors; - rdr::U32 monoBackground, monoForeground; - TIGHT_PALETTE palette; + int palMaxColors; + Palette palette; static const int defaultCompressLevel; static const TIGHT_CONF conf[]; diff --git a/common/rfb/TightPalette.cxx b/common/rfb/TightPalette.cxx deleted file mode 100644 index c4ed04e4..00000000 --- a/common/rfb/TightPalette.cxx +++ /dev/null @@ -1,110 +0,0 @@ -/* Copyright (C) 2000-2005 Constantin Kaplinsky. All Rights Reserved. - * - * This is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This software is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this software; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, - * USA. - */ - -// -// TightPalette class implementation. -// - -#include - -using namespace rfb; - -TightPalette::TightPalette(int maxColors) -{ - setMaxColors(maxColors); - reset(); -} - -void TightPalette::reset() -{ - m_numColors = 0; - memset(m_hash, 0, 256 * sizeof(TightColorList *)); -} - -void TightPalette::setMaxColors(int maxColors) -{ - m_maxColors = maxColors; - if (m_maxColors < 0) { - m_maxColors = 0; - } else if (m_maxColors > 254) { - m_maxColors = 254; - } -} - -int TightPalette::insert(rdr::U32 rgb, int numPixels) -{ - TightColorList *pnode; - TightColorList *prev_pnode = NULL; - int hash_key, idx, new_idx, count; - - hash_key = hashFunc(rgb); - - pnode = m_hash[hash_key]; - - while (pnode != NULL) { - if (pnode->rgb == rgb) { - // Such palette entry already exists. - new_idx = idx = pnode->idx; - count = m_entry[idx].numPixels + numPixels; - if (new_idx && m_entry[new_idx-1].numPixels < count) { - do { - m_entry[new_idx] = m_entry[new_idx-1]; - m_entry[new_idx].listNode->idx = new_idx; - new_idx--; - } - while (new_idx && m_entry[new_idx-1].numPixels < count); - - m_entry[new_idx].listNode = pnode; - pnode->idx = new_idx; - } - m_entry[new_idx].numPixels = count; - return m_numColors; - } - prev_pnode = pnode; - pnode = pnode->next; - } - - // Check if the palette is full. - if (m_numColors == 256 || m_numColors == m_maxColors) { - m_numColors = 0; - return 0; - } - - // Move palette entries with lesser pixel counts. - for ( idx = m_numColors; - idx > 0 && m_entry[idx-1].numPixels < numPixels; - idx-- ) { - m_entry[idx] = m_entry[idx-1]; - m_entry[idx].listNode->idx = idx; - } - - // Add new palette entry into the freed slot. - pnode = &m_list[m_numColors]; - if (prev_pnode != NULL) { - prev_pnode->next = pnode; - } else { - m_hash[hash_key] = pnode; - } - pnode->next = NULL; - pnode->idx = idx; - pnode->rgb = rgb; - m_entry[idx].listNode = pnode; - m_entry[idx].numPixels = numPixels; - - return ++m_numColors; -} diff --git a/common/rfb/TightPalette.h b/common/rfb/TightPalette.h deleted file mode 100644 index 2f6448ea..00000000 --- a/common/rfb/TightPalette.h +++ /dev/null @@ -1,127 +0,0 @@ -/* Copyright (C) 2000-2005 Constantin Kaplinsky. All Rights Reserved. - * - * This is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This software is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this software; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, - * USA. - */ - -// -// TightPalette class is a container for ordered color values. Colors -// are keys in a hash where values are frequency counts. Also, there -// is a list where colors are always sorted by these counts (more -// frequent first). -// - -#ifndef __RFB_TIGHTPALETTE_H__ -#define __RFB_TIGHTPALETTE_H__ - -#include -#include - -namespace rfb { - - struct TightColorList { - TightColorList *next; - int idx; - rdr::U32 rgb; - }; - - struct TightPaletteEntry { - TightColorList *listNode; - int numPixels; - }; - - class TightPalette { - - protected: - - // FIXME: Bigger hash table? Better hash function? - inline static int hashFunc(rdr::U32 rgb) { - return (rgb ^ (rgb >> 13)) & 0xFF; - } - - public: - - TightPalette(int maxColors = 254); - - // - // Re-initialize the object. This does not change maximum number - // of colors. - // - void reset(); - - // - // Set limit on the number of colors in the palette. Note that - // this value cannot exceed 254. - // - void setMaxColors(int maxColors); - - // - // Insert new color into the palette, or increment its counter if - // the color is already there. Returns new number of colors, or - // zero if the palette is full. If the palette becomes full, it - // reports zero colors and cannot be used any more without calling - // reset(). - // - int insert(rdr::U32 rgb, int numPixels); - - // - // Return number of colors in the palette. - // - inline int getNumColors() const { - return m_numColors; - } - - // - // Return the color specified by its index in the palette. - // - inline rdr::U32 getEntry(int i) const { - return (i < m_numColors) ? m_entry[i].listNode->rgb : (rdr::U32)-1; - } - - // - // Return the pixel counter of the color specified by its index. - // - inline int getCount(int i) const { - return (i < m_numColors) ? m_entry[i].numPixels : 0; - } - - // - // Return the index of a specified color. - // - inline rdr::U8 getIndex(rdr::U32 rgb) const { - TightColorList *pnode = m_hash[hashFunc(rgb)]; - while (pnode != NULL) { - if (pnode->rgb == rgb) { - return (rdr::U8)pnode->idx; - } - pnode = pnode->next; - } - return 0xFF; // no such color - } - - protected: - - int m_maxColors; - int m_numColors; - - TightPaletteEntry m_entry[256]; - TightColorList *m_hash[256]; - TightColorList m_list[256]; - - }; - -} // namespace rfb - -#endif // __RFB_TIGHTPALETTE_H__ diff --git a/common/rfb/hextileEncodeBetter.h b/common/rfb/hextileEncodeBetter.h index 2b6b160a..e1730ba5 100644 --- a/common/rfb/hextileEncodeBetter.h +++ b/common/rfb/hextileEncodeBetter.h @@ -26,7 +26,7 @@ #include #include -#include +#include #include @@ -114,13 +114,13 @@ class HEXTILE_TILE { private: bool m_processed[16][16]; - TightPalette m_pal; + Palette m_pal; }; HEXTILE_TILE::HEXTILE_TILE() : m_tile(NULL), m_width(0), m_height(0), m_size(0), m_flags(0), m_background(0), m_foreground(0), - m_numSubrects(0), m_pal(48 + 2 * BPP) + m_numSubrects(0) { } @@ -156,7 +156,7 @@ void HEXTILE_TILE::analyze() PIXEL_T *colorsPtr = m_colors; rdr::U8 *coordsPtr = m_coords; - m_pal.reset(); + m_pal.clear(); m_numSubrects = 0; // Have we found the first subrect already? @@ -200,7 +200,7 @@ void HEXTILE_TILE::analyze() *coordsPtr++ = (rdr::U8)((x << 4) | (y & 0x0F)); *coordsPtr++ = (rdr::U8)(((sw - 1) << 4) | ((sh - 1) & 0x0F)); - if (m_pal.insert(color, 1) == 0) { + if (!m_pal.insert(color, 1) || (m_pal.size() > (48 + 2 * BPP))) { // Handle palette overflow m_flags = hextileRaw; m_size = 0; @@ -221,16 +221,16 @@ void HEXTILE_TILE::analyze() } // Save number of colors in this tile (should be no less than 2) - int numColors = m_pal.getNumColors(); + int numColors = m_pal.size(); assert(numColors >= 2); - m_background = (PIXEL_T)m_pal.getEntry(0); + m_background = (PIXEL_T)m_pal.getColour(0); m_flags = hextileAnySubrects; int numSubrects = m_numSubrects - m_pal.getCount(0); if (numColors == 2) { // Monochrome tile - m_foreground = (PIXEL_T)m_pal.getEntry(1); + m_foreground = (PIXEL_T)m_pal.getColour(1); m_size = 1 + 2 * numSubrects; } else { // Colored tile diff --git a/common/rfb/tightEncode.h b/common/rfb/tightEncode.h index c121b7aa..62665300 100644 --- a/common/rfb/tightEncode.h +++ b/common/rfb/tightEncode.h @@ -1,5 +1,6 @@ /* Copyright (C) 2000-2003 Constantin Kaplinsky. All Rights Reserved. * Copyright (C) 2011 D. R. Commander. All Rights Reserved. + * Copyright 2014 Pierre Ossman for Cendio AB. * * This is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by @@ -53,82 +54,6 @@ namespace rfb { #ifndef TIGHT_ONCE #define TIGHT_ONCE -// -// Functions to operate on palette structures. -// - -#define HASH_FUNC16(rgb) ((int)(((rgb >> 8) + rgb) & 0xFF)) -#define HASH_FUNC32(rgb) ((int)(((rgb >> 16) + (rgb >> 8)) & 0xFF)) - -void TightEncoder::paletteReset(void) -{ - palNumColors = 0; - memset(palette.hash, 0, 256 * sizeof(TIGHT_COLOR_LIST *)); -} - -int TightEncoder::paletteInsert(rdr::U32 rgb, int numPixels, int bpp) -{ - TIGHT_COLOR_LIST *pnode; - TIGHT_COLOR_LIST *prev_pnode = NULL; - int hash_key, idx, new_idx, count; - - hash_key = (bpp == 16) ? HASH_FUNC16(rgb) : HASH_FUNC32(rgb); - - pnode = palette.hash[hash_key]; - - while (pnode != NULL) { - if (pnode->rgb == rgb) { - // Such palette entry already exists. - new_idx = idx = pnode->idx; - count = palette.entry[idx].numPixels + numPixels; - if (new_idx && palette.entry[new_idx-1].numPixels < count) { - do { - palette.entry[new_idx] = palette.entry[new_idx-1]; - palette.entry[new_idx].listNode->idx = new_idx; - new_idx--; - } - while (new_idx && - palette.entry[new_idx-1].numPixels < count); - palette.entry[new_idx].listNode = pnode; - pnode->idx = new_idx; - } - palette.entry[new_idx].numPixels = count; - return palNumColors; - } - prev_pnode = pnode; - pnode = pnode->next; - } - - // Check if palette is full. - if ( palNumColors == 256 || palNumColors == palMaxColors ) { - palNumColors = 0; - return 0; - } - - // Move palette entries with lesser pixel counts. - for ( idx = palNumColors; - idx > 0 && palette.entry[idx-1].numPixels < numPixels; - idx-- ) { - palette.entry[idx] = palette.entry[idx-1]; - palette.entry[idx].listNode->idx = idx; - } - - // Add new palette entry into the freed slot. - pnode = &palette.list[palNumColors]; - if (prev_pnode != NULL) { - prev_pnode->next = pnode; - } else { - palette.hash[hash_key] = pnode; - } - pnode->next = NULL; - pnode->idx = idx; - pnode->rgb = rgb; - palette.entry[idx].listNode = pnode; - palette.entry[idx].numPixels = numPixels; - - return (++palNumColors); -} - // // Compress the data (but do not perform actual compression if the data // size is less than TIGHT_MIN_TO_COMPRESS bytes. @@ -203,9 +128,10 @@ void TIGHT_ENCODE (const Rect& r, rdr::OutStream *os, bool forceSolid) if (forceSolid) { // Subrectangle has already been determined to be solid. - palNumColors = 1; ig->translatePixels(rawPixels, &solidColor, 1); pixels = (PIXEL_T *)&solidColor; + palette.clear(); + palette.insert(solidColor, 1); } else { // Analyze subrectangle's colors to determine best encoding method. palMaxColors = r.area() / pconf->idxMaxColorsDivisor; @@ -217,12 +143,12 @@ void TIGHT_ENCODE (const Rect& r, rdr::OutStream *os, bool forceSolid) if (clientpf.equal(serverpf) && clientpf.bpp >= 16) { // Count the colors in the raw buffer, so we can avoid unnecessary pixel // translation when encoding with JPEG. - if (grayScaleJPEG) palNumColors = 0; + if (grayScaleJPEG) palette.clear(); else FAST_FILL_PALETTE(rawPixels, stride, r); // JPEG can read from the raw buffer, but for the other methods, we need // to translate the raw pixels into an intermediate buffer. - if(palNumColors != 0 || jpegQuality == -1) { + if(palette.size() != 0 || jpegQuality == -1) { pixels = (PIXEL_T *)writer->getImageBuf(r.area()); stride = r.width(); ig->getImage(pixels, r); @@ -234,12 +160,12 @@ void TIGHT_ENCODE (const Rect& r, rdr::OutStream *os, bool forceSolid) stride = r.width(); ig->getImage(pixels, r); - if (grayScaleJPEG) palNumColors = 0; + if (grayScaleJPEG) palette.clear(); else FILL_PALETTE(pixels, r.area()); } } - switch (palNumColors) { + switch (palette.size()) { case 0: // Truecolor image #if (BPP != 8) @@ -297,7 +223,8 @@ void ENCODE_MONO_RECT (PIXEL_T *buf, const Rect& r, rdr::OutStream *os) os->writeU8(0x01); // Write the palette - PIXEL_T pal[2] = { (PIXEL_T)monoBackground, (PIXEL_T)monoForeground }; + PIXEL_T pal[2] = { (PIXEL_T)palette.getColour(0), + (PIXEL_T)palette.getColour(1) }; os->writeU8(1); os->writeBytes(pal, PACK_PIXELS(pal, 2)); @@ -311,7 +238,7 @@ void ENCODE_MONO_RECT (PIXEL_T *buf, const Rect& r, rdr::OutStream *os) int aligned_width; int x, y, bg_bits; - bg = (PIXEL_T) monoBackground; + bg = (PIXEL_T) pal[0]; aligned_width = w - w % 8; for (y = 0; y < h; y++) { @@ -365,10 +292,10 @@ void ENCODE_INDEXED_RECT (PIXEL_T *buf, const Rect& r, rdr::OutStream *os) // Write the palette { PIXEL_T pal[256]; - for (int i = 0; i < palNumColors; i++) - pal[i] = (PIXEL_T)palette.entry[i].listNode->rgb; - os->writeU8((rdr::U8)(palNumColors - 1)); - os->writeBytes(pal, PACK_PIXELS(pal, palNumColors)); + for (int i = 0; i < palette.size(); i++) + pal[i] = (PIXEL_T)palette.getColour(i); + os->writeU8((rdr::U8)(palette.size() - 1)); + os->writeBytes(pal, PACK_PIXELS(pal, palette.size())); } // Encode data in-place @@ -376,25 +303,19 @@ void ENCODE_INDEXED_RECT (PIXEL_T *buf, const Rect& r, rdr::OutStream *os) rdr::U8 *dst = (rdr::U8 *)buf; int count = r.area(); PIXEL_T rgb; - TIGHT_COLOR_LIST *pnode; int rep = 0; + unsigned char idx; while (count--) { rgb = *src++; while (count && *src == rgb) { rep++, src++, count--; } - pnode = palette.hash[HASH_FUNCTION(rgb)]; - while (pnode != NULL) { - if ((PIXEL_T)pnode->rgb == rgb) { - *dst++ = (rdr::U8)pnode->idx; - while (rep) { - *dst++ = (rdr::U8)pnode->idx; - rep--; - } - break; - } - pnode = pnode->next; + idx = palette.lookup(rgb); + *dst++ = idx; + while (rep) { + *dst++ = idx; + rep--; } } @@ -431,12 +352,12 @@ void FILL_PALETTE (PIXEL_T *data, int count) PIXEL_T c0, c1; int i, n0, n1; - palNumColors = 0; + palette.clear(); c0 = data[0]; for (i = 1; i < count && data[i] == c0; i++); if (i == count) { - palNumColors = 1; + palette.insert(c0, i); return; // Solid rectangle } @@ -455,14 +376,8 @@ void FILL_PALETTE (PIXEL_T *data, int count) break; } if (i == count) { - if (n0 > n1) { - monoBackground = (rdr::U32)c0; - monoForeground = (rdr::U32)c1; - } else { - monoBackground = (rdr::U32)c1; - monoForeground = (rdr::U32)c0; - } - palNumColors = 2; // Two colors + palette.insert(c0, n0); // Two colors + palette.insert(c1, n1); } } @@ -477,17 +392,17 @@ void FILL_PALETTE (PIXEL_T *data, int count) PIXEL_T c0, c1, ci = 0; int i, n0, n1, ni; + palette.clear(); + c0 = data[0]; for (i = 1; i < count && data[i] == c0; i++); if (i >= count) { - palNumColors = 1; // Solid rectangle + palette.insert(c0, i); // Solid rectangle return; } - if (palMaxColors < 2) { - palNumColors = 0; // Full-color format preferred - return; - } + if (palMaxColors < 2) + return; // Full-color format preferred n0 = i; c1 = data[i]; @@ -501,34 +416,26 @@ void FILL_PALETTE (PIXEL_T *data, int count) } else break; } - if (i >= count) { - if (n0 > n1) { - monoBackground = (rdr::U32)c0; - monoForeground = (rdr::U32)c1; - } else { - monoBackground = (rdr::U32)c1; - monoForeground = (rdr::U32)c0; - } - palNumColors = 2; // Two colors - return; - } - - paletteReset(); - paletteInsert (c0, (rdr::U32)n0, BPP); - paletteInsert (c1, (rdr::U32)n1, BPP); + palette.insert(c0, n0); + palette.insert(c1, n1); + if (i >= count) + return; // Two colors ni = 1; for (i++; i < count; i++) { if (data[i] == ci) { ni++; } else { - if (!paletteInsert (ci, (rdr::U32)ni, BPP)) + if (!palette.insert (ci, ni) || (palette.size() > palMaxColors)) { + palette.clear(); return; + } ci = data[i]; ni = 1; } } - paletteInsert (ci, (rdr::U32)ni, BPP); + if (!palette.insert (ci, ni) || (palette.size() > palMaxColors)) + palette.clear(); } void FAST_FILL_PALETTE (const PIXEL_T *data, int stride, const Rect& r) @@ -542,6 +449,8 @@ void FAST_FILL_PALETTE (const PIXEL_T *data, int stride, const Rect& r) serverpf.bufferFromPixel((rdr::U8*)&mask, ~0); + palette.clear(); + c0 = data[0] & mask; n0 = 0; for (rowptr = data; rowptr < dataend; rowptr += stride) { @@ -554,13 +463,11 @@ void FAST_FILL_PALETTE (const PIXEL_T *data, int stride, const Rect& r) soliddone: if (rowptr >= dataend) { - palNumColors = 1; // Solid rectangle - return; - } - if (palMaxColors < 2) { - palNumColors = 0; // Full-color format preferred + palette.insert(c0, 1); // Solid rectangle return; } + if (palMaxColors < 2) + return; // Full-color format preferred c1 = *colptr & mask; n1 = 0; @@ -592,21 +499,11 @@ void FAST_FILL_PALETTE (const PIXEL_T *data, int stride, const Rect& r) c0t = c0; c1t = c1; } - if (colptr2 >= dataend) { - if (n0 > n1) { - monoBackground = (rdr::U32)c0t; - monoForeground = (rdr::U32)c1t; - } else { - monoBackground = (rdr::U32)c1t; - monoForeground = (rdr::U32)c0t; - } - palNumColors = 2; // Two colors - return; - } + palette.insert(c0t, n0); + palette.insert(c1t, n1); - paletteReset(); - paletteInsert (c0t, (rdr::U32)n0, BPP); - paletteInsert (c1t, (rdr::U32)n1, BPP); + if (colptr2 >= dataend) + return; // Two colors ni = 1; colptr2++; @@ -623,8 +520,10 @@ void FAST_FILL_PALETTE (const PIXEL_T *data, int stride, const Rect& r) ig->translatePixels(&ci, &cit, 1); else cit = ci; - if (!paletteInsert (cit, (rdr::U32)ni, BPP)) + if (!palette.insert (cit, ni) || (palette.size() > palMaxColors)) { + palette.clear(); return; + } ci = (*colptr) & mask; ni = 1; } @@ -633,7 +532,8 @@ void FAST_FILL_PALETTE (const PIXEL_T *data, int stride, const Rect& r) colptr = rowptr; } ig->translatePixels(&ci, &cit, 1); - paletteInsert (cit, (rdr::U32)ni, BPP); + if (!palette.insert (cit, ni) || (palette.size() > palMaxColors)) + palette.clear(); } #endif // #if (BPP == 8) diff --git a/common/rfb/zrleEncode.h b/common/rfb/zrleEncode.h index 928ce967..34b5c675 100644 --- a/common/rfb/zrleEncode.h +++ b/common/rfb/zrleEncode.h @@ -31,6 +31,7 @@ #include #include +#include #include namespace rfb { @@ -61,55 +62,6 @@ namespace rfb { static const int bitsPerPackedPixel[] = { 0, 1, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 }; - -// The PaletteHelper class helps us build up the palette from pixel data by -// storing a reverse index using a simple hash-table - -class PaletteHelper { -public: - enum { MAX_SIZE = 127 }; - - PaletteHelper() - { - memset(index, 255, sizeof(index)); - size = 0; - } - - inline int hash(rdr::U32 pix) - { - return (pix ^ (pix >> 17)) & 4095; - } - - inline void insert(rdr::U32 pix) - { - if (size < MAX_SIZE) { - int i = hash(pix); - while (index[i] != 255 && key[i] != pix) - i++; - if (index[i] != 255) return; - - index[i] = size; - key[i] = pix; - palette[size] = pix; - } - size++; - } - - inline int lookup(rdr::U32 pix) - { - assert(size <= MAX_SIZE); - int i = hash(pix); - while (index[i] != 255 && key[i] != pix) - i++; - if (index[i] != 255) return index[i]; - return -1; - } - - rdr::U32 palette[MAX_SIZE]; - rdr::U8 index[4096+MAX_SIZE]; - rdr::U32 key[4096+MAX_SIZE]; - int size; -}; #endif void ZRLE_ENCODE_TILE (PIXEL_T* data, int w, int h, rdr::OutStream* os); @@ -150,7 +102,7 @@ void ZRLE_ENCODE_TILE (PIXEL_T* data, int w, int h, rdr::OutStream* os) { // First find the palette and the number of runs - PaletteHelper ph; + Palette palette; int runs = 0; int singlePixels = 0; @@ -167,7 +119,7 @@ void ZRLE_ENCODE_TILE (PIXEL_T* data, int w, int h, rdr::OutStream* os) while (*++ptr == pix) ; runs++; } - ph.insert(pix); + palette.insert(pix, 1); } //fprintf(stderr,"runs %d, single pixels %d, paletteSize %d\n", @@ -175,9 +127,9 @@ void ZRLE_ENCODE_TILE (PIXEL_T* data, int w, int h, rdr::OutStream* os) // Solid tile is a special case - if (ph.size == 1) { + if (palette.size() == 1) { os->writeU8(1); - os->WRITE_PIXEL(ph.palette[0]); + os->WRITE_PIXEL(palette.getColour(0)); return; } @@ -198,8 +150,8 @@ void ZRLE_ENCODE_TILE (PIXEL_T* data, int w, int h, rdr::OutStream* os) estimatedBytes = plainRleBytes; } - if (ph.size < 128) { - int paletteRleBytes = (BPPOUT/8) * ph.size + 2 * runs + singlePixels; + if (palette.size() < 128) { + int paletteRleBytes = (BPPOUT/8) * palette.size() + 2 * runs + singlePixels; if (paletteRleBytes < estimatedBytes) { useRle = true; @@ -207,9 +159,9 @@ void ZRLE_ENCODE_TILE (PIXEL_T* data, int w, int h, rdr::OutStream* os) estimatedBytes = paletteRleBytes; } - if (ph.size < 17) { - int packedBytes = ((BPPOUT/8) * ph.size + - w * h * bitsPerPackedPixel[ph.size-1] / 8); + if (palette.size() < 17) { + int packedBytes = ((BPPOUT/8) * palette.size() + + w * h * bitsPerPackedPixel[palette.size()-1] / 8); if (packedBytes < estimatedBytes) { useRle = false; @@ -219,12 +171,12 @@ void ZRLE_ENCODE_TILE (PIXEL_T* data, int w, int h, rdr::OutStream* os) } } - if (!usePalette) ph.size = 0; + if (!usePalette) palette.clear(); - os->writeU8((useRle ? 128 : 0) | ph.size); + os->writeU8((useRle ? 128 : 0) | palette.size()); - for (int i = 0; i < ph.size; i++) { - os->WRITE_PIXEL(ph.palette[i]); + for (int i = 0; i < palette.size(); i++) { + os->WRITE_PIXEL(palette.getColour(i)); } if (useRle) { @@ -240,14 +192,14 @@ void ZRLE_ENCODE_TILE (PIXEL_T* data, int w, int h, rdr::OutStream* os) ptr++; int len = ptr - runStart; if (len <= 2 && usePalette) { - int index = ph.lookup(pix); + int index = palette.lookup(pix); if (len == 2) os->writeU8(index); os->writeU8(index); continue; } if (usePalette) { - int index = ph.lookup(pix); + int index = palette.lookup(pix); os->writeU8(index | 128); } else { os->WRITE_PIXEL(pix); @@ -268,9 +220,9 @@ void ZRLE_ENCODE_TILE (PIXEL_T* data, int w, int h, rdr::OutStream* os) // packed pixels - assert (ph.size < 17); + assert (palette.size() < 17); - int bppp = bitsPerPackedPixel[ph.size-1]; + int bppp = bitsPerPackedPixel[palette.size()-1]; PIXEL_T* ptr = data; @@ -282,7 +234,7 @@ void ZRLE_ENCODE_TILE (PIXEL_T* data, int w, int h, rdr::OutStream* os) while (ptr < eol) { PIXEL_T pix = *ptr++; - rdr::U8 index = ph.lookup(pix); + rdr::U8 index = palette.lookup(pix); byte = (byte << bppp) | index; nbits += bppp; if (nbits >= 8) { -- 2.39.5