home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / src / Tools / glimpse-2.1 / compress / defs.h < prev    next >
Encoding:
C/C++ Source or Header  |  1995-05-16  |  8.1 KB  |  196 lines
  1. /* Copyright (c) 1994 Burra Gopal, Udi Manber.  All Rights Reserved. */
  2.  
  3. /**************************************************************************
  4.  * defs.h:    contains definitions for our static/dictionary based      *
  5.  *        compression scheme that is tailored for very fast search. *
  6.  **************************************************************************/
  7. #ifndef    _DEFS_H_
  8. #define _DEFS_H_
  9.  
  10. #include <sys/types.h>
  11. #include <sys/stat.h>
  12. #include <ctype.h>
  13. #include "glimpse.h"
  14.  
  15. #ifndef S_ISREG
  16. #define S_ISREG(mode) (0100000&(mode))
  17. #endif
  18.  
  19. #ifndef S_ISDIR
  20. #define S_ISDIR(mode) (0040000&(mode))
  21. #endif
  22.  
  23. #undef COMP_SUFFIX
  24. #undef DEF_STRING_FILE
  25. #undef DEF_HASH_FILE
  26. #undef DEF_FREQ_FILE
  27. #undef SIGNATURE_LEN
  28.  
  29. #define MIN_WORD_LEN        1        /* smaller words are not indexed: heuristics like special_texts etc. must be used: verbatim is good enough */
  30. #define AVG_WORD_LEN        12        /* average word length is 8-9 including '\0': have safety margin */
  31. #define HASH_TABLE_SIZE        MAX_64K_HASH
  32. #define SMALL_HASH_TABLE_SIZE    MAX_4K_HASH
  33. #define HASH_ENTRY_SIZE        32         /* hash-file stores: name of len=24, a 5 digit int, a ' ' + a '\n' = 31 bytes + some padding once in a while */
  34. #define DEF_BLOCKSIZE        4096        /* I/O unit size = OS page size */
  35. #define MIN_BLOCKSIZE        512        /* granularity for above and below */
  36. #define HASH_FILE_BLOCKS    (HASH_TABLE_SIZE * HASH_ENTRY_SIZE / MIN_BLOCKSIZE)
  37. #define STRING_FILE_BLOCKS    (HASH_TABLE_SIZE * MAX_WORD_LEN / MIN_BLOCKSIZE)
  38. #define MAX_SPECIAL_CHARS    32        /* Maximum # of special characters used during compress */
  39. #define DEF_SPECIAL_WORDS    32        /* Special words for which 1B codes are reserved */
  40.  
  41. #define COMP_ATLEAST        10        /* At least 10% compression is needed */
  42. #define COMP_SUFFIX        ".CZ"        /* Common suffix used for all compressed files: IT INCLUDES THE '.' !!! */
  43. #define DEF_INDEX_FILE        INDEX_FILE    /* same as glimpse's */
  44. #define DEF_STRING_FILE        ".glimpse_uncompress"
  45. #define DEF_HASH_FILE        ".glimpse_compress"
  46. #define DEF_FREQ_FILE        ".glimpse_quick"
  47. #define DEF_THRESHOLD        16        /* 256? default for min bytes to be coverd before storing in hash table */
  48. #define MAX_THRESHOLD        65535        /* MAX_WORDS*MAX_THRESHOLD must be < 2**32 - 1 = maxoffset = maxdiskspace = integer */
  49. #define MAX_LSB            254        /* 256 - |{'\0', '\n'}| */
  50. #define DEF_MAX_WORDS        (MAX_LSB*MAX_LSB)
  51.  
  52. #define SAMPLE_SIZE        8192        /* amount of data read to determine file-type: NOT CALLED FOR STDIN! */
  53. #define SIGNATURE_LEN        16        /* to avoid calling strlen: including \0! */
  54.  
  55. typedef struct _hash_entry {
  56.     struct _hash_entry *next;
  57.     char *word;                /* string itself */
  58.     union {
  59.         int    offset;            /* offset into the dictionary file: used only while building compress's dict from glimpse's dict */
  60.         struct {
  61.             short    freq;        /* number of times the word occurs -- provided it is in the dictionary */
  62.             short    index;        /* index into the string table */
  63.         } attribute;            /* once freq > THRESHOLD, its just an index into the string table: used only while compressing a file */
  64.     } val;
  65. } hash_entry;
  66.  
  67. /*
  68.  * The total number of special characters (1..4) CANNOT exceed MAX_SPECIAL_CHARS.
  69.  * The arrangement is as follows:
  70.  * 1. SPECIAL_TEXTS
  71.  * 2. SPECIAL_SEPARATORS
  72.  * 3. SPECIAL_DELIMITERS
  73.  * 4. VERBATIM
  74.  * 5. SPECIAL_WORDS
  75.  * Any rearrangement of these can be done provided the BEGIN/END values
  76.  * are defined properly: the NUMs remain the same.
  77.  */
  78.  
  79. #define BEGIN_SPECIAL_CHARS    1        /* character 0 is never a part of any code */
  80. #define END_SPECIAL_CHARS    30        /* Not including begin/end verbatim */
  81.  
  82. /* Special delimiters are text-sequences which can come after a word instead of a blank: this is a subset of the above with '\n' and '\t' */
  83. #define EASY_NUM_SPECIAL_DELIMITERS    8    /* numbered from 1 .. 8 */
  84. #define HARD_NUM_SPECIAL_DELIMITERS    9    /* extra: a special kind of newline */
  85. #define SPECIAL_DELIMITERS        { '.', ',', ':', '-', ';', '!', '"', '\'', '\n'}
  86. #define BEGIN_SPECIAL_DELIMITERS    BEGIN_SPECIAL_CHARS
  87. #define EASY_END_SPECIAL_DELIMITERS    9
  88. #define HARD_END_SPECIAL_DELIMITERS    10
  89.  
  90. /* Special separators are things that can separate two words: they are 2blanks, 2tabs or 2newlines */
  91. #define NUM_SEPARATORS        7        /* numbered from 10 .. 16 */
  92. #define NEWLINE            '\n'         /* = HARD_END_SPECIAL_DELIMITERS --> carefully chosen so that this is TRUE !!!! Speeds up searches */
  93. #define NOTBLANK        (NEWLINE + 1)    /* acts like unputc(' ') if char after a word != blk OR sp-delims */
  94. #define BLANK            (NOTBLANK + 1)
  95. #define TAB            (NOTBLANK + 2)
  96. #define TWOBLANKS        (NOTBLANK + 3)    /* Beginning of a sentence */
  97. #define TWOTABS            (NOTBLANK + 4)    /* Indentation */
  98. #define TWONEWLINES        (NOTBLANK + 5)    /* Beginning of a paragraph */
  99. #define BEGIN_SEPARATORS    10
  100. #define END_SEPARATORS        17
  101.  
  102. /*
  103.  * An alternate way would be to have a code for BLANK and NBLANKS, TAB and NTABS, and, NEWLINE and NNEWLINES:
  104.  * in each of these cases, the byte occuring immediately next would determine the number of BLANKS/TABS/NEWLINES.
  105.  * Though this works for a general number of cases, it needs two bytes of encoding: which makes us
  106.  * wonder whether those cases occur commonly enough to waste two bytes to encode two blanks (common).
  107.  * The present encoding guarantees 50% compression for any sequence of separators anyway, and is much simpler.
  108.  */
  109.  
  110. /* Special texts are text-sequences which have a 1 byte codes associated with them: these appear first among the special things */
  111. #define NUM_SPECIAL_TEXTS    13        /* numbered from 17 .. 29 */
  112. #define SPECIAL_TEXTS        { '.', ',', ':', '-', ';', '!', '"', '\'', '#', '$', '%', '(', ')'}    /* Could have used ?, @ and & too */
  113. #define BEGIN_SPECIAL_TEXTS    17
  114. #define END_SPECIAL_TEXTS    30
  115.  
  116. /* Characters for literal text */
  117. #define BEGIN_VERBATIM        30
  118. #define END_VERBATIM        31
  119. #define EASY_ONE_VERBATIM    EASY_END_SPECIAL_DELIMITERS
  120. #define HARD_ONE_VERBATIM    BEGIN_VERBATIM    /* Is not an ascii char since ascii is 32.. */
  121.  
  122. /* BEGIN and END SPECIAL_WORDS are variables */
  123.  
  124. #if    0
  125. /* THIS WON'T REALLY HELP SINCE SOURCE CODE RARELY HAS COMMON WORDS: KEYWORDS ARE VERY SMALL SO THEY HARDLY GIVE ANY COMPRESSION */
  126. char special_program_chars[] = { '.', ',', ':', '-', '!', ';', '?', '+', '/', '\'', '"', '~', '`', '&', '@', '#', '$', '%', '^', '*', '=', '(', ')', '{', '}', '[', ']', '_', '|', '\\', '<', '>' };
  127. #endif    /*0*/
  128.  
  129. /*
  130.  * Common exported functions.
  131.  */
  132.  
  133. unsigned short encode_index();
  134. unsigned short decode_index();
  135. unsigned int mygetc();
  136. int is_little_endian();
  137. int build_string();
  138. int build_hash();
  139. int dump_hash();
  140. int dump_string();
  141. int get_word_from_offset();
  142. int dump_and_free_string_hash();
  143. hash_entry *insert_hash();
  144. hash_entry *get_hash();
  145. int hash_it();
  146.  
  147. /*
  148.  * The beauty of this allocation scheme is that "free" does not need to be implemented!
  149.  * The total memory occupied by both the string and hash tables is appx 1.5 MB
  150.  */
  151.  
  152. #define hashfree(h)    if (usemalloc) free(e);
  153.  
  154. #define hashalloc(e) \
  155. {\
  156.     if (usemalloc) (e) = (hash_entry *)malloc(sizeof(hash_entry));\
  157.     else {\
  158.         if (free_hash == NULL) free_hash = (hash_entry *)malloc(sizeof(hash_entry) * DEF_MAX_WORDS);\
  159.         if (free_hash == NULL) (e) = NULL;\
  160.         else (e) = ((next_free_hash >= DEF_MAX_WORDS) ? (NULL) : (&(free_hash[next_free_hash ++])));\
  161.     }\
  162.     if ((e) == NULL) {fprintf(stderr, "Out of memory in cast-hash-table!\n"); exit(2); }\
  163. }
  164.  
  165. #define strfree(s)    if (usemalloc) free(s);
  166.  
  167. /* called ONLY in the build procedure in which we can afford to be slow and do an strcpy since sizes of words are not determined: hardcoded in build_hash() */
  168. #define stralloc(s, len) \
  169. {\
  170.     if (usemalloc) (s) = (char *)malloc(len);\
  171.     else {\
  172.         if (free_str == NULL) free_str = (char *)malloc(AVG_WORD_LEN * DEF_MAX_WORDS);\
  173.         if (free_str == NULL) (s) = NULL;\
  174.         else (s) = ((next_free_str >= AVG_WORD_LEN * DEF_MAX_WORDS) ? (NULL) : (&(free_str[next_free_str]))); next_free_str += (len);\
  175.     }\
  176.     if ((s) == NULL) {fprintf(stderr, "Out of memory in cast-string-table!\n"); exit(2); }\
  177. }
  178.  
  179. /* There is no equivalent strtablealloc since it is hardcoded into build_string and is not used anywhere else */
  180.  
  181. /* Some flags corr. to user options: avoid global variables for options, pass flags as parameters */
  182. #define TC_EASYSEARCH    0x1
  183. #define TC_UNTILNEWLINE    0x2
  184. #define TC_REMOVE    0x4
  185. #define TC_OVERWRITE    0x8
  186. #define TC_RECURSIVE    0x10
  187. #define TC_ERRORMSGS    0x20
  188. #define TC_SILENT    0x40
  189. #define TC_NOPROMPT    0x80
  190. #define TC_FILENAMESONSTDIN 0x100
  191.  
  192. #define CAST_VERSION    "1.0"
  193. #define CAST_DATE    "1994"
  194.  
  195. #endif    /*_DEFS_H_*/
  196.