Following the license change, modify the boilerplates in crypto/bn/
[openssl.git] / crypto / bn / bn_word.c
1 /*
2  * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
3  *
4  * Licensed under the Apache License 2.0 (the "License").  You may not use
5  * this file except in compliance with the License.  You can obtain a copy
6  * in the file LICENSE in the source distribution or at
7  * https://www.openssl.org/source/license.html
8  */
9
10 #include "internal/cryptlib.h"
11 #include "bn_lcl.h"
12
13 BN_ULONG BN_mod_word(const BIGNUM *a, BN_ULONG w)
14 {
15 #ifndef BN_LLONG
16     BN_ULONG ret = 0;
17 #else
18     BN_ULLONG ret = 0;
19 #endif
20     int i;
21
22     if (w == 0)
23         return (BN_ULONG)-1;
24
25 #ifndef BN_LLONG
26     /*
27      * If |w| is too long and we don't have BN_ULLONG then we need to fall
28      * back to using BN_div_word
29      */
30     if (w > ((BN_ULONG)1 << BN_BITS4)) {
31         BIGNUM *tmp = BN_dup(a);
32         if (tmp == NULL)
33             return (BN_ULONG)-1;
34
35         ret = BN_div_word(tmp, w);
36         BN_free(tmp);
37
38         return ret;
39     }
40 #endif
41
42     bn_check_top(a);
43     w &= BN_MASK2;
44     for (i = a->top - 1; i >= 0; i--) {
45 #ifndef BN_LLONG
46         /*
47          * We can assume here that | w <= ((BN_ULONG)1 << BN_BITS4) | and so
48          * | ret < ((BN_ULONG)1 << BN_BITS4) | and therefore the shifts here are
49          * safe and will not overflow
50          */
51         ret = ((ret << BN_BITS4) | ((a->d[i] >> BN_BITS4) & BN_MASK2l)) % w;
52         ret = ((ret << BN_BITS4) | (a->d[i] & BN_MASK2l)) % w;
53 #else
54         ret = (BN_ULLONG) (((ret << (BN_ULLONG) BN_BITS2) | a->d[i]) %
55                            (BN_ULLONG) w);
56 #endif
57     }
58     return (BN_ULONG)ret;
59 }
60
61 BN_ULONG BN_div_word(BIGNUM *a, BN_ULONG w)
62 {
63     BN_ULONG ret = 0;
64     int i, j;
65
66     bn_check_top(a);
67     w &= BN_MASK2;
68
69     if (!w)
70         /* actually this an error (division by zero) */
71         return (BN_ULONG)-1;
72     if (a->top == 0)
73         return 0;
74
75     /* normalize input (so bn_div_words doesn't complain) */
76     j = BN_BITS2 - BN_num_bits_word(w);
77     w <<= j;
78     if (!BN_lshift(a, a, j))
79         return (BN_ULONG)-1;
80
81     for (i = a->top - 1; i >= 0; i--) {
82         BN_ULONG l, d;
83
84         l = a->d[i];
85         d = bn_div_words(ret, l, w);
86         ret = (l - ((d * w) & BN_MASK2)) & BN_MASK2;
87         a->d[i] = d;
88     }
89     if ((a->top > 0) && (a->d[a->top - 1] == 0))
90         a->top--;
91     ret >>= j;
92     if (!a->top)
93         a->neg = 0; /* don't allow negative zero */
94     bn_check_top(a);
95     return ret;
96 }
97
98 int BN_add_word(BIGNUM *a, BN_ULONG w)
99 {
100     BN_ULONG l;
101     int i;
102
103     bn_check_top(a);
104     w &= BN_MASK2;
105
106     /* degenerate case: w is zero */
107     if (!w)
108         return 1;
109     /* degenerate case: a is zero */
110     if (BN_is_zero(a))
111         return BN_set_word(a, w);
112     /* handle 'a' when negative */
113     if (a->neg) {
114         a->neg = 0;
115         i = BN_sub_word(a, w);
116         if (!BN_is_zero(a))
117             a->neg = !(a->neg);
118         return i;
119     }
120     for (i = 0; w != 0 && i < a->top; i++) {
121         a->d[i] = l = (a->d[i] + w) & BN_MASK2;
122         w = (w > l) ? 1 : 0;
123     }
124     if (w && i == a->top) {
125         if (bn_wexpand(a, a->top + 1) == NULL)
126             return 0;
127         a->top++;
128         a->d[i] = w;
129     }
130     bn_check_top(a);
131     return 1;
132 }
133
134 int BN_sub_word(BIGNUM *a, BN_ULONG w)
135 {
136     int i;
137
138     bn_check_top(a);
139     w &= BN_MASK2;
140
141     /* degenerate case: w is zero */
142     if (!w)
143         return 1;
144     /* degenerate case: a is zero */
145     if (BN_is_zero(a)) {
146         i = BN_set_word(a, w);
147         if (i != 0)
148             BN_set_negative(a, 1);
149         return i;
150     }
151     /* handle 'a' when negative */
152     if (a->neg) {
153         a->neg = 0;
154         i = BN_add_word(a, w);
155         a->neg = 1;
156         return i;
157     }
158
159     if ((a->top == 1) && (a->d[0] < w)) {
160         a->d[0] = w - a->d[0];
161         a->neg = 1;
162         return 1;
163     }
164     i = 0;
165     for (;;) {
166         if (a->d[i] >= w) {
167             a->d[i] -= w;
168             break;
169         } else {
170             a->d[i] = (a->d[i] - w) & BN_MASK2;
171             i++;
172             w = 1;
173         }
174     }
175     if ((a->d[i] == 0) && (i == (a->top - 1)))
176         a->top--;
177     bn_check_top(a);
178     return 1;
179 }
180
181 int BN_mul_word(BIGNUM *a, BN_ULONG w)
182 {
183     BN_ULONG ll;
184
185     bn_check_top(a);
186     w &= BN_MASK2;
187     if (a->top) {
188         if (w == 0)
189             BN_zero(a);
190         else {
191             ll = bn_mul_words(a->d, a->d, a->top, w);
192             if (ll) {
193                 if (bn_wexpand(a, a->top + 1) == NULL)
194                     return 0;
195                 a->d[a->top++] = ll;
196             }
197         }
198     }
199     bn_check_top(a);
200     return 1;
201 }