forked from dsnet/compress
/
index.go
140 lines (128 loc) · 4.14 KB
/
index.go
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
// Copyright 2015, Joe Tsai. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE.md file.
package xflate
const (
unknownType = iota
deflateType
indexType
footerType
)
type index struct {
// Records is a list of records that indicate the location of all chunks
// in the stream. However, rather than recording the starting offset of
// each chunk, only the ending offsets are recorded.
//
// The starting record {0, 0} is not included since it is implied.
// The last record effectively holds the total size of the stream.
Records []record
BackSize int64 // Size of previous index when encoded
IndexSize int64 // Size of this index when encoded
}
type record struct {
CompOffset int64 // Offset in compressed stream where decompression can start from
RawOffset int64 // The uncompressed offset that CompOffset is associated with
Type int // Type of the record
}
// Reset resets the index.
func (idx *index) Reset() {
*idx = index{Records: idx.Records[:0]}
}
// AppendRecord appends a new record to the end of the index and reports whether
// the operation was successful or not.
func (idx *index) AppendRecord(compSize, rawSize int64, typ int) bool {
if rawSize < 0 || compSize < 0 {
return false // Invalid size
}
lastRec := idx.LastRecord()
rec := record{
CompOffset: lastRec.CompOffset + compSize,
RawOffset: lastRec.RawOffset + rawSize,
Type: typ,
}
if rec.CompOffset < lastRec.CompOffset || rec.RawOffset < lastRec.RawOffset {
return false // Overflow detected
}
idx.Records = append(idx.Records, rec)
return true
}
// AppendIndex appends the contents of another index onto the current receiver
// and reports whether the operation was successful or not.
func (idx *index) AppendIndex(other *index) bool {
var preRec record
for i, rec := range other.Records {
csize, rsize := rec.CompOffset-preRec.CompOffset, rec.RawOffset-preRec.RawOffset
if !idx.AppendRecord(csize, rsize, rec.Type) {
idx.Records = idx.Records[:len(idx.Records)-i] // Ensure atomic append
return false
}
preRec = rec
}
return true
}
// Search searches for the record that best matches the raw offset given.
// This search will return the location of the record with the lowest
// RawOffset that is still greater than the given offset.
// It return -1 if such a record does not exist.
//
// This method is intended to be used in conjunction with GetRecords,
// which returns a pair of records (prev, curr).
// With these records, the following can be computed:
//
// // Where in the underlying reader the decompressor should start from.
// compOffset := prev.CompOffset
//
// // The total number of uncompressed bytes to discard to reach offset.
// rawDiscard := offset - prev.RawOffset
//
// // The total compressed size of the current block.
// compSize := curr.CompOffset - prev.CompOffset
//
// // The total uncompressed size of the current block.
// rawSize := curr.RawOffset - prev.RawOffset
//
func (idx *index) Search(offset int64) int {
recs := idx.Records
i, imin, imax := -1, 0, len(recs)-1
for imax >= imin && i == -1 {
imid := (imin + imax) / 2
gteCurr := bool(offset >= recs[imid].RawOffset)
ltNext := bool(imid+1 >= len(recs) || offset < recs[imid+1].RawOffset)
if gteCurr && ltNext {
i = imid
} else if gteCurr {
imin = imid + 1
} else {
imax = imid - 1
}
}
return i + 1
}
// GetRecords returns the previous and current records at the given position.
// This method will automatically bind the search position within the bounds
// of the index. Thus, this will return zero value records if the position is
// too low, and the last record if the value is too high.
func (idx *index) GetRecords(i int) (prev, curr record) {
recs := idx.Records
if i > len(recs) {
i = len(recs)
}
if i-1 >= 0 && i-1 < len(recs) {
prev = recs[i-1]
}
if i >= 0 && i < len(recs) {
curr = recs[i]
} else {
curr = prev
curr.Type = unknownType
}
return prev, curr
}
// LastRecord returns the last record if it exists, otherwise the zero value.
func (idx *index) LastRecord() record {
var rec record
if len(idx.Records) > 0 {
rec = idx.Records[len(idx.Records)-1]
}
return rec
}