From 833d4e7f84f59099ee66eabfa3457ebb7d37eaa8 Mon Sep 17 00:00:00 2001 From: Denys Vlasenko Date: Wed, 3 Nov 2010 02:38:31 +0100 Subject: rename archival/libunarchive -> archival/libarchive; move bz/ into it Signed-off-by: Denys Vlasenko --- archival/bz/huffman.c | 229 -------------------------------------------------- 1 file changed, 229 deletions(-) delete mode 100644 archival/bz/huffman.c (limited to 'archival/bz/huffman.c') diff --git a/archival/bz/huffman.c b/archival/bz/huffman.c deleted file mode 100644 index 676b1af66..000000000 --- a/archival/bz/huffman.c +++ /dev/null @@ -1,229 +0,0 @@ -/* - * bzip2 is written by Julian Seward . - * Adapted for busybox by Denys Vlasenko . - * See README and LICENSE files in this directory for more information. - */ - -/*-------------------------------------------------------------*/ -/*--- Huffman coding low-level stuff ---*/ -/*--- huffman.c ---*/ -/*-------------------------------------------------------------*/ - -/* ------------------------------------------------------------------ -This file is part of bzip2/libbzip2, a program and library for -lossless, block-sorting data compression. - -bzip2/libbzip2 version 1.0.4 of 20 December 2006 -Copyright (C) 1996-2006 Julian Seward - -Please read the WARNING, DISCLAIMER and PATENTS sections in the -README file. - -This program is released under the terms of the license contained -in the file LICENSE. ------------------------------------------------------------------- */ - -/* #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_t zz, tmp; \ - zz = z; \ - tmp = heap[zz]; \ - while (weight[tmp] < weight[heap[zz >> 1]]) { \ - heap[zz] = heap[zz >> 1]; \ - zz >>= 1; \ - } \ - heap[zz] = tmp; \ -} - - -/* 90 bytes, 0.3% of overall compress speed */ -#if CONFIG_BZIP2_FEATURE_SPEED >= 1 - -/* macro works better than inline (gcc 4.2.1) */ -#define DOWNHEAP1(heap, weight, Heap) \ -{ \ - int32_t zz, yy, tmp; \ - zz = 1; \ - tmp = heap[zz]; \ - while (1) { \ - 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; \ -} - -#else - -static -void DOWNHEAP1(int32_t *heap, int32_t *weight, int32_t nHeap) -{ - int32_t zz, yy, tmp; - zz = 1; - tmp = heap[zz]; - while (1) { - 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; -} - -#endif - -/*---------------------------------------------------*/ -static -void BZ2_hbMakeCodeLengths(EState *s, - uint8_t *len, - int32_t *freq, - int32_t alphaSize, - int32_t maxLen) -{ - /* - * Nodes and heap entries run from 1. Entry 0 - * for both the heap and nodes is a sentinel. - */ - int32_t nNodes, nHeap, n1, n2, i, j, k; - Bool tooLong; - - /* bbox: moved to EState to save stack - int32_t heap [BZ_MAX_ALPHA_SIZE + 2]; - int32_t weight[BZ_MAX_ALPHA_SIZE * 2]; - int32_t parent[BZ_MAX_ALPHA_SIZE * 2]; - */ -#define heap (s->BZ2_hbMakeCodeLengths__heap) -#define weight (s->BZ2_hbMakeCodeLengths__weight) -#define parent (s->BZ2_hbMakeCodeLengths__parent) - - for (i = 0; i < alphaSize; i++) - weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8; - - while (1) { - 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--; DOWNHEAP1(heap, weight, nHeap); - n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP1(heap, weight, nHeap); - 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; - - /* 17 Oct 04: keep-going condition for the following loop used - to be 'i < alphaSize', which missed the last element, - theoretically leading to the possibility of the compressor - looping. However, this count-scaling step is only needed if - one of the generated Huffman code words is longer than - maxLen, which up to and including version 1.0.2 was 20 bits, - which is extremely unlikely. In version 1.0.3 maxLen was - changed to 17 bits, which has minimal effect on compression - ratio, but does mean this scaling step is used from time to - time, enough to verify that it works. - - This means that bzip2-1.0.3 and later will only produce - Huffman codes with a maximum length of 17 bits. However, in - order to preserve backwards compatibility with bitstreams - produced by versions pre-1.0.3, the decompressor must still - handle lengths of up to 20. */ - - for (i = 1; i <= alphaSize; i++) { - j = weight[i] >> 8; - /* bbox: yes, it is a signed division. - * don't replace with shift! */ - j = 1 + (j / 2); - weight[i] = j << 8; - } - } -#undef heap -#undef weight -#undef parent -} - - -/*---------------------------------------------------*/ -static -void BZ2_hbAssignCodes(int32_t *code, - uint8_t *length, - int32_t minLen, - int32_t maxLen, - int32_t alphaSize) -{ - int32_t 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; - } -} - - -/*-------------------------------------------------------------*/ -/*--- end huffman.c ---*/ -/*-------------------------------------------------------------*/ -- cgit v1.2.3