diff options
Diffstat (limited to 'lib/libc/stdlib')
| -rw-r--r-- | lib/libc/stdlib/Makefile.inc | 25 | ||||
| -rw-r--r-- | lib/libc/stdlib/atexit.c | 68 | ||||
| -rw-r--r-- | lib/libc/stdlib/atexit.h | 45 | ||||
| -rw-r--r-- | lib/libc/stdlib/getopt.3 | 260 | ||||
| -rw-r--r-- | lib/libc/stdlib/getopt.c | 117 | ||||
| -rw-r--r-- | lib/libc/stdlib/radixsort.c | 318 | ||||
| -rw-r--r-- | lib/libc/stdlib/random.c | 400 |
7 files changed, 1233 insertions, 0 deletions
diff --git a/lib/libc/stdlib/Makefile.inc b/lib/libc/stdlib/Makefile.inc new file mode 100644 index 000000000000..9982037064b2 --- /dev/null +++ b/lib/libc/stdlib/Makefile.inc @@ -0,0 +1,25 @@ +# @(#)Makefile.inc 8.3 (Berkeley) 2/4/95 + +# machine-independent stdlib sources +.PATH: ${.CURDIR}/${MACHINE}/stdlib ${.CURDIR}/stdlib + +SRCS+= abort.c atexit.c atof.c atoi.c atol.c bsearch.c calloc.c div.c \ + exit.c getenv.c getopt.c getsubopt.c heapsort.c labs.c ldiv.c \ + malloc.c merge.c putenv.c qsort.c radixsort.c rand.c random.c \ + setenv.c strtod.c strtol.c strtoq.c strtoul.c \ + strtouq.c system.c + +# machine-dependent stdlib sources +.include "${.CURDIR}/${MACHINE}/stdlib/Makefile.inc" + +MAN3+= abort.0 abs.0 alloca.0 atexit.0 atof.0 atoi.0 atol.0 bsearch.0 \ + calloc.0 div.0 exit.0 free.0 getenv.0 getopt.0 getsubopt.0 labs.0 \ + ldiv.0 malloc.0 memory.0 qsort.0 radixsort.0 rand.0 random.0 \ + realloc.0 strtol.0 strtoul.0 system.0 + +MLINKS+=getenv.3 setenv.3 getenv.3 unsetenv.3 getenv.3 putenv.3 +MLINKS+=qsort.3 heapsort.3 qsort.3 mergesort.3 +MLINKS+=rand.3 srand.3 +MLINKS+=random.3 initstate.3 random.3 setstate.3 random.3 srandom.3 +MLINKS+=strtol.3 strtoq.3 +MLINKS+=strtoul.3 strtouq.3 diff --git a/lib/libc/stdlib/atexit.c b/lib/libc/stdlib/atexit.c new file mode 100644 index 000000000000..bbf374e18db4 --- /dev/null +++ b/lib/libc/stdlib/atexit.c @@ -0,0 +1,68 @@ +/*- + * Copyright (c) 1990, 1993 + * 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 8.2 (Berkeley) 7/3/94"; +#endif /* LIBC_SCCS and not lint */ + +#include <stddef.h> +#include <stdlib.h> +#include "atexit.h" + +struct atexit *__atexit; /* points to head of LIFO stack */ + +/* + * 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..819151e2b952 --- /dev/null +++ b/lib/libc/stdlib/atexit.h @@ -0,0 +1,45 @@ +/*- + * Copyright (c) 1990, 1993 + * 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 8.2 (Berkeley) 7/3/94 + */ + +/* 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 */ +}; + +extern struct atexit *__atexit; /* points to head of LIFO stack */ diff --git a/lib/libc/stdlib/getopt.3 b/lib/libc/stdlib/getopt.3 new file mode 100644 index 000000000000..39cc5de17187 --- /dev/null +++ b/lib/libc/stdlib/getopt.3 @@ -0,0 +1,260 @@ +.\" Copyright (c) 1988, 1991, 1993 +.\" 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. +.\" +.\" @(#)getopt.3 8.5 (Berkeley) 4/27/95 +.\" +.Dd April 27, 1995 +.Dt GETOPT 3 +.Os BSD 4.3 +.Sh NAME +.Nm getopt +.Nd get option character from command line argument list +.Sh SYNOPSIS +.Fd #include <unistd.h> +.Vt extern char *optarg; +.Vt extern int optind; +.Vt extern int optopt; +.Vt extern int opterr; +.Vt extern int optreset; +.Ft int +.Fn getopt "int argc" "char * const *argv" "const char *optstring" +.Sh DESCRIPTION +The +.Fn getopt +function incrementally parses a command line argument list +.Fa argv +and returns the next +.Em known +option character. +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 elements: individual characters, and +characters followed by a colon to indicate an option argument +is to follow. +For example, an option string +.Li "\&""x"" +recognizes an option +.Dq Fl x , +and an option string +.Li "\&""x:"" +recognizes an option and argument +.Dq Fl x Ar argument . +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 . +The variable +.Va optopt +saves the last +.Em known +option character returned by +.Fn getopt . +.Pp +The variable +.Va opterr +and +.Va optind +are both initialized to 1. +The +.Va optind +variable may be set to another value before a set of calls to +.Fn getopt +in order to skip over more or less argv entries. +.Pp +In order to use +.Fn getopt +to evaluate multiple sets of arguments, or to evaluate a single set of +arguments multiple times, +the variable +.Va optreset +must be set to 1 before the second and each additional set of calls to +.Fn getopt , +and the variable +.Va optind +must be reinitialized. +.Pp +The +.Fn getopt +function +returns \-1 +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 returns \-1. +When all options have been processed (i.e., up to the first non-option +argument), +.Fn getopt +returns \-1. +.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 an error message and returns +.Ql ? +to the +.Em stderr . +Setting +.Va opterr +to a zero will disable these error messages. +If +.Va optstring +has a leading +.Ql \&: +then a missing option argument causes a +.Ql \&: +to be returned in addition to suppressing any error messages. +.Pp +Option arguments are allowed to begin with +.Dq Li \- ; +this is reasonable but +reduces the amount of error checking possible. +.Sh EXTENSIONS +The +.Va optreset +variable was added to make it possible to call the +.Fn getopt +function multiple times. +This is an extension to the +.St -p1003.2 +specification. +.Sh EXAMPLE +.Bd -literal -compact +extern char *optarg; +extern int optind; +int bflag, ch, fd; + +bflag = 0; +while ((ch = getopt(argc, argv, "bf:")) != -1) + switch(ch) { + case 'b': + bflag = 1; + break; + case 'f': + if ((fd = open(optarg, O_RDONLY, 0)) < 0) { + (void)fprintf(stderr, + "myname: %s: %s\en", optarg, strerror(errno)); + exit(1); + } + break; + case '?': + default: + usage(); +} +argc -= optind; +argv += optind; +.Ed +.Sh HISTORY +The +.Fn getopt +function appeared +.Bx 4.3 . +.Sh BUGS +The +.Fn getopt +function was once specified to return +.Dv EOF +instead of \-1. +This was changed by +.St -p1003.2-92 +to decouple +.Fn getopt +from +.Pa <stdio.h> . +.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 \-1. +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 in most cases. +.Bd -literal -offset indent +int length; +char *p; + +while ((c = getopt(argc, argv, "0123456789")) != -1) + 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..5dddf86072a5 --- /dev/null +++ b/lib/libc/stdlib/getopt.c @@ -0,0 +1,117 @@ +/* + * Copyright (c) 1987, 1993, 1994 + * 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[] = "@(#)getopt.c 8.3 (Berkeley) 4/27/95"; +#endif /* LIBC_SCCS and not lint */ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +int opterr = 1, /* if error message should be printed */ + optind = 1, /* index into parent argv vector */ + optopt, /* character checked for validity */ + optreset; /* reset getopt */ +char *optarg; /* argument associated with option */ + +#define BADCH (int)'?' +#define BADARG (int)':' +#define EMSG "" + +/* + * getopt -- + * Parse argc/argv argument vector. + */ +int +getopt(nargc, nargv, ostr) + int nargc; + char * const *nargv; + const char *ostr; +{ + extern char *__progname; + static char *place = EMSG; /* option letter processing */ + char *oli; /* option letter list index */ + + if (optreset || !*place) { /* update scanning pointer */ + optreset = 0; + if (optind >= nargc || *(place = nargv[optind]) != '-') { + place = EMSG; + return (-1); + } + if (place[1] && *++place == '-') { /* found "--" */ + ++optind; + place = EMSG; + return (-1); + } + } /* option letter okay? */ + if ((optopt = (int)*place++) == (int)':' || + !(oli = strchr(ostr, optopt))) { + /* + * if the user didn't specify '-' as an option, + * assume it means -1. + */ + if (optopt == (int)'-') + return (-1); + if (!*place) + ++optind; + if (opterr && *ostr != ':') + (void)fprintf(stderr, + "%s: illegal option -- %c\n", __progname, 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 (*ostr == ':') + return (BADARG); + if (opterr) + (void)fprintf(stderr, + "%s: option requires an argument -- %c\n", + __progname, optopt); + return (BADCH); + } + else /* white space */ + optarg = nargv[optind]; + place = EMSG; + ++optind; + } + return (optopt); /* dump back option letter */ +} diff --git a/lib/libc/stdlib/radixsort.c b/lib/libc/stdlib/radixsort.c new file mode 100644 index 000000000000..b932bf504821 --- /dev/null +++ b/lib/libc/stdlib/radixsort.c @@ -0,0 +1,318 @@ +/*- + * Copyright (c) 1990, 1993 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Peter McIlroy and by Dan Bernstein at New York University, + * + * 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 8.2 (Berkeley) 4/28/95"; +#endif /* LIBC_SCCS and not lint */ + +/* + * Radixsort routines. + * + * Program r_sort_a() is unstable but uses O(logN) extra memory for a stack. + * Use radixsort(a, n, trace, endchar) for this case. + * + * For stable sorting (using N extra pointers) use sradixsort(), which calls + * r_sort_b(). + * + * For a description of this code, see D. McIlroy, P. McIlroy, K. Bostic, + * "Engineering Radix Sort". + */ + +#include <sys/types.h> +#include <stdlib.h> +#include <stddef.h> +#include <errno.h> + +typedef struct { + const u_char **sa; + int sn, si; +} stack; + +static inline void simplesort + __P((const u_char **, int, int, const u_char *, u_int)); +static void r_sort_a __P((const u_char **, int, int, const u_char *, u_int)); +static void r_sort_b __P((const u_char **, + const u_char **, int, int, const u_char *, u_int)); + +#define THRESHOLD 20 /* Divert to simplesort(). */ +#define SIZE 512 /* Default stack size. */ + +#define SETUP { \ + if (tab == NULL) { \ + tr = tr0; \ + for (c = 0; c < endch; c++) \ + tr0[c] = c + 1; \ + tr0[c] = 0; \ + for (c++; c < 256; c++) \ + tr0[c] = c; \ + endch = 0; \ + } else { \ + endch = tab[endch]; \ + tr = tab; \ + if (endch != 0 && endch != 255) { \ + errno = EINVAL; \ + return (-1); \ + } \ + } \ +} + +int +radixsort(a, n, tab, endch) + const u_char **a, *tab; + int n; + u_int endch; +{ + const u_char *tr; + int c; + u_char tr0[256]; + + SETUP; + r_sort_a(a, n, 0, tr, endch); + return (0); +} + +int +sradixsort(a, n, tab, endch) + const u_char **a, *tab; + int n; + u_int endch; +{ + const u_char *tr, **ta; + int c; + u_char tr0[256]; + + SETUP; + if (n < THRESHOLD) + simplesort(a, n, 0, tr, endch); + else { + if ((ta = malloc(n * sizeof(a))) == NULL) + return (-1); + r_sort_b(a, ta, n, 0, tr, endch); + free(ta); + } + return (0); +} + +#define empty(s) (s >= sp) +#define pop(a, n, i) a = (--sp)->sa, n = sp->sn, i = sp->si +#define push(a, n, i) sp->sa = a, sp->sn = n, (sp++)->si = i +#define swap(a, b, t) t = a, a = b, b = t + +/* Unstable, in-place sort. */ +static void +r_sort_a(a, n, i, tr, endch) + const u_char **a; + int n, i; + const u_char *tr; + u_int endch; +{ + static int count[256], nc, bmin; + register int c; + register const u_char **ak, *r; + stack s[SIZE], *sp, *sp0, *sp1, temp; + int *cp, bigc; + const u_char **an, *t, **aj, **top[256]; + + /* Set up stack. */ + sp = s; + push(a, n, i); + while (!empty(s)) { + pop(a, n, i); + if (n < THRESHOLD) { + simplesort(a, n, i, tr, endch); + continue; + } + an = a + n; + + /* Make character histogram. */ + if (nc == 0) { + bmin = 255; /* First occupied bin, excluding eos. */ + for (ak = a; ak < an;) { + c = tr[(*ak++)[i]]; + if (++count[c] == 1 && c != endch) { + if (c < bmin) + bmin = c; + nc++; + } + } + if (sp + nc > s + SIZE) { /* Get more stack. */ + r_sort_a(a, n, i, tr, endch); + continue; + } + } + + /* + * Set top[]; push incompletely sorted bins onto stack. + * top[] = pointers to last out-of-place element in bins. + * count[] = counts of elements in bins. + * Before permuting: top[c-1] + count[c] = top[c]; + * during deal: top[c] counts down to top[c-1]. + */ + sp0 = sp1 = sp; /* Stack position of biggest bin. */ + bigc = 2; /* Size of biggest bin. */ + if (endch == 0) /* Special case: set top[eos]. */ + top[0] = ak = a + count[0]; + else { + ak = a; + top[255] = an; + } + for (cp = count + bmin; nc > 0; cp++) { + while (*cp == 0) /* Find next non-empty pile. */ + cp++; + if (*cp > 1) { + if (*cp > bigc) { + bigc = *cp; + sp1 = sp; + } + push(ak, *cp, i+1); + } + top[cp-count] = ak += *cp; + nc--; + } + swap(*sp0, *sp1, temp); /* Play it safe -- biggest bin last. */ + + /* + * Permute misplacements home. Already home: everything + * before aj, and in bin[c], items from top[c] on. + * Inner loop: + * r = next element to put in place; + * ak = top[r[i]] = location to put the next element. + * aj = bottom of 1st disordered bin. + * Outer loop: + * Once the 1st disordered bin is done, ie. aj >= ak, + * aj<-aj + count[c] connects the bins in a linked list; + * reset count[c]. + */ + for (aj = a; aj < an; *aj = r, aj += count[c], count[c] = 0) + for (r = *aj; aj < (ak = --top[c = tr[r[i]]]);) + swap(*ak, r, t); + } +} + +/* Stable sort, requiring additional memory. */ +static void +r_sort_b(a, ta, n, i, tr, endch) + const u_char **a, **ta; + int n, i; + const u_char *tr; + u_int endch; +{ + static int count[256], nc, bmin; + register int c; + register const u_char **ak, **ai; + stack s[512], *sp, *sp0, *sp1, temp; + const u_char **top[256]; + int *cp, bigc; + + sp = s; + push(a, n, i); + while (!empty(s)) { + pop(a, n, i); + if (n < THRESHOLD) { + simplesort(a, n, i, tr, endch); + continue; + } + + if (nc == 0) { + bmin = 255; + for (ak = a + n; --ak >= a;) { + c = tr[(*ak)[i]]; + if (++count[c] == 1 && c != endch) { + if (c < bmin) + bmin = c; + nc++; + } + } + if (sp + nc > s + SIZE) { + r_sort_b(a, ta, n, i, tr, endch); + continue; + } + } + + sp0 = sp1 = sp; + bigc = 2; + if (endch == 0) { + top[0] = ak = a + count[0]; + count[0] = 0; + } else { + ak = a; + top[255] = a + n; + count[255] = 0; + } + for (cp = count + bmin; nc > 0; cp++) { + while (*cp == 0) + cp++; + if ((c = *cp) > 1) { + if (c > bigc) { + bigc = c; + sp1 = sp; + } + push(ak, c, i+1); + } + top[cp-count] = ak += c; + *cp = 0; /* Reset count[]. */ + nc--; + } + swap(*sp0, *sp1, temp); + + for (ak = ta + n, ai = a+n; ak > ta;) /* Copy to temp. */ + *--ak = *--ai; + for (ak = ta+n; --ak >= ta;) /* Deal to piles. */ + *--top[tr[(*ak)[i]]] = *ak; + } +} + +static inline void +simplesort(a, n, b, tr, endch) /* insertion sort */ + register const u_char **a; + int n, b; + register const u_char *tr; + u_int endch; +{ + register u_char ch; + const u_char **ak, **ai, *s, *t; + + for (ak = a+1; --n >= 1; ak++) + for (ai = ak; ai > a; ai--) { + for (s = ai[0] + b, t = ai[-1] + b; + (ch = tr[*s]) != endch; s++, t++) + if (ch != tr[*t]) + break; + if (ch >= tr[*t]) + break; + swap(ai[0], ai[-1], s); + } +} diff --git a/lib/libc/stdlib/random.c b/lib/libc/stdlib/random.c new file mode 100644 index 000000000000..7c76158d9b97 --- /dev/null +++ b/lib/libc/stdlib/random.c @@ -0,0 +1,400 @@ +/* + * Copyright (c) 1983, 1993 + * 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[] = "@(#)random.c 8.2 (Berkeley) 5/19/95"; +#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. + * + * Modified 28 December 1994 by Jacob S. Rosenberg. + * The following changes have been made: + * All references to the type u_int have been changed to unsigned long. + * All references to type int have been changed to type long. Other + * cleanups have been made as well. A warning for both initstate and + * setstate has been inserted to the effect that on Sparc platforms + * the 'arg_state' variable must be forced to begin on word boundaries. + * This can be easily done by casting a long integer array to char *. + * The overall logic has been left STRICTLY alone. This software was + * tested on both a VAX and Sun SpacsStation with exactly the same + * results. The new version and the original give IDENTICAL results. + * The new version is somewhat faster than the original. As the + * documentation says: "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." For a buffer of + * 128 bytes, this new version runs about 19 percent faster and for a 16 + * byte buffer it is about 5 percent faster. + */ + +/* + * 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 long degrees[MAX_TYPES] = { DEG_0, DEG_1, DEG_2, DEG_3, DEG_4 }; +static long 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 long rand_type = TYPE_3; +static long rand_deg = DEG_3; +static long 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) + unsigned long x; +{ + register long i; + + if (rand_type == TYPE_0) + state[0] = x; + else { + 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. + * + * Note: The Sparc platform requires that arg_state begin on a long + * word boundary; otherwise a bus error will occur. Even so, lint will + * complain about mis-alignment, but you should disregard these messages. + */ +char * +initstate(seed, arg_state, n) + unsigned long seed; /* seed for R.N.G. */ + char *arg_state; /* pointer to state array */ + long n; /* # bytes of state info */ +{ + register char *ostate = (char *)(&state[-1]); + register long *long_arg_state = (long *) arg_state; + + 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 (%ld 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 *) (long_arg_state + 1); /* first location */ + end_ptr = &state[rand_deg]; /* must set end_ptr before srandom */ + srandom(seed); + if (rand_type == TYPE_0) + long_arg_state[0] = rand_type; + else + long_arg_state[0] = 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. + * + * Note: The Sparc platform requires that arg_state begin on a long + * word boundary; otherwise a bus error will occur. Even so, lint will + * complain about mis-alignment, but you should disregard these messages. + */ +char * +setstate(arg_state) + char *arg_state; /* pointer to state array */ +{ + register long *new_state = (long *) arg_state; + register long type = new_state[0] % MAX_TYPES; + register long 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 = (long *) (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() +{ + register long i; + register long *f, *r; + + if (rand_type == TYPE_0) { + i = state[0]; + state[0] = i = (i * 1103515245 + 12345) & 0x7fffffff; + } else { + /* + * Use local variables rather than static variables for speed. + */ + f = fptr; r = rptr; + *f += *r; + i = (*f >> 1) & 0x7fffffff; /* chucking least random bit */ + if (++f >= end_ptr) { + f = state; + ++r; + } + else if (++r >= end_ptr) { + r = state; + } + + fptr = f; rptr = r; + } + return(i); +} |