Coverage Report

Created: 2017-08-21 19:50

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/polly/lib/External/isl/imath/gmp_compat.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
  Name:     gmp_compat.c
3
  Purpose:  Provide GMP compatiable routines for imath library
4
  Author:   David Peixotto
5
6
  Copyright (c) 2012 Qualcomm Innovation Center, Inc. All rights reserved.
7
8
  Permission is hereby granted, free of charge, to any person obtaining a copy
9
  of this software and associated documentation files (the "Software"), to deal
10
  in the Software without restriction, including without limitation the rights
11
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
12
  copies of the Software, and to permit persons to whom the Software is
13
  furnished to do so, subject to the following conditions:
14
15
  The above copyright notice and this permission notice shall be included in
16
  all copies or substantial portions of the Software.
17
18
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
21
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
22
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
23
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
24
  SOFTWARE.
25
 */
26
#include "gmp_compat.h"
27
#include <stdlib.h>
28
#include <assert.h>
29
#include <ctype.h>
30
#include <string.h>
31
#include <stdio.h>
32
33
#if defined(_MSC_VER)
34
#include <BaseTsd.h>
35
typedef SSIZE_T ssize_t;
36
#endif
37
38
#ifdef  NDEBUG
39
3.65M
#define CHECK(res) 
(3.65M
res0
)
40
#else
41
#define CHECK(res) assert(((res) == MP_OK) && "expected MP_OK")
42
#endif
43
44
/* *(signed char *)&endian_test will thus either be:
45
 *     0b00000001 =  1 on big-endian
46
 *     0b11111111 = -1 on little-endian */
47
static const uint16_t endian_test = 0x1FF;
48
20.7k
#define HOST_ENDIAN (*(signed char *)&endian_test)
49
50
/*************************************************************************
51
 *
52
 * Functions with direct translations
53
 *
54
 *************************************************************************/
55
/* gmp: mpq_clear */
56
0
void GMPQAPI(clear)(mp_rat x) {
57
0
  mp_rat_clear(x);
58
0
}
59
60
/* gmp: mpq_cmp */
61
0
int GMPQAPI(cmp)(mp_rat op1, mp_rat op2) {
62
0
  return mp_rat_compare(op1, op2);
63
0
}
64
65
/* gmp: mpq_init */
66
0
void GMPQAPI(init)(mp_rat x) {
67
0
  CHECK(mp_rat_init(x));
68
0
}
69
70
/* gmp: mpq_mul */
71
0
void GMPQAPI(mul)(mp_rat product, mp_rat multiplier, mp_rat multiplicand) {
72
0
  CHECK(mp_rat_mul(multiplier, multiplicand, product));
73
0
}
74
75
/* gmp: mpq_set*/
76
0
void GMPQAPI(set)(mp_rat rop, mp_rat op) {
77
0
  CHECK(mp_rat_copy(op, rop));
78
0
}
79
80
/* gmp: mpz_abs */
81
0
void GMPZAPI(abs)(mp_int rop, mp_int op) {
82
0
  CHECK(mp_int_abs(op, rop));
83
0
}
84
85
/* gmp: mpz_add */
86
0
void GMPZAPI(add)(mp_int rop, mp_int op1, mp_int op2) {
87
0
  CHECK(mp_int_add(op1, op2, rop));
88
0
}
89
90
/* gmp: mpz_clear */
91
0
void GMPZAPI(clear)(mp_int x) {
92
0
  mp_int_clear(x);
93
0
}
94
95
/* gmp: mpz_cmp_si */
96
0
int GMPZAPI(cmp_si)(mp_int op1, long op2) {
97
0
  return mp_int_compare_value(op1, op2);
98
0
}
99
100
/* gmp: mpz_cmpabs */
101
0
int GMPZAPI(cmpabs)(mp_int op1, mp_int op2) {
102
0
  return mp_int_compare_unsigned(op1, op2);
103
0
}
104
105
/* gmp: mpz_cmp */
106
0
int GMPZAPI(cmp)(mp_int op1, mp_int op2) {
107
0
  return mp_int_compare(op1, op2);
108
0
}
109
110
/* gmp: mpz_init */
111
0
void GMPZAPI(init)(mp_int x) {
112
0
  CHECK(mp_int_init(x));
113
0
}
114
115
/* gmp: mpz_mul */
116
0
void GMPZAPI(mul)(mp_int rop, mp_int op1, mp_int op2) {
117
0
  CHECK(mp_int_mul(op1, op2, rop));
118
0
}
119
120
/* gmp: mpz_neg */
121
42.7k
void GMPZAPI(neg)(mp_int rop, mp_int op) {
122
42.7k
  CHECK(mp_int_neg(op, rop));
123
42.7k
}
124
125
/* gmp: mpz_set_si */
126
0
void GMPZAPI(set_si)(mp_int rop, long op) {
127
0
  CHECK(mp_int_set_value(rop, op));
128
0
}
129
130
/* gmp: mpz_set */
131
42.7k
void GMPZAPI(set)(mp_int rop, mp_int op) {
132
42.7k
  CHECK(mp_int_copy(op, rop));
133
42.7k
}
134
135
/* gmp: mpz_sub */
136
0
void GMPZAPI(sub)(mp_int rop, mp_int op1, mp_int op2) {
137
0
  CHECK(mp_int_sub(op1, op2, rop));
138
0
}
139
140
/* gmp: mpz_swap */
141
0
void GMPZAPI(swap)(mp_int rop1, mp_int rop2) {
142
0
  mp_int_swap(rop1, rop2);
143
0
}
144
145
/* gmp: mpq_sgn */
146
0
int GMPQAPI(sgn)(mp_rat op) {
147
0
  return mp_rat_compare_zero(op);
148
0
}
149
150
/* gmp: mpz_sgn */
151
0
int GMPZAPI(sgn)(mp_int op) {
152
0
  return mp_int_compare_zero(op);
153
0
}
154
155
/* gmp: mpq_set_ui */
156
0
void GMPQAPI(set_ui)(mp_rat rop, unsigned long op1, unsigned long op2) {
157
0
  CHECK(mp_rat_set_uvalue(rop, op1, op2));
158
0
}
159
160
/* gmp: mpz_set_ui */
161
0
void GMPZAPI(set_ui)(mp_int rop, unsigned long op) {
162
0
  CHECK(mp_int_set_uvalue(rop, op));
163
0
}
164
165
/* gmp: mpq_den_ref */
166
0
mp_int GMPQAPI(denref)(mp_rat op) {
167
0
  return mp_rat_denom_ref(op);
168
0
}
169
170
/* gmp: mpq_num_ref */
171
0
mp_int GMPQAPI(numref)(mp_rat op) {
172
0
  return mp_rat_numer_ref(op);
173
0
}
174
175
/* gmp: mpq_canonicalize */
176
0
void GMPQAPI(canonicalize)(mp_rat op) {
177
0
  CHECK(mp_rat_reduce(op));
178
0
}
179
180
/*************************************************************************
181
 *
182
 * Functions that can be implemented as a combination of imath functions
183
 *
184
 *************************************************************************/
185
/* gmp: mpz_addmul */
186
/* gmp: rop = rop + (op1 * op2) */
187
0
void GMPZAPI(addmul)(mp_int rop, mp_int op1, mp_int op2) {
188
0
  mpz_t tempz;
189
0
  mp_int temp = &tempz;
190
0
  mp_int_init(temp);
191
0
192
0
  CHECK(mp_int_mul(op1, op2, temp));
193
0
  CHECK(mp_int_add(rop, temp, rop));
194
0
  mp_int_clear(temp);
195
0
}
196
197
/* gmp: mpz_divexact */
198
/* gmp: only produces correct results when d divides n */
199
0
void GMPZAPI(divexact)(mp_int q, mp_int n, mp_int d) {
200
0
  CHECK(mp_int_div(n, d, q, NULL));
201
0
}
202
203
/* gmp: mpz_divisible_p */
204
/* gmp: return 1 if d divides n, 0 otherwise */
205
/* gmp: 0 is considered to divide only 0 */
206
0
int GMPZAPI(divisible_p)(mp_int n, mp_int d) {
207
0
  /* variables to hold remainder */
208
0
  mpz_t rz;
209
0
  mp_int r = &rz;
210
0
  int r_is_zero;
211
0
212
0
  /* check for d = 0 */
213
0
  int n_is_zero = mp_int_compare_zero(n) == 0;
214
0
  int d_is_zero = mp_int_compare_zero(d) == 0;
215
0
  if (d_is_zero)
216
0
    return n_is_zero;
217
0
218
0
  /* return true if remainder is 0 */
219
0
  
CHECK0
(mp_int_init(r));0
220
0
  CHECK(mp_int_div(n, d, NULL, r));
221
0
  r_is_zero = mp_int_compare_zero(r) == 0;
222
0
  mp_int_clear(r);
223
0
224
0
  return r_is_zero;
225
0
}
226
227
/* gmp: mpz_submul */
228
/* gmp: rop = rop - (op1 * op2) */
229
0
void GMPZAPI(submul)(mp_int rop, mp_int op1, mp_int op2) {
230
0
  mpz_t tempz;
231
0
  mp_int temp = &tempz;
232
0
  mp_int_init(temp);
233
0
234
0
  CHECK(mp_int_mul(op1, op2, temp));
235
0
  CHECK(mp_int_sub(rop, temp, rop));
236
0
237
0
  mp_int_clear(temp);
238
0
}
239
240
/* gmp: mpz_add_ui */
241
68.7k
void GMPZAPI(add_ui)(mp_int rop, mp_int op1, unsigned long op2) {
242
68.7k
  mpz_t tempz;
243
68.7k
  mp_int temp = &tempz;
244
68.7k
  CHECK(mp_int_init_uvalue(temp, op2));
245
68.7k
246
68.7k
  CHECK(mp_int_add(op1, temp, rop));
247
68.7k
248
68.7k
  mp_int_clear(temp);
249
68.7k
}
250
251
/* gmp: mpz_divexact_ui */
252
/* gmp: only produces correct results when d divides n */
253
0
void GMPZAPI(divexact_ui)(mp_int q, mp_int n, unsigned long d) {
254
0
  mpz_t tempz;
255
0
  mp_int temp = &tempz;
256
0
  CHECK(mp_int_init_uvalue(temp, d));
257
0
258
0
  CHECK(mp_int_div(n, temp, q, NULL));
259
0
260
0
  mp_int_clear(temp);
261
0
}
262
263
/* gmp: mpz_mul_ui */
264
0
void GMPZAPI(mul_ui)(mp_int rop, mp_int op1, unsigned long op2) {
265
0
  mpz_t tempz;
266
0
  mp_int temp = &tempz;
267
0
  CHECK(mp_int_init_uvalue(temp, op2));
268
0
269
0
  CHECK(mp_int_mul(op1, temp, rop));
270
0
271
0
  mp_int_clear(temp);
272
0
}
273
274
/* gmp: mpz_pow_ui */
275
/* gmp: 0^0 = 1 */
276
0
void GMPZAPI(pow_ui)(mp_int rop, mp_int base, unsigned long exp) {
277
0
  mpz_t tempz;
278
0
  mp_int temp = &tempz;
279
0
280
0
  /* check for 0^0 */
281
0
  if (
exp == 0 && 0
mp_int_compare_zero(base) == 00
)
{0
282
0
    CHECK(mp_int_set_value(rop, 1));
283
0
    return;
284
0
  }
285
0
286
0
  /* rop = base^exp */
287
0
  
CHECK0
(mp_int_init_uvalue(temp, exp));0
288
0
  CHECK(mp_int_expt_full(base, temp, rop));
289
0
  mp_int_clear(temp);
290
0
}
291
292
/* gmp: mpz_sub_ui */
293
96.8k
void GMPZAPI(sub_ui)(mp_int rop, mp_int op1, unsigned long op2) {
294
96.8k
  mpz_t tempz;
295
96.8k
  mp_int temp = &tempz;
296
96.8k
  CHECK(mp_int_init_uvalue(temp, op2));
297
96.8k
298
96.8k
  CHECK(mp_int_sub(op1, temp, rop));
299
96.8k
300
96.8k
  mp_int_clear(temp);
301
96.8k
}
302
303
/*************************************************************************
304
 *
305
 * Functions with different behavior in corner cases
306
 *
307
 *************************************************************************/
308
309
/* gmp: mpz_gcd */
310
2.20M
void GMPZAPI(gcd)(mp_int rop, mp_int op1, mp_int op2) {
311
2.20M
  int op1_is_zero = mp_int_compare_zero(op1) == 0;
312
2.20M
  int op2_is_zero = mp_int_compare_zero(op2) == 0;
313
2.20M
314
2.20M
  if (
op1_is_zero && 2.20M
op2_is_zero21
)
{0
315
0
    mp_int_zero(rop);
316
0
    return;
317
2.20M
  }
318
2.20M
319
2.20M
  
CHECK2.20M
(mp_int_gcd(op1, op2, rop));2.20M
320
2.20M
}
321
322
/* gmp: mpz_get_str */
323
1.44k
char* GMPZAPI(get_str)(char *str, int radix, mp_int op) {
324
1.44k
  int i, r, len;
325
1.44k
326
1.44k
  /* Support negative radix like gmp */
327
1.44k
  r = radix;
328
1.44k
  if (r < 0)
329
0
    r = -r;
330
1.44k
331
1.44k
  /* Compute the length of the string needed to hold the int */
332
1.44k
  len = mp_int_string_len(op, r);
333
1.44k
  if (
str == NULL1.44k
)
{1.44k
334
1.44k
    str = malloc(len);
335
1.44k
  }
336
1.44k
337
1.44k
  /* Convert to string using imath function */
338
1.44k
  CHECK(mp_int_to_string(op, r, str, len));
339
1.44k
340
1.44k
  /* Change case to match gmp */
341
28.9k
  for (i = 0; 
i < len - 128.9k
;
i++27.4k
)
342
27.4k
    
if (27.4k
radix < 027.4k
)
343
0
      str[i] = toupper(str[i]);
344
27.4k
    else
345
27.4k
      str[i] = tolower(str[i]);
346
1.44k
  return str;
347
1.44k
}
348
349
/* gmp: mpq_get_str */
350
0
char* GMPQAPI(get_str)(char *str, int radix, mp_rat op) {
351
0
  int i, r, len;
352
0
353
0
  /* Only print numerator if it is a whole number */
354
0
  if (mp_int_compare_value(mp_rat_denom_ref(op), 1) == 0)
355
0
    
return 0
GMPZAPI0
(get_str)(str, radix, mp_rat_numer_ref(op));
356
0
357
0
  /* Support negative radix like gmp */
358
0
  r = radix;
359
0
  if (r < 0)
360
0
    r = -r;
361
0
362
0
  /* Compute the length of the string needed to hold the int */
363
0
  len = mp_rat_string_len(op, r);
364
0
  if (
str == NULL0
)
{0
365
0
    str = malloc(len);
366
0
  }
367
0
368
0
  /* Convert to string using imath function */
369
0
  CHECK(mp_rat_to_string(op, r, str, len));
370
0
371
0
  /* Change case to match gmp */
372
0
  for (i = 0; 
i < len0
;
i++0
)
373
0
    
if (0
radix < 00
)
374
0
      str[i] = toupper(str[i]);
375
0
    else
376
0
      str[i] = tolower(str[i]);
377
0
378
0
  return str;
379
0
}
380
381
/* gmp: mpz_set_str */
382
0
int GMPZAPI(set_str)(mp_int rop, char *str, int base) {
383
0
  mp_result res = mp_int_read_string(rop, base, str);
384
0
  return ((res == MP_OK) ? 
00
:
-10
);
385
0
}
386
387
/* gmp: mpq_set_str */
388
0
int GMPQAPI(set_str)(mp_rat rop, char *s, int base) {
389
0
  char *slash;
390
0
  char *str;
391
0
  mp_result resN;
392
0
  mp_result resD;
393
0
  int res = 0;
394
0
395
0
  /* Copy string to temporary storage so we can modify it below */
396
0
  str = malloc(strlen(s)+1);
397
0
  strcpy(str, s);
398
0
399
0
  /* Properly format the string as an int by terminating at the / */
400
0
  slash = strchr(str, '/');
401
0
  if (slash)
402
0
    *slash = '\0';
403
0
404
0
  /* Parse numerator */
405
0
  resN = mp_int_read_string(mp_rat_numer_ref(rop), base, str);
406
0
407
0
  /* Parse denomenator if given or set to 1 if not */
408
0
  if (slash)
409
0
    resD = mp_int_read_string(mp_rat_denom_ref(rop), base, slash+1);
410
0
  else
411
0
    resD = mp_int_set_uvalue(mp_rat_denom_ref(rop), 1);
412
0
413
0
  /* Return failure if either parse failed */
414
0
  if (
resN != MP_OK || 0
resD != MP_OK0
)
415
0
    res = -1;
416
0
417
0
  free(str);
418
0
  return res;
419
0
}
420
421
0
static unsigned long get_long_bits(mp_int op) {
422
0
  /* Deal with integer that does not fit into unsigned long. We want to grab
423
0
   * the least significant digits that will fit into the long.  Read the digits
424
0
   * into the long starting at the most significant digit that fits into a
425
0
   * long. The long is shifted over by MP_DIGIT_BIT before each digit is added.
426
0
   * The shift is decomposed into two steps to follow the patten used in the
427
0
   * rest of the imath library. The two step shift is used to accomedate
428
0
   * architectures that don't deal well with 32-bit shifts. */
429
0
  mp_size num_digits_in_long = sizeof(unsigned long) / sizeof(mp_digit);
430
0
  mp_digit *digits = MP_DIGITS(op);
431
0
  unsigned long out = 0;
432
0
  int i;
433
0
434
0
  for (i = num_digits_in_long - 1; 
i >= 00
;
i--0
)
{0
435
0
    out <<= (MP_DIGIT_BIT/2);
436
0
    out <<= (MP_DIGIT_BIT/2);
437
0
    out  |= digits[i];
438
0
  }
439
0
440
0
  return out;
441
0
}
442
443
/* gmp: mpz_get_ui */
444
0
unsigned long GMPZAPI(get_ui)(mp_int op) {
445
0
  unsigned long out;
446
0
447
0
  /* Try a standard conversion that fits into an unsigned long */
448
0
  mp_result res = mp_int_to_uint(op, &out);
449
0
  if (res == MP_OK)
450
0
    return out;
451
0
452
0
  /* Abort the try if we don't have a range error in the conversion.
453
0
   * The range error indicates that the value cannot fit into a long. */
454
0
  
CHECK0
(res == MP_RANGE ? MP_OK : MP_RANGE);0
455
0
  if (res != MP_RANGE)
456
0
    return 0;
457
0
458
0
  return get_long_bits(op);
459
0
}
460
461
/* gmp: mpz_get_si */
462
0
long GMPZAPI(get_si)(mp_int op) {
463
0
  long out;
464
0
  unsigned long uout;
465
0
  int long_msb;
466
0
467
0
  /* Try a standard conversion that fits into a long */
468
0
  mp_result res = mp_int_to_int(op, &out);
469
0
  if (res == MP_OK)
470
0
    return out;
471
0
472
0
  /* Abort the try if we don't have a range error in the conversion.
473
0
   * The range error indicates that the value cannot fit into a long. */
474
0
  
CHECK0
(res == MP_RANGE ? MP_OK : MP_RANGE);0
475
0
  if (res != MP_RANGE)
476
0
    return 0;
477
0
478
0
  /* get least significant bits into an unsigned long */
479
0
  uout = get_long_bits(op);
480
0
481
0
  /* clear the top bit */
482
0
  long_msb = (sizeof(unsigned long) * 8) - 1;
483
0
  uout &= (~(1UL << long_msb));
484
0
485
0
  /* convert to negative if needed based on sign of op */
486
0
  if (
MP_SIGN0
(op) == MP_NEG0
)
487
0
    uout = 0 - uout;
488
0
489
0
  out = (long) uout;
490
0
  return out;
491
0
}
492
493
/* gmp: mpz_lcm */
494
270k
void GMPZAPI(lcm)(mp_int rop, mp_int op1, mp_int op2) {
495
270k
  int op1_is_zero = mp_int_compare_zero(op1) == 0;
496
270k
  int op2_is_zero = mp_int_compare_zero(op2) == 0;
497
270k
498
270k
  if (
op1_is_zero || 270k
op2_is_zero270k
)
{0
499
0
    mp_int_zero(rop);
500
0
    return;
501
270k
  }
502
270k
503
270k
  
CHECK270k
(mp_int_lcm(op1, op2, rop));270k
504
270k
  CHECK(mp_int_abs(rop, rop));
505
270k
}
506
507
/* gmp: mpz_mul_2exp */
508
/* gmp: allow big values for op2 when op1 == 0 */
509
0
void GMPZAPI(mul_2exp)(mp_int rop, mp_int op1, unsigned long op2) {
510
0
  if (mp_int_compare_zero(op1) == 0)
511
0
    mp_int_zero(rop);
512
0
  else
513
0
    CHECK(mp_int_mul_pow2(op1, op2, rop));
514
0
}
515
516
/*************************************************************************
517
 *
518
 * Functions needing expanded functionality
519
 *
520
 *************************************************************************/
521
/* [Note]Overview of division implementation
522
523
    All division operations (N / D) compute q and r such that
524
525
      N = q * D + r, with 0 <= abs(r) < abs(d)
526
527
    The q and r values are not uniquely specified by N and D. To specify which q
528
    and r values should be used, GMP implements three different rounding modes
529
    for integer division:
530
531
      ceiling  - round q twords +infinity, r has opposite sign as d
532
      floor    - round q twords -infinity, r has same sign as d
533
      truncate - round q twords zero,      r has same sign as n
534
535
    The imath library only supports truncate as a rounding mode. We need to
536
    implement the other rounding modes in terms of truncating division. We first
537
    perform the division in trucate mode and then adjust q accordingly. Once we
538
    know q, we can easily compute the correct r according the the formula above
539
    by computing:
540
541
      r = N - q * D
542
543
    The main task is to compute q. We can compute the correct q from a trucated
544
    version as follows.
545
546
    For ceiling rounding mode, if q is less than 0 then the truncated rounding
547
    mode is the same as the ceiling rounding mode.  If q is greater than zero
548
    then we need to round q up by one because the truncated version was rounded
549
    down to zero. If q equals zero then check to see if the result of the
550
    divison is positive. A positive result needs to increment q to one.
551
552
    For floor rounding mode, if q is greater than 0 then the trucated rounding
553
    mode is the same as the floor rounding mode. If q is less than zero then we
554
    need to round q down by one because the trucated mode rounded q up by one
555
    twords zero. If q is zero then we need to check to see if the result of the
556
    division is negative. A negative result needs to decrement q to negative
557
    one.
558
 */
559
560
/* gmp: mpz_cdiv_q */
561
31.0k
void GMPZAPI(cdiv_q)(mp_int q, mp_int n, mp_int d) {
562
31.0k
  mpz_t rz;
563
31.0k
  mp_int r = &rz;
564
31.0k
  int qsign, rsign, nsign, dsign;
565
31.0k
  CHECK(mp_int_init(r));
566
31.0k
567
31.0k
  /* save signs before division because q can alias with n or d */
568
31.0k
  nsign = mp_int_compare_zero(n);
569
31.0k
  dsign = mp_int_compare_zero(d);
570
31.0k
571
31.0k
  /* truncating division */
572
31.0k
  CHECK(mp_int_div(n, d, q, r));
573
31.0k
574
31.0k
  /* see: [Note]Overview of division implementation */
575
31.0k
  qsign = mp_int_compare_zero(q);
576
31.0k
  rsign = mp_int_compare_zero(r);
577
31.0k
  if (
qsign > 031.0k
)
{ /* q > 0 */2.91k
578
2.91k
    if (
rsign != 02.91k
)
{ /* r != 0 */1.26k
579
1.26k
      CHECK(mp_int_add_value(q, 1, q));
580
2.91k
    }
581
31.0k
  }
582
28.1k
  else 
if (28.1k
qsign == 028.1k
)
{ /* q == 0 */8.25k
583
8.25k
    if (
rsign != 08.25k
)
{ /* r != 0 */2.75k
584
2.75k
      if (
(nsign > 0 && 2.75k
dsign > 01.34k
) ||
(nsign < 0 && 1.41k
dsign < 01.41k
))
{1.34k
585
1.34k
        CHECK(mp_int_set_value(q, 1));
586
2.75k
      }
587
8.25k
    }
588
31.0k
  }
589
31.0k
  mp_int_clear(r);
590
31.0k
}
591
592
/* gmp: mpz_fdiv_q */
593
190k
void GMPZAPI(fdiv_q)(mp_int q, mp_int n, mp_int d) {
594
190k
  mpz_t rz;
595
190k
  mp_int r = &rz;
596
190k
  int qsign, rsign, nsign, dsign;
597
190k
  CHECK(mp_int_init(r));
598
190k
599
190k
  /* save signs before division because q can alias with n or d */
600
190k
  nsign = mp_int_compare_zero(n);
601
190k
  dsign = mp_int_compare_zero(d);
602
190k
603
190k
  /* truncating division */
604
190k
  CHECK(mp_int_div(n, d, q, r));
605
190k
606
190k
  /* see: [Note]Overview of division implementation */
607
190k
  qsign = mp_int_compare_zero(q);
608
190k
  rsign = mp_int_compare_zero(r);
609
190k
  if (
qsign < 0190k
)
{ /* q < 0 */41.1k
610
41.1k
    if (
rsign != 041.1k
)
{ /* r != 0 */14.1k
611
14.1k
      CHECK(mp_int_sub_value(q, 1, q));
612
41.1k
    }
613
190k
  }
614
149k
  else 
if (149k
qsign == 0149k
)
{ /* q == 0 */32.8k
615
32.8k
    if (
rsign != 032.8k
)
{ /* r != 0 */18.7k
616
18.7k
      if (
(nsign < 0 && 18.7k
dsign > 05.53k
) ||
(nsign > 0 && 13.1k
dsign < 013.1k
))
{5.53k
617
5.53k
        CHECK(mp_int_set_value(q, -1));
618
18.7k
      }
619
32.8k
    }
620
190k
  }
621
190k
  mp_int_clear(r);
622
190k
}
623
624
/* gmp: mpz_fdiv_r */
625
7.17k
void GMPZAPI(fdiv_r)(mp_int r, mp_int n, mp_int d) {
626
7.17k
  mpz_t qz;
627
7.17k
  mpz_t tempz;
628
7.17k
  mpz_t orig_dz;
629
7.17k
  mpz_t orig_nz;
630
7.17k
  mp_int q = &qz;
631
7.17k
  mp_int temp = &tempz;
632
7.17k
  mp_int orig_d = &orig_dz;
633
7.17k
  mp_int orig_n = &orig_nz;
634
7.17k
  CHECK(mp_int_init(q));
635
7.17k
  CHECK(mp_int_init(temp));
636
7.17k
  /* Make a copy of n in case n and d in case they overlap with q */
637
7.17k
  CHECK(mp_int_init_copy(orig_d, d));
638
7.17k
  CHECK(mp_int_init_copy(orig_n, n));
639
7.17k
640
7.17k
  /* floor division */
641
7.17k
  GMPZAPI(fdiv_q)(q, n, d);
642
7.17k
643
7.17k
  /* see: [Note]Overview of division implementation */
644
7.17k
  /* n = q * d + r  ==>  r = n - q * d */
645
7.17k
  mp_int_mul(q, orig_d, temp);
646
7.17k
  mp_int_sub(orig_n, temp, r);
647
7.17k
648
7.17k
  mp_int_clear(q);
649
7.17k
  mp_int_clear(temp);
650
7.17k
  mp_int_clear(orig_d);
651
7.17k
  mp_int_clear(orig_n);
652
7.17k
}
653
654
/* gmp: mpz_tdiv_q */
655
0
void GMPZAPI(tdiv_q)(mp_int q, mp_int n, mp_int d) {
656
0
  /* truncating division*/
657
0
  CHECK(mp_int_div(n, d, q, NULL));
658
0
}
659
660
/* gmp: mpz_fdiv_q_ui */
661
0
unsigned long GMPZAPI(fdiv_q_ui)(mp_int q, mp_int n, unsigned long d) {
662
0
  mpz_t tempz;
663
0
  mp_int temp = &tempz;
664
0
  mpz_t rz;
665
0
  mp_int r = &rz;
666
0
  mpz_t orig_nz;
667
0
  mp_int orig_n = &orig_nz;
668
0
  unsigned long rl;
669
0
  CHECK(mp_int_init_uvalue(temp, d));
670
0
  CHECK(mp_int_init(r));
671
0
  /* Make a copy of n in case n and q overlap */
672
0
  CHECK(mp_int_init_copy(orig_n, n));
673
0
674
0
  /* use floor division mode to compute q and r */
675
0
  GMPZAPI(fdiv_q)(q, n, temp);
676
0
  GMPZAPI(fdiv_r)(r, orig_n, temp);
677
0
  CHECK(mp_int_to_uint(r, &rl));
678
0
679
0
  mp_int_clear(temp);
680
0
  mp_int_clear(r);
681
0
  mp_int_clear(orig_n);
682
0
683
0
  return rl;
684
0
}
685
686
/* gmp: mpz_export */
687
2.63k
void* GMPZAPI(export)(void *rop, size_t *countp, int order, size_t size, int endian, size_t nails, mp_int op) {
688
2.63k
  int i, j;
689
2.63k
  int num_used_bytes;
690
2.63k
  size_t num_words, num_missing_bytes;
691
2.63k
  ssize_t word_offset;
692
2.63k
  unsigned char* dst;
693
2.63k
  mp_digit* src;
694
2.63k
  int src_bits;
695
2.63k
696
2.63k
  /* We do not have a complete implementation. Assert to ensure our
697
2.63k
   * restrictions are in place. */
698
2.63k
  assert(nails  == 0 && "Do not support non-full words");
699
2.63k
  assert(endian == 1 || endian == 0 || endian == -1);
700
2.63k
  assert(order == 1 || order == -1);
701
2.63k
702
2.63k
  /* Test for zero */
703
2.63k
  if (
mp_int_compare_zero(op) == 02.63k
)
{796
704
796
    if (countp)
705
0
      *countp = 0;
706
796
    return rop;
707
2.63k
  }
708
2.63k
709
2.63k
  /* Calculate how many words we need */
710
2.63k
  num_used_bytes  = mp_int_unsigned_len(op);
711
1.84k
  num_words       = (num_used_bytes + (size-1)) / size; /* ceil division */
712
1.84k
  assert(num_used_bytes > 0);
713
1.84k
714
1.84k
  /* Check to see if we will have missing bytes in the last word.
715
1.84k
716
1.84k
     Missing bytes can only occur when the size of words we output is
717
1.84k
     greater than the size of words used internally by imath. The number of
718
1.84k
     missing bytes is the number of bytes needed to fill out the last word. If
719
1.84k
     this number is greater than the size of a single mp_digit, then we need to
720
1.84k
     pad the word with extra zeros. Otherwise, the missing bytes can be filled
721
1.84k
     directly from the zeros in the last digit in the number.
722
1.84k
   */
723
1.84k
  num_missing_bytes   = (size * num_words) - num_used_bytes;
724
1.84k
  assert(num_missing_bytes < size);
725
1.84k
726
1.84k
  /* Allocate space for the result if needed */
727
1.84k
  if (
rop == NULL1.84k
)
{0
728
0
    rop = malloc(num_words * size);
729
1.84k
  }
730
1.84k
731
1.84k
  if (
endian == 01.84k
)
{1.84k
732
1.84k
    endian = HOST_ENDIAN;
733
1.84k
  }
734
1.84k
735
1.84k
  /* Initialize dst and src pointers */
736
1.84k
  dst = (unsigned char *) rop + (order >= 0 ? 
(num_words-1) * size0
:
01.84k
) + (endian >= 0 ?
size-10
:
01.84k
);
737
1.84k
  src = MP_DIGITS(op);
738
1.84k
  src_bits = MP_DIGIT_BIT;
739
1.84k
740
1.84k
  word_offset = (endian >= 0 ? 
size0
:
-size1.84k
) + (order < 0 ?
size1.84k
:
-size0
);
741
1.84k
742
3.71k
  for (i = 0; 
i < num_words3.71k
;
i++1.87k
)
{1.87k
743
4.70k
    for (j = 0; 
j < size && 4.70k
i * size + j < num_used_bytes4.61k
;
j++2.83k
)
{2.83k
744
2.83k
      if (
src_bits == 02.83k
)
{124
745
124
        ++src;
746
124
        src_bits = MP_DIGIT_BIT;
747
2.83k
      }
748
2.83k
      *dst = (*src >> (MP_DIGIT_BIT - src_bits)) & 0xFF;
749
2.83k
      src_bits -= 8;
750
2.83k
      dst -= endian;
751
2.83k
    }
752
14.0k
    for (; 
j < size14.0k
;
j++12.1k
)
{12.1k
753
12.1k
      *dst = 0;
754
12.1k
      dst -= endian;
755
12.1k
    }
756
1.87k
    dst += word_offset;
757
1.87k
  }
758
1.84k
759
1.84k
  if (countp)
760
0
    *countp = num_words;
761
2.63k
  return rop;
762
2.63k
}
763
764
/* gmp: mpz_import */
765
18.9k
void GMPZAPI(import)(mp_int rop, size_t count, int order, size_t size, int endian, size_t nails, const void* op) {
766
18.9k
  mpz_t tmpz;
767
18.9k
  mp_int tmp = &tmpz;
768
18.9k
  size_t total_size;
769
18.9k
  size_t num_digits;
770
18.9k
  ssize_t word_offset;
771
18.9k
  const unsigned char *src;
772
18.9k
  mp_digit *dst;
773
18.9k
  int dst_bits;
774
18.9k
  int i, j;
775
18.9k
  if (
count == 0 || 18.9k
op == NULL18.9k
)
776
0
    return;
777
18.9k
778
18.9k
  /* We do not have a complete implementation. Assert to ensure our
779
18.9k
   * restrictions are in place. */
780
18.9k
  assert(nails  == 0 && "Do not support non-full words");
781
18.9k
  assert(endian == 1 || endian == 0 || endian == -1);
782
18.9k
  assert(order == 1 || order == -1);
783
18.9k
784
18.9k
  if (
endian == 018.9k
)
{18.9k
785
18.9k
    endian = HOST_ENDIAN;
786
18.9k
  }
787
18.9k
788
18.9k
  /* Compute number of needed digits by ceil division */
789
18.9k
  total_size = count * size;
790
18.9k
  num_digits = (total_size + sizeof(mp_digit) - 1) / sizeof(mp_digit);
791
18.9k
792
18.9k
  /* Init temporary */
793
18.9k
  mp_int_init_size(tmp, num_digits);
794
81.5k
  for (i = 0; 
i < num_digits81.5k
;
i++62.6k
)
795
62.6k
    tmp->digits[i] = 0;
796
18.9k
797
18.9k
  /* Copy bytes */
798
18.9k
  src = (const unsigned char *) op + (order >= 0 ? 
(count-1) * size0
:
018.9k
) + (endian >= 0 ?
size-10
:
018.9k
);
799
18.9k
  dst = MP_DIGITS(tmp);
800
18.9k
  dst_bits = 0;
801
18.9k
802
18.9k
  word_offset = (endian >= 0 ? 
size0
:
-size18.9k
) + (order < 0 ?
size18.9k
:
-size0
);
803
18.9k
804
50.2k
  for (i = 0; 
i < count50.2k
;
i++31.3k
)
{31.3k
805
281k
    for (j = 0; 
j < size281k
;
j++250k
)
{250k
806
250k
      if (
dst_bits == 250k
MP_DIGIT_BIT250k
)
{43.6k
807
43.6k
        ++dst;
808
43.6k
        dst_bits = 0;
809
250k
      }
810
250k
      *dst |= ((mp_digit)*src) << dst_bits;
811
250k
      dst_bits += 8;
812
250k
      src -= endian;
813
250k
    }
814
31.3k
    src += word_offset;
815
31.3k
  }
816
18.9k
817
18.9k
  MP_USED(tmp) = num_digits;
818
18.9k
819
18.9k
  /* Remove leading zeros from number */
820
18.9k
  {
821
18.9k
    mp_size uz_   = MP_USED(tmp);
822
18.9k
    mp_digit *dz_ = MP_DIGITS(tmp) + uz_ -1;
823
61.4k
    while (
uz_ > 1 && 61.4k
(*dz_-- == 0)43.5k
)
824
42.5k
      --uz_;
825
18.9k
    MP_USED(tmp) = uz_;
826
18.9k
  }
827
18.9k
828
18.9k
  /* Copy to destination */
829
18.9k
  mp_int_copy(tmp, rop);
830
18.9k
  mp_int_clear(tmp);
831
18.9k
}
832
833
/* gmp: mpz_sizeinbase */
834
80
size_t GMPZAPI(sizeinbase)(mp_int op, int base) {
835
80
  mp_result res;
836
80
  size_t size;
837
80
838
80
  /* If op == 0, return 1 */
839
80
  if (mp_int_compare_zero(op) == 0)
840
0
    return 1;
841
80
842
80
  /* Compute string length in base */
843
80
  res = mp_int_string_len(op, base);
844
80
  CHECK((res > 0) == MP_OK);
845
80
846
80
  /* Now adjust the final size by getting rid of string artifacts */
847
80
  size = res;
848
80
849
80
  /* subtract one for the null terminator */
850
80
  size -= 1;
851
80
852
80
  /* subtract one for the negative sign */
853
80
  if (mp_int_compare_zero(op) < 0)
854
26
    size -= 1;
855
80
856
80
  return size;
857
80
}