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