VP10: Add palette mode part 1

Add palette mode for keyframe luma channel. Palette mode is enabled
when using "--tune-content=screen" in encoding config parameters.

on screen_content testset:  +6.89%
on derlr                 :  +0.00%

Design doc (WIP):
https://goo.gl/lD4yJw

Change-Id: Ib368b216bfd3ea21c6c27436934ad87afdaa6f88

26 files changed, 1272 insertions, 0 deletions

diff --git a/vp10/common/blockd.h b/vp10/common/blockd.h
index db49d9755..6d921b532 100644
--- a/vp10/common/blockd.h
+++ b/vp10/common/blockd.h
@@ -63,6 +63,20 @@ typedef struct {
 #define MAX_REF_FRAMES  4
 typedef int8_t MV_REFERENCE_FRAME;
 
+typedef struct {
+  // Number of base colors for Y (0) and UV (1)
+  uint8_t palette_size[2];
+  // Value of base colors for Y, U, and V
+#if CONFIG_VP9_HIGHBITDEPTH
+  uint16_t palette_colors[3 * PALETTE_MAX_SIZE];
+#else
+  uint8_t palette_colors[3 * PALETTE_MAX_SIZE];
+#endif  // CONFIG_VP9_HIGHBITDEPTH
+  // Only used by encoder to store the color index of the top left pixel.
+  // TODO(huisu): move this to encoder
+  uint8_t palette_first_color_idx[2];
+} PALETTE_MODE_INFO;
+
 // This structure now relates to 8x8 block regions.
 typedef struct {
   // Common for both INTER and INTRA blocks
@@ -78,6 +92,7 @@ typedef struct {
 
   // Only for INTRA blocks
   PREDICTION_MODE uv_mode;
+  PALETTE_MODE_INFO palette_mode_info;
 
   // Only for INTER blocks
   INTERP_FILTER interp_filter;
@@ -131,6 +146,7 @@ struct macroblockd_plane {
   ENTROPY_CONTEXT *above_context;
   ENTROPY_CONTEXT *left_context;
   int16_t seg_dequant[MAX_SEGMENTS][2];
+  uint8_t *color_index_map;
 
   // number of 4x4s in current block
   uint16_t n4_w, n4_h;
diff --git a/vp10/common/entropymode.c b/vp10/common/entropymode.c
index 009f1c913..a9fb71136 100644
--- a/vp10/common/entropymode.c
+++ b/vp10/common/entropymode.c
@@ -275,6 +275,438 @@ static const struct tx_probs default_tx_probs = {
     { 66  } }
 };
 
+const vpx_tree_index vp10_palette_size_tree[TREE_SIZE(PALETTE_SIZES)] = {
+    -TWO_COLORS, 2,
+    -THREE_COLORS, 4,
+    -FOUR_COLORS, 6,
+    -FIVE_COLORS, 8,
+    -SIX_COLORS, 10,
+    -SEVEN_COLORS, -EIGHT_COLORS,
+};
+
+// TODO(huisu): tune these probs
+const vpx_prob vp10_default_palette_y_size_prob[10][PALETTE_SIZES - 1] = {
+    {  96,  89, 100,  64,  77, 130},
+    {  22,  15,  44,  16,  34,  82},
+    {  30,  19,  57,  18,  38,  86},
+    {  94,  36, 104,  23,  43,  92},
+    { 116,  76, 107,  46,  65, 105},
+    { 112,  82,  94,  40,  70, 112},
+    { 147, 124, 123,  58,  69, 103},
+    { 180, 113, 136,  49,  45, 114},
+    { 107,  70,  87,  49, 154, 156},
+    {  98, 105, 142,  63,  64, 152},
+};
+
+const vpx_prob vp10_default_palette_uv_size_prob[10][PALETTE_SIZES - 1] = {
+    { 160, 196, 228, 213, 175, 230},
+    {  87, 148, 208, 141, 166, 163},
+    {  72, 151, 204, 139, 155, 161},
+    {  78, 135, 171, 104, 120, 173},
+    {  59,  92, 131,  78,  92, 142},
+    {  75, 118, 149,  84,  90, 128},
+    {  89,  87,  92,  66,  66, 128},
+    {  67,  53,  54,  55,  66,  93},
+    { 120, 130,  83, 171,  75, 214},
+    {  72,  55,  66,  68,  79, 107},
+};
+
+const vpx_prob vp10_default_palette_y_mode_prob[10][3] = {
+    { 240,  180,  100, },
+    { 240,  180,  100, },
+    { 240,  180,  100, },
+    { 240,  180,  100, },
+    { 240,  180,  100, },
+    { 240,  180,  100, },
+    { 240,  180,  100, },
+    { 240,  180,  100, },
+    { 240,  180,  100, },
+    { 240,  180,  100, },
+};
+
+
+const vpx_prob default_uv_palette_mode_prob[2] = {
+    253, 229
+};
+
+const vpx_tree_index
+vp10_palette_color_tree[PALETTE_MAX_SIZE - 1][TREE_SIZE(PALETTE_COLORS)] = {
+    {  // 2 colors
+        -PALETTE_COLOR_ONE, -PALETTE_COLOR_TWO,
+    },
+    {  // 3 colors
+        -PALETTE_COLOR_ONE, 2,
+        -PALETTE_COLOR_TWO, -PALETTE_COLOR_THREE,
+    },
+    {  // 4 colors
+        -PALETTE_COLOR_ONE, 2,
+        -PALETTE_COLOR_TWO, 4,
+        -PALETTE_COLOR_THREE, -PALETTE_COLOR_FOUR,
+    },
+    {  // 5 colors
+        -PALETTE_COLOR_ONE, 2,
+        -PALETTE_COLOR_TWO, 4,
+        -PALETTE_COLOR_THREE, 6,
+        -PALETTE_COLOR_FOUR, -PALETTE_COLOR_FIVE,
+    },
+    {  // 6 colors
+        -PALETTE_COLOR_ONE, 2,
+        -PALETTE_COLOR_TWO, 4,
+        -PALETTE_COLOR_THREE, 6,
+        -PALETTE_COLOR_FOUR, 8,
+        -PALETTE_COLOR_FIVE, -PALETTE_COLOR_SIX,
+    },
+    {  // 7 colors
+        -PALETTE_COLOR_ONE, 2,
+        -PALETTE_COLOR_TWO, 4,
+        -PALETTE_COLOR_THREE, 6,
+        -PALETTE_COLOR_FOUR, 8,
+        -PALETTE_COLOR_FIVE, 10,
+        -PALETTE_COLOR_SIX, -PALETTE_COLOR_SEVEN,
+    },
+    {  // 8 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,
+    },
+};
+
+const vpx_prob vp10_default_palette_y_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 },
+    }
+};
+
+const vpx_prob vp10_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 },
+    }
+};
+
+static const int palette_color_context_lookup[PALETTE_COLOR_CONTEXTS] = {
+    // (3, 0, 0, 0), (3, 2, 0, 0), (3, 3, 2, 0), (3, 3, 2, 2),
+    3993,  4235,  4378,  4380,
+    // (4, 3, 3, 0), (5, 0, 0, 0), (5, 3, 0, 0), (5, 3, 2, 0),
+    5720,  6655,  7018,  7040,
+    // (5, 5, 0, 0), (6, 2, 0, 0), (6, 2, 2, 0), (6, 4, 0, 0),
+    7260,  8228,  8250,  8470,
+    // (7, 3, 0, 0), (8, 0, 0, 0), (8, 2, 0, 0), (10, 0, 0, 0)
+    9680, 10648, 10890, 13310
+};
+
+int vp10_get_palette_color_context(const 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 + 10];
+  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];
+  }
+
+  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;
+    }
+
+  if (color_ctx >= PALETTE_COLOR_CONTEXTS)
+    color_ctx = 0;
+
+  return color_ctx;
+}
+
 void vp10_tx_counts_to_branch_counts_32x32(const unsigned int *tx_count_32x32p,
                                       unsigned int (*ct_32x32p)[2]) {
   ct_32x32p[0][0] = tx_count_32x32p[TX_4X4];
diff --git a/vp10/common/entropymode.h b/vp10/common/entropymode.h
index a8b749253..30b0ddb72 100644
--- a/vp10/common/entropymode.h
+++ b/vp10/common/entropymode.h
@@ -26,6 +26,12 @@ extern "C" {
 
 #define INTER_OFFSET(mode) ((mode) - NEARESTMV)
 
+#define PALETTE_COLOR_CONTEXTS 16
+#define PALETTE_MAX_SIZE 8
+#define PALETTE_BLOCK_SIZES (BLOCK_64X64 - BLOCK_8X8 + 1)
+#define PALETTE_Y_MODE_CONTEXTS 3
+
+
 struct VP10Common;
 
 struct tx_probs {
@@ -83,11 +89,26 @@ extern const vpx_prob vp10_kf_y_mode_prob[INTRA_MODES][INTRA_MODES]
                                         [INTRA_MODES - 1];
 extern const vpx_prob vp10_kf_partition_probs[PARTITION_CONTEXTS]
                                             [PARTITION_TYPES - 1];
+extern const vpx_prob
+vp10_default_palette_y_mode_prob[PALETTE_BLOCK_SIZES][PALETTE_Y_MODE_CONTEXTS];
+extern const vpx_prob
+vp10_default_palette_y_size_prob[PALETTE_BLOCK_SIZES][PALETTE_SIZES - 1];
+extern const vpx_prob
+vp10_default_palette_uv_size_prob[PALETTE_BLOCK_SIZES][PALETTE_SIZES - 1];
+extern const vpx_prob vp10_default_palette_y_color_prob
+[PALETTE_MAX_SIZE - 1][PALETTE_COLOR_CONTEXTS][PALETTE_COLORS - 1];
+extern const vpx_prob vp10_default_palette_uv_color_prob
+[PALETTE_MAX_SIZE - 1][PALETTE_COLOR_CONTEXTS][PALETTE_COLORS - 1];
+
 extern const vpx_tree_index vp10_intra_mode_tree[TREE_SIZE(INTRA_MODES)];
 extern const vpx_tree_index vp10_inter_mode_tree[TREE_SIZE(INTER_MODES)];
 extern const vpx_tree_index vp10_partition_tree[TREE_SIZE(PARTITION_TYPES)];
 extern const vpx_tree_index vp10_switchable_interp_tree
                                 [TREE_SIZE(SWITCHABLE_FILTERS)];
+extern const vpx_tree_index vp10_palette_size_tree[TREE_SIZE(PALETTE_SIZES)];
+extern const vpx_tree_index
+vp10_palette_color_tree[PALETTE_MAX_SIZE - 1][TREE_SIZE(PALETTE_COLORS)];
+
 
 void vp10_setup_past_independence(struct VP10Common *cm);
 
@@ -100,6 +121,18 @@ void vp10_tx_counts_to_branch_counts_16x16(const unsigned int *tx_count_16x16p,
 void vp10_tx_counts_to_branch_counts_8x8(const unsigned int *tx_count_8x8p,
                                     unsigned int (*ct_8x8p)[2]);
 
+static INLINE int vp10_ceil_log2(int n) {
+  int i = 1, p = 2;
+  while (p < n) {
+    i++;
+    p = p << 1;
+  }
+  return i;
+}
+
+int vp10_get_palette_color_context(const uint8_t *color_map, int cols,
+                                   int r, int c, int n, int *color_order);
+
 #ifdef __cplusplus
 }  // extern "C"
 #endif
diff --git a/vp10/common/enums.h b/vp10/common/enums.h
index a226a2d69..5f67e303e 100644
--- a/vp10/common/enums.h
+++ b/vp10/common/enums.h
@@ -109,6 +109,29 @@ typedef enum {
   PLANE_TYPES
 } PLANE_TYPE;
 
+typedef enum {
+  TWO_COLORS,
+  THREE_COLORS,
+  FOUR_COLORS,
+  FIVE_COLORS,
+  SIX_COLORS,
+  SEVEN_COLORS,
+  EIGHT_COLORS,
+  PALETTE_SIZES
+} PALETTE_SIZE;
+
+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;
+
 #define DC_PRED    0       // Average of above and left pixels
 #define V_PRED     1       // Vertical
 #define H_PRED     2       // Horizontal
diff --git a/vp10/common/onyxc_int.h b/vp10/common/onyxc_int.h
index e2454b0e2..73157b88d 100644
--- a/vp10/common/onyxc_int.h
+++ b/vp10/common/onyxc_int.h
@@ -185,6 +185,8 @@ typedef struct VP10Common {
 
   int allow_high_precision_mv;
 
+  int allow_screen_content_tools;
+
   // Flag signaling which frame contexts should be reset to default values.
   RESET_FRAME_CONTEXT_MODE reset_frame_context;
 
diff --git a/vp10/common/reconintra.c b/vp10/common/reconintra.c
index c53d7a197..5dc1a82b0 100644
--- a/vp10/common/reconintra.c
+++ b/vp10/common/reconintra.c
@@ -397,6 +397,40 @@ void vp10_predict_intra_block(const MACROBLOCKD *xd, int bwl_in,
   const int x = aoff * 4;
   const int y = loff * 4;
 
+  if (xd->mi[0]->mbmi.palette_mode_info.palette_size[plane != 0] > 0) {
+    const int bs = 4 * (1 << tx_size);
+    const int stride = 4 * (1 << bwl_in);
+    int r, c;
+    uint8_t *map = NULL;
+#if CONFIG_VP9_HIGHBITDEPTH
+    uint16_t *palette = xd->mi[0]->mbmi.palette_mode_info.palette_colors +
+        plane * PALETTE_MAX_SIZE;
+#else
+    uint8_t *palette = xd->mi[0]->mbmi.palette_mode_info.palette_colors +
+        plane * PALETTE_MAX_SIZE;
+#endif  // CONFIG_VP9_HIGHBITDEPTH
+
+    map = xd->plane[plane != 0].color_index_map;
+
+#if CONFIG_VP9_HIGHBITDEPTH
+    if (xd->cur_buf->flags & YV12_FLAG_HIGHBITDEPTH) {
+      uint16_t *dst16 = CONVERT_TO_SHORTPTR(dst);
+      for (r = 0; r < bs; ++r)
+        for (c = 0; c < bs; ++c)
+          dst16[r * dst_stride + c] =
+              palette[map[(r + y) * stride + c + x]];
+    } else {
+#endif  // CONFIG_VP9_HIGHBITDEPTH
+      for (r = 0; r < bs; ++r)
+        for (c = 0; c < bs; ++c)
+          dst[r * dst_stride + c] = palette[map[(r + y) * stride + c + x]];
+#if CONFIG_VP9_HIGHBITDEPTH
+    }
+#endif  // CONFIG_VP9_HIGHBITDEPTH
+
+    return;
+  }
+
 #if CONFIG_VP9_HIGHBITDEPTH
   if (xd->cur_buf->flags & YV12_FLAG_HIGHBITDEPTH) {
     build_intra_predictors_high(xd, ref, ref_stride, dst, dst_stride, mode,
diff --git a/vp10/decoder/decodeframe.c b/vp10/decoder/decodeframe.c
index ad02c953e..f19508c77 100644
--- a/vp10/decoder/decodeframe.c
+++ b/vp10/decoder/decodeframe.c
@@ -847,6 +847,9 @@ static void decode_block(VP10Decoder *const pbi, MACROBLOCKD *const xd,
       const int max_blocks_high = num_4x4_h + (xd->mb_to_bottom_edge >= 0 ?
           0 : xd->mb_to_bottom_edge >> (5 + pd->subsampling_y));
 
+      if (plane <= 1 && mbmi->palette_mode_info.palette_size[plane])
+          vp10_decode_palette_tokens(xd, plane, r);
+
       for (row = 0; row < max_blocks_high; row += step)
         for (col = 0; col < max_blocks_wide; col += step)
           predict_and_reconstruct_intra_block(xd, r, mbmi, plane,
@@ -1535,6 +1538,8 @@ static const uint8_t *decode_tiles(VP10Decoder *pbi,
                           &tile_data->bit_reader, pbi->decrypt_cb,
                           pbi->decrypt_state);
       vp10_init_macroblockd(cm, &tile_data->xd, tile_data->dqcoeff);
+      tile_data->xd.plane[0].color_index_map = tile_data->color_index_map[0];
+      tile_data->xd.plane[1].color_index_map = tile_data->color_index_map[1];
     }
   }
 
@@ -1757,6 +1762,8 @@ static const uint8_t *decode_tiles_mt(VP10Decoder *pbi,
                           &tile_data->bit_reader, pbi->decrypt_cb,
                           pbi->decrypt_state);
       vp10_init_macroblockd(cm, &tile_data->xd, tile_data->dqcoeff);
+      tile_data->xd.plane[0].color_index_map = tile_data->color_index_map[0];
+      tile_data->xd.plane[1].color_index_map = tile_data->color_index_map[1];
 
       worker->had_error = 0;
       if (i == num_workers - 1 || n == tile_cols - 1) {
@@ -1926,6 +1933,8 @@ static size_t read_uncompressed_header(VP10Decoder *pbi,
       memset(&cm->ref_frame_map, -1, sizeof(cm->ref_frame_map));
       pbi->need_resync = 0;
     }
+    if (cm->current_video_frame == 0)
+      cm->allow_screen_content_tools = vpx_rb_read_bit(rb);
   } else {
     cm->intra_only = cm->show_frame ? 0 : vpx_rb_read_bit(rb);
 
diff --git a/vp10/decoder/decodemv.c b/vp10/decoder/decodemv.c
index f157ada20..b334a3ec6 100644
--- a/vp10/decoder/decodemv.c
+++ b/vp10/decoder/decodemv.c
@@ -24,6 +24,19 @@
 
 #include "vpx_dsp/vpx_dsp_common.h"
 
+static INLINE int read_uniform(vpx_reader *r, int n) {
+  int l = get_unsigned_bits(n);
+  int m = (1 << l) - n;
+  int v = vpx_read_literal(r, l-1);
+
+  assert(l != 0);
+
+  if (v < m)
+    return v;
+  else
+    return (v << 1) - m + vpx_read_literal(r, 1);
+}
+
 static PREDICTION_MODE read_intra_mode(vpx_reader *r, const vpx_prob *p) {
   return (PREDICTION_MODE)vpx_read_tree(r, vp10_intra_mode_tree, p);
 }
@@ -196,6 +209,38 @@ static int read_skip(VP10_COMMON *cm, const MACROBLOCKD *xd,
   }
 }
 
+static void read_palette_mode_info(VP10_COMMON *const cm,
+                                   MACROBLOCKD *const xd,
+                                   vpx_reader *r) {
+  MODE_INFO *const mi = xd->mi[0];
+  MB_MODE_INFO *const mbmi = &mi->mbmi;
+  const MODE_INFO *above_mi = xd->above_mi;
+  const MODE_INFO *left_mi  = xd->left_mi;
+  const BLOCK_SIZE bsize = mbmi->sb_type;
+  int i, palette_ctx = 0;
+
+  if (above_mi)
+    palette_ctx += (above_mi->mbmi.palette_mode_info.palette_size[0] > 0);
+  if (left_mi)
+    palette_ctx += (left_mi->mbmi.palette_mode_info.palette_size[0] > 0);
+  if (vpx_read(r, vp10_default_palette_y_mode_prob[bsize - BLOCK_8X8]
+                                                   [palette_ctx])) {
+    int n;
+    PALETTE_MODE_INFO *pmi = &mbmi->palette_mode_info;
+
+    pmi->palette_size[0] =
+        vpx_read_tree(r, vp10_palette_size_tree,
+                      vp10_default_palette_y_size_prob[bsize - BLOCK_8X8]) + 2;
+    n = pmi->palette_size[0];
+
+    for (i = 0; i < n; ++i)
+      pmi->palette_colors[i] = vpx_read_literal(r, cm->bit_depth);
+
+    xd->plane[0].color_index_map[0] = read_uniform(r, n);
+    assert(xd->plane[0].color_index_map[0] < n);
+  }
+}
+
 static void read_intra_frame_mode_info(VP10_COMMON *const cm,
                                        MACROBLOCKD *const xd,
                                        int mi_row, int mi_col, vpx_reader *r) {
@@ -244,6 +289,12 @@ static void read_intra_frame_mode_info(VP10_COMMON *const cm,
   }
 
   mbmi->uv_mode = read_intra_mode(r, vp10_kf_uv_mode_prob[mbmi->mode]);
+
+  mbmi->palette_mode_info.palette_size[0] = 0;
+  mbmi->palette_mode_info.palette_size[1] = 0;
+  if (bsize >= BLOCK_8X8 && cm->allow_screen_content_tools &&
+      mbmi->mode == DC_PRED)
+    read_palette_mode_info(cm, xd, r);
 }
 
 static int read_mv_component(vpx_reader *r,
@@ -407,6 +458,9 @@ static void read_intra_block_mode_info(VP10_COMMON *const cm,
   }
 
   mbmi->uv_mode = read_intra_mode_uv(cm, xd, r, mbmi->mode);
+
+  mbmi->palette_mode_info.palette_size[0] = 0;
+  mbmi->palette_mode_info.palette_size[1] = 0;
 }
 
 static INLINE int is_mv_valid(const MV *mv) {
diff --git a/vp10/decoder/decoder.h b/vp10/decoder/decoder.h
index 67ab069ee..72a631020 100644
--- a/vp10/decoder/decoder.h
+++ b/vp10/decoder/decoder.h
@@ -34,6 +34,7 @@ typedef struct TileData {
   DECLARE_ALIGNED(16, MACROBLOCKD, xd);
   /* dqcoeff are shared by all the planes. So planes must be decoded serially */
   DECLARE_ALIGNED(16, tran_low_t, dqcoeff[32 * 32]);
+  DECLARE_ALIGNED(16, uint8_t, color_index_map[2][64 * 64]);
 } TileData;
 
 typedef struct TileWorkerData {
@@ -43,6 +44,7 @@ typedef struct TileWorkerData {
   DECLARE_ALIGNED(16, MACROBLOCKD, xd);
   /* dqcoeff are shared by all the planes. So planes must be decoded serially */
   DECLARE_ALIGNED(16, tran_low_t, dqcoeff[32 * 32]);
+  DECLARE_ALIGNED(16, uint8_t, color_index_map[2][64 * 64]);
   struct vpx_internal_error_info error_info;
 } TileWorkerData;
 
diff --git a/vp10/decoder/detokenize.c b/vp10/decoder/detokenize.c
index d39e3dc06..cda988831 100644
--- a/vp10/decoder/detokenize.c
+++ b/vp10/decoder/detokenize.c
@@ -257,6 +257,33 @@ void dec_set_contexts(const MACROBLOCKD *xd, struct macroblockd_plane *pd,
   }
 }
 
+void vp10_decode_palette_tokens(MACROBLOCKD *const xd, int plane,
+                                vpx_reader *r) {
+  MODE_INFO *const mi = xd->mi[0];
+  MB_MODE_INFO *const mbmi = &mi->mbmi;
+  const BLOCK_SIZE bsize = mbmi->sb_type;
+  int rows = 4 * num_4x4_blocks_high_lookup[bsize];
+  int cols = 4 * num_4x4_blocks_wide_lookup[bsize];
+  int color_idx, color_ctx, color_order[PALETTE_MAX_SIZE];
+  int n = mbmi->palette_mode_info.palette_size[plane != 0];
+  int i, j;
+  uint8_t *color_map = xd->plane[plane].color_index_map;
+  const vpx_prob (* prob)[PALETTE_COLOR_CONTEXTS][PALETTE_COLORS - 1] =
+      plane ? vp10_default_palette_uv_color_prob :
+          vp10_default_palette_y_color_prob;
+
+  for (i = 0; i < rows; ++i) {
+    for (j = (i == 0 ? 1 : 0); j < cols; ++j) {
+      color_ctx = vp10_get_palette_color_context(color_map, cols, i, j, n,
+                                                 color_order);
+      color_idx = vpx_read_tree(r, vp10_palette_color_tree[n - 2],
+                                prob[n - 2][color_ctx]);
+      assert(color_idx >= 0 && color_idx < n);
+      color_map[i * cols + j] = color_order[color_idx];
+    }
+  }
+}
+
 int vp10_decode_block_tokens(MACROBLOCKD *xd,
                             int plane, const scan_order *sc,
                             int x, int y,
diff --git a/vp10/decoder/detokenize.h b/vp10/decoder/detokenize.h
index c3fd90a72..d2677f612 100644
--- a/vp10/decoder/detokenize.h
+++ b/vp10/decoder/detokenize.h
@@ -20,6 +20,8 @@
 extern "C" {
 #endif
 
+void vp10_decode_palette_tokens(MACROBLOCKD *const xd, int plane,
+                                vpx_reader *r);
 int vp10_decode_block_tokens(MACROBLOCKD *xd,
                             int plane, const scan_order *sc,
                             int x, int y,
diff --git a/vp10/encoder/bitstream.c b/vp10/encoder/bitstream.c
index 1661fbd5d..0a3226d3f 100644
--- a/vp10/encoder/bitstream.c
+++ b/vp10/encoder/bitstream.c
@@ -44,6 +44,33 @@ static const struct vp10_token partition_encodings[PARTITION_TYPES] =
   {{0, 1}, {2, 2}, {6, 3}, {7, 3}};
 static const struct vp10_token inter_mode_encodings[INTER_MODES] =
   {{2, 2}, {6, 3}, {0, 1}, {7, 3}};
+static const struct vp10_token palette_size_encodings[] = {
+    {0, 1}, {2, 2}, {6, 3}, {14, 4}, {30, 5}, {62, 6}, {63, 6},
+};
+static const struct vp10_token
+palette_color_encodings[PALETTE_MAX_SIZE - 1][8] = {
+    {{0, 1}, {1, 1}},  // 2 colors
+    {{0, 1}, {2, 2}, {3, 2}},  // 3 colors
+    {{0, 1}, {2, 2}, {6, 3}, {7, 3}},  // 4 colors
+    {{0, 1}, {2, 2}, {6, 3}, {14, 4}, {15, 4}},  // 5 colors
+    {{0, 1}, {2, 2}, {6, 3}, {14, 4}, {30, 5}, {31, 5}},  // 6 colors
+    {{0, 1}, {2, 2}, {6, 3}, {14, 4}, {30, 5}, {62, 6}, {63, 6}},  // 7 colors
+    {{0, 1}, {2, 2}, {6, 3}, {14, 4},
+        {30, 5}, {62, 6}, {126, 7}, {127, 7}},  // 8 colors
+};
+
+static INLINE void write_uniform(vpx_writer *w, int n, int v) {
+  int l = get_unsigned_bits(n);
+  int m = (1 << l) - n;
+  if (l == 0)
+    return;
+  if (v < m) {
+    vpx_write_literal(w, v, l - 1);
+  } else {
+    vpx_write_literal(w, m + ((v - m) >> 1), l - 1);
+    vpx_write_literal(w, (v - m) & 1, 1);
+  }
+}
 
 static void write_intra_mode(vpx_writer *w, PREDICTION_MODE mode,
                              const vpx_prob *probs) {
@@ -120,6 +147,22 @@ static void update_switchable_interp_probs(VP10_COMMON *cm, vpx_writer *w,
                      counts->switchable_interp[j], SWITCHABLE_FILTERS, w);
 }
 
+static void pack_palette_tokens(vpx_writer *w, TOKENEXTRA **tp,
+                                BLOCK_SIZE bsize, int n) {
+  int rows = 4 * num_4x4_blocks_high_lookup[bsize];
+  int cols = 4 * num_4x4_blocks_wide_lookup[bsize];
+  int i;
+  TOKENEXTRA *p = *tp;
+
+  for (i = 0; i < rows * cols -1; ++i) {
+    vp10_write_token(w, vp10_palette_color_tree[n - 2], p->context_tree,
+                     &palette_color_encodings[n - 2][p->token]);
+    ++p;
+  }
+
+  *tp = p;
+}
+
 static void pack_mb_tokens(vpx_writer *w,
                            TOKENEXTRA **tp, const TOKENEXTRA *const stop,
                            vpx_bit_depth_t bit_depth, const TX_SIZE tx) {
@@ -353,6 +396,36 @@ static void pack_inter_mode_mvs(VP10_COMP *cpi, const MODE_INFO *mi,
   }
 }
 
+static void write_palette_mode_info(const VP10_COMMON *cm,
+                                    const MACROBLOCKD *xd,
+                                    const MODE_INFO *const mi,
+                                    vpx_writer *w) {
+  const MB_MODE_INFO *const mbmi = &mi->mbmi;
+  const MODE_INFO *const above_mi = xd->above_mi;
+  const MODE_INFO *const left_mi = xd->left_mi;
+  const BLOCK_SIZE bsize = mbmi->sb_type;
+  const PALETTE_MODE_INFO *pmi = &mbmi->palette_mode_info;
+  int palette_ctx = 0;
+  int n, i;
+
+  n = pmi->palette_size[0];
+  if (above_mi)
+    palette_ctx += (above_mi->mbmi.palette_mode_info.palette_size[0] > 0);
+  if (left_mi)
+    palette_ctx += (left_mi->mbmi.palette_mode_info.palette_size[0] > 0);
+  vpx_write(w, n > 0,
+            vp10_default_palette_y_mode_prob[bsize - BLOCK_8X8][palette_ctx]);
+  if (n > 0) {
+    vp10_write_token(w, vp10_palette_size_tree,
+                     vp10_default_palette_y_size_prob[bsize - BLOCK_8X8],
+                     &palette_size_encodings[n - 2]);
+    for (i = 0; i < n; ++i)
+      vpx_write_literal(w, pmi->palette_colors[i],
+                        cm->bit_depth);
+    write_uniform(w, n, pmi->palette_first_color_idx[0]);
+  }
+}
+
 static void write_mb_modes_kf(const VP10_COMMON *cm, const MACROBLOCKD *xd,
                               MODE_INFO **mi_8x8, vpx_writer *w) {
   const struct segmentation *const seg = &cm->seg;
@@ -387,6 +460,10 @@ static void write_mb_modes_kf(const VP10_COMMON *cm, const MACROBLOCKD *xd,
   }
 
   write_intra_mode(w, mbmi->uv_mode, vp10_kf_uv_mode_prob[mbmi->mode]);
+
+  if (bsize >= BLOCK_8X8 && cm->allow_screen_content_tools &&
+      mbmi->mode == DC_PRED)
+    write_palette_mode_info(cm, xd, mi, w);
 }
 
 static void write_modes_b(VP10_COMP *cpi, const TileInfo *const tile,
@@ -413,6 +490,13 @@ static void write_modes_b(VP10_COMP *cpi, const TileInfo *const tile,
     pack_inter_mode_mvs(cpi, m, w);
   }
 
+  if (m->mbmi.palette_mode_info.palette_size[0] > 0) {
+    assert(*tok < tok_end);
+    pack_palette_tokens(w, tok, m->mbmi.sb_type,
+                        m->mbmi.palette_mode_info.palette_size[0]);
+    assert(*tok < tok_end);
+  }
+
   if (!m->mbmi.skip) {
     assert(*tok < tok_end);
     for (plane = 0; plane < MAX_MB_PLANE; ++plane) {
@@ -1133,6 +1217,8 @@ static void write_uncompressed_header(VP10_COMP *cpi,
     write_sync_code(wb);
     write_bitdepth_colorspace_sampling(cm, wb);
     write_frame_size(cm, wb);
+    if (cm->current_video_frame == 0)
+      vpx_wb_write_bit(wb, cm->allow_screen_content_tools);
   } else {
     if (!cm->show_frame)
       vpx_wb_write_bit(wb, cm->intra_only);
diff --git a/vp10/encoder/block.h b/vp10/encoder/block.h
index cb2a234c9..df3830cb5 100644
--- a/vp10/encoder/block.h
+++ b/vp10/encoder/block.h
@@ -52,6 +52,13 @@ typedef struct {
   uint8_t mode_context[MAX_REF_FRAMES];
 } MB_MODE_INFO_EXT;
 
+typedef struct {
+  uint8_t best_palette_color_map[4096];
+  double kmeans_data_buf[4096];
+  uint8_t kmeans_indices_buf[4096];
+  uint8_t kmeans_pre_indices_buf[4096];
+} PALETTE_BUFFER;
+
 typedef struct macroblock MACROBLOCK;
 struct macroblock {
   struct macroblock_plane plane[MAX_MB_PLANE];
@@ -92,6 +99,8 @@ struct macroblock {
   int *nmvsadcost_hp[2];
   int **mvsadcost;
 
+  PALETTE_BUFFER *palette_buffer;
+
   // These define limits to motion vector components to prevent them
   // from extending outside the UMV borders
   int mv_col_min;
diff --git a/vp10/encoder/context_tree.c b/vp10/encoder/context_tree.c
index d210e3610..532e82caa 100644
--- a/vp10/encoder/context_tree.c
+++ b/vp10/encoder/context_tree.c
@@ -61,6 +61,11 @@ static void free_mode_context(PICK_MODE_CONTEXT *ctx) {
       ctx->eobs[i][k] = 0;
     }
   }
+
+  for (i = 0; i < 2; ++i) {
+    vpx_free(ctx->color_index_map[i]);
+    ctx->color_index_map[i] = 0;
+  }
 }
 
 static void alloc_tree_contexts(VP10_COMMON *cm, PC_TREE *tree,
diff --git a/vp10/encoder/context_tree.h b/vp10/encoder/context_tree.h
index 67a07cb50..2a0fffbfb 100644
--- a/vp10/encoder/context_tree.h
+++ b/vp10/encoder/context_tree.h
@@ -27,6 +27,7 @@ typedef struct {
   MODE_INFO mic;
   MB_MODE_INFO_EXT mbmi_ext;
   uint8_t *zcoeff_blk;
+  uint8_t *color_index_map[2];
   tran_low_t *coeff[MAX_MB_PLANE][3];
   tran_low_t *qcoeff[MAX_MB_PLANE][3];
   tran_low_t *dqcoeff[MAX_MB_PLANE][3];
diff --git a/vp10/encoder/encodeframe.c b/vp10/encoder/encodeframe.c
index ce1530c63..1876e88a7 100644
--- a/vp10/encoder/encodeframe.c
+++ b/vp10/encoder/encodeframe.c
@@ -1005,6 +1005,9 @@ static void update_state(VP10_COMP *cpi, ThreadData *td,
     p[i].eobs = ctx->eobs_pbuf[i][2];
   }
 
+  for (i = 0; i < 2; ++i)
+    pd[i].color_index_map = ctx->color_index_map[i];
+
   // Restore the coding context of the MB to that that was in place
   // when the mode was picked for it
   for (y = 0; y < mi_height; y++)
@@ -1136,6 +1139,19 @@ static void rd_pick_sb_modes(VP10_COMP *cpi,
     pd[i].dqcoeff = ctx->dqcoeff_pbuf[i][0];
     p[i].eobs = ctx->eobs_pbuf[i][0];
   }
+
+  if (cm->current_video_frame == 0 && cm->allow_screen_content_tools) {
+    for (i = 0; i < 2; ++i) {
+      if (ctx->color_index_map[i] == 0) {
+        CHECK_MEM_ERROR(cm, ctx->color_index_map[i],
+                        vpx_memalign(16, (ctx->num_4x4_blk << 4) *
+                                     sizeof(*ctx->color_index_map[i])));
+      }
+    }
+  }
+  for (i = 0; i < 2; ++i)
+    pd[i].color_index_map = ctx->color_index_map[i];
+
   ctx->is_coded = 0;
   ctx->skippable = 0;
   ctx->pred_pixel_ready = 0;
@@ -2938,6 +2954,16 @@ static void encode_superblock(VP10_COMP *cpi, ThreadData *td,
       vp10_encode_intra_block_plane(x, VPXMAX(bsize, BLOCK_8X8), plane);
     if (output_enabled)
       sum_intra_stats(td->counts, mi);
+
+    if (bsize >= BLOCK_8X8 && output_enabled) {
+      if (mbmi->palette_mode_info.palette_size[0] > 0) {
+        mbmi->palette_mode_info.palette_first_color_idx[0] =
+            xd->plane[0].color_index_map[0];
+        // TODO(huisu): this increases the use of token buffer. Needs stretch
+        // test to verify.
+        vp10_tokenize_palette_sb(td, bsize, 0, t);
+      }
+    }
     vp10_tokenize_sb(cpi, td, t, !output_enabled, VPXMAX(bsize, BLOCK_8X8));
   } else {
     int ref;
diff --git a/vp10/encoder/encoder.c b/vp10/encoder/encoder.c
index a38e1829e..cbc3a2b61 100644
--- a/vp10/encoder/encoder.c
+++ b/vp10/encoder/encoder.c
@@ -390,6 +390,9 @@ static void dealloc_compressor_data(VP10_COMP *cpi) {
 
   vp10_free_pc_tree(&cpi->td);
 
+  if (cpi->common.allow_screen_content_tools)
+    vpx_free(cpi->td.mb.palette_buffer);
+
   if (cpi->source_diff_var != NULL) {
     vpx_free(cpi->source_diff_var);
     cpi->source_diff_var = NULL;
@@ -1428,6 +1431,15 @@ void vp10_change_config(struct VP10_COMP *cpi, const VP10EncoderConfig *oxcf) {
                                              : REFRESH_FRAME_CONTEXT_BACKWARD;
   cm->reset_frame_context = RESET_FRAME_CONTEXT_NONE;
 
+  cm->allow_screen_content_tools = (cpi->oxcf.content == VP9E_CONTENT_SCREEN);
+  if (cm->allow_screen_content_tools) {
+    MACROBLOCK *x = &cpi->td.mb;
+    if (x->palette_buffer == 0) {
+      CHECK_MEM_ERROR(cm, x->palette_buffer,
+                      vpx_memalign(16, sizeof(*x->palette_buffer)));
+    }
+  }
+
   vp10_reset_segment_features(&cm->seg);
   vp10_set_high_precision_mv(cpi, 0);
 
@@ -1936,6 +1948,8 @@ void vp10_remove_compressor(VP10_COMP *cpi) {
       vpx_free(thread_data->td->counts);
       vp10_free_pc_tree(thread_data->td);
       vpx_free(thread_data->td);
+      if (cpi->common.allow_screen_content_tools)
+        vpx_free(thread_data->td->mb.palette_buffer);
     }
   }
   vpx_free(cpi->tile_thr_data);
diff --git a/vp10/encoder/encoder.h b/vp10/encoder/encoder.h
index 6f3f7113c..8f122305a 100644
--- a/vp10/encoder/encoder.h
+++ b/vp10/encoder/encoder.h
@@ -458,6 +458,12 @@ typedef struct VP10_COMP {
   int y_mode_costs[INTRA_MODES][INTRA_MODES][INTRA_MODES];
   int switchable_interp_costs[SWITCHABLE_FILTER_CONTEXTS][SWITCHABLE_FILTERS];
   int partition_cost[PARTITION_CONTEXTS][PARTITION_TYPES];
+  int palette_y_size_cost[10][PALETTE_SIZES];
+  int palette_uv_size_cost[10][PALETTE_SIZES];
+  int palette_y_color_cost[PALETTE_MAX_SIZE - 1][PALETTE_COLOR_CONTEXTS]
+                                                 [PALETTE_COLORS];
+  int palette_uv_color_cost[PALETTE_MAX_SIZE - 1][PALETTE_COLOR_CONTEXTS]
+                                                  [PALETTE_COLORS];
 
   int multi_arf_allowed;
   int multi_arf_enabled;
diff --git a/vp10/encoder/ethread.c b/vp10/encoder/ethread.c
index ea491058a..0a6df3983 100644
--- a/vp10/encoder/ethread.c
+++ b/vp10/encoder/ethread.c
@@ -96,6 +96,13 @@ void vp10_encode_tiles_mt(VP10_COMP *cpi) {
         CHECK_MEM_ERROR(cm, thread_data->td->counts,
                         vpx_calloc(1, sizeof(*thread_data->td->counts)));
 
+        // Allocate buffers used by palette coding mode.
+        if (cpi->common.allow_screen_content_tools) {
+          MACROBLOCK *x = &thread_data->td->mb;
+          CHECK_MEM_ERROR(cm, x->palette_buffer,
+                          vpx_memalign(16, sizeof(*x->palette_buffer)));
+        }
+
         // Create threads
         if (!winterface->reset(worker))
           vpx_internal_error(&cm->error, VPX_CODEC_ERROR,
diff --git a/vp10/encoder/palette.c b/vp10/encoder/palette.c
new file mode 100644
index 000000000..04e911884
--- /dev/null
+++ b/vp10/encoder/palette.c
@@ -0,0 +1,186 @@
+/*
+ *  Copyright (c) 2015 The WebM project authors. All Rights Reserved.
+ *
+ *  Use of this source code is governed by a BSD-style license
+ *  that can be found in the LICENSE file in the root of the source
+ *  tree. An additional intellectual property rights grant can be found
+ *  in the file PATENTS.  All contributing project authors may
+ *  be found in the AUTHORS file in the root of the source tree.
+ */
+
+#include "vp10/encoder/palette.h"
+
+static double calc_dist(const double *p1, const double *p2, int dim) {
+  double dist = 0;
+  int i = 0;
+
+  for (i = 0; i < dim; i++) {
+    dist = dist + (p1[i] - p2[i]) * (p1[i] - p2[i]);
+  }
+  return dist;
+}
+
+void vp10_calc_indices(const double *data, const double *centroids,
+                       uint8_t *indices, int n, int k, int dim) {
+  int i, j;
+  double min_dist, this_dist;
+
+  for (i = 0; i < n; i++) {
+    min_dist = calc_dist(data + i * dim, centroids, dim);
+    indices[i] = 0;
+    for (j = 1; j < k; j++) {
+      this_dist = calc_dist(data + i * dim, centroids + j * dim, dim);
+      if (this_dist < min_dist) {
+        min_dist = this_dist;
+        indices[i] = j;
+      }
+    }
+  }
+}
+
+static void calc_centroids(const double *data, double *centroids,
+                           const uint8_t *indices, int n, int k, int dim) {
+  int i, j, index;
+  int count[PALETTE_MAX_SIZE];
+
+  srand((unsigned int) data[0]);
+  memset(count, 0, sizeof(count[0]) * k);
+  memset(centroids, 0, sizeof(centroids[0]) * k * dim);
+
+  for (i = 0; i < n; i++) {
+    index = indices[i];
+    assert(index < k);
+    count[index]++;
+    for (j = 0; j < dim; j++) {
+      centroids[index * dim + j] += data[i * dim + j];
+    }
+  }
+
+  for (i = 0; i < k; i++) {
+    if (count[i] == 0) {
+      // TODO(huisu): replace rand() with something else.
+      memcpy(centroids + i * dim, data + (rand() % n) * dim,
+                 sizeof(centroids[0]) * dim);
+    } else {
+      const double norm = 1.0 / count[i];
+      for (j = 0; j < dim; j++)
+        centroids[i * dim + j] *= norm;
+    }
+  }
+}
+
+static double calc_total_dist(const double *data, const double *centroids,
+                              const uint8_t *indices, int n, int k, int dim) {
+  double dist = 0;
+  int i;
+  (void) k;
+
+  for (i = 0; i < n; i++)
+    dist += calc_dist(data + i * dim, centroids + indices[i] * dim, dim);
+
+  return dist;
+}
+
+int vp10_k_means(const double *data, double *centroids, uint8_t *indices,
+                 uint8_t *pre_indices, int n, int k, int dim, int max_itr) {
+  int i = 0;
+  double pre_dist, this_dist;
+  double pre_centroids[PALETTE_MAX_SIZE];
+
+  vp10_calc_indices(data, centroids, indices, n, k, dim);
+  pre_dist = calc_total_dist(data, centroids, indices, n, k, dim);
+  memcpy(pre_centroids, centroids, sizeof(pre_centroids[0]) * k * dim);
+  memcpy(pre_indices, indices, sizeof(pre_indices[0]) * n);
+  while (i < max_itr) {
+    calc_centroids(data, centroids, indices, n, k, dim);
+    vp10_calc_indices(data, centroids, indices, n, k, dim);
+    this_dist = calc_total_dist(data, centroids, indices, n, k, dim);
+
+    if (this_dist > pre_dist) {
+      memcpy(centroids, pre_centroids, sizeof(pre_centroids[0]) * k * dim);
+      memcpy(indices, pre_indices, sizeof(pre_indices[0]) * n);
+      break;
+    }
+    if (!memcmp(centroids, pre_centroids, sizeof(pre_centroids[0]) * k * dim))
+      break;
+
+    memcpy(pre_centroids, centroids, sizeof(pre_centroids[0]) * k * dim);
+    memcpy(pre_indices, indices, sizeof(pre_indices[0]) * n);
+    pre_dist = this_dist;
+    i++;
+  }
+
+  return i;
+}
+
+void vp10_insertion_sort(double *data, int n) {
+  int i, j, k;
+  double val;
+
+  if (n <= 1)
+    return;
+
+  for (i = 1; i < n; ++i) {
+    val = data[i];
+    j = 0;
+    while (val > data[j] && j < i)
+      ++j;
+
+    if (j == i)
+      continue;
+
+    for (k = i; k > j; --k)
+      data[k] = data[k - 1];
+    data[j] = val;
+  }
+}
+
+int vp10_count_colors(const uint8_t *src, int stride, int rows, int cols) {
+  int n = 0, r, c, i, val_count[256];
+  uint8_t val;
+  memset(val_count, 0, sizeof(val_count));
+
+  for (r = 0; r < rows; ++r) {
+    for (c = 0; c < cols; ++c) {
+      val = src[r * stride + c];
+      ++val_count[val];
+    }
+  }
+
+  for (i = 0; i < 256; ++i) {
+    if (val_count[i]) {
+      ++n;
+    }
+  }
+
+  return n;
+}
+
+#if CONFIG_VP9_HIGHBITDEPTH
+int vp10_count_colors_highbd(const uint8_t *src8, int stride, int rows,
+                             int cols, int bit_depth) {
+  int n = 0, r, c, i;
+  uint16_t val;
+  uint16_t *src = CONVERT_TO_SHORTPTR(src8);
+  int val_count[1 << 12];
+
+  assert(bit_depth <= 12);
+  memset(val_count, 0, (1 << 12) * sizeof(val_count[0]));
+  for (r = 0; r < rows; ++r) {
+    for (c = 0; c < cols; ++c) {
+      val = src[r * stride + c];
+      val_count[val]++;
+    }
+  }
+
+  for (i = 0; i < (1 << bit_depth); ++i) {
+    if (val_count[i]) {
+      ++n;
+    }
+  }
+
+  return n;
+}
+#endif  // CONFIG_VP9_HIGHBITDEPTH
+
+
diff --git a/vp10/encoder/palette.h b/vp10/encoder/palette.h
new file mode 100644
index 000000000..124cf7447
--- /dev/null
+++ b/vp10/encoder/palette.h
@@ -0,0 +1,35 @@
+/*
+ *  Copyright (c) 2015 The WebM project authors. All Rights Reserved.
+ *
+ *  Use of this source code is governed by a BSD-style license
+ *  that can be found in the LICENSE file in the root of the source
+ *  tree. An additional intellectual property rights grant can be found
+ *  in the file PATENTS.  All contributing project authors may
+ *  be found in the AUTHORS file in the root of the source tree.
+ */
+
+#ifndef VP10_ENCODER_PALETTE_H_
+#define VP10_ENCODER_PALETTE_H_
+
+#include "vp10/common/blockd.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+void vp10_insertion_sort(double *data, int n);
+void vp10_calc_indices(const double *data, const double *centroids,
+                       uint8_t *indices, int n, int k, int dim);
+int vp10_k_means(const double *data, double *centroids, uint8_t *indices,
+                 uint8_t *pre_indices, int n, int k, int dim, int max_itr);
+int vp10_count_colors(const uint8_t *src, int stride, int rows, int cols);
+#if CONFIG_VP9_HIGHBITDEPTH
+int vp10_count_colors_highbd(const uint8_t *src8, int stride, int rows,
+                             int cols, int bit_depth);
+#endif  // CONFIG_VP9_HIGHBITDEPTH
+
+#ifdef __cplusplus
+}  // extern "C"
+#endif
+
+#endif /* VP10_ENCODER_PALETTE_H_ */
diff --git a/vp10/encoder/rd.c b/vp10/encoder/rd.c
index bc5e1ae4f..806b8542b 100644
--- a/vp10/encoder/rd.c
+++ b/vp10/encoder/rd.c
@@ -84,6 +84,25 @@ static void fill_mode_costs(VP10_COMP *cpi) {
   for (i = 0; i < SWITCHABLE_FILTER_CONTEXTS; ++i)
     vp10_cost_tokens(cpi->switchable_interp_costs[i],
                     fc->switchable_interp_prob[i], vp10_switchable_interp_tree);
+
+  for (i = 0; i < 10; ++i) {
+    vp10_cost_tokens(cpi->palette_y_size_cost[i],
+                     vp10_default_palette_y_size_prob[i],
+                     vp10_palette_size_tree);
+    vp10_cost_tokens(cpi->palette_uv_size_cost[i],
+                     vp10_default_palette_uv_size_prob[i],
+                     vp10_palette_size_tree);
+  }
+
+  for (i = 0; i < PALETTE_MAX_SIZE - 1; ++i)
+    for (j = 0; j < PALETTE_COLOR_CONTEXTS; ++j) {
+      vp10_cost_tokens(cpi->palette_y_color_cost[i][j],
+                       vp10_default_palette_y_color_prob[i][j],
+                       vp10_palette_color_tree[i]);
+      vp10_cost_tokens(cpi->palette_uv_color_cost[i][j],
+                       vp10_default_palette_uv_color_prob[i][j],
+                       vp10_palette_color_tree[i]);
+    }
 }
 
 static void fill_token_costs(vp10_coeff_cost *c,
diff --git a/vp10/encoder/rdopt.c b/vp10/encoder/rdopt.c
index e3bbdd346..4c582b142 100644
--- a/vp10/encoder/rdopt.c
+++ b/vp10/encoder/rdopt.c
@@ -36,6 +36,7 @@
 #include "vp10/encoder/encodemv.h"
 #include "vp10/encoder/encoder.h"
 #include "vp10/encoder/mcomp.h"
+#include "vp10/encoder/palette.h"
 #include "vp10/encoder/quantize.h"
 #include "vp10/encoder/ratectrl.h"
 #include "vp10/encoder/rd.h"
@@ -130,6 +131,16 @@ static const REF_DEFINITION vp10_ref_order[MAX_REFS] = {
   {{INTRA_FRAME,  NONE}},
 };
 
+static INLINE int write_uniform_cost(int n, int v) {
+  int l = get_unsigned_bits(n), m = (1 << l) - n;
+  if (l == 0)
+    return 0;
+  if (v < m)
+    return (l - 1) * vp10_cost_bit(128, 0);
+  else
+    return l * vp10_cost_bit(128, 0);
+}
+
 static void swap_block_ptr(MACROBLOCK *x, PICK_MODE_CONTEXT *ctx,
                            int m, int n, int min_plane, int max_plane) {
   int i;
@@ -728,6 +739,162 @@ static int conditional_skipintra(PREDICTION_MODE mode,
   return 0;
 }
 
+void rd_pick_palette_intra_sby(VP10_COMP *cpi, MACROBLOCK *x, BLOCK_SIZE bsize,
+                               int palette_ctx, int dc_mode_cost,
+                               PALETTE_MODE_INFO *palette_mode_info,
+                               uint8_t *best_palette_color_map,
+                               TX_SIZE *best_tx, PREDICTION_MODE *mode_selected,
+                               int64_t *best_rd) {
+  MACROBLOCKD *const xd = &x->e_mbd;
+  MODE_INFO *const mic = xd->mi[0];
+  int rows = 4 * num_4x4_blocks_high_lookup[bsize];
+  int cols = 4 * num_4x4_blocks_wide_lookup[bsize];
+  int this_rate, this_rate_tokenonly, s;
+  int64_t this_distortion, this_rd;
+  int colors, n;
+  int src_stride = x->plane[0].src.stride;
+  uint8_t *src = x->plane[0].src.buf;
+
+#if CONFIG_VP9_HIGHBITDEPTH
+  if (cpi->common.use_highbitdepth)
+    colors = vp10_count_colors_highbd(src, src_stride, rows, cols,
+                                      cpi->common.bit_depth);
+  else
+#endif  // CONFIG_VP9_HIGHBITDEPTH
+    colors = vp10_count_colors(src, src_stride, rows, cols);
+  palette_mode_info->palette_size[0] = 0;
+
+  if (colors > 1 && colors <= 64 && cpi->common.allow_screen_content_tools) {
+    int r, c, i, j, k;
+    int max_itr = 50;
+    int color_ctx, color_idx = 0;
+    int color_order[PALETTE_MAX_SIZE];
+    double *data = x->palette_buffer->kmeans_data_buf;
+    uint8_t *indices = x->palette_buffer->kmeans_indices_buf;
+    uint8_t *pre_indices = x->palette_buffer->kmeans_pre_indices_buf;
+    double centroids[PALETTE_MAX_SIZE];
+    uint8_t *color_map;
+    double lb, ub, val;
+    PALETTE_MODE_INFO *pmi = &mic->mbmi.palette_mode_info;
+#if CONFIG_VP9_HIGHBITDEPTH
+    uint16_t *src16 = CONVERT_TO_SHORTPTR(src);
+    if (cpi->common.use_highbitdepth)
+      lb = ub = src16[0];
+    else
+#endif  // CONFIG_VP9_HIGHBITDEPTH
+      lb = ub = src[0];
+
+#if CONFIG_VP9_HIGHBITDEPTH
+    if (cpi->common.use_highbitdepth) {
+      for (r = 0; r < rows; ++r) {
+        for (c = 0; c < cols; ++c) {
+          val = src16[r * src_stride + c];
+          data[r * cols + c] = val;
+          if (val < lb)
+            lb = val;
+          else if (val > ub)
+            ub = val;
+        }
+      }
+    } else {
+#endif  // CONFIG_VP9_HIGHBITDEPTH
+      for (r = 0; r < rows; ++r) {
+        for (c = 0; c < cols; ++c) {
+          val = src[r * src_stride + c];
+          data[r * cols + c] = val;
+          if (val < lb)
+            lb = val;
+          else if (val > ub)
+            ub = val;
+        }
+      }
+#if CONFIG_VP9_HIGHBITDEPTH
+    }
+#endif  // CONFIG_VP9_HIGHBITDEPTH
+
+    mic->mbmi.mode = DC_PRED;
+
+    for (n = colors > PALETTE_MAX_SIZE ? PALETTE_MAX_SIZE : colors;
+        n >= 2; --n) {
+      for (i = 0; i < n; ++i)
+        centroids[i] = lb + (2 * i + 1) * (ub - lb) / n / 2;
+      vp10_k_means(data, centroids, indices, pre_indices, rows * cols,
+                   n, 1, max_itr);
+      vp10_insertion_sort(centroids, n);
+
+      // remove duplicates
+      i = 1;
+      k = n;
+      while (i < k) {
+        if (centroids[i] == centroids[i - 1]) {
+          j = i;
+          while (j < k - 1) {
+            centroids[j] = centroids[j + 1];
+            ++j;
+          }
+          --k;
+        } else {
+          ++i;
+        }
+      }
+
+#if CONFIG_VP9_HIGHBITDEPTH
+      if (cpi->common.use_highbitdepth)
+        for (i = 0; i < k; ++i)
+          mic->mbmi.palette_mode_info.palette_colors[i] =
+              clip_pixel_highbd(round(centroids[i]), cpi->common.bit_depth);
+      else
+#endif  // CONFIG_VP9_HIGHBITDEPTH
+        for (i = 0; i < k; ++i)
+          pmi->palette_colors[i] = clip_pixel(round(centroids[i]));
+      pmi->palette_size[0] = k;
+
+      vp10_calc_indices(data, centroids, indices, 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] = indices[r * cols + c];
+
+      super_block_yrd(cpi, x, &this_rate_tokenonly, &this_distortion,
+                      &s, NULL, bsize, *best_rd);
+      if (this_rate_tokenonly == INT_MAX)
+        continue;
+
+      this_rate = this_rate_tokenonly + dc_mode_cost +
+          cpi->common.bit_depth * k * vp10_cost_bit(128, 0) +
+          cpi->palette_y_size_cost[bsize - BLOCK_8X8][k - 2];
+      this_rate +=
+          vp10_cost_bit(vp10_default_palette_y_mode_prob[bsize - BLOCK_8X8]
+                                                         [palette_ctx], 1);
+      color_map = xd->plane[0].color_index_map;
+      this_rate +=  write_uniform_cost(k, xd->plane[0].color_index_map[0]);
+      for (i = 0; i < rows; ++i) {
+        for (j = (i == 0 ? 1 : 0); j < cols; ++j) {
+          color_ctx = vp10_get_palette_color_context(color_map, cols, i, j,
+                                                     k, color_order);
+          for (r = 0; r < k; ++r)
+            if (color_map[i * cols + j] == color_order[r]) {
+              color_idx = r;
+              break;
+            }
+          assert(color_idx < k);
+          this_rate +=
+              cpi->palette_y_color_cost[k - 2][color_ctx][color_idx];
+        }
+      }
+      this_rd = RDCOST(x->rdmult, x->rddiv, this_rate, this_distortion);
+
+      if (this_rd < *best_rd) {
+        *best_rd = this_rd;
+        *palette_mode_info = mic->mbmi.palette_mode_info;
+        memcpy(best_palette_color_map, xd->plane[0].color_index_map,
+               rows * cols * sizeof(xd->plane[0].color_index_map[0]));
+        *mode_selected = DC_PRED;
+        *best_tx = mic->mbmi.tx_size;
+      }
+    }
+  }
+}
+
 static int64_t rd_pick_intra4x4block(VP10_COMP *cpi, MACROBLOCK *x,
                                      int row, int col,
                                      PREDICTION_MODE *best_mode,
@@ -758,6 +925,7 @@ static int64_t rd_pick_intra4x4block(VP10_COMP *cpi, MACROBLOCK *x,
   memcpy(ta, a, sizeof(ta));
   memcpy(tl, l, sizeof(tl));
   xd->mi[0]->mbmi.tx_size = TX_4X4;
+  xd->mi[0]->mbmi.palette_mode_info.palette_size[0] = 0;
 
 #if CONFIG_VP9_HIGHBITDEPTH
   if (xd->cur_buf->flags & YV12_FLAG_HIGHBITDEPTH) {
@@ -1035,6 +1203,11 @@ static int64_t rd_pick_intra_sby_mode(VP10_COMP *cpi, MACROBLOCK *x,
   int64_t this_distortion, this_rd;
   TX_SIZE best_tx = TX_4X4;
   int *bmode_costs;
+  PALETTE_MODE_INFO palette_mode_info;
+  uint8_t *best_palette_color_map = x->palette_buffer->best_palette_color_map;
+  int rows = 4 * num_4x4_blocks_high_lookup[bsize];
+  int cols = 4 * num_4x4_blocks_wide_lookup[bsize];
+  int palette_ctx = 0;
   const MODE_INFO *above_mi = xd->above_mi;
   const MODE_INFO *left_mi = xd->left_mi;
   const PREDICTION_MODE A = vp10_above_block_mode(mic, above_mi, 0);
@@ -1042,6 +1215,13 @@ static int64_t rd_pick_intra_sby_mode(VP10_COMP *cpi, MACROBLOCK *x,
   bmode_costs = cpi->y_mode_costs[A][L];
 
   memset(x->skip_txfm, SKIP_TXFM_NONE, sizeof(x->skip_txfm));
+  palette_mode_info.palette_size[0] = 0;
+  mic->mbmi.palette_mode_info.palette_size[0] = 0;
+  if (above_mi)
+    palette_ctx += (above_mi->mbmi.palette_mode_info.palette_size[0] > 0);
+  if (left_mi)
+    palette_ctx += (left_mi->mbmi.palette_mode_info.palette_size[0] > 0);
+
   /* Y Search for intra prediction mode */
   for (mode = DC_PRED; mode <= TM_PRED; mode++) {
     mic->mbmi.mode = mode;
@@ -1053,6 +1233,10 @@ static int64_t rd_pick_intra_sby_mode(VP10_COMP *cpi, MACROBLOCK *x,
       continue;
 
     this_rate = this_rate_tokenonly + bmode_costs[mode];
+    if (cpi->common.allow_screen_content_tools && mode == DC_PRED)
+      this_rate +=
+          vp10_cost_bit(vp10_default_palette_y_mode_prob[bsize - BLOCK_8X8]
+                                                         [palette_ctx], 0);
     this_rd = RDCOST(x->rdmult, x->rddiv, this_rate, this_distortion);
 
     if (this_rd < best_rd) {
@@ -1066,8 +1250,22 @@ static int64_t rd_pick_intra_sby_mode(VP10_COMP *cpi, MACROBLOCK *x,
     }
   }
 
+  if (cpi->common.allow_screen_content_tools)
+    rd_pick_palette_intra_sby(cpi, x, bsize, palette_ctx, bmode_costs[DC_PRED],
+                              &palette_mode_info, best_palette_color_map,
+                              &best_tx, &mode_selected, &best_rd);
+
   mic->mbmi.mode = mode_selected;
   mic->mbmi.tx_size = best_tx;
+  mic->mbmi.palette_mode_info.palette_size[0] =
+      palette_mode_info.palette_size[0];
+  if (palette_mode_info.palette_size[0] > 0) {
+    memcpy(mic->mbmi.palette_mode_info.palette_colors,
+           palette_mode_info.palette_colors,
+           PALETTE_MAX_SIZE * sizeof(palette_mode_info.palette_colors[0]));
+    memcpy(xd->plane[0].color_index_map, best_palette_color_map,
+           rows * cols * sizeof(best_palette_color_map[0]));
+  }
 
   return best_rd;
 }
@@ -1138,6 +1336,7 @@ static int64_t rd_pick_intra_sbuv_mode(VP10_COMP *cpi, MACROBLOCK *x,
   int64_t this_distortion, this_sse;
 
   memset(x->skip_txfm, SKIP_TXFM_NONE, sizeof(x->skip_txfm));
+  xd->mi[0]->mbmi.palette_mode_info.palette_size[1] = 0;
   for (mode = DC_PRED; mode <= TM_PRED; ++mode) {
     if (!(cpi->sf.intra_uv_mode_mask[max_tx_size] & (1 << mode)))
       continue;
@@ -3057,6 +3256,8 @@ void vp10_rd_pick_inter_mode_sb(VP10_COMP *cpi,
     midx = end_pos;
   }
 
+  mbmi->palette_mode_info.palette_size[0] = 0;
+  mbmi->palette_mode_info.palette_size[1] = 0;
   for (midx = 0; midx < MAX_MODES; ++midx) {
     int mode_index = mode_map[midx];
     int mode_excluded = 0;
@@ -3536,6 +3737,8 @@ void vp10_rd_pick_inter_mode_sb_seg_skip(VP10_COMP *cpi,
 
   assert(segfeature_active(&cm->seg, segment_id, SEG_LVL_SKIP));
 
+  mbmi->palette_mode_info.palette_size[0] = 0;
+  mbmi->palette_mode_info.palette_size[1] = 0;
   mbmi->mode = ZEROMV;
   mbmi->uv_mode = DC_PRED;
   mbmi->ref_frame[0] = LAST_FRAME;
@@ -3683,6 +3886,9 @@ void vp10_rd_pick_inter_mode_sub8x8(VP10_COMP *cpi,
     frame_mv[ZEROMV][ref_frame].as_int = 0;
   }
 
+  mbmi->palette_mode_info.palette_size[0] = 0;
+  mbmi->palette_mode_info.palette_size[1] = 0;
+
   for (ref_index = 0; ref_index < MAX_REFS; ++ref_index) {
     int mode_excluded = 0;
     int64_t this_rd = INT64_MAX;
diff --git a/vp10/encoder/tokenize.c b/vp10/encoder/tokenize.c
index cbebd5aa8..2c9998ba0 100644
--- a/vp10/encoder/tokenize.c
+++ b/vp10/encoder/tokenize.c
@@ -487,6 +487,39 @@ static INLINE int get_tx_eob(const struct segmentation *seg, int segment_id,
   return segfeature_active(seg, segment_id, SEG_LVL_SKIP) ? 0 : eob_max;
 }
 
+void vp10_tokenize_palette_sb(struct ThreadData *const td,
+                              BLOCK_SIZE bsize, int plane,
+                              TOKENEXTRA **t) {
+  MACROBLOCK *const x = &td->mb;
+  MACROBLOCKD *const xd = &x->e_mbd;
+  MB_MODE_INFO *mbmi = &xd->mi[0]->mbmi;
+  uint8_t *color_map = xd->plane[0].color_index_map;
+  PALETTE_MODE_INFO *pmi = &mbmi->palette_mode_info;
+  int n = pmi->palette_size[plane != 0];
+  int i, j, k;
+  int color_new_idx = -1, color_ctx, color_order[PALETTE_MAX_SIZE];
+  int rows = 4 * num_4x4_blocks_high_lookup[bsize];
+  int cols = 4 * num_4x4_blocks_wide_lookup[bsize];
+
+  for (i = 0; i < rows; ++i) {
+    for (j = (i == 0 ? 1 : 0); j < cols; ++j) {
+      color_ctx = vp10_get_palette_color_context(color_map, cols, i, j, n,
+                                                 color_order);
+      for (k = 0; k < n; ++k)
+        if (color_map[i * cols + j] == color_order[k]) {
+          color_new_idx = k;
+          break;
+        }
+      assert(color_new_idx >= 0 && color_new_idx < n);
+
+      (*t)->token = color_new_idx;
+      (*t)->context_tree = vp10_default_palette_y_color_prob[n - 2][color_ctx];
+      (*t)->skip_eob_node = 0;
+      ++(*t);
+    }
+  }
+}
+
 static void tokenize_b(int plane, int block, BLOCK_SIZE plane_bsize,
                        TX_SIZE tx_size, void *arg) {
   struct tokenize_b_args* const args = arg;
diff --git a/vp10/encoder/tokenize.h b/vp10/encoder/tokenize.h
index 5bad415a9..1614add98 100644
--- a/vp10/encoder/tokenize.h
+++ b/vp10/encoder/tokenize.h
@@ -51,6 +51,9 @@ int vp10_has_high_freq_in_plane(MACROBLOCK *x, BLOCK_SIZE bsize, int plane);
 struct VP10_COMP;
 struct ThreadData;
 
+void vp10_tokenize_palette_sb(struct ThreadData *const td,
+                              BLOCK_SIZE bsize, int plane,
+                              TOKENEXTRA **t);
 void vp10_tokenize_sb(struct VP10_COMP *cpi, struct ThreadData *td,
                      TOKENEXTRA **t, int dry_run, BLOCK_SIZE bsize);
 
diff --git a/vp10/vp10cx.mk b/vp10/vp10cx.mk
index ead993ac2..7b77f314e 100644
--- a/vp10/vp10cx.mk
+++ b/vp10/vp10cx.mk
@@ -52,6 +52,8 @@ VP10_CX_SRCS-yes += encoder/tokenize.h
 VP10_CX_SRCS-yes += encoder/treewriter.h
 VP10_CX_SRCS-yes += encoder/mcomp.c
 VP10_CX_SRCS-yes += encoder/encoder.c
+VP10_CX_SRCS-yes += encoder/palette.h
+VP10_CX_SRCS-yes += encoder/palette.c
 VP10_CX_SRCS-yes += encoder/picklpf.c
 VP10_CX_SRCS-yes += encoder/picklpf.h
 VP10_CX_SRCS-yes += encoder/quantize.c