FFmpeg
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
dvdsubenc.c
Go to the documentation of this file.
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];
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 
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");
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 
436  .name = "dvdsub",
437  .type = AVMEDIA_TYPE_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 };