| /* 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 |
| */ |
| |
