Recursive Range Reduction (3R) HW&SW CODEC

I got the core part of the system working a few minutes ago :-D

More internal details will follow in the coming months.

It just occured to me... in my sleep :-D

The 3R code is also useful for geographic (or geometric) data coding.

Imagine you're creating a zoomable map of, for example, human population on Earth based on a system lile openstreetmap.org or google maps.

You might have a database of every inhabitant, that's about 7 billion entries, but you can't store or send that much data to the browser. What you can do however is send hierarchical data, with local sums over a sub-range of the location of interest.

Let's say you divide the globe into a 16x16 grid. If this is mapped over the Earth, 1/2 will be 0s because of the water that covers the globe (it's more like 2/3 but think of the people living on the islands).

You just have to store and transmit a 16*16=256 numbers block to the viewer. Many of these numbers are 0s and they are close to each other, 3R loves to remove consecutive 0s. 3R also adjusts the coding size for all the other numbers.

Now zoom in on one of the sub-zones : your viewer will fetch the corresponding 16*16 sub-block for the local data but with only 255 numbers inside (since you already know the total sum from the "top block".

If you want to have more accuracy, since your viewer might have a 1024² graphic resolution, you'll download more consecutive sub-blocks, but depending on the zooming factor, your sub-blocks might have too much resolution : no problem ! 3R blocks can be "partially decoded" and you can modify the decoder so it only outputs partial sums at a given level, and not the actual values.

But for now, I'll stay focused on high speed lossless image (de)compression.

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 !