00001 /*===========================================================================*
00002  * postdct.c                                                                 *
00003  *                                                                           *
00004  *      Procedures concerned with MPEG post-DCT processing:                  *
00005  *          quantization and RLE Huffman encoding                            *
00006  *                                                                           *
00007  * EXPORTED PROCEDURES:                                                      *
00008  *      Mpost_QuantZigBlock                                                  *
00009  *      Mpost_RLEHuffIBlock                                                  *
00010  *      Mpost_RLEHuffPBlock                                                  *
00011  *      Mpost_UnQuantZigBlock                                                *
00012  *                                                                           *
00013  *===========================================================================*/
00014 
00015 /*
00016  * Copyright (c) 1995 The Regents of the University of California.
00017  * All rights reserved.
00018  *
00019  * Permission to use, copy, modify, and distribute this software and its
00020  * documentation for any purpose, without fee, and without written agreement is
00021  * hereby granted, provided that the above copyright notice and the following
00022  * two paragraphs appear in all copies of this software.
00023  *
00024  * IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
00025  * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
00026  * OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
00027  * CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00028  *
00029  * THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
00030  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
00031  * AND FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
00032  * ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
00033  * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
00034  */
00035 
00036 /*
00037  *  $Header: /misc/elrond0/share/cvs/AFNI/src/mpeg_encodedir/postdct.c,v 1.4 2004/04/02 15:12:41 rwcox Exp $
00038  *  $Log: postdct.c,v $
00039  *  Revision 1.4  2004/04/02 15:12:41  rwcox
00040  *  Cput
00041  *
00042  *  Revision 1.3  2003/12/23 13:50:08  rwcox
00043  *  Cput
00044  *
00045  *  Revision 1.2  2003/12/03 14:46:14  rwcox
00046  *  Cput
00047  *
00048  *  Revision 1.1  2001/12/17 16:11:55  rwcox
00049  *  Cadd
00050  *
00051  * Revision 1.12  1995/06/21  18:26:39  smoot
00052  * added length estimator for P-blocks
00053  *
00054  * Revision 1.11  1995/04/23  23:22:59  eyhung
00055  * nothing changed
00056  *
00057  * Revision 1.10  1995/04/14  23:10:46  smoot
00058  * Added overflow detection to MPOST_DCT so it will adjust Qscales (above)
00059  *
00060  * Revision 1.9  1995/02/15  23:15:32  smoot
00061  * killed useless asserts
00062  *
00063  * Revision 1.8  1995/02/01  21:48:41  smoot
00064  * assure out is set properly, short circuit 0 revquant
00065  *
00066  * Revision 1.7  1995/01/30  19:56:37  smoot
00067  * Killed a <0 shift
00068  *
00069  * Revision 1.6  1995/01/25  23:07:33  smoot
00070  * Better DBG_PRINTs, multiply/divide instead of shifts
00071  *
00072  * Revision 1.5  1995/01/19  23:09:10  eyhung
00073  * Changed copyrights
00074  *
00075  * Revision 1.4  1995/01/16  08:17:08  eyhung
00076  * added realQuiet
00077  *
00078  * Revision 1.3  1994/11/12  02:11:58  keving
00079  * nothing
00080  *
00081  * Revision 1.2  1994/03/15  00:27:11  keving
00082  * nothing
00083  *
00084  * Revision 1.2  1994/03/15  00:27:11  keving
00085  * nothing
00086  *
00087  * Revision 1.1  1993/12/22  19:19:01  keving
00088  * nothing
00089  *
00090  * Revision 1.11  1993/07/22  22:23:43  keving
00091  * nothing
00092  *
00093  * Revision 1.10  1993/06/30  20:06:09  keving
00094  * nothing
00095  *
00096  * Revision 1.9  1993/06/03  21:08:08  keving
00097  * nothing
00098  *
00099  * Revision 1.8  1993/02/24  18:57:19  keving
00100  * nothing
00101  *
00102  * Revision 1.7  1993/02/23  22:58:36  keving
00103  * nothing
00104  *
00105  * Revision 1.6  1993/02/23  22:54:56  keving
00106  * nothing
00107  *
00108  * Revision 1.5  1993/02/17  23:18:20  dwallach
00109  * checkin prior to keving's joining the project
00110  *
00111  * Revision 1.4  1993/01/18  10:20:02  dwallach
00112  * *** empty log message ***
00113  *
00114  * Revision 1.3  1993/01/18  10:17:29  dwallach
00115  * RCS headers installed, code indented uniformly
00116  *
00117  * Revision 1.3  1993/01/18  10:17:29  dwallach
00118  * RCS headers installed, code indented uniformly
00119  *
00120  */
00121 
00122 
00123 /*==============*
00124  * HEADER FILES *
00125  *==============*/
00126 
00127 #include <assert.h>
00128 #include "all.h"
00129 #include "mtypes.h"
00130 #include "bitio.h"
00131 #include "huff.h"
00132 #include "postdct.h"
00133 #include "opts.h"
00134 
00135 /*==================*
00136  * STATIC VARIABLES *
00137  *==================*/
00138 
00139 /* ZAG[i] is the natural-order position of the i'th element of zigzag order. */
00140 int ZAG[] = {
00141     0, 1, 8, 16, 9, 2, 3, 10,
00142     17, 24, 32, 25, 18, 11, 4, 5,
00143     12, 19, 26, 33, 40, 48, 41, 34,
00144     27, 20, 13, 6, 7, 14, 21, 28,
00145     35, 42, 49, 56, 57, 50, 43, 36,
00146     29, 22, 15, 23, 30, 37, 44, 51,
00147     58, 59, 52, 45, 38, 31, 39, 46,
00148     53, 60, 61, 54, 47, 55, 62, 63
00149 };
00150 
00151 /*
00152  * possible optimization: reorder the qtable in the correct zigzag order, to
00153  * reduce the number of necessary lookups
00154  *
00155  * this table comes from the MPEG draft, p. D-16, Fig. 2-D.15.
00156  */
00157 int32 qtable[] = {
00158     8, 16, 19, 22, 26, 27, 29, 34,
00159     16, 16, 22, 24, 27, 29, 34, 37,
00160     19, 22, 26, 27, 29, 34, 34, 38,
00161     22, 22, 26, 27, 29, 34, 37, 40,
00162     22, 26, 27, 29, 32, 35, 40, 48,
00163     26, 27, 29, 32, 35, 40, 48, 58,
00164     26, 27, 29, 34, 38, 46, 56, 69,
00165     27, 29, 35, 38, 46, 56, 69, 83
00166 };
00167 
00168 int32 niqtable[] = {
00169      16, 16, 16, 16, 16, 16, 16, 16,
00170      16, 16, 16, 16, 16, 16, 16, 16,
00171      16, 16, 16, 16, 16, 16, 16, 16,
00172      16, 16, 16, 16, 16, 16, 16, 16,
00173      16, 16, 16, 16, 16, 16, 16, 16,
00174      16, 16, 16, 16, 16, 16, 16, 16,
00175      16, 16, 16, 16, 16, 16, 16, 16,
00176      16, 16, 16, 16, 16, 16, 16, 16
00177 };
00178 
00179 int32   *customQtable = NULL;
00180 int32   *customNIQtable = NULL;
00181 
00182 /*==================*
00183  * GLOBAL VARIABLES *
00184  *==================*/
00185 
00186 extern boolean realQuiet;
00187 
00188 /*=====================*
00189  * EXPORTED PROCEDURES *
00190  *=====================*/
00191 
00192 /*===========================================================================*
00193  *
00194  * Mpost_UnQuantZigBlock
00195  *
00196  *      unquantize and zig-zag (decode) a single block
00197  *      see section 2.4.4.1 of MPEG standard
00198  *
00199  * RETURNS:     nothing
00200  *
00201  * SIDE EFFECTS:    none
00202  *
00203  *===========================================================================*/
00204 void
00205 Mpost_UnQuantZigBlock(in, out, qscale, iblock)
00206     FlatBlock in;
00207     Block out;
00208     int qscale;
00209     boolean iblock;
00210 {
00211     register int index;
00212     int     start;
00213     int     position;
00214     register int            qentry;
00215     int     level, coeff;
00216     
00217     if ( iblock ) {
00218         /* qtable[0] must be 8 */
00219         out[0][0] = (int16)(in[0] * 8);
00220 
00221         /* don't need to do anything fancy here, because we saved orig
00222             value, not encoded dc value */
00223         start = 1;
00224     } else {
00225         start = 0;
00226     }
00227 
00228     for ( index = start;  index < DCTSIZE_SQ;  index++ ) {
00229         position = ZAG[index];
00230         level = in[index];
00231 
00232         if (level == 0) {
00233           ((int16 *)out)[position] = 0;
00234           continue;
00235         }
00236 
00237 
00238         if ( iblock ) {
00239             qentry = qtable[position] * qscale;
00240             coeff = (level*qentry)/8;
00241             if ( (coeff & 1) == 0 ) {
00242                 if ( coeff < 0 ) {
00243                     coeff++;
00244                 } else if ( coeff > 0 ) {
00245                     coeff--;
00246                 }
00247             }
00248         } else {
00249             qentry = niqtable[position] * qscale;
00250             if ( level == 0 ) {
00251                 coeff = 0;
00252             } else if ( level < 0 ) {
00253                 coeff = (((2*level)-1)*qentry) / 16;
00254                 if ( (coeff & 1) == 0 ) {
00255                     coeff++;
00256                 }
00257             } else {
00258                 coeff = (((2*level)+1)*qentry) >> 4;
00259                 if ( (coeff & 1) == 0 ) {
00260                     coeff--;
00261                 }
00262             }
00263 
00264             if ( coeff > 2047 ) {
00265                 coeff = 2047;
00266             } else if ( coeff < -2048 ) {
00267                 coeff = -2048;
00268             }
00269         }
00270 
00271         ((int16 *)out)[position] = coeff;
00272     }
00273 }
00274 
00275 
00276 /*===========================================================================*
00277  *
00278  * Mpost_QuantZigBlock
00279  *
00280  *      quantize and zigzags a block
00281  *
00282  * RETURNS:     MPOST_OVERFLOW if a generated value is outside |255|
00283  *              MPOST_ZERO     if all coeffs are zero
00284  *              MPOST_NON_ZERO otherwisw
00285  *
00286  * SIDE EFFECTS:    none
00287  *
00288  *===========================================================================*/
00289 int
00290 Mpost_QuantZigBlock(in, out, qscale, iblock)
00291     Block in;
00292     FlatBlock out;
00293     register int qscale;
00294     int iblock;
00295 {
00296   register int i;
00297   register int16 temp;
00298   register int qentry;
00299   register int position;
00300   boolean nonZero = FALSE;
00301   boolean overflow = FALSE;
00302   
00303   DBG_PRINT(("Mpost_QuantZigBlock...\n"));
00304   if (iblock) {
00305     /*
00306      * the DC coefficient is handled specially -- it's not
00307      * sensitive to qscale, but everything else is
00308      */
00309     temp = ((int16 *) in)[ZAG[0]];
00310     qentry = qtable[ZAG[0]];
00311     
00312     if (temp < 0) {
00313       temp = -temp;
00314       temp += (qentry >> 1);
00315       temp /= qentry;
00316       temp = -temp;
00317     } else {
00318       temp += (qentry >> 1);
00319       temp /= qentry;
00320     }
00321     if ( temp != 0 ) {
00322       nonZero = TRUE;
00323     }
00324     out[0] = temp;
00325     
00326     for (i = 1; i < DCTSIZE_SQ; i++) {
00327       position = ZAG[i];
00328       temp = ((int16 *) in)[position];
00329       qentry = qtable[position] * qscale;
00330       
00331       /* see 1993 MPEG doc, section D.6.3.4 */
00332       if (temp < 0) {
00333         temp = -temp;
00334         temp = (temp << 3);     /* temp > 0 */
00335         temp += (qentry >> 1);
00336         temp /= qentry;
00337         temp = -temp;
00338       } else {
00339         temp = (temp << 3);     /* temp > 0 */
00340         temp += (qentry >> 1);
00341         temp /= qentry;
00342       }
00343       
00344       if ( temp != 0 ) {
00345         nonZero = TRUE;
00346         out[i] = temp;
00347         if (temp < -255) {
00348           temp = -255;
00349           overflow = TRUE;
00350         } else if (temp > 255) {
00351           temp = 255;
00352           overflow = TRUE;
00353         }
00354       } else out[i]=0;
00355     }
00356   } else {
00357     for (i = 0; i < DCTSIZE_SQ; i++) {
00358       position = ZAG[i];
00359       temp = ((int16 *) in)[position];
00360       
00361       /* multiply by non-intra qtable */
00362       qentry = qscale * niqtable[position];
00363       
00364       /* see 1993 MPEG doc, D.6.4.5 */
00365       temp *= 8;
00366       temp /= qentry;       /* truncation toward 0 -- correct */
00367       
00368       if ( temp != 0 ) {
00369         nonZero = TRUE;
00370         out[i] = temp;
00371         if (temp < -255) {
00372           temp = -255;
00373           overflow = TRUE;
00374         } else if (temp > 255) {
00375           temp = 255;
00376           overflow = TRUE;
00377         }
00378         
00379       } else out[i]=0;
00380     }
00381   }
00382 
00383  if (overflow) return MPOST_OVERFLOW;
00384  if (nonZero)  return MPOST_NON_ZERO;
00385  return MPOST_ZERO;
00386 }
00387 
00388 
00389 
00390 /*===========================================================================*
00391  *
00392  * Mpost_RLEHuffIBlock
00393  *
00394  *      generate the huffman bits from an I-block
00395  *
00396  * RETURNS:     nothing
00397  *
00398  * SIDE EFFECTS:    none
00399  *
00400  *===========================================================================*/
00401 void
00402 Mpost_RLEHuffIBlock(in, out)
00403     FlatBlock in;
00404     BitBucket *out;
00405 {
00406     register int i;
00407     register int nzeros = 0;
00408     register int16 cur;
00409     register int16 acur;
00410     register uint32 code;
00411     register int nbits;
00412 
00413     /*
00414      * yes, Virginia, we start at 1.  The DC coefficient is handled
00415      * specially, elsewhere.  Not here.
00416      */
00417     for (i = 1; i < DCTSIZE_SQ; i++) {
00418         cur = in[i];
00419         acur = ABS(cur);
00420         if (cur) {
00421             if ( (nzeros < HUFF_MAXRUN) && (acur < huff_maxlevel[nzeros])) {
00422                 /*
00423                  * encode using the Huffman tables
00424                  */
00425 
00426                 DBG_PRINT(("rle_huff %02d.%02d: Run %02d, Level %4d\n", i,  ZAG[i], nzeros, cur));
00427                 code = (huff_table[nzeros])[acur];
00428                 nbits = (huff_bits[nzeros])[acur];
00429 
00430                 if (cur < 0) {
00431                     code |= 1;  /* the sign bit */
00432                 }
00433                 Bitio_Write(out, code, nbits);
00434             } else {
00435                 /*
00436                  * encode using the escape code
00437                  */
00438                 DBG_PRINT(("Escape\n"));
00439                 Bitio_Write(out, 0x1, 6);       /* ESCAPE */
00440                 DBG_PRINT(("Run Length\n"));
00441                 Bitio_Write(out, nzeros, 6);    /* Run-Length */
00442 
00443                 /*
00444                  * this shouldn't happen, but the other
00445                  * choice is to bomb out and dump core...
00446                  * Hmmm, seems to happen with small Qtable entries (1) -srs
00447                  */
00448                 if (cur < -255) {
00449                     cur = -255;
00450                 } else if (cur > 255) {
00451                     cur = 255;
00452                 }
00453 
00454                 DBG_PRINT(("Level\n"));
00455                 if (acur < 128) {
00456                     Bitio_Write(out, cur, 8);
00457                 } else {
00458                     if (cur < 0) {
00459                         Bitio_Write(out, 0x8001 + cur + 255, 16);
00460                     } else {
00461                         Bitio_Write(out, cur, 16);
00462                     }
00463                 }
00464             }
00465             nzeros = 0;
00466         } else {
00467             nzeros++;
00468         }
00469     }
00470     DBG_PRINT(("End of block\n"));
00471     Bitio_Write(out, 0x2, 2);   /* end of block marker */
00472 }
00473 
00474 
00475 /*===========================================================================*
00476  *
00477  * Mpost_RLEHuffPBlock
00478  *
00479  *      generate the huffman bits from an P-block
00480  *
00481  * RETURNS:     nothing
00482  *
00483  * SIDE EFFECTS:    none
00484  *
00485  *===========================================================================*/
00486 void
00487 Mpost_RLEHuffPBlock(in, out)
00488     FlatBlock in;
00489     BitBucket *out;
00490 {
00491     register int i;
00492     register int nzeros = 0;
00493     register int16 cur;
00494     register int16 acur;
00495     register uint32 code;
00496     register int nbits;
00497     boolean first_dct = TRUE;
00498 
00499     /*
00500      * yes, Virginia, we start at 0.
00501      */
00502     for (i = 0; i < DCTSIZE_SQ; i++) {
00503         cur = in[i];
00504         acur = ABS(cur);
00505         if (cur) {
00506             if ((nzeros < HUFF_MAXRUN) && (acur < huff_maxlevel[nzeros])) {
00507                 /*
00508                  * encode using the Huffman tables
00509                  */
00510 
00511                 DBG_PRINT(("rle_huff %02d.%02d: Run %02d, Level %4d\n", i, ZAG[i], nzeros, cur));
00512                 if ( first_dct && (nzeros == 0) && (acur == 1) ) {
00513                     /* actually, only needs = 0x2 */
00514                     code = (cur == 1) ? 0x2 : 0x3;
00515                     nbits = 2;
00516                 } else {
00517                     code = (huff_table[nzeros])[acur];
00518                     nbits = (huff_bits[nzeros])[acur];
00519                   }
00520 
00521                 assert(nbits);
00522 
00523                 if (cur < 0) {
00524                     code |= 1;  /* the sign bit */
00525                 }
00526                 Bitio_Write(out, code, nbits);
00527                 first_dct = FALSE;
00528             } else {
00529                 /*
00530                  * encode using the escape code
00531                  */
00532                 DBG_PRINT(("Escape\n"));
00533                 Bitio_Write(out, 0x1, 6);       /* ESCAPE */
00534                 DBG_PRINT(("Run Length\n"));
00535                 Bitio_Write(out, nzeros, 6);    /* Run-Length */
00536 
00537                 /*
00538                  * this shouldn't happen, but the other
00539                  * choice is to bomb out and dump core...
00540                  * Hmmm, seems to happen with small Qtable entries (1) -srs
00541                  */
00542                 if (cur < -255) {
00543                   cur = -255;
00544                 } else if (cur > 255) {
00545                   cur = 255;
00546                 }
00547 
00548                 DBG_PRINT(("Level\n"));
00549                 if (acur < 128) {
00550                     Bitio_Write(out, cur, 8);
00551                 } else {
00552                     if (cur < 0) {
00553                         Bitio_Write(out, 0x8001 + cur + 255, 16);
00554                     } else {
00555                         Bitio_Write(out, cur, 16);
00556                     }
00557                 }
00558 
00559                 first_dct = FALSE;
00560             }
00561             nzeros = 0;
00562         } else {
00563             nzeros++;
00564         }
00565     }
00566 
00567     /* actually, should REALLY return FALSE and not use this! */
00568 
00569     if ( first_dct ) {  /* have to give a first_dct even if all 0's */
00570         fprintf(stderr, "HUFF called with all-zero coefficients\n");
00571         fprintf(stderr, "exiting...\n");
00572         exit(1);
00573     }
00574 
00575     DBG_PRINT(("End of block\n"));
00576     Bitio_Write(out, 0x2, 2);   /* end of block marker */
00577 }
00578 
00579 
00580 /*===========================================================================*
00581  *
00582  * CalcRLEHuffLength
00583  *
00584  *      count the huffman bits for an P-block
00585  *
00586  * RETURNS:     number of bits
00587  *
00588  * SIDE EFFECTS:    none
00589  *
00590  *===========================================================================*/
00591 int
00592 CalcRLEHuffLength(in)
00593     FlatBlock in;
00594 {
00595   register int i;
00596   register int nzeros = 0;
00597   register int16 cur;
00598   register int16 acur;
00599   register int nbits;
00600   register int countbits=0;
00601   boolean first_dct = TRUE;
00602   
00603   for (i = 0; i < DCTSIZE_SQ; i++) {
00604     cur = in[i];
00605     acur = ABS(cur);
00606     if (cur) {
00607       if ((nzeros < HUFF_MAXRUN) && (acur < huff_maxlevel[nzeros])) {
00608         /*
00609          * encode using the Huffman tables
00610          */
00611 
00612         if ( first_dct && (nzeros == 0) && (acur == 1) ) {
00613           nbits = 2;
00614         } else {
00615           nbits = (huff_bits[nzeros])[acur];
00616         }
00617         countbits += nbits;
00618         first_dct = FALSE;
00619       } else {
00620         countbits += 12;        /* ESCAPE + runlength */
00621 
00622         if (acur < 128) {
00623           countbits += 8;
00624         } else {
00625           countbits += 16;
00626         }
00627 
00628         first_dct = FALSE;
00629       }
00630       nzeros = 0;
00631     } else {
00632       nzeros++;
00633     }
00634   }
00635   
00636   countbits += 2; /* end of block marker */
00637   return countbits;
00638 }