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