Coverage Report

Created: 2024-11-21 06:47

/src/libgmp/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
344k
{
71
344k
  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
344k
  if (BELOW_THRESHOLD (str_len, SET_STR_PRECOMPUTE_THRESHOLD))
106
344k
    return mpn_bc_set_str (rp, str, str_len, base);
107
0
  else
108
0
    {
109
0
      mp_ptr powtab_mem, tp;
110
0
      powers_t powtab[GMP_LIMB_BITS];
111
0
      int chars_per_limb;
112
0
      mp_size_t size;
113
0
      mp_size_t un;
114
0
      TMP_DECL;
115
116
0
      TMP_MARK;
117
118
0
      chars_per_limb = mp_bases[base].chars_per_limb;
119
120
0
      un = str_len / chars_per_limb + 1; /* FIXME: scalar integer division */
121
122
      /* Allocate one large block for the powers of big_base.  */
123
0
      powtab_mem = TMP_BALLOC_LIMBS (mpn_str_powtab_alloc (un));
124
125
0
      size_t n_pows = mpn_compute_powtab (powtab, powtab_mem, un, base);
126
0
      powers_t *pt = powtab + n_pows;
127
128
0
      tp = TMP_BALLOC_LIMBS (mpn_dc_set_str_itch (un));
129
0
      size = mpn_dc_set_str (rp, str, str_len, pt, tp);
130
131
0
      TMP_FREE;
132
0
      return size;
133
0
    }
134
344k
}
135
136
mp_size_t
137
mpn_dc_set_str (mp_ptr rp, const unsigned char *str, size_t str_len,
138
    const powers_t *powtab, mp_ptr tp)
139
0
{
140
0
  size_t len_lo, len_hi;
141
0
  mp_limb_t cy;
142
0
  mp_size_t ln, hn, n, sn;
143
144
0
  len_lo = powtab->digits_in_base;
145
146
0
  if (str_len <= len_lo)
147
0
    {
148
0
      if (BELOW_THRESHOLD (str_len, SET_STR_DC_THRESHOLD))
149
0
  return mpn_bc_set_str (rp, str, str_len, powtab->base);
150
0
      else
151
0
  return mpn_dc_set_str (rp, str, str_len, powtab - 1, tp);
152
0
    }
153
154
0
  len_hi = str_len - len_lo;
155
0
  ASSERT (len_lo >= len_hi);
156
157
0
  if (BELOW_THRESHOLD (len_hi, SET_STR_DC_THRESHOLD))
158
0
    hn = mpn_bc_set_str (tp, str, len_hi, powtab->base);
159
0
  else
160
0
    hn = mpn_dc_set_str (tp, str, len_hi, powtab - 1, rp);
161
162
0
  sn = powtab->shift;
163
164
0
  if (hn == 0)
165
0
    {
166
      /* Zero +1 limb here, to avoid reading an allocated but uninitialised
167
   limb in mpn_incr_u below.  */
168
0
      MPN_ZERO (rp, powtab->n + sn + 1);
169
0
    }
170
0
  else
171
0
    {
172
0
      if (powtab->n > hn)
173
0
  mpn_mul (rp + sn, powtab->p, powtab->n, tp, hn);
174
0
      else
175
0
  mpn_mul (rp + sn, tp, hn, powtab->p, powtab->n);
176
0
      MPN_ZERO (rp, sn);
177
0
    }
178
179
0
  str = str + str_len - len_lo;
180
0
  if (BELOW_THRESHOLD (len_lo, SET_STR_DC_THRESHOLD))
181
0
    ln = mpn_bc_set_str (tp, str, len_lo, powtab->base);
182
0
  else
183
0
    ln = mpn_dc_set_str (tp, str, len_lo, powtab - 1, tp + powtab->n + sn + 1);
184
185
0
  if (ln != 0)
186
0
    {
187
0
      cy = mpn_add_n (rp, rp, tp, ln);
188
0
      mpn_incr_u (rp + ln, cy);
189
0
    }
190
0
  n = hn + powtab->n + sn;
191
0
  return n - (rp[n - 1] == 0);
192
0
}
193
194
mp_size_t
195
mpn_bc_set_str (mp_ptr rp, const unsigned char *str, size_t str_len, int base)
196
344k
{
197
344k
  mp_size_t size;
198
344k
  size_t i;
199
344k
  long j;
200
344k
  mp_limb_t cy_limb;
201
202
344k
  mp_limb_t big_base;
203
344k
  int chars_per_limb;
204
344k
  mp_limb_t res_digit;
205
206
344k
  ASSERT (base >= 2);
207
344k
  ASSERT (base < numberof (mp_bases));
208
344k
  ASSERT (str_len >= 1);
209
210
344k
  big_base = mp_bases[base].big_base;
211
344k
  chars_per_limb = mp_bases[base].chars_per_limb;
212
213
344k
  size = 0;
214
15.7M
  for (i = chars_per_limb; i < str_len; i += chars_per_limb)
215
15.3M
    {
216
15.3M
      res_digit = *str++;
217
15.3M
      if (base == 10)
218
15.3M
  { /* This is a common case.
219
       Help the compiler to avoid multiplication.  */
220
292M
    for (j = MP_BASES_CHARS_PER_LIMB_10 - 1; j != 0; j--)
221
276M
      res_digit = res_digit * 10 + *str++;
222
15.3M
  }
223
0
      else
224
0
  {
225
0
    for (j = chars_per_limb - 1; j != 0; j--)
226
0
      res_digit = res_digit * base + *str++;
227
0
  }
228
229
15.3M
      if (size == 0)
230
317k
  {
231
317k
    if (res_digit != 0)
232
317k
      {
233
317k
        rp[0] = res_digit;
234
317k
        size = 1;
235
317k
      }
236
317k
  }
237
15.0M
      else
238
15.0M
  {
239
15.0M
#if HAVE_NATIVE_mpn_mul_1c
240
15.0M
    cy_limb = mpn_mul_1c (rp, rp, size, big_base, res_digit);
241
#else
242
    cy_limb = mpn_mul_1 (rp, rp, size, big_base);
243
    cy_limb += mpn_add_1 (rp, rp, size, res_digit);
244
#endif
245
15.0M
    if (cy_limb != 0)
246
15.0M
      rp[size++] = cy_limb;
247
15.0M
  }
248
15.3M
    }
249
250
344k
  big_base = base;
251
344k
  res_digit = *str++;
252
344k
  if (base == 10)
253
344k
    { /* This is a common case.
254
   Help the compiler to avoid multiplication.  */
255
2.56M
      for (j = str_len - (i - MP_BASES_CHARS_PER_LIMB_10) - 1; j > 0; j--)
256
2.21M
  {
257
2.21M
    res_digit = res_digit * 10 + *str++;
258
2.21M
    big_base *= 10;
259
2.21M
  }
260
344k
    }
261
0
  else
262
0
    {
263
0
      for (j = str_len - (i - chars_per_limb) - 1; j > 0; j--)
264
0
  {
265
0
    res_digit = res_digit * base + *str++;
266
0
    big_base *= base;
267
0
  }
268
0
    }
269
270
344k
  if (size == 0)
271
27.4k
    {
272
27.4k
      if (res_digit != 0)
273
27.4k
  {
274
27.4k
    rp[0] = res_digit;
275
27.4k
    size = 1;
276
27.4k
  }
277
27.4k
    }
278
317k
  else
279
317k
    {
280
317k
#if HAVE_NATIVE_mpn_mul_1c
281
317k
      cy_limb = mpn_mul_1c (rp, rp, size, big_base, res_digit);
282
#else
283
      cy_limb = mpn_mul_1 (rp, rp, size, big_base);
284
      cy_limb += mpn_add_1 (rp, rp, size, res_digit);
285
#endif
286
317k
      if (cy_limb != 0)
287
85.3k
  rp[size++] = cy_limb;
288
317k
    }
289
344k
  return size;
290
344k
}