Kodek

An interesting test development, and how the company got its name. K represents a constant used in mathematics, and a ring is a mathematical group object. The Kodek itself is a data compression idea, to store information in the topology of a data structure. The topology is modified in an exact sequence, and sometimes one of two modifications can be done instead of just the one defaulting modification, and reversing the modifications can deterministically detect which of the two modifications was done, when there is an option for such.

The code below is not working. The theoretical proof that some method will work involves the construction of bit streams which do not have a 50:50 ratio of zeros to ones, with the added condition that any zero can be made a one (or one a zero), and if turned back zero, the bit stream can be reversed. Then a sufficient (currently known best is less than fifty five) odd multiple of independent such things, can be considered together, and a majority indication would have more than two zeros for every one bit. At this point an error correction code exists providing a real bit stream of n bits per ((2+n):1) or n+3 bits of virtual stream, all mapped from a fixed number of bits in size bit generator.

This page is an investigation into other methods which may improve on those limits. An extensive investigation into bit asymmetric generation, while avoiding direct state mapping problems of there not being enough zero states to identify with every one of the one states. This is exceedingly difficult. The most effective method so far has been to take advantage of process noncommutivity, but generating a large bit state bias is hard, and so needs many parallel elements with a bias, in order to aggregate a sufficient statistical bias.

The option of which modification represents a bit value, and because the topology representation does not grow in size; repeating the processing can store any number of bits. The bits will be detected and decoded off from the topology in the reverse order they were placed onto the topology. The code below works with 32 bit integers at a time.

Port 287 has an IANA reservation for a block protocol based on a stream implementation of this technology. The current idea is a 4096 bytes to 32 bits implementation with some stream checking, working as FilterInputStream and FilterOutputStream stream adapters. Mark and reset are supported, and development of the best way to offer a compressed collection is being investigated.


/*
* (C) 2016 K Ring Technologies Ltd.
* All right reserved.
* A request to use this code can be sent to <jacko@kring.co.uk>.
*/
package uk.co.kring.data;

//==========================================================================
// K CODEC PACKING ALGORITHM (C)2016 K RING TECHNOLOGIES LTD.
//==========================================================================

//The K codec is an interesting algorithm for data compression. A reversable
//LCG PRBS goes through a sequence, and has branch points in the sequence as
//data is modulating the stream. The nature of any branch point, and unique
//reverse detection, requires that a choice of which branch to follow is
//decided mostly without user data choice. Ocassionally, it however does
//allow the opertunity for a bit decision to be placed (via what I term
//modulation) in the stream of branches, at no storage cost.

//Quite a lot of branches have to be sorted though to find what is refered
//to as a "strictly long" branch (where the decode is certain). This branch
//has the amazing property of unique decode, as the alternate paths of
//modulation will NEVER be confused in decode.

//"To make a rare event rarer still increases its self information. The rare
//event being detectable with a know statistical probability, can store more
//information by virtue of a deviation from this known probability. The
//deviation can be measured and the non modulated statistic restored, for
//further detection."

//The code is not that efficient, and has a bias for backup, not restore speed.
//=============================================================================

/**
*
* @author Jacko
*/
public class Kodek {

  //PRBS

  /* (a^b)%m */
  private int powmod(int a, int b, int m) {
    int x = 1, y = a;
    if(y > a) y %= m;
    while(b > 0) {
      if(b%2 == 1) {
        x *= y;
        if(x > m) x %= m;
      }
      y *= y;
      if(y > m) y %= m;
      b /= 2;
    }
    return x;
  }

  private int phi(int m) {
    int p = 1;
    int f = 2;
    int lf = 1;//last factor
    while(f < 65536) {
      if(m%f == 0) {
        m /= f;
        if(lf == f) p *= f; else p *= (f-1);
        lf = f;
      } else {
        f += 1;//slow, but correct
      }
      if(m == 1) break;
    }
    if(m != 1) p *= (m - 1);//remaining prime
    return p;
  }

  private int inverse(int a, int m) {
    return powmod(a, phi(m) - 1, m);
  }

  //sequence travel functions

  //the SEED contains the compressed information statistic
  int seed = 7;

  //these four are the sequencing control numbers, constants (sort of)
  private final int b[] = { 411, 713 };
  private final int i[] = new int[2];
  private final int mod = 34567;
  private boolean done = false;

  private void RevTravel(boolean val) {
    if(!done) {
      i[0] = inverse(b[0], mod);
      i[1] = inverse(b[1], mod);
      done = true;//don't do more than once!
    }
    int a = i[0];
    int c = b[1];
    if(val) {
      a = i[1];
      c = b[0];
    }
    int tmp = seed - c;
    if(tmp < 0) tmp += mod;//modulo
    seed = powmod(a * tmp, 1, mod);
  }

  private void ForTravel(boolean val) {
    int a = b[0];
    int c = b[1];
    if(val) {
      int t = a;
      a = c;
      c = t;
    }
    seed = powmod(a * seed + c, 1, mod);
  }

  private boolean stateLong() {
    return (seed & 4) == 0;//any bit except LSB?
  }

  //branch coding functions

  private void RevTravel0() {
    RevTravel(false);
  }

  private void ForTravel0() {
    ForTravel(false);
  }

  private void RevTravel1() {
    RevTravel(true);
  }

  private void ForTravel1() {
    ForTravel(true);
  }

  //strictly long test functions

  private boolean For0StrictShort() {
    //test??
    boolean x = !stateLong();
    ForTravel0();
    RevTravel1();
    x &= stateLong();//strict short
    ForTravel1();
    RevTravel0();//back at start
    return x;
  }

  private boolean Rev0StrictShort() {
    RevTravel0();
    //test??
    boolean x = For0StrictShort();
    ForTravel0();
    return x;
  }

  private boolean For1StrictLong() {
    //test??
    boolean x = stateLong();
    ForTravel1();
    RevTravel0();
    x &= !stateLong();//strict long
    ForTravel0();
    RevTravel1();//back at start
    return x;
  }

  private boolean Rev1StrictLong() {
    RevTravel1();
    //test??
    boolean x = For1StrictLong();
    ForTravel1();
    return x;
  }

  //user data provider functions

  private int buffer;
  private int cnt;

  private boolean absorb() {
    cnt--;
    boolean t = (buffer & 1) == 1;
    buffer >>= 1;
    return t;
  }

  private void emit(boolean val) {
    cnt--;
    buffer <<= 1;
    buffer |= val?1:0;
  }

  //state machine progression functions

  private void decompressOne() {
    if(Rev0StrictShort()) { //fails back 0 strict long
      RevTravel0();
      if(For1StrictLong()) emit(false);//0 (B)
      //default 0 route (E(SS))
      //back 0 strict long force causes everything else to move
      //to the following else.
    } else {
      //NEW
      RevTravel1();
      ForTravel0();
      RevTravel1();
      if(For1StrictLong() && For0StrictShort()) {
        ForTravel1();
        RevTravel0();
        return;//1 (F)
      }
      ForTravel1();
      RevTravel0();
      ForTravel1();
      if(Rev1StrictLong()) {
        RevTravel1();
        if(For0StrictShort()) emit(true);//1 (A)
        //1 forced 0 back strict long (C)
      } else {
        RevTravel0();
        //default 0 route (D)
      }
    }
  }

  private void compressOne() {
    if(For1StrictLong()) { 
      if(For0StrictShort()) {
        if(absorb()) ForTravel1();//1 (A)
        else ForTravel0();//0 (B)
      } else {
        ForTravel1();//go 1 route to force 0 back strict long (C)
      }
    } else {
      ForTravel0();//go 0 route to default 0 route (D + E(SS))
      RevTravel1();
      if(For1StrictLong() && !For0StrictShort()) {
        ForTravel1();//0 (D)
        return;
      }
      //NEW
      if(For1StrictLong() && For0StrictShort()) {
        ForTravel1();
        RevTravel0();
        ForTravel1();//1 (F)
      }
      ForTravel1();//0 (E(SS))
    }
  } 

  //blat - do an int!

  public void compress(int x) {
    buffer = x;
    cnt = 32;
    while(cnt > 0) {
      compressOne();
    }
  }

  public int decompress() {
    cnt = 32;
    while(cnt > 0) {
      decompressOne();
    }
    return buffer;
  }
}