yading@10: /*
yading@10:  * DVD subtitle encoding
yading@10:  * Copyright (c) 2005 Wolfram Gloger
yading@10:  *
yading@10:  * This file is part of FFmpeg.
yading@10:  *
yading@10:  * FFmpeg is free software; you can redistribute it and/or
yading@10:  * modify it under the terms of the GNU Lesser General Public
yading@10:  * License as published by the Free Software Foundation; either
yading@10:  * version 2.1 of the License, or (at your option) any later version.
yading@10:  *
yading@10:  * FFmpeg is distributed in the hope that it will be useful,
yading@10:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
yading@10:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
yading@10:  * Lesser General Public License for more details.
yading@10:  *
yading@10:  * You should have received a copy of the GNU Lesser General Public
yading@10:  * License along with FFmpeg; if not, write to the Free Software
yading@10:  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
yading@10:  */
yading@10: #include "avcodec.h"
yading@10: #include "bytestream.h"
yading@10: #include "internal.h"
yading@10: #include "libavutil/avassert.h"
yading@10: #include "libavutil/bprint.h"
yading@10: #include "libavutil/imgutils.h"
yading@10: 
yading@10: typedef struct {
yading@10:     uint32_t global_palette[16];
yading@10: } DVDSubtitleContext;
yading@10: 
yading@10: // ncnt is the nibble counter
yading@10: #define PUTNIBBLE(val)\
yading@10: do {\
yading@10:     if (ncnt++ & 1)\
yading@10:         *q++ = bitbuf | ((val) & 0x0f);\
yading@10:     else\
yading@10:         bitbuf = (val) << 4;\
yading@10: } while(0)
yading@10: 
yading@10: static void dvd_encode_rle(uint8_t **pq,
yading@10:                            const uint8_t *bitmap, int linesize,
yading@10:                            int w, int h,
yading@10:                            const int cmap[256])
yading@10: {
yading@10:     uint8_t *q;
yading@10:     unsigned int bitbuf = 0;
yading@10:     int ncnt;
yading@10:     int x, y, len, color;
yading@10: 
yading@10:     q = *pq;
yading@10: 
yading@10:     for (y = 0; y < h; ++y) {
yading@10:         ncnt = 0;
yading@10:         for(x = 0; x < w; x += len) {
yading@10:             color = bitmap[x];
yading@10:             for (len=1; x+len < w; ++len)
yading@10:                 if (bitmap[x+len] != color)
yading@10:                     break;
yading@10:             color = cmap[color];
yading@10:             av_assert0(color < 4);
yading@10:             if (len < 0x04) {
yading@10:                 PUTNIBBLE((len << 2)|color);
yading@10:             } else if (len < 0x10) {
yading@10:                 PUTNIBBLE(len >> 2);
yading@10:                 PUTNIBBLE((len << 2)|color);
yading@10:             } else if (len < 0x40) {
yading@10:                 PUTNIBBLE(0);
yading@10:                 PUTNIBBLE(len >> 2);
yading@10:                 PUTNIBBLE((len << 2)|color);
yading@10:             } else if (x+len == w) {
yading@10:                 PUTNIBBLE(0);
yading@10:                 PUTNIBBLE(0);
yading@10:                 PUTNIBBLE(0);
yading@10:                 PUTNIBBLE(color);
yading@10:             } else {
yading@10:                 if (len > 0xff)
yading@10:                     len = 0xff;
yading@10:                 PUTNIBBLE(0);
yading@10:                 PUTNIBBLE(len >> 6);
yading@10:                 PUTNIBBLE(len >> 2);
yading@10:                 PUTNIBBLE((len << 2)|color);
yading@10:             }
yading@10:         }
yading@10:         /* end of line */
yading@10:         if (ncnt & 1)
yading@10:             PUTNIBBLE(0);
yading@10:         bitmap += linesize;
yading@10:     }
yading@10: 
yading@10:     *pq = q;
yading@10: }
yading@10: 
yading@10: static int color_distance(uint32_t a, uint32_t b)
yading@10: {
yading@10:     int r = 0, d, i;
yading@10:     int alpha_a = 8, alpha_b = 8;
yading@10: 
yading@10:     for (i = 24; i >= 0; i -= 8) {
yading@10:         d = alpha_a * (int)((a >> i) & 0xFF) -
yading@10:             alpha_b * (int)((b >> i) & 0xFF);
yading@10:         r += d * d;
yading@10:         alpha_a = a >> 28;
yading@10:         alpha_b = b >> 28;
yading@10:     }
yading@10:     return r;
yading@10: }
yading@10: 
yading@10: /**
yading@10:  * Count colors used in a rectangle, quantizing alpha and grouping by
yading@10:  * nearest global palette entry.
yading@10:  */
yading@10: static void count_colors(AVCodecContext *avctx, unsigned hits[33],
yading@10:                          const AVSubtitleRect *r)
yading@10: {
yading@10:     DVDSubtitleContext *dvdc = avctx->priv_data;
yading@10:     unsigned count[256] = { 0 };
yading@10:     uint32_t *palette = (uint32_t *)r->pict.data[1];
yading@10:     uint32_t color;
yading@10:     int x, y, i, j, match, d, best_d, av_uninit(best_j);
yading@10:     uint8_t *p = r->pict.data[0];
yading@10: 
yading@10:     for (y = 0; y < r->h; y++) {
yading@10:         for (x = 0; x < r->w; x++)
yading@10:             count[*(p++)]++;
yading@10:         p += r->pict.linesize[0] - r->w;
yading@10:     }
yading@10:     for (i = 0; i < 256; i++) {
yading@10:         if (!count[i]) /* avoid useless search */
yading@10:             continue;
yading@10:         color = palette[i];
yading@10:         /* 0: transparent, 1-16: semi-transparent, 17-33 opaque */
yading@10:         match = color < 0x33000000 ? 0 : color < 0xCC000000 ? 1 : 17;
yading@10:         if (match) {
yading@10:             best_d = INT_MAX;
yading@10:             for (j = 0; j < 16; j++) {
yading@10:                 d = color_distance(0xFF000000 | color,
yading@10:                                    0xFF000000 | dvdc->global_palette[j]);
yading@10:                 if (d < best_d) {
yading@10:                     best_d = d;
yading@10:                     best_j = j;
yading@10:                 }
yading@10:             }
yading@10:             match += best_j;
yading@10:         }
yading@10:         hits[match] += count[i];
yading@10:     }
yading@10: }
yading@10: 
yading@10: static void select_palette(AVCodecContext *avctx, int out_palette[4],
yading@10:                            int out_alpha[4], unsigned hits[33])
yading@10: {
yading@10:     DVDSubtitleContext *dvdc = avctx->priv_data;
yading@10:     int i, j, bright, mult;
yading@10:     uint32_t color;
yading@10:     int selected[4] = { 0 };
yading@10:     uint32_t pseudopal[33] = { 0 };
yading@10:     uint32_t refcolor[3] = { 0x00000000, 0xFFFFFFFF, 0xFF000000 };
yading@10: 
yading@10:     /* Bonus for transparent: if the rectangle fits tightly the text, the
yading@10:        background color can be quite rare, but it would be ugly without it */
yading@10:     hits[0] *= 16;
yading@10:     /* Bonus for bright colors */
yading@10:     for (i = 0; i < 16; i++) {
yading@10:         if (!(hits[1 + i] + hits[17 + i]))
yading@10:             continue; /* skip unused colors to gain time */
yading@10:         color = dvdc->global_palette[i];
yading@10:         bright = 0;
yading@10:         for (j = 0; j < 3; j++, color >>= 8)
yading@10:             bright += (color & 0xFF) < 0x40 || (color & 0xFF) >= 0xC0;
yading@10:         mult = 2 + FFMIN(bright, 2);
yading@10:         hits[ 1 + i] *= mult;
yading@10:         hits[17 + i] *= mult;
yading@10:     }
yading@10: 
yading@10:     /* Select four most frequent colors */
yading@10:     for (i = 0; i < 4; i++) {
yading@10:         for (j = 0; j < 33; j++)
yading@10:             if (hits[j] > hits[selected[i]])
yading@10:                 selected[i] = j;
yading@10:         hits[selected[i]] = 0;
yading@10:     }
yading@10: 
yading@10:     /* Order the colors like in most DVDs:
yading@10:        0: background, 1: foreground, 2: outline */
yading@10:     for (i = 0; i < 16; i++) {
yading@10:         pseudopal[ 1 + i] = 0x80000000 | dvdc->global_palette[i];
yading@10:         pseudopal[17 + i] = 0xFF000000 | dvdc->global_palette[i];
yading@10:     }
yading@10:     for (i = 0; i < 3; i++) {
yading@10:         int best_d = color_distance(refcolor[i], pseudopal[selected[i]]);
yading@10:         for (j = i + 1; j < 4; j++) {
yading@10:             int d = color_distance(refcolor[i], pseudopal[selected[j]]);
yading@10:             if (d < best_d) {
yading@10:                 FFSWAP(int, selected[i], selected[j]);
yading@10:                 best_d = d;
yading@10:             }
yading@10:         }
yading@10:     }
yading@10: 
yading@10:     /* Output */
yading@10:     for (i = 0; i < 4; i++) {
yading@10:         out_palette[i] = selected[i] ? (selected[i] - 1) & 0xF : 0;
yading@10:         out_alpha  [i] = !selected[i] ? 0 : selected[i] < 17 ? 0x80 : 0xFF;
yading@10:     }
yading@10: }
yading@10: 
yading@10: static void build_color_map(AVCodecContext *avctx, int cmap[],
yading@10:                             const uint32_t palette[],
yading@10:                             const int out_palette[], unsigned int const out_alpha[])
yading@10: {
yading@10:     DVDSubtitleContext *dvdc = avctx->priv_data;
yading@10:     int i, j, d, best_d;
yading@10:     uint32_t pseudopal[4];
yading@10: 
yading@10:     for (i = 0; i < 4; i++)
yading@10:         pseudopal[i] = (out_alpha[i] << 24) |
yading@10:                        dvdc->global_palette[out_palette[i]];
yading@10:     for (i = 0; i < 256; i++) {
yading@10:         best_d = INT_MAX;
yading@10:         for (j = 0; j < 4; j++) {
yading@10:             d = color_distance(pseudopal[j], palette[i]);
yading@10:             if (d < best_d) {
yading@10:                 cmap[i] = j;
yading@10:                 best_d = d;
yading@10:             }
yading@10:         }
yading@10:     }
yading@10: }
yading@10: 
yading@10: static void copy_rectangle(AVSubtitleRect *dst, AVSubtitleRect *src, int cmap[])
yading@10: {
yading@10:     int x, y;
yading@10:     uint8_t *p, *q;
yading@10: 
yading@10:     p = src->pict.data[0];
yading@10:     q = dst->pict.data[0] + (src->x - dst->x) +
yading@10:                             (src->y - dst->y) * dst->pict.linesize[0];
yading@10:     for (y = 0; y < src->h; y++) {
yading@10:         for (x = 0; x < src->w; x++)
yading@10:             *(q++) = cmap[*(p++)];
yading@10:         p += src->pict.linesize[0] - src->w;
yading@10:         q += dst->pict.linesize[0] - src->w;
yading@10:     }
yading@10: }
yading@10: 
yading@10: static int encode_dvd_subtitles(AVCodecContext *avctx,
yading@10:                                 uint8_t *outbuf, int outbuf_size,
yading@10:                                 const AVSubtitle *h)
yading@10: {
yading@10:     DVDSubtitleContext *dvdc = avctx->priv_data;
yading@10:     uint8_t *q, *qq;
yading@10:     int offset1, offset2;
yading@10:     int i, rects = h->num_rects, ret;
yading@10:     unsigned global_palette_hits[33] = { 0 };
yading@10:     int cmap[256];
yading@10:     int out_palette[4];
yading@10:     int out_alpha[4];
yading@10:     AVSubtitleRect vrect;
yading@10:     uint8_t *vrect_data = NULL;
yading@10:     int x2, y2;
yading@10: 
yading@10:     if (rects == 0 || h->rects == NULL)
yading@10:         return AVERROR(EINVAL);
yading@10:     for (i = 0; i < rects; i++)
yading@10:         if (h->rects[i]->type != SUBTITLE_BITMAP) {
yading@10:             av_log(avctx, AV_LOG_ERROR, "Bitmap subtitle required\n");
yading@10:             return AVERROR(EINVAL);
yading@10:         }
yading@10:     vrect = *h->rects[0];
yading@10: 
yading@10:     if (rects > 1) {
yading@10:         /* DVD subtitles can have only one rectangle: build a virtual
yading@10:            rectangle containing all actual rectangles.
yading@10:            The data of the rectangles will be copied later, when the palette
yading@10:            is decided, because the rectangles may have different palettes. */
yading@10:         int xmin = h->rects[0]->x, xmax = xmin + h->rects[0]->w;
yading@10:         int ymin = h->rects[0]->y, ymax = ymin + h->rects[0]->h;
yading@10:         for (i = 1; i < rects; i++) {
yading@10:             xmin = FFMIN(xmin, h->rects[i]->x);
yading@10:             ymin = FFMIN(ymin, h->rects[i]->y);
yading@10:             xmax = FFMAX(xmax, h->rects[i]->x + h->rects[i]->w);
yading@10:             ymax = FFMAX(ymax, h->rects[i]->y + h->rects[i]->h);
yading@10:         }
yading@10:         vrect.x = xmin;
yading@10:         vrect.y = ymin;
yading@10:         vrect.w = xmax - xmin;
yading@10:         vrect.h = ymax - ymin;
yading@10:         if ((ret = av_image_check_size(vrect.w, vrect.h, 0, avctx)) < 0)
yading@10:             return ret;
yading@10: 
yading@10:         /* Count pixels outside the virtual rectangle as transparent */
yading@10:         global_palette_hits[0] = vrect.w * vrect.h;
yading@10:         for (i = 0; i < rects; i++)
yading@10:             global_palette_hits[0] -= h->rects[i]->w * h->rects[i]->h;
yading@10:     }
yading@10: 
yading@10:     for (i = 0; i < rects; i++)
yading@10:         count_colors(avctx, global_palette_hits, h->rects[i]);
yading@10:     select_palette(avctx, out_palette, out_alpha, global_palette_hits);
yading@10: 
yading@10:     if (rects > 1) {
yading@10:         if (!(vrect_data = av_calloc(vrect.w, vrect.h)))
yading@10:             return AVERROR(ENOMEM);
yading@10:         vrect.pict.data    [0] = vrect_data;
yading@10:         vrect.pict.linesize[0] = vrect.w;
yading@10:         for (i = 0; i < rects; i++) {
yading@10:             build_color_map(avctx, cmap, (uint32_t *)h->rects[i]->pict.data[1],
yading@10:                             out_palette, out_alpha);
yading@10:             copy_rectangle(&vrect, h->rects[i], cmap);
yading@10:         }
yading@10:         for (i = 0; i < 4; i++)
yading@10:             cmap[i] = i;
yading@10:     } else {
yading@10:         build_color_map(avctx, cmap, (uint32_t *)h->rects[0]->pict.data[1],
yading@10:                         out_palette, out_alpha);
yading@10:     }
yading@10: 
yading@10:     av_log(avctx, AV_LOG_DEBUG, "Selected palette:");
yading@10:     for (i = 0; i < 4; i++)
yading@10:         av_log(avctx, AV_LOG_DEBUG, " 0x%06x@@%02x (0x%x,0x%x)",
yading@10:                dvdc->global_palette[out_palette[i]], out_alpha[i],
yading@10:                out_palette[i], out_alpha[i] >> 4);
yading@10:     av_log(avctx, AV_LOG_DEBUG, "\n");
yading@10: 
yading@10:     // encode data block
yading@10:     q = outbuf + 4;
yading@10:     offset1 = q - outbuf;
yading@10:     // worst case memory requirement: 1 nibble per pixel..
yading@10:     if ((q - outbuf) + vrect.w * vrect.h / 2 + 17 + 21 > outbuf_size) {
yading@10:         av_log(NULL, AV_LOG_ERROR, "dvd_subtitle too big\n");
yading@10:         ret = AVERROR_BUFFER_TOO_SMALL;
yading@10:         goto fail;
yading@10:     }
yading@10:     dvd_encode_rle(&q, vrect.pict.data[0], vrect.w * 2,
yading@10:                    vrect.w, (vrect.h + 1) >> 1, cmap);
yading@10:     offset2 = q - outbuf;
yading@10:     dvd_encode_rle(&q, vrect.pict.data[0] + vrect.w, vrect.w * 2,
yading@10:                    vrect.w, vrect.h >> 1, cmap);
yading@10: 
yading@10:     // set data packet size
yading@10:     qq = outbuf + 2;
yading@10:     bytestream_put_be16(&qq, q - outbuf);
yading@10: 
yading@10:     // send start display command
yading@10:     bytestream_put_be16(&q, (h->start_display_time*90) >> 10);
yading@10:     bytestream_put_be16(&q, (q - outbuf) /*- 2 */ + 8 + 12 + 2);
yading@10:     *q++ = 0x03; // palette - 4 nibbles
yading@10:     *q++ = (out_palette[3] << 4) | out_palette[2];
yading@10:     *q++ = (out_palette[1] << 4) | out_palette[0];
yading@10:     *q++ = 0x04; // alpha - 4 nibbles
yading@10:     *q++ = (out_alpha[3] & 0xF0) | (out_alpha[2] >> 4);
yading@10:     *q++ = (out_alpha[1] & 0xF0) | (out_alpha[0] >> 4);
yading@10: 
yading@10:     // 12 bytes per rect
yading@10:     x2 = vrect.x + vrect.w - 1;
yading@10:     y2 = vrect.y + vrect.h - 1;
yading@10: 
yading@10:     *q++ = 0x05;
yading@10:     // x1 x2 -> 6 nibbles
yading@10:     *q++ = vrect.x >> 4;
yading@10:     *q++ = (vrect.x << 4) | ((x2 >> 8) & 0xf);
yading@10:     *q++ = x2;
yading@10:     // y1 y2 -> 6 nibbles
yading@10:     *q++ = vrect.y >> 4;
yading@10:     *q++ = (vrect.y << 4) | ((y2 >> 8) & 0xf);
yading@10:     *q++ = y2;
yading@10: 
yading@10:     *q++ = 0x06;
yading@10:     // offset1, offset2
yading@10:     bytestream_put_be16(&q, offset1);
yading@10:     bytestream_put_be16(&q, offset2);
yading@10: 
yading@10:     *q++ = 0x01; // start command
yading@10:     *q++ = 0xff; // terminating command
yading@10: 
yading@10:     // send stop display command last
yading@10:     bytestream_put_be16(&q, (h->end_display_time*90) >> 10);
yading@10:     bytestream_put_be16(&q, (q - outbuf) - 2 /*+ 4*/);
yading@10:     *q++ = 0x02; // set end
yading@10:     *q++ = 0xff; // terminating command
yading@10: 
yading@10:     qq = outbuf;
yading@10:     bytestream_put_be16(&qq, q - outbuf);
yading@10: 
yading@10:     av_log(NULL, AV_LOG_DEBUG, "subtitle_packet size=%td\n", q - outbuf);
yading@10:     ret = q - outbuf;
yading@10: 
yading@10: fail:
yading@10:     av_free(vrect_data);
yading@10:     return ret;
yading@10: }
yading@10: 
yading@10: static int dvdsub_init(AVCodecContext *avctx)
yading@10: {
yading@10:     DVDSubtitleContext *dvdc = avctx->priv_data;
yading@10:     static const uint32_t default_palette[16] = {
yading@10:         0x000000, 0x0000FF, 0x00FF00, 0xFF0000,
yading@10:         0xFFFF00, 0xFF00FF, 0x00FFFF, 0xFFFFFF,
yading@10:         0x808000, 0x8080FF, 0x800080, 0x80FF80,
yading@10:         0x008080, 0xFF8080, 0x555555, 0xAAAAAA,
yading@10:     };
yading@10:     AVBPrint extradata;
yading@10:     int i, ret;
yading@10: 
yading@10:     av_assert0(sizeof(dvdc->global_palette) == sizeof(default_palette));
yading@10:     memcpy(dvdc->global_palette, default_palette, sizeof(dvdc->global_palette));
yading@10: 
yading@10:     av_bprint_init(&extradata, 0, 1);
yading@10:     if (avctx->width && avctx->height)
yading@10:         av_bprintf(&extradata, "size: %dx%d\n", avctx->width, avctx->height);
yading@10:     av_bprintf(&extradata, "palette:");
yading@10:     for (i = 0; i < 16; i++)
yading@10:         av_bprintf(&extradata, " %06"PRIx32"%c",
yading@10:                    dvdc->global_palette[i] & 0xFFFFFF, i < 15 ? ',' : '\n');
yading@10: 
yading@10:     ret = avpriv_bprint_to_extradata(avctx, &extradata);
yading@10:     if (ret < 0)
yading@10:         return ret;
yading@10: 
yading@10:     return 0;
yading@10: }
yading@10: 
yading@10: static int dvdsub_encode(AVCodecContext *avctx,
yading@10:                          unsigned char *buf, int buf_size,
yading@10:                          const AVSubtitle *sub)
yading@10: {
yading@10:     //DVDSubtitleContext *s = avctx->priv_data;
yading@10:     int ret;
yading@10: 
yading@10:     ret = encode_dvd_subtitles(avctx, buf, buf_size, sub);
yading@10:     return ret;
yading@10: }
yading@10: 
yading@10: AVCodec ff_dvdsub_encoder = {
yading@10:     .name           = "dvdsub",
yading@10:     .type           = AVMEDIA_TYPE_SUBTITLE,
yading@10:     .id             = AV_CODEC_ID_DVD_SUBTITLE,
yading@10:     .init           = dvdsub_init,
yading@10:     .encode_sub     = dvdsub_encode,
yading@10:     .long_name      = NULL_IF_CONFIG_SMALL("DVD subtitles"),
yading@10:     .priv_data_size = sizeof(DVDSubtitleContext),
yading@10: };