1<?php
2
3namespace Mpdf\Gif;
4
5/**
6 * GIF Util - (C) 2003 Yamasoft (S/C)
7 *
8 * All Rights Reserved
9 *
10 * This file can be freely copied, distributed, modified, updated by anyone under the only
11 * condition to leave the original address (Yamasoft, http://www.yamasoft.com) and this header.
12 *
13 * @link http://www.yamasoft.com
14 */
15class Lzw
16{
17
18	var $MAX_LZW_BITS;
19
20	var $Fresh;
21	var $CodeSize;
22	var $SetCodeSize;
23	var $MaxCode;
24	var $MaxCodeSize;
25	var $FirstCode;
26	var $OldCode;
27
28	var $ClearCode;
29	var $EndCode;
30	var $Next;
31	var $Vals;
32	var $Stack;
33	var $sp;
34	var $Buf;
35	var $CurBit;
36	var $LastBit;
37	var $Done;
38	var $LastByte;
39
40	public function __construct()
41	{
42		$this->MAX_LZW_BITS = 12;
43
44		unset($this->Next);
45		unset($this->Vals);
46		unset($this->Stack);
47		unset($this->Buf);
48
49		$this->Next = range(0, (1 << $this->MAX_LZW_BITS) - 1);
50		$this->Vals = range(0, (1 << $this->MAX_LZW_BITS) - 1);
51		$this->Stack = range(0, (1 << ($this->MAX_LZW_BITS + 1)) - 1);
52		$this->Buf = range(0, 279);
53	}
54
55	function deCompress($data, &$datLen)
56	{
57		$stLen = strlen($data);
58		$datLen = 0;
59		$ret = "";
60		$dp = 0;  // data pointer
61		// INITIALIZATION
62		$this->LZWCommandInit($data, $dp);
63
64		while (($iIndex = $this->LZWCommand($data, $dp)) >= 0) {
65			$ret .= chr($iIndex);
66		}
67
68		$datLen = $dp;
69
70		if ($iIndex != -2) {
71			return false;
72		}
73
74		return $ret;
75	}
76
77	function LZWCommandInit(&$data, &$dp)
78	{
79		$this->SetCodeSize = ord($data[0]);
80		$dp += 1;
81
82		$this->CodeSize = $this->SetCodeSize + 1;
83		$this->ClearCode = 1 << $this->SetCodeSize;
84		$this->EndCode = $this->ClearCode + 1;
85		$this->MaxCode = $this->ClearCode + 2;
86		$this->MaxCodeSize = $this->ClearCode << 1;
87
88		$this->GetCodeInit($data, $dp);
89
90		$this->Fresh = 1;
91		for ($i = 0; $i < $this->ClearCode; $i++) {
92			$this->Next[$i] = 0;
93			$this->Vals[$i] = $i;
94		}
95
96		for (; $i < (1 << $this->MAX_LZW_BITS); $i++) {
97			$this->Next[$i] = 0;
98			$this->Vals[$i] = 0;
99		}
100
101		$this->sp = 0;
102		return 1;
103	}
104
105	function LZWCommand(&$data, &$dp)
106	{
107		if ($this->Fresh) {
108			$this->Fresh = 0;
109			do {
110				$this->FirstCode = $this->GetCode($data, $dp);
111				$this->OldCode = $this->FirstCode;
112			} while ($this->FirstCode == $this->ClearCode);
113
114			return $this->FirstCode;
115		}
116
117		if ($this->sp > 0) {
118			$this->sp--;
119			return $this->Stack[$this->sp];
120		}
121
122		while (($Code = $this->GetCode($data, $dp)) >= 0) {
123			if ($Code == $this->ClearCode) {
124				for ($i = 0; $i < $this->ClearCode; $i++) {
125					$this->Next[$i] = 0;
126					$this->Vals[$i] = $i;
127				}
128
129				for (; $i < (1 << $this->MAX_LZW_BITS); $i++) {
130					$this->Next[$i] = 0;
131					$this->Vals[$i] = 0;
132				}
133
134				$this->CodeSize = $this->SetCodeSize + 1;
135				$this->MaxCodeSize = $this->ClearCode << 1;
136				$this->MaxCode = $this->ClearCode + 2;
137				$this->sp = 0;
138				$this->FirstCode = $this->GetCode($data, $dp);
139				$this->OldCode = $this->FirstCode;
140
141				return $this->FirstCode;
142			}
143
144			if ($Code == $this->EndCode) {
145				return -2;
146			}
147
148			$InCode = $Code;
149			if ($Code >= $this->MaxCode) {
150				$this->Stack[$this->sp++] = $this->FirstCode;
151				$Code = $this->OldCode;
152			}
153
154			while ($Code >= $this->ClearCode) {
155				$this->Stack[$this->sp++] = $this->Vals[$Code];
156
157				if ($Code == $this->Next[$Code]) { // Circular table entry, big GIF Error!
158					return -1;
159				}
160
161				$Code = $this->Next[$Code];
162			}
163
164			$this->FirstCode = $this->Vals[$Code];
165			$this->Stack[$this->sp++] = $this->FirstCode;
166
167			if (($Code = $this->MaxCode) < (1 << $this->MAX_LZW_BITS)) {
168				$this->Next[$Code] = $this->OldCode;
169				$this->Vals[$Code] = $this->FirstCode;
170				$this->MaxCode++;
171
172				if (($this->MaxCode >= $this->MaxCodeSize) && ($this->MaxCodeSize < (1 << $this->MAX_LZW_BITS))) {
173					$this->MaxCodeSize *= 2;
174					$this->CodeSize++;
175				}
176			}
177
178			$this->OldCode = $InCode;
179			if ($this->sp > 0) {
180				$this->sp--;
181				return $this->Stack[$this->sp];
182			}
183		}
184
185		return $Code;
186	}
187
188	function GetCodeInit(&$data, &$dp)
189	{
190		$this->CurBit = 0;
191		$this->LastBit = 0;
192		$this->Done = 0;
193		$this->LastByte = 2;
194		return 1;
195	}
196
197	function GetCode(&$data, &$dp)
198	{
199		if (($this->CurBit + $this->CodeSize) >= $this->LastBit) {
200			if ($this->Done) {
201				if ($this->CurBit >= $this->LastBit) {
202					// Ran off the end of my bits
203					return 0;
204				}
205				return -1;
206			}
207
208			$this->Buf[0] = $this->Buf[$this->LastByte - 2];
209			$this->Buf[1] = $this->Buf[$this->LastByte - 1];
210
211			$Count = ord($data[$dp]);
212			$dp += 1;
213
214			if ($Count) {
215				for ($i = 0; $i < $Count; $i++) {
216					$this->Buf[2 + $i] = ord($data[$dp + $i]);
217				}
218				$dp += $Count;
219			} else {
220				$this->Done = 1;
221			}
222
223			$this->LastByte = 2 + $Count;
224			$this->CurBit = ($this->CurBit - $this->LastBit) + 16;
225			$this->LastBit = (2 + $Count) << 3;
226		}
227
228		$iRet = 0;
229		for ($i = $this->CurBit, $j = 0; $j < $this->CodeSize; $i++, $j++) {
230			$iRet |= (($this->Buf[intval($i / 8)] & (1 << ($i % 8))) != 0) << $j;
231		}
232
233		$this->CurBit += $this->CodeSize;
234		return $iRet;
235	}
236}
237