Bitwise IO: Difference between revisions
Content added Content deleted
m (→{{header|Haskell}}: add stub category for Go) |
(→{{header|Go}}: Add Go solution) |
||
Line 1,115: | Line 1,115: | ||
=={{header|Go}}== |
=={{header|Go}}== |
||
Based on the |
|||
<code>[https://golang.org/pkg/compress/lzw compress/lzw]</code> |
|||
encoder and decoder internal types |
|||
(with LZW specific stuff trimmed). |
|||
<lang Go>// Package bit provides bit-wise IO to an io.Writer and from an io.Reader. |
|||
package bit |
|||
import ( |
|||
"bufio" |
|||
"errors" |
|||
"io" |
|||
) |
|||
// Order specifies the bit ordering within a byte stream. |
|||
type Order int |
|||
const ( |
|||
// LSB is for Least Significant Bits first |
|||
LSB Order = iota |
|||
// MSB is for Most Significant Bits first |
|||
MSB |
|||
) |
|||
// ==== Writing / Encoding ==== |
|||
type writer interface { |
|||
io.ByteWriter |
|||
Flush() error |
|||
} |
|||
// Writer implements bit-wise writing to an io.Writer. |
|||
type Writer struct { |
|||
w writer |
|||
order Order |
|||
write func(uint32, uint) error // writeLSB or writeMSB |
|||
bits uint32 |
|||
nBits uint |
|||
err error |
|||
} |
|||
// writeLSB writes `width` bits of `c` in LSB order. |
|||
func (w *Writer) writeLSB(c uint32, width uint) error { |
|||
w.bits |= c << w.nBits |
|||
w.nBits += width |
|||
for w.nBits >= 8 { |
|||
if err := w.w.WriteByte(uint8(w.bits)); err != nil { |
|||
return err |
|||
} |
|||
w.bits >>= 8 |
|||
w.nBits -= 8 |
|||
} |
|||
return nil |
|||
} |
|||
// writeMSB writes `width` bits of `c` in MSB order. |
|||
func (w *Writer) writeMSB(c uint32, width uint) error { |
|||
w.bits |= c << (32 - width - w.nBits) |
|||
w.nBits += width |
|||
for w.nBits >= 8 { |
|||
if err := w.w.WriteByte(uint8(w.bits >> 24)); err != nil { |
|||
return err |
|||
} |
|||
w.bits <<= 8 |
|||
w.nBits -= 8 |
|||
} |
|||
return nil |
|||
} |
|||
// WriteBits writes up to 16 bits of `c` to the underlying writer. |
|||
// Even for MSB ordering the bits are taken from the lower bits of `c`. |
|||
// (e.g. WriteBits(0x0f,4) writes four 1 bits). |
|||
func (w *Writer) WriteBits(c uint16, width uint) error { |
|||
if w.err == nil { |
|||
w.err = w.write(uint32(c), width) |
|||
} |
|||
return w.err |
|||
} |
|||
var errClosed = errors.New("bit reader/writer is closed") |
|||
// Close closes the writer, flushing any pending output. |
|||
// It does not close the underlying writer. |
|||
func (w *Writer) Close() error { |
|||
if w.err != nil { |
|||
if w.err == errClosed { |
|||
return nil |
|||
} |
|||
return w.err |
|||
} |
|||
// Write the final bits (zero padded). |
|||
if w.nBits > 0 { |
|||
if w.order == MSB { |
|||
w.bits >>= 24 |
|||
} |
|||
if w.err = w.w.WriteByte(uint8(w.bits)); w.err != nil { |
|||
return w.err |
|||
} |
|||
} |
|||
w.err = w.w.Flush() |
|||
if w.err != nil { |
|||
return w.err |
|||
} |
|||
// Make any future calls to Write return errClosed. |
|||
w.err = errClosed |
|||
return nil |
|||
} |
|||
// NewWriter returns a new bit Writer that writes completed bytes to `w`. |
|||
func NewWriter(w io.Writer, order Order) *Writer { |
|||
bw := &Writer{order: order} |
|||
switch order { |
|||
case LSB: |
|||
bw.write = bw.writeLSB |
|||
case MSB: |
|||
bw.write = bw.writeMSB |
|||
default: |
|||
bw.err = errors.New("bit writer: unknown order") |
|||
return bw |
|||
} |
|||
if byteWriter, ok := w.(writer); ok { |
|||
bw.w = byteWriter |
|||
} else { |
|||
bw.w = bufio.NewWriter(w) |
|||
} |
|||
return bw |
|||
} |
|||
// ==== Reading / Decoding ==== |
|||
// Reader implements bit-wise reading from an io.Reader. |
|||
type Reader struct { |
|||
r io.ByteReader |
|||
bits uint32 |
|||
nBits uint |
|||
read func(width uint) (uint16, error) // readLSB or readMSB |
|||
err error |
|||
} |
|||
func (r *Reader) readLSB(width uint) (uint16, error) { |
|||
for r.nBits < width { |
|||
x, err := r.r.ReadByte() |
|||
if err != nil { |
|||
return 0, err |
|||
} |
|||
r.bits |= uint32(x) << r.nBits |
|||
r.nBits += 8 |
|||
} |
|||
bits := uint16(r.bits & (1<<width - 1)) |
|||
r.bits >>= width |
|||
r.nBits -= width |
|||
return bits, nil |
|||
} |
|||
func (r *Reader) readMSB(width uint) (uint16, error) { |
|||
for r.nBits < width { |
|||
x, err := r.r.ReadByte() |
|||
if err != nil { |
|||
return 0, err |
|||
} |
|||
r.bits |= uint32(x) << (24 - r.nBits) |
|||
r.nBits += 8 |
|||
} |
|||
bits := uint16(r.bits >> (32 - width)) |
|||
r.bits <<= width |
|||
r.nBits -= width |
|||
return bits, nil |
|||
} |
|||
// ReadBits reads up to 16 bits from the underlying reader. |
|||
func (r *Reader) ReadBits(width uint) (uint16, error) { |
|||
var bits uint16 |
|||
if r.err == nil { |
|||
bits, r.err = r.read(width) |
|||
} |
|||
return bits, r.err |
|||
} |
|||
// Close closes the reader. |
|||
// It does not close the underlying reader. |
|||
func (r *Reader) Close() error { |
|||
if r.err != nil && r.err != errClosed { |
|||
return r.err |
|||
} |
|||
r.err = errClosed |
|||
return nil |
|||
} |
|||
// NewReader returns a new bit Reader that reads bytes from `r`. |
|||
func NewReader(r io.Reader, order Order) *Reader { |
|||
br := new(Reader) |
|||
switch order { |
|||
case LSB: |
|||
br.read = br.readLSB |
|||
case MSB: |
|||
br.read = br.readMSB |
|||
default: |
|||
br.err = errors.New("bit writer: unknown order") |
|||
return br |
|||
} |
|||
if byteReader, ok := r.(io.ByteReader); ok { |
|||
br.r = byteReader |
|||
} else { |
|||
br.r = bufio.NewReader(r) |
|||
} |
|||
return br |
|||
}</lang> |
|||
And a test file (such as <code>bit_test.go</code>): |
|||
<lang Go>package bit |
|||
import ( |
|||
"bytes" |
|||
"fmt" |
|||
"io" |
|||
"log" |
|||
) |
|||
func ExampleWriter_WriteBits() { |
|||
var buf bytes.Buffer |
|||
bw := NewWriter(&buf, MSB) |
|||
bw.WriteBits(0x0f, 4) // Writes 1111 |
|||
bw.WriteBits(0x00, 1) // 0 |
|||
bw.WriteBits(0x13, 5) // 1001 1 |
|||
// Close will flush with zero bits, in this case |
|||
// 0000 00 |
|||
if err := bw.Close(); err != nil { |
|||
log.Fatal(err) |
|||
} |
|||
fmt.Printf("%08b", buf.Bytes()) |
|||
// Output: |
|||
// [11110100 11000000] |
|||
} |
|||
func Example() { |
|||
const message = "This is a test." |
|||
fmt.Printf("%q as bytes: % 02[1]X\n", message, []byte(message)) |
|||
fmt.Printf(" original bits: %08b\n", []byte(message)) |
|||
// Re-write in 7 bit chunks to buf: |
|||
var buf bytes.Buffer |
|||
bw := NewWriter(&buf, MSB) |
|||
for _, r := range message { |
|||
bw.WriteBits(uint16(r), 7) // nolint: errcheck |
|||
} |
|||
if err := bw.Close(); err != nil { |
|||
log.Fatal(err) |
|||
} |
|||
fmt.Printf("Written bitstream: %08b\n", buf.Bytes()) |
|||
fmt.Printf("Written bytes: % 02X\n", buf.Bytes()) |
|||
// Read back in 7 bit chunks: |
|||
br := NewReader(&buf, MSB) |
|||
var result []byte |
|||
for { |
|||
v, err := br.ReadBits(7) |
|||
if err != nil { |
|||
if err != io.EOF { |
|||
log.Fatal(err) |
|||
} |
|||
break |
|||
} |
|||
if v != 0 { |
|||
result = append(result, byte(v)) |
|||
} |
|||
} |
|||
fmt.Printf("Read back as \"%s\"\n", result) |
|||
// Output: |
|||
// "This is a test." as bytes: 54 68 69 73 20 69 73 20 61 20 74 65 73 74 2E |
|||
// original bits: [01010100 01101000 01101001 01110011 00100000 01101001 01110011 00100000 01100001 00100000 01110100 01100101 01110011 01110100 00101110] |
|||
// Written bitstream: [10101001 10100011 01001111 00110100 00011010 01111001 10100000 11000010 10000011 10100110 01011110 01111101 00010111 00000000] |
|||
// Written bytes: A9 A3 4F 34 1A 79 A0 C2 83 A6 5E 7D 17 00 |
|||
// Read back as "This is a test." |
|||
}</lang> |
|||
With this test file, running <code>go test -v</code> will compile the package and run the example verifying the output is as listed above in the <code>// Output:</code> comments. |
|||
Additionally, <code>godoc -ex</code> will extract the code comments and for documentation and include the examples at the appropriate place |
|||
(here the first goes with the <code>WriteBits</code> method and the later with the package documentation). |
|||
=={{header|Haskell}}== |
=={{header|Haskell}}== |