Compressed file format
======================

This page describes the precise compressed file format used by the current version of ATC. Note that it is not at all necessary to understand this in order to use ATC, this page is simply intended for those interested.

Conventions
-----------

* Integer data types are denoted using their names from the ``<cstdint.h>`` header for fixed-width integer types (without the suffix ``_t``, e.g. ``uint8``, ``uint16``, ...), while ``float`` and ``double`` refer to single-precision and double-precision numbers respectively.
* The byte order used to pack multi-byte values (such as 32-bit floating-point numbers, 64-bit unsigned integers, ...) into a sequence of bytes is always in little-endian. If the local machine's native byte order is big-endian, CMake should detect this during configuration and compile ATC with a different macro in order to apply the necessary byteswaps during execution.
* A bit stream refers to a sequence of bits, constructed according to the following rules:

    * These bits are packed into 64-bit unsigned integers, starting at the most significant bit.
    * Each time a 64-bit unsigned integer is filled with bits it is written to the byte stream. At the end of a bit stream, if this 64-bit buffer still contains information, it is fully written to the byte stream as well, including any redundant 0 bits.
    * When a data type consisting of multiple bits is written to the bit stream, it is written starting from the most significant bit.
    * When a data type consisting of multiple bytes is written to the bit stream, it is written starting from the least significant byte (regardless of the native byte order). Each byte is then written starting from the most significant bit.
    * When a integer variable in the bit stream is marked with "(EDL)", this means it is an ``uint64`` that is "encoded with dynamic length", i.e. it is encoded as a 6-bit integer ``length``, followed by a ``length``-bit integer that actually stores the value of the integer variable. This is used to efficiently represent integers with a high dynamic range.

* Internally, ATC always uses LSI mode ordering. In case the user prefers MSI ordering (as is the default), ATC will automatically apply the necessary transformations to other user parameters (tensor sizes, preferred mode processing/storage order, ...) to obtain the LSI equivalents. Therefore, when we refer to "the first mode" on this page, we refer to ATC's internal representation, which means we're talking about the mode whose index changes the fastest when traversing the flattened tensor. "The first factor" refers to the factor associated with "the first mode".
* When storing tensor sizes, ATC will store an array of type ``uint32`` of length ``modes``, starting with the first mode (as defined above) and ending with the last mode. 

Format
------
#. Header, consisting of:

    #. ``version_string_length`` (``uint8``): the length of the following version string, in characters
    #. Version string (``version_string_length`` * ``char``): the version string of the version of ATC that generated this compressed file (without a terminating null byte)
    #. The flags bit field (``uint16``) containing the following bits, from least significant to most significant:
    
        #. 1 bit for the research option :cpp:member:`atc::Options::rank_truncation`
        #. 1 bit for :cpp:member:`atc::Options::int_type` (0 = ``uint32``, 1 = ``uint64``)
        #. 1 bit for :cpp:member:`atc::Options::storage_order` (0 = ``LSI``, 1 = ``MSI``)
        #. 1 bit for the research option :cpp:member:`atc::Options::use_quantized_core_slice_norms` (normally 1, not intended for users)
        #. 1 bit for the option :cpp:member:`atc::Options::householder`
        #. 1 bit for the option :cpp:member:`atc::Options::entropy_coding_method` (0 = ``Arithmetic``, 1 = ``ANS``)
        #. 1 bit for the option :cpp:member:`atc::Options::apply_dct`
        #. 2 bits for the option :cpp:member:`atc::Options::core_flattening` (0 = ``Unfold``, 1 = ``Zigzag``, 2 = ``ZOrder``)
        #. 1 bit for the research option :cpp:member:`atc::Options::householder_weighting_method` (normally 0, not intended for users)
        
    #. The numerical ID (``uint8``) of the :cpp:type:`atc::DataType` of the original data. For the precise mapping, check the constant ``data_type_to_id_map`` in the source file |util.hpp|_.
    #. The number of modes of the input tensor (``uint8``)
    #. If :cpp:member:`atc::Options::rank_truncation` and :cpp:member:`atc::Options::apply_dct` are ``true``, the T-HODCT truncation ranks (modes * ``uint32``), otherwise this is skipped.
    #. If :cpp:member:`atc::Options::rank_truncation` is ``true``, the ST-HOSVD truncation ranks (modes * ``uint32``), otherwise this is skipped.
    #. The mode order used to store the quantized core (optionally set using :cpp:member:`atc::Options::mode_storage_order`) (modes * ``uint8``)

#. Array encodings of the quantized core, followed by the first quantized factor, the second quantized factor, ... and the last quantized factor. The order of coefficients in the flattened core is determined by the options :cpp:member:`atc::Options::mode_storage_order` and :cpp:member:`atc::Options::core_flattening`. If :cpp:member:`atc::Options::householder` is true, each factor is represented by the concatenation of the flattenings of its weighted Householder reflectors. If not, each factor is represented by its column-major flattening, after multiplying each column with the corresponding core slice norm. Each of these arrays is encoded as follows:

    #. The scaling factor (``double``) that was applied to the array before quantization
    #. If the array under consideration is the quantized core, the number of blocks (``uint64``) used to parallellize quantization and encoding, otherwise this is skipped.
    #. For each bit plane that was at least partially encoded:
    
        #. ``write_rle`` (``uint8``), which determines whether or not there is run-length-encoded data on this bit plane
        #. If ``write_rle`` is 1 on this bit plane, a bit stream encoding the frequency table used on this bit plane for the entropy coding of the run-lengths:
        
            #. The amount of ``(symbol, frequency)`` pairs (EDL)
            #. For each ``(symbol, frequency)`` pair:
            
                #. ``symbol`` (EDL)
                #. ``frequency`` (EDL)
        
        #. For each block on this bit plane, starting from block 0 (the block that handles the first contiguous block of rows in the bit matrix):
        
            #. The length of the following bit stream, in bytes (``uint64``)
            #. A bit stream containing:
            
                #. ``raw_size`` (``uint64``), the number of raw bits that follow
                #. The raw bits encoded in this block on this bit plane (``raw_size`` * 1 bit)
                #. If ``write_rle`` is 1 on this bit plane:
                
                    #. The number of symbols (run-lengths) that will be entropy-coded (EDL)
                    #. The entropy-coded stream representing the run-lengths that were encoded for this block on this bit plane. We either use arithmetic coding or asymmetric numeral systems depending on the value of :cpp:member:`atc::Options::entropy_coding_method`. The precise implementation is too detailed to describe here, so we refer the reader to the methods ``CompressedIO::arithmetic_encode``, ``CompressedIO::arithmetic_decode``, ``CompressedIO::ANS_encode`` and ``CompressedIO::ANS_decode`` in the source file |CompressedIO.cpp|_.
        
        #. If the current bit plane is not the lowest bit plane (at index 0):
        
            #. If ``all_raw`` was always 0 on the previous bit planes: ``all_raw`` (``uint8``), indicating whether or not the next bit planes will be encoded with (0) or without (1) run-length and entropy coding. If this value was set to 1 on one of the previous bit planes already, it is skipped here.
            #. ``done`` (``uint8``), indicating whether or not this is the last encoded bit plane (1) or not (0)
    
    #. If the array under consideration is the quantized core:
        
        #. If :cpp:member:`atc::Options::use_quantized_core_slice_norms` is true: ``quantized_sizes``, the sizes of the quantized core after pruning 0-slices, starting with the first mode (modes * ``uint32``)
        #. For each mode, starting with the first mode:
        
            #. The core slice norms that will be used to weight the factor coefficients (``sizes[mode]`` * ``double``). If :cpp:member:`atc::Options::use_quantized_core_slice_norms` is true, we will use the core slice norms after quantization and encoding, as well as ``quantized_sizes`` as ``sizes``. If not, we will use the core slice norms of the floating-point core after the ST-HOSVD, as well as the ST-HOSVD truncation ranks as ``sizes``.
    
    #. A bit stream, consisting of, for each non-zero coefficient in the encoded array: whether or not the coefficient is positive (1) or negative (0)

.. |util.hpp| replace:: ``util.hpp``
.. _util.hpp: URL_REPOSITORY_TREE/src/util.hpp
.. |CompressedIO.cpp| replace:: ``CompressedIO.cpp``
.. _CompressedIO.cpp: URL_REPOSITORY_TREE/src/io/CompressedIO.cpp
