[FFmpeg-devel,3/4] zmbvenc: Prevent memory/math overflows in block_cmp()

Submitted by matthew.w.fearnley@gmail.com on Dec. 19, 2018, 10 p.m.

Details

Message ID 20181219220003.27225-3-matthew.w.fearnley@gmail.com
State New
Headers show

Commit Message

matthew.w.fearnley@gmail.com Dec. 19, 2018, 10 p.m.
From: Matthew Fearnley <matthew.w.fearnley@gmail.com>

score_tab[] was only declared/initialised for elements 0..255, but with
block sizes set to 16*16, it was possible to reach 256.

This limit could also be overflowed in the histogram, because it was
declared with a uint8_t type.

This can be fixed, and also allow different ZMBV_BLOCK sizes, by making
score_tab[] with (ZMBV_BLOCK*ZMBV_BLOCK+1) elements, and declaring
histogram[] to use a uint16_t type.

Note: the maximum block size possible for PAL8 is 255*255 bytes, which is close
to the uint16_t limit.  To support full-colour pixel formats, a uint32_t could
potentially be required.
---
 libavcodec/zmbvenc.c | 8 +++++---
 1 file changed, 5 insertions(+), 3 deletions(-)

Comments

Tomas Härdin Dec. 20, 2018, 4:30 p.m.
ons 2018-12-19 klockan 22:00 +0000 skrev matthew.w.fearnley@gmail.com:
> > From: Matthew Fearnley <matthew.w.fearnley@gmail.com>
> 
> score_tab[] was only declared/initialised for elements 0..255, but with
> block sizes set to 16*16, it was possible to reach 256.
> 
> This limit could also be overflowed in the histogram, because it was
> declared with a uint8_t type.
> 
> This can be fixed, and also allow different ZMBV_BLOCK sizes, by making
> score_tab[] with (ZMBV_BLOCK*ZMBV_BLOCK+1) elements, and declaring
> histogram[] to use a uint16_t type.
> 
> Note: the maximum block size possible for PAL8 is 255*255 bytes, which is close
> to the uint16_t limit.  To support full-colour pixel formats, a uint32_t could
> potentially be required.

So a potential future encoder improvement would be to try different
block sizes? Could be a fun project for someone, like a GSoC
qualification task

> @@ -69,7 +69,7 @@ static inline int block_cmp(ZmbvEncContext *c, uint8_t *src, int stride,
>  {
>      int sum = 0;
>      int i, j;
> -    uint8_t histogram[256] = {0};
> +    uint16_t histogram[256] = {0};
>  
>      /* build frequency histogram of byte values for src[] ^ src2[] */
>      *xored = 0;
> @@ -285,7 +285,9 @@ static av_cold int encode_init(AVCodecContext *avctx)
>      int i;
>      int lvl = 9;
>  
> -    for(i=1; i<256; i++)
> +    /* entropy score table for block_cmp() */
> +    c->score_tab[0] = 0;
> +    for(i = 1; i <= ZMBV_BLOCK * ZMBV_BLOCK; i++)
>          c->score_tab[i] = -i * log2(i / (double)(ZMBV_BLOCK * ZMBV_BLOCK)) * 256;

It strikes me that due to the uint8_t overflow the old code actually
worked correctly, but only incidentally..

Looks good!

/Tomas
matthew.w.fearnley@gmail.com Dec. 22, 2018, 3:42 p.m.
> On 20 Dec 2018, at 16:30, Tomas Härdin <tjoppen@acc.umu.se> wrote:
> 
> ons 2018-12-19 klockan 22:00 +0000 skrev matthew.w.fearnley@gmail.com:
>>> From: Matthew Fearnley <matthew.w.fearnley@gmail.com>
>> 
>> score_tab[] was only declared/initialised for elements 0..255, but with
>> block sizes set to 16*16, it was possible to reach 256.
>> 
>> This limit could also be overflowed in the histogram, because it was
>> declared with a uint8_t type.
>> 
>> This can be fixed, and also allow different ZMBV_BLOCK sizes, by making
>> score_tab[] with (ZMBV_BLOCK*ZMBV_BLOCK+1) elements, and declaring
>> histogram[] to use a uint16_t type.
>> 
>> Note: the maximum block size possible for PAL8 is 255*255 bytes, which is close
>> to the uint16_t limit.  To support full-colour pixel formats, a uint32_t could
>> potentially be required.
> 
> So a potential future encoder improvement would be to try different
> block sizes? Could be a fun project for someone, like a GSoC
> qualification task

Yeah. The header allows for block dimensions up to 255, and the width and height can be different from each other.

They can technically be changed in each keyframe header, but I’ve not tested how the decoder handles that..

>> @@ -69,7 +69,7 @@ static inline int block_cmp(ZmbvEncContext *c, uint8_t *src, int stride,
>>  {
>>      int sum = 0;
>>      int i, j;
>> -    uint8_t histogram[256] = {0};
>> +    uint16_t histogram[256] = {0};
>>  
>>      /* build frequency histogram of byte values for src[] ^ src2[] */
>>      *xored = 0;
>> @@ -285,7 +285,9 @@ static av_cold int encode_init(AVCodecContext *avctx)
>>      int i;
>>      int lvl = 9;
>>  
>> -    for(i=1; i<256; i++)
>> +    /* entropy score table for block_cmp() */
>> +    c->score_tab[0] = 0;
>> +    for(i = 1; i <= ZMBV_BLOCK * ZMBV_BLOCK; i++)
>>          c->score_tab[i] = -i * log2(i / (double)(ZMBV_BLOCK * ZMBV_BLOCK)) * 256;
> 
> It strikes me that due to the uint8_t overflow the old code actually
> worked correctly, but only incidentally..

It’s almost ingenious, the way it manages that. I almost didn’t want to change it..

> Looks good!

Thanks :)

Patch hide | download patch | download mbox

diff --git a/libavcodec/zmbvenc.c b/libavcodec/zmbvenc.c
index 0e8ee5ce31..0ebae1b254 100644
--- a/libavcodec/zmbvenc.c
+++ b/libavcodec/zmbvenc.c
@@ -55,7 +55,7 @@  typedef struct ZmbvEncContext {
     int keyint, curfrm;
     z_stream zstream;
 
-    int score_tab[256];
+    int score_tab[ZMBV_BLOCK * ZMBV_BLOCK + 1];
 } ZmbvEncContext;
 
 
@@ -69,7 +69,7 @@  static inline int block_cmp(ZmbvEncContext *c, uint8_t *src, int stride,
 {
     int sum = 0;
     int i, j;
-    uint8_t histogram[256] = {0};
+    uint16_t histogram[256] = {0};
 
     /* build frequency histogram of byte values for src[] ^ src2[] */
     *xored = 0;
@@ -285,7 +285,9 @@  static av_cold int encode_init(AVCodecContext *avctx)
     int i;
     int lvl = 9;
 
-    for(i=1; i<256; i++)
+    /* entropy score table for block_cmp() */
+    c->score_tab[0] = 0;
+    for(i = 1; i <= ZMBV_BLOCK * ZMBV_BLOCK; i++)
         c->score_tab[i] = -i * log2(i / (double)(ZMBV_BLOCK * ZMBV_BLOCK)) * 256;
 
     c->avctx = avctx;