File indexing completed on 2024-05-12 04:45:15
0001 /* 0002 Copyright (C) 1999-2007 The Botan Project. All rights reserved. 0003 0004 Redistribution and use in source and binary forms, for any use, with or without 0005 modification, is permitted provided that the following conditions are met: 0006 0007 1. Redistributions of source code must retain the above copyright notice, this 0008 list of conditions, and the following disclaimer. 0009 0010 2. Redistributions in binary form must reproduce the above copyright notice, 0011 this list of conditions, and the following disclaimer in the documentation 0012 and/or other materials provided with the distribution. 0013 0014 THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) "AS IS" AND ANY EXPRESS OR IMPLIED 0015 WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 0016 MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ARE DISCLAIMED. 0017 0018 IN NO EVENT SHALL THE AUTHOR(S) OR CONTRIBUTOR(S) BE LIABLE FOR ANY DIRECT, 0019 INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 0020 BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 0021 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 0022 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE 0023 OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF 0024 ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 0025 */ 0026 // LICENSEHEADER_END 0027 namespace QCA { // WRAPNS_LINE 0028 /************************************************* 0029 * Karatsuba Multiplication Source File * 0030 * (C) 1999-2007 The Botan Project * 0031 *************************************************/ 0032 0033 } // WRAPNS_LINE 0034 #include <botan/mp_core.h> 0035 namespace QCA { // WRAPNS_LINE 0036 } // WRAPNS_LINE 0037 #include <botan/mem_ops.h> 0038 namespace QCA { // WRAPNS_LINE 0039 0040 namespace Botan { 0041 0042 namespace { 0043 0044 /************************************************* 0045 * Simple O(N^2) Multiplication * 0046 *************************************************/ 0047 void bigint_simple_mul(word z[], const word x[], u32bit x_size, const word y[], u32bit y_size) 0048 { 0049 clear_mem(z, x_size + y_size); 0050 0051 for (u32bit j = 0; j != x_size; ++j) 0052 z[j + y_size] = bigint_mul_add_words(z + j, y, y_size, x[j]); 0053 } 0054 0055 /************************************************* 0056 * Karatsuba Multiplication Operation * 0057 *************************************************/ 0058 void karatsuba_mul(word z[], const word x[], const word y[], u32bit N, word workspace[]) 0059 { 0060 const u32bit KARATSUBA_MUL_LOWER_SIZE = BOTAN_KARAT_MUL_THRESHOLD; 0061 0062 if (N == 6) 0063 bigint_comba_mul6(z, x, y); 0064 else if (N == 8) 0065 bigint_comba_mul8(z, x, y); 0066 else if (N < KARATSUBA_MUL_LOWER_SIZE || N % 2) 0067 bigint_simple_mul(z, x, N, y, N); 0068 else { 0069 const u32bit N2 = N / 2; 0070 0071 const word *x0 = x; 0072 const word *x1 = x + N2; 0073 const word *y0 = y; 0074 const word *y1 = y + N2; 0075 word *z0 = z; 0076 word *z1 = z + N; 0077 0078 const s32bit cmp0 = bigint_cmp(x0, N2, x1, N2); 0079 const s32bit cmp1 = bigint_cmp(y1, N2, y0, N2); 0080 0081 clear_mem(workspace, 2 * N); 0082 0083 if (cmp0 && cmp1) { 0084 if (cmp0 > 0) 0085 bigint_sub3(z0, x0, N2, x1, N2); 0086 else 0087 bigint_sub3(z0, x1, N2, x0, N2); 0088 0089 if (cmp1 > 0) 0090 bigint_sub3(z1, y1, N2, y0, N2); 0091 else 0092 bigint_sub3(z1, y0, N2, y1, N2); 0093 0094 karatsuba_mul(workspace, z0, z1, N2, workspace + N); 0095 } 0096 0097 karatsuba_mul(z0, x0, y0, N2, workspace + N); 0098 karatsuba_mul(z1, x1, y1, N2, workspace + N); 0099 0100 word carry = bigint_add3_nc(workspace + N, z0, N, z1, N); 0101 carry += bigint_add2_nc(z + N2, N, workspace + N, N); 0102 bigint_add2_nc(z + N + N2, N2, &carry, 1); 0103 0104 if ((cmp0 == cmp1) || (cmp0 == 0) || (cmp1 == 0)) 0105 bigint_add2(z + N2, 2 * N - N2, workspace, N); 0106 else 0107 bigint_sub2(z + N2, 2 * N - N2, workspace, N); 0108 } 0109 } 0110 0111 /************************************************* 0112 * Pick a good size for the Karatsuba multiply * 0113 *************************************************/ 0114 u32bit karatsuba_size(u32bit z_size, u32bit x_size, u32bit x_sw, u32bit y_size, u32bit y_sw) 0115 { 0116 if (x_sw > x_size || x_sw > y_size || y_sw > x_size || y_sw > y_size) 0117 return 0; 0118 0119 if (((x_size == x_sw) && (x_size % 2)) || ((y_size == y_sw) && (y_size % 2))) 0120 return 0; 0121 0122 u32bit start = (x_sw > y_sw) ? x_sw : y_sw; 0123 u32bit end = (x_size < y_size) ? x_size : y_size; 0124 0125 if (start == end) { 0126 if (start % 2) 0127 return 0; 0128 return start; 0129 } 0130 0131 for (u32bit j = start; j <= end; ++j) { 0132 if (j % 2) 0133 continue; 0134 0135 if (2 * j > z_size) 0136 return 0; 0137 0138 if (x_sw <= j && j <= x_size && y_sw <= j && j <= y_size) { 0139 if (j % 4 == 2 && (j + 2) <= x_size && (j + 2) <= y_size && 2 * (j + 2) <= z_size) 0140 return j + 2; 0141 return j; 0142 } 0143 } 0144 0145 return 0; 0146 } 0147 0148 /************************************************* 0149 * Handle small operand multiplies * 0150 *************************************************/ 0151 void handle_small_mul(word z[], 0152 u32bit z_size, 0153 const word x[], 0154 u32bit x_size, 0155 u32bit x_sw, 0156 const word y[], 0157 u32bit y_size, 0158 u32bit y_sw) 0159 { 0160 if (x_sw == 1) 0161 bigint_linmul3(z, y, y_sw, x[0]); 0162 else if (y_sw == 1) 0163 bigint_linmul3(z, x, x_sw, y[0]); 0164 0165 else if (x_sw <= 4 && x_size >= 4 && y_sw <= 4 && y_size >= 4 && z_size >= 8) 0166 bigint_comba_mul4(z, x, y); 0167 0168 else if (x_sw <= 6 && x_size >= 6 && y_sw <= 6 && y_size >= 6 && z_size >= 12) 0169 bigint_comba_mul6(z, x, y); 0170 0171 else if (x_sw <= 8 && x_size >= 8 && y_sw <= 8 && y_size >= 8 && z_size >= 16) 0172 bigint_comba_mul8(z, x, y); 0173 0174 else 0175 bigint_simple_mul(z, x, x_sw, y, y_sw); 0176 } 0177 0178 } 0179 0180 /************************************************* 0181 * Multiplication Algorithm Dispatcher * 0182 *************************************************/ 0183 void bigint_mul(word z[], 0184 u32bit z_size, 0185 word workspace[], 0186 const word x[], 0187 u32bit x_size, 0188 u32bit x_sw, 0189 const word y[], 0190 u32bit y_size, 0191 u32bit y_sw) 0192 { 0193 if (x_size <= 8 || y_size <= 8) { 0194 handle_small_mul(z, z_size, x, x_size, x_sw, y, y_size, y_sw); 0195 return; 0196 } 0197 0198 const u32bit N = karatsuba_size(z_size, x_size, x_sw, y_size, y_sw); 0199 0200 if (N) { 0201 clear_mem(workspace, 2 * N); 0202 karatsuba_mul(z, x, y, N, workspace); 0203 } else 0204 bigint_simple_mul(z, x, x_sw, y, y_sw); 0205 } 0206 0207 } 0208 } // WRAPNS_LINE