Add demo application.
[bertos.git] / 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 }