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