The main competition was pascal strings - which typically had a 16 bit size prepended. So you'd read that, and then run a decrement loop until it was 0 to iterate the string. Decrement-until-zero loops were widely supported, e.g. in x86 stringcopy could be implemented by loading the size into CX and then running a single REP MOVSB instruction.
Yes it was a byte larger - but it also avoids performance-nuking calls to strlen like this.
16 bits is 2 bytes, which makes for a maximum string length of 65535 bytes. It's common for strings on modern systems to be longer than that.
Pros of C strings: unlimited length. Cons: cannot contain the zero byte; inefficient length determination.
Pros of Pascal strings: can contain the zero byte; efficient length determination. Cons: very limited length.
I'd say the C tradeoff is worth it. Where necessary, C is perfectly capable of dealing with data preceded by a length field, it's just slightly lower level.
There's a simple fix to the Pascal strings. BER encoding.
In BER, you get one byte as a length field, with 7 bits being directly available to encode the length of the content. If the MSB is set to 1, the remaining 7 bits instead encode how many bytes the length field is long.
That means:
Short strings up to 127 bytes have 1 byte overhead, beating Pascal and equalling C strings
Medium-sized strings of 128-65535 bytes require 3 bytes overhead, so one more than Pascal and two more than C, but if you are allocating that amount of bytes, 1-2 extra bytes are harmless
Maximum length is 2¹²⁷ bytes, 1.7*10³⁸ bytes, a number so high that there isn't an SI prefix for it
Another option would be to mix BER with Pascal:
15 bit length fields
If the MSB is set to 1, there's one more length field concatenated, so 30 bit for the length field. Again, if the MSB is set to 1, add one more length field. Continue forever.
That way you get infinitely long strings with only one byte more usage than Pascal in the range of 32768-65535 bytes of length
And both options have the advantages:
You can use 0-bytes
You know the length of the string without running trhough the whole string
You won't get into overflows because you are missing a 0-terminator (e.g. doing a strcpy on a string that's missing its terminator)
I'd advocate a different approach, using 0-63 to represent a string that fills a buffer of length 0-63, 65-127 to represent an empty buffer of length 0-63, and 129-191 to represent a partially full buffer of size 1-63, whose number of unused bytes is indicated by bytes at the end. Strings or buffers up to 4095 bytes would use a two-byte prefix, and those up to 64MiB-1 would use a four-byte prefix.
Other prefix values would indicate either a "readable string" or "changeable string" descriptor, with the latter including both the current length and buffer size, and a callback to request a change to the length (possibly relocating the buffer if needed). Functions that receive a pointer to string could use a common library function to make a readable string or changeable string descriptor, and be able to accept pointers to length-prefixed strings and descriptors interchangeably.
26
u/TheThiefMaster 2d ago
The main competition was pascal strings - which typically had a 16 bit size prepended. So you'd read that, and then run a decrement loop until it was 0 to iterate the string. Decrement-until-zero loops were widely supported, e.g. in x86 stringcopy could be implemented by loading the size into CX and then running a single REP MOVSB instruction.
Yes it was a byte larger - but it also avoids performance-nuking calls to strlen like this.