home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_100 / 103_01 / pack.c < prev    next >
Text File  |  1985-03-10  |  13KB  |  448 lines
  1. /* 18 MAY 81    midnight */
  2. #include "BDSCIO.H"
  3.  
  4. #define        DEBUG        (debug != 0)
  5. int debug;
  6.  
  7. #define     TREEDONE    0
  8. #define        NOT_DONE    -1
  9. #define        HUGE_NO        30000
  10. #define        NUM_CH_TYPES    256
  11. #define        NREAD        4
  12. #define        NELEM        NUM_CH_TYPES*2
  13. #define        NUMSECS        8
  14. #define        ELEMSIZ        8
  15. #define        READ        0
  16. #define        WRITE        1
  17. #define        BOTH        2
  18. #define        NIL        -1    /* nil pointer */
  19. #define        NUL        '\0'
  20. #define        OUTCHAR        '>'
  21.  
  22. int STACK[50];
  23. int *SP;
  24. int OUTBYTE;
  25. int COUNTER;
  26. int BIT;
  27. int C;   /* general purpose to speed things */
  28. int BYTE_DONE;
  29.  
  30. struct ELEMENT 
  31.       { int occur;
  32.     int dad;
  33.     int son_zero;
  34.     int son_one;
  35.       }    tree [NELEM+100];
  36.  
  37. main(argc, argv)
  38. int argc;
  39. char **argv;
  40. {
  41. char tempfile[20], infile [20], outfile [20], s[100];
  42. char arg[30];
  43. int big_daddy;
  44. int i, j;
  45. int nsectors;    /* no. sectors in input file */
  46. int outsecs;    /* no. sectors after encoding file */
  47. int z;
  48.  
  49. debug = FALSE;
  50.  
  51. if (argc == 1)
  52.       { puts("\nThis program compresses a file into an encoded form,");
  53.     puts("\nfor more efficient storage. To 'unpack' and get the");
  54.     puts("\noriginal file back, use UNPACK.COM.");
  55.     puts("\nFormat:        A>pack    infile");
  56.     puts("\n    or        A>pack    infile>outfile");
  57.     puts("\ndefault outfile name is infile.PAK");
  58.     exit();
  59.       }
  60.  
  61. strcpy (tempfile, "TEMPCODE.$$$");
  62. infile[0] = outfile[0] = NUL;
  63. while (--argc > 0)
  64.       { strcpy (arg, *++argv);
  65.     if (OK == strcmp (arg, "-D"))
  66.           { debug = TRUE;
  67.         continue;
  68.           }
  69.  
  70.     if (ERROR != (j = find_char (arg, OUTCHAR)))
  71.           { if (j==0 || j== strlen(arg)-1 )
  72.               { puts("\nNO spaces allowed around output specifier");
  73.             printf("\n%s    is illegal.", arg);
  74.             continue;
  75.               }
  76.         else
  77.               sscanf (arg, "%s>%s", infile, outfile);
  78.           }
  79.     else
  80.           { strcpy (infile, arg);
  81.         if (ERROR != (j = find_char (arg,'.')))
  82.               { for (i=0; i<j; i++)
  83.                 outfile[i] = arg[i];
  84.             outfile[j] = NUL;
  85.               }
  86.         else strcpy (outfile, arg);
  87.         strcat (outfile, ".PAK");
  88.           }
  89.  
  90.     if (ERROR != (j = find_char (outfile,':')))
  91.           {    for (i=0; i<j+1; i++)
  92.             tempfile[i]=outfile[i];
  93.         tempfile[j+1] = NUL;
  94.         strcat(tempfile,"TEMPCODE.$$$");
  95.           }
  96.     if DEBUG printf("\ninfile = <%s>, outfile = <%s>",
  97.                infile,        outfile);
  98.     setmem (tree, NELEM*ELEMSIZ, NIL); /* set all to NIL */
  99.     for (i=0; i<NUM_CH_TYPES*2; i++)    tree[i].occur = 0;
  100.     if (ERROR == (nsectors =  count_occur (infile)))
  101.           { printf("\ncan't construct char. occur. table for <%s>",
  102.                                   infile);
  103.         continue;
  104.           }
  105.     if DEBUG printf("\nnsectors = %d", nsectors);
  106.     big_daddy = generate_tree ();
  107. if DEBUG
  108.       { printf("\nbig_daddy = %d",big_daddy);
  109.     printf("\n\nAnd here's the tree:\n\n");
  110.     puts ("\nHIT AN N TO KILL THIS\n");
  111.     for (z=0; z<NELEM; z++)
  112.         if (tree[z].dad!=NIL || tree[z].occur!=0)
  113.         printf("\n%d    0x%x    %d    %d    %d    %d",z,z,tree[z].occur,tree[z].dad,tree[z].son_one,tree[z].son_zero);
  114.       }
  115.     if (OK != write_occur (tempfile))
  116.           { printf("\nerror writing occurence info to <%s>",tempfile);
  117.         puts ("\nI can't pack this file");
  118.         continue;
  119.           }
  120.     if (OK != set_zero_one (tree))
  121.           { printf("\ncan't pack <%s>",infile);
  122.         continue;
  123.           }
  124.     if (ERROR == (outsecs = encode_file(infile, tempfile,nsectors)))
  125.           { printf("\nerror encoding <%s>", infile);
  126.         continue;
  127.           }
  128.     outsecs+=4;    /* this is for the occurrence info */
  129.     printf("\n%d sectors in <%s>;    %d sectors in <%s>",
  130.         nsectors, infile, outsecs, outfile);
  131.     printf("\nPercent savings is %d",
  132.             (100*(nsectors-outsecs))/nsectors);
  133.     if ( outsecs >= nsectors)
  134.           { printf("\nno savings in packing <%s>",infile);
  135.         unlink (tempfile);
  136.         continue;
  137.           }
  138.     else if (ERROR != open (outfile,READ))
  139.           { printf("\n<%s> already exists",outfile);
  140.         printf("\nShould I erase? (Y/N)");
  141.         if ('Y' != toupper (getchar()))        exit();
  142.         unlink (outfile);
  143.           }
  144.     rename (tempfile, outfile);
  145.     printf("\nencoded form of <%s> is in <%s>", infile, outfile);
  146.       }
  147.  
  148. }
  149.  
  150. /********************************************************************
  151. count # of occurenceds of each character in infile, storing values in
  152. tree structure; return total number sectors in infile, or ERROR
  153. ********************************************************************/
  154. int count_occur (infile)
  155. char *infile;
  156. /*    struct ELEMENT tree[];     is global now */
  157. {
  158. char charbuf [NREAD * SECSIZ];
  159. char *string;
  160. int i, fd, k;
  161. /* int c;   c is global */
  162. int nread, nsectors;
  163.  
  164. k=0;
  165. string=
  166. "zzzz ?snore zzzzzzbuzz click zot foo baz help! forp sniggledorp foobar fripnozzle blod yippeezoo this is a big file WOW\7";
  167.  
  168. if (ERROR == (fd = open (infile, READ)))
  169.       { printf("\nerror opening <%s> in count_occur", infile);
  170.     return (ERROR);
  171.       }
  172.  
  173. printf("<%s>\nand now we pause for station identification\nw",infile);
  174. nsectors = 0;
  175. nread = NREAD;
  176. while (nread == NREAD)
  177.       { setmem (charbuf, NREAD*SECSIZ, NUL);
  178.     nread = read(fd, charbuf, NREAD);
  179.     if (nread==ERROR) {printf("error in count char"); return ERROR;}
  180.     printf("%c",string[k++]);
  181.     if (k>= strlen (string))    k=0;
  182.     nsectors+=nread;
  183.     if DEBUG printf("\n\tnsectors=%d,     nread=%d",
  184.                  nsectors,        nread);
  185.     for (i=0; i < nread*SECSIZ; i++)
  186.           {    if (tree[charbuf[i]].occur++ >30000)
  187.             printf("oi chi wah wah");
  188.           }
  189.  
  190.       }
  191. return (nsectors);
  192. }
  193. /********************************************************************
  194. Generate the tree (backwards) that will be used to encode the file
  195. ********************************************************************/
  196. generate_tree ()
  197. /* struct ELEMENT tree[];  is now global */
  198. {
  199. int daddy, zero, one;
  200. int i, val, nextpapa;
  201.  
  202. daddy = NIL;
  203. nextpapa = NUM_CH_TYPES;
  204. puts("\nnow just be patient, this takes a while....");
  205. while (1)
  206.       { find_lowest ( &one, &zero);
  207.     if (one == NIL && zero == NIL)
  208.         return (daddy);        /* all done; even # char's */
  209.     else if (one == NIL)
  210.         return (zero);        /* all done; odd # chars   */
  211.  
  212.     if ( !(nextpapa%3))    putchar('z');
  213.     daddy = nextpapa++;
  214.     tree[daddy].son_zero = zero;
  215.     tree[daddy].son_one  = one ;
  216.     tree[daddy].occur = tree[zero].occur + tree[one].occur;
  217.     tree[zero].dad = daddy;
  218.     tree[one].dad = daddy;
  219.       }
  220.  
  221. return (daddy);
  222. }
  223.  
  224. /*******************************************************************
  225.     find the two elements with the lowest no. of occurences
  226.     in the file who don't have a daddy yet
  227. *********************************************************************/
  228. int find_lowest (low1, low0)
  229. /* struct ELEMENT tree[];   now global */
  230. int *low1, *low0;
  231. {
  232. int i, l0, l1;
  233. int l0_val, l1_val;
  234.  
  235. l0 = l1 = NIL;
  236. l0_val = l1_val = HUGE_NO;
  237. for (i=0; i<NUM_CH_TYPES*2; i++)
  238.       {
  239.     if ((tree[i].dad == NIL) && (tree[i].occur!=0))
  240.           {
  241.         if (tree[i].occur<l1_val && !(tree[i].occur<l0_val))
  242.               { l1_val = tree[i].occur;
  243.             l1 = i;
  244.               }
  245.         else if (tree[i].occur < l0_val)
  246.               { l1_val = l0_val;
  247.             l0_val = tree[i].occur;
  248.             l1 = l0;
  249.             l0 = i;
  250.               }
  251.           }
  252.       }
  253. *low1 = l1;
  254. *low0 = l0;
  255. }
  256.  
  257. /**********************************************************************
  258.         find character c in string
  259. **********************************************************************/
  260. int find_char (string, c)
  261. char *string, c;
  262. {
  263. char *ptr;
  264. int i;
  265.  
  266. for (i=0; string[i] != NUL; i++)
  267.     if (string[i] == c)    return (i);
  268.  
  269. return (ERROR);
  270. }
  271.  
  272. /********************************************************************
  273.  sets tree[].occur at each active element to 1 or 0 depending  on 
  274.  whether its dad says it's a son_one or a son_zero
  275. *********************************************************************/
  276. int set_zero_one ()
  277. /* struct ELEMENT tree[]; now global */
  278. {
  279. int i, daddy;
  280.  
  281. for (i=0; i<NELEM; i++)
  282.       { if (tree[i].dad == NIL)
  283.         continue;
  284.  
  285.     daddy = tree[i].dad;
  286.     if (tree[daddy].son_zero == i)
  287.         tree[i].occur = 0;
  288.     else if (tree[daddy].son_one == i)
  289.         tree[i].occur = -1;    /* -1 to be used when encoding */
  290.     else
  291.           { printf("\nelement #%d = %c does not ackowledge #%d = %c to be its son",
  292.              daddy, daddy,                i, i);
  293.  
  294.         return (ERROR);
  295.           }
  296.       }
  297. return (OK);
  298. }
  299.  
  300. /****************************************************************
  301.  write out the character occurrence information to tempfile before
  302.  packing the file
  303. *****************************************************************/
  304. int write_occur (tempfile)
  305. char *tempfile;
  306. /* struct ELEMENT tree[];  now global */
  307. {
  308. int fd, *ip;
  309. int i;
  310. char outbuf [4*SECSIZ]; /* info takes up 256*2 bytes = 4 sectors  */
  311.  
  312. if (ERROR == (fd = creat(tempfile)))
  313.       { printf("\nerror can not create <%s>",tempfile);
  314.     return (ERROR);
  315.       }
  316. ip = outbuf;
  317. for (i=0; i<NUM_CH_TYPES; i++)
  318.     *ip++ = tree[i].occur;
  319. if (4 != write (fd, outbuf, 4))
  320.       { printf("\nerror writing occur. info to <%s>", tempfile);
  321.     return (ERROR);
  322.       }
  323. if (ERROR == close (fd))
  324.       { printf("\nerror closing <%s> after writing occur. info",
  325.                             tempfile);
  326.     return (ERROR);
  327.       }
  328. return (OK);
  329. }
  330. /*******************************************************************
  331. Encodes the file.  A bit code for each char is generated by starting 
  332. at that char's element in the tree and following the pointers from it
  333. up to the "big-daddy" of the tree, picking off the occur fields of
  334. each element passed on the way. This is the bit code, backwards. 
  335. encode_file    expects that the occur field of each element will have 
  336. been cleared to  0  if it is a son_zero, or set to -1  if it is a
  337. son_one.
  338. Returns -1 on error, or the number of sectors in the ouput file
  339. ********************************************************************/
  340. int encode_file (infile, tempfile, nsectors)
  341. char *infile, *tempfile;
  342. /* struct ELEMENT tree[]; now global */
  343. int nsectors;
  344. {
  345. char inbuf [SECSIZ*NUMSECS], tbuf [SECSIZ*NUMSECS];
  346. int i, j, k, l;
  347. int pi, pt, fd, tfd;
  348. /* int C;         note-- these two have been made global for speed
  349. int BYTE_DONE;     TRUE when have just finished another
  350.                byte of encoded output file */
  351. int sec_finished;    /* TRUE when have just finished another
  352.                sector of encoded ouput file */
  353. int outsecs;        /* number of sectors in output file */
  354. int secsread;        /* number of sectors actually read */
  355. int done;        /* says whether were almost done */
  356.  
  357. if (ERROR == (fd = open (infile, READ)))
  358.       { printf("\nencode_file: can't open <%s> for reading", infile);
  359.     return (ERROR);
  360.       }
  361. else if (ERROR == (tfd = open (tempfile, BOTH)))
  362.       { printf("\nencode_file: can't open <%s> for writing",tempfile);
  363.     close (fd);
  364.     return (ERROR);
  365.       }
  366. pt = 0;    /* index into output buffer */
  367. sec_finished = FALSE;
  368. outsecs = 0;
  369. OUTBYTE = 0;    /* "buffer" for each encoded byte to output buffer */
  370. COUNTER = 128;
  371. SP = STACK;
  372. j=0;
  373.  
  374. seek(tfd,3,0);
  375. read(tfd,tbuf,1);    /* this is so we are poised to write */
  376. tbuf [pt++] = nsectors/256;    /* store length of un-encoded file */
  377. tbuf [pt++] = nsectors%256;    /* store length of un-encoded file */
  378. printf("\nSectors done on <%s>", infile);
  379.  
  380. done=FALSE;
  381. while (!done && ERROR != (secsread= read (fd, inbuf, NUMSECS))) /* get it in */
  382.       {    if (secsread!=NUMSECS) done=TRUE;
  383.     sec_finished = FALSE;
  384.         for (pi=0; pi<SECSIZ*secsread; pi++)    /* for (all chars in buffer) */
  385.           { C = inbuf[pi];
  386.         if (!(pi%SECSIZ)) printf("."); /* another sector */
  387.         if DEBUG printf("\n-------------------\n0x%x\n",C);
  388.  
  389.         /* get the bit pattern code into STACK */
  390.         do
  391.               { *SP++ = tree[C].occur;
  392.             C = tree[C].dad;
  393.               } while ( NIL != tree[C].dad );
  394.  
  395.  
  396.     /* Stuff the bit code into the output buffer. Each element in
  397.        the array STACK rep's a bit; one-bits were set to neg. one's
  398.        previously. COUNTER starts at 128 and is divided by two each
  399.        time to shift its bit pattern right one place each time;
  400.        ANDing this with BIT will set or clear the appropriate bit
  401.        position */
  402.  
  403.         do
  404.               { BIT = *--SP;
  405.         /*    if DEBUG printf("%d ",(BIT==-1)?1:0);    */
  406.             BYTE_DONE = FALSE;
  407.             OUTBYTE |= (BIT & COUNTER);
  408.             COUNTER /=2;
  409.             if (COUNTER == 0)    /* eight bits done */
  410.                   { COUNTER = 128;
  411.                 BYTE_DONE = TRUE;
  412.                 tbuf [pt++] = OUTBYTE;
  413.                 OUTBYTE = 0;
  414.                 if (pt == SECSIZ*NUMSECS)
  415.                       { if (NUMSECS != write (tfd, tbuf, NUMSECS))
  416.                           { printf("\nerror writing to <%s> in encode_file",tempfile);
  417.                             close (tfd);
  418.                         close (fd);
  419.                         return (ERROR);
  420.                           }
  421.                      pt = 0;
  422.                     sec_finished = TRUE;
  423.                     outsecs+=NUMSECS;
  424.                       }
  425.                   }
  426.               } while (SP != STACK);
  427.           }    /* end for ( all chars in input buffer ) */
  428.       }    /* end while ( there are more sectors....) */
  429. if (BYTE_DONE != TRUE)
  430.       { tbuf[pt++] = OUTBYTE;
  431.     sec_finished = FALSE;
  432.       }
  433. if (sec_finished != TRUE)
  434.       { if ((pt/SECSIZ)+1 != write(tfd, tbuf, (pt/SECSIZ)+1))
  435.     printf("\nerr writing to <%s> at end of encode_file",tempfile);
  436.     outsecs+=pt/SECSIZ+1;
  437.       }
  438.  
  439. if (ERROR == close (tfd))
  440.       { printf("\nencode_file: error closing <%s>",tempfile);
  441.     close (fd);
  442.     return (ERROR);
  443.       }
  444. close (fd);
  445.  
  446. return (outsecs);
  447. }
  448. ("\nencode_file: error closin