// //////////////////////////////////////////////////////////
// limitedjpeggzip.h
// written by Stephan Brumme, 2021
// see https://create.stephan-brumme.com/length-limited-prefix-codes/
//

#pragma once

// this file contains two very similar length-limiting algorithm:
// 1. the procedure described in JPEG Annex K.3
// 2. the technique found in MiniZ's source code
// both produce the same output while the latter is

/// adjust bit lengths based on the algorithm in JPEG Annex K.3 specification
/** - it's assumed that no value in histNumBits[] exceed 63
 *  - histNumBits[0] is unused and must be zero
 *  - modifications are performed in-place
 *  - maxLength must be a bit length where a prefix code exists
 *    => that means there are no more than 2^maxLength symbols
 *    => which is the same as sum(histNumBits) <= 2^maxLength
 *  - not much error checking, invalid input can easily crash the code
 *  - example: assume you generated a prefix code with the following bit lengths
 *             symbol A needs 1 bit, B isn't used (0 bits), C needs 2 bits, D 3 bits, E 4 bits, F and G need 5 bits each
 *             => histogram of the bit lengths of all used symbols is
 *                1x 0 bits (discarded), 1x 1 bits, 1x 2 bits, 1x 3 bits, 1x 4 bits and 2x 5 bits
 *             => { 0, 1, 1, 1, 1, 2 }
 *             => proper prefix code because its Kraft value is exactly 1.0 (1*2^-1 + 1*2^-2 + 1*2^-3 + 1*2^-4 + 2*2^-5 = 1.0)
 *             => code to reduce from max. 5 bits to max. 4 bits:
 *             int histNumBits[] = { 0, 1, 1, 1, 1, 2 };
 *             int newMaxLength = jpeg(4, 5, histNumBits); // enforce an upper limit of 4 bits (had up to 5 bits)
 *             => then histNumBits[] becomes { 0, 1, 1, 0, 4, 0 }
 *             => C moved from 2 to 3 bits while F and G were reduced from 5 to 4 bits
 *
 *             => code to reduce from max. 5 bits to max. 3 bits:
 *             int histNumBits[] = { 0, 1, 1, 1, 1, 2 };
 *             int newMaxLength = jpeg(3, 5, histNumBits); // enforce an upper limit of 3 bits (had up to 5 bits)
 *             => then histNumBits[] becomes { 0, 0, 2, 4, 0, 0 }
 *             => lots of changes: A one bit longer, E one bit shorter, F and G two bits shorter
 *  @param  oldMaxLength current maximum code length
 *  @param  newMaxLength desired new maximum code length, e.g. 15 for DEFLATE or JPEG
 *  @param  histNumBits histogram of bit lengths [in] and [out]
 *  @result actual maximum code length, 0 if error
 */
unsigned char limitedJpegInPlace(unsigned char newMaxLength, unsigned char oldMaxLength, unsigned int histNumBits[]);

/// adjust bit lengths based on the algorithm found in MiniZ's sources
/** - it's assumed that no value in histNumBits[] exceed 63
 *  - histNumBits[0] is unused and must be zero
 *  - modifications are performed in-place
 *  - maxLength must be a bit length where a prefix code exists
 *  - not much error checking, invalid input can easily crash the code
 *  @param  oldMaxLength current maximum code length
 *  @param  newMaxLength desired new maximum code length, e.g. 15 for DEFLATE or JPEG
 *  @param  histNumBits histogram of bit lengths [in] and [out]
 *  @result actual maximum code length, 0 if error
 */
unsigned char limitedMinizInPlace(unsigned char newMaxLength, unsigned char oldMaxLength, unsigned int histNumBits[]);


// ---------- same algorithm with a more convenient interface ----------

/// same as limitedJpegInPlace but histogram can be in any order and may contain zeros, the output is stored in a dedicated parameter
/** - the function rejects maxLength > 63 but I don't see any practical reasons you would need a larger limit ...
 *  @param  maxLength  maximum code length, e.g. 15 for JPEG
 *  @param  numCodes   number of codes, equals the array size of histogram and codeLength
 *  @param  histogram  how often each code/symbol was found
 *  @param  codeLength [out] computed code lengths
 *  @result actual maximum code length, 0 if error
 */
unsigned char limitedJpeg(unsigned char maxLength, unsigned int numCodes, const unsigned int histogram[], unsigned char codeLengths[]);

/// same as limitedMinizInPlace but histogram can be in any order and may contain zeros, the output is stored in a dedicated parameter
/** - the function rejects maxLength > 63 but I don't see any practical reasons you would need a larger limit ...
 *  @param  maxLength  maximum code length, e.g. 15 for DEFLATE
 *  @param  numCodes   number of codes, equals the array size of histogram and codeLength
 *  @param  histogram  how often each code/symbol was found
 *  @param  codeLength [out] computed code lengths
 *  @result actual maximum code length, 0 if error
 */
unsigned char limitedMiniz(unsigned char maxLength, unsigned int numCodes, const unsigned int histogram[], unsigned char codeLengths[]);