SkPDF: Implement Paeth predictor for images.

src/pdf/SkPngPredictors.cpp

Index: src/pdf/SkPngPredictors.cpp
diff --git a/src/pdf/SkPngPredictors.cpp b/src/pdf/SkPngPredictors.cpp
new file mode 100644
index 0000000000000000000000000000000000000000..adc49698aaf593f5edc681d17fc182e4f6fe9e5e
--- /dev/null
+++ b/src/pdf/SkPngPredictors.cpp
@@ -0,0 +1,219 @@
+/*
+ * 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 "SkPngPredictors.h"
+#include "SkTypes.h"
+
+// SkPngPredictors: Implement PNG-style prediction filters on a
+// scanline-by-scanline basis for SkPDF.
+
+// See <https://www.w3.org/TR/PNG/#9Filters> for reference.
+// Where used, a,b,c,x have the same meaning as in the standard.
+
+// "The approach that has by now become standard is known as the
+// minimum sum of absolute differences heuristic and was first
+// proposed by Lee Daniel Crocker in February 1995. In this
+// approach, the filtered bytes are treated as signed [bytes]. The
+// absolute value of each is then summed, and the filter type that
+// produces the smallest sum is chosen."
+
+static int8_t weight(uint8_t x) {
+    return SkTAbs(reinterpret_cast<int8_t&>(x));
+}
+
+// Type:0; Name:None; Filt(x) = Orig(x)
+// BPP == bytes-per-pixel
+// track: iff true, do not write into out; instead calculate "cost" of out.
+template<int BPP, bool track>
+static int none(int width, const uint8_t* prev,
+                const uint8_t* scanline, uint8_t* out) {
+    int64_t w = 0;
+    (void)prev;
+    static_assert(BPP > 0, "");
+    if (track) {
+        const uint8_t* end = &scanline[BPP * width];
+        while (scanline != end) {
+            w += weight(*scanline++);
+        }
+    } else {
+        if (out != scanline) {
+            memcpy(out, scanline, width * BPP);
+        }
+    }
+    return SkToInt(w);
+}
+
+// Type:1; Name:Sub; Filt(x) = Orig(x) - Orig(a)
+template<int BPP, bool track>
+static int sub(int width, const uint8_t* prev,
+               const uint8_t* scanline, uint8_t* out) {
+    static_assert(BPP > 0, "");
+    (void)prev;  // not used
+    int64_t w = 0;  // Use int64: SkToInt will catch overflow in worst case.
+    uint8_t a[BPP]{};  // a = left
+    const uint8_t* end = &scanline[BPP * width];
+    while (scanline != end) {
+        for (int i = 0; i < BPP; ++i) {
+            uint8_t x = *scanline++;
+            uint8_t v = x - a[i];
+            if (track) { w += weight(v); } else { *out++ = v; }
+            a[i] = x;
+        }
+    }
+    return SkToInt(w);
+}
+// Type:2; Name:Up; Filt(x) = Orig(x) - Orig(b)
+template<int BPP, bool track>
+static int up(int width, const uint8_t* prev,
+              const uint8_t* scanline, uint8_t* out) {
+    if (prev) {
+        int64_t w = 0;
+        const uint8_t* end = &scanline[BPP * width];
+        while (scanline != end) {
+            for (int i = 0; i < BPP; ++i) {
+                uint8_t v = *scanline++ - *prev++;
+                if (track) { w += weight(v); } else { *out++ = v; }
+            }
+        }
+        return SkToInt(w);
+    } else {
+        return none<BPP, track>(width, prev, scanline, out);
+    }
+}
+
+// Type:3; Name:Average; Filt(x) = Orig(x) - floor((Orig(a) + Orig(b)) / 2)
+template<int BPP, bool track>
+static int average(int width, const uint8_t* prev,
+                   const uint8_t* scanline, uint8_t* out) {
+    static_assert(BPP > 0, "");
+    int64_t w = 0;
+    const uint8_t* end = &scanline[BPP * width];
+    if (prev) {
+        uint8_t a[BPP]{}; // a = left, b = above
+        while (scanline != end) {
+            for (int i = 0; i < BPP; ++i) {
+                uint8_t x = *scanline++;
+                uint8_t v = x - SkToU8(((int)a[i] + (int)(*prev++)) / 2);
+                if (track) { w += weight(v); } else { *out++ = v; }
+                a[i] = x;
+            }
+        }
+    } else {
+        uint8_t a[BPP]{};
+        while (scanline != end) {
+            for (int i = 0; i < BPP; ++i) {
+                uint8_t x = *scanline++;
+                uint8_t v = x - a[i] / 2;  // average with zero.
+                if (track) { w += weight(v); } else { *out++ = v; }
+                a[i] = x;
+            }
+        }
+    }
+    return SkToInt(w);
+}
+
+// Type:4; Name: Paeth;
+// Filt(x) = Orig(x) - PaethPredictor(Orig(a), Orig(b), Orig(c))
+template<int BPP, bool track>
+static int paeth(int width, const uint8_t* prev, const uint8_t* scanline, uint8_t* out) {
+    static_assert(BPP > 0, "");
+    // a = left, b = above, c = upper left
+    if (!prev) {
+        return sub<BPP, track>(width, prev, scanline, out);
+    }
+    int64_t w = 0;
+    uint8_t a[BPP]{}, c[BPP]{};
+    const uint8_t* end = &scanline[BPP * width];
+    while (scanline != end) {
+        for (int i = 0; i < BPP; ++i) {
+            uint8_t b = *prev++;
+            uint8_t x = *scanline++;
+            int pa = SkTAbs<int>(b - c[i]);
+            int pb = SkTAbs<int>(a[i] - c[i]);
+            int pc = SkTAbs<int>((b - c[i]) + (a[i] - c[i]));
+            uint8_t pred = a[i];
+            if (pb < pa) { pred = b; pa = pb; }
+            if (pc < pa) { pred = c[i];       }
+            uint8_t v = x - pred;
+            if (track) { w += weight(v); } else { *out++ = v; }
+            a[i] = x;
+            c[i] = b;
+        }
+    }
+    return SkToInt(w);
+}
+
+// prev == out is okay.
+// prev can be null.
+// Return the type that is used.
+template<int BPP>
+uint8_t png_encode(int width,
+                   const uint8_t* prev,
+                   const uint8_t* scanline,
+                   uint8_t* out) {
+    int scores[5];
+    scores[0] = none<BPP, true>(width, prev, scanline, nullptr);
+    scores[1] = sub<BPP, true>(width, prev, scanline, nullptr);
+    scores[2] = up<BPP, true>(width, prev, scanline, nullptr);
+    scores[3] = average<BPP, true>(width, prev, scanline, nullptr);
+    scores[4] = paeth<BPP, true>(width, prev, scanline, nullptr);
+    uint8_t best = 0;
+    int best_score = scores[0];
+    for (uint8_t i = 1; i < SK_ARRAY_COUNT(scores); ++i) {
+        if (scores[i] < best_score) {
+            best = i;
+            best_score = scores[i];
+        }
+    }
+    //  9087 === 0
+    //  2346 === 1
+    //  6698 === 2
+    // 12747 === 3
+    //  6216 === 4
+    // SkDebugf("=== %d\n", best);
+    switch (best) {
+        case 0:
+            (void)none<BPP, false>(width, prev, scanline, out);
+            return best;
+        case 1:
+            (void)sub<BPP, false>(width, prev, scanline, out);
+            return best;
+        case 2:
+            (void)up<BPP, false>(width, prev, scanline, out);
+            return best;
+        case 3:
+            (void)average<BPP, false>(width, prev, scanline, out);
+            return best;
+        case 4:
+            (void)paeth<BPP, false>(width, prev, scanline, out);
+            return best;
+    }
+    SkASSERT(false);
+    return 0;
+}
+
+uint8_t SkPngEncode3(int width, const uint8_t* prev,
+                     const uint8_t* scanline, uint8_t* out) {
+    return png_encode<3>(width, prev, scanline, out);
+}
+
+uint8_t SkPngEncode1(int width, const uint8_t* prev,
+                     const uint8_t* scanline, uint8_t* out) {
+    return png_encode<1>(width, prev, scanline, out);
+}
+
+uint8_t SkPaethEncode3(int width, const uint8_t* prev,
+                     const uint8_t* scanline, uint8_t* out) {
+    (void)paeth<3, false>(width, prev, scanline, out);
+    return 4;
+}
+
+uint8_t SkPaethEncode1(int width, const uint8_t* prev,
+                     const uint8_t* scanline, uint8_t* out) {
+    (void)paeth<1, false>(width, prev, scanline, out);
+    return 4;
+}