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