#include <stdio.h>

//#include <string.h>

#include <stdlib.h>

//#include <signal.h>

//#include <errno.h>


int pixels = 0, sqcalls = 0, subcalls = 0;

#define TRUE (0==0)

#define FALSE (!TRUE)


#define HAVE_FULLY_TOUCHING_TEST 1


int touching(int xl, int yb, int w) // test if any pixels touch our square

{
    // test usoing a square of 100x100 at 150, 200.  Pixels should be 10,000

    if (xl+w <= 150) return FALSE;
    if (xl >=  150+100) return FALSE;
    if (yb+w <= 200) return FALSE;
    if (yb >= 200+100) return FALSE;
    return TRUE;
}

#ifdef HAVE_FULLY_TOUCHING_TEST

int fully_touching(int xl, int yb, int w) // test that all pixels match our square

{
    // test usoing a square of 100x100 at 150, 200.  Pixels should be 10,000

    if ((xl >=  150)
        && (xl+w <= 150+100)
        && (yb >= 200)
        && (yb+w <= 200+100)) return TRUE;
    return FALSE;
}
#endif


void sq(int xl, int yb, int w)
{
    int half = w>>1;
    sqcalls++;
    printf("sq(%d,%d, %d);\n", xl, yb, w);
#ifdef HAVE_FULLY_TOUCHING_TEST

    if (fully_touching(xl, yb, w)) {pixels+=w*w; return;}
#endif

    if (!touching(xl, yb, w)) return;
    if (w == 1) {pixels++; return;}
    sq(xl, yb, half);
    sq(xl+half, yb, half);
    sq(xl, yb+half, half);
    sq(xl+half, yb+half, half);
}

void subdivide(int xl, int yb, int xr, int yt)
// params are: xleft ybottom xright ytop

// lower bound inclusive, upper bound exclusive

{
  int w, h, len, SQ;

  subcalls++;
  
  w = xr-xl; h = yt-yb;
  len = (w > h ? h : w);

  if (len >= 256) SQ = 256;
  else if (len >= 128) SQ = 128;
  else if (len >= 64) SQ = 64;
  else if (len >= 32) SQ = 32;
  else if (len >= 16) SQ = 16;
  else if (len >= 8) SQ = 8;
  else if (len >= 4) SQ = 4;
  else if (len >= 2) SQ = 2;
  else SQ = 1;

  /* Subdivision into squares which match sprite sizes:

  +-----------------+-------+ yt
  |                 |       |
  |                 |       |
  +-----------------+-------+ yb+SQ
  |                 |       |
  |                 |       |
  |                 |       |
  |                 |       |
  |                 |       |
  |                 |       |
  |                 |       |
  +-----------------+-------+ yb
 xl                xl+SQ    xr   
  */  
  sq(xl, yb, SQ);
  if (xl+SQ<xr) subdivide(xl+SQ,yb,  xr, yb+SQ);
  if (yb+SQ<yt) subdivide(xl, yb+SQ, xl+SQ, yt);
  if ((xl+SQ<xr) && (yb+SQ<yt)) subdivide(xl+SQ, yb+SQ, xr, yt);  
}

int main(int argc, char **argv) {
    //    fprintf(stderr, "sizeof(long long) = %d\n", sizeof(long long));

    //    fprintf(stderr, "sizeof(long long *) = %d\n", sizeof(long long *));

    subdivide(0,0, 480, 340);
    fprintf(stderr, "%d pixels, %d subdivisions, %d pixel tests\n", pixels, subcalls, sqcalls);
    exit(0); return(1);
}