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

Groups > comp.lang.c > #73281 > unrolled thread

How to encode/decode string of decimal digits

Back to article view | Back to comp.lang.c

Contents

  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

Page 2 of 2 — ← Prev page 1 [2]

#73489

Il 21/10/2015 14:03, Eric Sosman ha scritto:
> On 10/21/2015 3:29 AM, pozz wrote:
>> Il 20/10/2015 14:38, Bartc ha scritto:
>>> On 20/10/2015 12:51, pozz wrote:
>>>> I answer here for everyone. Thank you very much for your suggestions.
>>>>
>>>> Il 19/10/2015 21:11, Tim Rentsch ha scritto:
>>>>  > [...]
>>>>> Similar idea to above, just slightly simpler implementation:
>>>>>
>>>>>      unsigned long long
>>>>>      compress( const char *s ){
>>>>>          return  strtoull( s, 0, 10 ) << 5  |  strlen( s );
>>>>>      }
>>>>>
>>>>>      void
>>>>>      decompress( char *s, unsigned long long n ){
>>>>>          sprintf( s, "%.*llu", (int){ n & 31 }, n >> 5 );
>>>>>      }
>>>>>
>>>>> I didn't do extensive testing but based on the little I
>>>>> did I think this works for decimal strings from 0 up to 17
>>>>> digits in length, including leading zeroes.
>>>>
>>>> I think this is the best method. I have to make some measurements, but
>>>> it is sufficiently compact and simple to write and understand.
>>>>
>>>> The strings will be stored in a linear array and they can be added
>>>> *and*
>>>> removed. So I have to understand if a position is empty.
>>>> With this method is sufficient to compare against zero.
>>>>
>>>> I have to search for a number in the list, and I'm going to process
>>>> each
>>>> number from the beginning to the end. The comparing between two strings
>>>> will be a simple compare between two uint64_t numbers.
>>>>
>>>> I know uint64_t is managed by "software" functions, but I think they
>>>> are
>>>> highly optimized from the compiler/library supplier for my
>>>> architecture.
>>>> Cortex-M0 is a 32-bit MCU, so I think uint64_t numbers would be managed
>>>> without complex operations.
>>>>
>>>> I think BCD representation is more complex without compressing much
>>>> more.
>>>
>>> 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.
>
>      If the array changes infrequently, perhaps you can afford to keep
> it in sorted order and use binary search.  9-10 comparisons per search
> quite likely beats 250-500!

I use Flash memory and you know, this technology can't be used as a RAM. 
There is a maximum number of erase/write operations before it is damaged.

Moreover, data can't be moved from a position to another one, because 
Flash memory is organized in rows and pages. You can erase only a *full* 
row (in my case, 256B) and write only a *full* page (in my case 64B).

Moving strings from one position to another in order to keep the array 
sorted isn't simple.


>      But, but, but: You've got 500-1000 strings of <=16 digits.  You
> could trivially store these as char[16] arrays (for a 16-digit string
> you can omit the '\0'; you know where it belongs) for a total of
> 8000-16000 bytes of memory.  The compression schemes discussed thus
> far squash these strings into 8 bytes each, halving the memory
> requirement.  You can save
>
>           *** ### $$$  !!! 4000-8000 bytes !!!   $$$ ### ***
>
> (Minus whatever extra space the encoding and decoding functions need,
> but that may perhaps come out of a different "budget.")
>
>      There surely exist circumstances where a savings of <8KB is worth
> fighting for, but unless you're in that sort of circumstance I'd have
> second thoughts about whether the effort was well-spent.  And if you
> *are* in such dire straits, there are fancier encodings that could
> squeeze out more memory still -- at the cost of more complexity and
> more code space.
>
>      But no matter what you do, the savings will be less than 16KB.

The size of Flash memory that I can use to save those strings is exactly 
16kB. But I have to save other parameters, so I have no more than 10kB.


>> 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.
>> 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.
>
>      Why "variable-length?"  You've told us the digit strings are short,
> and people have proposed at least four ways to encode those shortish
> strings as 64-bit numbers.  Just store the encoded number as a uint64_t
> and be done with it.

The strings are short, but not fixed-length. Here a small list of 
examples of *different* strings:
   1234
   01234
   00001234
   123456789012345
   9874321

[toc] | [prev] | [next] | [standalone]

#73499

On Wednesday, October 21, 2015 at 10:53:13 AM UTC-5, pozz wrote:
> I use Flash memory and you know, this technology can't be used as a RAM. 
> There is a maximum number of erase/write operations before it is damaged.

Before asking how to store things, I would suggest that you say what
resources your code will have to work with, what you need to store, and
what usage sequences you need to accommodate efficiently.  Working
efficiently with flash requires different program techniques from using
other kinds of memory, and details about erase-unit and write-unit sizes,
guarantees of atomic behavior, and requirements for power-failure recovery
all have a huge impact on program design, so it's impossible to offer much
in the way of recommendations without knowing all those things.

[toc] | [prev] | [next] | [standalone]

#73539

On 21/10/15 17:53, pozz wrote:
> Il 21/10/2015 14:03, Eric Sosman ha scritto:
<snip>
>>      Why "variable-length?"  You've told us the digit strings are short,
>> and people have proposed at least four ways to encode those shortish
>> strings as 64-bit numbers.  Just store the encoded number as a uint64_t
>> and be done with it.
> 
> The strings are short, but not fixed-length. Here a small list of
> examples of *different* strings:
>   1234
>   01234
>   00001234
>   123456789012345
>   9874321
> 

The simple solution here would be to map decimal digits 0 to 9 to hex
digits 0 to 9, and "space" or "no digit" to hex 'a'.  This would turn
those strings into:

0xaaaaaaaaaaaa1234
0xaaaaaaaaaaa01234
0xaaaaaaaa00001234
0xa123456789012345
0xaaaaaaaaa9874321

Clear, simple, fast to implement and easy for debugging (since the hex
values are human-readable).  Consider your packed strings as a uint64_t,
and your comparisons are a simple uint64_t compare.  Depending on the
speed of the flash on your particular Cortex-M0 chip, you might need
something like 4 clock cycles per compare - that's about 100 µs to
search through 1000 strings with a typical 48 MHz clock.  If that's
sufficient, then you are done.

However, things can get more complex with adding and removing, and
garbage collection.  You have 10K free, with 8K needed to hold all the
strings.  Writes can be done at 64B blocks - 8 strings.  Erases are 256B
- 4 write blocks, 32 strings.  I gather that the write and erase
operations are rare, and can therefore be slow.

When you write a single new string, it will therefore take the place of
4 strings - one real string, and 3 blanks with 0xff..ff (you don't need
any special checks for these during lookup - just run through them
normally).  Of course, if you have more than one new string to write at
at time then you can be more efficient.  Whenever you have written a few
pages of four such write blocks, you can compact them in new erase
block, and then erase the sparsely populated blocks.  To remove a
string, simply re-write the other 31 strings in the block as though they
were new strings, and erase that block.

This is not the most efficient method for handing erases and writes, and
doesn't track wear levelling.  But it should not be too hard to make
sure you roll the blocks somewhat, rather than re-using the same block
every time, and with perhaps 1000 to 10000 guaranteed erase/write cycles
(depending on your device), you can do many thousands of updates without
having to figure out more complex schemes.

Keep it simple and clear, and it will be easier to write correctly, and
will run fast even on a small Cortex M0.

[toc] | [prev] | [next] | [standalone]

#73542

Il 22/10/2015 11:47, David Brown ha scritto:
> On 21/10/15 17:53, pozz wrote:
>> Il 21/10/2015 14:03, Eric Sosman ha scritto:
> <snip>
>>>       Why "variable-length?"  You've told us the digit strings are short,
>>> and people have proposed at least four ways to encode those shortish
>>> strings as 64-bit numbers.  Just store the encoded number as a uint64_t
>>> and be done with it.
>>
>> The strings are short, but not fixed-length. Here a small list of
>> examples of *different* strings:
>>    1234
>>    01234
>>    00001234
>>    123456789012345
>>    9874321
>>
>
> The simple solution here would be to map decimal digits 0 to 9 to hex
> digits 0 to 9, and "space" or "no digit" to hex 'a'.  This would turn
> those strings into:
>
> 0xaaaaaaaaaaaa1234
> 0xaaaaaaaaaaa01234
> 0xaaaaaaaa00001234
> 0xa123456789012345
> 0xaaaaaaaaa9874321
>
> Clear, simple, fast to implement and easy for debugging (since the hex
> values are human-readable).

Ok for "easy for debugging" (you can read directly the string), but is 
the encoding process "simpler" than strtoull()/strlen()?

I can think of (I didn't test it):

   uint64_t encode(const char *s) {
     uint64_t ret;
     char buf[16 + 1];
     memset(buf, 0xAA, sizeof(buf) - 1);
     sprintf(&buf[sizeof(buf) - strlen(s)], string_to_encode);
     return strtoull(buf, NULL, 16);
   }

IMHO it isn't simpler.


> Consider your packed strings as a uint64_t,
> and your comparisons are a simple uint64_t compare.  Depending on the
> speed of the flash on your particular Cortex-M0 chip, you might need
> something like 4 clock cycles per compare - that's about 100 µs to
> search through 1000 strings with a typical 48 MHz clock.  If that's
> sufficient, then you are done.

It's ok and this is identical to the simple strtoull()/strlen() encoding.


> However, things can get more complex with adding and removing, and
> garbage collection.  You have 10K free, with 8K needed to hold all the
> strings.  Writes can be done at 64B blocks - 8 strings.  Erases are 256B
> - 4 write blocks, 32 strings.  I gather that the write and erase
> operations are rare, and can therefore be slow.

Yes.


> When you write a single new string, it will therefore take the place of
> 4 strings - one real string, and 3 blanks with 0xff..ff (you don't need
> any special checks for these during lookup - just run through them
> normally).  Of course, if you have more than one new string to write at
> at time then you can be more efficient.  Whenever you have written a few
> pages of four such write blocks, you can compact them in new erase
> block, and then erase the sparsely populated blocks.  To remove a
> string, simply re-write the other 31 strings in the block as though they
> were new strings, and erase that block.
>
> This is not the most efficient method for handing erases and writes, and
> doesn't track wear levelling.  But it should not be too hard to make
> sure you roll the blocks somewhat, rather than re-using the same block
> every time, and with perhaps 1000 to 10000 guaranteed erase/write cycles
> (depending on your device), you can do many thousands of updates without
> having to figure out more complex schemes.
>
> Keep it simple and clear, and it will be easier to write correctly, and
> will run fast even on a small Cortex M0.

[toc] | [prev] | [next] | [standalone]

#73545

pozz <pozzugno@gmail.com> writes:

> Il 22/10/2015 11:47, David Brown ha scritto:
>> On 21/10/15 17:53, pozz wrote:
>>> Il 21/10/2015 14:03, Eric Sosman ha scritto:
>> <snip>
>>>>       Why "variable-length?"  You've told us the digit strings are short,
>>>> and people have proposed at least four ways to encode those shortish
>>>> strings as 64-bit numbers.  Just store the encoded number as a uint64_t
>>>> and be done with it.
>>>
>>> The strings are short, but not fixed-length. Here a small list of
>>> examples of *different* strings:
>>>    1234
>>>    01234
>>>    00001234
>>>    123456789012345
>>>    9874321
>>>
>>
>> The simple solution here would be to map decimal digits 0 to 9 to hex
>> digits 0 to 9, and "space" or "no digit" to hex 'a'.  This would turn
>> those strings into:
>>
>> 0xaaaaaaaaaaaa1234
>> 0xaaaaaaaaaaa01234
>> 0xaaaaaaaa00001234
>> 0xa123456789012345
>> 0xaaaaaaaaa9874321
>>
>> Clear, simple, fast to implement and easy for debugging (since the hex
>> values are human-readable).
>
> Ok for "easy for debugging" (you can read directly the string), but is
> the encoding process "simpler" than strtoull()/strlen()?
>
> I can think of (I didn't test it):
>
>   uint64_t encode(const char *s) {
>     uint64_t ret;
>     char buf[16 + 1];
>     memset(buf, 0xAA, sizeof(buf) - 1);
>     sprintf(&buf[sizeof(buf) - strlen(s)], string_to_encode);
>     return strtoull(buf, NULL, 16);
>   }
>
> IMHO it isn't simpler.

  uint64_t encode(const char *str)
  {
       uint64_t r = 0xaaaaaaaaaaaaaaaa;
       while (*str) r = (r << 4) + *str++ - '0';
       return r;
  }

Hardly very complex, but it does use an explicit loop where strtoull and
strlen hide them (not that that's bad, just that there always going to
be a loop).

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#73557

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> pozz <pozzugno@gmail.com> writes:
>
>> Il 22/10/2015 11:47, David Brown ha scritto:
<snip>
>>> The simple solution here would be to map decimal digits 0 to 9 to hex
>>> digits 0 to 9, and "space" or "no digit" to hex 'a'.  This would turn
>>> those strings into:
>>>
>>> 0xaaaaaaaaaaaa1234
>>> 0xaaaaaaaaaaa01234
>>> 0xaaaaaaaa00001234
>>> 0xa123456789012345
>>> 0xaaaaaaaaa9874321
>>>
>>> Clear, simple, fast to implement and easy for debugging (since the hex
>>> values are human-readable).
>>
>> Ok for "easy for debugging" (you can read directly the string), but is
>> the encoding process "simpler" than strtoull()/strlen()?
<snip>
>   uint64_t encode(const char *str)
>   {
>        uint64_t r = 0xaaaaaaaaaaaaaaaa;
>        while (*str) r = (r << 4) + *str++ - '0';
>        return r;
>   }

Just to keep things clear, Tim's strtoull(...) << 5 | strlen() version
can represent all the valid strings up to 17 digits because it does not
use a full byte for the length as your variation did.  The plain
BCD+blank encoding will do only 16, but that seemed to be enough for
you.  Fancier encodings can get up to 18 digits and, if I've counted
them right, it is theoretically possible to encode all strings up to 19
digits in 64 bits, but that's likely to be very messy.

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#73564

On Thursday, October 22, 2015 at 9:51:41 AM UTC-5, Ben Bacarisse wrote:
> ...    Fancier encodings can get up to 18 digits and, if I've counted
> them right, it is theoretically possible to encode all strings up to 19
> digits in 64 bits, but that's likely to be very messy.

A uint64_t handles numbers up to 18446744073709551616 (20 digits)

Simple approach: Add 2 to the first digit, replacing it with two digits 10 or
11 if needed.

After decoding, if the leading digit is 1, subtract 2 from the initial
2-digit number.

These approaches may actually be simplified if you do your own string-to-
binary and binary-to-string conversion routines, since you could make the
string-to-binary routine regard 0x3A and 0x3B (the next two characters after
nine) as "digits" with values 10 and 11 (basically just ignore the fact
that they're not actually digits) in which case for encoding simply add two
to the character code of the first digit.  Likewise, when decoding, stop
doing the div/mod process when the residual gets below 11 and store the
residual, minus 2, as the leftmost digit.

[toc] | [prev] | [next] | [standalone]

#73568

supercat@casperkitty.com writes:

> On Thursday, October 22, 2015 at 9:51:41 AM UTC-5, Ben Bacarisse wrote:
>> ...    Fancier encodings can get up to 18 digits and, if I've counted
>> them right, it is theoretically possible to encode all strings up to 19
>> digits in 64 bits, but that's likely to be very messy.
>
> A uint64_t handles numbers up to 18446744073709551616 (20 digits)
>
> Simple approach: Add 2 to the first digit, replacing it with two digits 10 or
> 11 if needed.

Very nice.  I like it.  I don't think I'd ever have come up with adding
2 to the lead digit.  (It doesn't naturally encode the empty string of
digits, but that would be trivial to add as a special case if needed --
zero springs to mind!)

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#73582

Il 22/10/2015 18:31, supercat@casperkitty.com ha scritto:
> On Thursday, October 22, 2015 at 9:51:41 AM UTC-5, Ben Bacarisse wrote:
>> ...    Fancier encodings can get up to 18 digits and, if I've counted
>> them right, it is theoretically possible to encode all strings up to 19
>> digits in 64 bits, but that's likely to be very messy.
>
> A uint64_t handles numbers up to 18446744073709551616 (20 digits)
>
> Simple approach: Add 2 to the first digit, replacing it with two digits 10 or
> 11 if needed.
>
> After decoding, if the leading digit is 1, subtract 2 from the initial
> 2-digit number.

I'm sorry, I couldn't get it. Could you make some examples, please?

>
> These approaches may actually be simplified if you do your own string-to-
> binary and binary-to-string conversion routines, since you could make the
> string-to-binary routine regard 0x3A and 0x3B (the next two characters after
> nine) as "digits" with values 10 and 11 (basically just ignore the fact
> that they're not actually digits) in which case for encoding simply add two
> to the character code of the first digit.  Likewise, when decoding, stop
> doing the div/mod process when the residual gets below 11 and store the
> residual, minus 2, as the leftmost digit.
>

[toc] | [prev] | [next] | [standalone]

#73601

pozz <pozzugno@gmail.com> writes:

> Il 22/10/2015 18:31, supercat@casperkitty.com ha scritto:
>> On Thursday, October 22, 2015 at 9:51:41 AM UTC-5, Ben Bacarisse wrote:
>>> ...    Fancier encodings can get up to 18 digits and, if I've counted
>>> them right, it is theoretically possible to encode all strings up to 19
>>> digits in 64 bits, but that's likely to be very messy.
>>
>> A uint64_t handles numbers up to 18446744073709551616 (20 digits)
>>
>> Simple approach: Add 2 to the first digit, replacing it with two digits 10 or
>> 11 if needed.
>>
>> After decoding, if the leading digit is 1, subtract 2 from the initial
>> 2-digit number.
>
> I'm sorry, I couldn't get it. Could you make some examples, please?

I'm not the originator but still...

The idea is to split the string into a lead digit and the rest:

   0    => 0|
   99   => 9|9
   0000 => 0|000
   123  => 1|23
   80   => 8|0

and then add two to the lead digit and concatenate the result:

   0    => 0|    =>  2|0   =>  20
   99   => 9|9   => 11|9   => 119
   0000 => 0|000 =>  2|000 =>  2000
   123  => 1|23  =>  3|23  =>  323
   80   => 8|0   => 10|0   => 100

This gives you a number between 2 (from the string "0") up to
11999999999999999999 from 9999999999999999999 (19 9s).  That range of
numbers can be stored in a uint64_t directly.

The neat trick is that by adding two (rather than one) you can always
decode a leading "1" as being part of a "11" or "10" pair resulting from
an 8 or 9 in the original.  Were you to add only one, both "00" and "9"
would result in "10".

There are simpler, similar, approaches, such as just putting a "1" on
the left of the string, but that does not work for 19 digits though it
does for 18.  All of these require decimal conversion where the BCD
approach does not, but you get two or three more digits in exchange.

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#73607

On 23/10/2015 11:14, Ben Bacarisse wrote:
> pozz <pozzugno@gmail.com> writes:
>
>> Il 22/10/2015 18:31, supercat@casperkitty.com ha scritto:

>>> A uint64_t handles numbers up to 18446744073709551616 (20 digits)
>>>
>>> Simple approach: Add 2 to the first digit, replacing it with two digits 10 or
>>> 11 if needed.
>>>
>>> After decoding, if the leading digit is 1, subtract 2 from the initial
>>> 2-digit number.
>>
>> I'm sorry, I couldn't get it. Could you make some examples, please?
>
> I'm not the originator but still...
>
> The idea is to split the string into a lead digit and the rest:
>
>     0    => 0|
>     99   => 9|9
>     0000 => 0|000
>     123  => 1|23
>     80   => 8|0
>
> and then add two to the lead digit and concatenate the result:
>
>     0    => 0|    =>  2|0   =>  20
>     99   => 9|9   => 11|9   => 119
>     0000 => 0|000 =>  2|000 =>  2000
>     123  => 1|23  =>  3|23  =>  323
>     80   => 8|0   => 10|0   => 100
>
> This gives you a number between 2 (from the string "0") up to
> 11999999999999999999 from 9999999999999999999 (19 9s).  That range of
> numbers can be stored in a uint64_t directly.
>
> The neat trick is that by adding two (rather than one) you can always
> decode a leading "1" as being part of a "11" or "10" pair resulting from
> an 8 or 9 in the original.  Were you to add only one, both "00" and "9"
> would result in "10".
>
> There are simpler, similar, approaches, such as just putting a "1" on
> the left of the string, but that does not work for 19 digits though it
> does for 18.  All of these require decimal conversion where the BCD
> approach does not, but you get two or three more digits in exchange.

That all sounds clever, but...  what's the purpose of it? To find if a 
string contains a number that will be fit into 64 bits when converted to 
binary?

For that purpose, testing if the string has less than 20 digits is one 
way of doing it. (If it has exactly 20, then do a strcmp against 
"18446744073709551616" and make sure it returns -1.)


-- 
Bartc

[toc] | [prev] | [next] | [standalone]

#73617

Bartc <bc@freeuk.com> writes:

> On 23/10/2015 11:14, Ben Bacarisse wrote:
>> pozz <pozzugno@gmail.com> writes:
>>
>>> Il 22/10/2015 18:31, supercat@casperkitty.com ha scritto:
>
>>>> A uint64_t handles numbers up to 18446744073709551616 (20 digits)
>>>>
>>>> Simple approach: Add 2 to the first digit, replacing it with two digits 10 or
>>>> 11 if needed.
>>>>
>>>> After decoding, if the leading digit is 1, subtract 2 from the initial
>>>> 2-digit number.
>>>
>>> I'm sorry, I couldn't get it. Could you make some examples, please?
>>
>> I'm not the originator but still...
>>
>> The idea is to split the string into a lead digit and the rest:
>>
>>     0    => 0|
>>     99   => 9|9
>>     0000 => 0|000
>>     123  => 1|23
>>     80   => 8|0
>>
>> and then add two to the lead digit and concatenate the result:
>>
>>     0    => 0|    =>  2|0   =>  20
>>     99   => 9|9   => 11|9   => 119
>>     0000 => 0|000 =>  2|000 =>  2000
>>     123  => 1|23  =>  3|23  =>  323
>>     80   => 8|0   => 10|0   => 100
>>
>> This gives you a number between 2 (from the string "0") up to
>> 11999999999999999999 from 9999999999999999999 (19 9s).  That range of
>> numbers can be stored in a uint64_t directly.
>>
>> The neat trick is that by adding two (rather than one) you can always
>> decode a leading "1" as being part of a "11" or "10" pair resulting from
>> an 8 or 9 in the original.  Were you to add only one, both "00" and "9"
>> would result in "10".
>>
>> There are simpler, similar, approaches, such as just putting a "1" on
>> the left of the string, but that does not work for 19 digits though it
>> does for 18.  All of these require decimal conversion where the BCD
>> approach does not, but you get two or three more digits in exchange.
>
> That all sounds clever, but...  what's the purpose of it? To find if a
> string contains a number that will be fit into 64 bits when converted
> to binary?

No, to store a 19 digit string (that might have significant leading
zero) in 64 bits.  The simple scheme gets 16.  I thought that 19 would
probably be fiddly, but this method is neat, I think.  (It's a bit
fiddly, but simpler than anything I came up with for 19 digits.)

[For context: of course 19-digit decimal all fit in 64 bits.  The part
that makes this an interesting challenge is to encode leading zeros.
I.e. "0001" != "01" != "1".]

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#73550

On 22/10/15 13:44, pozz wrote:
> Il 22/10/2015 11:47, David Brown ha scritto:
>> On 21/10/15 17:53, pozz wrote:
>>> Il 21/10/2015 14:03, Eric Sosman ha scritto:
>> <snip>
>>>>       Why "variable-length?"  You've told us the digit strings are
>>>> short,
>>>> and people have proposed at least four ways to encode those shortish
>>>> strings as 64-bit numbers.  Just store the encoded number as a uint64_t
>>>> and be done with it.
>>>
>>> The strings are short, but not fixed-length. Here a small list of
>>> examples of *different* strings:
>>>    1234
>>>    01234
>>>    00001234
>>>    123456789012345
>>>    9874321
>>>
>>
>> The simple solution here would be to map decimal digits 0 to 9 to hex
>> digits 0 to 9, and "space" or "no digit" to hex 'a'.  This would turn
>> those strings into:
>>
>> 0xaaaaaaaaaaaa1234
>> 0xaaaaaaaaaaa01234
>> 0xaaaaaaaa00001234
>> 0xa123456789012345
>> 0xaaaaaaaaa9874321
>>
>> Clear, simple, fast to implement and easy for debugging (since the hex
>> values are human-readable).
> 
> Ok for "easy for debugging" (you can read directly the string), but is
> the encoding process "simpler" than strtoull()/strlen()?
> 
> I can think of (I didn't test it):
> 
>   uint64_t encode(const char *s) {
>     uint64_t ret;
>     char buf[16 + 1];
>     memset(buf, 0xAA, sizeof(buf) - 1);
>     sprintf(&buf[sizeof(buf) - strlen(s)], string_to_encode);
>     return strtoull(buf, NULL, 16);
>   }
> 
> IMHO it isn't simpler.

That is simply /gruesome/ code.  It might be acceptable for a quick test
on a PC if you can't think how to handle it better, but as an embedded
programmer with a history of working on much smaller devices than a
Cortex M0, I get nervous every time I see a library calls such as
"sprintf" and "strtoull".  These are useful functions in their place -
but they are very big, and very slow.

Ben posted a good implementation of the required function, so there is
no need for me to repeat it here.  And it is much simpler, much faster,
and much slower than your original method.


> 
>> Consider your packed strings as a uint64_t,
>> and your comparisons are a simple uint64_t compare.  Depending on the
>> speed of the flash on your particular Cortex-M0 chip, you might need
>> something like 4 clock cycles per compare - that's about 100 µs to
>> search through 1000 strings with a typical 48 MHz clock.  If that's
>> sufficient, then you are done.
> 
> It's ok and this is identical to the simple strtoull()/strlen() encoding.

The comparisons are just straight uint64_t compares in each case.  But
with the BCD encoding (with "a" for space), you have much smaller and
faster encode/decode functions.

[toc] | [prev] | [next] | [standalone]

#73574

David Brown <david.brown@hesbynett.no> wrote:
> On 21/10/15 17:53, pozz wrote:

(snip)
>> The strings are short, but not fixed-length. Here a small list of
>> examples of *different* strings:
>>   1234
>>   01234
>>   00001234
>>   123456789012345
>>   9874321
 
> The simple solution here would be to map decimal digits 0 to 9 to hex
> digits 0 to 9, and "space" or "no digit" to hex 'a'.  This would turn
> those strings into:
 
> 0xaaaaaaaaaaaa1234
> 0xaaaaaaaaaaa01234
> 0xaaaaaaaa00001234
> 0xa123456789012345
> 0xaaaaaaaaa9874321

As long as the numerical (binary) value isn't needed, such as
for arithmetic operations, I believe that this is the best choice.
(I might have used 0xf instead of 0xa, but it isn't much different.)

While sprintf() and strtoull() are easy to call, they are fairly
complicated functions, doing a lot of multiply and divide.
 
> Clear, simple, fast to implement and easy for debugging (since the hex
> values are human-readable).  Consider your packed strings as a uint64_t,
> and your comparisons are a simple uint64_t compare.  Depending on the
> speed of the flash on your particular Cortex-M0 chip, you might need
> something like 4 clock cycles per compare - that's about 100 µs to
> search through 1000 strings with a typical 48 MHz clock.  If that's
> sufficient, then you are done.

(snip)

-- glen

[toc] | [prev] | [next] | [standalone]

#73583

Il 23/10/2015 00:05, glen herrmannsfeldt ha scritto:
> David Brown <david.brown@hesbynett.no> wrote:
>> On 21/10/15 17:53, pozz wrote:
>
> (snip)
>>> The strings are short, but not fixed-length. Here a small list of
>>> examples of *different* strings:
>>>    1234
>>>    01234
>>>    00001234
>>>    123456789012345
>>>    9874321
>
>> The simple solution here would be to map decimal digits 0 to 9 to hex
>> digits 0 to 9, and "space" or "no digit" to hex 'a'.  This would turn
>> those strings into:
>
>> 0xaaaaaaaaaaaa1234
>> 0xaaaaaaaaaaa01234
>> 0xaaaaaaaa00001234
>> 0xa123456789012345
>> 0xaaaaaaaaa9874321
>
> As long as the numerical (binary) value isn't needed, such as
> for arithmetic operations, I believe that this is the best choice.
> (I might have used 0xf instead of 0xa, but it isn't much different.)
>
> While sprintf() and strtoull() are easy to call, they are fairly
> complicated functions, doing a lot of multiply and divide.

Yes, finally I think so too :-)

[toc] | [prev] | [next] | [standalone]

#73350

pozz <pozzugno@gmail.com> wrote:
> I have to manage string of decimal digits 0-9. They aren't integer 
> numbers, because the string "01234" is completely different than the 
> number 1234.
 
> I have a very limited embedded plaftorm, so I'm searching for a simple 
> compression/decompression method of a single string.

Is it used as a string or a number?

My first thought is to store as a BCD value, with a non 0-9 digit
in the leading non-zero positions, or only in the leading zero positions,
whichever is more convenient for later use. That works in either
a uint64_t or an array of (unsigned char). 

This allows for use of hex constants in your program, where you
need constants.  It also allows separation of digits with shift
and and operations. But it depends a lot on how it is used.
 
> I thought to use a uint64_t to store a 16-digits string. One byte (the 
> LSB) of uint64_t is used to save the number of leading zeros.

If you have hardware support for uint64_t, that might be a good way.
Many systems do uint64_t using 32 bit or 16 bit operations, possibly
with function calls.

-- glen

[toc] | [prev] | [next] | [standalone]

#73426

On Monday, October 19, 2015 at 7:29:04 AM UTC-5, pozz wrote:
> I have to manage string of decimal digits 0-9. They aren't integer 
> numbers, because the string "01234" is completely different than the 
> number 1234.

One may encode a 0-8 digit number, including a 1-of-36 "format selection"
in 32 bits, by preceding the number with a number 4-39 and then doing
a decimal-to-binary conversion.  To decode, simply do a decimal-to-binary
conversion and then regard the first digit (if 4-9) or two digits (if the
first digit is 1-3) as a formatting indicator.

To handle larger values, simply split them into two pieces and process
according to the above method.

If using an 8-bit or 16-bit processor, the approach may be more efficiently
implemented with four 16-bit chunks and a 1-5 format selector on each; if
using a 64-bit processor, using one 64-bit number, may be better; splitting
into 32-bit chunks would most likely be a reasonable approach on any
processor, however.

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.c

csiph-web