lz77c.js

// a toy lz77 compressor that outputs printable ascii, by @ryancdotorg

var compress = function(I) {                                                                                                                                   
  var p = 0, // position in input
      o = "", // compressed output string
      D, D_MAX = 479, // distance
      L, L_MAX = 19, // length
      match; // best match for current position

  // encode a (distance,length) tuple
  var encodeDL = function(d,l) {
    o = String.fromCharCode(31+(d%5)*19+l, 32+d/5) + o;
  };

  // encode a string literal (distance zero)
  var encodeSL = function(s) {
    var n = s.length;
    o = s.split("").reverse().join("") + String.fromCharCode(31+n, 32) + o;
  };

  while (p < I.length) {
    match = [0,0]; // reset the best match
    // look at least one back, but not before start of input or more than D_MAX
    for (D = 1; D <= D_MAX && D <= p; ++D) {
      // match should be longer than current best, but no more than L_MAX
      for (L = match[1]+1; L <= L_MAX && L <= I.length - p; ++L) {
        // check of distance, length pair matches from our current position
        if (I.substr(p-D, L) == I.substr(p, L)) {
          match = [D,L]; // update best match
        } else {
          break; // longer substrings aren't going to match either
        }
      }
    }

    // was any match found at all?
    if (match[1]) {
      encodeDL.apply(null, match);
      L = match[1];
    } else {
      L = Math.min(L_MAX, I.length - p);
      encodeSL(I.substr(p, L));
    }
    // advance position by however much we just encoded
    p += L;
  }
  return o;
};

// decompressor
// (r,t,a,h=r.length,o=t=>a=r.charCodeAt(--h)-32,e="")=>{while(h)for(t=5*o()+o()/19|0,a=a%19+1;a--;)e+=t?e.substr(-t,1):r.charAt(--h);return e}