Ensure frame rows are 16-byte aligned.
[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 }
576
577 /*Sets the current MCU stripe to super block row _sby.
578   Return: A non-zero value if this was the last MCU.*/
579 static int oc_enc_pipeline_set_stripe(oc_enc_ctx *_enc,
580  oc_enc_pipeline_state *_pipe,int _sby){
581   const oc_fragment_plane *fplane;
582   unsigned                 mcu_nvsbs;
583   int                      sby_end;
584   int                      notdone;
585   int                      vdec;
586   int                      pli;
587   mcu_nvsbs=_enc->mcu_nvsbs;
588   sby_end=_enc->state.fplanes[0].nvsbs;
589   notdone=_sby+mcu_nvsbs<sby_end;
590   if(notdone)sby_end=_sby+mcu_nvsbs;
591   vdec=0;
592   for(pli=0;pli<3;pli++){
593     fplane=_enc->state.fplanes+pli;
594     _pipe->sbi0[pli]=fplane->sboffset+(_sby>>vdec)*fplane->nhsbs;
595     _pipe->fragy0[pli]=_sby<<2-vdec;
596     _pipe->froffset[pli]=fplane->froffset
597      +_pipe->fragy0[pli]*(ptrdiff_t)fplane->nhfrags;
598     if(notdone){
599       _pipe->sbi_end[pli]=fplane->sboffset+(sby_end>>vdec)*fplane->nhsbs;
600       _pipe->fragy_end[pli]=sby_end<<2-vdec;
601     }
602     else{
603       _pipe->sbi_end[pli]=fplane->sboffset+fplane->nsbs;
604       _pipe->fragy_end[pli]=fplane->nvfrags;
605     }
606     vdec=!(_enc->state.info.pixel_fmt&2);
607   }
608   return notdone;
609 }
610
611 static void oc_enc_pipeline_finish_mcu_plane(oc_enc_ctx *_enc,
612  oc_enc_pipeline_state *_pipe,int _pli,int _sdelay,int _edelay){
613   /*Copy over all the uncoded fragments from this plane and advance the uncoded
614      fragment list.*/
615   if(_pipe->nuncoded_fragis[_pli]>0){
616     _pipe->uncoded_fragis[_pli]-=_pipe->nuncoded_fragis[_pli];
617     oc_frag_copy_list(&_enc->state,
618      _enc->state.ref_frame_data[OC_FRAME_SELF],
619      _enc->state.ref_frame_data[OC_FRAME_PREV],
620      _enc->state.ref_ystride[_pli],_pipe->uncoded_fragis[_pli],
621      _pipe->nuncoded_fragis[_pli],_enc->state.frag_buf_offs);
622     _pipe->nuncoded_fragis[_pli]=0;
623   }
624   /*Perform DC prediction.*/
625   oc_enc_pred_dc_frag_rows(_enc,_pli,
626    _pipe->fragy0[_pli],_pipe->fragy_end[_pli]);
627   /*Finish DC tokenization.*/
628   oc_enc_tokenize_dc_frag_list(_enc,_pli,
629    _pipe->coded_fragis[_pli],_pipe->ncoded_fragis[_pli],
630    _pipe->ndct_tokens1[_pli],_pipe->eob_run1[_pli]);
631   _pipe->ndct_tokens1[_pli]=_enc->ndct_tokens[_pli][1];
632   _pipe->eob_run1[_pli]=_enc->eob_run[_pli][1];
633   /*And advance the coded fragment list.*/
634   _enc->state.ncoded_fragis[_pli]+=_pipe->ncoded_fragis[_pli];
635   _pipe->coded_fragis[_pli]+=_pipe->ncoded_fragis[_pli];
636   _pipe->ncoded_fragis[_pli]=0;
637   /*Apply the loop filter if necessary.*/
638   if(_pipe->loop_filter){
639     oc_state_loop_filter_frag_rows(&_enc->state,
640      _pipe->bounding_values,OC_FRAME_SELF,_pli,
641      _pipe->fragy0[_pli]-_sdelay,_pipe->fragy_end[_pli]-_edelay);
642   }
643   else _sdelay=_edelay=0;
644   /*To fill borders, we have an additional two pixel delay, since a fragment
645      in the next row could filter its top edge, using two pixels from a
646      fragment in this row.
647     But there's no reason to delay a full fragment between the two.*/
648   oc_state_borders_fill_rows(&_enc->state,
649    _enc->state.ref_frame_idx[OC_FRAME_SELF],_pli,
650    (_pipe->fragy0[_pli]-_sdelay<<3)-(_sdelay<<1),
651    (_pipe->fragy_end[_pli]-_edelay<<3)-(_edelay<<1));
652 }
653
654
655
656 /*Cost information about the coded blocks in a MB.*/
657 struct oc_rd_metric{
658   int uncoded_ac_ssd;
659   int coded_ac_ssd;
660   int ac_bits;
661   int dc_flag;
662 };
663
664
665
666 static int oc_enc_block_transform_quantize(oc_enc_ctx *_enc,
667  oc_enc_pipeline_state *_pipe,int _pli,ptrdiff_t _fragi,
668  unsigned _rd_scale,unsigned _rd_iscale,oc_rd_metric *_mo,
669  oc_fr_state *_fr,oc_token_checkpoint **_stack){
670   ogg_int16_t            *dct;
671   ogg_int16_t            *data;
672   oc_qii_state            qs;
673   const ogg_uint16_t     *dequant;
674   ogg_uint16_t            dequant_dc;
675   ptrdiff_t               frag_offs;
676   int                     ystride;
677   const unsigned char    *src;
678   const unsigned char    *ref;
679   unsigned char          *dst;
680   int                     nonzero;
681   unsigned                uncoded_ssd;
682   unsigned                coded_ssd;
683   oc_token_checkpoint    *checkpoint;
684   oc_fragment            *frags;
685   int                     mb_mode;
686   int                     refi;
687   int                     mv_offs[2];
688   int                     nmv_offs;
689   int                     ac_bits;
690   int                     borderi;
691   int                     nqis;
692   int                     qti;
693   int                     qii;
694   int                     dc;
695   nqis=_enc->state.nqis;
696   frags=_enc->state.frags;
697   frag_offs=_enc->state.frag_buf_offs[_fragi];
698   ystride=_enc->state.ref_ystride[_pli];
699   src=_enc->state.ref_frame_data[OC_FRAME_IO]+frag_offs;
700   borderi=frags[_fragi].borderi;
701   qii=frags[_fragi].qii;
702   data=_enc->pipe.dct_data;
703   dct=data+64;
704   if(qii&~3){
705 #if !defined(OC_COLLECT_METRICS)
706     if(_enc->sp_level>=OC_SP_LEVEL_EARLY_SKIP){
707       /*Enable early skip detection.*/
708       frags[_fragi].coded=0;
709       frags[_fragi].refi=OC_FRAME_NONE;
710       oc_fr_skip_block(_fr);
711       return 0;
712     }
713 #endif
714     /*Try and code this block anyway.*/
715     qii&=3;
716     frags[_fragi].qii=qii;
717   }
718   refi=frags[_fragi].refi;
719   mb_mode=frags[_fragi].mb_mode;
720   ref=_enc->state.ref_frame_data[refi]+frag_offs;
721   dst=_enc->state.ref_frame_data[OC_FRAME_SELF]+frag_offs;
722   /*Motion compensation:*/
723   switch(mb_mode){
724     case OC_MODE_INTRA:{
725       nmv_offs=0;
726       oc_enc_frag_sub_128(_enc,data,src,ystride);
727     }break;
728     case OC_MODE_GOLDEN_NOMV:
729     case OC_MODE_INTER_NOMV:{
730       nmv_offs=1;
731       mv_offs[0]=0;
732       oc_enc_frag_sub(_enc,data,src,ref,ystride);
733     }break;
734     default:{
735       const oc_mv *frag_mvs;
736       frag_mvs=_enc->state.frag_mvs;
737       nmv_offs=oc_state_get_mv_offsets(&_enc->state,mv_offs,
738        _pli,frag_mvs[_fragi]);
739       if(nmv_offs>1){
740         oc_enc_frag_copy2(_enc,dst,
741          ref+mv_offs[0],ref+mv_offs[1],ystride);
742         oc_enc_frag_sub(_enc,data,src,dst,ystride);
743       }
744       else oc_enc_frag_sub(_enc,data,src,ref+mv_offs[0],ystride);
745     }break;
746   }
747 #if defined(OC_COLLECT_METRICS)
748   {
749     unsigned satd;
750     unsigned dc;
751     switch(nmv_offs){
752       case 0:satd=oc_enc_frag_intra_satd(_enc,&dc,src,ystride);break;
753       case 1:{
754         satd=oc_enc_frag_satd(_enc,&dc,src,ref+mv_offs[0],ystride);
755         satd+=dc;
756       }break;
757       default:{
758         satd=oc_enc_frag_satd(_enc,&dc,src,dst,ystride);
759         satd+=dc;
760       }break;
761     }
762     _enc->frag_satd[_fragi]=satd;
763   }
764 #endif
765   /*Transform:*/
766   oc_enc_fdct8x8(_enc,dct,data);
767   /*Quantize:*/
768   qti=mb_mode!=OC_MODE_INTRA;
769   dequant=_enc->dequant[_pli][qii][qti];
770   nonzero=oc_enc_quantize(_enc,data,dct,dequant,_enc->enquant[_pli][qii][qti]);
771   dc=data[0];
772   /*Tokenize.*/
773   checkpoint=*_stack;
774   if(_enc->sp_level<OC_SP_LEVEL_FAST_ANALYSIS){
775     ac_bits=oc_enc_tokenize_ac(_enc,_pli,_fragi,data,dequant,dct,nonzero+1,
776      _stack,OC_RD_ISCALE(_enc->lambda,_rd_iscale),qti?0:3);
777   }
778   else{
779     ac_bits=oc_enc_tokenize_ac_fast(_enc,_pli,_fragi,data,dequant,dct,nonzero+1,
780      _stack,OC_RD_ISCALE(_enc->lambda,_rd_iscale),qti?0:3);
781   }
782   /*Reconstruct.
783     TODO: nonzero may need to be adjusted after tokenization.*/
784   dequant_dc=dequant[0];
785   if(nonzero==0){
786     ogg_int16_t p;
787     int         ci;
788     int         qi01;
789     int         qi12;
790     /*We round this dequant product (and not any of the others) because there's
791        no iDCT rounding.*/
792     p=(ogg_int16_t)(dc*(ogg_int32_t)dequant_dc+15>>5);
793     /*LOOP VECTORIZES.*/
794     for(ci=0;ci<64;ci++)data[ci]=p;
795     /*We didn't code any AC coefficients, so don't change the quantizer.*/
796     qi01=_pipe->qs[_pli].qi01;
797     qi12=_pipe->qs[_pli].qi12;
798     if(qi01>0)qii=1+qi12;
799     else if(qi01>=0)qii=0;
800   }
801   else{
802     data[0]=dc*dequant_dc;
803     oc_idct8x8(&_enc->state,data,data,nonzero+1);
804   }
805   if(nqis>1){
806     oc_qii_state_advance(&qs,_pipe->qs+_pli,qii);
807     ac_bits+=qs.bits-_pipe->qs[_pli].bits;
808   }
809   if(!qti)oc_enc_frag_recon_intra(_enc,dst,ystride,data);
810   else{
811     oc_enc_frag_recon_inter(_enc,dst,
812      nmv_offs==1?ref+mv_offs[0]:dst,ystride,data);
813   }
814   /*If _fr is NULL, then this is an INTRA frame, and we can't skip blocks.*/
815 #if !defined(OC_COLLECT_METRICS)
816   if(_fr!=NULL)
817 #endif
818   {
819     /*In retrospect, should we have skipped this block?*/
820     if(borderi<0){
821       coded_ssd=oc_enc_frag_ssd(_enc,src,dst,ystride);
822     }
823     else{
824       coded_ssd=oc_enc_frag_border_ssd(_enc,src,dst,ystride,
825        _enc->state.borders[borderi].mask);
826     }
827     /*Scale to match DCT domain.*/
828     coded_ssd<<=4;
829 #if defined(OC_COLLECT_METRICS)
830     _enc->frag_ssd[_fragi]=coded_ssd;
831   }
832   if(_fr!=NULL){
833 #endif
834     coded_ssd=OC_RD_SCALE(coded_ssd,_rd_scale);
835     uncoded_ssd=_pipe->skip_ssd[_pli][_fragi-_pipe->froffset[_pli]];
836     if(uncoded_ssd<UINT_MAX&&
837      /*Don't allow luma blocks to be skipped in 4MV mode when VP3 compatibility
838         is enabled.*/
839      (!_enc->vp3_compatible||mb_mode!=OC_MODE_INTER_MV_FOUR||_pli)){
840       int overhead_bits;
841       overhead_bits=oc_fr_cost1(_fr);
842       /*Although the fragment coding overhead determination is accurate, it is
843          greedy, using very coarse-grained local information.
844         Allowing it to mildly discourage coding turns out to be beneficial, but
845          it's not clear that allowing it to encourage coding through negative
846          coding overhead deltas is useful.
847         For that reason, we disallow negative coding overheads.*/
848       if(overhead_bits<0)overhead_bits=0;
849       if(uncoded_ssd<=coded_ssd+(overhead_bits+ac_bits)*_enc->lambda){
850         /*Hm, not worth it; roll back.*/
851         oc_enc_tokenlog_rollback(_enc,checkpoint,(*_stack)-checkpoint);
852         *_stack=checkpoint;
853         frags[_fragi].coded=0;
854         frags[_fragi].refi=OC_FRAME_NONE;
855         oc_fr_skip_block(_fr);
856         return 0;
857       }
858     }
859     else _mo->dc_flag=1;
860     _mo->uncoded_ac_ssd+=uncoded_ssd;
861     _mo->coded_ac_ssd+=coded_ssd;
862     _mo->ac_bits+=ac_bits;
863     oc_fr_code_block(_fr);
864   }
865   /*GCC 4.4.4 generates a warning here because it can't tell that
866      the init code in the nqis check above will run anytime this
867      line runs.*/
868   if(nqis>1)*(_pipe->qs+_pli)=*&qs;
869   frags[_fragi].dc=dc;
870   frags[_fragi].coded=1;
871   return 1;
872 }
873
874 static int oc_enc_mb_transform_quantize_inter_luma(oc_enc_ctx *_enc,
875  oc_enc_pipeline_state *_pipe,unsigned _mbi,int _mode_overhead,
876  const unsigned _rd_scale[4],const unsigned _rd_iscale[4]){
877   /*Worst case token stack usage for 4 fragments.*/
878   oc_token_checkpoint  stack[64*4];
879   oc_token_checkpoint *stackptr;
880   const oc_sb_map     *sb_maps;
881   signed char         *mb_modes;
882   oc_fragment         *frags;
883   ptrdiff_t           *coded_fragis;
884   ptrdiff_t            ncoded_fragis;
885   ptrdiff_t           *uncoded_fragis;
886   ptrdiff_t            nuncoded_fragis;
887   oc_rd_metric         mo;
888   oc_fr_state          fr_checkpoint;
889   oc_qii_state         qs_checkpoint;
890   int                  mb_mode;
891   int                  refi;
892   int                  ncoded;
893   ptrdiff_t            fragi;
894   int                  bi;
895   *&fr_checkpoint=*(_pipe->fr+0);
896   *&qs_checkpoint=*(_pipe->qs+0);
897   sb_maps=(const oc_sb_map *)_enc->state.sb_maps;
898   mb_modes=_enc->state.mb_modes;
899   frags=_enc->state.frags;
900   coded_fragis=_pipe->coded_fragis[0];
901   ncoded_fragis=_pipe->ncoded_fragis[0];
902   uncoded_fragis=_pipe->uncoded_fragis[0];
903   nuncoded_fragis=_pipe->nuncoded_fragis[0];
904   mb_mode=mb_modes[_mbi];
905   refi=OC_FRAME_FOR_MODE(mb_mode);
906   ncoded=0;
907   stackptr=stack;
908   memset(&mo,0,sizeof(mo));
909   for(bi=0;bi<4;bi++){
910     fragi=sb_maps[_mbi>>2][_mbi&3][bi];
911     frags[fragi].refi=refi;
912     frags[fragi].mb_mode=mb_mode;
913     if(oc_enc_block_transform_quantize(_enc,_pipe,0,fragi,
914      _rd_scale[bi],_rd_iscale[bi],&mo,_pipe->fr+0,&stackptr)){
915       coded_fragis[ncoded_fragis++]=fragi;
916       ncoded++;
917     }
918     else *(uncoded_fragis-++nuncoded_fragis)=fragi;
919   }
920   if(ncoded>0&&!mo.dc_flag){
921     int cost;
922     /*Some individual blocks were worth coding.
923       See if that's still true when accounting for mode and MV overhead.*/
924     cost=mo.coded_ac_ssd+_enc->lambda*(mo.ac_bits
925      +oc_fr_cost4(&fr_checkpoint,_pipe->fr+0)+_mode_overhead);
926     if(mo.uncoded_ac_ssd<=cost){
927       /*Taking macroblock overhead into account, it is not worth coding this
928          MB.*/
929       oc_enc_tokenlog_rollback(_enc,stack,stackptr-stack);
930       *(_pipe->fr+0)=*&fr_checkpoint;
931       *(_pipe->qs+0)=*&qs_checkpoint;
932       for(bi=0;bi<4;bi++){
933         fragi=sb_maps[_mbi>>2][_mbi&3][bi];
934         if(frags[fragi].coded){
935           *(uncoded_fragis-++nuncoded_fragis)=fragi;
936           frags[fragi].coded=0;
937           frags[fragi].refi=OC_FRAME_NONE;
938         }
939         oc_fr_skip_block(_pipe->fr+0);
940       }
941       ncoded_fragis-=ncoded;
942       ncoded=0;
943     }
944   }
945   /*If no luma blocks coded, the mode is forced.*/
946   if(ncoded==0)mb_modes[_mbi]=OC_MODE_INTER_NOMV;
947   /*Assume that a 1MV with a single coded block is always cheaper than a 4MV
948      with a single coded block.
949     This may not be strictly true: a 4MV computes chroma MVs using (0,0) for
950      skipped blocks, while a 1MV does not.*/
951   else if(ncoded==1&&mb_mode==OC_MODE_INTER_MV_FOUR){
952     mb_modes[_mbi]=OC_MODE_INTER_MV;
953   }
954   _pipe->ncoded_fragis[0]=ncoded_fragis;
955   _pipe->nuncoded_fragis[0]=nuncoded_fragis;
956   return ncoded;
957 }
958
959 static void oc_enc_sb_transform_quantize_inter_chroma(oc_enc_ctx *_enc,
960  oc_enc_pipeline_state *_pipe,int _pli,int _sbi_start,int _sbi_end){
961   const ogg_uint16_t *mcu_rd_scale;
962   const ogg_uint16_t *mcu_rd_iscale;
963   const oc_sb_map    *sb_maps;
964   oc_sb_flags        *sb_flags;
965   oc_fr_state        *fr;
966   ptrdiff_t          *coded_fragis;
967   ptrdiff_t           ncoded_fragis;
968   ptrdiff_t          *uncoded_fragis;
969   ptrdiff_t           nuncoded_fragis;
970   ptrdiff_t           froffset;
971   int                 sbi;
972   fr=_pipe->fr+_pli;
973   mcu_rd_scale=(const ogg_uint16_t *)_enc->mcu_rd_scale;
974   mcu_rd_iscale=(const ogg_uint16_t *)_enc->mcu_rd_iscale;
975   sb_maps=(const oc_sb_map *)_enc->state.sb_maps;
976   sb_flags=_enc->state.sb_flags;
977   coded_fragis=_pipe->coded_fragis[_pli];
978   ncoded_fragis=_pipe->ncoded_fragis[_pli];
979   uncoded_fragis=_pipe->uncoded_fragis[_pli];
980   nuncoded_fragis=_pipe->nuncoded_fragis[_pli];
981   froffset=_pipe->froffset[_pli];
982   for(sbi=_sbi_start;sbi<_sbi_end;sbi++){
983     /*Worst case token stack usage for 1 fragment.*/
984     oc_token_checkpoint stack[64];
985     oc_rd_metric        mo;
986     int                 quadi;
987     int                 bi;
988     memset(&mo,0,sizeof(mo));
989     for(quadi=0;quadi<4;quadi++)for(bi=0;bi<4;bi++){
990       ptrdiff_t fragi;
991       fragi=sb_maps[sbi][quadi][bi];
992       if(fragi>=0){
993         oc_token_checkpoint *stackptr;
994         unsigned             rd_scale;
995         unsigned             rd_iscale;
996         rd_scale=mcu_rd_scale[fragi-froffset];
997         rd_iscale=mcu_rd_iscale[fragi-froffset];
998         stackptr=stack;
999         if(oc_enc_block_transform_quantize(_enc,_pipe,_pli,fragi,
1000          rd_scale,rd_iscale,&mo,fr,&stackptr)){
1001           coded_fragis[ncoded_fragis++]=fragi;
1002         }
1003         else *(uncoded_fragis-++nuncoded_fragis)=fragi;
1004       }
1005     }
1006     oc_fr_state_flush_sb(fr);
1007     sb_flags[sbi].coded_fully=fr->sb_full;
1008     sb_flags[sbi].coded_partially=fr->sb_partial;
1009   }
1010   _pipe->ncoded_fragis[_pli]=ncoded_fragis;
1011   _pipe->nuncoded_fragis[_pli]=nuncoded_fragis;
1012 }
1013
1014 /*Mode decision is done by exhaustively examining all potential choices.
1015   Obviously, doing the motion compensation, fDCT, tokenization, and then
1016    counting the bits each token uses is computationally expensive.
1017   Theora's EOB runs can also split the cost of these tokens across multiple
1018    fragments, and naturally we don't know what the optimal choice of Huffman
1019    codes will be until we know all the tokens we're going to encode in all the
1020    fragments.
1021   So we use a simple approach to estimating the bit cost and distortion of each
1022    mode based upon the SATD value of the residual before coding.
1023   The mathematics behind the technique are outlined by Kim \cite{Kim03}, but
1024    the process (modified somewhat from that of the paper) is very simple.
1025   We build a non-linear regression of the mappings from
1026    (pre-transform+quantization) SATD to (post-transform+quantization) bits and
1027    SSD for each qi.
1028   A separate set of mappings is kept for each quantization type and color
1029    plane.
1030   The mappings are constructed by partitioning the SATD values into a small
1031    number of bins (currently 24) and using a linear regression in each bin
1032    (as opposed to the 0th-order regression used by Kim).
1033   The bit counts and SSD measurements are obtained by examining actual encoded
1034    frames, with appropriate lambda values and optimal Huffman codes selected.
1035   EOB bits are assigned to the fragment that started the EOB run (as opposed to
1036    dividing them among all the blocks in the run; the latter approach seems
1037    more theoretically correct, but Monty's testing showed a small improvement
1038    with the former, though that may have been merely statistical noise).
1039
1040   @ARTICLE{Kim03,
1041     author="Hyun Mun Kim",
1042     title="Adaptive Rate Control Using Nonlinear Regression",
1043     journal="IEEE Transactions on Circuits and Systems for Video Technology",
1044     volume=13,
1045     number=5,
1046     pages="432--439",
1047     month=May,
1048     year=2003
1049   }*/
1050
1051 /*Computes (_ssd+_lambda*_rate)/(1<<OC_BIT_SCALE) with rounding, avoiding
1052    overflow for large lambda values.*/
1053 #define OC_MODE_RD_COST(_ssd,_rate,_lambda) \
1054  ((_ssd)>>OC_BIT_SCALE)+((_rate)>>OC_BIT_SCALE)*(_lambda) \
1055  +(((_ssd)&(1<<OC_BIT_SCALE)-1)+((_rate)&(1<<OC_BIT_SCALE)-1)*(_lambda) \
1056  +((1<<OC_BIT_SCALE)>>1)>>OC_BIT_SCALE)
1057
1058 static void oc_enc_mode_rd_init(oc_enc_ctx *_enc){
1059   int qii;
1060 #if defined(OC_COLLECT_METRICS)
1061   oc_enc_mode_metrics_load(_enc);
1062 #endif
1063   for(qii=0;qii<_enc->state.nqis;qii++){
1064     int qi;
1065     int pli;
1066     qi=_enc->state.qis[qii];
1067     for(pli=0;pli<3;pli++){
1068       int qti;
1069       for(qti=0;qti<2;qti++){
1070         int log_plq;
1071         int modeline;
1072         int bin;
1073         int dx;
1074         int dq;
1075         log_plq=_enc->log_plq[qi][pli][qti];
1076         /*Find the pair of rows in the mode table that bracket this quantizer.
1077           If it falls outside the range the table covers, then we just use a
1078            pair on the edge for linear extrapolation.*/
1079         for(modeline=0;modeline<OC_LOGQ_BINS-1&&
1080          OC_MODE_LOGQ[modeline+1][pli][qti]>log_plq;modeline++);
1081         /*Interpolate a row for this quantizer.*/
1082         dx=OC_MODE_LOGQ[modeline][pli][qti]-log_plq;
1083         dq=OC_MODE_LOGQ[modeline][pli][qti]-OC_MODE_LOGQ[modeline+1][pli][qti];
1084         if(dq==0)dq=1;
1085         for(bin=0;bin<OC_SAD_BINS;bin++){
1086           int y0;
1087           int z0;
1088           int dy;
1089           int dz;
1090           y0=OC_MODE_RD[modeline][pli][qti][bin].rate;
1091           z0=OC_MODE_RD[modeline][pli][qti][bin].rmse;
1092           dy=OC_MODE_RD[modeline+1][pli][qti][bin].rate-y0;
1093           dz=OC_MODE_RD[modeline+1][pli][qti][bin].rmse-z0;
1094           _enc->mode_rd[qii][pli][qti][bin].rate=
1095            (ogg_int16_t)OC_CLAMPI(-32768,y0+(dy*dx+(dq>>1))/dq,32767);
1096           _enc->mode_rd[qii][pli][qti][bin].rmse=
1097            (ogg_int16_t)OC_CLAMPI(-32768,z0+(dz*dx+(dq>>1))/dq,32767);
1098         }
1099       }
1100     }
1101   }
1102 }
1103
1104 /*Estimate the R-D cost of the DCT coefficients given the SATD of a block after
1105    prediction.*/
1106 static unsigned oc_dct_cost2(oc_enc_ctx *_enc,unsigned *_ssd,
1107  int _qii,int _pli,int _qti,int _satd){
1108   unsigned rmse;
1109   int      bin;
1110   int      dx;
1111   int      y0;
1112   int      z0;
1113   int      dy;
1114   int      dz;
1115   /*SATD metrics for chroma planes vary much less than luma, so we scale them
1116      by 4 to distribute them into the mode decision bins more evenly.*/
1117   _satd<<=_pli+1&2;
1118   bin=OC_MINI(_satd>>OC_SAD_SHIFT,OC_SAD_BINS-2);
1119   dx=_satd-(bin<<OC_SAD_SHIFT);
1120   y0=_enc->mode_rd[_qii][_pli][_qti][bin].rate;
1121   z0=_enc->mode_rd[_qii][_pli][_qti][bin].rmse;
1122   dy=_enc->mode_rd[_qii][_pli][_qti][bin+1].rate-y0;
1123   dz=_enc->mode_rd[_qii][_pli][_qti][bin+1].rmse-z0;
1124   rmse=OC_MAXI(z0+(dz*dx>>OC_SAD_SHIFT),0);
1125   *_ssd=rmse*rmse>>2*OC_RMSE_SCALE-OC_BIT_SCALE;
1126   return OC_MAXI(y0+(dy*dx>>OC_SAD_SHIFT),0);
1127 }
1128
1129 /*activity_avg must be positive, or flat regions could get a zero weight, which
1130    confounds analysis.
1131   We set the minimum to this value so that it also avoids the need for divide
1132    by zero checks in oc_mb_masking().*/
1133 # define OC_ACTIVITY_AVG_MIN (1<<OC_RD_SCALE_BITS)
1134
1135 static unsigned oc_mb_activity(oc_enc_ctx *_enc,unsigned _mbi,
1136  unsigned _activity[4]){
1137   const unsigned char   *src;
1138   const ptrdiff_t       *frag_buf_offs;
1139   const ptrdiff_t       *sb_map;
1140   unsigned               luma;
1141   int                    ystride;
1142   ptrdiff_t              frag_offs;
1143   ptrdiff_t              fragi;
1144   int                    bi;
1145   frag_buf_offs=_enc->state.frag_buf_offs;
1146   sb_map=_enc->state.sb_maps[_mbi>>2][_mbi&3];
1147   src=_enc->state.ref_frame_data[OC_FRAME_IO];
1148   ystride=_enc->state.ref_ystride[0];
1149   luma=0;
1150   for(bi=0;bi<4;bi++){
1151     const unsigned char *s;
1152     unsigned             x;
1153     unsigned             x2;
1154     unsigned             act;
1155     int                  i;
1156     int                  j;
1157     fragi=sb_map[bi];
1158     frag_offs=frag_buf_offs[fragi];
1159     /*TODO: This could be replaced with SATD^2, since we already have to
1160        compute SATD.*/
1161     x=x2=0;
1162     s=src+frag_offs;
1163     for(i=0;i<8;i++){
1164       for(j=0;j<8;j++){
1165         unsigned c;
1166         c=s[j];
1167         x+=c;
1168         x2+=c*c;
1169       }
1170       s+=ystride;
1171     }
1172     luma+=x;
1173     act=(x2<<6)-x*x;
1174     if(act<8<<12){
1175       /*The region is flat.*/
1176       act=OC_MINI(act,5<<12);
1177     }
1178     else{
1179       unsigned e1;
1180       unsigned e2;
1181       unsigned e3;
1182       unsigned e4;
1183       /*Test for an edge.
1184         TODO: There are probably much simpler ways to do this (e.g., it could
1185          probably be combined with the SATD calculation).
1186         Alternatively, we could split the block around the mean and compute the
1187          reduction in variance in each half.
1188         For a Gaussian source the reduction should be
1189          (1-2/pi) ~= 0.36338022763241865692446494650994.
1190         Significantly more reduction is a good indication of a bi-level image.
1191         This has the advantage of identifying, in addition to straight edges,
1192          small text regions, which would otherwise be classified as "texture".*/
1193       e1=e2=e3=e4=0;
1194       s=src+frag_offs-1;
1195       for(i=0;i<8;i++){
1196         for(j=0;j<8;j++){
1197           e1+=abs((s[j+2]-s[j]<<1)+(s-ystride)[j+2]-(s-ystride)[j]
1198            +(s+ystride)[j+2]-(s+ystride)[j]);
1199           e2+=abs(((s+ystride)[j+1]-(s-ystride)[j+1]<<1)
1200            +(s+ystride)[j]-(s-ystride)[j]+(s+ystride)[j+2]-(s-ystride)[j+2]);
1201           e3+=abs(((s+ystride)[j+2]-(s-ystride)[j]<<1)
1202            +(s+ystride)[j+1]-s[j]+s[j+2]-(s-ystride)[j+1]);
1203           e4+=abs(((s+ystride)[j]-(s-ystride)[j+2]<<1)
1204            +(s+ystride)[j+1]-s[j+2]+s[j]-(s-ystride)[j+1]);
1205         }
1206         s+=ystride;
1207       }
1208       /*If the largest component of the edge energy is at least 40% of the
1209          total, then classify the block as an edge block.*/
1210       if(5*OC_MAXI(OC_MAXI(e1,e2),OC_MAXI(e3,e4))>2*(e1+e2+e3+e4)){
1211          /*act=act_th*(act/act_th)**0.7
1212               =exp(log(act_th)+0.7*(log(act)-log(act_th))).
1213            Here act_th=5.0 and 0x394A=oc_blog32_q10(5<<12).*/
1214          act=oc_bexp32_q10(0x394A+(7*(oc_blog32_q10(act)-0x394A+5)/10));
1215       }
1216     }
1217     _activity[bi]=act;
1218   }
1219   return luma;
1220 }
1221
1222 static unsigned oc_mb_activity_fast(oc_enc_ctx *_enc,unsigned _mbi,
1223  unsigned _activity[4], unsigned _intra_satd[12]){
1224   int bi;
1225   for(bi=0;bi<4;bi++){
1226     unsigned act;
1227     act=(11*_intra_satd[bi]>>8)*_intra_satd[bi];
1228     if(act<8<<12){
1229       /*The region is flat.*/
1230       act=OC_MINI(act,5<<12);
1231     }
1232     _activity[bi]=act;
1233   }
1234   /*TODO: Once frag_intra_satd returns the signed DC value instead
1235      of the absolute value, this should pass it through.*/
1236   return 1;
1237 }
1238
1239 /*Compute the masking scales for the blocks in a macro block.
1240   All masking is computed from the luma blocks.
1241   We derive scaling factors for the chroma blocks from these, and use the same
1242    ones for all chroma blocks, regardless of the subsampling.
1243   It's possible for luma to be perfectly flat and yet have high chroma energy,
1244    but this is unlikely in non-artificial images, and not a case that has been
1245    addressed by any research to my knowledge.
1246   The output of the masking process is two scale factors, which are fed into
1247    the various R-D optimizations.
1248   The first, rd_scale, is applied to D in the equation
1249     D*rd_scale+lambda*R.
1250   This is the form that must be used to properly combine scores from multiple
1251    blocks, and can be interpreted as scaling distortions by their visibility.
1252   The inverse, rd_iscale, is applied to lambda in the equation
1253     D+rd_iscale*lambda*R.
1254   This is equivalent to the first form within a single block, but much faster
1255    to use when evaluating many possible distortions (e.g., during actual
1256    quantization, where separate distortions are evaluated for every
1257    coefficient).
1258   The two macros OC_RD_SCALE(rd_scale,d) and OC_RD_ISCALE(rd_iscale,lambda) are
1259    used to perform the multiplications with the proper re-scaling for the range
1260    of the scaling factors.
1261   Many researchers apply masking values directly to the quantizers used, and
1262    not to the R-D cost.
1263   Since we generally use MSE for D, rd_scale must use the square of their
1264    values to generate an equivalent effect.*/
1265 static unsigned oc_mb_masking(unsigned _rd_scale[5],unsigned _rd_iscale[5],
1266  const ogg_uint16_t _chroma_rd_scale[2],const unsigned _activity[4],
1267  unsigned _activity_avg,unsigned _luma,unsigned _luma_avg){
1268   unsigned activity_sum;
1269   unsigned la;
1270   unsigned lb;
1271   unsigned d;
1272   int      bi;
1273   int      bi_min;
1274   int      bi_min2;
1275   /*The ratio lb/la is meant to approximate
1276      ((((_luma-16)/219)*(255/128))**0.649**0.4**2), which is the
1277      effective luminance masking from~\cite{LKW06} (including the self-masking
1278      deflator).
1279     The following actually turns out to be a pretty good approximation for
1280      _luma>75 or so.
1281     For smaller values luminance does not really follow Weber's Law anyway, and
1282      this approximation gives a much less aggressive bitrate boost in this
1283      region.
1284     Though some researchers claim that contrast sensitivity actually decreases
1285      for very low luminance values, in my experience excessive brightness on
1286      LCDs or buggy color conversions (e.g., treating Y' as full-range instead
1287      of the CCIR 601 range) make artifacts in such regions extremely visible.
1288     We substitute _luma_avg for 128 to allow the strength of the masking to
1289      vary with the actual average image luminance, within certain limits (the
1290      caller has clamped _luma_avg to the range [90,160], inclusive).
1291     @ARTICLE{LKW06,
1292       author="Zhen Liu and Lina J. Karam and Andrew B. Watson",
1293       title="{JPEG2000} Encoding With Perceptual Distortion Control",
1294       journal="{IEEE} Transactions on Image Processing",
1295       volume=15,
1296       number=7,
1297       pages="1763--1778",
1298       month=Jul,
1299       year=2006
1300     }*/
1301 #if 0
1302   la=_luma+4*_luma_avg;
1303   lb=4*_luma+_luma_avg;
1304 #else
1305   /*Disable luminance masking.*/
1306   la=lb=1;
1307 #endif
1308   activity_sum=0;
1309   for(bi=0;bi<4;bi++){
1310     unsigned a;
1311     unsigned b;
1312     activity_sum+=_activity[bi];
1313     /*Apply activity masking.*/
1314     a=_activity[bi]+4*_activity_avg;
1315     b=4*_activity[bi]+_activity_avg;
1316     d=OC_RD_SCALE(b,1);
1317     /*And luminance masking.*/
1318     d=(a+(d>>1))/d;
1319     _rd_scale[bi]=(d*la+(lb>>1))/lb;
1320     /*And now the inverse.*/
1321     d=OC_MAXI(OC_RD_ISCALE(a,1),1);
1322     d=(b+(d>>1))/d;
1323     _rd_iscale[bi]=(d*lb+(la>>1))/la;
1324   }
1325   /*Now compute scaling factors for chroma blocks.
1326     We start by finding the two smallest iscales from the luma blocks.*/
1327   bi_min=_rd_iscale[1]<_rd_iscale[0];
1328   bi_min2=1-bi_min;
1329   for(bi=2;bi<4;bi++){
1330     if(_rd_iscale[bi]<_rd_iscale[bi_min]){
1331       bi_min2=bi_min;
1332       bi_min=bi;
1333     }
1334     else if(_rd_iscale[bi]<_rd_iscale[bi_min2])bi_min2=bi;
1335   }
1336   /*If the minimum iscale is less than 1.0, use the second smallest instead,
1337      and force the value to at least 1.0 (inflating chroma is a waste).*/
1338   if(_rd_iscale[bi_min]<(1<<OC_RD_ISCALE_BITS))bi_min=bi_min2;
1339   d=OC_MINI(_rd_scale[bi_min],1<<OC_RD_SCALE_BITS);
1340   _rd_scale[4]=OC_RD_SCALE(d,_chroma_rd_scale[0]);
1341   d=OC_MAXI(_rd_iscale[bi_min],1<<OC_RD_ISCALE_BITS);
1342   _rd_iscale[4]=OC_RD_ISCALE(d,_chroma_rd_scale[1]);
1343   return activity_sum;
1344 }
1345
1346 static void oc_mb_intra_satd(oc_enc_ctx *_enc,unsigned _mbi,
1347  unsigned _frag_satd[12]){
1348   const unsigned char   *src;
1349   const ptrdiff_t       *frag_buf_offs;
1350   const ptrdiff_t       *sb_map;
1351   const oc_mb_map_plane *mb_map;
1352   const unsigned char   *map_idxs;
1353   int                    map_nidxs;
1354   int                    mapii;
1355   int                    mapi;
1356   int                    ystride;
1357   int                    pli;
1358   int                    bi;
1359   ptrdiff_t              fragi;
1360   ptrdiff_t              frag_offs;
1361   unsigned               dc;
1362   frag_buf_offs=_enc->state.frag_buf_offs;
1363   sb_map=_enc->state.sb_maps[_mbi>>2][_mbi&3];
1364   src=_enc->state.ref_frame_data[OC_FRAME_IO];
1365   ystride=_enc->state.ref_ystride[0];
1366   for(bi=0;bi<4;bi++){
1367     fragi=sb_map[bi];
1368     frag_offs=frag_buf_offs[fragi];
1369     _frag_satd[bi]=oc_enc_frag_intra_satd(_enc,&dc,src+frag_offs,ystride);
1370   }
1371   mb_map=(const oc_mb_map_plane *)_enc->state.mb_maps[_mbi];
1372   map_idxs=OC_MB_MAP_IDXS[_enc->state.info.pixel_fmt];
1373   map_nidxs=OC_MB_MAP_NIDXS[_enc->state.info.pixel_fmt];
1374   /*Note: This assumes ref_ystride[1]==ref_ystride[2].*/
1375   ystride=_enc->state.ref_ystride[1];
1376   for(mapii=4;mapii<map_nidxs;mapii++){
1377     mapi=map_idxs[mapii];
1378     pli=mapi>>2;
1379     bi=mapi&3;
1380     fragi=mb_map[pli][bi];
1381     frag_offs=frag_buf_offs[fragi];
1382     _frag_satd[mapii]=oc_enc_frag_intra_satd(_enc,&dc,src+frag_offs,ystride);
1383   }
1384 }
1385
1386 /*Select luma block-level quantizers for a MB in an INTRA frame.*/
1387 static unsigned oc_analyze_intra_mb_luma(oc_enc_ctx *_enc,
1388  const oc_qii_state *_qs,unsigned _mbi,const unsigned _rd_scale[4]){
1389   const unsigned char *src;
1390   const ptrdiff_t     *frag_buf_offs;
1391   const oc_sb_map     *sb_maps;
1392   oc_fragment         *frags;
1393   ptrdiff_t            frag_offs;
1394   ptrdiff_t            fragi;
1395   oc_qii_state         qs[4][3];
1396   unsigned             cost[4][3];
1397   unsigned             ssd[4][3];
1398   unsigned             rate[4][3];
1399   int                  prev[3][3];
1400   unsigned             satd;
1401   unsigned             dc;
1402   unsigned             best_cost;
1403   unsigned             best_ssd;
1404   unsigned             best_rate;
1405   int                  best_qii;
1406   int                  qii;
1407   int                  lambda;
1408   int                  ystride;
1409   int                  nqis;
1410   int                  bi;
1411   frag_buf_offs=_enc->state.frag_buf_offs;
1412   sb_maps=(const oc_sb_map *)_enc->state.sb_maps;
1413   src=_enc->state.ref_frame_data[OC_FRAME_IO];
1414   ystride=_enc->state.ref_ystride[0];
1415   fragi=sb_maps[_mbi>>2][_mbi&3][0];
1416   frag_offs=frag_buf_offs[fragi];
1417   satd=oc_enc_frag_intra_satd(_enc,&dc,src+frag_offs,ystride);
1418   nqis=_enc->state.nqis;
1419   lambda=_enc->lambda;
1420   for(qii=0;qii<nqis;qii++){
1421     oc_qii_state_advance(qs[0]+qii,_qs,qii);
1422     rate[0][qii]=oc_dct_cost2(_enc,ssd[0]+qii,qii,0,0,satd)
1423      +(qs[0][qii].bits-_qs->bits<<OC_BIT_SCALE);
1424     ssd[0][qii]=OC_RD_SCALE(ssd[0][qii],_rd_scale[0]);
1425     cost[0][qii]=OC_MODE_RD_COST(ssd[0][qii],rate[0][qii],lambda);
1426   }
1427   for(bi=1;bi<4;bi++){
1428     fragi=sb_maps[_mbi>>2][_mbi&3][bi];
1429     frag_offs=frag_buf_offs[fragi];
1430     satd=oc_enc_frag_intra_satd(_enc,&dc,src+frag_offs,ystride);
1431     for(qii=0;qii<nqis;qii++){
1432       oc_qii_state qt[3];
1433       unsigned     cur_ssd;
1434       unsigned     cur_rate;
1435       int          best_qij;
1436       int          qij;
1437       oc_qii_state_advance(qt+0,qs[bi-1]+0,qii);
1438       cur_rate=oc_dct_cost2(_enc,&cur_ssd,qii,0,0,satd);
1439       cur_ssd=OC_RD_SCALE(cur_ssd,_rd_scale[bi]);
1440       best_ssd=ssd[bi-1][0]+cur_ssd;
1441       best_rate=rate[bi-1][0]+cur_rate
1442        +(qt[0].bits-qs[bi-1][0].bits<<OC_BIT_SCALE);
1443       best_cost=OC_MODE_RD_COST(best_ssd,best_rate,lambda);
1444       best_qij=0;
1445       for(qij=1;qij<nqis;qij++){
1446         unsigned chain_ssd;
1447         unsigned chain_rate;
1448         unsigned chain_cost;
1449         oc_qii_state_advance(qt+qij,qs[bi-1]+qij,qii);
1450         chain_ssd=ssd[bi-1][qij]+cur_ssd;
1451         chain_rate=rate[bi-1][qij]+cur_rate
1452          +(qt[qij].bits-qs[bi-1][qij].bits<<OC_BIT_SCALE);
1453         chain_cost=OC_MODE_RD_COST(chain_ssd,chain_rate,lambda);
1454         if(chain_cost<best_cost){
1455           best_cost=chain_cost;
1456           best_ssd=chain_ssd;
1457           best_rate=chain_rate;
1458           best_qij=qij;
1459         }
1460       }
1461       *(qs[bi]+qii)=*(qt+best_qij);
1462       cost[bi][qii]=best_cost;
1463       ssd[bi][qii]=best_ssd;
1464       rate[bi][qii]=best_rate;
1465       prev[bi-1][qii]=best_qij;
1466     }
1467   }
1468   best_qii=0;
1469   best_cost=cost[3][0];
1470   for(qii=1;qii<nqis;qii++){
1471     if(cost[3][qii]<best_cost){
1472       best_cost=cost[3][qii];
1473       best_qii=qii;
1474     }
1475   }
1476   frags=_enc->state.frags;
1477   for(bi=3;;){
1478     fragi=sb_maps[_mbi>>2][_mbi&3][bi];
1479     frags[fragi].qii=best_qii;
1480     if(bi--<=0)break;
1481     best_qii=prev[bi][best_qii];
1482   }
1483   return best_cost;
1484 }
1485
1486 /*Select a block-level quantizer for a single chroma block in an INTRA frame.*/
1487 static unsigned oc_analyze_intra_chroma_block(oc_enc_ctx *_enc,
1488  const oc_qii_state *_qs,int _pli,ptrdiff_t _fragi,unsigned _rd_scale){
1489   const unsigned char *src;
1490   oc_fragment         *frags;
1491   ptrdiff_t            frag_offs;
1492   oc_qii_state         qt[3];
1493   unsigned             cost[3];
1494   unsigned             satd;
1495   unsigned             dc;
1496   unsigned             best_cost;
1497   int                  best_qii;
1498   int                  qii;
1499   int                  lambda;
1500   int                  ystride;
1501   int                  nqis;
1502   src=_enc->state.ref_frame_data[OC_FRAME_IO];
1503   ystride=_enc->state.ref_ystride[_pli];
1504   frag_offs=_enc->state.frag_buf_offs[_fragi];
1505   satd=oc_enc_frag_intra_satd(_enc,&dc,src+frag_offs,ystride);
1506   /*Most chroma blocks have no AC coefficients to speak of anyway, so it's not
1507      worth spending the bits to change the AC quantizer.
1508     TODO: This may be worth revisiting when we separate out DC and AC
1509      predictions from SATD.*/
1510 #if 0
1511   nqis=_enc->state.nqis;
1512 #else
1513   nqis=1;
1514 #endif
1515   lambda=_enc->lambda;
1516   best_qii=0;
1517   for(qii=0;qii<nqis;qii++){
1518     unsigned cur_rate;
1519     unsigned cur_ssd;
1520     oc_qii_state_advance(qt+qii,_qs,qii);
1521     cur_rate=oc_dct_cost2(_enc,&cur_ssd,qii,_pli,0,satd)
1522      +(qt[qii].bits-_qs->bits<<OC_BIT_SCALE);
1523     cur_ssd=OC_RD_SCALE(cur_ssd,_rd_scale);
1524     cost[qii]=OC_MODE_RD_COST(cur_ssd,cur_rate,lambda);
1525   }
1526   best_cost=cost[0];
1527   for(qii=1;qii<nqis;qii++){
1528     if(cost[qii]<best_cost){
1529       best_cost=cost[qii];
1530       best_qii=qii;
1531     }
1532   }
1533   frags=_enc->state.frags;
1534   frags[_fragi].qii=best_qii;
1535   return best_cost;
1536 }
1537
1538 static void oc_enc_mb_transform_quantize_intra_luma(oc_enc_ctx *_enc,
1539  oc_enc_pipeline_state *_pipe,unsigned _mbi,
1540  const unsigned _rd_scale[4],const unsigned _rd_iscale[4]){
1541   /*Worst case token stack usage for 4 fragments.*/
1542   oc_token_checkpoint  stack[64*4];
1543   oc_token_checkpoint *stackptr;
1544   const oc_sb_map     *sb_maps;
1545   signed char         *mb_modes;
1546   oc_fragment         *frags;
1547   ptrdiff_t           *coded_fragis;
1548   ptrdiff_t            ncoded_fragis;
1549   ptrdiff_t            fragi;
1550   int                  bi;
1551   sb_maps=(const oc_sb_map *)_enc->state.sb_maps;
1552   mb_modes=_enc->state.mb_modes;
1553   frags=_enc->state.frags;
1554   coded_fragis=_pipe->coded_fragis[0];
1555   ncoded_fragis=_pipe->ncoded_fragis[0];
1556   stackptr=stack;
1557   for(bi=0;bi<4;bi++){
1558     fragi=sb_maps[_mbi>>2][_mbi&3][bi];
1559     frags[fragi].refi=OC_FRAME_SELF;
1560     frags[fragi].mb_mode=OC_MODE_INTRA;
1561     oc_enc_block_transform_quantize(_enc,_pipe,0,fragi,
1562      _rd_scale[bi],_rd_iscale[bi],NULL,NULL,&stackptr);
1563     coded_fragis[ncoded_fragis++]=fragi;
1564   }
1565   _pipe->ncoded_fragis[0]=ncoded_fragis;
1566 }
1567
1568 static void oc_enc_sb_transform_quantize_intra_chroma(oc_enc_ctx *_enc,
1569  oc_enc_pipeline_state *_pipe,int _pli,int _sbi_start,int _sbi_end){
1570   const ogg_uint16_t *mcu_rd_scale;
1571   const ogg_uint16_t *mcu_rd_iscale;
1572   const oc_sb_map    *sb_maps;
1573   ptrdiff_t          *coded_fragis;
1574   ptrdiff_t           ncoded_fragis;
1575   ptrdiff_t           froffset;
1576   int                 sbi;
1577   mcu_rd_scale=(const ogg_uint16_t *)_enc->mcu_rd_scale;
1578   mcu_rd_iscale=(const ogg_uint16_t *)_enc->mcu_rd_iscale;
1579   sb_maps=(const oc_sb_map *)_enc->state.sb_maps;
1580   coded_fragis=_pipe->coded_fragis[_pli];
1581   ncoded_fragis=_pipe->ncoded_fragis[_pli];
1582   froffset=_pipe->froffset[_pli];
1583   for(sbi=_sbi_start;sbi<_sbi_end;sbi++){
1584     /*Worst case token stack usage for 1 fragment.*/
1585     oc_token_checkpoint stack[64];
1586     int                 quadi;
1587     int                 bi;
1588     for(quadi=0;quadi<4;quadi++)for(bi=0;bi<4;bi++){
1589       ptrdiff_t fragi;
1590       fragi=sb_maps[sbi][quadi][bi];
1591       if(fragi>=0){
1592         oc_token_checkpoint *stackptr;
1593         unsigned             rd_scale;
1594         unsigned             rd_iscale;
1595         rd_scale=mcu_rd_scale[fragi-froffset];
1596         rd_iscale=mcu_rd_iscale[fragi-froffset];
1597         oc_analyze_intra_chroma_block(_enc,_pipe->qs+_pli,_pli,fragi,rd_scale);
1598         stackptr=stack;
1599         oc_enc_block_transform_quantize(_enc,_pipe,_pli,fragi,
1600          rd_scale,rd_iscale,NULL,NULL,&stackptr);
1601         coded_fragis[ncoded_fragis++]=fragi;
1602       }
1603     }
1604   }
1605   _pipe->ncoded_fragis[_pli]=ncoded_fragis;
1606 }
1607
1608 /*Analysis stage for an INTRA frame.*/
1609 void oc_enc_analyze_intra(oc_enc_ctx *_enc,int _recode){
1610   ogg_int64_t             activity_sum;
1611   ogg_int64_t             luma_sum;
1612   unsigned                activity_avg;
1613   unsigned                luma_avg;
1614   const ogg_uint16_t     *chroma_rd_scale;
1615   ogg_uint16_t           *mcu_rd_scale;
1616   ogg_uint16_t           *mcu_rd_iscale;
1617   const unsigned char    *map_idxs;
1618   int                     nmap_idxs;
1619   oc_sb_flags            *sb_flags;
1620   signed char            *mb_modes;
1621   const oc_mb_map        *mb_maps;
1622   const oc_sb_map        *sb_maps;
1623   oc_fragment            *frags;
1624   unsigned                stripe_sby;
1625   unsigned                mcu_nvsbs;
1626   int                     notstart;
1627   int                     notdone;
1628   int                     refi;
1629   int                     pli;
1630   _enc->state.frame_type=OC_INTRA_FRAME;
1631   oc_enc_tokenize_start(_enc);
1632   oc_enc_pipeline_init(_enc,&_enc->pipe);
1633   oc_enc_mode_rd_init(_enc);
1634   activity_sum=luma_sum=0;
1635   activity_avg=_enc->activity_avg;
1636   luma_avg=OC_CLAMPI(90<<8,_enc->luma_avg,160<<8);
1637   chroma_rd_scale=_enc->chroma_rd_scale[OC_INTRA_FRAME][_enc->state.qis[0]];
1638   mcu_rd_scale=_enc->mcu_rd_scale;
1639   mcu_rd_iscale=_enc->mcu_rd_iscale;
1640   /*Choose MVs and MB modes and quantize and code luma.
1641     Must be done in Hilbert order.*/
1642   map_idxs=OC_MB_MAP_IDXS[_enc->state.info.pixel_fmt];
1643   nmap_idxs=OC_MB_MAP_NIDXS[_enc->state.info.pixel_fmt];
1644   _enc->state.ncoded_fragis[0]=0;
1645   _enc->state.ncoded_fragis[1]=0;
1646   _enc->state.ncoded_fragis[2]=0;
1647   sb_flags=_enc->state.sb_flags;
1648   mb_modes=_enc->state.mb_modes;
1649   mb_maps=(const oc_mb_map *)_enc->state.mb_maps;
1650   sb_maps=(const oc_sb_map *)_enc->state.sb_maps;
1651   frags=_enc->state.frags;
1652   notstart=0;
1653   notdone=1;
1654   mcu_nvsbs=_enc->mcu_nvsbs;
1655   for(stripe_sby=0;notdone;stripe_sby+=mcu_nvsbs){
1656     ptrdiff_t cfroffset;
1657     unsigned  sbi;
1658     unsigned  sbi_end;
1659     notdone=oc_enc_pipeline_set_stripe(_enc,&_enc->pipe,stripe_sby);
1660     sbi_end=_enc->pipe.sbi_end[0];
1661     cfroffset=_enc->pipe.froffset[1];
1662     for(sbi=_enc->pipe.sbi0[0];sbi<sbi_end;sbi++){
1663       int quadi;
1664       /*Mode addressing is through Y plane, always 4 MB per SB.*/
1665       for(quadi=0;quadi<4;quadi++)if(sb_flags[sbi].quad_valid&1<<quadi){
1666         unsigned  activity[4];
1667         unsigned  rd_scale[5];
1668         unsigned  rd_iscale[5];
1669         unsigned  luma;
1670         unsigned  mbi;
1671         int       mapii;
1672         int       mapi;
1673         int       bi;
1674         ptrdiff_t fragi;
1675         mbi=sbi<<2|quadi;
1676         /*Activity masking.*/
1677         if(_enc->sp_level<OC_SP_LEVEL_FAST_ANALYSIS){
1678           luma=oc_mb_activity(_enc,mbi,activity);
1679         }
1680         else{
1681           unsigned intra_satd[12];
1682           oc_mb_intra_satd(_enc,mbi,intra_satd);
1683           luma=oc_mb_activity_fast(_enc,mbi,activity,intra_satd);
1684           for(bi=0;bi<4;bi++)frags[sb_maps[mbi>>2][mbi&3][bi]].qii=0;
1685         }
1686         activity_sum+=oc_mb_masking(rd_scale,rd_iscale,
1687          chroma_rd_scale,activity,activity_avg,luma,luma_avg);
1688         luma_sum+=luma;
1689         /*Motion estimation:
1690           We do a basic 1MV search for all macroblocks, coded or not,
1691            keyframe or not, unless we aren't using motion estimation at all.*/
1692         if(!_recode&&_enc->state.curframe_num>0&&
1693          _enc->sp_level<OC_SP_LEVEL_NOMC&&_enc->keyframe_frequency_force>1){
1694           oc_mcenc_search(_enc,mbi);
1695         }
1696         if(_enc->sp_level<OC_SP_LEVEL_FAST_ANALYSIS){
1697           oc_analyze_intra_mb_luma(_enc,_enc->pipe.qs+0,mbi,rd_scale);
1698         }
1699         mb_modes[mbi]=OC_MODE_INTRA;
1700         oc_enc_mb_transform_quantize_intra_luma(_enc,&_enc->pipe,
1701          mbi,rd_scale,rd_iscale);
1702         /*Propagate final MB mode and MVs to the chroma blocks.*/
1703         for(mapii=4;mapii<nmap_idxs;mapii++){
1704           mapi=map_idxs[mapii];
1705           pli=mapi>>2;
1706           bi=mapi&3;
1707           fragi=mb_maps[mbi][pli][bi];
1708           frags[fragi].refi=OC_FRAME_SELF;
1709           frags[fragi].mb_mode=OC_MODE_INTRA;
1710         }
1711         /*Save masking scale factors for chroma blocks.*/
1712         for(mapii=4;mapii<(nmap_idxs-4>>1)+4;mapii++){
1713           mapi=map_idxs[mapii];
1714           bi=mapi&3;
1715           fragi=mb_maps[mbi][1][bi];
1716           mcu_rd_scale[fragi-cfroffset]=(ogg_uint16_t)rd_scale[4];
1717           mcu_rd_iscale[fragi-cfroffset]=(ogg_uint16_t)rd_iscale[4];
1718         }
1719       }
1720     }
1721     oc_enc_pipeline_finish_mcu_plane(_enc,&_enc->pipe,0,notstart,notdone);
1722     /*Code chroma planes.*/
1723     for(pli=1;pli<3;pli++){
1724       oc_enc_sb_transform_quantize_intra_chroma(_enc,&_enc->pipe,
1725        pli,_enc->pipe.sbi0[pli],_enc->pipe.sbi_end[pli]);
1726       oc_enc_pipeline_finish_mcu_plane(_enc,&_enc->pipe,pli,notstart,notdone);
1727     }
1728     notstart=1;
1729   }
1730   /*Compute the average block activity and MB luma score for the frame.*/
1731   _enc->activity_avg=OC_MAXI(OC_ACTIVITY_AVG_MIN,
1732    (unsigned)((activity_sum+(_enc->state.fplanes[0].nfrags>>1))/
1733    _enc->state.fplanes[0].nfrags));
1734   _enc->luma_avg=(unsigned)((luma_sum+(_enc->state.nmbs>>1))/_enc->state.nmbs);
1735   /*Finish filling in the reference frame borders.*/
1736   refi=_enc->state.ref_frame_idx[OC_FRAME_SELF];
1737   for(pli=0;pli<3;pli++)oc_state_borders_fill_caps(&_enc->state,refi,pli);
1738   _enc->state.ntotal_coded_fragis=_enc->state.nfrags;
1739 }
1740
1741
1742
1743 /*Cost information about a MB mode.*/
1744 struct oc_mode_choice{
1745   unsigned      cost;
1746   unsigned      ssd;
1747   unsigned      rate;
1748   unsigned      overhead;
1749   unsigned char qii[12];
1750 };
1751
1752
1753
1754 static void oc_mode_set_cost(oc_mode_choice *_modec,int _lambda){
1755   _modec->cost=OC_MODE_RD_COST(_modec->ssd,
1756    _modec->rate+_modec->overhead,_lambda);
1757 }
1758
1759 /*A set of skip SSD's to use to disable early skipping.*/
1760 static const unsigned OC_NOSKIP[12]={
1761   UINT_MAX,UINT_MAX,UINT_MAX,UINT_MAX,
1762   UINT_MAX,UINT_MAX,UINT_MAX,UINT_MAX,
1763   UINT_MAX,UINT_MAX,UINT_MAX,UINT_MAX
1764 };
1765
1766 /*The estimated number of bits used by a coded chroma block to specify the AC
1767    quantizer.
1768   TODO: Currently this is just 0.5*log2(3) (estimating about 50% compression);
1769    measurements suggest this is in the right ballpark, but it varies somewhat
1770    with lambda.*/
1771 #define OC_CHROMA_QII_RATE ((0xCAE00D1DU>>31-OC_BIT_SCALE)+1>>1)
1772
1773 static void oc_analyze_mb_mode_luma(oc_enc_ctx *_enc,
1774  oc_mode_choice *_modec,const oc_fr_state *_fr,const oc_qii_state *_qs,
1775  const unsigned _frag_satd[12],const unsigned _skip_ssd[12],
1776  const unsigned _rd_scale[4],int _qti){
1777   oc_fr_state  fr;
1778   oc_qii_state qs;
1779   unsigned     ssd;
1780   unsigned     rate;
1781   unsigned     satd;
1782   unsigned     best_ssd;
1783   unsigned     best_rate;
1784   int          best_fri;
1785   int          best_qii;
1786   int          lambda;
1787   int          nqis;
1788   int          nskipped;
1789   int          bi;
1790   lambda=_enc->lambda;
1791   nqis=_enc->state.nqis;
1792   /*We could do a trellis optimization here, but we don't make final skip
1793      decisions until after transform+quantization, so the result wouldn't be
1794      optimal anyway.
1795     Instead we just use a greedy approach; for most SATD values, the
1796      differences between the qiis are large enough to drown out the cost to
1797      code the flags, anyway.*/
1798   *&fr=*_fr;
1799   *&qs=*_qs;
1800   ssd=rate=nskipped=0;
1801   for(bi=0;bi<4;bi++){
1802     oc_fr_state  ft[2];
1803     oc_qii_state qt[3];
1804     unsigned     best_cost;
1805     unsigned     cur_cost;
1806     unsigned     cur_ssd;
1807     unsigned     cur_rate;
1808     unsigned     cur_overhead;
1809     int          qii;
1810     satd=_frag_satd[bi];
1811     *(ft+0)=*&fr;
1812     oc_fr_code_block(ft+0);
1813     cur_overhead=ft[0].bits-fr.bits;
1814     best_rate=oc_dct_cost2(_enc,&best_ssd,0,0,_qti,satd)
1815      +(cur_overhead<<OC_BIT_SCALE);
1816     if(nqis>1){
1817       oc_qii_state_advance(qt+0,&qs,0);
1818       best_rate+=qt[0].bits-qs.bits<<OC_BIT_SCALE;
1819     }
1820     best_ssd=OC_RD_SCALE(best_ssd,_rd_scale[bi]);
1821     best_cost=OC_MODE_RD_COST(ssd+best_ssd,rate+best_rate,lambda);
1822     best_fri=0;
1823     best_qii=0;
1824     for(qii=1;qii<nqis;qii++){
1825       oc_qii_state_advance(qt+qii,&qs,qii);
1826       cur_rate=oc_dct_cost2(_enc,&cur_ssd,qii,0,_qti,satd)
1827        +(cur_overhead+qt[qii].bits-qs.bits<<OC_BIT_SCALE);
1828       cur_ssd=OC_RD_SCALE(cur_ssd,_rd_scale[bi]);
1829       cur_cost=OC_MODE_RD_COST(ssd+cur_ssd,rate+cur_rate,lambda);
1830       if(cur_cost<best_cost){
1831         best_cost=cur_cost;
1832         best_ssd=cur_ssd;
1833         best_rate=cur_rate;
1834         best_qii=qii;
1835       }
1836     }
1837     if(_skip_ssd[bi]<(UINT_MAX>>OC_BIT_SCALE)&&nskipped<3){
1838       *(ft+1)=*&fr;
1839       oc_fr_skip_block(ft+1);
1840       cur_overhead=ft[1].bits-fr.bits<<OC_BIT_SCALE;
1841       cur_ssd=_skip_ssd[bi]<<OC_BIT_SCALE;
1842       cur_cost=OC_MODE_RD_COST(ssd+cur_ssd,rate+cur_overhead,lambda);
1843       if(cur_cost<=best_cost){
1844         best_ssd=cur_ssd;
1845         best_rate=cur_overhead;
1846         best_fri=1;
1847         best_qii+=4;
1848       }
1849     }
1850     rate+=best_rate;
1851     ssd+=best_ssd;
1852     *&fr=*(ft+best_fri);
1853     if(best_fri==0)*&qs=*(qt+best_qii);
1854     else nskipped++;
1855     _modec->qii[bi]=best_qii;
1856   }
1857   _modec->ssd=ssd;
1858   _modec->rate=rate;
1859 }
1860
1861 static void oc_analyze_mb_mode_chroma(oc_enc_ctx *_enc,
1862  oc_mode_choice *_modec,const oc_fr_state *_fr,const oc_qii_state *_qs,
1863  const unsigned _frag_satd[12],const unsigned _skip_ssd[12],
1864  unsigned _rd_scale,int _qti){
1865   unsigned ssd;
1866   unsigned rate;
1867   unsigned satd;
1868   unsigned best_ssd;
1869   unsigned best_rate;
1870   int      best_qii;
1871   unsigned cur_cost;
1872   unsigned cur_ssd;
1873   unsigned cur_rate;
1874   int      lambda;
1875   int      nblocks;
1876   int      nqis;
1877   int      pli;
1878   int      bi;
1879   int      qii;
1880   lambda=_enc->lambda;
1881   /*Most chroma blocks have no AC coefficients to speak of anyway, so it's not
1882      worth spending the bits to change the AC quantizer.
1883     TODO: This may be worth revisiting when we separate out DC and AC
1884      predictions from SATD.*/
1885 #if 0
1886   nqis=_enc->state.nqis;
1887 #else
1888   nqis=1;
1889 #endif
1890   ssd=_modec->ssd;
1891   rate=_modec->rate;
1892   /*Because (except in 4:4:4 mode) we aren't considering chroma blocks in coded
1893      order, we assume a constant overhead for coded block and qii flags.*/
1894   nblocks=OC_MB_MAP_NIDXS[_enc->state.info.pixel_fmt];
1895   nblocks=(nblocks-4>>1)+4;
1896   bi=4;
1897   for(pli=1;pli<3;pli++){
1898     for(;bi<nblocks;bi++){
1899       unsigned best_cost;
1900       satd=_frag_satd[bi];
1901       best_rate=oc_dct_cost2(_enc,&best_ssd,0,pli,_qti,satd)
1902        +OC_CHROMA_QII_RATE;
1903       best_ssd=OC_RD_SCALE(best_ssd,_rd_scale);
1904       best_cost=OC_MODE_RD_COST(ssd+best_ssd,rate+best_rate,lambda);
1905       best_qii=0;
1906       for(qii=1;qii<nqis;qii++){
1907         cur_rate=oc_dct_cost2(_enc,&cur_ssd,qii,pli,_qti,satd)
1908          +OC_CHROMA_QII_RATE;
1909         cur_ssd=OC_RD_SCALE(cur_ssd,_rd_scale);
1910         cur_cost=OC_MODE_RD_COST(ssd+cur_ssd,rate+cur_rate,lambda);
1911         if(cur_cost<best_cost){
1912           best_cost=cur_cost;
1913           best_ssd=cur_ssd;
1914           best_rate=cur_rate;
1915           best_qii=qii;
1916         }
1917       }
1918       if(_skip_ssd[bi]<(UINT_MAX>>OC_BIT_SCALE)){
1919         cur_ssd=_skip_ssd[bi]<<OC_BIT_SCALE;
1920         cur_cost=OC_MODE_RD_COST(ssd+cur_ssd,rate,lambda);
1921         if(cur_cost<=best_cost){
1922           best_ssd=cur_ssd;
1923           best_rate=0;
1924           best_qii+=4;
1925         }
1926       }
1927       rate+=best_rate;
1928       ssd+=best_ssd;
1929       _modec->qii[bi]=best_qii;
1930     }
1931     nblocks=(nblocks-4<<1)+4;
1932   }
1933   _modec->ssd=ssd;
1934   _modec->rate=rate;
1935 }
1936
1937 static void oc_skip_cost(oc_enc_ctx *_enc,oc_enc_pipeline_state *_pipe,
1938  unsigned _mbi,const unsigned _rd_scale[4],unsigned _ssd[12]){
1939   const unsigned char   *src;
1940   const unsigned char   *ref;
1941   int                    ystride;
1942   const oc_fragment     *frags;
1943   const ptrdiff_t       *frag_buf_offs;
1944   const ptrdiff_t       *sb_map;
1945   const oc_mb_map_plane *mb_map;
1946   const unsigned char   *map_idxs;
1947   oc_mv                 *mvs;
1948   int                    map_nidxs;
1949   unsigned               uncoded_ssd;
1950   int                    mapii;
1951   int                    mapi;
1952   int                    pli;
1953   int                    bi;
1954   ptrdiff_t              fragi;
1955   ptrdiff_t              frag_offs;
1956   int                    borderi;
1957   src=_enc->state.ref_frame_data[OC_FRAME_IO];
1958   ref=_enc->state.ref_frame_data[OC_FRAME_PREV];
1959   ystride=_enc->state.ref_ystride[0];
1960   frags=_enc->state.frags;
1961   frag_buf_offs=_enc->state.frag_buf_offs;
1962   sb_map=_enc->state.sb_maps[_mbi>>2][_mbi&3];
1963   mvs=_enc->mb_info[_mbi].block_mv;
1964   for(bi=0;bi<4;bi++){
1965     fragi=sb_map[bi];
1966     borderi=frags[fragi].borderi;
1967     frag_offs=frag_buf_offs[fragi];
1968     if(borderi<0){
1969       uncoded_ssd=oc_enc_frag_ssd(_enc,src+frag_offs,ref+frag_offs,ystride);
1970     }
1971     else{
1972       uncoded_ssd=oc_enc_frag_border_ssd(_enc,
1973        src+frag_offs,ref+frag_offs,ystride,_enc->state.borders[borderi].mask);
1974     }
1975     /*Scale to match DCT domain and RD.*/
1976     uncoded_ssd=OC_RD_SKIP_SCALE(uncoded_ssd,_rd_scale[bi]);
1977     /*Motion is a special case; if there is more than a full-pixel motion
1978        against the prior frame, penalize skipping.
1979       TODO: The factor of two here is a kludge, but it tested out better than a
1980        hard limit.*/
1981     if(mvs[bi]!=0)uncoded_ssd*=2;
1982     _pipe->skip_ssd[0][fragi-_pipe->froffset[0]]=_ssd[bi]=uncoded_ssd;
1983   }
1984   mb_map=(const oc_mb_map_plane *)_enc->state.mb_maps[_mbi];
1985   map_nidxs=OC_MB_MAP_NIDXS[_enc->state.info.pixel_fmt];
1986   map_idxs=OC_MB_MAP_IDXS[_enc->state.info.pixel_fmt];
1987   map_nidxs=(map_nidxs-4>>1)+4;
1988   mapii=4;
1989   mvs=_enc->mb_info[_mbi].unref_mv;
1990   for(pli=1;pli<3;pli++){
1991     ystride=_enc->state.ref_ystride[pli];
1992     for(;mapii<map_nidxs;mapii++){
1993       mapi=map_idxs[mapii];
1994       bi=mapi&3;
1995       fragi=mb_map[pli][bi];
1996       borderi=frags[fragi].borderi;
1997       frag_offs=frag_buf_offs[fragi];
1998       if(borderi<0){
1999         uncoded_ssd=oc_enc_frag_ssd(_enc,src+frag_offs,ref+frag_offs,ystride);
2000       }
2001       else{
2002         uncoded_ssd=oc_enc_frag_border_ssd(_enc,
2003          src+frag_offs,ref+frag_offs,ystride,_enc->state.borders[borderi].mask);
2004       }
2005       /*Scale to match DCT domain and RD.*/
2006       uncoded_ssd=OC_RD_SKIP_SCALE(uncoded_ssd,_rd_scale[4]);
2007       /*Motion is a special case; if there is more than a full-pixel motion
2008          against the prior frame, penalize skipping.
2009         TODO: The factor of two here is a kludge, but it tested out better than
2010          a hard limit*/
2011       if(mvs[OC_FRAME_PREV]!=0)uncoded_ssd*=2;
2012       _pipe->skip_ssd[pli][fragi-_pipe->froffset[pli]]=_ssd[mapii]=uncoded_ssd;
2013     }
2014     map_nidxs=(map_nidxs-4<<1)+4;
2015   }
2016 }
2017
2018
2019 static void oc_cost_intra(oc_enc_ctx *_enc,oc_mode_choice *_modec,
2020  unsigned _mbi,const oc_fr_state *_fr,const oc_qii_state *_qs,
2021  const unsigned _frag_satd[12],const unsigned _skip_ssd[12],
2022  const unsigned _rd_scale[5]){
2023   oc_analyze_mb_mode_luma(_enc,_modec,_fr,_qs,_frag_satd,_skip_ssd,_rd_scale,0);
2024   oc_analyze_mb_mode_chroma(_enc,_modec,_fr,_qs,
2025    _frag_satd,_skip_ssd,_rd_scale[4],0);
2026   _modec->overhead=
2027    oc_mode_scheme_chooser_cost(&_enc->chooser,OC_MODE_INTRA)<<OC_BIT_SCALE;
2028   oc_mode_set_cost(_modec,_enc->lambda);
2029 }
2030
2031 static void oc_cost_inter(oc_enc_ctx *_enc,oc_mode_choice *_modec,
2032  unsigned _mbi,int _mb_mode,oc_mv _mv,
2033  const oc_fr_state *_fr,const oc_qii_state *_qs,
2034  const unsigned _skip_ssd[12],const unsigned _rd_scale[5]){
2035   unsigned               frag_satd[12];
2036   const unsigned char   *src;
2037   const unsigned char   *ref;
2038   int                    ystride;
2039   const ptrdiff_t       *frag_buf_offs;
2040   const ptrdiff_t       *sb_map;
2041   const oc_mb_map_plane *mb_map;
2042   const unsigned char   *map_idxs;
2043   int                    map_nidxs;
2044   int                    mapii;
2045   int                    mapi;
2046   int                    mv_offs[2];
2047   int                    pli;
2048   int                    bi;
2049   ptrdiff_t              fragi;
2050   ptrdiff_t              frag_offs;
2051   unsigned               dc;
2052   src=_enc->state.ref_frame_data[OC_FRAME_IO];
2053   ref=_enc->state.ref_frame_data[OC_FRAME_FOR_MODE(_mb_mode)];
2054   ystride=_enc->state.ref_ystride[0];
2055   frag_buf_offs=_enc->state.frag_buf_offs;
2056   sb_map=_enc->state.sb_maps[_mbi>>2][_mbi&3];
2057   _modec->rate=_modec->ssd=0;
2058   if(oc_state_get_mv_offsets(&_enc->state,mv_offs,0,_mv)>1){
2059     for(bi=0;bi<4;bi++){
2060       fragi=sb_map[bi];
2061       frag_offs=frag_buf_offs[fragi];
2062       frag_satd[bi]=oc_enc_frag_satd2(_enc,&dc,src+frag_offs,
2063        ref+frag_offs+mv_offs[0],ref+frag_offs+mv_offs[1],ystride);
2064       frag_satd[bi]+=dc;
2065     }
2066   }
2067   else{
2068     for(bi=0;bi<4;bi++){
2069       fragi=sb_map[bi];
2070       frag_offs=frag_buf_offs[fragi];
2071       frag_satd[bi]=oc_enc_frag_satd(_enc,&dc,src+frag_offs,
2072        ref+frag_offs+mv_offs[0],ystride);
2073       frag_satd[bi]+=dc;
2074     }
2075   }
2076   mb_map=(const oc_mb_map_plane *)_enc->state.mb_maps[_mbi];
2077   map_idxs=OC_MB_MAP_IDXS[_enc->state.info.pixel_fmt];
2078   map_nidxs=OC_MB_MAP_NIDXS[_enc->state.info.pixel_fmt];
2079   /*Note: This assumes ref_ystride[1]==ref_ystride[2].*/
2080   ystride=_enc->state.ref_ystride[1];
2081   if(oc_state_get_mv_offsets(&_enc->state,mv_offs,1,_mv)>1){
2082     for(mapii=4;mapii<map_nidxs;mapii++){
2083       mapi=map_idxs[mapii];
2084       pli=mapi>>2;
2085       bi=mapi&3;
2086       fragi=mb_map[pli][bi];
2087       frag_offs=frag_buf_offs[fragi];
2088       frag_satd[mapii]=oc_enc_frag_satd2(_enc,&dc,src+frag_offs,
2089        ref+frag_offs+mv_offs[0],ref+frag_offs+mv_offs[1],ystride);
2090       frag_satd[mapii]+=dc;
2091     }
2092   }
2093   else{
2094     for(mapii=4;mapii<map_nidxs;mapii++){
2095       mapi=map_idxs[mapii];
2096       pli=mapi>>2;
2097       bi=mapi&3;
2098       fragi=mb_map[pli][bi];
2099       frag_offs=frag_buf_offs[fragi];
2100       frag_satd[mapii]=oc_enc_frag_satd(_enc,&dc,src+frag_offs,
2101        ref+frag_offs+mv_offs[0],ystride);
2102       frag_satd[mapii]+=dc;
2103     }
2104   }
2105   oc_analyze_mb_mode_luma(_enc,_modec,_fr,_qs,frag_satd,_skip_ssd,_rd_scale,1);
2106   oc_analyze_mb_mode_chroma(_enc,_modec,_fr,_qs,
2107    frag_satd,_skip_ssd,_rd_scale[4],1);
2108   _modec->overhead=
2109    oc_mode_scheme_chooser_cost(&_enc->chooser,_mb_mode)<<OC_BIT_SCALE;
2110   oc_mode_set_cost(_modec,_enc->lambda);
2111 }
2112
2113 static void oc_cost_inter_nomv(oc_enc_ctx *_enc,oc_mode_choice *_modec,
2114  unsigned _mbi,int _mb_mode,const oc_fr_state *_fr,const oc_qii_state *_qs,
2115  const unsigned _skip_ssd[12],const unsigned _rd_scale[4]){
2116   oc_cost_inter(_enc,_modec,_mbi,_mb_mode,0,_fr,_qs,_skip_ssd,_rd_scale);
2117 }
2118
2119 static int oc_cost_inter1mv(oc_enc_ctx *_enc,oc_mode_choice *_modec,
2120  unsigned _mbi,int _mb_mode,oc_mv _mv,
2121  const oc_fr_state *_fr,const oc_qii_state *_qs,const unsigned _skip_ssd[12],
2122  const unsigned _rd_scale[4]){
2123   int bits0;
2124   oc_cost_inter(_enc,_modec,_mbi,_mb_mode,_mv,_fr,_qs,_skip_ssd,_rd_scale);
2125   bits0=OC_MV_BITS[0][OC_MV_X(_mv)+31]+OC_MV_BITS[0][OC_MV_Y(_mv)+31];
2126   _modec->overhead+=OC_MINI(_enc->mv_bits[0]+bits0,_enc->mv_bits[1]+12)
2127    -OC_MINI(_enc->mv_bits[0],_enc->mv_bits[1])<<OC_BIT_SCALE;
2128   oc_mode_set_cost(_modec,_enc->lambda);
2129   return bits0;
2130 }
2131
2132 /*A mapping from oc_mb_map (raster) ordering to oc_sb_map (Hilbert) ordering.*/
2133 static const unsigned char OC_MB_PHASE[4][4]={
2134   {0,1,3,2},{0,3,1,2},{0,3,1,2},{2,3,1,0}
2135 };
2136
2137 static void oc_cost_inter4mv(oc_enc_ctx *_enc,oc_mode_choice *_modec,
2138  unsigned _mbi,oc_mv _mv[4],const oc_fr_state *_fr,const oc_qii_state *_qs,
2139  const unsigned _skip_ssd[12],const unsigned _rd_scale[5]){
2140   unsigned               frag_satd[12];
2141   oc_mv                  lbmvs[4];
2142   oc_mv                  cbmvs[4];
2143   const unsigned char   *src;
2144   const unsigned char   *ref;
2145   int                    ystride;
2146   const ptrdiff_t       *frag_buf_offs;
2147   oc_mv                 *frag_mvs;
2148   const oc_mb_map_plane *mb_map;
2149   const unsigned char   *map_idxs;
2150   int                    map_nidxs;
2151   int                    nqis;
2152   int                    mapii;
2153   int                    mapi;
2154   int                    mv_offs[2];
2155   int                    pli;
2156   int                    bi;
2157   ptrdiff_t              fragi;
2158   ptrdiff_t              frag_offs;
2159   int                    bits0;
2160   int                    bits1;
2161   unsigned               satd;
2162   unsigned               dc;
2163   src=_enc->state.ref_frame_data[OC_FRAME_IO];
2164   ref=_enc->state.ref_frame_data[OC_FRAME_PREV];
2165   ystride=_enc->state.ref_ystride[0];
2166   frag_buf_offs=_enc->state.frag_buf_offs;
2167   frag_mvs=_enc->state.frag_mvs;
2168   mb_map=(const oc_mb_map_plane *)_enc->state.mb_maps[_mbi];
2169   _modec->rate=_modec->ssd=0;
2170   for(bi=0;bi<4;bi++){
2171     fragi=mb_map[0][bi];
2172     /*Save the block MVs as the current ones while we're here; we'll replace
2173        them if we don't ultimately choose 4MV mode.*/
2174     frag_mvs[fragi]=_mv[bi];
2175     frag_offs=frag_buf_offs[fragi];
2176     if(oc_state_get_mv_offsets(&_enc->state,mv_offs,0,_mv[bi])>1){
2177       satd=oc_enc_frag_satd2(_enc,&dc,src+frag_offs,
2178        ref+frag_offs+mv_offs[0],ref+frag_offs+mv_offs[1],ystride);
2179     }
2180     else{
2181       satd=oc_enc_frag_satd(_enc,&dc,src+frag_offs,
2182        ref+frag_offs+mv_offs[0],ystride);
2183     }
2184     frag_satd[OC_MB_PHASE[_mbi&3][bi]]=satd+dc;
2185   }
2186   oc_analyze_mb_mode_luma(_enc,_modec,_fr,_qs,frag_satd,
2187    _enc->vp3_compatible?OC_NOSKIP:_skip_ssd,_rd_scale,1);
2188   /*Figure out which blocks are being skipped and give them (0,0) MVs.*/
2189   bits0=0;
2190   bits1=0;
2191   nqis=_enc->state.nqis;
2192   for(bi=0;bi<4;bi++){
2193     if(_modec->qii[OC_MB_PHASE[_mbi&3][bi]]>=nqis)lbmvs[bi]=0;
2194     else{
2195       lbmvs[bi]=_mv[bi];
2196       bits0+=OC_MV_BITS[0][OC_MV_X(_mv[bi])+31]
2197        +OC_MV_BITS[0][OC_MV_Y(_mv[bi])+31];
2198       bits1+=12;
2199     }
2200   }
2201   (*OC_SET_CHROMA_MVS_TABLE[_enc->state.info.pixel_fmt])(cbmvs,lbmvs);
2202   map_idxs=OC_MB_MAP_IDXS[_enc->state.info.pixel_fmt];
2203   map_nidxs=OC_MB_MAP_NIDXS[_enc->state.info.pixel_fmt];
2204   /*Note: This assumes ref_ystride[1]==ref_ystride[2].*/
2205   ystride=_enc->state.ref_ystride[1];
2206   for(mapii=4;mapii<map_nidxs;mapii++){
2207     mapi=map_idxs[mapii];
2208     pli=mapi>>2;
2209     bi=mapi&3;
2210     fragi=mb_map[pli][bi];
2211     frag_offs=frag_buf_offs[fragi];
2212     /*TODO: We could save half these calls by re-using the results for the Cb
2213        and Cr planes; is it worth it?*/
2214     if(oc_state_get_mv_offsets(&_enc->state,mv_offs,pli,cbmvs[bi])>1){
2215       satd=oc_enc_frag_satd2(_enc,&dc,src+frag_offs,
2216        ref+frag_offs+mv_offs[0],ref+frag_offs+mv_offs[1],ystride);
2217     }
2218     else{
2219       satd=oc_enc_frag_satd(_enc,&dc,src+frag_offs,
2220        ref+frag_offs+mv_offs[0],ystride);
2221     }
2222     frag_satd[mapii]=satd+dc;
2223   }
2224   oc_analyze_mb_mode_chroma(_enc,_modec,_fr,_qs,
2225    frag_satd,_skip_ssd,_rd_scale[4],1);
2226   _modec->overhead=
2227    oc_mode_scheme_chooser_cost(&_enc->chooser,OC_MODE_INTER_MV_FOUR)
2228    +OC_MINI(_enc->mv_bits[0]+bits0,_enc->mv_bits[1]+bits1)
2229    -OC_MINI(_enc->mv_bits[0],_enc->mv_bits[1])<<OC_BIT_SCALE;
2230   oc_mode_set_cost(_modec,_enc->lambda);
2231 }
2232
2233 int oc_enc_analyze_inter(oc_enc_ctx *_enc,int _allow_keyframe,int _recode){
2234   oc_set_chroma_mvs_func  set_chroma_mvs;
2235   oc_qii_state            intra_luma_qs;
2236   oc_mv                   last_mv;
2237   oc_mv                   prior_mv;
2238   ogg_int64_t             interbits;
2239   ogg_int64_t             intrabits;
2240   ogg_int64_t             activity_sum;
2241   ogg_int64_t             luma_sum;
2242   unsigned                activity_avg;
2243   unsigned                luma_avg;
2244   const ogg_uint16_t     *chroma_rd_scale;
2245   ogg_uint16_t           *mcu_rd_scale;
2246   ogg_uint16_t           *mcu_rd_iscale;
2247   const unsigned char    *map_idxs;
2248   int                     nmap_idxs;
2249   unsigned               *coded_mbis;
2250   unsigned               *uncoded_mbis;
2251   size_t                  ncoded_mbis;
2252   size_t                  nuncoded_mbis;
2253   oc_sb_flags            *sb_flags;
2254   signed char            *mb_modes;
2255   const oc_sb_map        *sb_maps;
2256   const oc_mb_map        *mb_maps;
2257   oc_mb_enc_info         *embs;
2258   oc_fragment            *frags;
2259   oc_mv                  *frag_mvs;
2260   unsigned                stripe_sby;
2261   unsigned                mcu_nvsbs;
2262   int                     notstart;
2263   int                     notdone;
2264   unsigned                sbi;
2265   unsigned                sbi_end;
2266   int                     refi;
2267   int                     pli;
2268   int                     sp_level;
2269   sp_level=_enc->sp_level;
2270   set_chroma_mvs=OC_SET_CHROMA_MVS_TABLE[_enc->state.info.pixel_fmt];
2271   _enc->state.frame_type=OC_INTER_FRAME;
2272   oc_mode_scheme_chooser_reset(&_enc->chooser);
2273   oc_enc_tokenize_start(_enc);
2274   oc_enc_pipeline_init(_enc,&_enc->pipe);
2275   oc_enc_mode_rd_init(_enc);
2276   if(_allow_keyframe)oc_qii_state_init(&intra_luma_qs);
2277   _enc->mv_bits[0]=_enc->mv_bits[1]=0;
2278   interbits=intrabits=0;
2279   activity_sum=luma_sum=0;
2280   activity_avg=_enc->activity_avg;
2281   luma_avg=OC_CLAMPI(90<<8,_enc->luma_avg,160<<8);
2282   chroma_rd_scale=_enc->chroma_rd_scale[OC_INTER_FRAME][_enc->state.qis[0]];
2283   mcu_rd_scale=_enc->mcu_rd_scale;
2284   mcu_rd_iscale=_enc->mcu_rd_iscale;
2285   last_mv=prior_mv=0;
2286   /*Choose MVs and MB modes and quantize and code luma.
2287     Must be done in Hilbert order.*/
2288   map_idxs=OC_MB_MAP_IDXS[_enc->state.info.pixel_fmt];
2289   nmap_idxs=OC_MB_MAP_NIDXS[_enc->state.info.pixel_fmt];
2290   coded_mbis=_enc->coded_mbis;
2291   uncoded_mbis=coded_mbis+_enc->state.nmbs;
2292   ncoded_mbis=0;
2293   nuncoded_mbis=0;
2294   _enc->state.ncoded_fragis[0]=0;
2295   _enc->state.ncoded_fragis[1]=0;
2296   _enc->state.ncoded_fragis[2]=0;
2297   sb_flags=_enc->state.sb_flags;
2298   mb_modes=_enc->state.mb_modes;
2299   sb_maps=(const oc_sb_map *)_enc->state.sb_maps;
2300   mb_maps=(const oc_mb_map *)_enc->state.mb_maps;
2301   embs=_enc->mb_info;
2302   frags=_enc->state.frags;
2303   frag_mvs=_enc->state.frag_mvs;
2304   notstart=0;
2305   notdone=1;
2306   mcu_nvsbs=_enc->mcu_nvsbs;
2307   for(stripe_sby=0;notdone;stripe_sby+=mcu_nvsbs){
2308     ptrdiff_t cfroffset;
2309     notdone=oc_enc_pipeline_set_stripe(_enc,&_enc->pipe,stripe_sby);
2310     sbi_end=_enc->pipe.sbi_end[0];
2311     cfroffset=_enc->pipe.froffset[1];
2312     for(sbi=_enc->pipe.sbi0[0];sbi<sbi_end;sbi++){
2313       int quadi;
2314       /*Mode addressing is through Y plane, always 4 MB per SB.*/
2315       for(quadi=0;quadi<4;quadi++)if(sb_flags[sbi].quad_valid&1<<quadi){
2316         oc_mode_choice modes[8];
2317         unsigned       activity[4];
2318         unsigned       rd_scale[5];
2319         unsigned       rd_iscale[5];
2320         unsigned       skip_ssd[12];
2321         unsigned       intra_satd[12];
2322         unsigned       luma;
2323         int            mb_mv_bits_0;
2324         int            mb_gmv_bits_0;
2325         int            inter_mv_pref;
2326         int            mb_mode;
2327         int            refi;
2328         int            mv;
2329         unsigned       mbi;
2330         int            mapii;
2331         int            mapi;
2332         int            bi;
2333         ptrdiff_t      fragi;
2334         mbi=sbi<<2|quadi;
2335         oc_mb_intra_satd(_enc,mbi,intra_satd);
2336         /*Activity masking.*/
2337         if(sp_level<OC_SP_LEVEL_FAST_ANALYSIS){
2338           luma=oc_mb_activity(_enc,mbi,activity);
2339         }
2340         else{
2341           luma=oc_mb_activity_fast(_enc,mbi,activity,intra_satd);
2342         }
2343         luma_sum+=luma;
2344         activity_sum+=oc_mb_masking(rd_scale,rd_iscale,
2345          chroma_rd_scale,activity,activity_avg,luma,luma_avg);
2346         /*Motion estimation:
2347           We always do a basic 1MV search for all macroblocks, coded or not,
2348            keyframe or not.*/
2349         if(!_recode&&sp_level<OC_SP_LEVEL_NOMC)oc_mcenc_search(_enc,mbi);
2350         mv=0;
2351         /*Find the block choice with the lowest estimated coding cost.
2352           If a Cb or Cr block is coded but no Y' block from a macro block then
2353            the mode MUST be OC_MODE_INTER_NOMV.
2354           This is the default state to which the mode data structure is
2355            initialised in encoder and decoder at the start of each frame.*/
2356         /*Block coding cost is estimated from correlated SATD metrics.*/
2357         /*At this point, all blocks that are in frame are still marked coded.*/
2358         if(!_recode){
2359           embs[mbi].unref_mv[OC_FRAME_GOLD]=
2360            embs[mbi].analysis_mv[0][OC_FRAME_GOLD];
2361           embs[mbi].unref_mv[OC_FRAME_PREV]=
2362            embs[mbi].analysis_mv[0][OC_FRAME_PREV];
2363           embs[mbi].refined=0;
2364         }
2365         /*Estimate the cost of coding this MB in a keyframe.*/
2366         if(_allow_keyframe){
2367           oc_cost_intra(_enc,modes+OC_MODE_INTRA,mbi,
2368            _enc->pipe.fr+0,&intra_luma_qs,intra_satd,OC_NOSKIP,rd_scale);
2369           intrabits+=modes[OC_MODE_INTRA].rate;
2370           for(bi=0;bi<4;bi++){
2371             oc_qii_state_advance(&intra_luma_qs,&intra_luma_qs,
2372              modes[OC_MODE_INTRA].qii[bi]);
2373           }
2374         }
2375         /*Estimate the cost in a delta frame for various modes.*/
2376         oc_skip_cost(_enc,&_enc->pipe,mbi,rd_scale,skip_ssd);
2377         if(sp_level<OC_SP_LEVEL_NOMC){
2378           oc_cost_inter_nomv(_enc,modes+OC_MODE_INTER_NOMV,mbi,
2379            OC_MODE_INTER_NOMV,_enc->pipe.fr+0,_enc->pipe.qs+0,
2380            skip_ssd,rd_scale);
2381           oc_cost_intra(_enc,modes+OC_MODE_INTRA,mbi,
2382            _enc->pipe.fr+0,_enc->pipe.qs+0,intra_satd,skip_ssd,rd_scale);
2383           mb_mv_bits_0=oc_cost_inter1mv(_enc,modes+OC_MODE_INTER_MV,mbi,
2384            OC_MODE_INTER_MV,embs[mbi].unref_mv[OC_FRAME_PREV],
2385            _enc->pipe.fr+0,_enc->pipe.qs+0,skip_ssd,rd_scale);
2386           oc_cost_inter(_enc,modes+OC_MODE_INTER_MV_LAST,mbi,
2387            OC_MODE_INTER_MV_LAST,last_mv,_enc->pipe.fr+0,_enc->pipe.qs+0,
2388            skip_ssd,rd_scale);
2389           oc_cost_inter(_enc,modes+OC_MODE_INTER_MV_LAST2,mbi,
2390            OC_MODE_INTER_MV_LAST2,prior_mv,_enc->pipe.fr+0,_enc->pipe.qs+0,
2391            skip_ssd,rd_scale);
2392           oc_cost_inter_nomv(_enc,modes+OC_MODE_GOLDEN_NOMV,mbi,
2393            OC_MODE_GOLDEN_NOMV,_enc->pipe.fr+0,_enc->pipe.qs+0,
2394            skip_ssd,rd_scale);
2395           mb_gmv_bits_0=oc_cost_inter1mv(_enc,modes+OC_MODE_GOLDEN_MV,mbi,
2396            OC_MODE_GOLDEN_MV,embs[mbi].unref_mv[OC_FRAME_GOLD],
2397            _enc->pipe.fr+0,_enc->pipe.qs+0,skip_ssd,rd_scale);
2398           /*The explicit MV modes (2,6,7) have not yet gone through halfpel
2399              refinement.
2400             We choose the explicit MV mode that's already furthest ahead on
2401              R-D cost and refine only that one.
2402             We have to be careful to remember which ones we've refined so that
2403              we don't refine it again if we re-encode this frame.*/
2404           inter_mv_pref=_enc->lambda*3;
2405           if(sp_level<OC_SP_LEVEL_FAST_ANALYSIS){
2406             oc_cost_inter4mv(_enc,modes+OC_MODE_INTER_MV_FOUR,mbi,
2407              embs[mbi].block_mv,_enc->pipe.fr+0,_enc->pipe.qs+0,
2408              skip_ssd,rd_scale);
2409           }
2410           else{
2411             modes[OC_MODE_INTER_MV_FOUR].cost=UINT_MAX;
2412           }
2413           if(modes[OC_MODE_INTER_MV_FOUR].cost<modes[OC_MODE_INTER_MV].cost&&
2414            modes[OC_MODE_INTER_MV_FOUR].cost<modes[OC_MODE_GOLDEN_MV].cost){
2415             if(!(embs[mbi].refined&0x80)){
2416               oc_mcenc_refine4mv(_enc,mbi);
2417               embs[mbi].refined|=0x80;
2418             }
2419             oc_cost_inter4mv(_enc,modes+OC_MODE_INTER_MV_FOUR,mbi,
2420              embs[mbi].ref_mv,_enc->pipe.fr+0,_enc->pipe.qs+0,
2421              skip_ssd,rd_scale);
2422           }
2423           else if(modes[OC_MODE_GOLDEN_MV].cost+inter_mv_pref<
2424            modes[OC_MODE_INTER_MV].cost){
2425             if(!(embs[mbi].refined&0x40)){
2426               oc_mcenc_refine1mv(_enc,mbi,OC_FRAME_GOLD);
2427               embs[mbi].refined|=0x40;
2428             }
2429             mb_gmv_bits_0=oc_cost_inter1mv(_enc,modes+OC_MODE_GOLDEN_MV,mbi,
2430              OC_MODE_GOLDEN_MV,embs[mbi].analysis_mv[0][OC_FRAME_GOLD],
2431              _enc->pipe.fr+0,_enc->pipe.qs+0,skip_ssd,rd_scale);
2432           }
2433           if(!(embs[mbi].refined&0x04)){
2434             oc_mcenc_refine1mv(_enc,mbi,OC_FRAME_PREV);
2435             embs[mbi].refined|=0x04;
2436           }
2437           mb_mv_bits_0=oc_cost_inter1mv(_enc,modes+OC_MODE_INTER_MV,mbi,
2438            OC_MODE_INTER_MV,embs[mbi].analysis_mv[0][OC_FRAME_PREV],
2439            _enc->pipe.fr+0,_enc->pipe.qs+0,skip_ssd,rd_scale);
2440           /*Finally, pick the mode with the cheapest estimated R-D cost.*/
2441           mb_mode=OC_MODE_INTER_NOMV;
2442           if(modes[OC_MODE_INTRA].cost<modes[OC_MODE_INTER_NOMV].cost){
2443             mb_mode=OC_MODE_INTRA;
2444           }
2445           if(modes[OC_MODE_INTER_MV_LAST].cost<modes[mb_mode].cost){
2446             mb_mode=OC_MODE_INTER_MV_LAST;
2447           }
2448           if(modes[OC_MODE_INTER_MV_LAST2].cost<modes[mb_mode].cost){
2449             mb_mode=OC_MODE_INTER_MV_LAST2;
2450           }
2451           if(modes[OC_MODE_GOLDEN_NOMV].cost<modes[mb_mode].cost){
2452             mb_mode=OC_MODE_GOLDEN_NOMV;
2453           }
2454           if(modes[OC_MODE_GOLDEN_MV].cost<modes[mb_mode].cost){
2455             mb_mode=OC_MODE_GOLDEN_MV;
2456           }
2457           if(modes[OC_MODE_INTER_MV_FOUR].cost<modes[mb_mode].cost){
2458             mb_mode=OC_MODE_INTER_MV_FOUR;
2459           }
2460           /*We prefer OC_MODE_INTER_MV, but not over LAST and LAST2.*/
2461           if(mb_mode==OC_MODE_INTER_MV_LAST||mb_mode==OC_MODE_INTER_MV_LAST2){
2462             inter_mv_pref=0;
2463           }
2464           if(modes[OC_MODE_INTER_MV].cost<modes[mb_mode].cost+inter_mv_pref){
2465             mb_mode=OC_MODE_INTER_MV;
2466           }
2467         }
2468         else{
2469           oc_cost_inter_nomv(_enc,modes+OC_MODE_INTER_NOMV,mbi,
2470            OC_MODE_INTER_NOMV,_enc->pipe.fr+0,_enc->pipe.qs+0,
2471            skip_ssd,rd_scale);
2472           oc_cost_intra(_enc,modes+OC_MODE_INTRA,mbi,
2473            _enc->pipe.fr+0,_enc->pipe.qs+0,intra_satd,skip_ssd,rd_scale);
2474           oc_cost_inter_nomv(_enc,modes+OC_MODE_GOLDEN_NOMV,mbi,
2475            OC_MODE_GOLDEN_NOMV,_enc->pipe.fr+0,_enc->pipe.qs+0,
2476            skip_ssd,rd_scale);
2477           mb_mode=OC_MODE_INTER_NOMV;
2478           if(modes[OC_MODE_INTRA].cost<modes[OC_MODE_INTER_NOMV].cost){
2479             mb_mode=OC_MODE_INTRA;
2480           }
2481           if(modes[OC_MODE_GOLDEN_NOMV].cost<modes[mb_mode].cost){
2482             mb_mode=OC_MODE_GOLDEN_NOMV;
2483           }
2484           mb_mv_bits_0=mb_gmv_bits_0=0;
2485         }
2486         mb_modes[mbi]=mb_mode;
2487         /*Propagate the MVs to the luma blocks.*/
2488         if(mb_mode!=OC_MODE_INTER_MV_FOUR){
2489           switch(mb_mode){
2490             case OC_MODE_INTER_MV:{
2491               mv=embs[mbi].analysis_mv[0][OC_FRAME_PREV];
2492             }break;
2493             case OC_MODE_INTER_MV_LAST:mv=last_mv;break;
2494             case OC_MODE_INTER_MV_LAST2:mv=prior_mv;break;
2495             case OC_MODE_GOLDEN_MV:{
2496               mv=embs[mbi].analysis_mv[0][OC_FRAME_GOLD];
2497             }break;
2498           }
2499           for(bi=0;bi<4;bi++){
2500             fragi=mb_maps[mbi][0][bi];
2501             frag_mvs[fragi]=mv;
2502           }
2503         }
2504         for(bi=0;bi<4;bi++){
2505           fragi=sb_maps[mbi>>2][mbi&3][bi];
2506           frags[fragi].qii=modes[mb_mode].qii[bi];
2507         }
2508         if(oc_enc_mb_transform_quantize_inter_luma(_enc,&_enc->pipe,mbi,
2509          modes[mb_mode].overhead>>OC_BIT_SCALE,rd_scale,rd_iscale)>0){
2510           int orig_mb_mode;
2511           orig_mb_mode=mb_mode;
2512           mb_mode=mb_modes[mbi];
2513           refi=OC_FRAME_FOR_MODE(mb_mode);
2514           switch(mb_mode){
2515             case OC_MODE_INTER_MV:{
2516               prior_mv=last_mv;
2517               /*If we're backing out from 4MV, find the MV we're actually
2518                  using.*/
2519               if(orig_mb_mode==OC_MODE_INTER_MV_FOUR){
2520                 for(bi=0;;bi++){
2521                   fragi=mb_maps[mbi][0][bi];
2522                   if(frags[fragi].coded){
2523                     mv=last_mv=frag_mvs[fragi];
2524                     break;
2525                   }
2526                 }
2527                 mb_mv_bits_0=OC_MV_BITS[0][OC_MV_X(mv)+31]
2528                  +OC_MV_BITS[0][OC_MV_Y(mv)+31];
2529               }
2530               /*Otherwise we used the original analysis MV.*/
2531               else last_mv=embs[mbi].analysis_mv[0][OC_FRAME_PREV];
2532               _enc->mv_bits[0]+=mb_mv_bits_0;
2533               _enc->mv_bits[1]+=12;
2534             }break;
2535             case OC_MODE_INTER_MV_LAST2:{
2536               oc_mv tmp_mv;
2537               tmp_mv=prior_mv;
2538               prior_mv=last_mv;
2539               last_mv=tmp_mv;
2540             }break;
2541             case OC_MODE_GOLDEN_MV:{
2542               _enc->mv_bits[0]+=mb_gmv_bits_0;
2543               _enc->mv_bits[1]+=12;
2544             }break;
2545             case OC_MODE_INTER_MV_FOUR:{
2546               oc_mv lbmvs[4];
2547               oc_mv cbmvs[4];
2548               prior_mv=last_mv;
2549               for(bi=0;bi<4;bi++){
2550                 fragi=mb_maps[mbi][0][bi];
2551                 if(frags[fragi].coded){
2552                   lbmvs[bi]=last_mv=frag_mvs[fragi];
2553                   _enc->mv_bits[0]+=OC_MV_BITS[0][OC_MV_X(last_mv)+31]
2554                    +OC_MV_BITS[0][OC_MV_Y(last_mv)+31];
2555                   _enc->mv_bits[1]+=12;
2556                 }
2557                 /*Replace the block MVs for not-coded blocks with (0,0).*/
2558                 else lbmvs[bi]=0;
2559               }
2560               (*set_chroma_mvs)(cbmvs,lbmvs);
2561               for(mapii=4;mapii<nmap_idxs;mapii++){
2562                 mapi=map_idxs[mapii];
2563                 pli=mapi>>2;
2564                 bi=mapi&3;
2565                 fragi=mb_maps[mbi][pli][bi];
2566                 frags[fragi].qii=modes[OC_MODE_INTER_MV_FOUR].qii[mapii];
2567                 frags[fragi].refi=refi;
2568                 frags[fragi].mb_mode=mb_mode;
2569                 frag_mvs[fragi]=cbmvs[bi];
2570               }
2571             }break;
2572           }
2573           coded_mbis[ncoded_mbis++]=mbi;
2574           oc_mode_scheme_chooser_update(&_enc->chooser,mb_mode);
2575           interbits+=modes[mb_mode].rate+modes[mb_mode].overhead;
2576         }
2577         else{
2578           *(uncoded_mbis-++nuncoded_mbis)=mbi;
2579           mb_mode=OC_MODE_INTER_NOMV;
2580           refi=OC_FRAME_PREV;
2581           mv=0;
2582         }
2583         /*Propagate final MB mode and MVs to the chroma blocks.
2584           This has already been done for 4MV mode, since it requires individual
2585            block motion vectors.*/
2586         if(mb_mode!=OC_MODE_INTER_MV_FOUR){
2587           for(mapii=4;mapii<nmap_idxs;mapii++){
2588             mapi=map_idxs[mapii];
2589             pli=mapi>>2;
2590             bi=mapi&3;
2591             fragi=mb_maps[mbi][pli][bi];
2592             /*If we switched from 4MV mode to INTER_MV mode, then the qii
2593                values won't have been chosen with the right MV, but it's
2594                probaby not worth re-estimating them.*/
2595             frags[fragi].qii=modes[mb_mode].qii[mapii];
2596             frags[fragi].refi=refi;
2597             frags[fragi].mb_mode=mb_mode;
2598             frag_mvs[fragi]=mv;
2599           }
2600         }
2601         /*Save masking scale factors for chroma blocks.*/
2602         for(mapii=4;mapii<(nmap_idxs-4>>1)+4;mapii++){
2603           mapi=map_idxs[mapii];
2604           bi=mapi&3;
2605           fragi=mb_maps[mbi][1][bi];
2606           mcu_rd_scale[fragi-cfroffset]=(ogg_uint16_t)rd_scale[4];
2607           mcu_rd_iscale[fragi-cfroffset]=(ogg_uint16_t)rd_iscale[4];
2608         }
2609       }
2610       oc_fr_state_flush_sb(_enc->pipe.fr+0);
2611       sb_flags[sbi].coded_fully=_enc->pipe.fr[0].sb_full;
2612       sb_flags[sbi].coded_partially=_enc->pipe.fr[0].sb_partial;
2613     }
2614     oc_enc_pipeline_finish_mcu_plane(_enc,&_enc->pipe,0,notstart,notdone);
2615     /*Code chroma planes.*/
2616     for(pli=1;pli<3;pli++){
2617       oc_enc_sb_transform_quantize_inter_chroma(_enc,&_enc->pipe,
2618        pli,_enc->pipe.sbi0[pli],_enc->pipe.sbi_end[pli]);
2619       oc_enc_pipeline_finish_mcu_plane(_enc,&_enc->pipe,pli,notstart,notdone);
2620     }
2621     notstart=1;
2622   }
2623   /*Update the average block activity and MB luma score for the frame.
2624     We could use a Bessel follower here, but fast reaction is probably almost
2625      always best.*/
2626   _enc->activity_avg=OC_MAXI(OC_ACTIVITY_AVG_MIN,
2627    (unsigned)((activity_sum+(_enc->state.fplanes[0].nfrags>>1))/
2628    _enc->state.fplanes[0].nfrags));
2629   _enc->luma_avg=(unsigned)((luma_sum+(_enc->state.nmbs>>1))/_enc->state.nmbs);
2630   /*Finish filling in the reference frame borders.*/
2631   refi=_enc->state.ref_frame_idx[OC_FRAME_SELF];
2632   for(pli=0;pli<3;pli++)oc_state_borders_fill_caps(&_enc->state,refi,pli);
2633   /*Finish adding flagging overhead costs to inter bit counts to determine if
2634      we should have coded a key frame instead.*/
2635   if(_allow_keyframe){
2636     /*Technically the chroma plane counts are over-estimations, because they
2637        don't account for continuing runs from the luma planes, but the
2638        inaccuracy is small.
2639       We don't need to add the luma plane coding flag costs, because they are
2640        already included in the MB rate estimates.*/
2641     for(pli=1;pli<3;pli++)interbits+=_enc->pipe.fr[pli].bits<<OC_BIT_SCALE;
2642     if(interbits>intrabits)return 1;
2643   }
2644   _enc->ncoded_mbis=ncoded_mbis;
2645   /*Compact the coded fragment list.*/
2646   {
2647     ptrdiff_t ncoded_fragis;
2648     ncoded_fragis=_enc->state.ncoded_fragis[0];
2649     for(pli=1;pli<3;pli++){
2650       memmove(_enc->state.coded_fragis+ncoded_fragis,
2651        _enc->state.coded_fragis+_enc->state.fplanes[pli].froffset,
2652        _enc->state.ncoded_fragis[pli]*sizeof(*_enc->state.coded_fragis));
2653       ncoded_fragis+=_enc->state.ncoded_fragis[pli];
2654     }
2655     _enc->state.ntotal_coded_fragis=ncoded_fragis;
2656   }
2657   return 0;
2658 }