Re:Git's list of banned C functions
by selfhoster11 on Thursday March 04, 2021 @05:33PM
(#26349421)
The funny thing is that you can just use the topmost bit of the length to indicate that the string length is >127, and chain as many length bytes as you want before you begin the string proper (to save space). It would be still a better encoding than a null at the end.
This way you would trade in a null-byte-terminated variable length string for essentially a null-bit-terminated variable length number (plus the remaining string). I am not convinced that this actually would be much safer.
Re:Git's list of banned C functions
by selfhoster11 on Thursday March 04, 2021 @07:41PM
(#26350788)
Unicode does variable length bit strings too, so I'm not a visionary or anything. It would be safer for no other reason than that such a pattern could only occur at the start of the string, with zero special handling, while a null could occur anywhere in a zero-terminated string.
Re:Git's list of banned C functions
by pertymcpert on Thursday March 04, 2021 @06:21PM
(#26349934)
This is just the LEB128 format, which is used commonly used and I don't think there's any serious problems with it.
Re:Git's list of banned C functions
by selfhoster11 on Thursday March 04, 2021 @07:43PM
(#26350796)
Interesting. Thank you for sharing this!
At least you don't have (obvious) performance problems with it, because you will effectively never need more than 9 (usually 2 or 3) of these bytes.
But sure on modern 64 bit systems just using a 64 bit integer makes much more sense. On a small embedded 8 bit oder 16 bit microcontroller it might make sense.
Re:Git's list of banned C functions
by selfhoster11 on Thursday March 04, 2021 @07:46PM
(#26350823)
You are correct, I was trying to show that such a scheme was practical even in the early 1980s when zero-termination was beginning to dominate. This could well be used on 64-bit systems (just with a larger word size than a byte), though the utility of such a thing is questionable.
In a toy language I once wrote I got around that by encoding binary values as quaternary values and using a ternary system on top of that with a termination character: 11 = 1; 01 = 0; 00 = end; 10 was unused.
Having truly unbounded integers was rather fun. Of course performance was abysmal.
Pascal compilers of the time when Pascal was popular typically had a switch that disabled range checks for speed reasons.
Such a system would effectively remove that feature. Yes, you could disable range checks when indexing into a string, but you still would have to figure out how many length bytes there are. That would only be a little bit faster than a full range check.
Because of that, I don’t see how that would have been useful at the time.
It was a limitation, because they chose a byte length (to save space). So strings up to 255 characters only. It was decades before folks were comfortable with 32-bit length fields. And that still limited you to 4GB strings. In the bad old days, memory usage was king.