1 /* 2 Copyright 2008-2013 3 Matthias Ehmann, 4 Michael Gerhaeuser, 5 Carsten Miller, 6 Bianca Valentin, 7 Alfred Wassermann, 8 Peter Wilfahrt 9 10 This file is part of JSXGraph and JSXCompressor. 11 12 JSXGraph is free software dual licensed under the GNU LGPL or MIT License. 13 JSXCompressor is free software dual licensed under the GNU LGPL or Apache License. 14 15 You can redistribute it and/or modify it under the terms of the 16 17 * GNU Lesser General Public License as published by 18 the Free Software Foundation, either version 3 of the License, or 19 (at your option) any later version 20 OR 21 * MIT License: https://github.com/jsxgraph/jsxgraph/blob/master/LICENSE.MIT 22 OR 23 * Apache License Version 2.0 24 25 JSXGraph is distributed in the hope that it will be useful, 26 but WITHOUT ANY WARRANTY; without even the implied warranty of 27 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 28 GNU Lesser General Public License for more details. 29 30 You should have received a copy of the GNU Lesser General Public License, Apache 31 License, and the MIT License along with JSXGraph. If not, see 32 <http://www.gnu.org/licenses/>, <https://www.apache.org/licenses/LICENSE-2.0.html>, 33 and <http://opensource.org/licenses/MIT/>. 34 */ 35 36 37 /*global JXG: true, define: true*/ 38 /*jslint nomen: true, plusplus: true, bitwise: true*/ 39 40 /* depends: 41 jxg 42 */ 43 44 /** 45 * @fileoverview Utilities for uncompressing and base64 decoding 46 */ 47 48 define(['jxg'], function (JXG) { 49 50 "use strict"; 51 52 // Zip routine constants 53 54 var bitReverse = [ 55 0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0, 56 0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0, 57 0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8, 58 0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8, 59 0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4, 60 0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4, 61 0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec, 62 0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc, 63 0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2, 64 0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2, 65 0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea, 66 0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa, 67 0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6, 68 0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6, 69 0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee, 70 0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe, 71 0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1, 72 0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1, 73 0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9, 74 0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9, 75 0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5, 76 0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5, 77 0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed, 78 0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd, 79 0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3, 80 0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3, 81 0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb, 82 0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb, 83 0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7, 84 0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7, 85 0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef, 86 0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff 87 ], 88 cplens = [ 89 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 90 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0 91 ], 92 93 cplext = [ 94 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 95 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 99, 99 96 ], /* 99==invalid */ 97 98 cpdist = [ 99 0x0001, 0x0002, 0x0003, 0x0004, 0x0005, 0x0007, 0x0009, 0x000d, 100 0x0011, 0x0019, 0x0021, 0x0031, 0x0041, 0x0061, 0x0081, 0x00c1, 101 0x0101, 0x0181, 0x0201, 0x0301, 0x0401, 0x0601, 0x0801, 0x0c01, 102 0x1001, 0x1801, 0x2001, 0x3001, 0x4001, 0x6001 103 ], 104 105 cpdext = [ 106 0, 0, 0, 0, 1, 1, 2, 2, 107 3, 3, 4, 4, 5, 5, 6, 6, 108 7, 7, 8, 8, 9, 9, 10, 10, 109 11, 11, 12, 12, 13, 13 110 ], 111 112 border = [16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15], 113 114 NAMEMAX = 256; 115 116 117 // Util namespace 118 JXG.Util = JXG.Util || {}; 119 120 /** 121 * @class Unzip class 122 * Class for gunzipping, unzipping and base64 decoding of files. 123 * It is used for reading GEONExT, Geogebra and Intergeo files. 124 * 125 * Only Huffman codes are decoded in gunzip. 126 * The code is based on the source code for gunzip.c by Pasi Ojala 127 * @see http://www.cs.tut.fi/~albert/Dev/gunzip/gunzip.c 128 * @see http://www.cs.tut.fi/~albert 129 */ 130 JXG.Util.Unzip = function (barray) { 131 var gpflags, crc, SIZE, fileout, flens, fmax, skipdir, 132 outputArr = [], 133 output = '', 134 debug = false, 135 files = 0, 136 unzipped = [], 137 buf32k = new Array(32768), 138 bIdx = 0, 139 modeZIP = false, 140 barraylen = barray.length, 141 bytepos = 0, 142 bitpos = 0, 143 bb = 1, 144 bits = 0, 145 literalTree = new Array(288), 146 distanceTree = new Array(32), 147 treepos = 0, 148 Places = null, 149 Places2 = null, 150 impDistanceTree = new Array(64), 151 impLengthTree = new Array(64), 152 len = 0, 153 fpos = new Array(17), 154 nameBuf = []; 155 156 fpos[0] = 0; 157 158 function readByte() { 159 bits += 8; 160 161 if (bytepos < barraylen) { 162 return barray[bytepos++]; 163 } 164 165 return -1; 166 } 167 168 function byteAlign() { 169 bb = 1; 170 } 171 172 function readBit() { 173 var carry; 174 175 try { // Prevent problems on iOS7 with >> 176 bits++; 177 carry = (bb & 1); 178 bb >>= 1; 179 180 if (bb === 0) { 181 bb = readByte(); 182 carry = (bb & 1); 183 bb = (bb >> 1) | 0x80; 184 } 185 186 return carry; 187 } catch (e) { 188 throw e; 189 } 190 } 191 192 function readBits(a) { 193 var res = 0, 194 i = a; 195 196 // Prevent problems on iOS7 with >> 197 try { 198 while (i--) { 199 res = (res << 1) | readBit(); 200 } 201 202 if (a) { 203 res = bitReverse[res] >> (8 - a); 204 } 205 } catch (e) { 206 throw e; 207 } 208 209 return res; 210 } 211 212 function flushBuffer() { 213 bIdx = 0; 214 } 215 216 function addBuffer(a) { 217 SIZE++; 218 buf32k[bIdx++] = a; 219 outputArr.push(String.fromCharCode(a)); 220 221 if (bIdx === 0x8000) { 222 bIdx = 0; 223 } 224 } 225 226 function HufNode() { 227 this.b0 = 0; 228 this.b1 = 0; 229 this.jump = null; 230 this.jumppos = -1; 231 } 232 233 function isPat() { 234 while (true) { 235 if (fpos[len] >= fmax) { 236 return -1; 237 } 238 239 if (flens[fpos[len]] === len) { 240 return fpos[len]++; 241 } 242 243 fpos[len]++; 244 } 245 } 246 247 function rec() { 248 var curplace = Places[treepos], 249 tmp; 250 251 if (len === 17) { 252 return -1; 253 } 254 treepos++; 255 len++; 256 257 tmp = isPat(); 258 259 if (tmp >= 0) { 260 /* leaf cell for 0-bit */ 261 curplace.b0 = tmp; 262 } else { 263 /* Not a Leaf cell */ 264 curplace.b0 = 0x8000; 265 266 if (rec()) { 267 return -1; 268 } 269 } 270 271 tmp = isPat(); 272 273 if (tmp >= 0) { 274 /* leaf cell for 1-bit */ 275 curplace.b1 = tmp; 276 /* Just for the display routine */ 277 curplace.jump = null; 278 } else { 279 /* Not a Leaf cell */ 280 curplace.b1 = 0x8000; 281 curplace.jump = Places[treepos]; 282 curplace.jumppos = treepos; 283 if (rec()) { 284 return -1; 285 } 286 } 287 len--; 288 289 return 0; 290 } 291 292 function createTree(currentTree, numval, lengths, show) { 293 var i; 294 295 Places = currentTree; 296 treepos = 0; 297 flens = lengths; 298 fmax = numval; 299 300 for (i = 0; i < 17; i++) { 301 fpos[i] = 0; 302 } 303 len = 0; 304 305 if (rec()) { 306 return -1; 307 } 308 309 return 0; 310 } 311 312 function decodeValue(currentTree) { 313 var len, i, b, 314 xtreepos = 0, 315 X = currentTree[xtreepos]; 316 317 /* decode one symbol of the data */ 318 while (true) { 319 b = readBit(); 320 321 if (b) { 322 if (!(X.b1 & 0x8000)) { 323 /* If leaf node, return data */ 324 return X.b1; 325 } 326 327 X = X.jump; 328 len = currentTree.length; 329 330 for (i = 0; i < len; i++) { 331 if (currentTree[i] === X) { 332 xtreepos = i; 333 break; 334 } 335 } 336 } else { 337 if (!(X.b0 & 0x8000)) { 338 /* If leaf node, return data */ 339 return X.b0; 340 } 341 xtreepos++; 342 X = currentTree[xtreepos]; 343 } 344 } 345 } 346 347 function deflateLoop() { 348 var last, c, type, i, j, l, ll, ll2, len, blockLen, dist, cSum, 349 n, literalCodes, distCodes, lenCodes, z; 350 351 do { 352 last = readBit(); 353 type = readBits(2); 354 355 if (type === 0) { 356 // Stored 357 byteAlign(); 358 blockLen = readByte(); 359 blockLen |= (readByte() << 8); 360 361 cSum = readByte(); 362 cSum |= (readByte() << 8); 363 364 if (((blockLen ^ ~cSum) & 0xffff)) { 365 JXG.debug('BlockLen checksum mismatch\n'); 366 } 367 368 while (blockLen--) { 369 c = readByte(); 370 addBuffer(c); 371 } 372 } else if (type === 1) { 373 /* Fixed Huffman tables -- fixed decode routine */ 374 while (true) { 375 /* 376 256 0000000 0 377 : : : 378 279 0010111 23 379 0 00110000 48 380 : : : 381 143 10111111 191 382 280 11000000 192 383 : : : 384 287 11000111 199 385 144 110010000 400 386 : : : 387 255 111111111 511 388 389 Note the bit order! 390 */ 391 392 j = (bitReverse[readBits(7)] >> 1); 393 394 if (j > 23) { 395 j = (j << 1) | readBit(); /* 48..255 */ 396 397 if (j > 199) { /* 200..255 */ 398 j -= 128; /* 72..127 */ 399 j = (j << 1) | readBit(); /* 144..255 << */ 400 } else { /* 48..199 */ 401 j -= 48; /* 0..151 */ 402 if (j > 143) { 403 j = j + 136; /* 280..287 << */ 404 /* 0..143 << */ 405 } 406 } 407 } else { /* 0..23 */ 408 j += 256; /* 256..279 << */ 409 } 410 411 if (j < 256) { 412 addBuffer(j); 413 } else if (j === 256) { 414 /* EOF */ 415 break; 416 } else { 417 j -= 256 + 1; /* bytes + EOF */ 418 len = readBits(cplext[j]) + cplens[j]; 419 j = bitReverse[readBits(5)] >> 3; 420 421 if (cpdext[j] > 8) { 422 dist = readBits(8); 423 dist |= (readBits(cpdext[j] - 8) << 8); 424 } else { 425 dist = readBits(cpdext[j]); 426 } 427 428 dist += cpdist[j]; 429 430 for (j = 0; j < len; j++) { 431 c = buf32k[(bIdx - dist) & 0x7fff]; 432 addBuffer(c); 433 } 434 } 435 } // while 436 } else if (type === 2) { 437 // "static" just to preserve stack 438 ll = new Array(288 + 32); 439 440 // Dynamic Huffman tables 441 literalCodes = 257 + readBits(5); 442 distCodes = 1 + readBits(5); 443 lenCodes = 4 + readBits(4); 444 445 for (j = 0; j < 19; j++) { 446 ll[j] = 0; 447 } 448 449 // Get the decode tree code lengths 450 451 for (j = 0; j < lenCodes; j++) { 452 ll[border[j]] = readBits(3); 453 } 454 len = distanceTree.length; 455 456 for (i = 0; i < len; i++) { 457 distanceTree[i] = new HufNode(); 458 } 459 460 if (createTree(distanceTree, 19, ll, 0)) { 461 flushBuffer(); 462 return 1; 463 } 464 465 //read in literal and distance code lengths 466 n = literalCodes + distCodes; 467 i = 0; 468 z = -1; 469 470 while (i < n) { 471 z++; 472 j = decodeValue(distanceTree); 473 474 // length of code in bits (0..15) 475 if (j < 16) { 476 ll[i++] = j; 477 // repeat last length 3 to 6 times 478 } else if (j === 16) { 479 j = 3 + readBits(2); 480 481 if (i + j > n) { 482 flushBuffer(); 483 return 1; 484 } 485 l = i ? ll[i - 1] : 0; 486 487 while (j--) { 488 ll[i++] = l; 489 } 490 } else { 491 // 3 to 10 zero length codes 492 if (j === 17) { 493 j = 3 + readBits(3); 494 // j == 18: 11 to 138 zero length codes 495 } else { 496 j = 11 + readBits(7); 497 } 498 499 if (i + j > n) { 500 flushBuffer(); 501 return 1; 502 } 503 504 while (j--) { 505 ll[i++] = 0; 506 } 507 } 508 } 509 510 // Can overwrite tree decode tree as it is not used anymore 511 len = literalTree.length; 512 for (i = 0; i < len; i++) { 513 literalTree[i] = new HufNode(); 514 } 515 516 if (createTree(literalTree, literalCodes, ll, 0)) { 517 flushBuffer(); 518 return 1; 519 } 520 521 len = literalTree.length; 522 523 for (i = 0; i < len; i++) { 524 distanceTree[i] = new HufNode(); 525 } 526 527 ll2 = []; 528 529 for (i = literalCodes; i < ll.length; i++) { 530 ll2[i - literalCodes] = ll[i]; 531 } 532 533 if (createTree(distanceTree, distCodes, ll2, 0)) { 534 flushBuffer(); 535 return 1; 536 } 537 538 while (true) { 539 j = decodeValue(literalTree); 540 541 // In C64: if carry set 542 if (j >= 256) { 543 j -= 256; 544 if (j === 0) { 545 // EOF 546 break; 547 } 548 549 j -= 1; 550 len = readBits(cplext[j]) + cplens[j]; 551 j = decodeValue(distanceTree); 552 553 if (cpdext[j] > 8) { 554 dist = readBits(8); 555 dist |= (readBits(cpdext[j] - 8) << 8); 556 } else { 557 dist = readBits(cpdext[j]); 558 } 559 560 dist += cpdist[j]; 561 562 while (len--) { 563 c = buf32k[(bIdx - dist) & 0x7fff]; 564 addBuffer(c); 565 } 566 } else { 567 addBuffer(j); 568 } 569 } 570 } 571 } while (!last); 572 573 flushBuffer(); 574 byteAlign(); 575 576 return 0; 577 } 578 579 function nextFile() { 580 var i, c, extralen, filelen, size, compSize, crc, method, 581 tmp = []; 582 583 // Prevent problems on iOS7 with >> 584 try { 585 outputArr = []; 586 modeZIP = false; 587 tmp[0] = readByte(); 588 tmp[1] = readByte(); 589 590 //GZIP 591 if (tmp[0] === 0x78 && tmp[1] === 0xda) { 592 deflateLoop(); 593 unzipped[files] = [outputArr.join(''), 'geonext.gxt']; 594 files++; 595 } 596 597 //GZIP 598 if (tmp[0] === 0x1f && tmp[1] === 0x8b) { 599 skipdir(); 600 unzipped[files] = [outputArr.join(''), 'file']; 601 files++; 602 } 603 604 //ZIP 605 if (tmp[0] === 0x50 && tmp[1] === 0x4b) { 606 modeZIP = true; 607 tmp[2] = readByte(); 608 tmp[3] = readByte(); 609 610 if (tmp[2] === 0x03 && tmp[3] === 0x04) { 611 //MODE_ZIP 612 tmp[0] = readByte(); 613 tmp[1] = readByte(); 614 615 gpflags = readByte(); 616 gpflags |= (readByte() << 8); 617 618 method = readByte(); 619 method |= (readByte() << 8); 620 621 readByte(); 622 readByte(); 623 readByte(); 624 readByte(); 625 626 crc = readByte(); 627 crc |= (readByte() << 8); 628 crc |= (readByte() << 16); 629 crc |= (readByte() << 24); 630 631 compSize = readByte(); 632 compSize |= (readByte() << 8); 633 compSize |= (readByte() << 16); 634 compSize |= (readByte() << 24); 635 636 size = readByte(); 637 size |= (readByte() << 8); 638 size |= (readByte() << 16); 639 size |= (readByte() << 24); 640 641 filelen = readByte(); 642 filelen |= (readByte() << 8); 643 644 extralen = readByte(); 645 extralen |= (readByte() << 8); 646 647 i = 0; 648 nameBuf = []; 649 650 while (filelen--) { 651 c = readByte(); 652 if (c === '/' | c === ':') { 653 i = 0; 654 } else if (i < NAMEMAX - 1) { 655 nameBuf[i++] = String.fromCharCode(c); 656 } 657 } 658 659 if (!fileout) { 660 fileout = nameBuf; 661 } 662 663 i = 0; 664 while (i < extralen) { 665 c = readByte(); 666 i++; 667 } 668 669 SIZE = 0; 670 671 if (method === 8) { 672 deflateLoop(); 673 unzipped[files] = new Array(2); 674 unzipped[files][0] = outputArr.join(''); 675 unzipped[files][1] = nameBuf.join(''); 676 files++; 677 } 678 679 skipdir(); 680 } 681 } 682 } catch (e) { 683 throw e; 684 } 685 } 686 687 skipdir = function () { 688 var crc, compSize, size, os, i, c, 689 tmp = []; 690 691 if ((gpflags & 8)) { 692 tmp[0] = readByte(); 693 tmp[1] = readByte(); 694 tmp[2] = readByte(); 695 tmp[3] = readByte(); 696 697 if (tmp[0] === 0x50 && 698 tmp[1] === 0x4b && 699 tmp[2] === 0x07 && 700 tmp[3] === 0x08) { 701 crc = readByte(); 702 crc |= (readByte() << 8); 703 crc |= (readByte() << 16); 704 crc |= (readByte() << 24); 705 } else { 706 crc = tmp[0] | (tmp[1] << 8) | (tmp[2] << 16) | (tmp[3] << 24); 707 } 708 709 compSize = readByte(); 710 compSize |= (readByte() << 8); 711 compSize |= (readByte() << 16); 712 compSize |= (readByte() << 24); 713 714 size = readByte(); 715 size |= (readByte() << 8); 716 size |= (readByte() << 16); 717 size |= (readByte() << 24); 718 } 719 720 if (modeZIP) { 721 nextFile(); 722 } 723 724 tmp[0] = readByte(); 725 if (tmp[0] !== 8) { 726 return; 727 } 728 729 gpflags = readByte(); 730 731 readByte(); 732 readByte(); 733 readByte(); 734 readByte(); 735 736 readByte(); 737 os = readByte(); 738 739 if ((gpflags & 4)) { 740 tmp[0] = readByte(); 741 tmp[2] = readByte(); 742 len = tmp[0] + 256 * tmp[1]; 743 for (i = 0; i < len; i++) { 744 readByte(); 745 } 746 } 747 748 if ((gpflags & 8)) { 749 i = 0; 750 nameBuf = []; 751 752 c = readByte(); 753 while (c) { 754 if (c === '7' || c === ':') { 755 i = 0; 756 } 757 758 if (i < NAMEMAX - 1) { 759 nameBuf[i++] = c; 760 } 761 762 c = readByte(); 763 } 764 } 765 766 if ((gpflags & 16)) { 767 c = readByte(); 768 while (c) { 769 c = readByte(); 770 } 771 } 772 773 if ((gpflags & 2)) { 774 readByte(); 775 readByte(); 776 } 777 778 deflateLoop(); 779 780 crc = readByte(); 781 crc |= (readByte() << 8); 782 crc |= (readByte() << 16); 783 crc |= (readByte() << 24); 784 785 size = readByte(); 786 size |= (readByte() << 8); 787 size |= (readByte() << 16); 788 size |= (readByte() << 24); 789 790 if (modeZIP) { 791 nextFile(); 792 } 793 }; 794 795 JXG.Util.Unzip.prototype.unzipFile = function (name) { 796 var i; 797 798 this.unzip(); 799 800 for (i = 0; i < unzipped.length; i++) { 801 if (unzipped[i][1] === name) { 802 return unzipped[i][0]; 803 } 804 } 805 806 return ''; 807 }; 808 809 JXG.Util.Unzip.prototype.unzip = function () { 810 nextFile(); 811 return unzipped; 812 }; 813 }; 814 815 return JXG.Util; 816 }); 817