Warning, file /libraries/qca/src/botantools/botan/mp_misc.cpp was not indexed or was modified since last indexation (in which case cross-reference links may be missing, inaccurate or erroneous).
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 * MP Misc Functions 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/mp_asm.h> 0038 namespace QCA { // WRAPNS_LINE 0039 0040 namespace Botan { 0041 0042 extern "C" { 0043 0044 /************************************************* 0045 * Core Division Operation * 0046 *************************************************/ 0047 u32bit bigint_divcore(word q, word y1, word y2, word x1, word x2, word x3) 0048 { 0049 word y0 = 0; 0050 y2 = word_madd2(q, y2, y0, &y0); 0051 y1 = word_madd2(q, y1, y0, &y0); 0052 0053 if (y0 > x1) 0054 return 1; 0055 if (y0 < x1) 0056 return 0; 0057 if (y1 > x2) 0058 return 1; 0059 if (y1 < x2) 0060 return 0; 0061 if (y2 > x3) 0062 return 1; 0063 if (y2 < x3) 0064 return 0; 0065 return 0; 0066 } 0067 0068 /************************************************* 0069 * Compare two MP integers * 0070 *************************************************/ 0071 s32bit bigint_cmp(const word x[], u32bit x_size, const word y[], u32bit y_size) 0072 { 0073 if (x_size < y_size) { 0074 return (-bigint_cmp(y, y_size, x, x_size)); 0075 } 0076 0077 while (x_size > y_size) { 0078 if (x[x_size - 1]) 0079 return 1; 0080 x_size--; 0081 } 0082 for (u32bit j = x_size; j > 0; --j) { 0083 if (x[j - 1] > y[j - 1]) 0084 return 1; 0085 if (x[j - 1] < y[j - 1]) 0086 return -1; 0087 } 0088 return 0; 0089 } 0090 0091 /************************************************* 0092 * Do a 2-word/1-word Division * 0093 *************************************************/ 0094 word bigint_divop(word n1, word n0, word d) 0095 { 0096 word high = n1 % d, quotient = 0; 0097 0098 for (u32bit j = 0; j != MP_WORD_BITS; ++j) { 0099 word high_top_bit = (high & MP_WORD_TOP_BIT); 0100 0101 high <<= 1; 0102 high |= (n0 >> (MP_WORD_BITS - 1 - j)) & 1; 0103 quotient <<= 1; 0104 0105 if (high_top_bit || high >= d) { 0106 high -= d; 0107 quotient |= 1; 0108 } 0109 } 0110 0111 return quotient; 0112 } 0113 0114 /************************************************* 0115 * Do a 2-word/1-word Modulo * 0116 *************************************************/ 0117 word bigint_modop(word n1, word n0, word d) 0118 { 0119 word z = bigint_divop(n1, n0, d); 0120 word dummy = 0; 0121 z = word_madd2(z, d, dummy, &dummy); 0122 return (n0 - z); 0123 } 0124 0125 /************************************************* 0126 * Do a word*word->2-word Multiply * 0127 *************************************************/ 0128 void bigint_wordmul(word a, word b, word *out_low, word *out_high) 0129 { 0130 const u32bit MP_HWORD_BITS = MP_WORD_BITS / 2; 0131 const word MP_HWORD_MASK = ((word)1 << MP_HWORD_BITS) - 1; 0132 0133 const word a_hi = (a >> MP_HWORD_BITS); 0134 const word a_lo = (a & MP_HWORD_MASK); 0135 const word b_hi = (b >> MP_HWORD_BITS); 0136 const word b_lo = (b & MP_HWORD_MASK); 0137 0138 word x0 = a_hi * b_hi; 0139 word x1 = a_lo * b_hi; 0140 word x2 = a_hi * b_lo; 0141 word x3 = a_lo * b_lo; 0142 0143 x2 += x3 >> (MP_HWORD_BITS); 0144 x2 += x1; 0145 if (x2 < x1) 0146 x0 += ((word)1 << MP_HWORD_BITS); 0147 0148 *out_high = x0 + (x2 >> MP_HWORD_BITS); 0149 *out_low = ((x2 & MP_HWORD_MASK) << MP_HWORD_BITS) + (x3 & MP_HWORD_MASK); 0150 } 0151 } 0152 0153 } 0154 } // WRAPNS_LINE