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