← Back to branch summary

~ubuntu-branches/ubuntu/trusty/grub2/trusty

« back to all changes in this revision

Viewing changes to grub-core/lib/libgcrypt-grub/mpi/mpi-bit.c

  • Committer: Package Import Robot
  • Author(s): Colin Watson
  • Date: 2014-01-16 15:18:04 UTC
  • mfrom: (17.6.38 experimental)
  • Revision ID: package-import@ubuntu.com-20140116151804-3foouk7fpqcq3sxx
Tags: 2.02~beta2-2
* Convert patch handling to git-dpm.
* Add bi-endian support to ELF parser (Tomohiro B Berry).
* Adjust restore_mkdevicemap.patch to mark get_kfreebsd_version as static,
  to appease "gcc -Werror=missing-prototypes".
* Cherry-pick from upstream:
  - Change grub-macbless' manual page section to 8.
* Install grub-glue-efi, grub-macbless, grub-render-label, and
  grub-syslinux2cfg.
* grub-shell: Pass -no-pad to xorriso when building floppy images.

Show diffs side-by-side

added added

removed removed

Lines of Context:
grub-core/lib/libgcrypt-grub/mpi/mpi-bit.c
 
1
/* This file was automatically imported with 
 
2
   import_gcry.py. Please don't modify it */
 
3
/* mpi-bit.c  -  MPI bit level functions
 
4
 * Copyright (C) 1998, 1999, 2001, 2002, 2006 Free Software Foundation, Inc.
 
5
 *
 
6
 * This file is part of Libgcrypt.
 
7
 *
 
8
 * Libgcrypt is free software; you can redistribute it and/or modify
 
9
 * it under the terms of the GNU Lesser General Public License as
 
10
 * published by the Free Software Foundation; either version 2.1 of
 
11
 * the License, or (at your option) any later version.
 
12
 *
 
13
 * Libgcrypt is distributed in the hope that it will be useful,
 
14
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
15
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
16
 * GNU Lesser General Public License for more details.
 
17
 *
 
18
 * You should have received a copy of the GNU Lesser General Public
 
19
 * License along with this program; if not, write to the Free Software
 
20
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
 
21
 */
 
22
 
 
23
#include <config.h>
 
24
#include <stdio.h>
 
25
#include <stdlib.h>
 
26
#include "mpi-internal.h"
 
27
#include "longlong.h"
 
28
 
 
29
 
 
30
#ifdef MPI_INTERNAL_NEED_CLZ_TAB
 
31
#ifdef __STDC__
 
32
const
 
33
#endif
 
34
unsigned char
 
35
_gcry_clz_tab[] =
 
36
{
 
37
  0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
 
38
  6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
 
39
  7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
 
40
  7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
 
41
  8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 
42
  8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 
43
  8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 
44
  8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 
45
};
 
46
#endif
 
47
 
 
48
 
 
49
#define A_LIMB_1 ((mpi_limb_t)1)
 
50
 
 
51
 
 
52
/****************
 
53
 * Sometimes we have MSL (most significant limbs) which are 0;
 
54
 * this is for some reasons not good, so this function removes them.
 
55
 */
 
56
void
 
57
_gcry_mpi_normalize( gcry_mpi_t a )
 
58
{
 
59
    if( mpi_is_opaque(a) )
 
60
        return;
 
61
 
 
62
    for( ; a->nlimbs && !a->d[a->nlimbs-1]; a->nlimbs-- )
 
63
        ;
 
64
}
 
65
 
 
66
 
 
67
 
 
68
/****************
 
69
 * Return the number of bits in A.
 
70
 */
 
71
unsigned int
 
72
gcry_mpi_get_nbits( gcry_mpi_t a )
 
73
{
 
74
    unsigned n;
 
75
 
 
76
    if( mpi_is_opaque(a) ) {
 
77
        return a->sign; /* which holds the number of bits */
 
78
    }
 
79
 
 
80
    _gcry_mpi_normalize( a );
 
81
    if( a->nlimbs ) {
 
82
        mpi_limb_t alimb = a->d[a->nlimbs-1];
 
83
        if( alimb )
 
84
            count_leading_zeros( n, alimb );
 
85
        else
 
86
            n = BITS_PER_MPI_LIMB;
 
87
        n = BITS_PER_MPI_LIMB - n + (a->nlimbs-1) * BITS_PER_MPI_LIMB;
 
88
    }
 
89
    else
 
90
        n = 0;
 
91
    return n;
 
92
}
 
93
 
 
94
 
 
95
/****************
 
96
 * Test whether bit N is set.
 
97
 */
 
98
int
 
99
gcry_mpi_test_bit( gcry_mpi_t a, unsigned int n )
 
100
{
 
101
    unsigned int limbno, bitno;
 
102
    mpi_limb_t limb;
 
103
 
 
104
    limbno = n / BITS_PER_MPI_LIMB;
 
105
    bitno  = n % BITS_PER_MPI_LIMB;
 
106
 
 
107
    if( limbno >= a->nlimbs )
 
108
        return 0; /* too far left: this is a 0 */
 
109
    limb = a->d[limbno];
 
110
    return (limb & (A_LIMB_1 << bitno))? 1: 0;
 
111
}
 
112
 
 
113
 
 
114
/****************
 
115
 * Set bit N of A.
 
116
 */
 
117
void
 
118
gcry_mpi_set_bit( gcry_mpi_t a, unsigned int n )
 
119
{
 
120
  unsigned int limbno, bitno;
 
121
 
 
122
  limbno = n / BITS_PER_MPI_LIMB;
 
123
  bitno  = n % BITS_PER_MPI_LIMB;
 
124
 
 
125
  if ( limbno >= a->nlimbs )
 
126
    {
 
127
      mpi_resize (a, limbno+1 );
 
128
      a->nlimbs = limbno+1;
 
129
    }
 
130
  a->d[limbno] |= (A_LIMB_1<<bitno);
 
131
}
 
132
 
 
133
/****************
 
134
 * Set bit N of A. and clear all bits above
 
135
 */
 
136
void
 
137
gcry_mpi_set_highbit( gcry_mpi_t a, unsigned int n )
 
138
{
 
139
  unsigned int limbno, bitno;
 
140
 
 
141
  limbno = n / BITS_PER_MPI_LIMB;
 
142
  bitno  = n % BITS_PER_MPI_LIMB;
 
143
 
 
144
  if ( limbno >= a->nlimbs )
 
145
    {
 
146
      mpi_resize (a, limbno+1 );
 
147
      a->nlimbs = limbno+1;
 
148
    }
 
149
  a->d[limbno] |= (A_LIMB_1<<bitno);
 
150
  for ( bitno++; bitno < BITS_PER_MPI_LIMB; bitno++ )
 
151
    a->d[limbno] &= ~(A_LIMB_1 << bitno);
 
152
  a->nlimbs = limbno+1;
 
153
}
 
154
 
 
155
/****************
 
156
 * clear bit N of A and all bits above
 
157
 */
 
158
void
 
159
gcry_mpi_clear_highbit( gcry_mpi_t a, unsigned int n )
 
160
{
 
161
    unsigned int limbno, bitno;
 
162
 
 
163
    limbno = n / BITS_PER_MPI_LIMB;
 
164
    bitno  = n % BITS_PER_MPI_LIMB;
 
165
 
 
166
    if( limbno >= a->nlimbs )
 
167
        return; /* not allocated, therefore no need to clear bits
 
168
                   :-) */
 
169
 
 
170
    for( ; bitno < BITS_PER_MPI_LIMB; bitno++ )
 
171
        a->d[limbno] &= ~(A_LIMB_1 << bitno);
 
172
    a->nlimbs = limbno+1;
 
173
}
 
174
 
 
175
/****************
 
176
 * Clear bit N of A.
 
177
 */
 
178
void
 
179
gcry_mpi_clear_bit( gcry_mpi_t a, unsigned int n )
 
180
{
 
181
    unsigned int limbno, bitno;
 
182
 
 
183
    limbno = n / BITS_PER_MPI_LIMB;
 
184
    bitno  = n % BITS_PER_MPI_LIMB;
 
185
 
 
186
    if( limbno >= a->nlimbs )
 
187
        return; /* don't need to clear this bit, it's to far to left */
 
188
    a->d[limbno] &= ~(A_LIMB_1 << bitno);
 
189
}
 
190
 
 
191
 
 
192
/****************
 
193
 * Shift A by COUNT limbs to the right
 
194
 * This is used only within the MPI library
 
195
 */
 
196
void
 
197
_gcry_mpi_rshift_limbs( gcry_mpi_t a, unsigned int count )
 
198
{
 
199
    mpi_ptr_t ap = a->d;
 
200
    mpi_size_t n = a->nlimbs;
 
201
    unsigned int i;
 
202
 
 
203
    if( count >= n ) {
 
204
        a->nlimbs = 0;
 
205
        return;
 
206
    }
 
207
 
 
208
    for( i = 0; i < n - count; i++ )
 
209
        ap[i] = ap[i+count];
 
210
    ap[i] = 0;
 
211
    a->nlimbs -= count;
 
212
}
 
213
 
 
214
 
 
215
/*
 
216
 * Shift A by N bits to the right.
 
217
 */
 
218
void
 
219
gcry_mpi_rshift ( gcry_mpi_t x, gcry_mpi_t a, unsigned int n )
 
220
{
 
221
  mpi_size_t xsize;
 
222
  unsigned int i;
 
223
  unsigned int nlimbs = (n/BITS_PER_MPI_LIMB);
 
224
  unsigned int nbits = (n%BITS_PER_MPI_LIMB);
 
225
 
 
226
  if ( x == a )
 
227
    {
 
228
      /* In-place operation.  */
 
229
      if ( nlimbs >= x->nlimbs )
 
230
        {
 
231
          x->nlimbs = 0;
 
232
          return;
 
233
        }
 
234
 
 
235
      if (nlimbs)
 
236
        {
 
237
          for (i=0; i < x->nlimbs - nlimbs; i++ )
 
238
            x->d[i] = x->d[i+nlimbs];
 
239
          x->d[i] = 0;
 
240
          x->nlimbs -= nlimbs;
 
241
 
 
242
        }
 
243
      if ( x->nlimbs && nbits )
 
244
        _gcry_mpih_rshift ( x->d, x->d, x->nlimbs, nbits );
 
245
    }
 
246
  else if ( nlimbs )
 
247
    {
 
248
      /* Copy and shift by more or equal bits than in a limb. */
 
249
      xsize = a->nlimbs;
 
250
      x->sign = a->sign;
 
251
      RESIZE_IF_NEEDED (x, xsize);
 
252
      x->nlimbs = xsize;
 
253
      for (i=0; i < a->nlimbs; i++ )
 
254
        x->d[i] = a->d[i];
 
255
      x->nlimbs = i;
 
256
 
 
257
      if ( nlimbs >= x->nlimbs )
 
258
        {
 
259
          x->nlimbs = 0;
 
260
          return;
 
261
        }
 
262
 
 
263
      if (nlimbs)
 
264
        {
 
265
          for (i=0; i < x->nlimbs - nlimbs; i++ )
 
266
            x->d[i] = x->d[i+nlimbs];
 
267
          x->d[i] = 0;
 
268
          x->nlimbs -= nlimbs;
 
269
        }
 
270
 
 
271
      if ( x->nlimbs && nbits )
 
272
        _gcry_mpih_rshift ( x->d, x->d, x->nlimbs, nbits );
 
273
    }
 
274
  else
 
275
    {
 
276
      /* Copy and shift by less than bits in a limb.  */
 
277
      xsize = a->nlimbs;
 
278
      x->sign = a->sign;
 
279
      RESIZE_IF_NEEDED (x, xsize);
 
280
      x->nlimbs = xsize;
 
281
 
 
282
      if ( xsize )
 
283
        {
 
284
          if (nbits )
 
285
            _gcry_mpih_rshift (x->d, a->d, x->nlimbs, nbits );
 
286
          else
 
287
            {
 
288
              /* The rshift helper function is not specified for
 
289
                 NBITS==0, thus we do a plain copy here. */
 
290
              for (i=0; i < x->nlimbs; i++ )
 
291
                x->d[i] = a->d[i];
 
292
            }
 
293
        }
 
294
    }
 
295
  MPN_NORMALIZE (x->d, x->nlimbs);
 
296
}
 
297
 
 
298
 
 
299
/****************
 
300
 * Shift A by COUNT limbs to the left
 
301
 * This is used only within the MPI library
 
302
 */
 
303
void
 
304
_gcry_mpi_lshift_limbs (gcry_mpi_t a, unsigned int count)
 
305
{
 
306
  mpi_ptr_t ap;
 
307
  int n = a->nlimbs;
 
308
  int i;
 
309
 
 
310
  if (!count || !n)
 
311
    return;
 
312
 
 
313
  RESIZE_IF_NEEDED (a, n+count);
 
314
 
 
315
  ap = a->d;
 
316
  for (i = n-1; i >= 0; i--)
 
317
    ap[i+count] = ap[i];
 
318
  for (i=0; i < count; i++ )
 
319
    ap[i] = 0;
 
320
  a->nlimbs += count;
 
321
}
 
322
 
 
323
 
 
324
/*
 
325
 * Shift A by N bits to the left.
 
326
 */
 
327
void
 
328
gcry_mpi_lshift ( gcry_mpi_t x, gcry_mpi_t a, unsigned int n )
 
329
{
 
330
  unsigned int nlimbs = (n/BITS_PER_MPI_LIMB);
 
331
  unsigned int nbits = (n%BITS_PER_MPI_LIMB);
 
332
 
 
333
  if (x == a && !n)
 
334
    return;  /* In-place shift with an amount of zero.  */
 
335
 
 
336
  if ( x != a )
 
337
    {
 
338
      /* Copy A to X.  */
 
339
      unsigned int alimbs = a->nlimbs;
 
340
      int asign  = a->sign;
 
341
      mpi_ptr_t xp, ap;
 
342
 
 
343
      RESIZE_IF_NEEDED (x, alimbs+nlimbs+1);
 
344
      xp = x->d;
 
345
      ap = a->d;
 
346
      MPN_COPY (xp, ap, alimbs);
 
347
      x->nlimbs = alimbs;
 
348
      x->flags = a->flags;
 
349
      x->sign = asign;
 
350
    }
 
351
 
 
352
  if (nlimbs && !nbits)
 
353
    {
 
354
      /* Shift a full number of limbs.  */
 
355
      _gcry_mpi_lshift_limbs (x, nlimbs);
 
356
    }
 
357
  else if (n)
 
358
    {
 
359
      /* We use a very dump approach: Shift left by the number of
 
360
         limbs plus one and than fix it up by an rshift.  */
 
361
      _gcry_mpi_lshift_limbs (x, nlimbs+1);
 
362
      gcry_mpi_rshift (x, x, BITS_PER_MPI_LIMB - nbits);
 
363
    }
 
364
 
 
365
  MPN_NORMALIZE (x->d, x->nlimbs);
 
366
}