crypto/bn/bn_shift.c

   1 /*
   2  * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
   3  *
   4  * Licensed under the OpenSSL license (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 int BN_lshift1(BIGNUM *r, const BIGNUM *a)
  14 {
  15     register BN_ULONG *ap, *rp, t, c;
  16     int i;
  17
  18     bn_check_top(r);
  19     bn_check_top(a);
  20
  21     if (r != a) {
  22         r->neg = a->neg;
  23         if (bn_wexpand(r, a->top + 1) == NULL)
  24             return (0);
  25         r->top = a->top;
  26     } else {
  27         if (bn_wexpand(r, a->top + 1) == NULL)
  28             return (0);
  29     }
  30     ap = a->d;
  31     rp = r->d;
  32     c = 0;
  33     for (i = 0; i < a->top; i++) {
  34         t = *(ap++);
  35         *(rp++) = ((t << 1) | c) & BN_MASK2;
  36         c = (t & BN_TBIT) ? 1 : 0;
  37     }
  38     if (c) {
  39         *rp = 1;
  40         r->top++;
  41     }
  42     bn_check_top(r);
  43     return (1);
  44 }
  45
  46 int BN_rshift1(BIGNUM *r, const BIGNUM *a)
  47 {
  48     BN_ULONG *ap, *rp, t, c;
  49     int i, j;
  50
  51     bn_check_top(r);
  52     bn_check_top(a);
  53
  54     if (BN_is_zero(a)) {
  55         BN_zero(r);
  56         return (1);
  57     }
  58     i = a->top;
  59     ap = a->d;
  60     j = i - (ap[i - 1] == 1);
  61     if (a != r) {
  62         if (bn_wexpand(r, j) == NULL)
  63             return (0);
  64         r->neg = a->neg;
  65     }
  66     rp = r->d;
  67     t = ap[--i];
  68     c = (t & 1) ? BN_TBIT : 0;
  69     if (t >>= 1)
  70         rp[i] = t;
  71     while (i > 0) {
  72         t = ap[--i];
  73         rp[i] = ((t >> 1) & BN_MASK2) | c;
  74         c = (t & 1) ? BN_TBIT : 0;
  75     }
  76     r->top = j;
  77     bn_check_top(r);
  78     return (1);
  79 }
  80
  81 int BN_lshift(BIGNUM *r, const BIGNUM *a, int n)
  82 {
  83     int i, nw, lb, rb;
  84     BN_ULONG *t, *f;
  85     BN_ULONG l;
  86
  87     bn_check_top(r);
  88     bn_check_top(a);
  89
  90     if (n < 0) {
  91         BNerr(BN_F_BN_LSHIFT, BN_R_INVALID_SHIFT);
  92         return 0;
  93     }
  94
  95     r->neg = a->neg;
  96     nw = n / BN_BITS2;
  97     if (bn_wexpand(r, a->top + nw + 1) == NULL)
  98         return (0);
  99     lb = n % BN_BITS2;
 100     rb = BN_BITS2 - lb;
 101     f = a->d;
 102     t = r->d;
 103     t[a->top + nw] = 0;
 104     if (lb == 0)
 105         for (i = a->top - 1; i >= 0; i--)
 106             t[nw + i] = f[i];
 107     else
 108         for (i = a->top - 1; i >= 0; i--) {
 109             l = f[i];
 110             t[nw + i + 1] |= (l >> rb) & BN_MASK2;
 111             t[nw + i] = (l << lb) & BN_MASK2;
 112         }
 113     memset(t, 0, sizeof(*t) * nw);
 114     r->top = a->top + nw + 1;
 115     bn_correct_top(r);
 116     bn_check_top(r);
 117     return (1);
 118 }
 119
 120 int BN_rshift(BIGNUM *r, const BIGNUM *a, int n)
 121 {
 122     int i, j, nw, lb, rb;
 123     BN_ULONG *t, *f;
 124     BN_ULONG l, tmp;
 125
 126     bn_check_top(r);
 127     bn_check_top(a);
 128
 129     if (n < 0) {
 130         BNerr(BN_F_BN_RSHIFT, BN_R_INVALID_SHIFT);
 131         return 0;
 132     }
 133
 134     nw = n / BN_BITS2;
 135     rb = n % BN_BITS2;
 136     lb = BN_BITS2 - rb;
 137     if (nw >= a->top || a->top == 0) {
 138         BN_zero(r);
 139         return (1);
 140     }
 141     i = (BN_num_bits(a) - n + (BN_BITS2 - 1)) / BN_BITS2;
 142     if (r != a) {
 143         r->neg = a->neg;
 144         if (bn_wexpand(r, i) == NULL)
 145             return (0);
 146     } else {
 147         if (n == 0)
 148             return 1;           /* or the copying loop will go berserk */
 149     }
 150
 151     f = &(a->d[nw]);
 152     t = r->d;
 153     j = a->top - nw;
 154     r->top = i;
 155
 156     if (rb == 0) {
 157         for (i = j; i != 0; i--)
 158             *(t++) = *(f++);
 159     } else {
 160         l = *(f++);
 161         for (i = j - 1; i != 0; i--) {
 162             tmp = (l >> rb) & BN_MASK2;
 163             l = *(f++);
 164             *(t++) = (tmp | (l << lb)) & BN_MASK2;
 165         }
 166         if ((l = (l >> rb) & BN_MASK2))
 167             *(t) = l;
 168     }
 169     bn_check_top(r);
 170     return (1);
 171 }