/* Numdiff - compare putatively similar files, ignoring small numeric differences Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017 Ivano Primi This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see . */ #include #include #include #include"linesplit.h" #define O_DEF_SEP '\n' #define ESC_CHAR '\\' const unsigned char InvDigit = (unsigned char) -1; static unsigned char is_hex_digit (char ch) { if (ch >= '0' && ch <= '9') return ch - '0'; else { switch (ch) { case 'a': case 'A': return 10; case 'b': case 'B': return 11; case 'c': case 'C': return 12; case 'd': case 'D': return 13; case 'e': case 'E': return 14; case 'f': case 'F': return 15; default: return InvDigit; } } } static unsigned char is_oct_digit (char ch) { if (ch >= '0' && ch <= '7') return ch - '0'; else return InvDigit; } static int is_hex (const char* pafter_escape, char* byte) { unsigned char hb, lb; /* The return value is the number of hexadecimal digits successfully read */ if ( (hb = is_hex_digit (*pafter_escape)) != InvDigit ) { int rv = 1; lb = is_hex_digit (*(pafter_escape+1)); if (lb == InvDigit) { lb = hb; hb = 0; } else rv = 2; if ((byte)) *byte = (char)(16 * hb + lb); return rv; } else { if ((byte)) *byte = -1; return 0; } } static int is_oct (const char* pafter_escape, char* byte) { unsigned char ho, mo, lo; /* The return value is the number of octal digits successfully read */ if ( (ho = is_oct_digit (*pafter_escape)) != InvDigit ) { int rv = 1; mo = is_oct_digit (*(pafter_escape+1)); lo = is_oct_digit (*(pafter_escape+2)); if (mo == InvDigit) { lo = ho; ho = 0; mo = 0; } else { rv++; if (lo == InvDigit) { lo = mo; mo = ho; ho = 0; } else rv++; } if ((byte)) *byte = (char)(64 * ho + 8 * mo + lo); return (64 * (int)ho + 8 * (int)mo + (int)lo < 256 ? rv : 0); } else { if ((byte)) *byte = -1; return 0; } } static char process_character (const char* chp, const char** new_chp) { const char* nchp; char byte; int r; if (*chp == ESC_CHAR) { switch (*(chp+1)) { case 'a': byte = '\a'; nchp = chp+2; break; case 'b': byte = '\b'; nchp = chp+2; break; case 'f': byte = '\f'; nchp = chp+2; break; case 'n': byte = '\n'; nchp = chp+2; break; case 'r': byte = '\r'; nchp = chp+2; break; case 't': byte = '\t'; nchp = chp+2; break; case 'v': byte = '\v'; nchp = chp+2; break; case 's': byte = ' '; nchp = chp+2; break; case 'x': if ( (r = is_hex (chp+2, &byte)) && byte != '\0' ) nchp = chp + (r + 2); else { byte = *(chp+1); nchp = chp+2; } break; case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': if ( (r = is_oct (chp+1, &byte)) && byte != '\0' ) nchp = chp + (r + 1); else { byte = *(chp+1); nchp = chp+2; } break; default: byte = *(chp+1); nchp = chp+2; break; } } else { byte = *chp; nchp = chp+1; } if ((new_chp)) *new_chp = nchp; return byte; } /* Remark: process the substring [BPTR, EPTR) and return the result (NULL in case of error while allocating memory for the result). Precondition is EPTR >= BPTR. */ static char* process_substring (const char* bptr, const char* eptr) { size_t subssize = eptr - bptr + 1; const char* ptr; char *pstr, *pstrp; if ( !(pstr = (char*) calloc(subssize, sizeof(char))) ) return NULL; else { for (pstrp = pstr, ptr = bptr; ptr < eptr; pstrp++) { *pstrp = process_character (ptr, &ptr); } return pstr; } } /* Create and return a vector of strings using the description contained in the string pointed to by STR. The items in STR (to each of which should correspond a string in the returned vector) are separated by the character SEPARATOR. In case of error while allocating memory for the vector and its elements return NULL. Return NULL also if STR == NULL. Remark: SEPARATOR cannot be the nul character. Return NULL if SEPARATOR is the nul character. */ char** ssplit (const char* str, char separator) { size_t i, n; const char *beg, *ptr, *ptr2sep; char** sv; if (!str || separator == '\0') return NULL; for (beg = str; *beg == separator; beg++); /* Now BEG points to the first charatacrer of the buffer pointed to by STR which is not equal to SEPARATOR. */ /* First count the substrings contained in the buffer pointed to by STR. */ for (n = 1, ptr = beg; (ptr2sep = strchr (ptr, separator)) != NULL; n++) { for (ptr = ptr2sep+1; *ptr == separator; ptr++); } /* Now allocate memory for a vector of N+1 char*. If the allocation fails, return NULL. */ if ( !(sv = (char**) malloc ((n+1)*sizeof(char*))) ) return NULL; sv[n] = NULL; for (i = 0, ptr = beg; (ptr2sep = strchr (ptr, separator)) != NULL; i++) { sv[i] = process_substring (ptr, ptr2sep); if (!sv[i]) { delete_string_vector (sv); return NULL; } for (ptr = ptr2sep+1; *ptr == separator; ptr++); } if (*ptr != '\0') { ptr2sep = strchr (ptr, '\0'); sv[i] = process_substring (ptr, ptr2sep); if (!sv[i]) { delete_string_vector (sv); return NULL; } } return sv; } /* Create and return a vector of strings using the characters contained in the string pointed to by STR. To each (eventually escaped) character in this string will correspond exactly one string in the returned vector. Return NULL if STR == NULL or in case of out of memory. */ char** ssplit_former_way (const char* str) { if ((str)) { size_t n, ls = strlen(str); char **sv; const char *ptr, *nptr; sv = (char**) calloc (ls + 1, sizeof(char*)); if (!sv) return NULL; for (n = 0, ptr = str; *ptr != '\0'; ptr = nptr, n++) { sv[n] = (char*) malloc (2 *sizeof(char)); if ((sv[n])) { sv[n][0] = process_character (ptr, &nptr); sv[n][1] = '\0'; } else { delete_string_vector (sv); return NULL; } } return sv; } else return NULL; } /* Process the string pointed to by ISTR and return the result (NULL in case of error while allocating memory for the result). */ char* get_separating_string (const char* istr) { return process_substring (istr, istr+strlen(istr)); } /* Write to the file pointed to by FP the strings contained in the vector SV. Use SEPARATOR to separate each string from the following one. */ void print_string_vector (FILE* fp, const char** sv, char separator) { size_t n; if (!sv) { fputs ("", fp); fputc (separator, fp); } else { for (n = 0; sv[n] != NULL; n++) { fprintf (fp, "\"%s\"%c", sv[n], separator); } } } /* Rearrange the strings of the vector SV in descending order with respect to their length. Rem.: Pre-condition is that SV is NULL-terminated. This function is suitable only for small vectors, since it uses a bubble-sort algorithm. */ void sort_string_vector (char** sv) { if ((sv)) { size_t n, m, l, lmax, poslmax; char *tmp; for (n = 0; sv[n] != NULL; n++) { lmax = strlen(sv[n]); poslmax = n; for (m = n+1; sv[m] != NULL; m++) { if ( (l = strlen(sv[m])) > lmax ) { lmax = l; poslmax = m; } } tmp = sv[n]; sv[n] = sv[poslmax]; sv[poslmax] = tmp; } } } /* Remove duplicates from the vector SV. */ void remove_duplicates_from_string_vector (char** sv) { if ((sv)) { size_t k, m, n; for (n = 0; sv[n] != NULL; n++) { m = n+1; while (sv[m] != NULL) { if (strcmp (sv[m], sv[n]) == 0) { free((void*)sv[m]); for (k = m+1; sv[k] != NULL; k++) sv[k-1] = sv[k]; sv[k-1] = NULL; } else m++; } } } } /* Return 1 if the string pointed to by STR is found in the vector SV, otherwise 0. 0 should be also returned if STR or SV is NULL. */ int is_string_in_vector (const char* str, const char** sv) { if ((sv) && (str)) { size_t n; for (n = 0; sv[n] != NULL && strcmp(str, sv[n]) != 0; n++); return (sv[n] == NULL ? 0 : 1); } else return 0; } /* Return 0 if there is no string in the vector SV which contains the character CH, otherwise return the length of the longest string between those ones which contain the character CH. 0 should also be returned if SV is null. */ size_t is_char_in_vector (int ch, const char** sv) { if ((sv)) { size_t l, lm, n; for (lm = n = 0; sv[n] != NULL; n++) { if ( (strchr (sv[n], ch)) && (l = strlen (sv[n])) > lm) lm = l; } return lm; } else return 0; } /* Remove the memory allocated for the strings of the vector SV and then free the memory allocated for the vector itself. */ void delete_string_vector (char** sv) { size_t n; if ((sv)) { for (n = 0; sv[n] != NULL; n++) { free ((void*)sv[n]); } free((void*)sv); } } /* Return a pointer to the position following the initial segment of STR that does not contain any string from the vector SV. If such an initial segment does not exist, return a pointer to STR. Consider the string STR as ending at the first occurrence of EOS. SV must be NULL terminated, it cannot contain the empty ("") string nor a string of length > 1 with EOS being one of its non-null characters (but SV may well contain the string of length 1 having EOS as its only non-null character). Rem.: EOS can be the null character. If the string pointed to by STR does not contain any EOS character, a buffer overrun will occur. */ char* string_cspn (const char* str, const char** sv, int eos) { register const char *sviptr; register const char *endptr; register const char *nendptr; register const char *ptr; register size_t n; if (!str || !sv) { /* security check */ return NULL; } else { for (endptr = str; *endptr != eos; endptr++); for (nendptr = str; nendptr < endptr; nendptr++) { for (n = 0; sv[n] != NULL; n++) { for (ptr = nendptr, sviptr = sv[n]; *sviptr != '\0' && *sviptr == *ptr; sviptr++, ptr++); if (*sviptr == '\0') return (char*)nendptr; } } return (char*)nendptr; } } /* Return a pointer to the position following the initial segment of STR that consists entirely of strings from the vector SV. If such an initial segment does not exist, return a pointer to STR. Consider the string STR as ending at the first occurrence of EOS. SV must be NULL terminated, it cannot contain the empty ("") string nor a string of length > 1 with EOS being one of its non-null characters (but SV may well contain the string of length 1 having EOS as its only non-null character). Rem.: this function works under the assumption that the strings in the vector SV are ordered according to their lengths, where SV[0] is the string with the greatest length. EOS can be the null character. */ char* string_spn (const char* str, const char** sv, int eos) { register const char *ptr; register const char *nptr; register const char *sviptr; register size_t n; if (!str || !sv) { /* security check */ return NULL; } else { ptr = str; while (*ptr != eos) { /* Rem.: if strlen(sv[n])== 1 and sv[n][0] == EOS, then strstr(ptr, sv[n]) != ptr. Thus, whenever the following for cycle terminates, sv[n] can not be equal to the string "" (i.e. the string having EOS as its only null character). */ for (n = 0; sv[n] != NULL; n++) { for (nptr = ptr, sviptr = sv[n]; *sviptr!='\0' && *sviptr == *nptr; sviptr++, nptr++); if (*sviptr == '\0') { /* Rem.: if sv[n] does not contain any EOS, then by setting PTR to NPTR we do not skip any EOS. */ ptr = nptr; break; } } if (!sv[n]) break; } return (char*)ptr; } } #ifdef _TEST_LINE_SPLIT_ #define I_DEF_SEP ' ' static void print_help (const char* progname) { printf ("Usage: %s STRING\n\n", progname); } static void print_substring (FILE* fp, const char* bptr, const char* eptr, int nl) { const char *ptr; if (eptr > bptr) { for (ptr = bptr; ptr != eptr; ptr++) { putc (*ptr, fp); } if ((nl)) putc ('\n', fp); } } #define BUFFSIZE 1024 int main (int argc, char* argv[]) { if (argc != 2) { print_help(argv[0]); return 1; } else { char** string_vector = NULL; char** sv = NULL; char linebuff[BUFFSIZE] = ""; char *rv, *ptr, *endptr; size_t l; string_vector = ssplit (argv[1], I_DEF_SEP); sv = ssplit_former_way (argv[1]); remove_duplicates_from_string_vector (string_vector); remove_duplicates_from_string_vector (sv); sort_string_vector (string_vector); print_string_vector (stdout, (const char**)string_vector, O_DEF_SEP); l = is_char_in_vector (':', string_vector); printf ("Length of the longest string containing \':\' = %zu\n", l); puts ("\n\nSplitting the string in the former way produces the following result:"); print_string_vector (stdout, (const char**)sv, O_DEF_SEP); do { #ifdef _MINOR_TEST_ puts ("\nEnter a line of text (Ctrl+D to terminate)"); #endif rv = fgets (linebuff, BUFFSIZE, stdin); if ((rv)) { #ifdef _MINOR_TEST_ ptr = string_cspn (linebuff, (const char**)string_vector, '\0'); fputs ("Cspn =", stdout); print_substring (stdout, linebuff, ptr, 0); fputs ("|EoS|\n", stdout); ptr = string_spn (linebuff, (const char**)string_vector, '\0'); fputs ("Spn =", stdout); print_substring (stdout, linebuff, ptr, 0); fputs ("|EoS|\n", stdout); #else unsigned long fieldno; for (fieldno = 1, ptr = linebuff; *ptr != '\0'; fieldno++) { ptr = string_spn (ptr, (const char**)string_vector, '\0'); endptr = string_cspn (ptr, (const char**)string_vector, '\0'); if ((*ptr)) { printf ("%3lu.>", fieldno); print_substring (stdout, ptr, endptr, 0); puts ("<"); } ptr = endptr; } putchar ('\n'); #endif /* _MINOR_TEST_ */ } } while ((rv)); delete_string_vector (string_vector); return 0; } } #endif /* _TEST_LINE_SPLIT_ */