<?php

/* RLEINC compressor version 2.3.1
 * Copyright (C) 2013 Joel Yliluoma - http://iki.fi/bisqwit/
 * License: MIT
 */

function RLEINCcompress($data)
{
  /*
        ; LIT: Input byte c = 0..3F:
        ;        Put next c+0x01 bytes verbatim, except BACKWARDS
        ; END: Input byte c = 40:
        ;        End stream
        ; SEQ: Input byte c = 41..7F:
        ;        Read byte b
        ;        Put b, (c-0x3F) times; add 1 to b after each iteration
        ; DBL: Input byte c = 80..9F:
        ;        Read byte b1
        ;        Read byte b2
        ;        Put b1, (c-0x7D) times; swap b2 and b1 after each iteration
        ; RUN: Input byte c = A0..FF:
        ;        Read byte b
        ;        Put b, (0x101-c) times
  */

  $result = '';
  $a = 0;
  $b = strlen($data);
  
  $runs = Array();
  $dbls = Array();
  $seqs = Array();

  /* Find where are all the runs, and where are all the successive sequences */

  for($a=0; $a<$b; ) // Find runs of 1 byte
  {
    $c = ord($data[$a]);
    for($runlen = 1; $a+$runlen < $b && $c == ord($data[$a+$runlen]); ++$runlen);
    if($runlen > 0x61) $runlen = 0x61;
    if($runlen >= 3) $runs[$a] = $runlen;
    $a += $runlen;
  }

  for($a=0; $a+1<$b; ) // Find runs of 2 bytes
  {
    $c1 = ord($data[$a]);
    $c2 = ord($data[$a+1]);
    if($c1 == $c2) { ++$a; continue; }

    for($runlen = 2; $a+$runlen < $b && $c1 == ord($data[$a+$runlen]); ++$runlen)
    {
      $tmp = $c1; $c1 = $c2; $c2 = $tmp;
    }

    if($runlen > 0x22) $runlen = 0x22;
    if($runlen >= 5) $dbls[$a] = $runlen;
    $a += $runlen;
  }

  for($a=0; $a<$b; ) // Find runs of successive sequence
  {
    $c = ord($data[$a]);
    for($seqlen = 1; $a+$seqlen < $b && (++$c & 0xFF) == ord($data[$a+$seqlen]); ++$seqlen);
    if($seqlen >= 3) $seqs[$a] = $seqlen;
    $a += $seqlen;
  }

  /* Synthesize the result */
  for($a=0; $a<$b; )
  {
    // Where is the next run or the next sequence?
    $ra=$a+9999; foreach($runs as $ra => $rl) { if($ra >= $a) break; }
    $sa=$a+9999; foreach($seqs as $sa => $sl) { if($sa >= $a) break; }
    $da=$a+9999; foreach($dbls as $da => $dl) { if($da >= $a) break; }

    $time_until_run = $ra-$a; if($time_until_run<0) $time_until_run=9999;
    $time_until_seq = $sa-$a; if($time_until_seq<0) $time_until_seq=9999;
    $time_until_dbl = $da-$a; if($time_until_dbl<0) $time_until_dbl=9999;
    $time_until = min($b-$a, $time_until_run, $time_until_seq, $time_until_dbl, 0x40);

    if($time_until > 0)
    {
      // Do literal sequence. Store data in reverse.
      $result .= chr($time_until - 1);
      for($c=0; $c<$time_until; ++$c)
        $result .= $data[$a + $time_until-($c+1) ];
      #print "@$a: Literal $time_until\n";
      $a += $time_until;
      continue;
    }

    // Do we have a sequence?
    if($time_until_seq == 0)
    {
      // Figure out its length
      $length = min(0x40, $sl);
      if($time_until_run < $length) $length = max(3, $time_until_run);
      if($time_until_dbl < $length) $length = max(3, $time_until_dbl);
      $result .= chr(0x40+$length-1);
      $result .= $data[$a];
      #printf("@$a: Sequence %02X, length=%d (%02X)\n", ord($data[$a]), $length, 0x40+$length-1);
      $a += $length;
    }
    // Do we have a two-byte run?
    elseif($time_until_dbl == 0)
    {
      // Figure out its length
      $length = min(0x23, $dl);
      if($time_until_seq < $length) $length = max(3, $time_until_seq);
      if($time_until_run < $length) $length = max(3, $time_until_run);
      #printf("@$a: Dbl-Run %02X & %02X, length=%d (%02X)\n", ord($data[$a]), ord($data[$a+1]), $length, 0x80+($length-4));
      $result .= chr(0x80 + ($length-3));
      $result .= $data[$a];
      $result .= $data[$a+1];
      $a += $length;
    }
    else // We have a run
    {
      if($time_until_run != 0) print "ERROR in RLEINCcompress()\n";
      // Figure out its length
      $length = min(0x61, $rl);
      if($time_until_seq < $length) $length = max(3, $time_until_seq);
      if($time_until_dbl < $length) $length = max(3, $time_until_dbl);
      #printf("@$a: Run %02X, length=%d (%02X)\n", ord($data[$a]), $length, 0x101-$length);
      $result .= chr(0x101-$length);
      $result .= $data[$a];
      $a += $length;
    }
  }
  $result .= "\x40"; // end marker
  #printf("Result length %d\n", strlen($result));
  return $result;
}