[xiph-commits] r16186 - branches/theora-thusnelda/lib/enc
tterribe at svn.xiph.org
tterribe at svn.xiph.org
Thu Jun 25 21:00:08 PDT 2009
Author: tterribe
Date: 2009-06-25 21:00:07 -0700 (Thu, 25 Jun 2009)
New Revision: 16186
Modified:
branches/theora-thusnelda/lib/enc/tokenize.c
Log:
Remove the globally optimal (but dog-slow) tokenization code.
It was only left in the last commit so that a version of it ended up in the
repository; it was not intended to ever actually be used.
Modified: branches/theora-thusnelda/lib/enc/tokenize.c
===================================================================
--- branches/theora-thusnelda/lib/enc/tokenize.c 2009-06-26 02:52:40 UTC (rev 16185)
+++ branches/theora-thusnelda/lib/enc/tokenize.c 2009-06-26 04:00:07 UTC (rev 16186)
@@ -664,560 +664,6 @@
return bits;
}
-#if 0
-/*This version of the above finds the globally optimal solution, but is very
- computationally expensive, since it considers all possible partitions of a
- zero run (and thus is quadratic in the number of coefficients).*/
-int oc_enc_tokenize_ac(oc_enc_ctx *_enc,int _pli,ptrdiff_t _fragi,
- ogg_int16_t *_qdct,const ogg_uint16_t *_dequant,const ogg_int16_t *_dct,
- int _zzi,oc_token_checkpoint **_stack,int _acmin){
- oc_token_checkpoint *stack;
- ogg_uint32_t d2_accum[64];
- oc_quant_token tokens[64][4];
- unsigned char ntokens[64];
- unsigned char best_ti[64];
- ogg_uint16_t *eob_run;
- ogg_int32_t lambda;
- ogg_uint32_t cost;
- ogg_uint32_t sum_d2;
- int bits;
- int eob;
- int token;
- int eb;
- int next;
- int huffi;
- int zzi_max;
- int zzi;
- int ti;
- int zzj;
- int qc;
- lambda=_enc->lambda;
- huffi=_enc->huff_idxs[_enc->state.frame_type][1][_pli+1>>1];
- eob_run=_enc->eob_run[_pli];
- memset(tokens[0],0,sizeof(tokens[0]));
- ntokens[0]=1;
- best_ti[0]=0;
- sum_d2=0;
- zzi_max=_zzi;
- for(zzi=OC_MINI(_zzi,63);zzi>0;zzi--){
- ogg_uint32_t best_cost;
- int best_bits;
- int best_next;
- int best_token;
- int best_eb;
- int best_qc;
- int flush_bits;
- ogg_uint32_t d2;
- int c;
- int s;
- int tj;
- eob=eob_run[zzi];
- /*TODO: Move this into the tokenization state.*/
- flush_bits=eob>0?oc_token_bits(_enc,huffi,zzi,oc_make_eob_token(eob)):0;
- qc=_qdct[zzi];
- c=_dct[OC_FZIG_ZAG[zzi]];
- s=-(c<0);
- c=c+s^s;
- qc=qc+s^s;
- d2=c*(ogg_int32_t)c;
- sum_d2+=d2;
- d2_accum[zzi]=sum_d2;
- /*The hard case: attempt to code a zero here.*/
- if(qc<64&&(zzi>=_acmin||qc==0)){
- int zzk;
- int tk;
- /*Our base case is to code an EOB token.*/
- /*if(zzi_max<_zzi){
- best_bits=0;
- best_cost=0x7FFFFFFF;
- }
- else*/{
- eob=eob_run[zzi];
- if(eob<4095){
- best_bits=oc_token_bits(_enc,huffi,zzi,oc_make_eob_token(eob+1))
- -flush_bits;
- }
- else best_bits=oc_token_bits(_enc,huffi,zzi,OC_DCT_EOB1_TOKEN);
- best_cost=sum_d2+best_bits*lambda;
- }
- best_next=0;
- /*This token is just a marker.*/
- best_token=OC_DCT_EOB1_TOKEN;
- best_eb=0;
- best_qc=0;
- zzj=zzi+1;
- if(zzj<zzi_max){
- int zzj_max;
- /*Try a raw zero run.*/
- tj=best_ti[zzj];
- bits=flush_bits+oc_token_bits(_enc,huffi,zzi,OC_DCT_SHORT_ZRL_TOKEN);
- cost=d2+lambda*bits+tokens[zzj][tj].cost;
- if(cost<best_cost){
- best_next=(zzj<<2)+tj;
- best_token=OC_DCT_SHORT_ZRL_TOKEN;
- best_eb=0;
- best_cost=cost;
- best_bits=bits+tokens[zzj][tj].bits;
- best_qc=0;
- }
- /*Try a +/- 1 combo token.*/
- if(ntokens[zzj]>1){
- next=tokens[zzj][1].next;
- tk=next&3;
- zzk=next>>2;
- bits=flush_bits+oc_token_bits(_enc,huffi,zzi,OC_DCT_RUN_CAT1A)
- -(tokens[zzj][1].bits-tokens[zzk][tk].bits);
- cost=d2+lambda*bits+tokens[zzj][1].cost;
- if(cost<best_cost){
- best_next=next;
- best_token=OC_DCT_RUN_CAT1A;
- best_eb=tokens[zzj][1].token-OC_ONE_TOKEN;
- best_cost=cost;
- best_bits=bits+tokens[zzj][1].bits;
- best_qc=tokens[zzj][1].qc;
- }
- /*Try a +/- 2/3 combo token.*/
- if(ntokens[zzj]>2){
- next=tokens[zzj][2].next;
- tk=next&3;
- zzk=next>>2;
- bits=flush_bits+oc_token_bits(_enc,huffi,zzi,OC_DCT_RUN_CAT2A)
- -(tokens[zzj][2].bits-tokens[zzk][tk].bits);
- cost=d2+lambda*bits+tokens[zzj][2].cost;
- if(cost<best_cost){
- int cat;
- best_next=next;
- best_token=OC_DCT_RUN_CAT2A;
- cat=tokens[zzj][2].token-OC_TWO_TOKEN;
- best_eb=(((cat&1)|tokens[zzj][2].eb)<<1)+(cat>>1);
- best_cost=cost;
- best_bits=bits+tokens[zzj][2].bits;
- best_qc=tokens[zzj][2].qc;
- }
- }
- }
- /*Ensure a +/- 2/3 run can extend to the DC coefficient.*/
- zzj_max=zzi+3+(zzi+62>>6);
- for(zzj++;zzj<zzj_max&&zzj<zzi_max;zzj++){
- d2=d2_accum[zzi]-d2_accum[zzj];
- /*Try a raw zero run.*/
- tj=best_ti[zzj];
- bits=flush_bits+oc_token_bits(_enc,huffi,zzi,OC_DCT_SHORT_ZRL_TOKEN);
- cost=d2+lambda*bits+tokens[zzj][tj].cost;
- if(cost<best_cost){
- best_next=(zzj<<2)+tj;
- best_token=OC_DCT_SHORT_ZRL_TOKEN;
- best_eb=zzj-zzi-1;
- best_cost=cost;
- best_bits=bits+tokens[zzj][tj].bits;
- best_qc=0;
- }
- /*Try a +/- 1 combo token.*/
- if(ntokens[zzj]>1){
- next=tokens[zzj][1].next;
- tk=next&3;
- zzk=next>>2;
- token=OC_DCT_RUN_CAT1A+zzj-zzi-1;
- bits=flush_bits+oc_token_bits(_enc,huffi,zzi,token)
- -(tokens[zzj][1].bits-tokens[zzk][tk].bits);
- cost=d2+lambda*bits+tokens[zzj][1].cost;
- if(cost<best_cost){
- best_next=next;
- best_token=token;
- best_eb=tokens[zzj][1].token-OC_ONE_TOKEN;
- best_cost=cost;
- best_bits=bits+tokens[zzj][1].bits;
- best_qc=tokens[zzj][1].qc;
- }
- /*Try a +/- 2/3 combo token.*/
- if(ntokens[zzj]>2){
- next=tokens[zzj][2].next;
- tk=next&3;
- zzk=next>>2;
- bits=flush_bits+oc_token_bits(_enc,huffi,zzi,OC_DCT_RUN_CAT2B)
- -(tokens[zzj][2].bits-tokens[zzk][tk].bits);
- cost=d2+lambda*bits+tokens[zzj][2].cost;
- if(cost<best_cost){
- int cat;
- best_next=next;
- best_token=OC_DCT_RUN_CAT2B;
- cat=tokens[zzj][2].token-OC_TWO_TOKEN;
- best_eb=(((cat&1)|tokens[zzj][2].eb)<<2)+(cat&2)+zzj-zzi-2;
- best_cost=cost;
- best_bits=bits+tokens[zzj][2].bits;
- best_qc=tokens[zzj][2].qc;
- }
- }
- }
- }
- if(zzj<zzi_max){
- zzj_max=zzi+6;
- for(;zzj<zzj_max&&zzj<zzi_max;zzj++){
- d2=d2_accum[zzi]-d2_accum[zzj];
- /*Try a raw zero run.*/
- tj=best_ti[zzj];
- bits=flush_bits
- +oc_token_bits(_enc,huffi,zzi,OC_DCT_SHORT_ZRL_TOKEN);
- cost=d2+lambda*bits+tokens[zzj][tj].cost;
- if(cost<best_cost){
- best_next=(zzj<<2)+tj;
- best_token=OC_DCT_SHORT_ZRL_TOKEN;
- best_eb=zzj-zzi-1;
- best_cost=cost;
- best_bits=bits+tokens[zzj][tj].bits;
- best_qc=0;
- }
- /*Try a +/- 1 combo token.*/
- if(ntokens[zzj]>1){
- next=tokens[zzj][1].next;
- tk=next&3;
- zzk=next>>2;
- token=OC_DCT_RUN_CAT1A+zzj-zzi-1;
- bits=flush_bits+oc_token_bits(_enc,huffi,zzi,token)
- -(tokens[zzj][1].bits-tokens[zzk][tk].bits);
- cost=d2+lambda*bits+tokens[zzj][1].cost;
- if(cost<best_cost){
- best_next=next;
- best_token=token;
- best_eb=tokens[zzj][1].token-OC_ONE_TOKEN;
- best_cost=cost;
- best_bits=bits+tokens[zzj][1].bits;
- best_qc=tokens[zzj][1].qc;
- }
- }
- }
- if(zzj<zzi_max){
- zzj_max=zzi+17+(zzi+62>>6);
- for(;zzj<zzj_max&&zzj<zzi_max;zzj++){
- int cat;
- d2=d2_accum[zzi]-d2_accum[zzj];
- /*Try a raw zero run.*/
- cat=zzj-zzi>8;
- tj=best_ti[zzj];
- /*Don't use a long zero run to another zero coefficient.
- That's dumb.*/
- if(!cat||tj>0){
- token=OC_DCT_SHORT_ZRL_TOKEN+cat;
- bits=flush_bits+oc_token_bits(_enc,huffi,zzi,token);
- cost=d2+lambda*bits+tokens[zzj][tj].cost;
- if(cost<best_cost){
- best_next=(zzj<<2)+tj;
- best_token=token;
- best_eb=zzj-zzi-1;
- best_cost=cost;
- best_bits=bits+tokens[zzj][tj].bits;
- best_qc=0;
- }
- }
- /*Try a +/- 1 combo token.*/
- if(ntokens[zzj]>1){
- next=tokens[zzj][1].next;
- tk=next&3;
- zzk=next>>2;
- cat=zzj-zzi>9;
- token=OC_DCT_RUN_CAT1B+cat;
- bits=flush_bits+oc_token_bits(_enc,huffi,zzi,token)
- -(tokens[zzj][1].bits-tokens[zzk][tk].bits);
- cost=d2+lambda*bits+tokens[zzj][1].cost;
- if(cost<best_cost){
- best_next=next;
- best_token=token;
- best_eb=(tokens[zzj][1].token-OC_ONE_TOKEN<<cat+2)
- +zzj-zzi-6-(cat<<2);
- best_cost=cost;
- best_bits=bits+tokens[zzj][1].bits;
- best_qc=tokens[zzj][1].qc;
- }
- }
- }
- if(zzj<zzi_max){
- for(;zzj<zzi_max;zzj++){
- /*Try a raw zero run.*/
- tj=best_ti[zzj];
- /*But not to another zero coefficient; that's dumb.*/
- if(tj>0){
- d2=d2_accum[zzi]-d2_accum[zzj];
- bits=flush_bits
- +oc_token_bits(_enc,huffi,zzi,OC_DCT_ZRL_TOKEN);
- cost=d2+lambda*bits+tokens[zzj][tj].cost;
- if(cost<best_cost){
- best_next=(zzj<<2)+tj;
- best_token=OC_DCT_ZRL_TOKEN;
- best_eb=zzj-zzi-1;
- best_cost=cost;
- best_bits=bits+tokens[zzj][tj].bits;
- best_qc=0;
- }
- }
- }
- }
- }
- }
- }
- tokens[zzi][0].next=(unsigned char)best_next;
- tokens[zzi][0].token=(signed char)best_token;
- tokens[zzi][0].eb=(ogg_int16_t)best_eb;
- tokens[zzi][0].cost=best_cost;
- tokens[zzi][0].bits=best_bits;
- tokens[zzi][0].qc=best_qc;
- }
- else{
- tokens[zzi][0].next=0;
- tokens[zzi][0].token=-1;
- tokens[zzi][0].eb=-1;
- tokens[zzi][0].cost=0x7FFFFFFF;
- tokens[zzi][0].bits=0;
- tokens[zzi][0].qc=0;
- /*zzi_max=zzi+1;*/
- }
- if(qc>0){
- int dq;
- int e;
- dq=_dequant[zzi];
- e=dq-c;
- d2=e*(ogg_int32_t)e;
- token=OC_ONE_TOKEN-s;
- bits=flush_bits+oc_token_bits(_enc,huffi,zzi,token);
- zzj=zzi+1&63;
- tj=best_ti[zzj];
- next=(zzj<<2)+tj;
- tokens[zzi][1].next=(unsigned char)next;
- tokens[zzi][1].token=(signed char)token;
- tokens[zzi][1].eb=0;
- tokens[zzi][1].bits=bits+tokens[zzj][tj].bits;
- tokens[zzi][1].cost=d2+lambda*bits+tokens[zzj][tj].cost;
- tokens[zzi][1].qc=1+s^s;
- if(qc>1){
- e+=dq;
- d2=e*(ogg_int32_t)e;
- best_token=OC_TWO_TOKEN-s;
- best_eb=0;
- best_bits=flush_bits+oc_token_bits(_enc,huffi,zzi,best_token);
- best_cost=d2+lambda*best_bits;
- best_qc=2+s^s;
- if(qc>2){
- e+=dq;
- d2=e*(ogg_int32_t)e;
- bits=flush_bits+oc_token_bits(_enc,huffi,zzi,OC_DCT_VAL_CAT2);
- cost=d2+lambda*bits;
- if(cost<best_cost){
- best_token=OC_DCT_VAL_CAT2;
- best_eb=-s;
- best_bits=bits;
- best_cost=cost;
- best_qc=3+s^s;
- }
- }
- tokens[zzi][2].next=(unsigned char)next;
- tokens[zzi][2].token=(signed char)best_token;
- tokens[zzi][2].eb=(ogg_int16_t)best_eb;
- tokens[zzi][2].bits=best_bits+tokens[zzj][tj].bits;
- tokens[zzi][2].cost=best_cost+tokens[zzj][tj].cost;
- tokens[zzi][2].qc=best_qc;
- best_cost=0xFFFFFFFFU;
- if(qc>3){
- if(qc>4){
- if(qc>5){
- if(qc>6){
- if(qc>8){
- if(qc>12){
- if(qc>20){
- if(qc>36){
- if(qc>68){
- e=qc*dq-c;
- d2=e*(ogg_int32_t)e;
- best_token=OC_DCT_VAL_CAT8;
- best_eb=(-s<<9)+qc-69;
- best_bits=flush_bits
- +oc_token_bits(_enc,huffi,zzi,OC_DCT_VAL_CAT8);
- best_cost=d2+lambda*best_bits;
- best_qc=qc+s^s;
- qc=68;
- }
- e=qc*dq-c;
- d2=e*(ogg_int32_t)e;
- bits=flush_bits
- +oc_token_bits(_enc,huffi,zzi,OC_DCT_VAL_CAT7);
- cost=d2+lambda*bits;
- if(cost<=best_cost){
- best_token=OC_DCT_VAL_CAT7;
- best_eb=(-s<<5)+qc-37;
- best_bits=bits;
- best_cost=cost;
- best_qc=qc+s^s;
- }
- qc=36;
- }
- e=qc*dq-c;
- d2=e*(ogg_int32_t)e;
- bits=flush_bits
- +oc_token_bits(_enc,huffi,zzi,OC_DCT_VAL_CAT6);
- cost=d2+lambda*bits;
- if(cost<=best_cost){
- best_token=OC_DCT_VAL_CAT6;
- best_eb=(-s<<4)+qc-21;
- best_bits=bits;
- best_cost=cost;
- best_qc=qc+s^s;
- }
- qc=20;
- }
- e=qc*dq-c;
- d2=e*(ogg_int32_t)e;
- bits=flush_bits
- +oc_token_bits(_enc,huffi,zzi,OC_DCT_VAL_CAT5);
- cost=d2+lambda*bits;
- if(cost<=best_cost){
- best_token=OC_DCT_VAL_CAT5;
- best_eb=(-s<<3)+qc-13;
- best_bits=bits;
- best_cost=cost;
- best_qc=qc+s^s;
- }
- qc=12;
- }
- e=qc*dq-c;
- d2=e*(ogg_int32_t)e;
- bits=flush_bits
- +oc_token_bits(_enc,huffi,zzi,OC_DCT_VAL_CAT4);
- cost=d2+lambda*bits;
- if(cost<=best_cost){
- best_token=OC_DCT_VAL_CAT4;
- best_eb=(-s<<2)+qc-9;
- best_bits=bits;
- best_cost=cost;
- best_qc=qc+s^s;
- }
- qc=8;
- }
- e=qc*dq-c;
- d2=e*(ogg_int32_t)e;
- bits=flush_bits+oc_token_bits(_enc,huffi,zzi,OC_DCT_VAL_CAT3);
- cost=d2+lambda*bits;
- if(cost<=best_cost){
- best_token=OC_DCT_VAL_CAT3;
- best_eb=(-s<<1)+qc-7;
- best_bits=bits;
- best_cost=cost;
- best_qc=qc+s^s;
- }
- }
- e=6*dq-c;
- d2=e*(ogg_int32_t)e;
- bits=flush_bits+oc_token_bits(_enc,huffi,zzi,OC_DCT_VAL_CAT2+3);
- cost=d2+lambda*bits;
- if(cost<=best_cost){
- best_token=OC_DCT_VAL_CAT2+3;
- best_eb=-s;
- best_bits=bits;
- best_cost=cost;
- best_qc=6+s^s;
- }
- }
- e=5*dq-c;
- d2=e*(ogg_int32_t)e;
- bits=flush_bits+oc_token_bits(_enc,huffi,zzi,OC_DCT_VAL_CAT2+2);
- cost=d2+lambda*bits;
- if(cost<=best_cost){
- best_token=OC_DCT_VAL_CAT2+2;
- best_eb=-s;
- best_bits=bits;
- best_cost=cost;
- best_qc=5+s^s;
- }
- }
- e=4*dq-c;
- d2=e*(ogg_int32_t)e;
- bits=flush_bits+oc_token_bits(_enc,huffi,zzi,OC_DCT_VAL_CAT2+1);
- cost=d2+lambda*bits;
- if(cost<=best_cost){
- best_token=OC_DCT_VAL_CAT2+1;
- best_eb=-s;
- best_bits=bits;
- best_cost=cost;
- best_qc=4+s^s;
- }
- tokens[zzi][3].next=(unsigned char)next;
- tokens[zzi][3].token=(signed char)best_token;
- tokens[zzi][3].eb=(ogg_int16_t)best_eb;
- tokens[zzi][3].bits=best_bits+flush_bits+tokens[zzj][tj].bits;
- tokens[zzi][3].cost=best_cost+tokens[zzj][tj].cost;
- tokens[zzi][3].qc=best_qc;
- ntokens[zzi]=4;
- /*zzi_max=zzi+1;*/
- }
- else ntokens[zzi]=3;
- }
- else ntokens[zzi]=2;
- }
- else ntokens[zzi]=1;
- tj=ntokens[zzi]-1;
- for(ti=tj;ti-->0;)if(tokens[zzi][ti].cost<tokens[zzi][tj].cost)tj=ti;
- best_ti[zzi]=tj;
- }
- /*Emit the tokens from the best path through the trellis.*/
- stack=*_stack;
- zzi=1;
- ti=best_ti[1];
- bits=tokens[zzi][ti].bits;
- {
- int real_bits;
- int real_ssd;
- real_bits=0;
- real_ssd=0;
- do{
- oc_enc_tokenlog_checkpoint(_enc,stack++,_pli,zzi);
- eob=eob_run[zzi];
- if(tokens[zzi][ti].token<OC_NDCT_EOB_TOKEN_MAX){
- if(++eob>=4095){
- token=oc_make_eob_token_full(eob,&eb);
- real_bits+=oc_token_bits(_enc,huffi,zzi,token);
- oc_enc_token_log(_enc,_pli,zzi,token,eb);
- eob=0;
- }
- else if(eob>1){
- real_bits-=oc_token_bits(_enc,huffi,zzi,oc_make_eob_token(eob-1));
- }
- real_bits+=oc_token_bits(_enc,huffi,zzi,oc_make_eob_token(eob));
- eob_run[zzi]=eob;
- /*We don't include the actual EOB cost for this block in the return value.
- It will be paid for by the fragment that terminates the EOB run.*/
- bits-=tokens[zzi][ti].bits;
- for(;zzi<_zzi;zzi++){
- _qdct[zzi]=0;
- real_ssd+=_dct[OC_FZIG_ZAG[zzi]]*_dct[OC_FZIG_ZAG[zzi]];
- }
- if(_zzi<64)real_ssd+=_dct[OC_FZIG_ZAG[zzi]]*_dct[OC_FZIG_ZAG[zzi]];
- break;
- }
- /*Emit pending EOB run if any.*/
- if(eob>0){
- real_bits+=oc_token_bits(_enc,huffi,zzi,oc_make_eob_token(eob));
- oc_enc_eob_log(_enc,_pli,zzi,eob);
- eob_run[zzi]=0;
- }
- real_bits+=oc_token_bits(_enc,huffi,zzi,tokens[zzi][ti].token);
- oc_enc_token_log(_enc,_pli,zzi,tokens[zzi][ti].token,tokens[zzi][ti].eb);
- next=tokens[zzi][ti].next;
- qc=tokens[zzi][ti].qc;
- zzj=(next>>2)-1&63;
- for(;zzi<zzj;zzi++){
- _qdct[zzi]=0;
- real_ssd+=_dct[OC_FZIG_ZAG[zzi]]*_dct[OC_FZIG_ZAG[zzi]];
- }
- _qdct[zzj]=qc;
- real_ssd+=(qc*_dequant[zzj]-_dct[OC_FZIG_ZAG[zzi]])*
- (qc*_dequant[zzj]-_dct[OC_FZIG_ZAG[zzi]]);
- zzi=next>>2;
- ti=next&3;
- }
- while(zzi);
- *_stack=stack;
- }
- return bits;
-}
-#endif
-
void oc_enc_pred_dc_frag_rows(oc_enc_ctx *_enc,
int _pli,int _fragy0,int _frag_yend){
const oc_fragment_plane *fplane;
More information about the commits
mailing list