bignum.c

   1 /* bignum.c
   2
   3    Bignum operations that are missing from gmp.
   4
   5    Copyright (C) 2001 Niels Möller
   6
   7    This file is part of GNU Nettle.
   8
   9    GNU Nettle is free software: you can redistribute it and/or
  10    modify it under the terms of either:
  11
  12      * the GNU Lesser General Public License as published by the Free
  13        Software Foundation; either version 3 of the License, or (at your
  14        option) any later version.
  15
  16    or
  17
  18      * the GNU General Public License as published by the Free
  19        Software Foundation; either version 2 of the License, or (at your
  20        option) any later version.
  21
  22    or both in parallel, as here.
  23
  24    GNU Nettle is distributed in the hope that it will be useful,
  25    but WITHOUT ANY WARRANTY; without even the implied warranty of
  26    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  27    General Public License for more details.
  28
  29    You should have received copies of the GNU General Public License and
  30    the GNU Lesser General Public License along with this program.  If
  31    not, see http://www.gnu.org/licenses/.
  32 */
  33
  34 #if HAVE_CONFIG_H
  35 # include "config.h"
  36 #endif
  37
  38 #include <assert.h>
  39 #include <string.h>
  40
  41 #include "bignum.h"
  42
  43 /* Two's complement negation means that -x = ~x + 1, ~x = -(x+1),
  44  * and we use that x = ~~x = ~(-x-1).
  45  *
  46  * Examples:
  47  *
  48  *   x  ~x = -x+1     ~~x = x
  49  *  -1          0          ff
  50  *  -2          1          fe
  51  * -7f         7e          81
  52  * -80         7f          80
  53  * -81         80        ff7f
  54  */
  55
  56 /* Including extra sign bit, if needed. Also one byte for zero. */
  57 size_t
  58 nettle_mpz_sizeinbase_256_s(const mpz_t x)
  59 {
  60   if (mpz_sgn(x) >= 0)
  61     return 1 + mpz_sizeinbase(x, 2) / 8;
  62   else
  63     {
  64       /* We'll output ~~x, so we need as many bits as for ~x */
  65       size_t size;
  66       mpz_t c;
  67
  68       mpz_init(c);
  69       mpz_com(c, x); /* Same as c = - x - 1 = |x| + 1 */
  70       size = 1 + mpz_sizeinbase(c,2) / 8;
  71       mpz_clear(c);
  72
  73       return size;
  74     }
  75 }
  76
  77 size_t
  78 nettle_mpz_sizeinbase_256_u(const mpz_t x)
  79 {
  80   return (mpz_sizeinbase(x,2) + 7) / 8;
  81 }
  82
  83 static void
  84 nettle_mpz_to_octets(size_t length, uint8_t *s,
  85                      const mpz_t x, uint8_t sign)
  86 {
  87   uint8_t *dst = s + length - 1;
  88   size_t size = mpz_size(x);
  89   size_t i;
  90
  91   for (i = 0; i<size; i++)
  92     {
  93       mp_limb_t limb = mpz_getlimbn(x, i);
  94       size_t j;
  95
  96       for (j = 0; length && j < sizeof(mp_limb_t); j++)
  97         {
  98           *dst-- = sign ^ (limb & 0xff);
  99           limb >>= 8;
 100           length--;
 101         }
 102     }
 103
 104   if (length)
 105     memset(s, sign, length);
 106 }
 107
 108 void
 109 nettle_mpz_get_str_256(size_t length, uint8_t *s, const mpz_t x)
 110 {
 111   if (!length)
 112     {
 113       /* x must be zero */
 114       assert(!mpz_sgn(x));
 115       return;
 116     }
 117
 118   if (mpz_sgn(x) >= 0)
 119     {
 120       assert(nettle_mpz_sizeinbase_256_u(x) <= length);
 121       nettle_mpz_to_octets(length, s, x, 0);
 122     }
 123   else
 124     {
 125       mpz_t c;
 126       mpz_init(c);
 127       mpz_com(c, x);
 128
 129       assert(nettle_mpz_sizeinbase_256_u(c) <= length);
 130       nettle_mpz_to_octets(length, s, c, 0xff);
 131
 132       mpz_clear(c);
 133     }
 134 }
 135
 136 /* Converting from strings */
 137
 138 #ifdef mpz_import
 139 /* Was introduced in GMP-4.1 */
 140 # define nettle_mpz_from_octets(x, length, s) \
 141    mpz_import((x), (length), 1, 1, 0, 0, (s))
 142 #else
 143 static void
 144 nettle_mpz_from_octets(mpz_t x,
 145                        size_t length, const uint8_t *s)
 146 {
 147   size_t i;
 148
 149   mpz_set_ui(x, 0);
 150
 151   for (i = 0; i < length; i++)
 152     {
 153       mpz_mul_2exp(x, x, 8);
 154       mpz_add_ui(x, x, s[i]);
 155     }
 156 }
 157 #endif
 158
 159 void
 160 nettle_mpz_set_str_256_u(mpz_t x,
 161                          size_t length, const uint8_t *s)
 162 {
 163   nettle_mpz_from_octets(x, length, s);
 164 }
 165
 166 void
 167 nettle_mpz_init_set_str_256_u(mpz_t x,
 168                               size_t length, const uint8_t *s)
 169 {
 170   mpz_init(x);
 171   nettle_mpz_from_octets(x, length, s);
 172 }
 173
 174 void
 175 nettle_mpz_set_str_256_s(mpz_t x,
 176                          size_t length, const uint8_t *s)
 177 {
 178   if (!length)
 179     {
 180       mpz_set_ui(x, 0);
 181       return;
 182     }
 183
 184   nettle_mpz_from_octets(x, length, s);
 185
 186   if (s[0] & 0x80)
 187     {
 188       mpz_t t;
 189
 190       mpz_init_set_ui(t, 1);
 191       mpz_mul_2exp(t, t, length*8);
 192       mpz_sub(x, x, t);
 193       mpz_clear(t);
 194     }
 195 }
 196
 197 void
 198 nettle_mpz_init_set_str_256_s(mpz_t x,
 199                               size_t length, const uint8_t *s)
 200 {
 201   mpz_init(x);
 202   nettle_mpz_set_str_256_s(x, length, s);
 203 }