Trait constriction::stream::model::EntropyModel
source · pub trait EntropyModel<const PRECISION: usize> {
type Symbol;
type Probability: BitArray;
}Expand description
Base trait for probabilistic models of a data source.
All entropy models (see module level documentation) that can be used for
encoding and/or decoding with stream codes must implement this trait and at least one of
EncoderModel and/or DecoderModel. This trait exposes the type of Symbols
over which the entropy model is defined, the type that is used to represent a
Probability in fixed-point arithmetic, and the fixed point PRECISION (see
discussion of type parameters).
Blanket Implementation for &impl EntropyModel
We provide the following blanket implementation for references to EntropyModels:
impl<M, const PRECISION: usize> EntropyModel<PRECISION> for &M
where
M: EntropyModel<PRECISION> + ?Sized
{ ... }This means that, if some type M implements EntropyModel<PRECISION> for some
PRECISION, then so does the reference type &M. Analogous blanket implementations are
provided for the traits EncoderModel, DecoderModel, and
IterableEntropyModel. The implementations simply delegate all calls to M (which is
possible since all methods only take an &self receiver). Therefore:
- you don’t need to (and, in fact, currently can’t) implement
EntropyModel,EncoderModel, orDecoderModelfor reference types&M; just implement these traits for “value types”Mand you’ll get the implementation for the corresponding reference types for free. - when you write a function or method that takes a generic entropy model as an argument,
always take the entropy model (formally) by value (i.e., declare your function as
fn f(model: impl EntropyModel<PRECISION>)or asf<M: EntropyModel<PRECISION>>(model: M)). Since all references toEntropyModels are alsoEntropyModels themselves, a function with one of these signatures can be called with an entropy model passed in either by value or by reference. If your function or method needs to pass out several copies ofmodelthen add an extra boundM: Copy(see, e.g.,Encode::encode_iid_symbols). This will allow users to call your function either with a reference to an entropy model (all shared references implementCopy), or with some cheaply copyable entropy model such as a view to a lookup model (seeLookupDecoderModel::as_view).
See Also
Required Associated Types§
sourcetype Symbol
type Symbol
The type of data over which the entropy model is defined.
This is the type of an item of the uncompressed data.
Note that, although any given EntropyModel has a fixed associated Symbol type,
this doesn’t prevent you from encoding heterogeneous sequences of symbols where each
symbol has a different type. You can use a different EntropyModel with a different
associated Symbol type for each symbol.
sourcetype Probability: BitArray
type Probability: BitArray
The type used to represent probabilities, cumulatives, and quantiles.
This is a primitive unsigned integer type that must hold at least PRECISION bits.
An integer value p: Probability semantically represents the probability,
cumulative, or quantile p * 2.0^(-PRECISION) (where ^ denotes exponentiation and
PRECISION is a const generic parameter of the trait EntropyModel).
In many places where constriction’s public API returns probabilities, they have
already been verified to be nonzero. In such a case, the probability is returned as
a Probability::NonZero, which denotes the corresponding non-zeroable type (e.g.,
if Probability is u32 then Probability::NonZero is
NonZeroU32). The “bare” Probability type is mostly used
for left-cumulatives and quantiles (i.e., for points on the y-axis in the graph of a
cumulative distribution function).
Enforcing the Constraints
The constraint that 1 <= PRECISION <= Probability::BITS currently isn’t enforced
statically since Rust does not yet allow const expressions in type bounds.
Therefore, if your implementation of EntropyModel relies on this constraint at any
point, it should state it as an assertion: assert!(1 <= PRECISOIN && PRECISION <= Probability::BITS). This assertion has zero runtime cost because it can be
trivially evaluated at compile time and therefore will be optimized out if it holds.
The implementations provided by constriction strive to include this and related
assertions wherever necessary.
(Internal) Representation of Probability One
The case of “probability one” is treated specially. This case does not come up in
the public API since we disallow probability one for any individual symbol under any
entropy model, and since all left-sided cumulatives always correspond to a symbol
with nonzero probability. But the value “one” still comes up internally as the
right-cumulative of the last allowed symbol for any model. Although our treatment of
“probability one” can thus be considered an implementation detail, it is likely to
become an issue in third-party implementations of EntropyModel, so it is worth
documenting our recommended treatment.
We internally represent “probability one” by its normal fixed-point representation
of p = 1 << PRECISION (i.e., p = 2^PRECISION in mathematical notation) if this
value fits into Probability, i.e., if PRECISION != Probability::BITS. In the
(uncommon) case where PRECISION == Probability::BITS, we represent “probability
one” as the integer zero (i.e., cutting off the overflowing bit). This means that
any probability that is guaranteed to not be one can always be calculated by
subtracting its left-sided cumulative from its right-sided cumulative in wrapping
arithmetic. However, this convention means that one has to be careful not to confuse
probability zero with probabilty one. In our implementations, these two possible
interpretations of the integer p = 0 always turned out to be easy to disambiguate
statically.