Add support for multiple frames in SkCodec

include/codec/SkCodec.h

Index: include/codec/SkCodec.h
diff --git a/include/codec/SkCodec.h b/include/codec/SkCodec.h
index 363347dd72c08f0e05f97433bf9a5da473df05ea..be01c63bf154a924f99126aa8e936d9d31c20066 100644
--- a/include/codec/SkCodec.h
+++ b/include/codec/SkCodec.h
@@ -244,6 +244,8 @@ public:
         Options()
             : fZeroInitialized(kNo_ZeroInitialized)

[msarett, 2016/09/21 22:23:48]

I dislike having this option.  Obviously unrelated to your CL, but I'd like to
think about if we can delete it.

[scroggo, 2016/09/22 16:46:43]

It's certainly awkward to have both fZeroInitialized and fHasPriorFrame, since
they're certainly not both true.

But Android relies on this feature to greatly reduce their memory footprint. I
think we're stuck with this until b/11657454 is solved. (Unless Android just
gets so much more memory that it doesn't matter anymore. Although I suspect
devices with more memory will also have higher resolution screens, for which
they'll use even larger assets with more empty space. And I think on AndroidOne
etc we're still targeting devices with lower memory anyway.)

             , fSubset(NULL)
+            , fFrameIndex(0)

[msarett, 2016/09/21 22:23:48]

I think I might prefer it if all of the "multi-frame" stuff was kept together
somehow - maybe a struct inside this struct?

[scroggo, 2016/09/22 16:46:42]

I considered that, but I'm not sure whether it's better or worse. PS 3 tries it
out. Let me know what you think.

+            , fHasPriorFrame(false)
         {}

[msarett, 2016/09/21 22:23:48]

While I'm nitting on the Options object, here's another thought.  This seems to
hold all kinds of specialized things (which I think is necessary/fine) - but it
makes me think that the colorPtr and colorCountPtr also belong here (since they
are also specialized things).

[scroggo, 2016/09/22 16:46:43]

Yeah, we put those in the AndroidOptions object as an experiment, and I think we
liked that way of doing it. We just haven't followed through and done that here.

 
         ZeroInitialized fZeroInitialized;
@@ -265,6 +267,30 @@ public:
          *  to getScanlines().
          */
         SkIRect*        fSubset;
+
+        /**
+         *  For multiframe images, this represents the frame to decode.
+         *
+         *  Ignored by single frame images.
+         */
+        size_t          fFrameIndex;
+
+        /**
+         *  If true, the dst already contains the prior frame.
+         *
+         *  Only meaningful for multiframe images. If fFrameIndex needs to be
+         *  blended with a prior frame (as reported by
+         *  getRequiredFrame(fFrameIndex)), the client can set this to either
+         *  true or false:
+         *
+         *  true means that the prior frame is already in the dst, and this
+         *  codec only needs to decode fFrameIndex and blend it with the dst.
+         *
+         *  false means that the dst is uninitialized, so this codec needs to
+         *  first decode the prior frame (which in turn may need to decode its
+         *  prior frame).
+         */
+        bool            fHasPriorFrame;

[cblume, 2016/09/22 01:08:47]

I am curious about the design of this.

As I understand it, dst is an in/out param when fHasPriorFrame is true. So I
assume it will overwrite the contents.

However, gif has a dispose method which is effectively "display and discard". To
give an example, suppose:
frame 8 is our keyframe
frame 9 depends on 8, has display and discard
--So we clobber the contents of 8 with the contents of 9
frame 10 depends on 8, since 9 was discarded
--But we clobbered frame 8...

To get around this, we would have to make a copy of our keyframe.

This might be fine.

We have no way of knowing how much of the next frame will be clobbered so we
could end up doing a large copy just to replace most of it. In that case, it
might be better to have separate in and out params and let the decoder do the
copy as needed.

However, maybe the copy is fast enough that it would be better to copy and
clobber anyway.

[cblume, 2016/09/22 01:42:19]

Adding to this:
If we are still downloading the image and do not know if frame 8 will be used
again, we need that copy.

But if we have the frame information in advance or are after the first animation
cycle, we may actually know that frame 8 will never be used again. Imagine frame
11 is a new full-image keyframe.

In that case, it would be perhaps be okay to clobber frame 8 if we knew we would
want to purge it afterwords anyway.

[scroggo, 2016/09/22 16:46:43]

Agreed.

[scroggo, 2016/09/22 16:46:43]

That is correct.
Someone has to make a copy. Either the codec or the client. A goal of this API
is to leave caching decisions up to the client, and I think this falls into that
area. If the client does not want to continue caching frame 8, they can provide
8 as the dst. If they do want to keep it, they need to make a copy.
That's a good counterpoint.
I think it makes the API a little more complicated (and asks more of the codec),
but maybe it's worth it if it speeds things up. One aspect to consider - if the
client does *not* want to keep caching frame 8, and asks for 9 which depends on
8, they'll need to pass 8 to the codec. If we want to avoid the copy in that
case, I think we'll need to do the following:

The client passes 8 as an in/out parameter. This is similar the current patch
set, but it's inconsistent with how the client uses the API when they want to
continue caching 8 (8 as in parameter, 9 as out parameter)
We also have to consider how often it happens, and how much we're clobbering
versus keeping.

[cblume, 2016/09/22 21:29:02]

I agree with what you are saying. Good thinking.

If the next frame's info is ready, the client can ask about the update rect.
Actually, the client would also need to query the dispose method of that frame.

With dispose method + frame update rect, the client would know whether or not it
needs to copy. In which case, I think I agree that the client should be
responsible for copying.

[scroggo, 2016/09/23 15:53:15]

My preference would be to hide the dispose method + frame update rect until we
determine that there's a speed benefit to skipping the copy. (That said, it's
not that hard to expose it.)

[cblume, 2016/09/23 19:15:45]

I agree. We can cross that bridge if it becomes necessary. Until then, it is
needlessly overengineering.

     };
 
     /**
@@ -566,6 +592,40 @@ public:
      */
     int outputScanline(int inputScanline) const;
 
+    /**
+     *  Return the number of frames in the image.
+     *
+     *  May require reading through the stream to determine the number of
+     *  frames.
+     *
+     *  As such, future decoding calls may require a rewind.
+     */
+    size_t getFrameCount() {

[msarett, 2016/09/21 22:23:48]

Can we get away with not having this?  Seems like it allows the client to make
us do a bunch of extra work up front.  Maybe it's something they need to know
though...

[cblume, 2016/09/22 01:08:47]

In the case of gif and apng, we won't know in advance anyway.
If a buffer comes in that isn't the full image, we won't know if there are more
frames coming in the next buffer.

We could simply have this return an error code that specifies it isn't yet
known. But perhaps a better option would be let the client know "Here is how
many frames we are aware of so far. But we don't yet have the entire image
data." Maybe this can be achieved by having a separate bool isImageComplete() or
some such.


That said, from a client perspective it would be very helpful to know frame
count and dependency information prior to actually displaying that frame. Until
I know which frames are valuable to cache, I would be forced to defensively
cache them all.

Pulling out the metadata early would be useful to me.

[cblume, 2016/09/22 01:42:19]

Correcting myself:
We could still be wise about which frames we cache as we go. We can't be *as*
wise. But we don't need to defensively cache them all.

If we get the metadata as we go, we can be reasonable about what frames we want
to keep around for next loop through the animation.

[joostouwerling, 2016/09/22 15:43:16]

For apng, the acTL chunk with the number of frames appears before the full image
buffer so it would not be very expensive to implement this (please correct me if
I'm wrong). Does not change the arguments for gif, though. 

[scroggo, 2016/09/22 16:46:42]

FWIW, my initial design (patch set 1, which I worked on a long time ago, and
plays with some other ideas) did not have this method. You just queried for the
frames in order (or not, if you want...), and when you ask for a frame out of
bounds it returns false.

As Chris states in his response, it sounds like it is useful to know this ahead
of time. The downside is that we need to do work upfront (or whenever this
method is called - the client doesn't have to call it!), and then we have to
backtrack in the data to do actual decoding. This is fine with Blink's
SegmentReader, but on Android we may have to copy the input stream (or parts of
it).
I think that's generally the case. An image format could specify how many frames
it has up front (I think some of the ones we support do), but you cannot really
trust that, can you? If it has more or less frames actually in the data, you're
not going to care about the reported value. (We see something similar in BMP,
where the stream reports how long it is, but there are plenty of cases where it
is wrong.)
I don't think an error code would be useful. If we just count them as we go (and
no backtracking), then we won't know until we've decoded all the frames anyway,
so the client can just count.
FWIW, reporting how many frames we're aware of so far is how blink::ImageDecoder
works, and it is how I imagined this method working. (That's not clear from the
comment. I started to update the comment, but it would be confusing because
SkStreams are expected to block until they receive more data. But I think we're
going to have to move off of SkStreams anyway to support progressive/incremental
decoding properly.)
I think really you just want to know whether the codec has seen all the data.
But the client should know that, since they're supplying the data. So I don't
see what the codec has to add that's interesting.

[cblume, 2016/09/22 21:29:02]

Oh man, that is a bummer.

As a client, having the metadata in advance only provides benefit on the first
animation loop. After the first loop I can reuse the metadata.

That said, I understand Android's constraint. I REALLY wish we could lift that.
But this is the hand we are dealt right now.

If it would be easier to not provide this info in advance I am okay with it.
A common-enough case in Chrome is we scroll down to reveal an image. At that
point, our currently behavior is to catch up to where the animation should be.
If the animation looped in that time, we might actually be back at the
beginning.

If we had the metadata in advance, we wouldn't need to decode all the frames
completely to the end just to display the first frame. We could simply get the
frame count and durations.


Even if we were to keep the metadata after the first loop, it would require that
we have gone through the loop. In the case of scrolling down a webpage, we won't
have gone through the loop yet.


Maybe this is something we can consider later, since there are other options:
Maybe we can lift the Android requirement of forward-only reads. Maybe we can
change the catching-up behavior (this one is my preferred method).
Okay, that makes sense.

So as a client I can call this to get the currently-known-frame-count. And also
as a client, I will know whether or not I have provided all of the data to the
decoder.

If we get metadata in advance, the client can know "I have provided all of the
data, this now returns the actual maximum.".

And if we do not read metadata in advance, the client can perhaps request the
frame count before decoding the next frame. That way we would know there is a
next frame vs. we are looping. This would require Sk*Codec to check for a next
frame every time it decodes a frame. Is this good?
Yeah, I guess you are right. Good call.

[scroggo, 2016/09/23 15:53:15]

It might be easier not to provide the metadata up front, but I'm not convinced
it's a good decision. As you say, we'll have that data the second time through
the loop, but the first time through the loop we won't know anything about frame
dependencies. So the client won't be able to make any decisions about caching.
So they might save frames that they don't want to (seems bad on a page with lots
of animated gifs), or they might discard frames they ought to save (which means
the second loop, which you'd expect to run more smoothly, might have hiccups?).

Not providing the meta data upfront also makes providing the required frame more
awkward. The client would need to know the disposal method. And you could
imagine a bad client providing the wrong prior frame. Maybe that's not so bad
though.
That seems like a strong argument for getting the metadata up front.
In order to do that, I think we'd need a new API. (To be fair, we need a new API
to support animated GIF anyway.) The current decoding calls take a Java
InputStream, which cannot necessarily rewind. We can always copy the input,
though - that's what we do for BitmapRegionDecoder. And if Android wants to be
able to loop, copying the input would allow them to purge the Bitmaps and
re-decode - which could be cheaper than holding onto the Bitmaps.
What do you think the catching-up behavior should be? Will that make us
different from other browsers?
It sounds like what you really want to know is whether there is another frame,
not what the frame count is. But that would mean reading ahead in the stream
anyway. I suppose it would be less, so it would be cheaper than reading through
the whole stream.

[cblume, 2016/09/23 19:15:45]

An alternative would be if Chrome changed its catching-up behavior. I would like
to do this either way. I'll explain more below.
The current browser catch-up landscape is:

FF desktop: Catches up
FF mobile: Catches up
Safari desktop: Catches up
Safari mobile: Does not catch up
Edge desktop: Does not catch up
Edge mobile: I don't have a Windows phone to try. But since desktop doesn't,
I'll guess mobile doesn't either.

If we did not catch up, when we scroll down and reveal an image we could simply
start at the beginning of the animation. Similarly, when an image is scrolled
out of view and back into view, we can essentially "pause" the animation and
resume where we left off. The fastest code is no code, ya know? :D

Currently, every time we need to catch-up an animation we have burn a serious
amount of cpu and battery to churn through several frames. Worse, this is
effectively unbounded.

Another benefit is say we have a.gif in the DOM. Then a second later, we add a
new img tag to the DOM containing a.gif as well. We would need to maintain these
two images out of sync with each other since their start times are different.
But if we don't enforce the time-since-added-to-DOM, we could keep them on the
same frame and half our cache. Once again, you can have an effectively unlimited
number of a.gif images in your page all starting at different times.

Given that some other browsers already do this, I feel silly NOT doing it.

But just to be clear, we cannot ALWAYS keep images on the same frame:
https://crbug.com/527842
Yeah, you are right. I only need to know if there is a next frame.

When I read frame N, maybe the header for frame N+1 is immediately after? Maybe
it can be included as part of the read for frame N (and cached so we can query
if there is a next frame)?

[scroggo, 2016/09/23 21:15:00]

Those sound like good reasons to change the catchup behavior, especially if
other browsers do not agree on the right answer. I had thought our motivation
was that a page may have multiple GIFs that the designer expects to stay in
sync. I don't know whether that's a common use case, and it sounds like it won't
work on all browsers anyway, so maybe that's not a good motivation.
Essentially. (see [1]) It is possible there are other blocks in between, but
those look to be comments (we ignore) or another block without image data. So we
could go ahead and parse those.

[1]
http://giflib.sourceforge.net/whatsinagif/bits_and_bytes.html#logical_screen_...
That's an interesting idea. So the client asks for frame N, and the codec
returns frame N *and* the information about N + 1, specifically:
- does N + 1 exist
- what is the required frame for N + 1

But I can imagine a case where it's awkward:
- Codec has enough data to decode just N frames (again, the client knows it's
not the full data)
- Decoding frame N reports that N + 1 does not exist
- Client knows that there *may be* more frames, and supplies more data
- How does the client determine the true nature of N + 1? (does it exist,
required frame)
(maybe your answer is down below)
What would that API look like? A couple of options:

- struct FrameData nextFrameData(); (where FrameData contains required frame,
animation time perhaps, etc)
I do not like this one because it puts some more state into the codec (what is
the "next" frame?)

- struct FrameData getFrameData(size_t index);
This looks like it might read ahead to an arbitrary frame. If we implement it
that way, we might as well implement getFrameCount (as in patch set 2) or
vector<FrameData> getFrameData() (as in patch set 6). If we do not, it raises
questions about what we would return if the client tries to read ahead.

[cblume, 2016/09/23 23:31:32]

Oh no no. I didn't mean that the API changes. I meant that internally, in
Sk*Codec, reading a frame would also read in enough of the next frame's header
(if available, you are right) to allow us to query that info.

I was under the impression that if Sk*Codec doesn't make a copy of the data and
only reads forward, requesting a frame is the only thing that would advance the
read. Maybe I was understanding this incorrectly.
I also don't like "next" frame for that exact reason - it forces SkCodec to keep
state.
Oh. You are right.
I was thinking something like struct FrameData getFrameData(size_t index);
You are right that it seems like you could pass an arbitrary index which might
not have been read yet.
And even if it was the next frame index, the client may not have provided enough
data for it to be available.


All of this makes me feel more and more like we should read the metadata in
advance.


I think I like the vector<frameInfo> getFrameInfo() if we are allowed to read
the metadata in advance. As a client, I will know this is all the frame info we
are aware of so far.

[scroggo, 2016/09/26 15:51:43]

+1

+        return this->onGetFrameCount();
+    }
+
+    // The required frame for an independent frame is marked as
+    // kIndependentFrame.
+    static constexpr size_t kIndependentFrame = static_cast<size_t>(-1);
+
+    /**
+     *  For a multiframed image, return the image that frame |index| needs to
+     *  be blended with.
+     *
+     *  If the frame needs no blending, return kIndependentFrame.
+     */
+    size_t getRequiredFrame(size_t index) {
+        return this->onGetRequiredFrame(index);
+    }
+
+    /**
+     *  For a multiframed image, return the number of 1/100 seconds to
+     *  show frame |index|.
+     */
+    size_t getFrameDuration(size_t index) {
+        return this->onGetFrameDuration(index);
+    }
+
 protected:
     /**
      *  Takes ownership of SkStream*
@@ -706,6 +766,18 @@ protected:
 
     virtual int onOutputScanline(int inputScanline) const;
 
+    virtual size_t onGetFrameCount() {
+        return 1;
+    }
+
+    virtual size_t onGetRequiredFrame(size_t) {
+        return kIndependentFrame;
+    }
+
+    virtual size_t onGetFrameDuration(size_t) {
+        return 0;
+    }
+
     /**
      *  Used for testing with qcms.
      *  FIXME: Remove this when we are done comparing with qcms.