[FFmpeg-devel] [RFC][PATCH] FFV1 range coder state transition table optimization
Michael Niedermayer
michaelni
Sun Oct 24 19:22:54 CEST 2010
Hi
Patch below does a slow iterative optimization of the state transition table
used in the ffv1 range coder.
A older & messier version of this was used to find the currently used default
table.
Iam not sure what to do with it. It seems too slow for general use, also its
frame based not gop based which means it likely works better if ones frames
are large, though this doesnt make it faster ...
If someone wants to clean this up further or has ideas on how to make it much
faster ... its all welcome.
So is also someone finding a better default table ...
note, i do not plan to commit this.
diff --git a/libavcodec/ffv1.c b/libavcodec/ffv1.c
index 825b926..799a371 100644
--- a/libavcodec/ffv1.c
+++ b/libavcodec/ffv1.c
@@ -40,6 +40,8 @@
#define MAX_QUANT_TABLES 8
#define MAX_CONTEXT_INPUTS 5
+#define TABLESEARCH 1
+
extern const uint8_t ff_log2_run[32];
static const int8_t quant3[256]={
@@ -228,6 +230,7 @@ typedef struct PlaneContext{
typedef struct FFV1Context{
AVCodecContext *avctx;
+ RangeCoder best_coder;
RangeCoder c;
GetBitContext gb;
PutBitContext pb;
@@ -745,6 +748,13 @@ static av_cold int init_slice_contexts(FFV1Context *f){
}
#if CONFIG_FFV1_ENCODER
+static void mark_used(uint8_t used[256], uint8_t one_state[256], int state){
+ used[ state]=
+ used[256-state]=1;
+ if(!used[ one_state[ state] ]) mark_used(used, one_state, one_state[ state]);
+ if(!used[ one_state[256-state] ]) mark_used(used, one_state, one_state[256-state]);
+}
+
static int write_extra_header(FFV1Context *f){
RangeCoder * const c= &f->c;
uint8_t state[CONTEXT_SIZE];
@@ -1005,8 +1015,34 @@ static int encode_frame(AVCodecContext *avctx, unsigned char *buf, int buf_size,
int used_count= 0;
uint8_t keystate=128;
uint8_t *buf_p;
- int i;
-
+ int aci, dir, i;
+ int best_size= 1<<30;
+
+#ifdef TABLESEARCH
+#undef rand
+
+ if(!f->best_coder.one_state[128])
+ f->best_coder= *c;
+ for(aci=3; aci<253; aci++){ //FIXME 256
+ for(dir=0; dir != -20; dir= dir<0 ? -dir : -(dir+1)){
+ if(f->best_coder.one_state[aci]+dir <1 || f->best_coder.one_state[aci]+dir>255)
+ continue;
+ if(f->best_coder.one_state[aci]+dir+1 < aci)
+ continue;
+ if(aci>242 && f->best_coder.one_state[aci]+dir < aci)
+ continue;
+ if(aci>242 && aci<252 && f->best_coder.one_state[aci]+dir <= aci)
+ continue;
+
+ memcpy(f->state_transition, f->best_coder.one_state, sizeof(f->state_transition));
+
+ f->state_transition[aci]+=dir;
+
+ for(i=0; i<f->slice_count; i++){
+ FFV1Context *fs= f->slice_context[i];
+ memset(fs->rc_stat, 0, sizeof(fs->rc_stat));
+ }
+#endif
ff_init_range_encoder(c, buf, buf_size);
ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
@@ -1019,6 +1055,9 @@ static int encode_frame(AVCodecContext *avctx, unsigned char *buf, int buf_size,
write_header(f);
clear_state(f);
}else{
+#ifdef TABLESEARCH
+ av_abort();
+#endif
put_rac(c, &keystate, 0);
p->key_frame= 0;
}
@@ -1072,6 +1111,64 @@ static int encode_frame(AVCodecContext *avctx, unsigned char *buf, int buf_size,
buf_p += bytes;
}
+#ifdef TABLESEARCH
+ int size= ff_rac_terminate(c);
+
+ if(size < best_size){
+ int j;
+ int print=dir;
+ best_size= size;
+ uint8_t used[256]={0};
+
+ memset(f->rc_stat, 0, sizeof(f->rc_stat));
+ for(j=0; j<f->slice_count; j++){
+ FFV1Context *fs= f->slice_context[j];
+ for(i=0; i<256; i++){
+ f->rc_stat[i][0] += fs->rc_stat[i][0];
+ f->rc_stat[i][1] += fs->rc_stat[i][1];
+ }
+ }
+ print |= sort_stt(f, c->one_state);
+ mark_used(used, c->one_state, 128);
+ for(i=3;i<254; i++){
+ if(!used[i]){
+ int array[4];
+ av_assert0(!used[256-i]);
+ av_log(NULL, AV_LOG_ERROR, "U%d ", i);
+ array[0]= c->one_state[ i-1];
+ array[1]= c->one_state[ i-2];
+ array[2]= c->one_state[ i+1];
+ array[3]= c->one_state[ i+2];
+ c->one_state[ i] = array[ rand()/(RAND_MAX/4+1) ];
+ array[0]= c->one_state[256-i-1];
+ array[1]= c->one_state[256-i-2];
+ array[2]= c->one_state[256-i+1];
+ array[3]= c->one_state[256-i+2];
+ c->one_state[256-i] = array[ rand()/(RAND_MAX/4+1) ];
+ }
+ }
+ for(i=255; !used[i]; i--)
+ c->one_state[i]= i;
+ for(i++; i<256; i++)
+ c->one_state[256-i]= c->one_state[256-i+1];
+
+ for(i=1; i<256; i++)
+ av_assert0(c->one_state[i]>0);
+
+ f->best_coder= *c;
+ if(print){
+ for(i=0; i<256; i++)
+ av_log(NULL ,AV_LOG_ERROR, "%4d", c->one_state[i]);
+ av_log(NULL ,AV_LOG_ERROR, " %d %d %d\n", aci, dir, size);
+ //we dont know the exact size of the new case after reordering so we force it to be redone
+ aci--;
+ break;
+ }
+ }
+ }
+ }
+#endif
+
if((avctx->flags&CODEC_FLAG_PASS1) && (f->picture_number&31)==0){
int j;
char *p= avctx->stats_out;
--
Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB
No human being will ever know the Truth, for even if they happen to say it
by chance, they would not even known they had done so. -- Xenophanes
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: Digital signature
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20101024/d75a2451/attachment.pgp>
More information about the ffmpeg-devel
mailing list