Mercurial > vba-clojure

annotate src/win32/7zip/7z/C/BwtSort.c @ 1:f9f4f1b99eed

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
importing src directory
author Robert McIntyre <rlm@mit.edu>
date Sat, 03 Mar 2012 10:31:27 -0600
parents
children
rev   line source
rlm@1 1 /* BwtSort.c -- BWT block sorting
rlm@1 2 2008-08-17
rlm@1 3 Igor Pavlov
rlm@1 4 Public domain */
rlm@1 5
rlm@1 6 #include "BwtSort.h"
rlm@1 7 #include "Sort.h"
rlm@1 8
rlm@1 9 /* #define BLOCK_SORT_USE_HEAP_SORT */
rlm@1 10
rlm@1 11 #define NO_INLINE MY_FAST_CALL
rlm@1 12
rlm@1 13 /* Don't change it !!! */
rlm@1 14 #define kNumHashBytes 2
rlm@1 15 #define kNumHashValues (1 << (kNumHashBytes * 8))
rlm@1 16
rlm@1 17 /* kNumRefBitsMax must be < (kNumHashBytes * 8) = 16 */
rlm@1 18 #define kNumRefBitsMax 12
rlm@1 19
rlm@1 20 #define BS_TEMP_SIZE kNumHashValues
rlm@1 21
rlm@1 22 #ifdef BLOCK_SORT_EXTERNAL_FLAGS
rlm@1 23
rlm@1 24 /* 32 Flags in UInt32 word */
rlm@1 25 #define kNumFlagsBits 5
rlm@1 26 #define kNumFlagsInWord (1 << kNumFlagsBits)
rlm@1 27 #define kFlagsMask (kNumFlagsInWord - 1)
rlm@1 28 #define kAllFlags 0xFFFFFFFF
rlm@1 29
rlm@1 30 #else
rlm@1 31
rlm@1 32 #define kNumBitsMax 20
rlm@1 33 #define kIndexMask ((1 << kNumBitsMax) - 1)
rlm@1 34 #define kNumExtraBits (32 - kNumBitsMax)
rlm@1 35 #define kNumExtra0Bits (kNumExtraBits - 2)
rlm@1 36 #define kNumExtra0Mask ((1 << kNumExtra0Bits) - 1)
rlm@1 37
rlm@1 38 #define SetFinishedGroupSize(p, size) \
rlm@1 39 { *(p) |= ((((size) - 1) & kNumExtra0Mask) << kNumBitsMax); \
rlm@1 40 if ((size) > (1 << kNumExtra0Bits)) { \
rlm@1 41 *(p) |= 0x40000000; *((p) + 1) |= ((((size) - 1)>> kNumExtra0Bits) << kNumBitsMax); } } \
rlm@1 42
rlm@1 43 static void SetGroupSize(UInt32 *p, UInt32 size)
rlm@1 44 {
rlm@1 45 if (--size == 0)
rlm@1 46 return;
rlm@1 47 *p |= 0x80000000 | ((size & kNumExtra0Mask) << kNumBitsMax);
rlm@1 48 if (size >= (1 << kNumExtra0Bits))
rlm@1 49 {
rlm@1 50 *p |= 0x40000000;
rlm@1 51 p[1] |= ((size >> kNumExtra0Bits) << kNumBitsMax);
rlm@1 52 }
rlm@1 53 }
rlm@1 54
rlm@1 55 #endif
rlm@1 56
rlm@1 57 /*
rlm@1 58 SortGroup - is recursive Range-Sort function with HeapSort optimization for small blocks
rlm@1 59 "range" is not real range. It's only for optimization.
rlm@1 60 returns: 1 - if there are groups, 0 - no more groups
rlm@1 61 */
rlm@1 62
rlm@1 63 UInt32 NO_INLINE SortGroup(UInt32 BlockSize, UInt32 NumSortedBytes, UInt32 groupOffset, UInt32 groupSize, int NumRefBits, UInt32 *Indices
rlm@1 64 #ifndef BLOCK_SORT_USE_HEAP_SORT
rlm@1 65 , UInt32 left, UInt32 range
rlm@1 66 #endif
rlm@1 67 )
rlm@1 68 {
rlm@1 69 UInt32 *ind2 = Indices + groupOffset;
rlm@1 70 UInt32 *Groups;
rlm@1 71 if (groupSize <= 1)
rlm@1 72 {
rlm@1 73 /*
rlm@1 74 #ifndef BLOCK_SORT_EXTERNAL_FLAGS
rlm@1 75 SetFinishedGroupSize(ind2, 1);
rlm@1 76 #endif
rlm@1 77 */
rlm@1 78 return 0;
rlm@1 79 }
rlm@1 80 Groups = Indices + BlockSize + BS_TEMP_SIZE;
rlm@1 81 if (groupSize <= ((UInt32)1 << NumRefBits)
rlm@1 82 #ifndef BLOCK_SORT_USE_HEAP_SORT
rlm@1 83 && groupSize <= range
rlm@1 84 #endif
rlm@1 85 )
rlm@1 86 {
rlm@1 87 UInt32 *temp = Indices + BlockSize;
rlm@1 88 UInt32 j;
rlm@1 89 UInt32 mask, thereAreGroups, group, cg;
rlm@1 90 {
rlm@1 91 UInt32 gPrev;
rlm@1 92 UInt32 gRes = 0;
rlm@1 93 {
rlm@1 94 UInt32 sp = ind2[0] + NumSortedBytes;
rlm@1 95 if (sp >= BlockSize) sp -= BlockSize;
rlm@1 96 gPrev = Groups[sp];
rlm@1 97 temp[0] = (gPrev << NumRefBits);
rlm@1 98 }
rlm@1 99
rlm@1 100 for (j = 1; j < groupSize; j++)
rlm@1 101 {
rlm@1 102 UInt32 sp = ind2[j] + NumSortedBytes;
rlm@1 103 UInt32 g;
rlm@1 104 if (sp >= BlockSize) sp -= BlockSize;
rlm@1 105 g = Groups[sp];
rlm@1 106 temp[j] = (g << NumRefBits) | j;
rlm@1 107 gRes |= (gPrev ^ g);
rlm@1 108 }
rlm@1 109 if (gRes == 0)
rlm@1 110 {
rlm@1 111 #ifndef BLOCK_SORT_EXTERNAL_FLAGS
rlm@1 112 SetGroupSize(ind2, groupSize);
rlm@1 113 #endif
rlm@1 114 return 1;
rlm@1 115 }
rlm@1 116 }
rlm@1 117
rlm@1 118 HeapSort(temp, groupSize);
rlm@1 119 mask = ((1 << NumRefBits) - 1);
rlm@1 120 thereAreGroups = 0;
rlm@1 121
rlm@1 122 group = groupOffset;
rlm@1 123 cg = (temp[0] >> NumRefBits);
rlm@1 124 temp[0] = ind2[temp[0] & mask];
rlm@1 125
rlm@1 126 {
rlm@1 127 #ifdef BLOCK_SORT_EXTERNAL_FLAGS
rlm@1 128 UInt32 *Flags = Groups + BlockSize;
rlm@1 129 #else
rlm@1 130 UInt32 prevGroupStart = 0;
rlm@1 131 #endif
rlm@1 132
rlm@1 133 for (j = 1; j < groupSize; j++)
rlm@1 134 {
rlm@1 135 UInt32 val = temp[j];
rlm@1 136 UInt32 cgCur = (val >> NumRefBits);
rlm@1 137
rlm@1 138 if (cgCur != cg)
rlm@1 139 {
rlm@1 140 cg = cgCur;
rlm@1 141 group = groupOffset + j;
rlm@1 142
rlm@1 143 #ifdef BLOCK_SORT_EXTERNAL_FLAGS
rlm@1 144 {
rlm@1 145 UInt32 t = group - 1;
rlm@1 146 Flags[t >> kNumFlagsBits] &= ~(1 << (t & kFlagsMask));
rlm@1 147 }
rlm@1 148 #else
rlm@1 149 SetGroupSize(temp + prevGroupStart, j - prevGroupStart);
rlm@1 150 prevGroupStart = j;
rlm@1 151 #endif
rlm@1 152 }
rlm@1 153 else
rlm@1 154 thereAreGroups = 1;
rlm@1 155 {
rlm@1 156 UInt32 ind = ind2[val & mask];
rlm@1 157 temp[j] = ind;
rlm@1 158 Groups[ind] = group;
rlm@1 159 }
rlm@1 160 }
rlm@1 161
rlm@1 162 #ifndef BLOCK_SORT_EXTERNAL_FLAGS
rlm@1 163 SetGroupSize(temp + prevGroupStart, j - prevGroupStart);
rlm@1 164 #endif
rlm@1 165 }
rlm@1 166
rlm@1 167 for (j = 0; j < groupSize; j++)
rlm@1 168 ind2[j] = temp[j];
rlm@1 169 return thereAreGroups;
rlm@1 170 }
rlm@1 171
rlm@1 172 /* Check that all strings are in one group (cannot sort) */
rlm@1 173 {
rlm@1 174 UInt32 group, j;
rlm@1 175 UInt32 sp = ind2[0] + NumSortedBytes; if (sp >= BlockSize) sp -= BlockSize;
rlm@1 176 group = Groups[sp];
rlm@1 177 for (j = 1; j < groupSize; j++)
rlm@1 178 {
rlm@1 179 sp = ind2[j] + NumSortedBytes; if (sp >= BlockSize) sp -= BlockSize;
rlm@1 180 if (Groups[sp] != group)
rlm@1 181 break;
rlm@1 182 }
rlm@1 183 if (j == groupSize)
rlm@1 184 {
rlm@1 185 #ifndef BLOCK_SORT_EXTERNAL_FLAGS
rlm@1 186 SetGroupSize(ind2, groupSize);
rlm@1 187 #endif
rlm@1 188 return 1;
rlm@1 189 }
rlm@1 190 }
rlm@1 191
rlm@1 192 #ifndef BLOCK_SORT_USE_HEAP_SORT
rlm@1 193 {
rlm@1 194 /* ---------- Range Sort ---------- */
rlm@1 195 UInt32 i;
rlm@1 196 UInt32 mid;
rlm@1 197 for (;;)
rlm@1 198 {
rlm@1 199 UInt32 j;
rlm@1 200 if (range <= 1)
rlm@1 201 {
rlm@1 202 #ifndef BLOCK_SORT_EXTERNAL_FLAGS
rlm@1 203 SetGroupSize(ind2, groupSize);
rlm@1 204 #endif
rlm@1 205 return 1;
rlm@1 206 }
rlm@1 207 mid = left + ((range + 1) >> 1);
rlm@1 208 j = groupSize;
rlm@1 209 i = 0;
rlm@1 210 do
rlm@1 211 {
rlm@1 212 UInt32 sp = ind2[i] + NumSortedBytes; if (sp >= BlockSize) sp -= BlockSize;
rlm@1 213 if (Groups[sp] >= mid)
rlm@1 214 {
rlm@1 215 for (j--; j > i; j--)
rlm@1 216 {
rlm@1 217 sp = ind2[j] + NumSortedBytes; if (sp >= BlockSize) sp -= BlockSize;
rlm@1 218 if (Groups[sp] < mid)
rlm@1 219 {
rlm@1 220 UInt32 temp = ind2[i]; ind2[i] = ind2[j]; ind2[j] = temp;
rlm@1 221 break;
rlm@1 222 }
rlm@1 223 }
rlm@1 224 if (i >= j)
rlm@1 225 break;
rlm@1 226 }
rlm@1 227 }
rlm@1 228 while (++i < j);
rlm@1 229 if (i == 0)
rlm@1 230 {
rlm@1 231 range = range - (mid - left);
rlm@1 232 left = mid;
rlm@1 233 }
rlm@1 234 else if (i == groupSize)
rlm@1 235 range = (mid - left);
rlm@1 236 else
rlm@1 237 break;
rlm@1 238 }
rlm@1 239
rlm@1 240 #ifdef BLOCK_SORT_EXTERNAL_FLAGS
rlm@1 241 {
rlm@1 242 UInt32 t = (groupOffset + i - 1);
rlm@1 243 UInt32 *Flags = Groups + BlockSize;
rlm@1 244 Flags[t >> kNumFlagsBits] &= ~(1 << (t & kFlagsMask));
rlm@1 245 }
rlm@1 246 #endif
rlm@1 247
rlm@1 248 {
rlm@1 249 UInt32 j;
rlm@1 250 for (j = i; j < groupSize; j++)
rlm@1 251 Groups[ind2[j]] = groupOffset + i;
rlm@1 252 }
rlm@1 253
rlm@1 254 {
rlm@1 255 UInt32 res = SortGroup(BlockSize, NumSortedBytes, groupOffset, i, NumRefBits, Indices, left, mid - left);
rlm@1 256 return res | SortGroup(BlockSize, NumSortedBytes, groupOffset + i, groupSize - i, NumRefBits, Indices, mid, range - (mid - left));
rlm@1 257 }
rlm@1 258
rlm@1 259 }
rlm@1 260
rlm@1 261 #else
rlm@1 262
rlm@1 263 /* ---------- Heap Sort ---------- */
rlm@1 264
rlm@1 265 {
rlm@1 266 UInt32 j;
rlm@1 267 for (j = 0; j < groupSize; j++)
rlm@1 268 {
rlm@1 269 UInt32 sp = ind2[j] + NumSortedBytes; if (sp >= BlockSize) sp -= BlockSize;
rlm@1 270 ind2[j] = sp;
rlm@1 271 }
rlm@1 272
rlm@1 273 HeapSortRef(ind2, Groups, groupSize);
rlm@1 274
rlm@1 275 /* Write Flags */
rlm@1 276 {
rlm@1 277 UInt32 sp = ind2[0];
rlm@1 278 UInt32 group = Groups[sp];
rlm@1 279
rlm@1 280 #ifdef BLOCK_SORT_EXTERNAL_FLAGS
rlm@1 281 UInt32 *Flags = Groups + BlockSize;
rlm@1 282 #else
rlm@1 283 UInt32 prevGroupStart = 0;
rlm@1 284 #endif
rlm@1 285
rlm@1 286 for (j = 1; j < groupSize; j++)
rlm@1 287 {
rlm@1 288 sp = ind2[j];
rlm@1 289 if (Groups[sp] != group)
rlm@1 290 {
rlm@1 291 group = Groups[sp];
rlm@1 292 #ifdef BLOCK_SORT_EXTERNAL_FLAGS
rlm@1 293 {
rlm@1 294 UInt32 t = groupOffset + j - 1;
rlm@1 295 Flags[t >> kNumFlagsBits] &= ~(1 << (t & kFlagsMask));
rlm@1 296 }
rlm@1 297 #else
rlm@1 298 SetGroupSize(ind2 + prevGroupStart, j - prevGroupStart);
rlm@1 299 prevGroupStart = j;
rlm@1 300 #endif
rlm@1 301 }
rlm@1 302 }
rlm@1 303
rlm@1 304 #ifndef BLOCK_SORT_EXTERNAL_FLAGS
rlm@1 305 SetGroupSize(ind2 + prevGroupStart, j - prevGroupStart);
rlm@1 306 #endif
rlm@1 307 }
rlm@1 308 {
rlm@1 309 /* Write new Groups values and Check that there are groups */
rlm@1 310 UInt32 thereAreGroups = 0;
rlm@1 311 for (j = 0; j < groupSize; j++)
rlm@1 312 {
rlm@1 313 UInt32 group = groupOffset + j;
rlm@1 314 #ifndef BLOCK_SORT_EXTERNAL_FLAGS
rlm@1 315 UInt32 subGroupSize = ((ind2[j] & ~0xC0000000) >> kNumBitsMax);
rlm@1 316 if ((ind2[j] & 0x40000000) != 0)
rlm@1 317 subGroupSize += ((ind2[j + 1] >> kNumBitsMax) << kNumExtra0Bits);
rlm@1 318 subGroupSize++;
rlm@1 319 for (;;)
rlm@1 320 {
rlm@1 321 UInt32 original = ind2[j];
rlm@1 322 UInt32 sp = original & kIndexMask;
rlm@1 323 if (sp < NumSortedBytes) sp += BlockSize; sp -= NumSortedBytes;
rlm@1 324 ind2[j] = sp | (original & ~kIndexMask);
rlm@1 325 Groups[sp] = group;
rlm@1 326 if (--subGroupSize == 0)
rlm@1 327 break;
rlm@1 328 j++;
rlm@1 329 thereAreGroups = 1;
rlm@1 330 }
rlm@1 331 #else
rlm@1 332 UInt32 *Flags = Groups + BlockSize;
rlm@1 333 for (;;)
rlm@1 334 {
rlm@1 335 UInt32 sp = ind2[j]; if (sp < NumSortedBytes) sp += BlockSize; sp -= NumSortedBytes;
rlm@1 336 ind2[j] = sp;
rlm@1 337 Groups[sp] = group;
rlm@1 338 if ((Flags[(groupOffset + j) >> kNumFlagsBits] & (1 << ((groupOffset + j) & kFlagsMask))) == 0)
rlm@1 339 break;
rlm@1 340 j++;
rlm@1 341 thereAreGroups = 1;
rlm@1 342 }
rlm@1 343 #endif
rlm@1 344 }
rlm@1 345 return thereAreGroups;
rlm@1 346 }
rlm@1 347 }
rlm@1 348 #endif
rlm@1 349 }
rlm@1 350
rlm@1 351 /* conditions: blockSize > 0 */
rlm@1 352 UInt32 BlockSort(UInt32 *Indices, const Byte *data, UInt32 blockSize)
rlm@1 353 {
rlm@1 354 UInt32 *counters = Indices + blockSize;
rlm@1 355 UInt32 i;
rlm@1 356 UInt32 *Groups;
rlm@1 357 #ifdef BLOCK_SORT_EXTERNAL_FLAGS
rlm@1 358 UInt32 *Flags;
rlm@1 359 #endif
rlm@1 360
rlm@1 361 /* Radix-Sort for 2 bytes */
rlm@1 362 for (i = 0; i < kNumHashValues; i++)
rlm@1 363 counters[i] = 0;
rlm@1 364 for (i = 0; i < blockSize - 1; i++)
rlm@1 365 counters[((UInt32)data[i] << 8) | data[i + 1]]++;
rlm@1 366 counters[((UInt32)data[i] << 8) | data[0]]++;
rlm@1 367
rlm@1 368 Groups = counters + BS_TEMP_SIZE;
rlm@1 369 #ifdef BLOCK_SORT_EXTERNAL_FLAGS
rlm@1 370 Flags = Groups + blockSize;
rlm@1 371 {
rlm@1 372 UInt32 numWords = (blockSize + kFlagsMask) >> kNumFlagsBits;
rlm@1 373 for (i = 0; i < numWords; i++)
rlm@1 374 Flags[i] = kAllFlags;
rlm@1 375 }
rlm@1 376 #endif
rlm@1 377
rlm@1 378 {
rlm@1 379 UInt32 sum = 0;
rlm@1 380 for (i = 0; i < kNumHashValues; i++)
rlm@1 381 {
rlm@1 382 UInt32 groupSize = counters[i];
rlm@1 383 if (groupSize > 0)
rlm@1 384 {
rlm@1 385 #ifdef BLOCK_SORT_EXTERNAL_FLAGS
rlm@1 386 UInt32 t = sum + groupSize - 1;
rlm@1 387 Flags[t >> kNumFlagsBits] &= ~(1 << (t & kFlagsMask));
rlm@1 388 #endif
rlm@1 389 sum += groupSize;
rlm@1 390 }
rlm@1 391 counters[i] = sum - groupSize;
rlm@1 392 }
rlm@1 393
rlm@1 394 for (i = 0; i < blockSize - 1; i++)
rlm@1 395 Groups[i] = counters[((UInt32)data[i] << 8) | data[i + 1]];
rlm@1 396 Groups[i] = counters[((UInt32)data[i] << 8) | data[0]];
rlm@1 397
rlm@1 398 for (i = 0; i < blockSize - 1; i++)
rlm@1 399 Indices[counters[((UInt32)data[i] << 8) | data[i + 1]]++] = i;
rlm@1 400 Indices[counters[((UInt32)data[i] << 8) | data[0]]++] = i;
rlm@1 401
rlm@1 402 #ifndef BLOCK_SORT_EXTERNAL_FLAGS
rlm@1 403 {
rlm@1 404 UInt32 prev = 0;
rlm@1 405 for (i = 0; i < kNumHashValues; i++)
rlm@1 406 {
rlm@1 407 UInt32 prevGroupSize = counters[i] - prev;
rlm@1 408 if (prevGroupSize == 0)
rlm@1 409 continue;
rlm@1 410 SetGroupSize(Indices + prev, prevGroupSize);
rlm@1 411 prev = counters[i];
rlm@1 412 }
rlm@1 413 }
rlm@1 414 #endif
rlm@1 415 }
rlm@1 416
rlm@1 417 {
rlm@1 418 int NumRefBits;
rlm@1 419 UInt32 NumSortedBytes;
rlm@1 420 for (NumRefBits = 0; ((blockSize - 1) >> NumRefBits) != 0; NumRefBits++);
rlm@1 421 NumRefBits = 32 - NumRefBits;
rlm@1 422 if (NumRefBits > kNumRefBitsMax)
rlm@1 423 NumRefBits = kNumRefBitsMax;
rlm@1 424
rlm@1 425 for (NumSortedBytes = kNumHashBytes; ; NumSortedBytes <<= 1)
rlm@1 426 {
rlm@1 427 #ifndef BLOCK_SORT_EXTERNAL_FLAGS
rlm@1 428 UInt32 finishedGroupSize = 0;
rlm@1 429 #endif
rlm@1 430 UInt32 newLimit = 0;
rlm@1 431 for (i = 0; i < blockSize;)
rlm@1 432 {
rlm@1 433 UInt32 groupSize;
rlm@1 434 #ifdef BLOCK_SORT_EXTERNAL_FLAGS
rlm@1 435
rlm@1 436 if ((Flags[i >> kNumFlagsBits] & (1 << (i & kFlagsMask))) == 0)
rlm@1 437 {
rlm@1 438 i++;
rlm@1 439 continue;
rlm@1 440 }
rlm@1 441 for (groupSize = 1;
rlm@1 442 (Flags[(i + groupSize) >> kNumFlagsBits] & (1 << ((i + groupSize) & kFlagsMask))) != 0;
rlm@1 443 groupSize++);
rlm@1 444
rlm@1 445 groupSize++;
rlm@1 446
rlm@1 447 #else
rlm@1 448
rlm@1 449 groupSize = ((Indices[i] & ~0xC0000000) >> kNumBitsMax);
rlm@1 450 {
rlm@1 451 Bool finishedGroup = ((Indices[i] & 0x80000000) == 0);
rlm@1 452 if ((Indices[i] & 0x40000000) != 0)
rlm@1 453 {
rlm@1 454 groupSize += ((Indices[i + 1] >> kNumBitsMax) << kNumExtra0Bits);
rlm@1 455 Indices[i + 1] &= kIndexMask;
rlm@1 456 }
rlm@1 457 Indices[i] &= kIndexMask;
rlm@1 458 groupSize++;
rlm@1 459 if (finishedGroup || groupSize == 1)
rlm@1 460 {
rlm@1 461 Indices[i - finishedGroupSize] &= kIndexMask;
rlm@1 462 if (finishedGroupSize > 1)
rlm@1 463 Indices[i - finishedGroupSize + 1] &= kIndexMask;
rlm@1 464 {
rlm@1 465 UInt32 newGroupSize = groupSize + finishedGroupSize;
rlm@1 466 SetFinishedGroupSize(Indices + i - finishedGroupSize, newGroupSize);
rlm@1 467 finishedGroupSize = newGroupSize;
rlm@1 468 }
rlm@1 469 i += groupSize;
rlm@1 470 continue;
rlm@1 471 }
rlm@1 472 finishedGroupSize = 0;
rlm@1 473 }
rlm@1 474
rlm@1 475 #endif
rlm@1 476
rlm@1 477 if (NumSortedBytes >= blockSize)
rlm@1 478 {
rlm@1 479 UInt32 j;
rlm@1 480 for (j = 0; j < groupSize; j++)
rlm@1 481 {
rlm@1 482 UInt32 t = (i + j);
rlm@1 483 /* Flags[t >> kNumFlagsBits] &= ~(1 << (t & kFlagsMask)); */
rlm@1 484 Groups[Indices[t]] = t;
rlm@1 485 }
rlm@1 486 }
rlm@1 487 else
rlm@1 488 if (SortGroup(blockSize, NumSortedBytes, i, groupSize, NumRefBits, Indices
rlm@1 489 #ifndef BLOCK_SORT_USE_HEAP_SORT
rlm@1 490 , 0, blockSize
rlm@1 491 #endif
rlm@1 492 ) != 0)
rlm@1 493 newLimit = i + groupSize;
rlm@1 494 i += groupSize;
rlm@1 495 }
rlm@1 496 if (newLimit == 0)
rlm@1 497 break;
rlm@1 498 }
rlm@1 499 }
rlm@1 500 #ifndef BLOCK_SORT_EXTERNAL_FLAGS
rlm@1 501 for (i = 0; i < blockSize;)
rlm@1 502 {
rlm@1 503 UInt32 groupSize = ((Indices[i] & ~0xC0000000) >> kNumBitsMax);
rlm@1 504 if ((Indices[i] & 0x40000000) != 0)
rlm@1 505 {
rlm@1 506 groupSize += ((Indices[i + 1] >> kNumBitsMax) << kNumExtra0Bits);
rlm@1 507 Indices[i + 1] &= kIndexMask;
rlm@1 508 }
rlm@1 509 Indices[i] &= kIndexMask;
rlm@1 510 groupSize++;
rlm@1 511 i += groupSize;
rlm@1 512 }
rlm@1 513 #endif
rlm@1 514 return Groups[0];
rlm@1 515 }
rlm@1 516