Skip to content

SMTF Rice

Jump to bottom Edit New page
Brendan G Bohannon edited this page Jul 12, 2016 · 15 revisions

Table of Contents

Rice Variants

Different variations of Rice coding are possible:

  • Adaptive vs non-Adaptive
  • Schemes to limit the maximum code length
  • ...
  • AdRice may also be combined with an MTF variant to make a cheaper approximation of an adaptive-Huffman coding.

AdRice / AdRiceLL

Example for a bitstream encoded in LSB-first order, with values encoded with the LSB first in the bitstream.

Adaptive Rice with Length Limiting (AdRiceLL) may be used for commands and values. This consists of a unary coded Q value followed by Rk suffix bits. The Rk value is updated after every symbol depending on the value of Q.

  • Q=0..7: Encoded as a normal AdRice value.
    • Q=0: Rk'=Rk-1;
    • Q=1: Rk'=Rk;
    • Q=2|3: Rk'=Rk+1;
    • Q=4..7: Rk'=Rk+2;
  • AdRiceLL:
    • Q>=8: Encoded as 5+(Q-8)*3 bits. Rk'=Rk+3+(Q-8);
  • Rk is kept in the range of 0 to 15.
Example (Q Prefix Bits):
  • 0, Q=0, Rk=Rk-1;
  • 10, Q=1, Rk=Rk
  • 110, Q=2, Rk=Rk+1
  • 1110, Q=3, Rk=Rk+1
  • 11110, Q=4, Rk=Rk+2
  • ...
  • 11111110, Q=7, Rk=Rk+2
If Q is greater or equal to 8, then it will instead indicate the length of the suffix, with 5+(Q-8)*3 bits for the suffix. If the suffix is given as J, then the coded value is ((Q<

An Rice-coded value will have a Rk-bit suffix, ex:

  • 10xx (Q=1, Rk=2, Rk'=2)
  • 0xxxx (Q=0, Rk=4, Rk'=3)
And:
  • 1011, Encodes a logical 7 (Rk=2, Rk'=2)
  • 110101, Encodes a logical 21 (Rk=3, Rk'=4)
AdSRiceLL will be a signed variant used for signed values. These will have the sign folded into the LSB (0, -1, 1, -2, 2, -3, 3, ...).

AdRiceLL16

AdRiceLL variant constrained to a maximum coded symbol length of 16 bits.

  • Rk constrained to range of 0..7
  • Q constrained to 0..6
    • Q=0: Rk'=Rk-1;
    • Q=1: Rk'=Rk;
    • Q=2|3: Rk'=Rk+1;
    • Q=4|5: Rk'=Rk+2;
    • Q=6: Symbol is encoded as a 9 bit suffix, Rk'=Rk+3
  • Symbol range is 0..511
A Q=6 symbol will look like:
  • 1111-110x xxxx-xxxx
Longest Non-Escape Symbols:
  • Rk=7: 1110-xxxx xxx (11 bits, 384..511)
  • Rk=6: 1111-10xx xxxx (12 bits, 256..319)
Potential advantage is allowing a single big lookup table (no general-case fallbacks).
  • However, such a massive LUT would require 1MB (w/ 16 bit entries)
    • kkkl-lllv vvvv-vvvv
    • Potentially pretty bad for cache if done this way.
  • Could use a LUT only for non-escape symbols (Longest=12 bit):
    • Reduces LUT size to 64kB
    • Still requires an if-branch fallback case (if cheaper).
Possibility 2 (AdRiceLL14):
  • Rk constrained to range of 0..7 (or 0..8)
  • Q constrained to 0..4
    • Q=0: Rk'=Rk-1;
    • Q=1: Rk'=Rk;
    • Q=2|3: Rk'=Rk+1;
    • Q=4: Symbol is encoded as a 9 bit suffix, Rk'=Rk+3
  • Symbol range is 0..511
This limits the longest case to 14 bits:
  • 256kB for full LUT.
  • Longest Non-Escape is 11 bits.

AdRiceLL16B

Possibility 3 (AdRiceLL16B):

  • Rk constrained to range of 0..7 (or 0..8)
  • Q constrained to 0..6
    • Q=0: Rk'=Rk-1;
    • Q=1: Rk'=Rk;
    • Q=2|3: Rk'=Rk+1;
    • Q=4: Symbol is encoded as a 7 bit suffix, Rk'=Rk+2 (12 bits)
    • Q=5: Symbol is encoded as a 8 bit suffix, Rk'=Rk+2 (14 bits)
    • Q=6: Symbol is encoded as a 9 bit suffix, Rk'=Rk+3 (16 bits)
  • Symbol range is 0..511
This design could make more effective use of a 12-bit LUT.

MTF Variants

MTF Variants can help dealing with a more arbitrary mix of symbols:

  • Traditional MTF tends to be rather slow, so isn't used here.
  • There is a fast rotate-and-swap-once MTF variant, but effectiveness is limited.

SMTF

SMTF:

  • Values are encoded as a AdRiceLL encoded index(I).
  • 0: Returns the value in position 0.
  • 1-31: Swap I with I-1, returning the value which was previously in I.
  • 32-255: Rotate the table back 1 position, swapping the new 0 with the old I, returning the value previously at I.
SMTF+AdRice values are encoded as their indices, with the table swapping around such that more common symbols have smaller index values. Larger indices move to the front of the table, with the symbol that falls off the end reappearing in the "hole" left by that symbol. In this way the entire alphabet remains reachable.

This basic scheme (just using normal AdRice) is used for entropy coding commands in BTIC1H.

STF2

STF2: Another possibility is STF2:

  • Values are encoded as a AdRiceLL encoded index(I).
  • Swap I with (I*7)/8, returning the value that was at I.
    • This gives comparable results to SMTF, but avoids needing any branches, and is a little faster.
    • In some tests gives a closer-to-optimal ordering vs SMTF.
This scheme is currently used in BTIC4B.

Code Examples

Example, Decoding a Rice value with a table: 

 int LQTVQ_ReadAdRiceLL(BT4A_Context *ctx, byte *rk)
 {
 	int v, b;
 	int i, j, k, l;
 	b=LQTVQ_Peek8Bits(ctx);
 	j=lqtvq_decrice8[(*rk<<8)|b];
 	if(j)
 	{
 		i=(u16)j;
 		LQTVQ_SkipNBits(ctx, (j>>16)&15);
 		*rk=(j>>20)&15;
 		return(i);
 	}
 	i=LQTVQ_ReadAdRiceILL(ctx, rk);
 	return(i);
 }

lqtvq_decrice8

  • Index: Low 8=8 bits from bit-window. High 4=Rk.
  • Contents: 0..15=value, 16..19=length, 20..23=new Rk.
  • Table is constant or built during initialization.
  • 8 bits is because table needs to be small to hopefully fit in cache.
    • This table generally needs 16kB. Not ideal, but workable.
    • Actually, table could probably be reduced to 8kB
    • 0..7=value, 8..11=length, 12..15=new Rk.
Peeking 8 bits from the bit window: 
 int LQTVQ_Peek8Bits(BT4A_Context *ctx)
 {
 	u32 bw;
 	int bp, bits;
 	bp=ctx->bit_pos;
 	bw=ctx->bit_win;
 	bits=(byte)(bw>>bp);
 	return(bits);
 }

Advancing the window forwards a few bits: 

 void LQTVQ_SkipNBits(BT4A_Context *ctx, int len)
 {
 	int bp;
 	bp=ctx->bit_pos+len;
 	ctx->cs+=bp>>3;
 	ctx->bit_win=*(u32 *)ctx->cs;
 	ctx->bit_pos=bp&7;
 }

Reading a symbol (SMTF): 

 int LQTVQ_ReadSymbolSmtf(BT4A_Context *ctx,
 	BT4A_SmtfState *st)
 {
 	int i0, i1, i2, i3;
 	int i;
 	i=LQTVQ_ReadAdRiceLL(ctx, &(st->rk));
 	if(!i)
 	{
 		i0=(byte)(st->rov+i);
 		i2=st->tab[i0];
 		return(i2);
 	}
 	if(i<32)
 	{
 		i0=(byte)(st->rov+i);		i1=(byte)(st->rov+i-1);
 		i2=st->tab[i0];		i3=st->tab[i1];
 		st->tab[i0]=i3;		st->tab[i1]=i2;
 		st->idx[i2]=i1;		st->idx[i3]=i0;
 		return(i2);
 	}
 	i0=(byte)(st->rov+i);	i1=(byte)(st->rov-1);
 	i2=st->tab[i0];		i3=st->tab[i1];
 	st->tab[i0]=i3;		st->tab[i1]=i2;
 	st->idx[i2]=i1;		st->idx[i3]=i0;
 	st->rov--;
 	return(i2);
 }

Reading a symbol (STF2): 

 int BTIC4B_ReadSymbolSmtf(BTIC4B_Context *ctx,
 	BTIC4B_SmtfState *st)
 {
 	int i0, i1, i2, i3;
 	int i;
 	i=BTIC4B_ReadAdRiceLL(ctx, &(st->rk));
 	i0=i;			i1=(i*7)>>3;
 	i2=st->tab[i0];		i3=st->tab[i1];
 	st->tab[i0]=i3;		st->tab[i1]=i2;
 	return(i2);
 }

Read the Rice Q prefix: 

 int LQTVQ_ReadRiceQ(BT4A_Context *ctx)
 {
 	int v, b;
 	int i, j, k, l;
 	b=LQTVQ_Peek8Bits(ctx);
 	if(b!=255)
 	{
 		v=lqtvq_decriceq8[b];
 		LQTVQ_SkipNBits(ctx, v+1);
 		return(v);
 	}
 	LQTVQ_Skip8Bits(ctx);
 	v=8;
 	b=LQTVQ_Peek8Bits(ctx);
 	while(b==255)
 		{ LQTVQ_Skip8Bits(ctx); v+=8; b=LQTVQ_Peek8Bits(ctx); }
 	i=lqtvq_decriceq8[b];
 	LQTVQ_SkipNBits(ctx, i+1);
 	return(v+i);
 }

lqtvq_decriceq8:

  • Table giving how number of 1 bits are in the Q prefix.
  • This table is constant or built during initialization.
    • 255 is special because this means the Q prefix is longer than a single byte.
Read Rice internal (if the main lookup fails): 
 int LQTVQ_ReadAdRiceILL(BT4A_Context *ctx, byte *rk)
 {
 	int q, k, b, v;
 	int j;
 	k=*rk;
 	q=LQTVQ_ReadRiceQ(ctx);
 	if(q>=8)
 	{
 		v=LQTVQ_ReadNBits(ctx, 5+(q-8)*3);
 		*rk=k+3+(q-8);
 		return(v);
 	}
 	b=LQTVQ_ReadNBits(ctx, k);
 	v=(q<<k)|b;
 	*rk=lqtvq_decricenk8[(k<<4)|q];
 	return(v);
 }
Add a custom footer
Add a custom sidebar
Clone this wiki locally