Bitwise IO
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 asciiprint "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.
You are encouraged to solve this task according to the task description, using any language you may know.
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
<lang 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; </lang> 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: <lang 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; </lang>
Example of use: <lang 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; </lang>
C
Note: errors handling in this code is experimental!
File: bitio.h
<lang 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
</lang>
File: bitio.c
<lang 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;
} </lang>
Usage example
"Compression" of the ASCII byte standard input stream to the standard output:
<lang 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;
} </lang>
"Decompression" of a 7-bit encoded ASCII stream to a "regular" ASCII byte stream:
<lang 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;
} </lang>
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.
Forth
The stream status is kept on the stack ( b m ), where b is the character accumulator and m is a mask for the current bit. The accumulator is filled with bits starting with the MSB. (The writing code was originally used for Mandelbrot generation.)
<lang forth>\ writing
- init-write ( -- b m ) 0 128 ;
- flush-bits ( b m -- 0 128 ) drop emit init-write ;
- ?flush-bits ( b m -- b' m' ) dup 128 < if flush-bits then ;
- write-bit ( b m f -- b' m' )
if tuck or swap then 2/ dup 0= if flush-bits then ;
\ reading
- init-read ( -- b m ) key 128 ;
- eof? ( b m -- b m f ) dup if false else key? 0= then ;
- read-bit ( b m -- b' m' f )
dup 0= if 2drop init-read then 2dup and swap 2/ swap ;
</lang>
OCaml
The extLib provides bit oriented IO functions.
<lang 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;
</lang>
<lang 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)
</lang>
Perl
<lang perl>#! /usr/bin/perl
use strict;
- $buffer = write_bits(*STDOUT, $buffer, $number, $bits)
sub write_bits( $$$$ ) {
my ($out, $l, $num, $q) = @_;
$l .= substr(unpack("B*", pack("N", $num)),
-$q);
if ( (length($l) > 8) ) {
my $left = substr($l, 8); print $out pack("B8", $l); $l = $left;
} return $l;
}
- flush_bits(*STDOUT, $buffer)
sub flush_bits( $$ ) {
my ($out, $b) = @_;
print $out pack("B*", $b);
}
- ($val, $buf) = read_bits(*STDIN, $buf, $n)
sub read_bits( $$$ ) {
my ( $in, $b, $n ) = @_;
# we put a limit in the number of bits we can read
# with one shot; this should mirror the limit of the max
# integer value perl can hold
if ( $n > 32 ) { return 0; }
while ( length($b) < $n ) {
my $v; my $red = read($in, $v, 1); if ( $red < 1 ) { return ( 0, -1 ); } $b .= substr(unpack("B*", $v), -8);
}
my $bits = "0" x ( 32-$n ) . substr($b, 0, $n);
my $val = unpack("N", pack("B32", $bits));
$b = substr($b, $n);
return ($val, $b);
}</lang>
Crunching bytes discarding most significant bit (lossless compression for ASCII and few more!)
<lang perl>my $buf = ""; my $c; while( read(*STDIN, $c, 1) > 0 ) {
$buf = write_bits(*STDOUT, $buf, unpack("C1", $c), 7);
} flush_bits(*STDOUT, $buf);</lang>
Expanding each seven bits to fit a byte (padding the eight most significant bit with 0):
<lang perl>my $buf = ""; my $v; while(1) {
( $v, $buf ) = read_bits(*STDIN, $buf, 7);
last if ($buf < 0);
print pack("C1", $v);
}</lang>
Python
The module file bitio.py
<lang python>class BitWriter:
def __init__(self, f):
self.accumulator = 0
self.bcount = 0
self.out = f
def __del__(self):
self.flush()
def writebit(self, bit):
if self.bcount == 8 :
self.flush()
if bit > 0:
self.accumulator |= (1 << (7-self.bcount))
self.bcount += 1
def writebits(self, bits, n):
while n > 0:
self.writebit( bits & (1 << (n-1)) )
n -= 1
def flush(self):
self.out.write(chr(self.accumulator))
self.accumulator = 0
self.bcount = 0
class BitReader:
def __init__(self, f):
self.input = f
self.accumulator = 0
self.bcount = 0
self.read = 0
def readbit(self):
if self.bcount == 0 :
a = self.input.read(1)
if ( len(a) > 0 ):
self.accumulator = ord(a)
self.bcount = 8
self.read = len(a)
rv = ( self.accumulator & ( 1 << (self.bcount-1) ) ) >> (self.bcount-1)
self.bcount -= 1
return rv
def readbits(self, n):
v = 0
while n > 0:
v = (v << 1) | self.readbit()
n -= 1
return v</lang>
Usage example to "crunch" an 8-bit byte ASCII stream discarding the most significative "unused" bit...
<lang python>#! /usr/bin/env python import sys import bitio
o = bitio.BitWriter(sys.stdout) c = sys.stdin.read(1) while len(c) > 0:
o.writebits(ord(c), 7) c = sys.stdin.read(1)</lang>
... and to "decrunch" the same stream:
<lang python>#! /usr/bin/env python import sys import bitio
r = bitio.BitReader(sys.stdin) while True:
x = r.readbits(7)
if ( r.read == 0 ):
break
sys.stdout.write(chr(x))</lang>