home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 9 Archive / 09-Archive.zip / ZIP19P1.ZIP / bits.c < prev    next >
C/C++ Source or Header  |  1993-01-23  |  11KB  |  370 lines
  1. /*
  2.  
  3.  Copyright (C) 1990-1992 Mark Adler, Richard B. Wales, Jean-loup Gailly,
  4.  Kai Uwe Rommel and Igor Mandrichenko.
  5.  Permission is granted to any individual or institution to use, copy, or
  6.  redistribute this software so long as all of the original files are included
  7.  unmodified, that it is not sold for profit, and that this copyright notice
  8.  is retained.
  9.  
  10. */
  11.  
  12. /*
  13.  *  bits.c by Jean-loup Gailly and Kai Uwe Rommel.
  14.  *
  15.  *  This is a new version of im_bits.c originally written by Richard B. Wales
  16.  *
  17.  *  PURPOSE
  18.  *
  19.  *      Output variable-length bit strings. Compression can be done
  20.  *      to a file or to memory.
  21.  *
  22.  *  DISCUSSION
  23.  *
  24.  *      The PKZIP "deflate" file format interprets compressed file data
  25.  *      as a sequence of bits.  Multi-bit strings in the file may cross
  26.  *      byte boundaries without restriction.
  27.  *
  28.  *      The first bit of each byte is the low-order bit.
  29.  *
  30.  *      The routines in this file allow a variable-length bit value to
  31.  *      be output right-to-left (useful for literal values). For
  32.  *      left-to-right output (useful for code strings from the tree routines),
  33.  *      the bits must have been reversed first with bi_reverse().
  34.  *
  35.  *      For in-memory compression, the compressed bit stream goes directly
  36.  *      into the requested output buffer. The input data is read in blocks
  37.  *      by the mem_read() function.
  38.  *
  39.  *  INTERFACE
  40.  *
  41.  *      void bi_init (FILE *zipfile)
  42.  *          Initialize the bit string routines.
  43.  *
  44.  *      void send_bits (int value, int length)
  45.  *          Write out a bit string, taking the source bits right to
  46.  *          left.
  47.  *
  48.  *      int bi_reverse (int value, int length)
  49.  *          Reverse the bits of a bit string, taking the source bits left to
  50.  *          right and emitting them right to left.
  51.  *
  52.  *      void bi_windup (void)
  53.  *          Write out any remaining bits in an incomplete byte.
  54.  *
  55.  *      void copy_block(char far *buf, unsigned len, int header)
  56.  *          Copy a stored block to the zip file, storing first the length and
  57.  *          its one's complement if requested.
  58.  *
  59.  *      int seekable(void)
  60.  *          Return true if the zip file can be seeked.
  61.  *
  62.  *      ulg memcompress (char *tgt, ulg tgtsize, char *src, ulg srcsize);
  63.  *          Compress the source buffer src into the target buffer tgt.
  64.  */
  65.  
  66. #include "zip.h"
  67.  
  68. /* ===========================================================================
  69.  * Local data used by the "bit string" routines.
  70.  */
  71.  
  72. local FILE *zfile; /* output zip file */
  73.  
  74. local unsigned short bi_buf;
  75. /* Output buffer. bits are inserted starting at the bottom (least significant
  76.  * bits).
  77.  */
  78.  
  79. #define Buf_size (8 * 2*sizeof(char))
  80. /* Number of bits used within bi_buf. (bi_buf might be implemented on
  81.  * more than 16 bits on some systems.)
  82.  */
  83.  
  84. local int bi_valid;
  85. /* Number of valid bits in bi_buf.  All bits above the last valid bit
  86.  * are always zero.
  87.  */
  88.  
  89. char file_outbuf[1024];
  90. /* Output buffer for compression to file */
  91.  
  92. local char *in_buf, *out_buf;
  93. /* Current input and output buffers. in_buf is used only for in-memory
  94.  * compression.
  95.  */
  96.  
  97. local ulg in_offset, out_offset;
  98. /* Current offset in input and output buffers. in_offset is used only for
  99.  * in-memory compression.
  100.  */
  101.  
  102. local ulg in_size, out_size;
  103. /* Size of current input and output buffers */
  104.  
  105. int (*read_buf) OF((char *buf, unsigned size)) = file_read;
  106. /* Current input function. Set to mem_read for in-memory compression */
  107.  
  108. #ifdef DEBUG
  109. ulg bits_sent;   /* bit length of the compressed data */
  110. #endif
  111.  
  112. /* Output a 16 bit value to the bit stream, lower (oldest) byte first */
  113. #define PUTSHORT(w) \
  114. { if (out_offset < out_size-1) { \
  115.     out_buf[out_offset++] = (char) ((w) & 0xff); \
  116.     out_buf[out_offset++] = (char) ((ush)(w) >> 8); \
  117.   } else { \
  118.     flush_outbuf((w),2); \
  119.   } \
  120. }
  121.  
  122. #define PUTBYTE(b) \
  123. { if (out_offset < out_size) { \
  124.     out_buf[out_offset++] = (char) (b); \
  125.   } else { \
  126.     flush_outbuf((b),1); \
  127.   } \
  128. }
  129.  
  130.  
  131. /* ===========================================================================
  132.  *  Prototypes for local functions
  133.  */
  134. local int  mem_read     OF((char *buf, unsigned size));
  135. local void flush_outbuf OF((unsigned w, unsigned size));
  136.  
  137. /* ===========================================================================
  138.  * Initialize the bit string routines.
  139.  */
  140. void bi_init (zipfile)
  141.     FILE *zipfile;  /* output zip file, NULL for in-memory compression */
  142. {
  143.     zfile  = zipfile;
  144.     bi_buf = 0;
  145.     bi_valid = 0;
  146. #ifdef DEBUG
  147.     bits_sent = 0L;
  148. #endif
  149.  
  150.     /* Set the defaults for file compression. They are set by memcompress
  151.      * for in-memory compression.
  152.      */
  153.     if (zfile != NULL) {
  154.         out_buf = file_outbuf;
  155.         out_size = sizeof(file_outbuf);
  156.         out_offset = 0;
  157.         read_buf  = file_read;
  158.     }
  159. }
  160.  
  161. /* ===========================================================================
  162.  * Send a value on a given number of bits.
  163.  * IN assertion: length <= 16 and value fits in length bits.
  164.  */
  165. void send_bits(value, length)
  166.     int value;  /* value to send */
  167.     int length; /* number of bits */
  168. {
  169. #ifdef DEBUG
  170.     Tracevv((stderr," l %2d v %4x ", length, value));
  171.     Assert(length > 0 && length <= 15, "invalid length");
  172.     bits_sent += (ulg)length;
  173. #endif
  174.     /* If not enough room in bi_buf, use (valid) bits from bi_buf and
  175.      * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid))
  176.      * unused bits in value.
  177.      */
  178.     if (bi_valid > (int)Buf_size - length) {
  179.         bi_buf |= (value << bi_valid);
  180.         PUTSHORT(bi_buf);
  181.         bi_buf = (ush)value >> (Buf_size - bi_valid);
  182.         bi_valid += length - Buf_size;
  183.     } else {
  184.         bi_buf |= value << bi_valid;
  185.         bi_valid += length;
  186.     }
  187. }
  188.  
  189. /* ===========================================================================
  190.  * Reverse the first len bits of a code, using straightforward code (a faster
  191.  * method would use a table)
  192.  * IN assertion: 1 <= len <= 15
  193.  */
  194. unsigned bi_reverse(code, len)
  195.     unsigned code; /* the value to invert */
  196.     int len;       /* its bit length */
  197. {
  198.     register unsigned res = 0;
  199.     do {
  200.         res |= code & 1;
  201.         code >>= 1, res <<= 1;
  202.     } while (--len > 0);
  203.     return res >> 1;
  204. }
  205.  
  206. /* ===========================================================================
  207.  * Flush the current output buffer.
  208.  */
  209. local void flush_outbuf(w, size)
  210.     unsigned w;    /* value to flush */
  211.     unsigned size; /* it size in bytes (0, 1 or 2) */
  212. {
  213.     if (zfile == NULL) {
  214.         error("output buffer too small for in-memory compression");
  215.     }
  216.     /* Encrypt and write the output buffer: */
  217.     if (out_offset != 0) {
  218.         zfwrite(out_buf, 1, (extent)out_offset, zfile);
  219.         if (ferror(zfile)) error ("write error on zip file");
  220.     }
  221.     out_offset = 0;
  222.     if (size == 2) {
  223.         PUTSHORT(w);
  224.     } else if (size == 1) {
  225.         out_buf[out_offset++] = (char) (w & 0xff);
  226.     }
  227. }
  228.  
  229. /* ===========================================================================
  230.  * Write out any remaining bits in an incomplete byte.
  231.  */
  232. void bi_windup()
  233. {
  234.     if (bi_valid > 8) {
  235.         PUTSHORT(bi_buf);
  236.     } else if (bi_valid > 0) {
  237.         PUTBYTE(bi_buf);
  238.     }
  239.     if (zfile != NULL) {
  240.         flush_outbuf(0, 0);
  241.     }
  242.     bi_buf = 0;
  243.     bi_valid = 0;
  244. #ifdef DEBUG
  245.     bits_sent = (bits_sent+7) & ~7;
  246. #endif
  247. }
  248.  
  249. /* ===========================================================================
  250.  * Copy a stored block to the zip file, storing first the length and its
  251.  * one's complement if requested.
  252.  */
  253. void copy_block(buf, len, header)
  254.     char far *buf; /* the input data */
  255.     unsigned len;  /* its length */
  256.     int header;    /* true if block header must be written */
  257. {
  258.     bi_windup();              /* align on byte boundary */
  259.  
  260.     if (header) {
  261.         PUTSHORT((ush)len);   
  262.         PUTSHORT((ush)~len);
  263. #ifdef DEBUG
  264.         bits_sent += 2*16;
  265. #endif
  266.     }
  267.     if (zfile) {
  268.         flush_outbuf(0, 0);
  269.         zfwrite(buf, 1, len, zfile);
  270.         if (ferror(zfile)) error ("write error on zip file");
  271.     } else if (out_offset + (ulg)len > out_size) {
  272.         error("output buffer too small for in-memory compression");
  273.     } else {
  274.         memcpy(out_buf + out_offset, buf, len);
  275.         out_offset += (ulg)len;
  276.     }
  277. #ifdef DEBUG
  278.     bits_sent += (ulg)len<<3;
  279. #endif
  280. }
  281.  
  282.  
  283. /* ===========================================================================
  284.  * Return true if the zip file can be seeked. This is used to check if
  285.  * the local header can be re-rewritten. This function always returns
  286.  * true for in-memory compression.
  287.  * IN assertion: the local header has already been written (ftell() > 0).
  288.  */
  289. int seekable()
  290. {
  291.     return (zfile == NULL ||
  292.             (fseek(zfile, -1L, SEEK_CUR) == 0 &&
  293.              fseek(zfile,  1L, SEEK_CUR) == 0));
  294. }    
  295.  
  296. /* ===========================================================================
  297.  * In-memory compression. This version can be used only if the entire input
  298.  * fits in one memory buffer. The compression is then done in a single
  299.  * call of memcompress(). (An extension to allow repeated calls would be
  300.  * possible but is not needed here.)
  301.  * The first two bytes of the compressed output are set to a short with the
  302.  * method used (DEFLATE or STORE). The following four bytes contain the CRC.
  303.  * The values are stored in little-endian order on all machines.
  304.  * This function returns the byte size of the compressed output, including
  305.  * the first six bytes (method and crc).
  306.  */
  307.  
  308. ulg memcompress(tgt, tgtsize, src, srcsize)
  309.     char *tgt, *src;       /* target and source buffers */
  310.     ulg tgtsize, srcsize;  /* target and source sizes */
  311. {
  312.     ush att      = (ush)UNKNOWN;
  313.     ush flags    = 0;
  314.     ulg crc      = 0;
  315.     int method   = DEFLATE;
  316.  
  317.     if (tgtsize <= 6L) error("target buffer too small");
  318.  
  319.     crc = updcrc((char *)NULL, 0);
  320.     crc = updcrc(src, (extent) srcsize);
  321.  
  322.     read_buf  = mem_read;
  323.     in_buf    = src;
  324.     in_size   = srcsize;
  325.     in_offset = 0;
  326.  
  327.     out_buf    = tgt;
  328.     out_size   = tgtsize;
  329.     out_offset = 2 + 4;
  330.  
  331.     bi_init(NULL);
  332.     ct_init(&att, &method);
  333.     lm_init(level, &flags);
  334.     deflate();
  335.  
  336.     /* For portability, force little-endian order on all machines: */
  337.     tgt[0] = (char)(method & 0xff);
  338.     tgt[1] = (char)((method >> 8) & 0xff);
  339.     tgt[2] = (char)(crc & 0xff);
  340.     tgt[3] = (char)((crc >> 8) & 0xff);
  341.     tgt[4] = (char)((crc >> 16) & 0xff);
  342.     tgt[5] = (char)((crc >> 24) & 0xff);
  343.  
  344.     return out_offset;
  345. }
  346.  
  347. /* ===========================================================================
  348.  * In-memory read function. As opposed to file_read(), this function
  349.  * does not perform end-of-line translation, and does not update the
  350.  * crc and input size.
  351.  *    Note that the size of the entire input buffer is an unsigned long,
  352.  * but the size used in mem_read() is only an unsigned int. This makes a
  353.  * difference on 16 bit machines. mem_read() may be called several
  354.  * times for an in-memory compression.
  355.  */
  356. local int mem_read(buf, size)
  357.      char *buf;
  358.      unsigned size; 
  359. {
  360.     if (in_offset < in_size) {
  361.         ulg block_size = in_size - in_offset;
  362.         if (block_size > (ulg)size) block_size = (ulg)size;
  363.         memcpy(buf, in_buf + in_offset, (unsigned)block_size);
  364.         in_offset += block_size;
  365.         return (int)block_size;
  366.     } else {
  367.         return 0; /* end of input */
  368.     }
  369. }
  370.