src/jpeg.c

   1 /*
   2  * Copyright (C) 2001, Novell Inc.
   3  * Copyright (C) 2010  Kevin O'Connor <kevin@koconnor.net>
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  *
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  *
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  *
  17  * 3. Neither the name of Novell nor the names of the contributors may
  18  *    be used to endorse or promote products derived from this software
  19  *    without specific prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR "AS IS" AND ANY EXPRESS OR
  22  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  23  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  24  * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
  25  * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  26  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  27  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  29  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
  30  * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  31  * POSSIBILITY OF SUCH DAMAGE.
  32  *
  33  */
  34
  35 /*
  36  * a tiny jpeg decoder.
  37  *
  38  * written in August 2001 by Michael Schroeder <mls@suse.de>
  39  *
  40  */
  41
  42 #define __LITTLE_ENDIAN
  43 #include "util.h"
  44 #include "jpeg.h"
  45 #define ISHIFT 11
  46
  47 #define IFIX(a) ((int)((a) * (1 << ISHIFT) + .5))
  48 #define IMULT(a, b) (((a) * (b)) >> ISHIFT)
  49 #define ITOINT(a) ((a) >> ISHIFT)
  50
  51 #ifndef __P
  52 # define __P(x) x
  53 #endif
  54
  55 /* special markers */
  56 #define M_BADHUFF        -1
  57 #define M_EOF                0x80
  58
  59 struct in {
  60     unsigned char *p;
  61     unsigned int bits;
  62     int left;
  63     int marker;
  64
  65     int (*func) __P((void *));
  66     void *data;
  67 };
  68
  69 /*********************************/
  70 struct dec_hufftbl;
  71 struct enc_hufftbl;
  72
  73 union hufftblp {
  74     struct dec_hufftbl *dhuff;
  75     struct enc_hufftbl *ehuff;
  76 };
  77
  78 struct scan {
  79     int dc;               /* old dc value */
  80
  81     union hufftblp hudc;
  82     union hufftblp huac;
  83     int next;             /* when to switch to next scan */
  84
  85     int cid;              /* component id */
  86     int hv;               /* horiz/vert, copied from comp */
  87     int tq;               /* quant tbl, copied from comp */
  88 };
  89
  90 /*********************************/
  91
  92 #define DECBITS 10        /* seems to be the optimum */
  93
  94 struct dec_hufftbl {
  95     int maxcode[17];
  96     int valptr[16];
  97     unsigned char vals[256];
  98     unsigned int llvals[1 << DECBITS];
  99 };
 100
 101 static void decode_mcus __P((struct in *, int *, int, struct scan *, int *));
 102 static int dec_readmarker __P((struct in *));
 103 static void dec_makehuff __P((struct dec_hufftbl *, int *, unsigned char *));
 104
 105 static void setinput __P((struct in *, unsigned char *));
 106 /*********************************/
 107
 108 #undef PREC
 109 #define PREC int
 110
 111 static void idctqtab __P((unsigned char *, PREC *));
 112 static void idct __P((int *, int *, PREC *, PREC, int));
 113 static void scaleidctqtab __P((PREC *, PREC));
 114
 115 /*********************************/
 116
 117 static void initcol __P((PREC[][64]));
 118
 119 static void col221111 __P((int *, unsigned char *, int));
 120 static void col221111_16 __P((int *, unsigned char *, int));
 121 static void col221111_32 __P((int *, unsigned char *, int));
 122
 123 /*********************************/
 124
 125 #define ERR_NO_SOI 1
 126 #define ERR_NOT_8BIT 2
 127 #define ERR_HEIGHT_MISMATCH 3
 128 #define ERR_WIDTH_MISMATCH 4
 129 #define ERR_BAD_WIDTH_OR_HEIGHT 5
 130 #define ERR_TOO_MANY_COMPPS 6
 131 #define ERR_ILLEGAL_HV 7
 132 #define ERR_QUANT_TABLE_SELECTOR 8
 133 #define ERR_NOT_YCBCR_221111 9
 134 #define ERR_UNKNOWN_CID_IN_SCAN 10
 135 #define ERR_NOT_SEQUENTIAL_DCT 11
 136 #define ERR_WRONG_MARKER 12
 137 #define ERR_NO_EOI 13
 138 #define ERR_BAD_TABLES 14
 139 #define ERR_DEPTH_MISMATCH 15
 140
 141 /*********************************/
 142
 143 #define M_SOI   0xd8
 144 #define M_APP0  0xe0
 145 #define M_DQT   0xdb
 146 #define M_SOF0  0xc0
 147 #define M_DHT   0xc4
 148 #define M_DRI   0xdd
 149 #define M_SOS   0xda
 150 #define M_RST0  0xd0
 151 #define M_EOI   0xd9
 152 #define M_COM   0xfe
 153
 154 struct comp {
 155     int cid;
 156     int hv;
 157     int tq;
 158 };
 159
 160 #define MAXCOMP 4
 161 struct jpginfo {
 162     int nc;   /* number of components */
 163     int ns;   /* number of scans */
 164     int dri;  /* restart interval */
 165     int nm;   /* mcus til next marker */
 166     int rm;   /* next restart marker */
 167 };
 168
 169 struct jpeg_decdata {
 170     int dcts[6 * 64 + 16];
 171     int out[64 * 6];
 172     int dquant[3][64];
 173
 174     unsigned char *datap;
 175     struct jpginfo info;
 176     struct comp comps[MAXCOMP];
 177     struct scan dscans[MAXCOMP];
 178     unsigned char quant[4][64];
 179     struct dec_hufftbl dhuff[4];
 180     struct in in;
 181
 182     int height, width;
 183 };
 184
 185 static int getbyte(struct jpeg_decdata *jpeg)
 186 {
 187     return *jpeg->datap++;
 188 }
 189
 190 static int getword(struct jpeg_decdata *jpeg)
 191 {
 192     int c1, c2;
 193     c1 = *jpeg->datap++;
 194     c2 = *jpeg->datap++;
 195     return c1 << 8 | c2;
 196 }
 197
 198 static int readtables(struct jpeg_decdata *jpeg, int till)
 199 {
 200     int m, l, i, j, lq, pq, tq;
 201     int tc, th, tt;
 202
 203     for (;;) {
 204         if (getbyte(jpeg) != 0xff)
 205             return -1;
 206         if ((m = getbyte(jpeg)) == till)
 207             break;
 208
 209         switch (m) {
 210         case 0xc2:
 211             return 0;
 212
 213         case M_DQT:
 214             lq = getword(jpeg);
 215             while (lq > 2) {
 216                 pq = getbyte(jpeg);
 217                 tq = pq & 15;
 218                 if (tq > 3)
 219                     return -1;
 220                 pq >>= 4;
 221                 if (pq != 0)
 222                     return -1;
 223                 for (i = 0; i < 64; i++)
 224                     jpeg->quant[tq][i] = getbyte(jpeg);
 225                 lq -= 64 + 1;
 226             }
 227             break;
 228
 229         case M_DHT:
 230             l = getword(jpeg);
 231             while (l > 2) {
 232                 int hufflen[16], k;
 233                 unsigned char huffvals[256];
 234
 235                 tc = getbyte(jpeg);
 236                 th = tc & 15;
 237                 tc >>= 4;
 238                 tt = tc * 2 + th;
 239                 if (tc > 1 || th > 1)
 240                     return -1;
 241                 for (i = 0; i < 16; i++)
 242                     hufflen[i] = getbyte(jpeg);
 243                 l -= 1 + 16;
 244                 k = 0;
 245                 for (i = 0; i < 16; i++) {
 246                     for (j = 0; j < hufflen[i]; j++)
 247                         huffvals[k++] = getbyte(jpeg);
 248                     l -= hufflen[i];
 249                 }
 250                 dec_makehuff(jpeg->dhuff + tt, hufflen, huffvals);
 251             }
 252             break;
 253
 254         case M_DRI:
 255             l = getword(jpeg);
 256             jpeg->info.dri = getword(jpeg);
 257             break;
 258
 259         default:
 260             l = getword(jpeg);
 261             while (l-- > 2)
 262                 getbyte(jpeg);
 263             break;
 264         }
 265     }
 266     return 0;
 267 }
 268
 269 static void dec_initscans(struct jpeg_decdata *jpeg)
 270 {
 271     int i;
 272
 273     jpeg->info.nm = jpeg->info.dri + 1;
 274     jpeg->info.rm = M_RST0;
 275     for (i = 0; i < jpeg->info.ns; i++)
 276         jpeg->dscans[i].dc = 0;
 277 }
 278
 279 static int dec_checkmarker(struct jpeg_decdata *jpeg)
 280 {
 281     int i;
 282
 283     if (dec_readmarker(&jpeg->in) != jpeg->info.rm)
 284         return -1;
 285     jpeg->info.nm = jpeg->info.dri;
 286     jpeg->info.rm = (jpeg->info.rm + 1) & ~0x08;
 287     for (i = 0; i < jpeg->info.ns; i++)
 288         jpeg->dscans[i].dc = 0;
 289     return 0;
 290 }
 291
 292 struct jpeg_decdata *jpeg_alloc(void)
 293 {
 294     struct jpeg_decdata *jpeg = malloc_tmphigh(sizeof(*jpeg));
 295     return jpeg;
 296 }
 297
 298 int jpeg_decode(struct jpeg_decdata *jpeg, unsigned char *buf)
 299 {
 300     int i, j, m, tac, tdc;
 301
 302     if (!jpeg || !buf)
 303         return -1;
 304     jpeg->datap = buf;
 305     if (getbyte(jpeg) != 0xff)
 306         return ERR_NO_SOI;
 307     if (getbyte(jpeg) != M_SOI)
 308         return ERR_NO_SOI;
 309     if (readtables(jpeg, M_SOF0))
 310         return ERR_BAD_TABLES;
 311     getword(jpeg);
 312     i = getbyte(jpeg);
 313     if (i != 8)
 314         return ERR_NOT_8BIT;
 315     jpeg->height = getword(jpeg);
 316     jpeg->width = getword(jpeg);
 317     if ((jpeg->height & 15) || (jpeg->width & 15))
 318         return ERR_BAD_WIDTH_OR_HEIGHT;
 319     jpeg->info.nc = getbyte(jpeg);
 320     if (jpeg->info.nc > MAXCOMP)
 321         return ERR_TOO_MANY_COMPPS;
 322     for (i = 0; i < jpeg->info.nc; i++) {
 323         int h, v;
 324         jpeg->comps[i].cid = getbyte(jpeg);
 325         jpeg->comps[i].hv = getbyte(jpeg);
 326         v = jpeg->comps[i].hv & 15;
 327         h = jpeg->comps[i].hv >> 4;
 328         jpeg->comps[i].tq = getbyte(jpeg);
 329         if (h > 3 || v > 3)
 330             return ERR_ILLEGAL_HV;
 331         if (jpeg->comps[i].tq > 3)
 332             return ERR_QUANT_TABLE_SELECTOR;
 333     }
 334     if (readtables(jpeg, M_SOS))
 335         return ERR_BAD_TABLES;
 336     getword(jpeg);
 337     jpeg->info.ns = getbyte(jpeg);
 338     if (jpeg->info.ns != 3)
 339         return ERR_NOT_YCBCR_221111;
 340     for (i = 0; i < 3; i++) {
 341         jpeg->dscans[i].cid = getbyte(jpeg);
 342         tdc = getbyte(jpeg);
 343         tac = tdc & 15;
 344         tdc >>= 4;
 345         if (tdc > 1 || tac > 1)
 346             return ERR_QUANT_TABLE_SELECTOR;
 347         for (j = 0; j < jpeg->info.nc; j++)
 348             if (jpeg->comps[j].cid == jpeg->dscans[i].cid)
 349                 break;
 350         if (j == jpeg->info.nc)
 351             return ERR_UNKNOWN_CID_IN_SCAN;
 352         jpeg->dscans[i].hv = jpeg->comps[j].hv;
 353         jpeg->dscans[i].tq = jpeg->comps[j].tq;
 354         jpeg->dscans[i].hudc.dhuff = &jpeg->dhuff[tdc];
 355         jpeg->dscans[i].huac.dhuff = &jpeg->dhuff[2 + tac];
 356     }
 357
 358     i = getbyte(jpeg);
 359     j = getbyte(jpeg);
 360     m = getbyte(jpeg);
 361
 362     if (i != 0 || j != 63 || m != 0)
 363         return ERR_NOT_SEQUENTIAL_DCT;
 364
 365     if (jpeg->dscans[0].cid != 1 || jpeg->dscans[1].cid != 2
 366         || jpeg->dscans[2].cid != 3)
 367         return ERR_NOT_YCBCR_221111;
 368
 369     if (jpeg->dscans[0].hv != 0x22 || jpeg->dscans[1].hv != 0x11
 370         || jpeg->dscans[2].hv != 0x11)
 371         return ERR_NOT_YCBCR_221111;
 372
 373     idctqtab(jpeg->quant[jpeg->dscans[0].tq], jpeg->dquant[0]);
 374     idctqtab(jpeg->quant[jpeg->dscans[1].tq], jpeg->dquant[1]);
 375     idctqtab(jpeg->quant[jpeg->dscans[2].tq], jpeg->dquant[2]);
 376     initcol(jpeg->dquant);
 377     setinput(&jpeg->in, jpeg->datap);
 378
 379 #if 0
 380     /* landing zone */
 381     img[len] = 0;
 382     img[len + 1] = 0xff;
 383     img[len + 2] = M_EOF;
 384 #endif
 385
 386     dec_initscans(jpeg);
 387
 388     return 0;
 389 }
 390
 391 void jpeg_get_size(struct jpeg_decdata *jpeg, int *width, int *height)
 392 {
 393     *width = jpeg->width;
 394     *height = jpeg->height;
 395 }
 396
 397 int jpeg_show(struct jpeg_decdata *jpeg, unsigned char *pic
 398               , int width, int height, int depth)
 399 {
 400     int m, mcusx, mcusy, mx, my;
 401     int max[6];
 402
 403     if (jpeg->height != height)
 404         return ERR_HEIGHT_MISMATCH;
 405     if (jpeg->width != width)
 406         return ERR_WIDTH_MISMATCH;
 407
 408     mcusx = jpeg->width >> 4;
 409     mcusy = jpeg->height >> 4;
 410
 411     jpeg->dscans[0].next = 6 - 4;
 412     jpeg->dscans[1].next = 6 - 4 - 1;
 413     jpeg->dscans[2].next = 6 - 4 - 1 - 1;        /* 411 encoding */
 414     for (my = 0; my < mcusy; my++) {
 415         for (mx = 0; mx < mcusx; mx++) {
 416             if (jpeg->info.dri && !--jpeg->info.nm)
 417                 if (dec_checkmarker(jpeg))
 418                     return ERR_WRONG_MARKER;
 419
 420             decode_mcus(&jpeg->in, jpeg->dcts, 6, jpeg->dscans, max);
 421             idct(jpeg->dcts, jpeg->out, jpeg->dquant[0],
 422                  IFIX(128.5), max[0]);
 423             idct(jpeg->dcts + 64, jpeg->out + 64, jpeg->dquant[0],
 424                  IFIX(128.5), max[1]);
 425             idct(jpeg->dcts + 128, jpeg->out + 128,
 426                  jpeg->dquant[0], IFIX(128.5), max[2]);
 427             idct(jpeg->dcts + 192, jpeg->out + 192,
 428                  jpeg->dquant[0], IFIX(128.5), max[3]);
 429             idct(jpeg->dcts + 256, jpeg->out + 256,
 430                  jpeg->dquant[1], IFIX(0.5), max[4]);
 431             idct(jpeg->dcts + 320, jpeg->out + 320,
 432                  jpeg->dquant[2], IFIX(0.5), max[5]);
 433
 434             switch (depth) {
 435             case 32:
 436                 col221111_32(jpeg->out,
 437                              pic + (my * 16 * mcusx + mx) * 16 * 4,
 438                              mcusx * 16 * 4);
 439                 break;
 440             case 24:
 441                 col221111(jpeg->out,
 442                           pic + (my * 16 * mcusx + mx) * 16 * 3,
 443                           mcusx * 16 * 3);
 444                 break;
 445             case 16:
 446                 col221111_16(jpeg->out,
 447                              pic + (my * 16 * mcusx + mx) * (16 * 2),
 448                              mcusx * (16 * 2));
 449                 break;
 450             default:
 451                 return ERR_DEPTH_MISMATCH;
 452                 break;
 453             }
 454         }
 455     }
 456
 457     m = dec_readmarker(&jpeg->in);
 458     if (m != M_EOI)
 459         return ERR_NO_EOI;
 460
 461     return 0;
 462 }
 463
 464 /****************************************************************/
 465 /**************       huffman decoder             ***************/
 466 /****************************************************************/
 467
 468 static int fillbits __P((struct in *, int, unsigned int));
 469 static int dec_rec2 __P((struct in *, struct dec_hufftbl *, int *, int, int));
 470
 471 static void setinput(struct in *in, unsigned char *p)
 472 {
 473     in->p = p;
 474     in->left = 0;
 475     in->bits = 0;
 476     in->marker = 0;
 477 }
 478
 479 static int fillbits(struct in *in, int le, unsigned int bi)
 480 {
 481     int b, m;
 482
 483     if (in->marker) {
 484         if (le <= 16)
 485             in->bits = bi << 16, le += 16;
 486         return le;
 487     }
 488     while (le <= 24) {
 489         b = *in->p++;
 490         if (b == 0xff && (m = *in->p++) != 0) {
 491             if (m == M_EOF) {
 492                 if (in->func && (m = in->func(in->data)) == 0)
 493                     continue;
 494             }
 495             in->marker = m;
 496             if (le <= 16)
 497                 bi = bi << 16, le += 16;
 498             break;
 499         }
 500         bi = bi << 8 | b;
 501         le += 8;
 502     }
 503     in->bits = bi;                /* tmp... 2 return values needed */
 504     return le;
 505 }
 506
 507 static int dec_readmarker(struct in *in)
 508 {
 509     int m;
 510
 511     in->left = fillbits(in, in->left, in->bits);
 512     if ((m = in->marker) == 0)
 513         return 0;
 514     in->left = 0;
 515     in->marker = 0;
 516     return m;
 517 }
 518
 519 #define LEBI_DCL       int le, bi
 520 #define LEBI_GET(in)   (le = in->left, bi = in->bits)
 521 #define LEBI_PUT(in)   (in->left = le, in->bits = bi)
 522
 523 #define GETBITS(in, n) (                                     \
 524   (le < (n) ? le = fillbits(in, le, bi), bi = in->bits : 0), \
 525   (le -= (n)),                                               \
 526   bi >> le & ((1 << (n)) - 1)                                \
 527 )
 528
 529 #define UNGETBITS(in, n) ( \
 530   le += (n)                \
 531 )
 532
 533
 534 static int dec_rec2(struct in *in, struct dec_hufftbl *hu, int *runp,
 535                     int c, int i)
 536 {
 537     LEBI_DCL;
 538
 539     LEBI_GET(in);
 540     if (i) {
 541         UNGETBITS(in, i & 127);
 542         *runp = i >> 8 & 15;
 543         i >>= 16;
 544     } else {
 545         for (i = DECBITS;
 546              (c = ((c << 1) | GETBITS(in, 1))) >= (hu->maxcode[i]); i++);
 547         if (i >= 16) {
 548             in->marker = M_BADHUFF;
 549             return 0;
 550         }
 551         i = hu->vals[hu->valptr[i] + c - hu->maxcode[i - 1] * 2];
 552         *runp = i >> 4;
 553         i &= 15;
 554     }
 555     if (i == 0) {                /* sigh, 0xf0 is 11 bit */
 556         LEBI_PUT(in);
 557         return 0;
 558     }
 559     /* receive part */
 560     c = GETBITS(in, i);
 561     if (c < (1 << (i - 1)))
 562         c += (-1 << i) + 1;
 563     LEBI_PUT(in);
 564     return c;
 565 }
 566
 567 #define DEC_REC(in, hu, r, i)         (  \
 568   r = GETBITS(in, DECBITS),              \
 569   i = hu->llvals[r],                     \
 570   i & 128 ?                              \
 571     (                                    \
 572       UNGETBITS(in, i & 127),            \
 573       r = i >> 8 & 15,                   \
 574       i >> 16                            \
 575     )                                    \
 576   :                                      \
 577     (                                    \
 578       LEBI_PUT(in),                      \
 579       i = dec_rec2(in, hu, &r, r, i),    \
 580       LEBI_GET(in),                      \
 581       i                                  \
 582     )                                    \
 583 )
 584
 585 static void decode_mcus(struct in *in, int *dct, int n, struct scan *sc,
 586                         int *maxp)
 587 {
 588     struct dec_hufftbl *hu;
 589     int i, r, t;
 590     LEBI_DCL;
 591
 592     memset(dct, 0, n * 64 * sizeof(*dct));
 593     LEBI_GET(in);
 594     while (n-- > 0) {
 595         hu = sc->hudc.dhuff;
 596         *dct++ = (sc->dc += DEC_REC(in, hu, r, t));
 597
 598         hu = sc->huac.dhuff;
 599         i = 63;
 600         while (i > 0) {
 601             t = DEC_REC(in, hu, r, t);
 602             if (t == 0 && r == 0) {
 603                 dct += i;
 604                 break;
 605             }
 606             dct += r;
 607             *dct++ = t;
 608             i -= r + 1;
 609         }
 610         *maxp++ = 64 - i;
 611         if (n == sc->next)
 612             sc++;
 613     }
 614     LEBI_PUT(in);
 615 }
 616
 617 static void dec_makehuff(struct dec_hufftbl *hu, int *hufflen,
 618                          unsigned char *huffvals)
 619 {
 620     int code, k, i, j, d, x, c, v;
 621     for (i = 0; i < (1 << DECBITS); i++)
 622         hu->llvals[i] = 0;
 623
 624     /*
 625      * llvals layout:
 626      *
 627      * value v already known, run r, backup u bits:
 628      *  vvvvvvvvvvvvvvvv 0000 rrrr 1 uuuuuuu
 629      * value unknown, size b bits, run r, backup u bits:
 630      *  000000000000bbbb 0000 rrrr 0 uuuuuuu
 631      * value and size unknown:
 632      *  0000000000000000 0000 0000 0 0000000
 633      */
 634
 635     code = 0;
 636     k = 0;
 637     for (i = 0; i < 16; i++, code <<= 1) {        /* sizes */
 638         hu->valptr[i] = k;
 639         for (j = 0; j < hufflen[i]; j++) {
 640             hu->vals[k] = *huffvals++;
 641             if (i < DECBITS) {
 642                 c = code << (DECBITS - 1 - i);
 643                 v = hu->vals[k] & 0x0f;        /* size */
 644                 for (d = 1 << (DECBITS - 1 - i); --d >= 0;) {
 645                     if (v + i < DECBITS) {        /* both fit in table */
 646                         x = d >> (DECBITS - 1 - v - i);
 647                         if (v && x < (1 << (v - 1)))
 648                             x += (-1 << v) + 1;
 649                         x = x << 16 | (hu->vals[k] & 0xf0) << 4 |
 650                             (DECBITS - (i + 1 + v)) | 128;
 651                     } else
 652                         x = v << 16 | (hu->vals[k] & 0xf0) << 4 |
 653                             (DECBITS - (i + 1));
 654                     hu->llvals[c | d] = x;
 655                 }
 656             }
 657             code++;
 658             k++;
 659         }
 660         hu->maxcode[i] = code;
 661     }
 662     hu->maxcode[16] = 0x20000;        /* always terminate decode */
 663 }
 664
 665 /****************************************************************/
 666 /**************             idct                  ***************/
 667 /****************************************************************/
 668
 669 #define ONE ((PREC)IFIX(1.))
 670 #define S2  ((PREC)IFIX(0.382683432))
 671 #define C2  ((PREC)IFIX(0.923879532))
 672 #define C4  ((PREC)IFIX(0.707106781))
 673
 674 #define S22 ((PREC)IFIX(2 * 0.382683432))
 675 #define C22 ((PREC)IFIX(2 * 0.923879532))
 676 #define IC4 ((PREC)IFIX(1 / 0.707106781))
 677
 678 #define C3IC1 ((PREC)IFIX(0.847759065))        /* c3/c1 */
 679 #define C5IC1 ((PREC)IFIX(0.566454497))        /* c5/c1 */
 680 #define C7IC1 ((PREC)IFIX(0.198912367))        /* c7/c1 */
 681
 682 #define XPP(a,b) (t = a + b, b = a - b, a = t)
 683 #define XMP(a,b) (t = a - b, b = a + b, a = t)
 684 #define XPM(a,b) (t = a + b, b = b - a, a = t)
 685
 686 #define ROT(a,b,s,c) (  t = IMULT(a + b, s),      \
 687                         a = IMULT(a, c - s) + t,  \
 688                         b = IMULT(b, c + s) - t)
 689
 690 #define IDCT                \
 691 (                           \
 692   XPP(t0, t1),              \
 693   XMP(t2, t3),              \
 694   t2 = IMULT(t2, IC4) - t3, \
 695   XPP(t0, t3),              \
 696   XPP(t1, t2),              \
 697   XMP(t4, t7),              \
 698   XPP(t5, t6),              \
 699   XMP(t5, t7),              \
 700   t5 = IMULT(t5, IC4),      \
 701   ROT(t4, t6, S22, C22),    \
 702   t6 -= t7,                 \
 703   t5 -= t6,                 \
 704   t4 -= t5,                 \
 705   XPP(t0, t7),              \
 706   XPP(t1, t6),              \
 707   XPP(t2, t5),              \
 708   XPP(t3, t4)               \
 709 )
 710
 711 static unsigned char zig2[64] = {
 712      0,  2,  3,  9, 10, 20, 21, 35,
 713     14, 16, 25, 31, 39, 46, 50, 57,
 714      5,  7, 12, 18, 23, 33, 37, 48,
 715     27, 29, 41, 44, 52, 55, 59, 62,
 716     15, 26, 30, 40, 45, 51, 56, 58,
 717      1,  4,  8, 11, 19, 22, 34, 36,
 718     28, 42, 43, 53, 54, 60, 61, 63,
 719      6, 13, 17, 24, 32, 38, 47, 49
 720 };
 721
 722 static void idct(int *in, int *out, PREC * quant, PREC off, int max)
 723 {
 724     PREC t0, t1, t2, t3, t4, t5, t6, t7, t;
 725     PREC tmp[64], *tmpp;
 726     int i, j;
 727     unsigned char *zig2p;
 728
 729     t0 = off;
 730     if (max == 1) {
 731         t0 += in[0] * quant[0];
 732         for (i = 0; i < 64; i++)
 733             out[i] = ITOINT(t0);
 734         return;
 735     }
 736     zig2p = zig2;
 737     tmpp = tmp;
 738     for (i = 0; i < 8; i++) {
 739         j = *zig2p++;
 740         t0 += in[j] * quant[j];
 741         j = *zig2p++;
 742         t5 = in[j] * quant[j];
 743         j = *zig2p++;
 744         t2 = in[j] * quant[j];
 745         j = *zig2p++;
 746         t7 = in[j] * quant[j];
 747         j = *zig2p++;
 748         t1 = in[j] * quant[j];
 749         j = *zig2p++;
 750         t4 = in[j] * quant[j];
 751         j = *zig2p++;
 752         t3 = in[j] * quant[j];
 753         j = *zig2p++;
 754         t6 = in[j] * quant[j];
 755         IDCT;
 756         tmpp[0 * 8] = t0;
 757         tmpp[1 * 8] = t1;
 758         tmpp[2 * 8] = t2;
 759         tmpp[3 * 8] = t3;
 760         tmpp[4 * 8] = t4;
 761         tmpp[5 * 8] = t5;
 762         tmpp[6 * 8] = t6;
 763         tmpp[7 * 8] = t7;
 764         tmpp++;
 765         t0 = 0;
 766     }
 767     for (i = 0; i < 8; i++) {
 768         t0 = tmp[8 * i + 0];
 769         t1 = tmp[8 * i + 1];
 770         t2 = tmp[8 * i + 2];
 771         t3 = tmp[8 * i + 3];
 772         t4 = tmp[8 * i + 4];
 773         t5 = tmp[8 * i + 5];
 774         t6 = tmp[8 * i + 6];
 775         t7 = tmp[8 * i + 7];
 776         IDCT;
 777         out[8 * i + 0] = ITOINT(t0);
 778         out[8 * i + 1] = ITOINT(t1);
 779         out[8 * i + 2] = ITOINT(t2);
 780         out[8 * i + 3] = ITOINT(t3);
 781         out[8 * i + 4] = ITOINT(t4);
 782         out[8 * i + 5] = ITOINT(t5);
 783         out[8 * i + 6] = ITOINT(t6);
 784         out[8 * i + 7] = ITOINT(t7);
 785     }
 786 }
 787
 788 static unsigned char zig[64] = {
 789      0,  1,  5,  6, 14, 15, 27, 28,
 790      2,  4,  7, 13, 16, 26, 29, 42,
 791      3,  8, 12, 17, 25, 30, 41, 43,
 792      9, 11, 18, 24, 31, 40, 44, 53,
 793     10, 19, 23, 32, 39, 45, 52, 54,
 794     20, 22, 33, 38, 46, 51, 55, 60,
 795     21, 34, 37, 47, 50, 56, 59, 61,
 796     35, 36, 48, 49, 57, 58, 62, 63
 797 };
 798
 799 static PREC aaidct[8] = {
 800     IFIX(0.3535533906), IFIX(0.4903926402),
 801     IFIX(0.4619397663), IFIX(0.4157348062),
 802     IFIX(0.3535533906), IFIX(0.2777851165),
 803     IFIX(0.1913417162), IFIX(0.0975451610)
 804 };
 805
 806
 807 static void idctqtab(unsigned char *qin, PREC * qout)
 808 {
 809     int i, j;
 810
 811     for (i = 0; i < 8; i++)
 812         for (j = 0; j < 8; j++)
 813             qout[zig[i * 8 + j]] = qin[zig[i * 8 + j]] *
 814                 IMULT(aaidct[i], aaidct[j]);
 815 }
 816
 817 static void scaleidctqtab(PREC * q, PREC sc)
 818 {
 819     int i;
 820
 821     for (i = 0; i < 64; i++)
 822         q[i] = IMULT(q[i], sc);
 823 }
 824
 825 /****************************************************************/
 826 /**************          color decoder            ***************/
 827 /****************************************************************/
 828
 829 #define ROUND
 830
 831 /*
 832  * YCbCr Color transformation:
 833  *
 834  * y:0..255   Cb:-128..127   Cr:-128..127
 835  *
 836  *      R = Y                + 1.40200 * Cr
 837  *      G = Y - 0.34414 * Cb - 0.71414 * Cr
 838  *      B = Y + 1.77200 * Cb
 839  *
 840  * =>
 841  *      Cr *= 1.40200;
 842  *      Cb *= 1.77200;
 843  *      Cg = 0.19421 * Cb + .50937 * Cr;
 844  *      R = Y + Cr;
 845  *      G = Y - Cg;
 846  *      B = Y + Cb;
 847  *
 848  * =>
 849  *      Cg = (50 * Cb + 130 * Cr + 128) >> 8;
 850  */
 851
 852 static void initcol(PREC q[][64])
 853 {
 854     scaleidctqtab(q[1], IFIX(1.77200));
 855     scaleidctqtab(q[2], IFIX(1.40200));
 856 }
 857
 858 /* This is optimized for the stupid sun SUNWspro compiler. */
 859 #define STORECLAMP(a,x)                          \
 860 (                                                \
 861   (a) = (x),                                     \
 862   (unsigned int)(x) >= 256 ?                     \
 863     ((a) = (x) < 0 ? 0 : 255)                    \
 864   :                                              \
 865     0                                            \
 866 )
 867
 868 #define CLAMP(x) ((unsigned int)(x) >= 256 ? ((x) < 0 ? 0 : 255) : (x))
 869
 870 #ifdef ROUND
 871
 872 #define CBCRCG(yin, xin)                         \
 873 (                                                \
 874   cb = outc[0 +yin*8+xin],                       \
 875   cr = outc[64+yin*8+xin],                       \
 876   cg = (50 * cb + 130 * cr + 128) >> 8           \
 877 )
 878
 879 #else
 880
 881 #define CBCRCG(yin, xin)                         \
 882 (                                                \
 883   cb = outc[0 +yin*8+xin],                       \
 884   cr = outc[64+yin*8+xin],                       \
 885   cg = (3 * cb + 8 * cr) >> 4                    \
 886 )
 887
 888 #endif
 889
 890 #define PIC(yin, xin, p, xout)                   \
 891 (                                                \
 892   y = outy[(yin) * 8 + xin],                     \
 893   STORECLAMP(p[(xout) * 3 + 0], y + cr),         \
 894   STORECLAMP(p[(xout) * 3 + 1], y - cg),         \
 895   STORECLAMP(p[(xout) * 3 + 2], y + cb)          \
 896 )
 897
 898 #ifdef __LITTLE_ENDIAN
 899 #define PIC_16(yin, xin, p, xout, add)           \
 900 (                                                \
 901   y = outy[(yin) * 8 + xin],                     \
 902   y = ((CLAMP(y + cr + add*2+1) & 0xf8) <<  8) | \
 903       ((CLAMP(y - cg + add    ) & 0xfc) <<  3) | \
 904       ((CLAMP(y + cb + add*2+1)       ) >>  3),  \
 905   p[(xout) * 2 + 0] = y & 0xff,                  \
 906   p[(xout) * 2 + 1] = y >> 8                     \
 907 )
 908 #else
 909 #ifdef CONFIG_PPC
 910 #define PIC_16(yin, xin, p, xout, add)           \
 911 (                                                \
 912   y = outy[(yin) * 8 + xin],                     \
 913   y = ((CLAMP(y + cr + add*2+1) & 0xf8) <<  7) | \
 914       ((CLAMP(y - cg + add*2+1) & 0xf8) <<  2) | \
 915       ((CLAMP(y + cb + add*2+1)       ) >>  3),  \
 916   p[(xout) * 2 + 0] = y >> 8,                    \
 917   p[(xout) * 2 + 1] = y & 0xff                   \
 918 )
 919 #else
 920 #define PIC_16(yin, xin, p, xout, add)           \
 921 (                                                \
 922   y = outy[(yin) * 8 + xin],                     \
 923   y = ((CLAMP(y + cr + add*2+1) & 0xf8) <<  8) | \
 924       ((CLAMP(y - cg + add    ) & 0xfc) <<  3) | \
 925       ((CLAMP(y + cb + add*2+1)       ) >>  3),  \
 926   p[(xout) * 2 + 0] = y >> 8,                    \
 927   p[(xout) * 2 + 1] = y & 0xff                   \
 928 )
 929 #endif
 930 #endif
 931
 932 #define PIC_32(yin, xin, p, xout)               \
 933 (                                               \
 934   y = outy[(yin) * 8 + xin],                    \
 935   STORECLAMP(p[(xout) * 4 + 0], y + cr),        \
 936   STORECLAMP(p[(xout) * 4 + 1], y - cg),        \
 937   STORECLAMP(p[(xout) * 4 + 2], y + cb),        \
 938   p[(xout) * 4 + 3] = 0                         \
 939 )
 940
 941 #define PIC221111(xin)                                              \
 942 (                                                                   \
 943   CBCRCG(0, xin),                                                   \
 944   PIC(xin / 4 * 8 + 0, (xin & 3) * 2 + 0, pic0, xin * 2 + 0),       \
 945   PIC(xin / 4 * 8 + 0, (xin & 3) * 2 + 1, pic0, xin * 2 + 1),       \
 946   PIC(xin / 4 * 8 + 1, (xin & 3) * 2 + 0, pic1, xin * 2 + 0),       \
 947   PIC(xin / 4 * 8 + 1, (xin & 3) * 2 + 1, pic1, xin * 2 + 1)        \
 948 )
 949
 950 #define PIC221111_16(xin)                                           \
 951 (                                                                   \
 952   CBCRCG(0, xin),                                                   \
 953   PIC_16(xin / 4 * 8 + 0, (xin & 3) * 2 + 0, pic0, xin * 2 + 0, 3), \
 954   PIC_16(xin / 4 * 8 + 0, (xin & 3) * 2 + 1, pic0, xin * 2 + 1, 0), \
 955   PIC_16(xin / 4 * 8 + 1, (xin & 3) * 2 + 0, pic1, xin * 2 + 0, 1), \
 956   PIC_16(xin / 4 * 8 + 1, (xin & 3) * 2 + 1, pic1, xin * 2 + 1, 2)  \
 957 )
 958
 959 #define PIC221111_32(xin)                                           \
 960 (                                                                   \
 961   CBCRCG(0, xin),                                                   \
 962   PIC_32(xin / 4 * 8 + 0, (xin & 3) * 2 + 0, pic0, xin * 2 + 0),    \
 963   PIC_32(xin / 4 * 8 + 0, (xin & 3) * 2 + 1, pic0, xin * 2 + 1),    \
 964   PIC_32(xin / 4 * 8 + 1, (xin & 3) * 2 + 0, pic1, xin * 2 + 0),    \
 965   PIC_32(xin / 4 * 8 + 1, (xin & 3) * 2 + 1, pic1, xin * 2 + 1)     \
 966 )
 967
 968 static void col221111(int *out, unsigned char *pic, int width)
 969 {
 970     int i, j, k;
 971     unsigned char *pic0, *pic1;
 972     int *outy, *outc;
 973     int cr, cg, cb, y;
 974
 975     pic0 = pic;
 976     pic1 = pic + width;
 977     outy = out;
 978     outc = out + 64 * 4;
 979     for (i = 2; i > 0; i--) {
 980         for (j = 4; j > 0; j--) {
 981             for (k = 0; k < 8; k++) {
 982                 PIC221111(k);
 983             }
 984             outc += 8;
 985             outy += 16;
 986             pic0 += 2 * width;
 987             pic1 += 2 * width;
 988         }
 989         outy += 64 * 2 - 16 * 4;
 990     }
 991 }
 992
 993 static void col221111_16(int *out, unsigned char *pic, int width)
 994 {
 995     int i, j, k;
 996     unsigned char *pic0, *pic1;
 997     int *outy, *outc;
 998     int cr, cg, cb, y;
 999
1000     pic0 = pic;
1001     pic1 = pic + width;
1002     outy = out;
1003     outc = out + 64 * 4;
1004     for (i = 2; i > 0; i--) {
1005         for (j = 4; j > 0; j--) {
1006             for (k = 0; k < 8; k++) {
1007                 PIC221111_16(k);
1008             }
1009             outc += 8;
1010             outy += 16;
1011             pic0 += 2 * width;
1012             pic1 += 2 * width;
1013         }
1014         outy += 64 * 2 - 16 * 4;
1015     }
1016 }
1017
1018 static void col221111_32(int *out, unsigned char *pic, int width)
1019 {
1020     int i, j, k;
1021     unsigned char *pic0, *pic1;
1022     int *outy, *outc;
1023     int cr, cg, cb, y;
1024
1025     pic0 = pic;
1026     pic1 = pic + width;
1027     outy = out;
1028     outc = out + 64 * 4;
1029     for (i = 2; i > 0; i--) {
1030         for (j = 4; j > 0; j--) {
1031             for (k = 0; k < 8; k++) {
1032                 PIC221111_32(k);
1033             }
1034             outc += 8;
1035             outy += 16;
1036             pic0 += 2 * width;
1037             pic1 += 2 * width;
1038         }
1039         outy += 64 * 2 - 16 * 4;
1040     }
1041 }