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

   1 /*
   2  * ScreenPressor version 3 decoder
   3  *
   4  * Copyright (c) 2017 Paul B Mahol
   5  *
   6  * This file is part of FFmpeg.
   7  *
   8  * FFmpeg is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Lesser General Public
  10  * License as published by the Free Software Foundation; either
  11  * version 2.1 of the License, or (at your option) any later version.
  12  *
  13  * FFmpeg 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 GNU
  16  * Lesser General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with FFmpeg; if not, write to the Free Software
  20  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  21  */
  22
  23 #include <stdio.h>
  24 #include <stdlib.h>
  25 #include <string.h>
  26
  27 #include "libavutil/qsort.h"
  28
  29 #include "avcodec.h"
  30 #include "bytestream.h"
  31 #include "internal.h"
  32 #include "scpr.h"
  33
  34 static void renew_table3(uint32_t nsym, uint32_t *cntsum,
  35                          uint16_t *freqs, uint16_t *freqs1,
  36                          uint16_t *cnts, uint8_t *dectab)
  37 {
  38     uint32_t a = 0, b = 4096 / nsym, c = b - (b >> 1);
  39
  40     *cntsum = c * nsym;
  41
  42     for (int d = 0; d < nsym; d++) {
  43         freqs[d] = b;
  44         freqs1[d] = a;
  45         cnts[d] = c;
  46         for (int q = a + 128 - 1 >> 7, f = (a + b - 1 >> 7) + 1; q < f; q++)
  47             dectab[q] = d;
  48
  49         a += b;
  50     }
  51 }
  52
  53 static void reinit_tables3(SCPRContext * s)
  54 {
  55     for (int i = 0; i < 3; i++) {
  56         for (int j = 0; j < 4096; j++) {
  57             PixelModel3 *m = &s->pixel_model3[i][j];
  58             m->type = 0;
  59         }
  60     }
  61
  62     for (int i = 0; i < 6; i++) {
  63         renew_table3(256, &s->run_model3[i].cntsum,
  64                      s->run_model3[i].freqs[0], s->run_model3[i].freqs[1],
  65                      s->run_model3[i].cnts, s->run_model3[i].dectab);
  66     }
  67
  68     renew_table3(256, &s->range_model3.cntsum,
  69                  s->range_model3.freqs[0], s->range_model3.freqs[1],
  70                  s->range_model3.cnts, s->range_model3.dectab);
  71
  72     renew_table3(5, &s->fill_model3.cntsum,
  73                  s->fill_model3.freqs[0], s->fill_model3.freqs[1],
  74                  s->fill_model3.cnts, s->fill_model3.dectab);
  75
  76     renew_table3(256, &s->count_model3.cntsum,
  77                  s->count_model3.freqs[0], s->count_model3.freqs[1],
  78                  s->count_model3.cnts, s->count_model3.dectab);
  79
  80     for (int i = 0; i < 4; i++) {
  81         renew_table3(16, &s->sxy_model3[i].cntsum,
  82                      s->sxy_model3[i].freqs[0], s->sxy_model3[i].freqs[1],
  83                      s->sxy_model3[i].cnts, s->sxy_model3[i].dectab);
  84     }
  85
  86     for (int i = 0; i < 2; i++) {
  87         renew_table3(512, &s->mv_model3[i].cntsum,
  88                      s->mv_model3[i].freqs[0], s->mv_model3[i].freqs[1],
  89                      s->mv_model3[i].cnts, s->mv_model3[i].dectab);
  90     }
  91
  92     for (int i = 0; i < 6; i++) {
  93         renew_table3(6, &s->op_model3[i].cntsum,
  94                      s->op_model3[i].freqs[0], s->op_model3[i].freqs[1],
  95                      s->op_model3[i].cnts, s->op_model3[i].dectab);
  96     }
  97 }
  98
  99 static int decode3(GetByteContext *gb, RangeCoder *rc, uint32_t a, uint32_t b)
 100 {
 101     uint32_t code = a * (rc->code >> 12) + (rc->code & 0xFFF) - b;
 102
 103     while (code < 0x800000 && bytestream2_get_bytes_left(gb) > 0)
 104         code = bytestream2_get_byteu(gb) | (code << 8);
 105     rc->code = code;
 106
 107     return 0;
 108 }
 109
 110 static void rescale(PixelModel3 *m, int *totfr)
 111 {
 112     uint32_t a;
 113
 114     a = 256 - m->size;
 115     for (int b = 0; b < m->size; b++) {
 116         m->freqs[b] -= m->freqs[b] >> 1;
 117         a += m->freqs[b];
 118     }
 119
 120     *totfr = a;
 121 }
 122
 123 static int add_symbol(PixelModel3 *m, int index, uint32_t symbol, int *totfr, int max)
 124 {
 125     if (m->size == max)
 126         return 0;
 127
 128     for (int c = m->size - 1; c >= index; c--) {
 129         m->symbols[c + 1] = m->symbols[c];
 130         m->freqs[c + 1] = m->freqs[c];
 131     }
 132
 133     m->symbols[index] = symbol;
 134     m->freqs[index] = 50;
 135     m->size++;
 136
 137     if (m->maxpos >= index)
 138         m->maxpos++;
 139
 140     *totfr += 50;
 141     if (*totfr + 50 > 4096)
 142         rescale(m, totfr);
 143
 144     return 1;
 145 }
 146
 147 static int decode_adaptive45(PixelModel3 *m, int rccode, uint32_t *value,
 148                              uint16_t *a, uint16_t *b, uint32_t *c, int max)
 149 {
 150     uint32_t q, g, maxpos, d, e = *c, totfr = *c;
 151     int ret;
 152
 153     for (d = 0; e <= 2048; d++)
 154         e <<= 1;
 155     maxpos = m->maxpos;
 156     rccode >>= d;
 157     *c = m->freqs[maxpos];
 158     m->freqs[maxpos] += 4096 - e >> d;
 159
 160     for (q = 0, g = 0, e = 0; q < m->size; q++) {
 161         uint32_t f = m->symbols[q];
 162         uint32_t p = e + f - g;
 163         uint32_t k = m->freqs[q];
 164
 165         if (rccode < p) {
 166             *value = rccode - e + g;
 167             *b = rccode << d;
 168             *a = 1 << d;
 169             m->freqs[maxpos] = *c;
 170             ret = add_symbol(m, q, *value, &totfr, max);
 171             *c = totfr;
 172             return ret;
 173         }
 174
 175         if (p + k > rccode) {
 176             *value = f;
 177             e += *value - g;
 178             *b = e << d;
 179             *a = k << d;
 180             m->freqs[maxpos] = *c;
 181             m->freqs[q] += 50;
 182             totfr += 50;
 183             if ((q != maxpos) && (m->freqs[q] > m->freqs[maxpos]))
 184                 m->maxpos = q;
 185             if (totfr + 50 > 4096)
 186                 rescale(m, &totfr);
 187             *c = totfr;
 188             return 1;
 189         }
 190
 191         e += f - g + k;
 192         g = f + 1;
 193     }
 194
 195     m->freqs[maxpos] = *c;
 196     *value = g + rccode - e;
 197     *b = rccode << d;
 198     *a = 1 << d;
 199     ret = add_symbol(m, q, *value, &totfr, max);
 200     *c = totfr;
 201     return ret;
 202 }
 203
 204 static int update_model6_to_7(PixelModel3 *m)
 205 {
 206     PixelModel3 n = {0};
 207     int c, d, e, f, k, p, length, i, j, index;
 208     uint16_t *freqs, *freqs1, *cnts;
 209
 210     n.type = 7;
 211
 212     length = m->length;
 213     freqs = n.freqs;
 214     freqs1 = n.freqs1;
 215     cnts = n.cnts;
 216     n.cntsum = m->cnts[length];
 217     for (i = 0; i < length; i++) {
 218         if (!m->cnts[i])
 219             continue;
 220         index = m->symbols[i];
 221         freqs[index] = m->freqs[2 * i];
 222         freqs1[index] = m->freqs[2 * i + 1];
 223         cnts[index] = m->cnts[i];
 224     }
 225     c = 1 << m->fshift;
 226     d = c - (c >> 1);
 227     for (j = 0, e = 0; j < 256; j++) {
 228         f = freqs[j];
 229         if (!f) {
 230             f = c;
 231             freqs[j] = c;
 232             freqs1[j] = e;
 233             cnts[j] = d;
 234         }
 235         p = (e + 127) >> 7;
 236         k = ((f + e - 1) >> 7) + 1;
 237         if (k > FF_ARRAY_ELEMS(n.dectab))
 238             return AVERROR_INVALIDDATA;
 239         for (i = 0; i < k - p; i++)
 240             n.dectab[p + i] = j;
 241         e += f;
 242     }
 243
 244     memcpy(m, &n, sizeof(n));
 245
 246     return 0;
 247 }
 248
 249 static void calc_sum(PixelModel3 *m)
 250 {
 251     uint32_t a;
 252     int len;
 253
 254     len = m->length;
 255     a = 256 - m->size << (m->fshift > 0 ? m->fshift - 1 : 0);
 256     for (int c = 0; c < len; c++)
 257         a += m->cnts[c];
 258     m->cnts[len] = a;
 259 }
 260
 261 static void rescale_dec(PixelModel3 *m)
 262 {
 263     uint16_t cnts[256] = {0};
 264     uint16_t freqs[512] = {0};
 265     int b, c, e, g;
 266     uint32_t a;
 267
 268     for (a = 1 << (0 < m->fshift ? m->fshift - 1 : 0), b = 0; b < 256; b++)
 269         cnts[b] = a;
 270
 271     for (a = 0, b = m->size; a < b; a++)
 272         cnts[m->symbols[a]] = m->cnts[a];
 273
 274     for (b = a = 0; b < 256; b++) {
 275         freqs[2 * b] = cnts[b];
 276         freqs[2 * b + 1] = a;
 277         a += cnts[b];
 278     }
 279
 280     if (m->fshift > 0)
 281         m->fshift--;
 282
 283     a = 256 - m->size << (0 < m->fshift ? m->fshift - 1 : 0);
 284     for (b = 0, c = m->size; b < c; b++) {
 285         m->cnts[b] -= m->cnts[b] >> 1;
 286         a = a + m->cnts[b];
 287         e = m->symbols[b];
 288         g = freqs[2 * e + 1];
 289         m->freqs[2 * b] = freqs[2 * e];
 290         m->freqs[2 * b + 1] = g;
 291     }
 292     m->cnts[m->length] = a;
 293 }
 294
 295 static int update_model5_to_6(PixelModel3 *m, uint8_t value)
 296 {
 297     PixelModel3 n = {0};
 298     int c, d, e, f, g, k, q, p;
 299
 300     n.type = 6;
 301     n.length = 32;
 302
 303     for (c = m->size, d = 256 - c, e = 0; e < c; e++)
 304         d = d + m->freqs[e];
 305
 306     for (e = 0; d <= 2048; e++)
 307         d <<= 1;
 308
 309     for (q = d = 0, g = q = 0; g < c; g++) {
 310         p = m->symbols[g];
 311         d = d + (p - q);
 312         q = m->freqs[g];
 313         k = q << e;
 314         n.freqs[2 * g] = k;
 315         n.freqs[2 * g + 1] = d << e;
 316         n.cnts[g] = k - (k >> 1);
 317         n.symbols[g] = p;
 318         d += q;
 319         q = p + 1;
 320     }
 321
 322     n.fshift = e;
 323     e = 1 << n.fshift;
 324     d = 0;
 325     if (value > 0) {
 326         d = -1;
 327         for (p = f = g = 0; p < c; p++) {
 328             k = n.symbols[p];
 329             if (k > d && k < value) {
 330                 d = k;
 331                 g = n.freqs[2 * p];
 332                 f = n.freqs[2 * p + 1];
 333             }
 334         }
 335         d = 0 < g ? f + g + (value - d - 1 << n.fshift) : value << n.fshift;
 336     }
 337     n.freqs[2 * c] = e;
 338     n.freqs[2 * c + 1] = d;
 339     n.cnts[c] = e - (e >> 1);
 340     n.symbols[c] = value;
 341     n.size = c + 1;
 342     e = 25 << n.fshift;
 343     n.cnts[c] += e;
 344     n.cnts[32] += e;
 345     if (n.cnts[32] + e > 4096)
 346         rescale_dec(&n);
 347
 348     calc_sum(&n);
 349     for (c = 0, e = n.size - 1; c < e; c++) {
 350         for (g = c + 1, f = n.size; g < f; g++) {
 351             if (q = n.freqs[2 * g], k = n.freqs[2 * c], q > k) {
 352                 int l = n.freqs[2 * c + 1];
 353                 int h = n.freqs[2 * g + 1];
 354                 n.freqs[2 * c] = q;
 355                 n.freqs[2 * c + 1] = h;
 356                 n.freqs[2 * g] = k;
 357                 n.freqs[2 * g + 1] = l;
 358                 FFSWAP(uint16_t, n.cnts[c], n.cnts[g]);
 359                 FFSWAP(uint8_t, n.symbols[c], n.symbols[g]);
 360             }
 361         }
 362     }
 363
 364     memcpy(m, &n, sizeof(n));
 365
 366     return 0;
 367 }
 368
 369 static void grow_dec(PixelModel3 *m)
 370 {
 371     int a;
 372
 373     a = 2 * m->length;
 374     m->cnts[2 * m->length] = m->cnts[m->length];
 375     m->length = a;
 376 }
 377
 378 static int add_dec(PixelModel3 *m, int sym, int f1, int f2)
 379 {
 380     int size;
 381
 382     if (m->size >= 40 || m->size >= m->length)
 383         return -1;
 384
 385     size = m->size;
 386     m->symbols[size] = sym;
 387     m->freqs[2 * size] = f1;
 388     m->freqs[2 * size + 1] = f2;
 389     m->cnts[size] = f1 - (f1 >> 1);
 390     m->size++;
 391
 392     return size;
 393 }
 394
 395 static void incr_cntdec(PixelModel3 *m, int a)
 396 {
 397     int b, len, d, e, g;
 398
 399     b = 25 << m->fshift;
 400     len = m->length;
 401     m->cnts[a] += b;
 402     m->cnts[len] += b;
 403     if (a > 0 && m->cnts[a] > m->cnts[a - 1]) {
 404         FFSWAP(uint16_t, m->cnts[a], m->cnts[a - 1]);
 405         d = m->freqs[2 * a];
 406         e = m->freqs[2 * a + 1];
 407         g = m->freqs[2 * (a - 1) + 1];
 408         m->freqs[2 * a] = m->freqs[2 * (a - 1)];
 409         m->freqs[2 * a + 1] = g;
 410         g = a - 1;
 411         m->freqs[2 * g] = d;
 412         m->freqs[2 * g + 1] = e;
 413         FFSWAP(uint8_t, m->symbols[a], m->symbols[a - 1]);
 414     }
 415
 416     if (m->cnts[len] + b > 4096)
 417         rescale_dec(m);
 418 }
 419
 420 static int decode_adaptive6(PixelModel3 *m, uint32_t code, uint32_t *value,
 421                             uint16_t *a, uint16_t *b)
 422 {
 423     int c, d, e, f, g, q;
 424
 425     for (c = 0, d = 0, e = 0, f = 0, g = 0, q = m->size; g < q; g++) {
 426         uint32_t p = m->freqs[2 * g + 1];
 427
 428         if (p <= code) {
 429             uint32_t k = m->freqs[2 * g];
 430
 431             if (p + k > code) {
 432                 *value = m->symbols[g];
 433                 *a = k;
 434                 *b = p;
 435                 incr_cntdec(m, g);
 436                 return 1;
 437             }
 438
 439             if (p >= d) {
 440                 c = k;
 441                 d = p;
 442                 e = m->symbols[g];
 443             }
 444         }
 445     }
 446
 447     g = 1 << m->fshift;
 448     q = f = 0;
 449
 450     if (c > 0) {
 451         f = code - (d + c) >> m->fshift;
 452         q = f + e + 1;
 453         f = d + c + (f << m->fshift);
 454     } else {
 455         q = code >> m->fshift;
 456         f = q << m->fshift;
 457     }
 458
 459     *a = g;
 460     *b = f;
 461     *value = q;
 462
 463     c = add_dec(m, q, g, f);
 464     if (c < 0) {
 465         if (m->length == 64)
 466             return 0;
 467         grow_dec(m);
 468         c = add_dec(m, q, g, f);
 469     }
 470
 471     incr_cntdec(m, c);
 472     return 1;
 473 }
 474
 475 static int cmpbytes(const void *p1, const void *p2)
 476 {
 477     int left  = *(const uint8_t *)p1;
 478     int right = *(const uint8_t *)p2;
 479     return FFDIFFSIGN(left, right);
 480 }
 481
 482 static int update_model1_to_2(PixelModel3 *m, uint32_t val)
 483 {
 484     PixelModel3 n = {0};
 485     int i, b;
 486
 487     n.type = 2;
 488     n.size = m->size + 1;
 489     b = m->size;
 490     for (i = 0; i < b; i++)
 491         n.symbols[i] = m->symbols[i];
 492     n.symbols[b] = val;
 493
 494     memcpy(m, &n, sizeof(n));
 495
 496     return 0;
 497 }
 498
 499 static int update_model1_to_4(PixelModel3 *m, uint32_t val)
 500 {
 501     PixelModel3 n = {0};
 502     int size, i;
 503
 504     size = m->size;
 505     n.type = 4;
 506     n.size = size;
 507     for (i = 0; i < n.size; i++) {
 508         n.symbols[i] = m->symbols[i];
 509     }
 510     AV_QSORT(n.symbols, size, uint8_t, cmpbytes);
 511     for (i = 0; i < n.size; i++) {
 512         if (val == n.symbols[i]) {
 513             n.freqs[i] = 100;
 514             n.maxpos = i;
 515         } else {
 516             n.freqs[i] = 50;
 517         }
 518     }
 519
 520     memcpy(m, &n, sizeof(n));
 521
 522     return 0;
 523 }
 524
 525 static int update_model1_to_5(PixelModel3 *m, uint32_t val)
 526 {
 527     int i, size, freqs;
 528     uint32_t a;
 529
 530     update_model1_to_4(m, val);
 531     size = m->size;
 532     a = 256 - size;
 533     for (i = 0; i < size; i++, a += freqs)
 534         freqs = m->freqs[i];
 535     m->type = 5;
 536     m->cntsum = a;
 537
 538     return 0;
 539 }
 540
 541 static int decode_static1(PixelModel3 *m, uint32_t val)
 542 {
 543     uint32_t size;
 544
 545     size = m->size;
 546     for (int i = 0; i < size; i++) {
 547         if (val == m->symbols[i]) {
 548             if (size <= 4)
 549                 return update_model1_to_4(m, val);
 550             else
 551                 return update_model1_to_5(m, val);
 552         }
 553     }
 554
 555     if (size >= 14)
 556         return update_model1_to_2(m, val);
 557
 558     m->symbols[size] = val;
 559     m->size++;
 560     return 0;
 561 }
 562
 563 static int update_model2_to_6(PixelModel3 *m, uint8_t value, int a4)
 564 {
 565     PixelModel3 n = {0};
 566     int c, d, e, f, g, q;
 567
 568     n.type = 6;
 569     n.length = a4;
 570
 571     memset(n.symbols, 1u, a4);
 572
 573     c = m->size;
 574     d = 256 - c + (64 * c + 64);
 575     for (e = 0; d <= 2048; e++) {
 576         d <<= 1;
 577     }
 578
 579     g = q = 0;
 580     AV_QSORT(m->symbols, c, uint8_t, cmpbytes);
 581     for (f = d = 0; f < c; f++) {
 582         int p = f;
 583         int k = m->symbols[p];
 584         int l;
 585         g = g + (k - q);
 586
 587         if (k == value) {
 588             d = p;
 589             q = 128;
 590         } else {
 591             q = 64;
 592         }
 593         l = q << e;
 594         n.freqs[2 * p] = l;
 595         n.freqs[2 * p + 1] = g << e;
 596         n.symbols[p] = k;
 597         n.cnts[p] = l - (l >> 1);
 598         g += q;
 599         q = k + 1;
 600     }
 601     n.size = c;
 602     n.fshift = e;
 603     calc_sum(&n);
 604
 605     if (d > 0) {
 606         c = n.freqs[0];
 607         e = n.freqs[1];
 608         g = n.freqs[2 * d + 1];
 609         n.freqs[0] = n.freqs[2 * d];
 610         n.freqs[1] = g;
 611         n.freqs[2 * d] = c;
 612         n.freqs[2 * d + 1] = e;
 613         FFSWAP(uint16_t, n.cnts[0], n.cnts[d]);
 614         FFSWAP(uint8_t, n.symbols[0], n.symbols[d]);
 615     }
 616
 617     memcpy(m, &n, sizeof(n));
 618
 619     return 0;
 620 }
 621
 622 static int update_model2_to_3(PixelModel3 *m, uint32_t val)
 623 {
 624     PixelModel3 n = {0};
 625     uint32_t size;
 626
 627     n.type = 3;
 628     n.size = m->size + 1;
 629
 630     size = m->size;
 631     for (int i = 0; i < size; i++)
 632         n.symbols[i] = m->symbols[i];
 633     n.symbols[size] = val;
 634
 635     memcpy(m, &n, sizeof(n));
 636
 637     return 0;
 638 }
 639
 640 static int decode_static2(PixelModel3 *m, uint32_t val)
 641 {
 642     uint32_t size;
 643
 644     size = m->size;
 645     for (int i = 0; i < size; i++) {
 646         if (val == m->symbols[i]) {
 647             int a;
 648
 649             if (m->size <= 32)
 650                 a = 32;
 651             else
 652                 a = 64;
 653             return update_model2_to_6(m, val, a);
 654         }
 655     }
 656
 657     if (size >= 64)
 658         return update_model2_to_3(m, val);
 659
 660     m->symbols[size] = val;
 661     m->size++;
 662
 663     return 0;
 664 }
 665
 666 static int update_model3_to_7(PixelModel3 *m, uint8_t value)
 667 {
 668     PixelModel3 n = {0};
 669     int c, d, e, f, g, q;
 670
 671     n.type = 7;
 672
 673     for (c = 0; c < 256; c++) {
 674         d = c;
 675         n.freqs[d] = 1;
 676         n.cnts[d] = 1;
 677     }
 678
 679     for (c = m->size, d = (4096 - (256 - c)) / (c + 1) | 0, e = d - (d >> 1), g = 0; g < c;) {
 680         q = g++;
 681         q = m->symbols[q];
 682         n.freqs[q] = d;
 683         n.cnts[q] = e;
 684     }
 685     n.freqs[value] += d;
 686     n.cnts[value] += 16;
 687     for (d = c = n.cntsum = 0; 256 > d; d++) {
 688         e = d;
 689         n.cntsum += n.cnts[e];
 690         n.freqs1[e] = c;
 691         g = n.freqs[e];
 692         f = (c + g - 1 >> 7) + 1;
 693         if (f > FF_ARRAY_ELEMS(n.dectab))
 694             return AVERROR_INVALIDDATA;
 695         for (q = c + 128 - 1 >> 7; q < f; q++) {
 696             n.dectab[q] = e;
 697         }
 698         c += g;
 699     }
 700
 701     memcpy(m, &n, sizeof(n));
 702
 703     return 0;
 704 }
 705
 706 static int decode_static3(PixelModel3 *m, uint32_t val)
 707 {
 708     uint32_t size = m->size;
 709
 710     for (int i = 0; i < size; i++) {
 711         if (val == m->symbols[i])
 712             return update_model3_to_7(m, val);
 713     }
 714
 715     if (size >= 256)
 716         return 0;
 717
 718     m->symbols[size] = val;
 719     m->size++;
 720     return 0;
 721 }
 722
 723 static void sync_code3(GetByteContext *gb, RangeCoder *rc)
 724 {
 725     rc->code1++;
 726     if (rc->code1 == 0x20000) {
 727         rc->code = bytestream2_get_le32(gb);
 728         rc->code1 = 0;
 729     }
 730 }
 731
 732 static int decode_value3(SCPRContext *s, uint32_t max, uint32_t *cntsum,
 733                          uint16_t *freqs1, uint16_t *freqs2,
 734                          uint16_t *cnts, uint8_t *dectable,
 735                          uint32_t *value)
 736 {
 737     GetByteContext *gb = &s->gb;
 738     RangeCoder *rc = &s->rc;
 739     uint32_t r, y, a, b, e, g, q;
 740
 741     r = dectable[(rc->code & 0xFFFu) >> 7];
 742     if (r < max) {
 743         while (freqs2[r + 1] <= (rc->code & 0xFFF)) {
 744             if (++r >= max)
 745                 break;
 746         }
 747     }
 748
 749     if (r > max)
 750         return AVERROR_INVALIDDATA;
 751
 752     cnts[r] += 16;
 753     a = freqs1[r];
 754     b = freqs2[r];
 755     *cntsum += 16;
 756     if (*cntsum + 16 > 4096) {
 757         *cntsum = 0;
 758         for (int c = 0, i = 0; i < max + 1; i++) {
 759             e = cnts[i];
 760             freqs2[i] = c;
 761             freqs1[i] = e;
 762             g = (c + 127) >> 7;
 763             c += e;
 764             q = ((c - 1) >> 7) + 1;
 765             if (q > g) {
 766                 for (int j = 0; j < q - g; j++)
 767                     dectable[j + g] = i;
 768             }
 769             y = e - (e >> 1);
 770             cnts[i] = y;
 771             *cntsum += y;
 772         }
 773     }
 774
 775     decode3(gb, rc, a, b);
 776     sync_code3(gb, rc);
 777
 778     *value = r;
 779
 780     return 0;
 781 }
 782
 783 static void calc_sum5(PixelModel3 *m)
 784 {
 785     uint32_t a;
 786
 787     a = 256 - m->size;
 788     for (int b = 0; b < m->size; b++)
 789         a += m->freqs[b];
 790     m->cntsum = a;
 791 }
 792
 793 static int update_model4_to_5(PixelModel3 *m, uint32_t value)
 794 {
 795     PixelModel3 n = {0};
 796     int c, e, g, totfr;
 797
 798     n.type = 5;
 799
 800     for (c = 0, e = 0; c < m->size && m->symbols[c] < value; c++) {
 801         n.symbols[c] = m->symbols[c];
 802         e += n.freqs[c] = m->freqs[c];
 803     }
 804
 805     g = c;
 806     n.symbols[g] = value;
 807     e += n.freqs[g++] = 50;
 808     for (; c < m->size; g++, c++) {
 809         n.symbols[g] = m->symbols[c];
 810         e += n.freqs[g] = m->freqs[c];
 811     }
 812     n.size = m->size + 1;
 813     if (e > 4096)
 814         rescale(&n, &totfr);
 815
 816     calc_sum5(&n);
 817
 818     memcpy(m, &n, sizeof(n));
 819
 820     return 0;
 821 }
 822
 823 static int decode_unit3(SCPRContext *s, PixelModel3 *m, uint32_t code, uint32_t *value)
 824 {
 825     GetByteContext *gb = &s->gb;
 826     RangeCoder *rc = &s->rc;
 827     uint16_t a = 0, b = 0;
 828     uint32_t param;
 829     int type;
 830     int ret;
 831
 832     type = m->type;
 833     switch (type) {
 834     case 0:
 835         *value = bytestream2_get_byte(&s->gb);
 836         m->type = 1;
 837         m->size = 1;
 838         m->symbols[0] = *value;
 839         sync_code3(gb, rc);
 840         break;
 841     case 1:
 842         *value = bytestream2_get_byte(&s->gb);
 843         decode_static1(m, *value);
 844         sync_code3(gb, rc);
 845         break;
 846     case 2:
 847         *value = bytestream2_get_byte(&s->gb);
 848         decode_static2(m, *value);
 849         sync_code3(gb, rc);
 850         break;
 851     case 3:
 852         *value = bytestream2_get_byte(&s->gb);
 853         ret = decode_static3(m, *value);
 854         if (ret < 0)
 855             return AVERROR_INVALIDDATA;
 856         sync_code3(gb, rc);
 857         break;
 858     case 4:
 859         param = m->freqs[0] + m->freqs[1] + m->freqs[2] + m->freqs[3] + 256 - m->size;
 860         if (!decode_adaptive45(m, code, value, &a, &b, &param, 4))
 861             update_model4_to_5(m, *value);
 862         decode3(gb, rc, a, b);
 863         sync_code3(gb, rc);
 864         break;
 865     case 5:
 866         if (!decode_adaptive45(m, code, value, &a, &b, &m->cntsum, 16))
 867             update_model5_to_6(m, *value);
 868         decode3(gb, rc, a, b);
 869         sync_code3(gb, rc);
 870         break;
 871     case 6:
 872         if (!decode_adaptive6(m, code, value, &a, &b)) {
 873             ret = update_model6_to_7(m);
 874             if (ret < 0)
 875                 return AVERROR_INVALIDDATA;
 876         }
 877         decode3(gb, rc, a, b);
 878         sync_code3(gb, rc);
 879         break;
 880     case 7:
 881         return decode_value3(s, 255, &m->cntsum,
 882                              m->freqs, m->freqs1,
 883                              m->cnts, m->dectab, value);
 884     }
 885
 886     if (*value > 255)
 887         return AVERROR_INVALIDDATA;
 888
 889     return 0;
 890 }
 891
 892 static int decode_units3(SCPRContext * s, uint32_t *red,
 893                          uint32_t *green, uint32_t *blue,
 894                          int *cx, int *cx1)
 895 {
 896     RangeCoder *rc = &s->rc;
 897     int ret;
 898
 899     ret = decode_unit3(s, &s->pixel_model3[0][*cx + *cx1], rc->code & 0xFFF, red);
 900     if (ret < 0)
 901         return ret;
 902
 903     *cx1 = (*cx << 6) & 0xFC0;
 904     *cx = *red >> 2;
 905
 906     ret = decode_unit3(s, &s->pixel_model3[1][*cx + *cx1], rc->code & 0xFFF, green);
 907     if (ret < 0)
 908         return ret;
 909
 910     *cx1 = (*cx << 6) & 0xFC0;
 911     *cx = *green >> 2;
 912
 913     ret = decode_unit3(s, &s->pixel_model3[2][*cx + *cx1], rc->code & 0xFFF, blue);
 914     if (ret < 0)
 915         return ret;
 916
 917     *cx1 = (*cx << 6) & 0xFC0;
 918     *cx = *blue >> 2;
 919
 920     return 0;
 921 }
 922
 923 static void init_rangecoder3(RangeCoder *rc, GetByteContext *gb)
 924 {
 925     rc->code  = bytestream2_get_le32(gb);
 926     rc->code1 = 0;
 927 }
 928
 929 static int decompress_i3(AVCodecContext *avctx, uint32_t *dst, int linesize)
 930 {
 931     SCPRContext *s = avctx->priv_data;
 932     GetByteContext *gb = &s->gb;
 933     RangeCoder *rc = &s->rc;
 934     int cx = 0, cx1 = 0, k = 0;
 935     int run, off, y = 0, x = 0, ret;
 936     uint32_t backstep = linesize - avctx->width;
 937     uint32_t clr = 0, lx, ly, ptype, r, g, b;
 938
 939     bytestream2_skip(gb, 1);
 940     init_rangecoder3(rc, gb);
 941     reinit_tables3(s);
 942
 943     while (k < avctx->width + 1) {
 944         ret = decode_units3(s, &r, &g, &b, &cx, &cx1);
 945         if (ret < 0)
 946             return ret;
 947         ret = decode_value3(s, 255, &s->run_model3[0].cntsum,
 948                             s->run_model3[0].freqs[0],
 949                             s->run_model3[0].freqs[1],
 950                             s->run_model3[0].cnts,
 951                             s->run_model3[0].dectab, &run);
 952         if (ret < 0)
 953             return ret;
 954         if (run <= 0)
 955             return AVERROR_INVALIDDATA;
 956
 957         clr = (b << 16) + (g << 8) + r;
 958         k += run;
 959         while (run-- > 0) {
 960             if (y >= avctx->height)
 961                 return AVERROR_INVALIDDATA;
 962
 963             dst[y * linesize + x] = clr;
 964             lx = x;
 965             ly = y;
 966             x++;
 967             if (x >= avctx->width) {
 968                 x = 0;
 969                 y++;
 970             }
 971         }
 972     }
 973     off = -linesize - 1;
 974     ptype = 0;
 975
 976     while (x < avctx->width && y < avctx->height) {
 977         ret = decode_value3(s, 5, &s->op_model3[ptype].cntsum,
 978                             s->op_model3[ptype].freqs[0],
 979                             s->op_model3[ptype].freqs[1],
 980                             s->op_model3[ptype].cnts,
 981                             s->op_model3[ptype].dectab, &ptype);
 982         if (ret < 0)
 983             return ret;
 984         if (ptype == 0) {
 985             ret = decode_units3(s, &r, &g, &b, &cx, &cx1);
 986             if (ret < 0)
 987                 return ret;
 988             clr = (b << 16) + (g << 8) + r;
 989         }
 990         if (ptype > 5)
 991             return AVERROR_INVALIDDATA;
 992         ret = decode_value3(s, 255, &s->run_model3[ptype].cntsum,
 993                             s->run_model3[ptype].freqs[0],
 994                             s->run_model3[ptype].freqs[1],
 995                             s->run_model3[ptype].cnts,
 996                             s->run_model3[ptype].dectab, &run);
 997         if (ret < 0)
 998             return ret;
 999         if (run <= 0)
1000             return AVERROR_INVALIDDATA;
1001
1002         ret = decode_run_i(avctx, ptype, run, &x, &y, clr,
1003                            dst, linesize, &lx, &ly,
1004                            backstep, off, &cx, &cx1);
1005         if (ret < 0)
1006             return ret;
1007     }
1008
1009     return 0;
1010 }
1011
1012 static int decompress_p3(AVCodecContext *avctx,
1013                          uint32_t *dst, int linesize,
1014                          uint32_t *prev, int plinesize)
1015 {
1016     SCPRContext *s = avctx->priv_data;
1017     GetByteContext *gb = &s->gb;
1018     int ret, temp, min, max, x, y, cx = 0, cx1 = 0;
1019     int backstep = linesize - avctx->width;
1020     int mvx = 0, mvy = 0;
1021
1022     if (bytestream2_get_byte(gb) == 0)
1023         return 1;
1024     init_rangecoder3(&s->rc, gb);
1025
1026     ret  = decode_value3(s, 255, &s->range_model3.cntsum,
1027                          s->range_model3.freqs[0],
1028                          s->range_model3.freqs[1],
1029                          s->range_model3.cnts,
1030                          s->range_model3.dectab, &min);
1031     ret |= decode_value3(s, 255, &s->range_model3.cntsum,
1032                          s->range_model3.freqs[0],
1033                          s->range_model3.freqs[1],
1034                          s->range_model3.cnts,
1035                          s->range_model3.dectab, &temp);
1036     if (ret < 0)
1037         return ret;
1038
1039     min += temp << 8;
1040     ret |= decode_value3(s, 255, &s->range_model3.cntsum,
1041                          s->range_model3.freqs[0],
1042                          s->range_model3.freqs[1],
1043                          s->range_model3.cnts,
1044                          s->range_model3.dectab, &max);
1045     ret |= decode_value3(s, 255, &s->range_model3.cntsum,
1046                          s->range_model3.freqs[0],
1047                          s->range_model3.freqs[1],
1048                          s->range_model3.cnts,
1049                          s->range_model3.dectab, &temp);
1050     if (ret < 0)
1051         return ret;
1052
1053     max += temp << 8;
1054     if (min > max || min >= s->nbcount)
1055         return AVERROR_INVALIDDATA;
1056
1057     memset(s->blocks, 0, sizeof(*s->blocks) * s->nbcount);
1058
1059     while (min <= max) {
1060         int fill, count;
1061
1062         ret  = decode_value3(s, 4, &s->fill_model3.cntsum,
1063                              s->fill_model3.freqs[0],
1064                              s->fill_model3.freqs[1],
1065                              s->fill_model3.cnts,
1066                              s->fill_model3.dectab, &fill);
1067         ret |= decode_value3(s, 255, &s->count_model3.cntsum,
1068                              s->count_model3.freqs[0],
1069                              s->count_model3.freqs[1],
1070                              s->count_model3.cnts,
1071                              s->count_model3.dectab, &count);
1072         if (ret < 0)
1073             return ret;
1074         if (count <= 0)
1075             return AVERROR_INVALIDDATA;
1076
1077         while (min < s->nbcount && count-- > 0) {
1078             s->blocks[min++] = fill;
1079         }
1080     }
1081
1082     ret = av_frame_copy(s->current_frame, s->last_frame);
1083     if (ret < 0)
1084         return ret;
1085
1086     for (y = 0; y < s->nby; y++) {
1087         for (x = 0; x < s->nbx; x++) {
1088             int sy1 = 0, sy2 = 16, sx1 = 0, sx2 = 16;
1089
1090             if (s->blocks[y * s->nbx + x] == 0)
1091                 continue;
1092
1093             if (((s->blocks[y * s->nbx + x] + 1) & 1) > 0) {
1094                 ret  = decode_value3(s, 15, &s->sxy_model3[0].cntsum,
1095                                      s->sxy_model3[0].freqs[0],
1096                                      s->sxy_model3[0].freqs[1],
1097                                      s->sxy_model3[0].cnts,
1098                                      s->sxy_model3[0].dectab, &sx1);
1099                 ret |= decode_value3(s, 15, &s->sxy_model3[1].cntsum,
1100                                      s->sxy_model3[1].freqs[0],
1101                                      s->sxy_model3[1].freqs[1],
1102                                      s->sxy_model3[1].cnts,
1103                                      s->sxy_model3[1].dectab, &sy1);
1104                 ret |= decode_value3(s, 15, &s->sxy_model3[2].cntsum,
1105                                      s->sxy_model3[2].freqs[0],
1106                                      s->sxy_model3[2].freqs[1],
1107                                      s->sxy_model3[2].cnts,
1108                                      s->sxy_model3[2].dectab, &sx2);
1109                 ret |= decode_value3(s, 15, &s->sxy_model3[3].cntsum,
1110                                      s->sxy_model3[3].freqs[0],
1111                                      s->sxy_model3[3].freqs[1],
1112                                      s->sxy_model3[3].cnts,
1113                                      s->sxy_model3[3].dectab, &sy2);
1114                 if (ret < 0)
1115                     return ret;
1116
1117                 sx2++;
1118                 sy2++;
1119             }
1120             if (((s->blocks[y * s->nbx + x] + 3) & 2) > 0) {
1121                 int i, a, b, c, j, by = y * 16, bx = x * 16;
1122                 uint32_t code;
1123
1124                 a = s->rc.code & 0xFFF;
1125                 c = 1;
1126
1127                 if (a < 0x800)
1128                     c = 0;
1129                 b = 2048;
1130                 if (!c)
1131                     b = 0;
1132
1133                 code = a + ((s->rc.code >> 1) & 0xFFFFF800) - b;
1134                 while (code < 0x800000 && bytestream2_get_bytes_left(gb) > 0)
1135                     code = bytestream2_get_byteu(gb) | (code << 8);
1136                 s->rc.code = code;
1137
1138                 sync_code3(gb, &s->rc);
1139
1140                 if (!c) {
1141                     ret  = decode_value3(s, 511, &s->mv_model3[0].cntsum,
1142                                          s->mv_model3[0].freqs[0],
1143                                          s->mv_model3[0].freqs[1],
1144                                          s->mv_model3[0].cnts,
1145                                          s->mv_model3[0].dectab, &mvx);
1146                     ret |= decode_value3(s, 511, &s->mv_model3[1].cntsum,
1147                                          s->mv_model3[1].freqs[0],
1148                                          s->mv_model3[1].freqs[1],
1149                                          s->mv_model3[1].cnts,
1150                                          s->mv_model3[1].dectab, &mvy);
1151                     if (ret < 0)
1152                         return ret;
1153
1154                     mvx -= 256;
1155                     mvy -= 256;
1156                 }
1157
1158                 if (by + mvy + sy1 < 0 || bx + mvx + sx1 < 0 ||
1159                     by + mvy + sy1 >= avctx->height || bx + mvx + sx1 >= avctx->width)
1160                     return AVERROR_INVALIDDATA;
1161
1162                 for (i = 0; i < sy2 - sy1 && (by + sy1 + i) < avctx->height && (by + mvy + sy1 + i) < avctx->height; i++) {
1163                     for (j = 0; j < sx2 - sx1 && (bx + sx1 + j) < avctx->width && (bx + mvx + sx1 + j) < avctx->width; j++) {
1164                         dst[(by + i + sy1) * linesize + bx + sx1 + j] = prev[(by + mvy + sy1 + i) * plinesize + bx + sx1 + mvx + j];
1165                     }
1166                 }
1167             } else {
1168                 int run, bx = x * 16 + sx1, by = y * 16 + sy1;
1169                 uint32_t clr, ptype = 0, r, g, b;
1170
1171                 for (; by < y * 16 + sy2 && by < avctx->height;) {
1172                     ret = decode_value3(s, 5, &s->op_model3[ptype].cntsum,
1173                                         s->op_model3[ptype].freqs[0],
1174                                         s->op_model3[ptype].freqs[1],
1175                                         s->op_model3[ptype].cnts,
1176                                         s->op_model3[ptype].dectab, &ptype);
1177                     if (ret < 0)
1178                         return ret;
1179                     if (ptype == 0) {
1180                         ret = decode_units3(s, &r, &g, &b, &cx, &cx1);
1181                         if (ret < 0)
1182                             return ret;
1183
1184                         clr = (b << 16) + (g << 8) + r;
1185                     }
1186                     if (ptype > 5)
1187                         return AVERROR_INVALIDDATA;
1188                     ret = decode_value3(s, 255, &s->run_model3[ptype].cntsum,
1189                                         s->run_model3[ptype].freqs[0],
1190                                         s->run_model3[ptype].freqs[1],
1191                                         s->run_model3[ptype].cnts,
1192                                         s->run_model3[ptype].dectab, &run);
1193                     if (ret < 0)
1194                         return ret;
1195                     if (run <= 0)
1196                         return AVERROR_INVALIDDATA;
1197
1198                     ret = decode_run_p(avctx, ptype, run, x, y, clr,
1199                                        dst, prev, linesize, plinesize, &bx, &by,
1200                                        backstep, sx1, sx2, &cx, &cx1);
1201                     if (ret < 0)
1202                         return ret;
1203                 }
1204             }
1205         }
1206     }
1207
1208     return 0;
1209 }