From 11da511c784eca003deb90c23570f0873954e0de Mon Sep 17 00:00:00 2001 From: Duncan Wilkie Date: Sat, 18 Nov 2023 06:11:09 -0600 Subject: Initial commit. --- gmp-6.3.0/gen-bases.c | 265 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 265 insertions(+) create mode 100644 gmp-6.3.0/gen-bases.c (limited to 'gmp-6.3.0/gen-bases.c') diff --git a/gmp-6.3.0/gen-bases.c b/gmp-6.3.0/gen-bases.c new file mode 100644 index 0000000..5f5e7ed --- /dev/null +++ b/gmp-6.3.0/gen-bases.c @@ -0,0 +1,265 @@ +/* Generate mp_bases data. + +Copyright 1991, 1993, 1994, 1996, 2000, 2002, 2004, 2011, 2012, +2015-2018 Free Software Foundation, Inc. + +This file is part of the GNU MP Library. + +The GNU MP Library is free software; you can redistribute it and/or modify +it under the terms of either: + + * the GNU Lesser General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your + option) any later version. + +or + + * the GNU General Public License as published by the Free Software + Foundation; either version 2 of the License, or (at your option) any + later version. + +or both in parallel, as here. + +The GNU MP 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 General Public License +for more details. + +You should have received copies of the GNU General Public License and the +GNU Lesser General Public License along with the GNU MP Library. If not, +see https://www.gnu.org/licenses/. */ + +#include "bootstrap.c" + + +int chars_per_limb; +int big_base_ctz; +mpz_t big_base; +int normalization_steps; +mpz_t big_base_inverted; +mpz_t big_base_binverted; + +mpz_t t; + +#define POW2_P(n) (((n) & ((n) - 1)) == 0) + +unsigned int +ulog2 (unsigned int x) +{ + unsigned int i; + for (i = 0; x != 0; i++) + x >>= 1; + return i; +} + +void +binvert (int numb_bits) +{ + mpz_t bbo; + + mpz_init_set (bbo, big_base); + big_base_ctz = mpz_make_odd (bbo); + mpz_invert_2exp (big_base_binverted, bbo, numb_bits); +} + +void +generate (int limb_bits, int nail_bits, int base) +{ + int numb_bits = limb_bits - nail_bits; + + mpz_set_ui (t, 1L); + mpz_mul_2exp (t, t, numb_bits); + mpz_set_ui (big_base, (long) base); + chars_per_limb = 0; + while (mpz_cmp (big_base, t) <= 0) + { + mpz_mul_ui (big_base, big_base, (long) base); + chars_per_limb++; + } + + mpz_ui_pow_ui (big_base, (long) base, (long) chars_per_limb); + + normalization_steps = limb_bits - mpz_sizeinbase (big_base, 2); + + mpz_set_ui (t, 1L); + mpz_mul_2exp (t, t, 2*limb_bits - normalization_steps); + mpz_tdiv_q (big_base_inverted, t, big_base); + mpz_clrbit (big_base_inverted, limb_bits); + + binvert (numb_bits); +} + +void +header (int limb_bits, int nail_bits) +{ + int numb_bits = limb_bits - nail_bits; + + generate (limb_bits, nail_bits, 10); + + printf ("/* This file generated by gen-bases.c - DO NOT EDIT. */\n"); + printf ("\n"); + printf ("#if GMP_NUMB_BITS != %d\n", numb_bits); + printf ("Error, error, this data is for %d bits\n", numb_bits); + printf ("#endif\n"); + printf ("\n"); + printf ("/* mp_bases[10] data, as literal values */\n"); + printf ("#define MP_BASES_CHARS_PER_LIMB_10 %d\n", chars_per_limb); + printf ("#define MP_BASES_BIG_BASE_CTZ_10 %d\n", big_base_ctz); + printf ("#define MP_BASES_BIG_BASE_10 CNST_LIMB(0x"); + mpz_out_str (stdout, 16, big_base); + printf (")\n"); + printf ("#define MP_BASES_BIG_BASE_INVERTED_10 CNST_LIMB(0x"); + mpz_out_str (stdout, 16, big_base_inverted); + printf (")\n"); + printf ("#define MP_BASES_BIG_BASE_BINVERTED_10 CNST_LIMB(0x"); + mpz_out_str (stdout, 16, big_base_binverted); + printf (")\n"); + printf ("#define MP_BASES_NORMALIZATION_STEPS_10 %d\n", normalization_steps); +} + + +#define EXTRA 16 + +/* Compute log(2)/log(b) as a fixnum. */ +void +mp_2logb (mpz_t r, int bi, int prec) +{ + mpz_t t, t2, two, b; + int i; + + mpz_init (t); + mpz_setbit (t, prec + EXTRA); + + mpz_init (t2); + + mpz_init (two); + mpz_setbit (two, prec + EXTRA + 1); + + mpz_set_ui (r, 0); + + mpz_init_set_ui (b, bi); + mpz_mul_2exp (b, b, prec+EXTRA); + + for (i = prec-1; i >= 0; i--) + { + mpz_mul_2exp (b, b, prec+EXTRA); + mpz_sqrt (b, b); + + mpz_mul (t2, t, b); + mpz_tdiv_q_2exp (t2, t2, prec+EXTRA); + + if (mpz_cmp (t2, two) < 0) /* not too large? */ + { + mpz_setbit (r, i); /* set next less significant bit */ + mpz_swap (t, t2); /* new value acceptable */ + } + } + + mpz_clear (t); + mpz_clear (t2); + mpz_clear (two); + mpz_clear (b); +} + +void +table (int limb_bits, int nail_bits) +{ + int numb_bits = limb_bits - nail_bits; + int base; + mpz_t r, t, logb2, log2b; + + mpz_init (r); + mpz_init (t); + mpz_init (logb2); + mpz_init (log2b); + + printf ("/* This file generated by gen-bases.c - DO NOT EDIT. */\n"); + printf ("\n"); + printf ("#include \"gmp-impl.h\"\n"); + printf ("\n"); + printf ("#if GMP_NUMB_BITS != %d\n", numb_bits); + printf ("Error, error, this data is for %d bits\n", numb_bits); + printf ("#endif\n"); + printf ("\n"); + puts ("const struct bases mp_bases[257] =\n{"); + puts (" /* 0 */ { 0, 0, 0, 0, 0 },"); + puts (" /* 1 */ { 0, 0, 0, 0, 0 },"); + for (base = 2; base <= 256; base++) + { + generate (limb_bits, nail_bits, base); + mp_2logb (r, base, limb_bits + 8); + mpz_tdiv_q_2exp (logb2, r, 8); + mpz_set_ui (t, 1); + mpz_mul_2exp (t, t, 2*limb_bits + 5); + mpz_sub_ui (t, t, 1); + mpz_add_ui (r, r, 1); + mpz_tdiv_q (log2b, t, r); + + printf (" /* %3u */ { ", base); + if (POW2_P (base)) + { + mpz_set_ui (big_base, ulog2 (base) - 1); + mpz_set_ui (big_base_inverted, 0); + } + + printf ("%u,", chars_per_limb); + printf (" CNST_LIMB(0x"); + mpz_out_str (stdout, 16, logb2); + printf ("), CNST_LIMB(0x"); + mpz_out_str (stdout, 16, log2b); + printf ("), CNST_LIMB(0x"); + mpz_out_str (stdout, 16, big_base); + printf ("), CNST_LIMB(0x"); + mpz_out_str (stdout, 16, big_base_inverted); + printf (") },\n"); + } + + puts ("};"); + + mpz_clear (r); + mpz_clear (t); + mpz_clear (logb2); + mpz_clear (log2b); + +} + +int +main (int argc, char **argv) +{ + int limb_bits, nail_bits; + + mpz_init (big_base); + mpz_init (big_base_inverted); + mpz_init (big_base_binverted); + mpz_init (t); + + if (argc != 4) + { + fprintf (stderr, "Usage: gen-bases \n"); + exit (1); + } + + limb_bits = atoi (argv[2]); + nail_bits = atoi (argv[3]); + + if (limb_bits <= 0 + || nail_bits < 0 + || nail_bits >= limb_bits) + { + fprintf (stderr, "Invalid limb/nail bits: %d %d\n", + limb_bits, nail_bits); + exit (1); + } + + if (strcmp (argv[1], "header") == 0) + header (limb_bits, nail_bits); + else if (strcmp (argv[1], "table") == 0) + table (limb_bits, nail_bits); + else + { + fprintf (stderr, "Invalid header/table choice: %s\n", argv[1]); + exit (1); + } + + return 0; +} -- cgit v1.2.3