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 1 of 2  [1] 2  Next page →

#73281 — How to encode/decode string of decimal digits

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.

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.

uint64_t
compress(const char *s)
{
   uint64_t ret;
   unsigned char nz;

   ret = strtoull(s, NULL, 10);
   for (nz = 0; *s++ == '0'; nz++)
     ;
   ret = (ret << 8) + nz;
   return ret;
}

void
decompress(char *dst, uint64_t n)
{
   unsigned char nz;

   nz = n & 0xFF;
   n >>= 8;
   memset(dst, '0', nz);
   if (n > 0) {
     sprintf(&dst[nz], "%lld", n);
   } else {
     dst[nz] = '\0';
   }
}

In this way I can save one 16-digits string in 8 bytes.

Do you think of a better method?

[toc] | [next] | [standalone]

#73288

On 19/10/2015 13:28, 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.
>
> I have a very limited embedded plaftorm, so I'm searching for a simple
> compression/decompression method of a single string.
>
> 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.
>
> uint64_t
> compress(const char *s)
> {
>    uint64_t ret;
>    unsigned char nz;
>
>    ret = strtoull(s, NULL, 10);
>    for (nz = 0; *s++ == '0'; nz++)
>      ;
>    ret = (ret << 8) + nz;
>    return ret;
> }
>
> void
> decompress(char *dst, uint64_t n)
> {
>    unsigned char nz;
>
>    nz = n & 0xFF;
>    n >>= 8;
>    memset(dst, '0', nz);
>    if (n > 0) {
>      sprintf(&dst[nz], "%lld", n);
>    } else {
>      dst[nz] = '\0';
>    }
> }
>
> In this way I can save one 16-digits string in 8 bytes.
>
> Do you think of a better method?

How many leading zeros are there likely to be? And how important that 
they be recovered?

Also, is performance important? Because above you are converting strings 
into binary, and converting from binary into strings, all of which can 
require quite a bit of arithmetic to do.

Assuming you can have up to 255 leading zeros, and up to 16 significant 
digits, your basic data is 17 bytes (16 chars + 1 byte count, no 
terminator). Your method above reduces that to 8 bytes. Not a bad 
reduction, but a lot of work, and we don't know whether space is more 
important or speed.

You can reduce that to 9 bytes by using a 4-bit representation for each 
digit (BCD, 2 digits per byte), an easier conversion. Or 8 bytes if your 
forget the leading zero count.

There are far more elaborate methods to reduce below 8 bytes per string, 
but they can depend on how random the strings are.

-- 
Bartc

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

#73292

Il 19/10/2015 15:07, Bartc ha scritto:
> On 19/10/2015 13:28, 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.
>>
>> I have a very limited embedded plaftorm, so I'm searching for a simple
>> compression/decompression method of a single string.
>>
>> 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.
>>
>> uint64_t
>> compress(const char *s)
>> {
>>    uint64_t ret;
>>    unsigned char nz;
>>
>>    ret = strtoull(s, NULL, 10);
>>    for (nz = 0; *s++ == '0'; nz++)
>>      ;
>>    ret = (ret << 8) + nz;
>>    return ret;
>> }
>>
>> void
>> decompress(char *dst, uint64_t n)
>> {
>>    unsigned char nz;
>>
>>    nz = n & 0xFF;
>>    n >>= 8;
>>    memset(dst, '0', nz);
>>    if (n > 0) {
>>      sprintf(&dst[nz], "%lld", n);
>>    } else {
>>      dst[nz] = '\0';
>>    }
>> }
>>
>> In this way I can save one 16-digits string in 8 bytes.
>>
>> Do you think of a better method?
>
> How many leading zeros are there likely to be?

16 digits, including leading zeros. So there could be 16 leading zero at 
maximum (the exceptional case of the string "0000000000000000").
I don't know what could be the statistics of those strings, so I have to 
suppose all the strings have the same probability.


 > And how important that they be recovered?

It's a must.


> Also, is performance important? Because above you are converting strings
> into binary, and converting from binary into strings, all of which can
> require quite a bit of arithmetic to do.

This is correct. I'm using a Cortex-M0 MCU.


> Assuming you can have up to 255 leading zeros, and up to 16 significant
> digits, your basic data is 17 bytes (16 chars + 1 byte count, no
> terminator). Your method above reduces that to 8 bytes. Not a bad
> reduction, but a lot of work, and we don't know whether space is more
> important or speed.
>
> You can reduce that to 9 bytes by using a 4-bit representation for each
> digit (BCD, 2 digits per byte), an easier conversion. Or 8 bytes if your
> forget the leading zero count.

Yes, BCD is another possibility. I have to make some measure.

> There are far more elaborate methods to reduce below 8 bytes per string,
> but they can depend on how random the strings are.

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

#73295

On 19/10/2015 14:58, pozz wrote:
> Il 19/10/2015 15:07, Bartc ha scritto:
>> On 19/10/2015 13:28, pozz wrote:
>>> 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.

>> How many leading zeros are there likely to be?
>
> 16 digits, including leading zeros. So there could be 16 leading zero at
> maximum (the exceptional case of the string "0000000000000000").
> I don't know what could be the statistics of those strings, so I have to
> suppose all the strings have the same probability.

>
>  > And how important that they be recovered?
>
> It's a must.

> Yes, BCD is another possibility. I have to make some measure.

So, leading zeros are important (and that "00123" is different from 
"0123"), and there can be up to 16 characters.

That means that without reduction, each value can take up to 16 bytes. 
(Possibly with a 17th byte to terminate, but that is easy to avoid.)

Then BCD is the obvious easy choice as any string will fit into an 
8-byte integer (and Eric said you can use a non-digit code to represent 
a space, or perhaps as a terminator).

Would that be sufficient? If the strings vary in length, and they are 
mostly short, then you might be better off keeping them as strings.

Another, more fiddly way is to have variable-length BCD, which will 
average half the length of the strings.

Also, how are these different values stored; in an array? A linked list? 
How are they searched? There might be overheads we don't know about. 
Would it be possible to take advantage of duplicate strings?

Will leading zeros figure a lot? (In telephone numbers, there might be 
only 0, 1 or 2.) If more than that, you can use your idea of storing a 
count for those, but that works best with a variable-length method.

-- 
Bartc

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

#73298

pozz <pozzugno@gmail.com> writes:
<snip>
> Yes, BCD is another possibility. I have to make some measure.

Another BCD option is to encode every 3 decimal digits in 10 bits.  You
will be able to squeeze 18 digits in this way if you make special
provision for the case of 16, 17 and 18 leading zeros.

<snip>
-- 
Ben.

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

#73344

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

> pozz <pozzugno@gmail.com> writes:
> <snip>
>> Yes, BCD is another possibility. I have to make some measure.
>
> Another BCD option is to encode every 3 decimal digits in 10 bits.  You
> will be able to squeeze 18 digits in this way if you make special
> provision for the case of 16, 17 and 18 leading zeros.

... and another thought combining two other ideas: you get 18 digits
quite simply if you encode 9 base 121 digits in 7 bits each.  That is
every 7 bit represents two base 11 digits.  (Base 11 allows for '0' to
map to 1, '1' to 2 and so on.)

-- 
Ben.

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

#73291

On 10/19/2015 8:28 AM, 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.
>
> I have a very limited embedded plaftorm, so I'm searching for a simple
> compression/decompression method of a single string.
>
> 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.
>
> uint64_t
> compress(const char *s)
> {
>    uint64_t ret;
>    unsigned char nz;
>
>    ret = strtoull(s, NULL, 10);

     Aside: No error check?  I hope you *know* the input is valid...

>    for (nz = 0; *s++ == '0'; nz++)
>      ;
>    ret = (ret << 8) + nz;
>    return ret;
> }
>
> void
> decompress(char *dst, uint64_t n)
> {
>    unsigned char nz;
>
>    nz = n & 0xFF;
>    n >>= 8;
>    memset(dst, '0', nz);
>    if (n > 0) {
>      sprintf(&dst[nz], "%lld", n);
>    } else {
>      dst[nz] = '\0';
>    }
> }
>
> In this way I can save one 16-digits string in 8 bytes.
>
> Do you think of a better method?

     Much depends on your definition of "better."  Are you looking for
space efficiency (maximum compression), or speed, or simplicity, or ...?

     If it's simplicity you want, and you're sure you won't need more
than 16 decimal digits, I'd suggest encoding each digit as a four-bit
value and just packing them together.  The decimal digits use only ten
of the sixteen possible four-bit values, so one of the unused nybbles
could serve as a "no digit" or "blank" indicator.

     For tighter compression, you might try padding the string with X's
(before or after the digits; your choice) and converting the whole
thing as a base-eleven value where digits 0-9 stand for themselves and
the X stands for ten.  This would encode strings of up to 18 digits
in a 64-bit quantity, without much complexity.

     Tighter compression schemes certainly exist -- but before we start
exploring them, tell us more about what "better" means to you.

-- 
esosman@comcast-dot-net.invalid
"Don't be afraid of work. Make work afraid of you." -- TLM

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

#73341

On Mon, 19 Oct 2015 13:30:00 -0400, Eric Sosman
<esosman@comcast-dot-net.invalid> wrote:

>On 10/19/2015 8:28 AM, 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.
>>
>> I have a very limited embedded plaftorm, so I'm searching for a simple
>> compression/decompression method of a single string.
>>
>> 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.
>>
>> uint64_t
>> compress(const char *s)
>> {
>>    uint64_t ret;
>>    unsigned char nz;
>>
>>    ret = strtoull(s, NULL, 10);
>
>     Aside: No error check?  I hope you *know* the input is valid...
>
>>    for (nz = 0; *s++ == '0'; nz++)
>>      ;
>>    ret = (ret << 8) + nz;
>>    return ret;
>> }
>>
>> void
>> decompress(char *dst, uint64_t n)
>> {
>>    unsigned char nz;
>>
>>    nz = n & 0xFF;
>>    n >>= 8;
>>    memset(dst, '0', nz);
>>    if (n > 0) {
>>      sprintf(&dst[nz], "%lld", n);
>>    } else {
>>      dst[nz] = '\0';
>>    }
>> }
>>
>> In this way I can save one 16-digits string in 8 bytes.
>>
>> Do you think of a better method?
>
>     Much depends on your definition of "better."  Are you looking for
>space efficiency (maximum compression), or speed, or simplicity, or ...?
>
>     If it's simplicity you want, and you're sure you won't need more
>than 16 decimal digits, I'd suggest encoding each digit as a four-bit
>value and just packing them together.  The decimal digits use only ten
>of the sixteen possible four-bit values, so one of the unused nybbles
>could serve as a "no digit" or "blank" indicator.


Perhaps a variation on this.  Use one of the unused nibbles as a
string terminator.  So encode "1234" and "012345" as 0x1234FFFF and
0x01234FFF (32 bit encoded values for illustration).  If it's more
convenient, put the terminators on the other side (0xffff1234 and
0xfff012345).

Using the latter encoding, something like:

uint64_t compress(const char *s)
{
   uint64_t ret = 0xffffffffffffffff;

   while (*s)
     {
     ret << 4;
     ret += (*s) - '0';
     s++;
     }
   return ret;
}

void decompress(char *dst, uint64_t n)
{
   int i;
   unsigned t;

   for (i=0; i<16; i++)
   {
   t = (n & 0xf000000000000000) >> 60;
   if (t == 0xf)
     break;
   *dst = t + '0';
   dst++;
   n << 4;
   }

  *dst = 0;
}

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

#73348

On 10/19/2015 5:18 PM, Robert Wessel wrote:
> On Mon, 19 Oct 2015 13:30:00 -0400, Eric Sosman
> <esosman@comcast-dot-net.invalid> wrote:
>
>> On 10/19/2015 8:28 AM, 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.
>>>
>>> I have a very limited embedded plaftorm, so I'm searching for a simple
>>> compression/decompression method of a single string.
>>>
>>> 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.
>>>
>>> uint64_t
>>> compress(const char *s)
>>> {
>>>     uint64_t ret;
>>>     unsigned char nz;
>>>
>>>     ret = strtoull(s, NULL, 10);
>>
>>      Aside: No error check?  I hope you *know* the input is valid...
>>
>>>     for (nz = 0; *s++ == '0'; nz++)
>>>       ;
>>>     ret = (ret << 8) + nz;
>>>     return ret;
>>> }
>>>
>>> void
>>> decompress(char *dst, uint64_t n)
>>> {
>>>     unsigned char nz;
>>>
>>>     nz = n & 0xFF;
>>>     n >>= 8;
>>>     memset(dst, '0', nz);
>>>     if (n > 0) {
>>>       sprintf(&dst[nz], "%lld", n);
>>>     } else {
>>>       dst[nz] = '\0';
>>>     }
>>> }
>>>
>>> In this way I can save one 16-digits string in 8 bytes.
>>>
>>> Do you think of a better method?
>>
>>      Much depends on your definition of "better."  Are you looking for
>> space efficiency (maximum compression), or speed, or simplicity, or ...?
>>
>>      If it's simplicity you want, and you're sure you won't need more
>> than 16 decimal digits, I'd suggest encoding each digit as a four-bit
>> value and just packing them together.  The decimal digits use only ten
>> of the sixteen possible four-bit values, so one of the unused nybbles
>> could serve as a "no digit" or "blank" indicator.
>
> Perhaps a variation on this.  Use one of the unused nibbles as a
> string terminator.  So encode "1234" and "012345" as 0x1234FFFF and
> 0x01234FFF (32 bit encoded values for illustration).  If it's more
> convenient, put the terminators on the other side (0xffff1234 and
> 0xfff012345).

     That's how I expected the "no digit" to be used: As a way to
distinguish between a leading zero and a nothing.

     It's not the most space-efficient encoding possible, since it's
able to encode configurations with embedded nothings: If the input
is a digit string, all the nothings appear at the ends.  (Deciding
how the nothings are divided between left and right is left as a
particularly vacuous exercise for the reader. :)

     The thread has already produced at least four simple ways to
encode 1-18 decimal digits in a uint64_t, so I doubt it's worth
searching for super-dense encodings until and unless the O.P. says
he really needs them.  (It's a sad fact that denser encodings usually
require bigger and slower encoders and decoders.  The O.P. indicates
that he's writing for a machine of limited capability, so the really
fancy approaches may not be available to him.)

-- 
esosman@comcast-dot-net.invalid
"Don't be afraid of work. Make work afraid of you." -- TLM

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

#73376

On Mon, 2015-10-19, Eric Sosman wrote:
> On 10/19/2015 8:28 AM, 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.
>>
>> I have a very limited embedded plaftorm, so I'm searching for a simple
>> compression/decompression method of a single string.

...

>> Do you think of a better method?
>
>      Much depends on your definition of "better."  Are you looking for
> space efficiency (maximum compression), or speed, or simplicity, or ...?
>
>      If it's simplicity you want, and you're sure you won't need more
> than 16 decimal digits, I'd suggest encoding each digit as a four-bit
> value and just packing them together.  The decimal digits use only ten
> of the sixteen possible four-bit values, so one of the unused nybbles
> could serve as a "no digit" or "blank" indicator.

A thought related to that: it's an interesting little problem, but all
we really know about the conditions around it is (unless I missed
something) the phrase "a very limited embedded plaftorm" above. That's
very subjective ...

Is the OP sure that this isn't enough?

  struct my_number {
    char val[16+1]; // unfortunate that it wasn't 15+1
  };

Not that the BCD solution above is a lot more complicated; both end up
with a struct which is convenient to handle, nothing variable-length
and nothing that needs malloc().  Both can have invalid states which
you need to prevent (non-digits mixed with the digits).  But the
latter is compatible with C strings so you have access to printf(),
strlen() and so on.

>      Tighter compression schemes certainly exist -- but before we start
> exploring them, tell us more about what "better" means to you.
>
/Jorgen

-- 
  // Jorgen Grahn <grahn@  Oo  o.   .     .
\X/     snipabacken.se>   O  o   .

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

#73297

pozz <pozzugno@gmail.com> writes:

> 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.
>
> 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.

Just one remark about that...  You don't need a whole byte for the count
and if you use a variable length, I think you can store any 18 decimal
digit number.  The key observation being the large numbers can't have
many leading zeros.

<snip>
-- 
Ben.

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

#73307

pozz <pozzugno@gmail.com> writes:
> 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.

Are the strings "01234" and "1234" distinct?  What is the range of
permitted lengths of these strings?

[...]

-- 
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"

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

#73327

pozz <pozzugno@gmail.com> writes:

> 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.
>
> 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.
>
> uint64_t
> compress(const char *s)
> {
>   uint64_t ret;
>   unsigned char nz;
>
>   ret = strtoull(s, NULL, 10);
>   for (nz = 0; *s++ == '0'; nz++)
>     ;
>   ret = (ret << 8) + nz;
>   return ret;
> }
>
> void
> decompress(char *dst, uint64_t n)
> {
>   unsigned char nz;
>
>   nz = n & 0xFF;
>   n >>= 8;
>   memset(dst, '0', nz);
>   if (n > 0) {
>     sprintf(&dst[nz], "%lld", n);
>   } else {
>     dst[nz] = '\0';
>   }
> }
>
> In this way I can save one 16-digits string in 8 bytes.
>
> Do you think of a better method?

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.  

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

#73394

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.

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

#73397

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.

BCD 'compression' is a bit less than using binary, but in both cases you 
will anyway be reducing 16 bytes of data to 8 bytes. A 16-char string 
could also be directly stored, without too much difficult, as two 64-bit 
values. (And most of the time you will probably only have to compare one.)

But presumably the overheads of decimal/binary conversion are not a problem.

-- 
Bartc

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

#73416

Bartc <bc@freeuk.com> wrote:
> On 20/10/2015 12:51, pozz wrote:
>> I answer here for everyone. Thank you very much for your suggestions.

(snip)
>>>      unsigned long long
>>>      compress( const char *s ){
>>>          return  strtoull( s, 0, 10 ) << 5  |  strlen( s );
>>>      }

(snip)

>> I think this is the best method. I have to make some measurements, but
>> it is sufficiently compact and simple to write and understand.

If you already have strtoull() and sprintf(), this is pretty compact
to write. They do tend to be slow, as C library functions go.

>> 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.

If you never use them for their numerical value, the conversion 
between decimal digits and the internal binary representation is
not needed, and slow.

You don't mention doing arithmetic on them, just considering them
as digit strings.

>> 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.

It does depend on how often that conversion is done.

On less than 64 bit processors, uint64_t can be slow, but usually
add, subtract, and assignment are still fast enough. Multiply and
divide might be a lot slower.
 
> BCD 'compression' is a bit less than using binary, but in both cases you 
> will anyway be reducing 16 bytes of data to 8 bytes. A 16-char string 
> could also be directly stored, without too much difficult, as two 64-bit 
> values. (And most of the time you will probably only have to compare one.)

If you never need the binary value, I suspect the bcd form is easier
to process and faster. If you rarely need the binary value, it might 
still be faster.

> But presumably the overheads of decimal/binary conversion are 
> not a problem.

-- glen

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

#73461

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 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.

   "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).

Again a small benefit, the encode() and decode() functions are trivial 
to read and write.


> BCD 'compression' is a bit less than using binary, but in both cases you
> will anyway be reducing 16 bytes of data to 8 bytes. A 16-char string
> could also be directly stored, without too much difficult, as two 64-bit
> values. (And most of the time you will probably only have to compare one.)
>
> But presumably the overheads of decimal/binary conversion are not a
> problem.

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

#73469

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.

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

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.

-- 
Bartc

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

#73491

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 :-(

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

#73476

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!

     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.

> 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.

-- 
esosman@comcast-dot-net.invalid
"Don't be afraid of work. Make work afraid of you." -- TLM

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

Page 1 of 2  [1] 2  Next page →

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

csiph-web