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