1 /* $NetBSD: util.c,v 1.2 2017/04/18 04:35:18 maya Exp $ */ 2 3 /* 4 * Copyright (C) 1991-1994, 1997, 2006, 2008, 2012-2017 Free Software Foundation, Inc. 5 * Copyright (C) 2016-2017 Philip A. Nelson. 6 * All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 2. Redistributions in binary form must reproduce the above copyright 15 * notice, this list of conditions and the following disclaimer in the 16 * documentation and/or other materials provided with the distribution. 17 * 3. The names Philip A. Nelson and Free Software Foundation may not be 18 * used to endorse or promote products derived from this software 19 * without specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY PHILIP A. NELSON ``AS IS'' AND ANY EXPRESS OR 22 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 23 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 24 * IN NO EVENT SHALL PHILIP A. NELSON OR THE FREE SOFTWARE FOUNDATION BE 25 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 26 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 27 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 28 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 29 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 30 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF 31 * THE POSSIBILITY OF SUCH DAMAGE. 32 */ 33 34 /* util.c: Utility routines for bc. */ 35 36 #include "bcdefs.h" 37 #ifndef VARARGS 38 #include <stdarg.h> 39 #else 40 #include <varargs.h> 41 #endif 42 #include "proto.h" 43 44 45 /* strcopyof mallocs new memory and copies a string to to the new 46 memory. */ 47 48 char * 49 strcopyof (const char *str) 50 { 51 char *temp; 52 53 temp = bc_malloc (strlen (str)+1); 54 return (strcpy (temp,str)); 55 } 56 57 58 /* nextarg adds another value to the list of arguments. */ 59 60 arg_list * 61 nextarg (arg_list *args, int val, int is_var) 62 { arg_list *temp; 63 64 temp = bc_malloc (sizeof (arg_list)); 65 temp->av_name = val; 66 temp->arg_is_var = is_var; 67 temp->next = args; 68 69 return (temp); 70 } 71 72 73 /* For generate, we must produce a string in the form 74 "val,val,...,val". We also need a couple of static variables 75 for retaining old generated strings. It also uses a recursive 76 function that builds the string. */ 77 78 static char *arglist1 = NULL, *arglist2 = NULL; 79 80 81 /* make_arg_str does the actual construction of the argument string. 82 ARGS is the pointer to the list and LEN is the maximum number of 83 characters needed. 1 char is the minimum needed. 84 */ 85 86 static char *make_arg_str (arg_list *args, int len); 87 88 static char * 89 make_arg_str (arg_list *args, int len) 90 { 91 char *temp; 92 char sval[30]; 93 94 /* Recursive call. */ 95 if (args != NULL) 96 temp = make_arg_str (args->next, len+12); 97 else 98 { 99 temp = bc_malloc (len); 100 *temp = 0; 101 return temp; 102 } 103 104 /* Add the current number to the end of the string. */ 105 if (args->arg_is_var) 106 if (len != 1) 107 snprintf (sval, sizeof(sval), "*%d,", args->av_name); 108 else 109 snprintf (sval, sizeof(sval), "*%d", args->av_name); 110 else 111 if (len != 1) 112 snprintf (sval, sizeof(sval), "%d,", args->av_name); 113 else 114 snprintf (sval, sizeof(sval), "%d", args->av_name); 115 temp = strcat (temp, sval); 116 return (temp); 117 } 118 119 char * 120 arg_str (arg_list *args) 121 { 122 if (arglist2 != NULL) 123 free (arglist2); 124 arglist2 = arglist1; 125 arglist1 = make_arg_str (args, 1); 126 return (arglist1); 127 } 128 129 char * 130 call_str (arg_list *args) 131 { 132 arg_list *temp; 133 int arg_count; 134 int ix; 135 136 if (arglist2 != NULL) 137 free (arglist2); 138 arglist2 = arglist1; 139 140 /* Count the number of args and add the 0's and 1's. */ 141 for (temp = args, arg_count = 0; temp != NULL; temp = temp->next) 142 arg_count++; 143 arglist1 = bc_malloc(arg_count+1); 144 for (temp = args, ix=0; temp != NULL; temp = temp->next) 145 arglist1[ix++] = ( temp->av_name ? '1' : '0'); 146 arglist1[ix] = 0; 147 148 return (arglist1); 149 } 150 151 /* free_args frees an argument list ARGS. */ 152 153 void 154 free_args (arg_list *args) 155 { 156 arg_list *temp; 157 158 temp = args; 159 while (temp != NULL) 160 { 161 args = args->next; 162 free (temp); 163 temp = args; 164 } 165 } 166 167 168 /* Check for valid parameter (PARAMS) and auto (AUTOS) lists. 169 There must be no duplicates any where. Also, this is where 170 warnings are generated for array parameters. */ 171 172 void 173 check_params (arg_list *params, arg_list *autos) 174 { 175 arg_list *tmp1, *tmp2; 176 177 /* Check for duplicate parameters. */ 178 if (params != NULL) 179 { 180 tmp1 = params; 181 while (tmp1 != NULL) 182 { 183 tmp2 = tmp1->next; 184 while (tmp2 != NULL) 185 { 186 if (tmp2->av_name == tmp1->av_name) 187 yyerror ("duplicate parameter names"); 188 tmp2 = tmp2->next; 189 } 190 if (tmp1->arg_is_var) 191 ct_warn ("Variable array parameter"); 192 tmp1 = tmp1->next; 193 } 194 } 195 196 /* Check for duplicate autos. */ 197 if (autos != NULL) 198 { 199 tmp1 = autos; 200 while (tmp1 != NULL) 201 { 202 tmp2 = tmp1->next; 203 while (tmp2 != NULL) 204 { 205 if (tmp2->av_name == tmp1->av_name) 206 yyerror ("duplicate auto variable names"); 207 tmp2 = tmp2->next; 208 } 209 if (tmp1->arg_is_var) 210 yyerror ("* not allowed here"); 211 tmp1 = tmp1->next; 212 } 213 } 214 215 /* Check for duplicate between parameters and autos. */ 216 if ((params != NULL) && (autos != NULL)) 217 { 218 tmp1 = params; 219 while (tmp1 != NULL) 220 { 221 tmp2 = autos; 222 while (tmp2 != NULL) 223 { 224 if (tmp2->av_name == tmp1->av_name) 225 yyerror ("variable in both parameter and auto lists"); 226 tmp2 = tmp2->next; 227 } 228 tmp1 = tmp1->next; 229 } 230 } 231 } 232 233 /* genstr management to avoid buffer overflow. */ 234 void 235 set_genstr_size (int size) 236 { 237 if (size > genlen) { 238 if (genstr != NULL) 239 free(genstr); 240 genstr = bc_malloc (size); 241 genlen = size; 242 } 243 } 244 245 246 /* Initialize the code generator the parser. */ 247 248 void 249 init_gen (void) 250 { 251 /* Get things ready. */ 252 break_label = 0; 253 continue_label = 0; 254 next_label = 1; 255 out_count = 2; 256 if (compile_only) 257 printf ("@i"); 258 else 259 init_load (); 260 had_error = FALSE; 261 did_gen = FALSE; 262 set_genstr_size (64); 263 } 264 265 266 /* generate code STR for the machine. */ 267 268 void 269 generate (const char *str) 270 { 271 did_gen = TRUE; 272 if (compile_only) 273 { 274 printf ("%s",str); 275 out_count += strlen(str); 276 if (out_count > 60) 277 { 278 printf ("\n"); 279 out_count = 0; 280 } 281 } 282 else 283 load_code (str); 284 } 285 286 287 /* Execute the current code as loaded. */ 288 289 void 290 run_code(void) 291 { 292 /* If no compile errors run the current code. */ 293 if (!had_error && did_gen) 294 { 295 if (compile_only) 296 { 297 printf ("@r\n"); 298 out_count = 0; 299 } 300 else 301 execute (); 302 } 303 304 /* Reinitialize the code generation and machine. */ 305 if (did_gen) 306 init_gen(); 307 else 308 had_error = FALSE; 309 } 310 311 312 /* Output routines: Write a character CH to the standard output. 313 It keeps track of the number of characters output and may 314 break the output with a "\<cr>". Always used for numbers. */ 315 316 void 317 out_char (int ch) 318 { 319 if (ch == '\n') 320 { 321 out_col = 0; 322 putchar ('\n'); 323 } 324 else 325 { 326 out_col++; 327 if (out_col == line_size-1 && line_size != 0) 328 { 329 putchar ('\\'); 330 putchar ('\n'); 331 out_col = 1; 332 } 333 putchar (ch); 334 } 335 } 336 337 /* Output routines: Write a character CH to the standard output. 338 It keeps track of the number of characters output and may 339 break the output with a "\<cr>". This one is for strings. 340 In POSIX bc, strings are not broken across lines. */ 341 342 void 343 out_schar (int ch) 344 { 345 if (ch == '\n') 346 { 347 out_col = 0; 348 putchar ('\n'); 349 } 350 else 351 { 352 if (!std_only) 353 { 354 out_col++; 355 if (out_col == line_size-1 && line_size != 0) 356 { 357 putchar ('\\'); 358 putchar ('\n'); 359 out_col = 1; 360 } 361 } 362 putchar (ch); 363 } 364 } 365 366 367 /* The following are "Symbol Table" routines for the parser. */ 368 369 /* find_id returns a pointer to node in TREE that has the correct 370 ID. If there is no node in TREE with ID, NULL is returned. */ 371 372 id_rec * 373 find_id (id_rec *tree, const char *id) 374 { 375 int cmp_result; 376 377 /* Check for an empty tree. */ 378 if (tree == NULL) 379 return NULL; 380 381 /* Recursively search the tree. */ 382 cmp_result = strcmp (id, tree->id); 383 if (cmp_result == 0) 384 return tree; /* This is the item. */ 385 else if (cmp_result < 0) 386 return find_id (tree->left, id); 387 else 388 return find_id (tree->right, id); 389 } 390 391 392 /* insert_id_rec inserts a NEW_ID rec into the tree whose ROOT is 393 provided. insert_id_rec returns TRUE if the tree height from 394 ROOT down is increased otherwise it returns FALSE. This is a 395 recursive balanced binary tree insertion algorithm. */ 396 397 int insert_id_rec (id_rec **root, id_rec *new_id) 398 { 399 id_rec *A, *B; 400 401 /* If root is NULL, this where it is to be inserted. */ 402 if (*root == NULL) 403 { 404 *root = new_id; 405 new_id->left = NULL; 406 new_id->right = NULL; 407 new_id->balance = 0; 408 return (TRUE); 409 } 410 411 /* We need to search for a leaf. */ 412 if (strcmp (new_id->id, (*root)->id) < 0) 413 { 414 /* Insert it on the left. */ 415 if (insert_id_rec (&((*root)->left), new_id)) 416 { 417 /* The height increased. */ 418 (*root)->balance --; 419 420 switch ((*root)->balance) 421 { 422 case 0: /* no height increase. */ 423 return (FALSE); 424 case -1: /* height increase. */ 425 return (TRUE); 426 case -2: /* we need to do a rebalancing act. */ 427 A = *root; 428 B = (*root)->left; 429 if (B->balance <= 0) 430 { 431 /* Single Rotate. */ 432 A->left = B->right; 433 B->right = A; 434 *root = B; 435 A->balance = 0; 436 B->balance = 0; 437 } 438 else 439 { 440 /* Double Rotate. */ 441 *root = B->right; 442 B->right = (*root)->left; 443 A->left = (*root)->right; 444 (*root)->left = B; 445 (*root)->right = A; 446 switch ((*root)->balance) 447 { 448 case -1: 449 A->balance = 1; 450 B->balance = 0; 451 break; 452 case 0: 453 A->balance = 0; 454 B->balance = 0; 455 break; 456 case 1: 457 A->balance = 0; 458 B->balance = -1; 459 break; 460 } 461 (*root)->balance = 0; 462 } 463 } 464 } 465 } 466 else 467 { 468 /* Insert it on the right. */ 469 if (insert_id_rec (&((*root)->right), new_id)) 470 { 471 /* The height increased. */ 472 (*root)->balance ++; 473 474 switch ((*root)->balance) 475 { 476 case 0: /* no height increase. */ 477 return (FALSE); 478 case 1: /* height increase. */ 479 return (TRUE); 480 case 2: /* we need to do a rebalancing act. */ 481 A = *root; 482 B = (*root)->right; 483 if (B->balance >= 0) 484 { 485 /* Single Rotate. */ 486 A->right = B->left; 487 B->left = A; 488 *root = B; 489 A->balance = 0; 490 B->balance = 0; 491 } 492 else 493 { 494 /* Double Rotate. */ 495 *root = B->left; 496 B->left = (*root)->right; 497 A->right = (*root)->left; 498 (*root)->left = A; 499 (*root)->right = B; 500 switch ((*root)->balance) 501 { 502 case -1: 503 A->balance = 0; 504 B->balance = 1; 505 break; 506 case 0: 507 A->balance = 0; 508 B->balance = 0; 509 break; 510 case 1: 511 A->balance = -1; 512 B->balance = 0; 513 break; 514 } 515 (*root)->balance = 0; 516 } 517 } 518 } 519 } 520 521 /* If we fall through to here, the tree did not grow in height. */ 522 return (FALSE); 523 } 524 525 526 /* Initialize variables for the symbol table tree. */ 527 528 void 529 init_tree(void) 530 { 531 name_tree = NULL; 532 next_array = 1; 533 next_func = 1; 534 /* 0 => ibase, 1 => obase, 2 => scale, 3 => history, 4 => last. */ 535 next_var = 5; 536 } 537 538 539 /* Lookup routines for symbol table names. */ 540 541 int 542 lookup (char *name, int namekind) 543 { 544 id_rec *id; 545 546 /* Warn about non-standard name. */ 547 if (strlen(name) != 1) 548 ct_warn ("multiple letter name - %s", name); 549 550 /* Look for the id. */ 551 id = find_id (name_tree, name); 552 if (id == NULL) 553 { 554 /* We need to make a new item. */ 555 id = bc_malloc (sizeof (id_rec)); 556 id->id = strcopyof (name); 557 id->a_name = 0; 558 id->f_name = 0; 559 id->v_name = 0; 560 insert_id_rec (&name_tree, id); 561 } 562 563 /* Return the correct value. */ 564 switch (namekind) 565 { 566 567 case ARRAY: 568 /* ARRAY variable numbers are returned as negative numbers. */ 569 if (id->a_name != 0) 570 { 571 free (name); 572 return (-id->a_name); 573 } 574 id->a_name = next_array++; 575 if (id->a_name < MAX_STORE) 576 { 577 if (id->a_name >= a_count) 578 more_arrays (); 579 a_names[id->a_name] = name; 580 return (-id->a_name); 581 } 582 yyerror ("Too many array variables"); 583 bc_exit (1); 584 /*NOTREACHED*/ 585 586 case FUNCT: 587 case FUNCTDEF: 588 if (id->f_name != 0) 589 { 590 free(name); 591 /* Check to see if we are redefining a math lib function. */ 592 if (use_math && namekind == FUNCTDEF && id->f_name <= 6) 593 id->f_name = next_func++; 594 return (id->f_name); 595 } 596 id->f_name = next_func++; 597 if (id->f_name < MAX_STORE) 598 { 599 if (id->f_name >= f_count) 600 more_functions (); 601 f_names[id->f_name] = name; 602 return (id->f_name); 603 } 604 yyerror ("Too many functions"); 605 bc_exit (1); 606 /*NOTREACHED*/ 607 608 case SIMPLE: 609 if (id->v_name != 0) 610 { 611 free(name); 612 return (id->v_name); 613 } 614 id->v_name = next_var++; 615 if (id->v_name <= MAX_STORE) 616 { 617 if (id->v_name >= v_count) 618 more_variables (); 619 v_names[id->v_name - 1] = name; 620 return (id->v_name); 621 } 622 yyerror ("Too many variables"); 623 bc_exit (1); 624 /*NOTREACHED*/ 625 626 } 627 628 yyerror ("End of util.c/lookup() reached. Please report this bug."); 629 bc_exit (1); 630 /*NOTREACHED*/ 631 } 632 633 /* Print out the limits of this program. */ 634 635 void 636 limits(void) 637 { 638 printf ("BC_BASE_MAX = %d\n", BC_BASE_MAX); 639 printf ("BC_DIM_MAX = %ld\n", (long) BC_DIM_MAX); 640 printf ("BC_SCALE_MAX = %d\n", BC_SCALE_MAX); 641 printf ("BC_STRING_MAX = %d\n", BC_STRING_MAX); 642 printf ("MAX Exponent = %ld\n", (long) LONG_MAX); 643 printf ("Number of vars = %ld\n", (long) MAX_STORE); 644 #ifdef OLD_EQ_OP 645 printf ("Old assignment operatiors are valid. (=-, =+, ...)\n"); 646 #endif 647 } 648 649 /* bc_malloc will check the return value so all other places do not 650 have to do it! SIZE is the number of bytes to allocate. */ 651 652 void * 653 bc_malloc (size_t size) 654 { 655 void *ptr; 656 657 ptr = (void *) malloc (size); 658 if (ptr == NULL) 659 out_of_memory (); 660 661 return ptr; 662 } 663 664 665 /* The following routines are error routines for various problems. */ 666 667 /* Malloc could not get enought memory. */ 668 669 void 670 out_of_memory(void) 671 { 672 fprintf (stderr, "Fatal error: Out of memory for malloc.\n"); 673 bc_exit (1); 674 /*NOTREACHED*/ 675 } 676 677 678 679 /* The standard yyerror routine. Built with variable number of argumnets. */ 680 681 #ifndef VARARGS 682 #ifdef __STDC__ 683 void 684 yyerror (const char *str, ...) 685 #else 686 void 687 yyerror (str) 688 const char *str; 689 #endif 690 #else 691 void 692 yyerror (str, va_alist) 693 const char *str; 694 #endif 695 { 696 const char *name; 697 va_list args; 698 699 #ifndef VARARGS 700 va_start (args, str); 701 #else 702 va_start (args); 703 #endif 704 if (is_std_in) 705 name = "(standard_in)"; 706 else 707 name = file_name; 708 fprintf (stderr,"%s %d: ",name,line_no); 709 vfprintf (stderr, str, args); 710 fprintf (stderr, "\n"); 711 had_error = TRUE; 712 va_end (args); 713 } 714 715 716 /* The routine to produce warnings about non-standard features 717 found during parsing. */ 718 719 #ifndef VARARGS 720 #ifdef __STDC__ 721 void 722 ct_warn (const char *mesg, ...) 723 #else 724 void 725 ct_warn (mesg) 726 const char *mesg; 727 #endif 728 #else 729 void 730 ct_warn (mesg, va_alist) 731 const char *mesg; 732 #endif 733 { 734 const char *name; 735 va_list args; 736 737 #ifndef VARARGS 738 va_start (args, mesg); 739 #else 740 va_start (args); 741 #endif 742 if (std_only) 743 { 744 if (is_std_in) 745 name = "(standard_in)"; 746 else 747 name = file_name; 748 fprintf (stderr,"%s %d: Error: ",name,line_no); 749 vfprintf (stderr, mesg, args); 750 fprintf (stderr, "\n"); 751 had_error = TRUE; 752 } 753 else 754 if (warn_not_std) 755 { 756 if (is_std_in) 757 name = "(standard_in)"; 758 else 759 name = file_name; 760 fprintf (stderr,"%s %d: (Warning) ",name,line_no); 761 vfprintf (stderr, mesg, args); 762 fprintf (stderr, "\n"); 763 } 764 va_end (args); 765 } 766 767 /* Runtime error will print a message and stop the machine. */ 768 769 #ifndef VARARGS 770 #ifdef __STDC__ 771 void 772 rt_error (const char *mesg, ...) 773 #else 774 void 775 rt_error (mesg) 776 const char *mesg; 777 #endif 778 #else 779 void 780 rt_error (mesg, va_alist) 781 const char *mesg; 782 #endif 783 { 784 va_list args; 785 786 fprintf (stderr, "Runtime error (func=%s, adr=%d): ", 787 f_names[pc.pc_func], pc.pc_addr); 788 #ifndef VARARGS 789 va_start (args, mesg); 790 #else 791 va_start (args); 792 #endif 793 vfprintf (stderr, mesg, args); 794 va_end (args); 795 796 fprintf (stderr, "\n"); 797 runtime_error = TRUE; 798 } 799 800 801 /* A runtime warning tells of some action taken by the processor that 802 may change the program execution but was not enough of a problem 803 to stop the execution. */ 804 805 #ifndef VARARGS 806 #ifdef __STDC__ 807 void 808 rt_warn (const char *mesg, ...) 809 #else 810 void 811 rt_warn (const char *mesg) 812 #endif 813 #else 814 void 815 rt_warn (const char *mesg) 816 #endif 817 { 818 va_list args; 819 820 fprintf (stderr, "Runtime warning (func=%s, adr=%d): ", 821 f_names[pc.pc_func], pc.pc_addr); 822 #ifndef VARARGS 823 va_start (args, mesg); 824 #else 825 va_start (args); 826 #endif 827 vfprintf (stderr, mesg, args); 828 va_end (args); 829 830 fprintf (stderr, "\n"); 831 } 832 833 /* bc_exit: Make sure to reset the edit state. */ 834 835 void bc_exit(int val) 836 { 837 #if defined(LIBEDIT) 838 if (edit != NULL) 839 el_end(edit); 840 #endif 841 exit(val); 842 /*NOTREACHED*/ 843 } 844