diff mbox

[FFmpeg-devel,1/3] avcodec/get_bits: add cached bitstream reader

Message ID 20170708091206.9293-1-onemda@gmail.com
State Superseded
Headers show

Commit Message

Paul B Mahol July 8, 2017, 9:12 a.m. UTC 
Signed-off-by: Paul B Mahol <onemda@gmail.com>
---
 libavcodec/get_bits.h | 261 +++++++++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 235 insertions(+), 26 deletions(-)

Comments

foo86 July 8, 2017, 5:09 p.m. UTC | #1 
On Sat, Jul 08, 2017 at 11:12:06AM +0200, Paul B Mahol wrote:
> [...]

>  static inline void skip_bits(GetBitContext *s, int n)
>  {
> +#ifdef CACHED_BITSTREAM_READER
> +    if (n <= s->bits_left)
> +        skip_remaining(s, n);
> +    else {
> +        n -= s->bits_left;
> +        skip_remaining(s, s->bits_left);
This causes undefined behavior if s->bits_left == 64.

> +        if (n >= 64) {
> +            unsigned skip = n;
> +
> +            n -= skip;
> +            s->index += skip;
> +        }
This block looks strange.

> +        refill_32(s);
> +        if (n)
> +            skip_remaining(s, n);
> +    }
> +#else
>      OPEN_READER(re, s);
>      LAST_SKIP_BITS(re, s, n);
>      CLOSE_READER(re, s);
> +#endif
> +}
> +
> +static inline void skip_bits_long(GetBitContext *s, int n)
> +{
> +#ifdef CACHED_BITSTREAM_READER
> +    skip_bits(s, n);
> +#else
> +#if UNCHECKED_BITSTREAM_READER
> +    s->index += n;
> +#else
> +    s->index += av_clip(n, -s->index, s->size_in_bits_plus8 - s->index);
Uncached bitstream reader allows seeking back by passing negative n
here. If cached bitstream reader disallows this, there should be a
comment saying so (and possibly an assert).
Rostislav Pehlivanov July 8, 2017, 5:23 p.m. UTC | #2 
On 8 July 2017 at 10:12, Paul B Mahol <onemda@gmail.com> wrote:

> Signed-off-by: Paul B Mahol <onemda@gmail.com>
> ---
>  libavcodec/get_bits.h | 261 ++++++++++++++++++++++++++++++
> +++++++++++++++-----
>  1 file changed, 235 insertions(+), 26 deletions(-)
>
>
>
I still say it should be enabled by default with a flag to choose between
64 and 32 bit cache size (based on the arch). That'll give a speed increase
throughout most of the code and not cause much or any regression.
Paul B Mahol July 8, 2017, 5:25 p.m. UTC | #3 
On 7/8/17, foo86 <foobaz86@gmail.com> wrote:
> On Sat, Jul 08, 2017 at 11:12:06AM +0200, Paul B Mahol wrote:
>> [...]
>
>>  static inline void skip_bits(GetBitContext *s, int n)
>>  {
>> +#ifdef CACHED_BITSTREAM_READER
>> +    if (n <= s->bits_left)
>> +        skip_remaining(s, n);
>> +    else {
>> +        n -= s->bits_left;
>> +        skip_remaining(s, s->bits_left);
> This causes undefined behavior if s->bits_left == 64.

Could you elaborate?, it looks to me Libav have same issue.

>
>> +        if (n >= 64) {
>> +            unsigned skip = n;
>> +
>> +            n -= skip;
>> +            s->index += skip;
>> +        }
> This block looks strange.
>
>> +        refill_32(s);
>> +        if (n)
>> +            skip_remaining(s, n);
>> +    }
>> +#else
>>      OPEN_READER(re, s);
>>      LAST_SKIP_BITS(re, s, n);
>>      CLOSE_READER(re, s);
>> +#endif
>> +}
>> +
>> +static inline void skip_bits_long(GetBitContext *s, int n)
>> +{
>> +#ifdef CACHED_BITSTREAM_READER
>> +    skip_bits(s, n);
>> +#else
>> +#if UNCHECKED_BITSTREAM_READER
>> +    s->index += n;
>> +#else
>> +    s->index += av_clip(n, -s->index, s->size_in_bits_plus8 - s->index);
> Uncached bitstream reader allows seeking back by passing negative n
> here. If cached bitstream reader disallows this, there should be a
> comment saying so (and possibly an assert).

I can add seeking one from other API.
Hendrik Leppkes July 8, 2017, 6:07 p.m. UTC | #4 
On Sat, Jul 8, 2017 at 7:09 PM, foo86 <foobaz86@gmail.com> wrote:
> On Sat, Jul 08, 2017 at 11:12:06AM +0200, Paul B Mahol wrote:
>> [...]
>
>>  static inline void skip_bits(GetBitContext *s, int n)
>>  {
>> +#ifdef CACHED_BITSTREAM_READER
>> +    if (n <= s->bits_left)
>> +        skip_remaining(s, n);
>> +    else {
>> +        n -= s->bits_left;
>> +        skip_remaining(s, s->bits_left);
> This causes undefined behavior if s->bits_left == 64.
>
>> +        if (n >= 64) {
>> +            unsigned skip = n;
>> +
>> +            n -= skip;
>> +            s->index += skip;
>> +        }
> This block looks strange.
>
>> +        refill_32(s);
>> +        if (n)
>> +            skip_remaining(s, n);
>> +    }
>> +#else
>>      OPEN_READER(re, s);
>>      LAST_SKIP_BITS(re, s, n);
>>      CLOSE_READER(re, s);
>> +#endif
>> +}
>> +
>> +static inline void skip_bits_long(GetBitContext *s, int n)
>> +{
>> +#ifdef CACHED_BITSTREAM_READER
>> +    skip_bits(s, n);
>> +#else
>> +#if UNCHECKED_BITSTREAM_READER
>> +    s->index += n;
>> +#else
>> +    s->index += av_clip(n, -s->index, s->size_in_bits_plus8 - s->index);
> Uncached bitstream reader allows seeking back by passing negative n
> here. If cached bitstream reader disallows this, there should be a
> comment saying so (and possibly an assert).

This seems like an undocumented and possibly insecure/invalid use of
the API, maybe we should just generally discourage such use.

Why would you need to skip backwards anyway? Usually code uses
show_bits, or creates a copy of the reader so it can revert to the
original if needed.

- Hendrik
Hendrik Leppkes July 8, 2017, 6:44 p.m. UTC | #5 
On Sat, Jul 8, 2017 at 7:23 PM, Rostislav Pehlivanov
<atomnuker@gmail.com> wrote:
> On 8 July 2017 at 10:12, Paul B Mahol <onemda@gmail.com> wrote:
>
>> Signed-off-by: Paul B Mahol <onemda@gmail.com>
>> ---
>>  libavcodec/get_bits.h | 261 ++++++++++++++++++++++++++++++
>> +++++++++++++++-----
>>  1 file changed, 235 insertions(+), 26 deletions(-)
>>
>>
>>
> I still say it should be enabled by default with a flag to choose between
> 64 and 32 bit cache size (based on the arch). That'll give a speed increase
> throughout most of the code and not cause much or any regression.

Do you have any numbers for those claims?

- Hendrik
foo86 July 8, 2017, 6:45 p.m. UTC | #6 
On Sat, Jul 08, 2017 at 07:25:52PM +0200, Paul B Mahol wrote:
> On 7/8/17, foo86 <foobaz86@gmail.com> wrote:
> > On Sat, Jul 08, 2017 at 11:12:06AM +0200, Paul B Mahol wrote:
> >> [...]
> >
> >>  static inline void skip_bits(GetBitContext *s, int n)
> >>  {
> >> +#ifdef CACHED_BITSTREAM_READER
> >> +    if (n <= s->bits_left)
> >> +        skip_remaining(s, n);
> >> +    else {
> >> +        n -= s->bits_left;
> >> +        skip_remaining(s, s->bits_left);
> > This causes undefined behavior if s->bits_left == 64.
> 
> Could you elaborate?, it looks to me Libav have same issue.

Calling skip_bits_long() with n > 64 after init_get_bits() causes this
error:

libavcodec/get_bits.h:309:14: runtime error: shift exponent 64 is too
large for 64-bit type 'long unsigned int'
foo86 July 8, 2017, 6:59 p.m. UTC | #7 
On Sat, Jul 08, 2017 at 08:07:49PM +0200, Hendrik Leppkes wrote:
> On Sat, Jul 8, 2017 at 7:09 PM, foo86 <foobaz86@gmail.com> wrote:
> >> +static inline void skip_bits_long(GetBitContext *s, int n)
> >> +{
> >> +#ifdef CACHED_BITSTREAM_READER
> >> +    skip_bits(s, n);
> >> +#else
> >> +#if UNCHECKED_BITSTREAM_READER
> >> +    s->index += n;
> >> +#else
> >> +    s->index += av_clip(n, -s->index, s->size_in_bits_plus8 - s->index);
> > Uncached bitstream reader allows seeking back by passing negative n
> > here. If cached bitstream reader disallows this, there should be a
> > comment saying so (and possibly an assert).
> 
> This seems like an undocumented and possibly insecure/invalid use of
> the API, maybe we should just generally discourage such use.

If skip_bits_long() is not supposed to seek backward, then it's fine by
me. (I thought it was looking at its implementation which allows
negative n).

> Why would you need to skip backwards anyway? Usually code uses
> show_bits, or creates a copy of the reader so it can revert to the
> original if needed.

DCA XLL decoder needs to seek backward to recover from segment overread.
I will probably change it to create a copy of the GetBitContext as you
suggested, seems to be a better solution.
Paul B Mahol July 8, 2017, 7:17 p.m. UTC | #8 
On 7/8/17, foo86 <foobaz86@gmail.com> wrote:
> On Sat, Jul 08, 2017 at 08:07:49PM +0200, Hendrik Leppkes wrote:
>> On Sat, Jul 8, 2017 at 7:09 PM, foo86 <foobaz86@gmail.com> wrote:
>> >> +static inline void skip_bits_long(GetBitContext *s, int n)
>> >> +{
>> >> +#ifdef CACHED_BITSTREAM_READER
>> >> +    skip_bits(s, n);
>> >> +#else
>> >> +#if UNCHECKED_BITSTREAM_READER
>> >> +    s->index += n;
>> >> +#else
>> >> +    s->index += av_clip(n, -s->index, s->size_in_bits_plus8 -
>> >> s->index);
>> > Uncached bitstream reader allows seeking back by passing negative n
>> > here. If cached bitstream reader disallows this, there should be a
>> > comment saying so (and possibly an assert).
>>
>> This seems like an undocumented and possibly insecure/invalid use of
>> the API, maybe we should just generally discourage such use.
>
> If skip_bits_long() is not supposed to seek backward, then it's fine by
> me. (I thought it was looking at its implementation which allows
> negative n).
>
>> Why would you need to skip backwards anyway? Usually code uses
>> show_bits, or creates a copy of the reader so it can revert to the
>> original if needed.
>
> DCA XLL decoder needs to seek backward to recover from segment overread.
> I will probably change it to create a copy of the GetBitContext as you
> suggested, seems to be a better solution.

I will do same in skip_bits_long(). No need to change anything in codecs.
diff mbox

Patch

diff --git a/libavcodec/get_bits.h b/libavcodec/get_bits.h
index c530015..f404b80 100644
--- a/libavcodec/get_bits.h
+++ b/libavcodec/get_bits.h
@@ -1,5 +1,6 @@ 
 /*
- * copyright (c) 2004 Michael Niedermayer <michaelni@gmx.at>
+ * Copyright (c) 2004 Michael Niedermayer <michaelni@gmx.at>
+ * Copyright (c) 2016 Alexandra Hájková
  *
  * This file is part of FFmpeg.
  *
@@ -54,6 +55,10 @@ 
 
 typedef struct GetBitContext {
     const uint8_t *buffer, *buffer_end;
+#ifdef CACHED_BITSTREAM_READER
+    uint64_t cache;
+    unsigned bits_left;
+#endif
     int index;
     int size_in_bits;
     int size_in_bits_plus8;
@@ -106,12 +111,16 @@  typedef struct GetBitContext {
  * For examples see get_bits, show_bits, skip_bits, get_vlc.
  */
 
-#ifdef LONG_BITSTREAM_READER
+#ifdef CACHED_BITSTREAM_READER
+#   define MIN_CACHE_BITS 64
+#elif defined LONG_BITSTREAM_READER
 #   define MIN_CACHE_BITS 32
 #else
 #   define MIN_CACHE_BITS 25
 #endif
 
+#ifndef CACHED_BITSTREAM_READER
+
 #define OPEN_READER_NOSIZE(name, gb)            \
     unsigned int name ## _index = (gb)->index;  \
     unsigned int av_unused name ## _cache
@@ -196,20 +205,113 @@  typedef struct GetBitContext {
 
 #define GET_CACHE(name, gb) ((uint32_t) name ## _cache)
 
+#endif
+
 static inline int get_bits_count(const GetBitContext *s)
 {
+#ifdef CACHED_BITSTREAM_READER
+    return s->index - s->bits_left;
+#else
     return s->index;
+#endif
 }
 
-static inline void skip_bits_long(GetBitContext *s, int n)
+static inline void refill_32(GetBitContext *s)
 {
-#if UNCHECKED_BITSTREAM_READER
-    s->index += n;
+#ifdef CACHED_BITSTREAM_READER
+#if !UNCHECKED_BITSTREAM_READER
+    if (s->index >> 3 >= s->buffer_end - s->buffer)
+        return;
+#endif
+
+#ifdef BITSTREAM_READER_LE
+    s->cache       = (uint64_t)AV_RL32(s->buffer + (s->index >> 3)) << s->bits_left | s->cache;
 #else
-    s->index += av_clip(n, -s->index, s->size_in_bits_plus8 - s->index);
+    s->cache       = s->cache | (uint64_t)AV_RB32(s->buffer + (s->index >> 3)) << (32 - s->bits_left);
+#endif
+    s->index     += 32;
+    s->bits_left += 32;
+#endif
+}
+
+static inline void refill_64(GetBitContext *s)
+{
+#ifdef CACHED_BITSTREAM_READER
+#if !UNCHECKED_BITSTREAM_READER
+    if (s->index >> 3 >= s->buffer_end - s->buffer)
+        return;
+#endif
+
+#ifdef BITSTREAM_READER_LE
+    s->cache = AV_RL64(s->buffer + (s->index >> 3));
+#else
+    s->cache = AV_RB64(s->buffer + (s->index >> 3));
+#endif
+    s->index += 64;
+    s->bits_left = 64;
+#endif
+}
+
+#ifdef CACHED_BITSTREAM_READER
+static inline uint64_t get_val(GetBitContext *s, unsigned n)
+{
+    uint64_t ret;
+    av_assert2(n>0 && n<=63);
+#ifdef BITSTREAM_READER_LE
+    ret = s->cache & ((UINT64_C(1) << n) - 1);
+    s->cache >>= n;
+#else
+    ret = s->cache >> (64 - n);
+    s->cache <<= n;
+#endif
+    s->bits_left -= n;
+    return ret;
+}
+#endif
+
+#ifdef CACHED_BITSTREAM_READER
+static inline unsigned show_val(const GetBitContext *s, unsigned n)
+{
+#ifdef BITSTREAM_READER_LE
+    return s->cache & ((UINT64_C(1) << n) - 1);
+#else
+    return s->cache >> (64 - n);
+#endif
+}
+#endif
+
+/**
+ * Show 1-25 bits.
+ */
+static inline unsigned int show_bits(GetBitContext *s, int n)
+{
+    register int tmp;
+#ifdef CACHED_BITSTREAM_READER
+    if (n > s->bits_left)
+        refill_32(s);
+
+    tmp = show_val(s, n);
+#else
+    OPEN_READER_NOSIZE(re, s);
+    av_assert2(n>0 && n<=25);
+    UPDATE_CACHE(re, s);
+    tmp = SHOW_UBITS(re, s, n);
 #endif
+    return tmp;
 }
 
+#ifdef CACHED_BITSTREAM_READER
+static inline void skip_remaining(GetBitContext *s, unsigned n)
+{
+#ifdef BITSTREAM_READER_LE
+    s->cache >>= n;
+#else
+    s->cache <<= n;
+#endif
+    s->bits_left -= n;
+}
+#endif
+
 /**
  * Read MPEG-1 dc-style VLC (sign bit + mantissa with no MSB).
  * if MSB not set it is negative
@@ -217,6 +319,13 @@  static inline void skip_bits_long(GetBitContext *s, int n)
  */
 static inline int get_xbits(GetBitContext *s, int n)
 {
+#ifdef CACHED_BITSTREAM_READER
+    int32_t cache = show_bits(s, 32);
+    int sign = ~cache >> 31;
+    skip_remaining(s, n);
+
+    return ((((uint32_t)(sign ^ cache)) >> (32 - n)) ^ sign) - sign;
+#else
     register int sign;
     register int32_t cache;
     OPEN_READER(re, s);
@@ -227,8 +336,10 @@  static inline int get_xbits(GetBitContext *s, int n)
     LAST_SKIP_BITS(re, s, n);
     CLOSE_READER(re, s);
     return (NEG_USR32(sign ^ cache, n) ^ sign) - sign;
+#endif
 }
 
+#ifndef CACHED_BITSTREAM_READER
 static inline int get_xbits_le(GetBitContext *s, int n)
 {
     register int sign;
@@ -242,31 +353,61 @@  static inline int get_xbits_le(GetBitContext *s, int n)
     CLOSE_READER(re, s);
     return (zero_extend(sign ^ cache, n) ^ sign) - sign;
 }
+#endif
 
-static inline int get_sbits(GetBitContext *s, int n)
+/**
+ * Read 1-25 bits.
+ */
+static inline unsigned int get_bits(GetBitContext *s, int n)
 {
+#ifdef CACHED_BITSTREAM_READER
+    register int tmp = 0;
+#ifdef BITSTREAM_READER_LE
+    uint64_t left = 0;
+#endif
+
+    av_assert2(n>0 && n<=32);
+    if (n > s->bits_left) {
+        n -= s->bits_left;
+#ifdef BITSTREAM_READER_LE
+        left = s->bits_left;
+#endif
+        tmp = get_val(s, s->bits_left);
+        refill_32(s);
+    }
+
+#ifdef BITSTREAM_READER_LE
+    tmp = get_val(s, n) << left | tmp;
+#else
+    tmp = get_val(s, n) | tmp << n;
+#endif
+
+#else
     register int tmp;
     OPEN_READER(re, s);
     av_assert2(n>0 && n<=25);
     UPDATE_CACHE(re, s);
-    tmp = SHOW_SBITS(re, s, n);
+    tmp = SHOW_UBITS(re, s, n);
     LAST_SKIP_BITS(re, s, n);
     CLOSE_READER(re, s);
+#endif
     return tmp;
 }
 
-/**
- * Read 1-25 bits.
- */
-static inline unsigned int get_bits(GetBitContext *s, int n)
+static inline int get_sbits(GetBitContext *s, int n)
 {
     register int tmp;
+#ifdef CACHED_BITSTREAM_READER
+    av_assert2(n>0 && n<=25);
+    tmp = sign_extend(get_bits(s, n), n);
+#else
     OPEN_READER(re, s);
     av_assert2(n>0 && n<=25);
     UPDATE_CACHE(re, s);
-    tmp = SHOW_UBITS(re, s, n);
+    tmp = SHOW_SBITS(re, s, n);
     LAST_SKIP_BITS(re, s, n);
     CLOSE_READER(re, s);
+#endif
     return tmp;
 }
 
@@ -278,6 +419,7 @@  static av_always_inline int get_bitsz(GetBitContext *s, int n)
     return n ? get_bits(s, n) : 0;
 }
 
+#ifndef CACHED_BITSTREAM_READER
 static inline unsigned int get_bits_le(GetBitContext *s, int n)
 {
     register int tmp;
@@ -289,29 +431,54 @@  static inline unsigned int get_bits_le(GetBitContext *s, int n)
     CLOSE_READER(re, s);
     return tmp;
 }
-
-/**
- * Show 1-25 bits.
- */
-static inline unsigned int show_bits(GetBitContext *s, int n)
-{
-    register int tmp;
-    OPEN_READER_NOSIZE(re, s);
-    av_assert2(n>0 && n<=25);
-    UPDATE_CACHE(re, s);
-    tmp = SHOW_UBITS(re, s, n);
-    return tmp;
-}
+#endif
 
 static inline void skip_bits(GetBitContext *s, int n)
 {
+#ifdef CACHED_BITSTREAM_READER
+    if (n <= s->bits_left)
+        skip_remaining(s, n);
+    else {
+        n -= s->bits_left;
+        skip_remaining(s, s->bits_left);
+        if (n >= 64) {
+            unsigned skip = n;
+
+            n -= skip;
+            s->index += skip;
+        }
+        refill_32(s);
+        if (n)
+            skip_remaining(s, n);
+    }
+#else
     OPEN_READER(re, s);
     LAST_SKIP_BITS(re, s, n);
     CLOSE_READER(re, s);
+#endif
+}
+
+static inline void skip_bits_long(GetBitContext *s, int n)
+{
+#ifdef CACHED_BITSTREAM_READER
+    skip_bits(s, n);
+#else
+#if UNCHECKED_BITSTREAM_READER
+    s->index += n;
+#else
+    s->index += av_clip(n, -s->index, s->size_in_bits_plus8 - s->index);
+#endif
+#endif
 }
 
 static inline unsigned int get_bits1(GetBitContext *s)
 {
+#ifdef CACHED_BITSTREAM_READER
+    if (!s->bits_left)
+        refill_64(s);
+
+    return get_val(s, 1);
+#else
     unsigned int index = s->index;
     uint8_t result     = s->buffer[index >> 3];
 #ifdef BITSTREAM_READER_LE
@@ -328,6 +495,7 @@  static inline unsigned int get_bits1(GetBitContext *s)
     s->index = index;
 
     return result;
+#endif
 }
 
 static inline unsigned int show_bits1(GetBitContext *s)
@@ -348,6 +516,10 @@  static inline unsigned int get_bits_long(GetBitContext *s, int n)
     av_assert2(n>=0 && n<=32);
     if (!n) {
         return 0;
+#ifdef CACHED_BITSTREAM_READER
+    }
+    return get_bits(s, n);
+#else
     } else if (n <= MIN_CACHE_BITS) {
         return get_bits(s, n);
     } else {
@@ -359,6 +531,7 @@  static inline unsigned int get_bits_long(GetBitContext *s, int n)
         return ret | get_bits(s, n - 16);
 #endif
     }
+#endif
 }
 
 /**
@@ -442,6 +615,10 @@  static inline int init_get_bits(GetBitContext *s, const uint8_t *buffer,
     s->buffer_end         = buffer + buffer_size;
     s->index              = 0;
 
+#ifdef CACHED_BITSTREAM_READER
+    refill_64(s);
+#endif
+
     return ret;
 }
 
@@ -543,6 +720,19 @@  static inline const uint8_t *align_get_bits(GetBitContext *s)
         SKIP_BITS(name, gb, n);                                 \
     } while (0)
 
+/* Return the LUT element for the given bitstream configuration. */
+static inline int set_idx(GetBitContext *s, int code, int *n, int *nb_bits,
+                          VLC_TYPE (*table)[2])
+{
+    unsigned idx;
+
+    *nb_bits = -*n;
+    idx = show_bits(s, *nb_bits) + code;
+    *n = table[idx][1];
+
+    return table[idx][0];
+}
+
 /**
  * Parse a vlc code.
  * @param bits is the number of bits which will be read at once, must be
@@ -554,6 +744,24 @@  static inline const uint8_t *align_get_bits(GetBitContext *s)
 static av_always_inline int get_vlc2(GetBitContext *s, VLC_TYPE (*table)[2],
                                      int bits, int max_depth)
 {
+#ifdef CACHED_BITSTREAM_READER
+    int nb_bits;
+    unsigned idx = show_bits(s, bits);
+    int code = table[idx][0];
+    int n    = table[idx][1];
+
+    if (max_depth > 1 && n < 0) {
+        skip_remaining(s, bits);
+        code = set_idx(s, code, &n, &nb_bits, table);
+        if (max_depth > 2 && n < 0) {
+            skip_remaining(s, nb_bits);
+            code = set_idx(s, code, &n, &nb_bits, table);
+        }
+    }
+    skip_remaining(s, n);
+
+    return code;
+#else
     int code;
 
     OPEN_READER(re, s);
@@ -564,6 +772,7 @@  static av_always_inline int get_vlc2(GetBitContext *s, VLC_TYPE (*table)[2],
     CLOSE_READER(re, s);
 
     return code;
+#endif
 }
 
 static inline int decode012(GetBitContext *gb)