-
Notifications
You must be signed in to change notification settings - Fork 2
/
packagemerge.h
38 lines (31 loc) · 1.7 KB
/
packagemerge.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// //////////////////////////////////////////////////////////
// packagemerge.h
// written by Stephan Brumme, 2021
// see https://create.stephan-brumme.com/length-limited-prefix-codes/
//
#pragma once
#ifdef __cplusplus
extern "C" {
#endif
/// compute limited prefix code length based on Larmore/Hirschberg's package-merge algorithm
/** - histogram must be in ascending order and no entry must be zero
* - 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 or JPEG
* @param numCodes number of codes, equals the array size of histogram and codeLength
* @param A [in] how often each code/symbol was found [out] computed code lengths
* @result actual maximum code length, 0 if error
*/
unsigned char packageMergeSortedInPlace(unsigned char maxLength, unsigned int numCodes, unsigned int A[]);
// ---------- same algorithm with a more convenient interface ----------
/// same as before 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 or 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 packageMerge(unsigned char maxLength, unsigned int numCodes, const unsigned int histogram[], unsigned char codeLengths[]);
#ifdef __cplusplus
}
#endif