Python code coverage for Modules/_decimal/libmpdec/convolute.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 <stdio.h>
31	n/a	#include "bits.h"
32	n/a	#include "constants.h"
33	n/a	#include "fnt.h"
34	n/a	#include "fourstep.h"
35	n/a	#include "numbertheory.h"
36	n/a	#include "sixstep.h"
37	n/a	#include "umodarith.h"
38	n/a	#include "convolute.h"
39	n/a
40	n/a
41	n/a	/* Bignum: Fast convolution using the Number Theoretic Transform. Used for
42	n/a	the multiplication of very large coefficients. */
43	n/a
44	n/a
45	n/a	/* Convolute the data in c1 and c2. Result is in c1. */
46	n/a	int
47	n/a	fnt_convolute(mpd_uint_t c1, mpd_uint_t c2, mpd_size_t n, int modnum)
48	n/a	{
49	n/a	int (fnt)(mpd_uint_t , mpd_size_t, int);
50	n/a	int (inv_fnt)(mpd_uint_t , mpd_size_t, int);
51	n/a	#ifdef PPRO
52	n/a	double dmod;
53	n/a	uint32_t dinvmod[3];
54	n/a	#endif
55	n/a	mpd_uint_t n_inv, umod;
56	n/a	mpd_size_t i;
57	n/a
58	n/a
59	n/a	SETMODULUS(modnum);
60	n/a	n_inv = POWMOD(n, (umod-2));
61	n/a
62	n/a	if (ispower2(n)) {
63	n/a	if (n > SIX_STEP_THRESHOLD) {
64	n/a	fnt = six_step_fnt;
65	n/a	inv_fnt = inv_six_step_fnt;
66	n/a	}
67	n/a	else {
68	n/a	fnt = std_fnt;
69	n/a	inv_fnt = std_inv_fnt;
70	n/a	}
71	n/a	}
72	n/a	else {
73	n/a	fnt = four_step_fnt;
74	n/a	inv_fnt = inv_four_step_fnt;
75	n/a	}
76	n/a
77	n/a	if (!fnt(c1, n, modnum)) {
78	n/a	return 0;
79	n/a	}
80	n/a	if (!fnt(c2, n, modnum)) {
81	n/a	return 0;
82	n/a	}
83	n/a	for (i = 0; i < n-1; i += 2) {
84	n/a	mpd_uint_t x0 = c1[i];
85	n/a	mpd_uint_t y0 = c2[i];
86	n/a	mpd_uint_t x1 = c1[i+1];
87	n/a	mpd_uint_t y1 = c2[i+1];
88	n/a	MULMOD2(&x0, y0, &x1, y1);
89	n/a	c1[i] = x0;
90	n/a	c1[i+1] = x1;
91	n/a	}
92	n/a
93	n/a	if (!inv_fnt(c1, n, modnum)) {
94	n/a	return 0;
95	n/a	}
96	n/a	for (i = 0; i < n-3; i += 4) {
97	n/a	mpd_uint_t x0 = c1[i];
98	n/a	mpd_uint_t x1 = c1[i+1];
99	n/a	mpd_uint_t x2 = c1[i+2];
100	n/a	mpd_uint_t x3 = c1[i+3];
101	n/a	MULMOD2C(&x0, &x1, n_inv);
102	n/a	MULMOD2C(&x2, &x3, n_inv);
103	n/a	c1[i] = x0;
104	n/a	c1[i+1] = x1;
105	n/a	c1[i+2] = x2;
106	n/a	c1[i+3] = x3;
107	n/a	}
108	n/a
109	n/a	return 1;
110	n/a	}
111	n/a
112	n/a	/* Autoconvolute the data in c1. Result is in c1. */
113	n/a	int
114	n/a	fnt_autoconvolute(mpd_uint_t *c1, mpd_size_t n, int modnum)
115	n/a	{
116	n/a	int (fnt)(mpd_uint_t , mpd_size_t, int);
117	n/a	int (inv_fnt)(mpd_uint_t , mpd_size_t, int);
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 n_inv, umod;
123	n/a	mpd_size_t i;
124	n/a
125	n/a
126	n/a	SETMODULUS(modnum);
127	n/a	n_inv = POWMOD(n, (umod-2));
128	n/a
129	n/a	if (ispower2(n)) {
130	n/a	if (n > SIX_STEP_THRESHOLD) {
131	n/a	fnt = six_step_fnt;
132	n/a	inv_fnt = inv_six_step_fnt;
133	n/a	}
134	n/a	else {
135	n/a	fnt = std_fnt;
136	n/a	inv_fnt = std_inv_fnt;
137	n/a	}
138	n/a	}
139	n/a	else {
140	n/a	fnt = four_step_fnt;
141	n/a	inv_fnt = inv_four_step_fnt;
142	n/a	}
143	n/a
144	n/a	if (!fnt(c1, n, modnum)) {
145	n/a	return 0;
146	n/a	}
147	n/a	for (i = 0; i < n-1; i += 2) {
148	n/a	mpd_uint_t x0 = c1[i];
149	n/a	mpd_uint_t x1 = c1[i+1];
150	n/a	MULMOD2(&x0, x0, &x1, x1);
151	n/a	c1[i] = x0;
152	n/a	c1[i+1] = x1;
153	n/a	}
154	n/a
155	n/a	if (!inv_fnt(c1, n, modnum)) {
156	n/a	return 0;
157	n/a	}
158	n/a	for (i = 0; i < n-3; i += 4) {
159	n/a	mpd_uint_t x0 = c1[i];
160	n/a	mpd_uint_t x1 = c1[i+1];
161	n/a	mpd_uint_t x2 = c1[i+2];
162	n/a	mpd_uint_t x3 = c1[i+3];
163	n/a	MULMOD2C(&x0, &x1, n_inv);
164	n/a	MULMOD2C(&x2, &x3, n_inv);
165	n/a	c1[i] = x0;
166	n/a	c1[i+1] = x1;
167	n/a	c1[i+2] = x2;
168	n/a	c1[i+3] = x3;
169	n/a	}
170	n/a
171	n/a	return 1;
172	n/a	}
173	n/a
174	n/a