1 /****************************************************************/
2 /* file aritool0.c
3
4 ARIBAS interpreter for Arithmetic
5 Copyright (C) 1996 O.Forster
6
7 This program is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
11
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software
19 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
20
21 Address of the author
22
23 Otto Forster
24 Math. Institut der LMU
25 Theresienstr. 39
26 D-80333 Muenchen, Germany
27
28 Email forster@rz.mathematik.uni-muenchen.de
29 */
30 /****************************************************************/
31 /*
32 ** aritool0.c
33 ** Hilfsprozeduren fuer Integer-Arithmetik (bignums)
34 ** koennen zur Beschleunigung in Assembler geschrieben werden
35 */
36 /*
37 ** date of last change
38 ** 95-02-01
39 ** 97-02-24: pointer arithmetic in sumarr, diffarr, diff1arr
40 */
41
42 #include "common.h"
43
44 int sumarr _((word2 *x, int n, word2 *y));
45 int diffarr _((word2 *x, int n, word2 *y));
46 int diff1arr _((word2 *x, int n, word2 *y));
47 int incarr _((word2 *x, int n, unsigned a));
48 int decarr _((word2 *x, int n, unsigned a));
49 void cpyarr _((word2 *x, int n, word2 *y));
50 void cpyarr1 _((word2 *x, int n, word2 *y));
51 int cmparr _((word2 *x, int n, word2 *y, int m));
52 int shrarr _((word2 *x, int n, int k));
53 int shlarr _((word2 *x, int n, int k));
54 void setarr _((word2 *x, int n, unsigned a));
55 void notarr _((word2 *x, int n));
56 void andarr _((word2 *x, int n, word2 *y));
57 void orarr _((word2 *x, int n, word2 *y));
58 void xorarr _((word2 *x, int n, word2 *y));
59 unsigned int2bcd _((unsigned x));
60 unsigned bcd2int _((unsigned x));
61 int big2bcd _((word2 *x, int n, word2 *y));
62 int long2big _((word4 u, word2 *x));
63 word4 big2long _((word2 *x, int n));
64 word4 intsqrt _((word4 u));
65 int bitlen _((unsigned x));
66 int niblen _((unsigned x));
67 int bitcount _((unsigned u));
68
69
70 #if defined(MsDOS) || defined(DjGPP) || defined(SCOUNiX) || \
71 defined(LiNUX) || defined(MsWIN32)
72 #ifndef NO_ASSEMB
73 #define ASSEMB86
74 #endif
75 #endif
76
77 #ifndef ASSEMB86
78 /*
79 ** falls ASSEMB86 definiert ist, werden die folgenden Funktionen
80 ** durch Assembler-Code ersetzt
81 */
82
83 int multarr _((word2 *x, int n, unsigned a, word2 *y));
84 int divarr _((word2 *x, int n, unsigned a, word2 *restptr));
85 unsigned modarr _((word2 *x, int n, unsigned a));
86
87 /*-------------------------------------------------------------------*/
88 /*
89 ** y = (x,n) * a
90 ** funktioniert auch, wenn Platz y gleich oder <= Platz x
91 */
multarr(x,n,a,y)92 int multarr(x,n,a,y)
93 word2 *x, *y;
94 unsigned a;
95 int n;
96 {
97 register word4 u, carry = 0;
98 int nn;
99
100 if(a <= 1) {
101 if(!a)
102 return(0);
103 else {
104 cpyarr(x,n,y);
105 return(n);
106 }
107 }
108 nn = n;
109 while(--n >= 0) {
110 u = *x++;
111 u *= a;
112 u += carry;
113 *y++ = u & 0xFFFF;
114 carry = (u >> 16);
115 }
116 if(carry) {
117 *y = carry;
118 nn++;
119 }
120 return(nn);
121 }
122 /*-------------------------------------------------------------------*/
123 /*
124 ** dividiert Array (x,n) destruktiv durch 16-bit-Zahl a
125 ** und speichert Rest in *restptr
126 */
divarr(x,n,a,restptr)127 int divarr(x,n,a,restptr)
128 word2 *x, *restptr;
129 unsigned a;
130 int n;
131 {
132 register word4 u;
133 word2 *xx;
134 int nn;
135
136 if(n == 0) {
137 *restptr = 0;
138 return(0);
139 }
140 xx = x += n;
141 u = 0;
142 nn = n;
143 while(--n >= 0) {
144 u <<= 16;
145 u += *--x;
146 *x = u/a;
147 u %= a;
148 }
149 *restptr = u;
150 return(*--xx ? nn : nn-1);
151 }
152 /*-------------------------------------------------------------------*/
153 /*
154 ** Berechnet den Rest der Division von (x,n) durch 16-bit-Zahl a
155 ** Das Array (x,n) bleibt erhalten
156 */
modarr(x,n,a)157 unsigned modarr(x,n,a)
158 word2 *x;
159 int n;
160 unsigned a;
161 {
162 register word4 u;
163
164 if(n == 0 || a <= 1)
165 return(0);
166 x += n;
167 u = 0;
168 while(--n >= 0) {
169 u <<= 16;
170 u += *--x;
171 u %= a;
172 }
173 return(u);
174 }
175 /*-------------------------------------------------------------------*/
176 #else
177 #undef ASSEMB86
178 #endif
179
180
181 /*-------------------------------------------------------------------*/
182 /*
183 ** (x,n) := (x,n) + (y,n)
184 ** returns 1, if carry is generated, else returns 0
185 */
sumarr(x,n,y)186 int sumarr(x,n,y)
187 word2 *x, *y;
188 int n;
189 {
190 register word4 u;
191 unsigned carry = 0;
192
193 while(--n >= 0) {
194 u = *x;
195 u += *y++;
196 u += carry;
197 *x++ = u & 0xFFFF;
198 carry = (u >= 0x10000 ? 1 : 0);
199 }
200 return(carry);
201 }
202 /*-------------------------------------------------------------------*/
203 /*
204 ** (x,n) := (x,n) - (y,n)
205 ** returns 1, if borrow is generated, else returns 0
206 */
diffarr(x,n,y)207 int diffarr(x,n,y)
208 word2 *x, *y;
209 int n;
210 {
211 register word4 u;
212 unsigned borrow = 0;
213
214 while(--n >= 0) {
215 u = *x;
216 u -= *y++;
217 u -= borrow;
218 *x++ = u & 0xFFFF;
219 borrow = (u & 0xFFFF0000 ? 1 : 0);
220 }
221 return(borrow);
222 }
223 /*-------------------------------------------------------------------*/
224 /*
225 ** (x,n) := (y,n) - (x,n)
226 ** returns 1, if borrow is generated, else returns 0
227 */
diff1arr(x,n,y)228 int diff1arr(x,n,y)
229 word2 *x, *y;
230 int n;
231 {
232 register word4 u;
233 unsigned borrow = 0;
234
235 while(--n >= 0) {
236 u = *y++;
237 u -= *x;
238 u -= borrow;
239 *x++ = u & 0xFFFF;
240 borrow = (u & 0xFFFF0000 ? 1 : 0);
241 }
242 return(borrow);
243 }
244 /*-------------------------------------------------------------------*/
245 /*
246 ** addiert zu Array (x,n) die 16-bit-Zahl a
247 ** arbeitet destruktiv auf x
248 */
incarr(x,n,a)249 int incarr(x,n,a)
250 word2 *x;
251 int n;
252 unsigned a;
253 {
254 word4 u;
255 int nn = n;
256
257 while(a && --n >= 0) {
258 u = *x;
259 u += a;
260 *x++ = u & 0xFFFF;
261 a = (u >= 0x10000 ? 1 : 0);
262 }
263 if(a) {
264 *x = a;
265 nn++;
266 }
267 return(nn);
268 }
269 /*-------------------------------------------------------------------*/
270 /*
271 ** subtrahiert von Array x die 16-bit-Zahl a
272 ** arbeitet destruktiv auf x
273 ** setzt voraus x >= a
274 */
decarr(x,n,a)275 int decarr(x,n,a)
276 word2 *x;
277 int n;
278 unsigned a;
279 {
280 register word4 u;
281 word2 *xx;
282 int nn;
283
284 if(n == 0)
285 return(0);
286 xx = x + n - 1;
287 nn = n;
288 while(a && --n >= 0) {
289 u = *x;
290 u -= a;
291 *x++ = u & 0xFFFF;
292 a = (u & 0xFFFF0000 ? 1 : 0);
293 }
294 if(*xx == 0)
295 nn--;
296 return(nn);
297 }
298 /*-------------------------------------------------------------------*/
299 /*
300 ** kopiert (x,n) nach y beginnend von unten
301 */
cpyarr(x,n,y)302 void cpyarr(x,n,y)
303 word2 *x, *y;
304 int n;
305 {
306 while(--n >= 0)
307 *y++ = *x++;
308 }
309 /*-------------------------------------------------------------------*/
310 /*
311 ** kopiert (x,n) nach y beginnend von oben
312 */
cpyarr1(x,n,y)313 void cpyarr1(x,n,y)
314 word2 *x, *y;
315 int n;
316 {
317 x += n; y += n;
318
319 while(--n >= 0)
320 *--y = *--x;
321 }
322 /*-------------------------------------------------------------------*/
323 /*
324 ** liefert +1, falls (x,n) > (y,m);
325 ** -1, falls (x,n) < (y,m);
326 ** 0, falls (x,n) = (y,m);
327 */
cmparr(x,n,y,m)328 int cmparr(x,n,y,m)
329 word2 *x, *y;
330 int n, m;
331 {
332 if(n != m)
333 return(n > m ? 1 : -1);
334 if(!n)
335 return(0);
336 x += n;
337 y += n;
338 while(--n >= 0)
339 if(*--x != *--y)
340 break;
341 if(*x > *y)
342 return(1);
343 else if(*x < *y)
344 return(-1);
345 else
346 return(0);
347 }
348 /*-------------------------------------------------------------------*/
349 /*
350 ** Rechtsshift von (x,n) um k Bits; 0 <= k <= 15
351 ** arbeitet destruktiv auf x
352 */
shrarr(x,n,k)353 int shrarr(x,n,k)
354 word2 *x;
355 int n, k;
356 {
357 int i, k1 = 16 - k;
358 word2 temp;
359
360 if(!k || !n)
361 return(n);
362 for(i=1; i<n; i++) {
363 *x >>= k;
364 temp = *(x+1) << k1;
365 *x++ |= temp;
366 }
367 *x >>= k;
368 return(*x ? n : n-1);
369 }
370 /*-------------------------------------------------------------------*/
371 /*
372 ** Linksshift von (x,n) um k Bits; 0 <= k <= 15
373 ** arbeitet destruktiv auf x
374 */
shlarr(x,n,k)375 int shlarr(x,n,k)
376 word2 *x;
377 int n, k;
378 {
379 int i, k1 = 16 - k;
380 word2 u = 0, temp;
381
382 if(!k || !n)
383 return(n);
384 for(i=0; i<n; i++) {
385 temp = *x;
386 *x++ = (temp << k) | u;
387 u = (temp >> k1);
388 }
389 if(u) {
390 *x = u;
391 n++;
392 }
393 return(n);
394 }
395 /*-------------------------------------------------------------------*/
setarr(x,n,a)396 void setarr(x,n,a)
397 word2 *x;
398 int n;
399 unsigned a;
400 {
401 while(--n >= 0)
402 *x++ = a;
403 }
404 /*-------------------------------------------------------------------*/
notarr(x,n)405 void notarr(x,n)
406 word2 *x;
407 int n;
408 {
409 while(--n >= 0) {
410 *x = ~*x;
411 x++;
412 }
413 }
414 /*-------------------------------------------------------------------*/
andarr(x,n,y)415 void andarr(x,n,y)
416 word2 *x, *y;
417 int n;
418 {
419 while(--n >= 0) {
420 *x++ &= *y++;
421 }
422 }
423 /*-------------------------------------------------------------------*/
orarr(x,n,y)424 void orarr(x,n,y)
425 word2 *x, *y;
426 int n;
427 {
428 while(--n >= 0) {
429 *x++ |= *y++;
430 }
431 }
432 /*-------------------------------------------------------------------*/
xorarr(x,n,y)433 void xorarr(x,n,y)
434 word2 *x, *y;
435 int n;
436 {
437 while(--n >= 0) {
438 *x++ ^= *y++;
439 }
440 }
441 /*-------------------------------------------------------------------*/
int2bcd(x)442 unsigned int2bcd(x)
443 unsigned x;
444 {
445 int i;
446 word2 a[3];
447 unsigned y;
448
449 for(i=0; i<3; i++) {
450 a[i] = x % 10;
451 x /= 10;
452 }
453 y = x; /* a[3] */
454 for(i=2; i>=0; i--)
455 y = (y<<4) + a[i];
456 return(y);
457 }
458 /*-------------------------------------------------------------------*/
bcd2int(x)459 unsigned bcd2int(x)
460 unsigned x;
461 {
462 int i;
463 word2 a[3];
464 unsigned y;
465
466 for(i=0; i<3; i++) {
467 a[i] = (0x000F & x);
468 x >>= 4;
469 }
470 y = x;
471 for(i=2; i>=0; i--)
472 y = y*10 + a[i];
473 return(y);
474 }
475 /*-------------------------------------------------------------------*/
476 /*
477 ** verwandelt big-Array (x,n) in bcd-Array y
478 ** !!! arbeitet destruktiv auf x !!!
479 ** Rueckgabewert Anzahl der Dezimalstellen von x
480 */
big2bcd(x,n,y)481 int big2bcd(x,n,y)
482 word2 *x, *y;
483 int n;
484 {
485 int k = -1;
486
487 if(!n)
488 return(0);
489 while(n) {
490 n = divarr(x,n,10000,y);
491 *y = int2bcd(*y);
492 y++;
493 k++;
494 }
495 return(k*4 + niblen(*--y));
496 }
497 /*-------------------------------------------------------------------*/
long2big(u,x)498 int long2big(u,x)
499 word4 u;
500 word2 *x;
501 {
502 if(u == 0)
503 return(0);
504 x[0] = u;
505 if(u < 0x10000)
506 return(1);
507 else {
508 x[1] = (u >> 16);
509 return(2);
510 }
511 }
512 /*-------------------------------------------------------------------*/
big2long(x,n)513 word4 big2long(x,n)
514 word2 *x;
515 int n;
516 {
517 word4 u = 0;
518
519 if(n >= 2) {
520 u = x[1];
521 u <<= 16;
522 }
523 if(n >= 1)
524 u += x[0];
525 return(u);
526 }
527 /*-------------------------------------------------------------------*/
528 /*
529 ** berechnet die groesste ganze Zahl x mit x*x <= u
530 */
intsqrt(u)531 word4 intsqrt(u)
532 word4 u;
533 {
534 word4 v, x, x1, b;
535 int n;
536
537 if(!u)
538 return(0);
539 v = 0x40000000;
540 x = 0x8000;
541 n = 15;
542 while(v > u) {
543 v >>= 2;
544 x >>= 1;
545 n--;
546 }
547 b = x;
548 u -= v;
549 while(--n >= 0) {
550 b >>= 1;
551 x1 = x + b;
552 v = (x + x1) << n;
553 if(u >= v) {
554 x = x1;
555 u -= v;
556 }
557 }
558 return(x);
559 }
560 /*------------------------------------------------------------------*/
561 /*
562 ** bestimmt Laenge in Bits einer 16-Bit-Zahl x
563 ** 0 <= bitlen <= 16; bitlen = 0 <==> x == 0;
564 */
bitlen(x)565 int bitlen(x)
566 unsigned x;
567 {
568 int len;
569 unsigned mask;
570
571 if(x & 0xFF00) {
572 len = 16;
573 mask = 0x8000;
574 }
575 else if(x) {
576 len = 8;
577 mask = 0x0080;
578 }
579 else
580 return(0);
581 while(!(x & mask)) {
582 mask >>= 1;
583 len--;
584 }
585 return(len);
586 }
587 /*-------------------------------------------------------------------*/
niblen(x)588 int niblen(x)
589 unsigned x;
590 {
591 int len = 4;
592 unsigned mask = 0xF000;
593
594 if(!x)
595 return(0);
596 while(!(x & mask)) {
597 mask >>= 4;
598 len--;
599 }
600 return(len);
601 }
602 /*-------------------------------------------------------------------*/
603 /*
604 ** returns number of set bits in 16-bit number u
605 */
bitcount(u)606 PUBLIC int bitcount(u)
607 unsigned u;
608 {
609 unsigned mask = 1;
610 int count = 0;
611 int k;
612
613 for(k=0; k<16; k++) {
614 if(u & mask)
615 count++;
616 else if(mask > u)
617 break;
618 mask <<= 1;
619 }
620 return count;
621 }
622 /*********************************************************************/
623