2 * Microsoft Screen 1 (aka Windows Media Video V7 Screen) decoder
3 * Copyright (c) 2012 Konstantin Shishkov
5 * This file is part of FFmpeg.
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.
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.
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
24 * Microsoft Screen 1 (aka Windows Media Video V7 Screen) decoder
27 #include "libavutil/intfloat.h"
28 #include "libavutil/intreadwrite.h"
38 typedef struct ArithCoder {
43 #define MODEL_MIN_SYMS 2
44 #define MODEL_MAX_SYMS 256
45 #define THRESH_ADAPTIVE -1
47 #define THRESH_HIGH 50
49 typedef struct Model {
50 int cum_prob[MODEL_MAX_SYMS + 1];
51 int weights[MODEL_MAX_SYMS + 1];
52 int idx2sym[MODEL_MAX_SYMS + 1];
53 int sym2idx[MODEL_MAX_SYMS + 1];
55 int thr_weight, threshold;
58 static const int sec_order_sizes[4] = { 1, 7, 6, 1 };
60 enum ContextDirection {
67 typedef struct PixContext {
68 int cache_size, num_syms;
70 Model cache_model, full_model;
71 Model sec_models[4][8][4];
74 typedef struct MSS1Context {
75 AVCodecContext *avctx;
83 Model intra_region, inter_region;
84 Model pivot, edge_mode, split_mode;
85 PixContext intra_pix_ctx, inter_pix_ctx;
89 static void arith_init(ArithCoder *c, GetBitContext *gb)
93 c->value = get_bits(gb, 16);
97 static void arith_normalise(ArithCoder *c)
100 if (c->high >= 0x8000) {
101 if (c->low < 0x8000) {
102 if (c->low >= 0x4000 && c->high < 0xC000) {
119 c->value |= get_bits1(c->gb);
123 static int arith_get_bit(ArithCoder *c)
125 int range = c->high - c->low + 1;
126 int bit = (((c->value - c->low) << 1) + 1) / range;
129 c->low += range >> 1;
131 c->high = c->low + (range >> 1) - 1;
138 static int arith_get_bits(ArithCoder *c, int bits)
140 int range = c->high - c->low + 1;
141 int val = (((c->value - c->low + 1) << bits) - 1) / range;
142 int prob = range * val;
144 c->high = ((prob + range) >> bits) + c->low - 1;
145 c->low += prob >> bits;
152 static int arith_get_number(ArithCoder *c, int mod_val)
154 int range = c->high - c->low + 1;
155 int val = ((c->value - c->low + 1) * mod_val - 1) / range;
156 int prob = range * val;
158 c->high = (prob + range) / mod_val + c->low - 1;
159 c->low += prob / mod_val;
166 static int arith_get_prob(ArithCoder *c, int *probs)
168 int range = c->high - c->low + 1;
169 int val = ((c->value - c->low + 1) * probs[0] - 1) / range;
172 while (probs[sym] > val)
175 c->high = range * probs[sym - 1] / probs[0] + c->low - 1;
176 c->low += range * probs[sym] / probs[0];
181 static int model_calc_threshold(Model *m)
185 if (m->thr_weight == -1) {
186 thr = 2 * m->weights[m->num_syms] - 1;
187 thr = ((thr >> 1) + 4 * m->cum_prob[0]) / thr;
189 thr = m->num_syms * m->thr_weight;
192 return FFMIN(thr, 0x3FFF);
195 static void model_reset(Model *m)
199 for (i = 0; i <= m->num_syms; i++) {
201 m->cum_prob[i] = m->num_syms - i;
205 m->sym2idx[m->num_syms] = -1;
206 for (i = 0; i < m->num_syms; i++) {
207 m->sym2idx[i] = i + 1;
208 m->idx2sym[i + 1] = i;
212 static av_cold void model_init(Model *m, int num_syms, int thr_weight)
214 m->num_syms = num_syms;
215 m->thr_weight = thr_weight;
216 m->threshold = model_calc_threshold(m);
220 static void model_rescale_weights(Model *m)
225 if (m->thr_weight == -1)
226 m->threshold = model_calc_threshold(m);
227 while (m->cum_prob[0] > m->threshold) {
229 for (i = m->num_syms; i >= 0; i--) {
230 m->cum_prob[i] = cum_prob;
231 m->weights[i] = (m->weights[i] + 1) >> 1;
232 cum_prob += m->weights[i];
237 static void model_update(Model *m, int val)
241 if (m->weights[val] == m->weights[val - 1]) {
242 for (i = val; m->weights[i - 1] == m->weights[val]; i--);
246 sym1 = m->idx2sym[val];
247 sym2 = m->idx2sym[i];
249 m->idx2sym[val] = sym2;
250 m->idx2sym[i] = sym1;
251 m->sym2idx[sym1] = i;
252 m->sym2idx[sym2] = val;
258 for (i = val - 1; i >= 0; i--)
260 model_rescale_weights(m);
263 static int arith_get_model_sym(ArithCoder *c, Model *m)
267 idx = arith_get_prob(c, m->cum_prob);
269 val = m->idx2sym[idx];
270 model_update(m, idx);
277 static void pixctx_reset(PixContext *ctx)
281 for (i = 0; i < ctx->cache_size; i++)
284 model_reset(&ctx->cache_model);
285 model_reset(&ctx->full_model);
287 for (i = 0; i < 4; i++)
288 for (j = 0; j < sec_order_sizes[i]; j++)
289 for (k = 0; k < 4; k++)
290 model_reset(&ctx->sec_models[i][j][k]);
293 static av_cold void pixctx_init(PixContext *ctx, int cache_size)
297 ctx->cache_size = cache_size + 4;
298 ctx->num_syms = cache_size;
300 for (i = 0; i < ctx->cache_size; i++)
303 model_init(&ctx->cache_model, ctx->num_syms + 1, THRESH_LOW);
304 model_init(&ctx->full_model, 256, THRESH_HIGH);
306 for (i = 0; i < 4; i++) {
307 for (j = 0; j < sec_order_sizes[i]; j++) {
308 for (k = 0; k < 4; k++) {
309 model_init(&ctx->sec_models[i][j][k], 2 + i,
310 i ? THRESH_LOW : THRESH_ADAPTIVE);
316 static int decode_top_left_pixel(ArithCoder *acoder, PixContext *pctx)
320 val = arith_get_model_sym(acoder, &pctx->cache_model);
321 if (val < pctx->num_syms) {
322 pix = pctx->cache[val];
324 pix = arith_get_model_sym(acoder, &pctx->full_model);
325 for (i = 0; i < pctx->cache_size - 1; i++)
326 if (pctx->cache[i] == pix)
331 for (i = val; i > 0; i--)
332 pctx->cache[i] = pctx->cache[i - 1];
333 pctx->cache[0] = pix;
339 static int decode_pixel(ArithCoder *acoder, PixContext *pctx,
340 uint8_t *ngb, int num_ngb)
344 val = arith_get_model_sym(acoder, &pctx->cache_model);
345 if (val < pctx->num_syms) {
350 for (i = 0; i < pctx->cache_size; i++) {
351 for (j = 0; j < num_ngb; j++)
352 if (pctx->cache[i] == ngb[j])
360 val = FFMIN(i, pctx->cache_size - 1);
361 pix = pctx->cache[val];
363 pix = arith_get_model_sym(acoder, &pctx->full_model);
364 for (i = 0; i < pctx->cache_size - 1; i++)
365 if (pctx->cache[i] == pix)
370 for (i = val; i > 0; i--)
371 pctx->cache[i] = pctx->cache[i - 1];
372 pctx->cache[0] = pix;
378 static int decode_pixel_in_context(ArithCoder *acoder, PixContext *pctx,
379 uint8_t *src, int stride, int x, int y,
382 uint8_t neighbours[4];
390 memset(neighbours, src[-1], 4);
392 neighbours[TOP] = src[-stride];
394 neighbours[TOP_LEFT] = neighbours[LEFT] = neighbours[TOP];
396 neighbours[TOP_LEFT] = src[-stride - 1];
397 neighbours[ LEFT] = src[-1];
400 neighbours[TOP_RIGHT] = src[-stride + 1];
402 neighbours[TOP_RIGHT] = neighbours[TOP];
406 if (x >= 2 && src[-2] == neighbours[LEFT])
408 if (y >= 2 && src[-2 * stride] == neighbours[TOP])
412 ref_pix[0] = neighbours[0];
413 for (i = 1; i < 4; i++) {
414 for (j = 0; j < nlen; j++)
415 if (ref_pix[j] == neighbours[i])
418 ref_pix[nlen++] = neighbours[i];
427 if (neighbours[TOP] == neighbours[TOP_LEFT]) {
428 if (neighbours[TOP_RIGHT] == neighbours[TOP_LEFT])
430 else if (neighbours[LEFT] == neighbours[TOP_LEFT])
434 } else if (neighbours[TOP_RIGHT] == neighbours[TOP_LEFT]) {
435 if (neighbours[LEFT] == neighbours[TOP_LEFT])
439 } else if (neighbours[LEFT] == neighbours[TOP_LEFT]) {
446 if (neighbours[TOP] == neighbours[TOP_LEFT])
448 else if (neighbours[TOP_RIGHT] == neighbours[TOP_LEFT])
450 else if (neighbours[LEFT] == neighbours[TOP_LEFT])
452 else if (neighbours[TOP_RIGHT] == neighbours[TOP])
454 else if (neighbours[TOP] == neighbours[LEFT])
461 pix = arith_get_model_sym(acoder, &pctx->sec_models[nlen - 1][layer][sub]);
465 return decode_pixel(acoder, pctx, ref_pix, nlen);
468 static int decode_region(MSS1Context *ctx, ArithCoder *acoder, uint8_t *dst,
469 int x, int y, int width, int height, int stride,
474 dst += x + y * stride;
476 dst[0] = decode_top_left_pixel(acoder, pctx);
477 for (j = 0; j < height; j++) {
478 for (i = 0; i < width; i++) {
482 dst[i] = decode_pixel_in_context(acoder, pctx, dst + i, stride,
483 i, j, width - i - 1);
491 static int decode_region_masked(MSS1Context *ctx, ArithCoder *acoder,
492 uint8_t *dst, int stride, uint8_t *mask,
493 int mask_stride, int x, int y,
494 int width, int height,
499 dst += x + y * stride;
500 mask += x + y * mask_stride;
503 dst[0] = decode_top_left_pixel(acoder, pctx);
504 for (j = 0; j < height; j++) {
505 for (i = 0; i < width; i++) {
506 if (!i && !j || mask[i] != 0xFF)
509 dst[i] = decode_pixel_in_context(acoder, pctx, dst + i, stride,
510 i, j, width - i - 1);
519 static av_cold void codec_init(MSS1Context *ctx)
521 model_init(&ctx->intra_region, 2, THRESH_ADAPTIVE);
522 model_init(&ctx->inter_region, 2, THRESH_ADAPTIVE);
523 model_init(&ctx->split_mode, 3, THRESH_HIGH);
524 model_init(&ctx->edge_mode, 2, THRESH_HIGH);
525 model_init(&ctx->pivot, 3, THRESH_LOW);
526 pixctx_init(&ctx->intra_pix_ctx, 8);
527 pixctx_init(&ctx->inter_pix_ctx, 2);
531 static void codec_reset(MSS1Context *ctx)
533 model_reset(&ctx->intra_region);
534 model_reset(&ctx->inter_region);
535 model_reset(&ctx->split_mode);
536 model_reset(&ctx->edge_mode);
537 model_reset(&ctx->pivot);
538 pixctx_reset(&ctx->intra_pix_ctx);
539 pixctx_reset(&ctx->inter_pix_ctx);
544 static int decode_pal(MSS1Context *ctx, ArithCoder *acoder)
546 int i, ncol, r, g, b;
547 uint32_t *pal = ctx->pal + 256 - ctx->free_colours;
549 if (!ctx->free_colours)
552 ncol = arith_get_number(acoder, ctx->free_colours + 1);
553 for (i = 0; i < ncol; i++) {
554 r = arith_get_bits(acoder, 8);
555 g = arith_get_bits(acoder, 8);
556 b = arith_get_bits(acoder, 8);
557 *pal++ = (0xFF << 24) | (r << 16) | (g << 8) | b;
563 static int decode_pivot(MSS1Context *ctx, ArithCoder *acoder, int base)
567 inv = arith_get_model_sym(acoder, &ctx->edge_mode);
568 val = arith_get_model_sym(acoder, &ctx->pivot) + 1;
571 if ((base + 1) / 2 - 2 <= 0) {
575 val = arith_get_number(acoder, (base + 1) / 2 - 2) + 3;
583 return inv ? base - val : val;
586 static int decode_region_intra(MSS1Context *ctx, ArithCoder *acoder,
587 int x, int y, int width, int height)
591 mode = arith_get_model_sym(acoder, &ctx->intra_region);
595 int stride = ctx->pic_stride;
596 uint8_t *dst = ctx->pic_start + x + y * stride;
598 pix = decode_top_left_pixel(acoder, &ctx->intra_pix_ctx);
599 for (i = 0; i < height; i++, dst += stride)
600 memset(dst, pix, width);
602 return decode_region(ctx, acoder, ctx->pic_start,
603 x, y, width, height, ctx->pic_stride,
604 &ctx->intra_pix_ctx);
610 static int decode_intra(MSS1Context *ctx, ArithCoder *acoder,
611 int x, int y, int width, int height)
618 mode = arith_get_model_sym(acoder, &ctx->split_mode);
622 pivot = decode_pivot(ctx, acoder, height);
625 if (decode_intra(ctx, acoder, x, y, width, pivot))
627 if (decode_intra(ctx, acoder, x, y + pivot, width, height - pivot))
631 pivot = decode_pivot(ctx, acoder, width);
634 if (decode_intra(ctx, acoder, x, y, pivot, height))
636 if (decode_intra(ctx, acoder, x + pivot, y, width - pivot, height))
640 return decode_region_intra(ctx, acoder, x, y, width, height);
648 static int decode_region_inter(MSS1Context *ctx, ArithCoder *acoder,
649 int x, int y, int width, int height)
653 mode = arith_get_model_sym(acoder, &ctx->inter_region);
656 mode = decode_top_left_pixel(acoder, &ctx->inter_pix_ctx);
660 return decode_region_intra(ctx, acoder, x, y, width, height);
663 if (decode_region(ctx, acoder, ctx->mask,
664 x, y, width, height, ctx->mask_linesize,
665 &ctx->inter_pix_ctx) < 0)
667 return decode_region_masked(ctx, acoder, ctx->pic_start,
668 -ctx->pic.linesize[0], ctx->mask,
671 &ctx->intra_pix_ctx);
677 static int decode_inter(MSS1Context *ctx, ArithCoder *acoder,
678 int x, int y, int width, int height)
685 mode = arith_get_model_sym(acoder, &ctx->split_mode);
689 pivot = decode_pivot(ctx, acoder, height);
690 if (decode_inter(ctx, acoder, x, y, width, pivot))
692 if (decode_inter(ctx, acoder, x, y + pivot, width, height - pivot))
696 pivot = decode_pivot(ctx, acoder, width);
697 if (decode_inter(ctx, acoder, x, y, pivot, height))
699 if (decode_inter(ctx, acoder, x + pivot, y, width - pivot, height))
703 return decode_region_inter(ctx, acoder, x, y, width, height);
711 static int mss1_decode_frame(AVCodecContext *avctx, void *data, int *data_size,
714 const uint8_t *buf = avpkt->data;
715 int buf_size = avpkt->size;
716 MSS1Context *c = avctx->priv_data;
722 init_get_bits(&gb, buf, buf_size * 8);
723 arith_init(&acoder, &gb);
725 c->pic.reference = 3;
726 c->pic.buffer_hints = FF_BUFFER_HINTS_VALID | FF_BUFFER_HINTS_PRESERVE |
727 FF_BUFFER_HINTS_REUSABLE;
728 if ((ret = avctx->reget_buffer(avctx, &c->pic)) < 0) {
729 av_log(avctx, AV_LOG_ERROR, "reget_buffer() failed\n");
733 c->pic_start = c->pic.data[0] + c->pic.linesize[0] * (avctx->height - 1);
734 c->pic_stride = -c->pic.linesize[0];
735 if (!arith_get_bit(&acoder)) {
737 pal_changed = decode_pal(c, &acoder);
738 c->corrupted = decode_intra(c, &acoder, 0, 0,
739 avctx->width, avctx->height);
740 c->pic.key_frame = 1;
741 c->pic.pict_type = AV_PICTURE_TYPE_I;
744 return AVERROR_INVALIDDATA;
745 c->corrupted = decode_inter(c, &acoder, 0, 0,
746 avctx->width, avctx->height);
747 c->pic.key_frame = 0;
748 c->pic.pict_type = AV_PICTURE_TYPE_P;
751 return AVERROR_INVALIDDATA;
752 memcpy(c->pic.data[1], c->pal, AVPALETTE_SIZE);
753 c->pic.palette_has_changed = pal_changed;
755 *data_size = sizeof(AVFrame);
756 *(AVFrame*)data = c->pic;
758 /* always report that the buffer was completely consumed */
762 static av_cold int mss1_decode_init(AVCodecContext *avctx)
764 MSS1Context * const c = avctx->priv_data;
769 if (avctx->extradata_size < 52 + 256 * 3) {
770 av_log(avctx, AV_LOG_ERROR, "Insufficient extradata size %d\n",
771 avctx->extradata_size);
772 return AVERROR_INVALIDDATA;
775 if (AV_RB32(avctx->extradata) < avctx->extradata_size) {
776 av_log(avctx, AV_LOG_ERROR,
777 "Insufficient extradata size: expected %d got %d\n",
778 AV_RB32(avctx->extradata),
779 avctx->extradata_size);
780 return AVERROR_INVALIDDATA;
783 av_log(avctx, AV_LOG_DEBUG, "Encoder version %d.%d\n",
784 AV_RB32(avctx->extradata + 4), AV_RB32(avctx->extradata + 8));
785 c->free_colours = AV_RB32(avctx->extradata + 48);
786 if ((unsigned)c->free_colours > 256) {
787 av_log(avctx, AV_LOG_ERROR,
788 "Incorrect number of changeable palette entries: %d\n",
790 return AVERROR_INVALIDDATA;
792 av_log(avctx, AV_LOG_DEBUG, "%d free colour(s)\n", c->free_colours);
793 avctx->coded_width = AV_RB32(avctx->extradata + 20);
794 avctx->coded_height = AV_RB32(avctx->extradata + 24);
796 av_log(avctx, AV_LOG_DEBUG, "Display dimensions %dx%d\n",
797 AV_RB32(avctx->extradata + 12), AV_RB32(avctx->extradata + 16));
798 av_log(avctx, AV_LOG_DEBUG, "Coded dimensions %dx%d\n",
799 avctx->coded_width, avctx->coded_height);
800 av_log(avctx, AV_LOG_DEBUG, "%g frames per second\n",
801 av_int2float(AV_RB32(avctx->extradata + 28)));
802 av_log(avctx, AV_LOG_DEBUG, "Bitrate %d bps\n",
803 AV_RB32(avctx->extradata + 32));
804 av_log(avctx, AV_LOG_DEBUG, "Max. lead time %g ms\n",
805 av_int2float(AV_RB32(avctx->extradata + 36)));
806 av_log(avctx, AV_LOG_DEBUG, "Max. lag time %g ms\n",
807 av_int2float(AV_RB32(avctx->extradata + 40)));
808 av_log(avctx, AV_LOG_DEBUG, "Max. seek time %g ms\n",
809 av_int2float(AV_RB32(avctx->extradata + 44)));
811 for (i = 0; i < 256; i++)
812 c->pal[i] = 0xFF << 24 | AV_RB24(avctx->extradata + 52 + i * 3);
814 avctx->pix_fmt = PIX_FMT_PAL8;
816 c->mask_linesize = FFALIGN(avctx->width, 16);
817 c->mask = av_malloc(c->mask_linesize * avctx->height);
819 av_log(avctx, AV_LOG_ERROR, "Cannot allocate mask plane\n");
820 return AVERROR(ENOMEM);
823 avctx->coded_frame = &c->pic;
830 static av_cold int mss1_decode_end(AVCodecContext *avctx)
832 MSS1Context * const c = avctx->priv_data;
835 avctx->release_buffer(avctx, &c->pic);
841 AVCodec ff_mss1_decoder = {
843 .type = AVMEDIA_TYPE_VIDEO,
845 .priv_data_size = sizeof(MSS1Context),
846 .init = mss1_decode_init,
847 .close = mss1_decode_end,
848 .decode = mss1_decode_frame,
849 .capabilities = CODEC_CAP_DR1,
850 .long_name = NULL_IF_CONFIG_SMALL("MS Screen 1"),