Make the SATD functions return the signed DC value instead of abs(dc).
[theora.git] / lib / analyze.c
1 /********************************************************************
2  *                                                                  *
3  * THIS FILE IS PART OF THE OggTheora SOFTWARE CODEC SOURCE CODE.   *
4  * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *
5  * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
6  * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *
7  *                                                                  *
8  * THE Theora SOURCE CODE IS COPYRIGHT (C) 2002-2009                *
9  * by the Xiph.Org Foundation http://www.xiph.org/                  *
10  *                                                                  *
11  ********************************************************************
12
13   function: mode selection code
14   last mod: $Id$
15
16  ********************************************************************/
17 #include <limits.h>
18 #include <string.h>
19 #include "encint.h"
20 #include "modedec.h"
21 #if defined(OC_COLLECT_METRICS)
22 # include "collect.c"
23 #endif
24
25
26
27 typedef struct oc_rd_metric          oc_rd_metric;
28 typedef struct oc_mode_choice        oc_mode_choice;
29
30
31
32 /*There are 8 possible schemes used to encode macro block modes.
33   Schemes 0-6 use a maximally-skewed Huffman code to code each of the modes.
34   The same set of Huffman codes is used for each of these 7 schemes, but the
35    mode assigned to each codeword varies.
36   Scheme 0 writes a custom mapping from codeword to MB mode to the bitstream,
37    while schemes 1-6 have a fixed mapping.
38   Scheme 7 just encodes each mode directly in 3 bits.*/
39
40 /*The mode orderings for the various mode coding schemes.
41   Scheme 0 uses a custom alphabet, which is not stored in this table.
42   This is the inverse of the equivalent table OC_MODE_ALPHABETS in the
43    decoder.*/
44 static const unsigned char OC_MODE_RANKS[7][OC_NMODES]={
45   /*Last MV dominates.*/
46   /*L P M N I G GM 4*/
47   {3,4,2,0,1,5,6,7},
48   /*L P N M I G GM 4*/
49   {2,4,3,0,1,5,6,7},
50   /*L M P N I G GM 4*/
51   {3,4,1,0,2,5,6,7},
52   /*L M N P I G GM 4*/
53   {2,4,1,0,3,5,6,7},
54   /*No MV dominates.*/
55   /*N L P M I G GM 4*/
56   {0,4,3,1,2,5,6,7},
57   /*N G L P M I GM 4*/
58   {0,5,4,2,3,1,6,7},
59   /*Default ordering.*/
60   /*N I M L P G GM 4*/
61   {0,1,2,3,4,5,6,7}
62 };
63
64
65
66 /*Initialize the mode scheme chooser.
67   This need only be called once per encoder.*/
68 void oc_mode_scheme_chooser_init(oc_mode_scheme_chooser *_chooser){
69   int si;
70   _chooser->mode_ranks[0]=_chooser->scheme0_ranks;
71   for(si=1;si<8;si++)_chooser->mode_ranks[si]=OC_MODE_RANKS[si-1];
72 }
73
74 /*Reset the mode scheme chooser.
75   This needs to be called once for each frame, including the first.*/
76 static void oc_mode_scheme_chooser_reset(oc_mode_scheme_chooser *_chooser){
77   int si;
78   memset(_chooser->mode_counts,0,OC_NMODES*sizeof(*_chooser->mode_counts));
79   /*Scheme 0 starts with 24 bits to store the mode list in.*/
80   _chooser->scheme_bits[0]=24;
81   memset(_chooser->scheme_bits+1,0,7*sizeof(*_chooser->scheme_bits));
82   for(si=0;si<8;si++){
83     /*Scheme 7 should always start first, and scheme 0 should always start
84        last.*/
85     _chooser->scheme_list[si]=7-si;
86     _chooser->scheme0_list[si]=_chooser->scheme0_ranks[si]=si;
87   }
88 }
89
90 /*Return the cost of coding _mb_mode in the specified scheme.*/
91 static int oc_mode_scheme_chooser_scheme_mb_cost(
92  const oc_mode_scheme_chooser *_chooser,int _scheme,int _mb_mode){
93   int codebook;
94   int ri;
95   codebook=_scheme+1>>3;
96   /*For any scheme except 0, we can just use the bit cost of the mode's rank
97      in that scheme.*/
98   ri=_chooser->mode_ranks[_scheme][_mb_mode];
99   if(_scheme==0){
100     int mc;
101     /*For scheme 0, incrementing the mode count could potentially change the
102        mode's rank.
103       Find the index where the mode would be moved to in the optimal list,
104        and use its bit cost instead of the one for the mode's current
105        position in the list.*/
106     /*We don't actually reorder the list; this is for computing opportunity
107        cost, not an update.*/
108     mc=_chooser->mode_counts[_mb_mode];
109     while(ri>0&&mc>=_chooser->mode_counts[_chooser->scheme0_list[ri-1]])ri--;
110   }
111   return OC_MODE_BITS[codebook][ri];
112 }
113
114 /*This is the real purpose of this data structure: not actually selecting a
115    mode scheme, but estimating the cost of coding a given mode given all the
116    modes selected so far.
117   This is done via opportunity cost: the cost is defined as the number of bits
118    required to encode all the modes selected so far including the current one
119    using the best possible scheme, minus the number of bits required to encode
120    all the modes selected so far not including the current one using the best
121    possible scheme.
122   The computational expense of doing this probably makes it overkill.
123   Just be happy we take a greedy approach instead of trying to solve the
124    global mode-selection problem (which is NP-hard).
125   _mb_mode: The mode to determine the cost of.
126   Return: The number of bits required to code this mode.*/
127 static int oc_mode_scheme_chooser_cost(oc_mode_scheme_chooser *_chooser,
128  int _mb_mode){
129   int scheme0;
130   int scheme1;
131   int best_bits;
132   int mode_bits;
133   int si;
134   int scheme0_bits;
135   int scheme1_bits;
136   scheme0=_chooser->scheme_list[0];
137   scheme1=_chooser->scheme_list[1];
138   scheme0_bits=_chooser->scheme_bits[scheme0];
139   scheme1_bits=_chooser->scheme_bits[scheme1];
140   mode_bits=oc_mode_scheme_chooser_scheme_mb_cost(_chooser,scheme0,_mb_mode);
141   /*Typical case: If the difference between the best scheme and the next best
142      is greater than 6 bits, then adding just one mode cannot change which
143      scheme we use.*/
144   if(scheme1_bits-scheme0_bits>6)return mode_bits;
145   /*Otherwise, check to see if adding this mode selects a different scheme as
146      the best.*/
147   si=1;
148   best_bits=scheme0_bits+mode_bits;
149   do{
150     int cur_bits;
151     cur_bits=scheme1_bits+
152      oc_mode_scheme_chooser_scheme_mb_cost(_chooser,scheme1,_mb_mode);
153     if(cur_bits<best_bits)best_bits=cur_bits;
154     if(++si>=8)break;
155     scheme1=_chooser->scheme_list[si];
156     scheme1_bits=_chooser->scheme_bits[scheme1];
157   }
158   while(scheme1_bits-scheme0_bits<=6);
159   return best_bits-scheme0_bits;
160 }
161
162 /*Incrementally update the mode counts and per-scheme bit counts and re-order
163    the scheme lists once a mode has been selected.
164   _mb_mode: The mode that was chosen.*/
165 static void oc_mode_scheme_chooser_update(oc_mode_scheme_chooser *_chooser,
166  int _mb_mode){
167   int ri;
168   int si;
169   _chooser->mode_counts[_mb_mode]++;
170   /*Re-order the scheme0 mode list if necessary.*/
171   for(ri=_chooser->scheme0_ranks[_mb_mode];ri>0;ri--){
172     int pmode;
173     pmode=_chooser->scheme0_list[ri-1];
174     if(_chooser->mode_counts[pmode]>=_chooser->mode_counts[_mb_mode])break;
175     /*Reorder the mode ranking.*/
176     _chooser->scheme0_ranks[pmode]++;
177     _chooser->scheme0_list[ri]=pmode;
178   }
179   _chooser->scheme0_ranks[_mb_mode]=ri;
180   _chooser->scheme0_list[ri]=_mb_mode;
181   /*Now add the bit cost for the mode to each scheme.*/
182   for(si=0;si<8;si++){
183     _chooser->scheme_bits[si]+=
184      OC_MODE_BITS[si+1>>3][_chooser->mode_ranks[si][_mb_mode]];
185   }
186   /*Finally, re-order the list of schemes.*/
187   for(si=1;si<8;si++){
188     int sj;
189     int scheme0;
190     int bits0;
191     sj=si;
192     scheme0=_chooser->scheme_list[si];
193     bits0=_chooser->scheme_bits[scheme0];
194     do{
195       int scheme1;
196       scheme1=_chooser->scheme_list[sj-1];
197       if(bits0>=_chooser->scheme_bits[scheme1])break;
198       _chooser->scheme_list[sj]=scheme1;
199     }
200     while(--sj>0);
201     _chooser->scheme_list[sj]=scheme0;
202   }
203 }
204
205
206
207 /*The number of bits required to encode a super block run.
208   _run_count: The desired run count; must be positive and less than 4130.*/
209 static int oc_sb_run_bits(int _run_count){
210   int i;
211   for(i=0;_run_count>=OC_SB_RUN_VAL_MIN[i+1];i++);
212   return OC_SB_RUN_CODE_NBITS[i];
213 }
214
215 /*The number of bits required to encode a block run.
216   _run_count: The desired run count; must be positive and less than 30.*/
217 static int oc_block_run_bits(int _run_count){
218   return OC_BLOCK_RUN_CODE_NBITS[_run_count-1];
219 }
220
221
222
223 static void oc_fr_state_init(oc_fr_state *_fr){
224   _fr->bits=0;
225   _fr->sb_partial_count=0;
226   _fr->sb_full_count=0;
227   _fr->b_coded_count_prev=0;
228   _fr->b_coded_count=0;
229   _fr->b_count=0;
230   _fr->sb_prefer_partial=0;
231   _fr->sb_bits=0;
232   _fr->sb_partial=-1;
233   _fr->sb_full=-1;
234   _fr->b_coded_prev=-1;
235   _fr->b_coded=-1;
236 }
237
238
239 static int oc_fr_state_sb_cost(const oc_fr_state *_fr,
240  int _sb_partial,int _sb_full){
241   int bits;
242   int sb_partial_count;
243   int sb_full_count;
244   bits=0;
245   sb_partial_count=_fr->sb_partial_count;
246   /*Extend the sb_partial run, or start a new one.*/
247   if(_fr->sb_partial==_sb_partial){
248     if(sb_partial_count>=4129){
249       bits++;
250       sb_partial_count=0;
251     }
252     else bits-=oc_sb_run_bits(sb_partial_count);
253   }
254   else sb_partial_count=0;
255   bits+=oc_sb_run_bits(++sb_partial_count);
256   if(!_sb_partial){
257     /*Extend the sb_full run, or start a new one.*/
258     sb_full_count=_fr->sb_full_count;
259     if(_fr->sb_full==_sb_full){
260       if(sb_full_count>=4129){
261         bits++;
262         sb_full_count=0;
263       }
264       else bits-=oc_sb_run_bits(sb_full_count);
265     }
266     else sb_full_count=0;
267     bits+=oc_sb_run_bits(++sb_full_count);
268   }
269   return bits;
270 }
271
272 static void oc_fr_state_advance_sb(oc_fr_state *_fr,
273  int _sb_partial,int _sb_full){
274   int sb_partial_count;
275   int sb_full_count;
276   sb_partial_count=_fr->sb_partial_count;
277   if(_fr->sb_partial!=_sb_partial||sb_partial_count>=4129)sb_partial_count=0;
278   sb_partial_count++;
279   if(!_sb_partial){
280     sb_full_count=_fr->sb_full_count;
281     if(_fr->sb_full!=_sb_full||sb_full_count>=4129)sb_full_count=0;
282     sb_full_count++;
283     _fr->sb_full_count=sb_full_count;
284     _fr->sb_full=_sb_full;
285     /*Roll back the partial block state.*/
286     _fr->b_coded=_fr->b_coded_prev;
287     _fr->b_coded_count=_fr->b_coded_count_prev;
288   }
289   else{
290     /*Commit back the partial block state.*/
291     _fr->b_coded_prev=_fr->b_coded;
292     _fr->b_coded_count_prev=_fr->b_coded_count;
293   }
294   _fr->sb_partial_count=sb_partial_count;
295   _fr->sb_partial=_sb_partial;
296   _fr->b_count=0;
297   _fr->sb_prefer_partial=0;
298   _fr->sb_bits=0;
299 }
300
301 /*Commit the state of the current super block and advance to the next.*/
302 static void oc_fr_state_flush_sb(oc_fr_state *_fr){
303   int sb_partial;
304   int sb_full;
305   int b_coded_count;
306   int b_count;
307   b_count=_fr->b_count;
308   b_coded_count=_fr->b_coded_count;
309   sb_full=_fr->b_coded;
310   sb_partial=b_coded_count<b_count;
311   if(!sb_partial){
312     /*If the super block is fully coded/uncoded...*/
313     if(_fr->sb_prefer_partial){
314       /*So far coding this super block as partial was cheaper anyway.*/
315       if(b_coded_count>15||_fr->b_coded_prev<0){
316         int sb_bits;
317         /*If the block run is too long, this will limit how far it can be
318            extended into the next partial super block.
319           If we need to extend it farther, we don't want to have to roll all
320            the way back here (since there could be many full SBs between now
321            and then), so we disallow this.
322           Similarly, if this is the start of a stripe, we don't know how the
323            length of the outstanding block run from the previous stripe.*/
324         sb_bits=oc_fr_state_sb_cost(_fr,sb_partial,sb_full);
325         _fr->bits+=sb_bits-_fr->sb_bits;
326         _fr->sb_bits=sb_bits;
327       }
328       else sb_partial=1;
329     }
330   }
331   oc_fr_state_advance_sb(_fr,sb_partial,sb_full);
332 }
333
334 static void oc_fr_state_advance_block(oc_fr_state *_fr,int _b_coded){
335   ptrdiff_t bits;
336   int       sb_bits;
337   int       b_coded_count;
338   int       b_count;
339   int       sb_prefer_partial;
340   sb_bits=_fr->sb_bits;
341   bits=_fr->bits-sb_bits;
342   b_count=_fr->b_count;
343   b_coded_count=_fr->b_coded_count;
344   sb_prefer_partial=_fr->sb_prefer_partial;
345   if(b_coded_count>=b_count){
346     int sb_partial_bits;
347     /*This super block is currently fully coded/uncoded.*/
348     if(b_count<=0){
349       /*This is the first block in this SB.*/
350       b_count=1;
351       /*Check to see whether it's cheaper to code it partially or fully.*/
352       if(_fr->b_coded==_b_coded){
353         sb_partial_bits=-oc_block_run_bits(b_coded_count);
354         sb_partial_bits+=oc_block_run_bits(++b_coded_count);
355       }
356       else{
357         b_coded_count=1;
358         sb_partial_bits=2;
359       }
360       sb_partial_bits+=oc_fr_state_sb_cost(_fr,1,_b_coded);
361       sb_bits=oc_fr_state_sb_cost(_fr,0,_b_coded);
362       sb_prefer_partial=sb_partial_bits<sb_bits;
363       sb_bits^=(sb_partial_bits^sb_bits)&-sb_prefer_partial;
364     }
365     else if(_fr->b_coded==_b_coded){
366       b_coded_count++;
367       if(++b_count<16){
368         if(sb_prefer_partial){
369           /*Check to see if it's cheaper to code it fully.*/
370           sb_partial_bits=sb_bits;
371           sb_partial_bits+=oc_block_run_bits(b_coded_count);
372           if(b_coded_count>0){
373             sb_partial_bits-=oc_block_run_bits(b_coded_count-1);
374           }
375           sb_bits=oc_fr_state_sb_cost(_fr,0,_b_coded);
376           sb_prefer_partial=sb_partial_bits<sb_bits;
377           sb_bits^=(sb_partial_bits^sb_bits)&-sb_prefer_partial;
378         }
379         /*There's no need to check the converse (whether it's cheaper to code
380            this SB partially if we were coding it fully), since the cost to
381            code a SB partially can only increase as we add more blocks, whereas
382            the cost to code it fully stays constant.*/
383       }
384       else{
385         /*If we get to the end and this SB is still full, then force it to be
386            coded full.
387           Otherwise we might not be able to extend the block run far enough
388            into the next partial SB.*/
389         if(sb_prefer_partial){
390           sb_prefer_partial=0;
391           sb_bits=oc_fr_state_sb_cost(_fr,0,_b_coded);
392         }
393       }
394     }
395     else{
396       /*This SB was full, but now must be made partial.*/
397       if(!sb_prefer_partial){
398         sb_bits=oc_block_run_bits(b_coded_count);
399         if(b_coded_count>b_count){
400           sb_bits-=oc_block_run_bits(b_coded_count-b_count);
401         }
402         sb_bits+=oc_fr_state_sb_cost(_fr,1,_b_coded);
403       }
404       b_count++;
405       b_coded_count=1;
406       sb_prefer_partial=1;
407       sb_bits+=2;
408     }
409   }
410   else{
411     b_count++;
412     if(_fr->b_coded==_b_coded)sb_bits-=oc_block_run_bits(b_coded_count);
413     else b_coded_count=0;
414     sb_bits+=oc_block_run_bits(++b_coded_count);
415   }
416   _fr->bits=bits+sb_bits;
417   _fr->b_coded_count=b_coded_count;
418   _fr->b_coded=_b_coded;
419   _fr->b_count=b_count;
420   _fr->sb_prefer_partial=sb_prefer_partial;
421   _fr->sb_bits=sb_bits;
422 }
423
424 static void oc_fr_skip_block(oc_fr_state *_fr){
425   oc_fr_state_advance_block(_fr,0);
426 }
427
428 static void oc_fr_code_block(oc_fr_state *_fr){
429   oc_fr_state_advance_block(_fr,1);
430 }
431
432 static int oc_fr_cost1(const oc_fr_state *_fr){
433   oc_fr_state tmp;
434   ptrdiff_t   bits;
435   *&tmp=*_fr;
436   oc_fr_skip_block(&tmp);
437   bits=tmp.bits;
438   *&tmp=*_fr;
439   oc_fr_code_block(&tmp);
440   return (int)(tmp.bits-bits);
441 }
442
443 static int oc_fr_cost4(const oc_fr_state *_pre,const oc_fr_state *_post){
444   oc_fr_state tmp;
445   *&tmp=*_pre;
446   oc_fr_skip_block(&tmp);
447   oc_fr_skip_block(&tmp);
448   oc_fr_skip_block(&tmp);
449   oc_fr_skip_block(&tmp);
450   return (int)(_post->bits-tmp.bits);
451 }
452
453
454
455 static void oc_qii_state_init(oc_qii_state *_qs){
456   _qs->bits=0;
457   _qs->qi01_count=0;
458   _qs->qi01=-1;
459   _qs->qi12_count=0;
460   _qs->qi12=-1;
461 }
462
463
464 static void oc_qii_state_advance(oc_qii_state *_qd,
465  const oc_qii_state *_qs,int _qii){
466   ptrdiff_t bits;
467   int       qi01;
468   int       qi01_count;
469   int       qi12;
470   int       qi12_count;
471   bits=_qs->bits;
472   qi01=_qii+1>>1;
473   qi01_count=_qs->qi01_count;
474   if(qi01==_qs->qi01){
475     if(qi01_count>=4129){
476       bits++;
477       qi01_count=0;
478     }
479     else bits-=oc_sb_run_bits(qi01_count);
480   }
481   else qi01_count=0;
482   qi01_count++;
483   bits+=oc_sb_run_bits(qi01_count);
484   qi12_count=_qs->qi12_count;
485   if(_qii){
486     qi12=_qii>>1;
487     if(qi12==_qs->qi12){
488       if(qi12_count>=4129){
489         bits++;
490         qi12_count=0;
491       }
492       else bits-=oc_sb_run_bits(qi12_count);
493     }
494     else qi12_count=0;
495     qi12_count++;
496     bits+=oc_sb_run_bits(qi12_count);
497   }
498   else qi12=_qs->qi12;
499   _qd->bits=bits;
500   _qd->qi01=qi01;
501   _qd->qi01_count=qi01_count;
502   _qd->qi12=qi12;
503   _qd->qi12_count=qi12_count;
504 }
505
506
507
508 static void oc_enc_pipeline_init(oc_enc_ctx *_enc,oc_enc_pipeline_state *_pipe){
509   ptrdiff_t *coded_fragis;
510   unsigned   mcu_nvsbs;
511   ptrdiff_t  mcu_nfrags;
512   int        flimit;
513   int        hdec;
514   int        vdec;
515   int        pli;
516   int        nqis;
517   int        qii;
518   int        qi0;
519   int        qti;
520   /*Initialize the per-plane coded block flag trackers.
521     These are used for bit-estimation purposes only; the real flag bits span
522      all three planes, so we can't compute them in parallel.*/
523   for(pli=0;pli<3;pli++)oc_fr_state_init(_pipe->fr+pli);
524   for(pli=0;pli<3;pli++)oc_qii_state_init(_pipe->qs+pli);
525   /*Set up the per-plane skip SSD storage pointers.*/
526   mcu_nvsbs=_enc->mcu_nvsbs;
527   mcu_nfrags=mcu_nvsbs*_enc->state.fplanes[0].nhsbs*16;
528   hdec=!(_enc->state.info.pixel_fmt&1);
529   vdec=!(_enc->state.info.pixel_fmt&2);
530   _pipe->skip_ssd[0]=_enc->mcu_skip_ssd;
531   _pipe->skip_ssd[1]=_pipe->skip_ssd[0]+mcu_nfrags;
532   _pipe->skip_ssd[2]=_pipe->skip_ssd[1]+(mcu_nfrags>>hdec+vdec);
533   /*Set up per-plane pointers to the coded and uncoded fragments lists.
534     Unlike the decoder, each planes' coded and uncoded fragment list is kept
535      separate during the analysis stage; we only make the coded list for all
536      three planes contiguous right before the final packet is output
537      (destroying the uncoded lists, which are no longer needed).*/
538   coded_fragis=_enc->state.coded_fragis;
539   for(pli=0;pli<3;pli++){
540     _pipe->coded_fragis[pli]=coded_fragis;
541     coded_fragis+=_enc->state.fplanes[pli].nfrags;
542     _pipe->uncoded_fragis[pli]=coded_fragis;
543   }
544   memset(_pipe->ncoded_fragis,0,sizeof(_pipe->ncoded_fragis));
545   memset(_pipe->nuncoded_fragis,0,sizeof(_pipe->nuncoded_fragis));
546   /*Set up condensed quantizer tables.*/
547   qi0=_enc->state.qis[0];
548   nqis=_enc->state.nqis;
549   for(pli=0;pli<3;pli++){
550     for(qii=0;qii<nqis;qii++){
551       int qi;
552       qi=_enc->state.qis[qii];
553       for(qti=0;qti<2;qti++){
554         /*Set the DC coefficient in the dequantization table.*/
555         _enc->state.dequant_tables[qi][pli][qti][0]=
556          _enc->dequant_dc[qi0][pli][qti];
557         _enc->dequant[pli][qii][qti]=_enc->state.dequant_tables[qi][pli][qti];
558         /*Copy over the quantization table.*/
559         memcpy(_enc->enquant[pli][qii][qti],_enc->enquant_tables[qi][pli][qti],
560          _enc->opt_data.enquant_table_size);
561       }
562     }
563   }
564   /*Fix up the DC coefficients in the quantization tables.*/
565   oc_enc_enquant_table_fixup(_enc,_enc->enquant,nqis);
566   /*Initialize the tokenization state.*/
567   for(pli=0;pli<3;pli++){
568     _pipe->ndct_tokens1[pli]=0;
569     _pipe->eob_run1[pli]=0;
570   }
571   /*Initialize the bounding value array for the loop filter.*/
572   flimit=_enc->state.loop_filter_limits[_enc->state.qis[0]];
573   _pipe->loop_filter=flimit!=0;
574   if(flimit!=0)oc_loop_filter_init(&_enc->state,_pipe->bounding_values,flimit);
575   /*Clear the temporary DCT scratch space.*/
576   memset(_pipe->dct_data,0,sizeof(_pipe->dct_data));
577 }
578
579 /*Sets the current MCU stripe to super block row _sby.
580   Return: A non-zero value if this was the last MCU.*/
581 static int oc_enc_pipeline_set_stripe(oc_enc_ctx *_enc,
582  oc_enc_pipeline_state *_pipe,int _sby){
583   const oc_fragment_plane *fplane;
584   unsigned                 mcu_nvsbs;
585   int                      sby_end;
586   int                      notdone;
587   int                      vdec;
588   int                      pli;
589   mcu_nvsbs=_enc->mcu_nvsbs;
590   sby_end=_enc->state.fplanes[0].nvsbs;
591   notdone=_sby+mcu_nvsbs<sby_end;
592   if(notdone)sby_end=_sby+mcu_nvsbs;
593   vdec=0;
594   for(pli=0;pli<3;pli++){
595     fplane=_enc->state.fplanes+pli;
596     _pipe->sbi0[pli]=fplane->sboffset+(_sby>>vdec)*fplane->nhsbs;
597     _pipe->fragy0[pli]=_sby<<2-vdec;
598     _pipe->froffset[pli]=fplane->froffset
599      +_pipe->fragy0[pli]*(ptrdiff_t)fplane->nhfrags;
600     if(notdone){
601       _pipe->sbi_end[pli]=fplane->sboffset+(sby_end>>vdec)*fplane->nhsbs;
602       _pipe->fragy_end[pli]=sby_end<<2-vdec;
603     }
604     else{
605       _pipe->sbi_end[pli]=fplane->sboffset+fplane->nsbs;
606       _pipe->fragy_end[pli]=fplane->nvfrags;
607     }
608     vdec=!(_enc->state.info.pixel_fmt&2);
609   }
610   return notdone;
611 }
612
613 static void oc_enc_pipeline_finish_mcu_plane(oc_enc_ctx *_enc,
614  oc_enc_pipeline_state *_pipe,int _pli,int _sdelay,int _edelay){
615   /*Copy over all the uncoded fragments from this plane and advance the uncoded
616      fragment list.*/
617   if(_pipe->nuncoded_fragis[_pli]>0){
618     _pipe->uncoded_fragis[_pli]-=_pipe->nuncoded_fragis[_pli];
619     oc_frag_copy_list(&_enc->state,
620      _enc->state.ref_frame_data[OC_FRAME_SELF],
621      _enc->state.ref_frame_data[OC_FRAME_PREV],
622      _enc->state.ref_ystride[_pli],_pipe->uncoded_fragis[_pli],
623      _pipe->nuncoded_fragis[_pli],_enc->state.frag_buf_offs);
624     _pipe->nuncoded_fragis[_pli]=0;
625   }
626   /*Perform DC prediction.*/
627   oc_enc_pred_dc_frag_rows(_enc,_pli,
628    _pipe->fragy0[_pli],_pipe->fragy_end[_pli]);
629   /*Finish DC tokenization.*/
630   oc_enc_tokenize_dc_frag_list(_enc,_pli,
631    _pipe->coded_fragis[_pli],_pipe->ncoded_fragis[_pli],
632    _pipe->ndct_tokens1[_pli],_pipe->eob_run1[_pli]);
633   _pipe->ndct_tokens1[_pli]=_enc->ndct_tokens[_pli][1];
634   _pipe->eob_run1[_pli]=_enc->eob_run[_pli][1];
635   /*And advance the coded fragment list.*/
636   _enc->state.ncoded_fragis[_pli]+=_pipe->ncoded_fragis[_pli];
637   _pipe->coded_fragis[_pli]+=_pipe->ncoded_fragis[_pli];
638   _pipe->ncoded_fragis[_pli]=0;
639   /*Apply the loop filter if necessary.*/
640   if(_pipe->loop_filter){
641     oc_state_loop_filter_frag_rows(&_enc->state,
642      _pipe->bounding_values,OC_FRAME_SELF,_pli,
643      _pipe->fragy0[_pli]-_sdelay,_pipe->fragy_end[_pli]-_edelay);
644   }
645   else _sdelay=_edelay=0;
646   /*To fill borders, we have an additional two pixel delay, since a fragment
647      in the next row could filter its top edge, using two pixels from a
648      fragment in this row.
649     But there's no reason to delay a full fragment between the two.*/
650   oc_state_borders_fill_rows(&_enc->state,
651    _enc->state.ref_frame_idx[OC_FRAME_SELF],_pli,
652    (_pipe->fragy0[_pli]-_sdelay<<3)-(_sdelay<<1),
653    (_pipe->fragy_end[_pli]-_edelay<<3)-(_edelay<<1));
654 }
655
656
657
658 /*Cost information about the coded blocks in a MB.*/
659 struct oc_rd_metric{
660   int uncoded_ac_ssd;
661   int coded_ac_ssd;
662   int ac_bits;
663   int dc_flag;
664 };
665
666
667
668 static int oc_enc_block_transform_quantize(oc_enc_ctx *_enc,
669  oc_enc_pipeline_state *_pipe,int _pli,ptrdiff_t _fragi,
670  unsigned _rd_scale,unsigned _rd_iscale,oc_rd_metric *_mo,
671  oc_fr_state *_fr,oc_token_checkpoint **_stack){
672   ogg_int16_t            *data;
673   ogg_int16_t            *dct;
674   ogg_int16_t            *idct;
675   oc_qii_state            qs;
676   const ogg_uint16_t     *dequant;
677   ogg_uint16_t            dequant_dc;
678   ptrdiff_t               frag_offs;
679   int                     ystride;
680   const unsigned char    *src;
681   const unsigned char    *ref;
682   unsigned char          *dst;
683   int                     nonzero;
684   unsigned                uncoded_ssd;
685   unsigned                coded_ssd;
686   oc_token_checkpoint    *checkpoint;
687   oc_fragment            *frags;
688   int                     mb_mode;
689   int                     refi;
690   int                     mv_offs[2];
691   int                     nmv_offs;
692   int                     ac_bits;
693   int                     borderi;
694   int                     nqis;
695   int                     qti;
696   int                     qii;
697   int                     dc;
698   nqis=_enc->state.nqis;
699   frags=_enc->state.frags;
700   frag_offs=_enc->state.frag_buf_offs[_fragi];
701   ystride=_enc->state.ref_ystride[_pli];
702   src=_enc->state.ref_frame_data[OC_FRAME_IO]+frag_offs;
703   borderi=frags[_fragi].borderi;
704   qii=frags[_fragi].qii;
705   data=_enc->pipe.dct_data;
706   dct=data+64;
707   idct=data+128;
708   if(qii&~3){
709 #if !defined(OC_COLLECT_METRICS)
710     if(_enc->sp_level>=OC_SP_LEVEL_EARLY_SKIP){
711       /*Enable early skip detection.*/
712       frags[_fragi].coded=0;
713       frags[_fragi].refi=OC_FRAME_NONE;
714       oc_fr_skip_block(_fr);
715       return 0;
716     }
717 #endif
718     /*Try and code this block anyway.*/
719     qii&=3;
720   }
721   refi=frags[_fragi].refi;
722   mb_mode=frags[_fragi].mb_mode;
723   ref=_enc->state.ref_frame_data[refi]+frag_offs;
724   dst=_enc->state.ref_frame_data[OC_FRAME_SELF]+frag_offs;
725   /*Motion compensation:*/
726   switch(mb_mode){
727     case OC_MODE_INTRA:{
728       nmv_offs=0;
729       oc_enc_frag_sub_128(_enc,data,src,ystride);
730     }break;
731     case OC_MODE_GOLDEN_NOMV:
732     case OC_MODE_INTER_NOMV:{
733       nmv_offs=1;
734       mv_offs[0]=0;
735       oc_enc_frag_sub(_enc,data,src,ref,ystride);
736     }break;
737     default:{
738       const oc_mv *frag_mvs;
739       frag_mvs=_enc->state.frag_mvs;
740       nmv_offs=oc_state_get_mv_offsets(&_enc->state,mv_offs,
741        _pli,frag_mvs[_fragi]);
742       if(nmv_offs>1){
743         oc_enc_frag_copy2(_enc,dst,
744          ref+mv_offs[0],ref+mv_offs[1],ystride);
745         oc_enc_frag_sub(_enc,data,src,dst,ystride);
746       }
747       else oc_enc_frag_sub(_enc,data,src,ref+mv_offs[0],ystride);
748     }break;
749   }
750 #if defined(OC_COLLECT_METRICS)
751   {
752     unsigned satd;
753     switch(nmv_offs){
754       case 0:satd=oc_enc_frag_intra_satd(_enc,&dc,src,ystride);break;
755       case 1:{
756         satd=oc_enc_frag_satd(_enc,&dc,src,ref+mv_offs[0],ystride);
757         satd+=abs(dc);
758       }break;
759       default:{
760         satd=oc_enc_frag_satd(_enc,&dc,src,dst,ystride);
761         satd+=abs(dc);
762       }break;
763     }
764     _enc->frag_satd[_fragi]=satd;
765   }
766 #endif
767   /*Transform:*/
768   oc_enc_fdct8x8(_enc,dct,data);
769   /*Quantize:*/
770   qti=mb_mode!=OC_MODE_INTRA;
771   dequant=_enc->dequant[_pli][qii][qti];
772   nonzero=oc_enc_quantize(_enc,data,dct,dequant,_enc->enquant[_pli][qii][qti]);
773   dc=data[0];
774   /*Tokenize.*/
775   checkpoint=*_stack;
776   if(_enc->sp_level<OC_SP_LEVEL_FAST_ANALYSIS){
777     ac_bits=oc_enc_tokenize_ac(_enc,_pli,_fragi,idct,data,dequant,dct,
778      nonzero+1,_stack,OC_RD_ISCALE(_enc->lambda,_rd_iscale),qti?0:3);
779   }
780   else{
781     ac_bits=oc_enc_tokenize_ac_fast(_enc,_pli,_fragi,idct,data,dequant,dct,
782      nonzero+1,_stack,OC_RD_ISCALE(_enc->lambda,_rd_iscale),qti?0:3);
783   }
784   /*Reconstruct.
785     TODO: nonzero may need to be adjusted after tokenization.*/
786   dequant_dc=dequant[0];
787   if(nonzero==0){
788     ogg_int16_t p;
789     int         ci;
790     int         qi01;
791     int         qi12;
792     /*We round this dequant product (and not any of the others) because there's
793        no iDCT rounding.*/
794     p=(ogg_int16_t)(dc*(ogg_int32_t)dequant_dc+15>>5);
795     /*LOOP VECTORIZES.*/
796     for(ci=0;ci<64;ci++)data[ci]=p;
797     /*We didn't code any AC coefficients, so don't change the quantizer.*/
798     qi01=_pipe->qs[_pli].qi01;
799     qi12=_pipe->qs[_pli].qi12;
800     if(qi01>0)qii=1+qi12;
801     else if(qi01>=0)qii=0;
802   }
803   else{
804     idct[0]=dc*dequant_dc;
805     /*Note: This clears idct[] back to zero for the next block.*/
806     oc_idct8x8(&_enc->state,data,idct,nonzero+1);
807   }
808   frags[_fragi].qii=qii;
809   if(nqis>1){
810     oc_qii_state_advance(&qs,_pipe->qs+_pli,qii);
811     ac_bits+=qs.bits-_pipe->qs[_pli].bits;
812   }
813   if(!qti)oc_enc_frag_recon_intra(_enc,dst,ystride,data);
814   else{
815     oc_enc_frag_recon_inter(_enc,dst,
816      nmv_offs==1?ref+mv_offs[0]:dst,ystride,data);
817   }
818   /*If _fr is NULL, then this is an INTRA frame, and we can't skip blocks.*/
819 #if !defined(OC_COLLECT_METRICS)
820   if(_fr!=NULL)
821 #endif
822   {
823     /*In retrospect, should we have skipped this block?*/
824     if(borderi<0){
825       coded_ssd=oc_enc_frag_ssd(_enc,src,dst,ystride);
826     }
827     else{
828       coded_ssd=oc_enc_frag_border_ssd(_enc,src,dst,ystride,
829        _enc->state.borders[borderi].mask);
830     }
831     /*Scale to match DCT domain.*/
832     coded_ssd<<=4;
833 #if defined(OC_COLLECT_METRICS)
834     _enc->frag_ssd[_fragi]=coded_ssd;
835   }
836   if(_fr!=NULL){
837 #endif
838     coded_ssd=OC_RD_SCALE(coded_ssd,_rd_scale);
839     uncoded_ssd=_pipe->skip_ssd[_pli][_fragi-_pipe->froffset[_pli]];
840     if(uncoded_ssd<UINT_MAX&&
841      /*Don't allow luma blocks to be skipped in 4MV mode when VP3 compatibility
842         is enabled.*/
843      (!_enc->vp3_compatible||mb_mode!=OC_MODE_INTER_MV_FOUR||_pli)){
844       int overhead_bits;
845       overhead_bits=oc_fr_cost1(_fr);
846       /*Although the fragment coding overhead determination is accurate, it is
847          greedy, using very coarse-grained local information.
848         Allowing it to mildly discourage coding turns out to be beneficial, but
849          it's not clear that allowing it to encourage coding through negative
850          coding overhead deltas is useful.
851         For that reason, we disallow negative coding overheads.*/
852       if(overhead_bits<0)overhead_bits=0;
853       if(uncoded_ssd<=coded_ssd+(overhead_bits+ac_bits)*_enc->lambda){
854         /*Hm, not worth it; roll back.*/
855         oc_enc_tokenlog_rollback(_enc,checkpoint,(*_stack)-checkpoint);
856         *_stack=checkpoint;
857         frags[_fragi].coded=0;
858         frags[_fragi].refi=OC_FRAME_NONE;
859         oc_fr_skip_block(_fr);
860         return 0;
861       }
862     }
863     else _mo->dc_flag=1;
864     _mo->uncoded_ac_ssd+=uncoded_ssd;
865     _mo->coded_ac_ssd+=coded_ssd;
866     _mo->ac_bits+=ac_bits;
867     oc_fr_code_block(_fr);
868   }
869   /*GCC 4.4.4 generates a warning here because it can't tell that
870      the init code in the nqis check above will run anytime this
871      line runs.*/
872   if(nqis>1)*(_pipe->qs+_pli)=*&qs;
873   frags[_fragi].dc=dc;
874   frags[_fragi].coded=1;
875   return 1;
876 }
877
878 static int oc_enc_mb_transform_quantize_inter_luma(oc_enc_ctx *_enc,
879  oc_enc_pipeline_state *_pipe,unsigned _mbi,int _mode_overhead,
880  const unsigned _rd_scale[4],const unsigned _rd_iscale[4]){
881   /*Worst case token stack usage for 4 fragments.*/
882   oc_token_checkpoint  stack[64*4];
883   oc_token_checkpoint *stackptr;
884   const oc_sb_map     *sb_maps;
885   signed char         *mb_modes;
886   oc_fragment         *frags;
887   ptrdiff_t           *coded_fragis;
888   ptrdiff_t            ncoded_fragis;
889   ptrdiff_t           *uncoded_fragis;
890   ptrdiff_t            nuncoded_fragis;
891   oc_rd_metric         mo;
892   oc_fr_state          fr_checkpoint;
893   oc_qii_state         qs_checkpoint;
894   int                  mb_mode;
895   int                  refi;
896   int                  ncoded;
897   ptrdiff_t            fragi;
898   int                  bi;
899   *&fr_checkpoint=*(_pipe->fr+0);
900   *&qs_checkpoint=*(_pipe->qs+0);
901   sb_maps=(const oc_sb_map *)_enc->state.sb_maps;
902   mb_modes=_enc->state.mb_modes;
903   frags=_enc->state.frags;
904   coded_fragis=_pipe->coded_fragis[0];
905   ncoded_fragis=_pipe->ncoded_fragis[0];
906   uncoded_fragis=_pipe->uncoded_fragis[0];
907   nuncoded_fragis=_pipe->nuncoded_fragis[0];
908   mb_mode=mb_modes[_mbi];
909   refi=OC_FRAME_FOR_MODE(mb_mode);
910   ncoded=0;
911   stackptr=stack;
912   memset(&mo,0,sizeof(mo));
913   for(bi=0;bi<4;bi++){
914     fragi=sb_maps[_mbi>>2][_mbi&3][bi];
915     frags[fragi].refi=refi;
916     frags[fragi].mb_mode=mb_mode;
917     if(oc_enc_block_transform_quantize(_enc,_pipe,0,fragi,
918      _rd_scale[bi],_rd_iscale[bi],&mo,_pipe->fr+0,&stackptr)){
919       coded_fragis[ncoded_fragis++]=fragi;
920       ncoded++;
921     }
922     else *(uncoded_fragis-++nuncoded_fragis)=fragi;
923   }
924   if(ncoded>0&&!mo.dc_flag){
925     int cost;
926     /*Some individual blocks were worth coding.
927       See if that's still true when accounting for mode and MV overhead.*/
928     cost=mo.coded_ac_ssd+_enc->lambda*(mo.ac_bits
929      +oc_fr_cost4(&fr_checkpoint,_pipe->fr+0)+_mode_overhead);
930     if(mo.uncoded_ac_ssd<=cost){
931       /*Taking macroblock overhead into account, it is not worth coding this
932          MB.*/
933       oc_enc_tokenlog_rollback(_enc,stack,stackptr-stack);
934       *(_pipe->fr+0)=*&fr_checkpoint;
935       *(_pipe->qs+0)=*&qs_checkpoint;
936       for(bi=0;bi<4;bi++){
937         fragi=sb_maps[_mbi>>2][_mbi&3][bi];
938         if(frags[fragi].coded){
939           *(uncoded_fragis-++nuncoded_fragis)=fragi;
940           frags[fragi].coded=0;
941           frags[fragi].refi=OC_FRAME_NONE;
942         }
943         oc_fr_skip_block(_pipe->fr+0);
944       }
945       ncoded_fragis-=ncoded;
946       ncoded=0;
947     }
948   }
949   /*If no luma blocks coded, the mode is forced.*/
950   if(ncoded==0)mb_modes[_mbi]=OC_MODE_INTER_NOMV;
951   /*Assume that a 1MV with a single coded block is always cheaper than a 4MV
952      with a single coded block.
953     This may not be strictly true: a 4MV computes chroma MVs using (0,0) for
954      skipped blocks, while a 1MV does not.*/
955   else if(ncoded==1&&mb_mode==OC_MODE_INTER_MV_FOUR){
956     mb_modes[_mbi]=OC_MODE_INTER_MV;
957   }
958   _pipe->ncoded_fragis[0]=ncoded_fragis;
959   _pipe->nuncoded_fragis[0]=nuncoded_fragis;
960   return ncoded;
961 }
962
963 static void oc_enc_sb_transform_quantize_inter_chroma(oc_enc_ctx *_enc,
964  oc_enc_pipeline_state *_pipe,int _pli,int _sbi_start,int _sbi_end){
965   const ogg_uint16_t *mcu_rd_scale;
966   const ogg_uint16_t *mcu_rd_iscale;
967   const oc_sb_map    *sb_maps;
968   oc_sb_flags        *sb_flags;
969   oc_fr_state        *fr;
970   ptrdiff_t          *coded_fragis;
971   ptrdiff_t           ncoded_fragis;
972   ptrdiff_t          *uncoded_fragis;
973   ptrdiff_t           nuncoded_fragis;
974   ptrdiff_t           froffset;
975   int                 sbi;
976   fr=_pipe->fr+_pli;
977   mcu_rd_scale=(const ogg_uint16_t *)_enc->mcu_rd_scale;
978   mcu_rd_iscale=(const ogg_uint16_t *)_enc->mcu_rd_iscale;
979   sb_maps=(const oc_sb_map *)_enc->state.sb_maps;
980   sb_flags=_enc->state.sb_flags;
981   coded_fragis=_pipe->coded_fragis[_pli];
982   ncoded_fragis=_pipe->ncoded_fragis[_pli];
983   uncoded_fragis=_pipe->uncoded_fragis[_pli];
984   nuncoded_fragis=_pipe->nuncoded_fragis[_pli];
985   froffset=_pipe->froffset[_pli];
986   for(sbi=_sbi_start;sbi<_sbi_end;sbi++){
987     /*Worst case token stack usage for 1 fragment.*/
988     oc_token_checkpoint stack[64];
989     oc_rd_metric        mo;
990     int                 quadi;
991     int                 bi;
992     memset(&mo,0,sizeof(mo));
993     for(quadi=0;quadi<4;quadi++)for(bi=0;bi<4;bi++){
994       ptrdiff_t fragi;
995       fragi=sb_maps[sbi][quadi][bi];
996       if(fragi>=0){
997         oc_token_checkpoint *stackptr;
998         unsigned             rd_scale;
999         unsigned             rd_iscale;
1000         rd_scale=mcu_rd_scale[fragi-froffset];
1001         rd_iscale=mcu_rd_iscale[fragi-froffset];
1002         stackptr=stack;
1003         if(oc_enc_block_transform_quantize(_enc,_pipe,_pli,fragi,
1004          rd_scale,rd_iscale,&mo,fr,&stackptr)){
1005           coded_fragis[ncoded_fragis++]=fragi;
1006         }
1007         else *(uncoded_fragis-++nuncoded_fragis)=fragi;
1008       }
1009     }
1010     oc_fr_state_flush_sb(fr);
1011     sb_flags[sbi].coded_fully=fr->sb_full;
1012     sb_flags[sbi].coded_partially=fr->sb_partial;
1013   }
1014   _pipe->ncoded_fragis[_pli]=ncoded_fragis;
1015   _pipe->nuncoded_fragis[_pli]=nuncoded_fragis;
1016 }
1017
1018 /*Mode decision is done by exhaustively examining all potential choices.
1019   Obviously, doing the motion compensation, fDCT, tokenization, and then
1020    counting the bits each token uses is computationally expensive.
1021   Theora's EOB runs can also split the cost of these tokens across multiple
1022    fragments, and naturally we don't know what the optimal choice of Huffman
1023    codes will be until we know all the tokens we're going to encode in all the
1024    fragments.
1025   So we use a simple approach to estimating the bit cost and distortion of each
1026    mode based upon the SATD value of the residual before coding.
1027   The mathematics behind the technique are outlined by Kim \cite{Kim03}, but
1028    the process (modified somewhat from that of the paper) is very simple.
1029   We build a non-linear regression of the mappings from
1030    (pre-transform+quantization) SATD to (post-transform+quantization) bits and
1031    SSD for each qi.
1032   A separate set of mappings is kept for each quantization type and color
1033    plane.
1034   The mappings are constructed by partitioning the SATD values into a small
1035    number of bins (currently 24) and using a linear regression in each bin
1036    (as opposed to the 0th-order regression used by Kim).
1037   The bit counts and SSD measurements are obtained by examining actual encoded
1038    frames, with appropriate lambda values and optimal Huffman codes selected.
1039   EOB bits are assigned to the fragment that started the EOB run (as opposed to
1040    dividing them among all the blocks in the run; the latter approach seems
1041    more theoretically correct, but Monty's testing showed a small improvement
1042    with the former, though that may have been merely statistical noise).
1043
1044   @ARTICLE{Kim03,
1045     author="Hyun Mun Kim",
1046     title="Adaptive Rate Control Using Nonlinear Regression",
1047     journal="IEEE Transactions on Circuits and Systems for Video Technology",
1048     volume=13,
1049     number=5,
1050     pages="432--439",
1051     month=May,
1052     year=2003
1053   }*/
1054
1055 /*Computes (_ssd+_lambda*_rate)/(1<<OC_BIT_SCALE) with rounding, avoiding
1056    overflow for large lambda values.*/
1057 #define OC_MODE_RD_COST(_ssd,_rate,_lambda) \
1058  ((_ssd)>>OC_BIT_SCALE)+((_rate)>>OC_BIT_SCALE)*(_lambda) \
1059  +(((_ssd)&(1<<OC_BIT_SCALE)-1)+((_rate)&(1<<OC_BIT_SCALE)-1)*(_lambda) \
1060  +((1<<OC_BIT_SCALE)>>1)>>OC_BIT_SCALE)
1061
1062 static void oc_enc_mode_rd_init(oc_enc_ctx *_enc){
1063   int qii;
1064 #if defined(OC_COLLECT_METRICS)
1065   oc_enc_mode_metrics_load(_enc);
1066 #endif
1067   for(qii=0;qii<_enc->state.nqis;qii++){
1068     int qi;
1069     int pli;
1070     qi=_enc->state.qis[qii];
1071     for(pli=0;pli<3;pli++){
1072       int qti;
1073       for(qti=0;qti<2;qti++){
1074         int log_plq;
1075         int modeline;
1076         int bin;
1077         int dx;
1078         int dq;
1079         log_plq=_enc->log_plq[qi][pli][qti];
1080         /*Find the pair of rows in the mode table that bracket this quantizer.
1081           If it falls outside the range the table covers, then we just use a
1082            pair on the edge for linear extrapolation.*/
1083         for(modeline=0;modeline<OC_LOGQ_BINS-1&&
1084          OC_MODE_LOGQ[modeline+1][pli][qti]>log_plq;modeline++);
1085         /*Interpolate a row for this quantizer.*/
1086         dx=OC_MODE_LOGQ[modeline][pli][qti]-log_plq;
1087         dq=OC_MODE_LOGQ[modeline][pli][qti]-OC_MODE_LOGQ[modeline+1][pli][qti];
1088         if(dq==0)dq=1;
1089         for(bin=0;bin<OC_COMP_BINS;bin++){
1090           int y0;
1091           int z0;
1092           int dy;
1093           int dz;
1094           y0=OC_MODE_RD[modeline][pli][qti][bin].rate;
1095           z0=OC_MODE_RD[modeline][pli][qti][bin].rmse;
1096           dy=OC_MODE_RD[modeline+1][pli][qti][bin].rate-y0;
1097           dz=OC_MODE_RD[modeline+1][pli][qti][bin].rmse-z0;
1098           _enc->mode_rd[qii][pli][qti][bin].rate=
1099            (ogg_int16_t)OC_CLAMPI(-32768,y0+(dy*dx+(dq>>1))/dq,32767);
1100           _enc->mode_rd[qii][pli][qti][bin].rmse=
1101            (ogg_int16_t)OC_CLAMPI(-32768,z0+(dz*dx+(dq>>1))/dq,32767);
1102         }
1103       }
1104     }
1105   }
1106 }
1107
1108 /*Estimate the R-D cost of the DCT coefficients given the SATD of a block after
1109    prediction.*/
1110 static unsigned oc_dct_cost2(oc_enc_ctx *_enc,unsigned *_ssd,
1111  int _qii,int _pli,int _qti,int _satd){
1112   unsigned rmse;
1113   int      bin;
1114   int      dx;
1115   int      y0;
1116   int      z0;
1117   int      dy;
1118   int      dz;
1119   /*SATD metrics for chroma planes vary much less than luma, so we scale them
1120      by 4 to distribute them into the mode decision bins more evenly.*/
1121   _satd<<=_pli+1&2;
1122   bin=OC_MINI(_satd>>OC_SATD_SHIFT,OC_COMP_BINS-2);
1123   dx=_satd-(bin<<OC_SATD_SHIFT);
1124   y0=_enc->mode_rd[_qii][_pli][_qti][bin].rate;
1125   z0=_enc->mode_rd[_qii][_pli][_qti][bin].rmse;
1126   dy=_enc->mode_rd[_qii][_pli][_qti][bin+1].rate-y0;
1127   dz=_enc->mode_rd[_qii][_pli][_qti][bin+1].rmse-z0;
1128   rmse=OC_MAXI(z0+(dz*dx>>OC_SATD_SHIFT),0);
1129   *_ssd=rmse*rmse>>2*OC_RMSE_SCALE-OC_BIT_SCALE;
1130   return OC_MAXI(y0+(dy*dx>>OC_SATD_SHIFT),0);
1131 }
1132
1133 /*activity_avg must be positive, or flat regions could get a zero weight, which
1134    confounds analysis.
1135   We set the minimum to this value so that it also avoids the need for divide
1136    by zero checks in oc_mb_masking().*/
1137 # define OC_ACTIVITY_AVG_MIN (1<<OC_RD_SCALE_BITS)
1138
1139 static unsigned oc_mb_activity(oc_enc_ctx *_enc,unsigned _mbi,
1140  unsigned _activity[4]){
1141   const unsigned char *src;
1142   const ptrdiff_t     *frag_buf_offs;
1143   const ptrdiff_t     *sb_map;
1144   unsigned             luma;
1145   int                  ystride;
1146   ptrdiff_t            frag_offs;
1147   ptrdiff_t            fragi;
1148   int                  bi;
1149   frag_buf_offs=_enc->state.frag_buf_offs;
1150   sb_map=_enc->state.sb_maps[_mbi>>2][_mbi&3];
1151   src=_enc->state.ref_frame_data[OC_FRAME_IO];
1152   ystride=_enc->state.ref_ystride[0];
1153   luma=0;
1154   for(bi=0;bi<4;bi++){
1155     const unsigned char *s;
1156     unsigned             x;
1157     unsigned             x2;
1158     unsigned             act;
1159     int                  i;
1160     int                  j;
1161     fragi=sb_map[bi];
1162     frag_offs=frag_buf_offs[fragi];
1163     /*TODO: This could be replaced with SATD^2, since we already have to
1164        compute SATD.*/
1165     x=x2=0;
1166     s=src+frag_offs;
1167     for(i=0;i<8;i++){
1168       for(j=0;j<8;j++){
1169         unsigned c;
1170         c=s[j];
1171         x+=c;
1172         x2+=c*c;
1173       }
1174       s+=ystride;
1175     }
1176     luma+=x;
1177     act=(x2<<6)-x*x;
1178     if(act<8<<12){
1179       /*The region is flat.*/
1180       act=OC_MINI(act,5<<12);
1181     }
1182     else{
1183       unsigned e1;
1184       unsigned e2;
1185       unsigned e3;
1186       unsigned e4;
1187       /*Test for an edge.
1188         TODO: There are probably much simpler ways to do this (e.g., it could
1189          probably be combined with the SATD calculation).
1190         Alternatively, we could split the block around the mean and compute the
1191          reduction in variance in each half.
1192         For a Gaussian source the reduction should be
1193          (1-2/pi) ~= 0.36338022763241865692446494650994.
1194         Significantly more reduction is a good indication of a bi-level image.
1195         This has the advantage of identifying, in addition to straight edges,
1196          small text regions, which would otherwise be classified as "texture".*/
1197       e1=e2=e3=e4=0;
1198       s=src+frag_offs-1;
1199       for(i=0;i<8;i++){
1200         for(j=0;j<8;j++){
1201           e1+=abs((s[j+2]-s[j]<<1)+(s-ystride)[j+2]-(s-ystride)[j]
1202            +(s+ystride)[j+2]-(s+ystride)[j]);
1203           e2+=abs(((s+ystride)[j+1]-(s-ystride)[j+1]<<1)
1204            +(s+ystride)[j]-(s-ystride)[j]+(s+ystride)[j+2]-(s-ystride)[j+2]);
1205           e3+=abs(((s+ystride)[j+2]-(s-ystride)[j]<<1)
1206            +(s+ystride)[j+1]-s[j]+s[j+2]-(s-ystride)[j+1]);
1207           e4+=abs(((s+ystride)[j]-(s-ystride)[j+2]<<1)
1208            +(s+ystride)[j+1]-s[j+2]+s[j]-(s-ystride)[j+1]);
1209         }
1210         s+=ystride;
1211       }
1212       /*If the largest component of the edge energy is at least 40% of the
1213          total, then classify the block as an edge block.*/
1214       if(5*OC_MAXI(OC_MAXI(e1,e2),OC_MAXI(e3,e4))>2*(e1+e2+e3+e4)){
1215          /*act=act_th*(act/act_th)**0.7
1216               =exp(log(act_th)+0.7*(log(act)-log(act_th))).
1217            Here act_th=5.0 and 0x394A=oc_blog32_q10(5<<12).*/
1218          act=oc_bexp32_q10(0x394A+(7*(oc_blog32_q10(act)-0x394A+5)/10));
1219       }
1220     }
1221     _activity[bi]=act;
1222   }
1223   return luma;
1224 }
1225
1226 static void oc_mb_activity_fast(oc_enc_ctx *_enc,unsigned _mbi,
1227  unsigned _activity[4],const unsigned _intra_satd[12]){
1228   int bi;
1229   for(bi=0;bi<4;bi++){
1230     unsigned act;
1231     act=(11*_intra_satd[bi]>>8)*_intra_satd[bi];
1232     if(act<8<<12){
1233       /*The region is flat.*/
1234       act=OC_MINI(act,5<<12);
1235     }
1236     _activity[bi]=act;
1237   }
1238 }
1239
1240 /*Compute the masking scales for the blocks in a macro block.
1241   All masking is computed from the luma blocks.
1242   We derive scaling factors for the chroma blocks from these, and use the same
1243    ones for all chroma blocks, regardless of the subsampling.
1244   It's possible for luma to be perfectly flat and yet have high chroma energy,
1245    but this is unlikely in non-artificial images, and not a case that has been
1246    addressed by any research to my knowledge.
1247   The output of the masking process is two scale factors, which are fed into
1248    the various R-D optimizations.
1249   The first, rd_scale, is applied to D in the equation
1250     D*rd_scale+lambda*R.
1251   This is the form that must be used to properly combine scores from multiple
1252    blocks, and can be interpreted as scaling distortions by their visibility.
1253   The inverse, rd_iscale, is applied to lambda in the equation
1254     D+rd_iscale*lambda*R.
1255   This is equivalent to the first form within a single block, but much faster
1256    to use when evaluating many possible distortions (e.g., during actual
1257    quantization, where separate distortions are evaluated for every
1258    coefficient).
1259   The two macros OC_RD_SCALE(rd_scale,d) and OC_RD_ISCALE(rd_iscale,lambda) are
1260    used to perform the multiplications with the proper re-scaling for the range
1261    of the scaling factors.
1262   Many researchers apply masking values directly to the quantizers used, and
1263    not to the R-D cost.
1264   Since we generally use MSE for D, rd_scale must use the square of their
1265    values to generate an equivalent effect.*/
1266 static unsigned oc_mb_masking(unsigned _rd_scale[5],unsigned _rd_iscale[5],
1267  const ogg_uint16_t _chroma_rd_scale[2],const unsigned _activity[4],
1268  unsigned _activity_avg,unsigned _luma,unsigned _luma_avg){
1269   unsigned activity_sum;
1270   unsigned la;
1271   unsigned lb;
1272   unsigned d;
1273   int      bi;
1274   int      bi_min;
1275   int      bi_min2;
1276   /*The ratio lb/la is meant to approximate
1277      ((((_luma-16)/219)*(255/128))**0.649**0.4**2), which is the
1278      effective luminance masking from~\cite{LKW06} (including the self-masking
1279      deflator).
1280     The following actually turns out to be a pretty good approximation for
1281      _luma>75 or so.
1282     For smaller values luminance does not really follow Weber's Law anyway, and
1283      this approximation gives a much less aggressive bitrate boost in this
1284      region.
1285     Though some researchers claim that contrast sensitivity actually decreases
1286      for very low luminance values, in my experience excessive brightness on
1287      LCDs or buggy color conversions (e.g., treating Y' as full-range instead
1288      of the CCIR 601 range) make artifacts in such regions extremely visible.
1289     We substitute _luma_avg for 128 to allow the strength of the masking to
1290      vary with the actual average image luminance, within certain limits (the
1291      caller has clamped _luma_avg to the range [90,160], inclusive).
1292     @ARTICLE{LKW06,
1293       author="Zhen Liu and Lina J. Karam and Andrew B. Watson",
1294       title="{JPEG2000} Encoding With Perceptual Distortion Control",
1295       journal="{IEEE} Transactions on Image Processing",
1296       volume=15,
1297       number=7,
1298       pages="1763--1778",
1299       month=Jul,
1300       year=2006
1301     }*/
1302 #if 0
1303   la=_luma+4*_luma_avg;
1304   lb=4*_luma+_luma_avg;
1305 #else
1306   /*Disable luminance masking.*/
1307   la=lb=1;
1308 #endif
1309   activity_sum=0;
1310   for(bi=0;bi<4;bi++){
1311     unsigned a;
1312     unsigned b;
1313     activity_sum+=_activity[bi];
1314     /*Apply activity masking.*/
1315     a=_activity[bi]+4*_activity_avg;
1316     b=4*_activity[bi]+_activity_avg;
1317     d=OC_RD_SCALE(b,1);
1318     /*And luminance masking.*/
1319     d=(a+(d>>1))/d;
1320     _rd_scale[bi]=(d*la+(lb>>1))/lb;
1321     /*And now the inverse.*/
1322     d=OC_MAXI(OC_RD_ISCALE(a,1),1);
1323     d=(b+(d>>1))/d;
1324     _rd_iscale[bi]=(d*lb+(la>>1))/la;
1325   }
1326   /*Now compute scaling factors for chroma blocks.
1327     We start by finding the two smallest iscales from the luma blocks.*/
1328   bi_min=_rd_iscale[1]<_rd_iscale[0];
1329   bi_min2=1-bi_min;
1330   for(bi=2;bi<4;bi++){
1331     if(_rd_iscale[bi]<_rd_iscale[bi_min]){
1332       bi_min2=bi_min;
1333       bi_min=bi;
1334     }
1335     else if(_rd_iscale[bi]<_rd_iscale[bi_min2])bi_min2=bi;
1336   }
1337   /*If the minimum iscale is less than 1.0, use the second smallest instead,
1338      and force the value to at least 1.0 (inflating chroma is a waste).*/
1339   if(_rd_iscale[bi_min]<(1<<OC_RD_ISCALE_BITS))bi_min=bi_min2;
1340   d=OC_MINI(_rd_scale[bi_min],1<<OC_RD_SCALE_BITS);
1341   _rd_scale[4]=OC_RD_SCALE(d,_chroma_rd_scale[0]);
1342   d=OC_MAXI(_rd_iscale[bi_min],1<<OC_RD_ISCALE_BITS);
1343   _rd_iscale[4]=OC_RD_ISCALE(d,_chroma_rd_scale[1]);
1344   return activity_sum;
1345 }
1346
1347 static int oc_mb_intra_satd(oc_enc_ctx *_enc,unsigned _mbi,
1348  unsigned _frag_satd[12]){
1349   const unsigned char   *src;
1350   const ptrdiff_t       *frag_buf_offs;
1351   const ptrdiff_t       *sb_map;
1352   const oc_mb_map_plane *mb_map;
1353   const unsigned char   *map_idxs;
1354   int                    map_nidxs;
1355   int                    mapii;
1356   int                    mapi;
1357   int                    ystride;
1358   int                    pli;
1359   int                    bi;
1360   ptrdiff_t              fragi;
1361   ptrdiff_t              frag_offs;
1362   unsigned               luma;
1363   int                    dc;
1364   frag_buf_offs=_enc->state.frag_buf_offs;
1365   sb_map=_enc->state.sb_maps[_mbi>>2][_mbi&3];
1366   src=_enc->state.ref_frame_data[OC_FRAME_IO];
1367   ystride=_enc->state.ref_ystride[0];
1368   luma=0;
1369   for(bi=0;bi<4;bi++){
1370     fragi=sb_map[bi];
1371     frag_offs=frag_buf_offs[fragi];
1372     _frag_satd[bi]=oc_enc_frag_intra_satd(_enc,&dc,src+frag_offs,ystride);
1373     luma+=dc;
1374   }
1375   mb_map=(const oc_mb_map_plane *)_enc->state.mb_maps[_mbi];
1376   map_idxs=OC_MB_MAP_IDXS[_enc->state.info.pixel_fmt];
1377   map_nidxs=OC_MB_MAP_NIDXS[_enc->state.info.pixel_fmt];
1378   /*Note: This assumes ref_ystride[1]==ref_ystride[2].*/
1379   ystride=_enc->state.ref_ystride[1];
1380   for(mapii=4;mapii<map_nidxs;mapii++){
1381     mapi=map_idxs[mapii];
1382     pli=mapi>>2;
1383     bi=mapi&3;
1384     fragi=mb_map[pli][bi];
1385     frag_offs=frag_buf_offs[fragi];
1386     _frag_satd[mapii]=oc_enc_frag_intra_satd(_enc,&dc,src+frag_offs,ystride);
1387   }
1388   return luma;
1389 }
1390
1391 /*Select luma block-level quantizers for a MB in an INTRA frame.*/
1392 static unsigned oc_analyze_intra_mb_luma(oc_enc_ctx *_enc,
1393  const oc_qii_state *_qs,unsigned _mbi,const unsigned _rd_scale[4]){
1394   const unsigned char *src;
1395   const ptrdiff_t     *frag_buf_offs;
1396   const oc_sb_map     *sb_maps;
1397   oc_fragment         *frags;
1398   ptrdiff_t            frag_offs;
1399   ptrdiff_t            fragi;
1400   oc_qii_state         qs[4][3];
1401   unsigned             cost[4][3];
1402   unsigned             ssd[4][3];
1403   unsigned             rate[4][3];
1404   int                  prev[3][3];
1405   unsigned             satd;
1406   int                  dc;
1407   unsigned             best_cost;
1408   unsigned             best_ssd;
1409   unsigned             best_rate;
1410   int                  best_qii;
1411   int                  qii;
1412   int                  lambda;
1413   int                  ystride;
1414   int                  nqis;
1415   int                  bi;
1416   frag_buf_offs=_enc->state.frag_buf_offs;
1417   sb_maps=(const oc_sb_map *)_enc->state.sb_maps;
1418   src=_enc->state.ref_frame_data[OC_FRAME_IO];
1419   ystride=_enc->state.ref_ystride[0];
1420   fragi=sb_maps[_mbi>>2][_mbi&3][0];
1421   frag_offs=frag_buf_offs[fragi];
1422   satd=oc_enc_frag_intra_satd(_enc,&dc,src+frag_offs,ystride);
1423   nqis=_enc->state.nqis;
1424   lambda=_enc->lambda;
1425   for(qii=0;qii<nqis;qii++){
1426     oc_qii_state_advance(qs[0]+qii,_qs,qii);
1427     rate[0][qii]=oc_dct_cost2(_enc,ssd[0]+qii,qii,0,0,satd)
1428      +(qs[0][qii].bits-_qs->bits<<OC_BIT_SCALE);
1429     ssd[0][qii]=OC_RD_SCALE(ssd[0][qii],_rd_scale[0]);
1430     cost[0][qii]=OC_MODE_RD_COST(ssd[0][qii],rate[0][qii],lambda);
1431   }
1432   for(bi=1;bi<4;bi++){
1433     fragi=sb_maps[_mbi>>2][_mbi&3][bi];
1434     frag_offs=frag_buf_offs[fragi];
1435     satd=oc_enc_frag_intra_satd(_enc,&dc,src+frag_offs,ystride);
1436     for(qii=0;qii<nqis;qii++){
1437       oc_qii_state qt[3];
1438       unsigned     cur_ssd;
1439       unsigned     cur_rate;
1440       int          best_qij;
1441       int          qij;
1442       oc_qii_state_advance(qt+0,qs[bi-1]+0,qii);
1443       cur_rate=oc_dct_cost2(_enc,&cur_ssd,qii,0,0,satd);
1444       cur_ssd=OC_RD_SCALE(cur_ssd,_rd_scale[bi]);
1445       best_ssd=ssd[bi-1][0]+cur_ssd;
1446       best_rate=rate[bi-1][0]+cur_rate
1447        +(qt[0].bits-qs[bi-1][0].bits<<OC_BIT_SCALE);
1448       best_cost=OC_MODE_RD_COST(best_ssd,best_rate,lambda);
1449       best_qij=0;
1450       for(qij=1;qij<nqis;qij++){
1451         unsigned chain_ssd;
1452         unsigned chain_rate;
1453         unsigned chain_cost;
1454         oc_qii_state_advance(qt+qij,qs[bi-1]+qij,qii);
1455         chain_ssd=ssd[bi-1][qij]+cur_ssd;
1456         chain_rate=rate[bi-1][qij]+cur_rate
1457          +(qt[qij].bits-qs[bi-1][qij].bits<<OC_BIT_SCALE);
1458         chain_cost=OC_MODE_RD_COST(chain_ssd,chain_rate,lambda);
1459         if(chain_cost<best_cost){
1460           best_cost=chain_cost;
1461           best_ssd=chain_ssd;
1462           best_rate=chain_rate;
1463           best_qij=qij;
1464         }
1465       }
1466       *(qs[bi]+qii)=*(qt+best_qij);
1467       cost[bi][qii]=best_cost;
1468       ssd[bi][qii]=best_ssd;
1469       rate[bi][qii]=best_rate;
1470       prev[bi-1][qii]=best_qij;
1471     }
1472   }
1473   best_qii=0;
1474   best_cost=cost[3][0];
1475   for(qii=1;qii<nqis;qii++){
1476     if(cost[3][qii]<best_cost){
1477       best_cost=cost[3][qii];
1478       best_qii=qii;
1479     }
1480   }
1481   frags=_enc->state.frags;
1482   for(bi=3;;){
1483     fragi=sb_maps[_mbi>>2][_mbi&3][bi];
1484     frags[fragi].qii=best_qii;
1485     if(bi--<=0)break;
1486     best_qii=prev[bi][best_qii];
1487   }
1488   return best_cost;
1489 }
1490
1491 /*Select a block-level quantizer for a single chroma block in an INTRA frame.*/
1492 static unsigned oc_analyze_intra_chroma_block(oc_enc_ctx *_enc,
1493  const oc_qii_state *_qs,int _pli,ptrdiff_t _fragi,unsigned _rd_scale){
1494   const unsigned char *src;
1495   oc_fragment         *frags;
1496   ptrdiff_t            frag_offs;
1497   oc_qii_state         qt[3];
1498   unsigned             cost[3];
1499   unsigned             satd;
1500   int                  dc;
1501   unsigned             best_cost;
1502   int                  best_qii;
1503   int                  qii;
1504   int                  lambda;
1505   int                  ystride;
1506   int                  nqis;
1507   src=_enc->state.ref_frame_data[OC_FRAME_IO];
1508   ystride=_enc->state.ref_ystride[_pli];
1509   frag_offs=_enc->state.frag_buf_offs[_fragi];
1510   satd=oc_enc_frag_intra_satd(_enc,&dc,src+frag_offs,ystride);
1511   /*Most chroma blocks have no AC coefficients to speak of anyway, so it's not
1512      worth spending the bits to change the AC quantizer.
1513     TODO: This may be worth revisiting when we separate out DC and AC
1514      predictions from SATD.*/
1515 #if 0
1516   nqis=_enc->state.nqis;
1517 #else
1518   nqis=1;
1519 #endif
1520   lambda=_enc->lambda;
1521   best_qii=0;
1522   for(qii=0;qii<nqis;qii++){
1523     unsigned cur_rate;
1524     unsigned cur_ssd;
1525     oc_qii_state_advance(qt+qii,_qs,qii);
1526     cur_rate=oc_dct_cost2(_enc,&cur_ssd,qii,_pli,0,satd)
1527      +(qt[qii].bits-_qs->bits<<OC_BIT_SCALE);
1528     cur_ssd=OC_RD_SCALE(cur_ssd,_rd_scale);
1529     cost[qii]=OC_MODE_RD_COST(cur_ssd,cur_rate,lambda);
1530   }
1531   best_cost=cost[0];
1532   for(qii=1;qii<nqis;qii++){
1533     if(cost[qii]<best_cost){
1534       best_cost=cost[qii];
1535       best_qii=qii;
1536     }
1537   }
1538   frags=_enc->state.frags;
1539   frags[_fragi].qii=best_qii;
1540   return best_cost;
1541 }
1542
1543 static void oc_enc_mb_transform_quantize_intra_luma(oc_enc_ctx *_enc,
1544  oc_enc_pipeline_state *_pipe,unsigned _mbi,
1545  const unsigned _rd_scale[4],const unsigned _rd_iscale[4]){
1546   /*Worst case token stack usage for 4 fragments.*/
1547   oc_token_checkpoint  stack[64*4];
1548   oc_token_checkpoint *stackptr;
1549   const oc_sb_map     *sb_maps;
1550   oc_fragment         *frags;
1551   ptrdiff_t           *coded_fragis;
1552   ptrdiff_t            ncoded_fragis;
1553   ptrdiff_t            fragi;
1554   int                  bi;
1555   sb_maps=(const oc_sb_map *)_enc->state.sb_maps;
1556   frags=_enc->state.frags;
1557   coded_fragis=_pipe->coded_fragis[0];
1558   ncoded_fragis=_pipe->ncoded_fragis[0];
1559   stackptr=stack;
1560   for(bi=0;bi<4;bi++){
1561     fragi=sb_maps[_mbi>>2][_mbi&3][bi];
1562     frags[fragi].refi=OC_FRAME_SELF;
1563     frags[fragi].mb_mode=OC_MODE_INTRA;
1564     oc_enc_block_transform_quantize(_enc,_pipe,0,fragi,
1565      _rd_scale[bi],_rd_iscale[bi],NULL,NULL,&stackptr);
1566     coded_fragis[ncoded_fragis++]=fragi;
1567   }
1568   _pipe->ncoded_fragis[0]=ncoded_fragis;
1569 }
1570
1571 static void oc_enc_sb_transform_quantize_intra_chroma(oc_enc_ctx *_enc,
1572  oc_enc_pipeline_state *_pipe,int _pli,int _sbi_start,int _sbi_end){
1573   const ogg_uint16_t *mcu_rd_scale;
1574   const ogg_uint16_t *mcu_rd_iscale;
1575   const oc_sb_map    *sb_maps;
1576   ptrdiff_t          *coded_fragis;
1577   ptrdiff_t           ncoded_fragis;
1578   ptrdiff_t           froffset;
1579   int                 sbi;
1580   mcu_rd_scale=(const ogg_uint16_t *)_enc->mcu_rd_scale;
1581   mcu_rd_iscale=(const ogg_uint16_t *)_enc->mcu_rd_iscale;
1582   sb_maps=(const oc_sb_map *)_enc->state.sb_maps;
1583   coded_fragis=_pipe->coded_fragis[_pli];
1584   ncoded_fragis=_pipe->ncoded_fragis[_pli];
1585   froffset=_pipe->froffset[_pli];
1586   for(sbi=_sbi_start;sbi<_sbi_end;sbi++){
1587     /*Worst case token stack usage for 1 fragment.*/
1588     oc_token_checkpoint stack[64];
1589     int                 quadi;
1590     int                 bi;
1591     for(quadi=0;quadi<4;quadi++)for(bi=0;bi<4;bi++){
1592       ptrdiff_t fragi;
1593       fragi=sb_maps[sbi][quadi][bi];
1594       if(fragi>=0){
1595         oc_token_checkpoint *stackptr;
1596         unsigned             rd_scale;
1597         unsigned             rd_iscale;
1598         rd_scale=mcu_rd_scale[fragi-froffset];
1599         rd_iscale=mcu_rd_iscale[fragi-froffset];
1600         oc_analyze_intra_chroma_block(_enc,_pipe->qs+_pli,_pli,fragi,rd_scale);
1601         stackptr=stack;
1602         oc_enc_block_transform_quantize(_enc,_pipe,_pli,fragi,
1603          rd_scale,rd_iscale,NULL,NULL,&stackptr);
1604         coded_fragis[ncoded_fragis++]=fragi;
1605       }
1606     }
1607   }
1608   _pipe->ncoded_fragis[_pli]=ncoded_fragis;
1609 }
1610
1611 /*Analysis stage for an INTRA frame.*/
1612 void oc_enc_analyze_intra(oc_enc_ctx *_enc,int _recode){
1613   ogg_int64_t             activity_sum;
1614   ogg_int64_t             luma_sum;
1615   unsigned                activity_avg;
1616   unsigned                luma_avg;
1617   const ogg_uint16_t     *chroma_rd_scale;
1618   ogg_uint16_t           *mcu_rd_scale;
1619   ogg_uint16_t           *mcu_rd_iscale;
1620   const unsigned char    *map_idxs;
1621   int                     nmap_idxs;
1622   oc_sb_flags            *sb_flags;
1623   signed char            *mb_modes;
1624   const oc_mb_map        *mb_maps;
1625   const oc_sb_map        *sb_maps;
1626   oc_fragment            *frags;
1627   unsigned                stripe_sby;
1628   unsigned                mcu_nvsbs;
1629   int                     notstart;
1630   int                     notdone;
1631   int                     refi;
1632   int                     pli;
1633   _enc->state.frame_type=OC_INTRA_FRAME;
1634   oc_enc_tokenize_start(_enc);
1635   oc_enc_pipeline_init(_enc,&_enc->pipe);
1636   oc_enc_mode_rd_init(_enc);
1637   activity_sum=luma_sum=0;
1638   activity_avg=_enc->activity_avg;
1639   luma_avg=OC_CLAMPI(90<<8,_enc->luma_avg,160<<8);
1640   chroma_rd_scale=_enc->chroma_rd_scale[OC_INTRA_FRAME][_enc->state.qis[0]];
1641   mcu_rd_scale=_enc->mcu_rd_scale;
1642   mcu_rd_iscale=_enc->mcu_rd_iscale;
1643   /*Choose MVs and MB modes and quantize and code luma.
1644     Must be done in Hilbert order.*/
1645   map_idxs=OC_MB_MAP_IDXS[_enc->state.info.pixel_fmt];
1646   nmap_idxs=OC_MB_MAP_NIDXS[_enc->state.info.pixel_fmt];
1647   _enc->state.ncoded_fragis[0]=0;
1648   _enc->state.ncoded_fragis[1]=0;
1649   _enc->state.ncoded_fragis[2]=0;
1650   sb_flags=_enc->state.sb_flags;
1651   mb_modes=_enc->state.mb_modes;
1652   mb_maps=(const oc_mb_map *)_enc->state.mb_maps;
1653   sb_maps=(const oc_sb_map *)_enc->state.sb_maps;
1654   frags=_enc->state.frags;
1655   notstart=0;
1656   notdone=1;
1657   mcu_nvsbs=_enc->mcu_nvsbs;
1658   for(stripe_sby=0;notdone;stripe_sby+=mcu_nvsbs){
1659     ptrdiff_t cfroffset;
1660     unsigned  sbi;
1661     unsigned  sbi_end;
1662     notdone=oc_enc_pipeline_set_stripe(_enc,&_enc->pipe,stripe_sby);
1663     sbi_end=_enc->pipe.sbi_end[0];
1664     cfroffset=_enc->pipe.froffset[1];
1665     for(sbi=_enc->pipe.sbi0[0];sbi<sbi_end;sbi++){
1666       int quadi;
1667       /*Mode addressing is through Y plane, always 4 MB per SB.*/
1668       for(quadi=0;quadi<4;quadi++)if(sb_flags[sbi].quad_valid&1<<quadi){
1669         unsigned  activity[4];
1670         unsigned  rd_scale[5];
1671         unsigned  rd_iscale[5];
1672         unsigned  luma;
1673         unsigned  mbi;
1674         int       mapii;
1675         int       mapi;
1676         int       bi;
1677         ptrdiff_t fragi;
1678         mbi=sbi<<2|quadi;
1679         /*Activity masking.*/
1680         if(_enc->sp_level<OC_SP_LEVEL_FAST_ANALYSIS){
1681           luma=oc_mb_activity(_enc,mbi,activity);
1682         }
1683         else{
1684           unsigned intra_satd[12];
1685           luma=oc_mb_intra_satd(_enc,mbi,intra_satd);
1686           oc_mb_activity_fast(_enc,mbi,activity,intra_satd);
1687           for(bi=0;bi<4;bi++)frags[sb_maps[mbi>>2][mbi&3][bi]].qii=0;
1688         }
1689         activity_sum+=oc_mb_masking(rd_scale,rd_iscale,
1690          chroma_rd_scale,activity,activity_avg,luma,luma_avg);
1691         luma_sum+=luma;
1692         /*Motion estimation:
1693           We do a basic 1MV search for all macroblocks, coded or not,
1694            keyframe or not, unless we aren't using motion estimation at all.*/
1695         if(!_recode&&_enc->state.curframe_num>0&&
1696          _enc->sp_level<OC_SP_LEVEL_NOMC&&_enc->keyframe_frequency_force>1){
1697           oc_mcenc_search(_enc,mbi);
1698         }
1699         if(_enc->sp_level<OC_SP_LEVEL_FAST_ANALYSIS){
1700           oc_analyze_intra_mb_luma(_enc,_enc->pipe.qs+0,mbi,rd_scale);
1701         }
1702         mb_modes[mbi]=OC_MODE_INTRA;
1703         oc_enc_mb_transform_quantize_intra_luma(_enc,&_enc->pipe,
1704          mbi,rd_scale,rd_iscale);
1705         /*Propagate final MB mode and MVs to the chroma blocks.*/
1706         for(mapii=4;mapii<nmap_idxs;mapii++){
1707           mapi=map_idxs[mapii];
1708           pli=mapi>>2;
1709           bi=mapi&3;
1710           fragi=mb_maps[mbi][pli][bi];
1711           frags[fragi].refi=OC_FRAME_SELF;
1712           frags[fragi].mb_mode=OC_MODE_INTRA;
1713         }
1714         /*Save masking scale factors for chroma blocks.*/
1715         for(mapii=4;mapii<(nmap_idxs-4>>1)+4;mapii++){
1716           mapi=map_idxs[mapii];
1717           bi=mapi&3;
1718           fragi=mb_maps[mbi][1][bi];
1719           mcu_rd_scale[fragi-cfroffset]=(ogg_uint16_t)rd_scale[4];
1720           mcu_rd_iscale[fragi-cfroffset]=(ogg_uint16_t)rd_iscale[4];
1721         }
1722       }
1723     }
1724     oc_enc_pipeline_finish_mcu_plane(_enc,&_enc->pipe,0,notstart,notdone);
1725     /*Code chroma planes.*/
1726     for(pli=1;pli<3;pli++){
1727       oc_enc_sb_transform_quantize_intra_chroma(_enc,&_enc->pipe,
1728        pli,_enc->pipe.sbi0[pli],_enc->pipe.sbi_end[pli]);
1729       oc_enc_pipeline_finish_mcu_plane(_enc,&_enc->pipe,pli,notstart,notdone);
1730     }
1731     notstart=1;
1732   }
1733   /*Compute the average block activity and MB luma score for the frame.*/
1734   _enc->activity_avg=OC_MAXI(OC_ACTIVITY_AVG_MIN,
1735    (unsigned)((activity_sum+(_enc->state.fplanes[0].nfrags>>1))/
1736    _enc->state.fplanes[0].nfrags));
1737   _enc->luma_avg=(unsigned)((luma_sum+(_enc->state.nmbs>>1))/_enc->state.nmbs);
1738   /*Finish filling in the reference frame borders.*/
1739   refi=_enc->state.ref_frame_idx[OC_FRAME_SELF];
1740   for(pli=0;pli<3;pli++)oc_state_borders_fill_caps(&_enc->state,refi,pli);
1741   _enc->state.ntotal_coded_fragis=_enc->state.nfrags;
1742 }
1743
1744
1745
1746 /*Cost information about a MB mode.*/
1747 struct oc_mode_choice{
1748   unsigned      cost;
1749   unsigned      ssd;
1750   unsigned      rate;
1751   unsigned      overhead;
1752   unsigned char qii[12];
1753 };
1754
1755
1756
1757 static void oc_mode_set_cost(oc_mode_choice *_modec,int _lambda){
1758   _modec->cost=OC_MODE_RD_COST(_modec->ssd,
1759    _modec->rate+_modec->overhead,_lambda);
1760 }
1761
1762 /*A set of skip SSD's to use to disable early skipping.*/
1763 static const unsigned OC_NOSKIP[12]={
1764   UINT_MAX,UINT_MAX,UINT_MAX,UINT_MAX,
1765   UINT_MAX,UINT_MAX,UINT_MAX,UINT_MAX,
1766   UINT_MAX,UINT_MAX,UINT_MAX,UINT_MAX
1767 };
1768
1769 /*The estimated number of bits used by a coded chroma block to specify the AC
1770    quantizer.
1771   TODO: Currently this is just 0.5*log2(3) (estimating about 50% compression);
1772    measurements suggest this is in the right ballpark, but it varies somewhat
1773    with lambda.*/
1774 #define OC_CHROMA_QII_RATE ((0xCAE00D1DU>>31-OC_BIT_SCALE)+1>>1)
1775
1776 static void oc_analyze_mb_mode_luma(oc_enc_ctx *_enc,
1777  oc_mode_choice *_modec,const oc_fr_state *_fr,const oc_qii_state *_qs,
1778  const unsigned _frag_satd[12],const unsigned _skip_ssd[12],
1779  const unsigned _rd_scale[4],int _qti){
1780   oc_fr_state  fr;
1781   oc_qii_state qs;
1782   unsigned     ssd;
1783   unsigned     rate;
1784   unsigned     satd;
1785   unsigned     best_ssd;
1786   unsigned     best_rate;
1787   int          best_fri;
1788   int          best_qii;
1789   int          lambda;
1790   int          nqis;
1791   int          nskipped;
1792   int          bi;
1793   lambda=_enc->lambda;
1794   nqis=_enc->state.nqis;
1795   /*We could do a trellis optimization here, but we don't make final skip
1796      decisions until after transform+quantization, so the result wouldn't be
1797      optimal anyway.
1798     Instead we just use a greedy approach; for most SATD values, the
1799      differences between the qiis are large enough to drown out the cost to
1800      code the flags, anyway.*/
1801   *&fr=*_fr;
1802   *&qs=*_qs;
1803   ssd=rate=nskipped=0;
1804   for(bi=0;bi<4;bi++){
1805     oc_fr_state  ft[2];
1806     oc_qii_state qt[3];
1807     unsigned     best_cost;
1808     unsigned     cur_cost;
1809     unsigned     cur_ssd;
1810     unsigned     cur_rate;
1811     unsigned     cur_overhead;
1812     int          qii;
1813     satd=_frag_satd[bi];
1814     *(ft+0)=*&fr;
1815     oc_fr_code_block(ft+0);
1816     cur_overhead=ft[0].bits-fr.bits;
1817     best_rate=oc_dct_cost2(_enc,&best_ssd,0,0,_qti,satd)
1818      +(cur_overhead<<OC_BIT_SCALE);
1819     if(nqis>1){
1820       oc_qii_state_advance(qt+0,&qs,0);
1821       best_rate+=qt[0].bits-qs.bits<<OC_BIT_SCALE;
1822     }
1823     best_ssd=OC_RD_SCALE(best_ssd,_rd_scale[bi]);
1824     best_cost=OC_MODE_RD_COST(ssd+best_ssd,rate+best_rate,lambda);
1825     best_fri=0;
1826     best_qii=0;
1827     for(qii=1;qii<nqis;qii++){
1828       oc_qii_state_advance(qt+qii,&qs,qii);
1829       cur_rate=oc_dct_cost2(_enc,&cur_ssd,qii,0,_qti,satd)
1830        +(cur_overhead+qt[qii].bits-qs.bits<<OC_BIT_SCALE);
1831       cur_ssd=OC_RD_SCALE(cur_ssd,_rd_scale[bi]);
1832       cur_cost=OC_MODE_RD_COST(ssd+cur_ssd,rate+cur_rate,lambda);
1833       if(cur_cost<best_cost){
1834         best_cost=cur_cost;
1835         best_ssd=cur_ssd;
1836         best_rate=cur_rate;
1837         best_qii=qii;
1838       }
1839     }
1840     if(_skip_ssd[bi]<(UINT_MAX>>OC_BIT_SCALE)&&nskipped<3){
1841       *(ft+1)=*&fr;
1842       oc_fr_skip_block(ft+1);
1843       cur_overhead=ft[1].bits-fr.bits<<OC_BIT_SCALE;
1844       cur_ssd=_skip_ssd[bi]<<OC_BIT_SCALE;
1845       cur_cost=OC_MODE_RD_COST(ssd+cur_ssd,rate+cur_overhead,lambda);
1846       if(cur_cost<=best_cost){
1847         best_ssd=cur_ssd;
1848         best_rate=cur_overhead;
1849         best_fri=1;
1850         best_qii+=4;
1851       }
1852     }
1853     rate+=best_rate;
1854     ssd+=best_ssd;
1855     *&fr=*(ft+best_fri);
1856     if(best_fri==0)*&qs=*(qt+best_qii);
1857     else nskipped++;
1858     _modec->qii[bi]=best_qii;
1859   }
1860   _modec->ssd=ssd;
1861   _modec->rate=rate;
1862 }
1863
1864 static void oc_analyze_mb_mode_chroma(oc_enc_ctx *_enc,
1865  oc_mode_choice *_modec,const oc_fr_state *_fr,const oc_qii_state *_qs,
1866  const unsigned _frag_satd[12],const unsigned _skip_ssd[12],
1867  unsigned _rd_scale,int _qti){
1868   unsigned ssd;
1869   unsigned rate;
1870   unsigned satd;
1871   unsigned best_ssd;
1872   unsigned best_rate;
1873   int      best_qii;
1874   unsigned cur_cost;
1875   unsigned cur_ssd;
1876   unsigned cur_rate;
1877   int      lambda;
1878   int      nblocks;
1879   int      nqis;
1880   int      pli;
1881   int      bi;
1882   int      qii;
1883   lambda=_enc->lambda;
1884   /*Most chroma blocks have no AC coefficients to speak of anyway, so it's not
1885      worth spending the bits to change the AC quantizer.
1886     TODO: This may be worth revisiting when we separate out DC and AC
1887      predictions from SATD.*/
1888 #if 0
1889   nqis=_enc->state.nqis;
1890 #else
1891   nqis=1;
1892 #endif
1893   ssd=_modec->ssd;
1894   rate=_modec->rate;
1895   /*Because (except in 4:4:4 mode) we aren't considering chroma blocks in coded
1896      order, we assume a constant overhead for coded block and qii flags.*/
1897   nblocks=OC_MB_MAP_NIDXS[_enc->state.info.pixel_fmt];
1898   nblocks=(nblocks-4>>1)+4;
1899   bi=4;
1900   for(pli=1;pli<3;pli++){
1901     for(;bi<nblocks;bi++){
1902       unsigned best_cost;
1903       satd=_frag_satd[bi];
1904       best_rate=oc_dct_cost2(_enc,&best_ssd,0,pli,_qti,satd)
1905        +OC_CHROMA_QII_RATE;
1906       best_ssd=OC_RD_SCALE(best_ssd,_rd_scale);
1907       best_cost=OC_MODE_RD_COST(ssd+best_ssd,rate+best_rate,lambda);
1908       best_qii=0;
1909       for(qii=1;qii<nqis;qii++){
1910         cur_rate=oc_dct_cost2(_enc,&cur_ssd,qii,pli,_qti,satd)
1911          +OC_CHROMA_QII_RATE;
1912         cur_ssd=OC_RD_SCALE(cur_ssd,_rd_scale);
1913         cur_cost=OC_MODE_RD_COST(ssd+cur_ssd,rate+cur_rate,lambda);
1914         if(cur_cost<best_cost){
1915           best_cost=cur_cost;
1916           best_ssd=cur_ssd;
1917           best_rate=cur_rate;
1918           best_qii=qii;
1919         }
1920       }
1921       if(_skip_ssd[bi]<(UINT_MAX>>OC_BIT_SCALE)){
1922         cur_ssd=_skip_ssd[bi]<<OC_BIT_SCALE;
1923         cur_cost=OC_MODE_RD_COST(ssd+cur_ssd,rate,lambda);
1924         if(cur_cost<=best_cost){
1925           best_ssd=cur_ssd;
1926           best_rate=0;
1927           best_qii+=4;
1928         }
1929       }
1930       rate+=best_rate;
1931       ssd+=best_ssd;
1932       _modec->qii[bi]=best_qii;
1933     }
1934     nblocks=(nblocks-4<<1)+4;
1935   }
1936   _modec->ssd=ssd;
1937   _modec->rate=rate;
1938 }
1939
1940 static void oc_skip_cost(oc_enc_ctx *_enc,oc_enc_pipeline_state *_pipe,
1941  unsigned _mbi,const unsigned _rd_scale[4],unsigned _ssd[12]){
1942   const unsigned char   *src;
1943   const unsigned char   *ref;
1944   int                    ystride;
1945   const oc_fragment     *frags;
1946   const ptrdiff_t       *frag_buf_offs;
1947   const ptrdiff_t       *sb_map;
1948   const oc_mb_map_plane *mb_map;
1949   const unsigned char   *map_idxs;
1950   oc_mv                 *mvs;
1951   int                    map_nidxs;
1952   unsigned               uncoded_ssd;
1953   int                    mapii;
1954   int                    mapi;
1955   int                    pli;
1956   int                    bi;
1957   ptrdiff_t              fragi;
1958   ptrdiff_t              frag_offs;
1959   int                    borderi;
1960   src=_enc->state.ref_frame_data[OC_FRAME_IO];
1961   ref=_enc->state.ref_frame_data[OC_FRAME_PREV];
1962   ystride=_enc->state.ref_ystride[0];
1963   frags=_enc->state.frags;
1964   frag_buf_offs=_enc->state.frag_buf_offs;
1965   sb_map=_enc->state.sb_maps[_mbi>>2][_mbi&3];
1966   mvs=_enc->mb_info[_mbi].block_mv;
1967   for(bi=0;bi<4;bi++){
1968     fragi=sb_map[bi];
1969     borderi=frags[fragi].borderi;
1970     frag_offs=frag_buf_offs[fragi];
1971     if(borderi<0){
1972       uncoded_ssd=oc_enc_frag_ssd(_enc,src+frag_offs,ref+frag_offs,ystride);
1973     }
1974     else{
1975       uncoded_ssd=oc_enc_frag_border_ssd(_enc,
1976        src+frag_offs,ref+frag_offs,ystride,_enc->state.borders[borderi].mask);
1977     }
1978     /*Scale to match DCT domain and RD.*/
1979     uncoded_ssd=OC_RD_SKIP_SCALE(uncoded_ssd,_rd_scale[bi]);
1980     /*Motion is a special case; if there is more than a full-pixel motion
1981        against the prior frame, penalize skipping.
1982       TODO: The factor of two here is a kludge, but it tested out better than a
1983        hard limit.*/
1984     if(mvs[bi]!=0)uncoded_ssd*=2;
1985     _pipe->skip_ssd[0][fragi-_pipe->froffset[0]]=_ssd[bi]=uncoded_ssd;
1986   }
1987   mb_map=(const oc_mb_map_plane *)_enc->state.mb_maps[_mbi];
1988   map_nidxs=OC_MB_MAP_NIDXS[_enc->state.info.pixel_fmt];
1989   map_idxs=OC_MB_MAP_IDXS[_enc->state.info.pixel_fmt];
1990   map_nidxs=(map_nidxs-4>>1)+4;
1991   mapii=4;
1992   mvs=_enc->mb_info[_mbi].unref_mv;
1993   for(pli=1;pli<3;pli++){
1994     ystride=_enc->state.ref_ystride[pli];
1995     for(;mapii<map_nidxs;mapii++){
1996       mapi=map_idxs[mapii];
1997       bi=mapi&3;
1998       fragi=mb_map[pli][bi];
1999       borderi=frags[fragi].borderi;
2000       frag_offs=frag_buf_offs[fragi];
2001       if(borderi<0){
2002         uncoded_ssd=oc_enc_frag_ssd(_enc,src+frag_offs,ref+frag_offs,ystride);
2003       }
2004       else{
2005         uncoded_ssd=oc_enc_frag_border_ssd(_enc,
2006          src+frag_offs,ref+frag_offs,ystride,_enc->state.borders[borderi].mask);
2007       }
2008       /*Scale to match DCT domain and RD.*/
2009       uncoded_ssd=OC_RD_SKIP_SCALE(uncoded_ssd,_rd_scale[4]);
2010       /*Motion is a special case; if there is more than a full-pixel motion
2011          against the prior frame, penalize skipping.
2012         TODO: The factor of two here is a kludge, but it tested out better than
2013          a hard limit*/
2014       if(mvs[OC_FRAME_PREV]!=0)uncoded_ssd*=2;
2015       _pipe->skip_ssd[pli][fragi-_pipe->froffset[pli]]=_ssd[mapii]=uncoded_ssd;
2016     }
2017     map_nidxs=(map_nidxs-4<<1)+4;
2018   }
2019 }
2020
2021
2022 static void oc_cost_intra(oc_enc_ctx *_enc,oc_mode_choice *_modec,
2023  unsigned _mbi,const oc_fr_state *_fr,const oc_qii_state *_qs,
2024  const unsigned _frag_satd[12],const unsigned _skip_ssd[12],
2025  const unsigned _rd_scale[5]){
2026   oc_analyze_mb_mode_luma(_enc,_modec,_fr,_qs,_frag_satd,_skip_ssd,_rd_scale,0);
2027   oc_analyze_mb_mode_chroma(_enc,_modec,_fr,_qs,
2028    _frag_satd,_skip_ssd,_rd_scale[4],0);
2029   _modec->overhead=
2030    oc_mode_scheme_chooser_cost(&_enc->chooser,OC_MODE_INTRA)<<OC_BIT_SCALE;
2031   oc_mode_set_cost(_modec,_enc->lambda);
2032 }
2033
2034 static void oc_cost_inter(oc_enc_ctx *_enc,oc_mode_choice *_modec,
2035  unsigned _mbi,int _mb_mode,oc_mv _mv,
2036  const oc_fr_state *_fr,const oc_qii_state *_qs,
2037  const unsigned _skip_ssd[12],const unsigned _rd_scale[5]){
2038   unsigned               frag_satd[12];
2039   const unsigned char   *src;
2040   const unsigned char   *ref;
2041   int                    ystride;
2042   const ptrdiff_t       *frag_buf_offs;
2043   const ptrdiff_t       *sb_map;
2044   const oc_mb_map_plane *mb_map;
2045   const unsigned char   *map_idxs;
2046   int                    map_nidxs;
2047   int                    mapii;
2048   int                    mapi;
2049   int                    mv_offs[2];
2050   int                    pli;
2051   int                    bi;
2052   ptrdiff_t              fragi;
2053   ptrdiff_t              frag_offs;
2054   int                    dc;
2055   src=_enc->state.ref_frame_data[OC_FRAME_IO];
2056   ref=_enc->state.ref_frame_data[OC_FRAME_FOR_MODE(_mb_mode)];
2057   ystride=_enc->state.ref_ystride[0];
2058   frag_buf_offs=_enc->state.frag_buf_offs;
2059   sb_map=_enc->state.sb_maps[_mbi>>2][_mbi&3];
2060   _modec->rate=_modec->ssd=0;
2061   if(oc_state_get_mv_offsets(&_enc->state,mv_offs,0,_mv)>1){
2062     for(bi=0;bi<4;bi++){
2063       fragi=sb_map[bi];
2064       frag_offs=frag_buf_offs[fragi];
2065       frag_satd[bi]=oc_enc_frag_satd2(_enc,&dc,src+frag_offs,
2066        ref+frag_offs+mv_offs[0],ref+frag_offs+mv_offs[1],ystride);
2067       frag_satd[bi]+=abs(dc);
2068     }
2069   }
2070   else{
2071     for(bi=0;bi<4;bi++){
2072       fragi=sb_map[bi];
2073       frag_offs=frag_buf_offs[fragi];
2074       frag_satd[bi]=oc_enc_frag_satd(_enc,&dc,src+frag_offs,
2075        ref+frag_offs+mv_offs[0],ystride);
2076       frag_satd[bi]+=abs(dc);
2077     }
2078   }
2079   mb_map=(const oc_mb_map_plane *)_enc->state.mb_maps[_mbi];
2080   map_idxs=OC_MB_MAP_IDXS[_enc->state.info.pixel_fmt];
2081   map_nidxs=OC_MB_MAP_NIDXS[_enc->state.info.pixel_fmt];
2082   /*Note: This assumes ref_ystride[1]==ref_ystride[2].*/
2083   ystride=_enc->state.ref_ystride[1];
2084   if(oc_state_get_mv_offsets(&_enc->state,mv_offs,1,_mv)>1){
2085     for(mapii=4;mapii<map_nidxs;mapii++){
2086       mapi=map_idxs[mapii];
2087       pli=mapi>>2;
2088       bi=mapi&3;
2089       fragi=mb_map[pli][bi];
2090       frag_offs=frag_buf_offs[fragi];
2091       frag_satd[mapii]=oc_enc_frag_satd2(_enc,&dc,src+frag_offs,
2092        ref+frag_offs+mv_offs[0],ref+frag_offs+mv_offs[1],ystride);
2093       frag_satd[mapii]+=abs(dc);
2094     }
2095   }
2096   else{
2097     for(mapii=4;mapii<map_nidxs;mapii++){
2098       mapi=map_idxs[mapii];
2099       pli=mapi>>2;
2100       bi=mapi&3;
2101       fragi=mb_map[pli][bi];
2102       frag_offs=frag_buf_offs[fragi];
2103       frag_satd[mapii]=oc_enc_frag_satd(_enc,&dc,src+frag_offs,
2104        ref+frag_offs+mv_offs[0],ystride);
2105       frag_satd[mapii]+=abs(dc);
2106     }
2107   }
2108   oc_analyze_mb_mode_luma(_enc,_modec,_fr,_qs,frag_satd,_skip_ssd,_rd_scale,1);
2109   oc_analyze_mb_mode_chroma(_enc,_modec,_fr,_qs,
2110    frag_satd,_skip_ssd,_rd_scale[4],1);
2111   _modec->overhead=
2112    oc_mode_scheme_chooser_cost(&_enc->chooser,_mb_mode)<<OC_BIT_SCALE;
2113   oc_mode_set_cost(_modec,_enc->lambda);
2114 }
2115
2116 static void oc_cost_inter_nomv(oc_enc_ctx *_enc,oc_mode_choice *_modec,
2117  unsigned _mbi,int _mb_mode,const oc_fr_state *_fr,const oc_qii_state *_qs,
2118  const unsigned _skip_ssd[12],const unsigned _rd_scale[4]){
2119   oc_cost_inter(_enc,_modec,_mbi,_mb_mode,0,_fr,_qs,_skip_ssd,_rd_scale);
2120 }
2121
2122 static int oc_cost_inter1mv(oc_enc_ctx *_enc,oc_mode_choice *_modec,
2123  unsigned _mbi,int _mb_mode,oc_mv _mv,
2124  const oc_fr_state *_fr,const oc_qii_state *_qs,const unsigned _skip_ssd[12],
2125  const unsigned _rd_scale[4]){
2126   int bits0;
2127   oc_cost_inter(_enc,_modec,_mbi,_mb_mode,_mv,_fr,_qs,_skip_ssd,_rd_scale);
2128   bits0=OC_MV_BITS[0][OC_MV_X(_mv)+31]+OC_MV_BITS[0][OC_MV_Y(_mv)+31];
2129   _modec->overhead+=OC_MINI(_enc->mv_bits[0]+bits0,_enc->mv_bits[1]+12)
2130    -OC_MINI(_enc->mv_bits[0],_enc->mv_bits[1])<<OC_BIT_SCALE;
2131   oc_mode_set_cost(_modec,_enc->lambda);
2132   return bits0;
2133 }
2134
2135 /*A mapping from oc_mb_map (raster) ordering to oc_sb_map (Hilbert) ordering.*/
2136 static const unsigned char OC_MB_PHASE[4][4]={
2137   {0,1,3,2},{0,3,1,2},{0,3,1,2},{2,3,1,0}
2138 };
2139
2140 static void oc_cost_inter4mv(oc_enc_ctx *_enc,oc_mode_choice *_modec,
2141  unsigned _mbi,oc_mv _mv[4],const oc_fr_state *_fr,const oc_qii_state *_qs,
2142  const unsigned _skip_ssd[12],const unsigned _rd_scale[5]){
2143   unsigned               frag_satd[12];
2144   oc_mv                  lbmvs[4];
2145   oc_mv                  cbmvs[4];
2146   const unsigned char   *src;
2147   const unsigned char   *ref;
2148   int                    ystride;
2149   const ptrdiff_t       *frag_buf_offs;
2150   oc_mv                 *frag_mvs;
2151   const oc_mb_map_plane *mb_map;
2152   const unsigned char   *map_idxs;
2153   int                    map_nidxs;
2154   int                    nqis;
2155   int                    mapii;
2156   int                    mapi;
2157   int                    mv_offs[2];
2158   int                    pli;
2159   int                    bi;
2160   ptrdiff_t              fragi;
2161   ptrdiff_t              frag_offs;
2162   int                    bits0;
2163   int                    bits1;
2164   unsigned               satd;
2165   int                    dc;
2166   src=_enc->state.ref_frame_data[OC_FRAME_IO];
2167   ref=_enc->state.ref_frame_data[OC_FRAME_PREV];
2168   ystride=_enc->state.ref_ystride[0];
2169   frag_buf_offs=_enc->state.frag_buf_offs;
2170   frag_mvs=_enc->state.frag_mvs;
2171   mb_map=(const oc_mb_map_plane *)_enc->state.mb_maps[_mbi];
2172   _modec->rate=_modec->ssd=0;
2173   for(bi=0;bi<4;bi++){
2174     fragi=mb_map[0][bi];
2175     /*Save the block MVs as the current ones while we're here; we'll replace
2176        them if we don't ultimately choose 4MV mode.*/
2177     frag_mvs[fragi]=_mv[bi];
2178     frag_offs=frag_buf_offs[fragi];
2179     if(oc_state_get_mv_offsets(&_enc->state,mv_offs,0,_mv[bi])>1){
2180       satd=oc_enc_frag_satd2(_enc,&dc,src+frag_offs,
2181        ref+frag_offs+mv_offs[0],ref+frag_offs+mv_offs[1],ystride);
2182     }
2183     else{
2184       satd=oc_enc_frag_satd(_enc,&dc,src+frag_offs,
2185        ref+frag_offs+mv_offs[0],ystride);
2186     }
2187     frag_satd[OC_MB_PHASE[_mbi&3][bi]]=satd+abs(dc);
2188   }
2189   oc_analyze_mb_mode_luma(_enc,_modec,_fr,_qs,frag_satd,
2190    _enc->vp3_compatible?OC_NOSKIP:_skip_ssd,_rd_scale,1);
2191   /*Figure out which blocks are being skipped and give them (0,0) MVs.*/
2192   bits0=0;
2193   bits1=0;
2194   nqis=_enc->state.nqis;
2195   for(bi=0;bi<4;bi++){
2196     if(_modec->qii[OC_MB_PHASE[_mbi&3][bi]]>=nqis)lbmvs[bi]=0;
2197     else{
2198       lbmvs[bi]=_mv[bi];
2199       bits0+=OC_MV_BITS[0][OC_MV_X(_mv[bi])+31]
2200        +OC_MV_BITS[0][OC_MV_Y(_mv[bi])+31];
2201       bits1+=12;
2202     }
2203   }
2204   (*OC_SET_CHROMA_MVS_TABLE[_enc->state.info.pixel_fmt])(cbmvs,lbmvs);
2205   map_idxs=OC_MB_MAP_IDXS[_enc->state.info.pixel_fmt];
2206   map_nidxs=OC_MB_MAP_NIDXS[_enc->state.info.pixel_fmt];
2207   /*Note: This assumes ref_ystride[1]==ref_ystride[2].*/
2208   ystride=_enc->state.ref_ystride[1];
2209   for(mapii=4;mapii<map_nidxs;mapii++){
2210     mapi=map_idxs[mapii];
2211     pli=mapi>>2;
2212     bi=mapi&3;
2213     fragi=mb_map[pli][bi];
2214     frag_offs=frag_buf_offs[fragi];
2215     /*TODO: We could save half these calls by re-using the results for the Cb
2216        and Cr planes; is it worth it?*/
2217     if(oc_state_get_mv_offsets(&_enc->state,mv_offs,pli,cbmvs[bi])>1){
2218       satd=oc_enc_frag_satd2(_enc,&dc,src+frag_offs,
2219        ref+frag_offs+mv_offs[0],ref+frag_offs+mv_offs[1],ystride);
2220     }
2221     else{
2222       satd=oc_enc_frag_satd(_enc,&dc,src+frag_offs,
2223        ref+frag_offs+mv_offs[0],ystride);
2224     }
2225     frag_satd[mapii]=satd+abs(dc);
2226   }
2227   oc_analyze_mb_mode_chroma(_enc,_modec,_fr,_qs,
2228    frag_satd,_skip_ssd,_rd_scale[4],1);
2229   _modec->overhead=
2230    oc_mode_scheme_chooser_cost(&_enc->chooser,OC_MODE_INTER_MV_FOUR)
2231    +OC_MINI(_enc->mv_bits[0]+bits0,_enc->mv_bits[1]+bits1)
2232    -OC_MINI(_enc->mv_bits[0],_enc->mv_bits[1])<<OC_BIT_SCALE;
2233   oc_mode_set_cost(_modec,_enc->lambda);
2234 }
2235
2236 int oc_enc_analyze_inter(oc_enc_ctx *_enc,int _allow_keyframe,int _recode){
2237   oc_set_chroma_mvs_func  set_chroma_mvs;
2238   oc_qii_state            intra_luma_qs;
2239   oc_mv                   last_mv;
2240   oc_mv                   prior_mv;
2241   ogg_int64_t             interbits;
2242   ogg_int64_t             intrabits;
2243   ogg_int64_t             activity_sum;
2244   ogg_int64_t             luma_sum;
2245   unsigned                activity_avg;
2246   unsigned                luma_avg;
2247   const ogg_uint16_t     *chroma_rd_scale;
2248   ogg_uint16_t           *mcu_rd_scale;
2249   ogg_uint16_t           *mcu_rd_iscale;
2250   const unsigned char    *map_idxs;
2251   int                     nmap_idxs;
2252   unsigned               *coded_mbis;
2253   unsigned               *uncoded_mbis;
2254   size_t                  ncoded_mbis;
2255   size_t                  nuncoded_mbis;
2256   oc_sb_flags            *sb_flags;
2257   signed char            *mb_modes;
2258   const oc_sb_map        *sb_maps;
2259   const oc_mb_map        *mb_maps;
2260   oc_mb_enc_info         *embs;
2261   oc_fragment            *frags;
2262   oc_mv                  *frag_mvs;
2263   unsigned                stripe_sby;
2264   unsigned                mcu_nvsbs;
2265   int                     notstart;
2266   int                     notdone;
2267   unsigned                sbi;
2268   unsigned                sbi_end;
2269   int                     refi;
2270   int                     pli;
2271   int                     sp_level;
2272   sp_level=_enc->sp_level;
2273   set_chroma_mvs=OC_SET_CHROMA_MVS_TABLE[_enc->state.info.pixel_fmt];
2274   _enc->state.frame_type=OC_INTER_FRAME;
2275   oc_mode_scheme_chooser_reset(&_enc->chooser);
2276   oc_enc_tokenize_start(_enc);
2277   oc_enc_pipeline_init(_enc,&_enc->pipe);
2278   oc_enc_mode_rd_init(_enc);
2279   if(_allow_keyframe)oc_qii_state_init(&intra_luma_qs);
2280   _enc->mv_bits[0]=_enc->mv_bits[1]=0;
2281   interbits=intrabits=0;
2282   activity_sum=luma_sum=0;
2283   activity_avg=_enc->activity_avg;
2284   luma_avg=OC_CLAMPI(90<<8,_enc->luma_avg,160<<8);
2285   chroma_rd_scale=_enc->chroma_rd_scale[OC_INTER_FRAME][_enc->state.qis[0]];
2286   mcu_rd_scale=_enc->mcu_rd_scale;
2287   mcu_rd_iscale=_enc->mcu_rd_iscale;
2288   last_mv=prior_mv=0;
2289   /*Choose MVs and MB modes and quantize and code luma.
2290     Must be done in Hilbert order.*/
2291   map_idxs=OC_MB_MAP_IDXS[_enc->state.info.pixel_fmt];
2292   nmap_idxs=OC_MB_MAP_NIDXS[_enc->state.info.pixel_fmt];
2293   coded_mbis=_enc->coded_mbis;
2294   uncoded_mbis=coded_mbis+_enc->state.nmbs;
2295   ncoded_mbis=0;
2296   nuncoded_mbis=0;
2297   _enc->state.ncoded_fragis[0]=0;
2298   _enc->state.ncoded_fragis[1]=0;
2299   _enc->state.ncoded_fragis[2]=0;
2300   sb_flags=_enc->state.sb_flags;
2301   mb_modes=_enc->state.mb_modes;
2302   sb_maps=(const oc_sb_map *)_enc->state.sb_maps;
2303   mb_maps=(const oc_mb_map *)_enc->state.mb_maps;
2304   embs=_enc->mb_info;
2305   frags=_enc->state.frags;
2306   frag_mvs=_enc->state.frag_mvs;
2307   notstart=0;
2308   notdone=1;
2309   mcu_nvsbs=_enc->mcu_nvsbs;
2310   for(stripe_sby=0;notdone;stripe_sby+=mcu_nvsbs){
2311     ptrdiff_t cfroffset;
2312     notdone=oc_enc_pipeline_set_stripe(_enc,&_enc->pipe,stripe_sby);
2313     sbi_end=_enc->pipe.sbi_end[0];
2314     cfroffset=_enc->pipe.froffset[1];
2315     for(sbi=_enc->pipe.sbi0[0];sbi<sbi_end;sbi++){
2316       int quadi;
2317       /*Mode addressing is through Y plane, always 4 MB per SB.*/
2318       for(quadi=0;quadi<4;quadi++)if(sb_flags[sbi].quad_valid&1<<quadi){
2319         oc_mode_choice modes[8];
2320         unsigned       activity[4];
2321         unsigned       rd_scale[5];
2322         unsigned       rd_iscale[5];
2323         unsigned       skip_ssd[12];
2324         unsigned       intra_satd[12];
2325         unsigned       luma;
2326         int            mb_mv_bits_0;
2327         int            mb_gmv_bits_0;
2328         int            inter_mv_pref;
2329         int            mb_mode;
2330         int            refi;
2331         int            mv;
2332         unsigned       mbi;
2333         int            mapii;
2334         int            mapi;
2335         int            bi;
2336         ptrdiff_t      fragi;
2337         mbi=sbi<<2|quadi;
2338         luma=oc_mb_intra_satd(_enc,mbi,intra_satd);
2339         /*Activity masking.*/
2340         if(sp_level<OC_SP_LEVEL_FAST_ANALYSIS){
2341           oc_mb_activity(_enc,mbi,activity);
2342         }
2343         else oc_mb_activity_fast(_enc,mbi,activity,intra_satd);
2344         luma_sum+=luma;
2345         activity_sum+=oc_mb_masking(rd_scale,rd_iscale,
2346          chroma_rd_scale,activity,activity_avg,luma,luma_avg);
2347         /*Motion estimation:
2348           We always do a basic 1MV search for all macroblocks, coded or not,
2349            keyframe or not.*/
2350         if(!_recode&&sp_level<OC_SP_LEVEL_NOMC)oc_mcenc_search(_enc,mbi);
2351         mv=0;
2352         /*Find the block choice with the lowest estimated coding cost.
2353           If a Cb or Cr block is coded but no Y' block from a macro block then
2354            the mode MUST be OC_MODE_INTER_NOMV.
2355           This is the default state to which the mode data structure is
2356            initialised in encoder and decoder at the start of each frame.*/
2357         /*Block coding cost is estimated from correlated SATD metrics.*/
2358         /*At this point, all blocks that are in frame are still marked coded.*/
2359         if(!_recode){
2360           embs[mbi].unref_mv[OC_FRAME_GOLD]=
2361            embs[mbi].analysis_mv[0][OC_FRAME_GOLD];
2362           embs[mbi].unref_mv[OC_FRAME_PREV]=
2363            embs[mbi].analysis_mv[0][OC_FRAME_PREV];
2364           embs[mbi].refined=0;
2365         }
2366         /*Estimate the cost of coding this MB in a keyframe.*/
2367         if(_allow_keyframe){
2368           oc_cost_intra(_enc,modes+OC_MODE_INTRA,mbi,
2369            _enc->pipe.fr+0,&intra_luma_qs,intra_satd,OC_NOSKIP,rd_scale);
2370           intrabits+=modes[OC_MODE_INTRA].rate;
2371           for(bi=0;bi<4;bi++){
2372             oc_qii_state_advance(&intra_luma_qs,&intra_luma_qs,
2373              modes[OC_MODE_INTRA].qii[bi]);
2374           }
2375         }
2376         /*Estimate the cost in a delta frame for various modes.*/
2377         oc_skip_cost(_enc,&_enc->pipe,mbi,rd_scale,skip_ssd);
2378         if(sp_level<OC_SP_LEVEL_NOMC){
2379           oc_cost_inter_nomv(_enc,modes+OC_MODE_INTER_NOMV,mbi,
2380            OC_MODE_INTER_NOMV,_enc->pipe.fr+0,_enc->pipe.qs+0,
2381            skip_ssd,rd_scale);
2382           oc_cost_intra(_enc,modes+OC_MODE_INTRA,mbi,
2383            _enc->pipe.fr+0,_enc->pipe.qs+0,intra_satd,skip_ssd,rd_scale);
2384           mb_mv_bits_0=oc_cost_inter1mv(_enc,modes+OC_MODE_INTER_MV,mbi,
2385            OC_MODE_INTER_MV,embs[mbi].unref_mv[OC_FRAME_PREV],
2386            _enc->pipe.fr+0,_enc->pipe.qs+0,skip_ssd,rd_scale);
2387           oc_cost_inter(_enc,modes+OC_MODE_INTER_MV_LAST,mbi,
2388            OC_MODE_INTER_MV_LAST,last_mv,_enc->pipe.fr+0,_enc->pipe.qs+0,
2389            skip_ssd,rd_scale);
2390           oc_cost_inter(_enc,modes+OC_MODE_INTER_MV_LAST2,mbi,
2391            OC_MODE_INTER_MV_LAST2,prior_mv,_enc->pipe.fr+0,_enc->pipe.qs+0,
2392            skip_ssd,rd_scale);
2393           oc_cost_inter_nomv(_enc,modes+OC_MODE_GOLDEN_NOMV,mbi,
2394            OC_MODE_GOLDEN_NOMV,_enc->pipe.fr+0,_enc->pipe.qs+0,
2395            skip_ssd,rd_scale);
2396           mb_gmv_bits_0=oc_cost_inter1mv(_enc,modes+OC_MODE_GOLDEN_MV,mbi,
2397            OC_MODE_GOLDEN_MV,embs[mbi].unref_mv[OC_FRAME_GOLD],
2398            _enc->pipe.fr+0,_enc->pipe.qs+0,skip_ssd,rd_scale);
2399           /*The explicit MV modes (2,6,7) have not yet gone through halfpel
2400              refinement.
2401             We choose the explicit MV mode that's already furthest ahead on
2402              R-D cost and refine only that one.
2403             We have to be careful to remember which ones we've refined so that
2404              we don't refine it again if we re-encode this frame.*/
2405           inter_mv_pref=_enc->lambda*3;
2406           if(sp_level<OC_SP_LEVEL_FAST_ANALYSIS){
2407             oc_cost_inter4mv(_enc,modes+OC_MODE_INTER_MV_FOUR,mbi,
2408              embs[mbi].block_mv,_enc->pipe.fr+0,_enc->pipe.qs+0,
2409              skip_ssd,rd_scale);
2410           }
2411           else{
2412             modes[OC_MODE_INTER_MV_FOUR].cost=UINT_MAX;
2413           }
2414           if(modes[OC_MODE_INTER_MV_FOUR].cost<modes[OC_MODE_INTER_MV].cost&&
2415            modes[OC_MODE_INTER_MV_FOUR].cost<modes[OC_MODE_GOLDEN_MV].cost){
2416             if(!(embs[mbi].refined&0x80)){
2417               oc_mcenc_refine4mv(_enc,mbi);
2418               embs[mbi].refined|=0x80;
2419             }
2420             oc_cost_inter4mv(_enc,modes+OC_MODE_INTER_MV_FOUR,mbi,
2421              embs[mbi].ref_mv,_enc->pipe.fr+0,_enc->pipe.qs+0,
2422              skip_ssd,rd_scale);
2423           }
2424           else if(modes[OC_MODE_GOLDEN_MV].cost+inter_mv_pref<
2425            modes[OC_MODE_INTER_MV].cost){
2426             if(!(embs[mbi].refined&0x40)){
2427               oc_mcenc_refine1mv(_enc,mbi,OC_FRAME_GOLD);
2428               embs[mbi].refined|=0x40;
2429             }
2430             mb_gmv_bits_0=oc_cost_inter1mv(_enc,modes+OC_MODE_GOLDEN_MV,mbi,
2431              OC_MODE_GOLDEN_MV,embs[mbi].analysis_mv[0][OC_FRAME_GOLD],
2432              _enc->pipe.fr+0,_enc->pipe.qs+0,skip_ssd,rd_scale);
2433           }
2434           if(!(embs[mbi].refined&0x04)){
2435             oc_mcenc_refine1mv(_enc,mbi,OC_FRAME_PREV);
2436             embs[mbi].refined|=0x04;
2437           }
2438           mb_mv_bits_0=oc_cost_inter1mv(_enc,modes+OC_MODE_INTER_MV,mbi,
2439            OC_MODE_INTER_MV,embs[mbi].analysis_mv[0][OC_FRAME_PREV],
2440            _enc->pipe.fr+0,_enc->pipe.qs+0,skip_ssd,rd_scale);
2441           /*Finally, pick the mode with the cheapest estimated R-D cost.*/
2442           mb_mode=OC_MODE_INTER_NOMV;
2443           if(modes[OC_MODE_INTRA].cost<modes[OC_MODE_INTER_NOMV].cost){
2444             mb_mode=OC_MODE_INTRA;
2445           }
2446           if(modes[OC_MODE_INTER_MV_LAST].cost<modes[mb_mode].cost){
2447             mb_mode=OC_MODE_INTER_MV_LAST;
2448           }
2449           if(modes[OC_MODE_INTER_MV_LAST2].cost<modes[mb_mode].cost){
2450             mb_mode=OC_MODE_INTER_MV_LAST2;
2451           }
2452           if(modes[OC_MODE_GOLDEN_NOMV].cost<modes[mb_mode].cost){
2453             mb_mode=OC_MODE_GOLDEN_NOMV;
2454           }
2455           if(modes[OC_MODE_GOLDEN_MV].cost<modes[mb_mode].cost){
2456             mb_mode=OC_MODE_GOLDEN_MV;
2457           }
2458           if(modes[OC_MODE_INTER_MV_FOUR].cost<modes[mb_mode].cost){
2459             mb_mode=OC_MODE_INTER_MV_FOUR;
2460           }
2461           /*We prefer OC_MODE_INTER_MV, but not over LAST and LAST2.*/
2462           if(mb_mode==OC_MODE_INTER_MV_LAST||mb_mode==OC_MODE_INTER_MV_LAST2){
2463             inter_mv_pref=0;
2464           }
2465           if(modes[OC_MODE_INTER_MV].cost<modes[mb_mode].cost+inter_mv_pref){
2466             mb_mode=OC_MODE_INTER_MV;
2467           }
2468         }
2469         else{
2470           oc_cost_inter_nomv(_enc,modes+OC_MODE_INTER_NOMV,mbi,
2471            OC_MODE_INTER_NOMV,_enc->pipe.fr+0,_enc->pipe.qs+0,
2472            skip_ssd,rd_scale);
2473           oc_cost_intra(_enc,modes+OC_MODE_INTRA,mbi,
2474            _enc->pipe.fr+0,_enc->pipe.qs+0,intra_satd,skip_ssd,rd_scale);
2475           oc_cost_inter_nomv(_enc,modes+OC_MODE_GOLDEN_NOMV,mbi,
2476            OC_MODE_GOLDEN_NOMV,_enc->pipe.fr+0,_enc->pipe.qs+0,
2477            skip_ssd,rd_scale);
2478           mb_mode=OC_MODE_INTER_NOMV;
2479           if(modes[OC_MODE_INTRA].cost<modes[OC_MODE_INTER_NOMV].cost){
2480             mb_mode=OC_MODE_INTRA;
2481           }
2482           if(modes[OC_MODE_GOLDEN_NOMV].cost<modes[mb_mode].cost){
2483             mb_mode=OC_MODE_GOLDEN_NOMV;
2484           }
2485           mb_mv_bits_0=mb_gmv_bits_0=0;
2486         }
2487         mb_modes[mbi]=mb_mode;
2488         /*Propagate the MVs to the luma blocks.*/
2489         if(mb_mode!=OC_MODE_INTER_MV_FOUR){
2490           switch(mb_mode){
2491             case OC_MODE_INTER_MV:{
2492               mv=embs[mbi].analysis_mv[0][OC_FRAME_PREV];
2493             }break;
2494             case OC_MODE_INTER_MV_LAST:mv=last_mv;break;
2495             case OC_MODE_INTER_MV_LAST2:mv=prior_mv;break;
2496             case OC_MODE_GOLDEN_MV:{
2497               mv=embs[mbi].analysis_mv[0][OC_FRAME_GOLD];
2498             }break;
2499           }
2500           for(bi=0;bi<4;bi++){
2501             fragi=mb_maps[mbi][0][bi];
2502             frag_mvs[fragi]=mv;
2503           }
2504         }
2505         for(bi=0;bi<4;bi++){
2506           fragi=sb_maps[mbi>>2][mbi&3][bi];
2507           frags[fragi].qii=modes[mb_mode].qii[bi];
2508         }
2509         if(oc_enc_mb_transform_quantize_inter_luma(_enc,&_enc->pipe,mbi,
2510          modes[mb_mode].overhead>>OC_BIT_SCALE,rd_scale,rd_iscale)>0){
2511           int orig_mb_mode;
2512           orig_mb_mode=mb_mode;
2513           mb_mode=mb_modes[mbi];
2514           refi=OC_FRAME_FOR_MODE(mb_mode);
2515           switch(mb_mode){
2516             case OC_MODE_INTER_MV:{
2517               prior_mv=last_mv;
2518               /*If we're backing out from 4MV, find the MV we're actually
2519                  using.*/
2520               if(orig_mb_mode==OC_MODE_INTER_MV_FOUR){
2521                 for(bi=0;;bi++){
2522                   fragi=mb_maps[mbi][0][bi];
2523                   if(frags[fragi].coded){
2524                     mv=last_mv=frag_mvs[fragi];
2525                     break;
2526                   }
2527                 }
2528                 mb_mv_bits_0=OC_MV_BITS[0][OC_MV_X(mv)+31]
2529                  +OC_MV_BITS[0][OC_MV_Y(mv)+31];
2530               }
2531               /*Otherwise we used the original analysis MV.*/
2532               else last_mv=embs[mbi].analysis_mv[0][OC_FRAME_PREV];
2533               _enc->mv_bits[0]+=mb_mv_bits_0;
2534               _enc->mv_bits[1]+=12;
2535             }break;
2536             case OC_MODE_INTER_MV_LAST2:{
2537               oc_mv tmp_mv;
2538               tmp_mv=prior_mv;
2539               prior_mv=last_mv;
2540               last_mv=tmp_mv;
2541             }break;
2542             case OC_MODE_GOLDEN_MV:{
2543               _enc->mv_bits[0]+=mb_gmv_bits_0;
2544               _enc->mv_bits[1]+=12;
2545             }break;
2546             case OC_MODE_INTER_MV_FOUR:{
2547               oc_mv lbmvs[4];
2548               oc_mv cbmvs[4];
2549               prior_mv=last_mv;
2550               for(bi=0;bi<4;bi++){
2551                 fragi=mb_maps[mbi][0][bi];
2552                 if(frags[fragi].coded){
2553                   lbmvs[bi]=last_mv=frag_mvs[fragi];
2554                   _enc->mv_bits[0]+=OC_MV_BITS[0][OC_MV_X(last_mv)+31]
2555                    +OC_MV_BITS[0][OC_MV_Y(last_mv)+31];
2556                   _enc->mv_bits[1]+=12;
2557                 }
2558                 /*Replace the block MVs for not-coded blocks with (0,0).*/
2559                 else lbmvs[bi]=0;
2560               }
2561               (*set_chroma_mvs)(cbmvs,lbmvs);
2562               for(mapii=4;mapii<nmap_idxs;mapii++){
2563                 mapi=map_idxs[mapii];
2564                 pli=mapi>>2;
2565                 bi=mapi&3;
2566                 fragi=mb_maps[mbi][pli][bi];
2567                 frags[fragi].qii=modes[OC_MODE_INTER_MV_FOUR].qii[mapii];
2568                 frags[fragi].refi=refi;
2569                 frags[fragi].mb_mode=mb_mode;
2570                 frag_mvs[fragi]=cbmvs[bi];
2571               }
2572             }break;
2573           }
2574           coded_mbis[ncoded_mbis++]=mbi;
2575           oc_mode_scheme_chooser_update(&_enc->chooser,mb_mode);
2576           interbits+=modes[mb_mode].rate+modes[mb_mode].overhead;
2577         }
2578         else{
2579           *(uncoded_mbis-++nuncoded_mbis)=mbi;
2580           mb_mode=OC_MODE_INTER_NOMV;
2581           refi=OC_FRAME_PREV;
2582           mv=0;
2583         }
2584         /*Propagate final MB mode and MVs to the chroma blocks.
2585           This has already been done for 4MV mode, since it requires individual
2586            block motion vectors.*/
2587         if(mb_mode!=OC_MODE_INTER_MV_FOUR){
2588           for(mapii=4;mapii<nmap_idxs;mapii++){
2589             mapi=map_idxs[mapii];
2590             pli=mapi>>2;
2591             bi=mapi&3;
2592             fragi=mb_maps[mbi][pli][bi];
2593             /*If we switched from 4MV mode to INTER_MV mode, then the qii
2594                values won't have been chosen with the right MV, but it's
2595                probaby not worth re-estimating them.*/
2596             frags[fragi].qii=modes[mb_mode].qii[mapii];
2597             frags[fragi].refi=refi;
2598             frags[fragi].mb_mode=mb_mode;
2599             frag_mvs[fragi]=mv;
2600           }
2601         }
2602         /*Save masking scale factors for chroma blocks.*/
2603         for(mapii=4;mapii<(nmap_idxs-4>>1)+4;mapii++){
2604           mapi=map_idxs[mapii];
2605           bi=mapi&3;
2606           fragi=mb_maps[mbi][1][bi];
2607           mcu_rd_scale[fragi-cfroffset]=(ogg_uint16_t)rd_scale[4];
2608           mcu_rd_iscale[fragi-cfroffset]=(ogg_uint16_t)rd_iscale[4];
2609         }
2610       }
2611       oc_fr_state_flush_sb(_enc->pipe.fr+0);
2612       sb_flags[sbi].coded_fully=_enc->pipe.fr[0].sb_full;
2613       sb_flags[sbi].coded_partially=_enc->pipe.fr[0].sb_partial;
2614     }
2615     oc_enc_pipeline_finish_mcu_plane(_enc,&_enc->pipe,0,notstart,notdone);
2616     /*Code chroma planes.*/
2617     for(pli=1;pli<3;pli++){
2618       oc_enc_sb_transform_quantize_inter_chroma(_enc,&_enc->pipe,
2619        pli,_enc->pipe.sbi0[pli],_enc->pipe.sbi_end[pli]);
2620       oc_enc_pipeline_finish_mcu_plane(_enc,&_enc->pipe,pli,notstart,notdone);
2621     }
2622     notstart=1;
2623   }
2624   /*Update the average block activity and MB luma score for the frame.
2625     We could use a Bessel follower here, but fast reaction is probably almost
2626      always best.*/
2627   _enc->activity_avg=OC_MAXI(OC_ACTIVITY_AVG_MIN,
2628    (unsigned)((activity_sum+(_enc->state.fplanes[0].nfrags>>1))/
2629    _enc->state.fplanes[0].nfrags));
2630   _enc->luma_avg=(unsigned)((luma_sum+(_enc->state.nmbs>>1))/_enc->state.nmbs);
2631   /*Finish filling in the reference frame borders.*/
2632   refi=_enc->state.ref_frame_idx[OC_FRAME_SELF];
2633   for(pli=0;pli<3;pli++)oc_state_borders_fill_caps(&_enc->state,refi,pli);
2634   /*Finish adding flagging overhead costs to inter bit counts to determine if
2635      we should have coded a key frame instead.*/
2636   if(_allow_keyframe){
2637     /*Technically the chroma plane counts are over-estimations, because they
2638        don't account for continuing runs from the luma planes, but the
2639        inaccuracy is small.
2640       We don't need to add the luma plane coding flag costs, because they are
2641        already included in the MB rate estimates.*/
2642     for(pli=1;pli<3;pli++)interbits+=_enc->pipe.fr[pli].bits<<OC_BIT_SCALE;
2643     if(interbits>intrabits)return 1;
2644   }
2645   _enc->ncoded_mbis=ncoded_mbis;
2646   /*Compact the coded fragment list.*/
2647   {
2648     ptrdiff_t ncoded_fragis;
2649     ncoded_fragis=_enc->state.ncoded_fragis[0];
2650     for(pli=1;pli<3;pli++){
2651       memmove(_enc->state.coded_fragis+ncoded_fragis,
2652        _enc->state.coded_fragis+_enc->state.fplanes[pli].froffset,
2653        _enc->state.ncoded_fragis[pli]*sizeof(*_enc->state.coded_fragis));
2654       ncoded_fragis+=_enc->state.ncoded_fragis[pli];
2655     }
2656     _enc->state.ntotal_coded_fragis=ncoded_fragis;
2657   }
2658   return 0;
2659 }