Coverage Report

Created: 2026-02-09 06:30

next uncovered line (L), next uncovered region (R), next uncovered branch (B)
/src/h2o/deps/brotli/c/enc/entropy_encode.h
Line
Count
Source
1
/* Copyright 2010 Google Inc. All Rights Reserved.
2
3
   Distributed under MIT license.
4
   See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
5
*/
6
7
/* Entropy encoding (Huffman) utilities. */
8
9
#ifndef BROTLI_ENC_ENTROPY_ENCODE_H_
10
#define BROTLI_ENC_ENTROPY_ENCODE_H_
11
12
#include <brotli/types.h>
13
#include "./port.h"
14
15
#if defined(__cplusplus) || defined(c_plusplus)
16
extern "C" {
17
#endif
18
19
/* A node of a Huffman tree. */
20
typedef struct HuffmanTree {
21
  uint32_t total_count_;
22
  int16_t index_left_;
23
  int16_t index_right_or_value_;
24
} HuffmanTree;
25
26
static BROTLI_INLINE void InitHuffmanTree(HuffmanTree* self, uint32_t count,
27
0
    int16_t left, int16_t right) {
28
0
  self->total_count_ = count;
29
0
  self->index_left_ = left;
30
0
  self->index_right_or_value_ = right;
31
0
}
Unexecuted instantiation: brotli_bit_stream.c:InitHuffmanTree
Unexecuted instantiation: compress_fragment.c:InitHuffmanTree
Unexecuted instantiation: compress_fragment_two_pass.c:InitHuffmanTree
Unexecuted instantiation: encode.c:InitHuffmanTree
Unexecuted instantiation: entropy_encode.c:InitHuffmanTree
Unexecuted instantiation: metablock.c:InitHuffmanTree
32
33
/* Returns 1 is assignment of depths succeeded, otherwise 0. */
34
BROTLI_INTERNAL BROTLI_BOOL BrotliSetDepth(
35
    int p, HuffmanTree* pool, uint8_t* depth, int max_depth);
36
37
/* This function will create a Huffman tree.
38
39
   The (data,length) contains the population counts.
40
   The tree_limit is the maximum bit depth of the Huffman codes.
41
42
   The depth contains the tree, i.e., how many bits are used for
43
   the symbol.
44
45
   The actual Huffman tree is constructed in the tree[] array, which has to
46
   be at least 2 * length + 1 long.
47
48
   See http://en.wikipedia.org/wiki/Huffman_coding */
49
BROTLI_INTERNAL void BrotliCreateHuffmanTree(const uint32_t *data,
50
                                             const size_t length,
51
                                             const int tree_limit,
52
                                             HuffmanTree* tree,
53
                                             uint8_t *depth);
54
55
/* Change the population counts in a way that the consequent
56
   Huffman tree compression, especially its RLE-part will be more
57
   likely to compress this data more efficiently.
58
59
   length contains the size of the histogram.
60
   counts contains the population counts.
61
   good_for_rle is a buffer of at least length size */
62
BROTLI_INTERNAL void BrotliOptimizeHuffmanCountsForRle(
63
    size_t length, uint32_t* counts, uint8_t* good_for_rle);
64
65
/* Write a Huffman tree from bit depths into the bit-stream representation
66
   of a Huffman tree. The generated Huffman tree is to be compressed once
67
   more using a Huffman tree */
68
BROTLI_INTERNAL void BrotliWriteHuffmanTree(const uint8_t* depth,
69
                                            size_t num,
70
                                            size_t* tree_size,
71
                                            uint8_t* tree,
72
                                            uint8_t* extra_bits_data);
73
74
/* Get the actual bit values for a tree of bit depths. */
75
BROTLI_INTERNAL void BrotliConvertBitDepthsToSymbols(const uint8_t *depth,
76
                                                     size_t len,
77
                                                     uint16_t *bits);
78
79
/* Input size optimized Shell sort. */
80
typedef BROTLI_BOOL (*HuffmanTreeComparator)(
81
    const HuffmanTree*, const HuffmanTree*);
82
static BROTLI_INLINE void SortHuffmanTreeItems(HuffmanTree* items,
83
0
    const size_t n, HuffmanTreeComparator comparator) {
84
0
  static const size_t gaps[] = {132, 57, 23, 10, 4, 1};
85
0
  if (n < 13) {
86
    /* Insertion sort. */
87
0
    size_t i;
88
0
    for (i = 1; i < n; ++i) {
89
0
      HuffmanTree tmp = items[i];
90
0
      size_t k = i;
91
0
      size_t j = i - 1;
92
0
      while (comparator(&tmp, &items[j])) {
93
0
        items[k] = items[j];
94
0
        k = j;
95
0
        if (!j--) break;
96
0
      }
97
0
      items[k] = tmp;
98
0
    }
99
0
    return;
100
0
  } else {
101
    /* Shell sort. */
102
0
    int g = n < 57 ? 2 : 0;
103
0
    for (; g < 6; ++g) {
104
0
      size_t gap = gaps[g];
105
0
      size_t i;
106
0
      for (i = gap; i < n; ++i) {
107
0
        size_t j = i;
108
0
        HuffmanTree tmp = items[i];
109
0
        for (; j >= gap && comparator(&tmp, &items[j - gap]); j -= gap) {
110
0
          items[j] = items[j - gap];
111
0
        }
112
0
        items[j] = tmp;
113
0
      }
114
0
    }
115
0
  }
116
0
}
Unexecuted instantiation: brotli_bit_stream.c:SortHuffmanTreeItems
Unexecuted instantiation: compress_fragment.c:SortHuffmanTreeItems
Unexecuted instantiation: compress_fragment_two_pass.c:SortHuffmanTreeItems
Unexecuted instantiation: encode.c:SortHuffmanTreeItems
Unexecuted instantiation: entropy_encode.c:SortHuffmanTreeItems
Unexecuted instantiation: metablock.c:SortHuffmanTreeItems
117
118
#if defined(__cplusplus) || defined(c_plusplus)
119
}  /* extern "C" */
120
#endif
121
122
#endif  /* BROTLI_ENC_ENTROPY_ENCODE_H_ */