diff --git a/tests/CodecTest.cpp b/tests/CodecTest.cpp
index 12d6ac8..3cd993f 100644
--- a/tests/CodecTest.cpp
+++ b/tests/CodecTest.cpp
@@ -83,6 +83,62 @@
     return rect;
 }
 
+static void test_incremental_decode(skiatest::Reporter* r, SkCodec* codec, const SkImageInfo& info,
+        const SkMD5::Digest& goodDigest) {
+    SkBitmap bm;
+    bm.allocPixels(info);
+    SkAutoLockPixels autoLockPixels(bm);
+
+    REPORTER_ASSERT(r, SkCodec::kSuccess == codec->startIncrementalDecode(info, bm.getPixels(),
+                                                                          bm.rowBytes()));
+
+    REPORTER_ASSERT(r, SkCodec::kSuccess == codec->incrementalDecode());
+
+    compare_to_good_digest(r, goodDigest, bm);
+}
+
+// Test in stripes, similar to DM's kStripe_Mode
+static void test_in_stripes(skiatest::Reporter* r, SkCodec* codec, const SkImageInfo& info,
+                            const SkMD5::Digest& goodDigest) {
+    SkBitmap bm;
+    bm.allocPixels(info);
+    bm.eraseColor(SK_ColorYELLOW);
+
+    const int height = info.height();
+    // Note that if numStripes does not evenly divide height there will be an extra
+    // stripe.
+    const int numStripes = 4;
+
+    if (numStripes > height) {
+        // Image is too small.
+        return;
+    }
+
+    const int stripeHeight = height / numStripes;
+
+    // Iterate through the image twice. Once to decode odd stripes, and once for even.
+    for (int oddEven = 1; oddEven >= 0; oddEven--) {
+        for (int y = oddEven * stripeHeight; y < height; y += 2 * stripeHeight) {
+            SkIRect subset = SkIRect::MakeLTRB(0, y, info.width(),
+                                               SkTMin(y + stripeHeight, height));
+            SkCodec::Options options;
+            options.fSubset = &subset;
+            if (SkCodec::kSuccess != codec->startIncrementalDecode(info, bm.getAddr(0, y),
+                        bm.rowBytes(), &options)) {
+                ERRORF(r, "failed to start incremental decode!\ttop: %i\tbottom%i\n",
+                       subset.top(), subset.bottom());
+                return;
+            }
+            if (SkCodec::kSuccess != codec->incrementalDecode()) {
+                ERRORF(r, "failed incremental decode starting from line %i\n", y);
+                return;
+            }
+        }
+    }
+
+    compare_to_good_digest(r, goodDigest, bm);
+}
+
 template<typename Codec>
 static void test_codec(skiatest::Reporter* r, Codec* codec, SkBitmap& bm, const SkImageInfo& info,
         const SkISize& size, SkCodec::Result expectedResult, SkMD5::Digest* digest,
@@ -191,12 +247,14 @@
     return false;
 }
 
+// FIXME: Break up this giant function
 static void check(skiatest::Reporter* r,
                   const char path[],
                   SkISize size,
                   bool supportsScanlineDecoding,
                   bool supportsSubsetDecoding,
-                  bool supportsIncomplete = true) {
+                  bool supportsIncomplete,
+                  bool supportsNewScanlineDecoding = false) {
 
     SkAutoTDelete<SkStream> stream(resource(path));
     if (!stream) {
@@ -226,12 +284,15 @@
     test_codec(r, codec.get(), bm, info, size, expectedResult, &codecDigest, nullptr);
 
     // Scanline decoding follows.
-    // Need to call startScanlineDecode() first.
-    REPORTER_ASSERT(r, codec->getScanlines(bm.getAddr(0, 0), 1, 0)
-            == 0);
-    REPORTER_ASSERT(r, codec->skipScanlines(1)
-            == 0);
 
+    if (supportsNewScanlineDecoding && !isIncomplete) {
+        test_incremental_decode(r, codec, info, codecDigest);
+        test_in_stripes(r, codec, info, codecDigest);
+    }
+
+    // Need to call startScanlineDecode() first.
+    REPORTER_ASSERT(r, codec->getScanlines(bm.getAddr(0, 0), 1, 0) == 0);
+    REPORTER_ASSERT(r, !codec->skipScanlines(1));
     const SkCodec::Result startResult = codec->startScanlineDecode(info);
     if (supportsScanlineDecoding) {
         bm.eraseColor(SK_ColorYELLOW);
@@ -326,7 +387,7 @@
     }
 
     // SkAndroidCodec tests
-    if (supportsScanlineDecoding || supportsSubsetDecoding) {
+    if (supportsScanlineDecoding || supportsSubsetDecoding || supportsNewScanlineDecoding) {
 
         SkAutoTDelete<SkStream> stream(resource(path));
         if (!stream) {
@@ -383,16 +444,16 @@
 
 DEF_TEST(Codec, r) {
     // WBMP
-    check(r, "mandrill.wbmp", SkISize::Make(512, 512), true, false);
+    check(r, "mandrill.wbmp", SkISize::Make(512, 512), true, false, true);
 
     // WEBP
-    check(r, "baby_tux.webp", SkISize::Make(386, 395), false, true);
-    check(r, "color_wheel.webp", SkISize::Make(128, 128), false, true);
-    check(r, "yellow_rose.webp", SkISize::Make(400, 301), false, true);
+    check(r, "baby_tux.webp", SkISize::Make(386, 395), false, true, true);
+    check(r, "color_wheel.webp", SkISize::Make(128, 128), false, true, true);
+    check(r, "yellow_rose.webp", SkISize::Make(400, 301), false, true, true);
 
     // BMP
-    check(r, "randPixels.bmp", SkISize::Make(8, 8), true, false);
-    check(r, "rle.bmp", SkISize::Make(320, 240), true, false);
+    check(r, "randPixels.bmp", SkISize::Make(8, 8), true, false, true);
+    check(r, "rle.bmp", SkISize::Make(320, 240), true, false, true);
 
     // ICO
     // FIXME: We are not ready to test incomplete ICOs
@@ -400,7 +461,7 @@
     // Decodes an embedded BMP image
     check(r, "color_wheel.ico", SkISize::Make(128, 128), true, false, false);
     // Decodes an embedded PNG image
-    check(r, "google_chrome.ico", SkISize::Make(256, 256), true, false, false);
+    check(r, "google_chrome.ico", SkISize::Make(256, 256), false, false, false, true);
 
     // GIF
     // FIXME: We are not ready to test incomplete GIFs
@@ -410,30 +471,30 @@
     check(r, "randPixels.gif", SkISize::Make(8, 8), true, false, false);
 
     // JPG
-    check(r, "CMYK.jpg", SkISize::Make(642, 516), true, false);
-    check(r, "color_wheel.jpg", SkISize::Make(128, 128), true, false);
+    check(r, "CMYK.jpg", SkISize::Make(642, 516), true, false, true);
+    check(r, "color_wheel.jpg", SkISize::Make(128, 128), true, false, true);
     // grayscale.jpg is too small to test incomplete
     check(r, "grayscale.jpg", SkISize::Make(128, 128), true, false, false);
-    check(r, "mandrill_512_q075.jpg", SkISize::Make(512, 512), true, false);
+    check(r, "mandrill_512_q075.jpg", SkISize::Make(512, 512), true, false, true);
     // randPixels.jpg is too small to test incomplete
     check(r, "randPixels.jpg", SkISize::Make(8, 8), true, false, false);
 
     // PNG
-    check(r, "arrow.png", SkISize::Make(187, 312), true, false, false);
-    check(r, "baby_tux.png", SkISize::Make(240, 246), true, false, false);
-    check(r, "color_wheel.png", SkISize::Make(128, 128), true, false, false);
-    check(r, "half-transparent-white-pixel.png", SkISize::Make(1, 1), true, false, false);
-    check(r, "mandrill_128.png", SkISize::Make(128, 128), true, false, false);
-    check(r, "mandrill_16.png", SkISize::Make(16, 16), true, false, false);
-    check(r, "mandrill_256.png", SkISize::Make(256, 256), true, false, false);
-    check(r, "mandrill_32.png", SkISize::Make(32, 32), true, false, false);
-    check(r, "mandrill_512.png", SkISize::Make(512, 512), true, false, false);
-    check(r, "mandrill_64.png", SkISize::Make(64, 64), true, false, false);
-    check(r, "plane.png", SkISize::Make(250, 126), true, false, false);
-    // FIXME: We are not ready to test incomplete interlaced pngs
-    check(r, "plane_interlaced.png", SkISize::Make(250, 126), true, false, false);
-    check(r, "randPixels.png", SkISize::Make(8, 8), true, false, false);
-    check(r, "yellow_rose.png", SkISize::Make(400, 301), true, false, false);
+    check(r, "arrow.png", SkISize::Make(187, 312), false, false, true, true);
+    check(r, "baby_tux.png", SkISize::Make(240, 246), false, false, true, true);
+    check(r, "color_wheel.png", SkISize::Make(128, 128), false, false, true, true);
+    // half-transparent-white-pixel.png is too small to test incomplete
+    check(r, "half-transparent-white-pixel.png", SkISize::Make(1, 1), false, false, false, true);
+    check(r, "mandrill_128.png", SkISize::Make(128, 128), false, false, true, true);
+    check(r, "mandrill_16.png", SkISize::Make(16, 16), false, false, true, true);
+    check(r, "mandrill_256.png", SkISize::Make(256, 256), false, false, true, true);
+    check(r, "mandrill_32.png", SkISize::Make(32, 32), false, false, true, true);
+    check(r, "mandrill_512.png", SkISize::Make(512, 512), false, false, true, true);
+    check(r, "mandrill_64.png", SkISize::Make(64, 64), false, false, true, true);
+    check(r, "plane.png", SkISize::Make(250, 126), false, false, true, true);
+    check(r, "plane_interlaced.png", SkISize::Make(250, 126), false, false, true, true);
+    check(r, "randPixels.png", SkISize::Make(8, 8), false, false, true, true);
+    check(r, "yellow_rose.png", SkISize::Make(400, 301), false, false, true, true);
 
     // RAW
 // Disable RAW tests for Win32.
@@ -444,97 +505,6 @@
 #endif
 }
 
-// Test interlaced PNG in stripes, similar to DM's kStripe_Mode
-DEF_TEST(Codec_stripes, r) {
-    const char * path = "plane_interlaced.png";
-    SkAutoTDelete<SkStream> stream(resource(path));
-    if (!stream) {
-        SkDebugf("Missing resource '%s'\n", path);
-    }
-
-    SkAutoTDelete<SkCodec> codec(SkCodec::NewFromStream(stream.release()));
-    REPORTER_ASSERT(r, codec);
-
-    if (!codec) {
-        return;
-    }
-
-    switch (codec->getScanlineOrder()) {
-        case SkCodec::kBottomUp_SkScanlineOrder:
-        case SkCodec::kOutOfOrder_SkScanlineOrder:
-            ERRORF(r, "This scanline order will not match the original.");
-            return;
-        default:
-            break;
-    }
-
-    // Baseline for what the image should look like, using N32.
-    const SkImageInfo info = codec->getInfo().makeColorType(kN32_SkColorType);
-
-    SkBitmap bm;
-    bm.allocPixels(info);
-    SkAutoLockPixels autoLockPixels(bm);
-    SkCodec::Result result = codec->getPixels(info, bm.getPixels(), bm.rowBytes());
-    REPORTER_ASSERT(r, result == SkCodec::kSuccess);
-
-    SkMD5::Digest digest;
-    md5(bm, &digest);
-
-    // Now decode in stripes
-    const int height = info.height();
-    const int numStripes = 4;
-    int stripeHeight;
-    int remainingLines;
-    SkTDivMod(height, numStripes, &stripeHeight, &remainingLines);
-
-    bm.eraseColor(SK_ColorYELLOW);
-
-    result = codec->startScanlineDecode(info);
-    REPORTER_ASSERT(r, result == SkCodec::kSuccess);
-
-    // Odd stripes
-    for (int i = 1; i < numStripes; i += 2) {
-        // Skip the even stripes
-        bool skipResult = codec->skipScanlines(stripeHeight);
-        REPORTER_ASSERT(r, skipResult);
-
-        int linesDecoded = codec->getScanlines(bm.getAddr(0, i * stripeHeight), stripeHeight,
-                                     bm.rowBytes());
-        REPORTER_ASSERT(r, linesDecoded == stripeHeight);
-    }
-
-    // Even stripes
-    result = codec->startScanlineDecode(info);
-    REPORTER_ASSERT(r, result == SkCodec::kSuccess);
-
-    for (int i = 0; i < numStripes; i += 2) {
-        int linesDecoded = codec->getScanlines(bm.getAddr(0, i * stripeHeight), stripeHeight,
-                                     bm.rowBytes());
-        REPORTER_ASSERT(r, linesDecoded == stripeHeight);
-
-        // Skip the odd stripes
-        if (i + 1 < numStripes) {
-            bool skipResult = codec->skipScanlines(stripeHeight);
-            REPORTER_ASSERT(r, skipResult);
-        }
-    }
-
-    // Remainder at the end
-    if (remainingLines > 0) {
-        result = codec->startScanlineDecode(info);
-        REPORTER_ASSERT(r, result == SkCodec::kSuccess);
-
-        bool skipResult = codec->skipScanlines(height - remainingLines);
-        REPORTER_ASSERT(r, skipResult);
-
-        int linesDecoded = codec->getScanlines(bm.getAddr(0, height - remainingLines),
-                                     remainingLines, bm.rowBytes());
-        REPORTER_ASSERT(r, linesDecoded == remainingLines);
-    }
-
-    compare_to_good_digest(r, digest, bm);
-}
-
 static void test_invalid_stream(skiatest::Reporter* r, const void* stream, size_t len) {
     // Neither of these calls should return a codec. Bots should catch us if we leaked anything.
     SkCodec* codec = SkCodec::NewFromStream(new SkMemoryStream(stream, len, false));
@@ -677,26 +647,41 @@
         return;
     }
     SkAutoTDelete<SkCodec> decoder(SkCodec::NewFromStream(stream.release()));
+    if (!decoder) {
+        SkDebugf("Missing codec for %s\n", path);
+        return;
+    }
+
+    const SkImageInfo info = decoder->getInfo().makeColorType(kIndex_8_SkColorType);
 
     // This should return kSuccess because kIndex8 is supported.
     SkPMColor colorStorage[256];
     int colorCount;
-    SkCodec::Result result = decoder->startScanlineDecode(
-        decoder->getInfo().makeColorType(kIndex_8_SkColorType), nullptr, colorStorage, &colorCount);
-    REPORTER_ASSERT(r, SkCodec::kSuccess == result);
-    // The rest of the test is uninteresting if kIndex8 is not supported
-    if (SkCodec::kSuccess != result) {
+    SkCodec::Result result = decoder->startScanlineDecode(info, nullptr, colorStorage,
+                                                          &colorCount);
+    if (SkCodec::kSuccess == result) {
+        // This should return kInvalidParameters because, in kIndex_8 mode, we must pass in a valid
+        // colorPtr and a valid colorCountPtr.
+        result = decoder->startScanlineDecode(info, nullptr, nullptr, nullptr);
+        REPORTER_ASSERT(r, SkCodec::kInvalidParameters == result);
+        result = decoder->startScanlineDecode(info);
+        REPORTER_ASSERT(r, SkCodec::kInvalidParameters == result);
+    } else if (SkCodec::kUnimplemented == result) {
+        // New method should be supported:
+        SkBitmap bm;
+        sk_sp<SkColorTable> colorTable(new SkColorTable(colorStorage, 256));
+        bm.allocPixels(info, nullptr, colorTable.get());
+        result = decoder->startIncrementalDecode(info, bm.getPixels(), bm.rowBytes(), nullptr,
+                                                 colorStorage, &colorCount);
+        REPORTER_ASSERT(r, SkCodec::kSuccess == result);
+        result = decoder->startIncrementalDecode(info, bm.getPixels(), bm.rowBytes());
+        REPORTER_ASSERT(r, SkCodec::kInvalidParameters == result);
+    } else {
+        // The test is uninteresting if kIndex8 is not supported
+        ERRORF(r, "Should not call test_invalid_parameters for non-Index8 file: %s\n", path);
         return;
     }
 
-    // This should return kInvalidParameters because, in kIndex_8 mode, we must pass in a valid
-    // colorPtr and a valid colorCountPtr.
-    result = decoder->startScanlineDecode(
-        decoder->getInfo().makeColorType(kIndex_8_SkColorType), nullptr, nullptr, nullptr);
-    REPORTER_ASSERT(r, SkCodec::kInvalidParameters == result);
-    result = decoder->startScanlineDecode(
-        decoder->getInfo().makeColorType(kIndex_8_SkColorType));
-    REPORTER_ASSERT(r, SkCodec::kInvalidParameters == result);
 }
 
 DEF_TEST(Codec_Params, r) {
@@ -1012,3 +997,91 @@
 
     REPORTER_ASSERT(r, !codec);
 }
+
+// Only rewinds up to a limit.
+class LimitedRewindingStream : public SkStream {
+public:
+    static SkStream* Make(const char path[], size_t limit) {
+        SkStream* stream = resource(path);
+        if (!stream) {
+            return nullptr;
+        }
+        return new LimitedRewindingStream(stream, limit);
+    }
+
+    size_t read(void* buffer, size_t size) override {
+        const size_t bytes = fStream->read(buffer, size);
+        fPosition += bytes;
+        return bytes;
+    }
+
+    bool isAtEnd() const override {
+        return fStream->isAtEnd();
+    }
+
+    bool rewind() override {
+        if (fPosition <= fLimit && fStream->rewind()) {
+            fPosition = 0;
+            return true;
+        }
+
+        return false;
+    }
+
+private:
+    SkAutoTDelete<SkStream> fStream;
+    const size_t            fLimit;
+    size_t                  fPosition;
+
+    LimitedRewindingStream(SkStream* stream, size_t limit)
+        : fStream(stream)
+        , fLimit(limit)
+        , fPosition(0)
+    {
+        SkASSERT(fStream);
+    }
+};
+
+DEF_TEST(Codec_fallBack, r) {
+    // SkAndroidCodec needs to be able to fall back to scanline decoding
+    // if incremental decoding does not work. Make sure this does not
+    // require a rewind.
+
+    // Formats that currently do not support incremental decoding
+    auto files = {
+            "box.gif",
+            "CMYK.jpg",
+            "color_wheel.ico",
+            "mandrill.wbmp",
+            "randPixels.bmp",
+            };
+    for (auto file : files) {
+        SkStream* stream = LimitedRewindingStream::Make(file, 14);
+        if (!stream) {
+            SkDebugf("Missing resources (%s). Set --resourcePath.\n", file);
+            return;
+        }
+
+        SkAutoTDelete<SkCodec> codec(SkCodec::NewFromStream(stream));
+        if (!codec) {
+            ERRORF(r, "Failed to create codec for %s,", file);
+            continue;
+        }
+
+        SkImageInfo info = codec->getInfo().makeColorType(kN32_SkColorType);
+        SkBitmap bm;
+        bm.allocPixels(info);
+
+        if (SkCodec::kUnimplemented != codec->startIncrementalDecode(info, bm.getPixels(),
+                bm.rowBytes())) {
+            ERRORF(r, "Is scanline decoding now implemented for %s?", file);
+            continue;
+        }
+
+        // Scanline decoding should not require a rewind.
+        SkCodec::Result result = codec->startScanlineDecode(info);
+        if (SkCodec::kSuccess != result) {
+            ERRORF(r, "Scanline decoding failed for %s with %i", file, result);
+        }
+    }
+}