FFmpeg: libavcodec/rangecoder.c Source File

FFmpeg

[フレーム]

libavcodec

rangecoder.c

Go to the documentation of this file.

1 /*

2 * Range coder

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 */

22 /**

23 * @file

24 * Range coder.

25 * based upon

26 * "Range encoding: an algorithm for removing redundancy from a digitised

27 * message.

28 * G. N. N. Martin Presented in March 1979 to the Video &

29 * Data Recording Conference,

30 * IBM UK Scientific Center held in Southampton July 24-27 1979."

31 *

32 */

34 #include <string.h>

36 #include "libavutil/attributes.h"

37 #include "libavutil/avassert.h"

38 #include "avcodec.h"

39 #include "rangecoder.h"

40 #include "bytestream.h"

42 av_cold void ff_init_range_encoder(RangeCoder *c, uint8_t *buf, int buf_size)

43 {

44 c->bytestream_start =

45 c->bytestream = buf;

46 c->bytestream_end = buf + buf_size;

47 c->low = 0;

48 c->range = 0xFF00;

49 c->outstanding_count = 0;

50 c->outstanding_byte = -1;

51 }

53 av_cold void ff_init_range_decoder(RangeCoder *c, const uint8_t *buf,

54 int buf_size)

55 {

56 /* cast to avoid compiler warning */

57 ff_init_range_encoder(c, (uint8_t *)buf, buf_size);

59 c->low = bytestream_get_be16((const uint8_t **)&c->bytestream);

60 }

62 void ff_build_rac_states(RangeCoder *c, int factor, int max_p)

63 {

64 const int64_t one = 1LL << 32;

65 int64_t p;

66 int last_p8, p8, i;

68 memset(c->zero_state, 0, sizeof(c->zero_state));

69 memset(c->one_state, 0, sizeof(c->one_state));

71 last_p8 = 0;

72 p = one / 2;

73 for (i = 0; i < 128; i++) {

74 p8 = (256 * p + one / 2) >> 32; // FIXME: try without the one

75 if (p8 <= last_p8)

76 p8 = last_p8 + 1;

77 if (last_p8 && last_p8 < 256 && p8 <= max_p)

78 c->one_state[last_p8] = p8;

80 p += ((one - p) * factor + one / 2) >> 32;

81 last_p8 = p8;

82 }

84 for (i = 256 - max_p; i <= max_p; i++) {

85 if (c->one_state[i])

86 continue;

88 p = (i * one + 128) >> 8;

89 p += ((one - p) * factor + one / 2) >> 32;

90 p8 = (256 * p + one / 2) >> 32; // FIXME: try without the one

91 if (p8 <= i)

92 p8 = i + 1;

93 if (p8 > max_p)

94 p8 = max_p;

95 c->one_state[i] = p8;

96 }

98 for (i = 1; i < 255; i++)

99 c->zero_state[i] = 256 - c->one_state[256 - i];

100 }

101

102 /* Return the number of bytes written. */

103 int ff_rac_terminate(RangeCoder *c)

104 {

105 c->range = 0xFF;

106 c->low += 0xFF;

107 renorm_encoder(c);

108 c->range = 0xFF;

109 renorm_encoder(c);

110

111 av_assert1(c->low == 0);

112 av_assert1(c->range >= 0x100);

113

114 return c->bytestream - c->bytestream_start;

115 }

116

117 #ifdef TEST

118 #define SIZE 10240

119

120 #include "libavutil/lfg.h"

121 #include "libavutil/log.h"

122

123 static uint8_t b[9 * SIZE];

124 static uint8_t r[9 * SIZE];

125

126 int main(void)

127 {

128 RangeCoder c;

129 int i;

130 uint8_t state[10];

131 AVLFG prng;

132

133 av_lfg_init(&prng, 1);

134

135 ff_init_range_encoder(&c, b, SIZE);

136 ff_build_rac_states(&c, 0.05 * (1LL << 32), 128 + 64 + 32 + 16);

137

138 memset(state, 128, sizeof(state));

139

140 for (i = 0; i < SIZE; i++)

141 r[i] = av_lfg_get(&prng) % 7;

142

143 for (i = 0; i < SIZE; i++)

144 put_rac(&c, state, r[i] & 1);

145

146 ff_rac_terminate(&c);

147

148 ff_init_range_decoder(&c, b, SIZE);

149

150 memset(state, 128, sizeof(state));

151

152 for (i = 0; i < SIZE; i++)

153 if ((r[i] & 1) != get_rac(&c, state)) {

154 av_log(NULL, AV_LOG_ERROR, "rac failure at %d\n", i);

155 return 1;

156 }

157

158 return 0;

159 }

160 #endif /* TEST */

Generated on Sun Sep 14 2014 18:56:02 for FFmpeg by doxygen 1.8.2