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