git.cworth.org Git - vogl/blob - src/voglcore/vogl_radix_sort.h

   1 /**************************************************************************
   2  *
   3  * Copyright 2013-2014 RAD Game Tools and Valve Software
   4  * Copyright 2010-2014 Rich Geldreich and Tenacious Software LLC
   5  * All Rights Reserved.
   6  *
   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:
  13  *
  14  * The above copyright notice and this permission notice shall be included in
  15  * all copies or substantial portions of the Software.
  16  *
  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
  23  * THE SOFTWARE.
  24  *
  25  **************************************************************************/
  26
  27 // File: vogl_radix_sort.h
  28 #pragma once
  29
  30 #include "vogl_core.h"
  31
  32 namespace vogl
  33 {
  34     // Returns pointer to sorted array.
  35     template <typename T>
  36     T *radix_sort(uint num_vals, T *pBuf0, T *pBuf1, uint key_ofs, uint key_size)
  37     {
  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);
  41
  42         uint hist[256 * 4];
  43
  44         memset(hist, 0, sizeof(hist[0]) * 256 * key_size);
  45
  46 #define VOGL_GET_KEY(p) (*(uint *)((uint8 *)(p) + key_ofs))
  47
  48         if (key_size == 4)
  49         {
  50             T *p = pBuf0;
  51             T *q = pBuf0 + num_vals;
  52             for (; p != q; p++)
  53             {
  54                 const uint key = VOGL_GET_KEY(p);
  55
  56                 hist[key & 0xFF]++;
  57                 hist[256 + ((key >> 8) & 0xFF)]++;
  58                 hist[512 + ((key >> 16) & 0xFF)]++;
  59                 hist[768 + ((key >> 24) & 0xFF)]++;
  60             }
  61         }
  62         else if (key_size == 3)
  63         {
  64             T *p = pBuf0;
  65             T *q = pBuf0 + num_vals;
  66             for (; p != q; p++)
  67             {
  68                 const uint key = VOGL_GET_KEY(p);
  69
  70                 hist[key & 0xFF]++;
  71                 hist[256 + ((key >> 8) & 0xFF)]++;
  72                 hist[512 + ((key >> 16) & 0xFF)]++;
  73             }
  74         }
  75         else if (key_size == 2)
  76         {
  77             T *p = pBuf0;
  78             T *q = pBuf0 + (num_vals >> 1) * 2;
  79
  80             for (; p != q; p += 2)
  81             {
  82                 const uint key0 = VOGL_GET_KEY(p);
  83                 const uint key1 = VOGL_GET_KEY(p + 1);
  84
  85                 hist[key0 & 0xFF]++;
  86                 hist[256 + ((key0 >> 8) & 0xFF)]++;
  87
  88                 hist[key1 & 0xFF]++;
  89                 hist[256 + ((key1 >> 8) & 0xFF)]++;
  90             }
  91
  92             if (num_vals & 1)
  93             {
  94                 const uint key = VOGL_GET_KEY(p);
  95
  96                 hist[key & 0xFF]++;
  97                 hist[256 + ((key >> 8) & 0xFF)]++;
  98             }
  99         }
 100         else
 101         {
 102             VOGL_ASSERT(key_size == 1);
 103             if (key_size != 1)
 104                 return NULL;
 105
 106             T *p = pBuf0;
 107             T *q = pBuf0 + (num_vals >> 1) * 2;
 108
 109             for (; p != q; p += 2)
 110             {
 111                 const uint key0 = VOGL_GET_KEY(p);
 112                 const uint key1 = VOGL_GET_KEY(p + 1);
 113
 114                 hist[key0 & 0xFF]++;
 115                 hist[key1 & 0xFF]++;
 116             }
 117
 118             if (num_vals & 1)
 119             {
 120                 const uint key = VOGL_GET_KEY(p);
 121                 hist[key & 0xFF]++;
 122             }
 123         }
 124
 125         T *pCur = pBuf0;
 126         T *pNew = pBuf1;
 127
 128         for (uint pass = 0; pass < key_size; pass++)
 129         {
 130             const uint *pHist = &hist[pass << 8];
 131
 132             uint offsets[256];
 133
 134             uint cur_ofs = 0;
 135             for (uint i = 0; i < 256; i += 2)
 136             {
 137                 offsets[i] = cur_ofs;
 138                 cur_ofs += pHist[i];
 139
 140                 offsets[i + 1] = cur_ofs;
 141                 cur_ofs += pHist[i + 1];
 142             }
 143
 144             const uint pass_shift = pass << 3;
 145
 146             T *p = pCur;
 147             T *q = pCur + (num_vals >> 1) * 2;
 148
 149             for (; p != q; p += 2)
 150             {
 151                 uint c0 = (VOGL_GET_KEY(p) >> pass_shift) & 0xFF;
 152                 uint c1 = (VOGL_GET_KEY(p + 1) >> pass_shift) & 0xFF;
 153
 154                 if (c0 == c1)
 155                 {
 156                     uint dst_offset0 = offsets[c0];
 157
 158                     offsets[c0] = dst_offset0 + 2;
 159
 160                     pNew[dst_offset0] = p[0];
 161                     pNew[dst_offset0 + 1] = p[1];
 162                 }
 163                 else
 164                 {
 165                     uint dst_offset0 = offsets[c0]++;
 166                     uint dst_offset1 = offsets[c1]++;
 167
 168                     pNew[dst_offset0] = p[0];
 169                     pNew[dst_offset1] = p[1];
 170                 }
 171             }
 172
 173             if (num_vals & 1)
 174             {
 175                 uint c = (VOGL_GET_KEY(p) >> pass_shift) & 0xFF;
 176
 177                 uint dst_offset = offsets[c];
 178                 offsets[c] = dst_offset + 1;
 179
 180                 pNew[dst_offset] = *p;
 181             }
 182
 183             T *t = pCur;
 184             pCur = pNew;
 185             pNew = t;
 186         }
 187
 188         return pCur;
 189     }
 190
 191 #undef VOGL_GET_KEY
 192
 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)
 196     {
 197         VOGL_ASSERT(key_ofs < sizeof(T));
 198         VOGL_ASSERT_CLOSED_RANGE(key_size, 1, 4);
 199
 200         if (init_indices)
 201         {
 202             T *p = pIndices0;
 203             T *q = pIndices0 + (num_indices >> 1) * 2;
 204             uint i;
 205             for (i = 0; p != q; p += 2, i += 2)
 206             {
 207                 p[0] = static_cast<T>(i);
 208                 p[1] = static_cast<T>(i + 1);
 209             }
 210
 211             if (num_indices & 1)
 212                 *p = static_cast<T>(i);
 213         }
 214
 215         uint hist[256 * 4];
 216
 217         memset(hist, 0, sizeof(hist[0]) * 256 * key_size);
 218
 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))
 221
 222         if (key_size == 4)
 223         {
 224             T *p = pIndices0;
 225             T *q = pIndices0 + num_indices;
 226             for (; p != q; p++)
 227             {
 228                 const uint key = VOGL_GET_KEY(p);
 229
 230                 hist[key & 0xFF]++;
 231                 hist[256 + ((key >> 8) & 0xFF)]++;
 232                 hist[512 + ((key >> 16) & 0xFF)]++;
 233                 hist[768 + ((key >> 24) & 0xFF)]++;
 234             }
 235         }
 236         else if (key_size == 3)
 237         {
 238             T *p = pIndices0;
 239             T *q = pIndices0 + num_indices;
 240             for (; p != q; p++)
 241             {
 242                 const uint key = VOGL_GET_KEY(p);
 243
 244                 hist[key & 0xFF]++;
 245                 hist[256 + ((key >> 8) & 0xFF)]++;
 246                 hist[512 + ((key >> 16) & 0xFF)]++;
 247             }
 248         }
 249         else if (key_size == 2)
 250         {
 251             T *p = pIndices0;
 252             T *q = pIndices0 + (num_indices >> 1) * 2;
 253
 254             for (; p != q; p += 2)
 255             {
 256                 const uint key0 = VOGL_GET_KEY(p);
 257                 const uint key1 = VOGL_GET_KEY(p + 1);
 258
 259                 hist[key0 & 0xFF]++;
 260                 hist[256 + ((key0 >> 8) & 0xFF)]++;
 261
 262                 hist[key1 & 0xFF]++;
 263                 hist[256 + ((key1 >> 8) & 0xFF)]++;
 264             }
 265
 266             if (num_indices & 1)
 267             {
 268                 const uint key = VOGL_GET_KEY(p);
 269
 270                 hist[key & 0xFF]++;
 271                 hist[256 + ((key >> 8) & 0xFF)]++;
 272             }
 273         }
 274         else
 275         {
 276             VOGL_ASSERT(key_size == 1);
 277             if (key_size != 1)
 278                 return NULL;
 279
 280             T *p = pIndices0;
 281             T *q = pIndices0 + (num_indices >> 1) * 2;
 282
 283             for (; p != q; p += 2)
 284             {
 285                 const uint key0 = VOGL_GET_KEY(p);
 286                 const uint key1 = VOGL_GET_KEY(p + 1);
 287
 288                 hist[key0 & 0xFF]++;
 289                 hist[key1 & 0xFF]++;
 290             }
 291
 292             if (num_indices & 1)
 293             {
 294                 const uint key = VOGL_GET_KEY(p);
 295
 296                 hist[key & 0xFF]++;
 297             }
 298         }
 299
 300         T *pCur = pIndices0;
 301         T *pNew = pIndices1;
 302
 303         for (uint pass = 0; pass < key_size; pass++)
 304         {
 305             const uint *pHist = &hist[pass << 8];
 306
 307             uint offsets[256];
 308
 309             uint cur_ofs = 0;
 310             for (uint i = 0; i < 256; i += 2)
 311             {
 312                 offsets[i] = cur_ofs;
 313                 cur_ofs += pHist[i];
 314
 315                 offsets[i + 1] = cur_ofs;
 316                 cur_ofs += pHist[i + 1];
 317             }
 318
 319             const uint pass_shift = pass << 3;
 320
 321             T *p = pCur;
 322             T *q = pCur + (num_indices >> 1) * 2;
 323
 324             for (; p != q; p += 2)
 325             {
 326                 uint index0 = p[0];
 327                 uint index1 = p[1];
 328
 329                 uint c0 = (VOGL_GET_KEY_FROM_INDEX(index0) >> pass_shift) & 0xFF;
 330                 uint c1 = (VOGL_GET_KEY_FROM_INDEX(index1) >> pass_shift) & 0xFF;
 331
 332                 if (c0 == c1)
 333                 {
 334                     uint dst_offset0 = offsets[c0];
 335
 336                     offsets[c0] = dst_offset0 + 2;
 337
 338                     pNew[dst_offset0] = static_cast<T>(index0);
 339                     pNew[dst_offset0 + 1] = static_cast<T>(index1);
 340                 }
 341                 else
 342                 {
 343                     uint dst_offset0 = offsets[c0]++;
 344                     uint dst_offset1 = offsets[c1]++;
 345
 346                     pNew[dst_offset0] = static_cast<T>(index0);
 347                     pNew[dst_offset1] = static_cast<T>(index1);
 348                 }
 349             }
 350
 351             if (num_indices & 1)
 352             {
 353                 uint index = *p;
 354                 uint c = (VOGL_GET_KEY_FROM_INDEX(index) >> pass_shift) & 0xFF;
 355
 356                 uint dst_offset = offsets[c];
 357                 offsets[c] = dst_offset + 1;
 358
 359                 pNew[dst_offset] = static_cast<T>(index);
 360             }
 361
 362             T *t = pCur;
 363             pCur = pNew;
 364             pNew = t;
 365         }
 366
 367         return pCur;
 368     }
 369
 370 #undef VOGL_GET_KEY
 371 #undef VOGL_GET_KEY_FROM_INDEX
 372
 373 } // namespace vogl