1 typedef unsigned long ulong;
2 typedef unsigned int uint;
3 typedef unsigned short ushort;
4 typedef unsigned char uchar;
5 typedef signed char schar;
6
7 #define SIGN(n) (1UL<<(n-1))
8
9 typedef struct Vlong Vlong;
10 struct Vlong
11 {
12 union
13 {
14 struct
15 {
16 ulong lo;
17 ulong hi;
18 };
19 struct
20 {
21 ushort lols;
22 ushort loms;
23 ushort hils;
24 ushort hims;
25 };
26 };
27 };
28
29 void abort(void);
30
31 void _subv(Vlong*, Vlong, Vlong);
32
33 void
_d2v(Vlong * y,double d)34 _d2v(Vlong *y, double d)
35 {
36 union { double d; struct Vlong; } x;
37 ulong xhi, xlo, ylo, yhi;
38 int sh;
39
40 x.d = d;
41
42 xhi = (x.hi & 0xfffff) | 0x100000;
43 xlo = x.lo;
44 sh = 1075 - ((x.hi >> 20) & 0x7ff);
45
46 ylo = 0;
47 yhi = 0;
48 if(sh >= 0) {
49 /* v = (hi||lo) >> sh */
50 if(sh < 32) {
51 if(sh == 0) {
52 ylo = xlo;
53 yhi = xhi;
54 } else {
55 ylo = (xlo >> sh) | (xhi << (32-sh));
56 yhi = xhi >> sh;
57 }
58 } else {
59 if(sh == 32) {
60 ylo = xhi;
61 } else
62 if(sh < 64) {
63 ylo = xhi >> (sh-32);
64 }
65 }
66 } else {
67 /* v = (hi||lo) << -sh */
68 sh = -sh;
69 if(sh <= 10) {
70 ylo = xlo << sh;
71 yhi = (xhi << sh) | (xlo >> (32-sh));
72 } else {
73 /* overflow */
74 yhi = d; /* causes something awful */
75 }
76 }
77 if(x.hi & SIGN(32)) {
78 if(ylo != 0) {
79 ylo = -ylo;
80 yhi = ~yhi;
81 } else
82 yhi = -yhi;
83 }
84
85 y->hi = yhi;
86 y->lo = ylo;
87 }
88
89 void
_f2v(Vlong * y,float f)90 _f2v(Vlong *y, float f)
91 {
92
93 _d2v(y, f);
94 }
95
96 double
_v2d(Vlong x)97 _v2d(Vlong x)
98 {
99 if(x.hi & SIGN(32)) {
100 if(x.lo) {
101 x.lo = -x.lo;
102 x.hi = ~x.hi;
103 } else
104 x.hi = -x.hi;
105 return -((long)x.hi*4294967296. + x.lo);
106 }
107 return (long)x.hi*4294967296. + x.lo;
108 }
109
110 float
_v2f(Vlong x)111 _v2f(Vlong x)
112 {
113 return _v2d(x);
114 }
115
116 ulong _div64by32(Vlong, ulong, ulong*);
117 int _mul64by32(Vlong*, Vlong, ulong);
118
119 static void
slowdodiv(Vlong num,Vlong den,Vlong * q,Vlong * r)120 slowdodiv(Vlong num, Vlong den, Vlong *q, Vlong *r)
121 {
122 ulong numlo, numhi, denhi, denlo, quohi, quolo, t;
123 int i;
124
125 numhi = num.hi;
126 numlo = num.lo;
127 denhi = den.hi;
128 denlo = den.lo;
129
130 /*
131 * get a divide by zero
132 */
133 if(denlo==0 && denhi==0) {
134 numlo = numlo / denlo;
135 }
136
137 /*
138 * set up the divisor and find the number of iterations needed
139 */
140 if(numhi >= SIGN(32)) {
141 quohi = SIGN(32);
142 quolo = 0;
143 } else {
144 quohi = numhi;
145 quolo = numlo;
146 }
147 i = 0;
148 while(denhi < quohi || (denhi == quohi && denlo < quolo)) {
149 denhi = (denhi<<1) | (denlo>>31);
150 denlo <<= 1;
151 i++;
152 }
153
154 quohi = 0;
155 quolo = 0;
156 for(; i >= 0; i--) {
157 quohi = (quohi<<1) | (quolo>>31);
158 quolo <<= 1;
159 if(numhi > denhi || (numhi == denhi && numlo >= denlo)) {
160 t = numlo;
161 numlo -= denlo;
162 if(numlo > t)
163 numhi--;
164 numhi -= denhi;
165 quolo |= 1;
166 }
167 denlo = (denlo>>1) | (denhi<<31);
168 denhi >>= 1;
169 }
170
171 if(q) {
172 q->lo = quolo;
173 q->hi = quohi;
174 }
175 if(r) {
176 r->lo = numlo;
177 r->hi = numhi;
178 }
179 }
180
181 static void
dodiv(Vlong num,Vlong den,Vlong * qp,Vlong * rp)182 dodiv(Vlong num, Vlong den, Vlong *qp, Vlong *rp)
183 {
184 ulong n;
185 Vlong x, q, r;
186
187 if(den.hi > num.hi || (den.hi == num.hi && den.lo > num.lo)){
188 if(qp) {
189 qp->hi = 0;
190 qp->lo = 0;
191 }
192 if(rp) {
193 rp->hi = num.hi;
194 rp->lo = num.lo;
195 }
196 return;
197 }
198
199 if(den.hi != 0){
200 q.hi = 0;
201 n = num.hi/den.hi;
202 if(_mul64by32(&x, den, n) || x.hi > num.hi ||
203 (x.hi == num.hi && x.lo > num.lo))
204 slowdodiv(num, den, &q, &r);
205 else {
206 q.lo = n;
207 _subv(&r, num, x);
208 }
209 } else {
210 if(num.hi >= den.lo){
211 q.hi = n = num.hi/den.lo;
212 num.hi -= den.lo*n;
213 } else {
214 q.hi = 0;
215 }
216 q.lo = _div64by32(num, den.lo, &r.lo);
217 r.hi = 0;
218 }
219 if(qp) {
220 qp->lo = q.lo;
221 qp->hi = q.hi;
222 }
223 if(rp) {
224 rp->lo = r.lo;
225 rp->hi = r.hi;
226 }
227 }
228
229 void
_divvu(Vlong * q,Vlong n,Vlong d)230 _divvu(Vlong *q, Vlong n, Vlong d)
231 {
232
233 if(n.hi == 0 && d.hi == 0) {
234 q->hi = 0;
235 q->lo = n.lo / d.lo;
236 return;
237 }
238 dodiv(n, d, q, 0);
239 }
240
241 void
_modvu(Vlong * r,Vlong n,Vlong d)242 _modvu(Vlong *r, Vlong n, Vlong d)
243 {
244
245 if(n.hi == 0 && d.hi == 0) {
246 r->hi = 0;
247 r->lo = n.lo % d.lo;
248 return;
249 }
250 dodiv(n, d, 0, r);
251 }
252
253 static void
vneg(Vlong * v)254 vneg(Vlong *v)
255 {
256
257 if(v->lo == 0) {
258 v->hi = -v->hi;
259 return;
260 }
261 v->lo = -v->lo;
262 v->hi = ~v->hi;
263 }
264
265 void
_divv(Vlong * q,Vlong n,Vlong d)266 _divv(Vlong *q, Vlong n, Vlong d)
267 {
268 long nneg, dneg;
269
270 if(n.hi == (((long)n.lo)>>31) && d.hi == (((long)d.lo)>>31)) {
271 q->lo = (long)n.lo / (long)d.lo;
272 q->hi = ((long)q->lo) >> 31;
273 return;
274 }
275 nneg = n.hi >> 31;
276 if(nneg)
277 vneg(&n);
278 dneg = d.hi >> 31;
279 if(dneg)
280 vneg(&d);
281 dodiv(n, d, q, 0);
282 if(nneg != dneg)
283 vneg(q);
284 }
285
286 void
_modv(Vlong * r,Vlong n,Vlong d)287 _modv(Vlong *r, Vlong n, Vlong d)
288 {
289 long nneg, dneg;
290
291 if(n.hi == (((long)n.lo)>>31) && d.hi == (((long)d.lo)>>31)) {
292 r->lo = (long)n.lo % (long)d.lo;
293 r->hi = ((long)r->lo) >> 31;
294 return;
295 }
296 nneg = n.hi >> 31;
297 if(nneg)
298 vneg(&n);
299 dneg = d.hi >> 31;
300 if(dneg)
301 vneg(&d);
302 dodiv(n, d, 0, r);
303 if(nneg)
304 vneg(r);
305 }
306
307 void
_rshav(Vlong * r,Vlong a,int b)308 _rshav(Vlong *r, Vlong a, int b)
309 {
310 long t;
311
312 t = a.hi;
313 if(b >= 32) {
314 r->hi = t>>31;
315 if(b >= 64) {
316 /* this is illegal re C standard */
317 r->lo = t>>31;
318 return;
319 }
320 r->lo = t >> (b-32);
321 return;
322 }
323 if(b <= 0) {
324 r->hi = t;
325 r->lo = a.lo;
326 return;
327 }
328 r->hi = t >> b;
329 r->lo = (t << (32-b)) | (a.lo >> b);
330 }
331
332 void
_rshlv(Vlong * r,Vlong a,int b)333 _rshlv(Vlong *r, Vlong a, int b)
334 {
335 ulong t;
336
337 t = a.hi;
338 if(b >= 32) {
339 r->hi = 0;
340 if(b >= 64) {
341 /* this is illegal re C standard */
342 r->lo = 0;
343 return;
344 }
345 r->lo = t >> (b-32);
346 return;
347 }
348 if(b <= 0) {
349 r->hi = t;
350 r->lo = a.lo;
351 return;
352 }
353 r->hi = t >> b;
354 r->lo = (t << (32-b)) | (a.lo >> b);
355 }
356
357 void
_lshv(Vlong * r,Vlong a,int b)358 _lshv(Vlong *r, Vlong a, int b)
359 {
360 ulong t;
361
362 t = a.lo;
363 if(b >= 32) {
364 r->lo = 0;
365 if(b >= 64) {
366 /* this is illegal re C standard */
367 r->hi = 0;
368 return;
369 }
370 r->hi = t << (b-32);
371 return;
372 }
373 if(b <= 0) {
374 r->lo = t;
375 r->hi = a.hi;
376 return;
377 }
378 r->lo = t << b;
379 r->hi = (t >> (32-b)) | (a.hi << b);
380 }
381
382 void
_andv(Vlong * r,Vlong a,Vlong b)383 _andv(Vlong *r, Vlong a, Vlong b)
384 {
385 r->hi = a.hi & b.hi;
386 r->lo = a.lo & b.lo;
387 }
388
389 void
_orv(Vlong * r,Vlong a,Vlong b)390 _orv(Vlong *r, Vlong a, Vlong b)
391 {
392 r->hi = a.hi | b.hi;
393 r->lo = a.lo | b.lo;
394 }
395
396 void
_xorv(Vlong * r,Vlong a,Vlong b)397 _xorv(Vlong *r, Vlong a, Vlong b)
398 {
399 r->hi = a.hi ^ b.hi;
400 r->lo = a.lo ^ b.lo;
401 }
402
403 void
_vpp(Vlong * l,Vlong * r)404 _vpp(Vlong *l, Vlong *r)
405 {
406
407 l->hi = r->hi;
408 l->lo = r->lo;
409 r->lo++;
410 if(r->lo == 0)
411 r->hi++;
412 }
413
414 void
_vmm(Vlong * l,Vlong * r)415 _vmm(Vlong *l, Vlong *r)
416 {
417
418 l->hi = r->hi;
419 l->lo = r->lo;
420 if(r->lo == 0)
421 r->hi--;
422 r->lo--;
423 }
424
425 void
_ppv(Vlong * l,Vlong * r)426 _ppv(Vlong *l, Vlong *r)
427 {
428
429 r->lo++;
430 if(r->lo == 0)
431 r->hi++;
432 l->hi = r->hi;
433 l->lo = r->lo;
434 }
435
436 void
_mmv(Vlong * l,Vlong * r)437 _mmv(Vlong *l, Vlong *r)
438 {
439
440 if(r->lo == 0)
441 r->hi--;
442 r->lo--;
443 l->hi = r->hi;
444 l->lo = r->lo;
445 }
446
447 void
_vasop(Vlong * ret,void * lv,void fn (Vlong *,Vlong,Vlong),int type,Vlong rv)448 _vasop(Vlong *ret, void *lv, void fn(Vlong*, Vlong, Vlong), int type, Vlong rv)
449 {
450 Vlong t, u;
451
452 u.lo = 0;
453 u.hi = 0;
454 switch(type) {
455 default:
456 abort();
457 break;
458
459 case 1: /* schar */
460 t.lo = *(schar*)lv;
461 t.hi = t.lo >> 31;
462 fn(&u, t, rv);
463 *(schar*)lv = u.lo;
464 break;
465
466 case 2: /* uchar */
467 t.lo = *(uchar*)lv;
468 t.hi = 0;
469 fn(&u, t, rv);
470 *(uchar*)lv = u.lo;
471 break;
472
473 case 3: /* short */
474 t.lo = *(short*)lv;
475 t.hi = t.lo >> 31;
476 fn(&u, t, rv);
477 *(short*)lv = u.lo;
478 break;
479
480 case 4: /* ushort */
481 t.lo = *(ushort*)lv;
482 t.hi = 0;
483 fn(&u, t, rv);
484 *(ushort*)lv = u.lo;
485 break;
486
487 case 9: /* int */
488 t.lo = *(int*)lv;
489 t.hi = t.lo >> 31;
490 fn(&u, t, rv);
491 *(int*)lv = u.lo;
492 break;
493
494 case 10: /* uint */
495 t.lo = *(uint*)lv;
496 t.hi = 0;
497 fn(&u, t, rv);
498 *(uint*)lv = u.lo;
499 break;
500
501 case 5: /* long */
502 t.lo = *(long*)lv;
503 t.hi = t.lo >> 31;
504 fn(&u, t, rv);
505 *(long*)lv = u.lo;
506 break;
507
508 case 6: /* ulong */
509 t.lo = *(ulong*)lv;
510 t.hi = 0;
511 fn(&u, t, rv);
512 *(ulong*)lv = u.lo;
513 break;
514
515 case 7: /* vlong */
516 case 8: /* uvlong */
517 fn(&u, *(Vlong*)lv, rv);
518 *(Vlong*)lv = u;
519 break;
520 }
521 *ret = u;
522 }
523
524 void
_p2v(Vlong * ret,void * p)525 _p2v(Vlong *ret, void *p)
526 {
527 long t;
528
529 t = (ulong)p;
530 ret->lo = t;
531 ret->hi = 0;
532 }
533
534 void
_sl2v(Vlong * ret,long sl)535 _sl2v(Vlong *ret, long sl)
536 {
537 long t;
538
539 t = sl;
540 ret->lo = t;
541 ret->hi = t >> 31;
542 }
543
544 void
_ul2v(Vlong * ret,ulong ul)545 _ul2v(Vlong *ret, ulong ul)
546 {
547 long t;
548
549 t = ul;
550 ret->lo = t;
551 ret->hi = 0;
552 }
553
554 void
_si2v(Vlong * ret,int si)555 _si2v(Vlong *ret, int si)
556 {
557 long t;
558
559 t = si;
560 ret->lo = t;
561 ret->hi = t >> 31;
562 }
563
564 void
_ui2v(Vlong * ret,uint ui)565 _ui2v(Vlong *ret, uint ui)
566 {
567 long t;
568
569 t = ui;
570 ret->lo = t;
571 ret->hi = 0;
572 }
573
574 void
_sh2v(Vlong * ret,long sh)575 _sh2v(Vlong *ret, long sh)
576 {
577 long t;
578
579 t = (sh << 16) >> 16;
580 ret->lo = t;
581 ret->hi = t >> 31;
582 }
583
584 void
_uh2v(Vlong * ret,ulong ul)585 _uh2v(Vlong *ret, ulong ul)
586 {
587 long t;
588
589 t = ul & 0xffff;
590 ret->lo = t;
591 ret->hi = 0;
592 }
593
594 void
_sc2v(Vlong * ret,long uc)595 _sc2v(Vlong *ret, long uc)
596 {
597 long t;
598
599 t = (uc << 24) >> 24;
600 ret->lo = t;
601 ret->hi = t >> 31;
602 }
603
604 void
_uc2v(Vlong * ret,ulong ul)605 _uc2v(Vlong *ret, ulong ul)
606 {
607 long t;
608
609 t = ul & 0xff;
610 ret->lo = t;
611 ret->hi = 0;
612 }
613
614 long
_v2sc(Vlong rv)615 _v2sc(Vlong rv)
616 {
617 long t;
618
619 t = rv.lo & 0xff;
620 return (t << 24) >> 24;
621 }
622
623 long
_v2uc(Vlong rv)624 _v2uc(Vlong rv)
625 {
626
627 return rv.lo & 0xff;
628 }
629
630 long
_v2sh(Vlong rv)631 _v2sh(Vlong rv)
632 {
633 long t;
634
635 t = rv.lo & 0xffff;
636 return (t << 16) >> 16;
637 }
638
639 long
_v2uh(Vlong rv)640 _v2uh(Vlong rv)
641 {
642
643 return rv.lo & 0xffff;
644 }
645
646 long
_v2sl(Vlong rv)647 _v2sl(Vlong rv)
648 {
649
650 return rv.lo;
651 }
652
653 long
_v2ul(Vlong rv)654 _v2ul(Vlong rv)
655 {
656
657 return rv.lo;
658 }
659
660 long
_v2si(Vlong rv)661 _v2si(Vlong rv)
662 {
663
664 return rv.lo;
665 }
666
667 long
_v2ui(Vlong rv)668 _v2ui(Vlong rv)
669 {
670
671 return rv.lo;
672 }
673
674 int
_testv(Vlong rv)675 _testv(Vlong rv)
676 {
677 return rv.lo || rv.hi;
678 }
679
680 int
_eqv(Vlong lv,Vlong rv)681 _eqv(Vlong lv, Vlong rv)
682 {
683 return lv.lo == rv.lo && lv.hi == rv.hi;
684 }
685
686 int
_nev(Vlong lv,Vlong rv)687 _nev(Vlong lv, Vlong rv)
688 {
689 return lv.lo != rv.lo || lv.hi != rv.hi;
690 }
691
692 int
_ltv(Vlong lv,Vlong rv)693 _ltv(Vlong lv, Vlong rv)
694 {
695 return (long)lv.hi < (long)rv.hi ||
696 (lv.hi == rv.hi && lv.lo < rv.lo);
697 }
698
699 int
_lev(Vlong lv,Vlong rv)700 _lev(Vlong lv, Vlong rv)
701 {
702 return (long)lv.hi < (long)rv.hi ||
703 (lv.hi == rv.hi && lv.lo <= rv.lo);
704 }
705
706 int
_gtv(Vlong lv,Vlong rv)707 _gtv(Vlong lv, Vlong rv)
708 {
709 return (long)lv.hi > (long)rv.hi ||
710 (lv.hi == rv.hi && lv.lo > rv.lo);
711 }
712
713 int
_gev(Vlong lv,Vlong rv)714 _gev(Vlong lv, Vlong rv)
715 {
716 return (long)lv.hi > (long)rv.hi ||
717 (lv.hi == rv.hi && lv.lo >= rv.lo);
718 }
719
720 int
_lov(Vlong lv,Vlong rv)721 _lov(Vlong lv, Vlong rv)
722 {
723 return lv.hi < rv.hi ||
724 (lv.hi == rv.hi && lv.lo < rv.lo);
725 }
726
727 int
_lsv(Vlong lv,Vlong rv)728 _lsv(Vlong lv, Vlong rv)
729 {
730 return lv.hi < rv.hi ||
731 (lv.hi == rv.hi && lv.lo <= rv.lo);
732 }
733
734 int
_hiv(Vlong lv,Vlong rv)735 _hiv(Vlong lv, Vlong rv)
736 {
737 return lv.hi > rv.hi ||
738 (lv.hi == rv.hi && lv.lo > rv.lo);
739 }
740
741 int
_hsv(Vlong lv,Vlong rv)742 _hsv(Vlong lv, Vlong rv)
743 {
744 return lv.hi > rv.hi ||
745 (lv.hi == rv.hi && lv.lo >= rv.lo);
746 }
747