Close

First sample source code snippet

A project log for Recursive Range Reduction (3R) HW&SW CODEC

A high speed circuit design in JS and VHDL for decoding 3R bitstreams, a "quasi-entropy" code that compacts series of correlated numbers.

yann-guidon-ygdesYann Guidon / YGDES 08/23/2015 at 03:250 Comments

I've been working during all August to crack this code and here is one of the keys to the 3R stream decoder. Small, fast and easy, you can port it to most languages :

function decode_3R(DEPTH, // Log2(sample number)
     stream) {  // pointer to the array of sample

  var A=DEPTH-1,    // stack pointer
      C=0,          // loop counter
      R,            // checksum register
      S=1<<DEPTH,   // Shift register
      STACK=[],     // no-init stack
      T=stream[0],  // Temp. register
      flux_index=1,
      V;            // input value

  R=T;  // init
  function out_value(val) {
    R -= val;
    // insert your filter code here
  }

  do {
    while (true) {
      V = stream[flux_index++];  // read one input value
      if (S & 2)   
        break;

      STACK[A--] = T-V;
      T = V;
      S = S >> 1;
    }

    out_value(V);
    out_value(T-V);

    A=1;  // new stack pointer
    /* branch-prediction-friendly version
    if (C & 2) {
      A=2;
      if (C & 4) {
        A=3;
        if (C & 8) {
          A=4;
          if (C & 16) {
            A=5;          */
            while ( C & (1<<A) )
              A++;  /*
          }
        }
      }
    } */

    T = STACK[A--];
    S =
    C = C+2;
  } while (C < 1<<DEPTH);
  return R; // R=0 if the block is valid
}

function start() {
  var r=decode_3R(4, stream3R);
  alert(r==0?"OK":"Error");
}

It's hard to make it smaller and simpler. The 2003 source code loop was recursive and shorter but much less efficient...

One of the most obvious characteristics is that the size of the incoming sample block must be a power of two. In practice, it's not a huge problem because you can pad with 0s and the encoder will trim (most of) them anyway.

Oh and this version has a tiny but welcome perk : checksums are inherent to the codec's design, no need to add another (unless you're paranoid).

More to come soon !

Discussions