source: gsdl/trunk/trunk/mg/src/images/ppm.c@ 16583

Last change on this file since 16583 was 16583, checked in by davidb, 16 years ago

Undoing change commited in r16582
  • Property svn:executable set to *
  • Property svn:keywords set to Author Date Id Revision
File size: 12.0 KB
Line 
1/**************************************************************************
2 *
3 * ppm.c -- PPM data compression
4 * Copyright (C) 1987 Alistair Moffat
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19 *
20 * $Id: ppm.c 16583 2008-07-29 10:20:36Z davidb $
21 *
22 **************************************************************************/
23
24#include "sysfuncs.h"
25
26#include "arithcode.h"
27#include "model.h"
28
29
30
31/*
32 $Log$
33 Revision 1.1 2003/02/20 21:16:56 mdewsnip
34 Addition of MG package for search and retrieval
35
36 Revision 1.1 1999/08/10 21:17:33 sjboddie
37 renamed mg-1.3d directory mg
38
39 Revision 1.1 1998/11/17 09:33:55 rjmcnab
40 *** empty log message ***
41
42 * Revision 1.2 1994/09/20 04:42:02 tes
43 * For version 1.1
44 *
45 */
46
47static char *RCSID = "$Id: ppm.c 16583 2008-07-29 10:20:36Z davidb $";
48
49/* FIXEDORDER sets the maximum context length that will be used.
50 Making FIXEDORDER large increases the compression if there is enough
51 space to store the model, but when space limit is reached increasing
52 FIXEDORDER will decrease compression because of model thrashing.
53 Third order (FIXEDORDER=3) is suitable for a few hundred Kb of model
54 space, FIXEDORDER=1 is suitable for a few tens of kB.
55 This version requires that FIXEDORDER be a preprocessor rather
56 than runtime variable to allow loops to be unrolled and make for faster
57 execution. Maximum in this implementation is 3 */
58
59#ifndef FIXEDORDER
60#define FIXEDORDER 3
61#endif
62
63/* global variables */
64eventptr E = NULL; /* array of eventnodes */
65point numnodes = 0, nfreenodes = 0;
66long kbytes = defaultkbytes;
67/*boolean excluded[nchars]={false}; - MAHE */
68boolean excluded[16384] =
69{false}; /* excluded characters */
70
71/* local variables */
72#define defaultchunksize 4096 /* compression chunks */
73
74#define EOSchar (charsetsize)
75
76unsigned chunksize = defaultchunksize;
77eventptr s[FIXEDORDER + 1] =
78{NULL}, /* current contexts */
79 t[FIXEDORDER + 1] =
80{NULL}; /* new contexts */
81
82#if (FIXEDORDER==3)
83#define SHIFT_ST s[1] = t[0]; s[2] = t[1] ; s[3] = t[2]
84#else
85#if (FIXEDORDER==2)
86#define SHIFT_ST s[1] = t[0]; s[2] = t[1]
87#else
88#if (FIXEDORDER==1)
89#define SHIFT_ST s[1] = t[0]
90#else
91#define SHIFT_ST
92#endif
93#endif
94#endif
95
96/* follow a character list and set the exclusions */
97#define SET_EX(p) \
98do \
99{ register eventptr q; \
100 q = p32((p32(p))->next); \
101 for (; q!=ENULL; q=p32(q->next)) \
102 excluded[q->eventnum] = true; \
103} \
104while (false)
105
106/* clear the exclusions */
107#define CLEAR_EX(p) \
108do \
109{ register eventptr q; \
110 q = p32((p32(p))->next); \
111 for (; q!=ENULL; q=p32(q->next)) \
112 excluded[q->eventnum] = false; \
113} \
114while (false)
115
116/*==================================*/
117
118void
119write_model ()
120{
121 fprintf (stderr, "ppm");
122 write_method ();
123#ifdef NOEXCLUSIONS
124 fprintf (stderr, "nx");
125#endif
126 fprintf (stderr, "-o%1d", FIXEDORDER);
127 fprintf (stderr, "-k%ld", kbytes);
128}
129
130/*==================================*/
131
132void
133encode_in_order (n, e)
134 int n;
135 event e;
136/* encode character e in order n */
137{
138 boolean encoded;
139 int i, c;
140 t[n] = encode_event_noex (&s[n]->foll, e, &encoded);
141 if (encoded)
142 c = n;
143 else
144 for (c = n - 1; c >= 0; c--)
145 {
146#ifdef NOEXCLUSIONS
147 t[c] = encode_event_noex (&s[c]->foll, e, &encoded);
148#else
149 SET_EX (s[c + 1]->foll.list);
150 t[c] = encode_event (&s[c]->foll, e, &encoded);
151#endif
152 if (encoded)
153 break;
154 }
155 if (!encoded)
156 arithmetic_encode (e, e + 1, nchars);
157 for (i = c + 1; i <= n; i++)
158 if (i > 0)
159 t[i]->prev = p16 (t[i - 1]);
160 else
161 t[0]->prev = p16 (s[0]);
162 for (i = c - 1; i >= 0; i--)
163 t[i] = p32 (t[i + 1]->prev);
164#ifndef NOEXCLUSIONS
165 if (c != n)
166 CLEAR_EX (s[c + 1]->foll.list);
167#endif
168 SHIFT_ST;
169}
170
171/*==================================*/
172
173/* not required in this version */
174
175#if 0
176
177void
178decode_in_order (n, e)
179 int n;
180 event *e;
181{
182 boolean decoded;
183 int i, c;
184 t[n] = decode_event_noex (&s[n]->foll, &decoded, e);
185 if (decoded)
186 c = n;
187 else
188 for (c = n - 1; c >= 0; c--)
189 {
190#ifdef NOEXCLUSIONS
191 t[c] = decode_event_noex (&s[c]->foll, &decoded, e);
192#else
193 SET_EX (s[c + 1]->foll.list);
194 t[c] = decode_event (&s[c]->foll, &decoded, e);
195#endif
196 if (decoded)
197 break;
198 }
199 if (!decoded)
200 {
201 *e = arithmetic_decode_target (nchars);
202 arithmetic_decode (*e, *e + 1, nchars);
203 }
204 for (i = c + 1; i <= n; i++)
205 {
206 t[i]->eventnum = *e;
207 if (i > 0)
208 t[i]->prev = p16 (t[i - 1]);
209 else
210 t[0]->prev = p16 (s[0]);
211 }
212 {
213 register int i;
214 for (i = c - 1; i >= 0; i--)
215 t[i] = p32 (t[i + 1]->prev);
216 }
217#ifndef NOEXCLUSIONS
218 if (c != n)
219 CLEAR_EX (s[c + 1]->foll.list);
220#endif
221 SHIFT_ST;
222}
223
224#endif
225
226/*==================================*/
227
228void
229start_model ()
230{
231 int i;
232 /* is this the first call? */
233 if (E == NULL)
234 E = (eventptr) malloc ((unsigned) kbytes * 1024);
235 /* start off with no information */
236 numnodes = 0;
237 nfreenodes = maxnodes;
238 for (i = 0; i <= FIXEDORDER; i++)
239 {
240 s[i] = newnode (NULL);
241 if (i > 0)
242 s[i]->prev = p16 (s[i - 1]);
243 }
244}
245
246/*==================================*/
247
248void
249encodestring (str, n)
250 unsigned short *str;
251 int n;
252/* encode all n characters of the supplied string str */
253{
254 event e;
255 boolean encoded;
256 register eventptr S, T;
257 int i;
258#ifndef NOEXCLUSIONS
259 register eventptr Sex;
260#endif
261
262 if (E == NULL)
263 start_model ();
264 /* set the initial context node */
265 S = s[FIXEDORDER];
266
267 for (i = 0; i < n; i++)
268 {
269 /* encode one character */
270 e = *str++;
271 /* this next monstrosity is logically equivalent to
272 encode_in_order(FIXEDORDER,e)
273 the loop has been unrolled to make it all go faster */
274 for (;;)
275 {
276 T = encode_event_noex (&S->foll, e, &encoded);
277 if (encoded)
278 break;
279 t[FIXEDORDER] = T;
280
281#ifdef NOEXCLUSIONS
282#if (FIXEDORDER>2)
283 S = p32 (S->prev);
284 t[2] = encode_event_noex (&S->foll, e, &encoded);
285 t[3]->prev = p16 (t[2]);
286 if (encoded)
287 break;
288#endif
289
290#if (FIXEDORDER>1)
291 S = p32 (S->prev);
292 t[1] = encode_event_noex (&S->foll, e, &encoded);
293 t[2]->prev = p16 (t[1]);
294 if (encoded)
295 break;
296#endif
297
298#if (FIXEDORDER>0)
299 S = p32 (S->prev);
300 t[0] = encode_event_noex (&S->foll, e, &encoded);
301 t[1]->prev = p16 (t[0]);
302 if (encoded)
303 break;
304#endif
305#else
306#if (FIXEDORDER>2)
307 Sex = S;
308 SET_EX (Sex->foll.list);
309 S = p32 (S->prev);
310 t[2] = encode_event (&S->foll, e, &encoded);
311 t[3]->prev = p16 (t[2]);
312 if (encoded)
313 {
314 CLEAR_EX (Sex->foll.list);
315 break;
316 }
317#endif
318
319#if (FIXEDORDER>1)
320 Sex = S;
321 SET_EX (Sex->foll.list);
322 S = p32 (S->prev);
323 t[1] = encode_event (&S->foll, e, &encoded);
324 t[2]->prev = p16 (t[1]);
325 if (encoded)
326 {
327 CLEAR_EX (Sex->foll.list);
328 break;
329 }
330#endif
331
332#if (FIXEDORDER>0)
333 Sex = S;
334 SET_EX (Sex->foll.list);
335 S = p32 (S->prev);
336 t[0] = encode_event (&S->foll, e, &encoded);
337 t[1]->prev = p16 (t[0]);
338 if (encoded)
339 {
340 CLEAR_EX (Sex->foll.list);
341 break;
342 }
343 CLEAR_EX (Sex->foll.list);
344#endif
345#endif
346
347 arithmetic_encode (e, e + 1, nchars);
348 t[0]->prev = p16 (s[0]);
349 break;
350 }
351 /* phew! Update the current context to the latest node */
352 S = p32 (T->prev);
353
354 /* is there a danger of running out of space? */
355 if (nfreenodes <= FIXEDORDER)
356 {
357 start_model ();
358 S = s[FIXEDORDER];
359 }
360 }
361
362 /* save the current contexts for the various order submodels */
363 s[FIXEDORDER] = S;
364 for (i = FIXEDORDER; i > 0; i--)
365 s[i - 1] = p32 (s[i]->prev);
366 /* and send the terminator character */
367 encode_in_order (FIXEDORDER, EOSchar);
368 /* and check the space again */
369 if (nfreenodes <= FIXEDORDER)
370 start_model ();
371}
372
373/*==================================*/
374
375void
376decodestring (str, n)
377 unsigned short *str;
378 int *n;
379{
380 event e;
381 boolean decoded;
382 register eventptr S, T;
383#ifndef NOEXCLUSIONS
384 register eventptr Sex;
385#endif
386
387 /* just mimic the corresponding encoding actions */
388 if (E == NULL)
389 start_model ();
390 S = s[FIXEDORDER];
391
392 *n = 0;
393 for (;;)
394 { /* logically equivalent to "decode_in_order(FIXEDORDER,&e)" */
395
396 for (;;)
397 {
398 T = decode_event_noex (&S->foll, &decoded, &e);
399 if (decoded)
400 break;
401 t[FIXEDORDER] = T;
402
403#ifdef NOEXCLUSIONS
404#if (FIXEDORDER>2)
405 S = p32 (S->prev);
406 t[2] = decode_event_noex (&S->foll, &decoded, &e);
407 t[3]->prev = p16 (t[2]);
408 if (decoded)
409 {
410 t[3]->eventnum = e;
411 break;
412 }
413#endif
414
415#if (FIXEDORDER>1)
416 S = p32 (S->prev);
417 t[1] = decode_event_noex (&S->foll, &decoded, &e);
418 t[2]->prev = p16 (t[1]);
419 if (decoded)
420 {
421#if (FIXEDORDER>2)
422 t[3]->eventnum =
423#endif
424 t[2]->eventnum = e;
425 break;
426 }
427#endif
428
429#if (FIXEDORDER>0)
430 S = p32 (S->prev);
431 t[0] = decode_event_noex (&S->foll, &decoded, &e);
432 t[1]->prev = p16 (t[0]);
433 if (decoded)
434 {
435#if (FIXEDORDER>2)
436 t[3]->eventnum =
437#endif
438#if (FIXEDORDER>1)
439 t[2]->eventnum =
440#endif
441 t[1]->eventnum = e;
442 break;
443 }
444#endif
445#else
446#if (FIXEDORDER>2)
447 Sex = S;
448 SET_EX (Sex->foll.list);
449 S = p32 (S->prev);
450 t[2] = decode_event (&S->foll, &decoded, &e);
451 t[3]->prev = p16 (t[2]);
452 if (decoded)
453 {
454 t[3]->eventnum = e;
455 CLEAR_EX (Sex->foll.list);
456 break;
457 }
458#endif
459
460#if (FIXEDORDER>1)
461 Sex = S;
462 SET_EX (Sex->foll.list);
463 S = p32 (S->prev);
464 t[1] = decode_event (&S->foll, &decoded, &e);
465 t[2]->prev = p16 (t[1]);
466 if (decoded)
467 {
468#if (FIXEDORDER>2)
469 t[3]->eventnum =
470#endif
471 t[2]->eventnum = e;
472 CLEAR_EX (Sex->foll.list);
473 break;
474 }
475#endif
476
477#if (FIXEDORDER>0)
478 Sex = S;
479 SET_EX (Sex->foll.list);
480 S = p32 (S->prev);
481 t[0] = decode_event (&S->foll, &decoded, &e);
482 t[1]->prev = p16 (t[0]);
483 if (decoded)
484 {
485#if (FIXEDORDER>2)
486 t[3]->eventnum =
487#endif
488#if (FIXEDORDER>1)
489 t[2]->eventnum =
490#endif
491 t[1]->eventnum = e;
492 CLEAR_EX (Sex->foll.list);
493 break;
494 }
495 CLEAR_EX (Sex->foll.list);
496#endif
497#endif
498
499 e = arithmetic_decode_target (nchars);
500 arithmetic_decode (e, e + 1, nchars);
501#if (FIXEDORDER>2)
502 t[3]->eventnum =
503#endif
504#if (FIXEDORDER>1)
505 t[2]->eventnum =
506#endif
507#if (FIXEDORDER>0)
508 t[1]->eventnum =
509#endif
510 t[0]->eventnum = e;
511 t[0]->prev = p16 (s[0]);
512 break;
513 }
514 S = p32 (T->prev);
515
516 /* check the space requirements */
517 if (nfreenodes <= FIXEDORDER)
518 {
519 start_model ();
520 S = s[FIXEDORDER];
521 }
522 /* are we done? or do we save the char */
523 if (e == EOSchar)
524 break;
525 *str++ = e;
526 (*n)++;
527 }
528 s[FIXEDORDER] = S;
529}
530
531
532#if 0 /* Writing my own version of this - MAHE */
533void
534encodefile ()
535/* encodes a file by breaking into a sequence of fixed length chunks */
536{
537 unsigned char *str;
538 int c, n = 0;
539
540 str = (unsigned char *) malloc ((unsigned) chunksize);
541 startoutputingbits ();
542 startencoding ();
543
544 /* to encode the file, break it into chunks and encode the
545 chunks one by one */
546 while ((c = getchar ()) != EOF)
547 {
548 str[n++] = c;
549 if (n == chunksize)
550 {
551 encodestring (str, n);
552 rawbytes += n;
553 n = 0;
554 }
555 }
556 /* send final partial chunk */
557 if (n > 0)
558 {
559 encodestring (str, n);
560 rawbytes += n;
561 }
562 /* send EOF as an empty string */
563 encodestring (str, 0);
564 doneencoding ();
565 doneoutputingbits ();
566}
567
568void
569decodefile ()
570{
571 unsigned char *str;
572 int n, i;
573
574 str = (unsigned char *) malloc ((unsigned) chunksize);
575 startinputingbits ();
576 startdecoding ();
577 for (;;)
578 {
579 decodestring (str, &n);
580 if (n == 0)
581 break;
582 for (i = 0; i < n; i++)
583 putchar ((int) str[i]);
584 rawbytes += n;
585 }
586}
587
588#endif /* #if 0 */
Note: See TracBrowser for help on using the repository browser.