| huffman.c (90067) | huffman.c (146293) |
|---|---|
| 1 2/*-------------------------------------------------------------*/ 3/*--- Huffman coding low-level stuff ---*/ 4/*--- huffman.c ---*/ 5/*-------------------------------------------------------------*/ 6 7/*-- 8 This file is a part of bzip2 and/or libbzip2, a program and 9 library for lossless, block-sorting data compression. 10 | 1 2/*-------------------------------------------------------------*/ 3/*--- Huffman coding low-level stuff ---*/ 4/*--- huffman.c ---*/ 5/*-------------------------------------------------------------*/ 6 7/*-- 8 This file is a part of bzip2 and/or libbzip2, a program and 9 library for lossless, block-sorting data compression. 10 |
| 11 Copyright (C) 1996-2002 Julian R Seward. All rights reserved. | 11 Copyright (C) 1996-2005 Julian R Seward. All rights reserved. |
| 12 13 Redistribution and use in source and binary forms, with or without 14 modification, are permitted provided that the following conditions 15 are met: 16 17 1. Redistributions of source code must retain the above copyright 18 notice, this list of conditions and the following disclaimer. 19 --- 17 unchanged lines hidden (view full) --- 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. | 12 13 Redistribution and use in source and binary forms, with or without 14 modification, are permitted provided that the following conditions 15 are met: 16 17 1. Redistributions of source code must retain the above copyright 18 notice, this list of conditions and the following disclaimer. 19 --- 17 unchanged lines hidden (view full) --- 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@acm.org | 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 --- 103 unchanged lines hidden (view full) --- 157 k = i; 158 while (parent[k] >= 0) { k = parent[k]; j++; } 159 len[i-1] = j; 160 if (j > maxLen) tooLong = True; 161 } 162 163 if (! tooLong) break; 164 | 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 --- 103 unchanged lines hidden (view full) --- 157 k = i; 158 while (parent[k] >= 0) { k = parent[k]; j++; } 159 len[i-1] = j; 160 if (j > maxLen) tooLong = True; 161 } 162 163 if (! tooLong) break; 164 |
| 165 for (i = 1; i < alphaSize; i++) { | 165 /* 17 Oct 04: keep-going condition for the following loop used 166 to be 'i < alphaSize', which missed the last element, 167 theoretically leading to the possibility of the compressor 168 looping. However, this count-scaling step is only needed if 169 one of the generated Huffman code words is longer than 170 maxLen, which up to and including version 1.0.2 was 20 bits, 171 which is extremely unlikely. In version 1.0.3 maxLen was 172 changed to 17 bits, which has minimal effect on compression 173 ratio, but does mean this scaling step is used from time to 174 time, enough to verify that it works. 175 176 This means that bzip2-1.0.3 and later will only produce 177 Huffman codes with a maximum length of 17 bits. However, in 178 order to preserve backwards compatibility with bitstreams 179 produced by versions pre-1.0.3, the decompressor must still 180 handle lengths of up to 20. */ 181 182 for (i = 1; i <= alphaSize; i++) { |
| 166 j = weight[i] >> 8; 167 j = 1 + (j / 2); 168 weight[i] = j << 8; 169 } 170 } 171} 172 173 --- 55 unchanged lines hidden --- | 183 j = weight[i] >> 8; 184 j = 1 + (j / 2); 185 weight[i] = j << 8; 186 } 187 } 188} 189 190 --- 55 unchanged lines hidden --- |