From: Michael Niedermayer <michael@niedermayer.cc>
To: FFmpeg development discussions and patches <ffmpeg-devel@ffmpeg.org>
Subject: [FFmpeg-devel] [PATCH] avcodec/ffv1: Implement 2D RLE for remap
Date: Sat, 22 Mar 2025 19:01:39 +0100
Message-ID: <20250322180139.3462267-1-michael@niedermayer.cc> (raw)
ATM this performs as well or better as any other algorithm tried.
Its simple for the decoder.
On the encoder side complexity depends on how parameters are
choosen. But with a fixed mul_count of 1 and basic heuristic
it performs as well as any more complex choice i tried so far.
The encoder code here is flexible and allows mul_count > 1
and also can easily be used to exactly test various parameters.
Sponsored-by: Sovereign Tech Fund
Signed-off-by: Michael Niedermayer <michael@niedermayer.cc>
---
libavcodec/ffv1dec.c | 77 +++++++++++-----
libavcodec/ffv1enc.c | 205 ++++++++++++++++++++++++++++++++++---------
2 files changed, 218 insertions(+), 64 deletions(-)
diff --git a/libavcodec/ffv1dec.c b/libavcodec/ffv1dec.c
index f254c875a3f..19eb546d3f1 100644
--- a/libavcodec/ffv1dec.c
+++ b/libavcodec/ffv1dec.c
@@ -274,6 +274,17 @@ static void slice_set_damaged(FFV1Context *f, FFV1SliceContext *sc)
f->frame_damaged = 1;
}
+static int decode_current_mul(RangeCoder *rc, uint8_t state[32], int *mul, int mul_count, int64_t i)
+{
+ int ndx = (i * mul_count) >> 32;
+ av_assert2(ndx <= 4096U);
+
+ if (mul[ndx] < 0)
+ mul[ndx] = ff_ffv1_get_symbol(rc, state, 0) & 0x3FFFFFFF;
+
+ return mul[ndx];
+}
+
static int decode_remap(FFV1Context *f, FFV1SliceContext *sc)
{
unsigned int end = f->avctx->bits_per_raw_sample == 32 ? 0xFFFFFFFF : 0xFFFF;
@@ -282,33 +293,53 @@ 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][3][32];
int64_t i;
+ int mul[4096+1];
+ int mul_count;
+
memset(state, 128, sizeof(state));
- for (i=0; i <= end ; i++) {
- unsigned run = get_symbol_inline(&sc->c, state[lu], 0);
- if (run > end - i + 1)
- return AVERROR_INVALIDDATA;
- if (lu) {
- lu ^= !run;
- while (run--) {
- if (end == 0xFFFF) {
- sc->fltmap [p][j++] = i ^ ((i& 0x8000) ? 0 : flip);
- } else
- sc->fltmap32[p][j++] = i ^ ((i&0x80000000) ? 0 : flip);
- i++;
- }
- } else {
- i += run;
- if (i <= end) {
- if (end == 0xFFFF) {
- sc->fltmap [p][j++] = i ^ ((i& 0x8000) ? 0 : flip);
- } else {
- sc->fltmap32[p][j++] = i ^ ((i&0x80000000) ? 0 : flip);
- }
+ 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] = -1;
+
+ }
+ mul[mul_count] = 1;
+
+ memset(state, 128, sizeof(state));
+ int current_mul = 1;
+ for (i=0; i <= end ;) {
+ unsigned run = get_symbol_inline(&sc->c, state[lu][0], 0);
+ unsigned run0 = lu ? 0 : run;
+ unsigned run1 = lu ? run : 1;
+
+ i += run0 * current_mul;
+
+ while (run1--) {
+ 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;
}
- lu ^= !run;
+ if (i == end)
+ break;
+ if (i - 1 > end || j > 65535)
+ return AVERROR_INVALIDDATA;
+ if (end == 0xFFFF) {
+ sc->fltmap [p][j++] = i ^ ((i& 0x8000) ? 0 : flip);
+ } else
+ sc->fltmap32[p][j++] = i ^ ((i&0x80000000) ? 0 : flip);
+ i++;
+ current_mul = decode_current_mul(&sc->c, state[0][2], mul, mul_count, i);
+ }
+ if (lu) {
+ i += current_mul;
}
+ lu ^= !run;
}
}
return 0;
diff --git a/libavcodec/ffv1enc.c b/libavcodec/ffv1enc.c
index e557e7fcdfe..5b251ac2e80 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);
@@ -1258,59 +1261,179 @@ static void load_rgb_float32_frame(FFV1Context *f, FFV1SliceContext *sc,
AV_QSORT(unit[3], i, Unit, CMP);
}
+typedef struct RemapEncoderState {
+ int delta_stack[65536]; //We need to encode the run value before the adjustments, this stores the adjustments until we know the length of the run
+ int16_t index_stack[65537]; //only needed with multiple segments
+ uint8_t state[2][3][32];
+ int mul[4096+1];
+ RangeCoder rc;
+ int lu;
+ int run;
+ int64_t last_val;
+ int compact_index;
+ int mul_count;
+ int i;
+ int pixel_num;
+ int p;
+} RemapEncoderState;
+
+static inline void copy_state(RemapEncoderState *dst, const RemapEncoderState *src)
+{
+ dst->rc = src->rc;
+ memcpy(dst->mul, src->mul, (src->mul_count + 1) * sizeof(src->mul[0]));
+ memcpy(dst->delta_stack, src->delta_stack, src->run * sizeof(src->delta_stack[0]));
+ memcpy(dst->index_stack, src->index_stack, (src->run + 1) * sizeof(src->index_stack[0]));
+ memcpy(dst->state, src->state, sizeof(dst->state));
+ dst->lu = src->lu;
+ dst->run = src->run;
+ dst->last_val = src->last_val;
+ dst->compact_index = src->compact_index;
+ dst->mul_count = src->mul_count;
+ dst->i = src->i;
+ dst->pixel_num = src->pixel_num;
+ dst->p = src->p;
+}
+
+static inline void encode_mul(RemapEncoderState *s, int mul_index)
+{
+ av_assert2(s->mul[ mul_index ]);
+ if (s->mul[ mul_index ] < 0) {
+ s->mul[ mul_index ] *= -1;
+ put_symbol_inline(&s->rc, s->state[0][2], s->mul[ mul_index ], 0, NULL, NULL);
+ }
+}
+
+static int encode_float32_remap_segment(FFV1SliceContext *sc, Unit unit[4][65536],
+ RemapEncoderState *state_arg, int update, int final)
+{
+ RemapEncoderState s;
+
+ copy_state(&s, state_arg);
+
+ if (s.i == 0) {
+ memset(s.state, 128, sizeof(s.state));
+ put_symbol(&s.rc, s.state[0][0], s.mul_count, 0);
+ memset(s.state, 128, sizeof(s.state));
+ s.last_val = -1;
+ s.compact_index = -1;
+ s.lu = 0;
+ s.run = 0;
+ }
+
+ for (; s.i < s.pixel_num+1; s.i++) {
+ int64_t val;
+ if (s.i == s.pixel_num) {
+ if (s.last_val == 0xFFFFFFFF) {
+ break;
+ } else {
+ val = 1LL<<32;
+ }
+ } else
+ val = unit[s.p][s.i].val;
+
+ if (s.last_val != val) {
+ int current_mul_index = ((s.last_val + 1) * s.mul_count) >> 32;
+ int current_mul = s.i ? FFABS(s.mul[current_mul_index]) : 1;
+ int64_t delta = 0;
+ av_assert2(s.last_val < val);
+ av_assert2(current_mul > 0);
+
+ if (current_mul > 1) {
+ delta = val - s.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 += s.last_val;
+ }
+ av_assert2(s.last_val < val);
+ if (s.lu) {
+ s.index_stack[s.run] = current_mul_index;
+ av_assert2(s.run < FF_ARRAY_ELEMS(s.delta_stack));
+ if (val - s.last_val == 1) {
+ s.delta_stack[s.run] = delta;
+ s.run ++;
+ s.last_val += current_mul + delta;
+ } else {
+ put_symbol_inline(&s.rc, s.state[s.lu][0], s.run, 0, NULL, NULL);
+ for(int k=0; k<s.run; k++) {
+ int stack_mul = s.mul[ s.index_stack[k] ];
+ if (stack_mul>1)
+ put_symbol_inline(&s.rc, s.state[s.lu][1], s.delta_stack[k], 1, NULL, NULL);
+ encode_mul(&s, s.index_stack[k+1]);
+ }
+ if (s.run == 0)
+ s.lu ^= 1;
+ s.run = 0;
+ s.i--; // we did not encode val so we need to backstep
+ s.last_val += current_mul;
+ continue;
+ }
+ } else {
+ av_assert2(s.run == 0);
+ put_symbol_inline(&s.rc, s.state[s.lu][0], val - s.last_val - 1, 0, NULL, NULL);
+ if (current_mul > 1)
+ put_symbol_inline(&s.rc, s.state[s.lu][1], delta, 1, NULL, NULL);
+ if (val - s.last_val == 1)
+ s.lu ^= 1;
+ s.last_val += (val - s.last_val) * current_mul + delta;
+
+ encode_mul(&s, ((s.last_val + 1) * s.mul_count) >> 32);
+ }
+ s.compact_index ++;
+ }
+ if (final && s.i < s.pixel_num)
+ sc->bitmap[s.p][unit[s.p][s.i].ndx] = s.compact_index;
+ }
+
+ if (update) {
+ copy_state(state_arg, &s);
+ }
+ return get_rac_count(&s.rc);
+}
+
static void encode_float32_remap(FFV1Context *f, FFV1SliceContext *sc,
const uint8_t *src[4], Unit unit[4][65536])
{
- int pixel_num = sc->slice_width * sc->slice_height;
+ RemapEncoderState s;
+ s.pixel_num = sc->slice_width * sc->slice_height;
- av_assert0 (pixel_num <= 65536);
+ av_assert0 (s.pixel_num <= 65536);
for (int p= 0; p < 1 + 2*f->chroma_planes + f->transparency; p++) {
- int lu = 0;
- uint8_t state[2][32];
- int run = 0;
+ float score_tab[16] = {0};
int64_t last_val = -1;
- int compact_index = -1;
+ s.rc = sc->c;
+ s.i = 0;
+ s.p = p;
- memset(state, 128, sizeof(state));
- for (int i= 0; i<pixel_num+1; i++) {
- int64_t val;
- if (i == pixel_num) {
- if (last_val == 0xFFFFFFFF) {
- break;
- } else {
- val = 1LL<<32;
- }
- } else
- val = unit[p][i].val;
+ s.mul_count = 1;
- if (last_val != val) {
+ for (int i= 0; i<s.pixel_num; i++) {
+ int64_t val = unit[p][i].val;
+ if (val != last_val) {
av_assert2(last_val < val);
- if (lu) {
- if (val - last_val == 1) {
- run ++;
- last_val = val;
- } else {
- put_symbol_inline(&sc->c, state[lu], run, 0, NULL, NULL);
- if (run == 0)
- lu ^= 1;
- run = 0;
- i--; // we did not encode val so we need to backstep
- last_val ++;
- continue;
- }
- } else {
- av_assert2(run == 0);
- put_symbol_inline(&sc->c, state[lu], val - last_val - 1, 0, NULL, NULL);
- if (val - last_val == 1)
- lu ^= 1;
- last_val = val;
+ for(int si= 0; si < FF_ARRAY_ELEMS(score_tab); si++) {
+ int64_t delta = val - last_val;
+ int mul = last_val < 0 ? 1 : (1<<si);
+ int64_t cost = FFMAX((delta + mul/2) / mul, 1);
+ score_tab[si] += log2(cost) + fabs(delta - cost*mul);
}
- compact_index ++;
+ last_val = val;
}
- if (i < pixel_num)
- sc->bitmap[p][unit[p][i].ndx] = compact_index;
}
+ int best_index = 0;
+ for(int si= 1; si < FF_ARRAY_ELEMS(score_tab); si++) {
+ if (score_tab[si] < score_tab[ best_index ])
+ best_index = si;
+ }
+ s.mul[0] = -1 << best_index;
+ s.mul[s.mul_count] = 1;
+
+ encode_float32_remap_segment(sc, unit, &s, 1, 1);
+
+ sc->c = s.rc;
}
}
--
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".
next reply other threads:[~2025-03-22 18:01 UTC|newest]
Thread overview: 11+ messages / expand[flat|nested] mbox.gz Atom feed top
2025-03-22 18:01 Michael Niedermayer [this message]
-- strict thread matches above, loose matches on Subject: below --
2025-03-20 22:30 Michael Niedermayer
2025-03-20 23:07 ` Lynne
2025-03-21 20:13 ` Michael Niedermayer
2025-03-21 21:12 ` Michael Niedermayer
2025-03-21 21:36 ` Michael Niedermayer
2025-03-21 22:22 ` Michael Niedermayer
2025-03-22 17:45 ` Michael Niedermayer
2025-03-22 17:54 ` Jerome Martinez
2025-03-24 1:53 ` Michael Niedermayer
2025-03-24 12:31 ` Michael Niedermayer
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20250322180139.3462267-1-michael@niedermayer.cc \
--to=michael@niedermayer.cc \
--cc=ffmpeg-devel@ffmpeg.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Git Inbox Mirror of the ffmpeg-devel mailing list - see https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
This inbox may be cloned and mirrored by anyone:
git clone --mirror https://master.gitmailbox.com/ffmpegdev/0 ffmpegdev/git/0.git
# If you have public-inbox 1.1+ installed, you may
# initialize and index your mirror using the following commands:
public-inbox-init -V2 ffmpegdev ffmpegdev/ https://master.gitmailbox.com/ffmpegdev \
ffmpegdev@gitmailbox.com
public-inbox-index ffmpegdev
Example config snippet for mirrors.
AGPL code for this site: git clone https://public-inbox.org/public-inbox.git