GRASS Programmer's Manual
6.4.2(2012)
|
00001 #include <stdio.h> 00002 #include <grass/G3d.h> 00003 00004 #define G_254_SQUARE 64516 00005 #define G_254_TIMES_2 508 00006 00007 #define G_RLE_OUTPUT_CODE(code) (*((unsigned char *) dst++) = (code)) 00008 #define G_RLE_INPUT_CODE(codeP) (*(codeP) = *((unsigned char *) src++)) 00009 00010 /*---------------------------------------------------------------------------*/ 00011 00012 static int G_rle_codeLength(int length) 00013 { 00014 register int lPrime; 00015 int codeLength; 00016 00017 if (length == -1) 00018 return 2; 00019 if (length < 254) 00020 return 1; 00021 if (length < G_254_TIMES_2) 00022 return 2; 00023 if (length < G_254_SQUARE) 00024 return 3; 00025 00026 codeLength = 0; 00027 lPrime = length; 00028 while ((lPrime = lPrime / 254) != 0) 00029 codeLength++; 00030 return codeLength + 2; 00031 } 00032 00033 /*---------------------------------------------------------------------------*/ 00034 00035 static char *rle_length2code(int length, char *dst) 00036 { 00037 register int lPrime; 00038 00039 if (length == -1) { /* stop code */ 00040 G_RLE_OUTPUT_CODE(255); 00041 G_RLE_OUTPUT_CODE(255); 00042 00043 return dst; 00044 } 00045 00046 if (length < 254) { 00047 G_RLE_OUTPUT_CODE(length); 00048 00049 return dst; 00050 } 00051 00052 if (length < G_254_TIMES_2) { /* length == 254 + a; a < 254 */ 00053 G_RLE_OUTPUT_CODE(255); 00054 G_RLE_OUTPUT_CODE(length % 254); 00055 00056 return dst; 00057 } 00058 00059 if (length < G_254_SQUARE) { /* length = 254 * b + a; b, a < 254 */ 00060 G_RLE_OUTPUT_CODE(254); /* this if-clause included for efficiency only */ 00061 G_RLE_OUTPUT_CODE(length / 254); 00062 G_RLE_OUTPUT_CODE(length % 254); 00063 00064 return dst; 00065 } 00066 00067 /* length = 254 ^ c + 254 * b + a; b, a < 254 */ 00068 00069 lPrime = length; 00070 while ((lPrime = lPrime / 254) != 0) 00071 G_RLE_OUTPUT_CODE(254); 00072 00073 length %= G_254_SQUARE; 00074 00075 G_RLE_OUTPUT_CODE(length / 254); 00076 G_RLE_OUTPUT_CODE(length % 254); 00077 00078 return dst; 00079 } 00080 00081 /*---------------------------------------------------------------------------*/ 00082 00083 static char *rle_code2length(char *src, int *length) 00084 { 00085 int code; 00086 00087 if (G_RLE_INPUT_CODE(length) < 254) 00088 return src; /* length < 254 */ 00089 00090 if (*length == 255) { /* length == 254 + a; a < 254 */ 00091 if (G_RLE_INPUT_CODE(length) == 255) { 00092 *length = -1; 00093 return src; 00094 } 00095 00096 *length += 254; 00097 return src; 00098 } 00099 00100 G_RLE_INPUT_CODE(&code); 00101 if (code < 254) { /* length = 254 * b + a; b, a < 254 */ 00102 G_RLE_INPUT_CODE(length); /* this if-clause included for efficiency only */ 00103 *length += 254 * code; 00104 00105 return src; 00106 } 00107 00108 /* length = 254 ^ c + 254 * b + a; b, a < 254 */ 00109 00110 *length = G_254_SQUARE; 00111 while (G_RLE_INPUT_CODE(&code) == 254) 00112 *length *= 254; 00113 00114 *length += 254 * code; 00115 G_RLE_INPUT_CODE(&code); 00116 *length += code; 00117 00118 return src; 00119 } 00120 00121 /*---------------------------------------------------------------------------*/ 00122 00123 int G_rle_count_only(char *src, int nofElts, int eltLength) 00124 { 00125 int length, nofEqual; 00126 char *head, *tail, *headStop, *headStop2; 00127 00128 if (nofElts <= 0) 00129 G3d_fatalError("trying to encode 0-length list"); 00130 00131 length = 0; 00132 nofEqual = 1; 00133 head = src + eltLength; 00134 tail = src; 00135 00136 headStop = src + nofElts * eltLength; 00137 00138 while (head != headStop) { 00139 headStop2 = head + eltLength; 00140 00141 while (head != headStop2) { 00142 if (*head != *tail) { 00143 length += G_rle_codeLength(nofEqual) + eltLength; 00144 nofEqual = 1; 00145 tail = headStop2 - eltLength; 00146 break; 00147 } 00148 head++; 00149 tail++; 00150 } 00151 00152 if (head == headStop2) { 00153 nofEqual++; 00154 continue; 00155 } 00156 00157 head = headStop2; 00158 } 00159 length += G_rle_codeLength(nofEqual) + eltLength; 00160 00161 return length + G_rle_codeLength(-1); 00162 } 00163 00164 /*---------------------------------------------------------------------------*/ 00165 00166 void G_rle_encode(char *src, char *dst, int nofElts, int eltLength) 00167 { 00168 int length, nofEqual; 00169 char *head, *tail, *headStop, *headStop2; 00170 00171 if (nofElts <= 0) 00172 G3d_fatalError("trying to encode 0-length list"); 00173 00174 length = 0; 00175 nofEqual = 1; 00176 head = src + eltLength; 00177 tail = src; 00178 00179 headStop = src + nofElts * eltLength; 00180 00181 while (head != headStop) { 00182 headStop2 = head + eltLength; 00183 00184 while (head != headStop2) { 00185 if (*head != *tail) { 00186 dst = rle_length2code(nofEqual, dst); 00187 tail = headStop2 - eltLength * (nofEqual + 1); 00188 head = tail + eltLength; 00189 /* printf ("equal %d char %d\n", nofEqual, *tail); */ 00190 while (tail != head) 00191 *dst++ = *tail++; 00192 length += G_rle_codeLength(nofEqual) + eltLength; 00193 nofEqual = 1; 00194 tail = headStop2 - eltLength; 00195 break; 00196 } 00197 head++; 00198 tail++; 00199 } 00200 00201 if (head == headStop2) { 00202 nofEqual++; 00203 continue; 00204 } 00205 00206 head = headStop2; 00207 } 00208 00209 dst = rle_length2code(nofEqual, dst); 00210 tail = headStop - eltLength * nofEqual; 00211 head = tail + eltLength; 00212 while (tail != head) 00213 *dst++ = *tail++; 00214 length += G_rle_codeLength(nofEqual) + eltLength; 00215 dst = rle_length2code(-1, dst); 00216 length += G_rle_codeLength(-1); 00217 rle_code2length(dst - 2, &nofEqual); 00218 } 00219 00220 /*---------------------------------------------------------------------------*/ 00221 00222 void 00223 G_rle_decode(char *src, char *dst, int nofElts, int eltLength, 00224 int *lengthEncode, int *lengthDecode) 00225 { 00226 int nofEqual; 00227 char *src2, *srcStop, *src2Stop, *dstFirst; 00228 00229 srcStop = src + nofElts * eltLength; 00230 dstFirst = dst; 00231 00232 while (src != srcStop) { 00233 src = rle_code2length(src, &nofEqual); 00234 00235 if (nofEqual == -1) { 00236 *lengthEncode = src - (srcStop - nofElts * eltLength); 00237 *lengthDecode = dst - dstFirst; 00238 return; 00239 } 00240 00241 while (nofEqual--) { 00242 src2 = src; 00243 src2Stop = src2 + eltLength; 00244 while (src2 != src2Stop) 00245 *dst++ = *src2++; 00246 } 00247 src += eltLength; 00248 } 00249 00250 G3d_fatalError("G_rle_decode: string ends prematurely"); 00251 } 00252 00253 /*---------------------------------------------------------------------------*/ 00254 00255 void test_rle() 00256 { 00257 char c[100]; 00258 int length; 00259 00260 do { 00261 printf("length? "); 00262 scanf("%d", &length); 00263 printf("length = %d\n", length); 00264 printf("codeLength %d ", G_rle_codeLength(length)); 00265 (void)rle_length2code(length, c); 00266 length = 0; 00267 (void)rle_code2length(c, &length); 00268 printf("output length %d\n\n", length); 00269 } while (1); 00270 }