1 /* Copyright (C) 2002 artofcode LLC. 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 /* $Id: gsserial.c,v 1.1 2002/08/22 07:12:29 henrys Exp $ */
17 /* some utilities useful for converting objects to serial form */
18
19 #include "stdpre.h"
20 #include "gstypes.h"
21 #include "gsserial.h"
22
23
24 /*
25 * Procedures for converint between integers and a variable-length,
26 * little-endian string representation thereof. This scheme uses a
27 * base-128 format with the high-order bit of each byte used as a
28 * continuation flag ((b & 0x80) == 0 ==> this is the last byte of the
29 * current number). See gsserial.h for complete information.
30 */
31
32 /*
33 * Determine the size of the string representation of an unsigned or
34 * signed integer.
35 */
36 int
enc_u_size_uint(uint uval)37 enc_u_size_uint(uint uval)
38 {
39 int i = 1;
40
41 while ((uval >>= enc_u_shift) > 0)
42 ++i;
43 return i;
44 }
45
46 int
enc_s_size_int(int ival)47 enc_s_size_int(int ival)
48 {
49 /* MIN_INT must be handled specially */
50 if (ival < 0) {
51 if (ival == enc_s_min_int)
52 return enc_s_sizew_max;
53 ival = -ival;
54 }
55 return enc_u_sizew((uint)ival << 1);
56 }
57
58 /*
59 * Encode a signed or unsigned integer. The array pointed to by ptr is
60 * assumed to be large enough. The returned pointer immediately follows
61 * the encoded number.
62 */
63 byte *
enc_u_put_uint(uint uval,byte * ptr)64 enc_u_put_uint(uint uval, byte * ptr)
65 {
66 int tmp_v;
67
68 for (;;) {
69 tmp_v = uval & (enc_u_lim_1b - 1);
70 if ((uval >>= enc_u_shift) == 0)
71 break;
72 *ptr++ = tmp_v | enc_u_lim_1b;
73 }
74 *ptr++ = tmp_v;
75 return ptr;
76 }
77
78 byte *
enc_s_put_int(int ival,byte * ptr)79 enc_s_put_int(int ival, byte * ptr)
80 {
81 uint uval, tmp_v;
82
83 /* MIN_INT must be handled specially */
84 if (ival < 0 && ival != enc_s_min_int)
85 uval = (uint)-ival;
86 else
87 uval = (uint)ival;
88
89 tmp_v = (uval & enc_s_max_1b) | (ival < 0 ? enc_s_max_1b + 1 : 0);
90 if (uval > enc_s_max_1b) {
91 *ptr++ = tmp_v | enc_u_lim_1b;
92 return enc_u_put_uint(uval >> enc_s_shift0, ptr);
93 } else {
94 *ptr++ = tmp_v;
95 return ptr;
96 }
97 }
98
99
100 /*
101 * Decode an integer string for a signed or unsigned integer. Note that
102 * two forms of this procedure are provide, to allow both const and non-
103 * const byte pointers to be handled (the former is far more common).
104 */
105 const byte *
enc_u_get_uint(uint * pval,const byte * ptr)106 enc_u_get_uint(uint * pval, const byte * ptr)
107 {
108 uint uval = 0, tmp_val;
109 int shift = 0;
110
111 while (((tmp_val = *ptr++) & enc_u_lim_1b) != 0) {
112 uval |= (tmp_val & (enc_u_lim_1b - 1)) << shift;
113 shift += enc_u_shift;
114 }
115 *pval = uval | (tmp_val << shift);
116
117 return ptr;
118 }
119
120 byte *
enc_u_get_uint_nc(uint * pval,byte * ptr)121 enc_u_get_uint_nc(uint * pval, byte * ptr)
122 {
123 const byte * tmp_ptr = ptr;
124
125 tmp_ptr = enc_u_get_uint(pval, tmp_ptr);
126 return ptr += tmp_ptr - ptr;
127 }
128
129 const byte *
enc_s_get_int(int * pval,const byte * ptr)130 enc_s_get_int(int * pval, const byte * ptr)
131 {
132 int ival = *ptr++;
133 bool neg = false;
134
135 if ((ival & (enc_s_max_1b + 1)) != 0) {
136 ival ^= enc_s_max_1b + 1;
137 neg = true;
138 }
139 if ((ival & enc_u_lim_1b) != 0) {
140 uint tmp_val;
141
142 ival ^= enc_u_lim_1b;
143 ptr = enc_u_get_uint(&tmp_val, ptr);
144 ival |= tmp_val << enc_s_shift0;
145 }
146 if (neg && ival >= 0) /* >= check required for enc_s_min_int */
147 ival = -ival;
148
149 *pval = ival;
150 return ptr;
151 }
152
153 byte *
enc_s_get_int_nc(int * pval,byte * ptr)154 enc_s_get_int_nc(int * pval, byte * ptr)
155 {
156 const byte * tmp_ptr = ptr;
157
158 tmp_ptr = enc_s_get_int(pval, tmp_ptr);
159 return ptr += tmp_ptr - ptr;
160 }
161
162 #ifdef UNIT_TEST
163
164 #include <stdio.h>
165 #include <string.h>
166
167
168 /*
169 * Encoding and decoding of integers is verified using a round-trip process,
170 * integer ==> string ==> integer. The string size is separately checked to
171 * verify that it is not too large (it can't be too small if the round-trip
172 * check works). If an integer x is represented by nbytes, then it must be
173 * that x >= 1U << (7 * (n - 1)) (unsigned; 1U << (7 * (n - 2) + 6) for
174 * signed integers; there is no need to check 1-byte encodings).
175 *
176 * It is possible to check every value, but this is not necessary. Any
177 * failures that arise will do so in the vicinty of powers of 2.
178 */
179
180 /* check the length of an encoded string */
181 void
check_u_sizew(uint uval,int len)182 check_u_sizew(uint uval, int len)
183 {
184 if (len != enc_u_sizew(uval))
185 fprintf( stderr,
186 "Size calculation error for (usigned) %u (%d != %d)\n",
187 uval,
188 len,
189 enc_u_sizew(uval) );
190 if ( len > 1 &&
191 (len > enc_u_sizew_max || uval < 1U << (enc_u_shift * (len - 1))) )
192 fprintf( stderr, "unsigned encoding too large for %u (%d bytes)\n",
193 uval,
194 len );
195 }
196
197 void
check_s_sizew(int ival,int len)198 check_s_sizew(int ival, int len)
199 {
200 uint uval;
201
202 if (len != enc_s_sizew(ival))
203 fprintf( stderr,
204 "Size calculation error for (signed) %d (%d != %d)\n",
205 ival,
206 len,
207 enc_s_sizew(ival) );
208 if (len <= 1)
209 return;
210 if (ival < 0 && ival != enc_s_min_int)
211 uval = (uint)-ival;
212 else
213 uval = (uint)ival;
214 if ( len > enc_s_sizew_max ||
215 uval < 1U << (enc_s_shift1 * (len - 2) + enc_s_shift0) )
216 fprintf( stderr,
217 "signed encoding too large for %d (%d bytes)\n",
218 ival,
219 len );
220 }
221
222 /* check the encode and decode procedures on a value */
223 void
check_u(uint uval)224 check_u(uint uval)
225 {
226 byte buff[32]; /* generous size */
227 byte * cp0 = buff;
228 const byte * cp1 = buff;
229 byte * cp2 = buff;
230 uint res_val;
231
232 memset(buff, 0, sizeof(buff));
233 enc_u_putw(uval, cp0);
234 check_u_sizew(uval, cp0 - buff);
235 memset(cp0, (uval == 0 ? 0x7f : 0), sizeof(buff) - (cp0 - buff));
236
237 enc_u_getw(res_val, cp1);
238 if (cp1 != cp0)
239 fprintf( stderr,
240 "encoded length disparity (const) for "
241 "(unsigned) %u (%d != %d)\n",
242 uval,
243 cp0 - buff,
244 cp1 - buff );
245 if (res_val != uval)
246 fprintf( stderr,
247 "decode error (const) for (unsigned) %u (!= %u)\n",
248 uval,
249 res_val );
250
251 enc_u_getw_nc(res_val, cp2);
252 if (cp2 != cp0)
253 fprintf( stderr,
254 "encoded length disparity (non-const) for "
255 "(unsigned) %u (%d != %d)\n",
256 uval,
257 cp0 - buff,
258 cp1 - buff );
259 if (res_val != uval)
260 fprintf( stderr,
261 "decode error (non-const) for (unsigned) %u (!= %u)\n",
262 uval,
263 res_val );
264 }
265
266 void
check_s(int ival)267 check_s(int ival)
268 {
269 byte buff[32]; /* generous size */
270 byte * cp0 = buff;
271 const byte * cp1 = buff;
272 byte * cp2 = buff;
273 int res_val;
274
275 memset(buff, 0, sizeof(buff));
276 enc_s_putw(ival, cp0);
277 check_s_sizew(ival, cp0 - buff);
278 memset(cp0, (ival == 0 ? 0x7f : 0), sizeof(buff) - (cp0 - buff));
279
280 enc_s_getw(res_val, cp1);
281 if (cp1 != cp0)
282 fprintf( stderr,
283 "encoded length disparity (const) for "
284 "(signed) %d (%d != %d)\n",
285 ival,
286 cp0 - buff,
287 cp1 - buff );
288 if (res_val != ival)
289 fprintf( stderr,
290 "decode error (const) for (signed) %d (!= %d)\n",
291 ival,
292 res_val );
293
294 enc_s_getw_nc(res_val, cp2);
295 if (cp1 != cp0)
296 fprintf( stderr,
297 "encoded length disparity (non-const) for "
298 "(signed) %d (%d != %d)\n",
299 ival,
300 cp0 - buff,
301 cp1 - buff );
302 if (res_val != ival)
303 fprintf( stderr,
304 "decode error (non-const) for (unsigned) %d (!= %d)\n",
305 ival,
306 res_val );
307 }
308
309 /* test the provided value and some surrounding values */
310 void
check_u_vals(uint uval)311 check_u_vals(uint uval)
312 {
313 uint diff = 1;
314
315 check_u(uval);
316 do {
317 check_u(uval - diff);
318 check_u(uval + diff);
319 } while ((diff <<= 1) < uval);
320 }
321
322 void
check_s_vals(int ival)323 check_s_vals(int ival)
324 {
325 int diff = 1;
326
327 check_s(ival);
328 if (ival == enc_s_min_int) {
329 do {
330 check_s(ival - diff);
331 check_s(ival + diff);
332 } while ((diff <<= 1) != enc_s_min_int);
333 } else {
334 int abs_val = (ival < 0 ? -ival : ival);
335
336 do {
337 check_s(ival - diff);
338 check_s(ival + diff);
339 } while ((diff <<= 1) < abs_val);
340 }
341 }
342
343
344 int
main(void)345 main(void)
346 {
347 uint uval;
348 int ival;
349
350 check_u_vals(0);
351 for (uval = 1; uval != 0; uval <<= 1)
352 check_u_vals(uval);
353
354 check_s_vals(0);
355 for (ival = 1; ival != 0; ival <<= 1) {
356 check_s_vals(ival);
357 if (ival != enc_s_min_int)
358 check_s_vals(-ival);
359 }
360
361 fprintf(stderr, "all done\n");
362 return 0;
363 }
364
365 #endif /* UNIT_TEST */
366