1/*
2 * DVD subtitle decoding for ffmpeg
3 * Copyright (c) 2005 Fabrice Bellard
4 *
5 * This file is part of FFmpeg.
6 *
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.
11 *
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.
16 *
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
20 */
21#include "avcodec.h"
22#include "get_bits.h"
23#include "colorspace.h"
24#include "dsputil.h"
25
26//#define DEBUG
27
28static void yuv_a_to_rgba(const uint8_t *ycbcr, const uint8_t *alpha, uint32_t *rgba, int num_values)
29{
30    uint8_t *cm = ff_cropTbl + MAX_NEG_CROP;
31    uint8_t r, g, b;
32    int i, y, cb, cr;
33    int r_add, g_add, b_add;
34
35    for (i = num_values; i > 0; i--) {
36        y = *ycbcr++;
37        cb = *ycbcr++;
38        cr = *ycbcr++;
39        YUV_TO_RGB1_CCIR(cb, cr);
40        YUV_TO_RGB2_CCIR(r, g, b, y);
41        *rgba++ = (*alpha++ << 24) | (r << 16) | (g << 8) | b;
42    }
43}
44
45static int decode_run_2bit(GetBitContext *gb, int *color)
46{
47    unsigned int v, t;
48
49    v = 0;
50    for (t = 1; v < t && t <= 0x40; t <<= 2)
51        v = (v << 4) | get_bits(gb, 4);
52    *color = v & 3;
53    if (v < 4) { /* Code for fill rest of line */
54        return INT_MAX;
55    }
56    return v >> 2;
57}
58
59static int decode_run_8bit(GetBitContext *gb, int *color)
60{
61    int len;
62    int has_run = get_bits1(gb);
63    if (get_bits1(gb))
64        *color = get_bits(gb, 8);
65    else
66        *color = get_bits(gb, 2);
67    if (has_run) {
68        if (get_bits1(gb)) {
69            len = get_bits(gb, 7);
70            if (len == 0)
71                len = INT_MAX;
72            else
73                len += 9;
74        } else
75            len = get_bits(gb, 3) + 2;
76    } else
77        len = 1;
78    return len;
79}
80
81static int decode_rle(uint8_t *bitmap, int linesize, int w, int h,
82                      const uint8_t *buf, int start, int buf_size, int is_8bit)
83{
84    GetBitContext gb;
85    int bit_len;
86    int x, y, len, color;
87    uint8_t *d;
88
89    bit_len = (buf_size - start) * 8;
90    init_get_bits(&gb, buf + start, bit_len);
91
92    x = 0;
93    y = 0;
94    d = bitmap;
95    for(;;) {
96        if (get_bits_count(&gb) > bit_len)
97            return -1;
98        if (is_8bit)
99            len = decode_run_8bit(&gb, &color);
100        else
101            len = decode_run_2bit(&gb, &color);
102        len = FFMIN(len, w - x);
103        memset(d + x, color, len);
104        x += len;
105        if (x >= w) {
106            y++;
107            if (y >= h)
108                break;
109            d += linesize;
110            x = 0;
111            /* byte align */
112            align_get_bits(&gb);
113        }
114    }
115    return 0;
116}
117
118static void guess_palette(uint32_t *rgba_palette,
119                          uint8_t *colormap,
120                          uint8_t *alpha,
121                          uint32_t subtitle_color)
122{
123    uint8_t color_used[16];
124    int nb_opaque_colors, i, level, j, r, g, b;
125
126    for(i = 0; i < 4; i++)
127        rgba_palette[i] = 0;
128
129    memset(color_used, 0, 16);
130    nb_opaque_colors = 0;
131    for(i = 0; i < 4; i++) {
132        if (alpha[i] != 0 && !color_used[colormap[i]]) {
133            color_used[colormap[i]] = 1;
134            nb_opaque_colors++;
135        }
136    }
137
138    if (nb_opaque_colors == 0)
139        return;
140
141    j = nb_opaque_colors;
142    memset(color_used, 0, 16);
143    for(i = 0; i < 4; i++) {
144        if (alpha[i] != 0) {
145            if (!color_used[colormap[i]])  {
146                level = (0xff * j) / nb_opaque_colors;
147                r = (((subtitle_color >> 16) & 0xff) * level) >> 8;
148                g = (((subtitle_color >> 8) & 0xff) * level) >> 8;
149                b = (((subtitle_color >> 0) & 0xff) * level) >> 8;
150                rgba_palette[i] = b | (g << 8) | (r << 16) | ((alpha[i] * 17) << 24);
151                color_used[colormap[i]] = (i + 1);
152                j--;
153            } else {
154                rgba_palette[i] = (rgba_palette[color_used[colormap[i]] - 1] & 0x00ffffff) |
155                                    ((alpha[i] * 17) << 24);
156            }
157        }
158    }
159}
160
161#define READ_OFFSET(a) (big_offsets ? AV_RB32(a) : AV_RB16(a))
162
163static int decode_dvd_subtitles(AVSubtitle *sub_header,
164                                const uint8_t *buf, int buf_size)
165{
166    int cmd_pos, pos, cmd, x1, y1, x2, y2, offset1, offset2, next_cmd_pos;
167    int big_offsets, offset_size, is_8bit = 0;
168    const uint8_t *yuv_palette = 0;
169    uint8_t colormap[4], alpha[256];
170    int date;
171    int i;
172    int is_menu = 0;
173
174    if (buf_size < 10)
175        return -1;
176    memset(sub_header, 0, sizeof(*sub_header));
177
178    if (AV_RB16(buf) == 0) {   /* HD subpicture with 4-byte offsets */
179        big_offsets = 1;
180        offset_size = 4;
181        cmd_pos = 6;
182    } else {
183        big_offsets = 0;
184        offset_size = 2;
185        cmd_pos = 2;
186    }
187
188    cmd_pos = READ_OFFSET(buf + cmd_pos);
189
190    while (cmd_pos > 0 && cmd_pos < buf_size - 2 - offset_size) {
191        date = AV_RB16(buf + cmd_pos);
192        next_cmd_pos = READ_OFFSET(buf + cmd_pos + 2);
193        dprintf(NULL, "cmd_pos=0x%04x next=0x%04x date=%d\n",
194                cmd_pos, next_cmd_pos, date);
195        pos = cmd_pos + 2 + offset_size;
196        offset1 = -1;
197        offset2 = -1;
198        x1 = y1 = x2 = y2 = 0;
199        while (pos < buf_size) {
200            cmd = buf[pos++];
201            dprintf(NULL, "cmd=%02x\n", cmd);
202            switch(cmd) {
203            case 0x00:
204                /* menu subpicture */
205                is_menu = 1;
206                break;
207            case 0x01:
208                /* set start date */
209                sub_header->start_display_time = (date << 10) / 90;
210                break;
211            case 0x02:
212                /* set end date */
213                sub_header->end_display_time = (date << 10) / 90;
214                break;
215            case 0x03:
216                /* set colormap */
217                if ((buf_size - pos) < 2)
218                    goto fail;
219                colormap[3] = buf[pos] >> 4;
220                colormap[2] = buf[pos] & 0x0f;
221                colormap[1] = buf[pos + 1] >> 4;
222                colormap[0] = buf[pos + 1] & 0x0f;
223                pos += 2;
224                break;
225            case 0x04:
226                /* set alpha */
227                if ((buf_size - pos) < 2)
228                    goto fail;
229                alpha[3] = buf[pos] >> 4;
230                alpha[2] = buf[pos] & 0x0f;
231                alpha[1] = buf[pos + 1] >> 4;
232                alpha[0] = buf[pos + 1] & 0x0f;
233                pos += 2;
234            dprintf(NULL, "alpha=%x%x%x%x\n", alpha[0],alpha[1],alpha[2],alpha[3]);
235                break;
236            case 0x05:
237            case 0x85:
238                if ((buf_size - pos) < 6)
239                    goto fail;
240                x1 = (buf[pos] << 4) | (buf[pos + 1] >> 4);
241                x2 = ((buf[pos + 1] & 0x0f) << 8) | buf[pos + 2];
242                y1 = (buf[pos + 3] << 4) | (buf[pos + 4] >> 4);
243                y2 = ((buf[pos + 4] & 0x0f) << 8) | buf[pos + 5];
244                if (cmd & 0x80)
245                    is_8bit = 1;
246                dprintf(NULL, "x1=%d x2=%d y1=%d y2=%d\n", x1, x2, y1, y2);
247                pos += 6;
248                break;
249            case 0x06:
250                if ((buf_size - pos) < 4)
251                    goto fail;
252                offset1 = AV_RB16(buf + pos);
253                offset2 = AV_RB16(buf + pos + 2);
254                dprintf(NULL, "offset1=0x%04x offset2=0x%04x\n", offset1, offset2);
255                pos += 4;
256                break;
257            case 0x86:
258                if ((buf_size - pos) < 8)
259                    goto fail;
260                offset1 = AV_RB32(buf + pos);
261                offset2 = AV_RB32(buf + pos + 4);
262                dprintf(NULL, "offset1=0x%04x offset2=0x%04x\n", offset1, offset2);
263                pos += 8;
264                break;
265
266            case 0x83:
267                /* HD set palette */
268                if ((buf_size - pos) < 768)
269                    goto fail;
270                yuv_palette = buf + pos;
271                pos += 768;
272                break;
273            case 0x84:
274                /* HD set contrast (alpha) */
275                if ((buf_size - pos) < 256)
276                    goto fail;
277                for (i = 0; i < 256; i++)
278                    alpha[i] = 0xFF - buf[pos+i];
279                pos += 256;
280                break;
281
282            case 0xff:
283                goto the_end;
284            default:
285                dprintf(NULL, "unrecognised subpicture command 0x%x\n", cmd);
286                goto the_end;
287            }
288        }
289    the_end:
290        if (offset1 >= 0) {
291            int w, h;
292            uint8_t *bitmap;
293
294            /* decode the bitmap */
295            w = x2 - x1 + 1;
296            if (w < 0)
297                w = 0;
298            h = y2 - y1;
299            if (h < 0)
300                h = 0;
301            if (w > 0 && h > 0) {
302                if (sub_header->rects != NULL) {
303                    for (i = 0; i < sub_header->num_rects; i++) {
304                        av_freep(&sub_header->rects[i]->pict.data[0]);
305                        av_freep(&sub_header->rects[i]->pict.data[1]);
306                        av_freep(&sub_header->rects[i]);
307                    }
308                    av_freep(&sub_header->rects);
309                    sub_header->num_rects = 0;
310                }
311
312                bitmap = av_malloc(w * h);
313                sub_header->rects = av_mallocz(sizeof(*sub_header->rects));
314                sub_header->rects[0] = av_mallocz(sizeof(AVSubtitleRect));
315                sub_header->num_rects = 1;
316                sub_header->rects[0]->pict.data[0] = bitmap;
317                decode_rle(bitmap, w * 2, w, (h + 1) / 2,
318                           buf, offset1, buf_size, is_8bit);
319                decode_rle(bitmap + w, w * 2, w, h / 2,
320                           buf, offset2, buf_size, is_8bit);
321                sub_header->rects[0]->pict.data[1] = av_mallocz(AVPALETTE_SIZE);
322                if (is_8bit) {
323                    if (yuv_palette == 0)
324                        goto fail;
325                    sub_header->rects[0]->nb_colors = 256;
326                    yuv_a_to_rgba(yuv_palette, alpha, (uint32_t*)sub_header->rects[0]->pict.data[1], 256);
327                } else {
328                    sub_header->rects[0]->nb_colors = 4;
329                    guess_palette((uint32_t*)sub_header->rects[0]->pict.data[1],
330                                  colormap, alpha, 0xffff00);
331                }
332                sub_header->rects[0]->x = x1;
333                sub_header->rects[0]->y = y1;
334                sub_header->rects[0]->w = w;
335                sub_header->rects[0]->h = h;
336                sub_header->rects[0]->type = SUBTITLE_BITMAP;
337                sub_header->rects[0]->pict.linesize[0] = w;
338            }
339        }
340        if (next_cmd_pos == cmd_pos)
341            break;
342        cmd_pos = next_cmd_pos;
343    }
344    if (sub_header->num_rects > 0)
345        return is_menu;
346 fail:
347    if (sub_header->rects != NULL) {
348        for (i = 0; i < sub_header->num_rects; i++) {
349            av_freep(&sub_header->rects[i]->pict.data[0]);
350            av_freep(&sub_header->rects[i]->pict.data[1]);
351            av_freep(&sub_header->rects[i]);
352        }
353        av_freep(&sub_header->rects);
354        sub_header->num_rects = 0;
355    }
356    return -1;
357}
358
359static int is_transp(const uint8_t *buf, int pitch, int n,
360                     const uint8_t *transp_color)
361{
362    int i;
363    for(i = 0; i < n; i++) {
364        if (!transp_color[*buf])
365            return 0;
366        buf += pitch;
367    }
368    return 1;
369}
370
371/* return 0 if empty rectangle, 1 if non empty */
372static int find_smallest_bounding_rectangle(AVSubtitle *s)
373{
374    uint8_t transp_color[256];
375    int y1, y2, x1, x2, y, w, h, i;
376    uint8_t *bitmap;
377
378    if (s->num_rects == 0 || s->rects == NULL || s->rects[0]->w <= 0 || s->rects[0]->h <= 0)
379        return 0;
380
381    memset(transp_color, 0, 256);
382    for(i = 0; i < s->rects[0]->nb_colors; i++) {
383        if ((((uint32_t*)s->rects[0]->pict.data[1])[i] >> 24) == 0)
384            transp_color[i] = 1;
385    }
386    y1 = 0;
387    while (y1 < s->rects[0]->h && is_transp(s->rects[0]->pict.data[0] + y1 * s->rects[0]->pict.linesize[0],
388                                  1, s->rects[0]->w, transp_color))
389        y1++;
390    if (y1 == s->rects[0]->h) {
391        av_freep(&s->rects[0]->pict.data[0]);
392        s->rects[0]->w = s->rects[0]->h = 0;
393        return 0;
394    }
395
396    y2 = s->rects[0]->h - 1;
397    while (y2 > 0 && is_transp(s->rects[0]->pict.data[0] + y2 * s->rects[0]->pict.linesize[0], 1,
398                               s->rects[0]->w, transp_color))
399        y2--;
400    x1 = 0;
401    while (x1 < (s->rects[0]->w - 1) && is_transp(s->rects[0]->pict.data[0] + x1, s->rects[0]->pict.linesize[0],
402                                        s->rects[0]->h, transp_color))
403        x1++;
404    x2 = s->rects[0]->w - 1;
405    while (x2 > 0 && is_transp(s->rects[0]->pict.data[0] + x2, s->rects[0]->pict.linesize[0], s->rects[0]->h,
406                                  transp_color))
407        x2--;
408    w = x2 - x1 + 1;
409    h = y2 - y1 + 1;
410    bitmap = av_malloc(w * h);
411    if (!bitmap)
412        return 1;
413    for(y = 0; y < h; y++) {
414        memcpy(bitmap + w * y, s->rects[0]->pict.data[0] + x1 + (y1 + y) * s->rects[0]->pict.linesize[0], w);
415    }
416    av_freep(&s->rects[0]->pict.data[0]);
417    s->rects[0]->pict.data[0] = bitmap;
418    s->rects[0]->pict.linesize[0] = w;
419    s->rects[0]->w = w;
420    s->rects[0]->h = h;
421    s->rects[0]->x += x1;
422    s->rects[0]->y += y1;
423    return 1;
424}
425
426#ifdef DEBUG
427#undef fprintf
428#undef perror
429#undef exit
430static void ppm_save(const char *filename, uint8_t *bitmap, int w, int h,
431                     uint32_t *rgba_palette)
432{
433    int x, y, v;
434    FILE *f;
435
436    f = fopen(filename, "w");
437    if (!f) {
438        perror(filename);
439        exit(1);
440    }
441    fprintf(f, "P6\n"
442            "%d %d\n"
443            "%d\n",
444            w, h, 255);
445    for(y = 0; y < h; y++) {
446        for(x = 0; x < w; x++) {
447            v = rgba_palette[bitmap[y * w + x]];
448            putc((v >> 16) & 0xff, f);
449            putc((v >> 8) & 0xff, f);
450            putc((v >> 0) & 0xff, f);
451        }
452    }
453    fclose(f);
454}
455#endif
456
457static int dvdsub_decode(AVCodecContext *avctx,
458                         void *data, int *data_size,
459                         AVPacket *avpkt)
460{
461    const uint8_t *buf = avpkt->data;
462    int buf_size = avpkt->size;
463    AVSubtitle *sub = (void *)data;
464    int is_menu;
465
466    is_menu = decode_dvd_subtitles(sub, buf, buf_size);
467
468    if (is_menu < 0) {
469    no_subtitle:
470        *data_size = 0;
471
472        return buf_size;
473    }
474    if (!is_menu && find_smallest_bounding_rectangle(sub) == 0)
475        goto no_subtitle;
476
477#if defined(DEBUG)
478    dprintf(NULL, "start=%d ms end =%d ms\n",
479            sub->start_display_time,
480            sub->end_display_time);
481    ppm_save("/tmp/a.ppm", sub->rects[0]->pict.data[0],
482             sub->rects[0]->w, sub->rects[0]->h, sub->rects[0]->pict.data[1]);
483#endif
484
485    *data_size = 1;
486    return buf_size;
487}
488
489AVCodec dvdsub_decoder = {
490    "dvdsub",
491    AVMEDIA_TYPE_SUBTITLE,
492    CODEC_ID_DVD_SUBTITLE,
493    0,
494    NULL,
495    NULL,
496    NULL,
497    dvdsub_decode,
498    .long_name = NULL_IF_CONFIG_SMALL("DVD subtitles"),
499};
500