unthwack.c

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10

    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 }

Cache object: cbfa7b94de3476216ef3b209a3201d08

[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.

FreeBSD/Linux Kernel Cross Reference sys/port/unthwack.c

FreeBSD/Linux Kernel Cross Reference
sys/port/unthwack.c