Revision: 56768
http://sourceforge.net/p/brlcad/code/56768
Author: brlcad
Date: 2013-08-13 03:16:40 +0000 (Tue, 13 Aug 2013)
Log Message:
-----------
Fix 32-bit TIE. The problem was someone trying to be far too clever packing
bits into a pointer address. You read that right. Bits were being set/unset
and read from WITHIN the pointer VALUE. Even remember telling Justin many many
years ago this would be a problem, but obviously nothing came of that. My
vague recollection was that he was hijacking particular bits that were always
zero given particular struct allocation sizes. Of course, this is incredibly
presumptuous and volatile to struct member type sizes, 32-bit vs 64-bit
compilation, implicit padding/alignment issues, and more.
This gets TIE working on 32-bit compilation (and generally more portably all
around) by extracting those bit values that were being packed into their own
struct element (for both the kdtree and the tri structs) where this was
happening. This took quite a bit of very cautious surgery to extract and
propagate the bits correctly. There may be more needed (e.g., didn't test
single-precision), but seems to work swell in all the tests I threw at it.
Made (probably unnecessarily) most of the memory allocation zero-initialize
just for good measure too.
Modified Paths:
--------------
brlcad/trunk/src/librt/primitives/bot/tie.c
brlcad/trunk/src/librt/primitives/bot/tie_kdtree.c
brlcad/trunk/src/librt/primitives/bot/tieprivate.h
Modified: brlcad/trunk/src/librt/primitives/bot/tie.c
===================================================================
--- brlcad/trunk/src/librt/primitives/bot/tie.c 2013-08-13 02:53:41 UTC (rev
56767)
+++ brlcad/trunk/src/librt/primitives/bot/tie.c 2013-08-13 03:16:40 UTC (rev
56768)
@@ -100,10 +100,11 @@
tri->v[0] = v1.v[i2] - tri->data[0].v[i2];
tri->v[1] = v2.v[i2] - tri->data[0].v[i2];
+ /* !!! what? no entiendo. */
if (i1 == 0 && i2 == 1)
- tri->v = (tfloat *)((intptr_t)(tri->v) + 2);
+ tri->b = tri->b + 2;
else if (i1 == 0)
- tri->v = (tfloat *)((intptr_t)(tri->v) + 1);
+ tri->b = tri->b + 1;
/* Compute DotVN */
VSCALE(v1.v, tri->data[0].v, -1.0);
@@ -134,7 +135,7 @@
tie->tri_num = 0;
tie->tri_num_alloc = tri_num;
/* set to NULL if tri_num == 0. bu_malloc(0) causes issues. */
- tie->tri_list = tri_num?(struct tie_tri_s *)bu_malloc(sizeof(struct
tie_tri_s) * tri_num, "tie_init"):NULL;
+ tie->tri_list = tri_num?(struct tie_tri_s *)bu_calloc(tri_num,
sizeof(struct tie_tri_s), "tie_init"):NULL;
tie->stat = 0;
tie->rays_fired = 0;
}
@@ -154,7 +155,7 @@
/* Free Triangle Data */
for (i = 0; i < tie->tri_num; i++) {
- tfloat *ptr = (tfloat *)((intptr_t)(tie->tri_list[i].v) & ~0x7L);
+ tfloat *ptr = tie->tri_list[i].v;
bu_free(ptr, "free tfloat list");
}
bu_free(tie->tri_list, "tie_free");
@@ -209,9 +210,10 @@
struct tie_id_s t = {{0,0,0},{0,0,0},0,0,0}, id_list[256];
struct tie_tri_s *hit_list[256], *tri;
struct tie_geom_s *data;
- struct tie_kdtree_s *node_aligned, *temp[2];
+ struct tie_kdtree_s *node, *temp[2];
tfloat near, far, dirinv[3], dist;
- unsigned int i, n, hit_count;
+ unsigned int i, n;
+ uint8_t hit_count;
int ab[3], split, stack_ind;
void *result;
@@ -233,8 +235,8 @@
ab[i] = dirinv[i] < 0.0 ? 1.0 : 0.0;
}
- /* Extracting value of splitting plane from tie->kdtree pointer */
- split = ((intptr_t)(((struct tie_kdtree_s *)((intptr_t)tie->kdtree &
~0x7L))->data)) & 0x3;
+ /* Extracting value of splitting plane from the kdtree */
+ split = tie->kdtree->b & (uint32_t)0x3L;
/* Initialize ray segment */
if (ray->dir[split] < 0.0)
@@ -256,7 +258,7 @@
* Take the pointer from stack[stack_ind] and remove lower pts bits
used to store data to
* give a valid ptr address.
*/
- node_aligned = (struct tie_kdtree_s *)((intptr_t)stack[stack_ind].node
& ~0x7L);
+ node = stack[stack_ind].node;
stack_ind--;
/*
@@ -269,20 +271,20 @@
*
* Gordon Stoll's Mantra - Rays are Measured in Millions :-)
*/
- while (node_aligned && node_aligned->data &&
TIE_HAS_CHILDREN(node_aligned->data)) {
+ while (node && node->data && TIE_HAS_CHILDREN(node->b)) {
ray->kdtree_depth++;
/* Retrieve the splitting plane */
- split = ((intptr_t)(node_aligned->data)) & 0x3;
+ split = node->b & (uint32_t)0x3L;
/* Calculate the projected 1d distance to splitting axis */
- dist = (node_aligned->axis - ray->pos[split]) * dirinv[split];
+ dist = (node->axis - ray->pos[split]) * dirinv[split];
- temp[0] = &((struct tie_kdtree_s *)(node_aligned->data))[ab[split]];
- temp[1] = &((struct tie_kdtree_s
*)(node_aligned->data))[1-ab[split]];
+ temp[0] = &((struct tie_kdtree_s *)(node->data))[ab[split]];
+ temp[1] = &((struct tie_kdtree_s *)(node->data))[1-ab[split]];
i = near >= dist; /* Node B Only? */
- node_aligned = (struct tie_kdtree_s *)((intptr_t)(temp[i]) & ~0x7L);
+ node = temp[i];
if (far < dist || i)
continue;
@@ -295,7 +297,7 @@
far = dist;
}
- if (!node_aligned || !node_aligned->data) {
+ if (!node || !node->data) {
/* bu_log("INTERNAL ERROR: Unexpected TIE tree traversal
encountered\n"); */
continue;
}
@@ -306,7 +308,7 @@
*/
hit_count = 0;
- data = (struct tie_geom_s *)(node_aligned->data);
+ data = (struct tie_geom_s *)(node->data);
for (i = 0; i < data->tri_num; i++) {
/*
@@ -333,11 +335,11 @@
VSCALE(t.pos, ray->dir, t.dist);
VADD2(t.pos, ray->pos, t.pos);
- /* Extract i1 and i2 indices from lower bits of the v pointer */
- v = (tfloat *)((intptr_t)(tri->v) & ~0x7L);
+ /* Extract i1 and i2 indices from the 'b' field */
+ v = tri->v;
- i1 = TIE_TAB1[((intptr_t)(tri->v) & 0x7L)];
- i2 = TIE_TAB1[3 + ((intptr_t)(tri->v) & 0x7L)];
+ i1 = TIE_TAB1[tri->b & (uint32_t)0x7L];
+ i2 = TIE_TAB1[3 + (tri->b & (uint32_t)0x7L)];
/* Compute U and V */
u0 = t.pos[i1] - tri->data[0].v[i1];
@@ -363,7 +365,7 @@
continue;
/* Triangle Intersected, append it in the list */
- if (hit_count < 0xff) {
+ if (hit_count < 0xFF) {
hit_list[hit_count] = tri;
id_list[hit_count] = t;
hit_count++;
@@ -455,9 +457,8 @@
plist = (void *)((intptr_t)plist + pstride);
/* ??? this looks like it might cause fragmentation? use a memory pool?
*/
- tie->tri_list[tie->tri_num].v = (tfloat *)bu_malloc(2*sizeof(tfloat),
"alloc tfloat list");
- if (tie->tri_list[tie->tri_num].v == NULL)
- bu_log("Bad malloc! %s:%s:%d\n", __FILE__, __FUNCTION__, __LINE__);
+ tie->tri_list[tie->tri_num].v = (tfloat *)bu_calloc(2, sizeof(tfloat),
"alloc tfloat list");
+ tie->tri_list[tie->tri_num].b = 0;
tie->tri_num++;
}
return;
Modified: brlcad/trunk/src/librt/primitives/bot/tie_kdtree.c
===================================================================
--- brlcad/trunk/src/librt/primitives/bot/tie_kdtree.c 2013-08-13 02:53:41 UTC
(rev 56767)
+++ brlcad/trunk/src/librt/primitives/bot/tie_kdtree.c 2013-08-13 03:16:40 UTC
(rev 56768)
@@ -116,16 +116,14 @@
static void
tie_kdtree_free_node(struct tie_kdtree_s *node)
{
- struct tie_kdtree_s *node_aligned = (struct tie_kdtree_s *)((intptr_t)node
& ~0x7L);
-
- if (node_aligned && node_aligned->data &&
TIE_HAS_CHILDREN(node_aligned->data)) {
+ if (node && TIE_HAS_CHILDREN(node->b)) {
/* Node Data is KDTREE Children, Recurse */
- tie_kdtree_free_node(&((struct tie_kdtree_s
*)(((intptr_t)(node_aligned->data)) & ~0x7L))[0]);
- tie_kdtree_free_node(&((struct tie_kdtree_s
*)(((intptr_t)(node_aligned->data)) & ~0x7L))[1]);
+ tie_kdtree_free_node(&((struct tie_kdtree_s *)(node->data))[0]);
+ tie_kdtree_free_node(&((struct tie_kdtree_s *)(node->data))[1]);
} else {
/* This node points to a geometry node, free it */
struct tie_geom_s *tmp;
- tmp = (struct tie_geom_s *)((intptr_t)(node_aligned->data) & ~0x7L);
+ tmp = (struct tie_geom_s *)node->data;
if (tmp) {
if (tmp->tri_num > 0) {
bu_free(tmp->tri_list, "tri_list");
@@ -597,17 +595,11 @@
bu_bomb("Illegal tie kdtree method\n");
/* Allocate 2 children nodes for the parent node */
- node->data = (void *)bu_calloc(2, sizeof(struct tie_kdtree_s),
__FUNCTION__);
- if(((intptr_t)node->data & 0x7L))
- bu_log("node->data 0x%X is not aligned! %zu\n", node->data,
(intptr_t)node->data & 0x7L);
+ node->data = bu_calloc(2, sizeof(struct tie_kdtree_s), __FUNCTION__);
+ node->b = 0;
BU_ALLOC(((struct tie_kdtree_s *)(node->data))[0].data, struct tie_geom_s);
- if(((intptr_t)((struct tie_kdtree_s *)(node->data))[0].data & 0x7L))
- bu_log("node->data[0].data 0x%X is not aligned!\n", ((struct
tie_kdtree_s *)(node->data))[0].data);
-
BU_ALLOC(((struct tie_kdtree_s *)(node->data))[1].data, struct tie_geom_s);
- if(((intptr_t)((struct tie_kdtree_s *)(node->data))[1].data & 0x7L))
- bu_log("node->data[1].data 0x%X is not aligned!\n", ((struct
tie_kdtree_s *)(node->data))[1].data);
/* Initialize Triangle List */
child[0] = ((struct tie_geom_s *)(((struct tie_kdtree_s
*)(node->data))[0].data));
@@ -665,8 +657,9 @@
bu_free( child[n]->tri_list, "tri_list");
child[n]->tri_list = NULL;
}
- } else
+ } else {
child[n]->tri_list = (struct tie_tri_s
**)bu_realloc(child[n]->tri_list, sizeof(struct tie_tri_s *)*child[n]->tri_num,
__FUNCTION__);
+ }
}
/*
@@ -690,7 +683,7 @@
/* Assign the splitting dimension to the node */
/* If we've come this far then YES, this node DOES have child nodes, MARK
it as so. */
- node->data = (void *)(TIE_SET_HAS_CHILDREN(node->data) + split);
+ node->b = TIE_SET_HAS_CHILDREN(node->b) + split;
}
/*************************************************************
Modified: brlcad/trunk/src/librt/primitives/bot/tieprivate.h
===================================================================
--- brlcad/trunk/src/librt/primitives/bot/tieprivate.h 2013-08-13 02:53:41 UTC
(rev 56767)
+++ brlcad/trunk/src/librt/primitives/bot/tieprivate.h 2013-08-13 03:16:40 UTC
(rev 56768)
@@ -30,16 +30,17 @@
extern "C" {
#endif
-/* The last three bits of the void* in the kdtree are used to store data about
- * the object. 0x4 marks if the node has children (is set to 0 for a leaf), the
- * last two are the encoding for the splitting plane. Allocation must be a
- * multiple of 8. */
-#define TIE_HAS_CHILDREN(ptr) (((intptr_t)(ptr))&0x4L)
-#define TIE_SET_HAS_CHILDREN(ptr) (((intptr_t)(ptr))|0x4L)
+/* The last three bits of the 'b' field in the kdtree are used to
+ * store data about the object. 0x4L marks if the node has children
+ * (is set to 0 for a leaf), the last two are the encoding for the
+ * splitting plane.
+ */
+#define TIE_HAS_CHILDREN(bits) (bits & (uint32_t)0x4L)
+#define TIE_SET_HAS_CHILDREN(bits) (bits | (uint32_t)0x4L)
struct tie_geom_s {
- struct tie_tri_s **tri_list;
- unsigned int tri_num;
+ struct tie_tri_s **tri_list; /* 4-bytes or 8-bytes */
+ uint32_t tri_num; /* 4-bytes */
};
#ifdef _WIN32
@@ -48,9 +49,9 @@
#endif
struct tie_stack_s {
- struct tie_kdtree_s *node;
- tfloat near;
- tfloat far;
+ struct tie_kdtree_s *node; /* 4-bytes or 8-bytes */
+ tfloat near; /* 4-bytes or 8-bytes */
+ tfloat far; /* 4-bytes or 8-bytes */
};
#ifdef __cplusplus
This was sent by the SourceForge.net collaborative development platform, the
world's largest Open Source development site.
------------------------------------------------------------------------------
Get 100% visibility into Java/.NET code with AppDynamics Lite!
It's a free troubleshooting tool designed for production.
Get down to code-level detail for bottlenecks, with <2% overhead.
Download for free and get started troubleshooting in minutes.
http://pubads.g.doubleclick.net/gampad/clk?id=48897031&iu=/4140/ostg.clktrk
_______________________________________________
BRL-CAD Source Commits mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/brlcad-commits
