/src/ghostpdl/brotli/c/enc/metablock_inc.h

Source (jump to first uncovered line)
/* NOLINT(build/header_guard) */
/* Copyright 2015 Google Inc. All Rights Reserved.

   Distributed under MIT license.
   See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
*/

/* template parameters: FN */

#define HistogramType FN(Histogram)

/* Greedy block splitter for one block category (literal, command or distance).
*/
typedef struct FN(BlockSplitter) {
  /* Alphabet size of particular block category. */
  size_t alphabet_size_;
  /* We collect at least this many symbols for each block. */
  size_t min_block_size_;
  /* We merge histograms A and B if
       entropy(A+B) < entropy(A) + entropy(B) + split_threshold_,
     where A is the current histogram and B is the histogram of the last or the
     second last block type. */
  double split_threshold_;

  size_t num_blocks_;
  BlockSplit* split_;  /* not owned */
  HistogramType* histograms_;  /* not owned */
  size_t* histograms_size_;  /* not owned */

  /* Temporary storage for BlockSplitterFinishBlock. */
  HistogramType combined_histo[2];

  /* The number of symbols that we want to collect before deciding on whether
     or not to merge the block with a previous one or emit a new block. */
  size_t target_block_size_;
  /* The number of symbols in the current histogram. */
  size_t block_size_;
  /* Offset of the current histogram. */
  size_t curr_histogram_ix_;
  /* Offset of the histograms of the previous two block types. */
  size_t last_histogram_ix_[2];
  /* Entropy of the previous two block types. */
  double last_entropy_[2];
  /* The number of times we merged the current block with the last one. */
  size_t merge_last_count_;
} FN(BlockSplitter);

static void FN(InitBlockSplitter)(
    MemoryManager* m, FN(BlockSplitter)* self, size_t alphabet_size,
    size_t min_block_size, double split_threshold, size_t num_symbols,
    BlockSplit* split, HistogramType** histograms, size_t* histograms_size) {
  size_t max_num_blocks = num_symbols / min_block_size + 1;
  /* We have to allocate one more histogram than the maximum number of block
     types for the current histogram when the meta-block is too big. */
  size_t max_num_types =
      BROTLI_MIN(size_t, max_num_blocks, BROTLI_MAX_NUMBER_OF_BLOCK_TYPES + 1);
  self->alphabet_size_ = alphabet_size;
  self->min_block_size_ = min_block_size;
  self->split_threshold_ = split_threshold;
  self->num_blocks_ = 0;
  self->split_ = split;
  self->histograms_size_ = histograms_size;
  self->target_block_size_ = min_block_size;
  self->block_size_ = 0;
  self->curr_histogram_ix_ = 0;
  self->merge_last_count_ = 0;
  BROTLI_ENSURE_CAPACITY(m, uint8_t,
      split->types, split->types_alloc_size, max_num_blocks);
  BROTLI_ENSURE_CAPACITY(m, uint32_t,
      split->lengths, split->lengths_alloc_size, max_num_blocks);
  if (BROTLI_IS_OOM(m)) return;
  self->split_->num_blocks = max_num_blocks;
  BROTLI_DCHECK(*histograms == 0);
  *histograms_size = max_num_types;
  *histograms = BROTLI_ALLOC(m, HistogramType, *histograms_size);
  self->histograms_ = *histograms;
  if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(*histograms)) return;
  /* Clear only current histogram. */
  FN(HistogramClear)(&self->histograms_[0]);
  self->last_histogram_ix_[0] = self->last_histogram_ix_[1] = 0;
}

/* Does either of three things:
     (1) emits the current block with a new block type;
     (2) emits the current block with the type of the second last block;
     (3) merges the current block with the last block. */
static void FN(BlockSplitterFinishBlock)(
    FN(BlockSplitter)* self, BROTLI_BOOL is_final) {
  BlockSplit* split = self->split_;
  double* last_entropy = self->last_entropy_;
  HistogramType* histograms = self->histograms_;
  self->block_size_ =
      BROTLI_MAX(size_t, self->block_size_, self->min_block_size_);
  if (self->num_blocks_ == 0) {
    /* Create first block. */
    split->lengths[0] = (uint32_t)self->block_size_;
    split->types[0] = 0;
    last_entropy[0] =
        BitsEntropy(histograms[0].data_, self->alphabet_size_);
    last_entropy[1] = last_entropy[0];
    ++self->num_blocks_;
    ++split->num_types;
    ++self->curr_histogram_ix_;
    if (self->curr_histogram_ix_ < *self->histograms_size_)
      FN(HistogramClear)(&histograms[self->curr_histogram_ix_]);
    self->block_size_ = 0;
  } else if (self->block_size_ > 0) {
    double entropy = BitsEntropy(histograms[self->curr_histogram_ix_].data_,
                                 self->alphabet_size_);
    double combined_entropy[2];
    double diff[2];
    size_t j;
    for (j = 0; j < 2; ++j) {
      size_t last_histogram_ix = self->last_histogram_ix_[j];
      self->combined_histo[j] = histograms[self->curr_histogram_ix_];
      FN(HistogramAddHistogram)(&self->combined_histo[j],
          &histograms[last_histogram_ix]);
      combined_entropy[j] = BitsEntropy(
          &self->combined_histo[j].data_[0], self->alphabet_size_);
      diff[j] = combined_entropy[j] - entropy - last_entropy[j];
    }

    if (split->num_types < BROTLI_MAX_NUMBER_OF_BLOCK_TYPES &&
        diff[0] > self->split_threshold_ &&
        diff[1] > self->split_threshold_) {
      /* Create new block. */
      split->lengths[self->num_blocks_] = (uint32_t)self->block_size_;
      split->types[self->num_blocks_] = (uint8_t)split->num_types;
      self->last_histogram_ix_[1] = self->last_histogram_ix_[0];
      self->last_histogram_ix_[0] = (uint8_t)split->num_types;
      last_entropy[1] = last_entropy[0];
      last_entropy[0] = entropy;
      ++self->num_blocks_;
      ++split->num_types;
      ++self->curr_histogram_ix_;
      if (self->curr_histogram_ix_ < *self->histograms_size_)
        FN(HistogramClear)(&histograms[self->curr_histogram_ix_]);
      self->block_size_ = 0;
      self->merge_last_count_ = 0;
      self->target_block_size_ = self->min_block_size_;
    } else if (diff[1] < diff[0] - 20.0) {
      /* Combine this block with second last block. */
      split->lengths[self->num_blocks_] = (uint32_t)self->block_size_;
      split->types[self->num_blocks_] = split->types[self->num_blocks_ - 2];
      BROTLI_SWAP(size_t, self->last_histogram_ix_, 0, 1);
      histograms[self->last_histogram_ix_[0]] = self->combined_histo[1];
      last_entropy[1] = last_entropy[0];
      last_entropy[0] = combined_entropy[1];
      ++self->num_blocks_;
      self->block_size_ = 0;
      FN(HistogramClear)(&histograms[self->curr_histogram_ix_]);
      self->merge_last_count_ = 0;
      self->target_block_size_ = self->min_block_size_;
    } else {
      /* Combine this block with last block. */
      split->lengths[self->num_blocks_ - 1] += (uint32_t)self->block_size_;
      histograms[self->last_histogram_ix_[0]] = self->combined_histo[0];
      last_entropy[0] = combined_entropy[0];
      if (split->num_types == 1) {
        last_entropy[1] = last_entropy[0];
      }
      self->block_size_ = 0;
      FN(HistogramClear)(&histograms[self->curr_histogram_ix_]);
      if (++self->merge_last_count_ > 1) {
        self->target_block_size_ += self->min_block_size_;
      }
    }
  }
  if (is_final) {
    *self->histograms_size_ = split->num_types;
    split->num_blocks = self->num_blocks_;
  }
}

/* Adds the next symbol to the current histogram. When the current histogram
   reaches the target size, decides on merging the block. */
static void FN(BlockSplitterAddSymbol)(FN(BlockSplitter)* self, size_t symbol) {
  FN(HistogramAdd)(&self->histograms_[self->curr_histogram_ix_], symbol);
  ++self->block_size_;
  if (self->block_size_ == self->target_block_size_) {
    FN(BlockSplitterFinishBlock)(self, /* is_final = */ BROTLI_FALSE);
  }
}

#undef HistogramType

Line	Count	Source (jump to first uncovered line)
1		/* NOLINT(build/header_guard) */
2		/* Copyright 2015 Google Inc. All Rights Reserved.
3
4		Distributed under MIT license.
5		See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
6		*/
7
8		/* template parameters: FN */
9
10	0	#define HistogramType FN(Histogram)
11
12		/* Greedy block splitter for one block category (literal, command or distance).
13		*/
14		typedef struct FN(BlockSplitter) {
15		/* Alphabet size of particular block category. */
16		size_t alphabet_size_;
17		/* We collect at least this many symbols for each block. */
18		size_t min_block_size_;
19		/* We merge histograms A and B if
20		entropy(A+B) < entropy(A) + entropy(B) + split_threshold_,
21		where A is the current histogram and B is the histogram of the last or the
22		second last block type. */
23		double split_threshold_;
24
25		size_t num_blocks_;
26		BlockSplit* split_; /* not owned */
27		HistogramType* histograms_; /* not owned */
28		size_t* histograms_size_; /* not owned */
29
30		/* Temporary storage for BlockSplitterFinishBlock. */
31		HistogramType combined_histo[2];
32
33		/* The number of symbols that we want to collect before deciding on whether
34		or not to merge the block with a previous one or emit a new block. */
35		size_t target_block_size_;
36		/* The number of symbols in the current histogram. */
37		size_t block_size_;
38		/* Offset of the current histogram. */
39		size_t curr_histogram_ix_;
40		/* Offset of the histograms of the previous two block types. */
41		size_t last_histogram_ix_[2];
42		/* Entropy of the previous two block types. */
43		double last_entropy_[2];
44		/* The number of times we merged the current block with the last one. */
45		size_t merge_last_count_;
46		} FN(BlockSplitter);
47
48		static void FN(InitBlockSplitter)(
49		MemoryManager* m, FN(BlockSplitter)* self, size_t alphabet_size,
50		size_t min_block_size, double split_threshold, size_t num_symbols,
51	0	BlockSplit* split, HistogramType** histograms, size_t* histograms_size) {
52	0	size_t max_num_blocks = num_symbols / min_block_size + 1;
53		/* We have to allocate one more histogram than the maximum number of block
54		types for the current histogram when the meta-block is too big. */
55	0	size_t max_num_types =
56	0	BROTLI_MIN(size_t, max_num_blocks, BROTLI_MAX_NUMBER_OF_BLOCK_TYPES + 1);
57	0	self->alphabet_size_ = alphabet_size;
58	0	self->min_block_size_ = min_block_size;
59	0	self->split_threshold_ = split_threshold;
60	0	self->num_blocks_ = 0;
61	0	self->split_ = split;
62	0	self->histograms_size_ = histograms_size;
63	0	self->target_block_size_ = min_block_size;
64	0	self->block_size_ = 0;
65	0	self->curr_histogram_ix_ = 0;
66	0	self->merge_last_count_ = 0;
67	0	BROTLI_ENSURE_CAPACITY(m, uint8_t,
68	0	split->types, split->types_alloc_size, max_num_blocks);
69	0	BROTLI_ENSURE_CAPACITY(m, uint32_t,
70	0	split->lengths, split->lengths_alloc_size, max_num_blocks);
71	0	if (BROTLI_IS_OOM(m)) return;
72	0	self->split_->num_blocks = max_num_blocks;
73	0	BROTLI_DCHECK(*histograms == 0);
74	0	*histograms_size = max_num_types;
75	0	histograms = BROTLI_ALLOC(m, HistogramType, histograms_size);
76	0	self->histograms_ = *histograms;
77	0	if (BROTLI_IS_OOM(m) \|\| BROTLI_IS_NULL(*histograms)) return;
78		/* Clear only current histogram. */
79	0	FN(HistogramClear)(&self->histograms_[0]);
80	0	self->last_histogram_ix_[0] = self->last_histogram_ix_[1] = 0;
81	0	} Unexecuted instantiation: metablock.c:InitBlockSplitterLiteral Unexecuted instantiation: metablock.c:InitBlockSplitterCommand Unexecuted instantiation: metablock.c:InitBlockSplitterDistance
82
83		/* Does either of three things:
84		(1) emits the current block with a new block type;
85		(2) emits the current block with the type of the second last block;
86		(3) merges the current block with the last block. */
87		static void FN(BlockSplitterFinishBlock)(
88	0	FN(BlockSplitter)* self, BROTLI_BOOL is_final) {
89	0	BlockSplit* split = self->split_;
90	0	double* last_entropy = self->last_entropy_;
91	0	HistogramType* histograms = self->histograms_;
92	0	self->block_size_ =
93	0	BROTLI_MAX(size_t, self->block_size_, self->min_block_size_);
94	0	if (self->num_blocks_ == 0) {
95		/* Create first block. */
96	0	split->lengths[0] = (uint32_t)self->block_size_;
97	0	split->types[0] = 0;
98	0	last_entropy[0] =
99	0	BitsEntropy(histograms[0].data_, self->alphabet_size_);
100	0	last_entropy[1] = last_entropy[0];
101	0	++self->num_blocks_;
102	0	++split->num_types;
103	0	++self->curr_histogram_ix_;
104	0	if (self->curr_histogram_ix_ < *self->histograms_size_)
105	0	FN(HistogramClear)(&histograms[self->curr_histogram_ix_]);
106	0	self->block_size_ = 0;
107	0	} else if (self->block_size_ > 0) {
108	0	double entropy = BitsEntropy(histograms[self->curr_histogram_ix_].data_,
109	0	self->alphabet_size_);
110	0	double combined_entropy[2];
111	0	double diff[2];
112	0	size_t j;
113	0	for (j = 0; j < 2; ++j) {
114	0	size_t last_histogram_ix = self->last_histogram_ix_[j];
115	0	self->combined_histo[j] = histograms[self->curr_histogram_ix_];
116	0	FN(HistogramAddHistogram)(&self->combined_histo[j],
117	0	&histograms[last_histogram_ix]);
118	0	combined_entropy[j] = BitsEntropy(
119	0	&self->combined_histo[j].data_[0], self->alphabet_size_);
120	0	diff[j] = combined_entropy[j] - entropy - last_entropy[j];
121	0	}
122
123	0	if (split->num_types < BROTLI_MAX_NUMBER_OF_BLOCK_TYPES &&
124	0	diff[0] > self->split_threshold_ &&
125	0	diff[1] > self->split_threshold_) {
126		/* Create new block. */
127	0	split->lengths[self->num_blocks_] = (uint32_t)self->block_size_;
128	0	split->types[self->num_blocks_] = (uint8_t)split->num_types;
129	0	self->last_histogram_ix_[1] = self->last_histogram_ix_[0];
130	0	self->last_histogram_ix_[0] = (uint8_t)split->num_types;
131	0	last_entropy[1] = last_entropy[0];
132	0	last_entropy[0] = entropy;
133	0	++self->num_blocks_;
134	0	++split->num_types;
135	0	++self->curr_histogram_ix_;
136	0	if (self->curr_histogram_ix_ < *self->histograms_size_)
137	0	FN(HistogramClear)(&histograms[self->curr_histogram_ix_]);
138	0	self->block_size_ = 0;
139	0	self->merge_last_count_ = 0;
140	0	self->target_block_size_ = self->min_block_size_;
141	0	} else if (diff[1] < diff[0] - 20.0) {
142		/* Combine this block with second last block. */
143	0	split->lengths[self->num_blocks_] = (uint32_t)self->block_size_;
144	0	split->types[self->num_blocks_] = split->types[self->num_blocks_ - 2];
145	0	BROTLI_SWAP(size_t, self->last_histogram_ix_, 0, 1);
146	0	histograms[self->last_histogram_ix_[0]] = self->combined_histo[1];
147	0	last_entropy[1] = last_entropy[0];
148	0	last_entropy[0] = combined_entropy[1];
149	0	++self->num_blocks_;
150	0	self->block_size_ = 0;
151	0	FN(HistogramClear)(&histograms[self->curr_histogram_ix_]);
152	0	self->merge_last_count_ = 0;
153	0	self->target_block_size_ = self->min_block_size_;
154	0	} else {
155		/* Combine this block with last block. */
156	0	split->lengths[self->num_blocks_ - 1] += (uint32_t)self->block_size_;
157	0	histograms[self->last_histogram_ix_[0]] = self->combined_histo[0];
158	0	last_entropy[0] = combined_entropy[0];
159	0	if (split->num_types == 1) {
160	0	last_entropy[1] = last_entropy[0];
161	0	}
162	0	self->block_size_ = 0;
163	0	FN(HistogramClear)(&histograms[self->curr_histogram_ix_]);
164	0	if (++self->merge_last_count_ > 1) {
165	0	self->target_block_size_ += self->min_block_size_;
166	0	}
167	0	}
168	0	}
169	0	if (is_final) {
170	0	*self->histograms_size_ = split->num_types;
171	0	split->num_blocks = self->num_blocks_;
172	0	}
173	0	} Unexecuted instantiation: metablock.c:BlockSplitterFinishBlockLiteral Unexecuted instantiation: metablock.c:BlockSplitterFinishBlockCommand Unexecuted instantiation: metablock.c:BlockSplitterFinishBlockDistance
174
175		/* Adds the next symbol to the current histogram. When the current histogram
176		reaches the target size, decides on merging the block. */
177	0	static void FN(BlockSplitterAddSymbol)(FN(BlockSplitter)* self, size_t symbol) {
178	0	FN(HistogramAdd)(&self->histograms_[self->curr_histogram_ix_], symbol);
179	0	++self->block_size_;
180	0	if (self->block_size_ == self->target_block_size_) {
181	0	FN(BlockSplitterFinishBlock)(self, /* is_final = */ BROTLI_FALSE);
182	0	}
183	0	} Unexecuted instantiation: metablock.c:BlockSplitterAddSymbolCommand Unexecuted instantiation: metablock.c:BlockSplitterAddSymbolLiteral Unexecuted instantiation: metablock.c:BlockSplitterAddSymbolDistance
184
185		#undef HistogramType

Coverage Report

Created: 2025-06-24 07:01