src/hd/clumpbeams.c

#ifndef lint
static const char       RCSid[] = "$Id: clumpbeams.c,v 3.5 2003/07/21 22:30:18 schorsch Exp $";
#endif
/*
 * Bundle holodeck beams together into clumps.
 */

#include "holo.h"

#define flgop(p,i,op)           ((p)[(i)>>5] op (1L<<((i)&0x1f)))
#define isset(p,i)              flgop(p,i,&)
#define setfl(p,i)              flgop(p,i,|=)
#define clrfl(p,i)              flgop(p,i,&=~)

static int      bneighlist[9*9-1];
static int      bneighrem;

#define nextneigh()     (bneighrem<=0 ? 0 : bneighlist[--bneighrem])


gcshifti(gc, ia, di, hp)        /* shift cell row or column */
register GCOORD *gc;
int     ia, di;
register HOLO   *hp;
{
        int     nw;

        if (di > 0) {
                if (++gc->i[ia] >= hp->grid[((gc->w>>1)+1+ia)%3]) {
                        nw = ((gc->w&~1) + (ia<<1) + 3) % 6;
                        gc->i[ia] = gc->i[1-ia];
                        gc->i[1-ia] = gc->w&1 ? hp->grid[((nw>>1)+2-ia)%3]-1 : 0;
                        gc->w = nw;
                }
        } else if (di < 0) {
                if (--gc->i[ia] < 0) {
                        nw = ((gc->w&~1) + (ia<<1) + 2) % 6;
                        gc->i[ia] = gc->i[1-ia];
                        gc->i[1-ia] = gc->w&1 ? hp->grid[((nw>>1)+2-ia)%3]-1 : 0;
                        gc->w = nw;
                }
        }
}


mkneighgrid(ng, hp, gc)         /* compute neighborhood for grid cell */
GCOORD  ng[3*3];
HOLO    *hp;
GCOORD  *gc;
{
        GCOORD  gci0;
        register int    i, j;

        for (i = 3; i--; ) {
                gci0 = *gc;
                gcshifti(&gci0, 0, i-1, hp);
                for (j = 3; j--; ) {
                        *(ng+(3*i+j)) = gci0;
                        gcshifti(ng+(3*i+j), gci0.w==gc->w, j-1, hp);
                }
        }
}


static int
firstneigh(hp, b)               /* initialize neighbor list and return first */
HOLO    *hp;
int     b;
{
        GCOORD  wg0[9], wg1[9], bgc[2];
        int     i, j;

        hdbcoord(bgc, hp, b);
        mkneighgrid(wg0, hp, bgc);
        mkneighgrid(wg1, hp, bgc+1);
        bneighrem = 0;
        for (i = 9; i--; )
                for (j = 9; j--; ) {
                        if ((i == 4) & (j == 4))        /* don't copy starting beam */
                                continue;
                        if (wg0[i].w == wg1[j].w)
                                continue;
                        *bgc = *(wg0+i);
                        *(bgc+1) = *(wg1+j);
                        bneighlist[bneighrem++] = hdbindex(hp, bgc);
#ifdef DEBUG
                        if (bneighlist[bneighrem-1] <= 0)
                                error(CONSISTENCY, "bad beam in firstneigh");
#endif
                }
        return(nextneigh());
}


clumpbeams(hp, maxcnt, maxsiz, cf)      /* clump beams from hinp */
register HOLO   *hp;
int     maxcnt, maxsiz;
int     (*cf)();
{
        static short    primes[] = {9431,6803,4177,2659,1609,887,587,251,47,1};
        uint32  *bflags;
        int     *bqueue;
        int     bqlen;
        int32   bqtotal;
        int     bc, bci, bqc, myprime;
        register int    i;
                                        /* get clump size */
        if (maxcnt <= 1)
                maxcnt = nbeams(hp);
        maxsiz /= sizeof(RAYVAL);
                                        /* allocate beam queue */
        bqueue = (int *)malloc(maxcnt*sizeof(int));
        bflags = (uint32 *)calloc((nbeams(hp)>>5)+1,
                        sizeof(uint32));
        if ((bqueue == NULL) | (bflags == NULL))
                error(SYSTEM, "out of memory in clumpbeams");
                                        /* mark empty beams as done */
        for (i = nbeams(hp); i > 0; i--)
                if (!bnrays(hp, i))
                        setfl(bflags, i);
                                        /* pick a good prime step size */
        for (i = 0; primes[i]<<5 >= nbeams(hp); i++)
                ;
        while ((myprime = primes[i++]) > 1)
                if (nbeams(hp) % myprime)
                        break;
                                        /* add each input beam and neighbors */
        for (bc = bci = nbeams(hp); bc > 0; bc--,
                        bci += bci>myprime ? -myprime : nbeams(hp)-myprime) {
                if (isset(bflags, bci))
                        continue;
                bqueue[0] = bci;                /* initialize queue */
                bqlen = 1;
                bqtotal = bnrays(hp, i);
                setfl(bflags, bci);
                                                /* run through growing queue */
                for (bqc = 0; bqc < bqlen; bqc++) {
                                                /* add neighbors until full */
                        for (i = firstneigh(hp,bqueue[bqc]); i > 0;
                                        i = nextneigh()) {
                                if (isset(bflags, i))   /* done already? */
                                        continue;
                                bqueue[bqlen++] = i;    /* add it */
                                bqtotal += bnrays(hp, i);
                                setfl(bflags, i);
                                if (bqlen >= maxcnt ||
                                                (maxsiz && bqtotal >= maxsiz))
                                        break;          /* queue full */
                        }
                        if (i > 0)
                                break;
                }
                (*cf)(hp, bqueue, bqlen);       /* transfer clump */
        }
                                        /* all done; clean up */
        free((void *)bqueue);
        free((void *)bflags);
}
Revision:	3.6
Committed:	Sun Jul 27 22:12:02 2003 UTC (20 years, 8 months ago) by schorsch
Content type:	text/plain
Branch:	MAIN
Changes since 3.5:	+3 -3 lines
Log Message:	Added grouping parens to reduce ambiguity warnings.
#	User	Rev	Content
1	gwlarson	3.1	#ifndef lint
2	schorsch	3.6	static const char RCSid[] = "$Id: clumpbeams.c,v 3.5 2003/07/21 22:30:18 schorsch Exp $";
3	gwlarson	3.1	#endif
4			/*
5			* Bundle holodeck beams together into clumps.
6			*/
7
8			#include "holo.h"
9
10			#define flgop(p,i,op) ((p)[(i)>>5] op (1L<<((i)&0x1f)))
11			#define isset(p,i) flgop(p,i,&)
12			#define setfl(p,i) flgop(p,i,\|=)
13			#define clrfl(p,i) flgop(p,i,&=~)
14
15			static int bneighlist[9*9-1];
16			static int bneighrem;
17
18			#define nextneigh() (bneighrem<=0 ? 0 : bneighlist[--bneighrem])
19
20
21			gcshifti(gc, ia, di, hp) /* shift cell row or column */
22			register GCOORD *gc;
23			int ia, di;
24			register HOLO *hp;
25			{
26			int nw;
27
28			if (di > 0) {
29			if (++gc->i[ia] >= hp->grid[((gc->w>>1)+1+ia)%3]) {
30			nw = ((gc->w&~1) + (ia<<1) + 3) % 6;
31			gc->i[ia] = gc->i[1-ia];
32			gc->i[1-ia] = gc->w&1 ? hp->grid[((nw>>1)+2-ia)%3]-1 : 0;
33			gc->w = nw;
34			}
35			} else if (di < 0) {
36			if (--gc->i[ia] < 0) {
37			nw = ((gc->w&~1) + (ia<<1) + 2) % 6;
38			gc->i[ia] = gc->i[1-ia];
39			gc->i[1-ia] = gc->w&1 ? hp->grid[((nw>>1)+2-ia)%3]-1 : 0;
40			gc->w = nw;
41			}
42			}
43			}
44
45
46			mkneighgrid(ng, hp, gc) /* compute neighborhood for grid cell */
47			GCOORD ng[3*3];
48			HOLO *hp;
49			GCOORD *gc;
50			{
51			GCOORD gci0;
52			register int i, j;
53
54			for (i = 3; i--; ) {
55	schorsch	3.5	gci0 = *gc;
56	gwlarson	3.1	gcshifti(&gci0, 0, i-1, hp);
57			for (j = 3; j--; ) {
58	schorsch	3.5	(ng+(3i+j)) = gci0;
59	gwlarson	3.1	gcshifti(ng+(3*i+j), gci0.w==gc->w, j-1, hp);
60			}
61			}
62			}
63
64
65			static int
66			firstneigh(hp, b) /* initialize neighbor list and return first */
67			HOLO *hp;
68			int b;
69			{
70			GCOORD wg0[9], wg1[9], bgc[2];
71			int i, j;
72
73			hdbcoord(bgc, hp, b);
74			mkneighgrid(wg0, hp, bgc);
75			mkneighgrid(wg1, hp, bgc+1);
76			bneighrem = 0;
77			for (i = 9; i--; )
78			for (j = 9; j--; ) {
79	schorsch	3.6	if ((i == 4) & (j == 4)) /* don't copy starting beam */
80	gwlarson	3.1	continue;
81			if (wg0[i].w == wg1[j].w)
82			continue;
83	schorsch	3.5	bgc = (wg0+i);
84			(bgc+1) = (wg1+j);
85	gwlarson	3.1	bneighlist[bneighrem++] = hdbindex(hp, bgc);
86			#ifdef DEBUG
87			if (bneighlist[bneighrem-1] <= 0)
88			error(CONSISTENCY, "bad beam in firstneigh");
89			#endif
90			}
91			return(nextneigh());
92			}
93
94
95	gwlarson	3.2	clumpbeams(hp, maxcnt, maxsiz, cf) /* clump beams from hinp */
96	gwlarson	3.1	register HOLO *hp;
97			int maxcnt, maxsiz;
98	gwlarson	3.2	int (*cf)();
99	gwlarson	3.1	{
100			static short primes[] = {9431,6803,4177,2659,1609,887,587,251,47,1};
101	greg	3.4	uint32 *bflags;
102	gwlarson	3.1	int *bqueue;
103			int bqlen;
104	greg	3.4	int32 bqtotal;
105	gwlarson	3.1	int bc, bci, bqc, myprime;
106			register int i;
107			/* get clump size */
108			if (maxcnt <= 1)
109			maxcnt = nbeams(hp);
110			maxsiz /= sizeof(RAYVAL);
111			/* allocate beam queue */
112			bqueue = (int )malloc(maxcntsizeof(int));
113	greg	3.4	bflags = (uint32 *)calloc((nbeams(hp)>>5)+1,
114			sizeof(uint32));
115	schorsch	3.6	if ((bqueue == NULL) \| (bflags == NULL))
116	gwlarson	3.1	error(SYSTEM, "out of memory in clumpbeams");
117			/* mark empty beams as done */
118			for (i = nbeams(hp); i > 0; i--)
119			if (!bnrays(hp, i))
120			setfl(bflags, i);
121			/* pick a good prime step size */
122			for (i = 0; primes[i]<<5 >= nbeams(hp); i++)
123			;
124			while ((myprime = primes[i++]) > 1)
125			if (nbeams(hp) % myprime)
126			break;
127			/* add each input beam and neighbors */
128			for (bc = bci = nbeams(hp); bc > 0; bc--,
129			bci += bci>myprime ? -myprime : nbeams(hp)-myprime) {
130			if (isset(bflags, bci))
131			continue;
132			bqueue[0] = bci; /* initialize queue */
133			bqlen = 1;
134			bqtotal = bnrays(hp, i);
135			setfl(bflags, bci);
136			/* run through growing queue */
137			for (bqc = 0; bqc < bqlen; bqc++) {
138			/* add neighbors until full */
139			for (i = firstneigh(hp,bqueue[bqc]); i > 0;
140			i = nextneigh()) {
141			if (isset(bflags, i)) /* done already? */
142			continue;
143			bqueue[bqlen++] = i; /* add it */
144			bqtotal += bnrays(hp, i);
145			setfl(bflags, i);
146			if (bqlen >= maxcnt \|\|
147			(maxsiz && bqtotal >= maxsiz))
148			break; /* queue full */
149			}
150			if (i > 0)
151			break;
152			}
153	gwlarson	3.2	(cf)(hp, bqueue, bqlen); / transfer clump */
154	gwlarson	3.1	}
155	gwlarson	3.2	/* all done; clean up */
156	greg	3.3	free((void *)bqueue);
157			free((void *)bflags);
158	gwlarson	3.1	}