Results 1 to 11 of 11

Thread: RLE64

  1. #1
    Member nikkho's Avatar
    Join Date
    Jul 2011
    Location
    Spain
    Posts
    546
    Thanks
    219
    Thanked 164 Times in 105 Posts

    RLE64

    You can try too my simple RLE64 compressor/decompressor at http://guti.isgreat.org/static.php?page=RLE64.

    Even if ratio is quite bad, speed, is quite high.

  2. #2
    Member
    Join Date
    Aug 2011
    Location
    Canada
    Posts
    113
    Thanks
    9
    Thanked 22 Times in 15 Posts
    I also wrote a RLE compressor.
    Attached Files Attached Files

  3. #3
    Member nikkho's Avatar
    Join Date
    Jul 2011
    Location
    Spain
    Posts
    546
    Thanks
    219
    Thanked 164 Times in 105 Posts
    Quote Originally Posted by david_werecat View Post
    I also wrote a RLE compressor.
    I am not sure if it is faster while compressing/decompressing compared to my implementation, probably not, but the compression ratio, is a bit higher than my 8 bit implementation, so well done.
    Just curious about its source code implementation.

  4. #4
    Member
    Join Date
    Aug 2011
    Location
    Canada
    Posts
    113
    Thanks
    9
    Thanked 22 Times in 15 Posts
    Thanks! The source code is written without the CRT, so it might be a little cluttered. It's basic encoding scheme is when two consecutive bytes are of the same value, it writes one byte specifying the run length. It could compress better if it used encoding to allow for >255 byte runs, but I haven't implemented it yet. Here is the main source code:
    Attached Files Attached Files

  5. #5
    Member nikkho's Avatar
    Join Date
    Jul 2011
    Location
    Spain
    Posts
    546
    Thanks
    219
    Thanked 164 Times in 105 Posts
    I like a lot the RLE variant you have implemented, with less overhead than mine that uses a compressed block marker, needing one additional byte.
    Nevertheless, I do not like the implementation, that required reading byte per byte from the file.

  6. #6
    Member nikkho's Avatar
    Join Date
    Jul 2011
    Location
    Spain
    Posts
    546
    Thanks
    219
    Thanked 164 Times in 105 Posts
    By the way, on some high end machines, it has been reported to be able to compress at more than 6 Gigabytes per second (limited by memory bandwith):
    Code:
    RLE64 R3.00 - (c) 2011 by Javier Gutierrez Chamorro - http://guti.isgreat.org
    A fast Run Length Encoding (RLE) compressor / decompressor.
    
    Compressing girl.bmp (403920054 bytes)... Compressed girl.bmp in 61 ms (6621 MiB/s).
    Uncompressing girl.bmp.rle64 (21910710 bytes)... Uncompressed girl.bmp.rle64 in 109 ms (3705 MiB/s).

  7. #7
    Member
    Join Date
    Aug 2011
    Location
    Canada
    Posts
    113
    Thanks
    9
    Thanked 22 Times in 15 Posts
    That's very impressive! Nice work on the high speed!

    Also, for mine the file IO is buffered, so it reads 2mb chunks at a time. The function 'ReadBufferedByte' reads from the buffer and handles refilling it. It keeps memory usage low, but has minor speed impacts.
    Last edited by david_werecat; 19th August 2011 at 21:27.

  8. #8
    Member biject.bwts's Avatar
    Join Date
    Jun 2008
    Location
    texas
    Posts
    449
    Thanks
    23
    Thanked 14 Times in 10 Posts
    Quote Originally Posted by david_werecat View Post
    Thanks! The source code is written without the CRT, so it might be a little cluttered. It's basic encoding scheme is when two consecutive bytes are of the same value, it writes one byte specifying the run length. It could compress better if it used encoding to allow for >255 byte runs, but I haven't implemented it yet. Here is the main source code:
    I have written many version of RLE over the years. But if your currently doing what you say. Then it is very wasteful of space ( and therefore not bijective). I don't think it would cost much in time to fix this waste of space in compressing.

    First look at decompression:

    XX2XX3 might decompress to 9 X's as would
    XX7

    One way to fix this and and still allow the number field to be 0 to 255 extra bytes
    meaning
    X is 1 X
    XX0 is 2 is 2 X's
    XX255 is 257 X's the 255 stands for 255 extra X's
    allow
    XX0X to be 258 X's where the repeated character after number field is an extra 256 X's
    like wise
    XX3XX would be 2 + 3 + 2 * 256 or 517 X's

    This would not be hard to add and the output still not bijective. But it wastes less space while trying to follow your flavor of RLE.
    To make it bijective would require speical handling if last characters a repeat
    example if file ends in 1 X then X is out
    if 2 X's then XX out at end no number field
    then XX[n] would mean the n stands for 1 to 256 extra characters instead of 0 to 255 the trailing X's after the N could still stand for an extra 256 characters each.

  9. #9
    Member
    Join Date
    Aug 2011
    Location
    Canada
    Posts
    113
    Thanks
    9
    Thanked 22 Times in 15 Posts
    Thanks! I actually already do the extra bytes encoding method, but I guess I didn't describe it properly (I meant to put 257 byte runs...). Having single values after a run marker equate to 256 extra characters is a very good idea. I'll add this to my implementation soon.

  10. #10
    Member
    Join Date
    Aug 2011
    Location
    Canada
    Posts
    113
    Thanks
    9
    Thanked 22 Times in 15 Posts
    Version 1.1 adds in some of the ideas from biect.bwts. Thanks again for your suggestions. Also, a second 'large runs' mode has been added, which uses compact headers to mark runs up to 2^64 bytes in length. The 'large run' mode has very small losses to compression on files with small runs, but has huge gains for files with extremely long runs.

    note to nikkho: I hope that you don't mind me posting these on your thread...
    Attached Files Attached Files
    Last edited by david_werecat; 20th August 2011 at 09:04.

  11. #11
    Member nikkho's Avatar
    Join Date
    Jul 2011
    Location
    Spain
    Posts
    546
    Thanks
    219
    Thanked 164 Times in 105 Posts
    Quote Originally Posted by david_werecat View Post
    Version 1.1 adds in some of the ideas from biect.bwts. Thanks again for your suggestions. Also, a second 'large runs' mode has been added, which uses compact headers to mark runs up to 2^64 bytes in length. The 'large run' mode has very small losses to compression on files with small runs, but has huge gains for files with extremely long runs.
    Good work david_werecat!

    Quote Originally Posted by david_werecat View Post
    note to nikkho: I hope that you don't mind me posting these on your thread...
    Of course not, it is a pleasure.

Posting Permissions

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