which type of ANS does brunsli use?

[xiaoxiongli]

Dear all,

I read the brunsli's ANS related code, such as AddCode or PutSymbol..., As you know, the ANS has a lot of variant, but I can not figure out which type of ANS the brunsli is using.

Could you please help me to understand the brunsli's ANS algorithm?

[eustas]

Hello.

It is somewhere in-between rANS and tANS.

First of all, let's drop BRUNSLI_USE_MULT_BY_RECIPROCAL, it is just an optimisation. What's left?:

uint32_t PutSymbol(const ANSEncSymbolInfo t, uint8_t* nbits) {
  // By default, no normalisation is required.
  uint32_t bits = 0;
  *nbits = 0;
  // Check if normalisation is required...
  // rANS wiki: inverse of: if(x < (1 << 16)) x = (x << 16) + read16bits()
  if ((state_ >> (32 - BRUNSLI_ANS_LOG_TAB_SIZE)) >= t.freq_) {
    // Get normalisation output and normalise.
    bits = state_ & 0xffff;
    state_ >>= 16;
    *nbits = 16;
  }
  // rANS wiki: C(x,s) = (floor(x / f[s]) << n) + (x % f[s]) + CDF[s]
  state_ = ((state_ / t.freq_) << BRUNSLI_ANS_LOG_TAB_SIZE) + (state_ % t.freq_) + t.start_;
  return bits;
}

[eustas]

Hope it helps. If you have more questions, feel free to reopen the issue.

[xiaoxiongli]

Dear @eustas,

thank you very much for you reply. ^_^

And I feel confused about below ANS decode code in ReadSymbol and PutSymbol function:

Why the below two code segment is inverse of each other?

Decode code segment: if (state < (1u << 16u)) { state = (state_ << 16u) | in->GetNextWord(); }

Encode code segment: if ((state_ >> (32 - BRUNSLI_ANS_LOG_TABSIZE)) >= t.freq) { // Get normalisation output and normalise. bits = state & 0xffff; state >>= 16; *nbits = 16; }

BTW, I do not know how to reopen, so I just update comment here.