xref: /plan9/sys/src/cmd/gs/src/gsserial.c (revision 593dc095aefb2a85c828727bbfa9da139a49bdf4)
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