sys/src/9/port/unthwack.c

   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("unthwack: blocks dropped: seq=%ld cseq=%ld %d cmask=%#lx %#x\n",
 175                         seq, cseq, src[0], cmask, src[1]);
 176                 return -2;
 177         }
 178
 179         smax = src + nsrc;
 180         src += 2;
 181         utnbits = 0;
 182         utbits = 0;
 183         overbits = 0;
 184         lithist = ~0;
 185         while(src < smax || utnbits - overbits >= MinDecode){
 186                 while(utnbits <= 24){
 187                         utbits <<= 8;
 188                         if(src < smax)
 189                                 utbits |= *src++;
 190                         else
 191                                 overbits += 8;
 192                         utnbits += 8;
 193                 }
 194
 195                 /*
 196                  * literal
 197                  */
 198                 len = lenval[(utbits >> (utnbits - 5)) & 0x1f];
 199                 if(len == 0){
 200                         if(lithist & 0xf){
 201                                 utnbits -= 9;
 202                                 lit = (utbits >> utnbits) & 0xff;
 203                                 lit &= 255;
 204                         }else{
 205                                 utnbits -= 8;
 206                                 lit = (utbits >> utnbits) & 0x7f;
 207                                 if(lit < 32){
 208                                         if(lit < 24){
 209                                                 utnbits -= 2;
 210                                                 lit = (lit << 2) | ((utbits >> utnbits) & 3);
 211                                         }else{
 212                                                 utnbits -= 3;
 213                                                 lit = (lit << 3) | ((utbits >> utnbits) & 7);
 214                                         }
 215                                         lit = (lit - 64) & 0xff;
 216                                 }
 217                         }
 218                         if(d >= dmax)
 219                                 return -1;
 220                         *d++ = lit;
 221                         lithist = (lithist << 1) | (lit < 32) | (lit > 127);
 222                         blocks->maxoff++;
 223                         continue;
 224                 }
 225
 226                 /*
 227                  * length
 228                  */
 229                 if(len < 255)
 230                         utnbits -= lenbits[len];
 231                 else{
 232                         utnbits -= DBigLenBits;
 233                         code = ((utbits >> utnbits) & ((1 << DBigLenBits) - 1)) - DBigLenCode;
 234                         len = DMaxFastLen;
 235                         use = DBigLenBase;
 236                         bits = (DBigLenBits & 1) ^ 1;
 237                         while(code >= use){
 238                                 len += use;
 239                                 code -= use;
 240                                 code <<= 1;
 241                                 utnbits--;
 242                                 if(utnbits < 0)
 243                                         return -1;
 244                                 code |= (utbits >> utnbits) & 1;
 245                                 use <<= bits;
 246                                 bits ^= 1;
 247                         }
 248                         len += code;
 249
 250                         while(utnbits <= 24){
 251                                 utbits <<= 8;
 252                                 if(src < smax)
 253                                         utbits |= *src++;
 254                                 else
 255                                         overbits += 8;
 256                                 utnbits += 8;
 257                         }
 258                 }
 259
 260                 /*
 261                  * offset
 262                  */
 263                 utnbits -= 4;
 264                 bits = (utbits >> utnbits) & 0xf;
 265                 off = offbase[bits];
 266                 bits = offbits[bits];
 267
 268                 utnbits -= bits;
 269                 off |= (utbits >> utnbits) & ((1 << bits) - 1);
 270                 off++;
 271
 272                 b = blocks;
 273                 while(off > b->maxoff){
 274                         off -= b->maxoff;
 275                         b++;
 276                         if(b >= eblocks)
 277                                 return -1;
 278                 }
 279                 if(d + len > dmax
 280                 || b != blocks && len > off)
 281                         return -1;
 282                 s = b->data + b->maxoff - off;
 283                 blocks->maxoff += len;
 284
 285                 for(i = 0; i < len; i++)
 286                         d[i] = s[i];
 287                 d += len;
 288         }
 289         if(utnbits < overbits)
 290                 return -1;
 291
 292         len = d - blocks->data;
 293         memmove(dst, blocks->data, len);
 294
 295         unthwackinsert(ut, len, seq);
 296
 297         return len;
 298 }