src/bitmask.c

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