huffman.c
上传用户:yhdzpy8989
上传日期:2007-06-13
资源大小:13604k
文件大小:8k
- /*
- * ===========================================================================
- * PRODUCTION $Log: huffman.c,v $
- * PRODUCTION Revision 1000.0 2003/10/29 15:44:17 gouriano
- * PRODUCTION PRODUCTION: IMPORTED [ORIGINAL] Dev-tree R1.1
- * PRODUCTION
- * ===========================================================================
- */
- /*-------------------------------------------------------------*/
- /*--- Huffman coding low-level stuff ---*/
- /*--- huffman.c ---*/
- /*-------------------------------------------------------------*/
- /*--
- This file is a part of bzip2 and/or libbzip2, a program and
- library for lossless, block-sorting data compression.
- Copyright (C) 1996-2002 Julian R Seward. All rights reserved.
- Redistribution and use in source and binary forms, with or without
- modification, are permitted provided that the following conditions
- are met:
- 1. Redistributions of source code must retain the above copyright
- notice, this list of conditions and the following disclaimer.
- 2. The origin of this software must not be misrepresented; you must
- not claim that you wrote the original software. If you use this
- software in a product, an acknowledgment in the product
- documentation would be appreciated but is not required.
- 3. Altered source versions must be plainly marked as such, and must
- not be misrepresented as being the original software.
- 4. The name of the author may not be used to endorse or promote
- products derived from this software without specific prior written
- permission.
- THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
- OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
- WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
- DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
- GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
- INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
- WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
- NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
- SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- Julian Seward, Cambridge, UK.
- jseward@acm.org
- bzip2/libbzip2 version 1.0 of 21 March 2000
- This program is based on (at least) the work of:
- Mike Burrows
- David Wheeler
- Peter Fenwick
- Alistair Moffat
- Radford Neal
- Ian H. Witten
- Robert Sedgewick
- Jon L. Bentley
- For more information on these sources, see the manual.
- --*/
- #include "bzlib_private.h"
- /*---------------------------------------------------*/
- #define WEIGHTOF(zz0) ((zz0) & 0xffffff00)
- #define DEPTHOF(zz1) ((zz1) & 0x000000ff)
- #define MYMAX(zz2,zz3) ((zz2) > (zz3) ? (zz2) : (zz3))
- #define ADDWEIGHTS(zw1,zw2)
- (WEIGHTOF(zw1)+WEIGHTOF(zw2)) |
- (1 + MYMAX(DEPTHOF(zw1),DEPTHOF(zw2)))
- #define UPHEAP(z)
- {
- Int32 zz, tmp;
- zz = z; tmp = heap[zz];
- while (weight[tmp] < weight[heap[zz >> 1]]) {
- heap[zz] = heap[zz >> 1];
- zz >>= 1;
- }
- heap[zz] = tmp;
- }
- #define DOWNHEAP(z)
- {
- Int32 zz, yy, tmp;
- zz = z; tmp = heap[zz];
- while (True) {
- yy = zz << 1;
- if (yy > nHeap) break;
- if (yy < nHeap &&
- weight[heap[yy+1]] < weight[heap[yy]])
- yy++;
- if (weight[tmp] < weight[heap[yy]]) break;
- heap[zz] = heap[yy];
- zz = yy;
- }
- heap[zz] = tmp;
- }
- /*---------------------------------------------------*/
- void BZ2_hbMakeCodeLengths ( UChar *len,
- Int32 *freq,
- Int32 alphaSize,
- Int32 maxLen )
- {
- /*--
- Nodes and heap entries run from 1. Entry 0
- for both the heap and nodes is a sentinel.
- --*/
- Int32 nNodes, nHeap, n1, n2, i, j, k;
- Bool tooLong;
- Int32 heap [ BZ_MAX_ALPHA_SIZE + 2 ];
- Int32 weight [ BZ_MAX_ALPHA_SIZE * 2 ];
- Int32 parent [ BZ_MAX_ALPHA_SIZE * 2 ];
- for (i = 0; i < alphaSize; i++)
- weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8;
- while (True) {
- nNodes = alphaSize;
- nHeap = 0;
- heap[0] = 0;
- weight[0] = 0;
- parent[0] = -2;
- for (i = 1; i <= alphaSize; i++) {
- parent[i] = -1;
- nHeap++;
- heap[nHeap] = i;
- UPHEAP(nHeap);
- }
- AssertH( nHeap < (BZ_MAX_ALPHA_SIZE+2), 2001 );
-
- while (nHeap > 1) {
- n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
- n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
- nNodes++;
- parent[n1] = parent[n2] = nNodes;
- weight[nNodes] = ADDWEIGHTS(weight[n1], weight[n2]);
- parent[nNodes] = -1;
- nHeap++;
- heap[nHeap] = nNodes;
- UPHEAP(nHeap);
- }
- AssertH( nNodes < (BZ_MAX_ALPHA_SIZE * 2), 2002 );
- tooLong = False;
- for (i = 1; i <= alphaSize; i++) {
- j = 0;
- k = i;
- while (parent[k] >= 0) { k = parent[k]; j++; }
- len[i-1] = j;
- if (j > maxLen) tooLong = True;
- }
-
- if (! tooLong) break;
- for (i = 1; i < alphaSize; i++) {
- j = weight[i] >> 8;
- j = 1 + (j / 2);
- weight[i] = j << 8;
- }
- }
- }
- /*---------------------------------------------------*/
- void BZ2_hbAssignCodes ( Int32 *code,
- UChar *length,
- Int32 minLen,
- Int32 maxLen,
- Int32 alphaSize )
- {
- Int32 n, vec, i;
- vec = 0;
- for (n = minLen; n <= maxLen; n++) {
- for (i = 0; i < alphaSize; i++)
- if (length[i] == n) { code[i] = vec; vec++; };
- vec <<= 1;
- }
- }
- /*---------------------------------------------------*/
- void BZ2_hbCreateDecodeTables ( Int32 *limit,
- Int32 *base,
- Int32 *perm,
- UChar *length,
- Int32 minLen,
- Int32 maxLen,
- Int32 alphaSize )
- {
- Int32 pp, i, j, vec;
- pp = 0;
- for (i = minLen; i <= maxLen; i++)
- for (j = 0; j < alphaSize; j++)
- if (length[j] == i) { perm[pp] = j; pp++; };
- for (i = 0; i < BZ_MAX_CODE_LEN; i++) base[i] = 0;
- for (i = 0; i < alphaSize; i++) base[length[i]+1]++;
- for (i = 1; i < BZ_MAX_CODE_LEN; i++) base[i] += base[i-1];
- for (i = 0; i < BZ_MAX_CODE_LEN; i++) limit[i] = 0;
- vec = 0;
- for (i = minLen; i <= maxLen; i++) {
- vec += (base[i+1] - base[i]);
- limit[i] = vec-1;
- vec <<= 1;
- }
- for (i = minLen + 1; i <= maxLen; i++)
- base[i] = ((limit[i-1] + 1) << 1) - base[i];
- }
- /*-------------------------------------------------------------*/
- /*--- end huffman.c ---*/
- /*-------------------------------------------------------------*/