diff mbox

[FFmpeg-devel,1/2] Revert "avcodec/qtrle: Do not output duplicated frames on insufficient input"

Message ID 20190505185109.20957-1-cus@passwd.hu
State Accepted
Commit 8b71cc3363b5d5b01a56f334e8b6318374192076
Headers show

Commit Message

Marton Balint May 5, 2019, 6:51 p.m. UTC
This reverts commit a9dacdeea6168787a142209bd19fdd74aefc9dd6.

I don't think it is a good idea to drop frames from CFR input just because they
are duplicated, that can cause issues for API users expecting CFR input. Also
it can cause issues at the end of file, if the last frame is a duplicated
frame.

Fixes ticket #7880.

Signed-off-by: Marton Balint <cus@passwd.hu>
---
 libavcodec/qtrle.c        |  12 ++---
 tests/ref/fate/qtrle-8bit | 109 ++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 115 insertions(+), 6 deletions(-)

Comments

Carl Eugen Hoyos May 5, 2019, 6:57 p.m. UTC | #1
Am So., 5. Mai 2019 um 20:51 Uhr schrieb Marton Balint <cus@passwd.hu>:
>
> This reverts commit a9dacdeea6168787a142209bd19fdd74aefc9dd6.
>
> I don't think it is a good idea to drop frames from CFR input just because they
> are duplicated, that can cause issues for API users expecting CFR input. Also
> it can cause issues at the end of file, if the last frame is a duplicated
> frame.

> Fixes ticket #7880.

I am sure that this issue is reproducible with other codecs so I
would prefer a solution in ffmpeg.

Carl Eugen
Hendrik Leppkes May 5, 2019, 7:36 p.m. UTC | #2
On Sun, May 5, 2019 at 8:51 PM Marton Balint <cus@passwd.hu> wrote:
>
> This reverts commit a9dacdeea6168787a142209bd19fdd74aefc9dd6.
>
> I don't think it is a good idea to drop frames from CFR input just because they
> are duplicated, that can cause issues for API users expecting CFR input. Also
> it can cause issues at the end of file, if the last frame is a duplicated
> frame.
>
> Fixes ticket #7880.
>

qtrle is not the only codec such a change was applied to, and I've in
the past objected to this class of changes without much support.
"Security" arguments were used to squat any counter-argument.

- Hendrik
Michael Niedermayer May 6, 2019, 10:34 p.m. UTC | #3
On Sun, May 05, 2019 at 08:51:08PM +0200, Marton Balint wrote:
> This reverts commit a9dacdeea6168787a142209bd19fdd74aefc9dd6.
> 
> I don't think it is a good idea to drop frames from CFR input just because they
> are duplicated, that can cause issues for API users expecting CFR input. Also
> it can cause issues at the end of file, if the last frame is a duplicated
> frame.
> 
> Fixes ticket #7880.
> 
> Signed-off-by: Marton Balint <cus@passwd.hu>
> ---
>  libavcodec/qtrle.c        |  12 ++---
>  tests/ref/fate/qtrle-8bit | 109 ++++++++++++++++++++++++++++++++++++++++++++++
>  2 files changed, 115 insertions(+), 6 deletions(-)

This change would make the decoder quite a bit slower. It also would make 
encoding the output harder.
For example motion estimation would be run over unchanged frames even when
no cfr is wanted.

Also if one for consistency wants every decoder to not drop duplicated things
that will cause some major problems in other decoders.
Iam thinking of MPEG2 here, where the duplication is at a field level
perfectly progressive material would be turned into some mess with field
repetition in that case. Again undoing that in a subsequent stage would be
quite a bit harder and wastefull

so my oppinion is that its better to produce duplicated things only when
needed and not always and hardcoded in the decoder.

Thanks

[...]
Hendrik Leppkes May 6, 2019, 11:39 p.m. UTC | #4
On Tue, May 7, 2019 at 12:34 AM Michael Niedermayer
<michael@niedermayer.cc> wrote:
>
> On Sun, May 05, 2019 at 08:51:08PM +0200, Marton Balint wrote:
> > This reverts commit a9dacdeea6168787a142209bd19fdd74aefc9dd6.
> >
> > I don't think it is a good idea to drop frames from CFR input just because they
> > are duplicated, that can cause issues for API users expecting CFR input. Also
> > it can cause issues at the end of file, if the last frame is a duplicated
> > frame.
> >
> > Fixes ticket #7880.
> >
> > Signed-off-by: Marton Balint <cus@passwd.hu>
> > ---
> >  libavcodec/qtrle.c        |  12 ++---
> >  tests/ref/fate/qtrle-8bit | 109 ++++++++++++++++++++++++++++++++++++++++++++++
> >  2 files changed, 115 insertions(+), 6 deletions(-)
>
> This change would make the decoder quite a bit slower. It also would make
> encoding the output harder.
> For example motion estimation would be run over unchanged frames even when
> no cfr is wanted.

This is simple:
There is X input packets, any other decoder outputs X output frames.
FFmpeg outputs Y output frames (where Y < X). How can this be correct
decoding?

If you want to lesten the burden of static frames, a filter to detect
duplicates and make a stream VFR is what you should suggest, not
making decoders act "unexpectedly".

>
> Also if one for consistency wants every decoder to not drop duplicated things
> that will cause some major problems in other decoders.
> Iam thinking of MPEG2 here, where the duplication is at a field level
> perfectly progressive material would be turned into some mess with field
> repetition in that case. Again undoing that in a subsequent stage would be
> quite a bit harder and wastefull
>

There is quite a fundamental difference between CFR codecs where we
end up not generating output for an input packet just because we feel
like it, and the thought of somehow interpreting field repeat
metadata. That just smells like deflection, lets not go there.

- Hendrik
Hendrik Leppkes May 6, 2019, 11:42 p.m. UTC | #5
On Tue, May 7, 2019 at 1:39 AM Hendrik Leppkes <h.leppkes@gmail.com> wrote:
>
> On Tue, May 7, 2019 at 12:34 AM Michael Niedermayer
> <michael@niedermayer.cc> wrote:
> >
> > On Sun, May 05, 2019 at 08:51:08PM +0200, Marton Balint wrote:
> > > This reverts commit a9dacdeea6168787a142209bd19fdd74aefc9dd6.
> > >
> > > I don't think it is a good idea to drop frames from CFR input just because they
> > > are duplicated, that can cause issues for API users expecting CFR input. Also
> > > it can cause issues at the end of file, if the last frame is a duplicated
> > > frame.
> > >
> > > Fixes ticket #7880.
> > >
> > > Signed-off-by: Marton Balint <cus@passwd.hu>
> > > ---
> > >  libavcodec/qtrle.c        |  12 ++---
> > >  tests/ref/fate/qtrle-8bit | 109 ++++++++++++++++++++++++++++++++++++++++++++++
> > >  2 files changed, 115 insertions(+), 6 deletions(-)
> >
> > This change would make the decoder quite a bit slower. It also would make
> > encoding the output harder.
> > For example motion estimation would be run over unchanged frames even when
> > no cfr is wanted.
>
> This is simple:
> There is X input packets, any other decoder outputs X output frames.
> FFmpeg outputs Y output frames (where Y < X). How can this be correct
> decoding?
>
> If you want to lesten the burden of static frames, a filter to detect
> duplicates and make a stream VFR is what you should suggest, not
> making decoders act "unexpectedly".
>
> >
> > Also if one for consistency wants every decoder to not drop duplicated things
> > that will cause some major problems in other decoders.
> > Iam thinking of MPEG2 here, where the duplication is at a field level
> > perfectly progressive material would be turned into some mess with field
> > repetition in that case. Again undoing that in a subsequent stage would be
> > quite a bit harder and wastefull
> >
>
> There is quite a fundamental difference between CFR codecs where we
> end up not generating output for an input packet just because we feel
> like it, and the thought of somehow interpreting field repeat
> metadata. That just smells like deflection, lets not go there.
>

Also since you talk about making a "mess", this class of changes makes
quite a mess out of perfectly CFR material, to use your own
formulation. :)

- Hendrik
Marton Balint May 7, 2019, 12:03 a.m. UTC | #6
On Tue, 7 May 2019, Michael Niedermayer wrote:

> On Sun, May 05, 2019 at 08:51:08PM +0200, Marton Balint wrote:
>> This reverts commit a9dacdeea6168787a142209bd19fdd74aefc9dd6.
>>
>> I don't think it is a good idea to drop frames from CFR input just because they
>> are duplicated, that can cause issues for API users expecting CFR input. Also
>> it can cause issues at the end of file, if the last frame is a duplicated
>> frame.
>>
>> Fixes ticket #7880.
>>
>> Signed-off-by: Marton Balint <cus@passwd.hu>
>> ---
>>  libavcodec/qtrle.c        |  12 ++---
>>  tests/ref/fate/qtrle-8bit | 109 ++++++++++++++++++++++++++++++++++++++++++++++
>>  2 files changed, 115 insertions(+), 6 deletions(-)
>
> This change would make the decoder quite a bit slower.

I guess that can be easily fixed by only copying the buffer if it really 
is a different frame.

> It also would make encoding the output harder.
> For example motion estimation would be run over unchanged frames even when
> no cfr is wanted.

The performance penalty is much more acceptable to me than the issue 
described in the ticket. Do you see a straightforward way to fix it 
other than reverting?

>
> Also if one for consistency wants every decoder to not drop duplicated things
> that will cause some major problems in other decoders.
> Iam thinking of MPEG2 here, where the duplication is at a field level
> perfectly progressive material would be turned into some mess with field
> repetition in that case. Again undoing that in a subsequent stage would be
> quite a bit harder and wastefull
>
> so my oppinion is that its better to produce duplicated things only when
> needed and not always and hardcoded in the decoder.

The problem is that you are creating VFR from CFR behind the scenes even 
for files which are not meant to be VFR, so people don't expect to get VFR 
from them. There can be use cases where VFR generation is really 
beneficial, but it should not be the default IMHO. VFR is always more 
problematic, yes we mostly handle it, but not without issues here and 
there.

Regards,
Marton
Michael Niedermayer May 7, 2019, 10:43 p.m. UTC | #7
On Tue, May 07, 2019 at 02:03:22AM +0200, Marton Balint wrote:
> 
> 
> On Tue, 7 May 2019, Michael Niedermayer wrote:
> 
> >On Sun, May 05, 2019 at 08:51:08PM +0200, Marton Balint wrote:
> >>This reverts commit a9dacdeea6168787a142209bd19fdd74aefc9dd6.
> >>
> >>I don't think it is a good idea to drop frames from CFR input just because they
> >>are duplicated, that can cause issues for API users expecting CFR input. Also
> >>it can cause issues at the end of file, if the last frame is a duplicated
> >>frame.
> >>
> >>Fixes ticket #7880.
> >>
> >>Signed-off-by: Marton Balint <cus@passwd.hu>
> >>---
> >> libavcodec/qtrle.c        |  12 ++---
> >> tests/ref/fate/qtrle-8bit | 109 ++++++++++++++++++++++++++++++++++++++++++++++
> >> 2 files changed, 115 insertions(+), 6 deletions(-)
> >
> >This change would make the decoder quite a bit slower.
> 
> I guess that can be easily fixed by only copying the buffer if it really is
> a different frame.
> 
> >It also would make encoding the output harder.
> >For example motion estimation would be run over unchanged frames even when
> >no cfr is wanted.
> 
> The performance penalty is much more acceptable to me than the issue
> described in the ticket. Do you see a straightforward way to fix it other
> than reverting?

decoders can in general have frames at the end which need to be flushed
out. For example IPB mpeg1/2/4/...
In the same way the decoder could output a last frame representing the end
exactly

[...]
Michael Niedermayer May 8, 2019, 10:58 p.m. UTC | #8
On Tue, May 07, 2019 at 01:39:44AM +0200, Hendrik Leppkes wrote:
> On Tue, May 7, 2019 at 12:34 AM Michael Niedermayer
> <michael@niedermayer.cc> wrote:
> >
> > On Sun, May 05, 2019 at 08:51:08PM +0200, Marton Balint wrote:
> > > This reverts commit a9dacdeea6168787a142209bd19fdd74aefc9dd6.
> > >
> > > I don't think it is a good idea to drop frames from CFR input just because they
> > > are duplicated, that can cause issues for API users expecting CFR input. Also
> > > it can cause issues at the end of file, if the last frame is a duplicated
> > > frame.
> > >
> > > Fixes ticket #7880.
> > >
> > > Signed-off-by: Marton Balint <cus@passwd.hu>
> > > ---
> > >  libavcodec/qtrle.c        |  12 ++---
> > >  tests/ref/fate/qtrle-8bit | 109 ++++++++++++++++++++++++++++++++++++++++++++++
> > >  2 files changed, 115 insertions(+), 6 deletions(-)
> >
> > This change would make the decoder quite a bit slower. It also would make
> > encoding the output harder.
> > For example motion estimation would be run over unchanged frames even when
> > no cfr is wanted.
> 
> This is simple:
> There is X input packets, any other decoder outputs X output frames.
> FFmpeg outputs Y output frames (where Y < X). How can this be correct
> decoding?
> 
> If you want to lesten the burden of static frames, a filter to detect
> duplicates and make a stream VFR is what you should suggest, not
> making decoders act "unexpectedly".
> 

> >
> > Also if one for consistency wants every decoder to not drop duplicated things
> > that will cause some major problems in other decoders.
> > Iam thinking of MPEG2 here, where the duplication is at a field level
> > perfectly progressive material would be turned into some mess with field
> > repetition in that case. Again undoing that in a subsequent stage would be
> > quite a bit harder and wastefull
> >
> 
> There is quite a fundamental difference between CFR codecs where we
> end up not generating output for an input packet just because we feel
> like it, and the thought of somehow interpreting field repeat
> metadata. That just smells like deflection, lets not go there.

in ISO/IEC 13818-2: 1995 (E), repeat_first_field is part of the picture coding extension,
if its removed it will no longer decode. Iam not sure calling this metadata
is accurate.

also the description of the field is:
    [...]If progressive_sequence is equal to 0 and progressive_frame is equal to 1:
    If this flag is set to 0, the output of the decoding process corresponding to this reconstructed frame
    consists of two fields. The first field (top or bottom field as identified by top_field_first) is followed by the
    other field.
    If it is set to 1, the output of the decoding process corresponding to this reconstructed frame consists of
    three fields. The first field (top or bottom field as identified by top_field_first) is followed by the other
    field, then the first field is repeated. [...]

if you dont return 3 fields you break the normative specification. This speaks
about the "output of the decoding process" not how to interpret the output.

I bring MPEG2 up here because we dont do what the normative spec says
because it doesnt make sense for us. It does make sense if you output on a
analoge interlaced PAL/NTSC screen. It is fundamentally the same as the
CFR case, on one side a interlaced display as factor on the other a output
only capable to handle fixed duration (CFR) frames.

About CFR codecs, the cases this is about are generally input packets that
code the equivalent of "nothing changed". In frameworks that allow only CFR
an implementation would produce a duplicated frame. In frameworks that allow
VFR an implementation can omit the duplicated frame.

[...]
Kieran Kunhya May 9, 2019, 5:55 a.m. UTC | #9
>
> if you dont return 3 fields you break the normative specification. This
> speaks
> about the "output of the decoding process" not how to interpret the output.
>
> I bring MPEG2 up here because we dont do what the normative spec says
> because it doesnt make sense for us. It does make sense if you output on a
> analoge interlaced PAL/NTSC screen. It is fundamentally the same as the
> CFR case, on one side a interlaced display as factor on the other a output
> only capable to handle fixed duration (CFR) frames.
>
> About CFR codecs, the cases this is about are generally input packets that
> code the equivalent of "nothing changed". In frameworks that allow only CFR
> an implementation would produce a duplicated frame. In frameworks that
> allow
> VFR an implementation can omit the duplicated frame.
>

I don't really care about qtrle here but this is not comparable.
If you are a cfr output device, you *know* that you have to duplicate a
field because of the flag that's exported and this duration is clearly
defined.
But with the qtrle patch, you don't know how long the duration of the frame
just returned is.

Kieran
Marton Balint May 14, 2019, 8:31 p.m. UTC | #10
On Wed, 8 May 2019, Michael Niedermayer wrote:

> On Tue, May 07, 2019 at 02:03:22AM +0200, Marton Balint wrote:
>>
>>
>> On Tue, 7 May 2019, Michael Niedermayer wrote:
>>
>>> On Sun, May 05, 2019 at 08:51:08PM +0200, Marton Balint wrote:
>>>> This reverts commit a9dacdeea6168787a142209bd19fdd74aefc9dd6.
>>>>
>>>> I don't think it is a good idea to drop frames from CFR input just because they
>>>> are duplicated, that can cause issues for API users expecting CFR input. Also
>>>> it can cause issues at the end of file, if the last frame is a duplicated
>>>> frame.
>>>>
>>>> Fixes ticket #7880.
>>>>
>>>> Signed-off-by: Marton Balint <cus@passwd.hu>
>>>> ---
>>>> libavcodec/qtrle.c        |  12 ++---
>>>> tests/ref/fate/qtrle-8bit | 109 ++++++++++++++++++++++++++++++++++++++++++++++
>>>> 2 files changed, 115 insertions(+), 6 deletions(-)
>>>
>>> This change would make the decoder quite a bit slower.
>>
>> I guess that can be easily fixed by only copying the buffer if it really is
>> a different frame.
>>
>>> It also would make encoding the output harder.
>>> For example motion estimation would be run over unchanged frames even when
>>> no cfr is wanted.
>>
>> The performance penalty is much more acceptable to me than the issue
>> described in the ticket. Do you see a straightforward way to fix it other
>> than reverting?
>
> decoders can in general have frames at the end which need to be flushed
> out. For example IPB mpeg1/2/4/...
> In the same way the decoder could output a last frame representing the end
> exactly

Yeah, that probably would fix the ticket. However I am still worried 
that it is just a matter of time before somebody reports something else 
that is broken because of VFR and unknown frame duration.

Do you plan on working on fixing the ticket? It is a regression, so 
prefeably it should either be fixed in a reasonable time frame or if 
nobody is willing to do it then we should revert.

The original ossfuzz issue might also be fixed by keeping only the hunk 
which moves ff_reget_buffer down.

Regards,
Marton
Michael Niedermayer May 15, 2019, 6:21 p.m. UTC | #11
On Tue, May 14, 2019 at 10:31:00PM +0200, Marton Balint wrote:
> 
> 
> On Wed, 8 May 2019, Michael Niedermayer wrote:
> 
> >On Tue, May 07, 2019 at 02:03:22AM +0200, Marton Balint wrote:
> >>
> >>
> >>On Tue, 7 May 2019, Michael Niedermayer wrote:
> >>
> >>>On Sun, May 05, 2019 at 08:51:08PM +0200, Marton Balint wrote:
> >>>>This reverts commit a9dacdeea6168787a142209bd19fdd74aefc9dd6.
> >>>>
> >>>>I don't think it is a good idea to drop frames from CFR input just because they
> >>>>are duplicated, that can cause issues for API users expecting CFR input. Also
> >>>>it can cause issues at the end of file, if the last frame is a duplicated
> >>>>frame.
> >>>>
> >>>>Fixes ticket #7880.
> >>>>
> >>>>Signed-off-by: Marton Balint <cus@passwd.hu>
> >>>>---
> >>>>libavcodec/qtrle.c        |  12 ++---
> >>>>tests/ref/fate/qtrle-8bit | 109 ++++++++++++++++++++++++++++++++++++++++++++++
> >>>>2 files changed, 115 insertions(+), 6 deletions(-)
> >>>
> >>>This change would make the decoder quite a bit slower.
> >>
> >>I guess that can be easily fixed by only copying the buffer if it really is
> >>a different frame.
> >>
> >>>It also would make encoding the output harder.
> >>>For example motion estimation would be run over unchanged frames even when
> >>>no cfr is wanted.
> >>
> >>The performance penalty is much more acceptable to me than the issue
> >>described in the ticket. Do you see a straightforward way to fix it other
> >>than reverting?
> >
> >decoders can in general have frames at the end which need to be flushed
> >out. For example IPB mpeg1/2/4/...
> >In the same way the decoder could output a last frame representing the end
> >exactly
> 
> Yeah, that probably would fix the ticket. However I am still worried that it
> is just a matter of time before somebody reports something else that is
> broken because of VFR and unknown frame duration.
> 

> Do you plan on working on fixing the ticket? It is a regression, so
> prefeably it should either be fixed in a reasonable time frame or if nobody
> is willing to do it then we should revert.

ill post a patch that implements the last frame flush idea. 

thx

[...]
diff mbox

Patch

diff --git a/libavcodec/qtrle.c b/libavcodec/qtrle.c
index 2c29547e5a..7367f8688d 100644
--- a/libavcodec/qtrle.c
+++ b/libavcodec/qtrle.c
@@ -455,10 +455,12 @@  static int qtrle_decode_frame(AVCodecContext *avctx,
     int ret, size;
 
     bytestream2_init(&s->g, avpkt->data, avpkt->size);
+    if ((ret = ff_reget_buffer(avctx, s->frame)) < 0)
+        return ret;
 
     /* check if this frame is even supposed to change */
     if (avpkt->size < 8)
-        return avpkt->size;
+        goto done;
 
     /* start after the chunk size */
     size = bytestream2_get_be32(&s->g) & 0x3FFFFFFF;
@@ -472,20 +474,17 @@  static int qtrle_decode_frame(AVCodecContext *avctx,
     /* if a header is present, fetch additional decoding parameters */
     if (header & 0x0008) {
         if (avpkt->size < 14)
-            return avpkt->size;
+            goto done;
         start_line = bytestream2_get_be16(&s->g);
         bytestream2_skip(&s->g, 2);
         height     = bytestream2_get_be16(&s->g);
         bytestream2_skip(&s->g, 2);
         if (height > s->avctx->height - start_line)
-            return avpkt->size;
+            goto done;
     } else {
         start_line = 0;
         height     = s->avctx->height;
     }
-    if ((ret = ff_reget_buffer(avctx, s->frame)) < 0)
-        return ret;
-
     row_ptr = s->frame->linesize[0] * start_line;
 
     switch (avctx->bits_per_coded_sample) {
@@ -546,6 +545,7 @@  static int qtrle_decode_frame(AVCodecContext *avctx,
         memcpy(s->frame->data[1], s->pal, AVPALETTE_SIZE);
     }
 
+done:
     if ((ret = av_frame_ref(data, s->frame)) < 0)
         return ret;
     *got_frame      = 1;
diff --git a/tests/ref/fate/qtrle-8bit b/tests/ref/fate/qtrle-8bit
index 27bb8aad71..8da113d83e 100644
--- a/tests/ref/fate/qtrle-8bit
+++ b/tests/ref/fate/qtrle-8bit
@@ -4,60 +4,169 @@ 
 #dimensions 0: 640x480
 #sar 0: 0/1
 0,          0,          0,        1,   921600, 0x1492e3ed
+0,          1,          1,        1,   921600, 0x1492e3ed
+0,          2,          2,        1,   921600, 0x1492e3ed
 0,          3,          3,        1,   921600, 0x23ef4fc7
+0,          4,          4,        1,   921600, 0x23ef4fc7
 0,          5,          5,        1,   921600, 0xe406d4be
+0,          6,          6,        1,   921600, 0xe406d4be
+0,          7,          7,        1,   921600, 0xe406d4be
 0,          8,          8,        1,   921600, 0x62b8b5a1
+0,          9,          9,        1,   921600, 0x62b8b5a1
 0,         10,         10,        1,   921600, 0x7d8ba674
+0,         11,         11,        1,   921600, 0x7d8ba674
+0,         12,         12,        1,   921600, 0x7d8ba674
 0,         13,         13,        1,   921600, 0xfe666be7
+0,         14,         14,        1,   921600, 0xfe666be7
 0,         15,         15,        1,   921600, 0x721baec0
+0,         16,         16,        1,   921600, 0x721baec0
+0,         17,         17,        1,   921600, 0x721baec0
 0,         18,         18,        1,   921600, 0xc237180a
+0,         19,         19,        1,   921600, 0xc237180a
 0,         20,         20,        1,   921600, 0xf03a7482
+0,         21,         21,        1,   921600, 0xf03a7482
+0,         22,         22,        1,   921600, 0xf03a7482
 0,         23,         23,        1,   921600, 0x5612a391
+0,         24,         24,        1,   921600, 0x5612a391
 0,         25,         25,        1,   921600, 0x9dbcc46a
+0,         26,         26,        1,   921600, 0x9dbcc46a
+0,         27,         27,        1,   921600, 0x9dbcc46a
 0,         28,         28,        1,   921600, 0xa128a5d5
+0,         29,         29,        1,   921600, 0xa128a5d5
 0,         30,         30,        1,   921600, 0x63e0025c
+0,         31,         31,        1,   921600, 0x63e0025c
+0,         32,         32,        1,   921600, 0x63e0025c
 0,         33,         33,        1,   921600, 0x262359ed
+0,         34,         34,        1,   921600, 0x262359ed
 0,         35,         35,        1,   921600, 0x343688e8
+0,         36,         36,        1,   921600, 0x343688e8
+0,         37,         37,        1,   921600, 0x343688e8
+0,         38,         38,        1,   921600, 0x343688e8
+0,         39,         39,        1,   921600, 0x343688e8
+0,         40,         40,        1,   921600, 0x343688e8
+0,         41,         41,        1,   921600, 0x343688e8
+0,         42,         42,        1,   921600, 0x343688e8
+0,         43,         43,        1,   921600, 0x343688e8
+0,         44,         44,        1,   921600, 0x343688e8
 0,         45,         45,        1,   921600, 0xe4b29d57
+0,         46,         46,        1,   921600, 0xe4b29d57
+0,         47,         47,        1,   921600, 0xe4b29d57
 0,         48,         48,        1,   921600, 0x198e8a4a
+0,         49,         49,        1,   921600, 0x198e8a4a
 0,         50,         50,        1,   921600, 0x0cad8dc9
+0,         51,         51,        1,   921600, 0x0cad8dc9
+0,         52,         52,        1,   921600, 0x0cad8dc9
 0,         53,         53,        1,   921600, 0x1f74cf3d
+0,         54,         54,        1,   921600, 0x1f74cf3d
 0,         55,         55,        1,   921600, 0xec5b5449
+0,         56,         56,        1,   921600, 0xec5b5449
+0,         57,         57,        1,   921600, 0xec5b5449
 0,         58,         58,        1,   921600, 0x39829711
+0,         59,         59,        1,   921600, 0x39829711
 0,         60,         60,        1,   921600, 0x6de5b9c6
+0,         61,         61,        1,   921600, 0x6de5b9c6
+0,         62,         62,        1,   921600, 0x6de5b9c6
 0,         63,         63,        1,   921600, 0x47b0e9d4
+0,         64,         64,        1,   921600, 0x47b0e9d4
 0,         65,         65,        1,   921600, 0x756452b8
+0,         66,         66,        1,   921600, 0x756452b8
+0,         67,         67,        1,   921600, 0x756452b8
 0,         68,         68,        1,   921600, 0x6fce3478
+0,         69,         69,        1,   921600, 0x6fce3478
 0,         70,         70,        1,   921600, 0x372397cd
+0,         71,         71,        1,   921600, 0x372397cd
+0,         72,         72,        1,   921600, 0x372397cd
 0,         73,         73,        1,   921600, 0xe3999ba1
+0,         74,         74,        1,   921600, 0xe3999ba1
 0,         75,         75,        1,   921600, 0x6ba26b43
+0,         76,         76,        1,   921600, 0x6ba26b43
+0,         77,         77,        1,   921600, 0x6ba26b43
 0,         78,         78,        1,   921600, 0x4e9ee49e
+0,         79,         79,        1,   921600, 0x4e9ee49e
 0,         80,         80,        1,   921600, 0xdb5fd6e7
+0,         81,         81,        1,   921600, 0xdb5fd6e7
+0,         82,         82,        1,   921600, 0xdb5fd6e7
 0,         83,         83,        1,   921600, 0x8f2254a5
+0,         84,         84,        1,   921600, 0x8f2254a5
+0,         85,         85,        1,   921600, 0x8f2254a5
+0,         86,         86,        1,   921600, 0x8f2254a5
+0,         87,         87,        1,   921600, 0x8f2254a5
+0,         88,         88,        1,   921600, 0x8f2254a5
+0,         89,         89,        1,   921600, 0x8f2254a5
+0,         90,         90,        1,   921600, 0x8f2254a5
+0,         91,         91,        1,   921600, 0x8f2254a5
+0,         92,         92,        1,   921600, 0x8f2254a5
 0,         93,         93,        1,   921600, 0x57e95c32
+0,         94,         94,        1,   921600, 0x57e95c32
 0,         95,         95,        1,   921600, 0x41627a9b
+0,         96,         96,        1,   921600, 0x41627a9b
+0,         97,         97,        1,   921600, 0x41627a9b
 0,         98,         98,        1,   921600, 0x7412dcee
+0,         99,         99,        1,   921600, 0x7412dcee
 0,        100,        100,        1,   921600, 0xaebe10ed
+0,        101,        101,        1,   921600, 0xaebe10ed
+0,        102,        102,        1,   921600, 0xaebe10ed
 0,        103,        103,        1,   921600, 0x411a91f6
+0,        104,        104,        1,   921600, 0x411a91f6
 0,        105,        105,        1,   921600, 0xb059df3f
+0,        106,        106,        1,   921600, 0xb059df3f
+0,        107,        107,        1,   921600, 0xb059df3f
 0,        108,        108,        1,   921600, 0x4d6f5a77
+0,        109,        109,        1,   921600, 0x4d6f5a77
 0,        110,        110,        1,   921600, 0xbbf06df4
+0,        111,        111,        1,   921600, 0xbbf06df4
+0,        112,        112,        1,   921600, 0xbbf06df4
 0,        113,        113,        1,   921600, 0xe27f7bf6
+0,        114,        114,        1,   921600, 0xe27f7bf6
 0,        115,        115,        1,   921600, 0xd7e8360e
+0,        116,        116,        1,   921600, 0xd7e8360e
+0,        117,        117,        1,   921600, 0xd7e8360e
 0,        118,        118,        1,   921600, 0x1dd4c344
+0,        119,        119,        1,   921600, 0x1dd4c344
 0,        120,        120,        1,   921600, 0x7995a7ce
+0,        121,        121,        1,   921600, 0x7995a7ce
+0,        122,        122,        1,   921600, 0x7995a7ce
 0,        123,        123,        1,   921600, 0x2ef3c566
+0,        124,        124,        1,   921600, 0x2ef3c566
 0,        125,        125,        1,   921600, 0xf296736e
+0,        126,        126,        1,   921600, 0xf296736e
+0,        127,        127,        1,   921600, 0xf296736e
+0,        128,        128,        1,   921600, 0xf296736e
+0,        129,        129,        1,   921600, 0xf296736e
+0,        130,        130,        1,   921600, 0xf296736e
+0,        131,        131,        1,   921600, 0xf296736e
+0,        132,        132,        1,   921600, 0xf296736e
+0,        133,        133,        1,   921600, 0xf296736e
+0,        134,        134,        1,   921600, 0xf296736e
 0,        135,        135,        1,   921600, 0x1a488311
+0,        136,        136,        1,   921600, 0x1a488311
+0,        137,        137,        1,   921600, 0x1a488311
 0,        138,        138,        1,   921600, 0x9e28011b
+0,        139,        139,        1,   921600, 0x9e28011b
 0,        140,        140,        1,   921600, 0x84d1ea80
+0,        141,        141,        1,   921600, 0x84d1ea80
+0,        142,        142,        1,   921600, 0x84d1ea80
 0,        143,        143,        1,   921600, 0x9ed41052
+0,        144,        144,        1,   921600, 0x9ed41052
 0,        145,        145,        1,   921600, 0xd4db7206
+0,        146,        146,        1,   921600, 0xd4db7206
+0,        147,        147,        1,   921600, 0xd4db7206
 0,        148,        148,        1,   921600, 0x55f695a9
+0,        149,        149,        1,   921600, 0x55f695a9
 0,        150,        150,        1,   921600, 0x9d8c667f
+0,        151,        151,        1,   921600, 0x9d8c667f
+0,        152,        152,        1,   921600, 0x9d8c667f
 0,        153,        153,        1,   921600, 0x9b6037ec
+0,        154,        154,        1,   921600, 0x9b6037ec
 0,        155,        155,        1,   921600, 0x57c5e835
+0,        156,        156,        1,   921600, 0x57c5e835
+0,        157,        157,        1,   921600, 0x57c5e835
 0,        158,        158,        1,   921600, 0x476dad89
+0,        159,        159,        1,   921600, 0x476dad89
 0,        160,        160,        1,   921600, 0xcfd6ad2b
+0,        161,        161,        1,   921600, 0xcfd6ad2b
+0,        162,        162,        1,   921600, 0xcfd6ad2b
 0,        163,        163,        1,   921600, 0x3b372379
+0,        164,        164,        1,   921600, 0x3b372379
 0,        165,        165,        1,   921600, 0x36f245f5
+0,        166,        166,        1,   921600, 0x36f245f5