Bitwise IO: Difference between revisions
m (<code>; fixed C reserved identifier) |
m (<lang>) |
||
Line 26: | Line 26: | ||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
< |
<lang ada> |
||
with Ada.Streams; use Ada.Streams; |
with Ada.Streams; use Ada.Streams; |
||
with Ada.Finalization; |
with Ada.Finalization; |
||
Line 47: | Line 47: | ||
overriding procedure Finalize (Stream : in out Bit_Stream); |
overriding procedure Finalize (Stream : in out Bit_Stream); |
||
end Bit_Streams; |
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: |
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 |
package body Bit_Streams is |
||
procedure Finalize (Stream : in out Bit_Stream) is |
procedure Finalize (Stream : in out Bit_Stream) is |
||
Line 83: | Line 83: | ||
end Write; |
end Write; |
||
end Bit_Streams; |
end Bit_Streams; |
||
</ |
</lang> |
||
Example of use: |
Example of use: |
||
< |
<lang ada> |
||
with Ada.Streams.Stream_IO; use Ada.Streams.Stream_IO; |
with Ada.Streams.Stream_IO; use Ada.Streams.Stream_IO; |
||
with Bit_Streams; use Bit_Streams; |
with Bit_Streams; use Bit_Streams; |
||
Line 120: | Line 120: | ||
end if; |
end if; |
||
end Test_Bit_Streams; |
end Test_Bit_Streams; |
||
</ |
</lang> |
||
=={{header|C}}== |
=={{header|C}}== |
||
Line 128: | Line 128: | ||
File: bitio.h |
File: bitio.h |
||
< |
<lang c> |
||
#ifndef BIT_IO_H |
#ifndef BIT_IO_H |
||
#define BIT_IO_H |
#define BIT_IO_H |
||
Line 147: | Line 147: | ||
#endif |
#endif |
||
</ |
</lang> |
||
File: bitio.c |
File: bitio.c |
||
< |
<lang c> |
||
#include "bitio.h" |
#include "bitio.h" |
||
Line 249: | Line 249: | ||
return wbit; |
return wbit; |
||
} |
} |
||
</ |
</lang> |
||
===Usage example=== |
===Usage example=== |
||
Line 255: | Line 255: | ||
"Compression" of the ASCII byte standard input stream to the standard output: |
"Compression" of the ASCII byte standard input stream to the standard output: |
||
< |
<lang c> |
||
#include <stdio.h> |
#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
Line 270: | Line 270: | ||
return 0; |
return 0; |
||
} |
} |
||
</ |
</lang> |
||
"Decompression" of a 7-bit encoded ASCII stream to a "regular" ASCII byte stream: |
"Decompression" of a 7-bit encoded ASCII stream to a "regular" ASCII byte stream: |
||
< |
<lang c> |
||
#include <stdio.h> |
#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
Line 288: | Line 288: | ||
return 0; |
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. |
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. |
||
Line 295: | Line 295: | ||
The [http://code.google.com/p/ocaml-extlib/ extLib] provides [http://ocaml-extlib.googlecode.com/svn/doc/apiref/IO.html#6_BitsAPI bit oriented IO functions]. |
The [http://code.google.com/p/ocaml-extlib/ extLib] provides [http://ocaml-extlib.googlecode.com/svn/doc/apiref/IO.html#6_BitsAPI bit oriented IO functions]. |
||
< |
<lang ocaml> |
||
let write_7bit_string ~filename ~str = |
let write_7bit_string ~filename ~str = |
||
let oc = open_out filename in |
let oc = open_out filename in |
||
Line 303: | Line 303: | ||
close_out oc; |
close_out oc; |
||
;; |
;; |
||
</ |
</lang> |
||
< |
<lang ocaml> |
||
let read_7bit_string ~filename = |
let read_7bit_string ~filename = |
||
let ic = open_in filename in |
let ic = open_in filename in |
||
Line 315: | Line 315: | ||
with End_of_file -> |
with End_of_file -> |
||
(Buffer.contents buf) |
(Buffer.contents buf) |
||
</ |
</lang> |
Revision as of 12:33, 31 January 2009
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.
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>