apps/plugins/imageviewer/png/tinflate.c

   1 /***************************************************************************
   2  *             __________               __   ___.
   3  *   Open      \______   \ ____   ____ |  | _\_ |__   _______  ___
   4  *   Source     |       _//  _ \_/ ___\|  |/ /| __ \ /  _ \  \/  /
   5  *   Jukebox    |    |   (  <_> )  \___|    < | \_\ (  <_> > <  <
   6  *   Firmware   |____|_  /\____/ \___  >__|_ \|___  /\____/__/\_ \
   7  *                     \/            \/     \/    \/            \/
   8  * $Id$
   9  *
  10  * Original source:
  11  * Copyright (c) 2003 by Joergen Ibsen / Jibz
  12  *
  13  * Rockbox adaptation:
  14  * Copyright (c) 2010 by Marcin Bukat
  15  *
  16  * This program is free software; you can redistribute it and/or
  17  * modify it under the terms of the GNU General Public License
  18  * as published by the Free Software Foundation; either version 2
  19  * of the License, or (at your option) any later version.
  20  *
  21  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
  22  * KIND, either express or implied.
  23  *
  24  ****************************************************************************/
  25
  26 /*
  27  * tinflate  -  tiny inflate
  28  *
  29  * Copyright (c) 2003 by Joergen Ibsen / Jibz
  30  * All Rights Reserved
  31  *
  32  * http://www.ibsensoftware.com/
  33  *
  34  * This software is provided 'as-is', without any express
  35  * or implied warranty.  In no event will the authors be
  36  * held liable for any damages arising from the use of
  37  * this software.
  38  *
  39  * Permission is granted to anyone to use this software
  40  * for any purpose, including commercial applications,
  41  * and to alter it and redistribute it freely, subject to
  42  * the following restrictions:
  43  *
  44  * 1. The origin of this software must not be
  45  *    misrepresented; you must not claim that you
  46  *    wrote the original software. If you use this
  47  *    software in a product, an acknowledgment in
  48  *    the product documentation would be appreciated
  49  *    but is not required.
  50  *
  51  * 2. Altered source versions must be plainly marked
  52  *    as such, and must not be misrepresented as
  53  *    being the original software.
  54  *
  55  * 3. This notice may not be removed or altered from
  56  *    any source distribution.
  57  */
  58
  59 #include "tinf.h"
  60 #include <string.h> /* memcpy */
  61
  62 /* ------------------------------ *
  63  * -- internal data structures -- *
  64  * ------------------------------ */
  65
  66 typedef struct {
  67    unsigned short table[16];  /* table of code length counts */
  68    unsigned short trans[288]; /* code -> symbol translation table */
  69 } TINF_TREE;
  70
  71 typedef struct {
  72    unsigned short table[16];
  73    unsigned short trans[32];
  74 } TINF_SDTREE;
  75
  76 typedef struct {
  77    TINF_TREE sltree;
  78    TINF_TREE sdtree;
  79    unsigned char length_bits[30];
  80    unsigned short length_base[30];
  81    unsigned char dist_bits[30];
  82    unsigned short dist_base[30];
  83    unsigned char clcidx[19];
  84 } TINF_TABLES;
  85
  86 typedef struct {
  87    const unsigned char *source;
  88    unsigned int tag;
  89    unsigned int bitcount;
  90
  91    unsigned char *dest;
  92    unsigned int *destLen;
  93
  94    TINF_TREE ltree; /* dynamic length/symbol tree */
  95    TINF_TREE dtree; /* dynamic distance tree */
  96 } TINF_DATA;
  97
  98 /* static tables */
  99 TINF_TABLES tbl = {
 100     .sltree = {
 101         .table = {0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0018,
 102                   0x0098, 0x0070, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000},
 103
 104         .trans = {0x0100, 0x0101, 0x0102, 0x0103, 0x0104, 0x0105, 0x0106, 0x0107,
 105                   0x0108, 0x0109, 0x010a, 0x010b, 0x010c, 0x010d, 0x010e, 0x010f,
 106                   0x0110, 0x0111, 0x0112, 0x0113, 0x0114, 0x0115, 0x0116, 0x0117,
 107                   0x0000, 0x0001, 0x0002, 0x0003, 0x0004, 0x0005, 0x0006, 0x0007,
 108                   0x0008, 0x0009, 0x000a, 0x000b, 0x000c, 0x000d, 0x000e, 0x000f,
 109                   0x0010, 0x0011, 0x0012, 0x0013, 0x0014, 0x0015, 0x0016, 0x0017,
 110                   0x0018, 0x0019, 0x001a, 0x001b, 0x001c, 0x001d, 0x001e, 0x001f,
 111                   0x0020, 0x0021, 0x0022, 0x0023, 0x0024, 0x0025, 0x0026, 0x0027,
 112                   0x0028, 0x0029, 0x002a, 0x002b, 0x002c, 0x002d, 0x002e, 0x002f,
 113                   0x0030, 0x0031, 0x0032, 0x0033, 0x0034, 0x0035, 0x0036, 0x0037,
 114                   0x0038, 0x0039, 0x003a, 0x003b, 0x003c, 0x003d, 0x003e, 0x003f,
 115                   0x0040, 0x0041, 0x0042, 0x0043, 0x0044, 0x0045, 0x0046, 0x0047,
 116                   0x0048, 0x0049, 0x004a, 0x004b, 0x004c, 0x004d, 0x004e, 0x004f,
 117                   0x0050, 0x0051, 0x0052, 0x0053, 0x0054, 0x0055, 0x0056, 0x0057,
 118                   0x0058, 0x0059, 0x005a, 0x005b, 0x005c, 0x005d, 0x005e, 0x005f,
 119                   0x0060, 0x0061, 0x0062, 0x0063, 0x0064, 0x0065, 0x0066, 0x0067,
 120                   0x0068, 0x0069, 0x006a, 0x006b, 0x006c, 0x006d, 0x006e, 0x006f,
 121                   0x0070, 0x0071, 0x0072, 0x0073, 0x0074, 0x0075, 0x0076, 0x0077,
 122                   0x0078, 0x0079, 0x007a, 0x007b, 0x007c, 0x007d, 0x007e, 0x007f,
 123                   0x0080, 0x0081, 0x0082, 0x0083, 0x0084, 0x0085, 0x0086, 0x0087,
 124                   0x0088, 0x0089, 0x008a, 0x008b, 0x008c, 0x008d, 0x008e, 0x008f,
 125                   0x0118, 0x0119, 0x011a, 0x011b, 0x011c, 0x011d, 0x011e, 0x011f,
 126                   0x0090, 0x0091, 0x0092, 0x0093, 0x0094, 0x0095, 0x0096, 0x0097,
 127                   0x0098, 0x0099, 0x009a, 0x009b, 0x009c, 0x009d, 0x009e, 0x009f,
 128                   0x00a0, 0x00a1, 0x00a2, 0x00a3, 0x00a4, 0x00a5, 0x00a6, 0x00a7,
 129                   0x00a8, 0x00a9, 0x00aa, 0x00ab, 0x00ac, 0x00ad, 0x00ae, 0x00af,
 130                   0x00b0, 0x00b1, 0x00b2, 0x00b3, 0x00b4, 0x00b5, 0x00b6, 0x00b7,
 131                   0x00b8, 0x00b9, 0x00ba, 0x00bb, 0x00bc, 0x00bd, 0x00be, 0x00bf,
 132                   0x00c0, 0x00c1, 0x00c2, 0x00c3, 0x00c4, 0x00c5, 0x00c6, 0x00c7,
 133                   0x00c8, 0x00c9, 0x00ca, 0x00cb, 0x00cc, 0x00cd, 0x00ce, 0x00cf,
 134                   0x00d0, 0x00d1, 0x00d2, 0x00d3, 0x00d4, 0x00d5, 0x00d6, 0x00d7,
 135                   0x00d8, 0x00d9, 0x00da, 0x00db, 0x00dc, 0x00dd, 0x00de, 0x00df,
 136                   0x00e0, 0x00e1, 0x00e2, 0x00e3, 0x00e4, 0x00e5, 0x00e6, 0x00e7,
 137                   0x00e8, 0x00e9, 0x00ea, 0x00eb, 0x00ec, 0x00ed, 0x00ee, 0x00ef,
 138                   0x00f0, 0x00f1, 0x00f2, 0x00f3, 0x00f4, 0x00f5, 0x00f6, 0x00f7,
 139                   0x00f8, 0x00f9, 0x00fa, 0x00fb, 0x00fc, 0x00fd, 0x00fe, 0x00ff},
 140               },
 141
 142     .sdtree = {
 143         .table = {0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0020, 0x0000, 0x0000,
 144                   0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000},
 145
 146         .trans = {0x0000, 0x0001, 0x0002, 0x0003, 0x0004, 0x0005, 0x0006, 0x0007,
 147                   0x0008, 0x0009, 0x000a, 0x000b, 0x000c, 0x000d, 0x000e, 0x000f,
 148                   0x0010, 0x0011, 0x0012, 0x0013, 0x0014, 0x0015, 0x0016, 0x0017,
 149                   0x0018, 0x0019, 0x001a, 0x001b, 0x001c, 0x001d, 0x001e, 0x001f},
 150               },
 151
 152     .length_bits = {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 153                     0x01, 0x01, 0x01, 0x01, 0x02, 0x02, 0x02, 0x02,
 154                     0x03, 0x03, 0x03, 0x03, 0x04, 0x04, 0x04, 0x04,
 155                     0x05, 0x05, 0x05, 0x05, 0x00, 0x06},
 156
 157     .length_base = {0x0003, 0x0004, 0x0005, 0x0006, 0x0007, 0x0008, 0x0009, 0x000a,
 158                     0x000b, 0x000d, 0x000f, 0x0011, 0x0013, 0x0017, 0x001b, 0x001f,
 159                     0x0023, 0x002b, 0x0033, 0x003b, 0x0043, 0x0053, 0x0063, 0x0073,
 160                     0x0083, 0x00a3, 0x00c3, 0x00e3, 0x0102, 0x0143},
 161
 162     .dist_bits = {0x00, 0x00, 0x00, 0x00, 0x01, 0x01, 0x02, 0x02,
 163                   0x03, 0x03, 0x04, 0x04, 0x05, 0x05, 0x06, 0x06,
 164                   0x07, 0x07, 0x08, 0x08, 0x09, 0x09, 0x0a, 0x0a,
 165                   0x0b, 0x0b, 0x0c, 0x0c, 0x0d, 0x0d},
 166
 167     .dist_base = {0x0001, 0x0002, 0x0003, 0x0004, 0x0005, 0x0007, 0x0009, 0x000d,
 168                   0x0011, 0x0019, 0x0021, 0x0031, 0x0041, 0x0061, 0x0081, 0x00c1,
 169                   0x0101, 0x0181, 0x0201, 0x0301, 0x0401, 0x0601, 0x0801, 0x0c01,
 170                   0x1001, 0x1801, 0x2001, 0x3001, 0x4001, 0x6001},
 171
 172     .clcidx = {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15},
 173 };
 174
 175
 176 /* ----------------------- *
 177  * -- utility functions -- *
 178  * ----------------------- */
 179
 180 /* given an array of code lengths, build a tree */
 181 static void tinf_build_tree(TINF_TREE *t, const unsigned char *lengths, unsigned int num)
 182 {
 183    unsigned short offs[16];
 184    unsigned int i, sum;
 185
 186    /* clear code length count table */
 187    /* for (i = 0; i < 16; ++i) t->table[i] = 0; */
 188    memset(t->table, 0, sizeof(short)*16);
 189
 190    /* scan symbol lengths, and sum code length counts */
 191    for (i = 0; i < num; ++i) t->table[lengths[i]]++;
 192
 193    t->table[0] = 0;
 194
 195    /* compute offset table for distribution sort */
 196    for (sum = 0, i = 0; i < 16; ++i)
 197    {
 198       offs[i] = sum;
 199       sum += t->table[i];
 200    }
 201
 202    /* create code->symbol translation table (symbols sorted by code) */
 203    for (i = 0; i < num; ++i)
 204    {
 205       if (lengths[i]) t->trans[offs[lengths[i]]++] = i;
 206    }
 207 }
 208
 209 /* ---------------------- *
 210  * -- decode functions -- *
 211  * ---------------------- */
 212
 213 /* get one bit from source stream */
 214 static int tinf_getbit(TINF_DATA *d)
 215 {
 216    unsigned int bit;
 217
 218    /* check if tag is empty */
 219    if (!d->bitcount--)
 220    {
 221       /* load next tag */
 222       d->tag = *d->source++;
 223       d->bitcount = 7;
 224    }
 225
 226    /* shift bit out of tag */
 227    bit = d->tag & 0x01;
 228    d->tag >>= 1;
 229
 230    return bit;
 231 }
 232
 233 /* read a num bit value from a stream and add base */
 234 static unsigned int tinf_read_bits(TINF_DATA *d, int num, int base)
 235 {
 236    unsigned int val = 0;
 237
 238    /* read num bits */
 239    if (num)
 240    {
 241       unsigned int limit = 1 << (num);
 242       unsigned int mask;
 243
 244       for (mask = 1; mask < limit; mask <<= 1)
 245          if (tinf_getbit(d)) val += mask;
 246    }
 247
 248    return val + base;
 249 }
 250
 251 /* given a data stream and a tree, decode a symbol */
 252 static int tinf_decode_symbol(TINF_DATA *d, TINF_TREE *t)
 253 {
 254    int sum = 0, cur = 0, len = 0;
 255
 256    /* get more bits while code value is above sum */
 257    do {
 258
 259       cur = (cur << 1) + tinf_getbit(d);
 260
 261       ++len;
 262
 263       sum += t->table[len];
 264       cur -= t->table[len];
 265
 266    } while (cur >= 0);
 267
 268    return t->trans[sum + cur];
 269 }
 270
 271 /* given a data stream, decode dynamic trees from it */
 272 static void tinf_decode_trees(TINF_DATA *d, TINF_TREE *lt, TINF_TREE *dt, TINF_TABLES *tbl)
 273 {
 274    TINF_TREE code_tree;
 275    unsigned char lengths[288+32];
 276    unsigned int hlit, hdist, hclen;
 277    unsigned int i, num, length;
 278
 279    /* get 5 bits HLIT (257-286) */
 280    hlit = tinf_read_bits(d, 5, 257);
 281
 282    /* get 5 bits HDIST (1-32) */
 283    hdist = tinf_read_bits(d, 5, 1);
 284
 285    /* get 4 bits HCLEN (4-19) */
 286    hclen = tinf_read_bits(d, 4, 4);
 287
 288    /* for (i = 0; i < 19; ++i) lengths[i] = 0; */
 289    memset(lengths, 0, sizeof(unsigned char)*19);
 290
 291    /* read code lengths for code length alphabet */
 292    for (i = 0; i < hclen; ++i)
 293    {
 294       /* get 3 bits code length (0-7) */
 295       unsigned int clen = tinf_read_bits(d, 3, 0);
 296
 297       lengths[tbl->clcidx[i]] = clen;
 298    }
 299
 300    /* build code length tree */
 301    tinf_build_tree(&code_tree, lengths, 19);
 302
 303    /* decode code lengths for the dynamic trees */
 304    for (num = 0; num < hlit + hdist; )
 305    {
 306       int sym = tinf_decode_symbol(d, &code_tree);
 307
 308       switch (sym)
 309       {
 310       case 16:
 311          /* copy previous code length 3-6 times (read 2 bits) */
 312          {
 313             unsigned char prev = lengths[num - 1];
 314             for (length = tinf_read_bits(d, 2, 3); length; --length)
 315             {
 316                lengths[num++] = prev;
 317             }
 318          }
 319          break;
 320       case 17:
 321          /* repeat code length 0 for 3-10 times (read 3 bits) */
 322          for (length = tinf_read_bits(d, 3, 3); length; --length)
 323          {
 324             lengths[num++] = 0;
 325          }
 326          break;
 327       case 18:
 328          /* repeat code length 0 for 11-138 times (read 7 bits) */
 329          for (length = tinf_read_bits(d, 7, 11); length; --length)
 330          {
 331             lengths[num++] = 0;
 332          }
 333          break;
 334       default:
 335          /* values 0-15 represent the actual code lengths */
 336          lengths[num++] = sym;
 337          break;
 338       }
 339    }
 340
 341    /* build dynamic trees */
 342    tinf_build_tree(lt, lengths, hlit);
 343    tinf_build_tree(dt, lengths + hlit, hdist);
 344 }
 345
 346 /* ----------------------------- *
 347  * -- block inflate functions -- *
 348  * ----------------------------- */
 349
 350 /* given a stream and two trees, inflate a block of data */
 351 static int tinf_inflate_block_data(TINF_DATA *d, TINF_TREE *lt, TINF_TREE *dt, TINF_TABLES *tbl)
 352 {
 353    /* remember current output position */
 354    unsigned char *start = d->dest;
 355
 356    while (1)
 357    {
 358       int sym = tinf_decode_symbol(d, lt);
 359
 360       /* check for end of block */
 361       if (sym == 256)
 362       {
 363          *d->destLen += d->dest - start;
 364          return TINF_OK;
 365       }
 366
 367       if (sym < 256)
 368       {
 369          *d->dest++ = sym;
 370
 371       } else {
 372
 373          int length, dist, offs;
 374          int i;
 375
 376          sym -= 257;
 377
 378          /* possibly get more bits from length code */
 379          length = tinf_read_bits(d, tbl->length_bits[sym], tbl->length_base[sym]);
 380
 381          dist = tinf_decode_symbol(d, dt);
 382
 383          /* possibly get more bits from distance code */
 384          offs = tinf_read_bits(d, tbl->dist_bits[dist], tbl->dist_base[dist]);
 385
 386          /* copy match */
 387          for (i = 0; i < length; ++i)
 388          {
 389             d->dest[i] = d->dest[i - offs];
 390          }
 391
 392          d->dest += length;
 393       }
 394    }
 395 }
 396
 397 /* inflate an uncompressed block of data */
 398 static int tinf_inflate_uncompressed_block(TINF_DATA *d)
 399 {
 400    unsigned int length, invlength;
 401    /* unsigned int i; */
 402
 403    /* get length */
 404    length = d->source[1];
 405    length = (length << 8) + d->source[0];
 406
 407    /* get one's complement of length */
 408    invlength = d->source[3];
 409    invlength = (invlength << 8) + d->source[2];
 410
 411    /* check length */
 412    if (length != (~invlength & 0x0000ffff)) return TINF_DATA_ERROR;
 413
 414    d->source += 4;
 415
 416    /* copy block */
 417    /* for (i = length; i; --i) *d->dest++ = *d->source++; */
 418    memcpy(d->dest, d->source, sizeof(unsigned char)*length);
 419    d->dest += sizeof(unsigned char)*length;
 420    d->source += sizeof(unsigned char)*length;
 421
 422    /* make sure we start next block on a byte boundary */
 423    d->bitcount = 0;
 424
 425    *d->destLen += length;
 426
 427    return TINF_OK;
 428 }
 429
 430 /* inflate a block of data compressed with fixed huffman trees */
 431 static int tinf_inflate_fixed_block(TINF_DATA *d, TINF_TABLES *tbl)
 432 {
 433    /* decode block using fixed trees */
 434    return tinf_inflate_block_data(d, &tbl->sltree, &tbl->sdtree, tbl);
 435 }
 436
 437 /* inflate a block of data compressed with dynamic huffman trees */
 438 static int tinf_inflate_dynamic_block(TINF_DATA *d, TINF_TABLES *tbl)
 439 {
 440    /* decode trees from stream */
 441    tinf_decode_trees(d, &d->ltree, &d->dtree, tbl);
 442
 443    /* decode block using decoded trees */
 444    return tinf_inflate_block_data(d, &d->ltree, &d->dtree, tbl);
 445 }
 446
 447 /* ---------------------- *
 448  * -- public functions -- *
 449  * ---------------------- */
 450
 451 /* inflate stream from source to dest */
 452 int tinf_uncompress(void *dest, unsigned int *destLen,
 453                     const void *source, unsigned int sourceLen)
 454 {
 455     TINF_DATA d;
 456     int bfinal;
 457
 458     d.source = (const unsigned char *)source;
 459     d.bitcount = 0;
 460
 461     d.dest = (unsigned char *)dest;
 462     d.destLen = destLen;
 463
 464     *destLen = 0;
 465
 466     do {
 467
 468        unsigned int btype;
 469        int res;
 470
 471        /* read final block flag */
 472        bfinal = tinf_getbit(&d);
 473
 474        /* read block type (2 bits) */
 475        btype = tinf_read_bits(&d, 2, 0);
 476
 477        /* decompress block */
 478        switch (btype)
 479        {
 480        case 0:
 481           /* decompress uncompressed block */
 482           res = tinf_inflate_uncompressed_block(&d);
 483           break;
 484         case 1:
 485           /* decompress block with fixed huffman trees */
 486           res = tinf_inflate_fixed_block(&d,&tbl);
 487           break;
 488        case 2:
 489           /* decompress block with dynamic huffman trees */
 490           res = tinf_inflate_dynamic_block(&d,&tbl);
 491           break;
 492        default:
 493           return TINF_DATA_ERROR;
 494        }
 495
 496        if (res != TINF_OK) return TINF_DATA_ERROR;
 497
 498        if (d.source > (unsigned char *)source + sourceLen)
 499            return TINF_DATA_ERROR;
 500     } while (!bfinal);
 501
 502     return TINF_OK;
 503 }