Line | Branch | Exec | Source |
---|---|---|---|
1 | /* | ||
2 | * Range coder | ||
3 | * Copyright (c) 2004 Michael Niedermayer <michaelni@gmx.at> | ||
4 | * | ||
5 | * This file is part of FFmpeg. | ||
6 | * | ||
7 | * FFmpeg is free software; you can redistribute it and/or | ||
8 | * modify it under the terms of the GNU Lesser General Public | ||
9 | * License as published by the Free Software Foundation; either | ||
10 | * version 2.1 of the License, or (at your option) any later version. | ||
11 | * | ||
12 | * FFmpeg is distributed in the hope that it will be useful, | ||
13 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | ||
14 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | ||
15 | * Lesser General Public License for more details. | ||
16 | * | ||
17 | * You should have received a copy of the GNU Lesser General Public | ||
18 | * License along with FFmpeg; if not, write to the Free Software | ||
19 | * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA | ||
20 | */ | ||
21 | |||
22 | /** | ||
23 | * @file | ||
24 | * Range coder. | ||
25 | */ | ||
26 | |||
27 | #ifndef AVCODEC_RANGECODER_H | ||
28 | #define AVCODEC_RANGECODER_H | ||
29 | |||
30 | #include <stdint.h> | ||
31 | |||
32 | #include "libavutil/avassert.h" | ||
33 | #include "libavutil/intmath.h" | ||
34 | |||
35 | typedef struct RangeCoder { | ||
36 | int low; | ||
37 | int range; | ||
38 | int outstanding_count; | ||
39 | int outstanding_byte; | ||
40 | uint8_t zero_state[256]; | ||
41 | uint8_t one_state[256]; | ||
42 | uint8_t *bytestream_start; | ||
43 | uint8_t *bytestream; | ||
44 | uint8_t *bytestream_end; | ||
45 | int overread; | ||
46 | #define MAX_OVERREAD 2 | ||
47 | } RangeCoder; | ||
48 | |||
49 | void ff_init_range_encoder(RangeCoder *c, uint8_t *buf, int buf_size); | ||
50 | void ff_init_range_decoder(RangeCoder *c, const uint8_t *buf, int buf_size); | ||
51 | |||
52 | /** | ||
53 | * Terminates the range coder | ||
54 | * @param version version 0 requires the decoder to know the data size in bytes | ||
55 | * version 1 needs about 1 bit more space but does not need to | ||
56 | * carry the size from encoder to decoder | ||
57 | */ | ||
58 | int ff_rac_terminate(RangeCoder *c, int version); | ||
59 | |||
60 | void ff_build_rac_states(RangeCoder *c, int factor, int max_p); | ||
61 | |||
62 | 1633083721 | static inline void renorm_encoder(RangeCoder *c) | |
63 | { | ||
64 | // FIXME: optimize | ||
65 |
2/2✓ Branch 0 taken 104832986 times.
✓ Branch 1 taken 1633083721 times.
|
1737916707 | while (c->range < 0x100) { |
66 |
2/2✓ Branch 0 taken 10175 times.
✓ Branch 1 taken 104822811 times.
|
104832986 | if (c->outstanding_byte < 0) { |
67 | 10175 | c->outstanding_byte = c->low >> 8; | |
68 |
2/2✓ Branch 0 taken 68946511 times.
✓ Branch 1 taken 35876300 times.
|
104822811 | } else if (c->low <= 0xFF00) { |
69 | 68946511 | *c->bytestream++ = c->outstanding_byte; | |
70 |
2/2✓ Branch 0 taken 621599 times.
✓ Branch 1 taken 68946511 times.
|
69568110 | for (; c->outstanding_count; c->outstanding_count--) |
71 | 621599 | *c->bytestream++ = 0xFF; | |
72 | 68946511 | c->outstanding_byte = c->low >> 8; | |
73 |
2/2✓ Branch 0 taken 35118248 times.
✓ Branch 1 taken 758052 times.
|
35876300 | } else if (c->low >= 0x10000) { |
74 | 35118248 | *c->bytestream++ = c->outstanding_byte + 1; | |
75 |
2/2✓ Branch 0 taken 136359 times.
✓ Branch 1 taken 35118248 times.
|
35254607 | for (; c->outstanding_count; c->outstanding_count--) |
76 | 136359 | *c->bytestream++ = 0x00; | |
77 | 35118248 | c->outstanding_byte = (c->low >> 8) & 0xFF; | |
78 | } else { | ||
79 | 758052 | c->outstanding_count++; | |
80 | } | ||
81 | |||
82 | 104832986 | c->low = (c->low & 0xFF) << 8; | |
83 | 104832986 | c->range <<= 8; | |
84 | } | ||
85 | 1633083721 | } | |
86 | |||
87 | 1673460 | static inline int get_rac_count(RangeCoder *c) | |
88 | { | ||
89 | 1673460 | int x = c->bytestream - c->bytestream_start + c->outstanding_count; | |
90 |
2/2✓ Branch 0 taken 1672998 times.
✓ Branch 1 taken 462 times.
|
1673460 | if (c->outstanding_byte >= 0) |
91 | 1672998 | x++; | |
92 | 1673460 | return 8 * x - av_log2(c->range); | |
93 | } | ||
94 | |||
95 | 1633064997 | static inline void put_rac(RangeCoder *c, uint8_t *const state, int bit) | |
96 | { | ||
97 | 1633064997 | int range1 = (c->range * (*state)) >> 8; | |
98 | |||
99 | av_assert2(*state); | ||
100 | av_assert2(range1 < c->range); | ||
101 | av_assert2(range1 > 0); | ||
102 |
2/2✓ Branch 0 taken 715464304 times.
✓ Branch 1 taken 917600693 times.
|
1633064997 | if (!bit) { |
103 | 715464304 | c->range -= range1; | |
104 | 715464304 | *state = c->zero_state[*state]; | |
105 | } else { | ||
106 | 917600693 | c->low += c->range - range1; | |
107 | 917600693 | c->range = range1; | |
108 | 917600693 | *state = c->one_state[*state]; | |
109 | } | ||
110 | |||
111 | 1633064997 | renorm_encoder(c); | |
112 | 1633064997 | } | |
113 | |||
114 | 1510855873 | static inline void refill(RangeCoder *c) | |
115 | { | ||
116 |
2/2✓ Branch 0 taken 94019384 times.
✓ Branch 1 taken 1416836489 times.
|
1510855873 | if (c->range < 0x100) { |
117 | 94019384 | c->range <<= 8; | |
118 | 94019384 | c->low <<= 8; | |
119 |
2/2✓ Branch 0 taken 94017709 times.
✓ Branch 1 taken 1675 times.
|
94019384 | if (c->bytestream < c->bytestream_end) { |
120 | 94017709 | c->low += c->bytestream[0]; | |
121 | 94017709 | c->bytestream++; | |
122 | } else | ||
123 | 1675 | c->overread ++; | |
124 | } | ||
125 | 1510855873 | } | |
126 | |||
127 | 1510855873 | static inline int get_rac(RangeCoder *c, uint8_t *const state) | |
128 | { | ||
129 | 1510855873 | int range1 = (c->range * (*state)) >> 8; | |
130 | |||
131 | 1510855873 | c->range -= range1; | |
132 |
2/2✓ Branch 0 taken 653422449 times.
✓ Branch 1 taken 857433424 times.
|
1510855873 | if (c->low < c->range) { |
133 | 653422449 | *state = c->zero_state[*state]; | |
134 | 653422449 | refill(c); | |
135 | 653422449 | return 0; | |
136 | } else { | ||
137 | 857433424 | c->low -= c->range; | |
138 | 857433424 | *state = c->one_state[*state]; | |
139 | 857433424 | c->range = range1; | |
140 | 857433424 | refill(c); | |
141 | 857433424 | return 1; | |
142 | } | ||
143 | } | ||
144 | |||
145 | #endif /* AVCODEC_RANGECODER_H */ | ||
146 |