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 * MP Misc Functions 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/mp_asm.h>
38namespace QCA { // WRAPNS_LINE
39
40namespace Botan {
41
42extern "C" {
43
44/*************************************************
45 * Core Division Operation *
46 *************************************************/
47u32bit bigint_divcore(word q, word y1, word y2, word x1, word x2, word x3)
48{
49 word y0 = 0;
50 y2 = word_madd2(a: q, b: y2, c: y0, carry: &y0);
51 y1 = word_madd2(a: q, b: y1, c: y0, carry: &y0);
52
53 if (y0 > x1)
54 return 1;
55 if (y0 < x1)
56 return 0;
57 if (y1 > x2)
58 return 1;
59 if (y1 < x2)
60 return 0;
61 if (y2 > x3)
62 return 1;
63 if (y2 < x3)
64 return 0;
65 return 0;
66}
67
68/*************************************************
69 * Compare two MP integers *
70 *************************************************/
71s32bit bigint_cmp(const word x[], u32bit x_size, const word y[], u32bit y_size)
72{
73 if (x_size < y_size) {
74 return (-bigint_cmp(x: y, x_size: y_size, y: x, y_size: x_size));
75 }
76
77 while (x_size > y_size) {
78 if (x[x_size - 1])
79 return 1;
80 x_size--;
81 }
82 for (u32bit j = x_size; j > 0; --j) {
83 if (x[j - 1] > y[j - 1])
84 return 1;
85 if (x[j - 1] < y[j - 1])
86 return -1;
87 }
88 return 0;
89}
90
91/*************************************************
92 * Do a 2-word/1-word Division *
93 *************************************************/
94word bigint_divop(word n1, word n0, word d)
95{
96 word high = n1 % d, quotient = 0;
97
98 for (u32bit j = 0; j != MP_WORD_BITS; ++j) {
99 word high_top_bit = (high & MP_WORD_TOP_BIT);
100
101 high <<= 1;
102 high |= (n0 >> (MP_WORD_BITS - 1 - j)) & 1;
103 quotient <<= 1;
104
105 if (high_top_bit || high >= d) {
106 high -= d;
107 quotient |= 1;
108 }
109 }
110
111 return quotient;
112}
113
114/*************************************************
115 * Do a 2-word/1-word Modulo *
116 *************************************************/
117word bigint_modop(word n1, word n0, word d)
118{
119 word z = bigint_divop(n1, n0, d);
120 word dummy = 0;
121 z = word_madd2(a: z, b: d, c: dummy, carry: &dummy);
122 return (n0 - z);
123}
124
125/*************************************************
126 * Do a word*word->2-word Multiply *
127 *************************************************/
128void bigint_wordmul(word a, word b, word *out_low, word *out_high)
129{
130 const u32bit MP_HWORD_BITS = MP_WORD_BITS / 2;
131 const word MP_HWORD_MASK = ((word)1 << MP_HWORD_BITS) - 1;
132
133 const word a_hi = (a >> MP_HWORD_BITS);
134 const word a_lo = (a & MP_HWORD_MASK);
135 const word b_hi = (b >> MP_HWORD_BITS);
136 const word b_lo = (b & MP_HWORD_MASK);
137
138 word x0 = a_hi * b_hi;
139 word x1 = a_lo * b_hi;
140 word x2 = a_hi * b_lo;
141 word x3 = a_lo * b_lo;
142
143 x2 += x3 >> (MP_HWORD_BITS);
144 x2 += x1;
145 if (x2 < x1)
146 x0 += ((word)1 << MP_HWORD_BITS);
147
148 *out_high = x0 + (x2 >> MP_HWORD_BITS);
149 *out_low = ((x2 & MP_HWORD_MASK) << MP_HWORD_BITS) + (x3 & MP_HWORD_MASK);
150}
151}
152
153}
154} // WRAPNS_LINE
155

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