Go to the documentation of this file.00001
00002
00008
00009
00011
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00051
00052 #include "Stdafx.h"
00053
00054 using namespace IceCore;
00055
00056 #define INVALIDATE_RANKS mCurrentSize|=0x80000000
00057 #define VALIDATE_RANKS mCurrentSize&=0x7fffffff
00058 #define CURRENT_SIZE (mCurrentSize&0x7fffffff)
00059 #define INVALID_RANKS (mCurrentSize&0x80000000)
00060
00061 #define CHECK_RESIZE(n) \
00062 if(n!=mPreviousSize) \
00063 { \
00064 if(n>mCurrentSize) Resize(n); \
00065 else ResetRanks(); \
00066 mPreviousSize = n; \
00067 }
00068
00069 #define CREATE_HISTOGRAMS(type, buffer) \
00070 \
00071 ZeroMemory(mHistogram, 256*4*sizeof(udword)); \
00072 \
00073 \
00074 ubyte* p = (ubyte*)input; \
00075 ubyte* pe = &p[nb*4]; \
00076 udword* h0= &mHistogram[0]; \
00077 udword* h1= &mHistogram[256]; \
00078 udword* h2= &mHistogram[512]; \
00079 udword* h3= &mHistogram[768]; \
00080 \
00081 bool AlreadySorted = true; \
00082 \
00083 if(INVALID_RANKS) \
00084 { \
00085 \
00086 type* Running = (type*)buffer; \
00087 type PrevVal = *Running; \
00088 \
00089 while(p!=pe) \
00090 { \
00091 \
00092 type Val = *Running++; \
00093 \
00094 if(Val<PrevVal) { AlreadySorted = false; break; } \
00095 \
00096 PrevVal = Val; \
00097 \
00098 \
00099 h0[*p++]++; h1[*p++]++; h2[*p++]++; h3[*p++]++; \
00100 } \
00101 \
00102 \
00103 \
00104 \
00105 if(AlreadySorted) \
00106 { \
00107 mNbHits++; \
00108 for(udword i=0;i<nb;i++) mRanks[i] = i; \
00109 return *this; \
00110 } \
00111 } \
00112 else \
00113 { \
00114 \
00115 udword* Indices = mRanks; \
00116 type PrevVal = (type)buffer[*Indices]; \
00117 \
00118 while(p!=pe) \
00119 { \
00120 \
00121 type Val = (type)buffer[*Indices++]; \
00122 \
00123 if(Val<PrevVal) { AlreadySorted = false; break; } \
00124 \
00125 PrevVal = Val; \
00126 \
00127 \
00128 h0[*p++]++; h1[*p++]++; h2[*p++]++; h3[*p++]++; \
00129 } \
00130 \
00131 \
00132 \
00133 \
00134 if(AlreadySorted) { mNbHits++; return *this; } \
00135 } \
00136 \
00137 \
00138 while(p!=pe) \
00139 { \
00140 \
00141 h0[*p++]++; h1[*p++]++; h2[*p++]++; h3[*p++]++; \
00142 }
00143
00144 #define CHECK_PASS_VALIDITY(pass) \
00145 \
00146 udword* CurCount = &mHistogram[pass<<8]; \
00147 \
00148 \
00149 bool PerformPass = true; \
00150 \
00151 \
00152 \
00153 \
00154 \
00155 \
00156 \
00157 \
00158 \
00159 \
00160 ubyte UniqueVal = *(((ubyte*)input)+pass); \
00161 \
00162 \
00163 if(CurCount[UniqueVal]==nb) PerformPass=false;
00164
00166
00169
00170 RadixSort::RadixSort() : mCurrentSize(0), mRanks(null), mRanks2(null), mTotalCalls(0), mNbHits(0)
00171 {
00172 #ifndef RADIX_LOCAL_RAM
00173
00174 mHistogram = new udword[256*4];
00175 mOffset = new udword[256];
00176 #endif
00177
00178 INVALIDATE_RANKS;
00179 }
00180
00182
00185
00186 RadixSort::~RadixSort()
00187 {
00188
00189 #ifndef RADIX_LOCAL_RAM
00190 DELETEARRAY(mOffset);
00191 DELETEARRAY(mHistogram);
00192 #endif
00193 DELETEARRAY(mRanks2);
00194 DELETEARRAY(mRanks);
00195 }
00196
00198
00203
00204 bool RadixSort::Resize(udword nb)
00205 {
00206
00207 DELETEARRAY(mRanks2);
00208 DELETEARRAY(mRanks);
00209
00210
00211 mRanks = new udword[nb]; CHECKALLOC(mRanks);
00212 mRanks2 = new udword[nb]; CHECKALLOC(mRanks2);
00213
00214 return true;
00215 }
00216
00217 inline_ void RadixSort::CheckResize(udword nb)
00218 {
00219 udword CurSize = CURRENT_SIZE;
00220 if(nb!=CurSize)
00221 {
00222 if(nb>CurSize) Resize(nb);
00223 mCurrentSize = nb;
00224 INVALIDATE_RANKS;
00225 }
00226 }
00227
00229
00237
00238 RadixSort& RadixSort::Sort(const udword* input, udword nb, RadixHint hint)
00239 {
00240
00241 if(!input || !nb || nb&0x80000000) return *this;
00242
00243
00244 mTotalCalls++;
00245
00246
00247 CheckResize(nb);
00248
00249 #ifdef RADIX_LOCAL_RAM
00250
00251 udword mHistogram[256*4];
00252
00253 udword* mLink[256];
00254 #endif
00255
00256
00257
00258
00259
00260
00261 if(hint==RADIX_UNSIGNED) { CREATE_HISTOGRAMS(udword, input); }
00262 else { CREATE_HISTOGRAMS(sdword, input); }
00263
00264
00265 udword NbNegativeValues = 0;
00266 if(hint==RADIX_SIGNED)
00267 {
00268
00269
00270
00271 udword* h3= &mHistogram[768];
00272 for(udword i=128;i<256;i++) NbNegativeValues += h3[i];
00273 }
00274
00275
00276 for(udword j=0;j<4;j++)
00277 {
00278 CHECK_PASS_VALIDITY(j);
00279
00280
00281
00282 if(PerformPass)
00283 {
00284
00285 if(j!=3 || hint==RADIX_UNSIGNED)
00286 {
00287
00288
00289
00290
00291
00292 mLink[0] = mRanks2;
00293 for(udword i=1;i<256;i++) mLink[i] = mLink[i-1] + CurCount[i-1];
00294 }
00295 else
00296 {
00297
00298
00299
00300
00301 mLink[0] = &mRanks2[NbNegativeValues];
00302
00303 for(udword i=1;i<128;i++) mLink[i] = mLink[i-1] + CurCount[i-1];
00304
00305
00306
00307 mLink[128] = mRanks2;
00308
00309 for(udword i=129;i<256;i++) mLink[i] = mLink[i-1] + CurCount[i-1];
00310 }
00311
00312
00313 ubyte* InputBytes = (ubyte*)input;
00314 InputBytes += j;
00315 if(INVALID_RANKS)
00316 {
00317
00318 for(udword i=0;i<nb;i++) *mLink[InputBytes[i<<2]]++ = i;
00319 VALIDATE_RANKS;
00320 }
00321 else
00322 {
00323 udword* Indices = mRanks;
00324 udword* IndicesEnd = &mRanks[nb];
00325 while(Indices!=IndicesEnd)
00326 {
00327 udword id = *Indices++;
00328
00329 *mLink[InputBytes[id<<2]]++ = id;
00330 }
00331 }
00332
00333
00334 udword* Tmp = mRanks; mRanks = mRanks2; mRanks2 = Tmp;
00335 }
00336 }
00337 return *this;
00338 }
00339
00341
00349
00350 RadixSort& RadixSort::Sort(const float* input2, udword nb)
00351 {
00352
00353 if(!input2 || !nb || nb&0x80000000) return *this;
00354
00355
00356 mTotalCalls++;
00357
00358 udword* input = (udword*)input2;
00359
00360
00361 CheckResize(nb);
00362
00363 #ifdef RADIX_LOCAL_RAM
00364
00365 udword mHistogram[256*4];
00366
00367 udword* mLink[256];
00368 #endif
00369
00370
00371
00372
00373
00374
00375
00376
00377
00378 { CREATE_HISTOGRAMS(float, input2); }
00379
00380
00381 udword NbNegativeValues = 0;
00382
00383
00384
00385 udword* h3= &mHistogram[768];
00386 for(udword i=128;i<256;i++) NbNegativeValues += h3[i];
00387
00388
00389 for(udword j=0;j<4;j++)
00390 {
00391
00392 if(j!=3)
00393 {
00394
00395 CHECK_PASS_VALIDITY(j);
00396
00397 if(PerformPass)
00398 {
00399
00400
00401 mLink[0] = mRanks2;
00402
00403 for(udword i=1;i<256;i++) mLink[i] = mLink[i-1] + CurCount[i-1];
00404
00405
00406 ubyte* InputBytes = (ubyte*)input;
00407 InputBytes += j;
00408 if(INVALID_RANKS)
00409 {
00410
00411 for(udword i=0;i<nb;i++) *mLink[InputBytes[i<<2]]++ = i;
00412 VALIDATE_RANKS;
00413 }
00414 else
00415 {
00416 udword* Indices = mRanks;
00417 udword* IndicesEnd = &mRanks[nb];
00418 while(Indices!=IndicesEnd)
00419 {
00420 udword id = *Indices++;
00421
00422 *mLink[InputBytes[id<<2]]++ = id;
00423 }
00424 }
00425
00426
00427 udword* Tmp = mRanks; mRanks = mRanks2; mRanks2 = Tmp;
00428 }
00429 }
00430 else
00431 {
00432
00433 CHECK_PASS_VALIDITY(j);
00434
00435 if(PerformPass)
00436 {
00437
00438
00439 mLink[0] = &mRanks2[NbNegativeValues];
00440
00441 for(udword i=1;i<128;i++) mLink[i] = mLink[i-1] + CurCount[i-1];
00442
00443
00444
00445 mLink[255] = mRanks2;
00446
00447 for(udword i=0;i<127;i++) mLink[254-i] = mLink[255-i] + CurCount[255-i];
00448
00449 for(udword i=128;i<256;i++) mLink[i] += CurCount[i];
00450
00451
00452 if(INVALID_RANKS)
00453 {
00454 for(udword i=0;i<nb;i++)
00455 {
00456 udword Radix = input[i]>>24;
00457
00458
00459
00460 if(Radix<128) *mLink[Radix]++ = i;
00461 else *(--mLink[Radix]) = i;
00462 }
00463 VALIDATE_RANKS;
00464 }
00465 else
00466 {
00467 for(udword i=0;i<nb;i++)
00468 {
00469 udword Radix = input[mRanks[i]]>>24;
00470
00471
00472
00473 if(Radix<128) *mLink[Radix]++ = mRanks[i];
00474 else *(--mLink[Radix]) = mRanks[i];
00475 }
00476 }
00477
00478 udword* Tmp = mRanks; mRanks = mRanks2; mRanks2 = Tmp;
00479 }
00480 else
00481 {
00482
00483 if(UniqueVal>=128)
00484 {
00485 if(INVALID_RANKS)
00486 {
00487
00488 for(udword i=0;i<nb;i++) mRanks2[i] = nb-i-1;
00489 VALIDATE_RANKS;
00490 }
00491 else
00492 {
00493 for(udword i=0;i<nb;i++) mRanks2[i] = mRanks[nb-i-1];
00494 }
00495
00496
00497 udword* Tmp = mRanks; mRanks = mRanks2; mRanks2 = Tmp;
00498 }
00499 }
00500 }
00501 }
00502 return *this;
00503 }
00504
00506
00510
00511 udword RadixSort::GetUsedRam() const
00512 {
00513 udword UsedRam = sizeof(RadixSort);
00514 #ifndef RADIX_LOCAL_RAM
00515 UsedRam += 256*4*sizeof(udword);
00516 UsedRam += 256*sizeof(udword);
00517 #endif
00518 UsedRam += 2*CURRENT_SIZE*sizeof(udword);
00519 return UsedRam;
00520 }