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/intreadwrite.h"
38 
39 #include "avcodec.h"
40 #include "rangecoder.h"
41 
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 
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 }
124 
126 {
127  if (version == 1) {
128  RangeCoder tmp = *c;
129  get_rac(c, (uint8_t[]) { 129 });
130 
131  if (c->bytestream == tmp.bytestream && c->bytestream > c->bytestream_start)
132  tmp.low -= *--tmp.bytestream;
133  tmp.bytestream_end = tmp.bytestream;
134 
135  if (get_rac(&tmp, (uint8_t[]) { 129 }))
136  return AVERROR_INVALIDDATA;
137  } else {
138  if (c->bytestream_end != c->bytestream)
139  return AVERROR_INVALIDDATA;
140  }
141  return 0;
142 }
#define AVERROR_INVALIDDATA
Invalid data found when processing input.
Definition: error.h:59
uint32_t low
Definition: mss3.c:64
uint8_t zero_state[256]
Definition: rangecoder.h:40
Range coder.
uint8_t * bytestream_end
Definition: rangecoder.h:44
int version
Definition: avisynth_c.h:858
uint32_t range
Definition: mss3.c:64
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:87
uint8_t one_state[256]
Definition: rangecoder.h:41
Macro definitions for various function/variable attributes.
uint8_t
#define av_cold
Definition: attributes.h:82
static int get_rac(RangeCoder *c, uint8_t *const state)
Definition: rangecoder.h:136
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
int ff_rac_check_termination(RangeCoder *c, int version)
Check if at the current position there is a valid looking termination.
Definition: rangecoder.c:125
#define i(width, name, range_min, range_max)
Definition: cbs_h2645.c:259
static void renorm_encoder(RangeCoder *c)
Definition: rangecoder.h:71
simple assert() macros that are a bit more flexible than ISO C assert().
uint8_t * bytestream
Definition: rangecoder.h:43
#define av_assert1(cond)
assert() equivalent, that does not lie in speed critical code.
Definition: avassert.h:53
void ff_build_rac_states(RangeCoder *c, int factor, int max_p)
Definition: rangecoder.c:68
int outstanding_byte
Definition: rangecoder.h:39
Libavcodec external API header.
void * buf
Definition: avisynth_c.h:766
av_cold void ff_init_range_encoder(RangeCoder *c, uint8_t *buf, int buf_size)
Definition: rangecoder.c:42
av_cold void ff_init_range_decoder(RangeCoder *c, const uint8_t *buf, int buf_size)
Definition: rangecoder.c:53
static const int factor[16]
Definition: vf_pp7.c:75
int ff_rac_terminate(RangeCoder *c, int version)
Terminates the range coder.
Definition: rangecoder.c:109
int overread
Definition: rangecoder.h:45
int outstanding_count
Definition: rangecoder.h:38
#define put_rac(C, S, B)
uint8_t * bytestream_start
Definition: rangecoder.h:42
static uint8_t tmp[11]
Definition: aes_ctr.c:26