← Back to branch summary

~ubuntu-branches/ubuntu/wily/qca2/wily-proposed

« back to all changes in this revision

Viewing changes to qca/src/botantools/botan/mp_mul.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Jan Niehusmann
  • Date: 2007-10-27 18:51:54 UTC
  • mfrom: (1.1.2 upstream)
  • Revision ID: james.westby@ubuntu.com-20071027185154-4ir9ys3h2q9fofrw
Tags: 2.0.0-2
Upload to unstable

Show diffs side-by-side

added added

removed removed

Lines of Context:
qca/src/botantools/botan/mp_mul.cpp
1
 
/*
2
 
Copyright (C) 1999-2007 The Botan Project. All rights reserved.
3
 
 
4
 
Redistribution and use in source and binary forms, for any use, with or without
5
 
modification, is permitted provided that the following conditions are met:
6
 
 
7
 
1. Redistributions of source code must retain the above copyright notice, this
8
 
list of conditions, and the following disclaimer.
9
 
 
10
 
2. Redistributions in binary form must reproduce the above copyright notice,
11
 
this list of conditions, and the following disclaimer in the documentation
12
 
and/or other materials provided with the distribution.
13
 
 
14
 
THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) "AS IS" AND ANY EXPRESS OR IMPLIED
15
 
WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
16
 
MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ARE DISCLAIMED.
17
 
 
18
 
IN NO EVENT SHALL THE AUTHOR(S) OR CONTRIBUTOR(S) BE LIABLE FOR ANY DIRECT,
19
 
INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
20
 
BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21
 
DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
22
 
LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
23
 
OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
24
 
ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25
 
*/
26
 
// LICENSEHEADER_END
27
 
namespace QCA { // WRAPNS_LINE
28
 
/*************************************************
29
 
* Karatsuba Multiplication Source File           *
30
 
* (C) 1999-2007 The Botan Project                *
31
 
*************************************************/
32
 
 
33
 
} // WRAPNS_LINE
34
 
#include <botan/mp_core.h>
35
 
namespace QCA { // WRAPNS_LINE
36
 
} // WRAPNS_LINE
37
 
#include <botan/mem_ops.h>
38
 
namespace QCA { // WRAPNS_LINE
39
 
 
40
 
namespace Botan {
41
 
 
42
 
namespace {
43
 
 
44
 
/*************************************************
45
 
* Simple O(N^2) Multiplication                   *
46
 
*************************************************/
47
 
void bigint_simple_mul(word z[], const word x[], u32bit x_size,
48
 
                                 const word y[], u32bit y_size)
49
 
   {
50
 
   clear_mem(z, x_size + y_size);
51
 
 
52
 
   for(u32bit j = 0; j != x_size; ++j)
53
 
      z[j+y_size] = bigint_mul_add_words(z + j, y, y_size, x[j]);
54
 
   }
55
 
 
56
 
/*************************************************
57
 
* Karatsuba Multiplication Operation             *
58
 
*************************************************/
59
 
void karatsuba_mul(word z[], const word x[], const word y[], u32bit N,
60
 
                   word workspace[])
61
 
   {
62
 
   const u32bit KARATSUBA_MUL_LOWER_SIZE = BOTAN_KARAT_MUL_THRESHOLD;
63
 
 
64
 
   if(N == 6)
65
 
      bigint_comba_mul6(z, x, y);
66
 
   else if(N == 8)
67
 
      bigint_comba_mul8(z, x, y);
68
 
   else if(N < KARATSUBA_MUL_LOWER_SIZE || N % 2)
69
 
      bigint_simple_mul(z, x, N, y, N);
70
 
   else
71
 
      {
72
 
      const u32bit N2 = N / 2;
73
 
 
74
 
      const word* x0 = x;
75
 
      const word* x1 = x + N2;
76
 
      const word* y0 = y;
77
 
      const word* y1 = y + N2;
78
 
      word* z0 = z;
79
 
      word* z1 = z + N;
80
 
 
81
 
      const s32bit cmp0 = bigint_cmp(x0, N2, x1, N2);
82
 
      const s32bit cmp1 = bigint_cmp(y1, N2, y0, N2);
83
 
 
84
 
      clear_mem(workspace, 2*N);
85
 
 
86
 
      if(cmp0 && cmp1)
87
 
         {
88
 
         if(cmp0 > 0)
89
 
            bigint_sub3(z0, x0, N2, x1, N2);
90
 
         else
91
 
            bigint_sub3(z0, x1, N2, x0, N2);
92
 
 
93
 
         if(cmp1 > 0)
94
 
            bigint_sub3(z1, y1, N2, y0, N2);
95
 
         else
96
 
            bigint_sub3(z1, y0, N2, y1, N2);
97
 
 
98
 
         karatsuba_mul(workspace, z0, z1, N2, workspace+N);
99
 
         }
100
 
 
101
 
      karatsuba_mul(z0, x0, y0, N2, workspace+N);
102
 
      karatsuba_mul(z1, x1, y1, N2, workspace+N);
103
 
 
104
 
      word carry = bigint_add3_nc(workspace+N, z0, N, z1, N);
105
 
      carry += bigint_add2_nc(z + N2, N, workspace + N, N);
106
 
      bigint_add2_nc(z + N + N2, N2, &carry, 1);
107
 
 
108
 
      if((cmp0 == cmp1) || (cmp0 == 0) || (cmp1 == 0))
109
 
         bigint_add2(z + N2, 2*N-N2, workspace, N);
110
 
      else
111
 
         bigint_sub2(z + N2, 2*N-N2, workspace, N);
112
 
      }
113
 
   }
114
 
 
115
 
/*************************************************
116
 
* Pick a good size for the Karatsuba multiply    *
117
 
*************************************************/
118
 
u32bit karatsuba_size(u32bit z_size,
119
 
                      u32bit x_size, u32bit x_sw,
120
 
                      u32bit y_size, u32bit y_sw)
121
 
   {
122
 
   if(x_sw > x_size || x_sw > y_size || y_sw > x_size || y_sw > y_size)
123
 
      return 0;
124
 
 
125
 
   if(((x_size == x_sw) && (x_size % 2)) ||
126
 
      ((y_size == y_sw) && (y_size % 2)))
127
 
      return 0;
128
 
 
129
 
   u32bit start = (x_sw > y_sw) ? x_sw : y_sw;
130
 
   u32bit end = (x_size < y_size) ? x_size : y_size;
131
 
 
132
 
   if(start == end)
133
 
      {
134
 
      if(start % 2)
135
 
         return 0;
136
 
      return start;
137
 
      }
138
 
 
139
 
   for(u32bit j = start; j <= end; ++j)
140
 
      {
141
 
      if(j % 2)
142
 
         continue;
143
 
 
144
 
      if(2*j > z_size)
145
 
         return 0;
146
 
 
147
 
      if(x_sw <= j && j <= x_size && y_sw <= j && j <= y_size)
148
 
         {
149
 
         if(j % 4 == 2 &&
150
 
            (j+2) <= x_size && (j+2) <= y_size && 2*(j+2) <= z_size)
151
 
            return j+2;
152
 
         return j;
153
 
         }
154
 
      }
155
 
 
156
 
   return 0;
157
 
   }
158
 
 
159
 
/*************************************************
160
 
* Handle small operand multiplies                *
161
 
*************************************************/
162
 
void handle_small_mul(word z[], u32bit z_size,
163
 
                      const word x[], u32bit x_size, u32bit x_sw,
164
 
                      const word y[], u32bit y_size, u32bit y_sw)
165
 
   {
166
 
   if(x_sw == 1)        bigint_linmul3(z, y, y_sw, x[0]);
167
 
   else if(y_sw == 1)   bigint_linmul3(z, x, x_sw, y[0]);
168
 
 
169
 
   else if(x_sw <= 4 && x_size >= 4 &&
170
 
           y_sw <= 4 && y_size >= 4 && z_size >= 8)
171
 
      bigint_comba_mul4(z, x, y);
172
 
 
173
 
   else if(x_sw <= 6 && x_size >= 6 &&
174
 
           y_sw <= 6 && y_size >= 6 && z_size >= 12)
175
 
      bigint_comba_mul6(z, x, y);
176
 
 
177
 
   else if(x_sw <= 8 && x_size >= 8 &&
178
 
           y_sw <= 8 && y_size >= 8 && z_size >= 16)
179
 
      bigint_comba_mul8(z, x, y);
180
 
 
181
 
   else
182
 
      bigint_simple_mul(z, x, x_sw, y, y_sw);
183
 
   }
184
 
 
185
 
}
186
 
 
187
 
/*************************************************
188
 
* Multiplication Algorithm Dispatcher            *
189
 
*************************************************/
190
 
void bigint_mul(word z[], u32bit z_size, word workspace[],
191
 
                const word x[], u32bit x_size, u32bit x_sw,
192
 
                const word y[], u32bit y_size, u32bit y_sw)
193
 
   {
194
 
   if(x_size <= 8 || y_size <= 8)
195
 
      {
196
 
      handle_small_mul(z, z_size, x, x_size, x_sw, y, y_size, y_sw);
197
 
      return;
198
 
      }
199
 
 
200
 
   const u32bit N = karatsuba_size(z_size, x_size, x_sw, y_size, y_sw);
201
 
 
202
 
   if(N)
203
 
      {
204
 
      clear_mem(workspace, 2*N);
205
 
      karatsuba_mul(z, x, y, N, workspace);
206
 
      }
207
 
   else
208
 
      bigint_simple_mul(z, x, x_sw, y, y_sw);
209
 
   }
210
 
 
211
 
}
212
 
} // WRAPNS_LINE