diff options
| author | jsing <> | 2023-01-05 04:51:13 +0000 |
|---|---|---|
| committer | jsing <> | 2023-01-05 04:51:13 +0000 |
| commit | 2feadbb4023f1dfdb2ca4d0bbf07c8bb21440b19 (patch) | |
| tree | 14009b83106fd4fa918b0f183c1537afa8848e46 /src/lib | |
| parent | 95798f26b671da642392d4eafa1304fc0cd2139b (diff) | |
| download | openbsd-2feadbb4023f1dfdb2ca4d0bbf07c8bb21440b19.tar.gz openbsd-2feadbb4023f1dfdb2ca4d0bbf07c8bb21440b19.tar.bz2 openbsd-2feadbb4023f1dfdb2ca4d0bbf07c8bb21440b19.zip | |
Rewrite BN_rshift()
This improves readability and eliminates special handling for various
cases, making the code cleaner and closer to constant time.
Basic benchmarking shows a performance gain on modern 64 bit architectures,
while there is a decrease on legacy 32 bit architectures (i386),
particularly for the zero bit shift case (which is now handled in the
same code path).
ok tb@
Diffstat (limited to 'src/lib')
| -rw-r--r-- | src/lib/libcrypto/bn/bn_shift.c | 79 |
1 files changed, 42 insertions, 37 deletions
diff --git a/src/lib/libcrypto/bn/bn_shift.c b/src/lib/libcrypto/bn/bn_shift.c index 6f62d6488e..09f1c738ad 100644 --- a/src/lib/libcrypto/bn/bn_shift.c +++ b/src/lib/libcrypto/bn/bn_shift.c | |||
| @@ -1,4 +1,4 @@ | |||
| 1 | /* $OpenBSD: bn_shift.c,v 1.17 2022/11/26 16:08:51 tb Exp $ */ | 1 | /* $OpenBSD: bn_shift.c,v 1.18 2023/01/05 04:51:13 jsing Exp $ */ |
| 2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) | 2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) |
| 3 | * All rights reserved. | 3 | * All rights reserved. |
| 4 | * | 4 | * |
| @@ -169,50 +169,55 @@ BN_lshift(BIGNUM *r, const BIGNUM *a, int n) | |||
| 169 | int | 169 | int |
| 170 | BN_rshift(BIGNUM *r, const BIGNUM *a, int n) | 170 | BN_rshift(BIGNUM *r, const BIGNUM *a, int n) |
| 171 | { | 171 | { |
| 172 | int i, j, nw, lb, rb; | 172 | size_t count, shift_bits, shift_words; |
| 173 | BN_ULONG *t, *f; | 173 | size_t lshift, rshift; |
| 174 | BN_ULONG l, tmp; | 174 | ssize_t lstride; |
| 175 | BN_ULONG *dst, *src; | ||
| 176 | size_t i; | ||
| 175 | 177 | ||
| 176 | if (n < 0) { | 178 | if (n < 0) { |
| 177 | BNerror(BN_R_INVALID_LENGTH); | 179 | BNerror(BN_R_INVALID_LENGTH); |
| 178 | return 0; | 180 | return 0; |
| 179 | } | 181 | } |
| 180 | 182 | shift_bits = n; | |
| 181 | 183 | ||
| 182 | nw = n / BN_BITS2; | 184 | /* |
| 183 | rb = n % BN_BITS2; | 185 | * Right bit shift, potentially across word boundaries. |
| 184 | lb = BN_BITS2 - rb; | 186 | * |
| 185 | if (nw >= a->top || a->top == 0) { | 187 | * When shift is not an exact multiple of BN_BITS2, the top bits of |
| 188 | * the next word need to be left shifted and combined with the right | ||
| 189 | * shifted bits using bitwise OR. If shift is an exact multiple of | ||
| 190 | * BN_BITS2, the source for the left and right shifts are the same | ||
| 191 | * and the shifts become zero (which is effectively a memmove). | ||
| 192 | */ | ||
| 193 | shift_words = shift_bits / BN_BITS2; | ||
| 194 | rshift = shift_bits % BN_BITS2; | ||
| 195 | lshift = (BN_BITS2 - rshift) % BN_BITS2; | ||
| 196 | lstride = (lshift + rshift) / BN_BITS2; | ||
| 197 | |||
| 198 | if (a->top <= shift_words) { | ||
| 186 | BN_zero(r); | 199 | BN_zero(r); |
| 187 | return (1); | 200 | return 1; |
| 188 | } | ||
| 189 | i = (BN_num_bits(a) - n + (BN_BITS2 - 1)) / BN_BITS2; | ||
| 190 | if (r != a) { | ||
| 191 | r->neg = a->neg; | ||
| 192 | if (!bn_wexpand(r, i)) | ||
| 193 | return (0); | ||
| 194 | } else { | ||
| 195 | if (n == 0) | ||
| 196 | return 1; /* or the copying loop will go berserk */ | ||
| 197 | } | 201 | } |
| 202 | count = a->top - shift_words; | ||
| 198 | 203 | ||
| 199 | f = &(a->d[nw]); | 204 | if (!bn_wexpand(r, count)) |
| 200 | t = r->d; | 205 | return 0; |
| 201 | j = a->top - nw; | ||
| 202 | r->top = i; | ||
| 203 | 206 | ||
| 204 | if (rb == 0) { | 207 | src = a->d + shift_words; |
| 205 | for (i = j; i != 0; i--) | 208 | dst = r->d; |
| 206 | *(t++) = *(f++); | 209 | |
| 207 | } else { | 210 | for (i = 1; i < count; i++) { |
| 208 | l = *(f++); | 211 | *dst = src[lstride] << lshift | *src >> rshift; |
| 209 | for (i = j - 1; i != 0; i--) { | 212 | src++; |
| 210 | tmp = (l >> rb) & BN_MASK2; | 213 | dst++; |
| 211 | l = *(f++); | ||
| 212 | *(t++) = (tmp|(l << lb)) & BN_MASK2; | ||
| 213 | } | ||
| 214 | if ((l = (l >> rb) & BN_MASK2)) | ||
| 215 | *(t) = l; | ||
| 216 | } | 214 | } |
| 217 | return (1); | 215 | *dst = *src >> rshift; |
| 216 | |||
| 217 | r->top = count; | ||
| 218 | r->neg = a->neg; | ||
| 219 | |||
| 220 | bn_correct_top(r); | ||
| 221 | |||
| 222 | return 1; | ||
| 218 | } | 223 | } |