Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Deflate.js

By: a guest on Aug 2nd, 2011  |  syntax: JavaScript  |  size: 14.94 KB  |  views: 302  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. /*Copyright (c) 2008 notmasteryet
  2. Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
  3. The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
  4. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.*/
  5.  
  6. var staticCodes,
  7.         staticDistances;
  8. function Base64Reader(base64) {
  9.         "use strict";
  10.         this.position = 0;
  11.         this.base64 = base64;
  12.         this.bits = 0;
  13.         this.bitsLength = 0;
  14.         this.readByte = function () {
  15.                 var tailBits, ch, base64alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=", index, code;
  16.                 if (this.bitsLength === 0) {
  17.                         tailBits = 0;
  18.                         while (this.position < this.base64.length && this.bitsLength < 24) {
  19.                                 ch = this.base64.charAt(this.position);
  20.                                 ++this.position;
  21.                                 if (ch > " ") {
  22.                                         index = base64alphabet.indexOf(ch);
  23.                                         if (index < 0) {
  24.                                                 throw "Invalid character";
  25.                                         }
  26.                                         if (index < 64) {
  27.                                                 if (tailBits > 0) {
  28.                                                         throw "Invalid encoding (padding)";
  29.                                                 }
  30.                                                 this.bits = this.bits << 6 | index;
  31.                                         } else {
  32.                                                 if (this.bitsLength < 8) {
  33.                                                         throw "Invalid encoding (extra)";
  34.                                                 }
  35.                                                 this.bits <<= 6;
  36.                                                 tailBits += 6;
  37.                                         }
  38.                                         this.bitsLength += 6;
  39.                                 }
  40.                         }
  41.                         if (this.position >= this.base64.length) {
  42.                                 if (this.bitsLength === 0) {
  43.                                         return -1;
  44.                                 } else {
  45.                                         if (this.bitsLength < 24) {
  46.                                                 throw "Invalid encoding (end)";
  47.                                         }
  48.                                 }
  49.                         }
  50.                         if (tailBits === 6) {
  51.                                 tailBits = 8;
  52.                         } else {
  53.                                 if (tailBits === 12) {
  54.                                         tailBits = 16;
  55.                                 }
  56.                         }
  57.                         this.bits = this.bits >> tailBits;
  58.                         this.bitsLength -= tailBits;
  59.                 }
  60.                 this.bitsLength -= 8;
  61.                 code = this.bits >> this.bitsLength & 255;
  62.                 return code;
  63.         };
  64. }
  65.  
  66. function BitReader(reader) {
  67.         "use strict";
  68.         this.bitsLength = 0;
  69.         this.bits = 0;
  70.         this.reader = reader;
  71.         this.readBit = function () {
  72.                 var nextByte, bit;
  73.                 if (this.bitsLength === 0) {
  74.                         nextByte = this.reader.readByte();
  75.                         if (nextByte < 0) {
  76.                                 throw new Error("Unexpected end of stream");
  77.                         }
  78.                         this.bits = nextByte;
  79.                         this.bitsLength = 8;
  80.                 }
  81.                 bit = (this.bits & 1) !== 0;
  82.                 this.bits >>= 1;
  83.                 --this.bitsLength;
  84.                 return bit;
  85.         };
  86.         this.align = function () {
  87.                 this.bitsLength = 0;
  88.         };
  89.         this.readLSB = function (length) {
  90.                 var i, data = 0;
  91.                 for (i = 0; i < length; ++i) {
  92.                         if (this.readBit()) {
  93.                                 data |= 1 << i;
  94.                         }
  95.                 }
  96.                 return data;
  97.         };
  98.         this.readMSB = function (length) {
  99.                 var i, data = 0;
  100.                 for (i = 0; i < length; ++i) {
  101.                         if (this.readBit()) {
  102.                                 data = data << 1 | 1;
  103.                         } else {
  104.                                 data <<= 1;
  105.                         }
  106.                 }
  107.                 return data;
  108.         };
  109. }
  110.  
  111. function TextReader(translator) {
  112.         "use strict";
  113.         this.translator = translator;
  114.         this.unreads = new Array(0);
  115.         this.readChar = function () {
  116.                 if (this.unreads.length > 0) {
  117.                         return this.unreads.pop();
  118.                 } else {
  119.                         return translator.readChar();
  120.                 }
  121.         };
  122.         this.unreadChar = function (ch) {
  123.                 this.unreads.push(ch);
  124.         };
  125.         this.readToEnd = function () {
  126.                 var ch = this.readChar(),
  127.                         s = "",
  128.                         slarge = "";
  129.                 while (ch !== null) {
  130.                         s += ch;
  131.                         if (s.length > 1E3) {
  132.                                 slarge += s;
  133.                                 s = "";
  134.                         }
  135.                         ch = this.readChar();
  136.                 }
  137.                 return slarge + s;
  138.         };
  139.         this.readLine = function () {
  140.                 var ch = this.readChar(),
  141.                         s = "";
  142.                 if (ch === null) {
  143.                         return null;
  144.                 }
  145.                 while (ch !== "\r" && ch !== "\n") {
  146.                         s += ch;
  147.                         ch = this.readChar();
  148.                         if (ch === null) {
  149.                                 return s;
  150.                         }
  151.                 }
  152.                 if (ch === "\r") {
  153.                         ch = this.readChar();
  154.                         if (ch !== null && ch !== "\n") {
  155.                                 this.unreadChar(ch);
  156.                         }
  157.                 }
  158.                 return s;
  159.         };
  160. }
  161.  
  162. function DefaultTranslator(reader) {
  163.         "use strict";
  164.         this.reader = reader;
  165.         this.readChar = function () {
  166.                 var code = reader.readByte();
  167.                 return code < 0 ? null : String.fromCharCode(code);
  168.         };
  169. }
  170.  
  171. function UnicodeTranslator(reader) {
  172.         "use strict";
  173.         this.reader = reader;
  174.         this.bomState = 0;
  175.         this.readChar = function () {
  176.                 var b1 = reader.readByte(), b2, code;
  177.                 if (b1 < 0) {
  178.                         return null;
  179.                 }
  180.                 b2 = reader.readByte();
  181.                 if (b2 < 0) {
  182.                         throw "Incomplete unicode character";
  183.                 }
  184.                 if (this.bomState === 0 && b1 + b2 === 509) {
  185.                         this.bomState = b2 === 254 ? 1 : 2;
  186.                         b1 = reader.readByte();
  187.                         if (b1 < 0) {
  188.                                 return null;
  189.                         }
  190.                         b2 = reader.readByte();
  191.                         if (b2 < 0) {
  192.                                 throw "Incomplete unicode character";
  193.                         }
  194.                 } else {
  195.                         this.bomState = 1;
  196.                 }
  197.                 code = this.bomState === 1 ? b2 << 8 | b1 : b1 << 8 | b2;
  198.                 return String.fromCharCode(code);
  199.         };
  200. }
  201.  
  202. function Utf8Translator(reader) {
  203.         "use strict";
  204.         this.reader = reader;
  205.         this.waitBom = true;
  206.         this.pendingChar = null;
  207.         this.readChar = function () {
  208.                 var ch = null, b1, currentPrefix, validBits, mask, i, code, bi, v, w1, w2;
  209.                 do {
  210.                         if (this.pendingChar !== null) {
  211.                                 ch = this.pendingChar;
  212.                                 this.pendingChar = null;
  213.                         } else {
  214.                                 b1 = this.reader.readByte();
  215.                                 if (b1 < 0) {
  216.                                         return null;
  217.                                 }
  218.                                 if ((b1 & 128) === 0) {
  219.                                         ch = String.fromCharCode(b1);
  220.                                 } else {
  221.                                         currentPrefix = 192;
  222.                                         validBits = 5;
  223.                                         do {
  224.                                                 mask = currentPrefix >> 1 | 128;
  225.                                                 if ((b1 & mask) === currentPrefix) {
  226.                                                         break;
  227.                                                 }
  228.                                                 currentPrefix = currentPrefix >> 1 | 128;
  229.                                                 --validBits;
  230.                                         } while (validBits >= 0);
  231.                                         if (validBits > 0) {
  232.                                                 code = b1 & (1 << validBits) - 1;
  233.                                                 for (i = 5; i >= validBits; --i) {
  234.                                                         bi = this.reader.readByte();
  235.                                                         if ((bi & 192) !== 128) {
  236.                                                                 throw "Invalid sequence character";
  237.                                                         }
  238.                                                         code = code << 6 | bi & 63;
  239.                                                 }
  240.                                                 if (code <= 65535) {
  241.                                                         if (code === 65279 && this.waitBom) {
  242.                                                                 ch = null;
  243.                                                         } else {
  244.                                                                 ch = String.fromCharCode(code);
  245.                                                         }
  246.                                                 } else {
  247.                                                         v = code - 65536;
  248.                                                         w1 = 55296 | v >> 10 & 1023;
  249.                                                         w2 = 56320 | v & 1023;
  250.                                                         this.pendingChar = String.fromCharCode(w2);
  251.                                                         ch = String.fromCharCode(w1);
  252.                                                 }
  253.                                         } else {
  254.                                                 throw "Invalid character";
  255.                                         }
  256.                                 }
  257.                         }
  258.                         this.waitBom = false;
  259.                 } while (ch === null);
  260.                 return ch;
  261.         };
  262. }
  263.  
  264. function buildCodes(lengths) {
  265.         "use strict";
  266.         var i,
  267.                 maxBits = lengths[0],
  268.                 bitLengthsCount = [],
  269.                 bits,
  270.                 code = 0,
  271.                 nextCode = [],
  272.                 codes = new Array(lengths.length),
  273.                 n,
  274.                 len;
  275.         for (i = 1; i < lengths.length; i++) {
  276.                 if (maxBits < lengths[i]) {
  277.                         maxBits = lengths[i];
  278.                 }
  279.         }
  280.         for (i = 0; i <= maxBits; i++) {
  281.                 bitLengthsCount[i] = 0;
  282.         }
  283.         for (i = 0; i < lengths.length; i++) {
  284.                 ++bitLengthsCount[lengths[i]];
  285.         }
  286.         bitLengthsCount[0] = 0;
  287.         for (bits = 1; bits <= maxBits; bits++) {
  288.                 code = code + bitLengthsCount[bits - 1] << 1;
  289.                 nextCode[bits] = code;
  290.         }
  291.         for (n = 0; n < codes.length; n++) {
  292.                 len = lengths[n];
  293.                 if (len !== 0) {
  294.                         codes[n] = nextCode[len];
  295.                         nextCode[len]++;
  296.                 }
  297.         }
  298.         return codes;
  299. }
  300.  
  301. function buildTreeBranch(codes, prefix, prefixLength) {
  302.         "use strict";
  303.         if (codes.length === 0) {
  304.                 return null;
  305.         }
  306.         var branch = {},
  307.                 i,
  308.                 nextBit,
  309.                 ones = new Array(0),
  310.                 zeros = new Array(0);
  311.         branch.isLeaf = false;
  312.         for (i = 0; i < codes.length; ++i) {
  313.                 if (codes[i].length === prefixLength && codes[i].bits === prefix) {
  314.                         branch.isLeaf = true;
  315.                         branch.index = codes[i].index;
  316.                         break;
  317.                 } else {
  318.                         nextBit = (codes[i].bits >> codes[i].length - prefixLength - 1 & 1) > 0;
  319.                         if (nextBit) {
  320.                                 ones.push(codes[i]);
  321.                         } else {
  322.                                 zeros.push(codes[i]);
  323.                         }
  324.                 }
  325.         }
  326.         if (!branch.isLeaf) {
  327.                 branch.zero = buildTreeBranch(zeros, prefix << 1, prefixLength + 1);
  328.                 branch.one = buildTreeBranch(ones, prefix << 1 | 1, prefixLength + 1);
  329.         }
  330.         return branch;
  331. }
  332.  
  333. function buildTree(codes, lengths) {
  334.         "use strict";
  335.         var i,
  336.                 code,
  337.                 nonEmptyCodes = new Array(0);
  338.         for (i = 0; i < codes.length; ++i) {
  339.                 if (lengths[i] > 0) {
  340.                         code = {};
  341.                         code.bits = codes[i];
  342.                         code.length = lengths[i];
  343.                         code.index = i;
  344.                         nonEmptyCodes.push(code);
  345.                 }
  346.         }
  347.         return buildTreeBranch(nonEmptyCodes, 0, 0);
  348. }
  349.  
  350. function initializeStaticTrees() {
  351.         "use strict";
  352.         var i,
  353.                 codes = new Array(288),
  354.                 codesLengths = new Array(288),
  355.                 distances = new Array(32),
  356.                 distancesLengths = new Array(32);
  357.         for (i = 0; i <= 143; i++) {
  358.                 codes[i] = 48 + i;
  359.                 codesLengths[i] = 8;
  360.         }
  361.         for (i = 144; i <= 255; i++) {
  362.                 codes[i] = 400 + i - 144;
  363.                 codesLengths[i] = 9;
  364.         }
  365.         for (i = 256; i <= 279; i++) {
  366.                 codes[i] = 0 + i - 256;
  367.                 codesLengths[i] = 7;
  368.         }
  369.         for (i = 280; i <= 287; i++) {
  370.                 codes[i] = 192 + i - 280;
  371.                 codesLengths[i] = 8;
  372.         }
  373.         staticCodes = buildTree(codes, codesLengths);
  374.         for (i = 0; i <= 31; i++) {
  375.                 distances[i] = i;
  376.                 distancesLengths[i] = 5;
  377.         }
  378.         staticDistances = buildTree(distances, distancesLengths);
  379. }
  380.  
  381. function readDynamicTrees(bitReader) {
  382.         "use strict";
  383.         var hlit = bitReader.readLSB(5) + 257,
  384.                 hdist = bitReader.readLSB(5) + 1,
  385.                 hclen = bitReader.readLSB(4) + 4,
  386.                 i,
  387.                 clen = new Array(19),
  388.                 clenMap = [16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15],
  389.                 clenCodes,
  390.                 clenTree,
  391.                 lengthsSequence,
  392.                 q,
  393.                 p,
  394.                 code,
  395.                 repeat,
  396.                 codesLengths,
  397.                 codes,
  398.                 distancesLengths,
  399.                 distances,
  400.                 result = {};
  401.         for (i = 0; i < clen.length; ++i) {
  402.                 clen[i] = 0;
  403.         }
  404.         for (i = 0; i < hclen; ++i) {
  405.                 clen[clenMap[i]] = bitReader.readLSB(3);
  406.         }
  407.         clenCodes = buildCodes(clen);
  408.         clenTree = buildTree(clenCodes, clen);
  409.         lengthsSequence = new Array(0);
  410.         while (lengthsSequence.length < hlit + hdist) {
  411.                 p = clenTree;
  412.                 while (!p.isLeaf) {
  413.                         p = bitReader.readBit() ? p.one : p.zero;
  414.                 }
  415.                 code = p.index;
  416.                 if (code <= 15) {
  417.                         lengthsSequence.push(code);
  418.                 } else {
  419.                         if (code === 16) {
  420.                                 repeat = bitReader.readLSB(2) + 3;
  421.                                 for (q = 0; q < repeat; ++q) {
  422.                                         lengthsSequence.push(lengthsSequence[lengthsSequence.length - 1]);
  423.                                 }
  424.                         } else {
  425.                                 if (code === 17) {
  426.                                         repeat = bitReader.readLSB(3) + 3;
  427.                                         for (q = 0; q < repeat; ++q) {
  428.                                                 lengthsSequence.push(0);
  429.                                         }
  430.                                 } else {
  431.                                         if (code === 18) {
  432.                                                 repeat = bitReader.readLSB(7) + 11;
  433.                                                 for (q = 0; q < repeat; ++q) {
  434.                                                         lengthsSequence.push(0);
  435.                                                 }
  436.                                         }
  437.                                 }
  438.                         }
  439.                 }
  440.         }
  441.         codesLengths = lengthsSequence.slice(0, hlit);
  442.         codes = buildCodes(codesLengths);
  443.         distancesLengths = lengthsSequence.slice(hlit, hlit + hdist);
  444.         distances = buildCodes(distancesLengths);
  445.         result.codesTree = buildTree(codes, codesLengths);
  446.         result.distancesTree = buildTree(distances, distancesLengths);
  447.         return result;
  448. }
  449.  
  450. function Inflator(reader) {
  451.         "use strict";
  452.         this.reader = reader;
  453.         this.bitReader = new BitReader(reader);
  454.         this.buffer = new Array(0);
  455.         this.bufferPosition = 0;
  456.         this.state = 0;
  457.         this.blockFinal = false;
  458.         this.readByte = function () {
  459.                 var item, j, i, symbol, shift;
  460.                 while (this.bufferPosition >= this.buffer.length) {
  461.                         item = this.decodeItem();
  462.                         if (item === null) {
  463.                                 return -1;
  464.                         }
  465.                         switch (item.itemType) {
  466.                         case 0:
  467.                                 this.buffer = this.buffer.concat(item.array);
  468.                                 break;
  469.                         case 2:
  470.                                 this.buffer.push(item.symbol);
  471.                                 break;
  472.                         case 3:
  473.                                 j = this.buffer.length - item.distance;
  474.                                 for (i = 0; i < item.length; i++) {
  475.                                         this.buffer.push(this.buffer[j++]);
  476.                                 }
  477.                                 break;
  478.                         }
  479.                 }
  480.                 symbol = this.buffer[this.bufferPosition++];
  481.                 if (this.bufferPosition > 49152) {
  482.                         shift = this.buffer.length - 32768;
  483.                         if (shift > this.bufferPosition) {
  484.                                 shift = this.bufferPosition;
  485.                         }
  486.                         this.buffer.splice(0, shift);
  487.                         this.bufferPosition -= shift;
  488.                 }
  489.                 return symbol;
  490.         };
  491.         this.decodeItem = function () {
  492.                 if (this.state === 2) {
  493.                         return null;
  494.                 }
  495.                 var blockType, len, nlen, item = {}, i, nextByte, dynamicTrees, p, lengthCode, length, encodedLengthStart = [3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258], encodedLengthAdditionalBits = [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0], distanceCode, distance, encodedDistanceStart = [1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577], encodedDistanceAdditionalBits = [0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13];
  496.                 if (this.state === 0) {
  497.                         this.blockFinal = this.bitReader.readBit();
  498.                         blockType = this.bitReader.readLSB(2);
  499.                         switch (blockType) {
  500.                         case 0:
  501.                                 this.bitReader.align();
  502.                                 len = this.bitReader.readLSB(16);
  503.                                 nlen = this.bitReader.readLSB(16);
  504.                                 if ((len & ~nlen) !== len) {
  505.                                         throw "Invalid block type 0 length";
  506.                                 }
  507.                                 item = {};
  508.                                 item.itemType = 0;
  509.                                 item.array = [];
  510.                                 for (i = 0; i < len; ++i) {
  511.                                         nextByte = this.reader.readByte();
  512.                                         if (nextByte < 0) {
  513.                                                 throw "Uncomplete block";
  514.                                         }
  515.                                         item.array[i] = nextByte;
  516.                                 }
  517.                                 if (this.blockFinal) {
  518.                                         this.state = 2;
  519.                                 }
  520.                                 return item;
  521.                         case 1:
  522.                                 this.codesTree = staticCodes;
  523.                                 this.distancesTree = staticDistances;
  524.                                 this.state = 1;
  525.                                 break;
  526.                         case 2:
  527.                                 dynamicTrees = readDynamicTrees(this.bitReader);
  528.                                 this.codesTree = dynamicTrees.codesTree;
  529.                                 this.distancesTree = dynamicTrees.distancesTree;
  530.                                 this.state = 1;
  531.                                 break;
  532.                         default:
  533.                                 throw new Error("Invalid block type (3)");
  534.                         }
  535.                 }
  536.                 item = {};
  537.                 p = this.codesTree;
  538.                 while (!p.isLeaf) {
  539.                         p = this.bitReader.readBit() ? p.one : p.zero;
  540.                 }
  541.                 if (p.index < 256) {
  542.                         item.itemType = 2;
  543.                         item.symbol = p.index;
  544.                 } else {
  545.                         if (p.index > 256) {
  546.                                 lengthCode = p.index;
  547.                                 if (lengthCode > 285) {
  548.                                         throw new Error("Invalid length code");
  549.                                 }
  550.                                 length = encodedLengthStart[lengthCode - 257];
  551.                                 if (encodedLengthAdditionalBits[lengthCode - 257] > 0) {
  552.                                         length += this.bitReader.readLSB(encodedLengthAdditionalBits[lengthCode - 257]);
  553.                                 }
  554.                                 p = this.distancesTree;
  555.                                 while (!p.isLeaf) {
  556.                                         p = this.bitReader.readBit() ? p.one : p.zero;
  557.                                 }
  558.                                 distanceCode = p.index;
  559.                                 distance = encodedDistanceStart[distanceCode];
  560.                                 if (encodedDistanceAdditionalBits[distanceCode] > 0) {
  561.                                         distance += this.bitReader.readLSB(encodedDistanceAdditionalBits[distanceCode]);
  562.                                 }
  563.                                 item.itemType = 3;
  564.                                 item.distance = distance;
  565.                                 item.length = length;
  566.                         } else {
  567.                                 item.itemType = 1;
  568.                                 this.state = this.blockFinal ? 2 : 0;
  569.                         }
  570.                 }
  571.                 return item;
  572.         };
  573. }
  574. initializeStaticTrees();