Put 0 at the end of a palette and do not store it.upstream-main

This only applies to kSortedDefault and kMinimizeDelta.

Change-Id: I9d4178406ed2ef91c5c55f0a1919cfc6605fedf9

3 files changed, 27 insertions, 7 deletions

diff --git a/src/enc/vp8l_enc.c b/src/enc/vp8l_enc.c
index cd045e49..41a6d34e 100644
--- a/src/enc/vp8l_enc.c
+++ b/src/enc/vp8l_enc.c
@@ -1419,17 +1419,24 @@ static WebPEncodingError EncodePalette(VP8LBitWriter* const bw, int low_effort,
   uint32_t tmp_palette[MAX_PALETTE_SIZE];
   const int palette_size = enc->palette_size_;
   const uint32_t* const palette = enc->palette_;
+  // If the last element is 0, do not store it and count on automatic palette
+  // 0-filling. This can only happen if there is no pixel packing, hence if
+  // there are strictly more than 16 colors (after 0 is removed).
+  const uint32_t encoded_palette_size =
+      (enc->palette_[palette_size - 1] == 0 && palette_size > 17)
+          ? palette_size - 1
+          : palette_size;
   VP8LPutBits(bw, TRANSFORM_PRESENT, 1);
   VP8LPutBits(bw, COLOR_INDEXING_TRANSFORM, 2);
   assert(palette_size >= 1 && palette_size <= MAX_PALETTE_SIZE);
-  VP8LPutBits(bw, palette_size - 1, 8);
-  for (i = palette_size - 1; i >= 1; --i) {
+  VP8LPutBits(bw, encoded_palette_size - 1, 8);
+  for (i = encoded_palette_size - 1; i >= 1; --i) {
     tmp_palette[i] = VP8LSubPixels(palette[i], palette[i - 1]);
   }
   tmp_palette[0] = palette[0];
-  return EncodeImageNoHuffman(bw, tmp_palette, &enc->hash_chain_,
-                              &enc->refs_[0], palette_size, 1, /*quality=*/20,
-                              low_effort, enc->pic_, percent_range, percent);
+  return EncodeImageNoHuffman(
+      bw, tmp_palette, &enc->hash_chain_, &enc->refs_[0], encoded_palette_size,
+      1, /*quality=*/20, low_effort, enc->pic_, percent_range, percent);
 }
 
 // -----------------------------------------------------------------------------
diff --git a/src/utils/palette.c b/src/utils/palette.c
index 515da210..8ae0a5cd 100644
--- a/src/utils/palette.c
+++ b/src/utils/palette.c
@@ -191,6 +191,12 @@ static void PaletteSortMinimizeDeltas(const uint32_t* const palette_sorted,
   // Find greedily always the closest color of the predicted color to minimize
   // deltas in the palette. This reduces storage needs since the
   // palette is stored with delta encoding.
+  if (num_colors > 17) {
+    if (palette[0] == 0) {
+      --num_colors;
+      SwapColor(&palette[num_colors], &palette[0]);
+    }
+  }
   for (i = 0; i < num_colors; ++i) {
     int best_ix = i;
     uint32_t best_score = ~0U;
@@ -384,8 +390,13 @@ int PaletteSort(PaletteSorting method, const struct WebPPicture* const pic,
                 uint32_t* const palette) {
   switch (method) {
     case kSortedDefault:
-      // Nothing to do, we have already sorted the palette.
-      memcpy(palette, palette_sorted, num_colors * sizeof(*palette));
+      if (palette_sorted[0] == 0 && num_colors > 17) {
+        memcpy(palette, palette_sorted + 1,
+               (num_colors - 1) * sizeof(*palette_sorted));
+        palette[num_colors - 1] = 0;
+      } else {
+        memcpy(palette, palette_sorted, num_colors * sizeof(*palette));
+      }
       return 1;
     case kMinimizeDelta:
       PaletteSortMinimizeDeltas(palette_sorted, num_colors, palette);
diff --git a/src/utils/palette.h b/src/utils/palette.h
index 34479e46..417c61fa 100644
--- a/src/utils/palette.h
+++ b/src/utils/palette.h
@@ -53,6 +53,8 @@ int GetColorPalette(const struct WebPPicture* const pic,
 // Sorts the palette according to the criterion defined by 'method'.
 // 'palette_sorted' is the input palette sorted lexicographically, as done in
 // PrepareMapToPalette. Returns 0 on memory allocation error.
+// For kSortedDefault and kMinimizeDelta methods, 0 (if present) is set as the
+// last element to optimize later storage.
 int PaletteSort(PaletteSorting method, const struct WebPPicture* const pic,
                 const uint32_t* const palette_sorted, uint32_t num_colors,
                 uint32_t* const palette);