1cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 2cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project/*-------------------------------------------------------------*/ 3cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project/*--- Block sorting machinery ---*/ 4cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project/*--- blocksort.c ---*/ 5cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project/*-------------------------------------------------------------*/ 6cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 7cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project/* ------------------------------------------------------------------ 8cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project This file is part of bzip2/libbzip2, a program and library for 9cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project lossless, block-sorting data compression. 10cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 11172b266ed7845eac2edc7e7f8a72371356a9a277Nick Kralevich bzip2/libbzip2 version 1.0.6 of 6 September 2010 12172b266ed7845eac2edc7e7f8a72371356a9a277Nick Kralevich Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org> 13cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 14cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Please read the WARNING, DISCLAIMER and PATENTS sections in the 15cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project README file. 16cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 17cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project This program is released under the terms of the license contained 18cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project in the file LICENSE. 19cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ------------------------------------------------------------------ */ 20cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 21cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 22cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#include "bzlib_private.h" 23cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 24cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project/*---------------------------------------------*/ 25cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project/*--- Fallback O(N log(N)^2) sorting ---*/ 26cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project/*--- algorithm, for repetitive blocks ---*/ 27cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project/*---------------------------------------------*/ 28cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 29cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project/*---------------------------------------------*/ 30cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Projectstatic 31cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project__inline__ 32cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Projectvoid fallbackSimpleSort ( UInt32* fmap, 33cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project UInt32* eclass, 34cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 lo, 35cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 hi ) 36cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project{ 37cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 i, j, tmp; 38cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project UInt32 ec_tmp; 39cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 40cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (lo == hi) return; 41cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 42cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (hi - lo > 3) { 43cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project for ( i = hi-4; i >= lo; i-- ) { 44cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project tmp = fmap[i]; 45cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ec_tmp = eclass[tmp]; 46cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project for ( j = i+4; j <= hi && ec_tmp > eclass[fmap[j]]; j += 4 ) 47cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project fmap[j-4] = fmap[j]; 48cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project fmap[j-4] = tmp; 49cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 50cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 51cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 52cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project for ( i = hi-1; i >= lo; i-- ) { 53cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project tmp = fmap[i]; 54cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ec_tmp = eclass[tmp]; 55cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project for ( j = i+1; j <= hi && ec_tmp > eclass[fmap[j]]; j++ ) 56cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project fmap[j-1] = fmap[j]; 57cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project fmap[j-1] = tmp; 58cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 59cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project} 60cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 61cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 62cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project/*---------------------------------------------*/ 63cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#define fswap(zz1, zz2) \ 64cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; } 65cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 66cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#define fvswap(zzp1, zzp2, zzn) \ 67cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project{ \ 68cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 yyp1 = (zzp1); \ 69cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 yyp2 = (zzp2); \ 70cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 yyn = (zzn); \ 71cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project while (yyn > 0) { \ 72cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project fswap(fmap[yyp1], fmap[yyp2]); \ 73cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project yyp1++; yyp2++; yyn--; \ 74cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } \ 75cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project} 76cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 77cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 78cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#define fmin(a,b) ((a) < (b)) ? (a) : (b) 79cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 80cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#define fpush(lz,hz) { stackLo[sp] = lz; \ 81cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project stackHi[sp] = hz; \ 82cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project sp++; } 83cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 84cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#define fpop(lz,hz) { sp--; \ 85cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project lz = stackLo[sp]; \ 86cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project hz = stackHi[sp]; } 87cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 88cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#define FALLBACK_QSORT_SMALL_THRESH 10 89cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#define FALLBACK_QSORT_STACK_SIZE 100 90cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 91cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 92cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Projectstatic 93cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Projectvoid fallbackQSort3 ( UInt32* fmap, 94cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project UInt32* eclass, 95cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 loSt, 96cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 hiSt ) 97cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project{ 98cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 unLo, unHi, ltLo, gtHi, n, m; 99cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 sp, lo, hi; 100cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project UInt32 med, r, r3; 101cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 stackLo[FALLBACK_QSORT_STACK_SIZE]; 102cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 stackHi[FALLBACK_QSORT_STACK_SIZE]; 103cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 104cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project r = 0; 105cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 106cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project sp = 0; 107cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project fpush ( loSt, hiSt ); 108cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 109cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project while (sp > 0) { 110cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 111cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project AssertH ( sp < FALLBACK_QSORT_STACK_SIZE - 1, 1004 ); 112cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 113cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project fpop ( lo, hi ); 114cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (hi - lo < FALLBACK_QSORT_SMALL_THRESH) { 115cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project fallbackSimpleSort ( fmap, eclass, lo, hi ); 116cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project continue; 117cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 118cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 119cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /* Random partitioning. Median of 3 sometimes fails to 120cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project avoid bad cases. Median of 9 seems to help but 121cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project looks rather expensive. This too seems to work but 122cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project is cheaper. Guidance for the magic constants 123cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 7621 and 32768 is taken from Sedgewick's algorithms 124cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project book, chapter 35. 125cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project */ 126cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project r = ((r * 7621) + 1) % 32768; 127cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project r3 = r % 3; 128cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (r3 == 0) med = eclass[fmap[lo]]; else 129cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (r3 == 1) med = eclass[fmap[(lo+hi)>>1]]; else 130cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project med = eclass[fmap[hi]]; 131cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 132cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project unLo = ltLo = lo; 133cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project unHi = gtHi = hi; 134cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 135cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project while (1) { 136cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project while (1) { 137cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (unLo > unHi) break; 138cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project n = (Int32)eclass[fmap[unLo]] - (Int32)med; 139cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (n == 0) { 140cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project fswap(fmap[unLo], fmap[ltLo]); 141cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ltLo++; unLo++; 142cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project continue; 143cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project }; 144cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (n > 0) break; 145cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project unLo++; 146cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 147cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project while (1) { 148cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (unLo > unHi) break; 149cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project n = (Int32)eclass[fmap[unHi]] - (Int32)med; 150cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (n == 0) { 151cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project fswap(fmap[unHi], fmap[gtHi]); 152cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project gtHi--; unHi--; 153cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project continue; 154cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project }; 155cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (n < 0) break; 156cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project unHi--; 157cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 158cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (unLo > unHi) break; 159cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project fswap(fmap[unLo], fmap[unHi]); unLo++; unHi--; 160cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 161cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 162cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project AssertD ( unHi == unLo-1, "fallbackQSort3(2)" ); 163cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 164cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (gtHi < ltLo) continue; 165cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 166cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project n = fmin(ltLo-lo, unLo-ltLo); fvswap(lo, unLo-n, n); 167cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project m = fmin(hi-gtHi, gtHi-unHi); fvswap(unLo, hi-m+1, m); 168cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 169cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project n = lo + unLo - ltLo - 1; 170cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project m = hi - (gtHi - unHi) + 1; 171cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 172cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (n - lo > hi - m) { 173cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project fpush ( lo, n ); 174cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project fpush ( m, hi ); 175cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } else { 176cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project fpush ( m, hi ); 177cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project fpush ( lo, n ); 178cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 179cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 180cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project} 181cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 182cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#undef fmin 183cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#undef fpush 184cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#undef fpop 185cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#undef fswap 186cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#undef fvswap 187cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#undef FALLBACK_QSORT_SMALL_THRESH 188cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#undef FALLBACK_QSORT_STACK_SIZE 189cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 190cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 191cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project/*---------------------------------------------*/ 192cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project/* Pre: 193cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project nblock > 0 194cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project eclass exists for [0 .. nblock-1] 195cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ((UChar*)eclass) [0 .. nblock-1] holds block 196cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ptr exists for [0 .. nblock-1] 197cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 198cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Post: 199cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ((UChar*)eclass) [0 .. nblock-1] holds block 200cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project All other areas of eclass destroyed 201cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project fmap [0 .. nblock-1] holds sorted order 202cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project bhtab [ 0 .. 2+(nblock/32) ] destroyed 203cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project*/ 204cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 205cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#define SET_BH(zz) bhtab[(zz) >> 5] |= (1 << ((zz) & 31)) 206cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#define CLEAR_BH(zz) bhtab[(zz) >> 5] &= ~(1 << ((zz) & 31)) 207cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#define ISSET_BH(zz) (bhtab[(zz) >> 5] & (1 << ((zz) & 31))) 208cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#define WORD_BH(zz) bhtab[(zz) >> 5] 209cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#define UNALIGNED_BH(zz) ((zz) & 0x01f) 210cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 211cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Projectstatic 212cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Projectvoid fallbackSort ( UInt32* fmap, 213cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project UInt32* eclass, 214cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project UInt32* bhtab, 215cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 nblock, 216cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 verb ) 217cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project{ 218cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 ftab[257]; 219cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 ftabCopy[256]; 220cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 H, i, j, k, l, r, cc, cc1; 221cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 nNotDone; 222cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 nBhtab; 223cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project UChar* eclass8 = (UChar*)eclass; 224cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 225cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /*-- 226cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Initial 1-char radix sort to generate 227cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project initial fmap and initial BH bits. 228cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project --*/ 229cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (verb >= 4) 230cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project VPrintf0 ( " bucket sorting ...\n" ); 231cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project for (i = 0; i < 257; i++) ftab[i] = 0; 232cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project for (i = 0; i < nblock; i++) ftab[eclass8[i]]++; 233cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project for (i = 0; i < 256; i++) ftabCopy[i] = ftab[i]; 234cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project for (i = 1; i < 257; i++) ftab[i] += ftab[i-1]; 235cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 236cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project for (i = 0; i < nblock; i++) { 237cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project j = eclass8[i]; 238cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project k = ftab[j] - 1; 239cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ftab[j] = k; 240cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project fmap[k] = i; 241cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 242cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 243cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project nBhtab = 2 + (nblock / 32); 244cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project for (i = 0; i < nBhtab; i++) bhtab[i] = 0; 245cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project for (i = 0; i < 256; i++) SET_BH(ftab[i]); 246cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 247cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /*-- 248cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Inductively refine the buckets. Kind-of an 249cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project "exponential radix sort" (!), inspired by the 250cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Manber-Myers suffix array construction algorithm. 251cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project --*/ 252cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 253cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /*-- set sentinel bits for block-end detection --*/ 254cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project for (i = 0; i < 32; i++) { 255cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project SET_BH(nblock + 2*i); 256cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project CLEAR_BH(nblock + 2*i + 1); 257cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 258cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 259cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /*-- the log(N) loop --*/ 260cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project H = 1; 261cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project while (1) { 262cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 263cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (verb >= 4) 264cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project VPrintf1 ( " depth %6d has ", H ); 265cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 266cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project j = 0; 267cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project for (i = 0; i < nblock; i++) { 268cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (ISSET_BH(i)) j = i; 269cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project k = fmap[i] - H; if (k < 0) k += nblock; 270cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project eclass[k] = j; 271cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 272cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 273cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project nNotDone = 0; 274cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project r = -1; 275cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project while (1) { 276cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 277cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /*-- find the next non-singleton bucket --*/ 278cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project k = r + 1; 279cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project while (ISSET_BH(k) && UNALIGNED_BH(k)) k++; 280cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (ISSET_BH(k)) { 281cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project while (WORD_BH(k) == 0xffffffff) k += 32; 282cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project while (ISSET_BH(k)) k++; 283cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 284cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project l = k - 1; 285cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (l >= nblock) break; 286cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project while (!ISSET_BH(k) && UNALIGNED_BH(k)) k++; 287cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (!ISSET_BH(k)) { 288cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project while (WORD_BH(k) == 0x00000000) k += 32; 289cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project while (!ISSET_BH(k)) k++; 290cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 291cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project r = k - 1; 292cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (r >= nblock) break; 293cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 294cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /*-- now [l, r] bracket current bucket --*/ 295cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (r > l) { 296cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project nNotDone += (r - l + 1); 297cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project fallbackQSort3 ( fmap, eclass, l, r ); 298cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 299cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /*-- scan bucket and generate header bits-- */ 300cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project cc = -1; 301cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project for (i = l; i <= r; i++) { 302cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project cc1 = eclass[fmap[i]]; 303cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (cc != cc1) { SET_BH(i); cc = cc1; }; 304cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 305cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 306cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 307cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 308cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (verb >= 4) 309cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project VPrintf1 ( "%6d unresolved strings\n", nNotDone ); 310cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 311cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project H *= 2; 312cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (H > nblock || nNotDone == 0) break; 313cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 314cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 315cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /*-- 316cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Reconstruct the original block in 317cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project eclass8 [0 .. nblock-1], since the 318cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project previous phase destroyed it. 319cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project --*/ 320cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (verb >= 4) 321cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project VPrintf0 ( " reconstructing block ...\n" ); 322cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project j = 0; 323cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project for (i = 0; i < nblock; i++) { 324cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project while (ftabCopy[j] == 0) j++; 325cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ftabCopy[j]--; 326cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project eclass8[fmap[i]] = (UChar)j; 327cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 328cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project AssertH ( j < 256, 1005 ); 329cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project} 330cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 331cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#undef SET_BH 332cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#undef CLEAR_BH 333cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#undef ISSET_BH 334cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#undef WORD_BH 335cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#undef UNALIGNED_BH 336cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 337cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 338cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project/*---------------------------------------------*/ 339cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project/*--- The main, O(N^2 log(N)) sorting ---*/ 340cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project/*--- algorithm. Faster for "normal" ---*/ 341cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project/*--- non-repetitive blocks. ---*/ 342cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project/*---------------------------------------------*/ 343cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 344cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project/*---------------------------------------------*/ 345cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Projectstatic 346cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project__inline__ 347cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source ProjectBool mainGtU ( UInt32 i1, 348cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project UInt32 i2, 349cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project UChar* block, 350cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project UInt16* quadrant, 351cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project UInt32 nblock, 352cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32* budget ) 353cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project{ 354cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 k; 355cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project UChar c1, c2; 356cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project UInt16 s1, s2; 357cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 358cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project AssertD ( i1 != i2, "mainGtU" ); 359cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /* 1 */ 360cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project c1 = block[i1]; c2 = block[i2]; 361cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (c1 != c2) return (c1 > c2); 362cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project i1++; i2++; 363cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /* 2 */ 364cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project c1 = block[i1]; c2 = block[i2]; 365cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (c1 != c2) return (c1 > c2); 366cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project i1++; i2++; 367cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /* 3 */ 368cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project c1 = block[i1]; c2 = block[i2]; 369cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (c1 != c2) return (c1 > c2); 370cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project i1++; i2++; 371cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /* 4 */ 372cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project c1 = block[i1]; c2 = block[i2]; 373cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (c1 != c2) return (c1 > c2); 374cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project i1++; i2++; 375cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /* 5 */ 376cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project c1 = block[i1]; c2 = block[i2]; 377cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (c1 != c2) return (c1 > c2); 378cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project i1++; i2++; 379cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /* 6 */ 380cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project c1 = block[i1]; c2 = block[i2]; 381cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (c1 != c2) return (c1 > c2); 382cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project i1++; i2++; 383cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /* 7 */ 384cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project c1 = block[i1]; c2 = block[i2]; 385cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (c1 != c2) return (c1 > c2); 386cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project i1++; i2++; 387cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /* 8 */ 388cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project c1 = block[i1]; c2 = block[i2]; 389cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (c1 != c2) return (c1 > c2); 390cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project i1++; i2++; 391cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /* 9 */ 392cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project c1 = block[i1]; c2 = block[i2]; 393cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (c1 != c2) return (c1 > c2); 394cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project i1++; i2++; 395cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /* 10 */ 396cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project c1 = block[i1]; c2 = block[i2]; 397cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (c1 != c2) return (c1 > c2); 398cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project i1++; i2++; 399cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /* 11 */ 400cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project c1 = block[i1]; c2 = block[i2]; 401cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (c1 != c2) return (c1 > c2); 402cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project i1++; i2++; 403cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /* 12 */ 404cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project c1 = block[i1]; c2 = block[i2]; 405cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (c1 != c2) return (c1 > c2); 406cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project i1++; i2++; 407cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 408cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project k = nblock + 8; 409cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 410cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project do { 411cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /* 1 */ 412cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project c1 = block[i1]; c2 = block[i2]; 413cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (c1 != c2) return (c1 > c2); 414cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project s1 = quadrant[i1]; s2 = quadrant[i2]; 415cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (s1 != s2) return (s1 > s2); 416cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project i1++; i2++; 417cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /* 2 */ 418cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project c1 = block[i1]; c2 = block[i2]; 419cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (c1 != c2) return (c1 > c2); 420cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project s1 = quadrant[i1]; s2 = quadrant[i2]; 421cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (s1 != s2) return (s1 > s2); 422cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project i1++; i2++; 423cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /* 3 */ 424cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project c1 = block[i1]; c2 = block[i2]; 425cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (c1 != c2) return (c1 > c2); 426cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project s1 = quadrant[i1]; s2 = quadrant[i2]; 427cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (s1 != s2) return (s1 > s2); 428cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project i1++; i2++; 429cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /* 4 */ 430cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project c1 = block[i1]; c2 = block[i2]; 431cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (c1 != c2) return (c1 > c2); 432cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project s1 = quadrant[i1]; s2 = quadrant[i2]; 433cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (s1 != s2) return (s1 > s2); 434cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project i1++; i2++; 435cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /* 5 */ 436cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project c1 = block[i1]; c2 = block[i2]; 437cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (c1 != c2) return (c1 > c2); 438cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project s1 = quadrant[i1]; s2 = quadrant[i2]; 439cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (s1 != s2) return (s1 > s2); 440cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project i1++; i2++; 441cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /* 6 */ 442cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project c1 = block[i1]; c2 = block[i2]; 443cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (c1 != c2) return (c1 > c2); 444cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project s1 = quadrant[i1]; s2 = quadrant[i2]; 445cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (s1 != s2) return (s1 > s2); 446cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project i1++; i2++; 447cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /* 7 */ 448cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project c1 = block[i1]; c2 = block[i2]; 449cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (c1 != c2) return (c1 > c2); 450cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project s1 = quadrant[i1]; s2 = quadrant[i2]; 451cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (s1 != s2) return (s1 > s2); 452cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project i1++; i2++; 453cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /* 8 */ 454cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project c1 = block[i1]; c2 = block[i2]; 455cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (c1 != c2) return (c1 > c2); 456cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project s1 = quadrant[i1]; s2 = quadrant[i2]; 457cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (s1 != s2) return (s1 > s2); 458cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project i1++; i2++; 459cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 460cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (i1 >= nblock) i1 -= nblock; 461cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (i2 >= nblock) i2 -= nblock; 462cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 463cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project k -= 8; 464cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project (*budget)--; 465cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 466cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project while (k >= 0); 467cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 468cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project return False; 469cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project} 470cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 471cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 472cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project/*---------------------------------------------*/ 473cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project/*-- 474cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Knuth's increments seem to work better 475cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project than Incerpi-Sedgewick here. Possibly 476cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project because the number of elems to sort is 477cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project usually small, typically <= 20. 478cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project--*/ 479cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Projectstatic 480cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source ProjectInt32 incs[14] = { 1, 4, 13, 40, 121, 364, 1093, 3280, 481cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 9841, 29524, 88573, 265720, 482cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 797161, 2391484 }; 483cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 484cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Projectstatic 485cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Projectvoid mainSimpleSort ( UInt32* ptr, 486cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project UChar* block, 487cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project UInt16* quadrant, 488cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 nblock, 489cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 lo, 490cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 hi, 491cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 d, 492cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32* budget ) 493cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project{ 494cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 i, j, h, bigN, hp; 495cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project UInt32 v; 496cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 497cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project bigN = hi - lo + 1; 498cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (bigN < 2) return; 499cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 500cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project hp = 0; 501cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project while (incs[hp] < bigN) hp++; 502cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project hp--; 503cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 504cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project for (; hp >= 0; hp--) { 505cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project h = incs[hp]; 506cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 507cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project i = lo + h; 508cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project while (True) { 509cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 510cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /*-- copy 1 --*/ 511cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (i > hi) break; 512cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project v = ptr[i]; 513cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project j = i; 514cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project while ( mainGtU ( 515cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ptr[j-h]+d, v+d, block, quadrant, nblock, budget 516cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ) ) { 517cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ptr[j] = ptr[j-h]; 518cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project j = j - h; 519cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (j <= (lo + h - 1)) break; 520cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 521cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ptr[j] = v; 522cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project i++; 523cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 524cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /*-- copy 2 --*/ 525cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (i > hi) break; 526cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project v = ptr[i]; 527cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project j = i; 528cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project while ( mainGtU ( 529cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ptr[j-h]+d, v+d, block, quadrant, nblock, budget 530cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ) ) { 531cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ptr[j] = ptr[j-h]; 532cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project j = j - h; 533cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (j <= (lo + h - 1)) break; 534cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 535cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ptr[j] = v; 536cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project i++; 537cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 538cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /*-- copy 3 --*/ 539cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (i > hi) break; 540cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project v = ptr[i]; 541cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project j = i; 542cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project while ( mainGtU ( 543cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ptr[j-h]+d, v+d, block, quadrant, nblock, budget 544cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ) ) { 545cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ptr[j] = ptr[j-h]; 546cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project j = j - h; 547cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (j <= (lo + h - 1)) break; 548cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 549cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ptr[j] = v; 550cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project i++; 551cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 552cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (*budget < 0) return; 553cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 554cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 555cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project} 556cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 557cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 558cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project/*---------------------------------------------*/ 559cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project/*-- 560cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project The following is an implementation of 561cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project an elegant 3-way quicksort for strings, 562cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project described in a paper "Fast Algorithms for 563cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Sorting and Searching Strings", by Robert 564cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Sedgewick and Jon L. Bentley. 565cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project--*/ 566cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 567cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#define mswap(zz1, zz2) \ 568cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; } 569cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 570cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#define mvswap(zzp1, zzp2, zzn) \ 571cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project{ \ 572cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 yyp1 = (zzp1); \ 573cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 yyp2 = (zzp2); \ 574cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 yyn = (zzn); \ 575cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project while (yyn > 0) { \ 576cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project mswap(ptr[yyp1], ptr[yyp2]); \ 577cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project yyp1++; yyp2++; yyn--; \ 578cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } \ 579cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project} 580cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 581cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Projectstatic 582cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project__inline__ 583cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source ProjectUChar mmed3 ( UChar a, UChar b, UChar c ) 584cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project{ 585cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project UChar t; 586cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (a > b) { t = a; a = b; b = t; }; 587cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (b > c) { 588cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project b = c; 589cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (a > b) b = a; 590cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 591cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project return b; 592cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project} 593cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 594cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#define mmin(a,b) ((a) < (b)) ? (a) : (b) 595cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 596cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#define mpush(lz,hz,dz) { stackLo[sp] = lz; \ 597cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project stackHi[sp] = hz; \ 598cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project stackD [sp] = dz; \ 599cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project sp++; } 600cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 601cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#define mpop(lz,hz,dz) { sp--; \ 602cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project lz = stackLo[sp]; \ 603cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project hz = stackHi[sp]; \ 604cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project dz = stackD [sp]; } 605cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 606cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 607cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#define mnextsize(az) (nextHi[az]-nextLo[az]) 608cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 609cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#define mnextswap(az,bz) \ 610cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project { Int32 tz; \ 611cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project tz = nextLo[az]; nextLo[az] = nextLo[bz]; nextLo[bz] = tz; \ 612cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project tz = nextHi[az]; nextHi[az] = nextHi[bz]; nextHi[bz] = tz; \ 613cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project tz = nextD [az]; nextD [az] = nextD [bz]; nextD [bz] = tz; } 614cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 615cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 616cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#define MAIN_QSORT_SMALL_THRESH 20 617cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#define MAIN_QSORT_DEPTH_THRESH (BZ_N_RADIX + BZ_N_QSORT) 618cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#define MAIN_QSORT_STACK_SIZE 100 619cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 620cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Projectstatic 621cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Projectvoid mainQSort3 ( UInt32* ptr, 622cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project UChar* block, 623cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project UInt16* quadrant, 624cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 nblock, 625cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 loSt, 626cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 hiSt, 627cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 dSt, 628cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32* budget ) 629cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project{ 630cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 unLo, unHi, ltLo, gtHi, n, m, med; 631cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 sp, lo, hi, d; 632cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 633cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 stackLo[MAIN_QSORT_STACK_SIZE]; 634cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 stackHi[MAIN_QSORT_STACK_SIZE]; 635cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 stackD [MAIN_QSORT_STACK_SIZE]; 636cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 637cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 nextLo[3]; 638cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 nextHi[3]; 639cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 nextD [3]; 640cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 641cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project sp = 0; 642cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project mpush ( loSt, hiSt, dSt ); 643cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 644cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project while (sp > 0) { 645cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 646cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project AssertH ( sp < MAIN_QSORT_STACK_SIZE - 2, 1001 ); 647cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 648cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project mpop ( lo, hi, d ); 649cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (hi - lo < MAIN_QSORT_SMALL_THRESH || 650cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project d > MAIN_QSORT_DEPTH_THRESH) { 651cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project mainSimpleSort ( ptr, block, quadrant, nblock, lo, hi, d, budget ); 652cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (*budget < 0) return; 653cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project continue; 654cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 655cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 656cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project med = (Int32) 657cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project mmed3 ( block[ptr[ lo ]+d], 658cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project block[ptr[ hi ]+d], 659cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project block[ptr[ (lo+hi)>>1 ]+d] ); 660cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 661cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project unLo = ltLo = lo; 662cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project unHi = gtHi = hi; 663cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 664cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project while (True) { 665cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project while (True) { 666cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (unLo > unHi) break; 667cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project n = ((Int32)block[ptr[unLo]+d]) - med; 668cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (n == 0) { 669cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project mswap(ptr[unLo], ptr[ltLo]); 670cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ltLo++; unLo++; continue; 671cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project }; 672cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (n > 0) break; 673cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project unLo++; 674cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 675cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project while (True) { 676cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (unLo > unHi) break; 677cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project n = ((Int32)block[ptr[unHi]+d]) - med; 678cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (n == 0) { 679cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project mswap(ptr[unHi], ptr[gtHi]); 680cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project gtHi--; unHi--; continue; 681cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project }; 682cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (n < 0) break; 683cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project unHi--; 684cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 685cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (unLo > unHi) break; 686cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project mswap(ptr[unLo], ptr[unHi]); unLo++; unHi--; 687cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 688cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 689cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project AssertD ( unHi == unLo-1, "mainQSort3(2)" ); 690cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 691cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (gtHi < ltLo) { 692cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project mpush(lo, hi, d+1 ); 693cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project continue; 694cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 695cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 696cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project n = mmin(ltLo-lo, unLo-ltLo); mvswap(lo, unLo-n, n); 697cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project m = mmin(hi-gtHi, gtHi-unHi); mvswap(unLo, hi-m+1, m); 698cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 699cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project n = lo + unLo - ltLo - 1; 700cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project m = hi - (gtHi - unHi) + 1; 701cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 702cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project nextLo[0] = lo; nextHi[0] = n; nextD[0] = d; 703cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project nextLo[1] = m; nextHi[1] = hi; nextD[1] = d; 704cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project nextLo[2] = n+1; nextHi[2] = m-1; nextD[2] = d+1; 705cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 706cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (mnextsize(0) < mnextsize(1)) mnextswap(0,1); 707cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (mnextsize(1) < mnextsize(2)) mnextswap(1,2); 708cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (mnextsize(0) < mnextsize(1)) mnextswap(0,1); 709cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 710cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project AssertD (mnextsize(0) >= mnextsize(1), "mainQSort3(8)" ); 711cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project AssertD (mnextsize(1) >= mnextsize(2), "mainQSort3(9)" ); 712cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 713cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project mpush (nextLo[0], nextHi[0], nextD[0]); 714cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project mpush (nextLo[1], nextHi[1], nextD[1]); 715cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project mpush (nextLo[2], nextHi[2], nextD[2]); 716cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 717cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project} 718cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 719cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#undef mswap 720cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#undef mvswap 721cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#undef mpush 722cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#undef mpop 723cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#undef mmin 724cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#undef mnextsize 725cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#undef mnextswap 726cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#undef MAIN_QSORT_SMALL_THRESH 727cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#undef MAIN_QSORT_DEPTH_THRESH 728cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#undef MAIN_QSORT_STACK_SIZE 729cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 730cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 731cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project/*---------------------------------------------*/ 732cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project/* Pre: 733cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project nblock > N_OVERSHOOT 734cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project block32 exists for [0 .. nblock-1 +N_OVERSHOOT] 735cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ((UChar*)block32) [0 .. nblock-1] holds block 736cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ptr exists for [0 .. nblock-1] 737cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 738cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Post: 739cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ((UChar*)block32) [0 .. nblock-1] holds block 740cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project All other areas of block32 destroyed 741cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ftab [0 .. 65536 ] destroyed 742cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ptr [0 .. nblock-1] holds sorted order 743cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (*budget < 0), sorting was abandoned 744cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project*/ 745cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 746cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#define BIGFREQ(b) (ftab[((b)+1) << 8] - ftab[(b) << 8]) 747cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#define SETMASK (1 << 21) 748cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#define CLEARMASK (~(SETMASK)) 749cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 750cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Projectstatic 751cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Projectvoid mainSort ( UInt32* ptr, 752cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project UChar* block, 753cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project UInt16* quadrant, 754cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project UInt32* ftab, 755cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 nblock, 756cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 verb, 757cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32* budget ) 758cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project{ 759cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 i, j, k, ss, sb; 760cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 runningOrder[256]; 761cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Bool bigDone[256]; 762cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 copyStart[256]; 763cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 copyEnd [256]; 764cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project UChar c1; 765cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 numQSorted; 766cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project UInt16 s; 767cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (verb >= 4) VPrintf0 ( " main sort initialise ...\n" ); 768cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 769cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /*-- set up the 2-byte frequency table --*/ 770cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project for (i = 65536; i >= 0; i--) ftab[i] = 0; 771cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 772cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project j = block[0] << 8; 773cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project i = nblock-1; 774cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project for (; i >= 3; i -= 4) { 775cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project quadrant[i] = 0; 776cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project j = (j >> 8) | ( ((UInt16)block[i]) << 8); 777cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ftab[j]++; 778cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project quadrant[i-1] = 0; 779cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project j = (j >> 8) | ( ((UInt16)block[i-1]) << 8); 780cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ftab[j]++; 781cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project quadrant[i-2] = 0; 782cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project j = (j >> 8) | ( ((UInt16)block[i-2]) << 8); 783cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ftab[j]++; 784cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project quadrant[i-3] = 0; 785cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project j = (j >> 8) | ( ((UInt16)block[i-3]) << 8); 786cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ftab[j]++; 787cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 788cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project for (; i >= 0; i--) { 789cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project quadrant[i] = 0; 790cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project j = (j >> 8) | ( ((UInt16)block[i]) << 8); 791cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ftab[j]++; 792cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 793cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 794cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /*-- (emphasises close relationship of block & quadrant) --*/ 795cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project for (i = 0; i < BZ_N_OVERSHOOT; i++) { 796cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project block [nblock+i] = block[i]; 797cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project quadrant[nblock+i] = 0; 798cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 799cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 800cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (verb >= 4) VPrintf0 ( " bucket sorting ...\n" ); 801cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 802cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /*-- Complete the initial radix sort --*/ 803cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project for (i = 1; i <= 65536; i++) ftab[i] += ftab[i-1]; 804cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 805cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project s = block[0] << 8; 806cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project i = nblock-1; 807cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project for (; i >= 3; i -= 4) { 808cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project s = (s >> 8) | (block[i] << 8); 809cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project j = ftab[s] -1; 810cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ftab[s] = j; 811cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ptr[j] = i; 812cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project s = (s >> 8) | (block[i-1] << 8); 813cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project j = ftab[s] -1; 814cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ftab[s] = j; 815cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ptr[j] = i-1; 816cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project s = (s >> 8) | (block[i-2] << 8); 817cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project j = ftab[s] -1; 818cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ftab[s] = j; 819cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ptr[j] = i-2; 820cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project s = (s >> 8) | (block[i-3] << 8); 821cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project j = ftab[s] -1; 822cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ftab[s] = j; 823cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ptr[j] = i-3; 824cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 825cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project for (; i >= 0; i--) { 826cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project s = (s >> 8) | (block[i] << 8); 827cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project j = ftab[s] -1; 828cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ftab[s] = j; 829cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ptr[j] = i; 830cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 831cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 832cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /*-- 833cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Now ftab contains the first loc of every small bucket. 834cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Calculate the running order, from smallest to largest 835cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project big bucket. 836cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project --*/ 837cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project for (i = 0; i <= 255; i++) { 838cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project bigDone [i] = False; 839cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project runningOrder[i] = i; 840cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 841cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 842cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project { 843cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 vv; 844cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 h = 1; 845cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project do h = 3 * h + 1; while (h <= 256); 846cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project do { 847cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project h = h / 3; 848cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project for (i = h; i <= 255; i++) { 849cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project vv = runningOrder[i]; 850cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project j = i; 851cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project while ( BIGFREQ(runningOrder[j-h]) > BIGFREQ(vv) ) { 852cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project runningOrder[j] = runningOrder[j-h]; 853cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project j = j - h; 854cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (j <= (h - 1)) goto zero; 855cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 856cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project zero: 857cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project runningOrder[j] = vv; 858cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 859cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } while (h != 1); 860cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 861cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 862cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /*-- 863cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project The main sorting loop. 864cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project --*/ 865cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 866cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project numQSorted = 0; 867cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 868cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project for (i = 0; i <= 255; i++) { 869cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 870cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /*-- 871cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Process big buckets, starting with the least full. 872cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Basically this is a 3-step process in which we call 873cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project mainQSort3 to sort the small buckets [ss, j], but 874cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project also make a big effort to avoid the calls if we can. 875cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project --*/ 876cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ss = runningOrder[i]; 877cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 878cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /*-- 879cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Step 1: 880cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Complete the big bucket [ss] by quicksorting 881cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project any unsorted small buckets [ss, j], for j != ss. 882cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Hopefully previous pointer-scanning phases have already 883cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project completed many of the small buckets [ss, j], so 884cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project we don't have to sort them at all. 885cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project --*/ 886cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project for (j = 0; j <= 255; j++) { 887cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (j != ss) { 888cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project sb = (ss << 8) + j; 889cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if ( ! (ftab[sb] & SETMASK) ) { 890cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 lo = ftab[sb] & CLEARMASK; 891cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 hi = (ftab[sb+1] & CLEARMASK) - 1; 892cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (hi > lo) { 893cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (verb >= 4) 894cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project VPrintf4 ( " qsort [0x%x, 0x%x] " 895cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project "done %d this %d\n", 896cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ss, j, numQSorted, hi - lo + 1 ); 897cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project mainQSort3 ( 898cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ptr, block, quadrant, nblock, 899cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project lo, hi, BZ_N_RADIX, budget 900cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ); 901cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project numQSorted += (hi - lo + 1); 902cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (*budget < 0) return; 903cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 904cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 905cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ftab[sb] |= SETMASK; 906cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 907cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 908cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 909cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project AssertH ( !bigDone[ss], 1006 ); 910cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 911cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /*-- 912cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Step 2: 913cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Now scan this big bucket [ss] so as to synthesise the 914cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project sorted order for small buckets [t, ss] for all t, 915cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project including, magically, the bucket [ss,ss] too. 916cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project This will avoid doing Real Work in subsequent Step 1's. 917cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project --*/ 918cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project { 919cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project for (j = 0; j <= 255; j++) { 920cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project copyStart[j] = ftab[(j << 8) + ss] & CLEARMASK; 921cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project copyEnd [j] = (ftab[(j << 8) + ss + 1] & CLEARMASK) - 1; 922cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 923cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project for (j = ftab[ss << 8] & CLEARMASK; j < copyStart[ss]; j++) { 924cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project k = ptr[j]-1; if (k < 0) k += nblock; 925cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project c1 = block[k]; 926cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (!bigDone[c1]) 927cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ptr[ copyStart[c1]++ ] = k; 928cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 929cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project for (j = (ftab[(ss+1) << 8] & CLEARMASK) - 1; j > copyEnd[ss]; j--) { 930cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project k = ptr[j]-1; if (k < 0) k += nblock; 931cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project c1 = block[k]; 932cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (!bigDone[c1]) 933cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ptr[ copyEnd[c1]-- ] = k; 934cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 935cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 936cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 937cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project AssertH ( (copyStart[ss]-1 == copyEnd[ss]) 938cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project || 939cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /* Extremely rare case missing in bzip2-1.0.0 and 1.0.1. 940cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Necessity for this case is demonstrated by compressing 941cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project a sequence of approximately 48.5 million of character 942cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 251; 1.0.0/1.0.1 will then die here. */ 943cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project (copyStart[ss] == 0 && copyEnd[ss] == nblock-1), 944cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 1007 ) 945cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 946cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project for (j = 0; j <= 255; j++) ftab[(j << 8) + ss] |= SETMASK; 947cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 948cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /*-- 949cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Step 3: 950cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project The [ss] big bucket is now done. Record this fact, 951cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project and update the quadrant descriptors. Remember to 952cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project update quadrants in the overshoot area too, if 953cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project necessary. The "if (i < 255)" test merely skips 954cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project this updating for the last bucket processed, since 955cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project updating for the last bucket is pointless. 956cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 957cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project The quadrant array provides a way to incrementally 958cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project cache sort orderings, as they appear, so as to 959cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project make subsequent comparisons in fullGtU() complete 960cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project faster. For repetitive blocks this makes a big 961cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project difference (but not big enough to be able to avoid 962cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project the fallback sorting mechanism, exponential radix sort). 963cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 964cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project The precise meaning is: at all times: 965cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 966cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project for 0 <= i < nblock and 0 <= j <= nblock 967cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 968cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if block[i] != block[j], 969cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 970cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project then the relative values of quadrant[i] and 971cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project quadrant[j] are meaningless. 972cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 973cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project else { 974cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if quadrant[i] < quadrant[j] 975cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project then the string starting at i lexicographically 976cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project precedes the string starting at j 977cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 978cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project else if quadrant[i] > quadrant[j] 979cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project then the string starting at j lexicographically 980cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project precedes the string starting at i 981cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 982cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project else 983cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project the relative ordering of the strings starting 984cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project at i and j has not yet been determined. 985cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 986cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project --*/ 987cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project bigDone[ss] = True; 988cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 989cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (i < 255) { 990cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 bbStart = ftab[ss << 8] & CLEARMASK; 991cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 bbSize = (ftab[(ss+1) << 8] & CLEARMASK) - bbStart; 992cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 shifts = 0; 993cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 994cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project while ((bbSize >> shifts) > 65534) shifts++; 995cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 996cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project for (j = bbSize-1; j >= 0; j--) { 997cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 a2update = ptr[bbStart + j]; 998cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project UInt16 qVal = (UInt16)(j >> shifts); 999cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project quadrant[a2update] = qVal; 1000cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (a2update < BZ_N_OVERSHOOT) 1001cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project quadrant[a2update + nblock] = qVal; 1002cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 1003cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project AssertH ( ((bbSize-1) >> shifts) <= 65535, 1002 ); 1004cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 1005cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 1006cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 1007cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 1008cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (verb >= 4) 1009cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project VPrintf3 ( " %d pointers, %d sorted, %d scanned\n", 1010cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project nblock, numQSorted, nblock - numQSorted ); 1011cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project} 1012cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 1013cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#undef BIGFREQ 1014cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#undef SETMASK 1015cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project#undef CLEARMASK 1016cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 1017cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 1018cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project/*---------------------------------------------*/ 1019cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project/* Pre: 1020cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project nblock > 0 1021cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project arr2 exists for [0 .. nblock-1 +N_OVERSHOOT] 1022cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ((UChar*)arr2) [0 .. nblock-1] holds block 1023cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project arr1 exists for [0 .. nblock-1] 1024cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 1025cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Post: 1026cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ((UChar*)arr2) [0 .. nblock-1] holds block 1027cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project All other areas of block destroyed 1028cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project ftab [ 0 .. 65536 ] destroyed 1029cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project arr1 [0 .. nblock-1] holds sorted order 1030cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project*/ 1031cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Projectvoid BZ2_blockSort ( EState* s ) 1032cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project{ 1033cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project UInt32* ptr = s->ptr; 1034cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project UChar* block = s->block; 1035cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project UInt32* ftab = s->ftab; 1036cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 nblock = s->nblock; 1037cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 verb = s->verbosity; 1038cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 wfact = s->workFactor; 1039cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project UInt16* quadrant; 1040cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 budget; 1041cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 budgetInit; 1042cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Int32 i; 1043cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 1044cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (nblock < 10000) { 1045cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb ); 1046cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } else { 1047cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /* Calculate the location for quadrant, remembering to get 1048cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project the alignment right. Assumes that &(block[0]) is at least 1049cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 2-byte aligned -- this should be ok since block is really 1050cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project the first section of arr2. 1051cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project */ 1052cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project i = nblock+BZ_N_OVERSHOOT; 1053cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (i & 1) i++; 1054cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project quadrant = (UInt16*)(&(block[i])); 1055cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 1056cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project /* (wfact-1) / 3 puts the default-factor-30 1057cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project transition point at very roughly the same place as 1058cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project with v0.1 and v0.9.0. 1059cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project Not that it particularly matters any more, since the 1060cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project resulting compressed stream is now the same regardless 1061cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project of whether or not we use the main sort or fallback sort. 1062cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project */ 1063cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (wfact < 1 ) wfact = 1; 1064cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (wfact > 100) wfact = 100; 1065cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project budgetInit = nblock * ((wfact-1) / 3); 1066cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project budget = budgetInit; 1067cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 1068cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project mainSort ( ptr, block, quadrant, ftab, nblock, verb, &budget ); 1069cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (verb >= 3) 1070cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project VPrintf3 ( " %d work, %d block, ratio %5.2f\n", 1071cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project budgetInit - budget, 1072cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project nblock, 1073cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project (float)(budgetInit - budget) / 1074cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project (float)(nblock==0 ? 1 : nblock) ); 1075cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (budget < 0) { 1076cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (verb >= 2) 1077cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project VPrintf0 ( " too repetitive; using fallback" 1078cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project " sorting algorithm\n" ); 1079cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb ); 1080cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 1081cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project } 1082cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 1083cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project s->origPtr = -1; 1084cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project for (i = 0; i < s->nblock; i++) 1085cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project if (ptr[i] == 0) 1086cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project { s->origPtr = i; break; }; 1087cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 1088cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project AssertH( s->origPtr != -1, 1003 ); 1089cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project} 1090cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 1091cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project 1092cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project/*-------------------------------------------------------------*/ 1093cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project/*--- end blocksort.c ---*/ 1094cfb3b2780016b4e9ab4849e22d9c3acbaf535248The Android Open Source Project/*-------------------------------------------------------------*/ 1095