random_seed: Rewrite generic code

diff mbox

From: Michael Niedermayer <michaelni@gmx.at>

The new code is faster and reuses the previous state in case of
multiple calls.

The previous code could easily end up in near-infinite loops,
if the difference between two clock() calls never was larger than
1.

This makes fate-parseutils built with MSVC finish in finite time
when run in wine. (The one built with mingw actually manages to find
/dev/urandom so it doesn't do the generic code, but the MSVC build
doesn't try to do this.) On real windows, it seems to finish pretty
quickly.
---
Removed the use of AV_READ_TIME, did some extra cosmetic cleanup
I missed in the previous round.
---
 libavutil/random_seed.c |   45 ++++++++++++++++++++++++---------------------
 1 file changed, 24 insertions(+), 21 deletions(-)

Martin Storsjö <martin@martin.st> writes:

> From: Michael Niedermayer <michaelni@gmx.at>
>
> The new code is faster and reuses the previous state in case of
> multiple calls.
>
> The previous code could easily end up in near-infinite loops,
> if the difference between two clock() calls never was larger than
> 1.
>
> This makes fate-parseutils built with MSVC finish in finite time
> when run in wine. (The one built with mingw actually manages to find
> /dev/urandom so it doesn't do the generic code, but the MSVC build
> doesn't try to do this.) On real windows, it seems to finish pretty
> quickly.
> ---
> Removed the use of AV_READ_TIME, did some extra cosmetic cleanup
> I missed in the previous round.
> ---
>  libavutil/random_seed.c |   45 ++++++++++++++++++++++++---------------------
>  1 file changed, 24 insertions(+), 21 deletions(-)
>
> diff --git a/libavutil/random_seed.c b/libavutil/random_seed.c
> index 8ee4cb7..3eed303 100644
> --- a/libavutil/random_seed.c
> +++ b/libavutil/random_seed.c
> @@ -26,8 +26,12 @@
>  #include <fcntl.h>
>  #include <math.h>
>  #include <time.h>
> +#include <string.h>
>  #include "timer.h"
>  #include "random_seed.h"
> +#include "sha.h"
> +#include "intreadwrite.h"
> +#include <assert.h>
>
>  static int read_random(uint32_t *dst, const char *file)
>  {
> @@ -48,34 +52,33 @@ static int read_random(uint32_t *dst, const char *file)
>
>  static uint32_t get_generic_seed(void)
>  {
> +    uint8_t tmp[120];
> +    struct AVSHA *sha = (void*) tmp;

This doesn't even begin to guarantee proper alignment.  Can we please
fix the context allocation madness for this and others like it?  That
is, we should add proper allocation functions and deprecate/drop the
size variables.

Further to previous comments...

Martin Storsjö <martin@martin.st> writes:

>  static uint32_t get_generic_seed(void)
>  {
> +    uint8_t tmp[120];
> +    struct AVSHA *sha = (void*) tmp;
>      clock_t last_t  = 0;

POSIX reserves names in the *_t namespace.

> -    int bits        = 0;
> -    uint64_t random = 0;
> -    unsigned i;
> -    float s = 0.000000000001;
> +    static uint64_t i = 0;
> +    static uint32_t buffer[512] = { 0 };
> +    uint8_t digest[32];
> +    uint64_t last_i = i;
>
> -    for (i = 0; bits < 64; i++) {
> +    assert(sizeof(tmp) >= av_sha_size);



> +    for (;;) {
>          clock_t t = clock();
> +
> +        if (last_t == t) {
> +            buffer[i & 511]++;
> +        } else {
> +            buffer[++i & 511] += (t - last_t) % 3294638521U;
> +            if (last_i && i - last_i > 4 || i - last_i > 64)
> +                break;
>          }
>          last_t = t;
>      }

clock() returns the CPU time used by the current process in
microseconds, although the actual resolution is unspecified and is
typically nowhere near that accurate.  Thus (t - last_t) will always be
whatever actual resolution the system uses.

Furthermore, since a program is likely to call this function at the same
point in every execution, the CPU time it has used when this happens can
hardly be considered random.

All in all, this dance looks very poor in terms of entropy gathering.

> -#ifdef AV_READ_TIME
> -    random ^= AV_READ_TIME();
> -#else
> -    random ^= clock();
> -#endif
> -
> -    random += random >> 32;
>
> -    return random;
> +    av_sha_init(sha, 160);
> +    av_sha_update(sha, (uint8_t*) buffer, sizeof(buffer));
> +    av_sha_final(sha, digest);
> +    return AV_RB32(digest) + AV_RB32(digest + 32);

This reads outside the buffer.

>  }
>
>  uint32_t av_get_random_seed(void)
> -- 
> 1.7.9.5
>