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