diff options
Diffstat (limited to 'misc/ttf2woff/zopfli/tree.c')
-rw-r--r-- | misc/ttf2woff/zopfli/tree.c | 101 |
1 files changed, 101 insertions, 0 deletions
diff --git a/misc/ttf2woff/zopfli/tree.c b/misc/ttf2woff/zopfli/tree.c new file mode 100644 index 000000000..c4575119d --- /dev/null +++ b/misc/ttf2woff/zopfli/tree.c @@ -0,0 +1,101 @@ +/* +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) +*/ + +#include "tree.h" + +#include <assert.h> +#include <math.h> +#include <stdio.h> +#include <stdlib.h> + +#include "katajainen.h" +#include "util.h" + +void ZopfliLengthsToSymbols(const unsigned* lengths, size_t n, unsigned maxbits, + unsigned* symbols) { + size_t* bl_count = (size_t*)malloc(sizeof(size_t) * (maxbits + 1)); + size_t* next_code = (size_t*)malloc(sizeof(size_t) * (maxbits + 1)); + unsigned bits, i; + unsigned code; + + for (i = 0; i < n; i++) { + symbols[i] = 0; + } + + /* 1) Count the number of codes for each code length. Let bl_count[N] be the + number of codes of length N, N >= 1. */ + for (bits = 0; bits <= maxbits; bits++) { + bl_count[bits] = 0; + } + for (i = 0; i < n; i++) { + assert(lengths[i] <= maxbits); + bl_count[lengths[i]]++; + } + /* 2) Find the numerical value of the smallest code for each code length. */ + code = 0; + bl_count[0] = 0; + for (bits = 1; bits <= maxbits; bits++) { + code = (code + bl_count[bits-1]) << 1; + next_code[bits] = code; + } + /* 3) Assign numerical values to all codes, using consecutive values for all + codes of the same length with the base values determined at step 2. */ + for (i = 0; i < n; i++) { + unsigned len = lengths[i]; + if (len != 0) { + symbols[i] = next_code[len]; + next_code[len]++; + } + } + + free(bl_count); + free(next_code); +} + +void ZopfliCalculateEntropy(const size_t* count, size_t n, double* bitlengths) { + static const double kInvLog2 = 1.4426950408889; /* 1.0 / log(2.0) */ + unsigned sum = 0; + unsigned i; + double log2sum; + for (i = 0; i < n; ++i) { + sum += count[i]; + } + log2sum = (sum == 0 ? log(n) : log(sum)) * kInvLog2; + for (i = 0; i < n; ++i) { + /* When the count of the symbol is 0, but its cost is requested anyway, it + means the symbol will appear at least once anyway, so give it the cost as if + its count is 1.*/ + if (count[i] == 0) bitlengths[i] = log2sum; + else bitlengths[i] = log2sum - log(count[i]) * kInvLog2; + /* Depending on compiler and architecture, the above subtraction of two + floating point numbers may give a negative result very close to zero + instead of zero (e.g. -5.973954e-17 with gcc 4.1.2 on Ubuntu 11.4). Clamp + it to zero. These floating point imprecisions do not affect the cost model + significantly so this is ok. */ + if (bitlengths[i] < 0 && bitlengths[i] > -1e-5) bitlengths[i] = 0; + assert(bitlengths[i] >= 0); + } +} + +void ZopfliCalculateBitLengths(const size_t* count, size_t n, int maxbits, + unsigned* bitlengths) { + int error = ZopfliLengthLimitedCodeLengths(count, n, maxbits, bitlengths); + (void) error; + assert(!error); +} |