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