diff options
Diffstat (limited to 'blocksort.c')
-rw-r--r-- | blocksort.c | 77 |
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 || |