1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
|
/* Copyright 2014 Google Inc. All Rights Reserved.
Distributed under MIT license.
See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
*/
// Functions to convert brotli-related data structures into the
// brotli bit stream. The functions here operate under
// assumption that there is enough space in the storage, i.e., there are
// no out-of-range checks anywhere.
//
// These functions do bit addressing into a byte array. The byte array
// is called "storage" and the index to the bit is called storage_ix
// in function arguments.
#ifndef BROTLI_ENC_BROTLI_BIT_STREAM_H_
#define BROTLI_ENC_BROTLI_BIT_STREAM_H_
#include <vector>
#include "./metablock.h"
#include "./types.h"
namespace brotli {
// All Store functions here will use a storage_ix, which is always the bit
// position for the current storage.
// Stores a number between 0 and 255.
void StoreVarLenUint8(size_t n, size_t* storage_ix, uint8_t* storage);
// Stores the compressed meta-block header.
// REQUIRES: length > 0
// REQUIRES: length <= (1 << 24)
void StoreCompressedMetaBlockHeader(bool final_block,
size_t length,
size_t* storage_ix,
uint8_t* storage);
// Stores the uncompressed meta-block header.
// REQUIRES: length > 0
// REQUIRES: length <= (1 << 24)
void StoreUncompressedMetaBlockHeader(size_t length,
size_t* storage_ix,
uint8_t* storage);
// Stores a context map where the histogram type is always the block type.
void StoreTrivialContextMap(size_t num_types,
size_t context_bits,
size_t* storage_ix,
uint8_t* storage);
void StoreHuffmanTreeOfHuffmanTreeToBitMask(
const int num_codes,
const uint8_t *code_length_bitdepth,
size_t *storage_ix,
uint8_t *storage);
void StoreHuffmanTree(const uint8_t* depths, size_t num,
size_t *storage_ix, uint8_t *storage);
// Builds a Huffman tree from histogram[0:length] into depth[0:length] and
// bits[0:length] and stores the encoded tree to the bit stream.
void BuildAndStoreHuffmanTree(const uint32_t *histogram,
const size_t length,
uint8_t* depth,
uint16_t* bits,
size_t* storage_ix,
uint8_t* storage);
void BuildAndStoreHuffmanTreeFast(const uint32_t *histogram,
const size_t histogram_total,
const size_t max_bits,
uint8_t* depth,
uint16_t* bits,
size_t* storage_ix,
uint8_t* storage);
// Encodes the given context map to the bit stream. The number of different
// histogram ids is given by num_clusters.
void EncodeContextMap(const std::vector<uint32_t>& context_map,
size_t num_clusters,
size_t* storage_ix, uint8_t* storage);
// Data structure that stores everything that is needed to encode each block
// switch command.
struct BlockSplitCode {
std::vector<uint32_t> type_code;
std::vector<uint32_t> length_prefix;
std::vector<uint32_t> length_nextra;
std::vector<uint32_t> length_extra;
std::vector<uint8_t> type_depths;
std::vector<uint16_t> type_bits;
std::vector<uint8_t> length_depths;
std::vector<uint16_t> length_bits;
};
// Builds a BlockSplitCode data structure from the block split given by the
// vector of block types and block lengths and stores it to the bit stream.
void BuildAndStoreBlockSplitCode(const std::vector<uint8_t>& types,
const std::vector<uint32_t>& lengths,
const size_t num_types,
BlockSplitCode* code,
size_t* storage_ix,
uint8_t* storage);
// Stores the block switch command with index block_ix to the bit stream.
void StoreBlockSwitch(const BlockSplitCode& code,
const size_t block_ix,
size_t* storage_ix,
uint8_t* storage);
// REQUIRES: length > 0
// REQUIRES: length <= (1 << 24)
void StoreMetaBlock(const uint8_t* input,
size_t start_pos,
size_t length,
size_t mask,
uint8_t prev_byte,
uint8_t prev_byte2,
bool final_block,
uint32_t num_direct_distance_codes,
uint32_t distance_postfix_bits,
ContextType literal_context_mode,
const brotli::Command *commands,
size_t n_commands,
const MetaBlockSplit& mb,
size_t *storage_ix,
uint8_t *storage);
// Stores the meta-block without doing any block splitting, just collects
// one histogram per block category and uses that for entropy coding.
// REQUIRES: length > 0
// REQUIRES: length <= (1 << 24)
void StoreMetaBlockTrivial(const uint8_t* input,
size_t start_pos,
size_t length,
size_t mask,
bool is_last,
const brotli::Command *commands,
size_t n_commands,
size_t *storage_ix,
uint8_t *storage);
// Same as above, but uses static prefix codes for histograms with a only a few
// symbols, and uses static code length prefix codes for all other histograms.
// REQUIRES: length > 0
// REQUIRES: length <= (1 << 24)
void StoreMetaBlockFast(const uint8_t* input,
size_t start_pos,
size_t length,
size_t mask,
bool is_last,
const brotli::Command *commands,
size_t n_commands,
size_t *storage_ix,
uint8_t *storage);
// This is for storing uncompressed blocks (simple raw storage of
// bytes-as-bytes).
// REQUIRES: length > 0
// REQUIRES: length <= (1 << 24)
void StoreUncompressedMetaBlock(bool final_block,
const uint8_t* input,
size_t position, size_t mask,
size_t len,
size_t* storage_ix,
uint8_t* storage);
// Stores an empty metadata meta-block and syncs to a byte boundary.
void StoreSyncMetaBlock(size_t* storage_ix, uint8_t* storage);
} // namespace brotli
#endif // BROTLI_ENC_BROTLI_BIT_STREAM_H_
|
