nanocoat/lib/base/inflateProcess.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/debug.h"
  14
  15 sjme_errorCode sjme_inflate_processCodes(
  16         sjme_attrInNotNull sjme_inflate_state* state)
  17 {
  18         sjme_errorCode error;
  19         sjme_inflate_buffer* inBuffer;
  20         sjme_inflate_buffer* outBuffer;
  21         sjme_inflate_window* window;
  22         sjme_juint code, windowReadLen, windowReadDist;
  23
  24         if (state == NULL)
  25                 return SJME_ERROR_NULL_ARGUMENTS;
  26
  27         /* This must be set!! */
  28         if (state->readCode == NULL ||
  29                 state->readDist == NULL)
  30                 return SJME_ERROR_ILLEGAL_STATE;
  31
  32         /* Read as much as possible until we hit saturation. */
  33         inBuffer = &state->input;
  34         outBuffer = &state->output;
  35         window = &state->window;
  36         while (outBuffer->ready < SJME_INFLATE_IO_BUFFER_SATURATED)
  37         {
  38                 /* Read in code. */
  39                 code = INT32_MAX;
  40                 if (sjme_error_is(error = state->readCode(state, &code)) ||
  41                         code == INT32_MAX)
  42                         return sjme_error_default(error);
  43
  44                 /* Stop decoding! */
  45                 if (code == 256)
  46                 {
  47                         /* Reset back to initial step. */
  48                         state->step = SJME_INFLATE_STEP_CHECK_BTYPE;
  49                         state->readCode = NULL;
  50
  51                         /* Success! */
  52                         return SJME_ERROR_NONE;
  53                 }
  54
  55                 /* Literal byte value. */
  56                 else if (code >= 0 && code <= 255)
  57                 {
  58                         if (sjme_error_is(error = sjme_inflate_bitOut(
  59                                 outBuffer,
  60                                 SJME_INFLATE_LSB, window,
  61                                 8, code)))
  62                                 return sjme_error_default(error);
  63                 }
  64
  65                 /* Window. */
  66                 else if (code >= 257 && code <= 285)
  67                 {
  68                         /* Read in window length. */
  69                         windowReadLen = INT32_MAX;
  70                         if (sjme_error_is(error = sjme_inflate_processLength(
  71                                 state, inBuffer, code, &windowReadLen)) ||
  72                                 windowReadLen == INT32_MAX)
  73                                 return sjme_error_default(error);
  74
  75                         /* Read in distance. */
  76                         windowReadDist = INT32_MAX;
  77                         if (sjme_error_is(error = sjme_inflate_processDistance(
  78                                 state, inBuffer, code, &windowReadDist)) ||
  79                                 windowReadDist == INT32_MAX)
  80                                 return sjme_error_default(error);
  81
  82                         /* Copy from the input window. */
  83                         if (sjme_error_is(error = sjme_inflate_processWindow(
  84                                 state, outBuffer, window,
  85                                 windowReadDist, windowReadLen)))
  86                                 return sjme_error_default(error);
  87                 }
  88
  89                 /* Invalid. */
  90                 else
  91                         return SJME_ERROR_INFLATE_INVALID_CODE;
  92
  93                 /* Debug. */
  94                 sjme_message("Code: %d 0x%x", code, code);
  95                 sjme_message_hexDump(&window->window[0],
  96                         window->length);
  97         }
  98
  99         /* If we over-saturated, just stop and give all the data. */
 100         if (outBuffer->ready >= SJME_INFLATE_IO_BUFFER_SATURATED)
 101                 return SJME_ERROR_BUFFER_SATURATED;
 102         return SJME_ERROR_NONE;
 103 }
 104
 105 sjme_errorCode sjme_inflate_processDistance(
 106         sjme_attrInNotNull sjme_inflate_state* state,
 107         sjme_attrInNotNull sjme_inflate_buffer* inBuffer,
 108         sjme_attrInRange(257, 285) sjme_juint origCode,
 109         sjme_attrOutNotNull sjme_juint* outDist)
 110 {
 111         sjme_errorCode error;
 112         sjme_juint base, result, i, readIn;
 113
 114         if (state == NULL || inBuffer == NULL || outDist == NULL)
 115                 return SJME_ERROR_NULL_ARGUMENTS;
 116
 117         /* Read in distance code. */
 118         base = INT32_MAX;
 119         if (sjme_error_is(error = state->readDist(
 120                 state, &base)) || base == INT32_MAX)
 121                 return sjme_error_default(error);
 122
 123         /* Must be too high of a code! */
 124         if (base > 29)
 125                 return SJME_ERROR_INFLATE_INVALID_CODE;
 126
 127         /* Calculate the required distance to use */
 128         result = 1;
 129         for (i = 0; i < base; i++)
 130         {
 131                 /* Similar to length but in groups of two. */
 132                 if (i >= 2)
 133                         result += 1;
 134                 else
 135                         result += (1 << ((((i / 2)) - 1)));
 136         }
 137
 138         /* Also any extra bits needed as part of the distance. */
 139         if (base >= 4)
 140         {
 141                 /* Similarly the same as length, just smaller parts. */
 142                 i = ((base / 2)) - 1;
 143
 144                 /* Read in given bits. */
 145                 readIn = INT32_MAX;
 146                 if (sjme_error_is(error = sjme_inflate_bitIn(
 147                         inBuffer,
 148                         SJME_INFLATE_LSB, SJME_INFLATE_POP,
 149                         i, &readIn)) ||
 150                         readIn == INT32_MAX)
 151                         return sjme_error_default(error);
 152
 153                 /* Add in extra value. */
 154                 result += readIn;
 155         }
 156
 157         /* Give the result. */
 158         *outDist = result;
 159         return SJME_ERROR_NONE;
 160 }
 161
 162 sjme_errorCode sjme_inflate_processLength(
 163         sjme_attrInNotNull sjme_inflate_state* state,
 164         sjme_attrInNotNull sjme_inflate_buffer* inBuffer,
 165         sjme_attrInRange(257, 285) sjme_juint code,
 166         sjme_attrOutNotNull sjme_juint* outLength)
 167 {
 168         sjme_errorCode error;
 169         sjme_juint base, result, i, readIn;
 170
 171         if (state == NULL || inBuffer == NULL || outLength == NULL)
 172                 return SJME_ERROR_NULL_ARGUMENTS;
 173
 174         if (code < 257 || code > 285)
 175                 return SJME_ERROR_INFLATE_INVALID_CODE;
 176
 177         /* Maximum distance possible? */
 178         if (code == 285)
 179         {
 180                 *outLength = 258;
 181                 return SJME_ERROR_NONE;
 182         }
 183
 184         /* Get the base distance code. */
 185         base = code - 257;
 186
 187         /* Calculate the required length to use */
 188         result = 3;
 189         for (i = 0; i < base; i++)
 190         {
 191                 /* Determine how many groups of 4 the code is long. Since zero */
 192                 /* appears as items then subtract 1 to make it longer. However */
 193                 /* after the first 8 it goes up in a standard pattern. */
 194                 if (i < 8)
 195                         result += 1;
 196                 else
 197                         result += (1 << ((((i / 4)) - 1)));
 198         }
 199
 200         /* Also any extra bits needed as part of the length. */
 201         if (base >= 8)
 202         {
 203                 /* Calculate needed amount. Same as the length, it goes up in */
 204                 /* a specific pattern as well except without single increments. */
 205                 i = ((base / 4)) - 1;
 206
 207                 /* Read in given bits. */
 208                 readIn = INT32_MAX;
 209                 if (sjme_error_is(error = sjme_inflate_bitIn(
 210                         inBuffer,
 211                         SJME_INFLATE_LSB, SJME_INFLATE_POP,
 212                         i, &readIn)) ||
 213                         readIn == INT32_MAX)
 214                         return sjme_error_default(error);
 215
 216                 /* Add in extra value. */
 217                 result += readIn;
 218         }
 219
 220         /* Give the result. */
 221         *outLength = result;
 222         return SJME_ERROR_NONE;
 223 }
 224
 225 sjme_errorCode sjme_inflate_processWindow(
 226         sjme_attrInNotNull sjme_inflate_state* state,
 227         sjme_attrInNotNull sjme_inflate_buffer* outBuffer,
 228         sjme_attrInNotNull sjme_inflate_window* window,
 229         sjme_attrInPositive sjme_juint windowDist,
 230         sjme_attrInPositive sjme_juint windowLen)
 231 {
 232         sjme_errorCode error;
 233         sjme_juint maxLen, i, w, readBase;
 234         sjme_jubyte* chunk;
 235
 236         if (state == NULL || outBuffer == NULL || window == NULL)
 237                 return SJME_ERROR_NULL_ARGUMENTS;
 238
 239         /* The length chunk can never exceed the distance, however it does */
 240         /* wrap around accordingly. */
 241         maxLen = (windowLen > windowDist ? windowDist : windowLen);
 242
 243         sjme_message("Dist %d > %d", windowDist, window->length);
 244
 245         /* Cannot read more than what there is. */
 246         if (windowDist > window->length)
 247                 return SJME_ERROR_INFLATE_DISTANCE_OUT_OF_RANGE;
 248
 249         /* Setup buffer for the sliding window chunk. */
 250         chunk = sjme_alloca(sizeof(*chunk) * maxLen);
 251         if (chunk == NULL)
 252                 return SJME_ERROR_OUT_OF_MEMORY;
 253         memset(chunk, 0, sizeof(*chunk) * maxLen);
 254
 255         /* Can read in one full slice? */
 256         readBase = (window->end - windowDist) & SJME_INFLATE_WINDOW_MASK;
 257         if (readBase < window->end)
 258                 memmove(chunk, &window->window[readBase], maxLen);
 259
 260         /* Need to copy in two slices. */
 261         else
 262         {
 263                 i = SJME_INFLATE_WINDOW_SIZE - readBase;
 264                 memmove(&chunk[0], &window->window[readBase], i);
 265                 memmove(&chunk[i], &window->window[0], maxLen - i);
 266         }
 267
 268         /* Debug. */
 269         sjme_message("Dist chunk: %d", maxLen);
 270         sjme_message_hexDump(chunk, maxLen);
 271
 272         /* Write output. */
 273         for (i = 0, w = 0; i < windowLen; i++)
 274         {
 275                 /* Write value to the output. */
 276                 if (sjme_error_is(error = sjme_inflate_bitOut(
 277                         outBuffer, SJME_INFLATE_LSB, window,
 278                         8, chunk[w] & 0xFF)))
 279                         return sjme_error_default(error);
 280
 281                 /* Move window up, handle wrap around. */
 282                 if ((++w) >= maxLen)
 283                         w = 0;
 284         }
 285
 286         /* Success! */
 287         return SJME_ERROR_NONE;
 288 }
 289
 290
 291 sjme_errorCode sjme_inflate_readCodeDynamic(
 292         sjme_attrInNotNull sjme_inflate_state* state,
 293         sjme_attrOutNotNull sjme_juint* outCode)
 294 {
 295         if (state == NULL || outCode == NULL)
 296                 return SJME_ERROR_NULL_ARGUMENTS;
 297
 298         sjme_todo("Impl?");
 299         return sjme_error_notImplemented(0);
 300 }
 301
 302 sjme_errorCode sjme_inflate_readDistDynamic(
 303         sjme_attrInNotNull sjme_inflate_state* state,
 304         sjme_attrOutNotNull sjme_juint* outDist)
 305 {
 306         if (state == NULL || outDist == NULL)
 307                 return SJME_ERROR_NULL_ARGUMENTS;
 308
 309         sjme_todo("Impl?");
 310         return sjme_error_notImplemented(0);
 311 }
 312
 313 sjme_errorCode sjme_inflate_readCodeFixed(
 314         sjme_attrInNotNull sjme_inflate_state* state,
 315         sjme_attrOutNotNull sjme_juint* outCode)
 316 {
 317         sjme_errorCode error;
 318         sjme_inflate_buffer* inBuffer;
 319         sjme_juint hiSeven, bitsNeeded, litBase, litSub, raw;
 320
 321         if (state == NULL || outCode == NULL)
 322                 return SJME_ERROR_NULL_ARGUMENTS;
 323
 324         /* We at least need 7 bits for the minimum code length. */
 325         inBuffer = &state->input;
 326         if (sjme_error_is(error = sjme_inflate_bitNeed(inBuffer,
 327                 7)))
 328                 return sjme_error_default(error);
 329
 330         /* Read in upper 7 bits first, as a peek. */
 331         hiSeven = INT32_MAX;
 332         if (sjme_error_is(error = sjme_inflate_bitIn(inBuffer,
 333                 SJME_INFLATE_MSB, SJME_INFLATE_PEEK, 7,
 334                 &hiSeven)) || hiSeven == INT32_MAX)
 335                 return sjme_error_default(error);
 336
 337         /* Determine the actual number of bits we need. */
 338         /* 0b0000000 - 0b0010111 */
 339         if (hiSeven >= 0 && hiSeven <= 23)
 340         {
 341                 bitsNeeded = 7;
 342                 litBase = 256;
 343                 litSub = 0;
 344         }
 345
 346         /* 0b0011000[0] - 0b1011111[1] */
 347         else if (hiSeven >= 24 && hiSeven <= 95)
 348         {
 349                 bitsNeeded = 8;
 350                 litBase = 0;
 351                 litSub = 48;
 352         }
 353
 354         /* 0b1100000[0] - 0b1100011[1] */
 355         else if (hiSeven >= 96 && hiSeven <= 99)
 356         {
 357                 bitsNeeded = 8;
 358                 litBase = 280;
 359                 litSub = 192;
 360         }
 361
 362         /* 0b1100100[00] - 0b1111111[11] */
 363         else
 364         {
 365                 bitsNeeded = 9;
 366                 litBase = 144;
 367                 litSub = 400;
 368         }
 369
 370         /* Now that we know what we need, make sure we have it. */
 371         if (sjme_error_is(error = sjme_inflate_bitNeed(inBuffer,
 372                 bitsNeeded)))
 373                 return sjme_error_default(error);
 374
 375         /* Pop everything off now, so we can recover the code. */
 376         raw = INT32_MAX;
 377         if (sjme_error_is(error = sjme_inflate_bitIn(inBuffer,
 378                 SJME_INFLATE_MSB, SJME_INFLATE_POP,
 379                 bitsNeeded,
 380                 &raw)) || raw == INT32_MAX)
 381                 return sjme_error_default(error);
 382
 383         /* Recover the code. */
 384         *outCode = litBase + (raw - litSub);
 385         return SJME_ERROR_NONE;
 386 }
 387
 388 sjme_errorCode sjme_inflate_readDistFixed(
 389         sjme_attrInNotNull sjme_inflate_state* state,
 390         sjme_attrOutNotNull sjme_juint* outDist)
 391 {
 392         if (state == NULL || outDist == NULL)
 393                 return SJME_ERROR_NULL_ARGUMENTS;
 394
 395         /* Just a basic bit read. */
 396         return sjme_inflate_bitIn(&state->input,
 397                 SJME_INFLATE_MSB, SJME_INFLATE_POP,
 398                 5, outDist);
 399 }