1 | /* |
2 | * Copyright (c) 2008-2020 Stefan Krah. All rights reserved. |
3 | * |
4 | * Redistribution and use in source and binary forms, with or without |
5 | * modification, are permitted provided that the following conditions |
6 | * are met: |
7 | * |
8 | * 1. Redistributions of source code must retain the above copyright |
9 | * notice, this list of conditions and the following disclaimer. |
10 | * |
11 | * 2. Redistributions in binary form must reproduce the above copyright |
12 | * notice, this list of conditions and the following disclaimer in the |
13 | * documentation and/or other materials provided with the distribution. |
14 | * |
15 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS "AS IS" AND |
16 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
17 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
18 | * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE |
19 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
20 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
21 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
22 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
23 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
24 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
25 | * SUCH DAMAGE. |
26 | */ |
27 | |
28 | |
29 | #include "mpdecimal.h" |
30 | |
31 | #include <assert.h> |
32 | #include <stdio.h> |
33 | |
34 | #include "bits.h" |
35 | #include "difradix2.h" |
36 | #include "fnt.h" |
37 | #include "numbertheory.h" |
38 | |
39 | |
40 | /* Bignum: Fast transform for medium-sized coefficients. */ |
41 | |
42 | |
43 | /* forward transform, sign = -1 */ |
44 | int |
45 | std_fnt(mpd_uint_t *a, mpd_size_t n, int modnum) |
46 | { |
47 | struct fnt_params *tparams; |
48 | |
49 | assert(ispower2(n)); |
50 | assert(n >= 4); |
51 | assert(n <= 3*MPD_MAXTRANSFORM_2N); |
52 | |
53 | if ((tparams = _mpd_init_fnt_params(n, -1, modnum)) == NULL) { |
54 | return 0; |
55 | } |
56 | fnt_dif2(a, n, tparams); |
57 | |
58 | mpd_free(tparams); |
59 | return 1; |
60 | } |
61 | |
62 | /* reverse transform, sign = 1 */ |
63 | int |
64 | std_inv_fnt(mpd_uint_t *a, mpd_size_t n, int modnum) |
65 | { |
66 | struct fnt_params *tparams; |
67 | |
68 | assert(ispower2(n)); |
69 | assert(n >= 4); |
70 | assert(n <= 3*MPD_MAXTRANSFORM_2N); |
71 | |
72 | if ((tparams = _mpd_init_fnt_params(n, 1, modnum)) == NULL) { |
73 | return 0; |
74 | } |
75 | fnt_dif2(a, n, tparams); |
76 | |
77 | mpd_free(tparams); |
78 | return 1; |
79 | } |
80 | |