Tree::readLengthTable() - Code Metrics - mlocati/chm-lib - Measure and Improve Code Quality continuously with Scrutinizer

Tree::readLengthTable() B
last analyzed 2020-03-31 15:07 UTC

↳ Parent: Tree

Complexity

Conditions	11
Paths	22

Size

Total Lines

Duplication

Lines	15
Ratio	35.71 %

Code Coverage

Tests	31
CRAP Score	11

Importance

Changes

Metric	Value
dl	15
loc	42
ccs	31
cts	31
cp	1
rs	7.3166
c	0
b	0
f	0
cc	11
nc	22
nop	3
crap	11

How to fix Complexity

<?php

namespace CHMLib\LZX;

use Exception;
use CHMLib\Reader\BitReader;

/**
 * Huffman tree used in LZX decoding.
 */
class Tree
{
    /**
     * Table decoding overruns are allowed.
     *
     * @var int
     */
    const LENTABLE_SAFETY = 64;

    /**
     * Maximum number of symbols in the pre-tree.
     *
     * @var int
     */
    const PRETREE_NUM_ELEMENTS = 20;

    /**
     * The number of bits.
     *
     * @var int
     */
    protected $bits;

    /**
     * The maximum symbol.
     *
     * @var int
     */
    protected $maxSymbol;

    /**
     * The symbol list used to decode.
     *
     * @var int[]
     */
    protected $symbols;

    /**
     * The code lengths table.
     *
     * @var int[]
     */
    protected $lens;

    /**
     * Initialize the instance.
     *
     * @param int $bits The number of bits.
     * @param int $maxSymbol The maximum symbol.
     */
    public function __construct($bits, $maxSymbol)
    {
        $this->bits = $bits;
        $this->maxSymbol = $maxSymbol;
        $this->symbols = array_fill(0, (1 << $this->bits) + ($this->maxSymbol << 1), 0);
        $this->lens = array_fill(0, $this->maxSymbol + static::LENTABLE_SAFETY, 0);
    }

    /**
     * Build a fast Huffman decoding table out of just a canonical Huffman code lengths table.
     *
     * @throws \Exception Throws an Exception in case of errors.
     *
     * @author This function was coded by David Tritscher.
     */
    public function makeSymbolTable()
    {
        $bitNum = 1;
        $pos = 0;
        $tableMask = 1 << $this->bits;
        $bitMask = $tableMask >> 1;
        $nextSymbol = $bitMask;
        while ($bitNum <= $this->bits) {
            for ($symbol = 0; $symbol < $this->maxSymbol; ++$symbol) {
                if ($this->lens[$symbol] === $bitNum) {
                    $leaf = $pos;
                    $pos += $bitMask;
                    if ($pos > $tableMask) {
                        throw new Exception('Symbol table overruns');
                    }
                    while ($leaf < $pos) {
                        $this->symbols[$leaf++] = $symbol;
                    }
                }
            }
            $bitMask >>= 1;
            ++$bitNum;
        }
        if ($pos !== $tableMask) {
            for ($i = $pos; $i < $tableMask; ++$i) {
                $this->symbols[$i] = 0;
            }
            $pos <<= 16;
            $tableMask <<= 16;
            $bitMask = 1 << 15;
            while ($bitNum <= 16) {
                for ($symbol = 0; $symbol < $this->maxSymbol; ++$symbol) {
                    if ($this->lens[$symbol] === $bitNum) {
                        $leaf = $pos >> 16;
                        for ($fill = 0; $fill < $bitNum - $this->bits; ++$fill) {
                            if ($this->symbols[$leaf] === 0) {
                                $nextSymbol2 = $nextSymbol << 1;
                                $this->symbols[$nextSymbol2] = 0;
                                $this->symbols[$nextSymbol2 + 1] = 0;
                                $this->symbols[$leaf] = $nextSymbol++;
                            }
                            $leaf = $this->symbols[$leaf] << 1;
                            if ((($pos >> (15 - $fill)) & 1) !== 0) {
                                ++$leaf;
                            }
                        }
                        $this->symbols[$leaf] = $symbol;
                        $pos += $bitMask;
                        if ($pos > $tableMask) {
                            throw new Exception('Symbol table overflow');
                        }
                    }
                }
                $bitMask >>= 1;
                ++$bitNum;
            }
        }
        if ($pos !== $tableMask) {
            for ($sym = 0; $sym < $this->maxSymbol; ++$sym) {
                if ($this->lens[$sym] !== 0) {
                    throw new Exception('Erroneous symbol table');
                }
            }
        }
    }

    /**
     * Read the align lengths data.
     *
     * @param \CHMLib\Reader\BitReader $reader The reader that provides the data.
     *
     * @throws \Exception Throws an Exception in case of errors.
     */
    public function readAlignLengthTable(BitReader $reader)
    {
        for ($i = 0; $i < $this->maxSymbol; ++$i) {

            $this->lens[$i] = $reader->readLE(3);
        }
    }

    /**
     * Read in code lengths for symbols first to last in the given table.
     * The code lengths are stored in their own special LZX way.
     *
     * @param \CHMLib\Reader\BitReader $reader The reader that provides the data.
     * @param int $first
     * @param int $last
     */
    public function readLengthTable(BitReader $reader, $first, $last)
    {
        $preTree = new self(6, static::PRETREE_NUM_ELEMENTS);
        for ($i = 0; $i < $preTree->maxSymbol; ++$i) {

            $preTree->lens[$i] = $reader->readLE(4);
        }
        $preTree->makeSymbolTable();
        for ($pos = $first; $pos < $last;) {
            $symbol = $preTree->readHuffmanSymbol($reader);
            switch ($symbol) {
                case 0x11:

                    $pos2 = $pos + $reader->readLE(4) + 4;
                    while ($pos < $pos2) {
                        $this->lens[$pos++] = 0;
                    }
                    break;
                case 0x12:

                    $pos2 = $pos + $reader->readLE(5) + 20;
                    while ($pos < $pos2) {
                        $this->lens[$pos++] = 0;
                    }
                    break;
                case 0x13:
                    $pos2 = $pos + $reader->readLE(1) + 4;
                    $symbol = $this->lens[$pos] - $preTree->readHuffmanSymbol($reader);
                    if ($symbol < 0) {
                        $symbol += 0x11;
                    }
                    while ($pos < $pos2) {
                        $this->lens[$pos++] = $symbol;
                    }
                    break;
                default:
                    $symbol = $this->lens[$pos] - $symbol;
                    if ($symbol < 0) {
                        $symbol += 0x11;
                    }
                    $this->lens[$pos++] = $symbol;
                    break;
            }
        }
    }

    /**
     * Decode a Huffman symbol from the bitstream using the stated table and return it.
     *
     * @param \CHMLib\Reader\BitReader $reader The reader that provides the data.
     *
     * @throws \Exception Throws an Exception in case of errors.
     *
     * @return int
     */
    public function readHuffmanSymbol(BitReader $reader)
    {
        $next = $reader->peek(16, true);
        $symbol = $this->symbols[$reader->peek($this->bits, true)];
        if ($symbol >= $this->maxSymbol) {
            $j = 1 << (16 - $this->bits);
            do {
                $j >>= 1;
                $symbol <<= 1;
                $symbol |= ($next & $j) > 0 ? 1 : 0;
                $symbol = $this->symbols[$symbol];
            } while ($symbol >= $this->maxSymbol);
        }
        $reader->readLE($this->lens[$symbol]);

        return $symbol;
    }

    /**
     * Clear the code lengths table.
     */
    public function clear()
    {
        $count = count($this->lens);
        $this->lens = array_fill(0, $count, 0);
    }

    /**
     * Check if the length at 0xe8 is not zero.
     *
     * @return bool
     */
    public function isIntel()
    {
        return $this->lens[0xe8] !== 0;
    }
}


1			<?php
2
3			namespace CHMLib\LZX;
4
5			use Exception;
6			use CHMLib\Reader\BitReader;
7
8			/**
9			* Huffman tree used in LZX decoding.
10			*/
11			class Tree
12			{
13			/**
14			* Table decoding overruns are allowed.
15			*
16			* @var int
17			*/
18			const LENTABLE_SAFETY = 64;
19
20			/**
21			* Maximum number of symbols in the pre-tree.
22			*
23			* @var int
24			*/
25			const PRETREE_NUM_ELEMENTS = 20;
26
27			/**
28			* The number of bits.
29			*
30			* @var int
31			*/
32			protected $bits;
33
34			/**
35			* The maximum symbol.
36			*
37			* @var int
38			*/
39			protected $maxSymbol;
40
41			/**
42			* The symbol list used to decode.
43			*
44			* @var int[]
45			*/
46			protected $symbols;
47
48			/**
49			* The code lengths table.
50			*
51			* @var int[]
52			*/
53			protected $lens;
54
55			/**
56			* Initialize the instance.
57			*
58			* @param int $bits The number of bits.
59			* @param int $maxSymbol The maximum symbol.
60			*/
61	483		public function __construct($bits, $maxSymbol)
62			{
63	483		$this->bits = $bits;
64	483		$this->maxSymbol = $maxSymbol;
65	483		$this->symbols = array_fill(0, (1 << $this->bits) + ($this->maxSymbol << 1), 0);
66	483		$this->lens = array_fill(0, $this->maxSymbol + static::LENTABLE_SAFETY, 0);
67	483		}
68
69			/**
70			* Build a fast Huffman decoding table out of just a canonical Huffman code lengths table.
71			*
72			* @throws \Exception Throws an Exception in case of errors.
73			*
74			* @author This function was coded by David Tritscher.
75			*/
76	26		public function makeSymbolTable()
77			{
78	26		$bitNum = 1;
79	26		$pos = 0;
80	26		$tableMask = 1 << $this->bits;
81	26		$bitMask = $tableMask >> 1;
82	26		$nextSymbol = $bitMask;
83	26		while ($bitNum <= $this->bits) {
84	26		for ($symbol = 0; $symbol < $this->maxSymbol; ++$symbol) {
85	26		if ($this->lens[$symbol] === $bitNum) {
86	26		$leaf = $pos;
87	26		$pos += $bitMask;
88	26		if ($pos > $tableMask) {
89			throw new Exception('Symbol table overruns');
90			}
91	26		while ($leaf < $pos) {
92	26		$this->symbols[$leaf++] = $symbol;
93			}
94			}
95			}
96	26		$bitMask >>= 1;
97	26		++$bitNum;
98			}
99	26		if ($pos !== $tableMask) {
100	26		for ($i = $pos; $i < $tableMask; ++$i) {
101	26		$this->symbols[$i] = 0;
102			}
103	26		$pos <<= 16;
104	26		$tableMask <<= 16;
105	26		$bitMask = 1 << 15;
106	26		while ($bitNum <= 16) {
107	26		for ($symbol = 0; $symbol < $this->maxSymbol; ++$symbol) {
108	26		if ($this->lens[$symbol] === $bitNum) {
109	26		$leaf = $pos >> 16;
110	26		for ($fill = 0; $fill < $bitNum - $this->bits; ++$fill) {
111	26		if ($this->symbols[$leaf] === 0) {
112	26		$nextSymbol2 = $nextSymbol << 1;
113	26		$this->symbols[$nextSymbol2] = 0;
114	26		$this->symbols[$nextSymbol2 + 1] = 0;
115	26		$this->symbols[$leaf] = $nextSymbol++;
116			}
117	26		$leaf = $this->symbols[$leaf] << 1;
118	26		if ((($pos >> (15 - $fill)) & 1) !== 0) {
119	26		++$leaf;
120			}
121			}
122	26		$this->symbols[$leaf] = $symbol;
123	26		$pos += $bitMask;
124	26		if ($pos > $tableMask) {
125			throw new Exception('Symbol table overflow');
126			}
127			}
128			}
129	26		$bitMask >>= 1;
130	26		++$bitNum;
131			}
132			}
133	26		if ($pos !== $tableMask) {
134			for ($sym = 0; $sym < $this->maxSymbol; ++$sym) {
135			if ($this->lens[$sym] !== 0) {
136			throw new Exception('Erroneous symbol table');
137			}
138			}
139			}
140	26		}
141
142			/**
143			* Read the align lengths data.
144			*
145			* @param \CHMLib\Reader\BitReader $reader The reader that provides the data.
146			*
147			* @throws \Exception Throws an Exception in case of errors.
148			*/
149	6		public function readAlignLengthTable(BitReader $reader)
150			{
151	6	View Code Duplication	for ($i = 0; $i < $this->maxSymbol; ++$i) {
			0 ignored issues – show Duplication introduced 2016-05-04 14:16 UTC by Report Bug Copy Issue Report This code seems to be duplicated across your project. Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation. You can also find more detailed suggestions in the “Code” section of your repository. Loading history...
152	6		$this->lens[$i] = $reader->readLE(3);
153			}
154	6		}
155
156			/**
157			* Read in code lengths for symbols first to last in the given table.
158			* The code lengths are stored in their own special LZX way.
159			*
160			* @param \CHMLib\Reader\BitReader $reader The reader that provides the data.
161			* @param int $first
162			* @param int $last
163			*/
164	26		public function readLengthTable(BitReader $reader, $first, $last)
165			{
166	26		$preTree = new self(6, static::PRETREE_NUM_ELEMENTS);
167	26	View Code Duplication	for ($i = 0; $i < $preTree->maxSymbol; ++$i) {
			0 ignored issues – show Duplication introduced 2016-05-04 14:16 UTC by Report Bug Copy Issue Report This code seems to be duplicated across your project. Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation. You can also find more detailed suggestions in the “Code” section of your repository. Loading history...
168	26		$preTree->lens[$i] = $reader->readLE(4);
169			}
170	26		$preTree->makeSymbolTable();
171	26		for ($pos = $first; $pos < $last;) {
172	26		$symbol = $preTree->readHuffmanSymbol($reader);
173			switch ($symbol) {
174	26	View Code Duplication	case 0x11:
			0 ignored issues – show Duplication introduced 2016-05-04 14:16 UTC by Report Bug Copy Issue Report This code seems to be duplicated across your project. Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation. You can also find more detailed suggestions in the “Code” section of your repository. Loading history...
175	26		$pos2 = $pos + $reader->readLE(4) + 4;
176	26		while ($pos < $pos2) {
177	26		$this->lens[$pos++] = 0;
178			}
179	26		break;
180	26	View Code Duplication	case 0x12:
			0 ignored issues – show Duplication introduced 2016-05-04 14:16 UTC by Report Bug Copy Issue Report This code seems to be duplicated across your project. Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation. You can also find more detailed suggestions in the “Code” section of your repository. Loading history...
181	26		$pos2 = $pos + $reader->readLE(5) + 20;
182	26		while ($pos < $pos2) {
183	26		$this->lens[$pos++] = 0;
184			}
185	26		break;
186	26		case 0x13:
187	25		$pos2 = $pos + $reader->readLE(1) + 4;
188	25		$symbol = $this->lens[$pos] - $preTree->readHuffmanSymbol($reader);
189	25		if ($symbol < 0) {
190	25		$symbol += 0x11;
191			}
192	25		while ($pos < $pos2) {
193	25		$this->lens[$pos++] = $symbol;
194			}
195	25		break;
196			default:
197	26		$symbol = $this->lens[$pos] - $symbol;
198	26		if ($symbol < 0) {
199	26		$symbol += 0x11;
200			}
201	26		$this->lens[$pos++] = $symbol;
202	26		break;
203			}
204			}
205	26		}
206
207			/**
208			* Decode a Huffman symbol from the bitstream using the stated table and return it.
209			*
210			* @param \CHMLib\Reader\BitReader $reader The reader that provides the data.
211			*
212			* @throws \Exception Throws an Exception in case of errors.
213			*
214			* @return int
215			*/
216	26		public function readHuffmanSymbol(BitReader $reader)
217			{
218	26		$next = $reader->peek(16, true);
219	26		$symbol = $this->symbols[$reader->peek($this->bits, true)];
220	26		if ($symbol >= $this->maxSymbol) {
221	26		$j = 1 << (16 - $this->bits);
222			do {
223	26		$j >>= 1;
224	26		$symbol <<= 1;
225	26		$symbol \|= ($next & $j) > 0 ? 1 : 0;
226	26		$symbol = $this->symbols[$symbol];
227	26		} while ($symbol >= $this->maxSymbol);
228			}
229	26		$reader->readLE($this->lens[$symbol]);
230
231	26		return $symbol;
232			}
233
234			/**
235			* Clear the code lengths table.
236			*/
237	26		public function clear()
238			{
239	26		$count = count($this->lens);
240	26		$this->lens = array_fill(0, $count, 0);
241	26		}
242
243			/**
244			* Check if the length at 0xe8 is not zero.
245			*
246			* @return bool
247			*/
248	26		public function isIntel()
249			{
250	26		return $this->lens[0xe8] !== 0;
251			}
252			}
253

mlocati / chm-lib

Tree::readLengthTable() B last analyzed 2020-03-31 15:07 UTC

Complexity

Size

Duplication

Code Coverage

Importance

How to fix Complexity

Long Method

Duplication Side-by-Side

Filter issues like

Tree::readLengthTable() B
last analyzed 2020-03-31 15:07 UTC