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 
renew_table3(uint32_t nsym,uint32_t * cntsum,uint16_t * freqs,uint16_t * freqs1,uint16_t * cnts,uint8_t * dectab)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 
reinit_tables3(SCPRContext * s)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 
decode3(GetByteContext * gb,RangeCoder * rc,uint32_t a,uint32_t b)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 
rescale(PixelModel3 * m,int * totfr)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 
add_symbol(PixelModel3 * m,int index,uint32_t symbol,int * totfr,int max)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 
decode_adaptive45(PixelModel3 * m,int rccode,uint32_t * value,uint16_t * a,uint16_t * b,uint32_t * c,int max)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 
update_model6_to_7(PixelModel3 * m)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         for (i = 0; i < k - p; i++)
238             n.dectab[p + i] = j;
239         e += f;
240     }
241 
242     memcpy(m, &n, sizeof(n));
243 
244     return 0;
245 }
246 
calc_sum(PixelModel3 * m)247 static void calc_sum(PixelModel3 *m)
248 {
249     uint32_t a;
250     int len;
251 
252     len = m->length;
253     a = 256 - m->size << (m->fshift > 0 ? m->fshift - 1 : 0);
254     for (int c = 0; c < len; c++)
255         a += m->cnts[c];
256     m->cnts[len] = a;
257 }
258 
rescale_dec(PixelModel3 * m)259 static void rescale_dec(PixelModel3 *m)
260 {
261     uint16_t cnts[256] = {0};
262     uint16_t freqs[512] = {0};
263     int b, c, e, g;
264     uint32_t a;
265 
266     for (a = 1 << (0 < m->fshift ? m->fshift - 1 : 0), b = 0; b < 256; b++)
267         cnts[b] = a;
268 
269     for (a = 0, b = m->size; a < b; a++)
270         cnts[m->symbols[a]] = m->cnts[a];
271 
272     for (b = a = 0; b < 256; b++) {
273         freqs[2 * b] = cnts[b];
274         freqs[2 * b + 1] = a;
275         a += cnts[b];
276     }
277 
278     if (m->fshift > 0)
279         m->fshift--;
280 
281     a = 256 - m->size << (0 < m->fshift ? m->fshift - 1 : 0);
282     for (b = 0, c = m->size; b < c; b++) {
283         m->cnts[b] -= m->cnts[b] >> 1;
284         a = a + m->cnts[b];
285         e = m->symbols[b];
286         g = freqs[2 * e + 1];
287         m->freqs[2 * b] = freqs[2 * e];
288         m->freqs[2 * b + 1] = g;
289     }
290     m->cnts[m->length] = a;
291 }
292 
update_model5_to_6(PixelModel3 * m,uint8_t value)293 static int update_model5_to_6(PixelModel3 *m, uint8_t value)
294 {
295     PixelModel3 n = {0};
296     int c, d, e, f, g, k, q, p;
297 
298     n.type = 6;
299     n.length = 32;
300 
301     for (c = m->size, d = 256 - c, e = 0; e < c; e++)
302         d = d + m->freqs[e];
303 
304     for (e = 0; d <= 2048; e++)
305         d <<= 1;
306 
307     for (q = d = 0, g = q = 0; g < c; g++) {
308         p = m->symbols[g];
309         d = d + (p - q);
310         q = m->freqs[g];
311         k = q << e;
312         n.freqs[2 * g] = k;
313         n.freqs[2 * g + 1] = d << e;
314         n.cnts[g] = k - (k >> 1);
315         n.symbols[g] = p;
316         d += q;
317         q = p + 1;
318     }
319 
320     n.fshift = e;
321     e = 1 << n.fshift;
322     d = 0;
323     if (value > 0) {
324         d = -1;
325         for (p = f = g = 0; p < c; p++) {
326             k = n.symbols[p];
327             if (k > d && k < value) {
328                 d = k;
329                 g = n.freqs[2 * p];
330                 f = n.freqs[2 * p + 1];
331             }
332         }
333         d = 0 < g ? f + g + (value - d - 1 << n.fshift) : value << n.fshift;
334     }
335     n.freqs[2 * c] = e;
336     n.freqs[2 * c + 1] = d;
337     n.cnts[c] = e - (e >> 1);
338     n.symbols[c] = value;
339     n.size = c + 1;
340     e = 25 << n.fshift;
341     n.cnts[c] += e;
342     n.cnts[32] += e;
343     if (n.cnts[32] + e > 4096)
344         rescale_dec(&n);
345 
346     calc_sum(&n);
347     for (c = 0, e = n.size - 1; c < e; c++) {
348         for (g = c + 1, f = n.size; g < f; g++) {
349             if (q = n.freqs[2 * g], k = n.freqs[2 * c], q > k) {
350                 int l = n.freqs[2 * c + 1];
351                 int h = n.freqs[2 * g + 1];
352                 n.freqs[2 * c] = q;
353                 n.freqs[2 * c + 1] = h;
354                 n.freqs[2 * g] = k;
355                 n.freqs[2 * g + 1] = l;
356                 FFSWAP(uint16_t, n.cnts[c], n.cnts[g]);
357                 FFSWAP(uint8_t, n.symbols[c], n.symbols[g]);
358             }
359         }
360     }
361 
362     memcpy(m, &n, sizeof(n));
363 
364     return 0;
365 }
366 
grow_dec(PixelModel3 * m)367 static void grow_dec(PixelModel3 *m)
368 {
369     int a;
370 
371     a = 2 * m->length;
372     m->cnts[2 * m->length] = m->cnts[m->length];
373     m->length = a;
374 }
375 
add_dec(PixelModel3 * m,int sym,int f1,int f2)376 static int add_dec(PixelModel3 *m, int sym, int f1, int f2)
377 {
378     int size;
379 
380     if (m->size >= 40 || m->size >= m->length)
381         return -1;
382 
383     size = m->size;
384     m->symbols[size] = sym;
385     m->freqs[2 * size] = f1;
386     m->freqs[2 * size + 1] = f2;
387     m->cnts[size] = f1 - (f1 >> 1);
388     m->size++;
389 
390     return size;
391 }
392 
incr_cntdec(PixelModel3 * m,int a)393 static void incr_cntdec(PixelModel3 *m, int a)
394 {
395     int b, len, d, e, g;
396 
397     b = 25 << m->fshift;
398     len = m->length;
399     m->cnts[a] += b;
400     m->cnts[len] += b;
401     if (a > 0 && m->cnts[a] > m->cnts[a - 1]) {
402         FFSWAP(uint16_t, m->cnts[a], m->cnts[a - 1]);
403         d = m->freqs[2 * a];
404         e = m->freqs[2 * a + 1];
405         g = m->freqs[2 * (a - 1) + 1];
406         m->freqs[2 * a] = m->freqs[2 * (a - 1)];
407         m->freqs[2 * a + 1] = g;
408         g = a - 1;
409         m->freqs[2 * g] = d;
410         m->freqs[2 * g + 1] = e;
411         FFSWAP(uint8_t, m->symbols[a], m->symbols[a - 1]);
412     }
413 
414     if (m->cnts[len] + b > 4096)
415         rescale_dec(m);
416 }
417 
decode_adaptive6(PixelModel3 * m,uint32_t code,uint32_t * value,uint16_t * a,uint16_t * b)418 static int decode_adaptive6(PixelModel3 *m, uint32_t code, uint32_t *value,
419                             uint16_t *a, uint16_t *b)
420 {
421     int c, d, e, f, g, q;
422 
423     for (c = 0, d = 0, e = 0, f = 0, g = 0, q = m->size; g < q; g++) {
424         uint32_t p = m->freqs[2 * g + 1];
425 
426         if (p <= code) {
427             uint32_t k = m->freqs[2 * g];
428 
429             if (p + k > code) {
430                 *value = m->symbols[g];
431                 *a = k;
432                 *b = p;
433                 incr_cntdec(m, g);
434                 return 1;
435             }
436 
437             if (p >= d) {
438                 c = k;
439                 d = p;
440                 e = m->symbols[g];
441             }
442         }
443     }
444 
445     g = 1 << m->fshift;
446     q = f = 0;
447 
448     if (c > 0) {
449         f = code - (d + c) >> m->fshift;
450         q = f + e + 1;
451         f = d + c + (f << m->fshift);
452     } else {
453         q = code >> m->fshift;
454         f = q << m->fshift;
455     }
456 
457     *a = g;
458     *b = f;
459     *value = q;
460 
461     c = add_dec(m, q, g, f);
462     if (c < 0) {
463         if (m->length == 64)
464             return 0;
465         grow_dec(m);
466         c = add_dec(m, q, g, f);
467     }
468 
469     incr_cntdec(m, c);
470     return 1;
471 }
472 
cmpbytes(const void * p1,const void * p2)473 static int cmpbytes(const void *p1, const void *p2)
474 {
475     int left  = *(const uint8_t *)p1;
476     int right = *(const uint8_t *)p2;
477     return FFDIFFSIGN(left, right);
478 }
479 
update_model1_to_2(PixelModel3 * m,uint32_t val)480 static int update_model1_to_2(PixelModel3 *m, uint32_t val)
481 {
482     PixelModel3 n = {0};
483     int i, b;
484 
485     n.type = 2;
486     n.size = m->size + 1;
487     b = m->size;
488     for (i = 0; i < b; i++)
489         n.symbols[i] = m->symbols[i];
490     n.symbols[b] = val;
491 
492     memcpy(m, &n, sizeof(n));
493 
494     return 0;
495 }
496 
update_model1_to_4(PixelModel3 * m,uint32_t val)497 static int update_model1_to_4(PixelModel3 *m, uint32_t val)
498 {
499     PixelModel3 n = {0};
500     int size, i;
501 
502     size = m->size;
503     n.type = 4;
504     n.size = size;
505     for (i = 0; i < n.size; i++) {
506         n.symbols[i] = m->symbols[i];
507     }
508     AV_QSORT(n.symbols, size, uint8_t, cmpbytes);
509     for (i = 0; i < n.size; i++) {
510         if (val == n.symbols[i]) {
511             n.freqs[i] = 100;
512             n.maxpos = i;
513         } else {
514             n.freqs[i] = 50;
515         }
516     }
517 
518     memcpy(m, &n, sizeof(n));
519 
520     return 0;
521 }
522 
update_model1_to_5(PixelModel3 * m,uint32_t val)523 static int update_model1_to_5(PixelModel3 *m, uint32_t val)
524 {
525     PixelModel3 n = {0};
526     int i, size, freqs;
527     uint32_t a;
528 
529     size = m->size;
530     n.size = size;
531     for (i = 0; i < size; i++) {
532         n.symbols[i] = m->symbols[i];
533     }
534     AV_QSORT(n.symbols, size, uint8_t, cmpbytes);
535     size = n.size;
536     for (i = 0; i < size; i++) {
537         if (val == n.symbols[i]) {
538             n.freqs[i] = 100;
539             n.maxpos = i;
540         } else {
541             n.freqs[i] = 50;
542         }
543     }
544     a = 256 - size;
545     for (i = 0; i < size; i++, a += freqs)
546         freqs = n.freqs[i];
547     n.type = 5;
548     n.cntsum = a;
549 
550     memcpy(m, &n, sizeof(n));
551 
552     return 0;
553 }
554 
decode_static1(PixelModel3 * m,uint32_t val)555 static int decode_static1(PixelModel3 *m, uint32_t val)
556 {
557     uint32_t size;
558 
559     size = m->size;
560     for (int i = 0; i < size; i++) {
561         if (val == m->symbols[i]) {
562             if (size <= 4)
563                 return update_model1_to_4(m, val);
564             else
565                 return update_model1_to_5(m, val);
566         }
567     }
568 
569     if (size >= 14)
570         return update_model1_to_2(m, val);
571 
572     m->symbols[size] = val;
573     m->size++;
574     return 0;
575 }
576 
update_model2_to_6(PixelModel3 * m,uint8_t value,int a4)577 static int update_model2_to_6(PixelModel3 *m, uint8_t value, int a4)
578 {
579     PixelModel3 n = {0};
580     int c, d, e, f, g, q;
581 
582     n.type = 6;
583     n.length = a4;
584 
585     memset(n.symbols, 1u, a4);
586 
587     c = m->size;
588     d = 256 - c + (64 * c + 64);
589     for (e = 0; d <= 2048; e++) {
590         d <<= 1;
591     }
592 
593     g = q = 0;
594     AV_QSORT(m->symbols, c, uint8_t, cmpbytes);
595     for (f = d = 0; f < c; f++) {
596         int p = f;
597         int k = m->symbols[p];
598         int l;
599         g = g + (k - q);
600 
601         if (k == value) {
602             d = p;
603             q = 128;
604         } else {
605             q = 64;
606         }
607         l = q << e;
608         n.freqs[2 * p] = l;
609         n.freqs[2 * p + 1] = g << e;
610         n.symbols[p] = k;
611         n.cnts[p] = l - (l >> 1);
612         g += q;
613         q = k + 1;
614     }
615     n.size = c;
616     n.fshift = e;
617     calc_sum(&n);
618 
619     if (d > 0) {
620         c = n.freqs[0];
621         e = n.freqs[1];
622         g = n.freqs[2 * d + 1];
623         n.freqs[0] = n.freqs[2 * d];
624         n.freqs[1] = g;
625         n.freqs[2 * d] = c;
626         n.freqs[2 * d + 1] = e;
627         FFSWAP(uint16_t, n.cnts[0], n.cnts[d]);
628         FFSWAP(uint8_t, n.symbols[0], n.symbols[d]);
629     }
630 
631     memcpy(m, &n, sizeof(n));
632 
633     return 0;
634 }
635 
update_model2_to_3(PixelModel3 * m,uint32_t val)636 static int update_model2_to_3(PixelModel3 *m, uint32_t val)
637 {
638     PixelModel3 n = {0};
639     uint32_t size;
640 
641     n.type = 3;
642     n.size = m->size + 1;
643 
644     size = m->size;
645     for (int i = 0; i < size; i++)
646         n.symbols[i] = m->symbols[i];
647     n.symbols[size] = val;
648 
649     memcpy(m, &n, sizeof(n));
650 
651     return 0;
652 }
653 
decode_static2(PixelModel3 * m,uint32_t val)654 static int decode_static2(PixelModel3 *m, uint32_t val)
655 {
656     uint32_t size;
657 
658     size = m->size;
659     for (int i = 0; i < size; i++) {
660         if (val == m->symbols[i]) {
661             int a;
662 
663             if (m->size <= 32)
664                 a = 32;
665             else
666                 a = 64;
667             return update_model2_to_6(m, val, a);
668         }
669     }
670 
671     if (size >= 64)
672         return update_model2_to_3(m, val);
673 
674     m->symbols[size] = val;
675     m->size++;
676 
677     return 0;
678 }
679 
update_model3_to_7(PixelModel3 * m,uint8_t value)680 static int update_model3_to_7(PixelModel3 *m, uint8_t value)
681 {
682     PixelModel3 n = {0};
683     int c, d, e, f, g, q;
684 
685     n.type = 7;
686 
687     for (c = 0; c < 256; c++) {
688         d = c;
689         n.freqs[d] = 1;
690         n.cnts[d] = 1;
691     }
692 
693     for (c = m->size, d = (4096 - (256 - c)) / (c + 1) | 0, e = d - (d >> 1), g = 0; g < c;) {
694         q = g++;
695         q = m->symbols[q];
696         n.freqs[q] = d;
697         n.cnts[q] = e;
698     }
699     n.freqs[value] += d;
700     n.cnts[value] += 16;
701     for (d = c = n.cntsum = 0; 256 > d; d++) {
702         e = d;
703         n.cntsum += n.cnts[e];
704         n.freqs1[e] = c;
705         for (g = n.freqs[e], q = c + 128 - 1 >> 7, f = (c + g - 1 >> 7) + 1; q < f; q++) {
706             n.dectab[q] = e;
707         }
708         c += g;
709     }
710 
711     memcpy(m, &n, sizeof(n));
712 
713     return 0;
714 }
715 
decode_static3(PixelModel3 * m,uint32_t val)716 static int decode_static3(PixelModel3 *m, uint32_t val)
717 {
718     uint32_t size = m->size;
719 
720     for (int i = 0; i < size; i++) {
721         if (val == m->symbols[i])
722             return update_model3_to_7(m, val);
723     }
724 
725     if (size >= 256)
726         return 0;
727 
728     m->symbols[size] = val;
729     m->size++;
730     return 0;
731 }
732 
sync_code3(GetByteContext * gb,RangeCoder * rc)733 static void sync_code3(GetByteContext *gb, RangeCoder *rc)
734 {
735     rc->code1++;
736     if (rc->code1 == 0x20000) {
737         rc->code = bytestream2_get_le32(gb);
738         rc->code1 = 0;
739     }
740 }
741 
decode_value3(SCPRContext * s,uint32_t max,uint32_t * cntsum,uint16_t * freqs1,uint16_t * freqs2,uint16_t * cnts,uint8_t * dectable,uint32_t * value)742 static int decode_value3(SCPRContext *s, uint32_t max, uint32_t *cntsum,
743                          uint16_t *freqs1, uint16_t *freqs2,
744                          uint16_t *cnts, uint8_t *dectable,
745                          uint32_t *value)
746 {
747     GetByteContext *gb = &s->gb;
748     RangeCoder *rc = &s->rc;
749     uint32_t r, y, a, b, e, g, q;
750 
751     r = dectable[(rc->code & 0xFFFu) >> 7];
752     if (r < max) {
753         while (freqs2[r + 1] <= (rc->code & 0xFFF)) {
754             if (++r >= max)
755                 break;
756         }
757     }
758 
759     if (r > max)
760         return AVERROR_INVALIDDATA;
761 
762     cnts[r] += 16;
763     a = freqs1[r];
764     b = freqs2[r];
765     *cntsum += 16;
766     if (*cntsum + 16 > 4096) {
767         *cntsum = 0;
768         for (int c = 0, i = 0; i < max + 1; i++) {
769             e = cnts[i];
770             freqs2[i] = c;
771             freqs1[i] = e;
772             g = (c + 127) >> 7;
773             c += e;
774             q = ((c - 1) >> 7) + 1;
775             if (q > g) {
776                 for (int j = 0; j < q - g; j++)
777                     dectable[j + g] = i;
778             }
779             y = e - (e >> 1);
780             cnts[i] = y;
781             *cntsum += y;
782         }
783     }
784 
785     decode3(gb, rc, a, b);
786     sync_code3(gb, rc);
787 
788     *value = r;
789 
790     return 0;
791 }
792 
calc_sum5(PixelModel3 * m)793 static void calc_sum5(PixelModel3 *m)
794 {
795     uint32_t a;
796 
797     a = 256 - m->size;
798     for (int b = 0; b < m->size; b++)
799         a += m->freqs[b];
800     m->cntsum = a;
801 }
802 
update_model4_to_5(PixelModel3 * m,uint32_t value)803 static int update_model4_to_5(PixelModel3 *m, uint32_t value)
804 {
805     PixelModel3 n = {0};
806     int c, e, g, totfr;
807 
808     n.type = 5;
809 
810     for (c = 0, e = 0; c < m->size && m->symbols[c] < value; c++) {
811         n.symbols[c] = m->symbols[c];
812         e += n.freqs[c] = m->freqs[c];
813     }
814 
815     g = c;
816     n.symbols[g] = value;
817     e += n.freqs[g++] = 50;
818     for (; c < m->size; g++, c++) {
819         n.symbols[g] = m->symbols[c];
820         e += n.freqs[g] = m->freqs[c];
821     }
822     n.size = m->size + 1;
823     if (e > 4096)
824         rescale(&n, &totfr);
825 
826     calc_sum5(&n);
827 
828     memcpy(m, &n, sizeof(n));
829 
830     return 0;
831 }
832 
decode_unit3(SCPRContext * s,PixelModel3 * m,uint32_t code,uint32_t * value)833 static int decode_unit3(SCPRContext *s, PixelModel3 *m, uint32_t code, uint32_t *value)
834 {
835     GetByteContext *gb = &s->gb;
836     RangeCoder *rc = &s->rc;
837     uint16_t a = 0, b = 0;
838     uint32_t param;
839     int type;
840 
841     type = m->type;
842     switch (type) {
843     case 0:
844         *value = bytestream2_get_byte(&s->gb);
845         m->type = 1;
846         m->size = 1;
847         m->symbols[0] = *value;
848         sync_code3(gb, rc);
849         break;
850     case 1:
851         *value = bytestream2_get_byte(&s->gb);
852         decode_static1(m, *value);
853         sync_code3(gb, rc);
854         break;
855     case 2:
856         *value = bytestream2_get_byte(&s->gb);
857         decode_static2(m, *value);
858         sync_code3(gb, rc);
859         break;
860     case 3:
861         *value = bytestream2_get_byte(&s->gb);
862         decode_static3(m, *value);
863         sync_code3(gb, rc);
864         break;
865     case 4:
866         param = m->freqs[0] + m->freqs[1] + m->freqs[2] + m->freqs[3] + 256 - m->size;
867         if (!decode_adaptive45(m, code, value, &a, &b, &param, 4))
868             update_model4_to_5(m, *value);
869         decode3(gb, rc, a, b);
870         sync_code3(gb, rc);
871         break;
872     case 5:
873         if (!decode_adaptive45(m, code, value, &a, &b, &m->cntsum, 16))
874             update_model5_to_6(m, *value);
875         decode3(gb, rc, a, b);
876         sync_code3(gb, rc);
877         break;
878     case 6:
879         if (!decode_adaptive6(m, code, value, &a, &b)) {
880             update_model6_to_7(m);
881         }
882         decode3(gb, rc, a, b);
883         sync_code3(gb, rc);
884         break;
885     case 7:
886         return decode_value3(s, 255, &m->cntsum,
887                              m->freqs, m->freqs1,
888                              m->cnts, m->dectab, value);
889     }
890 
891     if (*value > 255)
892         return AVERROR_INVALIDDATA;
893 
894     return 0;
895 }
896 
decode_units3(SCPRContext * s,uint32_t * red,uint32_t * green,uint32_t * blue,int * cx,int * cx1)897 static int decode_units3(SCPRContext * s, uint32_t *red,
898                          uint32_t *green, uint32_t *blue,
899                          int *cx, int *cx1)
900 {
901     RangeCoder *rc = &s->rc;
902     int ret;
903 
904     ret = decode_unit3(s, &s->pixel_model3[0][*cx + *cx1], rc->code & 0xFFF, red);
905     if (ret < 0)
906         return ret;
907 
908     *cx1 = (*cx << 6) & 0xFC0;
909     *cx = *red >> 2;
910 
911     ret = decode_unit3(s, &s->pixel_model3[1][*cx + *cx1], rc->code & 0xFFF, green);
912     if (ret < 0)
913         return ret;
914 
915     *cx1 = (*cx << 6) & 0xFC0;
916     *cx = *green >> 2;
917 
918     ret = decode_unit3(s, &s->pixel_model3[2][*cx + *cx1], rc->code & 0xFFF, blue);
919     if (ret < 0)
920         return ret;
921 
922     *cx1 = (*cx << 6) & 0xFC0;
923     *cx = *blue >> 2;
924 
925     return 0;
926 }
927 
init_rangecoder3(RangeCoder * rc,GetByteContext * gb)928 static void init_rangecoder3(RangeCoder *rc, GetByteContext *gb)
929 {
930     rc->code  = bytestream2_get_le32(gb);
931     rc->code1 = 0;
932 }
933 
decompress_i3(AVCodecContext * avctx,uint32_t * dst,int linesize)934 static int decompress_i3(AVCodecContext *avctx, uint32_t *dst, int linesize)
935 {
936     SCPRContext *s = avctx->priv_data;
937     GetByteContext *gb = &s->gb;
938     RangeCoder *rc = &s->rc;
939     int cx = 0, cx1 = 0, k = 0;
940     int run, off, y = 0, x = 0, ret;
941     uint32_t backstep = linesize - avctx->width;
942     uint32_t clr = 0, lx, ly, ptype, r, g, b;
943 
944     bytestream2_skip(gb, 1);
945     init_rangecoder3(rc, gb);
946     reinit_tables3(s);
947 
948     while (k < avctx->width + 1) {
949         ret = decode_units3(s, &r, &g, &b, &cx, &cx1);
950         if (ret < 0)
951             return ret;
952         ret = decode_value3(s, 255, &s->run_model3[0].cntsum,
953                             s->run_model3[0].freqs[0],
954                             s->run_model3[0].freqs[1],
955                             s->run_model3[0].cnts,
956                             s->run_model3[0].dectab, &run);
957         if (ret < 0)
958             return ret;
959         if (run <= 0)
960             return AVERROR_INVALIDDATA;
961 
962         clr = (b << 16) + (g << 8) + r;
963         k += run;
964         while (run-- > 0) {
965             if (y >= avctx->height)
966                 return AVERROR_INVALIDDATA;
967 
968             dst[y * linesize + x] = clr;
969             lx = x;
970             ly = y;
971             x++;
972             if (x >= avctx->width) {
973                 x = 0;
974                 y++;
975             }
976         }
977     }
978     off = -linesize - 1;
979     ptype = 0;
980 
981     while (x < avctx->width && y < avctx->height) {
982         ret = decode_value3(s, 5, &s->op_model3[ptype].cntsum,
983                             s->op_model3[ptype].freqs[0],
984                             s->op_model3[ptype].freqs[1],
985                             s->op_model3[ptype].cnts,
986                             s->op_model3[ptype].dectab, &ptype);
987         if (ret < 0)
988             return ret;
989         if (ptype == 0) {
990             ret = decode_units3(s, &r, &g, &b, &cx, &cx1);
991             if (ret < 0)
992                 return ret;
993             clr = (b << 16) + (g << 8) + r;
994         }
995         if (ptype > 5)
996             return AVERROR_INVALIDDATA;
997         ret = decode_value3(s, 255, &s->run_model3[ptype].cntsum,
998                             s->run_model3[ptype].freqs[0],
999                             s->run_model3[ptype].freqs[1],
1000                             s->run_model3[ptype].cnts,
1001                             s->run_model3[ptype].dectab, &run);
1002         if (ret < 0)
1003             return ret;
1004         if (run <= 0)
1005             return AVERROR_INVALIDDATA;
1006 
1007         ret = decode_run_i(avctx, ptype, run, &x, &y, clr,
1008                            dst, linesize, &lx, &ly,
1009                            backstep, off, &cx, &cx1);
1010         if (ret < 0)
1011             return ret;
1012     }
1013 
1014     return 0;
1015 }
1016 
decompress_p3(AVCodecContext * avctx,uint32_t * dst,int linesize,uint32_t * prev,int plinesize)1017 static int decompress_p3(AVCodecContext *avctx,
1018                          uint32_t *dst, int linesize,
1019                          uint32_t *prev, int plinesize)
1020 {
1021     SCPRContext *s = avctx->priv_data;
1022     GetByteContext *gb = &s->gb;
1023     int ret, temp, min, max, x, y, cx = 0, cx1 = 0;
1024     int backstep = linesize - avctx->width;
1025     int mvx = 0, mvy = 0;
1026 
1027     if (bytestream2_get_byte(gb) == 0)
1028         return 1;
1029     init_rangecoder3(&s->rc, gb);
1030 
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, &min);
1036     ret |= decode_value3(s, 255, &s->range_model3.cntsum,
1037                          s->range_model3.freqs[0],
1038                          s->range_model3.freqs[1],
1039                          s->range_model3.cnts,
1040                          s->range_model3.dectab, &temp);
1041     if (ret < 0)
1042         return ret;
1043 
1044     min += temp << 8;
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, &max);
1050     ret |= decode_value3(s, 255, &s->range_model3.cntsum,
1051                          s->range_model3.freqs[0],
1052                          s->range_model3.freqs[1],
1053                          s->range_model3.cnts,
1054                          s->range_model3.dectab, &temp);
1055     if (ret < 0)
1056         return ret;
1057 
1058     max += temp << 8;
1059     if (min > max || min >= s->nbcount)
1060         return AVERROR_INVALIDDATA;
1061 
1062     memset(s->blocks, 0, sizeof(*s->blocks) * s->nbcount);
1063 
1064     while (min <= max) {
1065         int fill, count;
1066 
1067         ret  = decode_value3(s, 4, &s->fill_model3.cntsum,
1068                              s->fill_model3.freqs[0],
1069                              s->fill_model3.freqs[1],
1070                              s->fill_model3.cnts,
1071                              s->fill_model3.dectab, &fill);
1072         ret |= decode_value3(s, 255, &s->count_model3.cntsum,
1073                              s->count_model3.freqs[0],
1074                              s->count_model3.freqs[1],
1075                              s->count_model3.cnts,
1076                              s->count_model3.dectab, &count);
1077         if (ret < 0)
1078             return ret;
1079         if (count <= 0)
1080             return AVERROR_INVALIDDATA;
1081 
1082         while (min < s->nbcount && count-- > 0) {
1083             s->blocks[min++] = fill;
1084         }
1085     }
1086 
1087     ret = av_frame_copy(s->current_frame, s->last_frame);
1088     if (ret < 0)
1089         return ret;
1090 
1091     for (y = 0; y < s->nby; y++) {
1092         for (x = 0; x < s->nbx; x++) {
1093             int sy1 = 0, sy2 = 16, sx1 = 0, sx2 = 16;
1094 
1095             if (s->blocks[y * s->nbx + x] == 0)
1096                 continue;
1097 
1098             if (((s->blocks[y * s->nbx + x] + 1) & 1) > 0) {
1099                 ret  = decode_value3(s, 15, &s->sxy_model3[0].cntsum,
1100                                      s->sxy_model3[0].freqs[0],
1101                                      s->sxy_model3[0].freqs[1],
1102                                      s->sxy_model3[0].cnts,
1103                                      s->sxy_model3[0].dectab, &sx1);
1104                 ret |= decode_value3(s, 15, &s->sxy_model3[1].cntsum,
1105                                      s->sxy_model3[1].freqs[0],
1106                                      s->sxy_model3[1].freqs[1],
1107                                      s->sxy_model3[1].cnts,
1108                                      s->sxy_model3[1].dectab, &sy1);
1109                 ret |= decode_value3(s, 15, &s->sxy_model3[2].cntsum,
1110                                      s->sxy_model3[2].freqs[0],
1111                                      s->sxy_model3[2].freqs[1],
1112                                      s->sxy_model3[2].cnts,
1113                                      s->sxy_model3[2].dectab, &sx2);
1114                 ret |= decode_value3(s, 15, &s->sxy_model3[3].cntsum,
1115                                      s->sxy_model3[3].freqs[0],
1116                                      s->sxy_model3[3].freqs[1],
1117                                      s->sxy_model3[3].cnts,
1118                                      s->sxy_model3[3].dectab, &sy2);
1119                 if (ret < 0)
1120                     return ret;
1121 
1122                 sx2++;
1123                 sy2++;
1124             }
1125             if (((s->blocks[y * s->nbx + x] + 3) & 2) > 0) {
1126                 int i, a, b, c, j, by = y * 16, bx = x * 16;
1127                 uint32_t code;
1128 
1129                 a = s->rc.code & 0xFFF;
1130                 c = 1;
1131 
1132                 if (a < 0x800)
1133                     c = 0;
1134                 b = 2048;
1135                 if (!c)
1136                     b = 0;
1137 
1138                 code = a + ((s->rc.code >> 1) & 0xFFFFF800) - b;
1139                 while (code < 0x800000 && bytestream2_get_bytes_left(gb) > 0)
1140                     code = bytestream2_get_byteu(gb) | (code << 8);
1141                 s->rc.code = code;
1142 
1143                 sync_code3(gb, &s->rc);
1144 
1145                 if (!c) {
1146                     ret  = decode_value3(s, 511, &s->mv_model3[0].cntsum,
1147                                          s->mv_model3[0].freqs[0],
1148                                          s->mv_model3[0].freqs[1],
1149                                          s->mv_model3[0].cnts,
1150                                          s->mv_model3[0].dectab, &mvx);
1151                     ret |= decode_value3(s, 511, &s->mv_model3[1].cntsum,
1152                                          s->mv_model3[1].freqs[0],
1153                                          s->mv_model3[1].freqs[1],
1154                                          s->mv_model3[1].cnts,
1155                                          s->mv_model3[1].dectab, &mvy);
1156                     if (ret < 0)
1157                         return ret;
1158 
1159                     mvx -= 256;
1160                     mvy -= 256;
1161                 }
1162 
1163                 if (by + mvy + sy1 < 0 || bx + mvx + sx1 < 0 ||
1164                     by + mvy + sy1 >= avctx->height || bx + mvx + sx1 >= avctx->width)
1165                     return AVERROR_INVALIDDATA;
1166 
1167                 for (i = 0; i < sy2 - sy1 && (by + sy1 + i) < avctx->height && (by + mvy + sy1 + i) < avctx->height; i++) {
1168                     for (j = 0; j < sx2 - sx1 && (bx + sx1 + j) < avctx->width && (bx + mvx + sx1 + j) < avctx->width; j++) {
1169                         dst[(by + i + sy1) * linesize + bx + sx1 + j] = prev[(by + mvy + sy1 + i) * plinesize + bx + sx1 + mvx + j];
1170                     }
1171                 }
1172             } else {
1173                 int run, bx = x * 16 + sx1, by = y * 16 + sy1;
1174                 uint32_t clr, ptype = 0, r, g, b;
1175 
1176                 for (; by < y * 16 + sy2 && by < avctx->height;) {
1177                     ret = decode_value3(s, 5, &s->op_model3[ptype].cntsum,
1178                                         s->op_model3[ptype].freqs[0],
1179                                         s->op_model3[ptype].freqs[1],
1180                                         s->op_model3[ptype].cnts,
1181                                         s->op_model3[ptype].dectab, &ptype);
1182                     if (ret < 0)
1183                         return ret;
1184                     if (ptype == 0) {
1185                         ret = decode_units3(s, &r, &g, &b, &cx, &cx1);
1186                         if (ret < 0)
1187                             return ret;
1188 
1189                         clr = (b << 16) + (g << 8) + r;
1190                     }
1191                     if (ptype > 5)
1192                         return AVERROR_INVALIDDATA;
1193                     ret = decode_value3(s, 255, &s->run_model3[ptype].cntsum,
1194                                         s->run_model3[ptype].freqs[0],
1195                                         s->run_model3[ptype].freqs[1],
1196                                         s->run_model3[ptype].cnts,
1197                                         s->run_model3[ptype].dectab, &run);
1198                     if (ret < 0)
1199                         return ret;
1200                     if (run <= 0)
1201                         return AVERROR_INVALIDDATA;
1202 
1203                     ret = decode_run_p(avctx, ptype, run, x, y, clr,
1204                                        dst, prev, linesize, plinesize, &bx, &by,
1205                                        backstep, sx1, sx2, &cx, &cx1);
1206                     if (ret < 0)
1207                         return ret;
1208                 }
1209             }
1210         }
1211     }
1212 
1213     return 0;
1214 }
1215