Best library/algorithm for low RAM embedded data compression?

[ebclr]

http://demin.ws/blog/english/2012/09/18/miniz-minilzo/

[westfw]

IIRC, the "original" LZW compression algorithms were designed to be implemented IN HARDWARE, using relatively small fixed memories (of the sort that you could find ~1983)  They use a compression table of 2ⁿ bytes to produce an n-bit output symbol, and utilities like "compress" let you specify "n", directly controlling the memory used.  "compress -b14" (should use 16k of memory for its table) yields about 44% compression on your sample.
(and it should be expandable using standard "uncompress.")
I'm not sure how fast it is; compression is typically much slower than decompression.

That would perhaps be "good enough", and it should be trivial to play with...

You probably won't find an existing unix-y library that doesn't use dynamic memory allocation.  Some should be trivial to convert to static arrays.

Beware licensing issues.  The story is that L,Z, and W patented what they thought was a hardware technique applicable to disk drives and such, and were merely amused when someone implemented the "compress" software utility.  Entities started getting less amused when the software algorithm started popping up all over, in devices like modems (which looked a lot like hardware...)  Implementing V.42bis (the compression used in last-gen dialup modems, based on LZW) and selling it required separate licenses from three different companies.  Not horribly expensive licenses by corporate standards (~$15k one-time?  Each or all together, I don't remember.)  But annoying, and maybe beyond the reach of smaller companies.

[I wanted a rude username]

lz4, which you say you've already looked at, is still the best low CPU low memory use compressor.  You're not going to come close to it using "a simple huffman" compressor. zlib can get a  little better compression but at the cost of a LOT of CPU and memory.

You're absolutely right for OP's application, but there's at least one use case in which Huffman is a solid choice: packing plaintext strings into a low-end microcontroller.

Huffman and gzip -1 both provided 53% compression on a corpus of 2 KiB of all-lowercase strings (and Huffman uses practically no RAM). Otherwise I would have used the lz4.org implementation.

[hamster_nz]

So the bulk of the data appears to be signed data in 36-byte repeating structure:

Code: [Select]

c4 74 7f a2 42 47 ff ef 98 08 08 18 54 02 00 00 00 00 00 02 08 00 00 00 f2 20 18 18 00 00 ff ff 01 00 40 f0
 cd 74 7f a2 42 47 6e fe 88 08 08 24 54 02 00 00 00 00 00 02 08 00 00 00 ff ff ff ff 05 02 ff ff 01 00 60 91
 d5 74 7f a2 42 07 ff ef 98 08 08 30 54 02 00 00 00 00 00 02 08 00 00 00 f0 0d ff ff ff ff ff ff 01 00 20 b9
 de 74 7f a2 42 03 fe ff 8c 08 08 3c 54 02 00 00 00 00 00 02 08 00 00 00 8e 7c af cc d0 05 ff e5 01 00 e0 e0
 e7 74 7f a2 42 19 f8 ff 98 08 08 48 54 02 00 00 00 00 00 02 08 00 00 00 05 21 1a 3c 00 00 00 00 01 00 00 82
 ef 74 7f a2 42 26 31 e6 9c 08 08 54 54 02 00 00 00 00 00 02 08 00 00 00 a8 ea 03 00 00 00 00 00 01 00 60 30
 fa 74 7f a2 42 19 f8 ff 98 08 08 60 54 02 00 00 00 00 00 02 08 00 00 00 08 ff ff ff ff ff ff ff 01 00 00 8b
 2c 75 7f a2 42 c6 fe ff 8c 08 08 6c 54 02 00 00 00 00 00 02 08 00 00 00 ea 54 0a f5 09 00 ff ff 01 00 c0 b2
 35 75 7f a2 42 c6 fb ff 8c 08 08 78 54 02 00 00 00 00 00 02 08 00 00 00 f2 3f ff 00 00 00 00 00 01 00 80 da
 3e 75 7f a2 42 c6 fb ff 8c 08 08 84 54 02 00 00 00 00 00 02 08 00 00 00 f2 4f ff 00 00 00 00 00 01 00 00 5f
 5d 75 7f a2 42 00 03 f0 8c 08 08 90 54 02 00 00 00 00 00 02 08 00 00 00 ff fe 0c ff ff ff ff ff 01 00 c0 86
 66 75 7f a2 42 00 ff ef 8c 08 08 9c 54 02 00 00 00 00 00 02 08 00 00 00 64 06 55 7d ff ff ff ff 01 00 e0 27
 6e 75 7f a2 42 00 04 f0 8c 08 08 a8 54 02 00 00 00 00 00 02 08 00 00 00 f1 ff 88 e4 1c ff ff ff 01 00 a0 4f
 77 75 7f a2 42 00 23 f0 98 08 08 b4 54 02 00 00 00 00 00 02 08 00 00 00 00 00 f2 ff ff 72 ff ff 01 00 c0 cd
 ec 75 7f a2 42 06 00 ef 84 08 08 c0 54 02 00 00 00 00 00 02 08 00 00 00 64 15 17 f1 5a 2e 77 0e 01 00 80 f5
 f5 75 7f a2 42 47 f1 fe 98 08 08 cc 54 02 00 00 00 00 00 02 08 00 00 00 ff 05 02 ff ff ff ff ff 01 00 a0 96
 fd 75 7f a2 42 03 ff ef 8c 08 08 d8 54 02 00 00 00 00 00 02 08 00 00 00 6d 1a 00 10 e0 1c f2 03 01 00 60 be
 06 76 7f a2 42 31 ff ff 8c 08 08 e4 54 02 00 00 00 00 00 02 08 00 00 00 5c f1 ff 1e 00 00 ff fc 01 00 80 5f
 0e 76 7f a2 42 03 ff ef 8c 08 08 f0 54 02 00 00 00 00 00 02 08 00 00 00 6b 39 f9 08 dc 03 8d 2c 01 00 40 87
 17 76 7f a2 42 31 ff ff 8c 08 08 fc 54 02 00 00 00 00 00 02 08 00 00 00 5e 0d fc ff f3 4f f0 0f 01 00 60 28
 1f 76 7f a2 42 47 fc fe 98 08 08 08 55 02 00 00 00 00 00 02 08 00 00 00 ff 98 ff ff ff ff ff ff 01 00 c0 d6
 29 76 7f a2 42 05 22 f0 8c 08 08 14 55 02 00 00 00 00 00 02 08 00 00 00 31 02 ff ff ff ff ff 20 01 00 80 fe
 32 76 7f a2 42 05 fe ff 8c 08 08 20 55 02 00 00 00 00 00 02 08 00 00 00 8b ff ff ff ff ff fa ff 01 00 40 26
The data has two parts, text and binary.

The binary is flicking between FFs and 00s are caused by values that are slightly positive and slightly negative.

By biasing these values by 0x80000000 before you log them (or whatever size the field value is) you could make even more of the data zeros, aiding compression.

The real question is, if I do write spend time writing a data-aware heapless compression system for you, what is the reward? 

If you want to play at home. run the datafile (renamed to "to_compress.dat") through and watch the patterns:

Code: [Select]

#include <stdio.h>

int main(int argc, char *argv[]) {
   int i = 0;
   int c;
   FILE *f = fopen("to_compress.dat","rb");

   c = getc(f);
   while(c != EOF) {
      printf(" %02x", c);
      if(i == 35) {
         putchar('\n');
         i = 0;
      } else {
         i++;
      }
      c = getc(f);
   }
}


[SiliconWizard]

Obvious note: we talked a lot about footprint, but not much about execution time. If you have time constraints, some algorithms could simply be out of the question. That would certainly be something to check almost first. (And yes, I also think, as I hinted earlier, that a custom compression could be the answer here...)

[hamster_nz]

So...

Most common bytes:

Code: [Select]

  83785  fe
  94219  f0
 174505  8c
 246123  42
 248959  a2
 266717  01
 272894  02
 734713  08
1035297  ff
2449890  00

XORing with the character 36 characters ago produces mostly zeros:

Code: [Select]

17 fd 10 e3 00 00 c0 28 1b 00 00 00 00 00 00 00 00 00 00 0c 00 00 00 00 00 00 00 00 00 00 00 00 02 71 fb 08
28 f3 10 e3 00 00 40 f2 2e 00 00 00 00 05 fb 1f 00 00 00 14 00 00 00 00 00 00 00 00 00 00 00 00 9f df 85 0a
dd 0e 00 00 00 00 60 86 4b 00 00 00 00 8c fa 0f 00 00 00 7c 00 00 00 00 00 00 00 00 00 00 00 00 7d 05 14 f1
e6 00 00 b0 00 00 40 38 0f 00 00 00 00 00 01 00 00 00 00 14 00 00 00 00 00 00 00 00 00 00 00 00 d9 87 ee 86
86 82 00 b0 00 00 c0 e9 fa 00 00 00 00 00 00 00 00 00 00 0c 00 00 00 00 00 00 00 00 00 00 00 00 c2 82 82 00
82 82 00 82 00 00 e0 e0 50 00 00 00 00 cb b6 01 00 00 00 34 00 00 00 00 00 00 00 00 00 00 00 00 68 00 00 82
00 00 00 82 00 00 60 56 37 00 00 00 00 00 27 00 04 00 00 1c 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
fa fd 00 00 00 00 40 78 0b 00 00 00 00 44 90 01 04 00 00 f4 01 00 00 00 00 00 00 00 00 00 00 00 71 83 50 33
d5 07 00 1b 00 00 a0 52 1f 00 00 00 00 2b 00 00 10 00 00 0c 00 00 00 00 00 00 00 00 00 00 00 00 29 2c ae cc
2f fa 00 1b 00 00 e0 9d c2 03 00 00 00 ee 00 00 10 00 00 14 00 00 00 00 00 00 00 00 00 00 00 00 4d 05 0b f8
f6 fb 00 00 00 00 60 c4 73 00 00 00 00 36 01 10 14 00 00 3c 00 00 00 00 00 00 00 00 00 00 00 00 1a 5c f5 07
f9 fb 00 00 00 00 c0 b3 22 00 00 00 00 f0 fc 1f 14 00 00 14 00 00 00 00 00 00 00 00 00 00 00 00 0f f7 f3 00
0f 00 00 00 00 00 20 61 08 00 00 00 00 00 fc 1f 00 00 00 0c 00 00 00 00 00 00 00 00 00 00 00 00 9b f8 46 82
00 00 00 00 00 00 40 38 19 00 00 00 00 00 fb 1f 00 00 00 74 00 00 00 00 00 00 00 00 00 00 00 00 95 f9 cd 75
e2 00 00 00 00 00 c0 68 f7 00 00 00 00 23 fb 0f 14 00 00 1c 00 00 00 00 00 00 00 00 00 00 00 00 d6 fe 7b f7
e2 00 00 00 00 00 60 17 1a 00 00 00 00 07 00 00 00 00 00 34 00 00 00 00 00 00 00 00 00 00 00 00 55 cd fd f5
36 00 00 36 00 00 c0 3f 39 00 00 00 00 f1 e5 01 14 00 00 0c 00 00 00 00 00 00 00 00 00 00 00 00 0f b1 f1 35
36 00 00 36 00 00 80 72 5c 00 00 00 00 d3 1a 11 08 00 00 14 00 00 00 00 00 00 00 00 00 00 00 00 19 68 ea ce
30 d2 88 f1 00 00 20 a3 f9 01 00 00 00 05 ff 00 08 00 00 fc 00 00 00 00 00 00 00 00 00 00 00 00 09 0f 1a e1
c7 30 85 0d 00 00 a0 f2 17 00 00 00 00 31 00 00 00 00 00 14 00 00 00 00 00 00 00 00 00 00 00 00 89 e5 87 ef
f7 e2 0d 03 00 00 20 a1 09 00 00 00 00 31 00 00 00 00 00 0c 00 00 00 00 00 00 00 00 00 00 00 00 8f e6 7e f7
33 fc 72 2c 00 00 40 e8 3a 00 00 00 00 06 01 10 00 00 00 34 00 00 00 00 00 00 00 00 00 00 00 00 e0 e6 06 f7
33 fc 77 d3 00 00 60 a3 0b 00 00 00 00 37 01 10 14 00 00 1c 00 00 00 00 00 00 00 00 00 00 00 00 7a e2 00 bd

Now makes the statistics:

Code: [Select]

  40975  1c
  45391  1f
  55494  82
  58589  0f
  63518  10
  67533  0c
  75553  40
  83274  c0
  85332  01
 152862  14
 169547  ff
5618071  00

Second set of encoding - use an 8-bit value to indicate as a bit mask of "these are zeros" and then follow the mask with with the non-zero byte.

Code: [Select]

e2 00 00 00 00 00 60 17 1a 00 00 00 00 07 00 00 00 00 00 34 00 00 00 00 00 00 00 00 00 00 00 00 55 cd fd f5 36 00 00 36

Broken into 8-byte words

Code: [Select]

e2 00 00 00 00 00 60 17
1a 00 00 00 00 07 00 00
00 00 00 34 00 00 00 00
00 00 00 00 00 00 00 00
55 cd fd f5 36 00 00 36

With the mask on front and zeros removed:

Code: [Select]

83 e2 60 17
84 1a 07
10 34
00
F9 55 cd fd f5 36 36

which becomes

Code: [Select]

83 e2 60 17 84 1a 07 10 34 00 F9 55 cd fd f5 36 36

40 bytes to 17 bytes = compression to ~42% of original size

You might need to reset the "last 36" characters array on a block boundary (e.g. every 8192 bytes of output) so you can recover from a partial file corruption.

[ebclr]

https://www.segger.com/products/compression/emcompress/

https://youtu.be/a6dqhmb3lVE

[hamster_nz]

Running with this far more than I should...

Here is a filter to take STDIN and compress it to STDOUT:

Code: [Select]

#include <stdio.h>

static char last[36];
static char emitting[8];
static int emit_count = 0;
static int emit_mask = 0;
static int emit_data_count = 0;

static void emit(char c) {
  int i;
  if(c) {
     emit_mask |= 1<<emit_count;
     emitting[emit_data_count++] = c;
  }
  emit_count++;

  if(emit_count != 8)
     return;

  putchar(emit_mask);
  for(i = 0; i < emit_data_count; i++)
     putchar(emitting[i]);

  emit_data_count = 0;
  emit_count = 0;
  emit_mask = 0;
}

static void emit_flush(void) {
  int i;
  // Zeros that are explicitly added at the
  // end of file, not by the "zero mask" are padding
  while(emit_count != 8)
  {
    emit_mask |= 1<<emit_count;
    emitting[emit_data_count++] = 0x00;
    emit_count++;
  }

  putchar(emit_mask);
  for(i = 0; i < emit_data_count; i++)
     putchar(emitting[i]);

  emit_data_count = 0;
  emit_count = 0;
  emit_mask = 0;
}

int main(int argc, char *argv[]) {
   int i = 0, c;
   c = getchar();

   while(c != EOF) {
      emit((c^last[i]) &0xFF);
      last[i] = c;
      if(i == sizeof(last)-1) {
         i = 0;
      } else {
         i++;
      }
      c = getchar();
   }
   emit_flush();
}

And here is the opposite to expand STDIN to STDOUT:

Code: [Select]

#include <stdio.h>

char last[36];
int last_i;
void emit(char c) {
   c ^= last[last_i];
   putchar(c);
   last[last_i] = c;

   if(last_i == sizeof(last)-1)
       last_i = 0;
   else
       last_i++;
}

int main(int argc, char *argv[]) {
  int mc;
  int mask;
  mc = getchar();
  while(mc != EOF) {
     int c;
     mask = 0x1;
     while(mask != 0x100) {
       if((mc&mask) == 0) {
         emit(0);
       } else {
         c = getchar();
         if(c != EOF && c != 0)
           emit(c);
       }
       mask = mask << 1;
     }
     mc = getchar();
  }
}

Very simple, and compresses the test 8,660,615 byte file to 4,125,122 bytes (47% of original size).


Algorithm requirements (UPDATED):
- Implemented on ARM Cortex-M7 running 300 MHz  not tested - assume yes
- Algorithm cannot use heap (malloc) Tick!
- Support for fast shutdown, max ~50 ms (likely not working if large output / working buffers are used) Tick!
- Flash usage <100kb (the flash could potentially store a static dictionary) Tick!
- Ram usage <30kb Tick!
- Target compression rate > 40% on test data file Tick!
- System is currently running at 30% idle time. Target idle time with compression >20% not tested - assume yes
- Entire file zipped Tick!
- Lossless compression Tick!

[Siwastaja]

Good work.

All the data isn't in 36-byte records; there will be jumps like this:

Code: [Select]

00 02 08 00 00 00 8b ff ff ff ff ff fa ff 01 00 80 56 b8 82 81 a2 42 00 ca fe 98 06 06 12 a1 03 00 00 00 00
00 02 06 00 00 00 00 ff 00 00 00 00 01 00 a0 f7 bf 82 81 a2 42 05 ff ef 8c 08 08 1c a1 03 00 00 00 00 00 02

Where you can see the 82 81 pattern, which is clearly a part of a time stamp, jump by 2 bytes - so that particular frame is only 34 bytes. But they happen surprisingly rarely, so most messages are of the same length - probably 36 bytes is the maximum possible, since all jumps happen to the left.

The proposed "look-back-36-bytes" compression works so well because the jumps are so rare.

Code: [Select]

08 00 00 00 ff 0e 61 ff 07 ff ff ff 01 00 80 75 2c 95 81 a2 42 06 ff ea 98 03 03 08 ac 03 00 00 00 00 00 02
03 00 00 00 e5 fe 00 01 00 20 a4 8f 95 81 a2 42 06 00 ef 84 08 08 0f ac 03 00 00 00 00 00 02 08 00 00 00 64

This frame shows a 5-byte jump (pattern 95 81), i.e., it's a 31-byte record.


Why I looked it like this, I'm trying to guesstimate how many bits there is in the timestamp. It clearly has at least 4 bytes (you can see an increasing value pattern on 4 bytes) , but I'd guess there are more: one more on the LSB side, which is basically a random value due to the timestamp having enough resolution, and another on the MSB side, which is just fixed in such short capture. So maybe 6 bytes?

I guess it's this:

Code: [Select]

20 01 00 e0    9b b5 47 83 a2 42    06 fb ff 98 08 08 31 ce 04 00 00 00 00 00 02 08 00 00 00 00 05 85 d8 ff ff ff
ff 01 00 a0    c3 be 47 83 a2 42    05 fe ff 8c 08 08 3d ce 04 00 00 00 00 00 02 08 00 00 00 8b ff ff ff ff ff fa
ff 01 00 c0    64 c6 47 83 a2 42    05 ff ef 8c 08 08 49 ce 04 00 00 00 00 00 02 08 00 00 00 6c 51 84 09 00 00 21
1d 01 00 80    8c cf 47 83 a2 42    05 ff ef 8c 08 08 55 ce 04 00 00 00 00 00 02 08 00 00 00 6e 29 02 00 c0 f1 ff
ff 01 00 c0    41 34 48 83 a2 42    00 04 f0 8c 08 08 61 ce 04 00 00 00 00 00 02 08 00 00 00 f1 ff 8f 8c 1c ff ff
ff 01 00 80    69 3d 48 83 a2 42    00 df fe 98 08 08 6d ce 04 00 00 00 00 00 02 08 00 00 00 82 20 1d ff ff ff ff
00 01 00 e0    4c 54 48 83 a2 42    8c fe ff 8c 08 08 79 ce 04 00 00 00 00 00 02 08 00 00 00 63 ff ff fc ff ff ff

0x42 has to be the MSB - bytes after it change and can't be a part of the timestamp.
e0, a0, c0, 80, c0, 80, e0 clearly indicate some flags or similar, and are not the LSB of the timestamp.

I would guess these are raw CAN frames with added logging header, which obviously has a timestamp. With 6 bytes in timestamp, and raw extended frame being max 16 bytes, there are still 14 more bytes in the logger-generated header.

Getting rid of excess "extra" data, whatever it is in the headers, would help a lot in data reduction.

Timestamp can be reduced to 2 or 3 bytes likely (if you can guarantee no long silent breaks, and just let it wrap and reconstruct the MSBs later), and maybe you can just throw away everything else on that logger header.

It seems, the actual CAN frames only use 16/36 = 44% of the data - 56% is logger headers.

[Martin F]

Hi again,

Thanks for all the great inputs!

I'll try to provide some more detail on the specific format soon. Note that the sample I included is indeed raw CAN data from a tractor, aka J1939. In most J1939 cases there are 8 data bytes - but in other cases the data length may be lower, i.e. 1-8 data bytes. It can also be CAN FD, which is up to 64 data bytes. So in short, the data bytes will vary. There might be some optimization along your lines that could be implemented for specific cases (e.g. a J1939 specific compression), but for the general case the data length will vary.

Best,
Martin

[Jeroen3]

LZ4 seems to have:

Code: [Select]

/*
 * LZ4_HEAPMODE :
 * Select how default compression functions will allocate memory for their hash table,
 * in memory stack (0:default, fastest), or in memory heap (1:requires malloc()).
 */
So your heap requirement is not a problem.

[cv007]

Just curious what the underlying need for the compression happens to be. It would seem in any case once you get to a certain point, you either get a bigger sd card or use some form of compression, and those two choices follow you all the way up until sd card size limitations kick in (hardware or software). If you eliminate compression, you just move yourself 1/2 step forward in upgrading sd card sizes. I doubt the price of sd cards is a factor (if talking about tractors), so must be something else (not that there has to be a reason).

One thing maybe to consider in any compression methods, is how easy it is to deal with any corruption that may occur in the path of writing/storing/reading. Maybe its too uncommon to worry about though, although if it did happen and the data was important I suppose dealing with something more like raw data would be easier to recover. I'm not sure I would want to be on the cutting edge of compression techniques, and later wish I had just used a bigger sd card instead and avoided any problems.

I guess I'm just wondering when compression is a good idea, and when it is not.

[Martin F]

Hi cv007, your inputs make a lot of sense. The challenge here is that the data will be periodically offloaded from the SD card via WiFi or 3G/4G. The period in which a WiFi hotspot is available for the offload can be limited, so the more throughput we can achieve per minute, the better. This gives a secondary purpose to the compression beyond only saving SD capacity. For 3G/4G uploading at scale, it has direct cost implications that can be relatively impactful in business cases utilizing the device. But you're completely right that for the pure SD card aspect, it would probably not be worth it alone.

[mariush]

Let me throw some suggestions around.

Have you considered using some binary serialization format, like MessagePack or BSON?

Have you investigated using something super simple like plain LZ77 or the Palmdoc version of LZ77?
See https://wiki.mobileread.com/wiki/PalmDOC and https://en.wikipedia.org/wiki/LZ77_and_LZ78  and sourcecode for PalmDOC compression and compression : http://bazaar.launchpad.net/~kovid/calibre/trunk/view/head:/src/calibre/ebooks/compression/palmdoc.c

The PalmDOC format uses 4K blocks independent of each other and everything's in 2 bytes so it's fast to compress and uses very little memory.

I believe Crush ( https://sourceforge.net/projects/crush/files/CRUSH/1.00/crush100src.zip/download ) uses a LZ77 variant ... i tested on the 8 MB sample and compressed it down to 3,122,328 bytes

If you have multi-byte numbers but most values are small, maybe see if it's worth encoding numbers as variable length?
ex
* like UTF-8 encoding ( https://en.wikipedia.org/wiki/UTF-8#Description ) or
* just plain bit set to 1 means more bytes follow, 0 means it's last byte (so anything less than 128 would use 1 byte, anything that uses less than 14 bits can be stored in 2 bytes and so on)

[Siwastaja]

Hi again,

Thanks for all the great inputs!

I'll try to provide some more detail on the specific format soon. Note that the sample I included is indeed raw CAN data from a tractor, aka J1939. In most J1939 cases there are 8 data bytes - but in other cases the data length may be lower, i.e. 1-8 data bytes. It can also be CAN FD, which is up to 64 data bytes. So in short, the data bytes will vary. There might be some optimization along your lines that could be implemented for specific cases (e.g. a J1939 specific compression), but for the general case the data length will vary.

Best,
Martin

Hi Martin,

What is the purpose for the logging? Is it to prove something legally, or for "unknown" future purposes, so that you need to store every header bit-by-bit, and add enough ancillary information such as precise timestamps?

If not, how about just getting rid of the large headers, and just saving the raw CAN packet, possibly with a minimized timestamp (think about a 3 or 4 byte header, instead of 20 bytes you seem to now have). 1 byte would signify the total CAN frame len, and two bytes for timestamp.

As for CAN data, why not drop everything except ID, data, CRC and possibly the RTR & ACK bits? You could go from 128 bits (assuming extended frame with 8 bytes payload) to about 110 bits, (from 16 bytes to to 14 bytes.

It would be kinda elegant to fit a full 8 bytes of payload to 16 bytes, with the timestamp. This would be a larger reduction (-56%) than you specified, without any compression and not much trickery.

[cv007]

>The challenge here is that the data will be periodically offloaded from the SD card via WiFi or 3G/4G

I thought the data transfer rate going out would be a prime suspect, but dismissed that I as was only thinking of some direct method via pc (card reader, usb, etc). Wireless had not crossed my mind, although just like compression its all around me and largely goes unnoticed.

I guess you could still log to the sd card in 'raw', then use compression of some form on the upload. Maybe it does not matter when it is done, but the option to move the process to only when its needed may be useful. Maybe not.

Sorry for the slight detour.

[Mechatrommer]

the 1MB/minute (16KBps) is hardly categorized as high speed in Wifi world (lowest CAN bus speed spec), except if using china generic 433MHz radio, cheapest price internet subscription plan or interplanetary communication. but some other aspects may call for the compression scheme, such as to maximize data storage in a specified capacity storage device. to some, it matters if a DSO has 12 vs 24Mpts capacity, but with compression, the spec can be upped using 12Mpts HW to store 24Mpts data, so the DSO can be (BOM) cheaper at same the spec as more expensive HW device and hence win. DSO example maybe not suitable as its quite difficult to implement real time compression at GSps rate unless extra FPGA/MCU power (price) is provided but OP has demonstrated the need in his case earlier. if we have more/extra processing power at $0 cost, it will be better to be able to store double the capacity given a storage device size, we can also transmit double the speed in the air from what it can in uncompressed state, fwiw.

[Martin F]

To clarify, the device logs data to an SD card - it may be without WiFi for days or weeks. When it reaches WiFi, it may have e.g. 10 minutes to offload all the data - sometimes gigabytes. We considered compression during the transfer, but the challenge with this is that the data also needs to be encrypted in real-time on the SD card, as some users may have highly sensitive data. The encryption can only happen after the compression - hence our setup.

[Berni]

The most effective compression algorithms will always be the ones that are "content aware". This is why JPEG, PNG, GIF, FLAC, MPEG4 etc... exist

But that being said developing the custom algorithm for your application can take a LOT of work. Noisy data is quite annoying to lossless compression since it has a lot of "detail" that has to be perfectly captures yet it completely unpredictable. For waveform data this is usually dealt with applying lossy compression, taking the compression error and saving it along the data(But this data might only need 8bits of depth). But if lossy compression is acceptable then you can get really staggering compression ratios that get the data size bellow 10% of its original size while looking pretty much the same to a human looking at it.

This approach also makes progressive data transfer possible. Where you first send the lossy compressed data only, but then start sending the fine correction waveform to fix the compression errors and make it lossless again. That way the first part of the transfer already delivers usable data if it gets cut off mid transfer. A similar idea to this is used by progressive mode JPEG where the image in a browser can already be displayed entirely in low quality after the browser only receives the first 1/10th of the image file, the data that comes afterwards contains the rest of the data that is used to take the image to full quality.

[Harjit]

I need to compress log data on an M7 device with similar requirements. The links I've stored away for when I do the work are below. If you happen to benchmark these, I'd be very grateful if you shared the results.

https://github.com/lz4/lz4
https://github.com/atomicobject/heatshrink
https://github.com/richgel999/miniz
https://www.segger.com/products/compression/emcompress/emcompress-togo/

I happen to know Rich (richgel999 link above) and asked him about dynamic allocation and his response is below. Also, Rich is really into compression and has been for years.

From: Rich Geldreich
Sent: Monday, October 08, 2018 8:32 AM
To: harjit
Subject: Re: Hello
 
It's possible to disable malloc/free in miniz by #defining MINIZ_NO_MALLOC. You can't use any of the allocation related API's though, just the API's that take pointers to buffers. The tdefl and tinfl functions don't use malloc directly.

[hamster_nz]

Did you get anywhere with this?

Last night I played with a very simple sliding window compression....

[Martin F]

Hi again,

We will be looking into this over the next weeks.

We'll be investigating 2 options to start with, Zstandard (zstd) and emCompress by Segger. We're also investigating some more custom routines on the side, but the aim is to get an initial idea of the performance of those two first. It's worth noting that the dataset we shared was probably overly simplistic - there can be variations in many cases, e.g. instead of a fixed 8 data byte set, we can have between 1 and 64 data bytes, as well as regular/extended length IDs.

We looked at LZ4 and zstd and for now we'll try zstd first as we found the decoding simpler, while zstd also more prominently seems to feature the option of using static dictionaries. While we don't yet know if this will be the ideal route, it's nice to have the option.

As for emCompress, it seems quite tailor fit for the purpose and we've used SEGGER products in the past with good experiences. The price tag is not the main issue, so it's more a matter of whether we can use the decoding code as e.g. a *.dll file and keep it with the rest of our open source code on github. We're getting this clarified hopefully this week.

Martin

[brucehoult]

"we'll try zstd first as we found the decoding simpler"

You've got to be kidding.

lz4 has an incredibly simple format, which can be decoded with about a dozen lines of C. zstd format is extremely complex, and you need to juggle nested data blocks at several different levels, huffman trees .. all kinds of stuff.

Both lz4 and zstd were created by the same person, but with very different aims. lz4 is *fast*. Very fast. Compression is significantly faster than zstd and decompression is about 3x faster. But zstd has a much higher compression ration -- one of the best available.

Unoptimized lz4 decompression is as simple as this (I just tested it on an lz4 file with the initial header removed -- it's correct)

Code: [Select]

char *decompress(FILE *f, char *outPtr){
  int tok, n;
  while (tok = fgetc(f)){
    int litLen = (tok>>4)&0xf, copyLen = tok&0xf;
    if (litLen == 15) do {n=fgetc(f); litLen += n;} while (n == 255);
    for (int i=0; i<litLen; ++i) *outPtr++ = fgetc(f);
    int copyOff = fgetc(f) + fgetc(f)*256;
    if (copyLen == 15) do {n=fgetc(f); copyLen += n;} while (n == 255);
    char *copySrc = outPtr-copyOff;
    for (int i=0; i<copyLen+4; ++i) *outPtr++ = *copySrc++;
  }
  return outPtr;
}


[mariush]

I mentioned the PalmDOC compression a few posts above...

I wrote a code to compress and decompress using this algorithm, written in PHP... see attachment.
It's less than 200 lines of actual code, and you'll need less than 10 KB of RAM to compress 4 KB chunks (less if you use 2 KB chunks)
Well technically, you could compress with less than 1 KB of ram used, but it would be very slow... I'm using ram as a "dictionary" to get speed
You can encode and decode each chunk separately and you can append the compressed blocks without any problems as everything is done in bytes.

[Marco]

No idea about the (code) quality, but since there's no prediction based codec mentioned yet there's also Sprintz. An IoT codec for uniformly sampled time series data.

https://github.com/dblalock/sprintz