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.

Example: input bits 01010001 01010001; output 1010001 1010001 which grouped by byte will give: 10100011 01000100. Last bold bits are padding bits.

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 nine (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

Ada

<ada> with Ada.Streams; use Ada.Streams; with Ada.Finalization;

package Bit_Streams is

  type Bit is range 0..1;
  type Bit_Array is array (Positive range <>) of Bit;
  type Bit_Stream (Channel : not null access Root_Stream_Type'Class) is limited private;
  procedure Read (Stream : in out Bit_Stream; Data : out Bit_Array);
  procedure Write (Stream : in out Bit_Stream; Data : Bit_Array);

private

  type Bit_Stream (Channel : not null access Root_Stream_Type'Class) is
     new Ada.Finalization.Limited_Controlled with
  record
     Read_Count  : Natural := 0;
     Write_Count : Natural := 0;
     Input       : Stream_Element_Array (1..1);
     Output      : Stream_Element_Array (1..1);
  end record;
  overriding procedure Finalize (Stream : in out Bit_Stream);

end Bit_Streams; </ada> The package provides a bit stream interface to a conventional stream. The object of Bit_Stream has a discriminant of any stream type. This stream will be used for physical I/O. Bit_Stream reads and writes arrays of bits. There is no need to have flush procedure, because this is done upon object destruction. The implementation is straightforward, big endian encoding is of bits into Stream_Element units is used: <ada> package body Bit_Streams is

  procedure Finalize (Stream : in out Bit_Stream) is
  begin
     if Stream.Write_Count > 0 then
        Stream.Output (1) := Stream.Output (1) * 2**(Stream_Element'Size - Stream.Write_Count);
        Stream.Channel.Write (Stream.Output);
     end if;
  end Finalize;
  procedure Read (Stream : in out Bit_Stream; Data : out Bit_Array) is
     Last : Stream_Element_Offset;
  begin
     for Index in Data'Range loop
        if Stream.Read_Count = 0 then
           Stream.Channel.Read (Stream.Input, Last);
           Stream.Read_Count := Stream_Element'Size;
        end if;
        Data (Index) := Bit (Stream.Input (1) / 2**(Stream_Element'Size - 1));
        Stream.Input (1)  := Stream.Input (1) * 2;
        Stream.Read_Count := Stream.Read_Count - 1;
     end loop;
  end Read;
  procedure Write (Stream : in out Bit_Stream; Data : Bit_Array) is
  begin
     for Index in Data'Range loop
        if Stream.Write_Count = Stream_Element'Size then
           Stream.Channel.Write (Stream.Output);
           Stream.Write_Count := 0;
        end if;
        Stream.Output (1)  := Stream.Output (1) * 2 or Stream_Element (Data (Index));
        Stream.Write_Count := Stream.Write_Count + 1;
     end loop;
  end Write;

end Bit_Streams; </ada> Example of use: <ada> with Ada.Streams.Stream_IO; use Ada.Streams.Stream_IO; with Bit_Streams; use Bit_Streams;

procedure Test_Bit_Streams is

  File   : File_Type;
  ABACUS : Bit_Array :=
              (  1,0,0,0,0,0,1,  -- A, big endian
                 1,0,0,0,0,1,0,  -- B
                 1,0,0,0,0,0,1,  -- A
                 1,0,0,0,0,1,1,  -- C
                 1,0,1,0,1,0,1,  -- U
                 1,0,1,0,0,1,1   -- S 	
              );
  Data : Bit_Array (ABACUS'Range);

begin

  Create (File, Out_File, "abacus.dat");
  declare
     Bits : Bit_Stream (Stream (File));
  begin
     Write (Bits, ABACUS);
  end;
  Close (File);
  Open (File, In_File, "abacus.dat");
  declare
     Bits : Bit_Stream (Stream (File));
  begin
     Read (Bits, Data);
  end;
  Close (File);
  if Data /= ABACUS then
     raise Data_Error;
  end if;

end Test_Bit_Streams; </ada>

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], 7, 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.