1// Copyright 2013 Google Inc. All Rights Reserved.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//    http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14//
15// Author: lode.vandevenne@gmail.com (Lode Vandevenne)
16// Author: jyrki.alakuijala@gmail.com (Jyrki Alakuijala)
17
18// See zopflipng_lib.h
19
20#include "zopflipng_lib.h"
21
22#include <stdio.h>
23#include <set>
24#include <vector>
25
26#include "lodepng/lodepng.h"
27#include "lodepng/lodepng_util.h"
28#include "../zopfli/deflate.h"
29
30ZopfliPNGOptions::ZopfliPNGOptions()
31  : lossy_transparent(false)
32  , lossy_8bit(false)
33  , auto_filter_strategy(true)
34  , use_zopfli(true)
35  , num_iterations(15)
36  , num_iterations_large(5)
37  , block_split_strategy(1) {
38}
39
40// Deflate compressor passed as fuction pointer to LodePNG to have it use Zopfli
41// as its compression backend.
42unsigned CustomPNGDeflate(unsigned char** out, size_t* outsize,
43                          const unsigned char* in, size_t insize,
44                          const LodePNGCompressSettings* settings) {
45  const ZopfliPNGOptions* png_options =
46      static_cast<const ZopfliPNGOptions*>(settings->custom_context);
47  unsigned char bp = 0;
48  ZopfliOptions options;
49  ZopfliInitOptions(&options);
50
51  options.numiterations = insize < 200000
52      ? png_options->num_iterations : png_options->num_iterations_large;
53
54  if (png_options->block_split_strategy == 3) {
55    // Try both block splitting first and last.
56    unsigned char* out2 = 0;
57    size_t outsize2 = 0;
58    options.blocksplittinglast = 0;
59    ZopfliDeflate(&options, 2 /* Dynamic */, 1, in, insize, &bp, out, outsize);
60    bp = 0;
61    options.blocksplittinglast = 1;
62    ZopfliDeflate(&options, 2 /* Dynamic */, 1,
63                  in, insize, &bp, &out2, &outsize2);
64
65    if (outsize2 < *outsize) {
66      free(*out);
67      *out = out2;
68      *outsize = outsize2;
69      printf("Block splitting last was better\n");
70    } else {
71      free(out2);
72    }
73  } else {
74    if (png_options->block_split_strategy == 0) options.blocksplitting = 0;
75    options.blocksplittinglast = png_options->block_split_strategy == 2;
76    ZopfliDeflate(&options, 2 /* Dynamic */, 1, in, insize, &bp, out, outsize);
77  }
78
79  return 0;  // OK
80}
81
82// Returns 32-bit integer value for RGBA color.
83static unsigned ColorIndex(const unsigned char* color) {
84  return color[0] + 256u * color[1] + 65536u * color[1] + 16777216u * color[3];
85}
86
87// Counts amount of colors in the image, up to 257. If transparent_counts_as_one
88// is enabled, any color with alpha channel 0 is treated as a single color with
89// index 0.
90void CountColors(std::set<unsigned>* unique,
91                 const unsigned char* image, unsigned w, unsigned h,
92                 bool transparent_counts_as_one) {
93  unique->clear();
94  for (size_t i = 0; i < w * h; i++) {
95    unsigned index = ColorIndex(&image[i * 4]);
96    if (transparent_counts_as_one && image[i * 4 + 3] == 0) index = 0;
97    unique->insert(index);
98    if (unique->size() > 256) break;
99  }
100}
101
102// Remove RGB information from pixels with alpha=0
103void LossyOptimizeTransparent(lodepng::State* inputstate, unsigned char* image,
104    unsigned w, unsigned h) {
105  // First check if we want to preserve potential color-key background color,
106  // or instead use the last encountered RGB value all the time to save bytes.
107  bool key = true;
108  for (size_t i = 0; i < w * h; i++) {
109    if (image[i * 4 + 3] > 0 && image[i * 4 + 3] < 255) {
110      key = false;
111      break;
112    }
113  }
114  std::set<unsigned> count;  // Color count, up to 257.
115  CountColors(&count, image, w, h, true);
116  // If true, means palette is possible so avoid using different RGB values for
117  // the transparent color.
118  bool palette = count.size() <= 256;
119
120  // Choose the color key or first initial background color.
121  int r = 0, g = 0, b = 0;
122  if (key || palette) {
123    for (size_t i = 0; i < w * h; i++) {
124      if (image[i * 4 + 3] == 0) {
125        // Use RGB value of first encountered transparent pixel. This can be
126        // used as a valid color key, or in case of palette ensures a color
127        // existing in the input image palette is used.
128        r = image[i * 4 + 0];
129        g = image[i * 4 + 1];
130        b = image[i * 4 + 2];
131      }
132    }
133  }
134
135  for (size_t i = 0; i < w * h; i++) {
136    // if alpha is 0, alter the RGB value to a possibly more efficient one.
137    if (image[i * 4 + 3] == 0) {
138      image[i * 4 + 0] = r;
139      image[i * 4 + 1] = g;
140      image[i * 4 + 2] = b;
141    } else {
142      if (!key && !palette) {
143        // Use the last encountered RGB value if no key or palette is used: that
144        // way more values can be 0 thanks to the PNG filter types.
145        r = image[i * 4 + 0];
146        g = image[i * 4 + 1];
147        b = image[i * 4 + 2];
148      }
149    }
150  }
151
152  // If there are now less colors, update palette of input image to match this.
153  if (palette && inputstate->info_png.color.palettesize > 0) {
154    CountColors(&count, image, w, h, false);
155    if (count.size() < inputstate->info_png.color.palettesize) {
156      std::vector<unsigned char> palette_out;
157      unsigned char* palette_in = inputstate->info_png.color.palette;
158      for (size_t i = 0; i < inputstate->info_png.color.palettesize; i++) {
159        if (count.count(ColorIndex(&palette_in[i * 4])) != 0) {
160          palette_out.push_back(palette_in[i * 4 + 0]);
161          palette_out.push_back(palette_in[i * 4 + 1]);
162          palette_out.push_back(palette_in[i * 4 + 2]);
163          palette_out.push_back(palette_in[i * 4 + 3]);
164        }
165      }
166      inputstate->info_png.color.palettesize = palette_out.size() / 4;
167      for (size_t i = 0; i < palette_out.size(); i++) {
168        palette_in[i] = palette_out[i];
169      }
170    }
171  }
172}
173
174// Tries to optimize given a single PNG filter strategy.
175// Returns 0 if ok, other value for error
176unsigned TryOptimize(
177    const std::vector<unsigned char>& image, unsigned w, unsigned h,
178    const lodepng::State& inputstate, bool bit16,
179    const std::vector<unsigned char>& origfile,
180    ZopfliPNGFilterStrategy filterstrategy,
181    bool use_zopfli, int windowsize, const ZopfliPNGOptions* png_options,
182    std::vector<unsigned char>* out) {
183  unsigned error = 0;
184
185  lodepng::State state;
186  state.encoder.zlibsettings.windowsize = windowsize;
187  if (use_zopfli && png_options->use_zopfli) {
188    state.encoder.zlibsettings.custom_deflate = CustomPNGDeflate;
189    state.encoder.zlibsettings.custom_context = png_options;
190  }
191
192  if (inputstate.info_png.color.colortype == LCT_PALETTE) {
193    // Make it preserve the original palette order
194    lodepng_color_mode_copy(&state.info_raw, &inputstate.info_png.color);
195    state.info_raw.colortype = LCT_RGBA;
196    state.info_raw.bitdepth = 8;
197  }
198  if (bit16) {
199    state.info_raw.bitdepth = 16;
200  }
201
202  state.encoder.filter_palette_zero = 0;
203
204  std::vector<unsigned char> filters;
205  switch (filterstrategy) {
206    case kStrategyZero:
207      state.encoder.filter_strategy = LFS_ZERO;
208      break;
209    case kStrategyMinSum:
210      state.encoder.filter_strategy = LFS_MINSUM;
211      break;
212    case kStrategyEntropy:
213      state.encoder.filter_strategy = LFS_ENTROPY;
214      break;
215    case kStrategyBruteForce:
216      state.encoder.filter_strategy = LFS_BRUTE_FORCE;
217      break;
218    case kStrategyOne:
219    case kStrategyTwo:
220    case kStrategyThree:
221    case kStrategyFour:
222      // Set the filters of all scanlines to that number.
223      filters.resize(h, filterstrategy);
224      state.encoder.filter_strategy = LFS_PREDEFINED;
225      state.encoder.predefined_filters = &filters[0];
226      break;
227    case kStrategyPredefined:
228      lodepng::getFilterTypes(filters, origfile);
229      state.encoder.filter_strategy = LFS_PREDEFINED;
230      state.encoder.predefined_filters = &filters[0];
231      break;
232    default:
233      break;
234  }
235
236  state.encoder.add_id = false;
237  state.encoder.text_compression = 1;
238
239  error = lodepng::encode(*out, image, w, h, state);
240
241  // For very small output, also try without palette, it may be smaller thanks
242  // to no palette storage overhead.
243  if (!error && out->size() < 4096) {
244    lodepng::State teststate;
245    std::vector<unsigned char> temp;
246    lodepng::decode(temp, w, h, teststate, *out);
247    LodePNGColorMode& color = teststate.info_png.color;
248    if (color.colortype == LCT_PALETTE) {
249      std::vector<unsigned char> out2;
250      state.encoder.auto_convert = LAC_ALPHA;
251      bool grey = true;
252      for (size_t i = 0; i < color.palettesize; i++) {
253        if (color.palette[i * 4 + 0] != color.palette[i * 4 + 2]
254            || color.palette[i * 4 + 1] != color.palette[i * 4 + 2]) {
255          grey = false;
256          break;
257        }
258      }
259      if (grey) state.info_png.color.colortype = LCT_GREY_ALPHA;
260
261      error = lodepng::encode(out2, image, w, h, state);
262      if (out2.size() < out->size()) out->swap(out2);
263    }
264  }
265
266  if (error) {
267    printf("Encoding error %u: %s\n", error, lodepng_error_text(error));
268    return error;
269  }
270
271  return 0;
272}
273
274// Use fast compression to check which PNG filter strategy gives the smallest
275// output. This allows to then do the slow and good compression only on that
276// filter type.
277unsigned AutoChooseFilterStrategy(const std::vector<unsigned char>& image,
278                                  unsigned w, unsigned h,
279                                  const lodepng::State& inputstate, bool bit16,
280                                  const std::vector<unsigned char>& origfile,
281                                  int numstrategies,
282                                  ZopfliPNGFilterStrategy* strategies,
283                                  bool* enable) {
284  std::vector<unsigned char> out;
285  size_t bestsize = 0;
286  int bestfilter = 0;
287
288  // A large window size should still be used to do the quick compression to
289  // try out filter strategies: which filter strategy is the best depends
290  // largely on the window size, the closer to the actual used window size the
291  // better.
292  int windowsize = 8192;
293
294  for (int i = 0; i < numstrategies; i++) {
295    out.clear();
296    unsigned error = TryOptimize(image, w, h, inputstate, bit16, origfile,
297                                 strategies[i], false, windowsize, 0, &out);
298    if (error) return error;
299    if (bestsize == 0 || out.size() < bestsize) {
300      bestsize = out.size();
301      bestfilter = i;
302    }
303  }
304
305  for (int i = 0; i < numstrategies; i++) {
306    enable[i] = (i == bestfilter);
307  }
308
309  return 0;  /* OK */
310}
311
312// Keeps chunks with given names from the original png by literally copying them
313// into the new png
314void KeepChunks(const std::vector<unsigned char>& origpng,
315                const std::vector<std::string>& keepnames,
316                std::vector<unsigned char>* png) {
317  std::vector<std::string> names[3];
318  std::vector<std::vector<unsigned char> > chunks[3];
319
320  lodepng::getChunks(names, chunks, origpng);
321  std::vector<std::vector<unsigned char> > keepchunks[3];
322
323  // There are 3 distinct locations in a PNG file for chunks: between IHDR and
324  // PLTE, between PLTE and IDAT, and between IDAT and IEND. Keep each chunk at
325  // its corresponding location in the new PNG.
326  for (size_t i = 0; i < 3; i++) {
327    for (size_t j = 0; j < names[i].size(); j++) {
328      for (size_t k = 0; k < keepnames.size(); k++) {
329        if (keepnames[k] == names[i][j]) {
330          keepchunks[i].push_back(chunks[i][j]);
331        }
332      }
333    }
334  }
335
336  lodepng::insertChunks(*png, keepchunks);
337}
338
339int ZopfliPNGOptimize(const std::vector<unsigned char>& origpng,
340    const ZopfliPNGOptions& png_options,
341    bool verbose,
342    std::vector<unsigned char>* resultpng) {
343  // Use the largest possible deflate window size
344  int windowsize = 32768;
345
346  ZopfliPNGFilterStrategy filterstrategies[kNumFilterStrategies] = {
347    kStrategyZero, kStrategyOne, kStrategyTwo, kStrategyThree, kStrategyFour,
348    kStrategyMinSum, kStrategyEntropy, kStrategyPredefined, kStrategyBruteForce
349  };
350  bool strategy_enable[kNumFilterStrategies] = {
351    false, false, false, false, false, false, false, false, false
352  };
353  std::string strategy_name[kNumFilterStrategies] = {
354    "zero", "one", "two", "three", "four",
355    "minimum sum", "entropy", "predefined", "brute force"
356  };
357  for (size_t i = 0; i < png_options.filter_strategies.size(); i++) {
358    strategy_enable[png_options.filter_strategies[i]] = true;
359  }
360
361  std::vector<unsigned char> image;
362  unsigned w, h;
363  unsigned error;
364  lodepng::State inputstate;
365  error = lodepng::decode(image, w, h, inputstate, origpng);
366
367  if (error) {
368    if (verbose) {
369      printf("Decoding error %i: %s\n", error, lodepng_error_text(error));
370    }
371    return error;
372  }
373
374  bool bit16 = false;  // Using 16-bit per channel raw image
375  if (inputstate.info_png.color.bitdepth == 16 && !png_options.lossy_8bit) {
376    // Decode as 16-bit
377    image.clear();
378    error = lodepng::decode(image, w, h, origpng, LCT_RGBA, 16);
379    bit16 = true;
380  }
381
382  if (!error) {
383    // If lossy_transparent, remove RGB information from pixels with alpha=0
384    if (png_options.lossy_transparent && !bit16) {
385      LossyOptimizeTransparent(&inputstate, &image[0], w, h);
386    }
387
388    if (png_options.auto_filter_strategy) {
389      error = AutoChooseFilterStrategy(image, w, h, inputstate, bit16,
390                                       origpng,
391                                       /* Don't try brute force */
392                                       kNumFilterStrategies - 1,
393                                       filterstrategies, strategy_enable);
394    }
395  }
396
397  if (!error) {
398    size_t bestsize = 0;
399
400    for (int i = 0; i < kNumFilterStrategies; i++) {
401      if (!strategy_enable[i]) continue;
402
403      std::vector<unsigned char> temp;
404      error = TryOptimize(image, w, h, inputstate, bit16, origpng,
405                          filterstrategies[i], true /* use_zopfli */,
406                          windowsize, &png_options, &temp);
407      if (!error) {
408        if (verbose) {
409          printf("Filter strategy %s: %d bytes\n",
410                 strategy_name[i].c_str(), (int) temp.size());
411        }
412        if (bestsize == 0 || temp.size() < bestsize) {
413          bestsize = temp.size();
414          (*resultpng).swap(temp);  // Store best result so far in the output.
415        }
416      }
417    }
418
419    if (!png_options.keepchunks.empty()) {
420      KeepChunks(origpng, png_options.keepchunks, resultpng);
421    }
422  }
423
424  return error;
425}
426