Newsgroup: it.comp.lang.c++
Titolo: Scorrere i file bit a bit

Innanzitutto mi scuso per la possibilità che vediate due volte questo
post (l'ho gia postato su un news server free, ma non si è propagato a
quanto pare).
Il mio problema è il seguente, ho la necessità di scrivere/leggere
su un file (o cmq su uno stream) bit per bit e non byte per byte.
Mi sapete dare qualche indicazione?
-- 
   _  __                  _    || L' estate svuota la mente e così
  / |/ /__ __ _  ___ ___ (_)__ || mi ritrovo senza uno straccio di
 /    / -_)  ' \/ -_(_-</ (_-< || idea  per riempire questo spazio
/_/|_/\__/_/_/_/\__/___/_/___/ || bianco ...

Mi sapete dare qualche indicazione?
Leggi un byte alla volta ed estrai da ogni byte i suoi bit.
--
Andrea Laforgia (mica uno qualunque...)

Andrea Laforgia (mica uno qualunque...)
-- 
   _  __                  _    || L' estate svuota la mente e cosě


ditemi che non č cosě.
Una soluzione potrebbe essere: estrai un byte e lo trasformi in bit
(da esadecimale a binario), e leggi i singoli bit. Per il procedimento
inverso imposti un bit alla volta finchč non hai un byte (8 bit) e lo
scrivi sul file.
Ciao,
Mic

ditemi che non č cosě.
In realta' e' cosi', nel senso che l'unita' minima di
informazione leggibile/scrivibile e' il byte, ma non c'e' da
preoccuparsi.  Scrivere un byte equivale (nel 99.9% dei
casi) a scrivere 8 bit di fila.  Se ne serve scrivere solo
1, se ne scriveranno comunque 8, magari il primo valorizzato
e i restanti a 0.  Se ne serve scrivere 13, si scriveranno 2
byte (16) con i primi 13 valorizzati e i restanti 3 a 0, e
cosi' via...


scrivi sul file.
HTH
/* rwbits.c
   03/09/2001 h 23.55
   Andrea Laforgia
*/
#include <stdio.h>
#include <limits.h>
#include <ctype.h>
typedef unsigned char BIT;
typedef unsigned char BYTE;
BIT get_bit( BYTE byte, int pos )
{
    return ( byte >> pos ) & 1 ;
}
void put_bit( BYTE *pbyte, BIT bit )
{
     *pbyte = ( *pbyte << 1 ) | bit ;
}
int main()
{
    BIT bit ;
    BYTE r_byte, w_byte;
    int c, i ;
    puts( "scrivi il tuo nome e batti "\
          "\"Invio\" (CTRL+Z per terminare)" ) ;
    while ((c = getchar()) != EOF)
    {
          if ( isprint( c ) )
          {
             w_byte = 0;
             r_byte = (BYTE)c;
             for (i = CHAR_BIT - 1; i >= 0; i--)
             {
                 bit = get_bit( r_byte, i ) ;
                 put_bit( &w_byte, bit ) ;
             }
             printf( "(%c)\n", w_byte ) ;
          }
    }
    return 0;


 ha scritto nel messaggio
news:3b97f8b6...@news.tin.it...

Bisogna perň ricordarsi che se si devono scrivere un numero di bit non
divisibile per 8, bisogna in qualche modo aggiungere un "terminatore", un
qualcosa che ci dice che la serie di bit č terminata. Ho avuto giŕ a che
fare con questo problema e seguo questa regola:
se l'ultimo bit significativo č 1, si completa il byte che lo contiene con
tanti 0 quanto č lo spazio-bit libero, e viceversa.
ESEMPIO
Abbiamo scritto 16 bit, dobbiamo scrivere l'ultima sequenza 11011.
Ovviamente il file, anche se a noi interessano 21 bit, sarŕ di 24 bit, cioč
3 bytes.
Ci "avanzeranno" 3 bit, li riempiamo con bit contrari all'ultimo bit
scritto.
File: 8bit+8bit+"11011"+"000"=3bytes.
(Viceversa se l'ultimo bit č uno zero, riempiremo l'ultimo byte con degli 1:
File 8bit+8bit+"00100"+"111"=3bytes.)
In lettura dovremo prima di tutto trovare la lunghezza del file in bit, cioč
il numero di bit che effettivamente trasportano informazione. Per farlo
adoperiamo questa procedura:
Leggiamo l'ultimo byte del file
Byte="11011000"
leggiamo l'ultimo bit
bit="0"
dal fondo, risaliamo le posizioni finché non troviamo un bit diverso, nel
nostro caso "1", e ne individuiamo la posizione.
"11011...."
bit diverso č nella posizione 5.
ora sappiamo che gli ultimi (8-5) bit del file non hanno significato. Sono
il nostro "terminatore".
la lunghezza in bit del file č :
LunghezzaFileInByte*8-NumeroDiBitDelTerminatore.

 Leggiamo l'ultimo byte del file
Operazione spesso MOOOLTO lenta per i vari FileSystem... Non č forse piů 
semplice una (o due) long che specifichino subito la lunghezza in byte?
O ancora meglio un singolo byte all'inizio che specifica quanti bit sono 
significativi nell'ultimo byte.
-- 
Luc.

 semplice una (o due) long che specifichino subito la lunghezza in byte?
Ops... in bit.
-- 
Luc.

 cosi' via...
Il punto e' che io non posso buttare 7 bit cosi', il programma che devo
ritoccare
fa proprio questo cioe' invece di scrivere un bit scrive un byte intero
anche se
l'informazione da trasmettere e' in realta' 1 oppure 0, questo e'
inaccettabile
perche' si tratta dell'output di un codificatore di immagini, capirai
quindi tanta
fatica per cercare di ridurre il bit/rate e poi si buttano i bit cosi'
Cmq grazie ho visto l'esempio che hai scritto e me lo sto studiando :)
-- 
Un Nemesis dal web
-- 
Posted from 
pigato.labnet.cnit.it
 [217.9.64.14] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 semplice una (o due) long che specifichino subito la lunghezza in byte?
Hai fatto delle prove? Mi aspetterei che i file system odierni
supportino l'accesso diretto a qualsiasi byte di un file. Tra l'altro,
non e' magari meglio ricorrere ad opportune chiamate di sistema per
conoscere la lunghezza di un file?
Ciao,
Nicola

 conoscere la lunghezza di un file?
Certo! il problema è che l'unità di misura è il byte e qui vogliamo avere la 
precisione al bit.
-- 
Luc.

 Cmq grazie ho visto l'esempio che hai scritto e me lo sto studiando :)
bufferizza: copia in memoria e  lavora li' a blocchi di dati, + o meno 
vasti a seconda della tua macchina, con un flush ogni tanto su memoria 
video

 File: 8bit+8bit+"11011"+"000"=3bytes.
e se io volevo scrivere *esattamente* 11011000 come ultimo byte? e' vietato?
:-)
questo metodo e' mooooolto pericoloso (errato, direi), molto meglio come
dice Luc. IMHO.
--
Ciao by Allanon

 dice Luc. IMHO.
Anche se nel caso specifico scriveresti un ultimo byte tutto di 1. Usi
sempre meno spazio che a scrivere la dimensione in bit del file (ma
concordo sul fatto che non tutto l'hardware supporta seek efficienti).
Ciao,
Nicola

 Nicola
giusto... infatti c'ho pensato 1 mSec dopo aver premuto invio... :-)
--
Ciao by Allanon

esempio se un file è su CD-ROM la cosa può diventare lunga...
Francamente, queste obiezioni aggiungono poco alla
discussione.
Non c'entra nulla il tempo di accesso all'ultimo byte,
perche' non serve conoscere a priori la lunghezza precisa in
byte.
Se io voglio leggere un file bit a bit, arrivero' comunque
all'ultimo byte e, una volta letto, sapro' estrarre quanti
sono i byte effettivi secondo il metodo suggerito dal nostro
amico.


perche' non serve conoscere a priori la lunghezza precisa in byte.
A scanso di equivoci, intendevo "lunghezza in bit".
Voglio dire che, se il mio compito e' quello di leggere un
file bit a bit, non e' necessario conoscere a priori la
lunghezza in bit.


 --
Per l'uso che mi serviva dovevo risparmiare al massimo la memoria, dato che
dovevo salvare in un file una serie di "stringhe di bit" separate e non
potevo aggiungere un byte per ognuna che mi indicasse il numero di bit non
significativi.
Il mio metodo risparmia la memoria del file, il metodo che hai proposto tu
risparmia la velocità di lettura: tutto sta nello scegliere quello più
indicato per le proprie esigenze.

 :-)
Già, dimenticavo, in questo caso i bit "diversi " da aggiungere sono 8,
quindi nel tuo caso dovrai aggiungere "11111111", perché l'ultimo bit che
hai inserito è "0". Così il metodo funziona.

 Cmq grazie ho visto l'esempio che hai scritto e me lo sto studiando :)
Ah-ah. Anch'io uso il mio metodo per codificare immagini! Il fatto è che non
ho mai capito la codifica di Huffman, così mi sono inventato un protocollo
tutto mio. Comunque lo spreco di bit dipende dalla lunghezza della stringa
di bit che usi, cioè: se devi scrivere/leggere una stringa di 2000 bit, al
massimo sprecherai 8 bit, no?

e poi si buttano i bit cosi'.
I bit non si buttano, ma non e' pensabile scrivere 7 bit
senza necessariamente scrivere un byte.
In generale, non e' pensabile scrivere un numero di bit su
un file che non sia un multiplo di 8, ovvero che non sia
multiplo della grandezza in bit di un byte.
I codificatori di immagini devono "comprimere" e possono
farlo secondo molti algoritmi diversi (Huffman, Lempel-Ziv,
Run-Length-Encoding...).
Anni fa ho scritto un programma di compressione secondo
l'algoritmo di Huffman, ma il sorgente e' troppo lungo per
postarlo qui, se vuoi posso spedirtelo per e-mail (appena lo
trovo).


tutto mio.
Che livello di compressione massimo raggiungi con il tuo
metodo  ?


 multiplo della grandezza in bit di un byte.
Scusate ma vi rendete conto che state parlando di risparmiare bit nella
scrittura di un file?
Il file piu' corto possibile e' un file di un byte.
Ma un byte e' la sua dimensione "logica". La sua dimensione "fisica", ovvero lo
spazio occupato su disco, e' MOLTO di piu'. Se lavorate con un floppy e' di 512
byte. Se state su un HD e' possibilissimo che sia di qualche kilobyte. Lo spazio
esatto dipende dal file system e da eventuali settaggi di compressione dello
stesso.
Sinceramente non vedo dove stia il problema!
--
Andrea Ferro
---------
Brainbench C++ Master. Scored higher than 97% of previous takers
Scores: Overall 4.46, Conceptual 5.0, Problem-Solving 5.0
More info 
http://www.brainbench.com/transcript.jsp?pid=2522556

Sinceramente non vedo dove stia il problema!
Sinceramente non vedo cosa c'entri quest'ultimo punto...


 lunghezza in bit.
Opinabile.
-- 
Luc.

 Per l'uso che mi serviva dovevo risparmiare al massimo la memoria
Un byte in più (in un file) non penso abbia mai ucciso nessuno. 8)
-- 
Luc.

 Sinceramente non vedo dove stia il problema!
Lasciali stare con le loro 'seghe mentali'... 
-- 
Luc.

"uffa" <uf...@che.barba> wrote in message
news:29402439....@tin.it...

In effetti sto facendo proprio cosi', ho scritto una piccola classe che
rappresenta una
stringa sulla quale posso scrivere anche un singolo bit, in realta' tali
bit li bufferizzo su
un byte che poi quando e' pieno scarico sulla stringa.
Non ho capito pero' cosa intendi con la frase "flush ogni tanto sulla
memoria video", cosa
c'entra la memoria video?
-- 


 trovo).
Ti ringrazio ma non e' necessario, infatti il codificatore gia
c'e',  ed infatti quello che io sto trattando e' proprio l'uscita
prodotta da tale codificatore (che per la cronaca usa
la quantizzazione vettoriale per la codifica intraframe, ed
il conditional replenishment per quella interframe).
I bit a cui mi riferisco sono dei bit di segnalazione, il valore 1
indica che segue un byte contente l'indice della codeword che
codifica un blocchetto di 16X16 pixel, un valore 0 invece indica
che tale byte non verra' trasmesso inquanto predicibile
dal frame precedente. In situazioni quindi di frame che cambiano
poco io mi potrei ritrovare con una sequenza di zeri anche 
abbastanza lunga (~100 se non addirittura ~1000), sequenza 
che in teoria dovrebbe essere fatta da bit ma che in realta'
al momento e' fatta da byte.
-- 


 massimo sprecherai 8 bit, no?
No, leggi la mia risposta ad Andrea Laforgia per i dettagli.
-- 


 c'entra la memoria video?
 
la tua frase : "output di un codificatore di immagini, capirai quindi 
tanta fatica per cercare di ridurre il bit/rate" 
mi ha fatto pensare ad un output su video, ergo la frase 

uffa wrote:

No in realta' tale flusso non e' nient'altro che una sequenza di byte
memorizzati su una stringa (poi eventualmente copiata sul file).
--
Un Nemesis che finalmente puo' usare un vero news-server

 Sinceramente non vedo cosa c'entri quest'ultimo punto...
C'entra perche' alcuni messaggi (non tuoi) parlavano di quanti bit si
risparmiano usando il meccanismo del tappo con i bit invertiti invece che
l'header con un numero che indica la lunghezza. Un conto e' dire che se devo
salvare 800.000 bit e' meglio farlo come stringa di bit che come stringa di byte
ciascuno rappresentante un bit. Un altro e' fare una differenza fra un file
lungo N e uno lungo N+M dove M e' dell'ordine delle unità. Se il file e' lungo
10K usare 10K+4byte non cambia nulla. Se e' lungo 1 byte, usare 5 byte non
cambia nulla lo stesso. Su disco (se non e' compresso) 100 file da un byte
occupano lo stesso spazio di 100 file da 5 byte.


 un byte che poi quando e' pieno scarico sulla stringa.
Mi pare esista già nella STL. Anzi, dovrebbero esisterne ben due se consideri il
vettore di booleani.


Lo so. Infatti ti davo ragione.
Ah scusa, ho frainteso...


Opinabile.
Sarebbe gradito che esprimessi una motivazione per le tue
osservazioni.


Lasciali stare con le loro 'seghe mentali'... 
Luc vedi di darti una calmata, la masturbazione mentale non
e' una pratica diffusa qui dentro.


 e' una pratica diffusa qui dentro.
Io non avrò tempo materiale di controllare o postare codice C++, ma di 
discutere sugli algortimi si!
La tua affermazione che dice che conoscere a priori la lunghezza in bit di un 
bit-stream è inutile è francamente risibile.
 
-- 
Luc.

bit-stream č inutile č francamente risibile. 
Perche' ? lanci la pietra e nascondi la mano.
Dimostrami che a te serve conoscere la lunghezza in byte di
un file per poterlo leggere tutto.
Ovviamente non e' cosi'.
Il discorso fatto per i byte vale anche per i bit.


vettore di booleani.
Argh!!!!!! (tanta fatica sprecata)
Non è che mi puoi dire più precisamente cosa devo cercare?
-- 
   _  __                  _    || L' estate svuota la mente e così
  / |/ /__ __ _  ___ ___ (_)__ || mi ritrovo senza uno straccio di
 /    / -_)  ' \/ -_(_-</ (_-< || idea  per riempire questo spazio
/_/|_/\__/_/_/_/\__/___/_/___/ || bianco ...

 Non è che mi puoi dire più precisamente cosa devo cercare?
No. Ho scritto quel post prima di aver capito bene quello che volevi fare. La
funzionalità che ti da la classe di cui hai postato il sorgente (che tra
parentesi ha i difetti che tu stesso hai notato ma non mi sembra per altro
'sbagliata') non la trovi nella STL.
Comunque:
vector<bool> e' ottimizzato. Ovvero non usa internamente k bool per memorizzare
k valori ma bensi 'impacchetta' gli elementi in un qualche tipo implementation
defined (per esempio unsigned int).
La cosa e' buona se hai necessità di un vero vettore di booleani (soprattutto se
di grosse dimensioni). Ma non ti permette di estrarre nulla che non sia
effettivamente un booleano. Ovvero non puoi leggerti un char o un int composto
con i bit che hai inserito nel vettore.
bitset<N> invece rappresenta un array di N bit. La dimensione non e'
modificabile (ovvero i bit sono N dall'inizio alla fine). Non ha pertanto la
funzionalità di "inserimento" di un bit o cose simili. Pero', sempre che N sia
tale da permetterlo, puo' restituirti i bit impacchettati in un long. Potresti
usarlo come 'buffer' nella tua classe, ma non cambierebbe di molto la "fatica"
che hai fatto.
Quindi non hai un container di 'bit' che sia contemporaneamente ridimensionabile
e accedibile per 'byte'.
Per completezza andrebbe poi segnalato valarray<bool> che dal tuo punto di vista
vale tanto quanto un vector<bool>. Come tutti i valarray ha senso se accedi ai
dati secondo pattern di indicizzazione differenti e/o se esegui calcoli si piu'
valori "in parallelo".


 un file per poterlo leggere tutto.
Perchè, tu scrivi applicazioni in cui leggi TUTTO un file in memoria???
Beh, dove lavoro io che trattiamo con grossi file multimediali questo non 
accade... è bello però far visualizzare al programma quanto è lungo il file 
che verrà elaborato....
-- 
Luc.




che verrà elaborato....
Gia', ma spesso non e' necessario ai fini dell'elaborazione.


 metodo  ?
Per le immagini al massimoestremochepiùmassimononsipuò 64:1.

 Sinceramente non vedo dove stia il problema!
Se devi fare un compressore di filmati(tante immagini...) il problema lo
vedi subito...

"Andrea Ferro" <And...@UrkaDVD.it> ha scritto nel messaggio
news:9n5jr6$smq$1...@serv1.iunet.it...

Ma se devo salvare 10000 stringhe da una ventina di bit ognuna, aggiungendo
un byte che ne identifica la lunghezza per ognuna di esse ho 10000byte di
troppo...

 vedi subito...
Se devo fare un compressore di filmati non lo faccio che lavori immagine per
immagine. Lo faccio che lavori come minimo a blocchi (GOP). E a questo punto ho
come minimo ben due livelli di strutturazione prima di arrivare ad una
bitstream.


 troppo...
Scusa ma io avevo capito che dovevi salvare una bitstring in un file. O
perlomeno una per file. Se devi salvarne piu' di una allora il file non e' una
bitstream ma ha per forza un qualche tipo di strutturazione. E presumibilmente
sarà questa struttura che detterà la maniera giusta per identificare la
posizione e la lunghezza di ciascuna bitstream (perche' il problema ora non e'
piu' solo quello della lunghezza ma anche quello della posizione).
