grub/lib/LzFind.h

fa9e4066f08beec538e775443c5be79dd423fcabahrens/*
fa9e4066f08beec538e775443c5be79dd423fcabahrens *  GRUB  --  GRand Unified Bootloader
fa9e4066f08beec538e775443c5be79dd423fcabahrens *  Copyright (c) 1999-2008 Igor Pavlov
fa9e4066f08beec538e775443c5be79dd423fcabahrens *  Copyright (C) 2008  Free Software Foundation, Inc.
441d80aa4f613b6298fc8bd3151f4be02dbf84fclling *
441d80aa4f613b6298fc8bd3151f4be02dbf84fclling *  GRUB is free software: you can redistribute it and/or modify
fa9e4066f08beec538e775443c5be79dd423fcabahrens *  it under the terms of the GNU General Public License as published by
fa9e4066f08beec538e775443c5be79dd423fcabahrens *  the Free Software Foundation, either version 3 of the License, or
fa9e4066f08beec538e775443c5be79dd423fcabahrens *  (at your option) any later version.
fa9e4066f08beec538e775443c5be79dd423fcabahrens *
fa9e4066f08beec538e775443c5be79dd423fcabahrens *  GRUB is distributed in the hope that it will be useful,
fa9e4066f08beec538e775443c5be79dd423fcabahrens *  but WITHOUT ANY WARRANTY; without even the implied warranty of
fa9e4066f08beec538e775443c5be79dd423fcabahrens *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
fa9e4066f08beec538e775443c5be79dd423fcabahrens *  GNU General Public License for more details.
fa9e4066f08beec538e775443c5be79dd423fcabahrens *
fa9e4066f08beec538e775443c5be79dd423fcabahrens *  You should have received a copy of the GNU General Public License
fa9e4066f08beec538e775443c5be79dd423fcabahrens *  along with GRUB.  If not, see <http://www.gnu.org/licenses/>.
fa9e4066f08beec538e775443c5be79dd423fcabahrens */
fa9e4066f08beec538e775443c5be79dd423fcabahrens
fa9e4066f08beec538e775443c5be79dd423fcabahrens/*
fa9e4066f08beec538e775443c5be79dd423fcabahrens * This code was taken from LZMA SDK 4.58 beta, and was slightly modified
47cb52daa729f19e298c85a84e8df069365c5232Jeff Bonwick * to adapt it to GRUB's requirement.
aab80726335c76a7cae32c7300890248d73a51e3George Wilson *
e9103aaee0c546d4644791198c54abb03c89969eGarrett D'Amore * See <http://www.7-zip.org>, for more information about LZMA.
a7a845e4bf22fd1b2a284729ccd95c7370a0438cSteven Hartland */
c3d26abc9ee97b4f60233556aadeb57e0bd30bb9Matthew Ahrens
fa9e4066f08beec538e775443c5be79dd423fcabahrens#ifndef __LZFIND_H
fa9e4066f08beec538e775443c5be79dd423fcabahrens#define __LZFIND_H
fa9e4066f08beec538e775443c5be79dd423fcabahrens
fa9e4066f08beec538e775443c5be79dd423fcabahrens#include <grub/lib/LzmaTypes.h>
fa9e4066f08beec538e775443c5be79dd423fcabahrens
fa9e4066f08beec538e775443c5be79dd423fcabahrenstypedef UInt32 CLzRef;
fa9e4066f08beec538e775443c5be79dd423fcabahrens
fa9e4066f08beec538e775443c5be79dd423fcabahrenstypedef struct _CMatchFinder
fa9e4066f08beec538e775443c5be79dd423fcabahrens{
fa9e4066f08beec538e775443c5be79dd423fcabahrens  Byte *buffer;
fa9e4066f08beec538e775443c5be79dd423fcabahrens  UInt32 pos;
fa9e4066f08beec538e775443c5be79dd423fcabahrens  UInt32 posLimit;
fa9e4066f08beec538e775443c5be79dd423fcabahrens  UInt32 streamPos;
fa9e4066f08beec538e775443c5be79dd423fcabahrens  UInt32 lenLimit;
fa9e4066f08beec538e775443c5be79dd423fcabahrens
fa9e4066f08beec538e775443c5be79dd423fcabahrens  UInt32 cyclicBufferPos;
fa9e4066f08beec538e775443c5be79dd423fcabahrens  UInt32 cyclicBufferSize; /* it must be = (historySize + 1) */
fa9e4066f08beec538e775443c5be79dd423fcabahrens
fa9e4066f08beec538e775443c5be79dd423fcabahrens  UInt32 matchMaxLen;
fa9e4066f08beec538e775443c5be79dd423fcabahrens  CLzRef *hash;
fa9e4066f08beec538e775443c5be79dd423fcabahrens  CLzRef *son;
fa9e4066f08beec538e775443c5be79dd423fcabahrens  UInt32 hashMask;
fa9e4066f08beec538e775443c5be79dd423fcabahrens  UInt32 cutValue;
fa9e4066f08beec538e775443c5be79dd423fcabahrens
fa9e4066f08beec538e775443c5be79dd423fcabahrens  Byte *bufferBase;
fa9e4066f08beec538e775443c5be79dd423fcabahrens  ISeqInStream *stream;
fa9e4066f08beec538e775443c5be79dd423fcabahrens  int streamEndWasReached;
fa9e4066f08beec538e775443c5be79dd423fcabahrens
fa9e4066f08beec538e775443c5be79dd423fcabahrens  UInt32 blockSize;
5d7b4d438c4a51eccc95e77a83a437b4d48380ebMatthew Ahrens  UInt32 keepSizeBefore;
420dfc9585ff67e83ee7800a7ad2ebe1a9145983Chris Siden  UInt32 keepSizeAfter;
420dfc9585ff67e83ee7800a7ad2ebe1a9145983Chris Siden
fa9e4066f08beec538e775443c5be79dd423fcabahrens  UInt32 numHashBytes;
fa9e4066f08beec538e775443c5be79dd423fcabahrens  int directInput;
fa9e4066f08beec538e775443c5be79dd423fcabahrens  int btMode;
fa9e4066f08beec538e775443c5be79dd423fcabahrens  /* int skipModeBits; */
fa9e4066f08beec538e775443c5be79dd423fcabahrens  int bigHash;
fa9e4066f08beec538e775443c5be79dd423fcabahrens  UInt32 historySize;
fa9e4066f08beec538e775443c5be79dd423fcabahrens  UInt32 fixedHashSize;
fa9e4066f08beec538e775443c5be79dd423fcabahrens  UInt32 hashSizeSum;
fa9e4066f08beec538e775443c5be79dd423fcabahrens  UInt32 numSons;
fa9e4066f08beec538e775443c5be79dd423fcabahrens  SRes result;
fa9e4066f08beec538e775443c5be79dd423fcabahrens  UInt32 crc[256];
fa9e4066f08beec538e775443c5be79dd423fcabahrens} CMatchFinder;
fa9e4066f08beec538e775443c5be79dd423fcabahrens
fa9e4066f08beec538e775443c5be79dd423fcabahrens#define Inline_MatchFinder_GetPointerToCurrentPos(p) ((p)->buffer)
fa9e4066f08beec538e775443c5be79dd423fcabahrens#define Inline_MatchFinder_GetIndexByte(p, index) ((p)->buffer[(Int32)(index)])
fa9e4066f08beec538e775443c5be79dd423fcabahrens
420dfc9585ff67e83ee7800a7ad2ebe1a9145983Chris Siden#define Inline_MatchFinder_GetNumAvailableBytes(p) ((p)->streamPos - (p)->pos)
420dfc9585ff67e83ee7800a7ad2ebe1a9145983Chris Siden
420dfc9585ff67e83ee7800a7ad2ebe1a9145983Chris Sidenint MatchFinder_NeedMove(CMatchFinder *p);
420dfc9585ff67e83ee7800a7ad2ebe1a9145983Chris SidenByte *MatchFinder_GetPointerToCurrentPos(CMatchFinder *p);
420dfc9585ff67e83ee7800a7ad2ebe1a9145983Chris Sidenvoid MatchFinder_MoveBlock(CMatchFinder *p);
420dfc9585ff67e83ee7800a7ad2ebe1a9145983Chris Sidenvoid MatchFinder_ReadIfRequired(CMatchFinder *p);
420dfc9585ff67e83ee7800a7ad2ebe1a9145983Chris Siden
420dfc9585ff67e83ee7800a7ad2ebe1a9145983Chris Sidenvoid MatchFinder_Construct(CMatchFinder *p);
420dfc9585ff67e83ee7800a7ad2ebe1a9145983Chris Siden
fa9e4066f08beec538e775443c5be79dd423fcabahrens/* Conditions:
fa9e4066f08beec538e775443c5be79dd423fcabahrens     historySize <= 3 GB
fa9e4066f08beec538e775443c5be79dd423fcabahrens     keepAddBufferBefore + matchMaxLen + keepAddBufferAfter < 511MB
fa9e4066f08beec538e775443c5be79dd423fcabahrens*/
fa9e4066f08beec538e775443c5be79dd423fcabahrensint MatchFinder_Create(CMatchFinder *p, UInt32 historySize,
fa9e4066f08beec538e775443c5be79dd423fcabahrens    UInt32 keepAddBufferBefore, UInt32 matchMaxLen, UInt32 keepAddBufferAfter,
2fdbea25c2ba89186b8a6b7c6840ebc9f4dff245Aleksandr Guzovskiy    ISzAlloc *alloc);
fa9e4066f08beec538e775443c5be79dd423fcabahrensvoid MatchFinder_Free(CMatchFinder *p, ISzAlloc *alloc);
fa9e4066f08beec538e775443c5be79dd423fcabahrensvoid MatchFinder_Normalize3(UInt32 subValue, CLzRef *items, UInt32 numItems);
fa9e4066f08beec538e775443c5be79dd423fcabahrensvoid MatchFinder_ReduceOffsets(CMatchFinder *p, UInt32 subValue);
fa9e4066f08beec538e775443c5be79dd423fcabahrens
fa9e4066f08beec538e775443c5be79dd423fcabahrensUInt32 * GetMatchesSpec1(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *buffer, CLzRef *son,
fa9e4066f08beec538e775443c5be79dd423fcabahrens    UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 _cutValue,
fa9e4066f08beec538e775443c5be79dd423fcabahrens    UInt32 *distances, UInt32 maxLen);
fa9e4066f08beec538e775443c5be79dd423fcabahrens
fa9e4066f08beec538e775443c5be79dd423fcabahrens/*
fa9e4066f08beec538e775443c5be79dd423fcabahrensConditions:
b24ab6762772a3f6a89393947930c7fa61306783Jeff Bonwick  Mf_GetNumAvailableBytes_Func must be called before each Mf_GetMatchLen_Func.
fa9e4066f08beec538e775443c5be79dd423fcabahrens  Mf_GetPointerToCurrentPos_Func's result must be used only before any other function
e14bb3258d05c1b1077e2db7cf77088924e56919Jeff Bonwick*/
fa9e4066f08beec538e775443c5be79dd423fcabahrens
88ecc943b4eb72f7c4fbbd8435997b85ef171fc3George Wilsontypedef void (*Mf_Init_Func)(void *object);
fa9e4066f08beec538e775443c5be79dd423fcabahrenstypedef Byte (*Mf_GetIndexByte_Func)(void *object, Int32 index);
4f5064b73b1cc9de1d0f1a2ae700d519d4d565dfMark J Musantetypedef UInt32 (*Mf_GetNumAvailableBytes_Func)(void *object);
3b2aab18808792cbd248a12f1edf139b89833c13Matthew Ahrenstypedef const Byte * (*Mf_GetPointerToCurrentPos_Func)(void *object);
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Lingtypedef UInt32 (*Mf_GetMatches_Func)(void *object, UInt32 *distances);
cde58dbc6a23d4d38db7c8866312be83221c765fMatthew Ahrenstypedef void (*Mf_Skip_Func)(void *object, UInt32);
fa9e4066f08beec538e775443c5be79dd423fcabahrens
ad135b5d644628e791c3188a6ecbd9c257961ef8Christopher Sidentypedef struct _IMatchFinder
3b2aab18808792cbd248a12f1edf139b89833c13Matthew Ahrens{
fa9e4066f08beec538e775443c5be79dd423fcabahrens  Mf_Init_Func Init;
004388ebfdfe2ed7dfd2d153a876dfcc22d2c006casper  Mf_GetIndexByte_Func GetIndexByte;
fa9e4066f08beec538e775443c5be79dd423fcabahrens  Mf_GetNumAvailableBytes_Func GetNumAvailableBytes;
fa9e4066f08beec538e775443c5be79dd423fcabahrens  Mf_GetPointerToCurrentPos_Func GetPointerToCurrentPos;
fa9e4066f08beec538e775443c5be79dd423fcabahrens  Mf_GetMatches_Func GetMatches;
fa9e4066f08beec538e775443c5be79dd423fcabahrens  Mf_Skip_Func Skip;
fa9e4066f08beec538e775443c5be79dd423fcabahrens} IMatchFinder;
fa9e4066f08beec538e775443c5be79dd423fcabahrens
fa9e4066f08beec538e775443c5be79dd423fcabahrensvoid MatchFinder_CreateVTable(CMatchFinder *p, IMatchFinder *vTable);
fa9e4066f08beec538e775443c5be79dd423fcabahrens
b24ab6762772a3f6a89393947930c7fa61306783Jeff Bonwickvoid MatchFinder_Init(CMatchFinder *p);
fa9e4066f08beec538e775443c5be79dd423fcabahrensUInt32 Bt3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances);
741652b0d7a641dcc9c966750c26e41bcc641863Etienne DechampsUInt32 Hc3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances);
741652b0d7a641dcc9c966750c26e41bcc641863Etienne Dechampsvoid Bt3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num);
420dfc9585ff67e83ee7800a7ad2ebe1a9145983Chris Sidenvoid Hc3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num);
420dfc9585ff67e83ee7800a7ad2ebe1a9145983Chris Siden
420dfc9585ff67e83ee7800a7ad2ebe1a9145983Chris Siden#endif
420dfc9585ff67e83ee7800a7ad2ebe1a9145983Chris Siden