GRASS GIS 7 Programmer's Manual  7.9.dev(2021)-e5379bbd7
rle.c
Go to the documentation of this file.
1 #include <stdio.h>
2 #include <grass/raster3d.h>
3 
4 #define G_254_SQUARE 64516
5 #define G_254_TIMES_2 508
6 
7 #define G_RLE_OUTPUT_CODE(code) (*((unsigned char *) dst++) = (code))
8 #define G_RLE_INPUT_CODE(codeP) (*(codeP) = *((unsigned char *) src++))
9 
10 /*---------------------------------------------------------------------------*/
11 
12 static int G_rle_codeLength(int length)
13 {
14  register int lPrime;
15  int codeLength;
16 
17  if (length == -1)
18  return 2;
19  if (length < 254)
20  return 1;
21  if (length < G_254_TIMES_2)
22  return 2;
23  if (length < G_254_SQUARE)
24  return 3;
25 
26  codeLength = 0;
27  lPrime = length;
28  while ((lPrime = lPrime / 254) != 0)
29  codeLength++;
30  return codeLength + 2;
31 }
32 
33 /*---------------------------------------------------------------------------*/
34 
35 static char *rle_length2code(int length, char *dst)
36 {
37  register int lPrime;
38 
39  if (length == -1) { /* stop code */
40  G_RLE_OUTPUT_CODE(255);
41  G_RLE_OUTPUT_CODE(255);
42 
43  return dst;
44  }
45 
46  if (length < 254) {
47  G_RLE_OUTPUT_CODE(length);
48 
49  return dst;
50  }
51 
52  if (length < G_254_TIMES_2) { /* length == 254 + a; a < 254 */
53  G_RLE_OUTPUT_CODE(255);
54  G_RLE_OUTPUT_CODE(length % 254);
55 
56  return dst;
57  }
58 
59  if (length < G_254_SQUARE) { /* length = 254 * b + a; b, a < 254 */
60  G_RLE_OUTPUT_CODE(254); /* this if-clause included for efficiency only */
61  G_RLE_OUTPUT_CODE(length / 254);
62  G_RLE_OUTPUT_CODE(length % 254);
63 
64  return dst;
65  }
66 
67  /* TODO implement a corrected version for larger strings */
68  /* This code is simply wrong, it works only for c == 2, critical number for wrong computation is 254*254*2 = 129032 */
69  /* CORRECT: length = 254 ^ 2 + 254 * b + a; b, a < 254 */
70 
71  /* WRONG: length = 254 ^ c + 254 * b + a; b, a < 254 */
72 
73  lPrime = length;
74  while ((lPrime = lPrime / 254) != 0)
75  G_RLE_OUTPUT_CODE(254);
76 
77  length %= G_254_SQUARE;
78 
79  G_RLE_OUTPUT_CODE(length / 254);
80  G_RLE_OUTPUT_CODE(length % 254);
81 
82  /* Next should be: length = 254 ^ 3 + 254 ^ 2 * c + 254 * b + a; c, b, a < 254 */
83 
84  return dst;
85 }
86 
87 /*---------------------------------------------------------------------------*/
88 
89 static char *rle_code2length(char *src, int *length)
90 {
91  int code;
92 
93  if (G_RLE_INPUT_CODE(length) < 254)
94  return src; /* length < 254 */
95 
96  if (*length == 255) { /* length == 254 + a; a < 254 */
97  if (G_RLE_INPUT_CODE(length) == 255) {
98  *length = -1;
99  return src;
100  }
101 
102  *length += 254;
103  return src;
104  }
105 
106  G_RLE_INPUT_CODE(&code);
107  if (code < 254) { /* length = 254 * b + a; b, a < 254 */
108  G_RLE_INPUT_CODE(length); /* this if-clause included for efficiency only */
109  *length += 254 * code;
110 
111  return src;
112  }
113 
114  /* TODO implement a corrected version for larger strings */
115  /* This code is simply wrong, it works only for c == 2, critical number for wrong computation is 254*254*2 = 129032 */
116  /* CORRECT: length = 254 ^ 2 + 254 * b + a; b, a < 254 */
117 
118  /* WRONG: length = 254 ^ c + 254 * b + a; b, a < 254 */
119 
120  *length = G_254_SQUARE;
121  while (G_RLE_INPUT_CODE(&code) == 254)
122  *length *= 254;
123 
124  *length += 254 * code;
125  G_RLE_INPUT_CODE(&code);
126  *length += code;
127 
128  /* Next should be: length = 254 ^ 3 + 254 ^ 2 * c + 254 * b + a; c, b, a < 254 */
129 
130  return src;
131 }
132 
133 /*---------------------------------------------------------------------------*/
134 
135 int Rast3d_rle_count_only(char *src, int nofElts, int eltLength)
136 {
137  int length, nofEqual;
138  char *head, *tail, *headStop, *headStop2;
139 
140  if (nofElts <= 0)
141  Rast3d_fatal_error("trying to encode 0-length list");
142 
143  length = 0;
144  nofEqual = 1;
145  head = src + eltLength;
146  tail = src;
147 
148  headStop = src + nofElts * eltLength;
149 
150  while (head != headStop) {
151  headStop2 = head + eltLength;
152 
153  while (head != headStop2) {
154  if (*head != *tail) {
155  length += G_rle_codeLength(nofEqual) + eltLength;
156  nofEqual = 1;
157  tail = headStop2 - eltLength;
158  break;
159  }
160  head++;
161  tail++;
162  }
163 
164  if (head == headStop2) {
165  nofEqual++;
166  continue;
167  }
168 
169  head = headStop2;
170  }
171  length += G_rle_codeLength(nofEqual) + eltLength;
172 
173  return length + G_rle_codeLength(-1);
174 }
175 
176 /*---------------------------------------------------------------------------*/
177 
178 void Rast3d_rle_encode(char *src, char *dst, int nofElts, int eltLength)
179 {
180  int length, nofEqual;
181  char *head, *tail, *headStop, *headStop2;
182 
183  if (nofElts <= 0)
184  Rast3d_fatal_error("trying to encode 0-length list");
185 
186  length = 0;
187  nofEqual = 1;
188  head = src + eltLength;
189  tail = src;
190 
191  headStop = src + nofElts * eltLength;
192 
193  while (head != headStop) {
194  headStop2 = head + eltLength;
195 
196  while (head != headStop2) {
197  if (*head != *tail) {
198  dst = rle_length2code(nofEqual, dst);
199  tail = headStop2 - eltLength * (nofEqual + 1);
200  head = tail + eltLength;
201  /* printf ("equal %d char %d\n", nofEqual, *tail); */
202  while (tail != head)
203  *dst++ = *tail++;
204  length += G_rle_codeLength(nofEqual) + eltLength;
205  nofEqual = 1;
206  tail = headStop2 - eltLength;
207  break;
208  }
209  head++;
210  tail++;
211  }
212 
213  if (head == headStop2) {
214  nofEqual++;
215  continue;
216  }
217 
218  head = headStop2;
219  }
220 
221  dst = rle_length2code(nofEqual, dst);
222  tail = headStop - eltLength * nofEqual;
223  head = tail + eltLength;
224  while (tail != head)
225  *dst++ = *tail++;
226  length += G_rle_codeLength(nofEqual) + eltLength;
227  dst = rle_length2code(-1, dst);
228  length += G_rle_codeLength(-1);
229  rle_code2length(dst - 2, &nofEqual);
230 }
231 
232 /*---------------------------------------------------------------------------*/
233 
234 void
235 Rast3d_rle_decode(char *src, char *dst, int nofElts, int eltLength,
236  int *lengthEncode, int *lengthDecode)
237 {
238  int nofEqual;
239  char *src2, *srcStop, *src2Stop, *dstFirst;
240 
241  srcStop = src + nofElts * eltLength;
242  dstFirst = dst;
243 
244  while (src != srcStop) {
245  src = rle_code2length(src, &nofEqual);
246 
247  if (nofEqual == -1) {
248  *lengthEncode = src - (srcStop - nofElts * eltLength);
249  *lengthDecode = dst - dstFirst;
250  return;
251  }
252 
253  while (nofEqual--) {
254  src2 = src;
255  src2Stop = src2 + eltLength;
256  while (src2 != src2Stop)
257  *dst++ = *src2++;
258  }
259  src += eltLength;
260  }
261 
262  Rast3d_fatal_error("Rast3d_rle_decode: string ends prematurely");
263 }
264 
265 /*---------------------------------------------------------------------------*/
266 
267 /* TODO: Find out if this function used at all.
268  * Seems to be some leftover from the early pre-SVN days of GRASS GIS.
269  * Maris, 2018.
270  */
271 void test_rle()
272 {
273  char c[100];
274  int length;
275 
276  do {
277  printf("length? ");
278  if (scanf("%d", &length) != 1)
279  Rast3d_fatal_error("Error reading length");
280  printf("length = %d\n", length);
281  printf("codeLength %d ", G_rle_codeLength(length));
282  (void)rle_length2code(length, c);
283  length = 0;
284  (void)rle_code2length(c, &length);
285  printf("output length %d\n\n", length);
286  } while (1);
287 }
char * dst
Definition: lz4.h:599
#define G_254_TIMES_2
Definition: rle.c:5
#define G_254_SQUARE
Definition: rle.c:4
void Rast3d_fatal_error(const char *,...) __attribute__((format(printf
void test_rle()
Definition: rle.c:271
#define G_RLE_INPUT_CODE(codeP)
Definition: rle.c:8
int Rast3d_rle_count_only(char *src, int nofElts, int eltLength)
Definition: rle.c:135
void Rast3d_rle_encode(char *src, char *dst, int nofElts, int eltLength)
Definition: rle.c:178
#define G_RLE_OUTPUT_CODE(code)
Definition: rle.c:7
void Rast3d_rle_decode(char *src, char *dst, int nofElts, int eltLength, int *lengthEncode, int *lengthDecode)
Definition: rle.c:235