Home | History | Annotate | Download | only in zopflipng 
      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 (at) gmail.com (Lode Vandevenne)
     16 // Author: jyrki.alakuijala (at) 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 
     30 ZopfliPNGOptions::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.
     42 unsigned 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.
     83 static 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.
     90 void 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
    103 void 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
    176 unsigned 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.
    277 unsigned 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
    314 void 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 
    339 int 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