3 * Copyright (c) 2004 Michael Niedermayer <michaelni@gmx.at>
5 * This file is part of FFmpeg.
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.
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.
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
26 * "Range encoding: an algorithm for removing redundancy from a digitised
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."
36 #include "libavutil/attributes.h"
37 #include "libavutil/avassert.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
)
46 c
->bytestream_end
= buf
+ buf_size
;
49 c
->outstanding_count
= 0;
50 c
->outstanding_byte
= -1;
53 av_cold
void ff_init_range_decoder(RangeCoder
*c
, const uint8_t *buf
,
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
);
62 void ff_build_rac_states(RangeCoder
*c
, int factor
, int max_p
)
64 const int64_t one
= 1LL << 32;
68 memset(c
->zero_state
, 0, sizeof(c
->zero_state
));
69 memset(c
->one_state
, 0, sizeof(c
->one_state
));
73 for (i
= 0; i
< 128; i
++) {
74 p8
= (256 * p
+ one
/ 2) >> 32; // FIXME: try without the one
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;
84 for (i
= 256 - max_p
; i
<= max_p
; i
++) {
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
98 for (i
= 1; i
< 255; i
++)
99 c
->zero_state
[i
] = 256 - c
->one_state
[256 - i
];
102 /* Return the number of bytes written. */
103 int ff_rac_terminate(RangeCoder
*c
)
111 av_assert1(c
->low
== 0);
112 av_assert1(c
->range
>= 0x100);
114 return c
->bytestream
- c
->bytestream_start
;
120 #include "libavutil/lfg.h"
121 #include "libavutil/log.h"
123 static uint8_t b
[9 * SIZE
];
124 static uint8_t r
[9 * SIZE
];
133 av_lfg_init(&prng
, 1);
135 ff_init_range_encoder(&c
, b
, SIZE
);
136 ff_build_rac_states(&c
, 0.05 * (1LL << 32), 128 + 64 + 32 + 16);
138 memset(state
, 128, sizeof(state
));
140 for (i
= 0; i
< SIZE
; i
++)
141 r
[i
] = av_lfg_get(&prng
) % 7;
143 for (i
= 0; i
< SIZE
; i
++)
144 put_rac(&c
, state
, r
[i
] & 1);
146 ff_rac_terminate(&c
);
148 ff_init_range_decoder(&c
, b
, SIZE
);
150 memset(state
, 128, sizeof(state
));
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
);