File indexing completed on 2024-05-12 04:45:14
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 * Division Algorithm Source File * 0030 * (C) 1999-2007 The Botan Project * 0031 *************************************************/ 0032 0033 } // WRAPNS_LINE 0034 #include <botan/numthry.h> 0035 namespace QCA { // WRAPNS_LINE 0036 } // WRAPNS_LINE 0037 #include <botan/mp_core.h> 0038 namespace QCA { // WRAPNS_LINE 0039 0040 namespace Botan { 0041 0042 namespace { 0043 0044 /************************************************* 0045 * Handle signed operands, if necessary * 0046 *************************************************/ 0047 void sign_fixup(const BigInt &x, const BigInt &y, BigInt &q, BigInt &r) 0048 { 0049 if (x.sign() == BigInt::Negative) { 0050 q.flip_sign(); 0051 if (r.is_nonzero()) { 0052 --q; 0053 r = y.abs() - r; 0054 } 0055 } 0056 if (y.sign() == BigInt::Negative) 0057 q.flip_sign(); 0058 } 0059 0060 } 0061 0062 /************************************************* 0063 * Solve x = q * y + r * 0064 *************************************************/ 0065 void divide(const BigInt &x, const BigInt &y_arg, BigInt &q, BigInt &r) 0066 { 0067 if (y_arg.is_zero()) 0068 throw BigInt::DivideByZero(); 0069 0070 BigInt y = y_arg; 0071 const u32bit y_words = y.sig_words(); 0072 r = x; 0073 0074 r.set_sign(BigInt::Positive); 0075 y.set_sign(BigInt::Positive); 0076 0077 s32bit compare = r.cmp(y); 0078 0079 if (compare < 0) 0080 q = 0; 0081 else if (compare == 0) { 0082 q = 1; 0083 r = 0; 0084 } else { 0085 u32bit shifts = 0; 0086 word y_top = y[y.sig_words() - 1]; 0087 while (y_top < MP_WORD_TOP_BIT) { 0088 y_top <<= 1; 0089 ++shifts; 0090 } 0091 y <<= shifts; 0092 r <<= shifts; 0093 0094 const u32bit n = r.sig_words() - 1, t = y_words - 1; 0095 0096 q.get_reg().create(n - t + 1); 0097 if (n <= t) { 0098 while (r > y) { 0099 r -= y; 0100 q++; 0101 } 0102 r >>= shifts; 0103 sign_fixup(x, y_arg, q, r); 0104 return; 0105 } 0106 0107 BigInt temp = y << (MP_WORD_BITS * (n - t)); 0108 0109 while (r >= temp) { 0110 r -= temp; 0111 ++q[n - t]; 0112 } 0113 0114 for (u32bit j = n; j != t; --j) { 0115 const word x_j0 = r.word_at(j); 0116 const word x_j1 = r.word_at(j - 1); 0117 const word y_t = y.word_at(t); 0118 0119 if (x_j0 == y_t) 0120 q[j - t - 1] = MP_WORD_MAX; 0121 else 0122 q[j - t - 1] = bigint_divop(x_j0, x_j1, y_t); 0123 0124 while (bigint_divcore(q[j - t - 1], y_t, y.word_at(t - 1), x_j0, x_j1, r.word_at(j - 2))) 0125 --q[j - t - 1]; 0126 0127 r -= (q[j - t - 1] * y) << (MP_WORD_BITS * (j - t - 1)); 0128 if (r.is_negative()) { 0129 r += y << (MP_WORD_BITS * (j - t - 1)); 0130 --q[j - t - 1]; 0131 } 0132 } 0133 r >>= shifts; 0134 } 0135 0136 sign_fixup(x, y_arg, q, r); 0137 } 0138 0139 } 0140 } // WRAPNS_LINE