← Back to branch summary

~ubuntu-branches/ubuntu/intrepid/ecl/intrepid

« back to all changes in this revision

Viewing changes to src/gmp/mpn/generic/gcd_1.c

  • Committer: Bazaar Package Importer
  • Author(s): Peter Van Eynde
  • Date: 2006-05-17 02:46:26 UTC
  • Revision ID: james.westby@ubuntu.com-20060517024626-lljr08ftv9g9vefl
Tags: upstream-0.9h-20060510
Import upstream version 0.9h-20060510

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/gmp/mpn/generic/gcd_1.c
 
1
/* mpn_gcd_1 -- mpn and limb greatest common divisor.
 
2
 
 
3
Copyright 1994, 1996, 2000, 2001 Free Software Foundation, Inc.
 
4
 
 
5
This file is part of the GNU MP Library.
 
6
 
 
7
The GNU MP Library is free software; you can redistribute it and/or modify
 
8
it under the terms of the GNU Lesser General Public License as published by
 
9
the Free Software Foundation; either version 2.1 of the License, or (at your
 
10
option) any later version.
 
11
 
 
12
The GNU MP Library is distributed in the hope that it will be useful, but
 
13
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 
14
or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
 
15
License for more details.
 
16
 
 
17
You should have received a copy of the GNU Lesser General Public License
 
18
along with the GNU MP Library; see the file COPYING.LIB.  If not, write to
 
19
the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
 
20
MA 02111-1307, USA. */
 
21
 
 
22
#include "gmp.h"
 
23
#include "gmp-impl.h"
 
24
#include "longlong.h"
 
25
 
 
26
 
 
27
/* Does not work for U == 0 or V == 0.  It would be tough to make it work for
 
28
   V == 0 since gcd(x,0) = x, and U does not generally fit in an mp_limb_t.
 
29
 
 
30
   The threshold for doing u%v when size==1 will vary by CPU according to
 
31
   the speed of a division and the code generated for the main loop.  Any
 
32
   tuning for this is left to a CPU specific implementation.  */
 
33
 
 
34
mp_limb_t
 
35
mpn_gcd_1 (mp_srcptr up, mp_size_t size, mp_limb_t vlimb)
 
36
{
 
37
  mp_limb_t      ulimb;
 
38
  unsigned long  zero_bits, u_low_zero_bits;
 
39
 
 
40
  ASSERT (size >= 1);
 
41
  ASSERT (vlimb != 0);
 
42
  ASSERT_MPN_NONZERO_P (up, size);
 
43
 
 
44
  ulimb = up[0];
 
45
 
 
46
  /* Need vlimb odd for modexact, want it odd to get common zeros. */
 
47
  count_trailing_zeros (zero_bits, vlimb);
 
48
  vlimb >>= zero_bits;
 
49
 
 
50
  if (size > 1)
 
51
    {
 
52
      /* Must get common zeros before the mod reduction.  If ulimb==0 then
 
53
         vlimb already gives the common zeros.  */
 
54
      if (ulimb != 0)
 
55
        {
 
56
          count_trailing_zeros (u_low_zero_bits, ulimb);
 
57
          zero_bits = MIN (zero_bits, u_low_zero_bits);
 
58
        }
 
59
 
 
60
      ulimb = MPN_MOD_OR_MODEXACT_1_ODD (up, size, vlimb);
 
61
      if (ulimb == 0)
 
62
        goto done;
 
63
 
 
64
      goto strip_u_maybe;
 
65
    }
 
66
 
 
67
  /* size==1, so up[0]!=0 */
 
68
  count_trailing_zeros (u_low_zero_bits, ulimb);
 
69
  ulimb >>= u_low_zero_bits;
 
70
  zero_bits = MIN (zero_bits, u_low_zero_bits);
 
71
 
 
72
  /* make u bigger */
 
73
  if (vlimb > ulimb)
 
74
    MP_LIMB_T_SWAP (ulimb, vlimb);
 
75
 
 
76
  /* if u is much bigger than v, reduce using a division rather than
 
77
     chipping away at it bit-by-bit */
 
78
  if ((ulimb >> 16) > vlimb)
 
79
    {
 
80
      ulimb %= vlimb;
 
81
      if (ulimb == 0)
 
82
        goto done;
 
83
      goto strip_u_maybe;
 
84
    }
 
85
 
 
86
  while (ulimb != vlimb)
 
87
    {
 
88
      ASSERT (ulimb & 1);
 
89
      ASSERT (vlimb & 1);
 
90
 
 
91
      if (ulimb > vlimb)
 
92
        {
 
93
          ulimb -= vlimb;
 
94
          do
 
95
            {
 
96
              ulimb >>= 1;
 
97
              ASSERT (ulimb != 0);
 
98
            strip_u_maybe:
 
99
              ;
 
100
            }
 
101
          while ((ulimb & 1) == 0);
 
102
        }
 
103
      else /*  vlimb > ulimb.  */
 
104
        {
 
105
          vlimb -= ulimb;
 
106
          do
 
107
            {
 
108
              vlimb >>= 1;
 
109
              ASSERT (vlimb != 0);
 
110
            }
 
111
          while ((vlimb & 1) == 0);
 
112
        }
 
113
    }
 
114
 
 
115
 done:
 
116
  return vlimb << zero_bits;
 
117
}