GRASS Programmer's Manual  6.4.2(2012)
rle.c
Go to the documentation of this file.
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 }
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines