[FFmpeg-devel] [PATCH 3/4] zmbvenc: Prevent memory/math overflows in block_cmp()
From: Matthew Fearnley
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(-)
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;
--
2.17.1
___
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
[FFmpeg-devel] [PATCH 4/4] zmbvenc: use unsigned values for score calculations
From: Matthew Fearnley
All the values in score_tab are positive or 0, and so should be the sum
returned by block_cmp().
The logic in zmbv_me() assumes that all 'bv' values will be non-negative,
in order to guarantee an early return if ever bv==0.
---
libavcodec/zmbvenc.c | 7 ---
1 file changed, 4 insertions(+), 3 deletions(-)
diff --git a/libavcodec/zmbvenc.c b/libavcodec/zmbvenc.c
index 0ebae1b254..9e1b44f15d 100644
--- a/libavcodec/zmbvenc.c
+++ b/libavcodec/zmbvenc.c
@@ -63,11 +63,11 @@ typedef struct ZmbvEncContext {
* XXX should be optimized and moved to DSPContext
* TODO handle out of edge ME
*/
-static inline int block_cmp(ZmbvEncContext *c, uint8_t *src, int stride,
+static inline unsigned int block_cmp(ZmbvEncContext *c, uint8_t *src, int
stride,
uint8_t *src2, int stride2, int bw, int bh,
int *xored)
{
-int sum = 0;
+unsigned int sum = 0;
int i, j;
uint16_t histogram[256] = {0};
@@ -99,7 +99,8 @@ static inline int block_cmp(ZmbvEncContext *c, uint8_t *src,
int stride,
static int zmbv_me(ZmbvEncContext *c, uint8_t *src, int sstride, uint8_t *prev,
int pstride, int x, int y, int *mx, int *my, int *xored)
{
-int dx, dy, tx, ty, tv, bv, bw, bh;
+int dx, dy, tx, ty, bw, bh;
+unsigned int tv, bv;
int txored;
*mx = *my = 0;
--
2.17.1
___
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
[FFmpeg-devel] [PATCH 2/4] zmbvenc: ensure mx, my, xored are always set together in zmbv_me()
From: Matthew Fearnley
Store the value of *xored computed within block_cmp() in a local variable,
and only update the *xored parameter at the same time as *mx,*my are set.
This ensures that the value of *xored is accurate for the value of *mx,*my
whenever the function ends.
Note that the local variable is not needed in the intial block_cmp for (0,0)
because *mx,*my and *xored are all set there.
The previous logic worked by exiting early if ever !*xored, but put implicit
requirements on block_cmp() to:
- always return 0 if !xored
- never return a negative value
---
libavcodec/zmbvenc.c | 4 +++-
1 file changed, 3 insertions(+), 1 deletion(-)
diff --git a/libavcodec/zmbvenc.c b/libavcodec/zmbvenc.c
index 2f041dae32..0e8ee5ce31 100644
--- a/libavcodec/zmbvenc.c
+++ b/libavcodec/zmbvenc.c
@@ -100,6 +100,7 @@ static int zmbv_me(ZmbvEncContext *c, uint8_t *src, int
sstride, uint8_t *prev,
int pstride, int x, int y, int *mx, int *my, int *xored)
{
int dx, dy, tx, ty, tv, bv, bw, bh;
+int txored;
*mx = *my = 0;
bw = FFMIN(ZMBV_BLOCK, c->avctx->width - x);
@@ -111,11 +112,12 @@ static int zmbv_me(ZmbvEncContext *c, uint8_t *src, int
sstride, uint8_t *prev,
if(tx == x && ty == y) continue; // we already tested this block
dx = tx - x;
dy = ty - y;
-tv = block_cmp(c, src, sstride, prev + dx + dy * pstride, pstride,
bw, bh, xored);
+tv = block_cmp(c, src, sstride, prev + dx + dy * pstride, pstride,
bw, bh, );
if(tv < bv){
bv = tv;
*mx = dx;
*my = dy;
+ *xored = txored;
if(!bv) return 0;
}
}
--
2.17.1
___
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
[FFmpeg-devel] [PATCH 1/4] zmbvenc: don't sum the entropy when blocks are equal
From: Matthew Fearnley
If *xored is 0, then histogram[0]==bw*bh and histogram[1..255]==0.
Because histogram[0] is skipped over for the entropy calculation, the
return value is always 0 when *xored==0, so we don't need to waste time
calculating it.
This addition both clarifies the behaviour of the code and improves
the speed when the block matches.
---
libavcodec/zmbvenc.c | 5 +
1 file changed, 5 insertions(+)
diff --git a/libavcodec/zmbvenc.c b/libavcodec/zmbvenc.c
index 4d9147657d..2f041dae32 100644
--- a/libavcodec/zmbvenc.c
+++ b/libavcodec/zmbvenc.c
@@ -71,6 +71,7 @@ static inline int block_cmp(ZmbvEncContext *c, uint8_t *src,
int stride,
int i, j;
uint8_t histogram[256] = {0};
+/* build frequency histogram of byte values for src[] ^ src2[] */
*xored = 0;
for(j = 0; j < bh; j++){
for(i = 0; i < bw; i++){
@@ -82,6 +83,10 @@ static inline int block_cmp(ZmbvEncContext *c, uint8_t *src,
int stride,
src2 += stride2;
}
+/* early out if src and src2 are equal */
+if (!*xored) return 0;
+
+/* sum the entropy of the non-zero values */
for(i = 1; i < 256; i++)
sum += c->score_tab[histogram[i]];
--
2.17.1
___
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
[FFmpeg-devel] [PATCH] libavcodec/zmbvenc.c: don't allow motion estimation out of range.
From: Matthew Fearnley
The maximum allowable range for ZMBV motion estimation is [-64..63], since
the dx,dy values are each stored in the upper 7 bits of a signed char.
(Previously, the range was capped in the code to 127, resulting in an
effective range of [-127..126])
Also fix a range error in the zmbv_me() for-loops ('<' instead of '<='),
which made the limit asymmetrical [-N..N-1], and also prevented it from
reaching the blocks touching the bottom/right edges.
The range is now more symmetrical [-N..N], although this requires separate
range caps of 64 and 63 for negative and positive dx,dy.
Practically, this patch fixes graphical glitches e.g. when reencoding the
Commander Keen sample video with me_range 65 or higher:
ffmpeg -i keen4e_000.avi -c:v zmbv -me_range 65 keen4e_me65.avi
(Glitches are worse with higher me_range values up to 127.)
---
libavcodec/zmbvenc.c | 16 ++--
1 file changed, 10 insertions(+), 6 deletions(-)
diff --git a/libavcodec/zmbvenc.c b/libavcodec/zmbvenc.c
index 4d9147657d..300a53b08e 100644
--- a/libavcodec/zmbvenc.c
+++ b/libavcodec/zmbvenc.c
@@ -45,7 +45,7 @@
typedef struct ZmbvEncContext {
AVCodecContext *avctx;
-int range;
+int lrange, urange;
uint8_t *comp_buf, *work_buf;
uint8_t pal[768];
uint32_t pal2[256]; //for quick comparisons
@@ -101,8 +101,8 @@ static int zmbv_me(ZmbvEncContext *c, uint8_t *src, int
sstride, uint8_t *prev,
bh = FFMIN(ZMBV_BLOCK, c->avctx->height - y);
bv = block_cmp(c, src, sstride, prev, pstride, bw, bh, xored);
if(!bv) return 0;
-for(ty = FFMAX(y - c->range, 0); ty < FFMIN(y + c->range, c->avctx->height
- bh); ty++){
-for(tx = FFMAX(x - c->range, 0); tx < FFMIN(x + c->range,
c->avctx->width - bw); tx++){
+for(ty = FFMAX(y - c->lrange, 0); ty <= FFMIN(y + c->urange,
c->avctx->height - bh); ty++){
+for(tx = FFMAX(x - c->lrange, 0); tx <= FFMIN(x + c->urange,
c->avctx->width - bw); tx++){
if(tx == x && ty == y) continue; // we already tested this block
dx = tx - x;
dy = ty - y;
@@ -285,9 +285,13 @@ static av_cold int encode_init(AVCodecContext *avctx)
c->curfrm = 0;
c->keyint = avctx->keyint_min;
-c->range = 8;
-if(avctx->me_range > 0)
-c->range = FFMIN(avctx->me_range, 127);
+
+// Motion estimation range: maximum distance is -64..63
+c->lrange = c->urange = 8;
+if(avctx->me_range > 0){
+c->lrange = FFMIN(avctx->me_range, 64);
+c->urange = FFMIN(avctx->me_range, 63);
+}
if(avctx->compression_level >= 0)
lvl = avctx->compression_level;
--
2.17.1
___
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
