1 /****************************************************************************/
2 /* */
3 /* This file is part of CONCORDE */
4 /* */
5 /* (c) Copyright 1995--1999 by David Applegate, Robert Bixby, */
6 /* Vasek Chvatal, and William Cook */
7 /* */
8 /* Permission is granted for academic research use. For other uses, */
9 /* contact the authors for licensing options. */
10 /* */
11 /* Use at your own risk. We make no guarantees about the */
12 /* correctness or usefulness of this code. */
13 /* */
14 /****************************************************************************/
15
16 /****************************************************************************/
17 /* */
18 /* BIGGUY OPERATIONS: */
19 /* */
20 /* x += y CCbigguy_add (CCbigguy *x, CCbigguy y) */
21 /* x -= y CCbigguy_sub (CCbigguy *x, CCbigguy y) */
22 /* x += y*m CCbigguy_addmult (CCbigguy *x, CCbigguy y, */
23 /* int m) */
24 /* x<y -1, x==y 0, x>y 1 CCbigguy_cmp (CCbigguy x, CCbigguy y) */
25 /* ceil(x) CCbigguy_ceil (CCbigguy x) */
26 /* */
27 /* (double) x CCbigguy_bigguytod (CCbigguy x) */
28 /* (bigguy) i CCbigguy_itobigguy (int i) */
29 /* (bigguy) d CCbigguy_dtobigguy (double d) */
30 /* */
31 /* read(x) CCbigguy_sread (CC_SFILE *f, CCbigguy *x) */
32 /* write(x) CCbigguy_swrite (CC_SFILE *f, CCbigguy x) */
33 /* */
34 /* biggest possible x const CCbigguy CCbigguy_MAXBIGGUY */
35 /* smallest possible x const CCbigguy CCbigguy_MINBIGGUY */
36 /* 0 const CCbigguy CCbigguy_ZERO */
37 /* 1 const CCbigguy CCbigguy_ONE */
38 /* */
39 /* */
40 /* EXPORTED FUNCTIONS: */
41 /* */
42 /* int CCbigguy_swrite (CC_SFILE *f, CCbigguy x) */
43 /* NONE */
44 /* */
45 /* int CCbigguy_sread (CC_SFILE *f, CCbigguy *x) */
46 /* NONE */
47 /* */
48 /* void CCbigguy_addmult (CCbigguy *x, CCbigguy y, int m) */
49 /* If an overflow occurs, an error message is output and the routine */
50 /* aborts. If CC_BIGGUY_BUILTIN is defined, this is implemented by a */
51 /* macro, and has no overflow checking. */
52 /* */
53 /* int CCbigguy_cmp (CCbigguy x, CCbigguy y) */
54 /* If CC_BIGGUY_BUILTIN is defined, this is implemented by a macro, */
55 /* and has no overflow checking. */
56 /* */
57 /* double CCbigguytod (CCbigguy x) */
58 /* If CC_BIGGUY_BUILTIN is defined, this is implemented by a macro, */
59 /* and has no overflow checking. */
60 /* */
61 /* CCbigguy CCbigguy_itobigguy (int d) */
62 /* If CC_BIGGUY_BUILTIN is defined, this is implemented by a macro, */
63 /* and has no overflow checking. */
64 /* */
65 /* CCbigguy CCbigguy_dtobigguy (double d) */
66 /* If an overflow occurs, an error message is output and the routine */
67 /* aborts. If CC_BIGGUY_BUILTIN is defined, this is implemented by a */
68 /* macro, and has no overflow checking. */
69 /* */
70 /* CCbigguy CCbigguy_ceil (CCbigguy x) */
71 /* If an overflow occurs, an error message is output and the routine */
72 /* aborts. If CC_BIGGUY_BUILTIN is defined, this is implemented by a */
73 /* macro, and has no overflow checking. */
74 /* */
75 /****************************************************************************/
76
77 #include "machdefs.h"
78 #include "util.h"
79 #include "bigguy.h"
80
81 #ifdef CC_BIGGUY_BUILTIN
82
CCbigguy_swrite(CC_SFILE * f,CCbigguy x)83 int CCbigguy_swrite (CC_SFILE *f, CCbigguy x)
84 {
85 if (CCutil_swrite_ushort (f, (unsigned short) ((x>>48)&0xffff))) return -1;
86 if (CCutil_swrite_ushort (f, (unsigned short) ((x>>32)&0xffff))) return -1;
87 if (CCutil_swrite_ushort (f, (unsigned short) ((x>>16)&0xffff))) return -1;
88 if (CCutil_swrite_ushort (f, (unsigned short) (x&0xffff))) return -1;
89
90 return 0;
91 }
92
CCbigguy_sread(CC_SFILE * f,CCbigguy * x)93 int CCbigguy_sread (CC_SFILE *f, CCbigguy *x)
94 {
95 unsigned short y;
96
97 if (CCutil_sread_ushort (f, &y)) return -1;
98 *x = ((CCbigguy) y) << 48;
99 if (CCutil_sread_ushort (f, &y)) return -1;
100 *x |= ((CCbigguy) y) << 32;
101 if (CCutil_sread_ushort (f, &y)) return -1;
102 *x |= ((CCbigguy) y) << 16;
103 if (CCutil_sread_ushort (f, &y)) return -1;
104 *x |= ((CCbigguy) y);
105 return 0;
106 }
107
108 #else /* CC_BIGGUY_BUILTIN */
109
110 const CCbigguy CCbigguy_MINBIGGUY = {0x8000,0x0000,0x0000,0x0001};
111 const CCbigguy CCbigguy_MAXBIGGUY = {0x7fff,0xffff,0xffff,0xffff};
112 const CCbigguy CCbigguy_ZERO = {0,0,0,0};
113 const CCbigguy CCbigguy_ONE = {0,1,0,0};
114
115
116 static void
117 bigguy_neg (CCbigguy *x);
118
119
bigguy_neg(CCbigguy * x)120 static void bigguy_neg (CCbigguy *x)
121 {
122 x->ihi = ((unsigned int) 65535) - (unsigned int) x->ihi;
123 x->ilo = ((unsigned int) 65535) - (unsigned int) x->ilo;
124 x->fhi = ((unsigned int) 65535) - (unsigned int) x->fhi;
125 x->flo = ((unsigned int) 65535) - (unsigned int) x->flo;
126
127 if ((unsigned int) x->flo < 65535) {
128 x->flo = (unsigned int) x->flo + 1;
129 } else {
130 x->flo = 0;
131 if ((unsigned int) x->fhi < 65535) {
132 x->fhi = (unsigned int) x->fhi + 1;
133 } else {
134 x->fhi = 0;
135 if ((unsigned int) x->ilo < 65535) {
136 x->ilo = (unsigned int) x->ilo + 1;
137 } else {
138 x->ilo = 0;
139 if ((unsigned int) x->ihi == 32767) {
140 fprintf (stderr, "OVERFLOW in bigguy_neg\n");
141 fprintf (stderr, "BIGGUY errors are fatal\n");
142 abort ();
143 } else if ((unsigned int) x->ihi < 65535) {
144 x->ihi = (unsigned int) x->ihi + 1;
145 } else {
146 x->ihi = 0;
147 }
148 }
149 }
150 }
151 }
152
CCbigguy_swrite(CC_SFILE * f,CCbigguy x)153 int CCbigguy_swrite (CC_SFILE *f, CCbigguy x)
154 {
155 if (CCutil_swrite_ushort (f, x.ihi)) return -1;
156 if (CCutil_swrite_ushort (f, x.ilo)) return -1;
157 if (CCutil_swrite_ushort (f, x.fhi)) return -1;
158 if (CCutil_swrite_ushort (f, x.flo)) return -1;
159
160 return 0;
161 }
162
CCbigguy_sread(CC_SFILE * f,CCbigguy * x)163 int CCbigguy_sread (CC_SFILE *f, CCbigguy *x)
164 {
165 if (CCutil_sread_ushort (f, &(x->ihi))) return -1;
166 if (CCutil_sread_ushort (f, &(x->ilo))) return -1;
167 if (CCutil_sread_ushort (f, &(x->fhi))) return -1;
168 if (CCutil_sread_ushort (f, &(x->flo))) return -1;
169 return 0;
170 }
171
CCbigguy_bigguytod(CCbigguy x)172 double CCbigguy_bigguytod (CCbigguy x)
173 {
174 int sgn = 1;
175
176 if ((unsigned int) x.ihi >= 32768) {
177 bigguy_neg (&x);
178 sgn = -1;
179 }
180
181 return sgn * (((double) x.ihi) * 65536.0 +
182 ((double) x.ilo) +
183 ((double) x.fhi) / 65536.0 +
184 ((double) x.flo) / (65536.0*65536.0));
185 }
186
CCbigguy_itobigguy(int d)187 CCbigguy CCbigguy_itobigguy (int d)
188 {
189 CCbigguy x;
190 int sgn;
191
192 if (d < 0) {
193 d = -d;
194 sgn = -1;
195 } else {
196 sgn = 1;
197 }
198
199 if (d < 0 || (d >> 16) >= 32768) {
200 fprintf (stderr, "OVERFLOW in CCbigguy_itobigguy\n");
201 fprintf (stderr, "BIGGUY errors are fatal\n");
202 abort ();
203 }
204 x.ihi = ((unsigned short) (d >> 16));
205 x.ilo = ((unsigned short) (d & 0xffff));
206 x.fhi = 0;
207 x.flo = 0;
208
209 if (sgn == -1) {
210 bigguy_neg (&x);
211 }
212 return x;
213 }
214
CCbigguy_dtobigguy(double d)215 CCbigguy CCbigguy_dtobigguy (double d)
216 {
217 CCbigguy x;
218 int sgn;
219
220 if (d < 0.0) {
221 d = -d;
222 sgn = -1;
223 } else {
224 sgn = 1;
225 }
226
227 if (d / 65536.0 >= 32768.0) {
228 fprintf (stderr, "OVERFLOW in CCbigguy_dtobigguy (%.6f)\n", d * sgn);
229 fprintf (stderr, "BIGGUY errors are fatal\n");
230 abort ();
231 }
232
233 x.ihi = ((unsigned short) (d / 65536.0));
234 d -= ((double) x.ihi) * 65536.0;
235 x.ilo = ((unsigned short) d);
236 d -= ((double) x.ilo);
237 x.fhi = ((unsigned short) (d * 65536.0));
238 d -= ((double) x.fhi) / 65536.0;
239 x.flo = ((unsigned short) (d * 65536.0 * 65536.0));
240
241 if (sgn == -1) {
242 bigguy_neg (&x);
243 }
244
245 return x;
246 }
247
CCbigguy_ceil(CCbigguy x)248 CCbigguy CCbigguy_ceil (CCbigguy x)
249 {
250 if ((unsigned int) x.fhi || (unsigned int) x.flo) {
251 x.fhi = 0;
252 x.flo = 0;
253 x.ilo = (unsigned int) x.ilo + 1;
254 if ((unsigned int) x.ilo == 0) {
255 if ((unsigned int) x.ihi == 32767) {
256 fprintf (stderr, "OVERFLOW in CCbigguy_ceil\n");
257 fprintf (stderr, "BIGGUY errors are fatal\n");
258 abort ();
259 }
260 x.ihi = (unsigned int) x.ihi + 1;
261 }
262 }
263
264 return x;
265 }
266
CCbigguy_cmp(CCbigguy x,CCbigguy y)267 int CCbigguy_cmp (CCbigguy x, CCbigguy y)
268 {
269 if ((unsigned int) x.ihi >= 32768 && (unsigned int) y.ihi < 32768) return -1;
270 else if ((unsigned int) x.ihi < 32768 && (unsigned int) y.ihi >= 32768) return 1;
271 else if ((unsigned int) x.ihi < (unsigned int) y.ihi) return -1;
272 else if ((unsigned int) x.ihi > (unsigned int) y.ihi) return 1;
273 else if ((unsigned int) x.ilo < (unsigned int) y.ilo) return -1;
274 else if ((unsigned int) x.ilo > (unsigned int) y.ilo) return 1;
275 else if ((unsigned int) x.fhi < (unsigned int) y.fhi) return -1;
276 else if ((unsigned int) x.fhi > (unsigned int) y.fhi) return 1;
277 else if ((unsigned int) x.flo < (unsigned int) y.flo) return -1;
278 else if ((unsigned int) x.flo > (unsigned int) y.flo) return 1;
279 else return 0;
280 }
281
CCbigguy_addmult(CCbigguy * x,CCbigguy y,int m)282 void CCbigguy_addmult (CCbigguy *x, CCbigguy y, int m)
283 {
284 int carry = 0;
285 int sgn;
286 int oldsgn;
287 int mlo;
288 int mhi;
289
290 if (m == -m && m != 0) {
291 fprintf (stderr, "OVERFLOW in CCbigguy_addmult (1)\n");
292 fprintf (stderr, "BIGGUY errors are fatal\n");
293 abort ();
294 }
295
296 if ((unsigned int) y.ihi >= 32768) {
297 bigguy_neg (&y);
298 m = -m;
299 }
300
301 mhi = m / 65536;
302 mlo = m - mhi*65536;
303 if (mlo < -32768) {
304 mlo += 65536;
305 mhi--;
306 }
307 if (mlo > 32767) {
308 mlo -= 65536;
309 mhi++;
310 }
311 if (mlo < -32768 || mlo > 32767) {
312 fprintf (stderr, "OVERFLOW in CCbigguy_addmult (2)\n");
313 fprintf (stderr, "BIGGUY errors are fatal\n");
314 abort ();
315 }
316 if (mhi < -32768 || mhi > 32767) {
317 fprintf (stderr, "OVERFLOW in CCbigguy_addmult (3)\n");
318 fprintf (stderr, "BIGGUY errors are fatal\n");
319 abort ();
320 }
321
322 if ((unsigned int) x->ihi >= 32768) {
323 oldsgn = -1;
324 } else {
325 oldsgn = 1;
326 }
327
328 carry = (unsigned int) x->flo + mlo * (unsigned int) y.flo;
329 x->flo = carry & ((unsigned int) 0xffff);
330 carry -= (unsigned int) x->flo;
331 carry /= 65536;
332 carry = carry + (unsigned int) x->fhi + mlo * (unsigned int) y.fhi;
333 x->fhi = carry & ((unsigned int) 0xffff);
334 carry -= (unsigned int) x->fhi;
335 carry /= 65536;
336 carry = carry + (unsigned int) x->ilo + mlo * (unsigned int) y.ilo;
337 x->ilo = carry & ((unsigned int) 0xffff);
338 carry -= (unsigned int) x->ilo;
339 carry /= 65536;
340 carry = carry + (unsigned int) x->ihi + mlo * (unsigned int) y.ihi;
341 x->ihi = carry & ((unsigned int) 0xffff);
342 carry -= (unsigned int) x->ihi;
343 carry /= 65536;
344
345 if ((unsigned int) x->ihi >= 32768) {
346 sgn = -1;
347 } else {
348 sgn = 1;
349 }
350 if (carry < -1 || carry > 1 ||
351 (carry == -1 && !(oldsgn == 1 && sgn == -1)) ||
352 (carry == 0 && oldsgn != sgn) ||
353 (carry == 1 && !(oldsgn == -1 && sgn == 1))) {
354 fprintf (stderr, "OVERFLOW in CCbigguy_addmult (4)\n");
355 fprintf (stderr, "BIGGUY errors are fatal\n");
356 abort ();
357 }
358
359 oldsgn = sgn;
360
361 carry = (unsigned int) x->fhi + mhi * (unsigned int) y.flo;
362 x->fhi = carry & ((unsigned int) 0xffff);
363 carry -= (unsigned int) x->fhi;
364 carry /= 65536;
365 carry = carry + (unsigned int) x->ilo + mhi * (unsigned int) y.fhi;
366 x->ilo = carry & ((unsigned int) 0xffff);
367 carry -= (unsigned int) x->ilo;
368 carry /= 65536;
369 carry = carry + (unsigned int) x->ihi + mhi * (unsigned int) y.ilo;
370 x->ihi = carry & ((unsigned int) 0xffff);
371 carry -= (unsigned int) x->ihi;
372 carry /= 65536;
373 carry = carry + mhi * (unsigned int) y.ihi;
374
375 if ((unsigned int) x->ihi >= 32768) {
376 sgn = -1;
377 } else {
378 sgn = 1;
379 }
380 if (carry < -1 || carry > 1 ||
381 (carry == -1 && !(oldsgn == 1 && sgn == -1)) ||
382 (carry == 0 && oldsgn != sgn) ||
383 (carry == 1 && !(oldsgn == -1 && sgn == 1))) {
384 fprintf (stderr, "OVERFLOW in CCbigguy_addmult (4)\n");
385 fprintf (stderr, "BIGGUY errors are fatal\n");
386 abort ();
387 }
388 }
389
390 #endif /* CC_BIGGUY_BUILTIN */
391