1<?php
2/**
3 * This file is part of FPDI
4 *
5 * @package   setasign\Fpdi
6 * @copyright Copyright (c) 2020 Setasign GmbH & Co. KG (https://www.setasign.com)
7 * @license   http://opensource.org/licenses/mit-license The MIT License
8 */
9
10namespace setasign\Fpdi\PdfParser\Filter;
11
12/**
13 * Class for handling LZW encoded data
14 *
15 * @package setasign\Fpdi\PdfParser\Filter
16 */
17class Lzw implements FilterInterface
18{
19    /**
20     * @var null|string
21     */
22    protected $data;
23
24    /**
25     * @var array
26     */
27    protected $sTable = [];
28
29    /**
30     * @var int
31     */
32    protected $dataLength = 0;
33
34    /**
35     * @var int
36     */
37    protected $tIdx;
38
39    /**
40     * @var int
41     */
42    protected $bitsToGet = 9;
43
44    /**
45     * @var int
46     */
47    protected $bytePointer;
48
49    /**
50     * @var int
51     */
52    protected $nextData = 0;
53
54    /**
55     * @var int
56     */
57    protected $nextBits = 0;
58
59    /**
60     * @var array
61     */
62    protected $andTable = [511, 1023, 2047, 4095];
63
64    /**
65     * Method to decode LZW compressed data.
66     *
67     * @param string $data The compressed data
68     * @return string The uncompressed data
69     * @throws LzwException
70     */
71    public function decode($data)
72    {
73        if ($data[0] === "\x00" && $data[1] === "\x01") {
74            throw new LzwException(
75                'LZW flavour not supported.',
76                LzwException::LZW_FLAVOUR_NOT_SUPPORTED
77            );
78        }
79
80        $this->initsTable();
81
82        $this->data = $data;
83        $this->dataLength = \strlen($data);
84
85        // Initialize pointers
86        $this->bytePointer = 0;
87
88        $this->nextData = 0;
89        $this->nextBits = 0;
90
91        $oldCode = 0;
92
93        $uncompData = '';
94
95        while (($code = $this->getNextCode()) !== 257) {
96            if ($code === 256) {
97                $this->initsTable();
98                $code = $this->getNextCode();
99
100                if ($code === 257) {
101                    break;
102                }
103
104                $uncompData .= $this->sTable[$code];
105                $oldCode = $code;
106
107            } else {
108                if ($code < $this->tIdx) {
109                    $string = $this->sTable[$code];
110                    $uncompData .= $string;
111
112                    $this->addStringToTable($this->sTable[$oldCode], $string[0]);
113                    $oldCode = $code;
114                } else {
115                    $string = $this->sTable[$oldCode];
116                    $string .= $string[0];
117                    $uncompData .= $string;
118
119                    $this->addStringToTable($string);
120                    $oldCode = $code;
121                }
122            }
123        }
124
125        return $uncompData;
126    }
127
128    /**
129     * Initialize the string table.
130     */
131    protected function initsTable()
132    {
133        $this->sTable = [];
134
135        for ($i = 0; $i < 256; $i++) {
136            $this->sTable[$i] = \chr($i);
137        }
138
139        $this->tIdx = 258;
140        $this->bitsToGet = 9;
141    }
142
143    /**
144     * Add a new string to the string table.
145     *
146     * @param string $oldString
147     * @param string $newString
148     */
149    protected function addStringToTable($oldString, $newString = '')
150    {
151        $string = $oldString . $newString;
152
153        // Add this new String to the table
154        $this->sTable[$this->tIdx++] = $string;
155
156        if ($this->tIdx === 511) {
157            $this->bitsToGet = 10;
158        } elseif ($this->tIdx === 1023) {
159            $this->bitsToGet = 11;
160        } elseif ($this->tIdx === 2047) {
161            $this->bitsToGet = 12;
162        }
163    }
164
165    /**
166     * Returns the next 9, 10, 11 or 12 bits.
167     *
168     * @return integer
169     */
170    protected function getNextCode()
171    {
172        if ($this->bytePointer === $this->dataLength) {
173            return 257;
174        }
175
176        $this->nextData = ($this->nextData << 8) | (\ord($this->data[$this->bytePointer++]) & 0xff);
177        $this->nextBits += 8;
178
179        if ($this->nextBits < $this->bitsToGet) {
180            $this->nextData = ($this->nextData << 8) | (\ord($this->data[$this->bytePointer++]) & 0xff);
181            $this->nextBits += 8;
182        }
183
184        $code = ($this->nextData >> ($this->nextBits - $this->bitsToGet)) & $this->andTable[$this->bitsToGet - 9];
185        $this->nextBits -= $this->bitsToGet;
186
187        return $code;
188    }
189}
190