1b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne/* 2b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneCopyright 2011 Google Inc. All Rights Reserved. 3b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 4b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneLicensed under the Apache License, Version 2.0 (the "License"); 5b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenneyou may not use this file except in compliance with the License. 6b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneYou may obtain a copy of the License at 7b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 8b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne http://www.apache.org/licenses/LICENSE-2.0 9b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 10b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneUnless required by applicable law or agreed to in writing, software 11b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennedistributed under the License is distributed on an "AS IS" BASIS, 12b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneWITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneSee the License for the specific language governing permissions and 14b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennelimitations under the License. 15b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 16b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneAuthor: lode.vandevenne@gmail.com (Lode Vandevenne) 17b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneAuthor: jyrki.alakuijala@gmail.com (Jyrki Alakuijala) 18b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne*/ 19b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 20b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne/* 21b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneBounded package merge algorithm, based on the paper 22b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne"A Fast and Space-Economical Algorithm for Length-Limited Coding 23b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneJyrki Katajainen, Alistair Moffat, Andrew Turpin". 24b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne*/ 25b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 26b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#include "katajainen.h" 27b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#include <assert.h> 28b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#include <stdlib.h> 29b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 30b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennetypedef struct Node Node; 31b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 32b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne/* 33b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneNodes forming chains. Also used to represent leaves. 34b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne*/ 35b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennestruct Node { 36b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t weight; /* Total weight (symbol count) of this chain. */ 37b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne Node* tail; /* Previous node(s) of this chain, or 0 if none. */ 38b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne int count; /* Leaf symbol index, or number of leaves before this chain. */ 39b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne char inuse; /* Tracking for garbage collection. */ 40b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne}; 41b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 42b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne/* 43b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneMemory pool for nodes. 44b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne*/ 45b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennetypedef struct NodePool { 46b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne Node* nodes; /* The pool. */ 47b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne Node* next; /* Pointer to a possibly free node in the pool. */ 48b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne int size; /* Size of the memory pool. */ 49b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne} NodePool; 50b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 51b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne/* 52b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneInitializes a chain node with the given values and marks it as in use. 53b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne*/ 54b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennestatic void InitNode(size_t weight, int count, Node* tail, Node* node) { 55b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne node->weight = weight; 56b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne node->count = count; 57b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne node->tail = tail; 58b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne node->inuse = 1; 59b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne} 60b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 61b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne/* 62b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneFinds a free location in the memory pool. Performs garbage collection if needed. 63b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennelists: If given, used to mark in-use nodes during garbage collection. 64b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennemaxbits: Size of lists. 65b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennepool: Memory pool to get free node from. 66b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne*/ 67b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennestatic Node* GetFreeNode(Node* (*lists)[2], int maxbits, NodePool* pool) { 68b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (;;) { 69b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (pool->next >= &pool->nodes[pool->size]) { 70b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* Garbage collection. */ 71b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne int i; 72b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (i = 0; i < pool->size; i++) { 73b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne pool->nodes[i].inuse = 0; 74b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 75b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (lists) { 76b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (i = 0; i < maxbits * 2; i++) { 77b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne Node* node; 78b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (node = lists[i / 2][i % 2]; node; node = node->tail) { 79b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne node->inuse = 1; 80b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 81b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 82b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 83b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne pool->next = &pool->nodes[0]; 84b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 85b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (!pool->next->inuse) break; /* Found one. */ 86b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne pool->next++; 87b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 88b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne return pool->next++; 89b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne} 90b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 91b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 92b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne/* 93b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevennePerforms a Boundary Package-Merge step. Puts a new chain in the given list. The 94b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennenew chain is, depending on the weights, a leaf or a combination of two chains 95b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennefrom the previous list. 96b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennelists: The lists of chains. 97b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennemaxbits: Number of lists. 98b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenneleaves: The leaves, one per symbol. 99b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennenumsymbols: Number of leaves. 100b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennepool: the node memory pool. 101b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenneindex: The index of the list in which a new chain or leaf is required. 102b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennefinal: Whether this is the last time this function is called. If it is then it 103b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne is no more needed to recursively call self. 104b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne*/ 105b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennestatic void BoundaryPM(Node* (*lists)[2], int maxbits, 106b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne Node* leaves, int numsymbols, NodePool* pool, int index, char final) { 107b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne Node* newchain; 108b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne Node* oldchain; 109b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne int lastcount = lists[index][1]->count; /* Count of last chain of list. */ 110b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 111b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (index == 0 && lastcount >= numsymbols) return; 112b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 113b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne newchain = GetFreeNode(lists, maxbits, pool); 114b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne oldchain = lists[index][1]; 115b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 116b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* These are set up before the recursive calls below, so that there is a list 117b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne pointing to the new node, to let the garbage collection know it's in use. */ 118b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne lists[index][0] = oldchain; 119b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne lists[index][1] = newchain; 120b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 121b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (index == 0) { 122b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* New leaf node in list 0. */ 123b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne InitNode(leaves[lastcount].weight, lastcount + 1, 0, newchain); 124b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } else { 125b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t sum = lists[index - 1][0]->weight + lists[index - 1][1]->weight; 126b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (lastcount < numsymbols && sum > leaves[lastcount].weight) { 127b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* New leaf inserted in list, so count is incremented. */ 128b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne InitNode(leaves[lastcount].weight, lastcount + 1, oldchain->tail, 129b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne newchain); 130b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } else { 131b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne InitNode(sum, lastcount, lists[index - 1][1], newchain); 132b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (!final) { 133b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* Two lookahead chains of previous list used up, create new ones. */ 134b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne BoundaryPM(lists, maxbits, leaves, numsymbols, pool, index - 1, 0); 135b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne BoundaryPM(lists, maxbits, leaves, numsymbols, pool, index - 1, 0); 136b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 137b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 138b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 139b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne} 140b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 141b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne/* 142b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneInitializes each list with as lookahead chains the two leaves with lowest 143b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenneweights. 144b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne*/ 145b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennestatic void InitLists( 146b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne NodePool* pool, const Node* leaves, int maxbits, Node* (*lists)[2]) { 147b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne int i; 148b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne Node* node0 = GetFreeNode(0, maxbits, pool); 149b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne Node* node1 = GetFreeNode(0, maxbits, pool); 150b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne InitNode(leaves[0].weight, 1, 0, node0); 151b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne InitNode(leaves[1].weight, 2, 0, node1); 152b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (i = 0; i < maxbits; i++) { 153b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne lists[i][0] = node0; 154b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne lists[i][1] = node1; 155b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 156b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne} 157b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 158b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne/* 159b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneConverts result of boundary package-merge to the bitlengths. The result in the 160b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennelast chain of the last list contains the amount of active leaves in each list. 161b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennechain: Chain to extract the bit length from (last chain from last list). 162b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne*/ 163b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennestatic void ExtractBitLengths(Node* chain, Node* leaves, unsigned* bitlengths) { 164b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne Node* node; 165b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (node = chain; node; node = node->tail) { 166b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne int i; 167b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (i = 0; i < node->count; i++) { 168b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne bitlengths[leaves[i].count]++; 169b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 170b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 171b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne} 172b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 173b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne/* 174b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneComparator for sorting the leaves. Has the function signature for qsort. 175b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne*/ 176b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennestatic int LeafComparator(const void* a, const void* b) { 177b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne return ((const Node*)a)->weight - ((const Node*)b)->weight; 178b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne} 179b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 180981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenneint ZopfliLengthLimitedCodeLengths( 181b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne const size_t* frequencies, int n, int maxbits, unsigned* bitlengths) { 182b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne NodePool pool; 183b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne int i; 184b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne int numsymbols = 0; /* Amount of symbols with frequency > 0. */ 185b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne int numBoundaryPMRuns; 186b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 187b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* Array of lists of chains. Each list requires only two lookahead chains at 188b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne a time, so each list is a array of two Node*'s. */ 189b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne Node* (*lists)[2]; 190b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 191b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* One leaf per symbol. Only numsymbols leaves will be used. */ 192b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne Node* leaves = (Node*)malloc(n * sizeof(*leaves)); 193b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 194b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* Initialize all bitlengths at 0. */ 195b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (i = 0; i < n; i++) { 196b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne bitlengths[i] = 0; 197b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 198b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 199b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* Count used symbols and place them in the leaves. */ 200b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (i = 0; i < n; i++) { 201b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (frequencies[i]) { 202b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne leaves[numsymbols].weight = frequencies[i]; 203b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne leaves[numsymbols].count = i; /* Index of symbol this leaf represents. */ 204b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne numsymbols++; 205b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 206b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 207b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 208b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* Check special cases and error conditions. */ 209b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if ((1 << maxbits) < numsymbols) { 210b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne free(leaves); 211b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne return 1; /* Error, too few maxbits to represent symbols. */ 212b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 213b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (numsymbols == 0) { 214b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne free(leaves); 215b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne return 0; /* No symbols at all. OK. */ 216b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 217b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (numsymbols == 1) { 218b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne bitlengths[leaves[0].count] = 1; 219b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne free(leaves); 220b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne return 0; /* Only one symbol, give it bitlength 1, not 0. OK. */ 221b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 222b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 223b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* Sort the leaves from lightest to heaviest. */ 224b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne qsort(leaves, numsymbols, sizeof(Node), LeafComparator); 225b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 226b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* Initialize node memory pool. */ 227b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne pool.size = 2 * maxbits * (maxbits + 1); 228b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne pool.nodes = (Node*)malloc(pool.size * sizeof(*pool.nodes)); 229b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne pool.next = pool.nodes; 230b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (i = 0; i < pool.size; i++) { 231b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne pool.nodes[i].inuse = 0; 232b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 233b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 234b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne lists = (Node* (*)[2])malloc(maxbits * sizeof(*lists)); 235b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne InitLists(&pool, leaves, maxbits, lists); 236b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 237b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* In the last list, 2 * numsymbols - 2 active chains need to be created. Two 238b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne are already created in the initialization. Each BoundaryPM run creates one. */ 239b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne numBoundaryPMRuns = 2 * numsymbols - 4; 240b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (i = 0; i < numBoundaryPMRuns; i++) { 241b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne char final = i == numBoundaryPMRuns - 1; 242b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne BoundaryPM(lists, maxbits, leaves, numsymbols, &pool, maxbits - 1, final); 243b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 244b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 245b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne ExtractBitLengths(lists[maxbits - 1][1], leaves, bitlengths); 246b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 247b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne free(lists); 248b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne free(leaves); 249b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne free(pool.nodes); 250b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne return 0; /* OK. */ 251b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne} 252