An interesting (incomplete) algorithm for the ST2 transform: Schindler-Transform

stx2.c

// A sort based transform, like BWT
// From
// https://encode.ru/threads/1317-Schindler-Transform-(STX)
// See also:
// http://www.compressconsult.com/st/
// https://ieeexplore.ieee.org/document/1607307

uint Forward_ST2( byte* inpbuf, byte* outbuf, uint inplen ) {
  uint i,c,p,q;

  memset( o2, 0, sizeof(o2) );

  p = inpbuf[inplen-2];
  q = inpbuf[inplen-1]; 
  for( i=0; i<inplen; i++ ) {
    c = inpbuf[i];
    o2[1+p+(q<<8)]++;
    p = q; q = c;
  }

  for( i=0,c=2; i<CNUM*CNUM; i++ ) o2[i]=c, c+=o2[i+1];

  p = inpbuf[inplen-2]; outbuf[0] = p;
  q = inpbuf[inplen-1]; outbuf[1] = q;
  for( i=0; i<inplen; i++ ) {
    c = outbuf[ o2[p+(q<<8)]++ ] = inpbuf[i]; 
    p = q; q = c; 
  }

  return inplen+2;
}

uint Inverse_ST2( byte* inpbuf, byte* outbuf, uint inplen ) {
  uint i,j,c,p,q;

  memset( o1, 0, sizeof(o2) );
  memset( o2, 0, sizeof(o2) );

  for( i=2; i<inplen; i++ ) c=inpbuf[i], o1[1+c]++; // symbol freqs

  for( i=0,c=2; i<CNUM; i++ ) o1[i]=c, c+=o1[i+1]; o1[CNUM]=c; // now offsets

  for( j=0; j<CNUM; j++ ) { // symbol loop
    q = j;
    for( i=o1[j]; i<o1[j+1]; i++ ) {
      c = inpbuf[i]<<8;
      o2[1+q+c]++; // byte freqs
    }
  }
  for( i=0,c=2; i<CNUM*CNUM; i++ ) o2[i]=c, c+=o2[i+1];

  p = inpbuf[0]; 
  q = inpbuf[1]; 
  for( i=0; i<inplen-2; i++ ) {
    c = outbuf[i] = inpbuf[ o2[p+(q<<8)]++ ];
    p = q; q = c; 
  }

  return inplen-2;
}