« back to all changes in this revision
Viewing changes to support.h
- browse files at revision 1
- compare with another revision
- download diff
- download tarball
- view history from revision 1
- Committer: Bazaar Package Importer
- Author(s): Tim Abbott
- Date: 2008-05-27 20:23:43 UTC
- Revision ID: james.westby@ubuntu.com-20080527202343-ufcb3fwj2as0edoz
Tags: upstream-0.8
Import upstream version 0.8
- files added:
added
removed
support.h
1
/*
2
support.h: various support routines for test, profiling and tuning code
3
4
Copyright (C) 2007, 2008, David Harvey
5
6
This file is part of the zn_poly library (version 0.8).
7
8
This program is free software: you can redistribute it and/or modify
9
it under the terms of the GNU General Public License as published by
10
the Free Software Foundation, either version 2 of the License, or
11
(at your option) version 3 of the License.
12
13
This program is distributed in the hope that it will be useful,
14
but WITHOUT ANY WARRANTY; without even the implied warranty of
15
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16
GNU General Public License for more details.
17
18
You should have received a copy of the GNU General Public License
19
along with this program. If not, see <http://www.gnu.org/licenses/>.
20
21
*/
22
23
#ifndef ZNP_SUPPORT_H
24
#define ZNP_SUPPORT_H
25
26
27
#include <stdio.h>
28
#include <gmp.h>
29
#include "zn_poly_internal.h"
30
31
32
#ifdef __cplusplus
33
extern "C" {
34
#endif
35
36
37
38
/*
39
single global random state for test/profile modules
40
*/
41
extern gmp_randstate_t randstate;
42
43
44
45
/*
46
An array of modulus bitsizes, used by several test functions.
47
*/
48
extern unsigned test_bitsizes[];
49
extern unsigned num_test_bitsizes; // how big the array is
50
51
52
/*
53
Exports abs(op) to res, storing exactly len limbs
54
(zero-padded if necessary).
55
56
Sign of op is ignored.
57
58
abs(op) must fit into len limbs.
59
*/
60
void mpz_to_mpn(mp_limb_t* res, size_t len, const mpz_t op);
61
62
63
/*
64
Converts mpn buffer (exactly len limbs) to mpz.
65
66
Output is always non-negative.
67
*/
68
void mpn_to_mpz(mpz_t res, const mp_limb_t* op, size_t len);
69
70
71
/*
72
Returns random unsigned long in [0, max).
73
*/
74
ulong random_ulong(ulong max);
75
76
77
/*
78
Returns random unsigned long in [0, 2^bits).
79
*/
80
ulong random_ulong_bits(unsigned bits);
81
82
83
/*
84
Returns random modulus with exactly _bits_ bits, i.e. in the range
85
[2^(bits-1), 2^bits).
86
87
If require_odd is set, the returned modulus will be odd.
88
*/
89
ulong random_modulus(unsigned bits, int require_odd);
90
91
92
/*
93
Prints array to stdout, in format e.g. "[2 3 7]".
94
*/
95
void zn_array_print(const ulong* x, size_t len);
96
97
98
99
void ref_zn_array_mul(ulong* res, const ulong* op1, size_t len1,
100
const ulong* op2, size_t len2, const zn_mod_t mod);
101
102
void ref_zn_array_scalar_mul(ulong* res, const ulong* op, size_t len,
103
ulong x, const zn_mod_t mod);
104
105
void ref_zn_array_midmul(ulong* res, const ulong* op1, size_t len1,
106
const ulong* op2, size_t len2, const zn_mod_t mod);
107
108
void ref_zn_array_negamul(ulong* res, const ulong* op1, const ulong* op2,
109
size_t len, const zn_mod_t mod);
110
111
112
#if DEBUG
113
114
/*
115
Prints op to standard output (in normalised form).
116
*/
117
void zn_pmf_print(const zn_pmf_t op, ulong M, const zn_mod_t mod);
118
119
/*
120
Prints op to standard output.
121
*/
122
void zn_pmf_vec_print(const zn_pmf_vec_t op);
123
124
/*
125
Prints first _length_ coefficients of op to standard output.
126
*/
127
void zn_pmf_vec_print_trunc(const zn_pmf_vec_t op, ulong length);
128
129
130
#endif
131
132
133
134
/* ============================================================================
135
136
tuning routines
137
138
============================================================================ */
139
140
141
#define tune_mul_KS \
142
ZNP_tune_mul_KS
143
void tune_mul_KS(FILE* flog, int squaring, int verbose);
144
145
#define tune_mul_nussbaumer \
146
ZNP_tune_mul_nussbaumer
147
void tune_nussbaumer(FILE* flog, int squaring, int verbose);
148
149
#define tune_mul \
150
ZNP_tune_mul
151
void tune_mul(FILE* flog, int squaring, int verbose);
152
153
154
155
156
/* ============================================================================
157
158
structs used in profiling routines
159
160
============================================================================ */
161
162
163
enum
164
{
165
ALGO_MUL_BEST,
166
ALGO_MUL_KS1,
167
ALGO_MUL_KS1_REDC,
168
ALGO_MUL_KS2,
169
ALGO_MUL_KS2_REDC,
170
ALGO_MUL_KS3,
171
ALGO_MUL_KS3_REDC,
172
ALGO_MUL_KS4,
173
ALGO_MUL_KS4_REDC,
174
ALGO_MUL_FFT,
175
ALGO_MUL_NTL,
176
};
177
178
/*
179
struct for passing information to profile_mul
180
*/
181
typedef struct
182
{
183
size_t len; // length of polynomials to multiply
184
ulong n; // the modulus
185
int algo; // one of the ALGO_MUL_* values
186
int squaring; // whether to profile squaring or multiplication
187
}
188
profile_mul_info_struct;
189
190
typedef profile_mul_info_struct profile_mul_info_t[1];
191
192
/*
193
Profiles one of the multiplication routines.
194
195
_arg_ should point to a profile_mul_info_t describing what to profile.
196
197
Returns total cycle count for _count_ calls.
198
*/
199
double profile_mul(void* arg, unsigned long count);
200
201
/*
202
As above, but assumes that the algorithm is ALGO_MUL_NTL.
203
*/
204
double profile_mul_ntl(void* arg, unsigned long count);
205
206
207
208
enum
209
{
210
// fall back on calling zn_array_mul and reducing negacyclically
211
ALGO_NEGAMUL_FALLBACK,
212
213
// use Nussbaumer convolution
214
ALGO_NEGAMUL_NUSSBAUMER,
215
};
216
217
/*
218
struct for passing information to profile_negamul
219
*/
220
typedef struct
221
{
222
unsigned lg_len; // lg2 of polynomial length
223
ulong n; // the modulus
224
int algo; // one of the ALGO_NEGAMUL_* values
225
int squaring; // whether to profile squaring or multiplication
226
}
227
profile_negamul_info_struct;
228
229
typedef profile_negamul_info_struct profile_negamul_info_t[1];
230
231
/*
232
Profiles one of the negacyclic multiplication routines.
233
234
_arg_ should point to a profile_negamul_info_t describing what to profile.
235
236
Returns total cycle count for _count_ calls.
237
*/
238
double profile_negamul(void* arg, unsigned long count);
239
240
241
242
enum
243
{
244
ALGO_MIDMUL_BEST,
245
ALGO_MIDMUL_FALLBACK,
246
ALGO_MIDMUL_KS1,
247
ALGO_MIDMUL_KS2,
248
ALGO_MIDMUL_KS3,
249
ALGO_MIDMUL_KS4,
250
ALGO_MIDMUL_FFT,
251
};
252
253
/*
254
struct for passing information to profile_midmul
255
*/
256
typedef struct
257
{
258
size_t len; // we're doing a (2*len) x len middle product
259
ulong n; // the modulus
260
int algo; // one of the ALGO_MIDMUL_* values
261
}
262
profile_midmul_info_struct;
263
264
typedef profile_midmul_info_struct profile_midmul_info_t[1];
265
266
/*
267
Profiles one of the middle product routines.
268
269
_arg_ should point to a profile_midmul_info_t describing what to profile.
270
271
Returns total cycle count for _count_ calls.
272
*/
273
double profile_midmul(void* arg, unsigned long count);
274
275
276
277
enum
278
{
279
ALGO_INVERT_BEST,
280
ALGO_INVERT_NTL,
281
};
282
283
/*
284
struct for passing information to profile_invert
285
*/
286
typedef struct
287
{
288
size_t len; // we're doing a length len inversion
289
ulong n; // the modulus
290
int algo; // one of the ALGO_INVERT_* values
291
}
292
profile_invert_info_struct;
293
294
typedef profile_invert_info_struct profile_invert_info_t[1];
295
296
/*
297
Profiles one of the series inversion routines.
298
299
_arg_ should point to a profile_invert_info_t describing what to profile.
300
301
Returns total cycle count for _count_ calls.
302
*/
303
double profile_invert(void* arg, unsigned long count);
304
305
/*
306
As above, but assumes that the algorithm is ALGO_INVERT_NTL.
307
*/
308
double profile_invert_ntl(void* arg, unsigned long count);
309
310
311
312
313
double profile_bfly(void* arg, unsigned long count);
314
double profile_mpn_aors(void* arg, unsigned long count);
315
double profile_scalar_mul(void* arg, unsigned long count);
316
317
void prof_main(int argc, char* argv[]);
318
319
320
#ifdef __cplusplus
321
}
322
#endif
323
324
#endif
325
326
// end of file ****************************************************************
Loggerhead is a web-based interface for Breezy
Version: 2.0.1