[FFmpeg-devel] [PATCH] avcodec/ffv1: Implement 2D RLE for remap

* [FFmpeg-devel] [PATCH] avcodec/ffv1: Implement 2D RLE for remap
@ 2025-03-20 22:30 Michael Niedermayer
  2025-03-20 23:07 ` Lynne
  0 siblings, 1 reply; 9+ messages in thread
From: Michael Niedermayer @ 2025-03-20 22:30 UTC (permalink / raw)
  To: FFmpeg development discussions and patches

This performs about as good as the non LRU system for 16bit and
better than then the LRU system for 16 converted to 32. So
its basically performing best in all cases we have atm making
the LRU system unneeded.

Sponsored-by: Sovereign Tech Fund
Signed-off-by: Michael Niedermayer <michael@niedermayer.cc>
---
 libavcodec/ffv1dec.c | 47 ++++++++++++++++++++++++++++--
 libavcodec/ffv1enc.c | 69 +++++++++++++++++++++++++++++++++++++++-----
 2 files changed, 106 insertions(+), 10 deletions(-)

diff --git a/libavcodec/ffv1dec.c b/libavcodec/ffv1dec.c
index d45aabbbde8..a28aeacfcbc 100644
--- a/libavcodec/ffv1dec.c
+++ b/libavcodec/ffv1dec.c
@@ -283,25 +283,66 @@ static int decode_remap(FFV1Context *f, FFV1SliceContext *sc)
     for (int p= 0; p < 1 + 2*f->chroma_planes + f->transparency; p++) {
         int j = 0;
         int lu = 0;
-        uint8_t state[2][32];
+        uint8_t state[2][2][32];
         int64_t i;
+        int mul[4096+1];
+        int mul_count;
+
+        memset(state, 128, sizeof(state));
+        mul_count = ff_ffv1_get_symbol(&sc->c, state[0][0], 0);
+
+        if (mul_count > 4096U)
+            return AVERROR_INVALIDDATA;
+        for (int i = 0; i<mul_count; i++) {
+            mul[i] = ff_ffv1_get_symbol(&sc->c, state[0][0], 0);
+
+            if (mul[i] > (1U<<30))
+                return AVERROR_PATCHWELCOME;
+        }
+        mul[mul_count] = 1;
+
         memset(state, 128, sizeof(state));
         for (i=0; i <= end ; i++) {
-            unsigned run = get_symbol_inline(&sc->c, state[lu], 0);
+            unsigned run = get_symbol_inline(&sc->c, state[lu][0], 0);
+
             if (run > end - i + 1)
                 return AVERROR_INVALIDDATA;
             if (lu) {
+                if (run > 65536 - j)
+                    return AVERROR_INVALIDDATA;
                 lu ^= !run;
                 while (run--) {
+                    int current_mul = mul[(i * mul_count) >> 32];
+
+                    if (current_mul > 1) {
+                        int delta = get_symbol_inline(&sc->c, state[lu][1], 1);
+
+                        if (delta <= -current_mul || delta > current_mul/2)
+                            return AVERROR_INVALIDDATA; //not sure we should check this
+                        i += current_mul - 1 + delta;
+                    }
                     if (end == 0xFFFF) {
                         sc->fltmap  [p][j++] = i ^ ((i&    0x8000) ? 0 : flip);
                     } else
                         sc->fltmap32[p][j++] = i ^ ((i&0x80000000) ? 0 : flip);
                     i++;
                 }
+                int current_mul = mul[(i * mul_count) >> 32];
+
+                i += current_mul - 1;
             } else {
-                i += run;
+                int current_mul = mul[(i * mul_count) >> 32];
+
+                if (current_mul > 1) {
+                    int delta = get_symbol_inline(&sc->c, state[lu][1], 1);
+                    if (delta <= -current_mul || delta > current_mul/2)
+                        return AVERROR_INVALIDDATA;  //not sure we should check this
+                    i += (run + 1) * current_mul - 1 + delta;
+                } else
+                    i += run;
                 if (i <= end) {
+                    if (j > 65535)
+                        return AVERROR_INVALIDDATA;
                     if (end == 0xFFFF) {
                         sc->fltmap  [p][j++] = i ^ ((i&    0x8000) ? 0 : flip);
                     } else {
diff --git a/libavcodec/ffv1enc.c b/libavcodec/ffv1enc.c
index e557e7fcdfe..cce091ad3c3 100644
--- a/libavcodec/ffv1enc.c
+++ b/libavcodec/ffv1enc.c
@@ -433,7 +433,7 @@ static void set_micro_version(FFV1Context *f)
         if (f->version == 3) {
             f->micro_version = 4;
         } else if (f->version == 4) {
-            f->micro_version = 6;
+            f->micro_version = 7;
         } else
             av_assert0(0);
 
@@ -1179,6 +1179,9 @@ static void encode_histogram_remap(FFV1Context *f, FFV1SliceContext *sc)
         int lu = 0;
         uint8_t state[2][32];
         int run = 0;
+
+        memset(state, 128, sizeof(state));
+        put_symbol(&sc->c, state[0], 0, 0);
         memset(state, 128, sizeof(state));
         for (int i= 0; i<65536; i++) {
             int ri = i ^ ((i&0x8000) ? 0 : flip);
@@ -1267,11 +1270,44 @@ static void encode_float32_remap(FFV1Context *f, FFV1SliceContext *sc,
 
     for (int p= 0; p < 1 + 2*f->chroma_planes + f->transparency; p++) {
         int lu = 0;
-        uint8_t state[2][32];
+        uint8_t state[2][2][32];
         int run = 0;
         int64_t last_val = -1;
         int compact_index = -1;
+        int mul[4096+1];
+        int mul_count;
+        int delta_stack[65536];
+
+        float score_tab[16] = {0};
+        int best_index = 0;
+        for (int i= 0; i<pixel_num; i++) {
+            int64_t val = unit[p][i].val;
+            if (val != last_val) {
+                av_assert2(last_val < val);
+                for(int si= 0; si < FF_ARRAY_ELEMS(score_tab); si++) {
+                    int64_t delta = val - last_val;
+                    int mul = 1<<si;
+                    int64_t cost = FFMAX((delta + mul/2)  / mul, 1);
+                    score_tab[si] += log2(cost) + fabs(delta - cost*mul);
+                }
+            }
+            last_val = val;
+        }
+        for(int si= 1; si < FF_ARRAY_ELEMS(score_tab); si++) {
+            if (score_tab[si] < score_tab[ best_index ])
+                best_index = si;
+        }
+        memset(state, 128, sizeof(state));
+        mul_count = 1;
+        put_symbol(&sc->c, state[0][0], mul_count, 0);
+        for (int i = 0; i<mul_count; i++) {
+            mul[i] = 1<<best_index;
+            put_symbol(&sc->c, state[0][0], mul[i], 0);
+        }
+        mul[mul_count] = 1;
 
+
+        last_val = -1;
         memset(state, 128, sizeof(state));
         for (int i= 0; i<pixel_num+1; i++) {
             int64_t val;
@@ -1285,26 +1321,45 @@ static void encode_float32_remap(FFV1Context *f, FFV1SliceContext *sc,
                 val = unit[p][i].val;
 
             if (last_val != val) {
+                int current_mul = mul[((last_val + 1) * mul_count) >> 32];
+                int64_t delta = 0;
+                av_assert2(last_val < val);
+                if (current_mul > 1) {
+                    delta = val - last_val;
+                    val = FFMAX(1, (delta + current_mul/2) / current_mul);
+
+                    delta -= val*current_mul;
+                    av_assert2(delta <= current_mul/2);
+                    av_assert2(delta > -current_mul);
+                    val += last_val;
+                }
                 av_assert2(last_val < val);
                 if (lu) {
                     if (val - last_val == 1) {
+                        av_assert2(run < FF_ARRAY_ELEMS(delta_stack));
+                        delta_stack[run] = delta;
                         run ++;
-                        last_val = val;
+                        last_val += current_mul + delta;
                     } else {
-                        put_symbol_inline(&sc->c, state[lu], run, 0, NULL, NULL);
+                        put_symbol_inline(&sc->c, state[lu][0], run, 0, NULL, NULL);
+                        if (current_mul>1)
+                            for(int k=0; k<run; k++)
+                                put_symbol_inline(&sc->c, state[lu][1], delta_stack[k], 1, NULL, NULL);
                         if (run == 0)
                             lu ^= 1;
                         run = 0;
                         i--; // we did not encode val so we need to backstep
-                        last_val ++;
+                        last_val += current_mul;
                         continue;
                     }
                 } else {
                     av_assert2(run == 0);
-                    put_symbol_inline(&sc->c, state[lu], val - last_val - 1, 0, NULL, NULL);
+                    put_symbol_inline(&sc->c, state[lu][0], val - last_val - 1, 0, NULL, NULL);
+                    if (current_mul > 1)
+                        put_symbol_inline(&sc->c, state[lu][1], delta, 1, NULL, NULL);
                     if (val - last_val == 1)
                         lu ^= 1;
-                    last_val = val;
+                    last_val += (val - last_val) * current_mul + delta;
                 }
                 compact_index ++;
             }
-- 
2.48.1

_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel

To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".

^ permalink raw reply	[flat|nested] 9+ messages in thread