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