"Fossies" - the Fresh Open Source Software Archive

Member "pigz-2.8/zopfli/src/zopfli/tree.c" (11 Jan 2015, 3375 Bytes) of package /linux/privat/pigz-2.8.tar.gz:

    1 /*
    2 Copyright 2011 Google Inc. All Rights Reserved.
    3 
    4 Licensed under the Apache License, Version 2.0 (the "License");
    5 you may not use this file except in compliance with the License.
    6 You may obtain a copy of the License at
    7 
    8     http://www.apache.org/licenses/LICENSE-2.0
    9 
   10 Unless required by applicable law or agreed to in writing, software
   11 distributed under the License is distributed on an "AS IS" BASIS,
   12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   13 See the License for the specific language governing permissions and
   14 limitations under the License.
   15 
   16 Author: lode.vandevenne@gmail.com (Lode Vandevenne)
   17 Author: jyrki.alakuijala@gmail.com (Jyrki Alakuijala)
   18 */
   19 
   20 #include "tree.h"
   21 
   22 #include <assert.h>
   23 #include <math.h>
   24 #include <stdio.h>
   25 #include <stdlib.h>
   26 
   27 #include "katajainen.h"
   28 #include "util.h"
   29 
   30 void ZopfliLengthsToSymbols(const unsigned* lengths, size_t n, unsigned maxbits,
   31                             unsigned* symbols) {
   32   size_t* bl_count = (size_t*)malloc(sizeof(size_t) * (maxbits + 1));
   33   size_t* next_code = (size_t*)malloc(sizeof(size_t) * (maxbits + 1));
   34   unsigned bits, i;
   35   unsigned code;
   36 
   37   for (i = 0; i < n; i++) {
   38     symbols[i] = 0;
   39   }
   40 
   41   /* 1) Count the number of codes for each code length. Let bl_count[N] be the
   42   number of codes of length N, N >= 1. */
   43   for (bits = 0; bits <= maxbits; bits++) {
   44     bl_count[bits] = 0;
   45   }
   46   for (i = 0; i < n; i++) {
   47     assert(lengths[i] <= maxbits);
   48     bl_count[lengths[i]]++;
   49   }
   50   /* 2) Find the numerical value of the smallest code for each code length. */
   51   code = 0;
   52   bl_count[0] = 0;
   53   for (bits = 1; bits <= maxbits; bits++) {
   54     code = (code + bl_count[bits-1]) << 1;
   55     next_code[bits] = code;
   56   }
   57   /* 3) Assign numerical values to all codes, using consecutive values for all
   58   codes of the same length with the base values determined at step 2. */
   59   for (i = 0;  i < n; i++) {
   60     unsigned len = lengths[i];
   61     if (len != 0) {
   62       symbols[i] = next_code[len];
   63       next_code[len]++;
   64     }
   65   }
   66 
   67   free(bl_count);
   68   free(next_code);
   69 }
   70 
   71 void ZopfliCalculateEntropy(const size_t* count, size_t n, double* bitlengths) {
   72   static const double kInvLog2 = 1.4426950408889;  /* 1.0 / log(2.0) */
   73   unsigned sum = 0;
   74   unsigned i;
   75   double log2sum;
   76   for (i = 0; i < n; ++i) {
   77     sum += count[i];
   78   }
   79   log2sum = (sum == 0 ? log(n) : log(sum)) * kInvLog2;
   80   for (i = 0; i < n; ++i) {
   81     /* When the count of the symbol is 0, but its cost is requested anyway, it
   82     means the symbol will appear at least once anyway, so give it the cost as if
   83     its count is 1.*/
   84     if (count[i] == 0) bitlengths[i] = log2sum;
   85     else bitlengths[i] = log2sum - log(count[i]) * kInvLog2;
   86     /* Depending on compiler and architecture, the above subtraction of two
   87     floating point numbers may give a negative result very close to zero
   88     instead of zero (e.g. -5.973954e-17 with gcc 4.1.2 on Ubuntu 11.4). Clamp
   89     it to zero. These floating point imprecisions do not affect the cost model
   90     significantly so this is ok. */
   91     if (bitlengths[i] < 0 && bitlengths[i] > -1e-5) bitlengths[i] = 0;
   92     assert(bitlengths[i] >= 0);
   93   }
   94 }
   95 
   96 void ZopfliCalculateBitLengths(const size_t* count, size_t n, int maxbits,
   97                                unsigned* bitlengths) {
   98   int error = ZopfliLengthLimitedCodeLengths(count, n, maxbits, bitlengths);
   99   (void) error;
  100   assert(!error);
  101 }