mware/rle.c

   1 /*!
   2  * \file
   3  * <!--
   4  * Copyright 2004 Develer S.r.l. (http://www.develer.com/)
   5  * Copyright 1999, 2000, 2001 Bernardo Innocenti <bernie@develer.com>
   6  * This file is part of DevLib - See devlib/README for information.
   7  * -->
   8  *
   9  * \brief General-purpose run-length {en,de}coding algorithm (implementation)
  10  *
  11  * Original source code from http://www.compuphase.com/compress.htm
  12  *
  13  * \version $Id$
  14  * \author Bernardo Innocenti <bernie@develer.com>
  15  */
  16
  17 /*#*
  18  *#* $Log$
  19  *#* Revision 1.2  2004/08/25 14:12:09  rasky
  20  *#* Aggiornato il comment block dei log RCS
  21  *#*
  22  *#* Revision 1.1  2004/08/04 02:35:54  bernie
  23  *#* Import simple RLE algorithm.
  24  *#*
  25  *#*/
  26
  27 #include "rle.h"
  28
  29
  30 /*!
  31  * Run-length encode \a len bytes from the \a input buffer
  32  * to the \a output buffer.
  33  */
  34 int rle(unsigned char *output, const unsigned char *input, int len)
  35 {
  36         int count, index, i;
  37         unsigned char first;
  38         unsigned char *out;
  39
  40
  41         out = output;
  42         count = 0;
  43         while (count < len)
  44         {
  45                 index = count;
  46                 first = input[index++];
  47
  48                 /* Scan for bytes identical to the first one */
  49                 while ((index < len) && (index - count < 127) && (input[index] == first))
  50                         index++;
  51
  52                 if (index - count == 1)
  53                 {
  54                         /* Failed to "replicate" the current byte. See how many to copy.
  55                          */
  56                         while ((index < len) && (index - count < 127))
  57                         {
  58                                 /* Avoid a replicate run of only 2-bytes after a literal run.
  59                                  * There is no gain in this, and there is a risc of loss if the
  60                                  * run after the two identical bytes is another literal run.
  61                                  * So search for 3 identical bytes.
  62                                  */
  63                                 if ((input[index] == input[index - 1]) &&
  64                                         ((index > 1) && (input[index] == input[index - 2])))
  65                                 {
  66                                         /* Reset the index so we can back up these three identical
  67                                          * bytes in the next run.
  68                                          */
  69                                         index -= 2;
  70                                         break;
  71                                 }
  72
  73                                 index++;
  74                         }
  75
  76                         /* Output a run of uncompressed bytes: write length and values */
  77                         *out++ = (unsigned char)(count - index);
  78                         for (i = count; i < index; i++)
  79                                 *out++ = input[i];
  80             }
  81                 else
  82                 {
  83                         /* Output a compressed run: write length and value */
  84                         *out++ = (unsigned char)(index - count);
  85                         *out++ = first;
  86             }
  87
  88                 count = index;
  89         }
  90
  91         /* Output EOF marker */
  92         *out++ = 0;
  93
  94         return (out - output);
  95 }
  96
  97
  98 /*!
  99  * Run-length decode from the \a input buffer to the \a output
 100  * buffer.
 101  *
 102  * \note The output buffer must be large enough to accomodate
 103  *       all decoded output.
 104  */
 105 int unrle(unsigned char *output, const unsigned char *input)
 106 {
 107         signed char count;
 108         unsigned char *out;
 109         unsigned char value;
 110
 111
 112         out = output;
 113
 114         for (;;)
 115         {
 116                 count = (signed char)*input++;
 117                 if (count > 0)
 118                 {
 119                         /* replicate run */
 120                         value = *input++;
 121                         while (count--)
 122                                 *out++ = value;
 123                 }
 124                 else if (count < 0)
 125                 {
 126                         /* literal run */
 127                         while (count++)
 128                                 *out++ = *input++;
 129                 }
 130                 else
 131                         /* EOF */
 132                         break;
 133         }
 134
 135         return (out - output);
 136 }