Subversion Repositories ipe_artfile_utils

Rev

Blame | Last modification | View Log | RSS feed

  1. /**
  2.  * LZW Decoder for Imagination Pilots Entertainment 32-bit games (IPE32)
  3.  * - Where's Waldo? Exploring Geography
  4.  * - Eraser Turnabout by Imagination Pilots
  5.  * - Virtual K'Nex by Imagination Pilots
  6.  * ART file packer and unpacker by Daniel Marschall, ViaThinkSoft (C) 2018
  7.  * Revision: 2018-02-15
  8.  *
  9.  * Based on  : Basic LZW Data Compression program published in DDJ October 1989 issue.
  10.  *             by Mark R. Nelson
  11.  *             http://collaboration.cmc.ec.gc.ca/science/rpn/biblio/ddj/Website/articles/DDJ/1989/8910/8910b/8910b.htm
  12.  * Updated by: Shawn M. Regan, January 1990
  13.  *             http://mirror.bagelwood.com/textfiles/computers/regan.lst
  14.  * Updated by: Daniel Marschall, 11 February 2018
  15.  *             https://misc.daniel-marschall.de/code/c/lzw.c
  16.  * Changed for IPE32: - Simplified
  17.  *                    - Thread safe
  18.  *                    - MAX_BITS = 13
  19.  **/
  20.  
  21. #include <stdio.h>
  22. #include <stdlib.h>
  23. #include <stdint.h>
  24.  
  25. #include "utils.h"
  26. #include "ipe32_lzw_decoder.h"
  27.  
  28. #define INIT_BITS 9
  29. #define MAX_BITS 13           /* Do not exceed 14 with this program */
  30.  
  31. #if MAX_BITS == 14            /* Set the table size. Must be a prime    */
  32.   #define TABLE_SIZE 18041    /* number somewhat larger than 2^MAX_BITS.*/
  33. #elif MAX_BITS == 13
  34.   #define TABLE_SIZE 9029
  35. #else
  36.   #define TABLE_SIZE 5021
  37. #endif
  38.  
  39. #define CLEAR_TABLE 256    /* Code to flush the string table */
  40. #define TERMINATOR  257    /* To mark EOF Condition, instead of MAX_VALUE */
  41. #define FIRST_CODE  258    /* First available code for code_value table */
  42.  
  43. #define MAXVAL(n) (( 1 <<( n )) -1)   /* max_value formula macro */
  44.  
  45. unsigned char* decode_string(Ipe32LZWDecoder *decoder, unsigned char *buffer, unsigned int code) {
  46.         int i=0;
  47.  
  48.         while (code > 255) {
  49.                 *buffer++ = decoder->append_character[code];
  50.                 code = decoder->prefix_code[code];
  51.                 if (i++ >= 4000) {
  52.                         // printf("Error during code expansion\n");
  53.                         return NULL;
  54.                 }
  55.         }
  56.         *buffer=code;
  57.         return(buffer);
  58. }
  59.  
  60. unsigned input_code(Ipe32LZWDecoder *decoder, unsigned char* lzwInputBuffer, int* inputBufferPos) {
  61.         unsigned int return_value;
  62.  
  63.         while (decoder->input_bit_count <= 24) {
  64.                 decoder->input_bit_buffer |= lzwInputBuffer[(*inputBufferPos)] << (24 - decoder->input_bit_count);
  65.                 (*inputBufferPos)++;
  66.                 decoder->input_bit_count += 8;
  67.         }
  68.         return_value=decoder->input_bit_buffer >> (32-decoder->num_bits);
  69.         decoder->input_bit_buffer <<= decoder->num_bits;
  70.         decoder->input_bit_count -= decoder->num_bits;
  71.         return(return_value);
  72. }
  73.  
  74. void reset_input_buffer(Ipe32LZWDecoder *decoder) {
  75.         decoder->input_bit_count = 0;
  76.         decoder->input_bit_buffer = 0;
  77. }
  78.  
  79. void ipe32lzw_reset_decoder(Ipe32LZWDecoder *decoder) {
  80.         decoder->num_bits = INIT_BITS;
  81.         decoder->max_code = MAXVAL(decoder->num_bits);         /* Initialize max_value & max_code */
  82.  
  83.         // Make sure the input buffer is correctly flushed
  84.         reset_input_buffer(decoder);
  85. }
  86.  
  87. void ipe32lzw_init_decoder(Ipe32LZWDecoder *decoder) {
  88.         decoder->prefix_code      = malloc(TABLE_SIZE*sizeof(unsigned int));
  89.         decoder->append_character = malloc(TABLE_SIZE*sizeof(unsigned char));
  90.         ipe32lzw_reset_decoder(decoder);
  91. }
  92.  
  93. // Returns: Bytes written or -1 when an error occurs
  94. int ipe32lzw_decode(Ipe32LZWDecoder *decoder, unsigned char* outputBuffer, const size_t outpufBufferSize, unsigned char* lzwInputBuffer, const size_t maxReadBytes) {
  95.         unsigned int next_code=FIRST_CODE;
  96.         unsigned int new_code;
  97.         unsigned int old_code;
  98.         int character;
  99.         int clear_flag=1;          /* Need to clear the code value array */
  100.         unsigned char *string;
  101.  
  102.         int inputBufferPos = 0;
  103.         int outputBufferPos = 0;
  104.         #define OUTPUT(code) { if (outputBufferPos == outpufBufferSize) return -1; outputBuffer[outputBufferPos++] = code; }
  105.  
  106.         ipe32lzw_reset_decoder(decoder);
  107.  
  108.         while (1) {
  109.                 if (inputBufferPos == maxReadBytes) return -1;
  110.                 if ((new_code=input_code(decoder, lzwInputBuffer, &inputBufferPos)) == TERMINATOR) break;
  111.  
  112.                 if (clear_flag) {            /* Initialize or Re-Initialize */
  113.                         clear_flag=0;
  114.                         old_code=new_code;   /* The next three lines have been moved */
  115.                         character=old_code;  /* from the original */
  116.                         OUTPUT(old_code);
  117.                         continue;
  118.                 }
  119.                 if (new_code == CLEAR_TABLE) {     /* Clear string table */
  120.                         clear_flag=1;
  121.                         decoder->num_bits=INIT_BITS;
  122.                         next_code=FIRST_CODE;
  123.                         decoder->max_code = MAXVAL(decoder->num_bits);
  124.                         continue;
  125.                 }
  126.                 if (new_code >= next_code) {       /* Check for string+char+string */
  127.                         *decoder->decode_stack=character;
  128.                         string = decode_string(decoder, decoder->decode_stack+1,old_code);
  129.                 } else {
  130.                         string = decode_string(decoder, decoder->decode_stack,new_code);
  131.                 }
  132.                 if (string == NULL) return -1;
  133.  
  134.                 character = *string;              /* Output decoded string in reverse */
  135.                 while (string >= decoder->decode_stack) {
  136.                         OUTPUT(*string--);
  137.                 }
  138.  
  139.                 if (next_code <= decoder->max_code) {      /* Add to string table if not full */
  140.                         decoder->prefix_code[next_code]=old_code;
  141.                         decoder->append_character[next_code++]=character;
  142.                         if (next_code == decoder->max_code && decoder->num_bits < MAX_BITS) {
  143.                                 decoder->max_code = MAXVAL(++decoder->num_bits);
  144.                         }
  145.                 }
  146.                 old_code=new_code;
  147.         }
  148.  
  149.         return outputBufferPos;
  150. }
  151.  
  152. void ipe32lzw_free_decoder(Ipe32LZWDecoder *decoder) {
  153.         free(decoder->prefix_code);
  154.         free(decoder->append_character);
  155. }
  156.  
  157. Ipe32LZWDecoder* new_ipe32lzw_decoder(void) {
  158.         return (Ipe32LZWDecoder*)app_zero_alloc(sizeof(Ipe32LZWDecoder));
  159. }
  160.