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->pict.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->pict.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->pict.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->pict.data[0];
 240     q = dst->pict.data[0] + (src->x - dst->x) +
 241                             (src->y - dst->y) * dst->pict.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->pict.linesize[0] - src->w;
 246         q += dst->pict.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     vrect = *h->rects[0];
 281
 282     if (rects > 1) {
 283         /* DVD subtitles can have only one rectangle: build a virtual
 284            rectangle containing all actual rectangles.
 285            The data of the rectangles will be copied later, when the palette
 286            is decided, because the rectangles may have different palettes. */
 287         int xmin = h->rects[0]->x, xmax = xmin + h->rects[0]->w;
 288         int ymin = h->rects[0]->y, ymax = ymin + h->rects[0]->h;
 289         for (i = 1; i < rects; i++) {
 290             xmin = FFMIN(xmin, h->rects[i]->x);
 291             ymin = FFMIN(ymin, h->rects[i]->y);
 292             xmax = FFMAX(xmax, h->rects[i]->x + h->rects[i]->w);
 293             ymax = FFMAX(ymax, h->rects[i]->y + h->rects[i]->h);
 294         }
 295         vrect.x = xmin;
 296         vrect.y = ymin;
 297         vrect.w = xmax - xmin;
 298         vrect.h = ymax - ymin;
 299         if ((ret = av_image_check_size(vrect.w, vrect.h, 0, avctx)) < 0)
 300             return ret;
 301
 302         /* Count pixels outside the virtual rectangle as transparent */
 303         global_palette_hits[0] = vrect.w * vrect.h;
 304         for (i = 0; i < rects; i++)
 305             global_palette_hits[0] -= h->rects[i]->w * h->rects[i]->h;
 306     }
 307
 308     for (i = 0; i < rects; i++)
 309         count_colors(avctx, global_palette_hits, h->rects[i]);
 310     select_palette(avctx, out_palette, out_alpha, global_palette_hits);
 311
 312     if (rects > 1) {
 313         if (!(vrect_data = av_calloc(vrect.w, vrect.h)))
 314             return AVERROR(ENOMEM);
 315         vrect.pict.data    [0] = vrect_data;
 316         vrect.pict.linesize[0] = vrect.w;
 317         for (i = 0; i < rects; i++) {
 318             build_color_map(avctx, cmap, (uint32_t *)h->rects[i]->pict.data[1],
 319                             out_palette, out_alpha);
 320             copy_rectangle(&vrect, h->rects[i], cmap);
 321         }
 322         for (i = 0; i < 4; i++)
 323             cmap[i] = i;
 324     } else {
 325         build_color_map(avctx, cmap, (uint32_t *)h->rects[0]->pict.data[1],
 326                         out_palette, out_alpha);
 327     }
 328
 329     av_log(avctx, AV_LOG_DEBUG, "Selected palette:");
 330     for (i = 0; i < 4; i++)
 331         av_log(avctx, AV_LOG_DEBUG, " 0x%06x@@%02x (0x%x,0x%x)",
 332                dvdc->global_palette[out_palette[i]], out_alpha[i],
 333                out_palette[i], out_alpha[i] >> 4);
 334     av_log(avctx, AV_LOG_DEBUG, "\n");
 335
 336     // encode data block
 337     q = outbuf + 4;
 338     offset1 = q - outbuf;
 339     // worst case memory requirement: 1 nibble per pixel..
 340     if ((q - outbuf) + vrect.w * vrect.h / 2 + 17 + 21 > outbuf_size) {
 341         av_log(NULL, AV_LOG_ERROR, "dvd_subtitle too big\n");
 342         ret = AVERROR_BUFFER_TOO_SMALL;
 343         goto fail;
 344     }
 345     dvd_encode_rle(&q, vrect.pict.data[0], vrect.w * 2,
 346                    vrect.w, (vrect.h + 1) >> 1, cmap);
 347     offset2 = q - outbuf;
 348     dvd_encode_rle(&q, vrect.pict.data[0] + vrect.w, vrect.w * 2,
 349                    vrect.w, vrect.h >> 1, cmap);
 350
 351     if (dvdc->even_rows_fix && (vrect.h & 1)) {
 352         // Work-around for some players that want the height to be even.
 353         vrect.h++;
 354         *q++ = 0x00; // 0x00 0x00 == empty row, i.e. fully transparent
 355         *q++ = 0x00;
 356     }
 357
 358     // set data packet size
 359     qq = outbuf + 2;
 360     bytestream_put_be16(&qq, q - outbuf);
 361
 362     // send start display command
 363     bytestream_put_be16(&q, (h->start_display_time*90) >> 10);
 364     bytestream_put_be16(&q, (q - outbuf) /*- 2 */ + 8 + 12 + 2);
 365     *q++ = 0x03; // palette - 4 nibbles
 366     *q++ = (out_palette[3] << 4) | out_palette[2];
 367     *q++ = (out_palette[1] << 4) | out_palette[0];
 368     *q++ = 0x04; // alpha - 4 nibbles
 369     *q++ = (out_alpha[3] & 0xF0) | (out_alpha[2] >> 4);
 370     *q++ = (out_alpha[1] & 0xF0) | (out_alpha[0] >> 4);
 371
 372     // 12 bytes per rect
 373     x2 = vrect.x + vrect.w - 1;
 374     y2 = vrect.y + vrect.h - 1;
 375
 376     *q++ = 0x05;
 377     // x1 x2 -> 6 nibbles
 378     *q++ = vrect.x >> 4;
 379     *q++ = (vrect.x << 4) | ((x2 >> 8) & 0xf);
 380     *q++ = x2;
 381     // y1 y2 -> 6 nibbles
 382     *q++ = vrect.y >> 4;
 383     *q++ = (vrect.y << 4) | ((y2 >> 8) & 0xf);
 384     *q++ = y2;
 385
 386     *q++ = 0x06;
 387     // offset1, offset2
 388     bytestream_put_be16(&q, offset1);
 389     bytestream_put_be16(&q, offset2);
 390
 391     *q++ = forced ? 0x00 : 0x01; // start command
 392     *q++ = 0xff; // terminating command
 393
 394     // send stop display command last
 395     bytestream_put_be16(&q, (h->end_display_time*90) >> 10);
 396     bytestream_put_be16(&q, (q - outbuf) - 2 /*+ 4*/);
 397     *q++ = 0x02; // set end
 398     *q++ = 0xff; // terminating command
 399
 400     qq = outbuf;
 401     bytestream_put_be16(&qq, q - outbuf);
 402
 403     av_log(NULL, AV_LOG_DEBUG, "subtitle_packet size=%"PTRDIFF_SPECIFIER"\n", q - outbuf);
 404     ret = q - outbuf;
 405
 406 fail:
 407     av_free(vrect_data);
 408     return ret;
 409 }
 410
 411 static int dvdsub_init(AVCodecContext *avctx)
 412 {
 413     DVDSubtitleContext *dvdc = avctx->priv_data;
 414     static const uint32_t default_palette[16] = {
 415         0x000000, 0x0000FF, 0x00FF00, 0xFF0000,
 416         0xFFFF00, 0xFF00FF, 0x00FFFF, 0xFFFFFF,
 417         0x808000, 0x8080FF, 0x800080, 0x80FF80,
 418         0x008080, 0xFF8080, 0x555555, 0xAAAAAA,
 419     };
 420     AVBPrint extradata;
 421     int i, ret;
 422
 423     av_assert0(sizeof(dvdc->global_palette) == sizeof(default_palette));
 424     memcpy(dvdc->global_palette, default_palette, sizeof(dvdc->global_palette));
 425
 426     av_bprint_init(&extradata, 0, 1);
 427     if (avctx->width && avctx->height)
 428         av_bprintf(&extradata, "size: %dx%d\n", avctx->width, avctx->height);
 429     av_bprintf(&extradata, "palette:");
 430     for (i = 0; i < 16; i++)
 431         av_bprintf(&extradata, " %06"PRIx32"%c",
 432                    dvdc->global_palette[i] & 0xFFFFFF, i < 15 ? ',' : '\n');
 433
 434     ret = avpriv_bprint_to_extradata(avctx, &extradata);
 435     if (ret < 0)
 436         return ret;
 437
 438     return 0;
 439 }
 440
 441 static int dvdsub_encode(AVCodecContext *avctx,
 442                          unsigned char *buf, int buf_size,
 443                          const AVSubtitle *sub)
 444 {
 445     //DVDSubtitleContext *s = avctx->priv_data;
 446     int ret;
 447
 448     ret = encode_dvd_subtitles(avctx, buf, buf_size, sub);
 449     return ret;
 450 }
 451
 452 #define OFFSET(x) offsetof(DVDSubtitleContext, x)
 453 #define SE AV_OPT_FLAG_SUBTITLE_PARAM | AV_OPT_FLAG_ENCODING_PARAM
 454 static const AVOption options[] = {
 455     {"even_rows_fix", "Make number of rows even (workaround for some players)", OFFSET(even_rows_fix), AV_OPT_TYPE_INT, {.i64 = 0}, 0, 1, SE},
 456     { NULL },
 457 };
 458
 459 static const AVClass dvdsubenc_class = {
 460     .class_name = "VOBSUB subtitle encoder",
 461     .item_name  = av_default_item_name,
 462     .option     = options,
 463     .version    = LIBAVUTIL_VERSION_INT,
 464 };
 465
 466 AVCodec ff_dvdsub_encoder = {
 467     .name           = "dvdsub",
 468     .long_name      = NULL_IF_CONFIG_SMALL("DVD subtitles"),
 469     .type           = AVMEDIA_TYPE_SUBTITLE,
 470     .id             = AV_CODEC_ID_DVD_SUBTITLE,
 471     .init           = dvdsub_init,
 472     .encode_sub     = dvdsub_encode,
 473     .priv_class     = &dvdsubenc_class,
 474     .priv_data_size = sizeof(DVDSubtitleContext),
 475 };