(********************************************************************)
(*                                                                  *)
(*  lzw.s7i       Lempel-Ziv-Welch compression support library      *)
(*  Copyright (C) 2015, 2021, 2022  Thomas Mertes                   *)
(*                                                                  *)
(*  This file is part of the Seed7 Runtime Library.                 *)
(*                                                                  *)
(*  The Seed7 Runtime Library is free software; you can             *)
(*  redistribute it and/or modify it under the terms of the GNU     *)
(*  Lesser General Public License as published by the Free Software *)
(*  Foundation; either version 2.1 of the License, or (at your      *)
(*  option) any later version.                                      *)
(*                                                                  *)
(*  The Seed7 Runtime 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 Lesser General Public License for more    *)
(*  details.                                                        *)
(*                                                                  *)
(*  You should have received a copy of the GNU Lesser General       *)
(*  Public License along with this program; if not, write to the    *)
(*  Free Software Foundation, Inc., 51 Franklin Street,             *)
(*  Fifth Floor, Boston, MA  02110-1301, USA.                       *)
(*                                                                  *)
(********************************************************************)


include "bitdata.s7i";


(**
 *  Compress a string with the Lempel-Ziv-Welch (LZW) compression method.
 *  The packing order of bits in bytes is LSB-First (Least Significant
 *  Bit First). This compression method is used for [[gif|GIF]] files. Compressing
 *  starts with succ(''codeSize'') bits per coding point and goes up to
 *  12 bits per coding point. The code points 0 to pred(2 ** ''codeSize'')
 *  correspond to unchanged data. Code 2 ** ''codeSize'' starts a new
 *  block with a new table and succ(''codeSize'') bits per code point.
 *  Code succ(2 ** ''codeSize'') marks the end of the compressed data.
 *  @param uncompressed Data to be compressed
 *  @param codeSize Number of bits used by the uncompressed data.
 *  @return Compressed byte string of the ''uncompressed'' data.
 *)
const func string: lzwCompressLsb (in string: uncompressed, in integer: codeSize) is func
  result
    var string: compressed is "";
  local
    var lsbOutBitStream: compressedStream is lsbOutBitStream.value;
    var integer: clearCode is 0;
    var integer: endOfInformationCode is 0;
    var integer: code is 0;
    var char: ch is ' ';
    var hash [string] integer: mydict is (hash [string] integer).value;
    var string: buffer is "";
    var string: xstr is "";
    var integer: bitsToWrite is 0;
    var integer: moreBitsNeeded is 0;
  begin
    bitsToWrite := succ(codeSize);
    clearCode := 1 << codeSize;
    endOfInformationCode := succ(clearCode);
    for code range 0 to pred(clearCode) do
      mydict @:= [str(char(code))] code;
    end for;
    putBits(compressedStream, clearCode, bitsToWrite);
    bitsToWrite := succ(codeSize);
    moreBitsNeeded := 1 << bitsToWrite;
    for ch range uncompressed do
      xstr := buffer & str(ch);
      if xstr in mydict then
        buffer &:= str(ch)
      else
        putBits(compressedStream, mydict[buffer], bitsToWrite);
        code := length(mydict) + 2;
        mydict @:= [xstr] code;
        if code = moreBitsNeeded then
          if bitsToWrite = 12 then
            mydict := (hash [string] integer).value;
            for code range 0 to pred(clearCode) do
              mydict @:= [str(char(code))] code;
            end for;
            putBits(compressedStream, clearCode, bitsToWrite);
            bitsToWrite := succ(codeSize);
          else
            incr(bitsToWrite);
          end if;
          moreBitsNeeded := 1 << bitsToWrite;
        end if;
        buffer := str(ch);
      end if;
    end for;
    if buffer <> "" then
      putBits(compressedStream, mydict[buffer], bitsToWrite);
      if length(mydict) + 2 = moreBitsNeeded then
        if bitsToWrite = 12 then
          putBits(compressedStream, clearCode, bitsToWrite);
          bitsToWrite := succ(codeSize);
        else
          incr(bitsToWrite);
        end if;
      end if;
    end if;
    putBits(compressedStream, endOfInformationCode, bitsToWrite);
    flush(compressedStream);
    compressed := getBytes(compressedStream);
  end func;


(**
 *  Decompress an Lempel-Ziv-Welch (LZW) compressed [[bitdata#lsbInBitStream|lsbInBitStream]].
 *  The packing order of bits in bytes is LSB-First (Least Significant
 *  Bit First). This compression method is used for [[gif|GIF]] files. Decompressing
 *  starts with succ(''codeSize'') bits per coding point and goes up to
 *  12 bits per coding point. The code points 0 to pred(2 ** ''codeSize'')
 *  correspond to unchanged data. Code 2 ** ''codeSize'' starts a new
 *  block with a new table and succ(''codeSize'') bits per code point.
 *  Code succ(2 ** ''codeSize'') marks the end of the compressed data.
 *  @param compressed Byte string to be decompressed.
 *  @param codeSize Number of bits used by the decompressed data.
 *  @return Decompressed version of the ''compressed'' data.
 *)
const func string: lzwDecompress (inout lsbInBitStream: compressedStream,
    in integer: codeSize) is func
  result
    var string: decompressed is "";
  local
    const integer: maxTableIndex is 4095;
    var integer: bitsToRead is 0;
    var integer: clearCode is 0;
    var integer: endOfInformationCode is 0;
    var integer: code is 0;
    var integer: previousCode is 0;
    var array string: table is [0 .. maxTableIndex] times "";
    var integer: nextTableIndex is 0;
    var integer: moreBitsNeeded is 0;
  begin
    bitsToRead := succ(codeSize);
    clearCode := 1 << codeSize;
    for code range 0 to pred(clearCode) do
      table[code] := str(char(code));
    end for;
    endOfInformationCode := succ(clearCode);
    nextTableIndex := succ(endOfInformationCode);
    moreBitsNeeded := 1 << bitsToRead;
    previousCode := clearCode;
    code := getBits(compressedStream, bitsToRead);
    while code <> endOfInformationCode do
      if code = clearCode then
        bitsToRead := succ(codeSize);
        nextTableIndex := succ(endOfInformationCode);
        moreBitsNeeded := 1 << bitsToRead;
      elsif previousCode = clearCode then
        if code < nextTableIndex then
          decompressed &:= table[code];
        else
          raise RANGE_ERROR;
        end if;
      else
        if code < nextTableIndex then
          if nextTableIndex <= maxTableIndex then
            table[nextTableIndex] := table[previousCode] & str(table[code][1]);
            incr(nextTableIndex);
          end if;
          decompressed &:= table[code];
        elsif code = nextTableIndex then
          if nextTableIndex <= maxTableIndex then
            table[nextTableIndex] := table[previousCode] & str(table[previousCode][1]);
            incr(nextTableIndex);
            decompressed &:= table[code];
          else
            decompressed &:= table[previousCode] & str(table[previousCode][1]);
          end if;
        else
          raise RANGE_ERROR;
        end if;
        if nextTableIndex = moreBitsNeeded then
          incr(bitsToRead);
          if bitsToRead < 12 then
            moreBitsNeeded := 1 << bitsToRead;
          end if;
        end if;
      end if;
      previousCode := code;
      code := getBits(compressedStream, bitsToRead);
    end while;
  end func;


(**
 *  Decompress an Lempel-Ziv-Welch (LZW) compressed string.
 *  The packing order of bits in bytes is LSB-First (Least Significant
 *  Bit First). This compression method is used for [[gif|GIF]] files. Decompressing
 *  starts with succ(''codeSize'') bits per coding point and goes up to
 *  12 bits per coding point. The code points 0 to pred(2 ** ''codeSize'')
 *  correspond to unchanged data. Code 2 ** ''codeSize'' starts a new
 *  block with a new table and succ(''codeSize'') bits per code point.
 *  Code succ(2 ** ''codeSize'') marks the end of the compressed data.
 *  @param compressed Byte string to be decompressed.
 *  @param codeSize Number of bits used by the decompressed data.
 *  @return Decompressed version of the ''compressed'' data.
 *)
const func string: lzwDecompressLsb (in string: compressed, in integer: codeSize) is func
  result
    var string: decompressed is "";
  local
    var lsbInBitStream: compressedStream is lsbInBitStream.value;
  begin
    compressedStream := openLsbInBitStream(compressed);
    decompressed := lzwDecompress(compressedStream, codeSize);
  end func;


(**
 *  Compress a string with the Lempel-Ziv-Welch (LZW) compression method.
 *  The packing order of bits in bytes is MSB-First (Most Significant
 *  Bit First). This compression method is used in PDF files.
 *  Compressing starts with succ(''codeSize'') bits per coding point and
 *  goes up to 12 bits per coding point. The code points 0 to
 *  pred(2 ** ''codeSize'') correspond to unchanged data. Code
 *  2 ** ''codeSize'' starts a new a new block with a new table and
 *  succ(''codeSize'') bits per code point. Code succ(2 ** ''codeSize'')
 *  marks the end of the compressed data.
 *  @param uncompressed Data to be compressed
 *  @param codeSize Number of bits used by the uncompressed data.
 *  @return Compressed byte string of the ''uncompressed'' data.
 *)
const func string: lzwCompressMsb (in string: uncompressed, in integer: codeSize) is func
  result
    var string: compressed is "";
  local
    var msbOutBitStream: compressedStream is msbOutBitStream.value;
    var integer: clearCode is 0;
    var integer: endOfInformationCode is 0;
    var integer: code is 0;
    var char: ch is ' ';
    var hash [string] integer: mydict is (hash [string] integer).value;
    var string: buffer is "";
    var string: xstr is "";
    var integer: bitsToWrite is 0;
    var integer: moreBitsNeeded is 0;
  begin
    bitsToWrite := succ(codeSize);
    clearCode := 1 << codeSize;
    endOfInformationCode := succ(clearCode);
    for code range 0 to pred(clearCode) do
      mydict @:= [str(char(code))] code;
    end for;
    putBits(compressedStream, clearCode, bitsToWrite);
    bitsToWrite := succ(codeSize);
    moreBitsNeeded := 1 << bitsToWrite;
    for ch range uncompressed do
      xstr := buffer & str(ch);
      if xstr in mydict then
        buffer &:= str(ch)
      else
        putBits(compressedStream, mydict[buffer], bitsToWrite);
        code := length(mydict) + 2;
        mydict @:= [xstr] code;
        if code = moreBitsNeeded then
          if bitsToWrite = 12 then
            mydict := (hash [string] integer).value;
            for code range 0 to pred(clearCode) do
              mydict @:= [str(char(code))] code;
            end for;
            putBits(compressedStream, clearCode, bitsToWrite);
            bitsToWrite := succ(codeSize);
          else
            incr(bitsToWrite);
          end if;
          moreBitsNeeded := 1 << bitsToWrite;
        end if;
        buffer := str(ch);
      end if;
    end for;
    if buffer <> "" then
      putBits(compressedStream, mydict[buffer], bitsToWrite);
      if length(mydict) + 2 = moreBitsNeeded then
        if bitsToWrite = 12 then
          putBits(compressedStream, clearCode, bitsToWrite);
          bitsToWrite := succ(codeSize);
        else
          incr(bitsToWrite);
        end if;
      end if;
    end if;
    putBits(compressedStream, endOfInformationCode, bitsToWrite);
    flush(compressedStream);
    compressed := getBytes(compressedStream);
  end func;


(**
 *  Decompress an Lempel-Ziv-Welch (LZW) compressed [[bitdata#msbInBitStream|msbInBitStream]].
 *  The packing order of bits in bytes is MSB-First (Most Significant
 *  Bit First). This compression  method is used in PDF files.
 *  Decompressing starts with succ(''codeSize'') bits per coding point and
 *  goes up to 12 bits per coding point. The code points 0 to
 *  pred(2 ** ''codeSize'') correspond to unchanged data. Code
 *  2 ** ''codeSize'' starts a new block with a new table and
 *  succ(''codeSize'') bits per code point. Code succ(2 ** ''codeSize'')
 *  marks the end of the compressed data.
 *  @param compressed Byte string to be decompressed.
 *  @param codeSize Number of bits used by the decompressed data.
 *  @return Decompressed version of the ''compressed'' data.
 *)
const func string: lzwDecompress (inout msbInBitStream: compressedStream,
    in integer: codeSize) is func
  result
    var string: decompressed is "";
  local
    const integer: maxTableIndex is 4095;
    var integer: bitsToRead is 0;
    var integer: clearCode is 0;
    var integer: endOfInformationCode is 0;
    var integer: code is 0;
    var integer: previousCode is 0;
    var array string: table is [0 .. maxTableIndex] times "";
    var integer: nextTableIndex is 0;
    var integer: moreBitsNeeded is 0;
  begin
    bitsToRead := succ(codeSize);
    clearCode := 1 << codeSize;
    for code range 0 to pred(clearCode) do
      table[code] := str(char(code));
    end for;
    endOfInformationCode := succ(clearCode);
    nextTableIndex := succ(endOfInformationCode);
    moreBitsNeeded := 1 << bitsToRead;
    previousCode := clearCode;
    code := getBits(compressedStream, bitsToRead);
    while code <> endOfInformationCode do
      if code = clearCode then
        bitsToRead := succ(codeSize);
        nextTableIndex := succ(endOfInformationCode);
        moreBitsNeeded := 1 << bitsToRead;
      elsif previousCode = clearCode then
        if code < nextTableIndex then
          decompressed &:= table[code];
        else
          raise RANGE_ERROR;
        end if;
      else
        if code < nextTableIndex then
          if nextTableIndex <= maxTableIndex then
            table[nextTableIndex] := table[previousCode] & str(table[code][1]);
            incr(nextTableIndex);
          end if;
          decompressed &:= table[code];
        elsif code = nextTableIndex then
          if nextTableIndex <= maxTableIndex then
            table[nextTableIndex] := table[previousCode] & str(table[previousCode][1]);
            incr(nextTableIndex);
            decompressed &:= table[code];
          else
            decompressed &:= table[previousCode] & str(table[previousCode][1]);
          end if;
        else
          raise RANGE_ERROR;
        end if;
        if nextTableIndex = moreBitsNeeded then
          incr(bitsToRead);
          if bitsToRead < 12 then
            moreBitsNeeded := 1 << bitsToRead;
          end if;
        end if;
      end if;
      previousCode := code;
      code := getBits(compressedStream, bitsToRead);
    end while;
  end func;


(**
 *  Decompress an Lempel-Ziv-Welch (LZW) compressed string.
 *  The packing order of bits in bytes is MSB-First (Most Significant
 *  Bit First). This compression  method is used in PDF files.
 *  Decompressing starts with succ(''codeSize'') bits per coding point and
 *  goes up to 12 bits per coding point. The code points 0 to
 *  pred(2 ** ''codeSize'') correspond to unchanged data. Code
 *  2 ** ''codeSize'' starts a new block with a new table and
 *  succ(''codeSize'') bits per code point. Code succ(2 ** ''codeSize'')
 *  marks the end of the compressed data.
 *  @param compressed Byte string to be decompressed.
 *  @param codeSize Number of bits used by the decompressed data.
 *  @return Decompressed version of the ''compressed'' data.
 *)
const func string: lzwDecompressMsb (in string: compressed, in integer: codeSize) is func
  result
    var string: decompressed is "";
  local
    var msbInBitStream: compressedStream is msbInBitStream.value;
  begin
    compressedStream := openMsbInBitStream(compressed);
    decompressed := lzwDecompress(compressedStream, codeSize);
  end func;


(**
 *  Compress a string with the Lempel-Ziv-Welch (LZW) compression method.
 *  The packing order of bits in bytes is MSB-First (Most Significant
 *  Bit First). This compression method is used in [[tiff|TIFF]] and PDF files.
 *  EarlyChange means that the encoding width changes one code too early.
 *  Compressing starts with succ(''codeSize'') bits per coding point and
 *  goes up to 12 bits per coding point. The code points 0 to
 *  pred(2 ** ''codeSize'') correspond to unchanged data. Code
 *  2 ** ''codeSize'' starts a new a new block with a new table and
 *  succ(''codeSize'') bits per code point. Code succ(2 ** ''codeSize'')
 *  marks the end of the compressed data.
 *  @param uncompressed Data to be compressed
 *  @param codeSize Number of bits used by the uncompressed data.
 *  @return Compressed byte string of the ''uncompressed'' data.
 *)
const func string: lzwCompressMsbEarlyChange (in string: uncompressed, in integer: codeSize) is func
  result
    var string: compressed is "";
  local
    var msbOutBitStream: compressedStream is msbOutBitStream.value;
    var integer: clearCode is 0;
    var integer: endOfInformationCode is 0;
    var integer: code is 0;
    var char: ch is ' ';
    var hash [string] integer: mydict is (hash [string] integer).value;
    var string: buffer is "";
    var string: xstr is "";
    var integer: bitsToWrite is 0;
    var integer: moreBitsNeeded is 0;
  begin
    bitsToWrite := succ(codeSize);
    clearCode := 1 << codeSize;
    endOfInformationCode := succ(clearCode);
    for code range 0 to pred(clearCode) do
      mydict @:= [str(char(code))] code;
    end for;
    putBits(compressedStream, clearCode, bitsToWrite);
    bitsToWrite := succ(codeSize);
    moreBitsNeeded := pred(1 << bitsToWrite);
    for ch range uncompressed do
      xstr := buffer & str(ch);
      if xstr in mydict then
        buffer &:= str(ch)
      else
        putBits(compressedStream, mydict[buffer], bitsToWrite);
        code := length(mydict) + 2;
        mydict @:= [xstr] code;
        if code = moreBitsNeeded then
          if bitsToWrite = 12 then
            mydict := (hash [string] integer).value;
            for code range 0 to pred(clearCode) do
              mydict @:= [str(char(code))] code;
            end for;
            putBits(compressedStream, clearCode, bitsToWrite);
            bitsToWrite := succ(codeSize);
          else
            incr(bitsToWrite);
          end if;
          moreBitsNeeded := pred(1 << bitsToWrite);
        end if;
        buffer := str(ch);
      end if;
    end for;
    if buffer <> "" then
      putBits(compressedStream, mydict[buffer], bitsToWrite);
      if length(mydict) + 2 = moreBitsNeeded then
        if bitsToWrite = 12 then
          putBits(compressedStream, clearCode, bitsToWrite);
          bitsToWrite := succ(codeSize);
        else
          incr(bitsToWrite);
        end if;
      end if;
    end if;
    putBits(compressedStream, endOfInformationCode, bitsToWrite);
    flush(compressedStream);
    compressed := getBytes(compressedStream);
  end func;


(**
 *  Decompress an Lempel-Ziv-Welch (LZW) compressed [[bitdata#msbInBitStream|msbInBitStream]].
 *  The packing order of bits in bytes is MSB-First (Most Significant
 *  Bit First). This compression  method is used in [[tiff|TIFF]] and PDF files.
 *  EarlyChange means that the encoding width changes one code too early.
 *  Decompressing starts with succ(''codeSize'') bits per coding point and
 *  goes up to 12 bits per coding point. The code points 0 to
 *  pred(2 ** ''codeSize'') correspond to unchanged data. Code
 *  2 ** ''codeSize'' starts a new block with a new table and
 *  succ(''codeSize'') bits per code point. Code succ(2 ** ''codeSize'')
 *  marks the end of the compressed data.
 *  @param compressed Byte string to be decompressed.
 *  @param codeSize Number of bits used by the decompressed data.
 *  @return Decompressed version of the ''compressed'' data.
 *)
const func string: lzwDecompressEarlyChange (inout msbInBitStream: compressedStream,
    in integer: codeSize) is func
  result
    var string: decompressed is "";
  local
    const integer: maxTableIndex is 4095;
    var integer: bitsToRead is 0;
    var integer: clearCode is 0;
    var integer: endOfInformationCode is 0;
    var integer: code is 0;
    var integer: previousCode is 0;
    var array string: table is [0 .. maxTableIndex] times "";
    var integer: nextTableIndex is 0;
    var integer: moreBitsNeeded is 0;
  begin
    bitsToRead := succ(codeSize);
    clearCode := 1 << codeSize;
    for code range 0 to pred(clearCode) do
      table[code] := str(char(code));
    end for;
    endOfInformationCode := succ(clearCode);
    nextTableIndex := succ(endOfInformationCode);
    moreBitsNeeded := pred(1 << bitsToRead);
    previousCode := clearCode;
    code := getBits(compressedStream, bitsToRead);
    while code <> endOfInformationCode do
      if code = clearCode then
        bitsToRead := succ(codeSize);
        nextTableIndex := succ(endOfInformationCode);
        moreBitsNeeded := pred(1 << bitsToRead);
      elsif previousCode = clearCode then
        if code < nextTableIndex then
          decompressed &:= table[code];
        else
          raise RANGE_ERROR;
        end if;
      else
        if code < nextTableIndex then
          if nextTableIndex <= maxTableIndex then
            table[nextTableIndex] := table[previousCode] & str(table[code][1]);
            incr(nextTableIndex);
          end if;
          decompressed &:= table[code];
        elsif code = nextTableIndex then
          if nextTableIndex <= maxTableIndex then
            table[nextTableIndex] := table[previousCode] & str(table[previousCode][1]);
            incr(nextTableIndex);
            decompressed &:= table[code];
          else
            decompressed &:= table[previousCode] & str(table[previousCode][1]);
          end if;
        else
          raise RANGE_ERROR;
        end if;
        if nextTableIndex = moreBitsNeeded then
          incr(bitsToRead);
          if bitsToRead < 12 then
            moreBitsNeeded := pred(1 << bitsToRead);
          end if;
        end if;
      end if;
      previousCode := code;
      code := getBits(compressedStream, bitsToRead);
    end while;
  end func;


(**
 *  Decompress an Lempel-Ziv-Welch (LZW) compressed string.
 *  The packing order of bits in bytes is MSB-First (Most Significant
 *  Bit First). This compression  method is used in [[tiff|TIFF]] and PDF files.
 *  EarlyChange means that the encoding width changes one code too early.
 *  Decompressing starts with succ(''codeSize'') bits per coding point and
 *  goes up to 12 bits per coding point. The code points 0 to
 *  pred(2 ** ''codeSize'') correspond to unchanged data. Code
 *  2 ** ''codeSize'' starts a new block with a new table and
 *  succ(''codeSize'') bits per code point. Code succ(2 ** ''codeSize'')
 *  marks the end of the compressed data.
 *  @param compressed Byte string to be decompressed.
 *  @param codeSize Number of bits used by the decompressed data.
 *  @return Decompressed version of the ''compressed'' data.
 *)
const func string: lzwDecompressMsbEarlyChange (in string: compressed, in integer: codeSize) is func
  result
    var string: decompressed is "";
  local
    var msbInBitStream: compressedStream is msbInBitStream.value;
  begin
    compressedStream := openMsbInBitStream(compressed);
    decompressed := lzwDecompressEarlyChange(compressedStream, codeSize);
  end func;


(**
 *  Decompress an Lempel-Ziv-Welch (LZW) compressed [[bitdata#msbInBitStream|msbInBitStream]].
 *  The packing order of bits in bytes is MSB-First (Most Significant
 *  Bit First). This compression  method is used in [[tiff|TIFF]] and PDF files.
 *  EarlyChange means that the encoding width changes one code too early.
 *  Decompressing starts with succ(''codeSize'') bits per coding point and
 *  goes up to 12 bits per coding point. The code points 0 to
 *  pred(2 ** ''codeSize'') correspond to unchanged data. Code
 *  2 ** ''codeSize'' starts a new block with a new table and
 *  succ(''codeSize'') bits per code point. Code succ(2 ** ''codeSize'')
 *  marks the end of the compressed data.
 *  @param compressed Byte string to be decompressed.
 *  @param codeSize Number of bits used by the decompressed data.
 *  @param requestedLength Number of decompressed bytes to be read.
 *  @return Decompressed version of the ''compressed'' data.
 *)
const func string: lzwDecompressEarlyChange (inout msbInBitStream: compressedStream,
    in integer: codeSize, in integer: requestedLength) is func
  result
    var string: decompressed is "";
  local
    const integer: maxTableIndex is 4095;
    var integer: bitsToRead is 0;
    var integer: clearCode is 0;
    var integer: endOfInformationCode is 0;
    var integer: code is 0;
    var integer: previousCode is 0;
    var array string: table is [0 .. maxTableIndex] times "";
    var integer: nextTableIndex is 0;
    var integer: moreBitsNeeded is 0;
  begin
    bitsToRead := succ(codeSize);
    clearCode := 1 << codeSize;
    for code range 0 to pred(clearCode) do
      table[code] := str(char(code));
    end for;
    endOfInformationCode := succ(clearCode);
    nextTableIndex := succ(endOfInformationCode);
    moreBitsNeeded := pred(1 << bitsToRead);
    previousCode := clearCode;
    code := getBits(compressedStream, bitsToRead);
    while code <> endOfInformationCode and length(decompressed) < requestedLength do
      if code = clearCode then
        bitsToRead := succ(codeSize);
        nextTableIndex := succ(endOfInformationCode);
        moreBitsNeeded := pred(1 << bitsToRead);
      elsif previousCode = clearCode then
        if code < nextTableIndex then
          decompressed &:= table[code];
        else
          raise RANGE_ERROR;
        end if;
      else
        if code < nextTableIndex then
          if nextTableIndex <= maxTableIndex then
            table[nextTableIndex] := table[previousCode] & str(table[code][1]);
            incr(nextTableIndex);
          end if;
          decompressed &:= table[code];
        elsif code = nextTableIndex then
          if nextTableIndex <= maxTableIndex then
            table[nextTableIndex] := table[previousCode] & str(table[previousCode][1]);
            incr(nextTableIndex);
            decompressed &:= table[code];
          else
            decompressed &:= table[previousCode] & str(table[previousCode][1]);
          end if;
        else
          raise RANGE_ERROR;
        end if;
        if nextTableIndex = moreBitsNeeded then
          incr(bitsToRead);
          if bitsToRead < 12 then
            moreBitsNeeded := pred(1 << bitsToRead);
          end if;
        end if;
      end if;
      previousCode := code;
      code := getBits(compressedStream, bitsToRead);
    end while;
  end func;


(**
 *  Decompress an Lempel-Ziv-Welch (LZW) compressed string.
 *  The packing order of bits in bytes is MSB-First (Most Significant
 *  Bit First). This compression  method is used in [[tiff|TIFF]] and PDF files.
 *  EarlyChange means that the encoding width changes one code too early.
 *  Decompressing starts with succ(''codeSize'') bits per coding point and
 *  goes up to 12 bits per coding point. The code points 0 to
 *  pred(2 ** ''codeSize'') correspond to unchanged data. Code
 *  2 ** ''codeSize'' starts a new block with a new table and
 *  succ(''codeSize'') bits per code point. Code succ(2 ** ''codeSize'')
 *  marks the end of the compressed data.
 *  @param compressed Byte string to be decompressed.
 *  @param codeSize Number of bits used by the decompressed data.
 *  @param requestedLength Number of decompressed bytes to be read.
 *  @return Decompressed version of the ''compressed'' data.
 *)
const func string: lzwDecompressMsbEarlyChange (in string: compressed, in integer: codeSize,
    in integer: requestedLength) is func
  result
    var string: decompressed is "";
  local
    var msbInBitStream: compressedStream is msbInBitStream.value;
  begin
    compressedStream := openMsbInBitStream(compressed);
    decompressed := lzwDecompressEarlyChange(compressedStream, codeSize, requestedLength);
  end func;