aboutsummaryrefslogtreecommitdiff
path: root/blocksort.c
diff options
context:
space:
mode:
Diffstat (limited to 'blocksort.c')
-rw-r--r--blocksort.c77
1 files changed, 15 insertions, 62 deletions
diff --git a/blocksort.c b/blocksort.c
index 33ec9f5..8535c93 100644
--- a/blocksort.c
+++ b/blocksort.c
@@ -4,66 +4,19 @@
4/*--- blocksort.c ---*/ 4/*--- blocksort.c ---*/
5/*-------------------------------------------------------------*/ 5/*-------------------------------------------------------------*/
6 6
7/*-- 7/* ------------------------------------------------------------------
8 This file is a part of bzip2 and/or libbzip2, a program and 8 This file is part of bzip2/libbzip2, a program and library for
9 library for lossless, block-sorting data compression. 9 lossless, block-sorting data compression.
10 10
11 Copyright (C) 1996-2005 Julian R Seward. All rights reserved. 11 bzip2/libbzip2 version 1.0.4 of 20 December 2006
12 12 Copyright (C) 1996-2006 Julian Seward <jseward@bzip.org>
13 Redistribution and use in source and binary forms, with or without 13
14 modification, are permitted provided that the following conditions 14 Please read the WARNING, DISCLAIMER and PATENTS sections in the
15 are met: 15 README file.
16 16
17 1. Redistributions of source code must retain the above copyright 17 This program is released under the terms of the license contained
18 notice, this list of conditions and the following disclaimer. 18 in the file LICENSE.
19 19 ------------------------------------------------------------------ */
20 2. The origin of this software must not be misrepresented; you must
21 not claim that you wrote the original software. If you use this
22 software in a product, an acknowledgment in the product
23 documentation would be appreciated but is not required.
24
25 3. Altered source versions must be plainly marked as such, and must
26 not be misrepresented as being the original software.
27
28 4. The name of the author may not be used to endorse or promote
29 products derived from this software without specific prior written
30 permission.
31
32 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
33 OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
34 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
35 ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
36 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
37 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
38 GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
39 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
40 WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
41 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
42 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
43
44 Julian Seward, Cambridge, UK.
45 jseward@bzip.org
46 bzip2/libbzip2 version 1.0 of 21 March 2000
47
48 This program is based on (at least) the work of:
49 Mike Burrows
50 David Wheeler
51 Peter Fenwick
52 Alistair Moffat
53 Radford Neal
54 Ian H. Witten
55 Robert Sedgewick
56 Jon L. Bentley
57
58 For more information on these sources, see the manual.
59
60 To get some idea how the block sorting algorithms in this file
61 work, read my paper
62 On the Performance of BWT Sorting Algorithms
63 in Proceedings of the IEEE Data Compression Conference 2000,
64 Snowbird, Utah, USA, 27-30 March 2000. The main sort in this
65 file implements the algorithm called cache in the paper.
66--*/
67 20
68 21
69#include "bzlib_private.h" 22#include "bzlib_private.h"
@@ -155,7 +108,7 @@ void fallbackQSort3 ( UInt32* fmap,
155 108
156 while (sp > 0) { 109 while (sp > 0) {
157 110
158 AssertH ( sp < FALLBACK_QSORT_STACK_SIZE, 1004 ); 111 AssertH ( sp < FALLBACK_QSORT_STACK_SIZE - 1, 1004 );
159 112
160 fpop ( lo, hi ); 113 fpop ( lo, hi );
161 if (hi - lo < FALLBACK_QSORT_SMALL_THRESH) { 114 if (hi - lo < FALLBACK_QSORT_SMALL_THRESH) {
@@ -690,7 +643,7 @@ void mainQSort3 ( UInt32* ptr,
690 643
691 while (sp > 0) { 644 while (sp > 0) {
692 645
693 AssertH ( sp < MAIN_QSORT_STACK_SIZE, 1001 ); 646 AssertH ( sp < MAIN_QSORT_STACK_SIZE - 2, 1001 );
694 647
695 mpop ( lo, hi, d ); 648 mpop ( lo, hi, d );
696 if (hi - lo < MAIN_QSORT_SMALL_THRESH || 649 if (hi - lo < MAIN_QSORT_SMALL_THRESH ||