zopflipng_lib.cc revision 337d27f25ef15a6cf34fef2acd0613fddc411cb1 
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 <vector>
24
25#include "lodepng/lodepng.h"
26#include "lodepng/lodepng_util.h"
27#include "../zopfli/deflate.h"
28
29ZopfliPNGOptions::ZopfliPNGOptions()
30  : lossy_transparent(false)
31  , lossy_8bit(false)
32  , auto_filter_strategy(true)
33  , use_zopfli(true)
34  , num_iterations(15)
35  , num_iterations_large(5)
36  , block_split_strategy(1) {
37}
38
39// Deflate compressor passed as fuction pointer to LodePNG to have it use Zopfli
40// as its compression backend.
41unsigned CustomPNGDeflate(unsigned char** out, size_t* outsize,
42                          const unsigned char* in, size_t insize,
43                          const LodePNGCompressSettings* settings) {
44  const ZopfliPNGOptions* png_options =
45      static_cast<const ZopfliPNGOptions*>(settings->custom_context);
46  unsigned char bp = 0;
47  ZopfliOptions options;
48  ZopfliInitOptions(&options);
49
50  options.numiterations = insize < 200000
51      ? png_options->num_iterations : png_options->num_iterations_large;
52
53  if (png_options->block_split_strategy == 3) {
54    // Try both block splitting first and last.
55    unsigned char* out2 = 0;
56    size_t outsize2 = 0;
57    options.blocksplittinglast = 0;
58    ZopfliDeflate(&options, 2 /* Dynamic */, 1, in, insize, &bp, out, outsize);
59    bp = 0;
60    options.blocksplittinglast = 1;
61    ZopfliDeflate(&options, 2 /* Dynamic */, 1,
62                  in, insize, &bp, &out2, &outsize2);
63
64    if (outsize2 < *outsize) {
65      free(*out);
66      *out = out2;
67      *outsize = outsize2;
68      printf("Block splitting last was better\n");
69    } else {
70      free(out2);
71    }
72  } else {
73    if (png_options->block_split_strategy == 0) options.blocksplitting = 0;
74    options.blocksplittinglast = png_options->block_split_strategy == 2;
75    ZopfliDeflate(&options, 2 /* Dynamic */, 1, in, insize, &bp, out, outsize);
76  }
77
78  return 0;  // OK
79}
80
81// Remove RGB information from pixels with alpha=0
82void LossyOptimizeTransparent(unsigned char* image, unsigned w, unsigned h) {
83  // First check if we want to preserve potential color-key background color,
84  // or instead use the last encountered RGB value all the time to save bytes.
85  bool key = true;
86  for (size_t i = 0; i < w * h; i++) {
87    if (image[i * 4 + 3] > 0 && image[i * 4 + 3] < 255) {
88      key = false;
89      break;
90    }
91  }
92
93  // Choose the color key if color keying is used.
94  int r = 0, g = 0, b = 0;
95  if (key) {
96    for (size_t i = 0; i < w * h; i++) {
97      if (image[i * 4 + 3] == 0) {
98        // Use first encountered transparent pixel as the color key
99        r = image[i * 4 + 0];
100        g = image[i * 4 + 1];
101        b = image[i * 4 + 2];
102      }
103    }
104  }
105
106  for (size_t i = 0; i < w * h; i++) {
107    // if alpha is 0
108    if (image[i * 4 + 3] == 0) {
109      image[i * 4 + 0] = r;
110      image[i * 4 + 1] = g;
111      image[i * 4 + 2] = b;
112    } else {
113      if (!key) {
114        // Use the last encountered RGB value if no color keying is used.
115        r = image[i * 4 + 0];
116        g = image[i * 4 + 1];
117        b = image[i * 4 + 2];
118      }
119    }
120  }
121}
122
123// Tries to optimize given a single PNG filter strategy.
124// Returns 0 if ok, other value for error
125unsigned TryOptimize(
126    const std::vector<unsigned char>& image, unsigned w, unsigned h,
127    const lodepng::State& inputstate, bool bit16,
128    const std::vector<unsigned char>& origfile,
129    ZopfliPNGFilterStrategy filterstrategy,
130    bool use_zopfli, int windowsize, const ZopfliPNGOptions* png_options,
131    std::vector<unsigned char>* out) {
132  unsigned error = 0;
133
134  lodepng::State state;
135  state.encoder.zlibsettings.windowsize = windowsize;
136  if (use_zopfli && png_options->use_zopfli) {
137    ZopfliPNGOptions custom_context = *png_options;
138    state.encoder.zlibsettings.custom_deflate = CustomPNGDeflate;
139    state.encoder.zlibsettings.custom_context = &custom_context;
140  }
141
142  if (inputstate.info_png.color.colortype == LCT_PALETTE) {
143    // Make it preserve the original palette order
144    lodepng_color_mode_copy(&state.info_raw, &inputstate.info_png.color);
145    state.info_raw.colortype = LCT_RGBA;
146    state.info_raw.bitdepth = 8;
147  }
148  if (bit16) {
149    state.info_raw.bitdepth = 16;
150  }
151
152  state.encoder.filter_palette_zero = 0;
153
154  std::vector<unsigned char> filters;
155  switch (filterstrategy) {
156    case kStrategyZero:
157      state.encoder.filter_strategy = LFS_ZERO;
158      break;
159    case kStrategyMinSum:
160      state.encoder.filter_strategy = LFS_MINSUM;
161      break;
162    case kStrategyEntropy:
163      state.encoder.filter_strategy = LFS_ENTROPY;
164      break;
165    case kStrategyBruteForce:
166      state.encoder.filter_strategy = LFS_BRUTE_FORCE;
167      break;
168    case kStrategyOne:
169    case kStrategyTwo:
170    case kStrategyThree:
171    case kStrategyFour:
172      // Set the filters of all scanlines to that number.
173      filters.resize(h, filterstrategy);
174      state.encoder.filter_strategy = LFS_PREDEFINED;
175      state.encoder.predefined_filters = &filters[0];
176      break;
177    case kStrategyPredefined:
178      lodepng::getFilterTypes(filters, origfile);
179      state.encoder.filter_strategy = LFS_PREDEFINED;
180      state.encoder.predefined_filters = &filters[0];
181      break;
182    default:
183      break;
184  }
185
186  state.encoder.add_id = false;
187  state.encoder.text_compression = 1;
188
189  error = lodepng::encode(*out, image, w, h, state);
190
191  // For very small output, also try without palette, it may be smaller thanks
192  // to no palette storage overhead.
193  if (!error && out->size() < 4096) {
194    lodepng::State teststate;
195    std::vector<unsigned char> temp;
196    lodepng::decode(temp, w, h, teststate, *out);
197    LodePNGColorMode& color = teststate.info_png.color;
198    if (color.colortype == LCT_PALETTE) {
199      std::vector<unsigned char> out2;
200      state.encoder.auto_convert = LAC_ALPHA;
201      bool grey = true;
202      for (size_t i = 0; i < color.palettesize; i++) {
203        if (color.palette[i * 4 + 0] != color.palette[i * 4 + 2]
204            || color.palette[i * 4 + 1] != color.palette[i * 4 + 2]) {
205          grey = false;
206          break;
207        }
208      }
209      if (grey) state.info_png.color.colortype = LCT_GREY_ALPHA;
210
211      error = lodepng::encode(out2, image, w, h, state);
212      if (out2.size() < out->size()) out->swap(out2);
213    }
214  }
215
216  if (error) {
217    printf("Encoding error %i: %s\n", error, lodepng_error_text(error));
218    return error;
219  }
220
221  return 0;
222}
223
224// Use fast compression to check which PNG filter strategy gives the smallest
225// output. This allows to then do the slow and good compression only on that
226// filter type.
227unsigned AutoChooseFilterStrategy(const std::vector<unsigned char>& image,
228                                  unsigned w, unsigned h,
229                                  const lodepng::State& inputstate, bool bit16,
230                                  const std::vector<unsigned char>& origfile,
231                                  int numstrategies,
232                                  ZopfliPNGFilterStrategy* strategies,
233                                  bool* enable) {
234  std::vector<unsigned char> out;
235  size_t bestsize = 0;
236  int bestfilter = 0;
237
238  // A large window size should still be used to do the quick compression to
239  // try out filter strategies: which filter strategy is the best depends
240  // largely on the window size, the closer to the actual used window size the
241  // better.
242  int windowsize = 8192;
243
244  for (int i = 0; i < numstrategies; i++) {
245    out.clear();
246    unsigned error = TryOptimize(image, w, h, inputstate, bit16, origfile,
247                                 strategies[i], false, windowsize, 0, &out);
248    if (error) return error;
249    if (bestsize == 0 || out.size() < bestsize) {
250      bestsize = out.size();
251      bestfilter = i;
252    }
253  }
254
255  for (int i = 0; i < numstrategies; i++) {
256    enable[i] = (i == bestfilter);
257  }
258
259  return 0;  /* OK */
260}
261
262// Keeps chunks with given names from the original png by literally copying them
263// into the new png
264void KeepChunks(const std::vector<unsigned char>& origpng,
265                const std::vector<std::string>& keepnames,
266                std::vector<unsigned char>* png) {
267  std::vector<std::string> names[3];
268  std::vector<std::vector<unsigned char> > chunks[3];
269
270  lodepng::getChunks(names, chunks, origpng);
271  std::vector<std::vector<unsigned char> > keepchunks[3];
272
273  // There are 3 distinct locations in a PNG file for chunks: between IHDR and
274  // PLTE, between PLTE and IDAT, and between IDAT and IEND. Keep each chunk at
275  // its corresponding location in the new PNG.
276  for (size_t i = 0; i < 3; i++) {
277    for (size_t j = 0; j < names[i].size(); j++) {
278      for (size_t k = 0; k < keepnames.size(); k++) {
279        if (keepnames[k] == names[i][j]) {
280          keepchunks[i].push_back(chunks[i][j]);
281        }
282      }
283    }
284  }
285
286  lodepng::insertChunks(*png, keepchunks);
287}
288
289int ZopfliPNGOptimize(const std::vector<unsigned char>& origpng,
290    const ZopfliPNGOptions& png_options,
291    bool verbose,
292    std::vector<unsigned char>* resultpng) {
293  // Use the largest possible deflate window size
294  int windowsize = 32768;
295
296  ZopfliPNGFilterStrategy filterstrategies[kNumFilterStrategies] = {
297    kStrategyZero, kStrategyOne, kStrategyTwo, kStrategyThree, kStrategyFour,
298    kStrategyMinSum, kStrategyEntropy, kStrategyPredefined, kStrategyBruteForce
299  };
300  bool strategy_enable[kNumFilterStrategies] = {
301    false, false, false, false, false, false, false, false, false
302  };
303  std::string strategy_name[kNumFilterStrategies] = {
304    "zero", "one", "two", "three", "four",
305    "minimum sum", "entropy", "predefined", "brute force"
306  };
307  for (size_t i = 0; i < png_options.filter_strategies.size(); i++) {
308    strategy_enable[png_options.filter_strategies[i]] = true;
309  }
310
311
312  std::vector<unsigned char> image;
313  unsigned w, h;
314  unsigned error;
315  lodepng::State inputstate;
316  error = lodepng::decode(image, w, h, inputstate, origpng);
317
318  if (error) {
319    if (verbose) {
320      printf("Decoding error %i: %s\n", error, lodepng_error_text(error));
321    }
322    return error;
323  }
324
325  bool bit16 = false;  // Using 16-bit per channel raw image
326  if (inputstate.info_png.color.bitdepth == 16 && !png_options.lossy_8bit) {
327    // Decode as 16-bit
328    image.clear();
329    error = lodepng::decode(image, w, h, origpng, LCT_RGBA, 16);
330    bit16 = true;
331  }
332
333  if (!error) {
334    // If lossy_transparent, remove RGB information from pixels with alpha=0
335    if (png_options.lossy_transparent && !bit16) {
336      LossyOptimizeTransparent(&image[0], w, h);
337    }
338
339    if (png_options.auto_filter_strategy) {
340      error = AutoChooseFilterStrategy(image, w, h, inputstate, bit16,
341                                       origpng,
342                                       /* Don't try brute force */
343                                       kNumFilterStrategies - 1,
344                                       filterstrategies, strategy_enable);
345    }
346  }
347
348  if (!error) {
349    size_t bestsize = 0;
350
351    for (int i = 0; i < kNumFilterStrategies; i++) {
352      if (!strategy_enable[i]) continue;
353
354      std::vector<unsigned char> temp;
355      error = TryOptimize(image, w, h, inputstate, bit16, origpng,
356                          filterstrategies[i], true /* use_zopfli */,
357                          windowsize, &png_options, &temp);
358      if (!error) {
359        if (verbose) {
360          printf("Filter strategy %s: %d bytes\n",
361                 strategy_name[i].c_str(), (int) temp.size());
362        }
363        if (bestsize == 0 || temp.size() < bestsize) {
364          bestsize = temp.size();
365          (*resultpng).swap(temp);  // Store best result so far in the output.
366        }
367      }
368    }
369
370    if (!png_options.keepchunks.empty()) {
371      KeepChunks(origpng, png_options.keepchunks, resultpng);
372    }
373  }
374
375  return error;
376}
377