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