[FFmpeg-devel] [PATCH 1/3] lavc/h274: fix PRNG definition

[Niklas Haas]

On Thu, 28 Sep 2023 20:53:44 +0200 Michael Niedermayer <michael at niedermayer.cc> wrote:
> On Wed, Sep 27, 2023 at 03:56:15PM +0200, Niklas Haas wrote:
> > From: Niklas Haas <git at 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.