 |
fk0 (10.07.2018 00:38) , в ответ на [Embedded compression libs] Сводный топик автор: Evgeny_CD
Русский народный range coder им. Дмитрия Субботина (Carry-less Range Coder), впервые публиковался в fido:
web.archive.org/web/20110118163354/http: …thread/e2b843e33e1580e1/943e331f61748c2b
(ниже будет приведён полный текст)
Версия на языке D, с "моделью нулевого порядка", вполне реализуемой на МК (так же вместо динамической модели может вполне выступать статическая таблица частот):
web.archive.org/web/20150811135321/http: …mars/compression/algorithm/rangecoding.d
Я переписывал её на C и пользовался.
Оригинал:
Hi, All!
Я тут подумал, что потери в 1% для арифметического кодера это все-таки слишком
много, и слегка его соптимизировал. Теперь он теряет всего где-то 0.05%, что
имхо уже ерунда.
Параллельно как-то сам собой установился новый рекорд на размер процедуры
Encode - всего 5 строчек. 8-)
───[ Hачала _
]────────────────────────────────────────────────────
/*
* Carryless rangecoder (c) 1999 by Dmitry Subbotin
*/
#define TopValue (1<<24)
#define BotValue (1<<16)
class RangeCoder
{
uint low, code, range, passed;
FILE *f;
void OutByte (uc c) { passed++; fputc(c,f); }
uc InByte () { passed++; return fgetc(f); }
public:
uint GetPassed () { return passed; }
void StartEncode (FILE *F) { f=F; passed=low=0; range= (uint) -1; }
void FinishEncode () { DO(4) OutByte(low>>24), low<<=8; }
void StartDecode (FILE *F) { passed=low=code=0;
range= (uint) -1;
f=F; DO(4) code= code<<8 | InByte();
}
void Encode (uint cum_freq, uint freq, uint tot_freq) {
low+= cum_freq*(range/=tot_freq);
range*= freq;
while (range < TopValue && ((low ^ low+range) < TopValue ||
range < BotValue && ((range= -low & BotValue-1), 1)))
OutByte(low>>24), range<<=8, low<<=8;
}
uint GetFreq (uint tot_freq) {
uint tmp= (code-low)/(range/=tot_freq);
if (tmp >= tot_freq) throw ("Input data corrupt");
return tmp;
}
void Decode (uint cum_freq, uint freq, uint tot_freq) {
low+= cum_freq*range;
range*= freq;
while (range < TopValue && ((low ^ low+range) < TopValue ||
range < BotValue && ((range= -low & BotValue-1), 1)))
code= code<<8 | InByte(), range<<=8, low<<=8;
}
};
───[ Концы _
]─────────────────────────────────────────────────────
ps. Кто не понял - DO это
#define DO(n) for(int _=0; _<n; _++)
taste you later,
morf
Исходник на D:
/** Code for range coding, derived from public domain work by Dmitry Subbotin
Authors: Dmitry Subbotin (initial author of the Carry-less Range Coder)
Wei Li (D language) <oldrev@gmail.com>
License: BSD
Reference: sachingarg.com/compression/entropy_coding/64bit/
*/
module dotmars.compression.algorithm.rangecoding;
import dotmars.base.stdtypes;
import dotmars.io.stream;
template RangeCodingBase()
{
const uint Top = 1 << 24;
const uint Bottom = 1 << 16;
uint m_low = 0;
uint m_range = uint.max;
}
struct RangeEncoding(M)
{
public alias RangeEncoding!(M) SelfType;
public alias M Model;
mixin RangeCodingBase;
private Model m_model;
private bool m_flushed = false;
private Sink!(ubyte) m_sink = null;
void init(Sink!(ubyte) sink)
{
assert(sink !is null);
m_sink = sink;
m_model.init();
}
void encodeRange(uint symbolLow, uint symbolHigh, uint totalRange)
{
m_range /= totalRange;
m_low += symbolLow * m_range;
m_range *= symbolHigh - symbolLow;
while ((m_low ^ (m_low + m_range)) < Top || m_range < Bottom && ((m_range = -m_low & (Bottom - 1)), true))
{
ubyte b = m_low >> (m_low.sizeof * 8 - 8);
m_sink(b);
m_range <<= 8;
m_low <<= 8;
}
}
void encode(uint symbol)
{
encodeRange(m_model.low(symbol), m_model.high(symbol), m_model.total);
m_model.update(symbol);
}
void flush()
{
if(!m_flushed)
{
for(size_t i = 0; i < m_low.sizeof; i++)
{
ubyte b = m_low >> (m_low.sizeof * 8 - 8);
m_sink(b);
m_low <<= 8;
}
m_flushed = true;
}
}
}
struct RangeDecoding(M)
{
public alias RangeDecoding!(M) SelfType;
public alias M Model;
mixin RangeCodingBase;
private Model m_model;
private uint m_code;
private Emitter!(ubyte) m_emitter;
void init(Emitter!(ubyte) emitter)
{
assert(emitter !is null);
m_emitter = emitter;
for(size_t i = 0; i < m_code.sizeof; i++)
{
m_code = (m_code << 8) | emitter();
}
m_model.init();
}
uint currentCount(uint totalRange) //积累频率
{
return (m_code - m_low) / (m_range /= totalRange);
}
void decodeRange(uint symbolLow, uint symbolHigh, uint totalRange)
{
m_low += symbolLow * m_range;
m_range *= symbolHigh - symbolLow;
while ((m_low ^ m_low + m_range) < Top || m_range < Bottom && ((m_range = -m_low & Bottom - 1), true))
{
m_code= m_code << 8 | m_emitter(), m_range <<= 8, m_low <<= 8;
}
}
uint decode()
{
uint count = currentCount(m_model.total);
uint sym = m_model.getSymbol(count);
decodeRange(m_model.low(sym), m_model.high(sym), m_model.total);
m_model.update(sym);
return sym;
}
}
//简单0阶模型
struct OrderZeroModel(uint MaxSym, uint MaxScl = 16383)
{
public const uint MaxSymbol = MaxSym;
public const uint MaxScale = MaxScl;
static if(MaxScale > 0xffff)
private uint[MaxSymbol + 2] m_freq;
else
private ushort[MaxSymbol + 2] m_freq;
void init()
{
for(size_t i = 0; i < m_freq.length; i++)
{
m_freq[i] = i;
}
}
private void rescale()
{
for(uint i = 1; i < m_freq.length; i++)
{
m_freq[i] /= 2;
if(m_freq[i] <= m_freq[i - 1])
m_freq[i] = m_freq[ i - 1] + 1;
}
}
void update(uint sym)
{
for(size_t i = sym + 1; i < m_freq.length; i++) {
m_freq[i]++;
}
if(total() >= MaxScale)
rescale();
}
uint getSymbol(uint n)
{
uint sym = MaxSymbol;
while(m_freq[sym] > n) --sym;
return sym;
}
uint total()
{
return m_freq[m_freq.length - 1];
}
uint low(uint sym)
{
return m_freq[sym];
}
uint high(uint sym)
{
return m_freq[sym + 1];
}
uint opIndex(uint rhs)
{
return m_freq[rhs];
}
}
|