[Pen-commits] SF.net SVN: pen:[116] pygame/src

[<mdg...@us...>]

Revision: 116
          http://pen.svn.sourceforge.net/pen/?rev=116&view=rev
Author:   mdgeorge
Date:     2008-12-03 23:43:41 +0000 (Wed, 03 Dec 2008)

Log Message:
-----------
Moved all of the pygame stuff into pygame.  some of this is just copies of headers, some of it is patched.

Added Paths:
-----------
    pygame/src/bitmask.c
    pygame/src/bitmask.h

Removed Paths:
-------------
    include/

Added: pygame/src/bitmask.c
===================================================================
--- pygame/src/bitmask.c	                        (rev 0)
+++ pygame/src/bitmask.c	2008-12-03 23:43:41 UTC (rev 116)
@@ -0,0 +1,979 @@
+/*
+    Bitmask Collision Detection Library 1.5
+    Copyright (C) 2002-2005 Ulf Ekstrom except for the bitcount function which
+    is copyright (C) Donald W. Gillies, 1992, and the other bitcount function
+    which was taken from Jorg Arndt's excellent "Algorithms for Programmers"
+    text.
+  
+    This library is free software; you can redistribute it and/or
+    modify it under the terms of the GNU Library General Public
+    License as published by the Free Software Foundation; either
+    version 2 of the License, or (at your option) any later version.
+ 
+    This library is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+    Library General Public License for more details.
+ 
+    You should have received a copy of the GNU Library General Public
+    License along with this library; if not, write to the Free
+    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+
+#include <stdlib.h>
+#include <stddef.h>
+#include <string.h>
+#include "bitmask.h"
+
+#ifndef INLINE
+#warning No INLINE definition in bitmask.h, performance may suffer.
+#endif
+
+#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;
+  temp = malloc(offsetof(bitmask_t,bits) + h*((w - 1)/BITMASK_W_LEN + 1)*sizeof(BITMASK_W));  
+  if (!temp) 
+    return 0;
+  temp->w = w;
+  temp->h = h;
+  bitmask_clear(temp);
+  return temp;
+}
+
+void bitmask_free(bitmask_t *m)
+{
+  free(m);
+}
+
+void bitmask_clear(bitmask_t *m)
+{
+  memset(m->bits,0,m->h*((m->w - 1)/BITMASK_W_LEN + 1)*sizeof(BITMASK_W));
+}
+
+void bitmask_fill(bitmask_t *m)
+{
+    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)
+{
+  const BITMASK_W *a_entry,*a_end;
+  const BITMASK_W *b_entry;
+  const BITMASK_W *ap,*app,*bp;
+  unsigned int shift,rshift,i,astripes,bstripes;
+  
+  if ((xoffset >= a->w) || (yoffset >= a->h) || (b->h + yoffset <= 0) || (b->w + xoffset <= 0)) 
+      return 0;
+
+  if (xoffset >= 0) 
+    {
+    swapentry:
+      if (yoffset >= 0)
+	{
+	  a_entry = a->bits + a->h*((unsigned int)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*((unsigned int)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 = ((unsigned int)(a->w - 1))/BITMASK_W_LEN - (unsigned int)xoffset/BITMASK_W_LEN;
+	  bstripes = ((unsigned int)(b->w - 1))/BITMASK_W_LEN + 1;
+	  if (bstripes > astripes) /* zig-zag .. zig*/
+	    {
+	      for (i=0;i<astripes;i++)
+		{
+		  for (ap = a_entry, app = ap + a->h, bp = b_entry;ap < a_end;) 
+		    if ((*ap++ >> shift) & *bp || (*app++ << rshift) & *bp++) return 1;
+		  a_entry += a->h;
+		  a_end += a->h;
+		  b_entry += b->h;
+		}
+	      for (ap = a_entry,bp = b_entry;ap < a_end;)
+		  if ((*ap++ >> shift) & *bp++) return 1;
+	      return 0;
+	    }
+	  else /* zig-zag */
+	    {
+	      for (i=0;i<bstripes;i++)
+		{
+		  for (ap = a_entry, app = ap + a->h, bp = b_entry;ap < a_end;) 
+		    if ((*ap++ >> shift) & *bp || (*app++ << rshift) & *bp++) return 1;
+		  a_entry += a->h;
+		  a_end += a->h;
+		  b_entry += b->h;
+		}
+	      return 0;
+	    }
+	}
+      else /* xoffset is a multiple of the stripe width, and the above routines wont 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;ap < a_end;)
+		if (*ap++ & *bp++) return 1;
+	      a_entry += a->h;
+	      a_end += a->h;
+	      b_entry += b->h;
+	    }
+	  return 0;
+	}
+    }
+  else  
+    {
+      const bitmask_t *c = a;
+      a = b;
+      b = c;
+      xoffset *= -1;
+      yoffset *= -1;
+      goto swapentry;
+    }
+}
+
+/* Will hang if there are no bits set in w! */
+static INLINE int firstsetbit(BITMASK_W w)
+{
+  int i = 0;
+  while ((w & 1) == 0) 
+    {
+      i++;
+      w/=2;
+    }
+  return i;
+}
+
+/* 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_t *a, const bitmask_t *b, int xoffset, int yoffset, int *x, int *y)
+{
+  const BITMASK_W *a_entry,*a_end, *b_entry, *ap, *bp;
+  unsigned int shift,rshift,i,astripes,bstripes,xbase;
+  
+  if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h)) 
+      return 0;
+  
+  if (xoffset >= 0) 
+    {
+      xbase = xoffset/BITMASK_W_LEN; /* first stripe from mask a */
+      if (yoffset >= 0)
+	{
+	  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*xbase;
+	  a_end = a_entry + MIN(b->h + yoffset,a->h);
+	  b_entry = b->bits - yoffset;
+	  yoffset = 0; /* relied on below */
+	}
+      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;ap < a_end;ap++,bp++)
+		      if (*ap & (*bp << shift)) 
+			{
+			  *y = ap - a_entry + yoffset;
+			  *x = (xbase + i)*BITMASK_W_LEN + firstsetbit(*ap & (*bp << shift));
+			  return 1;
+			}
+		  a_entry += a->h;
+		  a_end += a->h;
+		  for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
+		      if (*ap & (*bp >> rshift)) 
+			{
+			  *y = ap - a_entry + yoffset;
+			  *x = (xbase + i + 1)*BITMASK_W_LEN + firstsetbit(*ap & (*bp >> rshift));
+			  return 1;
+			}
+		  b_entry += b->h;
+		}
+	      for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
+		if (*ap & (*bp << shift)) 
+		  {
+		    *y = ap - a_entry + yoffset;
+		    *x = (xbase + astripes)*BITMASK_W_LEN + firstsetbit(*ap & (*bp << shift));
+		    return 1;
+		  }
+	      return 0;
+	    }
+	  else /* zig-zag */
+	    {
+	      for (i=0;i<bstripes;i++)
+		{
+		  for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
+		      if (*ap & (*bp << shift)) 
+			{
+			  *y = ap - a_entry + yoffset;
+			  *x = (xbase + i)*BITMASK_W_LEN + firstsetbit(*ap & (*bp << shift));
+			  return 1;
+			}
+		  a_entry += a->h;
+		  a_end += a->h;
+		  for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
+		      if (*ap & (*bp >> rshift)) 
+			{
+			  *y = ap - a_entry + yoffset;
+			  *x = (xbase + i + 1)*BITMASK_W_LEN + firstsetbit(*ap & (*bp >> rshift));
+			  return 1;
+			}
+		  b_entry += b->h;
+		}
+	      return 0;
+	    }
+	}
+      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)/BITMASK_W_LEN + 1;
+	  for (i=0;i<astripes;i++)
+	    {
+	      for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
+		{
+		  if (*ap & *bp)
+		    {
+		      *y = ap - a_entry + yoffset;
+		      *x = (xbase + i)*BITMASK_W_LEN + firstsetbit(*ap & *bp); 
+		      return 1;
+		    }
+		}
+	      a_entry += a->h;
+	      a_end += a->h;
+	      b_entry += b->h;
+	    }
+	  return 0;
+	}
+    }
+  else  
+    {
+      if (bitmask_overlap_pos(b,a,-xoffset,-yoffset,x,y))
+	{
+	  *x += xoffset;
+	  *y += yoffset;
+	  return 1;
+	}
+      else
+	return 0;
+    }
+}
+
+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;
+  unsigned int shift,rshift,i,astripes,bstripes;
+  unsigned int count = 0;
+
+  if ((xoffset >= a->w) || (yoffset >= a->h) || (b->h + yoffset <= 0) || (b->w + xoffset <= 0)) 
+      return 0;
+  
+  if (xoffset >= 0) 
+    {
+    swapentry:
+      if (yoffset >= 0)
+	{
+	  a_entry = a->bits + a->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);
+	  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;ap < a_end;ap++,bp++)
+		    count += bitcount(((*ap >> shift) | (*(ap + a->h) << rshift)) & *bp);
+		  a_entry += a->h;
+		  a_end += a->h;
+		  b_entry += b->h;
+		}
+	      for (ap = a_entry,bp = b_entry;ap < a_end;)
+		count += bitcount((*ap++ >> shift) & *bp++);
+	      return count;
+	    }
+	  else /* zig-zag */
+	    {
+	      for (i=0;i<bstripes;i++)
+		{
+		  for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
+		    count += bitcount(((*ap >> shift) | (*(ap + a->h) << rshift)) & *bp);
+		  a_entry += a->h;
+		  a_end += a->h;
+		  b_entry += b->h;
+		}
+	      return count;
+	    }
+	}
+      else /* xoffset is a multiple of the stripe width, and the above routines wont 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;ap < a_end;)
+		count += bitcount(*ap++ & *bp++);
+
+	      a_entry += a->h;
+	      a_end += a->h;
+	      b_entry += b->h;
+	    }
+	  return count;
+	}
+    }
+  else  
+    {
+      const bitmask_t *c = a;
+      a = b;
+      b = c;
+      xoffset *= -1;
+      yoffset *= -1;
+      goto swapentry;
+    }
+}
+
+/* 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)
+{
+  BITMASK_W *a_entry,*a_end, *ap;
+  const BITMASK_W *b_entry, *b_end, *bp;
+  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;
+	  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);
+	  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;ap < a_end;ap++,bp++)
+		    *ap |= (*bp << shift);
+		  a_entry += a->h;
+		  a_end += a->h;
+		  for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
+		    *ap |= (*bp >> rshift);
+		  b_entry += b->h;
+		}
+	      for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
+		*ap |= (*bp << shift);
+	    }
+	  else /* zig-zag */
+	    {
+	      for (i=0;i<bstripes;i++)
+		{
+		  for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
+		    *ap |= (*bp << shift);
+		  a_entry += a->h;
+		  a_end += a->h;
+		  for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
+		    *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;ap < a_end;ap++,bp++)
+		{
+		  *ap |= *bp;
+		}
+	      a_entry += a->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;
+	}
+      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;
+	}
+      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;bp < b_end;bp++,ap++)
+		    *ap |= (*bp >> shift);
+		  b_entry += b->h;
+		  b_end += b->h;
+		  for (bp = b_entry,ap = a_entry;bp < b_end;bp++,ap++)
+		    *ap |= (*bp <<rshift); 
+		  a_entry += a->h;
+		}
+	      for (bp = b_entry,ap = a_entry;bp < b_end;bp++,ap++)
+		*ap |= (*bp >> shift);
+	    }
+	  else /* zig-zag */
+	    {
+	      for (i=0;i<bstripes;i++)
+		{
+		  for (bp = b_entry,ap = a_entry;bp < b_end;bp++,ap++)
+		    *ap |= (*bp >> shift);
+		  b_entry += b->h;
+		  b_end += b->h;
+		  for (bp = b_entry,ap = a_entry;bp < b_end;bp++,ap++)
+		    *ap |= (*bp << rshift);
+		  a_entry += a->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;bp < b_end;bp++,ap++)
+		{
+		  *ap |= *bp;
+		}
+	      b_entry += b->h;
+	      b_end += b->h;
+	      a_entry += a->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 > a->w)
+    {
+      BITMASK_W edgemask;
+      int n = a->w/BITMASK_W_LEN;
+      shift = (n + 1)*BITMASK_W_LEN - a->w;
+      edgemask = (~(BITMASK_W)0) >> shift;
+      a_end = a->bits + n*a->h + MIN(a->h,b->h + yoffset);
+      for (ap = a->bits + n*a->h + MAX(yoffset,0);ap<a_end;ap++)
+	*ap &= edgemask;
+    }
+}
+
+/* Erases mask b from mask a (a &= ~b) */
+void bitmask_erase(bitmask_t *a, const bitmask_t *b, int xoffset, int yoffset)
+{
+  BITMASK_W *a_entry,*a_end, *ap;
+  const BITMASK_W *b_entry, *b_end, *bp;
+  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;
+	  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);
+	  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;ap < a_end;ap++,bp++)
+		    *ap &= ~(*bp << shift);
+		  a_entry += a->h;
+		  a_end += a->h;
+		  for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
+		    *ap &= ~(*bp >> rshift);
+		  b_entry += b->h;
+		}
+	      for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
+		*ap &= ~(*bp << shift);
+	    }
+	  else /* zig-zag */
+	    {
+	      for (i=0;i<bstripes;i++)
+		{
+		  for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
+		    *ap &= ~(*bp << shift);
+		  a_entry += a->h;
+		  a_end += a->h;
+		  for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
+		    *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;ap < a_end;ap++,bp++)
+		{
+		  *ap &= ~*bp;
+		}
+	      a_entry += a->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;
+	}
+      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;
+	}
+      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;bp < b_end;bp++,ap++)
+		    *ap &= ~(*bp >> shift);
+		  b_entry += b->h;
+		  b_end += b->h;
+		  for (bp = b_entry,ap = a_entry;bp < b_end;bp++,ap++)
+		    *ap &= ~(*bp <<rshift); 
+		  a_entry += a->h;
+		}
+	      for (bp = b_entry,ap = a_entry;bp < b_end;bp++,ap++)
+		*ap |= (*bp >> shift);
+	    }
+	  else /* zig-zag */
+	    {
+	      for (i=0;i<bstripes;i++)
+		{
+		  for (bp = b_entry,ap = a_entry;bp < b_end;bp++,ap++)
+		    *ap &= ~(*bp >> shift);
+		  b_entry += b->h;
+		  b_end += b->h;
+		  for (bp = b_entry,ap = a_entry;bp < b_end;bp++,ap++)
+		    *ap &= ~(*bp << rshift);
+		  a_entry += a->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;bp < b_end;bp++,ap++)
+		*ap &= ~*bp;
+	      b_entry += b->h;
+	      b_end += b->h;
+	      a_entry += a->h;
+	    }
+	}
+    }	
+}
+
+
+
+bitmask_t *bitmask_scale(const bitmask_t *m, int w, int h)
+{
+  bitmask_t *nm;
+  int x,y,nx,ny,dx,dy,dnx,dny;
+
+  if (w < 1 || h < 1)
+    {
+      nm = bitmask_create(1,1);
+      return nm;
+    }
+
+  nm = bitmask_create(w,h);
+  if (!nm)
+    return NULL;
+  ny = dny = 0;
+  for (y=0,dy=h; y<m->h; y++,dy+=h)
+    {      
+      while (dny < dy)
+	{
+	  nx = dnx = 0;
+	  for (x=0,dx=w; x < m->w; x++, dx+=w)
+	    {
+	      if (bitmask_getbit(m,x,y))
+		{
+		  while (dnx < dx)
+		    {
+		      bitmask_setbit(nm,nx,ny);
+		      nx++;
+		      dnx += m->w;
+		    }
+		}
+	      else
+		{
+		  while (dnx < dx)
+		    {
+		      nx++;
+		      dnx += m->w;
+		    }
+		}
+	    }
+	  ny++;
+	  dny+=m->h;
+	}
+    }
+  return nm;
+}
+

Added: pygame/src/bitmask.h
===================================================================
--- pygame/src/bitmask.h	                        (rev 0)
+++ pygame/src/bitmask.h	2008-12-03 23:43:41 UTC (rev 116)
@@ -0,0 +1,138 @@
+/*
+    Bitmask 1.7 - A pixel-perfect collision detection library.
+
+    Copyright (C) 2002-2005 Ulf Ekstrom except for the bitcount
+    function which is copyright (C) Donald W. Gillies, 1992.
+  
+    This library is free software; you can redistribute it and/or
+    modify it under the terms of the GNU Library General Public
+    License as published by the Free Software Foundation; either
+    version 2 of the License, or (at your option) any later version.
+ 
+    This library is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+    Library General Public License for more details.
+ 
+    You should have received a copy of the GNU Library General Public
+    License along with this library; if not, write to the Free
+    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+#ifndef BITMASK_H
+#define BITMASK_H
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include <limits.h>
+/* Define INLINE for different compilers.  If your compiler does not
+   support inlining then there might be a performance hit in
+   bitmask_overlap_area().
+*/
+#ifndef INLINE
+# ifdef __GNUC__
+#  define INLINE inline
+# else
+#  ifdef _MSC_VER
+#   define INLINE __inline
+#  else
+#   define INLINE
+#  endif
+# endif
+#endif
+
+#define BITMASK_W unsigned long int
+#define BITMASK_W_LEN (sizeof(BITMASK_W)*CHAR_BIT)
+#define BITMASK_W_MASK (BITMASK_W_LEN - 1)
+#define BITMASK_N(n) ((BITMASK_W)1 << (n))
+
+typedef struct bitmask
+{
+  int w,h;
+  BITMASK_W bits[1];
+} bitmask_t;
+
+/* Creates a bitmask of width w and height h, where
+   w and h must both be greater than 0.
+   The mask is automatically cleared when created.
+ */
+bitmask_t *bitmask_create(int w, int h);
+
+/* Frees all the memory allocated by bitmask_create for m. */
+void bitmask_free(bitmask_t *m);
+
+/* Clears all bits in the mask */
+void bitmask_clear(bitmask_t *m);
+
+/* Sets all bits in the mask */
+void bitmask_fill(bitmask_t *m);
+
+/* Flips all bits in the mask */
+void bitmask_invert(bitmask_t *m);
+
+/* Counts the bits in the mask */
+unsigned int bitmask_count(bitmask_t *m);
+
+/* Returns nonzero if the bit at (x,y) is set.  Coordinates start at
+   (0,0) */
+static INLINE int bitmask_getbit(const bitmask_t *m, int x, int y) 
+{ 
+  return (m->bits[x/BITMASK_W_LEN*m->h + y] & BITMASK_N(x & BITMASK_W_MASK)) != 0;
+}
+
+/* Sets the bit at (x,y) */
+static INLINE void bitmask_setbit(bitmask_t *m, int x, int y)
+{ 
+  m->bits[x/BITMASK_W_LEN*m->h + y] |= BITMASK_N(x & BITMASK_W_MASK); 
+}
+
+/* Clears the bit at (x,y) */
+static INLINE void bitmask_clearbit(bitmask_t *m, int x, int y)
+{ 
+  m->bits[x/BITMASK_W_LEN*m->h + y] &= ~BITMASK_N(x & BITMASK_W_MASK); 
+}
+
+/* Returns nonzero if the masks overlap with the given offset. 
+   The overlap tests uses the following offsets (which may be negative):
+
+   +----+----------..
+   |A   | yoffset   
+   |  +-+----------..
+   +--|B        
+   |xoffset      
+   |  |
+   :  :  
+*/
+int bitmask_overlap(const bitmask_t *a, const bitmask_t *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 there is no overlap. */
+int bitmask_overlap_pos(const bitmask_t *a, const bitmask_t *b,
+			int xoffset, int yoffset, int *x, int *y);
+
+/* Returns the number of overlapping 'pixels' */
+int bitmask_overlap_area(const bitmask_t *a, const bitmask_t *b, int xoffset, int yoffset);
+
+/* Fills a mask with the overlap of two other masks. A bitwise AND. */
+void bitmask_overlap_mask (const bitmask_t *a, const bitmask_t *b, bitmask_t *c, int xoffset, int yoffset);
+
+/* Draws mask b onto mask a (bitwise OR). Can be used to compose large
+   (game background?) mask from several submasks, which may speed up
+   the testing. */
+
+void bitmask_draw(bitmask_t *a, const bitmask_t *b, int xoffset, int yoffset);
+
+void bitmask_erase(bitmask_t *a, const bitmask_t *b, int xoffset, int yoffset);
+
+/* Return a new scaled bitmask, with dimensions w*h. The quality of the
+   scaling may not be perfect for all circumstances, but it should
+   be reasonable. If either w or h is 0 a clear 1x1 mask is returned. */
+bitmask_t *bitmask_scale(const bitmask_t *m, int w, int h);
+
+#ifdef __cplusplus
+} /* End of extern "C" { */
+#endif
+
+#endif


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.