Bitwise IO: Difference between revisions
Content deleted Content added
m →{{header|Haskell}}: add stub category for Go |
→{{header|Go}}: Add Go solution |
||
Line 1,115:
=={{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}}==
|