1/* Generate Fibonacci table data.
2
3Copyright 2001, 2002, 2004 Free Software Foundation, Inc.
4
5This file is part of the GNU MP Library.
6
7The GNU MP Library is free software; you can redistribute it and/or modify
8it under the terms of the GNU Lesser General Public License as published by
9the Free Software Foundation; either version 3 of the License, or (at your
10option) any later version.
11
12The GNU MP Library is distributed in the hope that it will be useful, but
13WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
15License for more details.
16
17You should have received a copy of the GNU Lesser General Public License
18along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
19
20#include <stdio.h>
21#include "dumbmp.c"
22
23mpz_t  *f;
24int    fnum, fib_limit, luc_limit;
25
26void
27generate (int numb_bits)
28{
29  mpz_t  limit, l;
30  int    falloc, i;
31
32  mpz_init_set_ui (limit, 1L);
33  mpz_mul_2exp (limit, limit, numb_bits);
34
35  /* fib(2n) > 2^n, so use 2n as a limit for the table size */
36  falloc = 2 * numb_bits;
37  f = (mpz_t *) xmalloc (falloc * sizeof (*f));
38
39  mpz_init_set_ui (f[0], 1L);  /* F[-1] */
40  mpz_init_set_ui (f[1], 0L);  /* F[0] */
41
42  mpz_init (l);
43
44  for (i = 2; ; i++)
45    {
46      ASSERT (i < falloc);
47
48      /* F[i] = F[i-1] + F[i-2] */
49      mpz_init (f[i]);
50      mpz_add (f[i], f[i-1], f[i-2]);
51      if (mpz_cmp (f[i], limit) >= 0)
52        break;
53
54      fnum = i+1;
55      fib_limit = i-1;
56
57      /* L[i] = F[i]+2*F[i-1] */
58      mpz_add (l, f[i], f[i-1]);
59      mpz_add (l, l, f[i-1]);
60
61      if (mpz_cmp (l, limit) < 0)
62        luc_limit = i-1;
63    }
64
65  mpz_clear (limit);
66}
67
68
69void
70header (int numb_bits)
71{
72  printf ("/* This file generated by gen-fib.c - DO NOT EDIT. */\n");
73  printf ("\n");
74  printf ("#if GMP_NUMB_BITS != %d\n", numb_bits);
75  printf ("Error, error, this data is for %d bits\n", numb_bits);
76  printf ("#endif\n");
77  printf ("\n");
78  printf ("#define FIB_TABLE_LIMIT         %d\n", fib_limit);
79  printf ("#define FIB_TABLE_LUCNUM_LIMIT  %d\n", luc_limit);
80}
81
82void
83table (int numb_bits)
84{
85  int  i;
86
87  printf ("/* This file generated by gen-fib.c - DO NOT EDIT. */\n");
88  printf ("\n");
89  printf ("#include \"gmp.h\"\n");
90  printf ("#include \"gmp-impl.h\"\n");
91  printf ("\n");
92  printf ("#if GMP_NUMB_BITS != %d\n", numb_bits);
93  printf ("Error, error, this data is for %d bits\n", numb_bits);
94  printf ("#endif\n");
95  printf ("\n");
96  printf ("const mp_limb_t\n");
97  printf ("__gmp_fib_table[FIB_TABLE_LIMIT+2] = {\n");
98
99  for (i = 0; i < fnum; i++)
100    {
101      printf ("  CNST_LIMB (0x");
102      mpz_out_str (stdout, 16, f[i]);
103      printf ("),  /* %d */\n", i-1);
104    }
105  printf ("};\n");
106}
107
108int
109main (int argc, char *argv[])
110{
111  int  limb_bits, nail_bits, numb_bits;
112
113  if (argc != 4)
114    {
115      fprintf (stderr, "Usage: gen-bases <header|table> <limbbits> <nailbits>\n");
116      exit (1);
117    }
118
119  limb_bits = atoi (argv[2]);
120  nail_bits = atoi (argv[3]);
121
122  if (limb_bits <= 0
123      || nail_bits < 0
124      || nail_bits >= limb_bits)
125    {
126      fprintf (stderr, "Invalid limb/nail bits: %d %d\n",
127               limb_bits, nail_bits);
128      exit (1);
129    }
130  numb_bits = limb_bits - nail_bits;
131
132  generate (numb_bits);
133
134  if (strcmp (argv[1], "header") == 0)
135    header (numb_bits);
136  else if (strcmp (argv[1], "table") == 0)
137    table (numb_bits);
138  else
139    {
140      fprintf (stderr, "Invalid header/table choice: %s\n", argv[1]);
141      exit (1);
142    }
143
144  return 0;
145}
146