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

Groups > comp.lang.c > #73489

Re: How to encode/decode string of decimal digits

Show all headers | View raw

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

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

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