Advanced Strategic Command
oldlzw.cpp
Go to the documentation of this file.
1 
9 /*
10  This file is part of Advanced Strategic Command; http://www.asc-hq.de
11  Copyright (C) 1994-2010 Martin Bickel and Marc Schellenberger
12 
13  This program is free software; you can redistribute it and/or modify
14  it under the terms of the GNU General Public License as published by
15  the Free Software Foundation; either version 2 of the License, or
16  (at your option) any later version.
17 
18  This program is distributed in the hope that it will be useful,
19  but WITHOUT ANY WARRANTY; without even the implied warranty of
20  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21  GNU General Public License for more details.
22 
23  You should have received a copy of the GNU General Public License
24  along with this program; see the file COPYING. If not, write to the
25  Free Software Foundation, Inc., 59 Temple Place, Suite 330,
26  Boston, MA 02111-1307 USA
27 */
28 
29 
30 
32 
33 
35 {
36  mode = none;
37  initread = 0;
38  initwrite = 0;
39  DecodeBufferSize = 0;
40  decodeBuffer = NULL;
41  rdictionary = NULL;
42  readcnt = 0;
43  wdictionary = NULL;
44 }
45 
46 
47 void tlzwstreamcompression :: LZWOut ( CodeType code )
48 {
49  writelzwdata ( &code, sizeof( CodeType )) ;
50 
51  LZWTotBytesOut += 2;
52  LZWCurrBytesOut += 2;
53 }
54 
55 
56 
57 
58 /* our hashing lookup function */
59  IndexType tlzwstreamcompression :: LZWFind ( CodeType currcode, int in )
60 {
61  IndexType ndx;
62  int step = 11, pastzero = 0;
63 
64  ndx = ( ( IndexType ) currcode << 8 ) | in;
65  ndx = ndx % DICTIONARY_SIZE;
66 
67  for ( ;; )
68  {
69  if ( wdictionary[ ndx ].code == UNUSED_CODE )
70  break;
71  if ( wdictionary[ ndx ].parent == currcode &&
72  wdictionary[ ndx ].c == in )
73  break;
74  ndx += step;
75  if ( ndx >= DICTIONARY_SIZE)
76  {
77  ndx -= DICTIONARY_SIZE;
78  pastzero += 1;
79 
80  /*
81  * Next is a safety check. If the step
82  * value and the dictionary size are
83  * relatively prime, there should never
84  * be a problem. However, let's not loop
85  * too many times.
86  */
87 
88  if ( pastzero > 5 )
89  step = 1;
90  }
91 
92  }
93  return ( ndx );
94 }
95 
96 
97  void tlzwstreamcompression :: initreading ( void )
98 {
99  if ( mode == none ) { // 1: read, 2: write
100  char tempreadbuf[10];
101  int tempreadbufsize = 0;
102 
103  int lzw = 1;
104  int i;
105 
106  for (i = 0; i < strlen ( LZ_SIGNATURE ) + 3; i++) {
107  try {
108  readlzwdata ( &tempreadbuf[tempreadbufsize], 1 );
109  tempreadbufsize++;
110  } /* endtry */
111 
112  catch ( treadafterend ) {
113  tempreadbufsize--;
114  lzw = 0;
115  } /* endcatch */
116  }
117 
118  if ( lzw ) {
119  if ( tempreadbuf[0] )
120  lzw = 0;
121  if ( strcmp ( &tempreadbuf[1], LZ_SIGNATURE ) )
122  lzw = 0;
123  if ( tempreadbuf[strlen ( LZ_SIGNATURE ) + 2] )
124  lzw = 0;
125  }
126  if ( lzw == 1 ) {
127  mode = reading;
128 
129  rdictionary = new Rdictionary [DICTIONARY_SIZE];
130 
131  if ( rdictionary == NULL )
132  throw OutOfMemoryError ( DICTIONARY_SIZE * sizeof( struct Rdictionary ) );
133  } else {
134  lzw = 2;
135  if ( tempreadbuf[0] )
136  lzw = 0;
137  if ( strcmp ( &tempreadbuf[1], RLE_SIGNATURE ) )
138  lzw = 0;
139  if ( tempreadbuf[strlen ( RLE_SIGNATURE ) + 2] )
140  lzw = 0;
141 
142  if ( lzw == 2 ) {
143  rlestartbyte = tempreadbuf[strlen ( RLE_SIGNATURE ) + 3];
144 
145  rlenum = 0;
146  mode = readingrle;
147 
148  } else {
149  for ( i = 0; i < tempreadbufsize; i++ )
150  tempbuf.push ( tempreadbuf[i] );
151 
153  }
154  }
155  initread = 1;
156 
157  } else
158  if ( initwrite )
159  throw tinvalidmode ( "tlzwstreamcompression ", tnstream::IOMode ( mode ), tnstream::reading );
160 }
161 
162 
163 
164  void tlzwstreamcompression :: initwriting ( void )
165 {
166  if ( mode == none ) {
167 
168  freecode = STARTING_CODE;
169 
170  LZWTotBytesIn = 0;
171  LZWTotBytesOut = 0;
172  LZWCurrBytesIn = 0;
173  LZWCurrBytesOut = 0;
174 
175  Uint8 c = 0;
176  writelzwdata ( &c, 1 );
177  writelzwdata ( LZ_SIGNATURE, strlen ( LZ_SIGNATURE ) + 1 );
178  writelzwdata ( &c, 1 );
179 
180 
181  wdictionary = new Wdictionary [ DICTIONARY_SIZE ];
182 
183  if ( ! wdictionary )
184  throw OutOfMemoryError ( DICTIONARY_SIZE * sizeof( struct Wdictionary ) );
185 
186  for ( i = 0; i < DICTIONARY_SIZE; i++ )
187  wdictionary[ i ].code = UNUSED_CODE;
188 
189  currcodeloaded = 0;
190 
191  initwrite = 1;
192  mode = writing;
193 
194  } else
195  if ( initread )
196  throw tinvalidmode ( "tlzwstreamcompression ", tnstream::IOMode ( mode ) , tnstream::writing );
197 }
198 
199 
200 
201  void tlzwstreamcompression :: writedata ( const void* buf, int size )
202 {
203  if ( !initwrite )
204  initwriting();
205 
206  const char* buf2 = (char*) buf;
207  int pos = 0;
208 
209  if ( size ) {
210  if ( !currcodeloaded ) {
211  currcode = buf2[pos++];
212 
213  LZWTotBytesIn += 1;
214  LZWCurrBytesIn += 1;
215  currcode &= 0xFF; /* make sure we don't sign extend */
216 
217  currcodeloaded = 1;
218  }
219 
220  while ( pos < size )
221  {
222  in = buf2[pos++];
223 
224  LZWTotBytesIn += 1;
225  LZWCurrBytesIn += 1;
226  idx = LZWFind ( currcode, in );
227  if ( wdictionary[ idx ].code == UNUSED_CODE )
228  {
229  /* not a match */
230  LZWOut ( currcode );
231 
232  /* now, update the dictionary */
233  if ( freecode < MAX_CODE )
234  {
235  wdictionary[ idx ].c = in;
236  wdictionary[ idx ].code = freecode++;
237  wdictionary[ idx ].parent = currcode;
238  }
239  currcode = in;
240 
241  /* Had a miss; check compression efficiency */
242  if ( LZWCurrBytesIn >= 10000 )
243  {
244  unsigned ratio;
245  ratio = ( LZWCurrBytesOut * 100 ) /
246  LZWCurrBytesIn;
247 
248  LZWCurrBytesIn = 0;
249  LZWCurrBytesOut = 0;
250  if ( ratio > LZWBestRatio )
251  {
252  if ( ratio > 50 &&
253  ( ratio > 90 ||
254  ratio > LZWLastRatio + 10 ))
255  {
256  LZWOut ( NEW_DICTIONARY );
257  for ( i = 0;
258  i < DICTIONARY_SIZE; i++ )
259  wdictionary[ i ].code =
260  UNUSED_CODE;
261  freecode = STARTING_CODE;
262  }
263  }
264  else
265  LZWBestRatio = ratio;
266  LZWLastRatio = ratio;
267  }
268  }
269  else /* we match so far--keep going */
270  currcode = wdictionary[ idx ].code;
271 
272  }
273  }
274 }
275 
276 
277 
278  void tlzwstreamcompression :: LZWIn ( void )
279 {
280  readlzwdata ( &incode, sizeof( CodeType ) );
281  incode = SDL_SwapLE16( incode );
282 }
283 
284 
285 /* the active decompression routine */
286  unsigned tlzwstreamcompression :: LZWLoadBuffer ( unsigned count, CodeType code )
287 {
288  if ( code >= freecode )
289  throw tbufferoverflow();
290 
291  while ( code >= PRESET_CODE_MAX )
292  {
293  decodeBuffer[ count++ ] = rdictionary[ code ].c;
294  if ( count == DecodeBufferSize )
295  {
296  unsigned char* newBuffer = (unsigned char *) realloc ( decodeBuffer, DecodeBufferSize + 1000 );
297 
298  if ( ! newBuffer ) {
299  free ( decodeBuffer );
300  throw OutOfMemoryError ( DecodeBufferSize + 1000 );
301  } else {
302  decodeBuffer = newBuffer;
303  DecodeBufferSize += 1000;
304  }
305  }
306  code = rdictionary[ code ].parent;
307  }
308  decodeBuffer[ count++ ] = code;
309  return ( count );
310 }
311 
312 
313 
314 int tlzwstreamcompression :: readdata ( void* buf, int size, bool excpt )
315 {
316  if ( !initread )
317  initreading();
318 
319  int pos = 0;
320  char* buf2 = (char*) buf ;
321 
322 
323  if ( mode == readingdirect ) {
324  int tp = 0;
325  while ( pos < size && tempbuf.size() ) {
326  buf2 [pos++] = tempbuf.front();
327  tempbuf.pop();
328  tp++;
329  }
330  if ( size-pos > 0 )
331  tp += readlzwdata ( &buf2[pos], size-pos, excpt );
332 
333  return tp;
334 
335  } else
336 
337 
338 
339  if ( mode == readingrle ) {
340  while ( pos < size ) {
341 
342  if ( rlenum ) {
343  buf2[pos++] = rledata;
344  rlenum--;
345  } else {
346 
347  // getting byte
348 
349  if ( !readlzwdata ( &rledata, 1, excpt ))
350  return pos;
351 
352  if ( rledata == rlestartbyte ) {
353  readlzwdata ( &rlenum, 1 );
354  if ( rlenum > 2 )
355  readlzwdata ( &rledata, 1 );
356  } else
357  buf2[pos++] = rledata;
358  }
359 
360  } /* endwhile */
361  return pos;
362 
363  } else {
364 
365  while ( pos < size && tempbuf.size() ) {
366  buf2 [pos++] = tempbuf.front();
367  tempbuf.pop();
368  }
369 
370 
371  if ( pos < size ) {
372 
373  /* prime the pump */
374 
375  if (!DecodeBufferSize)
376  {
377  DecodeBufferSize = 1000;
378  decodeBuffer = (unsigned char * ) new char [ DecodeBufferSize ];
379  if ( decodeBuffer == NULL )
380  throw OutOfMemoryError ( DecodeBufferSize );
381  }
382 
383 
384  if ( !readcnt ) {
385 
386  priming:
387  freecode = STARTING_CODE;
388  LZWIn ( );
389 
390  if ( incode == END_OF_INPUT )
391  goto done;
392 
393  /* the first character always is itself */
394 
395  oldcode = incode;
396  inchar = incode;
397  buf2[ pos++ ] = incode;
398 
399  }
400 
401  while ( pos < size ) {
402  LZWIn ( );
403 
404  if ( incode == END_OF_INPUT )
405  break;
406 
407  if ( incode == NEW_DICTIONARY )
408  goto priming;
409 
410  if ( incode >= freecode )
411  {
412  /* We have a code that's not in our rdictionary! */
413  /* This can happen only one way--see text */
414 
415  count = LZWLoadBuffer ( 1, oldcode );
416 
417  /* Make last char same as first. Can use either */
418  /* inchar or the DecodeBuffer[count-1] */
419 
420  decodeBuffer[ 0 ] = inchar;
421  }
422  else
423  count = LZWLoadBuffer ( 0, incode );
424 
425  if ( count == 0 )
426  throw ASCexception();
427 
428  inchar = decodeBuffer[ count - 1 ];
429  while ( count )
430  {
431  if ( pos < size )
432  buf2 [pos++] = decodeBuffer[--count];
433  else
434  tempbuf.push ( decodeBuffer[--count] );
435  }
436 
437  /* now, update the rdictionary */
438  if ( freecode < MAX_CODE )
439  {
440  rdictionary[ freecode ].parent = oldcode;
441  rdictionary[ freecode ].c = inchar;
442  freecode += 1;
443 
444  }
445  oldcode = incode;
446  }
447  }
448  done:
449  readcnt++;
450 
451  return pos;
452  }
453 
454  // return 0;
455 }
456 
457 
459 {
460  if ( mode == writing ) {
461  LZWOut ( currcode );
462  LZWOut ( END_OF_INPUT );
463  mode = none;
464  }
465 }
466 
467 
469 {
470 
471  if ( rdictionary ) {
472  delete[] rdictionary;
473  rdictionary = NULL;
474  }
475  if ( wdictionary ) {
476  delete[] wdictionary;
477  wdictionary = NULL;
478  }
479 
480  if ( decodeBuffer ) {
481  delete[] decodeBuffer;
482  decodeBuffer = NULL;
483  }
484 
485 }
unsigned long IndexType
Definition: lzw.h:47
#define NEW_DICTIONARY
Definition: lzw.h:40
virtual int readlzwdata(void *buf, int size, bool excpt=true)=0
void writedata(const void *buf, int size)
Definition: oldlzw.cpp:201
virtual ~tlzwstreamcompression(void)
Definition: oldlzw.cpp:468
void close(void)
Definition: oldlzw.cpp:458
int readdata(void *buf, int size, bool excpt=true)
Definition: oldlzw.cpp:314
tlzwstreamcompression(void)
Definition: oldlzw.cpp:34
#define DICTIONARY_SIZE
Definition: lzw.h:44
unsigned short CodeType
Definition: lzw.h:46
#define MAX_CODE
Definition: lzw.h:43
#define UNUSED_CODE
Definition: lzw.h:41
virtual void writelzwdata(const void *buf, int size)=0
const char * RLE_SIGNATURE
Definition: basestrm.cpp:89
#define PRESET_CODE_MAX
Definition: lzw.h:38
const char * LZ_SIGNATURE
Definition: basestrm.cpp:88
#define STARTING_CODE
Definition: lzw.h:42
queue< Uint8, CDQ > tempbuf
Definition: basestrm.h:297
#define END_OF_INPUT
Definition: lzw.h:39
IOMode
the modes in which a stream can operate