git.sesse.net Git - ffmpeg/blob - 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     .long_name      = NULL_IF_CONFIG_SMALL("DVD subtitles"),
 438     .type           = AVMEDIA_TYPE_SUBTITLE,
 439     .id             = AV_CODEC_ID_DVD_SUBTITLE,
 440     .init           = dvdsub_init,
 441     .encode_sub     = dvdsub_encode,
 442     .priv_data_size = sizeof(DVDSubtitleContext),
 443 };