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