Средства и методы разработки

Русский народный range coder им. Дмитрия Субботина (Carry-less Range Coder), впервые публиковался в fido: https://web.archiv …580e1/943e331f61748c2b (ниже будет приведён полный текст) Версия на языке D, с "моделью нулевого порядка", вполне реализуемой на МК (так же вместо динамической модели может вполне выступать статическая таблица частот): https://web.archiv …lgorithm/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:	http://sachingarg. …/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];
	}
}