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 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.
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.
C#
<lang csharp>using System; using System.IO;
public class BitReader {
uint readData = 0; int startPosition = 0; int endPosition = 0;
public int InBuffer
{
get { return endPosition - startPosition; }
}
private Stream stream;
public Stream BaseStream
{
get { return stream; }
}
public BitReader(Stream stream)
{
this.stream = stream;
}
void EnsureData(int bitCount)
{
int readBits = bitCount - InBuffer;
while (readBits > 0)
{
int b = BaseStream.ReadByte();
if (b < 0) throw new InvalidOperationException("Unexpected end of stream");
readData |= checked((uint)b << endPosition);
endPosition += 8;
readBits -= 8;
}
}
public bool ReadBit()
{
return Read(1) > 0;
}
public int Read(int bitCount)
{
EnsureData(bitCount);
int result = (int)(readData >> startPosition) & ((1 << bitCount) - 1);
startPosition += bitCount;
if (endPosition == startPosition)
{
endPosition = startPosition = 0;
readData = 0;
}
else if (startPosition >= 8)
{
readData >>= startPosition;
endPosition -= startPosition;
startPosition = 0;
}
return result; }
public void Align()
{
endPosition = startPosition = 0;
readData = 0;
}
}
public class BitWriter {
uint data = 0; int dataLength = 0; Stream stream;
public Stream BaseStream
{
get { return stream; }
}
public int BitsToAligment
{
get { return (32 - dataLength) % 8; }
}
public BitWriter(Stream stream)
{
this.stream = stream;
}
public void WriteBit(bool value)
{
Write(value ? 1 : 0, 1);
}
public void Write(int value, int length)
{
uint currentData = data | checked((uint)value << dataLength);
int currentLength = dataLength + length;
while (currentLength >= 8)
{
BaseStream.WriteByte((byte)currentData);
currentData >>= 8;
currentLength -= 8;
}
data = currentData;
dataLength = currentLength;
}
public void Align()
{
if (dataLength > 0)
{
BaseStream.WriteByte((byte)data);
data = 0;
dataLength = 0;
}
}
}
class Program {
static void Main(string[] args)
{
MemoryStream ms = new MemoryStream();
BitWriter writer = new BitWriter(ms);
writer.WriteBit(true);
writer.Write(5, 3);
writer.Write(0x0155, 11);
writer.Align();
ms.Position = 0;
BitReader reader = new BitReader(ms);
Console.WriteLine(reader.ReadBit());
Console.WriteLine(reader.Read(3));
Console.WriteLine(reader.Read(11).ToString("x4"));
reader.Align();
}
}</lang>
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>
Haskell
<lang haskell>import Data.List import Data.Char import System.Environment
int2bin :: Int -> [Int] int2bin = unfoldr(\x -> if x==0 then Nothing
else Just (uncurry(flip(,)) (divMod x 2)))
bin2int :: [Int] -> Int bin2int = foldr ((.(2 *)).(+)) 0
bitReader = map (chr.bin2int). takeWhile(not.null). unfoldr(Just. splitAt 7)
. (take =<< (7 *) . (`div` 7) . length)
bitWriter xs = tt ++ z00 where
tt = concatMap (take 7.(++repeat 0).int2bin.ord) xs z00 = replicate (length xs `mod` 8) 0
main = do
(xs:_) <- getArgs let bits = bitWriter xs
putStrLn "Text to compress:" putStrLn $ '\t' : xs putStrLn $ "Uncompressed text length is " ++ show (length xs) putStrLn $ "Compressed text has " ++ show (length bits `div` 8) ++ " bytes." putStrLn "Read and decompress:" putStrLn $ '\t' : bitReader bits</lang>
- 7-bits code has lsb leading.
*Main> :main ["This text is used to illustrate the Rosetta Code task 'bit oriented IO'."]
Text to compress:
This text is used to illustrate the Rosetta Code task 'bit oriented IO'.
Uncompressed text length is 72
Compressed text has 63 bytes.
Read and decompress:
This text is used to illustrate the Rosetta Code task 'bit oriented IO'.
J
Solution <lang j>bitReader =: a. {~ _7 #.\ ({.~ <.&.(%&7)@#) bitWriter =: , @ ((7$2) & #: @ (a.&i.)), 0 $~ 8 | #</lang>
Usage
Do and undo bit oriented IO: <lang j>text=: 'This text is used to illustrate the Rosetta Code task about bit oriented IO.'
bitReader bitWriter text
This text is used to illustrate the Rosetta Code task about 'bit oriented IO'.</lang> Original text length: <lang j> # text 78</lang> Compressed length: <lang j> %&8 # bitWriter text 69</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 (char_of_int c); done; "" with IO.No_more_input -> (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>
Ruby
<lang ruby>def crunch(ascii)
bitstring = ascii.bytes.inject("") {|s, b| s << "%07d" % b.to_s(2)}
[bitstring].pack("B*")
end
def expand(binary)
bitstring = binary.unpack("B*")[0]
bitstring.scan(/[01]{7}/).inject("") {|s, b| s << Integer("0b#{b}").chr}
end
original = "This is an ascii string that will be crunched, written, read and expanded." puts "my ascii string is #{original.length} bytes"
filename = "crunched.out"
- write the compressed data
File.open(filename, "w") do |fh|
fh.binmode fh.print crunch(original)
end
filesize = File.size(filename) puts "the file containing the crunched text is #{filesize} bytes"
- read and expand
expanded = File.open(filename, "r") do |fh|
fh.binmode expand(fh.read)
end
if original == expanded
puts "success"
else
puts "fail!"
end</lang>
Tcl
<lang tcl>package require Tcl 8.5
proc crunch {ascii} {
binary scan $ascii B* bitstring
# crunch: remove the extraneous leading 0 bit
regsub -all {0(.{7})} $bitstring {\1} 7bitstring
set padded "$7bitstring[string repeat 0 [expr {8 - [string length $7bitstring]%8}]]"
return [binary format B* $padded]
}
proc expand {binary} {
binary scan $binary B* padded
# expand the 7 bit segments with their leading 0 bit
set bitstring "0[join [regexp -inline -all {.{7}} $padded] 0]"
return [binary format B* $bitstring]
}
proc crunch_and_write {ascii filename} {
set fh [open $filename w] fconfigure $fh -translation binary puts -nonewline $fh [crunch $ascii] close $fh
}
proc read_and_expand {filename} {
set fh [open $filename r] fconfigure $fh -translation binary set input [read $fh [file size $filename]] close $fh return [expand $input]
}
set original "This is an ascii string that will be crunched, written, read and expanded." puts "my ascii string is [string length $original] bytes"
set filename crunched.out crunch_and_write $original $filename
set filesize [file size $filename] puts "the file containing the crunched text is $filesize bytes"
set expanded [read_and_expand $filename]
if {$original eq $expanded} {
puts "the expanded string is the same as the original"
} else {
error "not the same"
}</lang> outputs
my ascii string is 74 bytes the file containing the crunched text is 65 bytes the expanded string is the same as the original