libvo/bitmap_packer.c

   1 /*
   2  * Calculate how to pack bitmap rectangles into a larger surface
   3  *
   4  * Copyright 2009, 2012 Uoti Urpala
   5  *
   6  * This file is part of mplayer2.
   7  *
   8  * mplayer2 is free software; you can redistribute it and/or modify
   9  * it under the terms of the GNU General Public License as published by
  10  * the Free Software Foundation; either version 2 of the License, or
  11  * (at your option) any later version.
  12  *
  13  * mplayer2 is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  * GNU General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU General Public License along
  19  * with mplayer2.  If not, see <http://www.gnu.org/licenses/>.
  20  */
  21
  22 #include <stdlib.h>
  23
  24 #include <libavutil/common.h>
  25
  26 #include "talloc.h"
  27 #include "bitmap_packer.h"
  28 #include "mp_msg.h"
  29 #include "mpcommon.h"
  30 #include "sub/ass_mp.h"
  31 #include "sub/dec_sub.h"
  32
  33
  34 #define HEIGHT_SORT_BITS 4
  35 static int size_index(int s)
  36 {
  37     int n = av_log2_16bit(s);
  38     return (n << HEIGHT_SORT_BITS)
  39        + (- 1 - (s << HEIGHT_SORT_BITS >> n) & (1 << HEIGHT_SORT_BITS) - 1);
  40 }
  41
  42 /* Pack the given rectangles into an area of size w * h.
  43  * The size of each rectangle is read from in[i].x / in[i].y.
  44  * The height of each rectangle must be less than 65536.
  45  * 'scratch' must point to work memory for num_rects+16 ints.
  46  * The packed position for rectangle number i is set in out[i].
  47  * Return 0 on success, -1 if the rectangles did not fit in w*h.
  48  *
  49  * The rectangles are placed in rows in order approximately sorted by
  50  * height (the approximate sorting is simpler than a full one would be,
  51  * and allows the algorithm to work in linear time). Additionally, to
  52  * reduce wasted space when there are a few tall rectangles, empty
  53  * lower-right parts of rows are filled recursively when the size of
  54  * rectangles in the row drops past a power-of-two threshold. So if a
  55  * row starts with rectangles of size 3x50, 10x40 and 5x20 then the
  56  * free rectangle with corners (13, 20)-(w, 50) is filled recursively.
  57  */
  58 static int pack_rectangles(struct pos *in, struct pos *out, int num_rects,
  59                            int w, int h, int *scratch, int *used_width)
  60 {
  61     int bins[16 << HEIGHT_SORT_BITS];
  62     int sizes[16 << HEIGHT_SORT_BITS] = { 0 };
  63     for (int i = 0; i < num_rects; i++)
  64         sizes[size_index(in[i].y)]++;
  65     int idx = 0;
  66     for (int i = 0; i < 16 << HEIGHT_SORT_BITS; i += 1 << HEIGHT_SORT_BITS) {
  67         for (int j = 0; j < 1 << HEIGHT_SORT_BITS; j++) {
  68             bins[i + j] = idx;
  69             idx += sizes[i + j];
  70         }
  71         scratch[idx++] = -1;
  72     }
  73     for (int i = 0; i < num_rects; i++)
  74         scratch[bins[size_index(in[i].y)]++] = i;
  75     for (int i = 0; i < 16; i++)
  76         bins[i] = bins[i << HEIGHT_SORT_BITS] - sizes[i << HEIGHT_SORT_BITS];
  77     struct {
  78         int size, x, bottom;
  79     } stack[16] = {{15, 0, h}}, s = {};
  80     int stackpos = 1;
  81     int y;
  82     while (stackpos) {
  83         y = s.bottom;
  84         s = stack[--stackpos];
  85         s.size++;
  86         while (s.size--) {
  87             int maxy = -1;
  88             int obj;
  89             while ((obj = scratch[bins[s.size]]) >= 0) {
  90                 int bottom = y + in[obj].y;
  91                 if (bottom > s.bottom)
  92                     break;
  93                 int right = s.x + in[obj].x;
  94                 if (right > w)
  95                     break;
  96                 bins[s.size]++;
  97                 out[obj] = (struct pos){s.x, y};
  98                 num_rects--;
  99                 if (maxy < 0)
 100                     stack[stackpos++] = s;
 101                 s.x = right;
 102                 maxy = FFMAX(maxy, bottom);
 103             }
 104             *used_width = FFMAX(*used_width, s.x);
 105             if (maxy > 0)
 106                 s.bottom = maxy;
 107         }
 108     }
 109     return num_rects ? -1 : y;
 110 }
 111
 112 int packer_pack(struct bitmap_packer *packer)
 113 {
 114     if (packer->count == 0)
 115         return 0;
 116     int w_orig = packer->w, h_orig = packer->h;
 117     struct pos *in = packer->in;
 118     int xmax = 0, ymax = 0;
 119     for (int i = 0; i < packer->count; i++) {
 120         if (in[i].x <= packer->padding || in[i].y <= packer->padding)
 121             in[i] = (struct pos){0, 0};
 122         if (in[i].x < 0 || in [i].x > 65535 || in[i].y < 0 || in[i].y > 65535) {
 123             mp_msg(MSGT_VO, MSGL_FATAL, "Invalid OSD / subtitle bitmap size\n");
 124             abort();
 125         }
 126         xmax = FFMAX(xmax, in[i].x);
 127         ymax = FFMAX(ymax, in[i].y);
 128     }
 129     xmax = FFMAX(0, xmax - packer->padding);
 130     ymax = FFMAX(0, ymax - packer->padding);
 131     if (xmax > packer->w)
 132         packer->w = 1 << av_log2(xmax - 1) + 1;
 133     if (ymax > packer->h)
 134         packer->h = 1 << av_log2(ymax - 1) + 1;
 135     while (1) {
 136         int used_width = 0;
 137         int y = pack_rectangles(in, packer->result, packer->count,
 138                                 packer->w + packer->padding,
 139                                 packer->h + packer->padding,
 140                                 packer->scratch, &used_width);
 141         if (y >= 0) {
 142             // No padding at edges
 143             packer->used_width = FFMIN(used_width, packer->w);
 144             packer->used_height = FFMIN(y, packer->h);
 145             return packer->w != w_orig || packer->h != h_orig;
 146         }
 147         if (packer->w <= packer->h && packer->w != packer->w_max)
 148             packer->w = FFMIN(packer->w * 2, packer->w_max);
 149         else if (packer->h != packer->h_max)
 150             packer->h = FFMIN(packer->h * 2, packer->h_max);
 151         else {
 152             packer->w = w_orig;
 153             packer->h = h_orig;
 154             return -1;
 155         }
 156     }
 157 }
 158
 159 void packer_set_size(struct bitmap_packer *packer, int size)
 160 {
 161     packer->count = size;
 162     if (size <= packer->asize)
 163         return;
 164     packer->asize = FFMAX(packer->asize * 2, size);
 165     talloc_free(packer->result);
 166     talloc_free(packer->scratch);
 167     packer->in = talloc_realloc(packer, packer->in, struct pos, packer->asize);
 168     packer->result = talloc_array_ptrtype(packer, packer->result,
 169                                           packer->asize);
 170     packer->scratch = talloc_array_ptrtype(packer, packer->scratch,
 171                                            packer->asize + 16);
 172 }
 173
 174 static int packer_pack_from_assimg(struct bitmap_packer *packer,
 175                                    struct ass_image *imglist)
 176 {
 177     int count = 0;
 178     struct ass_image *img = imglist;
 179     while (img) {
 180         if (count >= packer->asize)
 181             packer_set_size(packer, FFMAX(packer->asize * 2, 32));
 182         packer->in[count].x = img->w;
 183         packer->in[count].y = img->h;
 184         img = img->next;
 185         count++;
 186     }
 187     packer->count = count;
 188     return packer_pack(packer);
 189 }
 190
 191 int packer_pack_from_subbitmaps(struct bitmap_packer *packer,
 192                                 struct sub_bitmaps *b, int padding_pixels)
 193 {
 194     packer->padding = 0;
 195     packer->count = 0;
 196     if (b->type == SUBBITMAP_EMPTY)
 197         return 0;
 198     if (b->type == SUBBITMAP_LIBASS)
 199         return packer_pack_from_assimg(packer, b->imgs);
 200     packer->padding = padding_pixels;
 201     packer_set_size(packer, b->part_count);
 202     int a = packer->padding;
 203     for (int i = 0; i < b->part_count; i++)
 204         packer->in[i] = (struct pos){b->parts[i].w + a, b->parts[i].h + a};
 205     return packer_pack(packer);
 206 }