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