Login | ViewVC Help
View File | Revision Log | Show Annotations | Download File | View Changeset | Root Listing
root/ipe_artfile_utils/trunk/ipe32_lzw_decoder.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: 5512 byte(s)
Log Message:
Initial release to SVN

File Contents

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

Properties

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