From 28f540f45bbacd939bfd07f213bcad2bf730b1bf Mon Sep 17 00:00:00 2001 From: Roland McGrath Date: Sat, 18 Feb 1995 01:27:10 +0000 Subject: initial import --- stdlib/Makefile | 43 +++ stdlib/abs.c | 30 ++ stdlib/alloca.h | 44 +++ stdlib/atexit.c | 65 ++++ stdlib/atof.c | 30 ++ stdlib/atoi.c | 30 ++ stdlib/atol.c | 30 ++ stdlib/bsearch.c | 51 +++ stdlib/div.c | 92 +++++ stdlib/exit.c | 70 ++++ stdlib/exit.h | 44 +++ stdlib/labs.c | 31 ++ stdlib/ldiv.c | 92 +++++ stdlib/mblen.c | 31 ++ stdlib/mbstowcs.c | 78 ++++ stdlib/mbtowc.c | 84 +++++ stdlib/msort.c | 103 +++++ stdlib/on_exit.c | 37 ++ stdlib/qsort.c | 243 ++++++++++++ stdlib/rand.c | 30 ++ stdlib/random.c | 357 ++++++++++++++++++ stdlib/stdlib.h | 289 ++++++++++++++ stdlib/strtod.c | 1027 ++++++++++++++++++++++++++++++++++++++++++++++++++ stdlib/strtof.c | 12 + stdlib/strtol.c | 189 ++++++++++ stdlib/strtold.c | 12 + stdlib/strtoq.c | 22 ++ stdlib/strtoul.c | 21 ++ stdlib/strtouq.c | 22 ++ stdlib/testdiv.c | 33 ++ stdlib/testdiv.input | 2 + stdlib/testmb.c | 69 ++++ stdlib/testrand.c | 51 +++ stdlib/testsort.c | 38 ++ stdlib/tst-strtod.c | 94 +++++ stdlib/tst-strtol.c | 127 +++++++ stdlib/wcstombs.c | 77 ++++ stdlib/wctomb.c | 72 ++++ 38 files changed, 3772 insertions(+) create mode 100644 stdlib/Makefile create mode 100644 stdlib/abs.c create mode 100644 stdlib/alloca.h create mode 100644 stdlib/atexit.c create mode 100644 stdlib/atof.c create mode 100644 stdlib/atoi.c create mode 100644 stdlib/atol.c create mode 100644 stdlib/bsearch.c create mode 100644 stdlib/div.c create mode 100644 stdlib/exit.c create mode 100644 stdlib/exit.h create mode 100644 stdlib/labs.c create mode 100644 stdlib/ldiv.c create mode 100644 stdlib/mblen.c create mode 100644 stdlib/mbstowcs.c create mode 100644 stdlib/mbtowc.c create mode 100644 stdlib/msort.c create mode 100644 stdlib/on_exit.c create mode 100644 stdlib/qsort.c create mode 100644 stdlib/rand.c create mode 100644 stdlib/random.c create mode 100644 stdlib/stdlib.h create mode 100644 stdlib/strtod.c create mode 100644 stdlib/strtof.c create mode 100644 stdlib/strtol.c create mode 100644 stdlib/strtold.c create mode 100644 stdlib/strtoq.c create mode 100644 stdlib/strtoul.c create mode 100644 stdlib/strtouq.c create mode 100644 stdlib/testdiv.c create mode 100644 stdlib/testdiv.input create mode 100644 stdlib/testmb.c create mode 100644 stdlib/testrand.c create mode 100644 stdlib/testsort.c create mode 100644 stdlib/tst-strtod.c create mode 100644 stdlib/tst-strtol.c create mode 100644 stdlib/wcstombs.c create mode 100644 stdlib/wctomb.c (limited to 'stdlib') diff --git a/stdlib/Makefile b/stdlib/Makefile new file mode 100644 index 0000000000..1a1498c662 --- /dev/null +++ b/stdlib/Makefile @@ -0,0 +1,43 @@ +# Copyright (C) 1991, 1992, 1993, 1994, 1995 Free Software Foundation, Inc. +# This file is part of the GNU C Library. + +# The GNU C Library is free software; you can redistribute it and/or +# modify it under the terms of the GNU Library General Public License as +# published by the Free Software Foundation; either version 2 of the +# License, or (at your option) any later version. + +# The GNU C Library is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +# Library General Public License for more details. + +# You should have received a copy of the GNU Library General Public +# License along with the GNU C Library; see the file COPYING.LIB. If +# not, write to the Free Software Foundation, Inc., 675 Mass Ave, +# Cambridge, MA 02139, USA. + +# +# Makefile for stdlib routines +# +subdir := stdlib + +headers := stdlib.h alloca.h + +routines := \ + atof atoi atol \ + abort \ + bsearch qsort msort \ + getenv putenv setenv \ + exit on_exit atexit \ + abs labs \ + div ldiv \ + mblen mbstowcs mbtowc wcstombs wctomb \ + random rand \ + strtol strtoul strtoq strtouq \ + strtof strtod strtold \ + system + +distribute := exit.h +tests := tst-strtol tst-strtod testmb testrand testsort testdiv + +include ../Rules diff --git a/stdlib/abs.c b/stdlib/abs.c new file mode 100644 index 0000000000..b8db100b41 --- /dev/null +++ b/stdlib/abs.c @@ -0,0 +1,30 @@ +/* Copyright (C) 1991 Free Software Foundation, Inc. +This file is part of the GNU C Library. + +The GNU C Library is free software; you can redistribute it and/or +modify it under the terms of the GNU Library General Public License as +published by the Free Software Foundation; either version 2 of the +License, or (at your option) any later version. + +The GNU C Library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Library General Public License for more details. + +You should have received a copy of the GNU Library General Public +License along with the GNU C Library; see the file COPYING.LIB. If +not, write to the Free Software Foundation, Inc., 675 Mass Ave, +Cambridge, MA 02139, USA. */ + +#include +#include + +#undef abs + +/* Return the absolute value of I. */ +__CONSTVALUE +int +DEFUN(abs, (i), int i) +{ + return(i < 0 ? -i : i); +} diff --git a/stdlib/alloca.h b/stdlib/alloca.h new file mode 100644 index 0000000000..4e9de464a3 --- /dev/null +++ b/stdlib/alloca.h @@ -0,0 +1,44 @@ +/* Copyright (C) 1992 Free Software Foundation, Inc. +This file is part of the GNU C Library. + +The GNU C Library is free software; you can redistribute it and/or +modify it under the terms of the GNU Library General Public License as +published by the Free Software Foundation; either version 2 of the +License, or (at your option) any later version. + +The GNU C Library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Library General Public License for more details. + +You should have received a copy of the GNU Library General Public +License along with the GNU C Library; see the file COPYING.LIB. If +not, write to the, 1992 Free Software Foundation, Inc., 675 Mass Ave, +Cambridge, MA 02139, USA. */ + +#ifndef _ALLOCA_H +#define _ALLOCA_H 1 +#include + +#define __need_size_t +#include + +__BEGIN_DECLS + +/* Remove any previous definitions. */ +#undef __alloca +#undef alloca + +/* Allocate a block that will be freed when the calling function exits. */ +extern __ptr_t __alloca __P ((size_t __size)); +extern __ptr_t alloca __P ((size_t __size)); + +#ifdef __GNUC__ +#define __alloca(size) __builtin_alloca(size) +#endif /* GCC. */ + +#define alloca(size) __alloca(size) + +__END_DECLS + +#endif /* alloca.h */ diff --git a/stdlib/atexit.c b/stdlib/atexit.c new file mode 100644 index 0000000000..a2ab453576 --- /dev/null +++ b/stdlib/atexit.c @@ -0,0 +1,65 @@ +/* Copyright (C) 1991 Free Software Foundation, Inc. +This file is part of the GNU C Library. + +The GNU C Library is free software; you can redistribute it and/or +modify it under the terms of the GNU Library General Public License as +published by the Free Software Foundation; either version 2 of the +License, or (at your option) any later version. + +The GNU C Library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Library General Public License for more details. + +You should have received a copy of the GNU Library General Public +License along with the GNU C Library; see the file COPYING.LIB. If +not, write to the Free Software Foundation, Inc., 675 Mass Ave, +Cambridge, MA 02139, USA. */ + +#include +#include +#include "exit.h" + + +/* Register FUNC to be executed by `exit'. */ +int +DEFUN(atexit, (func), void EXFUN((*func), (NOARGS))) +{ + struct exit_function *new = __new_exitfn(); + + if (new == NULL) + return -1; + + new->flavor = ef_at; + new->func.at = func; + return 0; +} + + +static struct exit_function_list fnlist = { NULL, 0, }; +struct exit_function_list *__exit_funcs = &fnlist; + +struct exit_function * +DEFUN_VOID(__new_exitfn) +{ + register struct exit_function_list *l; + + for (l = __exit_funcs; l != NULL; l = l->next) + { + register size_t i; + for (i = 0; i < l->idx; ++i) + if (l->fns[i].flavor == ef_free) + return &l->fns[i]; + if (l->idx < sizeof(l->fns) / sizeof(l->fns[0])) + return &l->fns[l->idx++]; + } + + l = (struct exit_function_list *) malloc(sizeof(struct exit_function_list)); + if (l == NULL) + return NULL; + l->next = __exit_funcs; + __exit_funcs = l; + + l->idx = 1; + return &l->fns[0]; +} diff --git a/stdlib/atof.c b/stdlib/atof.c new file mode 100644 index 0000000000..79585464d1 --- /dev/null +++ b/stdlib/atof.c @@ -0,0 +1,30 @@ +/* Copyright (C) 1991 Free Software Foundation, Inc. +This file is part of the GNU C Library. + +The GNU C Library is free software; you can redistribute it and/or +modify it under the terms of the GNU Library General Public License as +published by the Free Software Foundation; either version 2 of the +License, or (at your option) any later version. + +The GNU C Library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Library General Public License for more details. + +You should have received a copy of the GNU Library General Public +License along with the GNU C Library; see the file COPYING.LIB. If +not, write to the Free Software Foundation, Inc., 675 Mass Ave, +Cambridge, MA 02139, USA. */ + +#include +#include + +#undef atof + + +/* Convert a string to a double. */ +double +DEFUN(atof, (nptr), CONST char *nptr) +{ + return(strtod(nptr, (char **) NULL)); +} diff --git a/stdlib/atoi.c b/stdlib/atoi.c new file mode 100644 index 0000000000..9fe280cc3e --- /dev/null +++ b/stdlib/atoi.c @@ -0,0 +1,30 @@ +/* Copyright (C) 1991 Free Software Foundation, Inc. +This file is part of the GNU C Library. + +The GNU C Library is free software; you can redistribute it and/or +modify it under the terms of the GNU Library General Public License as +published by the Free Software Foundation; either version 2 of the +License, or (at your option) any later version. + +The GNU C Library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Library General Public License for more details. + +You should have received a copy of the GNU Library General Public +License along with the GNU C Library; see the file COPYING.LIB. If +not, write to the Free Software Foundation, Inc., 675 Mass Ave, +Cambridge, MA 02139, USA. */ + +#include +#include + +#undef atoi + + +/* Convert a string to an int. */ +int +DEFUN(atoi, (nptr), CONST char *nptr) +{ + return((int) strtol(nptr, (char **) NULL, 10)); +} diff --git a/stdlib/atol.c b/stdlib/atol.c new file mode 100644 index 0000000000..75f599c107 --- /dev/null +++ b/stdlib/atol.c @@ -0,0 +1,30 @@ +/* Copyright (C) 1991 Free Software Foundation, Inc. +This file is part of the GNU C Library. + +The GNU C Library is free software; you can redistribute it and/or +modify it under the terms of the GNU Library General Public License as +published by the Free Software Foundation; either version 2 of the +License, or (at your option) any later version. + +The GNU C Library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Library General Public License for more details. + +You should have received a copy of the GNU Library General Public +License along with the GNU C Library; see the file COPYING.LIB. If +not, write to the Free Software Foundation, Inc., 675 Mass Ave, +Cambridge, MA 02139, USA. */ + +#include +#include + +#undef atol + + +/* Convert a string to a long int. */ +long int +DEFUN(atol, (nptr), CONST char *nptr) +{ + return(strtol(nptr, (char **) NULL, 10)); +} diff --git a/stdlib/bsearch.c b/stdlib/bsearch.c new file mode 100644 index 0000000000..d798eabd2b --- /dev/null +++ b/stdlib/bsearch.c @@ -0,0 +1,51 @@ +/* Copyright (C) 1991, 1992 Free Software Foundation, Inc. +This file is part of the GNU C Library. + +The GNU C Library is free software; you can redistribute it and/or +modify it under the terms of the GNU Library General Public License as +published by the Free Software Foundation; either version 2 of the +License, or (at your option) any later version. + +The GNU C Library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Library General Public License for more details. + +You should have received a copy of the GNU Library General Public +License along with the GNU C Library; see the file COPYING.LIB. If +not, write to the Free Software Foundation, Inc., 675 Mass Ave, +Cambridge, MA 02139, USA. */ + +#include +#include + + +/* Perform a binary search for KEY in BASE which has NMEMB elements + of SIZE bytes each. The comparisons are done by (*COMPAR)(). */ +PTR +DEFUN(bsearch, (key, base, nmemb, size, compar), + register CONST PTR key AND register CONST PTR base AND + size_t nmemb AND register size_t size AND + register int EXFUN((*compar), (CONST PTR, CONST PTR))) +{ + register size_t l, u, idx; + register CONST PTR p; + register int comparison; + + l = 0; + u = nmemb; + while (l < u) + { + idx = (l + u) / 2; + p = (PTR) (((CONST char *) base) + (idx * size)); + comparison = (*compar)(key, p); + if (comparison < 0) + u = idx; + else if (comparison > 0) + l = idx + 1; + else + return (PTR) p; + } + + return NULL; +} diff --git a/stdlib/div.c b/stdlib/div.c new file mode 100644 index 0000000000..5a0ee7da38 --- /dev/null +++ b/stdlib/div.c @@ -0,0 +1,92 @@ +/* Copyright (C) 1992 Free Software Foundation, Inc. +This file is part of the GNU C Library. + +The GNU C Library is free software; you can redistribute it and/or +modify it under the terms of the GNU Library General Public License as +published by the Free Software Foundation; either version 2 of the +License, or (at your option) any later version. + +The GNU C Library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Library General Public License for more details. + +You should have received a copy of the GNU Library General Public +License along with the GNU C Library; see the file COPYING.LIB. If +not, write to the Free Software Foundation, Inc., 675 Mass Ave, +Cambridge, MA 02139, USA. */ + +/* + * 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. + */ + +#include +#include + + +/* Return the `div_t' representation of NUMER over DENOM. */ +__CONSTVALUE +div_t +DEFUN(div, (numer, denom), int numer AND int denom) +{ + div_t result; + + result.quot = numer / denom; + result.rem = numer % denom; + + /* The ANSI standard says that |QUOT| <= |NUMER / DENOM|, where + NUMER / DENOM is to be computed in infinite precision. In + other words, we should always truncate the quotient towards + zero, never -infinity. Machine division and remainer may + work either way when one or both of NUMER or DENOM is + negative. If only one is negative and QUOT has been + truncated towards -infinity, REM will have the same sign as + DENOM and the opposite sign of NUMER; if both are negative + and QUOT has been truncated towards -infinity, REM will be + positive (will have the opposite sign of NUMER). These are + considered `wrong'. If both are NUM and DENOM are positive, + RESULT will always be positive. This all boils down to: if + NUMER >= 0, but REM < 0, we got the wrong answer. In that + case, to get the right answer, add 1 to QUOT and subtract + DENOM from REM. */ + + if (numer >= 0 && result.rem < 0) + { + ++result.quot; + result.rem -= denom; + } + + return result; +} diff --git a/stdlib/exit.c b/stdlib/exit.c new file mode 100644 index 0000000000..4f33a25cc4 --- /dev/null +++ b/stdlib/exit.c @@ -0,0 +1,70 @@ +/* Copyright (C) 1991, 1995 Free Software Foundation, Inc. +This file is part of the GNU C Library. + +The GNU C Library is free software; you can redistribute it and/or +modify it under the terms of the GNU Library General Public License as +published by the Free Software Foundation; either version 2 of the +License, or (at your option) any later version. + +The GNU C Library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Library General Public License for more details. + +You should have received a copy of the GNU Library General Public +License along with the GNU C Library; see the file COPYING.LIB. If +not, write to the Free Software Foundation, Inc., 675 Mass Ave, +Cambridge, MA 02139, USA. */ + +#include +#include +#include +#include +#include "exit.h" + +#ifdef HAVE_GNU_LD +#include "set-hooks.h" +DEFINE_HOOK (__libc_atexit, (void)) +#endif + + +/* Call all functions registered with `atexit' and `on_exit', + in the reverse of the order in which they were registered + perform stdio cleanup, and terminate program execution with STATUS. */ +void +DEFUN(exit, (status), int status) +{ + register CONST struct exit_function_list *l; + + for (l = __exit_funcs; l != NULL; l = l->next) + { + register size_t i = l->idx; + while (i-- > 0) + { + CONST struct exit_function *CONST f = &l->fns[i]; + switch (f->flavor) + { + case ef_free: + break; + case ef_on: + (*f->func.on.fn)(status, f->func.on.arg); + break; + case ef_at: + (*f->func.at)(); + break; + } + } + } + +#ifdef HAVE_GNU_LD + RUN_HOOK (__libc_atexit, ()); +#else + { + extern void EXFUN(_cleanup, (NOARGS)); + _cleanup(); + } +#endif + + _exit(status); +} + diff --git a/stdlib/exit.h b/stdlib/exit.h new file mode 100644 index 0000000000..214217853e --- /dev/null +++ b/stdlib/exit.h @@ -0,0 +1,44 @@ +/* Copyright (C) 1991 Free Software Foundation, Inc. +This file is part of the GNU C Library. + +The GNU C Library is free software; you can redistribute it and/or +modify it under the terms of the GNU Library General Public License as +published by the Free Software Foundation; either version 2 of the +License, or (at your option) any later version. + +The GNU C Library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Library General Public License for more details. + +You should have received a copy of the GNU Library General Public +License along with the GNU C Library; see the file COPYING.LIB. If +not, write to the Free Software Foundation, Inc., 675 Mass Ave, +Cambridge, MA 02139, USA. */ + +#ifndef _EXIT_H + +struct exit_function + { + enum { ef_free, ef_on, ef_at } flavor; /* `ef_free' MUST be zero! */ + union + { + void EXFUN((*at), (NOARGS)); + struct + { + void EXFUN((*fn), (int status, PTR arg)); + PTR arg; + } on; + } func; + }; +struct exit_function_list + { + struct exit_function_list *next; + size_t idx; + struct exit_function fns[32]; + }; +extern struct exit_function_list *__exit_funcs; + +extern struct exit_function *EXFUN(__new_exitfn, (NOARGS)); + +#endif /* exit.h */ diff --git a/stdlib/labs.c b/stdlib/labs.c new file mode 100644 index 0000000000..c54339f02b --- /dev/null +++ b/stdlib/labs.c @@ -0,0 +1,31 @@ +/* Copyright (C) 1991 Free Software Foundation, Inc. +This file is part of the GNU C Library. + +The GNU C Library is free software; you can redistribute it and/or +modify it under the terms of the GNU Library General Public License as +published by the Free Software Foundation; either version 2 of the +License, or (at your option) any later version. + +The GNU C Library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Library General Public License for more details. + +You should have received a copy of the GNU Library General Public +License along with the GNU C Library; see the file COPYING.LIB. If +not, write to the Free Software Foundation, Inc., 675 Mass Ave, +Cambridge, MA 02139, USA. */ + +#include +#include + +#undef labs + + +/* Return the absolute value of I. */ +__CONSTVALUE +long int +DEFUN(labs, (i), long int i) +{ + return(i < 0 ? -i : i); +} diff --git a/stdlib/ldiv.c b/stdlib/ldiv.c new file mode 100644 index 0000000000..661f1bdbcd --- /dev/null +++ b/stdlib/ldiv.c @@ -0,0 +1,92 @@ +/* Copyright (C) 1992 Free Software Foundation, Inc. +This file is part of the GNU C Library. + +The GNU C Library is free software; you can redistribute it and/or +modify it under the terms of the GNU Library General Public License as +published by the Free Software Foundation; either version 2 of the +License, or (at your option) any later version. + +The GNU C Library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Library General Public License for more details. + +You should have received a copy of the GNU Library General Public +License along with the GNU C Library; see the file COPYING.LIB. If +not, write to the Free Software Foundation, Inc., 675 Mass Ave, +Cambridge, MA 02139, USA. */ + +/* + * 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. + */ + +#include +#include + + +/* Return the `ldiv_t' representation of NUMER over DENOM. */ +__CONSTVALUE +ldiv_t +DEFUN(ldiv, (numer, denom), long int numer AND long int denom) +{ + ldiv_t result; + + result.quot = numer / denom; + result.rem = numer % denom; + + /* The ANSI standard says that |QUOT| <= |NUMER / DENOM|, where + NUMER / DENOM is to be computed in infinite precision. In + other words, we should always truncate the quotient towards + zero, never -infinity. Machine division and remainer may + work either way when one or both of NUMER or DENOM is + negative. If only one is negative and QUOT has been + truncated towards -infinity, REM will have the same sign as + DENOM and the opposite sign of NUMER; if both are negative + and QUOT has been truncated towards -infinity, REM will be + positive (will have the opposite sign of NUMER). These are + considered `wrong'. If both are NUM and DENOM are positive, + RESULT will always be positive. This all boils down to: if + NUMER >= 0, but REM < 0, we got the wrong answer. In that + case, to get the right answer, add 1 to QUOT and subtract + DENOM from REM. */ + + if (numer >= 0 && result.rem < 0) + { + ++result.quot; + result.rem -= denom; + } + + return result; +} diff --git a/stdlib/mblen.c b/stdlib/mblen.c new file mode 100644 index 0000000000..5393ce433c --- /dev/null +++ b/stdlib/mblen.c @@ -0,0 +1,31 @@ +/* Copyright (C) 1991 Free Software Foundation, Inc. +This file is part of the GNU C Library. + +The GNU C Library is free software; you can redistribute it and/or +modify it under the terms of the GNU Library General Public License as +published by the Free Software Foundation; either version 2 of the +License, or (at your option) any later version. + +The GNU C Library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Library General Public License for more details. + +You should have received a copy of the GNU Library General Public +License along with the GNU C Library; see the file COPYING.LIB. If +not, write to the Free Software Foundation, Inc., 675 Mass Ave, +Cambridge, MA 02139, USA. */ + +#include +#include + +#undef mblen + + +/* Return the length of the multibyte character (if there is one) + at S which is no longer than N characters. */ +int +DEFUN(mblen, (s, n), CONST char *s AND size_t n) +{ + return(mbtowc((wchar_t *) NULL, s, n)); +} diff --git a/stdlib/mbstowcs.c b/stdlib/mbstowcs.c new file mode 100644 index 0000000000..38c710279a --- /dev/null +++ b/stdlib/mbstowcs.c @@ -0,0 +1,78 @@ +/* Copyright (C) 1991, 1992 Free Software Foundation, Inc. +This file is part of the GNU C Library. + +The GNU C Library is free software; you can redistribute it and/or +modify it under the terms of the GNU Library General Public License as +published by the Free Software Foundation; either version 2 of the +License, or (at your option) any later version. + +The GNU C Library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Library General Public License for more details. + +You should have received a copy of the GNU Library General Public +License along with the GNU C Library; see the file COPYING.LIB. If +not, write to the Free Software Foundation, Inc., 675 Mass Ave, +Cambridge, MA 02139, USA. */ + +#include +#include +#include +#include + + +extern int _mb_shift; /* Defined in mbtowc.c. */ + +/* Convert the string of multibyte characters in S to `wchar_t's in + PWCS, writing no more than N. Return the number written, + or (size_t) -1 if an invalid multibyte character is encountered. */ +size_t +DEFUN(mbstowcs, (pwcs, s, n), + register wchar_t *pwcs AND register CONST char *s AND register size_t n) +{ + int save_shift; + register size_t written = 0; + + /* Save the shift state. */ + save_shift = _mb_shift; + /* Reset the shift state. */ + _mb_shift = 0; + + while (*s != '\0') + { + int len; + if (isascii (*s)) + { + *pwcs = (wchar_t) *s; + len = 1; + } + else + len = mbtowc (pwcs, s, n); + + if (len < 1) + { + /* Return an error. */ + written = (size_t) -1; + break; + } + else + { + /* Multibyte character converted. */ + ++pwcs; + ++written; + s += len; + n -= len; + } + } + + /* Terminate the string if it has space. */ + if (n > 0) + *pwcs = (wchar_t) 0; + + /* Restore the old shift state. */ + _mb_shift = save_shift; + + /* Return how many we wrote (or maybe an error). */ + return written; +} diff --git a/stdlib/mbtowc.c b/stdlib/mbtowc.c new file mode 100644 index 0000000000..62103407c0 --- /dev/null +++ b/stdlib/mbtowc.c @@ -0,0 +1,84 @@ +/* Copyright (C) 1991, 1992, 1995 Free Software Foundation, Inc. +This file is part of the GNU C Library. + +The GNU C Library is free software; you can redistribute it and/or +modify it under the terms of the GNU Library General Public License as +published by the Free Software Foundation; either version 2 of the +License, or (at your option) any later version. + +The GNU C Library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Library General Public License for more details. + +You should have received a copy of the GNU Library General Public +License along with the GNU C Library; see the file COPYING.LIB. If +not, write to the Free Software Foundation, Inc., 675 Mass Ave, +Cambridge, MA 02139, USA. */ + +#include +#include +#include +#include +#include +#include +#include + + +long int _mb_shift = 0; + +/* Convert the multibyte character at S, which is no longer + than N characters, to its `wchar_t' representation, placing + this n *PWC and returning its length. */ +int +DEFUN(mbtowc, (pwc, s, n), wchar_t *pwc AND CONST char *s AND size_t n) +{ + register CONST mb_char *mb; + register wchar_t i; + + if (s == NULL) + return _mb_shift != 0; + + if (*s == '\0') + /* ANSI 4.10.7.2, line 19. */ + return 0; + + if (isascii (*s)) + { + /* A normal ASCII character translates to itself. */ + if (pwc != NULL) + *pwc = (wchar_t) *s; + return 1; + } + + if (_ctype_info->mbchar == NULL || + _ctype_info->mbchar->mb_chars == NULL) + return -1; + + if (n > MB_CUR_MAX) + n = MB_CUR_MAX; + + for (i = 0; i < WCHAR_MAX; ++i) + { + mb = &_ctype_info->mbchar->mb_chars[i]; + /* EOF and NUL aren't MB chars. */ + if (i == (wchar_t) EOF || i == (wchar_t) '\0') + continue; + /* Normal ASCII values can't start MB chars. */ + else if (isascii(i)) + continue; + else if (mb->string == NULL || mb->len == 0) + continue; + else if (mb->len > n) + continue; + else if (!strncmp(mb->string, s, mb->len)) + { + _mb_shift += mb->shift; + if (pwc != NULL) + *pwc = i; + return mb->len; + } + } + + return -1; +} diff --git a/stdlib/msort.c b/stdlib/msort.c new file mode 100644 index 0000000000..92ba5182ed --- /dev/null +++ b/stdlib/msort.c @@ -0,0 +1,103 @@ +/* msort -- an alternative to qsort, with an identical interface. + Copyright (C) 1992 Free Software Foundation, Inc. + Written by Mike Haertel, September 1988. + +This file is part of the GNU C Library. + +The GNU C Library is free software; you can redistribute it and/or +modify it under the terms of the GNU Library General Public License as +published by the Free Software Foundation; either version 2 of the +License, or (at your option) any later version. + +The GNU C Library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Library General Public License for more details. + +You should have received a copy of the GNU Library General Public +License along with the GNU C Library; see the file COPYING.LIB. If +not, write to the Free Software Foundation, Inc., 675 Mass Ave, +Cambridge, MA 02139, USA. */ + +#include +#include +#include + +#define MEMCPY(dst, src, s) \ + ((s) == sizeof (int) \ + ? (*(int *) (dst) = *(int *) (src), (dst)) \ + : memcpy (dst, src, s)) + +static void +DEFUN(msort_with_tmp, (b, n, s, cmp, t), + PTR b AND size_t n AND size_t s AND __compar_fn_t cmp AND char *t) +{ + char *tmp; + char *b1, *b2; + size_t n1, n2; + + if (n <= 1) + return; + + n1 = n / 2; + n2 = n - n1; + b1 = b; + b2 = (char *) b + (n1 * s); + + msort_with_tmp (b1, n1, s, cmp, t); + msort_with_tmp (b2, n2, s, cmp, t); + + tmp = t; + + while (n1 > 0 && n2 > 0) + { + if ((*cmp) (b1, b2) <= 0) + { + MEMCPY (tmp, b1, s); + b1 += s; + --n1; + } + else + { + MEMCPY (tmp, b2, s); + b2 += s; + --n2; + } + tmp += s; + } + if (n1 > 0) + memcpy (tmp, b1, n1 * s); + memcpy (b, t, (n - n2) * s); +} + +void +DEFUN(qsort, (b, n, s, cmp), + PTR b AND size_t n AND size_t s AND __compar_fn_t cmp) +{ + CONST size_t size = n * s; + + if (size < 1024) + /* The temporary array is small, so put it on the stack. */ + msort_with_tmp (b, n, s, cmp, __alloca (size)); + else + { + /* It's somewhat large, so malloc it. */ + int save = errno; + char *tmp = malloc (size); + if (tmp == NULL) + { + /* Couldn't get space, so use the slower algorithm + that doesn't need a temporary array. */ + extern void EXFUN(_quicksort, (PTR __base, + size_t __nmemb, size_t __size, + __compar_fn_t __compar)); + _quicksort (b, n, s, cmp); + } + else + { + msort_with_tmp (b, n, s, cmp, tmp); + free (tmp); + } + errno = save; + } +} diff --git a/stdlib/on_exit.c b/stdlib/on_exit.c new file mode 100644 index 0000000000..bd100be895 --- /dev/null +++ b/stdlib/on_exit.c @@ -0,0 +1,37 @@ +/* Copyright (C) 1991 Free Software Foundation, Inc. +This file is part of the GNU C Library. + +The GNU C Library is free software; you can redistribute it and/or +modify it under the terms of the GNU Library General Public License as +published by the Free Software Foundation; either version 2 of the +License, or (at your option) any later version. + +The GNU C Library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Library General Public License for more details. + +You should have received a copy of the GNU Library General Public +License along with the GNU C Library; see the file COPYING.LIB. If +not, write to the Free Software Foundation, Inc., 675 Mass Ave, +Cambridge, MA 02139, USA. */ + +#include +#include +#include "exit.h" + +/* Register a function to be called by exit. */ +int +DEFUN(on_exit, (func, arg), + void EXFUN((*func), (int status, PTR arg)) AND PTR arg) +{ + struct exit_function *new = __new_exitfn(); + + if (new == NULL) + return -1; + + new->flavor = ef_on; + new->func.on.fn = func; + new->func.on.arg = arg; + return 0; +} diff --git a/stdlib/qsort.c b/stdlib/qsort.c new file mode 100644 index 0000000000..bc8d171b79 --- /dev/null +++ b/stdlib/qsort.c @@ -0,0 +1,243 @@ +/* Copyright (C) 1991, 1992 Free Software Foundation, Inc. +This file is part of the GNU C Library. +Written by Douglas C. Schmidt (schmidt@ics.uci.edu). + +The GNU C Library is free software; you can redistribute it and/or +modify it under the terms of the GNU Library General Public License as +published by the Free Software Foundation; either version 2 of the +License, or (at your option) any later version. + +The GNU C Library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Library General Public License for more details. + +You should have received a copy of the GNU Library General Public +License along with the GNU C Library; see the file COPYING.LIB. If +not, write to the Free Software Foundation, Inc., 675 Mass Ave, +Cambridge, MA 02139, USA. */ + +#include +#include +#include + +/* Byte-wise swap two items of size SIZE. */ +#define SWAP(a, b, size) \ + do \ + { \ + register size_t __size = (size); \ + register char *__a = (a), *__b = (b); \ + do \ + { \ + char __tmp = *__a; \ + *__a++ = *__b; \ + *__b++ = __tmp; \ + } while (--__size > 0); \ + } while (0) + +/* Discontinue quicksort algorithm when partition gets below this size. + This particular magic number was chosen to work best on a Sun 4/260. */ +#define MAX_THRESH 4 + +/* Stack node declarations used to store unfulfilled partition obligations. */ +typedef struct + { + char *lo; + char *hi; + } stack_node; + +/* The next 4 #defines implement a very fast in-line stack abstraction. */ +#define STACK_SIZE (8 * sizeof(unsigned long int)) +#define PUSH(low, high) ((void) ((top->lo = (low)), (top->hi = (high)), ++top)) +#define POP(low, high) ((void) (--top, (low = top->lo), (high = top->hi))) +#define STACK_NOT_EMPTY (stack < top) + + +/* Order size using quicksort. This implementation incorporates + four optimizations discussed in Sedgewick: + + 1. Non-recursive, using an explicit stack of pointer that store the + next array partition to sort. To save time, this maximum amount + of space required to store an array of MAX_INT is allocated on the + stack. Assuming a 32-bit integer, this needs only 32 * + sizeof(stack_node) == 136 bits. Pretty cheap, actually. + + 2. Chose the pivot element using a median-of-three decision tree. + This reduces the probability of selecting a bad pivot value and + eliminates certain extraneous comparisons. + + 3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving + insertion sort to order the MAX_THRESH items within each partition. + This is a big win, since insertion sort is faster for small, mostly + sorted array segements. + + 4. The larger of the two sub-partitions is always pushed onto the + stack first, with the algorithm then concentrating on the + smaller partition. This *guarantees* no more than log (n) + stack size is needed (actually O(1) in this case)! */ + +void +DEFUN(_quicksort, (pbase, total_elems, size, cmp), + PTR CONST pbase AND size_t total_elems AND size_t size AND + int EXFUN((*cmp), (CONST PTR, CONST PTR))) +{ + register char *base_ptr = (char *) pbase; + + /* Allocating SIZE bytes for a pivot buffer facilitates a better + algorithm below since we can do comparisons directly on the pivot. */ + char *pivot_buffer = (char *) __alloca (size); + CONST size_t max_thresh = MAX_THRESH * size; + + if (total_elems == 0) + /* Avoid lossage with unsigned arithmetic below. */ + return; + + if (total_elems > MAX_THRESH) + { + char *lo = base_ptr; + char *hi = &lo[size * (total_elems - 1)]; + /* Largest size needed for 32-bit int!!! */ + stack_node stack[STACK_SIZE]; + stack_node *top = stack + 1; + + while (STACK_NOT_EMPTY) + { + char *left_ptr; + char *right_ptr; + + char *pivot = pivot_buffer; + + /* Select median value from among LO, MID, and HI. Rearrange + LO and HI so the three values are sorted. This lowers the + probability of picking a pathological pivot value and + skips a comparison for both the LEFT_PTR and RIGHT_PTR. */ + + char *mid = lo + size * ((hi - lo) / size >> 1); + + if ((*cmp)((PTR) mid, (PTR) lo) < 0) + SWAP(mid, lo, size); + if ((*cmp)((PTR) hi, (PTR) mid) < 0) + SWAP(mid, hi, size); + else + goto jump_over; + if ((*cmp)((PTR) mid, (PTR) lo) < 0) + SWAP(mid, lo, size); + jump_over:; + memcpy(pivot, mid, size); + pivot = pivot_buffer; + + left_ptr = lo + size; + right_ptr = hi - size; + + /* Here's the famous ``collapse the walls'' section of quicksort. + Gotta like those tight inner loops! They are the main reason + that this algorithm runs much faster than others. */ + do + { + while ((*cmp)((PTR) left_ptr, (PTR) pivot) < 0) + left_ptr += size; + + while ((*cmp)((PTR) pivot, (PTR) right_ptr) < 0) + right_ptr -= size; + + if (left_ptr < right_ptr) + { + SWAP(left_ptr, right_ptr, size); + left_ptr += size; + right_ptr -= size; + } + else if (left_ptr == right_ptr) + { + left_ptr += size; + right_ptr -= size; + break; + } + } + while (left_ptr <= right_ptr); + + /* Set up pointers for next iteration. First determine whether + left and right partitions are below the threshold size. If so, + ignore one or both. Otherwise, push the larger partition's + bounds on the stack and continue sorting the smaller one. */ + + if ((size_t) (right_ptr - lo) <= max_thresh) + { + if ((size_t) (hi - left_ptr) <= max_thresh) + /* Ignore both small partitions. */ + POP(lo, hi); + else + /* Ignore small left partition. */ + lo = left_ptr; + } + else if ((size_t) (hi - left_ptr) <= max_thresh) + /* Ignore small right partition. */ + hi = right_ptr; + else if ((right_ptr - lo) > (hi - left_ptr)) + { + /* Push larger left partition indices. */ + PUSH(lo, right_ptr); + lo = left_ptr; + } + else + { + /* Push larger right partition indices. */ + PUSH(left_ptr, hi); + hi = right_ptr; + } + } + } + + /* Once the BASE_PTR array is partially sorted by quicksort the rest + is completely sorted using insertion sort, since this is efficient + for partitions below MAX_THRESH size. BASE_PTR points to the beginning + of the array to sort, and END_PTR points at the very last element in + the array (*not* one beyond it!). */ + +#define min(x, y) ((x) < (y) ? (x) : (y)) + + { + char *CONST end_ptr = &base_ptr[size * (total_elems - 1)]; + char *tmp_ptr = base_ptr; + char *thresh = min(end_ptr, base_ptr + max_thresh); + register char *run_ptr; + + /* Find smallest element in first threshold and place it at the + array's beginning. This is the smallest array element, + and the operation speeds up insertion sort's inner loop. */ + + for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size) + if ((*cmp)((PTR) run_ptr, (PTR) tmp_ptr) < 0) + tmp_ptr = run_ptr; + + if (tmp_ptr != base_ptr) + SWAP(tmp_ptr, base_ptr, size); + + /* Insertion sort, running from left-hand-side up to right-hand-side. */ + + run_ptr = base_ptr + size; + while ((run_ptr += size) <= end_ptr) + { + tmp_ptr = run_ptr - size; + while ((*cmp)((PTR) run_ptr, (PTR) tmp_ptr) < 0) + tmp_ptr -= size; + + tmp_ptr += size; + if (tmp_ptr != run_ptr) + { + char *trav; + + trav = run_ptr + size; + while (--trav >= run_ptr) + { + char c = *trav; + char *hi, *lo; + + for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo) + *hi = *lo; + *hi = c; + } + } + } + } +} + diff --git a/stdlib/rand.c b/stdlib/rand.c new file mode 100644 index 0000000000..1353432850 --- /dev/null +++ b/stdlib/rand.c @@ -0,0 +1,30 @@ +/* Copyright (C) 1991 Free Software Foundation, Inc. +This file is part of the GNU C Library. + +The GNU C Library is free software; you can redistribute it and/or +modify it under the terms of the GNU Library General Public License as +published by the Free Software Foundation; either version 2 of the +License, or (at your option) any later version. + +The GNU C Library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Library General Public License for more details. + +You should have received a copy of the GNU Library General Public +License along with the GNU C Library; see the file COPYING.LIB. If +not, write to the Free Software Foundation, Inc., 675 Mass Ave, +Cambridge, MA 02139, USA. */ + +#include +#include + +#undef rand + + +/* Return a random integer between 0 and RAND_MAX. */ +int +DEFUN_VOID(rand) +{ + return (int) __random(); +} diff --git a/stdlib/random.c b/stdlib/random.c new file mode 100644 index 0000000000..fb32b36b87 --- /dev/null +++ b/stdlib/random.c @@ -0,0 +1,357 @@ +/* + * Copyright (c) 1983 Regents of the University of California. + * All rights reserved. + * + * Redistribution and use in source and binary forms are permitted + * provided that the above copyright notice and this paragraph are + * duplicated in all such forms and that any documentation, + * advertising materials, and other materials related to such + * distribution and use acknowledge that the software was developed + * by the University of California, Berkeley. The name of the + * University may not be used to endorse or promote products derived + * from this software without specific prior written permission. + * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED + * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. + */ + +/* + * This is derived from the Berkeley source: + * @(#)random.c 5.5 (Berkeley) 7/6/88 + * It was reworked for the GNU C Library by Roland McGrath. + */ + +#include +#include +#include +#include +#include + + +/* 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() function 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 thi + 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 + separation between the two lower order coefficients of the trinomial. */ + +/* Linear congruential. */ +#define TYPE_0 0 +#define BREAK_0 8 +#define DEG_0 0 +#define SEP_0 0 + +/* x**7 + x**3 + 1. */ +#define TYPE_1 1 +#define BREAK_1 32 +#define DEG_1 7 +#define SEP_1 3 + +/* x**15 + x + 1. */ +#define TYPE_2 2 +#define BREAK_2 64 +#define DEG_2 15 +#define SEP_2 1 + +/* x**31 + x**3 + 1. */ +#define TYPE_3 3 +#define BREAK_3 128 +#define DEG_3 31 +#define SEP_3 3 + +/* x**63 + x + 1. */ +#define TYPE_4 4 +#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 int randtbl[DEG_3 + 1] = + { + TYPE_3, + -851904987, -43806228, -2029755270, 1390239686, -1912102820, + -485608943, 1969813258, -1590463333, -1944053249, 455935928, 508023712, + -1714531963, 1800685987, -2015299881, 654595283, -1149023258, + -1470005550, -1143256056, -1325577603, -1568001885, 1275120390, + -607508183, -205999574, -1696891592, 1492211999, -1528267240, + -952028296, -189082757, 362343714, 1424981831, 2039449641, + }; + +/* 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 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 int *fptr = &randtbl[SEP_3 + 1]; +static long int *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 int *state = &randtbl[1]; + +static int rand_type = TYPE_3; +static int rand_deg = DEG_3; +static int rand_sep = SEP_3; + +static long int *end_ptr = &randtbl[sizeof(randtbl) / sizeof(randtbl[0])]; + +/* 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 +DEFUN(__srandom, (x), unsigned int x) +{ + state[0] = x; + if (rand_type != TYPE_0) + { + register long int i; + for (i = 1; i < rand_deg; ++i) + state[i] = (1103515145 * state[i - 1]) + 12345; + fptr = &state[rand_sep]; + rptr = &state[0]; + for (i = 0; i < 10 * rand_deg; ++i) + (void) __random(); + } +} + +weak_alias (__srandom, srandom) +weak_alias (__srandom, srand) + +/* 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. */ +PTR +DEFUN(__initstate, (seed, arg_state, n), + unsigned int seed AND PTR arg_state AND size_t n) +{ + PTR ostate = (PTR) &state[-1]; + + if (rand_type == TYPE_0) + state[-1] = rand_type; + else + state[-1] = (MAX_TYPES * (rptr - state)) + rand_type; + if (n < BREAK_1) + { + if (n < BREAK_0) + { + errno = EINVAL; + return NULL; + } + 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 int *) arg_state)[1]; /* First location. */ + /* Must set END_PTR before srandom. */ + end_ptr = &state[rand_deg]; + __srandom(seed); + if (rand_type == TYPE_0) + state[-1] = rand_type; + else + state[-1] = (MAX_TYPES * (rptr - state)) + rand_type; + + return ostate; +} + +weak_alias (__initstate, initstate) + +/* 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. */ +PTR +DEFUN(__setstate, (arg_state), PTR arg_state) +{ + register long int *new_state = (long int *) arg_state; + register int type = new_state[0] % MAX_TYPES; + register int rear = new_state[0] / MAX_TYPES; + PTR ostate = (PTR) &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: + /* State info munged. */ + errno = EINVAL; + return NULL; + } + + state = &new_state[1]; + if (rand_type != TYPE_0) + { + rptr = &state[rear]; + fptr = &state[(rear + rand_sep) % rand_deg]; + } + /* Set end_ptr too. */ + end_ptr = &state[rand_deg]; + + return ostate; +} + +weak_alias (__setstate, setstate) + +/* 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 ther 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 int +DEFUN_VOID(__random) +{ + if (rand_type == TYPE_0) + { + state[0] = ((state[0] * 1103515245) + 12345) & LONG_MAX; + return state[0]; + } + else + { + long int i; + *fptr += *rptr; + /* Chucking least random bit. */ + i = (*fptr >> 1) & LONG_MAX; + ++fptr; + if (fptr >= end_ptr) + { + fptr = state; + ++rptr; + } + else + { + ++rptr; + if (rptr >= end_ptr) + rptr = state; + } + return i; + } +} + +weak_alias (__random, random) diff --git a/stdlib/stdlib.h b/stdlib/stdlib.h new file mode 100644 index 0000000000..d64a2ffb7c --- /dev/null +++ b/stdlib/stdlib.h @@ -0,0 +1,289 @@ +/* Copyright (C) 1991, 1992, 1993, 1994, 1995 Free Software Foundation, Inc. +This file is part of the GNU C Library. + +The GNU C Library is free software; you can redistribute it and/or +modify it under the terms of the GNU Library General Public License as +published by the Free Software Foundation; either version 2 of the +License, or (at your option) any later version. + +The GNU C Library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Library General Public License for more details. + +You should have received a copy of the GNU Library General Public +License along with the GNU C Library; see the file COPYING.LIB. If +not, write to the, 1992 Free Software Foundation, Inc., 675 Mass Ave, +Cambridge, MA 02139, USA. */ + +/* + * ANSI Standard: 4.10 GENERAL UTILITIES + */ + +#ifndef _STDLIB_H + +#define _STDLIB_H 1 +#include + +/* Get size_t, wchar_t and NULL from . */ +#define __need_size_t +#define __need_wchar_t +#define __need_NULL +#include + +#define __need_Emath +#include + +__BEGIN_DECLS + +/* Returned by `div'. */ +typedef struct + { + int quot; /* Quotient. */ + int rem; /* Remainder. */ + } div_t; + +/* Returned by `ldiv'. */ +typedef struct + { + long int quot; /* Quotient. */ + long int rem; /* Remainder. */ + } ldiv_t; + + +/* The largest number rand will return (same as INT_MAX). */ +#define RAND_MAX 2147483647 + + +/* We define these the same for all machines. + Changes from this to the outside world should be done in `_exit'. */ +#define EXIT_FAILURE 1 /* Failing exit status. */ +#define EXIT_SUCCESS 0 /* Successful exit status. */ + + +/* Maximum length of a multibyte character in the current locale. + This is just one until the fancy locale support is finished. */ +#define MB_CUR_MAX 1 + + +/* Convert a string to a floating-point number. */ +extern double atof __P ((__const char *__nptr)); +/* Convert a string to an integer. */ +extern int atoi __P ((__const char *__nptr)); +/* Convert a string to a long integer. */ +extern long int atol __P ((__const char *__nptr)); + +/* Convert a string to a floating-point number. */ +extern double strtod __P ((__const char *__nptr, char **__endptr)); + +#ifdef __USE_GNU +/* Likewise for `float' and `long double' sizes of floating-point numbers. */ +extern float __strtof __P ((__const char *__nptr, char **__endptr)); +extern float strtof __P ((__const char *__nptr, char **__endptr)); +extern __long_double_t __strtold __P ((__const char *__nptr, char **__endptr)); +extern __long_double_t strtold __P ((__const char *__nptr, char **__endptr)); +#endif + +/* Convert a string to a long integer. */ +extern long int strtol __P ((__const char *__nptr, char **__endptr, + int __base)); +/* Convert a string to an unsigned long integer. */ +extern unsigned long int strtoul __P ((__const char *__nptr, + char **__endptr, int __base)); + +#if defined (__GNUC__) && defined (__USE_BSD) +/* Convert a string to a quadword integer. */ +extern long long int strtoq __P ((__const char *__nptr, char **__endptr, + int __base)); +/* Convert a string to an unsigned quadword integer. */ +extern unsigned long long int strtouq __P ((__const char *__nptr, + char **__endptr, int __base)); +#endif /* GCC and use BSD. */ + +#if defined (__OPTIMIZE__) && __GNUC__ >= 2 +extern __inline double atof (__const char *__nptr) +{ return strtod(__nptr, (char **) NULL); } +extern __inline int atoi (__const char *__nptr) +{ return (int) strtol (__nptr, (char **) NULL, 10); } +extern __inline long int atol (__const char *__nptr) +{ return strtol (__nptr, (char **) NULL, 10); } +#endif /* Optimizing GCC >=2. */ + + +/* Return a random integer between 0 and RAND_MAX inclusive. */ +extern int rand __P ((void)); +/* Seed the random number generator with the given number. */ +extern void srand _