///////////////////////////////////////////////////////////////////////////////
// LZWStream.h

#ifndef LZWStreamh
#define LZWStreamh

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

/*
This is a small suite of simple compression classes that use the LZWStream algorithm optionally using the GIF coding format.
There is a CLZWStreamEncoder class and a CLZWStreamDecoder class (both derived from CLZWStream).
You can specify a File or an area of memory for each class to act upon.
A file is specifed simply by its Path, a section of memory by its Base and Length.
The simplest way to use a CString to hold the data:
  CString S("anna and nanna banned bananas and bandannas");
  CLZWStreamEncoder E(S);
  // S is now the compressed data (or the original data if no compression was possible).
  int CompressedLength=S.GetLength(); // At this point S may contain NULLs before its end. GetLength returns the correct length for the compressed data.
  CLZWStreamDecoder D(S);
  //S is now back to the original data or empty if we ran out of memory or the data was corrupt.
  if(S.IsEmpty() && CompressedLength) AfxMessageBox("LZWStream Decompression Failed");

You can use the 
  CLZWStreamEncoder Encoder;
  const char* src="anna and nanna banned bananas and bandannas";
  char LZWStream[64];
  char dst[64];
  Encoder.Encode(src, LZWStream, strlen(src)+1);
  CLZWStreamDecoder Decoder;
  Decoder.Decode(LZWStream, dst, Encoder.GetOutSize());
  double Ratio=strlen(src)+1./Encoder.GetOutSize();

  DeleteFile("ReadMeNow.txt");
  CLZWStreamEncoder Encoder;
  Encoder.Encode("ReadMe.txt", "ReadMe.LZWStream");
  CLZWStreamDecoder Decoder;
  Decoder.Decode("ReadMe.LZWStream", "ReadMeNow.txt");
*/
#ifndef Languageh
  static const char* sBadFileName ("Bad File Name.");
  static const char* sBadMAlloc   ("Out of Memory (RAM).");
  static const char* sBadDataCode ("Bad Data Code.");
  static const char* sDictOverflow("LZWStream Dictionary overflowed.");
#endif

class CLZWStream {
public:
  CLZWStream() : GIFEncoding(false), GotStoredByte(false), InFile(0), OutFile(0), InEnd(0), InBuf(0), OutBuf(0), OutSize(0), WriteVal(0), ReadVal(0), WriteBitCtr(0), ReadBitCtr(0) {}
  DWORD GetOutSize() {return OutSize;}
  void  UseGIFEncoding(bool Use=true) {GIFEncoding=Use;} // When true, use marker codes: InitCode & EndCode.

protected:
  DWORD OutSize;
  bool  GIFEncoding; // When true, use marker codes: InitCode & EndCode.

        FILE* InFile;  //May be used with files or memory:
        FILE* OutFile;
  const char* InBuf;
  const char* InEnd; //Points at the Byte after the last Byte to read.
        char* OutBuf;
  bool GotStoredByte;
  int  StoredByteValue; // its an int so that we can test for EOF
  bool EndData()            {return GotStoredByte ? false : !(GotStoredByte=((StoredByteValue=GetC())!=EOF));}
  BYTE ReadByte()           {return (BYTE)(GotStoredByte ? GotStoredByte=false,StoredByteValue : GetC());}
  int  GetC()               {if( InFile) return fgetc(InFile); else if(InBuf<InEnd) return *InBuf++; return EOF;}
  void WriteByte(BYTE Byte) {if(OutFile) fputc(Byte, OutFile); else if(OutBuf) *OutBuf++=Byte;}
  void CopyFile() {
    rewind(InFile);
    char buf[512]; //File Copy:
    while(fwrite(buf, 1, fread(buf, 1, sizeof(buf), InFile), OutFile));
  }

  DWORD ReadVal, WriteVal;
  BYTE  ReadBitCtr, WriteBitCtr;
  WORD  DictIdx; // Word counter already known in the DecDict.

/*
2^WordCounterBits gives the maximum word counter in the DecDict during *all* the compressions.
Possible values: 3 to 25.
Beyond 12, you can have memory allocation errors depending on your compiler and computer.
*/
  #define WordCounterBits 12

// MaxDictIdx gives the maximum word counter in the DecDict during *one* compression.
// This constant is restricted to the range of EndCode to 2^WordCounterBits.
  WORD MaxDictIdx;

//InitCode and EndCode are both consecutive coming up just after the last known word in the initial EncDict.
  WORD InitCode, EndCode;
};

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> CLZWStreamEncoder <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

class CLZWStreamEncoder : public CLZWStream {
public:
  CLZWStreamEncoder() {}
  CLZWStreamEncoder(CString& S) {
    if(S.IsEmpty()) return;
    CString D;
    const char* Err=Encode(&*S,D.GetBufferSetLength(2*S.GetLength()),S.GetLength()+1); //+1 is to include the null terminator incase it really is a string
    D.ReleaseBuffer(OutSize);
    if(!Err && OutSize!=(DWORD)S.GetLength()) S=D; // Don't compress if an error occurred
  }
  CLZWStreamEncoder       (const char* In, char* Out, DWORD Bytes) {Encode(In, Out, Bytes);}
  const char* Encode(const char* In, char* Out, DWORD Bytes) {
    InBuf=In;
    InEnd=InBuf+Bytes;
    OutBuf=Out;
    const char* Return=Encode();
    OutSize=OutBuf-Out;
    if(OutSize>=Bytes) memcpy(Out,In,Bytes);
    return Return;
  }
  CLZWStreamEncoder       (const char* InPath, const char* OutPath) {Encode(InPath, OutPath);}
  const char* Encode(const char* InPath, const char* OutPath) {
    const char* Return=0;
    if((InFile=fopen(InPath, "rb"))) {
      if((OutFile=fopen(OutPath, "wb"))) {
        Return=Encode();
        if(ftell(InFile)<=ftell(OutFile)) {
          OutFile=freopen(OutPath, "wb", OutFile); // You can't just rewind a stream thats been written to.
          CopyFile(); //If we didn't compress things then just copy the file.
        }
        OutSize=ftell(OutFile);
        fclose(OutFile);
      }else Return=sBadFileName;
      fclose(InFile);
    }else Return=sBadFileName;
    return Return;
  }

private:
  typedef struct DictValStruct {
    WORD Character;
    WORD Code;
    DictValStruct* Left;
    DictValStruct* Right;
  } DictValNode, *DictValNodePtr;

/*
Returned parameters: None.
Action: Compresses with LZWStream method all bytes read by the function 'ReadInput'.
Errors: An input/output error could disturb the running of the program.
*/
  const char* Encode() {
    WriteByte(0xFF); //Compressed data token.
    if(!EndInput()) {
      MaxDictIdx=1<<12; //Range: 2^3 to 2^WordCounterBits.
      BitsInCounter=8;  //Range: 1 to WordCounterBits-1 (usually, for pictures, set up to 1, or 4, or 8, in the case of monochrome, or 16-colors, or 256-colors picture).
      EncMinBitCtr=(BitsInCounter==1 ? 3 : BitsInCounter+1);
      InitCode=1<<(EncMinBitCtr-1);
      EndCode=InitCode+(GIFEncoding ? 1 : -1);
      for(register WORD i=0; i<=EndCode; ++i) {
        if(!(EncDict[i]=(DictValNodePtr)malloc(sizeof(DictValNode)))) {
          while(i) free(EncDict[--i]);
          return sBadMAlloc;
        }
        EncDict[i]->Character=i;
        EncDict[i]->Code=i;
        EncDict[i]->Left=0;
        EncDict[i]->Right=0;
      }
      memset(&EncDict[i], 0, (MaxDictIdx-i)*sizeof(DictValNodePtr));
      DictIdx=EndCode+1;
      EncBitCtr=EncMinBitCtr;
      if(GIFEncoding) WriteCodeLR(InitCode);
      DictValNodePtr it=EncDict[ReadInput()];
      while(!EndInput()) {
        WORD Symbol=ReadInput();
        DictValNodePtr NewNode=FindNode(it,Symbol);
        if((NewNode!=it)&&(NewNode->Character==Symbol)) it=NewNode;
        else {
          WriteCodeLR(it->Code);
          const char* Err=AddNode(it,NewNode,Symbol);
          if(Err) return Err;
          if(DictIdx==MaxDictIdx) {
          if(GIFEncoding) WriteCodeLR(InitCode);
//Re-initialise EncDict
            for(register WORD i=0; i<MaxDictIdx; ++i) EncDict[i]->Left=EncDict[i]->Right=0;
            DictIdx=EndCode+1;
            EncBitCtr=EncMinBitCtr;
          }
          it=EncDict[Symbol];
      } }
      WriteCodeLR(it->Code);
      if(GIFEncoding) WriteCodeLR(EndCode);
      EncEndLR();
      FreeDict();
    }
    return 0;
  }

  void FreeDict() {for(register WORD i=0; (i<MaxDictIdx)&&(EncDict[i]); ++i) free(EncDict[i]);}

  BYTE EncBitCtr; //Bit counter in the encoding.

/*
Bit counter for each data in input.
With BitsInCounter=1, we can compress/decompress monochrome pictures
and with BitsInCounter=8, we can handle 256-colors pictures or any kind of files.
*/
  BYTE BitsInCounter;
  BYTE EncMinBitCtr; //Bit counter to encode 'InitCode'.

  DictValNodePtr EncDict[1<<WordCounterBits];

/*
Returned parameters: None.
Action: Reads BitsInCounter via the function 'ReadByte'.
Errors: An input/output error could disturb the running of the program.
*/
  WORD ReadInput() {
    while(ReadBitCtr<BitsInCounter) {
      ReadVal=(ReadVal<<8)|ReadByte();
      ReadBitCtr+=8;
    }
    ReadBitCtr-=BitsInCounter;
    WORD ReadCode=(WORD)(ReadVal>>ReadBitCtr);
    ReadVal &= ((1<<ReadBitCtr)-1);
    return ReadCode;
  }

  bool EndInput()  {return (ReadBitCtr<BitsInCounter)&&EndData();}

/*
Returned parameters: Returns a node in the tree of the EncDict.
Action: Looks for 'Symbol' from 'it'.
This research is made from the left pointer of 'it'
(if the left pointer wasn't equal to 0) and then move to all the right
pointers until we reach the node containing 'Symbol' or the last node which
right pointer is 0.
Errors: If the Symbol has not been found out, (it=returned node) or ((returned node)->Character#Symbol).
The 'it' given to this routine must never be equal to 0.
*/
  DictValNodePtr FindNode(DictValNodePtr it, WORD Symbol) {
    DictValNodePtr NewNode;
    if(it->Left==0) return it;
    NewNode=it->Left;
    while((NewNode->Character!=Symbol)&&(NewNode->Right)) NewNode=NewNode->Right;
    return NewNode;
  }

/*
Returned parameters: None.
Action: Creates a NewNode in the tree of EncDict.
The summoning of this routine is normally done after a call to to FindNode.
Errors: None.
*/
  const char* AddNode(DictValNodePtr it, DictValNodePtr NewNode, WORD Symbol) {
    DictValNodePtr pDictValNode=EncDict[DictIdx];
    if(!pDictValNode) {
      if(!(pDictValNode=EncDict[DictIdx]=(DictValNodePtr)malloc(sizeof(DictValNode)))) {
        FreeDict();
        return sBadMAlloc;
      }
      pDictValNode->Code=DictIdx;
      pDictValNode->Left=0;
      pDictValNode->Right=0;
    }
    pDictValNode->Character=Symbol;
    if(it==NewNode) NewNode->Left=pDictValNode;
    else NewNode->Right=pDictValNode;
    if(++DictIdx==(WORD)(1<<EncBitCtr)) ++EncBitCtr;
    return 0;
  }

/*
Returned parameters: None.
Action: Sends the Value coded on 'EncBitCtr' bits in the stream of output codes.
The bits are stored from right to left. Example: aaabbbbcccc is written:
Bits     7 6 5 4 3 2 1 0
Byte 1   a a a b b b b c
Byte 2   c c c ? ? ? ? ?
Errors: An input/output error could disturb the running of the program.
*/
  void WriteCodeLR(WORD Value) {
    WriteVal=(WriteVal << EncBitCtr) | Value;
    WriteBitCtr+=EncBitCtr;
    while(WriteBitCtr>=8) {
      WriteBitCtr-=8;
      WriteByte((BYTE)(WriteVal >> WriteBitCtr));
      WriteVal &= ((1<<WriteBitCtr)-1);
  } }

/*
Returned parameters: None.
Action: Adds 0-bits to the last byte to write, if any.
This procedure is to be considered with the procedure WriteCodeLR.
Errors: An input/output error could disturb the running of the program.
*/
  void EncEndLR() {
    if(WriteBitCtr>0) WriteByte((BYTE)(WriteVal << (8-WriteBitCtr)));
    WriteVal=WriteBitCtr=0;
  }

/*
Returned parameters: None.
Action: Sends the Value coded on 'EncBitCtr' bits in the stream of output codes.
The bits are stored from right to left. Example: aaabbbbcccc is written:
Bits     7 6 5 4 3 2 1 0
Byte 1   c b b b b a a a
Byte 2   ? ? ? ? ? c c c
Errors: An input/output error could disturb the running of the program.
*/
  void WriteCodeRL(WORD Value) {
    WriteVal |= ((DWORD)Value) << WriteBitCtr;
    WriteBitCtr+=EncBitCtr;
    while(WriteBitCtr>=8) {
      WriteBitCtr-=8;
      WriteByte((BYTE)(WriteVal&0xFF));
      WriteVal=(WriteVal>>8) & ((1<<WriteBitCtr)-1);
  } }

/*
Returned parameters: None.
Action: Adds 0-bits to the last byte to write, if any.
This procedure is to be considered with the procedure WriteCodeRL.
Errors: An input/output error could disturb the running of the program.
*/
  void EncEndRL() {
    if(WriteBitCtr>0) WriteByte((BYTE)WriteVal);
    WriteVal=WriteBitCtr=0;
  }
};

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> CLZWStreamDecoder <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

class CLZWStreamDecoder : public CLZWStream {
public:
  CLZWStreamDecoder() : AutoReInitDict(false) {}
  CLZWStreamDecoder(CString& S) {
    if(S.IsEmpty()) return;
    CString D;
    const char* Err=Decode(&*S, D.GetBufferSetLength(2*S.GetLength()), S.GetLength());
    D.ReleaseBuffer();
    S=Err ? "" : D; // On Error return an empty string
  }
  CLZWStreamDecoder       (const char* In, char* Out, DWORD Bytes) {Decode(In, Out, Bytes);}
  const char* Decode(const char* In, char* Out, DWORD Bytes) {
    InBuf=In;
    InEnd=InBuf+Bytes;
    OutBuf=Out;
    if(ReadByte()==0xFF) return Decode(); //Compressed data token.
    memcpy(Out,In,Bytes);
    return 0;
  }
  CLZWStreamDecoder       (const char* InPath, const char* OutPath) {Decode(InPath, OutPath);}
  const char* Decode(const char* InPath, const char* OutPath) {
    const char* Return=0;
    if((InFile=fopen(InPath, "rb"))) {
      if((OutFile=fopen(OutPath, "wb"))) {
        if(ReadByte()==0xFF) Return=Decode(); //Compressed data token.
        else CopyFile(); //Its not compressed so just copy the file.
        OutSize=ftell(OutFile);
        fclose(OutFile);
      }else Return=sBadFileName;
      fclose(InFile);
    }else Return=sBadFileName;
    return Return;
  }

private:
/*
If AutoReInitDict=true, the dictionary is always increased (even if this makes an overflow error!).
If AutoReInitDict=false, the dictionary is not updated when it reaches its maximal capacity.
The reception of the Code 'InitCode' will force the dictionary to by flushed.
AutoReInitDict is only considered when using GIFEncoding
*/
  bool AutoReInitDict;

  typedef struct DictLinkStruct {
    WORD Character;
    DictLinkStruct* predecessor;
  } DictLinkNode, *pDictLinkNode;

  void FreeDict() {for(register WORD i=0;(i<MaxDictIdx)&&(DecDict[i]);i++) free(DecDict[i]);}
  BYTE DecBitCtr;

/*
Bit counter for each data in output.
With BitsOutCtr=1, we can compress/decompress monochrome pictures
and with BitsOutCtr=8, we can handle 256-colors pictures or any kind of files.
*/
  BYTE BitsOutCtr;
  BYTE DecMinBitCtr; // Bit counter to encode 'InitCode'.

  pDictLinkNode DecDict[1<<WordCounterBits];

/*
Returned parameters: None.
Action: Compresses with LZWStream method all bytes read by the function 'read_code_??'.
(where '??' is 'lr' or 'rl', depending on how you stored the bits in the compressed stream.
Errors: An input/output error could disturb the running of the program.
*/
  const char* Decode() {
    if(!EndData()) {
      register WORD i;
      MaxDictIdx=1<<12; // Attention: Possible values: 2^3 to 2^WordCounterBits
      BitsOutCtr=8;     /* Attention: Possible values: 1 to WordCounterBits-1
              (usually, for pictures, set up to 1, or 4, or 8, in the case
                   of monochrome, or 16-colors, or 256-colors picture). */
      if(BitsOutCtr==1) DecMinBitCtr=3;
      else DecMinBitCtr=BitsOutCtr+1;
      InitCode=1<<(DecMinBitCtr-1);
      EndCode=InitCode+(GIFEncoding ? 1 : -1);
      for(i=0; i<MaxDictIdx; ++i) {
        if(!(DecDict[i]=(pDictLinkNode)malloc(sizeof(DictLinkNode)))) {
          while(i) free(DecDict[--i]);
          return sBadMAlloc;
        }
        if(i<InitCode) DecDict[i]->Character=i;
        DecDict[i]->predecessor=0;
      }
      DictIdx=EndCode+1;
      DecBitCtr=DecMinBitCtr;
      WORD PrevCode=0;
      WORD FirstChar=0;
      WORD CurCode=ReadCodeLR();
      if(GIFEncoding) {
        if(CurCode!=InitCode) {
          FreeDict();
          return sBadDataCode;
        }
        if((CurCode=ReadCodeLR())<InitCode) {
          FirstChar=WriteString(PrevCode,CurCode,FirstChar);
          PrevCode=CurCode;
          CurCode=ReadCodeLR();
        }
        while(CurCode!=EndCode) {
          if(CurCode==InitCode) {
            for(register WORD i=InitCode; (i<MaxDictIdx)&&(DecDict[i]); ++i) DecDict[i]->predecessor=0;
            DictIdx=EndCode+1;
            DecBitCtr=DecMinBitCtr;
            CurCode=ReadCodeLR();
            if(CurCode<InitCode) {
              FirstChar=WriteString(PrevCode,CurCode,FirstChar);
              PrevCode=CurCode;
              CurCode=ReadCodeLR();
            }
          }else{
            if(CurCode>DictIdx) return sBadDataCode;
            if(AutoReInitDict) {
              if(DictIdx==MaxDictIdx) return sDictOverflow;
              FirstChar=WriteString(PrevCode,CurCode,FirstChar);
              AddString(PrevCode,FirstChar);
              PrevCode=CurCode;
              CurCode=ReadCodeLR();
            }else{
              FirstChar=WriteString(PrevCode,CurCode,FirstChar);
              if(DictIdx<MaxDictIdx) AddString(PrevCode,FirstChar);
              PrevCode=CurCode;
              CurCode=ReadCodeLR();
        } } }
        FreeDict();
      }else{
        PrevCode=CurCode;
        FirstChar=WriteString(PrevCode,CurCode,FirstChar);
        while((!EndData())||(ReadBitCtr>=DecBitCtr)) {
          CurCode=ReadCodeLR();
          if(CurCode>DictIdx) return sBadDataCode;
          FirstChar=WriteString(PrevCode,CurCode,FirstChar);
          if(DictIdx==MaxDictIdx-2) {
            for(register WORD i=InitCode; (i<MaxDictIdx)&&(DecDict[i]); ++i) DecDict[i]->predecessor=0;
            DictIdx=EndCode+1;
            DecBitCtr=DecMinBitCtr;
            if((!EndData())||(ReadBitCtr>=DecBitCtr)) {
              PrevCode=(CurCode=ReadCodeLR());
              FirstChar=WriteString(PrevCode,CurCode,FirstChar);
          } } else AddString(PrevCode,FirstChar);
          PrevCode=CurCode;
        }
        FreeDict();
      }
      EndOutput();
    }
    return 0;
  }

/*
Returned parameters: None.
Action: Writes 'BitsOutCtr' via the function WriteByte.
Errors: An input/output error could disturb the running of the program.
*/
  void WriteOutput(WORD Value) {
    WriteVal=(WriteVal << BitsOutCtr) | Value;
    WriteBitCtr+=BitsOutCtr;
    while(WriteBitCtr>=8) {
      WriteBitCtr-=8;
      WriteByte((BYTE)(WriteVal >> WriteBitCtr));
      WriteVal &= (1<<WriteBitCtr)-1;
  } }

/*
Returned parameters: None.
Action: Fills the last byte to write with 0-bits, if necessary.
This procedure is to be considered aith the procedure 'WriteOutput'.
Errors: An input/output error could disturb the running of the program.
*/
  void EndOutput() {
    if(WriteBitCtr>0) WriteByte((BYTE)(WriteVal << (8-WriteBitCtr)));
    WriteVal=WriteBitCtr=0;
  }

/*
Returned parameters: 'Character' can have been modified.
Action: Sends the string in the output stream given by the 'link' of the LZWStream DecDict.
'Character' contains to the end of the routine the first Character of the string.
Errors: None (except a possible overflow of the operational stack allocated
by the program, which must allows at least 8*MaxDictIdx bytes, corresponding
to an exceptional case.
*/
  void WriteLink(pDictLinkNode Link, WORD* Character) {
    if(Link->predecessor) {
      WriteLink(Link->predecessor,Character);
      WriteOutput(Link->Character);
    }else{
      WriteOutput(Link->Character);
       *Character=Link->Character;
  } }

/*
Returned parameters: Returns a byte.
Action: Writes the string of bytes associated to 'it' and returns
the first Character of this string.
Errors: None.
*/
  WORD WriteString(WORD PrevCode, WORD CurCode, WORD FirstChar) {
    WORD Character;
    if(CurCode<DictIdx) WriteLink(DecDict[CurCode], &Character);
    else {
      WriteLink(DecDict[PrevCode],&Character);
      WriteOutput(FirstChar);
    }
    return Character;
  }

/*
Returned parameters: None.
Action: Adds the string given by 'Code' to the DecDict.
Errors: None.
*/
  void AddString(WORD Code, WORD FirstChar) {
    DecDict[DictIdx]->Character=FirstChar;
    DecDict[DictIdx]->predecessor=DecDict[Code];
    if(++DictIdx+1==(WORD)(1<<DecBitCtr)) ++DecBitCtr;
  }

/*
Returned parameters: Returns the Value of Code.
Action: Returns the Value coded on 'DecBitCtr' bits from the stream of input codes.
The bits are stored from left to right. Example: aaabbbbcccc is written:
Bits     7 6 5 4 3 2 1 0
Byte 1   a a a b b b b c
Byte 2   c c c ? ? ? ? ?
Errors: An input/output error could disturb the running of the program.
*/
  WORD ReadCodeLR() {
    while(ReadBitCtr<DecBitCtr) {
      ReadVal=(ReadVal<<8)|ReadByte();
      ReadBitCtr+=8;
    }
    ReadBitCtr-=DecBitCtr;
    WORD ReadCode=(WORD)(ReadVal>>ReadBitCtr);
    ReadVal &= ((1<<ReadBitCtr)-1);
    return ReadCode;
  }

/*
Returned parameters: Returns the Value of Code.
Action: Returns the Value coded on 'DecBitCtr' bits from the stream of input codes.
The bits are stored from right to left. Example: aaabbbbcccc is written:
Bits     7 6 5 4 3 2 1 0
Byte 1   c b b b b a a a
Byte 2   ? ? ? ? ? c c c
Errors: An input/output error could disturb the running of the program.
*/
  WORD WriteCodeRL() {
    while(ReadBitCtr<DecBitCtr) {
      ReadVal |= ((DWORD)ReadByte())<<ReadBitCtr;
      ReadBitCtr+=8;
    }
    ReadBitCtr-=DecBitCtr;
    WORD ReadCode=(WORD)(ReadVal & ((1<<DecBitCtr)-1));
    ReadVal >>= DecBitCtr;
    return ReadCode;
  }
};

#endif //ndef LZWStreamh