| Message ID | 20230927135617.33952-1-ffmpeg@haasn.xyz |
|---|---|
| State | Accepted |
| Commit | 338a5fcdbe9571e6f22817a111621259d83f2e59 |
| Headers | show |
| Series | [FFmpeg-devel,1/3] lavc/h274: fix PRNG definition | expand |
| Context | Check | Description |
|---|---|---|
| andriy/make_x86 | success | Make finished |
| andriy/make_fate_x86 | success | Make fate finished |
Context: I compared our implementation against a H.274 reference stream. Identified this issues as a result. This is still not bit-exact, we round incorrectly in some cases (~2% of output pixels are +1 or -1). I'm not sure where we pick up the remaining error from..
On Wed, Sep 27, 2023 at 03:56:15PM +0200, Niklas Haas wrote: > From: Niklas Haas <git@haasn.dev> > > The spec specifies x^31 + x^3 + 1 as the polynomial, but the diagram in > Figure 1-1 omits the +1 offset. The initial implementation was based on > the diagram, but this is wrong (produces subtly incorrect results). > --- > libavcodec/h274.c | 2 +- > 1 file changed, 1 insertion(+), 1 deletion(-) > > diff --git a/libavcodec/h274.c b/libavcodec/h274.c > index a69f9411429..fc111cdb50d 100644 > --- a/libavcodec/h274.c > +++ b/libavcodec/h274.c > @@ -38,7 +38,7 @@ static void prng_shift(uint32_t *state) > { > // Primitive polynomial x^31 + x^3 + 1 (modulo 2) > uint32_t x = *state; > - uint8_t feedback = (x >> 2) ^ (x >> 30); > + uint8_t feedback = 1u ^ (x >> 2) ^ (x >> 30); > *state = (x << 1) | (feedback & 1u); where can i find the text describing this that you refer to ? thx [...]
On Wed, 27 Sep 2023 21:07:55 +0200 Michael Niedermayer <michael@niedermayer.cc> wrote:
> where can i find the text describing this that you refer to ?
It is in SMPTE RDD 5 (DOI 10.5594/SMPTE.RDD5.2006), you can find it on
the usual places.
On Thu, Sep 28, 2023 at 11:08 AM Niklas Haas <ffmpeg@haasn.xyz> wrote: > On Wed, 27 Sep 2023 21:07:55 +0200 Michael Niedermayer < > michael@niedermayer.cc> wrote: > > where can i find the text describing this that you refer to ? > > It is in SMPTE RDD 5 (DOI 10.5594/SMPTE.RDD5.2006), you can find it on > the usual places. > Could it maybe be mentioned in the commit log? Or documented in a comment (not familiar with the file, apologies if it's already so)
On Wed, Sep 27, 2023 at 03:56:15PM +0200, Niklas Haas wrote: > From: Niklas Haas <git@haasn.dev> > > The spec specifies x^31 + x^3 + 1 as the polynomial, but the diagram in > Figure 1-1 omits the +1 offset. The initial implementation was based on > the diagram, but this is wrong (produces subtly incorrect results). the +1 changes "nothing" if you take the prng with and without the +1 the 2 will produce 2 sequences that are negations of each other or said different if you start one from 1 and the other from ~1 they will produce the same sequence just 0 and 1 swaped you can also compute 32 bits at once using this: (this needs 64bits of the sequence as input though) not sure how useful it is, but it produces more bits quicker static void prng_shift32(uint64_t *state) { uint64_t x = *state; uint64_t y = x ^ x>>3; y ^= y>>6; y ^= y>>12; uint32_t feedback = (x >> 1) ^ (y >> 5) ^ (x >> 29) ^ (x >> 30); *state = (x << 32) | feedback; } [...]
On Thu, 28 Sep 2023 20:53:44 +0200 Michael Niedermayer <michael@niedermayer.cc> wrote: > On Wed, Sep 27, 2023 at 03:56:15PM +0200, Niklas Haas wrote: > > From: Niklas Haas <git@haasn.dev> > > > > The spec specifies x^31 + x^3 + 1 as the polynomial, but the diagram in > > Figure 1-1 omits the +1 offset. The initial implementation was based on > > the diagram, but this is wrong (produces subtly incorrect results). > > the +1 changes "nothing" > if you take the prng with and without the +1 the 2 will produce 2 > sequences that are negations of each other > > or said different if you start one from 1 and the other from ~1 > they will produce the same sequence just 0 and 1 swaped > > you can also compute 32 bits at once using this: > (this needs 64bits of the sequence as input though) > not sure how useful it is, but it produces more bits quicker > > static void prng_shift32(uint64_t *state) > { > uint64_t x = *state; > uint64_t y = x ^ x>>3; > y ^= y>>6; > y ^= y>>12; > uint32_t feedback = (x >> 1) ^ (y >> 5) ^ (x >> 29) ^ (x >> 30); > *state = (x << 32) | feedback; > } Thanks for the explanation and tip. In this case, PRNG output is by far not the bottleneck (we only need one 32-bit random value per 16x16 block), so I don't think it needs to be modified further.
On Thu, 28 Sep 2023 12:03:08 -0400 Vittorio Giovara <vittorio.giovara@gmail.com> wrote: > On Thu, Sep 28, 2023 at 11:08 AM Niklas Haas <ffmpeg@haasn.xyz> wrote: > > > On Wed, 27 Sep 2023 21:07:55 +0200 Michael Niedermayer < > > michael@niedermayer.cc> wrote: > > > where can i find the text describing this that you refer to ? > > > > It is in SMPTE RDD 5 (DOI 10.5594/SMPTE.RDD5.2006), you can find it on > > the usual places. > > > > Could it maybe be mentioned in the commit log? Or documented in a comment > (not familiar with the file, apologies if it's already so) Hi, it is mentioned in the commit message attached to the initial implementation of this file, and also linked multiple times throughout the source code.
diff --git a/libavcodec/h274.c b/libavcodec/h274.c index a69f9411429..fc111cdb50d 100644 --- a/libavcodec/h274.c +++ b/libavcodec/h274.c @@ -38,7 +38,7 @@ static void prng_shift(uint32_t *state) { // Primitive polynomial x^31 + x^3 + 1 (modulo 2) uint32_t x = *state; - uint8_t feedback = (x >> 2) ^ (x >> 30); + uint8_t feedback = 1u ^ (x >> 2) ^ (x >> 30); *state = (x << 1) | (feedback & 1u); }
From: Niklas Haas <git@haasn.dev> The spec specifies x^31 + x^3 + 1 as the polynomial, but the diagram in Figure 1-1 omits the +1 offset. The initial implementation was based on the diagram, but this is wrong (produces subtly incorrect results). --- libavcodec/h274.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)