huffman.cc

  1. /*
  2.   Huffman - Compresión/Expansión de archivos por el método de Huffman
  3.   Copyright (C) 1999 Francisco Cascales <fco@proinf.net>
  4.  
  5.   This program is free software; you can redistribute it and/or modify
  6.   it under the terms of the GNU General Public License as published by
  7.   the Free Software Foundation; either version 2 of the License, or
  8.   (at your option) any later version.
  9.  
  10.   This program is distributed in the hope that it will be useful,
  11.   but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  13.   GNU General Public License for more details.
  14.  
  15.   You should have received a copy of the GNU General Public License along
  16.   with this program; if not, write to the Free Software Foundation, Inc.,
  17.   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18.  */
  19. /*
  20.  * HUFFMAN
  21.  * Compresión/Expansión de ficheros
  22.  * por el método de Huffman.
  23.  * Fco. Cascales <fco@proinf.net>, junio-1999
  24.  *
  25.  * Compilado con DJGPP http://www.delorie.com/djgpp/
  26.  *
  27.  *
  28.  * ALGORITMO:
  29.  *
  30.  * Disponemos de un grupo de mensajes
  31.  * (los códigos ASCII que puedan aparecer) :
  32.  *
  33.  * S = { A1, A2, A3, ... }
  34.  *
  35.  * Y de un alfabeto binario (dígitos binarios) :
  36.  *
  37.  * D = { 0, 1 }
  38.  *
  39.  *
  40.  * 1.- Obtener probabilidades de aparición de cada
  41.  * mensaje.
  42.  *
  43.  * P1, P2, P3, ...
  44.  *
  45.  * 2.- Ordenar los mensajes en orden decreciente de
  46.  * sus probabilidades.
  47.  * 3.- Asignar a los dos últimos mensajes los dígitos
  48.  * binarios 0 y 1.
  49.  * 4.- Obtener un nuevo conjunto de mensajes en el
  50.  * cual los dos últimos mensajes se unen para
  51.  * formar un nuevo mensaje. Su probabilidad es la
  52.  * suma de los dos mensajes de donde procede.
  53.  * 5.- Volver al paso 2 si queda más de un mensaje.
  54.  *
  55.  * Con el proceso anterior hemos construido un  árbol.
  56.  * La codificación del mensaje se obtiene siguiendo el
  57.  * camino desde el nodo raíz hasta el mensaje.
  58.  *
  59.  */
  60.  
  61. //-------------------------------------
  62. // DEPENDENCIAS
  63.  
  64. #include <iostream.h> // <<
  65. #include <stdio.h> /* fopen */
  66. #include <stdlib.h> /* exit, qsort */
  67. #include <string.h> /* strupr */
  68. #include <conio.h> /* gotoxy, getch, textcolor */
  69. #include <math.h> /* ceil */
  70. #include <time.h> /* clock */
  71. #include <ctype.h> /* tolower */
  72. #include <stdarg.h> /* va_start */
  73. #include <pc.h> /* ScreenRows */
  74.  
  75. //-------------------------------------
  76. // MACROS
  77.  
  78. #define NUM_ASCII 256 // Número de códigos ASCII
  79. #define NUM_NODES (NUM_ASCII*2-1) // Número de nodos del árbol
  80. #define ORPHAN -1 // Nodo del árbol sin padre
  81. #define SIZE_BUFFER 65536 // Tamaño del buffer de salida, 1024
  82. #define MAX_CODE (NUM_ASCII/8) // Número máximo de bytes por código
  83. #define MAX_PATH 500 // Tamaño máximo del nombre de un archivo
  84.  
  85. #if (SIZE_BUFFER < NUM_ASCII/8)
  86. #error ­Buffer diminuto!
  87. #endif
  88.  
  89.  
  90. //-------------------------------------
  91. // TIPOS DE DATOS
  92.  
  93. typedef unsigned long int dword; // 32 bits
  94. typedef unsigned char byte; // 8 bits
  95.  
  96. //-------------------------------------
  97. // CLASE PILA DE BITS
  98.  
  99. class BitStack
  100. {
  101. public:
  102.  
  103. BitStack (int size); // Constructor
  104.  
  105. void Push (int bit); // Apila un bit
  106.  
  107. int Pop (); // Desapila un bit
  108.  
  109. void Subtract (int size); // Resta primeros bytes y ajusta la pila
  110.  
  111. void Add (byte *base, int size); // Agrega nuevos bytes y ajusta la pila
  112.  
  113. long Top ()
  114. {
  115. return topBit;
  116. }
  117.  
  118. byte *GetBuffer ()
  119. {
  120. return buffer;
  121. }
  122.  
  123. static void ReverseBits (byte *base, int n); // Invierte bits
  124.  
  125. private:
  126.  
  127. long topBit; // Pointer to current bit
  128. long noBytes; // Size of stack
  129. byte *buffer; // Stack
  130.  
  131. };
  132.  
  133.  
  134. //-------------------------------------
  135. // CLASE NODO HUFFMAN
  136.  
  137. class Node
  138. {
  139. public:
  140.  
  141. Node ()
  142. {
  143. parent = ORPHAN;
  144. weight = 0;
  145. child0 = ORPHAN;
  146. child1 = ORPHAN;
  147. }
  148.  
  149. int parent; // padre
  150. dword weight; // peso
  151. byte bit; // 0 o 1
  152. int child0; // hijo 0
  153. int child1; // hijo 1
  154. };
  155.  
  156. //-------------------------------------
  157. // CLASE CODIGO HUFFMAN
  158.  
  159.  
  160. class Code // No usado
  161. {
  162. public:
  163.  
  164. Code ()
  165. {
  166. bit = NULL;
  167. numBits = 0;
  168. }
  169.  
  170. char *bit; // Cadena de 1 y 0
  171. int numBits;
  172. };
  173.  
  174.  
  175. //-------------------------------------
  176. // CLASE HUFFMAN
  177.  
  178. class Huffman
  179. {
  180. public:
  181.  
  182. Huffman ();
  183.  
  184. void CompressFile (char *filename);
  185. void ExpandFile (char *filename);
  186.  
  187. void ShowStatistics (char *filename);
  188. void ShowTree (char *filename);
  189.  
  190. void SetColor (bool flag) { colored = flag; }
  191. void SetSortASCII (bool flag) { sortASCII = flag; }
  192. void SetVerbose (bool verbose) { this->verbose = verbose; }
  193.  
  194. private:
  195.  
  196. void MakeTree (); // Crea el árbol a partir de los pesos
  197.  
  198. void ReadProbability (char *filename); // Pesos de un archivo
  199. dword ReadHeader (char *filename); // Pesos de un archivo de Huffman
  200.  
  201. void WriteHeader (FILE *f); // Cabecera de un archivo de Huffman
  202.  
  203. void CalculeCodes (); // No usado
  204.  
  205. static bool IsHuffmanFile (char *filename); // ¨Tiene extensión .huf ?
  206.  
  207. void ShowBranch (int index, int level, int bit); // Una rama del árbol
  208. double PerCentNode (int index); // Tanto por ciento de un nodo
  209. double PerCentCompress (dword totalBits); // Porcentaje de compresión
  210. void Write (int color, char *format, ...); // Escribe un texto
  211.  
  212. private:
  213.  
  214. int root; // Nodo raíz del árbol
  215.  
  216. Node nodes [NUM_NODES]; // El árbol (los primeros 256 son el código ASCII)
  217. int sorted [NUM_NODES]; // Indices del árbol ordenados por pesos.
  218.  
  219. private:
  220.  
  221. Code codes [NUM_ASCII]; // No usado
  222.  
  223. private:
  224.  
  225. char fileOriginal [MAX_PATH]; // Nombre del archivo original
  226. char fileHuffman [MAX_PATH]; // Nombre del archivo comprimido
  227.  
  228. const static char EXT_HUF[] = ".huf"; // Extensión asociada
  229. const static char ID_HUFFMAN[] = "HUFFMAN (f)\x1A"; // Identificador de un archivo de Huffman
  230.  
  231. dword sumBytes; // Suma de los bytes del archivo original
  232.  
  233. private:
  234.  
  235. // Para estadísticas y árbol:
  236. bool colored; // En color, pero no redireccionable
  237. bool sortASCII; // Orden ASCII en vez de orden por pesos
  238. bool verbose; // Muestra más información
  239. };
  240.  
  241.  
  242. //-------------------------------------
  243. // VARIABLES GLOBALES
  244.  
  245.  
  246. //-------------------------------------
  247. // DECLARACION DE FUNCIONES
  248.  
  249. // Primarias
  250. void MostrarAyuda ();
  251. void ProcesarArgumentos (int numArgs, char *args[]);
  252.  
  253. // Generales
  254. char *ChangeExt (char *archivo, const char *nuevaExt);
  255. char *GetExt (char *archivo);
  256. void Error (char *mensaje);
  257.  
  258. char *reverse (char *cadena);
  259. char *str (dword num);
  260. char *binary (int byte);
  261.  
  262. void ElTiempoNoPasaEnBalde ();
  263.  
  264.  
  265. //-------------------------------------
  266. // FUNCIONES PRIMARIAS
  267.  
  268. /**
  269.  * Función principal
  270.  */
  271. int main (int argc, char *argv[])
  272. {
  273. ProcesarArgumentos (argc, argv);
  274. return 0;
  275. }
  276.  
  277. /**
  278.  * Uso de este programa
  279.  */
  280. void MostrarAyuda ()
  281. {
  282. puts (
  283. "HUFFMAN, Fco. Cascales (f) junio-1999, v0.1\n"
  284. "Compresión/Expansión de ficheros.\n"
  285. "\n"
  286. "Sintaxis: huffman argumentos archivos\n"
  287. "\n"
  288. "Argumentos:\n"
  289. " -e Expandir un archivo huffman\n"
  290. " -c Comprimir en un archivo huffman\n"
  291. "\n"
  292. " -s Estadísticas de un archivo\n"
  293. " -t Arbol binario de un archivo\n"
  294. "\n"
  295. " -a ANSI (sin color)\n"
  296. " -o Ordenar por ASCII\n"
  297. " -v Más información\n"
  298. );
  299. }
  300.  
  301.  
  302. /**
  303.  * Procesar argumentos en línea de comandos
  304.  *
  305.  */
  306. void ProcesarArgumentos (int numArgs, char *args[])
  307. {
  308. const int USADO = 0x0001;
  309. const int EXPANDIR = 0x0002;
  310. const int COMPRIMIR = 0x0004;
  311. const int ESTADIST = 0x0008;
  312. const int ARBOLBIN = 0x0010;
  313. const int SINCOLOR = 0x0020;
  314. const int ORDENADO = 0x0040;
  315. const int VERBOSE = 0x0080;
  316.  
  317. int flag = 0x0000;
  318.  
  319. for (int i=1; i<numArgs; ++i)
  320. {
  321. if (args[i][0] == '-' || args[i][0] == '/')
  322. {
  323. switch (tolower (args[i][1]))
  324. {
  325. case 'x':
  326. case 'e': flag |= EXPANDIR; break;
  327. case 'c': flag |= COMPRIMIR; break;
  328. case 's': flag |= ESTADIST; break;
  329. case 't': flag |= ARBOLBIN; break;
  330. case 'a': flag |= SINCOLOR; break;
  331. case 'o': flag |= ORDENADO; break;
  332. case 'v': flag |= VERBOSE; break;
  333. default:
  334. printf ("El argumento %s es incorrecto.\n", args[i]);
  335. }
  336. }
  337. else
  338. {
  339. Huffman huffman;
  340.  
  341. try {
  342.  
  343. huffman.SetColor ((flag & SINCOLOR) == 0);
  344. huffman.SetSortASCII ((flag & ORDENADO) != 0);
  345. huffman.SetVerbose ((flag & VERBOSE) != 0);
  346.  
  347. if (flag & EXPANDIR) huffman.ExpandFile (args[i]); else
  348. if (flag & COMPRIMIR) huffman.CompressFile (args[i]); else
  349. if (flag & ESTADIST) huffman.ShowStatistics (args[i]); else
  350. if (flag & ARBOLBIN) huffman.ShowTree (args[i]);
  351.  
  352. }
  353. catch (char const * message)
  354. {
  355. cout << endl << "Error: " << message << endl;
  356. }
  357.  
  358. //flag = USADO;
  359. printf ("\n");
  360. }
  361. }
  362. if (flag == 0x0000)
  363. {
  364. MostrarAyuda ();
  365. }
  366. }
  367.  
  368.  
  369. //-------------------------------------
  370. // FUNCIONES GENERALES
  371.  
  372.  
  373. /**
  374.  * Formateo de una cadena con par metros
  375.  * Ejemplo: puts (format ("Num %d", 4));
  376.  */
  377. char *format (char *format, ...)
  378. {
  379. va_list arg;
  380. static char buffer[256];
  381.  
  382. va_start(arg, format);
  383. vsprintf(buffer, format, arg);
  384. va_end(arg);
  385.  
  386. return buffer;
  387. }
  388.  
  389.  
  390. /**
  391.  * Cambia la extensión del archivo
  392.  *
  393.  * Ejemplo:
  394.  * strcpy (archivo, "c:\dir\pepe.txt");
  395.  * ChangeExt (archivo, ".txt");
  396.  * printf (archivo);
  397.  */
  398. char *ChangeExt (char *archivo, const char *nuevaExt)
  399. {
  400. #if 0
  401. char drive[MAXDRIVE];
  402. char dir[MAXDIR];
  403. char file[MAXFILE];
  404. char ext[MAXEXT];
  405.  
  406. fnsplit (archivo, drive, dir, file, ext);
  407. fnmerge (archivo, drive, dir, file, nuevaExt);
  408.  
  409. return archivo;
  410. #else
  411. int length = strlen (archivo);
  412.  
  413. for (int i=length-1; i>0; --i)
  414. {
  415. if (archivo[i] == '.')
  416. {
  417. strncpy (archivo+i, nuevaExt, length-i+1);
  418. break;
  419. }
  420. }
  421. return archivo;
  422. #endif
  423. }
  424.  
  425. /**
  426.  * Obtiene la extensión del archivo
  427.  * Ejemplo: GetExt ("c:\dir\pepe.txt") --> ".txt"
  428.  */
  429. char *GetExt (char *archivo)
  430. {
  431. #if 0
  432. char drive[MAXDRIVE];
  433. char dir[MAXDIR];
  434. char file[MAXFILE];
  435. static char ext[MAXEXT];
  436.  
  437. fnsplit( archivo, drive, dir, file, ext );
  438.  
  439. return ext;
  440. #else
  441. static char ext[10] = "";
  442.  
  443. for (int i=strlen(archivo)-1; i>0; --i)
  444. {
  445. if (archivo[i] == '.')
  446. {
  447. strncpy (ext, archivo+i, 10);
  448. ext[10-1] = '\0';
  449. }
  450. }
  451. return ext;
  452. #endif
  453. }
  454.  
  455.  
  456. #if 0
  457. /**
  458.  * Mensaje de error
  459.  */
  460. void Error (char *mensaje)
  461. {
  462. cerr << "ERROR: " << mensaje << endl;
  463. //fcloseall();
  464. exit (1);
  465. }
  466. #endif
  467.  
  468.  
  469. /**
  470.  * Invierte una cadena.
  471.  * Ejemplo: "PEPITO" pasa a ser "OTIPEP".
  472.  * Uso : printf ("%s", reverse("PEPITO"));
  473.  */
  474. char *reverse (char *cadena)
  475. {
  476. char *inicio = cadena;
  477. char *fin = cadena + strlen(cadena) - 1;
  478.  
  479. while (inicio < fin)
  480. {
  481. char temp = *inicio;
  482. *inicio = *fin;
  483. *fin = temp;
  484.  
  485. ++inicio;
  486. --fin;
  487. }
  488. return cadena;
  489. }
  490.  
  491. /**
  492.  * Convierte un número entero en cadena
  493.  * incluyendo puntos de millares.
  494.  *
  495.  * Ejemplo: 1234567 pasa a ser "1.234.567"
  496.  * Uso : printf ("%s", str (1234567));
  497.  * Nota : el buffer devuelto siempre es
  498.  * el mismo; es decir no se debe
  499.  * utilizar más de una vez en una
  500.  * instrucción printf (u otra).
  501.  */
  502. char *str (dword num)
  503. {
  504. static char cadena [25];
  505. int i = 0;
  506. int cifras = 0;
  507. int trio=0;
  508.  
  509. for (;;)
  510. {
  511. byte digito = (byte)(num % 10);
  512. cadena[i++] = digito + '0';
  513. num /= 10;
  514.  
  515. if (num == 0) break;
  516.  
  517. if (++trio == 3)
  518. {
  519. cadena[i++] = '.';
  520. trio = 0;
  521. }
  522. }
  523. cadena[i] = '\0';
  524.  
  525. return reverse (cadena);
  526. }
  527.  
  528.  
  529. /**
  530.  * Retorna una cadena con 1 y 0
  531.  * que es el número binario del argumento.
  532.  *
  533.  * Ejemplo: 0x36 --> "00110110"
  534.  */
  535. char *binary (int byte)
  536. {
  537. unsigned char uno;
  538. static char buffer[8+1];
  539. char *s = buffer;
  540.  
  541. byte &= 0xFF;
  542.  
  543. for (uno=0x80; uno; uno>>=1 )
  544. {
  545. *s++ = ((byte & uno) ? '1' : '0');
  546. }
  547. *s = '\0';
  548.  
  549. return buffer;
  550. }
  551.  
  552.  
  553. /**
  554.  * Cada segundo muestra un carácter nuevo
  555.  * en pantalla.
  556.  *
  557.  * Ejemplo: -*-*-*-*
  558.  * Uso : Se usa dentro del bucle de un
  559.  * algoritmo que requiera mucho
  560.  * tiempo de proceso. Así el usuario
  561.  * percibe que el ordenador no se
  562.  * ha quedado bloqueado.
  563.  */
  564. void ElTiempoNoPasaEnBalde ()
  565. {
  566. #if 1
  567. static clock_t startTime = 0;
  568. static char c = '*';
  569. clock_t endTime = clock ();
  570.  
  571. // Si ha pasado un segundo...
  572. if ((endTime-startTime)/CLOCKS_PER_SEC >= 1)
  573. {
  574. startTime = endTime;
  575. putch (c);
  576. //gotoxy (wherex()-1, wherey()); // El carácter en el mismo sitio
  577. c = (c == '*') ? '-' : '*';
  578. }
  579. #endif
  580. }
  581.  
  582. char *specialASCII [32+1] =
  583. {
  584. "NUL", // 0 Character Null
  585. "SOH", // 1 Start of Header
  586. "STX", // 2 Start of Text
  587. "ETX", // 3 End of Text
  588. "EOT", // 4 End of Transmission
  589. "ENQ", // 5 Enquiry
  590. "ACK", // 6 Acknowledge
  591. "BEL", // 7 Bell
  592. "BS", // 8 Backspace
  593. "HT", // 9 Horizontal Tab
  594. "LF", // 10 Line Feed
  595. "VT", // 11 Vertical Tab
  596. "FF", // 12 Form Feed
  597. "CR", // 13 Carriage Return
  598. "SO", // 14 Shift Out
  599. "SI", // 15 Shift In
  600. "DLE", // 16 Data Link Escape
  601. "DC1", // 17 Device Control 1
  602. "DC2", // 18 Device Control 2
  603. "DC3", // 19 Device Control 3
  604. "DC4", // 20 Device Control 4
  605. "NAK", // 21 Negative Acknowledge
  606. "SYN", // 22 Synchronous Idle
  607. "ETB", // 23 End of Transmission Block
  608. "CAN", // 24 Cancel
  609. "EM", // 25 End of Medium
  610. "SUB", // 26 Substitute
  611. "ESC", // 27 Escape
  612. "FS", // 28 File Separator
  613. "GS", // 29 Group Separator
  614. "RS", // 30 Record Separator
  615. "US", // 31 Unit Separator
  616.  
  617. "DEL" // ­127! Delete
  618. };
  619.  
  620.  
  621. /**
  622.  * Convierte un char en un string
  623.  *
  624.  * Ejemplos:
  625.  * ascii(97) --> "a"
  626.  * ascii(13) --> "CR"
  627.  */
  628. char *ascii (int c)
  629. {
  630. static char buffer[4];
  631.  
  632. if (c < 32)
  633. {
  634. strcpy (buffer, specialASCII[c]);
  635. }
  636. else if (c == 127)
  637. {
  638. strcpy (buffer, specialASCII[32]);
  639. }
  640. else
  641. {
  642. buffer[0] = c;
  643. buffer[1] = '\0';
  644. }
  645. return buffer;
  646. }
  647.  
  648.  
  649. //-------------------------------------
  650. // METODOS DE ARBOL DE HUFFMAN
  651.  
  652. /**
  653.  * Constructor del árbol de Huffman
  654.  */
  655. Huffman::Huffman ()
  656. {
  657. for (int i=0; i<NUM_NODES; ++i)
  658. {
  659. //nodes[i].parent = ORPHAN;
  660. //nodes[i].weight = 0;
  661.  
  662. sorted[i] = i; // Todos los índices del árbol
  663. }
  664.  
  665. root = ORPHAN;
  666.  
  667. strcpy (fileOriginal, "<no asignado>");
  668. strcpy (fileHuffman, "<no asignado>");
  669.  
  670. colored = true;
  671. sortASCII = false;
  672. verbose = false;
  673.  
  674. sumBytes = 0;
  675. }
  676.  
  677. /**
  678.  * Indica si es un archivo de Huffman
  679.  * mirando su extensión
  680.  */
  681. bool Huffman::IsHuffmanFile (char *filename)
  682. {
  683. int lenFile = strlen (filename);
  684. int lenExt = strlen (EXT_HUF);
  685.  
  686. if (lenFile < lenExt)
  687. {
  688. return false;
  689. }
  690. else
  691. {
  692. return
  693. stricmp (filename+lenFile-lenExt, EXT_HUF)
  694. == 0;
  695. }
  696. }
  697.  
  698. /**
  699.  * Orden creciente de pesos
  700.  * Función utilizada por 'qsort'.
  701.  */
  702. Node *nodesToCompare;
  703. int Compare (const void *a, const void *b)
  704. {
  705. dword weightA = nodesToCompare[*(int *)a].weight;
  706. dword weightB = nodesToCompare[*(int *)b].weight;
  707.  
  708. if (weightA > weightB) return +1; else
  709. if (weightA < weightB) return -1; else
  710. return 0;
  711. }
  712.  
  713. /**
  714.  * Crea el árbol
  715.  *
  716.  * Es el algoritmo de HUFFMAN propiamente dicho.
  717.  * Cuando se llega aquí ya se han de saber los
  718.  * pesos (probabilidades) de cada código ASCII.
  719.  * La salida es el árbol de codificación/decodificación.
  720.  */
  721. void Huffman::MakeTree ()
  722. {
  723. int numNodes = NUM_ASCII; // Número actual de nodos en el árbol.
  724. int parent = NUM_ASCII; // Nodo padre actual.
  725.  
  726.  
  727. for (int i=0; numNodes>1; --numNodes, ++parent)
  728. {
  729. // Ordenar en orden creciente de probabilidades
  730. nodesToCompare = nodes;
  731. qsort (sorted+i, numNodes, sizeof(int), Compare);
  732.  
  733. // Fuera los que son de peso cero
  734.  
  735. if (numNodes == NUM_ASCII)
  736. {
  737. for (i=0; i<NUM_NODES; ++i)
  738. {
  739. if (nodes[sorted[i]].weight)
  740. {
  741. numNodes -= i;
  742. break;
  743. }
  744. }
  745. }
  746.  
  747. // Los índices de peso más bajo
  748.  
  749. int cero = sorted[i++];
  750. int uno = sorted[i++];
  751.  
  752. nodes[cero].bit = 0;
  753. nodes[uno].bit = 1;
  754.  
  755. nodes[cero].parent = parent;
  756. nodes[uno].parent = parent;
  757.  
  758. nodes[parent].weight = nodes[cero].weight + nodes[uno].weight;
  759. nodes[parent].child0 = cero;
  760. nodes[parent].child1 = uno;
  761. }
  762.  
  763. root = parent-1;
  764. }
  765.  
  766. /**
  767.  * Escribe con color (no ANSI) o sin color (ANSI)
  768.  *
  769.  * Ejemplo: Write (LIGHTRED, "Tamaño %u\n", 1200);
  770.  *
  771.  * Notas:
  772.  * -Sin color se puede redireccionar la salida
  773.  * -Hace pausas autom ticamente cuando es en color
  774.  */
  775. void Huffman::Write (int color, char *format, ...)
  776. {
  777. va_list arg;
  778. char buffer[256];
  779. static int lineas=0;
  780. char *s;
  781.  
  782. va_start(arg, format);
  783. vsprintf(buffer, format, arg);
  784.  
  785.  
  786. if (colored) // Guai del Paraguay
  787. {
  788. textcolor (color);
  789.  
  790. for (s=buffer; *s; ++s)
  791. {
  792. if (*s == '\n') // Los cambios de línea son "\r\n"
  793. {
  794. cprintf ("\r");
  795. }
  796.  
  797. cprintf ("%c", *s); // El texto letra a letra
  798.  
  799. if (*s == '\n') // Es otra línea
  800. {
  801. ++lineas;
  802.  
  803. if (lineas >= ScreenRows()-2) // Demasiadas líneas
  804. {
  805. lineas = 0;
  806.  
  807. textcolor (LIGHTGRAY);
  808. cprintf("<pausa>");
  809. textcolor (color);
  810.  
  811. if (getch () == 27)
  812. {
  813. throw "Interrumpido por el usuario";
  814. }
  815. cprintf ("\r\n");
  816. //gotoxy (1, wherey()-1);
  817. }
  818. }
  819. }
  820. }
  821. else // El de toda la vida
  822. {
  823. for (s=buffer; *s; ++s)
  824. {
  825. printf ("%c", *s); // El texto letra a letra
  826. }
  827. }
  828.  
  829. va_end(arg);
  830. }
  831.  
  832.  
  833. /**
  834.  * Dibuja una rama del árbol
  835.  * Función recursiva que se inicia
  836.  * en el m‚todo ShowTree
  837.  *
  838.  * Par metros:
  839.  * index = nodo del árbol
  840.  * level = profundidad de la recursividad
  841.  * bit = rama 0 o rama 1
  842.  */
  843. void Huffman::ShowBranch (int index, int level, int bit)
  844. {
  845. static char slash [256*3] = ""; // tajo; ramas precedentes
  846.  
  847. if (nodes[index].weight)
  848. {
  849. if (level == 0) // Raíz
  850. {
  851. Write (LIGHTGRAY, "ÀÄ");
  852. }
  853. else if (bit == 1) // Rama 1
  854. {
  855. for (int i=0; i<strlen(slash)-1; ++i)
  856. {
  857. Write (LIGHTGRAY, "%c", slash[i]);
  858. }
  859. Write (LIGHTGRAY, "À");
  860. Write (LIGHTCYAN, "1");
  861. Write (LIGHTGRAY, "Ä");
  862.  
  863. }
  864. else if (bit == 0) // Rama 0
  865. {
  866. Write (LIGHTCYAN, "0");
  867. Write (LIGHTGRAY, "Ä");
  868. }
  869.  
  870. if (index < 256) // Nodo
  871. {
  872. Write (LIGHTGRAY, "Ä");
  873. Write (LIGHTGREEN, "x%02X", index);
  874.  
  875. if (verbose)
  876. {
  877. Write (LIGHTGRAY, "Ä");
  878. Write (CYAN, "%s", ascii (index));
  879.  
  880. Write (LIGHTGRAY, "Ä");
  881. Write (GREEN, "%6.2f%%", PerCentNode (index));
  882.  
  883. Write (LIGHTGRAY, "Ä");
  884. Write (CYAN, "%sb", str (nodes[index].weight));
  885. }
  886.  
  887. Write (LIGHTGRAY, "\n");
  888. }
  889. else // Bifurcación
  890. {
  891. Write (LIGHTGRAY, "Â");
  892.  
  893. int child0 = nodes[index].child0;
  894. int child1 = nodes[index].child1;
  895.  
  896. if (child0 != ORPHAN) // Ir a la rama 0
  897. {
  898. strcat (slash, " ³");
  899. ShowBranch (child0, level+1, 0);
  900. slash[strlen (slash) - 3] = '\0';
  901. }
  902. if (child1 != ORPHAN) // Ir a la rama 1
  903. {
  904. strcat (slash, " ");
  905. ShowBranch (child1, level+1, 1);
  906. slash[strlen (slash) - 3] = '\0';
  907. }
  908. }
  909. }
  910. }
  911.  
  912. /**
  913.  * Visualiza la estructura del árbol
  914.  */
  915. void Huffman::ShowTree (char *filename)
  916. {
  917. if (IsHuffmanFile (filename))
  918. {
  919. ReadHeader (filename);
  920. }
  921. else
  922. {
  923. ReadProbability (filename);
  924. }
  925.  
  926. Write (LIGHTGRAY, "\nArbol binario de %s\n³\n", filename);
  927.  
  928. ShowBranch (root, 0, -1);
  929.  
  930. // Restablecer color normal
  931. Write (LIGHTGRAY, " \n");
  932. }
  933.  
  934.  
  935. /**
  936.  * Grabar el encabezado del archivo de Huffman
  937.  *
  938.  */
  939. void Huffman::WriteHeader (FILE *f)
  940. {
  941. dword contador=0;
  942. dword i;
  943.  
  944.  
  945. // 1.- Identificador
  946.  
  947. fputs (ID_HUFFMAN, f); fputc (0, f);
  948.  
  949. // 2.- Nombre del fichero original
  950.  
  951. fputs (fileOriginal, f); fputc (0, f);
  952.  
  953. // 3.- Suma de los bytes del archivo original
  954.  
  955. fwrite (&sumBytes, sizeof(dword), 1, f);
  956.  
  957. // 4.- Número de códigos ASCII v lidos
  958.  
  959. for (i=0; i<NUM_ASCII; ++i)
  960. {
  961. if (nodes[i].weight != 0)
  962. {
  963. ++contador;
  964. }
  965. }
  966.  
  967. fwrite (&contador, sizeof(dword), 1, f);
  968.  
  969. // 5.- Escribir códigos ASCII con sus pesos
  970.  
  971. for (i=0; i<NUM_ASCII; ++i)
  972. {
  973. if (nodes[i].weight != 0)
  974. {
  975. fputc ((byte)i, f);
  976. fwrite (&nodes[i].weight, sizeof(dword), 1, f);
  977. }
  978. }
  979. }
  980.  
  981.  
  982. /**
  983.  * Leemos la cabecera del archivo de Huffman
  984.  *
  985.  */
  986. dword Huffman::ReadHeader (char *filename)
  987. {
  988. FILE *f;
  989. char buffer [MAX_PATH] = "";
  990. dword contador;
  991. dword i;
  992. dword length=0;
  993.  
  994.  
  995. if ((f = fopen (filename, "rb")) == NULL)
  996. {
  997. throw format ("No encuentro \"%s\"", filename);
  998. }
  999. else
  1000. {
  1001. strcpy (fileHuffman, filename);
  1002. }
  1003.  
  1004.  
  1005. // 1.- Leer identificador
  1006.  
  1007. for (i=0; i<MAX_PATH; ++i)
  1008. {
  1009. buffer [i] = fgetc (f);
  1010.  
  1011. if (buffer[i] == 0)
  1012. {
  1013. break;
  1014. }
  1015. }
  1016. if (!strcmp (buffer, ID_HUFFMAN))
  1017. {
  1018. length += (i+1);
  1019. }
  1020. else
  1021. {
  1022. fclose (f);
  1023. throw format ("El archivo \"%s\" no es de Huffman", fileHuffman);
  1024. }
  1025.  
  1026.  
  1027. // 2.- Leer nombre del fichero original
  1028.  
  1029. for (i=0; i<MAX_PATH; ++i)
  1030. {
  1031. buffer[i] = fgetc (f);
  1032.  
  1033. if (buffer[i] == 0)
  1034. {
  1035. length += (i+1);
  1036. strcpy (fileOriginal, buffer);
  1037. break;
  1038. }
  1039. }
  1040.  
  1041. // 3.- Leer suma de los bytes del archivo original
  1042.  
  1043. fread (&sumBytes, sizeof(dword), 1, f);
  1044. length += sizeof (dword);
  1045.  
  1046. // 4.- Número de códigos ASCII
  1047.  
  1048. fread (&contador, sizeof(dword), 1, f);
  1049. length += sizeof (dword);
  1050.  
  1051. // 5.- Leer códigos ASCII con sus pesos
  1052.  
  1053. for (i=0; i<contador; ++i)
  1054. {
  1055. int code = fgetc (f);
  1056.  
  1057. if (nodes[code].weight != 0)
  1058. {
  1059. fclose (f);
  1060. throw format ("Código repetido");
  1061. }
  1062.  
  1063. fread (&nodes[code].weight, sizeof(dword), 1, f);
  1064.  
  1065. length += (sizeof(char) + sizeof(dword));
  1066. }
  1067.  
  1068. fclose (f);
  1069.  
  1070. MakeTree ();
  1071.  
  1072. return length;
  1073. }
  1074.  
  1075.  
  1076. /**
  1077.  * Comprime el archivo
  1078.  */
  1079. void Huffman::CompressFile (char *filename)
  1080. {
  1081. BitStack stackCode (MAX_CODE);
  1082. BitStack stackOut (SIZE_BUFFER + MAX_CODE);
  1083.  
  1084. FILE *in; // input file
  1085. FILE *out; // output file
  1086. int code; // input character
  1087. dword totalBits=0;
  1088.  
  1089.  
  1090. ReadProbability (filename);
  1091.  
  1092. strcpy (fileHuffman, filename);
  1093. ChangeExt (fileHuffman, EXT_HUF);
  1094.  
  1095.  
  1096. if ((out = fopen (fileHuffman, "wb")) == NULL)
  1097. {
  1098. throw format ("No puedo escribir en \"%s\"", fileHuffman);
  1099. }
  1100. else
  1101. {
  1102. WriteHeader (out);
  1103. }
  1104.  
  1105. if ((in = fopen (fileOriginal, "rb")) == NULL)
  1106. {
  1107. fclose (out);
  1108. throw format ("No puedo abrir \"%s\"", fileOriginal);
  1109. }
  1110.  
  1111. printf ("Comprimiendo \"%s\" en \"%s\" ", fileOriginal, fileHuffman);
  1112.  
  1113. while ((code = fgetc (in)) != EOF)
  1114. {
  1115. // Read code of input character.
  1116. do
  1117. {
  1118. /*if (code == ORPHAN)
  1119.   {
  1120.   throw "Carácter sin código";
  1121.   }*/
  1122.  
  1123. stackCode.Push (nodes[code].bit);
  1124. code = nodes[code].parent;
  1125.  
  1126. } while (code != root);
  1127.  
  1128. // Send the bits to output.
  1129. while (stackCode.Top())
  1130. {
  1131. stackOut.Push (stackCode.Pop ());
  1132.  
  1133. ++totalBits;
  1134. }
  1135.  
  1136. // Send bytes to output file.
  1137. if (stackOut.Top () / 8 >= SIZE_BUFFER)
  1138. {
  1139. size_t sizeBuffer = fwrite (stackOut.GetBuffer (), sizeof(char), SIZE_BUFFER, out);
  1140. stackOut.Subtract (sizeBuffer);
  1141. }
  1142.  
  1143. ElTiempoNoPasaEnBalde ();
  1144. }
  1145.  
  1146. // Send last bytes to output file.
  1147. if (stackOut.Top ())
  1148. {
  1149. fwrite (stackOut.GetBuffer(), sizeof(char), stackOut.Top()/8+1, out);
  1150. }
  1151.  
  1152. fclose (in);
  1153. fclose (out);
  1154.  
  1155. printf ("%6.2f%%", PerCentCompress (totalBits));
  1156. }
  1157.  
  1158.  
  1159. /**
  1160.  * Expande el fichero
  1161.  */
  1162. void Huffman::ExpandFile (char *filename)
  1163. {
  1164. FILE *in;
  1165. FILE *out;
  1166. dword sizeFile; // Size of original file
  1167. size_t sizeBuffer; // Size of buffer
  1168. byte buffer[SIZE_BUFFER]; // Buffer input file
  1169. dword sumCheck=0;
  1170.  
  1171. BitStack stackIn (SIZE_BUFFER + MAX_CODE);
  1172.  
  1173.  
  1174. dword offset = ReadHeader (filename);
  1175.  
  1176.  
  1177. if ((in = fopen (fileHuffman, "rb")) == NULL)
  1178. {
  1179. throw format ("No puedo abrir \"%s\"", fileHuffman);
  1180. }
  1181. else
  1182. {
  1183. fseek (in, offset, SEEK_SET);
  1184. }
  1185.  
  1186.  
  1187. if ((out = fopen (fileOriginal, "wb")) == NULL)
  1188. {
  1189. fclose (in);
  1190. throw format ("No puedo escribir en \"%s\"", fileOriginal);
  1191. }
  1192.  
  1193. printf ("Expandiendo \"%s\" en \"%s\" ", fileHuffman, fileOriginal);
  1194.  
  1195.  
  1196. for (sizeFile = nodes[root].weight; sizeFile; --sizeFile)
  1197. {
  1198. // Get bytes to input file
  1199. if (stackIn.Top() / 8 < MAX_CODE)
  1200. {
  1201. sizeBuffer = fread (buffer, sizeof(char), SIZE_BUFFER, in);
  1202. BitStack::ReverseBits (buffer, sizeBuffer);
  1203. stackIn.Add (buffer, sizeBuffer);
  1204. }
  1205.  
  1206. int code = root;
  1207. do
  1208. {
  1209. if (stackIn.Pop ())
  1210. {
  1211. code = nodes[code].child1;
  1212. }
  1213. else
  1214. {
  1215. code = nodes[code].child0;
  1216. }
  1217.  
  1218. if (code < 0 || code > NUM_NODES)
  1219. {
  1220. fclose (in);
  1221. fclose (out);
  1222. throw format ("El archivo \"%s\" está corrompido", fileHuffman);
  1223. }
  1224.  
  1225. } while (code >= NUM_ASCII);
  1226.  
  1227. fputc (code, out);
  1228. sumCheck += code;
  1229.  
  1230. ElTiempoNoPasaEnBalde ();
  1231. }
  1232.  
  1233. fclose (in);
  1234. fclose (out);
  1235.  
  1236. if (sumBytes != sumCheck)
  1237. {
  1238. throw format ("Suma de bytes incorrecta en \"%s\"", fileHuffman);
  1239. }
  1240. }
  1241.  
  1242.  
  1243. /**
  1244.  * Leer pesos de cada código ASCII
  1245.  */
  1246. void Huffman::ReadProbability (char *filename)
  1247. {
  1248. FILE *f;
  1249. int car;
  1250.  
  1251. if ((f = fopen (filename, "rb")) == NULL)
  1252. {
  1253. throw format ("No encuentro \"%s\"", filename);
  1254. }
  1255. else
  1256. {
  1257. strcpy (fileOriginal, filename);
  1258. }
  1259.  
  1260. sumBytes = 0;
  1261.  
  1262. while ((car = fgetc (f)) != EOF)
  1263. {
  1264. nodes[car].weight++;
  1265. sumBytes += car;
  1266. }
  1267.  
  1268. fclose (f);
  1269.  
  1270. MakeTree ();
  1271. }
  1272.  
  1273.  
  1274. /**
  1275.  * Visualizar una tabla estadística.
  1276.  */
  1277. void Huffman::ShowStatistics (char *filename)
  1278. {
  1279. BitStack stack (NUM_ASCII/8);
  1280. dword totalBits=0;
  1281. int index;
  1282. int BRILLO=WHITE;
  1283. int NORMAL=LIGHTGRAY;
  1284.  
  1285. if (IsHuffmanFile (filename))
  1286. {
  1287. ReadHeader (filename);
  1288. }
  1289. else
  1290. {
  1291. ReadProbability (filename);
  1292. }
  1293.  
  1294. Write (NORMAL, "Estadísticas de \"%s\"\n", filename);
  1295.  
  1296. if (verbose)
  1297. {
  1298. Write (NORMAL, "\n PESOS PORC HEX BINARIO DEC CAR HUFFMAN\n");
  1299. }
  1300. else
  1301. {
  1302. Write (NORMAL, "\n PESOS PORC HEX HUFFMAN\n");
  1303. }
  1304.  
  1305. for (int i=NUM_NODES-1; i >= 0; --i)
  1306. {
  1307. if (sortASCII)
  1308. index = i; // Ordenado por código ASCII
  1309. else
  1310. index = sorted[i]; // Ordenado por pesos
  1311.  
  1312.  
  1313. if (nodes[index].weight == 0 || index > 255)
  1314. {
  1315. continue;
  1316. }
  1317.  
  1318. BRILLO = (BRILLO==LIGHTBLUE)? LIGHTRED : LIGHTBLUE;
  1319. NORMAL = (NORMAL== BLUE)? RED : BLUE;
  1320.  
  1321. Write (NORMAL,"\n");
  1322. Write (BRILLO, "%16s ", str (nodes[index].weight));
  1323. Write (NORMAL, "%5.2f%% ", PerCentNode (index));
  1324. Write (BRILLO, "x%02X ", index);
  1325.  
  1326. if (verbose)
  1327. {
  1328. char *bin = binary (index);
  1329. while (*bin)
  1330. {
  1331. if (*bin++ == '1')
  1332. Write (BRILLO, "1");
  1333. else
  1334. Write (NORMAL, "0");
  1335. }
  1336. Write (NORMAL, " ");
  1337.  
  1338. Write (NORMAL, "%3s ", ascii (index));
  1339. Write (NORMAL, "%3d ", index);
  1340. }
  1341.  
  1342. int code = index;
  1343. do
  1344. {
  1345. stack.Push (nodes[code].bit);
  1346. code = nodes[code].parent;
  1347.  
  1348. } while (code != root);
  1349.  
  1350. int noBits = 0;
  1351. while (stack.Top ())
  1352. {
  1353. ++noBits;
  1354.  
  1355. if (stack.Pop())
  1356. Write (BRILLO, "1");
  1357. else
  1358. Write (NORMAL, "0");
  1359. }
  1360. totalBits += noBits * nodes[index].weight;
  1361. }
  1362.  
  1363. NORMAL = LIGHTGRAY;
  1364.  
  1365. Write (NORMAL, "\n\n");
  1366.  
  1367. Write (NORMAL, "%16s bytes ocupa el original\n",
  1368. str (nodes[root].weight));
  1369.  
  1370. Write (NORMAL, "%16s bytes ocupa el comprimido\n",
  1371. str ((dword)ceil ((double)totalBits/8.0)));
  1372.  
  1373. Write (NORMAL, "%15.2f%% de reducción\n", PerCentCompress (totalBits));
  1374. }
  1375.  
  1376. /**
  1377.  * Calcula codes a partir de la
  1378.  * información del árbol
  1379.  */
  1380. void Huffman::CalculeCodes ()
  1381. {
  1382. BitStack stack (NUM_ASCII/8);
  1383.  
  1384. for (int i=0; i < NUM_ASCII; ++i)
  1385. {
  1386. if (codes[i].bit != NULL)
  1387. {
  1388. free (codes[i].bit);
  1389. }
  1390.  
  1391. if (nodes[i].weight == 0)
  1392. {
  1393. codes[i].bit = NULL;
  1394. codes[i].numBits = 0;
  1395. }
  1396. else
  1397. {
  1398. int n = i;
  1399. int numBits = 0;
  1400. do
  1401. {
  1402. ++numBits;
  1403. stack.Push (nodes[n].bit);
  1404. n = nodes[n].parent;
  1405.  
  1406. } while (n != root);
  1407.  
  1408.  
  1409. codes[i].numBits = numBits;
  1410. codes[i].bit = (char *)malloc (numBits+1);
  1411.  
  1412. char *b = codes[i].bit;
  1413. while (stack.Top ())
  1414. {
  1415. *b++ = stack.Pop() ? '1':'0';
  1416. }
  1417.  
  1418. *b = '\0';
  1419. }
  1420. }
  1421. }
  1422.  
  1423. /**
  1424.  * Porcentaje de un nodo
  1425.  */
  1426. double Huffman::PerCentNode (int index)
  1427. {
  1428. return (double)nodes[index].weight*100.0
  1429. / (double)nodes[root].weight;
  1430. }
  1431.  
  1432. double Huffman::PerCentCompress (dword totalBits)
  1433. {
  1434. return 100.0
  1435. - (double)(totalBits * 100.0)
  1436. / (double)(nodes[root].weight * 8.0);
  1437. }
  1438.  
  1439.  
  1440. //-------------------------------------
  1441. // METODOS DE LA PILA DE BITS
  1442.  
  1443. /**
  1444.  * Constructor
  1445.  */
  1446. BitStack::BitStack (int size)
  1447. {
  1448. noBytes = size;
  1449. topBit = 0;
  1450. buffer = (byte *)calloc (noBytes, sizeof(byte)); // Inicializado a 0
  1451.  
  1452. if (buffer == NULL)
  1453. {
  1454. throw "Falta memoria para el buffer del BitStack";
  1455. }
  1456. }
  1457.  
  1458. /**
  1459.  * Subtract first bytes and Adjust the stack
  1460.  */
  1461. void BitStack::Subtract (int size)
  1462. {
  1463. int i, j;
  1464.  
  1465. // Translate bytes to begin
  1466. for (i=0, j=size; j<noBytes; ++i, ++j)
  1467. {
  1468. buffer[i] = buffer[j];
  1469. }
  1470.  
  1471. // Clean garbage
  1472. for ( ; i<noBytes; ++i)
  1473. {
  1474. buffer[i] = 0;
  1475. }
  1476.  
  1477. topBit -= ((long)size) << 3; // Adjust the pointer
  1478.  
  1479. if (topBit < 0)
  1480. {
  1481. throw "Puntero de pila negativo en BitStack::Substract";
  1482. }
  1483.  
  1484. }
  1485.  
  1486. /**
  1487.  * Add new bytes and Adjust the stack
  1488.  */
  1489. void BitStack::Add (byte *base, int size)
  1490. {
  1491. int i, j;
  1492.  
  1493. // Translate bytes to end
  1494.  
  1495. for (i=topBit>>3, j=i+size; i>=0; --i, --j)
  1496. {
  1497. buffer[j] = buffer[i];
  1498. }
  1499.  
  1500. // Add bytes
  1501.  
  1502. for (i=0; i<size; ++i)
  1503. {
  1504. buffer[ i ] = base[ i ];
  1505. }
  1506.  
  1507. topBit += ((long)size)<<3; // Adjust the pointer
  1508.  
  1509. if ((topBit>>3) > noBytes)
  1510. {
  1511. throw "Puntero de pila demasiado grande en BitStack::Add";
  1512. }
  1513.  
  1514. }
  1515.  
  1516. /**
  1517.  * Add a bit to stack
  1518.  */
  1519. inline void BitStack::Push (int bit)
  1520. {
  1521. buffer [topBit >> 3] |= (bit & 1) << (topBit & 0x7);
  1522.  
  1523. ++topBit;
  1524.  
  1525. if ((topBit >> 3) > noBytes)
  1526. {
  1527. throw "Puntero de pila muy alto en BitStack::Push";
  1528. }
  1529. }
  1530.  
  1531. /**
  1532.  * Get a bit from stack
  1533.  */
  1534. inline int BitStack::Pop ()
  1535. {
  1536. --topBit;
  1537.  
  1538. if (topBit < 0)
  1539. {
  1540. throw "Puntero de pila negativo en BitStack::Pop";
  1541. }
  1542. byte mascara = 1 << (topBit & 0x7);
  1543. int bit = buffer[ topBit >> 3 ] & mascara ? 1:0;
  1544. buffer[topBit >> 3] &= ~mascara;
  1545.  
  1546. return bit;
  1547. }
  1548.  
  1549.  
  1550. /**
  1551.  * Invertir los bits
  1552.  */
  1553. void BitStack::ReverseBits (byte *base, int n)
  1554. {
  1555. int i, j, tmp;
  1556.  
  1557. // Reverse bytes
  1558. for (i=0, j=n-1; i<=j; i++, --j)
  1559. {
  1560. tmp = base[i];
  1561. base[i] = base[j];
  1562. base[j] = tmp;
  1563. }
  1564.  
  1565. // Reverse bits
  1566. for (i = 0; i < n; ++i)
  1567. {
  1568. tmp = 0;
  1569.  
  1570. for (j = 0; j < 8; j++)
  1571. {
  1572. tmp <<= 1;
  1573. tmp |= base[i] & 1;
  1574. base[i] >>= 1;
  1575. }
  1576. base[i] = tmp;
  1577. }
  1578. }
  1579.  
  1580. //-------------------------------------
  1581. // End Source File
  1582.  
  1583.  

Proinf.net