home *** CD-ROM | disk | FTP | other *** search
/ FM Towns: Free Software Collection 3 / FREEWARE.BIN / towns_os / whisper / source / lzss.c < prev    next >
Text File  |  1980-01-02  |  11KB  |  417 lines
  1. /********************************************************
  2.     ＬＺＳＳ法による圧縮
  3.  
  4.     88.8.15 Original 奥村晴彦(Turbo-C MS-DOS)
  5.     89.2.27 OS9/6809 MW-C Convert Nanno-NET Ken
  6.     89.2.27 Bug Fix ? Apend insnode(r,len) "len" by ken
  7.     90.1.27 Modefal By Ken
  8. *********************************************************/
  9. #include    <stdio.h>
  10. #include    <stdlib.h>
  11.  
  12. #define    TRUE    1
  13. #define    FALSE    0
  14. #define    ERR    (-1)
  15.  
  16. #define    unlink    remove
  17.  
  18. #define N   2048    /* バッファサイズ Max 4096 */
  19. #define F   18      /* 先読みバッファサイズ Max 18 */
  20. #define NIL N       /* 木の末端 */
  21.  
  22. char    *mak_work(char *file);
  23.  
  24. unsigned short int t_crc=0;
  25.  
  26. static  unsigned int mask;
  27. static  char    *bas,*ptr;
  28. static  char    dmy_buf[18];
  29. static  int     now,new,len;
  30. static  int     status,adr;
  31. static  int     pos,mat_len;
  32. static  char    *md_ptr;
  33.  
  34. static  char    text_buf[N+F-1];
  35. static  int     lson[N+1];
  36. static  int     rson[N+257];
  37. static  int     dad[N+1];
  38.  
  39. static unsigned short int crctbl[] = {
  40.         0x0000,0xC0C1,0xC181,0x0140,0xC301,0x03C0,0x0280,0xC241,
  41.         0xC601,0x06C0,0x0780,0xC741,0x0500,0xC5C1,0xC481,0x0440,
  42.         0xCC01,0x0CC0,0x0D80,0xCD41,0x0F00,0xCFC1,0xCE81,0x0E40,
  43.         0x0A00,0xCAC1,0xCB81,0x0B40,0xC901,0x09C0,0x0880,0xC841,
  44.         0xD801,0x18C0,0x1980,0xD941,0x1B00,0xDBC1,0xDA81,0x1A40,
  45.         0x1E00,0xDEC1,0xDF81,0x1F40,0xDD01,0x1DC0,0x1C80,0xDC41,
  46.         0x1400,0xD4C1,0xD581,0x1540,0xD701,0x17C0,0x1680,0xD641,
  47.         0xD201,0x12C0,0x1380,0xD341,0x1100,0xD1C1,0xD081,0x1040,
  48.         0xF001,0x30C0,0x3180,0xF141,0x3300,0xF3C1,0xF281,0x3240,
  49.         0x3600,0xF6C1,0xF781,0x3740,0xF501,0x35C0,0x3480,0xF441,
  50.         0x3C00,0xFCC1,0xFD81,0x3D40,0xFF01,0x3FC0,0x3E80,0xFE41,
  51.         0xFA01,0x3AC0,0x3B80,0xFB41,0x3900,0xF9C1,0xF881,0x3840,
  52.         0x2800,0xE8C1,0xE981,0x2940,0xEB01,0x2BC0,0x2A80,0xEA41,
  53.         0xEE01,0x2EC0,0x2F80,0xEF41,0x2D00,0xEDC1,0xEC81,0x2C40,
  54.         0xE401,0x24C0,0x2580,0xE541,0x2700,0xE7C1,0xE681,0x2640,
  55.         0x2200,0xE2C1,0xE381,0x2340,0xE101,0x21C0,0x2080,0xE041,
  56.         0xA001,0x60C0,0x6180,0xA141,0x6300,0xA3C1,0xA281,0x6240,
  57.         0x6600,0xA6C1,0xA781,0x6740,0xA501,0x65C0,0x6480,0xA441,
  58.         0x6C00,0xACC1,0xAD81,0x6D40,0xAF01,0x6FC0,0x6E80,0xAE41,
  59.         0xAA01,0x6AC0,0x6B80,0xAB41,0x6900,0xA9C1,0xA881,0x6840,
  60.         0x7800,0xB8C1,0xB981,0x7940,0xBB01,0x7BC0,0x7A80,0xBA41,
  61.         0xBE01,0x7EC0,0x7F80,0xBF41,0x7D00,0xBDC1,0xBC81,0x7C40,
  62.         0xB401,0x74C0,0x7580,0xB541,0x7700,0xB7C1,0xB681,0x7640,
  63.         0x7200,0xB2C1,0xB381,0x7340,0xB101,0x71C0,0x7080,0xB041,
  64.         0x5000,0x90C1,0x9181,0x5140,0x9301,0x53C0,0x5280,0x9241,
  65.         0x9601,0x56C0,0x5780,0x9741,0x5500,0x95C1,0x9481,0x5440,
  66.         0x9C01,0x5CC0,0x5D80,0x9D41,0x5F00,0x9FC1,0x9E81,0x5E40,
  67.         0x5A00,0x9AC1,0x9B81,0x5B40,0x9901,0x59C0,0x5880,0x9841,
  68.         0x8801,0x48C0,0x4980,0x8941,0x4B00,0x8BC1,0x8A81,0x4A40,
  69.         0x4E00,0x8EC1,0x8F81,0x4F40,0x8D01,0x4DC0,0x4C80,0x8C41,
  70.         0x4400,0x84C1,0x8581,0x4540,0x8701,0x47C0,0x4680,0x8641,
  71.         0x8201,0x42C0,0x4380,0x8341,0x4100,0x81C1,0x8081,0x4040 };
  72.  
  73. void    calcrc(unsigned char ch)
  74. {
  75.     t_crc = (t_crc >> 8 ^ crctbl[(t_crc ^ ch) & 0xff]);
  76. }
  77.  
  78. void    insnode(r,len)
  79. int     r,len;
  80. {
  81.     int     i,cmp;
  82.     unsigned char *key;
  83.     register int p;
  84.  
  85.     cmp = 1;
  86.     key = (unsigned char *)&text_buf[r]; 
  87.     p = N + 1 + key[0];
  88.     rson[r] = lson[r] = NIL; mat_len = 0;
  89.     for ( ; ; ) {
  90.         if ( cmp >= 0 ) {
  91.             if ( rson[p] != NIL )
  92.                 p = rson[p];
  93.             else {
  94.                 rson[p] = r; dad[r] = p;
  95.                 return;
  96.             }
  97.         } else {
  98.             if ( lson[p] != NIL )
  99.                 p = lson[p];
  100.             else {
  101.                 lson[p] = r; dad[r] = p;
  102.                 return;
  103.             }
  104.         }
  105.         for ( i = 1 ; i < len ; i++ ) {
  106.             if ( (cmp = key[i] - (unsigned char)text_buf[p + i]) != 0 )
  107.                 break;
  108.         }
  109.         if ( i > mat_len ) {
  110.             pos = p;
  111.             if ( (mat_len = i) >= len )
  112.                 break;
  113.         }
  114.     }
  115.     dad[r] = dad[p]; lson[r] = lson[p]; rson[r] = rson[p];
  116.     dad[lson[p]] = r; dad[rson[p]] = r;
  117.     if ( rson[dad[p]] == p )
  118.         rson[dad[p]] = r;
  119.     else
  120.         lson[dad[p]] = r;
  121.     dad[p] = NIL;
  122. }
  123. void    delnode(p)
  124. int     p;
  125. {
  126.     int     q;
  127.     register int dad_p;
  128.  
  129.     if ( (dad_p = dad[p]) == NIL )
  130.         return;
  131.     if ( rson[p] == NIL ) {
  132.         if ( rson[dad_p] == p )
  133.             rson[dad_p] = lson[p];
  134.         else
  135.             lson[dad_p] = lson[p];
  136.         dad[lson[p]] = dad_p;
  137.     } else if ( lson[p] == NIL ) {
  138.         if ( rson[dad_p] == p )
  139.             rson[dad_p] = rson[p];
  140.         else
  141.             lson[dad_p] = rson[p];
  142.         dad[rson[p]] = dad_p;
  143.     } else {
  144.         q = lson[p];
  145.         if ( rson[q] != NIL ) {
  146.             do {
  147.                 q = rson[q];
  148.             } while ( rson[q] != NIL );
  149.             rson[dad[q]] = lson[q]; dad[lson[q]] = dad[q];
  150.             lson[q] = lson[p]; dad[lson[p]] = q;
  151.             rson[q] = rson[p]; dad[rson[p]] = q;
  152.         } else {
  153.             rson[q] = rson[p]; dad[rson[p]] = q;
  154.         }
  155.         dad[q] = dad_p;
  156.         if ( rson[dad_p] == p )
  157.             rson[dad_p] = q;
  158.         else
  159.             lson[dad_p] = q;
  160.     }
  161.     dad[p] = NIL;
  162. }
  163. void    Enc_init(fp)
  164. FILE    *fp;
  165. {
  166.     int     i,c;
  167.  
  168.     for ( i = N + 1 ; i <= (N + 256) ; i++ )
  169.         rson[i] = NIL;
  170.     for ( i = 0 ; i < N ; i++ )
  171.         dad[i] = NIL;
  172.     for ( i = 0 ; i < (N - F) ; i++ )
  173.         text_buf[i] = ' ';
  174.  
  175.     bas = dmy_buf;
  176.     ptr = dmy_buf + 1;
  177.     dmy_buf[0] = 0;
  178.     mask = 1;
  179.     now = N- F;
  180.     new = 0;
  181.     t_crc = 0;
  182.  
  183.     for ( len = 0 ; len < F && (c = getc(fp)) != EOF ; len++ ) {
  184.         text_buf[now + len] = c;
  185.     calcrc(c);
  186.     }
  187.     for ( i = 1 ; i <= F ; i++ )
  188.         insnode(now - i,len);
  189.     insnode(now,len);
  190. }
  191. int     Enc_char(fp)
  192. FILE    *fp;
  193. {
  194.     int     i,n,c;
  195.  
  196.     for ( ; ; ) {
  197.         if ( mask >= 0x100 ) {
  198.             if ( bas < ptr )
  199.                 return *(bas++) & 0xFF;
  200.             dmy_buf[0] = 0;
  201.             mask = 1;
  202.             bas = dmy_buf;
  203.             ptr = dmy_buf + 1;
  204.         }
  205.         if ( len <= 0 )
  206.             return EOF;
  207.  
  208.         if ( mat_len <= 2 ) {
  209.             mat_len = 1;
  210.             dmy_buf[0] |= mask;
  211.             *(ptr++) = text_buf[now];
  212.         } else {
  213.             if ( mat_len > len ) mat_len = len;
  214.             *(ptr++) = pos;
  215.             *(ptr++) = (((pos >> 4) & 0xf0) | (mat_len -3));
  216.         }
  217.  
  218.         n = mat_len;
  219.         for ( i = 0 ; i < n &&
  220.                       (c = getc(fp)) != EOF ; i++ ) {
  221.             delnode(new);
  222.             text_buf[new] = c;
  223.             if ( new < (F - 1) )
  224.                 text_buf[new + N] = c;
  225.             new = (new + 1) & (N - 1);
  226.             now = (now + 1) & (N - 1);
  227.             insnode(now,len);
  228.         calcrc(c);
  229.         }
  230.         while ( i++ < n ) {
  231.             delnode(new);
  232.             new = (new + 1) & (N - 1);
  233.             now = (now + 1) & (N - 1);
  234.             if ( --len > 0 )
  235.                 insnode(now,len);
  236.         }
  237.  
  238.         if ( len <= 0 )
  239.             mask = 0x100;
  240.         else
  241.             mask <<= 1;
  242.     }
  243. }
  244.  
  245. #define D_Get_Mask  0
  246. #define D_Get_Char  1
  247. #define D_Get_HiAd  2
  248.  
  249. void    Dec_init()
  250. {
  251.     int     i;
  252.  
  253.     for ( i = 0 ; i < (N - F) ; i++ )
  254.         text_buf[i] = ' ';
  255.     now = N - F;
  256.     mask = 0;
  257.     status = D_Get_Char;
  258.     t_crc = 0;
  259. }
  260. void    Dec_char(ch,fp)
  261. unsigned int ch;
  262. FILE    *fp;
  263. {
  264.     int     n;
  265.  
  266.     ch &= 0xFF;
  267.     switch(status) {
  268.         case D_Get_Char:
  269.             if ( (mask & 0x100) == 0 ) {
  270.                 mask = 0xFF00 | ch;
  271.             } else {
  272.                 if ( mask & 1 ) {
  273.                     putc(ch,fp);
  274.                     text_buf[now++] = ch;
  275.                     now &= (N - 1);
  276.             calcrc(ch);
  277.                 } else {
  278.                     adr = ch;
  279.                     status = D_Get_HiAd;
  280.                 }
  281.                 mask >>= 1;
  282.             }
  283.             break;
  284.         case D_Get_HiAd:
  285.             adr |= ((ch & 0xf0) << 4);
  286.             n = (ch & 0x0f) + 3;
  287.             while ( n-- > 0 ) {
  288.                 ch = text_buf[adr++];
  289.                 adr &= (N - 1);
  290.                 putc(ch,fp);
  291.                 text_buf[now++] = ch;
  292.                 now &= (N - 1);
  293.         calcrc(ch);
  294.             }
  295.             status = D_Get_Char;
  296.             break;
  297.     }
  298. }
  299.  
  300. void    MDec_char(int ch)
  301. {
  302.     int     n;
  303.  
  304.     ch &= 0xFF;
  305.     switch(status) {
  306.         case D_Get_Char:
  307.             if ( (mask & 0x100) == 0 ) {
  308.                 mask = 0xFF00 | ch;
  309.             } else {
  310.                 if ( mask & 1 ) {
  311.                     *(md_ptr++) = ch;
  312.                     text_buf[now++] = ch;
  313.                     now &= (N - 1);
  314.                 } else {
  315.                     adr = ch;
  316.                     status = D_Get_HiAd;
  317.                 }
  318.                 mask >>= 1;
  319.             }
  320.             break;
  321.         case D_Get_HiAd:
  322.             adr |= ((ch & 0xf0) << 4);
  323.             n = (ch & 0x0f) + 3;
  324.             while ( n-- > 0 ) {
  325.                 ch = text_buf[adr++];
  326.                 adr &= (N - 1);
  327.                 *(md_ptr++) = ch;
  328.                 text_buf[now++] = ch;
  329.                 now &= (N - 1);
  330.             }
  331.             status = D_Get_Char;
  332.             break;
  333.     }
  334. }
  335. char    *MEM_lzss(FILE *fp)
  336. {
  337.     int     n,ch;
  338.     char    *p;
  339.     char    tmp[8];
  340.  
  341.     fread(tmp,1,5,fp);
  342.     if ( strncmp(tmp,"LZSS\x1A",5) != 0 ) {
  343.     rewind(fp);
  344.     return NULL;
  345.     }
  346.  
  347.     for ( n = 0 ; n < (N - F) ; n++ )
  348.         text_buf[n] = ' ';
  349.     now = N - F;
  350.     mask = 0;
  351.     status = D_Get_Char;
  352.  
  353.     fread(&n,sizeof(int),1,fp);
  354.     if ( (p = md_ptr = malloc(n)) == NULL )
  355.     return NULL;
  356.  
  357.     while ( (ch = getc(fp)) != EOF && md_ptr < (p + n) )
  358.     MDec_char(ch);
  359.  
  360.     return p;
  361. }
  362. int    COMP_lzss(char *file)
  363. {
  364.     FILE    *ifp,*ofp;
  365.     int     ch,fg,sw=FALSE;
  366.     long    fsz;
  367.     char    *work;
  368.     char    tmp[8];
  369.  
  370.     if ( (ifp = fopen(file,"rb")) == NULL )
  371.     return ERR;
  372.  
  373.     work = mak_work(file);
  374.     if ( (ofp = fopen(work,"wb")) == NULL ) {
  375.     fclose(ifp);
  376.     return ERR;
  377.     }
  378.  
  379.     fread(tmp,1,5,ifp);
  380.     if ( strncmp(tmp,"LZSS\x1A",5) != 0 )
  381.     sw = TRUE;
  382.  
  383.     if ( sw == FALSE ) {
  384.     fseek(ifp,0L,SEEK_END);
  385.     fsz = ftell(ifp);
  386.     rewind(ifp);
  387.  
  388.     fwrite("LZSS\x1A",1,5,ofp);
  389.     fwrite(&fsz,sizeof(long),1,ofp);
  390.  
  391.     Enc_init(ifp);
  392.     while ( (ch = Enc_char(ifp)) != EOF )
  393.         putc(ch,ofp);
  394.  
  395.     } else {
  396.     fread(&fsz,sizeof(long),1,ifp);
  397.  
  398.     Dec_init();
  399.     while ( (ch = getc(ifp)) != EOF )
  400.         Dec_char(ch,ofp);
  401.     }
  402.  
  403.     fg = (ferror(ifp) || ferror(ofp)) ? ERR:FALSE;
  404.  
  405.     fclose(ifp);
  406.     fclose(ofp);
  407.  
  408.     if ( fg != FALSE )
  409.         unlink(work);
  410.     else {
  411.     unlink(file);
  412.     rename(work,file);
  413.     }
  414.  
  415.     return fg;
  416. }
  417.