src/bitmask.cpp

   1 /*
   2  *                          bitmask.c 1.0
   3  *                          -------------
   4  *    Simple and efficient bitmask collision detection routines
   5  *  Copyright (C) 2002 Ulf Ekstrom except for the bitcount function.
   6  *
   7  *           >  See the header file for more info. <
   8  *
   9  *  Please email bugs and comments to Ulf Ekstrom, ulfek@ifm.liu.se
  10  *
  11  * This program is free software; you can redistribute it and/or
  12  * modify it under the terms of the GNU General Public License
  13  * as published by the Free Software Foundation; either version 2
  14  * of the License, or (at your option) any later version.
  15  *
  16  * This program is distributed in the hope that it will be useful,
  17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19  * GNU General Public License for more details.
  20  *
  21  * You should have received a copy of the GNU General Public License
  22  * along with this program; if not, write to the Free Software
  23  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  24  */
  25
  26 #include <config.h>
  27
  28 #include <cstdlib>
  29 #include <cstdio>
  30 #include <cstring>
  31 #include "bitmask.h"
  32
  33 #define MIN(a,b) ((a) < (b) ? (a) : (b))
  34
  35 bitmask *bitmask_create(int w, int h)
  36 {
  37   bitmask *temp = (bitmask*) malloc(sizeof(bitmask));
  38   if (! temp)
  39     return 0;
  40   temp->w = w;
  41   temp->h = h;
  42   temp->bits = (long unsigned int*) calloc(h*((w - 1)/BITW_LEN + 1),sizeof(BITW));
  43   if (! temp->bits)
  44     {
  45       free(temp);
  46       return 0;
  47     }
  48   else
  49     return temp;
  50 }
  51
  52 /* (C) Tobias Glaesser <tobi.web@gmx.de>, 2004.
  53    This function isn't available in the original bitmask library. */
  54 bitmask *bitmask_create_SDL(SDL_Surface* surf)
  55 {
  56   bitmask* pbitmask = bitmask_create(surf->w, surf->h);
  57   int w,h;
  58   SDL_PixelFormat* fmt;
  59   Uint32 temp, pixel;
  60   Uint8 alpha;
  61
  62   if(surf->format->BytesPerPixel != 4) //This function only works for true-color surfaces with an alpha channel
  63     return 0;
  64
  65   fmt = surf->format;
  66   for(h = 0; h <= surf->h; ++h)
  67     {
  68       for(w = 0; w <= surf->w; ++w)
  69         {
  70
  71           pixel = *((Uint32*)((Uint8 *)surf->pixels + h * surf->pitch + w * 4));
  72           /* Get Alpha component */
  73           temp=pixel&fmt->Amask; /* Isolate alpha component */
  74           temp=temp>>fmt->Ashift;/* Shift it down to 8-bit */
  75           temp=temp<<fmt->Aloss; /* Expand to a full 8-bit number */
  76           alpha=(Uint8)temp;
  77           if (fmt->Amask == 0 || alpha != 0)
  78             bitmask_setbit(pbitmask,w,h);
  79         }
  80     }
  81   return pbitmask;
  82 }
  83 void bitmask_free(bitmask *m)
  84 {
  85   free(m->bits);
  86   free(m);
  87 }
  88
  89 void bitmask_clear(bitmask *m)
  90 {
  91   memset(m->bits,0,m->h*((m->w - 1)/BITW_LEN + 1)*sizeof(BITW));
  92 }
  93
  94 void bitmask_fill(bitmask *m)
  95 {
  96   memset(m->bits,255,m->h*((m->w - 1)/BITW_LEN + 1)*sizeof(BITW));
  97 }
  98
  99 int bitmask_overlap(const bitmask *a,const bitmask *b,int xoffset, int yoffset)
 100 {
 101   BITW *a_entry,*a_end;
 102   BITW *b_entry;
 103   BITW *ap,*bp;
 104   int shift,rshift,i,astripes,bstripes;
 105
 106   if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h))
 107     return 0;
 108
 109   if (xoffset >= 0)
 110     {
 111       if (yoffset >= 0)
 112         {
 113           a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
 114           a_end = a_entry + MIN(b->h,a->h - yoffset);
 115           b_entry = b->bits;
 116         }
 117       else
 118         {
 119           a_entry = a->bits + a->h*(xoffset/BITW_LEN);
 120           a_end = a_entry + MIN(b->h + yoffset,a->h);
 121           b_entry = b->bits - yoffset;
 122         }
 123       shift = xoffset & BITW_MASK;
 124       if (shift)
 125         {
 126           rshift = BITW_LEN - shift;
 127           astripes = (a->w - 1)/BITW_LEN - xoffset/BITW_LEN;
 128           bstripes = (b->w - 1)/BITW_LEN + 1;
 129           if (bstripes > astripes) /* zig-zag .. zig*/
 130             {
 131               for (i=0;i<astripes;i++)
 132                 {
 133                   for (ap = a_entry,bp = b_entry;ap < a_end;) /* Join these two to one loop */
 134                     if ((*ap++ >> shift) & *bp++)
 135                       return 1;
 136                   a_entry += a->h;
 137                   a_end += a->h;
 138                   for (ap = a_entry,bp = b_entry;ap < a_end;)
 139                     if ((*ap++ << rshift) & *bp++)
 140                       return 1;
 141                   b_entry += b->h;
 142                 }
 143               for (ap = a_entry,bp = b_entry;ap < a_end;)
 144                 if ((*ap++ >> shift) & *bp++)
 145                   return 1;
 146               return 0;
 147             }
 148           else /* zig-zag */
 149             {
 150               for (i=0;i<bstripes;i++)
 151                 {
 152                   for (ap = a_entry,bp = b_entry;ap < a_end;)
 153                     if ((*ap++ >> shift) & *bp++)
 154                       return 1;
 155                   a_entry += a->h;
 156                   a_end += a->h;
 157                   for (ap = a_entry,bp = b_entry;ap < a_end;)
 158                     if ((*ap++  << rshift) & *bp++)
 159                       return 1;
 160                   b_entry += b->h;
 161                 }
 162               return 0;
 163             }
 164         }
 165       else /* xoffset is a multiple of the stripe width, and the above routines wont work */
 166         {
 167           astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
 168           for (i=0;i<astripes;i++)
 169             {
 170               for (ap = a_entry,bp = b_entry;ap < a_end;)
 171                 if (*ap++ & *bp++)
 172                   return 1;
 173               a_entry += a->h;
 174               a_end += a->h;
 175               b_entry += b->h;
 176             }
 177           return 0;
 178         }
 179     }
 180   else
 181     return bitmask_overlap(b,a,-xoffset,-yoffset);
 182 }
 183
 184 /* Will hang if there are no bits set in w! */
 185 static INLINE int firstsetbit(BITW w)
 186 {
 187   int i = 0;
 188   while ((w & 1) == 0)
 189     {
 190       i++;
 191       w/=2;
 192     }
 193   return i;
 194 }
 195
 196 /* x and y are given in the coordinates of mask a, and are untouched if the is no overlap */
 197 int bitmask_overlap_pos(const bitmask *a,const bitmask *b,int xoffset, int yoffset, int *x, int *y)
 198 {
 199   BITW *a_entry,*a_end;
 200   BITW *b_entry;
 201   BITW *ap,*bp;
 202   int shift,rshift,i,astripes,bstripes,xbase;
 203
 204   if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h))
 205     return 0;
 206
 207   if (xoffset >= 0)
 208     {
 209       xbase = xoffset/BITW_LEN; /* first stripe from mask a */
 210       if (yoffset >= 0)
 211         {
 212           a_entry = a->bits + a->h*xbase + yoffset;
 213           a_end = a_entry + MIN(b->h,a->h - yoffset);
 214           b_entry = b->bits;
 215         }
 216       else
 217         {
 218           a_entry = a->bits + a->h*xbase;
 219           a_end = a_entry + MIN(b->h + yoffset,a->h);
 220           b_entry = b->bits - yoffset;
 221           yoffset = 0; /* relied on below */
 222         }
 223       shift = xoffset & BITW_MASK;
 224       if (shift)
 225         {
 226           rshift = BITW_LEN - shift;
 227           astripes = (a->w - 1)/BITW_LEN - xoffset/BITW_LEN;
 228           bstripes = (b->w - 1)/BITW_LEN + 1;
 229           if (bstripes > astripes) /* zig-zag .. zig*/
 230             {
 231               for (i=0;i<astripes;i++)
 232                 {
 233                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 234                     if (*ap & (*bp << shift))
 235                       {
 236                         *y = ap - a_entry + yoffset;
 237                         *x = (xbase + i)*BITW_LEN + firstsetbit(*ap & (*bp << shift));
 238                         return 1;
 239                       }
 240                   a_entry += a->h;
 241                   a_end += a->h;
 242                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 243                     if (*ap & (*bp >> rshift))
 244                       {
 245                         *y = ap - a_entry + yoffset;
 246                         *x = (xbase + i + 1)*BITW_LEN + firstsetbit(*ap & (*bp >> rshift));
 247                         return 1;
 248                       }
 249                   b_entry += b->h;
 250                 }
 251               for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 252                 if (*ap & (*bp << shift))
 253                   {
 254                     *y = ap - a_entry + yoffset;
 255                     *x = (xbase + astripes)*BITW_LEN + firstsetbit(*ap & (*bp << shift));
 256                     return 1;
 257                   }
 258               return 0;
 259             }
 260           else /* zig-zag */
 261             {
 262               for (i=0;i<bstripes;i++)
 263                 {
 264                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 265                     if (*ap & (*bp << shift))
 266                       {
 267                         *y = ap - a_entry + yoffset;
 268                         *x = (xbase + i)*BITW_LEN + firstsetbit(*ap & (*bp << shift));
 269                         return 1;
 270                       }
 271                   a_entry += a->h;
 272                   a_end += a->h;
 273                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 274                     if (*ap & (*bp >> rshift))
 275                       {
 276                         *y = ap - a_entry + yoffset;
 277                         *x = (xbase + i + 1)*BITW_LEN + firstsetbit(*ap & (*bp >> rshift));
 278                         return 1;
 279                       }
 280                   b_entry += b->h;
 281                 }
 282               return 0;
 283             }
 284         }
 285       else /* xoffset is a multiple of the stripe width, and the above routines
 286            won't work. This way is also slightly faster. */
 287         {
 288           astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
 289           for (i=0;i<astripes;i++)
 290             {
 291               for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 292                 {
 293                   if (*ap & *bp)
 294                     {
 295                        *y = ap - a_entry + yoffset;
 296                        *x = (xbase + i)*BITW_LEN + firstsetbit(*ap & *bp);
 297                       return 1;
 298                     }
 299                 }
 300               a_entry += a->h;
 301               a_end += a->h;
 302               b_entry += b->h;
 303             }
 304           return 0;
 305         }
 306     }
 307   else
 308     {
 309       if (bitmask_overlap_pos(b,a,-xoffset,-yoffset,x,y))
 310         {
 311           *x += xoffset;
 312           *y += yoffset;
 313           return 1;
 314         }
 315       else
 316         return 0;
 317     }
 318 }
 319
 320 static INLINE int bitcount(unsigned long n)
 321 {
 322   if (BITW_LEN == 32)
 323     {
 324       /* (C) Donald W. Gillies, 1992.  All rights reserved.  You may reuse
 325          this bitcount() function anywhere you please as long as you retain
 326          this Copyright Notice. */
 327       register unsigned long tmp;
 328       return (tmp = (n) - (((n) >> 1) & 033333333333) -
 329                     (((n) >> 2) & 011111111111),
 330               tmp = ((tmp + (tmp >> 3)) & 030707070707),
 331               tmp =  (tmp + (tmp >> 6)),
 332               tmp = (tmp + (tmp >> 12) + (tmp >> 24)) & 077);
 333       /* End of Donald W. Gillies bitcount code */
 334     }
 335   else
 336     {
 337       /* Handle non-32 bit case the slow way */
 338       int nbits = 0;
 339       while (n)
 340         {
 341           if (n & 1)
 342             nbits++;
 343           n = n >> 1;
 344         }
 345       return nbits;
 346     }
 347 }
 348
 349
 350 int bitmask_overlap_area(const bitmask *a,const bitmask *b,int xoffset, int yoffset)
 351 {
 352   BITW *a_entry,*a_end;
 353   BITW *b_entry;
 354   BITW *ap,*bp;
 355   int shift,rshift,i,astripes,bstripes;
 356   int count = 0;
 357
 358   if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h))
 359     return 0;
 360
 361   if (xoffset >= 0)
 362     {
 363       if (yoffset >= 0)
 364         {
 365           a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
 366           a_end = a_entry + MIN(b->h,a->h - yoffset);
 367           b_entry = b->bits;
 368         }
 369       else
 370         {
 371           a_entry = a->bits + a->h*(xoffset/BITW_LEN);
 372           a_end = a_entry + MIN(b->h + yoffset,a->h);
 373           b_entry = b->bits - yoffset;
 374         }
 375       shift = xoffset & BITW_MASK;
 376       if (shift)
 377         {
 378           rshift = BITW_LEN - shift;
 379           astripes = (a->w - 1)/BITW_LEN - xoffset/BITW_LEN;
 380           bstripes = (b->w - 1)/BITW_LEN + 1;
 381           if (bstripes > astripes) /* zig-zag .. zig*/
 382             {
 383               for (i=0;i<astripes;i++)
 384                 {
 385                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 386                     count += bitcount(((*ap >> shift) | (*(ap + a->h) << rshift)) & *bp);
 387                   a_entry += a->h;
 388                   a_end += a->h;
 389                   b_entry += b->h;
 390                 }
 391               for (ap = a_entry,bp = b_entry;ap < a_end;)
 392                 count += bitcount((*ap++ >> shift) & *bp++);
 393               return count;
 394             }
 395           else /* zig-zag */
 396             {
 397               for (i=0;i<bstripes;i++)
 398                 {
 399                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 400                     count += bitcount(((*ap >> shift) | (*(ap + a->h) << rshift)) & *bp);
 401                   a_entry += a->h;
 402                   a_end += a->h;
 403                   b_entry += b->h;
 404                 }
 405               return count;
 406             }
 407         }
 408       else /* xoffset is a multiple of the stripe width, and the above routines wont work */
 409         {
 410           astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
 411           for (i=0;i<astripes;i++)
 412             {
 413               for (ap = a_entry,bp = b_entry;ap < a_end;)
 414                 count += bitcount(*ap++ & *bp++);
 415
 416               a_entry += a->h;
 417               a_end += a->h;
 418               b_entry += b->h;
 419             }
 420           return count;
 421         }
 422     }
 423   else
 424     return bitmask_overlap_area(b,a,-xoffset,-yoffset);
 425 }
 426
 427
 428 /* Draws mask b onto mask a (bitwise OR) */
 429 void bitmask_draw(bitmask *a,bitmask *b,int xoffset, int yoffset)
 430 {
 431   BITW *a_entry,*a_end;
 432   BITW *b_entry;
 433   BITW *ap,*bp;
 434   bitmask *swap;
 435   int shift,rshift,i,astripes,bstripes;
 436
 437   if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h))
 438     return;
 439
 440   if (xoffset >= 0)
 441     {
 442       if (yoffset >= 0)
 443         {
 444           a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
 445           a_end = a_entry + MIN(b->h,a->h - yoffset);
 446           b_entry = b->bits;
 447         }
 448       else
 449         {
 450           a_entry = a->bits + a->h*(xoffset/BITW_LEN);
 451           a_end = a_entry + MIN(b->h + yoffset,a->h);
 452           b_entry = b->bits - yoffset;
 453         }
 454       shift = xoffset & BITW_MASK;
 455       if (shift)
 456         {
 457           rshift = BITW_LEN - shift;
 458           astripes = (a->w - 1)/BITW_LEN - xoffset/BITW_LEN;
 459           bstripes = (b->w - 1)/BITW_LEN + 1;
 460           if (bstripes > astripes) /* zig-zag .. zig*/
 461             {
 462               for (i=0;i<astripes;i++)
 463                 {
 464                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 465                     *ap |= (*bp << shift);
 466                   a_entry += a->h;
 467                   a_end += a->h;
 468                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 469                     *ap |= (*bp >> rshift);
 470                   b_entry += b->h;
 471                 }
 472               for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 473                 *ap |= (*bp << shift);
 474               return;
 475             }
 476           else /* zig-zag */
 477             {
 478               for (i=0;i<bstripes;i++)
 479                 {
 480                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 481                     *ap |= (*bp << shift);
 482                   a_entry += a->h;
 483                   a_end += a->h;
 484                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 485                     *ap |= (*bp >> rshift);
 486                   b_entry += b->h;
 487                 }
 488               return;
 489             }
 490         }
 491       else /* xoffset is a multiple of the stripe width, and the above routines won't work. */
 492         {
 493           astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
 494           for (i=0;i<astripes;i++)
 495             {
 496               for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 497                 {
 498                   *ap |= *bp;
 499                 }
 500               a_entry += a->h;
 501               a_end += a->h;
 502               b_entry += b->h;
 503             }
 504           return;
 505         }
 506     }
 507   else
 508     {
 509       /* 'Swapping' arguments to be able to almost reuse the code above,
 510        should be taken care of by the compiler efficiently. */
 511       swap = a;
 512       a = b;
 513       b = swap;
 514       xoffset *= -1;
 515       yoffset *= -1;
 516
 517       if (yoffset >= 0)
 518         {
 519           a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
 520           a_end = a_entry + MIN(b->h,a->h - yoffset);
 521           b_entry = b->bits;
 522         }
 523       else
 524         {
 525           a_entry = a->bits + a->h*(xoffset/BITW_LEN);
 526           a_end = a_entry + MIN(b->h + yoffset,a->h);
 527           b_entry = b->bits - yoffset;
 528         }
 529       shift = xoffset & BITW_MASK;
 530       if (shift)
 531         {
 532           rshift = BITW_LEN - shift;
 533           astripes = (a->w - 1)/BITW_LEN - xoffset/BITW_LEN;
 534           bstripes = (b->w - 1)/BITW_LEN + 1;
 535           if (bstripes > astripes) /* zig-zag .. zig*/
 536             {
 537               for (i=0;i<astripes;i++)
 538                 {
 539                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 540                     *bp |= (*ap >> shift);
 541                   a_entry += a->h;
 542                   a_end += a->h;
 543                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 544                     *bp |= (*ap <<rshift);
 545                   b_entry += b->h;
 546                 }
 547               for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 548                 *bp |= (*ap >> shift);
 549               return;
 550             }
 551           else /* zig-zag */
 552             {
 553               for (i=0;i<bstripes;i++)
 554                 {
 555                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 556                     *bp |= (*ap >> shift);
 557                   a_entry += a->h;
 558                   a_end += a->h;
 559                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 560                     *bp |= (*ap << rshift);
 561                   b_entry += b->h;
 562                 }
 563               return;
 564             }
 565         }
 566       else /* xoffset is a multiple of the stripe width, and the above routines won't work. */
 567         {
 568           astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
 569           for (i=0;i<astripes;i++)
 570             {
 571               for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 572                 {
 573                   *bp |= *ap;
 574                 }
 575               a_entry += a->h;
 576               a_end += a->h;
 577               b_entry += b->h;
 578             }
 579           return;
 580         }
 581     }
 582 }