Hola a todos estoy analizando un codigo que consegui sobre este algoritmo de huffman, me intereso el tema de compresion, y despues de seguir esta lectura pues observe que tambien era posible el cifrado de datos, asi que los puse en marcha y algunas pequeñas modificaciones que realize, aunque sigue siendo el mismo code.
#include <iostream>
#include <cstdio>
using namespace std;
typedef struct _nodo{
char letra;
int frecuencia;
_nodo *sig;
_nodo *cero;
_nodo *uno;
} tipoNodo;
typedef struct _tabla{
char letra;
unsigned long int bits;
char nbits;
_tabla *sig;
} tipoTabla;
tipoTabla *Tabla;
void Cuenta(tipoNodo* &Lista, char c);
void Ordenar(tipoNodo* &Lista);
void InsertarOrden(tipoNodo* &Cabeza, tipoNodo *e);
void BorrarArbol(tipoNodo *n);
void CrearTabla(tipoNodo *n, int l, int v);
void InsertarTabla(char c, int l, int v);
tipoTabla *BuscaCaracter(tipoTabla *Tabla, char c);
int main(int argc, char *argv[]){
tipoNodo *Lista;
tipoNodo *Arbol;
FILE *fe, *fs;
char c;
tipoNodo *p;
tipoTabla *t;
int nElementos;
long int Longitud = 0;
unsigned long int dWORD;
int nBits;
if(argc < 3)
{
cout<<"\n\tUsar:\n\t"<<argv[0]<<" <fichero_entrada> <fichero_salida>\n";
return 1;
}
Lista = NULL;
fe = fopen(argv[1], "r");
while((c = fgetc(fe)) != EOF){
Longitud++;
Cuenta(Lista, c);
}
fclose(fe);
Ordenar(Lista);
Arbol = Lista;
while(Arbol && Arbol->sig){
p = new(tipoNodo);
p->letra = 0;
p->uno = Arbol;
Arbol = Arbol->sig;
p->cero = Arbol;
Arbol = Arbol->sig;
p->frecuencia = p->uno->frecuencia + p->cero->frecuencia;
InsertarOrden(Arbol, p);
}
Tabla = NULL;
CrearTabla(Arbol, 0, 0);
fs = fopen(argv[2], "wb");
fwrite(&Longitud, sizeof(long int), 1, fs);
nElementos = 0;
t = Tabla;
while(t){
nElementos++;
t = t->sig;
}
fwrite(&nElementos, sizeof(int), 1, fs);
t = Tabla;
while(t)
{
fwrite(&t->letra, sizeof(char), 1, fs);
fwrite(&t->bits, sizeof(unsigned long int), 1, fs);
fwrite(&t->nbits, sizeof(char), 1, fs);
t = t->sig;
}
fe = fopen(argv[1], "r");
dWORD = 0;
nBits = 0;
while((c = fgetc(fe)) != EOF)
{
t = BuscaCaracter(Tabla, c);
while(nBits + t->nbits > 32){
c = dWORD >> (nBits-8);
fwrite(&c, sizeof(char), 1, fs);
nBits -= 8;
}
dWORD <<= t->nbits;
dWORD |= t->bits;
nBits += t->nbits;
}
while(nBits>0){
if(nBits>=8) c = dWORD >> (nBits-8);
else c = dWORD << (8-nBits);
fwrite(&c, sizeof(char), 1, fs);
nBits -= 8;
}
fclose(fe);
fclose(fs);
BorrarArbol(Arbol);
while(Tabla){
t = Tabla;
Tabla = t->sig;
delete(t);
}
return 0;
}
void Cuenta(tipoNodo* &Lista, char c){
tipoNodo *p, *a, *q;
if(!Lista){
Lista = new(tipoNodo);
Lista->letra = c;
Lista->frecuencia = 1;
Lista->sig = Lista->cero = Lista->uno = NULL;
}
else{
p = Lista;
a = NULL;
while(p && p->letra < c){
a = p;
p = p->sig;
}
if(p && p->letra == c) p->frecuencia++;
else{
q = new(tipoNodo);
q->letra = c;
q->frecuencia = 1;
q->cero = q->uno = NULL;
q->sig = p;
if(a) a->sig = q;
else Lista = q;
}
}
}
void Ordenar(tipoNodo* &Lista){
tipoNodo *Lista2, *a;
if(!Lista) return;
Lista2 = Lista;
Lista = NULL;
while(Lista2){
a = Lista2;
Lista2 = a->sig;
InsertarOrden(Lista, a);
}
}
void InsertarOrden(tipoNodo* &Cabeza, tipoNodo *e)
{
tipoNodo *p, *a;
if(!Cabeza){
Cabeza = e;
Cabeza->sig = NULL;
}
else{
p = Cabeza;
a = NULL;
while(p && p->frecuencia < e->frecuencia){
a = p;
p = p->sig;
}
e->sig = p;
if(a) a->sig = e;
else Cabeza = e;
}
}
void CrearTabla(tipoNodo *n, int l, int v){
if(n->uno) CrearTabla(n->uno, l+1, (v<<1)|1);
if(n->cero) CrearTabla(n->cero, l+1, v<<1);
if(!n->uno && !n->cero) InsertarTabla(n->letra, l, v);
}
void InsertarTabla(char c, int l, int v){
tipoTabla *t, *p, *a;
t = new(tipoTabla);
t->letra = c;
t->bits = v;
t->nbits = l;
if(!Tabla){
Tabla = t;
Tabla->sig = NULL;
}
else{
p = Tabla;
a = NULL;
while(p && p->letra < t->letra){
a = p;
p = p->sig;
}
t->sig = p;
if(a) a->sig = t;
else Tabla = t;
}
}
tipoTabla *BuscaCaracter(tipoTabla *Tabla, char c){
tipoTabla *t;
t = Tabla;
while(t && t->letra != c) t = t->sig;
return t;
}
void BorrarArbol(tipoNodo *n){
if(n->cero) BorrarArbol(n->cero);
if(n->uno) BorrarArbol(n->uno);
delete(n);
}
Ahora estuve viendo que la logica era comprimir por que coge solo un digito y si se repite a esta le aumenta la cantidad de veces en un apartado de frecuencias, entonces seguido seria pasarle al arbol, para que reduzca el tamanño en Bits.
Pero note que en una frase de 15 bits, esta llegaba a 72 Bits. (nom comprime ...)
Luego observe que el texto guardado ya no es legible, no se si esto se deba a las funciones archivos:
fs = fopen(argv[2], "wb");
Lo asumi que tal vez este cifrado pero recorde que en archivos la escritura tambien se puede hacer en binario, cosa que aun no me queda, si deberia cifrar comprimir ?
Me da entender que con este algoritmo puedo comprimir el tamaño de la frase en texto plano y dicho sea de paso pueda comprimir/cifrar la informacion.
Ahora luego de encriptarlo vi que si era posible leer al supuesto archivo cifrado asi que decidi usar una forma de leer el archivo asi que use hexdump
y pude ver en el siquiete resultado:
00000000 0f 00 00 00 0c 00 00 00 0a 02 00 00 00 04 31 03 |..............1.|
00000010 00 00 00 04 61 00 00 00 00 04 62 01 00 00 00 04 |....a.....b.....|
00000020 64 06 00 00 00 04 65 03 00 00 00 02 6f 07 00 00 |d.....e.....o...|
00000030 00 04 70 04 00 00 00 04 72 05 00 00 00 04 74 04 |..p.....r.....t.|
00000040 00 00 00 03 75 0a 00 00 00 04 78 0b 00 00 00 04 |....u.....x.....|
00000050 9d c7 6d 16 b1 03 20 |..m... |
00000057
como se puede ver es posible la lectura de los caracteres usados en la supuesta encriptacion.
la frase usada fue:
pruebadetexto1la duda es:
. en realidad esto esta cifrado?
. por que puedo el texto si la idea de huffman es convertilo a binario?
lo digo por que con usando archivos en C, los textos usados para guardarlos en texto plano se guardan en binario y son ilegibles al leerlo.
Saludos.
Mostrar Mensajes
