Subversion Repositories ipe_artfile_utils

Rev

Blame | Last modification | View Log | RSS feed

  1. /**
  2.  * LZW Encoder 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_encoder.h"
  27.  
  28. #define INIT_BITS 9
  29. #define MAX_BITS 13           /* Do not exceed 14 with this program */
  30. #define HASHING_SHIFT (MAX_BITS - 8)
  31.  
  32. #if MAX_BITS == 14            /* Set the table size. Must be a prime    */
  33.   #define TABLE_SIZE 18041    /* number somewhat larger than 2^MAX_BITS.*/
  34. #elif MAX_BITS == 13
  35.   #define TABLE_SIZE 9029
  36. #else
  37.   #define TABLE_SIZE 5021
  38. #endif
  39.  
  40. #define CLEAR_TABLE 256    /* Code to flush the string table */
  41. #define TERMINATOR  257    /* To mark EOF Condition, instead of MAX_VALUE */
  42. #define FIRST_CODE  258    /* First available code for code_value table */
  43. #define CHECK_TIME  100    /* Check comp ratio every CHECK_TIME chars input */
  44.  
  45. #define MAXVAL(n) (( 1 <<( n )) -1)   /* max_value formula macro */
  46.  
  47. unsigned int find_match(Ipe32LZWEncoder *encoder, int hash_prefix, unsigned int hash_character) {
  48.         int index, offset;
  49.  
  50.         index = (hash_character << HASHING_SHIFT) ^ hash_prefix;
  51.  
  52.         offset = (index == 0) ? 1 : TABLE_SIZE - index;
  53.  
  54.         while (1) {
  55.                 if (encoder->code_value[index] == -1) {
  56.                         return(index);
  57.                 }
  58.                 if (encoder->prefix_code[index] == hash_prefix && encoder->append_character[index] == hash_character) {
  59.                         return(index);
  60.                 }
  61.                 index -= offset;
  62.                 if (index < 0) {
  63.                         index += TABLE_SIZE;
  64.                 }
  65.         }
  66. }
  67.  
  68. void output_code(Ipe32LZWEncoder *encoder, unsigned int code, unsigned char* outBuf, size_t* compressedPos) {
  69.         encoder->output_bit_buffer |= (uint32_t) code << (32 - encoder->num_bits - encoder->output_bit_count);
  70.         encoder->output_bit_count += encoder->num_bits;
  71.         while (encoder->output_bit_count >= 8) {
  72.                 outBuf[(*compressedPos)] = encoder->output_bit_buffer >> 24; // putc(output_bit_buffer >> 24, output);
  73.                 (*compressedPos)++;
  74.  
  75.                 encoder->output_bit_buffer <<= 8;
  76.                 encoder->output_bit_count -= 8;
  77.                 encoder->bytes_out++;
  78.         }
  79. }
  80.  
  81. void reset_output_buffer(Ipe32LZWEncoder *encoder) {
  82.         encoder->output_bit_count = 0;
  83.         encoder->output_bit_buffer = 0;
  84. }
  85.  
  86. void ipe32lzw_reset_encoder(Ipe32LZWEncoder *encoder) {
  87.         encoder->num_bits = INIT_BITS;
  88.         encoder->max_code = MAXVAL(encoder->num_bits);         /* Initialize max_value & max_code */
  89.         encoder->bytes_in = 0;
  90.         encoder->bytes_out = 0;
  91.         encoder->checkpoint = CHECK_TIME;
  92.  
  93.         // For some reason, the output buffer doesn't get correctly flushed when
  94.         // a new compression is started. So I made the static symbols global
  95.         // and clear them here.
  96.         reset_output_buffer(encoder);
  97. }
  98.  
  99. // Returns: Bytes written, or -1 if compression failed
  100. int ipe32lzw_encode(Ipe32LZWEncoder *encoder, unsigned char* compressedData, const size_t compressedBufLen, unsigned char* uncompressedData, const size_t uncompressedSize) {
  101.         unsigned int next_code=FIRST_CODE;
  102.         unsigned int index;
  103.         int i,                 /* All purpose integer */
  104.             ratio_new,         /* New compression ratio as a percentage */
  105.             ratio_old=100;     /* Original ratio at 100% */
  106.  
  107.         ipe32lzw_reset_encoder(encoder);
  108.  
  109.         for (i=0; i<TABLE_SIZE; ++i) {   /* Initialize the string table first */
  110.                 encoder->code_value[i]=-1;
  111.         }
  112.  
  113.         /* Get the first code */
  114.         if (compressedBufLen == 0) return -1;
  115.         unsigned int string_code = uncompressedData[0]; //string_code=getc(input);
  116.         size_t uncompressedPos = 1;
  117.         size_t compressedPos = 0;
  118.         #define OUTPUT(code) { if (compressedPos == compressedBufLen) return -1; output_code(encoder,code,compressedData,&compressedPos); }
  119.  
  120.         /* This is the main compression loop. Notice when the table is full we try
  121.          * to increment the code size. Only when num_bits == MAX_BITS and the code
  122.          * value table is full do we start to monitor the compression ratio.
  123.          */
  124.         while (uncompressedPos < uncompressedSize) { // while((character=getc(input)) != (unsigned)EOF) {
  125.                 unsigned int character = uncompressedData[uncompressedPos++];
  126.  
  127.                 ++encoder->bytes_in;
  128.                 index=find_match(encoder,string_code,character);
  129.                 if (encoder->code_value[index] != -1) {
  130.                         string_code=encoder->code_value[index];
  131.                 } else {
  132.                         if (next_code <= encoder->max_code) {
  133.                                 encoder->code_value[index]=next_code++;
  134.                                 encoder->prefix_code[index]=string_code;
  135.                                 encoder->append_character[index]=character;
  136.                         }
  137.                         OUTPUT(string_code);   /* Send out current code */
  138.                         string_code=character;
  139.                         if (next_code > encoder->max_code) {      /* Is table Full? */
  140.                                 if (encoder->num_bits < MAX_BITS) {     /* Any more bits? */
  141.                                         encoder->max_code = MAXVAL(++encoder->num_bits);  /* Increment code size then */
  142.                                 } else if (encoder->bytes_in > encoder->checkpoint) {         /* At checkpoint? */
  143.                                         if (encoder->num_bits == MAX_BITS) {
  144.                                                 ratio_new = encoder->bytes_out*100/encoder->bytes_in; /* New compression ratio */
  145.                                                 if (ratio_new > ratio_old) {        /* Has ratio degraded? */
  146.                                                         OUTPUT(CLEAR_TABLE); /* YES,flush string table */
  147.                                                         encoder->num_bits=INIT_BITS;
  148.                                                         next_code=FIRST_CODE;        /* Reset to FIRST_CODE */
  149.                                                         encoder->max_code = MAXVAL(encoder->num_bits); /* Re-Initialize this stuff */
  150.                                                         encoder->bytes_in = encoder->bytes_out = 0;
  151.                                                         ratio_old = 100;             /* Reset compression ratio */
  152.                                                         for (i=0; i<TABLE_SIZE; ++i) {  /* Reset code value array */
  153.                                                                 encoder->code_value[i]=-1;
  154.                                                         }
  155.                                                 } else {                                /* NO, then save new */
  156.                                                         ratio_old = ratio_new;          /* compression ratio */
  157.                                                 }
  158.                                         }
  159.                                         encoder->checkpoint = encoder->bytes_in + CHECK_TIME;  /* Set new checkpoint */
  160.                                 }
  161.                         }
  162.                 }
  163.         }
  164.         OUTPUT(string_code);   /* Output the last code */
  165.         if (next_code == encoder->max_code) {       /* Handles special case for bit */
  166.                 ++encoder->num_bits;                /* increment on EOF */
  167.         }
  168.         OUTPUT(TERMINATOR);    /* Output the end of buffer code */
  169.         OUTPUT(0);             /* Flush the output buffer */
  170.         OUTPUT(0);
  171.         OUTPUT(0);
  172.  
  173.         return compressedPos;
  174. }
  175.  
  176. void ipe32lzw_init_encoder(Ipe32LZWEncoder *encoder) {
  177.         /* The three buffers for the compression phase. */
  178.         encoder->code_value=malloc(TABLE_SIZE*sizeof(unsigned int));
  179.         encoder->prefix_code=malloc(TABLE_SIZE*sizeof(unsigned int));
  180.         encoder->append_character=malloc(TABLE_SIZE*sizeof(unsigned char));
  181.         ipe32lzw_reset_encoder(encoder);
  182. }
  183.  
  184. void ipe32lzw_free_encoder(Ipe32LZWEncoder *encoder) {
  185.         free(encoder->code_value);                    /* Needed only for compression */
  186.         free(encoder->prefix_code);
  187.         free(encoder->append_character);
  188. }
  189.  
  190. Ipe32LZWEncoder* new_ipe32lzw_encoder(void) {
  191.         return (Ipe32LZWEncoder*)app_zero_alloc(sizeof(Ipe32LZWEncoder));
  192. }
  193.