nanocoat/lib/base/inflate.c

   1 /* -*- Mode: C; indent-tabs-mode: t; tab-width: 4 -*-
   2 // ---------------------------------------------------------------------------
   3 // SquirrelJME
   4 //     Copyright (C) Stephanie Gawroriski <xer@multiphasicapps.net>
   5 // ---------------------------------------------------------------------------
   6 // SquirrelJME is under the Mozilla Public License Version 2.0.
   7 // See license.mkd for licensing and copyright information.
   8 // -------------------------------------------------------------------------*/
   9
  10 #include <string.h>
  11
  12 #include "sjme/inflate.h"
  13 #include "sjme/util.h"
  14
  15 /** Extra nodes to put into the traverse for overly complicated trees. */
  16 #define SJME_INFLATE_TRAVERSE_EXTRA \
  17         (maxCount)
  18
  19 /** Shuffled code length bits. */
  20 static const sjme_jubyte sjme_inflate_shuffleBits[SJME_INFLATE_NUM_CODE_LEN] =
  21 {
  22         16, 17, 18, 0, 8, 7, 9, 6,
  23         10, 5, 11, 4, 12, 3, 13,
  24         2, 14, 1, 15
  25 };
  26
  27 static sjme_errorCode sjme_inflate_bitFill(
  28         sjme_attrInNotNull sjme_inflate* inState)
  29 {
  30         sjme_errorCode error;
  31         sjme_jint avail, readCount;
  32         sjme_jubyte* buffer;
  33
  34         if (inState == NULL)
  35                 return SJME_ERROR_NULL_ARGUMENTS;
  36
  37         /* Pointless if the input hit EOF. */
  38         if (inState->inputEof)
  39                 return SJME_ERROR_NONE;
  40
  41         /* How much space is left in the input buffer? */
  42         avail = INT32_MAX;
  43         if (sjme_error_is(error = sjme_circleBuffer_available(
  44                 inState->inputBuffer, &avail)) ||
  45                 avail == INT32_MAX)
  46                 return sjme_error_default(error);
  47
  48         /* It is as full as it can get. */
  49         if (avail <= 0)
  50                 return SJME_ERROR_NONE;
  51
  52         /* Setup target buffer to read into. */
  53         buffer = sjme_alloca(avail);
  54         if (buffer == NULL)
  55                 return SJME_ERROR_OUT_OF_MEMORY;
  56         memset(buffer, 0, avail);
  57
  58         /* Read everything in as much as possible. */
  59         readCount = INT32_MAX;
  60         if (sjme_error_is(error = sjme_stream_inputReadFully(
  61                 inState->source, &readCount, buffer, avail)) ||
  62                 readCount == INT32_MAX)
  63                 return sjme_error_default(error);
  64
  65         /* EOF? */
  66         if (readCount < 0)
  67         {
  68                 inState->inputEof = SJME_JNI_TRUE;
  69                 return SJME_ERROR_NONE;
  70         }
  71
  72         /* Push onto the buffer. */
  73         if (sjme_error_is(error = sjme_circleBuffer_push(
  74                 inState->inputBuffer,
  75                 buffer, readCount,
  76                 SJME_CIRCLE_BUFFER_TAIL)))
  77                 return sjme_error_default(error);
  78
  79         /* Success! */
  80         return SJME_ERROR_NONE;
  81 }
  82
  83 static sjme_errorCode sjme_inflate_bitRead(
  84         sjme_attrInNotNull sjme_bitStream_input inStream,
  85         sjme_attrInNullable sjme_pointer functionData,
  86         sjme_attrOutNotNull sjme_jint* readCount,
  87         sjme_attrOutNotNullBuf(length) sjme_pointer outBuf,
  88         sjme_attrInPositiveNonZero sjme_jint length)
  89 {
  90         sjme_errorCode error;
  91         sjme_inflate* inState;
  92         sjme_jint limit;
  93
  94         inState = functionData;
  95         if (inStream == NULL || inState == NULL || readCount == NULL ||
  96                 outBuf == NULL)
  97                 return SJME_ERROR_NULL_ARGUMENTS;
  98
  99         if (length <= 0)
 100                 return SJME_ERROR_INDEX_OUT_OF_BOUNDS;
 101
 102         /* Always fill in before read. */
 103         if (sjme_error_is(error = sjme_inflate_bitFill(inState)))
 104                 return sjme_error_default(error);
 105
 106         /* How much is in the input buffer? */
 107         limit = INT32_MAX;
 108         if (sjme_error_is(error = sjme_circleBuffer_stored(
 109                 inState->inputBuffer, &limit)) ||
 110                 limit == INT32_MAX)
 111                 return sjme_error_default(error);
 112
 113         /* If this is zero then we do not have enough to read from. */
 114         if (limit == 0)
 115         {
 116                 /* However if EOF was hit, we stop. */
 117                 if (inState->inputEof)
 118                 {
 119                         *readCount = -1;
 120                         return SJME_ERROR_NONE;
 121                 }
 122
 123                 /* Otherwise, we need more data! */
 124                 return SJME_ERROR_TOO_SHORT;
 125         }
 126
 127         /* Do not exceed the storage limit. */
 128         if (limit > length)
 129                 limit = length;
 130
 131         /* Pop from the buffer. */
 132         if (sjme_error_is(error = sjme_circleBuffer_pop(
 133                 inState->inputBuffer, outBuf, limit,
 134                 SJME_CIRCLE_BUFFER_HEAD)))
 135                 return sjme_error_default(error);
 136
 137         /* Success! */
 138         *readCount = limit;
 139         return SJME_ERROR_NONE;
 140 }
 141
 142 static sjme_errorCode sjme_inflate_bitWrite(
 143         sjme_attrInNotNull sjme_bitStream_output outStream,
 144         sjme_attrInNullable sjme_pointer functionData,
 145         sjme_attrInNotNullBuf(length) sjme_buffer writeBuf,
 146         sjme_attrInPositiveNonZero sjme_jint length)
 147 {
 148         sjme_errorCode error;
 149         sjme_inflate* inState;
 150
 151         inState = functionData;
 152         if (outStream == NULL || inState == NULL || writeBuf == NULL)
 153                 return SJME_ERROR_NULL_ARGUMENTS;
 154
 155         if (length <= 0)
 156                 return SJME_ERROR_INDEX_OUT_OF_BOUNDS;
 157
 158         /* Push onto the window. */
 159         if (sjme_error_is(error = sjme_circleBuffer_push(
 160                 inState->window, writeBuf, length,
 161                 SJME_CIRCLE_BUFFER_TAIL)))
 162                 return sjme_error_default(error);
 163
 164         /* And onto the output buffer. */
 165         if (sjme_error_is(error = sjme_circleBuffer_push(
 166                 inState->outputBuffer, writeBuf, length,
 167                 SJME_CIRCLE_BUFFER_TAIL)))
 168                 return sjme_error_default(error);
 169
 170 #if defined(SJME_CONFIG_DEBUG) && defined(SJME_CONFIG_VERBOSE_INFLATE)
 171         /* Debug. */
 172         sjme_message_hexDump(writeBuf, length);
 173 #endif
 174
 175         /* Success! */
 176         return SJME_ERROR_NONE;
 177 }
 178
 179 static sjme_errorCode sjme_inflate_bufferSaturation(
 180         sjme_attrInNotNull sjme_inflate* inState,
 181         sjme_attrInPositiveNonZero sjme_jint bitsNeeded)
 182 {
 183         sjme_errorCode error;
 184         sjme_jint ready;
 185
 186         if (inState == NULL)
 187                 return SJME_ERROR_NULL_ARGUMENTS;
 188
 189         if (bitsNeeded <= 0)
 190                 return SJME_ERROR_INVALID_ARGUMENT;
 191
 192         /* The output buffer is saturated? */
 193         if (inState->outputBuffer->ready >= SJME_INFLATE_IO_BUFFER_SATURATED)
 194                 return SJME_ERROR_BUFFER_SATURATED;
 195
 196         /* How many bits are already in the window? */
 197         ready = INT32_MAX;
 198         if (sjme_error_is(error = sjme_bitStream_bitsReady(
 199                 SJME_AS_BITSTREAM(inState->input),
 200                 &ready)) || ready == INT32_MAX)
 201                 return sjme_error_default(error);
 202
 203         /* Add in all the input buffer bytes. */
 204         ready += (inState->inputBuffer->ready * 8);
 205
 206         /* Do we have enough? */
 207         if (ready >= bitsNeeded)
 208                 return SJME_ERROR_NONE;
 209         return SJME_ERROR_TOO_SHORT;
 210 }
 211
 212 static sjme_errorCode sjme_inflate_copyWindow(
 213         sjme_attrInNotNull sjme_inflate* inState,
 214         sjme_attrInValue sjme_jint length,
 215         sjme_attrInValue sjme_jint dist)
 216 {
 217         sjme_errorCode error;
 218         sjme_jint maxLen, i, at;
 219         sjme_jubyte* buf;
 220
 221         if (inState == NULL)
 222                 return SJME_ERROR_NULL_ARGUMENTS;
 223
 224         /* The maximum length that is valid is the smaller of the two values, */
 225         /* essentially the length could be 5 but the distance 2, we cannot */
 226         /* read past the end of the window, we can only read 2 bytes. */
 227         maxLen = (length < dist ? length : dist);
 228
 229         /* Allocate window buffer. */
 230         buf = sjme_alloca(maxLen);
 231         if (buf == NULL)
 232                 return SJME_ERROR_OUT_OF_MEMORY;
 233         memset(buf, 0, maxLen);
 234
 235         /* Read in from the window. */
 236         if (sjme_error_is(error = sjme_circleBuffer_get(inState->window,
 237                 buf, maxLen,
 238                 SJME_CIRCLE_BUFFER_TAIL, dist)))
 239                 return sjme_error_default(error);
 240
 241         /* Write in bytes from the window, this always wraps around the buffer. */
 242         for (i = 0, at = 0; i < length; i++)
 243         {
 244                 /* Write single byte. */
 245                 if (sjme_error_is(error = sjme_bitStream_outputWrite(
 246                         inState->output, SJME_BITSTREAM_LSB,
 247                         buf[at], 8)))
 248                         return sjme_error_default(error);
 249
 250                 /* Overflowing? */
 251                 if ((++at) >= maxLen)
 252                         at = 0;
 253         }
 254
 255         /* Success! */
 256         return SJME_ERROR_NONE;
 257 }
 258
 259 static sjme_errorCode sjme_inflate_drain(
 260         sjme_attrInNotNull sjme_inflate* inState,
 261         sjme_attrInOutNotNull sjme_jint* drainOff,
 262         sjme_attrOutNotNullBuf(length) sjme_buffer outBuf,
 263         sjme_attrInPositiveNonZero sjme_jint length)
 264 {
 265         sjme_errorCode error;
 266         sjme_jint stored, limit;
 267
 268         if (inState == NULL || drainOff == NULL || outBuf == NULL)
 269                 return SJME_ERROR_NULL_ARGUMENTS;
 270
 271         if (length <= 0)
 272                 return SJME_ERROR_INDEX_OUT_OF_BOUNDS;
 273
 274         /* How much is in the output buffer? */
 275         stored = INT32_MAX;
 276         if (sjme_error_is(error = sjme_circleBuffer_stored(
 277                 inState->outputBuffer, &stored)) ||
 278                 stored == INT32_MAX)
 279                 return sjme_error_default(error);
 280
 281         /* How much can be drained? */
 282         limit = length - (*drainOff);
 283         if (limit > stored)
 284                 limit = stored;
 285
 286         /* Nothing to do? */
 287         if (limit == 0)
 288                 return SJME_ERROR_NONE;
 289
 290         /* Pop off the head. */
 291         if (sjme_error_is(error = sjme_circleBuffer_pop(
 292                 inState->outputBuffer,
 293                 SJME_POINTER_OFFSET(outBuf, (*drainOff)),
 294                 limit, SJME_CIRCLE_BUFFER_HEAD)))
 295                 return sjme_error_default(error);
 296
 297         /* Move up the drain offset, which is also the cumulative total output. */
 298         (*drainOff) += limit;
 299
 300         /* Success! */
 301         return SJME_ERROR_NONE;
 302 }
 303
 304 static sjme_errorCode sjme_inflate_dynamicBitIn(
 305         sjme_attrInNotNull sjme_inflate* inState,
 306         sjme_attrInNotNull sjme_traverse_sjme_jint fromTree,
 307         sjme_attrOutNotNull sjme_juint* outValue)
 308 {
 309         sjme_errorCode error;
 310         sjme_traverse_iterator iterator;
 311         sjme_juint bit;
 312         sjme_juint* result;
 313
 314         if (inState == NULL || fromTree == NULL || outValue == NULL)
 315                 return SJME_ERROR_NULL_ARGUMENTS;
 316
 317         /* Start tree iteration. */
 318         memset(&iterator, 0, sizeof(iterator));
 319         if (sjme_error_is(error = sjme_traverse_iterate(
 320                 SJME_AS_TRAVERSE(fromTree), &iterator)))
 321                 return sjme_error_default(error);
 322
 323         /* Constantly read in bits until a leaf is hit. */
 324         for (;;)
 325         {
 326                 /* Read in bit. */
 327                 bit = INT32_MAX;
 328                 if (sjme_error_is(error = sjme_bitStream_inputRead(
 329                         inState->input,
 330                         SJME_BITSTREAM_LSB, &bit, 1)) ||
 331                         bit == INT32_MAX)
 332                         return sjme_error_default(error);
 333
 334                 /* Traverse in the tree. */
 335                 result = NULL;
 336                 if (sjme_error_is(error = sjme_traverse_iterateNext(
 337                         fromTree, &iterator, &result, bit, 1, sjme_jint, 0)))
 338                         return sjme_error_default(error);
 339
 340                 /* If a value was read, we are at a leaf. */
 341                 if (result != NULL)
 342                 {
 343                         *outValue = *result;
 344                         return SJME_ERROR_NONE;
 345                 }
 346         }
 347
 348         /* Fail if no value was read. */
 349         return SJME_ERROR_INFLATE_INVALID_CODE;
 350 }
 351
 352 static sjme_errorCode sjme_inflate_dynamicBuildReadCode(
 353         sjme_attrInNotNull sjme_inflate* inState,
 354         sjme_attrOutNotNull sjme_juint* codes,
 355         sjme_attrInOutNotNull sjme_jint* i,
 356         sjme_attrInPositiveNonZero sjme_jint count,
 357         sjme_attrInPositiveNonZero sjme_jint maxCount)
 358 {
 359         sjme_errorCode error;
 360         sjme_traverse_sjme_jint treeCodeLen;
 361         sjme_juint code, repFor, repVal;
 362         sjme_jint x;
 363
 364         if (inState == NULL || codes == NULL || i == NULL)
 365                 return SJME_ERROR_NONE;
 366
 367         if (count <= 0 || maxCount <= 0)
 368                 return SJME_ERROR_INVALID_ARGUMENT;
 369
 370         /* Need the code length tree. */
 371         treeCodeLen = inState->treeCodeLen;
 372         if (treeCodeLen == NULL)
 373                 return SJME_ERROR_ILLEGAL_STATE;
 374
 375         /* Read in code from the tree. */
 376         code = INT32_MAX;
 377         if (sjme_error_is(error = sjme_inflate_dynamicBitIn(
 378                 inState, treeCodeLen, &code)) || code == INT32_MAX)
 379                 return sjme_error_default(error);
 380
 381         /* Input is used literally. */
 382         if (code >= 0 && code < 16)
 383         {
 384                 if ((*i) >= maxCount)
 385                         return SJME_ERROR_INFLATE_INDEX_OVERFLOW;
 386
 387                 /* Uses the same input code. */
 388                 codes[(*i)++] = code;
 389                 return SJME_ERROR_NONE;
 390         }
 391
 392         /* Repeat previous length 3-6 times. */
 393         repVal = INT32_MAX;
 394         repFor = INT32_MAX;
 395         if (code == 16)
 396         {
 397                 /* Cannot be the first entry. */
 398                 if ((*i) <= 0)
 399                         return SJME_ERROR_INFLATE_INVALID_CODE_LENGTH;
 400
 401                 /* Repeat this... */
 402                 repVal = codes[(*i) - 1];
 403
 404                 /* This many times. */
 405                 if (sjme_error_is(error = sjme_bitStream_inputRead(
 406                         inState->input, SJME_BITSTREAM_LSB,
 407                         &repFor, 2)) || repFor == INT32_MAX)
 408                         return sjme_error_default(error);
 409                 repFor += 3;
 410         }
 411
 412         /* Repeat zero for 3-10 times */
 413         else if (code == 17)
 414         {
 415                 /* Repeat zero... */
 416                 repVal = 0;
 417
 418                 /* This many times. */
 419                 if (sjme_error_is(error = sjme_bitStream_inputRead(
 420                         inState->input, SJME_BITSTREAM_LSB,
 421                         &repFor, 3)) || repFor == INT32_MAX)
 422                         return sjme_error_default(error);
 423                 repFor += 3;
 424         }
 425
 426         /* Repeat zero for 11-138 times */
 427         else if (code == 18)
 428         {
 429                 /* Repeat zero... */
 430                 repVal = 0;
 431
 432                 /* This many times. */
 433                 if (sjme_error_is(error = sjme_bitStream_inputRead(
 434                         inState->input, SJME_BITSTREAM_LSB,
 435                         &repFor, 7)) || repFor == INT32_MAX)
 436                         return sjme_error_default(error);
 437                 repFor += 11;
 438         }
 439
 440         /* Invalid. */
 441         if (repFor == INT32_MAX || repVal == INT32_MAX)
 442                 return SJME_ERROR_INFLATE_INVALID_CODE;
 443
 444         /* Store in repeated values. */
 445         for (x = 0; x < repFor; x++)
 446         {
 447                 if ((*i) >= maxCount)
 448                         return SJME_ERROR_INFLATE_INDEX_OVERFLOW;
 449
 450                 /* Repeat the requested code. */
 451                 codes[(*i)++] = repVal;
 452         }
 453
 454         /* Success! */
 455         return SJME_ERROR_NONE;
 456 }
 457
 458 static sjme_errorCode sjme_inflate_dynamicBuildTree(
 459         sjme_attrInNotNull sjme_inflate* inState,
 460         sjme_attrOutNotNull sjme_traverse_sjme_jint* outTree,
 461         sjme_attrInNotNullBuf(count) sjme_juint* codeLens,
 462         sjme_attrInPositiveNonZero sjme_jint count,
 463         sjme_attrInPositiveNonZero sjme_jint maxCount)
 464 {
 465 #if defined(SJME_CONFIG_DEBUG) && defined(SJME_CONFIG_VERBOSE_INFLATE)
 466         sjme_cchar binary[40];
 467 #endif
 468         sjme_errorCode error;
 469         sjme_juint blCount[SJME_INFLATE_CODE_LEN_MAX_BITS + 1];
 470         sjme_juint nextCode[SJME_INFLATE_CODE_LEN_MAX_BITS + 1];
 471         sjme_juint code, len, nextCodeLen;
 472         sjme_jint i;
 473
 474         if (inState == NULL || outTree == NULL || codeLens == NULL)
 475                 return SJME_ERROR_NULL_ARGUMENTS;
 476
 477         if (count <= 0 || maxCount <= 0 || count > maxCount)
 478                 return SJME_ERROR_INVALID_ARGUMENT;
 479
 480         /* Need to allocate the tree? */
 481         if ((*outTree) == NULL)
 482                 if (sjme_error_is(error = sjme_traverse_new(
 483                         inState->inPool, outTree,
 484                         maxCount + SJME_INFLATE_TRAVERSE_EXTRA,
 485                         sjme_jint, 0)) ||
 486                         (*outTree) == NULL)
 487                         return sjme_error_default(error);
 488
 489         /* Wipe working arrays. */
 490         memset(blCount, 0, sizeof(blCount));
 491         memset(nextCode, 0, sizeof(nextCode));
 492
 493         /* Determine the bit length count for all the inputs */
 494         for (i = 0; i < count; i++)
 495                 blCount[codeLens[i]]++;
 496         blCount[0] = 0;
 497
 498         /* Find the numerical value of the smallest code for each code length. */
 499         code = 0;
 500         for (i = 1; i <= SJME_INFLATE_CODE_LEN_MAX_BITS; i++)
 501         {
 502                 code = (code + blCount[i - 1]) << 1;
 503                 nextCode[i] = code;
 504         }
 505
 506         /* Clear the target tree. */
 507         if (sjme_error_is(error = sjme_traverse_clear(
 508                 SJME_AS_TRAVERSE((*outTree)))))
 509                 return sjme_error_default(error);
 510
 511         /* Assign all values to codes. */
 512         for (i = 0; i < count; i++)
 513         {
 514                 /* Add code length to the huffman tree */
 515                 len = codeLens[i];
 516                 if (len != 0)
 517                 {
 518                         nextCodeLen = (nextCode[len])++;
 519
 520 #if defined(SJME_CONFIG_DEBUG) && defined(SJME_CONFIG_VERBOSE_INFLATE)
 521                         sjme_util_intToBinary(
 522                                 binary, sizeof(binary) - 1,
 523                                 nextCodeLen, len);
 524                         sjme_message("Tree -> %s = %d",
 525                                 binary, i);
 526 #endif
 527
 528                         /* Put into the tree. */
 529                         if (sjme_error_is(error = sjme_traverse_putM(
 530                                 SJME_AS_TRAVERSE((*outTree)),
 531                                 SJME_TRAVERSE_NORMAL,
 532                                 &i, nextCodeLen, len,
 533                                 sjme_jint, 0)))
 534                                 return sjme_error_default(error);
 535                 }
 536         }
 537
 538         /* Success! */
 539         return SJME_ERROR_NONE;
 540 }
 541
 542 static sjme_errorCode sjme_inflate_dynamicReadCode(
 543         sjme_attrInNotNull sjme_inflate* inState,
 544         sjme_attrOutNotNull sjme_juint* outCode)
 545 {
 546         sjme_errorCode error;
 547         sjme_juint code;
 548
 549         if (inState == NULL || outCode == NULL)
 550                 return SJME_ERROR_NULL_ARGUMENTS;
 551
 552         /* At least 1 bit of data. */
 553         if (sjme_error_is(error = sjme_inflate_bufferSaturation(inState,
 554                 1)))
 555                 return sjme_error_default(error);
 556
 557         /* Read in code. */
 558         code = INT32_MAX;
 559         if (sjme_error_is(error = sjme_inflate_dynamicBitIn(
 560                 inState, inState->treeLit, &code)) ||
 561                 code == INT32_MAX)
 562                 return sjme_error_default(error);
 563
 564         /* Give the code. */
 565         *outCode = code;
 566         return SJME_ERROR_NONE;
 567 }
 568
 569 static sjme_errorCode sjme_inflate_dynamicReadDist(
 570         sjme_attrInNotNull sjme_inflate* inState,
 571         sjme_attrOutNotNull sjme_juint* outDist)
 572 {
 573         sjme_errorCode error;
 574         sjme_juint code;
 575
 576         if (inState == NULL || outDist == NULL)
 577                 return SJME_ERROR_NULL_ARGUMENTS;
 578
 579         /* At least 1 bit of data. */
 580         if (sjme_error_is(error = sjme_inflate_bufferSaturation(inState,
 581                 1)))
 582                 return sjme_error_default(error);
 583
 584         /* Read in code. */
 585         code = INT32_MAX;
 586         if (sjme_error_is(error = sjme_inflate_dynamicBitIn(
 587                 inState, inState->treeDist, &code)) ||
 588                 code == INT32_MAX)
 589                 return sjme_error_default(error);
 590
 591         /* Give the code. */
 592         *outDist = code;
 593         return SJME_ERROR_NONE;
 594 }
 595
 596 static sjme_errorCode sjme_inflate_fixedReadCode(
 597         sjme_attrInNotNull sjme_inflate* inState,
 598         sjme_attrOutNotNull sjme_juint* outCode)
 599 {
 600         sjme_errorCode error;
 601         sjme_juint nine, nextBits, codeBase, nineBase, fragment;
 602
 603         if (inState == NULL || outCode == NULL)
 604                 return SJME_ERROR_NULL_ARGUMENTS;
 605
 606         /* Make sure we at least have 7 bits available. */
 607         if (sjme_error_is(error = sjme_inflate_bufferSaturation(inState,
 608                 7)))
 609                 return sjme_error_default(error);
 610
 611         /* Read in the first, or only, seven bits. */
 612         nine = INT32_MAX;
 613         if (sjme_error_is(error = sjme_bitStream_inputRead(
 614                 inState->input,
 615                 SJME_BITSTREAM_MSB, &nine, 7)) ||
 616                 nine == INT32_MAX)
 617                 return sjme_error_default(error);
 618
 619         /* Make this nine bits for consistency. */
 620         nine <<= 2;
 621
 622         /* Based on the current bit set, determine the code and remaining */
 623         /* bits we can read. */
 624         /* The mask is {upper range - lower range}, and is added to the base. */
 625         codeBase = INT32_MAX;
 626         nextBits = INT32_MAX;
 627         nineBase = INT32_MAX;
 628
 629         /* 256 - 279 / 0000000.. - 0010111.. */
 630         if (nine >= 0x000 && nine <= 0x05F)
 631         {
 632                 codeBase = 256;
 633                 nextBits = 0;
 634                 nineBase = 0x000;
 635         }
 636
 637         /*   0 - 143 / 00110000. - 10111111. */
 638         else if (nine >= 0x060 && nine <= 0x17F)
 639         {
 640                 codeBase = 0;
 641                 nextBits = 1;
 642                 nineBase = 0x060;
 643         }
 644
 645         /* 280 - 287 / 11000000. - 11000111. */
 646         else if (nine >= 0x180 && nine <= 0x18F)
 647         {
 648                 codeBase = 280;
 649                 nextBits = 1;
 650                 nineBase = 0x180;
 651         }
 652
 653         /* 144 - 255 / 110010000 - 111111111 */
 654         else if (nine >= 0x190 && nine <= 0x1FF)
 655         {
 656                 codeBase = 144;
 657                 nextBits = 2;
 658                 nineBase = 0x190;
 659         }
 660
 661         /* Invalid code? */
 662         if (codeBase == INT32_MAX || nextBits == INT32_MAX ||
 663                 nineBase == INT32_MAX)
 664                 return SJME_ERROR_INFLATE_INVALID_CODE;
 665
 666         /* If there are more bits to read, read them in now. */
 667         fragment = 0;
 668         if (nextBits != 0)
 669         {
 670                 /* Read in bits. */
 671                 fragment = INT32_MAX;
 672                 if (sjme_error_is(error = sjme_bitStream_inputRead(
 673                         inState->input, SJME_BITSTREAM_MSB,
 674                         &fragment, nextBits)) || fragment == INT32_MAX)
 675                         return sjme_error_default(error);
 676         }
 677
 678         /* Recompose the code, remember that we shifted left twice to make */
 679         /* a consistent 9 bits, if we did not need to do that, then undo it. */
 680         *outCode = codeBase + ((((nine - nineBase) >> (2 - nextBits)) | fragment));
 681
 682         /* Success! */
 683         return SJME_ERROR_NONE;
 684 }
 685
 686 static sjme_errorCode sjme_inflate_fixedReadDist(
 687         sjme_attrInNotNull sjme_inflate* inState,
 688         sjme_attrOutNotNull sjme_juint* outDist)
 689 {
 690         sjme_errorCode error;
 691         sjme_juint result;
 692
 693         if (inState == NULL || outDist == NULL)
 694                 return SJME_ERROR_NULL_ARGUMENTS;
 695
 696         /* Fixed huffman distance codes are always 5 bits. */
 697         result = INT32_MAX;
 698         if (sjme_error_is(error = sjme_bitStream_inputRead(
 699                 inState->input, SJME_BITSTREAM_MSB,
 700                 &result, 5)) || result == INT32_MAX)
 701                 return sjme_error_default(error);
 702
 703         /* Success! */
 704         *outDist = result;
 705         return SJME_ERROR_NONE;
 706 }
 707
 708 static sjme_errorCode sjme_inflate_readDistance(
 709         sjme_attrInNotNull sjme_inflate* inState,
 710         sjme_attrOutNotNull sjme_juint* outDist)
 711 {
 712         sjme_errorCode error;
 713         sjme_juint code, result, i, group;
 714
 715         if (inState == NULL || outDist == NULL)
 716                 return SJME_ERROR_NULL_ARGUMENTS;
 717
 718         /* Read in the base distance code. */
 719         code = INT32_MAX;
 720         if (sjme_error_is(error = inState->sub.huffman.readDist(
 721                 inState, &code)) || code == INT32_MAX)
 722                 return sjme_error_default(error);
 723
 724         /* Distance codes can only be so high. */
 725         if (code > 29)
 726                 return SJME_ERROR_INFLATE_INVALID_CODE;
 727
 728         /* Distances always start at 1. */
 729         result = 1;
 730
 731         /* Determine if any bits repeat. */
 732         for (i = 0; i < code; i++)
 733         {
 734                 /* Too short to repeat? */
 735                 if (i < 2)
 736                 {
 737                         result++;
 738                         continue;
 739                 }
 740
 741                 /* Otherwise, repeats in groups of two. */
 742                 group = ((i / 2) - 1);
 743                 result += (1 << group);
 744         }
 745
 746         /* Do we need to read in any extra bits to the distance value? */
 747         if (code >= 4)
 748         {
 749                 /* How many bits to read? */
 750                 group = (code / 2) - 1;
 751
 752                 /* Read in those extra bits. */
 753                 i = INT32_MAX;
 754                 if (sjme_error_is(error = sjme_bitStream_inputRead(
 755                         inState->input, SJME_BITSTREAM_LSB,
 756                         &i, group)) || i == INT32_MAX)
 757                         return sjme_error_default(error);
 758
 759                 /* Add in those bits. */
 760                 result += i;
 761         }
 762
 763         /* Success! */
 764         *outDist = result;
 765         return SJME_ERROR_NONE;
 766 }
 767
 768 static sjme_errorCode sjme_inflate_readLength(
 769         sjme_attrInNotNull sjme_inflate* inState,
 770         sjme_attrInRange(257, 285) sjme_juint code,
 771         sjme_attrOutNotNull sjme_juint* outLength)
 772 {
 773         sjme_errorCode error;
 774         sjme_juint result, base, i, group;
 775
 776         if (inState == NULL || outLength == NULL)
 777                 return SJME_ERROR_NULL_ARGUMENTS;
 778
 779         if (code < 257 || code > 285)
 780                 return SJME_ERROR_INVALID_ARGUMENT;
 781
 782         /* The max code is 258, note the fifty-eight and not eighty-five. */
 783         /* Previously in my Java inflate code, getting these wrong was bad. */
 784         if (code == 285)
 785         {
 786                 *outLength = 258;
 787                 return SJME_ERROR_NONE;
 788         }
 789
 790         /* Resultant length always starts at three. */
 791         result = 3;
 792
 793         /* Determine if there are any repeating bits. */
 794         for (base = code - 257, i = 0; i < base; i++)
 795         {
 796                 /* Is too short to be in a group. */
 797                 if (i < 8)
 798                 {
 799                         result++;
 800                         continue;
 801                 }
 802
 803                 /* Code lengths are in groups of 4, which get shifted up by their */
 804                 /* group index. */
 805                 group = ((i / 4) - 1);
 806                 result += (1 << group);
 807         }
 808
 809         /* Do we need to read in any extra bits to the length value? */
 810         if (base >= 8)
 811         {
 812                 /* How many bits to read? */
 813                 group = (base / 4) - 1;
 814
 815                 /* Read in those extra bits. */
 816                 i = INT32_MAX;
 817                 if (sjme_error_is(error = sjme_bitStream_inputRead(
 818                         inState->input, SJME_BITSTREAM_LSB,
 819                         &i, group)) || i == INT32_MAX)
 820                         return sjme_error_default(error);
 821
 822                 /* Add in those bits. */
 823                 result += i;
 824         }
 825
 826         /* Success! */
 827         *outLength = result;
 828         return SJME_ERROR_NONE;
 829 }
 830
 831 static sjme_errorCode sjme_inflate_stepBType(
 832         sjme_attrInNotNull sjme_inflate* inState)
 833 {
 834         sjme_errorCode error;
 835         sjme_juint isFinal, blockType;
 836
 837         if (inState == NULL)
 838                 return SJME_ERROR_NULL_ARGUMENTS;
 839
 840         /* If final was hit, then we are done. */
 841         if (inState->finalHit)
 842         {
 843                 inState->step = SJME_INFLATE_STEP_FINISHED;
 844                 return SJME_ERROR_NONE;
 845         }
 846
 847         /* Can we actually read the block? */
 848         if (sjme_error_is(error = sjme_inflate_bufferSaturation(
 849                 inState, 3)))
 850                 return sjme_error_default(error);
 851
 852         /* Read in final block flag. */
 853         isFinal = INT32_MAX;
 854         if (sjme_error_is(error = sjme_bitStream_inputRead(
 855                 inState->input,
 856                 SJME_BITSTREAM_LSB, &isFinal, 1)) ||
 857                 isFinal == INT32_MAX)
 858                 return sjme_error_default(error);
 859
 860         /* Read in block type. */
 861         blockType = INT32_MAX;
 862         if (sjme_error_is(error = sjme_bitStream_inputRead(
 863                 inState->input,
 864                 SJME_BITSTREAM_LSB, &blockType, 2)) ||
 865                 blockType == INT32_MAX)
 866                 return sjme_error_default(error);
 867
 868         /* Invalid. */
 869         if (blockType == 3)
 870                 return SJME_ERROR_INFLATE_INVALID_BTYPE;
 871
 872         /* Was the final block hit? */
 873         if (isFinal)
 874                 inState->finalHit = SJME_JNI_TRUE;
 875
 876         /* Which step to transition to? */
 877         if (blockType == 0)
 878                 inState->step = SJME_INFLATE_STEP_LITERAL_SETUP;
 879         else if (blockType == 1)
 880                 inState->step = SJME_INFLATE_STEP_FIXED_SETUP;
 881         else
 882                 inState->step = SJME_INFLATE_STEP_DYNAMIC_SETUP;
 883
 884         /* Success! */
 885         return SJME_ERROR_NONE;
 886 }
 887
 888 sjme_errorCode sjme_inflate_stepLiteralData(
 889         sjme_attrInNotNull sjme_inflate* inState)
 890 {
 891         sjme_errorCode error;
 892         sjme_jint left;
 893         sjme_juint raw;
 894
 895         if (inState == NULL)
 896                 return SJME_ERROR_NULL_ARGUMENTS;
 897
 898         /* Copy in what we can, provided the buffers are not saturated */
 899         /* and we have input data. */
 900         left = inState->sub.literalLeft;
 901         while (left > 0)
 902         {
 903                 /* Can we actually read a byte? */
 904                 if (sjme_error_is(error = sjme_inflate_bufferSaturation(
 905                         inState, 8)))
 906                         goto fail_saturated;
 907
 908                 /* Read in byte. */
 909                 raw = INT32_MAX;
 910                 if (sjme_error_is(error = sjme_bitStream_inputRead(
 911                         inState->input,
 912                         SJME_BITSTREAM_LSB, &raw, 8)) ||
 913                         raw == INT32_MAX)
 914                         goto fail_read;
 915
 916                 /* Write out bits. */
 917                 if (sjme_error_is(error = sjme_bitStream_outputWrite(
 918                         inState->output,
 919                         SJME_BITSTREAM_LSB, raw, 8)))
 920                         goto fail_write;
 921
 922                 /* We consumed a byte. */
 923                 left--;
 924         }
 925
 926         /* Store for next run. */
 927         inState->sub.literalLeft = left;
 928
 929         /* Did we read in all the data? Go back to the block type parse. */
 930         if (left == 0)
 931                 inState->step = SJME_INFLATE_STEP_CHECK_BTYPE;
 932
 933         /* Success! */
 934         return SJME_ERROR_NONE;
 935
 936 fail_write:
 937 fail_read:
 938 fail_saturated:
 939         /* Store for next run. */
 940         inState->sub.literalLeft = left;
 941
 942         return sjme_error_default(error);
 943 }
 944
 945 sjme_errorCode sjme_inflate_stepLiteralSetup(
 946         sjme_attrInNotNull sjme_inflate* inState)
 947 {
 948         sjme_errorCode error;
 949         sjme_juint len, nel;
 950
 951         if (inState == NULL)
 952                 return SJME_ERROR_NULL_ARGUMENTS;
 953
 954         /* Literal uncompressed data starts at the byte boundary. */
 955         if (sjme_error_is(error = sjme_bitStream_inputAlign(
 956                 inState->input,
 957                 8, NULL)))
 958                 return sjme_error_default(error);
 959
 960         /* Can we actually read the lengths? */
 961         if (sjme_error_is(error = sjme_inflate_bufferSaturation(
 962                 inState, 32)))
 963                 return sjme_error_default(error);
 964
 965         /* Read both the length and its complement. */
 966         len = INT32_MAX;
 967         nel = INT32_MAX;
 968         if (sjme_error_is(error = sjme_bitStream_inputRead(
 969                 inState->input, SJME_BITSTREAM_LSB,
 970                 &len, 16)))
 971                 return sjme_error_default(error);
 972         if (sjme_error_is(error = sjme_bitStream_inputRead(
 973                 inState->input, SJME_BITSTREAM_LSB,
 974                 &nel, 16)))
 975                 return sjme_error_default(error);
 976
 977         /* Both of these should be the complement to each other. */
 978         if (len != (nel ^ 0xFFFF))
 979                 return SJME_ERROR_INFLATE_INVALID_INVERT;
 980
 981         /* Setup for next step. */
 982         memset(&inState->sub, 0, sizeof(inState->sub));
 983         inState->sub.literalLeft = len;
 984         inState->step = SJME_INFLATE_STEP_LITERAL_DATA;
 985
 986         /* Success! */
 987         return SJME_ERROR_NONE;
 988 }
 989
 990 static sjme_errorCode sjme_inflate_stepDynamicSetup(
 991         sjme_attrInNotNull sjme_inflate* inState)
 992 {
 993         sjme_errorCode error;
 994         sjme_jint i;
 995         sjme_juint rawCodeLen[SJME_INFLATE_NUM_CODE_LEN];
 996         sjme_juint rawLit[SJME_INFLATE_NUM_LIT_LENS];
 997         sjme_juint rawDist[SJME_INFLATE_NUM_DIST_LENS];
 998         sjme_juint hLit, hDist, hcLen, raw;
 999
1000         if (inState == NULL)
1001                 return SJME_ERROR_NULL_ARGUMENTS;
1002
1003         /* Read in literal count. */
1004         hLit = INT32_MAX;
1005         if (sjme_error_is(error = sjme_bitStream_inputRead(
1006                 inState->input, SJME_BITSTREAM_LSB,
1007                 &hLit, 5)) ||
1008                 hLit == INT32_MAX)
1009                 return sjme_error_default(error);
1010
1011         /* Read in distance count. */
1012         hDist = INT32_MAX;
1013         if (sjme_error_is(error = sjme_bitStream_inputRead(
1014                 inState->input, SJME_BITSTREAM_LSB,
1015                 &hDist, 5)) ||
1016                 hDist == INT32_MAX)
1017                 return sjme_error_default(error);
1018
1019         /* Read in code length count. */
1020         hcLen = INT32_MAX;
1021         if (sjme_error_is(error = sjme_bitStream_inputRead(
1022                 inState->input, SJME_BITSTREAM_LSB,
1023                 &hcLen, 4)) ||
1024                 hcLen == INT32_MAX)
1025                 return sjme_error_default(error);
1026
1027         /* Determine their actual values. */
1028         hLit += 257;
1029         hDist += 1;
1030         hcLen += 4;
1031
1032         /* Read in raw code lengths. */
1033         memset(rawCodeLen, 0, sizeof(rawCodeLen));
1034         for (i = 0; i < hcLen; i++)
1035         {
1036                 /* Read in raw code length. */
1037                 raw = INT32_MAX;
1038                 if (sjme_error_is(error = sjme_bitStream_inputRead(
1039                         inState->input, SJME_BITSTREAM_LSB,
1040                         &raw, 3)) || raw == INT32_MAX)
1041                         return sjme_error_default(error);
1042
1043                 /* Shuffle it in appropriately, the shuffle is "optimized" according */
1044                 /* to RFC1951 so the most importing bits are set first. */
1045                 rawCodeLen[sjme_inflate_shuffleBits[i]] = raw;
1046         }
1047
1048         /* Build code length tree. */
1049         if (sjme_error_is(error = sjme_inflate_dynamicBuildTree(
1050                 inState, &inState->treeCodeLen,
1051                 &rawCodeLen[0],
1052                 SJME_INFLATE_NUM_CODE_LEN,
1053                 SJME_INFLATE_NUM_CODE_LEN)))
1054                 return sjme_error_default(error);
1055
1056         /* Read literal values. */
1057         memset(rawLit, 0, sizeof(rawLit));
1058         for (i = 0; i < hLit;)
1059         {
1060                 /* Read in raw code. */
1061                 if (sjme_error_is(error = sjme_inflate_dynamicBuildReadCode(
1062                         inState, &rawLit[0], &i,
1063                         hLit, SJME_INFLATE_NUM_LIT_LENS)))
1064                         return sjme_error_default(error);
1065         }
1066
1067         /* Build literal tree. */
1068         if (sjme_error_is(error = sjme_inflate_dynamicBuildTree(
1069                 inState, &inState->treeLit,
1070                 &rawLit[0],
1071                 hLit,
1072                 SJME_INFLATE_NUM_LIT_LENS)))
1073                 return sjme_error_default(error);
1074
1075         /* Read distance values. */
1076         memset(rawDist, 0, sizeof(rawDist));
1077         for (i = 0; i < hDist;)
1078         {
1079                 /* Read in raw code. */
1080                 if (sjme_error_is(error = sjme_inflate_dynamicBuildReadCode(
1081                         inState, &rawDist[0], &i, hDist,
1082                         SJME_INFLATE_NUM_DIST_LENS)))
1083                         return sjme_error_default(error);
1084         }
1085
1086         /* Build Distance tree. */
1087         if (sjme_error_is(error = sjme_inflate_dynamicBuildTree(
1088                 inState, &inState->treeDist,
1089                 &rawDist[0],
1090                 hDist,
1091                 SJME_INFLATE_NUM_DIST_LENS)))
1092                 return sjme_error_default(error);
1093
1094         /* Set state for code reading. */
1095         memset(&inState->sub, 0, sizeof(inState->sub));
1096         inState->sub.huffman.readCode = sjme_inflate_dynamicReadCode;
1097         inState->sub.huffman.readDist = sjme_inflate_dynamicReadDist;
1098
1099         /* Move onto decompression stage. */
1100         inState->step = SJME_INFLATE_STEP_INFLATE_FROM_TREE;
1101         return SJME_ERROR_NONE;
1102 }
1103
1104 static sjme_errorCode sjme_inflate_stepFixedSetup(
1105         sjme_attrInNotNull sjme_inflate* inState)
1106 {
1107         if (inState == NULL)
1108                 return SJME_ERROR_NULL_ARGUMENTS;
1109
1110         /* Setup for new state, which is very simple. */
1111         memset(&inState->sub, 0, sizeof(inState->sub));
1112         inState->sub.huffman.readCode = sjme_inflate_fixedReadCode;
1113         inState->sub.huffman.readDist = sjme_inflate_fixedReadDist;
1114
1115         /* Move onto decompression stage. */
1116         inState->step = SJME_INFLATE_STEP_INFLATE_FROM_TREE;
1117         return SJME_ERROR_NONE;
1118 }
1119
1120 static sjme_errorCode sjme_inflate_stepInflateFromTree(
1121         sjme_attrInNotNull sjme_inflate* inState)
1122 {
1123         sjme_errorCode error;
1124         sjme_juint code, length, dist;
1125
1126         if (inState == NULL)
1127                 return SJME_ERROR_NULL_ARGUMENTS;
1128
1129         /* Continual code reading loop, provided not saturated. */
1130         for (;;)
1131         {
1132                 /* Read in next code. */
1133                 code = INT32_MAX;
1134                 if (sjme_error_is(error = inState->sub.huffman.readCode(inState,
1135                         &code)) || code == INT32_MAX)
1136                         return sjme_error_default(error);
1137
1138                 /* Invalid. */
1139                 if (code > 285)
1140                         return SJME_ERROR_INFLATE_INVALID_CODE;
1141
1142                 /* Stop decompression. */
1143                 else if (code == 256)
1144                 {
1145                         /* Read the next block type. */
1146                         inState->step = SJME_INFLATE_STEP_CHECK_BTYPE;
1147                         break;
1148                 }
1149
1150                 /* Literal byte value. */
1151                 else if (code >= 0 && code <= 255)
1152                 {
1153                         /* Standard write. */
1154                         if (sjme_error_is(error = sjme_bitStream_outputWrite(
1155                                 inState->output, SJME_BITSTREAM_LSB,
1156                                 code, 8)))
1157                                 return sjme_error_default(error);
1158
1159                         continue;
1160                 }
1161
1162                 /* Read the length value, which is based on the code and may */
1163                 /* read in more values. */
1164                 length = INT32_MAX;
1165                 if (sjme_error_is(error = sjme_inflate_readLength(inState,
1166                         code, &length)) ||
1167                         length == INT32_MAX)
1168                         return sjme_error_default(error);
1169
1170                 /* Read in the distance. */
1171                 dist = INT32_MAX;
1172                 if (sjme_error_is(error = sjme_inflate_readDistance(inState,
1173                         &dist)) || dist == INT32_MAX)
1174                         return sjme_error_default(error);
1175
1176                 /* Copy from the window. */
1177                 if (sjme_error_is(error = sjme_inflate_copyWindow(
1178                         inState, (sjme_jint)length, (sjme_jint)dist)))
1179                         return sjme_error_default(error);
1180         }
1181
1182         /* Success! */
1183         return SJME_ERROR_NONE;
1184 }
1185
1186 sjme_errorCode sjme_inflate_destroy(
1187         sjme_attrInNotNull sjme_inflate* inState)
1188 {
1189         sjme_errorCode error;
1190
1191         if (inState == NULL)
1192                 return SJME_ERROR_NULL_ARGUMENTS;
1193
1194         /* Close the input bit stream. */
1195         if (inState->input != NULL)
1196         {
1197                 if (sjme_error_is(error = sjme_closeable_close(
1198                         SJME_AS_CLOSEABLE(inState->input))))
1199                         return sjme_error_default(error);
1200
1201                 inState->input = NULL;
1202         }
1203
1204         /* Close the output bit stream. */
1205         if (inState->output != NULL)
1206         {
1207                 if (sjme_error_is(error = sjme_closeable_close(
1208                         SJME_AS_CLOSEABLE(inState->output))))
1209                         return sjme_error_default(error);
1210
1211                 inState->output = NULL;
1212         }
1213
1214         /* Close the source stream. */
1215         if (inState->source != NULL)
1216         {
1217                 if (sjme_error_is(error = sjme_closeable_close(
1218                         SJME_AS_CLOSEABLE(inState->source))))
1219                         return sjme_error_default(error);
1220
1221                 inState->source = NULL;
1222         }
1223
1224         /* Destroy the input buffer. */
1225         if (inState->inputBuffer != NULL)
1226         {
1227                 if (sjme_error_is(error = sjme_circleBuffer_destroy(
1228                         inState->inputBuffer)))
1229                         return sjme_error_default(error);
1230
1231                 inState->inputBuffer = NULL;
1232         }
1233
1234         /* Destroy the output buffer. */
1235         if (inState->outputBuffer != NULL)
1236         {
1237                 if (sjme_error_is(error = sjme_circleBuffer_destroy(
1238                         inState->outputBuffer)))
1239                         return sjme_error_default(error);
1240
1241                 inState->outputBuffer = NULL;
1242         }
1243
1244         /* Destroy the output window. */
1245         if (inState->window != NULL)
1246         {
1247                 if (sjme_error_is(error = sjme_circleBuffer_destroy(
1248                         inState->window)))
1249                         return sjme_error_default(error);
1250
1251                 inState->window = NULL;
1252         }
1253
1254         /* Destroy code length tree. */
1255         if (inState->treeCodeLen != NULL)
1256         {
1257                 if (sjme_error_is(error = sjme_traverse_destroy(
1258                         SJME_AS_TRAVERSE(inState->treeCodeLen))))
1259                         return sjme_error_default(error);
1260
1261                 inState->treeCodeLen = NULL;
1262         }
1263
1264         /* Destroy literal tree. */
1265         if (inState->treeLit != NULL)
1266         {
1267                 if (sjme_error_is(error = sjme_traverse_destroy(
1268                         SJME_AS_TRAVERSE(inState->treeLit))))
1269                         return sjme_error_default(error);
1270
1271                 inState->treeLit = NULL;
1272         }
1273
1274         /* Destroy distance tree. */
1275         if (inState->treeDist != NULL)
1276         {
1277                 if (sjme_error_is(error = sjme_traverse_destroy(
1278                         SJME_AS_TRAVERSE(inState->treeDist))))
1279                         return sjme_error_default(error);
1280
1281                 inState->treeDist = NULL;
1282         }
1283
1284         /* Free self. */
1285         sjme_alloc_free(inState);
1286
1287         /* Success! */
1288         return SJME_ERROR_NONE;
1289 }
1290
1291 sjme_errorCode sjme_inflate_inflate(
1292         sjme_attrInNotNull sjme_inflate* inState,
1293         sjme_attrOutNotNull sjme_jint* readCount,
1294         sjme_attrOutNotNullBuf(length) sjme_buffer outBuf,
1295         sjme_attrInPositiveNonZero sjme_jint length)
1296 {
1297         sjme_errorCode error;
1298         sjme_jint drainOff;
1299
1300         if (inState == NULL || readCount == NULL || outBuf == NULL)
1301                 return SJME_ERROR_NULL_ARGUMENTS;
1302
1303         if (length <= 0)
1304                 return SJME_ERROR_INDEX_OUT_OF_BOUNDS;
1305
1306         /* If this previously failed, then recover it. */
1307         if (sjme_error_is(inState->failed))
1308                 return sjme_error_default(inState->failed);
1309
1310         /* Constant inflation loop. */
1311         drainOff = 0;
1312         for (;;)
1313         {
1314                 /* Can anything be drained? */
1315                 if (inState->outputBuffer->ready > 0)
1316                         if (sjme_error_is(error = sjme_inflate_drain(inState, &drainOff,
1317                                 outBuf, length)))
1318                         {
1319                                 inState->failed = error;
1320                                 return sjme_error_default(error);
1321                         }
1322
1323                 /* Did we actually finish? */
1324                 if (inState->step == SJME_INFLATE_STEP_CHECK_BTYPE &&
1325                         inState->finalHit)
1326                         inState->step = SJME_INFLATE_STEP_FINISHED;
1327
1328                 /* Finished? */
1329                 if (inState->step == SJME_INFLATE_STEP_FINISHED)
1330                 {
1331                         /* There is still data that can be read. */
1332                         if (drainOff != 0 || inState->outputBuffer->ready > 0)
1333                                 break;
1334
1335                         /* True EOF */
1336                         *readCount = -1;
1337                         return SJME_ERROR_NONE;
1338                 }
1339
1340                 /* Fill in the input buffer as much as possible, this will */
1341                 /* reduce any subsequent disk activity as it is done in bulk. */
1342                 if (sjme_error_is(error = sjme_inflate_bitFill(inState)))
1343                 {
1344                         inState->failed = error;
1345                         return sjme_error_default(error);
1346                 }
1347
1348                 /* Check the ready state, stop if not yet ready */
1349                 if (sjme_error_is(error = sjme_inflate_bufferSaturation(inState,
1350                         1)))
1351                 {
1352                         if (error == SJME_ERROR_TOO_SHORT)
1353                                 continue;
1354
1355                         if (error == SJME_ERROR_BUFFER_SATURATED)
1356                                 break;
1357
1358                         inState->failed = error;
1359                         return sjme_error_default(error);
1360                 }
1361
1362                 /* Which step at inflation are we at? */
1363                 error = SJME_ERROR_UNKNOWN;
1364                 switch (inState->step)
1365                 {
1366                         case SJME_INFLATE_STEP_CHECK_BTYPE:
1367                                 error = sjme_inflate_stepBType(inState);
1368                                 break;
1369
1370                         case SJME_INFLATE_STEP_LITERAL_DATA:
1371                                 error = sjme_inflate_stepLiteralData(inState);
1372                                 break;
1373
1374                         case SJME_INFLATE_STEP_LITERAL_SETUP:
1375                                 error = sjme_inflate_stepLiteralSetup(inState);
1376                                 break;
1377
1378                         case SJME_INFLATE_STEP_DYNAMIC_SETUP:
1379                                 error = sjme_inflate_stepDynamicSetup(inState);
1380                                 break;
1381
1382                         case SJME_INFLATE_STEP_FIXED_SETUP:
1383                                 error = sjme_inflate_stepFixedSetup(inState);
1384                                 break;
1385
1386                         case SJME_INFLATE_STEP_INFLATE_FROM_TREE:
1387                                 error = sjme_inflate_stepInflateFromTree(inState);
1388                                 break;
1389                 }
1390
1391                 /* Did inflation fail? */
1392                 if (sjme_error_is(error))
1393                 {
1394                         /* Not enough input data, need to fill more! */
1395                         if (error == SJME_ERROR_TOO_SHORT)
1396                                 continue;
1397
1398                         /* Or we filled the output buffer as much as possible and */
1399                         /* cannot fit anymore. */
1400                         if (error == SJME_ERROR_BUFFER_SATURATED)
1401                                 break;
1402
1403                         /* Set as failed. */
1404                         inState->failed = error;
1405                         return sjme_error_default(error);
1406                 }
1407         }
1408
1409         /* The amount written is the amount drained. */
1410         *readCount = drainOff;
1411         return SJME_ERROR_NONE;
1412 }
1413
1414 sjme_errorCode sjme_inflate_new(
1415         sjme_attrInNotNull sjme_alloc_pool* inPool,
1416         sjme_attrInNotNull sjme_inflate** outState,
1417         sjme_attrInNotNull sjme_stream_input source)
1418 {
1419         sjme_errorCode error;
1420         sjme_inflate* result;
1421         sjme_circleBuffer* inputBuffer;
1422         sjme_circleBuffer* outputBuffer;
1423         sjme_circleBuffer* window;
1424         sjme_bitStream_input input;
1425         sjme_bitStream_output output;
1426
1427         if (inPool == NULL || outState == NULL || source == NULL)
1428                 return SJME_ERROR_NULL_ARGUMENTS;
1429
1430         /* Allocate resultant state. */
1431         result = NULL;
1432         if (sjme_error_is(error = sjme_alloc(inPool, sizeof(*result),
1433                 (sjme_pointer*)&result)) ||
1434                 result == NULL)
1435                 goto fail_allocResult;
1436
1437         /* Allocate the input buffer. */
1438         inputBuffer = NULL;
1439         if (sjme_error_is(error = sjme_circleBuffer_new(inPool,
1440                 &inputBuffer,
1441                 SJME_CIRCLE_BUFFER_QUEUE,
1442                 SJME_INFLATE_IO_BUFFER_SIZE)) || inputBuffer == NULL)
1443                 goto fail_allocInputBuffer;
1444
1445         /* Allocate the output buffer. */
1446         outputBuffer = NULL;
1447         if (sjme_error_is(error = sjme_circleBuffer_new(inPool,
1448                 &outputBuffer,
1449                 SJME_CIRCLE_BUFFER_QUEUE,
1450                 SJME_INFLATE_IO_BUFFER_SIZE)) || outputBuffer == NULL)
1451                 goto fail_allocOutputBuffer;
1452
1453         /* Allocate window. */
1454         window = NULL;
1455         if (sjme_error_is(error = sjme_circleBuffer_new(inPool,
1456                 &window,
1457                 SJME_CIRCLE_BUFFER_WINDOW,
1458                 SJME_INFLATE_WINDOW_SIZE)) || window == NULL)
1459                 goto fail_allocWindow;
1460
1461         /* Open input bit stream. */
1462         input = NULL;
1463         if (sjme_error_is(error = sjme_bitStream_inputOpen(inPool,
1464                 &input, sjme_inflate_bitRead,
1465                 result, NULL)) || input == NULL)
1466                 goto fail_openInput;
1467
1468         /* Open output bit stream. */
1469         output = NULL;
1470         if (sjme_error_is(error = sjme_bitStream_outputOpen(inPool,
1471                 &output, sjme_inflate_bitWrite,
1472                 result, NULL)) || output == NULL)
1473                 goto fail_openOutput;
1474
1475         /* Store everything in the result now. */
1476         result->inPool = inPool;
1477         result->failed = SJME_ERROR_NONE;
1478         result->source = source;
1479         result->input = input;
1480         result->inputBuffer = inputBuffer;
1481         result->output = output;
1482         result->outputBuffer = outputBuffer;
1483         result->window = window;
1484
1485         /* Since we hold onto the source, count it up. */
1486         if (sjme_error_is(error = sjme_alloc_weakRef(source, NULL)))
1487                 goto fail_countSource;
1488
1489         /* Along with the input... */
1490         if (sjme_error_is(error = sjme_alloc_weakRef(input, NULL)))
1491                 goto fail_countSource;
1492
1493         /* and output bit streams! */
1494         if (sjme_error_is(error = sjme_alloc_weakRef(output, NULL)))
1495                 goto fail_countSource;
1496
1497         /* Success! */
1498         *outState = result;
1499         return SJME_ERROR_NONE;
1500
1501 fail_countSource:
1502 fail_openOutput:
1503         if (output != NULL)
1504                 sjme_closeable_close(SJME_AS_CLOSEABLE(output));
1505 fail_openInput:
1506         if (input != NULL)
1507                 sjme_closeable_close(SJME_AS_CLOSEABLE(input));
1508 fail_allocWindow:
1509         if (window != NULL)
1510                 sjme_circleBuffer_destroy(window);
1511 fail_allocOutputBuffer:
1512         if (outputBuffer != NULL)
1513                 sjme_circleBuffer_destroy(outputBuffer);
1514 fail_allocInputBuffer:
1515         if (inputBuffer != NULL)
1516                 sjme_circleBuffer_destroy(inputBuffer);
1517 fail_allocResult:
1518         if (result != NULL)
1519                 sjme_alloc_free(result);
1520
1521         return sjme_error_default(error);
1522 }