1 /* Copyright (C) 1995, 1996, 1998 Aladdin Enterprises. All rights reserved.
2
3 This software is provided AS-IS with no warranty, either express or
4 implied.
5
6 This software is distributed under license and may not be copied,
7 modified or distributed except as expressly authorized under the terms
8 of the license contained in the file LICENSE in this distribution.
9
10 For more information about licensing, please refer to
11 http://www.ghostscript.com/licensing/. For information on
12 commercial licensing, go to http://www.artifex.com/licensing/ or
13 contact Artifex Software, Inc., 101 Lucas Valley Road #110,
14 San Rafael, CA 94903, U.S.A., +1(415)492-9861.
15 */
16
17 /* $Id: smtf.c,v 1.4 2002/02/21 22:24:54 giles Exp $ */
18 /* MoveToFront filters */
19 #include "stdio_.h"
20 #include "strimpl.h"
21 #include "smtf.h"
22
23 /* ------ MoveToFrontEncode/Decode ------ */
24
25 private_st_MTF_state();
26
27 /* Initialize */
28 private int
s_MTF_init(stream_state * st)29 s_MTF_init(stream_state * st)
30 {
31 stream_MTF_state *const ss = (stream_MTF_state *) st;
32 int i;
33
34 for (i = 0; i < 256; i++)
35 ss->prev.b[i] = (byte) i;
36 return 0;
37 }
38
39 /* Encode a buffer */
40 private int
s_MTFE_process(stream_state * st,stream_cursor_read * pr,stream_cursor_write * pw,bool last)41 s_MTFE_process(stream_state * st, stream_cursor_read * pr,
42 stream_cursor_write * pw, bool last)
43 {
44 stream_MTF_state *const ss = (stream_MTF_state *) st;
45 register const byte *p = pr->ptr;
46 register byte *q = pw->ptr;
47 const byte *rlimit = pr->limit;
48 uint count = rlimit - p;
49 uint wcount = pw->limit - q;
50 int status =
51 (count < wcount ? 0 : (rlimit = p + wcount, 1));
52
53 while (p < rlimit) {
54 byte b = *++p;
55 int i;
56 byte prev = b, repl;
57
58 for (i = 0; (repl = ss->prev.b[i]) != b; i++)
59 ss->prev.b[i] = prev, prev = repl;
60 ss->prev.b[i] = prev;
61 *++q = (byte) i;
62 }
63 pr->ptr = p;
64 pw->ptr = q;
65 return status;
66 }
67
68 /* Stream template */
69 const stream_template s_MTFE_template = {
70 &st_MTF_state, s_MTF_init, s_MTFE_process, 1, 1
71 };
72
73 /* Decode a buffer */
74 private int
s_MTFD_process(stream_state * st,stream_cursor_read * pr,stream_cursor_write * pw,bool last)75 s_MTFD_process(stream_state * st, stream_cursor_read * pr,
76 stream_cursor_write * pw, bool last)
77 {
78 stream_MTF_state *const ss = (stream_MTF_state *) st;
79 register const byte *p = pr->ptr;
80 register byte *q = pw->ptr;
81 const byte *rlimit = pr->limit;
82 uint count = rlimit - p;
83 uint wcount = pw->limit - q;
84 int status = (count <= wcount ? 0 : (rlimit = p + wcount, 1));
85
86 /* Cache the first few entries in local variables. */
87 byte
88 v0 = ss->prev.b[0], v1 = ss->prev.b[1],
89 v2 = ss->prev.b[2], v3 = ss->prev.b[3];
90
91 while (p < rlimit) {
92 byte first;
93
94 /* Zeros far outnumber all other bytes in the BWBS */
95 /* code; check for them first. */
96 if (*++p == 0) {
97 *++q = v0;
98 continue;
99 }
100 switch (*p) {
101 default:
102 {
103 uint b = *p;
104 byte *bp = &ss->prev.b[b];
105
106 *++q = first = *bp;
107 #if arch_sizeof_long == 4
108 ss->prev.b[3] = v3;
109 #endif
110 /* Move trailing entries individually. */
111 for (;; bp--, b--) {
112 *bp = bp[-1];
113 if (!(b & (sizeof(long) - 1)))
114 break;
115 }
116 /* Move in long-size chunks. */
117 for (; (b -= sizeof(long)) != 0;) {
118 bp -= sizeof(long);
119
120 #if arch_is_big_endian
121 *(ulong *) bp =
122 (*(ulong *) bp >> 8) |
123 ((ulong) bp[-1] << ((sizeof(long) - 1) * 8));
124
125 #else
126 *(ulong *) bp = (*(ulong *) bp << 8) | bp[-1];
127 #endif
128 }
129 }
130 #if arch_sizeof_long > 4 /* better be 8! */
131 goto m7;
132 case 7:
133 *++q = first = ss->prev.b[7];
134 m7: ss->prev.b[7] = ss->prev.b[6];
135 goto m6;
136 case 6:
137 *++q = first = ss->prev.b[6];
138 m6: ss->prev.b[6] = ss->prev.b[5];
139 goto m5;
140 case 5:
141 *++q = first = ss->prev.b[5];
142 m5: ss->prev.b[5] = ss->prev.b[4];
143 goto m4;
144 case 4:
145 *++q = first = ss->prev.b[4];
146 m4: ss->prev.b[4] = v3;
147 #endif
148 goto m3;
149 case 3:
150 *++q = first = v3;
151 m3: v3 = v2, v2 = v1, v1 = v0, v0 = first;
152 break;
153 case 2:
154 *++q = first = v2;
155 v2 = v1, v1 = v0, v0 = first;
156 break;
157 case 1:
158 *++q = first = v1;
159 v1 = v0, v0 = first;
160 break;
161 }
162 }
163 ss->prev.b[0] = v0;
164 ss->prev.b[1] = v1;
165 ss->prev.b[2] = v2;
166 ss->prev.b[3] = v3;
167 pr->ptr = p;
168 pw->ptr = q;
169 return status;
170 }
171
172 /* Stream template */
173 const stream_template s_MTFD_template = {
174 &st_MTF_state, s_MTF_init, s_MTFD_process, 1, 1,
175 NULL, NULL, s_MTF_init
176 };
177