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