flat assembler
Message board for the users of flat assembler.

flat assembler > Macroinstructions > Assembly-time LZW compression

Author
Thread Post new topic Reply to topic
Tomasz Grysztar
Assembly Artist


Joined: 16 Jun 2003
Posts: 7178
Location: Kraków, Poland
Here comes one of the things I was very eager to try with the new fasm 1.71 features. It's a proof-of-concept code that shows the ability of new fasm to compress some code or data at assembly time. With earlier LOAD/STORE abilities the code could only be rewritten in place, which allowed encoding it but not compression.

To make an example I implemented the LZW algorithm, which is a very simple one and thus it was relatively easy task. This is straightforward implementation and it will be slow on any larger data - nonetheless it shows that the abilities of fasm have improved again.

Code:
virtual at 0
  __data::

      db "Some data to compress...",13,10

      file "test.txt"

  .size = $
end virtual



__LZW__MAX_ENTRIES = 4096

virtual at 0
  __LZW__table::
  dd __LZW__MAX_ENTRIES dup (?,?)
end virtual

__LZW__count = 102h

__LZW__last_byte = 0
__LZW__bit_offset = 0

macro __LZW__write data {
  local c,d,p
  d = __LZW__count-1
  c = 0
  while d
    d = d shr 1
    c = c + 1
  end while
  d = data
  while c > 0
    if __LZW__bit_offset + c >= 8
      p = 8 - __LZW__bit_offset
      db __LZW__last_byte or (d and (1 shl p - 1)) shl __LZW__bit_offset
      __LZW__last_byte = 0
      __LZW__bit_offset = 0
      c = c - p
      d = d shr p
    else
      __LZW__last_byte = __LZW__last_byte or d shl __LZW__bit_offset
      __LZW__bit_offset = __LZW__bit_offset + c
      c = 0
    end if
  end while
}

dictionary_code = 0
string_offset = 0
string_length = 0
scan_from = 102h

while string_offset + string_length < __data.size

  string_length = string_length + 1

  if string_length = 1

    load dictionary_code byte from __data:string_offset

  else

    in_dictionary = 0

    repeat __LZW__count - scan_from
       load entry_offset dword from __LZW__table:(scan_from+%-1)*8
       load entry_length dword from __LZW__table:(scan_from+%-1)*8+4
       if string_length = entry_length
         equal = 1
         repeat string_length
           load a byte from __data:string_offset+%-1
           load b byte from __data:entry_offset+%-1
           if a <> b
             equal = 0
             break
           end if
         end repeat
         if equal
           in_dictionary = 1
           dictionary_code = scan_from+%-1
           scan_from = scan_from+%
           break
         end if
       end if
    end repeat

    if ~ in_dictionary

      __LZW__write dictionary_code

      store dword string_offset at __LZW__table:__LZW__count*8
      store dword string_length at __LZW__table:__LZW__count*8+4
      __LZW__count = __LZW__count+1

      if __LZW__count>=__LZW__MAX_ENTRIES-1
        __LZW__write 100h
        __LZW__count = 102h
      end if

      string_offset = string_offset+string_length-1
      string_length = 0
      scan_from = 102h
    end if

  end if

end while

if string_length > 0
  __LZW__write dictionary_code
  __LZW__count = __LZW__count+1
  __LZW__write 101h
end if

if __LZW__bit_offset > 0
  db __LZW__last_byte
end if    
Post 22 Sep 2012, 14:57
View user's profile Send private message Visit poster's website Reply with quote
f0dder



Joined: 19 Feb 2004
Posts: 3170
Location: Denmark
Tomasz, you are crazy - in the positive sense Smile
Post 25 Sep 2012, 15:41
View user's profile Send private message Visit poster's website Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2019, Tomasz Grysztar.

Powered by rwasa.