Return to bits.c CVS log

Up to [MW Coherent from dump] / coherent / b / bin / zip

Annotation of coherent/b/bin/zip/bits.c, revision 1.1

1.1     ! root        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: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.