← Back to branch summary

~ubuntu-branches/ubuntu/saucy/nettle/saucy-proposed

« back to all changes in this revision

Viewing changes to bignum.c

  • Committer: Bazaar Package Importer
  • Author(s): Marek Habersack
  • Date: 2004-05-04 15:56:02 UTC
  • Revision ID: james.westby@ubuntu.com-20040504155602-7jbhw5mabvwksl3j
Tags: upstream-1.10
Import upstream version 1.10

Show diffs side-by-side

added added

removed removed

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