Source

pygame / src / bitmask.c

Diff from to

src/bitmask.c

 #define MIN(a,b) ((a) <= (b) ? (a) : (b))
 #define MAX(a,b) ((a) >= (b) ? (a) : (b))
 
+/* The code by Gillies is slightly (1-3%) faster than the more
+   readable code below */
+#define GILLIES
+
+static INLINE unsigned int bitcount(BITMASK_W n)
+{
+  if (BITMASK_W_LEN == 32)
+    {
+#ifdef GILLIES
+/* (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
+   /* This piece taken from Jorg Arndt's "Algorithms for Programmers" */
+    n  = ((n>>1) & 0x55555555) + (n & 0x55555555);  // 0-2 in 2 bits
+    n  = ((n>>2) & 0x33333333) + (n & 0x33333333);  // 0-4 in 4 bits
+    n  = ((n>>4) + n) & 0x0f0f0f0f;                 // 0-8 in 4 bits
+    n +=  n>> 8;                                    // 0-16 in 8 bits
+    n +=  n>>16;                                    // 0-32 in 8 bits
+    return  n & 0xff;
+#endif
+    }
+  else if (BITMASK_W_LEN == 64)
+    {
+      n  = ((n>>1) & 0x5555555555555555) + (n & 0x5555555555555555);
+      n  = ((n>>2) & 0x3333333333333333) + (n & 0x3333333333333333);
+      n  = ((n>>4) + n) & 0x0f0f0f0f0f0f0f0f;
+      n +=  n>> 8;                                    
+      n +=  n>>16;                                    
+      n +=  n>>32;
+      return  n & 0xff;
+    }
+  else
+    {
+      /* Handle non-32 or 64 bit case the slow way */
+      unsigned int nbits = 0;
+      while (n)
+	{
+	  if (n & 1)
+	    nbits++;
+	  n = n >> 1;
+	}
+      return nbits;
+    }
+}
+
 bitmask_t *bitmask_create(int w, int h)
 {
   bitmask_t *temp;
 
 void bitmask_fill(bitmask_t *m)
 {
-  int x,y;
-  for (y = 0; y < m->h; y++)
-    for (x = 0; x < m->w; x++)
-      bitmask_setbit(m, x, y);
+    int len, shift;
+    BITMASK_W *pixels, cmask, full;
+    
+    len = m->h*((m->w - 1)/BITMASK_W_LEN);
+    shift = BITMASK_W_LEN - (m->w % BITMASK_W_LEN);
+    full = ~(BITMASK_W)0;
+    cmask = (~(BITMASK_W)0) >> shift;    
+    /* fill all the pixels that aren't in the rightmost BITMASK_Ws */
+    for (pixels = m->bits; pixels < (m->bits + len); pixels++) {
+        *pixels = full;
+    }
+    /* for the rightmost BITMASK_Ws, use cmask to ensure we aren't setting
+       bits that are outside of the mask */
+    for (pixels = m->bits + len; pixels < (m->bits + len + m->h); pixels++) {
+        *pixels = cmask;
+    }
+}
+
+void bitmask_invert(bitmask_t *m)
+{
+    int len, shift;
+    BITMASK_W *pixels, cmask;
+    
+    len = m->h*((m->w - 1)/BITMASK_W_LEN);
+    shift = BITMASK_W_LEN - (m->w % BITMASK_W_LEN);
+    cmask = (~(BITMASK_W)0) >> shift;    
+    /* flip all the pixels that aren't in the rightmost BITMASK_Ws */
+    for (pixels = m->bits; pixels < (m->bits + len); pixels++) {
+        *pixels = ~(*pixels);
+    }
+    /* for the rightmost BITMASK_Ws, & with cmask to ensure we aren't setting
+       bits that are outside of the mask */
+    for (pixels = m->bits + len; pixels < (m->bits + len + m->h); pixels++) {
+        *pixels = cmask & ~(*pixels);
+    }
+}
+
+unsigned int bitmask_count(bitmask_t *m)
+{
+    BITMASK_W *pixels;
+    unsigned int tot = 0;
+    
+    for (pixels=m->bits; pixels<(m->bits+m->h*((m->w-1)/BITMASK_W_LEN + 1)); pixels++) {
+        tot += bitcount(*pixels);
+    }
+    
+    return tot;
 }
 
 int bitmask_overlap(const bitmask_t *a, const bitmask_t *b, int xoffset, int yoffset)
     }
 }
 
-/* The code by Gillies is slightly (1-3%) faster than the more
-   readable code below */
-#define GILLIES
-
-static INLINE unsigned int bitcount(BITMASK_W n)
-{
-  if (BITMASK_W_LEN == 32)
-    {
-#ifdef GILLIES
-/* (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
-   /* This piece taken from Jorg Arndt's "Algorithms for Programmers" */
-    n  = ((n>>1) & 0x55555555) + (n & 0x55555555);  // 0-2 in 2 bits
-    n  = ((n>>2) & 0x33333333) + (n & 0x33333333);  // 0-4 in 4 bits
-    n  = ((n>>4) + n) & 0x0f0f0f0f;                 // 0-8 in 4 bits
-    n +=  n>> 8;                                    // 0-16 in 8 bits
-    n +=  n>>16;                                    // 0-32 in 8 bits
-    return  n & 0xff;
-#endif
-    }
-  else if (BITMASK_W_LEN == 64)
-    {
-      n  = ((n>>1) & 0x5555555555555555) + (n & 0x5555555555555555);
-      n  = ((n>>2) & 0x3333333333333333) + (n & 0x3333333333333333);
-      n  = ((n>>4) + n) & 0x0f0f0f0f0f0f0f0f;
-      n +=  n>> 8;                                    
-      n +=  n>>16;                                    
-      n +=  n>>32;
-      return  n & 0xff;
-    }
-  else
-    {
-      /* Handle non-32 or 64 bit case the slow way */
-      unsigned int nbits = 0;
-      while (n)
-	{
-	  if (n & 1)
-	    nbits++;
-	  n = n >> 1;
-	}
-      return nbits;
-    }
-}
-
 int bitmask_overlap_area(const bitmask_t *a, const bitmask_t *b, int xoffset, int yoffset)
 {
   const BITMASK_W *a_entry,*a_end, *b_entry, *ap,*bp;
     }
 }
 
+/* Makes a mask of the overlap of two other masks */
+void bitmask_overlap_mask(const bitmask_t *a, const bitmask_t *b, bitmask_t *c, int xoffset, int yoffset)
+{
+  const BITMASK_W *a_entry,*a_end, *ap;
+  const BITMASK_W *b_entry, *b_end, *bp;
+  BITMASK_W *c_entry, *c_end, *cp;
+  int shift,rshift,i,astripes,bstripes;
+  
+  if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h)) 
+      return;
+  
+  if (xoffset >= 0) 
+    {
+      if (yoffset >= 0)
+	{
+	  a_entry = a->bits + a->h*(xoffset/BITMASK_W_LEN) + yoffset;
+	  c_entry = c->bits + c->h*(xoffset/BITMASK_W_LEN) + yoffset;
+	  a_end = a_entry + MIN(b->h,a->h - yoffset);
+	  b_entry = b->bits;
+	}
+      else
+	{
+	  a_entry = a->bits + a->h*(xoffset/BITMASK_W_LEN);
+	  c_entry = c->bits + c->h*(xoffset/BITMASK_W_LEN);
+	  a_end = a_entry + MIN(b->h + yoffset,a->h);
+	  b_entry = b->bits - yoffset;
+	}
+      shift = xoffset & BITMASK_W_MASK;
+      if (shift)
+	{
+	  rshift = BITMASK_W_LEN - shift;
+	  astripes = (a->w - 1)/BITMASK_W_LEN - xoffset/BITMASK_W_LEN;
+	  bstripes = (b->w - 1)/BITMASK_W_LEN + 1;
+	  if (bstripes > astripes) /* zig-zag .. zig*/
+	    {
+	      for (i=0;i<astripes;i++)
+		{
+		  for (ap = a_entry,bp = b_entry,cp = c_entry;ap < a_end;ap++,bp++,cp++)
+		    *cp = *ap & (*bp << shift);
+		  a_entry += a->h;
+		  c_entry += c->h;
+		  a_end += a->h;
+		  for (ap = a_entry,bp = b_entry,cp = c_entry;ap < a_end;ap++,bp++,cp++)
+		    *cp = *ap & (*bp >> rshift);
+		  b_entry += b->h;
+		}
+	      for (ap = a_entry,bp = b_entry,cp = c_entry;ap < a_end;ap++,bp++,cp++)
+		*cp = *ap & (*bp << shift);
+	    }
+	  else /* zig-zag */
+	    {
+	      for (i=0;i<bstripes;i++)
+		{
+		  for (ap = a_entry,bp = b_entry,cp = c_entry;ap < a_end;ap++,bp++,cp++)
+		    *cp = *ap & (*bp << shift);
+		  a_entry += a->h;
+		  c_entry += c->h;
+		  a_end += a->h;
+		  for (ap = a_entry,bp = b_entry,cp = c_entry;ap < a_end;ap++,bp++,cp++)
+		    *cp = *ap & (*bp >> rshift);
+		  b_entry += b->h;
+		}
+	    }
+	}
+      else /* xoffset is a multiple of the stripe width, 
+	      and the above routines won't work. */
+	{
+	  astripes = (MIN(b->w,a->w - xoffset) - 1)/BITMASK_W_LEN + 1;
+	  for (i=0;i<astripes;i++)
+	    {
+	      for (ap = a_entry,bp = b_entry,cp = c_entry;ap < a_end;ap++,bp++,cp++)
+		{
+		  *cp = *ap & *bp;
+		}
+	      a_entry += a->h;
+	      c_entry += c->h;
+	      a_end += a->h;
+	      b_entry += b->h;
+	    }
+	}
+    }
+  else  
+    {
+      xoffset *= -1;
+      yoffset *= -1;
+
+      if (yoffset >= 0)
+	{
+	  b_entry = b->bits + b->h*(xoffset/BITMASK_W_LEN) + yoffset;
+	  b_end = b_entry + MIN(a->h,b->h - yoffset);
+	  a_entry = a->bits;
+	  c_entry = c->bits;
+	}
+      else
+	{
+	  b_entry = b->bits + b->h*(xoffset/BITMASK_W_LEN);
+	  b_end = b_entry + MIN(a->h + yoffset,b->h);
+	  a_entry = a->bits - yoffset;
+	  c_entry = c->bits - yoffset;
+	}
+      shift = xoffset & BITMASK_W_MASK;
+      if (shift)
+	{
+	  rshift = BITMASK_W_LEN - shift;
+	  astripes = (b->w - 1)/BITMASK_W_LEN - xoffset/BITMASK_W_LEN;
+	  bstripes = (a->w - 1)/BITMASK_W_LEN + 1;
+	  if (bstripes > astripes) /* zig-zag .. zig*/
+	    {
+	      for (i=0;i<astripes;i++)
+		{
+		  for (bp = b_entry,ap = a_entry,cp = c_entry;bp < b_end;bp++,ap++,cp++)
+		    *cp = *ap & (*bp >> shift);
+		  b_entry += b->h;
+		  b_end += b->h;
+		  for (bp = b_entry,ap = a_entry,cp = c_entry;bp < b_end;bp++,ap++,cp++)
+		    *cp = *ap & (*bp <<rshift); 
+		  a_entry += a->h;
+		  c_entry += c->h;
+		}
+	      for (bp = b_entry,ap = a_entry,cp = c_entry;bp < b_end;bp++,ap++,cp++)
+		*cp = *ap & (*bp >> shift);
+	    }
+	  else /* zig-zag */
+	    {
+	      for (i=0;i<bstripes;i++)
+		{
+		  for (bp = b_entry,ap = a_entry,cp = c_entry;bp < b_end;bp++,ap++,cp++)
+		    *cp = *ap & (*bp >> shift);
+		  b_entry += b->h;
+		  b_end += b->h;
+		  for (bp = b_entry,ap = a_entry,cp = c_entry;bp < b_end;bp++,ap++,cp++)
+		    *cp = *ap & (*bp << rshift);
+		  a_entry += a->h;
+		  c_entry += c->h;
+		}
+	    }
+	}
+      else /* xoffset is a multiple of the stripe width, and the above routines won't work. */
+	{
+	  astripes = (MIN(a->w,b->w - xoffset) - 1)/BITMASK_W_LEN + 1;
+	  for (i=0;i<astripes;i++)
+	    {
+	      for (bp = b_entry,ap = a_entry,cp = c_entry;bp < b_end;bp++,ap++,cp++)
+		{
+		  *cp = *ap & *bp;
+		}
+	      b_entry += b->h;
+	      b_end += b->h;
+	      a_entry += a->h;
+	      c_entry += c->h;
+	    }
+	}
+      xoffset *= -1;
+      yoffset *= -1;
+    }	
+  /* Zero out bits outside the mask rectangle (to the right), if there
+   is a chance we were drawing there. */
+  if (xoffset + b->w > c->w)
+    {
+      BITMASK_W edgemask;
+      int n = c->w/BITMASK_W_LEN;
+      shift = (n + 1)*BITMASK_W_LEN - c->w;
+      edgemask = (~(BITMASK_W)0) >> shift;
+      c_end = c->bits + n*c->h + MIN(c->h,b->h + yoffset);
+      for (cp = c->bits + n*c->h + MAX(yoffset,0);cp<c_end;cp++)
+	*cp &= edgemask;
+    }
+}
+
 /* Draws mask b onto mask a (bitwise OR) */
 void bitmask_draw(bitmask_t *a, const bitmask_t *b, int xoffset, int yoffset)
 {
   return nm;
 }
 
+void bitmask_convolve(const bitmask_t *a, const bitmask_t *b, bitmask_t *o, int xoffset, int yoffset)
+{
+  int x, y;
+
+  xoffset += b->w - 1;
+  yoffset += b->h - 1;
+  for (y = 0; y < b->h; y++)
+    for (x = 0; x < b->w; x++)
+      if (bitmask_getbit(b, x, y))
+        bitmask_draw(o, a, xoffset - x, yoffset - y);
+}
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.