Noble Ape
The Central Directories of the Noble Ape Simulation.
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros
compress.c
Go to the documentation of this file.
1 /****************************************************************
2 
3  compress.c
4 
5  =============================================================
6 
7  Copyright 1996-2014 Tom Barbalet. All rights reserved.
8 
9  Permission is hereby granted, free of charge, to any person
10  obtaining a copy of this software and associated documentation
11  files (the "Software"), to deal in the Software without
12  restriction, including without limitation the rights to use,
13  copy, modify, merge, publish, distribute, sublicense, and/or
14  sell copies of the Software, and to permit persons to whom the
15  Software is furnished to do so, subject to the following
16  conditions:
17 
18  The above copyright notice and this permission notice shall be
19  included in all copies or substantial portions of the Software.
20 
21  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
22  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
23  OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
24  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
25  HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
26  WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
27  FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
28  OTHER DEALINGS IN THE SOFTWARE.
29 
30  This software and Noble Ape are a continuing work of Tom Barbalet,
31  begun on 13 June 1996. No apes or cats were harmed in the writing
32  of this software.
33 
34  ****************************************************************/
35 
36 /*
37 
38  This codes is based on a modified version of:
39 
40  **
41  ** Copyright (c) 1989 Mark R. Nelson
42  **
43  ** LZW data compression/expansion demonstration program.
44  **
45  ** April 13, 1989
46  **
47 
48  Now in the public domain.
49 
50  */
51 
52 #include "noble.h"
53 
54 #define BITS 16
55 #define HASHING_SHIFT (BITS-8)
56 #define MAX_VALUE ((1<<BITS)-1)
57 #define MAX_CODE (MAX_VALUE-1)
58 
59 #if BITS == 16
60 #define TABLE_SIZE 99991
61 #endif
62 #if BITS==14
63 #define TABLE_SIZE 18041
64 #endif
65 #if BITS==13
66 #define TABLE_SIZE 9029
67 #endif
68 #if BITS==12
69 #define TABLE_SIZE 5021
70 #endif
71 
72 n_c_int code_value[TABLE_SIZE]; /* This is code value array */
73 n_byte4 prefix_code[TABLE_SIZE]; /* This array holds the prefix codes */
74 n_byte append_character[TABLE_SIZE]; /* This array holds the appended chars */
75 
76 /*
77  ** This is the hashing routine. It tries to find a match for the prefix+char
78  ** string in the string table. If it finds it, the index is returned. If
79  ** the string is not found, the first available index in the string table is
80  ** returned instead.
81  */
82 static n_c_int find_match(n_byte4 hash_prefix, n_byte4 hash_character)
83 {
84  n_c_int offset;
85  n_c_int index=(hash_character<<HASHING_SHIFT) ^ hash_prefix;
86  if (index==0)
87  {
88  offset=1;
89  }
90  else
91  {
92  offset=TABLE_SIZE-index;
93  }
94  while (1)
95  {
96  if (code_value[index] == -1)
97  return index;
98 
99  if (prefix_code[index] == hash_prefix && append_character[index] == hash_character)
100  return index;
101 
102  index-=offset;
103  if (index<0)
104  {
105  index+=TABLE_SIZE;
106  }
107  }
108 }
109 
110 /*
111  ** This routine simply decodes a string from the string table, storing
112  ** it in buffer. The buffer can then be output in reverse order by
113  ** the expansion program.
114  */
115 static n_byte * decode_string(n_byte *buffer, n_byte4 code)
116 {
117  n_c_int i;
118  i=0;
119  while (code>255)
120  {
121  *buffer++=append_character[code];
122  code = prefix_code[code];
123  if (i++>4000)
124  {
125  (void)SHOW_ERROR("Fatal error during code expansion.\n");
126  }
127  }
128  *buffer = (n_byte)code;
129  return buffer;
130 }
131 /*
132  ** The following two routines are used to output variable negth
133  ** codes. They are written strivtly for clarity and are not
134  ** particularly efficent.
135  */
136 unsigned int input_code(n_file *input)
137 {
138  n_byte4 return_value;
139  static n_c_int input_bit_count=0;
140  static n_byte4 input_bit_buffer=0L;
141  while (input_bit_count<=24)
142  {
143  n_byte byte_character;
144  (void) io_read_bin(input, &byte_character);
145 
146  input_bit_buffer |= ((unsigned long) byte_character) << (24-input_bit_count);
147  input_bit_count+=8;
148  }
149  return_value = input_bit_buffer>>(32-BITS);
150  input_bit_buffer<<=BITS;
151  input_bit_count-=BITS;
152  return return_value;
153 }
154 
155 void output_code(n_file *output, n_byte4 code)
156 {
157  static n_c_int output_bit_count=0;
158  static n_byte4 output_bit_buffer=0L;
159  output_bit_buffer|=(n_byte4) code << (32-BITS-output_bit_count);
160  output_bit_count += BITS;
161  while (output_bit_count>=8)
162  {
163  /* putc(output_bit_buffer>>24,output);*/
164 
165  (void)io_file_write(output, output_bit_buffer>>24);
166 
167  output_bit_buffer<<=8;
168  output_bit_count-=8;
169  }
170 }
171 
172 /*
173  ** This is the compression routine. The code should be a fairly close
174  ** match to the algorithm accompanying the article.
175  */
176 void compress_compress(n_file *input,n_file *output)
177 {
178  n_byte4 next_code = 256; /* next available string code */
179  n_byte4 string_code;
180  n_byte4 index = 0;
181  n_byte byte_character;
182 
183  while(index<TABLE_SIZE) /* clear string table */
184  {
185  code_value[index++]=-1;
186  }
187 
188  (void)io_read_bin(input, &byte_character);
189 
190  string_code = byte_character; /* get the first code */
191  /*
192  ** This is the main loop where it all happens. This loop runs until all of
193  ** the input has been exhausted. Note that it stops adding codes to the
194  ** table after all of the possible codes have been defined.
195  */
196 
197  while (io_read_bin(input, &byte_character) != -1)
198  {
199  n_byte4 character = byte_character;
200 
201  index = find_match(string_code, character);
202 
203  if (code_value[index]!=-1)
204  {
205  string_code = code_value[index];
206  }
207  else
208  {
209  if (next_code<=MAX_CODE) {
210  code_value[index] = next_code++;
211  prefix_code[index] = string_code;
212  append_character[index] = (n_byte)character;
213  }
214  output_code(output,string_code);
215  string_code=character;
216  }
217  }
218  output_code(output,string_code);
219  output_code(output,MAX_VALUE);
220  output_code(output,0);
221 }
222 
223 /*
224  ** This is expansion routine. It takes an LZW format file, and expands
225  ** it to an output file. The code here should be a faitly close match to
226  ** the algorithm in the accompaning article.
227  */
228 void compress_expand(n_file *input,n_file *output)
229 {
230  n_byte4 next_code = 256;
231  n_byte4 new_code;
232  n_byte4 old_code=input_code(input);
233  n_c_int character=old_code;
234  n_byte *string;
235 
236  n_byte decode_stack[4000]; /* This array holds the decoded string */
237 
238 
239  (void)io_file_write(output, (n_byte)old_code);
240 
241  while ((new_code=input_code(input)) != (MAX_VALUE))
242  {
243 
244  /*
245  ** This code checks for the special STRING+CHARACTER+STRING+CHARACTER+STRING
246  ** case which generates an undefined code. It handles it by decoding
247  ** the last code, adding a single character to the end of the decode string.
248  */
249 
250  if (new_code >= next_code)
251  {
252  *decode_stack = (n_byte)character;
253  string = decode_string(decode_stack+1,old_code);
254  }
255  /*
256  ** Otherwise we do a straight decode of the new code.
257  */
258  else
259  {
260  string = decode_string(decode_stack, new_code);
261  }
262  character = *string;
263  while(string >= decode_stack)
264  {
265  (void)io_file_write(output, *string--);
266  }
267  if (next_code <= MAX_CODE)
268  {
269  prefix_code[next_code] = old_code;
270  append_character[next_code] = (n_byte)character;
271  next_code++;
272  }
273  old_code = new_code;
274  }
275 }