1 /*********************************************************************** 2 * * 3 * This software is part of the ast package * 4 * Copyright (c) 1995-2012 AT&T Intellectual Property * 5 * and is licensed under the * 6 * Eclipse Public License, Version 1.0 * 7 * by AT&T Intellectual Property * 8 * * 9 * A copy of the License is available at * 10 * http://www.eclipse.org/org/documents/epl-v10.html * 11 * (with md5 checksum b35adb5213ca9657e911e9befb180842) * 12 * * 13 * Information and Software Systems Research * 14 * AT&T Research * 15 * Florham Park NJ * 16 * * 17 * Phong Vo <kpv@research.att.com> * 18 * * 19 ***********************************************************************/ 20 #ifndef _VDELHDR_H 21 #define _VDELHDR_H 1 22 23 #include "vdelta.h" 24 25 #if _PACKAGE_ast 26 #include <ast_std.h> 27 #else 28 #if __STD_C 29 #include <stddef.h> 30 #else 31 #include <sys/types.h> 32 #endif 33 #endif /*_PACKAGE_ast*/ 34 35 #ifdef DEBUG 36 _BEGIN_EXTERNS_ 37 extern int abort(); 38 _END_EXTERNS_ 39 #define ASSERT(p) ((p) ? 0 : abort()) 40 #define DBTOTAL(t,v) ((t) += (v)) 41 #define DBMAX(m,v) ((m) = (m) > (v) ? (m) : (v) ) 42 #else 43 #define ASSERT(p) 44 #define DBTOTAL(t,v) 45 #define DBMAX(m,v) 46 #endif 47 48 /* short-hand notations */ 49 #define NIL(t) ((t)0) 50 #define reg register 51 #define uchar unsigned char 52 #define uint unsigned int 53 #define ulong unsigned long 54 55 /* default window size - Chosen to suit malloc() even on 16-bit machines. */ 56 #undef MAXINT 57 #define MAXINT ((int)(((uint)~0) >> 1)) 58 #define DFLTWINDOW (MAXINT <= 0x7fff ? 0x7fff : (1<<17) ) 59 #define HEADER(w) ((w)/4) 60 61 #define M_MIN 4 /* min number of bytes to match */ 62 63 /* The hash function is s[0]*alpha^3 + s[1]*alpha^2 + s[2]*alpha + s[3] */ 64 #define ALPHA 33 65 #if 0 66 #define A1(x,t) (ALPHA*(x)) 67 #define A2(x,t) (ALPHA*ALPHA*(x)) 68 #define A3(x,t) (ALPHA*ALPHA*ALPHA*(x)) 69 #else /* fast multiplication using shifts&adds */ 70 #define A1(x,t) ((t = (x)), (t + (t<<5)) ) 71 #define A2(x,t) ((t = (x)), (t + (t<<6) + (t<<10)) ) 72 #define A3(x,t) ((t = (x)), (t + (t<<5) + ((t+(t<<4))<<6) + ((t+(t<<4))<<11)) ) 73 #endif 74 #define HINIT(h,s,t) ((h = A3(s[0],t)), (h += A2(s[1],t)), (h += A1(s[2],t)+s[3]) ) 75 #define HNEXT(h,s,t) ((h -= A3(s[-1],t)), (h = A1(h,t) + s[3]) ) 76 77 #define EQUAL(s,t) ((s)[0] == (t)[0] && (s)[1] == (t)[1] && \ 78 (s)[2] == (t)[2] && (s)[3] == (t)[3] ) 79 80 /* Every instruction will start with a control byte. 81 ** For portability, only 8 bits of the byte are used. 82 ** The bits are used as follows: 83 ** iiii ssss 84 ** ssss: size of data involved. 85 ** iiii: this defines 16 instruction types: 86 ** 0: an ADD instruction. 87 ** 1,2,3: COPY with K_QUICK addressing scheme. 88 ** 4,5: COPY with K_SELF,K_HERE addressing schemes. 89 ** 6,7,8,9: COPY with K_RECENT addressing scheme. 90 ** For the above types, ssss if not zero codes the size; 91 ** otherwise, the size is coded in subsequent bytes. 92 ** 10,11: merged ADD/COPY with K_SELF,K_HERE addressing 93 ** 12,13,14,15: merged ADD/COPY with K_RECENT addressing. 94 ** For merged ADD/COPY instructions, ssss is divided into "cc aa" 95 ** where cc codes the size of COPY and aa codes the size of ADD. 96 */ 97 98 #define VD_BITS 8 /* # bits usable in a byte */ 99 100 #define S_BITS 4 /* bits for the size field */ 101 #define I_BITS 4 /* bits for the instruction type */ 102 103 /* The below macros compute the coding for a COPY address. 104 ** There are two caches, a "quick" cache of (K_QTYPE*256) addresses 105 ** and a revolving cache of K_RTYPE "recent" addresses. 106 ** First, we look in the quick cache to see if the address is there. 107 ** If so, we use the cache index as the code. 108 ** Otherwise, we compute from 0, the current location and 109 ** the "recent" cache an address that is closest to the being coded address, 110 ** then code the difference. The type is set accordingly. 111 ** 112 ** An invariance is 2*K_MERGE + K_QTYPE + 1 == 16 113 */ 114 #define K_RTYPE 4 /* # of K_RECENT types */ 115 #define K_QTYPE 3 /* # of K_QUICK types */ 116 #define K_MERGE (K_RTYPE+2) /* # of types allowing add+copy */ 117 #define K_QSIZE (K_QTYPE<<VD_BITS) /* size of K_QUICK cache */ 118 119 #define K_QUICK 1 /* start of K_QUICK types */ 120 #define K_SELF (K_QUICK+K_QTYPE) 121 #define K_HERE (K_SELF+1) 122 #define K_RECENT (K_HERE+1) /* start of K_RECENT types */ 123 124 #define K_DDECL(quick,recent,rhere) /* cache decls in vdelta */ \ 125 int quick[K_QSIZE]; int recent[K_RTYPE]; int rhere/*;*/ 126 #define K_UDECL(quick,recent,rhere) /* cache decls in vdupdate */ \ 127 long quick[K_QSIZE]; long recent[K_RTYPE]; int rhere/*;*/ 128 #define K_INIT(quick,recent,rhere) \ 129 { quick[rhere=0] = (1<<7); \ 130 while((rhere += 1) < K_QSIZE) quick[rhere] = rhere + (1<<7); \ 131 recent[rhere=0] = (1<<8); \ 132 while((rhere += 1) < K_RTYPE) recent[rhere] = (rhere+1)*(1<<8); \ 133 } 134 #define K_UPDATE(quick,recent,rhere,copy) \ 135 { quick[copy%K_QSIZE] = copy; \ 136 if((rhere += 1) >= K_RTYPE) rhere = 0; recent[rhere] = copy; \ 137 } 138 139 #define VD_ISCOPY(k) ((k) > 0 && (k) < (K_RECENT+K_RTYPE) ) 140 #define K_ISMERGE(k) ((k) >= (K_RECENT+K_RTYPE)) 141 142 #define A_SIZE ((1<<S_BITS)-1) /* max local ADD size */ 143 #define A_ISLOCAL(s) ((s) <= A_SIZE ) /* can be coded locally */ 144 #define A_LPUT(s) (s) /* coded local value */ 145 #define A_PUT(s) ((s) - (A_SIZE+1) ) /* coded normal value */ 146 147 #define A_ISHERE(i) ((i) & A_SIZE) /* locally coded size */ 148 #define A_LGET(i) ((i) & A_SIZE) 149 #define A_GET(s) ((s) + (A_SIZE+1) ) 150 151 #define C_SIZE ((1<<S_BITS)+M_MIN-2) /* max local COPY size */ 152 #define C_ISLOCAL(s) ((s) <= C_SIZE ) /* can be coded locally */ 153 #define C_LPUT(s) ((s) - (M_MIN-1) ) /* coded local value */ 154 #define C_PUT(s) ((s) - (C_SIZE+1) ) /* coded normal value */ 155 156 #define C_ISHERE(i) ((i) & ((1<<S_BITS)-1)) /* size was coded local */ 157 #define C_LGET(i) (((i) & ((1<<S_BITS)-1)) + (M_MIN-1) ) 158 #define C_GET(s) ((s) + (C_SIZE+1) ) 159 160 #define K_PUT(k) ((k) << S_BITS) 161 #define K_GET(i) ((i) >> S_BITS) 162 163 /* coding merged ADD/COPY instructions */ 164 #define A_TINY 2 /* bits for tiny ADD */ 165 #define A_TINYSIZE (1<<A_TINY) /* max tiny ADD size */ 166 #define A_ISTINY(s) ((s) <= A_TINYSIZE ) 167 #define A_TPUT(s) ((s) - 1) 168 #define A_TGET(i) (((i) & (A_TINYSIZE-1)) + 1) 169 170 #define C_TINY 2 /* bits for tiny COPY */ 171 #define C_TINYSIZE ((1<<C_TINY) + M_MIN-1) /* max tiny COPY size */ 172 #define C_ISTINY(s) ((s) <= C_TINYSIZE) 173 #define C_TPUT(s) (((s) - M_MIN) << A_TINY) 174 #define C_TGET(i) ((((i) >> A_TINY) & ((1<<C_TINY)-1)) + M_MIN ) 175 176 #define K_TPUT(k) (((k)+K_MERGE) << S_BITS) 177 178 #define MEMCPY(to,from,n) \ 179 switch(n) \ 180 { default: memcpy((Void_t*)to,(Void_t*)from,(size_t)n); \ 181 to += n; from += n; break; \ 182 case 7 : *to++ = *from++; \ 183 case 6 : *to++ = *from++; \ 184 case 5 : *to++ = *from++; \ 185 case 4 : *to++ = *from++; \ 186 case 3 : *to++ = *from++; \ 187 case 2 : *to++ = *from++; \ 188 case 1 : *to++ = *from++; \ 189 case 0 : break; \ 190 } 191 192 /* Below here is code for a buffered I/O subsystem to speed up I/O */ 193 #define I_SHIFT 7 194 #define I_MORE (1<<I_SHIFT) /* continuation bit */ 195 #define I_CODE(n) ((uchar)((n)&(I_MORE-1)) ) /* get lower bits */ 196 197 /* structure to do buffered IO */ 198 typedef struct _vdio_s 199 { uchar* next; 200 uchar* endb; 201 uchar* data; 202 int size; 203 int left; 204 long here; 205 Vddisc_t* delta; 206 uchar buf[1024]; 207 } Vdio_t; 208 209 #define ENDB(io) ((io)->endb) 210 #define NEXT(io) ((io)->next) 211 #define HERE(io) ((io)->here) 212 #define DATA(io) ((io)->data) 213 #define SIZE(io) ((io)->size) 214 #define LEFT(io) ((io)->left) 215 #define DELTA(io) ((io)->delta) 216 #define READF(io) ((io)->delta->readf) 217 #define WRITEF(io) ((io)->delta->writef) 218 #define REMAIN(io) (ENDB(io) - NEXT(io)) 219 #define INIT(io,delta) ((io)->endb = (io)->next = (io)->data = NIL(uchar*), \ 220 (io)->size = 0, (io)->here = 0, (io)->delta = (delta) ) 221 #define VDPUTC(io,c) ((REMAIN(io) > 0 || (*_Vdflsbuf)(io) > 0) ? \ 222 (int)(*(io)->next++ = (uchar)(c)) : -1 ) 223 #define VDGETC(io) ((REMAIN(io) > 0 || (*_Vdfilbuf)(io) > 0) ? \ 224 (int)(*(io)->next++) : -1 ) 225 #define VDREWIND(io) ((io)->next = (io)->data) 226 227 /* fast string I/O */ 228 #define STRPUTC(tab,c) (*(tab)->delta++ = (uchar)(c)) 229 #define STRWRITE(tab,s,n) {memcpy((tab)->delta,(s),(n)); (tab)->delta += (n);} 230 #define STRPUTU(tab,u,buf) \ 231 { reg uchar *s, *endb; reg ulong v = (u); \ 232 s = (endb = &buf[sizeof(buf)])-1; *s = I_CODE(v); \ 233 while((v >>= I_SHIFT)) *--s = I_CODE(v)|I_MORE; v = endb-s;\ 234 memcpy((tab)->delta,s,v); (tab)->delta += v; \ 235 } 236 #define STRGETC(tab) (*(tab)->delta++) 237 #define STRREAD(tab,s,n) {memcpy((s),(tab)->delta,(n)); (tab)->delta += (n);} 238 #define STRGETU(tab,u) \ 239 { reg int c; \ 240 for(u = 0;; ) \ 241 { c = *(tab)->delta++; u = (u<<I_SHIFT) | (c & (I_MORE-1)); \ 242 if(!(c&I_MORE)) break; \ 243 } \ 244 } 245 246 typedef struct _vdbufio_s 247 { int(* vdfilbuf)_ARG_((Vdio_t*)); 248 int(* vdflsbuf)_ARG_((Vdio_t*)); 249 ulong(* vdgetu)_ARG_((Vdio_t*, ulong)); 250 int(* vdputu)_ARG_((Vdio_t*, ulong)); 251 int(* vdread)_ARG_((Vdio_t*, uchar*, int)); 252 int(* vdwrite)_ARG_((Vdio_t*, uchar*, int)); 253 } Vdbufio_t; 254 #define _Vdfilbuf _Vdbufio.vdfilbuf 255 #define _Vdflsbuf _Vdbufio.vdflsbuf 256 #define _Vdgetu _Vdbufio.vdgetu 257 #define _Vdputu _Vdbufio.vdputu 258 #define _Vdread _Vdbufio.vdread 259 #define _Vdwrite _Vdbufio.vdwrite 260 261 _BEGIN_EXTERNS_ 262 extern Vdbufio_t _Vdbufio; 263 extern long _vdupdate_01 _ARG_((Vddisc_t*, Vddisc_t*, Vddisc_t*)); 264 #if !_PACKAGE_ast 265 extern Void_t* memcpy _ARG_((Void_t*, const Void_t*, size_t)); 266 extern Void_t* malloc _ARG_((size_t)); 267 extern void free _ARG_((Void_t*)); 268 #endif 269 _END_EXTERNS_ 270 271 #endif /*_VDELHDR_H*/ 272