lzrw1_test.c

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <inttypes.h>
#include <fcntl.h>

#ifdef TEST

#if defined(_WIN32) || defined(_WIN64)
#define WINDOWS
#include <windows.h>
#include "mmap.h"
#if defined(_MSC_VER)
#pragma comment(lib, "advapi32.lib")
#pragma comment(lib, "user32.lib")
#endif
#else
#define LINUX
#include <unistd.h>
#include <sys/types.h>
#include <sys/mman.h>
#endif

#define PS *p++!=*s++  /* Body of inner unrolled matching loop.         */
#define ITEMMAX 16     /* Maximum number of bytes in an expanded item.  */

uint32_t lzrw1_compress(uint8_t *inbuf, uint32_t inlen, uint8_t *outbuf) {
    uint8_t *in=inbuf,*out=outbuf;
    uint8_t *p_src_post=inbuf+inlen,*p_dst_post=outbuf+inlen;
    uint8_t *p_src_max1=p_src_post-ITEMMAX,*p_src_max16=p_src_post-16*ITEMMAX;
    uint8_t *hash[4096]={0},*p_control; uint16_t ctrl=0,bits=0;

    p_control=out; out+=2;

    for(;;) {
      uint8_t *p,*s; uint16_t unroll=16,len,index; uint32_t ofs;
      if (out>p_dst_post) return 0;
      if (in>p_src_max16)
        {unroll=1;
         if (in>p_src_max1)
           {if (in==p_src_post) break; goto literal;}}
      begin_unrolled_loop:
         index=((40543*((((in[0]<<4)^in[1])<<4)^in[2]))>>4) & 0xFFF;
         p=hash[index]; hash[index]=s=in; ofs=s-p;
         if (ofs>4095 || p<inbuf || ofs==0 || PS || PS || PS) {
           literal: 
            *out++=*in++; ctrl>>=1; bits++;
         } else {
          PS || PS || PS || PS || PS || PS || PS ||
          PS || PS || PS || PS || PS || PS || s++; 
          len=s-in-1;
          *out++=((ofs&0xF00)>>4)+(len-1); 
          *out++=ofs&0xFF;
          in+=len; 
          ctrl=(ctrl>>1)|0x8000; 
          bits++;
        }
      end_unrolled_loop: if (--unroll) goto begin_unrolled_loop;
      if (bits==16)
        {*p_control=ctrl&0xFF; *(p_control+1)=ctrl>>8;
         p_control=out; out+=2; ctrl=bits=0;}
     }
    ctrl>>=16-bits;
    *p_control++=ctrl&0xFF; *p_control++=ctrl>>8;
    if (p_control==out) out-=2;

    return (out - outbuf);
}
#endif

uint32_t lzrw1_decompress(void *inbuf, uint32_t inlen, void *outbuf) {
    uint32_t bits=0, ctrl, ofs, len;
    uint8_t *in=(uint8_t*)inbuf;
    uint8_t *out=(uint8_t*)outbuf;
    uint8_t *end=(uint8_t*)inbuf + inlen;
    uint8_t *ptr, c;
    
    while(in != end) {
      // read the length
      if(bits == 0) {
        ctrl = (*(uint16_t*)in); 
        in += 2;
        bits  = 16;
      }
      // compressed block?
      if(ctrl & 1) {
        c = *in++;
        // read the 4-bit length
        len  = (c & 0x0F) + 1;
        // read the 12-bit offset
        ofs  = (c & 0xF0) << 4;
        ofs |= *in++ & 0xFF;
        // calculate offset
        ptr  = out - ofs;
        // store bytes
        while(len--) *out++ = *ptr++;
      } else {
        *out++ = *in++;
      }
      ctrl >>= 1; bits--;
    }
    return (out - (uint8_t*)outbuf);
}

/**
; LZRW1 decompressor in 64 bytes of x86 assembly
; odzhan

    bits 32
    
    %ifndef BIN
      global lzrw1_decompressx
      global _lzrw1_decompressx
    %endif
    
lzrw1_decompressx:
_lzrw1_decompressx:
    pushad
    lea    esi, [esp+32+4]
    lodsd
    xchg   eax, ecx        ; ecx = inlen
    lodsd
    xchg   edi, eax        ; edi = outbuf
    lodsd
    xchg   esi, eax        ; esi = inbuf
    lea    ebp, [esi+ecx]  ; ebp = inbuf + inlen
L0:
    push   16 + 1          ; bits = 16
    pop    edx
    lodsw                  ; ctrl = *in++, ctrl |= (*in++) << 8
    xchg   ebx, eax        
L1:
    ; while(in != end) {
    cmp    esi, ebp
    je     L4
    ; if(--bits == 0) goto L0
    dec    edx
    jz     L0
L2:
    ; if(ctrl & 1) {
    shr    ebx, 1
    jnc    L3

    xor    eax, eax
    lodsb                  ; ofs = (*in & 0xF0) << 4
    aam    16
    movzx  ecx, al
    inc    ecx
    lodsb                  ; ofs |= *in++ & 0xFF;
    push   esi             ; save pointer to in
    mov    esi, edi        ; ptr  = out - ofs;
    sub    esi, eax
    rep    movsb           ; while(len--) *out++ = *ptr++;
    pop    esi             ; restore pointer to in
    jmp    L1
L3:
    ; } else {
    movsb                  ; *out++ = *in++;
    jmp    L1
    ; }
L4:
    sub    edi, [esp+32+8] ; edi = out - outbuf
    mov    [esp+28], edi   ; esp+_eax = edi
    popad
    ret
*/
uint32_t lzrw1_decompressx(uint32_t, void*, void*);

#ifdef TEST
int main(int argc, char *argv[]) {
    struct stat fs;
    int         fd;
    uint32_t    inlen, outlen, diff, unpcklen;
    void        *inbuf, *outbuf, *unpacked;
    char        *infile, *outfile;
    
    if(argc != 2) {
      printf("usage: lzrw1 <infile>\n");
      return 0;
    }
    
    infile = argv[1];
    
    if(stat(infile, &fs) != 0) {
      printf("unable to access %s\n", infile);
      return -1;
    }
    
    // open
    fd = open(infile, O_RDONLY);
    if(fd < 0) {
      printf("unable to open %s.\n", infile);
      return -1;
    }
    
    // map input file
    inlen = fs.st_size;
    inbuf = mmap(NULL, inlen, PROT_READ, MAP_PRIVATE, fd, 0);
      
    if(inbuf != NULL) {
      // allocate buffer for output
      outbuf = malloc(inlen);
      if(outbuf != NULL) {
        // compress data
        outlen = lzrw1_compress(inbuf, inlen, outbuf);
        if(outlen == 0) {
          printf("compression failed.\n");
        } else {
          // show the ratio
          diff = ((float)(inlen - outlen) / (float)inlen) * 100;
          printf("oiginal size: %"PRId32"\n"
                 "packed  size: %"PRId32"\n"
                 "reduced by %"PRId32"%%\n", inlen, outlen, diff);
        
          // decompress
          unpacked = malloc(inlen);
          unpcklen = lzrw1_decompressx(outlen, unpacked, outbuf);

          // show the ratio
          diff = ((float)(unpcklen - outlen) / (float)unpcklen) * 100;
          printf("\npacked size: %"PRId32"\n"
                 "unpacked size: %"PRId32"\n"
                 "increased by %"PRId32"%%\n", outlen, unpcklen, diff);
          free(unpacked);                 
        }
        free(outbuf);
      } else {
        printf("malloc() failed.\n", infile);
      }
      munmap(inbuf, inlen);
    } else {
      printf("mmap() failed.\n");
    }
    close(fd);
    return 0;
}
#endif