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