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     if (!r->top)
  78         r->neg = 0; /* don't allow negative zero */
  79     bn_check_top(r);
  80     return 1;
  81 }
  82
  83 int BN_lshift(BIGNUM *r, const BIGNUM *a, int n)
  84 {
  85     int i, nw, lb, rb;
  86     BN_ULONG *t, *f;
  87     BN_ULONG l;
  88
  89     bn_check_top(r);
  90     bn_check_top(a);
  91
  92     if (n < 0) {
  93         BNerr(BN_F_BN_LSHIFT, BN_R_INVALID_SHIFT);
  94         return 0;
  95     }
  96
  97     nw = n / BN_BITS2;
  98     if (bn_wexpand(r, a->top + nw + 1) == NULL)
  99         return 0;
 100     r->neg = a->neg;
 101     lb = n % BN_BITS2;
 102     rb = BN_BITS2 - lb;
 103     f = a->d;
 104     t = r->d;
 105     t[a->top + nw] = 0;
 106     if (lb == 0)
 107         for (i = a->top - 1; i >= 0; i--)
 108             t[nw + i] = f[i];
 109     else
 110         for (i = a->top - 1; i >= 0; i--) {
 111             l = f[i];
 112             t[nw + i + 1] |= (l >> rb) & BN_MASK2;
 113             t[nw + i] = (l << lb) & BN_MASK2;
 114         }
 115     memset(t, 0, sizeof(*t) * nw);
 116     r->top = a->top + nw + 1;
 117     bn_correct_top(r);
 118     bn_check_top(r);
 119     return 1;
 120 }
 121
 122 int BN_rshift(BIGNUM *r, const BIGNUM *a, int n)
 123 {
 124     int i, j, nw, lb, rb;
 125     BN_ULONG *t, *f;
 126     BN_ULONG l, tmp;
 127
 128     bn_check_top(r);
 129     bn_check_top(a);
 130
 131     if (n < 0) {
 132         BNerr(BN_F_BN_RSHIFT, BN_R_INVALID_SHIFT);
 133         return 0;
 134     }
 135
 136     nw = n / BN_BITS2;
 137     rb = n % BN_BITS2;
 138     lb = BN_BITS2 - rb;
 139     if (nw >= a->top || a->top == 0) {
 140         BN_zero(r);
 141         return 1;
 142     }
 143     i = (BN_num_bits(a) - n + (BN_BITS2 - 1)) / BN_BITS2;
 144     if (r != a) {
 145         if (bn_wexpand(r, i) == NULL)
 146             return 0;
 147         r->neg = a->neg;
 148     } else {
 149         if (n == 0)
 150             return 1;           /* or the copying loop will go berserk */
 151     }
 152
 153     f = &(a->d[nw]);
 154     t = r->d;
 155     j = a->top - nw;
 156     r->top = i;
 157
 158     if (rb == 0) {
 159         for (i = j; i != 0; i--)
 160             *(t++) = *(f++);
 161     } else {
 162         l = *(f++);
 163         for (i = j - 1; i != 0; i--) {
 164             tmp = (l >> rb) & BN_MASK2;
 165             l = *(f++);
 166             *(t++) = (tmp | (l << lb)) & BN_MASK2;
 167         }
 168         if ((l = (l >> rb) & BN_MASK2))
 169             *(t) = l;
 170     }
 171     if (!r->top)
 172         r->neg = 0; /* don't allow negative zero */
 173     bn_check_top(r);
 174     return 1;
 175 }