git.sesse.net Git - ffmpeg/blob - libavcodec/mss12.c

   1 /*
   2  * Copyright (c) 2012 Konstantin Shishkov
   3  *
   4  * This file is part of FFmpeg.
   5  *
   6  * FFmpeg is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2.1 of the License, or (at your option) any later version.
  10  *
  11  * FFmpeg is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with FFmpeg; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  19  */
  20
  21 /**
  22  * @file
  23  * Common functions for Microsoft Screen 1 and 2
  24  */
  25
  26 #include "libavutil/intfloat.h"
  27 #include "libavutil/intreadwrite.h"
  28 #include "avcodec.h"
  29 #include "mss12.h"
  30
  31 enum SplitMode {
  32     SPLIT_VERT = 0,
  33     SPLIT_HOR,
  34     SPLIT_NONE
  35 };
  36
  37 static const int sec_order_sizes[4] = { 1, 7, 6, 1 };
  38
  39 enum ContextDirection {
  40     TOP_LEFT = 0,
  41     TOP,
  42     TOP_RIGHT,
  43     LEFT
  44 };
  45
  46 static int model_calc_threshold(Model *m)
  47 {
  48     int thr;
  49
  50     if (m->thr_weight == -1) {
  51         thr = 2 * m->weights[m->num_syms] - 1;
  52         thr = ((thr >> 1) + 4 * m->cum_prob[0]) / thr;
  53     } else {
  54         thr = m->num_syms * m->thr_weight;
  55     }
  56
  57     return FFMIN(thr, 0x3FFF);
  58 }
  59
  60 static void model_reset(Model *m)
  61 {
  62     int i;
  63
  64     for (i = 0; i <= m->num_syms; i++) {
  65         m->weights[i]  = 1;
  66         m->cum_prob[i] = m->num_syms - i;
  67     }
  68     m->weights[0]           = -1;
  69     m->idx2sym[0]           = -1;
  70     m->sym2idx[m->num_syms] = -1;
  71     for (i = 0; i < m->num_syms; i++) {
  72         m->sym2idx[i]     = i + 1;
  73         m->idx2sym[i + 1] = i;
  74     }
  75 }
  76
  77 static av_cold void model_init(Model *m, int num_syms, int thr_weight)
  78 {
  79     m->num_syms   = num_syms;
  80     m->thr_weight = thr_weight;
  81     m->threshold  = model_calc_threshold(m);
  82     model_reset(m);
  83 }
  84
  85 static void model_rescale_weights(Model *m)
  86 {
  87     int i;
  88     int cum_prob;
  89
  90     if (m->thr_weight == -1)
  91         m->threshold = model_calc_threshold(m);
  92     while (m->cum_prob[0] > m->threshold) {
  93         cum_prob = 0;
  94         for (i = m->num_syms; i >= 0; i--) {
  95             m->cum_prob[i] = cum_prob;
  96             m->weights[i]  = (m->weights[i] + 1) >> 1;
  97             cum_prob      += m->weights[i];
  98         }
  99     }
 100 }
 101
 102 void ff_mss12_model_update(Model *m, int val)
 103 {
 104     int i;
 105
 106     if (m->weights[val] == m->weights[val - 1]) {
 107         for (i = val; m->weights[i - 1] == m->weights[val]; i--);
 108         if (i != val) {
 109             int sym1, sym2;
 110
 111             sym1 = m->idx2sym[val];
 112             sym2 = m->idx2sym[i];
 113
 114             m->idx2sym[val]  = sym2;
 115             m->idx2sym[i]    = sym1;
 116             m->sym2idx[sym1] = i;
 117             m->sym2idx[sym2] = val;
 118
 119             val = i;
 120         }
 121     }
 122     m->weights[val]++;
 123     for (i = val - 1; i >= 0; i--)
 124         m->cum_prob[i]++;
 125     model_rescale_weights(m);
 126 }
 127
 128 static void pixctx_reset(PixContext *ctx)
 129 {
 130     int i, j, k;
 131
 132     for (i = 0; i < ctx->cache_size; i++)
 133         ctx->cache[i] = i;
 134
 135     model_reset(&ctx->cache_model);
 136     model_reset(&ctx->full_model);
 137
 138     for (i = 0; i < 4; i++)
 139         for (j = 0; j < sec_order_sizes[i]; j++)
 140             for (k = 0; k < 4; k++)
 141                 model_reset(&ctx->sec_models[i][j][k]);
 142 }
 143
 144 static av_cold void pixctx_init(PixContext *ctx, int cache_size)
 145 {
 146     int i, j, k;
 147
 148     ctx->cache_size = cache_size + 4;
 149     ctx->num_syms   = cache_size;
 150
 151     for (i = 0; i < ctx->cache_size; i++)
 152         ctx->cache[i] = i;
 153
 154     model_init(&ctx->cache_model, ctx->num_syms + 1, THRESH_LOW);
 155     model_init(&ctx->full_model, 256, THRESH_HIGH);
 156
 157     for (i = 0; i < 4; i++) {
 158         for (j = 0; j < sec_order_sizes[i]; j++) {
 159             for (k = 0; k < 4; k++) {
 160                 model_init(&ctx->sec_models[i][j][k], 2 + i,
 161                            i ? THRESH_LOW : THRESH_ADAPTIVE);
 162             }
 163         }
 164     }
 165 }
 166
 167 static int decode_top_left_pixel(ArithCoder *acoder, PixContext *pctx)
 168 {
 169     int i, val, pix;
 170
 171     val = acoder->get_model_sym(acoder, &pctx->cache_model);
 172     if (val < pctx->num_syms) {
 173         pix = pctx->cache[val];
 174     } else {
 175         pix = acoder->get_model_sym(acoder, &pctx->full_model);
 176         for (i = 0; i < pctx->cache_size - 1; i++)
 177             if (pctx->cache[i] == pix)
 178                 break;
 179         val = i;
 180     }
 181     if (val) {
 182         for (i = val; i > 0; i--)
 183             pctx->cache[i] = pctx->cache[i - 1];
 184         pctx->cache[0] = pix;
 185     }
 186
 187     return pix;
 188 }
 189
 190 static int decode_pixel(ArithCoder *acoder, PixContext *pctx,
 191                         uint8_t *ngb, int num_ngb)
 192 {
 193     int i, val, pix;
 194
 195     val = acoder->get_model_sym(acoder, &pctx->cache_model);
 196     if (val < pctx->num_syms) {
 197         int idx, j;
 198
 199
 200         idx = 0;
 201         for (i = 0; i < pctx->cache_size; i++) {
 202             for (j = 0; j < num_ngb; j++)
 203                 if (pctx->cache[i] == ngb[j])
 204                     break;
 205             if (j == num_ngb) {
 206                 if (idx == val)
 207                     break;
 208                 idx++;
 209             }
 210         }
 211         val = FFMIN(i, pctx->cache_size - 1);
 212         pix = pctx->cache[val];
 213     } else {
 214         pix = acoder->get_model_sym(acoder, &pctx->full_model);
 215         for (i = 0; i < pctx->cache_size - 1; i++)
 216             if (pctx->cache[i] == pix)
 217                 break;
 218         val = i;
 219     }
 220     if (val) {
 221         for (i = val; i > 0; i--)
 222             pctx->cache[i] = pctx->cache[i - 1];
 223         pctx->cache[0] = pix;
 224     }
 225
 226     return pix;
 227 }
 228
 229 static int decode_pixel_in_context(ArithCoder *acoder, PixContext *pctx,
 230                                    uint8_t *src, int stride, int x, int y,
 231                                    int has_right)
 232 {
 233     uint8_t neighbours[4];
 234     uint8_t ref_pix[4];
 235     int nlen;
 236     int layer = 0, sub;
 237     int pix;
 238     int i, j;
 239
 240     if (!y) {
 241         memset(neighbours, src[-1], 4);
 242     } else {
 243         neighbours[TOP] = src[-stride];
 244         if (!x) {
 245             neighbours[TOP_LEFT] = neighbours[LEFT] = neighbours[TOP];
 246         } else {
 247             neighbours[TOP_LEFT] = src[-stride - 1];
 248             neighbours[    LEFT] = src[-1];
 249         }
 250         if (has_right)
 251             neighbours[TOP_RIGHT] = src[-stride + 1];
 252         else
 253             neighbours[TOP_RIGHT] = neighbours[TOP];
 254     }
 255
 256     sub = 0;
 257     if (x >= 2 && src[-2] == neighbours[LEFT])
 258         sub  = 1;
 259     if (y >= 2 && src[-2 * stride] == neighbours[TOP])
 260         sub |= 2;
 261
 262     nlen = 1;
 263     ref_pix[0] = neighbours[0];
 264     for (i = 1; i < 4; i++) {
 265         for (j = 0; j < nlen; j++)
 266             if (ref_pix[j] == neighbours[i])
 267                 break;
 268         if (j == nlen)
 269             ref_pix[nlen++] = neighbours[i];
 270     }
 271
 272     switch (nlen) {
 273     case 1:
 274     case 4:
 275         layer = 0;
 276         break;
 277     case 2:
 278         if (neighbours[TOP] == neighbours[TOP_LEFT]) {
 279             if (neighbours[TOP_RIGHT] == neighbours[TOP_LEFT])
 280                 layer = 3;
 281             else if (neighbours[LEFT] == neighbours[TOP_LEFT])
 282                 layer = 2;
 283             else
 284                 layer = 4;
 285         } else if (neighbours[TOP_RIGHT] == neighbours[TOP_LEFT]) {
 286             if (neighbours[LEFT] == neighbours[TOP_LEFT])
 287                 layer = 1;
 288             else
 289                 layer = 5;
 290         } else if (neighbours[LEFT] == neighbours[TOP_LEFT]) {
 291             layer = 6;
 292         } else {
 293             layer = 0;
 294         }
 295         break;
 296     case 3:
 297         if (neighbours[TOP] == neighbours[TOP_LEFT])
 298             layer = 0;
 299         else if (neighbours[TOP_RIGHT] == neighbours[TOP_LEFT])
 300             layer = 1;
 301         else if (neighbours[LEFT] == neighbours[TOP_LEFT])
 302             layer = 2;
 303         else if (neighbours[TOP_RIGHT] == neighbours[TOP])
 304             layer = 3;
 305         else if (neighbours[TOP] == neighbours[LEFT])
 306             layer = 4;
 307         else
 308             layer = 5;
 309         break;
 310     }
 311
 312     pix = acoder->get_model_sym(acoder, &pctx->sec_models[nlen - 1][layer][sub]);
 313     if (pix < nlen)
 314         return ref_pix[pix];
 315     else
 316         return decode_pixel(acoder, pctx, ref_pix, nlen);
 317 }
 318
 319 static int decode_region(MSS12Context *ctx, ArithCoder *acoder, uint8_t *dst,
 320                          int x, int y, int width, int height, int stride,
 321                          PixContext *pctx)
 322 {
 323     int i, j;
 324
 325     dst += x + y * stride;
 326
 327     dst[0] = decode_top_left_pixel(acoder, pctx);
 328     for (j = 0; j < height; j++) {
 329         for (i = 0; i < width; i++) {
 330             if (!i && !j)
 331                 continue;
 332
 333             dst[i] = decode_pixel_in_context(acoder, pctx, dst + i, stride,
 334                                              i, j, width - i - 1);
 335         }
 336         dst += stride;
 337     }
 338
 339     return 0;
 340 }
 341
 342 static int decode_region_masked(MSS12Context *ctx, ArithCoder *acoder,
 343                                 uint8_t *dst, int stride, uint8_t *mask,
 344                                 int mask_stride, int x, int y,
 345                                 int width, int height,
 346                                 PixContext *pctx)
 347 {
 348     int i, j;
 349
 350     dst  += x + y * stride;
 351     mask += x + y * mask_stride;
 352
 353     if (mask[0] == 0xFF)
 354         dst[0] = decode_top_left_pixel(acoder, pctx);
 355     for (j = 0; j < height; j++) {
 356         for (i = 0; i < width; i++) {
 357             if (!i && !j || mask[i] != 0xFF)
 358                 continue;
 359
 360             dst[i] = decode_pixel_in_context(acoder, pctx, dst + i, stride,
 361                                              i, j, width - i - 1);
 362         }
 363         dst  += stride;
 364         mask += mask_stride;
 365     }
 366
 367     return 0;
 368 }
 369
 370 static av_cold void codec_init(MSS12Context *ctx)
 371 {
 372     model_init(&ctx->intra_region, 2, THRESH_ADAPTIVE);
 373     model_init(&ctx->inter_region, 2, THRESH_ADAPTIVE);
 374     model_init(&ctx->split_mode,   3, THRESH_HIGH);
 375     model_init(&ctx->edge_mode,    2, THRESH_HIGH);
 376     model_init(&ctx->pivot,        3, THRESH_LOW);
 377     pixctx_init(&ctx->intra_pix_ctx, 8);
 378     pixctx_init(&ctx->inter_pix_ctx, 2);
 379     ctx->corrupted = 1;
 380 }
 381
 382 void ff_mss12_codec_reset(MSS12Context *ctx)
 383 {
 384     model_reset(&ctx->intra_region);
 385     model_reset(&ctx->inter_region);
 386     model_reset(&ctx->split_mode);
 387     model_reset(&ctx->edge_mode);
 388     model_reset(&ctx->pivot);
 389     pixctx_reset(&ctx->intra_pix_ctx);
 390     pixctx_reset(&ctx->inter_pix_ctx);
 391
 392     ctx->corrupted = 0;
 393 }
 394
 395 static int decode_pivot(MSS12Context *ctx, ArithCoder *acoder, int base)
 396 {
 397     int val, inv;
 398
 399     inv = acoder->get_model_sym(acoder, &ctx->edge_mode);
 400     val = acoder->get_model_sym(acoder, &ctx->pivot) + 1;
 401
 402     if (val > 2) {
 403         if ((base + 1) / 2 - 2 <= 0) {
 404             ctx->corrupted = 1;
 405             return 0;
 406         }
 407         val = acoder->get_number(acoder, (base + 1) / 2 - 2) + 3;
 408     }
 409
 410     if ((unsigned)val >= base) {
 411         ctx->corrupted = 1;
 412         return 0;
 413     }
 414
 415     return inv ? base - val : val;
 416 }
 417
 418 static int decode_region_intra(MSS12Context *ctx, ArithCoder *acoder,
 419                                int x, int y, int width, int height)
 420 {
 421     int mode;
 422
 423     mode = acoder->get_model_sym(acoder, &ctx->intra_region);
 424
 425     if (!mode) {
 426         int i, pix;
 427         int stride = ctx->pic_stride;
 428         uint8_t *dst = ctx->pic_start + x + y * stride;
 429
 430         pix = decode_top_left_pixel(acoder, &ctx->intra_pix_ctx);
 431         for (i = 0; i < height; i++, dst += stride)
 432             memset(dst, pix, width);
 433     } else {
 434         return decode_region(ctx, acoder, ctx->pic_start,
 435                              x, y, width, height, ctx->pic_stride,
 436                              &ctx->intra_pix_ctx);
 437     }
 438
 439     return 0;
 440 }
 441
 442 static int decode_region_inter(MSS12Context *ctx, ArithCoder *acoder,
 443                                int x, int y, int width, int height)
 444 {
 445     int mode;
 446
 447     mode = acoder->get_model_sym(acoder, &ctx->inter_region);
 448
 449     if (!mode) {
 450         mode = decode_top_left_pixel(acoder, &ctx->inter_pix_ctx);
 451         if (mode != 0xFF) {
 452             return 0;
 453         } else {
 454             return decode_region_intra(ctx, acoder, x, y, width, height);
 455         }
 456     } else {
 457         if (decode_region(ctx, acoder, ctx->mask,
 458                           x, y, width, height, ctx->mask_linesize,
 459                           &ctx->inter_pix_ctx) < 0)
 460             return -1;
 461         return decode_region_masked(ctx, acoder, ctx->pic_start,
 462                                     ctx->pic_stride, ctx->mask,
 463                                     ctx->mask_linesize,
 464                                     x, y, width, height,
 465                                     &ctx->intra_pix_ctx);
 466     }
 467
 468     return 0;
 469 }
 470
 471 int ff_mss12_decode_rect(MSS12Context *ctx, ArithCoder *acoder,
 472                          int x, int y, int width, int height)
 473 {
 474     int mode, pivot;
 475
 476     if (ctx->corrupted)
 477         return -1;
 478
 479     mode = acoder->get_model_sym(acoder, &ctx->split_mode);
 480
 481     switch (mode) {
 482     case SPLIT_VERT:
 483         pivot = decode_pivot(ctx, acoder, height);
 484         if (ff_mss12_decode_rect(ctx, acoder, x, y, width, pivot))
 485             return -1;
 486         if (ff_mss12_decode_rect(ctx, acoder, x, y + pivot, width, height - pivot))
 487             return -1;
 488         break;
 489     case SPLIT_HOR:
 490         pivot = decode_pivot(ctx, acoder, width);
 491         if (ff_mss12_decode_rect(ctx, acoder, x, y, pivot, height))
 492             return -1;
 493         if (ff_mss12_decode_rect(ctx, acoder, x + pivot, y, width - pivot, height))
 494             return -1;
 495         break;
 496     case SPLIT_NONE:
 497         if (ctx->keyframe)
 498             return decode_region_intra(ctx, acoder, x, y, width, height);
 499         else
 500             return decode_region_inter(ctx, acoder, x, y, width, height);
 501     default:
 502         return -1;
 503     }
 504
 505     return 0;
 506 }
 507
 508 av_cold int ff_mss12_decode_init(AVCodecContext *avctx, int version)
 509 {
 510     MSS12Context * const c = avctx->priv_data;
 511     int i;
 512
 513     c->avctx = avctx;
 514
 515     if (avctx->extradata_size < 52 + 256 * 3) {
 516         av_log(avctx, AV_LOG_ERROR, "Insufficient extradata size %d\n",
 517                avctx->extradata_size);
 518         return AVERROR_INVALIDDATA;
 519     }
 520
 521     if (AV_RB32(avctx->extradata) < avctx->extradata_size) {
 522         av_log(avctx, AV_LOG_ERROR,
 523                "Insufficient extradata size: expected %d got %d\n",
 524                AV_RB32(avctx->extradata),
 525                avctx->extradata_size);
 526         return AVERROR_INVALIDDATA;
 527     }
 528
 529     av_log(avctx, AV_LOG_DEBUG, "Encoder version %d.%d\n",
 530            AV_RB32(avctx->extradata + 4), AV_RB32(avctx->extradata + 8));
 531     c->free_colours     = AV_RB32(avctx->extradata + 48);
 532     if ((unsigned)c->free_colours > 256) {
 533         av_log(avctx, AV_LOG_ERROR,
 534                "Incorrect number of changeable palette entries: %d\n",
 535                c->free_colours);
 536         return AVERROR_INVALIDDATA;
 537     }
 538     av_log(avctx, AV_LOG_DEBUG, "%d free colour(s)\n", c->free_colours);
 539     avctx->coded_width  = AV_RB32(avctx->extradata + 20);
 540     avctx->coded_height = AV_RB32(avctx->extradata + 24);
 541
 542     av_log(avctx, AV_LOG_DEBUG, "Display dimensions %dx%d\n",
 543            AV_RB32(avctx->extradata + 12), AV_RB32(avctx->extradata + 16));
 544     av_log(avctx, AV_LOG_DEBUG, "Coded dimensions %dx%d\n",
 545            avctx->coded_width, avctx->coded_height);
 546     av_log(avctx, AV_LOG_DEBUG, "%g frames per second\n",
 547            av_int2float(AV_RB32(avctx->extradata + 28)));
 548     av_log(avctx, AV_LOG_DEBUG, "Bitrate %d bps\n",
 549            AV_RB32(avctx->extradata + 32));
 550     av_log(avctx, AV_LOG_DEBUG, "Max. lead time %g ms\n",
 551            av_int2float(AV_RB32(avctx->extradata + 36)));
 552     av_log(avctx, AV_LOG_DEBUG, "Max. lag time %g ms\n",
 553            av_int2float(AV_RB32(avctx->extradata + 40)));
 554     av_log(avctx, AV_LOG_DEBUG, "Max. seek time %g ms\n",
 555            av_int2float(AV_RB32(avctx->extradata + 44)));
 556
 557     for (i = 0; i < 256; i++)
 558         c->pal[i] = 0xFF << 24 | AV_RB24(avctx->extradata + 52 + i * 3);
 559
 560     avctx->pix_fmt = PIX_FMT_PAL8;
 561
 562     c->mask_linesize = FFALIGN(avctx->width, 16);
 563     c->mask          = av_malloc(c->mask_linesize * avctx->height);
 564     if (!c->mask) {
 565         av_log(avctx, AV_LOG_ERROR, "Cannot allocate mask plane\n");
 566         return AVERROR(ENOMEM);
 567     }
 568
 569     codec_init(c);
 570
 571     return 0;
 572 }
 573
 574 av_cold int ff_mss12_decode_end(AVCodecContext *avctx)
 575 {
 576     MSS12Context * const c = avctx->priv_data;
 577
 578     av_freep(&c->mask);
 579
 580     return 0;
 581 }