/*Daala video codec | |

Copyright (c) 2001-2013 Daala project contributors. All rights reserved. | |

Redistribution and use in source and binary forms, with or without | |

modification, are permitted provided that the following conditions are met: | |

- Redistributions of source code must retain the above copyright notice, this | |

list of conditions and the following disclaimer. | |

- Redistributions in binary form must reproduce the above copyright notice, | |

this list of conditions and the following disclaimer in the documentation | |

and/or other materials provided with the distribution. | |

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" | |

AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |

IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE | |

DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE | |

FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | |

DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR | |

SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER | |

CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, | |

OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |

OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.*/ | |

#if !defined(_entcode_H) | |

#define _entcode_H (1) | |

#include <limits.h> | |

#include <stddef.h> | |

#include "av1/common/odintrin.h" | |

/*Set this flag 1 to enable a "reduced overhead" version of the entropy coder. | |

This uses a partition function that more accurately follows the input | |

probability estimates at the expense of some additional CPU cost (though | |

still an order of magnitude less than a full division). | |

In classic arithmetic coding, the partition function maps a value x in the | |

range [0, ft] to a value in y in [0, r] with 0 < ft <= r via | |

y = x*r/ft. | |

Any deviation from this value increases coding inefficiency. | |

To avoid divisions, we require ft <= r < 2*ft (enforcing it by shifting up | |

ft if necessary), and replace that function with | |

y = x + OD_MINI(x, r - ft). | |

This counts values of x smaller than r - ft double compared to values larger | |

than r - ft, which over-estimates the probability of symbols at the start of | |

the alphabet, and under-estimates the probability of symbols at the end of | |

the alphabet. | |

The overall coding inefficiency assuming accurate probability models and | |

independent symbols is in the 1% range, which is similar to that of CABAC. | |

To reduce overhead even further, we split this into two cases: | |

1) r - ft > ft - (r - ft). | |

That is, we have more values of x that are double-counted than | |

single-counted. | |

In this case, we still double-count the first 2*r - 3*ft values of x, but | |

after that we alternate between single-counting and double-counting for | |

the rest. | |

2) r - ft < ft - (r - ft). | |

That is, we have more values of x that are single-counted than | |

double-counted. | |

In this case, we alternate between single-counting and double-counting for | |

the first 2*(r - ft) values of x, and single-count the rest. | |

For two equiprobable symbols in different places in the alphabet, this | |

reduces the maximum ratio of over-estimation to under-estimation from 2:1 | |

for the previous partition function to either 4:3 or 3:2 (for each of the | |

two cases above, respectively), assuming symbol probabilities significantly | |

greater than 1/32768. | |

That reduces the worst-case per-symbol overhead from 1 bit to 0.58 bits. | |

The resulting function is | |

e = OD_MAXI(2*r - 3*ft, 0); | |

y = x + OD_MINI(x, e) + OD_MINI(OD_MAXI(x - e, 0) >> 1, r - ft). | |

Here, e is a value that is greater than 0 in case 1, and 0 in case 2. | |

This function is about 3 times as expensive to evaluate as the high-overhead | |

version, but still an order of magnitude cheaper than a division, since it | |

is composed only of very simple operations. | |

Because we want to fit in 16-bit registers and must use unsigned values to do | |

so, we use saturating subtraction to enforce the maximums with 0. | |

Enabling this reduces the measured overhead in ectest from 0.805% to 0.621% | |

(vs. 0.022% for the division-based partition function with r much greater | |

than ft). | |

It improves performance on ntt-short-1 by about 0.3%.*/ | |

#define OD_EC_REDUCED_OVERHEAD (1) | |

/*OPT: od_ec_window must be at least 32 bits, but if you have fast arithmetic | |

on a larger type, you can speed up the decoder by using it here.*/ | |

typedef uint32_t od_ec_window; | |

#define OD_EC_WINDOW_SIZE ((int)sizeof(od_ec_window) * CHAR_BIT) | |

/*Unsigned subtraction with unsigned saturation. | |

This implementation of the macro is intentionally chosen to increase the | |

number of common subexpressions in the reduced-overhead partition function. | |

This matters for C code, but it would not for hardware with a saturating | |

subtraction instruction.*/ | |

#define OD_SUBSATU(a, b) ((a)-OD_MINI(a, b)) | |

/*The number of bits to use for the range-coded part of unsigned integers.*/ | |

#define OD_EC_UINT_BITS (4) | |

/*The resolution of fractional-precision bit usage measurements, i.e., | |

3 => 1/8th bits.*/ | |

#define OD_BITRES (3) | |

extern const uint16_t OD_UNIFORM_CDFS_Q15[135]; | |

/*Returns a Q15 CDF for a uniform probability distribution of the given size. | |

n: The size of the distribution. | |

This must be at least 2, and no more than 16.*/ | |

#define OD_UNIFORM_CDF_Q15(n) (OD_UNIFORM_CDFS_Q15 + ((n) * ((n)-1) >> 1) - 1) | |

/*See entcode.c for further documentation.*/ | |

OD_WARN_UNUSED_RESULT uint32_t od_ec_tell_frac(uint32_t nbits_total, | |

uint32_t rng); | |

#endif |