Login | ViewVC Help
View File | Revision Log | Show Annotations | Download File | View Changeset | Root Listing
root/ipe_artfile_utils/trunk/ipe32_lzw_encoder.c
Revision: 2
Committed: Thu Nov 8 11:19:36 2018 UTC (16 months, 2 weeks ago) by daniel-marschall
Content type: text/x-csrc
File size: 7541 byte(s)
Log Message:
Initial release to SVN

File Contents

# Content
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 }

Properties

Name Value
svn:mime-type text/x-csrc