File : s-gccdiv.adb
1 ------------------------------------------------------------------------------
2 -- --
3 -- GNAT COMPILER COMPONENTS --
4 -- --
5 -- S Y S T E M . G C C . D I V I S I O N S --
6 -- --
7 -- B o d y --
8 -- --
9 -- Copyright (C) 2013-2016, Free Software Foundation, Inc. --
10 -- --
11 -- GNAT is free software; you can redistribute it and/or modify it under --
12 -- terms of the GNU General Public License as published by the Free Soft- --
13 -- ware Foundation; either version 3, or (at your option) any later ver- --
14 -- sion. GNAT is distributed in the hope that it will be useful, but WITH- --
15 -- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY --
16 -- or FITNESS FOR A PARTICULAR PURPOSE. --
17 -- --
18 -- --
19 -- --
20 -- --
21 -- --
22 -- You should have received a copy of the GNU General Public License and --
23 -- a copy of the GCC Runtime Library Exception along with this program; --
24 -- see the files COPYING3 and COPYING.RUNTIME respectively. If not, see --
25 -- <http://www.gnu.org/licenses/>. --
26 -- --
27 -- GNAT was originally developed by the GNAT team at New York University. --
28 -- Extensive contributions were provided by Ada Core Technologies Inc. --
29 -- --
30 ------------------------------------------------------------------------------
31
32 -- Ada implementation of libgcc: 64-bit Divisions
33
34 package body System.GCC.Divisions is
35 use Interfaces;
36
37 function Udivmoddi3 (Num : Unsigned_64;
38 Den : Unsigned_64;
39 Return_Rem : Boolean)
40 return Unsigned_64;
41 -- Divide Num by Den and return the remainder if Return_Rem is true, or
42 -- the quotient if false.
43
44 function Divmoddi3 (Num : Integer_64;
45 Den : Integer_64;
46 Return_Rem : Boolean)
47 return Integer_64;
48 ----------------
49 -- Udivmoddi3 --
50 ----------------
51
52 function Udivmoddi3 (Num : Unsigned_64;
53 Den : Unsigned_64;
54 Return_Rem : Boolean)
55 return Unsigned_64
56 is
57 Q, R : Unsigned_64;
58 N : Unsigned_64;
59 begin
60 -- Check for division by 0
61 if Den = 0 then
62 raise Constraint_Error;
63 end if;
64
65 -- Restoring algorithm
66 Q := 0;
67 R := 0;
68 N := Num;
69 for I in 1 .. 64 loop
70 -- Insert one bit from the numerator
71 R := Shift_Left (R, 1) or Shift_Right (N, 63);
72 N := Shift_Left (N, 1);
73
74 -- Compute one bit of the quotient
75 Q := Shift_Left (Q, 1);
76 if R >= Den then
77 R := R - Den;
78 Q := Q or 1;
79 end if;
80
81 -- Loop invariants (they are also true before the loop):
82
83 -- The remainder is always less than the denominator
84 pragma Assert (R < Den);
85
86 -- Division definition
87 pragma Assert (Shift_Left (Q, 64 - I) * Den
88 + Shift_Left (R, 64 - I)
89 + Shift_Right (N, I) = Num);
90 end loop;
91
92 if Return_Rem then
93 return R;
94 else
95 return Q;
96 end if;
97 end Udivmoddi3;
98
99 -------------
100 -- Udivdi3 --
101 -------------
102
103 function Udivdi3 (Num : Unsigned_64; Den : Unsigned_64)
104 return Unsigned_64 is
105 begin
106 return Udivmoddi3 (Num, Den, False);
107 end Udivdi3;
108
109 -------------
110 -- Umoddi3 --
111 -------------
112
113 function Umoddi3 (Num : Unsigned_64; Den : Unsigned_64)
114 return Unsigned_64 is
115 begin
116 return Udivmoddi3 (Num, Den, True);
117 end Umoddi3;
118
119 ---------------
120 -- Divmoddi3 --
121 ---------------
122
123 function Divmoddi3 (Num : Integer_64;
124 Den : Integer_64;
125 Return_Rem : Boolean)
126 return Integer_64
127 is
128 Neg : Boolean := False;
129 N : Unsigned_64;
130 D : Unsigned_64;
131 R : Unsigned_64;
132 begin
133 if Num < 0 then
134 Neg := True;
135 N := Unsigned_64 (-Num);
136 else
137 N := Unsigned_64 (Num);
138 end if;
139
140 if Den < 0 then
141 Neg := not Neg;
142 D := Unsigned_64 (-Den);
143 else
144 D := Unsigned_64 (Den);
145 end if;
146
147 R := Udivmoddi3 (N, D, Return_Rem);
148
149 -- The remainder has the sign of the numerator
150 if Return_Rem then
151 Neg := Num < 0;
152 end if;
153
154 if Neg then
155 return -Integer_64 (R);
156 else
157 return Integer_64 (R);
158 end if;
159 end Divmoddi3;
160
161 ------------
162 -- Divdi3 --
163 ------------
164
165 function Divdi3 (Num : Integer_64; Den : Integer_64) return Integer_64 is
166 begin
167 return Divmoddi3 (Num, Den, False);
168 end Divdi3;
169
170 ------------
171 -- Moddi3 --
172 ------------
173
174 function Moddi3 (Num : Integer_64; Den : Integer_64) return Integer_64 is
175 begin
176 return Divmoddi3 (Num, Den, True);
177 end Moddi3;
178
179 end System.GCC.Divisions;