comun/programs/comunpress.cmn

# Simple compression library implementing the shitpress streaming algorithm,
# which I first wrote in C. This is also usable as a standalone utility. For
# use as a library push -1 onto stack before inluding this file, which will stop
# running the standalone code.
#
# PRINCIPLE: the algorithm is very simple, it can compress sequences of length
# 3 to 6 to just 2 bytes, by pushing a reference to that sequence occuring in
# the output history recently (latest 63 bytes).
#
# NOTE: this is compatible with the original C shitpress, though the compressed
# output may differ due to slight differences that were made here -- both
# outputs are valid shitpress compressed format.
#
# by drummyfish released under CC0 1.0, public domain

~_comunpressState       # 0: comp, 1: , 2: decomp , 3: decomp_marker
~_comunpressHistory:76  # when compressing first 6 are prebuffer
                        # -1 means EOF, -2 means empty
~_comunpressHelper:0
~_comunpressHelper2:0

_COMUNPRESS_MARKER: +xe0 . # special marker value, statistically unlikely

# Initializes compression (pass 0) or decompression (pass 1).
comunpressInit:
  $0 0 = -2 0 ?? >< # what to prefill history with? -2 for compression, else 0

  1 |< $:_comunpressState

  $_comunpressHistory>_comunpressHelper

  76 @' # fill history with 0s
    >< $0 $:_comunpressHelper ><
    $>_comunpressHelper
    --
  .
  ^ ^
.

_comunpressHistoryPush:
  $_comunpressHistory>_comunpressHelper

  75 @'
    ><
    $_comunpressHelper
    ><
    $:_comunpressHelper
    $>_comunpressHelper
    ><

    $1 0 << ?
      !@
    .

    --
  .
  ^ ^
.

# Feeds next byte to the (de)compression algorithm. Feeding a byte with value
# -1 means end of input. Returns N (possibly zero) output bytes in format -1,
# byteN, ..., byte2, byte1.
comunpressFeed:
  -1 >< # terminating -1

  $_comunpressState 1 |> 0 = ?
    # ------- COMPRESSING -------

    $0 -1 = ?
      ^
      # EOF: just output the rest of buffer (without compressing, KISS)

      $_comunpressHistory>_comunpressHelper

      5 @'
        $_comunpressHelper

        $0 0 << ?
          ^
        ;
          $0 _COMUNPRESS_MARKER = ?
            ^
            +xff ><
            _COMUNPRESS_MARKER
          .

          ><
        .

        $>_comunpressHelper

        --
      .
      ^
    ;
      # non-EOF:

      _comunpressHistoryPush

      $_comunpressHistory>_comunpressHelper
      5 $+_comunpressHelper

      $_comunpressHelper 0 >>= ? # ignore -1 and -2
        # stack: -1

        # now search for matches in history
        -1 # match_p (position)

        4 @' # for match_l (length) := 3 downto 0
          --
          $0 3 + # len (6 downto 3)

          $_comunpressHistory>_comunpressHelper
          6 $+_comunpressHelper

          0 @@ # for i := 0
            $0 63 >= ? # up to 63
              !@
            .

            # stack: -1 match_p match_l len i

            $0 $:4 # match_p := i

            $1 @' # for j := len - 1 downto 0
              --

              # stack: -1 match_p match_l len i j

              $_comunpressHistory>_comunpressHelper2
              6 $3 - $1 + $+_comunpressHelper2
              $_comunpressHelper2

              $_comunpressHelper>_comunpressHelper2
              $1 $+_comunpressHelper2
              $_comunpressHelper2

              != ?
                -1 $:5 # match_p := -1
                !@
              .
            .
            ^ # j

            $3 -1 != ? # match found?
              $3 63 = $3 3 = & ? # disallowed, would result in 0xff, reserved
                -1 $:4
              ;
                !@
              .
            .

            $>_comunpressHelper
            ++
          .
          ^ # i
          ^ # len

          $1 -1 != ? # match found?
            !@
          .
        .

        $1 0 >>= ? # match found?
          $0 3 +
          @'
            0 _comunpressHistoryPush
            --
          .
          ^

          $_comunpressHistory>_comunpressHelper

          $0 3 +
          @'
            -2 $:_comunpressHelper
            $>_comunpressHelper
            --
          .
          ^

          # now shift the pre-buffer 1 left:
          $0>_comunpressHelper
          $_comunpressHistory>0

          $>0 $:1' $>0 $:1' $>0 $:1' $>0 $:1' $>0 $:1 -2

          $_comunpressHelper>0

          # encode the reference for output:
          6 |< |                 # (match_p << 6) | match_l
          _COMUNPRESS_MARKER
        ;
          # no match was found, we'll just output one byte

          ^ ^ # match_l, match_p

          $_comunpressHistory>_comunpressHelper
          5 $+_comunpressHelper
          $_comunpressHelper

          $0 0 << ?
            ^
          ;
            $0 _COMUNPRESS_MARKER = ?
              +xff
              ><
            .
          .
        .
      .
    .
  ; # =============================
    # ------- DECOMPRESSING -------

    $_comunpressState 3 = ?
      # state: decompressing marker

      $0 +xff = ?
        # encoded marker, output it
        ^
        _COMUNPRESS_MARKER
      ;
        # sequence reference

        $0 +x3f &  # position
        $_comunpressHistory>_comunpressHelper
        $+_comunpressHelper
        
        6 |> 3 +   # length

        @'
          --
          $0
          $_comunpressHelper $:2
          $>_comunpressHelper
        .
        ^
      .

      2 $:_comunpressState
    ;
      # state: decompressing normal

      $0 _COMUNPRESS_MARKER = ?
        ^ # output nothing
        3 $:_comunpressState
      .

      # else do nothing, just leave the byte on top of stack
    .

    # push all output characters to history

    $0>_comunpressHelper

    @@
      $_comunpressHelper -1 = ?
        !@
      ;
        $<_comunpressHelper
      .
    .

    -1

    @@
      $>_comunpressHelper
      $_comunpressHelper

      $0 -1 = ?
        ^ !@
      .
    .

    @@
      $0 -1 = ?
        ^ !@
      .

      _comunpressHistoryPush
    . 
  .
.

# if using as pure library you may happily remove everything below

_comunpressStandalone:
  0 > ?
    "-" = ?
      "x" = ?
        1
      ;
        0
      .
    ;
      0
    .
  ;
    0
  .

  comunpressInit

  1 @ # stream loop
    <-

    <? !! ? # if EOF, feed -1
      ^ -1
    .

    comunpressFeed

    @@ # print all output chars to stdout
      $0 -1 = ?
        ^ !@
      .

      ->
    .

    <?
  .
.

$0 -1 != ?
  _comunpressStandalone
.