nest-open-source / nest-learning-thermostat / 5.1 / busybox / 4e78bdb482363ce3d708250ad80a9b303c48ade7 / . / busybox-1.19.3 / archival / libarchive / bz / huffman.c

/* | |

* bzip2 is written by Julian Seward <jseward@bzip.org>. | |

* Adapted for busybox by Denys Vlasenko <vda.linux@googlemail.com>. | |

* 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 <jseward@bzip.org> | |

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 ---*/ | |

/*-------------------------------------------------------------*/ |