package brotli
import "math"
type zopfliNode struct {
length uint32
distance uint32
dcode_insert_length uint32
u struct {
cost float32
next uint32
shortcut uint32
}
}
const maxEffectiveDistanceAlphabetSize = 544
const kInfinity float32 = 1.7e38
var kDistanceCacheIndex = []uint32 {0 , 1 , 2 , 3 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 1 , 1 , 1 , 1 }
var kDistanceCacheOffset = []int {0 , 0 , 0 , 0 , -1 , 1 , -2 , 2 , -3 , 3 , -1 , 1 , -2 , 2 , -3 , 3 }
func initZopfliNodes(array []zopfliNode , length uint ) {
var stub zopfliNode
var i uint
stub .length = 1
stub .distance = 0
stub .dcode_insert_length = 0
stub .u .cost = kInfinity
for i = 0 ; i < length ; i ++ {
array [i ] = stub
}
}
func zopfliNodeCopyLength(self *zopfliNode ) uint32 {
return self .length & 0x1FFFFFF
}
func zopfliNodeLengthCode(self *zopfliNode ) uint32 {
var modifier uint32 = self .length >> 25
return zopfliNodeCopyLength (self ) + 9 - modifier
}
func zopfliNodeCopyDistance(self *zopfliNode ) uint32 {
return self .distance
}
func zopfliNodeDistanceCode(self *zopfliNode ) uint32 {
var short_code uint32 = self .dcode_insert_length >> 27
if short_code == 0 {
return zopfliNodeCopyDistance (self ) + numDistanceShortCodes - 1
} else {
return short_code - 1
}
}
func zopfliNodeCommandLength(self *zopfliNode ) uint32 {
return zopfliNodeCopyLength (self ) + (self .dcode_insert_length & 0x7FFFFFF )
}
type zopfliCostModel struct {
cost_cmd_ [numCommandSymbols ]float32
cost_dist_ []float32
distance_histogram_size uint32
literal_costs_ []float32
min_cost_cmd_ float32
num_bytes_ uint
}
func initZopfliCostModel(self *zopfliCostModel , dist *distanceParams , num_bytes uint ) {
var distance_histogram_size uint32 = dist .alphabet_size
if distance_histogram_size > maxEffectiveDistanceAlphabetSize {
distance_histogram_size = maxEffectiveDistanceAlphabetSize
}
self .num_bytes_ = num_bytes
self .literal_costs_ = make ([]float32 , (num_bytes + 2 ))
self .cost_dist_ = make ([]float32 , (dist .alphabet_size ))
self .distance_histogram_size = distance_histogram_size
}
func cleanupZopfliCostModel(self *zopfliCostModel ) {
self .literal_costs_ = nil
self .cost_dist_ = nil
}
func setCost(histogram []uint32 , histogram_size uint , literal_histogram bool , cost []float32 ) {
var sum uint = 0
var missing_symbol_sum uint
var log2sum float32
var missing_symbol_cost float32
var i uint
for i = 0 ; i < histogram_size ; i ++ {
sum += uint (histogram [i ])
}
log2sum = float32 (fastLog2 (sum ))
missing_symbol_sum = sum
if !literal_histogram {
for i = 0 ; i < histogram_size ; i ++ {
if histogram [i ] == 0 {
missing_symbol_sum ++
}
}
}
missing_symbol_cost = float32 (fastLog2 (missing_symbol_sum )) + 2
for i = 0 ; i < histogram_size ; i ++ {
if histogram [i ] == 0 {
cost [i ] = missing_symbol_cost
continue
}
cost [i ] = log2sum - float32 (fastLog2 (uint (histogram [i ])))
if cost [i ] < 1 {
cost [i ] = 1
}
}
}
func zopfliCostModelSetFromCommands(self *zopfliCostModel , position uint , ringbuffer []byte , ringbuffer_mask uint , commands []command , last_insert_len uint ) {
var histogram_literal [numLiteralSymbols ]uint32
var histogram_cmd [numCommandSymbols ]uint32
var histogram_dist [maxEffectiveDistanceAlphabetSize ]uint32
var cost_literal [numLiteralSymbols ]float32
var pos uint = position - last_insert_len
var min_cost_cmd float32 = kInfinity
var cost_cmd []float32 = self .cost_cmd_ [:]
var literal_costs []float32
histogram_literal = [numLiteralSymbols ]uint32 {}
histogram_cmd = [numCommandSymbols ]uint32 {}
histogram_dist = [maxEffectiveDistanceAlphabetSize ]uint32 {}
for i := range commands {
var inslength uint = uint (commands [i ].insert_len_ )
var copylength uint = uint (commandCopyLen (&commands [i ]))
var distcode uint = uint (commands [i ].dist_prefix_ ) & 0x3FF
var cmdcode uint = uint (commands [i ].cmd_prefix_ )
var j uint
histogram_cmd [cmdcode ]++
if cmdcode >= 128 {
histogram_dist [distcode ]++
}
for j = 0 ; j < inslength ; j ++ {
histogram_literal [ringbuffer [(pos +j )&ringbuffer_mask ]]++
}
pos += inslength + copylength
}
setCost (histogram_literal [:], numLiteralSymbols , true , cost_literal [:])
setCost (histogram_cmd [:], numCommandSymbols , false , cost_cmd )
setCost (histogram_dist [:], uint (self .distance_histogram_size ), false , self .cost_dist_ )
for i := 0 ; i < numCommandSymbols ; i ++ {
min_cost_cmd = brotli_min_float (min_cost_cmd , cost_cmd [i ])
}
self .min_cost_cmd_ = min_cost_cmd
{
literal_costs = self .literal_costs_
var literal_carry float32 = 0.0
num_bytes := int (self .num_bytes_ )
literal_costs [0 ] = 0.0
for i := 0 ; i < num_bytes ; i ++ {
literal_carry += cost_literal [ringbuffer [(position +uint (i ))&ringbuffer_mask ]]
literal_costs [i +1 ] = literal_costs [i ] + literal_carry
literal_carry -= literal_costs [i +1 ] - literal_costs [i ]
}
}
}
func zopfliCostModelSetFromLiteralCosts(self *zopfliCostModel , position uint , ringbuffer []byte , ringbuffer_mask uint ) {
var literal_costs []float32 = self .literal_costs_
var literal_carry float32 = 0.0
var cost_dist []float32 = self .cost_dist_
var cost_cmd []float32 = self .cost_cmd_ [:]
var num_bytes uint = self .num_bytes_
var i uint
estimateBitCostsForLiterals (position , num_bytes , ringbuffer_mask , ringbuffer , literal_costs [1 :])
literal_costs [0 ] = 0.0
for i = 0 ; i < num_bytes ; i ++ {
literal_carry += literal_costs [i +1 ]
literal_costs [i +1 ] = literal_costs [i ] + literal_carry
literal_carry -= literal_costs [i +1 ] - literal_costs [i ]
}
for i = 0 ; i < numCommandSymbols ; i ++ {
cost_cmd [i ] = float32 (fastLog2 (uint (11 + uint32 (i ))))
}
for i = 0 ; uint32 (i ) < self .distance_histogram_size ; i ++ {
cost_dist [i ] = float32 (fastLog2 (uint (20 + uint32 (i ))))
}
self .min_cost_cmd_ = float32 (fastLog2 (11 ))
}
func zopfliCostModelGetCommandCost(self *zopfliCostModel , cmdcode uint16 ) float32 {
return self .cost_cmd_ [cmdcode ]
}
func zopfliCostModelGetDistanceCost(self *zopfliCostModel , distcode uint ) float32 {
return self .cost_dist_ [distcode ]
}
func zopfliCostModelGetLiteralCosts(self *zopfliCostModel , from uint , to uint ) float32 {
return self .literal_costs_ [to ] - self .literal_costs_ [from ]
}
func zopfliCostModelGetMinCostCmd(self *zopfliCostModel ) float32 {
return self .min_cost_cmd_
}
func updateZopfliNode(nodes []zopfliNode , pos uint , start_pos uint , len uint , len_code uint , dist uint , short_code uint , cost float32 ) {
var next *zopfliNode = &nodes [pos +len ]
next .length = uint32 (len | (len +9 -len_code )<<25 )
next .distance = uint32 (dist )
next .dcode_insert_length = uint32 (short_code <<27 | (pos - start_pos ))
next .u .cost = cost
}
type posData struct {
pos uint
distance_cache [4 ]int
costdiff float32
cost float32
}
type startPosQueue struct {
q_ [8 ]posData
idx_ uint
}
func initStartPosQueue(self *startPosQueue ) {
self .idx_ = 0
}
func startPosQueueSize(self *startPosQueue ) uint {
return brotli_min_size_t (self .idx_ , 8 )
}
func startPosQueuePush(self *startPosQueue , posdata *posData ) {
var offset uint = ^(self .idx_ ) & 7
self .idx_ ++
var len uint = startPosQueueSize (self )
var i uint
var q []posData = self .q_ [:]
q [offset ] = *posdata
for i = 1 ; i < len ; i ++ {
if q [offset &7 ].costdiff > q [(offset +1 )&7 ].costdiff {
var tmp posData = q [offset &7 ]
q [offset &7 ] = q [(offset +1 )&7 ]
q [(offset +1 )&7 ] = tmp
}
offset ++
}
}
func startPosQueueAt(self *startPosQueue , k uint ) *posData {
return &self .q_ [(k -self .idx_ )&7 ]
}
func computeMinimumCopyLength(start_cost float32 , nodes []zopfliNode , num_bytes uint , pos uint ) uint {
var min_cost float32 = start_cost
var len uint = 2
var next_len_bucket uint = 4
var next_len_offset uint = 10
for pos +len <= num_bytes && nodes [pos +len ].u .cost <= min_cost {
len ++
if len == next_len_offset {
min_cost += 1.0
next_len_offset += next_len_bucket
next_len_bucket *= 2
}
}
return uint (len )
}
func computeDistanceShortcut(block_start uint , pos uint , max_backward_limit uint , gap uint , nodes []zopfliNode ) uint32 {
var clen uint = uint (zopfliNodeCopyLength (&nodes [pos ]))
var ilen uint = uint (nodes [pos ].dcode_insert_length & 0x7FFFFFF )
var dist uint = uint (zopfliNodeCopyDistance (&nodes [pos ]))
if pos == 0 {
return 0
} else if dist +clen <= block_start +pos +gap && dist <= max_backward_limit +gap && zopfliNodeDistanceCode (&nodes [pos ]) > 0 {
return uint32 (pos )
} else {
return nodes [pos -clen -ilen ].u .shortcut
}
}
func computeDistanceCache(pos uint , starting_dist_cache []int , nodes []zopfliNode , dist_cache []int ) {
var idx int = 0
var p uint = uint (nodes [pos ].u .shortcut )
for idx < 4 && p > 0 {
var ilen uint = uint (nodes [p ].dcode_insert_length & 0x7FFFFFF )
var clen uint = uint (zopfliNodeCopyLength (&nodes [p ]))
var dist uint = uint (zopfliNodeCopyDistance (&nodes [p ]))
dist_cache [idx ] = int (dist )
idx ++
p = uint (nodes [p -clen -ilen ].u .shortcut )
}
for ; idx < 4 ; idx ++ {
dist_cache [idx ] = starting_dist_cache [0 ]
starting_dist_cache = starting_dist_cache [1 :]
}
}
func evaluateNode(block_start uint , pos uint , max_backward_limit uint , gap uint , starting_dist_cache []int , model *zopfliCostModel , queue *startPosQueue , nodes []zopfliNode ) {
var node_cost float32 = nodes [pos ].u .cost
nodes [pos ].u .shortcut = computeDistanceShortcut (block_start , pos , max_backward_limit , gap , nodes )
if node_cost <= zopfliCostModelGetLiteralCosts (model , 0 , pos ) {
var posdata posData
posdata .pos = pos
posdata .cost = node_cost
posdata .costdiff = node_cost - zopfliCostModelGetLiteralCosts (model , 0 , pos )
computeDistanceCache (pos , starting_dist_cache , nodes , posdata .distance_cache [:])
startPosQueuePush (queue , &posdata )
}
}
func updateNodes(num_bytes uint , block_start uint , pos uint , ringbuffer []byte , ringbuffer_mask uint , params *encoderParams , max_backward_limit uint , starting_dist_cache []int , num_matches uint , matches []backwardMatch , model *zopfliCostModel , queue *startPosQueue , nodes []zopfliNode ) uint {
var cur_ix uint = block_start + pos
var cur_ix_masked uint = cur_ix & ringbuffer_mask
var max_distance uint = brotli_min_size_t (cur_ix , max_backward_limit )
var max_len uint = num_bytes - pos
var max_zopfli_len uint = maxZopfliLen (params )
var max_iters uint = maxZopfliCandidates (params )
var min_len uint
var result uint = 0
var k uint
var gap uint = 0
evaluateNode (block_start , pos , max_backward_limit , gap , starting_dist_cache , model , queue , nodes )
{
var posdata *posData = startPosQueueAt (queue , 0 )
var min_cost float32 = (posdata .cost + zopfliCostModelGetMinCostCmd (model ) + zopfliCostModelGetLiteralCosts (model , posdata .pos , pos ))
min_len = computeMinimumCopyLength (min_cost , nodes , num_bytes , pos )
}
for k = 0 ; k < max_iters && k < startPosQueueSize (queue ); k ++ {
var posdata *posData = startPosQueueAt (queue , k )
var start uint = posdata .pos
var inscode uint16 = getInsertLengthCode (pos - start )
var start_costdiff float32 = posdata .costdiff
var base_cost float32 = start_costdiff + float32 (getInsertExtra (inscode )) + zopfliCostModelGetLiteralCosts (model , 0 , pos )
var best_len uint = min_len - 1
var j uint = 0
for ; j < numDistanceShortCodes && best_len < max_len ; j ++ {
var idx uint = uint (kDistanceCacheIndex [j ])
var backward uint = uint (posdata .distance_cache [idx ] + kDistanceCacheOffset [j ])
var prev_ix uint = cur_ix - backward
var len uint = 0
var continuation byte = ringbuffer [cur_ix_masked +best_len ]
if cur_ix_masked +best_len > ringbuffer_mask {
break
}
if backward > max_distance +gap {
continue
}
if backward <= max_distance {
if prev_ix >= cur_ix {
continue
}
prev_ix &= ringbuffer_mask
if prev_ix +best_len > ringbuffer_mask || continuation != ringbuffer [prev_ix +best_len ] {
continue
}
len = findMatchLengthWithLimit (ringbuffer [prev_ix :], ringbuffer [cur_ix_masked :], max_len )
} else {
continue
}
{
var dist_cost float32 = base_cost + zopfliCostModelGetDistanceCost (model , j )
var l uint
for l = best_len + 1 ; l <= len ; l ++ {
var copycode uint16 = getCopyLengthCode (l )
var cmdcode uint16 = combineLengthCodes (inscode , copycode , j == 0 )
var tmp float32
if cmdcode < 128 {
tmp = base_cost
} else {
tmp = dist_cost
}
var cost float32 = tmp + float32 (getCopyExtra (copycode )) + zopfliCostModelGetCommandCost (model , cmdcode )
if cost < nodes [pos +l ].u .cost {
updateZopfliNode (nodes , pos , start , l , l , backward , j +1 , cost )
result = brotli_max_size_t (result , l )
}
best_len = l
}
}
}
if k >= 2 {
continue
}
{
var len uint = min_len
for j = 0 ; j < num_matches ; j ++ {
var match backwardMatch = matches [j ]
var dist uint = uint (match .distance )
var is_dictionary_match bool = (dist > max_distance +gap )
var dist_code uint = dist + numDistanceShortCodes - 1
var dist_symbol uint16
var distextra uint32
var distnumextra uint32
var dist_cost float32
var max_match_len uint
prefixEncodeCopyDistance (dist_code , uint (params .dist .num_direct_distance_codes ), uint (params .dist .distance_postfix_bits ), &dist_symbol , &distextra )
distnumextra = uint32 (dist_symbol ) >> 10
dist_cost = base_cost + float32 (distnumextra ) + zopfliCostModelGetDistanceCost (model , uint (dist_symbol )&0x3FF )
max_match_len = backwardMatchLength (&match )
if len < max_match_len && (is_dictionary_match || max_match_len > max_zopfli_len ) {
len = max_match_len
}
for ; len <= max_match_len ; len ++ {
var len_code uint
if is_dictionary_match {
len_code = backwardMatchLengthCode (&match )
} else {
len_code = len
}
var copycode uint16 = getCopyLengthCode (len_code )
var cmdcode uint16 = combineLengthCodes (inscode , copycode , false )
var cost float32 = dist_cost + float32 (getCopyExtra (copycode )) + zopfliCostModelGetCommandCost (model , cmdcode )
if cost < nodes [pos +len ].u .cost {
updateZopfliNode (nodes , pos , start , uint (len ), len_code , dist , 0 , cost )
if len > result {
result = len
}
}
}
}
}
}
return result
}
func computeShortestPathFromNodes(num_bytes uint , nodes []zopfliNode ) uint {
var index uint = num_bytes
var num_commands uint = 0
for nodes [index ].dcode_insert_length &0x7FFFFFF == 0 && nodes [index ].length == 1 {
index --
}
nodes [index ].u .next = math .MaxUint32
for index != 0 {
var len uint = uint (zopfliNodeCommandLength (&nodes [index ]))
index -= uint (len )
nodes [index ].u .next = uint32 (len )
num_commands ++
}
return num_commands
}
func zopfliCreateCommands(num_bytes uint , block_start uint , nodes []zopfliNode , dist_cache []int , last_insert_len *uint , params *encoderParams , commands *[]command , num_literals *uint ) {
var max_backward_limit uint = maxBackwardLimit (params .lgwin )
var pos uint = 0
var offset uint32 = nodes [0 ].u .next
var i uint
var gap uint = 0
for i = 0 ; offset != math .MaxUint32 ; i ++ {
var next *zopfliNode = &nodes [uint32 (pos )+offset ]
var copy_length uint = uint (zopfliNodeCopyLength (next ))
var insert_length uint = uint (next .dcode_insert_length & 0x7FFFFFF )
pos += insert_length
offset = next .u .next
if i == 0 {
insert_length += *last_insert_len
*last_insert_len = 0
}
{
var distance uint = uint (zopfliNodeCopyDistance (next ))
var len_code uint = uint (zopfliNodeLengthCode (next ))
var max_distance uint = brotli_min_size_t (block_start +pos , max_backward_limit )
var is_dictionary bool = (distance > max_distance +gap )
var dist_code uint = uint (zopfliNodeDistanceCode (next ))
*commands = append (*commands , makeCommand (¶ms .dist , insert_length , copy_length , int (len_code )-int (copy_length ), dist_code ))
if !is_dictionary && dist_code > 0 {
dist_cache [3 ] = dist_cache [2 ]
dist_cache [2 ] = dist_cache [1 ]
dist_cache [1 ] = dist_cache [0 ]
dist_cache [0 ] = int (distance )
}
}
*num_literals += insert_length
pos += copy_length
}
*last_insert_len += num_bytes - pos
}
func zopfliIterate(num_bytes uint , position uint , ringbuffer []byte , ringbuffer_mask uint , params *encoderParams , gap uint , dist_cache []int , model *zopfliCostModel , num_matches []uint32 , matches []backwardMatch , nodes []zopfliNode ) uint {
var max_backward_limit uint = maxBackwardLimit (params .lgwin )
var max_zopfli_len uint = maxZopfliLen (params )
var queue startPosQueue
var cur_match_pos uint = 0
var i uint
nodes [0 ].length = 0
nodes [0 ].u .cost = 0
initStartPosQueue (&queue )
for i = 0 ; i +3 < num_bytes ; i ++ {
var skip uint = updateNodes (num_bytes , position , i , ringbuffer , ringbuffer_mask , params , max_backward_limit , dist_cache , uint (num_matches [i ]), matches [cur_match_pos :], model , &queue , nodes )
if skip < longCopyQuickStep {
skip = 0
}
cur_match_pos += uint (num_matches [i ])
if num_matches [i ] == 1 && backwardMatchLength (&matches [cur_match_pos -1 ]) > max_zopfli_len {
skip = brotli_max_size_t (backwardMatchLength (&matches [cur_match_pos -1 ]), skip )
}
if skip > 1 {
skip --
for skip != 0 {
i ++
if i +3 >= num_bytes {
break
}
evaluateNode (position , i , max_backward_limit , gap , dist_cache , model , &queue , nodes )
cur_match_pos += uint (num_matches [i ])
skip --
}
}
}
return computeShortestPathFromNodes (num_bytes , nodes )
}
func zopfliComputeShortestPath(num_bytes uint , position uint , ringbuffer []byte , ringbuffer_mask uint , params *encoderParams , dist_cache []int , hasher *h10 , nodes []zopfliNode ) uint {
var max_backward_limit uint = maxBackwardLimit (params .lgwin )
var max_zopfli_len uint = maxZopfliLen (params )
var model zopfliCostModel
var queue startPosQueue
var matches [2 * (maxNumMatchesH10 + 64 )]backwardMatch
var store_end uint
if num_bytes >= hasher .StoreLookahead () {
store_end = position + num_bytes - hasher .StoreLookahead () + 1
} else {
store_end = position
}
var i uint
var gap uint = 0
var lz_matches_offset uint = 0
nodes [0 ].length = 0
nodes [0 ].u .cost = 0
initZopfliCostModel (&model , ¶ms .dist , num_bytes )
zopfliCostModelSetFromLiteralCosts (&model , position , ringbuffer , ringbuffer_mask )
initStartPosQueue (&queue )
for i = 0 ; i +hasher .HashTypeLength ()-1 < num_bytes ; i ++ {
var pos uint = position + i
var max_distance uint = brotli_min_size_t (pos , max_backward_limit )
var skip uint
var num_matches uint
num_matches = findAllMatchesH10 (hasher , ¶ms .dictionary , ringbuffer , ringbuffer_mask , pos , num_bytes -i , max_distance , gap , params , matches [lz_matches_offset :])
if num_matches > 0 && backwardMatchLength (&matches [num_matches -1 ]) > max_zopfli_len {
matches [0 ] = matches [num_matches -1 ]
num_matches = 1
}
skip = updateNodes (num_bytes , position , i , ringbuffer , ringbuffer_mask , params , max_backward_limit , dist_cache , num_matches , matches [:], &model , &queue , nodes )
if skip < longCopyQuickStep {
skip = 0
}
if num_matches == 1 && backwardMatchLength (&matches [0 ]) > max_zopfli_len {
skip = brotli_max_size_t (backwardMatchLength (&matches [0 ]), skip )
}
if skip > 1 {
hasher .StoreRange (ringbuffer , ringbuffer_mask , pos +1 , brotli_min_size_t (pos +skip , store_end ))
skip --
for skip != 0 {
i ++
if i +hasher .HashTypeLength ()-1 >= num_bytes {
break
}
evaluateNode (position , i , max_backward_limit , gap , dist_cache , &model , &queue , nodes )
skip --
}
}
}
cleanupZopfliCostModel (&model )
return computeShortestPathFromNodes (num_bytes , nodes )
}
func createZopfliBackwardReferences(num_bytes uint , position uint , ringbuffer []byte , ringbuffer_mask uint , params *encoderParams , hasher *h10 , dist_cache []int , last_insert_len *uint , commands *[]command , num_literals *uint ) {
var nodes []zopfliNode
nodes = make ([]zopfliNode , (num_bytes + 1 ))
initZopfliNodes (nodes , num_bytes +1 )
zopfliComputeShortestPath (num_bytes , position , ringbuffer , ringbuffer_mask , params , dist_cache , hasher , nodes )
zopfliCreateCommands (num_bytes , position , nodes , dist_cache , last_insert_len , params , commands , num_literals )
nodes = nil
}
func createHqZopfliBackwardReferences(num_bytes uint , position uint , ringbuffer []byte , ringbuffer_mask uint , params *encoderParams , hasher hasherHandle , dist_cache []int , last_insert_len *uint , commands *[]command , num_literals *uint ) {
var max_backward_limit uint = maxBackwardLimit (params .lgwin )
var num_matches []uint32 = make ([]uint32 , num_bytes )
var matches_size uint = 4 * num_bytes
var store_end uint
if num_bytes >= hasher .StoreLookahead () {
store_end = position + num_bytes - hasher .StoreLookahead () + 1
} else {
store_end = position
}
var cur_match_pos uint = 0
var i uint
var orig_num_literals uint
var orig_last_insert_len uint
var orig_dist_cache [4 ]int
var orig_num_commands int
var model zopfliCostModel
var nodes []zopfliNode
var matches []backwardMatch = make ([]backwardMatch , matches_size )
var gap uint = 0
var shadow_matches uint = 0
var new_array []backwardMatch
for i = 0 ; i +hasher .HashTypeLength ()-1 < num_bytes ; i ++ {
var pos uint = position + i
var max_distance uint = brotli_min_size_t (pos , max_backward_limit )
var max_length uint = num_bytes - i
var num_found_matches uint
var cur_match_end uint
var j uint
if matches_size < cur_match_pos +maxNumMatchesH10 +shadow_matches {
var new_size uint = matches_size
if new_size == 0 {
new_size = cur_match_pos + maxNumMatchesH10 + shadow_matches
}
for new_size < cur_match_pos +maxNumMatchesH10 +shadow_matches {
new_size *= 2
}
new_array = make ([]backwardMatch , new_size )
if matches_size != 0 {
copy (new_array , matches [:matches_size ])
}
matches = new_array
matches_size = new_size
}
num_found_matches = findAllMatchesH10 (hasher .(*h10 ), ¶ms .dictionary , ringbuffer , ringbuffer_mask , pos , max_length , max_distance , gap , params , matches [cur_match_pos +shadow_matches :])
cur_match_end = cur_match_pos + num_found_matches
for j = cur_match_pos ; j +1 < cur_match_end ; j ++ {
assert (backwardMatchLength (&matches [j ]) <= backwardMatchLength (&matches [j +1 ]))
}
num_matches [i ] = uint32 (num_found_matches )
if num_found_matches > 0 {
var match_len uint = backwardMatchLength (&matches [cur_match_end -1 ])
if match_len > maxZopfliLenQuality11 {
var skip uint = match_len - 1
matches [cur_match_pos ] = matches [cur_match_end -1 ]
cur_match_pos ++
num_matches [i ] = 1
hasher .StoreRange (ringbuffer , ringbuffer_mask , pos +1 , brotli_min_size_t (pos +match_len , store_end ))
var pos uint = i
for i := 0 ; i < int (skip ); i ++ {
num_matches [pos +1 :][i ] = 0
}
i += skip
} else {
cur_match_pos = cur_match_end
}
}
}
orig_num_literals = *num_literals
orig_last_insert_len = *last_insert_len
copy (orig_dist_cache [:], dist_cache [:4 ])
orig_num_commands = len (*commands )
nodes = make ([]zopfliNode , (num_bytes + 1 ))
initZopfliCostModel (&model , ¶ms .dist , num_bytes )
for i = 0 ; i < 2 ; i ++ {
initZopfliNodes (nodes , num_bytes +1 )
if i == 0 {
zopfliCostModelSetFromLiteralCosts (&model , position , ringbuffer , ringbuffer_mask )
} else {
zopfliCostModelSetFromCommands (&model , position , ringbuffer , ringbuffer_mask , (*commands )[orig_num_commands :], orig_last_insert_len )
}
*commands = (*commands )[:orig_num_commands ]
*num_literals = orig_num_literals
*last_insert_len = orig_last_insert_len
copy (dist_cache , orig_dist_cache [:4 ])
zopfliIterate (num_bytes , position , ringbuffer , ringbuffer_mask , params , gap , dist_cache , &model , num_matches , matches , nodes )
zopfliCreateCommands (num_bytes , position , nodes , dist_cache , last_insert_len , params , commands , num_literals )
}
cleanupZopfliCostModel (&model )
nodes = nil
matches = nil
num_matches = nil
}
The pages are generated with Golds v0.6.7 . (GOOS=linux GOARCH=amd64)
Golds is a Go 101 project developed by Tapir Liu .
PR and bug reports are welcome and can be submitted to the issue list .
Please follow @Go100and1 (reachable from the left QR code) to get the latest news of Golds .