1 /** 2 * Compiler implementation of the 3 * $(LINK2 http://www.dlang.org, D programming language). 4 * 5 * Simple bit vector implementation. 6 * 7 * Copyright: Copyright (C) 2013-2020 by The D Language Foundation, All Rights Reserved 8 * Authors: $(LINK2 http://www.digitalmars.com, Walter Bright) 9 * License: $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0) 10 * Source: $(LINK2 https://github.com/dlang/dmd/blob/master/src/dmd/backend/dvec.d, backend/dvec.d) 11 */ 12 13 module dmd.backend.dvec; 14 15 import core.stdc.stdio; 16 import core.stdc.stdlib; 17 import core.stdc..string; 18 19 import core.bitop; 20 21 extern (C): 22 23 nothrow: 24 @nogc: 25 26 alias vec_base_t = size_t; // base type of vector 27 alias vec_t = vec_base_t*; 28 29 enum VECBITS = vec_base_t.sizeof * 8; // # of bits per entry 30 enum VECMASK = VECBITS - 1; // mask for bit position 31 enum VECSHIFT = (VECBITS == 16) ? 4 : (VECBITS == 32 ? 5 : 6); // # of bits in VECMASK 32 33 static assert(vec_base_t.sizeof == 2 && VECSHIFT == 4 || 34 vec_base_t.sizeof == 4 && VECSHIFT == 5 || 35 vec_base_t.sizeof == 8 && VECSHIFT == 6); 36 37 struct VecGlobal 38 { 39 int count; // # of vectors allocated 40 int initcount; // # of times package is initialized 41 vec_t[30] freelist; // free lists indexed by dim 42 43 nothrow: 44 @nogc: 45 46 void initialize() 47 { 48 if (initcount++ == 0) 49 count = 0; 50 } 51 52 void terminate() 53 { 54 if (--initcount == 0) 55 { 56 debug 57 { 58 if (count != 0) 59 { 60 printf("vecGlobal.count = %d\n", count); 61 assert(0); 62 } 63 } 64 else 65 assert(count == 0); 66 67 foreach (size_t i; 0 .. freelist.length) 68 { 69 void **vn; 70 for (void** v = cast(void **)freelist[i]; v; v = vn) 71 { 72 vn = cast(void **)(*v); 73 //mem_free(v); 74 .free(v); 75 } 76 freelist[i] = null; 77 } 78 } 79 } 80 81 vec_t allocate(size_t numbits) 82 { 83 if (numbits == 0) 84 return cast(vec_t) null; 85 const dim = (numbits + (VECBITS - 1)) >> VECSHIFT; 86 vec_t v; 87 if (dim < freelist.length && (v = freelist[dim]) != null) 88 { 89 freelist[dim] = *cast(vec_t *)v; 90 v += 2; 91 switch (dim) 92 { 93 case 5: v[4] = 0; goto case 4; 94 case 4: v[3] = 0; goto case 3; 95 case 3: v[2] = 0; goto case 2; 96 case 2: v[1] = 0; goto case 1; 97 case 1: v[0] = 0; 98 break; 99 default: memset(v,0,dim * vec_base_t.sizeof); 100 break; 101 } 102 goto L1; 103 } 104 else 105 { 106 v = cast(vec_t) calloc(dim + 2, vec_base_t.sizeof); 107 assert(v); 108 } 109 if (v) 110 { 111 v += 2; 112 L1: 113 vec_dim(v) = dim; 114 vec_numbits(v) = numbits; 115 /*printf("vec_calloc(%d): v = %p vec_numbits = %d vec_dim = %d\n", 116 numbits,v,vec_numbits(v),vec_dim(v));*/ 117 count++; 118 } 119 return v; 120 } 121 122 vec_t dup(const vec_t v) 123 { 124 if (!v) 125 return null; 126 127 const dim = vec_dim(v); 128 const nbytes = (dim + 2) * vec_base_t.sizeof; 129 vec_t vc; 130 vec_t result; 131 if (dim < freelist.length && (vc = freelist[dim]) != null) 132 { 133 freelist[dim] = *cast(vec_t *)vc; 134 goto L1; 135 } 136 else 137 { 138 vc = cast(vec_t) calloc(nbytes, 1); 139 assert(vc); 140 } 141 if (vc) 142 { 143 L1: 144 memcpy(vc,v - 2,nbytes); 145 count++; 146 result = vc + 2; 147 } 148 else 149 result = null; 150 return result; 151 } 152 153 void free(vec_t v) 154 { 155 /*printf("vec_free(%p)\n",v);*/ 156 if (v) 157 { 158 const dim = vec_dim(v); 159 v -= 2; 160 if (dim < freelist.length) 161 { 162 *cast(vec_t *)v = freelist[dim]; 163 freelist[dim] = v; 164 } 165 else 166 .free(v); 167 count--; 168 } 169 } 170 171 } 172 173 __gshared VecGlobal vecGlobal; 174 175 private pure vec_base_t MASK(uint b) { return cast(vec_base_t)1 << (b & VECMASK); } 176 177 pure ref inout(vec_base_t) vec_numbits(inout vec_t v) { return v[-1]; } 178 pure ref inout(vec_base_t) vec_dim(inout vec_t v) { return v[-2]; } 179 180 /************************** 181 * Initialize package. 182 */ 183 184 void vec_init() 185 { 186 vecGlobal.initialize(); 187 } 188 189 190 /************************** 191 * Terminate package. 192 */ 193 194 void vec_term() 195 { 196 vecGlobal.terminate(); 197 } 198 199 /******************************** 200 * Allocate a vector given # of bits in it. 201 * Clear the vector. 202 */ 203 204 vec_t vec_calloc(size_t numbits) 205 { 206 return vecGlobal.allocate(numbits); 207 } 208 209 /******************************** 210 * Allocate copy of existing vector. 211 */ 212 213 vec_t vec_clone(const vec_t v) 214 { 215 return vecGlobal.dup(v); 216 } 217 218 /************************** 219 * Free a vector. 220 */ 221 222 void vec_free(vec_t v) 223 { 224 /*printf("vec_free(%p)\n",v);*/ 225 return vecGlobal.free(v); 226 } 227 228 /************************** 229 * Realloc a vector to have numbits bits in it. 230 * Extra bits are set to 0. 231 */ 232 233 vec_t vec_realloc(vec_t v, size_t numbits) 234 { 235 /*printf("vec_realloc(%p,%d)\n",v,numbits);*/ 236 if (!v) 237 return vec_calloc(numbits); 238 if (!numbits) 239 { vec_free(v); 240 return null; 241 } 242 const vbits = vec_numbits(v); 243 if (numbits == vbits) 244 return v; 245 vec_t newv = vec_calloc(numbits); 246 if (newv) 247 { 248 const nbytes = (vec_dim(v) < vec_dim(newv)) ? vec_dim(v) : vec_dim(newv); 249 memcpy(newv,v,nbytes * vec_base_t.sizeof); 250 vec_clearextrabits(newv); 251 } 252 vec_free(v); 253 return newv; 254 } 255 256 /************************** 257 * Set bit b in vector v. 258 */ 259 260 pure 261 void vec_setbit(size_t b, vec_t v) 262 { 263 debug 264 { 265 if (!(v && b < vec_numbits(v))) 266 printf("vec_setbit(v = %p,b = %d): numbits = %d dim = %d\n", 267 v, cast(int) b, cast(int) (v ? vec_numbits(v) : 0), cast(int) (v ? vec_dim(v) : 0)); 268 } 269 assert(v && b < vec_numbits(v)); 270 core.bitop.bts(v, b); 271 } 272 273 /************************** 274 * Clear bit b in vector v. 275 */ 276 277 pure 278 void vec_clearbit(size_t b, vec_t v) 279 { 280 assert(v && b < vec_numbits(v)); 281 core.bitop.btr(v, b); 282 } 283 284 /************************** 285 * Test bit b in vector v. 286 */ 287 288 pure 289 size_t vec_testbit(size_t b, const vec_t v) 290 { 291 if (!v) 292 return 0; 293 debug 294 { 295 if (!(v && b < vec_numbits(v))) 296 printf("vec_setbit(v = %p,b = %d): numbits = %d dim = %d\n", 297 v, cast(int) b, cast(int) (v ? vec_numbits(v) : 0), cast(int) (v ? vec_dim(v) : 0)); 298 } 299 assert(v && b < vec_numbits(v)); 300 return core.bitop.bt(v, b); 301 } 302 303 /******************************** 304 * Find first set bit starting from b in vector v. 305 * If no bit is found, return vec_numbits(v). 306 */ 307 308 pure 309 size_t vec_index(size_t b, const vec_t vec) 310 { 311 if (!vec) 312 return 0; 313 const(vec_base_t)* v = vec; 314 if (b < vec_numbits(v)) 315 { 316 const vtop = &vec[vec_dim(v)]; 317 const bit = b & VECMASK; 318 if (bit != b) // if not starting in first word 319 v += b >> VECSHIFT; 320 size_t starv = *v >> bit; 321 while (1) 322 { 323 while (starv) 324 { 325 if (starv & 1) 326 return b; 327 b++; 328 starv >>= 1; 329 } 330 b = (b + VECBITS) & ~VECMASK; // round up to next word 331 if (++v >= vtop) 332 break; 333 starv = *v; 334 } 335 } 336 return vec_numbits(vec); 337 } 338 339 /******************************** 340 * Compute v1 &= v2. 341 */ 342 343 pure 344 void vec_andass(vec_t v1, const(vec_base_t)* v2) 345 { 346 if (v1) 347 { 348 assert(v2); 349 assert(vec_numbits(v1)==vec_numbits(v2)); 350 const vtop = &v1[vec_dim(v1)]; 351 for (; v1 < vtop; v1++,v2++) 352 *v1 &= *v2; 353 } 354 else 355 assert(!v2); 356 } 357 358 /******************************** 359 * Compute v1 = v2 & v3. 360 */ 361 362 pure 363 void vec_and(vec_t v1, const(vec_base_t)* v2, const(vec_base_t)* v3) 364 { 365 if (v1) 366 { 367 assert(v2 && v3); 368 assert(vec_numbits(v1)==vec_numbits(v2) && vec_numbits(v1)==vec_numbits(v3)); 369 const vtop = &v1[vec_dim(v1)]; 370 for (; v1 < vtop; v1++,v2++,v3++) 371 *v1 = *v2 & *v3; 372 } 373 else 374 assert(!v2 && !v3); 375 } 376 377 /******************************** 378 * Compute v1 ^= v2. 379 */ 380 381 pure 382 void vec_xorass(vec_t v1, const(vec_base_t)* v2) 383 { 384 if (v1) 385 { 386 assert(v2); 387 assert(vec_numbits(v1)==vec_numbits(v2)); 388 const vtop = &v1[vec_dim(v1)]; 389 for (; v1 < vtop; v1++,v2++) 390 *v1 ^= *v2; 391 } 392 else 393 assert(!v2); 394 } 395 396 /******************************** 397 * Compute v1 = v2 ^ v3. 398 */ 399 400 pure 401 void vec_xor(vec_t v1, const(vec_base_t)* v2, const(vec_base_t)* v3) 402 { 403 if (v1) 404 { 405 assert(v2 && v3); 406 assert(vec_numbits(v1)==vec_numbits(v2) && vec_numbits(v1)==vec_numbits(v3)); 407 const vtop = &v1[vec_dim(v1)]; 408 for (; v1 < vtop; v1++,v2++,v3++) 409 *v1 = *v2 ^ *v3; 410 } 411 else 412 assert(!v2 && !v3); 413 } 414 415 /******************************** 416 * Compute v1 |= v2. 417 */ 418 419 pure 420 void vec_orass(vec_t v1, const(vec_base_t)* v2) 421 { 422 if (v1) 423 { 424 debug assert(v2); 425 debug assert(vec_numbits(v1)==vec_numbits(v2)); 426 const vtop = &v1[vec_dim(v1)]; 427 for (; v1 < vtop; v1++,v2++) 428 *v1 |= *v2; 429 } 430 else 431 assert(!v2); 432 } 433 434 /******************************** 435 * Compute v1 = v2 | v3. 436 */ 437 438 pure 439 void vec_or(vec_t v1, const(vec_base_t)* v2, const(vec_base_t)* v3) 440 { 441 if (v1) 442 { 443 assert(v2 && v3); 444 assert(vec_numbits(v1)==vec_numbits(v2) && vec_numbits(v1)==vec_numbits(v3)); 445 const vtop = &v1[vec_dim(v1)]; 446 for (; v1 < vtop; v1++,v2++,v3++) 447 *v1 = *v2 | *v3; 448 } 449 else 450 assert(!v2 && !v3); 451 } 452 453 /******************************** 454 * Compute v1 -= v2. 455 */ 456 457 pure 458 void vec_subass(vec_t v1, const(vec_base_t)* v2) 459 { 460 if (v1) 461 { 462 assert(v2); 463 assert(vec_numbits(v1)==vec_numbits(v2)); 464 const vtop = &v1[vec_dim(v1)]; 465 for (; v1 < vtop; v1++,v2++) 466 *v1 &= ~*v2; 467 } 468 else 469 assert(!v2); 470 } 471 472 /******************************** 473 * Compute v1 = v2 - v3. 474 */ 475 476 pure 477 void vec_sub(vec_t v1, const(vec_base_t)* v2, const(vec_base_t)* v3) 478 { 479 if (v1) 480 { 481 assert(v2 && v3); 482 assert(vec_numbits(v1)==vec_numbits(v2) && vec_numbits(v1)==vec_numbits(v3)); 483 const vtop = &v1[vec_dim(v1)]; 484 for (; v1 < vtop; v1++,v2++,v3++) 485 *v1 = *v2 & ~*v3; 486 } 487 else 488 assert(!v2 && !v3); 489 } 490 491 /**************** 492 * Clear vector. 493 */ 494 495 pure 496 void vec_clear(vec_t v) 497 { 498 if (v) 499 memset(v, 0, v[0].sizeof * vec_dim(v)); 500 } 501 502 /**************** 503 * Set vector. 504 */ 505 506 pure 507 void vec_set(vec_t v) 508 { 509 if (v) 510 { 511 memset(v, ~0, v[0].sizeof * vec_dim(v)); 512 vec_clearextrabits(v); 513 } 514 } 515 516 /*************** 517 * Copy vector. 518 */ 519 520 pure 521 void vec_copy(vec_t to, const vec_t from) 522 { 523 if (to != from) 524 { 525 debug 526 { 527 if (!(to && from && vec_numbits(to) == vec_numbits(from))) 528 printf("to = x%p, from = x%p, numbits(to) = %d, numbits(from) = %d\n", 529 to, from, cast(int) (to ? vec_numbits(to) : 0), 530 cast(int) (from ? vec_numbits(from): 0)); 531 } 532 assert(to && from && vec_numbits(to) == vec_numbits(from)); 533 memcpy(to, from, to[0].sizeof * vec_dim(to)); 534 } 535 } 536 537 /**************** 538 * Return 1 if vectors are equal. 539 */ 540 541 pure 542 int vec_equal(const vec_t v1, const vec_t v2) 543 { 544 if (v1 == v2) 545 return 1; 546 assert(v1 && v2 && vec_numbits(v1) == vec_numbits(v2)); 547 return !memcmp(v1, v2, v1[0].sizeof * vec_dim(v1)); 548 } 549 550 /******************************** 551 * Return 1 if (v1 & v2) == 0 552 */ 553 554 pure 555 int vec_disjoint(const(vec_base_t)* v1, const(vec_base_t)* v2) 556 { 557 assert(v1 && v2); 558 assert(vec_numbits(v1) == vec_numbits(v2)); 559 const vtop = &v1[vec_dim(v1)]; 560 for (; v1 < vtop; v1++,v2++) 561 if (*v1 & *v2) 562 return 0; 563 return 1; 564 } 565 566 /********************* 567 * Clear any extra bits in vector. 568 */ 569 570 pure 571 void vec_clearextrabits(vec_t v) 572 { 573 assert(v); 574 const n = vec_numbits(v); 575 if (n & VECMASK) 576 v[vec_dim(v) - 1] &= MASK(cast(uint)n) - 1; 577 } 578 579 /****************** 580 * Write out vector. 581 */ 582 583 pure 584 void vec_println(const vec_t v) 585 { 586 debug 587 { 588 vec_print(v); 589 fputc('\n',stdout); 590 } 591 } 592 593 pure 594 void vec_print(const vec_t v) 595 { 596 debug 597 { 598 printf(" Vec %p, numbits %d dim %d", v, cast(int) vec_numbits(v), cast(int) vec_dim(v)); 599 if (v) 600 { 601 fputc('\t',stdout); 602 for (size_t i = 0; i < vec_numbits(v); i++) 603 fputc((vec_testbit(i,v)) ? '1' : '0',stdout); 604 } 605 } 606 } 607 608