1 /*
<lambda>null2 * Copyright (C) 2019 Square, Inc.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 // TODO move to SegmentedByteString class: https://youtrack.jetbrains.com/issue/KT-20427
18 @file:Suppress("NOTHING_TO_INLINE")
19
20 @file:JvmName("-SegmentedByteString") // A leading '-' hides this class from Java.
21
22 package okio.internal
23
24 import kotlin.jvm.JvmName
25 import okio.Buffer
26 import okio.ByteString
27 import okio.Segment
28 import okio.SegmentedByteString
29 import okio.arrayRangeEquals
30 import okio.checkOffsetAndCount
31 import okio.resolveDefaultParameter
32
33 internal fun IntArray.binarySearch(value: Int, fromIndex: Int, toIndex: Int): Int {
34 var left = fromIndex
35 var right = toIndex - 1
36
37 while (left <= right) {
38 val mid = (left + right) ushr 1 // protect from overflow
39 val midVal = this[mid]
40
41 when {
42 midVal < value -> left = mid + 1
43 midVal > value -> right = mid - 1
44 else -> return mid
45 }
46 }
47
48 // no exact match, return negative of where it should match
49 return -left - 1
50 }
51
52 /** Returns the index of the segment that contains the byte at `pos`. */
segmentnull53 internal fun SegmentedByteString.segment(pos: Int): Int {
54 // Search for (pos + 1) instead of (pos) because the directory holds sizes, not indexes.
55 val i = directory.binarySearch(pos + 1, 0, segments.size)
56 return if (i >= 0) i else i.inv() // If i is negative, bitflip to get the insert position.
57 }
58
59 /** Processes all segments, invoking `action` with the ByteArray and range of valid data. */
forEachSegmentnull60 internal inline fun SegmentedByteString.forEachSegment(
61 action: (data: ByteArray, offset: Int, byteCount: Int) -> Unit,
62 ) {
63 val segmentCount = segments.size
64 var s = 0
65 var pos = 0
66 while (s < segmentCount) {
67 val segmentPos = directory[segmentCount + s]
68 val nextSegmentOffset = directory[s]
69
70 action(segments[s], segmentPos, nextSegmentOffset - pos)
71 pos = nextSegmentOffset
72 s++
73 }
74 }
75
76 /**
77 * Processes the segments between `beginIndex` and `endIndex`, invoking `action` with the ByteArray
78 * and range of the valid data.
79 */
forEachSegmentnull80 private inline fun SegmentedByteString.forEachSegment(
81 beginIndex: Int,
82 endIndex: Int,
83 action: (data: ByteArray, offset: Int, byteCount: Int) -> Unit,
84 ) {
85 var s = segment(beginIndex)
86 var pos = beginIndex
87 while (pos < endIndex) {
88 val segmentOffset = if (s == 0) 0 else directory[s - 1]
89 val segmentSize = directory[s] - segmentOffset
90 val segmentPos = directory[segments.size + s]
91
92 val byteCount = minOf(endIndex, segmentOffset + segmentSize) - pos
93 val offset = segmentPos + (pos - segmentOffset)
94 action(segments[s], offset, byteCount)
95 pos += byteCount
96 s++
97 }
98 }
99
100 // TODO Kotlin's expect classes can't have default implementations, so platform implementations
101 // have to call these functions. Remove all this nonsense when expect class allow actual code.
102
commonSubstringnull103 internal inline fun SegmentedByteString.commonSubstring(beginIndex: Int, endIndex: Int): ByteString {
104 val endIndex = resolveDefaultParameter(endIndex)
105 require(beginIndex >= 0) { "beginIndex=$beginIndex < 0" }
106 require(endIndex <= size) { "endIndex=$endIndex > length($size)" }
107
108 val subLen = endIndex - beginIndex
109 require(subLen >= 0) { "endIndex=$endIndex < beginIndex=$beginIndex" }
110
111 when {
112 beginIndex == 0 && endIndex == size -> return this
113 beginIndex == endIndex -> return ByteString.EMPTY
114 }
115
116 val beginSegment = segment(beginIndex) // First segment to include
117 val endSegment = segment(endIndex - 1) // Last segment to include
118
119 val newSegments = segments.copyOfRange(beginSegment, endSegment + 1)
120 val newDirectory = IntArray(newSegments.size * 2)
121 var index = 0
122 for (s in beginSegment..endSegment) {
123 newDirectory[index] = minOf(directory[s] - beginIndex, subLen)
124 newDirectory[index++ + newSegments.size] = directory[s + segments.size]
125 }
126
127 // Set the new position of the first segment
128 val segmentOffset = if (beginSegment == 0) 0 else directory[beginSegment - 1]
129 newDirectory[newSegments.size] += beginIndex - segmentOffset
130
131 return SegmentedByteString(newSegments, newDirectory)
132 }
133
commonInternalGetnull134 internal inline fun SegmentedByteString.commonInternalGet(pos: Int): Byte {
135 checkOffsetAndCount(directory[segments.size - 1].toLong(), pos.toLong(), 1)
136 val segment = segment(pos)
137 val segmentOffset = if (segment == 0) 0 else directory[segment - 1]
138 val segmentPos = directory[segment + segments.size]
139 return segments[segment][pos - segmentOffset + segmentPos]
140 }
141
commonGetSizenull142 internal inline fun SegmentedByteString.commonGetSize() = directory[segments.size - 1]
143
144 internal inline fun SegmentedByteString.commonToByteArray(): ByteArray {
145 val result = ByteArray(size)
146 var resultPos = 0
147 forEachSegment { data, offset, byteCount ->
148 data.copyInto(
149 result,
150 destinationOffset = resultPos,
151 startIndex = offset,
152 endIndex = offset + byteCount,
153 )
154 resultPos += byteCount
155 }
156 return result
157 }
158
commonWritenull159 internal inline fun SegmentedByteString.commonWrite(buffer: Buffer, offset: Int, byteCount: Int) {
160 forEachSegment(offset, offset + byteCount) { data, offset, byteCount ->
161 val segment = Segment(data, offset, offset + byteCount, true, false)
162 if (buffer.head == null) {
163 segment.prev = segment
164 segment.next = segment.prev
165 buffer.head = segment.next
166 } else {
167 buffer.head!!.prev!!.push(segment)
168 }
169 }
170 buffer.size += byteCount
171 }
172
commonRangeEqualsnull173 internal inline fun SegmentedByteString.commonRangeEquals(
174 offset: Int,
175 other: ByteString,
176 otherOffset: Int,
177 byteCount: Int,
178 ): Boolean {
179 if (offset < 0 || offset > size - byteCount) return false
180 // Go segment-by-segment through this, passing arrays to other's rangeEquals().
181 var otherOffset = otherOffset
182 forEachSegment(offset, offset + byteCount) { data, offset, byteCount ->
183 if (!other.rangeEquals(otherOffset, data, offset, byteCount)) return false
184 otherOffset += byteCount
185 }
186 return true
187 }
188
commonRangeEqualsnull189 internal inline fun SegmentedByteString.commonRangeEquals(
190 offset: Int,
191 other: ByteArray,
192 otherOffset: Int,
193 byteCount: Int,
194 ): Boolean {
195 if (offset < 0 || offset > size - byteCount ||
196 otherOffset < 0 || otherOffset > other.size - byteCount
197 ) {
198 return false
199 }
200 // Go segment-by-segment through this, comparing ranges of arrays.
201 var otherOffset = otherOffset
202 forEachSegment(offset, offset + byteCount) { data, offset, byteCount ->
203 if (!arrayRangeEquals(data, offset, other, otherOffset, byteCount)) return false
204 otherOffset += byteCount
205 }
206 return true
207 }
208
commonCopyIntonull209 internal inline fun SegmentedByteString.commonCopyInto(
210 offset: Int,
211 target: ByteArray,
212 targetOffset: Int,
213 byteCount: Int,
214 ) {
215 checkOffsetAndCount(size.toLong(), offset.toLong(), byteCount.toLong())
216 checkOffsetAndCount(target.size.toLong(), targetOffset.toLong(), byteCount.toLong())
217 // Go segment-by-segment through this, copying ranges of arrays.
218 var targetOffset = targetOffset
219 forEachSegment(offset, offset + byteCount) { data, offset, byteCount ->
220 data.copyInto(target, targetOffset, offset, offset + byteCount)
221 targetOffset += byteCount
222 }
223 }
224
commonEqualsnull225 internal inline fun SegmentedByteString.commonEquals(other: Any?): Boolean {
226 return when {
227 other === this -> true
228 other is ByteString -> other.size == size && rangeEquals(0, other, 0, size)
229 else -> false
230 }
231 }
232
commonHashCodenull233 internal inline fun SegmentedByteString.commonHashCode(): Int {
234 var result = hashCode
235 if (result != 0) return result
236
237 // Equivalent to Arrays.hashCode(toByteArray()).
238 result = 1
239 forEachSegment { data, offset, byteCount ->
240 var i = offset
241 val limit = offset + byteCount
242 while (i < limit) {
243 result = 31 * result + data[i]
244 i++
245 }
246 }
247 hashCode = result
248 return result
249 }
250