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