Source code

Download source archive ↓

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