Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #98202

Re: Counted strings

Path csiph.com!news.swapon.de!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From Keith Thompson <kst-u@mib.org>
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 <lntwag3kry.fsf@kst-u.example.com> (permalink)
References <o1viji$9d6$1@dont-email.me> <97ca2dbf-f636-423d-93f8-61204901a182@googlegroups.com> <lnr35m46k2.fsf@kst-u.example.com> <ae62a155-9f37-4e0a-bfbe-c5655b333fb6@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

Show key headers only | View raw

Malcolm McLean <malcolm.mclean5@btinternet.com> writes:
> On Monday, December 5, 2016 at 5:41:17 PM UTC, Keith Thompson wrote:
>> Malcolm McLean <malcolm.mclean5@btinternet.com> 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  <http://www.ghoti.net/~kst>
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"

Back to comp.lang.c | Previous | Next — Previous in thread | 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