← Back to branch summary

~ubuntu-branches/ubuntu/wily/libzn-poly/wily

« back to all changes in this revision

Viewing changes to midmul.c

  • 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

Show diffs side-by-side

added added

removed removed

Lines of Context:
midmul.c
 
1
/*
 
2
   midmul.c:  middle products
 
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
#include "zn_poly_internal.h"
 
24
 
 
25
 
 
26
ulong zn_array_midmul_fallback_get_fudge(size_t len1, size_t len2,
 
27
                                         const zn_mod_t mod)
 
28
{
 
29
   return _zn_array_mul_get_fudge(len1, len2, 0, mod);
 
30
}
 
31
 
 
32
 
 
33
void zn_array_midmul_fallback(ulong* res, const ulong* op1, size_t len1,
 
34
                              const ulong* op2, size_t len2, int fastred,
 
35
                              const zn_mod_t mod)
 
36
{
 
37
   ZNP_ASSERT(len2 >= 1);
 
38
   ZNP_ASSERT(len1 >= len2);
 
39
 
 
40
   ZNP_FASTALLOC(temp, ulong, 6624, len1 + len2 - 1);
 
41
 
 
42
   // just do full product and extract relevant segment
 
43
   _zn_array_mul(temp, op1, len1, op2, len2, fastred, mod);
 
44
   zn_array_copy(res, temp + len2 - 1, len1 - len2 + 1);
 
45
 
 
46
   ZNP_FASTFREE(temp);
 
47
}
 
48
 
 
49
 
 
50
void _zn_array_midmul(ulong* res, const ulong* op1, size_t len1,
 
51
                      const ulong* op2, size_t len2, int fastred,
 
52
                      const zn_mod_t mod)
 
53
{
 
54
   ZNP_ASSERT(len2 >= 1);
 
55
   ZNP_ASSERT(len1 >= len2);
 
56
 
 
57
   tuning_info_t* i = &tuning_info[mod->bits];
 
58
 
 
59
   if (len2 < i->midmul_fft_crossover  ||  !(mod->n & 1))
 
60
      // (can't use FFT algorithm if the modulus is even)
 
61
      zn_array_midmul_fallback(res, op1, len1, op2, len2, fastred, mod);
 
62
   else
 
63
   {
 
64
      ulong scale = zn_array_midmul_fft_get_fudge(len1, len2, mod);
 
65
      zn_array_midmul_fft(res, op1, len1, op2, len2, scale, mod);
 
66
   }
 
67
}
 
68
 
 
69
 
 
70
void zn_array_midmul(ulong* res, const ulong* op1, size_t len1,
 
71
                     const ulong* op2, size_t len2, const zn_mod_t mod)
 
72
{
 
73
   _zn_array_midmul(res, op1, len1, op2, len2, 0, mod);
 
74
}
 
75
 
 
76
 
 
77
 
 
78
void zn_array_midmul_precomp1_init(zn_array_midmul_precomp1_t res,
 
79
                                   const ulong* op1, size_t len1,
 
80
                                   size_t len2, const zn_mod_t mod)
 
81
{
 
82
   res->len1 = len1;
 
83
   res->len2 = len2;
 
84
   res->mod = mod;
 
85
 
 
86
   int odd = (mod->n & 1);
 
87
 
 
88
   // figure out which algorithm to use
 
89
 
 
90
   if (!odd)
 
91
      // can't use FFT algorithm when modulus is even
 
92
      res->algo = ZNP_MIDMUL_ALGO_FALLBACK;
 
93
   else
 
94
   {
 
95
      tuning_info_t* i = &tuning_info[mod->bits];
 
96
   
 
97
      if (len2 < i->midmul_fft_crossover)
 
98
         res->algo = ZNP_MIDMUL_ALGO_FALLBACK;
 
99
      else
 
100
         res->algo = ZNP_MIDMUL_ALGO_FFT;
 
101
   }
 
102
 
 
103
   // now perform initialisation for chosen algorithm
 
104
 
 
105
   switch (res->algo)
 
106
   {
 
107
      case ZNP_MIDMUL_ALGO_FALLBACK:
 
108
      {
 
109
         // Make a copy of op1[0, len1).
 
110
 
 
111
         // If modulus is odd, multiply it by the appropriate fudge factor
 
112
         // so that we can use faster REDC reduction in the execute() routine.
 
113
         res->op1 = (ulong*) malloc(len1 * sizeof(ulong));
 
114
         if (odd)
 
115
         {
 
116
            ulong scale = zn_array_midmul_fallback_get_fudge(len1, len2, mod);
 
117
            zn_array_scalar_mul(res->op1, op1, len1, scale, mod);
 
118
         }
 
119
         else
 
120
            zn_array_copy(res->op1, op1, len1);
 
121
      }
 
122
      break;
 
123
 
 
124
      case ZNP_MIDMUL_ALGO_FFT:
 
125
      {
 
126
         res->precomp_fft = (struct zn_array_midmul_fft_precomp1_struct*)
 
127
                               malloc(sizeof(zn_array_midmul_fft_precomp1_t));
 
128
 
 
129
         // we do scaling in this init() routine, to avoid doing it during
 
130
         // each call to execute()
 
131
         ulong scale = zn_array_midmul_fft_precomp1_get_fudge(len1, len2, mod);
 
132
         zn_array_midmul_fft_precomp1_init(res->precomp_fft,
 
133
                                           op1, len1, len2, scale, mod);
 
134
      }
 
135
      break;
 
136
 
 
137
      default: ZNP_ASSERT(0);
 
138
   }
 
139
}
 
140
 
 
141
 
 
142
void zn_array_midmul_precomp1_clear(zn_array_midmul_precomp1_t op)
 
143
{
 
144
   // dispatch to appropriate cleanup code
 
145
   switch (op->algo)
 
146
   {
 
147
      case ZNP_MIDMUL_ALGO_FALLBACK:
 
148
         free(op->op1);
 
149
         break;
 
150
 
 
151
      case ZNP_MIDMUL_ALGO_FFT:
 
152
         zn_array_midmul_fft_precomp1_clear(op->precomp_fft);
 
153
         free(op->precomp_fft);
 
154
         break;
 
155
 
 
156
      default: ZNP_ASSERT(0);
 
157
   }
 
158
}
 
159
 
 
160
 
 
161
 
 
162
void zn_array_midmul_precomp1_execute(
 
163
            ulong* res, const ulong* op2,
 
164
            const zn_array_midmul_precomp1_t precomp)
 
165
{
 
166
   // dispatch to appropriate middle product code
 
167
   switch (precomp->algo)
 
168
   {
 
169
      case ZNP_MIDMUL_ALGO_FALLBACK:
 
170
         zn_array_midmul_fallback(res, precomp->op1, precomp->len1,
 
171
                                  op2, precomp->len2, precomp->mod->n & 1,
 
172
                                  precomp->mod);
 
173
         break;
 
174
 
 
175
      case ZNP_MIDMUL_ALGO_FFT:
 
176
         zn_array_midmul_fft_precomp1_execute(res, op2, 1,
 
177
                                              precomp->precomp_fft);
 
178
         break;
 
179
         
 
180
      default: ZNP_ASSERT(0);
 
181
   }
 
182
}
 
183
 
 
184
 
 
185
// end of file ****************************************************************