unthwack.c (5251B)
1 #include "u.h" 2 #include "lib.h" 3 #include "mem.h" 4 #include "dat.h" 5 #include "fns.h" 6 7 #include "thwack.h" 8 9 enum 10 { 11 DMaxFastLen = 7, 12 DBigLenCode = 0x3c, /* minimum code for large lenth encoding */ 13 DBigLenBits = 6, 14 DBigLenBase = 1 /* starting items to encode for big lens */ 15 }; 16 17 static uchar lenval[1 << (DBigLenBits - 1)] = 18 { 19 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 20 3, 3, 3, 3, 3, 3, 3, 3, 21 4, 4, 4, 4, 22 5, 23 6, 24 255, 25 255 26 }; 27 28 static uchar lenbits[] = 29 { 30 0, 0, 0, 31 2, 3, 5, 5, 32 }; 33 34 static uchar offbits[16] = 35 { 36 5, 5, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 12, 13 37 }; 38 39 static ushort offbase[16] = 40 { 41 0, 0x20, 42 0x40, 0x60, 43 0x80, 0xc0, 44 0x100, 0x180, 45 0x200, 0x300, 46 0x400, 0x600, 47 0x800, 0xc00, 48 0x1000, 49 0x2000 50 }; 51 52 void 53 unthwackinit(Unthwack *ut) 54 { 55 int i; 56 57 memset(ut, 0, sizeof *ut); 58 for(i = 0; i < DWinBlocks; i++) 59 ut->blocks[i].data = ut->data[i]; 60 } 61 62 ulong 63 unthwackstate(Unthwack *ut, uchar *mask) 64 { 65 ulong bseq, seq; 66 int slot, m; 67 68 seq = ~0UL; 69 m = 0; 70 slot = ut->slot; 71 for(;;){ 72 slot--; 73 if(slot < 0) 74 slot += DWinBlocks; 75 if(slot == ut->slot) 76 break; 77 if(ut->blocks[slot].maxoff == 0) 78 continue; 79 bseq = ut->blocks[slot].seq; 80 if(seq == ~0UL) 81 seq = bseq; 82 else if(seq - bseq > MaxSeqMask) 83 break; 84 else 85 m |= 1 << (seq - bseq - 1); 86 } 87 *mask = m; 88 return seq; 89 } 90 91 /* 92 * insert this block in it's correct sequence number order. 93 * replace the oldest block, which is always pointed to by ut->slot. 94 * the encoder doesn't use a history at wraparound, 95 * so don't worry about that case. 96 */ 97 static int 98 unthwackinsert(Unthwack *ut, int len, ulong seq) 99 { 100 uchar *d; 101 int slot, tslot; 102 103 tslot = ut->slot; 104 for(;;){ 105 slot = tslot - 1; 106 if(slot < 0) 107 slot += DWinBlocks; 108 if(ut->blocks[slot].seq <= seq || ut->blocks[slot].maxoff == 0) 109 break; 110 d = ut->blocks[tslot].data; 111 ut->blocks[tslot] = ut->blocks[slot]; 112 ut->blocks[slot].data = d; 113 tslot = slot; 114 } 115 ut->blocks[tslot].seq = seq; 116 ut->blocks[tslot].maxoff = len; 117 118 ut->slot++; 119 if(ut->slot >= DWinBlocks) 120 ut->slot = 0; 121 122 ut->blocks[ut->slot].seq = ~0UL; 123 ut->blocks[ut->slot].maxoff = 0; 124 125 return tslot; 126 } 127 128 int 129 unthwack(Unthwack *ut, uchar *dst, int ndst, uchar *src, int nsrc, ulong seq) 130 { 131 UnthwBlock blocks[CompBlocks], *b, *eblocks; 132 uchar *s, *d, *dmax, *smax, lit; 133 ulong cmask, cseq, bseq, utbits; 134 int i, off, len, bits, slot, use, code, utnbits, overbits, lithist; 135 136 if(nsrc < 4 || nsrc > ThwMaxBlock) 137 return -1; 138 139 slot = ut->slot; 140 b = blocks; 141 *b = ut->blocks[slot]; 142 d = b->data; 143 dmax = d + ndst; 144 145 /* 146 * set up the history blocks 147 */ 148 cseq = seq - src[0]; 149 cmask = src[1]; 150 b++; 151 while(cseq != seq && b < blocks + CompBlocks){ 152 slot--; 153 if(slot < 0) 154 slot += DWinBlocks; 155 if(slot == ut->slot) 156 break; 157 bseq = ut->blocks[slot].seq; 158 if(bseq == cseq){ 159 *b = ut->blocks[slot]; 160 b++; 161 if(cmask == 0){ 162 cseq = seq; 163 break; 164 } 165 do{ 166 bits = cmask & 1; 167 cseq--; 168 cmask >>= 1; 169 }while(!bits); 170 } 171 } 172 eblocks = b; 173 if(cseq != seq){ 174 print("blocks dropped: seq=%ld cseq=%ld %d cmask=%#lx %#x\n", seq, cseq, src[0], cmask, src[1]); 175 return -2; 176 } 177 178 smax = src + nsrc; 179 src += 2; 180 utnbits = 0; 181 utbits = 0; 182 overbits = 0; 183 lithist = ~0; 184 while(src < smax || utnbits - overbits >= MinDecode){ 185 while(utnbits <= 24){ 186 utbits <<= 8; 187 if(src < smax) 188 utbits |= *src++; 189 else 190 overbits += 8; 191 utnbits += 8; 192 } 193 194 /* 195 * literal 196 */ 197 len = lenval[(utbits >> (utnbits - 5)) & 0x1f]; 198 if(len == 0){ 199 if(lithist & 0xf){ 200 utnbits -= 9; 201 lit = (utbits >> utnbits) & 0xff; 202 lit &= 255; 203 }else{ 204 utnbits -= 8; 205 lit = (utbits >> utnbits) & 0x7f; 206 if(lit < 32){ 207 if(lit < 24){ 208 utnbits -= 2; 209 lit = (lit << 2) | ((utbits >> utnbits) & 3); 210 }else{ 211 utnbits -= 3; 212 lit = (lit << 3) | ((utbits >> utnbits) & 7); 213 } 214 lit = (lit - 64) & 0xff; 215 } 216 } 217 if(d >= dmax) 218 return -1; 219 *d++ = lit; 220 lithist = (lithist << 1) | (lit < 32) | (lit > 127); 221 blocks->maxoff++; 222 continue; 223 } 224 225 /* 226 * length 227 */ 228 if(len < 255) 229 utnbits -= lenbits[len]; 230 else{ 231 utnbits -= DBigLenBits; 232 code = ((utbits >> utnbits) & ((1 << DBigLenBits) - 1)) - DBigLenCode; 233 len = DMaxFastLen; 234 use = DBigLenBase; 235 bits = (DBigLenBits & 1) ^ 1; 236 while(code >= use){ 237 len += use; 238 code -= use; 239 code <<= 1; 240 utnbits--; 241 if(utnbits < 0) 242 return -1; 243 code |= (utbits >> utnbits) & 1; 244 use <<= bits; 245 bits ^= 1; 246 } 247 len += code; 248 249 while(utnbits <= 24){ 250 utbits <<= 8; 251 if(src < smax) 252 utbits |= *src++; 253 else 254 overbits += 8; 255 utnbits += 8; 256 } 257 } 258 259 /* 260 * offset 261 */ 262 utnbits -= 4; 263 bits = (utbits >> utnbits) & 0xf; 264 off = offbase[bits]; 265 bits = offbits[bits]; 266 267 utnbits -= bits; 268 off |= (utbits >> utnbits) & ((1 << bits) - 1); 269 off++; 270 271 b = blocks; 272 while(off > b->maxoff){ 273 off -= b->maxoff; 274 b++; 275 if(b >= eblocks) 276 return -1; 277 } 278 if(d + len > dmax 279 || (b != blocks && len > off)) 280 return -1; 281 s = b->data + b->maxoff - off; 282 blocks->maxoff += len; 283 284 for(i = 0; i < len; i++) 285 d[i] = s[i]; 286 d += len; 287 } 288 if(utnbits < overbits) 289 return -1; 290 291 len = d - blocks->data; 292 memmove(dst, blocks->data, len); 293 294 unthwackinsert(ut, len, seq); 295 296 return len; 297 }