Counted strings

From	jacobnavia <jacob@jacob.remcomp.fr>
Newsgroups	comp.lang.c
Subject	Counted strings
Date	2016-12-03 23:58 +0100
Organization	A noiseless patient Spider
Message-ID	<o1viji$9d6$1@dont-email.me> (permalink)

Show all headers | View raw

Instead of prefixing a string with its count, we could do a variable 
length encoding, like in utf8.

Strings of length 0 to 254 would be prefixed by a byte containing the 
length. If the value of that byte is 255 (0xff, all ones) it means that 
the length is encoded in the next two bytes.

Those two bytes encode lengths from 255 to 65535-2, --> 65533. The 
length is given by

l == index - 1,

i.e. if we read 576 from those two bytes, the real length of the 
following data bytes is 575.

Why? Because we need OBVIOUSLY a continuous function and we have used 
the value 255 as an escape character, limiting the full range. 
Accounting for that make us substract one.

If the length is all ones, however, it means that the length is stored 
in the four next characters, a string longer than 65533. Similar 
equation at this step: we need

l == index - 3 and we stop at 4GB - 4 with the useful lengths that this 
schema can accomodate. Obviously this can be continued to 64 bits, for 
strings longer than 4GB - 4.

I think it is useful since 254 chars is quite a lot (twitter has less) 
of strings where the extra overhead of this schema is zero, since the 
terminating zero also occupies a character. Many strings used by 
programs would fall into this category.

For a bit bigger strings/buffers, the wasted space is at most 255 to 3, 
a bit more than 1% at its worst: a string of length 255 needs 1 byte 
0xff and then the number '255' written over two bytes, so the overhead 
is 3.

The overhead drops significantly with all the longer strings (at 512, 
say, the overhead is 512 to 3, much less than 1%. The overhead is 
negligible with strings of length 65533 to 3. Still the zero terminated 
strings are more efficient (space wise) but make operations like 
determine the length of the string incredibly expensive.

The only problem of this schema is the relative complexity of the length 
determining procedure.

Other variations would be to make subtypes:

String8 would be:
typedef struct {
	unsigned char len;
	unsigned char data[];
} StringL8;

typedef struct {
	unsigned char len[2];
	unsigned char data[];
} StringL16;

typedef struct {
	unsigned char len[4];
	unsigned char data[];
} StringL32;

... etc. A program could then limit all strings to String16, for 
instance, accepting a larger overhead for small strings. This is to be 
weighted against the reduction in complexity and expensive copy 
operations to convert from one to another. Yes, with such a decision 
there would be no strings larger than 65535 but maybe the program 
doesn't have those, and if they are ever needed they would be treated 
specially.

Now, in this schema we have logical length, i.e. characters (glyphs) 
identical to byte length. But if we go for utf8 strings, we should store 
two numbers in the length field:

1) The length in bytes
2) The length in characters

Again, a similar scheme could be devised: The logical character count 
would have the same length as the byte length: 1, 2, 4, etc.

A length in one byte would be followed by a logical count in one byte, a 
byte length in 2 would be followed by 2 bytes of logical length, etc.

What are your ideas about counted strings?

How could it be done?

Back to comp.lang.c | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

Counted strings jacobnavia <jacob@jacob.remcomp.fr> - 2016-12-03 23:58 +0100
  Re: Counted strings supercat@casperkitty.com - 2016-12-03 15:40 -0800
  Counted stringsl Thiago Adams <thiago.adams@gmail.com> - 2016-12-03 15:40 -0800
  Re: Counted strings BartC <bc@freeuk.com> - 2016-12-04 00:20 +0000
  Re: Counted strings Richard Damon <Richard@Damon-Family.org> - 2016-12-03 21:26 -0500
    Re: Counted strings jacobnavia <jacob@jacob.remcomp.fr> - 2016-12-04 18:11 +0100
    Re: Counted strings Mark Storkamp <mstorkamp@yahoo.com> - 2016-12-04 19:25 -0600
  Re: Counted strings Keith Thompson <kst-u@mib.org> - 2016-12-03 18:57 -0800
  Re: Counted strings David Brown <david.brown@hesbynett.no> - 2016-12-04 16:33 +0100
    Re: Counted strings "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-12-04 07:52 -0800
      Re: Counted strings David Brown <david.brown@hesbynett.no> - 2016-12-04 17:10 +0100
        Re: Counted strings "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-12-04 10:14 -0800
          Re: Counted strings David Brown <david.brown@hesbynett.no> - 2016-12-04 20:20 +0100
            Re: Counted strings "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-12-04 16:49 -0800
              Re: Counted strings David Brown <david.brown@hesbynett.no> - 2016-12-05 10:40 +0100
                Re: Counted strings "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-12-05 05:51 -0800
                Re: Counted strings David Brown <david.brown@hesbynett.no> - 2016-12-05 16:10 +0100
                Re: Counted strings "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-12-05 07:38 -0800
                Re: Counted strings Melzzzzz <mel@zzzzz.com> - 2016-12-05 16:56 +0100
                Re: Counted strings "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-12-05 08:04 -0800
                Re: Counted strings Melzzzzz <mel@zzzzz.com> - 2016-12-05 17:16 +0100
                Re: Counted strings Jerry Stuckle <jstucklex@attglobal.net> - 2016-12-05 16:12 -0500
                Re: Counted strings "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-12-05 13:24 -0800
                Re: Counted strings David Brown <david.brown@hesbynett.no> - 2016-12-06 10:53 +0100
                Re: Counted strings "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-12-06 03:52 -0800
                Re: Counted strings David Brown <david.brown@hesbynett.no> - 2016-12-06 13:32 +0100
                Re: Counted strings "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-12-06 04:48 -0800
                Re: Counted strings Robert Spanjaard <spamtrap@arumes.com> - 2016-12-06 13:42 +0100
                Re: Counted strings "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-12-06 05:16 -0800
                Re: Counted strings Robert Spanjaard <spamtrap@arumes.com> - 2016-12-06 14:39 +0100
                Re: Counted strings "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-12-06 05:24 -0800
                Re: Counted strings fir <profesor.fir@gmail.com> - 2016-12-06 05:41 -0800
                Re: Counted strings fir <profesor.fir@gmail.com> - 2016-12-06 05:47 -0800
                Re: Counted strings Robert Spanjaard <spamtrap@arumes.com> - 2016-12-06 14:48 +0100
                Re: Counted strings "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-12-06 05:54 -0800
                Re: Counted strings fir <profesor.fir@gmail.com> - 2016-12-06 06:21 -0800
                Re: Counted strings fir <profesor.fir@gmail.com> - 2016-12-06 06:24 -0800
                Re: Counted strings Robert Spanjaard <spamtrap@arumes.com> - 2016-12-06 18:06 +0100
                Re: Counted strings "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-12-06 10:19 -0800
                Re: Counted strings Robert Spanjaard <spamtrap@arumes.com> - 2016-12-06 19:45 +0100
                Re: Counted strings "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-12-06 11:10 -0800
                Re: Counted strings fir <profesor.fir@gmail.com> - 2016-12-06 12:58 -0800
                Re: Counted strings fir <profesor.fir@gmail.com> - 2016-12-06 14:08 -0800
                Re: Counted strings Keith Thompson <kst-u@mib.org> - 2016-12-06 11:25 -0800
                Re: Counted strings fir <profesor.fir@gmail.com> - 2016-12-06 05:28 -0800
                Re: Counted strings David Brown <david.brown@hesbynett.no> - 2016-12-06 16:21 +0100
                Re: Counted strings "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-12-06 07:29 -0800
                Re: Counted strings fir <profesor.fir@gmail.com> - 2016-12-06 07:39 -0800
                Re: Counted strings fir <profesor.fir@gmail.com> - 2016-12-06 08:32 -0800
                Re: Counted strings fir <profesor.fir@gmail.com> - 2016-12-06 08:32 -0800
                Re: Counted strings BartC <bc@freeuk.com> - 2016-12-05 16:28 +0000
                Re: Counted strings "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-12-05 08:34 -0800
                Re: Counted strings BartC <bc@freeuk.com> - 2016-12-05 18:27 +0000
                Re: Counted strings "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-12-05 10:36 -0800
                Re: Counted strings Ian Collins <ian-news@hotmail.com> - 2016-12-06 08:19 +1300
                Re: Counted strings "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-12-05 11:22 -0800
                Re: Counted strings Ian Collins <ian-news@hotmail.com> - 2016-12-06 08:26 +1300
                Re: Counted strings BartC <bc@freeuk.com> - 2016-12-05 19:36 +0000
                Re: Counted strings Ian Collins <ian-news@hotmail.com> - 2016-12-06 08:41 +1300
                Re: Counted strings "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-12-05 11:48 -0800
                Re: Counted strings Thiago Adams <thiago.adams@gmail.com> - 2016-12-05 11:59 -0800
                Re: Counted strings jameskuyper@verizon.net - 2016-12-05 12:12 -0800
                Re: Counted strings "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-12-05 12:18 -0800
                Re: Counted strings jameskuyper@verizon.net - 2016-12-05 13:17 -0800
                Re: Counted strings "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-12-05 13:29 -0800
                Re: Counted strings jameskuyper@verizon.net - 2016-12-05 15:37 -0800
                Re: Counted strings "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-12-05 15:43 -0800
                Re: Counted strings David Brown <david.brown@hesbynett.no> - 2016-12-06 13:40 +0100
                Re: Counted strings "James R. Kuyper" <jameskuyper@verizon.net> - 2016-12-06 12:00 -0500
                Re: Counted strings "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-12-06 10:09 -0800
                Re: Counted strings Jerry Stuckle <jstucklex@attglobal.net> - 2016-12-06 13:33 -0500
                Re: Counted strings David Brown <david.brown@hesbynett.no> - 2016-12-06 21:24 +0100
                Re: Counted strings "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-12-06 12:56 -0800
                Re: Counted strings Keith Thompson <kst-u@mib.org> - 2016-12-05 12:22 -0800
                Re: Counted strings supercat@casperkitty.com - 2016-12-05 08:36 -0800
                Re: Counted strings BartC <bc@freeuk.com> - 2016-12-05 17:31 +0000
                Re: Counted strings David Brown <david.brown@hesbynett.no> - 2016-12-05 22:07 +0100
                Re: Counted strings Ian Collins <ian-news@hotmail.com> - 2016-12-06 10:14 +1300
                Re: Counted strings Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-12-05 22:11 +0000
                Re: Counted strings BartC <bc@freeuk.com> - 2016-12-06 02:13 +0000
                Re: Counted strings David Brown <david.brown@hesbynett.no> - 2016-12-05 21:57 +0100
                Re: Counted strings "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-12-05 13:01 -0800
                Re: Counted strings BartC <bc@freeuk.com> - 2016-12-05 21:22 +0000
                Re: Counted strings Ian Collins <ian-news@hotmail.com> - 2016-12-06 10:25 +1300
                Re: Counted strings BartC <bc@freeuk.com> - 2016-12-05 21:36 +0000
                Re: Counted strings jacobnavia <jacob@jacob.remcomp.fr> - 2016-12-05 22:33 +0100
                Re: Counted strings "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-12-05 17:03 -0500
    Re: Counted strings supercat@casperkitty.com - 2016-12-04 08:57 -0800
    Re: Counted strings Robert Spanjaard <spamtrap@arumes.com> - 2016-12-04 20:19 +0100
      Re: Counted strings David Brown <david.brown@hesbynett.no> - 2016-12-04 20:24 +0100
        Re: Counted strings Robert Spanjaard <spamtrap@arumes.com> - 2016-12-04 20:37 +0100
          Re: Counted strings David Brown <david.brown@hesbynett.no> - 2016-12-04 21:04 +0100
            Re: Counted strings Robert Spanjaard <spamtrap@arumes.com> - 2016-12-04 21:22 +0100
              Re: Counted strings BartC <bc@freeuk.com> - 2016-12-04 22:37 +0000
              Re: Counted strings David Thompson <dave.thompson2@verizon.net> - 2016-12-10 22:42 -0500
                Re: Counted strings Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-12-10 23:17 -0800
                Re: Counted strings Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-12-11 11:48 +0000
                Re: Counted strings Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-12-11 04:40 -0800
                Re: Counted strings Robert Spanjaard <spamtrap@arumes.com> - 2016-12-11 10:56 +0100
      Re: Counted strings Robert Wessel <robertwessel2@yahoo.com> - 2016-12-05 15:47 -0600
        Re: Counted strings Gareth Owen <gwowen@gmail.com> - 2016-12-05 22:01 +0000
          Re: Counted strings Robert Wessel <robertwessel2@yahoo.com> - 2016-12-05 22:28 -0600
        Re: Counted strings "Chris M. Thomasson" <invalid@invalid.invalid> - 2016-12-05 20:18 -0800
        Re: Counted strings Robert Spanjaard <spamtrap@arumes.com> - 2016-12-06 11:05 +0100
  Re: Counted strings luser droog <luser.droog@gmail.com> - 2016-12-04 13:13 -0800
  Re: Counted strings Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-12-05 09:30 -0800
    Re: Counted strings Keith Thompson <kst-u@mib.org> - 2016-12-05 09:41 -0800
      Re: Counted strings Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-12-06 11:19 -0800
        Re: Counted strings Keith Thompson <kst-u@mib.org> - 2016-12-06 11:44 -0800
  Re: Counted strings Tim Rentsch <txr@alumni.caltech.edu> - 2016-12-10 10:29 -0800
    Re: Counted strings supercat@casperkitty.com - 2016-12-10 11:08 -0800

csiph-web