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

*******************************************************************************
0. UPDATE
   ------
   
   After some tests, worst cases scenarios are too slow to be acceptable. And
   these scenarios are very probable. I included this version in the package
   though, in case you intend to compress only little files (4 or 8 Kbytes),
   and are nearly out of ram. In all other cases, please use the faster
   implementation, based on binary trees, which needs 25088 bytes of 
   temporary space.
*******************************************************************************
   
   
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 a small hash table
   to sort strings. That means two things. 
   
   Compared to, say, a binary tree implementation :
   - less memory needed,
   - slower.
   
   How much slower? I would say that it's acceptable. Give it a chance,
   test it (on real hardware, emulators are really bad in profiling),
   and decide if it suits your needs.
   
   Temporary space needed is 10240 bytes by default (can be less or more).
   
   Space needed by some other FASTER 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 should be in IWRAM too; 
      if you can't afford it, EWRAM will do it but much 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) You can choose between 5 different sizes for the temporary buffer :
   
      - WORK_8K5 : small size (8704 bytes) but the slowest,
      - WORK_09K : small size (9 Kbytes) but slow,
      - WORK_10K : medium size (10 Kbytes), the best choice if you want a 
                   good balance between size and speed,
      - WORK_12K : larger size (12 Kbytes), only a little faster, 
                   if you can affort it,
      - WORK_16K : largest (16 Kbytes), only a little faster,
                   if you can affort it,
   
   b) - BIGGER_FASTER_INSERT : little larger code size, big boost,
   
   c) - BIGGER_FASTER_DELETE : little larger code size, medium boost,
   
   d) - BIGGER_FASTER_DELINS : larger code size, small boost,
   
   e) - CALLED_MULTI_TIMES : larger code size, if you intend to call
                             the function 100000 times in a row (forget it),
                             
   f) - 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 : WORK_10K, BIGGER_FASTER_INSERT, BIGGER_FASTER_DELETE.
   

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.


Happy coding,
DKL (dkl_74@yahoo.fr)

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