From 059aa632c3ae8e11c1856d9275ac95648baaac04 Mon Sep 17 00:00:00 2001 From: Constantin Kaplinsky Date: Thu, 22 Sep 2005 00:59:47 +0000 Subject: [PATCH] Using new TightPalette helper class instead of std::map, in Hextile encoder. This improves performance of the encoder, and provides more space for optimizations. The palette implementation was extracted from the Tight encoder. git-svn-id: svn://svn.code.sf.net/p/tigervnc/code/trunk@324 3789f03b-4d11-0410-bbf8-ca57d06f2519 --- rfb/Makefile.in | 1 + rfb/TightPalette.cxx | 110 +++++++++++++++++++++++++++++++++ rfb/TightPalette.h | 127 ++++++++++++++++++++++++++++++++++++++ rfb/hextileEncodeBetter.h | 75 ++++++++++------------ 4 files changed, 272 insertions(+), 41 deletions(-) create mode 100644 rfb/TightPalette.cxx create mode 100644 rfb/TightPalette.h diff --git a/rfb/Makefile.in b/rfb/Makefile.in index 9919c179..12adbfc0 100644 --- a/rfb/Makefile.in +++ b/rfb/Makefile.in @@ -39,6 +39,7 @@ CXXSRCS = \ SSecurityVncAuth.cxx \ TightDecoder.cxx \ TightEncoder.cxx \ + TightPalette.cxx \ TransImageGetter.cxx \ UpdateTracker.cxx \ VNCSConnectionST.cxx \ diff --git a/rfb/TightPalette.cxx b/rfb/TightPalette.cxx new file mode 100644 index 00000000..4fe7a744 --- /dev/null +++ b/rfb/TightPalette.cxx @@ -0,0 +1,110 @@ +/* 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, int bpp) +{ + 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/rfb/TightPalette.h b/rfb/TightPalette.h new file mode 100644 index 00000000..3f8b7ad4 --- /dev/null +++ b/rfb/TightPalette.h @@ -0,0 +1,127 @@ +/* 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, int bpp); + + // + // 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/rfb/hextileEncodeBetter.h b/rfb/hextileEncodeBetter.h index 9e037927..7a0e168b 100644 --- a/rfb/hextileEncodeBetter.h +++ b/rfb/hextileEncodeBetter.h @@ -24,10 +24,9 @@ // EXTRA_ARGS - optional extra arguments // GET_IMAGE_INTO_BUF - gets a rectangle of pixel data into a buffer -#include - #include #include +#include #include @@ -56,19 +55,23 @@ class HEXTILE_TILE { HEXTILE_TILE (); // - // Initialize the object with new tile data. + // Initialize existing object instance with new tile data. // void newTile(const PIXEL_T *src, int w, int h); // - // Returns the size of encoded subrects data, including subrects count. + // Flags can include: hextileRaw, hextileAnySubrects and + // hextileSubrectsColoured. Note that if hextileRaw is set, other + // flags make no sense. Also, hextileSubrectsColoured is meaningful + // only when hextileAnySubrects is set as well. // - int getSize() const { return m_size; } + int getFlags() const { return m_flags; } // - // Flags can include: hextileAnySubrects, hextileSubrectsColoured. + // Returns the size of encoded subrects data, including subrect count. + // The size is zero if flags do not include hextileAnySubrects. // - int getFlags() const { return m_flags; } + int getSize() const { return m_size; } // // Return optimal background. @@ -91,7 +94,7 @@ class HEXTILE_TILE { protected: // - // Fill in m_coords[], m_colors[], m_counts[] and set m_numSubrects. + // Fill in m_coords[], m_colors[], m_pal and set m_numSubrects. // void buildTables(); @@ -116,12 +119,8 @@ class HEXTILE_TILE { private: - // DEBUG: Check performance for: (1) U8[] and (2) dyn.allocated. bool m_processed[16][16]; - - // FIXME: Use array for (BPP == 8)? - // DEBUG: Use own hashing like in ZRLE? - std::map m_counts; + TightPalette m_pal; }; HEXTILE_TILE::HEXTILE_TILE() @@ -137,6 +136,8 @@ void HEXTILE_TILE::newTile(const PIXEL_T *src, int w, int h) m_width = w; m_height = h; + // NOTE: These two methods should always be called from this place + // only, and exactly in this order. buildTables(); computeSize(); } @@ -147,7 +148,7 @@ void HEXTILE_TILE::buildTables() m_numSubrects = 0; memset(m_processed, 0, 16 * 16 * sizeof(bool)); - m_counts.clear(); + m_pal.reset(); int x, y, sx, sy, sw, sh, max_x; PIXEL_T color; @@ -181,7 +182,9 @@ void HEXTILE_TILE::buildTables() *colorsPtr++ = color; *coordsPtr++ = (rdr::U8)((x << 4) | (y & 0x0F)); *coordsPtr++ = (rdr::U8)(((sw - 1) << 4) | ((sh - 1) & 0x0F)); - m_counts[color] += 1; + + if (m_pal.insert(color, 1, BPP) == 0) + return; // palette overflow m_numSubrects++; @@ -200,7 +203,7 @@ void HEXTILE_TILE::buildTables() void HEXTILE_TILE::computeSize() { // Save the number of colors - int numColors = m_counts.size(); + int numColors = m_pal.getNumColors(); // Handle solid tile if (numColors == 1) { @@ -210,39 +213,28 @@ void HEXTILE_TILE::computeSize() return; } - std::map::iterator i; - // Handle monochrome tile - choose background and foreground if (numColors == 2) { - i = m_counts.begin(); - m_background = i->first; - int bgCount = i->second; - i++; - if (i->second <= bgCount) { - m_foreground = i->first; - } else { - m_foreground = m_background; - m_background = i->first; - bgCount = i->second;; - } + int bgCount = m_pal.getCount(0); + m_background = (PIXEL_T)m_pal.getEntry(0); + m_foreground = (PIXEL_T)m_pal.getEntry(1); m_flags = hextileAnySubrects; m_size = 1 + 2 * (m_numSubrects - bgCount); return; } - // Handle colored tile - choose the best background color - int bgCount = 0, count; - PIXEL_T color; - for (i = m_counts.begin(); i != m_counts.end(); i++) { - color = i->first; - count = i->second; - if (count > bgCount) { - bgCount = count; - m_background = color; - } + // Handle raw-encoded tile (there was palette overflow) + if (numColors == 0) { + m_flags = hextileRaw; + m_size = 0; + return; } + // Handle colored tile - choose the best background color + int bgCount = m_pal.getCount(0); + m_background = (PIXEL_T)m_pal.getEntry(0); + m_flags = hextileAnySubrects | hextileSubrectsColoured; m_size = 1 + (2 + (BPP/8)) * (m_numSubrects - bgCount); } @@ -311,16 +303,17 @@ void HEXTILE_ENCODE(const Rect& r, rdr::OutStream* os GET_IMAGE_INTO_BUF(t,buf); tile.newTile(buf, t.width(), t.height()); + int tileType = tile.getFlags(); int encodedLen = tile.getSize(); - if (encodedLen >= t.width() * t.height() * (BPP/8)) { + if ( (tileType & hextileRaw) != 0 || + encodedLen >= t.width() * t.height() * (BPP/8)) { os->writeU8(hextileRaw); os->writeBytes(buf, t.width() * t.height() * (BPP/8)); oldBgValid = oldFgValid = false; continue; } - int tileType = tile.getFlags(); PIXEL_T bg = tile.getBackground(); PIXEL_T fg = 0; -- 2.39.5