diff options
Diffstat (limited to 'katajainen.c')
| -rw-r--r-- | katajainen.c | 251 |
1 files changed, 0 insertions, 251 deletions
diff --git a/katajainen.c b/katajainen.c deleted file mode 100644 index 783ea08..0000000 --- a/katajainen.c +++ /dev/null @@ -1,251 +0,0 @@ -/* -Copyright 2011 Google Inc. All Rights Reserved. - -Licensed under the Apache License, Version 2.0 (the "License"); -you may not use this file except in compliance with the License. -You may obtain a copy of the License at - - http://www.apache.org/licenses/LICENSE-2.0 - -Unless required by applicable law or agreed to in writing, software -distributed under the License is distributed on an "AS IS" BASIS, -WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -See the License for the specific language governing permissions and -limitations under the License. - -Author: lode.vandevenne@gmail.com (Lode Vandevenne) -Author: jyrki.alakuijala@gmail.com (Jyrki Alakuijala) -*/ - -/* -Bounded package merge algorithm, based on the paper -"A Fast and Space-Economical Algorithm for Length-Limited Coding -Jyrki Katajainen, Alistair Moffat, Andrew Turpin". -*/ - -#include "katajainen.h" -#include <assert.h> -#include <stdlib.h> - -typedef struct Node Node; - -/* -Nodes forming chains. Also used to represent leaves. -*/ -struct Node { - size_t weight; /* Total weight (symbol count) of this chain. */ - Node* tail; /* Previous node(s) of this chain, or 0 if none. */ - int count; /* Leaf symbol index, or number of leaves before this chain. */ - char inuse; /* Tracking for garbage collection. */ -}; - -/* -Memory pool for nodes. -*/ -typedef struct NodePool { - Node* nodes; /* The pool. */ - Node* next; /* Pointer to a possibly free node in the pool. */ - int size; /* Size of the memory pool. */ -} NodePool; - -/* -Initializes a chain node with the given values and marks it as in use. -*/ -static void InitNode(size_t weight, int count, Node* tail, Node* node) { - node->weight = weight; - node->count = count; - node->tail = tail; - node->inuse = 1; -} - -/* -Finds a free location in the memory pool. Performs garbage collection if needed. -lists: If given, used to mark in-use nodes during garbage collection. -maxbits: Size of lists. -pool: Memory pool to get free node from. -*/ -static Node* GetFreeNode(Node* (*lists)[2], int maxbits, NodePool* pool) { - for (;;) { - if (pool->next >= &pool->nodes[pool->size]) { - /* Garbage collection. */ - int i; - for (i = 0; i < pool->size; i++) { - pool->nodes[i].inuse = 0; - } - if (lists) { - for (i = 0; i < maxbits * 2; i++) { - Node* node; - for (node = lists[i / 2][i % 2]; node; node = node->tail) { - node->inuse = 1; - } - } - } - pool->next = &pool->nodes[0]; - } - if (!pool->next->inuse) break; /* Found one. */ - pool->next++; - } - return pool->next++; -} - - -/* -Performs a Boundary Package-Merge step. Puts a new chain in the given list. The -new chain is, depending on the weights, a leaf or a combination of two chains -from the previous list. -lists: The lists of chains. -maxbits: Number of lists. -leaves: The leaves, one per symbol. -numsymbols: Number of leaves. -pool: the node memory pool. -index: The index of the list in which a new chain or leaf is required. -final: Whether this is the last time this function is called. If it is then it - is no more needed to recursively call self. -*/ -static void BoundaryPM(Node* (*lists)[2], int maxbits, - Node* leaves, int numsymbols, NodePool* pool, int index, char final) { - Node* newchain; - Node* oldchain; - int lastcount = lists[index][1]->count; /* Count of last chain of list. */ - - if (index == 0 && lastcount >= numsymbols) return; - - newchain = GetFreeNode(lists, maxbits, pool); - oldchain = lists[index][1]; - - /* These are set up before the recursive calls below, so that there is a list - pointing to the new node, to let the garbage collection know it's in use. */ - lists[index][0] = oldchain; - lists[index][1] = newchain; - - if (index == 0) { - /* New leaf node in list 0. */ - InitNode(leaves[lastcount].weight, lastcount + 1, 0, newchain); - } else { - size_t sum = lists[index - 1][0]->weight + lists[index - 1][1]->weight; - if (lastcount < numsymbols && sum > leaves[lastcount].weight) { - /* New leaf inserted in list, so count is incremented. */ - InitNode(leaves[lastcount].weight, lastcount + 1, oldchain->tail, - newchain); - } else { - InitNode(sum, lastcount, lists[index - 1][1], newchain); - if (!final) { - /* Two lookahead chains of previous list used up, create new ones. */ - BoundaryPM(lists, maxbits, leaves, numsymbols, pool, index - 1, 0); - BoundaryPM(lists, maxbits, leaves, numsymbols, pool, index - 1, 0); - } - } - } -} - -/* -Initializes each list with as lookahead chains the two leaves with lowest -weights. -*/ -static void InitLists( - NodePool* pool, const Node* leaves, int maxbits, Node* (*lists)[2]) { - int i; - Node* node0 = GetFreeNode(0, maxbits, pool); - Node* node1 = GetFreeNode(0, maxbits, pool); - InitNode(leaves[0].weight, 1, 0, node0); - InitNode(leaves[1].weight, 2, 0, node1); - for (i = 0; i < maxbits; i++) { - lists[i][0] = node0; - lists[i][1] = node1; - } -} - -/* -Converts result of boundary package-merge to the bitlengths. The result in the -last chain of the last list contains the amount of active leaves in each list. -chain: Chain to extract the bit length from (last chain from last list). -*/ -static void ExtractBitLengths(Node* chain, Node* leaves, unsigned* bitlengths) { - Node* node; - for (node = chain; node; node = node->tail) { - int i; - for (i = 0; i < node->count; i++) { - bitlengths[leaves[i].count]++; - } - } -} - -/* -Comparator for sorting the leaves. Has the function signature for qsort. -*/ -static int LeafComparator(const void* a, const void* b) { - return ((const Node*)a)->weight - ((const Node*)b)->weight; -} - -int ZopfliLengthLimitedCodeLengths( - const size_t* frequencies, int n, int maxbits, unsigned* bitlengths) { - NodePool pool; - int i; - int numsymbols = 0; /* Amount of symbols with frequency > 0. */ - int numBoundaryPMRuns; - - /* Array of lists of chains. Each list requires only two lookahead chains at - a time, so each list is a array of two Node*'s. */ - Node* (*lists)[2]; - - /* One leaf per symbol. Only numsymbols leaves will be used. */ - Node* leaves = (Node*)malloc(n * sizeof(*leaves)); - - /* Initialize all bitlengths at 0. */ - for (i = 0; i < n; i++) { - bitlengths[i] = 0; - } - - /* Count used symbols and place them in the leaves. */ - for (i = 0; i < n; i++) { - if (frequencies[i]) { - leaves[numsymbols].weight = frequencies[i]; - leaves[numsymbols].count = i; /* Index of symbol this leaf represents. */ - numsymbols++; - } - } - - /* Check special cases and error conditions. */ - if ((1 << maxbits) < numsymbols) { - free(leaves); - return 1; /* Error, too few maxbits to represent symbols. */ - } - if (numsymbols == 0) { - free(leaves); - return 0; /* No symbols at all. OK. */ - } - if (numsymbols == 1) { - bitlengths[leaves[0].count] = 1; - free(leaves); - return 0; /* Only one symbol, give it bitlength 1, not 0. OK. */ - } - - /* Sort the leaves from lightest to heaviest. */ - qsort(leaves, numsymbols, sizeof(Node), LeafComparator); - - /* Initialize node memory pool. */ - pool.size = 2 * maxbits * (maxbits + 1); - pool.nodes = (Node*)malloc(pool.size * sizeof(*pool.nodes)); - pool.next = pool.nodes; - for (i = 0; i < pool.size; i++) { - pool.nodes[i].inuse = 0; - } - - lists = (Node* (*)[2])malloc(maxbits * sizeof(*lists)); - InitLists(&pool, leaves, maxbits, lists); - - /* In the last list, 2 * numsymbols - 2 active chains need to be created. Two - are already created in the initialization. Each BoundaryPM run creates one. */ - numBoundaryPMRuns = 2 * numsymbols - 4; - for (i = 0; i < numBoundaryPMRuns; i++) { - char final = i == numBoundaryPMRuns - 1; - BoundaryPM(lists, maxbits, leaves, numsymbols, &pool, maxbits - 1, final); - } - - ExtractBitLengths(lists[maxbits - 1][1], leaves, bitlengths); - - free(lists); - free(leaves); - free(pool.nodes); - return 0; /* OK. */ -} |