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
_vasaddd(Vlong * ret,Vlong * lv,double rv)448 _vasaddd(Vlong *ret, Vlong *lv, double rv)
449 {
450 _d2v(lv, _v2d(*lv)+rv);
451 *ret = *lv;
452 }
453
454 void
_vassubd(Vlong * ret,Vlong * lv,double rv)455 _vassubd(Vlong *ret, Vlong *lv, double rv)
456 {
457 _d2v(lv, _v2d(*lv)-rv);
458 *ret = *lv;
459 }
460
461 void
_vasmuld(Vlong * ret,Vlong * lv,double rv)462 _vasmuld(Vlong *ret, Vlong *lv, double rv)
463 {
464 _d2v(lv, _v2d(*lv)*rv);
465 *ret = *lv;
466 }
467
468 void
_vasdivd(Vlong * ret,Vlong * lv,double rv)469 _vasdivd(Vlong *ret, Vlong *lv, double rv)
470 {
471 _d2v(lv, _v2d(*lv)/rv);
472 *ret = *lv;
473 }
474
475 void
_vasop(Vlong * ret,void * lv,void fn (Vlong *,Vlong,Vlong),int type,Vlong rv)476 _vasop(Vlong *ret, void *lv, void fn(Vlong*, Vlong, Vlong), int type, Vlong rv)
477 {
478 Vlong t, u;
479
480 u.lo = 0;
481 u.hi = 0;
482 switch(type) {
483 default:
484 abort();
485 break;
486
487 case 1: /* schar */
488 t.lo = *(schar*)lv;
489 t.hi = t.lo >> 31;
490 fn(&u, t, rv);
491 *(schar*)lv = u.lo;
492 break;
493
494 case 2: /* uchar */
495 t.lo = *(uchar*)lv;
496 t.hi = 0;
497 fn(&u, t, rv);
498 *(uchar*)lv = u.lo;
499 break;
500
501 case 3: /* short */
502 t.lo = *(short*)lv;
503 t.hi = t.lo >> 31;
504 fn(&u, t, rv);
505 *(short*)lv = u.lo;
506 break;
507
508 case 4: /* ushort */
509 t.lo = *(ushort*)lv;
510 t.hi = 0;
511 fn(&u, t, rv);
512 *(ushort*)lv = u.lo;
513 break;
514
515 case 9: /* int */
516 t.lo = *(int*)lv;
517 t.hi = t.lo >> 31;
518 fn(&u, t, rv);
519 *(int*)lv = u.lo;
520 break;
521
522 case 10: /* uint */
523 t.lo = *(uint*)lv;
524 t.hi = 0;
525 fn(&u, t, rv);
526 *(uint*)lv = u.lo;
527 break;
528
529 case 5: /* long */
530 t.lo = *(long*)lv;
531 t.hi = t.lo >> 31;
532 fn(&u, t, rv);
533 *(long*)lv = u.lo;
534 break;
535
536 case 6: /* ulong */
537 t.lo = *(ulong*)lv;
538 t.hi = 0;
539 fn(&u, t, rv);
540 *(ulong*)lv = u.lo;
541 break;
542
543 case 7: /* vlong */
544 case 8: /* uvlong */
545 fn(&u, *(Vlong*)lv, rv);
546 *(Vlong*)lv = u;
547 break;
548 }
549 *ret = u;
550 }
551
552 void
_p2v(Vlong * ret,void * p)553 _p2v(Vlong *ret, void *p)
554 {
555 long t;
556
557 t = (ulong)p;
558 ret->lo = t;
559 ret->hi = 0;
560 }
561
562 void
_sl2v(Vlong * ret,long sl)563 _sl2v(Vlong *ret, long sl)
564 {
565 long t;
566
567 t = sl;
568 ret->lo = t;
569 ret->hi = t >> 31;
570 }
571
572 void
_ul2v(Vlong * ret,ulong ul)573 _ul2v(Vlong *ret, ulong ul)
574 {
575 long t;
576
577 t = ul;
578 ret->lo = t;
579 ret->hi = 0;
580 }
581
582 void
_si2v(Vlong * ret,int si)583 _si2v(Vlong *ret, int si)
584 {
585 long t;
586
587 t = si;
588 ret->lo = t;
589 ret->hi = t >> 31;
590 }
591
592 void
_ui2v(Vlong * ret,uint ui)593 _ui2v(Vlong *ret, uint ui)
594 {
595 long t;
596
597 t = ui;
598 ret->lo = t;
599 ret->hi = 0;
600 }
601
602 void
_sh2v(Vlong * ret,long sh)603 _sh2v(Vlong *ret, long sh)
604 {
605 long t;
606
607 t = (sh << 16) >> 16;
608 ret->lo = t;
609 ret->hi = t >> 31;
610 }
611
612 void
_uh2v(Vlong * ret,ulong ul)613 _uh2v(Vlong *ret, ulong ul)
614 {
615 long t;
616
617 t = ul & 0xffff;
618 ret->lo = t;
619 ret->hi = 0;
620 }
621
622 void
_sc2v(Vlong * ret,long uc)623 _sc2v(Vlong *ret, long uc)
624 {
625 long t;
626
627 t = (uc << 24) >> 24;
628 ret->lo = t;
629 ret->hi = t >> 31;
630 }
631
632 void
_uc2v(Vlong * ret,ulong ul)633 _uc2v(Vlong *ret, ulong ul)
634 {
635 long t;
636
637 t = ul & 0xff;
638 ret->lo = t;
639 ret->hi = 0;
640 }
641
642 long
_v2sc(Vlong rv)643 _v2sc(Vlong rv)
644 {
645 long t;
646
647 t = rv.lo & 0xff;
648 return (t << 24) >> 24;
649 }
650
651 long
_v2uc(Vlong rv)652 _v2uc(Vlong rv)
653 {
654
655 return rv.lo & 0xff;
656 }
657
658 long
_v2sh(Vlong rv)659 _v2sh(Vlong rv)
660 {
661 long t;
662
663 t = rv.lo & 0xffff;
664 return (t << 16) >> 16;
665 }
666
667 long
_v2uh(Vlong rv)668 _v2uh(Vlong rv)
669 {
670
671 return rv.lo & 0xffff;
672 }
673
674 long
_v2sl(Vlong rv)675 _v2sl(Vlong rv)
676 {
677
678 return rv.lo;
679 }
680
681 long
_v2ul(Vlong rv)682 _v2ul(Vlong rv)
683 {
684
685 return rv.lo;
686 }
687
688 long
_v2si(Vlong rv)689 _v2si(Vlong rv)
690 {
691
692 return rv.lo;
693 }
694
695 long
_v2ui(Vlong rv)696 _v2ui(Vlong rv)
697 {
698
699 return rv.lo;
700 }
701
702 int
_testv(Vlong rv)703 _testv(Vlong rv)
704 {
705 return rv.lo || rv.hi;
706 }
707
708 int
_eqv(Vlong lv,Vlong rv)709 _eqv(Vlong lv, Vlong rv)
710 {
711 return lv.lo == rv.lo && lv.hi == rv.hi;
712 }
713
714 int
_nev(Vlong lv,Vlong rv)715 _nev(Vlong lv, Vlong rv)
716 {
717 return lv.lo != rv.lo || lv.hi != rv.hi;
718 }
719
720 int
_ltv(Vlong lv,Vlong rv)721 _ltv(Vlong lv, Vlong rv)
722 {
723 return (long)lv.hi < (long)rv.hi ||
724 (lv.hi == rv.hi && lv.lo < rv.lo);
725 }
726
727 int
_lev(Vlong lv,Vlong rv)728 _lev(Vlong lv, Vlong rv)
729 {
730 return (long)lv.hi < (long)rv.hi ||
731 (lv.hi == rv.hi && lv.lo <= rv.lo);
732 }
733
734 int
_gtv(Vlong lv,Vlong rv)735 _gtv(Vlong lv, Vlong rv)
736 {
737 return (long)lv.hi > (long)rv.hi ||
738 (lv.hi == rv.hi && lv.lo > rv.lo);
739 }
740
741 int
_gev(Vlong lv,Vlong rv)742 _gev(Vlong lv, Vlong rv)
743 {
744 return (long)lv.hi > (long)rv.hi ||
745 (lv.hi == rv.hi && lv.lo >= rv.lo);
746 }
747
748 int
_lov(Vlong lv,Vlong rv)749 _lov(Vlong lv, Vlong rv)
750 {
751 return lv.hi < rv.hi ||
752 (lv.hi == rv.hi && lv.lo < rv.lo);
753 }
754
755 int
_lsv(Vlong lv,Vlong rv)756 _lsv(Vlong lv, Vlong rv)
757 {
758 return lv.hi < rv.hi ||
759 (lv.hi == rv.hi && lv.lo <= rv.lo);
760 }
761
762 int
_hiv(Vlong lv,Vlong rv)763 _hiv(Vlong lv, Vlong rv)
764 {
765 return lv.hi > rv.hi ||
766 (lv.hi == rv.hi && lv.lo > rv.lo);
767 }
768
769 int
_hsv(Vlong lv,Vlong rv)770 _hsv(Vlong lv, Vlong rv)
771 {
772 return lv.hi > rv.hi ||
773 (lv.hi == rv.hi && lv.lo >= rv.lo);
774 }
775