wpkg test coverage results

Coverage test results of the Windows Packager by Made to Order Software Corporation.

LCOV - code coverage report
Current view: top level - bzip2 - huffman.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 58 63 92.1 %
Date: 2013-07-16 Functions: 3 3 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : 
       2             : /*-------------------------------------------------------------*/
       3             : /*--- Huffman coding low-level stuff                        ---*/
       4             : /*---                                             huffman.c ---*/
       5             : /*-------------------------------------------------------------*/
       6             : 
       7             : /* ------------------------------------------------------------------
       8             :    This file is part of bzip2/libbzip2, a program and library for
       9             :    lossless, block-sorting data compression.
      10             : 
      11             :    bzip2/libbzip2 version 1.0.6 of 6 September 2010
      12             :    Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>
      13             : 
      14             :    Please read the WARNING, DISCLAIMER and PATENTS sections in the 
      15             :    README file.
      16             : 
      17             :    This program is released under the terms of the license contained
      18             :    in the file LICENSE.
      19             :    ------------------------------------------------------------------ */
      20             : 
      21             : 
      22             : #include "bzlib_private.h"
      23             : 
      24             : /*---------------------------------------------------*/
      25             : #define WEIGHTOF(zz0)  ((zz0) & 0xffffff00)
      26             : #define DEPTHOF(zz1)   ((zz1) & 0x000000ff)
      27             : #define MYMAX(zz2,zz3) ((zz2) > (zz3) ? (zz2) : (zz3))
      28             : 
      29             : #define ADDWEIGHTS(zw1,zw2)                           \
      30             :    (WEIGHTOF(zw1)+WEIGHTOF(zw2)) |                    \
      31             :    (1 + MYMAX(DEPTHOF(zw1),DEPTHOF(zw2)))
      32             : 
      33             : #define UPHEAP(z)                                     \
      34             : {                                                     \
      35             :    Int32 zz, tmp;                                     \
      36             :    zz = z; tmp = heap[zz];                            \
      37             :    while (weight[tmp] < weight[heap[zz >> 1]]) {      \
      38             :       heap[zz] = heap[zz >> 1];                       \
      39             :       zz >>= 1;                                       \
      40             :    }                                                  \
      41             :    heap[zz] = tmp;                                    \
      42             : }
      43             : 
      44             : #define DOWNHEAP(z)                                   \
      45             : {                                                     \
      46             :    Int32 zz, yy, tmp;                                 \
      47             :    zz = z; tmp = heap[zz];                            \
      48             :    while (True) {                                     \
      49             :       yy = zz << 1;                                   \
      50             :       if (yy > nHeap) break;                          \
      51             :       if (yy < nHeap &&                               \
      52             :           weight[heap[yy+1]] < weight[heap[yy]])      \
      53             :          yy++;                                        \
      54             :       if (weight[tmp] < weight[heap[yy]]) break;      \
      55             :       heap[zz] = heap[yy];                            \
      56             :       zz = yy;                                        \
      57             :    }                                                  \
      58             :    heap[zz] = tmp;                                    \
      59             : }
      60             : 
      61             : 
      62             : /*---------------------------------------------------*/
      63       70596 : void BZ2_hbMakeCodeLengths ( UChar *len, 
      64             :                              Int32 *freq,
      65             :                              Int32 alphaSize,
      66             :                              Int32 maxLen )
      67             : {
      68             :    /*--
      69             :       Nodes and heap entries run from 1.  Entry 0
      70             :       for both the heap and nodes is a sentinel.
      71             :    --*/
      72             :    Int32 nNodes, nHeap, n1, n2, i, j, k;
      73             :    Bool  tooLong;
      74             : 
      75             :    Int32 heap   [ BZ_MAX_ALPHA_SIZE + 2 ];
      76             :    Int32 weight [ BZ_MAX_ALPHA_SIZE * 2 ];
      77             :    Int32 parent [ BZ_MAX_ALPHA_SIZE * 2 ]; 
      78             : 
      79    18272536 :    for (i = 0; i < alphaSize; i++)
      80    18201940 :       weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8;
      81             : 
      82             :    while (True) {
      83             : 
      84       70596 :       nNodes = alphaSize;
      85       70596 :       nHeap = 0;
      86             : 
      87       70596 :       heap[0] = 0;
      88       70596 :       weight[0] = 0;
      89       70596 :       parent[0] = -2;
      90             : 
      91    18272536 :       for (i = 1; i <= alphaSize; i++) {
      92    18201940 :          parent[i] = -1;
      93    18201940 :          nHeap++;
      94    18201940 :          heap[nHeap] = i;
      95    38109902 :          UPHEAP(nHeap);
      96             :       }
      97             : 
      98       70596 :       AssertH( nHeap < (BZ_MAX_ALPHA_SIZE+2), 2001 );
      99             :    
     100    18201940 :       while (nHeap > 1) {
     101   119433552 :          n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
     102   114270797 :          n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
     103    18131344 :          nNodes++;
     104    18131344 :          parent[n1] = parent[n2] = nNodes;
     105    18131344 :          weight[nNodes] = ADDWEIGHTS(weight[n1], weight[n2]);
     106    18131344 :          parent[nNodes] = -1;
     107    18131344 :          nHeap++;
     108    18131344 :          heap[nHeap] = nNodes;
     109    19522572 :          UPHEAP(nHeap);
     110             :       }
     111             : 
     112       70596 :       AssertH( nNodes < (BZ_MAX_ALPHA_SIZE * 2), 2002 );
     113             : 
     114       70596 :       tooLong = False;
     115    18272536 :       for (i = 1; i <= alphaSize; i++) {
     116    18201940 :          j = 0;
     117    18201940 :          k = i;
     118   165735807 :          while (parent[k] >= 0) { k = parent[k]; j++; }
     119    18201940 :          len[i-1] = j;
     120    18201940 :          if (j > maxLen) tooLong = True;
     121             :       }
     122             :       
     123       70596 :       if (! tooLong) break;
     124             : 
     125             :       /* 17 Oct 04: keep-going condition for the following loop used
     126             :          to be 'i < alphaSize', which missed the last element,
     127             :          theoretically leading to the possibility of the compressor
     128             :          looping.  However, this count-scaling step is only needed if
     129             :          one of the generated Huffman code words is longer than
     130             :          maxLen, which up to and including version 1.0.2 was 20 bits,
     131             :          which is extremely unlikely.  In version 1.0.3 maxLen was
     132             :          changed to 17 bits, which has minimal effect on compression
     133             :          ratio, but does mean this scaling step is used from time to
     134             :          time, enough to verify that it works.
     135             : 
     136             :          This means that bzip2-1.0.3 and later will only produce
     137             :          Huffman codes with a maximum length of 17 bits.  However, in
     138             :          order to preserve backwards compatibility with bitstreams
     139             :          produced by versions pre-1.0.3, the decompressor must still
     140             :          handle lengths of up to 20. */
     141             : 
     142           0 :       for (i = 1; i <= alphaSize; i++) {
     143           0 :          j = weight[i] >> 8;
     144           0 :          j = 1 + (j / 2);
     145           0 :          weight[i] = j << 8;
     146             :       }
     147           0 :    }
     148       70596 : }
     149             : 
     150             : 
     151             : /*---------------------------------------------------*/
     152       17649 : void BZ2_hbAssignCodes ( Int32 *code,
     153             :                          UChar *length,
     154             :                          Int32 minLen,
     155             :                          Int32 maxLen,
     156             :                          Int32 alphaSize )
     157             : {
     158             :    Int32 n, vec, i;
     159             : 
     160       17649 :    vec = 0;
     161      118423 :    for (n = minLen; n <= maxLen; n++) {
     162    26092100 :       for (i = 0; i < alphaSize; i++)
     163    25991326 :          if (length[i] == n) { code[i] = vec; vec++; };
     164      100774 :       vec <<= 1;
     165             :    }
     166       17649 : }
     167             : 
     168             : 
     169             : /*---------------------------------------------------*/
     170       16143 : void BZ2_hbCreateDecodeTables ( Int32 *limit,
     171             :                                 Int32 *base,
     172             :                                 Int32 *perm,
     173             :                                 UChar *length,
     174             :                                 Int32 minLen,
     175             :                                 Int32 maxLen,
     176             :                                 Int32 alphaSize )
     177             : {
     178             :    Int32 pp, i, j, vec;
     179             : 
     180       16143 :    pp = 0;
     181      106373 :    for (i = minLen; i <= maxLen; i++)
     182    23361204 :       for (j = 0; j < alphaSize; j++)
     183    23270974 :          if (length[j] == i) { perm[pp] = j; pp++; };
     184             : 
     185      387432 :    for (i = 0; i < BZ_MAX_CODE_LEN; i++) base[i] = 0;
     186     4178080 :    for (i = 0; i < alphaSize; i++) base[length[i]+1]++;
     187             : 
     188      371289 :    for (i = 1; i < BZ_MAX_CODE_LEN; i++) base[i] += base[i-1];
     189             : 
     190      387432 :    for (i = 0; i < BZ_MAX_CODE_LEN; i++) limit[i] = 0;
     191       16143 :    vec = 0;
     192             : 
     193      106373 :    for (i = minLen; i <= maxLen; i++) {
     194       90230 :       vec += (base[i+1] - base[i]);
     195       90230 :       limit[i] = vec-1;
     196       90230 :       vec <<= 1;
     197             :    }
     198       90230 :    for (i = minLen + 1; i <= maxLen; i++)
     199       74087 :       base[i] = ((limit[i-1] + 1) << 1) - base[i];
     200       16143 : }
     201             : 
     202             : 
     203             : /*-------------------------------------------------------------*/
     204             : /*--- end                                         huffman.c ---*/
     205             : /*-------------------------------------------------------------*/

Generated by: LCOV version 1.9

The wpkg tool is an open source tool created by Made to Order Software Corporation.