← Back to branch summary

~ubuntu-branches/debian/sid/botan/sid

« back to all changes in this revision

Viewing changes to src/mp_misc.cpp

  • Committer: Package Import Robot
  • Author(s): Laszlo Boszormenyi (GCS)
  • Date: 2018-03-01 22:23:25 UTC
  • mfrom: (1.2.2)
  • Revision ID: package-import@ubuntu.com-20180301222325-7p7vc45gu3hta34d
Tags: 2.4.0-2
* Don't remove .doctrees from the manual if it doesn't exist.
* Don't specify parallel to debhelper.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/mp_misc.cpp
1
 
/*************************************************
2
 
* MP Misc Functions Source File                  *
3
 
* (C) 1999-2007 The Botan Project                *
4
 
*************************************************/
5
 
 
6
 
#include <botan/mp_core.h>
7
 
#include <botan/mp_asm.h>
8
 
 
9
 
namespace Botan {
10
 
 
11
 
extern "C" {
12
 
 
13
 
/*************************************************
14
 
* Core Division Operation                        *
15
 
*************************************************/
16
 
u32bit bigint_divcore(word q, word y1, word y2,
17
 
                      word x1, word x2, word x3)
18
 
   {
19
 
   word y0 = 0;
20
 
   y2 = word_madd2(q, y2, y0, &y0);
21
 
   y1 = word_madd2(q, y1, y0, &y0);
22
 
 
23
 
   if(y0 > x1) return 1;
24
 
   if(y0 < x1) return 0;
25
 
   if(y1 > x2)  return 1;
26
 
   if(y1 < x2)  return 0;
27
 
   if(y2 > x3)  return 1;
28
 
   if(y2 < x3)  return 0;
29
 
   return 0;
30
 
   }
31
 
 
32
 
/*************************************************
33
 
* Compare two MP integers                        *
34
 
*************************************************/
35
 
s32bit bigint_cmp(const word x[], u32bit x_size,
36
 
                  const word y[], u32bit y_size)
37
 
   {
38
 
   if(x_size < y_size) { return (-bigint_cmp(y, y_size, x, x_size)); }
39
 
 
40
 
   while(x_size > y_size)
41
 
      {
42
 
      if(x[x_size-1])
43
 
         return 1;
44
 
      x_size--;
45
 
      }
46
 
   for(u32bit j = x_size; j > 0; --j)
47
 
      {
48
 
      if(x[j-1] > y[j-1]) return 1;
49
 
      if(x[j-1] < y[j-1]) return -1;
50
 
      }
51
 
   return 0;
52
 
   }
53
 
 
54
 
/*************************************************
55
 
* Do a 2-word/1-word Division                    *
56
 
*************************************************/
57
 
word bigint_divop(word n1, word n0, word d)
58
 
   {
59
 
   word high = n1 % d, quotient = 0;
60
 
 
61
 
   for(u32bit j = 0; j != MP_WORD_BITS; ++j)
62
 
      {
63
 
      word high_top_bit = (high & MP_WORD_TOP_BIT);
64
 
 
65
 
      high <<= 1;
66
 
      high |= (n0 >> (MP_WORD_BITS-1-j)) & 1;
67
 
      quotient <<= 1;
68
 
 
69
 
      if(high_top_bit || high >= d)
70
 
         {
71
 
         high -= d;
72
 
         quotient |= 1;
73
 
         }
74
 
      }
75
 
 
76
 
   return quotient;
77
 
   }
78
 
 
79
 
/*************************************************
80
 
* Do a 2-word/1-word Modulo                      *
81
 
*************************************************/
82
 
word bigint_modop(word n1, word n0, word d)
83
 
   {
84
 
   word z = bigint_divop(n1, n0, d);
85
 
   word dummy = 0;
86
 
   z = word_madd2(z, d, dummy, &dummy);
87
 
   return (n0-z);
88
 
   }
89
 
 
90
 
/*************************************************
91
 
* Do a word*word->2-word Multiply                *
92
 
*************************************************/
93
 
void bigint_wordmul(word a, word b, word* out_low, word* out_high)
94
 
   {
95
 
   const u32bit MP_HWORD_BITS = MP_WORD_BITS / 2;
96
 
   const word MP_HWORD_MASK = ((word)1 << MP_HWORD_BITS) - 1;
97
 
 
98
 
   const word a_hi = (a >> MP_HWORD_BITS);
99
 
   const word a_lo = (a & MP_HWORD_MASK);
100
 
   const word b_hi = (b >> MP_HWORD_BITS);
101
 
   const word b_lo = (b & MP_HWORD_MASK);
102
 
 
103
 
   word x0 = a_hi * b_hi;
104
 
   word x1 = a_lo * b_hi;
105
 
   word x2 = a_hi * b_lo;
106
 
   word x3 = a_lo * b_lo;
107
 
 
108
 
   x2 += x3 >> (MP_HWORD_BITS);
109
 
   x2 += x1;
110
 
   if(x2 < x1)
111
 
      x0 += ((word)1 << MP_HWORD_BITS);
112
 
 
113
 
   *out_high = x0 + (x2 >> MP_HWORD_BITS);
114
 
   *out_low = ((x2 & MP_HWORD_MASK) << MP_HWORD_BITS) + (x3 & MP_HWORD_MASK);
115
 
   }
116
 
 
117
 
}
118
 
 
119
 
}