About Microsofts rANS Patent
In 2022, Microsoft won a patent on rANS[1, 2]. This endangers those, who are using rANS. The rANS algorithm was used and deployed, even years, before Microsoft filed the patent. The rANS entropy coder is used in JPEG XL[3], CRAM[4], Google Draco[5] and Oodle LZNA[6], to name a few. CRAM, Draco and LZNA could be cited as prior art, as they existed at least one year before the patent was filed.
Prior art
Practically every Range Asymmetric Numeral Systems (rANS) decoder operates in a two-phase-structure. During a first phase of the two-phase-structure, an output symbol is generated using the state of the rANS decoder. During a second phase of the two-phase-structure, the state of the rANS decoder is updated using the currently decoded output symbol and its probability informations associated to it; and during the second phase of the two-phase-structure, repeatedly, until the value of the state is greater than a treshold, thus the state contains enough informations to generate the next output symbol, a portion of the encoded input data from the buffer is merged into the state of the rANS decoder. This is examplified in the following code:
// in this example, we use ryg_rans[7], specifically, rans_byte.h
// This method is specifically covered by prior art [4,5,6]
RansState rans;
//...
for(i=0;i<n;++i)
{
// phase one
// generate an output symbol using the state of the rANS decoder
auto code = RansDecGet(&rans, scale_bits);
auto symbol = cum2sym[code]; // find CDF[symbol] <= code < CDF[symbol+1]
buffer[i] = symbol;
// phase two
auto start = CDF[symbol];
auto freq = CDF[symbol+1] - start;
// update the state of the rANS decoder using the symbol and the CDF.
RansDecAdvanceStep(&rans, start, freq, scale_bits);
// until the state is greater than a treshold, thus, contains enough
// information to generate the next output symbol, merge a portion
// of the encoded data into the state of the rANS decoder. That
// treshold being RANS_BYTE_L-1.
RansDecRenorm(&rans, &inbufptr);
// This could also be condensed into the folloring function call:
// RansDecAdvance(&rans, &inbufptr, start, freq, scale_bits);
}Generally, a patent, even if granted, can’t be enforced, if prior art exists.
The Patent
Ironically, the menacing patent claims 1, 19 and 20 describe an algorithm, that is (slightly) different from the rANS algorithm we are all familiar with:
RansState rans;
std::optional<uint8_t> last_symbol;
// ...
for(i=0;i<n;++i)
{
// phase one:
// Depending on a determination of whether or not an output
// symbol from a previous iteration was generated,
if(last_symbol)
{
// selectively update the state of the RANS decoder using
// probability information for the output symbol from the
// previous iteration.
auto start = CDF[*last_symbol];
auto freq = CDF[*last_symbol + 1] - start;
RansDecAdvanceStep(&rans, start, freq, scale_bits);
last_symbol.reset();
}
// phase two:
// depending on a determination of whether or not the state
// of the RANS decoder is greater than a treshold, thus contains
// enough information to generate the output symbol for the
// current iteration,
// selectively merge a "portion" of the encoded data from
// an input buffer into the state of the RANS decoder.
RansDecRenorm(&rans, &inbufptr);
// selectively generate the output symbol for the current
// iteration using the state of the RANS decoder.
auto code = RansDecGet(&rans, scale_bits);
auto symbol = cum2sym[code]; // find CDF[symbol] <= code < CDF[symbol+1]
buffer[i] = symbol;
last_symbol.emplace(symbol);
}This arrangement of steps is different from the arrangement of steps used in common rANS decoders (such as JPEG XL), including prior art (such as CRAM, Draco, LZNA and ryg_rans). That arrangement, described in the patent, doesn’t make any sense to me. The patent describes this variant as useful for hardware implementations; the patent’s summary says:
In this way, the RANS decoder can decode the encoded data in a computationally efficient manner using the special-purpose hardware.
Conclusion
The method described in the patent can be trivially avoided. The only reason, it makes even sense to implement it in this way is, because it (supposedly) allows for a specialized hardware instruction to combine the renormalization and the decoding of the next symbol. Though, it is quentionable, if it fullfills the non-obviousness criteria.
Get Dat Sword’s stories in your inbox
Join Medium for free to get updates from this writer.
To the same conclusion came James Bonfield in a discussion on the encode.su forum[8].
