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 package okio.internal
21
22 import okio.Buffer
23 import okio.ByteString
24 import okio.Segment
25 import okio.SegmentedByteString
26 import okio.arrayRangeEquals
27 import okio.checkOffsetAndCount
28
29 internal fun IntArray.binarySearch(value: Int, fromIndex: Int, toIndex: Int): Int {
30 var left = fromIndex
31 var right = toIndex - 1
32
33 while (left <= right) {
34 val mid = (left + right) ushr 1 // protect from overflow
35 val midVal = this[mid]
36
37 when {
38 midVal < value -> left = mid + 1
39 midVal > value -> right = mid - 1
40 else -> return mid
41 }
42 }
43
44 // no exact match, return negative of where it should match
45 return -left - 1
46 }
47
48 /** Returns the index of the segment that contains the byte at `pos`. */
segmentnull49 internal fun SegmentedByteString.segment(pos: Int): Int {
50 // Search for (pos + 1) instead of (pos) because the directory holds sizes, not indexes.
51 val i = directory.binarySearch(pos + 1, 0, segments.size)
52 return if (i >= 0) i else i.inv() // If i is negative, bitflip to get the insert position.
53 }
54
55 /** Processes all segments, invoking `action` with the ByteArray and range of valid data. */
forEachSegmentnull56 internal inline fun SegmentedByteString.forEachSegment(
57 action: (data: ByteArray, offset: Int, byteCount: Int) -> Unit
58 ) {
59 val segmentCount = segments.size
60 var s = 0
61 var pos = 0
62 while (s < segmentCount) {
63 val segmentPos = directory[segmentCount + s]
64 val nextSegmentOffset = directory[s]
65
66 action(segments[s], segmentPos, nextSegmentOffset - pos)
67 pos = nextSegmentOffset
68 s++
69 }
70 }
71
72 /**
73 * Processes the segments between `beginIndex` and `endIndex`, invoking `action` with the ByteArray
74 * and range of the valid data.
75 */
forEachSegmentnull76 private inline fun SegmentedByteString.forEachSegment(
77 beginIndex: Int,
78 endIndex: Int,
79 action: (data: ByteArray, offset: Int, byteCount: Int) -> Unit
80 ) {
81 var s = segment(beginIndex)
82 var pos = beginIndex
83 while (pos < endIndex) {
84 val segmentOffset = if (s == 0) 0 else directory[s - 1]
85 val segmentSize = directory[s] - segmentOffset
86 val segmentPos = directory[segments.size + s]
87
88 val byteCount = minOf(endIndex, segmentOffset + segmentSize) - pos
89 val offset = segmentPos + (pos - segmentOffset)
90 action(segments[s], offset, byteCount)
91 pos += byteCount
92 s++
93 }
94 }
95
96 // TODO Kotlin's expect classes can't have default implementations, so platform implementations
97 // have to call these functions. Remove all this nonsense when expect class allow actual code.
98
commonSubstringnull99 internal inline fun SegmentedByteString.commonSubstring(beginIndex: Int, endIndex: Int): ByteString {
100 require(beginIndex >= 0) { "beginIndex=$beginIndex < 0" }
101 require(endIndex <= size) { "endIndex=$endIndex > length($size)" }
102
103 val subLen = endIndex - beginIndex
104 require(subLen >= 0) { "endIndex=$endIndex < beginIndex=$beginIndex" }
105
106 when {
107 beginIndex == 0 && endIndex == size -> return this
108 beginIndex == endIndex -> return ByteString.EMPTY
109 }
110
111 val beginSegment = segment(beginIndex) // First segment to include
112 val endSegment = segment(endIndex - 1) // Last segment to include
113
114 val newSegments = segments.copyOfRange(beginSegment, endSegment + 1)
115 val newDirectory = IntArray(newSegments.size * 2)
116 var index = 0
117 for (s in beginSegment..endSegment) {
118 newDirectory[index] = minOf(directory[s] - beginIndex, subLen)
119 newDirectory[index++ + newSegments.size] = directory[s + segments.size]
120 }
121
122 // Set the new position of the first segment
123 val segmentOffset = if (beginSegment == 0) 0 else directory[beginSegment - 1]
124 newDirectory[newSegments.size] += beginIndex - segmentOffset
125
126 return SegmentedByteString(newSegments, newDirectory)
127 }
128
commonInternalGetnull129 internal inline fun SegmentedByteString.commonInternalGet(pos: Int): Byte {
130 checkOffsetAndCount(directory[segments.size - 1].toLong(), pos.toLong(), 1)
131 val segment = segment(pos)
132 val segmentOffset = if (segment == 0) 0 else directory[segment - 1]
133 val segmentPos = directory[segment + segments.size]
134 return segments[segment][pos - segmentOffset + segmentPos]
135 }
136
commonGetSizenull137 internal inline fun SegmentedByteString.commonGetSize() = directory[segments.size - 1]
138
139 internal inline fun SegmentedByteString.commonToByteArray(): ByteArray {
140 val result = ByteArray(size)
141 var resultPos = 0
142 forEachSegment { data, offset, byteCount ->
143 data.copyInto(
144 result, destinationOffset = resultPos, startIndex = offset,
145 endIndex = offset + byteCount
146 )
147 resultPos += byteCount
148 }
149 return result
150 }
151
commonWritenull152 internal inline fun SegmentedByteString.commonWrite(buffer: Buffer, offset: Int, byteCount: Int) {
153 forEachSegment(offset, offset + byteCount) { data, offset, byteCount ->
154 val segment = Segment(data, offset, offset + byteCount, true, false)
155 if (buffer.head == null) {
156 segment.prev = segment
157 segment.next = segment.prev
158 buffer.head = segment.next
159 } else {
160 buffer.head!!.prev!!.push(segment)
161 }
162 }
163 buffer.size += byteCount
164 }
165
commonRangeEqualsnull166 internal inline fun SegmentedByteString.commonRangeEquals(
167 offset: Int,
168 other: ByteString,
169 otherOffset: Int,
170 byteCount: Int
171 ): Boolean {
172 if (offset < 0 || offset > size - byteCount) return false
173 // Go segment-by-segment through this, passing arrays to other's rangeEquals().
174 var otherOffset = otherOffset
175 forEachSegment(offset, offset + byteCount) { data, offset, byteCount ->
176 if (!other.rangeEquals(otherOffset, data, offset, byteCount)) return false
177 otherOffset += byteCount
178 }
179 return true
180 }
181
commonRangeEqualsnull182 internal inline fun SegmentedByteString.commonRangeEquals(
183 offset: Int,
184 other: ByteArray,
185 otherOffset: Int,
186 byteCount: Int
187 ): Boolean {
188 if (offset < 0 || offset > size - byteCount ||
189 otherOffset < 0 || otherOffset > other.size - byteCount
190 ) {
191 return false
192 }
193 // Go segment-by-segment through this, comparing ranges of arrays.
194 var otherOffset = otherOffset
195 forEachSegment(offset, offset + byteCount) { data, offset, byteCount ->
196 if (!arrayRangeEquals(data, offset, other, otherOffset, byteCount)) return false
197 otherOffset += byteCount
198 }
199 return true
200 }
201
commonEqualsnull202 internal inline fun SegmentedByteString.commonEquals(other: Any?): Boolean {
203 return when {
204 other === this -> true
205 other is ByteString -> other.size == size && rangeEquals(0, other, 0, size)
206 else -> false
207 }
208 }
209
commonHashCodenull210 internal inline fun SegmentedByteString.commonHashCode(): Int {
211 var result = hashCode
212 if (result != 0) return result
213
214 // Equivalent to Arrays.hashCode(toByteArray()).
215 result = 1
216 forEachSegment { data, offset, byteCount ->
217 var i = offset
218 val limit = offset + byteCount
219 while (i < limit) {
220 result = 31 * result + data[i]
221 i++
222 }
223 }
224 hashCode = result
225 return result
226 }
227