text: /* bits.c -- output variable-length bit strings
   * Copyright (C) 1992-1993 Jean-loup Gailly
   * This is free software; you can redistribute it and/or modify it under the
   * terms of the GNU General Public License, see the file COPYING.
   */
  
  
  /*
   *  PURPOSE
   *
   *      Output variable-length bit strings. Compression can be done
   *      to a file or to memory. (The latter is not supported in this version.)
   *
   *  DISCUSSION
   *
   *      The PKZIP "deflate" file format interprets compressed file data
   *      as a sequence of bits.  Multi-bit strings in the file may cross
   *      byte boundaries without restriction.
   *
   *      The first bit of each byte is the low-order bit.
   *
   *      The routines in this file allow a variable-length bit value to
   *      be output right-to-left (useful for literal values). For
   *      left-to-right output (useful for code strings from the tree routines),
   *      the bits must have been reversed first with bi_reverse().
   *
   *      For in-memory compression, the compressed bit stream goes directly
   *      into the requested output buffer. The input data is read in blocks
   *      by the mem_read() function. The buffer is limited to 64K on 16 bit
   *      machines.
   *
   *  INTERFACE
   *
   *      void bi_init (FILE *zipfile)
   *          Initialize the bit string routines.
   *
   *      void send_bits (int value, int length)
   *          Write out a bit string, taking the source bits right to
   *          left.
   *
   *      int bi_reverse (int value, int length)
   *          Reverse the bits of a bit string, taking the source bits left to
   *          right and emitting them right to left.
   *
   *      void bi_windup (void)
   *          Write out any remaining bits in an incomplete byte.
   *
   *      void copy_block(char *buf, unsigned len, int header)
   *          Copy a stored block to the zip file, storing first the length and
   *          its one's complement if requested.
   *
   */
  
  #include "tailor.h"
  #include "gzip.h"
  #include "crypt.h"
  
  #ifdef DEBUG
  #  include <stdio.h>
  #endif
  
  #ifdef RCSID
  static char rcsid[] = "$FreeBSD: src/gnu/usr.bin/gzip/bits.c,v 1.7 1999/08/27 23:35:49 peter Exp $";
  #endif
  
  /* ===========================================================================
   * Local data used by the "bit string" routines.
   */
  
  local file_t zfile; /* output gzip file */
  
  local unsigned short bi_buf;
  /* Output buffer. bits are inserted starting at the bottom (least significant
   * bits).
   */
  
  #define Buf_size (8 * 2*sizeof(char))
  /* Number of bits used within bi_buf. (bi_buf might be implemented on
   * more than 16 bits on some systems.)
   */
  
  local int bi_valid;
  /* Number of valid bits in bi_buf.  All bits above the last valid bit
   * are always zero.
   */
  
  int (*read_buf) OF((char *buf, unsigned size));
  /* Current input function. Set to mem_read for in-memory compression */
  
  #ifdef DEBUG
    ulg bits_sent;   /* bit length of the compressed data */
  #endif
  
  /* ===========================================================================
   * Initialize the bit string routines.
   */
  void bi_init (zipfile)
      file_t zipfile; /* output zip file, NO_FILE for in-memory compression */
  {
      zfile  = zipfile;
      bi_buf = 0;
      bi_valid = 0;
  #ifdef DEBUG
      bits_sent = 0L;
  #endif
  
      /* Set the defaults for file compression. They are set by memcompress
       * for in-memory compression.
       */
      if (zfile != NO_FILE) {
  	read_buf  = file_read;
      }
  }
  
  /* ===========================================================================
   * Send a value on a given number of bits.
   * IN assertion: length <= 16 and value fits in length bits.
   */
  void send_bits(value, length)
      int value;  /* value to send */
      int length; /* number of bits */
  {
  #ifdef DEBUG
      Tracev((stderr," l %2d v %4x ", length, value));
      Assert(length > 0 && length <= 15, "invalid length");
      bits_sent += (ulg)length;
  #endif
      /* If not enough room in bi_buf, use (valid) bits from bi_buf and
       * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid))
       * unused bits in value.
       */
      if (bi_valid > (int)Buf_size - length) {
          bi_buf |= (value << bi_valid);
          put_short(bi_buf);
          bi_buf = (ush)value >> (Buf_size - bi_valid);
          bi_valid += length - Buf_size;
      } else {
          bi_buf |= value << bi_valid;
          bi_valid += length;
      }
  }
  
  /* ===========================================================================
   * Reverse the first len bits of a code, using straightforward code (a faster
   * method would use a table)
   * IN assertion: 1 <= len <= 15
   */
  unsigned bi_reverse(code, len)
      unsigned code; /* the value to invert */
      int len;       /* its bit length */
  {
      register unsigned res = 0;
      do {
          res |= code & 1;
          code >>= 1, res <<= 1;
      } while (--len > 0);
      return res >> 1;
  }
  
  /* ===========================================================================
   * Write out any remaining bits in an incomplete byte.
   */
  void bi_windup()
  {
      if (bi_valid > 8) {
          put_short(bi_buf);
      } else if (bi_valid > 0) {
          put_byte(bi_buf);
      }
      bi_buf = 0;
      bi_valid = 0;
  #ifdef DEBUG
      bits_sent = (bits_sent+7) & ~7;
  #endif
  }
  
  /* ===========================================================================
   * Copy a stored block to the zip file, storing first the length and its
   * one's complement if requested.
   */
  void copy_block(buf, len, header)
      char     *buf;    /* the input data */
      unsigned len;     /* its length */
      int      header;  /* true if block header must be written */
  {
      bi_windup();              /* align on byte boundary */
  
      if (header) {
          put_short((ush)len);
          put_short((ush)~len);
  #ifdef DEBUG
          bits_sent += 2*16;
  #endif
      }
  #ifdef DEBUG
      bits_sent += (ulg)len<<3;
  #endif
      while (len--) {
  #ifdef CRYPT
          int t;
  	if (key) zencode(*buf, t);
  #endif
  	put_byte(*buf++);
      }
  }
  