Bitwise IO

Bitwise IO
You are encouraged to solve this task according to the task description, using any language you may know.

The aim of this task is to write functions (or create a class if your language is OO and you prefer) for reading and writing sequences of bits rather than single bytes.

As test, it is requested you use the write functions to output an ASCII bytes sequence (string) as 7-bits (not 7-bits packed into a 8-bit byte: you must write exactly 7-bits) and then use the read functions to read 7 bits per time and write the output padding the 8th bit with a 0 bit.

Be sure to provide a function to flush buffers when writing (since at the end real writing is done byte-quantized). Since reading procedes, so to say, from left to right, be sure that the significative bits of the last written (maybe incomplete) byte are left-aligned (pad with 0s).

Limits in the maximum number of bits that can be written/read in a single read/write operation are allowed.

These bit oriented I/O functions can be used to implement compressors and decompressors; e.g. Dynamic and Static Huffman encodings use variable length bits sequences, while LZW (see LZW compression) use fixed words eleven (or more) bits long (normally it is possible to dynamically increase the word length when the dictionary is full, up to a limit beyond which it is not convenient to do so)

• Errors handling is not mandatory

C

Note: errors handling in this code is experimental!

File: bitio.h

<c>#ifndef _BIT_IO_H

1. define _BIT_IO_H

1. include <stdio.h>

1. define BITS_PER_BYTE 8

void bits_flush(FILE *o); int bits_write(unsigned int d, int n, FILE *o); int bits_read(unsigned int *d, int n, FILE *o); int bits_getlast(unsigned int *d);

1. define BITERR_BITUNDERFLOW 1
2. define BITERR_BITOVERFLOW 2
3. define BITERR_NOERR 0

extern int biterr;

1. endif</c>

File: bitio.c

<c>#include "bitio.h"

int biterr;

static unsigned char bitbuf=0; static unsigned int cumulus=0; const static unsigned int sochar = sizeof(unsigned char)*BITS_PER_BYTE; const static unsigned int soint = sizeof(unsigned int)*BITS_PER_BYTE;

static unsigned char rbitbuf=0; static unsigned char rfree = 0;

static int read_bit(unsigned int *d, FILE *o) {

  int c;
  
  if ( rfree == 0 )
  {
     c = fgetc(o);
     if ( c == EOF )
     {
        biterr = BITERR_BITUNDERFLOW;
        return EOF;
     }
     rfree = sochar;
     rbitbuf = c;
  }
  
  *d <<= 1;
  *d |= ( rbitbuf >> (sochar - 1 ) ) & 1;
  rbitbuf <<= 1;
  rfree--;
  return 1;

}

static int appendbit(unsigned int d, FILE *o) {

  if ( cumulus == sochar )
  {
     fprintf(o, "%c", (unsigned int)bitbuf);
     cumulus = 0; bitbuf = 0;
  }
  bitbuf <<= 1;
  d &= 1 << (soint - 1);
  d >>= (soint - 1);
  bitbuf |= (d&1);
  cumulus++;
  return 1;

}

void bits_flush(FILE *o) {

  bitbuf <<= (sochar - cumulus);
  fprintf(o, "%c", bitbuf);
  fflush(o);
  cumulus = 0; bitbuf = 0;

}

int bits_read(unsigned int *d, int n, FILE *o) {

  int rbit = 0;
  int rv;
  
  biterr = BITERR_NOERR;
  if ( n > soint ) { biterr = BITERR_BITOVERFLOW; return EOF; }
  while ( n-- > 0 )
  {
     rv = read_bit(d, o);
     if ( rv == EOF ) return EOF; /* return rv; ? */
     rbit += rv;
  }
  return rbit;

}

int bits_getlast(unsigned int *d) {

 *d <<= (sochar - rfree);
 *d |= rbitbuf >> rfree;
 rbitbuf = 0;
 rfree = 0;
 return (sochar - rfree);

}

int bits_write(unsigned int d, int n, FILE *o) {

  unsigned int dpad;
  int wbit=0;
  
  if ( n > soint ) return -1;
  dpad = d << (soint - n);
  while( n-- > 0)
  {
     wbit += appendbit(dpad, o);
     dpad <<= 1;
  }
  return wbit;

}</c>

Usage example

File: bitwrite.c, which write the word ABACUS as 7-bit per byte sequence.

<c>#include <stdio.h>

1. include <stdlib.h>
2. include "bitio.h"

const char *s = "ABACUS";

int main() {

  int i;
  for(i=0; s[i] != 0; i++)
  {
     bits_write(s[i]>>4, 3, stdout);
     bits_write(s[i], 4, stdout);
  }
  bits_flush(stdout);
  return 0;

}</c>

File: bitread.c, which read 7-bits per time and write the group as a byte.

<c>#include <stdio.h>

1. include <stdlib.h>
2. include "bitio.h"

unsigned int db=0;

int main() {

  while( bits_read(&db, 7, stdin) != EOF )
  {
     printf("%c", db & 0x7f);
  }
  return 0;

}</c>

Feeding bitread with the output of bitwrite, the output to console is simply ABACUS.