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

source code of qca/src/botantools/botan/mp_mul.cpp