Fix typo in cipher_chacha20_poly1305_hw.c.
[openssl.git] / crypto / bn / bn_shift.c
1 /*
2  * Copyright 1995-2018 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 <assert.h>
11 #include "internal/cryptlib.h"
12 #include "bn_local.h"
13
14 int BN_lshift1(BIGNUM *r, const BIGNUM *a)
15 {
16     register BN_ULONG *ap, *rp, t, c;
17     int i;
18
19     bn_check_top(r);
20     bn_check_top(a);
21
22     if (r != a) {
23         r->neg = a->neg;
24         if (bn_wexpand(r, a->top + 1) == NULL)
25             return 0;
26         r->top = a->top;
27     } else {
28         if (bn_wexpand(r, a->top + 1) == NULL)
29             return 0;
30     }
31     ap = a->d;
32     rp = r->d;
33     c = 0;
34     for (i = 0; i < a->top; i++) {
35         t = *(ap++);
36         *(rp++) = ((t << 1) | c) & BN_MASK2;
37         c = (t & BN_TBIT) ? 1 : 0;
38     }
39     if (c) {
40         *rp = 1;
41         r->top++;
42     }
43     bn_check_top(r);
44     return 1;
45 }
46
47 int BN_rshift1(BIGNUM *r, const BIGNUM *a)
48 {
49     BN_ULONG *ap, *rp, t, c;
50     int i, j;
51
52     bn_check_top(r);
53     bn_check_top(a);
54
55     if (BN_is_zero(a)) {
56         BN_zero(r);
57         return 1;
58     }
59     i = a->top;
60     ap = a->d;
61     j = i - (ap[i - 1] == 1);
62     if (a != r) {
63         if (bn_wexpand(r, j) == NULL)
64             return 0;
65         r->neg = a->neg;
66     }
67     rp = r->d;
68     t = ap[--i];
69     c = (t & 1) ? BN_TBIT : 0;
70     if (t >>= 1)
71         rp[i] = t;
72     while (i > 0) {
73         t = ap[--i];
74         rp[i] = ((t >> 1) & BN_MASK2) | c;
75         c = (t & 1) ? BN_TBIT : 0;
76     }
77     r->top = j;
78     if (!r->top)
79         r->neg = 0; /* don't allow negative zero */
80     bn_check_top(r);
81     return 1;
82 }
83
84 int BN_lshift(BIGNUM *r, const BIGNUM *a, int n)
85 {
86     int ret;
87
88     if (n < 0) {
89         BNerr(BN_F_BN_LSHIFT, BN_R_INVALID_SHIFT);
90         return 0;
91     }
92
93     ret = bn_lshift_fixed_top(r, a, n);
94
95     bn_correct_top(r);
96     bn_check_top(r);
97
98     return ret;
99 }
100
101 /*
102  * In respect to shift factor the execution time is invariant of
103  * |n % BN_BITS2|, but not |n / BN_BITS2|. Or in other words pre-condition
104  * for constant-time-ness is |n < BN_BITS2| or |n / BN_BITS2| being
105  * non-secret.
106  */
107 int bn_lshift_fixed_top(BIGNUM *r, const BIGNUM *a, int n)
108 {
109     int i, nw;
110     unsigned int lb, rb;
111     BN_ULONG *t, *f;
112     BN_ULONG l, m, rmask = 0;
113
114     assert(n >= 0);
115
116     bn_check_top(r);
117     bn_check_top(a);
118
119     nw = n / BN_BITS2;
120     if (bn_wexpand(r, a->top + nw + 1) == NULL)
121         return 0;
122
123     if (a->top != 0) {
124         lb = (unsigned int)n % BN_BITS2;
125         rb = BN_BITS2 - lb;
126         rb %= BN_BITS2;            /* say no to undefined behaviour */
127         rmask = (BN_ULONG)0 - rb;  /* rmask = 0 - (rb != 0) */
128         rmask |= rmask >> 8;
129         f = &(a->d[0]);
130         t = &(r->d[nw]);
131         l = f[a->top - 1];
132         t[a->top] = (l >> rb) & rmask;
133         for (i = a->top - 1; i > 0; i--) {
134             m = l << lb;
135             l = f[i - 1];
136             t[i] = (m | ((l >> rb) & rmask)) & BN_MASK2;
137         }
138         t[0] = (l << lb) & BN_MASK2;
139     } else {
140         /* shouldn't happen, but formally required */
141         r->d[nw] = 0;
142     }
143     if (nw != 0)
144         memset(r->d, 0, sizeof(*t) * nw);
145
146     r->neg = a->neg;
147     r->top = a->top + nw + 1;
148     r->flags |= BN_FLG_FIXED_TOP;
149
150     return 1;
151 }
152
153 int BN_rshift(BIGNUM *r, const BIGNUM *a, int n)
154 {
155     int ret = 0;
156
157     if (n < 0) {
158         BNerr(BN_F_BN_RSHIFT, BN_R_INVALID_SHIFT);
159         return 0;
160     }
161
162     ret = bn_rshift_fixed_top(r, a, n);
163
164     bn_correct_top(r);
165     bn_check_top(r);
166
167     return ret;
168 }
169
170 /*
171  * In respect to shift factor the execution time is invariant of
172  * |n % BN_BITS2|, but not |n / BN_BITS2|. Or in other words pre-condition
173  * for constant-time-ness for sufficiently[!] zero-padded inputs is
174  * |n < BN_BITS2| or |n / BN_BITS2| being non-secret.
175  */
176 int bn_rshift_fixed_top(BIGNUM *r, const BIGNUM *a, int n)
177 {
178     int i, top, nw;
179     unsigned int lb, rb;
180     BN_ULONG *t, *f;
181     BN_ULONG l, m, mask;
182
183     bn_check_top(r);
184     bn_check_top(a);
185
186     assert(n >= 0);
187
188     nw = n / BN_BITS2;
189     if (nw >= a->top) {
190         /* shouldn't happen, but formally required */
191         BN_zero(r);
192         return 1;
193     }
194
195     rb = (unsigned int)n % BN_BITS2;
196     lb = BN_BITS2 - rb;
197     lb %= BN_BITS2;            /* say no to undefined behaviour */
198     mask = (BN_ULONG)0 - lb;   /* mask = 0 - (lb != 0) */
199     mask |= mask >> 8;
200     top = a->top - nw;
201     if (r != a && bn_wexpand(r, top) == NULL)
202         return 0;
203
204     t = &(r->d[0]);
205     f = &(a->d[nw]);
206     l = f[0];
207     for (i = 0; i < top - 1; i++) {
208         m = f[i + 1];
209         t[i] = (l >> rb) | ((m << lb) & mask);
210         l = m;
211     }
212     t[i] = l >> rb;
213
214     r->neg = a->neg;
215     r->top = top;
216     r->flags |= BN_FLG_FIXED_TOP;
217
218     return 1;
219 }