Re: How to encode/decode string of decimal digits

From	pozz <pozzugno@gmail.com>
Newsgroups	comp.lang.c
Subject	Re: How to encode/decode string of decimal digits
Date	2015-10-21 17:55 +0200
Organization	A noiseless patient Spider
Message-ID	<n08cdm$6ef$2@dont-email.me> (permalink)
References	(1 earlier) <kfnvba2fzb6.fsf@x-alumni2.alumni.caltech.edu> <n059nk$f4g$1@dont-email.me> <n05ch6$q5i$1@dont-email.me> <n07ep5$oi1$1@dont-email.me> <n07p65$rgh$1@dont-email.me>

Show all headers | View raw

Il 21/10/2015 12:27, Bartc ha scritto:
> On 21/10/2015 08:29, pozz wrote:
>> Il 20/10/2015 14:38, Bartc ha scritto:
>
>>> BCD is simpler. But you don't see the complexity of string <-> binary
>>> conversion because it's inside those library functions.
>>
>> In my case, I will have an array of maximum 500-1000 "digit strings"
>> saved in Flash memory, in compressed form. The user sometime adds and
>> remove a single string, but this operation is rare, so this could be a
>> little slow, even some seconds.
>> The frequent operation will be searching a "digit strings" in the array,
>> so comparing the reference string against each string in the array.
>
> So the search method is more important.
>
> I don't know how often you need to search, or how slow the cortex-m0 is,
> but if you're using a linear search, and it's a bottleneck, you might
> want to look at that.
>
> (With the right search method, you can keep the data as strings, and it
> might still be faster than a linear search using uint64_t
>
>>
>> If uint64_t integer is used as the encoding format of a "digit string",
>> the compare is very simple, it's just a comparison between two 64-bits
>> integers. On a 32-bits architecture, I think it will be a comparison
>> between two 32-bits registers. I think it's very simple.
>>
>> If a variable length BCD string is used, I think the comparison process
>> is slower. I have to compare a byte against a byte, but I have to check
>> the end of the string.
>
> That depends. If you store the length with the BCD (as a leading byte is
> simplest), and do a one-time strlen() on the reference string, then you
> can quickly check the length first, using a single byte comparison.

This means an array of 8-bytes can store only 14 digits (one byte is 
lost for length).


> That can eliminate most full comparisons if the lengths are mostly
> variable. But not if they are 90% the same.

As it happens :-)


> But, anything involving variable length entries will be harder to index
> if random access is involved (eg. not using a linear search), and harder
> to replace one entry with another of a different length.
>
>> Or I *need* to fill *all* the trailing nibbles with the terminator BCD
>> tag during encoding, for example 0xF. Only in this case, the comparison
>> is reduced to a memcmp() between two 8-bytes arrays.
>>
>>    "1234" -> 0x12, 0x34, 0xFF, 0xFF, ...
>>
>> Another small benefit of uint64_t is this is able to encode a longer
>> string (maybe up to 17-18 digits).
>
> That's also an advantage of keeping the data as strings, if memory
> allows (it'll need up to 10KB extra assuming a fixed-length slot per
> string). You can also add a string-length prefix for faster comparison.

Unfortunately memory doesn't allow :-(

Thread

How to encode/decode string of decimal digits pozz <pozzugno@gmail.com> - 2015-10-19 14:28 +0200
  Re: How to encode/decode string of decimal digits Bartc <bc@freeuk.com> - 2015-10-19 14:07 +0100
    Re: How to encode/decode string of decimal digits pozz <pozzugno@gmail.com> - 2015-10-19 15:58 +0200
      Re: How to encode/decode string of decimal digits Bartc <bc@freeuk.com> - 2015-10-19 15:22 +0100
      Re: How to encode/decode string of decimal digits Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-10-19 15:58 +0100
        Re: How to encode/decode string of decimal digits Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-10-19 22:28 +0100
  Re: How to encode/decode string of decimal digits Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-10-19 13:30 -0400
    Re: How to encode/decode string of decimal digits Robert Wessel <robertwessel2@yahoo.com> - 2015-10-19 16:18 -0500
      Re: How to encode/decode string of decimal digits Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-10-19 21:38 -0400
    Re: How to encode/decode string of decimal digits Jorgen Grahn <grahn+nntp@snipabacken.se> - 2015-10-20 08:00 +0000
  Re: How to encode/decode string of decimal digits Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-10-19 15:50 +0100
  Re: How to encode/decode string of decimal digits Keith Thompson <kst-u@mib.org> - 2015-10-19 09:01 -0700
  Re: How to encode/decode string of decimal digits Tim Rentsch <txr@alumni.caltech.edu> - 2015-10-19 12:11 -0700
    Re: How to encode/decode string of decimal digits pozz <pozzugno@gmail.com> - 2015-10-20 13:51 +0200
      Re: How to encode/decode string of decimal digits Bartc <bc@freeuk.com> - 2015-10-20 13:38 +0100
        Re: How to encode/decode string of decimal digits glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-10-20 16:05 +0000
        Re: How to encode/decode string of decimal digits pozz <pozzugno@gmail.com> - 2015-10-21 09:29 +0200
          Re: How to encode/decode string of decimal digits Bartc <bc@freeuk.com> - 2015-10-21 11:27 +0100
            Re: How to encode/decode string of decimal digits pozz <pozzugno@gmail.com> - 2015-10-21 17:55 +0200
          Re: How to encode/decode string of decimal digits Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-10-21 08:03 -0400
            Re: How to encode/decode string of decimal digits pozz <pozzugno@gmail.com> - 2015-10-21 17:53 +0200
              Re: How to encode/decode string of decimal digits supercat@casperkitty.com - 2015-10-21 09:37 -0700
              Re: How to encode/decode string of decimal digits David Brown <david.brown@hesbynett.no> - 2015-10-22 11:47 +0200
                Re: How to encode/decode string of decimal digits pozz <pozzugno@gmail.com> - 2015-10-22 13:44 +0200
                Re: How to encode/decode string of decimal digits Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-10-22 13:45 +0100
                Re: How to encode/decode string of decimal digits Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-10-22 15:51 +0100
                Re: How to encode/decode string of decimal digits supercat@casperkitty.com - 2015-10-22 09:31 -0700
                Re: How to encode/decode string of decimal digits Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-10-22 20:48 +0100
                Re: How to encode/decode string of decimal digits pozz <pozzugno@gmail.com> - 2015-10-23 10:14 +0200
                Re: How to encode/decode string of decimal digits Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-10-23 11:14 +0100
                Re: How to encode/decode string of decimal digits Bartc <bc@freeuk.com> - 2015-10-23 11:47 +0100
                Re: How to encode/decode string of decimal digits Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-10-23 13:22 +0100
                Re: How to encode/decode string of decimal digits David Brown <david.brown@hesbynett.no> - 2015-10-22 15:07 +0200
                Re: How to encode/decode string of decimal digits glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-10-22 22:05 +0000
                Re: How to encode/decode string of decimal digits pozz <pozzugno@gmail.com> - 2015-10-23 10:15 +0200
  Re: How to encode/decode string of decimal digits glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-10-19 22:02 +0000
  Re: How to encode/decode string of decimal digits supercat@casperkitty.com - 2015-10-20 10:09 -0700

csiph-web