sketch hooking into PNG_FILTER_OPTIMIZATIONS

src/codec/SkPngCodec.cpp

 /*
  * Copyright 2015 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #include "SkCodecPriv.h"
 #include "SkColorPriv.h"
 #include "SkColorTable.h"
 #include "SkBitmap.h"
 #include "SkMath.h"
 #include "SkPngCodec.h"
 #include "SkSize.h"
 #include "SkStream.h"
 #include "SkSwizzler.h"
 #include "SkTemplates.h"
 
+#if defined(__SSE2__)

[msarett, 2016/01/26 22:35:02]

Is there another file we can put this in?

Seems to add complicated to code a file that's already pretty long.  And maybe
I'm looking too far ahead, but I'm guessing that there'll be more filter opts to
come - Ooh maybe src/opts/SkPngFilters_opt?

[mtklein, 2016/01/26 22:52:17]

I do think there will be more of these.

We'll definitely want Paeth for bpp=3 in addition to this one for bpp=4.  Left
and Avg should be similar to Paeth, but a little faster and rather easier to
read and write.  Up is _so_ easy to write that we'll want to do that just
because it'll be so fun.   A single implementation for Up can handle all bpp,
and can handle any number of pixels at a time.  I'll leave that one for you. :)

As long as we're working on one pixel at a time, bpp only matters as far as
loading and storing.  So in terms of speed / implementation difficultly, things
break down into a couple classes by bpp:
   {4,8}:  fastest
   {2,3}:  not bad
   6: annoying
It's probably difficult to improve anything but Up for bpp=1 (notice that this
code is not below 0.25x).
I figure we don't care much about 16-bit component formats (bpp=2,6,8)?

[mtklein_C, 2016/01/27 00:21:26]

I've moved things to a new file, src/codec/SkPngFilters.cpp.

I've taken the opportunity to implement a few more filters.

I'm not confident that these new ones are any of:
   1. faster,
   2. usefully faster, or
   3. correct.
But I figured you might like to see how I'd evolve the file if we do write
those.

Still TBD are load3() / store3() and consequently the bpp=3 variants of Sub,
Avg, and Paeth.

+    #include "pngstruct.h"
+
+    // Returns bytewise |x-y|.
+    static __m128i absdiff_u8(__m128i x, __m128i y) {
+        // One of these two saturated subtractions will be the answer, the other zero.
+        return _mm_or_si128(_mm_subs_epu8(x,y), _mm_subs_epu8(y,x));
+    }
+
+    // Bytewise c ? t : e.
+    static __m128i if_then_else(__m128i c, __m128i t, __m128i e) {
+        // SSE 4.1+ would be: return _mm_blendv_epi8(e,t,c);
+        return _mm_or_si128(_mm_and_si128(c, t), _mm_andnot_si128(c, e));
+    }
+
+    static void sk_paeth4_sse2(png_row_infop row_info, png_bytep row_u8, png_const_bytep prev_u8) {
+        auto prev = (const uint32_t*)prev_u8;
+        auto row  = (uint32_t*)row_u8;
+        int n = row_info->rowbytes / 4;
+
+        // Paeth tries to predict pixel d using the pixel to the left of it, a,
+        // and two pixels from the previous row, b and c:
+        //   prev: c b
+        //   row:  a d
+        // The Paeth function predicts d to be whichever of a, b, or c is nearest to p=a+b-c.
+
+        // The first pixel has no left context, and so uses an Up filter, p = b.
+        // This works naturally with our main loop's p = a+b-c if we force a and c to zero.
+        // Here we zero b and d, which become c and a respectively at the start of the loop.
+        __m128i c, b = _mm_setzero_si128(),
+                a, d = _mm_setzero_si128();
+
+        while (n --> 0) {
+            c = b; b = _mm_cvtsi32_si128(*prev++);
+            a = d; d = _mm_cvtsi32_si128(*row);
+
+            // We can't express p in 8 bits, but luckily we can use this faux p instead:
+            __m128i min = _mm_min_epu8(a,b),
+                    max = _mm_max_epu8(a,b),
+                    faux_p = _mm_adds_epu8(min, _mm_subs_epu8(max, c));
+
+            // We could use faux_p for calculating all three of pa,pb,pc,
+            // but it's a little quicker to calculate the correct pa and pb directly.
+            __m128i pa = absdiff_u8(b,c),             // |a+b-c - a| == |b-c|
+                    pb = absdiff_u8(a,c),             // |a+b-c - b| == |a-c|
+                    faux_pc = absdiff_u8(faux_p, c);
+
+            // From here, things are straightforward.  Find the smallest distance to p...
+            __m128i smallest = _mm_min_epu8(_mm_min_epu8(pa, pb), faux_pc);
+
+            // ... then the predictor is the input corresponding to that smallest distance,
+            // breaking ties in favor of a over b over c.
+            __m128i nearest = if_then_else(_mm_cmpeq_epi8(smallest, pa), a,
+                              if_then_else(_mm_cmpeq_epi8(smallest, pb), b,
+                                                                         c));
+
+            // We've reconstructed d!  Leave it for next round to become a, and write it out.
+            d = _mm_add_epi8(d, nearest);
+            *row++ = _mm_cvtsi128_si32(d);
+        }
+    }
+
+    extern "C" void sk_png_init_filter_functions_sse2(png_structp png, unsigned int bpp) {
+        if (bpp == 4) {
+            png->read_filter[PNG_FILTER_VALUE_PAETH-1] = sk_paeth4_sse2;
+        }
+    }
+#endif
+
 ///////////////////////////////////////////////////////////////////////////////
 // Helper macros
 ///////////////////////////////////////////////////////////////////////////////
 
 #ifndef png_jmpbuf
 #  define png_jmpbuf(png_ptr) ((png_ptr)->jmpbuf)
 #endif
 
 /* These were dropped in libpng >= 1.4 */
 #ifndef png_infopp_NULL
@@ skipping 295 matching lines @@
                 png_set_tRNS_to_alpha(png_ptr);
                 png_set_gray_to_rgb(png_ptr);
                 skColorType = kN32_SkColorType;
                 skAlphaType = kUnpremul_SkAlphaType;
             } else {
                 skColorType = kGray_8_SkColorType;
                 skAlphaType = kOpaque_SkAlphaType;
             }
             break;
         case PNG_COLOR_TYPE_GRAY_ALPHA:
-            //FIXME: support gray with alpha as a color type 
-            //convert to RGBA 
+            //FIXME: support gray with alpha as a color type
+            //convert to RGBA
             png_set_gray_to_rgb(png_ptr);
             skColorType = kN32_SkColorType;
             skAlphaType = kUnpremul_SkAlphaType;
             break;
         case PNG_COLOR_TYPE_RGBA:
             skColorType = kN32_SkColorType;
             skAlphaType = kUnpremul_SkAlphaType;
             break;
         default:
             //all the color types have been covered above
@@ skipping 53 matching lines @@
 SkCodec::Result SkPngCodec::initializeSwizzler(const SkImageInfo& requestedInfo,
                                                const Options& options,
                                                SkPMColor ctable[],
                                                int* ctableCount) {
     // FIXME: Could we use the return value of setjmp to specify the type of
     // error?
     if (setjmp(png_jmpbuf(fPng_ptr))) {
         SkCodecPrintf("setjmp long jump!\n");
         return kInvalidInput;
     }
-    png_read_update_info(fPng_ptr, fInfo_ptr);  
+    png_read_update_info(fPng_ptr, fInfo_ptr);
 
     //srcColorType was determined in read_header() which determined png color type
     const SkColorType srcColorType = this->getInfo().colorType();
 
     switch (srcColorType) {
         case kIndex_8_SkColorType:
             //decode palette to Skia format
             fSrcConfig = SkSwizzler::kIndex;
             if (!this->decodePalette(kPremul_SkAlphaType == requestedInfo.alphaType(),
                     ctableCount)) {
                 return kInvalidInput;
             }
             break;
         case kGray_8_SkColorType:
             fSrcConfig = SkSwizzler::kGray;
-            break; 
+            break;
         case kN32_SkColorType:
             if (this->getInfo().alphaType() == kOpaque_SkAlphaType) {
                     fSrcConfig = SkSwizzler::kRGB;
                 } else {
                     fSrcConfig = SkSwizzler::kRGBA;
             }
             break;
         default:
             //would have exited before now if the colorType was supported by png
             SkASSERT(false);
-    }  
+    }
 
     // Copy the color table to the client if they request kIndex8 mode
     copy_color_table(requestedInfo, fColorTable, ctable, ctableCount);
 
     // Create the swizzler.  SkPngCodec retains ownership of the color table.
     const SkPMColor* colors = get_color_ptr(fColorTable.get());
     fSwizzler.reset(SkSwizzler::CreateSwizzler(fSrcConfig, colors, requestedInfo, options));
     if (!fSwizzler) {
         // FIXME: CreateSwizzler could fail for another reason.
         return kUnimplemented;
@@ skipping 170 matching lines @@
 
         return row;
     }
 
     bool onSkipScanlines(int count) override {
         // Assume that an error in libpng indicates an incomplete input.
         if (setjmp(png_jmpbuf(this->png_ptr()))) {
             SkCodecPrintf("setjmp long jump!\n");
             return false;
         }
-        //there is a potential tradeoff of memory vs speed created by putting this in a loop. 
-        //calling png_read_rows in a loop is insignificantly slower than calling it once with count 
+        //there is a potential tradeoff of memory vs speed created by putting this in a loop.
+        //calling png_read_rows in a loop is insignificantly slower than calling it once with count
         //as png_read_rows has it's own loop which calls png_read_row count times.
         for (int row = 0; row < count; row++) {
             png_read_rows(this->png_ptr(), &fSrcRow, png_bytepp_NULL, 1);
         }
         return true;
     }
 
 private:
     SkAutoTMalloc<uint8_t>      fStorage;
     uint8_t*                    fSrcRow;
@@ skipping 10 matching lines @@
         : INHERITED(srcInfo, stream, chunkReader, png_ptr, info_ptr, bitDepth, numberPasses)
         , fHeight(-1)
         , fCanSkipRewind(false)
     {
         SkASSERT(numberPasses != 1);
     }
 
     Result onStartScanlineDecode(const SkImageInfo& dstInfo, const Options& options,
             SkPMColor ctable[], int* ctableCount) override {
         if (!conversion_possible(dstInfo, this->getInfo())) {
-            return kInvalidConversion;    
+            return kInvalidConversion;
         }
 
         const Result result = this->initializeSwizzler(dstInfo, options, ctable,
                                                        ctableCount);
         if (result != kSuccess) {
             return result;
         }
 
         fHeight = dstInfo.height();
         // FIXME: This need not be called on a second call to onStartScanlineDecode.
@@ skipping 108 matching lines @@
     }
 
     if (1 == numberPasses) {
         return new SkPngScanlineDecoder(imageInfo, streamDeleter.detach(), chunkReader,
                                         png_ptr, info_ptr, bitDepth);
     }
 
     return new SkPngInterlacedScanlineDecoder(imageInfo, streamDeleter.detach(), chunkReader,
                                               png_ptr, info_ptr, bitDepth, numberPasses);
 }