1// Copyright 2015, Joe Tsai. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE.md file.
4
5package xflate
6
7const (
8	unknownType = iota
9	deflateType
10	indexType
11	footerType
12)
13
14type index struct {
15	// Records is a list of records that indicate the location of all chunks
16	// in the stream. However, rather than recording the starting offset of
17	// each chunk, only the ending offsets are recorded.
18	//
19	// The starting record {0, 0} is not included since it is implied.
20	// The last record effectively holds the total size of the stream.
21	Records []record
22
23	BackSize  int64 // Size of previous index when encoded
24	IndexSize int64 // Size of this index when encoded
25}
26
27type record struct {
28	CompOffset int64 // Offset in compressed stream where decompression can start from
29	RawOffset  int64 // The uncompressed offset that CompOffset is associated with
30	Type       int   // Type of the record
31}
32
33// Reset resets the index.
34func (idx *index) Reset() {
35	*idx = index{Records: idx.Records[:0]}
36}
37
38// AppendRecord appends a new record to the end of the index and reports whether
39// the operation was successful or not.
40func (idx *index) AppendRecord(compSize, rawSize int64, typ int) bool {
41	if rawSize < 0 || compSize < 0 {
42		return false // Invalid size
43	}
44
45	lastRec := idx.LastRecord()
46	rec := record{
47		CompOffset: lastRec.CompOffset + compSize,
48		RawOffset:  lastRec.RawOffset + rawSize,
49		Type:       typ,
50	}
51	if rec.CompOffset < lastRec.CompOffset || rec.RawOffset < lastRec.RawOffset {
52		return false // Overflow detected
53	}
54	idx.Records = append(idx.Records, rec)
55	return true
56}
57
58// AppendIndex appends the contents of another index onto the current receiver
59// and reports whether the operation was successful or not.
60func (idx *index) AppendIndex(other *index) bool {
61	var preRec record
62	for i, rec := range other.Records {
63		csize, rsize := rec.CompOffset-preRec.CompOffset, rec.RawOffset-preRec.RawOffset
64		if !idx.AppendRecord(csize, rsize, rec.Type) {
65			idx.Records = idx.Records[:len(idx.Records)-i] // Ensure atomic append
66			return false
67		}
68		preRec = rec
69	}
70	return true
71}
72
73// Search searches for the record that best matches the raw offset given.
74// This search will return the location of the record with the lowest
75// RawOffset that is still greater than the given offset.
76// It return -1 if such a record does not exist.
77//
78// This method is intended to be used in conjunction with GetRecords,
79// which returns a pair of records (prev, curr).
80// With these records, the following can be computed:
81//
82//	// Where in the underlying reader the decompressor should start from.
83//	compOffset := prev.CompOffset
84//
85//	// The total number of uncompressed bytes to discard to reach offset.
86//	rawDiscard := offset - prev.RawOffset
87//
88//	// The total compressed size of the current block.
89//	compSize := curr.CompOffset - prev.CompOffset
90//
91//	// The total uncompressed size of the current block.
92//	rawSize := curr.RawOffset - prev.RawOffset
93//
94func (idx *index) Search(offset int64) int {
95	recs := idx.Records
96	i, imin, imax := -1, 0, len(recs)-1
97	for imax >= imin && i == -1 {
98		imid := (imin + imax) / 2
99		gteCurr := bool(offset >= recs[imid].RawOffset)
100		ltNext := bool(imid+1 >= len(recs) || offset < recs[imid+1].RawOffset)
101		if gteCurr && ltNext {
102			i = imid
103		} else if gteCurr {
104			imin = imid + 1
105		} else {
106			imax = imid - 1
107		}
108	}
109	return i + 1
110}
111
112// GetRecords returns the previous and current records at the given position.
113// This method will automatically bind the search position within the bounds
114// of the index. Thus, this will return zero value records if the position is
115// too low, and the last record if the value is too high.
116func (idx *index) GetRecords(i int) (prev, curr record) {
117	recs := idx.Records
118	if i > len(recs) {
119		i = len(recs)
120	}
121	if i-1 >= 0 && i-1 < len(recs) {
122		prev = recs[i-1]
123	}
124	if i >= 0 && i < len(recs) {
125		curr = recs[i]
126	} else {
127		curr = prev
128		curr.Type = unknownType
129	}
130	return prev, curr
131}
132
133// LastRecord returns the last record if it exists, otherwise the zero value.
134func (idx *index) LastRecord() record {
135	var rec record
136	if len(idx.Records) > 0 {
137		rec = idx.Records[len(idx.Records)-1]
138	}
139	return rec
140}
141