From 72f573a5e7226d35c8b2b5def07848178b2f046c Mon Sep 17 00:00:00 2001 From: =?utf8?q?Tobias=20Gl=C3=A4=C3=9Fer?= Date: Sun, 8 Aug 2004 15:46:21 +0000 Subject: [PATCH] Merged the bitmask code with a newer version (1.3) of the bitmask library. SVN-Revision: 1726 --- src/bitmask.cpp | 93 ++++++++++++++++++++++++++++++++++++++------------------- src/bitmask.h | 18 +++++------ 2 files changed, 70 insertions(+), 41 deletions(-) diff --git a/src/bitmask.cpp b/src/bitmask.cpp index 65c927a40..65500903b 100644 --- a/src/bitmask.cpp +++ b/src/bitmask.cpp @@ -23,8 +23,9 @@ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ -#include -#include +#include +#include +#include #include "bitmask.h" #define MIN(a,b) ((a) < (b) ? (a) : (b)) @@ -46,6 +47,8 @@ bitmask *bitmask_create(int w, int h) return temp; } +/* (C) Tobias Glaesser , 2004. + This function isn't available in the original bitmask library. */ bitmask *bitmask_create_SDL(SDL_Surface* surf) { bitmask* pbitmask = bitmask_create(surf->w, surf->h); @@ -56,7 +59,7 @@ bitmask *bitmask_create_SDL(SDL_Surface* surf) if(surf->format->BytesPerPixel != 4) //This function only works for true-color surfaces with an alpha channel return 0; - + fmt = surf->format; for(h = 0; h <= surf->h; ++h) { @@ -81,6 +84,16 @@ void bitmask_free(bitmask *m) free(m); } +void bitmask_clear(bitmask *m) +{ + memset(m->bits,0,m->h*((m->w - 1)/BITW_LEN + 1)*sizeof(BITW)); +} + +void bitmask_fill(bitmask *m) +{ + memset(m->bits,255,m->h*((m->w - 1)/BITW_LEN + 1)*sizeof(BITW)); +} + int bitmask_overlap(const bitmask *a,const bitmask *b,int xoffset, int yoffset) { BITW *a_entry,*a_end; @@ -184,24 +197,26 @@ int bitmask_overlap_pos(const bitmask *a,const bitmask *b,int xoffset, int yoffs BITW *a_entry,*a_end; BITW *b_entry; BITW *ap,*bp; - int shift,rshift,i,astripes,bstripes; + int shift,rshift,i,astripes,bstripes,xbase; if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h)) return 0; if (xoffset >= 0) { + xbase = xoffset/BITW_LEN; /* first stripe from mask a */ if (yoffset >= 0) { - a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset; + a_entry = a->bits + a->h*xbase + yoffset; a_end = a_entry + MIN(b->h,a->h - yoffset); b_entry = b->bits; } else { - a_entry = a->bits + a->h*(xoffset/BITW_LEN); + a_entry = a->bits + a->h*xbase; a_end = a_entry + MIN(b->h + yoffset,a->h); b_entry = b->bits - yoffset; + yoffset = 0; /* relied on below */ } shift = xoffset & BITW_MASK; if (shift) @@ -216,8 +231,8 @@ int bitmask_overlap_pos(const bitmask *a,const bitmask *b,int xoffset, int yoffs for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++) if (*ap & (*bp << shift)) { - *y = (ap - a->bits) % a->h; - *x = ((ap - a->bits) / a->h)*BITW_LEN + firstsetbit(*ap & (*bp << shift)); + *y = ap - a_entry + yoffset; + *x = (xbase + i)*BITW_LEN + firstsetbit(*ap & (*bp << shift)); return 1; } a_entry += a->h; @@ -225,8 +240,8 @@ int bitmask_overlap_pos(const bitmask *a,const bitmask *b,int xoffset, int yoffs for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++) if (*ap & (*bp >> rshift)) { - *y = (ap - a->bits) % a->h; - *x = ((ap - a->bits) / a->h)*BITW_LEN + firstsetbit(*ap & (*bp >> rshift)); + *y = ap - a_entry + yoffset; + *x = (xbase + i + 1)*BITW_LEN + firstsetbit(*ap & (*bp >> rshift)); return 1; } b_entry += b->h; @@ -234,8 +249,8 @@ int bitmask_overlap_pos(const bitmask *a,const bitmask *b,int xoffset, int yoffs for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++) if (*ap & (*bp << shift)) { - *y = (ap - a->bits) % a->h; - *x = ((ap - a->bits) / a->h)*BITW_LEN + firstsetbit(*ap & (*bp << shift)); + *y = ap - a_entry + yoffset; + *x = (xbase + astripes)*BITW_LEN + firstsetbit(*ap & (*bp << shift)); return 1; } return 0; @@ -247,8 +262,8 @@ int bitmask_overlap_pos(const bitmask *a,const bitmask *b,int xoffset, int yoffs for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++) if (*ap & (*bp << shift)) { - *y = (ap - a->bits) % a->h; - *x = ((ap - a->bits) / a->h)*BITW_LEN + firstsetbit(*ap & (*bp << shift)); + *y = ap - a_entry + yoffset; + *x = (xbase + i)*BITW_LEN + firstsetbit(*ap & (*bp << shift)); return 1; } a_entry += a->h; @@ -256,8 +271,8 @@ int bitmask_overlap_pos(const bitmask *a,const bitmask *b,int xoffset, int yoffs for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++) if (*ap & (*bp >> rshift)) { - *y = (ap - a->bits) % a->h; - *x = ((ap - a->bits) / a->h)*BITW_LEN + firstsetbit(*ap & (*bp >> rshift)); + *y = ap - a_entry + yoffset; + *x = (xbase + i + 1)*BITW_LEN + firstsetbit(*ap & (*bp >> rshift)); return 1; } b_entry += b->h; @@ -265,7 +280,8 @@ int bitmask_overlap_pos(const bitmask *a,const bitmask *b,int xoffset, int yoffs return 0; } } - else /* xoffset is a multiple of the stripe width, and the above routines won't work. */ + else /* xoffset is a multiple of the stripe width, and the above routines + won't work. This way is also slightly faster. */ { astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1; for (i=0;ibits) % a->h; - *x = ((ap - a->bits) / a->h)*BITW_LEN + firstsetbit(*ap & *bp); + *y = ap - a_entry + yoffset; + *x = (xbase + i)*BITW_LEN + firstsetbit(*ap & *bp); return 1; } } @@ -299,20 +315,34 @@ int bitmask_overlap_pos(const bitmask *a,const bitmask *b,int xoffset, int yoffs } } - - -/* (C) Donald W. Gillies, 1992. All rights reserved. You may reuse - this bitcount() function anywhere you please as long as you retain - this Copyright Notice. */ static INLINE int bitcount(unsigned long n) { - register unsigned long tmp; - return (tmp = (n) - (((n) >> 1) & 033333333333) - (((n) >> 2) & 011111111111),\ - tmp = ((tmp + (tmp >> 3)) & 030707070707), \ - tmp = (tmp + (tmp >> 6)), \ - tmp = (tmp + (tmp >> 12) + (tmp >> 24)) & 077); + if (BITW_LEN == 32) + { + /* (C) Donald W. Gillies, 1992. All rights reserved. You may reuse + this bitcount() function anywhere you please as long as you retain + this Copyright Notice. */ + register unsigned long tmp; + return (tmp = (n) - (((n) >> 1) & 033333333333) - + (((n) >> 2) & 011111111111), + tmp = ((tmp + (tmp >> 3)) & 030707070707), + tmp = (tmp + (tmp >> 6)), + tmp = (tmp + (tmp >> 12) + (tmp >> 24)) & 077); + /* End of Donald W. Gillies bitcount code */ + } + else + { + /* Handle non-32 bit case the slow way */ + int nbits = 0; + while (n) + { + if (n & 1) + nbits++; + n = n >> 1; + } + return nbits; + } } -/* End of Donald W. Gillies bitcount code */ int bitmask_overlap_area(const bitmask *a,const bitmask *b,int xoffset, int yoffset) @@ -474,7 +504,8 @@ void bitmask_draw(bitmask *a,bitmask *b,int xoffset, int yoffset) } else { - /* 'Swapping' arguments to be able to almost reuse the code above */ + /* 'Swapping' arguments to be able to almost reuse the code above, + should be taken care of by the compiler efficiently. */ swap = a; a = b; b = swap; diff --git a/src/bitmask.h b/src/bitmask.h index 915b21c59..e699a7ff5 100644 --- a/src/bitmask.h +++ b/src/bitmask.h @@ -10,7 +10,6 @@ * to check for collisions. * The current implementation uses 32 bit wide stripes to hold * the masks, but should work just as well with 64 bit sizes. - * (Note that the current bitcount function is 32 bit only!) * * The overlap tests uses the following offsets (which may be negative): * @@ -26,11 +25,6 @@ * with some kind of pre-sorting to avoid comparing objects far from * each other. * - * BUGS: No known bugs, even though they may certainly be in here somewhere. - * Possible performance improvements could be to remove the div in - * bitmask_overlap_pos() and to implement wider stripes if the masks used - * are wider than 64 bits on the average. - * * Performance of the various functions goes something like: * (relative timings, smaller is better) * @@ -65,11 +59,12 @@ #define SUPERTUX_BITMASK_H #include +#include /* Define INLINE for different compilers. */ #ifndef INLINE # ifdef __GNUC__ -# define INLINE __inline__ +# define INLINE inline # else # ifdef _MSC_VER # define INLINE __inline @@ -80,8 +75,8 @@ #endif #define BITW unsigned long int -#define BITW_LEN 32 -#define BITW_MASK 31 +#define BITW_LEN (sizeof(BITW)*CHAR_BIT) +#define BITW_MASK (BITW_LEN - 1) #define BITN(n) ((BITW)1 << (n)) struct bitmask @@ -96,6 +91,9 @@ struct bitmask bitmask *bitmask_create(int w, int h); void bitmask_free(bitmask *m); +void bitmask_clear(bitmask *m); +void bitmask_fill(bitmask *m); + /* Returns nonzero if the bit at (x,y) is set. * Coordinates start at (0,0) */ @@ -123,7 +121,7 @@ static INLINE void bitmask_clearbit(bitmask *m,int x,int y) int bitmask_overlap(const bitmask *a,const bitmask *b,int xoffset, int yoffset); /* Like bitmask_overlap(), but will also give a point of intersection. - * x and y are given in the coordinates of mask a, and are untouched if the is + * x and y are given in the coordinates of mask a, and are untouched if there is * no overlap. */ int bitmask_overlap_pos(const bitmask *a,const bitmask *b,int xoffset, int yoffset, int *x, int *y); -- 2.11.0