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 Object Oriented and you prefer) for reading and writing sequences of bits. While the output of a print "STRING" is the ASCII byte sequence "S", "T", "R", "I", "N", "G", the output of a "print" of the bits sequence 0101011101010 (13 bits) must be 0101011101010; real I/O is performed always quantized by byte (avoiding endianness issues and relying on underlying buffering for performance), therefore you must obtain as output the bytes 0101 0111 0101 0000 (bold bits are padding bits), i.e. in hexadecimal 57 50.
As test, you can implement a rough (e.g. don't care about error handling or other issues) compression/decompression program for ASCII sequences of bytes, i.e. bytes for which the most significant bit is always unused, so that you can write seven bits instead of eight (each 8 bytes of input, we write 7 bytes of output).
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.
- Limits in the maximum number of bits that can be written/read in a single read/write operation are allowed.
- 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 of bits into Stream_Element units is used as required by the task: <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
- define _BIT_IO_H
- include <stdio.h>
- 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);
- define BITERR_BITUNDERFLOW 1
- define BITERR_BITOVERFLOW 2
- define BITERR_NOERR 0
extern int biterr;
- 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
"Compression" of the ASCII byte standard input stream to the standard output:
<c>#include <stdio.h>
- include <stdlib.h>
- include "bitio.h"
int main() {
int rbyte;
while( (rbyte=getchar()) != EOF )
{
bits_write(rbyte, 7, stdout);
}
bits_flush(stdout);
return 0;
}</c>
"Decompression" of a 7-bit encoded ASCII stream to a "regular" ASCII byte stream:
<c>#include <stdio.h>
- include <stdlib.h>
- include "bitio.h"
int main() {
unsigned int r=0;
while( bits_read(&r, 7, stdin) != EOF )
{
printf("%c", r&0x7f);
}
return 0;
}</c>
In some circumstances, the previous code could give an extra spurious byte; it happens when the original uncompressed input stream length (in byte) is 7 (mod 8); in this case, the last byte of the compressed stream contains only one "real" bit, the other 7 bits are just for padding. But the decompressor has no way to know this, and so it outputs the last 7 bits as they were "real", "expanding" them into a (spurious) byte.
OCaml
The extLib provides bit oriented IO functions.
<ocaml>let write_7bit_string ~filename ~str =
let oc = open_out filename in let ob = IO.output_bits(IO.output_channel oc) in String.iter (fun c -> IO.write_bits ob 7 (int_of_char c)) str; IO.flush_bits ob; close_out oc;
- </ocaml>
<ocaml>let read_7bit_string ~filename =
let ic = open_in filename in let ib = IO.input_bits(IO.input_channel ic) in let buf = Buffer.create 2048 in try while true do let c = IO.read_bits ib 7 in Buffer.add_char buf c; with End_of_file -> (Buffer.contents buf)</ocaml>