Path: csiph.com!news.swapon.de!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Keith Thompson Newsgroups: comp.lang.c Subject: Re: Counted strings Date: Tue, 06 Dec 2016 11:44:17 -0800 Organization: None to speak of Lines: 47 Message-ID: References: <97ca2dbf-f636-423d-93f8-61204901a182@googlegroups.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Info: mx02.eternal-september.org; posting-host="6b5cb11ca1c741a8bf9c5175046a39f6"; logging-data="16583"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+ZHGBGMC59aKkeCupcfMrZ" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.1 (gnu/linux) Cancel-Lock: sha1:kneNv1iEHtg54eHGZJFaHZhwmCI= sha1:w7qU21yED0maT7Yk6tMUFAJSwjE= Xref: csiph.com comp.lang.c:98202 Malcolm McLean writes: > On Monday, December 5, 2016 at 5:41:17 PM UTC, Keith Thompson wrote: >> Malcolm McLean writes: >> > On Saturday, December 3, 2016 at 10:58:20 PM UTC, jacobnavia wrote: >> >> What are your ideas about counted strings? >> >> >> >> How could it be done? >> >> >> > It's a very standard data compression problem. >> > >> > You need to gather statistics, but also consider ease of implementation >> > and obviousness. >> > I think 8 clear bits need to be the empty string. If the high bit of >> > the first byte is unset, it's asciiz (backwards compatibility). >> > That then gives us 7 bits to play with for encodings. We can store >> > UTF8 / ascii, 8 bit, 16 bit, 32 bit, 64 bit counts, and we've still >> > 4 bits left. So nul/non-nul terminated. Now it's three bits. >> >> So for strings of length 127 or less, you still have to scan for >> the terminating '\0' to determine the length. That could be a >> performance problem (and no improvement over standard C strings) >> if you have a lot of relatively short strings. >> > No, because the representation is slightly redundant. > "Fred" can be 'F' 'r' 'e' 'd' '\0' > or > 0x80, 0x04, 'F' 'r' 'e' 'd' So you *might* have to scan for the terminating '\0', depending on which of two representations was chosen. And what if I happen to want a string whose first character is 0x80? Is this: 0x80, 0x04, 'F' 'r' 'e' 'd' '\0' a 4-character string starting with 'F' (with a redundant null byte past the end), or a 6-character string starting with 0x80? Redundancy is ok. Ambiguity, not so much. [...] -- Keith Thompson (The_Other_Keith) kst-u@mib.org Working, but not speaking, for JetHead Development, Inc. "We must do something. This is something. Therefore, we must do this." -- Antony Jay and Jonathan Lynn, "Yes Minister"