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