src/pypdf/_codecs/_codecs.py
1"""
2This module is for codecs only.
3
4While the codec implementation can contain details of the PDF specification,
5the module should not do any PDF parsing.
6"""
7
8import io
9from abc import ABC, abstractmethod
10from typing import ClassVar
11
12from pypdf._utils import logger_warning
13from pypdf.errors import LimitReachedError, PdfStreamError
14
15
16class Codec(ABC):
17 """Abstract base class for all codecs."""
18
19 @abstractmethod
20 def encode(self, data: bytes) -> bytes:
21 """
22 Encode the input data.
23
24 Args:
25 data: Data to encode.
26
27 Returns:
28 Encoded data.
29
30 """
31
32 @abstractmethod
33 def decode(self, data: bytes) -> bytes:
34 """
35 Decode the input data.
36
37 Args:
38 data: Data to decode.
39
40 Returns:
41 Decoded data.
42
43 """
44
45
46class LzwCodec(Codec):
47 """Lempel-Ziv-Welch (LZW) adaptive compression codec."""
48
49 CLEAR_TABLE_MARKER = 256 # Special code to indicate table reset
50 EOD_MARKER = 257 # End-of-data marker
51 INITIAL_BITS_PER_CODE = 9 # Initial code bit width
52 MAX_BITS_PER_CODE = 12 # Maximum code bit width
53
54 _AND_TABLE: ClassVar[list[int]] = [511, 1023, 2047, 4095]
55
56 def __init__(self, max_output_length: int = 75_000_000) -> None:
57 self.max_output_length = max_output_length
58 self._table_index = -1
59 self._next_bits = -1
60 self._next_data = -1
61 self._byte_pointer = -1
62 self.decoding_table: list[bytes] = []
63
64 def _initialize_encoding_table(self) -> None:
65 """Initialize the encoding table and state to initial conditions."""
66 self.encoding_table: dict[bytes, int] = {bytes([i]): i for i in range(256)}
67 self.next_code = self.EOD_MARKER + 1
68 self.bits_per_code = self.INITIAL_BITS_PER_CODE
69 self.max_code_value = (1 << self.bits_per_code) - 1
70
71 def _increase_next_code(self) -> None:
72 """Update bits_per_code and max_code_value if necessary."""
73 self.next_code += 1
74 if (
75 self.next_code > self.max_code_value
76 and self.bits_per_code < self.MAX_BITS_PER_CODE
77 ):
78 self.bits_per_code += 1
79 self.max_code_value = (1 << self.bits_per_code) - 1
80
81 def encode(self, data: bytes) -> bytes:
82 """
83 Encode data using the LZW compression algorithm.
84
85 Taken from PDF 1.7 specs, "7.4.4.2 Details of LZW Encoding".
86 """
87 result_codes: list[int] = []
88
89 # The encoder shall begin by issuing a clear-table code
90 result_codes.append(self.CLEAR_TABLE_MARKER)
91 self._initialize_encoding_table()
92
93 current_sequence = b""
94 for byte in data:
95 next_sequence = current_sequence + bytes([byte])
96
97 if next_sequence in self.encoding_table:
98 # Extend current sequence if already in the table
99 current_sequence = next_sequence
100 else:
101 # Output code for the current sequence
102 result_codes.append(self.encoding_table[current_sequence])
103
104 # Add the new sequence to the table if there's room
105 if self.next_code <= (1 << self.MAX_BITS_PER_CODE) - 1:
106 self.encoding_table[next_sequence] = self.next_code
107 self._increase_next_code()
108 else:
109 # If the table is full, emit a clear-table command
110 result_codes.append(self.CLEAR_TABLE_MARKER)
111 self._initialize_encoding_table()
112
113 # Start new sequence
114 current_sequence = bytes([byte])
115
116 # Ensure everything actually is encoded
117 if current_sequence:
118 result_codes.append(self.encoding_table[current_sequence])
119 result_codes.append(self.EOD_MARKER)
120
121 return self._pack_codes_into_bytes(result_codes)
122
123 def _pack_codes_into_bytes(self, codes: list[int]) -> bytes:
124 """
125 Convert the list of result codes into a continuous byte stream, with codes packed as per the code bit-width.
126 The bit-width starts at 9 bits and expands as needed.
127 """
128 self._initialize_encoding_table()
129 buffer = 0
130 bits_in_buffer = 0
131 output = bytearray()
132
133 for code in codes:
134 buffer = (buffer << self.bits_per_code) | code
135 bits_in_buffer += self.bits_per_code
136
137 # Codes shall be packed into a continuous bit stream, high-order bit
138 # first. This stream shall then be divided into bytes, high-order bit
139 # first.
140 while bits_in_buffer >= 8:
141 bits_in_buffer -= 8
142 output.append((buffer >> bits_in_buffer) & 0xFF)
143
144 if code == self.CLEAR_TABLE_MARKER:
145 self._initialize_encoding_table()
146 elif code == self.EOD_MARKER:
147 continue
148 else:
149 self._increase_next_code()
150
151 # Flush any remaining bits in the buffer
152 if bits_in_buffer > 0:
153 output.append((buffer << (8 - bits_in_buffer)) & 0xFF)
154
155 return bytes(output)
156
157 def _initialize_decoding_table(self) -> None:
158 self.max_code_value = (1 << self.MAX_BITS_PER_CODE) - 1
159 if not self.decoding_table:
160 self.decoding_table = [
161 bytes([i]) for i in range(self.CLEAR_TABLE_MARKER)
162 ] + [b""] * (
163 self.max_code_value - self.CLEAR_TABLE_MARKER + 1
164 )
165 else:
166 for i in range(self.EOD_MARKER + 1, self._table_index):
167 self.decoding_table[i] = b""
168
169 self._table_index = self.EOD_MARKER + 1
170 self._bits_to_get = 9
171
172 def _next_code_decode(self, data: bytes) -> int:
173 try:
174 while self._next_bits < self._bits_to_get:
175 self._next_data = (self._next_data << 8) | (
176 data[self._byte_pointer]
177 )
178 self._byte_pointer += 1
179 self._next_bits += 8
180
181 code = (
182 self._next_data >> (self._next_bits - self._bits_to_get)
183 ) & self._AND_TABLE[self._bits_to_get - 9]
184 self._next_bits -= self._bits_to_get
185
186 # Reduce data to get rid of the overhead,
187 # which increases performance on large streams significantly.
188 self._next_data = self._next_data & 0xFFFFF
189 except IndexError:
190 return self.EOD_MARKER
191 return code
192
193 # The following method has been converted to Python from PDFsharp:
194 # https://github.com/empira/PDFsharp/blob/5fbf6ed14740bc4e16786816882d32e43af3ff5d/src/foundation/src/PDFsharp/src/PdfSharp/Pdf.Filters/LzwDecode.cs
195 #
196 # Original license:
197 #
198 # -------------------------------------------------------------------------
199 # Copyright (c) 2001-2024 empira Software GmbH, Troisdorf (Cologne Area),
200 # Germany
201 #
202 # http://docs.pdfsharp.net
203 #
204 # MIT License
205 #
206 # Permission is hereby granted, free of charge, to any person obtaining a
207 # copy of this software and associated documentation files (the "Software"),
208 # to deal in the Software without restriction, including without limitation
209 # the rights to use, copy, modify, merge, publish, distribute, sublicense,
210 # and/or sell copies of the Software, and to permit persons to whom the
211 # Software is furnished to do so, subject to the following conditions:
212 #
213 # The above copyright notice and this permission notice shall be included
214 # in all copies or substantial portions of the Software.
215 #
216 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
217 # IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
218 # FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
219 # THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
220 # LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
221 # FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
222 # DEALINGS IN THE SOFTWARE.
223 # --------------------------------------------------------------------------
224 def decode(self, data: bytes) -> bytes:
225 """
226 The following code was converted to Python from the following code:
227 https://github.com/empira/PDFsharp/blob/master/src/foundation/src/PDFsharp/src/PdfSharp/Pdf.Filters/LzwDecode.cs
228 """
229 self._table_index = 0
230 self._byte_pointer = 0
231 self._next_data = 0
232 self._next_bits = 0
233
234 output_stream = io.BytesIO()
235 output_length = 0
236
237 self._initialize_decoding_table()
238 old_code = self.CLEAR_TABLE_MARKER
239
240 while True:
241 code = self._next_code_decode(data)
242 if code == self.EOD_MARKER:
243 break
244
245 if code == self.CLEAR_TABLE_MARKER:
246 self._initialize_decoding_table()
247 code = self._next_code_decode(data)
248 if code == self.EOD_MARKER:
249 break
250 output_stream.write(decoded := self.decoding_table[code])
251 old_code = code
252 elif code < self._table_index:
253 decoded = self.decoding_table[code]
254 output_stream.write(decoded)
255 if old_code != self.CLEAR_TABLE_MARKER:
256 self._add_entry_decode(self.decoding_table[old_code], decoded[0])
257 old_code = code
258 else:
259 # The code is not in the table and not one of the special codes
260 base = self.decoding_table[old_code]
261 if not base:
262 raise PdfStreamError(
263 f"LZW code {code} out of range with empty base at table index {self._table_index}."
264 )
265 decoded = base + base[:1]
266 output_stream.write(decoded)
267 self._add_entry_decode(base, decoded[0])
268 old_code = code
269
270 output_length += len(decoded)
271 if output_length > self.max_output_length:
272 raise LimitReachedError(
273 f"Limit reached while decompressing: {output_length} > {self.max_output_length}"
274 )
275
276 return output_stream.getvalue()
277
278 def _add_entry_decode(self, old_string: bytes, new_char: int) -> None:
279 new_string = old_string + bytes([new_char])
280 if self._table_index > self.max_code_value:
281 logger_warning("Ignoring too large LZW table index.", source=__name__)
282 return
283 self.decoding_table[self._table_index] = new_string
284 self._table_index += 1
285
286 # Update the number of bits to get based on the table index
287 if self._table_index == 511:
288 self._bits_to_get = 10
289 elif self._table_index == 1023:
290 self._bits_to_get = 11
291 elif self._table_index == 2047:
292 self._bits_to_get = 12