LZSS compression for GBA v1.2.03
================================

1. Introduction
   ------------

   Did you notice that a lot of LZSS compressors were asking for a tremendous
   amount of temporary memory space? Do you need every byte of RAM the GBA gives
   you? 
   
   This implementation of the LZSS compression algorithm uses binary trees
   to sort strings. It's based on the original work of Haruhiko Okumura, but 
   with several differences.
   
   First, I don't use any temporary space for the sliding window, I'm just 
   adjusting offsets when needed. Also the sliding window size is 4095 bytes,
   15 more bytes than in the Okumura's original work. There's no buffer for the
   output, and the byte code isn't written sequentially.
   
   Temporary space needed is 25088 bytes, or 25092 bytes if the BUFFER_IN_IWRAM
   option is enabled.
   
   Space needed by some other implementations:
   - Mini LZO : 65536 bytes,
   - Original from Haruhiko Okumura (BST) : 29207 bytes.
   

2. Conditions
   ----------

   By order of importance,

   a) this code has been thought to be in IWRAM, if you can't afford it, 
      maybe you should search somewhere else,
      
   b) temporary buffer MUST be word aligned and can be in IWRAM or 
      in EWRAM (a little slower), 
      
   c) output buffer must be word aligned (the bios decompressing function
      asks it anyway) and can be in IWRAM, EWRAM or even SRAM,
   
   d) no restriction on the input buffer (no alignment, anywhere).


3. Configuration
   -------------
 
   Just uncomment the wanted options in 'lzss.S' before assembling.
 
   By order of performance (big boost -> small boost),

   a) - BIGGER_FASTER_INSERT : little larger code size, big boost,
   
   b) - BIGGER_FASTER_DELINS : larger code size, small boost,
   
   c) - DON'T ENABLE THIS OPTION IF YOUR TEMP SPACE IS NOT IN IWRAM !
        BUFFER_IN_IWRAM : if you have enough IWRAM memory, you can place temp
                          space in it, and enabling this option will speed up
                          the process a little; you will need 4 more bytes of
                          temp space though,
   
   d) - CALLED_MULTI_TIMES : larger code size, if you intend to call
                             the function 100000 times in a row (forget it),
                             
   e) - PAD_WITH_ZEROS : uncomment this if you want to pad zeros at the end
                         of the compressed file, to the next word alignment.
   
   The default configuration is the best one for a good balance between 
   size & speed, but test it yourself and choose the most appropriate
   for your program.
   
   Default is : BIGGER_FASTER_INSERT.
   

4. Assembling
   ----------
   
   With an ARM GAS :
     
     as -mthumb-interwork -mcpu=arm7tdmi lzss.S -o lzss.o
     
   For any other assembler, the source code shouldn't be too hard to convert.


5. Calling
   -------
   
   From GCC, declare this function :
   
     If your own code is anywhere else than in IWRAM :
       extern __attribute__((long_call)) *char LZ77CompWRAM(char*, char*, int, short*, char*);
     
     If your own code is in IWRAM :
       extern *char LZ77CompWRAM(char*, char*, int, short*, char*);
     
     - parameter 1 : pointer to data to compress,
     - parameter 2 : pointer to where data will be compressed,
     - parameter 3 : size of uncompressed data in bytes,
     - parameter 4 : pointer to temporary buffer,
     - parameter 5 : upper limit, only write compressed data before that address,
                     or an error will occur and a value of 0 will be returned,
          
     - return val. : pointer to the first free byte of RAM after the resulting 
                     compressed file; 0 if the compressed file is larger than
                     the uncompressed one (the compression was stopped), or if
                     the upper limit was reached.
     
     Example, to compress in SRAM : 
       
       ret = LZ77CompWRAM(data_2_comp, (char*) 0x0E000000, D2C_SIZE, tmp_buffer, (char*) 0x0E010000);
       if (ret)
         print_comp_size((int) ret - 0x0E000000);
       else
         process_error();
          
          
   From ASM : 
   
     r0-r3 must contain the first 4 parameters, the 5th one being on the stack.
     r0 will contain the return value.
   
6. Uncompressing
   -------------
   
   Just call the bios function 0x11 (WRAM output) or 0x12 (VRAM output) 
   in thumb mode, 0x110000 or 0x120000 in ARM mode. 
   r0 must contain the source address, and r1 the destination.
   
   Here is some GCC code, if you don't know asm :
   
   #ifdef __thumb__
   void uncomp_WRAM(unsigned int src, unsigned int dst)
   {
     asm volatile ( \
     "ldr r0, %0 \n" \
     "ldr r1, %1 \n" \
     "swi 0x11   \n" : \
     : \
     "m" (src), "m" (dst) : \
     "r0", "r1");
   }
   #else /* #ifdef __arm__ */
   void uncomp_WRAM(unsigned int src, unsigned int dst)
   {
     asm volatile ( \
     "ldr r0, %0   \n" \
     "ldr r1, %1   \n" \
     "swi 0x110000 \n" : \
     : \
     "m" (src), "m" (dst) : \
     "r0", "r1");
   }
   #endif /* __thumb__ */

   Example : uncomp_WRAM((unsigned int) &src_adr, (unsigned int) dest_ptr);
   

7. Final Note
   ----------
   
   If you find an error or something, don't hesitate to contact me.

You can find the latest version of this compressor, as well as a decompressor
which will allow you to uncompress from SRAM (bios functions can't do that),
at this address : 

http://www.geocities.com/dkl_74/

Happy coding,
DKL (dkl_74@yahoo.fr)

All content is copyright of the respective authors and copyright holders.
