Aggiungi questa pagina ai preferitiHome » Programmazione
Leggere file in ASM 64 bit Linux
Come leggere file in Assembly con Linux
18/12/2011 - In Programmazione - By kingk (art. no 302)Leggere file in ASM con Linux ASM x64
In questo articolo vedremo come leggere dei file in assembly con Linux, utilizzando l'assembly per processori a 64 bit.Per creare un programma interessante, creeremo un programma clone del comando cat di Linux scritto ovviamente in assembly.
Qui sotto riportiamo le parti di codice più interessanti del programma acat spiegate e commentate, il sorgente completo lo trovate compresso alla fine dell'articolo, è possibile compilarlo con NASM necessita un sistema operativo a 64bit, il codice sorgente è stato testato con Debian 6.
Come prima cosa per realizzare un programma clone del cat in assembly dobbiamo poter leggere i parametri passati al programma, in particolare ci interessa l'equivalente in C del parametro ARGV, ossia del file da stampare sullo schermo passato come parametro alla posizione 1.
Il nostro programma "acat" verrà utilizzato nel seguente modo per stampare a monitor il contenuto di un file:
./acat nome_del_file_da_stampare
Come leggere i parametri nei programmi scritti in assembly (argc e argv)
I parametri passati ad un programma in assembly verrano memorizzati dal kernel nello stack e saranno disponibili in modo molto semplice al programma assembler nelle prime posizioni dello stack, qui sotto riportiamo il listato di codice per leggerli.1) pop rcx ;Program Filename
2) pop rcx ;ARGC tells the number of ARGV to read
3) pop rcx ; ARGV[1] pointer!
4) mov rsi,rcx ;RSI is the argv[1] pointer
2) pop rcx ;ARGC tells the number of ARGV to read
3) pop rcx ; ARGV[1] pointer!
4) mov rsi,rcx ;RSI is the argv[1] pointer
Per leggere i parametri in assembly basta eseguire delle istruzioni "pop", per recuperare le informazioni passate dal kernel al programma mediante la memoria dello stack.
Il primo parametro letto è l'equivalente in C di argv[0], ossia il nome del programma.
Il secondo parametro è invece l'argc, il numero di parametri disponibili
Dal terzo parametro in poi si iniziano a leggere le stringhe passate da argv[1] ad argv[x].
Nel nostro esempio scartiamo le prime due, mentre memorizziamo il puntatore alla stringa argv[1] nel registro rsi, dopo di che per comodità salveremo la stringa argv[1] in una zona di memoria.
Come stampare una stringa su schermo in assembly x64 Linux
1) mov rdx,lenmsg1 ; arg3, length of string to print
2) mov rcx,msg1 ; arg2, pointer to string
3) mov rbx,1 ; arg1, where to write, screen
4) mov rax,4 ; write sysout command to int 80 hex
5) int 0x80 ; interrupt 80 hex, call kernel
2) mov rcx,msg1 ; arg2, pointer to string
3) mov rbx,1 ; arg1, where to write, screen
4) mov rax,4 ; write sysout command to int 80 hex
5) int 0x80 ; interrupt 80 hex, call kernel
Per stampare una stringa in assembly con linux è molto semplice, basta caricare i registri della CPU nel seguente modo:
rdx: Lunghezza della stringa da stampare
rcx: Locazione della memoria contenente il primo carattere della stringa da stampare, non è altro che un puntatore.
rbx: Dove si desidera stampare il valore 1 indica lo schermo
rax: La funzione del kernel da eseguire, 4 indica il comando write
infine basta generare l'interrupt 80h del kernel di linux con l'istruzione della riga 5, il Kernel linux penserà al resto, nella stessa maniera possiamo chiamare altre funzioni del kernel utilizzando i parametri corretti.
Come leggere un file in assembly
Per leggere un file in assembly come prima cosa bisogna utilizzare la funzione del kernel linux open file tramite il seguente listato:1) mov rax,5 ; the syscall number for open()
2) mov rbx,filename ; File Name pointer
3) mov rcx,2 ; Read Write flag
4) int 80h ; call the kernel
5) test rax,rax ; lets make sure it is valid
6) jns readstart ; if the file descriptor does not have
2) mov rbx,filename ; File Name pointer
3) mov rcx,2 ; Read Write flag
4) int 80h ; call the kernel
5) test rax,rax ; lets make sure it is valid
6) jns readstart ; if the file descriptor does not have
In maniera analoga al metodo per stampare caratteri sullo schermo, bisogna caricare i registri della cpu nel seguente modo:
rax: 5, funzione file open
rbx: puntatore alla stringa con il percorso del file
rcx: 2, flag read/write, indica la modalità di apertura del file
rdx: lunghezza del filename da aprire
Infine basta invocare l'interrupt 80h per dire al kernel di aprire il file.
Se tutto è andato bene, il registro rax conterrà il file descriptor, un numero che sarà maggiore di zero nel caso in cui l'apertura del file è andata a buon fine.
Possiamo ora finalmente leggere dal file con il seguente codice:
1) mov rbx,rax ; sys_open returned file descriptor into eax
2) mov rax,3 ; sys_read
3) mov rcx,buffer ; we are putting the ADDRESS of buf in ecx
4) mov rdx,bufsize ; we are putting the ADDRESS of bufsize in edx
5) int 80h ; call the kernel
2) mov rax,3 ; sys_read
3) mov rcx,buffer ; we are putting the ADDRESS of buf in ecx
4) mov rdx,bufsize ; we are putting the ADDRESS of bufsize in edx
5) int 80h ; call the kernel
Una volta aperto un file, è possibile leggerlo caricando i registri nel seguente modo:
rbx: file descriptor restituito dalla funzione open file nel registro rax
rax: 3, funzione per leggere file
rcx: locazione di una memoria di tipo byte
rdx: Lunghezza della memoria di tipo byte
Infine basta invocare l'interrupt 80h.
Il registro rax, conterrà il numero di byte letti dal file, si può inserire questa procedura in un loop per leggere interamente un file finche il registro rax sarà maggiore di 0.
Leggi e Commenta
Acat SourcesTags: Stampare caratteri su schermo in assembler con Linux - Acat programma clone di cat in assembly 64bit linux
Convertire una stringa esadecimale (hex) in intero (Integer) in C e C++
Conversione da Esadecimale a Integer in C/C++
12/08/2011 - In Programmazione - By kingk (art. no 261)Convertire una stringa esadecimale (HEX) in Integer C/C++
Come posso convertire una stringa esadecimale (hex) in intero in C/C++?Non esistono funzioni ufficiali nello standard ANSI per convertire una stringa esadecimale in numero intero, la funzione "atoh" riportata qui sotto consente di eseguire questa operazione, presentando un ottima portabilità in tutti i linguaggi di programmazione esistenti.
int atoh(char * string, int size, bool reverse)
{
//By www.oldwildweb.com
unsigned int value = 0;
int char_val = 0;
int hchar_val = 1;
if (reverse == true)
for (int i = 0; i < size; i++)
{
if (string[i] == '0')
char_val = 0;
if (string[i] == '1')
char_val = 1;
if (string[i] == '2')
char_val = 2;
if (string[i] == '3')
char_val = 3;
if (string[i] == '4')
char_val = 4;
if (string[i] == '5')
char_val = 5;
if (string[i] == '6')
char_val = 6;
if (string[i] == '7')
char_val = 7;
if (string[i] == '8')
char_val = 8;
if (string[i] == '9')
char_val = 9;
if (string[i] == 'a' || string[i] == 'A' )
char_val = 10;
if (string[i] == 'b' || string[i] == 'B' )
char_val = 11;
if (string[i] == 'c' || string[i] == 'C' )
char_val = 12;
if (string[i] == 'd' || string[i] == 'D' )
char_val = 13;
if (string[i] == 'e' || string[i] == 'E' )
char_val = 14;
if (string[i] == 'f' || string[i] == 'F' )
char_val = 15;
value = value + (hchar_val*char_val);
hchar_val *= 16;
}
else
for (int i = size-1; i >= 0; i--)
{
if (string[i] == '0')
char_val = 0;
if (string[i] == '1')
char_val = 1;
if (string[i] == '2')
char_val = 2;
if (string[i] == '3')
char_val = 3;
if (string[i] == '4')
char_val = 4;
if (string[i] == '5')
char_val = 5;
if (string[i] == '6')
char_val = 6;
if (string[i] == '7')
char_val = 7;
if (string[i] == '8')
char_val = 8;
if (string[i] == '9')
char_val = 9;
if (string[i] == 'a' || string[i] == 'A' )
char_val = 10;
if (string[i] == 'b' || string[i] == 'B' )
char_val = 11;
if (string[i] == 'c' || string[i] == 'C' )
char_val = 12;
if (string[i] == 'd' || string[i] == 'D' )
char_val = 13;
if (string[i] == 'e' || string[i] == 'E' )
char_val = 14;
if (string[i] == 'f' || string[i] == 'F' )
char_val = 15;
value = value + (hchar_val*char_val);
hchar_val *= 16;
}
return value;
}
Esempio di utilizzo:
atoh("F0",2, true);
//Output: 240
atoh("0F",2, false);
//Output: 240
Leggi e Commenta
Tags: Hex String to Integer C
Tool, Editor, IDE e Strumenti per sviluppare PHP
Quale strumento per sviluppare in PHP?
16/07/2011 - In Programmazione - By kingk (art. no 234)Tool, Editor, Ide e strumenti per sviluppare in PHP, HTML e Javascript
La scelta di tool e strumenti per lo sviluppo in PHP, HTML e Javascript è piuttosto vasta, in particolare nel panorama PHP vi segnaliamo 2 utili IDE che semplificano le operazioni si scrittura, debug e sincronizzazione con FTP server o SVN: Netbeans della Oracle Corporation e Eclipse.Meglio Netbeans PHP o Eclipse PHP?
Questi due ambienti di sviluppo open source per PHP sono entrambi di buon livello, tra i due ci ha colpito di più Netbeans che nella versione PHP ha qualche marcia in più, soprattutto per la sua semplicità d'uso, intuitività e ricchezza di utilissime funzioni, Eclipse invece è un pò più macchinoso ma rappresenta comunque una buona alternativa.Con Netbeansci si può facilmente sincronizzare in FTP e fare modifiche al volo sul server remoto dato che questa funzione è nativa ed implementata di default nell'IDE (volendo si può addirittura integrare la sincronizzazione con la funzione salva), con Eclipse questa operazione è più macchinosa e meno intuitiva, bisogna infatti ricorrere a plug-in addizionali non semplicissimi da installare a causa di alcuni bug e da configurare a causa della maschera di configurazione complicata.
Entrambi gli ambienti di sviluppo aiutano il programmatore a compilare funzioni, intendare il codice, ricercare errori, commentare selezioni di testo, rinominare variabili globalmente, ricercare funzioni etc. etc..
Non vi resta che provare Netbeans e Eclipse e fare una scelta!
Leggi e Commenta
Tags: Meglio Netbeans o Eclipse per PHP - Quale tool programma ide per sviluppare in PHP - Miglior IDE PHP - Editor per PHP
Backup e Ripristino MySQL
MySQL Backup e Ripristino i comandi
11/05/2011 - In programmazione - By kingk (art. no 180)Lista comandi mysqldump
In questo articolo elenchiamo i principali comandi per eseguire un backup di un database MySQL, e il ripristino tramite i comandi standard mysqldump e mysql.
DUMP (backup su file .sql) di tutti i database MySQL
mysqldump --user=**** --password=**** -A > /PERCORSO/DUMP.SQL
DUMP (backup su file .sql) di uno o più database MySQL
mysqldump --user=**** --password=**** --databases NOME1_DB NOME2_DB NOME3_DB > /PERCORSO/DUMP.SQL
DUMP (backup su file .sql) di tabelle dentro database MySQL
mysqldump --user=**** --password=**** --databases DB_NOME --tables NOME_TABELLA > /PERCORSO/DUMP.SQL
Ripristino di un database MySQL da DUMP .SQL
mysql --verbose --user=**** --password=**** NOME_DB < /PERCORSO/DUMP.SQL
Leggi e Commenta
Tags: Lista comandi mysqldump - mysqldump ripristino database
Socket Server in C esempio
Un Socket Server Multi CLient In C esempio programmazione
In Programmazione - By kingk (art. no 148)Un esempio di server multi client in C per Linux Echo Server Porta 502
La programmazione con i Socket in C può risultare molto difficoltosa, sopratutto se si intende realizzare un applicazione Server Multi Client.
In questo articolo abbiamo realizzato e allegato il codice C Linux, si tratta di un server multi client.
Questo codice rispetto altri che troverete in rete è molto semplice da comprendere, inoltre funziona piuttosto bene.
Questo software è un echo server che sfrutta i socket di tipo non bloccanti sulla porta 502.
Il funzionamento di questo codice è semplice: Viene creato un array di N socket, gestibili attraverso un loop principale che ne controlla il flusso.
Leggi e Commenta
Esempio socket server multi client in CTags: Socket Server in C esempio - Esempio di server multi client in C - Socket Server C Linux Non bloccante - Esempio no blocking socket C - Socket Server C Linux Non bloccante - Esempio programmazione server in C - I socket in C - Socket in C
Come creare software in Java Me per cellulari
Guida per creare il primo software per cellulari con Netbeans
In Programmazione - By kingk (art. no 71)Tratto dal sito partner Nokia-n9
Breve guida su come creare programmi per Nokia, e tutti i telefonini Java Me compatibili!
La creazione di software per cellulari è un operazione complicata, senza una guida di startup è molto difficile apprendere come creare software per telefonini.
In questa breve guida creeremo un semplice applicativo "Hello World" per telefoni Nokia, la conoscienza di Java non è indispensabile dato che questo è solo uno startup.
Come prima cosa scaricate una versione aggiornata del software Netbeans tra le varie versioni scegliete quella Java, compatibile con Java Me il formato Java per cellulari.
Una volta scaricato Netbeans eseguite il setup, è piuttosto semplice ed intuitivo da installare.
Scaricare quindi il Java JDK framework, questo pacchetto è indispensabile per sviluppare software Java di ogni tipo, dunque installarlo seguendo la procedura setup.
Finalmente siamo pronti!
Possiamo finalmente avviare Netbeans dal menù start di windows, o linux a seconda del vostro sistema operativo.
Una volta avviato Netbeans creiamo un nuovo progetto, selezioniamo dal menù:
File->New Project..
A questo punto scegliamo il tipo di progetto come: "Java Me" e poi "Mobile Application", Netbeans ci chiederà di scegliere il nome del progetto, inseriamo ad esempio: "TestJavaMe"
Nella schermata successiva utilizzeremo come opzioni
CLDC-1.0, e MIDP-2.0 per garantire una miglior compatibilità del nostro software anche con i telefoni più datati.
Questi due parametri sono solitamente indicati nelle caratteristiche tecniche del telefonino, indicano uno specifico set di funzioni del framework Java Me, i telefoni/device più aggiornati supporteranno le versioni più nuove.
Procedete con la creazione del progetto lasciando le impostazioni di default, a questo punto dovreste visualizzare una schermata come questa
Nella finestra di progettazione notiamo diversi tab:
Source, Screen, Flow, Analyzer.
Spostiamoci nella finestra "Screen"
In questo pannello è possibile disegnare la grafica del nostro software, aggiungere componenti, scritte, immagini semplicemende trascinando i controlli all'interno dell'area: Device Screen.
Proviamo a personalizzare il nostro form, selezionate il testo Welcome, e nelle proprietà del form scrivete il titolo: "Guida di http://Nokia-N9.it"
Adesso personalizziamo il controllo di testo con la scritta "Hello World", selezioniamo con il mouse il controllo, spostiamoci nel pannello Proprietà in basso a destra, modifichiamo i campo:
Label in: "Nokia-N9.it vi introduce al.."
Text in: "Vostro primo programma in Java Me!"
Proviamo adesso ad aggiungere il tasto ok nel form, trasciniamolo dala sezione commands, all'interno del nostro form, la lista Assigned Commands dovrebbe contenere il nuovo comando disponibile.
Dovreste ritrovarvi con una schermata come questa
A questo punto proviamo ad inserire del codice Java Me nella nostra applicazione, in questo modo ci sentiremo dei veri programmatori!
Click destro sul okCommand, listato nel gruppo Assigned Commands, selezionare Go To Source, a questo punto si aprirà l'area dove scrivere i comandi della funzione click nel tasto Ok, proviamo a modificare il testo del form inserendo la seguente linea di codice:
stringItem.setText("Tasto ok attivo!");
In questo modo:
Bene adesso non ci resta che provare quanto realizzato, utilizziamo il tasto verde Play per avviare l'emulatore.
Possiamo notare che schiacciando il tasto Ok il testo nella schermata viene modificato:
Ora non ci resta che compilare l'applicazione e installarla nel telefonino tramite usb, bluetooth etc..
Per compilare l'applicazione è sufficiente schiacciare F11
Il programma verrà compilato nella cartella:
Documenti->NetBeansProjects->TestJavaMe(o nome del progetto utilizzato)->dist->TestJavaMe(o nome del progetto utilizzato).jar
Articolo di Ugo Cirmignani
Leggi e Commenta
Tags: Software java per telefonini - Come creare software in java per telefonini - Guida java me - Java per cellulari la guida per lo startup
Una semplice guida per creare programmi per cellulare
Startup nella creazione del vostro primo programma per cellulari in java
In Programmazione - By kingk (art. no 59)Vi segnalamo un interessante guida su come realizzare un software per cellulari in Java Me, seguite l'indirizzo:
http://nokia-n9.it/2010/09/08/come-creare-software-in-java-me-per-cellulari/
Buona programmazione!
Leggi e Commenta
Implementazione dell'algoritmo di Huffman in c/c++
Esempio dell'algoritmo di Huffman in C/C++
In Programmazione - By kingk (art. no 21)In questo articolo viene rilasciato un esempio di implementazione dell'algoritmo di Huffman in C/C++.
Non verrà spiegato invece come funziona l'algoritmo (dato che in rete esistono molte informazioni al riguardo).
Per farla breve comunque il concetto di questo algoritmo è quello di sostituire i simboli più ricorrenti all'interno di un file con dei simboli con valore binario ridotto. I simboli binari per la sostituzione si ottengono creando una struttura dati ad albero particolare: albero di Huffman.
Questo algoritmo è attualmente utilizzato nei più noti software di compressione dati, combinato con altri algoritmi basati sul dizionario (come LZ77).
Questo codice non è particolarmente ottimizzato, tuttavia le prestazioni sono comunque interessanti in termini di velocità.
A differenza di altre implementazioni in questa, l'albero viene memorizzato con un sistema piuttosto efficace che consiste semplicemente in una lista ordinata di simboli all'inizio del file compresso.
Per testare questa implementazione dell'algoritmo di Huffman si può utilizzare lo stesso software con interfaccia grafica proposto nell'articolo riguardante l'implementazione in C/C++ di LZW
Autore: Ugo Cirmignani
Leggi e Commenta
Algoritmo di Huffman in C/C++Tags: Huffman in C - Algoritmi base di compressione dati Huffman - Implementazione Huffman in C
Un implementazione efficace dell'algoritmo LZW in C/C++ by Ugo Cirmignani
Descrizione implementazione ed esempio dell'algoritmo LZW in C/C++
In Programmazione - By kingk (art. no 18)In questo articolo viene illustrato brevemente l'algoritmo LZW, vedremo le insidie ed i consigli per una buona implementazione dell'algoritmo ed una sua buona implementazione in C/C++. Oltre al codice dimostrativo troverete un piccolo software in C++ denominato 'FAC' dotato di interfaccia grafica questo software è capace di comprimere/decomprimere directory in vari formati tra cui LZW con il codice compreso in questo articolo, il software in questione utilizza un algoritmo di concatenamento file per comprimere intere directory in file unici.
Senza soffermarci troppo sulla storia di LZW passiamo a descrivere le caratteristiche principali dell'algoritmo:
-Algoritmo Loseless (nessuna perdita di informazioni con la compressione/decompressione dei files)
-Ottima velocità di compressione/decompressione
-Buon rapporto di compressione
-Principio di funzionamento basato su dizionario (infatti l'algoritmo è un evoluzione del primo noto algoritmo a dizionario: LZ77)
-Possibilità di comprimere dati in streaming senza conoscere i dati prima della compressione
LZW è attualmente utilizzato soprattutto nella compressione delle immagini dei più noti formati di immagini esistenti, è un algoritmo libero da brevetti da non molti anni per questo motivo la sua diffusione è ancora limitata.
L'algoritmo basa il suo funzionamento sul principio di utilizzare un dizionario che viene costruito man mano durante la lettura di un file/stream di dati.
Ma cosa significa utilizzare un dizionario per la compressione file?
Il principio di funzionamento è molto banale, consiste nel sostituire un insieme di simboli ricorrenti con simboli abbreviati nei dati di output.
Per fare un esempio di un algoritmo con dizionario possiamo immaginare di comprimere un SMS sostituendo le parole più utilizzate con dei numeri binari.
Ad esempio utilizzando 16bit potremmo disporre di ben 65535 parole nel nostro nuovo dizionario compresso, più che sufficienti per comporre un SMS.
Il risparmio di questo algoritmo immaginario in termini di dati sarebbe notevole, infatti ogni parola potrebbe occupare solo 2 simboli (in informatica ogni carattere di testo occupa 8bit), con una compressione del genere potremmo arrivare a comporre SMS con un numero di parole quintuplicato rispetto ad un SMS classico.
Sfortunatamente in informatica nella maggior parte dei casi bisogna lavorare con dei dati molto vari e non ricorsivi come delle semplici parole, trovare un algoritmo buono per molte casistiche non è un impresa da poco, ma è proprio quello che LZW garantisce.
Come funziona LZW?
L'algoritmo inizializza in memoria un dizionario di base composto da 256 simboli (tutti i valori che 1 byte può assumere).
L'algoritmo procede leggendo byte dopo byte tutti i dati in ingresso accodandoli tra loro in un buffer al fine di formare simboli finché tali simboli sono presenti nel dizionario e producendo nel caso contrario il valore della posizione occupata dall'ultimo simbolo riscontrato nel buffer come output. I simboli non riscontrati vengono inseriti nel dizionario in maniera dinamica.
Per comprendere meglio il processo prendiamo ad esempio una parola da comprimere formata da 11 caratteri: ABCABEFGHIL
Dopo la prima lettura il buffer in ingresso sarà formato da: A
Il carattere A è un simbolo presente nel dizionario dato che questo è stato inizializzato con tutti i 256 simboli ad 8 bit, se nella memoria di buffer è presente un simbolo riscontrabile nel dizionario l'algoritmo continua la lettura accodando i byte nuovi a quelli che formano il simbolo riscontrato nel buffer.
Nel secondo passaggio l'algoritmo legge B, ed il buffer diventa: AB
AB è un simbolo non presente nel dizionario dato che inizialmente è formato da simboli ad un carattere singolo, a questo punto l'algoritmo inserisce il nuovo simbolo mai riscontrato AB nella prima posizione disponibile nel dizionario ossia la posizione n 257 che conterrà quindi il simbolo AB.
Aggiunto questo simbolo l'algoritmo produrrà un output corrispondente alla posizione dell'ultimo simbolo riscontrato ossia il valore della posizione associato al carattere A precisamente: 65
L'algoritmo procede scartando il simbolo mandato in output dal buffer e accodando il nuovo byte da leggere all'ultimo letto, il buffer diventa cosi BC.
Il nuovo simbolo BC non è presente nel dizionario, l'algoritmo inserisce il nuovo simbolo BC nella posizione 258, come output restituisce sempre il valore della posizione dell'ultimo simbolo riscontrato in questo il valore 66 associato al simbolo B.
Il processo continua e il buffer diventa: CA ma anche il simbolo CA non è presente nel dizionario, l'algoritmo produce come output la posizione del simbolo C cioè : 67 e inserisce il nuovo simbolo CA nella posizione 259
Nel prossimo step il buffer diventa AB, AB è un simbolo presente nel dizionario, l'algoritmo non produce nessun output e continua con la lettura (la compressione ha cosi inizio).
Il buffer diventa quindi: ABE, questo simbolo non è presente nel dizionario in questo caso come output abbiamo 257 (il valore del simbolo AB) il nuovo simbolo inserito nel dizionario è: ABE con valore 260 ed il buffer diventa EF.
L'algoritmo procede in questo modo finché i dati in ingresso non terminano.
La decompressione avviene in modo del tutto analogo alla compressione, ma con qualche piccola differenza facilmente intuibile.
Dal punto di vista logico l'algoritmo è piuttosto semplice da comprendere, dal punto di vista pratico una sua implementazione presenta notevoli difficoltà tecniche:
1) L'uso di memoria deve essere ottimizzato all'interno del codice, bisogna trovare un sistema per memorizzare un dizionario molto vasto in poco spazio dato che è molto facile riempire la ram di un calcolatore con una cattiva implementazione di LZW.
2 ) La ricerca dei simboli nel dizionario deve essere ottimizzata altrimenti il tempo per comprimere dati può rendere l'algoritmo inutilizzabile
3 ) I simboli devono essere scritti in un formato con bit-size variabile a seconda delle dimensioni del dizionario durante la fase di compressione per massimizzare i benefici dell'algoritmo, i linguaggi di programmazione non consentono di scrivere dati in un numero di bit non multiplo di 8 con funzioni convenzionali.
4) Bisogna limitare le dimensioni del dizionario, in informatica la grandezza dei numeri non è illimitata
5) Bisogna resettare il dizionario quando questo diventa pieno o il rapporto di compressione diventa sconveniente, dato che durante la compressione con questo metodo il rapporto di compressione tende molto facilmente al degrado a seconda della porzione di dati da comprimere.
Ho trovato una soluzione per ognuno di questi punti nella mia implementazione dell'algoritmo presente in questo articolo, alcune soluzioni non sono state ottimizzate al 100% per questioni di tempo, ma tuttavia mi ritengo comunque molto soddisfatto di questa mia buona implementazione di LZW
Vediamo bene le soluzioni ai problemi citati:
1)Per limitare lo spazio occupato dal dizionario si può conservare in memoria solamente una lista di coppie di variabili per ogni simbolo del dizionario esattamente una coppia prefisso/ultimo carattere. Si può notare che ogni nuovo simbolo da inserire nel dizionario non è altro che un vecchio simbolo presente nel dizionario con un ultimo carattere in più. Basta quindi memorizzare il valore del vecchio simbolo e il carattere che forma il nuovo simbolo e non memorizzare il nuovo simbolo per intero.
Nel primo passo di memorizzazione dell'esempio precedente l'inserimento del simbolo AB nel dizionario diventa qualcosa del tipo: prefisso 65 carattere B
2)In molte implementazioni di LZW per risolvere i problemi dei tempi di ricerca dei simboli all'interno del dizionario si utilizza un algoritmo di Hash per la ricerca, ma una soluzione simile comporta però molti svantaggi: L'algoritmo di Hash è un ulteriore complicazione all'interno di un codice non molto semplice, è difficile scrivere uno di questi algoritmi in modo perfetto, il costo di un algoritmo del genere poi non è pari a 1 ma può aumentare a seconda del tipo di dizionario che l'algoritmo crea in modo casuale, inoltre questo comporta un necessario incremento della memoria da dedicare al salvataggio del dizionario molte porzioni di memoria verranno sprecate a svantaggio delle capacità massime di compressione. Ho risolto questo punto per l'implementazione di questo algoritmo con una soluzione davvero ottimale che garantisce ricerche ad un costo fisso di 1.
Una soluzione ottimale consiste nello sfruttare al massimo la struttura ipotizzata per memorizzare il dizionario.
Possiamo notare che ogni elemento prefisso-carattere della nostra struttura verrà utilizzato per formare altri simboli del tipo prefisso/carattere+carattere secondo, il numero massimo di simboli derivati non sarà mai superiore a 256 per via dei principi di funzionamento dell'algoritmo.
Si può aggiungere quindi un array di 256 puntatori per ogni coppia prefisso-carattere, questi puntatori punteranno alle coppie derivate da quelle di origine. L'indice di questi puntatori verranno utilizzati con il carattere secondo.
Si può immaginare l'importanza di questa soluzione nella stesura di un implementazione.
3)Per massimizzare gli effetti della compressione bisogna memorizzare i valori dell'output utilizzando solo lo spazio necessario per memorizzarli. Questo significa che nel momento in cui nel dizionario viene aggiunto un simbolo con posizione 257, il valore dovrà occupare solamente 9 Bit di memoria e non 16bit anche se 16bit è la dimensione massima del dizionario, questo ovviamente finché il simbolo più grande del dizionario non avrà bisogno di più bit per la memorizzazione.
Il bit-size dovrà crescere in maniera dinamica a seconda della dimensione temporanea del dizionario, in un implementazione a 16 bit ad esempio il bit-size utilizzato dovrà partire da una grandezza di 9 bit fino a diventare di 16 bit in modo sequenziale in base alle dimensioni del dizionario raggiunte in ogni punto della compressione.
Bisogna realizzare in qualche modo delle procedure per ottenere questo risultato, il metodo più semplice è quello di creare un buffer di bit e scrivere i byte solo quando il buffer diventa multiplo di 8.
4)Le dimensioni del dizionario devono essere definite, il miglior metodo è quello di dare un limite al dizionario in base ad un bit-size, in questo modo non ci saranno informazioni sprecate nell'output compresso. Questo significa che se ad esempio utilizziamo 14 bit il numero massimo di simboli nel dizionario sarà
(2^14) - 1 = 16383 simboli.
5)Per evitare che la compressione degradi una volta che il dizionario è pieno si possono adottare 2 strade:
a) Si resetta il dizionario per tornare alla situazione iniziale nella quale si dispone di 256 simboli, è consigliabile riservare un simbolo nel dizionario per indicare al decompressore che il dizionario a partire dal simbolo speciale è stato resettato
b) Si analizza il rapporto di compressione e si resetta il dizionario ogni qualvolta questo degrada, questa tecnica è più raffinata della prima ma non porta benefici molto rilevanti. Nell'implementazione allegata a questo articolo viene utilizzata la soluzione a.
Autore dell'articolo:
Ugo Cirmignani
Leggi e Commenta
LZW Implementation by Ugo CirmignaniFAC (Fast Archive Creator)Sorgenti Linux
Tags: LZW in C - Comprimere i dati in c - Algoritmo base di compressione dati LZW - Implementazione LZW in C - Realizzare software come winzip - Compressione LZW - Comprimere LZW - Comprimere LZW
Lavorare con i bit in C# .Net
Esempio di programmazione con i bit nell'implemetazione in C# dell'algoritmo Base64
In Programmazione - By kingk (art. no 8)Spesso capita di dover lavorare con i bit, specialmente quando si lavora con i protocolli di comunicazione.
Sfortunatamente nei linguaggi di programmazione ad alto livello a differenza dell'asm, spesso mancano le funzioni giuste per accedere direttamente ai valori dei bit e il dato minimo che si può leggere è il byte.
In questo articolo propongo una semplice classe per il linguaggio di programmazione C# .Net utile per accedere direttamente ai bit di una variabile di tipo byte. Per un ulteriore dimostrazione dell'utilità di questa classe ho implementato anche l'algoritmo Base64 sfruttando i metodi per i bit.
I metodi della classe consentono di :
-Leggere il valore di un bit da un byte
-Settare il valore di un bit in un byte
-Codificare e Decodificare in base64
Spero che questa classe (scaricabile come di consueto) torni utile a qualcuno a presto!
Autore: Ugo Cirmignani
Leggi e Commenta
BIT CLASS C#Tags: Manipolare i bit - Come modificare bit e non byte in c#