FFmpeg
rangecoder.c
Go to the documentation of this file.
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  * 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 
33 #include <string.h>
34 
35 #include "libavutil/attributes.h"
36 #include "libavutil/avassert.h"
37 #include "libavutil/bswap.h"
38 #include "libavutil/intreadwrite.h"
39 
40 #include "rangecoder.h"
41 
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 }
52 
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);
58 
59  c->low = AV_RB16(c->bytestream);
60  c->bytestream += 2;
61  c->overread = 0;
62  if (c->low >= 0xFF00) {
63  c->low = 0xFF00;
64  c->bytestream_end = c->bytestream;
65  }
66 }
67 
68 void ff_build_rac_states(RangeCoder *c, int factor, int max_p)
69 {
70  const int64_t one = 1LL << 32;
71  int64_t p;
72  int last_p8, p8, i;
73 
74  memset(c->zero_state, 0, sizeof(c->zero_state));
75  memset(c->one_state, 0, sizeof(c->one_state));
76 
77  last_p8 = 0;
78  p = one / 2;
79  for (i = 0; i < 128; i++) {
80  p8 = (256 * p + one / 2) >> 32; // FIXME: try without the one
81  if (p8 <= last_p8)
82  p8 = last_p8 + 1;
83  if (last_p8 && last_p8 < 256 && p8 <= max_p)
84  c->one_state[last_p8] = p8;
85 
86  p += ((one - p) * factor + one / 2) >> 32;
87  last_p8 = p8;
88  }
89 
90  for (i = 256 - max_p; i <= max_p; i++) {
91  if (c->one_state[i])
92  continue;
93 
94  p = (i * one + 128) >> 8;
95  p += ((one - p) * factor + one / 2) >> 32;
96  p8 = (256 * p + one / 2) >> 32; // FIXME: try without the one
97  if (p8 <= i)
98  p8 = i + 1;
99  if (p8 > max_p)
100  p8 = max_p;
101  c->one_state[i] = p8;
102  }
103 
104  for (i = 1; i < 255; i++)
105  c->zero_state[i] = 256 - c->one_state[256 - i];
106 }
107 
108 /* Return the number of bytes written. */
110 {
111  if (version == 1)
112  put_rac(c, (uint8_t[]) { 129 }, 0);
113  c->range = 0xFF;
114  c->low += 0xFF;
115  renorm_encoder(c);
116  c->range = 0xFF;
117  renorm_encoder(c);
118 
119  av_assert1(c->low == 0);
120  av_assert1(c->range >= 0x100);
121 
122  return c->bytestream - c->bytestream_start;
123 }
int64_t
long long int64_t
Definition: coverity.c:34
rangecoder.h
ff_init_range_encoder
av_cold void ff_init_range_encoder(RangeCoder *c, uint8_t *buf, int buf_size)
Definition: rangecoder.c:42
avassert.h
av_cold
#define av_cold
Definition: attributes.h:90
intreadwrite.h
ff_rac_terminate
int ff_rac_terminate(RangeCoder *c, int version)
Terminates the range coder.
Definition: rangecoder.c:109
c
Undefined Behavior In the C some operations are like signed integer dereferencing freed accessing outside allocated Undefined Behavior must not occur in a C it is not safe even if the output of undefined operations is unused The unsafety may seem nit picking but Optimizing compilers have in fact optimized code on the assumption that no undefined Behavior occurs Optimizing code based on wrong assumptions can and has in some cases lead to effects beyond the output of computations The signed integer overflow problem in speed critical code Code which is highly optimized and works with signed integers sometimes has the problem that often the output of the computation does not c
Definition: undefined.txt:32
ff_init_range_decoder
av_cold void ff_init_range_decoder(RangeCoder *c, const uint8_t *buf, int buf_size)
Definition: rangecoder.c:53
ff_build_rac_states
void ff_build_rac_states(RangeCoder *c, int factor, int max_p)
Definition: rangecoder.c:68
attributes.h
version
version
Definition: libkvazaar.c:321
i
#define i(width, name, range_min, range_max)
Definition: cbs_h2645.c:255
renorm_encoder
static void renorm_encoder(RangeCoder *c)
Definition: rangecoder.h:62
av_assert1
#define av_assert1(cond)
assert() equivalent, that does not lie in speed critical code.
Definition: avassert.h:56
bswap.h
put_rac
#define put_rac(C, S, B)
factor
static const int factor[16]
Definition: vf_pp7.c:78
RangeCoder
Definition: mss3.c:62
AV_RB16
uint64_t_TMPL AV_WL64 unsigned int_TMPL AV_WL32 unsigned int_TMPL AV_WL24 unsigned int_TMPL AV_WL16 uint64_t_TMPL AV_WB64 unsigned int_TMPL AV_WB32 unsigned int_TMPL AV_WB24 unsigned int_TMPL AV_RB16
Definition: bytestream.h:98