Details | Last modification | View Log | RSS feed
| Rev | Author | Line No. | Line |
|---|---|---|---|
| 2 | daniel-mar | 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 | } |