[tialaramex]

Ha, looking through the links dang added, I came upon something I wrote back in December

I gave (somewhat arbitrarily) the example that safe Rust is OK with a 64-bit pointer (on a modern PC for example) having the value made by the UTF-8 text "LAUGHING". That's 8 bytes, 8 bytes is 64 bits, it fits perfectly. Of course I point out, unsafe Rust, which is allowed to dereference pointers, must never dereference this LAUGHING pointer, it's not actually pointing at anything, but it is allowed to exist in safe Rust.

Coincidentally, in like February or so this year, a new third-party Rust type "ColdString" was introduced to their reddit by somebody I've never met - I read about it and encouraged its author. ColdString is 64 bits (on modern hardware) because inside it's a pointer, and indeed if the text you wanted to store in a ColdString was "LAUGHING" you do that exactly as I described in the December post - it's just the UTF-8 encoded text, no problem. The clever trick inside ColdString is how it can know when that 64-bit pointer really is actually a pointer for longer strings - yet also allows any 0 to 8 byte UTF-8 text string to just be encoded in the ColdString itself directly.

[bonzini]

How does it do that? When the 64-bit pointer is actually a pointer, does it mangle it into something that is certainly not UTF-8 (e.g. changing its top byte to 0xC0, and assuming that bits 56-63 are the same as bits 48-55, or something like that)?

[tialaramex]

UTF-8 is a self-synchronizing encoding, so each UTF-8 byte tells you whether there were any previous bytes you'd need in order to understand it. Since we're storing a whole string our first byte logically cannot be such a "continuation byte", if it seems to be, we can say these eight bytes aren't UTF-8 encoded text but instead a pointer. The UTF-8 "continuation" marker is that the top bit is set and the next bit is not. So, we need to smash two bits of our pointer.

Now, by pointing only at memory aligned to 4 bytes, the way a 32-bit integer would be on a typical machine, the bottom two bits of the pointer are always zero. So, we ask for such 4-byte aligned pointers when allocating memory to point at, most allocators actually never give out smaller alignments anyway because they cause problems in C but we've told the allocator our requirement so even if it could it won't give out unaligned pointers.

Finally we need to re-arrange our pointer so that those two zero bits are in the right place to put a UTF-8 continuation marker. In Rust this is legal safe code, the map_addr method on a pointer is allowed to twiddle with a pointer's address bits (on typical platforms, all of them) and so long as your transform is reversible (which this one is) it will work correctly when you twiddle the pointer back and dereference that pointer in unsafe Rust.

[bonzini]

Ah, so it is basically a single rotr(x|2, 2), nice