Bitstream Biblioteca a Scala
Domanda
Ho bisogno di comprimere / decomprimere alcuni dati con un vecchio, in casa sviluppato Algoritmo. Ci ho un sacco di operazioni come:
if the next bit is 0 take the following 6 Bits and interpret them as an Int
if the next bits are 10 take the following 9 Bits and interpret them as an Int
etc.
conosce qualcuno qualcosa di simile a una classe "Bitstrem" in Scala? (Non ho trovato nulla e la speranza che non ho avuto per la sua attuazione da sola.)
Grazie
Modifica: Ho unito la risposta con http://www.scala-lang.org/node/8413 ( "The Architecture of Scala Collezioni") Se qualcuno ha bisogno samething:
abstract class Bit
object Bit {
val fromInt: Int => Bit = Array(Low, High)
val toInt: Bit => Int = Map(Low -> 0, High -> 1)
}
case object High extends Bit
case object Low extends Bit
import collection.IndexedSeqLike
import collection.mutable.{Builder, ArrayBuffer}
import collection.generic.CanBuildFrom
import collection.IndexedSeq
// IndexedSeqLike implements all concrete methods of IndexedSeq
// with newBuilder. (methods like take, filter, drop)
final class BitSeq private (val bits: Array[Int], val length: Int)
extends IndexedSeq[Bit]
with IndexedSeqLike[Bit, BitSeq]
{
import BitSeq._
// Mandatory for IndexedSeqLike
override protected[this] def newBuilder: Builder[Bit, BitSeq] =
BitSeq.newBuilder
//Mandatory for IndexedSeq
def apply(idx: Int): Bit = {
if(idx < 0 || length <= idx)
throw new IndexOutOfBoundsException
Bit.fromInt(bits(idx/N) >> (idx % N) & M)
}
}
object BitSeq {
// Bits per Int
private val N = 32
// Bitmask to isolate a bit
private val M = 0x01
def fromSeq(buf: Seq[Bit]): BitSeq = {
val bits = new Array[Int]((buf.length + N - 1) / N)
for(i <- 0 until buf.length) {
bits(i/N) |= Bit.toInt(buf(i)) << (i % N)
}
new BitSeq(bits, buf.length)
}
def apply(bits: Bit*) = fromSeq(bits)
def newBuilder: Builder[Bit, BitSeq] = new ArrayBuffer mapResult fromSeq
// Needed for map etc. (BitSeq map {:Bit} should return a BitSeq)
implicit def canBuilderFrom: CanBuildFrom[BitSeq, Bit, BitSeq] =
new CanBuildFrom[BitSeq, Bit, BitSeq] {
def apply(): Builder[Bit, BitSeq] = newBuilder
def apply(from: BitSeq): Builder[Bit, BitSeq] = newBuilder
}
}
Soluzione
Non è qualsiasi classe esistente che io sappia, ma è possibile sfruttare le classi esistenti per dare una mano con quasi tutte le operazioni difficili. Il trucco è quello di trasformare i dati in un flusso di int (o byte se non ci sarebbe abbastanza memoria). È quindi possibile utilizzare tutti i metodi pratici collezioni (per esempio take
) e solo sta a sinistra con il problema di trasformare i bit in memoria. Ma questo è facile se si pack i bit in ordine MSB.
object BitExample {
def bitInt(ii: Iterator[Int]): Int = (0 /: ii)((i,b) => (i<<1)|b)
def bitInt(ii: Iterable[Int]): Int = bitInt(ii.iterator)
class ArrayBits(bytes: Array[Byte]) extends Iterator[Int] {
private[this] var buffer = 0
private[this] var index,shift = -1
def hasNext = (shift > 0) || (index+1 < bytes.length)
def next = {
if (shift <= 0) {
index += 1
buffer = bytes(index) & 0xFF
shift = 7
}
else shift -= 1
(buffer >> shift) & 0x1
}
}
}
E poi si fanno le cose come
import BitExample._
val compressed = new ArrayBits( Array[Byte](14,29,126) ).toStream
val headless = compressed.dropWhile(_ == 0)
val (test,rest) = headless.splitAt(3)
if (bitInt(test) > 4) println(bitInt(rest.take(6)))
(Si può decidere se si desidera utilizzare l'iteratore direttamente o come un flusso, un elenco o qualsiasi altra cosa.)