Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
93.83%
304 / 324
58.82%
10 / 17
 CRAP
0.00%
0 / 1
CCITTFaxFilter
93.83%
304 / 324
58.82%
10 / 17
 153.15
0.00%
0 / 1
 __construct
100.00%
1 / 1
100.00%
1 / 1
 1
 encode
100.00%
29 / 29
100.00%
1 / 1
 15
 decode
100.00%
31 / 31
100.00%
1 / 1
 15
 decodeGroup3Row
100.00%
18 / 18
100.00%
1 / 1
 8
 decodeGroup4Row
97.44%
38 / 39
0.00%
0 / 1
 18
 readRunLength
88.24%
15 / 17
0.00%
0 / 1
 8.10
 matchHuffman
100.00%
16 / 16
100.00%
1 / 1
 4
 read2DMode
84.62%
33 / 39
0.00%
0 / 1
 19.18
 findB1
100.00%
8 / 8
100.00%
1 / 1
 6
 findChanging
100.00%
7 / 7
100.00%
1 / 1
 4
 skipEOL
75.00%
9 / 12
0.00%
0 / 1
 4.25
 packRow
100.00%
15 / 15
100.00%
1 / 1
 5
 unpackRow
90.00%
9 / 10
0.00%
0 / 1
 4.02
 encodeRunLength
70.00%
14 / 20
0.00%
0 / 1
 15.89
 encodeGroup3Row
100.00%
13 / 13
100.00%
1 / 1
 5
 encodeGroup4Row
97.56%
40 / 41
0.00%
0 / 1
 18
 bitsToBytes
100.00%
8 / 8
100.00%
1 / 1
 3
1<?php
2
3declare(strict_types=1);
4
5namespace Phpdftk\Filters;
6
7/**
8 * CCITTFaxDecode filter — ITU-T T.4 (Group 3) and T.6 (Group 4) fax codec.
9 *
10 * Encodes/decodes CCITT fax-compressed bitonal image data to/from raw
11 * uncompressed pixel rows (1 bit per pixel, rows padded to byte boundaries).
12 *
13 * Parameters match PDF spec ISO 32000-2 §7.4.6, Table 11:
14 *   K:       <0 = Group 4, 0 = Group 3 (1D), >0 = mixed 1D/2D
15 *   Columns: image width in pixels (default 1728)
16 *   Rows:    image height (0 = determined by EOB/data)
17 *   EndOfLine: require EOL codes (default false)
18 *   EncodedByteAlign: align rows to byte boundary (default false)
19 *   EndOfBlock: use EOFB/RTC codes (default true)
20 *   BlackIs1: if true, 1=black; if false, 0=black (default false)
21 *
22 * @see https://www.itu.int/rec/T-REC-T.4
23 * @see https://www.itu.int/rec/T-REC-T.6
24 */
25final class CCITTFaxFilter implements FilterInterface
26{
27    // White run-length Huffman codes (code => run length)
28    // Key: binary string of bits, Value: run length
29    // Terminating codes (0-63) and make-up codes (64, 128, ..., 2560)
30    private const WHITE_TERMINATING = [
31        '00110101' => 0, '000111' => 1, '0111' => 2, '1000' => 3,
32        '1011' => 4, '1100' => 5, '1110' => 6, '1111' => 7,
33        '10011' => 8, '10100' => 9, '00111' => 10, '01000' => 11,
34        '001000' => 12, '000011' => 13, '110100' => 14, '110101' => 15,
35        '101010' => 16, '101011' => 17, '0100111' => 18, '0001100' => 19,
36        '0001000' => 20, '0010111' => 21, '0000011' => 22, '0000100' => 23,
37        '0101000' => 24, '0101011' => 25, '0010011' => 26, '0100100' => 27,
38        '0011000' => 28, '00000010' => 29, '00000011' => 30, '00011010' => 31,
39        '00011011' => 32, '00010010' => 33, '00010011' => 34, '00010100' => 35,
40        '00010101' => 36, '00010110' => 37, '00010111' => 38, '00101000' => 39,
41        '00101001' => 40, '00101010' => 41, '00101011' => 42, '00101100' => 43,
42        '00101101' => 44, '00000100' => 45, '00000101' => 46, '00001010' => 47,
43        '00001011' => 48, '01010010' => 49, '01010011' => 50, '01010100' => 51,
44        '01010101' => 52, '00100100' => 53, '00100101' => 54, '01011000' => 55,
45        '01011001' => 56, '01011010' => 57, '01011011' => 58, '01001010' => 59,
46        '01001011' => 60, '00110010' => 61, '00110011' => 62, '00110100' => 63,
47    ];
48
49    private const WHITE_MAKEUP = [
50        '11011' => 64, '10010' => 128, '010111' => 192, '0110111' => 256,
51        '00110110' => 320, '00110111' => 384, '01100100' => 448, '01100101' => 512,
52        '01101000' => 576, '01100111' => 640, '011001100' => 704, '011001101' => 768,
53        '011010010' => 832, '011010011' => 896, '011010100' => 960, '011010101' => 1024,
54        '011010110' => 1088, '011010111' => 1152, '011011000' => 1216, '011011001' => 1280,
55        '011011010' => 1344, '011011011' => 1408, '010011000' => 1472, '010011001' => 1536,
56        '010011010' => 1600, '011000' => 1664, '010011011' => 1728,
57    ];
58
59    private const BLACK_TERMINATING = [
60        '0000110111' => 0, '010' => 1, '11' => 2, '10' => 3,
61        '011' => 4, '0011' => 5, '0010' => 6, '00011' => 7,
62        '000101' => 8, '000100' => 9, '0000100' => 10, '0000101' => 11,
63        '0000111' => 12, '00000100' => 13, '00000111' => 14, '000011000' => 15,
64        '0000010111' => 16, '0000011000' => 17, '0000001000' => 18, '00001100111' => 19,
65        '00001101000' => 20, '00001101100' => 21, '00000110111' => 22, '00000101000' => 23,
66        '00000010111' => 24, '00000011000' => 25, '000011001010' => 26, '000011001011' => 27,
67        '000011001100' => 28, '000011001101' => 29, '000001101000' => 30, '000001101001' => 31,
68        '000001101010' => 32, '000001101011' => 33, '000011010010' => 34, '000011010011' => 35,
69        '000011010100' => 36, '000011010101' => 37, '000011010110' => 38, '000011010111' => 39,
70        '000001101100' => 40, '000001101101' => 41, '000011011010' => 42, '000011011011' => 43,
71        '000001010010' => 44, '000001010011' => 45, '000001010100' => 46, '000001010101' => 47,
72        '000001011010' => 48, '000001011011' => 49, '000001100100' => 50, '000001100101' => 51,
73        '000001010110' => 52, '000001010111' => 53, '000001100110' => 54, '000001100111' => 55,
74        '000001101110' => 56, '000001101111' => 57, '000001001000' => 58, '000001001001' => 59,
75        '000001001010' => 60, '000001001011' => 61, '000001001100' => 62, '000001001101' => 63,
76    ];
77
78    private const BLACK_MAKEUP = [
79        '0000001111' => 64, '000011001000' => 128, '000011001001' => 192, '000001011000' => 256,
80        '000000110111' => 320, '000000101000' => 384, '000000010111' => 448, '000000011000' => 512,
81        '0000001100100' => 576, '0000001100101' => 640, '0000001101100' => 704, '0000001101101' => 768,
82        '0000001001010' => 832, '0000001001011' => 896, '0000001001100' => 960, '0000001001101' => 1024,
83        '0000001110010' => 1088, '0000001110011' => 1152, '0000001110100' => 1216, '0000001110101' => 1280,
84        '0000001110110' => 1344, '0000001110111' => 1408, '0000001010010' => 1472, '0000001010011' => 1536,
85        '0000001010100' => 1600, '0000001010101' => 1664, '0000001011010' => 1728,
86    ];
87
88    // Extended make-up codes (shared by white and black, 1792-2560)
89    private const EXTENDED_MAKEUP = [
90        '00000001000' => 1792, '00000001100' => 1856, '00000001101' => 1920,
91        '000000010010' => 1984, '000000010011' => 2048, '000000010100' => 2112,
92        '000000010101' => 2176, '000000010110' => 2240, '000000010111' => 2304,
93        '000000011100' => 2368, '000000011101' => 2432, '000000011110' => 2496,
94        '000000011111' => 2560,
95    ];
96
97    // Reverse lookup tables for encoding (run length => binary string)
98    private const WHITE_TERMINATING_ENC = [
99        0 => '00110101', 1 => '000111', 2 => '0111', 3 => '1000',
100        4 => '1011', 5 => '1100', 6 => '1110', 7 => '1111',
101        8 => '10011', 9 => '10100', 10 => '00111', 11 => '01000',
102        12 => '001000', 13 => '000011', 14 => '110100', 15 => '110101',
103        16 => '101010', 17 => '101011', 18 => '0100111', 19 => '0001100',
104        20 => '0001000', 21 => '0010111', 22 => '0000011', 23 => '0000100',
105        24 => '0101000', 25 => '0101011', 26 => '0010011', 27 => '0100100',
106        28 => '0011000', 29 => '00000010', 30 => '00000011', 31 => '00011010',
107        32 => '00011011', 33 => '00010010', 34 => '00010011', 35 => '00010100',
108        36 => '00010101', 37 => '00010110', 38 => '00010111', 39 => '00101000',
109        40 => '00101001', 41 => '00101010', 42 => '00101011', 43 => '00101100',
110        44 => '00101101', 45 => '00000100', 46 => '00000101', 47 => '00001010',
111        48 => '00001011', 49 => '01010010', 50 => '01010011', 51 => '01010100',
112        52 => '01010101', 53 => '00100100', 54 => '00100101', 55 => '01011000',
113        56 => '01011001', 57 => '01011010', 58 => '01011011', 59 => '01001010',
114        60 => '01001011', 61 => '00110010', 62 => '00110011', 63 => '00110100',
115    ];
116
117    private const WHITE_MAKEUP_ENC = [
118        64 => '11011', 128 => '10010', 192 => '010111', 256 => '0110111',
119        320 => '00110110', 384 => '00110111', 448 => '01100100', 512 => '01100101',
120        576 => '01101000', 640 => '01100111', 704 => '011001100', 768 => '011001101',
121        832 => '011010010', 896 => '011010011', 960 => '011010100', 1024 => '011010101',
122        1088 => '011010110', 1152 => '011010111', 1216 => '011011000', 1280 => '011011001',
123        1344 => '011011010', 1408 => '011011011', 1472 => '010011000', 1536 => '010011001',
124        1600 => '010011010', 1664 => '011000', 1728 => '010011011',
125    ];
126
127    private const BLACK_TERMINATING_ENC = [
128        0 => '0000110111', 1 => '010', 2 => '11', 3 => '10',
129        4 => '011', 5 => '0011', 6 => '0010', 7 => '00011',
130        8 => '000101', 9 => '000100', 10 => '0000100', 11 => '0000101',
131        12 => '0000111', 13 => '00000100', 14 => '00000111', 15 => '000011000',
132        16 => '0000010111', 17 => '0000011000', 18 => '0000001000', 19 => '00001100111',
133        20 => '00001101000', 21 => '00001101100', 22 => '00000110111', 23 => '00000101000',
134        24 => '00000010111', 25 => '00000011000', 26 => '000011001010', 27 => '000011001011',
135        28 => '000011001100', 29 => '000011001101', 30 => '000001101000', 31 => '000001101001',
136        32 => '000001101010', 33 => '000001101011', 34 => '000011010010', 35 => '000011010011',
137        36 => '000011010100', 37 => '000011010101', 38 => '000011010110', 39 => '000011010111',
138        40 => '000001101100', 41 => '000001101101', 42 => '000011011010', 43 => '000011011011',
139        44 => '000001010010', 45 => '000001010011', 46 => '000001010100', 47 => '000001010101',
140        48 => '000001011010', 49 => '000001011011', 50 => '000001100100', 51 => '000001100101',
141        52 => '000001010110', 53 => '000001010111', 54 => '000001100110', 55 => '000001100111',
142        56 => '000001101110', 57 => '000001101111', 58 => '000001001000', 59 => '000001001001',
143        60 => '000001001010', 61 => '000001001011', 62 => '000001001100', 63 => '000001001101',
144    ];
145
146    private const BLACK_MAKEUP_ENC = [
147        64 => '0000001111', 128 => '000011001000', 192 => '000011001001', 256 => '000001011000',
148        320 => '000000110111', 384 => '000000101000', 448 => '000000010111', 512 => '000000011000',
149        576 => '0000001100100', 640 => '0000001100101', 704 => '0000001101100', 768 => '0000001101101',
150        832 => '0000001001010', 896 => '0000001001011', 960 => '0000001001100', 1024 => '0000001001101',
151        1088 => '0000001110010', 1152 => '0000001110011', 1216 => '0000001110100', 1280 => '0000001110101',
152        1344 => '0000001110110', 1408 => '0000001110111', 1472 => '0000001010010', 1536 => '0000001010011',
153        1600 => '0000001010100', 1664 => '0000001010101', 1728 => '0000001011010',
154    ];
155
156    private const EXTENDED_MAKEUP_ENC = [
157        1792 => '00000001000', 1856 => '00000001100', 1920 => '00000001101',
158        1984 => '000000010010', 2048 => '000000010011', 2112 => '000000010100',
159        2176 => '000000010101', 2240 => '000000010110', 2304 => '000000010111',
160        2368 => '000000011100', 2432 => '000000011101', 2496 => '000000011110',
161        2560 => '000000011111',
162    ];
163
164    public function __construct(
165        private int $k = 0,
166        private int $columns = 1728,
167        private int $rows = 0,
168        private bool $endOfLine = false,
169        private bool $encodedByteAlign = false,
170        private bool $endOfBlock = true,
171        private bool $blackIs1 = false,
172    ) {}
173
174    public function encode(string $data): string
175    {
176        if ($data === '') {
177            return '';
178        }
179
180        $bytesPerRow = (int) ceil($this->columns / 8);
181        $rowCount = $this->rows > 0 ? $this->rows : intdiv(strlen($data), $bytesPerRow);
182        $bits = '';
183
184        if ($this->k < 0) {
185            // Group 4 (2D) — T.6
186            $refLine = array_fill(0, $this->columns, 0); // all-white reference
187
188            for ($r = 0; $r < $rowCount; $r++) {
189                if ($this->encodedByteAlign && $r > 0) {
190                    $rem = strlen($bits) % 8;
191                    if ($rem > 0) {
192                        $bits .= str_repeat('0', 8 - $rem);
193                    }
194                }
195
196                $row = $this->unpackRow($data, $r * $bytesPerRow);
197                $bits .= $this->encodeGroup4Row($row, $refLine);
198                $refLine = $row;
199            }
200
201            if ($this->endOfBlock) {
202                // EOFB = two consecutive EOL codes
203                $bits .= '000000000001000000000001';
204            }
205        } else {
206            // Group 3 (1D) — T.4
207            for ($r = 0; $r < $rowCount; $r++) {
208                if ($this->encodedByteAlign && $r > 0) {
209                    $rem = strlen($bits) % 8;
210                    if ($rem > 0) {
211                        $bits .= str_repeat('0', 8 - $rem);
212                    }
213                }
214
215                if ($this->endOfLine) {
216                    $bits .= '000000000001'; // EOL
217                }
218
219                $row = $this->unpackRow($data, $r * $bytesPerRow);
220                $bits .= $this->encodeGroup3Row($row);
221            }
222
223            if ($this->endOfBlock) {
224                // RTC = 6 consecutive EOL codes
225                $bits .= str_repeat('000000000001', 6);
226            }
227        }
228
229        return $this->bitsToBytes($bits);
230    }
231
232    public function decode(string $data): string
233    {
234        if ($data === '') {
235            return '';
236        }
237
238        $bitPos = 0;
239        $dataLen = strlen($data);
240        $output = '';
241        $rowCount = 0;
242        $maxRows = $this->rows > 0 ? $this->rows : PHP_INT_MAX;
243
244        // When endOfBlock is false and rows > 0, stop at row count rather
245        // than scanning for EOFB marker
246        if (!$this->endOfBlock && $this->rows > 0) {
247            $maxRows = $this->rows;
248        }
249
250        if ($this->k < 0) {
251            // Group 4 (2D) — T.6
252            $refLine = array_fill(0, $this->columns, 0); // all white reference
253
254            while ($rowCount < $maxRows && $bitPos < $dataLen * 8) {
255                if ($this->encodedByteAlign) {
256                    $bitPos = (int) (ceil($bitPos / 8) * 8);
257                }
258
259                $row = $this->decodeGroup4Row($data, $bitPos, $refLine);
260                if ($row === null) {
261                    break; // EOFB or end of data
262                }
263                $output .= $this->packRow($row);
264                $refLine = $row;
265                $rowCount++;
266            }
267        } else {
268            // Group 3 (1D) — T.4
269            while ($rowCount < $maxRows && $bitPos < $dataLen * 8) {
270                if ($this->encodedByteAlign) {
271                    $bitPos = (int) (ceil($bitPos / 8) * 8);
272                }
273
274                // Skip EOL if present
275                if ($this->endOfLine) {
276                    $this->skipEOL($data, $bitPos);
277                }
278
279                $row = $this->decodeGroup3Row($data, $bitPos);
280                if ($row === null) {
281                    break;
282                }
283                $output .= $this->packRow($row);
284                $rowCount++;
285            }
286        }
287
288        return $output;
289    }
290
291    /**
292     * Decode a single Group 3 (1D) row.
293     *
294     * @return list<int>|null pixel values (0 or 1), or null at end
295     */
296    private function decodeGroup3Row(string $data, int &$bitPos): ?array
297    {
298        $row = [];
299        $isWhite = true; // rows always start with white
300        $totalPixels = 0;
301
302        while ($totalPixels < $this->columns) {
303            $runLen = $this->readRunLength($data, $bitPos, $isWhite);
304            if ($runLen === null) {
305                if ($totalPixels === 0) {
306                    return null; // end of data
307                }
308                // Pad remaining pixels
309                $remaining = $this->columns - $totalPixels;
310                for ($i = 0; $i < $remaining; $i++) {
311                    $row[] = 0;
312                }
313                break;
314            }
315
316            $pixelValue = $isWhite ? 0 : 1;
317            for ($i = 0; $i < $runLen && $totalPixels < $this->columns; $i++) {
318                $row[] = $pixelValue;
319                $totalPixels++;
320            }
321            $isWhite = !$isWhite;
322        }
323
324        return $row;
325    }
326
327    /**
328     * Decode a single Group 4 (2D) row using the 2D coding modes.
329     *
330     * @param list<int> $refLine reference line pixels
331     * @return list<int>|null pixel values, or null at EOFB
332     */
333    private function decodeGroup4Row(string $data, int &$bitPos, array $refLine): ?array
334    {
335        $row = array_fill(0, $this->columns, 0);
336        $a0 = -1; // imaginary white element before position 0
337        $isWhite = true;
338
339        while ($a0 < $this->columns) {
340            // Read 2D mode code
341            $mode = $this->read2DMode($data, $bitPos);
342            if ($mode === null) {
343                if ($a0 < 0) {
344                    return null; // EOFB
345                }
346                break;
347            }
348
349            $a0Pos = max(0, $a0); // effective position for filling
350
351            switch ($mode) {
352                case 'pass':
353                    // Pass mode: b1 b2 reference — current color continues
354                    $b1 = $this->findB1($refLine, $a0, $isWhite);
355                    $b2 = $this->findChanging($refLine, $b1, $this->columns);
356                    // Fill the passed-over region with current color
357                    $pixelValue = $isWhite ? 0 : 1;
358                    while ($a0Pos < $b2 && $a0Pos < $this->columns) {
359                        $row[$a0Pos++] = $pixelValue;
360                    }
361                    $a0 = $b2;
362                    break;
363
364                case 'horizontal':
365                    // Horizontal mode: two 1D run lengths
366                    $run1 = $this->readRunLength($data, $bitPos, $isWhite) ?? 0;
367                    $run2 = $this->readRunLength($data, $bitPos, !$isWhite) ?? 0;
368
369                    $color1 = $isWhite ? 0 : 1;
370                    for ($i = 0; $i < $run1 && $a0Pos < $this->columns; $i++) {
371                        $row[$a0Pos++] = $color1;
372                    }
373                    $color2 = $isWhite ? 1 : 0;
374                    for ($i = 0; $i < $run2 && $a0Pos < $this->columns; $i++) {
375                        $row[$a0Pos++] = $color2;
376                    }
377                    $a0 = $a0Pos;
378                    break;
379
380                default:
381                    // Vertical mode: V(0), VR(1-3), VL(1-3)
382                    $b1 = $this->findB1($refLine, $a0, $isWhite);
383                    $a1 = $b1 + $mode; // mode is the delta (-3..+3)
384                    $a1 = max($a0Pos, min($a1, $this->columns));
385
386                    $pixelValue = $isWhite ? 0 : 1;
387                    while ($a0Pos < $a1) {
388                        $row[$a0Pos++] = $pixelValue;
389                    }
390                    $a0 = $a1;
391                    $isWhite = !$isWhite;
392                    break;
393            }
394        }
395
396        return $row;
397    }
398
399    /**
400     * Read a run length (terminating + make-up codes).
401     */
402    private function readRunLength(string $data, int &$bitPos, bool $isWhite): ?int
403    {
404        $total = 0;
405        $termTable = $isWhite ? self::WHITE_TERMINATING : self::BLACK_TERMINATING;
406        $makeupTable = $isWhite ? self::WHITE_MAKEUP : self::BLACK_MAKEUP;
407
408        // Read make-up codes first (if any)
409        while (true) {
410            $code = $this->matchHuffman($data, $bitPos, $makeupTable);
411            if ($code === null) {
412                $extCode = $this->matchHuffman($data, $bitPos, self::EXTENDED_MAKEUP);
413                if ($extCode !== null) {
414                    $total += $extCode;
415                    continue;
416                }
417                break;
418            }
419            $total += $code;
420        }
421
422        // Read terminating code
423        $term = $this->matchHuffman($data, $bitPos, $termTable);
424        if ($term === null) {
425            return $total > 0 ? $total : null;
426        }
427        $total += $term;
428
429        return $total;
430    }
431
432    /**
433     * Match a Huffman code from the given table.
434     *
435     * @param array<string, int> $table
436     */
437    private function matchHuffman(string $data, int &$bitPos, array $table): ?int
438    {
439        $savedPos = $bitPos;
440        $bits = '';
441        $maxLen = 13; // longest code in any table
442
443        for ($i = 0; $i < $maxLen; $i++) {
444            $byteIdx = intdiv($bitPos, 8);
445            if ($byteIdx >= strlen($data)) {
446                $bitPos = $savedPos;
447                return null;
448            }
449            $bitIdx = 7 - ($bitPos % 8);
450            $bit = (ord($data[$byteIdx]) >> $bitIdx) & 1;
451            $bits .= $bit;
452            $bitPos++;
453
454            if (isset($table[$bits])) {
455                return $table[$bits];
456            }
457        }
458
459        $bitPos = $savedPos;
460        return null;
461    }
462
463    /**
464     * Read a 2D mode code for Group 4 encoding.
465     *
466     * @return string|int|null 'pass', 'horizontal', or vertical delta (-3..+3), or null at EOFB
467     */
468    private function read2DMode(string $data, int &$bitPos): string|int|null
469    {
470        $savedPos = $bitPos;
471        $bits = '';
472
473        for ($i = 0; $i < 7; $i++) {
474            $byteIdx = intdiv($bitPos, 8);
475            if ($byteIdx >= strlen($data)) {
476                $bitPos = $savedPos;
477                return null;
478            }
479            $bitIdx = 7 - ($bitPos % 8);
480            $bit = (ord($data[$byteIdx]) >> $bitIdx) & 1;
481            $bits .= $bit;
482            $bitPos++;
483
484            $result = match ($bits) {
485                '1'       => 0,          // V(0) — vertical, no offset
486                '011'     => 1,          // VR(1)
487                '010'     => -1,         // VL(1)
488                '001'     => 'horizontal',
489                '0001'    => 'pass',
490                '000011'  => 2,          // VR(2)
491                '000010'  => -2,         // VL(2)
492                '0000011' => 3,          // VR(3)
493                '0000010' => -3,         // VL(3)
494                default   => null,
495            };
496
497            if ($result !== null) {
498                return $result;
499            }
500
501            // Check for EOFB (000000000001 000000000001)
502            if ($bits === '0000000') {
503                // Read more bits to check for EOFB
504                $moreBits = '';
505                for ($j = 0; $j < 17; $j++) {
506                    $byteIdx2 = intdiv($bitPos, 8);
507                    if ($byteIdx2 >= strlen($data)) {
508                        break;
509                    }
510                    $bitIdx2 = 7 - ($bitPos % 8);
511                    $moreBits .= (string) ((ord($data[$byteIdx2]) >> $bitIdx2) & 1);
512                    $bitPos++;
513                }
514                if (str_starts_with($bits . $moreBits, '000000000001000000000001')) {
515                    return null; // EOFB
516                }
517                // Not EOFB — backtrack
518                $bitPos = $savedPos;
519                return null;
520            }
521        }
522
523        $bitPos = $savedPos;
524        return null;
525    }
526
527    /**
528     * Find b1: the first changing element on the reference line to the right
529     * of a0 whose color is opposite to the current coding color.
530     *
531     * Per ITU-T T.6, b1 is a changing element (where pixel color differs
532     * from the previous pixel) strictly after a0, with opposite color.
533     * Position 0 is always a changing element (transition from imaginary white).
534     *
535     * @param list<int> $refLine
536     */
537    private function findB1(array $refLine, int $a0, bool $isWhite): int
538    {
539        $oppositeColor = $isWhite ? 1 : 0;
540        $startPos = max(0, $a0 + 1);
541
542        for ($pos = $startPos; $pos < $this->columns; $pos++) {
543            $current = $refLine[$pos] ?? 0;
544            // Position 0 is a changing element if it differs from imaginary white (0)
545            $prev = ($pos > 0) ? ($refLine[$pos - 1] ?? 0) : 0;
546
547            if ($current !== $prev && $current === $oppositeColor) {
548                return $pos;
549            }
550        }
551
552        return $this->columns;
553    }
554
555    /**
556     * Find the next changing element after position $start in the reference line.
557     *
558     * @param list<int> $refLine
559     */
560    private function findChanging(array $refLine, int $start, int $columns): int
561    {
562        if ($start >= $columns) {
563            return $columns;
564        }
565        $currentColor = $refLine[$start] ?? 0;
566        for ($i = $start + 1; $i < $columns; $i++) {
567            if (($refLine[$i] ?? 0) !== $currentColor) {
568                return $i;
569            }
570        }
571        return $columns;
572    }
573
574    /**
575     * Skip EOL code (000000000001) if present.
576     */
577    private function skipEOL(string $data, int &$bitPos): void
578    {
579        $savedPos = $bitPos;
580        $bits = '';
581        for ($i = 0; $i < 12; $i++) {
582            $byteIdx = intdiv($bitPos, 8);
583            if ($byteIdx >= strlen($data)) {
584                $bitPos = $savedPos;
585                return;
586            }
587            $bitIdx = 7 - ($bitPos % 8);
588            $bits .= (string) ((ord($data[$byteIdx]) >> $bitIdx) & 1);
589            $bitPos++;
590        }
591        if ($bits !== '000000000001') {
592            $bitPos = $savedPos; // not EOL, put bits back
593        }
594    }
595
596    /**
597     * Pack a row of pixel values (0/1) into bytes, with rows padded to byte boundaries.
598     *
599     * @param list<int> $row
600     */
601    private function packRow(array $row): string
602    {
603        $byte = 0;
604        $bitCount = 0;
605        $result = '';
606
607        foreach ($row as $pixel) {
608            $value = $this->blackIs1 ? $pixel : (1 - $pixel);
609            $byte = ($byte << 1) | $value;
610            $bitCount++;
611            if ($bitCount === 8) {
612                $result .= chr($byte);
613                $byte = 0;
614                $bitCount = 0;
615            }
616        }
617
618        // Pad last byte
619        if ($bitCount > 0) {
620            $byte <<= (8 - $bitCount);
621            $result .= chr($byte);
622        }
623
624        return $result;
625    }
626
627    // -----------------------------------------------------------------------
628    // Encode helpers
629    // -----------------------------------------------------------------------
630
631    /**
632     * Unpack raw bytes into pixel values (0/1) — inverse of packRow.
633     *
634     * @return list<int> pixel values (0 = white, 1 = black)
635     */
636    private function unpackRow(string $data, int $offset): array
637    {
638        $row = [];
639        $bytesPerRow = (int) ceil($this->columns / 8);
640
641        for ($i = 0; $i < $this->columns; $i++) {
642            $byteIdx = $offset + intdiv($i, 8);
643            $bitIdx = 7 - ($i % 8);
644            $rawBit = ($byteIdx < strlen($data))
645                ? (ord($data[$byteIdx]) >> $bitIdx) & 1
646                : 0;
647
648            // Invert the packRow transform: packRow does blackIs1 ? pixel : (1-pixel)
649            $row[] = $this->blackIs1 ? $rawBit : (1 - $rawBit);
650        }
651
652        return $row;
653    }
654
655    /**
656     * Encode a run length as Huffman bit codes.
657     */
658    private function encodeRunLength(int $runLength, bool $isWhite): string
659    {
660        $bits = '';
661        $makeupTable = $isWhite ? self::WHITE_MAKEUP_ENC : self::BLACK_MAKEUP_ENC;
662        $termTable = $isWhite ? self::WHITE_TERMINATING_ENC : self::BLACK_TERMINATING_ENC;
663
664        // Extended make-up codes for runs >= 1792 — the smallest extended
665        // makeup is 1792, so the while-guard ensures at least one entry fits.
666        while ($runLength >= 1792) {
667            $best = 1792;
668            foreach (self::EXTENDED_MAKEUP_ENC as $len => $code) {
669                if ($len <= $runLength && $len > $best) {
670                    $best = $len;
671                }
672            }
673            $bits .= self::EXTENDED_MAKEUP_ENC[$best];
674            $runLength -= $best;
675        }
676
677        // Standard make-up codes for runs >= 64
678        if ($runLength >= 64) {
679            // Find largest makeup code that fits
680            $best = 0;
681            foreach ($makeupTable as $len => $code) {
682                if ($len <= $runLength && $len > $best) {
683                    $best = $len;
684                }
685            }
686            if ($best > 0) {
687                $bits .= $makeupTable[$best];
688                $runLength -= $best;
689            }
690        }
691
692        // Terminating code (0-63)
693        $bits .= $termTable[$runLength];
694
695        return $bits;
696    }
697
698    /**
699     * Encode a single row using Group 3 (1D) coding.
700     *
701     * @param list<int> $row pixel values (0 = white, 1 = black)
702     */
703    private function encodeGroup3Row(array $row): string
704    {
705        $bits = '';
706        $isWhite = true;
707        $pos = 0;
708        $len = count($row);
709
710        while ($pos < $len) {
711            // Count run of same-color pixels
712            $runStart = $pos;
713            $currentColor = $isWhite ? 0 : 1;
714            while ($pos < $len && $row[$pos] === $currentColor) {
715                $pos++;
716            }
717            $runLen = $pos - $runStart;
718            $bits .= $this->encodeRunLength($runLen, $isWhite);
719            $isWhite = !$isWhite;
720        }
721
722        // If the row ended on a non-white run, we're done.
723        // If it ended on white and we still need a terminating black run of 0:
724        // Actually, rows just alternate starting from white. If all pixels are white,
725        // we emit white run = columns. No trailing black run needed.
726
727        return $bits;
728    }
729
730    /**
731     * Encode a single row using Group 4 (2D) coding against a reference line.
732     *
733     * @param list<int> $row current row pixel values
734     * @param list<int> $refLine reference line pixel values
735     */
736    private function encodeGroup4Row(array $row, array $refLine): string
737    {
738        $bits = '';
739        $a0 = -1; // imaginary white element before position 0
740        $isWhite = true;
741        $cols = $this->columns;
742
743        while ($a0 < $cols) {
744            $a0Pos = max(0, $a0); // effective position for pixel access
745
746            // a1: first position >= a0Pos where pixel differs from current coding color
747            $currentColor = $isWhite ? 0 : 1;
748            $a1 = $a0Pos;
749            while ($a1 < $cols && $row[$a1] === $currentColor) {
750                $a1++;
751            }
752
753            // a2: next changing element after a1
754            $a2 = $a1;
755            if ($a2 < $cols) {
756                $a2Color = $row[$a2];
757                $a2++;
758                while ($a2 < $cols && $row[$a2] === $a2Color) {
759                    $a2++;
760                }
761            }
762
763            // b1: first changing element on reference line to the right of a0
764            // with opposite color to current coding color
765            $b1 = $this->findB1($refLine, $a0, $isWhite);
766
767            // b2: next changing element after b1
768            $b2 = $this->findChanging($refLine, $b1, $cols);
769
770            if ($b2 < $a1) {
771                // Pass mode
772                $bits .= '0001';
773                $a0 = $b2;
774            } elseif (abs($a1 - $b1) <= 3) {
775                // Vertical mode
776                $delta = $a1 - $b1;
777                $bits .= match ($delta) {
778                    0 => '1',
779                    1 => '011',
780                    -1 => '010',
781                    2 => '000011',
782                    -2 => '000010',
783                    3 => '0000011',
784                    -3 => '0000010',
785                    default => throw new \RuntimeException("Invalid vertical delta: $delta"),
786                };
787                $a0 = $a1;
788                $isWhite = !$isWhite;
789            } else {
790                // Horizontal mode
791                $bits .= '001';
792
793                $run1 = $a1 - $a0Pos;
794                $run2 = $a2 - $a1;
795                $bits .= $this->encodeRunLength($run1, $isWhite);
796                $bits .= $this->encodeRunLength($run2, !$isWhite);
797
798                $a0 = $a2;
799            }
800        }
801
802        return $bits;
803    }
804
805    /**
806     * Convert a binary bit string to bytes (MSB-first, zero-padded).
807     */
808    private function bitsToBytes(string $bits): string
809    {
810        $result = '';
811        $len = strlen($bits);
812        for ($i = 0; $i < $len; $i += 8) {
813            $chunk = substr($bits, $i, 8);
814            if (strlen($chunk) < 8) {
815                $chunk = str_pad($chunk, 8, '0');
816            }
817            $result .= chr((int) bindec($chunk));
818        }
819        return $result;
820    }
821}