1 /**************************************************************************
3 * Copyright 2013-2014 RAD Game Tools and Valve Software
4 * Copyright 2010-2014 Rich Geldreich and Tenacious Software LLC
7 * Permission is hereby granted, free of charge, to any person obtaining a copy
8 * of this software and associated documentation files (the "Software"), to deal
9 * in the Software without restriction, including without limitation the rights
10 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
11 * copies of the Software, and to permit persons to whom the Software is
12 * furnished to do so, subject to the following conditions:
14 * The above copyright notice and this permission notice shall be included in
15 * all copies or substantial portions of the Software.
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
20 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
25 **************************************************************************/
27 // File: vogl_radix_sort.h
30 #include "vogl_core.h"
34 // Returns pointer to sorted array.
36 T *radix_sort(uint num_vals, T *pBuf0, T *pBuf1, uint key_ofs, uint key_size)
38 //VOGL_ASSERT_OPEN_RANGE(key_ofs, 0, sizeof(T));
39 VOGL_ASSERT(key_ofs < sizeof(T));
40 VOGL_ASSERT_CLOSED_RANGE(key_size, 1, 4);
44 memset(hist, 0, sizeof(hist[0]) * 256 * key_size);
46 #define VOGL_GET_KEY(p) (*(uint *)((uint8 *)(p) + key_ofs))
51 T *q = pBuf0 + num_vals;
54 const uint key = VOGL_GET_KEY(p);
57 hist[256 + ((key >> 8) & 0xFF)]++;
58 hist[512 + ((key >> 16) & 0xFF)]++;
59 hist[768 + ((key >> 24) & 0xFF)]++;
62 else if (key_size == 3)
65 T *q = pBuf0 + num_vals;
68 const uint key = VOGL_GET_KEY(p);
71 hist[256 + ((key >> 8) & 0xFF)]++;
72 hist[512 + ((key >> 16) & 0xFF)]++;
75 else if (key_size == 2)
78 T *q = pBuf0 + (num_vals >> 1) * 2;
80 for (; p != q; p += 2)
82 const uint key0 = VOGL_GET_KEY(p);
83 const uint key1 = VOGL_GET_KEY(p + 1);
86 hist[256 + ((key0 >> 8) & 0xFF)]++;
89 hist[256 + ((key1 >> 8) & 0xFF)]++;
94 const uint key = VOGL_GET_KEY(p);
97 hist[256 + ((key >> 8) & 0xFF)]++;
102 VOGL_ASSERT(key_size == 1);
107 T *q = pBuf0 + (num_vals >> 1) * 2;
109 for (; p != q; p += 2)
111 const uint key0 = VOGL_GET_KEY(p);
112 const uint key1 = VOGL_GET_KEY(p + 1);
120 const uint key = VOGL_GET_KEY(p);
128 for (uint pass = 0; pass < key_size; pass++)
130 const uint *pHist = &hist[pass << 8];
135 for (uint i = 0; i < 256; i += 2)
137 offsets[i] = cur_ofs;
140 offsets[i + 1] = cur_ofs;
141 cur_ofs += pHist[i + 1];
144 const uint pass_shift = pass << 3;
147 T *q = pCur + (num_vals >> 1) * 2;
149 for (; p != q; p += 2)
151 uint c0 = (VOGL_GET_KEY(p) >> pass_shift) & 0xFF;
152 uint c1 = (VOGL_GET_KEY(p + 1) >> pass_shift) & 0xFF;
156 uint dst_offset0 = offsets[c0];
158 offsets[c0] = dst_offset0 + 2;
160 pNew[dst_offset0] = p[0];
161 pNew[dst_offset0 + 1] = p[1];
165 uint dst_offset0 = offsets[c0]++;
166 uint dst_offset1 = offsets[c1]++;
168 pNew[dst_offset0] = p[0];
169 pNew[dst_offset1] = p[1];
175 uint c = (VOGL_GET_KEY(p) >> pass_shift) & 0xFF;
177 uint dst_offset = offsets[c];
178 offsets[c] = dst_offset + 1;
180 pNew[dst_offset] = *p;
193 // Returns pointer to sorted array.
194 template <typename T, typename Q>
195 T *indirect_radix_sort(uint num_indices, T *pIndices0, T *pIndices1, const Q *pKeys, uint key_ofs, uint key_size, bool init_indices)
197 VOGL_ASSERT(key_ofs < sizeof(T));
198 VOGL_ASSERT_CLOSED_RANGE(key_size, 1, 4);
203 T *q = pIndices0 + (num_indices >> 1) * 2;
205 for (i = 0; p != q; p += 2, i += 2)
207 p[0] = static_cast<T>(i);
208 p[1] = static_cast<T>(i + 1);
212 *p = static_cast<T>(i);
217 memset(hist, 0, sizeof(hist[0]) * 256 * key_size);
219 #define VOGL_GET_KEY(p) (*(const uint *)((const uint8 *)(pKeys + *(p)) + key_ofs))
220 #define VOGL_GET_KEY_FROM_INDEX(i) (*(const uint *)((const uint8 *)(pKeys + (i)) + key_ofs))
225 T *q = pIndices0 + num_indices;
228 const uint key = VOGL_GET_KEY(p);
231 hist[256 + ((key >> 8) & 0xFF)]++;
232 hist[512 + ((key >> 16) & 0xFF)]++;
233 hist[768 + ((key >> 24) & 0xFF)]++;
236 else if (key_size == 3)
239 T *q = pIndices0 + num_indices;
242 const uint key = VOGL_GET_KEY(p);
245 hist[256 + ((key >> 8) & 0xFF)]++;
246 hist[512 + ((key >> 16) & 0xFF)]++;
249 else if (key_size == 2)
252 T *q = pIndices0 + (num_indices >> 1) * 2;
254 for (; p != q; p += 2)
256 const uint key0 = VOGL_GET_KEY(p);
257 const uint key1 = VOGL_GET_KEY(p + 1);
260 hist[256 + ((key0 >> 8) & 0xFF)]++;
263 hist[256 + ((key1 >> 8) & 0xFF)]++;
268 const uint key = VOGL_GET_KEY(p);
271 hist[256 + ((key >> 8) & 0xFF)]++;
276 VOGL_ASSERT(key_size == 1);
281 T *q = pIndices0 + (num_indices >> 1) * 2;
283 for (; p != q; p += 2)
285 const uint key0 = VOGL_GET_KEY(p);
286 const uint key1 = VOGL_GET_KEY(p + 1);
294 const uint key = VOGL_GET_KEY(p);
303 for (uint pass = 0; pass < key_size; pass++)
305 const uint *pHist = &hist[pass << 8];
310 for (uint i = 0; i < 256; i += 2)
312 offsets[i] = cur_ofs;
315 offsets[i + 1] = cur_ofs;
316 cur_ofs += pHist[i + 1];
319 const uint pass_shift = pass << 3;
322 T *q = pCur + (num_indices >> 1) * 2;
324 for (; p != q; p += 2)
329 uint c0 = (VOGL_GET_KEY_FROM_INDEX(index0) >> pass_shift) & 0xFF;
330 uint c1 = (VOGL_GET_KEY_FROM_INDEX(index1) >> pass_shift) & 0xFF;
334 uint dst_offset0 = offsets[c0];
336 offsets[c0] = dst_offset0 + 2;
338 pNew[dst_offset0] = static_cast<T>(index0);
339 pNew[dst_offset0 + 1] = static_cast<T>(index1);
343 uint dst_offset0 = offsets[c0]++;
344 uint dst_offset1 = offsets[c1]++;
346 pNew[dst_offset0] = static_cast<T>(index0);
347 pNew[dst_offset1] = static_cast<T>(index1);
354 uint c = (VOGL_GET_KEY_FROM_INDEX(index) >> pass_shift) & 0xFF;
356 uint dst_offset = offsets[c];
357 offsets[c] = dst_offset + 1;
359 pNew[dst_offset] = static_cast<T>(index);
371 #undef VOGL_GET_KEY_FROM_INDEX