release/src/router/gmp/gen-bases.c

   1 /* Generate mp_bases data.
   2
   3 Copyright 1991, 1993, 1994, 1996, 2000, 2002, 2004, 2011, 2012 Free Software
   4 Foundation, Inc.
   5
   6 This file is part of the GNU MP Library.
   7
   8 The GNU MP Library is free software; you can redistribute it and/or modify
   9 it under the terms of either:
  10
  11   * the GNU Lesser General Public License as published by the Free
  12     Software Foundation; either version 3 of the License, or (at your
  13     option) any later version.
  14
  15 or
  16
  17   * the GNU General Public License as published by the Free Software
  18     Foundation; either version 2 of the License, or (at your option) any
  19     later version.
  20
  21 or both in parallel, as here.
  22
  23 The GNU MP Library is distributed in the hope that it will be useful, but
  24 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  25 or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  26 for more details.
  27
  28 You should have received copies of the GNU General Public License and the
  29 GNU Lesser General Public License along with the GNU MP Library.  If not,
  30 see https://www.gnu.org/licenses/.  */
  31
  32 #include "bootstrap.c"
  33
  34
  35 int    chars_per_limb;
  36 mpz_t  big_base;
  37 int    normalization_steps;
  38 mpz_t  big_base_inverted;
  39
  40 mpz_t  t;
  41
  42 #define POW2_P(n)  (((n) & ((n) - 1)) == 0)
  43
  44 unsigned int
  45 ulog2 (unsigned int x)
  46 {
  47   unsigned int i;
  48   for (i = 0;  x != 0;  i++)
  49     x >>= 1;
  50   return i;
  51 }
  52
  53 void
  54 generate (int limb_bits, int nail_bits, int base)
  55 {
  56   int  numb_bits = limb_bits - nail_bits;
  57
  58   mpz_set_ui (t, 1L);
  59   mpz_mul_2exp (t, t, numb_bits);
  60   mpz_set_ui (big_base, 1L);
  61   chars_per_limb = 0;
  62   for (;;)
  63     {
  64       mpz_mul_ui (big_base, big_base, (long) base);
  65       if (mpz_cmp (big_base, t) > 0)
  66         break;
  67       chars_per_limb++;
  68     }
  69
  70   mpz_ui_pow_ui (big_base, (long) base, (long) chars_per_limb);
  71
  72   normalization_steps = limb_bits - mpz_sizeinbase (big_base, 2);
  73
  74   mpz_set_ui (t, 1L);
  75   mpz_mul_2exp (t, t, 2*limb_bits - normalization_steps);
  76   mpz_tdiv_q (big_base_inverted, t, big_base);
  77   mpz_set_ui (t, 1L);
  78   mpz_mul_2exp (t, t, limb_bits);
  79   mpz_sub (big_base_inverted, big_base_inverted, t);
  80 }
  81
  82 void
  83 header (int limb_bits, int nail_bits)
  84 {
  85   int  numb_bits = limb_bits - nail_bits;
  86
  87   generate (limb_bits, nail_bits, 10);
  88
  89   printf ("/* This file generated by gen-bases.c - DO NOT EDIT. */\n");
  90   printf ("\n");
  91   printf ("#if GMP_NUMB_BITS != %d\n", numb_bits);
  92   printf ("Error, error, this data is for %d bits\n", numb_bits);
  93   printf ("#endif\n");
  94   printf ("\n");
  95   printf ("/* mp_bases[10] data, as literal values */\n");
  96   printf ("#define MP_BASES_CHARS_PER_LIMB_10      %d\n", chars_per_limb);
  97   printf ("#define MP_BASES_BIG_BASE_10            CNST_LIMB(0x");
  98   mpz_out_str (stdout, 16, big_base);
  99   printf (")\n");
 100   printf ("#define MP_BASES_BIG_BASE_INVERTED_10   CNST_LIMB(0x");
 101   mpz_out_str (stdout, 16, big_base_inverted);
 102   printf (")\n");
 103   printf ("#define MP_BASES_NORMALIZATION_STEPS_10 %d\n", normalization_steps);
 104 }
 105
 106
 107 #define EXTRA 16
 108
 109 /* Compute log(2)/log(b) as a fixnum. */
 110 void
 111 mp_2logb (mpz_t r, int bi, int prec)
 112 {
 113   mpz_t t, t2, two, b;
 114   int i;
 115
 116   mpz_init_set_ui (t, 1);
 117   mpz_mul_2exp (t, t, prec+EXTRA);
 118
 119   mpz_init (t2);
 120
 121   mpz_init_set_ui (two, 2);
 122   mpz_mul_2exp (two, two, prec+EXTRA);
 123
 124   mpz_set_ui (r, 0);
 125
 126   mpz_init_set_ui (b, bi);
 127   mpz_mul_2exp (b, b, prec+EXTRA);
 128
 129   for (i = prec-1; i >= 0; i--)
 130     {
 131       mpz_mul_2exp (b, b, prec+EXTRA);
 132       mpz_sqrt (b, b);
 133
 134       mpz_mul (t2, t, b);
 135       mpz_tdiv_q_2exp (t2, t2, prec+EXTRA);
 136
 137       if (mpz_cmp (t2, two) < 0)        /* not too large? */
 138         {
 139           mpz_setbit (r, i);            /* set next less significant bit */
 140           mpz_set (t, t2);              /* new value acceptable */
 141         }
 142     }
 143
 144   mpz_clear (t);
 145   mpz_clear (t2);
 146   mpz_clear (two);
 147   mpz_clear (b);
 148 }
 149
 150 void
 151 table (int limb_bits, int nail_bits)
 152 {
 153   int  numb_bits = limb_bits - nail_bits;
 154   int  base;
 155   mpz_t r, t, logb2, log2b;
 156
 157   mpz_init (r);
 158   mpz_init (t);
 159   mpz_init (logb2);
 160   mpz_init (log2b);
 161
 162   printf ("/* This file generated by gen-bases.c - DO NOT EDIT. */\n");
 163   printf ("\n");
 164   printf ("#include \"gmp.h\"\n");
 165   printf ("#include \"gmp-impl.h\"\n");
 166   printf ("\n");
 167   printf ("#if GMP_NUMB_BITS != %d\n", numb_bits);
 168   printf ("Error, error, this data is for %d bits\n", numb_bits);
 169   printf ("#endif\n");
 170   printf ("\n");
 171   puts ("const struct bases mp_bases[257] =\n{");
 172   puts ("  /*   0 */ { 0, 0, 0, 0, 0 },");
 173   puts ("  /*   1 */ { 0, 0, 0, 0, 0 },");
 174   for (base = 2; base <= 256; base++)
 175     {
 176       generate (limb_bits, nail_bits, base);
 177       mp_2logb (r, base, limb_bits + 8);
 178       mpz_tdiv_q_2exp (logb2, r, 8);
 179       mpz_set_ui (t, 1);
 180       mpz_mul_2exp (t, t, 2*limb_bits + 5);
 181       mpz_sub_ui (t, t, 1);
 182       mpz_add_ui (r, r, 1);
 183       mpz_tdiv_q (log2b, t, r);
 184
 185       printf ("  /* %3u */ { ", base);
 186       if (POW2_P (base))
 187         {
 188           mpz_set_ui (big_base, ulog2 (base) - 1);
 189           mpz_set_ui (big_base_inverted, 0);
 190         }
 191
 192       printf ("%u,", chars_per_limb);
 193       printf (" CNST_LIMB(0x");
 194       mpz_out_str (stdout, 16, logb2);
 195       printf ("), CNST_LIMB(0x");
 196       mpz_out_str (stdout, 16, log2b);
 197       printf ("), CNST_LIMB(0x");
 198       mpz_out_str (stdout, 16, big_base);
 199       printf ("), CNST_LIMB(0x");
 200       mpz_out_str (stdout, 16, big_base_inverted);
 201       printf (") },\n");
 202     }
 203
 204   puts ("};");
 205
 206   mpz_clear (r);
 207   mpz_clear (t);
 208   mpz_clear (logb2);
 209   mpz_clear (log2b);
 210
 211 }
 212
 213 int
 214 main (int argc, char **argv)
 215 {
 216   int  limb_bits, nail_bits;
 217
 218   mpz_init (big_base);
 219   mpz_init (big_base_inverted);
 220   mpz_init (t);
 221
 222   if (argc != 4)
 223     {
 224       fprintf (stderr, "Usage: gen-bases <header|table> <limbbits> <nailbits>\n");
 225       exit (1);
 226     }
 227
 228   limb_bits = atoi (argv[2]);
 229   nail_bits = atoi (argv[3]);
 230
 231   if (limb_bits <= 0
 232       || nail_bits < 0
 233       || nail_bits >= limb_bits)
 234     {
 235       fprintf (stderr, "Invalid limb/nail bits: %d %d\n",
 236                limb_bits, nail_bits);
 237       exit (1);
 238     }
 239
 240   if (strcmp (argv[1], "header") == 0)
 241     header (limb_bits, nail_bits);
 242   else if (strcmp (argv[1], "table") == 0)
 243     table (limb_bits, nail_bits);
 244   else
 245     {
 246       fprintf (stderr, "Invalid header/table choice: %s\n", argv[1]);
 247       exit (1);
 248     }
 249
 250   return 0;
 251 }