str_indices/
chars.rs

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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
//! Index by chars.

use crate::byte_chunk::{ByteChunk, Chunk};

/// Counts the chars in a string slice.
///
/// Runs in O(N) time.
#[inline]
pub fn count(text: &str) -> usize {
    count_impl::<Chunk>(text.as_bytes())
}

/// Converts from byte-index to char-index in a string slice.
///
/// If the byte is in the middle of a multi-byte char, returns the index of
/// the char that the byte belongs to.
///
/// Any past-the-end index will return the one-past-the-end char index.
///
/// Runs in O(N) time.
#[inline]
pub fn from_byte_idx(text: &str, byte_idx: usize) -> usize {
    let bytes = text.as_bytes();

    // Ensure the index is either a char boundary or is off the end of
    // the text.
    let mut i = byte_idx;
    while Some(true) == bytes.get(i).map(is_trailing_byte) {
        i -= 1;
    }

    count_impl::<Chunk>(&bytes[0..i.min(bytes.len())])
}

/// Converts from char-index to byte-index in a string slice.
///
/// Any past-the-end index will return the one-past-the-end byte index.
///
/// Runs in O(N) time.
#[inline]
pub fn to_byte_idx(text: &str, char_idx: usize) -> usize {
    to_byte_idx_impl::<Chunk>(text.as_bytes(), char_idx)
}

//-------------------------------------------------------------

#[inline(always)]
fn to_byte_idx_impl<T: ByteChunk>(text: &[u8], char_idx: usize) -> usize {
    if text.len() <= T::SIZE {
        // Bypass the more complex routine for short strings, where the
        // complexity hurts performance.
        let mut char_count = 0;
        for (i, byte) in text.iter().enumerate() {
            char_count += is_leading_byte(byte) as usize;
            if char_count > char_idx {
                return i;
            }
        }
        return text.len();
    }
    // Get `middle` so we can do more efficient chunk-based counting.
    // We can't use this to get `end`, however, because the start index of
    // `end` actually depends on the accumulating char counts during the
    // counting process.
    let (start, middle, _) = unsafe { text.align_to::<T>() };

    let mut byte_count = 0;
    let mut char_count = 0;

    // Take care of any unaligned bytes at the beginning.
    for byte in start.iter() {
        char_count += is_leading_byte(byte) as usize;
        if char_count > char_idx {
            return byte_count;
        }
        byte_count += 1;
    }

    // Process chunks in the fast path. Ensure that we don't go past the number
    // of chars we are counting towards
    let fast_path_chunks = middle.len().min((char_idx - char_count) / T::SIZE);
    let bytes = T::SIZE * 4;
    for chunks in middle[..fast_path_chunks].chunks_exact(4) {
        let val1 = count_trailing_chunk(chunks[0]);
        let val2 = count_trailing_chunk(chunks[1]);
        let val3 = count_trailing_chunk(chunks[2]);
        let val4 = count_trailing_chunk(chunks[3]);
        char_count += bytes - val1.add(val2).add(val3.add(val4)).sum_bytes();
        byte_count += bytes;
    }

    // Process the rest of chunks in the slow path.
    for chunk in middle[(fast_path_chunks - fast_path_chunks % 4)..].iter() {
        let new_char_count = char_count + T::SIZE - count_trailing_chunk(*chunk).sum_bytes();
        if new_char_count >= char_idx {
            break;
        }
        char_count = new_char_count;
        byte_count += T::SIZE;
    }

    // Take care of any unaligned bytes at the end.
    let end = &text[byte_count..];
    for byte in end.iter() {
        char_count += is_leading_byte(byte) as usize;
        if char_count > char_idx {
            break;
        }
        byte_count += 1;
    }

    byte_count
}

#[inline(always)]
pub(crate) fn count_impl<T: ByteChunk>(text: &[u8]) -> usize {
    if text.len() < T::SIZE {
        // Bypass the more complex routine for short strings, where the
        // complexity hurts performance.
        return text.iter().map(|x| is_leading_byte(x) as usize).sum();
    }
    // Get `middle` for more efficient chunk-based counting.
    let (start, middle, end) = unsafe { text.align_to::<T>() };

    let mut inv_count = 0;

    // Take care of unaligned bytes at the beginning.
    inv_count += start.iter().filter(|x| is_trailing_byte(x)).count();

    // Take care of the middle bytes in big chunks. Loop unrolled.
    for chunks in middle.chunks_exact(4) {
        let val1 = count_trailing_chunk(chunks[0]);
        let val2 = count_trailing_chunk(chunks[1]);
        let val3 = count_trailing_chunk(chunks[2]);
        let val4 = count_trailing_chunk(chunks[3]);
        inv_count += val1.add(val2).add(val3.add(val4)).sum_bytes();
    }
    let mut acc = T::zero();
    for chunk in middle.chunks_exact(4).remainder() {
        acc = acc.add(count_trailing_chunk(*chunk));
    }
    inv_count += acc.sum_bytes();

    // Take care of unaligned bytes at the end.
    inv_count += end.iter().filter(|x| is_trailing_byte(x)).count();

    text.len() - inv_count
}

#[inline(always)]
fn is_leading_byte(byte: &u8) -> bool {
    (byte & 0xC0) != 0x80
}

#[inline(always)]
fn is_trailing_byte(byte: &u8) -> bool {
    (byte & 0xC0) == 0x80
}

#[inline(always)]
fn count_trailing_chunk<T: ByteChunk>(val: T) -> T {
    val.bitand(T::splat(0xc0)).cmp_eq_byte(0x80)
}

//=============================================================

#[cfg(test)]
mod tests {
    use super::*;

    // 124 bytes, 100 chars, 4 lines
    const TEXT_LINES: &str = "Hello there!  How're you doing?\nIt's \
                              a fine day, isn't it?\nAren't you glad \
                              we're alive?\nこんにちは、みんなさん！";

    #[test]
    fn count_01() {
        let text = "Hello せかい! Hello せかい! Hello せかい! Hello せかい! Hello せかい!";

        assert_eq!(54, count(text));
    }

    #[test]
    fn count_02() {
        assert_eq!(100, count(TEXT_LINES));
    }

    #[test]
    fn from_byte_idx_01() {
        let text = "Hello せかい!";
        assert_eq!(0, from_byte_idx(text, 0));
        assert_eq!(1, from_byte_idx(text, 1));
        assert_eq!(6, from_byte_idx(text, 6));
        assert_eq!(6, from_byte_idx(text, 7));
        assert_eq!(6, from_byte_idx(text, 8));
        assert_eq!(7, from_byte_idx(text, 9));
        assert_eq!(7, from_byte_idx(text, 10));
        assert_eq!(7, from_byte_idx(text, 11));
        assert_eq!(8, from_byte_idx(text, 12));
        assert_eq!(8, from_byte_idx(text, 13));
        assert_eq!(8, from_byte_idx(text, 14));
        assert_eq!(9, from_byte_idx(text, 15));
        assert_eq!(10, from_byte_idx(text, 16));
        assert_eq!(10, from_byte_idx(text, 17));
        assert_eq!(10, from_byte_idx(text, 18));
        assert_eq!(10, from_byte_idx(text, 19));
    }

    #[test]
    fn from_byte_idx_02() {
        let text = "";
        assert_eq!(0, from_byte_idx(text, 0));
        assert_eq!(0, from_byte_idx(text, 1));

        let text = "h";
        assert_eq!(0, from_byte_idx(text, 0));
        assert_eq!(1, from_byte_idx(text, 1));
        assert_eq!(1, from_byte_idx(text, 2));

        let text = "hi";
        assert_eq!(0, from_byte_idx(text, 0));
        assert_eq!(1, from_byte_idx(text, 1));
        assert_eq!(2, from_byte_idx(text, 2));
        assert_eq!(2, from_byte_idx(text, 3));
    }

    #[test]
    fn from_byte_idx_03() {
        let text = "せかい";
        assert_eq!(0, from_byte_idx(text, 0));
        assert_eq!(0, from_byte_idx(text, 1));
        assert_eq!(0, from_byte_idx(text, 2));
        assert_eq!(1, from_byte_idx(text, 3));
        assert_eq!(1, from_byte_idx(text, 4));
        assert_eq!(1, from_byte_idx(text, 5));
        assert_eq!(2, from_byte_idx(text, 6));
        assert_eq!(2, from_byte_idx(text, 7));
        assert_eq!(2, from_byte_idx(text, 8));
        assert_eq!(3, from_byte_idx(text, 9));
        assert_eq!(3, from_byte_idx(text, 10));
        assert_eq!(3, from_byte_idx(text, 11));
        assert_eq!(3, from_byte_idx(text, 12));
    }

    #[test]
    fn from_byte_idx_04() {
        // Ascii range
        for i in 0..88 {
            assert_eq!(i, from_byte_idx(TEXT_LINES, i));
        }

        // Hiragana characters
        for i in 88..125 {
            assert_eq!(88 + ((i - 88) / 3), from_byte_idx(TEXT_LINES, i));
        }

        // Past the end
        for i in 125..130 {
            assert_eq!(100, from_byte_idx(TEXT_LINES, i));
        }
    }

    #[test]
    fn to_byte_idx_01() {
        let text = "Hello せかい!";
        assert_eq!(0, to_byte_idx(text, 0));
        assert_eq!(1, to_byte_idx(text, 1));
        assert_eq!(2, to_byte_idx(text, 2));
        assert_eq!(5, to_byte_idx(text, 5));
        assert_eq!(6, to_byte_idx(text, 6));
        assert_eq!(12, to_byte_idx(text, 8));
        assert_eq!(15, to_byte_idx(text, 9));
        assert_eq!(16, to_byte_idx(text, 10));
    }

    #[test]
    fn to_byte_idx_02() {
        let text = "せかい";
        assert_eq!(0, to_byte_idx(text, 0));
        assert_eq!(3, to_byte_idx(text, 1));
        assert_eq!(6, to_byte_idx(text, 2));
        assert_eq!(9, to_byte_idx(text, 3));
    }

    #[test]
    fn to_byte_idx_03() {
        let text = "Hello world!";
        assert_eq!(0, to_byte_idx(text, 0));
        assert_eq!(1, to_byte_idx(text, 1));
        assert_eq!(8, to_byte_idx(text, 8));
        assert_eq!(11, to_byte_idx(text, 11));
        assert_eq!(12, to_byte_idx(text, 12));
    }

    #[test]
    fn to_byte_idx_04() {
        let text = "Hello world! Hello せかい! Hello world! Hello せかい! \
                    Hello world! Hello せかい! Hello world! Hello せかい! \
                    Hello world! Hello せかい! Hello world! Hello せかい! \
                    Hello world! Hello せかい! Hello world! Hello せかい!";
        assert_eq!(0, to_byte_idx(text, 0));
        assert_eq!(30, to_byte_idx(text, 24));
        assert_eq!(60, to_byte_idx(text, 48));
        assert_eq!(90, to_byte_idx(text, 72));
        assert_eq!(115, to_byte_idx(text, 93));
        assert_eq!(120, to_byte_idx(text, 96));
        assert_eq!(150, to_byte_idx(text, 120));
        assert_eq!(180, to_byte_idx(text, 144));
        assert_eq!(210, to_byte_idx(text, 168));
        assert_eq!(239, to_byte_idx(text, 191));
    }

    #[test]
    fn to_byte_idx_05() {
        // Ascii range
        for i in 0..88 {
            assert_eq!(i, to_byte_idx(TEXT_LINES, i));
        }

        // Hiragana characters
        for i in 88..100 {
            assert_eq!(88 + ((i - 88) * 3), to_byte_idx(TEXT_LINES, i));
        }

        // Past the end
        for i in 100..110 {
            assert_eq!(124, to_byte_idx(TEXT_LINES, i));
        }
    }
}