src/external/tng_io/src/compression/mtf.c

   1 /* This code is part of the tng compression routines.
   2  *
   3  * Written by Daniel Spangberg and Magnus Lundborg
   4  * Copyright (c) 2010, 2013-2014 The GROMACS development team.
   5  *
   6  *
   7  * This program is free software; you can redistribute it and/or
   8  * modify it under the terms of the Revised BSD License.
   9  */
  10
  11
  12 #include <stdlib.h>
  13 #include <string.h>
  14 #include "../../include/compression/warnmalloc.h"
  15 #include "../../include/compression/mtf.h"
  16
  17 /* "Partial" MTF. Byte based. */
  18 /* Move to front coding.
  19    Acceptable inputs are max 8 bits (0-0xFF) */
  20 static void comp_conv_to_mtf_byte(unsigned char *vals, const int nvals,
  21                                   unsigned char *valsmtf)
  22 {
  23   int i;
  24   /* Indices into a linked list */
  25   int list[256];
  26   int dict[256];
  27   /* Head of the linked list */
  28   int head;
  29   for (i=0; i<256; i++)
  30     dict[i]=i;
  31   for (i=0; i<255; i++)
  32     list[i]=i+1;
  33   list[255]=-1; /* end. */
  34   head=0;
  35   for (i=0; i<nvals; i++)
  36     {
  37       int v=(int)vals[i];
  38       /* Find how early in the dict the value is */
  39       int ptr=head;
  40       int oldptr=-1;
  41       int r=0;
  42       while (dict[ptr]!=v)
  43         {
  44           oldptr=ptr;
  45           ptr=list[ptr];
  46           r++;
  47         }
  48       valsmtf[i]=(unsigned char)r;
  49       /* Move it to front in list */
  50       /* Is it the head? Then it is already at the front. */
  51       if (oldptr!=-1)
  52         {
  53           /* Remove it from inside the list */
  54           list[oldptr]=list[ptr];
  55           /* Move it to the front. */
  56           list[ptr]=head;
  57           head=ptr;
  58         }
  59     }
  60 }
  61
  62 void Ptngc_comp_conv_to_mtf_partial(unsigned int *vals, const int nvals,
  63                               unsigned int *valsmtf)
  64 {
  65   unsigned char *tmp=warnmalloc(nvals*2);
  66   int i, j;
  67
  68   memset(valsmtf, 0U, sizeof(unsigned int) * nvals);
  69
  70   for (j=0; j<3; j++)
  71     {
  72       for (i=0; i<nvals; i++)
  73         tmp[i]=(unsigned char)((vals[i]>>(8*j))&0xFF);
  74       comp_conv_to_mtf_byte(tmp,nvals,tmp+nvals);
  75       for (i=0; i<nvals; i++)
  76         valsmtf[i]|=(((unsigned int)(tmp[nvals+i]))<<(8*j));
  77     }
  78   free(tmp);
  79 }
  80
  81 void Ptngc_comp_conv_to_mtf_partial3(unsigned int *vals, const int nvals,
  82                                unsigned char *valsmtf)
  83 {
  84   unsigned char *tmp=warnmalloc(nvals);
  85   int i, j;
  86   for (j=0; j<3; j++)
  87     {
  88       for (i=0; i<nvals; i++)
  89         tmp[i]=(unsigned char)((vals[i]>>(8*j))&0xFF);
  90       comp_conv_to_mtf_byte(tmp,nvals,valsmtf+j*nvals);
  91     }
  92   free(tmp);
  93 }
  94
  95 /* Move to front decoding */
  96 static void comp_conv_from_mtf_byte(unsigned char *valsmtf, const int nvals,
  97                              unsigned char *vals)
  98 {
  99   int i;
 100   /* Indices into a linked list */
 101   int list[256];
 102   int dict[256];
 103   /* Head of the linked list */
 104   int head;
 105   for (i=0; i<256; i++)
 106     dict[i]=i;
 107   for (i=0; i<255; i++)
 108     list[i]=i+1;
 109   list[255]=-1; /* end. */
 110   head=0;
 111   for (i=0; i<nvals; i++)
 112     {
 113       int r=(int)valsmtf[i];
 114       /* Find value at position r in the list */
 115       int ptr=head;
 116       int oldptr=-1;
 117       int cnt=0;
 118       while (cnt<r)
 119         {
 120           oldptr=ptr;
 121           ptr=list[ptr];
 122           cnt++;
 123         }
 124       vals[i]=(unsigned int)dict[ptr];
 125       /* Move it to front in list */
 126       /* Is it the head? Then it is already at the front. */
 127       if (oldptr!=-1)
 128         {
 129           /* Remove it from inside the list */
 130           list[oldptr]=list[ptr];
 131           /* Move it to the front. */
 132           list[ptr]=head;
 133           head=ptr;
 134         }
 135     }
 136 }
 137
 138 void Ptngc_comp_conv_from_mtf_partial(unsigned int *valsmtf, const int nvals,
 139                                 unsigned int *vals)
 140 {
 141   unsigned char *tmp=warnmalloc(nvals*2);
 142   int i, j;
 143
 144   memset(vals, 0U, sizeof(unsigned int) * nvals);
 145
 146   for (j=0; j<3; j++)
 147     {
 148       for (i=0; i<nvals; i++)
 149         tmp[i]=(unsigned char)((valsmtf[i]>>(8*j))&0xFF);
 150       comp_conv_from_mtf_byte(tmp,nvals,tmp+nvals);
 151       for (i=0; i<nvals; i++)
 152         vals[i]|=(((unsigned int)(tmp[nvals+i]))<<(8*j));
 153     }
 154   free(tmp);
 155 }
 156
 157 void Ptngc_comp_conv_from_mtf_partial3(unsigned char *valsmtf, const int nvals,
 158                                  unsigned int *vals)
 159 {
 160   unsigned char *tmp=warnmalloc(nvals);
 161   int i, j;
 162
 163   memset(vals, 0U, sizeof(unsigned int) * nvals);
 164
 165   for (j=0; j<3; j++)
 166     {
 167       comp_conv_from_mtf_byte(valsmtf+j*nvals,nvals,tmp);
 168       for (i=0; i<nvals; i++)
 169         vals[i]|=(((unsigned int)(tmp[i]))<<(8*j));
 170     }
 171   free(tmp);
 172 }
 173
 174 /* Move to front coding.
 175    Acceptable inputs are max 24 bits (0-0xFFFFFF) */
 176 void Ptngc_comp_conv_to_mtf(unsigned int *vals, const int nvals,
 177                       unsigned int *dict, const int ndict,
 178                       unsigned int *valsmtf)
 179 {
 180   int i;
 181   /* Indices into a linked list */
 182   int *list=warnmalloc(ndict*sizeof *list);
 183   /* Head of the linked list */
 184   int head;
 185   for (i=0; i<ndict-1; i++)
 186     list[i]=i+1;
 187   list[ndict-1]=-1; /* end. */
 188   head=0;
 189   for (i=0; i<nvals; i++)
 190     {
 191       int v=vals[i];
 192       /* Find how early in the dict the value is */
 193       int ptr=head;
 194       int oldptr=-1;
 195       int r=0;
 196       while (dict[ptr]!=v)
 197         {
 198           oldptr=ptr;
 199           ptr=list[ptr];
 200           r++;
 201         }
 202       valsmtf[i]=r;
 203       /* Move it to front in list */
 204       /* Is it the head? Then it is already at the front. */
 205       if (oldptr!=-1)
 206         {
 207           /* Remove it from inside the list */
 208           list[oldptr]=list[ptr];
 209           /* Move it to the front. */
 210           list[ptr]=head;
 211           head=ptr;
 212         }
 213     }
 214   free(list);
 215 }
 216
 217 /* Move to front decoding */
 218 void Ptngc_comp_conv_from_mtf(unsigned int *valsmtf, const int nvals,
 219                         unsigned int *dict, const int ndict,
 220                         unsigned int *vals)
 221 {
 222   int i;
 223   /* Indices into a linked list */
 224   int *list=warnmalloc(ndict*sizeof *list);
 225   /* Head of the linked list */
 226   int head;
 227   for (i=0; i<ndict-1; i++)
 228     list[i]=i+1;
 229   list[ndict-1]=-1; /* end. */
 230   head=0;
 231   for (i=0; i<nvals; i++)
 232     {
 233       int r=valsmtf[i];
 234       /* Find value at position r in the list */
 235       int ptr=head;
 236       int oldptr=-1;
 237       int cnt=0;
 238       while (cnt<r)
 239         {
 240           oldptr=ptr;
 241           ptr=list[ptr];
 242           cnt++;
 243         }
 244       vals[i]=dict[ptr];
 245       /* Move it to front in list */
 246       /* Is it the head? Then it is already at the front. */
 247       if (oldptr!=-1)
 248         {
 249           /* Remove it from inside the list */
 250           list[oldptr]=list[ptr];
 251           /* Move it to the front. */
 252           list[ptr]=head;
 253           head=ptr;
 254         }
 255     }
 256   free(list);
 257 }
 258