(********************************************************************)
(*                                                                  *)
(*  bitdata.s7i   Read and write bits to and from strings           *)
(*  Copyright (C) 2015, 2017, 2019 - 2024  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 "bytedata.s7i";


(**
 *  Array to reverse the bits of small numbers.
 *  The first index is the number of bits to be reversed (between 2 and 9).
 *  The second index is the number for which the bits should be reversed.
 *   reverseBits[2][2#10]      returns  2#1
 *   reverseBits[4][2#1101]    returns  2#1011
 *   reverseBits[6][2#110101]  returns  2#101011
 *)
const array array integer: reverseBits is [2] (
    (* 2 *) [0] (0, 2, 1, 3),
    (* 3 *) [0] (0, 4, 2, 6, 1, 5, 3, 7),
    (* 4 *) [0] (0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15),
    (* 5 *) [0] (0, 16, 8, 24, 4, 20, 12, 28, 2, 18, 10, 26, 6, 22, 14, 30,
                 1, 17, 9, 25, 5, 21, 13, 29, 3, 19, 11, 27, 7, 23, 15, 31),
    (* 6 *) [0] (0, 32, 16, 48,  8, 40, 24, 56, 4, 36, 20, 52, 12, 44, 28, 60,
                 2, 34, 18, 50, 10, 42, 26, 58, 6, 38, 22, 54, 14, 46, 30, 62,
                 1, 33, 17, 49,  9, 41, 25, 57, 5, 37, 21, 53, 13, 45, 29, 61,
                 3, 35, 19, 51, 11, 43, 27, 59, 7, 39, 23, 55, 15, 47, 31, 63),
    (* 7 *) [0] (0, 64, 32,  96, 16, 80, 48, 112,  8, 72, 40, 104, 24, 88, 56, 120,
                 4, 68, 36, 100, 20, 84, 52, 116, 12, 76, 44, 108, 28, 92, 60, 124,
                 2, 66, 34,  98, 18, 82, 50, 114, 10, 74, 42, 106, 26, 90, 58, 122,
                 6, 70, 38, 102, 22, 86, 54, 118, 14, 78, 46, 110, 30, 94, 62, 126,
                 1, 65, 33,  97, 17, 81, 49, 113 , 9, 73, 41, 105, 25, 89, 57, 121,
                 5, 69, 37, 101, 21, 85, 53, 117, 13, 77, 45, 109, 29, 93, 61, 125,
                 3, 67, 35,  99, 19, 83, 51, 115, 11, 75, 43, 107, 27, 91, 59, 123,
                 7, 71, 39, 103, 23, 87, 55, 119, 15, 79, 47, 111, 31, 95, 63, 127),
    (* 8 *) [0] ( 0, 128, 64, 192, 32, 160,  96, 224, 16, 144, 80, 208, 48, 176, 112, 240,
                  8, 136, 72, 200, 40, 168, 104, 232, 24, 152, 88, 216, 56, 184, 120, 248,
                  4, 132, 68, 196, 36, 164, 100, 228, 20, 148, 84, 212, 52, 180, 116, 244,
                 12, 140, 76, 204, 44, 172, 108, 236, 28, 156, 92, 220, 60, 188, 124, 252,
                  2, 130, 66, 194, 34, 162,  98, 226, 18, 146, 82, 210, 50, 178, 114, 242,
                 10, 138, 74, 202, 42, 170, 106, 234, 26, 154, 90, 218, 58, 186, 122, 250,
                  6, 134, 70, 198, 38, 166, 102, 230, 22, 150, 86, 214, 54, 182, 118, 246,
                 14, 142, 78, 206, 46, 174, 110, 238, 30, 158, 94, 222, 62, 190, 126, 254,
                  1, 129, 65, 193, 33, 161,  97, 225, 17, 145, 81, 209, 49, 177, 113, 241,
                  9, 137, 73, 201, 41, 169, 105, 233, 25, 153, 89, 217, 57, 185, 121, 249,
                  5, 133, 69, 197, 37, 165, 101, 229, 21, 149, 85, 213, 53, 181, 117, 245,
                 13, 141, 77, 205, 45, 173, 109, 237, 29, 157, 93, 221, 61, 189, 125, 253,
                  3, 131, 67, 195, 35, 163,  99, 227, 19, 147, 83, 211, 51, 179, 115, 243,
                 11, 139, 75, 203, 43, 171, 107, 235, 27, 155, 91, 219, 59, 187, 123, 251,
                  7, 135, 71, 199, 39, 167, 103, 231, 23, 151, 87, 215, 55, 183, 119, 247,
                 15, 143, 79, 207, 47, 175, 111, 239, 31, 159, 95, 223, 63, 191, 127, 255),
    (* 9 *) [0] ( 0, 256, 128, 384, 64, 320, 192, 448, 32, 288, 160, 416,  96, 352, 224, 480,
                 16, 272, 144, 400, 80, 336, 208, 464, 48, 304, 176, 432, 112, 368, 240, 496,
                  8, 264, 136, 392, 72, 328, 200, 456, 40, 296, 168, 424, 104, 360, 232, 488,
                 24, 280, 152, 408, 88, 344, 216, 472, 56, 312, 184, 440, 120, 376, 248, 504,
                  4, 260, 132, 388, 68, 324, 196, 452, 36, 292, 164, 420, 100, 356, 228, 484,
                 20, 276, 148, 404, 84, 340, 212, 468, 52, 308, 180, 436, 116, 372, 244, 500,
                 12, 268, 140, 396, 76, 332, 204, 460, 44, 300, 172, 428, 108, 364, 236, 492,
                 28, 284, 156, 412, 92, 348, 220, 476, 60, 316, 188, 444, 124, 380, 252, 508,
                  2, 258, 130, 386, 66, 322, 194, 450, 34, 290, 162, 418,  98, 354, 226, 482,
                 18, 274, 146, 402, 82, 338, 210, 466, 50, 306, 178, 434, 114, 370, 242, 498,
                 10, 266, 138, 394, 74, 330, 202, 458, 42, 298, 170, 426, 106, 362, 234, 490,
                 26, 282, 154, 410, 90, 346, 218, 474, 58, 314, 186, 442, 122, 378, 250, 506,
                  6, 262, 134, 390, 70, 326, 198, 454, 38, 294, 166, 422, 102, 358, 230, 486,
                 22, 278, 150, 406, 86, 342, 214, 470, 54, 310, 182, 438, 118, 374, 246, 502,
                 14, 270, 142, 398, 78, 334, 206, 462, 46, 302, 174, 430, 110, 366, 238, 494,
                 30, 286, 158, 414, 94, 350, 222, 478, 62, 318, 190, 446, 126, 382, 254, 510,
                  1, 257, 129, 385, 65, 321, 193, 449, 33, 289, 161, 417,  97, 353, 225, 481,
                 17, 273, 145, 401, 81, 337, 209, 465, 49, 305, 177, 433, 113, 369, 241, 497,
                  9, 265, 137, 393, 73, 329, 201, 457, 41, 297, 169, 425, 105, 361, 233, 489,
                 25, 281, 153, 409, 89, 345, 217, 473, 57, 313, 185, 441, 121, 377, 249, 505,
                  5, 261, 133, 389, 69, 325, 197, 453, 37, 293, 165, 421, 101, 357, 229, 485,
                 21, 277, 149, 405, 85, 341, 213, 469, 53, 309, 181, 437, 117, 373, 245, 501,
                 13, 269, 141, 397, 77, 333, 205, 461, 45, 301, 173, 429, 109, 365, 237, 493,
                 29, 285, 157, 413, 93, 349, 221, 477, 61, 317, 189, 445, 125, 381, 253, 509,
                  3, 259, 131, 387, 67, 323, 195, 451, 35, 291, 163, 419,  99, 355, 227, 483,
                 19, 275, 147, 403, 83, 339, 211, 467, 51, 307, 179, 435, 115, 371, 243, 499,
                 11, 267, 139, 395, 75, 331, 203, 459, 43, 299, 171, 427, 107, 363, 235, 491,
                 27, 283, 155, 411, 91, 347, 219, 475, 59, 315, 187, 443, 123, 379, 251, 507,
                  7, 263, 135, 391, 71, 327, 199, 455, 39, 295, 167, 423, 103, 359, 231, 487,
                 23, 279, 151, 407, 87, 343, 215, 471, 55, 311, 183, 439, 119, 375, 247, 503,
                 15, 271, 143, 399, 79, 335, 207, 463, 47, 303, 175, 431, 111, 367, 239, 495,
                 31, 287, 159, 415, 95, 351, 223, 479, 63, 319, 191, 447, 127, 383, 255, 511));


const func integer: reverseBits (in integer: size, in var integer: bits) is func
  result
    var integer: reversed is 0;
  local
    var integer: bitPos is 0;
  begin
    for bitPos range 1 to size do
      reversed <<:= 1;
      reversed +:= bits mod 2;
      bits >>:= 1;
    end for;
  end func;


(**
 *  Type to read bitwise data starting with the least significant bit.
 *  This is used by the Huffman compression (as part of the deflate
 *  compression) used for ZIP and GZIP files. It is also used by the
 *  Lempel-Ziv-Welch compression used for GIF files.
 *  In a ''lsbInBitStream'' the read direction is from
 *  LSB (least significant bit) to MSB (most significant bit).
 *  For the bit position in a byte holds: 0 = LSB, 7 = MSB.
 *)
const type: lsbInBitStream is new struct
    var file: inFile is STD_NULL;
    var integer: buffer is 0;
    var integer: bitPos is 0;
    var string: striBuffer is "";
    var integer: striBufferIncrease is 4096;
    var integer: tailSize is 0;
    var integer: limit is 0;
    var integer: bytePos is 1;
  end struct;


# The type lsbBitStream is deprecated. Use lsbInBitStream instead.
const type: lsbBitStream is lsbInBitStream;


const proc: fillStriBuffer (inout lsbInBitStream: inBitStream) is func
  begin
    inBitStream.striBuffer := inBitStream.striBuffer[inBitStream.bytePos ..] &
                            gets(inBitStream.inFile, inBitStream.striBufferIncrease);
    if not hasNext(inBitStream.inFile) then
      # Append "\16#ff;\16#ff;\16#ff;\16#ff;\16#ff;" to the data.
      # This allows a peek of 32 bits also at the end of the data.
      inBitStream.striBuffer &:= "\16#ff;\16#ff;\16#ff;\16#ff;\16#ff;";
      inBitStream.tailSize := 5;
    end if;
    inBitStream.limit := max(0, length(inBitStream.striBuffer) - 4);
    inBitStream.bytePos := 1;
  end func;


const proc: fillBuffer (inout lsbInBitStream: inBitStream) is func
  begin
    if inBitStream.bytePos > inBitStream.limit then
      fillStriBuffer(inBitStream);
    end if;
    inBitStream.buffer := bytes2Int(inBitStream.striBuffer[inBitStream.bytePos fixLen 5], UNSIGNED, LE);
  end func;


(**
 *  Open an LSB bit stream from the file ''inFile'' for reading.
 *  In a ''lsbInBitStream'' the read direction is from
 *  LSB (least significant bit) to MSB (most significant bit).
 *)
const func lsbInBitStream: openLsbInBitStream (in file: inFile) is func
  result
    var lsbInBitStream: inBitStream is lsbInBitStream.value;
  begin
    inBitStream.inFile := inFile;
    fillBuffer(inBitStream);
  end func;


# The function openLsbBitStream(file) is deprecated. Use openLsbInBitStream(file) instead.
const func lsbInBitStream: openLsbBitStream (in file: inFile) is
  return openLsbInBitStream(inFile);


(**
 *  Open an LSB bit stream from the string ''stri'' for reading.
 *  In a ''lsbInBitStream'' the read direction is from
 *  LSB (least significant bit) to MSB (most significant bit).
 *)
const func lsbInBitStream: openLsbInBitStream (in string: stri) is func
  result
    var lsbInBitStream: inBitStream is lsbInBitStream.value;
  begin
    # Append "\16#ff;\16#ff;\16#ff;\16#ff;\16#ff;" to the data.
    # This allows a peek of 32 bits also at the end of the data.
    inBitStream.striBuffer := stri & "\16#ff;\16#ff;\16#ff;\16#ff;\16#ff;";
    inBitStream.limit := length(inBitStream.striBuffer);
    fillBuffer(inBitStream);
  end func;


# The function openLsbBitStream(string) is deprecated. Use openLsbInBitStream(string) instead.
const func lsbInBitStream: openLsbBitStream (in string: stri) is
  return openLsbInBitStream(stri);


(**
 *  Close an LSB bit stream and position the underlying file at the next byte.
 *)
const proc: close (inout lsbInBitStream: inBitStream) is func
  begin
    if inBitStream.inFile <> STD_NULL then
      if inBitStream.bitPos <> 0 then
        incr(inBitStream.bytePos);
      end if;
      seek(inBitStream.inFile, tell(inBitStream.inFile) -
           succ(length(inBitStream.striBuffer) -
                inBitStream.bytePos - inBitStream.tailSize));
    end if;
  end func;


(**
 *  Get one bit in LSB-First order from ''inBitStream''.
 *  The bit is read at the current byte and bit position. Afterwards
 *  byte and bit position are advanced by one bit. The read
 *  direction is from LSB (least significant bit) to MSB (most significant bit).
 *   aBitStream := openLsbInBitStream("\2#01101011;\2#11001110;");
 *   skipBits(aBitStream, 5);
 *   # Original data:  "\2#01101011;\2#11001110;"
 *   #                       ^
 *   #                    current
 *   #                   position
 *   getBit(aBitStream)  returns  2#1
 *   # Original data:  "\2#01101011;\2#11001110;"
 *   #                       1
 *   #                    bit of
 *   #                  the result
 *   # Now aBitStream is at bytePos=1 and bitPos=6 of the original data.
 *   # Original data:  "\2#01101011;\2#11001110;"
 *   #                      ^
 *   #                   current
 *   #                  position
 *  @param inBitStream LSB orderd bit stream from which the bit is read.
 *  @exception RANGE_ERROR If the end of ''inBitStream'' has been reached.
 *)
const func integer: getBit (inout lsbInBitStream: inBitStream) is func
  result
    var integer: resultBit is 0;
  begin
    resultBit := (inBitStream.buffer >> inBitStream.bitPos) mod 2;
    incr(inBitStream.bitPos);
    if inBitStream.bitPos >= 8 then
      inBitStream.bitPos := 0;
      incr(inBitStream.bytePos);
      if inBitStream.bytePos > inBitStream.limit then
        fillStriBuffer(inBitStream);
      end if;
      inBitStream.buffer := (inBitStream.buffer >> 8) +
          (bytes2Int(inBitStream.striBuffer[inBitStream.bytePos + 4 fixLen 1], UNSIGNED, LE) << 32);
    end if;
  end func;


(**
 *  Get ''bitWidth'' bits in LSB-First order from ''inBitStream''.
 *  The bits are read at the current byte and bit position. Afterwards
 *  byte and bit position are advanced by ''bitWidth'' bits. The read
 *  direction is from LSB (least significant bit) to MSB (most significant bit).
 *  If bits from the next byte(s) are read a byte order of little-endian
 *  is used.
 *   aBitStream := openLsbInBitStream("\2#01101011;\2#11001110;");
 *   skipBits(aBitStream, 5);
 *   # Original data:  "\2#01101011;\2#11001110;"
 *   #                       ^
 *   #                    current
 *   #                   position
 *   getBits(aBitStream, 5)  returns  2#10011
 *   # Original data:  "\2#01101011;\2#11001110;"
 *   #                     011               10
 *   #                 lower bits        higher bits
 *   #                  of result         of result
 *   # Now aBitStream is at bytePos=2 and bitPos=2 of the original data.
 *   # Original data:  "\2#01101011;\2#11001110;"
 *   #                                      ^
 *   #                                   current
 *   #                                   position
 *  @param inBitStream LSB orderd bit stream from which the bits are read.
 *  @param bitWidth Number of bits requested.
 *  @exception RANGE_ERROR If the end of ''inBitStream'' has been reached.
 *)
const func integer: getBits (inout lsbInBitStream: inBitStream, in integer: bitWidth) is func
  result
    var integer: resultBits is 0;
  local
    var integer: bytePosDelta is 0;
  begin
    resultBits := (inBitStream.buffer >> inBitStream.bitPos) mod (1 << bitWidth);
    inBitStream.bitPos +:= bitWidth;
    bytePosDelta := inBitStream.bitPos mdiv 8;
    if bytePosDelta <> 0 then
      inBitStream.bitPos := inBitStream.bitPos mod 8;
      inBitStream.bytePos +:= bytePosDelta;
      if inBitStream.bytePos > inBitStream.limit then
        fillStriBuffer(inBitStream);
      end if;
      if bytePosDelta = 1 then
        inBitStream.buffer := (inBitStream.buffer >> 8) +
            (bytes2Int(inBitStream.striBuffer[inBitStream.bytePos + 4 fixLen 1], UNSIGNED, LE) << 32);
      elsif bytePosDelta = 2 then
        inBitStream.buffer := (inBitStream.buffer >> 16) +
            (bytes2Int(inBitStream.striBuffer[inBitStream.bytePos + 3 fixLen 2], UNSIGNED, LE) << 24);
      else
        inBitStream.buffer := bytes2Int(inBitStream.striBuffer[inBitStream.bytePos fixLen 5], UNSIGNED, LE);
      end if;
    end if;
  end func;


(**
 *  Peek ''bitWidth'' bits in LSB-First order from ''inBitStream''.
 *  The bits are read at the current byte and bit position. Byte
 *  and bit position remain unchanged. The read direction is from
 *  LSB (least significant bit) to MSB (most significant bit).
 *  If bits from the next byte(s) are read a byte order of little-endian
 *  is used.
 *   aBitStream := openLsbInBitStream("\2#01101011;\2#10101101;");
 *   skipBits(aBitStream, 5);
 *   # Original data:  "\2#01101011;\2#10101101;"
 *   #                       ^
 *   #                    current
 *   #                   position
 *   peekBits(aBitStream, 6)  returns  2#101011
 *   # Original data:  "\2#01101011;\2#10101101;"
 *   #                     011              101
 *   #                 lower bits        higher bits
 *   #                  of result         of result
 *   # BytePos and bitPos of aBitStream have not changed.
 *  @param inBitStream LSB orderd bit stream from which the bits are peeked.
 *  @param bitWidth Number of bits requested.
 *  @exception RANGE_ERROR If the end of ''inBitStream'' has been reached.
 *)
const func integer: peekBits (inout lsbInBitStream: inBitStream, in integer: bitWidth) is
  return (inBitStream.buffer >> inBitStream.bitPos) mod (1 << bitWidth);


(**
 *  Advance the bit position of ''inBitStream'' by ''bitWidth'' bits.
 *   aBitStream := openLsbInBitStream("\2#01101011;\2#11001110;");
 *   # Now aBitStream has bytePos=1 and bitPos=0 of the original data.
 *   # Original data:  "\2#01101011;\2#11001110;"
 *   #                            ^
 *   #                         current
 *   #                        position
 *   skipBits(aBitStream, 5);
 *   # Now aBitStream is at bytePos=1 and bitPos=5 of the original data.
 *   # Original data:  "\2#01101011;\2#11001110;"
 *   #                       ^
 *   #                    current
 *   #                   position
 *  @param inBitStream LSB orderd bit stream from which the bits are skipped.
 *  @param bitWidth Number of bits to be skipped.
 *)
const proc: skipBits (inout lsbInBitStream: inBitStream, in integer: bitWidth) is func
  local
    var integer: bytePosDelta is 0;
  begin
    inBitStream.bitPos +:= bitWidth;
    bytePosDelta := inBitStream.bitPos mdiv 8;
    if bytePosDelta <> 0 then
      inBitStream.bitPos := inBitStream.bitPos mod 8;
      inBitStream.bytePos +:= bytePosDelta;
      if inBitStream.bytePos > inBitStream.limit then
        fillStriBuffer(inBitStream);
      end if;
      if bytePosDelta = 1 then
        inBitStream.buffer := (inBitStream.buffer >> 8) +
            (bytes2Int(inBitStream.striBuffer[inBitStream.bytePos + 4 fixLen 1], UNSIGNED, LE) << 32);
      elsif bytePosDelta = 2 then
        inBitStream.buffer := (inBitStream.buffer >> 16) +
            (bytes2Int(inBitStream.striBuffer[inBitStream.bytePos + 3 fixLen 2], UNSIGNED, LE) << 24);
      else
        inBitStream.buffer := bytes2Int(inBitStream.striBuffer[inBitStream.bytePos fixLen 5], UNSIGNED, LE);
      end if;
    end if;
  end func;


(**
 *  Get up to ''maxLength'' bytes from ''inBitStream''.
 *  The function returns bytes from the original data. If the current byte of
 *  ''inBitStream'' is partially used, it is not considered, and the bytes are
 *  read beginning with the next byte from the original data. After the data is
 *  read, the position of ''inBitStream'' is advanced to the beginning of the
 *  next byte. A ''maxLength'' of 0 sets the position to the beginning of the
 *  next byte and returns an empty string.
 *   aBitStream := openLsbInBitStream("\2#01101011;\2#1001111;\2#1001011;\2#1101;");
 *   skipBits(aBitStream, 5);
 *   # Original data:  "\2#01101011;\2#1001111;\2#1001011;\2#1101;"
 *   #                       ^
 *   #                    current
 *   #                   position
 *   gets(aBitStream, 2)  returns "\2#1001111;\2#1001011;" (="OK")
 *  @param inBitStream LSB orderd bit stream from which the bytes are read.
 *  @param maxLength The maximum number of bytes to be read.
 *  @exception RANGE_ERROR The parameter ''maxLength'' is negative.
 *)
const func string: gets (inout lsbInBitStream: inBitStream, in integer: maxLength) is func
  result
    var string: striRead is "";
  begin
    if maxLength < 0 then
      raise RANGE_ERROR;
    else
      # Go to the next available byte boundary
      if inBitStream.bitPos <> 0 then
        incr(inBitStream.bytePos);
        inBitStream.bitPos := 0;
      end if;
      if maxLength <> 0 then
        if maxLength <= succ(length(inBitStream.striBuffer) - inBitStream.bytePos) then
          striRead := inBitStream.striBuffer[inBitStream.bytePos fixLen maxLength];
          inBitStream.bytePos +:= maxLength;
        else
          striRead := inBitStream.striBuffer[inBitStream.bytePos ..] &
                      gets(inBitStream.inFile, maxLength -
                           succ(length(inBitStream.striBuffer) - inBitStream.bytePos));
          inBitStream.striBuffer := "";
          inBitStream.limit := 0;
          inBitStream.bytePos := 1;
        end if;
      end if;
      fillBuffer(inBitStream);
    end if;
  end func;


(**
 *  Type to read bitwise data starting with the most significant bit.
 *  This is used by the Huffman compression used for JPEG files.
 *  In a ''msbInBitStream'' the read direction is from
 *  MSB (most significant bit) to LSB (least significant bit).
 *  For the bit position in a byte holds: 0 = MSB, 7 = LSB.
 *)
const type: msbInBitStream is new struct
    var file: inFile is STD_NULL;
    var integer: buffer is 0;
    var integer: bitPos is 40;
    var string: striBuffer is "";
    var integer: striBufferIncrease is 4096;
    var integer: tailSize is 0;
    var integer: limit is 0;
    var integer: bytePos is 1;
  end struct;


# The type msbBitStream is deprecated. Use msbInBitStream instead.
const type: msbBitStream is msbInBitStream;


const proc: fillStriBuffer (inout msbInBitStream: inBitStream) is func
  begin
    inBitStream.striBuffer := inBitStream.striBuffer[inBitStream.bytePos ..] &
                            gets(inBitStream.inFile, inBitStream.striBufferIncrease);
    if not hasNext(inBitStream.inFile) then
      # Append "\16#ff;\16#ff;\16#ff;\16#ff;\16#ff;" to the data.
      # This allows a peek of 32 bits also at the end of the data.
      inBitStream.striBuffer &:= "\16#ff;\16#ff;\16#ff;\16#ff;\16#ff;";
      inBitStream.tailSize := 5;
    end if;
    inBitStream.limit := max(0, length(inBitStream.striBuffer) - 4);
    inBitStream.bytePos := 1;
  end func;


const proc: fillBuffer (inout msbInBitStream: inBitStream) is func
  begin
    if inBitStream.bytePos > inBitStream.limit then
      fillStriBuffer(inBitStream);
    end if;
    inBitStream.buffer := bytes2Int(inBitStream.striBuffer[inBitStream.bytePos fixLen 5], UNSIGNED, BE);
  end func;


(**
 *  Open an MSB bit stream from the file ''inFile'' for reading.
 *  In a ''msbInBitStream'' the read direction is from
 *  MSB (most significant bit) to LSB (least significant bit).
 *)
const func msbInBitStream: openMsbInBitStream (in file: inFile) is func
  result
    var msbInBitStream: inBitStream is msbInBitStream.value;
  begin
    inBitStream.inFile := inFile;
    fillBuffer(inBitStream);
  end func;


# The function openMsbBitStream(file) is deprecated. Use openMsbInBitStream(file) instead.
const func msbInBitStream: openMsbBitStream (in file: inFile) is
  return openMsbInBitStream(inFile);


(**
 *  Open an MSB bit stream from the string ''stri'' for reading.
 *  In a ''msbInBitStream'' the read direction is from
 *  MSB (most significant bit) to LSB (least significant bit).
 *)
const func msbInBitStream: openMsbInBitStream (in string: stri) is func
  result
    var msbInBitStream: inBitStream is msbInBitStream.value;
  begin
    # Append "\16#ff;\16#ff;\16#ff;\16#ff;\16#ff;" to the data.
    # This allows a peek of 32 bits also at the end of the data.
    inBitStream.striBuffer := stri & "\16#ff;\16#ff;\16#ff;\16#ff;\16#ff;";
    inBitStream.limit := length(inBitStream.striBuffer);
    fillBuffer(inBitStream);
  end func;


# The function openMsbBitStream(string) is deprecated. Use openMsbInBitStream(string) instead.
const func msbInBitStream: openMsbBitStream (in string: stri) is
  return openMsbInBitStream(stri);


(**
 *  Close an MSB bit stream and position the underlying file at the next byte.
 *)
const proc: close (inout msbInBitStream: inBitStream) is func
  begin
    if inBitStream.inFile <> STD_NULL then
      if inBitStream.bitPos <> 40 then
        incr(inBitStream.bytePos);
      end if;
      seek(inBitStream.inFile, tell(inBitStream.inFile) -
           succ(length(inBitStream.striBuffer) -
                inBitStream.bytePos - inBitStream.tailSize));
    end if;
  end func;


(**
 *  Get one bit in MSB-First order from ''inBitStream''.
 *  The bits are read at the current byte and bit position. Afterwards
 *  byte and bit position are advanced by ''bitWidth'' bits. The read
 *  direction is from MSB (most significant bit) to LSB (least significant bit).
 *  If bits from the next byte(s) are read a byte order of big-endian
 *  is used.
 *   aBitStream := openMsbInBitStream("\2#01011100;\2#11010110;");
 *   skipBits(aBitStream, 5);
 *   # Original data:  "\2#01011100;\2#11010110;";
 *   #                          ^
 *   #                       current
 *   #                      position
 *   getBit(aBitStream)  returns  2#1
 *   # Original data:  "\2#01011100;\2#11010110;";
 *   #                          1
 *   #                       bit of
 *   #                     the result
 *   # Now aBitStream is at bytePos=1 and bitPos=6 of the original data.
 *   # Original data:  "\2#01011100;\2#11010110;";
 *   #                           ^
 *   #                        current
 *   #                       position
 *  @param inBitStream MSB orderd bit stream from which the bits are peeked.
 *  @exception RANGE_ERROR If the end of ''inBitStream'' has been reached.
 *)
const func integer: getBit (inout msbInBitStream: inBitStream) is func
  result
    var integer: resultBit is 0;
  begin
    decr(inBitStream.bitPos);
    resultBit := (inBitStream.buffer >> inBitStream.bitPos) mod 2;
    if pred(inBitStream.bitPos) mdiv 8 <> 4 then
      inBitStream.bitPos := inBitStream.bitPos + 8;
      incr(inBitStream.bytePos);
      if inBitStream.bytePos > inBitStream.limit then
        fillStriBuffer(inBitStream);
      end if;
      inBitStream.buffer := ((inBitStream.buffer mod 2 ** 32) << 8) +
          bytes2Int(inBitStream.striBuffer[inBitStream.bytePos + 4 fixLen 1], UNSIGNED, BE);
    end if;
  end func;


(**
 *  Get ''bitWidth'' bits in MSB-First order from ''inBitStream''.
 *  The bits are read at the current byte and bit position. Afterwards
 *  byte and bit position are advanced by ''bitWidth'' bits. The read
 *  direction is from MSB (most significant bit) to LSB (least significant bit).
 *  If bits from the next byte(s) are read a byte order of big-endian
 *  is used.
 *   aBitStream := openMsbInBitStream("\2#01011100;\2#11010110;");
 *   skipBits(aBitStream, 5);
 *   # Original data:  "\2#01011100;\2#11010110;";
 *   #                          ^
 *   #                       current
 *   #                      position
 *   getBits(aBitStream, 5)  returns  2#10011
 *   # Original data:  "\2#01011100;\2#11010110;";
 *   #                          100    11
 *   #                   higher bits  lower bits
 *   #                    of result    of result
 *   # Now aBitStream is at bytePos=2 and bitPos=2 of the original data.
 *   # Original data:  "\2#01011100;\2#11010110;";
 *   #                                   ^
 *   #                                current
 *   #                                position
 *  @param inBitStream MSB orderd bit stream from which the bits are peeked.
 *  @param bitWidth Number of bits requested.
 *  @exception RANGE_ERROR If the end of ''inBitStream'' has been reached.
 *)
const func integer: getBits (inout msbInBitStream: inBitStream, in integer: bitWidth) is func
  result
    var integer: resultBits is 0;
  local
    var integer: bytePosDelta is 0;
  begin
    inBitStream.bitPos -:= bitWidth;
    resultBits := (inBitStream.buffer >> inBitStream.bitPos) mod (1 << bitWidth);
    bytePosDelta := 4 - pred(inBitStream.bitPos) mdiv 8;
    if bytePosDelta <> 0 then
      inBitStream.bitPos := inBitStream.bitPos + 8 * bytePosDelta;
      inBitStream.bytePos +:= bytePosDelta;
      if inBitStream.bytePos > inBitStream.limit then
        fillStriBuffer(inBitStream);
      end if;
      if bytePosDelta = 1 then
        inBitStream.buffer := ((inBitStream.buffer mod 2 ** 32) << 8) +
            bytes2Int(inBitStream.striBuffer[inBitStream.bytePos + 4 fixLen 1], UNSIGNED, BE);
      else
        inBitStream.buffer := bytes2Int(inBitStream.striBuffer[inBitStream.bytePos fixLen 5], UNSIGNED, BE);
      end if;
    end if;
  end func;


(**
 *  Peek ''bitWidth'' bits in MSB-First order from ''inBitStream''.
 *  The bits are read at the current byte and bit position. Byte
 *  and bit position remain unchanged. The read direction is from
 *  MSB (most significant bit) to LSB (least significant bit).
 *  If bits from the next byte(s) are read a byte order of big-endian
 *  is used.
 *   aBitStream := openMsbInBitStream("\2#01011100;\2#11010110;");
 *   skipBits(aBitStream, 5);
 *   # Original data:  "\2#01011100;\2#11010110;";
 *   #                          ^
 *   #                       current
 *   #                      position
 *   peekBits(aBitStream, 6)  returns  2#100110
 *   # Original data:  "\2#01011100;\2#11010110;";
 *   #                          100    110
 *   #                   higher bits  lower bits
 *   #                    of result    of result
 *   # BytePos and bitPos of aBitStream have not changed.
 *  @param inBitStream MSB orderd bit stream from which the bits are read.
 *  @param bitWidth Number of bits requested.
 *  @exception RANGE_ERROR If the end of ''inBitStream'' has been reached.
 *)
const func integer: peekBits (inout msbInBitStream: inBitStream, in integer: bitWidth) is
  return (inBitStream.buffer >> (inBitStream.bitPos - bitWidth)) mod (1 << bitWidth);


(**
 *  Advance the bit position of ''inBitStream'' by ''bitWidth'' bits.
 *   aBitStream := openMsbInBitStream("\2#01101011;\2#11001110;");
 *   # Now aBitStream has bytePos=1 and bitPos=0 of the original data.
 *   # Original data:  "\2#01101011;\2#11001110;"
 *   #                     ^
 *   #                  current
 *   #                 position
 *   skipBits(aBitStream, 5);
 *   # Now aBitStream is at bytePos=1 and bitPos=5 of the original data.
 *   # Original data:  "\2#01101011;\2#11001110;"
 *   #                          ^
 *   #                       current
 *   #                      position
 *  @param inBitStream MSB orderd bit stream from which the bits are skipped.
 *  @param bitWidth Number of bits to be skipped.
 *)
const proc: skipBits (inout msbInBitStream: inBitStream, in integer: bitWidth) is func
  local
    var integer: bytePosDelta is 0;
  begin
    inBitStream.bitPos -:= bitWidth;
    bytePosDelta := 4 - pred(inBitStream.bitPos) mdiv 8;
    if bytePosDelta <> 0 then
      inBitStream.bitPos := inBitStream.bitPos + 8 * bytePosDelta;
      inBitStream.bytePos +:= bytePosDelta;
      if inBitStream.bytePos > inBitStream.limit then
        fillStriBuffer(inBitStream);
      end if;
      if bytePosDelta = 1 then
        inBitStream.buffer := ((inBitStream.buffer mod 2 ** 32) << 8) +
            bytes2Int(inBitStream.striBuffer[inBitStream.bytePos + 4 fixLen 1], UNSIGNED, BE);
      else
        inBitStream.buffer := bytes2Int(inBitStream.striBuffer[inBitStream.bytePos fixLen 5], UNSIGNED, BE);
      end if;
    end if;
  end func;


(**
 *  Get up to ''maxLength'' bytes from ''inBitStream''.
 *  The function returns bytes from the original data. If the current byte of
 *  ''inBitStream'' is partially used, it is not considered, and the bytes are
 *  read beginning with the next byte from the original data. After the data is
 *  read, the position of ''inBitStream'' is advanced to the beginning of the
 *  next byte. A ''maxLength'' of 0 sets the position to the beginning of the
 *  next byte and returns an empty string.
 *   aBitStream := openMsbInBitStream("\2#01101011;\2#1001111;\2#1001011;\2#1101;");
 *   skipBits(aBitStream, 5);
 *   # Original data:  "\2#01101011;\2#1001111;\2#1001011;\2#1101;"
 *   #                       ^
 *   #                    current
 *   #                   position
 *   gets(aBitStream, 2)  returns "\2#1001111;\2#1001011;" (="OK")
 *  @param inBitStream MSB orderd bit stream from which the bytes are read.
 *  @param maxLength The maximum number of bytes to be read.
 *  @exception RANGE_ERROR The parameter ''maxLength'' is negative.
 *)
const func string: gets (inout msbInBitStream: inBitStream, in integer: maxLength) is func
  result
    var string: striRead is "";
  begin
    if maxLength < 0 then
      raise RANGE_ERROR;
    else
      # Go to the next available byte boundary
      if inBitStream.bitPos <> 40 then
        incr(inBitStream.bytePos);
        inBitStream.bitPos := 40;
      end if;
      if maxLength <> 0 then
        if maxLength <= succ(length(inBitStream.striBuffer) - inBitStream.bytePos) then
          striRead := inBitStream.striBuffer[inBitStream.bytePos fixLen maxLength];
          inBitStream.bytePos +:= maxLength;
        else
          striRead := inBitStream.striBuffer[inBitStream.bytePos ..] &
                      gets(inBitStream.inFile, maxLength -
                           succ(length(inBitStream.striBuffer) - inBitStream.bytePos));
          inBitStream.striBuffer := "";
          inBitStream.limit := 0;
          inBitStream.bytePos := 1;
        end if;
      end if;
      fillBuffer(inBitStream);
    end if;
  end func;


(**
 *  Type to write bitwise data starting with the least significant bit.
 *  In a ''lsbOutBitStream'' the write direction is from
 *  LSB (least significant bit) to MSB (most significant bit).
 *  For the bit position in a byte (bitPos) holds: 0 = LSB, 7 = MSB.
 *  The bits are stored in a string of bytes. The byte string can
 *  be obtained with the function getBytes(). The function flush()
 *  can be used to add a partially filled byte to the byte string.
 *  This bit encoding is used by the Huffman compression (as part of
 *  the deflate compression) used for ZIP and GZIP files. It is also
 *  used by the Lempel-Ziv-Welch compression used for GIF files.
 *)
const type: lsbOutBitStream is new struct
    var integer: buffer is 0;
    var integer: bitPos is 0;
    var string: byteString is "";
  end struct;


(**
 *  Append one bit in LSB-First order to ''outBitStream''.
 *  The append direction is from LSB (least significant bit) to
 *  MSB (most significant bit).
 *   # Stream data:   "\2#0101011;"  and  bitPos = 7
 *   #                   ^
 *   #                current
 *   #               position
 *   putBit(aBitStream, 2#1)
 *   # Stream data:  "\2#10101011;"  and  bitPos = 0
 *   #                   1
 *   #                appended
 *   #                  bit
 *   putBit(aBitStream, 2#1)
 *   # Stream data:  "\2#10101011;\2#1;"  and  bitPos = 1
 *   #                               1
 *   #                            appended
 *   #                              bit
 *  @param outBitStream Bit stream to which the bit is appended.
 *  @param bit Bit to be appended to ''outBitStream''.
 *)
const proc: putBit (inout lsbOutBitStream: outBitStream, in integer: bit) is func
  begin
    outBitStream.buffer +:= bit << outBitStream.bitPos;
    incr(outBitStream.bitPos);
    if outBitStream.bitPos = 8 then
      outBitStream.byteString &:= char(outBitStream.buffer);
      outBitStream.bitPos := 0;
      outBitStream.buffer := 0;
    end if;
  end func;


(**
 *  Append ''bitWidth'' bits in LSB-First order to ''outBitStream''.
 *  The append direction is from LSB (least significant bit) to
 *  MSB (most significant bit). If necessary additional bytes are
 *  added to ''stristri''.
 *   # Stream data:     "\2#01011;"  and  bitPos = 5
 *   #                     ^
 *   #                  current
 *   #                 position
 *   putBits(aBitStream, 2#10011, 5);
 *   # Stream data:  "\2#01101011;\2#10;"  and  bitPos = 2
 *   #                   011         10
 *   #                appended    appended
 *   #               lower bits  higher bits
 *  @param outBitStream Bit stream to which the bits are appended.
 *  @param bits Bits to be appended to ''outBitStream''.
 *  @param bitWidth Number of bits to be appended (width of ''bits'').
 *)
const proc: putBits (inout lsbOutBitStream: outBitStream, in integer: bits,
    in integer: bitWidth) is func
  begin
    outBitStream.buffer +:= bits << outBitStream.bitPos;
    outBitStream.bitPos +:= bitWidth;
    while outBitStream.bitPos >= 8 do
      outBitStream.byteString &:= char(outBitStream.buffer mod 256);
      outBitStream.bitPos -:= 8;
      outBitStream.buffer >>:= 8;
    end while;
  end func;


(**
 *  Obtain the length of the given ''outBitStream''.
 *  The bit stream length is measured in bits.
 *  @param outBitStream Bit stream from which the length is obtained.
 *  @return the length of the bit stream.
 *)
const func integer: length (in lsbOutBitStream: outBitStream) is
  return length(outBitStream.byteString) * 8 + outBitStream.bitPos;


(**
 *  Truncate ''outBitStream'' to the given ''length''.
 *  If the bit stream previously was larger than ''length'', the extra data is lost.
 *  If the bit stream previously was shorter, it is extended, and the extended
 *  part is filled with zero bits.
 *  @param outBitStream Bit stream to be truncated.
 *  @param length Requested length of ''outBitStream'' in bits.
 *  @exception RANGE_ERROR The requested length is negative.
 *)
const proc: truncate (inout lsbOutBitStream: outBitStream, in integer: length) is func
  local
    var integer: bytePos is 0;
    var integer: bitPos is 0;
  begin
    if length < 0 then
      raise RANGE_ERROR;
    else
      bytePos := length mdiv 8;
      bitPos := length mod 8;
      if bytePos < length(outBitStream.byteString) then
        outBitStream.buffer := ord(outBitStream.byteString[succ(bytePos)]) mod 2 ** bitPos;
        outBitStream.byteString := outBitStream.byteString[.. bytePos];
      elsif bytePos = length(outBitStream.byteString) then
        if bitPos < outBitStream.bitPos then
          outBitStream.buffer := outBitStream.buffer mod 2 ** bitPos;
        end if;
      else
        outBitStream.byteString &:= char(outBitStream.buffer);
        outBitStream.byteString &:= "\0;" mult bytePos - length(outBitStream.byteString);
        outBitStream.buffer := 0;
      end if;
      outBitStream.bitPos := bitPos;
    end if;
  end func;


(**
 *  Complete a partially filled byte and add it to the byte string.
 *  If ''outBitStream'' has a partially filled byte it is filled with zero
 *  bits and added to the byte string. If ''outBitStream'' has not a
 *  partially filled byte nothing is done.
 *  @param outBitStream Bit stream where the partially filled byte is added.
 *)
const proc: flush (inout lsbOutBitStream: outBitStream) is func
  begin
    if outBitStream.bitPos <> 0 then
      outBitStream.byteString &:= char(outBitStream.buffer);
      outBitStream.bitPos := 0;
    end if;
    outBitStream.buffer := 0;
  end func;


(**
 *  Obtain the byte string created from the bits written to ''outBitStream''.
 *  The returned byte string is removed from ''outBitStream''.
 *  A partially filled byte is not part of the returned byte string.
 *  The function flush() can be called in advance to add a
 *  partially filled byte to the byte string.
 *  @param outBitStream Bit stream from which the byte string is obtained.
 *  @return a string of completely filled bytes from ''outBitStream''.
 *)
const func string: getBytes (inout lsbOutBitStream: outBitStream) is func
  result
    var string: bytes is "";
  begin
    bytes := outBitStream.byteString;
    outBitStream.byteString := "";
  end func;


(**
 *  Add the given string ''stri'' to the byte string of ''outBitStream''.
 *  The ''outBitStream'' is flushed before adding ''stri''.
 *  @param outBitStream Bit stream to which ''stri'' is added.
 *  @param stri String to be added to ''outBitStream''.
 *)
const proc: write (inout lsbOutBitStream: outBitStream, in string: stri) is func
  begin
    flush(outBitStream);
    outBitStream.byteString &:= stri;
  end func;


(**
 *  Type to write bitwise data starting with the most significant bit.
 *  In a ''msbOutBitStream'' the write direction is from
 *  MSB (most significant bit) to LSB (least significant bit).
 *  For the bit position in a byte (bitSize) holds: 0 = MSB, 7 = LSB.
 *  The bits are stored in a string of bytes. The byte string can
 *  be obtained with the function getBytes(). The function flush()
 *  can be used to add a partially filled byte to the byte string.
 *  This bit encoding is used by the Huffman compression used for
 *  JPEG files.
 *)
const type: msbOutBitStream is new struct
    var integer: buffer is 0;
    var integer: bitSize is 0;
    var string: byteString is "";
  end struct;


(**
 *  Append one bit in MSB-First order to ''outBitStream''.
 *  The append direction is from MSB (most significant bit) to
 *  LSB (least significant bit).
 *   # Stream data:  "\2#01011100;"  and  bitPos = 7
 *   #                          ^
 *   #                       current
 *   #                       position
 *   putBit(aBitStream, 2#1)
 *   # Stream data:  "\2#01011101;"  and  bitPos = 0
 *   #                          1
 *   #                       appended
 *   #                         bit
 *   putBit(aBitStream, 2#1)
 *   # Stream data:  "\2#01011101;\2#10000000;"  and  bitPos = 1
 *   #                               1
 *   #                            appended
 *   #                              bit
 *  @param outBitStream Bit stream to which the bit is appended.
 *  @param bit Bit to be appended to ''outBitStream''.
 *)
const proc: putBit (inout msbOutBitStream: outBitStream, in integer: bit) is func
  begin
    outBitStream.buffer <<:= 1;
    outBitStream.buffer +:= bit;
    incr(outBitStream.bitSize);
    if outBitStream.bitSize = 8 then
      outBitStream.byteString &:= char(outBitStream.buffer);
      outBitStream.bitSize := 0;
      outBitStream.buffer := 0;
    end if;
  end func;


(**
 *  Append ''bitWidth'' bits in MSB-First order to ''outBitStream''.
 *  The append direction is from MSB (most significant bit) to
 *  LSB (least significant bit). If necessary additional bytes are
 *  added to ''outBitStream''.
 *   # Stream data:  "\2#01011000;"  and  bitPos = 5
 *   #                        ^
 *   #                     current
 *   #                    position
 *   putBitsMsb(stri, bitPos, 2#10011, 5);
 *   # Stream data:  "\2#01011100;\2#11000000;"  and  bitPos = 2
 *   #                        100    11
 *   #                    appended  appended
 *   #                 higher bits  lower bits
 *  @param outBitStream Bit stream to which the bits are appended.
 *  @param bits Bits to be appended to ''outBitStream''.
 *  @param bitWidth Number of bits to be appended (width of ''bits'').
 *)
const proc: putBits (inout msbOutBitStream: outBitStream, in integer: bits,
    in integer: bitWidth) is func
  local
    var integer: bitShift is 0;
  begin
    outBitStream.buffer <<:= bitWidth;
    outBitStream.buffer +:= bits;
    outBitStream.bitSize +:= bitWidth;
    if outBitStream.bitSize >= 8 then
      bitShift := outBitStream.bitSize;
      repeat
	bitShift -:= 8;
        outBitStream.byteString &:= char((outBitStream.buffer >> bitShift) mod 256);
      until bitShift < 8;
      outBitStream.bitSize := bitShift;
      outBitStream.buffer := outBitStream.buffer mod 2 ** bitShift;
    end if;
  end func;


(**
 *  Obtain the length of the given ''outBitStream''.
 *  The bit stream length is measured in bits.
 *  @param outBitStream Bit stream from which the length is obtained.
 *  @return the length of the bit stream.
 *)
const func integer: length (in msbOutBitStream: outBitStream) is
  return length(outBitStream.byteString) * 8 + outBitStream.bitSize;


(**
 *  Truncate ''outBitStream'' to the given ''length''.
 *  If the bit stream previously was larger than ''length'', the extra data is lost.
 *  If the bit stream previously was shorter, it is extended, and the extended
 *  part is filled with zero bits.
 *  @param outBitStream Bit stream to be truncated.
 *  @param length Requested length of ''outBitStream'' in bits.
 *  @exception RANGE_ERROR The requested length is negative.
 *)
const proc: truncate (inout msbOutBitStream: outBitStream, in integer: length) is func
  local
    var integer: bytePos is 0;
    var integer: bitSize is 0;
  begin
    if length < 0 then
      raise RANGE_ERROR;
    else
      bytePos := length mdiv 8;
      bitSize := length mod 8;
      if bytePos < length(outBitStream.byteString) then
        outBitStream.buffer := ord(outBitStream.byteString[succ(bytePos)]) >> (8 - bitSize);
        outBitStream.byteString := outBitStream.byteString[.. bytePos];
      elsif bytePos = length(outBitStream.byteString) then
        if bitSize < outBitStream.bitSize then
          outBitStream.buffer >>:= outBitStream.bitSize - bitSize;
        elsif bitSize > outBitStream.bitSize then
          outBitStream.buffer <<:= bitSize - outBitStream.bitSize;
        end if;
      else
        outBitStream.byteString &:= char(outBitStream.buffer << (8 - outBitStream.bitSize));
        outBitStream.byteString &:= "\0;" mult bytePos - length(outBitStream.byteString);
        outBitStream.buffer := 0;
      end if;
      outBitStream.bitSize := bitSize;
    end if;
  end func;


(**
 *  Complete a partially filled byte and add it to the byte string.
 *  If ''outBitStream'' has a partially filled byte it is filled with zero
 *  bits and added to the byte string. If ''outBitStream'' has not a
 *  partially filled byte nothing is done.
 *  @param outBitStream Bit stream where the partially filled byte is added.
 *)
const proc: flush (inout msbOutBitStream: outBitStream) is func
  begin
    if outBitStream.bitSize <> 0 then
      outBitStream.byteString &:= char(outBitStream.buffer << (8 - outBitStream.bitSize));
      outBitStream.bitSize := 0;
    end if;
    outBitStream.buffer := 0;
  end func;


(**
 *  Obtain the byte string created from the bits written to ''outBitStream''.
 *  The returned byte string is removed from ''outBitStream''.
 *  A partially filled byte is not part of the returned byte string.
 *  The function flush() can be called in advance to add a
 *  partially filled byte to the byte string.
 *  @param outBitStream Bit stream from which the byte string is obtained.
 *  @return a string of completely filled bytes from ''outBitStream''.
 *)
const func string: getBytes (inout msbOutBitStream: outBitStream) is func
  result
    var string: bytes is "";
  begin
    bytes := outBitStream.byteString;
    outBitStream.byteString := "";
  end func;


(**
 *  Add the given string ''stri'' to the byte string of ''outBitStream''.
 *  The ''outBitStream'' is flushed before adding ''stri''.
 *  @param outBitStream Bit stream to which ''stri'' is added.
 *  @param stri String to be added to ''outBitStream''.
 *)
const proc: write (inout msbOutBitStream: outBitStream, in string: stri) is func
  begin
    flush(outBitStream);
    outBitStream.byteString &:= stri;
  end func;


# The function putBitLsb(string) is deprecated. Use putBit(lsbOutBitStream) instead.
const proc: putBitLsb (inout string: stri, inout integer: bitPos, in integer: bit) is func
  begin
    if bitPos = 0 then
      stri &:= chr(bit);
      bitPos := 1;
    else
      stri @:= [length(stri)] chr(ord(stri[length(stri)]) + (bit << bitPos));
      bitPos := succ(bitPos) mod 8;
    end if;
  end func;


# The function putBitsLsb(string) is deprecated. Use putBits(lsbOutBitStream) instead.
const proc: putBitsLsb (inout string: stri, inout integer: bitPos, in var integer: bits,
    in var integer: bitWidth) is func
  local
    var integer: bitsFree is 0;
  begin
    bitsFree := 8 - bitPos;
    if bitsFree > bitWidth then
      # |---------8 bits---------|
      # | |--bitWidth---|-bitPos-|
      # |---bitsFree----|        |
      if bitPos = 0 then
        stri &:= chr(bits << bitPos);
      else
        stri @:= [length(stri)] chr(ord(stri[length(stri)]) + (bits << bitPos));
      end if;
      bitPos +:= bitWidth;
    else
      #   |---------8 bits---------|
      # ----bitWidth------|-bitPos-|
      #   |---bitsFree----|        |
      if bitPos <> 0 then
        stri @:= [length(stri)] chr(ord(stri[length(stri)]) + ((bits mod (1 << bitsFree)) << bitPos));
        bits >>:= bitsFree;
        bitWidth -:= bitsFree;
      end if;
      while bitWidth >= 8 do
        stri &:= chr(bits mod 256);
        bits >>:= 8;
        bitWidth -:= 8;
      end while;
      if bitWidth >= 1 then
        stri &:= chr(bits);
        bitPos := bitWidth;
      else
        bitPos := 0;
      end if;
    end if;
  end func;


# The function putBitMsb(string) is deprecated. Use putBit(msbOutBitStream) instead.
const proc: putBitMsb (inout string: stri, inout integer: bitPos, in integer: bit) is func
  begin
    if bitPos = 0 then
      stri &:= chr(bit << 7);
      bitPos := 1;
    else
      stri @:= [length(stri)] chr(ord(stri[length(stri)]) + (bit << (7 - bitPos)));
      bitPos := succ(bitPos) mod 8;
    end if;
  end func;


# The function putBitsMsb(string) is deprecated. Use putBits(msbOutBitStream) instead.
const proc: putBitsMsb (inout string: stri, inout integer: bitPos, in var integer: bits,
    in var integer: bitWidth) is func
  local
    var integer: bitsFree is 0;
  begin
    bitsFree := 8 - bitPos;
    if bitsFree > bitWidth then
      # |---------8 bits---------|
      # |-bitPos-|--bitWidth---| |
      # |        |---bitsFree----|
      if bitPos = 0 then
        stri &:= chr(bits << (bitsFree - bitWidth));
      else
        stri @:= [length(stri)] chr(ord(stri[length(stri)]) + (bits << (bitsFree - bitWidth)));
      end if;
      bitPos +:= bitWidth;
    else
      # |---------8 bits---------|
      # |-bitPos-|----bitWidth------
      # |        |---bitsFree----|
      if bitPos <> 0 then
        bitWidth -:= bitsFree;
        stri @:= [length(stri)] chr(ord(stri[length(stri)]) + (bits >> bitWidth));
        bits := bits mod (1 << bitWidth);
      end if;
      while bitWidth >= 8 do
        bitWidth -:= 8;
        stri &:= chr(bits >> bitWidth);
        bits := bits mod (1 << bitWidth);
      end while;
      if bitWidth >= 1 then
        stri &:= chr(bits << (8 - bitWidth));
        bitPos := bitWidth;
      else
        bitPos := 0;
      end if;
    end if;
  end func;


# The function getBitLsb(file) is deprecated. Use getBit(lsbInBitStream) instead.
const func integer: getBitLsb (inout file: inFile, inout integer: bitPos) is func
  result
    var integer: resultBit is 0;
  begin
    if bitPos = 8 then
      inFile.bufferChar := getc(inFile);
      resultBit := ord(inFile.bufferChar) mod 2;
      bitPos := 1;
    else
      resultBit := (ord(inFile.bufferChar) >> bitPos) mod 2;
      incr(bitPos);
    end if;
  end func;


# The function getBitsLsb(file) is deprecated. Use getBits(lsbInBitStream) instead.
const func integer: getBitsLsb (inout file: inFile, inout integer: bitPos,
    in var integer: bitWidth) is func
  result
    var integer: resultBits is 0;
  local
    var integer: bitsInByte is 0;
    var integer: bitsInResult is 0;
  begin
    if bitPos = 8 then
      bitPos := 0;
      inFile.bufferChar := getc(inFile);
    end if;
    bitsInByte := 8 - bitPos;
    if bitsInByte >= bitWidth then
      resultBits := (ord(inFile.bufferChar) >> bitPos) mod (1 << bitWidth);
      bitPos +:= bitWidth;
    else
      resultBits := ord(inFile.bufferChar) mod 256 >> bitPos;
      inFile.bufferChar := getc(inFile);
      bitWidth -:= bitsInByte;
      bitsInResult := bitsInByte;
      while bitWidth > 8 do
        resultBits +:= ord(inFile.bufferChar) << bitsInResult;
        inFile.bufferChar := getc(inFile);
        bitWidth -:= 8;
        bitsInResult +:= 8;
      end while;
      resultBits +:= ord(inFile.bufferChar) mod (1 << bitWidth) << bitsInResult;
      bitPos := bitWidth;
    end if;
  end func;


# The function putBitLsb(file) is deprecated. Use putBit(lsbOutBitStream) instead.
const proc: putBitLsb (inout file: outFile, inout integer: bitPos, in integer: bit) is func
  begin
    if bitPos = 7 then
      write(outFile, chr(ord(outFile.bufferChar) + (bit << bitPos)));
      outFile.bufferChar := '\0;';
      bitPos := 0;
    else
      outFile.bufferChar := chr(ord(outFile.bufferChar) + (bit << bitPos));
      incr(bitPos);
    end if;
  end func;


# The function putBitsLsb(file) is deprecated. Use putBits(lsbOutBitStream) instead.
const proc: putBitsLsb (inout file: outFile, inout integer: bitPos, in var integer: bits,
    in var integer: bitWidth) is func
  local
    var integer: bitsFree is 0;
  begin
    bitsFree := 8 - bitPos;
    if bitsFree > bitWidth then
      outFile.bufferChar := chr(ord(outFile.bufferChar) + (bits << bitPos));
      bitPos +:= bitWidth;
    else
      write(outFile, chr(ord(outFile.bufferChar) + ((bits mod (1 << bitsFree)) << bitPos)));
      bits >>:= bitsFree;
      bitWidth -:= bitsFree;
      while bitWidth >= 8 do
        write(outFile, chr(bits mod 256));
        bits >>:= 8;
        bitWidth -:= 8;
      end while;
      if bitWidth >= 1 then
        outFile.bufferChar := chr(bits);
        bitPos := bitWidth;
      else
        outFile.bufferChar := '\0;';
        bitPos := 0;
      end if;
    end if;
  end func;


# The function getBitMsb(file) is deprecated. Use getBit(msbInBitStream) instead.
const func integer: getBitMsb (inout file: inFile, inout integer: bitPos) is func
  result
    var integer: resultBit is 0;
  begin
    if bitPos = 8 then
      inFile.bufferChar := getc(inFile);
      resultBit := (ord(inFile.bufferChar) >> 7) mod 2;
      bitPos := 1;
    else
      resultBit := (ord(inFile.bufferChar) >> (7 - bitPos)) mod 2;
      incr(bitPos);
    end if;
  end func;


# The function getBitsMsb(file) is deprecated. Use getBits(msbInBitStream) instead.
const func integer: getBitsMsb (inout file: inFile, inout integer: bitPos,
    in var integer: bitWidth) is func
  result
    var integer: resultBits is 0;
  local
    var integer: bitsInByte is 0;
  begin
    if bitPos = 8 then
      bitPos := 0;
      inFile.bufferChar := getc(inFile);
    end if;
    bitsInByte := 8 - bitPos;
    if bitsInByte >= bitWidth then
      resultBits := (ord(inFile.bufferChar) >> (bitsInByte - bitWidth)) mod (1 << bitWidth);
      bitPos +:= bitWidth;
    else
      resultBits := ord(inFile.bufferChar) mod (1 << bitsInByte);
      inFile.bufferChar := getc(inFile);
      bitWidth -:= bitsInByte;
      while bitWidth > 8 do
        resultBits <<:= 8;
        resultBits +:= ord(inFile.bufferChar);
        inFile.bufferChar := getc(inFile);
        bitWidth -:= 8;
      end while;
      resultBits <<:= bitWidth;
      resultBits +:= (ord(inFile.bufferChar) >> (8 - bitWidth));
      bitPos := bitWidth;
    end if;
  end func;


# The function putBitMsb(file) is deprecated. Use putBit(msbOutBitStream) instead.
const proc: putBitMsb (inout file: outFile, inout integer: bitPos, in integer: bit) is func
  begin
    if bitPos = 7 then
      write(outFile, chr(ord(outFile.bufferChar) + bit));
      outFile.bufferChar := '\0;';
      bitPos := 0;
    else
      outFile.bufferChar := chr(ord(outFile.bufferChar) + (bit << (7 - bitPos)));
      incr(bitPos);
    end if;
  end func;


# The function putBitsMsb(file) is deprecated. Use putBits(msbOutBitStream) instead.
const proc: putBitsMsb (inout file: outFile, inout integer: bitPos, in var integer: bits,
    in var integer: bitWidth) is func
  local
    var integer: bitsFree is 0;
  begin
    bitsFree := 8 - bitPos;
    if bitsFree > bitWidth then
      outFile.bufferChar := chr(ord(outFile.bufferChar) + (bits << (bitsFree - bitWidth)));
      bitPos +:= bitWidth;
    else
      bitWidth -:= bitsFree;
      write(outFile, chr(ord(outFile.bufferChar) + (bits >> bitWidth)));
      bits := bits mod (1 << bitWidth);
      while bitWidth >= 8 do
        bitWidth -:= 8;
        write(outFile, chr(bits >> bitWidth));
        bits := bits mod (1 << bitWidth);
      end while;
      if bitWidth >= 1 then
        outFile.bufferChar := chr(bits << (8 - bitWidth));
        bitPos := bitWidth;
      else
        outFile.bufferChar := '\0;';
        bitPos := 0;
      end if;
    end if;
  end func;


(**
 *  Type describing a stream of bits that is read backwards.
 *  The bits are read from the most significant bit of the last byte
 *  to the least significant bit of the first byte.
 *)
const type: reverseBitStream is new struct
    var string: data is "";
    var integer: offset is 0;
  end struct;


(**
 *  Create a reverse bit stream from ''length'' bytes read from ''inFile''.
 *)
const func reverseBitStream: reverseBitStream (inout file: inFile, in integer: length) is func
  result
    var reverseBitStream: inBitStream is reverseBitStream.value;
  begin
    inBitStream.data := gets(inFile, length);
    inBitStream.offset := pred(length(inBitStream.data) * 8);
  end func;


(**
 *  Return the number of bits still present in the given reverse ''inBitStream''.
 *  Note that it is possible to read beyond the end fo the stream. In this
 *  case negative values are returned.
 *)
const func integer: bitsStillInStream (in reverseBitStream: inBitStream) is
    return succ(inBitStream.offset);


(**
 *  Return the number of bits read from the given reverse ''inBitStream''.
 *  Note that it is possible to read beyond the end fo the stream.
 *  So the function might return more bits than actually present.
 *)
const func integer: bitsRead (in reverseBitStream: inBitStream) is
    return pred(length(inBitStream.data) * 8) - inBitStream.offset;


(**
 *  Get ''bitWidth'' bits from the given reverse ''inBitStream''.
 *  The bits are read from the most significant bit of the last byte
 *  to the least significant bit of the first byte.
 *  It is possible to read beyond the end of the stream.
 *  In this case the stream is assumed to consist of zero bytes.
 *)
const func integer: getBits (inout reverseBitStream: inBitStream, in integer: bitWidth) is func
  result
    var integer: resultBits is 0;
  local
    var integer: indexOfHighestByte is 0;
    var integer: bitsLeftInHighestByte is 0;
    var integer: keepBitsInHighestByte is 0;
    var integer: valueFromHighestByte is 0;
    var integer: spanningFullBytes is 0;
    var integer: bitsFromLowestByte is 0;
    var integer: indexOfLowestByte is 0;
    var integer: startIndex is 0;
    var integer: index is 0;
  begin
    if bitWidth <> 0 then
      if inBitStream.offset >= 0 then
        indexOfHighestByte    := succ(inBitStream.offset mdiv 8);
        bitsLeftInHighestByte := succ(inBitStream.offset mod 8);

        if bitWidth < bitsLeftInHighestByte then
          # Can satisfy with bits from the highest byte
          keepBitsInHighestByte := bitsLeftInHighestByte - bitWidth;  # Number of bits that are preserved.
          resultBits := (ord(inBitStream.data[indexOfHighestByte]) >> keepBitsInHighestByte) mod (1 << bitWidth);
        else
          # take bits from highest byte
          valueFromHighestByte := ord(inBitStream.data[indexOfHighestByte]) mod (1 << bitsLeftInHighestByte);
          if bitWidth = bitsLeftInHighestByte then
            # Can satisfy with bits from the highest byte
            resultBits := valueFromHighestByte;
          else
            spanningFullBytes  := (bitWidth - bitsLeftInHighestByte) mdiv 8;
            bitsFromLowestByte := (bitWidth - bitsLeftInHighestByte) mod 8;

            indexOfLowestByte := pred(indexOfHighestByte - spanningFullBytes);
            if indexOfLowestByte >= 1 then
              resultBits := ord(inBitStream.data[indexOfLowestByte]) >> (8 - bitsFromLowestByte);
            else
              # We assume that below the offset 0 there are zero bytes.
              startIndex := -indexOfLowestByte;
            end if;

            for index range startIndex to pred(spanningFullBytes) do
              resultBits +:= ord(inBitStream.data[succ(indexOfLowestByte) + index]) << (index * 8 + bitsFromLowestByte);
            end for;

            resultBits +:= valueFromHighestByte << (spanningFullBytes * 8 + bitsFromLowestByte);
          end if;
        end if;
      end if;
      # Update offset even if we are beyond the end of the stream.
      inBitStream.offset -:= bitWidth;
    end if;
  end func;