vo_vdpau: split bitmap packing code into a separate file

Split the vo_vdpau code that calculates how to pack all subtitle
bitmaps into a larger surface into a separate file. This will allow
using it in other VOs.

Conflicts:
	Makefile
	libvo/vo_vdpau.c

Note: this commit does the same as an earlier commit by me
(4010dd0b1a27e3996). My commit added the vo_vdpau packer code as
eosd_packer.c, while this commit by uau uses bitmap_packer.c. Since
bitmap_packer.c has a different interface, and because there are more
commits changing OSD rendering coming, I will pick uau's version.
However, vo_gl, vo_gl3 and vo_direct3d are still using eosd_packer.c,
so to make the transition easier, don't delete eosd_packer.c yet.

1 files changed, 174 insertions, 0 deletions

diff --git a/libvo/bitmap_packer.c b/libvo/bitmap_packer.c
new file mode 100644
index 0000000000..2ae8a1eee0
--- /dev/null
+++ b/libvo/bitmap_packer.c
@@ -0,0 +1,174 @@
+/*
+ * Calculate how to pack bitmap rectangles into a larger surface
+ *
+ * Copyright 2009, 2012 Uoti Urpala
+ *
+ * This file is part of mplayer2.
+ *
+ * mplayer2 is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * mplayer2 is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with mplayer2.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include <stdlib.h>
+
+#include <libavutil/common.h>
+
+#include "talloc.h"
+#include "bitmap_packer.h"
+#include "mp_msg.h"
+#include "mpcommon.h"
+#include "sub/ass_mp.h"
+
+
+#define HEIGHT_SORT_BITS 4
+static int size_index(int s)
+{
+    int n = av_log2_16bit(s);
+    return (n << HEIGHT_SORT_BITS)
+       + (- 1 - (s << HEIGHT_SORT_BITS >> n) & (1 << HEIGHT_SORT_BITS) - 1);
+}
+
+/* Pack the given rectangles into an area of size w * h.
+ * The size of each rectangle is read from in[i].x / in[i].y.
+ * The height of each rectangle must be less than 65536.
+ * 'scratch' must point to work memory for num_rects+16 ints.
+ * The packed position for rectangle number i is set in out[i].
+ * Return 0 on success, -1 if the rectangles did not fit in w*h.
+ *
+ * The rectangles are placed in rows in order approximately sorted by
+ * height (the approximate sorting is simpler than a full one would be,
+ * and allows the algorithm to work in linear time). Additionally, to
+ * reduce wasted space when there are a few tall rectangles, empty
+ * lower-right parts of rows are filled recursively when the size of
+ * rectangles in the row drops past a power-of-two threshold. So if a
+ * row starts with rectangles of size 3x50, 10x40 and 5x20 then the
+ * free rectangle with corners (13, 20)-(w, 50) is filled recursively.
+ */
+static int pack_rectangles(struct pos *in, struct pos *out, int num_rects,
+                           int w, int h, int *scratch)
+{
+    int bins[16 << HEIGHT_SORT_BITS];
+    int sizes[16 << HEIGHT_SORT_BITS] = { 0 };
+    for (int i = 0; i < num_rects; i++)
+        sizes[size_index(in[i].y)]++;
+    int idx = 0;
+    for (int i = 0; i < 16 << HEIGHT_SORT_BITS; i += 1 << HEIGHT_SORT_BITS) {
+        for (int j = 0; j < 1 << HEIGHT_SORT_BITS; j++) {
+            bins[i + j] = idx;
+            idx += sizes[i + j];
+        }
+        scratch[idx++] = -1;
+    }
+    for (int i = 0; i < num_rects; i++)
+        scratch[bins[size_index(in[i].y)]++] = i;
+    for (int i = 0; i < 16; i++)
+        bins[i] = bins[i << HEIGHT_SORT_BITS] - sizes[i << HEIGHT_SORT_BITS];
+    struct {
+        int size, x, bottom;
+    } stack[16] = {{15, 0, h}}, s = {};
+    int stackpos = 1;
+    int y;
+    while (stackpos) {
+        y = s.bottom;
+        s = stack[--stackpos];
+        s.size++;
+        while (s.size--) {
+            int maxy = -1;
+            int obj;
+            while ((obj = scratch[bins[s.size]]) >= 0) {
+                int bottom = y + in[obj].y;
+                if (bottom > s.bottom)
+                    break;
+                int right = s.x + in[obj].x;
+                if (right > w)
+                    break;
+                bins[s.size]++;
+                out[obj] = (struct pos){s.x, y};
+                num_rects--;
+                if (maxy < 0)
+                    stack[stackpos++] = s;
+                s.x = right;
+                maxy = FFMAX(maxy, bottom);
+            }
+            if (maxy > 0)
+                s.bottom = maxy;
+        }
+    }
+    return num_rects ? -1 : 0;
+}
+
+int packer_pack(struct bitmap_packer *packer)
+{
+    if (packer->count == 0)
+        return 0;
+    int w_orig = packer->w, h_orig = packer->h;
+    struct pos *in = packer->in;
+    int xmax = 0, ymax = 0;
+    for (int i = 0; i < packer->count; i++) {
+        if (in[i].x == 0 || in[i].y == 0)
+            in[i] = (struct pos){0, 0};
+        if (in[i].x < 0 || in [i].x > 65535 || in[i].y < 0 || in[i].y > 65535) {
+            mp_msg(MSGT_VO, MSGL_FATAL, "Invalid OSD / subtitle bitmap size\n");
+            abort();
+        }
+        xmax = FFMAX(xmax, in[i].x);
+        ymax = FFMAX(ymax, in[i].y);
+    }
+    if (xmax > packer->w)
+        packer->w = 1 << av_log2(xmax - 1) + 1;
+    if (ymax > packer->h)
+        packer->h = 1 << av_log2(ymax - 1) + 1;
+    while (1) {
+        if (pack_rectangles(in, packer->result, packer->count, packer->w,
+                            packer->h, packer->scratch) >= 0)
+            return packer->w != w_orig || packer->h != h_orig;
+        if (packer->w <= packer->h && packer->w != packer->w_max)
+            packer->w = FFMIN(packer->w * 2, packer->w_max);
+        else if (packer->h != packer->h_max)
+            packer->h = FFMIN(packer->h * 2, packer->h_max);
+        else
+            return -1;
+    }
+}
+
+void packer_set_size(struct bitmap_packer *packer, int size)
+{
+    packer->count = size;
+    if (size <= packer->asize)
+        return;
+    packer->asize = FFMAX(packer->asize * 2, size);
+    talloc_free(packer->result);
+    talloc_free(packer->scratch);
+    packer->in = talloc_realloc(packer, packer->in, struct pos, packer->asize);
+    packer->result = talloc_array_ptrtype(packer, packer->result,
+                                          packer->asize);
+    packer->scratch = talloc_array_ptrtype(packer, packer->scratch,
+                                           packer->asize + 16);
+}
+
+int packer_pack_from_assimg(struct bitmap_packer *packer,
+                            struct ass_image *imglist)
+{
+    int count = 0;
+    struct ass_image *img = imglist;
+    while (img) {
+        if (count >= packer->asize)
+            packer_set_size(packer, FFMAX(packer->asize * 2, 32));
+        packer->in[count].x = img->w;
+        packer->in[count].y = img->h;
+        img = img->next;
+        count++;
+    }
+    packer->count = count;
+    return packer_pack(packer);
+}