1package brotli 2 3import "math" 4 5/* The distance symbols effectively used by "Large Window Brotli" (32-bit). */ 6const numHistogramDistanceSymbols = 544 7 8type histogramLiteral struct { 9 data_ [numLiteralSymbols]uint32 10 total_count_ uint 11 bit_cost_ float64 12} 13 14func histogramClearLiteral(self *histogramLiteral) { 15 self.data_ = [numLiteralSymbols]uint32{} 16 self.total_count_ = 0 17 self.bit_cost_ = math.MaxFloat64 18} 19 20func clearHistogramsLiteral(array []histogramLiteral, length uint) { 21 var i uint 22 for i = 0; i < length; i++ { 23 histogramClearLiteral(&array[i:][0]) 24 } 25} 26 27func histogramAddLiteral(self *histogramLiteral, val uint) { 28 self.data_[val]++ 29 self.total_count_++ 30} 31 32func histogramAddVectorLiteral(self *histogramLiteral, p []byte, n uint) { 33 self.total_count_ += n 34 n += 1 35 for { 36 n-- 37 if n == 0 { 38 break 39 } 40 self.data_[p[0]]++ 41 p = p[1:] 42 } 43} 44 45func histogramAddHistogramLiteral(self *histogramLiteral, v *histogramLiteral) { 46 var i uint 47 self.total_count_ += v.total_count_ 48 for i = 0; i < numLiteralSymbols; i++ { 49 self.data_[i] += v.data_[i] 50 } 51} 52 53func histogramDataSizeLiteral() uint { 54 return numLiteralSymbols 55} 56 57type histogramCommand struct { 58 data_ [numCommandSymbols]uint32 59 total_count_ uint 60 bit_cost_ float64 61} 62 63func histogramClearCommand(self *histogramCommand) { 64 self.data_ = [numCommandSymbols]uint32{} 65 self.total_count_ = 0 66 self.bit_cost_ = math.MaxFloat64 67} 68 69func clearHistogramsCommand(array []histogramCommand, length uint) { 70 var i uint 71 for i = 0; i < length; i++ { 72 histogramClearCommand(&array[i:][0]) 73 } 74} 75 76func histogramAddCommand(self *histogramCommand, val uint) { 77 self.data_[val]++ 78 self.total_count_++ 79} 80 81func histogramAddVectorCommand(self *histogramCommand, p []uint16, n uint) { 82 self.total_count_ += n 83 n += 1 84 for { 85 n-- 86 if n == 0 { 87 break 88 } 89 self.data_[p[0]]++ 90 p = p[1:] 91 } 92} 93 94func histogramAddHistogramCommand(self *histogramCommand, v *histogramCommand) { 95 var i uint 96 self.total_count_ += v.total_count_ 97 for i = 0; i < numCommandSymbols; i++ { 98 self.data_[i] += v.data_[i] 99 } 100} 101 102func histogramDataSizeCommand() uint { 103 return numCommandSymbols 104} 105 106type histogramDistance struct { 107 data_ [numDistanceSymbols]uint32 108 total_count_ uint 109 bit_cost_ float64 110} 111 112func histogramClearDistance(self *histogramDistance) { 113 self.data_ = [numDistanceSymbols]uint32{} 114 self.total_count_ = 0 115 self.bit_cost_ = math.MaxFloat64 116} 117 118func clearHistogramsDistance(array []histogramDistance, length uint) { 119 var i uint 120 for i = 0; i < length; i++ { 121 histogramClearDistance(&array[i:][0]) 122 } 123} 124 125func histogramAddDistance(self *histogramDistance, val uint) { 126 self.data_[val]++ 127 self.total_count_++ 128} 129 130func histogramAddVectorDistance(self *histogramDistance, p []uint16, n uint) { 131 self.total_count_ += n 132 n += 1 133 for { 134 n-- 135 if n == 0 { 136 break 137 } 138 self.data_[p[0]]++ 139 p = p[1:] 140 } 141} 142 143func histogramAddHistogramDistance(self *histogramDistance, v *histogramDistance) { 144 var i uint 145 self.total_count_ += v.total_count_ 146 for i = 0; i < numDistanceSymbols; i++ { 147 self.data_[i] += v.data_[i] 148 } 149} 150 151func histogramDataSizeDistance() uint { 152 return numDistanceSymbols 153} 154 155type blockSplitIterator struct { 156 split_ *blockSplit 157 idx_ uint 158 type_ uint 159 length_ uint 160} 161 162func initBlockSplitIterator(self *blockSplitIterator, split *blockSplit) { 163 self.split_ = split 164 self.idx_ = 0 165 self.type_ = 0 166 if split.lengths != nil { 167 self.length_ = uint(split.lengths[0]) 168 } else { 169 self.length_ = 0 170 } 171} 172 173func blockSplitIteratorNext(self *blockSplitIterator) { 174 if self.length_ == 0 { 175 self.idx_++ 176 self.type_ = uint(self.split_.types[self.idx_]) 177 self.length_ = uint(self.split_.lengths[self.idx_]) 178 } 179 180 self.length_-- 181} 182 183func buildHistogramsWithContext(cmds []command, num_commands uint, literal_split *blockSplit, insert_and_copy_split *blockSplit, dist_split *blockSplit, ringbuffer []byte, start_pos uint, mask uint, prev_byte byte, prev_byte2 byte, context_modes []int, literal_histograms []histogramLiteral, insert_and_copy_histograms []histogramCommand, copy_dist_histograms []histogramDistance) { 184 var pos uint = start_pos 185 var literal_it blockSplitIterator 186 var insert_and_copy_it blockSplitIterator 187 var dist_it blockSplitIterator 188 var i uint 189 190 initBlockSplitIterator(&literal_it, literal_split) 191 initBlockSplitIterator(&insert_and_copy_it, insert_and_copy_split) 192 initBlockSplitIterator(&dist_it, dist_split) 193 for i = 0; i < num_commands; i++ { 194 var cmd *command = &cmds[i] 195 var j uint 196 blockSplitIteratorNext(&insert_and_copy_it) 197 histogramAddCommand(&insert_and_copy_histograms[insert_and_copy_it.type_], uint(cmd.cmd_prefix_)) 198 199 /* TODO: unwrap iterator blocks. */ 200 for j = uint(cmd.insert_len_); j != 0; j-- { 201 var context uint 202 blockSplitIteratorNext(&literal_it) 203 context = literal_it.type_ 204 if context_modes != nil { 205 var lut contextLUT = getContextLUT(context_modes[context]) 206 context = (context << literalContextBits) + uint(getContext(prev_byte, prev_byte2, lut)) 207 } 208 209 histogramAddLiteral(&literal_histograms[context], uint(ringbuffer[pos&mask])) 210 prev_byte2 = prev_byte 211 prev_byte = ringbuffer[pos&mask] 212 pos++ 213 } 214 215 pos += uint(commandCopyLen(cmd)) 216 if commandCopyLen(cmd) != 0 { 217 prev_byte2 = ringbuffer[(pos-2)&mask] 218 prev_byte = ringbuffer[(pos-1)&mask] 219 if cmd.cmd_prefix_ >= 128 { 220 var context uint 221 blockSplitIteratorNext(&dist_it) 222 context = uint(uint32(dist_it.type_<<distanceContextBits) + commandDistanceContext(cmd)) 223 histogramAddDistance(©_dist_histograms[context], uint(cmd.dist_prefix_)&0x3FF) 224 } 225 } 226 } 227} 228