-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathkdasm.h
232 lines (203 loc) · 11.1 KB
/
kdasm.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
#ifndef KDASM_H
#define KDASM_H
// Copyright (c) 2012 Adrian Johnston. All rights reserved.
// Project Homepage: http://code.google.com/p/kdasm/
//
// Permission is hereby granted, free of charge, to any person obtaining
// a copy of this software and associated documentation files (the
// "Software"), to deal in the Software without restriction, including
// without limitation the rights to use, copy, modify, merge, publish,
// distribute, sublicense, and/or sell copies of the Software, and to
// permit persons to whom the Software is furnished to do so, subject to
// the following conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
// IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
// CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
// TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
// SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
// Kdasm: k-d tree compressor with efficient cache-optimized runtime.
typedef unsigned short KdasmU16;
// ----------------------------------------------------------------------------
// KdasmEncoding is an encoding of a k-d tree node cutting plane, jump statement or leaves.
// See Encoding Specification: http://goo.gl/3sU5N.
class KdasmEncoding
{
public:
enum {
NORMAL_X = 0x0000,
NORMAL_Y = 0x0001,
NORMAL_Z = 0x0002,
NORMAL_OPCODE = 0x0003,
NORMAL_MASK = 0x0003,
OPCODE_LEAVES = 0x0000,
OPCODE_LEAVES_FAR = 0x0004,
OPCODE_JUMP = 0x0008,
OPCODE_JUMP_FAR = 0x000c,
// With a distance length of 1 the value must fit in DISTANCE_IMMEDIATE_MASK and be less than DISTANCE_IMMEDIATE_MAX.
DISTANCE_IMMEDIATE_MASK = 0xfff0,
DISTANCE_IMMEDIATE_MAX = 0xffe0,
// Due to quantization, an immediate cutting plane has this width.
DISTANCE_IMMEDIATE_PLANE_WIDTH = 0x0010,
// With a distance length greater than 1 this is the max value of the first word.
DISTANCE_PREFIX_MAX = 0x001f,
LEAF_WORD_LENGTH_MAX = 0x001f,
TREE_INDEX_MAX = 0x001f,
IMMEDIATE_OFFSET_MAX = 0x03ff, // Max absolute value. Negative values allowed.
LEAF_COUNT_OVERFLOW = 0xffff, // An embedded header in the leaf data is required beyond this.
PAD_VALUE = 0xcccc // Impossible x axis cut with both stop bits set.
};
KdasmU16 GetRaw( void ) const { return m_word; }
KdasmU16 GetNomal( void ) const { return m_word & (KdasmU16)NORMAL_MASK; }
bool GetStop0( void ) const { return (m_word & (KdasmU16)STOP_BIT_0) != (KdasmU16)0; }
bool GetStop1( void ) const { return (m_word & (KdasmU16)STOP_BIT_1) != (KdasmU16)0; }
KdasmU16 GetDistanceImmediate( void ) const { return m_word & (KdasmU16)DISTANCE_IMMEDIATE_MASK; }
KdasmU16 GetDistancePrefix( void ) const { return m_word >> DISTANCE_PREFIX_SHIFT; }
KdasmU16 GetOpcode( void ) const { return m_word & (KdasmU16)OPCODE_MASK; }
bool GetIsImmediateOffset( void ) const { return (m_word & (KdasmU16)IMMEDIATE_BIT) != (KdasmU16)0; }
KdasmU16 GetImmediateOffset( void ) const { return m_word >> IMMEDIATE_SHIFT; }
KdasmU16 GetFarWordsCount( void ) const { return (m_word & (KdasmU16)WORDS_COUNT_MASK) >> WORDS_COUNT_SHIFT; }
KdasmU16 GetFarWordsOffset( void ) const { return m_word >> WORDS_OFFSET_SHIFT; }
KdasmU16 GetOffset( void ) const { return (m_word & (KdasmU16)OFFSET_MASK) >> OFFSET_SHIFT; }
KdasmU16 GetLength( void ) const { return m_word >> LENGTH_SHIFT; }
KdasmU16 GetTreeIndexStart( void ) const { return m_word >> TREE_INDEX_START_SHIFT; }
void SetRaw( KdasmU16 x ) { m_word = x; }
KdasmU16* Ptr( void ) { return &m_word; }
void SetNomal( KdasmU16 n ) { m_word = (m_word & ~(KdasmU16)NORMAL_MASK) | ((KdasmU16)NORMAL_MASK & n); }
void SetStop0( bool b ) { SetBool( b, STOP_BIT_0 ); }
void SetStop1( bool b ) { SetBool( b, STOP_BIT_1 ); }
void SetDistanceImmediate( KdasmU16 d ) { m_word = (m_word & ~(KdasmU16)DISTANCE_IMMEDIATE_MASK) | ((KdasmU16)DISTANCE_IMMEDIATE_MASK & d); }
void SetDistancePrefix( KdasmU16 n ) { SetNShift( n, DISTANCE_PREFIX_SHIFT ); }
void SetOpcode( KdasmU16 op ) { m_word = (m_word & ~(KdasmU16)OPCODE_MASK) | ((KdasmU16)OPCODE_MASK & op); }
void SetIsImmediateOffset( bool b ) { SetBool( b, IMMEDIATE_BIT ); }
void SetImmediateOffset( KdasmU16 n ) { SetNShift( n, IMMEDIATE_SHIFT ); }
void SetFarWordsCount( KdasmU16 n ) { SetNShiftAndMask( n, WORDS_COUNT_SHIFT, WORDS_COUNT_MASK ); }
void SetFarWordsOffset( KdasmU16 n ) { SetNShift( n, WORDS_OFFSET_SHIFT ); }
void SetOffset( KdasmU16 o ) { SetNShiftAndMask( o, OFFSET_SHIFT, OFFSET_MASK ); }
void SetLength( KdasmU16 n ) { SetNShift( n, LENGTH_SHIFT ); }
void SetTreeIndexStart( KdasmU16 n ) { SetNShift( n, TREE_INDEX_START_SHIFT ); }
// Convert floating point value between 0 and 1 to fixed point.
static KdasmU16 PackDistanceImmediate( float d01 )
{
d01 = (d01 < 0.0f) ? 0.0f : ((d01 > 1.0f) ? 1.0f : d01); // clamp [0..1]
return DISTANCE_IMMEDIATE_MASK & (KdasmU16)( d01 * (float)DISTANCE_IMMEDIATE_MAX );
}
// For Distance Length == 1. Returns the sides of the quantized cutting plane.
void UnpackDistanceImmediate( float* d01less, float* d01greater ) const
{
float do01 = (float)GetDistanceImmediate() * (1.0f / (float)(DISTANCE_IMMEDIATE_MAX));
*d01less = do01;
*d01greater = do01 + ((float)DISTANCE_IMMEDIATE_PLANE_WIDTH/(float)DISTANCE_IMMEDIATE_MAX + 2.0f*FLT_EPSILON);
}
// For distanceLength > 1. The number of words used to encode distance is constant.
template<int distanceLength> intptr_t UnpackDistance( void ) const
{
intptr_t distance = UnpackWords( distanceLength - 1, GetOffset() );
return distance | ( (intptr_t)( m_word & (KdasmU16)DISTANCE_PREFIX_MASK ) << ( 16 * ( distanceLength - 1 ) - DISTANCE_PREFIX_SHIFT ) );
}
intptr_t GetOffsetSigned( void ) const
{
return ( (intptr_t)GetOffset() ^ (intptr_t)OFFSET_SIGN_BIT ) - (intptr_t)OFFSET_SIGN_BIT;
}
intptr_t GetFarOffset( void ) const
{
if( GetIsImmediateOffset() )
{
return ( (intptr_t)GetImmediateOffset() ^ (intptr_t)IMMEDIATE_SIGN_BIT ) - (intptr_t)IMMEDIATE_SIGN_BIT;
}
KdasmU16 wordCount = GetFarWordsCount();
intptr_t signBit = (intptr_t)1 << (wordCount * 16 - 1);
return ( UnpackWords( wordCount, GetFarWordsOffset() ) ^ signBit ) - signBit;
}
private:
enum {
OPCODE_MASK = 0x000c, // NORMAL_OPCODE
STOP_BIT_0 = 0x0004, // NORMAL_X/Y/Z
STOP_BIT_1 = 0x0008,
IMMEDIATE_BIT = 0x0010, // OPCODE_LEAVES_FAR, OPCODE_JUMP_FAR
IMMEDIATE_SHIFT = 5,
IMMEDIATE_SIGN_BIT = 0x0400,
WORDS_COUNT_SHIFT = 5,
WORDS_COUNT_MASK = 0x00e0,
WORDS_OFFSET_SHIFT = 8,
OFFSET_SHIFT = 4, // OPCODE_LEAVES, OPCODE_JUMP
OFFSET_MASK = 0x07f0,
OFFSET_SIGN_BIT = 0x0040,
DISTANCE_PREFIX_MASK = 0xf800, // NORMAL_X/Y/Z
DISTANCE_PREFIX_SHIFT = 11,
LENGTH_SHIFT = 11, // OPCODE_LEAVES
TREE_INDEX_START_SHIFT = 11, // OPCODE_JUMP
};
void SetNShift( KdasmU16 n, int shift )
{
m_word = (m_word & (KdasmU16)((1 << shift) - 1)) | (KdasmU16)(n << shift);
}
void SetNShiftAndMask( KdasmU16 n, int shift, KdasmU16 mask )
{
m_word = (m_word & ~mask) | ((n << shift) & mask);
}
void SetBool( bool b, KdasmU16 mask )
{
m_word = (m_word & ~mask) | (b ? mask : 0);
}
intptr_t UnpackWords( KdasmU16 wordCount, KdasmU16 wordsOffset ) const
{
const KdasmU16* words = &m_word + wordsOffset;
intptr_t result = (intptr_t)*words;
while( --wordCount != 0 )
{
result <<= 16;
result |= (intptr_t)*++words;
}
return result;
}
KdasmU16 m_word;
};
// ----------------------------------------------------------------------------
// Inserted at the beginning of the first page.
class KdasmEncodingHeader
{
public:
enum {
DISTANCE_LENGTH_MAX = 0x0007,
HEADER_LENGTH = 2
};
enum PageBits {
PAGE_BITS_32B = 5,
PAGE_BITS_64B = 6,
PAGE_BITS_128B = 7
};
bool VersionCheck( void ) const { return m_words[0] == VERSION_1; }
// Number of KdasmU16 including prefix, or 1 for immediate storage.
KdasmU16 GetDistanceLength( void ) const { return m_words[1] & (KdasmU16)DISTANCE_LENGTH_MASK; }
bool IsLeavesAtRoot( void ) const { return ( m_words[1] & (KdasmU16)FLAG_LEAVES_AT_ROOT ) != 0; }
PageBits GetPageBits( void ) const { return (PageBits)((m_words[1] & (KdasmU16)PAGE_BITS_MASK) >> PAGE_BITS_SHIFT); }
// internal
void Reset( void ) { m_words[0] = VERSION_1; m_words[1] = 0; }
void SetDistanceLength( KdasmU16 dl ) { m_words[1] |= (KdasmU16)DISTANCE_LENGTH_MASK & dl; }
void SetIsLeavesAtRoot( bool b ) { m_words[1] |= b ? (KdasmU16)FLAG_LEAVES_AT_ROOT : 0; }
void SetPageBits( PageBits pb ) { m_words[1] |= (KdasmU16)PAGE_BITS_MASK & ((KdasmU16)pb << PAGE_BITS_SHIFT); }
KdasmU16 GetRaw( int index ) const { return m_words[index]; }
private:
union PortabilityCheck
{
char size_of_unsigned_short_incorrect[sizeof(KdasmU16) == 2];
char size_of_int_incorrect[sizeof(int) >= 4];
char size_of_encoding_incorrect[sizeof(KdasmEncoding) == 2];
char sign_extended_shift_incorrect[((-1)>>1) == (-1)];
};
enum {
VERSION_1 = 0x316b, // 'k','1'
DISTANCE_LENGTH_MASK = 0x0007,
FLAG_LEAVES_AT_ROOT = 0x0008, // Starts with a OPCODE_LEAVES_FAR reference.
PAGE_BITS_MASK = 0x00f0,
PAGE_BITS_SHIFT = 4,
};
KdasmU16 m_words[HEADER_LENGTH];
};
#endif // KDASM_H