4 * Code for JPEG lossless decoding. Large parts are grabbed from the IJG
8 * $Id: huffd.c,v 1.1 2003/10/21 12:08:53 jpr Exp $
20 #define RST0 0xD0 /* RST0 marker code */
22 static long getBuffer; /* current bit-extraction buffer */
23 static int bitsLeft; /* # of unused bits in it */
26 * The following variables keep track of the input buffer
27 * for the JPEG data, which is read by ReadJpegData.
29 Uchar *inputBuffer; /* Input buffer for JPEG data */
30 int inputBufferOffset = 0; /* Offset of current byte */
33 * Code for extracting the next N bits from the input stream.
34 * (N never exceeds 15 for JPEG data.)
35 * This needs to go as fast as possible!
37 * We read source bytes into getBuffer and dole out bits as needed.
38 * If getBuffer already contains enough bits, they are fetched in-line
39 * by the macros get_bits() and get_bit(). When there aren't enough bits,
40 * FillBitBuffer is called; it will attempt to fill getBuffer to the
41 * "high water mark", then extract the desired number of bits. The idea,
42 * of course, is to minimize the function-call overhead cost of entering
44 * On most machines MIN_GET_BITS should be 25 to allow the full 32-bit width
45 * of getBuffer to be used. (On machines with wider words, an even larger
46 * buffer could be used.)
49 #define BITS_PER_LONG (8*sizeof(long))
50 #define MIN_GET_BITS (BITS_PER_LONG-7) /* max value for long getBuffer */
53 * bmask[n] is mask for n rightmost bits
55 static int bmask[] = {0x0000,
56 0x0001, 0x0003, 0x0007, 0x000F,
57 0x001F, 0x003F, 0x007F, 0x00FF,
58 0x01FF, 0x03FF, 0x07FF, 0x0FFF,
59 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF};
62 *--------------------------------------------------------------
66 * Load up the bit buffer with at least nbits
67 * Process any stuffed bytes at this time.
73 * The bitwise global variables are updated.
75 *--------------------------------------------------------------
77 #define FillBitBuffer(nbits) { \
79 while (bitsLeft < MIN_GET_BITS) { \
81 /* If it's 0xFF, check and discard stuffed zero byte */ \
83 c2 = GetJpegChar (); \
90 /* OK, load c into getBuffer */ \
91 getBuffer = (getBuffer << 8) | c; \
94 }/*endof FillBitBuffer*/
96 /* Macros to make things go at some speed! */
97 /* NB: parameter to get_bits should be simple variable, not expression */
99 #define show_bits(nbits,rv) { \
100 if (bitsLeft < nbits) FillBitBuffer(nbits); \
101 rv = (getBuffer >> (bitsLeft-(nbits))) & bmask[nbits]; \
104 #define show_bits8(rv) { \
105 if (bitsLeft < 8) FillBitBuffer(8); \
106 rv = (getBuffer >> (bitsLeft-8)) & 0xff; \
109 #define flush_bits(nbits) { \
110 bitsLeft -= (nbits); \
113 #define get_bits(nbits,rv) { \
114 if (bitsLeft < nbits) FillBitBuffer(nbits); \
115 rv = ((getBuffer >> (bitsLeft -= (nbits)))) & bmask[nbits]; \
118 #define get_bit(rv) { \
119 if (!bitsLeft) FillBitBuffer(1); \
120 rv = (getBuffer >> (--bitsLeft)) & 1; \
124 *--------------------------------------------------------------
128 * Output one row of pixels stored in RowBuf.
134 * One row of pixels are write to file pointed by outFile.
136 *--------------------------------------------------------------
140 void PmPutRow24(MCU *RowBuf, int numCol, unsigned char **image)
144 for (col = 0; col < numCol; col++)
146 /* take each RGB column */
147 **image = (unsigned char) RowBuf[col][0];
148 *(*image+1) = (unsigned char) RowBuf[col][1];
149 *(*image+2) = (unsigned char) RowBuf[col][2];
155 void PmPutRow16(MCU *RowBuf, int numCol, unsigned short **image)
159 for (col = 0; col < numCol; col++)
161 **image = (unsigned short) RowBuf[col][0];
167 void PmPutRow8(MCU *RowBuf, int numCol, unsigned char **image)
171 for (col = 0; col < numCol; col++)
173 **image = (unsigned char) RowBuf[col][0];
182 *--------------------------------------------------------------
186 * Taken from Figure F.16: extract next coded symbol from
187 * input stream. This should becode a macro.
193 * Bitstream is parsed.
195 *--------------------------------------------------------------
197 #define HuffDecode(htbl,rv) \
202 * If the huffman code is less than 8 bits, we can use the fast \
203 * table lookup to get its value. It's more than 8 bits about \
204 * 3-4% of the time. \
207 if (htbl->numbits[code]) { \
208 flush_bits(htbl->numbits[code]); \
209 rv=htbl->value[code]; \
214 while (code > htbl->maxcode[l]) { \
216 code = (code << 1) | temp; \
221 * With garbage input we may reach the sentinel value l = 17. \
225 fprintf (stderr, "Corrupt JPEG data: bad Huffman code\n"); \
226 rv = 0; /* fake a zero as the safest result */ \
228 rv = htbl->huffval[htbl->valptr[l] + \
229 ((int)(code - htbl->mincode[l]))]; \
235 *--------------------------------------------------------------
239 * Code and table for Figure F.12: extend sign bit
242 * The extended value.
247 *--------------------------------------------------------------
249 static int extendTest[16] = /* entry n is 2**(n-1) */
250 {0, 0x0001, 0x0002, 0x0004, 0x0008, 0x0010, 0x0020, 0x0040, 0x0080,
251 0x0100, 0x0200, 0x0400, 0x0800, 0x1000, 0x2000, 0x4000};
253 static int extendOffset[16] = /* entry n is (-1 << n) + 1 */
254 {0, ((-1) << 1) + 1, ((-1) << 2) + 1, ((-1) << 3) + 1, ((-1) << 4) + 1,
255 ((-1) << 5) + 1, ((-1) << 6) + 1, ((-1) << 7) + 1, ((-1) << 8) + 1,
256 ((-1) << 9) + 1, ((-1) << 10) + 1, ((-1) << 11) + 1, ((-1) << 12) + 1,
257 ((-1) << 13) + 1, ((-1) << 14) + 1, ((-1) << 15) + 1};
259 #define HuffExtend(x,s) { \
260 if ((x) < extendTest[s]) { \
261 (x) += extendOffset[s]; \
266 *--------------------------------------------------------------
270 * Initialize for a Huffman-compressed scan.
271 * This is invoked after reading the SOS marker.
279 *--------------------------------------------------------------
281 void HuffDecoderInit (DecompressInfo *dcPtr)
284 JpegComponentInfo *compptr;
286 * Initialize siv-lyon1.fr
291 for (ci = 0; ci < dcPtr->compsInScan; ci++) {
292 compptr = dcPtr->curCompInfo[ci];
294 * Make sure requested tables are present
296 if (dcPtr->dcHuffTblPtrs[compptr->dcTblNo] == NULL) {
297 fprintf (stderr, "Error: Use of undefined Huffman table\n");
299 dcPtr->error = -1; return;
303 * Compute derived values for Huffman tables.
304 * We may do this more than once for same table, but it's not a
307 FixHuffTbl (dcPtr->dcHuffTblPtrs[compptr->dcTblNo]);
311 * Initialize restart stuff
313 dcPtr->restartInRows = (dcPtr->restartInterval)/(dcPtr->imageWidth);
314 dcPtr->restartRowsToGo = dcPtr->restartInRows;
315 dcPtr->nextRestartNum = 0;
319 *--------------------------------------------------------------
323 * Check for a restart marker & resynchronize decoder.
329 * BitStream is parsed, bit buffer is reset, etc.
331 *--------------------------------------------------------------
333 static void ProcessRestart(DecompressInfo *dcPtr)
339 * Throw away any unused bits remaining in bit buffer
341 nbytes = bitsLeft / 8;
345 * Scan for next JPEG marker
350 { /* skip any non-FF bytes */
357 { /* skip any duplicate FFs */
359 * we don't increment nbytes here since extra FFs are legal
365 while (c == 0); /* repeat if it was a stuffed FF/00 */
367 if (c != (RST0 + dcPtr->nextRestartNum)) {
370 * Uh-oh, the restart markers have been messed up too.
373 fprintf (stderr, "Error: Corrupt JPEG data. Exiting...\n");
375 dcPtr->error = -1; return;
379 * Update restart state
381 dcPtr->restartRowsToGo = dcPtr->restartInRows;
382 dcPtr->nextRestartNum = (dcPtr->nextRestartNum + 1) & 7;
386 *--------------------------------------------------------------
390 * Decode the first raster line of samples at the start of
391 * the scan and at the beginning of each restart interval.
392 * This includes modifying the component value so the real
393 * value, not the difference is returned.
399 * Bitstream is parsed.
401 *--------------------------------------------------------------
403 void DecodeFirstRow (DecompressInfo *dcPtr, MCU *curRowBuf)
405 register short curComp,ci;
406 register int s,col,compsInScan,numCOL;
407 register JpegComponentInfo *compptr;
410 Pr=dcPtr->dataPrecision;
412 compsInScan=dcPtr->compsInScan;
413 numCOL=dcPtr->imageWidth;
416 * the start of the scan or at the beginning of restart interval.
418 for (curComp = 0; curComp < compsInScan; curComp++) {
419 ci = dcPtr->MCUmembership[curComp];
420 compptr = dcPtr->curCompInfo[ci];
421 dctbl = dcPtr->dcHuffTblPtrs[compptr->dcTblNo];
424 * Section F.2.2.1: decode the difference
426 HuffDecode (dctbl,s);
435 * Add the predictor to the difference.
437 curRowBuf[0][curComp]=d+(1<<(Pr-Pt-1));
441 * the rest of the first row
443 for (col=1; col<numCOL; col++) {
444 for (curComp = 0; curComp < compsInScan; curComp++) {
445 ci = dcPtr->MCUmembership[curComp];
446 compptr = dcPtr->curCompInfo[ci];
447 dctbl = dcPtr->dcHuffTblPtrs[compptr->dcTblNo];
450 * Section F.2.2.1: decode the difference
452 HuffDecode (dctbl,s);
461 * Add the predictor to the difference.
463 curRowBuf[col][curComp]=d+curRowBuf[col-1][curComp];
467 if (dcPtr->restartInRows) {
468 (dcPtr->restartRowsToGo)--;
470 }/*endof DecodeFirstRow*/
473 *--------------------------------------------------------------
477 * Decode the input stream. This includes modifying
478 * the component value so the real value, not the
479 * difference is returned.
485 * Bitstream is parsed.
487 *--------------------------------------------------------------
489 void DecodeImage (DecompressInfo *dcPtr, unsigned short **image, int depth)
491 register int s, d, col, row;
492 register short curComp, ci;
494 JpegComponentInfo *compptr;
496 int numCOL, numROW, compsInScan;
497 MCU *prevRowBuf, *curRowBuf;
498 int imagewidth, Pt, psv;
499 unsigned short *image16tmp;
500 unsigned char *image8tmp, *image24tmp;
502 numCOL = imagewidth=dcPtr->imageWidth;
503 numROW = dcPtr->imageHeight;
504 compsInScan = dcPtr->compsInScan;
507 prevRowBuf = mcuROW2;
511 image8tmp = (unsigned char *) *image;
512 else if (depth == 16)
513 image16tmp = (unsigned short *) *image;
514 else if (depth == 24)
515 image24tmp = (unsigned char *) *image;
517 fprintf(stderr,"Unsupported image depth %d\n",depth);
518 dcPtr->error = -1; return;
522 * Decode the first row of image. Output the row and
523 * turn this row into a previous row for later predictor
527 DecodeFirstRow (dcPtr, curRowBuf);
530 PmPutRow8 (curRowBuf, numCOL, &image8tmp);
531 else if (depth == 16)
532 PmPutRow16 (curRowBuf, numCOL, &image16tmp);
533 else if (depth == 24)
534 PmPutRow24 (curRowBuf, numCOL, &image24tmp);
536 swap(MCU *, prevRowBuf, curRowBuf);
538 /* optimal case : 8 bit image, one color component, no restartInRows */
539 if ((depth == 8) && (compsInScan == 1) && (dcPtr->restartInRows == 0))
542 unsigned char *curPixelPtr;
545 /* initializations */
548 ci = dcPtr->MCUmembership[curComp];
549 compptr = dcPtr->curCompInfo[ci];
550 dctbl = dcPtr->dcHuffTblPtrs[compptr->dcTblNo];
551 curPixelPtr = image8tmp;
553 for (row=1; row<numROW; row++)
555 /* Upper neighbor is predictor for the first column */
556 /* Section F.2.2.1: decode the difference */
557 HuffDecode (dctbl,s);
558 if (s) { get_bits(s,d); HuffExtend(d,s); }
560 *curPixelPtr = (unsigned char) (d + *(curPixelPtr - numCOL));
564 for (col=1; col < numCOL; col++) {
565 /* Section F.2.2.1: decode the difference */
566 HuffDecode (dctbl, s);
567 if (s) { get_bits (s, d); HuffExtend (d, s); }
570 *curPixelPtr = (unsigned char) (d + *(curPixelPtr - 1));
576 for (col=1; col < numCOL; col++) {
577 /* Section F.2.2.1: decode the difference */
578 HuffDecode (dctbl, s);
579 if (s) { get_bits (s, d); HuffExtend (d, s); }
582 /* Predict : All predictors are calculated according to psv */
584 case 0: predictor = 0; break;
585 case 2: predictor = *(curPixelPtr - numCOL); break;
586 case 3: predictor = *(curPixelPtr - numCOL - 1); break;
587 case 4: upper = *(curPixelPtr - numCOL);
588 left = *(curPixelPtr - 1);
589 diag = *(curPixelPtr - numCOL - 1);
590 predictor = left + upper - diag; break;
591 case 5: upper = *(curPixelPtr - numCOL);
592 left = *(curPixelPtr - 1);
593 diag = *(curPixelPtr - numCOL - 1);
594 predictor = left+((upper-diag)>>1); break;
595 case 6: upper = *(curPixelPtr - numCOL);
596 left = *(curPixelPtr - 1);
597 diag = *(curPixelPtr - numCOL - 1);
598 predictor = upper+((left-diag)>>1); break;
599 case 7: upper = *(curPixelPtr - numCOL);
600 left = *(curPixelPtr - 1);
601 predictor = (left+upper)>>1; break;
602 default : predictor = 0;
605 *curPixelPtr = (unsigned char) (d + predictor);
613 else { /*normal case with 16 bits or color or ...*/
614 for (row=1; row<numROW; row++) {
616 * Account for restart interval, process restart marker if needed.
618 if (dcPtr->restartInRows)
620 if (dcPtr->restartRowsToGo == 0)
622 ProcessRestart (dcPtr); if (dcPtr->error) return;
624 * Reset predictors at restart.
626 DecodeFirstRow(dcPtr,curRowBuf);
628 PmPutRow8 (curRowBuf, numCOL, &image8tmp);
629 else if (depth == 16)
630 PmPutRow16 (curRowBuf, numCOL, &image16tmp);
631 else if (depth == 24)
632 PmPutRow24 (curRowBuf, numCOL, &image24tmp);
634 swap(MCU *,prevRowBuf,curRowBuf);
637 dcPtr->restartRowsToGo--;
641 * For the rest of the column on this row, predictor
642 * calculations are base on PSV.
645 /* several color components to decode (RGB colors)*/
647 /* The upper neighbors are predictors for the first column. */
648 for (curComp = 0; curComp < compsInScan; curComp++)
650 ci = dcPtr->MCUmembership[curComp];
651 compptr = dcPtr->curCompInfo[ci];
652 dctbl = dcPtr->dcHuffTblPtrs[compptr->dcTblNo];
654 /* Section F.2.2.1: decode the difference */
655 HuffDecode (dctbl,s);
656 if (s) { get_bits(s,d); HuffExtend(d,s); }
658 curRowBuf[0][curComp]=d+prevRowBuf[0][curComp];
661 for (col=1; col < numCOL; col++)
663 for (curComp = 0; curComp < compsInScan; curComp++)
665 ci = dcPtr->MCUmembership[curComp];
666 compptr = dcPtr->curCompInfo[ci];
667 dctbl = dcPtr->dcHuffTblPtrs[compptr->dcTblNo];
669 /* Section F.2.2.1: decode the difference */
670 HuffDecode (dctbl, s);
671 if (s) { get_bits (s, d); HuffExtend (d, s); }
674 QuickPredict (col,curComp,curRowBuf,prevRowBuf,psv,&predictor);
676 curRowBuf[col][curComp]=d+predictor;
681 PmPutRow8 (curRowBuf, numCOL, &image8tmp);
682 else if (depth == 16)
683 PmPutRow16 (curRowBuf, numCOL, &image16tmp);
684 else if (depth == 24)
685 PmPutRow24 (curRowBuf, numCOL, &image24tmp);
687 swap(MCU *, prevRowBuf, curRowBuf);
691 }/*endofmethod DecodeImage*/