diff --git a/common/rfb/CMakeLists.txt b/common/rfb/CMakeLists.txt
index 590aea7..48590f3 100644
--- a/common/rfb/CMakeLists.txt
+++ b/common/rfb/CMakeLists.txt
@@ -53,7 +53,6 @@
   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 0000000..a900335
--- /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 <assert.h>
+#include <string.h>
+
+#include <rdr/types.h>
+
+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 e2fa96e..a876b6f 100644
--- a/common/rfb/TightEncoder.h
+++ b/common/rfb/TightEncoder.h
@@ -23,6 +23,7 @@
 #include <rdr/ZlibOutStream.h>
 #include <rfb/Encoder.h>
 #include <rfb/JpegCompressor.h>
+#include <rfb/Palette.h>
 
 // FIXME: Check if specifying extern "C" is really necessary.
 #include <stdio.h>
@@ -45,28 +46,6 @@
   };
 
   //
-  // 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).
   // Last three parameters correspond to JPEG quality levels (0..9).
@@ -99,9 +78,6 @@
                       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 @@
     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 c4ed04e..0000000
--- 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 <rfb/TightPalette.h>
-
-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 2f6448e..0000000
--- 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 <string.h>
-#include <rdr/types.h>
-
-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 2b6b160..e1730ba 100644
--- a/common/rfb/hextileEncodeBetter.h
+++ b/common/rfb/hextileEncodeBetter.h
@@ -26,7 +26,7 @@
 
 #include <rdr/OutStream.h>
 #include <rfb/hextileConstants.h>
-#include <rfb/TightPalette.h>
+#include <rfb/Palette.h>
 
 #include <assert.h>
 
@@ -114,13 +114,13 @@
  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 @@
 
   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 @@
       *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 @@
   }
 
   // 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 c121b7a..6266530 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
@@ -54,82 +55,6 @@
 #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 @@
 
   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 @@
     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 @@
       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 @@
   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 @@
   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 @@
   // 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 @@
   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 @@
   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 @@
       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 @@
   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 @@
     } 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 @@
 
   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 @@
 
   soliddone:
   if (rowptr >= dataend) {
-    palNumColors = 1;           // Solid rectangle
+    palette.insert(c0, 1);      // Solid rectangle
     return;
   }
-  if (palMaxColors < 2) {
-    palNumColors = 0;           // Full-color format preferred
-    return;
-  }
+  if (palMaxColors < 2)
+    return;                     // Full-color format preferred
 
   c1 = *colptr & mask;
   n1 = 0;
@@ -592,21 +499,11 @@
     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 @@
           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 @@
     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 928ce96..34b5c67 100644
--- a/common/rfb/zrleEncode.h
+++ b/common/rfb/zrleEncode.h
@@ -31,6 +31,7 @@
 
 #include <rdr/OutStream.h>
 #include <rdr/ZlibOutStream.h>
+#include <rfb/Palette.h>
 #include <assert.h>
 
 namespace rfb {
@@ -61,55 +62,6 @@
 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 @@
 {
   // First find the palette and the number of runs
 
-  PaletteHelper ph;
+  Palette palette;
 
   int runs = 0;
   int singlePixels = 0;
@@ -167,7 +119,7 @@
       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 @@
 
   // 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 @@
     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 @@
       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 @@
     }
   }
 
-  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 @@
         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 @@
 
       // 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 @@
 
         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) {