release/src/router/lzo/src/lzo_dict.h

   1 /* lzo_dict.h -- dictionary definitions for the the LZO library
   2
   3    This file is part of the LZO real-time data compression library.
   4
   5    Copyright (C) 2011 Markus Franz Xaver Johannes Oberhumer
   6    Copyright (C) 2010 Markus Franz Xaver Johannes Oberhumer
   7    Copyright (C) 2009 Markus Franz Xaver Johannes Oberhumer
   8    Copyright (C) 2008 Markus Franz Xaver Johannes Oberhumer
   9    Copyright (C) 2007 Markus Franz Xaver Johannes Oberhumer
  10    Copyright (C) 2006 Markus Franz Xaver Johannes Oberhumer
  11    Copyright (C) 2005 Markus Franz Xaver Johannes Oberhumer
  12    Copyright (C) 2004 Markus Franz Xaver Johannes Oberhumer
  13    Copyright (C) 2003 Markus Franz Xaver Johannes Oberhumer
  14    Copyright (C) 2002 Markus Franz Xaver Johannes Oberhumer
  15    Copyright (C) 2001 Markus Franz Xaver Johannes Oberhumer
  16    Copyright (C) 2000 Markus Franz Xaver Johannes Oberhumer
  17    Copyright (C) 1999 Markus Franz Xaver Johannes Oberhumer
  18    Copyright (C) 1998 Markus Franz Xaver Johannes Oberhumer
  19    Copyright (C) 1997 Markus Franz Xaver Johannes Oberhumer
  20    Copyright (C) 1996 Markus Franz Xaver Johannes Oberhumer
  21    All Rights Reserved.
  22
  23    The LZO library is free software; you can redistribute it and/or
  24    modify it under the terms of the GNU General Public License as
  25    published by the Free Software Foundation; either version 2 of
  26    the License, or (at your option) any later version.
  27
  28    The LZO library is distributed in the hope that it will be useful,
  29    but WITHOUT ANY WARRANTY; without even the implied warranty of
  30    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  31    GNU General Public License for more details.
  32
  33    You should have received a copy of the GNU General Public License
  34    along with the LZO library; see the file COPYING.
  35    If not, write to the Free Software Foundation, Inc.,
  36    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  37
  38    Markus F.X.J. Oberhumer
  39    <markus@oberhumer.com>
  40    http://www.oberhumer.com/opensource/lzo/
  41  */
  42
  43
  44 /* WARNING: this file should *not* be used by applications. It is
  45    part of the implementation of the library and is subject
  46    to change.
  47  */
  48
  49
  50 #ifndef __LZO_DICT_H
  51 #define __LZO_DICT_H 1
  52
  53 #ifdef __cplusplus
  54 extern "C" {
  55 #endif
  56
  57
  58
  59 /***********************************************************************
  60 // dictionary size
  61 ************************************************************************/
  62
  63 /* dictionary needed for compression */
  64 #if !defined(D_BITS) && defined(DBITS)
  65 #  define D_BITS        DBITS
  66 #endif
  67 #if !defined(D_BITS)
  68 #  error "D_BITS is not defined"
  69 #endif
  70 #if (D_BITS < 16)
  71 #  define D_SIZE        LZO_SIZE(D_BITS)
  72 #  define D_MASK        LZO_MASK(D_BITS)
  73 #else
  74 #  define D_SIZE        LZO_USIZE(D_BITS)
  75 #  define D_MASK        LZO_UMASK(D_BITS)
  76 #endif
  77 #define D_HIGH          ((D_MASK >> 1) + 1)
  78
  79
  80 /* dictionary depth */
  81 #if !defined(DD_BITS)
  82 #  define DD_BITS       0
  83 #endif
  84 #define DD_SIZE         LZO_SIZE(DD_BITS)
  85 #define DD_MASK         LZO_MASK(DD_BITS)
  86
  87 /* dictionary length */
  88 #if !defined(DL_BITS)
  89 #  define DL_BITS       (D_BITS - DD_BITS)
  90 #endif
  91 #if (DL_BITS < 16)
  92 #  define DL_SIZE       LZO_SIZE(DL_BITS)
  93 #  define DL_MASK       LZO_MASK(DL_BITS)
  94 #else
  95 #  define DL_SIZE       LZO_USIZE(DL_BITS)
  96 #  define DL_MASK       LZO_UMASK(DL_BITS)
  97 #endif
  98
  99
 100 #if (D_BITS != DL_BITS + DD_BITS)
 101 #  error "D_BITS does not match"
 102 #endif
 103 #if (D_BITS < 6 || D_BITS > 18)
 104 #  error "invalid D_BITS"
 105 #endif
 106 #if (DL_BITS < 6 || DL_BITS > 20)
 107 #  error "invalid DL_BITS"
 108 #endif
 109 #if (DD_BITS < 0 || DD_BITS > 6)
 110 #  error "invalid DD_BITS"
 111 #endif
 112
 113
 114 #if !defined(DL_MIN_LEN)
 115 #  define DL_MIN_LEN    3
 116 #endif
 117 #if !defined(DL_SHIFT)
 118 #  define DL_SHIFT      ((DL_BITS + (DL_MIN_LEN - 1)) / DL_MIN_LEN)
 119 #endif
 120
 121
 122
 123 /***********************************************************************
 124 // dictionary access
 125 ************************************************************************/
 126
 127 #define LZO_HASH_GZIP                   1
 128 #define LZO_HASH_GZIP_INCREMENTAL       2
 129 #define LZO_HASH_LZO_INCREMENTAL_A      3
 130 #define LZO_HASH_LZO_INCREMENTAL_B      4
 131
 132 #if !defined(LZO_HASH)
 133 #  error "choose a hashing strategy"
 134 #endif
 135
 136 #undef DM
 137 #undef DX
 138
 139 #if (DL_MIN_LEN == 3)
 140 #  define _DV2_A(p,shift1,shift2) \
 141         (((( (lzo_xint)((p)[0]) << shift1) ^ (p)[1]) << shift2) ^ (p)[2])
 142 #  define _DV2_B(p,shift1,shift2) \
 143         (((( (lzo_xint)((p)[2]) << shift1) ^ (p)[1]) << shift2) ^ (p)[0])
 144 #  define _DV3_B(p,shift1,shift2,shift3) \
 145         ((_DV2_B((p)+1,shift1,shift2) << (shift3)) ^ (p)[0])
 146 #elif (DL_MIN_LEN == 2)
 147 #  define _DV2_A(p,shift1,shift2) \
 148         (( (lzo_xint)(p[0]) << shift1) ^ p[1])
 149 #  define _DV2_B(p,shift1,shift2) \
 150         (( (lzo_xint)(p[1]) << shift1) ^ p[2])
 151 #else
 152 #  error "invalid DL_MIN_LEN"
 153 #endif
 154 #define _DV_A(p,shift)      _DV2_A(p,shift,shift)
 155 #define _DV_B(p,shift)      _DV2_B(p,shift,shift)
 156 #define DA2(p,s1,s2) \
 157         (((((lzo_xint)((p)[2]) << (s2)) + (p)[1]) << (s1)) + (p)[0])
 158 #define DS2(p,s1,s2) \
 159         (((((lzo_xint)((p)[2]) << (s2)) - (p)[1]) << (s1)) - (p)[0])
 160 #define DX2(p,s1,s2) \
 161         (((((lzo_xint)((p)[2]) << (s2)) ^ (p)[1]) << (s1)) ^ (p)[0])
 162 #define DA3(p,s1,s2,s3) ((DA2((p)+1,s2,s3) << (s1)) + (p)[0])
 163 #define DS3(p,s1,s2,s3) ((DS2((p)+1,s2,s3) << (s1)) - (p)[0])
 164 #define DX3(p,s1,s2,s3) ((DX2((p)+1,s2,s3) << (s1)) ^ (p)[0])
 165 #define DMS(v,s)        ((lzo_uint) (((v) & (D_MASK >> (s))) << (s)))
 166 #define DM(v)           DMS(v,0)
 167
 168
 169 #if (LZO_HASH == LZO_HASH_GZIP)
 170    /* hash function like in gzip/zlib (deflate) */
 171 #  define _DINDEX(dv,p)     (_DV_A((p),DL_SHIFT))
 172
 173 #elif (LZO_HASH == LZO_HASH_GZIP_INCREMENTAL)
 174    /* incremental hash like in gzip/zlib (deflate) */
 175 #  define __LZO_HASH_INCREMENTAL 1
 176 #  define DVAL_FIRST(dv,p)  dv = _DV_A((p),DL_SHIFT)
 177 #  define DVAL_NEXT(dv,p)   dv = (((dv) << DL_SHIFT) ^ p[2])
 178 #  define _DINDEX(dv,p)     (dv)
 179 #  define DVAL_LOOKAHEAD    DL_MIN_LEN
 180
 181 #elif (LZO_HASH == LZO_HASH_LZO_INCREMENTAL_A)
 182    /* incremental LZO hash version A */
 183 #  define __LZO_HASH_INCREMENTAL 1
 184 #  define DVAL_FIRST(dv,p)  dv = _DV_A((p),5)
 185 #  define DVAL_NEXT(dv,p) \
 186                 dv ^= (lzo_xint)(p[-1]) << (2*5); dv = (((dv) << 5) ^ p[2])
 187 #  define _DINDEX(dv,p)     ((DMUL(0x9f5f,dv)) >> 5)
 188 #  define DVAL_LOOKAHEAD    DL_MIN_LEN
 189
 190 #elif (LZO_HASH == LZO_HASH_LZO_INCREMENTAL_B)
 191    /* incremental LZO hash version B */
 192 #  define __LZO_HASH_INCREMENTAL 1
 193 #  define DVAL_FIRST(dv,p)  dv = _DV_B((p),5)
 194 #  define DVAL_NEXT(dv,p) \
 195                 dv ^= p[-1]; dv = (((dv) >> 5) ^ ((lzo_xint)(p[2]) << (2*5)))
 196 #  define _DINDEX(dv,p)     ((DMUL(0x9f5f,dv)) >> 5)
 197 #  define DVAL_LOOKAHEAD    DL_MIN_LEN
 198
 199 #else
 200 #  error "choose a hashing strategy"
 201 #endif
 202
 203
 204 #ifndef DINDEX
 205 #define DINDEX(dv,p)        ((lzo_uint)((_DINDEX(dv,p)) & DL_MASK) << DD_BITS)
 206 #endif
 207 #if !defined(DINDEX1) && defined(D_INDEX1)
 208 #define DINDEX1             D_INDEX1
 209 #endif
 210 #if !defined(DINDEX2) && defined(D_INDEX2)
 211 #define DINDEX2             D_INDEX2
 212 #endif
 213
 214
 215
 216 #if !defined(__LZO_HASH_INCREMENTAL)
 217 #  define DVAL_FIRST(dv,p)  ((void) 0)
 218 #  define DVAL_NEXT(dv,p)   ((void) 0)
 219 #  define DVAL_LOOKAHEAD    0
 220 #endif
 221
 222
 223 #if !defined(DVAL_ASSERT)
 224 #if defined(__LZO_HASH_INCREMENTAL) && !defined(NDEBUG)
 225 #if (LZO_CC_CLANG || (LZO_CC_GNUC >= 0x020700ul) || LZO_CC_LLVM)
 226 static void __attribute__((__unused__))
 227 #else
 228 static void
 229 #endif
 230 DVAL_ASSERT(lzo_xint dv, const lzo_bytep p)
 231 {
 232     lzo_xint df;
 233     DVAL_FIRST(df,(p));
 234     assert(DINDEX(dv,p) == DINDEX(df,p));
 235 }
 236 #else
 237 #  define DVAL_ASSERT(dv,p) ((void) 0)
 238 #endif
 239 #endif
 240
 241
 242
 243 /***********************************************************************
 244 // dictionary updating
 245 ************************************************************************/
 246
 247 #if (LZO_DICT_USE_PTR)
 248 #  define DENTRY(p,in)                          (p)
 249 #  define GINDEX(m_pos,m_off,dict,dindex,in)    m_pos = dict[dindex]
 250 #else
 251 #  define DENTRY(p,in)                          ((lzo_dict_t) pd(p, in))
 252 #  define GINDEX(m_pos,m_off,dict,dindex,in)    m_off = dict[dindex]
 253 #endif
 254
 255
 256 #if (DD_BITS == 0)
 257
 258 #  define UPDATE_D(dict,drun,dv,p,in)       dict[ DINDEX(dv,p) ] = DENTRY(p,in)
 259 #  define UPDATE_I(dict,drun,index,p,in)    dict[index] = DENTRY(p,in)
 260 #  define UPDATE_P(ptr,drun,p,in)           (ptr)[0] = DENTRY(p,in)
 261
 262 #else
 263
 264 #  define UPDATE_D(dict,drun,dv,p,in)   \
 265         dict[ DINDEX(dv,p) + drun++ ] = DENTRY(p,in); drun &= DD_MASK
 266 #  define UPDATE_I(dict,drun,index,p,in)    \
 267         dict[ (index) + drun++ ] = DENTRY(p,in); drun &= DD_MASK
 268 #  define UPDATE_P(ptr,drun,p,in)   \
 269         (ptr) [ drun++ ] = DENTRY(p,in); drun &= DD_MASK
 270
 271 #endif
 272
 273
 274 /***********************************************************************
 275 // test for a match
 276 ************************************************************************/
 277
 278 #if (LZO_DICT_USE_PTR)
 279
 280 /* m_pos is either NULL or a valid pointer */
 281 #define LZO_CHECK_MPOS_DET(m_pos,m_off,in,ip,max_offset) \
 282         (m_pos == NULL || (m_off = pd(ip, m_pos)) > max_offset)
 283
 284 /* m_pos may point anywhere... */
 285 #define LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,max_offset) \
 286     (BOUNDS_CHECKING_OFF_IN_EXPR(( \
 287         m_pos = ip - (lzo_uint) PTR_DIFF(ip,m_pos), \
 288         PTR_LT(m_pos,in) || \
 289         (m_off = (lzo_uint) PTR_DIFF(ip,m_pos)) == 0 || \
 290          m_off > max_offset )))
 291
 292 #else
 293
 294 #define LZO_CHECK_MPOS_DET(m_pos,m_off,in,ip,max_offset) \
 295         (m_off == 0 || \
 296          ((m_off = pd(ip, in) - m_off) > max_offset) || \
 297          (m_pos = (ip) - (m_off), 0) )
 298
 299 #define LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,max_offset) \
 300         (pd(ip, in) <= m_off || \
 301          ((m_off = pd(ip, in) - m_off) > max_offset) || \
 302          (m_pos = (ip) - (m_off), 0) )
 303
 304 #endif
 305
 306
 307 #if (LZO_DETERMINISTIC)
 308 #  define LZO_CHECK_MPOS    LZO_CHECK_MPOS_DET
 309 #else
 310 #  define LZO_CHECK_MPOS    LZO_CHECK_MPOS_NON_DET
 311 #endif
 312
 313
 314
 315 #ifdef __cplusplus
 316 } /* extern "C" */
 317 #endif
 318
 319 #endif /* already included */
 320
 321 /*
 322 vi:ts=4:et
 323 */
 324