Onyx2D/O2zlib.m

   1 /* Copyright (c) 2007 Christopher J. W. Lloyd
   2
   3 Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
   4
   5 The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
   6
   7 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
   8
   9 /*  zlib decode is based on the public domain implementation by Sean Barrett  http://www.nothings.org/stb_image.c  V 0.57 */
  10
  11 #import <Foundation/NSString.h>
  12
  13 #import <assert.h>
  14 #import <stdlib.h>
  15 #import <memory.h>
  16
  17 typedef unsigned short uint16;
  18 static int e(const char *str){
  19    NSLog(@"STB ERROR %s",str);
  20    return 0;
  21 }
  22
  23 // fast-way is faster to check than jpeg huffman, but slow way is slower
  24 #define ZFAST_BITS  9 // accelerate all cases in default tables
  25 #define ZFAST_MASK  ((1 << ZFAST_BITS) - 1)
  26
  27 typedef struct {
  28    uint16 fast[1 << ZFAST_BITS];
  29    uint16 firstcode[16];
  30    int    maxcode[17];
  31    uint16 firstsymbol[16];
  32    unsigned char  size[288];
  33    uint16 value[288];
  34 } zhuffman;
  35
  36 static int bitreverse16(int n) {
  37   n = ((n & 0xAAAA) >>  1) | ((n & 0x5555) << 1);
  38   n = ((n & 0xCCCC) >>  2) | ((n & 0x3333) << 2);
  39   n = ((n & 0xF0F0) >>  4) | ((n & 0x0F0F) << 4);
  40   n = ((n & 0xFF00) >>  8) | ((n & 0x00FF) << 8);
  41   return n;
  42 }
  43
  44 static int bit_reverse(int v, int bits) {
  45    assert(bits <= 16);
  46    // to bit reverse n bits, reverse 16 and shift
  47    // e.g. 11 bits, bit reverse and shift away 5
  48    return bitreverse16(v) >> (16-bits);
  49 }
  50
  51 static int zbuild_huffman(zhuffman *z, const unsigned char *sizelist, int num) {
  52    int i,k=0;
  53    int code, next_code[16], sizes[17];
  54
  55    // DEFLATE spec for generating codes
  56    memset(sizes, 0, sizeof(sizes));
  57    memset(z->fast, 255, sizeof(z->fast));
  58    for (i=0; i < num; ++i)
  59       ++sizes[sizelist[i]];
  60    sizes[0] = 0;
  61    for (i=1; i < 16; ++i)
  62       assert(sizes[i] <= (1 << i));
  63    code = 0;
  64    for (i=1; i < 16; ++i) {
  65       next_code[i] = code;
  66       z->firstcode[i] = (uint16)code;
  67       z->firstsymbol[i] = (uint16)k;
  68       code = (code + sizes[i]);
  69       if (sizes[i])
  70          if (code-1 >= (1 << i)) return e("bad codelengths");
  71       z->maxcode[i] = code << (16-i); // preshift for inner loop
  72       code <<= 1;
  73       k += sizes[i];
  74    }
  75    z->maxcode[16] = 0x10000; // sentinel
  76    for (i=0; i < num; ++i) {
  77       int s = sizelist[i];
  78       if (s) {
  79          int c = next_code[s] - z->firstcode[s] + z->firstsymbol[s];
  80          z->size[c] = s;
  81          z->value[c] = (uint16)i;
  82          if (s <= ZFAST_BITS) {
  83             int k = bit_reverse(next_code[s],s);
  84             while (k < (1 << ZFAST_BITS)) {
  85                z->fast[k] = (uint16)c;
  86                k += (1 << s);
  87             }
  88          }
  89          ++next_code[s];
  90       }
  91    }
  92    return 1;
  93 }
  94
  95 // zlib-from-memory implementation for PNG reading
  96 //    because PNG allows splitting the zlib stream arbitrarily,
  97 //    and it's annoying structurally to have PNG call ZLIB call PNG,
  98 //    we require PNG read all the IDATs and combine them into a single
  99 //    memory buffer
 100
 101 typedef struct {
 102    const unsigned char *inBytes;
 103    unsigned             inLength;
 104    unsigned             inPosition;
 105
 106    unsigned char *outBytes;
 107    unsigned       outLength;
 108    unsigned       outPosition;
 109
 110    unsigned int  code_buffer;
 111    int           num_bits;
 112    zhuffman      z_length;
 113    zhuffman      z_distance;
 114 } O2FlateDecode;
 115
 116
 117 static unsigned char O2FlateDecodeNextByte(O2FlateDecode *inflate){
 118    if(inflate->inPosition<inflate->inLength)
 119     return inflate->inBytes[inflate->inPosition++];
 120
 121    return 0;
 122 }
 123
 124 static int length_base[31] = {
 125    3,4,5,6,7,8,9,10,11,13,
 126    15,17,19,23,27,31,35,43,51,59,
 127    67,83,99,115,131,163,195,227,258,0,0
 128 };
 129
 130 static int length_extra[31]= {
 131  0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0,0,0
 132 };
 133
 134 static int dist_base[32] = {
 135  1,2,3,4,5,7,9,13,17,25,33,49,65,97,129,193,
 136 257,385,513,769,1025,1537,2049,3073,4097,6145,8193,12289,16385,24577,0,0
 137 };
 138
 139 static int dist_extra[32] = {
 140  0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13
 141 };
 142
 143 static void fill_bits(O2FlateDecode *inflate) {
 144    do {
 145     assert(inflate->code_buffer < (1U << inflate->num_bits));
 146
 147     inflate->code_buffer |= O2FlateDecodeNextByte(inflate) << inflate->num_bits;
 148     inflate->num_bits += 8;
 149    } while (inflate->num_bits <= 24);
 150 }
 151
 152 static unsigned int zreceive(O2FlateDecode *inflate,int n) {
 153    unsigned int k;
 154
 155    if (inflate->num_bits < n)
 156     fill_bits(inflate);
 157
 158    k = inflate->code_buffer & ((1 << n) - 1);
 159    inflate->code_buffer >>= n;
 160    inflate->num_bits -= n;
 161
 162    return k;
 163 }
 164
 165 static int zhuffman_decode(O2FlateDecode *inflate,zhuffman *z) {
 166    int b,s,k;
 167
 168    if (inflate->num_bits < 16)
 169     fill_bits(inflate);
 170
 171    b = z->fast[inflate->code_buffer & ZFAST_MASK];
 172    if (b < 0xffff) {
 173       s = z->size[b];
 174       inflate->code_buffer >>= s;
 175       inflate->num_bits -= s;
 176
 177       return z->value[b];
 178    }
 179
 180    // not resolved by fast table, so compute it the slow way
 181    // use jpeg approach, which requires MSbits at top
 182    k = bit_reverse(inflate->code_buffer, 16);
 183    for (s=ZFAST_BITS+1; ; ++s)
 184       if (k < z->maxcode[s])
 185          break;
 186    if (s == 16)
 187     return -1; // invalid code!
 188
 189    // code size is s, so:
 190    b = (k >> (16-s)) - z->firstcode[s] + z->firstsymbol[s];
 191
 192    assert(z->size[b] == s);
 193
 194    inflate->code_buffer >>= s;
 195    inflate->num_bits -= s;
 196
 197    return z->value[b];
 198 }
 199
 200  // need to make room for n bytes
 201 static void expand(O2FlateDecode *inflate,int n)  {
 202    if(inflate->outPosition+n>inflate->outLength){
 203     do{
 204      inflate->outLength*=2;
 205     }while (inflate->outPosition + n > inflate->outLength);
 206
 207     inflate->outBytes = NSZoneRealloc(NULL,inflate->outBytes, inflate->outLength);
 208    }
 209 }
 210
 211 static void appendBytes(O2FlateDecode *inflate,const unsigned char *bytes,unsigned length){
 212    unsigned i;
 213
 214    for(i=0;i<length;i++)
 215     inflate->outBytes[inflate->outPosition++]=bytes[i];
 216 }
 217
 218 static int parse_huffman_block(O2FlateDecode *inflate) {
 219    for(;;) {
 220       int z = zhuffman_decode(inflate,&(inflate->z_length));
 221
 222       if (z < 256) {
 223          if (z < 0)
 224           return e("bad huffman code"); // error in huffman codes
 225
 226          expand(inflate,1);
 227          inflate->outBytes[inflate->outPosition++] = z;
 228       } else {
 229          int len,dist;
 230
 231          if (z == 256)
 232           return 1;
 233
 234          z -= 257;
 235          len = length_base[z];
 236          if (length_extra[z])
 237           len += zreceive(inflate,length_extra[z]);
 238
 239          z = zhuffman_decode(inflate,&(inflate->z_distance));
 240
 241          if (z < 0)
 242           return e("bad huffman code");
 243
 244          dist = dist_base[z];
 245          if (dist_extra[z])
 246           dist += zreceive(inflate,dist_extra[z]);
 247
 248          if (inflate->outPosition < dist)
 249           return e("bad dist");
 250
 251          expand(inflate,len); // we need to pre-expand to make sure outBytes doesn't change
 252          appendBytes(inflate,inflate->outBytes+inflate->outPosition-dist,len);
 253         }
 254    }
 255 }
 256
 257 static int compute_huffman_codes(O2FlateDecode *inflate) {
 258    static unsigned char length_dezigzag[19] = { 16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15 };
 259     zhuffman z_codelength;
 260    unsigned char lencodes[286+32+137];//padding for maximum single op
 261    unsigned char codelength_sizes[19];
 262    int i,n;
 263
 264    int hlit  = zreceive(inflate,5) + 257;
 265    int hdist = zreceive(inflate,5) + 1;
 266    int hclen = zreceive(inflate,4) + 4;
 267
 268    memset(codelength_sizes, 0, sizeof(codelength_sizes));
 269    for (i=0; i < hclen; ++i) {
 270       int s = zreceive(inflate,3);
 271
 272       codelength_sizes[length_dezigzag[i]] = s;
 273    }
 274    if (!zbuild_huffman(&z_codelength, codelength_sizes, 19))
 275     return 0;
 276
 277    n = 0;
 278    while (n < hlit + hdist) {
 279       int c = zhuffman_decode(inflate,&z_codelength);
 280
 281       assert(c >= 0 && c < 19);
 282
 283       if (c < 16)
 284          lencodes[n++] = c;
 285       else if (c == 16) {
 286          c = zreceive(inflate,2)+3;
 287          memset(lencodes+n, lencodes[n-1], c);
 288          n += c;
 289       } else if (c == 17) {
 290          c = zreceive(inflate,3)+3;
 291          memset(lencodes+n, 0, c);
 292          n += c;
 293       } else {
 294          assert(c == 18);
 295          c = zreceive(inflate,7)+11;
 296          memset(lencodes+n, 0, c);
 297          n += c;
 298       }
 299    }
 300    if (n != hlit+hdist)
 301     return e("bad codelengths");
 302    if (!zbuild_huffman(&(inflate->z_length), lencodes, hlit))
 303     return 0;
 304    if (!zbuild_huffman(&(inflate->z_distance), lencodes+hlit, hdist))
 305     return 0;
 306
 307    return 1;
 308 }
 309
 310 static int parse_uncompressed_block(O2FlateDecode *inflate) {
 311    unsigned char header[4];
 312    int len,nlen,k;
 313
 314    if (inflate->num_bits & 7)
 315       zreceive(inflate,inflate->num_bits & 7); // discard
 316
 317    // drain the bit-packed data into header
 318    k = 0;
 319    while (inflate->num_bits > 0) {
 320       header[k++] = (unsigned char) (inflate->code_buffer & 255); // wtf this warns?
 321       inflate->code_buffer >>= 8;
 322       inflate->num_bits -= 8;
 323    }
 324
 325    assert(inflate->num_bits == 0);
 326
 327    // now fill header the normal way
 328    while (k < 4)
 329       header[k++] = O2FlateDecodeNextByte(inflate);
 330
 331    len  = header[1] * 256 + header[0];
 332    nlen = header[3] * 256 + header[2];
 333
 334    if (nlen != (len ^ 0xffff))
 335     return e("zlib corrupt");
 336    if (inflate->inPosition + len > inflate->inLength)
 337     return e("read past buffer");
 338
 339    expand(inflate,len);
 340    appendBytes(inflate,inflate->inBytes+inflate->inPosition,len);
 341    inflate->inPosition += len;
 342
 343    return 1;
 344 }
 345
 346 static int parse_zlib_header(O2FlateDecode *inflate) {
 347    int cmf   = O2FlateDecodeNextByte(inflate);
 348       int cm       = cmf & 15;
 349      // int cinfo    = cmf >> 4;
 350    int flg   = O2FlateDecodeNextByte(inflate);
 351
 352    if ((cmf*256+flg) % 31 != 0)
 353     return e("bad zlib header"); // zlib spec
 354    if (flg & 32)
 355     return e("no preset dict"); // preset dictionary not allowed in png
 356    if (cm != 8)
 357     return e("bad compression"); // DEFLATE required for png
 358    // window = 1 << (8 + cinfo)... but who cares, we fully buffer output
 359
 360    return 1;
 361 }
 362
 363 static const unsigned char default_length[288] = {
 364 8,8,8,8,8,8,8,8,8,8,8,8,
 365 8,8,8,8,8,8,8,8,8,8,8,8,
 366 8,8,8,8,8,8,8,8,8,8,8,8,
 367 8,8,8,8,8,8,8,8,8,8,8,8,
 368 8,8,8,8,8,8,8,8,8,8,8,8,
 369 8,8,8,8,8,8,8,8,8,8,8,8,
 370 8,8,8,8,8,8,8,8,8,8,8,8,
 371 8,8,8,8,8,8,8,8,8,8,8,8,
 372 8,8,8,8,8,8,8,8,8,8,8,8,
 373 8,8,8,8,8,8,8,8,8,8,8,8,
 374 8,8,8,8,8,8,8,8,8,8,8,8,
 375 8,8,8,8,8,8,8,8,8,8,8,8,
 376 9,9,9,9,9,9,9,9,9,9,9,9,
 377 9,9,9,9,9,9,9,9,9,9,9,9,
 378 9,9,9,9,9,9,9,9,9,9,9,9,
 379 9,9,9,9,9,9,9,9,9,9,9,9,
 380 9,9,9,9,9,9,9,9,9,9,9,9,
 381 9,9,9,9,9,9,9,9,9,9,9,9,
 382 9,9,9,9,9,9,9,9,9,9,9,9,
 383 9,9,9,9,9,9,9,9,9,9,9,9,
 384 9,9,9,9,9,9,9,9,9,9,9,9,
 385 9,9,9,9,
 386 7,7,7,7,7,7,7,7,7,7,7,7,
 387 7,7,7,7,7,7,7,7,7,7,7,7,
 388 8,8,8,8,8,8,8,8,
 389
 390 };
 391
 392 static const unsigned char default_distance[32] = {
 393  5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
 394  5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
 395 };
 396
 397 static int parse_zlib(O2FlateDecode *inflate) {
 398    int final, type;
 399
 400    if (!parse_zlib_header(inflate))
 401     return 0;
 402    inflate->num_bits = 0;
 403    inflate->code_buffer = 0;
 404    do {
 405       final = zreceive(inflate,1);
 406       type = zreceive(inflate,2);
 407       if (type == 0) {
 408          if (!parse_uncompressed_block(inflate))
 409           return 0;
 410       } else if (type == 3) {
 411          return 0;
 412       } else {
 413          if (type == 1) {
 414             if (!zbuild_huffman(&(inflate->z_length)  , default_length  , 288))
 415              return 0;
 416             if (!zbuild_huffman(&(inflate->z_distance), default_distance,  32))
 417              return 0;
 418          } else {
 419             if (!compute_huffman_codes(inflate))
 420              return 0;
 421          }
 422          if (!parse_huffman_block(inflate))
 423           return 0;
 424       }
 425    } while (!final);
 426
 427    return 1;
 428 }
 429
 430 unsigned char *stbi_zlib_decode_malloc(const unsigned char *buffer, int len, int *outlen) {
 431    O2FlateDecode  inflateX;
 432    O2FlateDecode *inflate=&inflateX;
 433    int initial_size=8192;
 434    unsigned char *p = NSZoneMalloc(NULL,initial_size);
 435
 436    inflate->inBytes = buffer;
 437    inflate->inLength=len;
 438    inflate->inPosition=0;
 439
 440    if (p == NULL) return NULL;
 441
 442    inflate->outBytes = p;
 443    inflate->outPosition=0;
 444    inflate->outLength   =  initial_size;
 445
 446    if (parse_zlib(inflate)) {
 447       *outlen = inflate->outPosition;
 448       return inflate->outBytes;
 449    } else {
 450       free(inflate->outBytes);
 451       return NULL;
 452    }
 453 }