home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / slfinsta.zip / packinst / uac_dcpr.c < prev    next >
C/C++ Source or Header  |  2000-03-26  |  13KB  |  554 lines
  1. /* $Id: uac_dcpr.c,v 1.1 2000/03/27 04:53:11 ktk Exp $ */
  2.  
  3. /* ------------------------------------------------------------------------ */
  4. /*                                                                          */
  5. /*      These are the decompression algorithms.                             */
  6. /*      Don't change here anything (apart from memory allocation perhaps).  */
  7. /*      Any changes will very likely cause bugs!                            */
  8. /*                                                                          */
  9. /* ------------------------------------------------------------------------ */
  10.  
  11. #include "os.h"
  12.  
  13. #if defined(AMIGA)
  14.  #include <string.h> // mem*()
  15. #endif
  16. #if defined(DOS) || defined(WIN16) || defined(WINNT) || defined(OS2) || defined(UNIX)
  17.  #include <mem.h>    // mem*()
  18. #endif
  19.  
  20. #include <stdio.h>   // pipeit()
  21. #include <stdlib.h>  // malloc()
  22. #include <string.h>
  23.  
  24. #include "globals.h"
  25. #include "portable.h"
  26. #include "uac_comm.h"
  27. #include "uac_crc.h"
  28. #include "uac_dcpr.h"
  29. #include "uac_sys.h"
  30. #ifdef CRYPT
  31.  #include "unace_ps.h"
  32. #endif /* CRYPT */
  33.  
  34.  
  35. //------------------------------ QUICKSORT ---------------------------------//
  36. #define xchg_def(v1,v2) {INT dummy;\
  37.                          dummy=v1; \
  38.                          v1=v2;    \
  39.                          v2=dummy;}
  40.  
  41. void sortrange(INT left, INT right)
  42. {
  43.    INT  zl = left,
  44.         zr = right,
  45.         hyphen;
  46.  
  47.    hyphen = sort_freq[right];
  48.  
  49.    //divides by hyphen the given range into 2 parts
  50.    do
  51.    {
  52.       while (sort_freq[zl] > hyphen)
  53.          zl++;
  54.       while (sort_freq[zr] < hyphen)
  55.          zr--;
  56.       //found a too small (left side) and
  57.       //a too big (right side) element-->exchange them
  58.       if (zl <= zr)
  59.       {
  60.          xchg_def(sort_freq[zl], sort_freq[zr]);
  61.          xchg_def(sort_org[zl], sort_org[zr]);
  62.          zl++;
  63.          zr--;
  64.       }
  65.    }
  66.    while (zl < zr);
  67.  
  68.    //sort partial ranges - when very small, sort directly
  69.    if (left < zr)
  70.    {
  71.       if (left < zr - 1)
  72.          sortrange(left, zr);
  73.       else if (sort_freq[left] < sort_freq[zr])
  74.       {
  75.          xchg_def(sort_freq[left], sort_freq[zr]);
  76.          xchg_def(sort_org[left], sort_org[zr]);
  77.       }
  78.    }
  79.  
  80.    if (right > zl)
  81.    {
  82.       if (zl < right - 1)
  83.          sortrange(zl, right);
  84.       else if (sort_freq[zl] < sort_freq[right])
  85.       {
  86.          xchg_def(sort_freq[zl], sort_freq[right]);
  87.          xchg_def(sort_org[zl], sort_org[right]);
  88.       }
  89.    }
  90. }
  91.  
  92. void quicksort(INT n)
  93. {
  94.    INT  i;
  95.  
  96.    for (i = n + 1; i--;)
  97.       sort_org[i] = i;
  98.    sortrange(0, n);
  99. }
  100.  
  101. //------------------------------ read bits ---------------------------------//
  102. void readdat(void)
  103. {
  104.    UINT i;
  105.  
  106.    i = (size_rdb - 2) << 2;
  107.    rpos -= size_rdb - 2;
  108.    buf_rd[0] = buf_rd[size_rdb - 2];
  109.    buf_rd[1] = buf_rd[size_rdb - 1];
  110.    read_adds_blk((CHAR *) & buf_rd[2], i);
  111. #ifdef HI_LO_BYTE_ORDER
  112.    {
  113.       ULONG *p;
  114.       i>>=2;    // count LONGs not BYTEs
  115.       p=&buf_rd[2];
  116.       while (i--)
  117.       {
  118.          LONGswap(p);
  119.          p++; 
  120.       }
  121.    }
  122. #endif
  123. }
  124.  
  125. #define addbits(bits)                                   \
  126. {                                                       \
  127.   rpos+=(bits_rd+=bits)>>5;                             \
  128.   bits_rd&=31;                                          \
  129.   if (rpos==(size_rdb-2)) readdat();                    \
  130.   code_rd=(buf_rd[rpos] << bits_rd)                     \
  131.     +((buf_rd[rpos+1] >> (32-bits_rd))&(!bits_rd-1));   \
  132. }
  133.  
  134.  
  135. //---------------------- COMMENT DECOMPRESSION -----------------------------//
  136.  
  137. #define comm_cpr_hf(a,b) (a+b)
  138.  
  139. void dcpr_comm_init(void)
  140. {
  141.    INT  i;
  142.  
  143.    i = comm_cpr_size > size_rdb * sizeof(LONG) ? size_rdb * sizeof(LONG) : comm_cpr_size;
  144.    if (!f_err)
  145.       memcpy(buf_rd, comm, i);
  146. #ifdef HI_LO_BYTE_ORDER
  147.    {
  148.       ULONG *p;
  149.       i>>=2;    // count LONGs not BYTEs
  150.       p=buf_rd;
  151.       while (i--)
  152.       {
  153.          LONGswap(p);
  154.          p++; 
  155.       }
  156.    }
  157. #endif
  158.    code_rd = buf_rd[0];
  159.    rpos = bits_rd = 0;
  160. }
  161.  
  162. void dcpr_comm(INT comm_size)
  163. {
  164.    SHORT hash[comm_cpr_hf(255, 255) + 1];
  165.    INT  dpos = 0,
  166.         c,
  167.         pos = 0,
  168.         len,
  169.         hs;
  170.  
  171.    memset(&hash, 0, sizeof(hash));
  172.    if (comm_cpr_size)
  173.    {
  174.       dcpr_comm_init();
  175.       len = code_rd >> (32 - 15);
  176.       addbits(15);
  177.       if (len >= comm_size)
  178.          len = comm_size - 1;
  179.       if (read_wd(maxwd_mn, dcpr_code_mn, dcpr_wd_mn, max_cd_mn))
  180.          do
  181.          {
  182.             if (dpos > 1)
  183.             {
  184.                pos = hash[hs = comm_cpr_hf(comm[dpos - 1], comm[dpos - 2])];
  185.                hash[hs] = dpos;
  186.             }
  187.             addbits(dcpr_wd_mn[(c = dcpr_code_mn[code_rd >> (32 - maxwd_mn)])]);
  188.             if (rpos == size_rdb - 3)
  189.                rpos = 0;
  190.             if (c > 255)
  191.             {
  192.                c -= 256;
  193.                c += 2;
  194.                while (c--)
  195.                   comm[dpos++] = comm[pos++];
  196.             }
  197.             else
  198.             {
  199.                comm[dpos++] = c;
  200.             }
  201.          }
  202.          while (dpos < len);
  203.       comm[len] = 0;
  204.    }
  205. }
  206.  
  207. //------------------------- LZW1 DECOMPRESSION -----------------------------//
  208. void wrchar(CHAR ch)
  209. {
  210.    dcpr_do++;
  211.  
  212.    dcpr_text[dcpr_dpos] = ch;
  213.    dcpr_dpos++;
  214.    dcpr_dpos &= dcpr_dican;
  215. }
  216.  
  217. void copystr(LONG d, INT l)
  218. {
  219.    INT  mpos;
  220.  
  221.    dcpr_do += l;
  222.  
  223.    mpos = dcpr_dpos - d;
  224.    mpos &= dcpr_dican;
  225.  
  226.    if ((mpos >= dcpr_dicsiz - maxlength) || (dcpr_dpos >= dcpr_dicsiz - maxlength))
  227.    {
  228.       while (l--)
  229.       {
  230.          dcpr_text[dcpr_dpos] = dcpr_text[mpos];
  231.          dcpr_dpos++;
  232.          dcpr_dpos &= dcpr_dican;
  233.          mpos++;
  234.          mpos &= dcpr_dican;
  235.       }
  236.    }
  237.    else
  238.    {
  239.       while (l--)
  240.          dcpr_text[dcpr_dpos++] = dcpr_text[mpos++];
  241.       dcpr_dpos &= dcpr_dican;
  242.    }
  243. }
  244.  
  245. void decompress(void)
  246. {
  247.    INT  c,
  248.         lg,
  249.         i,
  250.         k;
  251.    ULONG dist;
  252.  
  253.    while (dcpr_do < dcpr_do_max)
  254.    {
  255.       if (!blocksize)
  256.          if (!calc_dectabs())
  257.             return;
  258.  
  259.       addbits(dcpr_wd_mn[(c = dcpr_code_mn[code_rd >> (32 - maxwd_mn)])]);
  260.       blocksize--;
  261.       if (c > 255)
  262.       {
  263.          if (c > 259)
  264.          {
  265.             if ((c -= 260) > 1)
  266.             {
  267.                dist = (code_rd >> (33 - c)) + (1L << (c - 1));
  268.                addbits(c - 1);
  269.             }
  270.             else
  271.                dist = c;
  272.             dcpr_olddist[(dcpr_oldnum = (dcpr_oldnum + 1) & 3)] = dist;
  273.             i = 2;
  274.             if (dist > maxdis2)
  275.             {
  276.                i++;
  277.                if (dist > maxdis3)
  278.                   i++;
  279.             }
  280.          }
  281.          else
  282.          {
  283.             dist = dcpr_olddist[(dcpr_oldnum - (c &= 255)) & 3];
  284.             for (k = c + 1; k--;)
  285.                dcpr_olddist[(dcpr_oldnum - k) & 3] = dcpr_olddist[(dcpr_oldnum - k + 1) & 3];
  286.             dcpr_olddist[dcpr_oldnum] = dist;
  287.             i = 2;
  288.             if (c > 1)
  289.                i++;
  290.          }
  291.          addbits(dcpr_wd_lg[(lg = dcpr_code_lg[code_rd >> (32 - maxwd_lg)])]);
  292.          dist++;
  293.          lg += i;
  294.          copystr(dist, lg);
  295.       }
  296.       else
  297.          wrchar(c);
  298.    }
  299. }
  300.  
  301. //-------------------------- HUFFMAN ROUTINES ------------------------------//
  302. INT  makecode(UINT maxwd, UINT size1_t, UCHAR * wd, USHORT * code)
  303. {
  304.    UINT maxc,
  305.         size2_t,
  306.         l,
  307.         c,
  308.         i,
  309.         max_make_code;
  310.  
  311.    memcpy(&sort_freq, wd, (size1_t + 1) * sizeof(CHAR));
  312.    if (size1_t)
  313.       quicksort(size1_t);
  314.    else
  315.       sort_org[0] = 0;
  316.    sort_freq[size1_t + 1] = size2_t = c = 0;
  317.    while (sort_freq[size2_t])
  318.       size2_t++;
  319.    if (size2_t < 2)
  320.    {
  321.       i = sort_org[0];
  322.       wd[i] = 1;
  323.       size2_t += (size2_t == 0);
  324.    }
  325.    size2_t--;
  326.  
  327.    max_make_code = 1 << maxwd;
  328.    for (i = size2_t + 1; i-- && c < max_make_code;)
  329.    {
  330.       maxc = 1 << (maxwd - sort_freq[i]);
  331.       l = sort_org[i];
  332.       if (c + maxc > max_make_code)
  333.       {
  334.          dcpr_do = dcpr_do_max;
  335.          return (0);
  336.       }
  337.       memset16(&code[c], l, maxc);
  338.       c += maxc;
  339.    }
  340.    return (1);
  341. }
  342.  
  343. INT  read_wd(UINT maxwd, USHORT * code, UCHAR * wd, INT max_el)
  344. {
  345.    UINT c,
  346.         i,
  347.         j,
  348.         num_el,
  349.         l,
  350.         uplim,
  351.         lolim;
  352.  
  353.    memset(wd, 0, max_el * sizeof(CHAR));
  354.    memset(code, 0, (1 << maxwd) * sizeof(SHORT));
  355.  
  356.    num_el = code_rd >> (32 - 9);
  357.    addbits(9);
  358.    if (num_el > max_el)
  359.       num_el = max_el;
  360.  
  361.    lolim = code_rd >> (32 - 4);
  362.    addbits(4);
  363.    uplim = code_rd >> (32 - 4);
  364.    addbits(4);
  365.  
  366.    for (i = -1; ++i <= uplim;)
  367.    {
  368.       wd_svwd[i] = code_rd >> (32 - 3);
  369.       addbits(3);
  370.    }
  371.    if (!makecode(maxwd_svwd, uplim, wd_svwd, code))
  372.       return (0);
  373.    j = 0;
  374.    while (j <= num_el)
  375.    {
  376.       c = code[code_rd >> (32 - maxwd_svwd)];
  377.       addbits(wd_svwd[c]);
  378.       if (c < uplim)
  379.          wd[j++] = c;
  380.       else
  381.       {
  382.          l = (code_rd >> 28) + 4;
  383.          addbits(4);
  384.          while (l-- && j <= num_el)
  385.             wd[j++] = 0;
  386.       }
  387.    }
  388.    if (uplim)
  389.       for (i = 0; ++i <= num_el;)
  390.          wd[i] = (wd[i] + wd[i - 1]) % uplim;
  391.    for (i = -1; ++i <= num_el;)
  392.       if (wd[i])
  393.          wd[i] += lolim;
  394.  
  395.    return (makecode(maxwd, num_el, wd, code));
  396.  
  397. }
  398.  
  399. INT  calc_dectabs(void)
  400. {
  401.    if (!read_wd(maxwd_mn, dcpr_code_mn, dcpr_wd_mn, max_cd_mn)
  402.        || !read_wd(maxwd_lg, dcpr_code_lg, dcpr_wd_lg, max_cd_lg))
  403.       return (0);
  404.  
  405.    blocksize = code_rd >> (32 - 15);
  406.    addbits(15);
  407.  
  408.    return (1);
  409. }
  410.  
  411. //---------------------------- BLOCK ROUTINES ------------------------------//
  412. INT  decompress_blk(CHAR * buf, UINT len)
  413. {
  414.    LONG old_pos = dcpr_dpos;
  415.    INT  i;
  416.  
  417.    dcpr_do = 0;
  418.    if ((dcpr_do_max = len - maxlength) > dcpr_size)
  419.       dcpr_do_max = dcpr_size;
  420.    if ((LONG) dcpr_size > 0 && dcpr_do_max)
  421.    {
  422.       decompress();
  423.       if (old_pos + dcpr_do > dcpr_dicsiz)
  424.       {
  425.          i = dcpr_dicsiz - old_pos;
  426.          memcpy(buf, &dcpr_text[old_pos], i);
  427.          memcpy(&buf[i], dcpr_text, dcpr_do - i);
  428.       }
  429.       else
  430.          memcpy(buf, &dcpr_text[old_pos], dcpr_do);
  431.    }
  432.    dcpr_size -= dcpr_do;
  433.    return (dcpr_do);
  434. }
  435.  
  436. INT unstore(CHAR * buf, UINT len)
  437. {
  438.    UINT rd = 0,
  439.         i,
  440.         pos = 0;
  441.  
  442. #ifdef CRYPT
  443.    len = crypt_len(len - 8);    /* because of decryption */
  444. #endif /* CRYPT */
  445.  
  446.    while ((i = read_adds_blk((CHAR *) buf_rd, (INT) ((i = ((len > dcpr_size) ? dcpr_size : len)) > size_rdb ? size_rdb : i))) != 0)
  447.    {
  448.       rd += i;
  449.       len -= i;
  450.       memcpy(&buf[pos], buf_rd, i);
  451.       pos += i;
  452.    }
  453.    dcpr_size -= rd;
  454.    for (i = 0; i < rd; i++)
  455.    {
  456.       dcpr_text[dcpr_dpos] = buf[i];
  457.       dcpr_dpos++;
  458.       dcpr_dpos &= dcpr_dican;
  459.    }
  460.    return (INT)rd;
  461. }
  462.  
  463. INT  dcpr_adds_blk(CHAR * buf, UINT len)
  464. {
  465.    INT  r;
  466.  
  467.    switch (fhead.TECH.TYPE)
  468.    {
  469.       case TYPE_STORE:
  470.          r = unstore(buf, len);
  471.          break;
  472.       case TYPE_LZW1:
  473.          r = decompress_blk(buf, len);
  474.          break;
  475.       default:
  476.          pipeit("\nFile compressed with unknown method. Decompression not possible.\n");
  477.          f_err = ERR_OTHER;
  478.          r = 0;
  479.    }
  480.    rd_crc = getcrc(rd_crc, (UCHAR *)buf, r);
  481.    return r;
  482. }
  483.  
  484.  
  485. //----------------------------- INIT ROUTINES ------------------------------//
  486. void dcpr_init(void)
  487. {
  488.    dcpr_frst_file = 1;
  489.  
  490.    dcpr_dic = 20;
  491.    while ((dcpr_text = malloc(dcpr_dicsiz = (LONG) 1 << dcpr_dic))==NULL)
  492.       dcpr_dic--;
  493.    dcpr_dican = dcpr_dicsiz - 1;
  494. }
  495.  
  496. void dcpr_init_file(void)
  497. {
  498.    UINT i;
  499.  
  500. #ifdef CRYPT
  501.  
  502.    reset_cryptkey();
  503.  
  504. #else /* CRYPT */
  505.  
  506.    if (head.HEAD_FLAGS & ACE_PASSW)
  507.    {
  508.       pipeit("\nFound passworded file. Decryption not supported.\n");
  509.       f_err = ERR_OTHER;
  510.       return;
  511.    }
  512.  
  513. #endif /* CRYPT */
  514.  
  515.    rd_crc = CRC_MASK;
  516.    dcpr_size = fhead.SIZE;
  517.    if (fhead.TECH.TYPE == TYPE_LZW1)
  518.    {
  519.       if ((fhead.TECH.PARM & 15) + 10 > dcpr_dic)
  520.       {
  521.          pipeit("\nNot enough memory or dictionary of archive too large.\n");
  522.          f_err = ERR_MEM;
  523.          return;
  524.       }
  525.  
  526.       i = size_rdb * sizeof(LONG);
  527.       read_adds_blk((CHAR *) buf_rd, i);
  528. #ifdef HI_LO_BYTE_ORDER
  529.       {
  530.          ULONG *p;
  531.          i>>=2;    // count LONGs not BYTEs
  532.          p=buf_rd;
  533.          while (i--)
  534.          {
  535.             LONGswap(p);
  536.             p++; 
  537.          }
  538.       }
  539. #endif
  540.       code_rd = buf_rd[0];
  541.       bits_rd = rpos = 0;
  542.  
  543.       blocksize = 0;
  544.    }
  545.    if (!adat.sol || dcpr_frst_file)
  546.       dcpr_dpos = 0;
  547.  
  548.    dcpr_oldnum = 0;
  549.    memset(&dcpr_olddist, 0, sizeof(dcpr_olddist));
  550.  
  551.    dcpr_frst_file = 0;
  552. }
  553.  
  554.