Christopher Prohm

Recently, I found myself needing to get a character from a Rust string by an arbitrary byte index. When I originally looked into the problem, std did not have an API for this use case. Starting with Rust 1.91.0, str::floor_char_boundary covers much of this use case. I still found the UTF-8 properties instructive, so in this post I would like to describe how they allow access by arbitrary byte offsets using only the underlying bit patterns.

In Rust, all strings are encoded as UTF-8. UTF-8 is a Unicode encoding, backwards compatible with the ASCII encoding. ASCII uses 7 bits of a byte. That leaves one bit in each byte unused. UTF-8 uses this additional bit to encode non-ASCII characters.

One caveat on terminology: in this post, I use character in the sense of a Rust char. That is a Unicode scalar value. A printable character on screen can be more complex. For example, multiple scalar values may combine into one grapheme cluster.

To check whether a byte encodes an ASCII character, the u8 type offers

impl u8 {
    // See: https://doc.rust-lang.org/1.97.0/src/core/num/mod.rs.html#627
    fn is_ascii(&self) -> bool {
        *self <= 127
    }
}

This check can also be formulated as a check on the leading number of ones.

fn is_ascii(c: u8) -> bool {
    c.leading_ones() == 0
}

With optimization enabled, both forms compile to a similarly small check. For rustc=1.97.0 as hosted on Godbolt's compiler explorer, they compile to the same assembly ¹.

UTF-8 encodes a character into up to 4 bytes. ASCII characters are always encoded into a single byte with the leading bit unset. Non-ASCII characters are encoded into multiple bytes. The number of leading one bits in the first byte encodes the number of total bytes:

fn get_number_of_bytes(c: u8) -> Result<usize, &'static str> {
    match c.leading_ones() {
        0 => Ok(1),
        2 => Ok(2),
        3 => Ok(3),
        4 => Ok(4),
        _ => Err("invalid UTF-8 start byte"),
    }
}

UTF-8 uses the otherwise unused single-leading-bit case to mark the following bytes. These bytes are also called continuation bytes. That is, each additional byte used to encode a character has a single leading one bit.

fn is_continuation(c: u8) -> bool {
    c.leading_ones() == 1
}

Consider the following examples. The first byte indicates the total width of the character. Subsequent bytes are continuation bytes and start with 10.

To reassemble a character from individual bytes, we have to strip the UTF-8 marker bits and then concatenate the remaining bits. As each continuation byte has 6 non-marker bits, the masked values are shifted by multiples of 6.

// NOTE: this code assumes that the given bytes encode a valid Unicode scalar
// value. This assumption is not validated.
fn assemble_character(bytes: &[u8]) -> Result<char, &'static str> {
    let codepoint = match bytes {
        [b0] => u32::from(*b0),
        [b0, b1] => {
            (u32::from(b0 & 0b_0001_1111) << 6)
                + u32::from(b1 & 0b_0011_1111)
        }
        [b0, b1, b2] => {
            (u32::from(b0 & 0b0000_1111) << 12)
                + (u32::from(b1 & 0b_0011_1111) << 6)
                + u32::from(b2 & 0b_0011_1111)
        }
        [b0, b1, b2, b4] => {
            (u32::from(b0 & 0b0000_0111) << 18)
                + (u32::from(b1 & 0b_0011_1111) << 12)
                + (u32::from(b2 & 0b_0011_1111) << 6)
                + u32::from(b4 & 0b_0011_1111)
        }
        _ => return Err("invalid UTF-8: got more than 4 bytes for a character"),
    };

    char::from_u32(codepoint).ok_or("invalid UTF-8: got invalid character")
}

To find the start byte for an arbitrary byte position, we can walk backwards from that position. A UTF-8 character can use at most four bytes. Therefore, we only have to inspect the current byte and the three preceding bytes. The first non-continuation byte in that window is the start of the character.

fn get_start_byte(bytes: &[u8], pos: usize) -> Result<usize, &'static str> {
    for delta in 0..4 {
        let Some(cand) = pos.checked_sub(delta) else {
            return Err("could not find start byte");
        };
        let Some(byte) = bytes.get(cand) else {
            return Err("could not find start byte");
        };
        if !is_continuation(*byte) {
            return Ok(cand);
        }
    }
    Err("could not find start byte")
}

With these helper functions, we can write a function that allows byte-offset access into a string. Given a position in a byte slice, the function returns the start byte and the decoded character.

fn get_character(bytes: &[u8], pos: usize) -> Result<(usize, char), &'static str> {
    let start_byte_index = get_start_byte(bytes, pos)?;
    let &start_byte = bytes.get(start_byte_index)
        .unwrap_or_else(|| unreachable!("get_start_byte returns a valid index"));

    let number_of_bytes = get_number_of_bytes(start_byte)?;

    let Some(end_byte_index) = start_byte_index.checked_add(number_of_bytes) else {
        return Err("invalid byte range");
    };
    let Some(character_bytes) = bytes.get(start_byte_index..end_byte_index) else {
        return Err("invalid byte range");
    };

    let character = assemble_character(character_bytes)?;

    Ok((start_byte_index, character))
}

This function is the byte-offset access initially asked for. Admittedly, my use case was a bit niche. I do not expect this functionality to be widely applicable. Still, I quite enjoyed learning about these properties of the UTF-8 encoding.

The following tests illustrate the behavior of the defined functions:

#[test]
fn test_number_of_bytes() -> Result<(), &'static str> {
    assert_eq!(get_number_of_bytes("a".as_bytes()[0])?, 1);
    assert_eq!(get_number_of_bytes("é".as_bytes()[0])?, 2);
    assert_eq!(get_number_of_bytes("€".as_bytes()[0])?, 3);
    assert_eq!(get_number_of_bytes("𝄞".as_bytes()[0])?, 4);
    Ok(())
}

#[test]
fn test_is_continuation() {
    assert!(!is_continuation("é".as_bytes()[0]));
    assert!(is_continuation("é".as_bytes()[1]));

    assert!(!is_continuation("€".as_bytes()[0]));
    assert!(is_continuation("€".as_bytes()[1]));
    assert!(is_continuation("€".as_bytes()[2]));

    assert!(!is_continuation("𝄞".as_bytes()[0]));
    assert!(is_continuation("𝄞".as_bytes()[1]));
    assert!(is_continuation("𝄞".as_bytes()[2]));
    assert!(is_continuation("𝄞".as_bytes()[3]));
}

#[test]
fn test_assemble_character() -> Result<(), &'static str> {
    assert_eq!(assemble_character("a".as_bytes())?, 'a');
    assert_eq!(assemble_character("é".as_bytes())?, 'é');
    assert_eq!(assemble_character("€".as_bytes())?, '€');
    assert_eq!(assemble_character("𝄞".as_bytes())?, '𝄞');
    Ok(())
}

#[test]
fn test_get_start_byte() -> Result<(), &'static str> {
    let bytes = "aé€𝄞".as_bytes();

    assert_eq!(get_start_byte(bytes, 0)?, 0);
    assert_eq!(get_start_byte(bytes, 1)?, 1);
    assert_eq!(get_start_byte(bytes, 2)?, 1);
    assert_eq!(get_start_byte(bytes, 3)?, 3);
    assert_eq!(get_start_byte(bytes, 4)?, 3);
    assert_eq!(get_start_byte(bytes, 5)?, 3);
    assert_eq!(get_start_byte(bytes, 6)?, 6);
    assert_eq!(get_start_byte(bytes, 7)?, 6);
    assert_eq!(get_start_byte(bytes, 8)?, 6);
    assert_eq!(get_start_byte(bytes, 9)?, 6);

    get_start_byte(bytes, 10).unwrap_err();

    Ok(())
}

#[test]
fn test_get_character() -> Result<(), &'static str> {
    let bytes = "aé€𝄞".as_bytes();

    assert_eq!(get_character(bytes, 0)?, (0, 'a'));
    assert_eq!(get_character(bytes, 1)?, (1, 'é'));
    assert_eq!(get_character(bytes, 2)?, (1, 'é'));
    assert_eq!(get_character(bytes, 3)?, (3, '€'));
    assert_eq!(get_character(bytes, 4)?, (3, '€'));
    assert_eq!(get_character(bytes, 5)?, (3, '€'));
    assert_eq!(get_character(bytes, 6)?, (6, '𝄞'));
    assert_eq!(get_character(bytes, 7)?, (6, '𝄞'));
    assert_eq!(get_character(bytes, 8)?, (6, '𝄞'));
    assert_eq!(get_character(bytes, 9)?, (6, '𝄞'));

    get_character(bytes, 10).unwrap_err();

    Ok(())
}

#[unsafe(no_mangle)]
pub fn is_ascii(c: u8) -> bool {
    c.is_ascii()
}

#[unsafe(no_mangle)]
pub fn is_ascii2(c: u8) -> bool {
    c.leading_ones() == 0
}

is_ascii:
        mov     eax, edi
        not     al
        shr     al, 7
        ret

is_ascii2 = is_ascii