1 /* Generate mp_bases data.
2
3 Copyright 1991, 1993, 1994, 1996, 2000, 2002, 2004, 2011, 2012,
4 2015-2018 Free Software 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 int big_base_ctz;
37 mpz_t big_base;
38 int normalization_steps;
39 mpz_t big_base_inverted;
40 mpz_t big_base_binverted;
41
42 mpz_t t;
43
44 #define POW2_P(n) (((n) & ((n) - 1)) == 0)
45
46 unsigned int
ulog2(unsigned int x)47 ulog2 (unsigned int x)
48 {
49 unsigned int i;
50 for (i = 0; x != 0; i++)
51 x >>= 1;
52 return i;
53 }
54
55 void
binvert(int numb_bits)56 binvert (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
65 void
generate(int limb_bits,int nail_bits,int base)66 generate (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
92 void
header(int limb_bits,int nail_bits)93 header (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. */
124 void
mp_2logb(mpz_t r,int bi,int prec)125 mp_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
164 void
table(int limb_bits,int nail_bits)165 table (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
226 int
main(int argc,char ** argv)227 main (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