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