diff options
-rw-r--r-- | ObsoleteFiles.inc | 7 | ||||
-rw-r--r-- | gnu/usr.bin/Makefile | 4 | ||||
-rw-r--r-- | usr.bin/Makefile | 2 | ||||
-rw-r--r-- | usr.bin/bc/Makefile | 17 | ||||
-rw-r--r-- | usr.bin/bc/USD.doc/Makefile | 13 | ||||
-rw-r--r-- | usr.bin/bc/USD.doc/bc | 1241 | ||||
-rw-r--r-- | usr.bin/bc/bc.1 | 400 | ||||
-rw-r--r-- | usr.bin/bc/bc.library | 263 | ||||
-rw-r--r-- | usr.bin/bc/bc.y | 1179 | ||||
-rw-r--r-- | usr.bin/bc/extern.h | 38 | ||||
-rw-r--r-- | usr.bin/bc/pathnames.h | 21 | ||||
-rw-r--r-- | usr.bin/bc/scan.l | 288 | ||||
-rw-r--r-- | usr.bin/dc/Makefile | 13 | ||||
-rw-r--r-- | usr.bin/dc/USD.doc/Makefile | 16 | ||||
-rw-r--r-- | usr.bin/dc/USD.doc/dc | 753 | ||||
-rw-r--r-- | usr.bin/dc/bcode.c | 1781 | ||||
-rw-r--r-- | usr.bin/dc/bcode.h | 98 | ||||
-rw-r--r-- | usr.bin/dc/dc.1 | 552 | ||||
-rw-r--r-- | usr.bin/dc/dc.c | 140 | ||||
-rw-r--r-- | usr.bin/dc/extern.h | 63 | ||||
-rw-r--r-- | usr.bin/dc/inout.c | 417 | ||||
-rw-r--r-- | usr.bin/dc/mem.c | 110 | ||||
-rw-r--r-- | usr.bin/dc/stack.c | 379 |
23 files changed, 7792 insertions, 3 deletions
diff --git a/ObsoleteFiles.inc b/ObsoleteFiles.inc index 5dc0e3e..1828449 100644 --- a/ObsoleteFiles.inc +++ b/ObsoleteFiles.inc @@ -14,6 +14,13 @@ # The file is partitioned: OLD_FILES first, then OLD_LIBS and OLD_DIRS last. # +# 20100120: replacing GNU bc/dc with BSDL versions +OLD_FILES+=usr/share/examples/bc/ckbook.b +OLD_FILES+=usr/share/examples/bc/pi.b +OLD_FILES+=usr/share/examples/bc/primes.b +OLD_FILES+=usr/share/examples/bc/twins.b +OLD_FILES+=usr/share/info/dc.info.gz +OLD_DIRS+=usr/share/examples/bc # 20100114: removal of ttyslot(3) OLD_FILES+=usr/share/man/man3/ttyslot.3.gz # 20100113: remove utmp.h, replace it by utmpx.h diff --git a/gnu/usr.bin/Makefile b/gnu/usr.bin/Makefile index 82792df..cc50659 100644 --- a/gnu/usr.bin/Makefile +++ b/gnu/usr.bin/Makefile @@ -2,12 +2,10 @@ .include <bsd.own.mk> -SUBDIR= bc \ - ${_binutils} \ +SUBDIR= ${_binutils} \ ${_cc} \ ${_cpio} \ ${_cvs} \ - dc \ dialog \ diff \ diff3 \ diff --git a/usr.bin/Makefile b/usr.bin/Makefile index 1917ae2..19f4296 100644 --- a/usr.bin/Makefile +++ b/usr.bin/Makefile @@ -18,6 +18,7 @@ SUBDIR= alias \ awk \ banner \ basename \ + bc \ ${_biff} \ ${_bluetooth} \ brandelf \ @@ -49,6 +50,7 @@ SUBDIR= alias \ ${_csup} \ ${_ctags} \ cut \ + dc \ ${_dig} \ dirname \ du \ diff --git a/usr.bin/bc/Makefile b/usr.bin/bc/Makefile new file mode 100644 index 0000000..e291555 --- /dev/null +++ b/usr.bin/bc/Makefile @@ -0,0 +1,17 @@ +# $FreeBSD$ +# $OpenBSD: Makefile,v 1.4 2006/06/30 19:02:28 otto Exp $ + +PROG= bc +SRCS= bc.y scan.l +CFLAGS+= -I. -I${.CURDIR} +WARNS?= 6 +#SUBDIR+= USD.doc + +FILES+= bc.library +FILESDIR= ${SHAREDIR}/misc + +#beforeinstall: +# install -c -o ${BINOWN} -g ${BINGRP} -m 444 ${.CURDIR}/bc.library \ +# ${DESTDIR}/usr/share/misc + +.include <bsd.prog.mk> diff --git a/usr.bin/bc/USD.doc/Makefile b/usr.bin/bc/USD.doc/Makefile new file mode 100644 index 0000000..44265d2 --- /dev/null +++ b/usr.bin/bc/USD.doc/Makefile @@ -0,0 +1,13 @@ +# $FreeBSD$ +# $OpenBSD: Makefile,v 1.3 2004/02/01 15:18:01 jmc Exp $ + +DOC= bc +DIR= usd/06.bc +SRCS= bc +MACROS= -ms +BINDIR= /usr/share/doc/papers + +paper.txt: ${SRCS} + ${ROFF} -Tascii ${SRCS} > ${.TARGET} + +.include <bsd.doc.mk> diff --git a/usr.bin/bc/USD.doc/bc b/usr.bin/bc/USD.doc/bc new file mode 100644 index 0000000..c4e68c6 --- /dev/null +++ b/usr.bin/bc/USD.doc/bc @@ -0,0 +1,1241 @@ +.\" $FreeBSD$ +.\" $OpenBSD: bc,v 1.9 2004/07/09 10:23:05 jmc Exp $ +.\" +.\" Copyright (C) Caldera International Inc. 2001-2002. +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code and documentation must retain the above +.\" copyright notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. All advertising materials mentioning features or use of this software +.\" must display the following acknowledgement: +.\" This product includes software developed or owned by Caldera +.\" International, Inc. +.\" 4. Neither the name of Caldera International, Inc. nor the names of other +.\" contributors may be used to endorse or promote products derived from +.\" this software without specific prior written permission. +.\" +.\" USE OF THE SOFTWARE PROVIDED FOR UNDER THIS LICENSE BY CALDERA +.\" INTERNATIONAL, INC. 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 CALDERA INTERNATIONAL, INC. 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. +.\" +.\" @(#)bc 6.2 (Berkeley) 4/17/91 +.\" +.if n \{\ +.po 5n +.ll 70n +.\} +.EH 'USD:6-%''BC \- An Arbitrary Precision Desk-Calculator Language' +.OH 'BC \- An Arbitrary Precision Desk-Calculator Language''USD:6-%' +.\".RP +.TL +BC \- An Arbitrary Precision Desk-Calculator Language +.AU +Lorinda Cherry +.AU +Robert Morris +.AI +.\" .MH +.AB +BC is a language and a compiler for doing arbitrary precision arithmetic +on the PDP-11 under the +.UX +time-sharing +system. The output of the compiler is interpreted and executed by +a collection of routines which can input, output, and do +arithmetic on indefinitely large integers and on scaled fixed-point +numbers. +.PP +These routines are themselves based on a dynamic storage allocator. +Overflow does not occur until all available core storage +is exhausted. +.PP +The language has a complete control structure as well as immediate-mode +operation. Functions can be defined and saved for later execution. +.PP +Two five hundred-digit numbers can be multiplied to give a +thousand digit result in about ten seconds. +.PP +A small collection of library functions is also available, +including sin, cos, arctan, log, exponential, and Bessel functions of +integer order. +.PP +Some of the uses of this compiler are +.IP \- +to do computation with large integers, +.IP \- +to do computation accurate to many decimal places, +.IP \- +conversion of numbers from one base to another base. +.AE +.PP +.SH +Introduction +.PP +BC is a language and a compiler for doing arbitrary precision +arithmetic on the +.UX +time-sharing system [1]. +The compiler was written to make conveniently available a +collection of routines (called DC [5]) which are capable of doing +arithmetic on integers of arbitrary size. The compiler +is by no means intended to provide a complete programming +language. +It is a minimal language facility. +.PP +There is a scaling provision that permits the +use of decimal point notation. +Provision is made for input and output in bases other than +decimal. Numbers can be converted from decimal to octal by +simply setting the output base to equal 8. +.PP +The actual limit on the number of digits that can +be handled depends on the amount of storage available on the machine. +Manipulation of numbers with many hundreds of digits +is possible even on the smallest versions of +.UX . +.PP +The syntax of BC has been deliberately selected to agree +substantially with the C language [2]. Those who +are familiar with C will find few surprises in this language. +.SH +Simple Computations with Integers +.PP +The simplest kind of statement is an arithmetic expression +on a line by itself. +For instance, if you type in the line: +.DS +.ft B +142857 + 285714 +.ft P +.DE +the program responds immediately with the line +.DS +.ft B +428571 +.ft P +.DE +The operators \-, *, /, %, and ^ can also be used; they +indicate subtraction, multiplication, division, remaindering, and +exponentiation, respectively. Division of integers produces an +integer result truncated toward zero. +Division by zero produces an error +comment. +.PP +Any term in an expression may be prefixed by a minus sign to +indicate that it is to be negated (the `unary' minus sign). +The expression +.DS +.ft B +7+\-3 +.ft P +.DE +is interpreted to mean that \-3 is to be added to 7. +.PP +More complex expressions with several operators and with +parentheses are interpreted just as in +Fortran, with ^ having the greatest binding +power, then * and % and /, and finally + and \-. +Contents of parentheses are evaluated before material +outside the parentheses. +Exponentiations are +performed from right to left and the other operators +from left to right. +The two expressions +.DS +.ft B +a^b^c and a^(b^c) +.ft P +.DE +are equivalent, as are the two expressions +.DS +.ft B +a*b*c and (a*b)*c +.ft P +.DE +BC shares with Fortran and C the undesirable convention that +.DS +\fBa/b*c\fP is equivalent to \fB(a/b)*c\fP +.ft P +.DE +.PP +Internal storage registers to hold numbers have single lower-case +letter names. The value of an expression can be assigned to +a register in the usual way. The statement +.DS +.ft B +x = x + 3 +.ft P +.DE +has the effect of increasing by three the value of the contents of the +register named x. +When, as in this case, the outermost operator is an =, the +assignment is performed but the result is not printed. +Only 26 of these named storage registers are available. +.PP +There is a built-in square root function whose +result is truncated to an integer (but see scaling below). +The lines +.DS +.ft B +x = sqrt(191) +x +.ft P +.DE +produce the printed result +.DS +.ft B +13 +.ft P +.DE +.SH +Bases +.PP +There are special internal quantities, called `ibase' and `obase'. +The contents of `ibase', initially set to 10, +determines the base used for interpreting numbers read in. +For example, the lines +.DS +.ft B +ibase = 8 +11 +.ft P +.DE +will produce the output line +.DS +.ft B +9 +.ft P +.DE +and you are all set up to do octal to decimal conversions. +Beware, however of trying to change the input base back +to decimal by typing +.DS +.ft B +ibase = 10 +.ft P +.DE +Because the number 10 is interpreted as octal, this statement will +have no effect. +For those who deal in hexadecimal notation, +the characters A\-F are permitted in numbers +(no matter what base is in effect) +and are +interpreted as digits having values 10\-15 respectively. +The statement +.DS +.ft B +ibase = A +.ft P +.DE +will change you back to decimal input base no matter what the +current input base is. +Negative and large positive input bases are +permitted but useless. +No mechanism has been provided for the input of arbitrary +numbers in bases less than 1 and greater than 16. +.PP +The contents of `obase', initially set to 10, are used as the base for output +numbers. The lines +.DS +.ft B +obase = 16 +1000 +.ft P +.DE +will produce the output line +.DS +.ft B +3E8 +.ft P +.DE +which is to be interpreted as a 3-digit hexadecimal number. +Very large output bases are permitted, and they are sometimes useful. +For example, large numbers can be output in groups of five digits +by setting `obase' to 100000. +Strange (i.e. 1, 0, or negative) output bases are +handled appropriately. +.PP +Very large numbers are split across lines with 70 characters per line. +Lines which are continued end with \\. +Decimal output conversion is practically instantaneous, but output +of very large numbers (i.e., more than 100 digits) with other bases +is rather slow. +Non-decimal output conversion of +a one hundred digit number takes about +three seconds. +.PP +It is best to remember that `ibase' and `obase' have no effect +whatever on the course of internal computation or +on the evaluation of expressions, but only affect input and +output conversion, respectively. +.SH +Scaling +.PP +A third special internal quantity called `scale' is +used to determine the scale of calculated +quantities. +Numbers may have +up to a specific number of decimal digits after the decimal point. +This fractional part is retained in further computations. +We refer to the number of digits after the decimal point of +a number as its scale. +The current implementation allows scales to be as large as can be +represented by a 32-bit unsigned number minus one. +This is a non-portable extension. +The original implementation allowed for a maximum scale of 99. +.PP +When two scaled numbers are combined by +means of one of the arithmetic operations, the result +has a scale determined by the following rules. For +addition and subtraction, the scale of the result is the larger +of the scales of the two operands. In this case, +there is never any truncation of the result. +For multiplications, the scale of the result is never +less than the maximum of the two scales of the operands, +never more than the sum of the scales of the operands +and, subject to those two restrictions, +the scale of the result is set equal to the contents of the internal +quantity `scale'. +The scale of a quotient is the contents of the internal +quantity `scale'. The scale of a remainder is +the sum of the scales of the quotient and the divisor. +The result of an exponentiation is scaled as if +the implied multiplications were performed. +An exponent must be an integer. +The scale of a square root is set to the maximum of the scale +of the argument and the contents of `scale'. +.PP +All of the internal operations are actually carried out in terms +of integers, with digits being discarded when necessary. +In every case where digits are discarded, truncation and +not rounding is performed. +.PP +The contents of +`scale' must be no greater than +4294967294 and no less than 0. It is initially set to 0. +.PP +The internal quantities `scale', `ibase', and `obase' can be +used in expressions just like other variables. +The line +.DS +.ft B +scale = scale + 1 +.ft P +.DE +increases the value of `scale' by one, and the line +.DS +.ft B +scale +.ft P +.DE +causes the current value of `scale' to be printed. +.PP +The value of `scale' retains its meaning as a +number of decimal digits to be retained in internal +computation even when `ibase' or `obase' are not equal to 10. +The internal computations (which are still conducted in decimal, +regardless of the bases) are performed to the specified number +of decimal digits, never hexadecimal or octal or any +other kind of digits. +.SH +Functions +.PP +The name of a function is a single lower-case letter. +Function names are permitted to collide with simple +variable names. +Twenty-six different defined functions are permitted +in addition to the twenty-six variable names. +The line +.DS +.ft B + define a(x){ +.ft P +.DE +begins the definition of a function with one argument. +This line must be followed by one or more statements, +which make up the body of the function, ending +with a right brace }. +Return of control from a function occurs when a return +statement is executed or when the end of the function is reached. +The return statement can take either +of the two forms +.DS +.ft B +return +return(x) +.ft P +.DE +In the first case, the value of the function is 0, and in +the second, the value of the expression in parentheses. +.PP +Variables used in the function can be declared as automatic +by a statement of the form +.DS +.ft B +auto x,y,z +.ft P +.DE +There can be only one `auto' statement in a function and it must +be the first statement in the definition. +These automatic variables are allocated space and initialized +to zero on entry to the function and thrown away on return. The +values of any variables with the same names outside the function +are not disturbed. +Functions may be called recursively and the automatic variables +at each level of call are protected. +The parameters named in a function definition are treated in +the same way as the automatic variables of that function +with the single exception that they are given a value +on entry to the function. +An example of a function definition is +.DS +.ft B + define a(x,y){ + auto z + z = x*y + return(z) + } +.ft P +.DE +The value of this function, when called, will be the +product of its +two arguments. +.PP +A function is called by the appearance of its name +followed by a string of arguments enclosed in +parentheses and separated by commas. +The result +is unpredictable if the wrong number of arguments is used. +.PP +Functions with no arguments are defined and called using +parentheses with nothing between them: b(). +.PP +If the function +.ft I +a +.ft +above has been defined, then the line +.DS +.ft B +a(7,3.14) +.ft P +.DE +would cause the result 21.98 to be printed and the line +.DS +.ft B +x = a(a(3,4),5) +.ft P +.DE +would cause the value of x to become 60. +.SH +Subscripted Variables +.PP +A single lower-case letter variable name +followed by an expression in brackets is called a subscripted +variable (an array element). +The variable name is called the array name and the expression +in brackets is called the subscript. +Only one-dimensional arrays are +permitted. The names of arrays are permitted to +collide with the names of simple variables and function names. +Any fractional +part of a subscript is discarded before use. +Subscripts must be greater than or equal to zero and +less than or equal to 2047. +.PP +Subscripted variables may be freely used in expressions, in +function calls, and in return statements. +.PP +An array name may be used as an argument to a function, +or may be declared as automatic in +a function definition by the use of empty brackets: +.DS +.ft B +f(a[\|]) +define f(a[\|]) +auto a[\|] +.ft P +.DE +When an array name is so used, the whole contents of the array +are copied for the use of the function, and thrown away on exit +from the function. +Array names which refer to whole arrays cannot be used +in any other contexts. +.SH +Control Statements +.PP +The `if', the `while', and the `for' statements +may be used to alter the flow within programs or to cause iteration. +The range of each of them is a statement or +a compound statement consisting of a collection of +statements enclosed in braces. +They are written in the following way +.DS +.ft B +if(relation) statement +if(relation) statement else statement +while(relation) statement +for(expression1; relation; expression2) statement +.ft P +.DE +or +.DS +.ft B +if(relation) {statements} +if(relation) {statements} else {statements} +while(relation) {statements} +for(expression1; relation; expression2) {statements} +.ft P +.DE +.PP +A relation in one of the control statements is an expression of the form +.DS +.ft B +x>y +.ft P +.DE +where two expressions are related by one of the six relational +operators `<', `>', `<=', `>=', `==', or `!='. +The relation `==' +stands for `equal to' and `!=' stands for `not equal to'. +The meaning of the remaining relational operators is +clear. +.PP +BEWARE of using `=' instead of `==' in a relational. Unfortunately, +both of them are legal, so you will not get a diagnostic +message, but `=' really will not do a comparison. +.PP +The `if' statement causes execution of its range +if and only if the relation is true. +Then control passes to the next statement in sequence. +If an `else' branch is present, the statements in this branch are +executed if the relation is false. +The `else' keyword is a non-portable extension. +.PP +The `while' statement causes execution of its range +repeatedly as long as the relation +is true. The relation is tested before each execution +of its range and if the relation +is false, control passes to the next statement beyond the range +of the while. +.PP +The `for' statement begins +by executing `expression1'. Then the relation is tested +and, if true, the statements in the range of the `for' are executed. +Then `expression2' is executed. The relation is tested, and so on. +The typical use of the `for' statement is for a controlled iteration, +as in the statement +.DS +.ft B +for(i=1; i<=10; i=i+1) i +.ft P +.DE +which will print the integers from 1 to 10. +Here are some examples of the use of the control statements. +.DS +.ft B +define f(n){ +auto i, x +x=1 +for(i=1; i<=n; i=i+1) x=x*i +return(x) +} +.ft P +.DE +The line +.DS +.ft B + f(a) +.ft P +.DE +will print +.ft I +a +.ft +factorial if +.ft I +a +.ft +is a positive integer. +Here is the definition of a function which will +compute values of the binomial coefficient +(m and n are assumed to be positive integers). +.DS +.ft B +define b(n,m){ +auto x, j +x=1 +for(j=1; j<=m; j=j+1) x=x*(n\-j+1)/j +return(x) +} +.ft P +.DE +The following function computes values of the exponential function +by summing the appropriate series +without regard for possible truncation errors: +.DS +.ft B +scale = 20 +define e(x){ + auto a, b, c, d, n + a = 1 + b = 1 + c = 1 + d = 0 + n = 1 + while(1==1){ + a = a*x + b = b*n + c = c + a/b + n = n + 1 + if(c==d) return(c) + d = c + } +} +.ft P +.DE +.SH +Some Details +.PP +There are some language features that every user should know +about even if he will not use them. +.PP +Normally statements are typed one to a line. It is also permissible +to type several statements on a line separated by semicolons. +.PP +If an assignment statement is parenthesized, it then has +a value and it can be used anywhere that an expression can. +For example, the line +.DS +.ft B +(x=y+17) +.ft P +.DE +not only makes the indicated assignment, but also prints the +resulting value. +.PP +Here is an example of a use of the value of an +assignment statement even when it is not parenthesized. +.DS +.ft B +x = a[i=i+1] +.ft P +.DE +causes a value to be assigned to x and also increments i +before it is used as a subscript. +.PP +The following constructs work in BC in exactly the same manner +as they do in the C language. Consult the appendix or the +C manuals [2] for their exact workings. +.DS +.ft B +.ta 2i +x=y=z is the same as x=(y=z) +x += y x = x+y +x \-= y x = x\-y +x *= y x = x*y +x /= y x = x/y +x %= y x = x%y +x ^= y x = x^y +x++ (x=x+1)\-1 +x\-\- (x=x\-1)+1 +++x x = x+1 +\-\-x x = x\-1 +.ft P +.DE +Even if you don't intend to use the constructs, +if you type one inadvertently, something correct but unexpected +may happen. +.SH +Three Important Things +.PP +1. To exit a BC program, type `quit'. +.PP +2. There is a comment convention identical to that of C and +of PL/I. Comments begin with `/*' and end with `*/'. +As a non-portable extension, comments may also start with a `#' and end with +a newline. +The newline is not part of the comment. +.PP +3. There is a library of math functions which may be obtained by +typing at command level +.DS +.ft B +bc \-l +.ft P +.DE +This command will load a set of library functions +which, at the time of writing, consists of sine (named `s'), +cosine (`c'), arctangent (`a'), natural logarithm (`l'), +exponential (`e') and Bessel functions of integer order (`j(n,x)'). Doubtless more functions will be added +in time. +The library sets the scale to 20. You can reset it to something +else if you like. +The design of these mathematical library routines +is discussed elsewhere [3]. +.PP +If you type +.DS +.ft B +bc file ... +.ft P +.DE +BC will read and execute the named file or files before accepting +commands from the keyboard. In this way, you may load your +favorite programs and function definitions. +.SH +Acknowledgement +.PP +The compiler is written in YACC [4]; its original +version was written by S. C. Johnson. +.SH +References +.IP [1] +K. Thompson and D. M. Ritchie, +.ft I +UNIX Programmer's Manual, +.ft +Bell Laboratories, +1978. +.IP [2] +B. W. Kernighan and +D. M. Ritchie, +.ft I +The C Programming Language, +.ft +Prentice-Hall, 1978. +.IP [3] +R. Morris, +.ft I +A Library of Reference Standard Mathematical Subroutines, +.ft +Bell Laboratories internal memorandum, 1975. +.IP [4] +S. C. Johnson, +.ft I +YACC \(em Yet Another Compiler-Compiler. +.ft +Bell Laboratories Computing Science Technical Report #32, 1978. +.IP [5] +R. Morris and L. L. Cherry, +.ft I +DC \- An Interactive Desk Calculator. +.ft +.LP +.bp +.ft B +.DS C +Appendix +.DE +.ft +.NH +Notation +.PP +In the following pages syntactic categories are in \fIitalics\fP; +literals are in \fBbold\fP; material in brackets [\|] is optional. +.NH +Tokens +.PP +Tokens consist of keywords, identifiers, constants, operators, +and separators. +Token separators may be blanks, tabs or comments. +Newline characters or semicolons separate statements. +.NH 2 +Comments +.PP +Comments are introduced by the characters /* and terminated by +*/. +As a non-portable extension, comments may also start with a # and +end with a newline. +The newline is not part of the comment. +.NH 2 +Identifiers +.PP +There are three kinds of identifiers \- ordinary identifiers, array identifiers +and function identifiers. +All three types consist of single lower-case letters. +Array identifiers are followed by square brackets, possibly +enclosing an expression describing a subscript. +Arrays are singly dimensioned and may contain up to 2048 +elements. +Indexing begins at zero so an array may be indexed from 0 to 2047. +Subscripts are truncated to integers. +Function identifiers are followed by parentheses, possibly enclosing arguments. +The three types of identifiers do not conflict; +a program can have a variable named \fBx\fP, +an array named \fBx\fP and a function named \fBx\fP, all of which are separate and +distinct. +.NH 2 +Keywords +.PP +The following are reserved keywords: +.ft B +.ta .5i 1.0i +.nf + ibase if + obase break + scale define + sqrt auto + length return + while quit + for continue + else last + print +.fi +.ft +.NH 2 +Constants +.PP +Constants consist of arbitrarily long numbers +with an optional decimal point. +The hexadecimal digits \fBA\fP\-\fBF\fP are also recognized as digits with +values 10\-15, respectively. +.NH 1 +Expressions +.PP +The value of an expression is printed unless the main +operator is an assignment. +The value printed is assigned to the special variable \fBlast\fP. +A single dot may be used as a synonym for \fBlast\fP. +This is a non-portable extension. +Precedence is the same as the order +of presentation here, with highest appearing first. +Left or right associativity, where applicable, is +discussed with each operator. +.bp +.NH 2 +Primitive expressions +.NH 3 +Named expressions +.PP +Named expressions are +places where values are stored. +Simply stated, +named expressions are legal on the left +side of an assignment. +The value of a named expression is the value stored in the place named. +.NH 4 +\fIidentifiers\fR +.PP +Simple identifiers are named expressions. +They have an initial value of zero. +.NH 4 +\fIarray-name\fP\|[\|\fIexpression\fP\|] +.PP +Array elements are named expressions. +They have an initial value of zero. +.NH 4 +\fBscale\fR, \fBibase\fR and \fBobase\fR +.PP +The internal registers +\fBscale\fP, \fBibase\fP and \fBobase\fP are all named expressions. +\fBscale\fP is the number of digits after the decimal point to be +retained in arithmetic operations. +\fBscale\fR has an initial value of zero. +\fBibase\fP and \fBobase\fP are the input and output number +radix respectively. +Both \fBibase\fR and \fBobase\fR have initial values of 10. +.NH 3 +Function calls +.NH 4 +\fIfunction-name\fB\|(\fR[\fIexpression\fR\|[\fB,\|\fIexpression\|\fR.\|.\|.\|]\|]\fB) +.PP +A function call consists of a function name followed by parentheses +containing a comma-separated list of +expressions, which are the function arguments. +A whole array passed as an argument is specified by the +array name followed by empty square brackets. +All function arguments are passed by +value. +As a result, changes made to the formal parameters have +no effect on the actual arguments. +If the function terminates by executing a return +statement, the value of the function is +the value of the expression in the parentheses of the return +statement or is zero if no expression is provided +or if there is no return statement. +.NH 4 +sqrt\|(\|\fIexpression\fP\|) +.PP +The result is the square root of the expression. +The result is truncated in the least significant decimal place. +The scale of the result is +the scale of the expression or the +value of +.ft B +scale, +.ft +whichever is larger. +.NH 4 +length\|(\|\fIexpression\fP\|) +.PP +The result is the total number of significant decimal digits in the expression. +The scale of the result is zero. +.NH 4 +scale\|(\|\fIexpression\fP\|) +.PP +The result is the scale of the expression. +The scale of the result is zero. +.NH 3 +Constants +.PP +Constants are primitive expressions. +.NH 3 +Parentheses +.PP +An expression surrounded by parentheses is +a primitive expression. +The parentheses are used to alter the +normal precedence. +.NH 2 +Unary operators +.PP +The unary operators +bind right to left. +.NH 3 +\-\|\fIexpression\fP +.PP +The result is the negative of the expression. +.NH 3 +++\|\fInamed-expression\fP +.PP +The named expression is +incremented by one. +The result is the value of the named expression after +incrementing. +.NH 3 +\-\-\|\fInamed-expression\fP +.PP +The named expression is +decremented by one. +The result is the value of the named expression after +decrementing. +.NH 3 +\fInamed-expression\fP\|++ +.PP +The named expression is +incremented by one. +The result is the value of the named expression before +incrementing. +.NH 3 +\fInamed-expression\fP\|\-\- +.PP +The named expression is +decremented by one. +The result is the value of the named expression before +decrementing. +.NH 2 +Exponentiation operator +.PP +The exponentiation operator binds right to left. +.NH 3 +\fIexpression\fP ^ \fIexpression\fP +.PP +The result is the first +expression raised to the power of the +second expression. +The second expression must be an integer. +If \fIa\fP +is the scale of the left expression +and \fIb\fP is the absolute value +of the right expression, +then the scale of the result is: +.PP +min\|(\|\fIa\(mub\fP,\|max\|(\|\fBscale\fP,\|\fIa\fP\|)\|) +.NH 2 +Multiplicative operators +.PP +The operators *, /, % bind left to right. +.NH 3 +\fIexpression\fP * \fIexpression\fP +.PP +The result is the product +of the two expressions. +If \fIa\fP and \fIb\fP are the +scales of the two expressions, +then the scale of the result is: +.PP +min\|(\|\fIa+b\fP,\|max\|(\|\fBscale\fP,\|\fIa\fP,\|\fIb\fP\|)\|) +.NH 3 +\fIexpression\fP / \fIexpression\fP +.PP +The result is the quotient of the two expressions. +The scale of the result is the value of \fBscale\fR. +.NH 3 +\fIexpression\fP % \fIexpression\fP +.PP +The % operator produces the remainder of the division +of the two expressions. +More precisely, +\fIa\fP%\fIb\fP is \fIa\fP\-\fIa\fP/\fIb\fP*\fIb\fP. +.PP +The scale of the result is the sum of the scale of +the divisor and the value of +.ft B +scale +.ft +.NH 2 +Additive operators +.PP +The additive operators bind left to right. +.NH 3 +\fIexpression\fP + \fIexpression\fP +.PP +The result is the sum of the two expressions. +The scale of the result is +the maximum of the scales of the expressions. +.NH 3 +\fIexpression\fP \- \fIexpression\fP +.PP +The result is the difference of the two expressions. +The scale of the result is the +maximum of the scales of the expressions. +.NH 2 +assignment operators +.PP +The assignment operators bind right to left. +.NH 3 +\fInamed-expression\fP = \fIexpression\fP +.PP +This expression results in assigning the value of the expression +on the right +to the named expression on the left. +.NH 3 +\fInamed-expression\fP += \fIexpression\fP +.NH 3 +\fInamed-expression\fP \-= \fIexpression\fP +.NH 3 +\fInamed-expression\fP *= \fIexpression\fP +.NH 3 +\fInamed-expression\fP /= \fIexpression\fP +.NH 3 +\fInamed-expression\fP %= \fIexpression\fP +.NH 3 +\fInamed-expression\fP ^= \fIexpression\fP +.PP +The result of the above expressions is equivalent +to ``named expression = named expression OP expression'', +where OP is the operator after the = sign. +.NH 1 +Relations +.PP +Unlike all other operators, the relational operators +are only valid as the object of an \fBif\fP, \fBwhile\fP, +or inside a \fBfor\fP statement. +.NH 2 +\fIexpression\fP < \fIexpression\fP +.NH 2 +\fIexpression\fP > \fIexpression\fP +.NH 2 +\fIexpression\fP <= \fIexpression\fP +.NH 2 +\fIexpression\fP >= \fIexpression\fP +.NH 2 +\fIexpression\fP == \fIexpression\fP +.NH 2 +\fIexpression\fP != \fIexpression\fP +.NH 1 +Storage classes +.PP +There are only two storage classes in BC, global and automatic +(local). +Only identifiers that are to be local to a function need be +declared with the \fBauto\fP command. +The arguments to a function +are local to the function. +All other identifiers are assumed to be global +and available to all functions. +All identifiers, global and local, have initial values +of zero. +Identifiers declared as \fBauto\fP are allocated on entry to the function +and released on returning from the function. +They therefore do not retain values between function calls. +\fBauto\fP arrays are specified by the array name followed by empty square brackets. +.PP +Automatic variables in BC do not work in exactly the same way +as in either C or PL/I. On entry to a function, the old values of +the names that appear as parameters and as automatic +variables are pushed onto a stack. +Until return is made from the function, reference to these +names refers only to the new values. +.NH 1 +Statements +.PP +Statements must be separated by semicolon or newline. +Except where altered by control statements, execution +is sequential. +.NH 2 +Expression statements +.PP +When a statement is an expression, unless +the main operator is an assignment, the value +of the expression is printed, followed by a newline character. +.NH 2 +Compound statements +.PP +Statements may be grouped together and used when one statement is expected +by surrounding them with { }. +.NH 2 +Quoted string statements +.PP +"any string" +.sp .5 +This statement prints the string inside the quotes. +.NH 2 +If statements +.sp .5 +\fBif\|(\|\fIrelation\fB\|)\|\fIstatement\fR +.PP +The substatement is executed if the relation is true. +.NH 2 +If-else statements +.sp .5 +\fBif\|(\|\fIrelation\fB\|)\|\fIstatement\fB\|else\|\fIstatement\fR +.PP +The first substatement is executed if the relation is true, the second +substatement if the relation is false. +The \fBif-else\fR statement is a non-portable extension. +.NH 2 +While statements +.sp .5 +\fBwhile\|(\|\fIrelation\fB\|)\|\fIstatement\fR +.PP +The statement is executed while the relation +is true. +The test occurs before each execution of the statement. +.NH 2 +For statements +.sp .5 +\fBfor\|(\|\fIexpression\fB; \fIrelation\fB; \fIexpression\fB\|)\|\fIstatement\fR +.PP +The \fBfor\fR statement is the same as +.nf +.ft I + first-expression + \fBwhile\|(\fPrelation\|\fB) {\fP + statement + last-expression + } +.ft R +.fi +.PP +All three expressions may be left out. +This is a non-portable extension. +.NH 2 +Break statements +.sp .5 +\fBbreak\fP +.PP +\fBbreak\fP causes termination of a \fBfor\fP or \fBwhile\fP statement. +.NH 2 +Continue statements +.sp .5 +\fBcontinue\fP +.PP +\fBcontinue\fP causes the next iteration of a \fBfor\fP or \fBwhile\fP +statement to start, skipping the remainder of the loop. +For a \fBwhile\fP statement, execution continues with the evaluation +of the condition. +For a \fBfor\fP statement, execution continues with evaluation of +the last-expression. +The \fBcontinue\fP statement is a non-portable extension. +.NH 2 +Auto statements +.sp .5 +\fBauto \fIidentifier\fR\|[\|\fB,\fIidentifier\fR\|] +.PP +The \fBauto\fR statement causes the values of the identifiers to be pushed down. +The identifiers can be ordinary identifiers or array identifiers. +Array identifiers are specified by following the array name by empty square +brackets. +The auto statement must be the first statement +in a function definition. +.NH 2 +Define statements +.sp .5 +.nf +\fBdefine(\|\fR[\fIparameter\|\fR[\fB\|,\|\fIparameter\|.\|.\|.\|\fR]\|]\|\fB)\|{\fI + statements\|\fB}\fR +.fi +.PP +The \fBdefine\fR statement defines a function. +The parameters may +be ordinary identifiers or array names. +Array names must be followed by empty square brackets. +As a non-portable extension, the opening brace may also appear on the +next line. +.NH 2 +Return statements +.sp .5 +\fBreturn\fP +.sp .5 +\fBreturn(\fI\|expression\|\fB)\fR +.PP +The \fBreturn\fR statement causes termination of a function, +popping of its auto variables, and +specifies the result of the function. +The first form is equivalent to \fBreturn(0)\fR. +The result of the function is the result of the expression +in parentheses. +Leaving out the expression between parentheses is equivalent to +\fBreturn(0)\fR. +As a non-portable extension, the parentheses may be left out. +.NH 2 +Print +.PP +The \fBprint\fR statement takes a list of comma-separated expressions. +Each expression in the list is evaluated and the computed +value is printed and assigned to the variable `last'. +No trailing newline is printed. +The expression may also be a string enclosed in double quotes. +Within these strings the following escape sequences may be used: +\ea +for bell (alert), +`\eb' +for backspace, +`\ef' +for formfeed, +`\en' +for newline, +`\er' +for carriage return, +`\et' +`for tab, +`\eq' +for double quote and +`\e\e' +for backslash. +Any other character following a backslash will be ignored. +Strings will not be assigned to `last'. +The \fBprint\fR statement is a non-portable extension. +.NH 2 +Quit +.PP +The \fBquit\fR statement stops execution of a BC program and returns +control to UNIX when it is first encountered. +Because it is not treated as an executable statement, +it cannot be used +in a function definition or in an +.ft B +if, for, +.ft +or +.ft B +while +.ft +statement. diff --git a/usr.bin/bc/bc.1 b/usr.bin/bc/bc.1 new file mode 100644 index 0000000..a623b9c --- /dev/null +++ b/usr.bin/bc/bc.1 @@ -0,0 +1,400 @@ +.\" $FreeBSD$ +.\" $OpenBSD: bc.1,v 1.25 2010/01/02 19:48:56 schwarze Exp $ +.\" +.\" Copyright (C) Caldera International Inc. 2001-2002. +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code and documentation must retain the above +.\" copyright notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. All advertising materials mentioning features or use of this software +.\" must display the following acknowledgement: +.\" This product includes software developed or owned by Caldera +.\" International, Inc. +.\" 4. Neither the name of Caldera International, Inc. nor the names of other +.\" contributors may be used to endorse or promote products derived from +.\" this software without specific prior written permission. +.\" +.\" USE OF THE SOFTWARE PROVIDED FOR UNDER THIS LICENSE BY CALDERA +.\" INTERNATIONAL, INC. 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 CALDERA INTERNATIONAL, INC. 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. +.\" +.\" @(#)bc.1 6.8 (Berkeley) 8/8/91 +.\" +.Dd May 31 2007 +.Dt BC 1 +.Os +.Sh NAME +.Nm bc +.Nd arbitrary-precision arithmetic language and calculator +.Sh SYNOPSIS +.Nm bc +.Op Fl cl +.Op Fl e Ar expression +.Op Ar file ... +.Sh DESCRIPTION +.Nm +is an interactive processor for a language which resembles +C but provides unlimited precision arithmetic. +It takes input from any expressions on the command line and +any files given, then reads the standard input. +.Pp +Options available: +.Bl -tag -width Ds +.It Fl c +.It Fl d +.It Fl Fl debug +.Nm +is actually a preprocessor for +.Xr dc 1 , +which it invokes automatically, unless the +.Fl c +.Pq compile only +option is present. +In this case the generated +.Xr dc 1 +instructions are sent to the standard output, +instead of being interpreted by a running +.Xr dc 1 +process. +.It Fl e Ar exp +.It Fl Fl expression Ar exp +Evaluate +.Ar expression . +If multiple +.Fl e +options are specified, they are processed in the order given, +separated by newlines. +.It Fl h +.It Fl Fl help +Prints usage information. +.It Fl l +.It Fl Fl mathlib +Allow specification of an arbitrary precision math library. +The definitions in the library are available to command line +expressions. +.It Fl v +.It Fl Fl version +Prints version information. +.El +.Pp +The syntax for +.Nm +programs is as follows: +.Sq L +means letter a-z; +.Sq E +means expression; +.Sq S +means statement. +As a non-portable extension, it is possible to use long names +in addition to single letter names. +A long name is a sequence starting with a lowercase letter +followed by any number of lowercase letters and digits. +The underscore character +.Pq Sq _ +counts as a letter. +.Pp +Comments +.Bd -unfilled -offset indent -compact +are enclosed in /* and */ +are enclosed in # and the next newline +.Ed +.Pp +The newline is not part of the line comment, +which in itself is a non-portable extension. +.Pp +Names +.Bd -unfilled -offset indent -compact +simple variables: L +array elements: L [ E ] +The words `ibase', `obase', and `scale' +The word `last' or a single dot +.Ed +.Pp +Other operands +.Bd -unfilled -offset indent -compact +arbitrarily long numbers with optional sign and decimal point +( E ) +sqrt ( E ) +length ( E ) number of significant decimal digits +scale ( E ) number of digits right of decimal point +L ( E , ... , E ) +.Ed +.Pp +The sequence +.Sq \e<newline><whitespace> +is ignored within numbers. +.Pp +Operators +.Pp +The following arithmetic and logical operators can be used. +The semantics of the operators is the same as in the C language. +They are listed in order of decreasing precedence. +Operators in the same group have the same precedence. +.Bl -column -offset indent "= += \-= *= /= %= ^=" "Associativity" \ +"multiply, divide, modulus" +.It Sy "Operator" Ta Sy "Associativity" Ta Sy "Description" +.It "++ \-\-" Ta "none" Ta "increment, decrement" +.It "\-" Ta "none" Ta "unary minus" +.It "^" Ta "right" Ta "power" +.It "* / %" Ta "left" Ta "multiply, divide, modulus" +.It "+ \-" Ta "left" Ta "plus, minus" +.It "= += -= *= /= %= ^=" Ta "right" Ta "assignment" +.It "== <= >= != < >" Ta "none" Ta "relational" +.It "!" Ta "none" Ta "boolean not" +.It "&&" Ta "left" Ta "boolean and" +.It "||" Ta "left" Ta "boolean or" +.El +.Pp +Note the following: +.Bl -bullet -offset indent +.It +The relational operators may appear in any expression. +The +.St -p1003.2 +standard only allows them in the conditional expression of an +.Sq if , +.Sq while +or +.Sq for +statement. +.It +The relational operators have a lower precedence than the assignment +operators. +This has the consequence that the expression +.Sy a = b < c +is interpreted as +.Sy (a = b) < c , +which is probably not what the programmer intended. +.It +In contrast with the C language, the relational operators all have +the same precedence, and are non-associative. +The expression +.Sy a < b < c +will produce a syntax error. +.It +The boolean operators (!, && and ||) are non-portable extensions. +.It +The boolean not +(!) operator has much lower precedence than the same operator in the +C language. +This has the consequence that the expression +.Sy !a < b +is interpreted as +.Sy !(a < b) . +Prudent programmers use parentheses when writing expressions involving +boolean operators. +.El +.Pp +Statements +.Bd -unfilled -offset indent -compact +E +{ S ; ... ; S } +if ( E ) S +if ( E ) S else S +while ( E ) S +for ( E ; E ; E ) S +null statement +break +continue +quit +a string of characters, enclosed in double quotes +print E ,..., E +.Ed +.Pp +A string may contain any character, except double quote. +The if statement with an else branch is a non-portable extension. +All three E's in a for statement may be empty. +This is a non-portable extension. +The continue and print statements are also non-portable extensions. +.Pp +The print statement takes a list of comma-separated expressions. +Each expression in the list is evaluated and the computed +value is printed and assigned to the variable `last'. +No trailing newline is printed. +The expression may also be a string enclosed in double quotes. +Within these strings the following escape sequences may be used: +.Sq \ea +for bell (alert), +.Sq \eb +for backspace, +.Sq \ef +for formfeed, +.Sq \en +for newline, +.Sq \er +for carriage return, +.Sq \et +for tab, +.Sq \eq +for double quote and +.Sq \e\e +for backslash. +Any other character following a backslash will be ignored. +Strings will not be assigned to `last'. +.Pp +Function definitions +.Bd -unfilled -offset indent +define L ( L ,..., L ) { + auto L, ... , L + S; ... S + return ( E ) +} +.Ed +.Pp +As a non-portable extension, the opening brace of the define statement +may appear on the next line. +The return statement may also appear in the following forms: +.Bd -unfilled -offset indent +return +return () +return E +.Ed +.Pp +The first two are equivalent to the statement +.Dq return 0 . +The last form is a non-portable extension. +Not specifying a return statement is equivalent to writing +.Dq return (0) . +.Pp +Functions available in the math library, which is loaded by specifying the +.Fl l +flag on the command line +.Pp +.Bl -tag -width j(n,x) -offset indent -compact +.It s(x) +sine +.It c(x) +cosine +.It e(x) +exponential +.It l(x) +log +.It a(x) +arctangent +.It j(n,x) +Bessel function +.El +.Pp +All function arguments are passed by value. +.Pp +The value of a statement that is an expression is printed +unless the main operator is an assignment. +The value printed is assigned to the special variable `last'. +This is a non-portable extension. +A single dot may be used as a synonym for `last'. +Either semicolons or newlines may separate statements. +Assignment to +.Ar scale +influences the number of digits to be retained on arithmetic +operations in the manner of +.Xr dc 1 . +Assignments to +.Ar ibase +or +.Ar obase +set the input and output number radix respectively. +.Pp +The same letter may be used as an array, a function, +and a simple variable simultaneously. +All variables are global to the program. +`Auto' variables are pushed down during function calls. +When using arrays as function arguments +or defining them as automatic variables, +empty square brackets must follow the array name. +.Pp +For example +.Bd -literal -offset indent +scale = 20 +define e(x){ + auto a, b, c, i, s + a = 1 + b = 1 + s = 1 + for(i=1; 1==1; i++){ + a = a*x + b = b*i + c = a/b + if(c == 0) return(s) + s = s+c + } +} +.Ed +.Pp +defines a function to compute an approximate value of +the exponential function and +.Pp +.Dl for(i=1; i<=10; i++) e(i) +.Pp +prints approximate values of the exponential function of +the first ten integers. +.Bd -literal -offset indent +$ bc -l -e 'scale = 500; 2 * a(2^10000)' -e quit +.Ed +.Pp +prints an approximation of pi. +.Sh FILES +.Bl -tag -width /usr/share/misc/bc.library -compact +.It Pa /usr/share/misc/bc.library +math library, read when the +.Fl l +option is specified on the command line. +.El +.Sh SEE ALSO +.Xr dc 1 +.Pp +"BC \- An Arbitrary Precision Desk-Calculator Language", +.Pa /usr/share/doc/usd/06.bc/ . +.Sh STANDARDS +The +.Nm +utility is compliant with the +.St -p1003.1-2008 +specification. +.Pp +The flags +.Op Fl ce +are extensions to that specification. +.Sh HISTORY +The +.Nm +first command appeared in +.At v6 . +A complete rewrite of the +.Nm +command first appeared in +.Ox 3.5 . +.Sh AUTHORS +.An -nosplit +The original version of the +.Nm +command was written by +.An Robert Morris +and +.An Lorinda Cherry . +The current version of the +.Nm +utility was written by +.An Otto Moerbeek . +.Sh BUGS +.Ql Quit +is interpreted when read, not when executed. +.Pp +Some non-portable extensions, as found in the GNU version of the +.Nm +utility are not implemented (yet). diff --git a/usr.bin/bc/bc.library b/usr.bin/bc/bc.library new file mode 100644 index 0000000..c3145ab --- /dev/null +++ b/usr.bin/bc/bc.library @@ -0,0 +1,263 @@ +/* $FreeBSD$ */ +/* $OpenBSD: bc.library,v 1.3 2007/02/03 21:15:06 otto Exp $ */ + +/* + * Copyright (C) Caldera International Inc. 2001-2002. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code and documentation must retain the above + * copyright notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed or owned by Caldera + * International, Inc. + * 4. Neither the name of Caldera International, Inc. nor the names of other + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * USE OF THE SOFTWARE PROVIDED FOR UNDER THIS LICENSE BY CALDERA + * INTERNATIONAL, INC. 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 CALDERA INTERNATIONAL, INC. 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. + */ + +/* + * @(#)bc.library 5.1 (Berkeley) 4/17/91 + */ + +scale = 20 +define e(x) { + auto a, b, c, d, e, g, t, w, y, r + + r = ibase + ibase = A + t = scale + scale = t + .434*x + 1 + + w = 0 + if (x < 0) { + x = -x + w = 1 + } + y = 0 + while (x > 2) { + x = x/2 + y = y + 1 + } + + a = 1 + b = 1 + c = b + d = 1 + e = 1 + for (a = 1; 1 == 1; a++) { + b = b*x + c = c*a + b + d = d*a + g = c/d + if (g == e) { + g = g/1 + while (y--) { + g = g*g + } + scale = t + ibase = r + if (w == 1) return (1/g) + return (g/1) + } + e = g + } +} + +define l(x) { + auto a, b, c, d, e, f, g, u, s, t, r + r = ibase + ibase = A + if (x <= 0) { + a = (1 - 10^scale) + ibase = r + return (a) + } + t = scale + + f = 1 + scale = scale + scale(x) - length(x) + 1 + s = scale + while (x > 2) { + s = s + (length(x) - scale(x))/2 + 1 + if (s > 0) scale = s + x = sqrt(x) + f = f*2 + } + while (x < .5) { + s = s + (length(x) - scale(x))/2 + 1 + if (s > 0) scale = s + x = sqrt(x) + f = f*2 + } + + scale = t + length(f) - scale(f) + 1 + u = (x - 1)/(x + 1) + + scale = scale + 1.1*length(t) - 1.1*scale(t) + s = u*u + b = 2*f + c = b + d = 1 + e = 1 + for (a = 3; 1 == 1 ; a = a + 2) { + b = b*s + c = c*a + d*b + d = d*a + g = c/d + if (g == e) { + scale = t + ibase = r + return (u*c/d) + } + e = g + } +} + +define s(x) { + auto a, b, c, s, t, y, p, n, i, r + r = ibase + ibase = A + t = scale + y = x/.7853 + s = t + length(y) - scale(y) + if (s < t) s = t + scale = s + p = a(1) + + scale = 0 + if (x >= 0) n = (x/(2*p) + 1)/2 + if (x < 0) n = (x/(2*p) - 1)/2 + x = x - 4*n*p + if (n % 2 != 0) x = -x + + scale = t + length(1.2*t) - scale(1.2*t) + y = -x*x + a = x + b = 1 + s = x + for (i =3 ; 1 == 1; i = i + 2) { + a = a*y + b = b*i*(i - 1) + c = a/b + if (c == 0) { + scale = t + ibase = r + return (s/1) + } + s = s + c + } +} + +define c(x) { + auto t, r + r = ibase + ibase = A + t = scale + scale = scale + 1 + x = s(x + 2*a(1)) + scale = t + ibase = r + return (x/1) +} + +define a(x) { + auto a, b, c, d, e, f, g, s, t, r + if (x == 0) return(0) + + r = ibase + ibase = A + if (x == 1) { + if (scale < 52) { + a = .7853981633974483096156608458198757210492923498437764/1 + ibase = r + return (a) + } + } + t = scale + f = 1 + while (x > .5) { + scale = scale + 1 + x = -(1 - sqrt(1. + x*x))/x + f = f*2 + } + while (x < -.5) { + scale = scale + 1 + x = -(1 - sqrt(1. + x*x))/x + f = f*2 + } + s = -x*x + b = f + c = f + d = 1 + e = 1 + for (a = 3; 1 == 1; a = a + 2) { + b = b*s + c = c*a + d*b + d = d*a + g = c/d + if (g == e) { + ibase = r + scale = t + return (x*c/d) + } + e = g + } +} + +define j(n,x) { + auto a, b, c, d, e, g, i, s, k, t, r + + r = ibase + ibase = A + t = scale + k = 1.36*x + 1.16*t - n + k = length(k) - scale(k) + if (k > 0) scale = scale + k + + s = -x*x/4 + if (n < 0) { + n = -n + x = -x + } + a = 1 + c = 1 + for (i = 1; i <= n; i++) { + a = a*x + c = c*2*i + } + b = a + d = 1 + e = 1 + for (i = 1; 1; i++) { + a = a*s + b = b*i*(n + i) + a + c = c*i*(n + i) + g = b/c + if (g == e) { + ibase = r + scale = t + return (g/1) + } + e = g + } +} diff --git a/usr.bin/bc/bc.y b/usr.bin/bc/bc.y new file mode 100644 index 0000000..6492168 --- /dev/null +++ b/usr.bin/bc/bc.y @@ -0,0 +1,1179 @@ +%{ +/* $OpenBSD: bc.y,v 1.33 2009/10/27 23:59:36 deraadt Exp $ */ + +/* + * Copyright (c) 2003, Otto Moerbeek <otto@drijf.net> + * + * 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 <sys/cdefs.h> +__FBSDID("$FreeBSD$"); + +#include <sys/types.h> +#include <sys/wait.h> + +#include <ctype.h> +#include <err.h> +#include <errno.h> +#include <getopt.h> +#include <limits.h> +#include <search.h> +#include <signal.h> +#include <stdarg.h> +#include <stdbool.h> +#include <string.h> +#include <unistd.h> + +#include "extern.h" +#include "pathnames.h" + +#define BC_VER "1.0-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 { + ssize_t index; + union { + char *astr; + const char *cstr; + } u; +}; + +int yyparse(void); +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); +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[] = +{ + {"debug", no_argument, NULL, 'd'}, + {"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 { + ssize_t node; + struct lvalue lvalue; + const char *str; + char *astr; +} + +%token COMMA SEMICOLON LPAR RPAR LBRACE RBRACE LBRACKET RBRACKET DOT +%token NEWLINE +%token <astr> LETTER +%token <str> 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 <str> ASSIGN_OP +%left PLUS MINUS +%left MULTIPLY DIVIDE REMAINDER +%right EXPONENT +%nonassoc UMINUS +%nonassoc INCR DECR + +%type <lvalue> named_expression +%type <node> argument_list +%type <node> alloc_macro +%type <node> expression +%type <node> function +%type <node> function_header +%type <node> input_item +%type <node> opt_argument_list +%type <node> opt_expression +%type <node> opt_relational_expression +%type <node> opt_statement +%type <node> print_expression +%type <node> print_expression_list +%type <node> relational_expression +%type <node> return_expression +%type <node> semicolon_list +%type <node> statement +%type <node> statement_list + +%% + +program : /* empty */ + | program input_item + ; + +input_item : semicolon_list NEWLINE + { + emit($1); + 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)); + 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) +{ + if (instructions[i].index >= 0) + while (instructions[i].index != END_NODE) + emit(instructions[i++].index); + else + fputs(instructions[i].u.cstr, stdout); +} + +static void +emit_macro(int nodeidx, ssize_t code) +{ + putchar('['); + emit(code); + 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_short num; + u_char *p; + + /* 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 *str, *p; + int n; + + if (yyin != NULL && feof(yyin)) + n = asprintf(&str, "%s: %s:%d: %s: unexpected EOF", + __progname, filename, lineno, s); + else if (isspace(yytext[0]) || !isprint(yytext[0])) + n = asprintf(&str, + "%s: %s:%d: %s: ascii char 0x%02x unexpected", + __progname, filename, lineno, s, yytext[0]); + 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 [-cdhlqv] [-e expression] [file ...]\n", + __progname); + exit(1); +} + +static char * +escape(const char *str) +{ + char *ret, *p; + + 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 */ +void +sigchld(int signo) +{ + pid_t pid; + int status; + + switch (signo) { + default: + for (;;) { + pid = waitpid(dc, &status, WCONTINUED); + if (pid == -1) { + if (errno == EINTR) + continue; + _exit(0); + } + if (WIFEXITED(status) || WIFSIGNALED(status)) + _exit(0); + else + break; + } + } +} + +int +main(int argc, char *argv[]) +{ + int i, ch; + int p[2]; + char *q; + + init(); + setlinebuf(stdout); + + sargv = malloc(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"); + } + } + yywrap(); + return (yyparse()); +} diff --git a/usr.bin/bc/extern.h b/usr.bin/bc/extern.h new file mode 100644 index 0000000..a99c46c --- /dev/null +++ b/usr.bin/bc/extern.h @@ -0,0 +1,38 @@ +/* $FreeBSD$ */ +/* $OpenBSD: extern.h,v 1.6 2006/03/18 20:44:43 otto Exp $ */ + +/* + * Copyright (c) 2003, Otto Moerbeek <otto@drijf.net> + * + * 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 <stdio.h> + +struct lvalue { + ssize_t load; + ssize_t store; +}; + +int yylex(void); +void yyerror(const char *); +void fatal(const char *); +void abort_line(int); + +extern int lineno; +extern int fileindex; +extern int sargc; +extern const char **sargv; +extern const char *filename; +extern char *cmdexpr; +bool interactive; diff --git a/usr.bin/bc/pathnames.h b/usr.bin/bc/pathnames.h new file mode 100644 index 0000000..defb766 --- /dev/null +++ b/usr.bin/bc/pathnames.h @@ -0,0 +1,21 @@ +/* $FreeBSD$ */ +/* $OpenBSD: pathnames.h,v 1.1 2003/09/25 19:32:44 otto Exp $ */ + +/* + * Copyright (c) 2003, Otto Moerbeek <otto@drijf.net> + * + * 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. + */ + +#define _PATH_LIBB "/usr/share/misc/bc.library" +#define _PATH_DC "/usr/bin/dc" diff --git a/usr.bin/bc/scan.l b/usr.bin/bc/scan.l new file mode 100644 index 0000000..9c21fc2 --- /dev/null +++ b/usr.bin/bc/scan.l @@ -0,0 +1,288 @@ +%{ +/* $OpenBSD: scan.l,v 1.23 2009/10/27 23:59:36 deraadt Exp $ */ + +/* + * Copyright (c) 2003, Otto Moerbeek <otto@drijf.net> + * + * 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 <sys/cdefs.h> +__FBSDID("$FreeBSD$"); + +#include <err.h> +#include <errno.h> +#include <signal.h> +#include <stdbool.h> +#include <string.h> +#include <unistd.h> + +#include "extern.h" +#include "bc.h" +#include "pathnames.h" + +int lineno; + +static char *strbuf = NULL; +static size_t strbuf_sz = 1; +static bool dot_seen; + +static void init_strbuf(void); +static void add_str(const char *); + +%} + +%option always-interactive + +DIGIT [0-9A-F] +ALPHA [a-z_] +ALPHANUM [a-z_0-9] + +%x comment string number + +%% + +"/*" BEGIN(comment); +<comment>{ + "*/" BEGIN(INITIAL); + \n lineno++; + \* ; + [^*\n]+ ; + <<EOF>> fatal("end of file in comment"); +} + +\" BEGIN(string); init_strbuf(); +<string>{ + [^"\n\\\[\]]+ add_str(yytext); + \[ add_str("\\["); + \] add_str("\\]"); + \\ add_str("\\\\"); + \n add_str("\n"); lineno++; + \" BEGIN(INITIAL); yylval.str = strbuf; return STRING; + <<EOF>> fatal("end of file in string"); +} + +{DIGIT}+ { + BEGIN(number); + dot_seen = false; + init_strbuf(); + add_str(yytext); + } +\. { + BEGIN(number); + dot_seen = true; + init_strbuf(); + add_str("."); + } +<number>{ + {DIGIT}+ add_str(yytext); + \. { + if (dot_seen) { + BEGIN(INITIAL); + yylval.str = strbuf; + unput('.'); + return (NUMBER); + } else { + dot_seen = true; + add_str("."); + } + } + \\\n[ \t]* lineno++; + [^0-9A-F\.] { + BEGIN(INITIAL); + unput(yytext[0]); + if (strcmp(strbuf, ".") == 0) + return (DOT); + else { + yylval.str = strbuf; + return (NUMBER); + } + } +} + +"auto" return (AUTO); +"break" return (BREAK); +"continue" return (CONTINUE); +"define" return (DEFINE); +"else" return (ELSE); +"ibase" return (IBASE); +"if" return (IF); +"last" return (DOT); +"for" return (FOR); +"length" return (LENGTH); +"obase" return (OBASE); +"print" return (PRINT); +"quit" return (QUIT); +"return" return (RETURN); +"scale" return (SCALE); +"sqrt" return (SQRT); +"while" return (WHILE); + +"^" return (EXPONENT); +"*" return (MULTIPLY); +"/" return (DIVIDE); +"%" return (REMAINDER); + +"!" return (BOOL_NOT); +"&&" return (BOOL_AND); +"||" return (BOOL_OR); + +"+" return (PLUS); +"-" return (MINUS); + +"++" return (INCR); +"--" return (DECR); + +"=" yylval.str = ""; return (ASSIGN_OP); +"+=" yylval.str = "+"; return (ASSIGN_OP); +"-=" yylval.str = "-"; return (ASSIGN_OP); +"*=" yylval.str = "*"; return (ASSIGN_OP); +"/=" yylval.str = "/"; return (ASSIGN_OP); +"%=" yylval.str = "%"; return (ASSIGN_OP); +"^=" yylval.str = "^"; return (ASSIGN_OP); + +"==" return (EQUALS); +"<=" return (LESS_EQ); +">=" return (GREATER_EQ); +"!=" return (UNEQUALS); +"<" return (LESS); +">" return (GREATER); + +"," return (COMMA); +";" return (SEMICOLON); + +"(" return (LPAR); +")" return (RPAR); + +"[" return (LBRACKET); +"]" return (RBRACKET); + +"{" return (LBRACE); +"}" return (RBRACE); + +{ALPHA}{ALPHANUM}* { + /* alloc an extra byte for the type marker */ + char *p = malloc(yyleng + 2); + if (p == NULL) + err(1, NULL); + strlcpy(p, yytext, yyleng + 1); + yylval.astr = p; + return (LETTER); + } + +\\\n lineno++; +\n lineno++; return (NEWLINE); + +#[^\n]* ; +[ \t] ; +<<EOF>> return (QUIT); +. yyerror("illegal character"); + +%% + +static void +init_strbuf(void) +{ + if (strbuf == NULL) { + strbuf = malloc(strbuf_sz); + if (strbuf == NULL) + err(1, NULL); + } + strbuf[0] = '\0'; +} + +static void +add_str(const char *str) +{ + size_t arglen; + + arglen = strlen(str); + + if (strlen(strbuf) + arglen + 1 > strbuf_sz) { + size_t newsize; + char *p; + + newsize = strbuf_sz + arglen + 1; + p = realloc(strbuf, newsize); + if (p == NULL) { + free(strbuf); + err(1, NULL); + } + strbuf_sz = newsize; + strbuf = p; + } + strlcat(strbuf, str, strbuf_sz); +} + +/* ARGSUSED */ +void +abort_line(int sig) +{ + static const char str[] = "[\n]P\n"; + int save_errno; + + switch (sig) { + default: + save_errno = errno; + YY_FLUSH_BUFFER; /* XXX signal race? */ + write(STDOUT_FILENO, str, sizeof(str) - 1); + errno = save_errno; + } +} + +int +yywrap(void) +{ + static int state; + static YY_BUFFER_STATE buf; + + if (fileindex == 0 && sargc > 0 && strcmp(sargv[0], _PATH_LIBB) == 0) { + filename = sargv[fileindex++]; + yyin = fopen(filename, "r"); + lineno = 1; + if (yyin == NULL) + err(1, "cannot open %s", filename); + return (0); + } + if (state == 0 && cmdexpr[0] != '\0') { + buf = yy_scan_string(cmdexpr); + state++; + lineno = 1; + filename = "command line"; + return (0); + } else if (state == 1) { + yy_delete_buffer(buf); + free(cmdexpr); + state++; + } + if (yyin != NULL && yyin != stdin) + fclose(yyin); + if (fileindex < sargc) { + filename = sargv[fileindex++]; + yyin = fopen(filename, "r"); + lineno = 1; + if (yyin == NULL) + err(1, "cannot open %s", filename); + return (0); + } else if (fileindex == sargc) { + fileindex++; + yyin = stdin; + if (interactive) + signal(SIGINT, abort_line); + lineno = 1; + filename = "stdin"; + return (0); + } + return (1); +} + diff --git a/usr.bin/dc/Makefile b/usr.bin/dc/Makefile new file mode 100644 index 0000000..1ad72e0 --- /dev/null +++ b/usr.bin/dc/Makefile @@ -0,0 +1,13 @@ +# $FreeBSD$ +# $OpenBSD: Makefile,v 1.2 2006/11/26 11:31:09 deraadt Exp $ + +PROG= dc +SRCS= dc.c bcode.c inout.c mem.c stack.c +LDADD= -lcrypto +DPADD= ${LIBCRYPTO} + +#SUBDIR+= USD.doc + +WARNS?= 6 + +.include <bsd.prog.mk> diff --git a/usr.bin/dc/USD.doc/Makefile b/usr.bin/dc/USD.doc/Makefile new file mode 100644 index 0000000..4a272a5 --- /dev/null +++ b/usr.bin/dc/USD.doc/Makefile @@ -0,0 +1,16 @@ +# $FreeBSD$ +# $OpenBSD: Makefile,v 1.2 2004/02/01 15:18:01 jmc Exp $ + +DOC= dc +DIR= usd/05.dc +SRCS= dc +MACROS= -ms +BINDIR= /usr/share/doc/papers + +paper.ps: ${SRCS} + ${EQN} ${SRCS} | ${ROFF} > ${.TARGET} + +paper.txt: ${SRCS} + ${EQN} -Tascii ${SRCS} | ${ROFF} -Tascii > ${.TARGET} + +.include <bsd.doc.mk> diff --git a/usr.bin/dc/USD.doc/dc b/usr.bin/dc/USD.doc/dc new file mode 100644 index 0000000..4caa0f4 --- /dev/null +++ b/usr.bin/dc/USD.doc/dc @@ -0,0 +1,753 @@ +.\" $FreeBSD$ +.\" $OpenBSD: dc,v 1.2 2003/09/22 19:08:27 otto Exp $ +.\" +.\" Copyright (C) Caldera International Inc. 2001-2002. +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code and documentation must retain the above +.\" copyright notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. All advertising materials mentioning features or use of this software +.\" must display the following acknowledgement: +.\" This product includes software developed or owned by Caldera +.\" International, Inc. +.\" 4. Neither the name of Caldera International, Inc. nor the names of other +.\" contributors may be used to endorse or promote products derived from +.\" this software without specific prior written permission. +.\" +.\" USE OF THE SOFTWARE PROVIDED FOR UNDER THIS LICENSE BY CALDERA +.\" INTERNATIONAL, INC. 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 CALDERA INTERNATIONAL, INC. 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. +.\" +.\" @(#)dc 8.1 (Berkeley) 6/8/93 +.\" +.EH 'USD:5-%''DC \- An Interactive Desk Calculator' +.OH 'DC \- An Interactive Desk Calculator''USD:5-%' +.\".RP +.\" ....TM 75-1271-8 39199 39199-11 +.ND +.TL +DC \- An Interactive Desk Calculator +.AU "MH 2C-524" 3878 +Robert Morris +.AU +Lorinda Cherry +.AI +.\" .MH +.AB +DC is an interactive desk calculator program implemented +on the +.UX +time-sharing system to do arbitrary-precision +integer arithmetic. +It has provision for manipulating scaled fixed-point numbers and +for input and output in bases other than decimal. +.PP +The size of numbers that can be manipulated is limited +only by available core storage. +On typical implementations of +.UX , +the size of numbers that +can be handled varies from several hundred digits on the smallest +systems to several thousand on the largest. +.AE +.PP +.SH +.PP +.ft I +Editor's note: the description of the implementation details of DC in this +paper is only valid for the original version of DC. +The current version of DC uses a different approach. +.ft +.PP +DC is an arbitrary precision arithmetic package implemented +on the +.UX +time-sharing system +in the form of an interactive desk calculator. +It works like a stacking calculator using reverse Polish notation. +Ordinarily DC operates on decimal integers, but one may +specify an input base, output base, and a number of fractional +digits to be maintained. +.PP +A language called BC [1] has been developed which accepts +programs written in the familiar style of higher-level +programming languages and compiles output which is +interpreted by DC. +Some of the commands described below were designed +for the compiler interface and are not easy for a human user +to manipulate. +.PP +Numbers that are typed into DC are put on a push-down +stack. +DC commands work by taking the top number or two +off the stack, performing the desired operation, and pushing the result +on the stack. +If an argument is given, +input is taken from that file until its end, +then from the standard input. +.SH +SYNOPTIC DESCRIPTION +.PP +Here we describe the DC commands that are intended +for use by people. The additional commands that are +intended to be invoked by compiled output are +described in the detailed description. +.PP +Any number of commands are permitted on a line. +Blanks and new-line characters are ignored except within numbers +and in places where a register name is expected. +.PP +The following constructions are recognized: +.SH +number +.IP +The value of the number is pushed onto the main stack. +A number is an unbroken string of the digits 0-9 +and the capital letters A\-F which are treated as digits +with values 10\-15 respectively. +The number may be preceded by an underscore _ to input a +negative number. +Numbers may contain decimal points. +.SH ++ \- * % ^ +.IP +The +top two values on the stack are added +(\fB+\fP), +subtracted +(\fB\-\fP), +multiplied (\fB*\fP), +divided (\fB/\fP), +remaindered (\fB%\fP), +or exponentiated (^). +The two entries are popped off the stack; +the result is pushed on the stack in their place. +The result of a division is an integer truncated toward zero. +See the detailed description below for the treatment of +numbers with decimal points. +An exponent must not have any digits after the decimal point. +.SH +s\fIx\fP +.IP +The +top of the main stack is popped and stored into +a register named \fIx\fP, where \fIx\fP may be any character. +If +the +.ft B +s +.ft +is capitalized, +.ft I +x +.ft +is treated as a stack and the value is pushed onto it. +Any character, even blank or new-line, is a valid register name. +.SH +l\fIx\fP +.IP +The +value in register +.ft I +x +.ft +is pushed onto the stack. +The register +.ft I +x +.ft +is not altered. +If the +.ft B +l +.ft +is capitalized, +register +.ft I +x +.ft +is treated as a stack and its top value is popped onto the main stack. +.LP +All registers start with empty value which is treated as a zero +by the command \fBl\fP and is treated as an error by the command \fBL\fP. +.SH +d +.IP +The +top value on the stack is duplicated. +.SH +p +.IP +The top value on the stack is printed. +The top value remains unchanged. +.SH +f +.IP +All values on the stack and in registers are printed. +.SH +x +.IP +treats the top element of the stack as a character string, +removes it from the stack, and +executes it as a string of DC commands. +.SH +[ ... ] +.IP +puts the bracketed character string onto the top of the stack. +.SH +q +.IP +exits the program. +If executing a string, the recursion level is +popped by two. +If +.ft B +q +.ft +is capitalized, +the top value on the stack is popped and the string execution level is popped +by that value. +.SH +<\fIx\fP >\fIx\fP =\fIx\fP !<\fIx\fP !>\fIx\fP !=\fIx\fP +.IP +The +top two elements of the stack are popped and compared. +Register +.ft I +x +.ft +is executed if they obey the stated +relation. +Exclamation point is negation. +.SH +v +.IP +replaces the top element on the stack by its square root. +The square root of an integer is truncated to an integer. +For the treatment of numbers with decimal points, see +the detailed description below. +.SH +! +.IP +interprets the rest of the line as a +.UX +command. +Control returns to DC when the +.UX +command terminates. +.SH +c +.IP +All values on the stack are popped; the stack becomes empty. +.SH +i +.IP +The top value on the stack is popped and used as the +number radix for further input. +If \fBi\fP is capitalized, the value of +the input base is pushed onto the stack. +No mechanism has been provided for the input of arbitrary +numbers in bases less than 1 or greater than 16. +.SH +o +.IP +The top value on the stack is popped and used as the +number radix for further output. +If \fBo\fP is capitalized, the value of the output +base is pushed onto the stack. +.SH +k +.IP +The top of the stack is popped, and that value is used as +a scale factor +that influences the number of decimal places +that are maintained during multiplication, division, and exponentiation. +The scale factor must be greater than or equal to zero and +less than 100. +If \fBk\fP is capitalized, the value of the scale factor +is pushed onto the stack. +.SH +z +.IP +The value of the stack level is pushed onto the stack. +.SH +? +.IP +A line of input is taken from the input source (usually the console) +and executed. +.SH +DETAILED DESCRIPTION +.SH +Internal Representation of Numbers +.PP +Numbers are stored internally using a dynamic storage allocator. +Numbers are kept in the form of a string +of digits to the base 100 stored one digit per byte +(centennial digits). +The string is stored with the low-order digit at the +beginning of the string. +For example, the representation of 157 +is 57,1. +After any arithmetic operation on a number, care is taken +that all digits are in the range 0\-99 and that +the number has no leading zeros. +The number zero is represented by the empty string. +.PP +Negative numbers are represented in the 100's complement +notation, which is analogous to two's complement notation for binary +numbers. +The high order digit of a negative number is always \-1 +and all other digits are in the range 0\-99. +The digit preceding the high order \-1 digit is never a 99. +The representation of \-157 is 43,98,\-1. +We shall call this the canonical form of a number. +The advantage of this kind of representation of negative +numbers is ease of addition. When addition is performed digit +by digit, the result is formally correct. The result need only +be modified, if necessary, to put it into canonical form. +.PP +Because the largest valid digit is 99 and the byte can +hold numbers twice that large, addition can be carried out +and the handling of carries done later when +that is convenient, as it sometimes is. +.PP +An additional byte is stored with each number beyond +the high order digit to indicate the number of +assumed decimal digits after the decimal point. The representation +of .001 is 1,\fI3\fP +where the scale has been italicized to emphasize the fact that it +is not the high order digit. +The value of this extra byte is called the +.ft B +scale factor +.ft +of the number. +.SH +The Allocator +.PP +DC uses a dynamic string storage allocator +for all of its internal storage. +All reading and writing of numbers internally is done through +the allocator. +Associated with each string in the allocator is a four-word header containing pointers +to the beginning of the string, the end of the string, +the next place to write, and the next place to read. +Communication between the allocator and DC +is done via pointers to these headers. +.PP +The allocator initially has one large string on a list +of free strings. All headers except the one pointing +to this string are on a list of free headers. +Requests for strings are made by size. +The size of the string actually supplied is the next higher +power of 2. +When a request for a string is made, the allocator +first checks the free list to see if there is +a string of the desired size. +If none is found, the allocator finds the next larger free string and splits it repeatedly until +it has a string of the right size. +Left-over strings are put on the free list. +If there are no larger strings, +the allocator tries to coalesce smaller free strings into +larger ones. +Since all strings are the result +of splitting large strings, +each string has a neighbor that is next to it in core +and, if free, can be combined with it to make a string twice as long. +This is an implementation of the `buddy system' of allocation +described in [2]. +.PP +Failing to find a string of the proper length after coalescing, +the allocator asks the system for more space. +The amount of space on the system is the only limitation +on the size and number of strings in DC. +If at any time in the process of trying to allocate a string, the allocator runs out of +headers, it also asks the system for more space. +.PP +There are routines in the allocator for reading, writing, copying, rewinding, +forward-spacing, and backspacing strings. +All string manipulation is done using these routines. +.PP +The reading and writing routines +increment the read pointer or write pointer so that +the characters of a string are read or written in +succession by a series of read or write calls. +The write pointer is interpreted as the end of the +information-containing portion of a string and a call +to read beyond that point returns an end-of-string indication. +An attempt to write beyond the end of a string +causes the allocator to +allocate a larger space and then copy +the old string into the larger block. +.SH +Internal Arithmetic +.PP +All arithmetic operations are done on integers. +The operands (or operand) needed for the operation are popped +from the main stack and their scale factors stripped off. +Zeros are added or digits removed as necessary to get +a properly scaled result from the internal arithmetic routine. +For example, if the scale of the operands is different and decimal +alignment is required, as it is for +addition, zeros are appended to the operand with the smaller +scale. +After performing the required arithmetic operation, +the proper scale factor is appended to the end of the number before +it is pushed on the stack. +.PP +A register called \fBscale\fP plays a part +in the results of most arithmetic operations. +\fBscale\fP is the bound on the number of decimal places retained in +arithmetic computations. +\fBscale\fP may be set to the number on the top of the stack +truncated to an integer with the \fBk\fP command. +\fBK\fP may be used to push the value of \fBscale\fP on the stack. +\fBscale\fP must be greater than or equal to 0 and less than 100. +The descriptions of the individual arithmetic operations will +include the exact effect of \fBscale\fP on the computations. +.SH +Addition and Subtraction +.PP +The scales of the two numbers are compared and trailing +zeros are supplied to the number with the lower scale to give both +numbers the same scale. The number with the smaller scale is +multiplied by 10 if the difference of the scales is odd. +The scale of the result is then set to the larger of the scales +of the two operands. +.PP +Subtraction is performed by negating the number +to be subtracted and proceeding as in addition. +.PP +Finally, the addition is performed digit by digit from the +low order end of the number. The carries are propagated +in the usual way. +The resulting number is brought into canonical form, which may +require stripping of leading zeros, or for negative numbers +replacing the high-order configuration 99,\-1 by the digit \-1. +In any case, digits which are not in the range 0\-99 must +be brought into that range, propagating any carries or borrows +that result. +.SH +Multiplication +.PP +The scales are removed from the two operands and saved. +The operands are both made positive. +Then multiplication is performed in +a digit by digit manner that exactly mimics the hand method +of multiplying. +The first number is multiplied by each digit of the second +number, beginning with its low order digit. The intermediate +products are accumulated into a partial sum which becomes the +final product. +The product is put into the canonical form and its sign is +computed from the signs of the original operands. +.PP +The scale of the result is set equal to the sum +of the scales of the two operands. +If that scale is larger than the internal register +.ft B +scale +.ft +and also larger than both of the scales of the two operands, +then the scale of the result is set equal to the largest +of these three last quantities. +.SH +Division +.PP +The scales are removed from the two operands. +Zeros are appended or digits removed from the dividend to make +the scale of the result of the integer division equal to +the internal quantity +\fBscale\fP. +The signs are removed and saved. +.PP +Division is performed much as it would be done by hand. +The difference of the lengths of the two numbers +is computed. +If the divisor is longer than the dividend, +zero is returned. +Otherwise the top digit of the divisor is divided into the top +two digits of the dividend. +The result is used as the first (high-order) digit of the +quotient. +It may turn out be one unit too low, but if it is, the next +trial quotient will be larger than 99 and this will be +adjusted at the end of the process. +The trial digit is multiplied by the divisor and the result subtracted +from the dividend and the process is repeated to get +additional quotient digits until the remaining +dividend is smaller than the divisor. +At the end, the digits of the quotient are put into +the canonical form, with propagation of carry as needed. +The sign is set from the sign of the operands. +.SH +Remainder +.PP +The division routine is called and division is performed +exactly as described. The quantity returned is the remains of the +dividend at the end of the divide process. +Since division truncates toward zero, remainders have the same +sign as the dividend. +The scale of the remainder is set to +the maximum of the scale of the dividend and +the scale of the quotient plus the scale of the divisor. +.SH +Square Root +.PP +The scale is stripped from the operand. +Zeros are added if necessary to make the +integer result have a scale that is the larger of +the internal quantity +\fBscale\fP +and the scale of the operand. +.PP +The method used to compute sqrt(y) is Newton's method +with successive approximations by the rule +.EQ +x sub {n+1} ~=~ half ( x sub n + y over x sub n ) +.EN +The initial guess is found by taking the integer square root +of the top two digits. +.SH +Exponentiation +.PP +Only exponents with zero scale factor are handled. If the exponent is +zero, then the result is 1. If the exponent is negative, then +it is made positive and the base is divided into one. The scale +of the base is removed. +.PP +The integer exponent is viewed as a binary number. +The base is repeatedly squared and the result is +obtained as a product of those powers of the base that +correspond to the positions of the one-bits in the binary +representation of the exponent. +Enough digits of the result +are removed to make the scale of the result the same as if the +indicated multiplication had been performed. +.SH +Input Conversion and Base +.PP +Numbers are converted to the internal representation as they are read +in. +The scale stored with a number is simply the number of fractional digits input. +Negative numbers are indicated by preceding the number with a \fB\_\fP (an +underscore). +The hexadecimal digits A\-F correspond to the numbers 10\-15 regardless of input base. +The \fBi\fP command can be used to change the base of the input numbers. +This command pops the stack, truncates the resulting number to an integer, +and uses it as the input base for all further input. +The input base is initialized to 10 but may, for example be changed to +8 or 16 to do octal or hexadecimal to decimal conversions. +The command \fBI\fP will push the value of the input base on the stack. +.SH +Output Commands +.PP +The command \fBp\fP causes the top of the stack to be printed. +It does not remove the top of the stack. +All of the stack and internal registers can be output +by typing the command \fBf\fP. +The \fBo\fP command can be used to change the output base. +This command uses the top of the stack, truncated to an integer as +the base for all further output. +The output base in initialized to 10. +It will work correctly for any base. +The command \fBO\fP pushes the value of the output base on the stack. +.SH +Output Format and Base +.PP +The input and output bases only affect +the interpretation of numbers on input and output; they have no +effect on arithmetic computations. +Large numbers are output with 70 characters per line; +a \\ indicates a continued line. +All choices of input and output bases work correctly, although not all are +useful. +A particularly useful output base is 100000, which has the effect of +grouping digits in fives. +Bases of 8 and 16 can be used for decimal-octal or decimal-hexadecimal +conversions. +.SH +Internal Registers +.PP +Numbers or strings may be stored in internal registers or loaded on the stack +from registers with the commands \fBs\fP and \fBl\fP. +The command \fBs\fIx\fR pops the top of the stack and +stores the result in register \fBx\fP. +\fIx\fP can be any character. +\fBl\fIx\fR puts the contents of register \fBx\fP on the top of the stack. +The \fBl\fP command has no effect on the contents of register \fIx\fP. +The \fBs\fP command, however, is destructive. +.SH +Stack Commands +.PP +The command \fBc\fP clears the stack. +The command \fBd\fP pushes a duplicate of the number on the top of the stack +on the stack. +The command \fBz\fP pushes the stack size on the stack. +The command \fBX\fP replaces the number on the top of the stack +with its scale factor. +The command \fBZ\fP replaces the top of the stack +with its length. +.SH +Subroutine Definitions and Calls +.PP +Enclosing a string in \fB[ ]\fP pushes the ascii string on the stack. +The \fBq\fP command quits or in executing a string, pops the recursion levels by two. +.SH +Internal Registers \- Programming DC +.PP +The load and store +commands together with \fB[ ]\fP to store strings, \fBx\fP to execute +and the testing commands `<', `>', `=', `!<', `!>', `!=' can be used to program +DC. +The \fBx\fP command assumes the top of the stack is an string of DC commands +and executes it. +The testing commands compare the top two elements on the stack and if the relation holds, execute the register +that follows the relation. +For example, to print the numbers 0-9, +.DS +[lip1+ si li10>a]sa +0si lax +.DE +.SH +Push-Down Registers and Arrays +.PP +These commands were designed for used by a compiler, not by +people. +They involve push-down registers and arrays. +In addition to the stack that commands work on, DC can be thought +of as having individual stacks for each register. +These registers are operated on by the commands \fBS\fP and \fBL\fP. +\fBS\fIx\fR pushes the top value of the main stack onto the stack for +the register \fIx\fP. +\fBL\fIx\fR pops the stack for register \fIx\fP and puts the result on the main +stack. +The commands \fBs\fP and \fBl\fP also work on registers but not as push-down +stacks. +\fBl\fP doesn't effect the top of the +register stack, and \fBs\fP destroys what was there before. +.PP +The commands to work on arrays are \fB:\fP and \fB;\fP. +\fB:\fIx\fR pops the stack and uses this value as an index into +the array \fIx\fP. +The next element on the stack is stored at this index in \fIx\fP. +An index must be greater than or equal to 0 and +less than 2048. +\fB;\fIx\fR is the command to load the main stack from the array \fIx\fP. +The value on the top of the stack is the index +into the array \fIx\fP of the value to be loaded. +.SH +Miscellaneous Commands +.PP +The command \fB!\fP interprets the rest of the line as a +.UX +command and passes it to +.UX +to execute. +One other compiler command is \fBQ\fP. +This command uses the top of the stack as the number of levels of recursion to skip. +.SH +DESIGN CHOICES +.PP +The real reason for the use of a dynamic storage allocator was +that a general purpose program could be (and in fact has been) +used for a variety of other tasks. +The allocator has some value for input and for compiling (i.e. +the bracket [...] commands) where it cannot be known in advance +how long a string will be. +The result was that at a modest +cost in execution time, all considerations of string allocation +and sizes of strings were removed from the remainder of the program +and debugging was made easier. The allocation method +used wastes approximately 25% of available space. +.PP +The choice of 100 as a base for internal arithmetic +seemingly has no compelling advantage. Yet the base cannot +exceed 127 because of hardware limitations and at the cost +of 5% in space, debugging was made a great deal easier and +decimal output was made much faster. +.PP +The reason for a stack-type arithmetic design was +to permit all DC commands from addition to subroutine execution +to be implemented in essentially the same way. The result +was a considerable degree of logical separation of the final +program into modules with very little communication between +modules. +.PP +The rationale for the lack of interaction between the scale and the bases +was to provide an understandable means of proceeding after +a change of base or scale when numbers had already been entered. +An earlier implementation which had global notions of +scale and base did not work out well. +If the value of +.ft B +scale +.ft +were to be interpreted in the current +input or output base, +then a change of base or scale in the midst of a +computation would cause great confusion in the interpretation +of the results. +The current scheme has the advantage that the value of +the input and output bases +are only used for input and output, respectively, and they +are ignored in all other operations. +The value of +scale +is not used for any essential purpose by any part of the program +and it is used only to prevent the number of +decimal places resulting from the arithmetic operations from +growing beyond all bounds. +.PP +The design rationale for the choices for the scales of +the results of arithmetic were that in no case should +any significant digits be thrown away if, on appearances, the +user actually wanted them. Thus, if the user wants +to add the numbers 1.5 and 3.517, it seemed reasonable to give +him the result 5.017 without requiring him to unnecessarily +specify his rather obvious requirements for precision. +.PP +On the other hand, multiplication and exponentiation produce +results with many more digits than their operands and it +seemed reasonable to give as a minimum the number of decimal +places in the operands but not to give more than that +number of digits +unless the user asked for them by specifying a value for \fBscale\fP. +Square root can be handled in just the same way as multiplication. +The operation of division gives arbitrarily many decimal places +and there is simply no way to guess how many places the user +wants. +In this case only, the user must +specify a \fBscale\fP to get any decimal places at all. +.PP +The scale of remainder was chosen to make it possible +to recreate the dividend from the quotient and remainder. +This is easy to implement; no digits are thrown away. +.SH +References +.IP [1] +L. L. Cherry, R. Morris, +.ft I +BC \- An Arbitrary Precision Desk-Calculator Language. +.ft +.IP [2] +K. C. Knowlton, +.ft I +A Fast Storage Allocator, +.ft +Comm. ACM \fB8\fP, pp. 623-625 (Oct. 1965). diff --git a/usr.bin/dc/bcode.c b/usr.bin/dc/bcode.c new file mode 100644 index 0000000..8b22008 --- /dev/null +++ b/usr.bin/dc/bcode.c @@ -0,0 +1,1781 @@ +/* $OpenBSD: bcode.c,v 1.40 2009/10/27 23:59:37 deraadt Exp $ */ + +/* + * Copyright (c) 2003, Otto Moerbeek <otto@drijf.net> + * + * 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 <sys/cdefs.h> +__FBSDID("$FreeBSD$"); + +#include <err.h> +#include <limits.h> +#include <openssl/ssl.h> +#include <signal.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "extern.h" + +BIGNUM zero; + +#define __inline + +#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 stack stack; + u_int scale; + u_int obase; + u_int ibase; + size_t readsp; + bool extended_regs; + size_t reg_array_size; + struct stack *reg; + volatile sig_atomic_t interrupted; + struct source *readstack; + size_t readstack_sz; +}; + +static struct bmachine bmachine; +static void sighandler(int); + +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 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 }, + { '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])) + +static void +sighandler(int ignored) +{ + + switch (ignored) + { + default: + bmachine.interrupted = true; + } +} + +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; + BN_init(&zero); + bn_check(BN_zero(&zero)); + signal(SIGINT, sighandler); +} + +/* 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); + } +} + +__inline 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_check(BN_sub(n->number, &zero, 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 +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_cmp(n->number, &zero) < 0) + 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) +{ + size_t i; + struct number *n; + + 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 value *value; + u_int scale = 0; + struct number *n; + + + 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 (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 value *value; + size_t digits; + struct number *n = NULL; + + 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) +{ + char str[2]; + struct value *value; + struct number *n; + + 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 idx, ch1, ch2; + + 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) +{ + int idx; + struct value *v, copy; + struct number *n; + + 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) +{ + int idx; + struct value *val; + + idx = readreg(); + if (idx >= 0) { + val = pop(); + if (val == NULL) { + return; + } + stack_set_tos(&bmachine.reg[idx], val); + } +} + +static void +load_stack(void) +{ + int idx; + struct stack *stack; + struct value *value; + + 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) +{ + int idx; + struct value *value; + + idx = readreg(); + if (idx >= 0) { + value = pop(); + if (value == NULL) + return; + stack_push(&bmachine.reg[idx], value); + } +} + +static void +load_array(void) +{ + int reg; + struct number *inumber, *n; + u_long idx; + struct stack *stack; + struct value *v, copy; + + reg = readreg(); + if (reg >= 0) { + inumber = pop_number(); + if (inumber == NULL) + return; + idx = get_ulong(inumber); + if (BN_cmp(inumber->number, &zero) < 0) + 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) +{ + int reg; + struct number *inumber; + u_long idx; + struct value *value; + struct stack *stack; + + 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_cmp(inumber->number, &zero) < 0) { + 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; + struct number *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; + struct number *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) +{ + 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); + + if (rscale > bmachine.scale && rscale > ascale && rscale > bscale) { + r->scale = rscale; + normalize(r, max(bmachine.scale, max(ascale, bscale))); + } else + r->scale = rscale; +} + +static void +bmul(void) +{ + struct number *a, *b; + struct number *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); + + push_number(r); + free_number(a); + free_number(b); +} + +static void +bdiv(void) +{ + struct number *a, *b; + struct number *r; + u_int scale; + BN_CTX *ctx; + + 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; + struct number *r; + u_int scale; + BN_CTX *ctx; + + 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; + struct number *rdiv, *rmod; + u_int scale; + BN_CTX *ctx; + + 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 scale; + + p = pop_number(); + if (p == NULL) { + return; + } + a = pop_number(); + if (a == NULL) { + push_number(p); + return; + } + + if (p->scale != 0) + warnx("Runtime warning: non-zero scale in exponent"); + normalize(p, 0); + + neg = false; + if (BN_cmp(p->number, &zero) < 0) { + neg = true; + negate(p); + scale = 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); + scale = a->scale * (u_int)b; + if (scale > m || (a->scale > 0 && (b == BN_MASK2 || + b > UINT_MAX))) + scale = m; + } + + if (BN_is_zero(p->number)) { + r = new_number(); + bn_check(BN_one(r->number)); + normalize(r, scale); + } else { + while (!BN_is_bit_set(p->number, 0)) { + bmul_number(a, a, a); + bn_check(BN_rshift1(p->number, p->number)); + } + + r = dup_number(a); + normalize(r, scale); + bn_check(BN_rshift1(p->number, p->number)); + + while (!BN_is_zero(p->number)) { + bmul_number(a, a, a); + if (BN_is_bit_set(p->number, 0)) + bmul_number(r, r, a); + 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 + scale); + normalize(r, scale); + bn_check(BN_div(r->number, NULL, one, r->number, ctx)); + BN_free(one); + BN_CTX_free(ctx); + } else + normalize(r, scale); + } + 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; + struct number *r; + BIGNUM *x, *y; + u_int scale, onecount; + BN_CTX *ctx; + + onecount = 0; + n = pop_number(); + if (n == NULL) { + return; + } + if (BN_is_zero(n->number)) { + r = new_number(); + push_number(r); + } else if (BN_cmp(n->number, &zero) < 0) + 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) +{ + int idx, elseidx; + struct number *a, *b; + bool ok; + struct value *v; + + 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) +{ + int ch; + + for (;;) { + ch = readch(); + switch (ch) { + 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 (ch = 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 * + 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) + return; + eval_string(p); +} + +void +eval(void) +{ + int ch; + + for (;;) { + ch = readch(); + if (ch == EOF) { + if (bmachine.readsp == 0) + return; + src_free(); + bmachine.readsp--; + continue; + } + if (bmachine.interrupted) { + if (bmachine.readsp > 0) { + src_free(); + bmachine.readsp--; + continue; + } else + bmachine.interrupted = false; + } +#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 + } +} diff --git a/usr.bin/dc/bcode.h b/usr.bin/dc/bcode.h new file mode 100644 index 0000000..df175fe --- /dev/null +++ b/usr.bin/dc/bcode.h @@ -0,0 +1,98 @@ +/* $FreeBSD$ */ +/* $OpenBSD: bcode.h,v 1.5 2006/01/16 08:09:25 otto Exp $ */ + +/* + * Copyright (c) 2003, Otto Moerbeek <otto@drijf.net> + * + * 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 <sys/types.h> +#include <openssl/bn.h> + +struct number { + BIGNUM *number; + u_int scale; +}; + +enum stacktype { + BCODE_NONE, + BCODE_NUMBER, + BCODE_STRING +}; + +enum bcode_compare { + BCODE_EQUAL, + BCODE_NOT_EQUAL, + BCODE_LESS, + BCODE_NOT_LESS, + BCODE_GREATER, + BCODE_NOT_GREATER +}; + +struct array; + +struct value { + union { + struct number *num; + char *string; + } u; + struct array *array; + enum stacktype type; +}; + +struct array { + struct value *data; + size_t size; +}; + +struct stack { + struct value *stack; + ssize_t sp; + ssize_t size; +}; + +struct source; + +struct vtable { + int (*readchar)(struct source *); + void (*unreadchar)(struct source *); + char *(*readline)(struct source *); + void (*free)(struct source *); +}; + +struct source { + struct vtable *vtable; + union { + FILE *stream; + struct { + u_char *buf; + size_t pos; + } string; + } u; + int lastchar; +}; + +void init_bmachine(bool); +void reset_bmachine(struct source *); +void scale_number(BIGNUM *, int); +void normalize(struct number *, u_int); +void eval(void); +void pn(const char *, const struct number *); +void pbn(const char *, const BIGNUM *); +void negate(struct number *); +void split_number(const struct number *, BIGNUM *, BIGNUM *); +void bmul_number(struct number *, struct number *, + struct number *); + +extern BIGNUM zero; diff --git a/usr.bin/dc/dc.1 b/usr.bin/dc/dc.1 new file mode 100644 index 0000000..1706538 --- /dev/null +++ b/usr.bin/dc/dc.1 @@ -0,0 +1,552 @@ +.\" $FreeBSD$ +.\" $OpenBSD: dc.1,v 1.24 2010/01/02 19:48:56 schwarze Exp $ +.\" +.\" Copyright (C) Caldera International Inc. 2001-2002. +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code and documentation must retain the above +.\" copyright notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. All advertising materials mentioning features or use of this software +.\" must display the following acknowledgement: +.\" This product includes software developed or owned by Caldera +.\" International, Inc. +.\" 4. Neither the name of Caldera International, Inc. nor the names of other +.\" contributors may be used to endorse or promote products derived from +.\" this software without specific prior written permission. +.\" +.\" USE OF THE SOFTWARE PROVIDED FOR UNDER THIS LICENSE BY CALDERA +.\" INTERNATIONAL, INC. 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 CALDERA INTERNATIONAL, INC. 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. +.\" +.\" @(#)dc.1 8.1 (Berkeley) 6/6/93 +.\" +.Dd Jan 28 2009 +.Dt DC 1 +.Os +.Sh NAME +.Nm dc +.Nd desk calculator +.Sh SYNOPSIS +.Nm +.Op Fl hxV +.Op Fl e Ar expression +.Op Fl f Ar filename +.Op Ar filename +.Sh DESCRIPTION +.Nm +is an arbitrary precision arithmetic package. +The overall structure of +.Nm +is +a stacking (reverse Polish) calculator i.e.\& +numbers are stored on a stack. +Adding a number pushes it onto the stack. +Arithmetic operations pop arguments off the stack +and push the results. +See also the +.Xr bc 1 +utility, which is a preprocessor for +.Nm +providing infix notation and a C-like syntax +which implements functions and reasonable control +structures for programs. +The options are as follows: +.Bl -tag -width Ds +.It Fl e Ar expr +.It Fl Fl expression Ar expr +Evaluate +.Ar expression . +If multiple +.Fl e +options are specified, they will be processed in the order given. +If no +.Ar filename +argument is given, execution will stop after processing the expressions +given on the command line, +otherwise processing will continue with the contents of +.Ar filename . +.It Fl f Ar filename +.It Fl Fl file Ar filename +Process the content of the given file before further calculations are done. +If multiple +.Fl f +options are specified, they will be processed in the order given. +.It Fl h +.It Fl Fl help +Print short usage info. +.It Fl V +.It Fl Fl version +Print version info. +.It Fl x +Enable extended register mode. +This mode is used by +.Xr bc 1 +to allow more than 256 registers. +See +.Sx Registers +for a more detailed description. +.El +.Pp +Ordinarily, +.Nm +operates on decimal integers, +but one may specify an input base, output base, +and a number of fractional digits (scale) to be maintained. +If an argument is given, +input is taken from that file until its end, +then from the standard input. +Whitespace is ignored, except where it signals the end of a number, +end of a line or when a register name is expected. +The following constructions are recognized: +.Bl -tag -width "number" +.It Va number +The value of the number is pushed on the stack. +A number is an unbroken string of the digits 0\-9 and letters A\-F. +It may be preceded by an underscore +.Pq Sq _ +to input a negative number. +A number may contain a single decimal point. +A number may also contain the characters A\-F, with the values 10\-15. +.It Cm "+ - / * % ~ ^" +The +top two values on the stack are added +(+), +subtracted +(\-), +multiplied (*), +divided (/), +remaindered (%), +divided and remaindered (~), +or exponentiated (^). +The two entries are popped off the stack; +the result is pushed on the stack in their place. +Any fractional part of an exponent is ignored. +.Pp +For addition and subtraction, the scale of the result is the maximum +of scales of the operands. +For division the scale of the result is defined +by the scale set by the +.Ic k +operation. +For multiplication, the scale is defined by the expression +.Sy min(a+b,max(a,b,scale)) , +where +.Sy a +and +.Sy b +are the scales of the operands, and +.Sy scale +is the scale defined by the +.Ic k +operation. +For exponentiation with a non-negative exponent, the scale of the result is +.Sy min(a*b,max(scale,a)) , +where +.Sy a +is the scale of the base, and +.Sy b +is the +.Em value +of the exponent. +If the exponent is negative, the scale of the result is the scale +defined by the +.Ic k +operation. +.Pp +In the case of the division and modulus operator (~), +the resultant quotient is pushed first followed by the remainder. +This is a shorthand for the sequence: +.Bd -literal -offset indent -compact +x y / x y % +.Ed +The division and modulus operator is a non-portable extension. +.It Ic a +Pop the top value from the stack. +If that value is a number, compute the integer part of the number modulo 256. +If the result is zero, push an empty string. +Otherwise push a one character string by interpreting the computed value +as an +.Tn ASCII +character. +.Pp +If the top value is a string, push a string containing the first character +of the original string. +If the original string is empty, an empty string is pushed back. +The +.Ic a +operator is a non-portable extension. +.It Ic c +All values on the stack are popped. +.It Ic d +The top value on the stack is duplicated. +.It Ic f +All values on the stack are printed, separated by newlines. +.It Ic G +The top two numbers are popped from the stack and compared. +A one is pushed if the top of the stack is equal to the second number +on the stack. +A zero is pushed otherwise. +This is a non-portable extension. +.It Ic I +Pushes the input base on the top of the stack. +.It Ic i +The top value on the stack is popped and used as the +base for further input. +The initial input base is 10. +.It Ic J +Pop the top value from the stack. +The recursion level is popped by that value and, following that, +the input is skipped until the first occurrence of the +.Ic M +operator. +The +.Ic J +operator is a non-portable extension, used by the +.Xr bc 1 +command. +.It Ic K +The current scale factor is pushed onto the stack. +.It Ic k +The top of the stack is popped, and that value is used as +a non-negative scale factor: +the appropriate number of places +are printed on output, +and maintained during multiplication, division, and exponentiation. +The interaction of scale factor, +input base, and output base will be reasonable if all are changed +together. +.It Ic L Ns Ar x +Register +.Ar x +is treated as a stack and its top value is popped onto the main stack. +.It Ic l Ns Ar x +The +value in register +.Ar x +is pushed on the stack. +The register +.Ar x +is not altered. +Initially, all registers contain the value zero. +.It Ic M +Mark used by the +.Ic J +operator. +The +.Ic M +operator is a non-portable extensions, used by the +.Xr bc 1 +command. +.It Ic N +The top of the stack is replaced by one if the top of the stack +is equal to zero. +If the top of the stack is unequal to zero, it is replaced by zero. +This is a non-portable extension. +.It Ic n +The top value on the stack is popped and printed without a newline. +This is a non-portable extension. +.It Ic O +Pushes the output base on the top of the stack. +.It Ic o +The top value on the stack is popped and used as the +base for further output. +The initial output base is 10. +.It Ic P +The top of the stack is popped. +If the top of the stack is a string, it is printed without a trailing newline. +If the top of the stack is a number, it is interpreted as a +base 256 number, and each digit of this base 256 number is printed as +an +.Tn ASCII +character, without a trailing newline. +.It Ic p +The top value on the stack is printed with a trailing newline. +The top value remains unchanged. +.It Ic Q +The top value on the stack is popped and the string execution level is popped +by that value. +.It Ic q +Exits the program. +If executing a string, the recursion level is +popped by two. +.It Ic R +The top of the stack is removed (popped). +This is a non-portable extension. +.It Ic r +The top two values on the stack are reversed (swapped). +This is a non-portable extension. +.It Ic S Ns Ar x +Register +.Ar x +is treated as a stack. +The top value of the main stack is popped and pushed on it. +.It Ic s Ns Ar x +The +top of the stack is popped and stored into +a register named +.Ar x . +.It Ic v +Replaces the top element on the stack by its square root. +The scale of the result is the maximum of the scale of the argument +and the current value of scale. +.It Ic X +Replaces the number on the top of the stack with its scale factor. +If the top of the stack is a string, replace it with the integer 0. +.It Ic x +Treats the top element of the stack as a character string +and executes it as a string of +.Nm +commands. +.It Ic Z +Replaces the number on the top of the stack with its length. +The length of a string is its number of characters. +The length of a number is its number of digits, not counting the minus sign +and decimal point. +.It Ic z +The stack level is pushed onto the stack. +.It Cm [ Ns ... Ns Cm ] +Puts the bracketed +.Tn ASCII +string onto the top of the stack. +If the string includes brackets, these must be properly balanced. +The backslash character +.Pq Sq \e +may be used as an escape character, making it +possible to include unbalanced brackets in strings. +To include a backslash in a string, use a double backslash. +.It Xo +.Cm < Ns Va x +.Cm > Ns Va x +.Cm = Ns Va x +.Cm !< Ns Va x +.Cm !> Ns Va x +.Cm != Ns Va x +.Xc +The top two elements of the stack are popped and compared. +Register +.Ar x +is executed if they obey the stated +relation. +.It Xo +.Cm < Ns Va x Ns e Ns Va y +.Cm > Ns Va x Ns e Ns Va y +.Cm = Ns Va x Ns e Ns Va y +.Cm !< Ns Va x Ns e Ns Va y +.Cm !> Ns Va x Ns e Ns Va y +.Cm != Ns Va x Ns e Ns Va y +.Xc +These operations are variants of the comparison operations above. +The first register name is followed by the letter +.Sq e +and another register name. +Register +.Ar x +will be executed if the relation is true, and register +.Ar y +will be executed if the relation is false. +This is a non-portable extension. +.It Ic \&( +The top two numbers are popped from the stack and compared. +A one is pushed if the top of the stack is less than the second number +on the stack. +A zero is pushed otherwise. +This is a non-portable extension. +.It Ic { +The top two numbers are popped from the stack and compared. +A one is pushed if the top of stack is less than or equal to the +second number on the stack. +A zero is pushed otherwise. +This is a non-portable extension. +.It Ic \&! +Interprets the rest of the line as a +.Ux +command. +.It Ic \&? +A line of input is taken from the input source (usually the terminal) +and executed. +.It Ic : Ns Ar r +Pop two values from the stack. +The second value on the stack is stored into the array +.Ar r +indexed by the top of stack. +.It Ic ; Ns Ar r +Pop a value from the stack. +The value is used as an index into register +.Ar r . +The value in this register is pushed onto the stack. +.Pp +Array elements initially have the value zero. +Each level of a stacked register has its own array associated with +it. +The command sequence +.Bd -literal -offset indent +[first] 0:a [dummy] Sa [second] 0:a 0;a p La 0;a p +.Ed +.Pp +will print +.Bd -literal -offset indent +second +first +.Ed +.Pp +since the string +.Ql second +is written in an array that is later popped, to reveal the array that +stored +.Ql first . +.It Ic # +Skip the rest of the line. +This is a non-portable extension. +.El +.Ss Registers +Registers have a single character name +.Ar x , +where +.Ar x +may be any character, including space, tab or any other special character. +If extended register mode is enabled using the +.Fl x +option and the register identifier +.Ar x +has the value 255, the next two characters are interpreted as a +two-byte register index. +The set of standard single character registers and the set of extended +registers do not overlap. +Extended register mode is a non-portable extension. +.Sh EXAMPLES +An example which prints the first ten values of +.Ic n! : +.Bd -literal -offset indent +[la1+dsa*pla10>y]sy +0sa1 +lyx +.Ed +.Pp +Independent of the current input base, the command +.Bd -literal -offset indent +Ai +.Ed +.Pp +will reset the input base to decimal 10. +.Sh DIAGNOSTICS +.Bl -diag +.It %c (0%o) is unimplemented +an undefined operation was called. +.It stack empty +for not enough elements on the stack to do what was asked. +.It stack register '%c' (0%o) is empty +for an +.Ar L +operation from a stack register that is empty. +.It Runtime warning: non-zero scale in exponent +for a fractional part of an exponent that is being ignored. +.It divide by zero +for trying to divide by zero. +.It remainder by zero +for trying to take a remainder by zero. +.It square root of negative number +for trying to take the square root of a negative number. +.It index too big +for an array index that is larger than 2048. +.It negative index +for a negative array index. +.It "input base must be a number between 2 and 16" +for trying to set an illegal input base. +.It output base must be a number greater than 1 +for trying to set an illegal output base. +.It scale must be a nonnegative number +for trying to set a negative or zero scale. +.It scale too large +for trying to set a scale that is too large. +A scale must be representable as a 32-bit unsigned number. +.It Q command argument exceeded string execution depth +for trying to pop the recursion level more than the current +recursion level. +.It Q command requires a number >= 1 +for trying to pop an illegal number of recursion levels. +.It recursion too deep +for too many levels of nested execution. +.Pp +The recursion level is increased by one if the +.Ar x +or +.Ar ?\& +operation or one of the compare operations resulting in the execution +of register is executed. +As an exception, the recursion level is not increased if the operation +is executed as the last command of a string. +For example, the commands +.Bd -literal -offset indent +[lax]sa +1 lax +.Ed +.Pp +will execute an endless loop, while the commands +.Bd -literal -offset indent +[laxp]sa +1 lax +.Ed +.Pp +will terminate because of a too deep recursion level. +.It J command argument exceeded string execution depth +for trying to pop the recursion level more than the current +recursion level. +.It mark not found +for a failed scan for an occurrence of the +.Ic M +operator. +.El +.Sh SEE ALSO +.Xr bc 1 +.Rs +.%B USD:05 +.%A L. L. Cherry +.%A R. Morris +.%T "DC \- An Interactive Desk Calculator" +.Re +.Sh STANDARDS +The arithmetic operations of the +.Nm +utility are expected to conform to the definition listed in the +.Xr bc 1 +section of the +.St -p1003.2 +specification. +.Sh HISTORY +The +.Nm +command first appeared in +.At v6 . +A complete rewrite of the +.Nm +command using the +.Xr bn 3 +big number routines first appeared in +.Ox 3.5 . +.Sh AUTHORS +.An -nosplit +The original version of the +.Nm +command was written by +.An Robert Morris +and +.An Lorinda Cherry . +The current version of the +.Nm +utility was written by +.An Otto Moerbeek . diff --git a/usr.bin/dc/dc.c b/usr.bin/dc/dc.c new file mode 100644 index 0000000..fd412b8 --- /dev/null +++ b/usr.bin/dc/dc.c @@ -0,0 +1,140 @@ +/* $OpenBSD: dc.c,v 1.11 2009/10/27 23:59:37 deraadt Exp $ */ + +/* + * Copyright (c) 2003, Otto Moerbeek <otto@drijf.net> + * Copyright (c) 2009, Gabor Kovesdan <gabor@FreeBSD.org> + * + * 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 <sys/cdefs.h> +__FBSDID("$FreeBSD$"); + +#include <sys/stat.h> + +#include <ctype.h> +#include <err.h> +#include <errno.h> +#include <getopt.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <unistd.h> + +#include "extern.h" + +#define DC_VER "1.3-FreeBSD" + +static void usage(void); + +extern char *__progname; + +struct source src; + +struct option long_options[] = +{ + {"expression", required_argument, NULL, 'e'}, + {"file", required_argument, NULL, 'f'}, + {"help", no_argument, NULL, 'h'}, + {"version", no_argument, NULL, 'V'} +}; + +static void +usage(void) +{ + fprintf(stderr, "usage: %s [-hVx] [-e expression] [file]\n", + __progname); + exit(1); +} + +static void +procfile(char *fname) { + FILE *file; + struct stat st; + + file = fopen(fname, "r"); + if (file == NULL) + err(1, "cannot open file %s", fname); + if (fstat(fileno(file), &st) == -1) + err(1, "%s", fname); + if (S_ISDIR(st.st_mode)) { + errno = EISDIR; + err(1, "%s", fname); + } + src_setstream(&src, file); + reset_bmachine(&src); + eval(); + fclose(file); +} + +int +main(int argc, char *argv[]) +{ + int ch; + bool extended_regs = false; + char *buf; + bool preproc_done = false; + + if ((buf = strdup("")) == NULL) + err(1, NULL); + + init_bmachine(extended_regs); + setlinebuf(stdout); + setlinebuf(stderr); + + /* accept and ignore a single dash to be 4.4BSD dc(1) compatible */ + while ((ch = getopt_long(argc, argv, "e:f:Vx", long_options, NULL)) != -1) { + switch (ch) { + case 'e': + src_setstring(&src, optarg); + reset_bmachine(&src); + eval(); + preproc_done = true; + break; + case 'f': + procfile(optarg); + preproc_done = true; + break; + case 'x': + extended_regs = true; + break; + case 'V': + fprintf(stderr, "%s (BSD bc) %s\n", __progname, DC_VER); + exit(0); + break; + case '-': + break; + case 'h': + /* FALLTHROUGH */ + default: + usage(); + } + } + argc -= optind; + argv += optind; + + if (argc > 1) + usage(); + if (argc == 1) { + procfile(argv[0]); + preproc_done = true; + } + if (preproc_done) + return (0); + + src_setstream(&src, stdin); + reset_bmachine(&src); + eval(); + + return (0); +} diff --git a/usr.bin/dc/extern.h b/usr.bin/dc/extern.h new file mode 100644 index 0000000..4abf063 --- /dev/null +++ b/usr.bin/dc/extern.h @@ -0,0 +1,63 @@ +/* $FreeBSD$ */ +/* $OpenBSD: extern.h,v 1.3 2006/01/16 08:09:25 otto Exp $ */ + +/* + * Copyright (c) 2003, Otto Moerbeek <otto@drijf.net> + * + * 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 <stdbool.h> +#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); +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 *); */ diff --git a/usr.bin/dc/inout.c b/usr.bin/dc/inout.c new file mode 100644 index 0000000..b3239bc --- /dev/null +++ b/usr.bin/dc/inout.c @@ -0,0 +1,417 @@ +/* $OpenBSD: inout.c,v 1.15 2009/10/27 23:59:37 deraadt Exp $ */ + +/* + * Copyright (c) 2003, Otto Moerbeek <otto@drijf.net> + * + * 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 <sys/cdefs.h> +__FBSDID("$FreeBSD$"); + +#include <openssl/ssl.h> +#include <ctype.h> +#include <err.h> +#include <string.h> + +#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 ch, i; + + 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 buf[12]; + char *q = buf; + + strlcpy(buf, p, sizeof(buf)); + while (*q) + putcharwrap(f, *q++); +} + +struct number * +readnumber(struct source *src, u_int base) +{ + struct number *n; + int ch; + bool sign = false; + bool dot = false; + BN_ULONG v; + u_int i; + + 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) +{ + int count, i, sz, new_sz, ch; + char *p; + 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); + 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 *int_part, *fract_part; + int digits; + char buf[11]; + size_t sz; + unsigned int i; + struct stack stack; + char *p; + + 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_cmp(b->number, &zero) < 0) + 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); + 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("<array>", 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 numbits, i, ch; + + v = BN_dup(n->number); + bn_checkp(v); + + if (BN_cmp(v, &zero) < 0) + bn_check(BN_sub(v, &zero, v)); + + 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); +} diff --git a/usr.bin/dc/mem.c b/usr.bin/dc/mem.c new file mode 100644 index 0000000..364d674 --- /dev/null +++ b/usr.bin/dc/mem.c @@ -0,0 +1,110 @@ +/* $OpenBSD: mem.c,v 1.5 2009/10/27 23:59:37 deraadt Exp $ */ + +/* + * Copyright (c) 2003, Otto Moerbeek <otto@drijf.net> + * + * 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 <sys/cdefs.h> +__FBSDID("$FreeBSD$"); + +#include <openssl/err.h> + +#include <err.h> +#include <stdlib.h> +#include <string.h> + +#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) +{ + void *q; + + q = realloc(p, sz); + 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()); +} diff --git a/usr.bin/dc/stack.c b/usr.bin/dc/stack.c new file mode 100644 index 0000000..775c563 --- /dev/null +++ b/usr.bin/dc/stack.c @@ -0,0 +1,379 @@ +/* $OpenBSD: stack.c,v 1.11 2009/10/27 23:59:37 deraadt Exp $ */ + +/* + * Copyright (c) 2003, Otto Moerbeek <otto@drijf.net> + * + * 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 <sys/cdefs.h> +__FBSDID("$FreeBSD$"); + +#include <err.h> +#include <stdlib.h> +#include <string.h> + +#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; + } + if (v->array != NULL) { + 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, i; + + if (++stack->sp == stack->size) { + new_size = stack->size * 2 + 1; + stack->stack = brealloc(stack->stack, + new_size * sizeof(*stack->stack)); + for (i = stack->size; i < new_size; i++) + stack->stack[i].array = NULL; + 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; +} + +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; +} + +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); + if (stack->stack[stack->sp].array != 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); + if (stack->stack[stack->sp].array != 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)); + 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); +} |