src/mtf/mtf.c

   1 /*----------------------------------------------------------------------------
   2  *                   jacu - Just Another Compression Utility
   3  *----------------------------------------------------------------------------
   4  * This file is part of jacu.
   5  *
   6  * jacu is free software; you can redistribute it and/or modify it under the
   7  * terms of the GNU General Public License as published by the Free Software
   8  * Foundation; either version 2 of the License, or (at your option) any later
   9  * version.
  10  *
  11  * jacu is distributed in the hope that it will be useful, but WITHOUT ANY
  12  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  13  * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
  14  * details.
  15  *
  16  * You should have received a copy of the GNU General Public License along
  17  * with jacu; if not, write to the Free Software Foundation, Inc., 59 Temple
  18  * Place, Suite 330, Boston, MA  02111-1307  USA
  19  *----------------------------------------------------------------------------
  20  */
  21
  22 #include "mtf.h"
  23
  24 /****privadas*****/
  25 int no_pertenece(char *z, char c, int len);
  26
  27 void pop_front(char *z, unsigned int pos);
  28
  29 int get_pos(char *z, int len, char c);
  30 /****fin privadas******/
  31
  32 void print_z(char *z, int len)
  33 {
  34         int i;
  35         for(i=0; i<len; i++)
  36                 fprintf(stderr, "%c", z[i]);
  37         fprintf(stderr, "\n");
  38 }
  39
  40 unsigned char *jacu_mtf(unsigned char *datos, int len, unsigned char **_z, int *z_len)
  41 {
  42         unsigned char *z;
  43         unsigned char *pos;
  44         int i, size;
  45
  46         pos = (unsigned char *)malloc(len*sizeof(unsigned char));
  47         z = jacu_buscar_z(datos, len, &size);
  48         *_z = (unsigned char*)malloc(size*sizeof(unsigned char));
  49         memcpy(*_z, z, size*sizeof(unsigned char));
  50         for(i=0; i<len; i++){
  51                 pos[i] = get_pos(z, size, datos[i]);
  52                 if (pos[i] != 0)
  53                         pop_front(z, pos[i]);
  54         }
  55         (*z_len) = size;
  56         free(z);
  57         return pos;
  58 }
  59
  60 unsigned char *jacu_mtf_inv(unsigned char *z, unsigned char *pos, int len)
  61 {
  62         char *datos;
  63         int i;
  64
  65         datos = (char*)malloc(sizeof(char)*len);
  66         for(i=0; i<len; i++){
  67                 datos[i] = z[(unsigned int)pos[i]];
  68                 if (pos[i] != 0)
  69                         pop_front(z, (unsigned int)pos[i]);
  70         }
  71         return datos;
  72 }
  73
  74 unsigned char *jacu_buscar_z(unsigned char* datos, int len, int *size)
  75 {
  76         char *z;
  77         int i, j=0;
  78
  79         z = NULL;
  80         for(i=0; i<len; i++){
  81                 if( no_pertenece(z, datos[i], j) == -1 ){
  82                         j++;
  83                         z = realloc(z, j*sizeof(char));
  84                         z[j-1]=datos[i];
  85                         *size = j;
  86                 }
  87         }
  88         return z;
  89 }
  90
  91
  92 int no_pertenece(char *z, char c, int len)
  93 {
  94         int i;
  95
  96         for(i=0; i<len; i++)
  97                 if (z[i] == c)
  98                         return 0;
  99         return -1;
 100 }
 101
 102 void pop_front(char *z, unsigned int pos)
 103 {
 104         char aux;
 105         int i=0;
 106
 107         if (pos > 255) printf("pos > = %u\n", pos);
 108         if (pos < 0u) printf("pos < = %d\n", pos);
 109         aux = z[pos];
 110         for(i=pos; i>0; i--)
 111                 z[i]=z[i-1];
 112         z[0]=aux;
 113 }
 114
 115 int get_pos(char *z, int len, char c)
 116 {
 117         int pos;
 118         if (z==NULL) return -1;
 119
 120         for(pos=0; pos<len; pos++)
 121                 if ( z[pos] == c )
 122                         return pos;
 123         return -1;
 124 }