1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.commons.imaging.formats.tiff.itu_t4;
18
19 import java.io.ByteArrayInputStream;
20 import java.io.IOException;
21
22 import org.apache.commons.imaging.ImagingException;
23 import org.apache.commons.imaging.common.Allocator;
24 import org.apache.commons.imaging.formats.tiff.itu_t4.T4_T6_Tables.Entry;
25
26 public final class T4AndT6Compression {
27 private static final HuffmanTree<Integer> WHITE_RUN_LENGTHS = new HuffmanTree<>();
28 private static final HuffmanTree<Integer> BLACK_RUN_LENGTHS = new HuffmanTree<>();
29 private static final HuffmanTree<Entry> CONTROL_CODES = new HuffmanTree<>();
30
31 public static final int WHITE = 0;
32 public static final int BLACK = 1;
33
34 static {
35 try {
36 for (final Entry entry : T4_T6_Tables.WHITE_TERMINATING_CODES) {
37 WHITE_RUN_LENGTHS.insert(entry.bitString, entry.value);
38 }
39 for (final Entry entry : T4_T6_Tables.WHITE_MAKE_UP_CODES) {
40 WHITE_RUN_LENGTHS.insert(entry.bitString, entry.value);
41 }
42 for (final Entry entry : T4_T6_Tables.BLACK_TERMINATING_CODES) {
43 BLACK_RUN_LENGTHS.insert(entry.bitString, entry.value);
44 }
45 for (final Entry entry : T4_T6_Tables.BLACK_MAKE_UP_CODES) {
46 BLACK_RUN_LENGTHS.insert(entry.bitString, entry.value);
47 }
48 for (final Entry entry : T4_T6_Tables.ADDITIONAL_MAKE_UP_CODES) {
49 WHITE_RUN_LENGTHS.insert(entry.bitString, entry.value);
50 BLACK_RUN_LENGTHS.insert(entry.bitString, entry.value);
51 }
52 CONTROL_CODES.insert(T4_T6_Tables.EOL.bitString, T4_T6_Tables.EOL);
53 CONTROL_CODES.insert(T4_T6_Tables.EOL13.bitString, T4_T6_Tables.EOL13);
54 CONTROL_CODES.insert(T4_T6_Tables.EOL14.bitString, T4_T6_Tables.EOL14);
55 CONTROL_CODES.insert(T4_T6_Tables.EOL15.bitString, T4_T6_Tables.EOL15);
56 CONTROL_CODES.insert(T4_T6_Tables.EOL16.bitString, T4_T6_Tables.EOL16);
57 CONTROL_CODES.insert(T4_T6_Tables.EOL17.bitString, T4_T6_Tables.EOL17);
58 CONTROL_CODES.insert(T4_T6_Tables.EOL18.bitString, T4_T6_Tables.EOL18);
59 CONTROL_CODES.insert(T4_T6_Tables.EOL19.bitString, T4_T6_Tables.EOL19);
60 CONTROL_CODES.insert(T4_T6_Tables.P.bitString, T4_T6_Tables.P);
61 CONTROL_CODES.insert(T4_T6_Tables.H.bitString, T4_T6_Tables.H);
62 CONTROL_CODES.insert(T4_T6_Tables.V0.bitString, T4_T6_Tables.V0);
63 CONTROL_CODES.insert(T4_T6_Tables.VL1.bitString, T4_T6_Tables.VL1);
64 CONTROL_CODES.insert(T4_T6_Tables.VL2.bitString, T4_T6_Tables.VL2);
65 CONTROL_CODES.insert(T4_T6_Tables.VL3.bitString, T4_T6_Tables.VL3);
66 CONTROL_CODES.insert(T4_T6_Tables.VR1.bitString, T4_T6_Tables.VR1);
67 CONTROL_CODES.insert(T4_T6_Tables.VR2.bitString, T4_T6_Tables.VR2);
68 CONTROL_CODES.insert(T4_T6_Tables.VR3.bitString, T4_T6_Tables.VR3);
69 } catch (final ImagingException cannotHappen) {
70 throw new IllegalStateException(cannotHappen);
71 }
72 }
73
74 private static int changingElementAt(final int[] line, final int position) {
75 if (position < 0 || position >= line.length) {
76 return WHITE;
77 }
78 return line[position];
79 }
80
81 private static void compress1DLine(final BitInputStreamFlexible inputStream, final BitArrayOutputStream outputStream, final int[] referenceLine,
82 final int width) throws ImagingException {
83 int color = WHITE;
84 int runLength = 0;
85
86 for (int x = 0; x < width; x++) {
87 try {
88 final int nextColor = inputStream.readBits(1);
89 if (referenceLine != null) {
90 referenceLine[x] = nextColor;
91 }
92 if (color == nextColor) {
93 ++runLength;
94 } else {
95 writeRunLength(outputStream, runLength, color);
96 color = nextColor;
97 runLength = 1;
98 }
99 } catch (final IOException ioException) {
100 throw new ImagingException("Error reading image to compress", ioException);
101 }
102 }
103
104 writeRunLength(outputStream, runLength, color);
105 }
106
107
108
109
110
111
112
113
114
115
116 public static byte[] compressModifiedHuffman(final byte[] uncompressed, final int width, final int height) throws ImagingException {
117 final BitInputStreamFlexible inputStream = new BitInputStreamFlexible(new ByteArrayInputStream(uncompressed));
118 try (BitArrayOutputStream outputStream = new BitArrayOutputStream()) {
119 for (int y = 0; y < height; y++) {
120 compress1DLine(inputStream, outputStream, null, width);
121 inputStream.flushCache();
122 outputStream.flush();
123 }
124 return outputStream.toByteArray();
125 }
126 }
127
128 private static int compressT(final int a0, final int a1, final int b1, final BitArrayOutputStream outputStream, final int codingA0Color,
129 final int[] codingLine) {
130 final int a1b1 = a1 - b1;
131 if (-3 <= a1b1 && a1b1 <= 3) {
132 T4_T6_Tables.Entry entry;
133 switch (a1b1) {
134 case -3:
135 entry = T4_T6_Tables.VL3;
136 break;
137 case -2:
138 entry = T4_T6_Tables.VL2;
139 break;
140 case -1:
141 entry = T4_T6_Tables.VL1;
142 break;
143 case 0:
144 entry = T4_T6_Tables.V0;
145 break;
146 case 1:
147 entry = T4_T6_Tables.VR1;
148 break;
149 case 2:
150 entry = T4_T6_Tables.VR2;
151 break;
152 default:
153 entry = T4_T6_Tables.VR3;
154 break;
155 }
156 entry.writeBits(outputStream);
157 return a1;
158 }
159 final int a2 = nextChangingElement(codingLine, 1 - codingA0Color, a1 + 1);
160 final int a0a1 = a1 - a0;
161 final int a1a2 = a2 - a1;
162 T4_T6_Tables.H.writeBits(outputStream);
163 writeRunLength(outputStream, a0a1, codingA0Color);
164 writeRunLength(outputStream, a1a2, 1 - codingA0Color);
165 return a2;
166 }
167
168 public static byte[] compressT4_1D(final byte[] uncompressed, final int width, final int height, final boolean hasFill) throws ImagingException {
169 final BitInputStreamFlexible inputStream = new BitInputStreamFlexible(new ByteArrayInputStream(uncompressed));
170 try (BitArrayOutputStream outputStream = new BitArrayOutputStream()) {
171 if (hasFill) {
172 T4_T6_Tables.EOL16.writeBits(outputStream);
173 } else {
174 T4_T6_Tables.EOL.writeBits(outputStream);
175 }
176
177 for (int y = 0; y < height; y++) {
178 compress1DLine(inputStream, outputStream, null, width);
179 if (hasFill) {
180 int bitsAvailable = outputStream.getBitsAvailableInCurrentByte();
181 if (bitsAvailable < 4) {
182 outputStream.flush();
183 bitsAvailable = 8;
184 }
185 for (; bitsAvailable > 4; bitsAvailable--) {
186 outputStream.writeBit(0);
187 }
188 }
189 T4_T6_Tables.EOL.writeBits(outputStream);
190 inputStream.flushCache();
191 }
192
193 return outputStream.toByteArray();
194 }
195 }
196
197 public static byte[] compressT4_2D(final byte[] uncompressed, final int width, final int height, final boolean hasFill, final int parameterK)
198 throws ImagingException {
199 final BitInputStreamFlexible inputStream = new BitInputStreamFlexible(new ByteArrayInputStream(uncompressed));
200 final BitArrayOutputStream outputStream = new BitArrayOutputStream();
201 int[] referenceLine = Allocator.intArray(width);
202 int[] codingLine = Allocator.intArray(width);
203 int kCounter = 0;
204 if (hasFill) {
205 T4_T6_Tables.EOL16.writeBits(outputStream);
206 } else {
207 T4_T6_Tables.EOL.writeBits(outputStream);
208 }
209
210 for (int y = 0; y < height; y++) {
211 if (kCounter > 0) {
212
213 outputStream.writeBit(0);
214 for (int i = 0; i < width; i++) {
215 try {
216 codingLine[i] = inputStream.readBits(1);
217 } catch (final IOException ioException) {
218 throw new ImagingException("Error reading image to compress", ioException);
219 }
220 }
221 int codingA0Color = WHITE;
222 int referenceA0Color = WHITE;
223 int a1 = nextChangingElement(codingLine, codingA0Color, 0);
224 int b1 = nextChangingElement(referenceLine, referenceA0Color, 0);
225 int b2 = nextChangingElement(referenceLine, 1 - referenceA0Color, b1 + 1);
226 for (int a0 = 0; a0 < width;) {
227 if (b2 < a1) {
228 T4_T6_Tables.P.writeBits(outputStream);
229 a0 = b2;
230 } else {
231 a0 = compressT(a0, a1, b1, outputStream, codingA0Color, codingLine);
232 if (a0 == a1) {
233 codingA0Color = 1 - codingA0Color;
234 }
235 }
236 referenceA0Color = changingElementAt(referenceLine, a0);
237 a1 = nextChangingElement(codingLine, codingA0Color, a0 + 1);
238 if (codingA0Color == referenceA0Color) {
239 b1 = nextChangingElement(referenceLine, referenceA0Color, a0 + 1);
240 } else {
241 b1 = nextChangingElement(referenceLine, referenceA0Color, a0 + 1);
242 b1 = nextChangingElement(referenceLine, 1 - referenceA0Color, b1 + 1);
243 }
244 b2 = nextChangingElement(referenceLine, 1 - codingA0Color, b1 + 1);
245 }
246 final int[] swap = referenceLine;
247 referenceLine = codingLine;
248 codingLine = swap;
249 } else {
250
251 outputStream.writeBit(1);
252 compress1DLine(inputStream, outputStream, referenceLine, width);
253 }
254 if (hasFill) {
255 int bitsAvailable = outputStream.getBitsAvailableInCurrentByte();
256 if (bitsAvailable < 4) {
257 outputStream.flush();
258 bitsAvailable = 8;
259 }
260 for (; bitsAvailable > 4; bitsAvailable--) {
261 outputStream.writeBit(0);
262 }
263 }
264 T4_T6_Tables.EOL.writeBits(outputStream);
265 kCounter++;
266 if (kCounter == parameterK) {
267 kCounter = 0;
268 }
269 inputStream.flushCache();
270 }
271
272 return outputStream.toByteArray();
273 }
274
275 public static byte[] compressT6(final byte[] uncompressed, final int width, final int height) throws ImagingException {
276 try (ByteArrayInputStream bais = new ByteArrayInputStream(uncompressed);
277 BitInputStreamFlexible inputStream = new BitInputStreamFlexible(bais)) {
278 final BitArrayOutputStream outputStream = new BitArrayOutputStream();
279 int[] referenceLine = Allocator.intArray(width);
280 int[] codingLine = Allocator.intArray(width);
281 for (int y = 0; y < height; y++) {
282 for (int i = 0; i < width; i++) {
283 try {
284 codingLine[i] = inputStream.readBits(1);
285 } catch (final IOException e) {
286 throw new ImagingException("Error reading image to compress", e);
287 }
288 }
289 int codingA0Color = WHITE;
290 int referenceA0Color = WHITE;
291 int a1 = nextChangingElement(codingLine, codingA0Color, 0);
292 int b1 = nextChangingElement(referenceLine, referenceA0Color, 0);
293 int b2 = nextChangingElement(referenceLine, 1 - referenceA0Color, b1 + 1);
294 for (int a0 = 0; a0 < width;) {
295 if (b2 < a1) {
296 T4_T6_Tables.P.writeBits(outputStream);
297 a0 = b2;
298 } else {
299 a0 = compressT(a0, a1, b1, outputStream, codingA0Color, codingLine);
300 if (a0 == a1) {
301 codingA0Color = 1 - codingA0Color;
302 }
303 }
304 referenceA0Color = changingElementAt(referenceLine, a0);
305 a1 = nextChangingElement(codingLine, codingA0Color, a0 + 1);
306 if (codingA0Color == referenceA0Color) {
307 b1 = nextChangingElement(referenceLine, referenceA0Color, a0 + 1);
308 } else {
309 b1 = nextChangingElement(referenceLine, referenceA0Color, a0 + 1);
310 b1 = nextChangingElement(referenceLine, 1 - referenceA0Color, b1 + 1);
311 }
312 b2 = nextChangingElement(referenceLine, 1 - codingA0Color, b1 + 1);
313 }
314 final int[] swap = referenceLine;
315 referenceLine = codingLine;
316 codingLine = swap;
317 inputStream.flushCache();
318 }
319
320 T4_T6_Tables.EOL.writeBits(outputStream);
321 T4_T6_Tables.EOL.writeBits(outputStream);
322 return outputStream.toByteArray();
323 } catch (final IOException ioException) {
324 throw new ImagingException("I/O error", ioException);
325 }
326 }
327
328
329
330
331
332
333
334
335
336
337 public static byte[] decompressModifiedHuffman(final byte[] compressed, final int width, final int height) throws ImagingException {
338 try (ByteArrayInputStream baos = new ByteArrayInputStream(compressed);
339 BitInputStreamFlexible inputStream = new BitInputStreamFlexible(baos);
340 BitArrayOutputStream outputStream = new BitArrayOutputStream()) {
341 for (int y = 0; y < height; y++) {
342 int color = WHITE;
343 int rowLength;
344 for (rowLength = 0; rowLength < width;) {
345 final int runLength = readTotalRunLength(inputStream, color);
346 for (int i = 0; i < runLength; i++) {
347 outputStream.writeBit(color);
348 }
349 color = 1 - color;
350 rowLength += runLength;
351 }
352
353 if (rowLength == width) {
354 inputStream.flushCache();
355 outputStream.flush();
356 } else if (rowLength > width) {
357 throw new ImagingException("Unrecoverable row length error in image row " + y);
358 }
359 }
360 return outputStream.toByteArray();
361 } catch (final IOException ioException) {
362 throw new ImagingException("Error reading image to decompress", ioException);
363 }
364 }
365
366
367
368
369
370
371
372
373
374
375
376 public static byte[] decompressT4_1D(final byte[] compressed, final int width, final int height, final boolean hasFill) throws ImagingException {
377 final BitInputStreamFlexible inputStream = new BitInputStreamFlexible(new ByteArrayInputStream(compressed));
378 try (BitArrayOutputStream outputStream = new BitArrayOutputStream()) {
379 for (int y = 0; y < height; y++) {
380 int rowLength;
381 try {
382 final T4_T6_Tables.Entry entry = CONTROL_CODES.decode(inputStream);
383 if (!isEol(entry, hasFill)) {
384 throw new ImagingException("Expected EOL not found");
385 }
386 int color = WHITE;
387 for (rowLength = 0; rowLength < width;) {
388 final int runLength = readTotalRunLength(inputStream, color);
389 for (int i = 0; i < runLength; i++) {
390 outputStream.writeBit(color);
391 }
392 color = 1 - color;
393 rowLength += runLength;
394 }
395 } catch (final ImagingException huffmanException) {
396 throw new ImagingException("Decompression error", huffmanException);
397 }
398
399 if (rowLength == width) {
400 outputStream.flush();
401 } else if (rowLength > width) {
402 throw new ImagingException("Unrecoverable row length error in image row " + y);
403 }
404 }
405 return outputStream.toByteArray();
406 }
407 }
408
409
410
411
412
413
414
415
416
417
418
419
420 public static byte[] decompressT4_2D(final byte[] compressed, final int width, final int height, final boolean hasFill) throws ImagingException {
421 final BitInputStreamFlexible inputStream = new BitInputStreamFlexible(new ByteArrayInputStream(compressed));
422 try (BitArrayOutputStream outputStream = new BitArrayOutputStream()) {
423 final int[] referenceLine = Allocator.intArray(width);
424 for (int y = 0; y < height; y++) {
425 int rowLength = 0;
426 try {
427 T4_T6_Tables.Entry entry = CONTROL_CODES.decode(inputStream);
428 if (!isEol(entry, hasFill)) {
429 throw new ImagingException("Expected EOL not found");
430 }
431 final int tagBit = inputStream.readBits(1);
432 if (tagBit == 0) {
433
434 int codingA0Color = WHITE;
435 int referenceA0Color = WHITE;
436 int b1 = nextChangingElement(referenceLine, referenceA0Color, 0);
437 int b2 = nextChangingElement(referenceLine, 1 - referenceA0Color, b1 + 1);
438 for (int a0 = 0; a0 < width;) {
439 int a1;
440 int a2;
441 entry = CONTROL_CODES.decode(inputStream);
442 if (entry == T4_T6_Tables.P) {
443 fillRange(outputStream, referenceLine, a0, b2, codingA0Color);
444 a0 = b2;
445 } else if (entry == T4_T6_Tables.H) {
446 final int a0a1 = readTotalRunLength(inputStream, codingA0Color);
447 a1 = a0 + a0a1;
448 fillRange(outputStream, referenceLine, a0, a1, codingA0Color);
449 final int a1a2 = readTotalRunLength(inputStream, 1 - codingA0Color);
450 a2 = a1 + a1a2;
451 fillRange(outputStream, referenceLine, a1, a2, 1 - codingA0Color);
452 a0 = a2;
453 } else {
454 int a1b1;
455 if (entry == T4_T6_Tables.V0) {
456 a1b1 = 0;
457 } else if (entry == T4_T6_Tables.VL1) {
458 a1b1 = -1;
459 } else if (entry == T4_T6_Tables.VL2) {
460 a1b1 = -2;
461 } else if (entry == T4_T6_Tables.VL3) {
462 a1b1 = -3;
463 } else if (entry == T4_T6_Tables.VR1) {
464 a1b1 = 1;
465 } else if (entry == T4_T6_Tables.VR2) {
466 a1b1 = 2;
467 } else if (entry == T4_T6_Tables.VR3) {
468 a1b1 = 3;
469 } else {
470 throw new ImagingException("Invalid/unknown T.4 control code " + entry.bitString);
471 }
472 a1 = b1 + a1b1;
473 fillRange(outputStream, referenceLine, a0, a1, codingA0Color);
474 a0 = a1;
475 codingA0Color = 1 - codingA0Color;
476 }
477 referenceA0Color = changingElementAt(referenceLine, a0);
478 if (codingA0Color == referenceA0Color) {
479 b1 = nextChangingElement(referenceLine, referenceA0Color, a0 + 1);
480 } else {
481 b1 = nextChangingElement(referenceLine, referenceA0Color, a0 + 1);
482 b1 = nextChangingElement(referenceLine, 1 - referenceA0Color, b1 + 1);
483 }
484 b2 = nextChangingElement(referenceLine, 1 - codingA0Color, b1 + 1);
485 rowLength = a0;
486 }
487 } else {
488
489 int color = WHITE;
490 for (rowLength = 0; rowLength < width;) {
491 final int runLength = readTotalRunLength(inputStream, color);
492 for (int i = 0; i < runLength; i++) {
493 outputStream.writeBit(color);
494 referenceLine[rowLength + i] = color;
495 }
496 color = 1 - color;
497 rowLength += runLength;
498 }
499 }
500 } catch (final IOException e) {
501 throw new ImagingException("Decompression error", e);
502 }
503
504 if (rowLength == width) {
505 outputStream.flush();
506 } else if (rowLength > width) {
507 throw new ImagingException("Unrecoverable row length error in image row " + y);
508 }
509 }
510
511 return outputStream.toByteArray();
512 }
513 }
514
515
516
517
518
519
520
521
522
523
524
525 public static byte[] decompressT6(final byte[] compressed, final int width, final int height) throws ImagingException {
526 try (BitInputStreamFlexible inputStream = new BitInputStreamFlexible(new ByteArrayInputStream(compressed));
527 BitArrayOutputStream outputStream = new BitArrayOutputStream()) {
528 final int[] referenceLine = Allocator.intArray(width);
529 for (int y = 0; y < height; y++) {
530 int rowLength = 0;
531 int codingA0Color = WHITE;
532 int referenceA0Color = WHITE;
533 int b1 = nextChangingElement(referenceLine, referenceA0Color, 0);
534 int b2 = nextChangingElement(referenceLine, 1 - referenceA0Color, b1 + 1);
535 for (int a0 = 0; a0 < width;) {
536 int a1;
537 int a2;
538 final T4_T6_Tables.Entry entry = CONTROL_CODES.decode(inputStream);
539 if (entry == T4_T6_Tables.P) {
540 fillRange(outputStream, referenceLine, a0, b2, codingA0Color);
541 a0 = b2;
542 } else if (entry == T4_T6_Tables.H) {
543 final int a0a1 = readTotalRunLength(inputStream, codingA0Color);
544 a1 = a0 + a0a1;
545 fillRange(outputStream, referenceLine, a0, a1, codingA0Color);
546 final int a1a2 = readTotalRunLength(inputStream, 1 - codingA0Color);
547 a2 = a1 + a1a2;
548 fillRange(outputStream, referenceLine, a1, a2, 1 - codingA0Color);
549 a0 = a2;
550 } else {
551 int a1b1;
552 if (entry == T4_T6_Tables.V0) {
553 a1b1 = 0;
554 } else if (entry == T4_T6_Tables.VL1) {
555 a1b1 = -1;
556 } else if (entry == T4_T6_Tables.VL2) {
557 a1b1 = -2;
558 } else if (entry == T4_T6_Tables.VL3) {
559 a1b1 = -3;
560 } else if (entry == T4_T6_Tables.VR1) {
561 a1b1 = 1;
562 } else if (entry == T4_T6_Tables.VR2) {
563 a1b1 = 2;
564 } else if (entry == T4_T6_Tables.VR3) {
565 a1b1 = 3;
566 } else {
567 throw new ImagingException("Invalid/unknown T.6 control code " + entry.bitString);
568 }
569 a1 = b1 + a1b1;
570 fillRange(outputStream, referenceLine, a0, a1, codingA0Color);
571 a0 = a1;
572 codingA0Color = 1 - codingA0Color;
573 }
574 referenceA0Color = changingElementAt(referenceLine, a0);
575 if (codingA0Color == referenceA0Color) {
576 b1 = nextChangingElement(referenceLine, referenceA0Color, a0 + 1);
577 } else {
578 b1 = nextChangingElement(referenceLine, referenceA0Color, a0 + 1);
579 b1 = nextChangingElement(referenceLine, 1 - referenceA0Color, b1 + 1);
580 }
581 b2 = nextChangingElement(referenceLine, 1 - codingA0Color, b1 + 1);
582 rowLength = a0;
583 }
584 if (rowLength == width) {
585 outputStream.flush();
586 } else if (rowLength > width) {
587 throw new ImagingException("Unrecoverable row length error in image row " + y);
588 }
589 }
590 return outputStream.toByteArray();
591 } catch (final IOException e) {
592 if (e instanceof ImagingException) {
593 throw (ImagingException) e;
594 }
595
596 throw new ImagingException("Closing stream", e);
597 }
598 }
599
600 private static void fillRange(final BitArrayOutputStream outputStream, final int[] referenceRow, final int a0, final int end, final int color) {
601 for (int i = a0; i < end; i++) {
602 referenceRow[i] = color;
603 outputStream.writeBit(color);
604 }
605 }
606
607 private static boolean isEol(final T4_T6_Tables.Entry entry, final boolean hasFill) {
608 if (entry == T4_T6_Tables.EOL) {
609 return true;
610 }
611 if (hasFill) {
612 return entry == T4_T6_Tables.EOL13 || entry == T4_T6_Tables.EOL14 || entry == T4_T6_Tables.EOL15 || entry == T4_T6_Tables.EOL16
613 || entry == T4_T6_Tables.EOL17 || entry == T4_T6_Tables.EOL18 || entry == T4_T6_Tables.EOL19;
614 }
615 return false;
616 }
617
618 private static T4_T6_Tables.Entry lowerBound(final T4_T6_Tables.Entry[] entries, final int value) {
619 int first = 0;
620 int last = entries.length - 1;
621 do {
622 final int middle = first + last >>> 1;
623 if (entries[middle].value <= value && (middle + 1 >= entries.length || value < entries[middle + 1].value)) {
624 return entries[middle];
625 }
626 if (entries[middle].value > value) {
627 last = middle - 1;
628 } else {
629 first = middle + 1;
630 }
631 } while (first < last);
632
633 return entries[first];
634 }
635
636 private static int nextChangingElement(final int[] line, final int currentColour, final int start) {
637 int position;
638 for (position = start; position < line.length && line[position] == currentColour; position++) {
639
640 }
641
642 return Math.min(position, line.length);
643 }
644
645 private static int readTotalRunLength(final BitInputStreamFlexible bitStream, final int color) throws ImagingException {
646 int totalLength = 0;
647 Integer runLength;
648 do {
649 if (color == WHITE) {
650 runLength = WHITE_RUN_LENGTHS.decode(bitStream);
651 } else {
652 runLength = BLACK_RUN_LENGTHS.decode(bitStream);
653 }
654 totalLength += runLength;
655 } while (runLength > 63);
656 return totalLength;
657 }
658
659 private static void writeRunLength(final BitArrayOutputStream bitStream, int runLength, final int color) {
660 final T4_T6_Tables.Entry[] makeUpCodes;
661 final T4_T6_Tables.Entry[] terminatingCodes;
662 if (color == WHITE) {
663 makeUpCodes = T4_T6_Tables.WHITE_MAKE_UP_CODES;
664 terminatingCodes = T4_T6_Tables.WHITE_TERMINATING_CODES;
665 } else {
666 makeUpCodes = T4_T6_Tables.BLACK_MAKE_UP_CODES;
667 terminatingCodes = T4_T6_Tables.BLACK_TERMINATING_CODES;
668 }
669 while (runLength >= 1792) {
670 final T4_T6_Tables.Entry entry = lowerBound(T4_T6_Tables.ADDITIONAL_MAKE_UP_CODES, runLength);
671 entry.writeBits(bitStream);
672 runLength -= entry.value;
673 }
674 while (runLength >= 64) {
675 final T4_T6_Tables.Entry entry = lowerBound(makeUpCodes, runLength);
676 entry.writeBits(bitStream);
677 runLength -= entry.value;
678 }
679 final T4_T6_Tables.Entry terminatingEntry = terminatingCodes[runLength];
680 terminatingEntry.writeBits(bitStream);
681 }
682
683 private T4AndT6Compression() {
684 }
685 }