Coverage Report

Created: 2019-04-21 11:35

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/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
5.33M
#define CHECK(res) (
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
7.17k
#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
8.73k
void GMPZAPI(neg)(mp_int rop, mp_int op) {
122
8.73k
  CHECK(mp_int_neg(op, rop));
123
8.73k
}
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
8.73k
void GMPZAPI(set)(mp_int rop, mp_int op) {
132
8.73k
  CHECK(mp_int_copy(op, rop));
133
8.73k
}
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
  CHECK(mp_int_init(r));
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
20.6k
void GMPZAPI(add_ui)(mp_int rop, mp_int op1, unsigned long op2) {
242
20.6k
  mpz_t tempz;
243
20.6k
  mp_int temp = &tempz;
244
20.6k
  CHECK(mp_int_init_uvalue(temp, op2));
245
20.6k
246
20.6k
  CHECK(mp_int_add(op1, temp, rop));
247
20.6k
248
20.6k
  mp_int_clear(temp);
249
20.6k
}
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 && mp_int_compare_zero(base) == 0) {
282
0
    CHECK(mp_int_set_value(rop, 1));
283
0
    return;
284
0
  }
285
0
286
0
  /* rop = base^exp */
287
0
  CHECK(mp_int_init_uvalue(temp, exp));
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
28.5k
void GMPZAPI(sub_ui)(mp_int rop, mp_int op1, unsigned long op2) {
294
28.5k
  mpz_t tempz;
295
28.5k
  mp_int temp = &tempz;
296
28.5k
  CHECK(mp_int_init_uvalue(temp, op2));
297
28.5k
298
28.5k
  CHECK(mp_int_sub(op1, temp, rop));
299
28.5k
300
28.5k
  mp_int_clear(temp);
301
28.5k
}
302
303
/*************************************************************************
304
 *
305
 * Functions with different behavior in corner cases
306
 *
307
 *************************************************************************/
308
309
/* gmp: mpz_gcd */
310
2.06M
void GMPZAPI(gcd)(mp_int rop, mp_int op1, mp_int op2) {
311
2.06M
  int op1_is_zero = mp_int_compare_zero(op1) == 0;
312
2.06M
  int op2_is_zero = mp_int_compare_zero(op2) == 0;
313
2.06M
314
2.06M
  if (op1_is_zero && 
op2_is_zero3
) {
315
0
    mp_int_zero(rop);
316
0
    return;
317
0
  }
318
2.06M
319
2.06M
  CHECK(mp_int_gcd(op1, op2, rop));
320
2.06M
}
321
322
/* gmp: mpz_get_str */
323
571
char* GMPZAPI(get_str)(char *str, int radix, mp_int op) {
324
571
  int i, r, len;
325
571
326
571
  /* Support negative radix like gmp */
327
571
  r = radix;
328
571
  if (r < 0)
329
0
    r = -r;
330
571
331
571
  /* Compute the length of the string needed to hold the int */
332
571
  len = mp_int_string_len(op, r);
333
571
  if (str == NULL) {
334
571
    str = malloc(len);
335
571
  }
336
571
337
571
  /* Convert to string using imath function */
338
571
  CHECK(mp_int_to_string(op, r, str, len));
339
571
340
571
  /* Change case to match gmp */
341
12.0k
  for (i = 0; i < len - 1; 
i++11.5k
)
342
11.5k
    if (radix < 0)
343
0
      str[i] = toupper(str[i]);
344
11.5k
    else
345
11.5k
      str[i] = tolower(str[i]);
346
571
  return str;
347
571
}
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 GMPZAPI(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 == NULL) {
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 < len; i++)
373
0
    if (radix < 0)
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) ? 0 : -1);
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 || resD != MP_OK)
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 >= 0; i--) {
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
  CHECK(res == MP_RANGE ? MP_OK : MP_RANGE);
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
  CHECK(res == MP_RANGE ? MP_OK : MP_RANGE);
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_SIGN(op) == MP_NEG)
487
0
    uout = 0 - uout;
488
0
489
0
  out = (long) uout;
490
0
  return out;
491
0
}
492
493
/* gmp: mpz_lcm */
494
250k
void GMPZAPI(lcm)(mp_int rop, mp_int op1, mp_int op2) {
495
250k
  int op1_is_zero = mp_int_compare_zero(op1) == 0;
496
250k
  int op2_is_zero = mp_int_compare_zero(op2) == 0;
497
250k
498
250k
  if (op1_is_zero || op2_is_zero) {
499
0
    mp_int_zero(rop);
500
0
    return;
501
0
  }
502
250k
503
250k
  CHECK(mp_int_lcm(op1, op2, rop));
504
250k
  CHECK(mp_int_abs(rop, rop));
505
250k
}
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
8.76k
void GMPZAPI(cdiv_q)(mp_int q, mp_int n, mp_int d) {
562
8.76k
  mpz_t rz;
563
8.76k
  mp_int r = &rz;
564
8.76k
  int qsign, rsign, nsign, dsign;
565
8.76k
  CHECK(mp_int_init(r));
566
8.76k
567
8.76k
  /* save signs before division because q can alias with n or d */
568
8.76k
  nsign = mp_int_compare_zero(n);
569
8.76k
  dsign = mp_int_compare_zero(d);
570
8.76k
571
8.76k
  /* truncating division */
572
8.76k
  CHECK(mp_int_div(n, d, q, r));
573
8.76k
574
8.76k
  /* see: [Note]Overview of division implementation */
575
8.76k
  qsign = mp_int_compare_zero(q);
576
8.76k
  rsign = mp_int_compare_zero(r);
577
8.76k
  if (qsign > 0) {    /* q > 0 */
578
976
    if (rsign != 0) { /* r != 0 */
579
436
      CHECK(mp_int_add_value(q, 1, q));
580
436
    }
581
976
  }
582
7.79k
  else if (qsign == 0) { /* q == 0 */
583
1.54k
    if (rsign != 0) {    /* r != 0 */
584
683
      if ((nsign > 0 && 
dsign > 0294
) ||
(389
nsign < 0389
&&
dsign < 0389
)) {
585
294
        CHECK(mp_int_set_value(q, 1));
586
294
      }
587
683
    }
588
1.54k
  }
589
8.76k
  mp_int_clear(r);
590
8.76k
}
591
592
/* gmp: mpz_fdiv_q */
593
152k
void GMPZAPI(fdiv_q)(mp_int q, mp_int n, mp_int d) {
594
152k
  mpz_t rz;
595
152k
  mp_int r = &rz;
596
152k
  int qsign, rsign, nsign, dsign;
597
152k
  CHECK(mp_int_init(r));
598
152k
599
152k
  /* save signs before division because q can alias with n or d */
600
152k
  nsign = mp_int_compare_zero(n);
601
152k
  dsign = mp_int_compare_zero(d);
602
152k
603
152k
  /* truncating division */
604
152k
  CHECK(mp_int_div(n, d, q, r));
605
152k
606
152k
  /* see: [Note]Overview of division implementation */
607
152k
  qsign = mp_int_compare_zero(q);
608
152k
  rsign = mp_int_compare_zero(r);
609
152k
  if (qsign < 0) {    /* q  < 0 */
610
37.9k
    if (rsign != 0) { /* r != 0 */
611
12.2k
      CHECK(mp_int_sub_value(q, 1, q));
612
12.2k
    }
613
37.9k
  }
614
114k
  else if (qsign == 0) { /* q == 0 */
615
13.1k
    if (rsign != 0) {    /* r != 0 */
616
5.66k
      if ((nsign < 0 && 
dsign > 01.67k
) ||
(3.99k
nsign > 03.99k
&&
dsign < 03.99k
)) {
617
1.67k
        CHECK(mp_int_set_value(q, -1));
618
1.67k
      }
619
5.66k
    }
620
13.1k
  }
621
152k
  mp_int_clear(r);
622
152k
}
623
624
/* gmp: mpz_fdiv_r */
625
2.19k
void GMPZAPI(fdiv_r)(mp_int r, mp_int n, mp_int d) {
626
2.19k
  mpz_t qz;
627
2.19k
  mpz_t tempz;
628
2.19k
  mpz_t orig_dz;
629
2.19k
  mpz_t orig_nz;
630
2.19k
  mp_int q = &qz;
631
2.19k
  mp_int temp = &tempz;
632
2.19k
  mp_int orig_d = &orig_dz;
633
2.19k
  mp_int orig_n = &orig_nz;
634
2.19k
  CHECK(mp_int_init(q));
635
2.19k
  CHECK(mp_int_init(temp));
636
2.19k
  /* Make a copy of n in case n and d in case they overlap with q */
637
2.19k
  CHECK(mp_int_init_copy(orig_d, d));
638
2.19k
  CHECK(mp_int_init_copy(orig_n, n));
639
2.19k
640
2.19k
  /* floor division */
641
2.19k
  GMPZAPI(fdiv_q)(q, n, d);
642
2.19k
643
2.19k
  /* see: [Note]Overview of division implementation */
644
2.19k
  /* n = q * d + r  ==>  r = n - q * d */
645
2.19k
  mp_int_mul(q, orig_d, temp);
646
2.19k
  mp_int_sub(orig_n, temp, r);
647
2.19k
648
2.19k
  mp_int_clear(q);
649
2.19k
  mp_int_clear(temp);
650
2.19k
  mp_int_clear(orig_d);
651
2.19k
  mp_int_clear(orig_n);
652
2.19k
}
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
899
void* GMPZAPI(export)(void *rop, size_t *countp, int order, size_t size, int endian, size_t nails, mp_int op) {
688
899
  int i, j;
689
899
  int num_used_bytes;
690
899
  size_t num_words, num_missing_bytes;
691
899
  ssize_t word_offset;
692
899
  unsigned char* dst;
693
899
  mp_digit* src;
694
899
  int src_bits;
695
899
696
899
  /* We do not have a complete implementation. Assert to ensure our
697
899
   * restrictions are in place. */
698
899
  assert(nails  == 0 && "Do not support non-full words");
699
899
  assert(endian == 1 || endian == 0 || endian == -1);
700
899
  assert(order == 1 || order == -1);
701
899
702
899
  /* Test for zero */
703
899
  if (mp_int_compare_zero(op) == 0) {
704
295
    if (countp)
705
0
      *countp = 0;
706
295
    return rop;
707
295
  }
708
604
709
604
  /* Calculate how many words we need */
710
604
  num_used_bytes  = mp_int_unsigned_len(op);
711
604
  num_words       = (num_used_bytes + (size-1)) / size; /* ceil division */
712
604
  assert(num_used_bytes > 0);
713
604
714
604
  /* Check to see if we will have missing bytes in the last word.
715
604
716
604
     Missing bytes can only occur when the size of words we output is
717
604
     greater than the size of words used internally by imath. The number of
718
604
     missing bytes is the number of bytes needed to fill out the last word. If
719
604
     this number is greater than the size of a single mp_digit, then we need to
720
604
     pad the word with extra zeros. Otherwise, the missing bytes can be filled
721
604
     directly from the zeros in the last digit in the number.
722
604
   */
723
604
  num_missing_bytes   = (size * num_words) - num_used_bytes;
724
604
  assert(num_missing_bytes < size);
725
604
726
604
  /* Allocate space for the result if needed */
727
604
  if (rop == NULL) {
728
0
    rop = malloc(num_words * size);
729
0
  }
730
604
731
604
  if (endian == 0) {
732
604
    endian = HOST_ENDIAN;
733
604
  }
734
604
735
604
  /* Initialize dst and src pointers */
736
604
  dst = (unsigned char *) rop + (order >= 0 ? 
(num_words-1) * size0
: 0) + (endian >= 0 ?
size-10
: 0);
737
604
  src = MP_DIGITS(op);
738
604
  src_bits = MP_DIGIT_BIT;
739
604
740
604
  word_offset = (endian >= 0 ? 
size0
: -size) + (order < 0 ? size :
-size0
);
741
604
742
1.20k
  for (i = 0; i < num_words; 
i++604
) {
743
1.42k
    for (j = 0; j < size && 
i * size + j < num_used_bytes1.40k
;
j++819
) {
744
819
      if (src_bits == 0) {
745
16
        ++src;
746
16
        src_bits = MP_DIGIT_BIT;
747
16
      }
748
819
      *dst = (*src >> (MP_DIGIT_BIT - src_bits)) & 0xFF;
749
819
      src_bits -= 8;
750
819
      dst -= endian;
751
819
    }
752
4.61k
    for (; j < size; 
j++4.01k
) {
753
4.01k
      *dst = 0;
754
4.01k
      dst -= endian;
755
4.01k
    }
756
604
    dst += word_offset;
757
604
  }
758
604
759
604
  if (countp)
760
0
    *countp = num_words;
761
604
  return rop;
762
604
}
763
764
/* gmp: mpz_import */
765
6.57k
void GMPZAPI(import)(mp_int rop, size_t count, int order, size_t size, int endian, size_t nails, const void* op) {
766
6.57k
  mpz_t tmpz;
767
6.57k
  mp_int tmp = &tmpz;
768
6.57k
  size_t total_size;
769
6.57k
  size_t num_digits;
770
6.57k
  ssize_t word_offset;
771
6.57k
  const unsigned char *src;
772
6.57k
  mp_digit *dst;
773
6.57k
  int dst_bits;
774
6.57k
  int i, j;
775
6.57k
  if (count == 0 || op == NULL)
776
6.57k
    
return0
;
777
6.57k
778
6.57k
  /* We do not have a complete implementation. Assert to ensure our
779
6.57k
   * restrictions are in place. */
780
6.57k
  assert(nails  == 0 && "Do not support non-full words");
781
6.57k
  assert(endian == 1 || endian == 0 || endian == -1);
782
6.57k
  assert(order == 1 || order == -1);
783
6.57k
784
6.57k
  if (endian == 0) {
785
6.57k
    endian = HOST_ENDIAN;
786
6.57k
  }
787
6.57k
788
6.57k
  /* Compute number of needed digits by ceil division */
789
6.57k
  total_size = count * size;
790
6.57k
  num_digits = (total_size + sizeof(mp_digit) - 1) / sizeof(mp_digit);
791
6.57k
792
6.57k
  /* Init temporary */
793
6.57k
  mp_int_init_size(tmp, num_digits);
794
28.8k
  for (i = 0; i < num_digits; 
i++22.2k
)
795
22.2k
    tmp->digits[i] = 0;
796
6.57k
797
6.57k
  /* Copy bytes */
798
6.57k
  src = (const unsigned char *) op + (order >= 0 ? 
(count-1) * size0
: 0) + (endian >= 0 ?
size-10
: 0);
799
6.57k
  dst = MP_DIGITS(tmp);
800
6.57k
  dst_bits = 0;
801
6.57k
802
6.57k
  word_offset = (endian >= 0 ? 
size0
: -size) + (order < 0 ? size :
-size0
);
803
6.57k
804
17.7k
  for (i = 0; i < count; 
i++11.1k
) {
805
100k
    for (j = 0; j < size; 
j++89.1k
) {
806
89.1k
      if (dst_bits == MP_DIGIT_BIT) {
807
15.7k
        ++dst;
808
15.7k
        dst_bits = 0;
809
15.7k
      }
810
89.1k
      *dst |= ((mp_digit)*src) << dst_bits;
811
89.1k
      dst_bits += 8;
812
89.1k
      src -= endian;
813
89.1k
    }
814
11.1k
    src += word_offset;
815
11.1k
  }
816
6.57k
817
6.57k
  MP_USED(tmp) = num_digits;
818
6.57k
819
6.57k
  /* Remove leading zeros from number */
820
6.57k
  {
821
6.57k
    mp_size uz_   = MP_USED(tmp);
822
6.57k
    mp_digit *dz_ = MP_DIGITS(tmp) + uz_ -1;
823
21.8k
    while (uz_ > 1 && 
(*dz_-- == 0)15.5k
)
824
15.2k
      --uz_;
825
6.57k
    MP_USED(tmp) = uz_;
826
6.57k
  }
827
6.57k
828
6.57k
  /* Copy to destination */
829
6.57k
  mp_int_copy(tmp, rop);
830
6.57k
  mp_int_clear(tmp);
831
6.57k
}
832
833
/* gmp: mpz_sizeinbase */
834
22
size_t GMPZAPI(sizeinbase)(mp_int op, int base) {
835
22
  mp_result res;
836
22
  size_t size;
837
22
838
22
  /* If op == 0, return 1 */
839
22
  if (mp_int_compare_zero(op) == 0)
840
0
    return 1;
841
22
842
22
  /* Compute string length in base */
843
22
  res = mp_int_string_len(op, base);
844
22
  CHECK((res > 0) == MP_OK);
845
22
846
22
  /* Now adjust the final size by getting rid of string artifacts */
847
22
  size = res;
848
22
849
22
  /* subtract one for the null terminator */
850
22
  size -= 1;
851
22
852
22
  /* subtract one for the negative sign */
853
22
  if (mp_int_compare_zero(op) < 0)
854
7
    size -= 1;
855
22
856
22
  return size;
857
22
}