2 * CCITT Fax Group 3 and 4 decompression
3 * Copyright (c) 2008 Konstantin Shishkov
5 * This file is part of FFmpeg.
7 * FFmpeg is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation; either
10 * version 2.1 of the License, or (at your option) any later version.
12 * FFmpeg is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with FFmpeg; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
24 * CCITT Fax Group 3 and 4 decompression
25 * @author Konstantin Shishkov
27 #include "libavutil/thread.h"
33 #define CCITT_SYMS 104
35 static const uint16_t ccitt_syms[CCITT_SYMS] = {
36 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,
37 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
38 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38,
39 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51,
40 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64,
41 128, 192, 256, 320, 384, 448, 512, 576, 640, 704, 768, 832, 896,
42 960, 1024, 1088, 1152, 1216, 1280, 1344, 1408, 1472, 1536, 1600, 1664, 1728,
43 1792, 1856, 1920, 1984, 2048, 2112, 2176, 2240, 2304, 2368, 2432, 2496, 2560
46 static const uint8_t ccitt_codes_bits[2][CCITT_SYMS] =
49 0x35, 0x07, 0x07, 0x08, 0x0B, 0x0C, 0x0E, 0x0F, 0x13, 0x14, 0x07, 0x08, 0x08,
50 0x03, 0x34, 0x35, 0x2A, 0x2B, 0x27, 0x0C, 0x08, 0x17, 0x03, 0x04, 0x28, 0x2B,
51 0x13, 0x24, 0x18, 0x02, 0x03, 0x1A, 0x1B, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
52 0x28, 0x29, 0x2A, 0x2B, 0x2C, 0x2D, 0x04, 0x05, 0x0A, 0x0B, 0x52, 0x53, 0x54,
53 0x55, 0x24, 0x25, 0x58, 0x59, 0x5A, 0x5B, 0x4A, 0x4B, 0x32, 0x33, 0x34, 0x1B,
54 0x12, 0x17, 0x37, 0x36, 0x37, 0x64, 0x65, 0x68, 0x67, 0xCC, 0xCD, 0xD2, 0xD3,
55 0xD4, 0xD5, 0xD6, 0xD7, 0xD8, 0xD9, 0xDA, 0xDB, 0x98, 0x99, 0x9A, 0x18, 0x9B,
56 0x08, 0x0C, 0x0D, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x1C, 0x1D, 0x1E, 0x1F
59 0x37, 0x02, 0x03, 0x02, 0x03, 0x03, 0x02, 0x03, 0x05, 0x04, 0x04, 0x05, 0x07,
60 0x04, 0x07, 0x18, 0x17, 0x18, 0x08, 0x67, 0x68, 0x6C, 0x37, 0x28, 0x17, 0x18,
61 0xCA, 0xCB, 0xCC, 0xCD, 0x68, 0x69, 0x6A, 0x6B, 0xD2, 0xD3, 0xD4, 0xD5, 0xD6,
62 0xD7, 0x6C, 0x6D, 0xDA, 0xDB, 0x54, 0x55, 0x56, 0x57, 0x64, 0x65, 0x52, 0x53,
63 0x24, 0x37, 0x38, 0x27, 0x28, 0x58, 0x59, 0x2B, 0x2C, 0x5A, 0x66, 0x67, 0x0F,
64 0xC8, 0xC9, 0x5B, 0x33, 0x34, 0x35, 0x6C, 0x6D, 0x4A, 0x4B, 0x4C, 0x4D, 0x72,
65 0x73, 0x74, 0x75, 0x76, 0x77, 0x52, 0x53, 0x54, 0x55, 0x5A, 0x5B, 0x64, 0x65,
66 0x08, 0x0C, 0x0D, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x1C, 0x1D, 0x1E, 0x1F
70 static const uint8_t ccitt_codes_lens[2][CCITT_SYMS] =
73 8, 6, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 7,
74 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
75 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
76 8, 8, 8, 8, 5, 5, 6, 7, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9,
77 9, 9, 9, 9, 9, 9, 9, 9, 9, 6, 9, 11, 11, 11, 12, 12, 12, 12, 12, 12,
81 10, 3, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 7, 8, 8, 9, 10, 10, 10, 11,
82 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
83 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
84 12, 12, 12, 12, 10, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13,
85 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 11, 11, 11, 12, 12, 12, 12, 12, 12,
90 static const uint8_t ccitt_group3_2d_bits[11] = {
91 1, 1, 2, 2, 2, 1, 3, 3, 3, 1, 1
94 static const uint8_t ccitt_group3_2d_lens[11] = {
95 4, 3, 7, 6, 3, 1, 3, 6, 7, 7, 9
98 static VLC ccitt_vlc[2], ccitt_group3_2d_vlc;
100 static av_cold void ccitt_unpack_init(void)
102 static VLC_TYPE code_table1[528][2];
103 static VLC_TYPE code_table2[648][2];
106 ccitt_vlc[0].table = code_table1;
107 ccitt_vlc[0].table_allocated = 528;
108 ccitt_vlc[1].table = code_table2;
109 ccitt_vlc[1].table_allocated = 648;
110 for (i = 0; i < 2; i++) {
111 ff_init_vlc_sparse(&ccitt_vlc[i], 9, CCITT_SYMS,
112 ccitt_codes_lens[i], 1, 1,
113 ccitt_codes_bits[i], 1, 1,
115 INIT_VLC_USE_NEW_STATIC);
117 INIT_VLC_STATIC(&ccitt_group3_2d_vlc, 9, 11,
118 ccitt_group3_2d_lens, 1, 1,
119 ccitt_group3_2d_bits, 1, 1, 512);
122 av_cold void ff_ccitt_unpack_init(void)
124 static AVOnce init_static_once = AV_ONCE_INIT;
125 ff_thread_once(&init_static_once, ccitt_unpack_init);
128 static int decode_uncompressed(AVCodecContext *avctx, GetBitContext *gb,
129 unsigned int *pix_left, int **runs,
130 const int *runend, int *mode)
141 cwi = show_bits(gb, 11);
143 av_log(avctx, AV_LOG_ERROR, "Invalid uncompressed codeword\n");
144 return AVERROR_INVALIDDATA;
146 cwi = 10 - av_log2(cwi);
147 skip_bits(gb, cwi + 1);
149 newmode = get_bits1(gb);
159 for (k = 0; k < 2; k++) {
162 *(*runs)++ = saved_run;
163 if (*runs >= runend) {
164 av_log(avctx, AV_LOG_ERROR, "uncompressed run overrun\n");
165 return AVERROR_INVALIDDATA;
167 if (*pix_left <= saved_run) {
168 av_log(avctx, AV_LOG_ERROR, "uncompressed run went out of bounds\n");
169 return AVERROR_INVALIDDATA;
171 *pix_left -= saved_run;
175 saved_run += codes[k];
179 *(*runs)++ = saved_run;
180 if (*runs >= runend) {
181 av_log(avctx, AV_LOG_ERROR, "uncompressed run overrun\n");
182 return AVERROR_INVALIDDATA;
184 if (*pix_left <= saved_run) {
185 if (*pix_left == saved_run)
187 av_log(avctx, AV_LOG_ERROR, "uncompressed run went out of boundsE\n");
188 return AVERROR_INVALIDDATA;
190 *pix_left -= saved_run;
193 if (newmode != *mode) { //FIXME CHECK
195 if (*runs >= runend) {
196 av_log(avctx, AV_LOG_ERROR, "uncompressed run overrun\n");
197 return AVERROR_INVALIDDATA;
204 static int decode_group3_1d_line(AVCodecContext *avctx, GetBitContext *gb,
205 unsigned int pix_left, int *runs,
209 unsigned int run = 0;
212 t = get_vlc2(gb, ccitt_vlc[mode].table, 9, 2);
216 if (runs >= runend) {
217 av_log(avctx, AV_LOG_ERROR, "Run overrun\n");
218 return AVERROR_INVALIDDATA;
220 if (pix_left <= run) {
223 av_log(avctx, AV_LOG_ERROR, "Run went out of bounds\n");
224 return AVERROR_INVALIDDATA;
229 } else if ((int)t == -1) {
230 if (show_bits(gb, 12) == 15) {
233 ret = decode_uncompressed(avctx, gb, &pix_left, &runs, runend, &mode);
239 av_log(avctx, AV_LOG_ERROR, "Incorrect code\n");
240 return AVERROR_INVALIDDATA;
248 static int decode_group3_2d_line(AVCodecContext *avctx, GetBitContext *gb,
249 unsigned int width, int *runs,
250 const int *runend, const int *ref)
252 int mode = 0, saved_run = 0, t;
253 int run_off = *ref++;
254 unsigned int offs = 0, run = 0;
256 while (offs < width) {
257 int cmode = get_vlc2(gb, ccitt_group3_2d_vlc.table, 9, 1);
259 av_log(avctx, AV_LOG_ERROR, "Incorrect mode VLC\n");
260 return AVERROR_INVALIDDATA;
262 if (!cmode) { //pass mode
265 run = run_off - offs;
270 av_log(avctx, AV_LOG_ERROR, "Run went out of bounds\n");
271 return AVERROR_INVALIDDATA;
274 } else if (cmode == 1) { //horizontal mode
276 for (k = 0; k < 2; k++) {
279 t = get_vlc2(gb, ccitt_vlc[mode].table, 9, 2);
281 av_log(avctx, AV_LOG_ERROR, "Incorrect code\n");
282 return AVERROR_INVALIDDATA;
288 *runs++ = run + saved_run;
289 if (runs >= runend) {
290 av_log(avctx, AV_LOG_ERROR, "Run overrun\n");
291 return AVERROR_INVALIDDATA;
295 if (offs > width || run > width) {
296 av_log(avctx, AV_LOG_ERROR, "Run went out of bounds\n");
297 return AVERROR_INVALIDDATA;
301 } else if (cmode == 9 || cmode == 10) {
302 int xxx = get_bits(gb, 3);
303 if (cmode == 9 && xxx == 7) {
305 int pix_left = width - offs;
308 av_log(avctx, AV_LOG_ERROR, "saved run %d on entering uncompressed mode\n", saved_run);
309 return AVERROR_INVALIDDATA;
311 ret = decode_uncompressed(avctx, gb, &pix_left, &runs, runend, &mode);
312 offs = width - pix_left;
318 avpriv_report_missing_feature(avctx, "Special mode %d xxx=%d support", cmode, xxx);
319 return AVERROR_PATCHWELCOME;
321 } else { //vertical mode
322 run = run_off - offs + (cmode - 5);
325 if (offs > width || run > width) {
326 av_log(avctx, AV_LOG_ERROR, "Run went out of bounds\n");
327 return AVERROR_INVALIDDATA;
329 *runs++ = run + saved_run;
330 if (runs >= runend) {
331 av_log(avctx, AV_LOG_ERROR, "Run overrun\n");
332 return AVERROR_INVALIDDATA;
338 while (offs < width && run_off <= offs) {
345 if (runs >= runend) {
346 av_log(avctx, AV_LOG_ERROR, "Run overrun\n");
354 static void put_line(uint8_t *dst, int size, int width, const int *runs)
357 int run, mode = ~0, pix_left = width, run_idx = 0;
359 init_put_bits(&pb, dst, size);
360 while (pix_left > 0) {
361 run = runs[run_idx++];
364 for (; run > 16; run -= 16)
365 put_sbits(&pb, 16, mode);
367 put_sbits(&pb, run, mode);
372 static int find_group3_syncmarker(GetBitContext *gb, int srcsize)
374 unsigned int state = -1;
375 srcsize -= get_bits_count(gb);
376 while (srcsize-- > 0) {
377 state += state + get_bits1(gb);
378 if ((state & 0xFFF) == 1)
384 int ff_ccitt_unpack(AVCodecContext *avctx, const uint8_t *src, int srcsize,
385 uint8_t *dst, int height, int stride,
386 enum TiffCompr compr, int opts)
390 int *runs, *ref = NULL, *runend;
392 int runsize = avctx->width + 2;
395 runs = av_malloc_array(runsize, sizeof(runs[0]));
396 ref = av_malloc_array(runsize, sizeof(ref[0]));
398 ret = AVERROR(ENOMEM);
401 ref[0] = avctx->width;
404 if ((ret = init_get_bits8(&gb, src, srcsize)) < 0)
406 has_eol = show_bits(&gb, 12) == 1 || show_bits(&gb, 16) == 1;
408 for (j = 0; j < height; j++) {
409 runend = runs + runsize;
410 if (compr == TIFF_G4) {
411 ret = decode_group3_2d_line(avctx, &gb, avctx->width, runs, runend,
416 int g3d1 = (compr == TIFF_G3) && !(opts & 1);
417 if (compr != TIFF_CCITT_RLE &&
419 find_group3_syncmarker(&gb, srcsize * 8) < 0)
421 if (compr == TIFF_CCITT_RLE || g3d1 || get_bits1(&gb))
422 ret = decode_group3_1d_line(avctx, &gb, avctx->width, runs,
425 ret = decode_group3_2d_line(avctx, &gb, avctx->width, runs,
427 if (compr == TIFF_CCITT_RLE)
430 if (avctx->err_recognition & AV_EF_EXPLODE && ret < 0)
434 put_line(dst, stride, avctx->width, ref);
436 put_line(dst, stride, avctx->width, runs);
437 FFSWAP(int *, runs, ref);