diff options
Diffstat (limited to 'misc/ttf2woff/zopfli/katajainen.c')
-rw-r--r-- | misc/ttf2woff/zopfli/katajainen.c | 262 |
1 files changed, 262 insertions, 0 deletions
diff --git a/misc/ttf2woff/zopfli/katajainen.c b/misc/ttf2woff/zopfli/katajainen.c new file mode 100644 index 000000000..145901755 --- /dev/null +++ b/misc/ttf2woff/zopfli/katajainen.c @@ -0,0 +1,262 @@ +/* +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> +#include <limits.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. */ +}; + +/* +Memory pool for nodes. +*/ +typedef struct NodePool { + Node* next; /* Pointer to a free node in the 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; +} + +/* +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. +*/ +static void BoundaryPM(Node* (*lists)[2], Node* leaves, int numsymbols, + NodePool* pool, int index) { + Node* newchain; + Node* oldchain; + int lastcount = lists[index][1]->count; /* Count of last chain of list. */ + + if (index == 0 && lastcount >= numsymbols) return; + + newchain = pool->next++; + 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); + /* Two lookahead chains of previous list used up, create new ones. */ + BoundaryPM(lists, leaves, numsymbols, pool, index - 1); + BoundaryPM(lists, leaves, numsymbols, pool, index - 1); + } + } +} + +static void BoundaryPMFinal(Node* (*lists)[2], + Node* leaves, int numsymbols, NodePool* pool, int index) { + int lastcount = lists[index][1]->count; /* Count of last chain of list. */ + + size_t sum = lists[index - 1][0]->weight + lists[index - 1][1]->weight; + + if (lastcount < numsymbols && sum > leaves[lastcount].weight) { + Node* newchain = pool->next; + Node* oldchain = lists[index][1]->tail; + + lists[index][1] = newchain; + newchain->count = lastcount + 1; + newchain->tail = oldchain; + } else { + lists[index][1]->tail = lists[index - 1][1]; + } +} + +/* +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 = pool->next++; + Node* node1 = pool->next++; + 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) { + int counts[16] = {0}; + unsigned end = 16; + unsigned ptr = 15; + unsigned value = 1; + Node* node; + int val; + + for (node = chain; node; node = node->tail) { + counts[--end] = node->count; + } + + val = counts[15]; + while (ptr >= end) { + for (; val > counts[ptr - 1]; val--) { + bitlengths[leaves[val - 1].count] = value; + } + ptr--; + value++; + } +} + +/* +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; + Node* nodes; + + /* 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. */ + } + if (numsymbols == 2) { + bitlengths[leaves[0].count]++; + bitlengths[leaves[1].count]++; + free(leaves); + return 0; + } + + /* Sort the leaves from lightest to heaviest. Add count into the same + variable for stable sorting. */ + for (i = 0; i < numsymbols; i++) { + if (leaves[i].weight >= + ((size_t)1 << (sizeof(leaves[0].weight) * CHAR_BIT - 9))) { + free(leaves); + return 1; /* Error, we need 9 bits for the count. */ + } + leaves[i].weight = (leaves[i].weight << 9) | leaves[i].count; + } + qsort(leaves, numsymbols, sizeof(Node), LeafComparator); + for (i = 0; i < numsymbols; i++) { + leaves[i].weight >>= 9; + } + + if (numsymbols - 1 < maxbits) { + maxbits = numsymbols - 1; + } + + /* Initialize node memory pool. */ + nodes = (Node*)malloc(maxbits * 2 * numsymbols * sizeof(Node)); + pool.next = nodes; + + 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 - 1; i++) { + BoundaryPM(lists, leaves, numsymbols, &pool, maxbits - 1); + } + BoundaryPMFinal(lists, leaves, numsymbols, &pool, maxbits - 1); + + ExtractBitLengths(lists[maxbits - 1][1], leaves, bitlengths); + + free(lists); + free(leaves); + free(nodes); + return 0; /* OK. */ +} |