/* lzo_dict.h -- dictionary definitions for the the LZO library
This file is part of the LZO real-time data compression library.
Copyright (C) 2008 Markus Franz Xaver Johannes Oberhumer
Copyright (C) 2007 Markus Franz Xaver Johannes Oberhumer
Copyright (C) 2006 Markus Franz Xaver Johannes Oberhumer
Copyright (C) 2005 Markus Franz Xaver Johannes Oberhumer
Copyright (C) 2004 Markus Franz Xaver Johannes Oberhumer
Copyright (C) 2003 Markus Franz Xaver Johannes Oberhumer
Copyright (C) 2002 Markus Franz Xaver Johannes Oberhumer
Copyright (C) 2001 Markus Franz Xaver Johannes Oberhumer
Copyright (C) 2000 Markus Franz Xaver Johannes Oberhumer
Copyright (C) 1999 Markus Franz Xaver Johannes Oberhumer
Copyright (C) 1998 Markus Franz Xaver Johannes Oberhumer
Copyright (C) 1997 Markus Franz Xaver Johannes Oberhumer
Copyright (C) 1996 Markus Franz Xaver Johannes Oberhumer
All Rights Reserved.
The LZO library is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License as
published by the Free Software Foundation; either version 2 of
the License, or (at your option) any later version.
The LZO library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with the LZO library; see the file COPYING.
If not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
Markus F.X.J. Oberhumer
<markus@oberhumer.com>
http://www.oberhumer.com/opensource/lzo/
*/
/* WARNING: this file should *not* be used by applications. It is
part of the implementation of the library and is subject
to change.
*/
#ifndef __LZO_DICT_H
#define __LZO_DICT_H
#ifdef __cplusplus
extern "C" {
#endif
/***********************************************************************
// dictionary size
************************************************************************/
/* dictionary needed for compression */
#if !defined(D_BITS) && defined(DBITS)
# define D_BITS DBITS
#endif
#if !defined(D_BITS)
# error "D_BITS is not defined"
#endif
#if (D_BITS < 16)
# define D_SIZE LZO_SIZE(D_BITS)
# define D_MASK LZO_MASK(D_BITS)
#else
# define D_SIZE LZO_USIZE(D_BITS)
# define D_MASK LZO_UMASK(D_BITS)
#endif
#define D_HIGH ((D_MASK >> 1) + 1)
/* dictionary depth */
#if !defined(DD_BITS)
# define DD_BITS 0
#endif
#define DD_SIZE LZO_SIZE(DD_BITS)
#define DD_MASK LZO_MASK(DD_BITS)
/* dictionary length */
#if !defined(DL_BITS)
# define DL_BITS (D_BITS - DD_BITS)
#endif
#if (DL_BITS < 16)
# define DL_SIZE LZO_SIZE(DL_BITS)
# define DL_MASK LZO_MASK(DL_BITS)
#else
# define DL_SIZE LZO_USIZE(DL_BITS)
# define DL_MASK LZO_UMASK(DL_BITS)
#endif
#if (D_BITS != DL_BITS + DD_BITS)
# error "D_BITS does not match"
#endif
#if (D_BITS < 8 || D_BITS > 18)
# error "invalid D_BITS"
#endif
#if (DL_BITS < 8 || DL_BITS > 20)
# error "invalid DL_BITS"
#endif
#if (DD_BITS < 0 || DD_BITS > 6)
# error "invalid DD_BITS"
#endif
#if !defined(DL_MIN_LEN)
# define DL_MIN_LEN 3
#endif
#if !defined(DL_SHIFT)
# define DL_SHIFT ((DL_BITS + (DL_MIN_LEN - 1)) / DL_MIN_LEN)
#endif
/***********************************************************************
// dictionary access
************************************************************************/
#define LZO_HASH_GZIP 1
#define LZO_HASH_GZIP_INCREMENTAL 2
#define LZO_HASH_LZO_INCREMENTAL_A 3
#define LZO_HASH_LZO_INCREMENTAL_B 4
#if !defined(LZO_HASH)
# error "choose a hashing strategy"
#endif
#undef DM
#undef DX
#if (DL_MIN_LEN == 3)
# define _DV2_A(p,shift1,shift2) \
(((( (lzo_xint)((p)[0]) << shift1) ^ (p)[1]) << shift2) ^ (p)[2])
# define _DV2_B(p,shift1,shift2) \
(((( (lzo_xint)((p)[2]) << shift1) ^ (p)[1]) << shift2) ^ (p)[0])
# define _DV3_B(p,shift1,shift2,shift3) \
((_DV2_B((p)+1,shift1,shift2) << (shift3)) ^ (p)[0])
#elif (DL_MIN_LEN == 2)
# define _DV2_A(p,shift1,shift2) \
(( (lzo_xint)(p[0]) << shift1) ^ p[1])
# define _DV2_B(p,shift1,shift2) \
(( (lzo_xint)(p[1]) << shift1) ^ p[2])
#else
# error "invalid DL_MIN_LEN"
#endif
#define _DV_A(p,shift) _DV2_A(p,shift,shift)
#define _DV_B(p,shift) _DV2_B(p,shift,shift)
#define DA2(p,s1,s2) \
(((((lzo_xint)((p)[2]) << (s2)) + (p)[1]) << (s1)) + (p)[0])
#define DS2(p,s1,s2) \
(((((lzo_xint)((p)[2]) << (s2)) - (p)[1]) << (s1)) - (p)[0])
#define DX2(p,s1,s2) \
(((((lzo_xint)((p)[2]) << (s2)) ^ (p)[1]) << (s1)) ^ (p)[0])
#define DA3(p,s1,s2,s3) ((DA2((p)+1,s2,s3) << (s1)) + (p)[0])
#define DS3(p,s1,s2,s3) ((DS2((p)+1,s2,s3) << (s1)) - (p)[0])
#define DX3(p,s1,s2,s3) ((DX2((p)+1,s2,s3) << (s1)) ^ (p)[0])
#define DMS(v,s) ((lzo_uint) (((v) & (D_MASK >> (s))) << (s)))
#define DM(v) DMS(v,0)
#if (LZO_HASH == LZO_HASH_GZIP)
/* hash function like in gzip/zlib (deflate) */
# define _DINDEX(dv,p) (_DV_A((p),DL_SHIFT))
#elif (LZO_HASH == LZO_HASH_GZIP_INCREMENTAL)
/* incremental hash like in gzip/zlib (deflate) */
# define __LZO_HASH_INCREMENTAL
# define DVAL_FIRST(dv,p) dv = _DV_A((p),DL_SHIFT)
# define DVAL_NEXT(dv,p) dv = (((dv) << DL_SHIFT) ^ p[2])
# define _DINDEX(dv,p) (dv)
# define DVAL_LOOKAHEAD DL_MIN_LEN
#elif (LZO_HASH == LZO_HASH_LZO_INCREMENTAL_A)
/* incremental LZO hash version A */
# define __LZO_HASH_INCREMENTAL
# define DVAL_FIRST(dv,p) dv = _DV_A((p),5)
# define DVAL_NEXT(dv,p) \
dv ^= (lzo_xint)(p[-1]) << (2*5); dv = (((dv) << 5) ^ p[2])
# define _DINDEX(dv,p) ((DMUL(0x9f5f,dv)) >> 5)
# define DVAL_LOOKAHEAD DL_MIN_LEN
#elif (LZO_HASH == LZO_HASH_LZO_INCREMENTAL_B)
/* incremental LZO hash version B */
# define __LZO_HASH_INCREMENTAL
# define DVAL_FIRST(dv,p) dv = _DV_B((p),5)
# define DVAL_NEXT(dv,p) \
dv ^= p[-1]; dv = (((dv) >> 5) ^ ((lzo_xint)(p[2]) << (2*5)))
# define _DINDEX(dv,p) ((DMUL(0x9f5f,dv)) >> 5)
# define DVAL_LOOKAHEAD DL_MIN_LEN
#else
# error "choose a hashing strategy"
#endif
#ifndef DINDEX
#define DINDEX(dv,p) ((lzo_uint)((_DINDEX(dv,p)) & DL_MASK) << DD_BITS)
#endif
#if !defined(DINDEX1) && defined(D_INDEX1)
#define DINDEX1 D_INDEX1
#endif
#if !defined(DINDEX2) && defined(D_INDEX2)
#define DINDEX2 D_INDEX2
#endif
#if !defined(__LZO_HASH_INCREMENTAL)
# define DVAL_FIRST(dv,p) ((void) 0)
# define DVAL_NEXT(dv,p) ((void) 0)
# define DVAL_LOOKAHEAD 0
#endif
#if !defined(DVAL_ASSERT)
#if defined(__LZO_HASH_INCREMENTAL) && !defined(NDEBUG)
static void DVAL_ASSERT(lzo_xint dv, const lzo_bytep p)
{
lzo_xint df;
DVAL_FIRST(df,(p));
assert(DINDEX(dv,p) == DINDEX(df,p));
}
#else
# define DVAL_ASSERT(dv,p) ((void) 0)
#endif
#endif
/***********************************************************************
// dictionary updating
************************************************************************/
#if defined(LZO_DICT_USE_PTR)
# define DENTRY(p,in) (p)
# define GINDEX(m_pos,m_off,dict,dindex,in) m_pos = dict[dindex]
#else
# define DENTRY(p,in) ((lzo_uint) ((p)-(in)))
# define GINDEX(m_pos,m_off,dict,dindex,in) m_off = dict[dindex]
#endif
#if (DD_BITS == 0)
# define UPDATE_D(dict,drun,dv,p,in) dict[ DINDEX(dv,p) ] = DENTRY(p,in)
# define UPDATE_I(dict,drun,index,p,in) dict[index] = DENTRY(p,in)
# define UPDATE_P(ptr,drun,p,in) (ptr)[0] = DENTRY(p,in)
#else
# define UPDATE_D(dict,drun,dv,p,in) \
dict[ DINDEX(dv,p) + drun++ ] = DENTRY(p,in); drun &= DD_MASK
# define UPDATE_I(dict,drun,index,p,in) \
dict[ (index) + drun++ ] = DENTRY(p,in); drun &= DD_MASK
# define UPDATE_P(ptr,drun,p,in) \
(ptr) [ drun++ ] = DENTRY(p,in); drun &= DD_MASK
#endif
/***********************************************************************
// test for a match
************************************************************************/
#if defined(LZO_DICT_USE_PTR)
/* m_pos is either NULL or a valid pointer */
#define LZO_CHECK_MPOS_DET(m_pos,m_off,in,ip,max_offset) \
(m_pos == NULL || (m_off = pd(ip, m_pos)) > max_offset)
/* m_pos may point anywhere... */
#define LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,max_offset) \
(BOUNDS_CHECKING_OFF_IN_EXPR(( \
m_pos = ip - (lzo_uint) PTR_DIFF(ip,m_pos), \
PTR_LT(m_pos,in) || \
(m_off = (lzo_uint) PTR_DIFF(ip,m_pos)) <= 0 || \
m_off > max_offset )))
#else
#define LZO_CHECK_MPOS_DET(m_pos,m_off,in,ip,max_offset) \
(m_off == 0 || \
((m_off = pd(ip, in) - m_off) > max_offset) || \
(m_pos = (ip) - (m_off), 0) )
#define LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,max_offset) \
(pd(ip, in) <= m_off || \
((m_off = pd(ip, in) - m_off) > max_offset) || \
(m_pos = (ip) - (m_off), 0) )
#endif
#if defined(LZO_DETERMINISTIC)
# define LZO_CHECK_MPOS LZO_CHECK_MPOS_DET
#else
# define LZO_CHECK_MPOS LZO_CHECK_MPOS_NON_DET
#endif
#ifdef __cplusplus
} /* extern "C" */
#endif
#endif /* already included */
/*
vi:ts=4:et
*/
