diff options
Diffstat (limited to 'usr.bin/dc')
| -rw-r--r-- | usr.bin/dc/Makefile | 10 | ||||
| -rw-r--r-- | usr.bin/dc/USD.doc/dc | 753 | ||||
| -rw-r--r-- | usr.bin/dc/bcode.c | 1775 | ||||
| -rw-r--r-- | usr.bin/dc/bcode.h | 98 | ||||
| -rw-r--r-- | usr.bin/dc/dc.1 | 548 | ||||
| -rw-r--r-- | usr.bin/dc/dc.c | 135 | ||||
| -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 |
10 files changed, 4288 insertions, 0 deletions
diff --git a/usr.bin/dc/Makefile b/usr.bin/dc/Makefile new file mode 100644 index 0000000..ee91c95 --- /dev/null +++ b/usr.bin/dc/Makefile @@ -0,0 +1,10 @@ +# $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 +CFLAGS+=--param max-inline-insns-single=64 +DPADD= ${LIBCRYPTO} +LDADD= -lcrypto + +.include <bsd.prog.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..e80c635 --- /dev/null +++ b/usr.bin/dc/bcode.c @@ -0,0 +1,1775 @@ +/* $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 source *readstack; + struct stack *reg; + struct stack stack; + volatile sig_atomic_t interrupted; + u_int scale; + u_int obase; + u_int ibase; + size_t readsp; + size_t reg_array_size; + size_t readstack_sz; + bool extended_regs; +}; + +static struct bmachine bmachine; +static 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) +{ + struct number *n; + size_t i; + + i = stack_size(&bmachine.stack); + n = new_number(); + bn_check(BN_set_word(n->number, i)); + push_number(n); +} + +static void +push_scale(void) +{ + struct number *n; + struct value *value; + u_int scale = 0; + + value = pop(); + if (value != NULL) { + switch (value->type) { + case BCODE_NONE: + return; + case BCODE_NUMBER: + scale = value->u.num->scale; + break; + case BCODE_STRING: + break; + } + stack_free_value(value); + n = new_number(); + bn_check(BN_set_word(n->number, scale)); + push_number(n); + } +} + +static u_int +count_digits(const struct number *n) +{ + struct number *int_part, *fract_part; + u_int i; + + if (BN_is_zero(n->number)) + return (1); + + int_part = new_number(); + fract_part = new_number(); + fract_part->scale = n->scale; + split_number(n, int_part->number, fract_part->number); + + i = 0; + while (!BN_is_zero(int_part->number)) { + BN_div_word(int_part->number, 10); + i++; + } + free_number(int_part); + free_number(fract_part); + return (i + n->scale); +} + +static void +num_digits(void) +{ + struct number *n = NULL; + struct value *value; + size_t digits; + + value = pop(); + if (value != NULL) { + switch (value->type) { + case BCODE_NONE: + return; + case BCODE_NUMBER: + digits = count_digits(value->u.num); + n = new_number(); + bn_check(BN_set_word(n->number, digits)); + break; + case BCODE_STRING: + digits = strlen(value->u.string); + n = new_number(); + bn_check(BN_set_word(n->number, digits)); + break; + } + stack_free_value(value); + push_number(n); + } +} + +static void +to_ascii(void) +{ + struct number *n; + struct value *value; + char str[2]; + + value = pop(); + if (value != NULL) { + str[1] = '\0'; + switch (value->type) { + case BCODE_NONE: + return; + case BCODE_NUMBER: + n = value->u.num; + normalize(n, 0); + if (BN_num_bits(n->number) > 8) + bn_check(BN_mask_bits(n->number, 8)); + str[0] = (char)BN_get_word(n->number); + break; + case BCODE_STRING: + str[0] = value->u.string[0]; + break; + } + stack_free_value(value); + push_string(bstrdup(str)); + } +} + +static int +readreg(void) +{ + int ch1, ch2, idx; + + idx = readch(); + if (idx == 0xff && bmachine.extended_regs) { + ch1 = readch(); + ch2 = readch(); + if (ch1 == EOF || ch2 == EOF) { + warnx("unexpected eof"); + idx = -1; + } else + idx = (ch1 << 8) + ch2 + UCHAR_MAX + 1; + } + if (idx < 0 || (unsigned)idx >= bmachine.reg_array_size) { + warnx("internal error: reg num = %d", idx); + idx = -1; + } + return (idx); +} + +static void +load(void) +{ + struct number *n; + struct value *v; + struct value copy; + int idx; + + idx = readreg(); + if (idx >= 0) { + v = stack_tos(&bmachine.reg[idx]); + if (v == NULL) { + n = new_number(); + bn_check(BN_zero(n->number)); + push_number(n); + } else + push(stack_dup_value(v, ©)); + } +} + +static void +store(void) +{ + struct value *val; + int idx; + + idx = readreg(); + if (idx >= 0) { + val = pop(); + if (val == NULL) { + return; + } + stack_set_tos(&bmachine.reg[idx], val); + } +} + +static void +load_stack(void) +{ + struct stack *stack; + struct value *value; + int idx; + + idx = readreg(); + if (idx >= 0) { + stack = &bmachine.reg[idx]; + value = NULL; + if (stack_size(stack) > 0) { + value = stack_pop(stack); + } + if (value != NULL) + push(value); + else + warnx("stack register '%c' (0%o) is empty", + idx, idx); + } +} + +static void +store_stack(void) +{ + struct value *value; + int idx; + + idx = readreg(); + if (idx >= 0) { + value = pop(); + if (value == NULL) + return; + stack_push(&bmachine.reg[idx], value); + } +} + +static void +load_array(void) +{ + struct number *inumber, *n; + struct stack *stack; + struct value *v; + struct value copy; + u_long idx; + int reg; + + reg = readreg(); + if (reg >= 0) { + inumber = pop_number(); + if (inumber == NULL) + return; + idx = get_ulong(inumber); + if (BN_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) +{ + struct number *inumber; + struct value *value; + struct stack *stack; + u_long idx; + int reg; + + reg = readreg(); + if (reg >= 0) { + inumber = pop_number(); + if (inumber == NULL) + return; + value = pop(); + if (value == NULL) { + free_number(inumber); + return; + } + idx = get_ulong(inumber); + if (BN_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, *r; + + a = pop_number(); + if (a == NULL) { + return; + } + b = pop_number(); + if (b == NULL) { + push_number(a); + return; + } + + r = new_number(); + r->scale = max(a->scale, b->scale); + if (r->scale > a->scale) + normalize(a, r->scale); + else if (r->scale > b->scale) + normalize(b, r->scale); + bn_check(BN_add(r->number, a->number, b->number)); + push_number(r); + free_number(a); + free_number(b); +} + +static void +bsub(void) +{ + struct number *a, *b, *r; + + a = pop_number(); + if (a == NULL) { + return; + } + b = pop_number(); + if (b == NULL) { + push_number(a); + return; + } + + r = new_number(); + + r->scale = max(a->scale, b->scale); + if (r->scale > a->scale) + normalize(a, r->scale); + else if (r->scale > b->scale) + normalize(b, r->scale); + bn_check(BN_sub(r->number, b->number, a->number)); + push_number(r); + free_number(a); + free_number(b); +} + +void +bmul_number(struct number *r, struct number *a, struct number *b) +{ + 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, *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, *r; + BN_CTX *ctx; + u_int scale; + + a = pop_number(); + if (a == NULL) { + return; + } + b = pop_number(); + if (b == NULL) { + push_number(a); + return; + } + + r = new_number(); + r->scale = bmachine.scale; + scale = max(a->scale, b->scale); + + if (BN_is_zero(a->number)) + warnx("divide by zero"); + else { + normalize(a, scale); + normalize(b, scale + r->scale); + + ctx = BN_CTX_new(); + bn_checkp(ctx); + bn_check(BN_div(r->number, NULL, b->number, a->number, ctx)); + BN_CTX_free(ctx); + } + push_number(r); + free_number(a); + free_number(b); +} + +static void +bmod(void) +{ + struct number *a, *b, *r; + BN_CTX *ctx; + u_int scale; + + a = pop_number(); + if (a == NULL) { + return; + } + b = pop_number(); + if (b == NULL) { + push_number(a); + return; + } + + r = new_number(); + scale = max(a->scale, b->scale); + r->scale = max(b->scale, a->scale + bmachine.scale); + + if (BN_is_zero(a->number)) + warnx("remainder by zero"); + else { + normalize(a, scale); + normalize(b, scale + bmachine.scale); + + ctx = BN_CTX_new(); + bn_checkp(ctx); + bn_check(BN_mod(r->number, b->number, a->number, ctx)); + BN_CTX_free(ctx); + } + push_number(r); + free_number(a); + free_number(b); +} + +static void +bdivmod(void) +{ + struct number *a, *b, *rdiv, *rmod; + BN_CTX *ctx; + u_int scale; + + a = pop_number(); + if (a == NULL) { + return; + } + b = pop_number(); + if (b == NULL) { + push_number(a); + return; + } + + rdiv = new_number(); + rmod = new_number(); + rdiv->scale = bmachine.scale; + rmod->scale = max(b->scale, a->scale + bmachine.scale); + scale = max(a->scale, b->scale); + + if (BN_is_zero(a->number)) + warnx("divide by zero"); + else { + normalize(a, scale); + normalize(b, scale + bmachine.scale); + + ctx = BN_CTX_new(); + bn_checkp(ctx); + bn_check(BN_div(rdiv->number, rmod->number, + b->number, a->number, ctx)); + BN_CTX_free(ctx); + } + push_number(rdiv); + push_number(rmod); + free_number(a); + free_number(b); +} + +static void +bexp(void) +{ + struct number *a, *p, *r; + u_int scale; + bool neg; + + 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, *r; + BIGNUM *x, *y; + BN_CTX *ctx; + u_int onecount, scale; + + onecount = 0; + n = pop_number(); + if (n == NULL) { + return; + } + if (BN_is_zero(n->number)) { + r = new_number(); + push_number(r); + } else if (BN_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) +{ + struct number *a, *b; + struct value *v; + int idx, elseidx; + bool ok; + + elseidx = NO_ELSE; + idx = readreg(); + if (readch() == 'e') + elseidx = readreg(); + else + unreadch(); + + a = pop_number(); + if (a == NULL) + return; + b = pop_number(); + if (b == NULL) { + push_number(a); + return; + } + + ok = compare_numbers(type, a, b); + + if (!ok && elseidx != NO_ELSE) + idx = elseidx; + + if (idx >= 0 && (ok || (!ok && elseidx != NO_ELSE))) { + v = stack_tos(&bmachine.reg[idx]); + if (v == NULL) + warnx("register '%c' (0%o) is empty", idx, idx); + else { + switch(v->type) { + case BCODE_NONE: + warnx("register '%c' (0%o) is empty", idx, idx); + break; + case BCODE_NUMBER: + warn("eval called with non-string argument"); + break; + case BCODE_STRING: + eval_string(bstrdup(v->u.string)); + break; + } + } + } +} + + +static void +nop(void) +{ + +} + +static void +quit(void) +{ + + if (bmachine.readsp < 2) + exit(0); + src_free(); + bmachine.readsp--; + src_free(); + bmachine.readsp--; +} + +static void +quitN(void) +{ + struct number *n; + u_long i; + + n = pop_number(); + if (n == NULL) + return; + i = get_ulong(n); + free_number(n); + if (i == BN_MASK2 || i == 0) + warnx("Q command requires a number >= 1"); + else if (bmachine.readsp < i) + warnx("Q command argument exceeded string execution depth"); + else { + while (i-- > 0) { + src_free(); + bmachine.readsp--; + } + } +} + +static void +skipN(void) +{ + struct number *n; + u_long i; + + n = pop_number(); + if (n == NULL) + return; + i = get_ulong(n); + if (i == BN_MASK2) + warnx("J command requires a number >= 0"); + else if (i > 0 && bmachine.readsp < i) + warnx("J command argument exceeded string execution depth"); + else { + while (i-- > 0) { + src_free(); + bmachine.readsp--; + } + skip_until_mark(); + } +} + +static void +skip_until_mark(void) +{ + + for (;;) { + switch (readch()) { + case 'M': + return; + case EOF: + errx(1, "mark not found"); + return; + case 'l': + case 'L': + case 's': + case 'S': + case ':': + case ';': + case '<': + case '>': + case '=': + readreg(); + if (readch() == 'e') + readreg(); + else + unreadch(); + break; + case '[': + free(read_string(&bmachine.readstack[bmachine.readsp])); + break; + case '!': + switch (readch()) { + case '<': + case '>': + case '=': + readreg(); + if (readch() == 'e') + readreg(); + else + unreadch(); + break; + default: + free(readline()); + break; + } + break; + default: + break; + } + } +} + +static void +parse_number(void) +{ + + unreadch(); + push_number(readnumber(&bmachine.readstack[bmachine.readsp], + bmachine.ibase)); +} + +static void +unknown(void) +{ + int ch = bmachine.readstack[bmachine.readsp].lastchar; + warnx("%c (0%o) is unimplemented", ch, ch); +} + +static void +eval_string(char *p) +{ + int ch; + + if (bmachine.readsp > 0) { + /* Check for tail call. Do not recurse in that case. */ + ch = readch(); + if (ch == EOF) { + src_free(); + src_setstring(&bmachine.readstack[bmachine.readsp], p); + return; + } else + unreadch(); + } + if (bmachine.readsp == bmachine.readstack_sz - 1) { + size_t newsz = bmachine.readstack_sz * 2; + struct source *stack; + stack = realloc(bmachine.readstack, newsz * + 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..9290cf1 --- /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 size; + ssize_t sp; +}; + +struct source; + +struct vtable { + int (*readchar)(struct source *); + void (*unreadchar)(struct source *); + char *(*readline)(struct source *); + void (*free)(struct source *); +}; + +struct source { + union { + struct { + u_char *buf; + size_t pos; + } string; + FILE *stream; + } u; + struct vtable *vtable; + 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..03fc762 --- /dev/null +++ b/usr.bin/dc/dc.1 @@ -0,0 +1,548 @@ +.\" $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 January 22, 2010 +.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 , 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 , 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 , Fl Fl help +Print short usage info. +.It Fl V , 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 +.Pp +.An -nosplit +.An L. L. Cherry , +.An R. Morris +"DC \- An Interactive Desk Calculator" +.Pa /usr/share/doc/usd/05.dc/ . +.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..1376653 --- /dev/null +++ b/usr.bin/dc/dc.c @@ -0,0 +1,135 @@ +/* $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) { + struct stat st; + FILE *file; + + 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, preproc_done = false; + + /* 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; + + init_bmachine(extended_regs); + setlinebuf(stdout); + setlinebuf(stderr); + + 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..4a2bb70 --- /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 i, ch; + + i = 0; + while (i < BUFSIZ-1) { + ch = src_getcharstring(src); + if (ch == EOF) + break; + buf[i++] = ch; + if (ch == '\n') + break; + } + buf[i] = '\0'; + return (bstrdup(buf)); +} + +static void +src_freestring(struct source *src) +{ + + free(src->u.string.buf); +} + +static void +flushwrap(FILE *f) +{ + + if (lastchar != -1) + putc(lastchar, f); +} + +static void +putcharwrap(FILE *f, int ch) +{ + + if (charcount >= MAX_CHARS_PER_LINE) { + charcount = 0; + fputs("\\\n", f); + } + if (lastchar != -1) { + charcount++; + putc(lastchar, f); + } + lastchar = ch; +} + +static void +printwrap(FILE *f, const char *p) +{ + char *q; + char buf[12]; + + q = buf; + strlcpy(buf, p, sizeof(buf)); + while (*q) + putcharwrap(f, *q++); +} + +struct number * +readnumber(struct source *src, u_int base) +{ + struct number *n; + BN_ULONG v; + u_int i; + int ch; + bool dot = false, sign = false; + + n = new_number(); + bn_check(BN_zero(n->number)); + + while ((ch = (*src->vtable->readchar)(src)) != EOF) { + + if ('0' <= ch && ch <= '9') + v = ch - '0'; + else if ('A' <= ch && ch <= 'F') + v = ch - 'A' + 10; + else if (ch == '_') { + sign = true; + continue; + } else if (ch == '.') { + if (dot) + break; + dot = true; + continue; + } else { + (*src->vtable->unreadchar)(src); + break; + } + if (dot) + n->scale++; + + bn_check(BN_mul_word(n->number, base)); + +#if 0 + /* work around a bug in BN_add_word: 0 += 0 is buggy.... */ + if (v > 0) +#endif + bn_check(BN_add_word(n->number, v)); + } + if (base != 10) { + scale_number(n->number, n->scale); + for (i = 0; i < n->scale; i++) + BN_div_word(n->number, base); + } + if (sign) + negate(n); + return (n); +} + +char * +read_string(struct source *src) +{ + char *p; + int count, ch, i, new_sz, sz; + bool escape; + + escape = false; + count = 1; + i = 0; + sz = 15; + p = bmalloc(sz + 1); + + while ((ch = (*src->vtable->readchar)(src)) != EOF) { + if (!escape) { + if (ch == '[') + count++; + else if (ch == ']') + count--; + if (count == 0) + break; + } + if (ch == '\\' && !escape) + escape = true; + else { + escape = false; + if (i == sz) { + new_sz = sz * 2; + p = brealloc(p, new_sz + 1); + sz = new_sz; + } + p[i++] = ch; + } + } + p[i] = '\0'; + return (p); +} + +static char * +get_digit(u_long num, int digits, u_int base) +{ + char *p; + + if (base <= 16) { + p = bmalloc(2); + p[0] = num >= 10 ? num + 'A' - 10 : num + '0'; + p[1] = '\0'; + } else { + if (asprintf(&p, "%0*lu", digits, num) == -1) + err(1, NULL); + } + return (p); +} + +void +printnumber(FILE *f, const struct number *b, u_int base) +{ + struct number *fract_part, *int_part; + struct stack stack; + char *p; + char buf[11]; + size_t sz; + unsigned int i; + int digits; + + charcount = 0; + lastchar = -1; + if (BN_is_zero(b->number)) + putcharwrap(f, '0'); + + int_part = new_number(); + fract_part = new_number(); + fract_part->scale = b->scale; + + if (base <= 16) + digits = 1; + else { + digits = snprintf(buf, sizeof(buf), "%u", base-1); + } + split_number(b, int_part->number, fract_part->number); + + i = 0; + stack_init(&stack); + while (!BN_is_zero(int_part->number)) { + BN_ULONG rem = BN_div_word(int_part->number, base); + stack_pushstring(&stack, get_digit(rem, digits, base)); + i++; + } + sz = i; + if (BN_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 ch, i, numbits; + + 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..78fb429 --- /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..950b4e5 --- /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 i, new_size; + + 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); +} |
