diff options
author | Bruno Haible <bruno@clisp.org> | 2001-09-09 13:47:04 +0000 |
---|---|---|
committer | Bruno Haible <bruno@clisp.org> | 2001-09-09 13:47:04 +0000 |
commit | 9d65a34db5e6dcec46eadd6d6f0375982143ce0d (patch) | |
tree | 3c4952c62366e6d41778ad22cfd374aff1addc8d | |
parent | 61f6bc47b3c8068a969b9afce5d674f099b6c6c0 (diff) | |
download | external_gettext-9d65a34db5e6dcec46eadd6d6f0375982143ce0d.zip external_gettext-9d65a34db5e6dcec46eadd6d6f0375982143ce0d.tar.gz external_gettext-9d65a34db5e6dcec46eadd6d6f0375982143ce0d.tar.bz2 |
Move the gcd function to lib/.
-rw-r--r-- | lib/ChangeLog | 7 | ||||
-rw-r--r-- | lib/Makefile.am | 6 | ||||
-rw-r--r-- | lib/gcd.c | 80 | ||||
-rw-r--r-- | lib/gcd.h | 33 | ||||
-rw-r--r-- | src/ChangeLog | 4 | ||||
-rw-r--r-- | src/format-lisp.c | 65 |
6 files changed, 128 insertions, 67 deletions
diff --git a/lib/ChangeLog b/lib/ChangeLog index 56a9552..03e041a 100644 --- a/lib/ChangeLog +++ b/lib/ChangeLog @@ -1,5 +1,12 @@ 2001-09-02 Bruno Haible <haible@clisp.cons.org> + * gcd.h: New file. + * gcd.c: New file. + * Makefile.am (libnlsut_a_SOURCES): Add gcd.c. + (noinst_HEADERS): Add gcd.h. + +2001-09-02 Bruno Haible <haible@clisp.cons.org> + * pipe.h: Ensure pid_t gets declared. * pipe-bidi.c: Include pipe.h. * pipe-in.c: Likewise. diff --git a/lib/Makefile.am b/lib/Makefile.am index 86ea5cc..488ac0a 100644 --- a/lib/Makefile.am +++ b/lib/Makefile.am @@ -28,13 +28,13 @@ stdbool.h.in \ gen-lbrkprop.c 3level.h libnlsut_a_SOURCES = basename.c c-ctype.c concatpath.c findprog.c fstrcmp.c \ -full-write.c getopt.c getopt1.c hash.c linebreak.c localcharset.c mbswidth.c \ -obstack.c pipe-bidi.c pipe-in.c pipe-out.c progname.c safe-read.c \ +full-write.c gcd.c getopt.c getopt1.c hash.c linebreak.c localcharset.c \ +mbswidth.c obstack.c pipe-bidi.c pipe-in.c pipe-out.c progname.c safe-read.c \ wait-process.c xerror.c xgetcwd.c xmalloc.c xstrdup.c libnlsut_a_LIBADD = @ALLOCA@ @LIBOBJS@ -noinst_HEADERS = c-ctype.h error.h findprog.h fstrcmp.h full-write.h \ +noinst_HEADERS = c-ctype.h error.h findprog.h fstrcmp.h full-write.h gcd.h \ getline.h getopt.h hash.h lbrkprop.h linebreak.h mbswidth.h obstack.h \ pathmax.h pipe.h progname.h safe-read.h system.h utf8-ucs4.h utf16-ucs4.h \ wait-process.h xerror.h diff --git a/lib/gcd.c b/lib/gcd.c new file mode 100644 index 0000000..a2dfc52 --- /dev/null +++ b/lib/gcd.c @@ -0,0 +1,80 @@ +/* Arithmetic. + Copyright (C) 2001 Free Software Foundation, Inc. + Written by Bruno Haible <haible@clisp.cons.org>, 2001. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2, or (at your option) + any later version. + + This program 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 General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software Foundation, + Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ + +/* Specification. */ +#include "gcd.h" + +/* Return the greatest common divisor of a > 0 and b > 0. */ +unsigned int +gcd (a, b) + unsigned int a; + unsigned int b; +{ + /* Why no division, as in Euclid's algorithm? Because in Euclid's algorithm + the division result floor(a/b) or floor(b/a) is very often = 1 or = 2, + and nearly always < 8. A sequence of a few subtractions and tests is + faster than a division. */ + /* Why not Euclid's algorithm? Because the two integers can be shifted by 1 + bit in a single instruction, and the algorithm uses fewer variables than + Euclid's algorithm. */ + + unsigned int c = a | b; + c = c ^ (c - 1); + /* c = largest power of 2 that divides a and b. */ + + if (a & c) + { + if (b & c) + goto odd_odd; + else + goto odd_even; + } + else + { + if (b & c) + goto even_odd; + else + abort (); + } + + for (;;) + { + odd_odd: /* a/c and b/c both odd */ + if (a == b) + break; + if (a > b) + { + a = a - b; + even_odd: /* a/c even, b/c odd */ + do + a = a >> 1; + while ((a & c) == 0); + } + else + { + b = b - a; + odd_even: /* a/c odd, b/c even */ + do + b = b >> 1; + while ((b & c) == 0); + } + } + + /* a = b */ + return a; +} diff --git a/lib/gcd.h b/lib/gcd.h new file mode 100644 index 0000000..8fadde2 --- /dev/null +++ b/lib/gcd.h @@ -0,0 +1,33 @@ +/* Arithmetic. + Copyright (C) 2001 Free Software Foundation, Inc. + Written by Bruno Haible <haible@clisp.cons.org>, 2001. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2, or (at your option) + any later version. + + This program 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 General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software Foundation, + Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ + +#ifndef _GCD_H +#define _GCD_H + +#ifndef PARAMS +# if defined (__GNUC__) || __STDC__ +# define PARAMS(args) args +# else +# define PARAMS(args) () +# endif +#endif + +/* Return the greatest common divisor of a > 0 and b > 0. */ +extern unsigned int gcd PARAMS ((unsigned int a, unsigned int b)); + +#endif /* _GCD_H */ diff --git a/src/ChangeLog b/src/ChangeLog index 4c26d42..27c8a5b 100644 --- a/src/ChangeLog +++ b/src/ChangeLog @@ -1,3 +1,7 @@ +2001-09-02 Bruno Haible <haible@clisp.cons.org> + + * format-lisp.c (gcd): Remove function. Include "gcd.h" instead. + 2001-09-03 Bruno Haible <haible@clisp.cons.org> * xgettext.c (usage): Mention ObjectiveC and Java. diff --git a/src/format-lisp.c b/src/format-lisp.c index 482e082..b8fc090 100644 --- a/src/format-lisp.c +++ b/src/format-lisp.c @@ -25,6 +25,7 @@ #include "format.h" #include "c-ctype.h" +#include "gcd.h" #include "system.h" #include "error.h" #include "progname.h" @@ -127,7 +128,6 @@ struct param /* Prototypes for local functions. Needed to ensure compiler checking of function argument counts despite of K&R C function definition syntax. */ #define union make_union -static unsigned int gcd PARAMS ((unsigned int a, unsigned int b)); static void verify_element PARAMS ((const struct format_arg * e)); static void verify_list PARAMS ((const struct format_arg_list *list)); static inline void free_element PARAMS ((struct format_arg *element)); @@ -232,69 +232,6 @@ static bool format_check PARAMS ((const lex_pos_ty *pos, void *msgid_descr, void *msgstr_descr)); -/* ============================== Arithmetic ============================== */ - -/* Return the greatest common divisor of a > 0 and b > 0. */ -static unsigned int -gcd (a, b) - unsigned int a; - unsigned int b; -{ - /* Why no division, as in Euclid's algorithm? Because in Euclid's algorithm - the division result floor(a/b) or floor(b/a) is very often = 1 or = 2, - and nearly always < 8. A sequence of a few subtractions and tests is - faster than a division. */ - /* Why not Euclid's algorithm? Because the two integers can be shifted by 1 - bit in a single instruction, and the algorithm uses fewer variables than - Euclid's algorithm. */ - - unsigned int c = a | b; - c = c ^ (c - 1); - /* c = largest power of 2 that divides a and b. */ - - if (a & c) - { - if (b & c) - goto odd_odd; - else - goto odd_even; - } - else - { - if (b & c) - goto even_odd; - else - abort (); - } - - for (;;) - { - odd_odd: /* a/c and b/c both odd */ - if (a == b) - break; - if (a > b) - { - a = a - b; - even_odd: /* a/c even, b/c odd */ - do - a = a >> 1; - while ((a & c) == 0); - } - else - { - b = b - a; - odd_even: /* a/c odd, b/c even */ - do - b = b >> 1; - while ((b & c) == 0); - } - } - - /* a = b */ - return a; -} - - /* ======================= Verify a format_arg_list ======================= */ /* Verify some invariants. */ |