1 /* ========================================================================
2 * Copyright 2008 Mark Crispin
3 * ========================================================================
4 */
5
6 /*
7 * Program: Miscellaneous utility routines
8 *
9 * Author: Mark Crispin
10 *
11 * Date: 5 July 1988
12 * Last Edited: 19 November 2008
13 *
14 * Previous versions of this file were
15 *
16 * Copyright 1988-2006 University of Washington
17 *
18 * Licensed under the Apache License, Version 2.0 (the "License");
19 * you may not use this file except in compliance with the License.
20 * You may obtain a copy of the License at
21 *
22 * http://www.apache.org/licenses/LICENSE-2.0
23 *
24 * This original version of this file is
25 * Copyright 1988 Stanford University
26 * and was developed in the Symbolic Systems Resources Group of the Knowledge
27 * Systems Laboratory at Stanford University in 1987-88, and was funded by the
28 * Biomedical Research Technology Program of the NationalInstitutes of Health
29 * under grant number RR-00785.
30 */
31
32
33 #include <ctype.h>
34 #include "c-client.h"
35
36 /* Convert ASCII string to all uppercase
37 * Accepts: string pointer
38 * Returns: string pointer
39 *
40 * Don't use islower/toupper since this function must be ASCII only.
41 */
42
ucase(unsigned char * s)43 unsigned char *ucase (unsigned char *s)
44 {
45 unsigned char *t;
46 /* if lowercase covert to upper */
47 for (t = s; *t; t++) if ((*t >= 'a') && (*t <= 'z')) *t -= ('a' - 'A');
48 return s; /* return string */
49 }
50
51
52 /* Convert string to all lowercase
53 * Accepts: string pointer
54 * Returns: string pointer
55 *
56 * Don't use isupper/tolower since this function must be ASCII only.
57 */
58
lcase(unsigned char * s)59 unsigned char *lcase (unsigned char *s)
60 {
61 unsigned char *t;
62 /* if uppercase covert to lower */
63 for (t = s; *t; t++) if ((*t >= 'A') && (*t <= 'Z')) *t += ('a' - 'A');
64 return s; /* return string */
65 }
66
67 /* Copy string to free storage
68 * Accepts: source string
69 * Returns: free storage copy of string
70 */
71
cpystr(const char * string)72 char *cpystr (const char *string)
73 {
74 return string ? strcpy ((char *) fs_get (1 + strlen (string)),string) : NIL;
75 }
76
77
78 /* Copy text/size to free storage as sized text
79 * Accepts: destination sized text
80 * pointer to source text
81 * size of source text
82 * Returns: text as a char *
83 */
84
cpytxt(SIZEDTEXT * dst,char * text,unsigned long size)85 char *cpytxt (SIZEDTEXT *dst,char *text,unsigned long size)
86 {
87 /* flush old space */
88 if (dst->data) fs_give ((void **) &dst->data);
89 /* copy data in sized text */
90 memcpy (dst->data = (unsigned char *)
91 fs_get ((size_t) (dst->size = size) + 1),text,(size_t) size);
92 dst->data[size] = '\0'; /* tie off text */
93 return (char *) dst->data; /* convenience return */
94 }
95
96 /* Copy sized text to free storage as sized text
97 * Accepts: destination sized text
98 * source sized text
99 * Returns: text as a char *
100 */
101
textcpy(SIZEDTEXT * dst,SIZEDTEXT * src)102 char *textcpy (SIZEDTEXT *dst,SIZEDTEXT *src)
103 {
104 /* flush old space */
105 if (dst->data) fs_give ((void **) &dst->data);
106 /* copy data in sized text */
107 memcpy (dst->data = (unsigned char *)
108 fs_get ((size_t) (dst->size = src->size) + 1),
109 src->data,(size_t) src->size);
110 dst->data[dst->size] = '\0'; /* tie off text */
111 return (char *) dst->data; /* convenience return */
112 }
113
114
115 /* Copy stringstruct to free storage as sized text
116 * Accepts: destination sized text
117 * source stringstruct
118 * Returns: text as a char *
119 */
120
textcpystring(SIZEDTEXT * text,STRING * bs)121 char *textcpystring (SIZEDTEXT *text,STRING *bs)
122 {
123 unsigned long i = 0;
124 /* clear old space */
125 if (text->data) fs_give ((void **) &text->data);
126 /* make free storage space in sized text */
127 text->data = (unsigned char *) fs_get ((size_t) (text->size = SIZE (bs)) +1);
128 while (i < text->size) text->data[i++] = SNX (bs);
129 text->data[i] = '\0'; /* tie off text */
130 return (char *) text->data; /* convenience return */
131 }
132
133
134 /* Copy stringstruct from offset to free storage as sized text
135 * Accepts: destination sized text
136 * source stringstruct
137 * offset into stringstruct
138 * size of source text
139 * Returns: text as a char *
140 */
141
textcpyoffstring(SIZEDTEXT * text,STRING * bs,unsigned long offset,unsigned long size)142 char *textcpyoffstring (SIZEDTEXT *text,STRING *bs,unsigned long offset,
143 unsigned long size)
144 {
145 unsigned long i = 0;
146 /* clear old space */
147 if (text->data) fs_give ((void **) &text->data);
148 SETPOS (bs,offset); /* offset the string */
149 /* make free storage space in sized text */
150 text->data = (unsigned char *) fs_get ((size_t) (text->size = size) + 1);
151 while (i < size) text->data[i++] = SNX (bs);
152 text->data[i] = '\0'; /* tie off text */
153 return (char *) text->data; /* convenience return */
154 }
155
156 /* Returns index of rightmost bit in word
157 * Accepts: pointer to a 32 bit value
158 * Returns: -1 if word is 0, else index of rightmost bit
159 *
160 * Bit is cleared in the word
161 */
162
find_rightmost_bit(unsigned long * valptr)163 unsigned long find_rightmost_bit (unsigned long *valptr)
164 {
165 unsigned long value = *valptr;
166 unsigned long bit = 0;
167 if (!(value & 0xffffffff)) return 0xffffffff;
168 /* binary search for rightmost bit */
169 if (!(value & 0xffff)) value >>= 16, bit += 16;
170 if (!(value & 0xff)) value >>= 8, bit += 8;
171 if (!(value & 0xf)) value >>= 4, bit += 4;
172 if (!(value & 0x3)) value >>= 2, bit += 2;
173 if (!(value & 0x1)) value >>= 1, bit += 1;
174 *valptr ^= (1 << bit); /* clear specified bit */
175 return bit;
176 }
177
178
179 /* Return minimum of two integers
180 * Accepts: integer 1
181 * integer 2
182 * Returns: minimum
183 */
184
min(long i,long j)185 long min (long i,long j)
186 {
187 return ((i < j) ? i : j);
188 }
189
190
191 /* Return maximum of two integers
192 * Accepts: integer 1
193 * integer 2
194 * Returns: maximum
195 */
196
max(long i,long j)197 long max (long i,long j)
198 {
199 return ((i > j) ? i : j);
200 }
201
202 /* Search, case-insensitive for ASCII characters
203 * Accepts: base string
204 * length of base string
205 * pattern string
206 * length of pattern string
207 * Returns: T if pattern exists inside base, else NIL
208 */
209
search(unsigned char * base,long basec,unsigned char * pat,long patc)210 long search (unsigned char *base,long basec,unsigned char *pat,long patc)
211 {
212 long i,j,k;
213 int c;
214 unsigned char mask[256];
215 static unsigned char alphatab[256] = {
216 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
217 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
218 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
219 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
220 255,223,223,223,223,223,223,223,223,223,223,223,223,223,223,223,
221 223,223,223,223,223,223,223,223,223,223,223,255,255,255,255,255,
222 255,223,223,223,223,223,223,223,223,223,223,223,223,223,223,223,
223 223,223,223,223,223,223,223,223,223,223,223,255,255,255,255,255,
224 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
225 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
226 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
227 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
228 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
229 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
230 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
231 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255
232 };
233 /* validate arguments */
234 if (base && (basec > 0) && pat && (basec >= patc)) {
235 if (patc <= 0) return T; /* empty pattern always succeeds */
236 memset (mask,0,256); /* initialize search validity mask */
237 for (i = 0; i < patc; i++) if (!mask[c = pat[i]]) {
238 /* mark single character if non-alphabetic */
239 if (alphatab[c] & 0x20) mask[c] = T;
240 /* else mark both cases */
241 else mask[c & 0xdf] = mask[c | 0x20] = T;
242 }
243 /* Boyer-Moore type search */
244 for (i = --patc; i < basec; i += (mask[c] ? 1 : (j + 1)))
245 for (j = patc,c = base[k = i]; !((c ^ pat[j]) & alphatab[c]);
246 j--,c = base[--k])
247 if (!j) return T; /* found a match! */
248 }
249 return NIL; /* pattern not found */
250 }
251
252 /* Boyer-Moore string search
253 * Accepts: base string
254 * length of base string
255 * pattern string
256 * length of pattern string
257 * Returns: T if pattern exists inside base, else NIL
258 */
259
ssearch(unsigned char * base,long basec,unsigned char * pat,long patc)260 long ssearch (unsigned char *base,long basec,unsigned char *pat,long patc)
261 {
262 long i,j,k;
263 int c;
264 unsigned char mask[256];
265 /* validate arguments */
266 if (base && (basec > 0) && pat && (basec >= patc)) {
267 if (patc <= 0) return T; /* empty pattern always succeeds */
268 memset (mask,0,256); /* initialize search validity mask */
269 for (i = 0; i < patc; i++) mask[pat[i]] = T;
270 /* Boyer-Moore type search */
271 for (i = --patc, c = pat[i]; i < basec; i += (mask[c] ? 1 : (j + 1)))
272 for (j = patc,c = base[k = i]; (c == pat[j]); j--,c = base[--k])
273 if (!j) return T; /* found a match! */
274 }
275 return NIL; /* pattern not found */
276 }
277
278 /* Create a hash table
279 * Accepts: size of new table (note: should be a prime)
280 * Returns: hash table
281 */
282
hash_create(size_t size)283 HASHTAB *hash_create (size_t size)
284 {
285 size_t i = sizeof (size_t) + size * sizeof (HASHENT *);
286 HASHTAB *ret = (HASHTAB *) memset (fs_get (i),0,i);
287 ret->size = size;
288 return ret;
289 }
290
291
292 /* Destroy hash table
293 * Accepts: hash table
294 */
295
hash_destroy(HASHTAB ** hashtab)296 void hash_destroy (HASHTAB **hashtab)
297 {
298 if (*hashtab) {
299 hash_reset (*hashtab); /* reset hash table */
300 fs_give ((void **) hashtab);
301 }
302 }
303
304
305 /* Reset hash table
306 * Accepts: hash table
307 */
308
hash_reset(HASHTAB * hashtab)309 void hash_reset (HASHTAB *hashtab)
310 {
311 size_t i;
312 HASHENT *ent,*nxt;
313 /* free each hash entry */
314 for (i = 0; i < hashtab->size; i++) if (ent = hashtab->table[i])
315 for (hashtab->table[i] = NIL; ent; ent = nxt) {
316 nxt = ent->next; /* get successor */
317 fs_give ((void **) &ent); /* flush this entry */
318 }
319 }
320
321 /* Calculate index into hash table
322 * Accepts: hash table
323 * entry name
324 * Returns: index
325 */
326
hash_index(HASHTAB * hashtab,char * key)327 unsigned long hash_index (HASHTAB *hashtab,char *key)
328 {
329 unsigned long i,ret;
330 /* polynomial of letters of the word */
331 for (ret = 0; i = (unsigned int) *key++; ret += i) ret *= HASHMULT;
332 return ret % (unsigned long) hashtab->size;
333 }
334
335
336 /* Look up name in hash table
337 * Accepts: hash table
338 * key
339 * Returns: associated data
340 */
341
hash_lookup(HASHTAB * hashtab,char * key)342 void **hash_lookup (HASHTAB *hashtab,char *key)
343 {
344 HASHENT *ret;
345 for (ret = hashtab->table[hash_index (hashtab,key)]; ret; ret = ret->next)
346 if (!strcmp (key,ret->name)) return ret->data;
347 return NIL;
348 }
349
350 /* Add entry to hash table
351 * Accepts: hash table
352 * key
353 * associated data
354 * number of extra data slots
355 * Returns: hash entry
356 * Caller is responsible for ensuring that entry isn't already in table
357 */
358
hash_add(HASHTAB * hashtab,char * key,void * data,long extra)359 HASHENT *hash_add (HASHTAB *hashtab,char *key,void *data,long extra)
360 {
361 unsigned long i = hash_index (hashtab,key);
362 size_t j = sizeof (HASHENT) + (extra * sizeof (void *));
363 HASHENT *ret = (HASHENT *) memset (fs_get (j),0,j);
364 ret->next = hashtab->table[i];/* insert as new head in this index */
365 ret->name = key; /* set up hash key */
366 ret->data[0] = data; /* and first data */
367 return hashtab->table[i] = ret;
368 }
369
370
371 /* Look up name in hash table
372 * Accepts: hash table
373 * key
374 * associated data
375 * number of extra data slots
376 * Returns: associated data
377 */
378
hash_lookup_and_add(HASHTAB * hashtab,char * key,void * data,long extra)379 void **hash_lookup_and_add (HASHTAB *hashtab,char *key,void *data,long extra)
380 {
381 HASHENT *ret;
382 unsigned long i = hash_index (hashtab,key);
383 size_t j = sizeof (HASHENT) + (extra * sizeof (void *));
384 for (ret = hashtab->table[i]; ret; ret = ret->next)
385 if (!strcmp (key,ret->name)) return ret->data;
386 ret = (HASHENT *) memset (fs_get (j),0,j);
387 ret->next = hashtab->table[i];/* insert as new head in this index */
388 ret->name = key; /* set up hash key */
389 ret->data[0] = data; /* and first data */
390 return (hashtab->table[i] = ret)->data;
391 }
392
393 /* Convert two hex characters into byte
394 * Accepts: char for high nybble
395 * char for low nybble
396 * Returns: byte
397 *
398 * Arguments must be isxdigit validated
399 */
400
hex2byte(unsigned char c1,unsigned char c2)401 unsigned char hex2byte (unsigned char c1,unsigned char c2)
402 {
403 /* merge the two nybbles */
404 return ((c1 -= (isdigit (c1) ? '0' : ((c1 <= 'Z') ? 'A' : 'a') - 10)) << 4) +
405 (c2 - (isdigit (c2) ? '0' : ((c2 <= 'Z') ? 'A' : 'a') - 10));
406 }
407
408
409 /* Compare two unsigned longs
410 * Accepts: first value
411 * second value
412 * Returns: -1 if l1 < l2, 0 if l1 == l2, 1 if l1 > l2
413 */
414
compare_ulong(unsigned long l1,unsigned long l2)415 int compare_ulong (unsigned long l1,unsigned long l2)
416 {
417 if (l1 < l2) return -1;
418 if (l1 > l2) return 1;
419 return 0;
420 }
421
422
423 /* Compare two unsigned chars, case-independent
424 * Accepts: first value
425 * second value
426 * Returns: -1 if c1 < c2, 0 if c1 == c2, 1 if c1 > c2
427 *
428 * Don't use isupper/tolower since this function must be ASCII only.
429 */
430
compare_uchar(unsigned char c1,unsigned char c2)431 int compare_uchar (unsigned char c1,unsigned char c2)
432 {
433 return compare_ulong (((c1 >= 'a') && (c1 <= 'z')) ? c1 - ('a' - 'A') : c1,
434 ((c2 >= 'a') && (c2 <= 'z')) ? c2 - ('a' - 'A') : c2);
435 }
436
437 /* Compare two strings by octet
438 * Accepts: first string
439 * second string
440 * Returns: -1 if s1 < s2, 0 if s1 == s2, 1 if s1 > s2
441 *
442 * Effectively strcmp() but without locales
443 */
444
compare_string(unsigned char * s1,unsigned char * s2)445 int compare_string (unsigned char *s1,unsigned char *s2)
446 {
447 int i;
448 if (!s1) return s2 ? -1 : 0; /* empty string cases */
449 else if (!s2) return 1;
450 for (; *s1 && *s2; s1++,s2++) if (i = (compare_ulong (*s1,*s2))) return i;
451 if (*s1) return 1; /* first string is longer */
452 return *s2 ? -1 : 0; /* second string longer : strings identical */
453 }
454
455
456 /* Compare two case-independent ASCII strings
457 * Accepts: first string
458 * second string
459 * Returns: -1 if s1 < s2, 0 if s1 == s2, 1 if s1 > s2
460 *
461 * Effectively strcasecmp() but without locales
462 */
463
compare_cstring(unsigned char * s1,unsigned char * s2)464 int compare_cstring (unsigned char *s1,unsigned char *s2)
465 {
466 int i;
467 if (!s1) return s2 ? -1 : 0; /* empty string cases */
468 else if (!s2) return 1;
469 for (; *s1 && *s2; s1++,s2++) if (i = (compare_uchar (*s1,*s2))) return i;
470 if (*s1) return 1; /* first string is longer */
471 return *s2 ? -1 : 0; /* second string longer : strings identical */
472 }
473
474
475 /* Compare case-independent string with sized text
476 * Accepts: first string
477 * sized text
478 * Returns: -1 if s1 < s2, 0 if s1 == s2, 1 if s1 > s2
479 */
480
compare_csizedtext(unsigned char * s1,SIZEDTEXT * s2)481 int compare_csizedtext (unsigned char *s1,SIZEDTEXT *s2)
482 {
483 int i;
484 unsigned char *s;
485 unsigned long j;
486 if (!s1) return s2 ? -1 : 0; /* null string cases */
487 else if (!s2) return 1;
488 for (s = (char *) s2->data,j = s2->size; *s1 && j; ++s1,++s,--j)
489 if (i = (compare_uchar (*s1,*s))) return i;
490 if (*s1) return 1; /* first string is longer */
491 return j ? -1 : 0; /* second string longer : strings identical */
492 }
493