Something went wrong. Try again.
🎥 Command line media player
Something went wrong. Try again.
C
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198/* * Calculate how to pack bitmap rectangles into a larger surface * * Copyright 2009, 2012 Uoti Urpala * * This file is part of mpv. * * mpv is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public * License as published by the Free Software Foundation; either * version 2.1 of the License, or (at your option) any later version. * * mpv 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 Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with mpv. If not, see <http://www.gnu.org/licenses/>. */
#include <stdlib.h>#include <assert.h>#include <stdio.h>#include <limits.h>
#include "mpv_talloc.h"#include "bitmap_packer.h"#include "common/common.h"
#define IS_POWER_OF_2(x) (((x) > 0) && !(((x) - 1) & (x)))
void packer_reset(struct bitmap_packer *packer){ struct bitmap_packer old = *packer; *packer = (struct bitmap_packer) { .w_max = old.w_max, .h_max = old.h_max, }; talloc_free_children(packer);}
void packer_get_bb(struct bitmap_packer *packer, struct pos out_bb[2]){ out_bb[0] = (struct pos) {0}; out_bb[1] = (struct pos) {packer->used_width, packer->used_height};}
#define HEIGHT_SORT_BITS 4static int size_index(int s){ int n = mp_log2(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 *used_width){ 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 = {0}; 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 = MPMAX(maxy, bottom); } *used_width = MPMAX(*used_width, s.x); if (maxy > 0) s.bottom = maxy; } } return num_rects ? -1 : y;}
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}; } else { in[i].x += packer->padding * 2; in[i].y += packer->padding * 2; } if (in[i].x < 0 || in [i].x > 65535 || in[i].y < 0 || in[i].y > 65535) { fprintf(stderr, "Invalid OSD / subtitle bitmap size\n"); abort(); } xmax = MPMAX(xmax, in[i].x); ymax = MPMAX(ymax, in[i].y); } if (xmax > packer->w) packer->w = 1 << (mp_log2(xmax - 1) + 1); if (ymax > packer->h) packer->h = 1 << (mp_log2(ymax - 1) + 1); while (1) { int used_width = 0; int y = pack_rectangles(in, packer->result, packer->count, packer->w, packer->h, packer->scratch, &used_width); if (y >= 0) { packer->used_width = MPMIN(used_width, packer->w); packer->used_height = MPMIN(y, packer->h); assert(packer->w == 0 || IS_POWER_OF_2(packer->w)); assert(packer->h == 0 || IS_POWER_OF_2(packer->h)); if (packer->padding) { for (int i = 0; i < packer->count; i++) { packer->result[i].x += packer->padding; packer->result[i].y += packer->padding; } } return packer->w != w_orig || packer->h != h_orig; } int w_max = packer->w_max > 0 ? packer->w_max : INT_MAX; int h_max = packer->h_max > 0 ? packer->h_max : INT_MAX; if (packer->w <= packer->h && packer->w != w_max) packer->w = MPMIN(packer->w * 2, w_max); else if (packer->h != h_max) packer->h = MPMIN(packer->h * 2, h_max); else { packer->w = w_orig; packer->h = h_orig; return -1; } }}
void packer_set_size(struct bitmap_packer *packer, int size){ packer->count = size; if (size <= packer->asize) return; packer->asize = MPMAX(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);}