home *** CD-ROM | disk | FTP | other *** search
/ Otherware / Otherware_1_SB_Development.iso / mac / util / unix / macutil2.sha / macutil / macunpack / de_lzah.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-11-05  |  6.7 KB  |  277 lines
  1. #include "macunpack.h"
  2. #ifdef SIT
  3. #define DELZAH
  4. #endif /* SIT */
  5. #ifdef LZH
  6. #define DELZAH
  7. #endif /* LZH */
  8. #ifdef DELZAH
  9. #include "globals.h"
  10. #include "../util/masks.h"
  11. #include "../fileio/wrfile.h"
  12.  
  13. /* Note: compare with LZSS decoding in lharc! */
  14.  
  15. #define N    314
  16. #define T    (2*N-1)
  17.  
  18. /*    Huffman table used for first 6 bits of offset:
  19.     #bits    codes
  20.     3    0x000
  21.     4    0x040-0x080
  22.     5    0x100-0x2c0
  23.     6    0x300-0x5c0
  24.     7    0x600-0xbc0
  25.     8    0xc00-0xfc0
  26. */
  27.  
  28. static unsigned short HuffCode[] = {
  29.     0x000, 0x000, 0x000, 0x000, 0x000, 0x000, 0x000, 0x000,
  30.     0x000, 0x000, 0x000, 0x000, 0x000, 0x000, 0x000, 0x000,
  31.     0x000, 0x000, 0x000, 0x000, 0x000, 0x000, 0x000, 0x000,
  32.     0x000, 0x000, 0x000, 0x000, 0x000, 0x000, 0x000, 0x000,
  33.     0x040, 0x040, 0x040, 0x040, 0x040, 0x040, 0x040, 0x040,
  34.     0x040, 0x040, 0x040, 0x040, 0x040, 0x040, 0x040, 0x040,
  35.     0x080, 0x080, 0x080, 0x080, 0x080, 0x080, 0x080, 0x080,
  36.     0x080, 0x080, 0x080, 0x080, 0x080, 0x080, 0x080, 0x080,
  37.     0x0c0, 0x0c0, 0x0c0, 0x0c0, 0x0c0, 0x0c0, 0x0c0, 0x0c0,
  38.     0x0c0, 0x0c0, 0x0c0, 0x0c0, 0x0c0, 0x0c0, 0x0c0, 0x0c0,
  39.     0x100, 0x100, 0x100, 0x100, 0x100, 0x100, 0x100, 0x100,
  40.     0x140, 0x140, 0x140, 0x140, 0x140, 0x140, 0x140, 0x140,
  41.     0x180, 0x180, 0x180, 0x180, 0x180, 0x180, 0x180, 0x180,
  42.     0x1c0, 0x1c0, 0x1c0, 0x1c0, 0x1c0, 0x1c0, 0x1c0, 0x1c0,
  43.     0x200, 0x200, 0x200, 0x200, 0x200, 0x200, 0x200, 0x200,
  44.     0x240, 0x240, 0x240, 0x240, 0x240, 0x240, 0x240, 0x240,
  45.     0x280, 0x280, 0x280, 0x280, 0x280, 0x280, 0x280, 0x280,
  46.     0x2c0, 0x2c0, 0x2c0, 0x2c0, 0x2c0, 0x2c0, 0x2c0, 0x2c0,
  47.     0x300, 0x300, 0x300, 0x300, 0x340, 0x340, 0x340, 0x340,
  48.     0x380, 0x380, 0x380, 0x380, 0x3c0, 0x3c0, 0x3c0, 0x3c0,
  49.     0x400, 0x400, 0x400, 0x400, 0x440, 0x440, 0x440, 0x440,
  50.     0x480, 0x480, 0x480, 0x480, 0x4c0, 0x4c0, 0x4c0, 0x4c0,
  51.     0x500, 0x500, 0x500, 0x500, 0x540, 0x540, 0x540, 0x540,
  52.     0x580, 0x580, 0x580, 0x580, 0x5c0, 0x5c0, 0x5c0, 0x5c0,
  53.     0x600, 0x600, 0x640, 0x640, 0x680, 0x680, 0x6c0, 0x6c0,
  54.     0x700, 0x700, 0x740, 0x740, 0x780, 0x780, 0x7c0, 0x7c0,
  55.     0x800, 0x800, 0x840, 0x840, 0x880, 0x880, 0x8c0, 0x8c0,
  56.     0x900, 0x900, 0x940, 0x940, 0x980, 0x980, 0x9c0, 0x9c0,
  57.     0xa00, 0xa00, 0xa40, 0xa40, 0xa80, 0xa80, 0xac0, 0xac0,
  58.     0xb00, 0xb00, 0xb40, 0xb40, 0xb80, 0xb80, 0xbc0, 0xbc0,
  59.     0xc00, 0xc40, 0xc80, 0xcc0, 0xd00, 0xd40, 0xd80, 0xdc0,
  60.     0xe00, 0xe40, 0xe80, 0xec0, 0xf00, 0xf40, 0xf80, 0xfc0};
  61.  
  62. static short HuffLength[] = {
  63.     3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
  64.     3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
  65.     4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
  66.     4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
  67.     4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
  68.     5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
  69.     5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
  70.     5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
  71.     5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
  72.     6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  73.     6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  74.     6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  75.     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  76.     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  77.     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  78.     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8};
  79.  
  80. unsigned char (*lzah_getbyte)();
  81.  
  82. static void lzah_inithuf();
  83. static void lzah_reorder();
  84. static void lzah_move();
  85. static void lzah_getbit();
  86. static void lzah_outchar();
  87.  
  88. static char lzah_buf[4096];
  89. static int lzah_bufptr;
  90. static int lzah_bitsavail;
  91. static int lzah_bits;
  92. static int Frequ[1000];
  93. static int ForwTree[1000];
  94. static int BackTree[1000];
  95.  
  96. void de_lzah(obytes)
  97. unsigned long obytes;
  98. {
  99.     int i, i1, j, ch, byte, offs, skip;
  100.  
  101.     lzah_inithuf();
  102.     lzah_bitsavail = 0;
  103.     for(i = 0; i < 4036; i++) {
  104.     lzah_buf[i] = ' ';
  105.     }
  106.     lzah_bufptr = 4036;
  107.     while(obytes != 0) {
  108.     ch = ForwTree[T - 1];
  109.     while(ch < T) {
  110.         lzah_getbit();
  111.         if(lzah_bits & 0x80) {
  112.         ch = ch + 1;
  113.         }
  114.         ch = ForwTree[ch];
  115.     }
  116.     ch -= T;
  117.     if(Frequ[T - 1] >= 0x8000) {
  118.         lzah_reorder();
  119.     }
  120.  
  121.     i = BackTree[ch + T];
  122.     do {
  123.         j = ++Frequ[i];
  124.         i1 = i + 1;
  125.         if(Frequ[i1] < j) {
  126.         while(Frequ[++i1] < j) ;
  127.         i1--;
  128.         Frequ[i] = Frequ[i1];
  129.         Frequ[i1] = j;
  130.  
  131.         j = ForwTree[i];
  132.         BackTree[j] = i1;
  133.         if(j < T) {
  134.             BackTree[j + 1] = i1;
  135.         }
  136.         ForwTree[i] = ForwTree[i1];
  137.         ForwTree[i1] = j;
  138.         j = ForwTree[i];
  139.         BackTree[j] = i;
  140.         if(j < T) {
  141.             BackTree[j + 1] = i;
  142.         }
  143.         i = i1;
  144.         }
  145.         i = BackTree[i];
  146.     } while(i != 0);
  147.  
  148.     if(ch < 256) {
  149.         lzah_outchar((char)ch);
  150.         obytes--;
  151.     } else {
  152.         if(lzah_bitsavail != 0) {
  153.         byte = (lzah_bits << 1) & BYTEMASK;
  154.         lzah_bits = (*lzah_getbyte)() & BYTEMASK;
  155.         byte |= (lzah_bits >> lzah_bitsavail);
  156.         lzah_bits = lzah_bits << (7 - lzah_bitsavail);
  157.         } else {
  158.         byte = (*lzah_getbyte)() & BYTEMASK;
  159.         }
  160.         offs = HuffCode[byte];
  161.         skip = HuffLength[byte] - 2;
  162.         while(skip-- != 0) {
  163.         byte = byte + byte;
  164.         lzah_getbit();
  165.         if(lzah_bits & 0x80) {
  166.             byte++;
  167.         }
  168.         }
  169.         offs |= (byte & 0x3f);
  170.         offs = ((lzah_bufptr - offs - 1) & 0xfff);
  171.         ch = ch - 253;
  172.         while(ch-- > 0) {
  173.         lzah_outchar(lzah_buf[offs++ & 0xfff]);
  174.         obytes--;
  175.         if(obytes == 0) {
  176.             break;
  177.         }
  178.         }
  179.     }
  180.     }
  181. }
  182.  
  183. static void lzah_inithuf()
  184. {
  185.     int i, j;
  186.  
  187.     for(i = 0; i < N; i++) {
  188.     Frequ[i] = 1;
  189.     ForwTree[i] = i + T;
  190.     BackTree[i + T] = i;
  191.     }
  192.     for(i = 0, j = N; j < T; i += 2, j++) {
  193.     Frequ[j] = Frequ[i] + Frequ[i + 1];
  194.     ForwTree[j] = i;
  195.     BackTree[i] = j;
  196.     BackTree[i + 1] = j;
  197.     }
  198.     Frequ[T] = 0xffff;
  199.     BackTree[T - 1] = 0;
  200. }
  201.  
  202. static void lzah_reorder()
  203. {
  204.     int i, j, k, l;
  205.  
  206.     j = 0;
  207.     for(i = 0; i < T; i++) {
  208.     if(ForwTree[i] >= T) {
  209.         Frequ[j] = ((Frequ[i] + 1) >> 1);
  210.         ForwTree[j] = ForwTree[i];
  211.         j++;
  212.     }
  213.     }
  214.     for(i = 0, j = N; i < T; i += 2, j++) {
  215.     k = i + 1;
  216.     l = Frequ[i] + Frequ[k];
  217.     Frequ[j] = l;
  218.     k = j - 1;
  219.     while(l < Frequ[k]) {
  220.         k--;
  221.     }
  222.     k = k + 1;
  223.     lzah_move(Frequ + k, Frequ + k + 1, j - k);
  224.     Frequ[k] = l;
  225.     lzah_move(ForwTree + k, ForwTree + k + 1, j - k);
  226.     ForwTree[k] = i;
  227.     }
  228.     for(i = 0; i < T; i++) {
  229.     k = ForwTree[i];
  230.     if(k >= T) {
  231.         BackTree[k] = i;
  232.     } else {
  233.         BackTree[k] = i;
  234.         BackTree[k + 1] = i;
  235.     }
  236.     }
  237. }
  238.  
  239. static void lzah_move(p, q, n)
  240. int *p, *q, n;
  241. {
  242.     if(p > q) {
  243.     while(n-- > 0) {
  244.         *q++ = *p++;
  245.     }
  246.     } else {
  247.     p += n;
  248.     q += n;
  249.     while(n-- > 0) {
  250.         *--q = *--p;
  251.     }
  252.     }
  253. }
  254.  
  255. static void lzah_getbit()
  256. {
  257.     if(lzah_bitsavail != 0) {
  258.     lzah_bits = lzah_bits + lzah_bits;
  259.     lzah_bitsavail--;
  260.     } else {
  261.     lzah_bits = (*lzah_getbyte)() & BYTEMASK;
  262.     lzah_bitsavail = 7;
  263.     }
  264. }
  265.  
  266. static void lzah_outchar(ch)
  267. char ch;
  268. {
  269.     *out_ptr++ = ch;
  270.     lzah_buf[lzah_bufptr++] = ch;
  271.     lzah_bufptr &= 0xfff;
  272. }
  273. #else /* DELZAH */
  274. int delzah; /* keep lint and some compilers happy */
  275. #endif /* DELZAH */
  276.  
  277.