Index: head/usr.bin/bc/bc.y =================================================================== --- head/usr.bin/bc/bc.y (revision 314703) +++ head/usr.bin/bc/bc.y (revision 314704) @@ -1,1216 +1,1216 @@ %{ -/* $OpenBSD: bc.y,v 1.44 2013/11/20 21:33:54 deraadt Exp $ */ +/* $OpenBSD: bc.y,v 1.46 2014/10/14 15:35:18 deraadt Exp $ */ /* * Copyright (c) 2003, Otto Moerbeek * * Permission to use, copy, modify, and distribute this software for any * purpose with or without fee is hereby granted, provided that the above * copyright notice and this permission notice appear in all copies. * * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ /* * This implementation of bc(1) uses concepts from the original 4.4 * BSD bc(1). The code itself is a complete rewrite, based on the * Posix defined bc(1) grammar. Other differences include type safe * usage of pointers to build the tree of emitted code, typed yacc * rule values, dynamic allocation of all data structures and a * completely rewritten lexical analyzer using lex(1). * * Some effort has been made to make sure that the generated code is * the same as the code generated by the older version, to provide * easy regression testing. */ #include __FBSDID("$FreeBSD$"); #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include "extern.h" #include "pathnames.h" #define BC_VER "1.1-FreeBSD" #define END_NODE ((ssize_t) -1) #define CONST_STRING ((ssize_t) -2) #define ALLOC_STRING ((ssize_t) -3) extern char *yytext; extern FILE *yyin; struct tree { union { char *astr; const char *cstr; } u; ssize_t index; }; int yywrap(void); int fileindex; int sargc; const char **sargv; const char *filename; char *cmdexpr; static void grow(void); static ssize_t cs(const char *); static ssize_t as(const char *); static ssize_t node(ssize_t, ...); static void emit(ssize_t, int); static void emit_macro(int, ssize_t); static void free_tree(void); static ssize_t numnode(int); static ssize_t lookup(char *, size_t, char); static ssize_t letter_node(char *); static ssize_t array_node(char *); static ssize_t function_node(char *); static void add_par(ssize_t); static void add_local(ssize_t); static void warning(const char *); static void init(void); static void usage(void); static char *escape(const char *); static ssize_t instr_sz = 0; static struct tree *instructions = NULL; static ssize_t current = 0; static int macro_char = '0'; static int reset_macro_char = '0'; static int nesting = 0; static int breakstack[16]; static int breaksp = 0; static ssize_t prologue; static ssize_t epilogue; static bool st_has_continue; static char str_table[UCHAR_MAX][2]; static bool do_fork = true; static u_short var_count; static pid_t dc; static void sigchld(int); extern char *__progname; #define BREAKSTACK_SZ (sizeof(breakstack)/sizeof(breakstack[0])) /* These values are 4.4BSD bc compatible */ #define FUNC_CHAR 0x01 #define ARRAY_CHAR 0xa1 /* Skip '\0', [, \ and ] */ #define ENCODE(c) ((c) < '[' ? (c) : (c) + 3); #define VAR_BASE (256-4) #define MAX_VARIABLES (VAR_BASE * VAR_BASE) const struct option long_options[] = { {"expression", required_argument, NULL, 'e'}, {"help", no_argument, NULL, 'h'}, {"mathlib", no_argument, NULL, 'l'}, /* compatibility option */ {"quiet", no_argument, NULL, 'q'}, {"version", no_argument, NULL, 'v'}, {NULL, no_argument, NULL, 0} }; %} %start program %union { struct lvalue lvalue; const char *str; char *astr; ssize_t node; } %token COMMA SEMICOLON LPAR RPAR LBRACE RBRACE LBRACKET RBRACKET DOT %token NEWLINE %token LETTER %token NUMBER STRING %token DEFINE BREAK QUIT LENGTH %token RETURN FOR IF WHILE SQRT %token SCALE IBASE OBASE AUTO %token CONTINUE ELSE PRINT %left BOOL_OR %left BOOL_AND %nonassoc BOOL_NOT %nonassoc EQUALS LESS_EQ GREATER_EQ UNEQUALS LESS GREATER %right ASSIGN_OP %left PLUS MINUS %left MULTIPLY DIVIDE REMAINDER %right EXPONENT %nonassoc UMINUS %nonassoc INCR DECR %type named_expression %type argument_list %type alloc_macro %type expression %type function %type function_header %type input_item %type opt_argument_list %type opt_expression %type opt_relational_expression %type opt_statement %type print_expression %type print_expression_list %type relational_expression %type return_expression %type semicolon_list %type statement %type statement_list %% program : /* empty */ | program input_item ; input_item : semicolon_list NEWLINE { emit($1, 0); macro_char = reset_macro_char; putchar('\n'); free_tree(); st_has_continue = false; } | function { putchar('\n'); free_tree(); st_has_continue = false; } | error NEWLINE { yyerrok; } | error QUIT { yyerrok; } ; semicolon_list : /* empty */ { $$ = cs(""); } | statement | semicolon_list SEMICOLON statement { $$ = node($1, $3, END_NODE); } | semicolon_list SEMICOLON ; statement_list : /* empty */ { $$ = cs(""); } | statement | statement_list NEWLINE | statement_list NEWLINE statement { $$ = node($1, $3, END_NODE); } | statement_list SEMICOLON | statement_list SEMICOLON statement { $$ = node($1, $3, END_NODE); } ; opt_statement : /* empty */ { $$ = cs(""); } | statement ; statement : expression { $$ = node($1, cs("ps."), END_NODE); } | named_expression ASSIGN_OP expression { if ($2[0] == '\0') $$ = node($3, cs($2), $1.store, END_NODE); else $$ = node($1.load, $3, cs($2), $1.store, END_NODE); } | STRING { $$ = node(cs("["), as($1), cs("]P"), END_NODE); } | BREAK { if (breaksp == 0) { warning("break not in for or while"); YYERROR; } else { $$ = node( numnode(nesting - breakstack[breaksp-1]), cs("Q"), END_NODE); } } | CONTINUE { if (breaksp == 0) { warning("continue not in for or while"); YYERROR; } else { st_has_continue = true; $$ = node(numnode(nesting - breakstack[breaksp-1] - 1), cs("J"), END_NODE); } } | QUIT { sigset_t mask; putchar('q'); fflush(stdout); if (dc) { sigprocmask(SIG_BLOCK, NULL, &mask); sigsuspend(&mask); } else exit(0); } | RETURN return_expression { if (nesting == 0) { warning("return must be in a function"); YYERROR; } $$ = $2; } | FOR LPAR alloc_macro opt_expression SEMICOLON opt_relational_expression SEMICOLON opt_expression RPAR opt_statement pop_nesting { ssize_t n; if (st_has_continue) n = node($10, cs("M"), $8, cs("s."), $6, $3, END_NODE); else n = node($10, $8, cs("s."), $6, $3, END_NODE); emit_macro($3, n); $$ = node($4, cs("s."), $6, $3, cs(" "), END_NODE); } | IF LPAR alloc_macro pop_nesting relational_expression RPAR opt_statement { emit_macro($3, $7); $$ = node($5, $3, cs(" "), END_NODE); } | IF LPAR alloc_macro pop_nesting relational_expression RPAR opt_statement ELSE alloc_macro pop_nesting opt_statement { emit_macro($3, $7); emit_macro($9, $11); $$ = node($5, $3, cs("e"), $9, cs(" "), END_NODE); } | WHILE LPAR alloc_macro relational_expression RPAR opt_statement pop_nesting { ssize_t n; if (st_has_continue) n = node($6, cs("M"), $4, $3, END_NODE); else n = node($6, $4, $3, END_NODE); emit_macro($3, n); $$ = node($4, $3, cs(" "), END_NODE); } | LBRACE statement_list RBRACE { $$ = $2; } | PRINT print_expression_list { $$ = $2; } ; alloc_macro : /* empty */ { $$ = cs(str_table[macro_char]); macro_char++; /* Do not use [, \ and ] */ if (macro_char == '[') macro_char += 3; /* skip letters */ else if (macro_char == 'a') macro_char = '{'; else if (macro_char == ARRAY_CHAR) macro_char += 26; else if (macro_char == 255) fatal("program too big"); if (breaksp == BREAKSTACK_SZ) fatal("nesting too deep"); breakstack[breaksp++] = nesting++; } ; pop_nesting : /* empty */ { breaksp--; } ; function : function_header opt_parameter_list RPAR opt_newline LBRACE NEWLINE opt_auto_define_list statement_list RBRACE { int n = node(prologue, $8, epilogue, cs("0"), numnode(nesting), cs("Q"), END_NODE); emit_macro($1, n); reset_macro_char = macro_char; nesting = 0; breaksp = 0; } ; function_header : DEFINE LETTER LPAR { $$ = function_node($2); free($2); prologue = cs(""); epilogue = cs(""); nesting = 1; breaksp = 0; breakstack[breaksp] = 0; } ; opt_newline : /* empty */ | NEWLINE ; opt_parameter_list : /* empty */ | parameter_list ; parameter_list : LETTER { add_par(letter_node($1)); free($1); } | LETTER LBRACKET RBRACKET { add_par(array_node($1)); free($1); } | parameter_list COMMA LETTER { add_par(letter_node($3)); free($3); } | parameter_list COMMA LETTER LBRACKET RBRACKET { add_par(array_node($3)); free($3); } ; opt_auto_define_list : /* empty */ | AUTO define_list NEWLINE | AUTO define_list SEMICOLON ; define_list : LETTER { add_local(letter_node($1)); free($1); } | LETTER LBRACKET RBRACKET { add_local(array_node($1)); free($1); } | define_list COMMA LETTER { add_local(letter_node($3)); free($3); } | define_list COMMA LETTER LBRACKET RBRACKET { add_local(array_node($3)); free($3); } ; opt_argument_list : /* empty */ { $$ = cs(""); } | argument_list ; argument_list : expression | argument_list COMMA expression { $$ = node($1, $3, END_NODE); } | argument_list COMMA LETTER LBRACKET RBRACKET { $$ = node($1, cs("l"), array_node($3), END_NODE); free($3); } ; opt_relational_expression : /* empty */ { $$ = cs(" 0 0="); } | relational_expression ; relational_expression : expression EQUALS expression { $$ = node($1, $3, cs("="), END_NODE); } | expression UNEQUALS expression { $$ = node($1, $3, cs("!="), END_NODE); } | expression LESS expression { $$ = node($1, $3, cs(">"), END_NODE); } | expression LESS_EQ expression { $$ = node($1, $3, cs("!<"), END_NODE); } | expression GREATER expression { $$ = node($1, $3, cs("<"), END_NODE); } | expression GREATER_EQ expression { $$ = node($1, $3, cs("!>"), END_NODE); } | expression { $$ = node($1, cs(" 0!="), END_NODE); } ; return_expression : /* empty */ { $$ = node(cs("0"), epilogue, numnode(nesting), cs("Q"), END_NODE); } | expression { $$ = node($1, epilogue, numnode(nesting), cs("Q"), END_NODE); } | LPAR RPAR { $$ = node(cs("0"), epilogue, numnode(nesting), cs("Q"), END_NODE); } ; opt_expression : /* empty */ { $$ = cs(" 0"); } | expression ; expression : named_expression { $$ = node($1.load, END_NODE); } | DOT { $$ = node(cs("l."), END_NODE); } | NUMBER { $$ = node(cs(" "), as($1), END_NODE); } | LPAR expression RPAR { $$ = $2; } | LETTER LPAR opt_argument_list RPAR { $$ = node($3, cs("l"), function_node($1), cs("x"), END_NODE); free($1); } | MINUS expression %prec UMINUS { $$ = node(cs(" 0"), $2, cs("-"), END_NODE); } | expression PLUS expression { $$ = node($1, $3, cs("+"), END_NODE); } | expression MINUS expression { $$ = node($1, $3, cs("-"), END_NODE); } | expression MULTIPLY expression { $$ = node($1, $3, cs("*"), END_NODE); } | expression DIVIDE expression { $$ = node($1, $3, cs("/"), END_NODE); } | expression REMAINDER expression { $$ = node($1, $3, cs("%"), END_NODE); } | expression EXPONENT expression { $$ = node($1, $3, cs("^"), END_NODE); } | INCR named_expression { $$ = node($2.load, cs("1+d"), $2.store, END_NODE); } | DECR named_expression { $$ = node($2.load, cs("1-d"), $2.store, END_NODE); } | named_expression INCR { $$ = node($1.load, cs("d1+"), $1.store, END_NODE); } | named_expression DECR { $$ = node($1.load, cs("d1-"), $1.store, END_NODE); } | named_expression ASSIGN_OP expression { if ($2[0] == '\0') $$ = node($3, cs($2), cs("d"), $1.store, END_NODE); else $$ = node($1.load, $3, cs($2), cs("d"), $1.store, END_NODE); } | LENGTH LPAR expression RPAR { $$ = node($3, cs("Z"), END_NODE); } | SQRT LPAR expression RPAR { $$ = node($3, cs("v"), END_NODE); } | SCALE LPAR expression RPAR { $$ = node($3, cs("X"), END_NODE); } | BOOL_NOT expression { $$ = node($2, cs("N"), END_NODE); } | expression BOOL_AND alloc_macro pop_nesting expression { ssize_t n = node(cs("R"), $5, END_NODE); emit_macro($3, n); $$ = node($1, cs("d0!="), $3, END_NODE); } | expression BOOL_OR alloc_macro pop_nesting expression { ssize_t n = node(cs("R"), $5, END_NODE); emit_macro($3, n); $$ = node($1, cs("d0="), $3, END_NODE); } | expression EQUALS expression { $$ = node($1, $3, cs("G"), END_NODE); } | expression UNEQUALS expression { $$ = node($1, $3, cs("GN"), END_NODE); } | expression LESS expression { $$ = node($3, $1, cs("("), END_NODE); } | expression LESS_EQ expression { $$ = node($3, $1, cs("{"), END_NODE); } | expression GREATER expression { $$ = node($1, $3, cs("("), END_NODE); } | expression GREATER_EQ expression { $$ = node($1, $3, cs("{"), END_NODE); } ; named_expression : LETTER { $$.load = node(cs("l"), letter_node($1), END_NODE); $$.store = node(cs("s"), letter_node($1), END_NODE); free($1); } | LETTER LBRACKET expression RBRACKET { $$.load = node($3, cs(";"), array_node($1), END_NODE); $$.store = node($3, cs(":"), array_node($1), END_NODE); free($1); } | SCALE { $$.load = cs("K"); $$.store = cs("k"); } | IBASE { $$.load = cs("I"); $$.store = cs("i"); } | OBASE { $$.load = cs("O"); $$.store = cs("o"); } ; print_expression_list : print_expression | print_expression_list COMMA print_expression { $$ = node($1, $3, END_NODE); } print_expression : expression { $$ = node($1, cs("ds.n"), END_NODE); } | STRING { char *p = escape($1); $$ = node(cs("["), as(p), cs("]n"), END_NODE); free(p); } %% static void grow(void) { struct tree *p; size_t newsize; if (current == instr_sz) { newsize = instr_sz * 2 + 1; - p = realloc(instructions, newsize * sizeof(*p)); + p = reallocarray(instructions, newsize, sizeof(*p)); if (p == NULL) { free(instructions); err(1, NULL); } instructions = p; instr_sz = newsize; } } static ssize_t cs(const char *str) { grow(); instructions[current].index = CONST_STRING; instructions[current].u.cstr = str; return (current++); } static ssize_t as(const char *str) { grow(); instructions[current].index = ALLOC_STRING; instructions[current].u.astr = strdup(str); if (instructions[current].u.astr == NULL) err(1, NULL); return (current++); } static ssize_t node(ssize_t arg, ...) { va_list ap; ssize_t ret; va_start(ap, arg); ret = current; grow(); instructions[current++].index = arg; do { arg = va_arg(ap, ssize_t); grow(); instructions[current++].index = arg; } while (arg != END_NODE); va_end(ap); return (ret); } static void emit(ssize_t i, int level) { if (level > 1000) errx(1, "internal error: tree level > 1000"); if (instructions[i].index >= 0) { while (instructions[i].index != END_NODE && instructions[i].index != i) { emit(instructions[i].index, level + 1); i++; } } else if (instructions[i].index != END_NODE) fputs(instructions[i].u.cstr, stdout); } static void emit_macro(int nodeidx, ssize_t code) { putchar('['); emit(code, 0); printf("]s%s\n", instructions[nodeidx].u.cstr); nesting--; } static void free_tree(void) { ssize_t i; for (i = 0; i < current; i++) if (instructions[i].index == ALLOC_STRING) free(instructions[i].u.astr); current = 0; } static ssize_t numnode(int num) { const char *p; if (num < 10) p = str_table['0' + num]; else if (num < 16) p = str_table['A' - 10 + num]; else errx(1, "internal error: break num > 15"); return (node(cs(" "), cs(p), END_NODE)); } static ssize_t lookup(char * str, size_t len, char type) { ENTRY entry, *found; u_char *p; u_short num; /* The scanner allocated an extra byte already */ if (str[len-1] != type) { str[len] = type; str[len+1] = '\0'; } entry.key = str; found = hsearch(entry, FIND); if (found == NULL) { if (var_count == MAX_VARIABLES) errx(1, "too many variables"); p = malloc(4); if (p == NULL) err(1, NULL); num = var_count++; p[0] = 255; p[1] = ENCODE(num / VAR_BASE + 1); p[2] = ENCODE(num % VAR_BASE + 1); p[3] = '\0'; entry.data = (char *)p; entry.key = strdup(str); if (entry.key == NULL) err(1, NULL); found = hsearch(entry, ENTER); if (found == NULL) err(1, NULL); } return (cs(found->data)); } static ssize_t letter_node(char *str) { size_t len; len = strlen(str); if (len == 1 && str[0] != '_') return (cs(str_table[(int)str[0]])); else return (lookup(str, len, 'L')); } static ssize_t array_node(char *str) { size_t len; len = strlen(str); if (len == 1 && str[0] != '_') return (cs(str_table[(int)str[0] - 'a' + ARRAY_CHAR])); else return (lookup(str, len, 'A')); } static ssize_t function_node(char *str) { size_t len; len = strlen(str); if (len == 1 && str[0] != '_') return (cs(str_table[(int)str[0] - 'a' + FUNC_CHAR])); else return (lookup(str, len, 'F')); } static void add_par(ssize_t n) { prologue = node(cs("S"), n, prologue, END_NODE); epilogue = node(epilogue, cs("L"), n, cs("s."), END_NODE); } static void add_local(ssize_t n) { prologue = node(cs("0S"), n, prologue, END_NODE); epilogue = node(epilogue, cs("L"), n, cs("s."), END_NODE); } void yyerror(const char *s) { char *p, *str; int n; if (yyin != NULL && feof(yyin)) n = asprintf(&str, "%s: %s:%d: %s: unexpected EOF", __progname, filename, lineno, s); else if (yytext[0] == '\n') n = asprintf(&str, "%s: %s:%d: %s: newline unexpected", __progname, filename, lineno, s); else if (isspace((unsigned char)yytext[0]) || !isprint((unsigned char)yytext[0])) n = asprintf(&str, "%s: %s:%d: %s: ascii char 0x%02x unexpected", __progname, filename, lineno, s, yytext[0] & 0xff); else n = asprintf(&str, "%s: %s:%d: %s: %s unexpected", __progname, filename, lineno, s, yytext); if (n == -1) err(1, NULL); fputs("c[", stdout); for (p = str; *p != '\0'; p++) { if (*p == '[' || *p == ']' || *p =='\\') putchar('\\'); putchar(*p); } fputs("]pc\n", stdout); free(str); } void fatal(const char *s) { errx(1, "%s:%d: %s", filename, lineno, s); } static void warning(const char *s) { warnx("%s:%d: %s", filename, lineno, s); } static void init(void) { unsigned int i; for (i = 0; i < UCHAR_MAX; i++) { str_table[i][0] = i; str_table[i][1] = '\0'; } if (hcreate(1 << 16) == 0) err(1, NULL); } static void usage(void) { fprintf(stderr, "usage: %s [-chlv] [-e expression] [file ...]\n", __progname); exit(1); } static char * escape(const char *str) { char *p, *ret; ret = malloc(strlen(str) + 1); if (ret == NULL) err(1, NULL); p = ret; while (*str != '\0') { /* * We get _escaped_ strings here. Single backslashes are * already converted to double backslashes */ if (*str == '\\') { if (*++str == '\\') { switch (*++str) { case 'a': *p++ = '\a'; break; case 'b': *p++ = '\b'; break; case 'f': *p++ = '\f'; break; case 'n': *p++ = '\n'; break; case 'q': *p++ = '"'; break; case 'r': *p++ = '\r'; break; case 't': *p++ = '\t'; break; case '\\': *p++ = '\\'; break; } str++; } else { *p++ = '\\'; *p++ = *str++; } } else *p++ = *str++; } *p = '\0'; return (ret); } /* ARGSUSED */ static void sigchld(int signo __unused) { pid_t pid; int status, save_errno = errno; for (;;) { pid = waitpid(dc, &status, WCONTINUED | WNOHANG); if (pid == -1) { if (errno == EINTR) continue; _exit(0); } else if (pid == 0) break; if (WIFEXITED(status) || WIFSIGNALED(status)) _exit(0); else break; } errno = save_errno; } static const char * dummy_prompt(void) { return (""); } int main(int argc, char *argv[]) { char *q; int p[2]; int ch, i; init(); setvbuf(stdout, NULL, _IOLBF, 0); - sargv = malloc(argc * sizeof(char *)); + sargv = reallocarray(NULL, argc, sizeof(char *)); if (sargv == NULL) err(1, NULL); if ((cmdexpr = strdup("")) == NULL) err(1, NULL); /* The d debug option is 4.4 BSD bc(1) compatible */ while ((ch = getopt_long(argc, argv, "cde:hlqv", long_options, NULL)) != -1) { switch (ch) { case 'c': case 'd': do_fork = false; break; case 'e': q = cmdexpr; if (asprintf(&cmdexpr, "%s%s\n", cmdexpr, optarg) == -1) err(1, NULL); free(q); break; case 'h': usage(); break; case 'l': sargv[sargc++] = _PATH_LIBB; break; case 'q': /* compatibility option */ break; case 'v': fprintf(stderr, "%s (BSD bc) %s\n", __progname, BC_VER); exit(0); break; default: usage(); } } argc -= optind; argv += optind; interactive = isatty(STDIN_FILENO); for (i = 0; i < argc; i++) sargv[sargc++] = argv[i]; if (do_fork) { if (pipe(p) == -1) err(1, "cannot create pipe"); dc = fork(); if (dc == -1) err(1, "cannot fork"); else if (dc != 0) { signal(SIGCHLD, sigchld); close(STDOUT_FILENO); dup(p[1]); close(p[0]); close(p[1]); } else { close(STDIN_FILENO); dup(p[0]); close(p[0]); close(p[1]); execl(_PATH_DC, "dc", "-x", (char *)NULL); err(1, "cannot find dc"); } } if (interactive) { gettty(&ttysaved); el = el_init("bc", stdin, stderr, stderr); hist = history_init(); history(hist, &he, H_SETSIZE, 100); el_set(el, EL_HIST, history, hist); el_set(el, EL_EDITOR, "emacs"); el_set(el, EL_SIGNAL, 1); el_set(el, EL_PROMPT, dummy_prompt); el_set(el, EL_ADDFN, "bc_eof", "", bc_eof); el_set(el, EL_BIND, "^D", "bc_eof", NULL); el_source(el, NULL); } yywrap(); return (yyparse()); } Index: head/usr.bin/dc/bcode.c =================================================================== --- head/usr.bin/dc/bcode.c (revision 314703) +++ head/usr.bin/dc/bcode.c (revision 314704) @@ -1,1777 +1,1777 @@ -/* $OpenBSD: bcode.c,v 1.45 2012/11/07 11:06:14 otto Exp $ */ +/* $OpenBSD: bcode.c,v 1.46 2014/10/08 03:59:56 doug Exp $ */ /* * Copyright (c) 2003, Otto Moerbeek * * Permission to use, copy, modify, and distribute this software for any * purpose with or without fee is hereby granted, provided that the above * copyright notice and this permission notice appear in all copies. * * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ #include __FBSDID("$FreeBSD$"); #include #include #include #include #include #include #include #include "extern.h" /* #define DEBUGGING */ #define MAX_ARRAY_INDEX 2048 #define READSTACK_SIZE 8 #define NO_ELSE -2 /* -1 is EOF */ #define REG_ARRAY_SIZE_SMALL (UCHAR_MAX + 1) #define REG_ARRAY_SIZE_BIG (UCHAR_MAX + 1 + USHRT_MAX + 1) struct bmachine { struct source *readstack; struct stack *reg; struct stack stack; u_int scale; u_int obase; u_int ibase; size_t readsp; size_t reg_array_size; size_t readstack_sz; bool extended_regs; }; static struct bmachine bmachine; static __inline int readch(void); static __inline void unreadch(void); static __inline char *readline(void); static __inline void src_free(void); static __inline u_int max(u_int, u_int); static u_long get_ulong(struct number *); static __inline void push_number(struct number *); static __inline void push_string(char *); static __inline void push(struct value *); static __inline struct value *tos(void); static __inline struct number *pop_number(void); static __inline char *pop_string(void); static __inline void clear_stack(void); static __inline void print_tos(void); static void print_err(void); static void pop_print(void); static void pop_printn(void); static __inline void print_stack(void); static __inline void dup(void); static void swap(void); static void drop(void); static void get_scale(void); static void set_scale(void); static void get_obase(void); static void set_obase(void); static void get_ibase(void); static void set_ibase(void); static void stackdepth(void); static void push_scale(void); static u_int count_digits(const struct number *); static void num_digits(void); static void to_ascii(void); static void push_line(void); static void comment(void); static void bexec(char *); static void badd(void); static void bsub(void); static void bmul(void); static void bdiv(void); static void bmod(void); static void bdivmod(void); static void bexp(void); static bool bsqrt_stop(const BIGNUM *, const BIGNUM *, u_int *); static void bsqrt(void); static void not(void); static void equal_numbers(void); static void less_numbers(void); static void lesseq_numbers(void); static void equal(void); static void not_equal(void); static void less(void); static void not_less(void); static void greater(void); static void not_greater(void); static void not_compare(void); static bool compare_numbers(enum bcode_compare, struct number *, struct number *); static void compare(enum bcode_compare); static int readreg(void); static void load(void); static void store(void); static void load_stack(void); static void store_stack(void); static void load_array(void); static void store_array(void); static void nop(void); static void quit(void); static void quitN(void); static void skipN(void); static void skip_until_mark(void); static void parse_number(void); static void unknown(void); static void eval_string(char *); static void eval_line(void); static void eval_tos(void); typedef void (*opcode_function)(void); struct jump_entry { u_char ch; opcode_function f; }; static opcode_function jump_table[UCHAR_MAX]; static const struct jump_entry jump_table_data[] = { { ' ', nop }, { '!', not_compare }, { '#', comment }, { '%', bmod }, { '(', less_numbers }, { '*', bmul }, { '+', badd }, { '-', bsub }, { '.', parse_number }, { '/', bdiv }, { '0', parse_number }, { '1', parse_number }, { '2', parse_number }, { '3', parse_number }, { '4', parse_number }, { '5', parse_number }, { '6', parse_number }, { '7', parse_number }, { '8', parse_number }, { '9', parse_number }, { ':', store_array }, { ';', load_array }, { '<', less }, { '=', equal }, { '>', greater }, { '?', eval_line }, { 'A', parse_number }, { 'B', parse_number }, { 'C', parse_number }, { 'D', parse_number }, { 'E', parse_number }, { 'F', parse_number }, { 'G', equal_numbers }, { 'I', get_ibase }, { 'J', skipN }, { 'K', get_scale }, { 'L', load_stack }, { 'M', nop }, { 'N', not }, { 'O', get_obase }, { 'P', pop_print }, { 'Q', quitN }, { 'R', drop }, { 'S', store_stack }, { 'X', push_scale }, { 'Z', num_digits }, { '[', push_line }, { '\f', nop }, { '\n', nop }, { '\r', nop }, { '\t', nop }, { '^', bexp }, { '_', parse_number }, { 'a', to_ascii }, { 'c', clear_stack }, { 'd', dup }, { 'e', print_err }, { 'f', print_stack }, { 'i', set_ibase }, { 'k', set_scale }, { 'l', load }, { 'n', pop_printn }, { 'o', set_obase }, { 'p', print_tos }, { 'q', quit }, { 'r', swap }, { 's', store }, { 'v', bsqrt }, { 'x', eval_tos }, { 'z', stackdepth }, { '{', lesseq_numbers }, { '~', bdivmod } }; #define JUMP_TABLE_DATA_SIZE \ (sizeof(jump_table_data)/sizeof(jump_table_data[0])) void init_bmachine(bool extended_registers) { unsigned int i; bmachine.extended_regs = extended_registers; bmachine.reg_array_size = bmachine.extended_regs ? REG_ARRAY_SIZE_BIG : REG_ARRAY_SIZE_SMALL; bmachine.reg = calloc(bmachine.reg_array_size, sizeof(bmachine.reg[0])); if (bmachine.reg == NULL) err(1, NULL); for (i = 0; i < UCHAR_MAX; i++) jump_table[i] = unknown; for (i = 0; i < JUMP_TABLE_DATA_SIZE; i++) jump_table[jump_table_data[i].ch] = jump_table_data[i].f; stack_init(&bmachine.stack); for (i = 0; i < bmachine.reg_array_size; i++) stack_init(&bmachine.reg[i]); bmachine.readstack_sz = READSTACK_SIZE; bmachine.readstack = calloc(sizeof(struct source), bmachine.readstack_sz); if (bmachine.readstack == NULL) err(1, NULL); bmachine.obase = bmachine.ibase = 10; } u_int bmachine_scale(void) { return bmachine.scale; } /* Reset the things needed before processing a (new) file */ void reset_bmachine(struct source *src) { bmachine.readsp = 0; bmachine.readstack[0] = *src; } static __inline int readch(void) { struct source *src = &bmachine.readstack[bmachine.readsp]; return (src->vtable->readchar(src)); } static __inline void unreadch(void) { struct source *src = &bmachine.readstack[bmachine.readsp]; src->vtable->unreadchar(src); } static __inline char * readline(void) { struct source *src = &bmachine.readstack[bmachine.readsp]; return (src->vtable->readline(src)); } static __inline void src_free(void) { struct source *src = &bmachine.readstack[bmachine.readsp]; src->vtable->free(src); } #ifdef DEBUGGING void pn(const char *str, const struct number *n) { char *p = BN_bn2dec(n->number); if (p == NULL) err(1, "BN_bn2dec failed"); fputs(str, stderr); fprintf(stderr, " %s (%u)\n" , p, n->scale); OPENSSL_free(p); } void pbn(const char *str, const BIGNUM *n) { char *p = BN_bn2dec(n); if (p == NULL) err(1, "BN_bn2dec failed"); fputs(str, stderr); fprintf(stderr, " %s\n", p); OPENSSL_free(p); } #endif static __inline u_int max(u_int a, u_int b) { return (a > b ? a : b); } static unsigned long factors[] = { 0, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 }; void scale_number(BIGNUM *n, int s) { unsigned int abs_scale; if (s == 0) return; abs_scale = s > 0 ? s : -s; if (abs_scale < sizeof(factors)/sizeof(factors[0])) { if (s > 0) bn_check(BN_mul_word(n, factors[abs_scale])); else BN_div_word(n, factors[abs_scale]); } else { BIGNUM *a, *p; BN_CTX *ctx; a = BN_new(); bn_checkp(a); p = BN_new(); bn_checkp(p); ctx = BN_CTX_new(); bn_checkp(ctx); bn_check(BN_set_word(a, 10)); bn_check(BN_set_word(p, abs_scale)); bn_check(BN_exp(a, a, p, ctx)); if (s > 0) bn_check(BN_mul(n, n, a, ctx)); else bn_check(BN_div(n, NULL, n, a, ctx)); BN_CTX_free(ctx); BN_free(a); BN_free(p); } } void split_number(const struct number *n, BIGNUM *i, BIGNUM *f) { u_long rem; bn_checkp(BN_copy(i, n->number)); if (n->scale == 0 && f != NULL) bn_check(BN_zero(f)); else if (n->scale < sizeof(factors)/sizeof(factors[0])) { rem = BN_div_word(i, factors[n->scale]); if (f != NULL) bn_check(BN_set_word(f, rem)); } else { BIGNUM *a, *p; BN_CTX *ctx; a = BN_new(); bn_checkp(a); p = BN_new(); bn_checkp(p); ctx = BN_CTX_new(); bn_checkp(ctx); bn_check(BN_set_word(a, 10)); bn_check(BN_set_word(p, n->scale)); bn_check(BN_exp(a, a, p, ctx)); bn_check(BN_div(i, f, n->number, a, ctx)); BN_CTX_free(ctx); BN_free(a); BN_free(p); } } void normalize(struct number *n, u_int s) { scale_number(n->number, s - n->scale); n->scale = s; } static u_long get_ulong(struct number *n) { normalize(n, 0); return (BN_get_word(n->number)); } void negate(struct number *n) { BN_set_negative(n->number, !BN_is_negative(n->number)); } static __inline void push_number(struct number *n) { stack_pushnumber(&bmachine.stack, n); } static __inline void push_string(char *string) { stack_pushstring(&bmachine.stack, string); } static __inline void push(struct value *v) { stack_push(&bmachine.stack, v); } static __inline struct value * tos(void) { return (stack_tos(&bmachine.stack)); } static __inline struct value * pop(void) { return (stack_pop(&bmachine.stack)); } static __inline struct number * pop_number(void) { return (stack_popnumber(&bmachine.stack)); } static __inline char * pop_string(void) { return (stack_popstring(&bmachine.stack)); } static __inline void clear_stack(void) { stack_clear(&bmachine.stack); } static __inline void print_stack(void) { stack_print(stdout, &bmachine.stack, "", bmachine.obase); } static __inline void print_tos(void) { struct value *value = tos(); if (value != NULL) { print_value(stdout, value, "", bmachine.obase); putchar('\n'); } else warnx("stack empty"); } static void print_err(void) { struct value *value = tos(); if (value != NULL) { print_value(stderr, value, "", bmachine.obase); (void)putc('\n', stderr); } else warnx("stack empty"); } static void pop_print(void) { struct value *value = pop(); if (value != NULL) { switch (value->type) { case BCODE_NONE: break; case BCODE_NUMBER: normalize(value->u.num, 0); print_ascii(stdout, value->u.num); fflush(stdout); break; case BCODE_STRING: fputs(value->u.string, stdout); fflush(stdout); break; } stack_free_value(value); } } static void pop_printn(void) { struct value *value = pop(); if (value != NULL) { print_value(stdout, value, "", bmachine.obase); fflush(stdout); stack_free_value(value); } } static __inline void dup(void) { stack_dup(&bmachine.stack); } static void swap(void) { stack_swap(&bmachine.stack); } static void drop(void) { struct value *v = pop(); if (v != NULL) stack_free_value(v); } static void get_scale(void) { struct number *n; n = new_number(); bn_check(BN_set_word(n->number, bmachine.scale)); push_number(n); } static void set_scale(void) { struct number *n; u_long scale; n = pop_number(); if (n != NULL) { if (BN_is_negative(n->number)) warnx("scale must be a nonnegative number"); else { scale = get_ulong(n); if (scale != BN_MASK2 && scale <= UINT_MAX) bmachine.scale = (u_int)scale; else warnx("scale too large"); } free_number(n); } } static void get_obase(void) { struct number *n; n = new_number(); bn_check(BN_set_word(n->number, bmachine.obase)); push_number(n); } static void set_obase(void) { struct number *n; u_long base; n = pop_number(); if (n != NULL) { base = get_ulong(n); if (base != BN_MASK2 && base > 1 && base <= UINT_MAX) bmachine.obase = (u_int)base; else warnx("output base must be a number greater than 1"); free_number(n); } } static void get_ibase(void) { struct number *n; n = new_number(); bn_check(BN_set_word(n->number, bmachine.ibase)); push_number(n); } static void set_ibase(void) { struct number *n; u_long base; n = pop_number(); if (n != NULL) { base = get_ulong(n); if (base != BN_MASK2 && 2 <= base && base <= 16) bmachine.ibase = (u_int)base; else warnx("input base must be a number between 2 and 16 " "(inclusive)"); free_number(n); } } static void stackdepth(void) { struct number *n; size_t i; i = stack_size(&bmachine.stack); n = new_number(); bn_check(BN_set_word(n->number, i)); push_number(n); } static void push_scale(void) { struct number *n; struct value *value; u_int scale = 0; value = pop(); if (value != NULL) { switch (value->type) { case BCODE_NONE: return; case BCODE_NUMBER: scale = value->u.num->scale; break; case BCODE_STRING: break; } stack_free_value(value); n = new_number(); bn_check(BN_set_word(n->number, scale)); push_number(n); } } static u_int count_digits(const struct number *n) { struct number *int_part, *fract_part; u_int i; if (BN_is_zero(n->number)) return n->scale ? n->scale : 1; int_part = new_number(); fract_part = new_number(); fract_part->scale = n->scale; split_number(n, int_part->number, fract_part->number); i = 0; while (!BN_is_zero(int_part->number)) { BN_div_word(int_part->number, 10); i++; } free_number(int_part); free_number(fract_part); return (i + n->scale); } static void num_digits(void) { struct number *n = NULL; struct value *value; size_t digits; value = pop(); if (value != NULL) { switch (value->type) { case BCODE_NONE: return; case BCODE_NUMBER: digits = count_digits(value->u.num); n = new_number(); bn_check(BN_set_word(n->number, digits)); break; case BCODE_STRING: digits = strlen(value->u.string); n = new_number(); bn_check(BN_set_word(n->number, digits)); break; } stack_free_value(value); push_number(n); } } static void to_ascii(void) { struct number *n; struct value *value; char str[2]; value = pop(); if (value != NULL) { str[1] = '\0'; switch (value->type) { case BCODE_NONE: return; case BCODE_NUMBER: n = value->u.num; normalize(n, 0); if (BN_num_bits(n->number) > 8) bn_check(BN_mask_bits(n->number, 8)); str[0] = (char)BN_get_word(n->number); break; case BCODE_STRING: str[0] = value->u.string[0]; break; } stack_free_value(value); push_string(bstrdup(str)); } } static int readreg(void) { int ch1, ch2, idx; idx = readch(); if (idx == 0xff && bmachine.extended_regs) { ch1 = readch(); ch2 = readch(); if (ch1 == EOF || ch2 == EOF) { warnx("unexpected eof"); idx = -1; } else idx = (ch1 << 8) + ch2 + UCHAR_MAX + 1; } if (idx < 0 || (unsigned)idx >= bmachine.reg_array_size) { warnx("internal error: reg num = %d", idx); idx = -1; } return (idx); } static void load(void) { struct number *n; struct value *v; struct value copy; int idx; idx = readreg(); if (idx >= 0) { v = stack_tos(&bmachine.reg[idx]); if (v == NULL) { n = new_number(); bn_check(BN_zero(n->number)); push_number(n); } else push(stack_dup_value(v, ©)); } } static void store(void) { struct value *val; int idx; idx = readreg(); if (idx >= 0) { val = pop(); if (val == NULL) { return; } stack_set_tos(&bmachine.reg[idx], val); } } static void load_stack(void) { struct stack *stack; struct value *value; int idx; idx = readreg(); if (idx >= 0) { stack = &bmachine.reg[idx]; value = NULL; if (stack_size(stack) > 0) { value = stack_pop(stack); } if (value != NULL) push(value); else warnx("stack register '%c' (0%o) is empty", idx, idx); } } static void store_stack(void) { struct value *value; int idx; idx = readreg(); if (idx >= 0) { value = pop(); if (value == NULL) return; stack_push(&bmachine.reg[idx], value); } } static void load_array(void) { struct number *inumber, *n; struct stack *stack; struct value *v; struct value copy; u_long idx; int reg; reg = readreg(); if (reg >= 0) { inumber = pop_number(); if (inumber == NULL) return; idx = get_ulong(inumber); if (BN_is_negative(inumber->number)) warnx("negative idx"); else if (idx == BN_MASK2 || idx > MAX_ARRAY_INDEX) warnx("idx too big"); else { stack = &bmachine.reg[reg]; v = frame_retrieve(stack, idx); if (v == NULL || v->type == BCODE_NONE) { n = new_number(); bn_check(BN_zero(n->number)); push_number(n); } else push(stack_dup_value(v, ©)); } free_number(inumber); } } static void store_array(void) { struct number *inumber; struct value *value; struct stack *stack; u_long idx; int reg; reg = readreg(); if (reg >= 0) { inumber = pop_number(); if (inumber == NULL) return; value = pop(); if (value == NULL) { free_number(inumber); return; } idx = get_ulong(inumber); if (BN_is_negative(inumber->number)) { warnx("negative idx"); stack_free_value(value); } else if (idx == BN_MASK2 || idx > MAX_ARRAY_INDEX) { warnx("idx too big"); stack_free_value(value); } else { stack = &bmachine.reg[reg]; frame_assign(stack, idx, value); } free_number(inumber); } } static void push_line(void) { push_string(read_string(&bmachine.readstack[bmachine.readsp])); } static void comment(void) { free(readline()); } static void bexec(char *line) { system(line); free(line); } static void badd(void) { struct number *a, *b, *r; a = pop_number(); if (a == NULL) return; b = pop_number(); if (b == NULL) { push_number(a); return; } r = new_number(); r->scale = max(a->scale, b->scale); if (r->scale > a->scale) normalize(a, r->scale); else if (r->scale > b->scale) normalize(b, r->scale); bn_check(BN_add(r->number, a->number, b->number)); push_number(r); free_number(a); free_number(b); } static void bsub(void) { struct number *a, *b, *r; a = pop_number(); if (a == NULL) return; b = pop_number(); if (b == NULL) { push_number(a); return; } r = new_number(); r->scale = max(a->scale, b->scale); if (r->scale > a->scale) normalize(a, r->scale); else if (r->scale > b->scale) normalize(b, r->scale); bn_check(BN_sub(r->number, b->number, a->number)); push_number(r); free_number(a); free_number(b); } void bmul_number(struct number *r, struct number *a, struct number *b, u_int scale) { BN_CTX *ctx; /* Create copies of the scales, since r might be equal to a or b */ u_int ascale = a->scale; u_int bscale = b->scale; u_int rscale = ascale + bscale; ctx = BN_CTX_new(); bn_checkp(ctx); bn_check(BN_mul(r->number, a->number, b->number, ctx)); BN_CTX_free(ctx); r->scale = rscale; if (rscale > bmachine.scale && rscale > ascale && rscale > bscale) normalize(r, max(scale, max(ascale, bscale))); } static void bmul(void) { struct number *a, *b, *r; a = pop_number(); if (a == NULL) return; b = pop_number(); if (b == NULL) { push_number(a); return; } r = new_number(); bmul_number(r, a, b, bmachine.scale); push_number(r); free_number(a); free_number(b); } static void bdiv(void) { struct number *a, *b, *r; BN_CTX *ctx; u_int scale; a = pop_number(); if (a == NULL) return; b = pop_number(); if (b == NULL) { push_number(a); return; } r = new_number(); r->scale = bmachine.scale; scale = max(a->scale, b->scale); if (BN_is_zero(a->number)) warnx("divide by zero"); else { normalize(a, scale); normalize(b, scale + r->scale); ctx = BN_CTX_new(); bn_checkp(ctx); bn_check(BN_div(r->number, NULL, b->number, a->number, ctx)); BN_CTX_free(ctx); } push_number(r); free_number(a); free_number(b); } static void bmod(void) { struct number *a, *b, *r; BN_CTX *ctx; u_int scale; a = pop_number(); if (a == NULL) return; b = pop_number(); if (b == NULL) { push_number(a); return; } r = new_number(); scale = max(a->scale, b->scale); r->scale = max(b->scale, a->scale + bmachine.scale); if (BN_is_zero(a->number)) warnx("remainder by zero"); else { normalize(a, scale); normalize(b, scale + bmachine.scale); ctx = BN_CTX_new(); bn_checkp(ctx); bn_check(BN_mod(r->number, b->number, a->number, ctx)); BN_CTX_free(ctx); } push_number(r); free_number(a); free_number(b); } static void bdivmod(void) { struct number *a, *b, *rdiv, *rmod; BN_CTX *ctx; u_int scale; a = pop_number(); if (a == NULL) return; b = pop_number(); if (b == NULL) { push_number(a); return; } rdiv = new_number(); rmod = new_number(); rdiv->scale = bmachine.scale; rmod->scale = max(b->scale, a->scale + bmachine.scale); scale = max(a->scale, b->scale); if (BN_is_zero(a->number)) warnx("divide by zero"); else { normalize(a, scale); normalize(b, scale + bmachine.scale); ctx = BN_CTX_new(); bn_checkp(ctx); bn_check(BN_div(rdiv->number, rmod->number, b->number, a->number, ctx)); BN_CTX_free(ctx); } push_number(rdiv); push_number(rmod); free_number(a); free_number(b); } static void bexp(void) { struct number *a, *p; struct number *r; bool neg; u_int rscale; p = pop_number(); if (p == NULL) return; a = pop_number(); if (a == NULL) { push_number(p); return; } if (p->scale != 0) { BIGNUM *i, *f; i = BN_new(); bn_checkp(i); f = BN_new(); bn_checkp(f); split_number(p, i, f); if (!BN_is_zero(f)) warnx("Runtime warning: non-zero fractional part in exponent"); BN_free(i); BN_free(f); } normalize(p, 0); neg = false; if (BN_is_negative(p->number)) { neg = true; negate(p); rscale = bmachine.scale; } else { /* Posix bc says min(a.scale * b, max(a.scale, scale) */ u_long b; u_int m; b = BN_get_word(p->number); m = max(a->scale, bmachine.scale); rscale = a->scale * (u_int)b; if (rscale > m || (a->scale > 0 && (b == BN_MASK2 || b > UINT_MAX))) rscale = m; } if (BN_is_zero(p->number)) { r = new_number(); bn_check(BN_one(r->number)); normalize(r, rscale); } else { u_int ascale, mscale; ascale = a->scale; while (!BN_is_bit_set(p->number, 0)) { ascale *= 2; bmul_number(a, a, a, ascale); bn_check(BN_rshift1(p->number, p->number)); } r = dup_number(a); bn_check(BN_rshift1(p->number, p->number)); mscale = ascale; while (!BN_is_zero(p->number)) { ascale *= 2; bmul_number(a, a, a, ascale); if (BN_is_bit_set(p->number, 0)) { mscale += ascale; bmul_number(r, r, a, mscale); } bn_check(BN_rshift1(p->number, p->number)); } if (neg) { BN_CTX *ctx; BIGNUM *one; one = BN_new(); bn_checkp(one); bn_check(BN_one(one)); ctx = BN_CTX_new(); bn_checkp(ctx); scale_number(one, r->scale + rscale); if (BN_is_zero(r->number)) warnx("divide by zero"); else bn_check(BN_div(r->number, NULL, one, r->number, ctx)); BN_free(one); BN_CTX_free(ctx); r->scale = rscale; } else normalize(r, rscale); } push_number(r); free_number(a); free_number(p); } static bool bsqrt_stop(const BIGNUM *x, const BIGNUM *y, u_int *onecount) { BIGNUM *r; bool ret; r = BN_new(); bn_checkp(r); bn_check(BN_sub(r, x, y)); if (BN_is_one(r)) (*onecount)++; ret = BN_is_zero(r); BN_free(r); return (ret || *onecount > 1); } static void bsqrt(void) { struct number *n, *r; BIGNUM *x, *y; BN_CTX *ctx; u_int onecount, scale; onecount = 0; n = pop_number(); if (n == NULL) return; if (BN_is_zero(n->number)) { r = new_number(); push_number(r); } else if (BN_is_negative(n->number)) warnx("square root of negative number"); else { scale = max(bmachine.scale, n->scale); normalize(n, 2*scale); x = BN_dup(n->number); bn_checkp(x); bn_check(BN_rshift(x, x, BN_num_bits(x)/2)); y = BN_new(); bn_checkp(y); ctx = BN_CTX_new(); bn_checkp(ctx); for (;;) { bn_checkp(BN_copy(y, x)); bn_check(BN_div(x, NULL, n->number, x, ctx)); bn_check(BN_add(x, x, y)); bn_check(BN_rshift1(x, x)); if (bsqrt_stop(x, y, &onecount)) break; } r = bmalloc(sizeof(*r)); r->scale = scale; r->number = y; BN_free(x); BN_CTX_free(ctx); push_number(r); } free_number(n); } static void not(void) { struct number *a; a = pop_number(); if (a == NULL) return; a->scale = 0; bn_check(BN_set_word(a->number, BN_get_word(a->number) ? 0 : 1)); push_number(a); } static void equal(void) { compare(BCODE_EQUAL); } static void equal_numbers(void) { struct number *a, *b, *r; a = pop_number(); if (a == NULL) return; b = pop_number(); if (b == NULL) { push_number(a); return; } r = new_number(); bn_check(BN_set_word(r->number, compare_numbers(BCODE_EQUAL, a, b) ? 1 : 0)); push_number(r); } static void less_numbers(void) { struct number *a, *b, *r; a = pop_number(); if (a == NULL) return; b = pop_number(); if (b == NULL) { push_number(a); return; } r = new_number(); bn_check(BN_set_word(r->number, compare_numbers(BCODE_LESS, a, b) ? 1 : 0)); push_number(r); } static void lesseq_numbers(void) { struct number *a, *b, *r; a = pop_number(); if (a == NULL) return; b = pop_number(); if (b == NULL) { push_number(a); return; } r = new_number(); bn_check(BN_set_word(r->number, compare_numbers(BCODE_NOT_GREATER, a, b) ? 1 : 0)); push_number(r); } static void not_equal(void) { compare(BCODE_NOT_EQUAL); } static void less(void) { compare(BCODE_LESS); } static void not_compare(void) { switch (readch()) { case '<': not_less(); break; case '>': not_greater(); break; case '=': not_equal(); break; default: unreadch(); bexec(readline()); break; } } static void not_less(void) { compare(BCODE_NOT_LESS); } static void greater(void) { compare(BCODE_GREATER); } static void not_greater(void) { compare(BCODE_NOT_GREATER); } static bool compare_numbers(enum bcode_compare type, struct number *a, struct number *b) { u_int scale; int cmp; scale = max(a->scale, b->scale); if (scale > a->scale) normalize(a, scale); else if (scale > b->scale) normalize(b, scale); cmp = BN_cmp(a->number, b->number); free_number(a); free_number(b); switch (type) { case BCODE_EQUAL: return (cmp == 0); case BCODE_NOT_EQUAL: return (cmp != 0); case BCODE_LESS: return (cmp < 0); case BCODE_NOT_LESS: return (cmp >= 0); case BCODE_GREATER: return (cmp > 0); case BCODE_NOT_GREATER: return (cmp <= 0); } return (false); } static void compare(enum bcode_compare type) { struct number *a, *b; struct value *v; int idx, elseidx; bool ok; elseidx = NO_ELSE; idx = readreg(); if (readch() == 'e') elseidx = readreg(); else unreadch(); a = pop_number(); if (a == NULL) return; b = pop_number(); if (b == NULL) { push_number(a); return; } ok = compare_numbers(type, a, b); if (!ok && elseidx != NO_ELSE) idx = elseidx; if (idx >= 0 && (ok || (!ok && elseidx != NO_ELSE))) { v = stack_tos(&bmachine.reg[idx]); if (v == NULL) warnx("register '%c' (0%o) is empty", idx, idx); else { switch(v->type) { case BCODE_NONE: warnx("register '%c' (0%o) is empty", idx, idx); break; case BCODE_NUMBER: warn("eval called with non-string argument"); break; case BCODE_STRING: eval_string(bstrdup(v->u.string)); break; } } } } static void nop(void) { } static void quit(void) { if (bmachine.readsp < 2) exit(0); src_free(); bmachine.readsp--; src_free(); bmachine.readsp--; } static void quitN(void) { struct number *n; u_long i; n = pop_number(); if (n == NULL) return; i = get_ulong(n); free_number(n); if (i == BN_MASK2 || i == 0) warnx("Q command requires a number >= 1"); else if (bmachine.readsp < i) warnx("Q command argument exceeded string execution depth"); else { while (i-- > 0) { src_free(); bmachine.readsp--; } } } static void skipN(void) { struct number *n; u_long i; n = pop_number(); if (n == NULL) return; i = get_ulong(n); if (i == BN_MASK2) warnx("J command requires a number >= 0"); else if (i > 0 && bmachine.readsp < i) warnx("J command argument exceeded string execution depth"); else { while (i-- > 0) { src_free(); bmachine.readsp--; } skip_until_mark(); } } static void skip_until_mark(void) { for (;;) { switch (readch()) { case 'M': return; case EOF: errx(1, "mark not found"); return; case 'l': case 'L': case 's': case 'S': case ':': case ';': case '<': case '>': case '=': readreg(); if (readch() == 'e') readreg(); else unreadch(); break; case '[': free(read_string(&bmachine.readstack[bmachine.readsp])); break; case '!': switch (readch()) { case '<': case '>': case '=': readreg(); if (readch() == 'e') readreg(); else unreadch(); break; default: free(readline()); break; } break; default: break; } } } static void parse_number(void) { unreadch(); push_number(readnumber(&bmachine.readstack[bmachine.readsp], bmachine.ibase)); } static void unknown(void) { int ch = bmachine.readstack[bmachine.readsp].lastchar; warnx("%c (0%o) is unimplemented", ch, ch); } static void eval_string(char *p) { int ch; if (bmachine.readsp > 0) { /* Check for tail call. Do not recurse in that case. */ ch = readch(); if (ch == EOF) { src_free(); src_setstring(&bmachine.readstack[bmachine.readsp], p); return; } else unreadch(); } if (bmachine.readsp == bmachine.readstack_sz - 1) { size_t newsz = bmachine.readstack_sz * 2; struct source *stack; - stack = realloc(bmachine.readstack, newsz * + stack = reallocarray(bmachine.readstack, newsz, sizeof(struct source)); if (stack == NULL) err(1, "recursion too deep"); bmachine.readstack_sz = newsz; bmachine.readstack = stack; } src_setstring(&bmachine.readstack[++bmachine.readsp], p); } static void eval_line(void) { /* Always read from stdin */ struct source in; char *p; clearerr(stdin); src_setstream(&in, stdin); p = (*in.vtable->readline)(&in); eval_string(p); } static void eval_tos(void) { char *p; p = pop_string(); if (p != NULL) eval_string(p); } void eval(void) { int ch; for (;;) { ch = readch(); if (ch == EOF) { if (bmachine.readsp == 0) return; src_free(); bmachine.readsp--; continue; } #ifdef DEBUGGING fprintf(stderr, "# %c\n", ch); stack_print(stderr, &bmachine.stack, "* ", bmachine.obase); fprintf(stderr, "%zd =>\n", bmachine.readsp); #endif if (0 <= ch && ch < (signed)UCHAR_MAX) (*jump_table[ch])(); else warnx("internal error: opcode %d", ch); #ifdef DEBUGGING stack_print(stderr, &bmachine.stack, "* ", bmachine.obase); fprintf(stderr, "%zd ==\n", bmachine.readsp); #endif } } Index: head/usr.bin/dc/extern.h =================================================================== --- head/usr.bin/dc/extern.h (revision 314703) +++ head/usr.bin/dc/extern.h (revision 314704) @@ -1,63 +1,63 @@ /* $FreeBSD$ */ -/* $OpenBSD: extern.h,v 1.3 2006/01/16 08:09:25 otto Exp $ */ +/* $OpenBSD: extern.h,v 1.4 2014/12/01 13:13:00 deraadt Exp $ */ /* * Copyright (c) 2003, Otto Moerbeek * * Permission to use, copy, modify, and distribute this software for any * purpose with or without fee is hereby granted, provided that the above * copyright notice and this permission notice appear in all copies. * * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ #include #include "bcode.h" /* inout.c */ void src_setstream(struct source *, FILE *); void src_setstring(struct source *, char *); struct number *readnumber(struct source *, u_int); void printnumber(FILE *, const struct number *, u_int); char *read_string(struct source *); void print_value(FILE *, const struct value *, const char *, u_int); void print_ascii(FILE *, const struct number *); /* mem.c */ struct number *new_number(void); void free_number(struct number *); struct number *dup_number(const struct number *); void *bmalloc(size_t); -void *brealloc(void *, size_t); +void *breallocarray(void *, size_t, size_t); char *bstrdup(const char *p); void bn_check(int); void bn_checkp(const void *); /* stack.c */ void stack_init(struct stack *); void stack_free_value(struct value *); struct value *stack_dup_value(const struct value *, struct value *); void stack_swap(struct stack *); size_t stack_size(const struct stack *); void stack_dup(struct stack *); void stack_pushnumber(struct stack *, struct number *); void stack_pushstring(struct stack *stack, char *); void stack_push(struct stack *, struct value *); void stack_set_tos(struct stack *, struct value *); struct value *stack_tos(const struct stack *); struct value *stack_pop(struct stack *); struct number *stack_popnumber(struct stack *); char *stack_popstring(struct stack *); void stack_clear(struct stack *); void stack_print(FILE *, const struct stack *, const char *, u_int base); void frame_assign(struct stack *, size_t, const struct value *); struct value *frame_retrieve(const struct stack *, size_t); /* void frame_free(struct stack *); */ Index: head/usr.bin/dc/inout.c =================================================================== --- head/usr.bin/dc/inout.c (revision 314703) +++ head/usr.bin/dc/inout.c (revision 314704) @@ -1,418 +1,418 @@ -/* $OpenBSD: inout.c,v 1.17 2012/11/07 11:06:14 otto Exp $ */ +/* $OpenBSD: inout.c,v 1.18 2014/12/01 13:13:00 deraadt Exp $ */ /* * Copyright (c) 2003, Otto Moerbeek * * Permission to use, copy, modify, and distribute this software for any * purpose with or without fee is hereby granted, provided that the above * copyright notice and this permission notice appear in all copies. * * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ #include __FBSDID("$FreeBSD$"); #include #include #include #include #include "extern.h" #define MAX_CHARS_PER_LINE 68 static int lastchar; static int charcount; static int src_getcharstream(struct source *); static void src_ungetcharstream(struct source *); static char *src_getlinestream(struct source *); static int src_getcharstring(struct source *); static void src_ungetcharstring(struct source *); static char *src_getlinestring(struct source *); static void src_freestring(struct source *); static void flushwrap(FILE *); static void putcharwrap(FILE *, int); static void printwrap(FILE *, const char *); static char *get_digit(u_long, int, u_int); static struct vtable stream_vtable = { src_getcharstream, src_ungetcharstream, src_getlinestream, NULL }; static struct vtable string_vtable = { src_getcharstring, src_ungetcharstring, src_getlinestring, src_freestring }; void src_setstream(struct source *src, FILE *stream) { src->u.stream = stream; src->vtable = &stream_vtable; } void src_setstring(struct source *src, char *p) { src->u.string.buf = (u_char *)p; src->u.string.pos = 0; src->vtable = &string_vtable; } static int src_getcharstream(struct source *src) { return (src->lastchar = getc(src->u.stream)); } static void src_ungetcharstream(struct source *src) { ungetc(src->lastchar, src->u.stream); } static char * src_getlinestream(struct source *src) { char buf[BUFSIZ]; if (fgets(buf, BUFSIZ, src->u.stream) == NULL) return (bstrdup("")); return bstrdup(buf); } static int src_getcharstring(struct source *src) { src->lastchar = src->u.string.buf[src->u.string.pos]; if (src->lastchar == '\0') return (EOF); else { src->u.string.pos++; return (src->lastchar); } } static void src_ungetcharstring(struct source *src) { if (src->u.string.pos > 0) { if (src->lastchar != '\0') --src->u.string.pos; } } static char * src_getlinestring(struct source *src) { char buf[BUFSIZ]; int i, ch; i = 0; while (i < BUFSIZ-1) { ch = src_getcharstring(src); if (ch == EOF) break; buf[i++] = ch; if (ch == '\n') break; } buf[i] = '\0'; return (bstrdup(buf)); } static void src_freestring(struct source *src) { free(src->u.string.buf); } static void flushwrap(FILE *f) { if (lastchar != -1) putc(lastchar, f); } static void putcharwrap(FILE *f, int ch) { if (charcount >= MAX_CHARS_PER_LINE) { charcount = 0; fputs("\\\n", f); } if (lastchar != -1) { charcount++; putc(lastchar, f); } lastchar = ch; } static void printwrap(FILE *f, const char *p) { char *q; char buf[12]; q = buf; strlcpy(buf, p, sizeof(buf)); while (*q) putcharwrap(f, *q++); } struct number * readnumber(struct source *src, u_int base) { struct number *n; BN_ULONG v; u_int i; int ch; bool dot = false, sign = false; n = new_number(); bn_check(BN_zero(n->number)); while ((ch = (*src->vtable->readchar)(src)) != EOF) { if ('0' <= ch && ch <= '9') v = ch - '0'; else if ('A' <= ch && ch <= 'F') v = ch - 'A' + 10; else if (ch == '_') { sign = true; continue; } else if (ch == '.') { if (dot) break; dot = true; continue; } else { (*src->vtable->unreadchar)(src); break; } if (dot) n->scale++; bn_check(BN_mul_word(n->number, base)); #if 0 /* work around a bug in BN_add_word: 0 += 0 is buggy.... */ if (v > 0) #endif bn_check(BN_add_word(n->number, v)); } if (base != 10) { scale_number(n->number, n->scale); for (i = 0; i < n->scale; i++) BN_div_word(n->number, base); } if (sign) negate(n); return (n); } char * read_string(struct source *src) { char *p; int count, ch, i, new_sz, sz; bool escape; escape = false; count = 1; i = 0; sz = 15; p = bmalloc(sz + 1); while ((ch = (*src->vtable->readchar)(src)) != EOF) { if (!escape) { if (ch == '[') count++; else if (ch == ']') count--; if (count == 0) break; } if (ch == '\\' && !escape) escape = true; else { escape = false; if (i == sz) { new_sz = sz * 2; - p = brealloc(p, new_sz + 1); + p = breallocarray(p, 1, new_sz + 1); sz = new_sz; } p[i++] = ch; } } p[i] = '\0'; return (p); } static char * get_digit(u_long num, int digits, u_int base) { char *p; if (base <= 16) { p = bmalloc(2); p[0] = num >= 10 ? num + 'A' - 10 : num + '0'; p[1] = '\0'; } else { if (asprintf(&p, "%0*lu", digits, num) == -1) err(1, NULL); } return (p); } void printnumber(FILE *f, const struct number *b, u_int base) { struct number *fract_part, *int_part; struct stack stack; char *p; char buf[11]; size_t sz; unsigned int i; int digits; charcount = 0; lastchar = -1; if (BN_is_zero(b->number)) putcharwrap(f, '0'); int_part = new_number(); fract_part = new_number(); fract_part->scale = b->scale; if (base <= 16) digits = 1; else { digits = snprintf(buf, sizeof(buf), "%u", base-1); } split_number(b, int_part->number, fract_part->number); i = 0; stack_init(&stack); while (!BN_is_zero(int_part->number)) { BN_ULONG rem = BN_div_word(int_part->number, base); stack_pushstring(&stack, get_digit(rem, digits, base)); i++; } sz = i; if (BN_is_negative(b->number)) putcharwrap(f, '-'); for (i = 0; i < sz; i++) { p = stack_popstring(&stack); if (base > 16) putcharwrap(f, ' '); printwrap(f, p); free(p); } stack_clear(&stack); if (b->scale > 0) { struct number *num_base; BIGNUM mult, stop; putcharwrap(f, '.'); num_base = new_number(); bn_check(BN_set_word(num_base->number, base)); BN_init(&mult); bn_check(BN_one(&mult)); BN_init(&stop); bn_check(BN_one(&stop)); scale_number(&stop, b->scale); i = 0; while (BN_cmp(&mult, &stop) < 0) { u_long rem; if (i && base > 16) putcharwrap(f, ' '); i = 1; bmul_number(fract_part, fract_part, num_base, bmachine_scale()); split_number(fract_part, int_part->number, NULL); rem = BN_get_word(int_part->number); p = get_digit(rem, digits, base); int_part->scale = 0; normalize(int_part, fract_part->scale); bn_check(BN_sub(fract_part->number, fract_part->number, int_part->number)); printwrap(f, p); free(p); bn_check(BN_mul_word(&mult, base)); } free_number(num_base); BN_free(&mult); BN_free(&stop); } flushwrap(f); free_number(int_part); free_number(fract_part); } void print_value(FILE *f, const struct value *value, const char *prefix, u_int base) { fputs(prefix, f); switch (value->type) { case BCODE_NONE: if (value->array != NULL) fputs("", f); break; case BCODE_NUMBER: printnumber(f, value->u.num, base); break; case BCODE_STRING: fputs(value->u.string, f); break; } } void print_ascii(FILE *f, const struct number *n) { BIGNUM *v; int ch, i, numbits; v = BN_dup(n->number); bn_checkp(v); if (BN_is_negative(v)) BN_set_negative(v, 0); numbits = BN_num_bytes(v) * 8; while (numbits > 0) { ch = 0; for (i = 0; i < 8; i++) ch |= BN_is_bit_set(v, numbits-i-1) << (7 - i); putc(ch, f); numbits -= 8; } BN_free(v); } Index: head/usr.bin/dc/mem.c =================================================================== --- head/usr.bin/dc/mem.c (revision 314703) +++ head/usr.bin/dc/mem.c (revision 314704) @@ -1,110 +1,110 @@ -/* $OpenBSD: mem.c,v 1.5 2009/10/27 23:59:37 deraadt Exp $ */ +/* $OpenBSD: mem.c,v 1.6 2014/12/01 13:13:00 deraadt Exp $ */ /* * Copyright (c) 2003, Otto Moerbeek * * Permission to use, copy, modify, and distribute this software for any * purpose with or without fee is hereby granted, provided that the above * copyright notice and this permission notice appear in all copies. * * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ #include __FBSDID("$FreeBSD$"); #include #include #include #include #include "extern.h" struct number * new_number(void) { struct number *n; n = bmalloc(sizeof(*n)); n->scale = 0; n->number = BN_new(); if (n->number == NULL) err(1, NULL); return (n); } void free_number(struct number *n) { BN_free(n->number); free(n); } struct number * dup_number(const struct number *a) { struct number *n; n = bmalloc(sizeof(*n)); n->scale = a->scale; n->number = BN_dup(a->number); bn_checkp(n->number); return (n); } void * bmalloc(size_t sz) { void *p; p = malloc(sz); if (p == NULL) err(1, NULL); return (p); } void * -brealloc(void *p, size_t sz) +breallocarray(void *p, size_t nmemb, size_t size) { void *q; - q = realloc(p, sz); + q = reallocarray(p, nmemb, size); if (q == NULL) err(1, NULL); return (q); } char * bstrdup(const char *p) { char *q; q = strdup(p); if (q == NULL) err(1, NULL); return (q); } void bn_check(int x) \ { if (x == 0) err(1, "big number failure %lx", ERR_get_error()); } void bn_checkp(const void *p) \ { if (p == NULL) err(1, "allocation failure %lx", ERR_get_error()); } Index: head/usr.bin/dc/stack.c =================================================================== --- head/usr.bin/dc/stack.c (revision 314703) +++ head/usr.bin/dc/stack.c (revision 314704) @@ -1,372 +1,372 @@ -/* $OpenBSD: stack.c,v 1.12 2014/11/26 15:05:51 otto Exp $ */ +/* $OpenBSD: stack.c,v 1.13 2014/12/01 13:13:00 deraadt Exp $ */ /* * Copyright (c) 2003, Otto Moerbeek * * Permission to use, copy, modify, and distribute this software for any * purpose with or without fee is hereby granted, provided that the above * copyright notice and this permission notice appear in all copies. * * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ #include __FBSDID("$FreeBSD$"); #include #include #include #include "extern.h" static __inline bool stack_empty(const struct stack *); static void stack_grow(struct stack *); static struct array *array_new(void); static __inline void array_free(struct array *); static struct array *array_dup(const struct array *); static __inline void array_grow(struct array *, size_t); static __inline void array_assign(struct array *, size_t, const struct value *); static __inline struct value *array_retrieve(const struct array *, size_t); void stack_init(struct stack *stack) { stack->size = 0; stack->sp = -1; stack->stack = NULL; } static __inline bool stack_empty(const struct stack *stack) { bool empty = stack->sp == -1; if (empty) warnx("stack empty"); return empty; } /* Clear number or string, but leave value itself */ void stack_free_value(struct value *v) { switch (v->type) { case BCODE_NONE: break; case BCODE_NUMBER: free_number(v->u.num); break; case BCODE_STRING: free(v->u.string); break; } array_free(v->array); v->array = NULL; } /* Copy number or string content into already allocated target */ struct value * stack_dup_value(const struct value *a, struct value *copy) { copy->type = a->type; switch (a->type) { case BCODE_NONE: break; case BCODE_NUMBER: copy->u.num = dup_number(a->u.num); break; case BCODE_STRING: copy->u.string = strdup(a->u.string); if (copy->u.string == NULL) err(1, NULL); break; } copy->array = a->array == NULL ? NULL : array_dup(a->array); return (copy); } size_t stack_size(const struct stack *stack) { return (stack->sp + 1); } void stack_dup(struct stack *stack) { struct value *value; struct value copy; value = stack_tos(stack); if (value == NULL) { warnx("stack empty"); return; } stack_push(stack, stack_dup_value(value, ©)); } void stack_swap(struct stack *stack) { struct value copy; if (stack->sp < 1) { warnx("stack empty"); return; } copy = stack->stack[stack->sp]; stack->stack[stack->sp] = stack->stack[stack->sp-1]; stack->stack[stack->sp-1] = copy; } static void stack_grow(struct stack *stack) { size_t new_size; if (++stack->sp == stack->size) { new_size = stack->size * 2 + 1; - stack->stack = brealloc(stack->stack, - new_size * sizeof(*stack->stack)); + stack->stack = breallocarray(stack->stack, + new_size, sizeof(*stack->stack)); stack->size = new_size; } } void stack_pushnumber(struct stack *stack, struct number *b) { stack_grow(stack); stack->stack[stack->sp].type = BCODE_NUMBER; stack->stack[stack->sp].u.num = b; stack->stack[stack->sp].array = NULL; } void stack_pushstring(struct stack *stack, char *string) { stack_grow(stack); stack->stack[stack->sp].type = BCODE_STRING; stack->stack[stack->sp].u.string = string; stack->stack[stack->sp].array = NULL; } void stack_push(struct stack *stack, struct value *v) { switch (v->type) { case BCODE_NONE: stack_grow(stack); stack->stack[stack->sp].type = BCODE_NONE; break; case BCODE_NUMBER: stack_pushnumber(stack, v->u.num); break; case BCODE_STRING: stack_pushstring(stack, v->u.string); break; } stack->stack[stack->sp].array = v->array == NULL ? NULL : array_dup(v->array); } struct value * stack_tos(const struct stack *stack) { if (stack->sp == -1) return (NULL); return &stack->stack[stack->sp]; } void stack_set_tos(struct stack *stack, struct value *v) { if (stack->sp == -1) stack_push(stack, v); else { stack_free_value(&stack->stack[stack->sp]); stack->stack[stack->sp] = *v; stack->stack[stack->sp].array = v->array == NULL ? NULL : array_dup(v->array); } } struct value * stack_pop(struct stack *stack) { if (stack_empty(stack)) return (NULL); return &stack->stack[stack->sp--]; } struct number * stack_popnumber(struct stack *stack) { if (stack_empty(stack)) return (NULL); array_free(stack->stack[stack->sp].array); stack->stack[stack->sp].array = NULL; if (stack->stack[stack->sp].type != BCODE_NUMBER) { warnx("not a number"); /* XXX remove */ return (NULL); } return stack->stack[stack->sp--].u.num; } char * stack_popstring(struct stack *stack) { if (stack_empty(stack)) return (NULL); array_free(stack->stack[stack->sp].array); stack->stack[stack->sp].array = NULL; if (stack->stack[stack->sp].type != BCODE_STRING) { warnx("not a string"); /* XXX remove */ return (NULL); } return stack->stack[stack->sp--].u.string; } void stack_clear(struct stack *stack) { while (stack->sp >= 0) stack_free_value(&stack->stack[stack->sp--]); free(stack->stack); stack_init(stack); } void stack_print(FILE *f, const struct stack *stack, const char *prefix, u_int base) { ssize_t i; for (i = stack->sp; i >= 0; i--) { print_value(f, &stack->stack[i], prefix, base); putc('\n', f); } } static struct array * array_new(void) { struct array *a; a = bmalloc(sizeof(*a)); a->data = NULL; a->size = 0; return a; } static __inline void array_free(struct array *a) { size_t i; if (a == NULL) return; for (i = 0; i < a->size; i++) stack_free_value(&a->data[i]); free(a->data); free(a); } static struct array * array_dup(const struct array *a) { struct array *n; size_t i; if (a == NULL) return (NULL); n = array_new(); array_grow(n, a->size); for (i = 0; i < a->size; i++) stack_dup_value(&a->data[i], &n->data[i]); return (n); } static __inline void array_grow(struct array *array, size_t newsize) { size_t i; - array->data = brealloc(array->data, newsize * sizeof(*array->data)); + array->data = breallocarray(array->data, newsize, sizeof(*array->data)); for (i = array->size; i < newsize; i++) { array->data[i].type = BCODE_NONE; array->data[i].array = NULL; } array->size = newsize; } static __inline void array_assign(struct array *array, size_t i, const struct value *v) { if (i >= array->size) array_grow(array, i + 1); stack_free_value(&array->data[i]); array->data[i] = *v; } static __inline struct value * array_retrieve(const struct array *array, size_t i) { if (i >= array->size) return (NULL); return &array->data[i]; } void frame_assign(struct stack *stack, size_t i, const struct value *v) { struct array *a; struct value n; if (stack->sp == -1) { n.type = BCODE_NONE; n.array = NULL; stack_push(stack, &n); } a = stack->stack[stack->sp].array; if (a == NULL) a = stack->stack[stack->sp].array = array_new(); array_assign(a, i, v); } struct value * frame_retrieve(const struct stack *stack, size_t i) { struct array *a; if (stack->sp == -1) return (NULL); a = stack->stack[stack->sp].array; if (a == NULL) a = stack->stack[stack->sp].array = array_new(); return array_retrieve(a, i); } Index: head/usr.bin/patch/inp.c =================================================================== --- head/usr.bin/patch/inp.c (revision 314703) +++ head/usr.bin/patch/inp.c (revision 314704) @@ -1,433 +1,433 @@ /*- * Copyright 1986, Larry Wall * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following condition is met: * 1. Redistributions of source code must retain the above copyright notice, * this condition and the following disclaimer. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND ANY * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * patch - a program to apply diffs to original files * * -C option added in 1998, original code by Marc Espie, based on FreeBSD * behaviour * - * $OpenBSD: inp.c,v 1.36 2012/04/10 14:46:34 ajacoutot Exp $ + * $OpenBSD: inp.c,v 1.44 2015/07/26 14:32:19 millert Exp $ * $FreeBSD$ */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include "common.h" #include "util.h" #include "pch.h" #include "inp.h" /* Input-file-with-indexable-lines abstract type */ static size_t i_size; /* size of the input file */ static char *i_womp; /* plan a buffer for entire file */ static char **i_ptr; /* pointers to lines in i_womp */ static char empty_line[] = { '\0' }; static int tifd = -1; /* plan b virtual string array */ static char *tibuf[2]; /* plan b buffers */ static LINENUM tiline[2] = {-1, -1}; /* 1st line in each buffer */ static size_t lines_per_buf; /* how many lines per buffer */ static size_t tibuflen; /* plan b buffer length */ static size_t tireclen; /* length of records in tmp file */ static bool rev_in_string(const char *); static bool reallocate_lines(size_t *); /* returns false if insufficient memory */ static bool plan_a(const char *); static void plan_b(const char *); /* New patch--prepare to edit another file. */ void re_input(void) { if (using_plan_a) { free(i_ptr); i_ptr = NULL; if (i_womp != NULL) { munmap(i_womp, i_size); i_womp = NULL; } i_size = 0; } else { using_plan_a = true; /* maybe the next one is smaller */ close(tifd); tifd = -1; free(tibuf[0]); free(tibuf[1]); tibuf[0] = tibuf[1] = NULL; tiline[0] = tiline[1] = -1; tireclen = 0; } } /* Construct the line index, somehow or other. */ void scan_input(const char *filename) { if (!plan_a(filename)) plan_b(filename); if (verbose) { say("Patching file %s using Plan %s...\n", filename, (using_plan_a ? "A" : "B")); } } static bool reallocate_lines(size_t *lines_allocated) { char **p; size_t new_size; new_size = *lines_allocated * 3 / 2; - p = realloc(i_ptr, (new_size + 2) * sizeof(char *)); + p = reallocarray(i_ptr, new_size + 2, sizeof(char *)); if (p == NULL) { /* shucks, it was a near thing */ munmap(i_womp, i_size); i_womp = NULL; free(i_ptr); i_ptr = NULL; *lines_allocated = 0; return false; } *lines_allocated = new_size; i_ptr = p; return true; } /* Try keeping everything in memory. */ static bool plan_a(const char *filename) { int ifd, statfailed; char *p, *s; struct stat filestat; ptrdiff_t sz; size_t i; size_t iline, lines_allocated; #ifdef DEBUGGING if (debug & 8) return false; #endif if (filename == NULL || *filename == '\0') return false; statfailed = stat(filename, &filestat); if (statfailed && ok_to_create_file) { if (verbose) say("(Creating file %s...)\n", filename); /* * in check_patch case, we still display `Creating file' even * though we're not. The rule is that -C should be as similar * to normal patch behavior as possible */ if (check_only) return true; makedirs(filename, true); close(creat(filename, 0666)); statfailed = stat(filename, &filestat); } if (statfailed) fatal("can't find %s\n", filename); filemode = filestat.st_mode; if (!S_ISREG(filemode)) fatal("%s is not a normal file--can't patch\n", filename); if ((uint64_t)filestat.st_size > SIZE_MAX) { say("block too large to mmap\n"); return false; } i_size = (size_t)filestat.st_size; if (out_of_mem) { set_hunkmax(); /* make sure dynamic arrays are allocated */ out_of_mem = false; return false; /* force plan b because plan a bombed */ } if ((ifd = open(filename, O_RDONLY)) < 0) pfatal("can't open file %s", filename); if (i_size) { i_womp = mmap(NULL, i_size, PROT_READ, MAP_PRIVATE, ifd, 0); if (i_womp == MAP_FAILED) { perror("mmap failed"); i_womp = NULL; close(ifd); return false; } } else { i_womp = NULL; } close(ifd); if (i_size) madvise(i_womp, i_size, MADV_SEQUENTIAL); /* estimate the number of lines */ lines_allocated = i_size / 25; if (lines_allocated < 100) lines_allocated = 100; if (!reallocate_lines(&lines_allocated)) return false; /* now scan the buffer and build pointer array */ iline = 1; i_ptr[iline] = i_womp; /* test for NUL too, to maintain the behavior of the original code */ for (s = i_womp, i = 0; i < i_size && *s != '\0'; s++, i++) { if (*s == '\n') { if (iline == lines_allocated) { if (!reallocate_lines(&lines_allocated)) return false; } /* these are NOT NUL terminated */ i_ptr[++iline] = s + 1; } } /* if the last line contains no EOL, append one */ if (i_size > 0 && i_womp[i_size - 1] != '\n') { last_line_missing_eol = true; /* fix last line */ sz = s - i_ptr[iline]; p = malloc(sz + 1); if (p == NULL) { free(i_ptr); i_ptr = NULL; munmap(i_womp, i_size); i_womp = NULL; return false; } memcpy(p, i_ptr[iline], sz); p[sz] = '\n'; i_ptr[iline] = p; /* count the extra line and make it point to some valid mem */ i_ptr[++iline] = empty_line; } else last_line_missing_eol = false; input_lines = iline - 1; /* now check for revision, if any */ if (revision != NULL) { if (i_womp == NULL || !rev_in_string(i_womp)) { if (force) { if (verbose) say("Warning: this file doesn't appear " "to be the %s version--patching anyway.\n", revision); } else if (batch) { fatal("this file doesn't appear to be the " "%s version--aborting.\n", revision); } else { ask("This file doesn't appear to be the " "%s version--patch anyway? [n] ", revision); if (*buf != 'y') fatal("aborted\n"); } } else if (verbose) say("Good. This file appears to be the %s version.\n", revision); } return true; /* plan a will work */ } /* Keep (virtually) nothing in memory. */ static void plan_b(const char *filename) { FILE *ifp; size_t i = 0, j, len, maxlen = 1; char *lbuf = NULL, *p; bool found_revision = (revision == NULL); using_plan_a = false; if ((ifp = fopen(filename, "r")) == NULL) pfatal("can't open file %s", filename); unlink(TMPINNAME); if ((tifd = open(TMPINNAME, O_EXCL | O_CREAT | O_WRONLY, 0666)) < 0) pfatal("can't open file %s", TMPINNAME); while ((p = fgetln(ifp, &len)) != NULL) { if (p[len - 1] == '\n') p[len - 1] = '\0'; else { /* EOF without EOL, copy and add the NUL */ if ((lbuf = malloc(len + 1)) == NULL) fatal("out of memory\n"); memcpy(lbuf, p, len); lbuf[len] = '\0'; p = lbuf; last_line_missing_eol = true; len++; } if (revision != NULL && !found_revision && rev_in_string(p)) found_revision = true; if (len > maxlen) maxlen = len; /* find longest line */ } free(lbuf); if (ferror(ifp)) pfatal("can't read file %s", filename); if (revision != NULL) { if (!found_revision) { if (force) { if (verbose) say("Warning: this file doesn't appear " "to be the %s version--patching anyway.\n", revision); } else if (batch) { fatal("this file doesn't appear to be the " "%s version--aborting.\n", revision); } else { ask("This file doesn't appear to be the %s " "version--patch anyway? [n] ", revision); if (*buf != 'y') fatal("aborted\n"); } } else if (verbose) say("Good. This file appears to be the %s version.\n", revision); } fseek(ifp, 0L, SEEK_SET); /* rewind file */ tireclen = maxlen; tibuflen = maxlen > BUFFERSIZE ? maxlen : BUFFERSIZE; lines_per_buf = tibuflen / maxlen; tibuf[0] = malloc(tibuflen + 1); if (tibuf[0] == NULL) fatal("out of memory\n"); tibuf[1] = malloc(tibuflen + 1); if (tibuf[1] == NULL) fatal("out of memory\n"); for (i = 1;; i++) { p = tibuf[0] + maxlen * (i % lines_per_buf); if (i % lines_per_buf == 0) /* new block */ if (write(tifd, tibuf[0], tibuflen) != (ssize_t) tibuflen) pfatal("can't write temp file"); if (fgets(p, maxlen + 1, ifp) == NULL) { input_lines = i - 1; if (i % lines_per_buf != 0) if (write(tifd, tibuf[0], tibuflen) != (ssize_t) tibuflen) pfatal("can't write temp file"); break; } j = strlen(p); /* These are '\n' terminated strings, so no need to add a NUL */ if (j == 0 || p[j - 1] != '\n') p[j] = '\n'; } fclose(ifp); close(tifd); if ((tifd = open(TMPINNAME, O_RDONLY)) < 0) pfatal("can't reopen file %s", TMPINNAME); } /* * Fetch a line from the input file, \n terminated, not necessarily \0. */ char * ifetch(LINENUM line, int whichbuf) { if (line < 1 || line > input_lines) { if (warn_on_invalid_line) { say("No such line %ld in input file, ignoring\n", line); warn_on_invalid_line = false; } return NULL; } if (using_plan_a) return i_ptr[line]; else { LINENUM offline = line % lines_per_buf; LINENUM baseline = line - offline; if (tiline[0] == baseline) whichbuf = 0; else if (tiline[1] == baseline) whichbuf = 1; else { tiline[whichbuf] = baseline; if (lseek(tifd, (off_t) (baseline / lines_per_buf * tibuflen), SEEK_SET) < 0) pfatal("cannot seek in the temporary input file"); if (read(tifd, tibuf[whichbuf], tibuflen) != (ssize_t) tibuflen) pfatal("error reading tmp file %s", TMPINNAME); } return tibuf[whichbuf] + (tireclen * offline); } } /* * True if the string argument contains the revision number we want. */ static bool rev_in_string(const char *string) { const char *s; size_t patlen; if (revision == NULL) return true; patlen = strlen(revision); if (strnEQ(string, revision, patlen) && isspace((unsigned char)string[patlen])) return true; for (s = string; *s; s++) { if (isspace((unsigned char)*s) && strnEQ(s + 1, revision, patlen) && isspace((unsigned char)s[patlen + 1])) { return true; } } return false; }