lzo/src/lzo_dict.h - platform/external/syslinux - Git at Google

 /* lzo_dict.h -- dictionary definitions for the the LZO library

    This file is part of the LZO real-time data compression library.

    Copyright (C) 1996-2014 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 1

 #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 < 6 || D_BITS > 18)
 #  error "invalid D_BITS"
 #endif
 #if (DL_BITS < 6 || 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 1
 #  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 1
 #  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 1
 #  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)
 #if (LZO_CC_CLANG || (LZO_CC_GNUC >= 0x020700ul) || LZO_CC_LLVM)
 static void __attribute__((__unused__))
 #else
 static void
 #endif
 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 (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_dict_t) pd(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 (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 (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
 */
	/* lzo_dict.h -- dictionary definitions for the the LZO library

	This file is part of the LZO real-time data compression library.

	Copyright (C) 1996-2014 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 1

	#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 < 6 \|\| D_BITS > 18)
	# error "invalid D_BITS"
	#endif
	#if (DL_BITS < 6 \|\| 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 1
	# 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 1
	# 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 1
	# 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)
	#if (LZO_CC_CLANG \|\| (LZO_CC_GNUC >= 0x020700ul) \|\| LZO_CC_LLVM)
	static void __attribute__((__unused__))
	#else
	static void
	#endif
	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 (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_dict_t) pd(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 (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 (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
	*/