Results 1 to 13 of 13

Thread: Good Compression for Microcontrollers

  1. #1
    Member elektronika's Avatar
    Join Date
    Mar 2010
    Location
    Indonesia
    Posts
    9
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Good Compression for Microcontrollers

    Dear All,

    I am new in compression, I have searched and built some compression algorithm in my PC. I want to make a simple benchmark on the PC. The final product will be inside the microcontroller. The microcontroller will run at ~~400MHz so it is a quite powerful one. My question is how should I choose the compression algorithms? For example I read Balz by encode is a bit heavy (requires core2duo or something like that) so I can't use it in my project.

    Kindest Regards,




    E

  2. #2
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,507
    Thanks
    742
    Thanked 665 Times in 359 Posts
    you should select compression algo that provides best compression ratio for your data within given limitations of c/d speed and memory

  3. #3
    Member elektronika's Avatar
    Join Date
    Mar 2010
    Location
    Indonesia
    Posts
    9
    Thanks
    0
    Thanked 0 Times in 0 Posts
    And how to know it? So what comes into my mind is that I make a benchmark of several compressors (7zip, zlib, balz, dark, etc) inside the PC and discuss it with my friends. And in the end port it to the microcontroller.

    How to test the compressors inside the PC with how much it use ram memory? I ve done some benchmark regarding speed and compression ratio, but yeah..the processing power and memory usage needed for the compressor is unknown. Any idea how to measure it?

  4. #4
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,474
    Thanks
    26
    Thanked 121 Times in 95 Posts
    It heavily depends on characteristics of that microcontroller. For example most compressors depends on latency of RAM access.

    Most compressors are not realtime so there's nothing like "required processing power". On slower processor the compression will be slower but it will work (provided enough memory). Also memory usage can be tuned for various applications.

  5. #5
    Member
    Join Date
    May 2008
    Location
    Germany
    Posts
    410
    Thanks
    37
    Thanked 60 Times in 37 Posts
    if you have only small memory within the microcomputersystem,
    then i propose you

    lzo-compression
    http://www.oberhumer.com/opensource/lzo/
    http://www.lzop.org/


    if you have many memory,
    then i propose you

    ppmd-compression
    especially the new-rewritten-version within 7z

    http://sourceforge.net/projects/seve.../topic/3604593


    other popular good compression-method:

    bzip2-compression (is too within 7z)


    of course the best compression method depends from

    - which data you want to compress: is it text, natural text or binary data ?
    - how many time do you have to compress ?
    - do you want to compress often
    or do want to compress once and often decompress ?

    best regards

  6. #6
    Member elektronika's Avatar
    Join Date
    Mar 2010
    Location
    Indonesia
    Posts
    9
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Memory

    I think I will have a fair large memory (not until GB though)...around MB maybe...

    and the file that I want to compress is not big either. I have seen LZO from oberhumer and have tested it, it is really fast, but not that good in compression ratio. (I tested it inside PC)

    I have tested the bzip2 also inside PC.

    7zip give lzma sdk and I ve tested that also. 7zip has some compression algorithms that make me confused and just take the lzma sdk. How to just take the ppmd algorithm?

    The data itself is still unknown. But for sure it is not a text nor a picture nor sound. It will be just some measurement data with numbers. The microcontroller will only compress the data. No decompression.
    How often do it needs to compress is also unclear yet.

  7. #7
    Member
    Join Date
    May 2008
    Location
    Germany
    Posts
    410
    Thanks
    37
    Thanked 60 Times in 37 Posts
    you wrote
    "It will be just some measurement data with numbers."

    if it is floating-point data
    - then there are some specialized algorithm -
    for example:
    http://www.csl.cornell.edu/~burtscher/research/FPC/

    if it are fixed-point-numbers

    then you can first try to store the data as binary coded decimals ...

  8. #8
    Member
    Join Date
    Sep 2008
    Location
    France
    Posts
    863
    Thanks
    461
    Thanked 257 Times in 105 Posts
    I suspect memory limitation will be the most important part to tame for your project. Many compression algorithm just span or need large amount of tables, sometimes parameterable up to a limit, so a few MB could be too little for some of them, and more than enough for others.

    The second point is data itself. Measurement data, this is a bit more precise.
    What size is this measurement data ?
    This can really change your need. Depending if you are talking of KB, tens, thousands or MB, optimal algorithm is going to be very different.

    Then comes speed of course. Your application does not look real time, so it should not be a large issue, provided that compression time are not too large, obviously strongest algorithms are out of the loop, but this shouldn't be a problem.

    Writing compression algorithms for lightweight embedded devices is fun. You'll be surprised how much compression can be tuned for this class of application. Re-using PC algorithm is one way to go, and usually not the most appropriate. But if it fits your need, then why not...

  9. #9
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,372
    Thanks
    213
    Thanked 1,020 Times in 541 Posts

  10. #10
    Member
    Join Date
    May 2008
    Location
    Germany
    Posts
    410
    Thanks
    37
    Thanked 60 Times in 37 Posts
    @shelwien: thanks for the link!

    it was new for me that PPM works good with such a small memory!

    ---
    igor pavlov has rewritten the ppmd-compression-code especially for using within zip-files

    http://sourceforge.net/projects/seve.../topic/3604593
    ---

    quick test: (db.dmp has 648.331.264 Bytes)

    ppms e -fdbp2 -o2 db.dmp - resulting file has 82.866.212 Bytes
    ppms e -fdbp3 -o3 db.dmp - resulting file has 55.691.929 Bytes
    ppms e -fdbp4 -o4 db.dmp - resulting file has 40.921.395 Bytes
    ppms e -fdbp5 -o5 db.dmp - resulting file has 35.051.304 Bytes
    ppms e -fdbp6 -o6 db.dmp - resulting file has 32.934.400 Bytes
    ppms e -fdbp7 -o7 db.dmp - resulting file has 31.861.241 Bytes
    ppms e -fdbp8 -o8 db.dmp - resulting file has 31.560.807 Bytes

    ---
    c:\COMPRESS\PGM>ppms e -fdbp2 -o2 db.dmp
    Small PPMII compressor with 1024KB memory heap, variant J, Feb 21 2006
    db.dmp:648331264 >82866190, 1.02 bpb, CutOffs: 34,
    speed: 20636 KB/sec

    c:\COMPRESS\PGM>ppms e -fdbp3 -o3 db.dmp
    Small PPMII compressor with 1024KB memory heap, variant J, Feb 21 2006
    db.dmp:648331264 >55691907, 0.02 bpb, CutOffs: 75,
    speed: 23120 KB/sec

    c:\COMPRESS\PGM>ppms e -fdbp4 -o4 db.dmp
    Small PPMII compressor with 1024KB memory heap, variant J, Feb 21 2006
    db.dmp:648331264 >40921373, 0.04 bpb, CutOffs:163,
    speed: 23517 KB/sec

    c:\COMPRESS\PGM>ppms e -fdbp5 -o5 db.dmp
    Small PPMII compressor with 1024KB memory heap, variant J, Feb 21 2006
    db.dmp:648331264 >35051282, 0.04 bpb, CutOffs:453,
    speed: 22827 KB/sec

    c:\COMPRESS\PGM>ppms e -fdbp6 -o6 db.dmp
    Small PPMII compressor with 1024KB memory heap, variant J, Feb 21 2006
    db.dmp:648331264 >32934378, 0.01 bpb, CutOffs:1144,
    speed: 19498 KB/sec

    c:\COMPRESS\PGM>ppms e -fdbp7 -o7 db.dmp
    Small PPMII compressor with 1024KB memory heap, variant J, Feb 21 2006
    db.dmp:648331264 >31861219, 0.00 bpb, CutOffs:2490,
    speed: 16918 KB/sec

    c:\COMPRESS\PGM>ppms e -fdbp8 -o8 db.dmp
    Small PPMII compressor with 1024KB memory heap, variant J, Feb 21 2006
    db.dmp:648331264 >31560785, 0.06 bpb, CutOffs:4479,
    speed: 14139 KB/sec
    ---

    ---
    7z 9.11: we give the 7z-compressor only 1 MByte memory
    ---
    7z a a.zip -mm=ppmd -mmem=64m -mo=10

    -mo={N} Order (word size) (2-16)
    -mmem={N} Memory usage (1m-256m)

    Default values for different -mx switches:
    -mx1: -mmem=1m -mo=4
    -mx3: -mmem=4m -mo=6
    -mx5: -mmem=16m -mo=8
    -mx7: -mmem=64m -mo=10
    -mx9: -mmem=128m -mo=16
    ---
    7za a dbz104.zip -mm=ppmd -mmem=1m -mo=4 db.dmp - resulting file has 41.797.473 Bytes
    7za a dbz105.zip -mm=ppmd -mmem=1m -mo=5 db.dmp - resulting file has 36.547.543 Bytes
    7za a dbz106.zip -mm=ppmd -mmem=1m -mo=6 db.dmp - resulting file has 35.294.135 Bytes
    7za a dbz107.zip -mm=ppmd -mmem=1m -mo=7 db.dmp - resulting file has 35.326.059 Bytes
    7za a dbz108.zip -mm=ppmd -mmem=1m -mo=8 db.dmp - resulting file has 35.968.193 Bytes
    7za a dbz109.zip -mm=ppmd -mmem=1m -mo=9 db.dmp - resulting file has 36.685.704 Bytes
    7za a dbz110.zip -mm=ppmd -mmem=1m -mo=10 db.dmp - resulting file has 37.515.309 Bytes
    7za a dbz111.zip -mm=ppmd -mmem=1m -mo=11 db.dmp - resulting file has 38.711.891 Bytes
    7za a dbz112.zip -mm=ppmd -mmem=1m -mo=12 db.dmp - resulting file has 39.692.770 Bytes

    ---
    igor pavlov wrote:
    ---
    PPMD var.I supports additional mode (CUT-OFF)
    that can be slightly better in compression ratio for big files,
    but original PPMD code and WinZip contain bug in that code,
    so I have disabled that mode now to keep compatibility with WinZip decoder.
    If Dmitry Shkarin (PPMD author) fixes it and WinZip updates that code,
    maybe I'll enable CUT-OFF mode.
    ---
    FAZIT: if we give the compressor only 1 MByte memory
    then ppms compresses sometimes clearly better then the ppmd from 7z
    ---

    ask: Is the compression from ppms only better
    because the "not included (CUT-OFF) mode" ?

    @shelwien:
    Have you any hints why ppms compresses better ?

    can we tune the ppmd from within 7z ?

    @elektronika:
    if this will be possible then i think i have a clear favorit for you:

    ***
    creating a zip-file by using the ppmd method from 7zip
    ***

    best regards

  11. #11
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,372
    Thanks
    213
    Thanked 1,020 Times in 541 Posts
    In ppms, pointers are allocated separately from context tree, so its more compact.
    So it can store more statistics in the same space, thus better compression.

    Also there's no sense to look into 7z for ppmd:
    http://compression.ru/ds/ppmdj1.rar
    http://ctxmodel.net/files/PPMd/ppmd_Jr1_sh8.rar

  12. #12
    Member elektronika's Avatar
    Join Date
    Mar 2010
    Location
    Indonesia
    Posts
    9
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by Shelwien View Post
    Thank you Shelwien..I saw in the website it needs 1MB or less RAM..although it is in russian and the translation in the internet shows really bad result..

    Any idea about the translation?

  13. #13
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,372
    Thanks
    213
    Thanked 1,020 Times in 541 Posts
    Translation of what?
    Its a PPM with suffix tree, nothing else is explained anywhere,
    so you can just read the source.
    Well, there's an article about that modelling method in general:
    http://ctxmodel.net/files/PPMd/ENGPAPER.txt
    But I don't see how it would help you in any way :)

Similar Threads

  1. Replies: 11
    Last Post: 20th February 2008, 11:39

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •