diff options
author | mtklein <mtklein@chromium.org> | 2016-01-27 13:01:41 -0800 |
---|---|---|
committer | Commit bot <commit-bot@chromium.org> | 2016-01-27 13:01:41 -0800 |
commit | 372d65cc6ee743944a9fb58a734b3f1eb253b015 (patch) | |
tree | bc3d189df4a09d3318eb620bbba86637c50cb421 /src/codec | |
parent | 9ce4110a29b02ae3b95903cfbe0e61f31143e66e (diff) |
sketch hooking into PNG_FILTER_OPTIMIZATIONS
Local timing says this 4-byte Paeth function takes about 0.3x the time the serial libpng code does, dropping from ~10 cycles per byte to ~2.9.
bpp=4 is mainly an easy demo. This approach can work for any bpp up to 16, 1 pixel at a time, at roughly the same cost per pixel. Doing more than 1 pixel at a time is a tricky math problem I have yet to attempt to solve.
Everything here can be trivially downgraded to MMX, supporting bpp up to 8. It seems to be a little slower (~3.5 cycles per byte), but it would make the code compatible with every x86 that can still power on.
I've tried four approaches:
- this way;
- doing things naively in 16-bit;
- a 16-bit version that requires division by 3 (i.e. mulhi_epu16(..., 0x5580) );
- a mostly 8-bit version of the same.
They're all fine, but this one is consistently the fastest I've measured.
I'd be happy to settle on the naive 16-bit version too, which would have a very clear implementation that's only minorly slower than this version. The other two are way more complicated, and would require us to draw some serious ASCII diagrams to explain.
I have learned that the .skp serialization tests (serialize-8888) have a nice side effect of testing the correctness of these filters!
(Since writing the description above, I've bumped things up to {Paeth,Sub,Avg} x { 3 bpp, 4 bpp }.)
BUG=skia:
GOLD_TRYBOT_URL= https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&issue=1573943002
Review URL: https://codereview.chromium.org/1573943002
Diffstat (limited to 'src/codec')
-rw-r--r-- | src/codec/SkPngCodec.cpp | 34 | ||||
-rw-r--r-- | src/codec/SkPngFilters.cpp | 168 | ||||
-rw-r--r-- | src/codec/SkPngFilters.h | 26 |
3 files changed, 220 insertions, 8 deletions
diff --git a/src/codec/SkPngCodec.cpp b/src/codec/SkPngCodec.cpp index 66215a6c73..9691f12d4d 100644 --- a/src/codec/SkPngCodec.cpp +++ b/src/codec/SkPngCodec.cpp @@ -11,11 +11,29 @@ #include "SkBitmap.h" #include "SkMath.h" #include "SkPngCodec.h" +#include "SkPngFilters.h" #include "SkSize.h" #include "SkStream.h" #include "SkSwizzler.h" #include "SkTemplates.h" +#if defined(__SSE2__) + #include "pngstruct.h" + + extern "C" void sk_png_init_filter_functions_sse2(png_structp png, unsigned int bpp) { + if (bpp == 3) { + png->read_filter[PNG_FILTER_VALUE_SUB -1] = sk_sub3_sse2; + png->read_filter[PNG_FILTER_VALUE_AVG -1] = sk_avg3_sse2; + png->read_filter[PNG_FILTER_VALUE_PAETH-1] = sk_paeth3_sse2; + } + if (bpp == 4) { + png->read_filter[PNG_FILTER_VALUE_SUB -1] = sk_sub4_sse2; + png->read_filter[PNG_FILTER_VALUE_AVG -1] = sk_avg4_sse2; + png->read_filter[PNG_FILTER_VALUE_PAETH-1] = sk_paeth4_sse2; + } + } +#endif + /////////////////////////////////////////////////////////////////////////////// // Helper macros /////////////////////////////////////////////////////////////////////////////// @@ -331,8 +349,8 @@ static bool read_header(SkStream* stream, SkPngChunkReader* chunkReader, } 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; @@ -406,7 +424,7 @@ SkCodec::Result SkPngCodec::initializeSwizzler(const SkImageInfo& requestedInfo, 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(); @@ -422,7 +440,7 @@ SkCodec::Result SkPngCodec::initializeSwizzler(const SkImageInfo& requestedInfo, break; case kGray_8_SkColorType: fSrcConfig = SkSwizzler::kGray; - break; + break; case kN32_SkColorType: if (this->getInfo().alphaType() == kOpaque_SkAlphaType) { fSrcConfig = SkSwizzler::kRGB; @@ -433,7 +451,7 @@ SkCodec::Result SkPngCodec::initializeSwizzler(const SkImageInfo& requestedInfo, 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); @@ -624,8 +642,8 @@ public: 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); @@ -656,7 +674,7 @@ public: 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, diff --git a/src/codec/SkPngFilters.cpp b/src/codec/SkPngFilters.cpp new file mode 100644 index 0000000000..115810ea7c --- /dev/null +++ b/src/codec/SkPngFilters.cpp @@ -0,0 +1,168 @@ +/* + * Copyright 2016 Google Inc. + * + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ + +#include "SkPngFilters.h" +#include "SkTypes.h" + +// Functions in this file look at most 3 pixels (a,b,c) to predict the fourth (d). +// They're positioned like this: +// prev: c b +// row: a d +// The Sub filter predicts d=a, Avg d=(a+b)/2, and Paeth predicts d to be whichever +// of a, b, or c is closest to p=a+b-c. (Up also exists, predicting d=b.) + +#if defined(__SSE2__) + + template <int bpp> + static __m128i load(const void* p) { + static_assert(bpp <= 4, ""); + + uint32_t packed; + memcpy(&packed, p, bpp); + return _mm_cvtsi32_si128(packed); + } + + template <int bpp> + static void store(void* p, __m128i v) { + static_assert(bpp <= 4, ""); + + uint32_t packed = _mm_cvtsi128_si32(v); + memcpy(p, &packed, bpp); + } + + template <int bpp> + static void sk_sub_sse2(png_row_infop row_info, png_bytep row, png_const_bytep) { + // The Sub filter predicts each pixel as the previous pixel, a. + // There is no pixel to the left of the first pixel. It's encoded directly. + // That works with our main loop if we just say that left pixel was zero. + __m128i a, d = _mm_setzero_si128(); + + int rb = row_info->rowbytes; + while (rb > 0) { + a = d; d = load<bpp>(row); + d = _mm_add_epi8(d, a); + store<bpp>(row, d); + + row += bpp; + rb -= bpp; + } + } + + template <int bpp> + void sk_avg_sse2(png_row_infop row_info, png_bytep row, png_const_bytep prev) { + // The Avg filter predicts each pixel as the (truncated) average of a and b. + // There's no pixel to the left of the first pixel. Luckily, it's + // predicted to be half of the pixel above it. So again, this works + // perfectly with our loop if we make sure a starts at zero. + const __m128i zero = _mm_setzero_si128(); + __m128i b; + __m128i a, d = zero; + + int rb = row_info->rowbytes; + while (rb > 0) { + b = load<bpp>(prev); + a = d; d = load<bpp>(row ); + + // PNG requires a truncating average here, so sadly we can't just use _mm_avg_epu8... + __m128i avg = _mm_avg_epu8(a,b); + // ...but we can fix it up by subtracting off 1 if it rounded up. + avg = _mm_sub_epi8(avg, _mm_and_si128(_mm_xor_si128(a,b), _mm_set1_epi8(1))); + + d = _mm_add_epi8(d, avg); + store<bpp>(row, d); + + prev += bpp; + row += bpp; + rb -= bpp; + } + } + + // 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)); + } + + template <int bpp> + void sk_paeth_sse2(png_row_infop row_info, png_bytep row, png_const_bytep prev) { + // 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(); + + int rb = row_info->rowbytes; + while (rb > 0) { + c = b; b = load<bpp>(prev); + a = d; d = load<bpp>(row ); + + // We can't express p in 8 bits, but luckily we can use this faux p instead. + // (I have no deep insight here... I just proved this with brute force.) + __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, and pc, + // but it's a little quicker to calculate the correct pa and pb directly, + // and the predictor remains the same. (Again, brute force.) + __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); + store<bpp>(row, d); + + prev += bpp; + row += bpp; + rb -= bpp; + } + } + + void sk_sub3_sse2(png_row_infop row_info, png_bytep row, png_const_bytep prev) { + sk_sub_sse2<3>(row_info, row, prev); + } + void sk_sub4_sse2(png_row_infop row_info, png_bytep row, png_const_bytep prev) { + sk_sub_sse2<4>(row_info, row, prev); + } + + void sk_avg3_sse2(png_row_infop row_info, png_bytep row, png_const_bytep prev) { + sk_avg_sse2<3>(row_info, row, prev); + } + void sk_avg4_sse2(png_row_infop row_info, png_bytep row, png_const_bytep prev) { + sk_avg_sse2<4>(row_info, row, prev); + } + + void sk_paeth3_sse2(png_row_infop row_info, png_bytep row, png_const_bytep prev) { + sk_paeth_sse2<3>(row_info, row, prev); + } + void sk_paeth4_sse2(png_row_infop row_info, png_bytep row, png_const_bytep prev) { + sk_paeth_sse2<4>(row_info, row, prev); + } + +#endif diff --git a/src/codec/SkPngFilters.h b/src/codec/SkPngFilters.h new file mode 100644 index 0000000000..5fc446881c --- /dev/null +++ b/src/codec/SkPngFilters.h @@ -0,0 +1,26 @@ +/* + * Copyright 2016 Google Inc. + * + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ + +#ifndef SkPngFilters_DEFINED +#define SkPngFilters_DEFINED + +#include "png.h" + +// We don't bother specializing Up... +// it's so simple it's usually already perfectly autovectorized. + +// These all require bpp=3 (i.e. RGB). +void sk_sub3_sse2(png_row_infop, png_bytep, png_const_bytep); +void sk_avg3_sse2(png_row_infop, png_bytep, png_const_bytep); +void sk_paeth3_sse2(png_row_infop, png_bytep, png_const_bytep); + +// These all require bpp=4 (i.e. RGBA). +void sk_sub4_sse2(png_row_infop, png_bytep, png_const_bytep); +void sk_avg4_sse2(png_row_infop, png_bytep, png_const_bytep); +void sk_paeth4_sse2(png_row_infop, png_bytep, png_const_bytep); + +#endif//SkPngFilterOpts_DEFINED |