diff options
Diffstat (limited to 'lib/libc/stdlib')
68 files changed, 8727 insertions, 0 deletions
diff --git a/lib/libc/stdlib/Makefile.inc b/lib/libc/stdlib/Makefile.inc new file mode 100644 index 000000000000..972887fbd82a --- /dev/null +++ b/lib/libc/stdlib/Makefile.inc @@ -0,0 +1,37 @@ +# @(#)Makefile.inc 5.6 (Berkeley) 6/4/91 + +# stdlib sources +.PATH: ${.CURDIR}/${MACHINE}/stdlib ${.CURDIR}/stdlib + +SRCS+= abort.c atexit.c atoi.c atol.c bsearch.c calloc.c div.c exit.c \ + getenv.c getopt.c heapsort.c malloc.c multibyte.c \ + putenv.c qsort.c radixsort.c rand.c random.c setenv.c strtod.c \ + strtol.c strtoul.c system.c \ + _rand48.c drand48.c erand48.c jrand48.c lcong48.c lrand48.c \ + mrand48.c nrand48.c seed48.c srand48.c + +.if (${MACHINE} == "hp300") +SRCS+= abs.s div.c labs.c ldiv.c atof.c +.elif (${MACHINE} == "i386") +SRCS+= abs.s div.s labs.s ldiv.s atof.c +.elif (${MACHINE} == "tahoe") +SRCS+= abs.s div.c labs.c ldiv.c atof.c +.elif (${MACHINE} == "vax") +SRCS+= abs.s div.c labs.c ldiv.c atof.c +.endif + +MAN3+= stdlib/abort.3 stdlib/abs.3 stdlib/alloca.3 stdlib/atexit.3 \ + stdlib/atof.3 stdlib/atoi.3 stdlib/atol.3 stdlib/bsearch.3 \ + stdlib/calloc.3 stdlib/div.3 stdlib/exit.3 stdlib/free.3 \ + stdlib/getenv.3 stdlib/getopt.3 stdlib/labs.3 stdlib/ldiv.3 \ + stdlib/malloc.3 stdlib/memory.3 stdlib/qsort.3 stdlib/radixsort.3 \ + stdlib/rand.3 stdlib/rand48.3 stdlib/random.3 stdlib/realloc.3 \ + stdlib/strtod.3 stdlib/strtol.3 stdlib/strtoul.3 stdlib/system.3 + +MLINKS+=getenv.3 setenv.3 getenv.3 unsetenv.3 getenv.3 putenv.3 +MLINKS+=qsort.3 heapsort.3 +MLINKS+=rand.3 srand.3 +MLINKS+=random.3 initstate.3 random.3 setstate.3 random.3 srandom.3 +MLINKS+=rand48.3 drand48.3 rand48.3 erand48.3 rand48.3 lrand48.3 +MLINKS+=rand48.3 mrand48.3 rand48.3 nrand48.3 rand48.3 jrand48.3 +MLINKS+=rand48.3 srand48.3 rand48.3 seed48.3 rand48.3 lcong48.3 diff --git a/lib/libc/stdlib/_rand48.c b/lib/libc/stdlib/_rand48.c new file mode 100644 index 000000000000..990e2c86949b --- /dev/null +++ b/lib/libc/stdlib/_rand48.c @@ -0,0 +1,46 @@ +/* + * Copyright (c) 1993 Martin Birgmeier + * All rights reserved. + * + * You may redistribute unmodified or modified versions of this source + * code provided that the above copyright notice and this and the + * following conditions are retained. + * + * This software is provided ``as is'', and comes with no warranties + * of any kind. I shall in no event be liable for anything that happens + * to anyone/anything when using this software. + */ + +#include "rand48.h" + +unsigned short _rand48_seed[3] = { + RAND48_SEED_0, + RAND48_SEED_1, + RAND48_SEED_2 +}; +unsigned short _rand48_mult[3] = { + RAND48_MULT_0, + RAND48_MULT_1, + RAND48_MULT_2 +}; +unsigned short _rand48_add = RAND48_ADD; + +void +_dorand48(unsigned short xseed[3]) +{ + unsigned long accu; + unsigned short temp[2]; + + accu = (unsigned long) _rand48_mult[0] * (unsigned long) xseed[0] + + (unsigned long) _rand48_add; + temp[0] = (unsigned short) accu; /* lower 16 bits */ + accu >>= sizeof(unsigned short) * 8; + accu += (unsigned long) _rand48_mult[0] * (unsigned long) xseed[1] + + (unsigned long) _rand48_mult[1] * (unsigned long) xseed[0]; + temp[1] = (unsigned short) accu; /* middle 16 bits */ + accu >>= sizeof(unsigned short) * 8; + accu += _rand48_mult[0] * xseed[2] + _rand48_mult[1] * xseed[1] + _rand48_mult[2] * xseed[0]; + xseed[0] = temp[0]; + xseed[1] = temp[1]; + xseed[2] = (unsigned short) accu; +} diff --git a/lib/libc/stdlib/abort.3 b/lib/libc/stdlib/abort.3 new file mode 100644 index 000000000000..b8037821d708 --- /dev/null +++ b/lib/libc/stdlib/abort.3 @@ -0,0 +1,70 @@ +.\" Copyright (c) 1990, 1991 The Regents of the University of California. +.\" All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" the American National Standards Committee X3, on Information +.\" Processing Systems. +.\" +.\" 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 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 by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)abort.3 6.7 (Berkeley) 6/29/91 +.\" +.Dd June 29, 1991 +.Dt ABORT 3 +.Os +.Sh NAME +.Nm abort +.Nd cause abnormal program termination +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft void +.Fn abort void +.Sh DESCRIPTION +The +.Fn abort +function causes abnormal program termination to occur, unless the +signal +.Dv SIGABRT +is being caught and the signal handler does not return. +.Pp +No open streams are closed or flushed. +.Sh RETURN VALUES +The +.Nm abort +function +never returns. +.Sh SEE ALSO +.Xr sigaction 2 , +.Xr exit 2 +.Sh STANDARDS +The +.Fn abort +function +conforms to +.St -ansiC . diff --git a/lib/libc/stdlib/abort.c b/lib/libc/stdlib/abort.c new file mode 100644 index 000000000000..b5393e9a710c --- /dev/null +++ b/lib/libc/stdlib/abort.c @@ -0,0 +1,65 @@ +/* + * Copyright (c) 1985 Regents of the University of California. + * 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 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 by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)abort.c 5.11 (Berkeley) 2/23/91"; +#endif /* LIBC_SCCS and not lint */ + +#include <sys/signal.h> +#include <stdlib.h> +#include <stddef.h> +#include <unistd.h> + +void +abort() +{ + sigset_t mask; + + sigfillset(&mask); + /* + * don't block SIGABRT to give any handler a chance; we ignore + * any errors -- X311J doesn't allow abort to return anyway. + */ + sigdelset(&mask, SIGABRT); + (void)sigprocmask(SIG_SETMASK, &mask, (sigset_t *)NULL); + (void)kill(getpid(), SIGABRT); + + /* + * if SIGABRT ignored, or caught and the handler returns, do + * it again, only harder. + */ + (void)signal(SIGABRT, SIG_DFL); + (void)sigprocmask(SIG_SETMASK, &mask, (sigset_t *)NULL); + (void)kill(getpid(), SIGABRT); + exit(1); +} diff --git a/lib/libc/stdlib/abs.3 b/lib/libc/stdlib/abs.3 new file mode 100644 index 000000000000..2de161c4fc99 --- /dev/null +++ b/lib/libc/stdlib/abs.3 @@ -0,0 +1,73 @@ +.\" Copyright (c) 1990, 1991 The Regents of the University of California. +.\" All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" the American National Standards Committee X3, on Information +.\" Processing Systems. +.\" +.\" 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 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 by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)abs.3 6.4 (Berkeley) 6/29/91 +.\" +.Dd June 29, 1991 +.Dt ABS 3 +.Os +.Sh NAME +.Nm abs +.Nd integer absolute value function +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft int +.Fn abs "int j" +.Sh DESCRIPTION +The +.Fn abs +function +computes +the absolute value of the integer +.Ar j . +.Sh RETURN VALUES +The +.Fn abs +function +returns +the absolute value. +.Sh SEE ALSO +.Xr floor 3 , +.Xr labs 3 +.Xr cabs 3 +.Xr hypot 3 +.Xr math 3 +.Sh STANDARDS +The +.Fn abs +function conforms to +.St -ansiC . +.Sh BUGS +The absolute value of the most negative integer remains negative. diff --git a/lib/libc/stdlib/abs.c b/lib/libc/stdlib/abs.c new file mode 100644 index 000000000000..ebfd1a5f1ef7 --- /dev/null +++ b/lib/libc/stdlib/abs.c @@ -0,0 +1,45 @@ +/*- + * Copyright (c) 1990 The Regents of the University of California. + * 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 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 by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)abs.c 5.2 (Berkeley) 5/17/90"; +#endif /* LIBC_SCCS and not lint */ + +#include <stdlib.h> + +int +abs(j) + int j; +{ + return(j < 0 ? -j : j); +} diff --git a/lib/libc/stdlib/alloca.3 b/lib/libc/stdlib/alloca.3 new file mode 100644 index 000000000000..350fe9b88891 --- /dev/null +++ b/lib/libc/stdlib/alloca.3 @@ -0,0 +1,78 @@ +.\" Copyright (c) 1980, 1991 Regents of the University of California. +.\" 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 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 by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)alloca.3 5.1 (Berkeley) 5/2/91 +.\" +.Dd May 2, 1991 +.Dt ALLOCA 3 +.Os BSD 4 +.Sh NAME +.Nm alloca +.Nd memory allocator +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft void * +.Fn alloca "size_t size" +.Sh DESCRIPTION +The +.Fn alloca +function +allocates +.Fa size +bytes of space in the stack frame of the caller. +This temporary space is automatically freed on +return. +.Sh RETURN VALUES +The +.Fn alloca +function returns a pointer to the beginning of the allocated space. +If the allocation failed, a +.Dv NULL +pointer is returned. +.Sh SEE ALSO +.Xr brk 2 , +.Xr pagesize 2 +.Xr calloc 3 , +.Xr malloc 3 , +.Xr realloc 3 , +.Sh BUGS +The +.Fn alloca +function +is machine dependent; its use is discouraged. +.\" .Sh HISTORY +.\" The +.\" .Fn alloca +.\" function appeared in +.\" .Bx ?? . +.\" The function appeared in 32v, pwb and pwb.2 and in 3bsd 4bsd +.\" The first man page (or link to a man page that I can find at the +.\" moment is 4.3... diff --git a/lib/libc/stdlib/atexit.3 b/lib/libc/stdlib/atexit.3 new file mode 100644 index 000000000000..f68382e7ce76 --- /dev/null +++ b/lib/libc/stdlib/atexit.3 @@ -0,0 +1,77 @@ +.\" Copyright (c) 1990, 1991 The Regents of the University of California. +.\" All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" Chris Torek and the American National Standards Committee X3, +.\" on Information Processing Systems. +.\" +.\" 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 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 by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)atexit.3 5.3 (Berkeley) 6/29/91 +.\" +.Dd June 29, 1991 +.Dt ATEXIT 3 +.Os +.Sh NAME +.Nm atexit +.Nd register a function to be called on exit +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft int +.Fn atexit "void (*function)(void)" +.Sh DESCRIPTION +The +.Fn atexit +function +registers the given +.Ar function +to be called at program exit, whether via +.Xr exit 3 +or via return from the program's +.Em main . +Functions so registered are called in reverse order; +no arguments are passed. +At least 32 functions can always be registered, +and more are allowed as long as sufficient memory can be allocated. +.Sh RETURN VALUES +.Rv -std atexit +.Sh ERRORS +.Bl -tag -width [ENOMEM] +.It Bq Er ENOMEM +No memory was available to add the function to the list. +The existing list of functions is unmodified. +.El +.Sh SEE ALSO +.Xr exit 3 +.Sh STANDARDS +The +.Fn atexit +function +conforms to +.St -ansiC . diff --git a/lib/libc/stdlib/atexit.c b/lib/libc/stdlib/atexit.c new file mode 100644 index 000000000000..06d1d6b96375 --- /dev/null +++ b/lib/libc/stdlib/atexit.c @@ -0,0 +1,66 @@ +/*- + * Copyright (c) 1990 The Regents of the University of California. + * All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Chris Torek. + * + * 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 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 by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)atexit.c 5.2 (Berkeley) 11/14/90"; +#endif /* LIBC_SCCS and not lint */ + +#include <stddef.h> +#include <stdlib.h> +#include "atexit.h" + +/* + * Register a function to be performed at exit. + */ +int +atexit(fn) + void (*fn)(); +{ + static struct atexit __atexit0; /* one guaranteed table */ + register struct atexit *p; + + if ((p = __atexit) == NULL) + __atexit = p = &__atexit0; + else if (p->ind >= ATEXIT_SIZE) { + if ((p = malloc(sizeof(*p))) == NULL) + return (-1); + p->ind = 0; + p->next = __atexit; + __atexit = p; + } + p->fns[p->ind++] = fn; + return (0); +} diff --git a/lib/libc/stdlib/atexit.h b/lib/libc/stdlib/atexit.h new file mode 100644 index 000000000000..4ec9bb976d49 --- /dev/null +++ b/lib/libc/stdlib/atexit.h @@ -0,0 +1,45 @@ +/*- + * Copyright (c) 1990 The Regents of the University of California. + * 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 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 by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + * @(#)atexit.h 5.1 (Berkeley) 5/15/90 + */ + +/* must be at least 32 to guarantee ANSI conformance */ +#define ATEXIT_SIZE 32 + +struct atexit { + struct atexit *next; /* next in list */ + int ind; /* next index in this table */ + void (*fns[ATEXIT_SIZE])(); /* the table itself */ +}; + +struct atexit *__atexit; /* points to head of LIFO stack */ diff --git a/lib/libc/stdlib/atof.3 b/lib/libc/stdlib/atof.3 new file mode 100644 index 000000000000..4f30b50e1326 --- /dev/null +++ b/lib/libc/stdlib/atof.3 @@ -0,0 +1,87 @@ +.\" Copyright (c) 1991 The Regents of the University of California. +.\" All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" the American National Standards Committee X3, on Information +.\" Processing Systems. +.\" +.\" 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 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 by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)atof.3 6.4 (Berkeley) 6/29/91 +.\" +.Dd June 29, 1991 +.Dt ATOF 3 +.Os +.Sh NAME +.Nm atof +.Nd convert +.Tn ASCII +string to double +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft double +.Fn atof "const char *nptr" +.Sh DESCRIPTION +The +.Fn atof +function converts the initial portion of the string pointed to by +.Ar nptr +to +.Ar double +representation. +.Pp +It is equivalent to: +.Bd -literal -offset indent +strtod(nptr, (char **)NULL); +.Ed +.Sh SEE ALSO +.Xr atoi 3 , +.Xr atol 3 , +.Xr strtod 3 , +.Xr strtol 3 , +.Xr strtoul 3 +.Sh STANDARDS +The +.Fn atof +function conforms to +.St -ansiC . +.Sh BUGS +This manual page represents intent instead of actual practice. +While it is intended that +.Fn atof +be implemented using +.Xr strtod 3 , +this has not yet happened. +In the current system, +.Fn atof +translates a string in the following form to a double: a string of +leading white space, possibly followed by a sign (``+'' or ``-''), +followed by a digit string which may contain one decimal point (``.''), +which may be followed by either of the exponent flags (``E'' or ``e''), +and lastly, followed by a signed or unsigned integer. diff --git a/lib/libc/stdlib/atof.c b/lib/libc/stdlib/atof.c new file mode 100644 index 000000000000..c3577abfa275 --- /dev/null +++ b/lib/libc/stdlib/atof.c @@ -0,0 +1,46 @@ +/* + * Copyright (c) 1988 The Regents of the University of California. + * 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 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 by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)atof.c 5.3 (Berkeley) 1/8/93"; +#endif /* LIBC_SCCS and not lint */ + +#include <stdlib.h> +#include <stddef.h> + +double +atof(ascii) + const char *ascii; +{ + return(strtod(ascii, (char **)NULL)); +} diff --git a/lib/libc/stdlib/atoi.3 b/lib/libc/stdlib/atoi.3 new file mode 100644 index 000000000000..eccd780fb974 --- /dev/null +++ b/lib/libc/stdlib/atoi.3 @@ -0,0 +1,74 @@ +.\" Copyright (c) 1990, 1991 The Regents of the University of California. +.\" All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" the American National Standards Committee X3, on Information +.\" Processing Systems. +.\" +.\" 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 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 by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)atoi.3 5.3 (Berkeley) 6/29/91 +.\" +.Dd June 29, 1991 +.Dt ATOI 3 +.Os +.Sh NAME +.Nm atoi +.Nd convert +.Tn ASCII +string to integer +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft int +.Fn atoi "const char *nptr" +.Sh DESCRIPTION +The +.Fn atoi +function converts the initial portion of the string pointed to by +.Em nptr +to +.Em integer +representation. +.Pp +It is equivalent to: +.Pp +.Bd -literal -offset indent +(int)strtol(nptr, (char **)NULL, 10); +.Ed +.Sh SEE ALSO +.Xr atof 3 , +.Xr atol 3 , +.Xr strtod 3 , +.Xr strtol 3 , +.Xr strtoul 3 +.Sh STANDARDS +The +.Fn atoi +function conforms to +.St -ansiC . diff --git a/lib/libc/stdlib/atoi.c b/lib/libc/stdlib/atoi.c new file mode 100644 index 000000000000..c100c88bb049 --- /dev/null +++ b/lib/libc/stdlib/atoi.c @@ -0,0 +1,45 @@ +/* + * Copyright (c) 1988 Regents of the University of California. + * 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 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 by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)atoi.c 5.7 (Berkeley) 2/23/91"; +#endif /* LIBC_SCCS and not lint */ + +#include <stdlib.h> +#include <stddef.h> + +atoi(str) + const char *str; +{ + return((int)strtol(str, (char **)NULL, 10)); +} diff --git a/lib/libc/stdlib/atol.3 b/lib/libc/stdlib/atol.3 new file mode 100644 index 000000000000..326fc0177153 --- /dev/null +++ b/lib/libc/stdlib/atol.3 @@ -0,0 +1,74 @@ +.\" Copyright (c) 1990, 1991 The Regents of the University of California. +.\" All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" the American National Standards Committee X3, on Information +.\" Processing Systems. +.\" +.\" 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 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 by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)atol.3 5.3 (Berkeley) 6/29/91 +.\" +.Dd June 29, 1991 +.Dt ATOL 3 +.Os +.Sh NAME +.Nm atol +.Nd convert +.Tn ASCII +string to long integer +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft long +.Fn atol "const char *nptr" +.Sh DESCRIPTION +The +.Fn atol +function converts the initial portion of the string pointed to by +.Ar nptr +to +.Em long integer +representation. +.Pp +It is equivalent to: +.Bd -literal -offset indent +strtol(nptr, (char **)NULL, 10); +.Ed +.Sh SEE ALSO +.Xr atof 3 , +.Xr atoi 3 , +.Xr strtod 3 , +.Xr strtol 3 , +.Xr strtoul 3 +.Sh STANDARDS +The +.Fn atol +function +conforms to +.St -ansiC . diff --git a/lib/libc/stdlib/atol.c b/lib/libc/stdlib/atol.c new file mode 100644 index 000000000000..920302edb3c3 --- /dev/null +++ b/lib/libc/stdlib/atol.c @@ -0,0 +1,46 @@ +/* + * Copyright (c) 1988 Regents of the University of California. + * 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 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 by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)atol.c 5.7 (Berkeley) 2/23/91"; +#endif /* LIBC_SCCS and not lint */ + +#include <stddef.h> +#include <stdlib.h> + +long +atol(str) + const char *str; +{ + return(strtol(str, (char **)NULL, 10)); +} diff --git a/lib/libc/stdlib/bsearch.3 b/lib/libc/stdlib/bsearch.3 new file mode 100644 index 000000000000..35c5a426f522 --- /dev/null +++ b/lib/libc/stdlib/bsearch.3 @@ -0,0 +1,90 @@ +.\" Copyright (c) 1990, 1991 The Regents of the University of California. +.\" All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" the American National Standards Committee X3, on Information +.\" Processing Systems. +.\" +.\" 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 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 by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)bsearch.3 5.6 (Berkeley) 6/29/91 +.\" +.Dd June 29, 1991 +.Dt BSEARCH 3 +.Os +.Sh NAME +.Nm bsearch +.Nd binary search of a sorted table +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft void * +.Fn bsearch "const void *key" "const void *base" "size_t nmemb" "size_t size" "int (*compar) (const void *, const void *)" +.Sh DESCRIPTION +The +.Fn bsearch +function searches an array of +.Fa nmemb +objects, the inital member of which is +pointed to by +.Fa base , +for a member that matches the object pointed to by +.Fa key . +The size of each member of the array is specified by +.Fa size . +.Pp +The contents of the array should be in ascending sorted order according +to the comparison function referenced by +.Fa compar . +The +.Fa compar +routine +is expected to have two +two arguments which point to the +.Fa key +object and to an array member, in that order, and should return an integer +less than, equal to, or greater than zero if the +.Fa key +object is found, respectively, to be less than, to match, or be +greater than the array member. +.Sh RETURN VALUES +The +.Fn bsearch +function returns a pointer to a matching member of the array, or a null +pointer if no match is found. +If two members compare as equal, which member is matched is unspecified. +.Sh SEE ALSO +.Xr db 3 , +.Xr lsearch 3 , +.Xr qsort 3 , +.\" .Xr tsearch 3 +.Sh STANDARDS +The +.Fn bsearch +function conforms to +.St -ansiC . diff --git a/lib/libc/stdlib/bsearch.c b/lib/libc/stdlib/bsearch.c new file mode 100644 index 000000000000..ca7ffe628794 --- /dev/null +++ b/lib/libc/stdlib/bsearch.c @@ -0,0 +1,80 @@ +/* + * Copyright (c) 1990 Regents of the University of California. + * 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 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 by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)bsearch.c 5.4 (Berkeley) 2/23/91"; +#endif /* LIBC_SCCS and not lint */ + +#include <stddef.h> /* size_t */ +#include <stdlib.h> + +/* + * Perform a binary search. + * + * The code below is a bit sneaky. After a comparison fails, we + * divide the work in half by moving either left or right. If lim + * is odd, moving left simply involves halving lim: e.g., when lim + * is 5 we look at item 2, so we change lim to 2 so that we will + * look at items 0 & 1. If lim is even, the same applies. If lim + * is odd, moving right again involes halving lim, this time moving + * the base up one item past p: e.g., when lim is 5 we change base + * to item 3 and make lim 2 so that we will look at items 3 and 4. + * If lim is even, however, we have to shrink it by one before + * halving: e.g., when lim is 4, we still looked at item 2, so we + * have to make lim 3, then halve, obtaining 1, so that we will only + * look at item 3. + */ +void * +bsearch(key, base0, nmemb, size, compar) + register const void *key; + const void *base0; + size_t nmemb; + register size_t size; + register int (*compar) __P((const void *, const void *)); +{ + register const char *base = base0; + register int lim, cmp; + register const void *p; + + for (lim = nmemb; lim != 0; lim >>= 1) { + p = base + (lim >> 1) * size; + cmp = (*compar)(key, p); + if (cmp == 0) + return ((void *)p); + if (cmp > 0) { /* key > p: move right */ + base = (char *)p + size; + lim--; + } /* else move left */ + } + return (NULL); +} diff --git a/lib/libc/stdlib/calloc.3 b/lib/libc/stdlib/calloc.3 new file mode 100644 index 000000000000..0ac4a9a9db25 --- /dev/null +++ b/lib/libc/stdlib/calloc.3 @@ -0,0 +1,70 @@ +.\" Copyright (c) 1991 The Regents of the University of California. +.\" All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" the American National Standards Committee X3, on Information +.\" Processing Systems. +.\" +.\" 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 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 by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)calloc.3 5.2 (Berkeley) 6/29/91 +.\" +.Dd June 29, 1991 +.Dt CALLOC 3 +.Os +.Sh NAME +.Nm calloc +.Nd allocate clean memory (zero initialized space) +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft void * +.Fn calloc "size_t nmemb" "size_t size" +.Sh DESCRIPTION +The +.Fn calloc +function allocates space for an array of +.Fa nmemb +objects, each of whose size is +.Fa size . +The space is initialized to all bits zero. +.Sh RETURN VALUES +The +.Fn calloc +function returns +a pointer to the +the allocated space if successful; otherwise a null pointer is returned. +.Sh SEE ALSO +.Xr malloc 3 , +.Xr realloc 3 , +.Xr free 3 , +.Sh STANDARDS +The +.Fn calloc +function conforms to +.St -ansiC . diff --git a/lib/libc/stdlib/calloc.c b/lib/libc/stdlib/calloc.c new file mode 100644 index 000000000000..fbfa1de5ba5c --- /dev/null +++ b/lib/libc/stdlib/calloc.c @@ -0,0 +1,59 @@ +/*- + * Copyright (c) 1990 The Regents of the University of California. + * 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 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 by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)calloc.c 5.6 (Berkeley) 2/23/91"; +#endif /* LIBC_SCCS and not lint */ + +#include <stdlib.h> +#include <string.h> + +void * +calloc(num, size) + size_t num; + register size_t size; +{ + register void *p; + + size *= num; + if (p = malloc(size)) + bzero(p, size); + return(p); +} + +void +cfree(p) + void *p; +{ + (void)free(p); +} diff --git a/lib/libc/stdlib/div.3 b/lib/libc/stdlib/div.3 new file mode 100644 index 000000000000..4c97ffca885a --- /dev/null +++ b/lib/libc/stdlib/div.3 @@ -0,0 +1,67 @@ +.\" Copyright (c) 1990, 1991 The Regents of the University of California. +.\" All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" Chris Torek. +.\" 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 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 by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)div.3 5.2 (Berkeley) 4/19/91 +.\" +.Dd April 19, 1991 +.Dt DIV 3 +.Os +.Sh NAME +.Nm div +.Nd return quotient and remainder from division +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft div_t +.Fn div "int num" "int denom" +.Sh DESCRIPTION +The +.Fn div +function +computes the value +.Fa num/denom +and returns the quotient and remainder in a structure named +.Fa div_t +that contains two +.Em int +members named +.Fa quot +and +.Fa rem . +.Sh SEE ALSO +.Xr ldiv 3 +.Sh STANDARDS +The +.Fn div +function +conforms to +.St -ansiC . diff --git a/lib/libc/stdlib/div.c b/lib/libc/stdlib/div.c new file mode 100644 index 000000000000..ce21a722c504 --- /dev/null +++ b/lib/libc/stdlib/div.c @@ -0,0 +1,79 @@ +/* + * Copyright (c) 1990 Regents of the University of California. + * All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Chris Torek. + * + * 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 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 by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)div.c 5.2 (Berkeley) 4/16/91"; +#endif /* LIBC_SCCS and not lint */ + +#include <stdlib.h> /* div_t */ + +div_t +div(num, denom) + int num, denom; +{ + div_t r; + + r.quot = num / denom; + r.rem = num % denom; + /* + * The ANSI standard says that |r.quot| <= |n/d|, where + * n/d is to be computed in infinite precision. In other + * words, we should always truncate the quotient towards + * 0, never -infinity. + * + * Machine division and remainer may work either way when + * one or both of n or d is negative. If only one is + * negative and r.quot has been truncated towards -inf, + * r.rem will have the same sign as denom and the opposite + * sign of num; if both are negative and r.quot has been + * truncated towards -inf, r.rem will be positive (will + * have the opposite sign of num). These are considered + * `wrong'. + * + * If both are num and denom are positive, r will always + * be positive. + * + * This all boils down to: + * if num >= 0, but r.rem < 0, we got the wrong answer. + * In that case, to get the right answer, add 1 to r.quot and + * subtract denom from r.rem. + */ + if (num >= 0 && r.rem < 0) { + r.quot++; + r.rem -= denom; + } + return (r); +} diff --git a/lib/libc/stdlib/drand48.c b/lib/libc/stdlib/drand48.c new file mode 100644 index 000000000000..cec04a6a2425 --- /dev/null +++ b/lib/libc/stdlib/drand48.c @@ -0,0 +1,22 @@ +/* + * Copyright (c) 1993 Martin Birgmeier + * All rights reserved. + * + * You may redistribute unmodified or modified versions of this source + * code provided that the above copyright notice and this and the + * following conditions are retained. + * + * This software is provided ``as is'', and comes with no warranties + * of any kind. I shall in no event be liable for anything that happens + * to anyone/anything when using this software. + */ + +#include "rand48.h" + +extern unsigned short _rand48_seed[3]; + +double +drand48(void) +{ + return erand48(_rand48_seed); +} diff --git a/lib/libc/stdlib/erand48.c b/lib/libc/stdlib/erand48.c new file mode 100644 index 000000000000..286904c27839 --- /dev/null +++ b/lib/libc/stdlib/erand48.c @@ -0,0 +1,23 @@ +/* + * Copyright (c) 1993 Martin Birgmeier + * All rights reserved. + * + * You may redistribute unmodified or modified versions of this source + * code provided that the above copyright notice and this and the + * following conditions are retained. + * + * This software is provided ``as is'', and comes with no warranties + * of any kind. I shall in no event be liable for anything that happens + * to anyone/anything when using this software. + */ + +#include "rand48.h" + +double +erand48(unsigned short xseed[3]) +{ + _dorand48(xseed); + return ldexp((double) xseed[0], -48) + + ldexp((double) xseed[1], -32) + + ldexp((double) xseed[2], -16); +} diff --git a/lib/libc/stdlib/exit.3 b/lib/libc/stdlib/exit.3 new file mode 100644 index 000000000000..040a7fc97184 --- /dev/null +++ b/lib/libc/stdlib/exit.3 @@ -0,0 +1,83 @@ +.\" Copyright (c) 1990, 1991 The Regents of the University of California. +.\" All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" the American National Standards Committee X3, on Information +.\" Processing Systems. +.\" +.\" 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 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 by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)exit.3 6.6 (Berkeley) 6/29/91 +.\" +.Dd June 29, 1991 +.Dt EXIT 3 +.Os +.Sh NAME +.Nm exit +.Nd perform normal program termination +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft void +.Fn exit "int status" +.Sh DESCRIPTION +.Fn Exit +terminates a process. +.Pp +Before termination it performs the following functions in the +order listed: +.Bl -enum -offset indent +.It +Call the functions registered with the +.Xr atexit 3 +function, in the reverse order of their registration. +.It +Flush all open output streams. +.It +Close all open streams. +.It +Unlink all files created with the +.Xr tmpfile 3 +function. +.El +.Sh RETURN VALUES +The +.Fn exit +function +never returns. +.Sh SEE ALSO +.Xr _exit 2 , +.Xr atexit 3 , +.Xr intro 3 , +.Xr tmpfile 3 +.Sh STANDARDS +The +.Fn exit +function +conforms to +.St -ansiC . diff --git a/lib/libc/stdlib/exit.c b/lib/libc/stdlib/exit.c new file mode 100644 index 000000000000..0d3c72520f46 --- /dev/null +++ b/lib/libc/stdlib/exit.c @@ -0,0 +1,60 @@ +/*- + * Copyright (c) 1990 The Regents of the University of California. + * 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 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 by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)exit.c 5.4 (Berkeley) 2/23/91"; +#endif /* LIBC_SCCS and not lint */ + +#include <stdlib.h> +#include <unistd.h> +#include "atexit.h" + +void (*__cleanup)(); + +/* + * Exit, flushing stdio buffers if necessary. + */ +void +exit(status) + int status; +{ + register struct atexit *p; + register int n; + + for (p = __atexit; p; p = p->next) + for (n = p->ind; --n >= 0;) + (*p->fns[n])(); + if (__cleanup) + (*__cleanup)(); + _exit(status); +} diff --git a/lib/libc/stdlib/free.3 b/lib/libc/stdlib/free.3 new file mode 100644 index 000000000000..3ee964b8b7e2 --- /dev/null +++ b/lib/libc/stdlib/free.3 @@ -0,0 +1,81 @@ +.\" Copyright (c) 1991 The Regents of the University of California. +.\" All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" the American National Standards Committee X3, on Information +.\" Processing Systems. +.\" +.\" 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 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 by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)free.3 5.2 (Berkeley) 6/29/91 +.\" +.Dd June 29, 1991 +.Dt FREE 3 +.Os +.Sh NAME +.Nm free +.Nd free up memory allocated with malloc, calloc or realloc +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft void +.Fn free "void *ptr" +.Sh DESCRIPTION +The +.Fn free +function causes the space pointed to by +.Fa ptr +to be deallocated, that is, made available +for further allocation. +If +.Fa ptr +is a null pointer, no action occurs. +Otherwise, if the argument does not match a pointer earlier +returned by the +.Xr calloc , +.Xr malloc , +or +.Xr realloc +function, or if the space has been deallocated by a call to +.Fn free +or +.Xr realloc , +general havoc may occur. +.Sh RETURN VALUES +The +.Fn free +function returns no value. +.Sh SEE ALSO +.Xr calloc 3 , +.Xr malloc 3 , +.Xr realloc 3 +.Sh STANDARDS +The +.Fn free +function conforms to +.St -ansiC . diff --git a/lib/libc/stdlib/getenv.3 b/lib/libc/stdlib/getenv.3 new file mode 100644 index 000000000000..c5d56215b2eb --- /dev/null +++ b/lib/libc/stdlib/getenv.3 @@ -0,0 +1,151 @@ +.\" Copyright (c) 1988, 1991 The Regents of the University of California. +.\" All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" the American National Standards Committee X3, on Information +.\" Processing Systems. +.\" +.\" 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 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 by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)getenv.3 6.11 (Berkeley) 6/29/91 +.\" +.Dd June 29, 1991 +.Dt GETENV 3 +.Os +.Sh NAME +.Nm getenv , +.Nm putenv , +.Nm setenv , +.Nm unsetenv +.Nd environment variable functions +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft char * +.Fn getenv "const char *name" +.Ft int +.Fn setenv "const char *name" "const char *value" "int overwrite" +.Ft int +.Fn putenv "const char *string" +.Ft void +.Fn unsetenv "const char *name" +.Sh DESCRIPTION +These functions set, unset and fetch environment variables from the +host +.Em environment list . +For compatibility with differing environment conventions, +the given arguments +.Ar name +and +.Ar value +may be appended and prepended, +respectively, +with an equal sign +.Dq Li \&= . +.Pp +The +.Fn getenv +function obtains the current value of the environment variable, +.Ar name . +If the variable +.Ar name +is not in the current environment , +a null pointer is returned. +.Pp +The +.Fn setenv +function inserts or resets the environment variable +.Ar name +in the current environment list. +If the variable +.Ar name +does not exist in the list, +it is inserted with the given +.Ar value. +If the variable does exist, the argument +.Ar overwrite +is tested; if +.Ar overwrite is +zero, the +variable is not reset, otherwise it is reset +to the given +.Ar value . +.Pp +The +.Fn putenv +function +performs the equivalent of: +.Bd -literal -offset indent +setenv(name, value, 1); +.Ed +.Pp +The +.Fn unsetenv +function +deletes all instances of the variable name pointed to by +.Fa name +from the list. +.Sh RETURN VALUES +The functions +.Fn setenv +and +.Fn putenv +return zero if successful; otherwise the global variable +.Va errno +is set to indicate the error and a +\-1 is returned. +.Sh ERRORS +.Bl -tag -width [ENOMEM] +.It Bq Er ENOMEM +The function +.Fn setenv +or +.Fn putenv +failed because they were unable to allocate memory for the environment. +.El +.Sh SEE ALSO +.Xr csh 1 , +.Xr sh 1 , +.Xr execve 2 , +.Xr environ 7 +.Sh STANDARDS +The +.Fn getenv +function conforms to +.St -ansiC . +.Sh HISTORY +The functions +.Fn setenv +and +.Fn unsetenv +appeared in +.At v7 . +The +.Fn putenv +function appeared in +.Bx 4.3 Reno . diff --git a/lib/libc/stdlib/getenv.c b/lib/libc/stdlib/getenv.c new file mode 100644 index 000000000000..b07212d5bfc3 --- /dev/null +++ b/lib/libc/stdlib/getenv.c @@ -0,0 +1,82 @@ +/* + * Copyright (c) 1987 Regents of the University of California. + * 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 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 by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)getenv.c 5.8 (Berkeley) 2/23/91"; +#endif /* LIBC_SCCS and not lint */ + +#include <stdlib.h> +#include <stddef.h> +#include <string.h> + +/* + * getenv -- + * Returns ptr to value associated with name, if any, else NULL. + */ +char * +getenv(name) + const char *name; +{ + int offset; + char *_findenv(); + + return(_findenv(name, &offset)); +} + +/* + * _findenv -- + * Returns pointer to value associated with name, if any, else NULL. + * Sets offset to be the offset of the name/value combination in the + * environmental array, for use by setenv(3) and unsetenv(3). + * Explicitly removes '=' in argument name. + * + * This routine *should* be a static; don't use it. + */ +char * +_findenv(name, offset) + register char *name; + int *offset; +{ + extern char **environ; + register int len; + register char **P, *C; + + for (C = name, len = 0; *C && *C != '='; ++C, ++len); + for (P = environ; *P; ++P) + if (!strncmp(*P, name, len)) + if (*(C = *P + len) == '=') { + *offset = P - environ; + return(++C); + } + return(NULL); +} diff --git a/lib/libc/stdlib/getopt.3 b/lib/libc/stdlib/getopt.3 new file mode 100644 index 000000000000..c21a0a725faf --- /dev/null +++ b/lib/libc/stdlib/getopt.3 @@ -0,0 +1,210 @@ +.\" Copyright (c) 1988, 1991 Regents of the University of California. +.\" 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 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 by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)getopt.3 6.16 (Berkeley) 4/19/91 +.\" +.Dd April 19, 1991 +.Dt GETOPT 3 +.Os BSD 4.3 +.Sh NAME +.Nm getopt +.Nd get option letter from argv +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Vt extern char *optarg +.Vt extern int optind +.Vt extern int opterr +.Ft int +.Fn getopt "int argc" "char * const *argv" "const char *optstring" +.Sh DESCRIPTION +The +.Fn getopt +function gets +the next +.Em known +option character from +.Fa argv . +An option character is +.Em known +if it has been specified in the string of accepted option characters, +.Fa optstring . +.Pp +The option string +.Fa optstring +may contain the following characters; letters and +letters followed by a colon to indicate an option argument +is to follow. It does not matter to +.Fn getopt +if a following argument has leading white space. +.Pp +On return from +.Fn getopt , +.Va optarg +points to an option argument, if it is anticipated, +and the variable +.Va optind +contains the index to the next +.Fa argv +argument for a subsequent call +to +.Fn getopt . +.Pp +The variable +.Va opterr +and +.Va optind +are both initialized to 1. +In order to use +.Fn getopt +to evaluate multiple sets of arguments, or to evaluate a single set of +arguments multiple times, +.Va optind +must be initialized to the number of argv entries to be skipped in each +evaluation. +.Pp +The +.Fn getopt +function +returns an +.Dv EOF +when the argument list is exhausted, or a non-recognized +option is encountered. +The interpretation of options in the argument list may be cancelled +by the option +.Ql -- +(double dash) which causes +.Fn getopt +to signal the end of argument processing and return an +.Dv EOF . +When all options have been processed (i.e., up to the first non-option +argument), +.Fn getopt +returns +.Dv EOF . +.Sh DIAGNOSTICS +If the +.Fn getopt +function encounters a character not found in the string +.Va optarg +or detects +a missing option argument +it writes error message +.Ql ? +to the +.Em stderr . +Setting +.Va opterr +to a zero will disable these error messages. +.Sh EXAMPLE +.Bd -literal -compact +extern char *optarg; +extern int optind; +int bflag, ch, fd; + +bflag = 0; +while ((ch = getopt(argc, argv, "bf:")) != EOF) + switch(ch) { + case 'b': + bflag = 1; + break; + case 'f': + if ((fd = open(optarg, O_RDONLY, 0)) < 0) { + (void)fprintf(stderr, + "myname: unable to read file %s.\en", optarg); + exit(1) ; + } + break; + case '?': + default: + usage(); +} +argc -= optind; +argv += optind; +.Ed +.Sh HISTORY +The +.Fn getopt +function appeared +.Bx 4.3 . +.Sh BUGS +Option arguments are allowed to begin with +.Dq Li \- ; +this is reasonable but +reduces the amount of error checking possible. +.Pp +A single dash +.Dq Li - +may be specified as an character in +.Fa optstring , +however it should +.Em never +have an argument associated with it. +This allows +.Fn getopt +to be used with programs that expect +.Dq Li - +as an option flag. +This practice is wrong, and should not be used in any current development. +It is provided for backward compatibility +.Em only . +By default, a single dash causes +.Fn getopt +to return +.Dv EOF . +This is, we believe, compatible with System V. +.Pp +It is also possible to handle digits as option letters. +This allows +.Fn getopt +to be used with programs that expect a number +.Pq Dq Li \&-\&3 +as an option. +This practice is wrong, and should not be used in any current development. +It is provided for backward compatibility +.Em only . +The following code fragment works fairly well. +.Bd -literal -offset indent +int length; +char *p; + +while ((c = getopt(argc, argv, "0123456789")) != EOF) + switch (c) { + case '0': case '1': case '2': case '3': case '4': + case '5': case '6': case '7': case '8': case '9': + p = argv[optind - 1]; + if (p[0] == '-' && p[1] == ch && !p[2]) + length = atoi(++p); + else + length = atoi(argv[optind] + 1); + break; + } +} +.Ed diff --git a/lib/libc/stdlib/getopt.c b/lib/libc/stdlib/getopt.c new file mode 100644 index 000000000000..7126cc1da95a --- /dev/null +++ b/lib/libc/stdlib/getopt.c @@ -0,0 +1,120 @@ +/* + * Copyright (c) 1987 Regents of the University of California. + * 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 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 by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)getopt.c 4.13 (Berkeley) 2/23/91"; +#endif /* LIBC_SCCS and not lint */ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +/* + * get option letter from argument vector + */ +int opterr = 1, /* if error message should be printed */ + optind = 1, /* index into parent argv vector */ + optopt; /* character checked for validity */ +char *optarg; /* argument associated with option */ + +#define BADCH (int)'?' +#define EMSG "" + +int +getopt(nargc, nargv, ostr) + int nargc; + char * const *nargv; + const char *ostr; +{ + static char *place = EMSG; /* option letter processing */ + register char *oli; /* option letter list index */ + char *p; + + if (!*place) { /* update scanning pointer */ + if (optind >= nargc || *(place = nargv[optind]) != '-') { + place = EMSG; + return(EOF); + } + if (place[1] && *++place == '-') { /* found "--" */ + ++optind; + place = EMSG; + return(EOF); + } + } /* option letter okay? */ + if ((optopt = (int)*place++) == (int)':' || + !(oli = index(ostr, optopt))) { + /* + * if the user didn't specify '-' as an option, + * assume it means EOF. + */ + if (optopt == (int)'-') + return(EOF); + if (!*place) + ++optind; + if (opterr) { + if (!(p = rindex(*nargv, '/'))) + p = *nargv; + else + ++p; + (void)fprintf(stderr, "%s: illegal option -- %c\n", + p, optopt); + } + return(BADCH); + } + if (*++oli != ':') { /* don't need argument */ + optarg = NULL; + if (!*place) + ++optind; + } + else { /* need an argument */ + if (*place) /* no white space */ + optarg = place; + else if (nargc <= ++optind) { /* no arg */ + place = EMSG; + if (!(p = rindex(*nargv, '/'))) + p = *nargv; + else + ++p; + if (opterr) + (void)fprintf(stderr, + "%s: option requires an argument -- %c\n", + p, optopt); + return(BADCH); + } + else /* white space */ + optarg = nargv[optind]; + place = EMSG; + ++optind; + } + return(optopt); /* dump back option letter */ +} diff --git a/lib/libc/stdlib/heapsort.c b/lib/libc/stdlib/heapsort.c new file mode 100644 index 000000000000..2b7046621566 --- /dev/null +++ b/lib/libc/stdlib/heapsort.c @@ -0,0 +1,125 @@ +/*- + * Copyright (c) 1991 The Regents of the University of California. + * 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 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 by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)heapsort.c 5.1 (Berkeley) 6/4/91"; +#endif /* LIBC_SCCS and not lint */ + +#include <sys/cdefs.h> +#include <sys/types.h> +#include <errno.h> +#include <stdlib.h> + +/* + * Swap two areas of size number of bytes. Although qsort(3) permits random + * blocks of memory to be sorted, sorting pointers is almost certainly the + * common case (and, were it not, could easily be made so). Regardless, it + * isn't worth optimizing; the SWAP's get sped up by the cache, and pointer + * arithmetic gets lost in the time required for comparison function calls. + */ +#define SWAP(a, b) { \ + cnt = size; \ + do { \ + ch = *a; \ + *a++ = *b; \ + *b++ = ch; \ + } while (--cnt); \ +} + +/* + * Build the list into a heap, where a heap is defined such that for + * the records K1 ... KN, Kj/2 >= Kj for 1 <= j/2 <= j <= N. + * + * There two cases. If j == nmemb, select largest of Ki and Kj. If + * j < nmemb, select largest of Ki, Kj and Kj+1. + * + * The initial value depends on if we're building the initial heap or + * reconstructing it after saving a value. + */ +#define HEAP(initval) { \ + for (i = initval; (j = i * 2) <= nmemb; i = j) { \ + p = (char *)bot + j * size; \ + if (j < nmemb && compar(p, p + size) < 0) { \ + p += size; \ + ++j; \ + } \ + t = (char *)bot + i * size; \ + if (compar(p, t) <= 0) \ + break; \ + SWAP(t, p); \ + } \ +} + +/* + * Heapsort -- Knuth, Vol. 3, page 145. Runs in O (N lg N), both average + * and worst. While heapsort is faster than the worst case of quicksort, + * the BSD quicksort does median selection so that the chance of finding + * a data set that will trigger the worst case is nonexistent. Heapsort's + * only advantage over quicksort is that it requires no additional memory. + */ +heapsort(bot, nmemb, size, compar) + register void *bot; + register size_t nmemb, size; + int (*compar) __P((const void *, const void *)); +{ + register char *p, *t, ch; + register int cnt, i, j, l; + + if (nmemb <= 1) + return (0); + if (!size) { + errno = EINVAL; + return (-1); + } + /* + * Items are numbered from 1 to nmemb, so offset from size bytes + * below the starting address. + */ + bot -= size; + + for (l = nmemb / 2 + 1; --l;) + HEAP(l); + + /* + * For each element of the heap, save the largest element into its + * final slot, then recreate the heap. + */ + while (nmemb > 1) { + p = (char *)bot + size; + t = (char *)bot + nmemb * size; + SWAP(p, t); + --nmemb; + HEAP(1); + } + return (0); +} diff --git a/lib/libc/stdlib/jrand48.c b/lib/libc/stdlib/jrand48.c new file mode 100644 index 000000000000..051d5a69f515 --- /dev/null +++ b/lib/libc/stdlib/jrand48.c @@ -0,0 +1,21 @@ +/* + * Copyright (c) 1993 Martin Birgmeier + * All rights reserved. + * + * You may redistribute unmodified or modified versions of this source + * code provided that the above copyright notice and this and the + * following conditions are retained. + * + * This software is provided ``as is'', and comes with no warranties + * of any kind. I shall in no event be liable for anything that happens + * to anyone/anything when using this software. + */ + +#include "rand48.h" + +long +jrand48(unsigned short xseed[3]) +{ + _dorand48(xseed); + return ((long) xseed[2] << 16) + (long) xseed[1]; +} diff --git a/lib/libc/stdlib/labs.3 b/lib/libc/stdlib/labs.3 new file mode 100644 index 000000000000..5e568be846cc --- /dev/null +++ b/lib/libc/stdlib/labs.3 @@ -0,0 +1,66 @@ +.\" Copyright (c) 1990, 1991 The Regents of the University of California. +.\" All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" the American National Standards Committee X3, on Information +.\" Processing Systems. +.\" +.\" 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 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 by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)labs.3 5.3 (Berkeley) 6/29/91 +.\" +.Dd June 29, 1991 +.Dt LABS 3 +.Os +.Sh NAME +.Nm labs +.Nd return the absolute value of a long integer +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft long +.Fn labs "long j" +.Sh DESCRIPTION +The +.Fn labs +function +returns the absolute value of the long integer +.Ar j . +.Sh SEE ALSO +.Xr abs 3 , +.Xr floor 3 , +.Xr cabs 3 , +.Xr math 3 +.Sh STANDARDS +The +.Fn labs +function +conforms to +.St -ansiC . +.Sh BUGS +The absolute value of the most negative integer remains negative. diff --git a/lib/libc/stdlib/labs.c b/lib/libc/stdlib/labs.c new file mode 100644 index 000000000000..a43a5c19549c --- /dev/null +++ b/lib/libc/stdlib/labs.c @@ -0,0 +1,45 @@ +/*- + * Copyright (c) 1990 The Regents of the University of California. + * 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 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 by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)labs.c 5.2 (Berkeley) 5/17/90"; +#endif /* LIBC_SCCS and not lint */ + +#include <stdlib.h> + +long +labs(j) + long j; +{ + return(j < 0 ? -j : j); +} diff --git a/lib/libc/stdlib/lcong48.c b/lib/libc/stdlib/lcong48.c new file mode 100644 index 000000000000..f13826b3d3f3 --- /dev/null +++ b/lib/libc/stdlib/lcong48.c @@ -0,0 +1,30 @@ +/* + * Copyright (c) 1993 Martin Birgmeier + * All rights reserved. + * + * You may redistribute unmodified or modified versions of this source + * code provided that the above copyright notice and this and the + * following conditions are retained. + * + * This software is provided ``as is'', and comes with no warranties + * of any kind. I shall in no event be liable for anything that happens + * to anyone/anything when using this software. + */ + +#include "rand48.h" + +extern unsigned short _rand48_seed[3]; +extern unsigned short _rand48_mult[3]; +extern unsigned short _rand48_add; + +void +lcong48(unsigned short p[7]) +{ + _rand48_seed[0] = p[0]; + _rand48_seed[1] = p[1]; + _rand48_seed[2] = p[2]; + _rand48_mult[0] = p[3]; + _rand48_mult[1] = p[4]; + _rand48_mult[2] = p[5]; + _rand48_add = p[6]; +} diff --git a/lib/libc/stdlib/ldiv.3 b/lib/libc/stdlib/ldiv.3 new file mode 100644 index 000000000000..09c22c1c41c1 --- /dev/null +++ b/lib/libc/stdlib/ldiv.3 @@ -0,0 +1,70 @@ +.\" Copyright (c) 1990, 1991 The Regents of the University of California. +.\" All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" Chris Torek and the American National Standards Committee X3, +.\" on Information Processing Systems. +.\" +.\" 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 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 by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)ldiv.3 5.3 (Berkeley) 6/29/91 +.\" +.Dd June 29, 1991 +.Dt LDIV 3 +.Os +.Sh NAME +.Nm ldiv +.Nd return quotient and remainder from division +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft ldiv_t +.Fn ldiv "int num" "int denom" +.Sh DESCRIPTION +The +.Fn ldiv +function +computes the value +.Ar num/denom +and returns the quotient and remainder in a structure named +.Ar ldiv_t +that contains two +.Em long integer +members named +.Ar quot +and +.Ar rem . +.Sh SEE ALSO +.Xr div 3 , +.Xr math 3 +.Sh STANDARDS +The +.Fn ldiv +function +conforms to +.St -ansiC . diff --git a/lib/libc/stdlib/ldiv.c b/lib/libc/stdlib/ldiv.c new file mode 100644 index 000000000000..0fa1764e30cf --- /dev/null +++ b/lib/libc/stdlib/ldiv.c @@ -0,0 +1,58 @@ +/* + * Copyright (c) 1990 Regents of the University of California. + * All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Chris Torek. + * + * 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 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 by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)ldiv.c 5.2 (Berkeley) 4/16/91"; +#endif /* LIBC_SCCS and not lint */ + +#include <stdlib.h> /* ldiv_t */ + +ldiv_t +ldiv(num, denom) + long num, denom; +{ + ldiv_t r; + + /* see div.c for comments */ + + r.quot = num / denom; + r.rem = num % denom; + if (num >= 0 && r.rem < 0) { + r.quot++; + r.rem -= denom; + } + return (r); +} diff --git a/lib/libc/stdlib/lrand48.c b/lib/libc/stdlib/lrand48.c new file mode 100644 index 000000000000..a3d0111cf4d5 --- /dev/null +++ b/lib/libc/stdlib/lrand48.c @@ -0,0 +1,23 @@ +/* + * Copyright (c) 1993 Martin Birgmeier + * All rights reserved. + * + * You may redistribute unmodified or modified versions of this source + * code provided that the above copyright notice and this and the + * following conditions are retained. + * + * This software is provided ``as is'', and comes with no warranties + * of any kind. I shall in no event be liable for anything that happens + * to anyone/anything when using this software. + */ + +#include "rand48.h" + +extern unsigned short _rand48_seed[3]; + +long +lrand48(void) +{ + _dorand48(_rand48_seed); + return ((long) _rand48_seed[2] << 15) + ((long) _rand48_seed[1] >> 1); +} diff --git a/lib/libc/stdlib/malloc.3 b/lib/libc/stdlib/malloc.3 new file mode 100644 index 000000000000..37641b4ee775 --- /dev/null +++ b/lib/libc/stdlib/malloc.3 @@ -0,0 +1,90 @@ +.\" Copyright (c) 1980, 1991 Regents of the University of California. +.\" All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" the American National Standards Committee X3, on Information +.\" Processing Systems. +.\" +.\" 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 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 by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)malloc.3 6.7 (Berkeley) 6/29/91 +.\" +.Dd June 29, 1991 +.Dt MALLOC 3 +.Os BSD 4 +.Sh NAME +.Nm malloc , +.Nd general memory allocation function +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft void * +.Fn malloc "size_t size" +.Sh DESCRIPTION +The +.Fn malloc +function allocates uninitialized space for an object whose +size is specified by +.Fa size . +The +.Fn malloc +function maintains multiple lists of free blocks according to size, allocating +space from the appropriate list. +.Pp +The allocated space is +suitably aligned (after possible pointer +coercion) for storage of any type of object. If the space is of +.Em pagesize +or larger, the memory returned will be page-aligned. +.Sh RETURN VALUES +The +.Fn malloc +function returns +a pointer to the allocated space if successful; otherwise +a null pointer is returned. +.Sh SEE ALSO +.Xr brk 2 , +.Xr pagesize 2 , +.Xr free 3 , +.Xr calloc 3 , +.Xr alloca 3 , +.Xr realloc 3 , +.Xr memory 3 +.Sh STANDARDS +The +.Fn malloc +function conforms to +.St -ansiC . +.Sh BUGS +The current implementation of +.Xr malloc +does not always fail gracefully when system +memory limits are approached. +It may fail to allocate memory when larger free blocks could be broken +up, or when limits are exceeded because the size is rounded up. +It is optimized for sizes that are powers of two. diff --git a/lib/libc/stdlib/malloc.c b/lib/libc/stdlib/malloc.c new file mode 100644 index 000000000000..df60e3e034c3 --- /dev/null +++ b/lib/libc/stdlib/malloc.c @@ -0,0 +1,420 @@ +/* + * Copyright (c) 1983 Regents of the University of California. + * 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 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 by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)malloc.c 5.11 (Berkeley) 2/23/91"; +#endif /* LIBC_SCCS and not lint */ + +/* + * malloc.c (Caltech) 2/21/82 + * Chris Kingsley, kingsley@cit-20. + * + * This is a very fast storage allocator. It allocates blocks of a small + * number of different sizes, and keeps free lists of each size. Blocks that + * don't exactly fit are passed up to the next larger size. In this + * implementation, the available sizes are 2^n-4 (or 2^n-10) bytes long. + * This is designed for use in a virtual memory environment. + */ + +#include <sys/types.h> +#include <stdlib.h> +#include <string.h> +#include <unistd.h> + +#define NULL 0 + +static void morecore(); +static int findbucket(); + +/* + * The overhead on a block is at least 4 bytes. When free, this space + * contains a pointer to the next free block, and the bottom two bits must + * be zero. When in use, the first byte is set to MAGIC, and the second + * byte is the size index. The remaining bytes are for alignment. + * If range checking is enabled then a second word holds the size of the + * requested block, less 1, rounded up to a multiple of sizeof(RMAGIC). + * The order of elements is critical: ov_magic must overlay the low order + * bits of ov_next, and ov_magic can not be a valid ov_next bit pattern. + */ +union overhead { + union overhead *ov_next; /* when free */ + struct { + u_char ovu_magic; /* magic number */ + u_char ovu_index; /* bucket # */ +#ifdef RCHECK + u_short ovu_rmagic; /* range magic number */ + u_int ovu_size; /* actual block size */ +#endif + } ovu; +#define ov_magic ovu.ovu_magic +#define ov_index ovu.ovu_index +#define ov_rmagic ovu.ovu_rmagic +#define ov_size ovu.ovu_size +}; + +#define MAGIC 0xef /* magic # on accounting info */ +#define RMAGIC 0x5555 /* magic # on range info */ + +#ifdef RCHECK +#define RSLOP sizeof (u_short) +#else +#define RSLOP 0 +#endif + +/* + * nextf[i] is the pointer to the next free block of size 2^(i+3). The + * smallest allocatable block is 8 bytes. The overhead information + * precedes the data area returned to the user. + */ +#define NBUCKETS 30 +static union overhead *nextf[NBUCKETS]; +extern char *sbrk(); + +static int pagesz; /* page size */ +static int pagebucket; /* page size bucket */ + +#ifdef MSTATS +/* + * nmalloc[i] is the difference between the number of mallocs and frees + * for a given block size. + */ +static u_int nmalloc[NBUCKETS]; +#include <stdio.h> +#endif + +#if defined(DEBUG) || defined(RCHECK) +#define ASSERT(p) if (!(p)) botch("p") +#include <stdio.h> +static +botch(s) + char *s; +{ + fprintf(stderr, "\r\nassertion botched: %s\r\n", s); + (void) fflush(stderr); /* just in case user buffered it */ + abort(); +} +#else +#define ASSERT(p) +#endif + +void * +malloc(nbytes) + size_t nbytes; +{ + register union overhead *op; + register int bucket, n; + register unsigned amt; + + /* + * First time malloc is called, setup page size and + * align break pointer so all data will be page aligned. + */ + if (pagesz == 0) { + pagesz = n = getpagesize(); + op = (union overhead *)sbrk(0); + n = n - sizeof (*op) - ((int)op & (n - 1)); + if (n < 0) + n += pagesz; + if (n) { + if (sbrk(n) == (char *)-1) + return (NULL); + } + bucket = 0; + amt = 8; + while (pagesz > amt) { + amt <<= 1; + bucket++; + } + pagebucket = bucket; + } + /* + * Convert amount of memory requested into closest block size + * stored in hash buckets which satisfies request. + * Account for space used per block for accounting. + */ + if (nbytes <= (n = pagesz - sizeof (*op) - RSLOP)) { +#ifndef RCHECK + amt = 8; /* size of first bucket */ + bucket = 0; +#else + amt = 16; /* size of first bucket */ + bucket = 1; +#endif + n = -(sizeof (*op) + RSLOP); + } else { + amt = pagesz; + bucket = pagebucket; + } + while (nbytes > amt + n) { + amt <<= 1; + if (amt == 0) + return (NULL); + bucket++; + } + /* + * If nothing in hash bucket right now, + * request more memory from the system. + */ + if ((op = nextf[bucket]) == NULL) { + morecore(bucket); + if ((op = nextf[bucket]) == NULL) + return (NULL); + } + /* remove from linked list */ + nextf[bucket] = op->ov_next; + op->ov_magic = MAGIC; + op->ov_index = bucket; +#ifdef MSTATS + nmalloc[bucket]++; +#endif +#ifdef RCHECK + /* + * Record allocated size of block and + * bound space with magic numbers. + */ + op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1); + op->ov_rmagic = RMAGIC; + *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC; +#endif + return ((char *)(op + 1)); +} + +/* + * Allocate more memory to the indicated bucket. + */ +static void +morecore(bucket) + int bucket; +{ + register union overhead *op; + register int sz; /* size of desired block */ + int amt; /* amount to allocate */ + int nblks; /* how many blocks we get */ + + /* + * sbrk_size <= 0 only for big, FLUFFY, requests (about + * 2^30 bytes on a VAX, I think) or for a negative arg. + */ + sz = 1 << (bucket + 3); +#ifdef DEBUG + ASSERT(sz > 0); +#else + if (sz <= 0) + return; +#endif + if (sz < pagesz) { + amt = pagesz; + nblks = amt / sz; + } else { + amt = sz + pagesz; + nblks = 1; + } + op = (union overhead *)sbrk(amt); + /* no more room! */ + if ((int)op == -1) + return; + /* + * Add new memory allocated to that on + * free list for this hash bucket. + */ + nextf[bucket] = op; + while (--nblks > 0) { + op->ov_next = (union overhead *)((caddr_t)op + sz); + op = (union overhead *)((caddr_t)op + sz); + } +} + +void +free(cp) + void *cp; +{ + register int size; + register union overhead *op; + + if (cp == NULL) + return; + op = (union overhead *)((caddr_t)cp - sizeof (union overhead)); +#ifdef DEBUG + ASSERT(op->ov_magic == MAGIC); /* make sure it was in use */ +#else + if (op->ov_magic != MAGIC) + return; /* sanity */ +#endif +#ifdef RCHECK + ASSERT(op->ov_rmagic == RMAGIC); + ASSERT(*(u_short *)((caddr_t)(op + 1) + op->ov_size) == RMAGIC); +#endif + size = op->ov_index; + ASSERT(size < NBUCKETS); + op->ov_next = nextf[size]; /* also clobbers ov_magic */ + nextf[size] = op; +#ifdef MSTATS + nmalloc[size]--; +#endif +} + +/* + * When a program attempts "storage compaction" as mentioned in the + * old malloc man page, it realloc's an already freed block. Usually + * this is the last block it freed; occasionally it might be farther + * back. We have to search all the free lists for the block in order + * to determine its bucket: 1st we make one pass thru the lists + * checking only the first block in each; if that fails we search + * ``realloc_srchlen'' blocks in each list for a match (the variable + * is extern so the caller can modify it). If that fails we just copy + * however many bytes was given to realloc() and hope it's not huge. + */ +int realloc_srchlen = 4; /* 4 should be plenty, -1 =>'s whole list */ + +void * +realloc(cp, nbytes) + void *cp; + size_t nbytes; +{ + register u_int onb; + register int i; + union overhead *op; + char *res; + int was_alloced = 0; + + if (cp == NULL) + return (malloc(nbytes)); + op = (union overhead *)((caddr_t)cp - sizeof (union overhead)); + if (op->ov_magic == MAGIC) { + was_alloced++; + i = op->ov_index; + } else { + /* + * Already free, doing "compaction". + * + * Search for the old block of memory on the + * free list. First, check the most common + * case (last element free'd), then (this failing) + * the last ``realloc_srchlen'' items free'd. + * If all lookups fail, then assume the size of + * the memory block being realloc'd is the + * largest possible (so that all "nbytes" of new + * memory are copied into). Note that this could cause + * a memory fault if the old area was tiny, and the moon + * is gibbous. However, that is very unlikely. + */ + if ((i = findbucket(op, 1)) < 0 && + (i = findbucket(op, realloc_srchlen)) < 0) + i = NBUCKETS; + } + onb = 1 << (i + 3); + if (onb < pagesz) + onb -= sizeof (*op) + RSLOP; + else + onb += pagesz - sizeof (*op) - RSLOP; + /* avoid the copy if same size block */ + if (was_alloced) { + if (i) { + i = 1 << (i + 2); + if (i < pagesz) + i -= sizeof (*op) + RSLOP; + else + i += pagesz - sizeof (*op) - RSLOP; + } + if (nbytes <= onb && nbytes > i) { +#ifdef RCHECK + op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1); + *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC; +#endif + return(cp); + } else + free(cp); + } + if ((res = malloc(nbytes)) == NULL) + return (NULL); + if (cp != res) /* common optimization if "compacting" */ + bcopy(cp, res, (nbytes < onb) ? nbytes : onb); + return (res); +} + +/* + * Search ``srchlen'' elements of each free list for a block whose + * header starts at ``freep''. If srchlen is -1 search the whole list. + * Return bucket number, or -1 if not found. + */ +static +findbucket(freep, srchlen) + union overhead *freep; + int srchlen; +{ + register union overhead *p; + register int i, j; + + for (i = 0; i < NBUCKETS; i++) { + j = 0; + for (p = nextf[i]; p && j != srchlen; p = p->ov_next) { + if (p == freep) + return (i); + j++; + } + } + return (-1); +} + +#ifdef MSTATS +/* + * mstats - print out statistics about malloc + * + * Prints two lines of numbers, one showing the length of the free list + * for each size category, the second showing the number of mallocs - + * frees for each size category. + */ +mstats(s) + char *s; +{ + register int i, j; + register union overhead *p; + int totfree = 0, + totused = 0; + + fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s); + for (i = 0; i < NBUCKETS; i++) { + for (j = 0, p = nextf[i]; p; p = p->ov_next, j++) + ; + fprintf(stderr, " %d", j); + totfree += j * (1 << (i + 3)); + } + fprintf(stderr, "\nused:\t"); + for (i = 0; i < NBUCKETS; i++) { + fprintf(stderr, " %d", nmalloc[i]); + totused += nmalloc[i] * (1 << (i + 3)); + } + fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n", + totused, totfree); +} +#endif diff --git a/lib/libc/stdlib/memory.3 b/lib/libc/stdlib/memory.3 new file mode 100644 index 000000000000..27b07a9f9d5a --- /dev/null +++ b/lib/libc/stdlib/memory.3 @@ -0,0 +1,70 @@ +.\" Copyright (c) 1991 Regents of the University of California. +.\" 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 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 by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)memory.3 5.1 (Berkeley) 5/2/91 +.\" +.Dd May 2, 1991 +.Dt MEMORY 3 +.Os BSD 4 +.Sh NAME +.Nm malloc , +.Nm free , +.Nm realloc , +.Nm calloc , +.Nm alloca +.Nd general memory allocation operations +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft void * +.Fn malloc "size_t size" +.Ft void +.Fn free "void *ptr" +.Ft void * +.Fn realloc "void *ptr" "size_t size" +.Ft void * +.Fn calloc "size_t nelem" "size_t elsize" +.Ft void * +.Fn alloca "size_t size" +.Sh DESCRIPTION +These functions allocate and free memory for the calling process. +They are described in the +individual manual pages. +.Sh SEE ALSO +.Xr calloc 3 , +.Xr free 3 , +.Xr malloc 3 , +.Xr realloc 3 , +.Xr alloca 3 , +.Sh STANDARDS +These functions, with the exception of +.Fn alloca +conform to +.St -ansiC . diff --git a/lib/libc/stdlib/mrand48.c b/lib/libc/stdlib/mrand48.c new file mode 100644 index 000000000000..b23db51185f3 --- /dev/null +++ b/lib/libc/stdlib/mrand48.c @@ -0,0 +1,23 @@ +/* + * Copyright (c) 1993 Martin Birgmeier + * All rights reserved. + * + * You may redistribute unmodified or modified versions of this source + * code provided that the above copyright notice and this and the + * following conditions are retained. + * + * This software is provided ``as is'', and comes with no warranties + * of any kind. I shall in no event be liable for anything that happens + * to anyone/anything when using this software. + */ + +#include "rand48.h" + +extern unsigned short _rand48_seed[3]; + +long +mrand48(void) +{ + _dorand48(_rand48_seed); + return ((long) _rand48_seed[2] << 16) + (long) _rand48_seed[1]; +} diff --git a/lib/libc/stdlib/multibyte.c b/lib/libc/stdlib/multibyte.c new file mode 100644 index 000000000000..695127969633 --- /dev/null +++ b/lib/libc/stdlib/multibyte.c @@ -0,0 +1,105 @@ +/* + * Copyright (c) 1991 The Regents of the University of California. + * 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 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 by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)multibyte.c 5.1 (Berkeley) 2/18/91"; +#endif /* LIBC_SCCS and not lint */ + +#include <stdlib.h> + +/* + * Stub multibyte character functions. + * These ignore the current fixed ("C") locale and + * always indicate that no multibyte characters are supported. + */ + +int +mblen(s, n) + const char *s; + size_t n; +{ + if (s && n && *s) + return -1; + return 0; +} + +/*ARGSUSED*/ +int +mbtowc(pwc, s, n) + wchar_t *pwc; + const char *s; + size_t n; +{ + if (s && n && *s) + return -1; + return 0; +} + +/*ARGSUSED*/ +int +#ifdef __STDC__ +wctomb(char *s, wchar_t wchar) +#else +wctomb(s, wchar) + char *s; + wchar_t wchar; +#endif +{ + if (s) + return -1; + return 0; +} + +/*ARGSUSED*/ +size_t +mbstowcs(pwcs, s, n) + wchar_t *pwcs; + const char *s; + size_t n; +{ + if (s && n && *s) + return -1; + return 0; +} + +/*ARGSUSED*/ +size_t +wcstombs(s, pwcs, n) + char *s; + const wchar_t *pwcs; + size_t n; +{ + if (pwcs && n && *pwcs) + return -1; + return 0; +} diff --git a/lib/libc/stdlib/nrand48.c b/lib/libc/stdlib/nrand48.c new file mode 100644 index 000000000000..6c54065e7e0f --- /dev/null +++ b/lib/libc/stdlib/nrand48.c @@ -0,0 +1,21 @@ +/* + * Copyright (c) 1993 Martin Birgmeier + * All rights reserved. + * + * You may redistribute unmodified or modified versions of this source + * code provided that the above copyright notice and this and the + * following conditions are retained. + * + * This software is provided ``as is'', and comes with no warranties + * of any kind. I shall in no event be liable for anything that happens + * to anyone/anything when using this software. + */ + +#include "rand48.h" + +long +nrand48(unsigned short xseed[3]) +{ + _dorand48(xseed); + return ((long) xseed[2] << 15) + ((long) xseed[1] >> 1); +} diff --git a/lib/libc/stdlib/putenv.c b/lib/libc/stdlib/putenv.c new file mode 100644 index 000000000000..2a9728e8c45f --- /dev/null +++ b/lib/libc/stdlib/putenv.c @@ -0,0 +1,58 @@ +/*- + * Copyright (c) 1988 The Regents of the University of California. + * 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 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 by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)putenv.c 5.4 (Berkeley) 2/23/91"; +#endif /* LIBC_SCCS and not lint */ + +#include <stdlib.h> +#include <string.h> + +int +putenv(str) + const char *str; +{ + register char *p, *equal; + int rval; + + if (!(p = strdup(str))) + return(1); + if (!(equal = index(p, '='))) { + (void)free(p); + return(1); + } + *equal = '\0'; + rval = setenv(p, equal + 1, 1); + (void)free(p); + return(rval); +} diff --git a/lib/libc/stdlib/qsort.3 b/lib/libc/stdlib/qsort.3 new file mode 100644 index 000000000000..03f1b8d4ef44 --- /dev/null +++ b/lib/libc/stdlib/qsort.3 @@ -0,0 +1,168 @@ +.\" Copyright (c) 1990, 1991 The Regents of the University of California. +.\" All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" the American National Standards Committee X3, on Information +.\" Processing Systems. +.\" +.\" 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 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 by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)qsort.3 6.7 (Berkeley) 6/29/91 +.\" +.Dd June 29, 1991 +.Dt QSORT 3 +.Os +.Sh NAME +.Nm qsort, heapsort +.Nd sort functions +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft void +.Fn qsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)" +.Ft int +.Fn heapsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)" +.Sh DESCRIPTION +The +.Fn qsort +function is a modified partition-exchange sort, or quicksort. +The +.Fn heapsort +function is a modified selection sort. +.Pp +The +.Fn qsort +and +.Fn heapsort +functions sort an array of +.Fa nmemb +objects, the initial member of which is pointed to by +.Fa base . +The size of each object is specified by +.Fa size . +.Pp +The contents of the array are sorted in ascending order according to +a comparison function pointed to by +.Fa compar , +which is called with two arguments that point to the objects being +compared. +.Pp +The comparison function must return an integer less than, equal to, or +greater than zero if the first argument is considered to be respectively +less than, equal to, or greater than the second. +.Pp +The functions +.Fn qsort +and +.Fn heapsort +are +.Em not +stable, that is, if two members compare as equal, their order in +the sorted array is undefined. +.Pp +The +.Fn qsort +function is an implementation of C.A.R. Hoare's ``quicksort'' algorithm, +a variant of partition-exchange sorting; in particular, see D.E. Knuth's +Algorithm Q. +.Fn Qsort +takes O N lg N average time. +This implementation uses median selection to avoid the traditional +O N**2 worst-case behavior. +.Pp +The +.Fn heapsort +function is an implementation of J.W.J. William's ``heapsort'' algorithm, +a variant of selection sorting; in particular, see D.E. Knuth's Algorithm H. +.Fn Heapsort +takes O N lg N worst-case time. +Its +.Em only +advantage over +.Fn qsort +is that it uses no additional memory. +.Sh RETURN VALUES +The +.Fn qsort +function +returns no value. +.Pp +Upon successful completion, +.Fn heapsort +returns 0. +Otherwise, it returns \-1 and the global variable +.Va errno +is set to indicate the error. +.Sh ERRORS +The +.Fn heapsort +function succeeds unless: +.Bl -tag -width Er +.It Bq Er EINVAL +The +.Fa size +argument is zero. +.Sh COMPATIBILITY +Previous versions of +.Fn qsort +did not permit the comparison routine to itself call +.Fn qsort 3 . +This is no longer true. +.Sh SEE ALSO +.Xr sort 1 , +.Xr radixsort 3 +.Rs +.%A Hoare, C.A.R. +.%D 1962 +.%T "Quicksort" +.%J "The Computer Journal" +.%V 5:1 +.%P pp. 10-15 +.Re +.Rs +.%A Williams, J.W.J +.%D 1964 +.%T "Heapsort" +.%J "Communications of the ACM" +.%V 7:1 +.%P pp. 347-348 +.Re +.Rs +.%A Knuth, D.E. +.%D 1968 +.%B "The Art of Computer Programming" +.%V Vol. 3 +.%T "Sorting and Searching" +.%P pp. 114-123, 145-149 +.Re +.Sh STANDARDS +The +.Fn qsort +function +conforms to +.St -ansiC . diff --git a/lib/libc/stdlib/qsort.c b/lib/libc/stdlib/qsort.c new file mode 100644 index 000000000000..44a86d03f446 --- /dev/null +++ b/lib/libc/stdlib/qsort.c @@ -0,0 +1,275 @@ +/*- + * Copyright (c) 1980, 1983, 1990 The Regents of the University of California. + * 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 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 by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)qsort.c 5.9 (Berkeley) 2/23/91"; +#endif /* LIBC_SCCS and not lint */ + +#include <sys/types.h> +#include <stdlib.h> + +/* + * MTHRESH is the smallest partition for which we compare for a median + * value instead of using the middle value. + */ +#define MTHRESH 6 + +/* + * THRESH is the minimum number of entries in a partition for continued + * partitioning. + */ +#define THRESH 4 + +void +qsort(bot, nmemb, size, compar) + void *bot; + size_t nmemb, size; + int (*compar) __P((const void *, const void *)); +{ + static void insertion_sort(), quick_sort(); + + if (nmemb <= 1) + return; + + if (nmemb >= THRESH) + quick_sort(bot, nmemb, size, compar); + else + insertion_sort(bot, nmemb, size, compar); +} + +/* + * Swap two areas of size number of bytes. Although qsort(3) permits random + * blocks of memory to be sorted, sorting pointers is almost certainly the + * common case (and, were it not, could easily be made so). Regardless, it + * isn't worth optimizing; the SWAP's get sped up by the cache, and pointer + * arithmetic gets lost in the time required for comparison function calls. + */ +#define SWAP(a, b) { \ + cnt = size; \ + do { \ + ch = *a; \ + *a++ = *b; \ + *b++ = ch; \ + } while (--cnt); \ +} + +/* + * Knuth, Vol. 3, page 116, Algorithm Q, step b, argues that a single pass + * of straight insertion sort after partitioning is complete is better than + * sorting each small partition as it is created. This isn't correct in this + * implementation because comparisons require at least one (and often two) + * function calls and are likely to be the dominating expense of the sort. + * Doing a final insertion sort does more comparisons than are necessary + * because it compares the "edges" and medians of the partitions which are + * known to be already sorted. + * + * This is also the reasoning behind selecting a small THRESH value (see + * Knuth, page 122, equation 26), since the quicksort algorithm does less + * comparisons than the insertion sort. + */ +#define SORT(bot, n) { \ + if (n > 1) \ + if (n == 2) { \ + t1 = bot + size; \ + if (compar(t1, bot) < 0) \ + SWAP(t1, bot); \ + } else \ + insertion_sort(bot, n, size, compar); \ +} + +static void +quick_sort(bot, nmemb, size, compar) + register char *bot; + register int size; + int nmemb, (*compar)(); +{ + register int cnt; + register u_char ch; + register char *top, *mid, *t1, *t2; + register int n1, n2; + char *bsv; + static void insertion_sort(); + + /* bot and nmemb must already be set. */ +partition: + + /* find mid and top elements */ + mid = bot + size * (nmemb >> 1); + top = bot + (nmemb - 1) * size; + + /* + * Find the median of the first, last and middle element (see Knuth, + * Vol. 3, page 123, Eq. 28). This test order gets the equalities + * right. + */ + if (nmemb >= MTHRESH) { + n1 = compar(bot, mid); + n2 = compar(mid, top); + if (n1 < 0 && n2 > 0) + t1 = compar(bot, top) < 0 ? top : bot; + else if (n1 > 0 && n2 < 0) + t1 = compar(bot, top) > 0 ? top : bot; + else + t1 = mid; + + /* if mid element not selected, swap selection there */ + if (t1 != mid) { + SWAP(t1, mid); + mid -= size; + } + } + + /* Standard quicksort, Knuth, Vol. 3, page 116, Algorithm Q. */ +#define didswap n1 +#define newbot t1 +#define replace t2 + didswap = 0; + for (bsv = bot;;) { + for (; bot < mid && compar(bot, mid) <= 0; bot += size); + while (top > mid) { + if (compar(mid, top) <= 0) { + top -= size; + continue; + } + newbot = bot + size; /* value of bot after swap */ + if (bot == mid) /* top <-> mid, mid == top */ + replace = mid = top; + else { /* bot <-> top */ + replace = top; + top -= size; + } + goto swap; + } + if (bot == mid) + break; + + /* bot <-> mid, mid == bot */ + replace = mid; + newbot = mid = bot; /* value of bot after swap */ + top -= size; + +swap: SWAP(bot, replace); + bot = newbot; + didswap = 1; + } + + /* + * Quicksort behaves badly in the presence of data which is already + * sorted (see Knuth, Vol. 3, page 119) going from O N lg N to O N^2. + * To avoid this worst case behavior, if a re-partitioning occurs + * without swapping any elements, it is not further partitioned and + * is insert sorted. This wins big with almost sorted data sets and + * only loses if the data set is very strangely partitioned. A fix + * for those data sets would be to return prematurely if the insertion + * sort routine is forced to make an excessive number of swaps, and + * continue the partitioning. + */ + if (!didswap) { + insertion_sort(bsv, nmemb, size, compar); + return; + } + + /* + * Re-partition or sort as necessary. Note that the mid element + * itself is correctly positioned and can be ignored. + */ +#define nlower n1 +#define nupper n2 + bot = bsv; + nlower = (mid - bot) / size; /* size of lower partition */ + mid += size; + nupper = nmemb - nlower - 1; /* size of upper partition */ + + /* + * If must call recursively, do it on the smaller partition; this + * bounds the stack to lg N entries. + */ + if (nlower > nupper) { + if (nupper >= THRESH) + quick_sort(mid, nupper, size, compar); + else { + SORT(mid, nupper); + if (nlower < THRESH) { + SORT(bot, nlower); + return; + } + } + nmemb = nlower; + } else { + if (nlower >= THRESH) + quick_sort(bot, nlower, size, compar); + else { + SORT(bot, nlower); + if (nupper < THRESH) { + SORT(mid, nupper); + return; + } + } + bot = mid; + nmemb = nupper; + } + goto partition; + /* NOTREACHED */ +} + +static void +insertion_sort(bot, nmemb, size, compar) + char *bot; + register int size; + int nmemb, (*compar)(); +{ + register int cnt; + register u_char ch; + register char *s1, *s2, *t1, *t2, *top; + + /* + * A simple insertion sort (see Knuth, Vol. 3, page 81, Algorithm + * S). Insertion sort has the same worst case as most simple sorts + * (O N^2). It gets used here because it is (O N) in the case of + * sorted data. + */ + top = bot + nmemb * size; + for (t1 = bot + size; t1 < top;) { + for (t2 = t1; (t2 -= size) >= bot && compar(t1, t2) < 0;); + if (t1 != (t2 += size)) { + /* Bubble bytes up through each element. */ + for (cnt = size; cnt--; ++t1) { + ch = *t1; + for (s1 = s2 = t1; (s2 -= size) >= t2; s1 = s2) + *s1 = *s2; + *s1 = ch; + } + } else + t1 += size; + } +} diff --git a/lib/libc/stdlib/radixsort.3 b/lib/libc/stdlib/radixsort.3 new file mode 100644 index 000000000000..0575ec798c63 --- /dev/null +++ b/lib/libc/stdlib/radixsort.3 @@ -0,0 +1,143 @@ +.\" Copyright (c) 1990, 1991 The Regents of the University of California. +.\" 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 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 by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)radixsort.3 5.5 (Berkeley) 4/19/91 +.\" +.Dd April 19, 1991 +.Dt RADIXSORT 3 +.Os +.Sh NAME +.Nm radixsort +.Nd radix sort +.Sh SYNOPSIS +.Fd #include <limits.h> +.Fd #include <stdlib.h> +.Ft int +.Fn radixsort "u_char **base" "int nmemb" "u_char *table" "u_char endbyte" +.Sh DESCRIPTION +The +.Fn radixsort +function +is a modified radix sort. +.Pp +The +.Fn radixsort +function sorts an array of +.Fa nmemb +pointers to byte strings, the initial member of which is referenced +by +.Fa base . +The byte strings may contain any values; the end of each string +is denoted by the user-specified value +.Fa endbyte . +The contents of the array are sorted in ascending order according +to the +.Tn ASCII +order of the byte strings they reference. +.Pp +Applications may specify a sort order by providing the +.Fa table +argument. +If +.Pf non- Dv NULL , +.Fa table +must reference an array of +.Dv UCHAR_MAX ++ 1 bytes which contains the sort +weight of each possible byte value. +The end-of-string byte must have a sort weight of 0. +More than one byte may have the same sort weight. +The +.Fa table +argument +is useful for applications which wish to sort different characters +equally; for example, providing a table with the same weights +for A-Z as for a-z will result in a case-insensitive sort. +.Pp +The +.Fn radixsort +function +is stable, that is, if two elements compare as equal, their order in +the sorted array is unchanged. +.Pp +The +.Fn radixsort +function +is a variant of most-significant-byte radix sorting; in particular, see +D.E. Knuth's Algorithm R and section 5.2.5, exercise 10. +The +.Fn radixsort +function +takes linear time relative to the number of bytes in the strings. +.Sh RETURN VALUES +Upon successful completion 0 is returned. +Otherwise, \-1 is returned and the global variable +.Va errno +is set to indicate the error. +.Sh ERRORS +The +.Fn radixsort +function +may fail and set +.Va errno +for any of the errors specified for the library routine +.Xr malloc 3 . +.Sh SEE ALSO +.Xr sort 1 , +.Xr qsort 3 +.Pp +.Rs +.%A Knuth, D.E. +.%D 1968 +.%B "The Art of Computer Programming" +.%T "Sorting and Searching" +.%V Vol. 3 +.%P pp. 170-178 +.Re +.Rs +.%A Paige, R. +.%D 1987 +.%T "Three Partition Refinement Algorithms" +.%J "SIAM J. Comput." +.%V Vol. 16 +.%N No. 6 +.Re +.Sh HISTORY +The +.Fn radixsort +function is +.Ud . +.Sh BUGS +The +.Fa nmemb +argument +must be less than the maximum integer, +.Dv INT_MAX . diff --git a/lib/libc/stdlib/radixsort.c b/lib/libc/stdlib/radixsort.c new file mode 100644 index 000000000000..5ba481818650 --- /dev/null +++ b/lib/libc/stdlib/radixsort.c @@ -0,0 +1,289 @@ +/*- + * Copyright (c) 1990 The Regents of the University of California. + * 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 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 by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)radixsort.c 5.7 (Berkeley) 2/23/91"; +#endif /* LIBC_SCCS and not lint */ + +#include <sys/types.h> +#include <limits.h> +#include <stdlib.h> +#include <stddef.h> +#include <string.h> + +/* + * __rspartition is the cutoff point for a further partitioning instead + * of a shellsort. If it changes check __rsshell_increments. Both of + * these are exported, as the best values are data dependent. + */ +#define NPARTITION 40 +int __rspartition = NPARTITION; +int __rsshell_increments[] = { 4, 1, 0, 0, 0, 0, 0, 0 }; + +/* + * Stackp points to context structures, where each structure schedules a + * partitioning. Radixsort exits when the stack is empty. + * + * If the buckets are placed on the stack randomly, the worst case is when + * all the buckets but one contain (npartitions + 1) elements and the bucket + * pushed on the stack last contains the rest of the elements. In this case, + * stack growth is bounded by: + * + * limit = (nelements / (npartitions + 1)) - 1; + * + * This is a very large number, 52,377,648 for the maximum 32-bit signed int. + * + * By forcing the largest bucket to be pushed on the stack first, the worst + * case is when all but two buckets each contain (npartitions + 1) elements, + * with the remaining elements split equally between the first and last + * buckets pushed on the stack. In this case, stack growth is bounded when: + * + * for (partition_cnt = 0; nelements > npartitions; ++partition_cnt) + * nelements = + * (nelements - (npartitions + 1) * (nbuckets - 2)) / 2; + * The bound is: + * + * limit = partition_cnt * (nbuckets - 1); + * + * This is a much smaller number, 4590 for the maximum 32-bit signed int. + */ +#define NBUCKETS (UCHAR_MAX + 1) + +typedef struct _stack { + const u_char **bot; + int indx, nmemb; +} CONTEXT; + +#define STACKPUSH { \ + stackp->bot = p; \ + stackp->nmemb = nmemb; \ + stackp->indx = indx; \ + ++stackp; \ +} +#define STACKPOP { \ + if (stackp == stack) \ + break; \ + --stackp; \ + bot = stackp->bot; \ + nmemb = stackp->nmemb; \ + indx = stackp->indx; \ +} + +/* + * A variant of MSD radix sorting; see Knuth Vol. 3, page 177, and 5.2.5, + * Ex. 10 and 12. Also, "Three Partition Refinement Algorithms, Paige + * and Tarjan, SIAM J. Comput. Vol. 16, No. 6, December 1987. + * + * This uses a simple sort as soon as a bucket crosses a cutoff point, + * rather than sorting the entire list after partitioning is finished. + * This should be an advantage. + * + * This is pure MSD instead of LSD of some number of MSD, switching to + * the simple sort as soon as possible. Takes linear time relative to + * the number of bytes in the strings. + */ +int +#if __STDC__ +radixsort(const u_char **l1, int nmemb, const u_char *tab, u_char endbyte) +#else +radixsort(l1, nmemb, tab, endbyte) + const u_char **l1; + register int nmemb; + const u_char *tab; + u_char endbyte; +#endif +{ + register int i, indx, t1, t2; + register const u_char **l2; + register const u_char **p; + register const u_char **bot; + register const u_char *tr; + CONTEXT *stack, *stackp; + int c[NBUCKETS + 1], max; + u_char ltab[NBUCKETS]; + static void shellsort(); + + if (nmemb <= 1) + return(0); + + /* + * T1 is the constant part of the equation, the number of elements + * represented on the stack between the top and bottom entries. + * It doesn't get rounded as the divide by 2 rounds down (correct + * for a value being subtracted). T2, the nelem value, has to be + * rounded up before each divide because we want an upper bound; + * this could overflow if nmemb is the maximum int. + */ + t1 = ((__rspartition + 1) * (NBUCKETS - 2)) >> 1; + for (i = 0, t2 = nmemb; t2 > __rspartition; i += NBUCKETS - 1) + t2 = ((t2 + 1) >> 1) - t1; + if (i) { + if (!(stack = stackp = (CONTEXT *)malloc(i * sizeof(CONTEXT)))) + return(-1); + } else + stack = stackp = NULL; + + /* + * There are two arrays, one provided by the user (l1), and the + * temporary one (l2). The data is sorted to the temporary stack, + * and then copied back. The speedup of using index to determine + * which stack the data is on and simply swapping stacks back and + * forth, thus avoiding the copy every iteration, turns out to not + * be any faster than the current implementation. + */ + if (!(l2 = (const u_char **)malloc(sizeof(u_char *) * nmemb))) + return(-1); + + /* + * Tr references a table of sort weights; multiple entries may + * map to the same weight; EOS char must have the lowest weight. + */ + if (tab) + tr = tab; + else { + for (t1 = 0, t2 = endbyte; t1 < t2; ++t1) + ltab[t1] = t1 + 1; + ltab[t2] = 0; + for (t1 = endbyte + 1; t1 < NBUCKETS; ++t1) + ltab[t1] = t1; + tr = ltab; + } + + /* First sort is entire stack */ + bot = l1; + indx = 0; + + for (;;) { + /* Clear bucket count array */ + bzero((char *)c, sizeof(c)); + + /* + * Compute number of items that sort to the same bucket + * for this index. + */ + for (p = bot, i = nmemb; --i >= 0;) + ++c[tr[(*p++)[indx]]]; + + /* + * Sum the number of characters into c, dividing the temp + * stack into the right number of buckets for this bucket, + * this index. C contains the cumulative total of keys + * before and included in this bucket, and will later be + * used as an index to the bucket. c[NBUCKETS] contains + * the total number of elements, for determining how many + * elements the last bucket contains. At the same time + * find the largest bucket so it gets pushed first. + */ + for (i = max = t1 = 0, t2 = __rspartition; i <= NBUCKETS; ++i) { + if (c[i] > t2) { + t2 = c[i]; + max = i; + } + t1 = c[i] += t1; + } + + /* + * Partition the elements into buckets; c decrements through + * the bucket, and ends up pointing to the first element of + * the bucket. + */ + for (i = nmemb; --i >= 0;) { + --p; + l2[--c[tr[(*p)[indx]]]] = *p; + } + + /* Copy the partitioned elements back to user stack */ + bcopy(l2, bot, nmemb * sizeof(u_char *)); + + ++indx; + /* + * Sort buckets as necessary; don't sort c[0], it's the + * EOS character bucket, and nothing can follow EOS. + */ + for (i = max; i; --i) { + if ((nmemb = c[i + 1] - (t1 = c[i])) < 2) + continue; + p = bot + t1; + if (nmemb > __rspartition) + STACKPUSH + else + shellsort(p, indx, nmemb, tr); + } + for (i = max + 1; i < NBUCKETS; ++i) { + if ((nmemb = c[i + 1] - (t1 = c[i])) < 2) + continue; + p = bot + t1; + if (nmemb > __rspartition) + STACKPUSH + else + shellsort(p, indx, nmemb, tr); + } + /* Break out when stack is empty */ + STACKPOP + } + + free((char *)l2); + free((char *)stack); + return(0); +} + +/* + * Shellsort (diminishing increment sort) from Data Structures and + * Algorithms, Aho, Hopcraft and Ullman, 1983 Edition, page 290; + * see also Knuth Vol. 3, page 84. The increments are selected from + * formula (8), page 95. Roughly O(N^3/2). + */ +static void +shellsort(p, indx, nmemb, tr) + register u_char **p, *tr; + register int indx, nmemb; +{ + register u_char ch, *s1, *s2; + register int incr, *incrp, t1, t2; + + for (incrp = __rsshell_increments; incr = *incrp++;) + for (t1 = incr; t1 < nmemb; ++t1) + for (t2 = t1 - incr; t2 >= 0;) { + s1 = p[t2] + indx; + s2 = p[t2 + incr] + indx; + while ((ch = tr[*s1++]) == tr[*s2] && ch) + ++s2; + if (ch > tr[*s2]) { + s1 = p[t2]; + p[t2] = p[t2 + incr]; + p[t2 + incr] = s1; + t2 -= incr; + } else + break; + } +} diff --git a/lib/libc/stdlib/rand.3 b/lib/libc/stdlib/rand.3 new file mode 100644 index 000000000000..883ccbe7288e --- /dev/null +++ b/lib/libc/stdlib/rand.3 @@ -0,0 +1,84 @@ +.\" Copyright (c) 1990, 1991 The Regents of the University of California. +.\" All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" the American National Standards Committee X3, on Information +.\" Processing Systems. +.\" +.\" 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 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 by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)rand.3 6.7 (Berkeley) 6/29/91 +.\" +.Dd June 29, 1991 +.Dt RAND 3 +.Os +.Sh NAME +.Nm rand , +.Nm srand +.Nd bad random number generator +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft void +.Fn srand "unsigned seed" +.Ft int +.Fn rand void +.Sh DESCRIPTION +.Bf -symbolic +These interfaces are obsoleted by random(3). +.Ef +.Pp +The +.Fn rand +function computes a sequence of pseudo-random integers in the range +of 0 to +.Dv RAND_MAX +(as defined by the header file +.Aq Pa stdlib.h ) . +.Pp +The +.Fn srand +function sets its argument as the seed for a new sequence of +pseudo-random numbers to be returned by +.Fn rand . +These sequences are repeatable by calling +.Fn srand +with the same seed value. +.Pp +If no seed value is provided, the functions are automatically +seeded with a value of 1. +.Sh SEE ALSO +.Xr random 3 +.Sh STANDARDS +The +.Fn rand +and +.Fn srand +functions +conform to +.St -ansiC . diff --git a/lib/libc/stdlib/rand.c b/lib/libc/stdlib/rand.c new file mode 100644 index 000000000000..f96af3005605 --- /dev/null +++ b/lib/libc/stdlib/rand.c @@ -0,0 +1,54 @@ +/*- + * Copyright (c) 1990 The Regents of the University of California. + * 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 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 by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)rand.c 5.6 (Berkeley) 6/24/91"; +#endif /* LIBC_SCCS and not lint */ + +#include <sys/types.h> +#include <stdlib.h> + +static u_long next = 1; + +int +rand() +{ + return ((next = next * 1103515245 + 12345) % (RAND_MAX + 1)); +} + +void +srand(seed) +u_int seed; +{ + next = seed; +} diff --git a/lib/libc/stdlib/rand48.3 b/lib/libc/stdlib/rand48.3 new file mode 100644 index 000000000000..fead60db46e2 --- /dev/null +++ b/lib/libc/stdlib/rand48.3 @@ -0,0 +1,163 @@ +\" Copyright (c) 1993 Martin Birgmeier +.\" All rights reserved. +.\" +.\" You may redistribute unmodified or modified versions of this source +.\" code provided that the above copyright notice and this and the +.\" following conditions are retained. +.\" +.\" This software is provided ``as is'', and comes with no warranties +.\" of any kind. I shall in no event be liable for anything that happens +.\" to anyone/anything when using this software. +.\" +.\" @(#)rand48.3 V1.0 MB 8 Oct 1993 +.\" +.Dd October 8, 1993 +.Dt RAND48 3 +.Os FreeBSD +.Sh NAME +.Nm drand48 , +.Nm erand48 , +.Nm lrand48 , +.Nm nrand48 , +.Nm mrand48 , +.Nm jrand48 , +.Nm srand48 , +.Nm seed48 , +.Nm lcong48 +.Nd pseudo random number generators and initialization routines +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft double +.Fn drand48 void +.Ft double +.Fn erand48 "unsigned short xseed[3]" +.Ft long +.Fn lrand48 void +.Ft long +.Fn nrand48 "unsigned short xseed[3]" +.Ft long +.Fn mrand48 void +.Ft long +.Fn jrand48 "unsigned short xseed[3]" +.Ft void +.Fn srand48 "long seed" +.Ft "unsigned short *" +.Fn seed48 "unsigned short xseed[3]" +.Ft void +.Fn lcong48 "unsigned short p[7]" +.Sh DESCRIPTION +The +.Fn rand48 +family of functions generates pseudo-random numbers using a linear +congruential algorithm working on integers 48 bits in size. The +particular formula employed is +r(n+1) = (a * r(n) + c) mod m +where the default values are +for the multiplicand a = 0xfdeece66d = 25214903917 and +the addend c = 0xb = 11. The modul is always fixed at m = 2 ** 48. +r(n) is called the seed of the random number generator. +.Pp +For all the six generator routines described next, the first +computational step is to perform a single iteration of the algorithm. +.Pp +.Fn drand48 +and +.Fn erand48 +return values of type double. The full 48 bits of r(n+1) are +loaded into the mantissa of the returned value, with the exponent set +such that the values produced lie in the interval [0.0, 1.0). +.Pp +.Fn lrand48 +and +.Fn nrand48 +return values of type long in the range +[-2**31, 2**31-1]. The high-order (32) bits of +r(n+1) are loaded into the returned value. +.Pp +.Fn mrand48 +and +.Fn jrand48 +return values of type long in the range +[0, 2**31-1]. The high-order (31) bits of +r(n+1) are loaded into the lower bits of the returned value, with +the topmost (sign) bit set to zero. +.Pp +.Fn drand48 , +.Fn lrand48 , +and +.Fn mrand48 +use an internal buffer to store r(n). For these functions +the initial value of r(0) = 0x1234abcd330e = 20017429951246. +.Pp +On the other hand, +.Fn erand48 , +.Fn nrand48 , +and +.Fn jrand48 +use a user-supplied buffer to store the seed r(n), +which consists of an array of 3 shorts, where the zeroth member +holds the least significant bits. +.Pp +All functions share the same multiplicand and addend. +.Pp +.Fn srand48 +is used to initialize the internal buffer r(n) of +.Fn drand48 , +.Fn lrand48 , +and +.Fn mrand48 +such that the 32 bits of the seed value are copied into the upper 32 bits +of r(n), with the lower 16 bits of r(n) arbitrarily being set to 0x330e. +Additionally, the constant multiplicand and addend of the algorithm are +reset to the default values given above. +.Pp +.Fn seed48 +also initializes the internal buffer r(n) of +.Fn drand48 , +.Fn lrand48 , +and +.Fn mrand48 , +but here all 48 bits of the seed can be specified in an array of 3 shorts, +where the zeroth member specifies the lowest bits. Again, +the constant multiplicand and addend of the algorithm are +reset to the default values given above. +.Fn seed48 +returns a pointer to an array of 3 shorts which contains the old seed. +This array is statically allocated, thus its contents are lost after +each new call to +.Fn seed48 . +.Pp +Finally, +.Fn lcong48 +allows full control over the multiplicand and addend used in +.Fn drand48 , +.Fn erand48 , +.Fn lrand48 , +.Fn nrand48 , +.Fn mrand48 , +and +.Fn jrand48 , +and the seed used in +.Fn drand48 , +.Fn lrand48 , +and +.Fn mrand48 . +An array of 7 shorts is passed as parameter; the first three shorts are +used to initialize the seed; the second three are used to initialize the +multiplicand; and the last short is used to initialize the addend. +It is thus not possible to use values greater than 0xffff as the addend. +.Pp +Note that all three methods of seeding the random number generator +always also set the multiplicand and addend for any of the six +generator calls. +.Pp +For a more powerful random number generator, see +.Xr random 3 +.Sh AUTHOR +Martin Birgmeier +.Sh SEE ALSO +.Xr rand 3 , +.Xr random 3 . +============================== cut here ============================== + + diff --git a/lib/libc/stdlib/rand48.h b/lib/libc/stdlib/rand48.h new file mode 100644 index 000000000000..5b9f87d176e4 --- /dev/null +++ b/lib/libc/stdlib/rand48.h @@ -0,0 +1,30 @@ +/* + * Copyright (c) 1993 Martin Birgmeier + * All rights reserved. + * + * You may redistribute unmodified or modified versions of this source + * code provided that the above copyright notice and this and the + * following conditions are retained. + * + * This software is provided ``as is'', and comes with no warranties + * of any kind. I shall in no event be liable for anything that happens + * to anyone/anything when using this software. + */ + +#ifndef _RAND48_H_ +#define _RAND48_H_ + +#include <math.h> +#include <stdlib.h> + +void _dorand48 __P((unsigned short[3])); + +#define RAND48_SEED_0 (0x330e) +#define RAND48_SEED_1 (0xabcd) +#define RAND48_SEED_2 (0x1234) +#define RAND48_MULT_0 (0xe66d) +#define RAND48_MULT_1 (0xdeec) +#define RAND48_MULT_2 (0x0005) +#define RAND48_ADD (0x000b) + +#endif /* _RAND48_H_ */ diff --git a/lib/libc/stdlib/random.3 b/lib/libc/stdlib/random.3 new file mode 100644 index 000000000000..872983cd9e86 --- /dev/null +++ b/lib/libc/stdlib/random.3 @@ -0,0 +1,166 @@ +.\" Copyright (c) 1983, 1991 The Regents of the University of California. +.\" 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 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 by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)random.3 6.5 (Berkeley) 4/19/91 +.\" +.Dd April 19, 1991 +.Dt RANDOM 3 +.Os BSD 4.2 +.Sh NAME +.Nm random , +.Nm srandom , +.Nm initstate , +.Nm setstate +.Nd better random number generator; routines for changing generators +.Sh SYNOPSIS +.Fd #include <stdlib> +.Ft long +.Fn random void +.Ft void +.Fn srandom "unsigned seed" +.Ft char * +.Fn initstate "unsigned seed" "char *state" "int n" +.Ft char * +.Fn setstate "char *state" +.Sh DESCRIPTION +The +.Fn random +function +uses a non-linear additive feedback random number generator employing a +default table of size 31 long integers to return successive pseudo-random +numbers in the range from 0 to +.if t 2\u\s731\s10\d\(mi1. +.if n (2**31)\(mi1. +The period of this random number generator is very large, approximately +.if t 16\(mu(2\u\s731\s10\d\(mi1). +.if n 16*((2**31)\(mi1). +.Pp +The +.Fn random Ns / Fn srandom +have (almost) the same calling sequence and initialization properties as +.Xr rand 3 Ns / Xr srand 3 . +The difference is that +.Xr rand +produces a much less random sequence \(em in fact, the low dozen bits +generated by rand go through a cyclic pattern. All the bits generated by +.Fn random +are usable. For example, +.Sq Li random()&01 +will produce a random binary +value. +.Pp +Unlike +.Xr srand , +.Fn srandom +does not return the old seed; the reason for this is that the amount of +state information used is much more than a single word. (Two other +routines are provided to deal with restarting/changing random +number generators). Like +.Xr rand 3 , +however, +.Fn random +will by default produce a sequence of numbers that can be duplicated +by calling +.Fn srandom +with +.Ql 1 +as the seed. +.Pp +The +.Fn initstate +routine allows a state array, passed in as an argument, to be initialized +for future use. The size of the state array (in bytes) is used by +.Fn initstate +to decide how sophisticated a random number generator it should use \(em the +more state, the better the random numbers will be. +(Current "optimal" values for the amount of state information are +8, 32, 64, 128, and 256 bytes; other amounts will be rounded down to +the nearest known amount. Using less than 8 bytes will cause an error.) +The seed for the initialization (which specifies a starting point for +the random number sequence, and provides for restarting at the same +point) is also an argument. +The +.Fn initstate +function +returns a pointer to the previous state information array. +.Pp +Once a state has been initialized, the +.Fn setstate +routine provides for rapid switching between states. +The +.Fn setstate +function +returns a pointer to the previous state array; its +argument state array is used for further random number generation +until the next call to +.Fn initstate +or +.Fn setstate . +.Pp +Once a state array has been initialized, it may be restarted at a +different point either by calling +.Fn initstate +(with the desired seed, the state array, and its size) or by calling +both +.Fn setstate +(with the state array) and +.Fn srandom +(with the desired seed). +The advantage of calling both +.Fn setstate +and +.Fn srandom +is that the size of the state array does not have to be remembered after +it is initialized. +.Pp +With 256 bytes of state information, the period of the random number +generator is greater than +.if t 2\u\s769\s10\d, +.if n 2**69 +which should be sufficient for most purposes. +.Sh AUTHOR +Earl T. Cohen +.Sh DIAGNOSTICS +If +.Fn initstate +is called with less than 8 bytes of state information, or if +.Fn setstate +detects that the state information has been garbled, error +messages are printed on the standard error output. +.Sh SEE ALSO +.Xr rand 3 +.Sh HISTORY +These +functions appeared in +.Bx 4.2 . +.Sh BUGS +About 2/3 the speed of +.Xr rand 3 . diff --git a/lib/libc/stdlib/random.c b/lib/libc/stdlib/random.c new file mode 100644 index 000000000000..74c5c363885c --- /dev/null +++ b/lib/libc/stdlib/random.c @@ -0,0 +1,363 @@ +/* + * Copyright (c) 1983 Regents of the University of California. + * 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 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 by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)random.c 5.9 (Berkeley) 2/23/91"; +#endif /* LIBC_SCCS and not lint */ + +#include <stdio.h> +#include <stdlib.h> + +/* + * random.c: + * + * An improved random number generation package. In addition to the standard + * rand()/srand() like interface, this package also has a special state info + * interface. The initstate() routine is called with a seed, an array of + * bytes, and a count of how many bytes are being passed in; this array is + * then initialized to contain information for random number generation with + * that much state information. Good sizes for the amount of state + * information are 32, 64, 128, and 256 bytes. The state can be switched by + * calling the setstate() routine with the same array as was initiallized + * with initstate(). By default, the package runs with 128 bytes of state + * information and generates far better random numbers than a linear + * congruential generator. If the amount of state information is less than + * 32 bytes, a simple linear congruential R.N.G. is used. + * + * Internally, the state information is treated as an array of longs; the + * zeroeth element of the array is the type of R.N.G. being used (small + * integer); the remainder of the array is the state information for the + * R.N.G. Thus, 32 bytes of state information will give 7 longs worth of + * state information, which will allow a degree seven polynomial. (Note: + * the zeroeth word of state information also has some other information + * stored in it -- see setstate() for details). + * + * The random number generation technique is a linear feedback shift register + * approach, employing trinomials (since there are fewer terms to sum up that + * way). In this approach, the least significant bit of all the numbers in + * the state table will act as a linear feedback shift register, and will + * have period 2^deg - 1 (where deg is the degree of the polynomial being + * used, assuming that the polynomial is irreducible and primitive). The + * higher order bits will have longer periods, since their values are also + * influenced by pseudo-random carries out of the lower bits. The total + * period of the generator is approximately deg*(2**deg - 1); thus doubling + * the amount of state information has a vast influence on the period of the + * generator. Note: the deg*(2**deg - 1) is an approximation only good for + * large deg, when the period of the shift register is the dominant factor. + * With deg equal to seven, the period is actually much longer than the + * 7*(2**7 - 1) predicted by this formula. + */ + +/* + * For each of the currently supported random number generators, we have a + * break value on the amount of state information (you need at least this + * many bytes of state info to support this random number generator), a degree + * for the polynomial (actually a trinomial) that the R.N.G. is based on, and + * the separation between the two lower order coefficients of the trinomial. + */ +#define TYPE_0 0 /* linear congruential */ +#define BREAK_0 8 +#define DEG_0 0 +#define SEP_0 0 + +#define TYPE_1 1 /* x**7 + x**3 + 1 */ +#define BREAK_1 32 +#define DEG_1 7 +#define SEP_1 3 + +#define TYPE_2 2 /* x**15 + x + 1 */ +#define BREAK_2 64 +#define DEG_2 15 +#define SEP_2 1 + +#define TYPE_3 3 /* x**31 + x**3 + 1 */ +#define BREAK_3 128 +#define DEG_3 31 +#define SEP_3 3 + +#define TYPE_4 4 /* x**63 + x + 1 */ +#define BREAK_4 256 +#define DEG_4 63 +#define SEP_4 1 + +/* + * Array versions of the above information to make code run faster -- + * relies on fact that TYPE_i == i. + */ +#define MAX_TYPES 5 /* max number of types above */ + +static int degrees[MAX_TYPES] = { DEG_0, DEG_1, DEG_2, DEG_3, DEG_4 }; +static int seps [MAX_TYPES] = { SEP_0, SEP_1, SEP_2, SEP_3, SEP_4 }; + +/* + * Initially, everything is set up as if from: + * + * initstate(1, &randtbl, 128); + * + * Note that this initialization takes advantage of the fact that srandom() + * advances the front and rear pointers 10*rand_deg times, and hence the + * rear pointer which starts at 0 will also end up at zero; thus the zeroeth + * element of the state information, which contains info about the current + * position of the rear pointer is just + * + * MAX_TYPES * (rptr - state) + TYPE_3 == TYPE_3. + */ + +static long randtbl[DEG_3 + 1] = { + TYPE_3, + 0x9a319039, 0x32d9c024, 0x9b663182, 0x5da1f342, 0xde3b81e0, 0xdf0a6fb5, + 0xf103bc02, 0x48f340fb, 0x7449e56b, 0xbeb1dbb0, 0xab5c5918, 0x946554fd, + 0x8c2e680f, 0xeb3d799f, 0xb11ee0b7, 0x2d436b86, 0xda672e2a, 0x1588ca88, + 0xe369735d, 0x904f35f7, 0xd7158fd6, 0x6fa6f051, 0x616e6b96, 0xac94efdc, + 0x36413f93, 0xc622c298, 0xf5a42ab8, 0x8a88d77b, 0xf5ad9d0e, 0x8999220b, + 0x27fb47b9, +}; + +/* + * fptr and rptr are two pointers into the state info, a front and a rear + * pointer. These two pointers are always rand_sep places aparts, as they + * cycle cyclically through the state information. (Yes, this does mean we + * could get away with just one pointer, but the code for random() is more + * efficient this way). The pointers are left positioned as they would be + * from the call + * + * initstate(1, randtbl, 128); + * + * (The position of the rear pointer, rptr, is really 0 (as explained above + * in the initialization of randtbl) because the state table pointer is set + * to point to randtbl[1] (as explained below). + */ +static long *fptr = &randtbl[SEP_3 + 1]; +static long *rptr = &randtbl[1]; + +/* + * The following things are the pointer to the state information table, the + * type of the current generator, the degree of the current polynomial being + * used, and the separation between the two pointers. Note that for efficiency + * of random(), we remember the first location of the state information, not + * the zeroeth. Hence it is valid to access state[-1], which is used to + * store the type of the R.N.G. Also, we remember the last location, since + * this is more efficient than indexing every time to find the address of + * the last element to see if the front and rear pointers have wrapped. + */ +static long *state = &randtbl[1]; +static int rand_type = TYPE_3; +static int rand_deg = DEG_3; +static int rand_sep = SEP_3; +static long *end_ptr = &randtbl[DEG_3 + 1]; + +/* + * srandom: + * + * Initialize the random number generator based on the given seed. If the + * type is the trivial no-state-information type, just remember the seed. + * Otherwise, initializes state[] based on the given "seed" via a linear + * congruential generator. Then, the pointers are set to known locations + * that are exactly rand_sep places apart. Lastly, it cycles the state + * information a given number of times to get rid of any initial dependencies + * introduced by the L.C.R.N.G. Note that the initialization of randtbl[] + * for default usage relies on values produced by this routine. + */ +void +srandom(x) + u_int x; +{ + register int i, j; + + if (rand_type == TYPE_0) + state[0] = x; + else { + j = 1; + state[0] = x; + for (i = 1; i < rand_deg; i++) + state[i] = 1103515245 * state[i - 1] + 12345; + fptr = &state[rand_sep]; + rptr = &state[0]; + for (i = 0; i < 10 * rand_deg; i++) + (void)random(); + } +} + +/* + * initstate: + * + * Initialize the state information in the given array of n bytes for future + * random number generation. Based on the number of bytes we are given, and + * the break values for the different R.N.G.'s, we choose the best (largest) + * one we can and set things up for it. srandom() is then called to + * initialize the state information. + * + * Note that on return from srandom(), we set state[-1] to be the type + * multiplexed with the current value of the rear pointer; this is so + * successive calls to initstate() won't lose this information and will be + * able to restart with setstate(). + * + * Note: the first thing we do is save the current state, if any, just like + * setstate() so that it doesn't matter when initstate is called. + * + * Returns a pointer to the old state. + */ +char * +initstate(seed, arg_state, n) + u_int seed; /* seed for R.N.G. */ + char *arg_state; /* pointer to state array */ + int n; /* # bytes of state info */ +{ + register char *ostate = (char *)(&state[-1]); + + if (rand_type == TYPE_0) + state[-1] = rand_type; + else + state[-1] = MAX_TYPES * (rptr - state) + rand_type; + if (n < BREAK_0) { + (void)fprintf(stderr, + "random: not enough state (%d bytes); ignored.\n", n); + return(0); + } + if (n < BREAK_1) { + rand_type = TYPE_0; + rand_deg = DEG_0; + rand_sep = SEP_0; + } else if (n < BREAK_2) { + rand_type = TYPE_1; + rand_deg = DEG_1; + rand_sep = SEP_1; + } else if (n < BREAK_3) { + rand_type = TYPE_2; + rand_deg = DEG_2; + rand_sep = SEP_2; + } else if (n < BREAK_4) { + rand_type = TYPE_3; + rand_deg = DEG_3; + rand_sep = SEP_3; + } else { + rand_type = TYPE_4; + rand_deg = DEG_4; + rand_sep = SEP_4; + } + state = &(((long *)arg_state)[1]); /* first location */ + end_ptr = &state[rand_deg]; /* must set end_ptr before srandom */ + srandom(seed); + if (rand_type == TYPE_0) + state[-1] = rand_type; + else + state[-1] = MAX_TYPES*(rptr - state) + rand_type; + return(ostate); +} + +/* + * setstate: + * + * Restore the state from the given state array. + * + * Note: it is important that we also remember the locations of the pointers + * in the current state information, and restore the locations of the pointers + * from the old state information. This is done by multiplexing the pointer + * location into the zeroeth word of the state information. + * + * Note that due to the order in which things are done, it is OK to call + * setstate() with the same state as the current state. + * + * Returns a pointer to the old state information. + */ +char * +setstate(arg_state) + char *arg_state; +{ + register long *new_state = (long *)arg_state; + register int type = new_state[0] % MAX_TYPES; + register int rear = new_state[0] / MAX_TYPES; + char *ostate = (char *)(&state[-1]); + + if (rand_type == TYPE_0) + state[-1] = rand_type; + else + state[-1] = MAX_TYPES * (rptr - state) + rand_type; + switch(type) { + case TYPE_0: + case TYPE_1: + case TYPE_2: + case TYPE_3: + case TYPE_4: + rand_type = type; + rand_deg = degrees[type]; + rand_sep = seps[type]; + break; + default: + (void)fprintf(stderr, + "random: state info corrupted; not changed.\n"); + } + state = &new_state[1]; + if (rand_type != TYPE_0) { + rptr = &state[rear]; + fptr = &state[(rear + rand_sep) % rand_deg]; + } + end_ptr = &state[rand_deg]; /* set end_ptr too */ + return(ostate); +} + +/* + * random: + * + * If we are using the trivial TYPE_0 R.N.G., just do the old linear + * congruential bit. Otherwise, we do our fancy trinomial stuff, which is + * the same in all the other cases due to all the global variables that have + * been set up. The basic operation is to add the number at the rear pointer + * into the one at the front pointer. Then both pointers are advanced to + * the next location cyclically in the table. The value returned is the sum + * generated, reduced to 31 bits by throwing away the "least random" low bit. + * + * Note: the code takes advantage of the fact that both the front and + * rear pointers can't wrap on the same call by not testing the rear + * pointer if the front one has wrapped. + * + * Returns a 31-bit random number. + */ +long +random() +{ + long i; + + if (rand_type == TYPE_0) + i = state[0] = (state[0] * 1103515245 + 12345) & 0x7fffffff; + else { + *fptr += *rptr; + i = (*fptr >> 1) & 0x7fffffff; /* chucking least random bit */ + if (++fptr >= end_ptr) { + fptr = state; + ++rptr; + } else if (++rptr >= end_ptr) + rptr = state; + } + return(i); +} diff --git a/lib/libc/stdlib/realloc.3 b/lib/libc/stdlib/realloc.3 new file mode 100644 index 000000000000..ee3e64018fc7 --- /dev/null +++ b/lib/libc/stdlib/realloc.3 @@ -0,0 +1,99 @@ +.\" Copyright (c) 1991 The Regents of the University of California. +.\" 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 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 by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)realloc.3 5.1 (Berkeley) 5/2/91 +.\" +.Dd May 2, 1991 +.Dt REALLOC 3 +.Os +.Sh NAME +.Nm realloc +.Nd reallocation of memory function +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft void * +.Fn realloc "void *ptr" "size_t size" +.Sh DESCRIPTION +The +.Fn realloc +function changes the size of the object pointed to by +.Fa ptr +to the size specified by +.Fa size . +The contents of the object are unchanged up to the lesser +of the new and old sizes. +If the new size is larger, the value of the newly allocated portion +of the object is indeterminate. +If +.Fa ptr +is a null pointer, the +.Fn realloc +function behaves like the +.Xr malloc 3 +function for the specified size. +Otherwise, if +.Fa ptr +does not match a pointer earlier returned by the +.Xr calloc 3 , +.Xr malloc 3 , +or +.Fn realloc +function, or if the space has been deallocated +by a call to the +.Xr free +or +.Fn realloc +function, unpredictable and usually detrimental +behaviour will occur. +If the space cannot be allocated, the object +pointed to by +.Fa ptr +is unchanged. +If +.Fa size +is zero and +.Fa ptr +is not a null pointer, the object it points to is freed. +.Pp +The +.Fn realloc +function returns either a null pointer or a pointer +to the possibly moved allocated space. +.Sh SEE ALSO +.Xr alloca 3 , +.Xr calloc 3 , +.Xr free 3 , +.Xr malloc 3 , +.Sh STANDARDS +The +.Fn realloc +function conforms to +.St -ansiC . diff --git a/lib/libc/stdlib/seed48.c b/lib/libc/stdlib/seed48.c new file mode 100644 index 000000000000..258c4bac3c9f --- /dev/null +++ b/lib/libc/stdlib/seed48.c @@ -0,0 +1,36 @@ +/* + * Copyright (c) 1993 Martin Birgmeier + * All rights reserved. + * + * You may redistribute unmodified or modified versions of this source + * code provided that the above copyright notice and this and the + * following conditions are retained. + * + * This software is provided ``as is'', and comes with no warranties + * of any kind. I shall in no event be liable for anything that happens + * to anyone/anything when using this software. + */ + +#include "rand48.h" + +extern unsigned short _rand48_seed[3]; +extern unsigned short _rand48_mult[3]; +extern unsigned short _rand48_add; + +unsigned short * +seed48(unsigned short xseed[3]) +{ + static unsigned short sseed[3]; + + sseed[0] = _rand48_seed[0]; + sseed[1] = _rand48_seed[1]; + sseed[2] = _rand48_seed[2]; + _rand48_seed[0] = xseed[0]; + _rand48_seed[1] = xseed[1]; + _rand48_seed[2] = xseed[2]; + _rand48_mult[0] = RAND48_MULT_0; + _rand48_mult[1] = RAND48_MULT_1; + _rand48_mult[2] = RAND48_MULT_2; + _rand48_add = RAND48_ADD; + return sseed; +} diff --git a/lib/libc/stdlib/setenv.c b/lib/libc/stdlib/setenv.c new file mode 100644 index 000000000000..14efac37b37c --- /dev/null +++ b/lib/libc/stdlib/setenv.c @@ -0,0 +1,118 @@ +/* + * Copyright (c) 1987 Regents of the University of California. + * 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 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 by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)setenv.c 5.6 (Berkeley) 6/4/91"; +#endif /* LIBC_SCCS and not lint */ + +#include <stddef.h> +#include <stdlib.h> +#include <string.h> + +/* + * setenv -- + * Set the value of the environmental variable "name" to be + * "value". If rewrite is set, replace any current value. + */ +setenv(name, value, rewrite) + register const char *name; + register const char *value; + int rewrite; +{ + extern char **environ; + static int alloced; /* if allocated space before */ + register char *C; + int l_value, offset; + char *_findenv(); + + if (*value == '=') /* no `=' in value */ + ++value; + l_value = strlen(value); + if ((C = _findenv(name, &offset))) { /* find if already exists */ + if (!rewrite) + return (0); + if (strlen(C) >= l_value) { /* old larger; copy over */ + while (*C++ = *value++); + return (0); + } + } else { /* create new slot */ + register int cnt; + register char **P; + + for (P = environ, cnt = 0; *P; ++P, ++cnt); + if (alloced) { /* just increase size */ + environ = (char **)realloc((char *)environ, + (size_t)(sizeof(char *) * (cnt + 2))); + if (!environ) + return (-1); + } + else { /* get new space */ + alloced = 1; /* copy old entries into it */ + P = (char **)malloc((size_t)(sizeof(char *) * + (cnt + 2))); + if (!P) + return (-1); + bcopy(environ, P, cnt * sizeof(char *)); + environ = P; + } + environ[cnt + 1] = NULL; + offset = cnt; + } + for (C = (char *)name; *C && *C != '='; ++C); /* no `=' in name */ + if (!(environ[offset] = /* name + `=' + value */ + malloc((size_t)((int)(C - name) + l_value + 2)))) + return (-1); + for (C = environ[offset]; (*C = *name++) && *C != '='; ++C) + ; + for (*C++ = '='; *C++ = *value++; ) + ; + return (0); +} + +/* + * unsetenv(name) -- + * Delete environmental variable "name". + */ +void +unsetenv(name) + const char *name; +{ + extern char **environ; + register char **P; + int offset; + + while (_findenv(name, &offset)) /* if set multiple times */ + for (P = &environ[offset];; ++P) + if (!(*P = *(P + 1))) + break; +} diff --git a/lib/libc/stdlib/srand48.c b/lib/libc/stdlib/srand48.c new file mode 100644 index 000000000000..fd369a094c51 --- /dev/null +++ b/lib/libc/stdlib/srand48.c @@ -0,0 +1,30 @@ +/* + * Copyright (c) 1993 Martin Birgmeier + * All rights reserved. + * + * You may redistribute unmodified or modified versions of this source + * code provided that the above copyright notice and this and the + * following conditions are retained. + * + * This software is provided ``as is'', and comes with no warranties + * of any kind. I shall in no event be liable for anything that happens + * to anyone/anything when using this software. + */ + +#include "rand48.h" + +extern unsigned short _rand48_seed[3]; +extern unsigned short _rand48_mult[3]; +extern unsigned short _rand48_add; + +void +srand48(long seed) +{ + _rand48_seed[0] = RAND48_SEED_0; + _rand48_seed[1] = (unsigned short) seed; + _rand48_seed[2] = (unsigned short) (seed >> 16); + _rand48_mult[0] = RAND48_MULT_0; + _rand48_mult[1] = RAND48_MULT_1; + _rand48_mult[2] = RAND48_MULT_2; + _rand48_add = RAND48_ADD; +} diff --git a/lib/libc/stdlib/strtod.3 b/lib/libc/stdlib/strtod.3 new file mode 100644 index 000000000000..53e3935f07fb --- /dev/null +++ b/lib/libc/stdlib/strtod.3 @@ -0,0 +1,118 @@ +.\" Copyright (c) 1990, 1991 The Regents of the University of California. +.\" All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" the American National Standards Committee X3, on Information +.\" Processing Systems. +.\" +.\" 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 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 by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)strtod.3 5.3 (Berkeley) 6/29/91 +.\" +.Dd June 29, 1991 +.Dt STRTOD 3 +.Os +.Sh NAME +.Nm strtod +.Nd convert +.Tn ASCII +string to double +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft double +.Fn strtod "const char *nptr" "char **endptr" +.Sh DESCRIPTION +The +.Fn strtod +function converts the initial portion of the string +pointed to by +.Fa nptr +to +.Em double +representation. +.Pp +The expected form of the string is an optional plus (``+'') or minus +sign (``-'') followed by a sequence of digits optionally containing +a decimal-point character, optionally followed by an exponent. +An exponent consists of an ``E'' or ``e'', followed by an optional plus +or minus sign, followed by a sequence of digits. +.Pp +Leading white-space characters in the string (as defined by the +.Xr isspace 3 +function) are skipped. +.Sh RETURN VALUES +The +.Fn strtod +function returns the converted value, if any. +.Pp +If +.Fa endptr +is not +.Dv NULL , +a pointer to the character after the last character used +in the conversion is stored in the location referenced by +.Fa endptr . +.Pp +If no conversion is performed, zero is returned and the value of +.Fa nptr +is stored in the location referenced by +.Fa endptr . +.Pp +If the correct value would cause overflow, plus or minus +.Dv HUGE_VAL +is returned (according to the sign of the value), and +.Dv ERANGE +is stored in +.Va errno . +If the correct value would cause underflow, zero is +returned and +.Dv ERANGE +is stored in +.Va errno . +.Sh ERRORS +.Bl -tag -width [ERANGE] +.It Bq Er ERANGE +Overflow or underflow occurred. +.Sh SEE ALSO +.Xr atof 3 , +.Xr atoi 3 , +.Xr atol 3 , +.Xr strtol 3 , +.Xr strtoul 3 +.Sh STANDARDS +The +.Fn strtod +function +conforms to +.St -ansiC . +.Sh BUGS +This manual page represents intent instead of actual practice. +The +.Fn strtod +function is not currently available. diff --git a/lib/libc/stdlib/strtod.c b/lib/libc/stdlib/strtod.c new file mode 100644 index 000000000000..26bd80d2e882 --- /dev/null +++ b/lib/libc/stdlib/strtod.c @@ -0,0 +1,2410 @@ +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)strtod.c 5.1 (Berkeley) 11/13/92"; +#endif /* LIBC_SCCS and not lint */ + +/**************************************************************** + * + * The author of this software is David M. Gay. + * + * Copyright (c) 1991 by AT&T. + * + * Permission to use, copy, modify, and distribute this software for any + * purpose without fee is hereby granted, provided that this entire notice + * is included in all copies of any software which is or includes a copy + * or modification of this software and in all copies of the supporting + * documentation for such software. + * + * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED + * WARRANTY. IN PARTICULAR, NEITHER THE AUTHOR NOR AT&T MAKES ANY + * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY + * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE. + * + ***************************************************************/ + +/* Please send bug reports to + David M. Gay + AT&T Bell Laboratories, Room 2C-463 + 600 Mountain Avenue + Murray Hill, NJ 07974-2070 + U.S.A. + dmg@research.att.com or research!dmg + */ + +/* strtod for IEEE-, VAX-, and IBM-arithmetic machines. + * + * This strtod returns a nearest machine number to the input decimal + * string (or sets errno to ERANGE). With IEEE arithmetic, ties are + * broken by the IEEE round-even rule. Otherwise ties are broken by + * biased rounding (add half and chop). + * + * Inspired loosely by William D. Clinger's paper "How to Read Floating + * Point Numbers Accurately" [Proc. ACM SIGPLAN '90, pp. 92-101]. + * + * Modifications: + * + * 1. We only require IEEE, IBM, or VAX double-precision + * arithmetic (not IEEE double-extended). + * 2. We get by with floating-point arithmetic in a case that + * Clinger missed -- when we're computing d * 10^n + * for a small integer d and the integer n is not too + * much larger than 22 (the maximum integer k for which + * we can represent 10^k exactly), we may be able to + * compute (d*10^k) * 10^(e-k) with just one roundoff. + * 3. Rather than a bit-at-a-time adjustment of the binary + * result in the hard case, we use floating-point + * arithmetic to determine the adjustment to within + * one bit; only in really hard cases do we need to + * compute a second residual. + * 4. Because of 3., we don't need a large table of powers of 10 + * for ten-to-e (just some small tables, e.g. of 10^k + * for 0 <= k <= 22). + */ + +/* + * #define IEEE_8087 for IEEE-arithmetic machines where the least + * significant byte has the lowest address. + * #define IEEE_MC68k for IEEE-arithmetic machines where the most + * significant byte has the lowest address. + * #define Sudden_Underflow for IEEE-format machines without gradual + * underflow (i.e., that flush to zero on underflow). + * #define IBM for IBM mainframe-style floating-point arithmetic. + * #define VAX for VAX-style floating-point arithmetic. + * #define Unsigned_Shifts if >> does treats its left operand as unsigned. + * #define No_leftright to omit left-right logic in fast floating-point + * computation of dtoa. + * #define Check_FLT_ROUNDS if FLT_ROUNDS can assume the values 2 or 3. + * #define RND_PRODQUOT to use rnd_prod and rnd_quot (assembly routines + * that use extended-precision instructions to compute rounded + * products and quotients) with IBM. + * #define ROUND_BIASED for IEEE-format with biased rounding. + * #define Inaccurate_Divide for IEEE-format with correctly rounded + * products but inaccurate quotients, e.g., for Intel i860. + * #define Just_16 to store 16 bits per 32-bit long when doing high-precision + * integer arithmetic. Whether this speeds things up or slows things + * down depends on the machine and the number being converted. + * #define KR_headers for old-style C function headers. + * #define Bad_float_h if your system lacks a float.h or if it does not + * define some or all of DBL_DIG, DBL_MAX_10_EXP, DBL_MAX_EXP, + * FLT_RADIX, FLT_ROUNDS, and DBL_MAX. + */ + +#define IEEE_8087 + +#ifdef DEBUG +#include "stdio.h" +#define Bug(x) {fprintf(stderr, "%s\n", x); exit(1);} +#endif + +#ifdef __cplusplus +#include "malloc.h" +#include "memory.h" +#else +#ifndef KR_headers +#include "stdlib.h" +#include "string.h" +#else +#include "malloc.h" +#include "memory.h" +#endif +#endif + +#include "errno.h" +#ifdef Bad_float_h +#undef __STDC__ +#ifdef IEEE_MC68k +#define IEEE_ARITHMETIC +#endif +#ifdef IEEE_8087 +#define IEEE_ARITHMETIC +#endif +#ifdef IEEE_ARITHMETIC +#define DBL_DIG 15 +#define DBL_MAX_10_EXP 308 +#define DBL_MAX_EXP 1024 +#define FLT_RADIX 2 +#define FLT_ROUNDS 1 +#define DBL_MAX 1.7976931348623157e+308 +#endif + +#ifdef IBM +#define DBL_DIG 16 +#define DBL_MAX_10_EXP 75 +#define DBL_MAX_EXP 63 +#define FLT_RADIX 16 +#define FLT_ROUNDS 0 +#define DBL_MAX 7.2370055773322621e+75 +#endif + +#ifdef VAX +#define DBL_DIG 16 +#define DBL_MAX_10_EXP 38 +#define DBL_MAX_EXP 127 +#define FLT_RADIX 2 +#define FLT_ROUNDS 1 +#define DBL_MAX 1.7014118346046923e+38 +#endif + +#ifndef LONG_MAX +#define LONG_MAX 2147483647 +#endif +#else +#include "float.h" +#endif +#ifndef __MATH_H__ +#include "math.h" +#endif + +#ifdef __cplusplus +extern "C" { +#endif + +#ifndef CONST +#ifdef KR_headers +#define CONST /* blank */ +#else +#define CONST const +#endif +#endif + +#ifdef Unsigned_Shifts +#define Sign_Extend(a,b) if (b < 0) a |= 0xffff0000; +#else +#define Sign_Extend(a,b) /*no-op*/ +#endif + +#if defined(IEEE_8087) + defined(IEEE_MC68k) + defined(VAX) + defined(IBM) != 1 +Exactly one of IEEE_8087, IEEE_MC68k, VAX, or IBM should be defined. +#endif + +#ifdef IEEE_8087 +#define word0(x) ((unsigned long *)&x)[1] +#define word1(x) ((unsigned long *)&x)[0] +#else +#define word0(x) ((unsigned long *)&x)[0] +#define word1(x) ((unsigned long *)&x)[1] +#endif + +/* The following definition of Storeinc is appropriate for MIPS processors. + * An alternative that might be better on some machines is + * #define Storeinc(a,b,c) (*a++ = b << 16 | c & 0xffff) + */ +#if defined(IEEE_8087) + defined(VAX) +#define Storeinc(a,b,c) (((unsigned short *)a)[1] = (unsigned short)b, \ +((unsigned short *)a)[0] = (unsigned short)c, a++) +#else +#define Storeinc(a,b,c) (((unsigned short *)a)[0] = (unsigned short)b, \ +((unsigned short *)a)[1] = (unsigned short)c, a++) +#endif + +/* #define P DBL_MANT_DIG */ +/* Ten_pmax = floor(P*log(2)/log(5)) */ +/* Bletch = (highest power of 2 < DBL_MAX_10_EXP) / 16 */ +/* Quick_max = floor((P-1)*log(FLT_RADIX)/log(10) - 1) */ +/* Int_max = floor(P*log(FLT_RADIX)/log(10) - 1) */ + +#if defined(IEEE_8087) + defined(IEEE_MC68k) +#define Exp_shift 20 +#define Exp_shift1 20 +#define Exp_msk1 0x100000 +#define Exp_msk11 0x100000 +#define Exp_mask 0x7ff00000 +#define P 53 +#define Bias 1023 +#define IEEE_Arith +#define Emin (-1022) +#define Exp_1 0x3ff00000 +#define Exp_11 0x3ff00000 +#define Ebits 11 +#define Frac_mask 0xfffff +#define Frac_mask1 0xfffff +#define Ten_pmax 22 +#define Bletch 0x10 +#define Bndry_mask 0xfffff +#define Bndry_mask1 0xfffff +#define LSB 1 +#define Sign_bit 0x80000000 +#define Log2P 1 +#define Tiny0 0 +#define Tiny1 1 +#define Quick_max 14 +#define Int_max 14 +#define Infinite(x) (word0(x) == 0x7ff00000) /* sufficient test for here */ +#else +#undef Sudden_Underflow +#define Sudden_Underflow +#ifdef IBM +#define Exp_shift 24 +#define Exp_shift1 24 +#define Exp_msk1 0x1000000 +#define Exp_msk11 0x1000000 +#define Exp_mask 0x7f000000 +#define P 14 +#define Bias 65 +#define Exp_1 0x41000000 +#define Exp_11 0x41000000 +#define Ebits 8 /* exponent has 7 bits, but 8 is the right value in b2d */ +#define Frac_mask 0xffffff +#define Frac_mask1 0xffffff +#define Bletch 4 +#define Ten_pmax 22 +#define Bndry_mask 0xefffff +#define Bndry_mask1 0xffffff +#define LSB 1 +#define Sign_bit 0x80000000 +#define Log2P 4 +#define Tiny0 0x100000 +#define Tiny1 0 +#define Quick_max 14 +#define Int_max 15 +#else /* VAX */ +#define Exp_shift 23 +#define Exp_shift1 7 +#define Exp_msk1 0x80 +#define Exp_msk11 0x800000 +#define Exp_mask 0x7f80 +#define P 56 +#define Bias 129 +#define Exp_1 0x40800000 +#define Exp_11 0x4080 +#define Ebits 8 +#define Frac_mask 0x7fffff +#define Frac_mask1 0xffff007f +#define Ten_pmax 24 +#define Bletch 2 +#define Bndry_mask 0xffff007f +#define Bndry_mask1 0xffff007f +#define LSB 0x10000 +#define Sign_bit 0x8000 +#define Log2P 1 +#define Tiny0 0x80 +#define Tiny1 0 +#define Quick_max 15 +#define Int_max 15 +#endif +#endif + +#ifndef IEEE_Arith +#define ROUND_BIASED +#endif + +#ifdef RND_PRODQUOT +#define rounded_product(a,b) a = rnd_prod(a, b) +#define rounded_quotient(a,b) a = rnd_quot(a, b) +#ifdef KR_headers +extern double rnd_prod(), rnd_quot(); +#else +extern double rnd_prod(double, double), rnd_quot(double, double); +#endif +#else +#define rounded_product(a,b) a *= b +#define rounded_quotient(a,b) a /= b +#endif + +#define Big0 (Frac_mask1 | Exp_msk1*(DBL_MAX_EXP+Bias-1)) +#define Big1 0xffffffff + +#ifndef Just_16 +/* When Pack_32 is not defined, we store 16 bits per 32-bit long. + * This makes some inner loops simpler and sometimes saves work + * during multiplications, but it often seems to make things slightly + * slower. Hence the default is now to store 32 bits per long. + */ +#ifndef Pack_32 +#define Pack_32 +#endif +#endif + +#define Kmax 15 + +#ifdef __cplusplus +extern "C" double strtod(const char *s00, char **se); +extern "C" char *dtoa(double d, int mode, int ndigits, + int *decpt, int *sign, char **rve); +#endif + + struct +Bigint { + struct Bigint *next; + int k, maxwds, sign, wds; + unsigned long x[1]; +}; + + typedef struct Bigint Bigint; + + static Bigint *freelist[Kmax+1]; + + static Bigint * +Balloc +#ifdef KR_headers + (k) int k; +#else + (int k) +#endif +{ + int x; + Bigint *rv; + + if (rv = freelist[k]) { + freelist[k] = rv->next; + } else { + x = 1 << k; + rv = (Bigint *)malloc(sizeof(Bigint) + (x-1)*sizeof(long)); + rv->k = k; + rv->maxwds = x; + } + rv->sign = rv->wds = 0; + return rv; +} + + static void +Bfree +#ifdef KR_headers + (v) Bigint *v; +#else + (Bigint *v) +#endif +{ + if (v) { + v->next = freelist[v->k]; + freelist[v->k] = v; + } +} + +#define Bcopy(x,y) memcpy((char *)&x->sign, (char *)&y->sign, \ +y->wds*sizeof(long) + 2*sizeof(int)) + + static Bigint * +multadd +#ifdef KR_headers + (b, m, a) Bigint *b; int m, a; +#else + (Bigint *b, int m, int a) /* multiply by m and add a */ +#endif +{ + int i, wds; + unsigned long *x, y; +#ifdef Pack_32 + unsigned long xi, z; +#endif + Bigint *b1; + + wds = b->wds; + x = b->x; + i = 0; + do { +#ifdef Pack_32 + xi = *x; + y = (xi & 0xffff) * m + a; + z = (xi >> 16) * m + (y >> 16); + a = (int)(z >> 16); + *x++ = (z << 16) + (y & 0xffff); +#else + y = *x * m + a; + a = (int)(y >> 16); + *x++ = y & 0xffff; +#endif + } while (++i < wds); + if (a) { + if (wds >= b->maxwds) { + b1 = Balloc(b->k+1); + Bcopy(b1, b); + Bfree(b); + b = b1; + } + b->x[wds++] = a; + b->wds = wds; + } + return b; +} + + static Bigint * +s2b +#ifdef KR_headers + (s, nd0, nd, y9) CONST char *s; int nd0, nd; unsigned long y9; +#else + (CONST char *s, int nd0, int nd, unsigned long y9) +#endif +{ + Bigint *b; + int i, k; + long x, y; + + x = (nd + 8) / 9; + for (k = 0, y = 1; x > y; y <<= 1, k++) ; +#ifdef Pack_32 + b = Balloc(k); + b->x[0] = y9; + b->wds = 1; +#else + b = Balloc(k+1); + b->x[0] = y9 & 0xffff; + b->wds = (b->x[1] = y9 >> 16) ? 2 : 1; +#endif + + i = 9; + if (9 < nd0) { + s += 9; + do + b = multadd(b, 10, *s++ - '0'); + while (++i < nd0); + s++; + } else + s += 10; + for (; i < nd; i++) + b = multadd(b, 10, *s++ - '0'); + return b; +} + + static int +hi0bits +#ifdef KR_headers + (x) register unsigned long x; +#else + (register unsigned long x) +#endif +{ + register int k = 0; + + if (!(x & 0xffff0000)) { + k = 16; + x <<= 16; + } + if (!(x & 0xff000000)) { + k += 8; + x <<= 8; + } + if (!(x & 0xf0000000)) { + k += 4; + x <<= 4; + } + if (!(x & 0xc0000000)) { + k += 2; + x <<= 2; + } + if (!(x & 0x80000000)) { + k++; + if (!(x & 0x40000000)) + return 32; + } + return k; +} + + static int +lo0bits +#ifdef KR_headers + (y) unsigned long *y; +#else + (unsigned long *y) +#endif +{ + register int k; + register unsigned long x = *y; + + if (x & 7) { + if (x & 1) + return 0; + if (x & 2) { + *y = x >> 1; + return 1; + } + *y = x >> 2; + return 2; + } + k = 0; + if (!(x & 0xffff)) { + k = 16; + x >>= 16; + } + if (!(x & 0xff)) { + k += 8; + x >>= 8; + } + if (!(x & 0xf)) { + k += 4; + x >>= 4; + } + if (!(x & 0x3)) { + k += 2; + x >>= 2; + } + if (!(x & 1)) { + k++; + x >>= 1; + if (!x & 1) + return 32; + } + *y = x; + return k; +} + + static Bigint * +i2b +#ifdef KR_headers + (i) int i; +#else + (int i) +#endif +{ + Bigint *b; + + b = Balloc(1); + b->x[0] = i; + b->wds = 1; + return b; + } + + static Bigint * +mult +#ifdef KR_headers + (a, b) Bigint *a, *b; +#else + (Bigint *a, Bigint *b) +#endif +{ + Bigint *c; + int k, wa, wb, wc; + unsigned long carry, y, z; + unsigned long *x, *xa, *xae, *xb, *xbe, *xc, *xc0; +#ifdef Pack_32 + unsigned long z2; +#endif + + if (a->wds < b->wds) { + c = a; + a = b; + b = c; + } + k = a->k; + wa = a->wds; + wb = b->wds; + wc = wa + wb; + if (wc > a->maxwds) + k++; + c = Balloc(k); + for (x = c->x, xa = x + wc; x < xa; x++) + *x = 0; + xa = a->x; + xae = xa + wa; + xb = b->x; + xbe = xb + wb; + xc0 = c->x; +#ifdef Pack_32 + for (; xb < xbe; xb++, xc0++) { + if (y = *xb & 0xffff) { + x = xa; + xc = xc0; + carry = 0; + do { + z = (*x & 0xffff) * y + (*xc & 0xffff) + carry; + carry = z >> 16; + z2 = (*x++ >> 16) * y + (*xc >> 16) + carry; + carry = z2 >> 16; + Storeinc(xc, z2, z); + } while (x < xae); + *xc = carry; + } + if (y = *xb >> 16) { + x = xa; + xc = xc0; + carry = 0; + z2 = *xc; + do { + z = (*x & 0xffff) * y + (*xc >> 16) + carry; + carry = z >> 16; + Storeinc(xc, z, z2); + z2 = (*x++ >> 16) * y + (*xc & 0xffff) + carry; + carry = z2 >> 16; + } while (x < xae); + *xc = z2; + } + } +#else + for (; xb < xbe; xc0++) { + if (y = *xb++) { + x = xa; + xc = xc0; + carry = 0; + do { + z = *x++ * y + *xc + carry; + carry = z >> 16; + *xc++ = z & 0xffff; + } while (x < xae); + *xc = carry; + } + } +#endif + for (xc0 = c->x, xc = xc0 + wc; wc > 0 && !*--xc; --wc) ; + c->wds = wc; + return c; +} + + static Bigint *p5s; + + static Bigint * +pow5mult +#ifdef KR_headers + (b, k) Bigint *b; int k; +#else + (Bigint *b, int k) +#endif +{ + Bigint *b1, *p5, *p51; + int i; + static int p05[3] = { 5, 25, 125 }; + + if (i = k & 3) + b = multadd(b, p05[i-1], 0); + + if (!(k >>= 2)) + return b; + if (!(p5 = p5s)) { + /* first time */ + p5 = p5s = i2b(625); + p5->next = 0; + } + for (;;) { + if (k & 1) { + b1 = mult(b, p5); + Bfree(b); + b = b1; + } + if (!(k >>= 1)) + break; + if (!(p51 = p5->next)) { + p51 = p5->next = mult(p5,p5); + p51->next = 0; + } + p5 = p51; + } + return b; +} + + static Bigint * +lshift +#ifdef KR_headers + (b, k) Bigint *b; int k; +#else + (Bigint *b, int k) +#endif +{ + int i, k1, n, n1; + Bigint *b1; + unsigned long *x, *x1, *xe, z; + +#ifdef Pack_32 + n = k >> 5; +#else + n = k >> 4; +#endif + k1 = b->k; + n1 = n + b->wds + 1; + for (i = b->maxwds; n1 > i; i <<= 1) + k1++; + b1 = Balloc(k1); + x1 = b1->x; + for (i = 0; i < n; i++) + *x1++ = 0; + x = b->x; + xe = x + b->wds; +#ifdef Pack_32 + if (k &= 0x1f) { + k1 = 32 - k; + z = 0; + do { + *x1++ = *x << k | z; + z = *x++ >> k1; + } while (x < xe); + if (*x1 = z) + ++n1; + } +#else + if (k &= 0xf) { + k1 = 16 - k; + z = 0; + do { + *x1++ = *x << k & 0xffff | z; + z = *x++ >> k1; + } while (x < xe); + if (*x1 = z) + ++n1; + } +#endif + else + do + *x1++ = *x++; + while (x < xe); + b1->wds = n1 - 1; + Bfree(b); + return b1; +} + + static int +cmp +#ifdef KR_headers + (a, b) Bigint *a, *b; +#else + (Bigint *a, Bigint *b) +#endif +{ + unsigned long *xa, *xa0, *xb, *xb0; + int i, j; + + i = a->wds; + j = b->wds; +#ifdef DEBUG + if (i > 1 && !a->x[i-1]) + Bug("cmp called with a->x[a->wds-1] == 0"); + if (j > 1 && !b->x[j-1]) + Bug("cmp called with b->x[b->wds-1] == 0"); +#endif + if (i -= j) + return i; + xa0 = a->x; + xa = xa0 + j; + xb0 = b->x; + xb = xb0 + j; + for (;;) { + if (*--xa != *--xb) + return *xa < *xb ? -1 : 1; + if (xa <= xa0) + break; + } + return 0; +} + + static Bigint * +diff +#ifdef KR_headers + (a, b) Bigint *a, *b; +#else + (Bigint *a, Bigint *b) +#endif +{ + Bigint *c; + int i, wa, wb; + long borrow, y; /* We need signed shifts here. */ + unsigned long *xa, *xae, *xb, *xbe, *xc; +#ifdef Pack_32 + long z; +#endif + + i = cmp(a,b); + if (!i) { + c = Balloc(0); + c->wds = 1; + c->x[0] = 0; + return c; + } + if (i < 0) { + c = a; + a = b; + b = c; + i = 1; + } else + i = 0; + c = Balloc(a->k); + c->sign = i; + wa = a->wds; + xa = a->x; + xae = xa + wa; + wb = b->wds; + xb = b->x; + xbe = xb + wb; + xc = c->x; + borrow = 0; +#ifdef Pack_32 + do { + y = (*xa & 0xffff) - (*xb & 0xffff) + borrow; + borrow = y >> 16; + Sign_Extend(borrow, y); + z = (*xa++ >> 16) - (*xb++ >> 16) + borrow; + borrow = z >> 16; + Sign_Extend(borrow, z); + Storeinc(xc, z, y); + } while (xb < xbe); + while (xa < xae) { + y = (*xa & 0xffff) + borrow; + borrow = y >> 16; + Sign_Extend(borrow, y); + z = (*xa++ >> 16) + borrow; + borrow = z >> 16; + Sign_Extend(borrow, z); + Storeinc(xc, z, y); + } +#else + do { + y = *xa++ - *xb++ + borrow; + borrow = y >> 16; + Sign_Extend(borrow, y); + *xc++ = y & 0xffff; + } while (xb < xbe); + while (xa < xae) { + y = *xa++ + borrow; + borrow = y >> 16; + Sign_Extend(borrow, y); + *xc++ = y & 0xffff; + } +#endif + while (!*--xc) + wa--; + c->wds = wa; + return c; +} + + static double +ulp +#ifdef KR_headers + (x) double x; +#else + (double x) +#endif +{ + register long L; + double a; + + L = (word0(x) & Exp_mask) - (P-1)*Exp_msk1; +#ifndef Sudden_Underflow + if (L > 0) { +#endif +#ifdef IBM + L |= Exp_msk1 >> 4; +#endif + word0(a) = L; + word1(a) = 0; +#ifndef Sudden_Underflow + } else { + L = -L >> Exp_shift; + if (L < Exp_shift) { + word0(a) = 0x80000 >> L; + word1(a) = 0; + } else { + word0(a) = 0; + L -= Exp_shift; + word1(a) = L >= 31 ? 1 : 1 << 31 - L; + } + } +#endif + return a; +} + + static double +b2d +#ifdef KR_headers + (a, e) Bigint *a; int *e; +#else + (Bigint *a, int *e) +#endif +{ + unsigned long *xa, *xa0, w, y, z; + int k; + double d; +#ifdef VAX + unsigned long d0, d1; +#else +#define d0 word0(d) +#define d1 word1(d) +#endif + + xa0 = a->x; + xa = xa0 + a->wds; + y = *--xa; +#ifdef DEBUG + if (!y) Bug("zero y in b2d"); +#endif + k = hi0bits(y); + *e = 32 - k; +#ifdef Pack_32 + if (k < Ebits) { + d0 = Exp_1 | y >> Ebits - k; + w = xa > xa0 ? *--xa : 0; + d1 = y << (32-Ebits) + k | w >> Ebits - k; + goto ret_d; + } + z = xa > xa0 ? *--xa : 0; + if (k -= Ebits) { + d0 = Exp_1 | y << k | z >> 32 - k; + y = xa > xa0 ? *--xa : 0; + d1 = z << k | y >> 32 - k; + } else { + d0 = Exp_1 | y; + d1 = z; + } +#else + if (k < Ebits + 16) { + z = xa > xa0 ? *--xa : 0; + d0 = Exp_1 | y << k - Ebits | z >> Ebits + 16 - k; + w = xa > xa0 ? *--xa : 0; + y = xa > xa0 ? *--xa : 0; + d1 = z << k + 16 - Ebits | w << k - Ebits | y >> 16 + Ebits - k; + goto ret_d; + } + z = xa > xa0 ? *--xa : 0; + w = xa > xa0 ? *--xa : 0; + k -= Ebits + 16; + d0 = Exp_1 | y << k + 16 | z << k | w >> 16 - k; + y = xa > xa0 ? *--xa : 0; + d1 = w << k + 16 | y << k; +#endif + ret_d: +#ifdef VAX + word0(d) = d0 >> 16 | d0 << 16; + word1(d) = d1 >> 16 | d1 << 16; +#else +#undef d0 +#undef d1 +#endif + return d; +} + + static Bigint * +d2b +#ifdef KR_headers + (d, e, bits) double d; int *e, *bits; +#else + (double d, int *e, int *bits) +#endif +{ + Bigint *b; + int de, i, k; + unsigned long *x, y, z; +#ifdef VAX + unsigned long d0, d1; + d0 = word0(d) >> 16 | word0(d) << 16; + d1 = word1(d) >> 16 | word1(d) << 16; +#else +#define d0 word0(d) +#define d1 word1(d) +#endif + +#ifdef Pack_32 + b = Balloc(1); +#else + b = Balloc(2); +#endif + x = b->x; + + z = d0 & Frac_mask; + d0 &= 0x7fffffff; /* clear sign bit, which we ignore */ +#ifdef Sudden_Underflow + de = (int)(d0 >> Exp_shift); +#ifndef IBM + z |= Exp_msk11; +#endif +#else + if (de = (int)(d0 >> Exp_shift)) + z |= Exp_msk1; +#endif +#ifdef Pack_32 + if (y = d1) { + if (k = lo0bits(&y)) { + x[0] = y | z << 32 - k; + z >>= k; + } + else + x[0] = y; + i = b->wds = (x[1] = z) ? 2 : 1; + } else { +#ifdef DEBUG + if (!z) + Bug("Zero passed to d2b"); +#endif + k = lo0bits(&z); + x[0] = z; + i = b->wds = 1; + k += 32; + } +#else + if (y = d1) { + if (k = lo0bits(&y)) + if (k >= 16) { + x[0] = y | z << 32 - k & 0xffff; + x[1] = z >> k - 16 & 0xffff; + x[2] = z >> k; + i = 2; + } else { + x[0] = y & 0xffff; + x[1] = y >> 16 | z << 16 - k & 0xffff; + x[2] = z >> k & 0xffff; + x[3] = z >> k+16; + i = 3; + } + else { + x[0] = y & 0xffff; + x[1] = y >> 16; + x[2] = z & 0xffff; + x[3] = z >> 16; + i = 3; + } + } else { +#ifdef DEBUG + if (!z) + Bug("Zero passed to d2b"); +#endif + k = lo0bits(&z); + if (k >= 16) { + x[0] = z; + i = 0; + } else { + x[0] = z & 0xffff; + x[1] = z >> 16; + i = 1; + } + k += 32; + } + while (!x[i]) + --i; + b->wds = i + 1; +#endif +#ifndef Sudden_Underflow + if (de) { +#endif +#ifdef IBM + *e = (de - Bias - (P-1) << 2) + k; + *bits = 4*P + 8 - k - hi0bits(word0(d) & Frac_mask); +#else + *e = de - Bias - (P-1) + k; + *bits = P - k; +#endif +#ifndef Sudden_Underflow + } else { + *e = de - Bias - (P-1) + 1 + k; +#ifdef Pack_32 + *bits = 32*i - hi0bits(x[i-1]); +#else + *bits = (i+2)*16 - hi0bits(x[i]); +#endif + } +#endif + return b; +} +#undef d0 +#undef d1 + + static double +ratio +#ifdef KR_headers + (a, b) Bigint *a, *b; +#else + (Bigint *a, Bigint *b) +#endif +{ + double da, db; + int k, ka, kb; + + da = b2d(a, &ka); + db = b2d(b, &kb); +#ifdef Pack_32 + k = ka - kb + 32*(a->wds - b->wds); +#else + k = ka - kb + 16*(a->wds - b->wds); +#endif +#ifdef IBM + if (k > 0) { + word0(da) += (k >> 2)*Exp_msk1; + if (k &= 3) + da *= 1 << k; + } else { + k = -k; + word0(db) += (k >> 2)*Exp_msk1; + if (k &= 3) + db *= 1 << k; + } +#else + if (k > 0) + word0(da) += k*Exp_msk1; + else { + k = -k; + word0(db) += k*Exp_msk1; + } +#endif + return da / db; +} + + static double +tens[] = { + 1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, + 1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19, + 1e20, 1e21, 1e22 +#ifdef VAX + , 1e23, 1e24 +#endif + }; + + static double +#ifdef IEEE_Arith +bigtens[] = { 1e16, 1e32, 1e64, 1e128, 1e256 }; +static double tinytens[] = { 1e-16, 1e-32, 1e-64, 1e-128, 1e-256 }; +#define n_bigtens 5 +#else +#ifdef IBM +bigtens[] = { 1e16, 1e32, 1e64 }; +static double tinytens[] = { 1e-16, 1e-32, 1e-64 }; +#define n_bigtens 3 +#else +bigtens[] = { 1e16, 1e32 }; +static double tinytens[] = { 1e-16, 1e-32 }; +#define n_bigtens 2 +#endif +#endif + + double +strtod +#ifdef KR_headers + (s00, se) CONST char *s00; char **se; +#else + (CONST char *s00, char **se) +#endif +{ + int bb2, bb5, bbe, bd2, bd5, bbbits, bs2, c, dsign, + e, e1, esign, i, j, k, nd, nd0, nf, nz, nz0, sign; + CONST char *s, *s0, *s1; + double aadj, aadj1, adj, rv, rv0; + long L; + unsigned long y, z; + Bigint *bb, *bb1, *bd, *bd0, *bs, *delta; + sign = nz0 = nz = 0; + rv = 0.; + for (s = s00;;s++) switch(*s) { + case '-': + sign = 1; + /* no break */ + case '+': + if (*++s) + goto break2; + /* no break */ + case 0: + s = s00; + goto ret; + case '\t': + case '\n': + case '\v': + case '\f': + case '\r': + case ' ': + continue; + default: + goto break2; + } + break2: + if (*s == '0') { + nz0 = 1; + while (*++s == '0') ; + if (!*s) + goto ret; + } + s0 = s; + y = z = 0; + for (nd = nf = 0; (c = *s) >= '0' && c <= '9'; nd++, s++) + if (nd < 9) + y = 10*y + c - '0'; + else if (nd < 16) + z = 10*z + c - '0'; + nd0 = nd; + if (c == '.') { + c = *++s; + if (!nd) { + for (; c == '0'; c = *++s) + nz++; + if (c > '0' && c <= '9') { + s0 = s; + nf += nz; + nz = 0; + goto have_dig; + } + goto dig_done; + } + for (; c >= '0' && c <= '9'; c = *++s) { + have_dig: + nz++; + if (c -= '0') { + nf += nz; + for (i = 1; i < nz; i++) + if (nd++ < 9) + y *= 10; + else if (nd <= DBL_DIG + 1) + z *= 10; + if (nd++ < 9) + y = 10*y + c; + else if (nd <= DBL_DIG + 1) + z = 10*z + c; + nz = 0; + } + } + } + dig_done: + e = 0; + if (c == 'e' || c == 'E') { + if (!nd && !nz && !nz0) { + s = s00; + goto ret; + } + s00 = s; + esign = 0; + switch(c = *++s) { + case '-': + esign = 1; + case '+': + c = *++s; + } + if (c >= '0' && c <= '9') { + while (c == '0') + c = *++s; + if (c > '0' && c <= '9') { + L = c - '0'; + s1 = s; + while ((c = *++s) >= '0' && c <= '9') + L = 10*L + c - '0'; + if (s - s1 > 8 || L > 19999) + /* Avoid confusion from exponents + * so large that e might overflow. + */ + e = 19999; /* safe for 16 bit ints */ + else + e = (int)L; + if (esign) + e = -e; + } else + e = 0; + } else + s = s00; + } + if (!nd) { + if (!nz && !nz0) + s = s00; + goto ret; + } + e1 = e -= nf; + + /* Now we have nd0 digits, starting at s0, followed by a + * decimal point, followed by nd-nd0 digits. The number we're + * after is the integer represented by those digits times + * 10**e */ + + if (!nd0) + nd0 = nd; + k = nd < DBL_DIG + 1 ? nd : DBL_DIG + 1; + rv = y; + if (k > 9) + rv = tens[k - 9] * rv + z; + if (nd <= DBL_DIG +#ifndef RND_PRODQUOT + && FLT_ROUNDS == 1 +#endif + ) { + if (!e) + goto ret; + if (e > 0) { + if (e <= Ten_pmax) { +#ifdef VAX + goto vax_ovfl_check; +#else + /* rv = */ rounded_product(rv, tens[e]); + goto ret; +#endif + } + i = DBL_DIG - nd; + if (e <= Ten_pmax + i) { + /* A fancier test would sometimes let us do + * this for larger i values. + */ + e -= i; + rv *= tens[i]; +#ifdef VAX + /* VAX exponent range is so narrow we must + * worry about overflow here... + */ + vax_ovfl_check: + word0(rv) -= P*Exp_msk1; + /* rv = */ rounded_product(rv, tens[e]); + if ((word0(rv) & Exp_mask) + > Exp_msk1*(DBL_MAX_EXP+Bias-1-P)) + goto ovfl; + word0(rv) += P*Exp_msk1; +#else + /* rv = */ rounded_product(rv, tens[e]); +#endif + goto ret; + } + } +#ifndef Inaccurate_Divide + else if (e >= -Ten_pmax) { + /* rv = */ rounded_quotient(rv, tens[-e]); + goto ret; + } +#endif + } + e1 += nd - k; + + /* Get starting approximation = rv * 10**e1 */ + + if (e1 > 0) { + if (i = e1 & 15) + rv *= tens[i]; + if (e1 &= ~15) { + if (e1 > DBL_MAX_10_EXP) { + ovfl: + errno = ERANGE; +#ifdef __STDC__ + rv = HUGE_VAL; +#else + /* Can't trust HUGE_VAL */ +#ifdef IEEE_Arith + word0(rv) = Exp_mask; + word1(rv) = 0; +#else + word0(rv) = Big0; + word1(rv) = Big1; +#endif +#endif + goto ret; + } + if (e1 >>= 4) { + for (j = 0; e1 > 1; j++, e1 >>= 1) + if (e1 & 1) + rv *= bigtens[j]; + /* The last multiplication could overflow. */ + word0(rv) -= P*Exp_msk1; + rv *= bigtens[j]; + if ((z = word0(rv) & Exp_mask) + > Exp_msk1*(DBL_MAX_EXP+Bias-P)) + goto ovfl; + if (z > Exp_msk1*(DBL_MAX_EXP+Bias-1-P)) { + /* set to largest number */ + /* (Can't trust DBL_MAX) */ + word0(rv) = Big0; + word1(rv) = Big1; + } + else + word0(rv) += P*Exp_msk1; + } + } + } else if (e1 < 0) { + e1 = -e1; + if (i = e1 & 15) + rv /= tens[i]; + if (e1 &= ~15) { + e1 >>= 4; + for (j = 0; e1 > 1; j++, e1 >>= 1) + if (e1 & 1) + rv *= tinytens[j]; + /* The last multiplication could underflow. */ + rv0 = rv; + rv *= tinytens[j]; + if (!rv) { + rv = 2.*rv0; + rv *= tinytens[j]; + if (!rv) { + undfl: + rv = 0.; + errno = ERANGE; + goto ret; + } + word0(rv) = Tiny0; + word1(rv) = Tiny1; + /* The refinement below will clean + * this approximation up. + */ + } + } + } + + /* Now the hard part -- adjusting rv to the correct value.*/ + + /* Put digits into bd: true value = bd * 10^e */ + + bd0 = s2b(s0, nd0, nd, y); + + for (;;) { + bd = Balloc(bd0->k); + Bcopy(bd, bd0); + bb = d2b(rv, &bbe, &bbbits); /* rv = bb * 2^bbe */ + bs = i2b(1); + + if (e >= 0) { + bb2 = bb5 = 0; + bd2 = bd5 = e; + } else { + bb2 = bb5 = -e; + bd2 = bd5 = 0; + } + if (bbe >= 0) + bb2 += bbe; + else + bd2 -= bbe; + bs2 = bb2; +#ifdef Sudden_Underflow +#ifdef IBM + j = 1 + 4*P - 3 - bbbits + ((bbe + bbbits - 1) & 3); +#else + j = P + 1 - bbbits; +#endif +#else + i = bbe + bbbits - 1; /* logb(rv) */ + if (i < Emin) /* denormal */ + j = bbe + (P-Emin); + else + j = P + 1 - bbbits; +#endif + bb2 += j; + bd2 += j; + i = bb2 < bd2 ? bb2 : bd2; + if (i > bs2) + i = bs2; + if (i > 0) { + bb2 -= i; + bd2 -= i; + bs2 -= i; + } + if (bb5 > 0) { + bs = pow5mult(bs, bb5); + bb1 = mult(bs, bb); + Bfree(bb); + bb = bb1; + } + if (bb2 > 0) + bb = lshift(bb, bb2); + if (bd5 > 0) + bd = pow5mult(bd, bd5); + if (bd2 > 0) + bd = lshift(bd, bd2); + if (bs2 > 0) + bs = lshift(bs, bs2); + delta = diff(bb, bd); + dsign = delta->sign; + delta->sign = 0; + i = cmp(delta, bs); + if (i < 0) { + /* Error is less than half an ulp -- check for + * special case of mantissa a power of two. + */ + if (dsign || word1(rv) || word0(rv) & Bndry_mask) + break; + delta = lshift(delta,Log2P); + if (cmp(delta, bs) > 0) + goto drop_down; + break; + } + if (i == 0) { + /* exactly half-way between */ + if (dsign) { + if ((word0(rv) & Bndry_mask1) == Bndry_mask1 + && word1(rv) == 0xffffffff) { + /*boundary case -- increment exponent*/ + word0(rv) = (word0(rv) & Exp_mask) + + Exp_msk1 +#ifdef IBM + | Exp_msk1 >> 4 +#endif + ; + word1(rv) = 0; + break; + } + } else if (!(word0(rv) & Bndry_mask) && !word1(rv)) { + drop_down: + /* boundary case -- decrement exponent */ +#ifdef Sudden_Underflow + L = word0(rv) & Exp_mask; +#ifdef IBM + if (L < Exp_msk1) +#else + if (L <= Exp_msk1) +#endif + goto undfl; + L -= Exp_msk1; +#else + L = (word0(rv) & Exp_mask) - Exp_msk1; +#endif + word0(rv) = L | Bndry_mask1; + word1(rv) = 0xffffffff; +#ifdef IBM + goto cont; +#else + break; +#endif + } +#ifndef ROUND_BIASED + if (!(word1(rv) & LSB)) + break; +#endif + if (dsign) + rv += ulp(rv); +#ifndef ROUND_BIASED + else { + rv -= ulp(rv); +#ifndef Sudden_Underflow + if (!rv) + goto undfl; +#endif + } +#endif + break; + } + if ((aadj = ratio(delta, bs)) <= 2.) { + if (dsign) + aadj = aadj1 = 1.; + else if (word1(rv) || word0(rv) & Bndry_mask) { +#ifndef Sudden_Underflow + if (word1(rv) == Tiny1 && !word0(rv)) + goto undfl; +#endif + aadj = 1.; + aadj1 = -1.; + } else { + /* special case -- power of FLT_RADIX to be */ + /* rounded down... */ + + if (aadj < 2./FLT_RADIX) + aadj = 1./FLT_RADIX; + else + aadj *= 0.5; + aadj1 = -aadj; + } + } else { + aadj *= 0.5; + aadj1 = dsign ? aadj : -aadj; +#ifdef Check_FLT_ROUNDS + switch(FLT_ROUNDS) { + case 2: /* towards +infinity */ + aadj1 -= 0.5; + break; + case 0: /* towards 0 */ + case 3: /* towards -infinity */ + aadj1 += 0.5; + } +#else + if (FLT_ROUNDS == 0) + aadj1 += 0.5; +#endif + } + y = word0(rv) & Exp_mask; + + /* Check for overflow */ + + if (y == Exp_msk1*(DBL_MAX_EXP+Bias-1)) { + rv0 = rv; + word0(rv) -= P*Exp_msk1; + adj = aadj1 * ulp(rv); + rv += adj; + if ((word0(rv) & Exp_mask) >= + Exp_msk1*(DBL_MAX_EXP+Bias-P)) { + if (word0(rv0) == Big0 && word1(rv0) == Big1) + goto ovfl; + word0(rv) = Big0; + word1(rv) = Big1; + goto cont; + } else + word0(rv) += P*Exp_msk1; + } else { +#ifdef Sudden_Underflow + if ((word0(rv) & Exp_mask) <= P*Exp_msk1) { + rv0 = rv; + word0(rv) += P*Exp_msk1; + adj = aadj1 * ulp(rv); + rv += adj; +#ifdef IBM + if ((word0(rv) & Exp_mask) < P*Exp_msk1) +#else + if ((word0(rv) & Exp_mask) <= P*Exp_msk1) +#endif + { + if (word0(rv0) == Tiny0 + && word1(rv0) == Tiny1) + goto undfl; + word0(rv) = Tiny0; + word1(rv) = Tiny1; + goto cont; + } else + word0(rv) -= P*Exp_msk1; + } else { + adj = aadj1 * ulp(rv); + rv += adj; + } +#else + /* Compute adj so that the IEEE rounding rules will + * correctly round rv + adj in some half-way cases. + * If rv * ulp(rv) is denormalized (i.e., + * y <= (P-1)*Exp_msk1), we must adjust aadj to avoid + * trouble from bits lost to denormalization; + * example: 1.2e-307 . + */ + if (y <= (P-1)*Exp_msk1 && aadj >= 1.) { + aadj1 = (double)(int)(aadj + 0.5); + if (!dsign) + aadj1 = -aadj1; + } + adj = aadj1 * ulp(rv); + rv += adj; +#endif + } + z = word0(rv) & Exp_mask; + if (y == z) { + /* Can we stop now? */ + L = aadj; + aadj -= L; + /* The tolerances below are conservative. */ + if (dsign || word1(rv) || word0(rv) & Bndry_mask) { + if (aadj < .4999999 || aadj > .5000001) + break; + } else if (aadj < .4999999/FLT_RADIX) + break; + } + cont: + Bfree(bb); + Bfree(bd); + Bfree(bs); + Bfree(delta); + } + Bfree(bb); + Bfree(bd); + Bfree(bs); + Bfree(bd0); + Bfree(delta); + ret: + if (se) + *se = (char *)s; + return sign ? -rv : rv; +} + + static int +quorem +#ifdef KR_headers + (b, S) Bigint *b, *S; +#else + (Bigint *b, Bigint *S) +#endif +{ + int n; + long borrow, y; + unsigned long carry, q, ys; + unsigned long *bx, *bxe, *sx, *sxe; +#ifdef Pack_32 + long z; + unsigned long si, zs; +#endif + + n = S->wds; +#ifdef DEBUG + /*debug*/ if (b->wds > n) + /*debug*/ Bug("oversize b in quorem"); +#endif + if (b->wds < n) + return 0; + sx = S->x; + sxe = sx + --n; + bx = b->x; + bxe = bx + n; + q = *bxe / (*sxe + 1); /* ensure q <= true quotient */ +#ifdef DEBUG + /*debug*/ if (q > 9) + /*debug*/ Bug("oversized quotient in quorem"); +#endif + if (q) { + borrow = 0; + carry = 0; + do { +#ifdef Pack_32 + si = *sx++; + ys = (si & 0xffff) * q + carry; + zs = (si >> 16) * q + (ys >> 16); + carry = zs >> 16; + y = (*bx & 0xffff) - (ys & 0xffff) + borrow; + borrow = y >> 16; + Sign_Extend(borrow, y); + z = (*bx >> 16) - (zs & 0xffff) + borrow; + borrow = z >> 16; + Sign_Extend(borrow, z); + Storeinc(bx, z, y); +#else + ys = *sx++ * q + carry; + carry = ys >> 16; + y = *bx - (ys & 0xffff) + borrow; + borrow = y >> 16; + Sign_Extend(borrow, y); + *bx++ = y & 0xffff; +#endif + } while (sx <= sxe); + if (!*bxe) { + bx = b->x; + while (--bxe > bx && !*bxe) + --n; + b->wds = n; + } + } + if (cmp(b, S) >= 0) { + q++; + borrow = 0; + carry = 0; + bx = b->x; + sx = S->x; + do { +#ifdef Pack_32 + si = *sx++; + ys = (si & 0xffff) + carry; + zs = (si >> 16) + (ys >> 16); + carry = zs >> 16; + y = (*bx & 0xffff) - (ys & 0xffff) + borrow; + borrow = y >> 16; + Sign_Extend(borrow, y); + z = (*bx >> 16) - (zs & 0xffff) + borrow; + borrow = z >> 16; + Sign_Extend(borrow, z); + Storeinc(bx, z, y); +#else + ys = *sx++ + carry; + carry = ys >> 16; + y = *bx - (ys & 0xffff) + borrow; + borrow = y >> 16; + Sign_Extend(borrow, y); + *bx++ = y & 0xffff; +#endif + } while (sx <= sxe); + bx = b->x; + bxe = bx + n; + if (!*bxe) { + while (--bxe > bx && !*bxe) + --n; + b->wds = n; + } + } + return q; +} + +/* dtoa for IEEE arithmetic (dmg): convert double to ASCII string. + * + * Inspired by "How to Print Floating-Point Numbers Accurately" by + * Guy L. Steele, Jr. and Jon L. White [Proc. ACM SIGPLAN '90, pp. 92-101]. + * + * Modifications: + * 1. Rather than iterating, we use a simple numeric overestimate + * to determine k = floor(log10(d)). We scale relevant + * quantities using O(log2(k)) rather than O(k) multiplications. + * 2. For some modes > 2 (corresponding to ecvt and fcvt), we don't + * try to generate digits strictly left to right. Instead, we + * compute with fewer bits and propagate the carry if necessary + * when rounding the final digit up. This is often faster. + * 3. Under the assumption that input will be rounded nearest, + * mode 0 renders 1e23 as 1e23 rather than 9.999999999999999e22. + * That is, we allow equality in stopping tests when the + * round-nearest rule will give the same floating-point value + * as would satisfaction of the stopping test with strict + * inequality. + * 4. We remove common factors of powers of 2 from relevant + * quantities. + * 5. When converting floating-point integers less than 1e16, + * we use floating-point arithmetic rather than resorting + * to multiple-precision integers. + * 6. When asked to produce fewer than 15 digits, we first try + * to get by with floating-point arithmetic; we resort to + * multiple-precision integer arithmetic only if we cannot + * guarantee that the floating-point calculation has given + * the correctly rounded result. For k requested digits and + * "uniformly" distributed input, the probability is + * something like 10^(k-15) that we must resort to the long + * calculation. + */ + +char * +__dtoa +#ifdef KR_headers + (d, mode, ndigits, decpt, sign, rve) + double d; int mode, ndigits, *decpt, *sign; char **rve; +#else + (double d, int mode, int ndigits, int *decpt, int *sign, char **rve) +#endif +{ + /* Arguments ndigits, decpt, sign are similar to those + of ecvt and fcvt; trailing zeros are suppressed from + the returned string. If not null, *rve is set to point + to the end of the return value. If d is +-Infinity or NaN, + then *decpt is set to 9999. + + mode: + 0 ==> shortest string that yields d when read in + and rounded to nearest. + 1 ==> like 0, but with Steele & White stopping rule; + e.g. with IEEE P754 arithmetic , mode 0 gives + 1e23 whereas mode 1 gives 9.999999999999999e22. + 2 ==> max(1,ndigits) significant digits. This gives a + return value similar to that of ecvt, except + that trailing zeros are suppressed. + 3 ==> through ndigits past the decimal point. This + gives a return value similar to that from fcvt, + except that trailing zeros are suppressed, and + ndigits can be negative. + 4-9 should give the same return values as 2-3, i.e., + 4 <= mode <= 9 ==> same return as mode + 2 + (mode & 1). These modes are mainly for + debugging; often they run slower but sometimes + faster than modes 2-3. + 4,5,8,9 ==> left-to-right digit generation. + 6-9 ==> don't try fast floating-point estimate + (if applicable). + + Values of mode other than 0-9 are treated as mode 0. + + Sufficient space is allocated to the return value + to hold the suppressed trailing zeros. + */ + + int bbits, b2, b5, be, dig, i, ieps, ilim, ilim0, ilim1, + j, j1, k, k0, k_check, leftright, m2, m5, s2, s5, + spec_case, try_quick; + long L; +#ifndef Sudden_Underflow + int denorm; + unsigned long x; +#endif + Bigint *b, *b1, *delta, *mlo, *mhi, *S; + double d2, ds, eps; + char *s, *s0; + static Bigint *result; + static int result_k; + + if (result) { + result->k = result_k; + result->maxwds = 1 << result_k; + Bfree(result); + result = 0; + } + + if (word0(d) & Sign_bit) { + /* set sign for everything, including 0's and NaNs */ + *sign = 1; + word0(d) &= ~Sign_bit; /* clear sign bit */ + } + else + *sign = 0; + +#if defined(IEEE_Arith) + defined(VAX) +#ifdef IEEE_Arith + if ((word0(d) & Exp_mask) == Exp_mask) +#else + if (word0(d) == 0x8000) +#endif + { + /* Infinity or NaN */ + *decpt = 9999; + s = +#ifdef IEEE_Arith + !word1(d) && !(word0(d) & 0xfffff) ? "Infinity" : +#endif + "NaN"; + if (rve) + *rve = +#ifdef IEEE_Arith + s[3] ? s + 8 : +#endif + s + 3; + return s; + } +#endif +#ifdef IBM + d += 0; /* normalize */ +#endif + if (!d) { + *decpt = 1; + s = "0"; + if (rve) + *rve = s + 1; + return s; + } + + b = d2b(d, &be, &bbits); +#ifdef Sudden_Underflow + i = (int)(word0(d) >> Exp_shift1 & (Exp_mask>>Exp_shift1)); +#else + if (i = (int)(word0(d) >> Exp_shift1 & (Exp_mask>>Exp_shift1))) { +#endif + d2 = d; + word0(d2) &= Frac_mask1; + word0(d2) |= Exp_11; +#ifdef IBM + if (j = 11 - hi0bits(word0(d2) & Frac_mask)) + d2 /= 1 << j; +#endif + + /* log(x) ~=~ log(1.5) + (x-1.5)/1.5 + * log10(x) = log(x) / log(10) + * ~=~ log(1.5)/log(10) + (x-1.5)/(1.5*log(10)) + * log10(d) = (i-Bias)*log(2)/log(10) + log10(d2) + * + * This suggests computing an approximation k to log10(d) by + * + * k = (i - Bias)*0.301029995663981 + * + ( (d2-1.5)*0.289529654602168 + 0.176091259055681 ); + * + * We want k to be too large rather than too small. + * The error in the first-order Taylor series approximation + * is in our favor, so we just round up the constant enough + * to compensate for any error in the multiplication of + * (i - Bias) by 0.301029995663981; since |i - Bias| <= 1077, + * and 1077 * 0.30103 * 2^-52 ~=~ 7.2e-14, + * adding 1e-13 to the constant term more than suffices. + * Hence we adjust the constant term to 0.1760912590558. + * (We could get a more accurate k by invoking log10, + * but this is probably not worthwhile.) + */ + + i -= Bias; +#ifdef IBM + i <<= 2; + i += j; +#endif +#ifndef Sudden_Underflow + denorm = 0; + } else { + /* d is denormalized */ + + i = bbits + be + (Bias + (P-1) - 1); + x = i > 32 ? word0(d) << 64 - i | word1(d) >> i - 32 + : word1(d) << 32 - i; + d2 = x; + word0(d2) -= 31*Exp_msk1; /* adjust exponent */ + i -= (Bias + (P-1) - 1) + 1; + denorm = 1; + } +#endif + ds = (d2-1.5)*0.289529654602168 + 0.1760912590558 + i*0.301029995663981; + k = (int)ds; + if (ds < 0. && ds != k) + k--; /* want k = floor(ds) */ + k_check = 1; + if (k >= 0 && k <= Ten_pmax) { + if (d < tens[k]) + k--; + k_check = 0; + } + j = bbits - i - 1; + if (j >= 0) { + b2 = 0; + s2 = j; + } else { + b2 = -j; + s2 = 0; + } + if (k >= 0) { + b5 = 0; + s5 = k; + s2 += k; + } else { + b2 -= k; + b5 = -k; + s5 = 0; + } + if (mode < 0 || mode > 9) + mode = 0; + try_quick = 1; + if (mode > 5) { + mode -= 4; + try_quick = 0; + } + leftright = 1; + switch(mode) { + case 0: + case 1: + ilim = ilim1 = -1; + i = 18; + ndigits = 0; + break; + case 2: + leftright = 0; + /* no break */ + case 4: + if (ndigits <= 0) + ndigits = 1; + ilim = ilim1 = i = ndigits; + break; + case 3: + leftright = 0; + /* no break */ + case 5: + i = ndigits + k + 1; + ilim = i; + ilim1 = i - 1; + if (i <= 0) + i = 1; + } + j = sizeof(unsigned long); + for (result_k = 0; sizeof(Bigint) - sizeof(unsigned long) + j < i; + j <<= 1) result_k++; + result = Balloc(result_k); + s = s0 = (char *)result; + + if (ilim >= 0 && ilim <= Quick_max && try_quick) { + + /* Try to get by with floating-point arithmetic. */ + + i = 0; + d2 = d; + k0 = k; + ilim0 = ilim; + ieps = 2; /* conservative */ + if (k > 0) { + ds = tens[k&0xf]; + j = k >> 4; + if (j & Bletch) { + /* prevent overflows */ + j &= Bletch - 1; + d /= bigtens[n_bigtens-1]; + ieps++; + } + for (; j; j >>= 1, i++) + if (j & 1) { + ieps++; + ds *= bigtens[i]; + } + d /= ds; + } else if (j1 = -k) { + d *= tens[j1 & 0xf]; + for (j = j1 >> 4; j; j >>= 1, i++) + if (j & 1) { + ieps++; + d *= bigtens[i]; + } + } + if (k_check && d < 1. && ilim > 0) { + if (ilim1 <= 0) + goto fast_failed; + ilim = ilim1; + k--; + d *= 10.; + ieps++; + } + eps = ieps*d + 7.; + word0(eps) -= (P-1)*Exp_msk1; + if (ilim == 0) { + S = mhi = 0; + d -= 5.; + if (d > eps) + goto one_digit; + if (d < -eps) + goto no_digits; + goto fast_failed; + } +#ifndef No_leftright + if (leftright) { + /* Use Steele & White method of only + * generating digits needed. + */ + eps = 0.5/tens[ilim-1] - eps; + for (i = 0;;) { + L = d; + d -= L; + *s++ = '0' + (int)L; + if (d < eps) + goto ret1; + if (1. - d < eps) + goto bump_up; + if (++i >= ilim) + break; + eps *= 10.; + d *= 10.; + } + } else { +#endif + /* Generate ilim digits, then fix them up. */ + eps *= tens[ilim-1]; + for (i = 1;; i++, d *= 10.) { + L = d; + d -= L; + *s++ = '0' + (int)L; + if (i == ilim) { + if (d > 0.5 + eps) + goto bump_up; + else if (d < 0.5 - eps) { + while (*--s == '0'); + s++; + goto ret1; + } + break; + } + } +#ifndef No_leftright + } +#endif + fast_failed: + s = s0; + d = d2; + k = k0; + ilim = ilim0; + } + + /* Do we have a "small" integer? */ + + if (be >= 0 && k <= Int_max) { + /* Yes. */ + ds = tens[k]; + if (ndigits < 0 && ilim <= 0) { + S = mhi = 0; + if (ilim < 0 || d <= 5*ds) + goto no_digits; + goto one_digit; + } + for (i = 1;; i++) { + L = d / ds; + d -= L*ds; +#ifdef Check_FLT_ROUNDS + /* If FLT_ROUNDS == 2, L will usually be high by 1 */ + if (d < 0) { + L--; + d += ds; + } +#endif + *s++ = '0' + (int)L; + if (i == ilim) { + d += d; + if (d > ds || d == ds && L & 1) { + bump_up: + while (*--s == '9') + if (s == s0) { + k++; + *s = '0'; + break; + } + ++*s++; + } + break; + } + if (!(d *= 10.)) + break; + } + goto ret1; + } + + m2 = b2; + m5 = b5; + mhi = mlo = 0; + if (leftright) { + if (mode < 2) { + i = +#ifndef Sudden_Underflow + denorm ? be + (Bias + (P-1) - 1 + 1) : +#endif +#ifdef IBM + 1 + 4*P - 3 - bbits + ((bbits + be - 1) & 3); +#else + 1 + P - bbits; +#endif + } else { + j = ilim - 1; + if (m5 >= j) + m5 -= j; + else { + s5 += j -= m5; + b5 += j; + m5 = 0; + } + if ((i = ilim) < 0) { + m2 -= i; + i = 0; + } + } + b2 += i; + s2 += i; + mhi = i2b(1); + } + if (m2 > 0 && s2 > 0) { + i = m2 < s2 ? m2 : s2; + b2 -= i; + m2 -= i; + s2 -= i; + } + if (b5 > 0) { + if (leftright) { + if (m5 > 0) { + mhi = pow5mult(mhi, m5); + b1 = mult(mhi, b); + Bfree(b); + b = b1; + } + if (j = b5 - m5) + b = pow5mult(b, j); + } else + b = pow5mult(b, b5); + } + S = i2b(1); + if (s5 > 0) + S = pow5mult(S, s5); + + /* Check for special case that d is a normalized power of 2. */ + + if (mode < 2) { + if (!word1(d) && !(word0(d) & Bndry_mask) +#ifndef Sudden_Underflow + && word0(d) & Exp_mask +#endif + ) { + /* The special case */ + b2 += Log2P; + s2 += Log2P; + spec_case = 1; + } else + spec_case = 0; + } + + /* Arrange for convenient computation of quotients: + * shift left if necessary so divisor has 4 leading 0 bits. + * + * Perhaps we should just compute leading 28 bits of S once + * and for all and pass them and a shift to quorem, so it + * can do shifts and ors to compute the numerator for q. + */ +#ifdef Pack_32 + if (i = ((s5 ? 32 - hi0bits(S->x[S->wds-1]) : 1) + s2) & 0x1f) + i = 32 - i; +#else + if (i = ((s5 ? 32 - hi0bits(S->x[S->wds-1]) : 1) + s2) & 0xf) + i = 16 - i; +#endif + if (i > 4) { + i -= 4; + b2 += i; + m2 += i; + s2 += i; + } else if (i < 4) { + i += 28; + b2 += i; + m2 += i; + s2 += i; + } + if (b2 > 0) + b = lshift(b, b2); + if (s2 > 0) + S = lshift(S, s2); + if (k_check) { + if (cmp(b,S) < 0) { + k--; + b = multadd(b, 10, 0); /* we botched the k estimate */ + if (leftright) + mhi = multadd(mhi, 10, 0); + ilim = ilim1; + } + } + if (ilim <= 0 && mode > 2) { + if (ilim < 0 || cmp(b,S = multadd(S,5,0)) <= 0) { + /* no digits, fcvt style */ + no_digits: + k = -1 - ndigits; + goto ret; + } + one_digit: + *s++ = '1'; + k++; + goto ret; + } + if (leftright) { + if (m2 > 0) + mhi = lshift(mhi, m2); + + /* Compute mlo -- check for special case + * that d is a normalized power of 2. + */ + + mlo = mhi; + if (spec_case) { + mhi = Balloc(mhi->k); + Bcopy(mhi, mlo); + mhi = lshift(mhi, Log2P); + } + + for (i = 1;;i++) { + dig = quorem(b,S) + '0'; + /* Do we yet have the shortest decimal string + * that will round to d? + */ + j = cmp(b, mlo); + delta = diff(S, mhi); + j1 = delta->sign ? 1 : cmp(b, delta); + Bfree(delta); +#ifndef ROUND_BIASED + if (j1 == 0 && !mode && !(word1(d) & 1)) { + if (dig == '9') + goto round_9_up; + if (j > 0) + dig++; + *s++ = dig; + goto ret; + } +#endif + if (j < 0 || j == 0 && !mode +#ifndef ROUND_BIASED + && !(word1(d) & 1) +#endif + ) { + if (j1 > 0) { + b = lshift(b, 1); + j1 = cmp(b, S); + if ((j1 > 0 || j1 == 0 && dig & 1) + && dig++ == '9') + goto round_9_up; + } + *s++ = dig; + goto ret; + } + if (j1 > 0) { + if (dig == '9') { /* possible if i == 1 */ + round_9_up: + *s++ = '9'; + goto roundoff; + } + *s++ = dig + 1; + goto ret; + } + *s++ = dig; + if (i == ilim) + break; + b = multadd(b, 10, 0); + if (mlo == mhi) + mlo = mhi = multadd(mhi, 10, 0); + else { + mlo = multadd(mlo, 10, 0); + mhi = multadd(mhi, 10, 0); + } + } + } else + for (i = 1;; i++) { + *s++ = dig = quorem(b,S) + '0'; + if (i >= ilim) + break; + b = multadd(b, 10, 0); + } + + /* Round off last digit */ + + b = lshift(b, 1); + j = cmp(b, S); + if (j > 0 || j == 0 && dig & 1) { + roundoff: + while (*--s == '9') + if (s == s0) { + k++; + *s++ = '1'; + goto ret; + } + ++*s++; + } else { + while (*--s == '0'); + s++; + } + ret: + Bfree(S); + if (mhi) { + if (mlo && mlo != mhi) + Bfree(mlo); + Bfree(mhi); + } + ret1: + Bfree(b); + if (s == s0) { /* don't return empty string */ + *s++ = '0'; + k = 0; + } + *s = 0; + *decpt = k + 1; + if (rve) + *rve = s; + return s0; + } +#ifdef __cplusplus +} +#endif diff --git a/lib/libc/stdlib/strtol.3 b/lib/libc/stdlib/strtol.3 new file mode 100644 index 000000000000..570ac1bfee35 --- /dev/null +++ b/lib/libc/stdlib/strtol.3 @@ -0,0 +1,153 @@ +.\" Copyright (c) 1990, 1991 The Regents of the University of California. +.\" All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" Chris Torek and the American National Standards Committee X3, +.\" on Information Processing Systems. +.\" +.\" 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 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 by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)strtol.3 5.3 (Berkeley) 6/29/91 +.\" +.Dd June 29, 1991 +.Dt STRTOL 3 +.Os +.Sh NAME +.Nm strtol +.Nd convert string value to a long integer +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Fd #include <limits.h> +.Ft long +.Fn strtol "char *nptr" "char **endptr" "int base" +.Sh DESCRIPTION +The +.Fn strtol +function +converts the string in +.Fa nptr +to a +.Em long +value according to the given +.Fa base , +which must be between 2 and 36 inclusive, +or be the special value 0. +.Pp +The string may begin with an arbitrary amount of white space +(as determined by +.Xr isspace 3 ) +followed by a single optional +.Ql + +or +.Ql - +sign. +If +.Fa base +is zero or 16, +the string may then include a +.Ql 0x +prefix, +and the number will be read in base 16; otherwise, a zero +.Fa base +is taken as 10 (decimal) unless the next character is +.Ql 0 , +in which case it is taken as 8 (octal). +.Pp +The remainder of the string is converted to a +.Em long +value in the obvious manner, +stopping at the first character which is not a valid digit +in the given base. +(In bases above 10, the letter +.Ql A +in either upper or lower case +represents 10, +.Ql B +represents 11, and so forth, with +.Ql Z +representing 35.) +.Pp +If +.Fa endptr +is non nil, +.Fn strtol +stores the address of the first invalid character in +.Fa *endptr . +If there were no digits at all, however, +.Fn strtol +stores the original value of +.Fa nptr +in +.Fa *endptr . +(Thus, if +.Fa *nptr +is not +.Ql \e0 +but +.Fa **endptr +is +.Ql \e0 +on return, the entire string was valid.) +.Sh RETURN VALUES +The +.Fn strtol +function +returns the result of the conversion, +unless the value would underflow or overflow. +If an underflow occurs, +.Fn strtol +returns +.Dv LONG_MIN . +If an overflow occurs, +.Fn strtol +returns +.Dv LONG_MAX . +In both cases, +.Va errno +is set to +.Er ERANGE . +.Sh ERRORS +.Bl -tag -width [ERANGE] +.It Bq Er ERANGE +The given string was out of range; the value converted has been clamped. +.El +.Sh SEE ALSO +.Xr atof 3 , +.Xr atoi 3 , +.Xr atol 3 , +.Xr strtod 3 , +.Xr strtoul 3 +.Sh STANDARDS +The +.Fn strtol +function +conforms to +.St -ansiC . +.Sh BUGS +Ignores the current locale. diff --git a/lib/libc/stdlib/strtol.c b/lib/libc/stdlib/strtol.c new file mode 100644 index 000000000000..000d87647af6 --- /dev/null +++ b/lib/libc/stdlib/strtol.c @@ -0,0 +1,129 @@ +/*- + * Copyright (c) 1990 The Regents of the University of California. + * 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 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 by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)strtol.c 5.4 (Berkeley) 2/23/91"; +#endif /* LIBC_SCCS and not lint */ + +#include <limits.h> +#include <ctype.h> +#include <errno.h> +#include <stdlib.h> + + +/* + * Convert a string to a long integer. + * + * Ignores `locale' stuff. Assumes that the upper and lower case + * alphabets and digits are each contiguous. + */ +long +strtol(nptr, endptr, base) + const char *nptr; + char **endptr; + register int base; +{ + register const char *s = nptr; + register unsigned long acc; + register int c; + register unsigned long cutoff; + register int neg = 0, any, cutlim; + + /* + * Skip white space and pick up leading +/- sign if any. + * If base is 0, allow 0x for hex and 0 for octal, else + * assume decimal; if base is already 16, allow 0x. + */ + do { + c = *s++; + } while (isspace(c)); + if (c == '-') { + neg = 1; + c = *s++; + } else if (c == '+') + c = *s++; + if ((base == 0 || base == 16) && + c == '0' && (*s == 'x' || *s == 'X')) { + c = s[1]; + s += 2; + base = 16; + } + if (base == 0) + base = c == '0' ? 8 : 10; + + /* + * Compute the cutoff value between legal numbers and illegal + * numbers. That is the largest legal value, divided by the + * base. An input number that is greater than this value, if + * followed by a legal input character, is too big. One that + * is equal to this value may be valid or not; the limit + * between valid and invalid numbers is then based on the last + * digit. For instance, if the range for longs is + * [-2147483648..2147483647] and the input base is 10, + * cutoff will be set to 214748364 and cutlim to either + * 7 (neg==0) or 8 (neg==1), meaning that if we have accumulated + * a value > 214748364, or equal but the next digit is > 7 (or 8), + * the number is too big, and we will return a range error. + * + * Set any if any `digits' consumed; make it negative to indicate + * overflow. + */ + cutoff = neg ? -(unsigned long)LONG_MIN : LONG_MAX; + cutlim = cutoff % (unsigned long)base; + cutoff /= (unsigned long)base; + for (acc = 0, any = 0;; c = *s++) { + if (isdigit(c)) + c -= '0'; + else if (isalpha(c)) + c -= isupper(c) ? 'A' - 10 : 'a' - 10; + else + break; + if (c >= base) + break; + if (any < 0 || acc > cutoff || acc == cutoff && c > cutlim) + any = -1; + else { + any = 1; + acc *= base; + acc += c; + } + } + if (any < 0) { + acc = neg ? LONG_MIN : LONG_MAX; + errno = ERANGE; + } else if (neg) + acc = -acc; + if (endptr != 0) + *endptr = any ? s - 1 : (char *)nptr; + return (acc); +} diff --git a/lib/libc/stdlib/strtoul.3 b/lib/libc/stdlib/strtoul.3 new file mode 100644 index 000000000000..696c63f936b7 --- /dev/null +++ b/lib/libc/stdlib/strtoul.3 @@ -0,0 +1,147 @@ +.\" Copyright (c) 1990, 1991 The Regents of the University of California. +.\" All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" Chris Torek and the American National Standards Committee X3, +.\" on Information Processing Systems. +.\" +.\" 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 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 by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)strtoul.3 5.3 (Berkeley) 6/29/91 +.\" +.Dd June 29, 1991 +.Dt STRTOUL 3 +.Os +.Sh NAME +.Nm strtoul +.Nd convert a string to an unsigned long integer +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Fd #include <limits.h> +.Fn strtoul "const char *nptr" "char **endptr" "int base" +.Sh DESCRIPTION +The +.Fn strtoul +function +converts the string in +.Fa nptr +to an +.Em unsigned long +value according to the given +.Fa base , +which must be between 2 and 36 inclusive, +or be the special value 0. +.Pp +The string may begin with an arbitrary amount of white space +(as determined by +.Xr isspace 3 ) +followed by a single optional +.Ql + +or +.Ql - +sign. +If +.Fa base +is zero or 16, +the string may then include a +.Ql 0x +prefix, +and the number will be read in base 16; otherwise, a zero +.Fa base +is taken as 10 (decimal) unless the next character is +.Ql 0 , +in which case it is taken as 8 (octal). +.Pp +The remainder of the string is converted to an +.Em unsigned long +value in the obvious manner, +stopping at the end of the string +or at the first character that does not produce a valid digit +in the given base. +(In bases above 10, the letter +.Ql A +in either upper or lower case +represents 10, +.Ql B +represents 11, and so forth, with +.Ql Z +representing 35.) +.Pp +If +.Fa endptr +is non nil, +.Fn strtoul +stores the address of the first invalid character in +.Fa *endptr . +If there were no digits at all, however, +.Fn strtoul +stores the original value of +.Fa nptr +in +.Fa *endptr . +(Thus, if +.Fa *nptr +is not +.Ql \e0 +but +.Fa **endptr +is +.Ql \e0 +on return, the entire string was valid.) +.Sh RETURN VALUES +The +.Fn strtoul +function +returns either the result of the conversion +or, if there was a leading minus sign, +the negation of the result of the conversion, +unless the original (non-negated) value would overflow; +in the latter case, +.Fn strtoul +returns +.Dv ULONG_MAX +and sets the global variable +.Va errno +to +.Er ERANGE . +.Sh ERRORS +.Bl -tag -width [ERANGE] +.It Bq Er ERANGE +The given string was out of range; the value converted has been clamped. +.El +.Sh SEE ALSO +.Xr strtol 3 +.Sh STANDARDS +The +.Fn strtoul +function +conforms to +.St -ansiC . +.Sh BUGS +Ignores the current locale. diff --git a/lib/libc/stdlib/strtoul.c b/lib/libc/stdlib/strtoul.c new file mode 100644 index 000000000000..ed8c1080ba6e --- /dev/null +++ b/lib/libc/stdlib/strtoul.c @@ -0,0 +1,107 @@ +/* + * Copyright (c) 1990 Regents of the University of California. + * 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 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 by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)strtoul.c 5.3 (Berkeley) 2/23/91"; +#endif /* LIBC_SCCS and not lint */ + +#include <limits.h> +#include <ctype.h> +#include <errno.h> +#include <stdlib.h> + +/* + * Convert a string to an unsigned long integer. + * + * Ignores `locale' stuff. Assumes that the upper and lower case + * alphabets and digits are each contiguous. + */ +unsigned long +strtoul(nptr, endptr, base) + const char *nptr; + char **endptr; + register int base; +{ + register const char *s = nptr; + register unsigned long acc; + register int c; + register unsigned long cutoff; + register int neg = 0, any, cutlim; + + /* + * See strtol for comments as to the logic used. + */ + do { + c = *s++; + } while (isspace(c)); + if (c == '-') { + neg = 1; + c = *s++; + } else if (c == '+') + c = *s++; + if ((base == 0 || base == 16) && + c == '0' && (*s == 'x' || *s == 'X')) { + c = s[1]; + s += 2; + base = 16; + } + if (base == 0) + base = c == '0' ? 8 : 10; + cutoff = (unsigned long)ULONG_MAX / (unsigned long)base; + cutlim = (unsigned long)ULONG_MAX % (unsigned long)base; + for (acc = 0, any = 0;; c = *s++) { + if (isdigit(c)) + c -= '0'; + else if (isalpha(c)) + c -= isupper(c) ? 'A' - 10 : 'a' - 10; + else + break; + if (c >= base) + break; + if (any < 0 || acc > cutoff || acc == cutoff && c > cutlim) + any = -1; + else { + any = 1; + acc *= base; + acc += c; + } + } + if (any < 0) { + acc = ULONG_MAX; + errno = ERANGE; + } else if (neg) + acc = -acc; + if (endptr != 0) + *endptr = any ? s - 1 : (char *)nptr; + return (acc); +} diff --git a/lib/libc/stdlib/system.3 b/lib/libc/stdlib/system.3 new file mode 100644 index 000000000000..78c927cebcb1 --- /dev/null +++ b/lib/libc/stdlib/system.3 @@ -0,0 +1,93 @@ +.\" Copyright (c) 1990, 1991 The Regents of the University of California. +.\" All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" the American National Standards Committee X3, on Information +.\" Processing Systems. +.\" +.\" 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 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 by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)system.3 6.5 (Berkeley) 6/29/91 +.\" +.Dd June 29, 1991 +.Dt SYSTEM 3 +.Os +.Sh NAME +.Nm system +.Nd pass a command to the shell +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft int +.Fn system "const char *string" +.Sh DESCRIPTION +The +.Fn system +function +hands the argument +.Fa string +to the command interpreter +.Xr sh 1 . +The calling process waits for the shell +to finish executing the command, +ignoring +.Dv SIGINT +and +.Dv SIGQUIT , +and blocking +.Dv SIGCHLD . +.Pp +If +.Fa string +is a +.Dv NULL +pointer, +.Fn system +will return non-zero if the command interpreter +.Xr sh 1 +is available, and zero if it is not. +.Pp +The +.Fn system +function +returns the exit status of the shell, or \-1 if the +.Xr wait 3 +for the shell failed. +A return value of 127 means the execution of the shell +failed. +.Sh SEE ALSO +.Xr sh 1 , +.Xr execve 2 , +.Xr wait 2 , +.Xr popen 3 +.Sh STANDARDS +The +.Fn system +function +conforms to +.St -ansiC . diff --git a/lib/libc/stdlib/system.c b/lib/libc/stdlib/system.c new file mode 100644 index 000000000000..f8c3a2352d8d --- /dev/null +++ b/lib/libc/stdlib/system.c @@ -0,0 +1,76 @@ +/* + * Copyright (c) 1988 The Regents of the University of California. + * 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 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 by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)system.c 5.10 (Berkeley) 2/23/91"; +#endif /* LIBC_SCCS and not lint */ + +#include <sys/types.h> +#include <sys/signal.h> +#include <sys/wait.h> +#include <stdlib.h> +#include <stddef.h> +#include <unistd.h> +#include <paths.h> + +system(command) + const char *command; +{ + union wait pstat; + pid_t pid; + int omask; + sig_t intsave, quitsave; + + if (!command) /* just checking... */ + return(1); + + omask = sigblock(sigmask(SIGCHLD)); + switch(pid = vfork()) { + case -1: /* error */ + (void)sigsetmask(omask); + pstat.w_status = 0; + pstat.w_retcode = 127; + return(pstat.w_status); + case 0: /* child */ + (void)sigsetmask(omask); + execl(_PATH_BSHELL, "sh", "-c", command, (char *)NULL); + _exit(127); + } + intsave = signal(SIGINT, SIG_IGN); + quitsave = signal(SIGQUIT, SIG_IGN); + pid = waitpid(pid, (int *)&pstat, 0); + (void)sigsetmask(omask); + (void)signal(SIGINT, intsave); + (void)signal(SIGQUIT, quitsave); + return(pid == -1 ? -1 : pstat.w_status); +} |