gcc/testsuite/gcc.c-torture/execute/920501-2.c

   1 void abort (void);
   2 void exit (int);
   3
   4 unsigned long
   5 gcd_ll (unsigned long long x, unsigned long long y)
   6 {
   7   for (;;)
   8     {
   9       if (y == 0)
  10         return (unsigned long) x;
  11       x = x % y;
  12       if (x == 0)
  13         return (unsigned long) y;
  14       y = y % x;
  15     }
  16 }
  17
  18 unsigned long long
  19 powmod_ll (unsigned long long b, unsigned e, unsigned long long m)
  20 {
  21   unsigned t;
  22   unsigned long long pow;
  23   int i;
  24
  25   if (e == 0)
  26     return 1;
  27
  28   /* Find the most significant bit in E.  */
  29   t = e;
  30   for (i = 0; t != 0; i++)
  31     t >>= 1;
  32
  33   /* The most sign bit in E is handled outside of the loop, by beginning
  34      with B in POW, and decrementing I.  */
  35   pow = b;
  36   i -= 2;
  37
  38   for (; i >= 0; i--)
  39     {
  40       pow = pow * pow % m;
  41       if ((1 << i) & e)
  42         pow = pow * b % m;
  43     }
  44
  45   return pow;
  46 }
  47
  48 unsigned long factab[10];
  49
  50 void
  51 facts (t, a_int, x0, p)
  52      unsigned long long t;
  53      int a_int;
  54      int x0;
  55      unsigned p;
  56 {
  57   unsigned long *xp = factab;
  58   unsigned long long x, y;
  59   unsigned long q = 1;
  60   unsigned long long a = a_int;
  61   int i;
  62   unsigned long d;
  63   int j = 1;
  64   unsigned long tmp;
  65   int jj = 0;
  66
  67   x = x0;
  68   y = x0;
  69
  70   for (i = 1; i < 10000; i++)
  71     {
  72       x = powmod_ll (x, p, t) + a;
  73       y = powmod_ll (y, p, t) + a;
  74       y = powmod_ll (y, p, t) + a;
  75
  76       if (x > y)
  77         tmp = x - y;
  78       else
  79         tmp = y - x;
  80       q = (unsigned long long) q * tmp % t;
  81
  82       if (i == j)
  83         {
  84           jj += 1;
  85           j += jj;
  86           d = gcd_ll (q, t);
  87           if (d != 1)
  88             {
  89               *xp++ = d;
  90               t /= d;
  91               if (t == 1)
  92                 {
  93                   return;
  94                   *xp = 0;
  95                 }
  96             }
  97         }
  98     }
  99 }
 100
 101 int
 102 main (void)
 103 {
 104   unsigned long long t;
 105   unsigned x0, a;
 106   unsigned p;
 107
 108   p = 27;
 109   t = (1ULL << p) - 1;
 110
 111   a = -1;
 112   x0 = 3;
 113
 114   facts (t, a, x0, p);
 115   if (factab[0] != 7 || factab[1] != 73 || factab[2] != 262657)
 116     abort();
 117   exit (0);
 118 }