Coverage Report

Created: 2024-11-21 07:03

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