1 /*
2 * str - string list routines
3 *
4 * Copyright (C) 1999-2007,2021 David I. Bell and Ernest Bowen
5 *
6 * Primary author: David I. Bell
7 *
8 * Calc is open software; you can redistribute it and/or modify it under
9 * the terms of the version 2.1 of the GNU Lesser General Public License
10 * as published by the Free Software Foundation.
11 *
12 * Calc is distributed in the hope that it will be useful, but WITHOUT
13 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
15 * Public License for more details.
16 *
17 * A copy of version 2.1 of the GNU Lesser General Public License is
18 * distributed with calc under the filename COPYING-LGPL. You should have
19 * received a copy with calc; if not, write to Free Software Foundation, Inc.
20 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
21 *
22 * Under source code control: 1990/02/15 01:48:10
23 * File existed as early as: before 1990
24 *
25 * Share and enjoy! :-) http://www.isthe.com/chongo/tech/comp/calc/
26 */
27
28
29 #include <stdio.h>
30 #include <ctype.h>
31 #include "have_string.h"
32 #ifdef HAVE_STRING_H
33 # include <string.h>
34 #endif
35 #include "calc.h"
36 #include "alloc.h"
37 #include "str.h"
38 #include "strl.h"
39
40
41 #include "banned.h" /* include after system header <> includes */
42
43
44 #define STR_TABLECHUNK 100 /* how often to reallocate string table */
45 #define STR_CHUNK (1<<11) /* size of string storage allocation */
46 #define OCTET_VALUES 256 /* number of different values in a OCTET */
47 #define STR_UNIQUE (1<<7) /* size of string to allocate separately */
48
49 STRING _nullstring_ = {"", 0, 1, NULL};
50
51 STATIC char *chartable; /* single character string table */
52
53 STATIC struct {
54 long l_count; /* count of strings in table */
55 long l_maxcount; /* maximum strings storable in table */
56 size_t l_avail; /* characters available in current string */
57 char *l_alloc; /* next available string storage */
58 char **l_table; /* current string table */
59 } literals;
60
61
62 /*
63 * Initialize or reinitialize a string header for use.
64 *
65 * given:
66 * hp structure to be inited
67 */
68 void
initstr(STRINGHEAD * hp)69 initstr(STRINGHEAD *hp)
70 {
71 if (hp->h_list == NULL) {
72 /* alloc + 1 guard paranoia */
73 hp->h_list = (char *)malloc(STR_CHUNK + 1);
74 if (hp->h_list == NULL) {
75 math_error("Cannot allocate string header");
76 /*NOTREACHED*/
77 }
78 hp->h_list[STR_CHUNK] = '\0'; /* guard paranoia */
79 hp->h_avail = STR_CHUNK;
80 hp->h_used = 0;
81 }
82 hp->h_avail += hp->h_used;
83 hp->h_used = 0;
84 hp->h_count = 0;
85 hp->h_list[0] = '\0';
86 hp->h_list[1] = '\0';
87 }
88
89
90 /*
91 * Copy a string to the end of a list of strings, and return the address
92 * of the copied string. Returns NULL if the string could not be copied.
93 * No checks are made to see if the string is already in the list.
94 * The string cannot be null or have embedded nulls.
95 *
96 * given:
97 * hp header of string storage
98 * str string to be added
99 */
100 char *
addstr(STRINGHEAD * hp,char * str)101 addstr(STRINGHEAD *hp, char *str)
102 {
103 char *retstr; /* returned string pointer */
104 char *list; /* string list */
105 long newsize; /* new size of string list */
106 size_t len; /* length of current string */
107
108 if ((str == NULL) || (*str == '\0'))
109 return NULL;
110 len = strlen(str) + 1;
111 if (len >= hp->h_avail) {
112 /* alloc + 1 guard paranoia */
113 newsize = len + STR_CHUNK + hp->h_used + hp->h_avail + 1;
114 /* alloc + 1 guard paranoia */
115 list = (char *)realloc(hp->h_list, newsize + 1);
116 if (list == NULL)
117 return NULL;
118 list[newsize] = '\0'; /* guard paranoia */
119 hp->h_list = list;
120 hp->h_avail = newsize - hp->h_used;
121 }
122 retstr = hp->h_list + hp->h_used;
123 hp->h_used += len;
124 hp->h_avail -= len;
125 hp->h_count++;
126 strlcpy(retstr, str, len);
127 retstr[len] = '\0';
128 return retstr;
129 }
130
131
132 /*
133 * Return a null-terminated string which consists of a single character.
134 * The table is initialized on the first call.
135 */
136 char *
charstr(int ch)137 charstr(int ch)
138 {
139 char *cp;
140 int i;
141
142 if (chartable == NULL) {
143 /* alloc + 1 guard paranoia */
144 cp = (char *)malloc((OCTET_VALUES + 1)*2);
145 if (cp == NULL) {
146 math_error("Cannot allocate character table");
147 /*NOTREACHED*/
148 }
149 for (i = 0; i < OCTET_VALUES; i++) {
150 *cp++ = (char)i;
151 *cp++ = '\0';
152 }
153 chartable = cp - (OCTET_VALUES*2);
154 *cp++ = '\0'; /* guard paranoia */
155 *cp++ = '\0'; /* guard paranoia */
156 }
157 return &chartable[(ch & 0xff) * 2];
158 }
159
160
161 /*
162 * Find a string with the specified name and return its number in the
163 * string list. The first string is numbered zero. Minus one is returned
164 * if the string is not found.
165 *
166 * given:
167 * hp header of string storage
168 * str string to be added
169 */
170 int
findstr(STRINGHEAD * hp,char * str)171 findstr(STRINGHEAD *hp, char *str)
172 {
173 register char *test; /* string being tested */
174 size_t len; /* length of string being found */
175 size_t testlen; /* length of test string */
176 int index; /* index of string */
177
178 if ((hp->h_count <= 0) || (str == NULL))
179 return -1;
180 len = strlen(str);
181 test = hp->h_list;
182 index = 0;
183 while (*test) {
184 testlen = strlen(test);
185 if ((testlen == len) && (*test == *str) &&
186 (strcmp(test, str) == 0))
187 return index;
188 test += (testlen + 1);
189 index++;
190 }
191 return -1;
192 }
193
194
195 /*
196 * Return the name of a string with the given index.
197 * If the index is illegal, a pointer to an empty string is returned.
198 *
199 * given:
200 * hp header of string storage
201 * n string index
202 */
203 char *
namestr(STRINGHEAD * hp,long n)204 namestr(STRINGHEAD *hp, long n)
205 {
206 register char *str; /* current string */
207
208 if (n >= hp->h_count)
209 return "";
210 str = hp->h_list;
211 while (*str) {
212 if (--n < 0)
213 return str;
214 str += (strlen(str) + 1);
215 }
216 return "";
217 }
218
219
220 /*
221 * Useful routine to return the index of one string within another one
222 * which has the format: "str1\000str2\000str3\000...strn\0\0". Index starts
223 * at one for the first string. Returns zero if the string being checked
224 * is not contained in the formatted string.
225 *
226 * Be sure to use \000 instead of \0. ANSI-C compilers interpret "foo\0foo..."
227 * as "foo\017oo...".
228 *
229 * given:
230 * format string formatted into substrings
231 * test string to be found in formatted string
232 */
233 long
stringindex(char * format,char * test)234 stringindex(char *format, char *test)
235 {
236 long index; /* found index */
237 size_t len; /* length of current piece of string */
238 size_t testlen; /* length of test string */
239
240 testlen = strlen(test);
241 index = 1;
242 while (*format) {
243 len = strlen(format);
244 if ((len == testlen) && (*format == *test) &&
245 (strcmp(format, test) == 0))
246 return index;
247 format += (len + 1);
248 index++;
249 }
250 return 0;
251 }
252
253
254 /*
255 * Add a possibly new literal string to the literal string pool.
256 * Returns the new string address which is guaranteed to be always valid.
257 * Duplicate strings will repeatedly return the same address.
258 */
259 char *
addliteral(char * str)260 addliteral(char *str)
261 {
262 register char **table; /* table of strings */
263 char *newstr; /* newly allocated string */
264 long count; /* number of strings */
265 size_t len; /* length of string to allocate */
266
267 len = strlen(str);
268 if (len <= 1)
269 return charstr(*str);
270 /*
271 * See if the string is already in the table.
272 */
273 table = literals.l_table;
274 count = literals.l_count;
275 while (count-- > 0) {
276 if ((str[0] == table[0][0]) && (str[1] == table[0][1]) &&
277 (strcmp(str, table[0]) == 0))
278 return table[0];
279 table++;
280 }
281 /*
282 * Make the table of string pointers larger if necessary.
283 */
284 if (literals.l_count >= literals.l_maxcount) {
285 count = literals.l_maxcount + STR_TABLECHUNK;
286 if (literals.l_maxcount) {
287 /* alloc + 1 guard paranoia */
288 table = (char **) realloc(literals.l_table,
289 (count + 1) * sizeof(char *));
290 table[count] = NULL; /* guard paranoia */
291 } else {
292 /* alloc + 1 guard paranoia */
293 table = (char **) malloc((count + 1) * sizeof(char *));
294 table[count] = NULL; /* guard paranoia */
295 }
296 if (table == NULL) {
297 math_error("Cannot allocate string literal table");
298 /*NOTREACHED*/
299 }
300 literals.l_table = table;
301 literals.l_maxcount = count;
302 }
303 table = literals.l_table;
304 /*
305 * If the new string is very long, allocate it manually.
306 *
307 * Add room for trailing NUL and then round up to a
308 * memory chunk (in this case we pick the size of a FULL
309 * just because that is a nice size) for extra padded room.
310 */
311 len = ROUNDUP(len+1, FULL_LEN);
312 if (len >= STR_UNIQUE) {
313 /* alloc + 1 guard paranoia */
314 newstr = (char *)malloc(len + 1);
315 if (newstr == NULL) {
316 math_error("Cannot allocate large literal string");
317 /*NOTREACHED*/
318 }
319 newstr[len] = '\0'; /* guard paranoia */
320 strlcpy(newstr, str, len);
321 table[literals.l_count++] = newstr;
322 return newstr;
323 }
324 /*
325 * If the remaining space in the allocate string is too small,
326 * then allocate a new one.
327 */
328 if (literals.l_avail < len) {
329 /* alloc + 1 guard paranoia */
330 newstr = (char *)malloc(STR_CHUNK + 1);
331 if (newstr == NULL) {
332 math_error("Cannot allocate new literal string");
333 /*NOTREACHED*/
334 }
335 newstr[STR_CHUNK] = '\0'; /* guard paranoia */
336 literals.l_alloc = newstr;
337 literals.l_avail = STR_CHUNK;
338 }
339 /*
340 * Allocate the new string from the allocate string.
341 */
342 newstr = literals.l_alloc;
343 literals.l_avail -= len;
344 literals.l_alloc += len;
345 table[literals.l_count++] = newstr;
346 strlcpy(newstr, str, len);
347 return newstr;
348 }
349
350
351 STRING *
stringadd(STRING * s1,STRING * s2)352 stringadd(STRING *s1, STRING *s2)
353 {
354 STRING *s;
355 char *cfrom, *c;
356 long len;
357
358 len = s1->s_len + s2->s_len;
359 s = stralloc();
360 s->s_len = len;
361 s->s_str = (char *) malloc(len + 1);
362 if (s->s_str == NULL)
363 return NULL;
364 len = s1->s_len;
365 cfrom = s1->s_str;
366 c = s->s_str;
367 while (len-- > 0)
368 *c++ = *cfrom++;
369 len = s2->s_len;
370 cfrom = s2->s_str;
371 while (len-- > 0)
372 *c++ = *cfrom++;
373 *c = '\0';
374 return s;
375 }
376
377 /*
378 * stringneg reverses the characters in a string, returns null if malloc fails
379 */
380 STRING *
stringneg(STRING * str)381 stringneg(STRING *str)
382 {
383 long len;
384 STRING *s;
385 char *c, *cfrom;
386
387 len = str->s_len;
388 if (len <= 1)
389 return slink(str);
390 c = (char *) malloc(len + 1);
391 if (c == NULL)
392 return NULL;
393 s = stralloc();
394 s->s_len = len;
395 s->s_str = c;
396 cfrom = str->s_str + len;
397 while (len-- > 0)
398 *c++ = *--cfrom;
399 *c = '\0';
400 return s;
401 }
402
403 STRING *
stringsub(STRING * s1,STRING * s2)404 stringsub(STRING *s1, STRING *s2)
405 {
406 STRING *tmp, *s;
407
408 tmp = stringneg(s2);
409 if (tmp == NULL)
410 return NULL;
411 s = stringadd(s1, tmp);
412 if (s != NULL)
413 sfree(tmp);
414 return s;
415 }
416
417 /*
418 * stringmul: repeated concatenation, reverse if negative multiplier
419 * returns null if malloc fails
420 */
421 STRING *
stringmul(NUMBER * q,STRING * str)422 stringmul(NUMBER *q, STRING *str)
423 {
424 long len;
425 size_t j;
426 NUMBER *tmp1, *tmp2;
427 char *c, *c1;
428 STRING *s;
429 BOOL neg;
430
431 if (str->s_len == 0)
432 return slink(str);
433 neg = qisneg(q);
434 q = neg ? qneg(q): qlink(q);
435 tmp1 = itoq(str->s_len);
436 tmp2 = qmul(q, tmp1);
437 qfree(tmp1);
438 tmp1 = qint(tmp2);
439 qfree(tmp2);
440 if (zge31b(tmp1->num)) {
441 qfree(q);
442 qfree(tmp1);
443 return NULL;
444 }
445 len = qtoi(tmp1);
446 qfree(tmp1);
447 qfree(q);
448 if (len == 0)
449 return slink(&_nullstring_);
450 c = (char *) malloc(len + 1);
451 if (c == NULL)
452 return NULL;
453 str = neg ? stringneg(str) : slink(str);
454 s = stralloc();
455 s->s_str = c;
456 s->s_len = len;
457 j = 0;
458 c1 = str->s_str;
459 while (len-- > 0) {
460 *c++ = *c1++;
461 if (++j == str->s_len) {
462 j = 0;
463 c1 = str->s_str;
464 }
465 }
466 *c = '\0';
467 sfree(str);
468 return s;
469 }
470
471 STRING *
stringand(STRING * s1,STRING * s2)472 stringand(STRING *s1, STRING *s2)
473 {
474 STRING *s;
475 size_t len;
476 char *c1, *c2, *c;
477
478 if (s1->s_len == 0 || s2->s_len == 0)
479 return slink(&_nullstring_);
480 len = s1->s_len;
481 if (s2->s_len < len)
482 len = s2->s_len;
483 s = stralloc();
484 s->s_len = len;
485 c = malloc(len + 1);
486 if (c == NULL)
487 return NULL;
488 s->s_str = c;
489 c1 = s1->s_str;
490 c2 = s2->s_str;
491 while (len-- > 0)
492 *c++ = *c1++ & *c2++;
493 return s;
494 }
495
496
497 STRING *
stringor(STRING * s1,STRING * s2)498 stringor(STRING *s1, STRING *s2)
499 {
500 STRING *s;
501 long len, i, j;
502 char *c1, *c2, *c;
503
504 if (s1->s_len < s2->s_len) {
505 s = s1;
506 s1 = s2;
507 s2 = s;
508 } /* Now len(s1) >= len(s2) */
509 if (s2->s_len == 0)
510 return slink(s1);
511 i = s1->s_len;
512 if (i == 0)
513 return slink(&_nullstring_);
514 len = s1->s_len;
515 s = stralloc();
516 s->s_len = len;
517 c = malloc(len + 1);
518 if (c == NULL)
519 return NULL;
520 s->s_str = c;
521 c1 = s1->s_str;
522 c2 = s2->s_str;
523 i = s2->s_len;
524 j = s1->s_len - i;
525 while (i-- > 0)
526 *c++ = *c1++ | *c2++;
527 while (j-- > 0)
528 *c++ = *c1++;
529 return s;
530 }
531
532
533 STRING *
stringxor(STRING * s1,STRING * s2)534 stringxor(STRING *s1, STRING *s2)
535 {
536 STRING *s;
537 long len, i, j;
538 char *c1, *c2, *c;
539
540 if (s1->s_len < s2->s_len) {
541 s = s1;
542 s1 = s2;
543 s2 = s;
544 } /* Now len(s1) >= len(s2) */
545 if (s2->s_len == 0)
546 return slink(s1);
547 i = s1->s_len;
548 if (i == 0)
549 return slink(&_nullstring_);
550 len = s1->s_len;
551 s = stralloc();
552 s->s_len = len;
553 c = malloc(len + 1);
554 if (c == NULL)
555 return NULL;
556 s->s_str = c;
557 c1 = s1->s_str;
558 c2 = s2->s_str;
559 i = s2->s_len;
560 j = s1->s_len - i;
561 while (i-- > 0)
562 *c++ = *c1++ ^ *c2++;
563 while (j-- > 0)
564 *c++ = *c1++;
565 return s;
566 }
567
568
569 STRING *
stringdiff(STRING * s1,STRING * s2)570 stringdiff(STRING *s1, STRING *s2)
571 {
572 STRING *s;
573 size_t i;
574 char *c2, *c;
575
576 i = s1->s_len;
577 if (i == 0)
578 return slink(s1);
579 s = stringcopy(s1);
580 if (i > s2->s_len)
581 i = s2->s_len;
582 c = s->s_str;
583 c2 = s2->s_str;
584 while (i-- > 0)
585 *c++ &= ~*c2++;
586 return s;
587 }
588
589 STRING *
stringcomp(STRING * s1)590 stringcomp(STRING *s1)
591 {
592 long len;
593 STRING *s;
594 char *c1, *c;
595
596 len = s1->s_len;
597 if (len == 0)
598 return slink(&_nullstring_);
599 c = malloc(len + 1);
600 if (c == NULL)
601 return NULL;
602 s = stralloc();
603 s->s_len = len;
604 s->s_str = c;
605 c1 = s1->s_str;
606 while (len-- > 0)
607 *c++ = ~*c1++;
608 *c = '\0';
609 return s;
610 }
611
612 STRING *
stringsegment(STRING * s1,long n1,long n2)613 stringsegment(STRING *s1, long n1, long n2)
614 {
615 STRING *s;
616 char *c, *c1;
617 long len;
618
619 if ((n1 < 0 && n2 < 0) ||
620 ((size_t)n1 >= s1->s_len && (size_t)n2 >= s1->s_len))
621 return slink(&_nullstring_);
622 if (n1 < 0)
623 n1 = 0;
624 if (n2 < 0)
625 n2 = 0;
626 if ((size_t)n1 >= s1->s_len)
627 n1 = s1->s_len - 1;
628 if ((size_t)n2 >= s1->s_len)
629 n2 = s1->s_len - 1;
630 len = (n1 >= n2) ? n1 - n2 + 1 : n2 - n1 + 1;
631 s = stralloc();
632 c = malloc(len + 1);
633 if (c == NULL)
634 return NULL;
635 s->s_len = len;
636 s->s_str = c;
637 c1 = s1->s_str + n1;
638 if (n1 >= n2) {
639 /*
640 * We prevent the c1 pointer from walking behind s1_s_str
641 * by stopping one short of the end and running the loop one
642 * more time.
643 *
644 * We could stop the loop with just len-- > 0, but stopping
645 * short and running the loop one last time manually helps make
646 * code checkers such as insure happy.
647 */
648 while (len-- > 1) {
649 *c++ = *c1--;
650 }
651 /* run the loop manually one last time */
652 *c++ = *c1;
653 } else {
654 while (len-- > 0)
655 *c++ = *c1++;
656 }
657 *c = '\0';
658 return s;
659 }
660
661 /*
662 * stringshift shifts s1 n bits to left if n > 0, -n to the right if n < 0;
663 * octets in string considered to be in decreasing order of index, as in
664 * ... a_3 a_2 a_1 a_0. Returned string has same length as s1.
665 * Vacated bits are filled with '\0'; bits shifted off end are lost
666 */
667 STRING *
stringshift(STRING * s1,long n)668 stringshift(STRING *s1, long n)
669 {
670 char *c1, *c;
671 STRING *s;
672 long len, i, j, k;
673 BOOL right;
674 char ch;
675
676 len = s1->s_len;
677 if (len == 0 || n == 0)
678 return slink(s1);
679 right = (n < 0);
680 if (right) n = -n;
681 j = n & 7;
682 k = 8 - j;
683 n >>= 3;
684 c = malloc(len + 1);
685 if (c == NULL)
686 return NULL;
687 s = stralloc();
688 s->s_len = len;
689 s->s_str = c;
690 c[len] = '\0';
691 if (n > len)
692 n = len;
693 ch = '\0';
694 c1 = s1->s_str;
695 i = n;
696 if (right) {
697 c += len;
698 c1 += len;
699 while (i-- > 0)
700 *--c = '\0';
701 i = len - n;
702 while (i-- > 0) {
703 *--c = ((unsigned char) *--c1 >> j) | ch;
704 ch = (unsigned char) *c1 << k;
705 }
706 } else {
707 while (i-- > 0)
708 *c++ = '\0';
709 i = len - n;
710 while (i-- > 0) {
711 *c++ = ((unsigned char) *c1 << j) | ch;
712 ch = (unsigned char) *c1++ >> k;
713 }
714 }
715 return s;
716 }
717
718 /*
719 * stringtoupper makes st upper case
720 */
721 STRING *
stringtoupper(STRING * st)722 stringtoupper(STRING *st)
723 {
724 char *c1, *c2;
725 size_t num;
726
727 if (st->s_len > 0) {
728 c1 = st->s_str;
729 num = st->s_len;
730 c2 = c1;
731 while (num-- > 0)
732 *c1++ = (char)toupper((int)*c2++);
733 *c1 = '\0';
734 }
735 return slink(st);
736 }
737
738 /*
739 * stringtolower makes st lower case
740 */
741 STRING *
stringtolower(STRING * st)742 stringtolower(STRING *st)
743 {
744 char *c1, *c2;
745 size_t num;
746
747 if (st->s_len > 0) {
748 c1 = st->s_str;
749 num = st->s_len;
750 c2 = c1;
751 while (num-- > 0)
752 *c1++ = (char)tolower((int)*c2++);
753 *c1 = '\0';
754 }
755 return slink(st);
756 }
757
758
759 /*
760 * stringcpy copies as many characters as possible
761 * from s2 to s1 and returns s1
762 */
763 STRING *
stringcpy(STRING * s1,STRING * s2)764 stringcpy(STRING *s1, STRING *s2)
765 {
766 char *c1, *c2;
767 size_t num;
768
769 if (s1->s_len > 0) {
770 c1 = s1->s_str;
771 c2 = s2->s_str;
772 num = s1->s_len;
773 if (num > s2->s_len)
774 num = s2->s_len;
775 while (num-- > 0)
776 *c1++ = *c2++;
777 *c1 = '\0';
778 }
779 return slink(s1);
780 }
781
782 /*
783 * stringncpy copies up to num characters from s2 to s1 and returns s1
784 * If num > size(s2) null characters are copied until s1 is full or
785 * a total of num characters have been copied
786 */
787 STRING *
stringncpy(STRING * s1,STRING * s2,size_t num)788 stringncpy(STRING *s1, STRING *s2, size_t num)
789 {
790 char *c1, *c2;
791 size_t i;
792
793 if (num > s1->s_len)
794 num = s1->s_len;
795 i = num;
796 if (i > s2->s_len)
797 i = s2->s_len;
798 c1 = s1->s_str;
799 c2 = s2->s_str;
800 while (i-- > 0)
801 *c1++ = *c2++;
802 if (num > s2->s_len) {
803 memset(c1, 0, num - s2->s_len);
804 }
805 return slink(s1);
806 }
807
808
809 /*
810 * stringcontent counts the number of set bits in s
811 */
812 long
stringcontent(STRING * s)813 stringcontent(STRING *s)
814 {
815 char *c;
816 unsigned char ch;
817 long count;
818 long len;
819
820 len = s->s_len;
821 count = 0;
822 c = s->s_str;
823 while (len-- > 0) {
824 ch = *c++;
825 while (ch) {
826 count += (ch & 1);
827 ch >>= 1;
828 }
829 }
830 return count;
831 }
832
833 long
stringhighbit(STRING * s)834 stringhighbit(STRING *s)
835 {
836 char *c;
837 unsigned char ch;
838 long i;
839
840 i = s->s_len;
841 c = s->s_str + i;
842 while (--i >= 0 && *--c == '\0');
843 if (i < 0)
844 return -1;
845 i <<= 3;
846 for (ch = *c; ch >>= 1; i++);
847 return i;
848 }
849
850 long
stringlowbit(STRING * s)851 stringlowbit(STRING *s)
852 {
853 char *c;
854 unsigned char ch;
855 long i;
856
857 for (i = s->s_len, c = s->s_str; i > 0 && *c == '\0'; i--, c++);
858 if (i == 0)
859 return -1;
860 i = (s->s_len - i) << 3;
861 for (ch = *c; !(ch & 1); ch >>= 1, i++);
862 return i;
863 }
864
865
866 /*
867 * stringcompare compares first len characters of strings starting at c1, c2
868 * Returns TRUE if and only if a difference is encountered.
869 * Essentially a local version of memcmp.
870 */
871 S_FUNC BOOL
stringcompare(char * c1,char * c2,long len)872 stringcompare(char *c1, char *c2, long len)
873 {
874 while (len-- > 0) {
875 if (*c1++ != *c2++)
876 return TRUE;
877 }
878 return FALSE;
879 }
880
881 /*
882 * stringcmp returns TRUE if strings differ, FALSE if strings equal
883 */
884 BOOL
stringcmp(STRING * s1,STRING * s2)885 stringcmp(STRING *s1, STRING *s2)
886 {
887 if (s1->s_len != s2->s_len)
888 return TRUE;
889 return stringcompare(s1->s_str, s2->s_str, s1->s_len);
890 }
891
892
893 /*
894 * stringrel returns 0 if strings are equal; otherwise 1 or -1 according
895 * as the greater of the first unequal characters are in the first or
896 * second string, or in the case of unequal-length strings when the compared
897 * characters are all equal, 1 or -1 according as the first or second string
898 * is longer.
899 */
900 FLAG
stringrel(STRING * s1,STRING * s2)901 stringrel(STRING *s1, STRING *s2)
902 {
903 char *c1, *c2;
904 long i1, i2;
905
906 if (s1 == s2)
907 return 0;
908
909 i1 = s1->s_len;
910 i2 = s2->s_len;
911 if (i2 == 0)
912 return (i1 > 0);
913 if (i1 == 0)
914 return -1;
915 c1 = s1->s_str;
916 c2 = s2->s_str;
917 while (i1 > 1 && i2 > 1 && *c1 == *c2) {
918 i1--;
919 i2--;
920 c1++;
921 c2++;
922 }
923 if ((unsigned char) *c1 > (unsigned char) *c2) return 1;
924 if ((unsigned char) *c1 < (unsigned char) *c2) return -1;
925 if (i1 < i2) return -1;
926 return (i1 > i2);
927 }
928
929 /* Case independent stringrel(STRING *s1, STRING *s2)
930 * stringcaserel returns 0 if strings are equal; otherwise 1 or -1 according
931 * as the greater of the first unequal characters are in the first or
932 * second string, or in the case of unequal-length strings when the compared
933 * characters are all equal, 1 or -1 according as the first or second string
934 * is longer.
935 */
936 FLAG
stringcaserel(STRING * s1,STRING * s2)937 stringcaserel(STRING *s1, STRING *s2)
938 {
939 char *c1, *c2;
940 long i1, i2;
941
942 if (s1 == s2)
943 return 0;
944
945 i1 = s1->s_len;
946 i2 = s2->s_len;
947 if (i2 == 0)
948 return (i1 > 0);
949 if (i1 == 0)
950 return -1;
951 c1 = s1->s_str;
952 c2 = s2->s_str;
953 while (i1 > 1 && i2 > 1 && tolower(*c1) == tolower(*c2)) {
954 i1--;
955 i2--;
956 c1++;
957 c2++;
958 }
959 if ( (tolower(*c1)) > (tolower(*c2)))
960 return 1;
961 if ( (tolower(*c1)) < (tolower(*c2)))
962 return -1;
963 if (i1 < i2) return -1;
964 return (i1 > i2);
965 }
966 /*
967 * str with characters c0, c1, ... is considered as a bitstream, 8 bits
968 * per character; within a character the bits ordered from low order to
969 * high order. For 0 <= i < 8 * length of str, stringbit returns 1 or 0
970 * according as the bit with index i is set or not set; other values of i
971 * return -1.
972 */
973 int
stringbit(STRING * s,long index)974 stringbit(STRING *s, long index)
975 {
976 unsigned int ch;
977 int res;
978
979 if (index < 0)
980 return -1;
981 res = index & 7;
982 index >>= 3;
983 if ((size_t)index >= s->s_len)
984 return -1;
985 ch = s->s_str[index];
986 return (ch >> res) & 1;
987 }
988
989
990 BOOL
stringtest(STRING * s)991 stringtest(STRING *s)
992 {
993 long i;
994 char *c;
995
996 i = s->s_len;
997 c = s->s_str;
998 while (i-- > 0) {
999 if (*c++)
1000 return TRUE;
1001 }
1002 return FALSE;
1003 }
1004
1005 /*
1006 * If index is in acceptable range, stringsetbit sets or resets specified
1007 * bit in string s according as val is TRUE or FALSE, and returns 0.
1008 * Returns 1 if index < 0; 2 if index too large.
1009 */
1010 int
stringsetbit(STRING * s,long index,BOOL val)1011 stringsetbit(STRING *s, long index, BOOL val)
1012 {
1013 char *c;
1014 int bit;
1015
1016 if (index < 0)
1017 return 1;
1018 bit = 1 << (index & 7);
1019 index >>= 3;
1020 if ((size_t)index >= s->s_len)
1021 return 2;
1022 c = &s->s_str[index];
1023 *c &= ~bit;
1024 if (val)
1025 *c |= bit;
1026 return 0;
1027 }
1028
1029 /*
1030 * stringsearch returns 0 and sets index = i if the first occurrence
1031 * of s2 in s1 for start <= i < end is at index i. If no such occurrence
1032 * is found, -1 is returned.
1033 */
1034 int
stringsearch(STRING * s1,STRING * s2,long start,long end,ZVALUE * index)1035 stringsearch(STRING *s1, STRING *s2, long start, long end, ZVALUE *index)
1036 {
1037 long len2, i, j;
1038 char *c1, *c2, *c;
1039 char ch;
1040
1041 len2 = s2->s_len;
1042 if (start < 0)
1043 start = 0;
1044 if (end < start + len2)
1045 return -1;
1046 if (len2 == 0) {
1047 itoz(start, index);
1048 return 0;
1049 }
1050 i = end - start - len2;
1051 c1 = s1->s_str + start;
1052 ch = *s2->s_str;
1053 while (i-- >= 0) {
1054 if (*c1++ == ch) {
1055 c = c1;
1056 c2 = s2->s_str;
1057 j = len2;
1058 while (--j > 0 && *c++ == *++c2);
1059 if (j == 0) {
1060 itoz(end - len2 - i - 1, index);
1061 return 0;
1062 }
1063 }
1064 }
1065 return -1;
1066 }
1067
1068 int
stringrsearch(STRING * s1,STRING * s2,long start,long end,ZVALUE * index)1069 stringrsearch(STRING *s1, STRING *s2, long start, long end, ZVALUE *index)
1070 {
1071 long len1, len2, i, j;
1072 char *c1, *c2, *c, *c2top;
1073 char ch;
1074
1075 len1 = s1->s_len;
1076 len2 = s2->s_len;
1077 if (start < 0)
1078 start = 0;
1079 if (end > len1)
1080 end = len1;
1081 if (end < start + len2)
1082 return -1;
1083 if (len2 == 0) {
1084 itoz(start, index);
1085 return 0;
1086 }
1087 i = end - start - len2 + 1;
1088 c1 = s1->s_str + end - 1;
1089 c2top = s2->s_str + len2 - 1;
1090 ch = *c2top;
1091
1092 while (--i >= 0) {
1093 if (*c1-- == ch) {
1094 c = c1;
1095 j = len2;
1096 c2 = c2top;
1097 while (--j > 0 && *c-- == *--c2);
1098 if (j == 0) {
1099 itoz(start + i, index);
1100 return 0;
1101 }
1102 }
1103 }
1104 return -1;
1105 }
1106
1107
1108 /*
1109 * String allocation routines
1110 */
1111
1112 #define STRALLOC 100
1113
1114
1115 STATIC STRING *freeStr = NULL;
1116 STATIC STRING **firstStrs = NULL;
1117 STATIC long blockcount = 0;
1118
1119
1120 STRING *
stralloc(void)1121 stralloc(void)
1122 {
1123 STRING *temp;
1124 STRING **newfn;
1125
1126 if (freeStr == NULL) {
1127 /* alloc + 1 guard paranoia */
1128 freeStr = (STRING *) malloc(sizeof (STRING) * (STRALLOC + 1));
1129 if (freeStr == NULL) {
1130 math_error("Unable to allocate memory for stralloc");
1131 /*NOTREACHED*/
1132 }
1133 /* guard paranoia */
1134 memset(freeStr+STRALLOC, 0, sizeof(STRING));
1135 freeStr[STRALLOC - 1].s_next = NULL;
1136 freeStr[STRALLOC - 1].s_links = 0;
1137
1138 /*
1139 * We prevent the temp pointer from walking behind freeStr
1140 * by stopping one short of the end and running the loop one
1141 * more time.
1142 *
1143 * We would stop the loop with just temp >= freeStr, but
1144 * doing this helps make code checkers such as insure happy.
1145 */
1146 for (temp = freeStr + STRALLOC - 2; temp > freeStr; --temp) {
1147 temp->s_next = temp + 1;
1148 temp->s_links = 0;
1149 }
1150 /* run the loop manually one last time */
1151 temp->s_next = temp + 1;
1152 temp->s_links = 0;
1153
1154 blockcount++;
1155 if (firstStrs == NULL) {
1156 /* alloc + 1 guard paranoia */
1157 newfn = (STRING **)
1158 malloc((blockcount + 1) * sizeof(STRING *));
1159 newfn[blockcount] = NULL; /* guard paranoia */
1160 } else {
1161 /* alloc + 1 guard paranoia */
1162 newfn = (STRING **)
1163 realloc(firstStrs,
1164 (blockcount + 1) * sizeof(STRING *));
1165 newfn[blockcount] = NULL; /* guard paranoia */
1166 }
1167 if (newfn == NULL) {
1168 math_error("Cannot allocate new string block");
1169 /*NOTREACHED*/
1170 }
1171 firstStrs = newfn;
1172 firstStrs[blockcount - 1] = freeStr;
1173 }
1174 temp = freeStr;
1175 freeStr = temp->s_next;
1176 temp->s_links = 1;
1177 temp->s_str = NULL;
1178 return temp;
1179 }
1180
1181
1182 /*
1183 * makestring to be called only when str is the result of a malloc
1184 */
1185 STRING *
makestring(char * str)1186 makestring(char *str)
1187 {
1188 STRING *s;
1189 size_t len;
1190
1191 len = strlen(str);
1192 s = stralloc();
1193 s->s_str = str;
1194 s->s_len = len;
1195 return s;
1196 }
1197
1198 STRING *
charstring(int ch)1199 charstring(int ch)
1200 {
1201 STRING *s;
1202 char *c;
1203
1204 c = (char *) malloc(2);
1205 if (c == NULL) {
1206 math_error("Allocation failure for charstring");
1207 /*NOTREACHED*/
1208 }
1209 s = stralloc();
1210 s->s_len = 1;
1211 s->s_str = c;
1212 *c++ = (char) ch;
1213 *c = '\0';
1214 return s;
1215 }
1216
1217
1218 /*
1219 * makenewstring creates a new string by copying null-terminated str;
1220 * str is not freed
1221 */
1222 STRING *
makenewstring(char * str)1223 makenewstring(char *str)
1224 {
1225 STRING *s;
1226 char *c;
1227 size_t len;
1228
1229 len = strlen(str);
1230 if (len == 0)
1231 return slink(&_nullstring_);
1232 c = (char *) malloc(len + 1);
1233 if (c == NULL) {
1234 math_error("malloc for makenewstring failed");
1235 /*NOTREACHED*/
1236 }
1237 s = stralloc();
1238 s->s_str = c;
1239 s->s_len = len;
1240 memcpy(c, str, len);
1241 c[len] = '\0';
1242 return s;
1243 }
1244
1245
1246 STRING *
stringcopy(STRING * s1)1247 stringcopy (STRING *s1)
1248 {
1249 STRING *s;
1250 char *c;
1251 long len;
1252
1253 len = s1->s_len;
1254 if (len == 0)
1255 return slink(s1);
1256 c = malloc(len + 1);
1257 if (c == NULL) {
1258 math_error("Malloc failed for stringcopy");
1259 /*NOTREACHED*/
1260 }
1261 s = stralloc();
1262 s->s_len = len;
1263 s->s_str = c;
1264 memcpy(c, s1->s_str, len);
1265 c[len] = '\0';
1266 return s;
1267 }
1268
1269
1270 STRING *
slink(STRING * s)1271 slink(STRING *s)
1272 {
1273 if (s->s_links <= 0) {
1274 math_error("Argument for slink has non-positive links!!!");
1275 /*NOTREACHED*/
1276 }
1277 ++s->s_links;
1278 return s;
1279 }
1280
1281
1282 void
sfree(STRING * s)1283 sfree(STRING *s)
1284 {
1285 if (s->s_links <= 0) {
1286 math_error("Argument for sfree has non-positive links!!!");
1287 /*NOTREACHED*/
1288 }
1289 if (--s->s_links > 0 || s->s_len == 0)
1290 return;
1291 free(s->s_str);
1292 s->s_next = freeStr;
1293 freeStr = s;
1294 }
1295
1296 STATIC long stringconstcount = 0;
1297 STATIC long stringconstavail = 0;
1298 STATIC STRING **stringconsttable;
1299 #define STRCONSTALLOC 100
1300
1301 void
initstrings(void)1302 initstrings(void)
1303 {
1304 /* alloc + 1 guard paranoia */
1305 stringconsttable = (STRING **)
1306 malloc(sizeof(STRING *) * (STRCONSTALLOC + 1));
1307 if (stringconsttable == NULL) {
1308 math_error("Unable to allocate constant table");
1309 /*NOTREACHED*/
1310 }
1311 stringconsttable[STRCONSTALLOC] = NULL; /* guard paranoia */
1312 stringconsttable[0] = &_nullstring_;
1313 stringconstcount = 1;
1314 stringconstavail = STRCONSTALLOC - 1;
1315 }
1316
1317 /*
1318 * addstring is called only from token.c
1319 * When called, len is length of string including '\0'
1320 */
1321 long
addstring(char * str,size_t len)1322 addstring(char *str, size_t len)
1323 {
1324 STRING **sp;
1325 STRING *s;
1326 char *c;
1327 long index; /* index into constant table */
1328 long first; /* first non-null position found */
1329 BOOL havefirst;
1330
1331 if (len < 1) {
1332 math_error("addstring length including trailing NUL < 1");
1333 }
1334 if (stringconstavail <= 0) {
1335 if (stringconsttable == NULL) {
1336 initstrings();
1337 } else {
1338 /* alloc + 1 guard paranoia */
1339 sp = (STRING **)
1340 realloc((char *) stringconsttable,
1341 sizeof(STRING *) *
1342 (stringconstcount + STRCONSTALLOC + 1));
1343 if (sp == NULL) {
1344 math_error("Unable to reallocate string "
1345 "const table");
1346 /*NOTREACHED*/
1347 }
1348 /* guard paranoia */
1349 sp[stringconstcount + STRCONSTALLOC] = NULL;
1350 stringconsttable = sp;
1351 stringconstavail = STRCONSTALLOC;
1352 }
1353 }
1354 len--;
1355 first = 0;
1356 havefirst = FALSE;
1357 sp = stringconsttable;
1358 for (index = 0; index < stringconstcount; index++, sp++) {
1359 s = *sp;
1360 if (s->s_links == 0) {
1361 if (!havefirst) {
1362 havefirst = TRUE;
1363 first = index;
1364 }
1365 continue;
1366 }
1367 if (s->s_len == len && stringcompare(s->s_str, str, len) == 0) {
1368 s->s_links++;
1369 return index;
1370 }
1371 }
1372 s = stralloc();
1373 c = (char *) malloc(len + 1);
1374 if (c == NULL) {
1375 math_error("Unable to allocate string constant memory");
1376 /*NOTREACHED*/
1377 }
1378 s->s_str = c;
1379 s->s_len = len;
1380 memcpy(s->s_str, str, len+1);
1381 if (havefirst) {
1382 stringconsttable[first] = s;
1383 return first;
1384 }
1385 stringconstavail--;
1386 stringconsttable[stringconstcount++] = s;
1387 return index;
1388 }
1389
1390
1391 STRING *
findstring(long index)1392 findstring(long index)
1393 {
1394 if (index < 0 || index >= stringconstcount) {
1395 math_error("Bad index for findstring");
1396 /*NOTREACHED*/
1397 }
1398 return stringconsttable[index];
1399 }
1400
1401
1402 void
freestringconstant(long index)1403 freestringconstant(long index)
1404 {
1405 STRING *s;
1406 STRING **sp;
1407
1408 if (index >= 0) {
1409 s = findstring(index);
1410 sfree(s);
1411 if (index == stringconstcount - 1) {
1412 sp = &stringconsttable[index];
1413 while (stringconstcount > 0 && (*sp)->s_links == 0) {
1414 stringconstcount--;
1415 stringconstavail++;
1416 sp--;
1417 }
1418 }
1419 }
1420 }
1421
1422 long
printechar(char * c)1423 printechar(char *c)
1424 {
1425 unsigned char ch, cc;
1426 unsigned char ech; /* for escape sequence */
1427
1428 ch = *c;
1429 if (ch >= ' ' && ch < 127 && ch != '\\' && ch != '\"' && ch != '\'') {
1430 math_chr(ch);
1431 return 1;
1432 }
1433 math_chr('\\');
1434 ech = 0;
1435 switch (ch) {
1436 case '\a': ech = 'a'; break;
1437 case '\b': ech = 'b'; break;
1438 case '\f': ech = 'f'; break;
1439 case '\n': ech = 'n'; break;
1440 case '\r': ech = 'r'; break;
1441 case '\t': ech = 't'; break;
1442 case '\v': ech = 'v'; break;
1443 case '\\': ech = '\\'; break;
1444 case '\"': ech = '\"'; break;
1445 case '\'': ech = '\''; break;
1446 case 0: ech = '0'; break;
1447 case 27: ech = 'e'; break;
1448 }
1449 if (ech == '0') {
1450 cc = *(c + 1);
1451 if (cc >= '0' && cc < '8') {
1452 math_str("000");
1453 return 4;
1454 }
1455 }
1456 if (ech) {
1457 math_chr(ech);
1458 return 2;
1459 }
1460 math_chr('x');
1461 cc = ch / 16;
1462 math_chr((cc < 10) ? '0' + cc : 87 + cc);
1463 cc = ch % 16;
1464 math_chr((cc < 10) ? '0' + cc : 87 + cc);
1465 return 4;
1466 }
1467
1468
1469 void
fitstring(char * str,long len,long width)1470 fitstring(char *str, long len, long width)
1471 {
1472 long i, j, n, max;
1473 char *c;
1474 unsigned char ch, nch;
1475
1476 max = (width - 3)/2;
1477 if (len == 0)
1478 return;
1479 c = str;
1480 for (i = 0, n = 0; i < len && n < max; i++) {
1481 n += printechar(c++);
1482 }
1483 if (i >= len)
1484 return;
1485 c = str + len;
1486 nch = '\0';
1487 for (n = 0, j = len ; j > i && n < max ; --j, nch = ch) {
1488 ch = *--c;
1489 n++;
1490 if (ch >= ' ' && ch <= 127 && ch != '\\' && ch != '\"')
1491 continue;
1492 n++;
1493 switch (ch) {
1494 case '\a':
1495 case '\b':
1496 case '\f':
1497 case '\n':
1498 case '\r':
1499 case '\t':
1500 case '\v':
1501 case '\\':
1502 case '\"':
1503 case '\'':
1504 case 27:
1505 continue;
1506 }
1507 if (ch >= 64 || (nch >= '0' && nch <= '7')) {
1508 n += 2;
1509 continue;
1510 }
1511 if (ch >= 8)
1512 n++;
1513 }
1514 if (j > i)
1515 math_str("...");
1516 while (j++ < len)
1517 (void) printechar(c++);
1518 }
1519
1520 void
strprint(STRING * str)1521 strprint(STRING *str) {
1522 long n;
1523 char *c;
1524
1525 c = str->s_str;
1526 n = str->s_len;
1527
1528 while (n-- > 0)
1529 (void) printechar(c++);
1530 }
1531
1532 void
showstrings(void)1533 showstrings(void)
1534 {
1535 STRING *sp;
1536 long i, j, k;
1537 long count;
1538
1539
1540 printf("Index Links Length String\n");
1541 printf("----- ----- ------ ------\n");
1542 sp = &_nullstring_;
1543 printf(" 0 %5ld 0 \"\"\n", sp->s_links);
1544 for (i = 0, k = 1, count = 1; i < blockcount; i++) {
1545 sp = firstStrs[i];
1546 for (j = 0; j < STRALLOC; j++, k++, sp++) {
1547 if (sp->s_links > 0) {
1548 ++count;
1549 printf("%5ld %5ld %6ld \"",
1550 k, sp->s_links, (long int)sp->s_len);
1551 fitstring(sp->s_str, sp->s_len, 50);
1552 printf("\"\n");
1553 }
1554 }
1555 }
1556 printf("\nNumber: %ld\n", count);
1557 }
1558
1559
1560 void
showliterals(void)1561 showliterals(void)
1562 {
1563 STRING *sp;
1564 long i;
1565 long count = 0;
1566
1567
1568 printf("Index Links Length String\n");
1569 printf("----- ----- ------ ------\n");
1570 for (i = 0; i < stringconstcount; i++) {
1571 sp = stringconsttable[i];
1572 if (sp->s_links > 0) {
1573 ++count;
1574 printf("%5ld %5ld %6ld \"",
1575 i, sp->s_links, (long int)sp->s_len);
1576 fitstring(sp->s_str, sp->s_len, 50);
1577 printf("\"\n");
1578 }
1579
1580 }
1581 printf("\nNumber: %ld\n", count);
1582 }
1583