| 1 |
// Copyright (c) 2001-2016, Alliance for Open Media. All rights reserved |
| 2 |
// Copyright (c) 2017-2022, The rav1e contributors. All rights reserved |
| 3 |
// |
| 4 |
// This source code is subject to the terms of the BSD 2 Clause License and |
| 5 |
// the Alliance for Open Media Patent License 1.0. If the BSD 2 Clause License |
| 6 |
// was not distributed with this source code in the LICENSE file, you can |
| 7 |
// obtain it at www.aomedia.org/license/software. If the Alliance for Open |
| 8 |
// Media Patent License 1.0 was not distributed with this source code in the |
| 9 |
// PATENTS file, you can obtain it at www.aomedia.org/license/patent. |
| 10 |
|
| 11 |
#![allow(non_camel_case_types)] |
| 12 |
|
| 13 |
cfg_if::cfg_if! { |
| 14 |
if #[cfg(nasm_x86_64)] { |
| 15 |
pub use crate::asm::x86::ec::*; |
| 16 |
} else { |
| 17 |
pub use self::rust::*; |
| 18 |
} |
| 19 |
} |
| 20 |
|
| 21 |
use crate::context::{CDFContext, CDFContextLog, CDFOffset}; |
| 22 |
use bitstream_io::{BigEndian, BitWrite, BitWriter}; |
| 23 |
use std::io; |
| 24 |
|
| 25 |
pub const OD_BITRES: u8 = 3; |
| 26 |
const EC_PROB_SHIFT: u32 = 6; |
| 27 |
const EC_MIN_PROB: u32 = 4; |
| 28 |
type ec_window = u32; |
| 29 |
|
| 30 |
/// Public trait interface to a bitstream `Writer`: a `Counter` can be |
| 31 |
/// used to count bits for cost analysis without actually storing |
| 32 |
/// anything (using a new `WriterCounter` as a `Writer`), to record |
| 33 |
/// tokens for later writing (using a new `WriterRecorder` as a |
| 34 |
/// `Writer`) to write actual final bits out using a range encoder |
| 35 |
/// (using a new `WriterEncoder` as a `Writer`). A `WriterRecorder`'s |
| 36 |
/// contents can be replayed into a `WriterEncoder`. |
| 37 |
pub trait Writer { |
| 38 |
/// Write a symbol `s`, using the passed in cdf reference; leaves `cdf` unchanged |
| 39 |
fn symbol<const CDF_LEN: usize>(&mut self, s: u32, cdf: &[u16; CDF_LEN]); |
| 40 |
/// return approximate number of fractional bits in `OD_BITRES` |
| 41 |
/// precision to write a symbol `s` using the passed in cdf reference; |
| 42 |
/// leaves `cdf` unchanged |
| 43 |
fn symbol_bits(&self, s: u32, cdf: &[u16]) -> u32; |
| 44 |
/// Write a symbol `s`, using the passed in cdf reference; updates the referenced cdf. |
| 45 |
fn symbol_with_update<const CDF_LEN: usize>( |
| 46 |
&mut self, s: u32, cdf: CDFOffset<CDF_LEN>, log: &mut CDFContextLog, |
| 47 |
fc: &mut CDFContext, |
| 48 |
); |
| 49 |
/// Write a bool using passed in probability |
| 50 |
fn bool(&mut self, val: bool, f: u16); |
| 51 |
/// Write a single bit with flat probability |
| 52 |
fn bit(&mut self, bit: u16); |
| 53 |
/// Write literal `bits` with flat probability |
| 54 |
fn literal(&mut self, bits: u8, s: u32); |
| 55 |
/// Write passed `level` as a golomb code |
| 56 |
fn write_golomb(&mut self, level: u32); |
| 57 |
/// Write a value `v` in `[0, n-1]` quasi-uniformly |
| 58 |
fn write_quniform(&mut self, n: u32, v: u32); |
| 59 |
/// Return fractional bits needed to write a value `v` in `[0, n-1]` |
| 60 |
/// quasi-uniformly |
| 61 |
fn count_quniform(&self, n: u32, v: u32) -> u32; |
| 62 |
/// Write symbol `v` in `[0, n-1]` with parameter `k` as finite subexponential |
| 63 |
fn write_subexp(&mut self, n: u32, k: u8, v: u32); |
| 64 |
/// Return fractional bits needed to write symbol v in `[0, n-1]` with |
| 65 |
/// parameter k as finite subexponential |
| 66 |
fn count_subexp(&self, n: u32, k: u8, v: u32) -> u32; |
| 67 |
/// Write symbol `v` in `[0, n-1]` with parameter `k` as finite |
| 68 |
/// subexponential based on a reference `r` also in `[0, n-1]`. |
| 69 |
fn write_unsigned_subexp_with_ref(&mut self, v: u32, mx: u32, k: u8, r: u32); |
| 70 |
/// Return fractional bits needed to write symbol `v` in `[0, n-1]` with |
| 71 |
/// parameter `k` as finite subexponential based on a reference `r` |
| 72 |
/// also in `[0, n-1]`. |
| 73 |
fn count_unsigned_subexp_with_ref( |
| 74 |
&self, v: u32, mx: u32, k: u8, r: u32, |
| 75 |
) -> u32; |
| 76 |
/// Write symbol v in `[-(n-1), n-1]` with parameter k as finite |
| 77 |
/// subexponential based on a reference ref also in `[-(n-1), n-1]`. |
| 78 |
fn write_signed_subexp_with_ref( |
| 79 |
&mut self, v: i32, low: i32, high: i32, k: u8, r: i32, |
| 80 |
); |
| 81 |
/// Return fractional bits needed to write symbol `v` in `[-(n-1), n-1]` |
| 82 |
/// with parameter `k` as finite subexponential based on a reference |
| 83 |
/// `r` also in `[-(n-1), n-1]`. |
| 84 |
fn count_signed_subexp_with_ref( |
| 85 |
&self, v: i32, low: i32, high: i32, k: u8, r: i32, |
| 86 |
) -> u32; |
| 87 |
/// Return current length of range-coded bitstream in integer bits |
| 88 |
fn tell(&mut self) -> u32; |
| 89 |
/// Return current length of range-coded bitstream in fractional |
| 90 |
/// bits with `OD_BITRES` decimal precision |
| 91 |
fn tell_frac(&mut self) -> u32; |
| 92 |
/// Save current point in coding/recording to a checkpoint |
| 93 |
fn checkpoint(&mut self) -> WriterCheckpoint; |
| 94 |
/// Restore saved position in coding/recording from a checkpoint |
| 95 |
fn rollback(&mut self, _: &WriterCheckpoint); |
| 96 |
/// Add additional bits from rate estimators without coding a real symbol |
| 97 |
fn add_bits_frac(&mut self, bits_frac: u32); |
| 98 |
} |
| 99 |
|
| 100 |
/// `StorageBackend` is an internal trait used to tie a specific `Writer` |
| 101 |
/// implementation's storage to the generic `Writer`. It would be |
| 102 |
/// private, but Rust is deprecating 'private trait in a public |
| 103 |
/// interface' support. |
| 104 |
pub trait StorageBackend { |
| 105 |
/// Store partially-computed range code into given storage backend |
| 106 |
fn store(&mut self, fl: u16, fh: u16, nms: u16); |
| 107 |
/// Return bit-length of encoded stream to date |
| 108 |
fn stream_bits(&mut self) -> usize; |
| 109 |
/// Backend implementation of checkpoint to pass through Writer interface |
| 110 |
fn checkpoint(&mut self) -> WriterCheckpoint; |
| 111 |
/// Backend implementation of rollback to pass through Writer interface |
| 112 |
fn rollback(&mut self, _: &WriterCheckpoint); |
| 113 |
} |
| 114 |
|
| 115 |
#[derive(Debug, Clone)] |
| 116 |
pub struct WriterBase<S> { |
| 117 |
/// The number of values in the current range. |
| 118 |
rng: u16, |
| 119 |
/// The number of bits of data in the current value. |
| 120 |
cnt: i16, |
| 121 |
#[cfg(feature = "desync_finder")] |
| 122 |
/// Debug enable flag |
| 123 |
debug: bool, |
| 124 |
/// Extra offset added to `tell()` and `tell_frac()` to approximate costs |
| 125 |
/// of actually coding a symbol |
| 126 |
fake_bits_frac: u32, |
| 127 |
/// Use-specific storage |
| 128 |
s: S, |
| 129 |
} |
| 130 |
|
| 131 |
#[derive(Debug, Clone)] |
| 132 |
pub struct WriterCounter { |
| 133 |
/// Bits that would be shifted out to date |
| 134 |
bits: usize, |
| 135 |
} |
| 136 |
|
| 137 |
#[derive(Debug, Clone)] |
| 138 |
pub struct WriterRecorder { |
| 139 |
/// Storage for tokens |
| 140 |
storage: Vec<(u16, u16, u16)>, |
| 141 |
/// Bits that would be shifted out to date |
| 142 |
bits: usize, |
| 143 |
} |
| 144 |
|
| 145 |
#[derive(Debug, Clone)] |
| 146 |
pub struct WriterEncoder { |
| 147 |
/// A buffer for output bytes with their associated carry flags. |
| 148 |
precarry: Vec<u16>, |
| 149 |
/// The low end of the current range. |
| 150 |
low: ec_window, |
| 151 |
} |
| 152 |
|
| 153 |
#[derive(Clone)] |
| 154 |
pub struct WriterCheckpoint { |
| 155 |
/// Stream length coded/recorded to date, in the unit used by the Writer, |
| 156 |
/// which may be bytes or bits. This depends on the assumption |
| 157 |
/// that a Writer will only ever restore its own Checkpoint. |
| 158 |
stream_size: usize, |
| 159 |
/// To be defined by backend |
| 160 |
backend_var: usize, |
| 161 |
/// Saved number of values in the current range. |
| 162 |
rng: u16, |
| 163 |
/// Saved number of bits of data in the current value. |
| 164 |
cnt: i16, |
| 165 |
} |
| 166 |
|
| 167 |
/// Constructor for a counting Writer |
| 168 |
impl WriterCounter { |
| 169 |
#[inline] |
| 170 |
pub const fn new() -> WriterBase<WriterCounter> { |
| 171 |
WriterBase::new(WriterCounter { bits: 0 }) |
| 172 |
} |
| 173 |
} |
| 174 |
|
| 175 |
/// Constructor for a recording Writer |
| 176 |
impl WriterRecorder { |
| 177 |
#[inline] |
| 178 |
pub const fn new() -> WriterBase<WriterRecorder> { |
| 179 |
WriterBase::new(WriterRecorder { storage: Vec::new(), bits: 0 }) |
| 180 |
} |
| 181 |
} |
| 182 |
|
| 183 |
/// Constructor for a encoding Writer |
| 184 |
impl WriterEncoder { |
| 185 |
#[inline] |
| 186 |
pub const fn new() -> WriterBase<WriterEncoder> { |
| 187 |
WriterBase::new(WriterEncoder { precarry: Vec::new(), low: 0 }) |
| 188 |
} |
| 189 |
} |
| 190 |
|
| 191 |
/// The Counter stores nothing we write to it, it merely counts the |
| 192 |
/// bit usage like in an Encoder for cost analysis. |
| 193 |
impl StorageBackend for WriterBase<WriterCounter> { |
| 194 |
#[inline] |
| 195 |
fn store(&mut self, fl: u16, fh: u16, nms: u16) { |
| 196 |
let (_l, r) = self.lr_compute(fl, fh, nms); |
| 197 |
let d = r.leading_zeros() as usize; |
| 198 |
|
| 199 |
self.s.bits += d; |
| 200 |
self.rng = r << d; |
| 201 |
} |
| 202 |
#[inline] |
| 203 |
fn stream_bits(&mut self) -> usize { |
| 204 |
self.s.bits |
| 205 |
} |
| 206 |
#[inline] |
| 207 |
fn checkpoint(&mut self) -> WriterCheckpoint { |
| 208 |
WriterCheckpoint { |
| 209 |
stream_size: self.s.bits, |
| 210 |
backend_var: 0, |
| 211 |
rng: self.rng, |
| 212 |
// We do not use `cnt` within Counter, but setting it here allows the compiler |
| 213 |
// to do a 32-bit merged load/store. |
| 214 |
cnt: self.cnt, |
| 215 |
} |
| 216 |
} |
| 217 |
#[inline] |
| 218 |
fn rollback(&mut self, checkpoint: &WriterCheckpoint) { |
| 219 |
self.rng = checkpoint.rng; |
| 220 |
self.s.bits = checkpoint.stream_size; |
| 221 |
} |
| 222 |
} |
| 223 |
|
| 224 |
/// The Recorder does not produce a range-coded bitstream, but it |
| 225 |
/// still tracks the range coding progress like in an Encoder, as it |
| 226 |
/// neds to be able to report bit costs for RDO decisions. It stores a |
| 227 |
/// pair of mostly-computed range coding values per token recorded. |
| 228 |
impl StorageBackend for WriterBase<WriterRecorder> { |
| 229 |
#[inline] |
| 230 |
fn store(&mut self, fl: u16, fh: u16, nms: u16) { |
| 231 |
let (_l, r) = self.lr_compute(fl, fh, nms); |
| 232 |
let d = r.leading_zeros() as usize; |
| 233 |
|
| 234 |
self.s.bits += d; |
| 235 |
self.rng = r << d; |
| 236 |
self.s.storage.push((fl, fh, nms)); |
| 237 |
} |
| 238 |
#[inline] |
| 239 |
fn stream_bits(&mut self) -> usize { |
| 240 |
self.s.bits |
| 241 |
} |
| 242 |
#[inline] |
| 243 |
fn checkpoint(&mut self) -> WriterCheckpoint { |
| 244 |
WriterCheckpoint { |
| 245 |
stream_size: self.s.bits, |
| 246 |
backend_var: self.s.storage.len(), |
| 247 |
rng: self.rng, |
| 248 |
cnt: self.cnt, |
| 249 |
} |
| 250 |
} |
| 251 |
#[inline] |
| 252 |
fn rollback(&mut self, checkpoint: &WriterCheckpoint) { |
| 253 |
self.rng = checkpoint.rng; |
| 254 |
self.cnt = checkpoint.cnt; |
| 255 |
self.s.bits = checkpoint.stream_size; |
| 256 |
self.s.storage.truncate(checkpoint.backend_var); |
| 257 |
} |
| 258 |
} |
| 259 |
|
| 260 |
/// An Encoder produces an actual range-coded bitstream from passed in |
| 261 |
/// tokens. It does not retain any information about the coded |
| 262 |
/// tokens, only the resulting bitstream, and so it cannot be replayed |
| 263 |
/// (only checkpointed and rolled back). |
| 264 |
impl StorageBackend for WriterBase<WriterEncoder> { |
| 265 |
fn store(&mut self, fl: u16, fh: u16, nms: u16) { |
| 266 |
let (l, r) = self.lr_compute(fl, fh, nms); |
| 267 |
let mut low = l + self.s.low; |
| 268 |
let mut c = self.cnt; |
| 269 |
let d = r.leading_zeros() as usize; |
| 270 |
let mut s = c + (d as i16); |
| 271 |
|
| 272 |
if s >= 0 { |
| 273 |
c += 16; |
| 274 |
let mut m = (1 << c) - 1; |
| 275 |
if s >= 8 { |
| 276 |
self.s.precarry.push((low >> c) as u16); |
| 277 |
low &= m; |
| 278 |
c -= 8; |
| 279 |
m >>= 8; |
| 280 |
} |
| 281 |
self.s.precarry.push((low >> c) as u16); |
| 282 |
s = c + (d as i16) - 24; |
| 283 |
low &= m; |
| 284 |
} |
| 285 |
self.s.low = low << d; |
| 286 |
self.rng = r << d; |
| 287 |
self.cnt = s; |
| 288 |
} |
| 289 |
#[inline] |
| 290 |
fn stream_bits(&mut self) -> usize { |
| 291 |
self.s.precarry.len() * 8 |
| 292 |
} |
| 293 |
#[inline] |
| 294 |
fn checkpoint(&mut self) -> WriterCheckpoint { |
| 295 |
WriterCheckpoint { |
| 296 |
stream_size: self.s.precarry.len(), |
| 297 |
backend_var: self.s.low as usize, |
| 298 |
rng: self.rng, |
| 299 |
cnt: self.cnt, |
| 300 |
} |
| 301 |
} |
| 302 |
fn rollback(&mut self, checkpoint: &WriterCheckpoint) { |
| 303 |
self.rng = checkpoint.rng; |
| 304 |
self.cnt = checkpoint.cnt; |
| 305 |
self.s.low = checkpoint.backend_var as ec_window; |
| 306 |
self.s.precarry.truncate(checkpoint.stream_size); |
| 307 |
} |
| 308 |
} |
| 309 |
|
| 310 |
/// A few local helper functions needed by the Writer that are not |
| 311 |
/// part of the public interface. |
| 312 |
impl<S> WriterBase<S> { |
| 313 |
/// Internal constructor called by the subtypes that implement the |
| 314 |
/// actual encoder and Recorder. |
| 315 |
#[inline] |
| 316 |
#[cfg(not(feature = "desync_finder"))] |
| 317 |
const fn new(storage: S) -> Self { |
| 318 |
WriterBase { rng: 0x8000, cnt: -9, fake_bits_frac: 0, s: storage } |
| 319 |
} |
| 320 |
|
| 321 |
#[inline] |
| 322 |
#[cfg(feature = "desync_finder")] |
| 323 |
fn new(storage: S) -> Self { |
| 324 |
WriterBase { |
| 325 |
rng: 0x8000, |
| 326 |
cnt: -9, |
| 327 |
debug: std::env::var_os("RAV1E_DEBUG").is_some(), |
| 328 |
fake_bits_frac: 0, |
| 329 |
s: storage, |
| 330 |
} |
| 331 |
} |
| 332 |
|
| 333 |
/// Compute low and range values from token cdf values and local state |
| 334 |
const fn lr_compute(&self, fl: u16, fh: u16, nms: u16) -> (ec_window, u16) { |
| 335 |
let r = self.rng as u32; |
| 336 |
debug_assert!(32768 <= r); |
| 337 |
let mut u = (((r >> 8) * (fl as u32 >> EC_PROB_SHIFT)) |
| 338 |
>> (7 - EC_PROB_SHIFT)) |
| 339 |
+ EC_MIN_PROB * nms as u32; |
| 340 |
if fl >= 32768 { |
| 341 |
u = r; |
| 342 |
} |
| 343 |
let v = (((r >> 8) * (fh as u32 >> EC_PROB_SHIFT)) >> (7 - EC_PROB_SHIFT)) |
| 344 |
+ EC_MIN_PROB * (nms - 1) as u32; |
| 345 |
(r - u, (u - v) as u16) |
| 346 |
} |
| 347 |
|
| 348 |
/// Given the current total integer number of bits used and the current value of |
| 349 |
/// rng, computes the fraction number of bits used to `OD_BITRES` precision. |
| 350 |
/// This is used by `od_ec_enc_tell_frac()` and `od_ec_dec_tell_frac()`. |
| 351 |
/// `nbits_total`: The number of whole bits currently used, i.e., the value |
| 352 |
/// returned by `od_ec_enc_tell()` or `od_ec_dec_tell()`. |
| 353 |
/// `rng`: The current value of rng from either the encoder or decoder state. |
| 354 |
/// Return: The number of bits scaled by `2**OD_BITRES`. |
| 355 |
/// This will always be slightly larger than the exact value (e.g., all |
| 356 |
/// rounding error is in the positive direction). |
| 357 |
fn frac_compute(nbits_total: u32, mut rng: u32) -> u32 { |
| 358 |
// To handle the non-integral number of bits still left in the encoder/decoder |
| 359 |
// state, we compute the worst-case number of bits of val that must be |
| 360 |
// encoded to ensure that the value is inside the range for any possible |
| 361 |
// subsequent bits. |
| 362 |
// The computation here is independent of val itself (the decoder does not |
| 363 |
// even track that value), even though the real number of bits used after |
| 364 |
// od_ec_enc_done() may be 1 smaller if rng is a power of two and the |
| 365 |
// corresponding trailing bits of val are all zeros. |
| 366 |
// If we did try to track that special case, then coding a value with a |
| 367 |
// probability of 1/(1 << n) might sometimes appear to use more than n bits. |
| 368 |
// This may help explain the surprising result that a newly initialized |
| 369 |
// encoder or decoder claims to have used 1 bit. |
| 370 |
let nbits = nbits_total << OD_BITRES; |
| 371 |
let mut l = 0; |
| 372 |
for _ in 0..OD_BITRES { |
| 373 |
rng = (rng * rng) >> 15; |
| 374 |
let b = rng >> 16; |
| 375 |
l = (l << 1) | b; |
| 376 |
rng >>= b; |
| 377 |
} |
| 378 |
nbits - l |
| 379 |
} |
| 380 |
|
| 381 |
const fn recenter(r: u32, v: u32) -> u32 { |
| 382 |
if v > (r << 1) { |
| 383 |
v |
| 384 |
} else if v >= r { |
| 385 |
(v - r) << 1 |
| 386 |
} else { |
| 387 |
((r - v) << 1) - 1 |
| 388 |
} |
| 389 |
} |
| 390 |
|
| 391 |
#[cfg(feature = "desync_finder")] |
| 392 |
fn print_backtrace(&self, s: u32) { |
| 393 |
let mut depth = 3; |
| 394 |
backtrace::trace(|frame| { |
| 395 |
let ip = frame.ip(); |
| 396 |
|
| 397 |
depth -= 1; |
| 398 |
|
| 399 |
if depth == 0 { |
| 400 |
backtrace::resolve(ip, |symbol| { |
| 401 |
if let Some(name) = symbol.name() { |
| 402 |
println!("Writing symbol {} from {}", s, name); |
| 403 |
} |
| 404 |
}); |
| 405 |
false |
| 406 |
} else { |
| 407 |
true |
| 408 |
} |
| 409 |
}); |
| 410 |
} |
| 411 |
} |
| 412 |
|
| 413 |
/// Replay implementation specific to the Recorder |
| 414 |
impl WriterBase<WriterRecorder> { |
| 415 |
/// Replays the partially-computed range tokens out of the Recorder's |
| 416 |
/// storage and into the passed in Writer, which may be an Encoder |
| 417 |
/// or another Recorder. Clears the Recorder after replay. |
| 418 |
pub fn replay(&mut self, dest: &mut dyn StorageBackend) { |
| 419 |
for &(fl, fh, nms) in &self.s.storage { |
| 420 |
dest.store(fl, fh, nms); |
| 421 |
} |
| 422 |
self.rng = 0x8000; |
| 423 |
self.cnt = -9; |
| 424 |
self.s.storage.truncate(0); |
| 425 |
self.s.bits = 0; |
| 426 |
} |
| 427 |
} |
| 428 |
|
| 429 |
/// Done implementation specific to the Encoder |
| 430 |
impl WriterBase<WriterEncoder> { |
| 431 |
/// Indicates that there are no more symbols to encode. Flushes |
| 432 |
/// remaining state into coding and returns a vector containing the |
| 433 |
/// final bitstream. |
| 434 |
pub fn done(&mut self) -> Vec<u8> { |
| 435 |
// We output the minimum number of bits that ensures that the symbols encoded |
| 436 |
// thus far will be decoded correctly regardless of the bits that follow. |
| 437 |
let l = self.s.low; |
| 438 |
let mut c = self.cnt; |
| 439 |
let mut s = 10; |
| 440 |
let m = 0x3FFF; |
| 441 |
let mut e = ((l + m) & !m) | (m + 1); |
| 442 |
|
| 443 |
s += c; |
| 444 |
|
| 445 |
if s > 0 { |
| 446 |
let mut n = (1 << (c + 16)) - 1; |
| 447 |
|
| 448 |
loop { |
| 449 |
self.s.precarry.push((e >> (c + 16)) as u16); |
| 450 |
e &= n; |
| 451 |
s -= 8; |
| 452 |
c -= 8; |
| 453 |
n >>= 8; |
| 454 |
|
| 455 |
if s <= 0 { |
| 456 |
break; |
| 457 |
} |
| 458 |
} |
| 459 |
} |
| 460 |
|
| 461 |
let mut c = 0; |
| 462 |
let mut offs = self.s.precarry.len(); |
| 463 |
// dynamic allocation: grows during encode |
| 464 |
let mut out = vec![0_u8; offs]; |
| 465 |
while offs > 0 { |
| 466 |
offs -= 1; |
| 467 |
c += self.s.precarry[offs]; |
| 468 |
out[offs] = c as u8; |
| 469 |
c >>= 8; |
| 470 |
} |
| 471 |
|
| 472 |
out |
| 473 |
} |
| 474 |
} |
| 475 |
|
| 476 |
/// Generic/shared implementation for `Writer`s with `StorageBackend`s |
| 477 |
/// (ie, `Encoder`s and `Recorder`s) |
| 478 |
impl<S> Writer for WriterBase<S> |
| 479 |
where |
| 480 |
WriterBase<S>: StorageBackend, |
| 481 |
{ |
| 482 |
/// Encode a single binary value. |
| 483 |
/// `val`: The value to encode (0 or 1). |
| 484 |
/// `f`: The probability that the val is one, scaled by 32768. |
| 485 |
fn bool(&mut self, val: bool, f: u16) { |
| 486 |
debug_assert!(0 < f); |
| 487 |
debug_assert!(f < 32768); |
| 488 |
self.symbol(u32::from(val), &[f, 0]); |
| 489 |
} |
| 490 |
/// Encode a single boolean value. |
| 491 |
/// |
| 492 |
/// - `val`: The value to encode (`false` or `true`). |
| 493 |
/// - `f`: The probability that the `val` is `true`, scaled by `32768`. |
| 494 |
fn bit(&mut self, bit: u16) { |
| 495 |
self.bool(bit == 1, 16384); |
| 496 |
} |
| 497 |
// fake add bits |
| 498 |
fn add_bits_frac(&mut self, bits_frac: u32) { |
| 499 |
self.fake_bits_frac += bits_frac |
| 500 |
} |
| 501 |
/// Encode a literal bitstring, bit by bit in MSB order, with flat |
| 502 |
/// probability. |
| 503 |
/// |
| 504 |
/// - 'bits': Length of bitstring |
| 505 |
/// - 's': Bit string to encode |
| 506 |
fn literal(&mut self, bits: u8, s: u32) { |
| 507 |
for bit in (0..bits).rev() { |
| 508 |
self.bit((1 & (s >> bit)) as u16); |
| 509 |
} |
| 510 |
} |
| 511 |
/// Encodes a symbol given a cumulative distribution function (CDF) table in Q15. |
| 512 |
/// |
| 513 |
/// - `s`: The index of the symbol to encode. |
| 514 |
/// - `cdf`: The CDF, such that symbol s falls in the range |
| 515 |
/// `[s > 0 ? cdf[s - 1] : 0, cdf[s])`. |
| 516 |
/// The values must be monotonically non-decreasing, and the last value |
| 517 |
/// must be greater than 32704. There should be at most 16 values. |
| 518 |
/// The lower 6 bits of the last value hold the count. |
| 519 |
#[inline(always)] |
| 520 |
fn symbol<const CDF_LEN: usize>(&mut self, s: u32, cdf: &[u16; CDF_LEN]) { |
| 521 |
debug_assert!(cdf[cdf.len() - 1] < (1 << EC_PROB_SHIFT)); |
| 522 |
let s = s as usize; |
| 523 |
debug_assert!(s < cdf.len()); |
| 524 |
// The above is stricter than the following overflow check: s <= cdf.len() |
| 525 |
let nms = cdf.len() - s; |
| 526 |
let fl = if s > 0 { |
| 527 |
// SAFETY: We asserted that s is less than the length of the cdf |
| 528 |
unsafe { *cdf.get_unchecked(s - 1) } |
| 529 |
} else { |
| 530 |
32768 |
| 531 |
}; |
| 532 |
// SAFETY: We asserted that s is less than the length of the cdf |
| 533 |
let fh = unsafe { *cdf.get_unchecked(s) }; |
| 534 |
debug_assert!((fh >> EC_PROB_SHIFT) <= (fl >> EC_PROB_SHIFT)); |
| 535 |
debug_assert!(fl <= 32768); |
| 536 |
self.store(fl, fh, nms as u16); |
| 537 |
} |
| 538 |
/// Encodes a symbol given a cumulative distribution function (CDF) |
| 539 |
/// table in Q15, then updates the CDF probabilities to reflect we've |
| 540 |
/// written one more symbol 's'. |
| 541 |
/// |
| 542 |
/// - `s`: The index of the symbol to encode. |
| 543 |
/// - `cdf`: The CDF, such that symbol s falls in the range |
| 544 |
/// `[s > 0 ? cdf[s - 1] : 0, cdf[s])`. |
| 545 |
/// The values must be monotonically non-decreasing, and the last value |
| 546 |
/// must be greater 32704. There should be at most 16 values. |
| 547 |
/// The lower 6 bits of the last value hold the count. |
| 548 |
fn symbol_with_update<const CDF_LEN: usize>( |
| 549 |
&mut self, s: u32, cdf: CDFOffset<CDF_LEN>, log: &mut CDFContextLog, |
| 550 |
fc: &mut CDFContext, |
| 551 |
) { |
| 552 |
#[cfg(feature = "desync_finder")] |
| 553 |
{ |
| 554 |
if self.debug { |
| 555 |
self.print_backtrace(s); |
| 556 |
} |
| 557 |
} |
| 558 |
let cdf = log.push(fc, cdf); |
| 559 |
self.symbol(s, cdf); |
| 560 |
|
| 561 |
update_cdf(cdf, s); |
| 562 |
} |
| 563 |
/// Returns approximate cost for a symbol given a cumulative |
| 564 |
/// distribution function (CDF) table and current write state. |
| 565 |
/// |
| 566 |
/// - `s`: The index of the symbol to encode. |
| 567 |
/// - `cdf`: The CDF, such that symbol s falls in the range |
| 568 |
/// `[s > 0 ? cdf[s - 1] : 0, cdf[s])`. |
| 569 |
/// The values must be monotonically non-decreasing, and the last value |
| 570 |
/// must be greater than 32704. There should be at most 16 values. |
| 571 |
/// The lower 6 bits of the last value hold the count. |
| 572 |
fn symbol_bits(&self, s: u32, cdf: &[u16]) -> u32 { |
| 573 |
let mut bits = 0; |
| 574 |
debug_assert!(cdf[cdf.len() - 1] < (1 << EC_PROB_SHIFT)); |
| 575 |
debug_assert!(32768 <= self.rng); |
| 576 |
let rng = (self.rng >> 8) as u32; |
| 577 |
let fh = cdf[s as usize] as u32 >> EC_PROB_SHIFT; |
| 578 |
let r: u32 = if s > 0 { |
| 579 |
let fl = cdf[s as usize - 1] as u32 >> EC_PROB_SHIFT; |
| 580 |
((rng * fl) >> (7 - EC_PROB_SHIFT)) - ((rng * fh) >> (7 - EC_PROB_SHIFT)) |
| 581 |
+ EC_MIN_PROB |
| 582 |
} else { |
| 583 |
let nms1 = cdf.len() as u32 - s - 1; |
| 584 |
self.rng as u32 |
| 585 |
- ((rng * fh) >> (7 - EC_PROB_SHIFT)) |
| 586 |
- nms1 * EC_MIN_PROB |
| 587 |
}; |
| 588 |
|
| 589 |
// The 9 here counteracts the offset of -9 baked into cnt. Don't include a termination bit. |
| 590 |
let pre = Self::frac_compute((self.cnt + 9) as u32, self.rng as u32); |
| 591 |
let d = r.leading_zeros() - 16; |
| 592 |
let mut c = self.cnt; |
| 593 |
let mut sh = c + (d as i16); |
| 594 |
if sh >= 0 { |
| 595 |
c += 16; |
| 596 |
if sh >= 8 { |
| 597 |
bits += 8; |
| 598 |
c -= 8; |
| 599 |
} |
| 600 |
bits += 8; |
| 601 |
sh = c + (d as i16) - 24; |
| 602 |
} |
| 603 |
// The 9 here counteracts the offset of -9 baked into cnt. Don't include a termination bit. |
| 604 |
Self::frac_compute((bits + sh + 9) as u32, r << d) - pre |
| 605 |
} |
| 606 |
/// Encode a golomb to the bitstream. |
| 607 |
/// |
| 608 |
/// - 'level': passed in value to encode |
| 609 |
fn write_golomb(&mut self, level: u32) { |
| 610 |
let x = level + 1; |
| 611 |
let length = 32 - x.leading_zeros(); |
| 612 |
|
| 613 |
for _ in 0..length - 1 { |
| 614 |
self.bit(0); |
| 615 |
} |
| 616 |
|
| 617 |
for i in (0..length).rev() { |
| 618 |
self.bit(((x >> i) & 0x01) as u16); |
| 619 |
} |
| 620 |
} |
| 621 |
/// Write a value `v` in `[0, n-1]` quasi-uniformly |
| 622 |
/// - `n`: size of interval |
| 623 |
/// - `v`: value to encode |
| 624 |
fn write_quniform(&mut self, n: u32, v: u32) { |
| 625 |
if n > 1 { |
| 626 |
let l = 32 - n.leading_zeros() as u8; |
| 627 |
let m = (1 << l) - n; |
| 628 |
if v < m { |
| 629 |
self.literal(l - 1, v); |
| 630 |
} else { |
| 631 |
self.literal(l - 1, m + ((v - m) >> 1)); |
| 632 |
self.literal(1, (v - m) & 1); |
| 633 |
} |
| 634 |
} |
| 635 |
} |
| 636 |
/// Returns `QOD_BITRES` bits for a value `v` in `[0, n-1]` quasi-uniformly |
| 637 |
/// - `n`: size of interval |
| 638 |
/// - `v`: value to encode |
| 639 |
fn count_quniform(&self, n: u32, v: u32) -> u32 { |
| 640 |
let mut bits = 0; |
| 641 |
if n > 1 { |
| 642 |
let l = 32 - n.leading_zeros(); |
| 643 |
let m = (1 << l) - n; |
| 644 |
bits += (l - 1) << OD_BITRES; |
| 645 |
if v >= m { |
| 646 |
bits += 1 << OD_BITRES; |
| 647 |
} |
| 648 |
} |
| 649 |
bits |
| 650 |
} |
| 651 |
/// Write symbol `v` in `[0, n-1]` with parameter `k` as finite subexponential |
| 652 |
/// |
| 653 |
/// - `n`: size of interval |
| 654 |
/// - `k`: "parameter" |
| 655 |
/// - `v`: value to encode |
| 656 |
fn write_subexp(&mut self, n: u32, k: u8, v: u32) { |
| 657 |
let mut i = 0; |
| 658 |
let mut mk = 0; |
| 659 |
loop { |
| 660 |
let b = if i != 0 { k + i - 1 } else { k }; |
| 661 |
let a = 1 << b; |
| 662 |
if n <= mk + 3 * a { |
| 663 |
self.write_quniform(n - mk, v - mk); |
| 664 |
break; |
| 665 |
} else { |
| 666 |
let t = v >= mk + a; |
| 667 |
self.bool(t, 16384); |
| 668 |
if t { |
| 669 |
i += 1; |
| 670 |
mk += a; |
| 671 |
} else { |
| 672 |
self.literal(b, v - mk); |
| 673 |
break; |
| 674 |
} |
| 675 |
} |
| 676 |
} |
| 677 |
} |
| 678 |
/// Returns `QOD_BITRES` bits for symbol `v` in `[0, n-1]` with parameter `k` |
| 679 |
/// as finite subexponential |
| 680 |
/// |
| 681 |
/// - `n`: size of interval |
| 682 |
/// - `k`: "parameter" |
| 683 |
/// - `v`: value to encode |
| 684 |
fn count_subexp(&self, n: u32, k: u8, v: u32) -> u32 { |
| 685 |
let mut i = 0; |
| 686 |
let mut mk = 0; |
| 687 |
let mut bits = 0; |
| 688 |
loop { |
| 689 |
let b = if i != 0 { k + i - 1 } else { k }; |
| 690 |
let a = 1 << b; |
| 691 |
if n <= mk + 3 * a { |
| 692 |
bits += self.count_quniform(n - mk, v - mk); |
| 693 |
break; |
| 694 |
} else { |
| 695 |
let t = v >= mk + a; |
| 696 |
bits += 1 << OD_BITRES; |
| 697 |
if t { |
| 698 |
i += 1; |
| 699 |
mk += a; |
| 700 |
} else { |
| 701 |
bits += (b as u32) << OD_BITRES; |
| 702 |
break; |
| 703 |
} |
| 704 |
} |
| 705 |
} |
| 706 |
bits |
| 707 |
} |
| 708 |
/// Write symbol `v` in `[0, n-1]` with parameter `k` as finite |
| 709 |
/// subexponential based on a reference `r` also in `[0, n-1]`. |
| 710 |
/// |
| 711 |
/// - `v`: value to encode |
| 712 |
/// - `n`: size of interval |
| 713 |
/// - `k`: "parameter" |
| 714 |
/// - `r`: reference |
| 715 |
fn write_unsigned_subexp_with_ref(&mut self, v: u32, n: u32, k: u8, r: u32) { |
| 716 |
if (r << 1) <= n { |
| 717 |
self.write_subexp(n, k, Self::recenter(r, v)); |
| 718 |
} else { |
| 719 |
self.write_subexp(n, k, Self::recenter(n - 1 - r, n - 1 - v)); |
| 720 |
} |
| 721 |
} |
| 722 |
/// Returns `QOD_BITRES` bits for symbol `v` in `[0, n-1]` |
| 723 |
/// with parameter `k` as finite subexponential based on a |
| 724 |
/// reference `r` also in `[0, n-1]`. |
| 725 |
/// |
| 726 |
/// - `v`: value to encode |
| 727 |
/// - `n`: size of interval |
| 728 |
/// - `k`: "parameter" |
| 729 |
/// - `r`: reference |
| 730 |
fn count_unsigned_subexp_with_ref( |
| 731 |
&self, v: u32, n: u32, k: u8, r: u32, |
| 732 |
) -> u32 { |
| 733 |
if (r << 1) <= n { |
| 734 |
self.count_subexp(n, k, Self::recenter(r, v)) |
| 735 |
} else { |
| 736 |
self.count_subexp(n, k, Self::recenter(n - 1 - r, n - 1 - v)) |
| 737 |
} |
| 738 |
} |
| 739 |
/// Write symbol `v` in `[-(n-1), n-1]` with parameter `k` as finite |
| 740 |
/// subexponential based on a reference `r` also in `[-(n-1), n-1]`. |
| 741 |
/// |
| 742 |
/// - `v`: value to encode |
| 743 |
/// - `n`: size of interval |
| 744 |
/// - `k`: "parameter" |
| 745 |
/// - `r`: reference |
| 746 |
fn write_signed_subexp_with_ref( |
| 747 |
&mut self, v: i32, low: i32, high: i32, k: u8, r: i32, |
| 748 |
) { |
| 749 |
self.write_unsigned_subexp_with_ref( |
| 750 |
(v - low) as u32, |
| 751 |
(high - low) as u32, |
| 752 |
k, |
| 753 |
(r - low) as u32, |
| 754 |
); |
| 755 |
} |
| 756 |
/// Returns `QOD_BITRES` bits for symbol `v` in `[-(n-1), n-1]` |
| 757 |
/// with parameter `k` as finite subexponential based on a |
| 758 |
/// reference `r` also in `[-(n-1), n-1]`. |
| 759 |
/// |
| 760 |
/// - `v`: value to encode |
| 761 |
/// - `n`: size of interval |
| 762 |
/// - `k`: "parameter" |
| 763 |
/// - `r`: reference |
| 764 |
fn count_signed_subexp_with_ref( |
| 765 |
&self, v: i32, low: i32, high: i32, k: u8, r: i32, |
| 766 |
) -> u32 { |
| 767 |
self.count_unsigned_subexp_with_ref( |
| 768 |
(v - low) as u32, |
| 769 |
(high - low) as u32, |
| 770 |
k, |
| 771 |
(r - low) as u32, |
| 772 |
) |
| 773 |
} |
| 774 |
/// Returns the number of bits "used" by the encoded symbols so far. |
| 775 |
/// This same number can be computed in either the encoder or the |
| 776 |
/// decoder, and is suitable for making coding decisions. The value |
| 777 |
/// will be the same whether using an `Encoder` or `Recorder`. |
| 778 |
/// |
| 779 |
/// Return: The integer number of bits. |
| 780 |
/// This will always be slightly larger than the exact value (e.g., all |
| 781 |
/// rounding error is in the positive direction). |
| 782 |
fn tell(&mut self) -> u32 { |
| 783 |
// The 10 here counteracts the offset of -9 baked into cnt, and adds 1 extra |
| 784 |
// bit, which we reserve for terminating the stream. |
| 785 |
(((self.stream_bits()) as i32) + (self.cnt as i32) + 10) as u32 |
| 786 |
+ (self.fake_bits_frac >> 8) |
| 787 |
} |
| 788 |
/// Returns the number of bits "used" by the encoded symbols so far. |
| 789 |
/// This same number can be computed in either the encoder or the |
| 790 |
/// decoder, and is suitable for making coding decisions. The value |
| 791 |
/// will be the same whether using an `Encoder` or `Recorder`. |
| 792 |
/// |
| 793 |
/// Return: The number of bits scaled by `2**OD_BITRES`. |
| 794 |
/// This will always be slightly larger than the exact value (e.g., all |
| 795 |
/// rounding error is in the positive direction). |
| 796 |
fn tell_frac(&mut self) -> u32 { |
| 797 |
Self::frac_compute(self.tell(), self.rng as u32) + self.fake_bits_frac |
| 798 |
} |
| 799 |
/// Save current point in coding/recording to a checkpoint that can |
| 800 |
/// be restored later. A `WriterCheckpoint` can be generated for an |
| 801 |
/// `Encoder` or `Recorder`, but can only be used to rollback the `Writer` |
| 802 |
/// instance from which it was generated. |
| 803 |
fn checkpoint(&mut self) -> WriterCheckpoint { |
| 804 |
StorageBackend::checkpoint(self) |
| 805 |
} |
| 806 |
/// Roll back a given `Writer` to the state saved in the `WriterCheckpoint` |
| 807 |
/// |
| 808 |
/// - 'wc': Saved `Writer` state/posiiton to restore |
| 809 |
fn rollback(&mut self, wc: &WriterCheckpoint) { |
| 810 |
StorageBackend::rollback(self, wc) |
| 811 |
} |
| 812 |
} |
| 813 |
|
| 814 |
pub trait BCodeWriter { |
| 815 |
fn recenter_nonneg(&mut self, r: u16, v: u16) -> u16; |
| 816 |
fn recenter_finite_nonneg(&mut self, n: u16, r: u16, v: u16) -> u16; |
| 817 |
/// # Errors |
| 818 |
/// |
| 819 |
/// - Returns `std::io::Error` if the writer cannot be written to. |
| 820 |
fn write_quniform(&mut self, n: u16, v: u16) -> Result<(), std::io::Error>; |
| 821 |
/// # Errors |
| 822 |
/// |
| 823 |
/// - Returns `std::io::Error` if the writer cannot be written to. |
| 824 |
fn write_subexpfin( |
| 825 |
&mut self, n: u16, k: u16, v: u16, |
| 826 |
) -> Result<(), std::io::Error>; |
| 827 |
/// # Errors |
| 828 |
/// |
| 829 |
/// - Returns `std::io::Error` if the writer cannot be written to. |
| 830 |
fn write_refsubexpfin( |
| 831 |
&mut self, n: u16, k: u16, r: i16, v: i16, |
| 832 |
) -> Result<(), std::io::Error>; |
| 833 |
/// # Errors |
| 834 |
/// |
| 835 |
/// - Returns `std::io::Error` if the writer cannot be written to. |
| 836 |
fn write_s_refsubexpfin( |
| 837 |
&mut self, n: u16, k: u16, r: i16, v: i16, |
| 838 |
) -> Result<(), std::io::Error>; |
| 839 |
} |
| 840 |
|
| 841 |
impl<W: io::Write> BCodeWriter for BitWriter<W, BigEndian> { |
| 842 |
fn recenter_nonneg(&mut self, r: u16, v: u16) -> u16 { |
| 843 |
/* Recenters a non-negative literal v around a reference r */ |
| 844 |
if v > (r << 1) { |
| 845 |
v |
| 846 |
} else if v >= r { |
| 847 |
(v - r) << 1 |
| 848 |
} else { |
| 849 |
((r - v) << 1) - 1 |
| 850 |
} |
| 851 |
} |
| 852 |
fn recenter_finite_nonneg(&mut self, n: u16, r: u16, v: u16) -> u16 { |
| 853 |
/* Recenters a non-negative literal v in [0, n-1] around a |
| 854 |
reference r also in [0, n-1] */ |
| 855 |
if (r << 1) <= n { |
| 856 |
self.recenter_nonneg(r, v) |
| 857 |
} else { |
| 858 |
self.recenter_nonneg(n - 1 - r, n - 1 - v) |
| 859 |
} |
| 860 |
} |
| 861 |
fn write_quniform(&mut self, n: u16, v: u16) -> Result<(), std::io::Error> { |
| 862 |
if n > 1 { |
| 863 |
let l = 16 - n.leading_zeros() as u8; |
| 864 |
let m = (1 << l) - n; |
| 865 |
if v < m { |
| 866 |
self.write_var(l as u32 - 1, v) |
| 867 |
} else { |
| 868 |
self.write_var(l as u32 - 1, m + ((v - m) >> 1))?; |
| 869 |
self.write::<1, u16>((v - m) & 1) |
| 870 |
} |
| 871 |
} else { |
| 872 |
Ok(()) |
| 873 |
} |
| 874 |
} |
| 875 |
fn write_subexpfin( |
| 876 |
&mut self, n: u16, k: u16, v: u16, |
| 877 |
) -> Result<(), std::io::Error> { |
| 878 |
/* Finite subexponential code that codes a symbol v in [0, n-1] with parameter k */ |
| 879 |
let mut i = 0; |
| 880 |
let mut mk = 0; |
| 881 |
loop { |
| 882 |
let b = if i > 0 { k + i - 1 } else { k }; |
| 883 |
let a = 1 << b; |
| 884 |
if n <= mk + 3 * a { |
| 885 |
return self.write_quniform(n - mk, v - mk); |
| 886 |
} else { |
| 887 |
let t = v >= mk + a; |
| 888 |
self.write_bit(t)?; |
| 889 |
if t { |
| 890 |
i += 1; |
| 891 |
mk += a; |
| 892 |
} else { |
| 893 |
return self.write_var(b as u32, v - mk); |
| 894 |
} |
| 895 |
} |
| 896 |
} |
| 897 |
} |
| 898 |
fn write_refsubexpfin( |
| 899 |
&mut self, n: u16, k: u16, r: i16, v: i16, |
| 900 |
) -> Result<(), std::io::Error> { |
| 901 |
/* Finite subexponential code that codes a symbol v in [0, n-1] with |
| 902 |
parameter k based on a reference ref also in [0, n-1]. |
| 903 |
Recenters symbol around r first and then uses a finite subexponential code. */ |
| 904 |
let recentered_v = self.recenter_finite_nonneg(n, r as u16, v as u16); |
| 905 |
self.write_subexpfin(n, k, recentered_v) |
| 906 |
} |
| 907 |
fn write_s_refsubexpfin( |
| 908 |
&mut self, n: u16, k: u16, r: i16, v: i16, |
| 909 |
) -> Result<(), std::io::Error> { |
| 910 |
/* Signed version of the above function */ |
| 911 |
self.write_refsubexpfin( |
| 912 |
(n << 1) - 1, |
| 913 |
k, |
| 914 |
r + (n - 1) as i16, |
| 915 |
v + (n - 1) as i16, |
| 916 |
) |
| 917 |
} |
| 918 |
} |
| 919 |
|
| 920 |
pub(crate) fn cdf_to_pdf<const CDF_LEN: usize>( |
| 921 |
cdf: &[u16; CDF_LEN], |
| 922 |
) -> [u16; CDF_LEN] { |
| 923 |
let mut pdf = [0; CDF_LEN]; |
| 924 |
let mut z = 32768u16 >> EC_PROB_SHIFT; |
| 925 |
for (d, &a) in pdf.iter_mut().zip(cdf.iter()) { |
| 926 |
*d = z - (a >> EC_PROB_SHIFT); |
| 927 |
z = a >> EC_PROB_SHIFT; |
| 928 |
} |
| 929 |
pdf |
| 930 |
} |
| 931 |
|
| 932 |
pub(crate) mod rust { |
| 933 |
// Function to update the CDF for Writer calls that do so. |
| 934 |
#[inline] |
| 935 |
pub fn update_cdf<const N: usize>(cdf: &mut [u16; N], val: u32) { |
| 936 |
use crate::context::CDF_LEN_MAX; |
| 937 |
let nsymbs = cdf.len(); |
| 938 |
let mut rate = 3 + (nsymbs >> 1).min(2); |
| 939 |
if let Some(count) = cdf.last_mut() { |
| 940 |
rate += (*count >> 4) as usize; |
| 941 |
*count += 1 - (*count >> 5); |
| 942 |
} else { |
| 943 |
return; |
| 944 |
} |
| 945 |
// Single loop (faster) |
| 946 |
for (i, v) in |
| 947 |
cdf[..nsymbs - 1].iter_mut().enumerate().take(CDF_LEN_MAX - 1) |
| 948 |
{ |
| 949 |
if i as u32 >= val { |
| 950 |
*v -= *v >> rate; |
| 951 |
} else { |
| 952 |
*v += (32768 - *v) >> rate; |
| 953 |
} |
| 954 |
} |
| 955 |
} |
| 956 |
} |
| 957 |
|
| 958 |
#[cfg(test)] |
| 959 |
mod test { |
| 960 |
use super::*; |
| 961 |
|
| 962 |
const WINDOW_SIZE: i16 = 32; |
| 963 |
const LOTS_OF_BITS: i16 = 0x4000; |
| 964 |
|
| 965 |
#[derive(Debug)] |
| 966 |
struct Reader<'a> { |
| 967 |
buf: &'a [u8], |
| 968 |
bptr: usize, |
| 969 |
dif: ec_window, |
| 970 |
rng: u16, |
| 971 |
cnt: i16, |
| 972 |
} |
| 973 |
|
| 974 |
impl<'a> Reader<'a> { |
| 975 |
fn new(buf: &'a [u8]) -> Self { |
| 976 |
let mut r = Reader { |
| 977 |
buf, |
| 978 |
bptr: 0, |
| 979 |
dif: (1 << (WINDOW_SIZE - 1)) - 1, |
| 980 |
rng: 0x8000, |
| 981 |
cnt: -15, |
| 982 |
}; |
| 983 |
r.refill(); |
| 984 |
r |
| 985 |
} |
| 986 |
|
| 987 |
fn refill(&mut self) { |
| 988 |
let mut s = WINDOW_SIZE - 9 - (self.cnt + 15); |
| 989 |
while s >= 0 && self.bptr < self.buf.len() { |
| 990 |
assert!(s <= WINDOW_SIZE - 8); |
| 991 |
self.dif ^= (self.buf[self.bptr] as ec_window) << s; |
| 992 |
self.cnt += 8; |
| 993 |
s -= 8; |
| 994 |
self.bptr += 1; |
| 995 |
} |
| 996 |
if self.bptr >= self.buf.len() { |
| 997 |
self.cnt = LOTS_OF_BITS; |
| 998 |
} |
| 999 |
} |
| 1000 |
|
| 1001 |
fn normalize(&mut self, dif: ec_window, rng: u32) { |
| 1002 |
assert!(rng <= 65536); |
| 1003 |
let d = rng.leading_zeros() - 16; |
| 1004 |
//let d = 16 - (32-rng.leading_zeros()); |
| 1005 |
self.cnt -= d as i16; |
| 1006 |
/*This is equivalent to shifting in 1's instead of 0's.*/ |
| 1007 |
self.dif = ((dif + 1) << d) - 1; |
| 1008 |
self.rng = (rng << d) as u16; |
| 1009 |
if self.cnt < 0 { |
| 1010 |
self.refill() |
| 1011 |
} |
| 1012 |
} |
| 1013 |
|
| 1014 |
fn bool(&mut self, f: u32) -> bool { |
| 1015 |
assert!(f < 32768); |
| 1016 |
let r = self.rng as u32; |
| 1017 |
assert!(self.dif >> (WINDOW_SIZE - 16) < r); |
| 1018 |
assert!(32768 <= r); |
| 1019 |
let v = (((r >> 8) * (f >> EC_PROB_SHIFT)) >> (7 - EC_PROB_SHIFT)) |
| 1020 |
+ EC_MIN_PROB; |
| 1021 |
let vw = v << (WINDOW_SIZE - 16); |
| 1022 |
let (dif, rng, ret) = if self.dif >= vw { |
| 1023 |
(self.dif - vw, r - v, false) |
| 1024 |
} else { |
| 1025 |
(self.dif, v, true) |
| 1026 |
}; |
| 1027 |
self.normalize(dif, rng); |
| 1028 |
ret |
| 1029 |
} |
| 1030 |
|
| 1031 |
fn symbol(&mut self, icdf: &[u16]) -> i32 { |
| 1032 |
let r = self.rng as u32; |
| 1033 |
assert!(self.dif >> (WINDOW_SIZE - 16) < r); |
| 1034 |
assert!(32768 <= r); |
| 1035 |
let n = icdf.len() as u32 - 1; |
| 1036 |
let c = self.dif >> (WINDOW_SIZE - 16); |
| 1037 |
let mut v = self.rng as u32; |
| 1038 |
let mut ret = 0i32; |
| 1039 |
let mut u = v; |
| 1040 |
v = ((r >> 8) * (icdf[ret as usize] as u32 >> EC_PROB_SHIFT)) |
| 1041 |
>> (7 - EC_PROB_SHIFT); |
| 1042 |
v += EC_MIN_PROB * (n - ret as u32); |
| 1043 |
while c < v { |
| 1044 |
u = v; |
| 1045 |
ret += 1; |
| 1046 |
v = ((r >> 8) * (icdf[ret as usize] as u32 >> EC_PROB_SHIFT)) |
| 1047 |
>> (7 - EC_PROB_SHIFT); |
| 1048 |
v += EC_MIN_PROB * (n - ret as u32); |
| 1049 |
} |
| 1050 |
assert!(v < u); |
| 1051 |
assert!(u <= r); |
| 1052 |
let new_dif = self.dif - (v << (WINDOW_SIZE - 16)); |
| 1053 |
self.normalize(new_dif, u - v); |
| 1054 |
ret |
| 1055 |
} |
| 1056 |
} |
| 1057 |
|
| 1058 |
#[test] |
| 1059 |
fn booleans() { |
| 1060 |
let mut w = WriterEncoder::new(); |
| 1061 |
|
| 1062 |
w.bool(false, 1); |
| 1063 |
w.bool(true, 2); |
| 1064 |
w.bool(false, 3); |
| 1065 |
w.bool(true, 1); |
| 1066 |
w.bool(true, 2); |
| 1067 |
w.bool(false, 3); |
| 1068 |
|
| 1069 |
let b = w.done(); |
| 1070 |
|
| 1071 |
let mut r = Reader::new(&b); |
| 1072 |
|
| 1073 |
assert!(!r.bool(1)); |
| 1074 |
assert!(r.bool(2)); |
| 1075 |
assert!(!r.bool(3)); |
| 1076 |
assert!(r.bool(1)); |
| 1077 |
assert!(r.bool(2)); |
| 1078 |
assert!(!r.bool(3)); |
| 1079 |
} |
| 1080 |
|
| 1081 |
#[test] |
| 1082 |
fn cdf() { |
| 1083 |
let cdf = [7296, 3819, 1716, 0]; |
| 1084 |
|
| 1085 |
let mut w = WriterEncoder::new(); |
| 1086 |
|
| 1087 |
w.symbol(0, &cdf); |
| 1088 |
w.symbol(0, &cdf); |
| 1089 |
w.symbol(0, &cdf); |
| 1090 |
w.symbol(1, &cdf); |
| 1091 |
w.symbol(1, &cdf); |
| 1092 |
w.symbol(1, &cdf); |
| 1093 |
w.symbol(2, &cdf); |
| 1094 |
w.symbol(2, &cdf); |
| 1095 |
w.symbol(2, &cdf); |
| 1096 |
|
| 1097 |
let b = w.done(); |
| 1098 |
|
| 1099 |
let mut r = Reader::new(&b); |
| 1100 |
|
| 1101 |
assert_eq!(r.symbol(&cdf), 0); |
| 1102 |
assert_eq!(r.symbol(&cdf), 0); |
| 1103 |
assert_eq!(r.symbol(&cdf), 0); |
| 1104 |
assert_eq!(r.symbol(&cdf), 1); |
| 1105 |
assert_eq!(r.symbol(&cdf), 1); |
| 1106 |
assert_eq!(r.symbol(&cdf), 1); |
| 1107 |
assert_eq!(r.symbol(&cdf), 2); |
| 1108 |
assert_eq!(r.symbol(&cdf), 2); |
| 1109 |
assert_eq!(r.symbol(&cdf), 2); |
| 1110 |
} |
| 1111 |
|
| 1112 |
#[test] |
| 1113 |
fn mixed() { |
| 1114 |
let cdf = [7296, 3819, 1716, 0]; |
| 1115 |
|
| 1116 |
let mut w = WriterEncoder::new(); |
| 1117 |
|
| 1118 |
w.symbol(0, &cdf); |
| 1119 |
w.bool(true, 2); |
| 1120 |
w.symbol(0, &cdf); |
| 1121 |
w.bool(true, 2); |
| 1122 |
w.symbol(0, &cdf); |
| 1123 |
w.bool(true, 2); |
| 1124 |
w.symbol(1, &cdf); |
| 1125 |
w.bool(true, 1); |
| 1126 |
w.symbol(1, &cdf); |
| 1127 |
w.bool(false, 2); |
| 1128 |
w.symbol(1, &cdf); |
| 1129 |
w.symbol(2, &cdf); |
| 1130 |
w.symbol(2, &cdf); |
| 1131 |
w.symbol(2, &cdf); |
| 1132 |
|
| 1133 |
let b = w.done(); |
| 1134 |
|
| 1135 |
let mut r = Reader::new(&b); |
| 1136 |
|
| 1137 |
assert_eq!(r.symbol(&cdf), 0); |
| 1138 |
assert!(r.bool(2)); |
| 1139 |
assert_eq!(r.symbol(&cdf), 0); |
| 1140 |
assert!(r.bool(2)); |
| 1141 |
assert_eq!(r.symbol(&cdf), 0); |
| 1142 |
assert!(r.bool(2)); |
| 1143 |
assert_eq!(r.symbol(&cdf), 1); |
| 1144 |
assert!(r.bool(1)); |
| 1145 |
assert_eq!(r.symbol(&cdf), 1); |
| 1146 |
assert!(!r.bool(2)); |
| 1147 |
assert_eq!(r.symbol(&cdf), 1); |
| 1148 |
assert_eq!(r.symbol(&cdf), 2); |
| 1149 |
assert_eq!(r.symbol(&cdf), 2); |
| 1150 |
assert_eq!(r.symbol(&cdf), 2); |
| 1151 |
} |
| 1152 |
} |