1: /*_ vec.c Mon Oct 31 1994 */
2: /* Copyright (C) 1986-2000 by Digital Mars */
3: /* Written by Walter Bright */
4: /* Bit vector package */
5:
6: #include <stdio.h>
7: #include <string.h>
8: #ifndef assert
9: #include <assert.h>
10: #endif
11: #include "vec.h"
12: #include "mem.h"
13:
14: static int vec_count; /* # of vectors allocated */
15: static int vec_initcount = 0; /* # of times package is initialized */
16:
17: #define VECMAX 20
18: static vec_t vecfreelist[VECMAX];
19:
20: #if 1
21: #define MASK(b) (1 << ((b) & VECMASK))
22: #else
23: #define MASK(b) bmask[(b) & VECMASK]
24: static unsigned bmask[VECMASK + 1] =
25: {
26: 1,2,4,8,0x10,0x20,0x40,0x80,
27: 0x100,0x200,0x400,0x800,0x1000,0x2000,0x4000,0x8000,
28: #if __INTSIZE == 4
29: 0x10000,0x20000,0x40000,0x80000,0x100000,0x200000,0x400000,0x800000,
30: 0x1000000,0x2000000,0x4000000,0x8000000,
31: 0x10000000,0x20000000,0x40000000,0x80000000
32: #endif
33: };
34: #endif
35:
36: /**************************
37: * Initialize package.
38: */
39:
40: void vec_init()
41: {
42: assert(sizeof(vec_base_t)==2&&VECSHIFT==4||sizeof(vec_base_t)==4&&VECSHIFT== 5);
43: if (vec_initcount++ == 0)
44: vec_count = 0;
45: }
46:
47: /**************************
48: * Terminate package.
49: */
50:
51: void vec_term()
52: {
53: if (--vec_initcount == 0)
54: {
55:
56: #ifdef DEBUG
57: if (vec_count != 0)
58: {
59: printf("vec_count = %d\n",vec_count);
60: assert(0);
61: }
62: #else
63: assert(vec_count == 0);
64: #endif
65: #if TERMCODE
66: int i;
67: for (i = 0; i < VECMAX; i++)
68: { void **v;
69: void **vn;
70:
71: for (v = (void **)vecfreelist[i]; v; v = vn)
72: {
73: vn = (void **)(*v);
74: mem_free(v);
75: }
76: vecfreelist[i] = NULL;
77: }
78: #endif
79: }
80: }
81:
82: /********************************
83: * Allocate a vector given # of bits in it.
84: * Clear the vector.
85: */
86:
87: vec_t vec_calloc(unsigned numbits)
88: { vec_t v;
89: int dim;
90:
91: if (numbits == 0)
92: return (vec_t) NULL;
93: dim = (numbits + (VECBITS - 1)) >> VECSHIFT;
94: if (dim < VECMAX && (v = vecfreelist[dim]) != NULL)
95: {
96: vecfreelist[dim] = *(vec_t *)v;
97: v += 2;
98: switch (dim)
99: {
100: case 5: v[4] = 0;
101: case 4: v[3] = 0;
102: case 3: v[2] = 0;
103: case 2: v[1] = 0;
104: case 1: v[0] = 0;
105: break;
106: default: memset(v,0,dim * sizeof(vec_base_t));
107: break;
108: }
109: goto L1;
110: }
111: else
112: {
113: v = (vec_t) mem_calloc((dim + 2) * sizeof(vec_base_t));
114: }
115: if (v)
116: {
117: v += 2;
118: L1:
119: vec_dim(v) = dim;
120: vec_numbits(v) = numbits;
121: /*printf("vec_calloc(%d): v = %p vec_numbits = %d vec_dim = %d\n",
122: numbits,v,vec_numbits(v),vec_dim(v));*/
123: vec_count++;
124: }
125: return v;
126: }
127:
128: /********************************
129: * Allocate copy of existing vector.
130: */
131:
132: vec_t vec_clone(vec_t v)
133: { vec_t vc;
134: int dim;
135: unsigned nbytes;
136:
137: if (v)
138: { dim = vec_dim(v);
139: nbytes = (dim + 2) * sizeof(vec_base_t);
140: if (dim < VECMAX && (vc = vecfreelist[dim]) != NULL)
141: {
142: vecfreelist[dim] = *(vec_t *)vc;
143: goto L1;
144: }
145: else
146: {
147: vc = (vec_t) mem_calloc(nbytes);
148: }
149: if (vc)
150: {
151: L1:
152: memcpy(vc,v - 2,nbytes);
153: vec_count++;
154: v = vc + 2;
155: }
156: else
157: v = NULL;
158: }
159: return v;
160: }
161:
162: /**************************
163: * Free a vector.
164: */
165:
166: void vec_free(vec_t v)
167: {
168: /*printf("vec_free(%p)\n",v);*/
169: if (v)
170: { int dim = vec_dim(v);
171:
172: v -= 2;
173: if (dim < VECMAX)
174: {
175: *(vec_t *)v = vecfreelist[dim];
176: vecfreelist[dim] = v;
177: }
178: else
179: mem_free(v);
180: vec_count--;
181: }
182: }
183:
184: /**************************
185: * Realloc a vector to have numbits bits in it.
186: * Extra bits are set to 0.
187: */
188:
189: vec_t vec_realloc(vec_t v,unsigned numbits)
190: { vec_t newv;
191: unsigned vbits;
192:
193: /*printf("vec_realloc(%p,%d)\n",v,numbits);*/
194: if (!v)
195: return vec_calloc(numbits);
196: if (!numbits)
197: { vec_free(v);
198: return NULL;
199: }
200: vbits = vec_numbits(v);
201: if (numbits == vbits)
202: return v;
203: newv = vec_calloc(numbits);
204: if (newv)
205: { unsigned nbytes;
206:
207: nbytes = (vec_dim(v) < vec_dim(newv)) ? vec_dim(v) : vec_dim(newv);
208: memcpy(newv,v,nbytes * sizeof(vec_base_t));
209: vec_clearextrabits(newv);
210: }
211: vec_free(v);
212: return newv;
213: }
214:
215: /**************************
216: * Set bit b in vector v.
217: */
218:
219: #ifndef vec_setbit
220:
221: #if _M_I86 && __INTSIZE == 4 && __SC__
222: __declspec(naked) void __pascal vec_setbit(unsigned b,vec_t v)
223: {
224: _asm
225: {
226: mov EAX,b-4[ESP]
227: mov ECX,v-4[ESP]
228: bts [ECX],EAX
229: ret 8
230: }
231: }
232: #else
233: void vec_setbit(unsigned b,vec_t v)
234: {
235: #ifdef DEBUG
236: if (!(v && b < vec_numbits(v)))
237: printf("vec_setbit(v = %p,b = %d): numbits = %d dim = %d\n",
238: v,b,v ? vec_numbits(v) : 0, v ? vec_dim(v) : 0);
239: #endif
240: assert(v && b < vec_numbits(v));
241: *(v + (b >> VECSHIFT)) |= MASK(b);
242: }
243: #endif
244:
245: #endif
246:
247: /**************************
248: * Clear bit b in vector v.
249: */
250:
251: #ifndef vec_clearbit
252:
253: #if _M_I86 && __INTSIZE == 4 && __SC__
254: __declspec(naked) void __pascal vec_clearbit(unsigned b,vec_t v)
255: {
256: _asm
257: {
258: mov EAX,b-4[ESP]
259: mov ECX,v-4[ESP]
260: btr [ECX],EAX
261: ret 8
262: }
263: }
264: #else
265: void vec_clearbit(unsigned b,vec_t v)
266: {
267: assert(v && b < vec_numbits(v));
268: *(v + (b >> VECSHIFT)) &= ~MASK(b);
269: }
270: #endif
271:
272: #endif
273:
274: /**************************
275: * Test bit b in vector v.
276: */
277:
278: #ifndef vec_testbit
279:
280: #if _M_I86 && __INTSIZE == 4 && __SC__
281: __declspec(naked) int __pascal vec_testbit(unsigned b,vec_t v)
282: {
283: _asm
284: {
285: mov EAX,v-4[ESP]
286: mov ECX,b-4[ESP]
287: test EAX,EAX
288: jz L1
289: bt [EAX],ECX
290: sbb EAX,EAX
291: L1: ret 8
292: }
293: }
294: #else
295: int vec_testbit(unsigned b,vec_t v)
296: {
297: if (!v)
298: return 0;
299: #ifdef DEBUG
300: if (b >= vec_numbits(v))
301: { printf("vec_testbit(v = %p,b = %d): numbits = %d dim = %d\n",
302: v,b,vec_numbits(v),vec_dim(v));
303: b = (unsigned)-1;
304: }
305: #endif
306: assert(b < vec_numbits(v));
307: #if __I86__ >= 3 && __SC__
308: _asm
309: {
310: #if __INTSIZE == 4
311: mov EAX,b
312: mov ECX,v
313: bt [ECX],EAX
314: sbb EAX,EAX
315: #elif __COMPACT__ || __LARGE__ || __VCM__
316: mov AX,b
317: les BX,v
318: bt ES:[BX],AX
319: sbb AX,AX
320: #else
321: mov AX,b
322: mov CX,v
323: bt [CX],AX
324: sbb AX,AX
325: #endif
326: }
327: #ifdef DEBUG
328: { int x = _AX;
329: assert((x != 0) == ((*(v + (b >> VECSHIFT)) & MASK(b)) != 0));
330: }
331: #endif
332: #else
333: return *(v + (b >> VECSHIFT)) & MASK(b);
334: #endif
335: }
336: #endif
337:
338: #endif
339:
340: /********************************
341: * Find first set bit starting from b in vector v.
342: * If no bit is found, return vec_numbits(v).
343: */
344:
345: unsigned vec_index(unsigned b,vec_t vec)
346: { register unsigned starv;
347: register vec_t v,vtop;
348: unsigned bit;
349:
350: if (!vec)
351: return 0;
352: v = vec;
353: if (b < vec_numbits(v))
354: { vtop = &vec[vec_dim(v)];
355: bit = b & VECMASK;
356: if (bit != b) /* if not starting in first word */
357: v += b >> VECSHIFT;
358: starv = *v >> bit;
359: while (1)
360: {
361: while (starv)
362: { if (starv & 1)
363: return b;
364: b++;
365: starv >>= 1;
366: }
367: b = (b + VECBITS) & ~VECMASK; /* round up to next word */
368: if (++v >= vtop)
369: break;
370: starv = *v;
371: }
372: }
373: return vec_numbits(vec);
374: }
375:
376: /********************************
377: * Compute v1 &= v2.
378: */
379:
380: void vec_andass(vec_t v1,vec_t v2)
381: { vec_t vtop;
382:
383: if (v1)
384: {
385: assert(v2);
386: assert(vec_numbits(v1)==vec_numbits(v2));
387: vtop = &v1[vec_dim(v1)];
388: for (; v1 < vtop; v1++,v2++)
389: *v1 &= *v2;
390: }
391: else
392: assert(!v2);
393: }
394:
395: /********************************
396: * Compute v1 = v2 & v3.
397: */
398:
399: void vec_and(vec_t v1,vec_t v2,vec_t v3)
400: { vec_t vtop;
401:
402: if (v1)
403: {
404: assert(v2 && v3);
405: assert(vec_numbits(v1)==vec_numbits(v2) && vec_numbits(v1)==vec_numbits(v3));
406: vtop = &v1[vec_dim(v1)];
407: for (; v1 < vtop; v1++,v2++,v3++)
408: *v1 = *v2 & *v3;
409: }
410: else
411: assert(!v2 && !v3);
412: }
413:
414: /********************************
415: * Compute v1 ^= v2.
416: */
417:
418: void vec_xorass(vec_t v1,vec_t v2)
419: { vec_t vtop;
420:
421: if (v1)
422: {
423: assert(v2);
424: assert(vec_numbits(v1)==vec_numbits(v2));
425: vtop = &v1[vec_dim(v1)];
426: for (; v1 < vtop; v1++,v2++)
427: *v1 ^= *v2;
428: }
429: else
430: assert(!v2);
431: }
432:
433: /********************************
434: * Compute v1 = v2 ^ v3.
435: */
436:
437: void vec_xor(vec_t v1,vec_t v2,vec_t v3)
438: { vec_t vtop;
439:
440: if (v1)
441: {
442: assert(v2 && v3);
443: assert(vec_numbits(v1)==vec_numbits(v2) && vec_numbits(v1)==vec_numbits(v3));
444: vtop = &v1[vec_dim(v1)];
445: for (; v1 < vtop; v1++,v2++,v3++)
446: *v1 = *v2 ^ *v3;
447: }
448: else
449: assert(!v2 && !v3);
450: }
451:
452: /********************************
453: * Compute v1 |= v2.
454: */
455:
456: void vec_orass(vec_t v1,vec_t v2)
457: { vec_t vtop;
458:
459: if (v1)
460: {
461: #ifdef DEBUG
462: assert(v2);
463: assert(vec_numbits(v1)==vec_numbits(v2));
464: #endif
465: vtop = &v1[vec_dim(v1)];
466: #if __INTSIZE == 2 && __I86__ && (__COMPACT__ || __LARGE__ || __VCM__)
467: _asm
468: {
469: push DS
470: lds SI,v2
471: les DI,v1
472: mov CX,word ptr vtop
473: cmp CX,DI
474: jz L1
475: L2: mov AX,[SI]
476: add SI,2
477: or ES:[DI],AX
478: add DI,2
479: cmp DI,CX
480: jb L2
481: L1: pop DS
482: #if __SC__ <= 0x610
483: jmp Lret
484: #endif
485: }
486: #else
487: for (; v1 < vtop; v1++,v2++)
488: *v1 |= *v2;
489: #endif
490: }
491: else
492: assert(!v2);
493: Lret: ;
warning C4102: 'Lret' : unreferenced label
494: }
495:
496: /********************************
497: * Compute v1 = v2 | v3.
498: */
499:
500: void vec_or(vec_t v1,vec_t v2,vec_t v3)
501: { vec_t vtop;
502:
503: if (v1)
504: {
505: assert(v2 && v3);
506: assert(vec_numbits(v1)==vec_numbits(v2) && vec_numbits(v1)==vec_numbits(v3));
507: vtop = &v1[vec_dim(v1)];
508: for (; v1 < vtop; v1++,v2++,v3++)
509: *v1 = *v2 | *v3;
510: }
511: else
512: assert(!v2 && !v3);
513: }
514:
515: /********************************
516: * Compute v1 -= v2.
517: */
518:
519: void vec_subass(vec_t v1,vec_t v2)
520: { vec_t vtop;
521:
522: if (v1)
523: {
524: assert(v2);
525: assert(vec_numbits(v1)==vec_numbits(v2));
526: vtop = &v1[vec_dim(v1)];
527: for (; v1 < vtop; v1++,v2++)
528: *v1 &= ~*v2;
529: }
530: else
531: assert(!v2);
532: }
533:
534: /********************************
535: * Compute v1 = v2 - v3.
536: */
537:
538: void vec_sub(vec_t v1,vec_t v2,vec_t v3)
539: { vec_t vtop;
540:
541: if (v1)
542: {
543: assert(v2 && v3);
544: assert(vec_numbits(v1)==vec_numbits(v2) && vec_numbits(v1)==vec_numbits(v3));
545: vtop = &v1[vec_dim(v1)];
546: for (; v1 < vtop; v1++,v2++,v3++)
547: *v1 = *v2 & ~*v3;
548: }
549: else
550: assert(!v2 && !v3);
551: }
552:
553: /****************
554: * Clear vector.
555: */
556:
557: void vec_clear(vec_t v)
558: {
559: if (v)
560: memset(v,0,sizeof(v[0]) * vec_dim(v));
561: }
562:
563: /****************
564: * Set vector.
565: */
566:
567: void vec_set(vec_t v)
568: {
569: if (v)
570: { memset(v,~0,sizeof(v[0]) * vec_dim(v));
571: vec_clearextrabits(v);
572: }
573: }
574:
575: /***************
576: * Copy vector.
577: */
578:
579: void vec_copy(vec_t to,vec_t from)
580: {
581: if (to != from)
582: {
583: #ifdef DEBUG
584: if (!(to && from && vec_numbits(to) == vec_numbits(from)))
585: printf("to = x%lx, from = x%lx, numbits(to) = %d, numbits(from) = %d\n",
586: (long)to,(long)from,to ? vec_numbits(to) : 0, from ? vec_numbits(from): 0);
587: #endif
588: assert(to && from && vec_numbits(to) == vec_numbits(from));
589: memcpy(to,from,sizeof(to[0]) * vec_dim(to));
590: }
591: }
592:
593: /****************
594: * Return 1 if vectors are equal.
595: */
596:
597: int vec_equal(vec_t v1,vec_t v2)
598: {
599: if (v1 == v2)
600: return 1;
601: assert(v1 && v2 && vec_numbits(v1) == vec_numbits(v2));
602: return !memcmp(v1,v2,sizeof(v1[0]) * vec_dim(v1));
603: }
604:
605: /********************************
606: * Return 1 if (v1 & v2) == 0
607: */
608:
609: int vec_disjoint(vec_t v1,vec_t v2)
610: { vec_t vtop;
611:
612: assert(v1 && v2);
613: assert(vec_numbits(v1)==vec_numbits(v2));
614: vtop = &v1[vec_dim(v1)];
615: for (; v1 < vtop; v1++,v2++)
616: if (*v1 & *v2)
617: return 0;
618: return 1;
619: }
620:
621: /*********************
622: * Clear any extra bits in vector.
623: */
624:
625: void vec_clearextrabits(vec_t v)
626: { unsigned n;
627:
628: assert(v);
629: n = vec_numbits(v);
630: if (n & VECMASK)
631: v[vec_dim(v) - 1] &= MASK(n) - 1;
632: }
633:
634: /******************
635: * Write out vector.
636: */
637:
638: void vec_println(vec_t v)
639: {
640: #ifdef DEBUG
641: vec_print(v);
642: fputc('\n',stdout);
643: #endif
644: }
645:
646: void vec_print(vec_t v)
647: { register unsigned i;
warning C4101: 'i' : unreferenced local variable
648:
649: #ifdef DEBUG
650: printf(" Vec %p, numbits %d dim %d",v,vec_numbits(v),vec_dim(v));
651: if (v)
652: { fputc('\t',stdout);
653: for (i = 0; i < vec_numbits(v); i++)
654: fputc((vec_testbit(i,v)) ? '1' : '0',stdout);
655: }
656: #endif
657: }
658: