gif-code / deCompression.ts

/**
 * 
 * This file holds the components needed to compress and decompress gif image data.
 * Main components are the Compressor and Decompressors classes who offer the methods to compress or decompress data according to the LZW algorithm that gifs use.
 *  
 */


/**
 * Special case of TrieNodes that do not have children. Making for a reversed Trie like structure where one only knows the parents.
 * Used by the {@link Decompressor}
 */
class ChildlessTrieNode {
  public nodeValue: number;
  public parent: ChildlessTrieNode | undefined;

  constructor(code: number) {
    this.nodeValue = code;
  }

  /**
   * Returns the sequence of codevalues from thge path of the root to this node
   * @param includeRoot indicates if the root's node value should be included in the sequence. Default is false
   */
  resolveTrieToSequence(includeRoot = false): Array<number> {
    if (this.parent == undefined) {
      if (includeRoot) {
        return [this.nodeValue];
      }
      return [];
    }

    const sequence = [this.nodeValue];
    let node = this.parent;
    while (node.parent) {
      sequence.push(node.nodeValue);
      node = node.parent;
    }

    if (includeRoot) {
      sequence.push(node.nodeValue);
    };

    sequence.reverse();
    return sequence;
  }

}


/**
 * Class for a simple Trie data structure. Each node can have a parent and as many children as needed.
 * Used by the {@link Compressor}
 */
class TrieNode {
  public codeValue: number;
  public parent?: TrieNode;
  public children: TrieNode[];

  constructor(code: number) {
    this.codeValue = code;
    this.children = new Array();
  }

  addChild(child: TrieNode, pos: number) {
    this.children[pos] = child;
  }

  /**
   * Method to recursively eliminate all parent links. Maybe not needed in JS, but here for memory reasons back from ther C++ port.
   */
  orphanator() {
    this.parent = undefined;
    this.children.forEach(element => { element?.orphanator(); });
  }

}


/**
 * Decompressor for GIF images.
 * Offers methods to either decompress table based image data directly, or general gif lzw compressed data 
 */
class Decompressor {
  private dicitionaryBase: Array<ChildlessTrieNode>; // basic array, holding only TrieNodes for our base cases
  private reverseCodeMap: Map<number, ChildlessTrieNode>; //resolves codevalues to nodes in the subtrees
  private unpacker: UnpackingBench; // gives access to the formerly packed codes
  private MAXCODESIZE = 12; // for gifs this should be 12
  private nextCodenumber = 0; //next codenumber to be put into the codemap
  private codesize = 0; // how many bits do we currently use per code?
  private resetCode = 0; // special code for "ups we need to reset the dictionary because we run out of space". Is set to amount of colors +1
  private endOfDataCode = 0; // special code for end of data. Is set to amount of colors +2
  private minimumlzwCodeLenght = 0; // smallest amount of bits needed to read a code, obtained from the tbid

  constructor() {
    this.dicitionaryBase = new Array();
    this.unpacker = new UnpackingBench();
    this.reverseCodeMap = new Map();
  }

  /**
   * Decompress method that takes care of reading the min code lenght and pulling all that delicious data out of its wrapper
   */
  decompressTableBasedImageData(tbid: TableBasedImageData) {
    return this.decompress(tbid.getImageData(), tbid.LZWMinimumCodeSize());
  }

  /**
   * sets the amount of bits needed to represent the amount of base symbols (i.e. at least the amount of colors) before decompressing a datastream
   */
  private setMinimumlzwCodeLenght(minimumlzwCodeLenght: number) {
    this.minimumlzwCodeLenght = minimumlzwCodeLenght;
  }

  /**
   * Main method to decompress data that was compressed with the gif lzw variant.
   * For Table Based Image Data use the {@link decompressTableBasedImageData} method
   * @param compressedData compressed data that should be decompressed
   * @param minCodeLenght The amount of bits needed to represent the number of base symbols used. (i.e. the amount of colors in a gif image)
   * @returns Array of decompressed symbols
   */
  decompress(compressedData: Array<number>, minCodeLenght: number): Array<number> {
    this.setMinimumlzwCodeLenght(minCodeLenght);
    this.prepareBaseValues();
    this.resetcodemap();
    this.unpacker.loadPackeData(compressedData);

    const indexStream = []; // will later contain the output

    let prevCode = this.unpacker.getNextCode();

    while (prevCode == this.resetCode && !this.unpacker.nextCodeEmpty) {
      prevCode = this.unpacker.getNextCode();
    }

    if (prevCode == this.endOfDataCode) {
      console.log("empty data")
      return [];
    }

    indexStream.push(prevCode); // first "normal" code is always just a direct symbol

    while (!this.unpacker.nextCodeEmpty) {
      let nextCode = this.unpacker.getNextCode();
      if (nextCode == this.endOfDataCode) {
        break;
      }

      if (nextCode == this.resetCode) {
        this.resetcodemap();
        prevCode = this.unpacker.getNextCode();
        while (prevCode == this.resetCode && !this.unpacker.nextCodeEmpty) {
          prevCode = this.unpacker.getNextCode();
        }

        if (nextCode == this.endOfDataCode) {
          console.log("EOD code encountered directly after a reset " + this.unpacker.packedData.length); // good for debugging and later checks for not well formed data
          break;
        }
        // no lookup needed because we have reset the codemap.
        indexStream.push(prevCode);
        continue;

      } else {
        //prevcode is already in our dictionary but for debubbing purposes we still check
        if (!this.reverseCodeMap.get(prevCode)) {
          throw new Error(" An Error occured. A code was encountered that should have been known but it was not. " + prevCode + " " + nextCode + " " + this.nextCodenumber)
        }
        const newCodeSeq = Array.from(this.reverseCodeMap.get(prevCode)!.resolveTrieToSequence(true));

        //two cases for if we already know the code or not
        if (this.reverseCodeMap.has(nextCode)) {
          const t = this.reverseCodeMap.get(nextCode)!.resolveTrieToSequence(true)
          indexStream.push(...t);
          newCodeSeq.push(t[0]);
        } else {
          newCodeSeq.push(newCodeSeq[0]);
          indexStream.push(...newCodeSeq);
        }

        //handling of codesize increase
        if (this.nextCodenumber >= ((1 << this.codesize) - 1)) {
          if (this.codesize == this.MAXCODESIZE) {
            //not elegant but it allows us to add the last possible codenumber (2^12-1) without accidents
            if (this.nextCodenumber != ((1 << this.codesize) - 1)) {
              prevCode = nextCode;
              // we are not allowing any bigger codenumbers so adding anything new to the codemap makes nos ense.
              continue;
            }
          } else {
            this.codesize++;
            this.unpacker.setCurrentCodeSize(this.codesize);
          }
        }

        //add new codesequence to the Trie and reverse map
        const position = newCodeSeq[newCodeSeq.length - 1];
        const newNode = new ChildlessTrieNode(position);
        newNode.parent = this.reverseCodeMap.get(prevCode)!;
        this.reverseCodeMap.set(this.nextCodenumber, newNode);

        this.nextCodenumber++;
        prevCode = nextCode;
      }
    }

    //cleanup
    this.tearDown()

    return indexStream;
  }

  /**
   * sets some values at the start of decompression which will never change during decompression
   */
  private prepareBaseValues() {
    this.resetCode = 1 << this.minimumlzwCodeLenght;
    this.endOfDataCode = this.resetCode + 1;
    this.nextCodenumber = this.endOfDataCode + 1;
    for (let i = 0; i < this.resetCode; i++) {
      const node = new ChildlessTrieNode(i);
      this.dicitionaryBase[i] = node;
    }
  }

  /** 
   * Helper function which resets the dicitonary to only the base cases and resets the codesize. 
  */
  private resetcodemap() {
    // clear gets rid of all non-base nodes because references are only kept via map
    this.reverseCodeMap.clear()
    this.nextCodenumber = this.endOfDataCode + 1;
    this.codesize = this.minimumlzwCodeLenght + 1;

    for (let i = 0; i < this.resetCode; i++) {
      // a bit dumb but else we can't really point to our base symbols in the structure
      this.reverseCodeMap.set(i, this.dicitionaryBase[i]);
    }

    this.unpacker.setCurrentCodeSize(this.codesize);
  }

  /**
   * cleans up the state after decompression
   */
  private tearDown() {
    this.dicitionaryBase = new Array();
    this.unpacker = new UnpackingBench();
    this.reverseCodeMap = new Map();
  }

}


/**
 * Compressor for GIF images.
 * Offers methods to compress data into a new table based image data directly, or to do basic compression 
 */
class Compressor {
  private dicitonaryroot: TrieNode; // basis of our Trie
  private currCodeMapPos: TrieNode; //instead of a temporary buffer we simply store where in the Trie we are
  private packer: PackingBench; // takes care of bit packing the compressed data
  private MAXCODESIZE = 12; // for gifs this should be 12
  private nextCodenumber = 0; //next codenumber to be put into the codemap. On reset it is 2**initial codesize + 1
  private codesize = 0; // how many bits do we currently use per code.
  private resetCode = 0; // special code for "ups we need to reset the dictionary because we run out of space". Is set to 2**initial codesize
  private endOfDataCode = 0; // special code for end of data. Is set to 2**initial codesize + 2
  private minLZWCodeSize = 0; //minimal amount of bits needed to represent the number of colors. Codes for packing compressed data will use one more bit. At least 2, at most MaxCodesize

  constructor() {
    this.dicitonaryroot = new TrieNode(0);
    this.currCodeMapPos = this.dicitonaryroot;
    this.packer = new PackingBench();
  }

  /**
   * Resets the dicitonary and codesize
   */
  private resetcodemap() {
    //this.dicitonaryroot.orphanator(); //trades a bit of speed for sooner cleanup
    this.dicitonaryroot = new TrieNode(0);

    this.nextCodenumber = this.endOfDataCode + 1;

    for (let i = 0; i < this.resetCode; i++) {
      this.dicitonaryroot.addChild(new TrieNode(i), i);
    }

    this.currCodeMapPos = this.dicitonaryroot;

    this.codesize = this.minLZWCodeSize + 1; // the least amount of bits needed to store the next number in the codemap
    this.packer.setCurrentCodeSize(this.codesize);
  }

  /**
   * Main part of the compression. Adds symbols into a Trie to walk and build up the compüression dictionary. 
   * Adds the corresponding compression numbers to the packer whenever needed.
   * @param symbol next symbol to be added to the compression
   * @returns true if compression took place, else false  (equivalent to the question if the newly added symbol lead to a new dicitonary entry or not)
   */
  private addSymbolToCompressor(symbol: number): boolean {

    // no actual compression needs to take place because we are not at a leaf of the Trie
    if (this.currCodeMapPos.children[symbol] != undefined) {
      this.currCodeMapPos = this.currCodeMapPos.children[symbol];
      return false;
    }

    this.packer.addCode(this.currCodeMapPos.codeValue);

    // increase codesize if needed. And reset if codesize gets above 12
    if (this.nextCodenumber >= (1 << this.codesize)) {
      if (this.codesize == this.MAXCODESIZE) {
        // We could add a locked flag to allow the compressor to decide if the codemap should simply stop growing and be kept for some time longer
        this.packer.addCode(this.resetCode);
        this.resetcodemap();
        // no code added to our map cause we start fresh next round
      } else {
        this.codesize++;
        this.currCodeMapPos.addChild(new TrieNode(this.nextCodenumber), symbol)
        this.nextCodenumber++;
      }
      this.packer.setCurrentCodeSize(this.codesize);
    } else {
      this.currCodeMapPos.addChild(new TrieNode(this.nextCodenumber), symbol)
      this.nextCodenumber++;
    }

    this.currCodeMapPos = this.dicitonaryroot.children[symbol];

    return true;

  }

  /**
   * Ends the compression by adding  whatever is left uncompressed to the packer,a dding a end of data code, and then returning the compressed data
   * @returns The compressed data
   */
  private endCompression(): Array<number> {
    if (this.currCodeMapPos != this.dicitonaryroot) {
      this.packer.addCode(this.currCodeMapPos.codeValue);
    }

    this.packer.addCode(this.endOfDataCode);
    const packedData = this.packer.endPacking();
    return packedData;
  }

  /**
   * Compresses a given sequence of indecies according to the gif augmented version of the LZW algortihm.
   * @param indexes An array of indecies for a gif image. Entries need to be less than 2^minCodeSize (for example [0-255] for a minCodeSize of 8)
   * @param minCodeSize At least the amount of bits needed to represent the highest given index. For gifs this value has to be between 2 and 12, and should correspond to the size of the associated colortable
   * @returns The compressed gif image data
   */
  compress(indexes: number[], minCodeSize: number): Array<number> {
    this.setUp(minCodeSize)
    this.packer.addCode(this.resetCode);
    for (let index of indexes) {
      this.addSymbolToCompressor(index)
    }
    const compressedData = this.endCompression();
    this.tearDown()
    return compressedData
  }

  /**
   * Same as {@link compress} but returns a ready to use TableBasedImageData object
   * @returns TableBasedImageData which can be used as gifblock
   */
  compressToTableBasedImageData(indexes: number[], minCodeSize: number) {
    const compressed = this.compress(indexes, minCodeSize)
    return new TableBasedImageData({ lzwMinSize: minCodeSize, imageData: compressed })
  }

  /**
   * Sets some values that will not change during compression
   */
  private setUp(minCodeSize: number) {
    this.minLZWCodeSize = minCodeSize
    this.resetCode = 1 << this.minLZWCodeSize;
    this.endOfDataCode = this.resetCode + 1;
    this.resetcodemap()
  }

  /**
   * cleans the satte after compression
   */
  private tearDown() {
    this.dicitonaryroot = new TrieNode(0);
    this.currCodeMapPos = this.dicitonaryroot;
    this.packer = new PackingBench();
  }

}


/** 
 * Allows packing codes into one long sequence of bytes
 * Code sizes for packing should be set by the user (like the compressor) to enter the right data.
 */
class PackingBench {
  private packedData: number[] = [];
  private currentBit: number = 0; // bit-position on the workbench
  private workbench: number = 0; // we use 16 bit to prepare data for packing.
  private currentCodeSize: number = 8; //how many bits the added codes should take up

  static masks: number[] = [
    0x0, 0x1, 0x3, 0x7, 0xF, 0x1F, 0x3F, 0x7F,
    0xFF, 0x1FF, 0x3FF, 0x7FF, 0xFFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF
  ];

  setCurrentCodeSize(codeSize: number) {
    this.currentCodeSize = codeSize;
  }

  /**
   * Puts the next code onto the bench. It will be packed with the current codesize. Code must not be larger than the current codesize allows. 
   * @param value code to be added.
   */
  addCode(value: number): void {
    // if we go above the lenght of our workbench we put as much on it as we can before storing the packed data and adding the rest to a fresh workbench
    if ((this.currentBit + this.currentCodeSize) > 16) {
      const temp = (value << this.currentBit);
      this.workbench = this.workbench | temp;

      const t1 = (this.workbench >> 8) & PackingBench.masks[8];
      const t2 = PackingBench.masks[8] & this.workbench;

      this.packedData.push(t2);
      this.packedData.push(t1);

      this.workbench = (value >> (16 - this.currentBit));
      this.currentBit = (this.currentBit + this.currentCodeSize) - 16;

    } else {
      const temp = (value << this.currentBit);
      this.workbench = this.workbench | temp;
      this.currentBit = this.currentBit + this.currentCodeSize;
    }
  }

  /**
   * Ends the packing process. If there is still unpacked data it will be packed and the end padded with 0s.
   * Also resets the state so new packing can be started
   * @returns the packed data
   */
  endPacking(): Array<number> {
    // flush whatever is left on the workbench into packedData
    if (this.currentBit != 0) {
      if (this.currentBit <= 8) {
        const t1 = ((this.workbench & PackingBench.masks[8]));
        this.packedData.push(t1);
      } else {
        const t1 = (this.workbench >> 8) & PackingBench.masks[8];
        const t2 = PackingBench.masks[8] & this.workbench;
        this.packedData.push(t2);
        this.packedData.push(t1);
      }
    }
    // shallow copy because we reset the original
    const tmpArr = Object.assign([], this.packedData);
    this.reset();

    return tmpArr
  }

  /**
   * resets the state to some default values
   */
  private reset(): void {
    this.packedData = [];
    this.currentBit = 0;
    this.workbench = 0;
    this.currentCodeSize = 8;
  }

}


/**
 * Allows access to the prior packed codes in a compressed gif image.
 * Code sizes should be set by the user (like the decompressor) to get the right data.
 */
class UnpackingBench {
  public packedData: Array<number> = []; //unlike in the cpp variant where we used a stack. Here we need to make sure the first byte is at the end like in a queue, because JS pop works like that -.-
  private currentBit: number = 0; // current position on the workbench
  private workbench: number = 0; // 16 bit buffer to load and read from
  private currentCodeSize: number = 8; //size of codes to be read
  public nextCodeEmpty = true;

  static masks: number[] = [
    0x0, 0x1, 0x3, 0x7, 0xF, 0x1F, 0x3F, 0x7F,
    0xFF, 0x1FF, 0x3FF, 0x7FF, 0xFFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF
  ];

  /**
   * Sets the size of codes that should be returned. 
   * @param codeSize 
   */
  setCurrentCodeSize(codeSize: number) {
    this.currentCodeSize = codeSize;
  }

  /**
   * resets the inner state of the UnpackingBench. Should be called before it is reused.
   */
  reset(): void {
    this.packedData = [];
    this.currentBit = 0;
    this.workbench = 0;
    this.currentCodeSize = 8;
    this.nextCodeEmpty = true;
  }

  /**
   * Load data into the unpacker. Note:The first byte to read has to be the last in the array because we use pop
   * @param data packed data to be loaded
   */
  loadPackeData(data: Array<number>) {
    if (data.length != 0) {
      this.packedData = Array.from(data);
      this.packedData.reverse();
      this.nextCodeEmpty = false;

      // already preload data onto workbench
      this.workbench = this.packedData.pop()!;
      if (this.packedData.length != 0) {
        this.workbench = this.workbench | (this.packedData.pop()! << 8)
      }
    }
  }

  /**
   * Unpacks and returns the next code, using  the currently set code size 
   * @returns next code number from loaded packed data, or 0 if nextCodeEmpty is true
   */
  getNextCode(): number {

    if (this.nextCodeEmpty) {
      console.log("No more data");
      return 0;
    }
    // basically data will "fall" into the workbench from the left to the right whenever we fill up

    let output = 0;

    if (this.currentBit + this.currentCodeSize > 16) { // we need more data than is in the buffer so we grab some data from the stack to fill up

      let overhang = (this.currentBit + this.currentCodeSize) - 16;
      output = (this.workbench >> this.currentBit); //put the data that we do have on the bench into position, we fill the rest later
      this.workbench = this.packedData.pop()!; // refill the first 8 bit
      if (this.packedData.length !== 0) { // add another 8 bit if we can
        const tmp = this.packedData.pop()!; // can't be empty because we checked
        this.workbench = this.workbench | (tmp << 8); // refill the last 8 bit
      }

      if (this.packedData.length == 0) { // if we cannot load any more data at the current code size, we are official empty
        this.nextCodeEmpty = true;
      }

      // now add the rest to the output
      output = output | ((this.workbench & UnpackingBench.masks[overhang]) << (this.currentCodeSize - overhang));
      this.currentBit = overhang;

    } else {
      output = (this.workbench >> this.currentBit) & UnpackingBench.masks[this.currentCodeSize];
      this.currentBit = this.currentBit + this.currentCodeSize;

      if (this.packedData.length == 0 && this.currentBit + this.currentCodeSize > 16) { //special case where the next code is a overhang but we did not laod enough data before
        this.nextCodeEmpty = true;
      }

    }

    return output;
  }

}