Merge commit '42cf7f91f1e9dabf494ff469d8f67ac8b33b0f63'
[ffmpeg.git] / libavcodec / dvdsubenc.c
1 /*
2  * DVD subtitle encoding
3  * Copyright (c) 2005 Wolfram Gloger
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 "bytestream.h"
23 #include "internal.h"
24 #include "libavutil/avassert.h"
25 #include "libavutil/bprint.h"
26 #include "libavutil/imgutils.h"
27 #include "libavutil/opt.h"
28
29 typedef struct {
30     AVClass *class;
31     uint32_t global_palette[16];
32     int even_rows_fix;
33 } DVDSubtitleContext;
34
35 // ncnt is the nibble counter
36 #define PUTNIBBLE(val)\
37 do {\
38     if (ncnt++ & 1)\
39         *q++ = bitbuf | ((val) & 0x0f);\
40     else\
41         bitbuf = (val) << 4;\
42 } while(0)
43
44 static void dvd_encode_rle(uint8_t **pq,
45                            const uint8_t *bitmap, int linesize,
46                            int w, int h,
47                            const int cmap[256])
48 {
49     uint8_t *q;
50     unsigned int bitbuf = 0;
51     int ncnt;
52     int x, y, len, color;
53
54     q = *pq;
55
56     for (y = 0; y < h; ++y) {
57         ncnt = 0;
58         for(x = 0; x < w; x += len) {
59             color = bitmap[x];
60             for (len=1; x+len < w; ++len)
61                 if (bitmap[x+len] != color)
62                     break;
63             color = cmap[color];
64             av_assert0(color < 4);
65             if (len < 0x04) {
66                 PUTNIBBLE((len << 2)|color);
67             } else if (len < 0x10) {
68                 PUTNIBBLE(len >> 2);
69                 PUTNIBBLE((len << 2)|color);
70             } else if (len < 0x40) {
71                 PUTNIBBLE(0);
72                 PUTNIBBLE(len >> 2);
73                 PUTNIBBLE((len << 2)|color);
74             } else if (x+len == w) {
75                 PUTNIBBLE(0);
76                 PUTNIBBLE(0);
77                 PUTNIBBLE(0);
78                 PUTNIBBLE(color);
79             } else {
80                 if (len > 0xff)
81                     len = 0xff;
82                 PUTNIBBLE(0);
83                 PUTNIBBLE(len >> 6);
84                 PUTNIBBLE(len >> 2);
85                 PUTNIBBLE((len << 2)|color);
86             }
87         }
88         /* end of line */
89         if (ncnt & 1)
90             PUTNIBBLE(0);
91         bitmap += linesize;
92     }
93
94     *pq = q;
95 }
96
97 static int color_distance(uint32_t a, uint32_t b)
98 {
99     int r = 0, d, i;
100     int alpha_a = 8, alpha_b = 8;
101
102     for (i = 24; i >= 0; i -= 8) {
103         d = alpha_a * (int)((a >> i) & 0xFF) -
104             alpha_b * (int)((b >> i) & 0xFF);
105         r += d * d;
106         alpha_a = a >> 28;
107         alpha_b = b >> 28;
108     }
109     return r;
110 }
111
112 /**
113  * Count colors used in a rectangle, quantizing alpha and grouping by
114  * nearest global palette entry.
115  */
116 static void count_colors(AVCodecContext *avctx, unsigned hits[33],
117                          const AVSubtitleRect *r)
118 {
119     DVDSubtitleContext *dvdc = avctx->priv_data;
120     unsigned count[256] = { 0 };
121     uint32_t *palette = (uint32_t *)r->data[1];
122     uint32_t color;
123     int x, y, i, j, match, d, best_d, av_uninit(best_j);
124     uint8_t *p = r->data[0];
125
126     for (y = 0; y < r->h; y++) {
127         for (x = 0; x < r->w; x++)
128             count[*(p++)]++;
129         p += r->linesize[0] - r->w;
130     }
131     for (i = 0; i < 256; i++) {
132         if (!count[i]) /* avoid useless search */
133             continue;
134         color = palette[i];
135         /* 0: transparent, 1-16: semi-transparent, 17-33 opaque */
136         match = color < 0x33000000 ? 0 : color < 0xCC000000 ? 1 : 17;
137         if (match) {
138             best_d = INT_MAX;
139             for (j = 0; j < 16; j++) {
140                 d = color_distance(0xFF000000 | color,
141                                    0xFF000000 | dvdc->global_palette[j]);
142                 if (d < best_d) {
143                     best_d = d;
144                     best_j = j;
145                 }
146             }
147             match += best_j;
148         }
149         hits[match] += count[i];
150     }
151 }
152
153 static void select_palette(AVCodecContext *avctx, int out_palette[4],
154                            int out_alpha[4], unsigned hits[33])
155 {
156     DVDSubtitleContext *dvdc = avctx->priv_data;
157     int i, j, bright, mult;
158     uint32_t color;
159     int selected[4] = { 0 };
160     uint32_t pseudopal[33] = { 0 };
161     uint32_t refcolor[3] = { 0x00000000, 0xFFFFFFFF, 0xFF000000 };
162
163     /* Bonus for transparent: if the rectangle fits tightly the text, the
164        background color can be quite rare, but it would be ugly without it */
165     hits[0] *= 16;
166     /* Bonus for bright colors */
167     for (i = 0; i < 16; i++) {
168         if (!(hits[1 + i] + hits[17 + i]))
169             continue; /* skip unused colors to gain time */
170         color = dvdc->global_palette[i];
171         bright = 0;
172         for (j = 0; j < 3; j++, color >>= 8)
173             bright += (color & 0xFF) < 0x40 || (color & 0xFF) >= 0xC0;
174         mult = 2 + FFMIN(bright, 2);
175         hits[ 1 + i] *= mult;
176         hits[17 + i] *= mult;
177     }
178
179     /* Select four most frequent colors */
180     for (i = 0; i < 4; i++) {
181         for (j = 0; j < 33; j++)
182             if (hits[j] > hits[selected[i]])
183                 selected[i] = j;
184         hits[selected[i]] = 0;
185     }
186
187     /* Order the colors like in most DVDs:
188        0: background, 1: foreground, 2: outline */
189     for (i = 0; i < 16; i++) {
190         pseudopal[ 1 + i] = 0x80000000 | dvdc->global_palette[i];
191         pseudopal[17 + i] = 0xFF000000 | dvdc->global_palette[i];
192     }
193     for (i = 0; i < 3; i++) {
194         int best_d = color_distance(refcolor[i], pseudopal[selected[i]]);
195         for (j = i + 1; j < 4; j++) {
196             int d = color_distance(refcolor[i], pseudopal[selected[j]]);
197             if (d < best_d) {
198                 FFSWAP(int, selected[i], selected[j]);
199                 best_d = d;
200             }
201         }
202     }
203
204     /* Output */
205     for (i = 0; i < 4; i++) {
206         out_palette[i] = selected[i] ? (selected[i] - 1) & 0xF : 0;
207         out_alpha  [i] = !selected[i] ? 0 : selected[i] < 17 ? 0x80 : 0xFF;
208     }
209 }
210
211 static void build_color_map(AVCodecContext *avctx, int cmap[],
212                             const uint32_t palette[],
213                             const int out_palette[], unsigned int const out_alpha[])
214 {
215     DVDSubtitleContext *dvdc = avctx->priv_data;
216     int i, j, d, best_d;
217     uint32_t pseudopal[4];
218
219     for (i = 0; i < 4; i++)
220         pseudopal[i] = (out_alpha[i] << 24) |
221                        dvdc->global_palette[out_palette[i]];
222     for (i = 0; i < 256; i++) {
223         best_d = INT_MAX;
224         for (j = 0; j < 4; j++) {
225             d = color_distance(pseudopal[j], palette[i]);
226             if (d < best_d) {
227                 cmap[i] = j;
228                 best_d = d;
229             }
230         }
231     }
232 }
233
234 static void copy_rectangle(AVSubtitleRect *dst, AVSubtitleRect *src, int cmap[])
235 {
236     int x, y;
237     uint8_t *p, *q;
238
239     p = src->data[0];
240     q = dst->data[0] + (src->x - dst->x) +
241                             (src->y - dst->y) * dst->linesize[0];
242     for (y = 0; y < src->h; y++) {
243         for (x = 0; x < src->w; x++)
244             *(q++) = cmap[*(p++)];
245         p += src->linesize[0] - src->w;
246         q += dst->linesize[0] - src->w;
247     }
248 }
249
250 static int encode_dvd_subtitles(AVCodecContext *avctx,
251                                 uint8_t *outbuf, int outbuf_size,
252                                 const AVSubtitle *h)
253 {
254     DVDSubtitleContext *dvdc = avctx->priv_data;
255     uint8_t *q, *qq;
256     int offset1, offset2;
257     int i, rects = h->num_rects, ret;
258     unsigned global_palette_hits[33] = { 0 };
259     int cmap[256];
260     int out_palette[4];
261     int out_alpha[4];
262     AVSubtitleRect vrect;
263     uint8_t *vrect_data = NULL;
264     int x2, y2;
265     int forced = 0;
266
267     if (rects == 0 || !h->rects)
268         return AVERROR(EINVAL);
269     for (i = 0; i < rects; i++)
270         if (h->rects[i]->type != SUBTITLE_BITMAP) {
271             av_log(avctx, AV_LOG_ERROR, "Bitmap subtitle required\n");
272             return AVERROR(EINVAL);
273         }
274     /* Mark this subtitle forced if any of the rectangles is forced. */
275     for (i = 0; i < rects; i++)
276         if ((h->rects[i]->flags & AV_SUBTITLE_FLAG_FORCED) != 0) {
277             forced = 1;
278             break;
279         }
280
281 #if FF_API_AVPICTURE
282 FF_DISABLE_DEPRECATION_WARNINGS
283     for (i = 0; i < rects; i++)
284         if (!h->rects[i]->data[0]) {
285             AVSubtitleRect *rect = h->rects[i];
286             int j;
287             for (j = 0; j < 4; j++) {
288                 rect->data[j] = rect->pict.data[j];
289                 rect->linesize[j] = rect->pict.linesize[j];
290             }
291         }
292 FF_ENABLE_DEPRECATION_WARNINGS
293 #endif
294
295     vrect = *h->rects[0];
296
297     if (rects > 1) {
298         /* DVD subtitles can have only one rectangle: build a virtual
299            rectangle containing all actual rectangles.
300            The data of the rectangles will be copied later, when the palette
301            is decided, because the rectangles may have different palettes. */
302         int xmin = h->rects[0]->x, xmax = xmin + h->rects[0]->w;
303         int ymin = h->rects[0]->y, ymax = ymin + h->rects[0]->h;
304         for (i = 1; i < rects; i++) {
305             xmin = FFMIN(xmin, h->rects[i]->x);
306             ymin = FFMIN(ymin, h->rects[i]->y);
307             xmax = FFMAX(xmax, h->rects[i]->x + h->rects[i]->w);
308             ymax = FFMAX(ymax, h->rects[i]->y + h->rects[i]->h);
309         }
310         vrect.x = xmin;
311         vrect.y = ymin;
312         vrect.w = xmax - xmin;
313         vrect.h = ymax - ymin;
314         if ((ret = av_image_check_size(vrect.w, vrect.h, 0, avctx)) < 0)
315             return ret;
316
317         /* Count pixels outside the virtual rectangle as transparent */
318         global_palette_hits[0] = vrect.w * vrect.h;
319         for (i = 0; i < rects; i++)
320             global_palette_hits[0] -= h->rects[i]->w * h->rects[i]->h;
321     }
322
323     for (i = 0; i < rects; i++)
324         count_colors(avctx, global_palette_hits, h->rects[i]);
325     select_palette(avctx, out_palette, out_alpha, global_palette_hits);
326
327     if (rects > 1) {
328         if (!(vrect_data = av_calloc(vrect.w, vrect.h)))
329             return AVERROR(ENOMEM);
330         vrect.data    [0] = vrect_data;
331         vrect.linesize[0] = vrect.w;
332         for (i = 0; i < rects; i++) {
333             build_color_map(avctx, cmap, (uint32_t *)h->rects[i]->data[1],
334                             out_palette, out_alpha);
335             copy_rectangle(&vrect, h->rects[i], cmap);
336         }
337         for (i = 0; i < 4; i++)
338             cmap[i] = i;
339     } else {
340         build_color_map(avctx, cmap, (uint32_t *)h->rects[0]->data[1],
341                         out_palette, out_alpha);
342     }
343
344     av_log(avctx, AV_LOG_DEBUG, "Selected palette:");
345     for (i = 0; i < 4; i++)
346         av_log(avctx, AV_LOG_DEBUG, " 0x%06"PRIx32"@@%02x (0x%x,0x%x)",
347                dvdc->global_palette[out_palette[i]], out_alpha[i],
348                out_palette[i], out_alpha[i] >> 4);
349     av_log(avctx, AV_LOG_DEBUG, "\n");
350
351     // encode data block
352     q = outbuf + 4;
353     offset1 = q - outbuf;
354     // worst case memory requirement: 1 nibble per pixel..
355     if ((q - outbuf) + vrect.w * vrect.h / 2 + 17 + 21 > outbuf_size) {
356         av_log(NULL, AV_LOG_ERROR, "dvd_subtitle too big\n");
357         ret = AVERROR_BUFFER_TOO_SMALL;
358         goto fail;
359     }
360     dvd_encode_rle(&q, vrect.data[0], vrect.w * 2,
361                    vrect.w, (vrect.h + 1) >> 1, cmap);
362     offset2 = q - outbuf;
363     dvd_encode_rle(&q, vrect.data[0] + vrect.w, vrect.w * 2,
364                    vrect.w, vrect.h >> 1, cmap);
365
366     if (dvdc->even_rows_fix && (vrect.h & 1)) {
367         // Work-around for some players that want the height to be even.
368         vrect.h++;
369         *q++ = 0x00; // 0x00 0x00 == empty row, i.e. fully transparent
370         *q++ = 0x00;
371     }
372
373     // set data packet size
374     qq = outbuf + 2;
375     bytestream_put_be16(&qq, q - outbuf);
376
377     // send start display command
378     bytestream_put_be16(&q, (h->start_display_time*90) >> 10);
379     bytestream_put_be16(&q, (q - outbuf) /*- 2 */ + 8 + 12 + 2);
380     *q++ = 0x03; // palette - 4 nibbles
381     *q++ = (out_palette[3] << 4) | out_palette[2];
382     *q++ = (out_palette[1] << 4) | out_palette[0];
383     *q++ = 0x04; // alpha - 4 nibbles
384     *q++ = (out_alpha[3] & 0xF0) | (out_alpha[2] >> 4);
385     *q++ = (out_alpha[1] & 0xF0) | (out_alpha[0] >> 4);
386
387     // 12 bytes per rect
388     x2 = vrect.x + vrect.w - 1;
389     y2 = vrect.y + vrect.h - 1;
390
391     *q++ = 0x05;
392     // x1 x2 -> 6 nibbles
393     *q++ = vrect.x >> 4;
394     *q++ = (vrect.x << 4) | ((x2 >> 8) & 0xf);
395     *q++ = x2;
396     // y1 y2 -> 6 nibbles
397     *q++ = vrect.y >> 4;
398     *q++ = (vrect.y << 4) | ((y2 >> 8) & 0xf);
399     *q++ = y2;
400
401     *q++ = 0x06;
402     // offset1, offset2
403     bytestream_put_be16(&q, offset1);
404     bytestream_put_be16(&q, offset2);
405
406     *q++ = forced ? 0x00 : 0x01; // start command
407     *q++ = 0xff; // terminating command
408
409     // send stop display command last
410     bytestream_put_be16(&q, (h->end_display_time*90) >> 10);
411     bytestream_put_be16(&q, (q - outbuf) - 2 /*+ 4*/);
412     *q++ = 0x02; // set end
413     *q++ = 0xff; // terminating command
414
415     qq = outbuf;
416     bytestream_put_be16(&qq, q - outbuf);
417
418     av_log(NULL, AV_LOG_DEBUG, "subtitle_packet size=%"PTRDIFF_SPECIFIER"\n", q - outbuf);
419     ret = q - outbuf;
420
421 fail:
422     av_free(vrect_data);
423     return ret;
424 }
425
426 static int dvdsub_init(AVCodecContext *avctx)
427 {
428     DVDSubtitleContext *dvdc = avctx->priv_data;
429     static const uint32_t default_palette[16] = {
430         0x000000, 0x0000FF, 0x00FF00, 0xFF0000,
431         0xFFFF00, 0xFF00FF, 0x00FFFF, 0xFFFFFF,
432         0x808000, 0x8080FF, 0x800080, 0x80FF80,
433         0x008080, 0xFF8080, 0x555555, 0xAAAAAA,
434     };
435     AVBPrint extradata;
436     int i, ret;
437
438     av_assert0(sizeof(dvdc->global_palette) == sizeof(default_palette));
439     memcpy(dvdc->global_palette, default_palette, sizeof(dvdc->global_palette));
440
441     av_bprint_init(&extradata, 0, 1);
442     if (avctx->width && avctx->height)
443         av_bprintf(&extradata, "size: %dx%d\n", avctx->width, avctx->height);
444     av_bprintf(&extradata, "palette:");
445     for (i = 0; i < 16; i++)
446         av_bprintf(&extradata, " %06"PRIx32"%c",
447                    dvdc->global_palette[i] & 0xFFFFFF, i < 15 ? ',' : '\n');
448
449     ret = avpriv_bprint_to_extradata(avctx, &extradata);
450     if (ret < 0)
451         return ret;
452
453     return 0;
454 }
455
456 static int dvdsub_encode(AVCodecContext *avctx,
457                          unsigned char *buf, int buf_size,
458                          const AVSubtitle *sub)
459 {
460     //DVDSubtitleContext *s = avctx->priv_data;
461     int ret;
462
463     ret = encode_dvd_subtitles(avctx, buf, buf_size, sub);
464     return ret;
465 }
466
467 #define OFFSET(x) offsetof(DVDSubtitleContext, x)
468 #define SE AV_OPT_FLAG_SUBTITLE_PARAM | AV_OPT_FLAG_ENCODING_PARAM
469 static const AVOption options[] = {
470     {"even_rows_fix", "Make number of rows even (workaround for some players)", OFFSET(even_rows_fix), AV_OPT_TYPE_BOOL, {.i64 = 0}, 0, 1, SE},
471     { NULL },
472 };
473
474 static const AVClass dvdsubenc_class = {
475     .class_name = "VOBSUB subtitle encoder",
476     .item_name  = av_default_item_name,
477     .option     = options,
478     .version    = LIBAVUTIL_VERSION_INT,
479 };
480
481 AVCodec ff_dvdsub_encoder = {
482     .name           = "dvdsub",
483     .long_name      = NULL_IF_CONFIG_SMALL("DVD subtitles"),
484     .type           = AVMEDIA_TYPE_SUBTITLE,
485     .id             = AV_CODEC_ID_DVD_SUBTITLE,
486     .init           = dvdsub_init,
487     .encode_sub     = dvdsub_encode,
488     .priv_class     = &dvdsubenc_class,
489     .priv_data_size = sizeof(DVDSubtitleContext),
490 };