1 /*===========================================================================*
2 * postdct.c *
3 * *
4 * Procedures concerned with MPEG post-DCT processing: *
5 * quantization and RLE Huffman encoding *
6 * *
7 * EXPORTED PROCEDURES: *
8 * Mpost_QuantZigBlock *
9 * Mpost_RLEHuffIBlock *
10 * Mpost_RLEHuffPBlock *
11 * Mpost_UnQuantZigBlock *
12 * *
13 *===========================================================================*/
14
15 /*
16 * Copyright (c) 1995 The Regents of the University of California.
17 * All rights reserved.
18 *
19 * Permission to use, copy, modify, and distribute this software and its
20 * documentation for any purpose, without fee, and without written agreement is
21 * hereby granted, provided that the above copyright notice and the following
22 * two paragraphs appear in all copies of this software.
23 *
24 * IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
25 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
26 * OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
27 * CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 *
29 * THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
30 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
31 * AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
32 * ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
33 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
34 */
35
36 /*
37 * $Header$
38 * $Log$
39 * Revision 1.4 2004/04/02 15:12:41 rwcox
40 * Cput
41 *
42 * Revision 1.3 2003/12/23 13:50:08 rwcox
43 * Cput
44 *
45 * Revision 1.2 2003/12/03 14:46:14 rwcox
46 * Cput
47 *
48 * Revision 1.1 2001/12/17 16:11:55 rwcox
49 * Cadd
50 *
51 * Revision 1.12 1995/06/21 18:26:39 smoot
52 * added length estimator for P-blocks
53 *
54 * Revision 1.11 1995/04/23 23:22:59 eyhung
55 * nothing changed
56 *
57 * Revision 1.10 1995/04/14 23:10:46 smoot
58 * Added overflow detection to MPOST_DCT so it will adjust Qscales (above)
59 *
60 * Revision 1.9 1995/02/15 23:15:32 smoot
61 * killed useless asserts
62 *
63 * Revision 1.8 1995/02/01 21:48:41 smoot
64 * assure out is set properly, short circuit 0 revquant
65 *
66 * Revision 1.7 1995/01/30 19:56:37 smoot
67 * Killed a <0 shift
68 *
69 * Revision 1.6 1995/01/25 23:07:33 smoot
70 * Better DBG_PRINTs, multiply/divide instead of shifts
71 *
72 * Revision 1.5 1995/01/19 23:09:10 eyhung
73 * Changed copyrights
74 *
75 * Revision 1.4 1995/01/16 08:17:08 eyhung
76 * added realQuiet
77 *
78 * Revision 1.3 1994/11/12 02:11:58 keving
79 * nothing
80 *
81 * Revision 1.2 1994/03/15 00:27:11 keving
82 * nothing
83 *
84 * Revision 1.2 1994/03/15 00:27:11 keving
85 * nothing
86 *
87 * Revision 1.1 1993/12/22 19:19:01 keving
88 * nothing
89 *
90 * Revision 1.11 1993/07/22 22:23:43 keving
91 * nothing
92 *
93 * Revision 1.10 1993/06/30 20:06:09 keving
94 * nothing
95 *
96 * Revision 1.9 1993/06/03 21:08:08 keving
97 * nothing
98 *
99 * Revision 1.8 1993/02/24 18:57:19 keving
100 * nothing
101 *
102 * Revision 1.7 1993/02/23 22:58:36 keving
103 * nothing
104 *
105 * Revision 1.6 1993/02/23 22:54:56 keving
106 * nothing
107 *
108 * Revision 1.5 1993/02/17 23:18:20 dwallach
109 * checkin prior to keving's joining the project
110 *
111 * Revision 1.4 1993/01/18 10:20:02 dwallach
112 * *** empty log message ***
113 *
114 * Revision 1.3 1993/01/18 10:17:29 dwallach
115 * RCS headers installed, code indented uniformly
116 *
117 * Revision 1.3 1993/01/18 10:17:29 dwallach
118 * RCS headers installed, code indented uniformly
119 *
120 */
121
122
123 /*==============*
124 * HEADER FILES *
125 *==============*/
126
127 #include <assert.h>
128 #include "all.h"
129 #include "mtypes.h"
130 #include "bitio.h"
131 #include "huff.h"
132 #include "postdct.h"
133 #include "opts.h"
134
135 /*==================*
136 * STATIC VARIABLES *
137 *==================*/
138
139 /* ZAG[i] is the natural-order position of the i'th element of zigzag order. */
140 int ZAG[] = {
141 0, 1, 8, 16, 9, 2, 3, 10,
142 17, 24, 32, 25, 18, 11, 4, 5,
143 12, 19, 26, 33, 40, 48, 41, 34,
144 27, 20, 13, 6, 7, 14, 21, 28,
145 35, 42, 49, 56, 57, 50, 43, 36,
146 29, 22, 15, 23, 30, 37, 44, 51,
147 58, 59, 52, 45, 38, 31, 39, 46,
148 53, 60, 61, 54, 47, 55, 62, 63
149 };
150
151 /*
152 * possible optimization: reorder the qtable in the correct zigzag order, to
153 * reduce the number of necessary lookups
154 *
155 * this table comes from the MPEG draft, p. D-16, Fig. 2-D.15.
156 */
157 int32 qtable[] = {
158 8, 16, 19, 22, 26, 27, 29, 34,
159 16, 16, 22, 24, 27, 29, 34, 37,
160 19, 22, 26, 27, 29, 34, 34, 38,
161 22, 22, 26, 27, 29, 34, 37, 40,
162 22, 26, 27, 29, 32, 35, 40, 48,
163 26, 27, 29, 32, 35, 40, 48, 58,
164 26, 27, 29, 34, 38, 46, 56, 69,
165 27, 29, 35, 38, 46, 56, 69, 83
166 };
167
168 int32 niqtable[] = {
169 16, 16, 16, 16, 16, 16, 16, 16,
170 16, 16, 16, 16, 16, 16, 16, 16,
171 16, 16, 16, 16, 16, 16, 16, 16,
172 16, 16, 16, 16, 16, 16, 16, 16,
173 16, 16, 16, 16, 16, 16, 16, 16,
174 16, 16, 16, 16, 16, 16, 16, 16,
175 16, 16, 16, 16, 16, 16, 16, 16,
176 16, 16, 16, 16, 16, 16, 16, 16
177 };
178
179 int32 *customQtable = NULL;
180 int32 *customNIQtable = NULL;
181
182 /*==================*
183 * GLOBAL VARIABLES *
184 *==================*/
185
186 extern boolean realQuiet;
187
188 /*=====================*
189 * EXPORTED PROCEDURES *
190 *=====================*/
191
192 /*===========================================================================*
193 *
194 * Mpost_UnQuantZigBlock
195 *
196 * unquantize and zig-zag (decode) a single block
197 * see section 2.4.4.1 of MPEG standard
198 *
199 * RETURNS: nothing
200 *
201 * SIDE EFFECTS: none
202 *
203 *===========================================================================*/
204 void
Mpost_UnQuantZigBlock(in,out,qscale,iblock)205 Mpost_UnQuantZigBlock(in, out, qscale, iblock)
206 FlatBlock in;
207 Block out;
208 int qscale;
209 boolean iblock;
210 {
211 register int index;
212 int start;
213 int position;
214 register int qentry;
215 int level, coeff;
216
217 if ( iblock ) {
218 /* qtable[0] must be 8 */
219 out[0][0] = (int16)(in[0] * 8);
220
221 /* don't need to do anything fancy here, because we saved orig
222 value, not encoded dc value */
223 start = 1;
224 } else {
225 start = 0;
226 }
227
228 for ( index = start; index < DCTSIZE_SQ; index++ ) {
229 position = ZAG[index];
230 level = in[index];
231
232 if (level == 0) {
233 ((int16 *)out)[position] = 0;
234 continue;
235 }
236
237
238 if ( iblock ) {
239 qentry = qtable[position] * qscale;
240 coeff = (level*qentry)/8;
241 if ( (coeff & 1) == 0 ) {
242 if ( coeff < 0 ) {
243 coeff++;
244 } else if ( coeff > 0 ) {
245 coeff--;
246 }
247 }
248 } else {
249 qentry = niqtable[position] * qscale;
250 if ( level == 0 ) {
251 coeff = 0;
252 } else if ( level < 0 ) {
253 coeff = (((2*level)-1)*qentry) / 16;
254 if ( (coeff & 1) == 0 ) {
255 coeff++;
256 }
257 } else {
258 coeff = (((2*level)+1)*qentry) >> 4;
259 if ( (coeff & 1) == 0 ) {
260 coeff--;
261 }
262 }
263
264 if ( coeff > 2047 ) {
265 coeff = 2047;
266 } else if ( coeff < -2048 ) {
267 coeff = -2048;
268 }
269 }
270
271 ((int16 *)out)[position] = coeff;
272 }
273 }
274
275
276 /*===========================================================================*
277 *
278 * Mpost_QuantZigBlock
279 *
280 * quantize and zigzags a block
281 *
282 * RETURNS: MPOST_OVERFLOW if a generated value is outside |255|
283 * MPOST_ZERO if all coeffs are zero
284 * MPOST_NON_ZERO otherwisw
285 *
286 * SIDE EFFECTS: none
287 *
288 *===========================================================================*/
289 int
Mpost_QuantZigBlock(in,out,qscale,iblock)290 Mpost_QuantZigBlock(in, out, qscale, iblock)
291 Block in;
292 FlatBlock out;
293 register int qscale;
294 int iblock;
295 {
296 register int i;
297 register int16 temp;
298 register int qentry;
299 register int position;
300 boolean nonZero = FALSE;
301 boolean overflow = FALSE;
302
303 DBG_PRINT(("Mpost_QuantZigBlock...\n"));
304 if (iblock) {
305 /*
306 * the DC coefficient is handled specially -- it's not
307 * sensitive to qscale, but everything else is
308 */
309 temp = ((int16 *) in)[ZAG[0]];
310 qentry = qtable[ZAG[0]];
311
312 if (temp < 0) {
313 temp = -temp;
314 temp += (qentry >> 1);
315 temp /= qentry;
316 temp = -temp;
317 } else {
318 temp += (qentry >> 1);
319 temp /= qentry;
320 }
321 if ( temp != 0 ) {
322 nonZero = TRUE;
323 }
324 out[0] = temp;
325
326 for (i = 1; i < DCTSIZE_SQ; i++) {
327 position = ZAG[i];
328 temp = ((int16 *) in)[position];
329 qentry = qtable[position] * qscale;
330
331 /* see 1993 MPEG doc, section D.6.3.4 */
332 if (temp < 0) {
333 temp = -temp;
334 temp = (temp << 3); /* temp > 0 */
335 temp += (qentry >> 1);
336 temp /= qentry;
337 temp = -temp;
338 } else {
339 temp = (temp << 3); /* temp > 0 */
340 temp += (qentry >> 1);
341 temp /= qentry;
342 }
343
344 if ( temp != 0 ) {
345 nonZero = TRUE;
346 out[i] = temp;
347 if (temp < -255) {
348 temp = -255;
349 overflow = TRUE;
350 } else if (temp > 255) {
351 temp = 255;
352 overflow = TRUE;
353 }
354 } else out[i]=0;
355 }
356 } else {
357 for (i = 0; i < DCTSIZE_SQ; i++) {
358 position = ZAG[i];
359 temp = ((int16 *) in)[position];
360
361 /* multiply by non-intra qtable */
362 qentry = qscale * niqtable[position];
363
364 /* see 1993 MPEG doc, D.6.4.5 */
365 temp *= 8;
366 temp /= qentry; /* truncation toward 0 -- correct */
367
368 if ( temp != 0 ) {
369 nonZero = TRUE;
370 out[i] = temp;
371 if (temp < -255) {
372 temp = -255;
373 overflow = TRUE;
374 } else if (temp > 255) {
375 temp = 255;
376 overflow = TRUE;
377 }
378
379 } else out[i]=0;
380 }
381 }
382
383 if (overflow) return MPOST_OVERFLOW;
384 if (nonZero) return MPOST_NON_ZERO;
385 return MPOST_ZERO;
386 }
387
388
389
390 /*===========================================================================*
391 *
392 * Mpost_RLEHuffIBlock
393 *
394 * generate the huffman bits from an I-block
395 *
396 * RETURNS: nothing
397 *
398 * SIDE EFFECTS: none
399 *
400 *===========================================================================*/
401 void
Mpost_RLEHuffIBlock(in,out)402 Mpost_RLEHuffIBlock(in, out)
403 FlatBlock in;
404 BitBucket *out;
405 {
406 register int i;
407 register int nzeros = 0;
408 register int16 cur;
409 register int16 acur;
410 register uint32 code;
411 register int nbits;
412
413 /*
414 * yes, Virginia, we start at 1. The DC coefficient is handled
415 * specially, elsewhere. Not here.
416 */
417 for (i = 1; i < DCTSIZE_SQ; i++) {
418 cur = in[i];
419 acur = ABS(cur);
420 if (cur) {
421 if ( (nzeros < HUFF_MAXRUN) && (acur < huff_maxlevel[nzeros])) {
422 /*
423 * encode using the Huffman tables
424 */
425
426 DBG_PRINT(("rle_huff %02d.%02d: Run %02d, Level %4d\n", i, ZAG[i], nzeros, cur));
427 code = (huff_table[nzeros])[acur];
428 nbits = (huff_bits[nzeros])[acur];
429
430 if (cur < 0) {
431 code |= 1; /* the sign bit */
432 }
433 Bitio_Write(out, code, nbits);
434 } else {
435 /*
436 * encode using the escape code
437 */
438 DBG_PRINT(("Escape\n"));
439 Bitio_Write(out, 0x1, 6); /* ESCAPE */
440 DBG_PRINT(("Run Length\n"));
441 Bitio_Write(out, nzeros, 6); /* Run-Length */
442
443 /*
444 * this shouldn't happen, but the other
445 * choice is to bomb out and dump core...
446 * Hmmm, seems to happen with small Qtable entries (1) -srs
447 */
448 if (cur < -255) {
449 cur = -255;
450 } else if (cur > 255) {
451 cur = 255;
452 }
453
454 DBG_PRINT(("Level\n"));
455 if (acur < 128) {
456 Bitio_Write(out, cur, 8);
457 } else {
458 if (cur < 0) {
459 Bitio_Write(out, 0x8001 + cur + 255, 16);
460 } else {
461 Bitio_Write(out, cur, 16);
462 }
463 }
464 }
465 nzeros = 0;
466 } else {
467 nzeros++;
468 }
469 }
470 DBG_PRINT(("End of block\n"));
471 Bitio_Write(out, 0x2, 2); /* end of block marker */
472 }
473
474
475 /*===========================================================================*
476 *
477 * Mpost_RLEHuffPBlock
478 *
479 * generate the huffman bits from an P-block
480 *
481 * RETURNS: nothing
482 *
483 * SIDE EFFECTS: none
484 *
485 *===========================================================================*/
486 void
Mpost_RLEHuffPBlock(in,out)487 Mpost_RLEHuffPBlock(in, out)
488 FlatBlock in;
489 BitBucket *out;
490 {
491 register int i;
492 register int nzeros = 0;
493 register int16 cur;
494 register int16 acur;
495 register uint32 code;
496 register int nbits;
497 boolean first_dct = TRUE;
498
499 /*
500 * yes, Virginia, we start at 0.
501 */
502 for (i = 0; i < DCTSIZE_SQ; i++) {
503 cur = in[i];
504 acur = ABS(cur);
505 if (cur) {
506 if ((nzeros < HUFF_MAXRUN) && (acur < huff_maxlevel[nzeros])) {
507 /*
508 * encode using the Huffman tables
509 */
510
511 DBG_PRINT(("rle_huff %02d.%02d: Run %02d, Level %4d\n", i, ZAG[i], nzeros, cur));
512 if ( first_dct && (nzeros == 0) && (acur == 1) ) {
513 /* actually, only needs = 0x2 */
514 code = (cur == 1) ? 0x2 : 0x3;
515 nbits = 2;
516 } else {
517 code = (huff_table[nzeros])[acur];
518 nbits = (huff_bits[nzeros])[acur];
519 }
520
521 assert(nbits);
522
523 if (cur < 0) {
524 code |= 1; /* the sign bit */
525 }
526 Bitio_Write(out, code, nbits);
527 first_dct = FALSE;
528 } else {
529 /*
530 * encode using the escape code
531 */
532 DBG_PRINT(("Escape\n"));
533 Bitio_Write(out, 0x1, 6); /* ESCAPE */
534 DBG_PRINT(("Run Length\n"));
535 Bitio_Write(out, nzeros, 6); /* Run-Length */
536
537 /*
538 * this shouldn't happen, but the other
539 * choice is to bomb out and dump core...
540 * Hmmm, seems to happen with small Qtable entries (1) -srs
541 */
542 if (cur < -255) {
543 cur = -255;
544 } else if (cur > 255) {
545 cur = 255;
546 }
547
548 DBG_PRINT(("Level\n"));
549 if (acur < 128) {
550 Bitio_Write(out, cur, 8);
551 } else {
552 if (cur < 0) {
553 Bitio_Write(out, 0x8001 + cur + 255, 16);
554 } else {
555 Bitio_Write(out, cur, 16);
556 }
557 }
558
559 first_dct = FALSE;
560 }
561 nzeros = 0;
562 } else {
563 nzeros++;
564 }
565 }
566
567 /* actually, should REALLY return FALSE and not use this! */
568
569 if ( first_dct ) { /* have to give a first_dct even if all 0's */
570 fprintf(stderr, "HUFF called with all-zero coefficients\n");
571 fprintf(stderr, "exiting...\n");
572 exit(1);
573 }
574
575 DBG_PRINT(("End of block\n"));
576 Bitio_Write(out, 0x2, 2); /* end of block marker */
577 }
578
579
580 /*===========================================================================*
581 *
582 * CalcRLEHuffLength
583 *
584 * count the huffman bits for an P-block
585 *
586 * RETURNS: number of bits
587 *
588 * SIDE EFFECTS: none
589 *
590 *===========================================================================*/
591 int
CalcRLEHuffLength(in)592 CalcRLEHuffLength(in)
593 FlatBlock in;
594 {
595 register int i;
596 register int nzeros = 0;
597 register int16 cur;
598 register int16 acur;
599 register int nbits;
600 register int countbits=0;
601 boolean first_dct = TRUE;
602
603 for (i = 0; i < DCTSIZE_SQ; i++) {
604 cur = in[i];
605 acur = ABS(cur);
606 if (cur) {
607 if ((nzeros < HUFF_MAXRUN) && (acur < huff_maxlevel[nzeros])) {
608 /*
609 * encode using the Huffman tables
610 */
611
612 if ( first_dct && (nzeros == 0) && (acur == 1) ) {
613 nbits = 2;
614 } else {
615 nbits = (huff_bits[nzeros])[acur];
616 }
617 countbits += nbits;
618 first_dct = FALSE;
619 } else {
620 countbits += 12; /* ESCAPE + runlength */
621
622 if (acur < 128) {
623 countbits += 8;
624 } else {
625 countbits += 16;
626 }
627
628 first_dct = FALSE;
629 }
630 nzeros = 0;
631 } else {
632 nzeros++;
633 }
634 }
635
636 countbits += 2; /* end of block marker */
637 return countbits;
638 }
639