src/common/hilbert.h

/* C header file for Hilbert curve functions */
#if !defined(_hilbert_h_)
#define _hilbert_h_

#ifdef __cplusplus
extern "C" {
#endif

/* define the bitmask_t type as an integer of sufficient size */
typedef unsigned long long bitmask_t;
/* define the halfmask_t type as an integer of 1/2 the size of bitmask_t */
typedef unsigned long halfmask_t;

/*****************************************************************
 * hilbert_i2c
 * 
 * Convert an index into a Hilbert curve to a set of coordinates.
 * Inputs:
 *  nDims:      Number of coordinate axes.
 *  nBits:      Number of bits per axis.
 *  index:      The index, contains nDims*nBits bits (so nDims*nBits must be <= 8*sizeof(bitmask_t)).
 * Outputs:
 *  coord:      The list of nDims coordinates, each with nBits bits.
 * Assumptions:
 *      nDims*nBits <= (sizeof index) * (bits_per_byte)
 */

void hilbert_i2c(unsigned nDims, unsigned nBits, bitmask_t index, bitmask_t coord[]);

/*****************************************************************
 * hilbert_c2i
 * 
 * Convert coordinates of a point on a Hilbert curve to its index.
 * Inputs:
 *  nDims:      Number of coordinates.
 *  nBits:      Number of bits/coordinate.
 *  coord:      Array of n nBits-bit coordinates.
 * Outputs:
 *  index:      Output index value.  nDims*nBits bits.
 * Assumptions:
 *      nDims*nBits <= (sizeof bitmask_t) * (bits_per_byte)
 */

bitmask_t hilbert_c2i(unsigned nDims, unsigned nBits, bitmask_t const coord[]);

/*****************************************************************
 * hilbert_cmp, hilbert_ieee_cmp
 * 
 * Determine which of two points lies further along the Hilbert curve
 * Inputs:
 *  nDims:      Number of coordinates.
 *  nBytes:     Number of bytes of storage/coordinate (hilbert_cmp only)
 *  nBits:      Number of bits/coordinate. (hilbert_cmp only)
 *  coord1:     Array of nDims nBytes-byte coordinates (or doubles for ieee_cmp).
 *  coord2:     Array of nDims nBytes-byte coordinates (or doubles for ieee_cmp).
 * Return value:
 *      -1, 0, or 1 according to whether
           coord1<coord2, coord1==coord2, coord1>coord2
 * Assumptions:
 *      nBits <= (sizeof bitmask_t) * (bits_per_byte)
 */

int hilbert_cmp(unsigned nDims, unsigned nBytes, unsigned nBits, void const* coord1, void const* coord2);
int hilbert_ieee_cmp(unsigned nDims, double const* coord1, double const* coord2);

/*****************************************************************
 * hilbert_box_vtx
 * 
 * Determine the first or last vertex of a box to lie on a Hilbert curve
 * Inputs:
 *  nDims:      Number of coordinates.
 *  nBytes:     Number of bytes/coordinate.
 *  nBits:      Number of bits/coordinate. (hilbert_box_vtx only)
 *  findMin:    Is it the least vertex sought?
 *  coord1:     Array of nDims nBytes-byte coordinates - one corner of box
 *  coord2:     Array of nDims nBytes-byte coordinates - opposite corner
 * Output:
 *      c1 and c2 modified to refer to selected corner
 *      value returned is log2 of size of largest power-of-two-aligned box that
 *      contains the selected corner and no other corners
 * Assumptions:
 *      nBits <= (sizeof bitmask_t) * (bits_per_byte)
 */
unsigned
hilbert_box_vtx(unsigned nDims, unsigned nBytes, unsigned nBits,
                int findMin, void* c1, void* c2);
unsigned
hilbert_ieee_box_vtx(unsigned nDims,
                     int findMin, double* c1, double* c2);

/*****************************************************************
 * hilbert_box_pt
 * 
 * Determine the first or last point of a box to lie on a Hilbert curve
 * Inputs:
 *  nDims:      Number of coordinates.
 *  nBytes:     Number of bytes/coordinate.
 *  nBits:      Number of bits/coordinate.
 *  findMin:    Is it the least vertex sought?
 *  coord1:     Array of nDims nBytes-byte coordinates - one corner of box
 *  coord2:     Array of nDims nBytes-byte coordinates - opposite corner
 * Output:
 *      c1 and c2 modified to refer to least point
 * Assumptions:
 *      nBits <= (sizeof bitmask_t) * (bits_per_byte)
 */
unsigned
hilbert_box_pt(unsigned nDims, unsigned nBytes, unsigned nBits,
               int findMin, void* coord1, void* coord2);
unsigned
hilbert_ieee_box_pt(unsigned nDims,
                    int findMin, double* c1, double* c2);

/*****************************************************************
 * hilbert_nextinbox
 * 
 * Determine the first point of a box after a given point to lie on a Hilbert curve
 * Inputs:
 *  nDims:      Number of coordinates.
 *  nBytes:     Number of bytes/coordinate.
 *  nBits:      Number of bits/coordinate.
 *  findPrev:   Is the previous point sought?
 *  coord1:     Array of nDims nBytes-byte coordinates - one corner of box
 *  coord2:     Array of nDims nBytes-byte coordinates - opposite corner
 *  point:      Array of nDims nBytes-byte coordinates - lower bound on point returned
 *  
 * Output:
      if returns 1:
 *      c1 and c2 modified to refer to least point after "point" in box
      else returns 0:
        arguments unchanged; "point" is beyond the last point of the box
 * Assumptions:
 *      nBits <= (sizeof bitmask_t) * (bits_per_byte)
 */
int
hilbert_nextinbox(unsigned nDims, unsigned nBytes, unsigned nBits,
                  int findPrev, void* coord1, void* coord2,
                  void const* point);

/*****************************************************************
 * hilbert_incr
 * 
 * Advance from one point to its successor on a Hilbert curve
 * Inputs:
 *  nDims:      Number of coordinates.
 *  nBits:      Number of bits/coordinate.
 *  coord:      Array of nDims nBits-bit coordinates.
 * Output:
 *  coord:      Next point on Hilbert curve
 * Assumptions:
 *      nBits <= (sizeof bitmask_t) * (bits_per_byte)
 */

void
hilbert_incr(unsigned nDims, unsigned nBits, bitmask_t coord[]);

#ifdef __cplusplus
}
#endif

#endif /* _hilbert_h_ */
Revision:	3.1
Committed:	Fri Feb 18 00:40:25 2011 UTC (14 years, 8 months ago) by greg
Content type:	text/plain
Branch:	MAIN
Log Message:	Major code reorg, moving mgflib to common and introducing BSDF material
#	User	Rev	Content
1	greg	3.1	/* C header file for Hilbert curve functions */
2			#if !defined(_hilbert_h_)
3			#define _hilbert_h_
4
5			#ifdef __cplusplus
6			extern "C" {
7			#endif
8
9			/* define the bitmask_t type as an integer of sufficient size */
10			typedef unsigned long long bitmask_t;
11			/* define the halfmask_t type as an integer of 1/2 the size of bitmask_t */
12			typedef unsigned long halfmask_t;
13
14			/*****************************************************************
15			* hilbert_i2c
16			*
17			* Convert an index into a Hilbert curve to a set of coordinates.
18			* Inputs:
19			* nDims: Number of coordinate axes.
20			* nBits: Number of bits per axis.
21			* index: The index, contains nDimsnBits bits (so nDimsnBits must be <= 8*sizeof(bitmask_t)).
22			* Outputs:
23			* coord: The list of nDims coordinates, each with nBits bits.
24			* Assumptions:
25			* nDimsnBits <= (sizeof index) (bits_per_byte)
26			*/
27
28			void hilbert_i2c(unsigned nDims, unsigned nBits, bitmask_t index, bitmask_t coord[]);
29
30			/*****************************************************************
31			* hilbert_c2i
32			*
33			* Convert coordinates of a point on a Hilbert curve to its index.
34			* Inputs:
35			* nDims: Number of coordinates.
36			* nBits: Number of bits/coordinate.
37			* coord: Array of n nBits-bit coordinates.
38			* Outputs:
39			* index: Output index value. nDims*nBits bits.
40			* Assumptions:
41			* nDimsnBits <= (sizeof bitmask_t) (bits_per_byte)
42			*/
43
44			bitmask_t hilbert_c2i(unsigned nDims, unsigned nBits, bitmask_t const coord[]);
45
46			/*****************************************************************
47			* hilbert_cmp, hilbert_ieee_cmp
48			*
49			* Determine which of two points lies further along the Hilbert curve
50			* Inputs:
51			* nDims: Number of coordinates.
52			* nBytes: Number of bytes of storage/coordinate (hilbert_cmp only)
53			* nBits: Number of bits/coordinate. (hilbert_cmp only)
54			* coord1: Array of nDims nBytes-byte coordinates (or doubles for ieee_cmp).
55			* coord2: Array of nDims nBytes-byte coordinates (or doubles for ieee_cmp).
56			* Return value:
57			* -1, 0, or 1 according to whether
58			coord1<coord2, coord1==coord2, coord1>coord2
59			* Assumptions:
60			* nBits <= (sizeof bitmask_t) * (bits_per_byte)
61			*/
62
63			int hilbert_cmp(unsigned nDims, unsigned nBytes, unsigned nBits, void const* coord1, void const* coord2);
64			int hilbert_ieee_cmp(unsigned nDims, double const* coord1, double const* coord2);
65
66			/*****************************************************************
67			* hilbert_box_vtx
68			*
69			* Determine the first or last vertex of a box to lie on a Hilbert curve
70			* Inputs:
71			* nDims: Number of coordinates.
72			* nBytes: Number of bytes/coordinate.
73			* nBits: Number of bits/coordinate. (hilbert_box_vtx only)
74			* findMin: Is it the least vertex sought?
75			* coord1: Array of nDims nBytes-byte coordinates - one corner of box
76			* coord2: Array of nDims nBytes-byte coordinates - opposite corner
77			* Output:
78			* c1 and c2 modified to refer to selected corner
79			* value returned is log2 of size of largest power-of-two-aligned box that
80			* contains the selected corner and no other corners
81			* Assumptions:
82			* nBits <= (sizeof bitmask_t) * (bits_per_byte)
83			*/
84			unsigned
85			hilbert_box_vtx(unsigned nDims, unsigned nBytes, unsigned nBits,
86			int findMin, void* c1, void* c2);
87			unsigned
88			hilbert_ieee_box_vtx(unsigned nDims,
89			int findMin, double* c1, double* c2);
90
91			/*****************************************************************
92			* hilbert_box_pt
93			*
94			* Determine the first or last point of a box to lie on a Hilbert curve
95			* Inputs:
96			* nDims: Number of coordinates.
97			* nBytes: Number of bytes/coordinate.
98			* nBits: Number of bits/coordinate.
99			* findMin: Is it the least vertex sought?
100			* coord1: Array of nDims nBytes-byte coordinates - one corner of box
101			* coord2: Array of nDims nBytes-byte coordinates - opposite corner
102			* Output:
103			* c1 and c2 modified to refer to least point
104			* Assumptions:
105			* nBits <= (sizeof bitmask_t) * (bits_per_byte)
106			*/
107			unsigned
108			hilbert_box_pt(unsigned nDims, unsigned nBytes, unsigned nBits,
109			int findMin, void* coord1, void* coord2);
110			unsigned
111			hilbert_ieee_box_pt(unsigned nDims,
112			int findMin, double* c1, double* c2);
113
114			/*****************************************************************
115			* hilbert_nextinbox
116			*
117			* Determine the first point of a box after a given point to lie on a Hilbert curve
118			* Inputs:
119			* nDims: Number of coordinates.
120			* nBytes: Number of bytes/coordinate.
121			* nBits: Number of bits/coordinate.
122			* findPrev: Is the previous point sought?
123			* coord1: Array of nDims nBytes-byte coordinates - one corner of box
124			* coord2: Array of nDims nBytes-byte coordinates - opposite corner
125			* point: Array of nDims nBytes-byte coordinates - lower bound on point returned
126			*
127			* Output:
128			if returns 1:
129			* c1 and c2 modified to refer to least point after "point" in box
130			else returns 0:
131			arguments unchanged; "point" is beyond the last point of the box
132			* Assumptions:
133			* nBits <= (sizeof bitmask_t) * (bits_per_byte)
134			*/
135			int
136			hilbert_nextinbox(unsigned nDims, unsigned nBytes, unsigned nBits,
137			int findPrev, void* coord1, void* coord2,
138			void const* point);
139
140			/*****************************************************************
141			* hilbert_incr
142			*
143			* Advance from one point to its successor on a Hilbert curve
144			* Inputs:
145			* nDims: Number of coordinates.
146			* nBits: Number of bits/coordinate.
147			* coord: Array of nDims nBits-bit coordinates.
148			* Output:
149			* coord: Next point on Hilbert curve
150			* Assumptions:
151			* nBits <= (sizeof bitmask_t) * (bits_per_byte)
152			*/
153
154			void
155			hilbert_incr(unsigned nDims, unsigned nBits, bitmask_t coord[]);
156
157			#ifdef __cplusplus
158			}
159			#endif
160
161			#endif /* _hilbert_h_ */