<commit_before>//
//  Deflate.swift
//  SWCompression
//
//  Created by <NAME> on 23.10.16.
//  Copyright © 2016 <NAME>. All rights reserved.
//

import Foundation

// TODO: Rename HuffmanTableError to HuffmanTreeError.
/**
 Error happened during deflate decompression. 
 It may indicate that either the data is damaged or it might not be compressed with DEFLATE at all.
 
 - `WrongBlockLengths`: `length` and `nlength` bytes of uncompressed block were not compatible.
 - `HuffmanTableError`: either error occured while parsing bytes related to Huffman coding or
    problem is happened during various calculations of Huffman coding.
 - `UnknownBlockType`: block type was 3, which is unknown block type.
 */
public enum DeflateError: Error {
    /// Uncompressed block' `length` and `nlength` bytes were not compatible.
    case WrongBlockLengths
    /// Either error occured while parsing bytes related to Huffman coding or problem is happened during various calculations of Huffman coding.
    case HuffmanTableError
    /// Block type was 3, which is unknown block type.
    case UnknownBlockType
}

/// Provides function to decompress data, which were compressed with DEFLATE
public class Deflate: DecompressionAlgorithm {

    /**
        Decompresses `compressedData` with DEFLATE algortihm.

        If data passed is not actually compressed with DEFLATE, `DeflateError` will be thrown.

     - Parameter compressedData: Data compressed with DEFLATE.
     
     - Throws: `DeflateError` if unexpected byte (bit) sequence was encountered in `compressedData`. 
        It may indicate that either the data is damaged or it might not be compressed with DEFLATE at all.

     - Returns: Decompressed data.
     */
    public static func decompress(compressedData data: Data) throws -> Data {
        /// Object with input data which supports convenient work with bit shifts.
        let pointerData = DataWithPointer(data: data, bitOrder: .reversed)
        return try decompress(pointerData: pointerData)
    }

    static func decompress(pointerData: DataWithPointer) throws -> Data {
        /// Object for storing output data
        var out: [UInt8] = []

        while true {
            /// Is this a last block?
            let isLastBit = pointerData.bit()
            /// Type of the current block.
            let blockType = [UInt8](pointerData.bits(count: 2).reversed())

            if blockType == [0, 0] { // Uncompressed block.
                pointerData.skipUntilNextByte()
                /// Length of the uncompressed data.
                let length = pointerData.intFromBits(count: 16)
                /// 1-complement of the length.
                let nlength = pointerData.intFromBits(count: 16)
                // Check if lengths are OK (nlength should be a 1-complement of length).
                // TODO: Rename WrongBlockLengths to WrongUncompressedBlockLengths (or something else)
                guard length & nlength == 0 else { throw DeflateError.WrongBlockLengths }
                // Process uncompressed data into the output
                // TODO: Replace precondition with guard and error throwing.
                precondition(pointerData.bitMask == 1, "Misaligned byte.")
                for _ in 0..<length {
                    out.append(pointerData.alignedByte())
                }
            } else if blockType == [1, 0] || blockType == [0, 1] {
                // Block with Huffman coding (either static or dynamic)

                // Declaration of Huffman tables which will be populated and used later.
                // There are two alphabets in use and each one needs a Huffman table.

                /// Huffman table for literal bytes.
                var mainLiterals: HuffmanTree
                /// Huffman table for bytes alphabet and alphabet of pairs (length, backward distance).
                var mainDistances: HuffmanTree

                if blockType == [0, 1] { // Static Huffman
                    // In this case codes for literals and distances are fixed.
                    // Bootstraps for tables (first element in pair is code, second is number of bits).
                    let staticHuffmanBootstrap = [[0, 8], [144, 9], [256, 7], [280, 8], [288, -1]]
                    let staticHuffmanLengthsBootstrap = [[0, 5], [32, -1]]
                    // Initialize tables from these bootstraps.
                    mainLiterals = HuffmanTree(bootstrap: staticHuffmanBootstrap)
                    mainDistances = HuffmanTree(bootstrap: staticHuffmanLengthsBootstrap)
                } else { // Dynamic Huffman
                    // In this case there are Huffman codes for two alphabets in data right after block header.<commit_msg>Uncompressed block now added to out a little bit more efficient.<commit_after>//
//  Deflate.swift
//  SWCompression
//
//  Created by <NAME> on 23.10.16.
//  Copyright © 2016 <NAME>. All rights reserved.
//

import Foundation

// TODO: Rename HuffmanTableError to HuffmanTreeError.
/**
 Error happened during deflate decompression. 
 It may indicate that either the data is damaged or it might not be compressed with DEFLATE at all.
 
 - `WrongBlockLengths`: `length` and `nlength` bytes of uncompressed block were not compatible.
 - `HuffmanTableError`: either error occured while parsing bytes related to Huffman coding or
    problem is happened during various calculations of Huffman coding.
 - `UnknownBlockType`: block type was 3, which is unknown block type.
 */
public enum DeflateError: Error {
    /// Uncompressed block' `length` and `nlength` bytes were not compatible.
    case WrongBlockLengths
    /// Either error occured while parsing bytes related to Huffman coding or problem is happened during various calculations of Huffman coding.
    case HuffmanTableError
    /// Block type was 3, which is unknown block type.
    case UnknownBlockType
}

/// Provides function to decompress data, which were compressed with DEFLATE
public class Deflate: DecompressionAlgorithm {

    /**
        Decompresses `compressedData` with DEFLATE algortihm.

        If data passed is not actually compressed with DEFLATE, `DeflateError` will be thrown.

     - Parameter compressedData: Data compressed with DEFLATE.
     
     - Throws: `DeflateError` if unexpected byte (bit) sequence was encountered in `compressedData`. 
        It may indicate that either the data is damaged or it might not be compressed with DEFLATE at all.

     - Returns: Decompressed data.
     */
    public static func decompress(compressedData data: Data) throws -> Data {
        /// Object with input data which supports convenient work with bit shifts.
        let pointerData = DataWithPointer(data: data, bitOrder: .reversed)
        return try decompress(pointerData: pointerData)
    }

    static func decompress(pointerData: DataWithPointer) throws -> Data {
        /// Object for storing output data
        var out: [UInt8] = []

        while true {
            /// Is this a last block?
            let isLastBit = pointerData.bit()
            /// Type of the current block.
            let blockType = [UInt8](pointerData.bits(count: 2).reversed())

            if blockType == [0, 0] { // Uncompressed block.
                pointerData.skipUntilNextByte()
                /// Length of the uncompressed data.
                let length = pointerData.intFromBits(count: 16)
                /// 1-complement of the length.
                let nlength = pointerData.intFromBits(count: 16)
                // Check if lengths are OK (nlength should be a 1-complement of length).
                // TODO: Rename WrongBlockLengths to WrongUncompressedBlockLengths (or something else)
                guard length & nlength == 0 else { throw DeflateError.WrongBlockLengths }
                // Process uncompressed data into the output
                // TODO: Replace precondition with guard and error throwing.
                precondition(pointerData.bitMask == 1, "Misaligned byte.")
                var ind = out.count
                out.append(contentsOf: Array(repeating: 0, count: length))
                for _ in 0..<length {
                    out[ind] = pointerData.alignedByte()
                    ind += 1
                }
            } else if blockType == [1, 0] || blockType == [0, 1] {
                // Block with Huffman coding (either static or dynamic)

                // Declaration of Huffman tables which will be populated and used later.
                // There are two alphabets in use and each one needs a Huffman table.

                /// Huffman table for literal bytes.
                var mainLiterals: HuffmanTree
                /// Huffman table for bytes alphabet and alphabet of pairs (length, backward distance).
                var mainDistances: HuffmanTree

                if blockType == [0, 1] { // Static Huffman
                    // In this case codes for literals and distances are fixed.
                    // Bootstraps for tables (first element in pair is code, second is number of bits).
                    let staticHuffmanBootstrap = [[0, 8], [144, 9], [256, 7], [280, 8], [288, -1]]
                    let staticHuffmanLengthsBootstrap = [[0, 5], [32, -1]]
                    // Initialize tables from these bootstraps.
                    mainLiterals = HuffmanTree(bootstrap: staticHuffmanBootstrap)
                    mainDistances = HuffmanTree(bootstrap: staticHuffmanLengthsBootstrap)
                } else { // Dynamic Huffman
                    // In this case there are Huffman codes for two alphabets in data right after block header.
{'fraction_non_alphanumeric': 0.07515050861532074, 'fraction_numerical': 0.011625493045463982, 'mean_word_length': 2.1642036124794743, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1639483', 'n_tokens_mistral': 2594, 'n_tokens_neox': 2316, 'n_words': 986}