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. */
+}