[svn] / trunk / xvidcore / src / utils / mbtransquant.c Repository:
ViewVC logotype

Diff of /trunk/xvidcore/src/utils/mbtransquant.c

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 82, Fri Mar 29 00:38:29 2002 UTC revision 1663, Sat Dec 10 05:20:35 2005 UTC
# Line 1  Line 1 
1   /******************************************************************************  /*****************************************************************************
2    *                                                                            *   *
3    *  This file is part of XviD, a free MPEG-4 video encoder/decoder            *   *  XVID MPEG-4 VIDEO CODEC
4    *                                                                            *   *  - MB Transfert/Quantization functions -
5    *  XviD is an implementation of a part of one or more MPEG-4 Video tools     *   *
6    *  as specified in ISO/IEC 14496-2 standard.  Those intending to use this    *   *  Copyright(C) 2001-2003  Peter Ross <pross@xvid.org>
7    *  software module in hardware or software products are advised that its     *   *               2001-2003  Michael Militzer <isibaar@xvid.org>
8    *  use may infringe existing patents or copyrights, and any such use         *   *               2003       Edouard Gomez <ed.gomez@free.fr>
9    *  would be at such party's own risk.  The original developer of this        *   *
10    *  software module and his/her company, and subsequent editors and their     *   *  This program is free software ; you can redistribute it and/or modify
11    *  companies, will have no liability for use of this software or             *   *  it under the terms of the GNU General Public License as published by
12    *  modifications or derivatives thereof.                                     *   *  the Free Software Foundation ; either version 2 of the License, or
13    *                                                                            *   *  (at your option) any later version.
14    *  XviD is free software; you can redistribute it and/or modify it           *   *
15    *  under the terms of the GNU General Public License as published by         *   *  This program is distributed in the hope that it will be useful,
16    *  the Free Software Foundation; either version 2 of the License, or         *   *  but WITHOUT ANY WARRANTY ; without even the implied warranty of
17    *  (at your option) any later version.                                       *   *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
18    *                                                                            *   *  GNU General Public License for more details.
19    *  XviD is distributed in the hope that it will be useful, but               *   *
20    *  WITHOUT ANY WARRANTY; without even the implied warranty of                *   *  You should have received a copy of the GNU General Public License
21    *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the             *   *  along with this program ; if not, write to the Free Software
22    *  GNU General Public License for more details.                              *   *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
23    *                                                                            *   *
24    *  You should have received a copy of the GNU General Public License         *   * $Id: mbtransquant.c,v 1.31 2005-12-10 05:20:35 syskin Exp $
25    *  along with this program; if not, write to the Free Software               *   *
26    *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA  *   ****************************************************************************/
   *                                                                            *  
   ******************************************************************************/  
   
  /******************************************************************************  
   *                                                                            *  
   *  mbtransquant.c                                                            *  
   *                                                                            *  
   *  Copyright (C) 2001 - Peter Ross <pross@cs.rmit.edu.au>                    *  
   *  Copyright (C) 2001 - Michael Militzer <isibaar@xvid.org>                  *  
   *                                                                            *  
   *  For more information visit the XviD homepage: http://www.xvid.org         *  
   *                                                                            *  
   ******************************************************************************/  
   
  /******************************************************************************  
   *                                                                            *  
   *  Revision history:                                                         *  
   *                                                                            *  
   *  29.03.2002 interlacing speedup - used transfer strides instead of  
   *             manual field-to-frame conversion  
   *  26.03.2002 interlacing support - moved transfers outside loops  
   *  22.12.2001 get_dc_scaler() moved to common.h  
   *  19.11.2001 introduced coefficient thresholding (Isibaar)                  *  
   *  17.11.2001 initial version                                                *  
   *                                                                            *  
   ******************************************************************************/  
27    
28    #include <stdio.h>
29    #include <stdlib.h>
30  #include <string.h>  #include <string.h>
31    
32  #include "../portab.h"  #include "../portab.h"
# Line 59  Line 35 
35  #include "../global.h"  #include "../global.h"
36  #include "mem_transfer.h"  #include "mem_transfer.h"
37  #include "timer.h"  #include "timer.h"
38    #include "../bitstream/mbcoding.h"
39    #include "../bitstream/zigzag.h"
40  #include "../dct/fdct.h"  #include "../dct/fdct.h"
41  #include "../dct/idct.h"  #include "../dct/idct.h"
42  #include "../quant/quant_mpeg4.h"  #include "../quant/quant.h"
 #include "../quant/quant_h263.h"  
43  #include "../encoder.h"  #include "../encoder.h"
44    
45  #define MIN(X, Y) ((X)<(Y)?(X):(Y))  #include  "../quant/quant_matrix.h"
 #define MAX(X, Y) ((X)>(Y)?(X):(Y))  
46    
47  #define TOOSMALL_LIMIT 1 /* skip blocks having a coefficient sum below this value */  MBFIELDTEST_PTR MBFieldTest;
48    
49  /* this isnt pretty, but its better than 20 ifdefs */  /*
50     * Skip blocks having a coefficient sum below this value. This value will be
51  void MBTransQuantIntra(const MBParam *pParam,   * corrected according to the MB quantizer to avoid artifacts for quant==1
52                         MACROBLOCK * pMB,   */
53                         const uint32_t x_pos,  #define PVOP_TOOSMALL_LIMIT 1
54                         const uint32_t y_pos,  #define BVOP_TOOSMALL_LIMIT 3
                        int16_t data[6*64],  
                        int16_t qcoeff[6*64],  
                        IMAGE * const pCurrent)  
55    
56    /*****************************************************************************
57     * Local functions
58     ****************************************************************************/
59    
60    /* permute block and return field dct choice */
61    static __inline uint32_t
62    MBDecideFieldDCT(int16_t data[6 * 64])
63  {  {
64            uint32_t field = MBFieldTest(data);
65    
66          uint32_t stride = pParam->edged_width;          if (field)
67          uint32_t stride2 = stride / 2;                  MBFrameToField(data);
         uint32_t next_block = stride * 8;  
         uint32_t i;  
         uint32_t iQuant = pParam->quant;  
         uint8_t *pY_Cur, *pU_Cur, *pV_Cur;  
   
         pY_Cur = pCurrent->y + (y_pos << 4) * stride + (x_pos << 4);  
         pU_Cur = pCurrent->u + (y_pos << 3) * stride2 + (x_pos << 3);  
         pV_Cur = pCurrent->v + (y_pos << 3) * stride2 + (x_pos << 3);  
68    
69          start_timer();          return field;
70          transfer_8to16copy(&data[0*64], pY_Cur,                                 stride);  }
         transfer_8to16copy(&data[1*64], pY_Cur + 8,                             stride);  
         transfer_8to16copy(&data[2*64], pY_Cur + next_block,    stride);  
         transfer_8to16copy(&data[3*64], pY_Cur + next_block + 8,stride);  
         transfer_8to16copy(&data[4*64], pU_Cur,                                 stride2);  
         transfer_8to16copy(&data[5*64], pV_Cur,                                 stride2);  
         stop_transfer_timer();  
71    
72    /* Performs Forward DCT on all blocks */
73    static __inline void
74    MBfDCT(const MBParam * const pParam,
75               const FRAMEINFO * const frame,
76               MACROBLOCK * const pMB,
77               uint32_t x_pos,
78               uint32_t y_pos,
79               int16_t data[6 * 64])
80    {
81            /* Handles interlacing */
82          start_timer();          start_timer();
83          pMB->field_dct = 0;          pMB->field_dct = 0;
84          if (pParam->global_flags & XVID_INTERLACING)          if ((frame->vol_flags & XVID_VOL_INTERLACING) &&
85          {                  (x_pos>0) && (x_pos<pParam->mb_width-1) &&
86                    (y_pos>0) && (y_pos<pParam->mb_height-1)) {
87                  pMB->field_dct = MBDecideFieldDCT(data);                  pMB->field_dct = MBDecideFieldDCT(data);
88          }          }
89          stop_interlacing_timer();          stop_interlacing_timer();
90    
91          for(i = 0; i < 6; i++)          /* Perform DCT */
         {  
                 uint32_t iDcScaler = get_dc_scaler(iQuant, i < 4);  
   
92                  start_timer();                  start_timer();
93                  fdct(&data[i*64]);          fdct((short * const)&data[0 * 64]);
94            fdct((short * const)&data[1 * 64]);
95            fdct((short * const)&data[2 * 64]);
96            fdct((short * const)&data[3 * 64]);
97            fdct((short * const)&data[4 * 64]);
98            fdct((short * const)&data[5 * 64]);
99                  stop_dct_timer();                  stop_dct_timer();
100    }
101    
102                  if (pParam->quant_type == H263_QUANT)  /* Performs Inverse DCT on all blocks */
103    static __inline void
104    MBiDCT(int16_t data[6 * 64],
105               const uint8_t cbp)
106                  {                  {
107                          start_timer();                          start_timer();
108                          quant_intra(&qcoeff[i*64], &data[i*64], iQuant, iDcScaler);          if(cbp & (1 << (5 - 0))) idct((short * const)&data[0 * 64]);
109                          stop_quant_timer();          if(cbp & (1 << (5 - 1))) idct((short * const)&data[1 * 64]);
110            if(cbp & (1 << (5 - 2))) idct((short * const)&data[2 * 64]);
111                          start_timer();          if(cbp & (1 << (5 - 3))) idct((short * const)&data[3 * 64]);
112                          dequant_intra(&data[i*64], &qcoeff[i*64], iQuant, iDcScaler);          if(cbp & (1 << (5 - 4))) idct((short * const)&data[4 * 64]);
113                          stop_iquant_timer();          if(cbp & (1 << (5 - 5))) idct((short * const)&data[5 * 64]);
114            stop_idct_timer();
115                  }                  }
116                  else  
117    /* Quantize all blocks -- Intra mode */
118    static __inline void
119    MBQuantIntra(const MBParam * pParam,
120                             const FRAMEINFO * const frame,
121                             const MACROBLOCK * pMB,
122                             int16_t qcoeff[6 * 64],
123                             int16_t data[6*64])
124                  {                  {
125            int mpeg;
126            int scaler_lum, scaler_chr;
127    
128            quant_intraFuncPtr const quant[2] =
129                    {
130                            quant_h263_intra,
131                            quant_mpeg_intra
132                    };
133    
134            mpeg = !!(pParam->vol_flags & XVID_VOL_MPEGQUANT);
135            scaler_lum = get_dc_scaler(pMB->quant, 1);
136            scaler_chr = get_dc_scaler(pMB->quant, 0);
137    
138            /* Quantize the block */
139                          start_timer();                          start_timer();
140                          quant4_intra(&qcoeff[i*64], &data[i*64], iQuant, iDcScaler);          quant[mpeg](&data[0 * 64], &qcoeff[0 * 64], pMB->quant, scaler_lum, pParam->mpeg_quant_matrices);
141            quant[mpeg](&data[1 * 64], &qcoeff[1 * 64], pMB->quant, scaler_lum, pParam->mpeg_quant_matrices);
142            quant[mpeg](&data[2 * 64], &qcoeff[2 * 64], pMB->quant, scaler_lum, pParam->mpeg_quant_matrices);
143            quant[mpeg](&data[3 * 64], &qcoeff[3 * 64], pMB->quant, scaler_lum, pParam->mpeg_quant_matrices);
144            quant[mpeg](&data[4 * 64], &qcoeff[4 * 64], pMB->quant, scaler_chr, pParam->mpeg_quant_matrices);
145            quant[mpeg](&data[5 * 64], &qcoeff[5 * 64], pMB->quant, scaler_chr, pParam->mpeg_quant_matrices);
146                          stop_quant_timer();                          stop_quant_timer();
147    }
148    
149    /* DeQuantize all blocks -- Intra mode */
150    static __inline void
151    MBDeQuantIntra(const MBParam * pParam,
152                               const int iQuant,
153                               int16_t qcoeff[6 * 64],
154                               int16_t data[6*64])
155    {
156            int mpeg;
157            int scaler_lum, scaler_chr;
158    
159            quant_intraFuncPtr const dequant[2] =
160                    {
161                            dequant_h263_intra,
162                            dequant_mpeg_intra
163                    };
164    
165            mpeg = !!(pParam->vol_flags & XVID_VOL_MPEGQUANT);
166            scaler_lum = get_dc_scaler(iQuant, 1);
167            scaler_chr = get_dc_scaler(iQuant, 0);
168    
169                          start_timer();                          start_timer();
170                          dequant4_intra(&data[i*64], &qcoeff[i*64], iQuant, iDcScaler);          dequant[mpeg](&qcoeff[0 * 64], &data[0 * 64], iQuant, scaler_lum, pParam->mpeg_quant_matrices);
171            dequant[mpeg](&qcoeff[1 * 64], &data[1 * 64], iQuant, scaler_lum, pParam->mpeg_quant_matrices);
172            dequant[mpeg](&qcoeff[2 * 64], &data[2 * 64], iQuant, scaler_lum, pParam->mpeg_quant_matrices);
173            dequant[mpeg](&qcoeff[3 * 64], &data[3 * 64], iQuant, scaler_lum, pParam->mpeg_quant_matrices);
174            dequant[mpeg](&qcoeff[4 * 64], &data[4 * 64], iQuant, scaler_chr, pParam->mpeg_quant_matrices);
175            dequant[mpeg](&qcoeff[5 * 64], &data[5 * 64], iQuant, scaler_chr, pParam->mpeg_quant_matrices);
176                          stop_iquant_timer();                          stop_iquant_timer();
177                  }                  }
178    
179    static int
180    dct_quantize_trellis_c(int16_t *const Out,
181                                               const int16_t *const In,
182                                               int Q,
183                                               const uint16_t * const Zigzag,
184                                               const uint16_t * const QuantMatrix,
185                                               int Non_Zero,
186                                               int Sum,
187                                               int Lambda_Mod);
188    
189    /* Quantize all blocks -- Inter mode */
190    static __inline uint8_t
191    MBQuantInter(const MBParam * pParam,
192                             const FRAMEINFO * const frame,
193                             const MACROBLOCK * pMB,
194                             int16_t data[6 * 64],
195                             int16_t qcoeff[6 * 64],
196                             int bvop,
197                             int limit)
198    {
199    
200            int i;
201            uint8_t cbp = 0;
202            int sum;
203            int code_block, mpeg;
204    
205            quant_interFuncPtr const quant[2] =
206                    {
207                            quant_h263_inter,
208                            quant_mpeg_inter
209                    };
210    
211            mpeg = !!(pParam->vol_flags & XVID_VOL_MPEGQUANT);
212    
213            for (i = 0; i < 6; i++) {
214    
215                    /* Quantize the block */
216                  start_timer();                  start_timer();
                 idct(&data[i*64]);  
                 stop_idct_timer();  
         }  
217    
218          if (pMB->field_dct)                  sum = quant[mpeg](&qcoeff[i*64], &data[i*64], pMB->quant, pParam->mpeg_quant_matrices);
219    
220                    if(sum && (pMB->quant > 2) && (frame->vop_flags & XVID_VOP_TRELLISQUANT)) {
221                            const uint16_t *matrix;
222                            const static uint16_t h263matrix[] =
223          {          {
224                  next_block = stride;                                          16, 16, 16, 16, 16, 16, 16, 16,
225                  stride *= 2;                                          16, 16, 16, 16, 16, 16, 16, 16,
226                                            16, 16, 16, 16, 16, 16, 16, 16,
227                                            16, 16, 16, 16, 16, 16, 16, 16,
228                                            16, 16, 16, 16, 16, 16, 16, 16,
229                                            16, 16, 16, 16, 16, 16, 16, 16,
230                                            16, 16, 16, 16, 16, 16, 16, 16,
231                                            16, 16, 16, 16, 16, 16, 16, 16
232                                    };
233    
234                            matrix = (mpeg)?get_inter_matrix(pParam->mpeg_quant_matrices):h263matrix;
235                            sum = dct_quantize_trellis_c(&qcoeff[i*64], &data[i*64],
236                                                                                     pMB->quant, &scan_tables[0][0],
237                                                                                     matrix,
238                                                                                     63,
239                                                                                     sum,
240                                                                                     pMB->lambda[i]);
241          }          }
242                    stop_quant_timer();
243    
244          start_timer();                  /*
245          transfer_16to8copy(pY_Cur,                  &data[0*64], stride);                   * We code the block if the sum is higher than the limit and if the first
246          transfer_16to8copy(pY_Cur + 8,              &data[1*64], stride);                   * two AC coefficients in zig zag order are not zero.
247          transfer_16to8copy(pY_Cur + next_block,     &data[2*64], stride);                   */
248          transfer_16to8copy(pY_Cur + next_block + 8, &data[3*64], stride);                  code_block = 0;
249          transfer_16to8copy(pU_Cur,                  &data[4*64], stride2);                  if ((sum >= limit) || (qcoeff[i*64+1] != 0) || (qcoeff[i*64+8] != 0)) {
250          transfer_16to8copy(pV_Cur,                  &data[5*64], stride2);                          code_block = 1;
251          stop_transfer_timer();                  } else {
252    
253                            if (bvop && (pMB->mode == MODE_DIRECT || pMB->mode == MODE_DIRECT_NO4V)) {
254                                    /* dark blocks prevention for direct mode */
255                                    if ((qcoeff[i*64] < -1) || (qcoeff[i*64] > 0))
256                                            code_block = 1;
257                            } else {
258                                    /* not direct mode */
259                                    if (qcoeff[i*64] != 0)
260                                            code_block = 1;
261                            }
262                    }
263    
264                    /* Set the corresponding cbp bit */
265                    cbp |= code_block << (5 - i);
266  }  }
267    
268            return(cbp);
269    }
270    
271  uint8_t MBTransQuantInter(const MBParam *pParam,  /* DeQuantize all blocks -- Inter mode */
272                            MACROBLOCK * pMB,  static __inline void
273                            const uint32_t x_pos, const uint32_t y_pos,  MBDeQuantInter(const MBParam * pParam,
274                               const int iQuant,
275                            int16_t data[6*64],                            int16_t data[6*64],
276                            int16_t qcoeff[6*64],                            int16_t qcoeff[6*64],
277                            IMAGE * const pCurrent)                             const uint8_t cbp)
278    {
279            int mpeg;
280    
281            quant_interFuncPtr const dequant[2] =
282  {  {
283                            dequant_h263_inter,
284                            dequant_mpeg_inter
285                    };
286    
287            mpeg = !!(pParam->vol_flags & XVID_VOL_MPEGQUANT);
288    
289            start_timer();
290            if(cbp & (1 << (5 - 0))) dequant[mpeg](&data[0 * 64], &qcoeff[0 * 64], iQuant, pParam->mpeg_quant_matrices);
291            if(cbp & (1 << (5 - 1))) dequant[mpeg](&data[1 * 64], &qcoeff[1 * 64], iQuant, pParam->mpeg_quant_matrices);
292            if(cbp & (1 << (5 - 2))) dequant[mpeg](&data[2 * 64], &qcoeff[2 * 64], iQuant, pParam->mpeg_quant_matrices);
293            if(cbp & (1 << (5 - 3))) dequant[mpeg](&data[3 * 64], &qcoeff[3 * 64], iQuant, pParam->mpeg_quant_matrices);
294            if(cbp & (1 << (5 - 4))) dequant[mpeg](&data[4 * 64], &qcoeff[4 * 64], iQuant, pParam->mpeg_quant_matrices);
295            if(cbp & (1 << (5 - 5))) dequant[mpeg](&data[5 * 64], &qcoeff[5 * 64], iQuant, pParam->mpeg_quant_matrices);
296            stop_iquant_timer();
297    }
298    
299    typedef void (transfer_operation_8to16_t) (int16_t *Dst, const uint8_t *Src, int BpS);
300    typedef void (transfer_operation_16to8_t) (uint8_t *Dst, const int16_t *Src, int BpS);
301    
302    
303    static __inline void
304    MBTrans8to16(const MBParam * const pParam,
305                             const FRAMEINFO * const frame,
306                             const MACROBLOCK * const pMB,
307                             const uint32_t x_pos,
308                             const uint32_t y_pos,
309                             int16_t data[6 * 64])
310    {
311          uint32_t stride = pParam->edged_width;          uint32_t stride = pParam->edged_width;
312          uint32_t stride2 = stride / 2;          uint32_t stride2 = stride / 2;
313          uint32_t next_block = stride * 8;          uint32_t next_block = stride * 8;
         uint32_t i;  
         uint32_t iQuant = pParam->quant;  
314          uint8_t *pY_Cur, *pU_Cur, *pV_Cur;          uint8_t *pY_Cur, *pU_Cur, *pV_Cur;
315          uint8_t cbp = 0;          const IMAGE * const pCurrent = &frame->image;
         uint32_t sum;  
316    
317            /* Image pointers */
318          pY_Cur = pCurrent->y + (y_pos << 4) * stride + (x_pos << 4);          pY_Cur = pCurrent->y + (y_pos << 4) * stride + (x_pos << 4);
319          pU_Cur = pCurrent->u + (y_pos << 3) * stride2 + (x_pos << 3);          pU_Cur = pCurrent->u + (y_pos << 3) * stride2 + (x_pos << 3);
320          pV_Cur = pCurrent->v + (y_pos << 3) * stride2 + (x_pos << 3);          pV_Cur = pCurrent->v + (y_pos << 3) * stride2 + (x_pos << 3);
321    
322            /* Do the transfer */
323          start_timer();          start_timer();
324          pMB->field_dct = 0;          transfer_8to16copy(&data[0 * 64], pY_Cur, stride);
325          if (pParam->global_flags & XVID_INTERLACING)          transfer_8to16copy(&data[1 * 64], pY_Cur + 8, stride);
326          {          transfer_8to16copy(&data[2 * 64], pY_Cur + next_block, stride);
327                  pMB->field_dct = MBDecideFieldDCT(data);          transfer_8to16copy(&data[3 * 64], pY_Cur + next_block + 8, stride);
328            transfer_8to16copy(&data[4 * 64], pU_Cur, stride2);
329            transfer_8to16copy(&data[5 * 64], pV_Cur, stride2);
330            stop_transfer_timer();
331          }          }
         stop_interlacing_timer();  
332    
333          for(i = 0; i < 6; i++)  static __inline void
334    MBTrans16to8(const MBParam * const pParam,
335                             const FRAMEINFO * const frame,
336                             const MACROBLOCK * const pMB,
337                             const uint32_t x_pos,
338                             const uint32_t y_pos,
339                             int16_t data[6 * 64],
340                             const uint32_t add, /* Must be 1 or 0 */
341                             const uint8_t cbp)
342          {          {
343                  /*          uint8_t *pY_Cur, *pU_Cur, *pV_Cur;
344                   *  no need to transfer 8->16-bit          uint32_t stride = pParam->edged_width;
345                   * (this is performed already in motion compensation)          uint32_t stride2 = stride / 2;
346                   */          uint32_t next_block = stride * 8;
347                  start_timer();          const IMAGE * const pCurrent = &frame->image;
                 fdct(&data[i*64]);  
                 stop_dct_timer();  
348    
349                  if (pParam->quant_type == 0)          /* Array of function pointers, indexed by [add] */
350            transfer_operation_16to8_t  * const functions[2] =
351                  {                  {
352                          start_timer();                          (transfer_operation_16to8_t*)transfer_16to8copy,
353                          sum = quant_inter(&qcoeff[i*64], &data[i*64], iQuant);                          (transfer_operation_16to8_t*)transfer_16to8add,
354                          stop_quant_timer();                  };
355                  }  
356                  else          transfer_operation_16to8_t *transfer_op = NULL;
357                  {  
358                          start_timer();          /* Image pointers */
359                          sum = quant4_inter(&qcoeff[i*64], &data[i*64], iQuant);          pY_Cur = pCurrent->y + (y_pos << 4) * stride  + (x_pos << 4);
360                          stop_quant_timer();          pU_Cur = pCurrent->u + (y_pos << 3) * stride2 + (x_pos << 3);
361            pV_Cur = pCurrent->v + (y_pos << 3) * stride2 + (x_pos << 3);
362    
363            if (pMB->field_dct) {
364                    next_block = stride;
365                    stride *= 2;
366                  }                  }
367    
368                  if(sum >= TOOSMALL_LIMIT) { // skip block ?          /* Operation function */
369            transfer_op = functions[add];
370    
371                          if (pParam->quant_type == H263_QUANT)          /* Do the operation */
                         {  
372                                  start_timer();                                  start_timer();
373                                  dequant_inter(&data[i*64], &qcoeff[i*64], iQuant);          if (cbp&32) transfer_op(pY_Cur,                                         &data[0 * 64], stride);
374                                  stop_iquant_timer();          if (cbp&16) transfer_op(pY_Cur + 8,                                     &data[1 * 64], stride);
375            if (cbp& 8) transfer_op(pY_Cur + next_block,            &data[2 * 64], stride);
376            if (cbp& 4) transfer_op(pY_Cur + next_block + 8,        &data[3 * 64], stride);
377            if (cbp& 2) transfer_op(pU_Cur,                                         &data[4 * 64], stride2);
378            if (cbp& 1) transfer_op(pV_Cur,                                         &data[5 * 64], stride2);
379            stop_transfer_timer();
380                          }                          }
381                          else  
382    /*****************************************************************************
383     * Module functions
384     ****************************************************************************/
385    
386    void
387    MBTransQuantIntra(const MBParam * const pParam,
388                                      const FRAMEINFO * const frame,
389                                      MACROBLOCK * const pMB,
390                                      const uint32_t x_pos,
391                                      const uint32_t y_pos,
392                                      int16_t data[6 * 64],
393                                      int16_t qcoeff[6 * 64])
394                          {                          {
                                 start_timer();  
                                 dequant4_inter(&data[i*64], &qcoeff[i*64], iQuant);  
                                 stop_iquant_timer();  
                         }  
395    
396                          cbp |= 1 << (5 - i);          /* Transfer data */
397            MBTrans8to16(pParam, frame, pMB, x_pos, y_pos, data);
398    
399                          start_timer();          /* Perform DCT (and field decision) */
400                          idct(&data[i*64]);          MBfDCT(pParam, frame, pMB, x_pos, y_pos, data);
401                          stop_idct_timer();  
402                  }          /* Quantize the block */
403            MBQuantIntra(pParam, frame, pMB, data, qcoeff);
404    
405            /* DeQuantize the block */
406            MBDeQuantIntra(pParam, pMB->quant, data, qcoeff);
407    
408            /* Perform inverse DCT*/
409            MBiDCT(data, 0x3F);
410    
411            /* Transfer back the data -- Don't add data */
412            MBTrans16to8(pParam, frame, pMB, x_pos, y_pos, data, 0, 0x3F);
413          }          }
414    
415          if (pMB->field_dct)  
416    uint8_t
417    MBTransQuantInter(const MBParam * const pParam,
418                                      const FRAMEINFO * const frame,
419                                      MACROBLOCK * const pMB,
420                                      const uint32_t x_pos,
421                                      const uint32_t y_pos,
422                                      int16_t data[6 * 64],
423                                      int16_t qcoeff[6 * 64])
424          {          {
425                  next_block = stride;          uint8_t cbp;
426                  stride *= 2;          uint32_t limit;
         }  
427    
428          start_timer();          /* There is no MBTrans8to16 for Inter block, that's done in motion compensation
429          if (cbp & 32)           * already */
                 transfer_16to8add(pY_Cur,                  &data[0*64], stride);  
         if (cbp & 16)  
                 transfer_16to8add(pY_Cur + 8,              &data[1*64], stride);  
         if (cbp & 8)  
                 transfer_16to8add(pY_Cur + next_block,     &data[2*64], stride);  
         if (cbp & 4)  
                 transfer_16to8add(pY_Cur + next_block + 8, &data[3*64], stride);  
         if (cbp & 2)  
                 transfer_16to8add(pU_Cur,                  &data[4*64], stride2);  
         if (cbp & 1)  
                 transfer_16to8add(pV_Cur,                  &data[5*64], stride2);  
         stop_transfer_timer();  
430    
431          return cbp;          /* Perform DCT (and field decision) */
432            MBfDCT(pParam, frame, pMB, x_pos, y_pos, data);
433    
434  }          /* Set the limit threshold */
435            limit = PVOP_TOOSMALL_LIMIT + ((pMB->quant == 1)? 1 : 0);
436    
437            if (frame->vop_flags & XVID_VOP_CARTOON)
438                    limit *= 3;
439    
440  /* if sum(diff between field lines) < sum(diff between frame lines), use field dct */          /* Quantize the block */
441            cbp = MBQuantInter(pParam, frame, pMB, data, qcoeff, 0, limit);
442    
443            /* DeQuantize the block */
444            MBDeQuantInter(pParam, pMB->quant, data, qcoeff, cbp);
445    
446  #define ABS(X) (X)<0 ? -(X) : (X)          /* Perform inverse DCT*/
447            MBiDCT(data, cbp);
448    
449  uint32_t MBDecideFieldDCT(int16_t data[6*64])          /* Transfer back the data -- Add the data */
450            MBTrans16to8(pParam, frame, pMB, x_pos, y_pos, data, 1, cbp);
451    
452            return(cbp);
453    }
454    
455    uint8_t
456    MBTransQuantInterBVOP(const MBParam * pParam,
457                                              FRAMEINFO * frame,
458                                              MACROBLOCK * pMB,
459                                              const uint32_t x_pos,
460                                              const uint32_t y_pos,
461                                              int16_t data[6 * 64],
462                                              int16_t qcoeff[6 * 64])
463  {  {
464            uint8_t cbp;
465            uint32_t limit;
466    
467            /* There is no MBTrans8to16 for Inter block, that's done in motion compensation
468             * already */
469    
470            /* Perform DCT (and field decision) */
471            MBfDCT(pParam, frame, pMB, x_pos, y_pos, data);
472    
473            /* Set the limit threshold */
474            limit = BVOP_TOOSMALL_LIMIT;
475    
476            if (frame->vop_flags & XVID_VOP_CARTOON)
477                    limit *= 2;
478    
479            /* Quantize the block */
480            cbp = MBQuantInter(pParam, frame, pMB, data, qcoeff, 1, limit);
481    
482            /*
483             * History comment:
484             * We don't have to DeQuant, iDCT and Transfer back data for B-frames.
485             *
486             * BUT some plugins require the rebuilt original frame to be passed so we
487             * have to take care of that here
488             */
489            if((pParam->plugin_flags & XVID_REQORIGINAL)) {
490    
491                    /* DeQuantize the block */
492                    MBDeQuantInter(pParam, pMB->quant, data, qcoeff, cbp);
493    
494                    /* Perform inverse DCT*/
495                    MBiDCT(data, cbp);
496    
497                    /* Transfer back the data -- Add the data */
498                    MBTrans16to8(pParam, frame, pMB, x_pos, y_pos, data, 1, cbp);
499            }
500    
501          const uint8_t blocks[] = {0*64, 0*64, 0*64, 0*64, 2*64, 2*64, 2*64, 2*64};          return(cbp);
502    }
503    
504    /* if sum(diff between field lines) < sum(diff between frame lines), use field dct */
505    uint32_t
506    MBFieldTest_c(int16_t data[6 * 64])
507    {
508            const uint8_t blocks[] =
509                    { 0 * 64, 0 * 64, 0 * 64, 0 * 64, 2 * 64, 2 * 64, 2 * 64, 2 * 64 };
510          const uint8_t lines[]  = {0, 16, 32, 48, 0, 16, 32, 48};          const uint8_t lines[]  = {0, 16, 32, 48, 0, 16, 32, 48};
511    
512          int frame = 0, field = 0;          int frame = 0, field = 0;
513          int i, j;          int i, j;
514    
515          for (i=0 ; i<7 ; ++i)          for (i = 0; i < 7; ++i) {
516          {                  for (j = 0; j < 8; ++j) {
517                  for (j=0 ; j<8 ; ++j)                          frame +=
518                  {                                  abs(data[0 * 64 + (i + 1) * 8 + j] - data[0 * 64 + i * 8 + j]);
519                          frame += ABS(data[0*64 + (i+1)*8 + j] - data[0*64 + i*8 + j]);                          frame +=
520                          frame += ABS(data[1*64 + (i+1)*8 + j] - data[1*64 + i*8 + j]);                                  abs(data[1 * 64 + (i + 1) * 8 + j] - data[1 * 64 + i * 8 + j]);
521                          frame += ABS(data[2*64 + (i+1)*8 + j] - data[2*64 + i*8 + j]);                          frame +=
522                          frame += ABS(data[3*64 + (i+1)*8 + j] - data[3*64 + i*8 + j]);                                  abs(data[2 * 64 + (i + 1) * 8 + j] - data[2 * 64 + i * 8 + j]);
523                            frame +=
524                                    abs(data[3 * 64 + (i + 1) * 8 + j] - data[3 * 64 + i * 8 + j]);
525    
526                          field += ABS(data[blocks[i+1] + lines[i+1] + j] -\                          field +=
527                                    abs(data[blocks[i + 1] + lines[i + 1] + j] -
528                                       data[blocks[i  ] + lines[i  ] + j]);                                       data[blocks[i  ] + lines[i  ] + j]);
529                          field += ABS(data[blocks[i+1] + lines[i+1] + 8 + j] -\                          field +=
530                                    abs(data[blocks[i + 1] + lines[i + 1] + 8 + j] -
531                                       data[blocks[i  ] + lines[i  ] + 8 + j]);                                       data[blocks[i  ] + lines[i  ] + 8 + j]);
532                          field += ABS(data[blocks[i+1] + 64 + lines[i+1] + j] -\                          field +=
533                                    abs(data[blocks[i + 1] + 64 + lines[i + 1] + j] -
534                                       data[blocks[i  ] + 64 + lines[i  ] + j]);                                       data[blocks[i  ] + 64 + lines[i  ] + j]);
535                          field += ABS(data[blocks[i+1] + 64 + lines[i+1] + 8 + j] -\                          field +=
536                                    abs(data[blocks[i + 1] + 64 + lines[i + 1] + 8 + j] -
537                                       data[blocks[i  ] + 64 + lines[i  ] + 8 + j]);                                       data[blocks[i  ] + 64 + lines[i  ] + 8 + j]);
538                  }                  }
539          }          }
540    
541          if (frame > field)          return (frame >= (field + 350));
         {  
                 MBFrameToField(data);  
         }  
   
         return (frame > field);  
542  }  }
543    
544    
# Line 311  Line 547 
547  #define MOVLINE(X,Y) memcpy(X, Y, sizeof(tmp))  #define MOVLINE(X,Y) memcpy(X, Y, sizeof(tmp))
548  #define LINE(X,Y)    &data[X*64 + Y*8]  #define LINE(X,Y)    &data[X*64 + Y*8]
549    
550  void MBFrameToField(int16_t data[6*64])  void
551    MBFrameToField(int16_t data[6 * 64])
552  {  {
553          int16_t tmp[8];          int16_t tmp[8];
554    
555          /* left blocks */          /* left blocks */
556    
557          // 1=2, 2=4, 4=8, 8=1          /* 1=2, 2=4, 4=8, 8=1 */
558          MOVLINE(tmp,            LINE(0,1));          MOVLINE(tmp,            LINE(0,1));
559          MOVLINE(LINE(0,1),      LINE(0,2));          MOVLINE(LINE(0,1),      LINE(0,2));
560          MOVLINE(LINE(0,2),      LINE(0,4));          MOVLINE(LINE(0,2),      LINE(0,4));
561          MOVLINE(LINE(0,4),      LINE(2,0));          MOVLINE(LINE(0,4),      LINE(2,0));
562          MOVLINE(LINE(2,0),      tmp);          MOVLINE(LINE(2,0),      tmp);
563    
564          // 3=6, 6=12, 12=9, 9=3          /* 3=6, 6=12, 12=9, 9=3 */
565          MOVLINE(tmp,            LINE(0,3));          MOVLINE(tmp,            LINE(0,3));
566          MOVLINE(LINE(0,3),      LINE(0,6));          MOVLINE(LINE(0,3),      LINE(0,6));
567          MOVLINE(LINE(0,6),      LINE(2,4));          MOVLINE(LINE(0,6),      LINE(2,4));
568          MOVLINE(LINE(2,4),      LINE(2,1));          MOVLINE(LINE(2,4),      LINE(2,1));
569          MOVLINE(LINE(2,1),      tmp);          MOVLINE(LINE(2,1),      tmp);
570    
571          // 5=10, 10=5          /* 5=10, 10=5 */
572          MOVLINE(tmp,            LINE(0,5));          MOVLINE(tmp,            LINE(0,5));
573          MOVLINE(LINE(0,5),      LINE(2,2));          MOVLINE(LINE(0,5),      LINE(2,2));
574          MOVLINE(LINE(2,2),      tmp);          MOVLINE(LINE(2,2),      tmp);
575    
576          // 7=14, 14=13, 13=11, 11=7          /* 7=14, 14=13, 13=11, 11=7 */
577          MOVLINE(tmp,            LINE(0,7));          MOVLINE(tmp,            LINE(0,7));
578          MOVLINE(LINE(0,7),      LINE(2,6));          MOVLINE(LINE(0,7),      LINE(2,6));
579          MOVLINE(LINE(2,6),      LINE(2,5));          MOVLINE(LINE(2,6),      LINE(2,5));
# Line 345  Line 582 
582    
583          /* right blocks */          /* right blocks */
584    
585          // 1=2, 2=4, 4=8, 8=1          /* 1=2, 2=4, 4=8, 8=1 */
586          MOVLINE(tmp,            LINE(1,1));          MOVLINE(tmp,            LINE(1,1));
587          MOVLINE(LINE(1,1),      LINE(1,2));          MOVLINE(LINE(1,1),      LINE(1,2));
588          MOVLINE(LINE(1,2),      LINE(1,4));          MOVLINE(LINE(1,2),      LINE(1,4));
589          MOVLINE(LINE(1,4),      LINE(3,0));          MOVLINE(LINE(1,4),      LINE(3,0));
590          MOVLINE(LINE(3,0),      tmp);          MOVLINE(LINE(3,0),      tmp);
591    
592          // 3=6, 6=12, 12=9, 9=3          /* 3=6, 6=12, 12=9, 9=3 */
593          MOVLINE(tmp,            LINE(1,3));          MOVLINE(tmp,            LINE(1,3));
594          MOVLINE(LINE(1,3),      LINE(1,6));          MOVLINE(LINE(1,3),      LINE(1,6));
595          MOVLINE(LINE(1,6),      LINE(3,4));          MOVLINE(LINE(1,6),      LINE(3,4));
596          MOVLINE(LINE(3,4),      LINE(3,1));          MOVLINE(LINE(3,4),      LINE(3,1));
597          MOVLINE(LINE(3,1),      tmp);          MOVLINE(LINE(3,1),      tmp);
598    
599          // 5=10, 10=5          /* 5=10, 10=5 */
600          MOVLINE(tmp,            LINE(1,5));          MOVLINE(tmp,            LINE(1,5));
601          MOVLINE(LINE(1,5),      LINE(3,2));          MOVLINE(LINE(1,5),      LINE(3,2));
602          MOVLINE(LINE(3,2),      tmp);          MOVLINE(LINE(3,2),      tmp);
603    
604          // 7=14, 14=13, 13=11, 11=7          /* 7=14, 14=13, 13=11, 11=7 */
605          MOVLINE(tmp,            LINE(1,7));          MOVLINE(tmp,            LINE(1,7));
606          MOVLINE(LINE(1,7),      LINE(3,6));          MOVLINE(LINE(1,7),      LINE(3,6));
607          MOVLINE(LINE(3,6),      LINE(3,5));          MOVLINE(LINE(3,6),      LINE(3,5));
608          MOVLINE(LINE(3,5),      LINE(3,3));          MOVLINE(LINE(3,5),      LINE(3,3));
609          MOVLINE(LINE(3,3),      tmp);          MOVLINE(LINE(3,3),      tmp);
610  }  }
611    
612    /*****************************************************************************
613     *               Trellis based R-D optimal quantization
614     *
615     *   Trellis Quant code (C) 2003 Pascal Massimino skal(at)planet-d.net
616     *
617     ****************************************************************************/
618    
619    /*----------------------------------------------------------------------------
620     *
621     *        Trellis-Based quantization
622     *
623     * So far I understand this paper:
624     *
625     *  "Trellis-Based R-D Optimal Quantization in H.263+"
626     *    J.Wen, M.Luttrell, J.Villasenor
627     *    IEEE Transactions on Image Processing, Vol.9, No.8, Aug. 2000.
628     *
629     * we are at stake with a simplified Bellmand-Ford / Dijkstra Single
630     * Source Shortest Path algo. But due to the underlying graph structure
631     * ("Trellis"), it can be turned into a dynamic programming algo,
632     * partially saving the explicit graph's nodes representation. And
633     * without using a heap, since the open frontier of the DAG is always
634     * known, and of fixed size.
635     *--------------------------------------------------------------------------*/
636    
637    
638    
639    /* Codes lengths for relevant levels. */
640    
641    /* let's factorize: */
642    static const uint8_t Code_Len0[64] = {
643            30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,
644            30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 };
645    static const uint8_t Code_Len1[64] = {
646            20,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,
647            30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 };
648    static const uint8_t Code_Len2[64] = {
649            19,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,
650            30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 };
651    static const uint8_t Code_Len3[64] = {
652            18,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,
653            30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 };
654    static const uint8_t Code_Len4[64] = {
655            17,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,
656            30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 };
657    static const uint8_t Code_Len5[64] = {
658            16,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,
659            30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 };
660    static const uint8_t Code_Len6[64] = {
661            15,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,
662            30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 };
663    static const uint8_t Code_Len7[64] = {
664            13,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,
665            30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 };
666    static const uint8_t Code_Len8[64] = {
667            11,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,
668            30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 };
669    static const uint8_t Code_Len9[64] = {
670            12,21,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,
671            30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 };
672    static const uint8_t Code_Len10[64] = {
673            12,20,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,
674            30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 };
675    static const uint8_t Code_Len11[64] = {
676            12,19,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,
677            30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 };
678    static const uint8_t Code_Len12[64] = {
679            11,17,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,
680            30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 };
681    static const uint8_t Code_Len13[64] = {
682            11,15,21,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,
683            30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 };
684    static const uint8_t Code_Len14[64] = {
685            10,12,19,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,
686            30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 };
687    static const uint8_t Code_Len15[64] = {
688            10,13,17,19,21,21,21,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,
689            30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 };
690    static const uint8_t Code_Len16[64] = {
691            9,12,13,18,18,19,19,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,
692            30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30};
693    static const uint8_t Code_Len17[64] = {
694            8,11,13,14,14,14,15,19,19,19,21,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,
695            30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 };
696    static const uint8_t Code_Len18[64] = {
697            7, 9,11,11,13,13,13,15,15,15,16,22,22,22,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,
698            30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 };
699    static const uint8_t Code_Len19[64] = {
700            5, 7, 9,10,10,11,11,11,11,11,13,14,16,17,17,18,18,18,18,18,18,18,18,20,20,21,21,30,30,30,30,30,
701            30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 };
702    static const uint8_t Code_Len20[64] = {
703            3, 4, 5, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 9, 9,10,10,10,10,10,10,10,10,12,12,13,13,12,13,14,15,15,
704            15,16,16,16,16,17,17,17,18,18,19,19,19,19,19,19,19,19,21,21,22,22,30,30,30,30,30,30,30,30,30,30 };
705    
706    /* a few more table for LAST table: */
707    static const uint8_t Code_Len21[64] = {
708            13,20,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,
709            30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30};
710    static const uint8_t Code_Len22[64] = {
711            12,15,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,
712            30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30};
713    static const uint8_t Code_Len23[64] = {
714            10,12,15,15,15,16,16,16,16,17,17,17,17,17,17,17,17,18,18,18,18,18,18,18,18,19,19,19,19,20,20,20,
715            20,21,21,21,21,21,21,21,21,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30};
716    static const uint8_t Code_Len24[64] = {
717            5, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9,10,10,10,10,10,10,10,10,11,11,11,11,12,12,12,
718            12,13,13,13,13,13,13,13,13,14,16,16,16,16,17,17,17,17,18,18,18,18,18,18,18,18,19,19,19,19,19,19};
719    
720    
721    static const uint8_t * const B16_17_Code_Len[24] = { /* levels [1..24] */
722            Code_Len20,Code_Len19,Code_Len18,Code_Len17,
723            Code_Len16,Code_Len15,Code_Len14,Code_Len13,
724            Code_Len12,Code_Len11,Code_Len10,Code_Len9,
725            Code_Len8, Code_Len7 ,Code_Len6 ,Code_Len5,
726            Code_Len4, Code_Len3, Code_Len3 ,Code_Len2,
727            Code_Len2, Code_Len1, Code_Len1, Code_Len1,
728    };
729    
730    static const uint8_t * const B16_17_Code_Len_Last[6] = { /* levels [1..6] */
731            Code_Len24,Code_Len23,Code_Len22,Code_Len21, Code_Len3, Code_Len1,
732    };
733    
734    /* TL_SHIFT controls the precision of the RD optimizations in trellis
735     * valid range is [10..16]. The bigger, the more trellis is vulnerable
736     * to overflows in cost formulas.
737     *  - 10 allows ac values up to 2^11 == 2048
738     *  - 16 allows ac values up to 2^8 == 256
739     */
740    #define TL_SHIFT 11
741    #define TL(q) ((0xfe00>>(16-TL_SHIFT))/(q*q))
742    
743    static const int Trellis_Lambda_Tabs[31] = {
744            TL( 1),TL( 2),TL( 3),TL( 4),TL( 5),TL( 6), TL( 7),
745            TL( 8),TL( 9),TL(10),TL(11),TL(12),TL(13),TL(14), TL(15),
746            TL(16),TL(17),TL(18),TL(19),TL(20),TL(21),TL(22), TL(23),
747            TL(24),TL(25),TL(26),TL(27),TL(28),TL(29),TL(30), TL(31)
748    };
749    #undef TL
750    
751    static int __inline
752    Find_Last(const int16_t *C, const uint16_t *Zigzag, int i)
753    {
754            while(i>=0)
755                    if (C[Zigzag[i]])
756                            return i;
757                    else i--;
758            return -1;
759    }
760    
761    #define TRELLIS_MIN_EFFORT      3
762    
763    /* this routine has been strippen of all debug code */
764    static int
765    dct_quantize_trellis_c(int16_t *const Out,
766                                               const int16_t *const In,
767                                               int Q,
768                                               const uint16_t * const Zigzag,
769                                               const uint16_t * const QuantMatrix,
770                                               int Non_Zero,
771                                               int Sum,
772                                               int Lambda_Mod)
773    {
774    
775            /* Note: We should search last non-zero coeffs on *real* DCT input coeffs
776             * (In[]), not quantized one (Out[]). However, it only improves the result
777             * *very* slightly (~0.01dB), whereas speed drops to crawling level :)
778             * Well, actually, taking 1 more coeff past Non_Zero into account sometimes
779             * helps. */
780            typedef struct { int16_t Run, Level; } NODE;
781    
782            NODE Nodes[65], Last = { 0, 0};
783            uint32_t Run_Costs0[64+1];
784            uint32_t * const Run_Costs = Run_Costs0 + 1;
785    
786            /* it's 1/lambda, actually */
787            const int Lambda = (Lambda_Mod*Trellis_Lambda_Tabs[Q-1])>>LAMBDA_EXP;
788    
789            int Run_Start = -1;
790            uint32_t Min_Cost = 2<<TL_SHIFT;
791    
792            int Last_Node = -1;
793            uint32_t Last_Cost = 0;
794    
795            int i, j;
796    
797            /* source (w/ CBP penalty) */
798            Run_Costs[-1] = 2<<TL_SHIFT;
799    
800            Non_Zero = Find_Last(Out, Zigzag, Non_Zero);
801            if (Non_Zero < TRELLIS_MIN_EFFORT)
802                    Non_Zero = TRELLIS_MIN_EFFORT;
803    
804            for(i=0; i<=Non_Zero; i++) {
805                    const int q = ((Q*QuantMatrix[Zigzag[i]])>>4);
806                    const int Mult = 2*q;
807                    const int Bias = (q-1) | 1;
808                    const int Lev0 = Mult + Bias;
809    
810                    const int AC = In[Zigzag[i]];
811                    const int Level1 = Out[Zigzag[i]];
812                    const unsigned int Dist0 = Lambda* AC*AC;
813                    uint32_t Best_Cost = 0xf0000000;
814                    Last_Cost += Dist0;
815    
816                    /* very specialized loop for -1,0,+1 */
817                    if ((uint32_t)(Level1+1)<3) {
818                            int dQ;
819                            int Run;
820                            uint32_t Cost0;
821    
822                            if (AC<0) {
823                                    Nodes[i].Level = -1;
824                                    dQ = Lev0 + AC;
825                            } else {
826                                    Nodes[i].Level = 1;
827                                    dQ = Lev0 - AC;
828                            }
829                            Cost0 = Lambda*dQ*dQ;
830    
831                            Nodes[i].Run = 1;
832                            Best_Cost = (Code_Len20[0]<<TL_SHIFT) + Run_Costs[i-1]+Cost0;
833                            for(Run=i-Run_Start; Run>0; --Run) {
834                                    const uint32_t Cost_Base = Cost0 + Run_Costs[i-Run];
835                                    const uint32_t Cost = Cost_Base + (Code_Len20[Run-1]<<TL_SHIFT);
836                                    const uint32_t lCost = Cost_Base + (Code_Len24[Run-1]<<TL_SHIFT);
837    
838                                    /* TODO: what about tie-breaks? Should we favor short runs or
839                                     * long runs? Although the error is the same, it would not be
840                                     * spread the same way along high and low frequencies... */
841    
842                                    /* Gruel: I'd say, favour short runs => hifreq errors (HVS) */
843    
844                                    if (Cost<Best_Cost) {
845                                            Best_Cost        = Cost;
846                                            Nodes[i].Run = Run;
847                                    }
848    
849                                    if (lCost<Last_Cost) {
850                                            Last_Cost  = lCost;
851                                            Last.Run   = Run;
852                                            Last_Node  = i;
853                                    }
854                            }
855                            if (Last_Node==i)
856                                    Last.Level = Nodes[i].Level;
857                    } else if (51U>(uint32_t)(Level1+25)) {
858                            /* "big" levels (not less than ESC3, though) */
859                            const uint8_t *Tbl_L1, *Tbl_L2, *Tbl_L1_Last, *Tbl_L2_Last;
860                            int Level2;
861                            int dQ1, dQ2;
862                            int Run;
863                            uint32_t Dist1,Dist2;
864                            int dDist21;
865    
866                            if (Level1>1) {
867                                    dQ1 = Level1*Mult-AC + Bias;
868                                    dQ2 = dQ1 - Mult;
869                                    Level2 = Level1-1;
870                                    Tbl_L1          = (Level1<=24) ? B16_17_Code_Len[Level1-1]         : Code_Len0;
871                                    Tbl_L2          = (Level2<=24) ? B16_17_Code_Len[Level2-1]         : Code_Len0;
872                                    Tbl_L1_Last = (Level1<=6) ? B16_17_Code_Len_Last[Level1-1] : Code_Len0;
873                                    Tbl_L2_Last = (Level2<=6) ? B16_17_Code_Len_Last[Level2-1] : Code_Len0;
874                            } else { /* Level1<-1 */
875                                    dQ1 = Level1*Mult-AC - Bias;
876                                    dQ2 = dQ1 + Mult;
877                                    Level2 = Level1 + 1;
878                                    Tbl_L1          = (Level1>=-24) ? B16_17_Code_Len[Level1^-1]      : Code_Len0;
879                                    Tbl_L2          = (Level2>=-24) ? B16_17_Code_Len[Level2^-1]      : Code_Len0;
880                                    Tbl_L1_Last = (Level1>=- 6) ? B16_17_Code_Len_Last[Level1^-1] : Code_Len0;
881                                    Tbl_L2_Last = (Level2>=- 6) ? B16_17_Code_Len_Last[Level2^-1] : Code_Len0;
882                            }
883    
884                            Dist1 = Lambda*dQ1*dQ1;
885                            Dist2 = Lambda*dQ2*dQ2;
886                            dDist21 = Dist2-Dist1;
887    
888                            for(Run=i-Run_Start; Run>0; --Run)
889                            {
890                                    const uint32_t Cost_Base = Dist1 + Run_Costs[i-Run];
891                                    uint32_t Cost1, Cost2;
892                                    int bLevel;
893    
894                                    /* for sub-optimal (but slightly worth it, speed-wise) search,
895                                     * uncomment the following:
896                                     *              if (Cost_Base>=Best_Cost) continue;
897                                     * (? doesn't seem to have any effect -- gruel ) */
898    
899                                    Cost1 = Cost_Base + (Tbl_L1[Run-1]<<TL_SHIFT);
900                                    Cost2 = Cost_Base + (Tbl_L2[Run-1]<<TL_SHIFT) + dDist21;
901    
902                                    if (Cost2<Cost1) {
903                                            Cost1 = Cost2;
904                                            bLevel = Level2;
905                                    } else {
906                                            bLevel = Level1;
907                                    }
908    
909                                    if (Cost1<Best_Cost) {
910                                            Best_Cost = Cost1;
911                                            Nodes[i].Run   = Run;
912                                            Nodes[i].Level = bLevel;
913                                    }
914    
915                                    Cost1 = Cost_Base + (Tbl_L1_Last[Run-1]<<TL_SHIFT);
916                                    Cost2 = Cost_Base + (Tbl_L2_Last[Run-1]<<TL_SHIFT) + dDist21;
917    
918                                    if (Cost2<Cost1) {
919                                            Cost1 = Cost2;
920                                            bLevel = Level2;
921                                    } else {
922                                            bLevel = Level1;
923                                    }
924    
925                                    if (Cost1<Last_Cost) {
926                                            Last_Cost  = Cost1;
927                                            Last.Run   = Run;
928                                            Last.Level = bLevel;
929                                            Last_Node  = i;
930                                    }
931                            } /* end of "for Run" */
932                    } else {
933                            /* Very very high levels, with no chance of being optimizable
934                             * => Simply pick best Run. */
935                            int Run;
936                            for(Run=i-Run_Start; Run>0; --Run) {
937                                    /* 30 bits + no distortion */
938                                    const uint32_t Cost = (30<<TL_SHIFT) + Run_Costs[i-Run];
939                                    if (Cost<Best_Cost) {
940                                            Best_Cost = Cost;
941                                            Nodes[i].Run   = Run;
942                                            Nodes[i].Level = Level1;
943                                    }
944    
945                                    if (Cost<Last_Cost) {
946                                            Last_Cost  = Cost;
947                                            Last.Run   = Run;
948                                            Last.Level = Level1;
949                                            Last_Node  = i;
950                                    }
951                            }
952                    }
953    
954    
955                    Run_Costs[i] = Best_Cost;
956    
957                    if (Best_Cost < Min_Cost + Dist0) {
958                            Min_Cost = Best_Cost;
959                            Run_Start = i;
960                    } else {
961                            /* as noticed by Michael Niedermayer (michaelni at gmx.at),
962                             * there's a code shorter by 1 bit for a larger run (!), same
963                             * level. We give it a chance by not moving the left barrier too
964                             * much. */
965                            while( Run_Costs[Run_Start]>Min_Cost+(1<<TL_SHIFT) )
966                                    Run_Start++;
967    
968                            /* spread on preceding coeffs the cost incurred by skipping this
969                             * one */
970                            for(j=Run_Start; j<i; ++j) Run_Costs[j] += Dist0;
971                            Min_Cost += Dist0;
972                    }
973            }
974    
975            /* It seems trellis doesn't give good results... just leave the block untouched
976             * and return the original sum value */
977            if (Last_Node<0)
978                    return Sum;
979    
980            /* reconstruct optimal sequence backward with surviving paths */
981            memset(Out, 0x00, 64*sizeof(*Out));
982            Out[Zigzag[Last_Node]] = Last.Level;
983            i = Last_Node - Last.Run;
984            Sum = abs(Last.Level);
985            while(i>=0) {
986                    Out[Zigzag[i]] = Nodes[i].Level;
987                    Sum += abs(Nodes[i].Level);
988                    i -= Nodes[i].Run;
989            }
990    
991            return Sum;
992    }
993    
994    /* original version including heavy debugging info */
995    
996    #ifdef DBGTRELL
997    
998    #define DBG 0
999    
1000    static __inline uint32_t Evaluate_Cost(const int16_t *C, int Mult, int Bias,
1001                                                                               const uint16_t * Zigzag, int Max, int Lambda)
1002    {
1003    #if (DBG>0)
1004            const int16_t * const Ref = C + 6*64;
1005            int Last = Max;
1006            int Bits = 0;
1007            int Dist = 0;
1008            int i;
1009            uint32_t Cost;
1010    
1011            while(Last>=0 && C[Zigzag[Last]]==0)
1012                    Last--;
1013    
1014            if (Last>=0) {
1015                    int j=0, j0=0;
1016                    int Run, Level;
1017    
1018                    Bits = 2;   /* CBP */
1019                    while(j<Last) {
1020                            while(!C[Zigzag[j]])
1021                                    j++;
1022                            if (j==Last)
1023                                    break;
1024                            Level=C[Zigzag[j]];
1025                            Run = j - j0;
1026                            j0 = ++j;
1027                            if (Level>=-24 && Level<=24)
1028                                    Bits += B16_17_Code_Len[(Level<0) ? -Level-1 : Level-1][Run];
1029                            else
1030                                    Bits += 30;
1031                    }
1032                    Level = C[Zigzag[Last]];
1033                    Run = j - j0;
1034                    if (Level>=-6 && Level<=6)
1035                            Bits += B16_17_Code_Len_Last[(Level<0) ? -Level-1 : Level-1][Run];
1036                    else
1037                            Bits += 30;
1038            }
1039    
1040            for(i=0; i<=Last; ++i) {
1041                    int V = C[Zigzag[i]]*Mult;
1042                    if (V>0)
1043                            V += Bias;
1044                    else
1045                            if (V<0)
1046                                    V -= Bias;
1047                    V -= Ref[Zigzag[i]];
1048                    Dist += V*V;
1049            }
1050            Cost = Lambda*Dist + (Bits<<TL_SHIFT);
1051            if (DBG==1)
1052                    printf( " Last:%2d/%2d Cost = [(Bits=%5.0d) + Lambda*(Dist=%6.0d) = %d ] >>12= %d ", Last,Max, Bits, Dist, Cost, Cost>>12 );
1053            return Cost;
1054    
1055    #else
1056            return 0;
1057    #endif
1058    }
1059    
1060    
1061    static int
1062    dct_quantize_trellis_h263_c(int16_t *const Out, const int16_t *const In, int Q, const uint16_t * const Zigzag, int Non_Zero)
1063    {
1064    
1065        /*
1066             * Note: We should search last non-zero coeffs on *real* DCT input coeffs (In[]),
1067             * not quantized one (Out[]). However, it only improves the result *very*
1068             * slightly (~0.01dB), whereas speed drops to crawling level :)
1069             * Well, actually, taking 1 more coeff past Non_Zero into account sometimes helps.
1070             */
1071            typedef struct { int16_t Run, Level; } NODE;
1072    
1073            NODE Nodes[65], Last;
1074            uint32_t Run_Costs0[64+1];
1075            uint32_t * const Run_Costs = Run_Costs0 + 1;
1076            const int Mult = 2*Q;
1077            const int Bias = (Q-1) | 1;
1078            const int Lev0 = Mult + Bias;
1079            const int Lambda = Trellis_Lambda_Tabs[Q-1];    /* it's 1/lambda, actually */
1080    
1081            int Run_Start = -1;
1082            Run_Costs[-1] = 2<<TL_SHIFT;                          /* source (w/ CBP penalty) */
1083            uint32_t Min_Cost = 2<<TL_SHIFT;
1084    
1085            int Last_Node = -1;
1086            uint32_t Last_Cost = 0;
1087    
1088            int i, j;
1089    
1090    #if (DBG>0)
1091            Last.Level = 0; Last.Run = -1; /* just initialize to smthg */
1092    #endif
1093    
1094            Non_Zero = Find_Last(Out, Zigzag, Non_Zero);
1095            if (Non_Zero<0)
1096                    return -1;
1097    
1098            for(i=0; i<=Non_Zero; i++)
1099            {
1100                    const int AC = In[Zigzag[i]];
1101                    const int Level1 = Out[Zigzag[i]];
1102                    const int Dist0 = Lambda* AC*AC;
1103                    uint32_t Best_Cost = 0xf0000000;
1104                    Last_Cost += Dist0;
1105    
1106                    if ((uint32_t)(Level1+1)<3)                 /* very specialized loop for -1,0,+1 */
1107                    {
1108                            int dQ;
1109                            int Run;
1110                            uint32_t Cost0;
1111    
1112                            if (AC<0) {
1113                                    Nodes[i].Level = -1;
1114                                    dQ = Lev0 + AC;
1115                            } else {
1116                                    Nodes[i].Level = 1;
1117                                    dQ = Lev0 - AC;
1118                            }
1119                            Cost0 = Lambda*dQ*dQ;
1120    
1121                            Nodes[i].Run = 1;
1122                            Best_Cost = (Code_Len20[0]<<TL_SHIFT) + Run_Costs[i-1]+Cost0;
1123                            for(Run=i-Run_Start; Run>0; --Run)
1124                            {
1125                                    const uint32_t Cost_Base = Cost0 + Run_Costs[i-Run];
1126                                    const uint32_t Cost = Cost_Base + (Code_Len20[Run-1]<<TL_SHIFT);
1127                                    const uint32_t lCost = Cost_Base + (Code_Len24[Run-1]<<TL_SHIFT);
1128    
1129                                    /*
1130                                     * TODO: what about tie-breaks? Should we favor short runs or
1131                                     * long runs? Although the error is the same, it would not be
1132                                     * spread the same way along high and low frequencies...
1133                                     */
1134                                    if (Cost<Best_Cost) {
1135                                            Best_Cost    = Cost;
1136                                            Nodes[i].Run = Run;
1137                                    }
1138    
1139                                    if (lCost<Last_Cost) {
1140                                            Last_Cost  = lCost;
1141                                            Last.Run   = Run;
1142                                            Last_Node  = i;
1143                                    }
1144                            }
1145                            if (Last_Node==i)
1146                                    Last.Level = Nodes[i].Level;
1147    
1148                            if (DBG==1) {
1149                                    Run_Costs[i] = Best_Cost;
1150                                    printf( "Costs #%2d: ", i);
1151                                    for(j=-1;j<=Non_Zero;++j) {
1152                                            if (j==Run_Start)            printf( " %3.0d|", Run_Costs[j]>>12 );
1153                                            else if (j>Run_Start && j<i) printf( " %3.0d|", Run_Costs[j]>>12 );
1154                                            else if (j==i)               printf( "(%3.0d)", Run_Costs[j]>>12 );
1155                                            else                         printf( "  - |" );
1156                                    }
1157                                    printf( "<%3.0d %2d %d>", Min_Cost>>12, Nodes[i].Level, Nodes[i].Run );
1158                                    printf( "  Last:#%2d {%3.0d %2d %d}", Last_Node, Last_Cost>>12, Last.Level, Last.Run );
1159                                    printf( " AC:%3.0d Dist0:%3d Dist(%d)=%d", AC, Dist0>>12, Nodes[i].Level, Cost0>>12 );
1160                                    printf( "\n" );
1161                            }
1162                    }
1163                    else                      /* "big" levels */
1164                    {
1165                            const uint8_t *Tbl_L1, *Tbl_L2, *Tbl_L1_Last, *Tbl_L2_Last;
1166                            int Level2;
1167                            int dQ1, dQ2;
1168                            int Run;
1169                            uint32_t Dist1,Dist2;
1170                            int dDist21;
1171    
1172                            if (Level1>1) {
1173                                    dQ1 = Level1*Mult-AC + Bias;
1174                                    dQ2 = dQ1 - Mult;
1175                                    Level2 = Level1-1;
1176                                    Tbl_L1      = (Level1<=24) ? B16_17_Code_Len[Level1-1]     : Code_Len0;
1177                                    Tbl_L2      = (Level2<=24) ? B16_17_Code_Len[Level2-1]     : Code_Len0;
1178                                    Tbl_L1_Last = (Level1<=6) ? B16_17_Code_Len_Last[Level1-1] : Code_Len0;
1179                                    Tbl_L2_Last = (Level2<=6) ? B16_17_Code_Len_Last[Level2-1] : Code_Len0;
1180                            } else { /* Level1<-1 */
1181                                    dQ1 = Level1*Mult-AC - Bias;
1182                                    dQ2 = dQ1 + Mult;
1183                                    Level2 = Level1 + 1;
1184                                    Tbl_L1      = (Level1>=-24) ? B16_17_Code_Len[Level1^-1]      : Code_Len0;
1185                                    Tbl_L2      = (Level2>=-24) ? B16_17_Code_Len[Level2^-1]      : Code_Len0;
1186                                    Tbl_L1_Last = (Level1>=- 6) ? B16_17_Code_Len_Last[Level1^-1] : Code_Len0;
1187                                    Tbl_L2_Last = (Level2>=- 6) ? B16_17_Code_Len_Last[Level2^-1] : Code_Len0;
1188                            }
1189                            Dist1 = Lambda*dQ1*dQ1;
1190                            Dist2 = Lambda*dQ2*dQ2;
1191                            dDist21 = Dist2-Dist1;
1192    
1193                            for(Run=i-Run_Start; Run>0; --Run)
1194                            {
1195                                    const uint32_t Cost_Base = Dist1 + Run_Costs[i-Run];
1196                                    uint32_t Cost1, Cost2;
1197                                    int bLevel;
1198    
1199    /*
1200     * for sub-optimal (but slightly worth it, speed-wise) search, uncomment the following:
1201     *        if (Cost_Base>=Best_Cost) continue;
1202     */
1203                                    Cost1 = Cost_Base + (Tbl_L1[Run-1]<<TL_SHIFT);
1204                                    Cost2 = Cost_Base + (Tbl_L2[Run-1]<<TL_SHIFT) + dDist21;
1205    
1206                                    if (Cost2<Cost1) {
1207                                            Cost1 = Cost2;
1208                                            bLevel = Level2;
1209                                    } else
1210                                            bLevel = Level1;
1211    
1212                                    if (Cost1<Best_Cost) {
1213                                            Best_Cost = Cost1;
1214                                            Nodes[i].Run   = Run;
1215                                            Nodes[i].Level = bLevel;
1216                                    }
1217    
1218                                    Cost1 = Cost_Base + (Tbl_L1_Last[Run-1]<<TL_SHIFT);
1219                                    Cost2 = Cost_Base + (Tbl_L2_Last[Run-1]<<TL_SHIFT) + dDist21;
1220    
1221                                    if (Cost2<Cost1) {
1222                                            Cost1 = Cost2;
1223                                            bLevel = Level2;
1224                                    } else
1225                                            bLevel = Level1;
1226    
1227                                    if (Cost1<Last_Cost) {
1228                                            Last_Cost  = Cost1;
1229                                            Last.Run   = Run;
1230                                            Last.Level = bLevel;
1231                                            Last_Node  = i;
1232                                    }
1233                            } /* end of "for Run" */
1234    
1235                            if (DBG==1) {
1236                                    Run_Costs[i] = Best_Cost;
1237                                    printf( "Costs #%2d: ", i);
1238                                    for(j=-1;j<=Non_Zero;++j) {
1239                                            if (j==Run_Start)            printf( " %3.0d|", Run_Costs[j]>>12 );
1240                                            else if (j>Run_Start && j<i) printf( " %3.0d|", Run_Costs[j]>>12 );
1241                                            else if (j==i)               printf( "(%3.0d)", Run_Costs[j]>>12 );
1242                                            else                         printf( "  - |" );
1243                                    }
1244                                    printf( "<%3.0d %2d %d>", Min_Cost>>12, Nodes[i].Level, Nodes[i].Run );
1245                                    printf( "  Last:#%2d {%3.0d %2d %d}", Last_Node, Last_Cost>>12, Last.Level, Last.Run );
1246                                    printf( " AC:%3.0d Dist0:%3d Dist(%2d):%3d Dist(%2d):%3d", AC, Dist0>>12, Level1, Dist1>>12, Level2, Dist2>>12 );
1247                                    printf( "\n" );
1248                            }
1249                    }
1250    
1251                    Run_Costs[i] = Best_Cost;
1252    
1253                    if (Best_Cost < Min_Cost + Dist0) {
1254                            Min_Cost = Best_Cost;
1255                            Run_Start = i;
1256                    }
1257                    else
1258                    {
1259                            /*
1260                             * as noticed by Michael Niedermayer (michaelni at gmx.at), there's
1261                             * a code shorter by 1 bit for a larger run (!), same level. We give
1262                             * it a chance by not moving the left barrier too much.
1263                             */
1264    
1265                            while( Run_Costs[Run_Start]>Min_Cost+(1<<TL_SHIFT) )
1266                                    Run_Start++;
1267    
1268                            /* spread on preceding coeffs the cost incurred by skipping this one */
1269                            for(j=Run_Start; j<i; ++j) Run_Costs[j] += Dist0;
1270                            Min_Cost += Dist0;
1271                    }
1272            }
1273    
1274            if (DBG) {
1275                    Last_Cost = Evaluate_Cost(Out,Mult,Bias, Zigzag,Non_Zero, Lambda);
1276                    if (DBG==1) {
1277                            printf( "=> " );
1278                            for(i=0; i<=Non_Zero; ++i) printf( "[%3.0d] ", Out[Zigzag[i]] );
1279                            printf( "\n" );
1280                    }
1281            }
1282    
1283            if (Last_Node<0)
1284                    return -1;
1285    
1286            /* reconstruct optimal sequence backward with surviving paths */
1287            memset(Out, 0x00, 64*sizeof(*Out));
1288            Out[Zigzag[Last_Node]] = Last.Level;
1289            i = Last_Node - Last.Run;
1290            while(i>=0) {
1291                    Out[Zigzag[i]] = Nodes[i].Level;
1292                    i -= Nodes[i].Run;
1293            }
1294    
1295            if (DBG) {
1296                    uint32_t Cost = Evaluate_Cost(Out,Mult,Bias, Zigzag,Non_Zero, Lambda);
1297                    if (DBG==1) {
1298                            printf( "<= " );
1299                            for(i=0; i<=Last_Node; ++i) printf( "[%3.0d] ", Out[Zigzag[i]] );
1300                            printf( "\n--------------------------------\n" );
1301                    }
1302                    if (Cost>Last_Cost) printf( "!!! %u > %u\n", Cost, Last_Cost );
1303            }
1304            return Last_Node;
1305    }
1306    
1307    #undef DBG
1308    
1309    #endif
Legend:
Removed from v.82  
changed lines
  Added in v.1663
No admin address has been configured
 ViewVC Help
Powered by ViewVC 1.0.4