The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


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

FreeBSD/Linux Kernel Cross Reference
sys/libkern/mkext.c

Version: -  FREEBSD  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-2  -  FREEBSD-11-1  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-4  -  FREEBSD-10-3  -  FREEBSD-10-2  -  FREEBSD-10-1  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-3  -  FREEBSD-9-2  -  FREEBSD-9-1  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-4  -  FREEBSD-8-3  -  FREEBSD-8-2  -  FREEBSD-8-1  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-4  -  FREEBSD-7-3  -  FREEBSD-7-2  -  FREEBSD-7-1  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-4  -  FREEBSD-6-3  -  FREEBSD-6-2  -  FREEBSD-6-1  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-5  -  FREEBSD-5-4  -  FREEBSD-5-3  -  FREEBSD-5-2  -  FREEBSD-5-1  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  linux-2.6  -  linux-2.4.22  -  MK83  -  MK84  -  PLAN9  -  DFBSD  -  NETBSD  -  NETBSD5  -  NETBSD4  -  NETBSD3  -  NETBSD20  -  OPENBSD  -  xnu-517  -  xnu-792  -  xnu-792.6.70  -  xnu-1228  -  xnu-1456.1.26  -  xnu-1699.24.8  -  xnu-2050.18.24  -  OPENSOLARIS  -  minix-3-1-1 
SearchContext: -  none  -  3  -  10 

    1 /*
    2  * Copyright (c) 2000-2004 Apple Computer, Inc. All rights reserved.
    3  *
    4  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
    5  * 
    6  * This file contains Original Code and/or Modifications of Original Code
    7  * as defined in and that are subject to the Apple Public Source License
    8  * Version 2.0 (the 'License'). You may not use this file except in
    9  * compliance with the License. The rights granted to you under the License
   10  * may not be used to create, or enable the creation or redistribution of,
   11  * unlawful or unlicensed copies of an Apple operating system, or to
   12  * circumvent, violate, or enable the circumvention or violation of, any
   13  * terms of an Apple operating system software license agreement.
   14  * 
   15  * Please obtain a copy of the License at
   16  * http://www.opensource.apple.com/apsl/ and read it before using this file.
   17  * 
   18  * The Original Code and all software distributed under the License are
   19  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
   20  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
   21  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
   22  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
   23  * Please see the License for the specific language governing rights and
   24  * limitations under the License.
   25  * 
   26  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
   27  */
   28 #include <string.h>
   29 #include <libkern/mkext.h>
   30 
   31 #define BASE 65521L /* largest prime smaller than 65536 */
   32 #define NMAX 5000  
   33 // NMAX (was 5521) the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1
   34 
   35 #define DO1(buf,i)  {s1 += buf[i]; s2 += s1;}
   36 #define DO2(buf,i)  DO1(buf,i); DO1(buf,i+1);
   37 #define DO4(buf,i)  DO2(buf,i); DO2(buf,i+2);
   38 #define DO8(buf,i)  DO4(buf,i); DO4(buf,i+4);
   39 #define DO16(buf)   DO8(buf,0); DO8(buf,8);
   40 
   41 u_int32_t
   42 mkext_adler32(uint8_t *buf, int32_t len)
   43 {
   44     unsigned long s1 = 1; // adler & 0xffff;
   45     unsigned long s2 = 0; // (adler >> 16) & 0xffff;
   46     int k;
   47 
   48     while (len > 0) {
   49         k = len < NMAX ? len : NMAX;
   50         len -= k;
   51         while (k >= 16) {
   52             DO16(buf);
   53             buf += 16;
   54             k -= 16;
   55         }
   56         if (k != 0) do {
   57             s1 += *buf++;
   58             s2 += s1;
   59         } while (--k);
   60         s1 %= BASE;
   61         s2 %= BASE;
   62     }
   63     return (s2 << 16) | s1;
   64 }
   65 
   66 
   67 /**************************************************************
   68  LZSS.C -- A Data Compression Program
   69 ***************************************************************
   70     4/6/1989 Haruhiko Okumura
   71     Use, distribute, and modify this program freely.
   72     Please send me your improved versions.
   73         PC-VAN      SCIENCE
   74         NIFTY-Serve PAF01022
   75         CompuServe  74050,1022
   76 
   77 **************************************************************/
   78 
   79 #define N         4096  /* size of ring buffer - must be power of 2 */
   80 #define F         18    /* upper limit for match_length */
   81 #define THRESHOLD 2     /* encode string into position and length
   82                            if match_length is greater than this */
   83 #define NIL       N     /* index for root of binary search trees */
   84 
   85 struct encode_state {
   86     /*
   87      * left & right children & parent. These constitute binary search trees.
   88      */
   89     int lchild[N + 1], rchild[N + 257], parent[N + 1];
   90 
   91     /* ring buffer of size N, with extra F-1 bytes to aid string comparison */
   92     u_int8_t text_buf[N + F - 1];
   93 
   94     /*
   95      * match_length of longest match.
   96      * These are set by the insert_node() procedure.
   97      */
   98     int match_position, match_length;
   99 };
  100 
  101 
  102 int
  103 decompress_lzss(u_int8_t *dst, u_int32_t dstlen, u_int8_t *src, u_int32_t srclen)
  104 {
  105     /* ring buffer of size N, with extra F-1 bytes to aid string comparison */
  106     u_int8_t text_buf[N + F - 1];
  107     u_int8_t *dststart = dst;
  108         u_int8_t *dstend = dst + dstlen;
  109     u_int8_t *srcend = src + srclen;
  110     int  i, j, k, r, c;
  111     unsigned int flags;
  112     
  113     dst = dststart;
  114     srcend = src + srclen;
  115     for (i = 0; i < N - F; i++)
  116         text_buf[i] = ' ';
  117     r = N - F;
  118     flags = 0;
  119     for ( ; ; ) {
  120         if (((flags >>= 1) & 0x100) == 0) {
  121             if (src < srcend) c = *src++; else break;
  122             flags = c | 0xFF00;  /* uses higher byte cleverly */
  123         }   /* to count eight */
  124         if (flags & 1) {
  125             if (src < srcend) c = *src++; else break;
  126             *dst++ = c;
  127                         if (dst >= dstend) {
  128                                 goto finish;
  129                         }
  130             text_buf[r++] = c;
  131             r &= (N - 1);
  132         } else {
  133             if (src < srcend) i = *src++; else break;
  134             if (src < srcend) j = *src++; else break;
  135             i |= ((j & 0xF0) << 4);
  136             j  =  (j & 0x0F) + THRESHOLD;
  137             for (k = 0; k <= j; k++) {
  138                 c = text_buf[(i + k) & (N - 1)];
  139                 *dst++ = c;
  140                                 if (dst >= dstend) {
  141                                         goto finish;
  142                                 }
  143                 text_buf[r++] = c;
  144                 r &= (N - 1);
  145             }
  146         }
  147     }
  148 finish:
  149     return dst - dststart;
  150 }
  151 
  152 #if !KERNEL
  153 
  154 /*
  155  * initialize state, mostly the trees
  156  *
  157  * For i = 0 to N - 1, rchild[i] and lchild[i] will be the right and left 
  158  * children of node i.  These nodes need not be initialized.  Also, parent[i] 
  159  * is the parent of node i.  These are initialized to NIL (= N), which stands 
  160  * for 'not used.'  For i = 0 to 255, rchild[N + i + 1] is the root of the 
  161  * tree for strings that begin with character i.  These are initialized to NIL. 
  162  * Note there are 256 trees. */
  163 static void init_state(struct encode_state *sp)
  164 {
  165     int  i;
  166 
  167     bzero(sp, sizeof(*sp));
  168 
  169     for (i = 0; i < N - F; i++)
  170         sp->text_buf[i] = ' ';
  171     for (i = N + 1; i <= N + 256; i++)
  172         sp->rchild[i] = NIL;
  173     for (i = 0; i < N; i++)
  174         sp->parent[i] = NIL;
  175 }
  176 
  177 /*
  178  * Inserts string of length F, text_buf[r..r+F-1], into one of the trees
  179  * (text_buf[r]'th tree) and returns the longest-match position and length
  180  * via the global variables match_position and match_length.
  181  * If match_length = F, then removes the old node in favor of the new one,
  182  * because the old one will be deleted sooner. Note r plays double role,
  183  * as tree node and position in buffer.
  184  */
  185 static void insert_node(struct encode_state *sp, int r)
  186 {
  187     int  i, p, cmp;
  188     u_int8_t  *key;
  189 
  190     cmp = 1;
  191     key = &sp->text_buf[r];
  192     p = N + 1 + key[0];
  193     sp->rchild[r] = sp->lchild[r] = NIL;
  194     sp->match_length = 0;
  195     for ( ; ; ) {
  196         if (cmp >= 0) {
  197             if (sp->rchild[p] != NIL)
  198                 p = sp->rchild[p];
  199             else {
  200                 sp->rchild[p] = r; 
  201                 sp->parent[r] = p;
  202                 return;
  203             }
  204         } else {
  205             if (sp->lchild[p] != NIL)
  206                 p = sp->lchild[p];
  207             else {
  208                 sp->lchild[p] = r;
  209                 sp->parent[r] = p;
  210                 return;
  211             }
  212         }
  213         for (i = 1; i < F; i++) {
  214             if ((cmp = key[i] - sp->text_buf[p + i]) != 0)
  215                 break;
  216         }
  217         if (i > sp->match_length) {
  218             sp->match_position = p;
  219             if ((sp->match_length = i) >= F)
  220                 break;
  221         }
  222     }
  223     sp->parent[r] = sp->parent[p];
  224     sp->lchild[r] = sp->lchild[p];
  225     sp->rchild[r] = sp->rchild[p];
  226     sp->parent[sp->lchild[p]] = r;
  227     sp->parent[sp->rchild[p]] = r;
  228     if (sp->rchild[sp->parent[p]] == p)
  229         sp->rchild[sp->parent[p]] = r;
  230     else
  231         sp->lchild[sp->parent[p]] = r;
  232     sp->parent[p] = NIL;  /* remove p */
  233 }
  234 
  235 /* deletes node p from tree */
  236 static void delete_node(struct encode_state *sp, int p)
  237 {
  238     int  q;
  239     
  240     if (sp->parent[p] == NIL)
  241         return;  /* not in tree */
  242     if (sp->rchild[p] == NIL)
  243         q = sp->lchild[p];
  244     else if (sp->lchild[p] == NIL)
  245         q = sp->rchild[p];
  246     else {
  247         q = sp->lchild[p];
  248         if (sp->rchild[q] != NIL) {
  249             do {
  250                 q = sp->rchild[q];
  251             } while (sp->rchild[q] != NIL);
  252             sp->rchild[sp->parent[q]] = sp->lchild[q];
  253             sp->parent[sp->lchild[q]] = sp->parent[q];
  254             sp->lchild[q] = sp->lchild[p];
  255             sp->parent[sp->lchild[p]] = q;
  256         }
  257         sp->rchild[q] = sp->rchild[p];
  258         sp->parent[sp->rchild[p]] = q;
  259     }
  260     sp->parent[q] = sp->parent[p];
  261     if (sp->rchild[sp->parent[p]] == p)
  262         sp->rchild[sp->parent[p]] = q;
  263     else
  264         sp->lchild[sp->parent[p]] = q;
  265     sp->parent[p] = NIL;
  266 }
  267 
  268 #endif /* !KERNEL */
  269 

Cache object: a1cb8f2dd26fe6e6da027077d0ce86a6


[ 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.