faxcompr.c 15.1 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
/*
 * CCITT Fax Group 3 and 4 decompression
 * Copyright (c) 2008 Konstantin Shishkov
 *
 * This file is part of FFmpeg.
 *
 * FFmpeg is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * FFmpeg is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with FFmpeg; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 */

/**
23
 * @file
24
 * CCITT Fax Group 3 and 4 decompression
25 26 27
 * @author Konstantin Shishkov
 */
#include "avcodec.h"
28
#include "get_bits.h"
29
#include "put_bits.h"
30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98
#include "faxcompr.h"

#define CCITT_SYMS 104

static const uint16_t ccitt_syms[CCITT_SYMS] = {
    0,    1,    2,    3,    4,    5,    6,    7,    8,    9,   10,   11,   12,
   13,   14,   15,   16,   17,   18,   19,   20,   21,   22,   23,   24,   25,
   26,   27,   28,   29,   30,   31,   32,   33,   34,   35,   36,   37,   38,
   39,   40,   41,   42,   43,   44,   45,   46,   47,   48,   49,   50,   51,
   52,   53,   54,   55,   56,   57,   58,   59,   60,   61,   62,   63,   64,
  128,  192,  256,  320,  384,  448,  512,  576,  640,  704,  768,  832,  896,
  960, 1024, 1088, 1152, 1216, 1280, 1344, 1408, 1472, 1536, 1600, 1664, 1728,
 1792, 1856, 1920, 1984, 2048, 2112, 2176, 2240, 2304, 2368, 2432, 2496, 2560
};

static const uint8_t ccitt_codes_bits[2][CCITT_SYMS] =
{
  {
    0x35, 0x07, 0x07, 0x08, 0x0B, 0x0C, 0x0E, 0x0F, 0x13, 0x14, 0x07, 0x08, 0x08,
    0x03, 0x34, 0x35, 0x2A, 0x2B, 0x27, 0x0C, 0x08, 0x17, 0x03, 0x04, 0x28, 0x2B,
    0x13, 0x24, 0x18, 0x02, 0x03, 0x1A, 0x1B, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
    0x28, 0x29, 0x2A, 0x2B, 0x2C, 0x2D, 0x04, 0x05, 0x0A, 0x0B, 0x52, 0x53, 0x54,
    0x55, 0x24, 0x25, 0x58, 0x59, 0x5A, 0x5B, 0x4A, 0x4B, 0x32, 0x33, 0x34, 0x1B,
    0x12, 0x17, 0x37, 0x36, 0x37, 0x64, 0x65, 0x68, 0x67, 0xCC, 0xCD, 0xD2, 0xD3,
    0xD4, 0xD5, 0xD6, 0xD7, 0xD8, 0xD9, 0xDA, 0xDB, 0x98, 0x99, 0x9A, 0x18, 0x9B,
    0x08, 0x0C, 0x0D, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x1C, 0x1D, 0x1E, 0x1F
  },
  {
    0x37, 0x02, 0x03, 0x02, 0x03, 0x03, 0x02, 0x03, 0x05, 0x04, 0x04, 0x05, 0x07,
    0x04, 0x07, 0x18, 0x17, 0x18, 0x08, 0x67, 0x68, 0x6C, 0x37, 0x28, 0x17, 0x18,
    0xCA, 0xCB, 0xCC, 0xCD, 0x68, 0x69, 0x6A, 0x6B, 0xD2, 0xD3, 0xD4, 0xD5, 0xD6,
    0xD7, 0x6C, 0x6D, 0xDA, 0xDB, 0x54, 0x55, 0x56, 0x57, 0x64, 0x65, 0x52, 0x53,
    0x24, 0x37, 0x38, 0x27, 0x28, 0x58, 0x59, 0x2B, 0x2C, 0x5A, 0x66, 0x67, 0x0F,
    0xC8, 0xC9, 0x5B, 0x33, 0x34, 0x35, 0x6C, 0x6D, 0x4A, 0x4B, 0x4C, 0x4D, 0x72,
    0x73, 0x74, 0x75, 0x76, 0x77, 0x52, 0x53, 0x54, 0x55, 0x5A, 0x5B, 0x64, 0x65,
    0x08, 0x0C, 0x0D, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x1C, 0x1D, 0x1E, 0x1F
  }
};

static const uint8_t ccitt_codes_lens[2][CCITT_SYMS] =
{
  {
     8,  6,  4,  4,  4,  4,  4,  4,  5,  5,  5,  5,  6,  6,  6,  6,  6,  6,  7,  7,
     7,  7,  7,  7,  7,  7,  7,  7,  7,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,
     8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,
     8,  8,  8,  8,  5,  5,  6,  7,  8,  8,  8,  8,  8,  8,  9,  9,  9,  9,  9,  9,
     9,  9,  9,  9,  9,  9,  9,  9,  9,  6,  9, 11, 11, 11, 12, 12, 12, 12, 12, 12,
    12, 12, 12, 12
  },
  {
    10,  3,  2,  2,  3,  4,  4,  5,  6,  6,  7,  7,  7,  8,  8,  9, 10, 10, 10, 11,
    11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
    12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
    12, 12, 12, 12, 10, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13,
    13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 11, 11, 11, 12, 12, 12, 12, 12, 12,
    12, 12, 12, 12
  }
};

static const uint8_t ccitt_group3_2d_bits[11] = {
    1, 1, 2, 2, 2, 1, 3, 3, 3, 1, 1
};

static const uint8_t ccitt_group3_2d_lens[11] = {
    4, 3, 7, 6, 3, 1, 3, 6, 7, 7, 9
};

static VLC ccitt_vlc[2], ccitt_group3_2d_vlc;

99
av_cold void ff_ccitt_unpack_init(void)
100 101 102 103 104 105
{
    static VLC_TYPE code_table1[528][2];
    static VLC_TYPE code_table2[648][2];
    int i;
    static int initialized = 0;

106
    if (initialized)
107 108 109 110 111
        return;
    ccitt_vlc[0].table = code_table1;
    ccitt_vlc[0].table_allocated = 528;
    ccitt_vlc[1].table = code_table2;
    ccitt_vlc[1].table_allocated = 648;
112
    for (i = 0; i < 2; i++) {
113 114 115 116 117
        ff_init_vlc_sparse(&ccitt_vlc[i], 9, CCITT_SYMS,
                           ccitt_codes_lens[i], 1, 1,
                           ccitt_codes_bits[i], 1, 1,
                           ccitt_syms, 2, 2,
                           INIT_VLC_USE_NEW_STATIC);
118 119 120 121 122 123 124
    }
    INIT_VLC_STATIC(&ccitt_group3_2d_vlc, 9, 11,
                    ccitt_group3_2d_lens, 1, 1,
                    ccitt_group3_2d_bits, 1, 1, 512);
    initialized = 1;
}

125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157
static int decode_uncompressed(AVCodecContext *avctx, GetBitContext *gb,
                               unsigned int *pix_left, int **runs,
                               const int *runend, int *mode)
{
    int eob = 0;
    int newmode;
    int saved_run = 0;

    do {
        int cwi, k;
        int cw = 0;
        int codes[2];
        do {
            cwi = show_bits(gb, 11);
            if (!cwi) {
                av_log(avctx, AV_LOG_ERROR, "Invalid uncompressed codeword\n");
                return AVERROR_INVALIDDATA;
            }
            cwi = 10 - av_log2(cwi);
            skip_bits(gb, cwi + 1);
            if (cwi > 5) {
                newmode = get_bits1(gb);
                eob = 1;
                cwi -= 6;
            }
            cw += cwi;
        } while(cwi == 5);

        codes[0] = cw;
        codes[1] = !eob;

        for (k = 0; k < 2; k++) {
            if (codes[k]) {
158
                if (*mode == !k) {
159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191
                    *(*runs)++ = saved_run;
                    if (*runs >= runend) {
                        av_log(avctx, AV_LOG_ERROR, "uncompressed run overrun\n");
                        return AVERROR_INVALIDDATA;
                    }
                    if (*pix_left <= saved_run) {
                        av_log(avctx, AV_LOG_ERROR, "uncompressed run went out of bounds\n");
                        return AVERROR_INVALIDDATA;
                    }
                    *pix_left -= saved_run;
                    saved_run = 0;
                    *mode = !*mode;
                }
                saved_run += codes[k];
            }
        }
    } while (!eob);
    *(*runs)++ = saved_run;
    if (*runs >= runend) {
        av_log(avctx, AV_LOG_ERROR, "uncompressed run overrun\n");
        return AVERROR_INVALIDDATA;
    }
    if (*pix_left <= saved_run) {
        if (*pix_left == saved_run)
            return 1;
        av_log(avctx, AV_LOG_ERROR, "uncompressed run went out of boundsE\n");
        return AVERROR_INVALIDDATA;
    }
    *pix_left -= saved_run;
    saved_run = 0;
    *mode = !*mode;
    if (newmode != *mode) { //FIXME CHECK
        *(*runs)++ = 0;
192 193 194 195
        if (*runs >= runend) {
            av_log(avctx, AV_LOG_ERROR, "uncompressed run overrun\n");
            return AVERROR_INVALIDDATA;
        }
196 197 198 199
        *mode = newmode;
    }
    return 0;
}
200 201

static int decode_group3_1d_line(AVCodecContext *avctx, GetBitContext *gb,
202 203
                                 unsigned int pix_left, int *runs,
                                 const int *runend)
204
{
205 206
    int mode         = 0;
    unsigned int run = 0;
207
    unsigned int t;
208 209
    for (;;) {
        t    = get_vlc2(gb, ccitt_vlc[mode].table, 9, 2);
210
        run += t;
211
        if (t < 64) {
212
            *runs++ = run;
213
            if (runs >= runend) {
214
                av_log(avctx, AV_LOG_ERROR, "Run overrun\n");
215
                return AVERROR_INVALIDDATA;
216
            }
217 218
            if (pix_left <= run) {
                if (pix_left == run)
219 220
                    break;
                av_log(avctx, AV_LOG_ERROR, "Run went out of bounds\n");
221
                return AVERROR_INVALIDDATA;
222
            }
223
            pix_left -= run;
224 225 226
            run       = 0;
            mode      = !mode;
        } else if ((int)t == -1) {
227
            if (show_bits(gb, 12) == 15) {
228
                int ret;
229
                skip_bits(gb, 12);
230 231 232 233 234
                ret = decode_uncompressed(avctx, gb, &pix_left, &runs, runend, &mode);
                if (ret < 0) {
                    return ret;
                } else if (ret)
                    break;
235 236 237 238
            } else {
                av_log(avctx, AV_LOG_ERROR, "Incorrect code\n");
                return AVERROR_INVALIDDATA;
            }
239 240 241 242 243 244 245
        }
    }
    *runs++ = 0;
    return 0;
}

static int decode_group3_2d_line(AVCodecContext *avctx, GetBitContext *gb,
246 247
                                 unsigned int width, int *runs,
                                 const int *runend, const int *ref)
248
{
249 250 251
    int mode          = 0, saved_run = 0, t;
    int run_off       = *ref++;
    unsigned int offs = 0, run = 0;
252

253
    while (offs < width) {
254
        int cmode = get_vlc2(gb, ccitt_group3_2d_vlc.table, 9, 1);
255
        if (cmode == -1) {
256
            av_log(avctx, AV_LOG_ERROR, "Incorrect mode VLC\n");
257
            return AVERROR_INVALIDDATA;
258
        }
259
        if (!cmode) { //pass mode
260
            if (run_off < width)
261
                run_off += *ref++;
262 263
            run      = run_off - offs;
            offs     = run_off;
264
            if (run_off < width)
265
                run_off += *ref++;
266
            if (offs > width) {
267
                av_log(avctx, AV_LOG_ERROR, "Run went out of bounds\n");
268
                return AVERROR_INVALIDDATA;
269 270
            }
            saved_run += run;
271
        } else if (cmode == 1) { //horizontal mode
272
            int k;
273
            for (k = 0; k < 2; k++) {
274
                run = 0;
275
                for (;;) {
276
                    t = get_vlc2(gb, ccitt_vlc[mode].table, 9, 2);
277
                    if (t == -1) {
278
                        av_log(avctx, AV_LOG_ERROR, "Incorrect code\n");
279
                        return AVERROR_INVALIDDATA;
280 281
                    }
                    run += t;
282
                    if (t < 64)
283 284 285
                        break;
                }
                *runs++ = run + saved_run;
286
                if (runs >= runend) {
287
                    av_log(avctx, AV_LOG_ERROR, "Run overrun\n");
288
                    return AVERROR_INVALIDDATA;
289
                }
290
                saved_run = 0;
291 292
                offs     += run;
                if (offs > width || run > width) {
293
                    av_log(avctx, AV_LOG_ERROR, "Run went out of bounds\n");
294
                    return AVERROR_INVALIDDATA;
295 296 297
                }
                mode = !mode;
            }
298
        } else if (cmode == 9 || cmode == 10) {
299
            int xxx = get_bits(gb, 3);
300
            if (cmode == 9 && xxx == 7) {
301 302
                int ret;
                int pix_left = width - offs;
303 304 305 306 307

                if (saved_run) {
                    av_log(avctx, AV_LOG_ERROR, "saved run %d on entering uncompressed mode\n", saved_run);
                    return AVERROR_INVALIDDATA;
                }
308 309 310 311 312 313
                ret = decode_uncompressed(avctx, gb, &pix_left, &runs, runend, &mode);
                offs = width - pix_left;
                if (ret < 0) {
                    return ret;
                } else if (ret)
                    break;
314 315 316 317
            } else {
                avpriv_report_missing_feature(avctx, "Special mode %d xxx=%d support", cmode, xxx);
                return AVERROR_PATCHWELCOME;
            }
318 319
        } else { //vertical mode
            run      = run_off - offs + (cmode - 5);
Michael Niedermayer's avatar
Michael Niedermayer committed
320
            run_off -= *--ref;
321 322
            offs    += run;
            if (offs > width || run > width) {
323
                av_log(avctx, AV_LOG_ERROR, "Run went out of bounds\n");
324
                return AVERROR_INVALIDDATA;
325 326
            }
            *runs++ = run + saved_run;
327
            if (runs >= runend) {
328
                av_log(avctx, AV_LOG_ERROR, "Run overrun\n");
329
                return AVERROR_INVALIDDATA;
330
            }
331
            saved_run = 0;
332
            mode      = !mode;
333
        }
334
        //sync line pointers
335
        while (offs < width && run_off <= offs) {
336 337 338
            run_off += *ref++;
            run_off += *ref++;
        }
339 340
    }
    *runs++ = saved_run;
341
    if (saved_run) {
342
        if (runs >= runend) {
343 344 345 346 347
            av_log(avctx, AV_LOG_ERROR, "Run overrun\n");
            return -1;
        }
        *runs++ = 0;
    }
348 349 350 351 352 353
    return 0;
}

static void put_line(uint8_t *dst, int size, int width, const int *runs)
{
    PutBitContext pb;
354
    int run, mode = ~0, pix_left = width, run_idx = 0;
355

356
    init_put_bits(&pb, dst, size);
357 358 359
    while (pix_left > 0) {
        run       = runs[run_idx++];
        mode      = ~mode;
360
        pix_left -= run;
361
        for (; run > 16; run -= 16)
362
            put_sbits(&pb, 16, mode);
363
        if (run)
Michael Niedermayer's avatar
Michael Niedermayer committed
364
            put_sbits(&pb, run, mode);
365
    }
366
    flush_put_bits(&pb);
367 368 369 370
}

static int find_group3_syncmarker(GetBitContext *gb, int srcsize)
{
371 372
    unsigned int state = -1;
    srcsize -= get_bits_count(gb);
373 374 375
    while (srcsize-- > 0) {
        state += state + get_bits1(gb);
        if ((state & 0xFFF) == 1)
376
            return 0;
377
    }
378
    return -1;
379 380
}

381
int ff_ccitt_unpack(AVCodecContext *avctx, const uint8_t *src, int srcsize,
382 383
                    uint8_t *dst, int height, int stride,
                    enum TiffCompr compr, int opts)
384 385 386
{
    int j;
    GetBitContext gb;
387
    int *runs, *ref = NULL, *runend;
388
    int ret;
389
    int runsize = avctx->width + 2;
390
    int has_eol;
391

392 393
    runs = av_malloc_array(runsize, sizeof(runs[0]));
    ref  = av_malloc_array(runsize, sizeof(ref[0]));
394
    if (!runs || !ref) {
395
        ret = AVERROR(ENOMEM);
396 397
        goto fail;
    }
398 399 400
    ref[0] = avctx->width;
    ref[1] = 0;
    ref[2] = 0;
401
    if ((ret = init_get_bits8(&gb, src, srcsize)) < 0)
402
        goto fail;
403 404
    has_eol = show_bits(&gb, 12) == 1 || show_bits(&gb, 16) == 1;

405
    for (j = 0; j < height; j++) {
406
        runend = runs + runsize;
407 408 409
        if (compr == TIFF_G4) {
            ret = decode_group3_2d_line(avctx, &gb, avctx->width, runs, runend,
                                        ref);
410
            if (ret < 0)
411
                goto fail;
412
        } else {
413
            int g3d1 = (compr == TIFF_G3) && !(opts & 1);
414
            if (compr != TIFF_CCITT_RLE &&
415
                has_eol &&
416
                find_group3_syncmarker(&gb, srcsize * 8) < 0)
417
                break;
418 419 420
            if (compr == TIFF_CCITT_RLE || g3d1 || get_bits1(&gb))
                ret = decode_group3_1d_line(avctx, &gb, avctx->width, runs,
                                            runend);
421
            else
422 423 424
                ret = decode_group3_2d_line(avctx, &gb, avctx->width, runs,
                                            runend, ref);
            if (compr == TIFF_CCITT_RLE)
425
                align_get_bits(&gb);
426
        }
427 428 429
        if (avctx->err_recognition & AV_EF_EXPLODE && ret < 0)
            goto fail;

430
        if (ret < 0) {
431
            put_line(dst, stride, avctx->width, ref);
432
        } else {
433
            put_line(dst, stride, avctx->width, runs);
434
            FFSWAP(int *, runs, ref);
435 436 437
        }
        dst += stride;
    }
438
    ret = 0;
439
fail:
440 441
    av_free(runs);
    av_free(ref);
442
    return ret;
443
}