From 6ad18db24f23d8eec073a156a18c78f2bb04c4bf Mon Sep 17 00:00:00 2001
From: hui su <huisu@google.com>
Date: Thu, 19 Mar 2015 15:55:29 -0700
Subject: [PATCH] Palette experiment: encode color indices based on context
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

The basic idea is to use a pixel’s neighboring colors as
context to predict its own color. Up to 4 neighbors are
considered here: left, left-above, above, right-above.
To reduce the number of contexts,  the combination of any
4 (or less) colors are mapped to a reduced number of
patterns. For example, 1111, 2222, 3333, … , can be mapped
to the same pattern: AAAA. SImilarly, 1122, 1133, 2233, …,
can be mapped to the pattern AABB. In this way, the total
number of color contexts is reduced to 16.

This almost doubles the gain of palette coding on screen
content videos.

on screen_content
--enable-palette                                  +14.2%
--enable-palette --enable-tx-skip                 +21.2%

on derflr
--enable-palette                                  +0.12%
with all other experiments                        +6.16%

Change-Id: I560306dae216f2ac11a9214968c2ad2319fa1718
---
 vp9/common/vp9_blockd.h       |   5 +-
 vp9/common/vp9_entropymode.c  | 302 ++++++++++++++---
 vp9/common/vp9_entropymode.h  |  11 +-
 vp9/common/vp9_enums.h        |  12 +
 vp9/common/vp9_palette.c      | 152 ++++++---
 vp9/common/vp9_palette.h      |  42 ++-
 vp9/decoder/vp9_decodemv.c    | 182 ++++-------
 vp9/encoder/vp9_bitstream.c   | 222 +++++++------
 vp9/encoder/vp9_encodeframe.c |  10 +-
 vp9/encoder/vp9_encoder.h     |  10 +-
 vp9/encoder/vp9_rd.c          |  12 +-
 vp9/encoder/vp9_rdopt.c       | 595 +++++++++++++++++-----------------
 12 files changed, 914 insertions(+), 641 deletions(-)

diff --git a/vp9/common/vp9_blockd.h b/vp9/common/vp9_blockd.h
index a74bb6525..01e969256 100644
--- a/vp9/common/vp9_blockd.h
+++ b/vp9/common/vp9_blockd.h
@@ -39,7 +39,8 @@ extern "C" {
 #define PALETTE_BUF_SIZE 16
 #define PALETTE_MAX_SIZE 8
 #define PALETTE_DELTA_BIT 0
-#define PALETTE_MAX_RUNS 128
+#define PALETTE_MAX_RUNS 512
+#define PALETTE_COLOR_CONTEXTS 16
 #endif  // CONFIG_PALETTE
 
 /* Segment Feature Masks */
@@ -357,7 +358,7 @@ typedef struct macroblockd {
   DECLARE_ALIGNED(16, uint8_t, color_index_map[2][64 * 64]);
   DECLARE_ALIGNED(16, int, palette_scan_buffer[64 * 64]);
   DECLARE_ALIGNED(16, uint8_t, palette_map_buffer[64 * 64]);
-#endif
+#endif  // CONFIG_PALETTE
 
   ENTROPY_CONTEXT *above_context[MAX_MB_PLANE];
   ENTROPY_CONTEXT left_context[MAX_MB_PLANE][16];
diff --git a/vp9/common/vp9_entropymode.c b/vp9/common/vp9_entropymode.c
index 05d85fcf1..3843159e4 100644
--- a/vp9/common/vp9_entropymode.c
+++ b/vp9/common/vp9_entropymode.c
@@ -444,34 +444,6 @@ const vp9_tree_index vp9_palette_scan_order_tree
   -SPIRAL_SCAN, -ZZ_SCAN,
 };
 
-static const vp9_prob
-default_palette_scan_order_prob[10][PALETTE_SCAN_ORDERS - 1] = {
-    {  95, 152, 184},
-    {  79, 102, 219},
-    { 114, 143, 201},
-    { 121, 133, 178},
-    {  80, 163, 180},
-    { 147, 124, 192},
-    { 140, 202, 142},
-    {  91, 238, 206},
-    { 214, 203, 180},
-    {  85, 223,  29},
-};
-
-static const vp9_prob
-default_palette_uv_scan_order_prob[10][PALETTE_SCAN_ORDERS - 1] = {
-    { 131, 171, 112},
-    {  29, 133, 213},
-    { 159, 147, 196},
-    {  86, 113, 173},
-    {  36, 210, 119},
-    { 148, 156, 160},
-    { 104, 209,  72},
-    {  37, 253, 232},
-    { 198, 240, 153},
-    {  61, 253, 109},
-};
-
 static const vp9_prob default_palette_enabled_prob[10][3] = {
     { 240,  180,  100, },
     { 240,  180,  100, },
@@ -489,6 +461,264 @@ static const vp9_prob default_palette_enabled_prob[10][3] = {
 static const vp9_prob default_uv_palette_enabled_prob[2] = {
     253, 229
 };
+
+const vp9_tree_index vp9_palette_color_tree[TREE_SIZE(PALETTE_COLORS)] = {
+  -PALETTE_COLOR_ONE, 2,
+  -PALETTE_COLOR_TWO, 4,
+  -PALETTE_COLOR_THREE, 6,
+  -PALETTE_COLOR_FOUR, 8,
+  -PALETTE_COLOR_FIVE, 10,
+  -PALETTE_COLOR_SIX, 12,
+  -PALETTE_COLOR_SEVEN, -PALETTE_COLOR_EIGHT
+};
+
+static const vp9_prob default_palette_color_prob
+[PALETTE_MAX_SIZE - 1][PALETTE_COLOR_CONTEXTS][PALETTE_COLORS - 1] = {
+    {  // 2 colors
+        { 230, 255, 128, 128, 128, 128, 128 },
+        { 214, 255, 128, 128, 128, 128, 128 },
+        { 128, 128, 128, 128, 128, 128, 128 },
+        { 128, 128, 128, 128, 128, 128, 128 },
+        { 128, 128, 128, 128, 128, 128, 128 },
+        { 240, 255, 128, 128, 128, 128, 128 },
+        {  73, 255, 128, 128, 128, 128, 128 },
+        { 128, 128, 128, 128, 128, 128, 128 },
+        { 130, 255, 128, 128, 128, 128, 128 },
+        { 227, 255, 128, 128, 128, 128, 128 },
+        { 128, 128, 128, 128, 128, 128, 128 },
+        { 188, 255, 128, 128, 128, 128, 128 },
+        {  75, 255, 128, 128, 128, 128, 128 },
+        { 250, 255, 128, 128, 128, 128, 128 },
+        { 223, 255, 128, 128, 128, 128, 128 },
+        { 252, 255, 128, 128, 128, 128, 128 },
+    }, {  // 3 colors
+        { 229, 137, 255, 128, 128, 128, 128 },
+        { 197, 120, 255, 128, 128, 128, 128 },
+        { 107, 195, 255, 128, 128, 128, 128 },
+        { 128, 128, 128, 128, 128, 128, 128 },
+        {  27, 151, 255, 128, 128, 128, 128 },
+        { 230, 130, 255, 128, 128, 128, 128 },
+        {  37, 230, 255, 128, 128, 128, 128 },
+        {  67, 221, 255, 128, 128, 128, 128 },
+        { 124, 230, 255, 128, 128, 128, 128 },
+        { 195, 109, 255, 128, 128, 128, 128 },
+        {  99, 122, 255, 128, 128, 128, 128 },
+        { 205, 208, 255, 128, 128, 128, 128 },
+        {  40, 235, 255, 128, 128, 128, 128 },
+        { 251, 132, 255, 128, 128, 128, 128 },
+        { 237, 186, 255, 128, 128, 128, 128 },
+        { 253, 112, 255, 128, 128, 128, 128 },
+    }, {  // 4 colors
+        { 195,  87, 128, 255, 128, 128, 128 },
+        { 143, 100, 123, 255, 128, 128, 128 },
+        {  94, 124, 119, 255, 128, 128, 128 },
+        {  77,  91, 130, 255, 128, 128, 128 },
+        {  39, 114, 178, 255, 128, 128, 128 },
+        { 222,  94, 125, 255, 128, 128, 128 },
+        {  44, 203, 132, 255, 128, 128, 128 },
+        {  68, 175, 122, 255, 128, 128, 128 },
+        { 110, 187, 124, 255, 128, 128, 128 },
+        { 152,  91, 128, 255, 128, 128, 128 },
+        {  70, 109, 181, 255, 128, 128, 128 },
+        { 133, 113, 164, 255, 128, 128, 128 },
+        {  47, 205, 133, 255, 128, 128, 128 },
+        { 247,  94, 136, 255, 128, 128, 128 },
+        { 205, 122, 146, 255, 128, 128, 128 },
+        { 251, 100, 141, 255, 128, 128, 128 },
+    }, {  // 5 colors
+        { 195,  65,  84, 125, 255, 128, 128 },
+        { 150,  76,  84, 121, 255, 128, 128 },
+        {  94, 110,  81, 117, 255, 128, 128 },
+        {  79,  85,  91, 139, 255, 128, 128 },
+        {  26, 102, 139, 127, 255, 128, 128 },
+        { 220,  73,  91, 119, 255, 128, 128 },
+        {  38, 203,  86, 127, 255, 128, 128 },
+        {  61, 186,  72, 124, 255, 128, 128 },
+        { 132, 199,  84, 128, 255, 128, 128 },
+        { 172,  52,  62, 120, 255, 128, 128 },
+        { 102,  89, 121, 122, 255, 128, 128 },
+        { 182,  48,  69, 186, 255, 128, 128 },
+        {  36, 206,  87, 126, 255, 128, 128 },
+        { 249,  55,  67, 122, 255, 128, 128 },
+        { 218,  88,  75, 122, 255, 128, 128 },
+        { 253,  64,  80, 119, 255, 128, 128 },
+    }, {  // 6 colors
+        { 182,  54,  64,  75, 118, 255, 128 },
+        { 126,  67,  70,  76, 116, 255, 128 },
+        {  79,  92,  67,  85, 120, 255, 128 },
+        {  63,  61,  81, 118, 132, 255, 128 },
+        {  21,  80, 105,  83, 119, 255, 128 },
+        { 215,  72,  74,  74, 111, 255, 128 },
+        {  50, 176,  63,  79, 120, 255, 128 },
+        {  72, 148,  66,  77, 120, 255, 128 },
+        { 105, 177,  57,  78, 130, 255, 128 },
+        { 150,  66,  66,  80, 127, 255, 128 },
+        {  81,  76, 109,  85, 116, 255, 128 },
+        { 113,  81,  62,  96, 148, 255, 128 },
+        {  54, 179,  69,  82, 121, 255, 128 },
+        { 244,  47,  48,  67, 118, 255, 128 },
+        { 198,  83,  53,  65, 121, 255, 128 },
+        { 250,  42,  51,  69, 110, 255, 128 },
+    }, {  // 7 colors
+        { 182,  45,  54,  62,  74, 113, 255 },
+        { 124,  63,  57,  62,  77, 114, 255 },
+        {  77,  80,  56,  66,  76, 117, 255 },
+        {  63,  57,  69,  98,  85, 131, 255 },
+        {  19,  81,  98,  63,  80, 116, 255 },
+        { 215,  56,  60,  63,  68, 105, 255 },
+        {  50, 174,  50,  60,  79, 118, 255 },
+        {  68, 151,  50,  58,  73, 117, 255 },
+        { 104, 182,  53,  57,  79, 127, 255 },
+        { 156,  50,  51,  63,  77, 111, 255 },
+        {  88,  67,  97,  59,  82, 120, 255 },
+        { 114,  81,  46,  65, 103, 132, 255 },
+        {  55, 166,  57,  66,  82, 120, 255 },
+        { 245,  34,  38,  43,  63, 114, 255 },
+        { 203,  68,  45,  47,  60, 118, 255 },
+        { 250,  35,  37,  47,  66, 110, 255 },
+    }, {  // 8 colors
+        { 180,  43,  46,  50,  56,  69, 109 },
+        { 116,  53,  51,  49,  57,  73, 115 },
+        {  79,  70,  49,  50,  59,  74, 117 },
+        {  60,  54,  57,  70,  62,  83, 129 },
+        {  20,  73,  85,  52,  66,  81, 119 },
+        { 213,  56,  52,  49,  53,  62, 104 },
+        {  48, 161,  41,  45,  56,  77, 116 },
+        {  68, 139,  40,  47,  54,  71, 116 },
+        { 123, 166,  42,  43,  52,  76, 130 },
+        { 153,  44,  44,  47,  54,  79, 129 },
+        {  87,  64,  83,  49,  60,  75, 127 },
+        { 131,  68,  43,  48,  73,  96, 130 },
+        {  55, 152,  45,  51,  64,  77, 113 },
+        { 243,  30,  28,  33,  41,  65, 114 },
+        { 202,  56,  35,  36,  42,  63, 123 },
+        { 249,  31,  29,  32,  45,  68, 111 },
+    }
+};
+
+static const vp9_prob default_palette_uv_color_prob
+[PALETTE_MAX_SIZE - 1][PALETTE_COLOR_CONTEXTS][PALETTE_COLORS - 1] = {
+    {  // 2 colors
+        { 228, 255, 128, 128, 128, 128, 128 },
+        { 195, 255, 128, 128, 128, 128, 128 },
+        { 128, 128, 128, 128, 128, 128, 128 },
+        { 128, 128, 128, 128, 128, 128, 128 },
+        { 128, 128, 128, 128, 128, 128, 128 },
+        { 228, 255, 128, 128, 128, 128, 128 },
+        {  71, 255, 128, 128, 128, 128, 128 },
+        { 128, 128, 128, 128, 128, 128, 128 },
+        { 129, 255, 128, 128, 128, 128, 128 },
+        { 206, 255, 128, 128, 128, 128, 128 },
+        { 128, 128, 128, 128, 128, 128, 128 },
+        { 136, 255, 128, 128, 128, 128, 128 },
+        {  98, 255, 128, 128, 128, 128, 128 },
+        { 236, 255, 128, 128, 128, 128, 128 },
+        { 222, 255, 128, 128, 128, 128, 128 },
+        { 249, 255, 128, 128, 128, 128, 128 },
+    }, {  // 3 colors
+        { 198, 136, 255, 128, 128, 128, 128 },
+        { 178, 105, 255, 128, 128, 128, 128 },
+        { 100, 206, 255, 128, 128, 128, 128 },
+        { 128, 128, 128, 128, 128, 128, 128 },
+        {  12, 136, 255, 128, 128, 128, 128 },
+        { 219, 134, 255, 128, 128, 128, 128 },
+        {  50, 198, 255, 128, 128, 128, 128 },
+        {  61, 231, 255, 128, 128, 128, 128 },
+        { 110, 209, 255, 128, 128, 128, 128 },
+        { 173, 106, 255, 128, 128, 128, 128 },
+        { 145, 166, 255, 128, 128, 128, 128 },
+        { 156, 175, 255, 128, 128, 128, 128 },
+        {  69, 183, 255, 128, 128, 128, 128 },
+        { 241, 163, 255, 128, 128, 128, 128 },
+        { 224, 160, 255, 128, 128, 128, 128 },
+        { 246, 154, 255, 128, 128, 128, 128 },
+    }, {  // 4 colors
+        { 173,  88, 143, 255, 128, 128, 128 },
+        { 146,  81, 127, 255, 128, 128, 128 },
+        {  84, 134, 102, 255, 128, 128, 128 },
+        {  69, 138, 140, 255, 128, 128, 128 },
+        {  31, 103, 200, 255, 128, 128, 128 },
+        { 217, 101, 139, 255, 128, 128, 128 },
+        {  51, 174, 121, 255, 128, 128, 128 },
+        {  64, 177, 109, 255, 128, 128, 128 },
+        {  96, 179, 145, 255, 128, 128, 128 },
+        { 164,  77, 114, 255, 128, 128, 128 },
+        {  87,  94, 156, 255, 128, 128, 128 },
+        { 105,  57, 173, 255, 128, 128, 128 },
+        {  63, 158, 137, 255, 128, 128, 128 },
+        { 236, 102, 156, 255, 128, 128, 128 },
+        { 197, 115, 153, 255, 128, 128, 128 },
+        { 245, 106, 154, 255, 128, 128, 128 },
+    }, {  // 5 colors
+        { 179,  64,  97, 129, 255, 128, 128 },
+        { 137,  56,  88, 125, 255, 128, 128 },
+        {  82, 107,  61, 118, 255, 128, 128 },
+        {  59, 113,  86, 115, 255, 128, 128 },
+        {  23,  88, 118, 130, 255, 128, 128 },
+        { 213,  66,  90, 125, 255, 128, 128 },
+        {  37, 181, 103, 121, 255, 128, 128 },
+        {  47, 188,  61, 131, 255, 128, 128 },
+        { 104, 185, 103, 144, 255, 128, 128 },
+        { 163,  39,  76, 112, 255, 128, 128 },
+        {  94,  74, 131, 126, 255, 128, 128 },
+        { 142,  42, 103, 163, 255, 128, 128 },
+        {  53, 162,  99, 149, 255, 128, 128 },
+        { 239,  54,  84, 108, 255, 128, 128 },
+        { 203,  84, 110, 147, 255, 128, 128 },
+        { 248,  70, 105, 151, 255, 128, 128 },
+    }, {  // 6 colors
+        { 189,  50,  67,  90, 130, 255, 128 },
+        { 114,  50,  55,  90, 123, 255, 128 },
+        {  66,  76,  54,  82, 128, 255, 128 },
+        {  43,  69,  69,  80, 129, 255, 128 },
+        {  22,  59,  87,  88, 141, 255, 128 },
+        { 203,  49,  68,  87, 122, 255, 128 },
+        {  43, 157,  74, 104, 146, 255, 128 },
+        {  54, 138,  51,  95, 138, 255, 128 },
+        {  82, 171,  58, 102, 146, 255, 128 },
+        { 129,  38,  59,  64, 168, 255, 128 },
+        {  56,  67, 119,  92, 112, 255, 128 },
+        {  96,  62,  53, 132,  82, 255, 128 },
+        {  60, 147,  77, 108, 145, 255, 128 },
+        { 238,  76,  73,  93, 148, 255, 128 },
+        { 189,  86,  73, 103, 157, 255, 128 },
+        { 246,  62,  75,  83, 167, 255, 128 },
+    }, {  // 7 colors
+        { 179,  42,  51,  73,  99, 134, 255 },
+        { 119,  52,  52,  61,  64, 114, 255 },
+        {  53,  77,  35,  65,  71, 131, 255 },
+        {  38,  70,  51,  68,  89, 144, 255 },
+        {  23,  65, 128,  73,  97, 131, 255 },
+        { 210,  47,  52,  63,  81, 143, 255 },
+        {  42, 159,  57,  68,  98, 143, 255 },
+        {  49, 153,  45,  82,  93, 143, 255 },
+        {  81, 169,  52,  72, 113, 151, 255 },
+        { 136,  46,  35,  56,  75,  96, 255 },
+        {  57,  84, 109,  47, 107, 131, 255 },
+        { 128,  78,  57,  36, 128,  85, 255 },
+        {  54, 149,  68,  77,  94, 153, 255 },
+        { 243,  58,  50,  71,  81, 167, 255 },
+        { 189,  92,  64,  70, 121, 173, 255 },
+        { 248,  35,  38,  51,  82, 201, 255 },
+    }, {  // 8 colors
+        { 201,  40,  36,  42,  64,  92, 123 },
+        { 116,  43,  33,  43,  73, 102, 128 },
+        {  46,  77,  37,  69,  62,  78, 150 },
+        {  40,  65,  52,  50,  76,  89, 133 },
+        {  28,  48,  91,  17,  64,  77, 133 },
+        { 218,  43,  43,  37,  56,  72, 163 },
+        {  41, 155,  44,  83,  82, 129, 180 },
+        {  44, 141,  29,  55,  64,  89, 147 },
+        {  92, 166,  48,  45,  59, 126, 179 },
+        { 169,  35,  49,  41,  36,  99, 139 },
+        {  55,  77,  77,  56,  60,  75, 156 },
+        { 155,  81,  51,  64,  57, 182, 255 },
+        {  60, 134,  49,  49,  93, 128, 174 },
+        { 244,  98,  51,  46,  22,  73, 238 },
+        { 189,  70,  40,  87,  93,  79, 201 },
+        { 248,  54,  49,  40,  29,  42, 227 },
+    }
+};
 #endif  // CONFIG_PALETTE
 
 #if CONFIG_SUPERTX
@@ -625,11 +855,11 @@ void vp9_init_mode_probs(FRAME_CONTEXT *fc) {
   vp9_copy(fc->palette_size_prob, default_palette_size_prob);
   vp9_copy(fc->palette_enabled_prob, default_palette_enabled_prob);
   vp9_copy(fc->palette_uv_enabled_prob, default_uv_palette_enabled_prob);
-  vp9_copy(fc->palette_scan_order_prob, default_palette_scan_order_prob);
-  vp9_copy(fc->palette_uv_scan_order_prob, default_palette_uv_scan_order_prob);
   vp9_copy(fc->palette_run_length_prob, default_palette_run_length_prob);
   vp9_copy(fc->palette_uv_size_prob, default_palette_uv_size_prob);
   vp9_copy(fc->palette_uv_run_length_prob, default_palette_uv_run_length_prob);
+  vp9_copy(fc->palette_color_prob, default_palette_color_prob);
+  vp9_copy(fc->palette_uv_color_prob, default_palette_uv_color_prob);
 #endif  // CONFIG_PALETTE
 #if CONFIG_SUPERTX
   vp9_copy(fc->supertx_prob, default_supertx_prob);
@@ -827,18 +1057,6 @@ void vp9_adapt_mode_probs(VP9_COMMON *cm) {
 #endif  // CONFIG_WEDGE_PARTITION
 
 #if CONFIG_PALETTE
-  for (i = 0; i < 10; i++) {
-    adapt_probs(vp9_palette_scan_order_tree,
-                pre_fc->palette_scan_order_prob[i],
-                counts->y_palette_scan_order[i],
-                fc->palette_scan_order_prob[i]);
-  }
-  for (i = 0; i < 10; i++) {
-    adapt_probs(vp9_palette_scan_order_tree,
-                pre_fc->palette_uv_scan_order_prob[i],
-                counts->uv_palette_scan_order[i],
-                fc->palette_uv_scan_order_prob[i]);
-  }
   for (i = 0; i < 10; i++) {
     adapt_probs(vp9_palette_size_tree, pre_fc->palette_size_prob[i],
                 counts->y_palette_size[i],
diff --git a/vp9/common/vp9_entropymode.h b/vp9/common/vp9_entropymode.h
index f916135ba..5bc291437 100644
--- a/vp9/common/vp9_entropymode.h
+++ b/vp9/common/vp9_entropymode.h
@@ -69,12 +69,14 @@ typedef struct frame_contexts {
 #if CONFIG_PALETTE
   vp9_prob palette_enabled_prob[10][3];
   vp9_prob palette_uv_enabled_prob[2];
-  vp9_prob palette_scan_order_prob[10][PALETTE_SCAN_ORDERS - 1];
-  vp9_prob palette_uv_scan_order_prob[10][PALETTE_SCAN_ORDERS - 1];
   vp9_prob palette_size_prob[10][PALETTE_SIZES - 1];
   vp9_prob palette_run_length_prob[10][PALETTE_RUN_LENGTHS - 1];
   vp9_prob palette_uv_size_prob[10][PALETTE_SIZES - 1];
   vp9_prob palette_uv_run_length_prob[10][PALETTE_RUN_LENGTHS - 1];
+  vp9_prob palette_color_prob[PALETTE_MAX_SIZE - 1][PALETTE_COLOR_CONTEXTS]
+                                                    [PALETTE_COLORS - 1];
+  vp9_prob palette_uv_color_prob[PALETTE_MAX_SIZE - 1][PALETTE_COLOR_CONTEXTS]
+                                                       [PALETTE_COLORS - 1];
 #endif  // CONFIG_PALETTE
 #if CONFIG_SUPERTX
   vp9_prob supertx_prob[PARTITION_SUPERTX_CONTEXTS][TX_SIZES];
@@ -169,14 +171,15 @@ extern const vp9_tree_index vp9_switchable_interp_tree
                                 [TREE_SIZE(SWITCHABLE_FILTERS)];
 #if CONFIG_EXT_TX
 extern const vp9_tree_index vp9_ext_tx_tree[TREE_SIZE(EXT_TX_TYPES)];
-#endif
+#endif  // CONFIG_EXT_TX
 #if CONFIG_PALETTE
 extern const vp9_tree_index vp9_palette_size_tree[TREE_SIZE(PALETTE_SIZES)];
 extern const vp9_tree_index
 vp9_palette_scan_order_tree[TREE_SIZE(PALETTE_SCAN_ORDERS)];
 extern const vp9_tree_index
 vp9_palette_run_length_tree[TREE_SIZE(PALETTE_RUN_LENGTHS)];
-#endif
+extern const vp9_tree_index vp9_palette_color_tree[TREE_SIZE(PALETTE_COLORS)];
+#endif  // CONFIG_PALETTE
 #if CONFIG_COPY_MODE
 extern const vp9_tree_index vp9_copy_mode_tree_l2[TREE_SIZE(2)];
 extern const vp9_tree_index vp9_copy_mode_tree[TREE_SIZE(COPY_MODE_COUNT - 1)];
diff --git a/vp9/common/vp9_enums.h b/vp9/common/vp9_enums.h
index 39a885ee8..903ffa536 100644
--- a/vp9/common/vp9_enums.h
+++ b/vp9/common/vp9_enums.h
@@ -157,6 +157,18 @@ typedef enum {
   ZZ_SCAN,
   PALETTE_SCAN_ORDERS
 } PALETTE_SCAN_ORDER;
+
+typedef enum {
+  PALETTE_COLOR_ONE,
+  PALETTE_COLOR_TWO,
+  PALETTE_COLOR_THREE,
+  PALETTE_COLOR_FOUR,
+  PALETTE_COLOR_FIVE,
+  PALETTE_COLOR_SIX,
+  PALETTE_COLOR_SEVEN,
+  PALETTE_COLOR_EIGHT,
+  PALETTE_COLORS
+} PALETTE_COLOR;
 #endif  // CONFIG_PALETTE
 
 typedef enum {
diff --git a/vp9/common/vp9_palette.c b/vp9/common/vp9_palette.c
index b90b45f83..4e4dc9fe7 100644
--- a/vp9/common/vp9_palette.c
+++ b/vp9/common/vp9_palette.c
@@ -16,7 +16,7 @@
 #include "vp9/common/vp9_palette.h"
 
 #if CONFIG_PALETTE
-void insertion_sort(double *data, int n) {
+void vp9_insertion_sort(double *data, int n) {
   int i, j, k;
   double val;
 
@@ -38,7 +38,7 @@ void insertion_sort(double *data, int n) {
   }
 }
 
-int count_colors(const uint8_t *src, int stride, int rows, int cols) {
+int vp9_count_colors(const uint8_t *src, int stride, int rows, int cols) {
   int n = 0, r, c, i, val_count[256];
   uint8_t val;
   vpx_memset(val_count, 0, sizeof(val_count));
@@ -59,7 +59,7 @@ int count_colors(const uint8_t *src, int stride, int rows, int cols) {
     return n;
 }
 
-int run_lengh_encoding(uint8_t *seq, int n, uint16_t *runs, int max_run) {
+int vp9_run_lengh_encoding(uint8_t *seq, int n, uint16_t *runs, int max_run) {
   int this_run, i, l = 0;
   uint8_t symbol;
 
@@ -81,7 +81,7 @@ int run_lengh_encoding(uint8_t *seq, int n, uint16_t *runs, int max_run) {
   return l;
 }
 
-int run_lengh_decoding(uint16_t *runs, int l, uint8_t *seq) {
+int vp9_run_lengh_decoding(uint16_t *runs, int l, uint8_t *seq) {
   int i, j = 0;
 
   for (i = 0; i < l; i += 2) {
@@ -92,7 +92,8 @@ int run_lengh_decoding(uint16_t *runs, int l, uint8_t *seq) {
   return j;
 }
 
-void transpose_block(uint8_t *seq_in, uint8_t *seq_out, int rows, int cols) {
+static void transpose_block(uint8_t *seq_in, uint8_t *seq_out, int rows,
+                            int cols) {
   int r, c;
 
   for (r = 0; r < cols; r++)
@@ -100,8 +101,8 @@ void transpose_block(uint8_t *seq_in, uint8_t *seq_out, int rows, int cols) {
       seq_out[r * rows + c] = seq_in[c * cols + r];
 }
 
-void palette_color_insertion(uint8_t *old_colors, int *m, int *count,
-                             MB_MODE_INFO *mbmi) {
+void vp9_palette_color_insertion(uint8_t *old_colors, int *m, int *count,
+                                 MB_MODE_INFO *mbmi) {
   int k = *m, n = mbmi->palette_literal_size;
   int i, j, l, min_idx = -1;
   uint8_t *new_colors = mbmi->palette_literal_colors;
@@ -149,7 +150,7 @@ void palette_color_insertion(uint8_t *old_colors, int *m, int *count,
   *m = k;
 }
 
-int palette_color_lookup(uint8_t *dic, int n, uint8_t val, int bits) {
+int vp9_palette_color_lookup(uint8_t *dic, int n, uint8_t val, int bits) {
   int j, min, arg_min = 0, i = 1;
 
   if (n < 1)
@@ -172,7 +173,7 @@ int palette_color_lookup(uint8_t *dic, int n, uint8_t val, int bits) {
     return -1;
 }
 
-int get_bit_depth(int n) {
+int vp9_get_bit_depth(int n) {
   int i = 1, p = 2;
   while (p < n) {
     i++;
@@ -182,18 +183,7 @@ int get_bit_depth(int n) {
   return i;
 }
 
-int palette_max_run(BLOCK_SIZE bsize) {
-  int table[BLOCK_SIZES] = {
-      32, 32, 32, 32,  // BLOCK_4X4,   BLOCK_4X8,   BLOCK_8X4,   BLOCK_8X8
-      64, 64, 64, 64,  // BLOCK_8X16,  BLOCK_16X8,  BLOCK_16X16, BLOCK_16X32
-      64, 64, 64, 64,  // BLOCK_32X16, BLOCK_32X32, BLOCK_32X64, BLOCK_64X32
-      64               // BLOCK_64X64
-  };
-
-  return table[bsize];
-}
-
-double calc_dist(double *p1, double *p2, int dim) {
+static double calc_dist(double *p1, double *p2, int dim) {
   double dist = 0;
   int i = 0;
 
@@ -203,8 +193,8 @@ double calc_dist(double *p1, double *p2, int dim) {
   return dist;
 }
 
-void calc_indices(double *data, double *centroids, int *indices,
-                  int n, int k, int dim) {
+void vp9_calc_indices(double *data, double *centroids, int *indices,
+                      int n, int k, int dim) {
   int i, j;
   double min_dist, this_dist;
 
@@ -260,21 +250,21 @@ double calc_total_dist(double *data, double *centroids, int *indices,
   return dist;
 }
 
-int k_means(double *data, double *centroids, int *indices,
-             int n, int k, int dim, int max_itr) {
+int vp9_k_means(double *data, double *centroids, int *indices,
+                int n, int k, int dim, int max_itr) {
   int i = 0;
   int *pre_indices;
   double pre_total_dist, cur_total_dist;
   double pre_centroids[256];
 
   pre_indices = vpx_memalign(16, n * sizeof(indices[0]));
-  calc_indices(data, centroids, indices, n, k, dim);
+  vp9_calc_indices(data, centroids, indices, n, k, dim);
   pre_total_dist = calc_total_dist(data, centroids, indices, n, k, dim);
   vpx_memcpy(pre_centroids, centroids, sizeof(pre_centroids[0]) * k * dim);
   vpx_memcpy(pre_indices, indices, sizeof(pre_indices[0]) * n);
   while (i < max_itr) {
     calc_centroids(data, centroids, indices, n, k, dim);
-    calc_indices(data, centroids, indices, n, k, dim);
+    vp9_calc_indices(data, centroids, indices, n, k, dim);
     cur_total_dist = calc_total_dist(data, centroids, indices, n, k, dim);
 
     if (cur_total_dist > pre_total_dist && 0) {
@@ -295,13 +285,13 @@ int k_means(double *data, double *centroids, int *indices,
   return i;
 }
 
-int is_in_boundary(int rows, int cols, int r, int c) {
+static int is_in_boundary(int rows, int cols, int r, int c) {
   if (r < 0 || r >= rows || c < 0 || c >= cols)
     return 0;
   return 1;
 }
 
-void zz_scan_order(int *order, int rows, int cols) {
+static void zz_scan_order(int *order, int rows, int cols) {
   int r, c, dir, idx;
 
   vpx_memset(order, 0, sizeof(order[0]) * rows * cols);
@@ -338,8 +328,8 @@ void zz_scan_order(int *order, int rows, int cols) {
   order[idx] = (rows - 1) * cols + cols - 1;
 }
 
-void spiral_order(int *order, int cols, int r_start, int c_start,
-                int h, int w, int idx) {
+static void spiral_order(int *order, int cols, int r_start, int c_start,
+                         int h, int w, int idx) {
   int r, c;
 
   if (h <= 0 && w <= 0) {
@@ -369,12 +359,12 @@ void spiral_order(int *order, int cols, int r_start, int c_start,
   spiral_order(order, cols, r_start + 1, c_start + 1, h - 2, w - 2, idx);
 }
 
-void spiral_scan_order(int *order, int rows, int cols) {
+static void spiral_scan_order(int *order, int rows, int cols) {
   spiral_order(order, cols, 0, 0, rows - 1, cols - 1, 0);
 }
 
-void palette_scan(uint8_t *color_index_map, uint8_t *sequence,
-                  int rows, int cols, PALETTE_SCAN_ORDER ps, int *scan_order) {
+void vp9_palette_scan(uint8_t *color_index_map, uint8_t *sequence, int rows,
+                      int cols, PALETTE_SCAN_ORDER ps, int *scan_order) {
   int i;
 
   switch (ps) {
@@ -399,8 +389,8 @@ void palette_scan(uint8_t *color_index_map, uint8_t *sequence,
   }
 }
 
-void palette_iscan(uint8_t *color_index_map, uint8_t *sequence,
-                   int rows, int cols, PALETTE_SCAN_ORDER ps, int *scan_order) {
+void vp9_palette_iscan(uint8_t *color_index_map, uint8_t *sequence, int rows,
+                       int cols, PALETTE_SCAN_ORDER ps, int *scan_order) {
   int i;
 
   switch (ps) {
@@ -425,21 +415,97 @@ void palette_iscan(uint8_t *color_index_map, uint8_t *sequence,
   }
 }
 
-void update_palette_counts(FRAME_COUNTS *counts, MB_MODE_INFO *mbmi,
-                           BLOCK_SIZE bsize, int palette_ctx) {
+void vp9_update_palette_counts(FRAME_COUNTS *counts, MB_MODE_INFO *mbmi,
+                               BLOCK_SIZE bsize, int palette_ctx) {
   int idx = bsize - BLOCK_8X8;
 
   counts->y_palette_enabled[idx][palette_ctx][mbmi->palette_enabled[0]]++;
   counts->uv_palette_enabled[mbmi->palette_enabled[0]]
                             [mbmi->palette_enabled[1]]++;
-  if (mbmi->palette_enabled[0]) {
-    counts->y_palette_scan_order[idx][mbmi->palette_scan_order[0]]++;
+  if (mbmi->palette_enabled[0])
     counts->y_palette_size[idx][mbmi->palette_size[0] - 2]++;
+  if (mbmi->palette_enabled[1])
+    counts->uv_palette_size[idx][mbmi->palette_size[1] - 2]++;
+}
+
+static const int palette_color_context_lookup[PALETTE_COLOR_CONTEXTS] = {
+    3993,  4235,  4378,  4380,  // (3, 0, 0, 0), (3, 2, 0, 0),
+                                // (3, 3, 2, 0), (3, 3, 2, 2),
+    5720,  6655,  7018,  7040,  // (4, 3, 3, 0), (5, 0, 0, 0),
+                                // (5, 3, 0, 0), (5, 3, 2, 0),
+    7260,  8228,  8250,  8470,  // (5, 5, 0, 0), (6, 2, 0, 0),
+                                // (6, 2, 2, 0), (6, 4, 0, 0),
+    9680, 10648, 10890, 13310   // (7, 3, 0, 0), (8, 0, 0, 0),
+                                // (8, 2, 0, 0), (10, 0, 0, 0)
+};
+
+int vp9_get_palette_color_context(uint8_t *color_map, int cols,
+                                  int r, int c, int n, int *color_order) {
+  int i, j, max, max_idx, temp;
+  int scores[PALETTE_MAX_SIZE];
+  int weights[4] = {3, 2, 3, 2};
+  int color_ctx = 0;
+  int color_neighbors[4];
+
+  assert(n <= PALETTE_MAX_SIZE);
+
+  if (c - 1 >= 0)
+    color_neighbors[0] = color_map[r * cols + c - 1];
+  else
+    color_neighbors[0] = -1;
+  if (c - 1 >= 0 && r - 1 >= 0)
+    color_neighbors[1] = color_map[(r - 1) * cols + c - 1];
+  else
+    color_neighbors[1] = -1;
+  if (r - 1 >= 0)
+    color_neighbors[2] = color_map[(r - 1) * cols + c];
+  else
+    color_neighbors[2] = -1;
+  if (r - 1 >= 0 && c + 1 <= cols - 1)
+    color_neighbors[3] = color_map[(r - 1) * cols + c + 1];
+  else
+    color_neighbors[3] = -1;
+
+  for (i = 0; i < PALETTE_MAX_SIZE; i++)
+    color_order[i] = i;
+  memset(scores, 0, PALETTE_MAX_SIZE * sizeof(scores[0]));
+  for (i = 0; i < 4; i++) {
+    if (color_neighbors[i] >= 0)
+      scores[color_neighbors[i]] += weights[i];
   }
 
-  if (mbmi->palette_enabled[1]) {
-    counts->uv_palette_scan_order[idx][mbmi->palette_scan_order[1]]++;
-    counts->uv_palette_size[idx][mbmi->palette_size[1] - 2]++;
+  for (i = 0; i < 4; i++) {
+    max = scores[i];
+    max_idx = i;
+    j = i + 1;
+    while (j < n) {
+      if (scores[j] > max) {
+        max = scores[j];
+        max_idx = j;
+      }
+      j++;
+    }
+
+    if (max_idx != i) {
+      temp = scores[i];
+      scores[i] = scores[max_idx];
+      scores[max_idx] = temp;
+
+      temp = color_order[i];
+      color_order[i] = color_order[max_idx];
+      color_order[max_idx] = temp;
+    }
   }
+
+  for (i = 0; i < 4; i++)
+    color_ctx = color_ctx * 11 + scores[i];
+
+  for (i = 0; i < PALETTE_COLOR_CONTEXTS; i++)
+    if (color_ctx == palette_color_context_lookup[i]) {
+      color_ctx = i;
+      break;
+    }
+
+  return color_ctx;
 }
 #endif  // CONFIG_PALETTE
diff --git a/vp9/common/vp9_palette.h b/vp9/common/vp9_palette.h
index 3148a38dd..bfc28e672 100644
--- a/vp9/common/vp9_palette.h
+++ b/vp9/common/vp9_palette.h
@@ -15,28 +15,26 @@
 #include "vp9/common/vp9_entropymode.h"
 
 #if CONFIG_PALETTE
-int count_colors(const uint8_t *src, int stride, int rows, int cols);
-void insertion_sort(double *data, int n);
-int run_lengh_encoding(uint8_t *seq, int n, uint16_t *runs, int max_run);
-int run_lengh_decoding(uint16_t *runs, int l, uint8_t *seq);
-void transpose_block(uint8_t *seq_in, uint8_t *seq_out, int rows, int cols);
-void palette_color_insertion(uint8_t *old_colors, int *m, int *count,
-                             MB_MODE_INFO *mbmi);
-int palette_color_lookup(uint8_t *dic, int n, uint8_t val, int bits);
-int palette_max_run(BLOCK_SIZE bsize);
-int get_bit_depth(int n);
-int k_means(double *data, double *centroids, int *indices,
-             int n, int k, int dim, int max_itr);
-void calc_indices(double *data, double *centroids, int *indices,
-                  int n, int k, int dim);
-void zz_scan_order(int *order, int rows, int cols);
-void spiral_scan_order(int *order, int rows, int cols);
-void palette_scan(uint8_t *color_index_map, uint8_t *sequence,
-                  int rows, int cols, PALETTE_SCAN_ORDER ps, int *scan_order);
-void palette_iscan(uint8_t *color_index_map, uint8_t *sequence,
-                   int rows, int cols, PALETTE_SCAN_ORDER ps, int *scan_order);
-void update_palette_counts(FRAME_COUNTS *counts, MB_MODE_INFO *mbmi,
-                           BLOCK_SIZE bsize, int palette_ctx);
+int vp9_count_colors(const uint8_t *src, int stride, int rows, int cols);
+void vp9_insertion_sort(double *data, int n);
+int vp9_run_lengh_encoding(uint8_t *seq, int n, uint16_t *runs, int max_run);
+int vp9_run_lengh_decoding(uint16_t *runs, int l, uint8_t *seq);
+void vp9_palette_color_insertion(uint8_t *old_colors, int *m, int *count,
+                                 MB_MODE_INFO *mbmi);
+int vp9_palette_color_lookup(uint8_t *dic, int n, uint8_t val, int bits);
+int vp9_get_bit_depth(int n);
+int vp9_k_means(double *data, double *centroids, int *indices,
+                int n, int k, int dim, int max_itr);
+void vp9_calc_indices(double *data, double *centroids, int *indices,
+                      int n, int k, int dim);
+void vp9_palette_scan(uint8_t *color_index_map, uint8_t *sequence, int rows,
+                      int cols, PALETTE_SCAN_ORDER ps, int *scan_order);
+void vp9_palette_iscan(uint8_t *color_index_map, uint8_t *sequence, int rows,
+                       int cols, PALETTE_SCAN_ORDER ps, int *scan_order);
+void vp9_update_palette_counts(FRAME_COUNTS *counts, MB_MODE_INFO *mbmi,
+                               BLOCK_SIZE bsize, int palette_ctx);
+int vp9_get_palette_color_context(uint8_t *color_map, int cols,
+                                  int r, int c, int n, int *color_order);
 #endif
 
 #endif  // VP9_COMMON_VP9_PALETTE_H_
diff --git a/vp9/decoder/vp9_decodemv.c b/vp9/decoder/vp9_decodemv.c
index cea3769c0..2e9695199 100644
--- a/vp9/decoder/vp9_decodemv.c
+++ b/vp9/decoder/vp9_decodemv.c
@@ -240,10 +240,11 @@ static void read_intra_frame_mode_info(VP9_COMMON *const cm,
   }
 
   if (mbmi->palette_enabled[0]) {
-    int i, m1, m2, d, val;
+    int i, j, m1, m2, val, n, color_idx, color_ctx;
     int rows = 4 * num_4x4_blocks_high_lookup[bsize];
     int cols = 4 * num_4x4_blocks_wide_lookup[bsize];
-    PALETTE_RUN_LENGTH bits;
+    int color_order[PALETTE_MAX_SIZE];
+    uint8_t *color_map = xd->plane[0].color_index_map;
 
     mbmi->mode = DC_PRED;
     mbmi->palette_size[0] =
@@ -265,19 +266,14 @@ static void read_intra_frame_mode_info(VP9_COMMON *const cm,
     else
       mbmi->palette_delta_bitdepth = 0;
 
-    mbmi->palette_run_length[0] =
-        vp9_read_literal(r, get_bit_depth(palette_max_run(bsize)));
-    mbmi->palette_run_length[0] = (mbmi->palette_run_length[0]) << 1;
-    mbmi->palette_scan_order[0] =
-        vp9_read_tree(r, vp9_palette_scan_order_tree,
-                      cm->fc.palette_scan_order_prob[bsize - BLOCK_8X8]);
     m1 = mbmi->palette_indexed_size;
     m2 = mbmi->palette_literal_size;
+    n = mbmi->palette_size[0];
 
     if (m1 > 0) {
       for (i = 0; i < m1; i++)
         mbmi->palette_indexed_colors[i] =
-            vp9_read_literal(r, get_bit_depth(cm->current_palette_size));
+            vp9_read_literal(r, vp9_get_bit_depth(cm->current_palette_size));
       if (mbmi->palette_delta_bitdepth > 0) {
         int s;
         for (i = 0; i < m1; i++) {
@@ -304,54 +300,40 @@ static void read_intra_frame_mode_info(VP9_COMMON *const cm,
       }
     }
 
-    d = get_bit_depth(rows * cols);
-    for (i = 0; i < mbmi->palette_run_length[0]; i += 2) {
-      mbmi->palette_runs[i] =
-          vp9_read_literal(r, get_bit_depth(m1 + m2));
+    vp9_palette_color_insertion(cm->current_palette_colors,
+                                &cm ->current_palette_size,
+                                cm->current_palette_count, mbmi);
 
-      bits = vp9_read_tree(r, vp9_palette_run_length_tree,
-                           cm->fc.palette_run_length_prob[bsize - BLOCK_8X8]);
-      if (bits == MAX_BITS)
-        mbmi->palette_runs[i + 1] = vp9_read_literal(r, d);
-      else
-        mbmi->palette_runs[i + 1] = vp9_read_literal(r, bits - ONE_BITS + 1);
-      mbmi->palette_runs[i + 1] += 1;
+    color_map[0] = vp9_read_literal(r,
+                                    vp9_get_bit_depth(mbmi->palette_size[0]));
+    for (i = 0; i < rows; i++) {
+      for (j = (i == 0 ? 1 : 0); j < cols; j++) {
+        color_ctx = vp9_get_palette_color_context(color_map, cols, i, j, n,
+                                                  color_order);
+        color_idx = vp9_read_tree(r, vp9_palette_color_tree,
+                                  cm->fc.palette_color_prob[n - 2][color_ctx]);
+
+        color_map[i * cols + j] = color_order[color_idx];
+      }
     }
 
-    palette_color_insertion(cm->current_palette_colors,
-                            &cm ->current_palette_size,
-                            cm->current_palette_count, mbmi);
-    run_lengh_decoding(mbmi->palette_runs, mbmi->palette_run_length[0],
-                       xd->palette_map_buffer);
-    palette_iscan(xd->plane[0].color_index_map, xd->palette_map_buffer,
-                  rows, cols, mbmi->palette_scan_order[0],
-                  xd->palette_scan_buffer);
     mbmi->tx_size = MIN(max_txsize_lookup[bsize],
                         tx_mode_to_biggest_tx_size[cm->tx_mode]);
   }
 
   if (mbmi->palette_enabled[1]) {
-    int i, d;
+    int i, j;
     int rows = 4 * num_4x4_blocks_high_lookup[bsize] >>
         xd->plane[1].subsampling_y;
     int cols = 4 * num_4x4_blocks_wide_lookup[bsize] >>
         xd->plane[1].subsampling_x;
-    PALETTE_RUN_LENGTH bits;
-    BLOCK_SIZE uv_bsize = get_plane_block_size(bsize, &xd->plane[1]);
 
     mbmi->uv_mode = DC_PRED;
-
     if (xd->plane[1].subsampling_x && xd->plane[1].subsampling_y) {
       mbmi->palette_size[1] =
           vp9_read_tree(r, vp9_palette_size_tree,
                         cm->fc.palette_uv_size_prob[bsize - BLOCK_8X8]);
       mbmi->palette_size[1] += 2;
-      mbmi->palette_run_length[1] =
-          vp9_read_literal(r, get_bit_depth(palette_max_run(uv_bsize)));
-      mbmi->palette_run_length[1] = (mbmi->palette_run_length[1]) << 1;
-      mbmi->palette_scan_order[1] =
-          vp9_read_tree(r, vp9_palette_scan_order_tree,
-                        cm->fc.palette_uv_scan_order_prob[bsize - BLOCK_8X8]);
     } else {
       mbmi->palette_size[1] = mbmi->palette_size[0];
     }
@@ -362,25 +344,21 @@ static void read_intra_frame_mode_info(VP9_COMMON *const cm,
       mbmi->palette_colors[2 * PALETTE_MAX_SIZE + i] = vp9_read_literal(r, 8);
 
     if (xd->plane[1].subsampling_x && xd->plane[1].subsampling_y) {
-      d = get_bit_depth(rows * cols);
-      for (i = 0; i < mbmi->palette_run_length[1]; i += 2) {
-        mbmi->palette_runs[PALETTE_MAX_RUNS + i] =
-            vp9_read_literal(r, get_bit_depth(mbmi->palette_size[1]));
-        bits = vp9_read_tree(r, vp9_palette_run_length_tree,
-                             cm->fc.
-                             palette_uv_run_length_prob[bsize - BLOCK_8X8]);
-        if (bits == MAX_BITS)
-          mbmi->palette_runs[PALETTE_MAX_RUNS + i + 1] = vp9_read_literal(r, d);
-        else
-          mbmi->palette_runs[PALETTE_MAX_RUNS + i + 1] =
-              vp9_read_literal(r, bits - ONE_BITS + 1);
-        mbmi->palette_runs[ PALETTE_MAX_RUNS + i + 1] += 1;
+      int color_idx = 0, color_ctx = 0;
+      int n = mbmi->palette_size[1];
+      int color_order[PALETTE_MAX_SIZE];
+      uint8_t *color_map = xd->plane[1].color_index_map;
+
+      color_map[0] = vp9_read_literal(r, vp9_get_bit_depth(n));
+      for (i = 0; i < rows; i++) {
+        for (j = (i == 0 ? 1 : 0); j < cols; j++) {
+          color_ctx = vp9_get_palette_color_context(color_map, cols, i, j, n,
+                                                    color_order);
+          color_idx = vp9_read_tree(r, vp9_palette_color_tree,
+                              cm->fc.palette_uv_color_prob[n - 2][color_ctx]);
+          color_map[i * cols + j] = color_order[color_idx];
+        }
       }
-
-      run_lengh_decoding(mbmi->palette_runs + PALETTE_MAX_RUNS,
-                         mbmi->palette_run_length[1], xd->palette_map_buffer);
-      palette_iscan(xd->plane[1].color_index_map, xd->palette_map_buffer, rows,
-                    cols, mbmi->palette_scan_order[1], xd->palette_scan_buffer);
     }
   }
 
@@ -1283,45 +1261,36 @@ static void read_inter_frame_mode_info(VP9_COMMON *const cm,
 
     if (mbmi->palette_enabled[0]) {
       BLOCK_SIZE bsize = mbmi->sb_type;
-      int i, d;
+      int i, j, n, color_ctx, color_idx;
       int rows = 4 * num_4x4_blocks_high_lookup[bsize];
       int cols = 4 * num_4x4_blocks_wide_lookup[bsize];
-      PALETTE_RUN_LENGTH bits;
+      int color_order[PALETTE_MAX_SIZE];
+      uint8_t *color_map = xd->plane[0].color_index_map;
 
       mbmi->mode = DC_PRED;
       mbmi->palette_size[0] =
           vp9_read_tree(r, vp9_palette_size_tree,
                         cm->fc.palette_size_prob[bsize - BLOCK_8X8]);
       mbmi->palette_size[0] += 2;
-      mbmi->palette_run_length[0] =
-          vp9_read_literal(r, get_bit_depth(palette_max_run(bsize)));
-      mbmi->palette_run_length[0] = (mbmi->palette_run_length[0]) << 1;
-      mbmi->palette_scan_order[0] =
-          vp9_read_tree(r, vp9_palette_scan_order_tree,
-                        cm->fc.palette_scan_order_prob[bsize - BLOCK_8X8]);
-
-      for (i = 0; i < mbmi->palette_size[0]; i++) {
-        mbmi->palette_colors[i] = vp9_read_literal(r, 8);
-      }
+      n = mbmi->palette_size[0];
 
-      d = get_bit_depth(rows * cols);
-      for (i = 0; i < mbmi->palette_run_length[0]; i += 2) {
-        mbmi->palette_runs[i] =
-            vp9_read_literal(r, get_bit_depth(mbmi->palette_size[0]));
+      for (i = 0; i < mbmi->palette_size[0]; i++)
+        mbmi->palette_colors[i] = vp9_read_literal(r, 8);
 
-        bits = vp9_read_tree(r, vp9_palette_run_length_tree,
-                             cm->fc.palette_run_length_prob[bsize - BLOCK_8X8]);
-        if (bits == MAX_BITS)
-          mbmi->palette_runs[i + 1] = vp9_read_literal(r, d);
-        else
-          mbmi->palette_runs[i + 1] = vp9_read_literal(r, bits - ONE_BITS + 1);
-        mbmi->palette_runs[i + 1] += 1;
+      color_map[0] = vp9_read_literal(r,
+                                      vp9_get_bit_depth(mbmi->palette_size[0]));
+      for (i = 0; i < rows; i++) {
+        for (j = (i == 0 ? 1 : 0); j < cols; j++) {
+          color_ctx = vp9_get_palette_color_context(color_map, cols, i, j, n,
+                                                    color_order);
+          color_idx = vp9_read_tree(r, vp9_palette_color_tree,
+                                    cm->fc.palette_color_prob[n - 2]
+                                                              [color_ctx]);
+
+          color_map[i * cols + j] = color_order[color_idx];
+        }
       }
 
-      run_lengh_decoding(mbmi->palette_runs, mbmi->palette_run_length[0],
-                         xd->palette_map_buffer);
-      palette_iscan(xd->plane[0].color_index_map, xd->palette_map_buffer, rows,
-                    cols, mbmi->palette_scan_order[0], xd->palette_scan_buffer);
       mbmi->tx_size = MIN(max_txsize_lookup[bsize],
                           tx_mode_to_biggest_tx_size[cm->tx_mode]);
       if (!cm->frame_parallel_decoding_mode)
@@ -1330,14 +1299,12 @@ static void read_inter_frame_mode_info(VP9_COMMON *const cm,
     }
 
     if (mbmi->palette_enabled[1]) {
-      int i, d;
+      int i, j;
       BLOCK_SIZE bsize = mbmi->sb_type;
       int rows = 4 * num_4x4_blocks_high_lookup[bsize] >>
           xd->plane[1].subsampling_y;
       int cols = 4 * num_4x4_blocks_wide_lookup[bsize] >>
           xd->plane[1].subsampling_x;
-      PALETTE_RUN_LENGTH bits;
-      BLOCK_SIZE uv_bsize = get_plane_block_size(bsize, &xd->plane[1]);
 
       mbmi->uv_mode = DC_PRED;
       if (xd->plane[1].subsampling_x && xd->plane[1].subsampling_y) {
@@ -1345,12 +1312,6 @@ static void read_inter_frame_mode_info(VP9_COMMON *const cm,
             vp9_read_tree(r, vp9_palette_size_tree,
                           cm->fc.palette_uv_size_prob[bsize - BLOCK_8X8]);
         mbmi->palette_size[1] += 2;
-        mbmi->palette_run_length[1] =
-            vp9_read_literal(r, get_bit_depth(palette_max_run(uv_bsize)));
-        mbmi->palette_run_length[1] = (mbmi->palette_run_length[1]) << 1;
-        mbmi->palette_scan_order[1] =
-            vp9_read_tree(r, vp9_palette_scan_order_tree,
-                          cm->fc.palette_uv_scan_order_prob[bsize - BLOCK_8X8]);
       } else {
         mbmi->palette_size[1] = mbmi->palette_size[0];
       }
@@ -1361,27 +1322,22 @@ static void read_inter_frame_mode_info(VP9_COMMON *const cm,
         mbmi->palette_colors[2 * PALETTE_MAX_SIZE + i] = vp9_read_literal(r, 8);
 
       if (xd->plane[1].subsampling_x && xd->plane[1].subsampling_y) {
-        d = get_bit_depth(rows * cols);
-        for (i = 0; i < mbmi->palette_run_length[1]; i += 2) {
-          mbmi->palette_runs[PALETTE_MAX_RUNS + i] =
-              vp9_read_literal(r, get_bit_depth(mbmi->palette_size[1]));
-          bits = vp9_read_tree(r, vp9_palette_run_length_tree,
-                               cm->fc.palette_uv_run_length_prob[bsize -
-                                                                 BLOCK_8X8]);
-          if (bits == MAX_BITS)
-            mbmi->palette_runs[PALETTE_MAX_RUNS + i + 1] =
-                vp9_read_literal(r, d);
-          else
-            mbmi->palette_runs[PALETTE_MAX_RUNS + i + 1] =
-                vp9_read_literal(r, bits - ONE_BITS + 1);
-          mbmi->palette_runs[ PALETTE_MAX_RUNS + i + 1] += 1;
+        int color_idx = 0, color_ctx = 0;
+        int n = mbmi->palette_size[1];
+        int color_order[PALETTE_MAX_SIZE];
+        uint8_t *color_map = xd->plane[1].color_index_map;
+
+        color_map[0] = vp9_read_literal(r, vp9_get_bit_depth(n));
+        for (i = 0; i < rows; i++) {
+          for (j = (i == 0 ? 1 : 0); j < cols; j++) {
+            color_ctx = vp9_get_palette_color_context(color_map, cols, i, j, n,
+                                                      color_order);
+            color_idx = vp9_read_tree(r, vp9_palette_color_tree,
+                                      cm->fc.palette_uv_color_prob[n - 2]
+                                                                   [color_ctx]);
+            color_map[i * cols + j] = color_order[color_idx];
+          }
         }
-
-        run_lengh_decoding(mbmi->palette_runs + PALETTE_MAX_RUNS,
-                           mbmi->palette_run_length[1], xd->palette_map_buffer);
-        palette_iscan(xd->plane[1].color_index_map, xd->palette_map_buffer,
-                      rows, cols, mbmi->palette_scan_order[1],
-                      xd->palette_scan_buffer);
       }
     }
 
@@ -1397,7 +1353,7 @@ static void read_inter_frame_mode_info(VP9_COMMON *const cm,
         palette_ctx += (above_mi->mbmi.palette_enabled[0] == 1);
       if (left_mi)
         palette_ctx += (left_mi->mbmi.palette_enabled[0] == 1);
-      update_palette_counts(&cm->counts, mbmi, bsize, palette_ctx);
+      vp9_update_palette_counts(&cm->counts, mbmi, bsize, palette_ctx);
     }
 
     if (!mbmi->palette_enabled[0]) {
diff --git a/vp9/encoder/vp9_bitstream.c b/vp9/encoder/vp9_bitstream.c
index b774b5436..93c6e489e 100644
--- a/vp9/encoder/vp9_bitstream.c
+++ b/vp9/encoder/vp9_bitstream.c
@@ -22,7 +22,7 @@
 #include "vp9/common/vp9_mvref_common.h"
 #if CONFIG_PALETTE
 #include "vp9/common/vp9_palette.h"
-#endif
+#endif  // CONFIG_PALETTE
 #include "vp9/common/vp9_pred_common.h"
 #include "vp9/common/vp9_seg_common.h"
 #include "vp9/common/vp9_systemdependent.h"
@@ -48,7 +48,8 @@ static struct vp9_token ext_tx_encodings[EXT_TX_TYPES];
 static struct vp9_token palette_size_encodings[PALETTE_SIZES];
 static struct vp9_token palette_scan_order_encodings[PALETTE_SCAN_ORDERS];
 static struct vp9_token palette_run_length_encodings[PALETTE_RUN_LENGTHS];
-#endif
+static struct vp9_token palette_color_encodings[PALETTE_COLORS];
+#endif  // CONFIG_PALETTE
 #if CONFIG_COPY_MODE
 static struct vp9_token copy_mode_encodings_l2[2];
 static struct vp9_token copy_mode_encodings[COPY_MODE_COUNT - 1];
@@ -83,7 +84,8 @@ void vp9_entropy_mode_init() {
                        vp9_palette_scan_order_tree);
   vp9_tokens_from_tree(palette_run_length_encodings,
                        vp9_palette_run_length_tree);
-#endif
+  vp9_tokens_from_tree(palette_color_encodings, vp9_palette_color_tree);
+#endif  // CONFIG_PALETTE
 #if CONFIG_COMPOUND_MODES
   vp9_tokens_from_tree(inter_compound_mode_encodings,
                        vp9_inter_compound_mode_tree);
@@ -467,75 +469,70 @@ static void pack_inter_mode_mvs(VP9_COMP *cpi, const MODE_INFO *mi,
 
 #if CONFIG_PALETTE
   if (!is_inter && bsize >= BLOCK_8X8 && cm->allow_palette_mode) {
-    int l, n, i, d, bits, ctx;
-    BLOCK_SIZE uv_bsize = get_plane_block_size(bsize, &xd->plane[1]);
+    int n, i, j, k, rows, cols, palette_ctx, color_ctx;
+    int color_new_idx = -1, color_order[PALETTE_MAX_SIZE];
+    uint8_t buffer[4096];
     const MODE_INFO *above_mi = xd->up_available ?
         xd->mi[-xd->mi_stride].src_mi : NULL;
     const MODE_INFO *left_mi = xd->left_available ?
         xd->mi[-1].src_mi : NULL;
 
-    ctx = 0;
+    palette_ctx = 0;
     if (above_mi)
-      ctx += (above_mi->mbmi.palette_enabled[0] == 1);
+      palette_ctx += (above_mi->mbmi.palette_enabled[0] == 1);
     if (left_mi)
-      ctx += (left_mi->mbmi.palette_enabled[0] == 1);
+      palette_ctx += (left_mi->mbmi.palette_enabled[0] == 1);
     vp9_write(w, mbmi->palette_enabled[0],
-              cm->fc.palette_enabled_prob[bsize - BLOCK_8X8][ctx]);
+              cm->fc.palette_enabled_prob[bsize - BLOCK_8X8][palette_ctx]);
     vp9_write(w, mbmi->palette_enabled[1],
               cm->fc.palette_uv_enabled_prob[mbmi->palette_enabled[0]]);
 
     if (mbmi->palette_enabled[0]) {
-      int rows = 4 * num_4x4_blocks_high_lookup[bsize];
-      int cols = 4 * num_4x4_blocks_wide_lookup[bsize];
+      rows = 4 * num_4x4_blocks_high_lookup[bsize];
+      cols = 4 * num_4x4_blocks_wide_lookup[bsize];
       n = mbmi->palette_size[0];
-      l = mbmi->palette_run_length[0];
 
       vp9_write_token(w, vp9_palette_size_tree,
                       cm->fc.palette_size_prob[bsize - BLOCK_8X8],
                       &palette_size_encodings[n - 2]);
-      vp9_write_literal(w, (l >> 1),
-                        get_bit_depth(palette_max_run(bsize)));
-      vp9_write_token(w, vp9_palette_scan_order_tree,
-                      cm->fc.palette_scan_order_prob[bsize - BLOCK_8X8],
-                      &palette_scan_order_encodings
-                      [mbmi->palette_scan_order[0]]);
 
       for (i = 0; i < n; i++)
         vp9_write_literal(w, mbmi->palette_colors[i], 8);
 
-      d = get_bit_depth(rows * cols);
-      for (i = 0; i < l; i += 2) {
-        vp9_write_literal(w, mbmi->palette_runs[i],
-                          get_bit_depth(n));
-        bits = get_bit_depth(mbmi->palette_runs[i + 1]);
-        vp9_write_token(w, vp9_palette_run_length_tree,
-                        cm->fc.palette_run_length_prob[bsize - BLOCK_8X8],
-                        &palette_run_length_encodings[bits > 6 ?
-                            6 : bits - 1]);
-        vp9_write_literal(w, mbmi->palette_runs[i + 1] - 1,
-                          bits > 6 ? d : bits);
+      vp9_run_lengh_decoding(cpi->mb.e_mbd.mi->mbmi.palette_runs,
+                             mbmi->palette_run_length[0],
+                             cpi->mb.e_mbd.palette_map_buffer);
+      vp9_palette_iscan(buffer, cpi->mb.e_mbd.palette_map_buffer, rows, cols,
+                        mbmi->palette_scan_order[0],
+                        cpi->mb.e_mbd.palette_scan_buffer);
+      vp9_write_literal(w, buffer[0], vp9_get_bit_depth(n));
+      for (i = 0; i < rows; i++) {
+        for (j = (i == 0 ? 1 : 0); j < cols; j++) {
+          color_ctx = vp9_get_palette_color_context(buffer, cols, i, j, n,
+                                                    color_order);
+          for (k = 0; k < n; k++)
+            if (buffer[i * cols + j] == color_order[k]) {
+              color_new_idx = k;
+              break;
+            }
+          vp9_write_token(w, vp9_palette_color_tree,
+                          cm->fc.palette_color_prob[n - 2][color_ctx],
+                          &palette_color_encodings[color_new_idx]);
+        }
       }
     }
 
     if (mbmi->palette_enabled[1]) {
-      const uint16_t *runs = mbmi->palette_runs + PALETTE_MAX_RUNS;
-      int rows = 4 * num_4x4_blocks_high_lookup[bsize] >>
+      rows = 4 * num_4x4_blocks_high_lookup[bsize] >>
           xd->plane[1].subsampling_y;
-      int cols = 4 * num_4x4_blocks_wide_lookup[bsize] >>
+      cols = 4 * num_4x4_blocks_wide_lookup[bsize] >>
           xd->plane[1].subsampling_x;
       n = mbmi->palette_size[1];
-      l = mbmi->palette_run_length[1];
 
       if (xd->plane[1].subsampling_x && xd->plane[1].subsampling_y) {
         vp9_write_token(w, vp9_palette_size_tree,
                         cm->fc.palette_uv_size_prob[bsize - BLOCK_8X8],
                         &palette_size_encodings[n - 2]);
-        vp9_write_literal(w, (l >> 1),
-                          get_bit_depth(palette_max_run(uv_bsize)));
-        vp9_write_token(w, vp9_palette_scan_order_tree,
-                        cm->fc.palette_uv_scan_order_prob[bsize - BLOCK_8X8],
-                        &palette_scan_order_encodings
-                        [mbmi->palette_scan_order[1]]);
       }
 
       for (i = 0; i < n; i++)
@@ -544,17 +541,27 @@ static void pack_inter_mode_mvs(VP9_COMP *cpi, const MODE_INFO *mi,
         vp9_write_literal(w, mbmi->palette_colors[2 * PALETTE_MAX_SIZE + i], 8);
 
       if (xd->plane[1].subsampling_x && xd->plane[1].subsampling_y) {
-        d = get_bit_depth(rows * cols);
-        for (i = 0; i < l; i += 2) {
-          vp9_write_literal(w, runs[i],
-                            get_bit_depth(mbmi->palette_size[1]));
-          bits = get_bit_depth(runs[i + 1]);
-          vp9_write_token(w, vp9_palette_run_length_tree,
-                          cm->fc.palette_uv_run_length_prob[bsize - BLOCK_8X8],
-                                      &palette_run_length_encodings[bits > 6 ?
-                                                                6 : bits - 1]);
-          vp9_write_literal(w, runs[i + 1] - 1,
-                            bits > 6 ? d : bits);
+        vp9_run_lengh_decoding(cpi->mb.e_mbd.mi->mbmi.palette_runs +
+                               PALETTE_MAX_RUNS,
+                               mbmi->palette_run_length[1],
+                               cpi->mb.e_mbd.palette_map_buffer);
+        vp9_palette_iscan(buffer, cpi->mb.e_mbd.palette_map_buffer, rows,
+                          cols, mbmi->palette_scan_order[1],
+                          cpi->mb.e_mbd.palette_scan_buffer);
+        vp9_write_literal(w, buffer[0], vp9_get_bit_depth(n));
+        for (i = 0; i < rows; i++) {
+          for (j = (i == 0 ? 1 : 0); j < cols; j++) {
+            color_ctx = vp9_get_palette_color_context(buffer, cols, i, j, n,
+                                                      color_order);
+            for (k = 0; k < n; k++)
+              if (buffer[i * cols + j] == color_order[k]) {
+                color_new_idx = k;
+                break;
+              }
+            vp9_write_token(w, vp9_palette_color_tree,
+                            cm->fc.palette_uv_color_prob[n - 2][color_ctx],
+                            &palette_color_encodings[color_new_idx]);
+          }
         }
       }
     }
@@ -836,7 +843,12 @@ static void pack_inter_mode_mvs(VP9_COMP *cpi, const MODE_INFO *mi,
   }
 }
 
-static void write_mb_modes_kf(const VP9_COMMON *cm, const MACROBLOCKD *xd,
+static void write_mb_modes_kf(const VP9_COMMON *cm,
+#if CONFIG_PALETTE
+                              MACROBLOCKD *xd,
+#else
+                              const MACROBLOCKD *xd,
+#endif  // CONFIG_PALETTE
                               MODE_INFO *mi_8x8, vp9_writer *w) {
   const struct segmentation *const seg = &cm->seg;
   const MODE_INFO *const mi = mi_8x8;
@@ -853,25 +865,26 @@ static void write_mb_modes_kf(const VP9_COMMON *cm, const MACROBLOCKD *xd,
 
 #if CONFIG_PALETTE
   if (bsize >= BLOCK_8X8 && cm->allow_palette_mode) {
-    int l, m1, m2, i, d, bits, ctx;
-    BLOCK_SIZE uv_bsize = get_plane_block_size(bsize, &xd->plane[1]);
+    int n, m1, m2, i, j, k, rows, cols, palette_ctx, color_ctx;
+    int color_new_idx = -1, color_order[PALETTE_MAX_SIZE];
+    uint8_t buffer[4096];
 
-    ctx = 0;
+    palette_ctx = 0;
     if (above_mi)
-      ctx += (above_mi->mbmi.palette_enabled[0] == 1);
+      palette_ctx += (above_mi->mbmi.palette_enabled[0] == 1);
     if (left_mi)
-      ctx += (left_mi->mbmi.palette_enabled[0] == 1);
+      palette_ctx += (left_mi->mbmi.palette_enabled[0] == 1);
     vp9_write(w, mbmi->palette_enabled[0],
-              cm->fc.palette_enabled_prob[bsize - BLOCK_8X8][ctx]);
+              cm->fc.palette_enabled_prob[bsize - BLOCK_8X8][palette_ctx]);
     vp9_write(w, mbmi->palette_enabled[1],
               cm->fc.palette_uv_enabled_prob[mbmi->palette_enabled[0]]);
 
     if (mbmi->palette_enabled[0]) {
-      int rows = 4 * num_4x4_blocks_high_lookup[bsize];
-      int cols = 4 * num_4x4_blocks_wide_lookup[bsize];
+      rows = 4 * num_4x4_blocks_high_lookup[bsize];
+      cols = 4 * num_4x4_blocks_wide_lookup[bsize];
+      n = mbmi->palette_size[0];
       m1 = mbmi->palette_indexed_size;
       m2 = mbmi->palette_literal_size;
-      l = mbmi->palette_run_length[0];
 
       vp9_write_token(w, vp9_palette_size_tree,
                       cm->fc.palette_size_prob[bsize - BLOCK_8X8],
@@ -880,20 +893,13 @@ static void write_mb_modes_kf(const VP9_COMMON *cm, const MACROBLOCKD *xd,
           || !mbmi->palette_enabled[1])
         vp9_encode_uniform(w, MIN(mbmi->palette_size[0] + 1, 8),
                            mbmi->palette_indexed_size);
-
       if (PALETTE_DELTA_BIT)
         vp9_write_literal(w, mbmi->palette_delta_bitdepth, PALETTE_DELTA_BIT);
-      vp9_write_literal(w, (l >> 1),
-                        get_bit_depth(palette_max_run(bsize)));
-      vp9_write_token(w, vp9_palette_scan_order_tree,
-                      cm->fc.palette_scan_order_prob[bsize - BLOCK_8X8],
-                      &palette_scan_order_encodings
-                      [mbmi->palette_scan_order[0]]);
 
       if (m1 > 0) {
         for (i = 0; i < m1; i++)
           vp9_write_literal(w, mbmi->palette_indexed_colors[i],
-                            get_bit_depth(mbmi->current_palette_size));
+                            vp9_get_bit_depth(mbmi->current_palette_size));
         if (mbmi->palette_delta_bitdepth > 0) {
           for (i = 0; i < m1; i++) {
             vp9_write_bit(w, mbmi->palette_color_delta[i] < 0);
@@ -907,57 +913,67 @@ static void write_mb_modes_kf(const VP9_COMMON *cm, const MACROBLOCKD *xd,
           vp9_write_literal(w, mbmi->palette_literal_colors[i], 8);
       }
 
-      d = get_bit_depth(rows * cols);
-      for (i = 0; i < l; i += 2) {
-        vp9_write_literal(w, mbmi->palette_runs[i],
-                          get_bit_depth(m1 + m2));
-        bits = get_bit_depth(mbmi->palette_runs[i + 1]);
-        vp9_write_token(w, vp9_palette_run_length_tree,
-                        cm->fc.palette_run_length_prob[bsize - BLOCK_8X8],
-                        &palette_run_length_encodings[bits > 6 ?
-                            6 : bits - 1]);
-        vp9_write_literal(w, mbmi->palette_runs[i + 1] - 1,
-                          bits > 6 ? d : bits);
+      vp9_run_lengh_decoding(mi_8x8->mbmi.palette_runs,
+                             mbmi->palette_run_length[0],
+                             xd->palette_map_buffer);
+      vp9_palette_iscan(buffer, xd->palette_map_buffer, rows, cols,
+                        mbmi->palette_scan_order[0], xd->palette_scan_buffer);
+      vp9_write_literal(w, buffer[0], vp9_get_bit_depth(n));
+      for (i = 0; i < rows; i++) {
+        for (j = (i == 0 ? 1 : 0); j < cols; j++) {
+          color_ctx = vp9_get_palette_color_context(buffer, cols, i, j, n,
+                                                    color_order);
+          for (k = 0; k < n; k++)
+            if (buffer[i * cols + j] == color_order[k]) {
+              color_new_idx = k;
+              break;
+            }
+          vp9_write_token(w, vp9_palette_color_tree,
+                          cm->fc.palette_color_prob[n - 2][color_ctx],
+                          &palette_color_encodings[color_new_idx]);
+        }
       }
     }
 
     if (mbmi->palette_enabled[1]) {
-      const uint16_t *runs = mbmi->palette_runs + PALETTE_MAX_RUNS;
-      int rows = 4 * num_4x4_blocks_high_lookup[bsize] >>
+      rows = 4 * num_4x4_blocks_high_lookup[bsize] >>
           xd->plane[1].subsampling_y;
-      int cols = 4 * num_4x4_blocks_wide_lookup[bsize] >>
+      cols = 4 * num_4x4_blocks_wide_lookup[bsize] >>
           xd->plane[1].subsampling_x;
-      l = mbmi->palette_run_length[1];
+      n = mbmi->palette_size[1];
 
       if (xd->plane[1].subsampling_x && xd->plane[1].subsampling_y) {
         vp9_write_token(w, vp9_palette_size_tree,
                         cm->fc.palette_uv_size_prob[bsize - BLOCK_8X8],
-                        &palette_size_encodings[mbmi->palette_size[1] - 2]);
-        vp9_write_literal(w, (l >> 1),
-                          get_bit_depth(palette_max_run(uv_bsize)));
-        vp9_write_token(w, vp9_palette_scan_order_tree,
-                        cm->fc.palette_uv_scan_order_prob[bsize - BLOCK_8X8],
-                        &palette_scan_order_encodings
-                        [mbmi->palette_scan_order[1]]);
+                        &palette_size_encodings[n - 2]);
       }
 
-      for (i = 0; i < mbmi->palette_size[1]; i++)
+      for (i = 0; i < n; i++)
         vp9_write_literal(w, mbmi->palette_colors[PALETTE_MAX_SIZE + i], 8);
-      for (i = 0; i < mbmi->palette_size[1]; i++)
+      for (i = 0; i < n; i++)
         vp9_write_literal(w, mbmi->palette_colors[2 * PALETTE_MAX_SIZE + i], 8);
 
       if (xd->plane[1].subsampling_x && xd->plane[1].subsampling_y) {
-        d = get_bit_depth(rows * cols);
-        for (i = 0; i < l; i += 2) {
-          vp9_write_literal(w, runs[i],
-                            get_bit_depth(mbmi->palette_size[1]));
-          bits = get_bit_depth(runs[i + 1]);
-          vp9_write_token(w, vp9_palette_run_length_tree,
-                          cm->fc.palette_uv_run_length_prob[bsize - BLOCK_8X8],
-                                        &palette_run_length_encodings[bits > 6 ?
-                                                                 6 : bits - 1]);
-          vp9_write_literal(w, runs[i + 1] - 1,
-                            bits > 6 ? d : bits);
+        vp9_run_lengh_decoding(mi_8x8->mbmi.palette_runs + PALETTE_MAX_RUNS,
+                               mbmi->palette_run_length[1],
+                               xd->palette_map_buffer);
+        vp9_palette_iscan(buffer, xd->palette_map_buffer, rows,
+                          cols, mbmi->palette_scan_order[1],
+                          xd->palette_scan_buffer);
+        vp9_write_literal(w, buffer[0], vp9_get_bit_depth(n));
+        for (i = 0; i < rows; i++) {
+          for (j = (i == 0 ? 1 : 0); j < cols; j++) {
+            color_ctx = vp9_get_palette_color_context(buffer, cols, i, j, n,
+                                                      color_order);
+            for (k = 0; k < n; k++)
+              if (buffer[i * cols + j] == color_order[k]) {
+                color_new_idx = k;
+                break;
+              }
+            vp9_write_token(w, vp9_palette_color_tree,
+                            cm->fc.palette_uv_color_prob[n - 2][color_ctx],
+                            &palette_color_encodings[color_new_idx]);
+          }
         }
       }
     }
diff --git a/vp9/encoder/vp9_encodeframe.c b/vp9/encoder/vp9_encodeframe.c
index 06679b4f2..d3e40aacb 100644
--- a/vp9/encoder/vp9_encodeframe.c
+++ b/vp9/encoder/vp9_encodeframe.c
@@ -795,7 +795,7 @@ static void update_state(VP9_COMP *cpi, PICK_MODE_CONTEXT *ctx,
   for (i = 0; i < 2; i++) {
     pd[i].color_index_map = ctx->color_index_map[i];
   }
-#endif
+#endif  // CONFIG_PALETTE
 
   // Restore the coding context of the MB to that that was in place
   // when the mode was picked for it
@@ -4989,9 +4989,9 @@ static void encode_superblock(VP9_COMP *cpi, TOKENEXTRA **t, int output_enabled,
     vp9_tokenize_sb(cpi, t, !output_enabled, MAX(bsize, BLOCK_8X8));
 #if CONFIG_PALETTE
     if (mbmi->palette_enabled[0] && output_enabled) {
-      palette_color_insertion(cm->current_palette_colors,
-                              &cm ->current_palette_size,
-                              cm->current_palette_count, mbmi);
+      vp9_palette_color_insertion(cm->current_palette_colors,
+                                  &cm ->current_palette_size,
+                                  cm->current_palette_count, mbmi);
     }
     if (frame_is_intra_only(cm) && output_enabled && bsize >= BLOCK_8X8) {
       cm->block_counter++;
@@ -5080,7 +5080,7 @@ static void encode_superblock(VP9_COMP *cpi, TOKENEXTRA **t, int output_enabled,
           palette_ctx += (above_mi->mbmi.palette_enabled[0] == 1);
         if (left_mi)
           palette_ctx += (left_mi->mbmi.palette_enabled[0] == 1);
-        update_palette_counts(&cm->counts, mbmi, bsize, palette_ctx);
+        vp9_update_palette_counts(&cm->counts, mbmi, bsize, palette_ctx);
       }
 #endif  // CONFIG_PALETTE
   }
diff --git a/vp9/encoder/vp9_encoder.h b/vp9/encoder/vp9_encoder.h
index 1b2a2ccbc..ccf042f7c 100644
--- a/vp9/encoder/vp9_encoder.h
+++ b/vp9/encoder/vp9_encoder.h
@@ -398,11 +398,17 @@ typedef struct VP9_COMP {
   int switchable_interp_costs[SWITCHABLE_FILTER_CONTEXTS][SWITCHABLE_FILTERS];
 #if CONFIG_EXT_TX
   int ext_tx_costs[3][EXT_TX_TYPES];
-#endif
+#endif  // CONFIG_EXT_TX
 #if CONFIG_COPY_MODE
   int copy_mode_cost_l2[COPY_MODE_CONTEXTS][2];
   int copy_mode_cost[COPY_MODE_CONTEXTS][COPY_MODE_COUNT - 1];
-#endif
+#endif  // CONFIG_COPY_MODE
+#if CONFIG_PALETTE
+  int palette_color_costs[PALETTE_MAX_SIZE - 1][PALETTE_COLOR_CONTEXTS]
+                                                [PALETTE_COLORS];
+  int palette_uv_color_costs[PALETTE_MAX_SIZE - 1][PALETTE_COLOR_CONTEXTS]
+                                                   [PALETTE_COLORS];
+#endif  // CONFIG_PALETTE
 
   PICK_MODE_CONTEXT *leaf_tree;
   PC_TREE *pc_tree;
diff --git a/vp9/encoder/vp9_rd.c b/vp9/encoder/vp9_rd.c
index 2ffc74734..ad8e0e47c 100644
--- a/vp9/encoder/vp9_rd.c
+++ b/vp9/encoder/vp9_rd.c
@@ -85,7 +85,17 @@ static void fill_mode_costs(VP9_COMP *cpi) {
 #if CONFIG_EXT_TX
   for (i = TX_4X4; i <= TX_16X16; ++i)
     vp9_cost_tokens(cpi->ext_tx_costs[i], fc->ext_tx_prob[i], vp9_ext_tx_tree);
-#endif
+#endif  // CONFIG_EXT_TX
+#if CONFIG_PALETTE
+  for (i = 0; i < PALETTE_MAX_SIZE - 1; ++i)
+    for (j = 0; j < PALETTE_COLOR_CONTEXTS; ++j)
+      vp9_cost_tokens(cpi->palette_color_costs[i][j],
+                      fc->palette_color_prob[i][j], vp9_palette_color_tree);
+  for (i = 0; i < PALETTE_MAX_SIZE - 1; ++i)
+    for (j = 0; j < PALETTE_COLOR_CONTEXTS; ++j)
+      vp9_cost_tokens(cpi->palette_uv_color_costs[i][j],
+                      fc->palette_uv_color_prob[i][j], vp9_palette_color_tree);
+#endif  // CONFIG_PALETTE
 }
 
 static void fill_token_costs(vp9_coeff_cost *c,
diff --git a/vp9/encoder/vp9_rdopt.c b/vp9/encoder/vp9_rdopt.c
index 859984dd4..a779012e1 100644
--- a/vp9/encoder/vp9_rdopt.c
+++ b/vp9/encoder/vp9_rdopt.c
@@ -22,7 +22,7 @@
 #include "vp9/common/vp9_mvref_common.h"
 #if CONFIG_PALETTE
 #include "vp9/common/vp9_palette.h"
-#endif
+#endif  // CONFIG_PALETTE
 #include "vp9/common/vp9_pred_common.h"
 #include "vp9/common/vp9_quant_common.h"
 #include "vp9/common/vp9_reconinter.h"
@@ -1506,17 +1506,19 @@ static int64_t rd_pick_intra_sby_mode(VP9_COMP *cpi, MACROBLOCK *x,
 
 #if CONFIG_PALETTE
   mic->mbmi.current_palette_size = cpi->common.current_palette_size;
-  colors = count_colors(src, src_stride, rows, cols);
+  colors = vp9_count_colors(src, src_stride, rows, cols);
   if (colors > 1 && colors <= 64 && cpi->common.allow_palette_mode) {
     int n, r, c, i, j, temp, max_itr = 200, k;
-    int l, m1, m2, d = get_bit_depth(rows * cols);
+    int l, m1, m2;
     int bits, best_bits = 0, total_bits, best_total_bits;
+    int color_ctx = 0, color_idx = 0;
+    int color_order[PALETTE_MAX_SIZE];
     int palette_size_cost[PALETTE_SIZES];
-    int palette_scan_order_cost[PALETTE_SCAN_ORDERS];
     int palette_run_length_cost[PALETTE_RUN_LENGTHS];
     double centroids[PALETTE_MAX_SIZE];
     double lb = src[0], ub = src[0], val;
     int64_t local_tx_cache[TX_MODES];
+    uint8_t *color_map;
     PALETTE_SCAN_ORDER ps;
 #if CONFIG_TX_SKIP
     int this_rate_tokenonly_s, s_s;
@@ -1531,9 +1533,6 @@ static int64_t rd_pick_intra_sby_mode(VP9_COMP *cpi, MACROBLOCK *x,
     vp9_cost_tokens(palette_size_cost,
                     cpi->common.fc.palette_size_prob[bsize - BLOCK_8X8],
                     vp9_palette_size_tree);
-    vp9_cost_tokens(palette_scan_order_cost,
-                    cpi->common.fc.palette_scan_order_prob[bsize - BLOCK_8X8],
-                    vp9_palette_scan_order_tree);
     vp9_cost_tokens(palette_run_length_cost,
                     cpi->common.fc.palette_run_length_prob[bsize - BLOCK_8X8],
                     vp9_palette_run_length_tree);
@@ -1556,9 +1555,9 @@ static int64_t rd_pick_intra_sby_mode(VP9_COMP *cpi, MACROBLOCK *x,
         n >= 2; n--) {
       for (i = 0; i < n; i++)
         centroids[i] = lb + (2 * i + 1) * (ub - lb) / n / 2;
-      r = k_means(x->kmeans_data_buffer, centroids, x->kmeans_indices_buffer,
-                  rows * cols, n, 1, max_itr);
-      insertion_sort(centroids, n);
+      r = vp9_k_means(x->kmeans_data_buffer, centroids,
+                      x->kmeans_indices_buffer, rows * cols, n, 1, max_itr);
+      vp9_insertion_sort(centroids, n);
       i = 1;
       k = n;
       while (i < k) {
@@ -1582,9 +1581,9 @@ static int64_t rd_pick_intra_sby_mode(VP9_COMP *cpi, MACROBLOCK *x,
         m1 = 0;
         m2 = 0;
         for (j = 0; j < k; j++) {
-          temp = palette_color_lookup(cpi->common.current_palette_colors,
-                                      cpi->common.current_palette_size,
-                                      mic->mbmi.palette_colors[j], bits);
+          temp = vp9_palette_color_lookup(cpi->common.current_palette_colors,
+                                          cpi->common.current_palette_size,
+                                          mic->mbmi.palette_colors[j], bits);
           if (temp >= 0) {
             mic->mbmi.palette_indexed_colors[m1] = temp;
             mic->mbmi.palette_color_delta[m1] =
@@ -1597,7 +1596,7 @@ static int64_t rd_pick_intra_sby_mode(VP9_COMP *cpi, MACROBLOCK *x,
             m2++;
           }
         }
-        total_bits = m1 * get_bit_depth(cpi->common.current_palette_size) +
+        total_bits = m1 * vp9_get_bit_depth(cpi->common.current_palette_size) +
             m1 * (bits == 0 ? 0 : bits + 1) + m2 * 8;
         if (total_bits <= best_total_bits) {
           best_total_bits = total_bits;
@@ -1608,9 +1607,9 @@ static int64_t rd_pick_intra_sby_mode(VP9_COMP *cpi, MACROBLOCK *x,
       m1 = 0;
       m2 = 0;
       for (i = 0; i < k; i++) {
-        temp = palette_color_lookup(cpi->common.current_palette_colors,
-                                    cpi->common.current_palette_size,
-                                    mic->mbmi.palette_colors[i], best_bits);
+        temp = vp9_palette_color_lookup(cpi->common.current_palette_colors,
+                                        cpi->common.current_palette_size,
+                                        mic->mbmi.palette_colors[i], best_bits);
         if (temp >= 0) {
           mic->mbmi.palette_indexed_colors[m1] = temp;
           mic->mbmi.palette_color_delta[m1] =
@@ -1639,8 +1638,8 @@ static int64_t rd_pick_intra_sby_mode(VP9_COMP *cpi, MACROBLOCK *x,
       for (i = 0; i < k; i++) {
         centroids[i] = (double) mic->mbmi.palette_colors[i];
       }
-      calc_indices(x->kmeans_data_buffer, centroids, x->kmeans_indices_buffer,
-                   rows * cols, k, 1);
+      vp9_calc_indices(x->kmeans_data_buffer, centroids,
+                       x->kmeans_indices_buffer, rows * cols, k, 1);
       for (r = 0; r < rows; r++) {
         for (c = 0; c < cols; c++) {
           xd->plane[0].color_index_map[r * cols + c] =
@@ -1684,63 +1683,71 @@ static int64_t rd_pick_intra_sby_mode(VP9_COMP *cpi, MACROBLOCK *x,
         continue;
       }
 
-      for (ps = H_SCAN; ps < PALETTE_SCAN_ORDERS; ps++) {
-        palette_scan(xd->plane[0].color_index_map, xd->palette_map_buffer,
-                     rows, cols, ps, xd->palette_scan_buffer);
-        l = run_lengh_encoding(xd->palette_map_buffer, rows * cols,
-                               mic->mbmi.palette_runs, palette_max_run(bsize));
-        if (!l)
-          continue;
 
-        this_rate = this_rate_tokenonly +
-            (vp9_encode_uniform_cost(MIN(k + 1, 8), m1) + PALETTE_DELTA_BIT
-                + get_bit_depth(palette_max_run(bsize)) +
-                get_bit_depth(mic->mbmi.current_palette_size) * m1 +
-                best_bits * m1 +
-                8 * m2 + get_bit_depth(k) * (l >> 1)) * vp9_cost_bit(128, 0) +
-                vp9_cost_bit(cpi->common.fc.palette_enabled_prob
-                             [bsize - BLOCK_8X8][palette_ctx], 1) +
-                             palette_size_cost[k - 2] +
-                             palette_scan_order_cost[ps];
-        for (i = 0; i < l; i += 2) {
-          int bits = get_bit_depth(mic->mbmi.palette_runs[i + 1]);
-          this_rate += palette_run_length_cost[bits > 6 ? 6 : bits - 1];
-          this_rate += (bits > 6 ? d : bits) * vp9_cost_bit(128, 0);
+      for (ps = H_SCAN; ps <= PALETTE_SCAN_ORDERS; ps++) {
+        vp9_palette_scan(xd->plane[0].color_index_map, xd->palette_map_buffer,
+                         rows, cols, ps, xd->palette_scan_buffer);
+        l = vp9_run_lengh_encoding(xd->palette_map_buffer, rows * cols,
+                                   mic->mbmi.palette_runs,
+                                   PALETTE_MAX_RUNS >> 1);
+        if (l)
+          break;
+      }
+      if (!l)
+        continue;
+
+      this_rate = this_rate_tokenonly +
+          (1 + vp9_encode_uniform_cost(MIN(k + 1, 8), m1) + PALETTE_DELTA_BIT
+              + vp9_get_bit_depth(mic->mbmi.current_palette_size) * m1 +
+              best_bits * m1 + 8 * m2) * vp9_cost_bit(128, 0) +
+              palette_size_cost[k - 2];
+      color_map = xd->plane[0].color_index_map;
+      this_rate +=  vp9_get_bit_depth(k) * vp9_cost_bit(128, 0);
+      for (i = 0; i < rows; i++) {
+        for (j = (i == 0 ? 1 : 0); j < cols; j++) {
+          color_ctx = vp9_get_palette_color_context(color_map, cols, i, j, n,
+                                                    color_order);
+          for (r = 0; r < n; r++)
+            if (color_map[i * cols + j] == color_order[r]) {
+              color_idx = r;
+              break;
+            }
+          this_rate += cpi->palette_color_costs[k - 2][color_ctx][color_idx];
         }
+      }
 #if CONFIG_TX_SKIP
-        this_rate += vp9_cost_bit(cpi->common.fc.y_tx_skip_prob[0],
-                                  mic->mbmi.tx_skip[0]);
+      this_rate += vp9_cost_bit(cpi->common.fc.y_tx_skip_prob[0],
+                                mic->mbmi.tx_skip[0]);
 #endif  // CONFIG_TX_SKIP
-        this_rd = RDCOST(x->rdmult, x->rddiv, this_rate, this_distortion);
-        if (this_rd < best_rd) {
-          mode_selected   = DC_PRED;
-          best_rd         = this_rd;
-          best_tx         = mic->mbmi.tx_size;
-          *rate           = this_rate;
-          *rate_tokenonly = this_rate_tokenonly;
-          *distortion     = this_distortion;
-          *skippable      = s;
-          best_n = k;
-          best_l = l;
-          palette_selected = 1;
-          best_ps = ps;
-          best_m1 = m1;
-          best_m2 = m2;
-          palette_delta_bitdepth = best_bits;
-          vpx_memcpy(best_palette, mic->mbmi.palette_colors,
-                     k * sizeof(best_palette[0]));
-          vpx_memcpy(best_runs, mic->mbmi.palette_runs,
-                     l * sizeof(best_runs[0]));
-          vpx_memcpy(best_index, mic->mbmi.palette_indexed_colors,
-                     best_m1 * sizeof(best_index[0]));
-          vpx_memcpy(palette_color_delta, mic->mbmi.palette_color_delta,
-                     best_m1 * sizeof(palette_color_delta[0]));
-          vpx_memcpy(best_literal, mic->mbmi.palette_literal_colors,
-                     best_m2 * sizeof(best_literal[0]));
+      this_rd = RDCOST(x->rdmult, x->rddiv, this_rate, this_distortion);
+      if (this_rd < best_rd) {
+        mode_selected   = DC_PRED;
+        best_rd         = this_rd;
+        best_tx         = mic->mbmi.tx_size;
+        *rate           = this_rate;
+        *rate_tokenonly = this_rate_tokenonly;
+        *distortion     = this_distortion;
+        *skippable      = s;
+        best_n = k;
+        best_l = l;
+        palette_selected = 1;
+        best_ps = ps;
+        best_m1 = m1;
+        best_m2 = m2;
+        palette_delta_bitdepth = best_bits;
+        vpx_memcpy(best_palette, mic->mbmi.palette_colors,
+                   k * sizeof(best_palette[0]));
+        vpx_memcpy(best_runs, mic->mbmi.palette_runs,
+                   l * sizeof(best_runs[0]));
+        vpx_memcpy(best_index, mic->mbmi.palette_indexed_colors,
+                   best_m1 * sizeof(best_index[0]));
+        vpx_memcpy(palette_color_delta, mic->mbmi.palette_color_delta,
+                   best_m1 * sizeof(palette_color_delta[0]));
+        vpx_memcpy(best_literal, mic->mbmi.palette_literal_colors,
+                   best_m2 * sizeof(best_literal[0]));
 #if CONFIG_TX_SKIP
-          tx_skipped = mic->mbmi.tx_skip[0];
+        tx_skipped = mic->mbmi.tx_skip[0];
 #endif  // CONFIG_TX_SKIP
-        }
       }
     }
   }
@@ -1776,11 +1783,12 @@ static int64_t rd_pick_intra_sby_mode(VP9_COMP *cpi, MACROBLOCK *x,
                best_m1 * sizeof(palette_color_delta[0]));
     vpx_memcpy(mic->mbmi.palette_literal_colors, best_literal,
                best_m2 * sizeof(best_literal[0]));
-    run_lengh_decoding(mic->mbmi.palette_runs, mic->mbmi.palette_run_length[0],
-                       xd->palette_map_buffer);
-    palette_iscan(xd->plane[0].color_index_map, xd->palette_map_buffer,
-                  rows, cols, mic->mbmi.palette_scan_order[0],
-                  xd->palette_scan_buffer);
+    vp9_run_lengh_decoding(mic->mbmi.palette_runs,
+                           mic->mbmi.palette_run_length[0],
+                           xd->palette_map_buffer);
+    vp9_palette_iscan(xd->plane[0].color_index_map, xd->palette_map_buffer,
+                      rows, cols, mic->mbmi.palette_scan_order[0],
+                      xd->palette_scan_buffer);
 #if CONFIG_FILTERINTRA
     mic->mbmi.filterbit = 0;
 #endif  // CONFIG_FILTERINTRA
@@ -2011,14 +2019,14 @@ static int64_t rd_pick_intra_sbuv_mode(VP9_COMP *cpi, MACROBLOCK *x,
   if (xd->mi[0].src_mi->mbmi.sb_type >= BLOCK_8X8 &&
       xd->plane[1].subsampling_x && xd->plane[1].subsampling_y &&
       cpi->common.allow_palette_mode) {
-    int colors_u = count_colors(src_u, src_stride, rows, cols);
-    int colors_v = count_colors(src_v, src_stride, rows, cols);
+    int colors_u = vp9_count_colors(src_u, src_stride, rows, cols);
+    int colors_v = vp9_count_colors(src_v, src_stride, rows, cols);
     int colors = colors_u > colors_v ? colors_u : colors_v;
 
     if (colors > 1 && colors <= 64) {
-      int n, r, c, i, j, max_itr = 200;
-      int l, d = get_bit_depth(rows * cols);
-      int palette_scan_order_cost[PALETTE_SCAN_ORDERS];
+      int n, r, c, i, j, l, max_itr = 200;
+      int color_ctx = 0, color_idx = 0;
+      int color_order[PALETTE_MAX_SIZE];
       int palette_run_length_cost[PALETTE_RUN_LENGTHS];
       int palette_size_cost[PALETTE_SIZES];
       double centroids[2 * PALETTE_MAX_SIZE];
@@ -2026,15 +2034,13 @@ static int64_t rd_pick_intra_sbuv_mode(VP9_COMP *cpi, MACROBLOCK *x,
       double lb_v = src_v[0], ub_v = src_v[0], val;
       PALETTE_SCAN_ORDER ps;
       BLOCK_SIZE uv_bsize = get_plane_block_size(bsize, &xd->plane[1]);
+      uint8_t *color_map;
 #if CONFIG_TX_SKIP
       int this_rate_tokenonly_s, s_s;
       int64_t this_distortion_s;
 #endif  // CONFIG_TX_SKIP
 
       i = uv_bsize - BLOCK_4X4;
-      vp9_cost_tokens(palette_scan_order_cost,
-                      cpi->common.fc.palette_uv_scan_order_prob[i],
-                      vp9_palette_scan_order_tree);
       vp9_cost_tokens(palette_size_cost,
                       cpi->common.fc.palette_uv_size_prob[i],
                       vp9_palette_size_tree);
@@ -2073,8 +2079,8 @@ static int64_t rd_pick_intra_sbuv_mode(VP9_COMP *cpi, MACROBLOCK *x,
           centroids[i * 2 + 1] =
               lb_v + (2 * i + 1) * (ub_v - lb_v) / n / 2;;
         }
-        r = k_means(x->kmeans_data_buffer, centroids, x->kmeans_indices_buffer,
-                    rows * cols, n, 2, max_itr);
+        r = vp9_k_means(x->kmeans_data_buffer, centroids,
+                        x->kmeans_indices_buffer, rows * cols, n, 2, max_itr);
 
         mbmi->palette_size[1] = n;
         for (i = 1; i < 3; i++) {
@@ -2126,55 +2132,62 @@ static int64_t rd_pick_intra_sbuv_mode(VP9_COMP *cpi, MACROBLOCK *x,
         }
 
         for (ps = H_SCAN; ps < PALETTE_SCAN_ORDERS; ps++) {
-          palette_scan(xd->plane[1].color_index_map, xd->palette_map_buffer,
-                       rows, cols, ps, xd->palette_scan_buffer);
-          l = run_lengh_encoding(xd->palette_map_buffer, rows * cols,
-                                 mbmi->palette_runs + PALETTE_MAX_RUNS,
-                                 palette_max_run(uv_bsize));
-          if (!l)
-            continue;
+          vp9_palette_scan(xd->plane[1].color_index_map, xd->palette_map_buffer,
+                           rows, cols, ps, xd->palette_scan_buffer);
+          l = vp9_run_lengh_encoding(xd->palette_map_buffer, rows * cols,
+                                     mbmi->palette_runs + PALETTE_MAX_RUNS,
+                                     PALETTE_MAX_RUNS >> 1);
+          if (l)
+            break;
+        }
+        if (!l)
+          continue;
 
-          this_rate = this_rate_tokenonly +
-              (get_bit_depth(palette_max_run(uv_bsize)) + 2 * 8 * n +
-                  get_bit_depth(n) * (l >> 1)) * vp9_cost_bit(128, 0) +
-                  vp9_cost_bit(cpi->common.fc.palette_uv_enabled_prob
-                               [mbmi->palette_enabled[0]], 1) +
-                               palette_size_cost[n - 2] +
-                               palette_scan_order_cost[ps];
-          for (i = 0; i < l; i += 2) {
-            int bits = get_bit_depth(
-                mbmi->palette_runs[PALETTE_MAX_RUNS + i + 1]);
-            this_rate += palette_run_length_cost[bits > 6 ? 6 : bits - 1];
-            this_rate += (bits > 6 ? d : bits) * vp9_cost_bit(128, 0);
+        color_map = xd->plane[1].color_index_map;
+        this_rate = this_rate_tokenonly +
+            (1 + 2 * 8 * n) * vp9_cost_bit(128, 0) +
+            palette_size_cost[n - 2];
+        this_rate +=  vp9_get_bit_depth(n) * vp9_cost_bit(128, 0);
+        for (i = 0; i < rows; i++) {
+          for (j = (i == 0 ? 1 : 0); j < cols; j++) {
+            color_ctx = vp9_get_palette_color_context(color_map, cols, i, j, n,
+                                                      color_order);
+            for (r = 0; r < n; r++)
+              if (color_map[i * cols + j] == color_order[r]) {
+                color_idx = r;
+                break;
+              }
+            this_rate += cpi->palette_uv_color_costs[n - 2][color_ctx]
+                                                            [color_idx];
           }
+        }
 #if CONFIG_TX_SKIP
-          this_rate += vp9_cost_bit(cpi->common.fc.
-                                    uv_tx_skip_prob[mbmi->tx_skip[0]],
-                                    mbmi->tx_skip[1]);
+        this_rate += vp9_cost_bit(cpi->common.fc.
+                                  uv_tx_skip_prob[mbmi->tx_skip[0]],
+                                  mbmi->tx_skip[1]);
 #endif  // CONFIG_TX_SKIP
-          this_rd = RDCOST(x->rdmult, x->rddiv, this_rate, this_distortion);
-          if (this_rd < best_rd) {
-            mode_selected   = DC_PRED;
-            best_rd         = this_rd;
-            *rate           = this_rate;
-            *rate_tokenonly = this_rate_tokenonly;
-            *distortion     = this_distortion;
-            *skippable      = s;
-            best_n = n;
-            best_l = l;
-            palette_selected = 1;
-            best_ps = ps;
-            vpx_memcpy(best_palette, mbmi->palette_colors + PALETTE_MAX_SIZE,
-                       2 * PALETTE_MAX_SIZE * sizeof(best_palette[0]));
-            vpx_memcpy(best_runs, mbmi->palette_runs + PALETTE_MAX_RUNS,
-                       PALETTE_MAX_RUNS * sizeof(best_runs[0]));
+        this_rd = RDCOST(x->rdmult, x->rddiv, this_rate, this_distortion);
+        if (this_rd < best_rd) {
+          mode_selected   = DC_PRED;
+          best_rd         = this_rd;
+          *rate           = this_rate;
+          *rate_tokenonly = this_rate_tokenonly;
+          *distortion     = this_distortion;
+          *skippable      = s;
+          best_n = n;
+          best_l = l;
+          palette_selected = 1;
+          best_ps = ps;
+          vpx_memcpy(best_palette, mbmi->palette_colors + PALETTE_MAX_SIZE,
+                     2 * PALETTE_MAX_SIZE * sizeof(best_palette[0]));
+          vpx_memcpy(best_runs, mbmi->palette_runs + PALETTE_MAX_RUNS,
+                     PALETTE_MAX_RUNS * sizeof(best_runs[0]));
 #if CONFIG_TX_SKIP
-            tx_skipped = mbmi->tx_skip[1];
+          tx_skipped = mbmi->tx_skip[1];
 #endif  // CONFIG_TX_SKIP
 #if CONFIG_FILTERINTRA
-            fbit_selected = 0;
+          fbit_selected = 0;
 #endif  // CONFIG_FILTERINTRA
-          }
         }
       }
     }
@@ -2198,11 +2211,11 @@ static int64_t rd_pick_intra_sbuv_mode(VP9_COMP *cpi, MACROBLOCK *x,
                2 * PALETTE_MAX_SIZE * sizeof(best_palette[0]));
     vpx_memcpy(mbmi->palette_runs + PALETTE_MAX_RUNS, best_runs,
                best_l * sizeof(best_runs[0]));
-    run_lengh_decoding(mbmi->palette_runs + PALETTE_MAX_RUNS,
-                       mbmi->palette_run_length[1], xd->palette_map_buffer);
-    palette_iscan(xd->plane[1].color_index_map, xd->palette_map_buffer,
-                  rows, cols, mbmi->palette_scan_order[1],
-                  xd->palette_scan_buffer);
+    vp9_run_lengh_decoding(mbmi->palette_runs + PALETTE_MAX_RUNS,
+                           mbmi->palette_run_length[1], xd->palette_map_buffer);
+    vp9_palette_iscan(xd->plane[1].color_index_map, xd->palette_map_buffer,
+                      rows, cols, mbmi->palette_scan_order[1],
+                      xd->palette_scan_buffer);
   }
 #endif  // CONFIG_PALETTE
   return best_rd;
@@ -4860,7 +4873,7 @@ void vp9_rd_pick_intra_mode_sb(VP9_COMP *cpi, MACROBLOCK *x,
     int cols = 4 * num_4x4_blocks_wide_lookup[bsize];
     int src_stride_y = x->plane[0].src.stride;
     int src_stride_uv = x->plane[1].src.stride;
-    int colors = count_colors(src_y, src_stride_y, rows, cols);
+    int colors = vp9_count_colors(src_y, src_stride_y, rows, cols);
 
     if (colors >= 2 && colors <= 64 && cm->allow_palette_mode) {
       uint16_t best_runs[PALETTE_MAX_RUNS];
@@ -4869,17 +4882,19 @@ void vp9_rd_pick_intra_mode_sb(VP9_COMP *cpi, MACROBLOCK *x,
       int8_t palette_color_delta[PALETTE_MAX_SIZE];
       int64_t local_tx_cache[TX_MODES], sse;
       int m1, m2, n, l, best_bits, best_n = 0, best_l = 0;
-      int r, c, i, j;
-      int d = get_bit_depth(rows * cols), max_itr = 200;
+      int r, c, i, j, max_itr = 200;
       int palette_run_length_cost[PALETTE_RUN_LENGTHS];
       int palette_size_cost[PALETTE_SIZES];
       int best_m1 = 0, best_m2 = 0, palette_delta_bitdepth = 0;
+      int color_ctx = 0, color_idx = 0;
+      int color_order[PALETTE_MAX_SIZE];
       double centroids[3 * PALETTE_MAX_SIZE];
       double lb = src_y[0], ub = src_y[0];
       MB_MODE_INFO *mbmi = &xd->mi[0].src_mi->mbmi;
       MB_MODE_INFO mbmi_copy;
       RD_COST palette_rd, palette_best_rd;
       PALETTE_SCAN_ORDER ps, best_ps = H_SCAN;
+      uint8_t *color_map;
 #if CONFIG_TX_SKIP
       int q_idx = vp9_get_qindex(&cpi->common.seg, mbmi->segment_id,
                                  cpi->common.base_qindex);
@@ -4928,8 +4943,8 @@ void vp9_rd_pick_intra_mode_sb(VP9_COMP *cpi, MACROBLOCK *x,
           centroids[i * 3 + 1] = 128;
           centroids[i * 3 + 2] = 128;
         }
-        r = k_means(x->kmeans_data_buffer, centroids, x->kmeans_indices_buffer,
-                    rows * cols, n, 3, max_itr);
+        r = vp9_k_means(x->kmeans_data_buffer, centroids,
+                        x->kmeans_indices_buffer, rows * cols, n, 3, max_itr);
         for (i = 0; i < 3; i++) {
           for (j = 0; j < n; j++)
             mbmi->palette_colors[i * PALETTE_MAX_SIZE + j] =
@@ -4938,13 +4953,12 @@ void vp9_rd_pick_intra_mode_sb(VP9_COMP *cpi, MACROBLOCK *x,
         for (r = 0; r < rows; r++)
           for (c = 0; c < cols; c++)
             xd->plane[0].color_index_map[r * cols + c] =
-                x->kmeans_data_buffer[r * cols + c];
+                x->kmeans_indices_buffer[r * cols + c];
         m1 = 0;
         m2 = n;
         best_bits = 0;
         vpx_memcpy(mbmi->palette_literal_colors, mbmi->palette_colors,
                    m2 * sizeof(mbmi->palette_literal_colors[0]));
-
 #if CONFIG_TX_SKIP
         mbmi->tx_skip[0] = 0;
         mbmi->tx_skip[1] = 0;
@@ -5016,65 +5030,76 @@ void vp9_rd_pick_intra_mode_sb(VP9_COMP *cpi, MACROBLOCK *x,
           continue;
 
         for (ps = H_SCAN; ps < PALETTE_SCAN_ORDERS; ps++) {
-          palette_scan(xd->plane[0].color_index_map, xd->palette_map_buffer,
-                       rows, cols, ps, xd->palette_scan_buffer);
-          l = run_lengh_encoding(xd->palette_map_buffer, rows * cols,
-                                 mbmi->palette_runs, palette_max_run(bsize));
-          if (!l)
-            continue;
+          vp9_palette_scan(xd->plane[0].color_index_map, xd->palette_map_buffer,
+                           rows, cols, ps, xd->palette_scan_buffer);
+          l = vp9_run_lengh_encoding(xd->palette_map_buffer, rows * cols,
+                                     mbmi->palette_runs, PALETTE_MAX_RUNS >> 1);
+          if (l)
+            break;
+        }
+        if (!l)
+          continue;
 
-          rate_y = rate_y_tokenonly +
-              (1 + PALETTE_DELTA_BIT + get_bit_depth(palette_max_run(bsize)) +
-                  2 + n * m2 + get_bit_depth(n) * (l >> 1)) *
-                  vp9_cost_bit(128, 0) + palette_size_cost[n - 2];
-          for (i = 0; i < l; i += 2) {
-            int bits = get_bit_depth(mbmi->palette_runs[i + 1]);
-            rate_y += palette_run_length_cost[bits > 6 ? 6 : bits - 1];
-            rate_y += (bits > 6 ? d : bits) * vp9_cost_bit(128, 0);
+        rate_y = rate_y_tokenonly +
+            (1 + PALETTE_DELTA_BIT + n * m2) * vp9_cost_bit(128, 0) +
+                palette_size_cost[n - 2];
+        color_map = xd->plane[0].color_index_map;
+        rate_y +=  vp9_get_bit_depth(n) * vp9_cost_bit(128, 0);
+
+        for (i = 0; i < rows; i++) {
+          for (j = (i == 0 ? 1 : 0); j < cols; j++) {
+            color_ctx = vp9_get_palette_color_context(color_map, cols, i, j, n,
+                                                      color_order);
+            for (r = 0; r < n; r++)
+              if (color_map[i * cols + j] == color_order[r]) {
+                color_idx = r;
+                break;
+              }
+            rate_y += cpi->palette_color_costs[n - 2][color_ctx][color_idx];
           }
-          rate_uv = rate_uv_tokenonly +
-              (1 +  8 * 2 * n) * vp9_cost_bit(128, 0);
+        }
+        rate_uv = rate_uv_tokenonly +
+            (1 +  8 * 2 * n) * vp9_cost_bit(128, 0);
 #if CONFIG_TX_SKIP
-          rate_y += vp9_cost_bit(cpi->common.fc.y_tx_skip_prob[0],
-                                 mbmi->tx_skip[0]);
-          rate_uv +=
-              vp9_cost_bit(cpi->common.fc.uv_tx_skip_prob[mbmi->tx_skip[0]],
-                           mbmi->tx_skip[1]);
+        rate_y += vp9_cost_bit(cpi->common.fc.y_tx_skip_prob[0],
+                               mbmi->tx_skip[0]);
+        rate_uv +=
+            vp9_cost_bit(cpi->common.fc.uv_tx_skip_prob[mbmi->tx_skip[0]],
+                         mbmi->tx_skip[1]);
 #endif  // CONFIG_TX_SKIP
-          if (y_skip && uv_skip) {
-            palette_rd.rate = rate_y + rate_uv - rate_y_tokenonly -
-                rate_uv_tokenonly + vp9_cost_bit(vp9_get_skip_prob(cm, xd), 1);
-            palette_rd.dist = dist_y + dist_uv;
-          } else {
-            palette_rd.rate = rate_y + rate_uv +
-                vp9_cost_bit(vp9_get_skip_prob(cm, xd), 0);
-            palette_rd.dist = dist_y + dist_uv;
-          }
-          palette_rd.rdcost =
-              RDCOST(x->rdmult, x->rddiv, palette_rd.rate, palette_rd.dist);
-          if (palette_rd.rdcost < palette_best_rd.rdcost) {
-            palette_best_rd = palette_rd;
-            best_n = n;
-            best_l = l;
-            best_ps = ps;
-            best_m1 = m1;
-            best_m2 = m2;
-            palette_delta_bitdepth = best_bits;
+        if (y_skip && uv_skip) {
+          palette_rd.rate = rate_y + rate_uv - rate_y_tokenonly -
+              rate_uv_tokenonly + vp9_cost_bit(vp9_get_skip_prob(cm, xd), 1);
+          palette_rd.dist = dist_y + dist_uv;
+        } else {
+          palette_rd.rate = rate_y + rate_uv +
+              vp9_cost_bit(vp9_get_skip_prob(cm, xd), 0);
+          palette_rd.dist = dist_y + dist_uv;
+        }
+        palette_rd.rdcost =
+            RDCOST(x->rdmult, x->rddiv, palette_rd.rate, palette_rd.dist);
+        if (palette_rd.rdcost < palette_best_rd.rdcost) {
+          palette_best_rd = palette_rd;
+          best_n = n;
+          best_l = l;
+          best_ps = ps;
+          best_m1 = m1;
+          best_m2 = m2;
+          palette_delta_bitdepth = best_bits;
 #if CONFIG_TX_SKIP
-            tx_skipped = mbmi->tx_skip[0];
-            tx_skipped_uv = mbmi->tx_skip[1];
+          tx_skipped = mbmi->tx_skip[0];
+          tx_skipped_uv = mbmi->tx_skip[1];
 #endif  // CONFIG_TX_SKIP
 
-            vpx_memcpy(best_palette, mbmi->palette_colors,
-                       PALETTE_MAX_SIZE * 3 * sizeof(best_palette[0]));
-            vpx_memcpy(best_runs, mbmi->palette_runs, l * sizeof(best_runs[0]));
-            vpx_memcpy(best_index, mbmi->palette_indexed_colors,
-                       best_m1 * sizeof(best_index[0]));
-            vpx_memcpy(palette_color_delta, mbmi->palette_color_delta,
-                       best_m1 * sizeof(palette_color_delta[0]));
-            vpx_memcpy(best_literal, mbmi->palette_literal_colors,
-                       best_m2 * sizeof(best_literal[0]));
-          }
+          vpx_memcpy(best_palette, mbmi->palette_colors,
+                     PALETTE_MAX_SIZE * 3 * sizeof(best_palette[0]));
+          vpx_memcpy(best_runs, mbmi->palette_runs, l * sizeof(best_runs[0]));
+          vpx_memcpy(best_index, mbmi->palette_indexed_colors,
+                     best_m1 * sizeof(best_index[0]));
+          vpx_memcpy(palette_color_delta, mbmi->palette_color_delta,
+                     best_m1 * sizeof(palette_color_delta[0]));
+          vpx_memcpy(best_literal, mbmi->palette_literal_colors,
+                     best_m2 * sizeof(best_literal[0]));
         }
       }
 
@@ -5111,23 +5136,32 @@ void vp9_rd_pick_intra_mode_sb(VP9_COMP *cpi, MACROBLOCK *x,
 #endif  // CONFIG_TX_SKIP
       } else {
         *mbmi = mbmi_copy;
-        if (mbmi->palette_enabled[0]) {
-          run_lengh_decoding(mbmi->palette_runs, mbmi->palette_run_length[0],
-                             xd->palette_map_buffer);
-          palette_iscan(xd->plane[0].color_index_map, xd->palette_map_buffer,
-                        rows, cols, mbmi->palette_scan_order[0],
-                        xd->palette_scan_buffer);
-        }
+      }
+      if (mbmi->palette_enabled[0]) {
+        vp9_run_lengh_decoding(mbmi->palette_runs, mbmi->palette_run_length[0],
+                               xd->palette_map_buffer);
+        vp9_palette_iscan(xd->plane[0].color_index_map, xd->palette_map_buffer,
+                          rows, cols, mbmi->palette_scan_order[0],
+                          xd->palette_scan_buffer);
+      }
+
+      if (mbmi->palette_enabled[1]) {
+        vp9_run_lengh_decoding(mbmi->palette_runs + PALETTE_MAX_RUNS,
+                               mbmi->palette_run_length[1],
+                               xd->palette_map_buffer);
+        vp9_palette_iscan(xd->plane[1].color_index_map, xd->palette_map_buffer,
+                          rows, cols, mbmi->palette_scan_order[1],
+                          xd->palette_scan_buffer);
       }
       ctx->mic = *xd->mi[0].src_mi;
     }
   }
 
   if (xd->mi[0].src_mi->mbmi.palette_enabled[0]) {
-    palette_color_insertion(ctx->palette_colors_buf,
-                            &ctx->palette_buf_size,
-                            ctx->palette_count_buf,
-                            &(xd->mi[0].src_mi->mbmi));
+    vp9_palette_color_insertion(ctx->palette_colors_buf,
+                                &ctx->palette_buf_size,
+                                ctx->palette_count_buf,
+                                &(xd->mi[0].src_mi->mbmi));
   }
 #endif  // CONFIG_PALETTE
 }
@@ -6381,26 +6415,27 @@ void vp9_rd_pick_inter_mode_sb(VP9_COMP *cpi, MACROBLOCK *x,
   if (bsize >= BLOCK_8X8 && cpi->common.allow_palette_mode &&
       !is_inter_block(mbmi)) {
     MB_MODE_INFO mbmi_copy = *mbmi;
-    colors = count_colors(src, src_stride, rows, cols);
+    colors = vp9_count_colors(src, src_stride, rows, cols);
     x->skip = 0;
     if (colors > 1 && colors <= 64) {
-      int n, r, c, i, j, max_itr = 200, k;
-      int l, d = get_bit_depth(rows * cols);
+      int n, r, c, i, j, max_itr = 200, k, l;
+      int color_ctx = 0, color_idx = 0;
+      int color_order[PALETTE_MAX_SIZE];
       int palette_size_cost[PALETTE_SIZES];
       int palette_run_length_cost[PALETTE_RUN_LENGTHS];
-      int palette_scan_order_cost[PALETTE_SCAN_ORDERS];
       double centroids[PALETTE_MAX_SIZE];
       double lb = src[0], ub = src[0], val;
       PALETTE_SCAN_ORDER ps;
 
       int64_t this_rd = INT64_MAX, this_rd_y, best_rd_y;
       int rate2, rate_y , rate_uv, best_token_rate_y = INT_MAX;
-      int total_rate_y, current_best_total_rate_y, best_total_rate_y = INT_MAX;
+      int total_rate_y, best_total_rate_y = INT_MAX;
       int64_t distortion2, distortion_y, distortion_uv;
       int64_t best_distortion_y = INT64_MAX;
       int skippable, skip_y = 0;
       int64_t tx_cache[TX_MODES];
       TX_SIZE uv_tx;
+      uint8_t *color_map;
 #if CONFIG_TX_SKIP
       int rate_y_s, skippable_s;
       int64_t distortion_y_s;
@@ -6419,9 +6454,6 @@ void vp9_rd_pick_inter_mode_sb(VP9_COMP *cpi, MACROBLOCK *x,
       vp9_cost_tokens(palette_run_length_cost,
                       cpi->common.fc.palette_run_length_prob[bsize - BLOCK_8X8],
                       vp9_palette_run_length_tree);
-      vp9_cost_tokens(palette_scan_order_cost,
-                      cpi->common.fc.palette_scan_order_prob[bsize - BLOCK_8X8],
-                      vp9_palette_scan_order_tree);
       mbmi->ref_frame[0] = INTRA_FRAME;
       mbmi->mode = DC_PRED;
       for (r = 0; r < rows; r++) {
@@ -6446,9 +6478,9 @@ void vp9_rd_pick_inter_mode_sb(VP9_COMP *cpi, MACROBLOCK *x,
           n >= 2; n--) {
         for (i = 0; i < n; i++)
           centroids[i] = lb + (2 * i + 1) * (ub - lb) / n / 2;
-        r = k_means(x->kmeans_data_buffer, centroids, x->kmeans_indices_buffer,
-                    rows * cols, n, 1, max_itr);
-        insertion_sort(centroids, n);
+        r = vp9_k_means(x->kmeans_data_buffer, centroids,
+                        x->kmeans_indices_buffer, rows * cols, n, 1, max_itr);
+        vp9_insertion_sort(centroids, n);
         i = 1;
         k = n;
         while (i < k) {
@@ -6469,8 +6501,8 @@ void vp9_rd_pick_inter_mode_sb(VP9_COMP *cpi, MACROBLOCK *x,
           mbmi->palette_colors[i] = clip_pixel(round(centroids[i]));
           centroids[i] = (double) mbmi->palette_colors[i];
         }
-        calc_indices(x->kmeans_data_buffer, centroids, x->kmeans_indices_buffer,
-                     rows * cols, k, 1);
+        vp9_calc_indices(x->kmeans_data_buffer, centroids,
+                         x->kmeans_indices_buffer, rows * cols, k, 1);
         for (r = 0; r < rows; r++) {
           for (c = 0; c < cols; c++) {
             xd->plane[0].color_index_map[r * cols + c] =
@@ -6510,52 +6542,46 @@ void vp9_rd_pick_inter_mode_sb(VP9_COMP *cpi, MACROBLOCK *x,
           continue;
         }
 
-        current_best_total_rate_y = INT_MAX;
         for (ps = H_SCAN; ps < PALETTE_SCAN_ORDERS; ps++) {
-          palette_scan(xd->plane[0].color_index_map, xd->palette_map_buffer,
-                       rows, cols, ps, xd->palette_scan_buffer);
-          l = run_lengh_encoding(xd->palette_map_buffer, rows * cols,
-                                 mbmi->palette_runs, palette_max_run(bsize));
-          if (!l)
-            continue;
+          vp9_palette_scan(xd->plane[0].color_index_map, xd->palette_map_buffer,
+                           rows, cols, ps, xd->palette_scan_buffer);
+          l = vp9_run_lengh_encoding(xd->palette_map_buffer, rows * cols,
+                                     mbmi->palette_runs, PALETTE_MAX_RUNS >> 1);
+          if (l)
+            break;
+        }
+        if (!l)
+          continue;
 
-          total_rate_y = rate_y +
-              (get_bit_depth(palette_max_run(bsize)) + 8 * k +
-                  get_bit_depth(k) * (l >> 1)) * vp9_cost_bit(128, 0) +
-                  vp9_cost_bit(cm->fc.palette_enabled_prob
-                               [bsize - BLOCK_8X8][palette_ctx], 1) +
-                               palette_size_cost[k - 2] +
-                               palette_scan_order_cost[ps];
-          for (i = 0; i < l; i += 2) {
-            int bits = get_bit_depth(mbmi->palette_runs[i + 1]);
-            total_rate_y += palette_run_length_cost[bits > 6 ? 6 : bits - 1];
-            total_rate_y += (bits > 6 ? d : bits) * vp9_cost_bit(128, 0);
+        total_rate_y = rate_y + palette_size_cost[k - 2] +
+            8 * k * vp9_cost_bit(128, 0) +
+            vp9_cost_bit(cm->fc.palette_enabled_prob
+                         [bsize - BLOCK_8X8][palette_ctx], 1);
+        color_map = xd->plane[0].color_index_map;
+        total_rate_y +=  vp9_get_bit_depth(k) * vp9_cost_bit(128, 0);
+        for (i = 0; i < rows; i++) {
+          for (j = (i == 0 ? 1 : 0); j < cols; j++) {
+            color_ctx = vp9_get_palette_color_context(color_map, cols, i, j, n,
+                                                      color_order);
+            for (r = 0; r < n; r++)
+              if (color_map[i * cols + j] == color_order[r]) {
+                color_idx = r;
+                break;
+              }
+            total_rate_y += cpi->palette_color_costs[k - 2][color_ctx]
+                                                            [color_idx];
           }
+        }
 #if CONFIG_TX_SKIP
           total_rate_y += vp9_cost_bit(cpi->common.fc.y_tx_skip_prob[0],
                                  mbmi->tx_skip[0]);
 #endif  // CONFIG_TX_SKIP
-          if (total_rate_y < current_best_total_rate_y) {
-            mbmi->palette_scan_order[0] = ps;
-            current_best_total_rate_y = total_rate_y;
-          }
-        }
-
-        palette_scan(xd->plane[0].color_index_map, xd->palette_map_buffer,
-                     rows, cols, mbmi->palette_scan_order[0],
-                     xd->palette_scan_buffer);
-        l = run_lengh_encoding(xd->palette_map_buffer, rows * cols,
-                               mbmi->palette_runs, palette_max_run(bsize));
-        if (!l)
-          continue;
-
-        this_rd_y = RDCOST(x->rdmult, x->rddiv,
-                           current_best_total_rate_y, distortion_y);
+        this_rd_y = RDCOST(x->rdmult, x->rddiv, total_rate_y, distortion_y);
         if (this_rd_y < best_rd_y) {
           best_rd_y = this_rd_y;
           skip_y = skippable;
           best_distortion_y = distortion_y;
-          best_total_rate_y = current_best_total_rate_y;
+          best_total_rate_y = total_rate_y;
           best_token_rate_y = rate_y;
           best_n = k;
           best_l = l;
@@ -6574,57 +6600,18 @@ void vp9_rd_pick_inter_mode_sb(VP9_COMP *cpi, MACROBLOCK *x,
         uv_tx = get_uv_tx_size_impl(mbmi->tx_size, bsize,
                                     xd->plane[1].subsampling_x,
                                     xd->plane[1].subsampling_y);
-        if (rate_uv_intra[uv_tx] == INT_MAX) {
-          choose_intra_uv_mode(cpi, ctx, bsize, uv_tx,
-                               &rate_uv_intra[uv_tx], &rate_uv_tokenonly[uv_tx],
-                               &dist_uv[uv_tx], &skip_uv[uv_tx],
+        choose_intra_uv_mode(cpi, ctx, bsize, uv_tx,
+                             &rate_uv_intra[uv_tx], &rate_uv_tokenonly[uv_tx],
+                             &dist_uv[uv_tx], &skip_uv[uv_tx],
 #if CONFIG_FILTERINTRA
-                               &fbit_uv[uv_tx],
+                             &fbit_uv[uv_tx],
 #endif  // CONFIG_FILTERINTRA
-                               &mode_uv[uv_tx]);
-          palette_enabled_uv[uv_tx] = mbmi->palette_enabled[1];
-          if (palette_enabled_uv[uv_tx]) {
-            palette_size_uv[uv_tx] = mbmi->palette_size[1];
-            palette_run_length_uv[uv_tx] = mbmi->palette_run_length[1];
-            ps_uv[uv_tx] = mbmi->palette_scan_order[1];
-            vpx_memcpy(&palette_colors_uv[uv_tx][0],
-                       mbmi->palette_colors + PALETTE_MAX_SIZE,
-                       2 * PALETTE_MAX_SIZE *
-                       sizeof(palette_colors_uv[uv_tx][0]));
-            vpx_memcpy(&palette_runs_uv[uv_tx][0],
-                       mbmi->palette_runs + PALETTE_MAX_RUNS,
-                       PALETTE_MAX_RUNS * sizeof(palette_runs_uv[uv_tx][0]));
-          }
-#if CONFIG_TX_SKIP
-          tx_skipped_uv[uv_tx] = mbmi->tx_skip[1];
-#endif  // CONFIG_TX_SKIP
-        }
-
+                             &mode_uv[uv_tx]);
         rate_uv = rate_uv_tokenonly[uv_tx];
         distortion_uv = dist_uv[uv_tx];
         skippable = skip_y && skip_uv[uv_tx];
         mbmi->uv_mode = mode_uv[uv_tx];
 
-        mbmi->palette_enabled[1] = palette_enabled_uv[uv_tx];
-        if (mbmi->palette_enabled[1]) {
-          mbmi->palette_size[1] = palette_size_uv[uv_tx];
-          mbmi->palette_run_length[1] = palette_run_length_uv[uv_tx];
-          mbmi->palette_scan_order[1] = ps_uv[uv_tx];
-          vpx_memcpy(mbmi->palette_colors + PALETTE_MAX_SIZE,
-                     &palette_colors_uv[uv_tx][0],
-                     2 * PALETTE_MAX_SIZE *
-                     sizeof(palette_colors_uv[uv_tx][0]));
-          vpx_memcpy(mbmi->palette_runs + PALETTE_MAX_RUNS,
-                     &palette_runs_uv[uv_tx][0],
-                     PALETTE_MAX_RUNS * sizeof(palette_runs_uv[uv_tx][0]));
-        }
-#if CONFIG_FILTERINTRA
-        mbmi->uv_filterbit = fbit_uv[uv_tx];
-#endif  // CONFIG_FILTERINTRA
-#if CONFIG_TX_SKIP
-        mbmi->tx_skip[1] = tx_skipped_uv[uv_tx];
-#endif  // CONFIG_TX_SKIP
-
         rate2 = best_total_rate_y + rate_uv_intra[uv_tx];
         distortion2 = best_distortion_y + distortion_uv;
         x->skip = skippable;
@@ -6677,24 +6664,24 @@ void vp9_rd_pick_inter_mode_sb(VP9_COMP *cpi, MACROBLOCK *x,
     int rows = 4 * num_4x4_blocks_high_lookup[bsize];
     int cols = 4 * num_4x4_blocks_wide_lookup[bsize];
 
-    run_lengh_decoding(mbmi->palette_runs, mbmi->palette_run_length[0],
-                       xd->palette_map_buffer);
-    palette_iscan(xd->plane[0].color_index_map, xd->palette_map_buffer,
-                  rows, cols, mbmi->palette_scan_order[0],
-                  xd->palette_scan_buffer);
+    vp9_run_lengh_decoding(mbmi->palette_runs, mbmi->palette_run_length[0],
+                           xd->palette_map_buffer);
+    vp9_palette_iscan(xd->plane[0].color_index_map, xd->palette_map_buffer,
+                      rows, cols, mbmi->palette_scan_order[0],
+                      xd->palette_scan_buffer);
   }
 
   if (mbmi->palette_enabled[1]) {
     int rows = 4 * num_4x4_blocks_high_lookup[bsize] >>
         xd->plane[1].subsampling_y;
     int cols = 4 * num_4x4_blocks_wide_lookup[bsize] >>
-        xd->plane[1].subsampling_y;
+        xd->plane[1].subsampling_x;
 
-    run_lengh_decoding(mbmi->palette_runs + PALETTE_MAX_RUNS,
-                       mbmi->palette_run_length[1], xd->palette_map_buffer);
-    palette_iscan(xd->plane[1].color_index_map, xd->palette_map_buffer,
-                  rows, cols, mbmi->palette_scan_order[1],
-                  xd->palette_scan_buffer);
+    vp9_run_lengh_decoding(mbmi->palette_runs + PALETTE_MAX_RUNS,
+                           mbmi->palette_run_length[1], xd->palette_map_buffer);
+    vp9_palette_iscan(xd->plane[1].color_index_map, xd->palette_map_buffer,
+                      rows, cols, mbmi->palette_scan_order[1],
+                      xd->palette_scan_buffer);
   }
 #endif  // CONFIG_PALETTE
 }
-- 
2.49.0