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         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 
calc_sum(PixelModel3 * m)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 
rescale_dec(PixelModel3 * m)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 
update_model5_to_6(PixelModel3 * m,uint8_t value)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 
grow_dec(PixelModel3 * m)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 
add_dec(PixelModel3 * m,int sym,int f1,int f2)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 
incr_cntdec(PixelModel3 * m,int a)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 
decode_adaptive6(PixelModel3 * m,uint32_t code,uint32_t * value,uint16_t * a,uint16_t * b)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 
cmpbytes(const void * p1,const void * p2)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 
update_model1_to_2(PixelModel3 * m,uint32_t val)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 
update_model1_to_4(PixelModel3 * m,uint32_t val)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 
update_model1_to_5(PixelModel3 * m,uint32_t val)525 static int update_model1_to_5(PixelModel3 *m, uint32_t val)
526 {
527     PixelModel3 n = {0};
528     int i, size, freqs;
529     uint32_t a;
530 
531     size = m->size;
532     n.size = size;
533     for (i = 0; i < size; i++) {
534         n.symbols[i] = m->symbols[i];
535     }
536     AV_QSORT(n.symbols, size, uint8_t, cmpbytes);
537     size = n.size;
538     for (i = 0; i < size; i++) {
539         if (val == n.symbols[i]) {
540             n.freqs[i] = 100;
541             n.maxpos = i;
542         } else {
543             n.freqs[i] = 50;
544         }
545     }
546     a = 256 - size;
547     for (i = 0; i < size; i++, a += freqs)
548         freqs = n.freqs[i];
549     n.type = 5;
550     n.cntsum = a;
551 
552     memcpy(m, &n, sizeof(n));
553 
554     return 0;
555 }
556 
decode_static1(PixelModel3 * m,uint32_t val)557 static int decode_static1(PixelModel3 *m, uint32_t val)
558 {
559     uint32_t size;
560 
561     size = m->size;
562     for (int i = 0; i < size; i++) {
563         if (val == m->symbols[i]) {
564             if (size <= 4)
565                 return update_model1_to_4(m, val);
566             else
567                 return update_model1_to_5(m, val);
568         }
569     }
570 
571     if (size >= 14)
572         return update_model1_to_2(m, val);
573 
574     m->symbols[size] = val;
575     m->size++;
576     return 0;
577 }
578 
update_model2_to_6(PixelModel3 * m,uint8_t value,int a4)579 static int update_model2_to_6(PixelModel3 *m, uint8_t value, int a4)
580 {
581     PixelModel3 n = {0};
582     int c, d, e, f, g, q;
583 
584     n.type = 6;
585     n.length = a4;
586 
587     memset(n.symbols, 1u, a4);
588 
589     c = m->size;
590     d = 256 - c + (64 * c + 64);
591     for (e = 0; d <= 2048; e++) {
592         d <<= 1;
593     }
594 
595     g = q = 0;
596     AV_QSORT(m->symbols, c, uint8_t, cmpbytes);
597     for (f = d = 0; f < c; f++) {
598         int p = f;
599         int k = m->symbols[p];
600         int l;
601         g = g + (k - q);
602 
603         if (k == value) {
604             d = p;
605             q = 128;
606         } else {
607             q = 64;
608         }
609         l = q << e;
610         n.freqs[2 * p] = l;
611         n.freqs[2 * p + 1] = g << e;
612         n.symbols[p] = k;
613         n.cnts[p] = l - (l >> 1);
614         g += q;
615         q = k + 1;
616     }
617     n.size = c;
618     n.fshift = e;
619     calc_sum(&n);
620 
621     if (d > 0) {
622         c = n.freqs[0];
623         e = n.freqs[1];
624         g = n.freqs[2 * d + 1];
625         n.freqs[0] = n.freqs[2 * d];
626         n.freqs[1] = g;
627         n.freqs[2 * d] = c;
628         n.freqs[2 * d + 1] = e;
629         FFSWAP(uint16_t, n.cnts[0], n.cnts[d]);
630         FFSWAP(uint8_t, n.symbols[0], n.symbols[d]);
631     }
632 
633     memcpy(m, &n, sizeof(n));
634 
635     return 0;
636 }
637 
update_model2_to_3(PixelModel3 * m,uint32_t val)638 static int update_model2_to_3(PixelModel3 *m, uint32_t val)
639 {
640     PixelModel3 n = {0};
641     uint32_t size;
642 
643     n.type = 3;
644     n.size = m->size + 1;
645 
646     size = m->size;
647     for (int i = 0; i < size; i++)
648         n.symbols[i] = m->symbols[i];
649     n.symbols[size] = val;
650 
651     memcpy(m, &n, sizeof(n));
652 
653     return 0;
654 }
655 
decode_static2(PixelModel3 * m,uint32_t val)656 static int decode_static2(PixelModel3 *m, uint32_t val)
657 {
658     uint32_t size;
659 
660     size = m->size;
661     for (int i = 0; i < size; i++) {
662         if (val == m->symbols[i]) {
663             int a;
664 
665             if (m->size <= 32)
666                 a = 32;
667             else
668                 a = 64;
669             return update_model2_to_6(m, val, a);
670         }
671     }
672 
673     if (size >= 64)
674         return update_model2_to_3(m, val);
675 
676     m->symbols[size] = val;
677     m->size++;
678 
679     return 0;
680 }
681 
update_model3_to_7(PixelModel3 * m,uint8_t value)682 static int update_model3_to_7(PixelModel3 *m, uint8_t value)
683 {
684     PixelModel3 n = {0};
685     int c, d, e, f, g, q;
686 
687     n.type = 7;
688 
689     for (c = 0; c < 256; c++) {
690         d = c;
691         n.freqs[d] = 1;
692         n.cnts[d] = 1;
693     }
694 
695     for (c = m->size, d = (4096 - (256 - c)) / (c + 1) | 0, e = d - (d >> 1), g = 0; g < c;) {
696         q = g++;
697         q = m->symbols[q];
698         n.freqs[q] = d;
699         n.cnts[q] = e;
700     }
701     n.freqs[value] += d;
702     n.cnts[value] += 16;
703     for (d = c = n.cntsum = 0; 256 > d; d++) {
704         e = d;
705         n.cntsum += n.cnts[e];
706         n.freqs1[e] = c;
707         g = n.freqs[e];
708         f = (c + g - 1 >> 7) + 1;
709         if (f > FF_ARRAY_ELEMS(n.dectab))
710             return AVERROR_INVALIDDATA;
711         for (q = c + 128 - 1 >> 7; q < f; q++) {
712             n.dectab[q] = e;
713         }
714         c += g;
715     }
716 
717     memcpy(m, &n, sizeof(n));
718 
719     return 0;
720 }
721 
decode_static3(PixelModel3 * m,uint32_t val)722 static int decode_static3(PixelModel3 *m, uint32_t val)
723 {
724     uint32_t size = m->size;
725 
726     for (int i = 0; i < size; i++) {
727         if (val == m->symbols[i])
728             return update_model3_to_7(m, val);
729     }
730 
731     if (size >= 256)
732         return 0;
733 
734     m->symbols[size] = val;
735     m->size++;
736     return 0;
737 }
738 
sync_code3(GetByteContext * gb,RangeCoder * rc)739 static void sync_code3(GetByteContext *gb, RangeCoder *rc)
740 {
741     rc->code1++;
742     if (rc->code1 == 0x20000) {
743         rc->code = bytestream2_get_le32(gb);
744         rc->code1 = 0;
745     }
746 }
747 
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)748 static int decode_value3(SCPRContext *s, uint32_t max, uint32_t *cntsum,
749                          uint16_t *freqs1, uint16_t *freqs2,
750                          uint16_t *cnts, uint8_t *dectable,
751                          uint32_t *value)
752 {
753     GetByteContext *gb = &s->gb;
754     RangeCoder *rc = &s->rc;
755     uint32_t r, y, a, b, e, g, q;
756 
757     r = dectable[(rc->code & 0xFFFu) >> 7];
758     if (r < max) {
759         while (freqs2[r + 1] <= (rc->code & 0xFFF)) {
760             if (++r >= max)
761                 break;
762         }
763     }
764 
765     if (r > max)
766         return AVERROR_INVALIDDATA;
767 
768     cnts[r] += 16;
769     a = freqs1[r];
770     b = freqs2[r];
771     *cntsum += 16;
772     if (*cntsum + 16 > 4096) {
773         *cntsum = 0;
774         for (int c = 0, i = 0; i < max + 1; i++) {
775             e = cnts[i];
776             freqs2[i] = c;
777             freqs1[i] = e;
778             g = (c + 127) >> 7;
779             c += e;
780             q = ((c - 1) >> 7) + 1;
781             if (q > g) {
782                 for (int j = 0; j < q - g; j++)
783                     dectable[j + g] = i;
784             }
785             y = e - (e >> 1);
786             cnts[i] = y;
787             *cntsum += y;
788         }
789     }
790 
791     decode3(gb, rc, a, b);
792     sync_code3(gb, rc);
793 
794     *value = r;
795 
796     return 0;
797 }
798 
calc_sum5(PixelModel3 * m)799 static void calc_sum5(PixelModel3 *m)
800 {
801     uint32_t a;
802 
803     a = 256 - m->size;
804     for (int b = 0; b < m->size; b++)
805         a += m->freqs[b];
806     m->cntsum = a;
807 }
808 
update_model4_to_5(PixelModel3 * m,uint32_t value)809 static int update_model4_to_5(PixelModel3 *m, uint32_t value)
810 {
811     PixelModel3 n = {0};
812     int c, e, g, totfr;
813 
814     n.type = 5;
815 
816     for (c = 0, e = 0; c < m->size && m->symbols[c] < value; c++) {
817         n.symbols[c] = m->symbols[c];
818         e += n.freqs[c] = m->freqs[c];
819     }
820 
821     g = c;
822     n.symbols[g] = value;
823     e += n.freqs[g++] = 50;
824     for (; c < m->size; g++, c++) {
825         n.symbols[g] = m->symbols[c];
826         e += n.freqs[g] = m->freqs[c];
827     }
828     n.size = m->size + 1;
829     if (e > 4096)
830         rescale(&n, &totfr);
831 
832     calc_sum5(&n);
833 
834     memcpy(m, &n, sizeof(n));
835 
836     return 0;
837 }
838 
decode_unit3(SCPRContext * s,PixelModel3 * m,uint32_t code,uint32_t * value)839 static int decode_unit3(SCPRContext *s, PixelModel3 *m, uint32_t code, uint32_t *value)
840 {
841     GetByteContext *gb = &s->gb;
842     RangeCoder *rc = &s->rc;
843     uint16_t a = 0, b = 0;
844     uint32_t param;
845     int type;
846     int ret;
847 
848     type = m->type;
849     switch (type) {
850     case 0:
851         *value = bytestream2_get_byte(&s->gb);
852         m->type = 1;
853         m->size = 1;
854         m->symbols[0] = *value;
855         sync_code3(gb, rc);
856         break;
857     case 1:
858         *value = bytestream2_get_byte(&s->gb);
859         decode_static1(m, *value);
860         sync_code3(gb, rc);
861         break;
862     case 2:
863         *value = bytestream2_get_byte(&s->gb);
864         decode_static2(m, *value);
865         sync_code3(gb, rc);
866         break;
867     case 3:
868         *value = bytestream2_get_byte(&s->gb);
869         ret = decode_static3(m, *value);
870         if (ret < 0)
871             return AVERROR_INVALIDDATA;
872         sync_code3(gb, rc);
873         break;
874     case 4:
875         param = m->freqs[0] + m->freqs[1] + m->freqs[2] + m->freqs[3] + 256 - m->size;
876         if (!decode_adaptive45(m, code, value, &a, &b, &param, 4))
877             update_model4_to_5(m, *value);
878         decode3(gb, rc, a, b);
879         sync_code3(gb, rc);
880         break;
881     case 5:
882         if (!decode_adaptive45(m, code, value, &a, &b, &m->cntsum, 16))
883             update_model5_to_6(m, *value);
884         decode3(gb, rc, a, b);
885         sync_code3(gb, rc);
886         break;
887     case 6:
888         if (!decode_adaptive6(m, code, value, &a, &b)) {
889             ret = update_model6_to_7(m);
890             if (ret < 0)
891                 return AVERROR_INVALIDDATA;
892         }
893         decode3(gb, rc, a, b);
894         sync_code3(gb, rc);
895         break;
896     case 7:
897         return decode_value3(s, 255, &m->cntsum,
898                              m->freqs, m->freqs1,
899                              m->cnts, m->dectab, value);
900     }
901 
902     if (*value > 255)
903         return AVERROR_INVALIDDATA;
904 
905     return 0;
906 }
907 
decode_units3(SCPRContext * s,uint32_t * red,uint32_t * green,uint32_t * blue,int * cx,int * cx1)908 static int decode_units3(SCPRContext * s, uint32_t *red,
909                          uint32_t *green, uint32_t *blue,
910                          int *cx, int *cx1)
911 {
912     RangeCoder *rc = &s->rc;
913     int ret;
914 
915     ret = decode_unit3(s, &s->pixel_model3[0][*cx + *cx1], rc->code & 0xFFF, red);
916     if (ret < 0)
917         return ret;
918 
919     *cx1 = (*cx << 6) & 0xFC0;
920     *cx = *red >> 2;
921 
922     ret = decode_unit3(s, &s->pixel_model3[1][*cx + *cx1], rc->code & 0xFFF, green);
923     if (ret < 0)
924         return ret;
925 
926     *cx1 = (*cx << 6) & 0xFC0;
927     *cx = *green >> 2;
928 
929     ret = decode_unit3(s, &s->pixel_model3[2][*cx + *cx1], rc->code & 0xFFF, blue);
930     if (ret < 0)
931         return ret;
932 
933     *cx1 = (*cx << 6) & 0xFC0;
934     *cx = *blue >> 2;
935 
936     return 0;
937 }
938 
init_rangecoder3(RangeCoder * rc,GetByteContext * gb)939 static void init_rangecoder3(RangeCoder *rc, GetByteContext *gb)
940 {
941     rc->code  = bytestream2_get_le32(gb);
942     rc->code1 = 0;
943 }
944 
decompress_i3(AVCodecContext * avctx,uint32_t * dst,int linesize)945 static int decompress_i3(AVCodecContext *avctx, uint32_t *dst, int linesize)
946 {
947     SCPRContext *s = avctx->priv_data;
948     GetByteContext *gb = &s->gb;
949     RangeCoder *rc = &s->rc;
950     int cx = 0, cx1 = 0, k = 0;
951     int run, off, y = 0, x = 0, ret;
952     uint32_t backstep = linesize - avctx->width;
953     uint32_t clr = 0, lx, ly, ptype, r, g, b;
954 
955     bytestream2_skip(gb, 1);
956     init_rangecoder3(rc, gb);
957     reinit_tables3(s);
958 
959     while (k < avctx->width + 1) {
960         ret = decode_units3(s, &r, &g, &b, &cx, &cx1);
961         if (ret < 0)
962             return ret;
963         ret = decode_value3(s, 255, &s->run_model3[0].cntsum,
964                             s->run_model3[0].freqs[0],
965                             s->run_model3[0].freqs[1],
966                             s->run_model3[0].cnts,
967                             s->run_model3[0].dectab, &run);
968         if (ret < 0)
969             return ret;
970         if (run <= 0)
971             return AVERROR_INVALIDDATA;
972 
973         clr = (b << 16) + (g << 8) + r;
974         k += run;
975         while (run-- > 0) {
976             if (y >= avctx->height)
977                 return AVERROR_INVALIDDATA;
978 
979             dst[y * linesize + x] = clr;
980             lx = x;
981             ly = y;
982             x++;
983             if (x >= avctx->width) {
984                 x = 0;
985                 y++;
986             }
987         }
988     }
989     off = -linesize - 1;
990     ptype = 0;
991 
992     while (x < avctx->width && y < avctx->height) {
993         ret = decode_value3(s, 5, &s->op_model3[ptype].cntsum,
994                             s->op_model3[ptype].freqs[0],
995                             s->op_model3[ptype].freqs[1],
996                             s->op_model3[ptype].cnts,
997                             s->op_model3[ptype].dectab, &ptype);
998         if (ret < 0)
999             return ret;
1000         if (ptype == 0) {
1001             ret = decode_units3(s, &r, &g, &b, &cx, &cx1);
1002             if (ret < 0)
1003                 return ret;
1004             clr = (b << 16) + (g << 8) + r;
1005         }
1006         if (ptype > 5)
1007             return AVERROR_INVALIDDATA;
1008         ret = decode_value3(s, 255, &s->run_model3[ptype].cntsum,
1009                             s->run_model3[ptype].freqs[0],
1010                             s->run_model3[ptype].freqs[1],
1011                             s->run_model3[ptype].cnts,
1012                             s->run_model3[ptype].dectab, &run);
1013         if (ret < 0)
1014             return ret;
1015         if (run <= 0)
1016             return AVERROR_INVALIDDATA;
1017 
1018         ret = decode_run_i(avctx, ptype, run, &x, &y, clr,
1019                            dst, linesize, &lx, &ly,
1020                            backstep, off, &cx, &cx1);
1021         if (ret < 0)
1022             return ret;
1023     }
1024 
1025     return 0;
1026 }
1027 
decompress_p3(AVCodecContext * avctx,uint32_t * dst,int linesize,uint32_t * prev,int plinesize)1028 static int decompress_p3(AVCodecContext *avctx,
1029                          uint32_t *dst, int linesize,
1030                          uint32_t *prev, int plinesize)
1031 {
1032     SCPRContext *s = avctx->priv_data;
1033     GetByteContext *gb = &s->gb;
1034     int ret, temp, min, max, x, y, cx = 0, cx1 = 0;
1035     int backstep = linesize - avctx->width;
1036     int mvx = 0, mvy = 0;
1037 
1038     if (bytestream2_get_byte(gb) == 0)
1039         return 1;
1040     init_rangecoder3(&s->rc, gb);
1041 
1042     ret  = decode_value3(s, 255, &s->range_model3.cntsum,
1043                          s->range_model3.freqs[0],
1044                          s->range_model3.freqs[1],
1045                          s->range_model3.cnts,
1046                          s->range_model3.dectab, &min);
1047     ret |= decode_value3(s, 255, &s->range_model3.cntsum,
1048                          s->range_model3.freqs[0],
1049                          s->range_model3.freqs[1],
1050                          s->range_model3.cnts,
1051                          s->range_model3.dectab, &temp);
1052     if (ret < 0)
1053         return ret;
1054 
1055     min += temp << 8;
1056     ret |= decode_value3(s, 255, &s->range_model3.cntsum,
1057                          s->range_model3.freqs[0],
1058                          s->range_model3.freqs[1],
1059                          s->range_model3.cnts,
1060                          s->range_model3.dectab, &max);
1061     ret |= decode_value3(s, 255, &s->range_model3.cntsum,
1062                          s->range_model3.freqs[0],
1063                          s->range_model3.freqs[1],
1064                          s->range_model3.cnts,
1065                          s->range_model3.dectab, &temp);
1066     if (ret < 0)
1067         return ret;
1068 
1069     max += temp << 8;
1070     if (min > max || min >= s->nbcount)
1071         return AVERROR_INVALIDDATA;
1072 
1073     memset(s->blocks, 0, sizeof(*s->blocks) * s->nbcount);
1074 
1075     while (min <= max) {
1076         int fill, count;
1077 
1078         ret  = decode_value3(s, 4, &s->fill_model3.cntsum,
1079                              s->fill_model3.freqs[0],
1080                              s->fill_model3.freqs[1],
1081                              s->fill_model3.cnts,
1082                              s->fill_model3.dectab, &fill);
1083         ret |= decode_value3(s, 255, &s->count_model3.cntsum,
1084                              s->count_model3.freqs[0],
1085                              s->count_model3.freqs[1],
1086                              s->count_model3.cnts,
1087                              s->count_model3.dectab, &count);
1088         if (ret < 0)
1089             return ret;
1090         if (count <= 0)
1091             return AVERROR_INVALIDDATA;
1092 
1093         while (min < s->nbcount && count-- > 0) {
1094             s->blocks[min++] = fill;
1095         }
1096     }
1097 
1098     ret = av_frame_copy(s->current_frame, s->last_frame);
1099     if (ret < 0)
1100         return ret;
1101 
1102     for (y = 0; y < s->nby; y++) {
1103         for (x = 0; x < s->nbx; x++) {
1104             int sy1 = 0, sy2 = 16, sx1 = 0, sx2 = 16;
1105 
1106             if (s->blocks[y * s->nbx + x] == 0)
1107                 continue;
1108 
1109             if (((s->blocks[y * s->nbx + x] + 1) & 1) > 0) {
1110                 ret  = decode_value3(s, 15, &s->sxy_model3[0].cntsum,
1111                                      s->sxy_model3[0].freqs[0],
1112                                      s->sxy_model3[0].freqs[1],
1113                                      s->sxy_model3[0].cnts,
1114                                      s->sxy_model3[0].dectab, &sx1);
1115                 ret |= decode_value3(s, 15, &s->sxy_model3[1].cntsum,
1116                                      s->sxy_model3[1].freqs[0],
1117                                      s->sxy_model3[1].freqs[1],
1118                                      s->sxy_model3[1].cnts,
1119                                      s->sxy_model3[1].dectab, &sy1);
1120                 ret |= decode_value3(s, 15, &s->sxy_model3[2].cntsum,
1121                                      s->sxy_model3[2].freqs[0],
1122                                      s->sxy_model3[2].freqs[1],
1123                                      s->sxy_model3[2].cnts,
1124                                      s->sxy_model3[2].dectab, &sx2);
1125                 ret |= decode_value3(s, 15, &s->sxy_model3[3].cntsum,
1126                                      s->sxy_model3[3].freqs[0],
1127                                      s->sxy_model3[3].freqs[1],
1128                                      s->sxy_model3[3].cnts,
1129                                      s->sxy_model3[3].dectab, &sy2);
1130                 if (ret < 0)
1131                     return ret;
1132 
1133                 sx2++;
1134                 sy2++;
1135             }
1136             if (((s->blocks[y * s->nbx + x] + 3) & 2) > 0) {
1137                 int i, a, b, c, j, by = y * 16, bx = x * 16;
1138                 uint32_t code;
1139 
1140                 a = s->rc.code & 0xFFF;
1141                 c = 1;
1142 
1143                 if (a < 0x800)
1144                     c = 0;
1145                 b = 2048;
1146                 if (!c)
1147                     b = 0;
1148 
1149                 code = a + ((s->rc.code >> 1) & 0xFFFFF800) - b;
1150                 while (code < 0x800000 && bytestream2_get_bytes_left(gb) > 0)
1151                     code = bytestream2_get_byteu(gb) | (code << 8);
1152                 s->rc.code = code;
1153 
1154                 sync_code3(gb, &s->rc);
1155 
1156                 if (!c) {
1157                     ret  = decode_value3(s, 511, &s->mv_model3[0].cntsum,
1158                                          s->mv_model3[0].freqs[0],
1159                                          s->mv_model3[0].freqs[1],
1160                                          s->mv_model3[0].cnts,
1161                                          s->mv_model3[0].dectab, &mvx);
1162                     ret |= decode_value3(s, 511, &s->mv_model3[1].cntsum,
1163                                          s->mv_model3[1].freqs[0],
1164                                          s->mv_model3[1].freqs[1],
1165                                          s->mv_model3[1].cnts,
1166                                          s->mv_model3[1].dectab, &mvy);
1167                     if (ret < 0)
1168                         return ret;
1169 
1170                     mvx -= 256;
1171                     mvy -= 256;
1172                 }
1173 
1174                 if (by + mvy + sy1 < 0 || bx + mvx + sx1 < 0 ||
1175                     by + mvy + sy1 >= avctx->height || bx + mvx + sx1 >= avctx->width)
1176                     return AVERROR_INVALIDDATA;
1177 
1178                 for (i = 0; i < sy2 - sy1 && (by + sy1 + i) < avctx->height && (by + mvy + sy1 + i) < avctx->height; i++) {
1179                     for (j = 0; j < sx2 - sx1 && (bx + sx1 + j) < avctx->width && (bx + mvx + sx1 + j) < avctx->width; j++) {
1180                         dst[(by + i + sy1) * linesize + bx + sx1 + j] = prev[(by + mvy + sy1 + i) * plinesize + bx + sx1 + mvx + j];
1181                     }
1182                 }
1183             } else {
1184                 int run, bx = x * 16 + sx1, by = y * 16 + sy1;
1185                 uint32_t clr, ptype = 0, r, g, b;
1186 
1187                 for (; by < y * 16 + sy2 && by < avctx->height;) {
1188                     ret = decode_value3(s, 5, &s->op_model3[ptype].cntsum,
1189                                         s->op_model3[ptype].freqs[0],
1190                                         s->op_model3[ptype].freqs[1],
1191                                         s->op_model3[ptype].cnts,
1192                                         s->op_model3[ptype].dectab, &ptype);
1193                     if (ret < 0)
1194                         return ret;
1195                     if (ptype == 0) {
1196                         ret = decode_units3(s, &r, &g, &b, &cx, &cx1);
1197                         if (ret < 0)
1198                             return ret;
1199 
1200                         clr = (b << 16) + (g << 8) + r;
1201                     }
1202                     if (ptype > 5)
1203                         return AVERROR_INVALIDDATA;
1204                     ret = decode_value3(s, 255, &s->run_model3[ptype].cntsum,
1205                                         s->run_model3[ptype].freqs[0],
1206                                         s->run_model3[ptype].freqs[1],
1207                                         s->run_model3[ptype].cnts,
1208                                         s->run_model3[ptype].dectab, &run);
1209                     if (ret < 0)
1210                         return ret;
1211                     if (run <= 0)
1212                         return AVERROR_INVALIDDATA;
1213 
1214                     ret = decode_run_p(avctx, ptype, run, x, y, clr,
1215                                        dst, prev, linesize, plinesize, &bx, &by,
1216                                        backstep, sx1, sx2, &cx, &cx1);
1217                     if (ret < 0)
1218                         return ret;
1219                 }
1220             }
1221         }
1222     }
1223 
1224     return 0;
1225 }
1226