Coverage Report

Created: 2023-02-22 06:39

/src/gmp-6.2.1/mpn/set_str.c
Line
Count
Source (jump to first uncovered line)
1
/* mpn_set_str (mp_ptr res_ptr, const char *str, size_t str_len, int base) --
2
   Convert a STR_LEN long base BASE byte string pointed to by STR to a limb
3
   vector pointed to by RES_PTR.  Return the number of limbs in RES_PTR.
4
5
   Contributed to the GNU project by Torbjorn Granlund.
6
7
   THE FUNCTIONS IN THIS FILE, EXCEPT mpn_set_str, ARE INTERNAL WITH MUTABLE
8
   INTERFACES.  IT IS ONLY SAFE TO REACH THEM THROUGH DOCUMENTED INTERFACES.
9
   IN FACT, IT IS ALMOST GUARANTEED THAT THEY WILL CHANGE OR DISAPPEAR IN A
10
   FUTURE GNU MP RELEASE.
11
12
Copyright 1991-2017 Free Software Foundation, Inc.
13
14
This file is part of the GNU MP Library.
15
16
The GNU MP Library is free software; you can redistribute it and/or modify
17
it under the terms of either:
18
19
  * the GNU Lesser General Public License as published by the Free
20
    Software Foundation; either version 3 of the License, or (at your
21
    option) any later version.
22
23
or
24
25
  * the GNU General Public License as published by the Free Software
26
    Foundation; either version 2 of the License, or (at your option) any
27
    later version.
28
29
or both in parallel, as here.
30
31
The GNU MP Library is distributed in the hope that it will be useful, but
32
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
33
or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
34
for more details.
35
36
You should have received copies of the GNU General Public License and the
37
GNU Lesser General Public License along with the GNU MP Library.  If not,
38
see https://www.gnu.org/licenses/.  */
39
40
41
/* TODO:
42
43
      Perhaps do not compute the highest power?
44
      Instead, multiply twice by the 2nd highest power:
45
46
         _______
47
        |_______|  hp
48
        |_______|  pow
49
       _______________
50
      |_______________|  final result
51
52
53
         _______
54
        |_______|  hp
55
      |___|  pow[-1]
56
     ___________
57
    |___________|  intermediate result
58
      |___|  pow[-1]
59
       _______________
60
      |_______________|  final result
61
62
      Generalizing that idea, perhaps we should make powtab contain successive
63
      cubes, not squares.
64
*/
65
66
#include "gmp-impl.h"
67
68
mp_size_t
69
mpn_set_str (mp_ptr rp, const unsigned char *str, size_t str_len, int base)
70
10.6k
{
71
10.6k
  if (POW2_P (base))
72
0
    {
73
      /* The base is a power of 2.  Read the input string from least to most
74
   significant character/digit.  */
75
76
0
      const unsigned char *s;
77
0
      int next_bitpos;
78
0
      mp_limb_t res_digit;
79
0
      mp_size_t size;
80
0
      int bits_per_indigit = mp_bases[base].big_base;
81
82
0
      size = 0;
83
0
      res_digit = 0;
84
0
      next_bitpos = 0;
85
86
0
      for (s = str + str_len - 1; s >= str; s--)
87
0
  {
88
0
    int inp_digit = *s;
89
90
0
    res_digit |= ((mp_limb_t) inp_digit << next_bitpos) & GMP_NUMB_MASK;
91
0
    next_bitpos += bits_per_indigit;
92
0
    if (next_bitpos >= GMP_NUMB_BITS)
93
0
      {
94
0
        rp[size++] = res_digit;
95
0
        next_bitpos -= GMP_NUMB_BITS;
96
0
        res_digit = inp_digit >> (bits_per_indigit - next_bitpos);
97
0
      }
98
0
  }
99
100
0
      if (res_digit != 0)
101
0
  rp[size++] = res_digit;
102
0
      return size;
103
0
    }
104
105
10.6k
  if (BELOW_THRESHOLD (str_len, SET_STR_PRECOMPUTE_THRESHOLD))
106
8.83k
    return mpn_bc_set_str (rp, str, str_len, base);
107
1.83k
  else
108
1.83k
    {
109
1.83k
      mp_ptr powtab_mem, tp;
110
1.83k
      powers_t powtab[GMP_LIMB_BITS];
111
1.83k
      int chars_per_limb;
112
1.83k
      powers_t *pt;
113
1.83k
      size_t n_pows;
114
1.83k
      mp_size_t size;
115
1.83k
      mp_size_t un;
116
1.83k
      TMP_DECL;
117
118
1.83k
      TMP_MARK;
119
120
1.83k
      chars_per_limb = mp_bases[base].chars_per_limb;
121
122
1.83k
      un = str_len / chars_per_limb + 1; /* FIXME: scalar integer division */
123
124
      /* Allocate one large block for the powers of big_base.  */
125
1.83k
      powtab_mem = TMP_BALLOC_LIMBS (mpn_str_powtab_alloc (un));
126
127
1.83k
      n_pows = mpn_compute_powtab (powtab, powtab_mem, un, base);
128
1.83k
      pt = powtab + n_pows;
129
130
1.83k
      tp = TMP_BALLOC_LIMBS (mpn_dc_set_str_itch (un));
131
1.83k
      size = mpn_dc_set_str (rp, str, str_len, pt, tp);
132
133
1.83k
      TMP_FREE;
134
1.83k
      return size;
135
1.83k
    }
136
10.6k
}
137
138
mp_size_t
139
mpn_dc_set_str (mp_ptr rp, const unsigned char *str, size_t str_len,
140
    const powers_t *powtab, mp_ptr tp)
141
28.4k
{
142
28.4k
  size_t len_lo, len_hi;
143
28.4k
  mp_limb_t cy;
144
28.4k
  mp_size_t ln, hn, n, sn;
145
146
28.4k
  len_lo = powtab->digits_in_base;
147
148
28.4k
  if (str_len <= len_lo)
149
0
    {
150
0
      if (BELOW_THRESHOLD (str_len, SET_STR_DC_THRESHOLD))
151
0
  return mpn_bc_set_str (rp, str, str_len, powtab->base);
152
0
      else
153
0
  return mpn_dc_set_str (rp, str, str_len, powtab - 1, tp);
154
0
    }
155
156
28.4k
  len_hi = str_len - len_lo;
157
28.4k
  ASSERT (len_lo >= len_hi);
158
159
28.4k
  if (BELOW_THRESHOLD (len_hi, SET_STR_DC_THRESHOLD))
160
16.2k
    hn = mpn_bc_set_str (tp, str, len_hi, powtab->base);
161
12.1k
  else
162
12.1k
    hn = mpn_dc_set_str (tp, str, len_hi, powtab - 1, rp);
163
164
28.4k
  sn = powtab->shift;
165
166
28.4k
  if (hn == 0)
167
4.92k
    {
168
      /* Zero +1 limb here, to avoid reading an allocated but uninitialised
169
   limb in mpn_incr_u below.  */
170
4.92k
      MPN_ZERO (rp, powtab->n + sn + 1);
171
4.92k
    }
172
23.5k
  else
173
23.5k
    {
174
23.5k
      if (powtab->n > hn)
175
4.05k
  mpn_mul (rp + sn, powtab->p, powtab->n, tp, hn);
176
19.4k
      else
177
19.4k
  mpn_mul (rp + sn, tp, hn, powtab->p, powtab->n);
178
23.5k
      MPN_ZERO (rp, sn);
179
23.5k
    }
180
181
28.4k
  str = str + str_len - len_lo;
182
28.4k
  if (BELOW_THRESHOLD (len_lo, SET_STR_DC_THRESHOLD))
183
14.0k
    ln = mpn_bc_set_str (tp, str, len_lo, powtab->base);
184
14.4k
  else
185
14.4k
    ln = mpn_dc_set_str (tp, str, len_lo, powtab - 1, tp + powtab->n + sn + 1);
186
187
28.4k
  if (ln != 0)
188
24.3k
    {
189
24.3k
      cy = mpn_add_n (rp, rp, tp, ln);
190
24.3k
      mpn_incr_u (rp + ln, cy);
191
24.3k
    }
192
28.4k
  n = hn + powtab->n + sn;
193
28.4k
  return n - (rp[n - 1] == 0);
194
28.4k
}
195
196
mp_size_t
197
mpn_bc_set_str (mp_ptr rp, const unsigned char *str, size_t str_len, int base)
198
39.1k
{
199
39.1k
  mp_size_t size;
200
39.1k
  size_t i;
201
39.1k
  long j;
202
39.1k
  mp_limb_t cy_limb;
203
204
39.1k
  mp_limb_t big_base;
205
39.1k
  int chars_per_limb;
206
39.1k
  mp_limb_t res_digit;
207
208
39.1k
  ASSERT (base >= 2);
209
39.1k
  ASSERT (base < numberof (mp_bases));
210
39.1k
  ASSERT (str_len >= 1);
211
212
39.1k
  big_base = mp_bases[base].big_base;
213
39.1k
  chars_per_limb = mp_bases[base].chars_per_limb;
214
215
39.1k
  size = 0;
216
383k
  for (i = chars_per_limb; i < str_len; i += chars_per_limb)
217
344k
    {
218
344k
      res_digit = *str++;
219
344k
      if (base == 10)
220
344k
  { /* This is a common case.
221
       Help the compiler to avoid multiplication.  */
222
6.55M
    for (j = MP_BASES_CHARS_PER_LIMB_10 - 1; j != 0; j--)
223
6.20M
      res_digit = res_digit * 10 + *str++;
224
344k
  }
225
0
      else
226
0
  {
227
0
    for (j = chars_per_limb - 1; j != 0; j--)
228
0
      res_digit = res_digit * base + *str++;
229
0
  }
230
231
344k
      if (size == 0)
232
125k
  {
233
125k
    if (res_digit != 0)
234
27.5k
      {
235
27.5k
        rp[0] = res_digit;
236
27.5k
        size = 1;
237
27.5k
      }
238
125k
  }
239
219k
      else
240
219k
  {
241
219k
#if HAVE_NATIVE_mpn_mul_1c
242
219k
    cy_limb = mpn_mul_1c (rp, rp, size, big_base, res_digit);
243
#else
244
    cy_limb = mpn_mul_1 (rp, rp, size, big_base);
245
    cy_limb += mpn_add_1 (rp, rp, size, res_digit);
246
#endif
247
219k
    if (cy_limb != 0)
248
219k
      rp[size++] = cy_limb;
249
219k
  }
250
344k
    }
251
252
39.1k
  big_base = base;
253
39.1k
  res_digit = *str++;
254
39.1k
  if (base == 10)
255
39.1k
    { /* This is a common case.
256
   Help the compiler to avoid multiplication.  */
257
615k
      for (j = str_len - (i - MP_BASES_CHARS_PER_LIMB_10) - 1; j > 0; j--)
258
576k
  {
259
576k
    res_digit = res_digit * 10 + *str++;
260
576k
    big_base *= 10;
261
576k
  }
262
39.1k
    }
263
0
  else
264
0
    {
265
0
      for (j = str_len - (i - chars_per_limb) - 1; j > 0; j--)
266
0
  {
267
0
    res_digit = res_digit * base + *str++;
268
0
    big_base *= base;
269
0
  }
270
0
    }
271
272
39.1k
  if (size == 0)
273
11.5k
    {
274
11.5k
      if (res_digit != 0)
275
2.53k
  {
276
2.53k
    rp[0] = res_digit;
277
2.53k
    size = 1;
278
2.53k
  }
279
11.5k
    }
280
27.5k
  else
281
27.5k
    {
282
27.5k
#if HAVE_NATIVE_mpn_mul_1c
283
27.5k
      cy_limb = mpn_mul_1c (rp, rp, size, big_base, res_digit);
284
#else
285
      cy_limb = mpn_mul_1 (rp, rp, size, big_base);
286
      cy_limb += mpn_add_1 (rp, rp, size, res_digit);
287
#endif
288
27.5k
      if (cy_limb != 0)
289
23.7k
  rp[size++] = cy_limb;
290
27.5k
    }
291
39.1k
  return size;
292
39.1k
}