ยปCore Development>Code coverage>Modules/_decimal/libmpdec/numbertheory.c

Python code coverage for Modules/_decimal/libmpdec/numbertheory.c

#countcontent
1n/a/*
2n/a * Copyright (c) 2008-2016 Stefan Krah. All rights reserved.
3n/a *
4n/a * Redistribution and use in source and binary forms, with or without
5n/a * modification, are permitted provided that the following conditions
6n/a * are met:
7n/a *
8n/a * 1. Redistributions of source code must retain the above copyright
9n/a * notice, this list of conditions and the following disclaimer.
10n/a *
11n/a * 2. Redistributions in binary form must reproduce the above copyright
12n/a * notice, this list of conditions and the following disclaimer in the
13n/a * documentation and/or other materials provided with the distribution.
14n/a *
15n/a * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS "AS IS" AND
16n/a * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17n/a * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18n/a * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
19n/a * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20n/a * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
21n/a * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
22n/a * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
23n/a * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
24n/a * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
25n/a * SUCH DAMAGE.
26n/a */
27n/a
28n/a
29n/a#include "mpdecimal.h"
30n/a#include <stdlib.h>
31n/a#include <assert.h>
32n/a#include "bits.h"
33n/a#include "umodarith.h"
34n/a#include "numbertheory.h"
35n/a
36n/a
37n/a/* Bignum: Initialize the Number Theoretic Transform. */
38n/a
39n/a
40n/a/*
41n/a * Return the nth root of unity in F(p). This corresponds to e**((2*pi*i)/n)
42n/a * in the Fourier transform. We have w**n == 1 (mod p).
43n/a * n := transform length.
44n/a * sign := -1 for forward transform, 1 for backward transform.
45n/a * modnum := one of {P1, P2, P3}.
46n/a */
47n/ampd_uint_t
48n/a_mpd_getkernel(mpd_uint_t n, int sign, int modnum)
49n/a{
50n/a mpd_uint_t umod, p, r, xi;
51n/a#ifdef PPRO
52n/a double dmod;
53n/a uint32_t dinvmod[3];
54n/a#endif
55n/a
56n/a SETMODULUS(modnum);
57n/a r = mpd_roots[modnum]; /* primitive root of F(p) */
58n/a p = umod;
59n/a xi = (p-1) / n;
60n/a
61n/a if (sign == -1)
62n/a return POWMOD(r, (p-1-xi));
63n/a else
64n/a return POWMOD(r, xi);
65n/a}
66n/a
67n/a/*
68n/a * Initialize and return transform parameters.
69n/a * n := transform length.
70n/a * sign := -1 for forward transform, 1 for backward transform.
71n/a * modnum := one of {P1, P2, P3}.
72n/a */
73n/astruct fnt_params *
74n/a_mpd_init_fnt_params(mpd_size_t n, int sign, int modnum)
75n/a{
76n/a struct fnt_params *tparams;
77n/a mpd_uint_t umod;
78n/a#ifdef PPRO
79n/a double dmod;
80n/a uint32_t dinvmod[3];
81n/a#endif
82n/a mpd_uint_t kernel, w;
83n/a mpd_uint_t i;
84n/a mpd_size_t nhalf;
85n/a
86n/a assert(ispower2(n));
87n/a assert(sign == -1 || sign == 1);
88n/a assert(P1 <= modnum && modnum <= P3);
89n/a
90n/a nhalf = n/2;
91n/a tparams = mpd_sh_alloc(sizeof *tparams, nhalf, sizeof (mpd_uint_t));
92n/a if (tparams == NULL) {
93n/a return NULL;
94n/a }
95n/a
96n/a SETMODULUS(modnum);
97n/a kernel = _mpd_getkernel(n, sign, modnum);
98n/a
99n/a tparams->modnum = modnum;
100n/a tparams->modulus = umod;
101n/a tparams->kernel = kernel;
102n/a
103n/a /* wtable[] := w**0, w**1, ..., w**(nhalf-1) */
104n/a w = 1;
105n/a for (i = 0; i < nhalf; i++) {
106n/a tparams->wtable[i] = w;
107n/a w = MULMOD(w, kernel);
108n/a }
109n/a
110n/a return tparams;
111n/a}
112n/a
113n/a/* Initialize wtable of size three. */
114n/avoid
115n/a_mpd_init_w3table(mpd_uint_t w3table[3], int sign, int modnum)
116n/a{
117n/a mpd_uint_t umod;
118n/a#ifdef PPRO
119n/a double dmod;
120n/a uint32_t dinvmod[3];
121n/a#endif
122n/a mpd_uint_t kernel;
123n/a
124n/a SETMODULUS(modnum);
125n/a kernel = _mpd_getkernel(3, sign, modnum);
126n/a
127n/a w3table[0] = 1;
128n/a w3table[1] = kernel;
129n/a w3table[2] = POWMOD(kernel, 2);
130n/a}
131n/a
132n/a