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