blob: 9deb92755ee6aae3e77e787d4c8856c64cf30962 (
plain)
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
|
/*
* SPDX-License-Identifier: (LGPL-3.0-only WITH LGPL-3.0-linking-exception) OR MPL-2.0
*/
/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
package mozilla.components.lib.publicsuffixlist.ext
import kotlin.experimental.and
private const val BITMASK = 0xff.toByte()
/**
* Performs a binary search for the provided [labels] on the [ByteArray]'s data.
*
* This algorithm is based on OkHttp's PublicSuffixDatabase class:
* https://github.com/square/okhttp/blob/1977136/okhttp/src/main/kotlin/okhttp3/internal/publicsuffix/PublicSuffixDatabase.kt
*/
@Suppress("ComplexMethod", "NestedBlockDepth")
internal fun ByteArray.binarySearch(labels: List<ByteArray>, labelIndex: Int): String? {
var low = 0
var high = size
var match: String? = null
while (low < high) {
val mid = (low + high) / 2
val start = findStartOfLineFromIndex(mid)
val end = findEndOfLineFromIndex(start)
val publicSuffixLength = start + end - start
var compareResult: Int
var currentLabelIndex = labelIndex
var currentLabelByteIndex = 0
var publicSuffixByteIndex = 0
var expectDot = false
while (true) {
val byte0 =
if (expectDot) {
expectDot = false
'.'.code.toByte()
} else {
labels[currentLabelIndex][currentLabelByteIndex] and BITMASK
}
val byte1 = this[start + publicSuffixByteIndex] and BITMASK
// Compare the bytes. Note that the file stores UTF-8 encoded bytes, so we must compare
// the
// unsigned bytes.
compareResult = (byte0.toUByte() - byte1.toUByte()).toInt()
if (compareResult != 0) {
break
}
publicSuffixByteIndex++
currentLabelByteIndex++
if (publicSuffixByteIndex == publicSuffixLength) {
break
}
if (labels[currentLabelIndex].size == currentLabelByteIndex) {
// We've exhausted our current label. Either there are more labels to compare, in
// which
// case we expect a dot as the next character. Otherwise, we've checked all our
// labels.
if (currentLabelIndex == labels.size - 1) {
break
} else {
currentLabelIndex++
currentLabelByteIndex = -1
expectDot = true
}
}
}
if (compareResult < 0) {
high = start - 1
} else if (compareResult > 0) {
low = start + end + 1
} else {
// We found a match, but are the lengths equal?
val publicSuffixBytesLeft = publicSuffixLength - publicSuffixByteIndex
var labelBytesLeft = labels[currentLabelIndex].size - currentLabelByteIndex
for (i in currentLabelIndex + 1 until labels.size) {
labelBytesLeft += labels[i].size
}
if (labelBytesLeft < publicSuffixBytesLeft) {
high = start - 1
} else if (labelBytesLeft > publicSuffixBytesLeft) {
low = start + end + 1
} else {
// Found a match.
match = String(this, start, publicSuffixLength, Charsets.UTF_8)
break
}
}
}
return match
}
/** Search for a '\n' that marks the start of a value. Don't go back past the start of the array. */
private fun ByteArray.findStartOfLineFromIndex(start: Int): Int {
var index = start
while (index > -1 && this[index] != '\n'.code.toByte()) {
index--
}
index++
return index
}
/** Search for a '\n' that marks the end of a value. */
private fun ByteArray.findEndOfLineFromIndex(start: Int): Int {
var end = 1
while (this[start + end] != '\n'.code.toByte()) {
end++
}
return end
}
|
