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

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